PaperlayerView exact revision on arXiv

Source-linked AI summary

Contextual Decision Processes with Low Bellman Rank are PAC-Learnable

Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, Robert E. Schapire

arXiv:1610.09512v2cs.LGstat.ML

TL;DR

The paper asks how to tractably solve sequential decision-making problems with rich observations. It introduces Contextual Decision Processes and Bellman rank, then presents an iterative exploration algorithm with a PAC guarantee whose sample complexity depends logarithmically on the function class and not directly on context-space size.

  • Problem

    The paper studies how to tractably solve sequential decision-making problems when agents receive rich observations.

  • Method

    It formulates Contextual Decision Processes, uses Bellman rank to characterize exploration complexity, and iteratively refines candidate Q-value functions by optimistic evaluation and Bellman-error elimination.

  • Results

    ˜O(M 2H3K log(N/δ)/ϵ2) trajectories suffice to find an ϵ-suboptimal policy when the optimal value function is represented by F, with logarithmic dependence on F and no direct dependence on context-space size.

  • Takeaways & Limitations

    The results support sample-efficient learning across settings with low Bellman rank and remain robust to misspecified value classes, unknown rank, and infinite classes with bounded statistical complexity.

  • Takeaways & Limitations

    The stated sample-complexity bound is worse than the small-state MDP lower bound in its M, H, and log(N) factors, leaving optimal CDP sample complexity open.

Abstract

from arXiv · show

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.

1 Introduction

The paper introduces Contextual Decision Processes and Bellman rank to address systematic exploration in reinforcement learning with rich observations and function approximation. It develops Olive, which learns near-optimal policies with sample complexity independent of context-space size.

  • Contextual Decision Processes generalize MDPs with state contexts and POMDPs with history contexts for sample-efficient near-optimal policy learning.
  • Bellman rank is an algebraic-dimension measure of the interaction between a CDP and its value-function approximator, and is small in many natural settings.For tabular MDPs it is bounded by transition-matrix rank; for reactive POMDP value functions it is at most the number of hidden states.
  • Olive combines optimism-driven exploration with Bellman error-based search to iteratively eliminate inconsistent candidate Q-value functions.It evaluates a surviving function's greedy policy, then removes candidates violating Bellman equations when predictions fail verification.
  • ˜O(M 2H3K log(N/δ)/ϵ2) trajectories suffice to find an ϵ-suboptimal policy when the optimal value function belongs to F.M is Bellman rank, H the horizon, K the number of actions, N the candidate-class size, and δ the failure probability.
  • The sample-complexity bound depends logarithmically on the function class and has no direct dependence on context-space size.This supports powerful function approximation and applies to settings with very large or infinite context spaces.
  • Extensions address misspecified optimal value functions, unknown Bellman rank, and infinite function classes with bounded statistical complexity.The paper characterizes these results as robustness of Bellman rank for exploration difficulty.
  • Olive's computational complexity is polynomial in the number of value functions, making it intractable for powerful function classes.The authors identify computational tractability and empirical evaluation as open problems.

2 Contextual Decision Processes (CDPs)

Contextual Decision Processes (CDPs) provide a flexible framework for sequential decision-making with rich observations, using contexts and function approximation to seek near-optimal policies. The paper defines validity through Bellman equations and connects CDPs to MDPs and POMDPs.

  • Model: CDPs are defined by a context space, action space, horizon, and system descriptor governing initial contexts and subsequent rewards and contexts.The system descriptor includes an initial-context distribution and an interaction-dependent transition process.
  • Model: A CDP proceeds episodically: the agent observes contexts, chooses actions through a policy, receives rewards, and observes subsequent contexts for H steps.Policies map contexts to actions, with stochastic policy sequences also allowed.
  • Examples: CDPs generalize MDPs with states as contexts and POMDPs with histories or observation windows as contexts.Using history as context preserves the ability to represent optimal policies, while sliding windows provide a smaller contextual representation in some applications.
  • Value-based RL: Value-based learning uses a function class F to approximate action values and selects actions with greedy policies πf(x) = argmaxa∈A f(x, a).The goal is to identify a function that satisfies the relevant Bellman equations and whose greedy policy achieves high value.
  • Bellman validity: A function f is valid when its Bellman equation holds for every greedy roll-in policy πf′ and every level h.Average Bellman error measures self-consistency between predictions at adjacent levels under a roll-in policy.
  • Optimality: When Q⋆ belongs to F, it is valid, equals the selected optimal function f⋆, and yields the optimal long-term value V⋆.The framework also permits weaker settings where only valid functions are assumed, and approximate validity can provide graceful degradation.

3 Bellman Factorization and Bellman Rank

Bellman rank measures the structural complexity of Bellman errors across candidate functions and roll-in policies. Low rank supports tractable exploration, and the paper shows that many RL models—including MDPs, POMDPs, PSRs, and LQRs—have naturally bounded Bellman rank.

  • Motivation: Learning CDPs is generally hard without structural assumptions because they include models with arbitrarily large state or observation spaces.Low statistical complexity of F alone does not resolve the policy-dependent data-distribution problem.
  • Motivation: Low Bellman rank captures process structure that can make efficient reinforcement learning possible despite exponential lower bounds for unrestricted CDPs.The paper motivates the measure as a way to represent Bellman errors concisely and check validity tractably.
  • Definition: Bellman rank is a uniform upper bound on the ranks of Bellman error matrices whose entries are E(f, πf′, h).The measure characterizes the Bellman equations induced jointly by the CDP and value-function class.
  • MDPs: Tabular MDPs admit Bellman rank M = |S|, while MDPs with transition matrices of rank at most M admit Bellman rank M.These bounds show that the relevant dimension can reflect observable states or latent low-rank transition structure.
  • POMDPs: Reactive POMDPs admit Bellman rank bounded by the number of hidden states, without dependence on the observation-space size.The framework therefore applies to settings with large observations when the latent process has limited structure.
  • Other settings: PSRs have Bellman rank bounded by their linear dimension, while LQRs with non-stationary quadratic value functions have rank at most d^2 + 1.The Olive algorithm does not directly apply to LQRs because their action space is continuous.

4 Algorithm and Main Results

This section defines the PAC-learning objective for contextual decision processes and presents Olive, an optimistic value-function elimination algorithm. Under Bellman factorization, Olive achieves polynomial sample complexity independent of the number of contexts, while computational efficiency and optimal dependence on parameters remain open issues.

  • PAC Learning Objective: The PAC objective is to output an ε-suboptimal policy with probability at least 1−δ, using complexity polynomial in M, K, H, 1/ε, log(N), and log(1/δ), but independent of |X|.Here M is Bellman rank, K the number of actions, H the time horizon, and N the function-class cardinality.
  • Olive Algorithm: Olive iteratively selects the surviving value function with the highest predicted initial value, evaluates its greedy policy, and eliminates functions with large Bellman error.The algorithm terminates when the selected function has small average Bellman error at every level.
  • Limitations: Olive’s computational complexity is polynomial in the number of value functions, making enumeration intractable for the powerful classes motivating the theory.The paper leaves a computationally efficient implementation for future work and focuses on sample efficiency.
  • Olive Algorithm: Bellman factorization bounds the number of learning iterations by the Bellman rank, enabling Olive to halt after polynomially many episodes.The factorization embeds relevant distributions in an M-dimensional space, where each learning step makes progress.
  • Main Guarantee: Olive returns a policy satisfying V^π̂ ≥ V^⋆−ε with probability at least 1−δ and uses polynomially many episodes when the function class admits Bellman factorization.The theorem applies to contextual decision processes and function classes with parameters M and ζ.
  • Main Guarantee: In contextual bandits, where M=1 and H=1, Olive achieves the optimal sample complexity O(K log(N)/ε^2).The paper also gives an Ω(MKH/ε^2) lower bound for the small-state MDP special case.

5 Extensions

The paper extends Olive beyond known Bellman rank, finite function classes, and exact assumptions. These extensions support unknown-rank adaptation, separate policy and value representations, infinite classes with finite dimensions, and graceful degradation under approximation errors.

  • Unknown Bellman Rank: A doubling schedule guesses the unknown Bellman rank and preserves the same asymptotic sample complexity.When the guess is below the true rank, the subroutine may fail to terminate; explicit termination handles this case.
  • Separate Representations: Olive can use separate policy and V-value-function classes by associating each pair (π,g) with a corresponding Q-value function.The algorithm interacts with a function through its greedy policy and the mapping x↦f(x,π_f(x)).
  • Infinite Hypothesis Classes: For infinite classes, finite Natarajan dimension for policies and finite pseudo-dimension for value functions replace log N in the sample-complexity analysis.The infinite-class guarantee also has quadratic rather than linear dependence on K.
  • Infinite Hypothesis Classes: The infinite-class analysis currently incurs quadratic dependence on K, although the paper identifies this as potentially technical and suggests refined empirical-process analysis could recover linear dependence.The change arises because the finite-class proof uses a low-variance importance-weight argument that does not apply directly.
  • Approximate Assumptions: Oliver extends Olive to approximate validity and approximate Bellman factorization, with performance degrading gracefully as either assumption is violated.The extension is motivated by unknown environment dynamics and the approximate nature of modeled environments.

6 Proofs of Main Results

The proof establishes an explore-or-terminate argument and uses Bellman factorization to limit the number of iterations with large Bellman error. Concentration bounds then control estimation errors and yield the PAC guarantee.

  • Explore-or-Terminate: At each iteration, the optimistic policy is either approximately optimal or reaches a context distribution where it has large Bellman error.This creates the explore-or-terminate structure underlying the proof.
  • Explore-or-Terminate: If the selected function has small average Bellman error on its own roll-in distribution at every level, Olive terminates and its policy is near optimal.The policy-loss decomposition relates performance loss to the sum of Bellman errors.
  • Iteration Complexity: The optimal function is retained because reliable Bellman-error estimates prevent elimination when its Bellman error is zero.The iteration-complexity argument then bounds how often suboptimal functions can trigger learning steps.
  • Iteration Complexity: Bellman factorization limits the number of iterations at any level to a quantity proportional to M, because each surviving high-error function imposes new progress in an M-dimensional space.A volumetric argument makes this progress guarantee robust to sampling effects.
  • Concentration and Sample Complexity: Deviation bounds control predicted values, evaluation errors, and learning-step Bellman errors, and their sample requirements combine into the overall episode bound.Fresh data and conditional failure-probability control support the combined high-probability guarantee.

7 Conclusions and Discussions

The paper presents CDPs and Bellman factorization as a framework for sample-efficient reinforcement learning with rich observations, while identifying computational efficiency and several extensions as open problems.

  • Olive’s computational complexity is polynomial in the number of value functions, making it intractable for powerful function classes.
  • The paper asks whether computationally efficient algorithms or suitable supervised-learning oracles can be developed for this setting.
  • The sample complexity depends polynomially on the action-space cardinality, leaving large or continuous action spaces as an open extension.
  • The paper leaves open whether sample-efficient reinforcement learning can use only a policy class rather than a value-function class.
  • Without additional assumptions, value-based RL for CDPs has a sample-complexity lower bound of order KH.

A.2 A Polynomial Lower Bound that Depends on Bellman Rank

This section establishes lower bounds for contextual and layered episodic decision processes, showing that structural assumptions and Bellman rank constrain achievable sample complexity.

  • The constructed process is a finite-horizon CDP with Bellman rank at most M, so the lower bound applies within the paper’s structural setting.The reward sum is bounded in [0,1], and the full value-function class admits a Bellman factorization.
  • For any algorithm, some layered episodic MDP requires Ω(MKH/ϵ^2) trajectories to achieve an ϵ-optimal policy with probability exceeding the stated constant threshold.The construction has H layers, M states per layer, and K actions.
  • The lower bound embeds Θ(MH) independent multi-arm bandit problems, requiring the algorithm to identify the best action in many of them.Best-arm identification yields the K/ϵ^2 dependence.
  • The hard MDP contains waiting, bandit, good, and bad states across H levels, with only the good terminal state providing reward.Each bandit state has one action whose transition advantage is τ over the others.
  • Low Bellman rank also covers generalized POMDP settings, where the rank can be bounded by hidden-state size or by observation- and model-structure parameters.Reactive value functions can yield rank polynomial in the number of observations even with large hidden-state spaces.

B.5 Linear Quadratic Regulators

The LQR analysis shows that linear policies induce quadratic value functions, the optimal policy is linear, and Bellman factorization has low rank under the stated assumptions.

  • A finite-horizon LQR uses linear dynamics with state, action, and noise variables, and assumes bounded system parameters plus positive-definite cost conditions.The context space is R^d × [H], with continuous state and action spaces.
  • The LQR admits Bellman factorization with Bellman rank at most d^2 + 1, while its norm parameter is exponential in H and polynomial in other parameters.The chosen parameter bounds ensure that the optimal policy and value function belong to the specified classes.
  • Linear non-stationary policies induce non-stationary quadratic value functions with a constant offset.The quadratic representation follows by backward induction over the horizon.
  • The optimal policy is non-stationary and linear, while the optimal value function is non-stationary and quadratic.The policy matrices and value-function parameters are defined recursively.
  • The optimal policy matrix satisfies P⋆,h = (I + BᵀΛ⋆,h+1B)^−1BᵀΛ⋆,h+1A.

C Auxiliary Proofs of the Main Lemmas

The appendix analyzes the robust variant Oliver rather than repeating Olive’s proof, and organizes the technical arguments into main, adaptation, and deviation-bound components.

  • Oliver with parameters θ = 0 and η = 0 is precisely Olive, so the appendix’s analysis recovers Olive’s corresponding guarantees.
  • The proofs are divided into main arguments, lemmas adapting Todd’s work, and deviation bounds.

C.1 Main Proofs

The proofs establish that Bellman-error estimates support optimism, elimination, and exploration, while volumetric arguments bound exploration iterations and concentration bounds control estimation error.

  • The average Bellman-error expression equals the difference between V_f and V^{π_f}.
  • If the estimates satisfy their required accuracy and f⋆_θ is never eliminated, termination yields a policy meeting the stated near-optimality guarantee.
  • A volumetric argument shows that each exploration update contracts the minimum-volume enclosing ellipsoid, bounding the number of iterations at each level.
  • The ellipsoid-volume proof starts from a bounded initial ball and combines geometric contraction with ΨΦ ≤ ζ to control exploration complexity.
  • Importance weighting makes the Bellman-error estimator unbiased under the target policy distribution, enabling concentration around the population error.

D.1 Proof for Unknown Bellman Rank (Theorem 2)

The unknown-rank procedure repeatedly runs the base algorithm with increasing rank guesses, preserving near-optimality and adding only logarithmic overhead.

  • The failure probabilities assigned across repeated calls sum to at most δ, so all required high-probability events hold simultaneously.
  • The optimal function is never eliminated, and whenever the algorithm returns a policy, that policy is near-optimal.
  • log2 M + 1 calls suffice before the rank guess reaches the true Bellman rank, with the final guess at most 2M.
  • The total sample complexity differs from the final base-algorithm bound by factors that are at most logarithmic in the relevant parameters.

D.2 Proofs for Infinite Hypothesis Classes

The infinite-class analysis replaces finite-class union bounds with dimension-based deviation bounds, yielding guarantees controlled by policy and value-function complexity.

  • Finite Natarajan dimension for Π and finite pseudo dimension for G provide the complexity assumptions for the infinite-class analysis.
  • Theorem 3 follows by substituting uniform deviation bounds for the corresponding finite-class estimates.
  • With probability at least 1 − δ, the value estimate is within ϵ/8 simultaneously for every pair (π, g) ∈ Π × G.
  • In the separable case, the value estimate and population value are independent of π, making sample complexity independent of d_Π.
  • Uniform Bellman-error estimates hold within φ simultaneously over Π × G for fixed π_t and h_t.

D.2.2 Proof of Lemma 16

The proof bounds the complexity of policy–value-function product classes and applies the resulting uniform deviation control to the three terms in the Bellman-error estimator.

  • The three Bellman-error terms are controlled separately using the product-class lemma and a singleton identity-function class for the middle term.
  • The product class of policy indicators and value functions has pseudo dimension at most 6(d_Π + d_V) log(2eK(d_Π + d_V)).
  • The proof converts pseudo-dimension control into a growth bound by relating thresholded product hypotheses to restrictions of Π and V.
  • The relevant restriction class is formed from the Cartesian product of policy restrictions and value-function restrictions.

D.3 Proofs for OLIVER

The proof of Theorem 4 establishes the output policy's suboptimality and then bounds the algorithm's sample complexity using deviation guarantees and iteration limits.

  • Theorem 4 proof: Theorem 4's proof invokes Lemmas 9 and 10 to establish the output policy's suboptimality and sample-complexity guarantees.The proof first assumes their preconditions and later verifies them through deviation bounds.
  • Sample complexity: The algorithm's total iterations are bounded by applying the per-iteration result and limiting the relevant events across every h ∈[H].The proof states that the limiting count applies 3 times for every h ∈[H].
  • Deviation bounds: Lemma 10 is applied at level h = ht after Eq. (27) is satisfied, supporting the proof's per-iteration analysis.The passage attributes satisfaction of Eq. (27) to the choice of φ and ϵ′.
  • Failure probability allocation: The deviation analysis splits the total failure probability δ among events, including δ/3 for estimating ˆVf once and a separate event for estimating ˆE each iteration.The passages identify Lemma 12 for the one-time ˆVf estimate and Lemma 14 for the every-iteration ˆE estimate.
  • Deviation bounds: The choices of nest, neval, and n ensure | ˆVf −Vf| ≤ϵ/8 and | ˜E(ft, πt, h) −E(ft, πt, h)| ≤ϵ/(8H).These bounds are tighter than the ϵ′/8 and ϵ′/(8H) bounds required because ϵ ≤ϵ′.
Loading 1610.09512v2…