📊 statistics

A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

This paper introduces novel classical and quantum online reinforcement learning algorithms for finite- and infinite-horizon Markov Decision Processes under a generative model that leverage direct optimal policy computation to bypass traditional paradigms like optimism and posterior sampling, achieving improved regret bounds including a polylogarithmic dependence on time steps for quantum methods.

Original authors: Andris Ambainis, Joao F. Doriguello, Debbie Lim

Published 2026-07-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Andris Ambainis, Joao F. Doriguello, Debbie Lim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game where the rules are hidden. You don't know which buttons lead to treasure and which ones drop you into a pit. To win, you have to keep pressing buttons, watching what happens, and slowly figuring out the best strategy. This is the heart of Reinforcement Learning (RL), a branch of artificial intelligence where a computer "agent" learns by interacting with an environment to maximize rewards. The mathematical framework for this is called a Markov Decision Process (MDP). Think of an MDP as a map of all possible game states (like "standing on a cliff" or "holding a key") and the probabilities of what happens next when you take an action. The goal is to find the perfect "policy"—a rulebook that tells the agent exactly what to do in every situation to get the highest score.

For a long time, scientists have been trying to make these learning agents smarter and faster. A major hurdle has been the "exploration vs. exploitation" dilemma: should the agent try new, risky moves to learn more about the world (exploration), or stick to the moves it already knows are good (exploitation)? Most traditional methods rely on a strategy called "optimism in the face of uncertainty," where the agent guesses that unknown paths might be amazing just to encourage trying them. However, this paper introduces a twist: what if the agent had a "cheat code" or a "simulator" it could use occasionally to test moves without actually playing the game? The authors explore how giving the agent this special access, combined with the power of quantum computing, could revolutionize how fast these agents learn.

The Paper's Big Idea: A Hybrid Training Camp

The authors, Andris Ambainis, Joao F. Doriguello, and Debbie Lim, propose a new way to train these AI agents. They suggest a hybrid online-offline model. Imagine the agent is a student. In the "online" phase, the student is in a real classroom, taking a test. Every wrong answer costs them points (this is the "regret" or the penalty for not being perfect). This is the expensive, real-world part. But then, the student gets a break. They step into a "simulation lab" (the offline phase). In this lab, they have a magical "generative model"—a simulator that can instantly show them the outcome of any move they want, over and over again, without any penalty.

The key innovation here is that the agent can switch between these two modes. It plays the real game for a while, accumulates some mistakes, and then goes to the simulator to crunch the numbers and figure out the perfect strategy. Once it has a better plan, it goes back to the real game. The paper argues that this "bit of freedom" to use a simulator changes everything.

Ditching the Old Rules

One of the most interesting parts of the paper is what it tells us not to do. For decades, the standard advice for RL agents was to use "optimism in the face of uncertainty." This is like telling a student, "Since you don't know if that door leads to gold or a trap, assume it's gold so you'll go check it out." The authors show that if you have access to a simulator (even just occasionally), you don't need to guess. You can just go into the simulator, run the numbers, and calculate the actual best move directly.

They explicitly argue against the need for "optimism" or "posterior sampling" (another complex guessing method) in this specific setup. Instead of guessing what might be true, the agent can compute the optimal policy directly using the simulator data. This shift allows them to avoid the messy, uncertain parts of traditional learning and jump straight to the solution.

The Quantum Superpower

Now, let's talk about the "quantum" part. The authors didn't just stop at using a simulator; they asked, "What if the simulator runs on a quantum computer?" Quantum computers are famous for being able to process vast amounts of possibilities simultaneously. By using quantum algorithms inside the simulator phase, the agent can estimate the outcomes of actions much faster than a classical computer could.

The paper presents new algorithms for three different types of game scenarios:

Finite-Horizon: Games that end after a set number of steps (like a level in a video game).
Infinite-Horizon Discounted: Games that go on forever, but future rewards are worth slightly less than immediate ones (like earning interest on money).
Infinite-Horizon Undiscounted: Games that go on forever with equal weight on all rewards (like a steady job).

For all these scenarios, the authors found that their quantum algorithms can achieve a "regret bound" that depends on the number of time steps ( $T$ ) only by a tiny amount (like the logarithm of $T$ , or $\log T$ ). However, it is crucial to note that the performance still depends significantly on the size of the game world itself. The algorithms' efficiency is heavily influenced by the number of possible states ( $S$ ), the number of possible actions ( $A$ ), and the game's length or effective horizon ( $H$ or $\Gamma$ ). While the quantum agent's error grows very slowly as the game gets longer (polylogarithmic in $T$ ), the complexity of the calculation still scales with the size of the state and action spaces.

In plain English, this means that as the game gets longer and longer, the quantum agent's performance doesn't degrade much at all relative to time, but the initial "cost" to learn the game is still determined by how complex the game map is. In contrast, classical algorithms usually see their errors grow with the square root of time ( $\sqrt{T}$ ). The paper shows that by using the quantum simulator, the agent can break the classical barrier, learning exponentially faster specifically when the agent is allowed a certain amount of time in the simulator (controlled by a "budget" parameter $\beta$ between 1 and 2). If the agent is allowed enough freedom to practice in the simulator, the quantum advantage is massive; if the simulator time is too short, the advantage shrinks.

How Sure Are They?

The authors are very confident in their mathematical proofs. They didn't just run a simulation on a computer and say, "It looks like it works." They provided rigorous mathematical proofs showing that their algorithms will produce an optimal policy with a specific probability (usually $1 - \delta$ , where $\delta$ is a tiny chance of failure). They proved that their quantum algorithms require fewer "queries" (or checks of the simulator) to reach a good solution compared to the best-known classical methods.

However, they are also careful to note the conditions. Their "super-fast" results depend heavily on the "budget" parameter ( $\beta$ ), which controls how much time the agent spends in the simulator versus the real world. If the agent is allowed enough time in the simulator (specifically when $\beta$ is between 1 and 2), the quantum advantage is massive. If the simulator time is too short, the advantage shrinks. They also point out that their method relies on the agent having access to a "generative model" (the simulator), which is a specific type of setup that isn't always available in every real-world scenario.

The Bottom Line

This paper suggests that if we can give AI agents a "sandbox" to practice in—a simulator where they can test moves freely—and if we can run that sandbox on a quantum computer, we can teach them to master complex environments incredibly fast. They don't need to guess or be overly optimistic; they can just calculate the best path. While this requires a specific setup (the hybrid model and quantum access) and the speedup is most dramatic when the agent has enough "practice time" in the simulator, the results show a clear path toward AI that learns with a level of efficiency that classical computers simply cannot match. It's a reminder that sometimes, a little bit of freedom to practice without consequences goes a very long way.

Technical Summary: A Bit of Freedom Goes a Long Way

Problem Statement

The paper addresses the problem of learning Markov Decision Processes (MDPs) in an online setting, specifically focusing on minimizing regret (the difference between the agent's accumulated reward and that of an optimal policy). The authors study three distinct MDP settings:

Finite-horizon MDPs: Agents interact for a fixed number of steps $H$ .
Infinite-horizon discounted MDPs: Agents interact indefinitely, with rewards discounted by a factor $\gamma \in [0, 1)$ .
Infinite-horizon undiscounted MDPs: Agents interact indefinitely with average reward criteria, specifically focusing on weakly communicating MDPs.

A central challenge in Reinforcement Learning (RL) is the exploration-exploitation trade-off. Traditional online RL algorithms often rely on principles like "optimism in the face of uncertainty" or "posterior sampling" to manage uncertainty about the environment's transition probabilities. The paper investigates whether these paradigms can be bypassed by introducing a hybrid interaction model that allows for "offline" generative access to the environment.

Methodology

The Hybrid Online-Offline RL Model

The core methodological contribution is the proposal of a hybrid online-offline RL model. This model separates the learning process into two alternating phases:

Online Phase (Exploration): The agent interacts with the environment classically. It chooses actions, receives rewards, and observes state transitions. Crucially, regret accumulates during this phase.
Offline Phase (Generative Learning): The agent has access to a "simulator" or oracle ( $C_p$ classically, $Q_p$ quantumly) that allows it to sample transitions from the environment in a generative fashion. During this phase, the agent can perform arbitrary computations, including quantum operations and accessing the inverse of the oracle, without accumulating regret.

The "freedom" in this model is regulated by a budget parameter $\beta$ . If the online phase lasts $\tau$ steps, the agent is allowed $O(\tau^\beta)$ queries to the oracle in the subsequent offline phase. This constraint prevents the agent from trivially solving the problem by simply simulating the environment enough times to learn the optimal policy perfectly before interacting online.

Algorithmic Approach

The proposed algorithms follow a phased structure (Algorithm 1):

The agent runs an online phase of length $\tau_\ell$ .
In the subsequent offline phase, the agent uses the oracle to compute an $\epsilon_\ell$ -optimal policy using subroutines derived from Section 2.
The length of the online phase increases (doubling trick) to balance the cost of exploration against the precision of the computed policy.

The authors avoid standard "optimism" heuristics. Instead, they directly compute approximate optimal policies during the offline phase using:

Classical Subroutines: Variance-reduced value iteration (based on Sidford et al. [55]) and standard backward induction.
Quantum Subroutines: Quantized versions of value iteration employing Quantum Mean Estimation (Kothari and O'Donnell [57]) for estimating expected values and Quantum Minimum Finding (Dürr and Høyer [58]) for selecting optimal actions.

Correction of Prior Quantum RL Works

The paper critically analyzes previous quantum RL works (e.g., [23, 24, 98]), arguing they contain a fundamental flaw. These works assumed that quantum amplitude estimation could be performed on a collection of stored quantum states $\{Q_p|s\rangle, Q_p^\dagger|s\rangle\}$ . The authors clarify that amplitude estimation requires sequential, coherent applications of the oracle on a single quantum state, not access to a static collection of states. The proposed hybrid model resolves this by treating the collection of exploration steps as the "online" phase and the coherent quantum computation as the "offline" phase.

Key Contributions and Results

1. Novel Quantum Algorithms for Policy Computation

The authors present new quantum algorithms for computing $\epsilon$ -optimal policies under a generative model, serving as subroutines for the online learning process:

Finite-Horizon: A quantum algorithm with query complexity $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$ . This improves upon classical bounds and matches concurrent work [60].
Infinite-Horizon Discounted: A quantum algorithm with query complexity $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$ .
Infinite-Horizon Undiscounted: A novel quantum algorithm for weakly communicating MDPs with query complexity $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$ , assuming the Bellman operator is a $J$ -stage $\nu$ -span contraction.

2. Improved Regret Bounds

By leveraging the hybrid model and the new subroutines, the paper derives new regret bounds for online learning:

Finite-Horizon:
- Classical: Matches the state-of-the-art $\tilde{O}(\sqrt{HSAT})$ for specific parameter ranges but avoids extra terms found in prior works.
- Quantum: Achieves $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ . For $\beta \in [1, 2)$ , the dependence on $T$ is reduced to polylogarithmic, breaking the classical $\sqrt{T}$ barrier.
Infinite-Horizon Discounted:
- Classical: Matches the $\tilde{O}(\sqrt{\Gamma^3SAT})$ bound of He et al. [97] under certain conditions.
- Quantum: Achieves $\tilde{O}(\min\{\Gamma^{1.5}SA, \Gamma^3S\sqrt{A}\} T^{1-\beta})$ . For $\beta \ge 1$ , the regret is polylogarithmic in $T$ , representing a new result.
Infinite-Horizon Undiscounted:
- Classical: Improves upon the $\tilde{O}(\Lambda \sqrt{S^2AT})$ bound of Bartlett and Tewari [26] to $\tilde{O}(\sqrt{\Lambda SAT})$ .
- Quantum: Achieves $\tilde{O}(\Lambda S \sqrt{A} T^{1-\beta})$ . For $\beta \ge 1$ , the regret is polylogarithmic in $T$ , a significant improvement over the $\tilde{O}(\Lambda S^5 A^4)$ bound of prior quantum work [98].

3. Analysis of the Budget Parameter $\beta$

The paper identifies a "sweet spot" for the budget parameter $\beta$ :

$\beta < 1$ : Both classical and quantum algorithms exhibit polynomial regret in $T$ .
$\beta \in [1, 2)$ : Quantum algorithms achieve exponential improvement in $T$ (polylogarithmic regret) compared to classical algorithms (which remain $\tilde{O}(\sqrt{T})$ ).
$\beta \ge 2$ : The quantum advantage in $T$ vanishes as classical algorithms also achieve polylogarithmic regret.

Significance and Claims

The paper claims that the introduction of a "bit of freedom" (the offline generative phase) fundamentally changes the landscape of RL. By decoupling the accumulation of regret from the policy computation, the authors demonstrate that:

Paradigm Shift: It is possible to avoid standard RL heuristics like "optimism in the face of uncertainty" and instead compute optimal policies directly using generative access.
Quantum Advantage: Quantum computers can provide substantial advantages in the learning process, specifically achieving polylogarithmic regret in the number of time steps $T$ for a specific range of the budget parameter ( $\beta \in [1, 2)$ ).
Model Correction: The work rectifies fundamental errors in previous quantum RL literature regarding the implementation of amplitude estimation, establishing a rigorous framework for future quantum RL research.

The authors conclude that while their model assumes an offline phase (which may not exist in all physical settings), it stimulates the exploration of new RL models and highlights the potential of quantum speedups when agents have limited, structured access to environment simulations. They acknowledge that formalizing a meaningful quantum RL model without offline phases that still achieves polylogarithmic regret remains an open question.