Finding the Time to Think: Learning Planning Budgets in Real-Time RL

기술 요약: 생각할 시간 찾기: 실시간 RL에서의 계획 예산 학습

문제 정의: 가변 지연 실시간 RL (Variable-Delay Real-Time RL)

표준 강화학습(RL)과 마르코프 결정 과정(MDP)은 에이전트가 행동을 계산하는 동안 환경이 무한정 기다려준다는 가정하에 작동합니다. 즉, 숙고(deliberation)에 따른 비용이 발생하지 않습니다. 그러나 실시간 설정에서는 이 가정이 성립하지 않습니다. 에이전트의 계산 시간과 관계없이 환경은 지속적으로 진행됩니다. 너무 늦게 실행된 완벽한 행동은 적시에 실행된 차선책보다 종종 열등합니다.

이전 연구(Ramstedt & Pal, 2019)는 고정된 지연 시간(예: 계산을 위해 정확히 1 타임스텝 소요)을 가진 실시간 RL을 정형화했지만, 본 논문은 가변 지연 실시간 RL을 도입합니다. 이 프레임워크에서 에이전트는 정적인 함수가 아니라 시간 속에서 실행되는 절차입니다. 에이전트는 각 결정 시점에서 얼마나 오래 숙고할지를 결정해야 합니다. 숙고의 비용은 에이전트가 계획을 수행하는 동안 발생하는 환경의 진행(또는 보드 게임에서의 클락 소모)으로 "지불"됩니다. 이는 메타 추론(meta-reasoning) 과제를 생성합니다. 즉, 에이전트는 계획의 품질과 숙고 시간 동안 발생하는 상태의 저하 사이에서 균형을 잡아야 합니다. 계획하는 방법을 계획하는 행위 자체가 최적화하고자 하는 계획과 동일한 실시간 비용을 초래하는 역설에 빠질 위험이 있습니다.

방법론

저자들은 계획 알고리즘과 '얼마나 많이' 계획할 것인가에 대한 결정을 분리하는, 예산이 책정된 옵션(budgeted options) 기반의 **준마르코프 결정 과정(Semi-Markov Decision Process, SMDP)**을 제안합니다.

1. 아키텍처 구성 요소:

   • 반사 정책 ($\pi_{reflex}$): 한 프레임 미만의 매우 짧은 시간 내에 실행되는 빠르고 가벼운 정책(예: MCTS가 없는 AlphaZero 모델의 정책 헤드)입니다. 플래너가 백그라운드에서 실행되는 동안 즉각적인 행동을 공급합니다.
   • 언제든 사용 가능한 행동 정밀화 계산 ($\{c_k\}$): 이산적인 지속 시간 $k$에 의해 인덱싱된 유한한 계산 집합입니다. 본 연구에서는 이를 $k$ 프레임 동안의 몬테카를로 트리 탐색(MCTS) 실행으로 구현했습니다. 더 긴 실행($c_k$)은 더 높은 품질의 행동을 생성하지만 더 많은 시간이 소요됩니다.
   • 예산 옵션 ($o_k$): 각 옵션 $o_k$는 계산 $c_k$를 래핑합니다. 옵션이 시작되면, 에이전트는 $c_k$가 실행되는 동안 $\pi_{reflex}$로부터 추출된 $k-1$개의 행동을 실행하기로 확정합니다. $k$번째 프레임에 정밀화된 행동이 실행됩니다.
   • 게이팅 정책 ($\pi_{gate}$): PPO를 통해 학습된 가벼운 신경망으로, 메타 정책 역할을 합니다. 현재 상태(게임 관측값, 플래너 특징, 가치 추정치)를 관찰하고 다음 메타 스텝을 위한 예산 $k$(옵션의 지속 시간)를 선택합니다.

2. 학습 프로토콜:

   • 2단계 학습: 먼저 특정 환경에 대해 베이스 AlphaZero 스타일의 플래너를 학습시킵니다. 그 후 이 플래너들을 **동결(frozen)**합니다. 두 번째로, 동결된 플래너 위에서 게이팅 정책을 학습시킵니다.
   • 메타-MDP 정형화: 게이팅 정책은 옵션의 선택을 행동으로 하는 이산 제어 문제를 해결합니다. 보상은 $k$ 프레임 동안의 누적 수익이며, $\gamma^k$로 할인됩니다.
   • 적응형 GAE: 메타 스텝의 지속 시간($k$)이 가변적이기 때문에, 저자들은 per-meta-step 할인 $\gamma^k$를 어드밴티지 계산에 전달하도록 일반화된 어드밴티지 추정(GAE)을 수정했습니다.

3. 환경 구현:

   • 확정 행동 환경 (Pac-Man, Real-Time Tetris, Snake): 환경이 연속적으로 진행됩니다. 에이전트는 계획하는 동안 $k-1$개의 반사 행동을 실행합니다. 계획의 비용은 계산 중에 변화하는 세계의 상태입니다.
   • 클락 환경 (Speed Hex, Speed Go): 보드는 정적이지만, 공유된 클락이 생각하는 시간과 함께 줄어듭니다. 반사 정책은 계획 창 동안 "no-op(아무것도 하지 않음)"을 출력합니다. 비용은 남은 시간 예산의 감소입니다.

주요 기여

1. 가변 지연 실시간 RL 프레임워크: 지연 선택을 시스템이 부과한 제약이 아닌 학습 가능한 문제로 취급함으로써, 고정 지연 프레임워크를 일반화했습니다.
2. 계획 트레이드오프의 경험적 특성화: 저자들은 계획 품질과 추론 레이턴시가 MCTS 시뮬레이션 횟수와 함께 스케일링된다는 점을 입증했습니다. 이러한 공동 스케일링은 고정된 예산보다는 적응형 할당의 필요성을 뒷받적합니다.
3. 동결된 플래너 상의 적응형 게이팅: 동결된 AlphaZero 플래너 위에서 학습된 가벼운 게이팅 정책을 사용하여 상태 의존적 계획 예산을 학습하는 방법입니다. 이는 게이팅 정책의 순방향 패스가 MCTS 롤아웃보다 수만 배 저렴하므로 "계획에 대한 계획"이라는 역설을 피할 수 있게 합니다.
4. 실제 하드웨어 검증: 제안된 방법은 아키텍처 변경이나 재학습 없이 진정한 비동기식 2-GPU 배치(환경/반사용 GPU 하나, MCTS용 GPU 하나)에서 검증되었으며, 이는 시뮬레이션에서 학습된 정책이 하드웨어 분리 실행에 효과적으로 전이됨을 보여줍니다.

결과

게이팅 정책은 Pac-Man, Real-Time Tetris, Snake, Speed Hex, Speed Go의 다섯 가지 환경에서 평가되었습니다.

• 베이스라인 대비 성능: 적응형 게이팅 정책은 다음 모델들을 일관되로 능가했습니다:
  • 고정 예산 정책: 단일 $k$ 값에 제한된 에이전트 (예: 항상 1, 2, 3 또는 4 프레임 동안 계획).
  • 휴리스틱 베이스라인: "Greedy"(항상 최대 시뮬레이션) 및 게임 엔진에서 흔히 쓰이는 "Midpeak"(종 모양 분포 할당)를 포함합니다.
  • 랜덤 베이스라인: 예산을 무작위로 선택하는 것은 성능이 현저히 낮았으며, 이는 언제 계산량을 할당할지가 얼마나 많이 할당할지만큼 중요하다는 것을 확인시켜 줍니다.
• 구체적 이득:
  • Pac-Man: 최적의 고정 예산 대비 +10.3% 향상.
  • Real-Time Tetris: 최적의 고정 예산 대비 +65% 향상.
  • Snake: +10.9% 향상.
  • Speed Hex/Go: 게이팅 정책은 다양한 클락 제약 조건 하에서 고정 예산 및 휴리스틱보다 높은 기대 점수를 달성했습니다.
• 행동 분석: 게이팅 정책은 고위험 또는 제약이 있는 상태(예: Pac-Man에서 유령이 가까이 있는 경우, Tetris의 밀집된 보드, Snake의 도달 가능성이 낮은 상태)에서 더 깊은 계획(높은 $k$)을 할당하고, 안전하거나 열린 상태에서는 빠르게 반응(낮은 $k$)하는 법을 학습했습니다. 또한 Speed Hex/Go에서 재학습 없이 다른 클락 예산에 대해서도 일반화 능력을 보여주었습니다.
• 하드웨어 전이: 두 개의 GPU 비동기 설정(H100, A100, A40)에서, 정책은 수정 없이 시뮬레이션에서 실제 하드웨어로 깔끔하게 전이되었습니다. 레이턴시는 H100 및 A100에서 예산 범위 내에 머물렀으며, 리턴 값은 시뮬레이션 결과와 밀접하게 일치했습니다.

의의 및 주장

본 논문은 실시간 상호작용과 표준 RL 사이의 근본적인 불일치를 해결하기 위해 숙고 시간을 동적으로 관리해야 할 자원으로 정형화함으로써 이를 해결한다고 주장합니다. 그 의의는 다음과 같습니다:

• 메타 추론 역설 탈출: 동결된 플래너 위에 가벼운 게이트를 사용함으로써, 시스템은 계획하는 방법을 계획하는 데 드는 계산 오버헤드를 피하며, 이는 실제 배포에 실용적입니다.
• 상태 의존적 자원 할당: 결과는 단일 고정 계획 예산이 최적이 아니며, 계산의 가치는 상태에 따라 크게 달라진다는 것을 입증합니다.
• 비동기 하드웨어로의 확장성: "확정 행동" 학습 프로토콜은 비동기 실행의 역학을 성공적으로 모델링하여, 시뮬레이션에서 학습된 정책이 수정 없이 환경과 플래너가 분리된 하드웨어에 배포될 수 있게 합니다.

인정된 한계점:

• 본 프레임워크는 확정 단계에 대해 완벽한 환경 시뮬레이터를 가정합니다 (MCTS가 $k-1$개의 반사 행동을 정확하게 예측해야 함).
• 게이팅 정책은 동결된 플래너를 대상으로 학습됩니다. 플래너와 게이트의 공동 최적화는 향후 과제로 남겨두었습니다.
• 예산 집합 $\mathcal{K}$는 수동으로 캘리브레이션된 이산 값입니다. 연속적이거나 더 풍부한 계산 어휘(vocabularies)를 사용하는 방식이 향후 확장안으로 제안되었습니다.