PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Reinforcement Learning with Linear Function Approximation

Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan

arXiv:1907.05388v2cs.LGmath.OCstat.ML

TL;DR

Function approximation extends RL beyond tabular problems but creates statistical and computational challenges. This paper gives an optimistic LSVI algorithm for linear MDPs and proves polynomial efficiency with regret independent of the numbers of states and actions.

  • Problem

    Function approximation is needed for large RL problems, yet it creates statistical challenges and existing theoretical guarantees largely apply only to tabular RL.

  • Method

    The paper uses an optimistic modification of Least-Squares Value Iteration with Upper-Confidence Bounds for episodic linear Markov decision processes.

  • Results

    Regret is eO(sqrt(d^3H^3T)), independent of the numbers of states and actions, while runtime and sample complexity are polynomial without a simulator or additional assumptions.

  • Takeaways & Limitations

    The result provides a provably efficient RL algorithm for linear MDPs whose dependence on the planning horizon is polynomial rather than exponential.

  • Takeaways & Limitations

    The guarantee assumes a linear MDP, meaning that transition kernels and rewards are linear and the action-value function is consequently linear.

Abstract

from arXiv · show

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)---a classical algorithm frequently studied in the linear setting---achieves $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret, where $d$ is the ambient dimension of feature space, $H$ is the length of each episode, and $T$ is the total number of steps. Importantly, such regret is independent of the number of states and actions.

1 Introduction

Function approximation extends RL beyond tabular problems but creates statistical, computational, and exploration challenges. This paper addresses whether provably efficient RL is possible for linear dynamics and rewards without simulators or stronger assumptions.

  • Motivation: Function approximation is needed for RL problems with enormous state spaces, but theoretical guarantees have largely remained tabular.Tabular methods face the curse of dimensionality, while function approximation supports practical domains including Atari, Go, robotics, and dialogue systems.
  • Motivation: Sparse visitation makes reliable value estimation difficult, while simple linear function classes can introduce bias when optimal values or policies are nonlinear.These tensions create fundamental statistical problems for RL system design.
  • Open problem: The central question is whether RL algorithms with function approximation can be efficient in both runtime and sample complexity.Efficiency should depend on intrinsic function-class complexity rather than the number of states.
  • Related work: Prior approaches often require a simulator or stronger assumptions such as deterministic, low-variance, or specially parameterized transitions.These conditions simplify exploration or transition estimation.
  • Contribution: Linear MDPs exploit linear reward and transition structure, yielding regret that scales with feature dimension d rather than state count S.The paper presents optimistic LSVI as the first algorithm in this setting with polynomial runtime and sample complexity without additional oracles or stronger assumptions.
  • Results and scope: The proposed regret is independent of the number of states and actions, while misspecification introduces a linear regret term proportional to the error ζ.The latter applies when the underlying transition model is only ζ-close to linear.

2 Preliminaries

The paper studies episodic MDPs in which an agent learns through state transitions and rewards over finite-horizon episodes. In a linear MDP, rewards and transition kernels depend linearly on features, making action-value functions linear in those features.

  • Episodic MDPs: An episodic MDP has state and action spaces, horizon H, transition kernels P, and reward functions r.At each step, the agent observes a state, selects an action, receives a bounded reward, and transitions to a new state.
  • Policies and values: A policy maps each state and time step to an action, while value functions measure expected cumulative rewards from states or state-action pairs.An optimal policy exists, and the regret over episodes compares its value with the value achieved by the agent’s policies.
  • Dynamic programming: Bellman equations express value recursively through immediate rewards and expected next-state values, and optimal policies are greedy with respect to optimal action-value functions.Therefore, estimating optimal action-value functions suffices to find an optimal policy.
  • Linear MDPs: A linear MDP assumes transition kernels and rewards are linear in a feature map φ, with bounded feature and parameter norms.The transition model can still have infinitely many degrees of freedom because its unknown coefficients are measures over states.
  • Linear action values: Under a linear MDP, every policy’s action-value function is linear in φ, so RL algorithms can focus on linear action-value functions.Tabular MDPs and simplex feature spaces are special cases of the linear formulation.
  • Algorithm: LSVI-UCB performs a parameter-estimation pass followed by greedy policy execution at each episode.The algorithm uses upper-confidence bounds to realize optimism and initializes parameters with regularization in the first episode.

3 Main Results

The paper gives LSVI-UCB polynomial runtime and sample-complexity guarantees for linear MDPs, including robustness to approximate linearity. Its regret depends on feature dimension and horizon, not the numbers of states or actions.

  • Algorithm: LSVI-UCB uses optimism through an upper-confidence-bound bonus added to least-squares value iteration.Each episode updates value-function parameters, then executes the resulting greedy policy.
  • Linear MDP guarantee: The regret is polynomial in the planning horizon H rather than exponential, and independent of the numbers of states S and actions A.Compared with the tabular dependence on SA, the bound uses polynomial dependence on feature dimension d.
  • Efficiency: The algorithm runs in O(d^2AKT) time and uses O(d^2H + dAT) space, both independent of S.The dominant computation evaluates action values across previously observed steps.
  • Sample complexity: In the fixed-initial-state setting, the linear model yields an ε-optimal policy using eO(d^3H^4/ε^2) samples with at least constant probability.With misspecification, the guarantee becomes ε + eO(ζdH^2) for the policy-value gap.
  • Misspecified setting: Under ζ-approximate linearity, LSVI-UCB incurs an additional eO(ζdHT) regret term that is linear in T.The approximation allows transition and reward errors up to ζ, measured for transitions in total variation distance.

4 Mechanisms

The analysis combines value-aware uniform concentration with linear transition structure to show that LSVI approximates the optimal Bellman equation. This handles dependence between learned value functions and observed samples.

  • Step 1: Value-Aware Uniform Concentration: The proof first controls the empirical-to-regularized transition estimate using value-aware uniform concentration.Uniformity is needed because later value functions depend on earlier sampled actions and states.
  • Step 1: Value-Aware Uniform Concentration: The relevant value-function class has bounded parameters and a small covering number, producing a logarithmic covering-number term.This uniform concentration applies to all value functions used by the algorithm.
  • Step 2: Linear Markov Transitions: The second step uses linear Markov transitions to show that the regularized least-squares transition estimate is valid for the value functions of interest.This transfers information across state-action pairs even when nearby pairs are rarely or never revisited.
  • Conclusion: Combining both steps establishes bP_hV_(h+1)(x,a) ≈ P_hV_(h+1)(x,a), so LSVI approximates the optimal Bellman equation.The proof requires approximation only over a small value-function class, not total-variation closeness of transition models.
  • Proof strategy: The proof adapts concentration and regret techniques from tabular MDPs and linear bandits.The full proofs are deferred to the appendices.

5 Conclusion

The paper establishes a provably efficient algorithm for linear MDPs without a simulator or additional assumptions, while identifying unresolved questions about optimal dependencies and transition-linearity requirements.

  • The paper presents the first RL algorithm with polynomial runtime and sample complexity for linear MDPs without requiring a simulator or additional assumptions.
  • Least-Squares Value Iteration with a UCB bonus is the paper’s core algorithmic approach.
  • On the optimal dependencies on d and H: The regret bound has a gap from the tabular-derived lower bound in its dependence on episode length H.The authors attribute this gap to the Hoeffding-type exploration bonus and suggest a Bernstein-type bonus could remove one H factor.
  • On the optimal dependencies on d and H: The optimal dependence on feature dimension d remains unclear, especially when the number of actions is very large.
  • On the assumption of linear transition dynamics: The main assumption requires linear transition dynamics, although the proof only needs linearity when transitions are applied to the considered value-function class.The paper leaves as an open question whether efficient RL is possible without linear transition structure.
  • On the assumption of linear transition dynamics: Under generic feature maps and policies, linear transitions are necessary for zero Bellman error for all policies under the stated mild conditions.

A Properties of Linear MDP

Linear MDPs impose structure that keeps action-value functions linear in the feature map for every policy and makes linear transitions necessary for universal Bellman closure under mild conditions.

  • The central property of a linear MDP is that the action-value function is linear in the feature map for any policy.
  • For every policy π, there are step-dependent weight vectors w^π_h representing Q^π_h as a linear function of φ.
  • Under mild conditions, Bellman closure of all linear action-value functions for every policy implies that the Markov transition measures are linear in φ.
  • The proof derives transition linearity by contrasting two actions at a fixed state and showing that transition probabilities can be represented as linear functions of φ.
  • The resulting transition representation is P_h(· | x, a) = ⟨φ(x, a), μ(·)⟩.
  • Because each transition is a probability measure, the linear-MDP assumption also imposes implicit structure on the feature space.

B Proof of Theorem 3.1

The proof controls LSVI-UCB’s estimation errors with concentration and optimism lemmas, then combines them to obtain a high-probability regret bound.

  • The proof proceeds by introducing notation, establishing lemmas, and combining them to prove Theorem 3.1.
  • The concentration lemma controls fluctuations in least-squares value iteration on a high-probability event.For fixed p, the event has probability at least 1 − p/2.
  • Appropriate bonuses make the estimated Q-values upper bounds on the optimal Q-values with high confidence.
  • The proof recursively bounds the difference between maintained and true value functions using the next-step difference plus an error controlled by the bonus.
  • With λ = 1 and β = c · dH√ι, LSVI-UCB has total regret at most O(√(d^3H^3Tι^2)) with probability 1 − p.

C Proof of Theorem 3.2

The proof establishes concentration and optimism properties for LSVI-UCB in the misspecified setting, then combines them to bound regret. Misspecification contributes an error that scales linearly with ζ.

  • Approximation control: For any policy, the action-value function remains close to a linear function, with the approximation controlled by the misspecification level.This property is established through corresponding linear weights and a recursive induction over steps.
  • Concentration: The stochastic noise is controlled on a high-probability event, with the event probability bounded below by 1 −p/2.The concentration event uses χ = log[2(cβ + 1)dT/p].
  • Proof strategy: The proof adapts the theorem's argument to misspecified linear MDPs, where model misspecification creates potentially adversarial noise.The adversarial component is distinct from the stochastic concentration noise handled elsewhere.
  • Optimism: 4H(H + 1 −h)ζ bounds the misspecification error in the optimistic Q-values for every state-action-step-episode tuple.The bound is obtained by induction and yields optimism up to an error linear in ζ.
  • Theorem conclusion: λ = 1 and βk = c · (d√kd)H are selected in Algorithm 1 before the final high-probability regret bound is established.The theorem states the guarantee with probability 1 −p.
  • Regret decomposition: 4H^2ζ is added to the per-episode value gap when converting approximate optimism into a regret bound.The proof then combines this term with the remaining concentration and estimation terms.

D Auxiliary Lemmas

This section introduces auxiliary lemmas and their proofs for the subsequent analysis.

  • The section presents several auxiliary lemmas and their proofs.

D.1 Important inequalities for summations

This subsection develops summation and matrix inequalities used in the analysis, including eigenvalue-based expressions for regularized covariance matrices.

  • The subsection begins by collecting short inequalities for controlling summations.
  • Λt inherits its eigenvectors from Pt while shifting each eigenvalue by the regularization λ.The decomposition supports trace calculations involving (Λt)^−1Pt.
  • A bounded feature sequence with a positive-definite initialization yields a uniform control statement for the regularized matrices Λt.The assumptions include ∥φt∥ ≤ 1 and λmin(Λ0) ≥ 1.

D.2 Concentration inequalities for self-normalized processes

This subsection develops self-normalized concentration tools and covering-number bounds needed for uniform control over the value-function class.

  • Concentration inequalities: The concentration results apply to stochastic processes with conditionally zero-mean, sub-Gaussian noise and predictable feature vectors.The feature process is modeled relative to the preceding filtration.
  • Concentration inequalities: Uniform concentration over the value-function class introduces an additional logarithmic dependence on its covering number.
  • Covering numbers: The ε-covering number of a Euclidean ball in R^d with radius R is at most (1 + 2R/ε)^d.
  • Covering numbers: For the parameterized value-function class, the logarithm of the covering number is bounded by separate contributions from the vector and matrix parameters.The resulting bound includes d log(1 + 4L/ε) and a d^2-dependent matrix term.
Loading 1907.05388v2…