How much data does an agent need to learn a near-optimal policy? This question lies at the heart of reinforcement learning (RL) theory. If an algorithm requires too many samples, it becomes impractical for real-world deployment; if it requires too few, it might be mathematically impossible.
To map these boundaries, researchers focus on minimax-optimal sample complexity—the absolute minimum number of environment interactions required by any algorithm to guarantee an $\epsilon$-optimal policy under the worst possible environment configurations. Achieving minimax optimality means an algorithm's upper bound on data requirements perfectly matches the information-theoretic lower bound of the problem class.
Over the last two decades, the RL theory community has systematically closed the gaps between upper and lower bounds across increasingly complex settings. By unpacking how these algorithms work, we can understand the core mechanisms—such as variance reduction, primal-dual balancing, and horizon-matching—that allow agents to reach the absolute speed limits of learning.
Shaving the Horizon: Variance Reduction in Simulators
The foundational sandbox for sample complexity analysis is the generative model (or simulator) setting, where an agent can query transitions from any arbitrary state-action pair.
In a discounted infinite-horizon Markov Decision Process (MDP), the effective planning horizon is dictated by the discount factor $\gamma$, roughly corresponding to $1/(1-\gamma)$ steps. Early tabular algorithms suffered from loose sample complexity bounds because errors compounded quadratically or cubically across this horizon.
The breakthrough in finding the exact statistical floor came from a refined understanding of how variance propagates through Bellman equations. Azar et al. demonstrated that the true minimax-optimal sample complexity for a generative model scales exactly with $\mathcal{O}((1-\gamma)^{-3}\epsilon^{-2})$.
To understand why this works intuitively, consider how standard Value Iteration updates its estimates. At each step, it samples next-state transitions, introducing statistical noise. If analyzed naively, this noise accumulates over the effective horizon. To counteract this, Sidford et al. introduced Variance-Reduced Q-Value Iteration (vQVI).
Instead of blindly re-sampling transitions at every iteration, vQVI occasionally freezes a "reference" value function and computes its exact expectation. In subsequent iterations, the algorithm only samples the deviations from this reference point. Because the variance of these deviations is significantly lower than the variance of the raw transitions, the algorithm prevents error compounding, effectively hitting the information-theoretic speed limit.
Ergodicity and Steady States: Average-Reward MDPs
When moving from discounted MDPs to average-reward MDPs, the safety net of the discount factor $\gamma$ disappears. The agent's performance is evaluated on its long-term steady-state average reward. Here, the difficulty of the environment is no longer governed by an artificial discount, but by the environment's intrinsic geometry: its mixing time ($t_{\text{mix}}$) or span, which measures how long it takes to transition from any state to any other state.
For years, a significant gap remained between the theoretical lower bounds and the best-known algorithms for average-reward settings. The turning point came from bridging average-reward problems back to their discounted counterparts.
Jin et al. and Wang et al. successfully closed this gap, establishing a minimax-optimal rate of $\widetilde{O}(|S||A|t_{\text{mix}}\epsilon^{-2})$.
The core intuition behind this reduction is timescale matching. An average-reward MDP can be approximated by a discounted MDP if the discount factor is chosen carefully to match the mixing scale of the environment (i.e., setting $1-\gamma \approx 1/t_{\text{mix}}$). By combining this reduction with a refined model-based analysis that tracks the steady-state distributions, the authors proved that learning long-term average behaviors does not require quadratically more data than discounted planning. Zurek et al. extended these insights to show that sample complexity scales linearly with the environment's span across both weakly communicating and general average-reward MDPs.
Safety Without Statistical Penalty: Constrained MDPs
In real-world systems like autonomous driving, maximizing rewards is insufficient; the agent must also strictly satisfy safety constraints. This is modeled via Constrained MDPs (CMDPs). Intuitively, forcing an agent to balance multiple competing constraints should make learning harder and require more data. Remarkably, recent algorithmic innovations prove this intuition wrong.
A common approach to solving CMDPs is the primal-dual framework, which converts constraints into dynamic penalties using Lagrange multipliers. The primal step updates the policy to maximize the penalized reward, while the dual step adjusts the penalties based on constraint violations.
Bai et al. demonstrated that a conservative primal-dual approach can achieve zero constraint violations during deployment while maintaining the unconstrained optimal sample complexity of $\tilde{O}(1/\epsilon^2)$.
The mechanism that makes this work is a conservative buffer. If an agent optimizes directly up to the safety boundary, random statistical noise in the empirical data will inevitably cause it to cross into unsafe territory. By shifting the target constraint boundary inward by a buffer proportional to the statistical uncertainty of the data, any fluctuations remain safely within the feasible region.
Standard CMDP: [------- Safe Zone -------|-- Unsafe Zone --]
^ Target Boundary (Risk of violation due to noise)
Conservative: [---- Safe Zone ----|-- Buffer --|-- Unsafe Zone --]
^ Shifted Target (Noise stays in buffer)
Furthermore, Mondal et al. showed that this efficiency carries over to complex, general parameterized policies. By incorporating momentum-based acceleration into the primal-dual updates, the authors proved that the optimization trajectory can be stabilized, completely closing the efficiency gap between simple tabular models and high-dimensional parameterized spaces. This rate holds even under the restrictive conditions of offline learning, as shown by Hong et al..
Eliminating the "Burn-In" Cost in Online Learning
In pure online reinforcement learning, an agent does not enjoy the luxury of a simulator or a pre-collected offline dataset; it must learn entirely through sequential, real-time interaction with the environment.
Historically, proving minimax optimality in this setting required a massive caveat known as a burn-in cost. Theoretical analyses often assumed that the agent had already collected a large initial batch of exploratory data before the optimal sample efficiency kicked in. This created a disconnect between theory and early-stage learning performance.
This theoretical hurdle was recently cleared by Chen et al., who proved that a model-based online algorithm can achieve minimax-optimal regret from the very first episode, entirely eliminating the burn-in requirement.
The reason this works comes down to tight, non-asymptotic tracking of epistemic uncertainty. Instead of relying on loose, global exploration bonuses, the authors utilized refined variance bounds that adaptively scale with the remaining horizon length. By precisely balancing exploration and exploitation at every single step, the agent avoids redundant exploration without needing a data safety net.
In a similar vein, Ma et al. leveraged a probabilistic inference framework to achieve near minimax-optimal sample complexity in infinite-horizon discounted settings without a generative model, demonstrating that sequential interaction can be just as data-efficient as simulator-based learning.
Key Foundational Work
Real-Time Scheduling via Reinforcement Learning (2010) — contributed 2 concept elements to this direction.
Exploration and apprenticeship learning in reinforcement learning (2005) — contributed 1 concept elements to this direction.