Abstract
Reinforcement Learning (RL) performance often degrades as the planning horizon increases. This paper demonstrates that this difficulty is rooted in the representational complexity of the optimal value function. As the discount factor $\gamma$ approaches 1, the Rademacher complexity of the value function space grows, and action-gaps—the difference in value between optimal and sub-optimal actions—collapse. These findings provide a theoretical basis for the necessity of hierarchical decompositions in solving long-horizon tasks.
Introduction
In Reinforcement Learning, the discount factor $\gamma \in [0, 1)$ is the primary lever for controlling an agent's planning horizon. While a long horizon is theoretically necessary for complex, multi-step tasks, practitioners frequently observe that increasing $\gamma$ leads to training instability and failure. Traditional explanations focus on sample inefficiency or exploration difficulties. However, this research suggests a more fundamental bottleneck: the representational complexity of the solution itself.
Theoretical Complexity of Value Functions
The authors utilize Generalized Rademacher Complexity to quantify the "richness" or "wiggliness" of the space of possible optimal value functions. A key theoretical contribution is Theorem 1, which proves that the complexity of the optimal value function space is proportional to $\frac{1}{1-\gamma}$:
$$\mathcal{R}(\mathcal{V}^*_\gamma) = \frac{R_{max}}{2(1-\gamma)}$$
Crucially, this complexity is independent of the number of states or actions. This implies that as the horizon grows, the value function becomes fundamentally harder to represent, requiring neural networks with significantly higher capacity and precision to maintain accuracy.
The Action-Gap Collapse
A second major challenge in Long Horizon Problems (LHPs) is the "action-gap"—the difference between the $Q$-value of the optimal action and the next-best alternative. If this gap is too small, even minor approximation errors in a neural network can lead the agent to select a sub-optimal action.
In environments with "bottlenecks" (states that connect distinct regions), the action-gap often vanishes as the horizon increases. In the MDP shown above, the immediate choice at $s_m$ becomes mathematically negligible when planning many steps ahead, as the long-term accumulated rewards begin to dwarf the immediate differences.
As shown in the figure above, the action gap often follows a parabolic or declining trajectory as $\gamma$ increases. This leads to a "resolution problem" where function approximators lose the ability to distinguish the best action from noise, resulting in a U-shaped performance curve where agents fail at both very low and very high discount factors.
Experimental Validation
The paper validates these theories using a Fruit Collection Task in a $5 \times 5$ grid-world. By training Deep Neural Networks (DNNs) to fit the ground-truth value function via supervised learning, the authors isolated the representation problem from the exploration problem.
Key findings include:
- Performance Degradation: Even with perfect data, DNNs struggled to fit the value function at high $\gamma$. Performance peaked at $\gamma \approx 0.7$ and degraded as it approached 1.0.
- Capacity Requirements: Larger neural networks were able to maintain performance over a wider range of horizons, confirming that LHPs demand higher representational capacity.
Conclusion and Implications
The difficulty of long-horizon RL is not merely a matter of data collection; it is a fundamental limit of value function representation. These results provide strong theoretical support for Hierarchical RL and the Options framework. By partitioning the state space at bottlenecks and using shorter planning horizons for sub-tasks, we can avoid the representational explosion and action-gap collapse inherent in monolithic, long-horizon value functions.
Summary updated