PaperlayerView exact revision on arXiv

Source-linked AI summary

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes

Dongruo Zhou, Quanquan Gu, Csaba Szepesvari

arXiv:2012.08507v2cs.LGmath.OCstat.ML

TL;DR

The paper studies whether computationally efficient, nearly minimax-optimal online RL is possible with linear function approximation, focusing on linear mixture MDPs. It develops Bernstein-type concentration tools and two algorithms, obtaining nearly minimax-optimal regret in episodic and discounted settings, with guarantees limited to specified large-dimension and large-sample regimes.

  • Problem

    Online RL with linear function approximation still has a gap between upper and lower regret bounds, motivating the search for computationally efficient nearly minimax-optimal algorithms.

  • Method

    The paper develops a Bernstein-type self-normalized concentration inequality and uses weighted regression and variance-aware bonuses in UCRL-VTR+ and UCLK+ for linear mixture MDPs.

  • Results

    UCRL-VTR+ and UCLK+ achieve regret bounds matching their corresponding lower bounds up to logarithmic factors, making them nearly minimax optimal in their respective settings.

  • Takeaways & Limitations

    The results provide computationally efficient, nearly minimax-optimal online RL algorithms with linear function approximation for linear mixture MDPs.

  • Takeaways & Limitations

    The near-minimax guarantees hold only for stated large-dimension and large-sample regimes, leaving it open whether these restrictions can be removed.

Abstract

from arXiv · show

We study reinforcement learning (RL) with linear function approximation where the underlying transition probability kernel of the Markov decision process (MDP) is a linear mixture model (Jia et al., 2020; Ayoub et al., 2020; Zhou et al., 2020) and the learning agent has access to either an integration or a sampling oracle of the individual basis kernels. We propose a new Bernstein-type concentration inequality for self-normalized martingales for linear bandit problems with bounded noise. Based on the new inequality, we propose a new, computationally efficient algorithm with linear function approximation named $\text{UCRL-VTR}^{+}$ for the aforementioned linear mixture MDPs in the episodic undiscounted setting. We show that $\text{UCRL-VTR}^{+}$ attains an $\tilde O(dH\sqrt{T})$ regret where $d$ is the dimension of feature mapping, $H$ is the length of the episode and $T$ is the number of interactions with the MDP. We also prove a matching lower bound $Ω(dH\sqrt{T})$ for this setting, which shows that $\text{UCRL-VTR}^{+}$ is minimax optimal up to logarithmic factors. In addition, we propose the $\text{UCLK}^{+}$ algorithm for the same family of MDPs under discounting and show that it attains an $\tilde O(d\sqrt{T}/(1-γ)^{1.5})$ regret, where $γ\in [0,1)$ is the discount factor. Our upper bound matches the lower bound $Ω(d\sqrt{T}/(1-γ)^{1.5})$ proved by Zhou et al. (2020) up to logarithmic factors, suggesting that $\text{UCLK}^{+}$ is nearly minimax optimal. To the best of our knowledge, these are the first computationally efficient, nearly minimax optimal algorithms for RL with linear function approximation.

1 Introduction

The paper addresses the remaining gap between upper and lower regret bounds for computationally efficient online RL with linear function approximation by studying linear mixture MDPs. It introduces Bernstein-based methods and algorithms that achieve nearly minimax-optimal regret in episodic and discounted settings, subject to stated dimension and sample-size restrictions.

  • Motivation: Online RL with linear function approximation still had a gap between upper and lower regret bounds, with or without anchor state-action assumptions.The paper frames closing this gap as a central motivation for its work.
  • Setting: Linear mixture MDPs restrict the transition kernel to a linear mixture of basis kernels and permit computationally efficient learning with integration or sampling oracles.The proposed algorithms target this special class of MDPs.
  • Concentration inequality: The paper develops a Bernstein-type self-normalized concentration inequality for vector-valued martingales that improves the dominating term from R√d to σ√d + R.Here R and σ^2 characterize noise magnitude and variance, respectively.
  • Linear bandits: Weighted OFUL applies weighted ridge regression to bounded-noise linear bandits and strictly improves the regret bound obtained by OFUL.Bandits are treated as an episodic RL special case with episode length one.
  • Episodic RL: UCRL-VTR+ combines weighted ridge regression with a new value-function variance estimator for episodic linear mixture MDPs.Its regret is eO(dH√T), with a nearly matching lower bound Ω(dH√T), establishing minimax optimality up to logarithmic factors.
  • Discounted RL: UCLK+ extends UCLK to discounted linear mixture MDPs and attains eO(d√T/(1 − γ)^1.5) regret, matching the corresponding lower bound up to logarithmic factors.The result suggests near minimax optimality for the discounted setting.
  • Contribution: The paper presents UCRL-VTR+ and UCLK+ as the first computationally efficient, nearly minimax-optimal online RL algorithms with linear function approximation, ignoring logarithmic factors.The comparison is made against previous bounds that differed from lower bounds by factors involving d, H, or 1/(1 − γ).

2 Related Work

Prior work developed linear-bandit methods and several linear-function-approximation formulations for RL, while nearly minimax optimal online RL remained unresolved. This paper extends Bernstein-bonus ideas to linear function approximation.

  • Linear Bandits: Linear bandits are studied as the simplest RL setting, with episode length H = 1.
  • Linear Bandits: Earlier infinite-armed linear-bandit algorithms progressively improved regret guarantees, with Li et al. (2019b) matching the lower bound up to logarithmic factors.
  • Linear Bandits: Previous linear-bandit work focused on sub-Gaussian reward noise, whereas bounded magnitude and variance permit a better regret bound.
  • RL with Linear Function Approximation: Existing RL formulations include low Bellman rank, linear MDPs, low inherent Bellman error, and linear mixture MDPs.
  • Bernstein Bonuses for Tabular MDPs: Tabular Bernstein-bonus methods use the law of total variance, and this work extends that idea to linear function approximation.

3 Preliminaries

The paper formalizes episodic and discounted MDPs, their value functions and regret objectives, and the linear mixture assumptions used for transition kernels. The unknown transition parameters are learned online under oracle access to basis kernels.

  • The paper studies RL with linear function approximation in both episodic and infinite-horizon discounted MDPs.
  • Episodic MDPs: An episodic MDP has horizon H, stage-dependent rewards and transition kernels, and policies selecting actions across the H stages.
  • Regret: Regret measures the loss relative to optimal value: episodic regret aggregates per-episode gaps, while discounted regret sums suboptimality gaps over T interaction rounds.
  • Discounted MDPs: A discounted MDP uses discount factor γ ∈ [0,1), deterministic rewards in [0,1], and transition kernel P.
  • Linear Mixture MDPs: In a linear mixture MDP, each transition probability is the inner product of a feature vector and an unknown parameter vector bounded by B.
  • Linear Mixture MDPs: For discounted problems, the effective horizon is defined as H̄ = 1/(1 − γ).

4 Challenges and New Technical Tools

The paper identifies conservative, magnitude-based confidence bounds and heteroscedastic regression as barriers to minimax regret, then develops variance-aware concentration and estimation tools. These tools support Weighted OFUL for bounded-noise linear bandits and the design of improved RL algorithms.

  • Barriers to Minimax Optimality: UCRL-VTR learns an unknown transition parameter and constructs optimistic action-value estimates, but its magnitude-based confidence radius limits the resulting regret analysis.The method uses regularized linear regression and confidence ellipsoids centered at the learned parameter.
  • Barriers to Minimax Optimality: Confidence radii based on value-function magnitude are too conservative because value-function variance can be smaller by a factor H.This motivates variance-sensitive Bernstein-type concentration bounds.
  • Barriers to Minimax Optimality: Non-uniform response variances create a heteroscedastic linear bandit problem that uniform variance bounds cannot improve.The proposed remedy is to estimate variances and use weighted least-squares estimation.
  • Bernstein-type Concentration: Theorem 4.1 extends scalar Bernstein concentration to self-normalized vector-valued martingales with bounded noise magnitude and variance.It strengthens prior Hoeffding-Azuma-type self-normalized inequalities in this bounded-noise setting.
  • Bernstein-type Concentration: The new concentration inequality improves prior bounds by exploiting noise variance, which is bounded above by noise magnitude or sub-Gaussian norm.The improvement applies to a smaller class of bounded-magnitude and bounded-variance noise distributions.
  • Weighted Ridge Regression and Heteroscedastic Linear Bandits: Weighted OFUL extends OFUL by incorporating variance information through weighted ridge regression for bounded-noise linear bandits.Its regret is strictly better than OFUL because σ_t ≤ R.

5 Optimal Exploration for Episodic MDPs

UCRL-VTR+ extends value-targeted regression to episodic linear mixture MDPs using variance-aware weighted estimation and optimistic confidence sets. Its regret upper bound is matched by a lower bound up to logarithmic factors, establishing minimax optimality.

  • UCRL-VTR+ is an improved UCRL-VTR algorithm for episodic linear mixture MDPs.
  • The algorithm maintains ellipsoidal confidence sets and constructs optimistic action-value estimates, acting greedily with respect to them.
  • Weighted Ridge Regression and Optimistic Estimates of Value Functions: Weighted ridge regression estimates the transition parameter using value-function variance information rather than only value-function magnitude.
  • Variance Estimator: The variance estimator combines empirical first- and second-moment estimates with an offset term and clips the result to control its range.
  • For linear mixture MDPs, the algorithm has computational complexity O(poly(d)|A|T).
  • With probability at least 1 −5δ, UCRL-VTR+ satisfies the episodic regret upper bound stated in Theorem 5.3.
  • A matching lower bound of Ω(dH√T) shows that UCRL-VTR+ is minimax optimal up to logarithmic factors.

6 Optimal Exploration for Discounted MDPs

For discounted linear mixture MDPs, the paper proposes UCLK+ and analyzes its optimistic exploration, weighted estimation, confidence sets, and regret. The analysis shows near-minimax performance in the stated large-dimension and large-sample regime.

  • UCLK+ is the discounted counterpart of UCRL-VTR+ and is designed for infinite-horizon discounted linear mixture MDPs.
  • Algorithm and analysis: UCLK+ uses multi-epoch optimistic planning, maintaining confidence sets of plausible MDPs and applying Extended Value Iteration to select a near-optimal plausible model.Epoch boundaries depend on previous observations, and the confidence set includes the true parameter with high probability.
  • Algorithm and analysis: The algorithm modifies UCLK’s bonus through weighted ridge regression, using an empirical variance estimate plus an offset term to upper-bound the true variance.The paper expects this weighting to produce a more accurate estimate of the underlying parameter.
  • Computational efficiency: EVI is computationally efficient under the stated oracle assumptions because its value updates reduce to polynomial-time maximizations over the confidence set and actions.The construction uses vectors computed over a fixed polynomial-size state subset and a factored linear model.
  • Regret analysis: With probability at least 1 − 5δ, Theorem 6.3 bounds UCLK+’s total regret for discounted, B-bounded linear mixture MDPs when λ = 1/B^2.The confidence-set and variance guarantees used in the analysis hold with probability at least 1 − 3δ simultaneously over 1 ≤ t ≤ T.
  • Regret analysis: In the large-dimension and large-sample regime, UCLK+ matches the discounted linear-mixture regret lower bound up to logarithmic factors and is therefore nearly minimax optimal.The stated regime uses U = ⌈(1 − γ)^−1 log(T/(1 − γ))⌉, d ≥ (1 − γ)^−1, and T ≥ d^4(1 − γ)^−1 + d^3(1 − γ)^−2.

7 Conclusion and Future Work

The paper develops a Bernstein-type concentration inequality and uses it to obtain nearly minimax-optimal regret guarantees for linear mixture MDPs, while identifying restrictions on the regimes where optimality holds.

  • The Bernstein-type concentration inequality tightens existing self-normalized confidence sets for linear bandits in low-variance settings.It improves the dominating dimension-dependent term when the reward noise has variance σ2 and bounded magnitude R.
  • UCRL-VTR+ achieves eO(dH√T) regret for episodic linear mixture MDPs.The algorithm is computationally efficient and is based on the new concentration inequality.
  • Both regret bounds match corresponding lower bounds up to logarithmic factors, establishing near-minimax optimality.The conclusion applies to both proposed algorithms and their respective settings.
  • The near-minimax claims currently apply only in large-dimension and large-sample regimes.For UCRL-VTR+, the stated conditions are d ≥ H and T ≥ d4H2 + d3H3; for UCLK+, they are d ≥ (1−γ)−1 and T ≥ d4(1−γ)−1 + d3(1−γ)−2.

A The Definition of State- and Action-value Functions for Nonstationary Policies in Discounted MDPs

This section defines state- and action-value functions for nonstationary policies using probability distributions over future trajectories conditioned on histories and state-action pairs.

  • The construction fixes a nonstationary policy, state-action pair, time index, and history before defining a probability distribution over future trajectories.The distribution incorporates the transition kernels and the policy’s future action choices.
  • The value function Vπ_t is defined similarly from the same history-dependent construction.These definitions are intended to avoid an ill-defined formulation in the introduction.
  • The action-value function Qπ_t(s,a) is defined using the expectation associated with the constructed trajectory distribution.The notation suppresses the dependence of the value on the history.
  • The Bellman equations follow directly from these definitions, and the resulting values agree with the introductory definitions whenever those values are well-defined.This agreement holds regardless of the initial distribution used in the introductory formulation.

B Proof of Theorems in Section 4

This section establishes the proofs of the theorems stated in Section 4.

  • The section proves Theorem 4.1 and Corollary 4.2.

B.1 Proof of Theorem 4.1

The proof of Theorem 4.1 combines Freedman’s inequality, self-normalized concentration, matrix identities, and induction to establish a uniform high-probability bound.

  • Concentration ingredients: The proof follows Dani et al. (2008) with a refined analysis and invokes Freedman’s inequality together with a self-normalized linear-bandit result.The argument uses martingale measurability and bounded-noise conditions.
  • Concentration ingredients: The auxiliary lemmas bound the martingale terms using conditional variance, almost-sure noise bounds, increasing confidence radii, and union bounds over time.These bounds are established simultaneously for all t with controlled failure probability.
  • Final bound: Matrix inversion identities and monotonicity of Zt control the proof’s intermediate terms and yield the final confidence bound on the high-probability event.The event holds with probability at least 1 − δ after combining the lemma events.
  • Inductive argument: The proof defines an event on which the auxiliary lemmas hold and uses induction to show Zi ≤ βi for every i.The base case is Z0 = β0 = 0, and the induction step substitutes the auxiliary bounds into the recursive inequality.

B.2 Proof of Theorem 4.2

The proof establishes a high-probability confidence event, bounds each round’s pseudo-regret using optimism, and controls the cumulative terms through a two-set decomposition and self-normalized estimates.

  • With high probability, the concentration event holds and the optimal parameter belongs to the confidence set.The proof applies Theorem 4.1 to normalized covariates and noise, then proceeds on the resulting event.
  • Optimism bounds the round-t pseudo-regret by the difference between the optimistic parameter and the true parameter.The decomposition introduces the previous estimate as an intermediate term.
  • The cumulative bound decomposes the rounds into two disjoint subsets, I1 and I2, to separately control their contributions.The proof then applies norm bounds, Cauchy-Schwarz, and inequalities for the normalized features.
  • Substituting the bounds for the decomposed terms yields the theorem’s final result.

B.4 Derivation of the Bound in (4.5)

This derivation extends a self-normalized concentration bound to bounded noise and uses it to construct nested confidence sets with a high-probability guarantee.

  • The argument restates a concentration inequality and extends it to the general case of noise bounded by R.The extension handles conditional second-moment information in addition to boundedness.
  • A regularization choice λ = eΘ(dR2L2/(σ2 + RL∥µ∗∥2)) minimizes the resulting upper bound on ∥µt − µ∗∥Zt.
  • The proof tracks filtrations and measurability to apply concentration results to the episodic algorithm’s confidence-set construction.It explicitly distinguishes variables measurable before and after each episode stage because of the backward construction.
  • A two-step peeling argument defines confidence sets ˇCk,h and eCk,h and establishes their required containment relations.The proof notes that the refined set bCk,h is contained in ˇCk,h and uses weighted estimates to reduce the leading factor.
  • With probability at least 1 −3δ, the target parameter belongs to the refined confidence sets across stages and episodes.

C.2 Proof of Theorem 5.3

The proof of Theorem 5.3 combines optimism, variance control, Azuma-Hoeffding concentration, and elliptical-potential bounds to obtain the regret guarantee.

  • On the confidence event, Lemma C.4 establishes that the algorithm’s Q-values upper-bound the optimal Q-values by induction.The induction uses optimism, confidence-set membership, and monotonicity of the transition operator.
  • Lemma C.5 controls the cumulative variance-related terms using Bellman equations, Cauchy-Schwarz, and telescoping arguments.
  • Lemma C.6 bounds the remaining feature-dependent contribution through an elliptical-potential term involving 2dH log(1 + K/λ).
  • Substituting the component bounds and simplifying yields the theorem’s regret inequalities.The proof also uses the total variance lemma and algebraic loosening to complete the bound.
  • An event intersection holds with probability 1 −5δ, allowing the proof to invoke Lemmas C.4, C.5, and C.6 simultaneously.

C.3 Proof of Theorem 5.6

The lower-bound proof constructs a family of episodic MDPs whose regret can be related to linear bandit regret, then applies a bandit lower bound across stages.

  • The hard MDP family is analyzed through transition probabilities, expected actions, and the value difference between optimal and arbitrary policies.
  • Only the absorbing state xH+2 provides reward 1, so the value difference is characterized by the probability of reaching that state.
  • The optimal policy selects at each stage the action maximizing ⟨µh, a⟩, whose maximum equals (d −1)∆.
  • A linear bandit lower bound is established for hypercube actions and Bernoulli rewards using Pinsker’s inequality and relative-entropy decomposition.
  • Each policy induces a bandit algorithm whose stage-h action distribution matches the policy’s conditional MDP action distribution.The construction feeds the policy the known kernels and observed outcomes to simulate the corresponding stage.
  • The resulting lower bound is obtained by applying the bandit guarantee and substituting δ = 1/H and T = KH.

D.2 Proof of Theorem 6.3

The proof of Theorem 6.3 combines high-probability events, optimism, variance control, epoch counting, and self-normalized bounds to control the regret. Technical lemmas establish confidence-set validity, bounded value estimates, martingale concentration, and logarithmic epoch growth before the final regret bound follows.

  • Martingale concentration: The martingale sequence Mt has conditional mean zero and bounded magnitude |Mt| ≤ 4 ¯H, enabling concentration through Lemma C.2.Measurability of πt+1, Vt, at, and st+1 establishes the martingale-difference property and adaptedness.
  • Regret decomposition: The regret decomposition controls value-estimation terms using total-variance bounds, Cauchy–Schwarz inequalities, confidence-set geometry, and the bounded variation of Vt within epochs.The proof separately bounds terms I1, I2, and I3 before substituting the resulting inequalities into the main regret relation.
  • Optimism and confidence sets: The confidence construction is optimistic: ¯H ≥ Qt(s,a) ≥ Q∗(s,a) and ¯H ≥ Vt(s) ≥ V∗(s), while Lemma D.4 supplies a suitable θt in each epoch confidence set.These inequalities support replacing optimal values with optimistic estimates during the regret decomposition.
  • Epoch complexity: K(T) ≤ 2d log(1 + Td/λ), because determinant growth under the epoch update rule limits the number of epochs.The proof uses det(Σ0)=λ^d, det(ΣT)≤(λ+dT)^d, and doubling determinant growth across epochs.
  • High-probability events: With probability at least 1−5δ, the events E, E1, and E2 hold simultaneously, providing the high-probability basis for the regret analysis.Event E follows with probability at least 1−3δ, while E1 and E2 each hold with probability at least 1−δ.
  • Final bound: Combining the intermediate bounds and using Lemma D.3 yields Regret(T) ≤ Regret′(T), completing the proof of Theorem 6.3.The final rearrangement uses K(T)=e^O(d) and the auxiliary inequality x=e^O(a√x+b) ⇒ x=e^O(a^2+b).
Loading 2012.08507v2…