On Value Function Representation of Long Horizon Problems

Lucas Lehnert, Romain Laroche, Harm van Seijen

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.

An MDP with a bottleneck state $s_m$ where the agent must choose between a small immediate reward ($s_l$) and a larger but harder-to-reach reward ($s_r$).

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.

The action gap at state $s_l$ collapses as the discount factor $\gamma$ approaches 1, especially in deterministic environments ($\epsilon=0$).

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

Abstract

In Reinforcement Learning, an intelligent agent has to make a sequence of decisions to accomplish a goal. If this sequence is long, then the agent has to plan over a long horizon. While learning the optimal policy and its value function is a well studied problem in Reinforcement Learning, this paper focuses on the structure of the optimal value function and how hard it is to represent the optimal value function. We show that the generalized Rademacher complexity of the hypothesis space of all optimal value functions is dependent on the planning horizon and independent of the state and action space size. Further, we present bounds on the action-gaps of action value functions and show that they can collapse if a long planning horizon is used. The theoretical results are verified empirically on randomly generated MDPs and on a grid-world fruit collection task using deep value function approximation. Our theoretical results highlight a connection between value function approximation and the Options framework and suggest that value functions should be decomposed along bottlenecks of the MDP's transition dynamics.
BibTeX
@inproceedings{lehnert2018value,
  author = {Lucas Lehnert and Romain Laroche and Harm van Seijen},
  title = {{On Value Function Representation of Long Horizon Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11646},
}
Figure