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

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 consider three distinct MDP settings:

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

A central challenge in Reinforcement Learning (RL) is the exploration-exploitation trade-off. In the classical setting, agents must learn transition probabilities $p(\cdot|s, a)$ while interacting with the environment. In the quantum setting, a fundamental issue arises: standard quantum oracles allow for superposition and inverse operations, which can lead to undefined regret measures if the agent interacts with the environment in a quantum fashion throughout the learning process. Furthermore, prior quantum RL works attempting to achieve polylogarithmic regret in time $T$ relied on flawed assumptions regarding the coherent application of quantum amplitude estimation.

Methodology

The Hybrid Online-Offline RL Model

To resolve the definitional issues of regret in quantum RL and to leverage quantum speedups, the authors propose a hybrid online-offline RL model. This model separates the learning process into two distinct phases:

1. 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. The agent does not have access to quantum oracles here.
2. Offline Phase (Generative Learning): The agent is granted "freedom" to interact with the environment via a generative model.
   • In the classical offline phase, the agent accesses a sampling oracle $C_p$ that returns next states $s'$ given $(s, a)$.
   • In the quantum offline phase, the agent accesses a quantum oracle $Q_p$ (and its inverse) that prepares superpositions of next states.
   • Constraint: The number of oracle calls in the offline phase is bounded by a function of the previous online phase's length $\tau$, specifically $O(\tau^\beta)$, where $\beta \in [0, \infty)$ is a "budget" parameter. This prevents the agent from obtaining a near-optimal policy with zero regret by simply querying the oracle excessively.

Algorithmic Approach

The proposed algorithms (Algorithm 1) progress in epochs. In each epoch $\ell$:

1. Offline Computation: Using the data gathered in the previous online phase (length $\tau_{\ell-1}$), the agent computes an $\epsilon_\ell$-optimal policy.
   • Classical: Uses known sample-optimal algorithms (e.g., Sidford et al.) to compute policies.
   • Quantum: The authors introduce novel quantum algorithms for computing optimal policies under a generative model. These algorithms utilize quantum mean estimation (Kothari and O'Donnell) and quantum minimum/maximum finding (Dürr and Høyer) to accelerate value iteration.
2. Online Execution: The computed policy $\pi^{(\ell)}$ is executed in the environment for a duration determined by a doubling trick (increasing the horizon by a factor of 2 or $2H$).
3. Regret Analysis: The total regret is bounded by summing the sub-optimality of the policies used in each online phase.

Key Technical Contributions

1. Novel Quantum Algorithms for Generative Models:

   • Finite-Horizon: The authors design quantum algorithms that improve upon classical query complexity. They combine quantized value iteration with variance reduction techniques. The query complexity is $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$, improving the dependence on $H$ and $A$ compared to classical bounds.
   • Infinite-Horizon Discounted: Similar improvements are achieved, with query complexity $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$.
   • Infinite-Horizon Undiscounted: This is a new contribution. The authors propose a quantum algorithm for weakly communicating MDPs under the assumption that the optimal Bellman operator is a $J$-stage $\nu$-span contraction. The complexity is $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$.

2. Correction of Prior Quantum RL Works:
   The paper critiques previous works (e.g., Ganguly et al., Zhong et al.) that claimed polylogarithmic regret. The authors argue these works incorrectly assumed that quantum amplitude estimation could be performed on a collection of stored states rather than requiring sequential, coherent applications of the oracle and its inverse. The proposed hybrid model corrects this by enforcing a distinct offline phase where such coherent operations can be performed without incurring regret.

3. Regret Bounds under the Hybrid Model:
   The authors derive regret bounds for both classical and quantum settings as a function of the budget parameter $\beta$:

   • Finite-Horizon:
     • Classical: $\tilde{O}(\sqrt{HSAT})$ (matching state-of-the-art) when $\beta \ge 2$.
     • Quantum: $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ for $\beta < 1$, and polylogarithmic in $T$ for $\beta \ge 1$.
   • Infinite-Horizon Discounted:
     • Quantum: Achieves $\tilde{O}(\text{polylog}(T))$ regret when $\beta \ge 1$, breaking the classical $\Omega(\sqrt{T})$ barrier.
   • Infinite-Horizon Undiscounted:
     • Quantum: Achieves $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ regret for $\beta \ge 1$, significantly improving upon the $\tilde{O}(\Lambda S^5 A^4)$ bound of prior quantum works.

Results and Significance

The paper claims that the "bit of freedom" provided by the offline generative phase allows for a substantial improvement in learning efficiency.

• Quantum Advantage: The most significant result is the demonstration that quantum computers can achieve polylogarithmic regret in the time horizon $T$ (specifically when $\beta \in [1, 2)$), whereas classical algorithms are fundamentally limited to $\Omega(\sqrt{T})$ regret in these settings. This represents an exponential improvement in the dependence on $T$.
• Parameter Dependence: The quantum algorithms improve the dependence on the state space size $S$, action space size $A$, and horizon $H$ (or effective horizon $\Gamma$) compared to both classical algorithms and previous quantum attempts.
• Model Validity: The paper establishes that the hybrid online-offline model is a necessary and meaningful framework for quantum RL. It resolves the ambiguity of defining regret in quantum interactions and corrects the theoretical flaws in previous literature that assumed regret-free quantum exploration without such a separation.

The authors conclude that while the exponential quantum advantage in $T$ vanishes when the budget $\beta$ is very large ($\beta \ge 2$, where classical algorithms also achieve polylogarithmic regret), there exists a critical range ($\beta \in [1, 2)$) where quantum computers provide a substantial advantage. The paper identifies this range as the primary area where quantum speedups in RL are most impactful under the proposed model.