Research map / Bandits and online learning / RL theory and MDPs
Achieving Constant Regret in Linear Markov Decision Processes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Cert-LSVI-UCB, a parameter-free multi-phase LSVI-UCB variant with a certified estimator for misspecified linear MDPs that achieves a high-probability instance-dependent regret bound independent of the number of episodes K.
Problem
Regret of RL with linear function approximation typically grows logarithmically with the number of episodes K; the paper asks whether constant (K-independent) high-probability regret is achievable under misspecification without prior distributional assumptions.
Approach
A certified estimator that stops a multi-phase value-targeted regression when optimistic and pessimistic phase estimates become inconsistent, together with layer-dependent quantization and a covering argument over only the first l+ phases, removes the log K factor; a fine-grained union bound converts gap-based counts into regret.
Key results
- Cert-LSVI-UCB has regret Õ(d^3H^5/Δ) with high probability, independent of K, when misspecification ζ is below Õ(Δ/(√d H^2)).
- In the well-specified case the bound removes the log K factor of prior LSVI-UCB instance-dependent bound Õ(d^3H^5Δ^{-1} log K).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Cert-LSVI-UCB instead of LSVI-UCB | Linear MDP · Well-specified linear MDP | high-probability regret: \tilde\cO(d^3H^5\Delta^{-1} \log(K)) -> \tilde\cO(d^3H^5\Delta^{-1}) | Helped |
| Allow misspecification up to the stated threshold | Cert-LSVI-UCB · Misspecified linear MDP | high-probability regret: \tilde\cO(d^3H^5\Delta^{-1}) | Helped |
| Use Cert-LSVI-UCB without a prior feature-distribution assumption | Linear MDP · Linear MDP | high-probability regret: \tilde \cO(d^3H^5\Delta^{-1}) | Helped |
Surprising findings
- Constant high-probability regret does not contradict the Ω(Δ^{-1} log K) expected regret lower bound; converting to expectation with δ=1/K recovers a logarithmic expected bound.
Limitations
- Dependence on H and d in the instance-dependent bound may not be optimal.
- Analysis assumes uniform misspecification across all actions.
- Misspecification threshold ζ must be below Õ(Δ/(√d H^2)), restricting applicability.
Experimental setup
Metrics: cumulative regret (theoretical bound)
Baselines: LSVI-UCB Sup-LSVI-UCB
Builds on: LSVI-UCB Sup-LSVI-UCB SupLinUCB misspecified linear MDP
Closest papers by meaning
- Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes (ICML 2023 · similarity 0.93)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.92)
- Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes (ICML 2023 · similarity 0.92)
- Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.91)
- Position: Constants are Critical in Regret Bounds for Reinforcement Learning (ICML 2025 · similarity 0.90)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.