PaperlayerView exact revision on arXiv

Source-linked AI summary

Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

Chi Jin, Qinghua Liu, Sobhan Miryoosefi

arXiv:2102.00815v4cs.LGcs.AIstat.ML

TL;DR

The paper investigates which minimal structural assumptions enable sample-efficient RL with function approximation. It introduces Bellman Eluder dimension, develops GOLF and reanalyzes OLIVE, and proves sample-efficient learning for the resulting broad class with guarantees independent of state-action-space size.

  • Problem

    Existing efficient RL results often rely on strong assumptions such as linear approximation or LQR structure, motivating the search for weaker assumptions that still permit sample-efficient learning.

  • Method

    The paper introduces Bellman Eluder dimension, designs the optimization-based GOLF algorithm, and reanalyzes the hypothesis-elimination algorithm OLIVE.

  • Results

    Both GOLF and OLIVE learn near-optimal policies for low-BE-dimension problems using a polynomial number of samples independent of state-action-space size.

  • Takeaways & Limitations

    Low BE dimension provides a broad tractable class that includes most existing tractable RL problem classes and adds examples such as kernel reactive POMDPs.

  • Takeaways & Limitations

    The BE framework does not address model-based function-approximation examples such as low witness rank, although it covers low Eluder dimension problems.

Abstract

from arXiv · show

Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure -- Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm -- GOLF, and reanalyzes a hypothesis elimination-based algorithm -- OLIVE (proposed in Jiang et al., 2017). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.

1 Introduction

The paper asks which weak structural assumptions enable sample-efficient RL with function approximation. It introduces Bellman Eluder dimension as a broad complexity measure and develops algorithms for learning problems in this class.

  • Motivation: Function approximation addresses enormous state spaces but creates challenges in generalization, limited exploration, and identifying sufficient structure for efficient learning.These challenges motivate seeking assumptions weaker than commonly used linear or LQR structure.
  • Research question: The paper frames the central question as identifying minimal structural assumptions that empower sample-efficient reinforcement learning.Its approach is to identify a rich class covering practical applications and design algorithms that learn any problem in that class.
  • Bellman Eluder dimension: Bellman Eluder dimension defines a rich RL problem class that contains low Bellman rank and low Eluder dimension problems, covering almost all existing tractable RL classes.The paper also identifies kernel reactive POMDPs as a new example outside both earlier frameworks.
  • Algorithms and guarantees: GOLF provably learns near-optimal policies for low-BE-dimension problems with sample complexity polynomial in relevant parameters and independent of state-action-space size.Its guarantees match or improve prior results in several subclasses, including linear, low Bellman rank, and low Eluder dimension settings.
  • Algorithms and guarantees: OLIVE is reanalyzed to learn low-BE-dimension problems sample-efficiently under slightly weaker assumptions, but with worse sample complexity than GOLF.In the low Bellman rank setting, the OLIVE result matches the earlier guarantee of Jiang et al. (2017).
  • Scope: The framework directly addresses exploration rather than assuming exploratory data or a simulator, unlike the batch RL setting reviewed by the paper.This distinguishes the paper’s setting from approaches that avoid explicit exploration.

2 Preliminaries

The paper frames RL with function approximation as a setting where sample-efficient learning requires structural assumptions beyond realizability. It introduces the MDP, policy and value-function notation, approximation assumptions, and covering numbers used throughout.

  • MDP model: Episodic MDPs are defined by states, actions, horizon H, transition measures, and reward functions, with an agent interacting from a fixed initial state.Episodes terminate after H steps, and rewards are assumed non-negative; deterministic rewards are used for notational simplicity.
  • Objectives: The RL objective is to find an ϵ-optimal policy with few interactions or achieve sublinear regret.A policy is ϵ-optimal when its initial value is within ϵ of the optimal value.
  • Function approximation: Function approximation supplies candidate Q-functions from a prespecified class F to approximate the optimal Q-function Q⋆.The class is factored by step, with f_H+1 set to zero because no reward is collected afterward.
  • Assumptions: Realizability requires F to contain Q⋆, while completeness requires F to be closed under the Bellman operator.Completeness is written as T_hF_h+1 ⊆ F_h for every step h.
  • Complexity measures: The paper uses ϵ-covering numbers to measure infinite function classes under the maximum stepwise sup-norm metric.N_F(ϵ) is the minimum number of representative functions needed to approximate every member within ϵ.
  • Eluder dimension: Eluder dimension measures the length of sequences containing progressively approximately independent points, generalizing linear independence to nonlinear function classes.Its distributional analogue replaces pointwise function values with expected values under selected probability measures.

3 Bellman Eluder Dimension

Bellman Eluder dimension applies distributional Eluder dimension to Bellman residuals, producing a broad complexity measure for RL. The resulting class contains low Bellman-rank and low-Eluder-dimension problems and is strictly broader in general.

  • Definition: Bellman Eluder dimension is introduced as a complexity measure based on Bellman residual functions and distributions over state-action pairs.It is defined by applying distributional Eluder dimension to residuals of the form (I−T_h)F.
  • Distributional Eluder dimension: Distributional Eluder dimension measures approximate independence through expected function values under a restricted family of probability measures.This can be statistically easier than estimating function values at every individual point.
  • Distribution families: The BE dimension depends on the function class, error level, Bellman step, and distribution family, with D_F and D_∆ as the paper’s two choices.D_F contains distributions generated by greedy policies, whereas D_∆ contains point-mass distributions on state-action pairs.
  • Known classes: Low Bellman rank is a special case of low BE dimension, with only a logarithmic multiplicative factor in the normalization and accuracy parameters.Bellman rank represents average Bellman error through an inner product of low-dimensional vectors.
  • Known classes: Low Eluder dimension is also contained in low BE dimension under completeness, because pointwise Eluder dimension is a special case of distributional Eluder dimension.The inclusion follows from completeness and the distributional generalization.
  • Strict richness: The low-BE class is strictly larger than the union of low-Eluder and low-Bellman-rank classes, including kernel reactive POMDPs.For any m, examples exist with BE dimension at most 5 but Eluder dimension and Bellman rank at least m.

4 Algorithm GOLF

GOLF is an optimization-based algorithm that combines optimistic planning with local fitting constraints over collected transition data. Under realizability and generalized completeness, it learns near-optimal policies for low-BE problems with state-space-independent guarantees.

  • Algorithm: GOLF maintains datasets and a confidence set, then repeatedly chooses an optimistic function and follows its greedy policy.Each episode collects one trajectory and updates the confidence set using the new transition data.
  • Local fitting: GOLF’s local regression constraint permits functions whose squared loss is only slightly above the best loss over an auxiliary class G.The loss acts as a proxy for squared Bellman error, making the constraint a relaxed Fitted Q-Iteration update.
  • Limitation: The optimization problem in GOLF’s optimistic-planning step cannot generally be solved computationally efficiently.This is a computational limitation distinct from the statistical guarantees.
  • Assumptions: GOLF requires realizability and generalized completeness, where the auxiliary class G contains Bellman images of functions in F.Choosing G=F reduces generalized completeness to standard completeness.
  • Guarantees: The regret is independent of the number of states, while matching the linear-setting benchmark and improving dependencies reported for low Eluder dimension and low Bellman rank.For low Bellman rank, the sample complexity is linear rather than quadratic in the rank.
  • Guarantees: GOLF’s sample complexity is ˜O(H^2d log(N_F∪G)/ϵ^2), scaling linearly with BE dimension and log covering number.The guarantee applies to learning an O(ϵ)-optimal policy under the stated assumptions.
  • Proof strategy: The proof establishes optimism, exploits confidence-set sharpness, and uses low BE dimension to relate current-policy errors to errors under previous policies.Optimism follows from retaining Q⋆ in the confidence set; sharpness comes from small empirical Bellman-error proxy loss.

5 Algorithm OLIVE

OLIVE is reanalyzed as a hypothesis-elimination algorithm that also learns low-BE problems. It avoids completeness but has worse sample complexity, no sublinear regret guarantee, and a distribution-family restriction relative to GOLF.

  • Guarantee: OLIVE can learn RL problems with low BE dimension despite originally being designed for low Bellman rank.The paper’s reanalysis establishes this result under assumptions weaker than those used by GOLF.
  • Comparison with GOLF: OLIVE does not require completeness, but its sample complexity is worse than GOLF’s and it has no sublinear regret guarantee.This is the principal trade-off between the two algorithms’ assumptions and performance guarantees.
  • Algorithm: OLIVE alternates optimistic planning, Bellman-error estimation, and elimination of candidate functions with large estimated Bellman error.It outputs the optimistic policy when the estimated cumulative error is small; otherwise, it eliminates functions exceeding a stepwise threshold.
  • Limitation: OLIVE is computationally inefficient in general because its optimistic-planning component can require solving an NP-hard problem in the worst case.The limitation concerns implementation of the planning step rather than the statistical sample guarantee.
  • Theoretical guarantee: OLIVE outputs an O(ϵ)-optimal policy using at most O(H^3d^2 log[N_F(ζ_elim/8)] · ι/ϵ^2) episodes.Here d is the BE dimension at scale ϵ/H and ι is logarithmic in H, d, δ, and ϵ.
  • Proof idea: The elimination procedure can activate at most d times per step, so OLIVE terminates within dH+1 phases and outputs an Hζ_act-optimal policy.The bound follows because successive activated policies form a BE-independent sequence.

6 Conclusion

The paper introduces Q-type and V-type Bellman rank variants alongside BE dimension, and provides V-type algorithmic variants and guarantees. It relates V-type Bellman rank to V-type BE dimension while distinguishing their sampling conventions.

  • Algorithmic variants: The paper presents V-type variants of GOLF and OLIVE, with the latter’s proof obtained by modifying the corresponding Q-type argument.The supplied conclusion passages establish the variant definitions and their relation, while algorithmic details appear elsewhere in the paper.
  • V-type Bellman rank: The V-type Bellman rank factorizes average Bellman error using feature maps φ_h and ψ_h with bounded product norm ζ.The error evaluates f under the greedy policy of f′ and samples the action from the greedy policy of f.
  • Q-type versus V-type: V-type and Q-type Bellman errors coincide when f = f′, but differ in how the action at the evaluated step is sampled.Q-type samples the action from the roll-in policy, whereas V-type samples it from the greedy policy of the evaluated function.
  • V-type BE dimension: V-type BE dimension measures the complexity of finding functions whose expected Bellman error is small under state distributions in Π.The state-wise Bellman residual class and distribution family Π define the corresponding complexity measure.
  • Relation between measures: Low V-type Bellman rank implies low V-type BE dimension up to a logarithmic factor for distributions generated by greedy-policy roll-ins.The relevant distribution family is D_F, consisting of measures generated by rolling in with greedy policies.

A.1 Algorithm V-type GOLF

The V-type algorithms modify data collection to use uniformly random actions at the evaluated step, enabling guarantees for V-type BE-dimension problems. V-type GOLF has better dependence and broader distributional applicability than V-type OLIVE, while Q-type results retain stronger regret guarantees.

  • A.1 Algorithm V-type GOLF: V-type GOLF rolls in with π_k, then takes a uniformly random action at step h to collect transition data.This is the defining difference from the Q-type analogue.
  • A.1 Algorithm V-type GOLF: With probability at least 0.99, V-type GOLF outputs an O(ϵ)-optimal policy under the stated assumptions and parameter choice.The theorem specifies β through a logarithmic expression involving K, H, the function classes, d, |A|, and ϵ.
  • Comparison with V-type OLIVE: V-type GOLF depends linearly on V-type BE dimension, whereas V-type OLIVE depends quadratically on it.This is one of the stated advantages of V-type GOLF over V-type OLIVE.
  • Comparison with V-type OLIVE: V-type GOLF applies for finite V-type BE dimension with respect to either D_F or D_Δ, while V-type OLIVE has no guarantee for D_Δ.The broader distributional applicability is the second stated advantage of GOLF.
  • Scope of guarantees: Q-type BE-dimension results include regret and sample-complexity guarantees, whereas the V-type counterpart has only sample-complexity results.The stated reason is the need for uniformly random actions in the V-type algorithms.
  • A.2 Algorithm V-type OLIVE: V-type OLIVE outputs an O(ϵ)-optimal policy using at most O(H^3d^2|A| log(|F|) · ι/ϵ^2) episodes under realizability and finite F.Its success probability is at least 1 − δ, with ι = c log[Hd|A|/δϵ].
  • A.2 Algorithm V-type OLIVE: For finite Bellman rank d and finite F, V-type OLIVE requires ˜O(H^3d^2|A| log(|F|)/ϵ^2) samples, matching Jiang et al. (2017).A finite-covering-number extension replaces log(|F|) with a covering-number term.
  • Q-type versus V-type: Q-type Bellman rank is more suitable for LQR because Q-type guarantees are independent of the number of actions, unlike V-type guarantees.The comparison matters for LQR, which has an infinite action set but small Q-type and V-type Bellman rank.

B.2 Effective dimension and kernel MDPs

Effective dimension provides a route from Hilbert-space structure to low Eluder dimension and hence low BE dimension, covering kernel MDPs and kernel reactive POMDPs. Effective Bellman rank extends this route when induced feature sets are approximately low-dimensional.

  • Effective dimension: A function class with low effective dimension has low Eluder dimension, making effective dimension a sufficient structural condition for low BE dimension.The paper also notes that Eluder dimension is more general because it does not require the same Hilbert-space linear structure.
  • Kernel MDPs: Kernel MDPs represent transitions as Hilbert-space inner products and rewards linearly, with effective dimension controlling their induced complexity.The feature map φ is known, while ψ and the reward parameter are unknown; regularization conditions constrain the representation.
  • Kernel MDPs: Kernel MDPs have low Eluder dimension and bounded log-covering number when their effective dimension is bounded.These properties support applying GOLF or OLIVE to an appropriate realizable and complete function class.
  • Effective Bellman rank: Effective Bellman rank is introduced as a tool for controlling BE dimension, including in kernel reactive POMDPs.Both Q-type and V-type effective Bellman rank are shown to upper-bound the corresponding BE dimension.
  • Effective Bellman rank: Effective Bellman rank can be much smaller than original Bellman rank when the induced feature set approximately lies in a low-dimensional linear subspace.In finite-dimensional Euclidean spaces, it is also upper-bounded by original Bellman rank up to logarithmic factors.
  • Kernel reactive POMDPs: Kernel reactive POMDPs have low V-type BE dimension when their effective dimension is low, even though their Eluder dimension and original Bellman rank can be arbitrarily large.If realizability also holds, V-type OLIVE yields a polynomial sample-complexity guarantee.

C.3 Proof of Proposition 13

The proposition constructs a linear bandit instance whose Eluder and Bellman ranks grow with m, while its BE dimension remains bounded by 5. This separates BE dimension from both conventional complexity measures in the example.

  • Construction: The instance uses m actions a_i = (1; e_i), functions f_θi(a) = a^⊤θ_i, and an identically zero reward function.The horizon and state-space size are both one.
  • Eluder dimension: The Eluder dimension is at least m − 1 because a_1, …, a_{m−1} form an ϵ-independent sequence for ϵ ∈ (0, 1].The functions agree on prior points but differ by 1 at the current point.
  • Bellman rank: The Bellman residual matrix is E = Θ^⊤Θ and has rank m, so the Bellman rank is at least m.Here Θ contains the vectors θ_1 through θ_m.
  • BE dimension: The BE dimension is at most 5 because the Bellman residual class equals F_1 and D_F coincides with D_Δ in this setting.The proof reduces the claim to bounding dim_D^E(F_1, D_Δ, ϵ) by 5.

D.1 Proof of Theorem 15

The proof bounds regret through cumulative Bellman error, then controls that error using distributional Eluder dimension and concentration. Confidence-set guarantees ensure optimism and low Bellman error with high probability.

  • Confidence-set guarantees: The selected value function is therefore an upper bound of Q⋆ with high probability.
  • Confidence-set guarantees: With probability at least 1−δ, the optimal value function Q⋆ remains in every confidence set.This follows from Lemma 40 and standard martingale concentration arguments.
  • Regret reduction: The cumulative regret is upper bounded by the sum of Bellman errors through policy-loss decomposition.
  • Bellman-error control: Lemma 41 is applied in two ways to obtain regret bounds in terms of two different complexity measures.The proof instantiates the lemma with X = S × A, Φ = (I − T_h)F, and Π = D_Δ,h for one application.
  • Concentration: Freedman’s inequality and union bounds provide the high-probability concentration needed to complete the regret analysis.
  • Bellman-error control: Distributional Eluder dimension controls how often the expected Bellman error can exceed a threshold in a sequence of measures.The argument bounds the number of large-error terms using dependence and independence properties.

E.1 Full proof of Theorem 18

The OLIVE proof establishes concentration for activation and elimination, preserves Q⋆ in the surviving class, and uses BE dimension to bound the number of elimination phases. Consequently, OLIVE terminates within dH + 1 phases and outputs a 4ϵ-optimal policy with high probability.

  • High-probability events: With probability at least 1−δ, activation and elimination events hold throughout the first dH + 1 phases.The events include activation when Bellman error is large, elimination of functions with error at least 2ζ_elim, and preservation of Q⋆.
  • Guarantee: OLIVE terminates within dH + 1 phases and outputs a 4ϵ-optimal policy with high probability.This conclusion uses optimism of f_k and policy-loss decomposition.
  • Termination: At most d activations can occur at each step h, because d + 1 activations would form an ϵ/H-independent sequence contradicting BE dimension.
  • Concentration: Azuma-Hoeffding concentration and a union bound justify the activation and elimination guarantees.
  • High-probability events: Q⋆ is not eliminated, while functions with sufficiently large Bellman error are removed when elimination activates.

F.1 Proof of Theorem 23

The proof of Theorem 23 adapts the OLIVE analysis to the EV-based setting. Concentration controls activation and elimination, BE dimension bounds the number of phases, and the resulting regret is controlled through cumulative Bellman error.

  • High-probability events: With probability at least 1−δ, activation, elimination, and preservation of Q⋆ hold throughout the first dH + 1 phases.
  • Termination: OLIVE terminates within dH + 1 phases because d + 1 activations would contradict the BE-dimension definition.The contradiction arises from an ϵ/H-independent sequence of roll-in distributions.
  • Guarantee: OLIVE outputs a 4ϵ-optimal policy with high probability.The conclusion follows from optimism and policy-loss decomposition once termination is established.
  • Concentration: Azuma-Bernstein concentration and union bounds support the elimination guarantees in the EV-based procedure.
  • Elimination: Q⋆ is never eliminated because its expected Bellman error is identically zero for every policy and step.
  • Regret analysis: The regret proof reduces cumulative regret to Bellman error and then applies the DE-dimension bound.

G.1 Proof of Proposition 29

The proposition proofs relate effective dimension and Eluder dimension to finite covers and Bellman independence. They also express expected Bellman error through policy- and function-dependent components, including for kernel reactive POMDPs.

  • Effective dimension: Finite ϵ-effective dimension represents functions as linear predictors over a feature map with parameters in a bounded set.The proof writes F = {f_θ(·) = ⟨φ(·), θ⟩_H | θ ∈ Θ}, with Θ ⊂ B_H(1).
  • Eluder dimension: Eluder dimension restricts attention to the span of an independent feature sequence, yielding a finite-dimensional projection for covering F_h.
  • Covering argument: An ϵ-net over that projection gives a cover whose logarithmic size is bounded by O(n · log(1 + nH/ϵ)).
  • Bellman independence: An ϵ-independent sequence of measures with respect to (I − T_h)F can be represented using policy-generated distributions and corresponding functions.
  • Reactive POMDP connection: Expected Bellman error factors into a policy-dependent component and a function-dependent component in the reactive-POMDP argument.

H Discussions on DF versus D∆in BE Dimension

The paper shows that BE dimension can differ sharply depending on whether it is induced by greedy-policy roll-in distributions or all Dirac distributions. Proposition 45 constructs examples where either distribution choice yields constant BE dimension while the other can be arbitrarily larger.

  • The contrasting constructions establish that the choice between DF and D∆ is substantive rather than interchangeable in BE-dimension analysis.The paper frames this as either dimension being arbitrarily larger than the other.
  • Proposition 45 shows that neither BE dimension induced by DF nor by D∆ is always smaller than the other.For any m, the proposition provides constructions in which one dimension is bounded by an absolute constant while the other grows with m.
  • In the first construction, the agent always starts at s1 in an m-state, two-action, one-step problem, so it cannot visit the other states.The construction uses zero rewards and H = 1.
  • For this construction, DF is a singleton, giving dimBE(F, D∆, ϵ) at most 1, while D∆ admits an m-length 1-independent sequence and hence dimension at least m.These conclusions hold for all ϵ ∈ (0, 1].
  • In the second construction, two states are sampled uniformly at episode start, with m actions and zero rewards.The associated function class is F1 = {fi(s, a) = (2 · 1(s = s1) −1) + 0.5 · 1(a = ai) : i ∈[m]}.
  • The greedy-policy roll-in distributions µ1, . . . , µm form a 0.5-independent sequence, so dimBE(F, DF, ϵ) is at least m for all ϵ ∈ (0, 0.5].Each µi is uniform over (s1, ai) and (s2, ai), and the expected value of fj under µi is 0.5·1(i = j).
Loading 2102.00815v4…