PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Near Optimal Policies with Low Inherent Bellman Error

Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, Emma Brunskill

arXiv:2003.00153v3cs.LGcs.AI

TL;DR

The paper asks whether online exploration remains statistically efficient with approximate linear action-value functions under low inherent Bellman error. It introduces ELEANOR, an optimistic global-optimization extension of LSVI, and shows optimal regret rates in a setting more general than low-rank MDPs, with a LINUCB reduction for misspecified contextual linear bandits. Computational tractability for the MDP setting remains open.

  • Problem

    Approximate dynamic programming with linear architectures can diverge, motivating the study of effective exploration under low inherent Bellman error.

  • Method

    ELEANOR extends LSVI by choosing optimistic parameters through global optimization across the horizon while enforcing linearity.

  • Results

    The method achieves an optimal statistical regret bound, improves the low-rank MDP bound by a d factor, and has a misspecification analysis for contextual linear bandits.

  • Takeaways & Limitations

    Low inherent Bellman error supports statistically efficient online exploration beyond low-rank MDPs, while its amplification is only by a sqrt(d_t) factor in the analyzed setting.

  • Takeaways & Limitations

    Computational tractability of the ELEANOR optimization for the MDP setting remains unresolved.

Abstract

from arXiv · show

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.

1. Introduction

The paper studies online exploration with linear action-value approximators under low inherent Bellman error, a setting related to but more general than low-rank MDPs. It proposes ELEANOR, derives statistically optimal regret rates, and connects the approach to misspecified contextual linear bandits.

  • Low inherent Bellman error is more general than the low-rank MDP assumption used in prior exploration work.
  • ELEANOR is an optimistic generalization of LSVI for finite-horizon MDPs with exact or approximate LSVI conditions.
  • The regret bound is unimprovable in statistical rates, while performance degrades gracefully with positive inherent Bellman error.
  • The approach improves the best-known low-rank MDP regret bound by a d factor and reduces to LINUCB for contextual linear bandits.With misspecification, it remains computationally tractable when the misspecification level is known.
  • Global optimization preserves linear value representations because statewise perturbations can cause exponential error propagation in the more general setting.The method handles bias through linear Bellman-error propagation and variance through a small linear action-value class.

2. Notation

The paper formulates an undiscounted finite-horizon MDP with state-action rewards, transition kernels, and non-stationary value functions. Backward induction applies Bellman equations from the terminal timestep to compute optimal action values and policies.

  • The MDP has state space S, action space A, and horizon length H, with expected rewards and transition kernels for each state-action pair.
  • A non-stationary policy selects actions across timesteps, inducing state-action value functions through immediate rewards and expected future values.
  • An optimal policy exists under regularity conditions, with corresponding optimal value and action-value functions.
  • Value iteration initializes the terminal value at zero and recursively computes optimal action values using Bellman equations from t = H down to 1.
  • The Bellman operator applies the immediate reward plus expected continuation value under the maximizing next action.

3. Linear Value Function Frameworks

The framework represents action-value functions linearly in state-action features and measures their Bellman projection error through inherent Bellman error. Zero error implies restricted reward and transition linearity, while remaining strictly more general than low-rank MDPs and distinct from LSPI conditions.

  • Linear approximation: Each action-value function is represented as Qt(s, a) = φt(s, a)^Tθt using a possibly timestep-dependent feature map of dimension dt.
  • Inherent Bellman error: Inherent Bellman error is the maximum timestep projection error when the Bellman operator maps an approximated action-value function back toward the linear function class.
  • Zero-error properties: When I = 0, rewards are linear and transitions act linearly on members of the next-step value-function class.
  • Relations to low-rank MDPs: Zero inherent Bellman error requires TtQt+1 ⊆ Qt, making it more general than low-rank MDPs, whose Bellman operator remains in the feature range for arbitrary Qt+1.
  • Relations to LSPI: The zero-error condition and LSPI linearity are distinct: one concerns parameter-induced optimal policies, while the other concerns action values of arbitrary policies.
  • Relation to Bellman rank: LSVI conditions imply Bellman rank at most d, but OLIVE is not statistically efficient here because its guarantee depends explicitly on the potentially large or infinite action space.

4. Algorithm

ELEANOR extends optimistic LSVI by selecting parameters through a global horizon-wide optimization program that accounts for statistical uncertainty and misspecification. Its design preserves linearity and targets optimism at the initial state, but computationally efficient implementation remains unresolved.

  • Online updates: The algorithm uses regularized least squares with empirical feature covariances updated from trajectory observations.
  • Planning optimization: ELEANOR chooses optimistic parameters by solving a global optimization problem across the entire horizon at each episode.
  • Optimistic parameter construction: The least-squares parameter is constrained and perturbed by a vector whose radius accounts for noise, misspecification, and regularization bias.
  • Global perturbations: Global maximization over perturbations preserves linear value-function representations and avoids exponential propagation of errors.
  • Optimism: ELEANOR seeks optimism at the initial state rather than necessarily selecting optimistic actions at later encountered states, while retaining rate-optimal efficiency.
  • Limitations: Computationally efficient implementation is difficult, although the authors do not regard this difficulty as a fundamental barrier.

5. Main Result: Regret Upper Bound

Under Assumption 1, ELEANOR achieves a high-probability regret bound for linear action-value functions with inherent Bellman error, and improves the low-rank MDP rate.

  • The analysis allows rewards to match the value-function scale after rescaling and permits negative rewards.This differs from the usual setting with rewards in [0,1] and values in [0,H].
  • ELEANOR’s high-probability regret bound is stated under Assumption 1 with λ = 1.The assumptions include sub-Gaussian noise, bounded feature and parameter norms, and compact parameter sets.
  • The regret expression hides only logarithmic factors in d_t, H, K, and 1/δ.
  • Low-rank MDPs: For low-rank MDPs, ELEANOR improves the main regret rate over Jin et al. (2020) by a √d factor.The improvement follows from optimizing directly in parameter space rather than perturbing the value function with exploration bonuses.
  • Low-rank MDPs: The inherent Bellman error also covers approximate low-rank MDPs, with a √d saving in the misspecification term.The projection argument contributes to this improvement.

6. Contextual Misspecified Linear Bandits

When H = 1, ELEANOR becomes LINUCB for contextual misspecified linear bandits, using a modified exploration width that depends on misspecification.

  • For H = 1, ELEANOR reduces to LINUCB or OFUL and interprets inherent Bellman error as reward-function misspecification.
  • The resulting arm-selection strategy has a closed-form solution and a high-probability regret bound.
  • Misspecification requires correcting the confidence-interval width through the exploration parameter α_k.Without misspecification, the algorithm has the standard LINUCB confidence width; with misspecification, an additional correction is used.
  • Large misspecification can make the regret bound vacuous, consistently with exponential sample complexity being unavoidable for identifying a positive-return arm.The paper notes this does not contradict its result because rO(K) equals the maximum possible loss over K episodes.
  • The method handles contextual misspecified linear bandits, where the action set can change with the context, but requires knowledge of the misspecification level.

7. Lower Bounds

The paper establishes lower bounds matching ELEANOR’s statistical rate, including in the inherent-Bellman-error setting, so the dependence is unimprovable up to constants and logarithms.

  • ELEANOR’s statistical rate is unimprovable because a lower bound can be borrowed directly from the bandit literature.
  • There are H-horizon MDP classes satisfying the assumptions for which any algorithm incurs a lower-bounded expected regret when K = Ω(d²).
  • The lower bound rules out saving an H factor through a law-of-total-variance argument without imposing further structure on linear function approximations.The setting contains harder instances than the tabular lower bound, including a linear bandit at a single timestep.
  • The approximation-error analysis matches the LSPI result in its √d amplification of misspecification, despite addressing the harder online setting.
  • A second lower bound extends the construction to MDPs with nonzero inherent Bellman error.

8. Proof Overview

ELEANOR seeks optimistic linear value functions through global parameter optimization, controlling bias from inherent Bellman error and variance through bandit-style confidence intervals.

  • Proof strategy: The proof aims to bound regret by combining near-optimism with a decomposition of the learner’s value loss.
  • Propagation of errors: The inherent Bellman error supplies a parameter and residual that approximate each Bellman backup within additive error I.
  • Representational constraint: Adding exploration bonuses is ruled out because the perturbed backup can leave the linear function space and cause divergence.
  • Propagation of errors: A projection argument shows that large prediction errors cannot persist for many episodes because exploring novel feature directions improves future predictions.
  • Noise error: Covering and self-normalized concentration arguments keep confidence intervals at the same order as in bandit analyses despite the moving target V_t+1.
  • Optimization: Global optimization returns an optimistic initial-state solution while preserving a linear action-value representation.
  • Propagation of errors: The resulting backup error accumulates linearly across timesteps, yielding near-optimism at the initial state.
  • Regret decomposition: Summing the near-optimism, prediction, and martingale terms over timesteps and episodes produces the regret bound.

9. Conclusion

The paper introduces online exploration with linear approximators under low inherent Bellman error and claims optimal regret rates for statistical complexity and Bellman-operator non-closedness. It also identifies harder computational requirements and extends misspecified contextual linear-bandit analysis.

  • The paper introduces an algorithm for online exploration with linear approximators under low inherent Bellman error.
  • The regret bound is optimal with respect to statistical rates and the lack of closedness of the Bellman operator.
  • Global optimization may be unavoidable for more general linear approximators, making computational tractability harder than in prior low-rank work.
  • Working directly in parameter space enables linear rather than exponential error propagation and limits the complexity of the value-function class.
  • A simple modification of a mainstream algorithm handles misspecified contextual linear bandits, although the analysis requires knowledge of the misspecification level.

B. On the Inherent Bellman Error

Low inherent Bellman error is distinct from policy-value linearity and is strictly more general than the low-rank MDP assumption. The section gives constructions showing these assumptions differ and motivates choosing value iteration or policy improvement according to the representation.

  • Low-rank MDPs imply zero inherent Bellman error, but zero inherent Bellman error does not imply a low-rank MDP.
  • The chain construction has feature dimension 2 independent of N, is not low-rank, and nevertheless has zero inherent Bellman error.
  • Low-rank MDPs imply linearly parameterizable policy value functions, but the converse fails.
  • Zero inherent Bellman error can coexist with policies whose action-value functions are not linearly parameterizable, while policy-value linearity can coexist with positive inherent Bellman error.
  • When inherent Bellman error is zero, approximate value iteration converges to the global optimum; when all policies are linearly parameterizable, approximate policy improvement should be used.

C.1. First Step Analysis

The analysis establishes feasibility and optimism for the algorithm, controls failure events and transition noise with high probability, and derives the main regret result. The lower-bound construction embeds linear and misspecified bandit problems into an MDP.

  • If the program admits a feasible solution, its parameter sequence lies in the prescribed functional spaces and satisfies the first-step analysis.
  • With high probability, concentration bounds control transition noise uniformly over the value-function class through covering and self-normalized linear-bandit arguments.
  • The recursively defined best approximant is feasible, so the algorithm’s returned initial value is at least the corresponding optimal-value benchmark.
  • The main theorem gives a high-probability regret bound for ELEANOR jointly over all episodes.
  • The lower-bound construction embeds linear and misspecified linear-bandit problems into an MDP, yielding unavoidable regret contributions from both components.

D.3.5. COMPUTATION OF INHERENT BELLMAN ERROR

The lower-bound construction computes inherent Bellman error by separating a linear subproblem from misspecified bandit subproblems. It sets the misspecification level equal to the Bellman error and derives a corresponding regret lower bound.

  • At timestep 1, the construction is linear because the backup value can be represented exactly by the feature map.
  • At later timesteps, the approximation error is bounded by ǫ, giving inherent Bellman error I = ǫ.
  • The misspecified subpart contains H independently chosen problems, producing a regret contribution that scales with H and the misspecification level.
  • The MDP class shares feature maps across instances while varying the linear-bandit parameter and misspecified reward responses.
  • The resulting theorem gives a lower bound for any algorithm over feature dimensions d_t ≥ 3 and sufficiently large K.

E. Misspecified Contextual Linear Bandit

The misspecified contextual linear-bandit specialization simplifies ELEANOR’s objective and connects it to LINUCB, with an exploration correction for nonzero misspecification. A tighter projection argument explains the resulting dimension dependence and relates the correction to prior work.

  • ELEANOR’s simplified optimization program is computationally tractable depending on the size of the action space.
  • When the inherent Bellman error is zero, the specialization coincides with classical LINUCB.
  • Nonzero misspecification requires adding an I correction to the exploration parameter.
  • Without this correction, LINUCB can fail in misspecified linear bandits.
  • The correction partially appeared in earlier work for a different setting, while this analysis uses a tighter projection argument to save a d factor.
Loading 2003.00153v3…