In episodic reinforcement learning (RL), an agent interacts with an environment in sequences of a fixed length, known as the planning horizon $H$. For years, a fundamental challenge in RL theory has been the "curse of the horizon": the way sample complexity and regret bounds scale with $H$.
Early theoretical frameworks often produced loose bounds showing that the number of samples required to learn an optimal policy scaled cubically ($H^3$) or quartically ($H^4$) with the horizon. This created a massive disconnect between theory and practice. In practice, long-horizon tasks are challenging due to credit assignment, but they do not require the astronomically large datasets predicted by naive models.
Recent breakthroughs have bridged this gap by developing horizon-free or horizon-tight bounds. Understanding why these bounds work requires looking at how errors compound over time and how we can use the intrinsic variance of the environment to stop this inflation.
The Root of the Curse: Compounding Worst-Case Errors
To understand why traditional bounds scale poorly with $H$, consider how an RL agent estimates the value of a state. The value of a state is the expected sum of future rewards. If an agent's estimate of the reward at any single step has an uncertainty of $\epsilon$, a naive worst-case analysis assumes that these uncertainties add up linearly over the course of the episode. Over a horizon of $H$ steps, the total uncertainty in the value function scales as $H\epsilon$.
When proving regret bounds, this $H$ factor compounds. For instance, in model-free or model-based exploration algorithms, this uncertainty dictates the size of the optimistic "bonus" given to unexplored states. Because the bonus is inflated by $H$, the agent explores too conservatively or requires far more samples to settle on an optimal policy. As noted by Christoph Dann et al. in Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning, early sample complexity models overpredicted data requirements precisely because they failed to account for how these errors interact across sequential steps.
Conversely, theoretical models sometimes obscured this difficulty through artificial reward normalization (e.g., scaling rewards to sum to 1). As argued by Nan Jiang et al. in Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon, this practice makes sample complexity appear independent of the horizon in theory, while failing to reflect the practical challenges of exploration and credit assignment in long sequences.
The Solution: The Law of Total Variance
The key to breaking the horizon dependence is moving away from worst-case concentration inequalities (like Hoeffding's inequality) and adopting variance-aware concentration inequalities (like Bernstein's inequality).
Hoeffding's inequality assumes that every step introduces maximum uncertainty. Bernstein's inequality, however, scales the uncertainty bonus based on the actual variance of the next-state value function. The core mathematical intuition relies on the Law of Total Variance for MDPs. This law states that the sum of the conditional variances of the value function along a trajectory is bounded by the total range of the cumulative reward, rather than $H$ times the maximum single-step variance.
If an environment is deterministic, or if the total reward an agent can collect is tightly bounded, the actual variance across a trajectory is incredibly small, even if $H$ is large. By embedding this variance directly into the confidence sets of the transitions, the algorithm can drastically reduce its exploration bonuses.
Mohammad Gheshlaghi Azar et al. pioneered this approach in On the Sample Complexity of Reinforcement Learning with a Generative Model, using a variance-based analysis to close the gap between upper and lower bounds for value iteration. Instead of paying a penalty for $H$ at every step, the variance-aware analysis ensures that the error bounds scale with the true stochasticity of the trajectory.
Constructing Horizon-Free Confidence Sets
To achieve true "horizon-free" bounds—where the performance guarantees scale logarithmically with or are completely independent of $H$—the agent must maintain tight confidence sets even when dealing with function approximation.
In environments with large state spaces, linear function approximation is often used to generalize across states. However, controlling the propagation of variance through a linear model over a long horizon is notoriously difficult. The authors of Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP solved this by introducing a "peeling" technique. This method breaks the parameter space into fine-grained shells based on variance levels, allowing the algorithm to construct confidence sets that adapt to the noise of the environment. This effectively achieved a logarithmic dependency on the horizon for linear mixture MDPs.
Furthermore, Runlong Zhou et al. demonstrated in Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments that by leveraging these sharp variance metrics, algorithms can automatically achieve minimax regret in highly stochastic environments while collapsing to near-zero regret in deterministic worlds, completely bypassing the temporal curse of dimensionality.
Standard Analysis (Hoeffding):
Step 1 (Error: ε) -> Step 2 (Error: 2ε) -> ... -> Step H (Error: Hε)
Result: Regret scales polynomially with H.
Variance-Aware Analysis (Bernstein + Total Variance):
Step 1 (Var_1) -> Step 2 (Var_2) -> ... -> Step H (Var_H)
Result: Σ Var_i ≤ Total Reward Range. Regret scales logarithmically with H.
Exploiting Instance-Specific Gaps
Another powerful mechanism for eliminating horizon dependence is exploiting the sub-optimality gap ($\Delta$). The gap is the difference in expected value between the optimal action and the best sub-optimal action in a given state.
If an environment has large sub-optimality gaps, the problem becomes significantly easier: once the agent's uncertainty drops below $\Delta$, it will never choose the sub-optimal action again. Max Simchowitz et al. utilized this in Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs by introducing a "clipping" analysis technique. This technique clips the exploration bonuses once the statistical evidence is strong enough to rule out sub-optimal actions, yielding logarithmic regret bounds that adapt directly to the environment's difficulty rather than its worst-case horizon length.
This philosophy is fully realized in algorithms like EULER, introduced by Andrea Zanette et al. in Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds. EULER simultaneously bounds the environmental variance and the sub-optimality gaps. Because it tracks both upper and lower bounds on the value function, it automatically provides tighter guarantees for "easy" problems (like deterministic paths or bandit-like tasks) without requiring any prior knowledge from the designer.