acceptodds
Under review as a conference paper at ICLR 2027

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

Abstract

Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy—a function that tells the agent which action to take. In this work, we study two types of MDPs—finite-horizon and infinite-horizon discounted—and propose new quantum algorithms for approximating optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our query complexities improve on previous works, thus approaching already established quantum lower bounds.

Primary area:
generative models
Keywords:
quantum machine learning, markov decision process, reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cfJqOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The main claim of this paper is to provide a quantum algorithm that can improves both the time-dependent finite-horizon MDP and time-independent infinite-horizon MDP.

The techniques that the authors used are standard quantum tools like standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, as well as some enhanced value-iteration classical algorithms.

Critical strengths

The main strength of this paper is to provide a unified quantum algorithm to solve time-dependent finite horizon and time-independent infinite horizon MDA problems.

The paper requires expert in the area and the experts need to be well-versed in classical as well as quantum algorithms.

Critical weaknesses

The main drawback of this paper is that all the techniques used are indeed very standards quantum tools, and it is based one a classical classical (improved) MDP algorithms.

I tried to go through the main results, but the proofs are not easy to read, and there were a lot of "details' that the authors just skimmed over. So unless the authors provide more detail analysis and presentation, I am not sure whether the results are like what they claimed.

This paper improves the query complexity of obtaining epsilon-optimal policy (and potentially V-value functions) for time-dependent finite-horizon MDP. However, this improvement only exists for some time-independent infinite-horizon MDP (Notice that they pick up another factor of \Gamma). Besides, this improvement may be be extensible to obtaining Q-value functions. That is to say, the best quantum query complexity of obtaining Q-value functions remain as claimed by previous results. Therefore, the results of this paper is not as strong as it tried to claim.

Questions for authors

The proposed algorithm is really a "quantized" version of the standard value iteration. So there has to be a quantization errors and if one chooses a really small quantization error, what is the impact to the query complexity? This is not clear to me and this is an important issue.

This paper improves the query complexity of obtaining epsilon-optimal policy (and potentially V-value functions) for time-dependent finite-horizon MDP. However, this improvement only exists for some time-independent infinite-horizon MDP (Notice that they pick up another factor of \Gamma). Besides, this improvement may be be extensible to obtaining Q-value functions.

Can the authors show it detail how it can be extensible to other Q-value functions?

Also, please theoretically show the impact of Γ\Gamma.

Reviewer_hheROpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2(+1)
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper studies quantum algorithms for computing approximately optimal policies in Markov Decision Processes (MDPs) under a quantum generative model, considering both finite-horizon and infinite-horizon discounted settings. The authors propose quantum value iteration algorithms that combine variance-aware quantum mean estimation, Dürr–Høyer quantum maximum finding, and classical techniques based on monotonicity and total-variance analysis. By leveraging these techniques, the proposed algorithms aim to achieve simultaneous improvements in the dependence on the planning horizon and the number of actions. Specifically, the paper claims query complexities of O~(H2.5SA/ε)\widetilde{O}(H^{2.5}S\sqrt{A}/\varepsilon) for finite-horizon MDPs and O~(Γ2.5SA/ε)\widetilde{O}(\Gamma^{2.5}S\sqrt{A}/\varepsilon) for infinite-horizon discounted MDPs, improving upon previous quantum upper bounds in the corresponding parameter regimes.

Critical strengths
  • The main strength of this paper is its improved quantum query complexity for both finite-horizon and infinite-horizon discounted MDPs.
  • The key technical contribution is combining variance-sensitive quantum mean estimation with quantum maximum finding while preserving a total-variance-based error analysis. This gives them a better complexity guarantee than the previous one.
Critical weaknesses

I have a concern about the use of Dürr–Høyer (DH96) maximum finding in the proof of Theorem 1 (pages 8–9), and similarly in Theorem 2, which is critical as it may affect the central correctness and complexity claim of the algorithm.

The quantum mean estimation algorithm only guarantees that the estimate is accurate with high probability. Even when it succeeds, the output may be a superposition of different valid estimates, rather than a single fixed value for each action. However, the authors seem to treat it as a deterministic value oracle when applying DH96. In particular, it is unclear whether the operator-norm bound on page 9 follows from the stated mean estimation guarantee. Could the authors clarify why standard DH96 maximum finding can be applied here? Alternatively, would a generalized minimum/maximum finding algorithm, such as that of van Apeldoorn and Gilyén, be needed to handle these uncertain estimates? If so, can the claimed query complexities still be maintained?

Update: the authors have solved my concern about the maximum finding with detailed arguments, and the improvements on time dependent settings looks interesting. It might be inspiring for us to know about same complexity for time dependent and independent settings. Therefore, I decide to update my score.

Questions for authors

See the weakness part.

Reviewer_istoOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies planning in tabular finite-horizon and infinite-horizon discounted MDPs with coherent quantum access to a generative model and its inverse. It proposes value-iteration algorithms combining variance-sensitive quantum mean estimation, quantum maximum finding over actions, and total-variance error bounds. For discounted MDPs it additionally maintains a monotonicity condition to obtain a near-optimal stationary policy rather than only an accurate value estimate. The claimed query bounds are O~(H5/2SA/ϵ)\widetilde O(H^{5/2}S\sqrt A/\epsilon) for time-dependent finite-horizon MDPs and O~(Γ5/2SA/ϵ)\widetilde O(\Gamma^{5/2}S\sqrt A/\epsilon) for discounted MDPs, where Γ=(1−γ)−1\Gamma=(1-\gamma)^{-1}. These improve the corresponding maximum-finding branches of previous quantum bounds, although a factor of the horizon remains relative to the stated lower bounds. In the discounted setting, the earlier linear-in-AA branch may still be preferable in some parameter regimes.

Critical strengths
  1. Useful joint improvement in two parameters. The proposed avoidance of variance-reduction preprocessing permits the intended combination of variance-sensitive estimation with action maximum finding. If the coherent composition is established, the resulting H5/2SA/ϵH^{5/2}S\sqrt A/\epsilon and Γ5/2SA/ϵ\Gamma^{5/2}S\sqrt A/\epsilon bounds improve the corresponding branches of previous bounds in a meaningful, clearly stated way (Section 4 and Theorems 1–2).

  2. Attention to the policy guarantee. Appendix A explicitly uses monotonicity and retains the previous action whenever a candidate update is smaller. This addresses the distinction between obtaining a good value estimate and obtaining a good stationary policy. The total-variance analyses also explain the horizon dependence instead of relying on a worst-case sum of local errors.

Critical weaknesses
  1. Fact 2 does not directly give the fixed-output oracle used by Fact 1. On p. 8, Equation (1) represents the good branch for each action as one fixed pair of computational-basis estimates ∣μ~(s,a)⟩∣σ~(s,a)⟩|\widetilde\mu(s,a)\rangle|\widetilde\sigma(s,a)\rangle, with probability 1−δa1-\delta_a. The stated mean-estimation guarantee, as in Kothari and O'Donnell, Theorem 1.1, only bounds the probability of producing a numerically accurate estimate. After deferring measurements, the good branch can contain a superposition of several different accurate estimates; there need not be one estimate with probability 1−δa1-\delta_a. The hybrid argument on p. 9 removes the bad-output amplitude but does not resolve this distinction: its ideal oracle is assumed to be a deterministic function-value oracle, as required by Fact 1. This affects the step claiming an exact maximum of the biased estimates, and hence the proof of the joint A\sqrt A advantage in both algorithms. A repair must handle multiple good numerical outputs and retain the action-dependent one-sided error needed for the total-variance analysis, rather than replacing it with a uniform worst-case tolerance. The distinction between exact-value and approximate numerical oracles is also made explicit in Gao, Ji, and Wang, Sections 1.1 and 3; that reference alone does not verify the variance-sensitive repair needed here.

  2. The source-code motivation overstates the assumed oracle access. Section 3, p. 4, lines 171–175 says that reversibly compiling an ordinary randomized simulator straightforwardly produces the displayed clean state ∑s′p(s′∣s,a)∣s′⟩\sum_{s'}\sqrt{p(s'\mid s,a)}|s'\rangle. In general it produces a coherent sampler retaining the random seed, schematically ∑zqz∣z⟩∣f(s,a,z)⟩\sum_z\sqrt{q_z}|z\rangle|f(s,a,z)\rangle. Erasing that seed while preserving the output amplitudes is an additional state-generation problem, not an automatic consequence of replacing classical gates by reversible gates. The explicitly assumed oracle is a legitimate model, so this observation alone does not refute the theorem. The paper should correct the claimed equivalence or state and analyze a garbage-preserving sampler model under which the algorithm also works.

Questions for authors
  1. Can you state and prove the precise coherent estimation/maximum-finding lemma used in Algorithm 1, steps 7–8, and Algorithm 2, steps 7–8? In particular, how are multiple accurate numerical outputs in the coherent good branch handled, and how does the resulting selected action/value retain the one-sided, action-dependent error bound used on p. 8 and in Equation (5)? If a fixed estimate per action is intended instead, what establishes that stronger output guarantee at the stated query cost?

  2. Can the algorithms be formulated with a coherent sampler that retains its random seed/garbage, together with its inverse? If so, please state that access model and explain why every estimation and maximum-finding step still applies. Otherwise, please qualify the source-code-to-clean-oracle claim on p. 4.

Comments on the paper

1 comment

We are a bit disappointed with the lack of engagement from the reviewers' side. Only one reviewer acknowledged our comments (by raising their score). It calls into question the need for a rebuttal period in the first place. Regardless, we summarise the two main complains from the reviewers and how we addressed them.

  1. Two reviewers identified a potential bug in our proof. More precisely, a step in the algorithm can output (a superposition of) several good approximations instead of just one, which can be a problem for the subsequent step. We fixed this issue by employing a more elaborate subroutine than the old one. None of our results have changed due to this change.

  2. One of our models focused on the time-independent setting and the third reviewer questioned about the time-dependent setting. Even though we have never seen a work, classical or quantum, address this setting, since it is a bit unusual for a few different reasons, we have properly extended the model to the time-dependent case. Contrary to what the reviewer thought, the complexities haven't gotten worse from this generalisation but have stayed exactly the same.

We hope this summary helps other reviewers and area chairs.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.