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

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

Problem Definition: Variable-Delay Real-Time RL

Standard Reinforcement Learning (RL) and Markov Decision Processes (MDPs) operate under the assumption that the environment waits indefinitely for the agent to compute an action; thus, deliberation carries no cost. In real-time settings, this assumption fails: the environment progresses continuously regardless of the agent's computation time. A perfect action executed too late is often inferior to a timely, suboptimal action.

While prior work (Ramstedt & Pal, 2019) formalized real-time RL with a fixed delay (e.g., exactly one timestep to compute), this paper introduces Variable-Delay Real-Time RL. In this framework, the agent is not a static function but a procedure running in time. The agent must decide how long to deliberate at each decision point. The cost of deliberation is "paid" as environmental progress (or clock depletion in board games) while the agent computes. This creates a meta-reasoning challenge: the agent must balance the quality of the planned action against the degradation of the state caused by the time spent planning. Naively planning how long to plan risks a paradox where the meta-decision itself incurs the same real-time costs as the planning it seeks to optimize.

Methodology

The authors propose a solution based on a Semi-Markov Decision Process (SMDP) over budgeted options, decoupling the planning algorithm from the decision of how much to plan.

1. Architecture Components:

   • Reflex Policy ($\pi_{reflex}$): A fast, lightweight policy (e.g., the policy head of an AlphaZero model without MCTS) that runs in well under one frame. It supplies immediate actions for the environment while the planner runs in the background.
   • Anytime Action-Refinement Computations ($\{c_k\}$): A finite set of computations indexed by discrete duration $k$. In this work, these are instantiated as Monte Carlo Tree Search (MCTS) runs for $k$ frames. Longer runs ($c_k$) produce higher-quality actions but take more time.
   • Budgeted Options ($o_k$): Each option $o_k$ wraps a computation $c_k$. When initiated, the agent commits to executing $k-1$ actions drawn from $\pi_{reflex}$ while $c_k$ runs. On the $k$-th frame, the refined action from $c_k$ is executed.
   • Gating Policy ($\pi_{gate}$): A lightweight neural network trained via Proximal Policy Optimization (PPO) that acts as a meta-policy. It observes the current state (game observation, planner features, and value estimates) and selects the budget $k$ (the duration of the option) for the next meta-step.

2. Training Protocol:

   • Two-Phase Training: First, base AlphaZero-style planners are trained for specific environments. These planners are then frozen. Second, the gating policy is trained on top of the frozen planner.
   • Meta-MDP Formulation: The gating policy solves a discrete control problem where actions are the selection of budgeted options. The reward is the cumulative return over the $k$ frames of the option, discounted by $\gamma^k$.
   • Adapted GAE: Because meta-steps have variable durations ($k$), the authors adapt Generalized Advantage Estimation (GAE) to carry the per-meta-step discount $\gamma^k$ through the advantage computation.

3. Environment Instantiations:

   • Committed-Action Environments (Pac-Man, Real-Time Tetris, Snake): The environment progresses continuously. The agent executes $k-1$ reflex actions while planning. The cost of planning is the world state changing during the computation.
   • Clock Environments (Speed Hex, Speed Go): The board is static, but a shared clock depletes with thinking time. The reflex policy emits "no-ops" during the planning window. The cost is the reduction of the remaining time budget.

Key Contributions

1. Variable-Delay Real-Time RL Framework: A generalization of fixed-delay frameworks where the agent chooses its own deliberation time, treating delay selection as a learnable problem rather than a system-imposed constraint.
2. Empirical Characterization of Planning Trade-offs: The authors establish that planning quality and inference latency scale together with MCTS simulation counts. This joint scaling motivates the need for adaptive allocation rather than fixed budgets.
3. Adaptive Gating on Frozen Planners: A method to learn state-dependent planning budgets using a lightweight gating policy trained on top of a frozen AlphaZero planner. This avoids the "planning-about-planning" paradox because a single gate forward pass is orders of magnitude cheaper than an MCTS rollout.
4. Real-World Hardware Validation: The method is validated in a true asynchronous, two-GPU deployment (one GPU for the environment/reflex, one for MCTS) without architectural changes or retraining, demonstrating that the simulation-trained policy transfers effectively to hardware-separated execution.

Results

The gating policy was evaluated across five environments: Pac-Man, Real-Time Tetris, Snake, Speed Hex, and Speed Go.

• Performance vs. Baselines: The adaptive gating policy consistently outperformed:
  • Fixed-Budget Policies: Agents constrained to a single $k$ (e.g., always planning for 1, 2, 3, or 4 frames).
  • Heuristic Baselines: Including "Greedy" (always max simulations) and "Midpeak" (bell-curve allocation common in game engines).
  • Random Baselines: Randomly selecting budgets performed significantly worse, confirming that when to allocate compute is as critical as how much.
• Specific Gains:
  • Pac-Man: +10.3% improvement over the best fixed budget.
  • Real-Time Tetris: +65% improvement over the best fixed budget.
  • Snake: +10.9% improvement.
  • Speed Hex/Go: The gating policy achieved higher expected scores than both fixed budgets and heuristics across varying clock constraints.
• Behavioral Analysis: The gating policy learned to allocate deeper planning (higher $k$) in high-stakes or constrained states (e.g., ghosts close in Pac-Man, dense boards in Tetris, low reachability in Snake) and reacted quickly (low $k$) in safe or open states. It also demonstrated generalization to different clock budgets in Speed Hex/Go without retraining.
• Hardware Transfer: In a two-GPU asynchronous setup (H100, A100, A40), the policies transferred cleanly from simulation to real hardware. Latency remained within budget on H100 and A100, and returns matched simulation counterparts closely.

Significance and Claims

The paper claims to address a fundamental mismatch between standard RL and real-time interaction by formalizing deliberation time as a resource that must be managed dynamically. The significance lies in:

• Escaping the Meta-Reasoning Paradox: By using a lightweight gate on a frozen planner, the system avoids the computational overhead of planning how to plan, making the approach practical for real-time deployment.
• State-Dependent Resource Allocation: The results demonstrate that a single fixed planning budget is suboptimal; the value of computation is highly state-dependent.
• Scalability to Asynchronous Hardware: The "committed-action" training protocol successfully models the dynamics of asynchronous execution, allowing policies trained in simulation to deploy on separate hardware (environment vs. planner) without modification.

Limitations Acknowledged:

• The framework assumes a perfect environment simulator for the committed steps (MCTS must accurately predict the $k-1$ reflex actions).
• The gating policy is trained on a frozen planner; joint optimization of the planner and gate is left as future work.
• The budget set $\mathcal{K}$ is hand-calibrated and discrete; continuous or richer compute vocabularies are suggested as future extensions.