Abstract
In this paper, we study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraints on the number of batches. The multi-batch reinforcement learning framework requires the agent to provide a time schedule to update policies in advance, which is particularly suitable for scenarios where the agent suffers extensively from changing the policy adaptively. Given a finite-horizon MDP with $S$ states, $A$ actions, and planning horizon $H$, we design a computationally efficient algorithm to achieve near-optimal regret of $\tilde{O}(\sqrt{SAH^3K\ln(1/\delta)})$ in $K$ episodes using $O(H+\log_2\log_2(K))$ batches. To our best knowledge, it is the first $\tilde{O}(\sqrt{SAH^3K})$ regret bound with $O(H+\log_2\log_2(K))$ batch complexity. Meanwhile, we show that to achieve $\tilde{O}(\mathrm{poly}(S,A,H)\sqrt{K})$ regret, the number of batches is at least $\Omega(H/\log_A(K)+ \log_2\log_2(K))$, which matches our upper bound up to logarithmic terms. Our technical contributions are two-fold: 1) a near-optimal design scheme to explore over unlearned states; and 2) a computationally efficient algorithm to explore certain directions with an approximated transition model.
Introduction
In standard Reinforcement Learning (RL), an agent typically updates its strategy adaptively—often after every single episode—to balance exploring new states and exploiting known rewards. While this leads to low "regret" (the difference between the agent's performance and the optimal strategy), it presents significant hurdles for real-world deployment.
Frequent policy changes are problematic for two primary reasons:
- Parallelism: If a policy must change every episode, one cannot easily run thousands of simulations or trials in parallel.
- Deployment Costs: In fields like medicine or hardware optimization, changing a policy (e.g., a patient's treatment plan or a chip's logic) requires expensive expert review or time-consuming re-compilation.
This paper addresses the Multi-batch RL framework, where the agent must decide the number and length of "batches" before the learning process begins. Within a batch, the policy remains fixed, allowing for massive parallelism. The central challenge is determining how few batches can be used while still achieving the theoretical "gold standard" for regret.
Methodology
The authors propose a framework based on Policy Elimination and a novel exploration design. Their approach consists of three main stages:
1. Raw Exploration (Stages 1 & 2)
The agent identifies "infrequent" state-action-state triples—parts of the environment that are difficult to reach. By redirecting these to a virtual "absorbed" state, the algorithm simplifies the model and focuses on the reachable state space.
2. Policy Elimination (Stage 3)
The agent maintains a confidence region of possible transition models. Before each batch, it eliminates policies that are demonstrably sub-optimal based on the data collected in previous batches.
3. Near-Optimal Design Scheme
To decide which policy to run in the next batch, the authors use a design scheme that ensures the data collected provides a "proper coverage ratio" for all remaining viable policies. This prevents the agent from missing critical information due to the lack of real-time policy updates.
A key technical innovation is the Sum operator, which allows the agent to combine multiple exploration policies into a single, history-independent policy that can be executed efficiently without increasing the complexity of the agent's decision-making process.
Theoretical Contributions
Upper Bound
The proposed algorithm achieves a regret of $\tilde{O}(\sqrt{SAH^3K})$ with a batch complexity of $O(H + \log_2 \log_2 K)$. This is the first result to achieve this near-optimal regret level with such low batch requirements. Unlike previous theoretical RL algorithms that are mathematically sound but computationally intractable, this algorithm is "computationally efficient," meaning it runs in polynomial time relative to the MDP's parameters.
Lower Bound
The authors prove that to achieve any regret that is polynomial in $S, A, H$ and $\sqrt{K}$, an agent fundamentally requires at least $\Omega(H/\log_A K + \log_2 \log_2 K)$ batches. This demonstrates that their upper bound is nearly "tight" (optimal) and that the batch complexity is driven by two distinct factors:
- The $H$ term: Required to explore the sequential structure of the MDP.
- The $\log \log K$ term: Required to refine the policy, mirroring results seen in simpler multi-armed bandit problems.
Key Insights
- Bridging the Gap: Previous work either suffered from high switching costs or required "triggers" that monitored data in real-time (preventing true batching). This paper provides a schedule that is fixed before the batch starts.
- Tightness Matters: By ensuring the estimated occupancy distribution is within a constant ratio of the true distribution, the authors can use computationally efficient linear programming to find exploration policies.
Limitations and Future Work
While this work provides a significant theoretical breakthrough, several areas remain for future exploration:
- Tabular Constraint: The current results are limited to "tabular" RL, where the number of states ($S$) and actions ($A$) are finite. Generalizing these results to RL with function approximation (e.g., Linear MDPs or Deep RL) is a critical next step for scaling to continuous state spaces.
- Constant Factors: While the "Big-O" complexity is optimal, the constant factors in the regret bound remain large, which may limit immediate application in scenarios with very small sample sizes.
In conclusion, this paper establishes that we can drastically reduce the need for adaptivity in RL without significantly sacrificing performance, providing a robust theoretical foundation for more efficient, parallelizable reinforcement learning.
Summary updated