Research map / Bandits and online learning / RL theory and MDPs

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs · 1 citations (OpenAlex)

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 Q-UCRL, an optimism-based model-based quantum RL algorithm for infinite-horizon average-reward MDPs that uses quantum mean estimation on quantum transition oracle samples to claim a regret bound independent of T (O~(1)) versus classical O~(sqrt T).

Problem

Regret minimization for infinite-horizon average-reward tabular MDPs when the agent has access to a quantum transition oracle, with the goal of beating the classical Omega(sqrt T) regret barrier.

Approach

Extends UCRL-style optimistic model-based RL by replacing classical transition estimates with quantum multivariate mean estimates (QBounded) computed at epoch ends, combined across epochs with count-weighted averaging so each quantum sample is measured only once; the regret analysis uses Bellman error bounds rather than martingale concentration.

Key results

• Theorem 1 claims Q-UCRL regret of O(S^5 A^4 T_mix log^3(T/SA) log^{1/2}(T sqrt S) log(S^2 A T)), which is polylogarithmic in T (stated as O~(1)) versus classical O~(sqrt T).
• Quantum mean estimation gives O(1/n) error rate versus classical O(1/sqrt n), a quadratic improvement in estimation.
• The paper's Bellman error bound improves by a quadratic factor over classical UC-UCRL according to the authors.

Measured effects reported in the paper

Surprising findings

• The claimed O~(1) regret is independent of T, which contradicts the classical Omega(sqrt T) lower bound framing and relies on the quantum oracle assumption and a bad-event analysis that the authors state is only O~(1/T^4).

Limitations

• Purely theoretical; no experiments or simulations are reported, and the checklist marks computational experiments as absent.
• Relies on a strong quantum transition oracle assumption and known rewards and finite mixing time.
• Regret bound has large polynomial dependence (S^5 A^4 T_mix) and an extra log factor; the analysis has several possibly inconsistent steps (e.g., Lemma 4 bounds, epoch-count sums).

Experimental setup

Metrics: regret bound (theoretical)

Baselines: UCRL UC-CURL

Builds on: UCRL UC-CURL QBounded quantum multivariate mean estimator

Closest papers by meaning

• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret (ICML 2024 · similarity 0.91)
• Quantum Algorithms for Finite-horizon Markov Decision Processes (ICML 2025 · similarity 0.89)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach (ICML 2025 · similarity 0.87)
• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.86)
• Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.86)
• Quantum Algorithm for Online Exp-concave Optimization (ICML 2024 · similarity 0.86)