Quantum Algorithms for Finite-horizon Markov Decision Processes

We sincerely thank Reviewer FX1s for the thoughtful and constructive feedback. Below, we address the reviewer’s concerns regarding references, the typo in Theorem 4.2, the definition of "minimax optimal," the clarity of the algorithm name "QVI," the cost of constructing quantum oracles, and the potential applications and extensions of our techniques.

The statement in Section 1 that "the quantum algorithm and analysis there cannot be applied to general finite-horizon MDPs," refers to (Naguleswaran et al., 2006), which only focuses on a specific class of MDPs—deterministic shortest path problems—and does not generalize to broader finite-horizon MDPs. We agree that (Wiedemann et al., 2022) addresses general finite-horizon MDPs, and we have properly cited this work in Section 1. However, their algorithm is inefficient, with a quantum sample complexity exponential in the state space for obtaining a near-optimal policy. Besides, we appreciate the reviewer for recommending [1] which provides a super-quadratic improvement in policy gradient estimation. However, [1] did not directly show how such a method can be applied to solve MDP problems. It would be an interesting direction to explore whether this powerful technique can be used to improve the results in (Cornelissen, 2018) for solving MDP problems.

We apologize for the typo in Theorem 4.2 and we will correct this in the revised manuscript. Additionally, we acknowledge the lack of clarity in defining "minimax optimal." To clarify, we plan to replace "minimax optimal" with " (asymptotically) optimal" and formally define that an algorithm is (asymptotically) optimal if its query/sample complexity matches the corresponding lower bound up to constant factors [3]. Accordingly, we propose to revise the claim that "QVI-3 and QVI-4 are nearly minimax optimal" to "QVI-3 and QVI-4 are nearly (asymptotically) optimal (up to log terms) in computing near-optimal V/Q values and policies, provided the time horizon $H$ is a constant." For example, QVI-3's quantum sample complexity in computing near-optimal V values and policies is $\tilde{O}\left( \frac{S \sqrt{ A } H^{3}}{\epsilon} \right)$ (Theorem 4.4) while the quantum lower bound is $\Omega\left( \frac{S\sqrt{ A }H^{1.5}}{\epsilon \log^{1.5}(\epsilon^{-1})} \right)$ (Theorem 4.7), differing by a factor of $H^{1.5}$ and a log term.

We apologize for the lack of clarity in the algorithm name "QVI." We plan to revise the sentence "..., we propose a quantum value iteration algorithm QVI-1, ..." in the first paragraph of our summarized contributions in Section 1 to explicitly introduce the term "QVI". "QVI" stands for Quantum Value Iteration, where “VI” refers to the classical Value Iteration algorithm and “Q” indicates our quantum adaptation using subroutines like QMS and QME.

We appreciate the concern about the cost of constructing the quantum oracles in Definitions 3.2 and 4.1. For the quantum generative model in Definition 4.1, as noted in our response to Reviewer Xd2s, the classical generative model G and the quantum generative model $\mathcal{G}$ have similar costs at the elementary gate-level if the classical circuit of the classical generative model is accessible. Furthermore, assuming that the classical generative model can be called in constant time and that we have access to quantum random access memory (QRAM) in [2], the time complexities of QVI-3 and QVI-4 are the same as the sample complexities of QVI-3 and QVI-4 up to log terms, so the reported speedups for QVI-3 and QVI-4 remains valid. Similarly, the time complexity of QVI-1 and QVI-2 is not degraded by the construction of quantum oracle $O_{\mathcal{QM}}$ (Definition 3.2) either. Specifically, suppose the classical oracle $O_{\mathcal{M}}$ in Definition 3.1 is a computer program, and we have its source code, we can also efficiently convert the classical circuit of $O_{\mathcal{M}}$ to a quantum circuit to implement the quantum oracle $O_{\mathcal{QM}}$. Unlike the quantum generative model, the output of the quantum oracle $O_{\mathcal{QM}}$ is not a superposition. Therefore, even without access to QRAM, the time complexities of QVI-1 and QVI-2 are the same as the quantum query complexities of QVI-1 and QVI-2 up to log terms as long as the classical oracle $O_{\mathcal{M}}$ can be called in constant time.

We thank the reviewer for encouraging more discussion on the applications and extensions of our techniques. Our quantum algorithms have potential use in robotics (e.g., path planning) and operations research (e.g., inventory management). Our theoretical techniques could be extended to partially observable or multi-agent MDPs.

[1] Clayton, Connor, et al. "Differentiable Quantum Computing for Large-scale Linear Control.".

[2] Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. "Quantum random access memory.".

[3] Cormen, Thomas H., et al. "Introduction to algorithms".

We appreciate the reviewer’s concern regarding the perceived lack of novelty in our quantum algorithms. While our algorithms leverage QMS and QME as in prior work (Wang et al., 2021), their analysis for infinite-horizon MDPs can not be readily applied to time-dependent and finite-horizon MDPs. A key contribution of our work lies in the design and analysis of QVI-4. Note that in our setting, the value operator in Definition 2.1 is time-dependent and lacks contraction property-unlike the infinite-horizon case, which allows iterative policy/value updates via fixed points. This lacks of contraction property in our setting poses significant challenges in designing QVI-4. In SolveMdp1 (Wang et al., 2021), the $\epsilon_{k}$ optimal V/Q-values and policy can be directly used to initialize the next epoch $k+1$. This is not feasible in our case. To address this, we propose another initialization strategy in QVI-4, setting $V_{k+1,h}^{(0)}= V_{k,h}$ for all $h\in[H]$ and initializing $V_{k,H}= V_{k,H}^{(0)}=\mathbf{0}$. We then use induction on $k$ to prove the correctness of QVI-4 (Lemma B.4), showing non-trivial technical contributions in extending quantum algorithms to finite-horizon MDPs.

We appreciate the reviewer’s question about the lower bound for classical methods in the exact dynamics setting. We can derive a classical lower bound of $\Omega(S^2 A)$ in the exact dynamics setting by adapting the method from [2] to finite-horizon MDPs. Consider two hard instances $M_{1}$​ and $M_{2}$ similar to those in [2]. ​In $M_{1}$, we can derive that the optimal value for $s\in \mathcal{S}\_{U}$ is $V^{\*}\_{h}(s)=\frac{H-1-h}{2}$, while in $M_{2}$, the optimal value for $s\in \mathcal{S}\_{U} \setminus \{ \overline{s} \}$ remains $V^{\*}\_{h}(s)=\frac{H-1-h}{2}$ but $V\_{h}^{\*}(\overline{s})=H-1-h$. To achieve $\frac{H-1}{4}$-optimal $V\_{0}$ with high probability, any algorithm must distinguish $M_{1}$ from $M_{2}$, requiring to search for two discrepancies in an array of size $\Omega(S^{2} A)$. Therefore, the classical lower bound for computing an $\epsilon$ optimal $V_{0}$ for the time-independent and finite-horizon MDP is $\Omega(S^{2} A)$ for $\epsilon \in (0,\frac{H-1}{4})$. This implies the classical lower bound for obtaining an $\epsilon$ optimal policy for the time-dependent and finite-horizon MDP in the exact dynamics setting is $\Omega(S^{2} A)$. This classical lower bound can also be derived using the reduction technique in Appendix B.3.

We acknowledge the reviewer’s concern on the clarity of a high-level overview of the proposed algorithms. Sections 3 and 4 already include high-level overviews (also noted by Reviewer FX1s), and we plan to make them more prominent. Besides, QMEBO uses binary oracles to encode the $P_{h|s,a}$ and $\hat{V}\_{h}$ and transfer this information to amplitude via controlled rotation unitary operators, followed by amplitude estimation to compute an estimate of $P_{h|s,a}^{T} \hat{V}\_{h}$.

We thank the reviewer for pointing out the missing reference [1]. While [1] studies quantum speedup for policy gradient methods in finite-horizon MDP and explores connections to infinite-horizon MDP, our work differs in three key differences. First, [1] only provides quantum speedups for estimating the gradients of V values. It does not produce a bound on the overall complexity for their algorithms to converge and obtain a near-optimal policy. In contrast, we directly quantify the complexity for computing a near-optimal policy. Second, regarding the approximation between finite-time and infinite-time, note that [1] uses the approximation to solve infinite-horizon MDP. Perhaps due to this reason, their result (Theorem 3.1 and 4.1) requires the finite-horizon MDP to also have a discount factor away from 1. In contrast, our paper is not interested in infinite-horizon MDP. Instead, we only use it to derive a lower bound. As a result, for our solution to finite-horizon MDP, we do not require a discount factor away from 1. Therefore, our results are new and more broadly applicable than [1].

We agree that a time-dependent MDP can be converted to a time-independent MDP by expanding the state space to $\mathcal{S}' = \mathcal{S} \times [H]$. However, this transformation does not reduce the complexity. Even including [1] , the only known quantum algorithm for general finite-horizon MDP remains that of (Wiedemann et al., 2022), whose sample complexity to obtain an $\epsilon$-optimal policy is $O(A^{3SH/2}H/\epsilon)$ for time-dependent setting and $O(A^{3S/2}H/\epsilon)$ for time-independent setting. Thus, even after reduction, their complexity with the enlarged state space $S'$ remains $O(A^{3SH/2}H/\epsilon)$, which is inferior to our algorithms.

[1] Jerbi, Sofiene, et al. "Quantum policy gradient algorithms.".

[2] Chen, Yichen, and Mengdi Wang. "Lower bound on the computational complexity of discounted markov decision problems.".

We sincerely thank Reviewer Xd2s for the detailed feedback on our submission. Below, we address the reviewer’s concerns regarding the technical contributions and the justification of the comparison between quantum and classical generative models, while proposing feasible revisions to strengthen our submission.

We acknowledge the reviewer’s concern that our quantum algorithms may appear to simply replace classical subroutines with well-known quantum ones, such as quantum maximum searching QMS (Durr & Hoyer, 1999) and quantum mean estimation QME (Montanaro, 2015). However, we would like to highlight the significant technical contributions of our work, which go beyond straightforward substitutions. First, a key technical contribution of our work is the development of the Quantum Mean Estimation with Binary Oracles (QMEBO, Algorithm 3) subroutine in the exact dynamics setting (Section 3.2). QMEBO adapts quantum mean estimation for binary oracles, achieving a speedup in the state space $S$ (from $O(S)$ to $O(\sqrt{ S } /\epsilon)$) for near-optimal policies. This is a non-trivial adaptation that enables the application of quantum techniques to MDPs. Second, while our algorithms do leverage well-known QMS and QME, it is nontrivial to infuse the two existing quantum subroutines into existing reinforcement learning frameworks. For example, as pointed in Section 4.2, when integrating the total variance technique and QME, we can not directly apply QME2 as its classical counterpart, because QME2 requires prior knowledge of $\sigma\_{k,h}^{s,a}$ and an upper bound on $\sigma\_{k,h}^{s,a}$ to estimate the $\mu\_{k,h}^{s,a}$ to an error of $\frac{\epsilon \sigma\_{k,h}^{s,a}}{(2H^{1.5})}$. To address this, we propose to use QME1 to obtain an estimate $(\hat{\sigma}\_{k,h}^{s,a})^{2}$ of $(\sigma\_{k,h}^{s,a})^{2}$ with an error $4b$ and use QME2 to estimate $\mu\_{k,h}^{s,a}$ with an error proportional to $\overline{\sigma}\_{k,h}^{s,a}=\sqrt{ (\hat{\sigma}\_{k,h}^{s,a})^{2}+4b}$. This integration demonstrates the technical depth required to adapt quantum subroutines to our setting, contributing to the field of quantum reinforcement learning.

We thank the reviewer for raising the important question about the fairness of comparing quantum and classical generative models for MDPs. In fact, the comparison is fair because implementing quantum generation model $\mathcal{G}$ (Definition 4.1) has a comparable overhead as the classical generation model $G$ (Eq. 3, Section 4). In the classical generative model setting, it is assumed that we can access to a classical generative model/simulator $G$ that draws samples from the distribution $P_{h|s,a}$. The classical generative model makes particular sense when the environment is a computer program, and thus we can use the same computer program to simulate the drawing of samples. Specifically, if the simulator is a computer program and we have its source code, then for the classical generative model $G$ we can produce a Boolean circuit $\mathcal{C}$ that acts as the simulator, i.e., draws samples from the distribution $P_{h|s,a}$. For the quantum generative model, we use the fundamental result in quantum computation ([1], Nielsen & Chuang, 2010, Section 1.4.1) that any classical circuit $\mathcal{C}$ with $N$ logic gates can be efficiently converted into a quantum circuit $\mathcal{Q}$ with $O(N)$ logic gates, capable of computing on quantum superpositions of inputs. Moreover, the conversion is efficient and can be achieved by simple conversion rules at the logic gate level by using the Toffoli gate. The authors in (Wang et al., 2021, arXiv:2112.08451) confirmed this by explicitly constructing the quantum generative model for infinite-horizon MDPs from a circuit of the corresponding classical generative model in Appendix A. We believe such a construction method can be readily extended to the case of finite-horizon MDPs. Thus, the classical generative model $G$ and the quantum generative model $\mathcal{G}$ have comparable costs at the elementary gate level, making the comparison between the quantum sample complexity with the classical sample complexity fair. Furthermore, the time complexities of QVI-3 and QVI-4 are the same as the quantum sample complexities of QVI-3 and QVI-4 up to log terms under the assumptions that the classical generative model can be called in constant time and that we have access to quantum random access memory (QRAM) proposed in [2]. Roughly speaking, QRAM is a memory that stores the classical values and that allows them all to be read at once in quantum superposition. To address the reviewer's concern, we propose to add a paragraph in Section 4 to explicitly justify the comparison between the quantum and classical generative models.

[1] Bennett, Charles H. "Logical reversibility of computation.".

[2] Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. "Quantum random access memory.".

We sincerely thank Reviewer tc3r for the thorough and constructive feedback on our submission. Below, we address the reviewer’s concerns and provide clarifications to strengthen our submission.

We acknowledge the reviewer’s concern regarding the lack of empirical validation in our current submission. As a primarily theoretical contribution, our work focuses on establishing the correctness and complexity of the proposed quantum value iteration (QVI) algorithms for finite-horizon MDPs in two distinct settings, as evidenced by the formal proofs provided in the appendix. We recognize the importance of empirical evaluation in demonstrating practical impact; however, the current state of quantum hardware poses significant challenges for implementing and testing quantum algorithms at scale. Specifically, the limited qubit counts, high error rates, and restricted access to large-scale quantum computers make it difficult to empirically validate the proposed speedups at this stage. We are committed to pursuing empirical validation in future work. Besides, to address the reviewer’s suggestion for making the quantum speedup more concrete, we propose to include an illustrative example of a toy MDP, such as the Inventory Management Problem, in Section 3 and Section 4 to demonstrate the difference in query complexity between classical value iteration and QVI algorithms.