Learning Near Optimal Policies with Low Inherent Bellman Error

Andrea Zanette, Alessandro Lazaric, Mykel J. Kochenderfer, Emma BrunskillarXiv 2020 · OpenReview

Abstract

We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration. First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work. Second we provide an algorithm with a high probability regret bound $\widetilde O(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H \sqrt{d_t} \mathcal{I} K)$ where $H$ is the horizon, $K$ is the number of episodes, $\mathcal{I}$ is the value of the inherent Bellman error and $d_t$ is the feature dimension at timestep $t$. In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound. This has two important consequences: 1) it shows that exploration is possible using only batch assumptions with an algorithm that achieves the optimal statistical rate for the setting we consider, which is more general than prior work on low-rank MDPs 2) the lack of closedness (measured by the inherent Bellman error) is only amplified by $\sqrt{d_t}$ despite working in the online setting. Finally, the algorithm reduces to the celebrated LinUCB when $H=1$ but with a different choice of the exploration parameter that allows handling misspecified contextual linear bandits. While computational tractability questions remain open for the MDP setting, this enriches the class of MDPs with a linear representation for the action-value function where statistically efficient reinforcement learning is possible.

Introduction

In reinforcement learning (RL), the agent's primary challenge is balancing the exploration of unknown states with the exploitation of known rewards. While this problem is well-understood in "tabular" settings—where states and actions are discrete and limited—real-world applications often involve massive or continuous state spaces. To handle this complexity, researchers use function approximation, such as linear models, to generalize across states.

This paper, presented at ICML 2020, addresses the theoretical limits of exploration when using linear action-value functions. It moves beyond the restrictive "low-rank MDP" assumptions prevalent in prior literature to a more general framework based on Inherent Bellman Error (IBE).

The Problem: Beyond Low-Rank MDPs

Most existing theories for linear RL rely on the "low-rank" (or linear) MDP assumption, which requires that both the transition dynamics and the reward functions of the environment possess a specific linear structure. However, this is often too rigid for practical environments.

A more relaxed and common assumption in "batch" RL (where the agent learns from a fixed dataset) is the Inherent Bellman Error. IBE measures the "closedness" of a function class under the Bellman operator. Essentially, it asks: if we have a linear value function and apply the Bellman update, how far does the result stray from being linear?

The authors identify two critical gaps in the current research:

  1. Online Exploration: Can we achieve efficient exploration in an online setting using only the IBE assumption?
  2. The Curse of Misspecification: In linear settings, small approximation errors (bias) can propagate and explode exponentially as the agent's planning horizon increases. The goal is to find an algorithm that handles this misspecification gracefully.

The ELEANOR Algorithm

The authors propose ELEANOR (Efficient Linear Exploration of Actions by Nonlinear Optimization of the Residuals). ELEANOR introduces a fundamental shift in how optimism is applied in RL.

Global Optimism vs. Local Bonuses

Standard optimistic algorithms typically add an "exploration bonus" to every state-action pair. However, adding these bonuses often makes the resulting value function non-linear. In the context of IBE, this non-linearity breaks the core assumption and leads to exponential error propagation.

ELEANOR instead employs Global Optimism. Rather than adding local bonuses, it performs a global optimization over the parameter space. It searches for the most optimistic strictly linear value function that remains consistent with the observed data. By maintaining strict linearity, the algorithm ensures that approximation errors propagate linearly rather than exponentially.

Key Theoretical Insights

1. The Generality of IBE

The paper proves that the IBE condition is strictly more general than the low-rank MDP assumption. This bridges the gap between simple linear bandits and complex MDPs, providing a "Goldilocks" assumption that is flexible yet structured enough for efficient learning.

2. The $\sqrt{d}$ Price of Misspecification

A significant finding is that in the online setting, the misspecification error ($\mathcal{I}$) is amplified by a factor of $\sqrt{d}$, where $d$ is the feature dimension. This matches results previously found in generative models, suggesting that this amplification is a fundamental statistical limit of linear approximation.

3. Statistical Optimality

The authors establish a regret bound for ELEANOR: $$\tilde{O}\left(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H \sqrt{d_t} \mathcal{I} K\right)$$ Where $H$ is the horizon, $d$ is the dimension, $K$ is the number of episodes, and $\mathcal{I}$ is the inherent Bellman error. Crucially, they also provide a matching lower bound, proving that no algorithm can outperform ELEANOR in terms of scaling with $d, H,$ and $K$ under these assumptions.

Conclusion and Future Work

ELEANOR represents a milestone in statistically efficient RL, offering a minimax optimal algorithm for a broad class of MDPs. It also provides a unified view of RL and bandits; when the horizon $H=1$, ELEANOR reduces to the LinUCB algorithm, albeit with a modified exploration parameter that accounts for model misspecification.

However, challenges remain. While ELEANOR is statistically efficient (requiring few samples), it is not yet computationally efficient. The "Planning Optimization Program" requires solving a complex non-linear optimization problem. Future research is needed to find computationally tractable versions of this global optimization and to develop "agnostic" versions of the algorithm that do not require prior knowledge of the error level $\mathcal{I}$.

Summary updated

Abstract

We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration. First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work. Second we provide an algorithm with a high probability regret bound $\widetilde O(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H \sqrt{d_t} \IBE K)$ where $H$ is the horizon, $K$ is the number of episodes, $\IBE$ is the value if the inherent Bellman error and $d_t$ is the feature dimension at timestep $t$. In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound. This has two important consequences: 1) it shows that exploration is possible using only \emph{batch assumptions} with an algorithm that achieves the optimal statistical rate for the setting we consider, which is more general than prior work on low-rank MDPs 2) the lack of closedness (measured by the inherent Bellman error) is only amplified by $\sqrt{d_t}$ despite working in the online setting. Finally, the algorithm reduces to the celebrated \textsc{LinUCB} when $H=1$ but with a different choice of the exploration parameter that allows handling misspecified contextual linear bandits. While computational tractability questions remain open for the MDP setting, this enriches the class of MDPs with a linear representation for the action-value function where statistically efficient reinforcement learning is possible.
BibTeX
@misc{zanette2020learning,
  author = {Andrea Zanette and Alessandro Lazaric and Mykel J. Kochenderfer and Emma Brunskill},
  title = {{Learning Near Optimal Policies with Low Inherent Bellman Error}},
  year = {2020},
  eprint = {2003.00153},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.00153},
}
Figure