Research map / Bandits and online learning / RL theory and MDPs
Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret
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 quantum UCRL-style algorithms for online exploration in tabular and linear mixture MDPs that use quantum amplitude/mean estimation with lazy doubling-trick updates to achieve poly(log T) worst-case regret.
Problem
Online exploration in quantum reinforcement learning with quantum-accessible environments: achieving regret better than the classical Omega(sqrt(T)) barrier for tabular and linear mixture MDPs.
Approach
Combine UCRL2/UCRL-VTR style optimism with quantum multi-dimensional amplitude estimation and multivariate mean estimation, using a doubling-trick lazy update schedule (for visit counts in tabular MDPs, and determinant doubling for linear mixture MDPs) plus a binary-search feature estimation procedure, so that quantum samples can be reused and estimation error shrinks faster than classical 1/sqrt(
Key results
- Quantum UCRL achieves regret O(S^2 A H^3 log(T) log(S^2AH log(T)/delta)) for tabular MDPs with high probability.
- Quantum UCRL-VTR for linear mixture MDPs achieves regret O(d^{5/2} H^{9/2} log^{3/2}(1+T^3/d) * iota), logarithmic in T.
- The paper notes that the tabular and linear results break the classical Omega(sqrt(T)) worst-case lower bound, and the results are theoretical with no experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum amplitude estimation and lazy updating in place of classical sampling-based model estimation | Tabular MDP exploration · Tabular MDP | regret: \tilde{\cO}(\mathrm{poly}(S, A, H) \cdot \sqrt{T}) -> \caO\left(S^2 A H^3 \log(T) \log(S^2AH \log(T) / \delta)\right) | Helped |
| Use quantum mean estimation, feature estimation, and lazy updating in place of classical sampling-based estimation | Linear mixture MDP exploration · Linear mixture MDP | regret: \tilde{\cO}(\mathrm{poly}(d, H) \cdot \sqrt{T}) -> \cO\Big( d^{5/2} H^{9/2} \log^{3/2}\big(1 + \frac{T^3}{d}\big) \cdot | Helped |
Surprising findings
- Logarithmic worst-case regret in quantum RL circumvents the classical Omega(sqrt(T)) lower bound that applies to classical algorithms.
Limitations
- Dependence on S, H (and d, H) is likely not tight; the paper conjectures improvements.
- Assumes a quantum-accessible environment with transition and reward oracles and known reward function.
- Results are purely theoretical with no empirical validation.
Experimental setup
Metrics: worst-case regret
Baselines: UCRL2 UCRL-VTR classical sqrt(T) regret algorithms
Builds on: UCRL2 UCRL-VTR UCBVI quantum amplitude estimation quantum multivariate mean estimation
Closest papers by meaning
- Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes (ICML 2025 · similarity 0.91)
- Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets (AAAI 2023 · similarity 0.90)
- Quantum Algorithms for Finite-horizon Markov Decision Processes (ICML 2025 · similarity 0.88)
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.87)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.87)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.87)
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.