Frequentist Regret Bounds for Randomized Least-Squares Value Iteration

Andrea Zanette; David Brandfonbrener; Emma Brunskill; Matteo Pirotta; Alessandro Lazaric

Source-linked AI summary

Frequentist Regret Bounds for Randomized Least-Squares Value Iteration

Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, Alessandro Lazaric

arXiv:1911.00567v7Nov 1, 2019cs.LGstat.ML

TL;DR

Large or continuous-state RL requires function approximation because tabular exploration becomes infeasible, but randomized exploration with such approximation lacked frequentist regret guarantees. The paper introduces an optimistic RLSVI variant for low-rank MDPs and proves a frequentist regret bound while controlling exploration through perturbed value estimates.

Problem
Tabular exploration is infeasible in large or continuous MDPs, while RLSVI had been analyzed with function approximation only for Bayesian regret.
Method
The paper modifies RLSVI with an optimistic default value function and carefully tuned Gaussian perturbations of linear least-squares value estimates.
Results
The paper provides the first frequentist regret analysis for randomized exploration with linear function approximation in finite-horizon low-rank MDPs.
Takeaways & Limitations
The analysis adds a provably efficient randomized-exploration design and analytical techniques for function approximation under low-rank dynamics.
Takeaways & Limitations
The resulting regret has an extra dH factor compared with an optimistic approach, and whether this gap is necessary remains open.

Abstract

from arXiv · show

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approximation is mandatory. In this paper, we introduce an optimistically-initialized variant of the popular randomized least-squares value iteration (RLSVI), a model-free algorithm where exploration is induced by perturbing the least-squares approximation of the action-value function. Under the assumption that the Markov decision process has low-rank transition dynamics, we prove that the frequentist regret of RLSVI is upper-bounded by $\widetilde O(d^2 H^2 \sqrt{T})$ where $ d $ are the feature dimension, $ H $ is the horizon, and $ T $ is the total number of steps. To the best of our knowledge, this is the first frequentist regret analysis for randomized exploration with function approximation.

1 Introduction

Large or continuous-state RL makes tabular exploration infeasible, motivating function-approximation methods with tractable frequentist regret guarantees. The paper analyzes an optimistic RLSVI variant under low-rank transition dynamics.

Motivation: Tabular exploration methods degrade with state and action cardinality, creating a need for scalable exploration with provable regret guarantees.Discretization and contextual-MDP approaches offer partial solutions, but can be computationally intractable or statistically loose.
Prior work: RLSVI integrates Thompson-sampling exploration with linear value-function approximation, but prior analyses covered only tabular settings and Bayesian regret.The paper addresses the gap by providing a frequentist analysis with function approximation.
Contribution: The proposed analysis modifies RLSVI so perturbed value estimates are optimistic with constant probability, despite perturbations propagating across finite-horizon iterations.The perturbation must exceed estimation error while remaining controlled over the horizon.
Main result: The regret bound is expressed in terms of the horizon H, feature dimension d, misspecification level ǫ, and sample count T under low-rank dynamics.The supplied expression includes H, d, ǫ, and T, while its displayed factors are partially garbled.
Open question: The randomized approach retains an extra dH regret factor relative to an optimistic approach, leaving the necessity of this gap as an open research question.The paper frames this comparison as analogous to a gap in the bandit literature.

2 Preliminaries

The paper studies finite-horizon MDPs with unknown rewards and transitions, representing action values linearly in features. Its structural assumption is approximately low-rank transition dynamics with linear rewards.

Learning problem: The agent interacts over fixed-length episodes with unknown transition and reward functions and is evaluated by cumulative regret.Initial states may be chosen arbitrarily and are revealed to the agent.
Function approximation: Linear function approximation represents each action-value function as φ_t(s,a)^Tθ_t, reducing dependence on the state-action space to feature dimension d.The feature map may vary with timestep.
Structural assumption: The MDP is assumed coherent with the feature representation through approximately low-rank transition dynamics and rewards linear in the features.Misspecification is bounded by ǫ in the supplied assumption fragments.
Consequence: When ǫ = 0, the Q-function of every policy is linear in the feature map at every timestep.This proposition connects the low-rank MDP assumption to exact linear value representation.

3 Algorithm

opt-rlsvi combines an optimistic default value function with Gaussian perturbations of least-squares estimates. The design controls abnormal values and creates optimism for exploration without clipping.

Algorithm overview: opt-rlsvi uses an optimistic default value function during an initial phase and injects tuned perturbations to obtain frequentist regret guarantees in low-rank MDPs.The default function controls error propagation rather than adding further optimism.
Randomized exploration: At each episode, the algorithm performs value iteration and perturbs the learned parameter with mean-zero Gaussian noise.The perturbation is applied to the linear least-squares estimate at each timestep.
Randomized exploration: Noise variance scales with the inverse regularized design matrix, producing larger perturbations in less-explored feature directions.The magnitude is selected to ensure sufficient exploration.
Optimism analysis: The analysis proves optimism with constant probability by expressing the value-function difference as a one-dimensional biased random walk.The walk’s bias comes from environment-noise bounds and its variance from injected pseudonoise; clipping would obstruct this analysis.
Value construction: The default value function avoids propagating unreasonable estimates, while the Q-function interpolates between that default and the linear estimate as uncertainty decreases.Continuity facilitates the concentration analysis.

4 Main Result

The paper gives the first frequentist regret bound for a Thompson-sampling-based algorithm with linear value approximation in low-rank MDPs. The bound applies to opt-rlsvi and is compared with deterministic optimism and tabular RLSVI analyses.

The paper presents the first frequentist regret bound for a TS-based algorithm with approximate linear rewards and low-rank transition dynamics.
With probability at least 1 − δ, opt-rlsvi satisfies the theorem’s regret bound under the stated parameter choices and assumptions.
The algorithm can be implemented in space O(d^2H + dAHK) and time O(d^2AHK^2) for finite action spaces.
Unlike related model-based methods that may require Ω(S) computation, opt-rlsvi is designed for linear function approximation and finite action spaces.
In the matched setting, the leading regret term is Hd times worse than Jin et al. (2019).
The additional dH dependence is attributed to the larger perturbations required by Thompson-sampling proofs to guarantee optimism, with total horizon-system dimensionality dH.

5 Proof Outline

The proof decomposes regret into estimation, optimism, and martingale components. It combines concentration bounds with a randomized-walk argument showing constant-probability optimism, then controls warmup and pessimism terms.

The proof combines one-step Q-function expansion, high-probability noise bounds, constant-probability optimism, and a final regret decomposition.
5.1 One-Step Analysis of Q functions: The one-step decomposition separates environment noise, injected pseudonoise, and the next-step value-function difference.
5.4.1 Bound on estimation: Self-normalizing linear-bandit arguments and a union bound control the regression noise uniformly over possible value functions.
5.3 Stochastic Optimism and Random Walk: This matching variance makes the initial randomized value function optimistic with constant probability.
5.3 Stochastic Optimism and Random Walk: The injected pseudonoise forms a one-dimensional normal random walk whose standard deviation matches the high-probability bias from environment noise.
Warmup regret uses a default function while value estimates may be unbounded, and the remaining terms are controlled through concentration and pessimism arguments.

6 Concluding Remarks

The paper establishes high-probability regret analysis for function-approximation RLSVI under approximately low-rank MDP structure. Its proof develops bounded linear value representations, decomposes estimation errors, and controls the resulting terms through concentration arguments.

The work provides high-probability regret bounds for a modified RLSVI algorithm with function approximation.
Compared with optimistic approaches, the method inherits an extra dH regret factor, leaving the corresponding Thompson-sampling question open.
The analysis assumes approximately low-rank transitions, which imply approximately linear Q functions with bounded parameters.
The proof decomposes estimation error into value-function differences, environment noise, pseudonoise, regularization, and low-rank misspecification.
The analysis controls these terms using confidence bounds, good events, and inductive boundedness arguments across timesteps.

E.1 Bounding the Misspecification Error

This section bounds the misspecification contribution arising from the approximately low-rank transition assumption. The argument combines the assumption, bounded value functions, and norm inequalities to control this error term.

The misspecification term is bounded using the approximate low-rank assumption and the boundedness of estimated and true value functions.
The proof applies triangle-inequality, Hölder, and Cauchy–Schwarz arguments to combine the available bounds.

E.3 Bounding the Environment Noise

This section develops concentration and covering arguments for the environment-noise contribution, then uses inductive bounds to control the resulting Q-value estimates. The proof also establishes boundedness across cases in the Q-value interpolation scheme.

The concentration step treats bounded martingale differences as subgaussian and applies self-normalized bounds over a covering of parameter and covariance sets.
The covering argument controls changes in Q-values across linear, default, and interpolating cases.
The boundedness induction shows that the estimated Q-values remain within the horizon-dependent range when the preceding-step values satisfy the induction hypothesis.
The proof combines misspecification, regularization, concentration, and interpolation bounds to maintain the desired Q-value range across timesteps.

E.5 Putting it All Together: Good Event with High Probability

The final argument combines the component bounds through backward induction and a union bound. It obtains a high-probability good event covering all timesteps and episodes.

The proof intersects the component events and then applies a union bound over episodes to obtain the overall guarantee.
The good event holds for every timestep in an episode with probability at least 1 − δ/(8K).
Backward induction starts from the terminal condition Q_H+1,k = 0 and propagates the required bounds toward earlier timesteps.

F Optimism

The analysis establishes optimism by relating perturbed least-squares value estimates to a one-dimensional random walk and controlling the resulting recursion. It decomposes the recursion across state regions and proves a high-probability optimism guarantee.

F Optimism: The optimism proof reduces the value-function difference to a one-dimensional random walk along the optimal policy.Conditioned on the history and starting state, the relevant feature vector is non-random, enabling normal-random-walk arguments.
F Optimism: The recursion partitions states according to feature-norm events and separately bounds the resulting L, S, and M terms.The L term uses a misspecification bound, the S term exploits linearity, and the M term interpolates between linear and default values.
F Optimism: Lemma F.2 proves that the perturbed value estimate is optimistic with high probability under the stated δ and ϵ conditions.The proof combines the optimistic random-walk event with the good-event probability and the recursion bound.

G.1 Main Theorem Statement

The main theorem gives a high-probability regret bound for opt-rlsvi under approximately linear rewards and low-rank transitions. A corollary specializes the result under additional bounds on the feature and model-complexity parameters.

G.1 Main Theorem Statement: Theorem 2 states a joint high-probability regret bound for opt-rlsvi across all episodes under Assumption 2 and specified parameter choices.The theorem sets λ = 1, chooses α_L, α_U, and σ^2 as defined in Section D, and lets T = HK.
G.1 Main Theorem Statement: The proof obtains the theorem by combining the relevant intermediate bounds with a union bound.The text explicitly attributes the final step to a union bound over Lemmas 8 and 9.
G.1 Main Theorem Statement: Corollary 2 specializes the regret guarantee when L_φ = rO(1) and L_ψ, L_r = rO(d).The specialized statement retains probability at least 1 − δ for opt-rlsvi.

G.2 Bounding the Estimation Error

The estimation-error analysis separates well-behaved and large-feature-norm cases, then controls the resulting sums using martingale concentration and feature-sum bounds. The argument combines these components with lower-order terms to obtain the desired high-probability control.

G.2 Bounding the Estimation Error: The estimation analysis splits each timestep into a linear case with small normalized feature norm and a complementary case bounded by H.Under the small-norm event the Q function is linear; otherwise the value-function difference is bounded in the worst case.
G.2 Bounding the Estimation Error: Azuma-Hoeffding controls the martingale-difference terms after the good events bound each truncated summand by 2H.The proof applies this concentration separately to the relevant sums and combines the resulting events.
G.2 Bounding the Estimation Error: The final estimation bound combines the case decomposition, feature-sum inequalities, high-probability good events, and lower-order terms.The text reports that the good events and martingale bounds hold jointly with probability at least 1 − δ/2 before adding the lower-order contribution.