PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-based Reinforcement Learning and the Eluder Dimension

Ian Osband, Benjamin Van Roy

arXiv:1406.1853v2stat.MLcs.LG

TL;DR

The paper asks how to learn effectively in unknown MDPs without relying on finite state-action cardinality. It analyzes PSRL for parameterized MDPs, extending eluder dimension to reinforcement learning, and obtains unified dimensionality-dependent regret guarantees.

  • Problem

    Learning to optimize an unknown MDP requires performance guarantees that can depend on structural dimensionality rather than state-action cardinality.

  • Method

    The paper analyzes posterior sampling for reinforcement learning and extends eluder dimension to characterize the complexity of parameterized MDPs.

  • Results

    PSRL satisfies general regret bounds in parameterized MDPs and provides state of the art guarantees in several important settings.

  • Takeaways & Limitations

    The analysis provides a unified framework for model-based reinforcement learning whose guarantees scale with reward and transition-function dimensionality.

  • Takeaways & Limitations

    The paper assumes exact posterior sampling, leaves extension to non-episodic MDPs open, and notes computational intractability for a comparable optimistic variant.

Abstract

from arXiv · show

We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly as $\tilde{O}(\sqrt{d_K d_E T})$ where $T$ is time elapsed, $d_K$ is the Kolmogorov dimension and $d_E$ is the \emph{eluder dimension}. These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings. Moreover, we present a simple and computationally efficient algorithm \emph{posterior sampling for reinforcement learning} (PSRL) that satisfies these bounds.

1 Introduction

The paper studies regret-based learning in unknown MDPs, where exploration must be balanced against exploitation. It develops PSRL and an eluder-dimension analysis to obtain dimensionality-dependent guarantees beyond state-action cardinality.

  • Unknown MDP learning requires balancing exploration that improves environmental understanding against exploitation of existing knowledge for short-term rewards.
  • Regret measures the shortfall between an agent’s expected rewards and those of the optimal policy during learning.
  • Existing near-optimal regret bounds are available for model-based algorithms but grow with the cardinality of state and action spaces, which may be enormous or infinite.
  • Structured function classes can improve on cardinality-based guarantees, although prior results include computationally intractable algorithms and bounds that may approach linearity.
  • PSRL receives a unified analysis with regret depending on the dimensionality of reward and transition function classes, supported by an extension of eluder dimension to reinforcement learning.

2 Problem formulation

The paper formulates learning as repeated episodic interaction with a random finite-horizon MDP and defines policies, values, and regret over those episodes. Its setup assumes vector-valued states and uses future-value regularity to support analysis.

  • The environment is a random finite-horizon MDP with state and action spaces, reward and transition distributions, a horizon τ, and an initial-state distribution ρ.
  • The state space is assumed to be a subset of finite-dimensional Euclidean space, while discrete states can be represented as probability vectors.
  • The one-step future value is the expected value of the optimal policy under a next-state distribution, with regularity examined through Lipschitz continuity in distribution means.
  • An agent selects a policy distribution for each episode based on the history observed before that episode begins.
  • Regret accumulates episode regret relative to the optimal policy for the realized MDP and may be random because of the MDP, sampling, transitions, and rewards.

3 Main results

PSRL samples an MDP from the posterior at each episode and follows its optimal policy, yielding regret bounds based on function-class dimensionality. The results apply broadly and include explicit guarantees for linear-quadratic systems, while an optimistic alternative remains computationally intractable.

  • Posterior sampling for reinforcement learning: PSRL samples an MDP from the posterior at each episode and executes the policy optimal for that sampled MDP.The algorithm starts from a prior and updates the posterior using episode histories.
  • General regret bound: Theorem 1 bounds PSRL's expected regret at any time T for parameterized reward and transition function families.The bound assumes the true MDP belongs to the specified families and the future value function has a global Lipschitz constant.
  • General regret bound: The analysis characterizes learning complexity using the Kolmogorov dimension and eluder dimension of the relevant function classes.The eluder dimension is evaluated at precision T^-1, while logarithmic terms in T are suppressed in asymptotic notation.
  • Applications: Explicit eluder-dimension bounds yield regret guarantees for discrete MDPs, linear-quadratic control, and generalized linear systems.The paper states that these eluder dimensions scale comparably with more traditional dimensionality notions.
  • Applications: For bounded n-dimensional linear-quadratic systems, the paper applies the general result using the largest eigenvalue λ1 of the Riccati-equation matrix Q.The constrained LQR future-value Lipschitz constant is upper-bounded by 2Cλ1.
  • Comparison with optimism: An optimistic variant could achieve similar high-probability regret bounds, but remains computationally intractable even with an approximate MDP planner.The paper suggests PSRL may be more statistically efficient because it is not affected by loose analysis.

4 Eluder dimension

The paper extends eluder dimension to vector-valued function classes to capture sequential learning complexity in potentially infinite MDPs. It relates this measure to function-class structure and supplies bounds for finite, linear, quadratic, and generalized linear classes.

  • Definition and motivation: The paper extends eluder dimension from real-valued to vector-valued functions to quantify complexity in potentially infinite MDPs.For vector-valued distribution classes, the analysis applies the concept to their mean-function class.
  • Definition and motivation: Eluder dimension measures the longest sequence of inputs whose function values remain unrevealed by observations at preceding inputs.The definition permits nonlinear and approximate dependencies through ε-dependence.
  • Definition and motivation: The eluder dimension is specialized to sequential measurements, unlike traditional supervised-learning measures such as VC dimension.The paper notes that a class learnable quickly for supervised learning may still require arbitrarily long interaction to control well.
  • Function-class bounds: For finite input spaces, a counting argument bounds eluder dimension, with the bound tight for independent measurements.This is stated for any function class and any positive precision ε.
  • Function-class bounds: The paper provides eluder-dimension bounds for linear, quadratic, and generalized linear function classes.The generalized linear class uses a component-wise independent function with bounded derivatives.

5 Confidence sets

The confidence-set analysis centers least-squares estimates inside sets that contain the true reward or transition function with high probability. Eluder dimension then controls how often these sets remain wide and bounds their cumulative predictive deviation.

  • Constructing confidence sets: The analysis builds high-probability confidence sets for reward and transition functions using the eluder dimension.Regret is bounded by the maximum deviation within these confidence sets.
  • Constructing confidence sets: The confidence sets are centered on least-squares estimates, with β_t controlling their growth and empirical norm measuring deviation.The construction uses covering numbers, noise parameters, and a discretization-based control parameter.
  • Constructing confidence sets: Standard martingale concentration combined with discretization ensures that the true function lies in the confidence sets with high probability.The argument extends the corresponding reward-function analysis to vector-valued functions.
  • Controlling uncertainty: Set width is the maximum L2 deviation between any two functions in a confidence set evaluated at an input.This width measures local uncertainty used in the regret analysis.
  • Controlling uncertainty: The eluder dimension bounds the number of large widths and thereby controls the cumulative deviation over time.The argument reorders widths and accounts for the episodic interaction structure.

6 Analysis

The analysis decomposes PSRL regret into cumulative Bellman error, then bounds it using confidence sets and eluder-dimension widths under a future-value regularity condition.

  • Regret decomposition: PSRL regret is decomposed into cumulative Bellman error through repeated dynamic-programming arguments and martingale-difference expectations.The decomposition is the bridge from regret analysis to confidence-set bounds.
  • Regularity assumption: The analysis assumes future value is Lipschitz, a weaker requirement than Lipschitz optimal values because system noise smooths future values.The assumption is needed for efficient regret bounds when state and action spaces are infinite.
  • Confidence sets: Reward and transition confidence sets are constructed jointly, conditioning on events that contain the true and sampled functions in every episode.The sets are denoted R_k and P_k, with the joint conditioning events A and B.
  • Posterior sampling: Posterior sampling equates the expected future-value Lipschitz constant of the sampled MDP with that of the true MDP.This identity is used to control the conditional Lipschitz contribution in the regret analysis.
  • Regret bound: The expected regret bound depends on reward and transition eluder dimensions through τ(C_R d_E(R) + C_P d_E(P)), alongside confidence and covering terms.The proof defines d_E(R) and d_E(P) as eluder dimensions evaluated at T^-1.

7 Conclusion

The paper establishes general dimensional regret bounds for PSRL and identifies computational, episodic, and planning limitations that remain unresolved.

  • Conclusion: PSRL receives a new analysis yielding regret bounds that depend on MDP dimensionality rather than cardinality.The authors describe these as the first regret bounds for reinforcement learning in such a general setting.
  • Limitations: Exact posterior sampling may require extensive computation, and the analysis is restricted to learning with episodic resets.The authors explicitly leave extension to MDPs without episodic resets for future work.
  • Limitations: Planning for an optimal policy can remain intractable even in a known MDP, so the method assumes access to an approximate MDP planner that may require lengthy computations.The conclusion identifies model-free learning as a possible way to avoid complicated MDP planning.

A Confidence sets with high probability

The appendix builds high-probability confidence sets by combining martingale concentration with discretization through an α-cover and controlling the resulting approximation error.

  • Concentration tools: The confidence-set proof begins with exponential-martingale and concentration guarantees for adapted random variables.These lemmas provide the probabilistic control used later in the confidence analysis.
  • Discretization: An α-cover discretizes the function class, enabling a union bound over the finite cover before extending the result to every function.For every f in F, a covered function is chosen within the stated norm tolerance α.
  • Discretization error: The discretization error is bounded under uniform approximation, with Cauchy–Schwarz and sub-Gaussian bounds controlling the summed deviation over time.The appendix then applies this lemma to the least-squares minimizer to obtain the desired high-probability result.

B Bounding the number of large widths

The appendix bounds how often confidence widths can remain large by relating dependence sequences to eluder dimension, then specializes the argument to linear and generalized function classes.

  • Large-width counting: The number of large widths is controlled by finding disjoint subsequences on which a point remains ε-dependent.With episodic update delay, up to τ − 1 proper subsequences may be lost.
  • Eluder dimension: The eluder dimension is the maximum length of a sequence whose elements remain ε-independent under the function class.For every ε > 0, the dimension is bounded by the domain cardinality because each point is ε-dependent on itself.
  • Linear functions: For linear functions, determinant and trace arguments bound the cumulative widths using feature vectors and the evolving matrix V_k.The proof uses V_k = V_{k−1} + φ_kφ_k^T and an upper bound on its determinant.
  • Function-class extensions: The linear-function result extends to quadratic and component-wise transformed classes through reductions and norm rescaling.The transformed-class proof applies the linear argument after reducing the relevant expression and rescaling ε by r.

D Bounded LQR control

The bounded LQR analysis shows that projection preserves or improves the relevant quadratic reward structure, making the value function flatter and yielding an effective Lipschitz constant of 2Cλ1.

  • Bounded LQR model: R(x) = −xT Ax + ǫR and P(x) = ΠC(Bx + ǫP) define the bounded linear quadratic controller through quadratic rewards and projected transitions.A is positive semi-definite, and ΠC projects onto the ∥· ∥2-ball of radius C.
  • Lipschitz control: 2Cλ1 bounds the value difference between two states whose ∥· ∥2-norms are at most C.The bound follows from the quadratic value form and λ1, the largest eigenvalue of Q.
  • Bounded-system consequence: The bounded LQR value function is always greater than or equal to the unconstrained value function because projection excludes the low-reward outer region while retaining the higher-reward inner region.The analysis concludes that the bounded value function becomes flatter, so 2Cλ1 remains an effective Lipschitz constant.

E UCRL-Eluder

The UCRL-Eluder variant forms confidence sets over reward and transition models, then selects an optimistic policy for each episode. Although its regret guarantee is high-probability, the optimism step is generally computationally intractable.

  • Confidence-set construction: At episode k, the algorithm forms reward and transition confidence sets and defines Mk as the MDPs contained in both sets.The confidence sets use β∗ with confidence schedule 1/k2.
  • Optimistic planning: The algorithm computes a policy that maximizes reward over all MDPs in Mk, following the optimistic style of UCRL2.This policy is applied throughout the episode while rewards and successor states are observed.
  • Guarantee: The optimistic algorithm guarantees regret bounds similar to PSRL with high probability over all MDP M∗.Its confidence sets are derived from the PSRL analysis.
  • Computational limitation: Step 4 is generally computationally intractable, even when solving for the optimal policy is possible for a given MDP.The difficulty comes from optimizing over the entire confidence-set family Mk.
Loading 1406.1853v2…