Quantum Algorithms for Finite-horizon Markov Decision Processes
Authors: Bin Luo
Yuwen Huang
Jonathan Allcock
Xiaojun Lin
Shengyu Zhang
John C.S. Lui
Venue: ICML 2025 poster (2025)
Keywords: Quantum algorithms
Markov decision processes
lower bounds
Primary area: reinforcement_learning
TL;DR: We design quantum algorithms that solve finite-horizon Markov decision process problems more efficiently than classical algorithms and establish quantum lower bounds to rule out the possibility of exponential quantum speedups.

Abstract: In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment's dynamics (i.e., transition probabilities), we prove that our **Quantum Value Iteration (QVI)** algorithm **QVI-1** achieves a quadratic speedup in the size of the action space $(A)$ compared with the classical value iteration algorithm for computing the optimal policy ($\pi^{\ast}$) and the optimal V-value function ($V_{0}^{\ast}$). Furthermore, our algorithm **QVI-2** provides an additional speedup in the size of the state space $(S)$ when obtaining near-optimal policies and V-value functions. Both **QVI-1** and **QVI-2** achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on $S$ and $A$. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms **QVI-3** and **QVI-4** achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of $A$, estimation error $(\epsilon)$, and time horizon $(H)$. More importantly, we prove quantum lower bounds to show that **QVI-3** and **QVI-4** are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.

Quantum Algorithms for Finite-horizon Markov Decision Processes
Bin Luo Yuwen Huang'
Jonathan Allcock 2 Xiaojun Lin'
Shengyu Zhang? John C.S. Lui
Abstract
MDPs have been applied in fields such as networks, robotics, and operations research (Alsheikh et al., 2015; Matignon et al., 2012). Despite their wide applicability, MDPs often face significant computational challenges in practice. A key issue arises when the number of possible states or actions in the system becomes very large. In particular, this "curse of dimensionality" makes solving MDPs computationally infeasible in many practical scenarios (Powell, 2007).
In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct set- tings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment's dynamics (i.e., transition probabilities), we prove that our Quantum Value Iteration (QVI) algo- rithm QVI-1 achieves a quadratic speedup in the size of the action space (A) compared with the classical value iteration algorithm for computing the optimal policy (x*) and the optimal V-value function (. Furthermore, our algorithm QVI- 2 provides an additional speedup in the size of the state space (5) when obtaining pear-optimal policies and V-value functions. Both QVI-1 and QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on and A. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, prove that our algorithms QVI- 3 and QVI-4 achieve improvements in sample complexity over the state-of-the-ar (SOTA) clas- sical algorithm in terms of A, estimation error (c), and time horizon (H). More importantly, we prove quantum lower bounds to show that QVI-3 and QVI4 are asymptotically optimal, up to loga- rithmic factors, assuming constant time horizon.
Quantum computing is new computing paradigm that har- nesses the laws of quantum mechanics. For certain classes of problems, such as unstructured search (Grover, 1996), prime number factoring (Shor, 1994), optimization (Sidford & Zhang, 2023; Jordan, 2005; Liu et al., 2024) and online learning (He et al., 2024; 2022; Wan al., 2023), quantum computing demonstrates significant speedups over classi- cal computing. Recent advancements in quantum hardware (Arute et al., 2019; AI et al., 2024) indicate that practical quantum computers can be a reality in the near future.
Given the importance of MDPs and the advancement in quantum computing, researchers have explored various quantum algorithms to reduce the time complexity solv- ing MDPs. In the stochastic control domain, (Naguleswaran & White, 2005) suggested two quantum techniques that can potentially be used to accelerate classical algorithms for finite-horizon MDPs (Puterman, 2014). However, this work only focused on problem formulation and did not pro- vide a concrete quantum algorithm for finite- horizon MDPs with performance guarantee. (Naguleswaran et al., 2006) applied quantum walk (Magniez et al., 2007) efficiently solve specific class of MDPs, namely deterministic short- est path problems. However, the quantum algorithm and analysis there cannot be applied to general Umite-horizon MDPs. For RI, researchers proposed to replace subrou- tines of existing RL frameworks by quantum algorithms. For example, (Wiedemann et al., 2022) proposed use a quantum Monte Carlo (MC) (Montanaro, 2015) to replace the classical MC method policy evaluation. However, their algorithm is inefficient as its quantum sample complex- ity is exponential with respect to S in both time-dependent and time-independent settings for obtaining near-optimal policies. Improved sample-complextty results that do not increase exponentially in S have been obtained for infinite- horizon MDPs. For example, (Cherrat et al., 2023) utilized quantum linear system solver (Chakraborty et al., 2019) to
1. Introduction
Markov Decision Processes (MDPs) provide a mathemat- ical framework for modeling decision-makee problems in uncertain environments. They are an important frame- work to model discrete-the time stochastic control and reinforce- ment learning (RL) (Puterman, 2014; Agarwal et al., 2019).
'The Chinese University of Hong Kong, Hong Kong, China TTeneett Quantum Laboratory, Hong Kong, China. Correspon- dence to: Yuwen Huang Syywen.huange wim..cukk.dd..hke
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
approximate Q-values during the policy evaluation. (Wang et al., 2021) proposed nearly minimax optimal quantum al- gorithms for infinite-horizon MDPs by leveraging quantum mean estimation (Montanaro, 2015) and quantum maxi- mum searching (Durr& & Hoyer, 1999). Besides, (Cornelis- sen, 2018) applied quantum gradient estimation (Gilyén et al., 2019) in policy improvement. However, these algo- rithms are only tailored mainite-horizon problems with time-invariant value function, thus preventing their use in finite-horizon and time-dependent scenarios where the value functions depend on time.
and any vector / E Y.,, we denote the element of / at entry by (()). For any / E TR the operations vf. Is]. and f are applied component-wise. Given two vectors f1. E R,,, we define max f2} as their element-wise maximum, and write fi S /2 to indicate component-wis inequality. The bold symbols 0 and 1 represent vectors of all zeros and ones, respectively, and a scalar z in an equation with vectors should be interpreted as x 1. We usually identify function f X + Y as a vector f E Yx.
MDP Preliminaries: We study time-dependent and finite- horizon MDPs in two settings: (a) the exact dynamics set- ting (Section 3) and (b) the generative model setting (Sec- tion 4). In both settings, the MDP has a finite and dis- crete state space and action space A. In each time step h [M]] an agent need to decide which action a E A to take for each state a at the state in the time step h E [H], the agent ob- tains a reward ra(s,a) E [0. 1] and transitions to the next state s' E S with probability Ps (s a). We de- fine a finite-horizon and time-dependent MDP as a 5-tuple M = (S,A, { H-1 {ra) - H). We define = [S] and A = -Al, which are the cardinalities of S and A re- spectively. A policy ι is a mapping from S x [H] to A. where (ss, h) specifies the action that the agent should take in the state at the time step h. The policy space is de- fined as II == AS([H), In MDPs, the objective of the agent is to find a policy π that maximizes the expected cumula- tive reward over // time horizon. This can be written as maximizing the V-value function, Vi, : S - R, at each time step h. Specifically, the V-value function at time h for initial state under policy π is defined as VT == E [Et=] re (t)(TT, 8h, = = where ot = π ( 1). Simi- larly, the Q-value function Q 8 A - R is defined as (7, a) = E [EE re(se, at) |T = 8, an = =a]
Thus, one open question is, can one design quantum al- gorithms that are more efficient than classical algorithms in obtaining the optimal or e-optimal policy, V-value and Q-value functions f for "finite-horizon" " and "time rimeedependent" MDPs? We address this open question in both the exact dynamics setting and the generative model setting. Our contributions are as follows:
S. After taking the action
In the exact dynamics setting (Section 3), we propose a Quantum Value Iteration (QVI) algorithm QVI-1, that computes the optimal policy and V-value function with a quadratic speedup in A compared with the clas- sical value iteration algorithm. Additionally, QVI-2 achieves a further speedup in S for obtaining near- optimal policies and V-value functions, enabled by our novel quantum subroutine, quantum mean estimation with binary oracles (QMEBO), for mean estimation of arbitrary bounded functions. Besides, we also derive new classical lower bounds for computing near-optimal policies and V-value functions. summary of these results is provided in Table 1.
In the generative model setting (Section 4), we pro- pose two quantum algorithms, QVI-3 and QVI-4, to efficiently compute e-optimal policies and value func- tions. Compared with SOTA classical algorithms for time-dependent and finite-horizon MDPs, both QVI-3 and QVI-4 achieves speedups in H, and c, with QVI-3 additionally achieving a quadratic speedups in A.
For a policy n, we define P E RSAXSA as the matrix with entries PA ((s) a), (s', a')) = Pa a) if = (Ts') and 0 otherwise. For any Q RSXA we define PAO E RSA as (PT (), = =Eres Pa (s',(((((s') slight abuse of notation, we define Pr E SASS as the ma- trix satisfying PA ((s,a), a)) = Pa(s"Is, a) for any h E [H]. For any fixed s E S, a E A and h E [H]. we define Pals.a E R$ as the vector satisfying (s)) = Ps a). There- fore, we can express B[f(s')|6 ~ Paleaa = PT Phis.ad for any f E R.S.
With a
Assuming access to a quantum generative oracle for dieeddepnndent and finite-horizon MDPs, we establish quantum lower bounds for obtaining near-optimal poli- cies, V-value functions, and Q-value functions. Our results demonstrate that QVI-3 and QVI-4 are asymp- totically optimal, up to log factors, provided that H is a constant. Further, our results also lead to a new lower bound for obtaining Q-values in the classical setting. summary of the upper and lower bounds in the generative model setting is provided in Table 2.
For any vector u E RS, we define (v) E RSSA as a vec- tor satisfying (o)) a) = Varlo(>")|s' ~ ( a)] for any h E [H] In the vector notation, it can be written as ( = p2 x² - (Pao)2. We also define 0s (v) = (v)
We define V(Q) E R as [V(Q])+ max.c and T()) E A as [T(()) = arg (((sc) for any vector Q E RSSA
2. Preliminaries
Define notations: For an arbitrary positive integer n, we define [n] as the set (0, (0,....n n - 1}. For any finite set X
2

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Classical query complexity
Quantum query complexity
Goal:
Upper bound
Lower bound
Upper bound
Optimal n², Vo
SAA
S2 A [Theorem 3.2]
S VAH [Theorem 3.6]
e-accurate estimate of n² and (Vr
SHAH
S A [Theorem 3.2]
SAA' [Theorem 3.91
1-1
Th=0
Table 1. Classsical and quantum query complexities for solving time-dependent and finite-horizon MDPs in the exact dynamics setting. All quantum upper hounds are Ö()), assuming constant failure probability 6. The range of error term is (0, H]. The classical upper bounds are (-)). derived from the value iteration algorithm in (Puterman, 2014). The classical lower bounds are S2(-). which holds for (H))
Goal: obtain an e-accurate estimate of
Classical sample complexity
Quantum sample complexity
Upper bound
Lower bound
Upper bound
Lower bound
{2% H-1 hED
SAff
SAH 2
Theorem 4.7]
SAH23
Theorem 4.6]
SAH
Theorem 4.7]
SAH
Theorem 4.6]
n", (V
SAH'
SAH
[Theorem 4.7]
SVAH25
[Theorem 4.7]
SVAR
[Theorem 4.4]
Table 2. Classical and quantum sample complexities for solving time- time-dependent and tnite-horizon MDPs in the generative model setting. All bounds assume a constant maximum failure probability 8. All upper bounds are Ö(). which requires e E O(1/ /H) for [Theorem 4.6] and e (0, H] for [Theorem 4.4). All lower bounds are (2(.). which holds for E (0, 1/2). The classical upper bounds for all goals were shown in (Li et al., 2020). The classical lower bound for x and (V/ J===
H-1 was shown in (Sidford et al., 2018).
Below, provide formal definitions for some important concepts in the finite-horizon MDP M..
as (e). The symbol (:), where i [m]. denotes the i + 1-th standard basis vector, with J0) typically reserved for the first standard basis vector. In this paper, real numbers are encoded in the computational basis using fixed-point binary representation with precision ~-P Specifically, a real number k is encoded as [Bi[k]) |ka... ......k ki)) E C². where kn .a....,, kg ......g.g-1 ka-p-kg-p-t ... kg is the binary string of k. We assume that and p are sufficiently large so that there is no overflow in storing real numbers.
Definition 2.1 (Value operator associated with a policy). For any policy π E II, let T (.) be the value operator associated with π such that, for all u RS, h [H] and E S, [T (u)),
r(s, (s, + PT M),,m(a,A)" U. We let (V Jh denote the V-value functions of policy n, which H-1
satisfies T," (V Vi for all h E [H].
Definition 2.2 (Optimal value and policy). Define the opti-
We now define a quantum oracle for arbitrary functions and vectors, which is often referred to as binary oracle.
mal value of initial state s E S at each time step h [H] of the finite-horizon MDP M (s) == max (s). A policy is said to be an optimal policy x² if VO = Vo-
Definition 2.4 (Quantum oracle for functions and vectors).
Similarly, we can also define the optimal value of an ini-
Let be finite set of size N and f RR. A quantum oracle encoding J is a unitary operator By CN @ C²
tial pair of (s, a) E S x A at each time step h E [H] as Q%,(s, a) = max QT, (s)
ON @ C such that B, (i) [0) + 1t) [Bilf(t)) for all E [N]. where Bi(f(i) is the binary representation of f() with precision P-P
Definition 2.3 (c-optimal value function and policy). We 1111
say that V-value functions [V are e-optimal if [IV% 10-V,,l Vvllac < c for all E [H] and a policy π E II e-optimal if V - V Il S e for all h E [M), which implies the V-value functions of are e-optimal. Similarly, c-optimal if
3. Exact Dynamics Setting
In this setting, is assumed that the environment's dynamics are fully known, i.e., the transition probability matrix P,, each time step h is explicitly provided for the entire state- action space. To formalize this assumption, we introduce the classical oracle for 3.1. Given this classical oracle, the classical value iteration algorithm (Algorithm 6) can obtain an optimal policy x²
say that Q-value functions {Qn) 1127 Qu I c for all h [H).
Before introducing our quantum algorithms, a brief overview of Dirac notation (Nielsen & Chuang, 2010) is given to ensure clarity. In Dirac notation, vectors e in a complex vector space C are represented
Quantum Preliminaries:
MDPs O.M in Definition
3

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
and optimal value (s) for any initial state S with O AH) queries the oracle OM (Bellman, 1958).
Algorithm Quantum Value Iteration QVI-I(M,,
1: Require: MDP M,, quantum oracle OOM. maximum
Definition 3.1 (Classical oracle of an MDP). We define classical oracle OM S x A X [H] x S - [0, 1] x [0.1] for time-deepeee demeedennddent and finite-horizon MDP .M satisfying OM: (8, a, h 8') + (n (s, a), (s))-
failure probability 5 E (0, 1)-
2: Initialize: Ç - (SHH), -.
3: for h - 0 do
4: create quantum oracle Byn for vector Vh+ RS
5: Vs E S: create a quantum oracle B encoding
To understand the limits of classical algorithms under this setting, we establish a lower bound on query complexity for computing near-optimal policies and V-value functions. This result adapts the techniques developed for infinite- horizon MDPs in (Chen& & Wang, 2017) the finite-horizon case. The rigorous proof of Theorem 3.2 is presented in Appendix A.2.
vector Qna E AAA with ORM and Bynt. satisfying Qma(a) + rn(s, a) + Pils, Ph+z 6: V f(s, h) + QMS E A}
7: E S: Vi((s) + Qn,s
8: end for
9: Return: म, Vo
Theorem 3.2 (Classical lower bounds). Let S and A be finite sets of states and actions. Let H 2 2 be positive in- teger and e E (0, = be an error parameter. We consider the following time-dependent and finite-horizon MDP M = (S,A, {Pm) HH- {raln=o 1 H), where Th E [0, 1]$xA for all h E {H. Given access to the classical oracle Om, any algorithm K, which lakes M as an input and outputs e- IT" with probability at least 0.9, must require at least S(S A) queries to OM the worst case of input M.
can be called constant time, the quantum oracle OaM can be called in constant time as well. Under this assump- tion, query complexity directly reflects the time complexity for both the classical and quantum algorithms.
With the quantum oracle OoM, our objective is to design quantum algorithms that can compute " and V2 (s) for all s E S with probability at least - 6, while minimizing the total number of queries to 0gm-
approximations of {VR)H=) Jb=
H-1
We first introduce an existing quantum subroutine, quantum maximum searching algorithm (Durr & Hoyer, 1999), which can efficiently find the maximum of a list of unsorted N E z numbers using only O(vN) queries to that list. In contrast, the best-possible classical algorithm must examine all N elements in the worst case to find the maximum.
3.1. Speedup on A
Having established the classical baseline, we now turn to in- vestigating whether quantum algorithms can offer improve- ments, particularly in the dependence on the action space size A. To have a fair comparison on the time complexity between a classical algorithm and a quantum algorithm, we first define the quantum analog of the classical oracle OM-
Theorem 3.4 (Quantum maximum searching (Durr & Hoyer, 1999)). Let B, be a quantum oracle encoding a vector J E RN,, N N E Zt There exists a quantum maxi- mum searching algorithm, QMS, which, for any 6 > O, can identify an index such that f(i is the maximum value in f. with a success probability of al least 1 8. The algorithm requires at most ē. 1og(1/8) queries to Bj, where ē ē>> O is constant.
Definition 3.3 (Quantum oracle of an MDP). A quantum oracle of an MDP M is a unitary operator Oom CS &
C#
C @ C & C
C
2
& 2 such that
Oem: [s) la) (N) (s') 10) 10)
+ (s) la) ()) 18') Biira(s a))) |Bi (P)))
for h')) E SxAx [H]x where Bi(ra (s, a)) and Bi(Pr)s,a('') denote the binary representation of Th (s, a) and (s)) with precision P
We use QMS, (ff()) : [N]] to denote the process of finding the index of the maximum value of vector f us- ing QMS, with success probability at least 1 - 8. Note that the classical value iteration algorithm needs to take the maximum over the whole action space in the Bellman recur- sion to obtain the estimates of optimal V-value function Vi* and optimal action π (s, h)) for state s at time stage h. We incorporate QMS in this step to reduce the query complex- ity from ((A) to (VA)). Now, we propose our quantum value iteration algorithm QVI-1 in Algorithm 1. In order to use QMS correctly, one needs to suitably encode the vector V/- and Qr.e with the binary oracles. In summary, QVI-1 returns an optimal policy and optimal values (Theorem 3.5) but only requires VAH) queries to the quantum ora- cle OoM (Theorem 3.6). The proof of Theorems 3.5 and
We define the number of queries made to the quantum oracle OeM or classical oracle OM as the quantum or classical query complexity, respectively. Comparing quantum and classical time complexities can be achieved by examining their respective query complexities, because implementing OeM has comparable overhead as O... Specifically, given Boolean circuit of OM with N logic gates, it can be con- verted into quantum circuit of ORM with O(N) quantum gates. This conversion can be efficiently achieved by simple conversion rules at the logic gate level (Nielsen & Chuang, 2010). Therefore. ORM and OM have comparable costs at the elementary gate level. Then, if the classical oracle O.M
4

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
3.6 can be found in Appendix A.3, where we also analyze the cost of the qubit resources of QVI-1.
Algorithm 2 Quantum Value Iteration QVI-2(M,,,,))
1: Require: MDP M. quantum oracle QOM. maximum error e E (0, H), failure probability E (0, 1).
Theorem 3.5 (Correctness of QVI-1). The outputs ät and Vo satisfy that î = 'T' and Vo- Ve with success probability at least - 5.
2: Initialize: Ç < 8/ (42SA' 1.S H log(1/6)), VH f 0.
for h H 1, 1....,........... 0 do
4: create quantum oracle By encoding VA+1
Theorem 3.6 (Complexity of QVI-1), The quantum query
complexity of QVI-1 in terms of the quantum oracle 0eM is (S33/AR log(SH
[0, 1 defined by V + /n+1/H
5:
Vs S: create quantum oracle Ban.. encoding
2h.s E R defined by
3.2. Speedup on S
sn,a(a) H OMEBO, Va-1. PaM. B 2n
Since QVI-1 achieves speedup in the action space size A, it is advantageous for problems with large action space, such as natural language processing. where each text in a large dietionary corresponds to a distinct action (Feng et al., 2024). However, in problems modeled by numerous variables, such as Chess or Go, where each position in a vast board is represented as state, the state space can be much larger than the action space and time horizon (Bellman, 1962). In such scenarios, QVI-1 may not be suitable due to its complexity of O(S²). This complexity arises for two reasons: (1) one needs to update O(S) Q-value functions at each time step: (2) computing the "precise mean" of the V-value function from the last time step needs ((S) queries to the oracle OaM when updating each Q-value function. Note that for obtaining an "c-estimation of the mean" of n Boolean variables. quantum algorithms only need O (min(( n²)) queries to a binary oracle (Nayak & Wu, 1999; Beals et al., 2001). This suggests that quantum speedup in S may be achievable if one is satisfied with a near-optimal policy. Therefore, next we investigate whether there exists a quantum algorithm that can obtain c-optimal policies and V-value functions for an MDP M but only requires OSSSooly (SSypoly(AAALL ()) queries to OQM, where 0 <<c c 2.
6: Vs E S: create quantum oracle Ba encoding
Qne E R with ORM and Ben.. satisfying
Qno(a) + max(ra(s, a) (2),
( 7: Vs S: ftss, h) + QMS, (a) : A}
8: Vs S: Vn(s) + (f (f(s,)))
9: end for
10: Return: म., H-1
all Ω. then the algorithm QMEBO requires O(12N c + log(L/))) queries to Bp and By to output an estimate js of p == [[](()] Jr p) = y such that Pr( ul < <) 1 - 0 for any 8 > 0.
f(x)
We denote QMEBO, (p" B. cy. as an estimate of pf f. to an error less than e with probability at least 1 - 8 obtained by QMEBO. The key step of QMEBO lies in line 4, where a binary oracle B, is transformed into unitary oracle U.- Unlike Bp. U, encodes the information of the probability distribution p in amplitude rather than in quan- tum state. Using Üp, we prepare the state (0) defined as
Σ VP
P N
10)
11).
(2)
N
The transformation and the required query complexity are presented in Theorem A.3. After encoding the function f in the amplitudes (lines 5-6), the amplitude estimation (Theo- rem A.5) is applied to compute an estimate 14, of p" J/N with an error of c/N in the loop k. Finally, guaranteed by the Powering lemma (Lemma A.4), the output ja is an e-estimate of p² f with probability at least 8. The com- plete version and full analysis of QMEBO is presented in Appendix A.4.
To achieve this optimization goal, we propose QVI-2 in Algorithm 2. where the quantum subroutine QMEBO, as used in the fifth step, is defined in Algorithm 3. The main difference between QVI-1 and QVI-2 is that we compute an estimate of the expectation of hj Vn+1 rather than its precise value in each time step / in QV1-2. Since the oracle OeM that encodes the probability distribution Pais,a is a binary oracle, we cannot directly apply the existing quan- tum mean estimation algorithms (Montanaro, 2015), which require an oracle that encodes the probability distribution in the amplitude (See Theorem 4.2). Hence, we design a new quantum subroutine in Algorithm 3, denoted as quantum mean estimation with binary oracles (QMEBO).
With QMEBO, it only requires O(VS/e) queries to the oracle OoM to obtain an e-estimate of a/s,a V for any V [0, sls. Compared with computing the precise value of pT hls,a V with O(S) queries to OoM, QMEBO reduces the query complexity from O(S) to O(VS). Finally, QVI-2 only requires ( poly(VA, 1/)))) queries to 0gM (Theorem 3.9). By suitably controlling the error induced by QMEBO, one can ensure that QVI-2 can obtain c-optimal policies and V-value functions (Theorem 3.8). Note that we subtract the H times error induced by QMEBO in line
Theorem 3.7 (Quantum mean estimation with binary ora- cles). Let Ω be a finite set with cardinulity N, p (rx) a discrete probability distribution over Ω and f f + IR a function. Suppose we have access to a binary oracle B, encoding the probability distribution p and a binary ora- cle By encoding the function f. If the function f satisfies
5

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Algorithm 3 Quantum Mean Estimation with Binary Ora- f. ff"
out that the quantum state output by 9 is similar a sample drawn from the probability distribution Pala,e in Eq. (4). Definition 4.1 (Quantum generative model of an MDP). The quantum generative model of a time-dependent and finite-horizon MDP M is a unitary matrix G C @ CA @ C"
cles spp
e,))
1: Require: Bp encoding a probability distribution p p= (pi)ken on a finite set with cardinality N. By encod- ing functionn f = (Je) where fi [0, 1J. maximum error e, maximum failure probability 8 E (0, 1).
C
C
CS
C4 @ C"
C CJ satisfying
2: Initialize: K- Olog 1/6), T = 0 O + 2
G (s) aa)
(h) 10) 10}
3: for k E [K] do
(5)
4: Prepare state ) Üp 10) (0) using Bp
[s)|a) 1b)
Σ
VVPaaaaas 15') liv)
5: Attach [0) s(++1) qubits on ( and apply By
where J 2 0 is an arbitrary integer and list) E C/ are
1150)) = VN Ex
i=1 vPi (t) [0) [Bi(f]) (0) + (
arbitrary auxiliary states.
6: Perform controlled rotation Ry based on [Bi(f]) and
revert By
We define the number of calls that algorithm makes to the quantum generative model G or classical generative model G as its quantum or classical sample complexity. Note that in Section 3.1, we have argued that comparing the time complexities of using quantum oracle and using a classi- cal oracle can be reduced to comparing the quantum and classical query complexities. In this section, although the quantum generative model g that we use is different from the quantum oracle OoM, the same reduction from time complexity to sample complexity still holds. The reason is that G and G have similar costs at the elementary gate level, assuming access to the classical circuit implementing G. addition, it only incurs logarithmic overhead for g to encode the transition probabilities into quantum amplitudes, provided that quantum random access memory (QRAM) (Giovannetti et al., 2008) is available. Finally, the quantum time complexities match the quantum sample complexities up to log factors, provided that these assumptions hold and G can be called in constant time.
(2)(2) = VN E Vp.fi (t) (000) + (
7: Apply T iterations of amplitude estimation with state
(1) = ( operator U = 2 (e) (0b - I, and pro- jector P = I @ (000) (000) to obtain pau.
8: end for
9: Return: jt N ((e))()
of QVI-2 which allows the estimates (a) to have an one-sided error. This is a variant of the monotonicity tech- nique which was originally proposed for solving the infinite- horizon MDPs more efficiently (Sidford et al., 2018). This technique ensures that the value function V,, is bounded by the value function of the policy Vi at the same time step.
Theorem 3.8 (Correctness of QVI-2). The outputs प and (V. H-1 Th= satisfy that Vi - S V. < V < V% for all h E [H] with a success probability at least 1 - 5.
Theorem 3.9 (Complexity of QV1-2). The quantum query complexity of QVI-2 in terms of the quantum oracle of MDPs 0aM is
We formally state the optimization goals in this setting. For given time-dependent and finite-horizon MDP M, E (0, H) and ă E (0, policies, V-value functions and Q-value functions with prob- ability at least 1 - 8. With these objectives, we aim to design algorithms that require as few queries to the quantum generative model G as possible.
0 $1. VAH' log(S (0g(SA1511/0))
want to obtain e-optimal
(3)
4. Generative Model Setting
Even though the exact dynamic model allows precise calcu- lation of optimal policies and values, such a model is not always readily available in a complex environment. In this section, we focus on the generative model setting as studied in (Li et al., 2020). Specifically, we assume that the agent lacks full access to the transition probabilities but can query generative model sample transitions for specific state- action pairs. Note that similar models have often been used in the classical setting, where one is assumed to have access to a generative model G, which can generate N independent samples for each (s, (a,,,,) E S x A x [H] satisfying
Before delving into our algorithms, we first introduce an- other important quantum subroutine, quantum mean estima- tion, in Theorem 4.2. Quantum mean estimation consists of two similar quantum algorithms, which are QME1 and QME2. Both of them are referred to as QME.
Theorem 4.2 (Quantum mean estimation (Montanaro, 2015)). There are two quantum algorithms, denoted as QMEI and QME2, with the following properties. Let St be fintt set, p (P=)xeg a discrete probability distribution over Ω and f Ω - R function. Assume access to quantum oracle Up for the probability distribution p sat- isfying U, : :10) 10) + Ezee vPz (x) (ja) where (ia) are arbitrary auxiliary states, as well as an oracle By for the function f. Then,
(s) lid. Phls,as i= 1=
(4)
Correspondingly, we define a quantum generative model g for an MDP M in Definition 4.1. It is important to point
6

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
1. Taking u,e 0 as additional inputs, along with the assumption that 0 S f(x) S u for all x E S2 QMEI requires ( + queries to Up and By,
Algorithm 4 Quantum Value Iteration (M,
1: Require: MDP M, quantum generative model G. max- imum error e E (0, H]. maximum failure probability
8 E (0. 1).
2. Taking σ > O and e E (0,4 as additional inputs, along with the assumption that Var[f(x) | x ~ p] S o², QME2 needs ( (g)) queries to Up and B
Initialize: ( < 5/ (455AA log(1/6)), VH <
3: for h = H 11 1,..., do
4: create quantum oracle By encoding Vh+1 E ES
to output an estimate iı of μ Blf(2) | x~ p|-p==10 pp" sat- isfying Pr(Iä pl > c) < 1/3. Furthermore, by repeating either QME1 or QME2 a total of (loo(1/6)) times and taking the median of the outputs, one can obtain another 6.
Ys E S : create a quantum oracle BEn,. encoding
En,s E R.A with 9 and Bih-- satisfying
(n,)(a)
(MEII((PA)) Vn+1), 2Hz) 2H
6:
create a quantum oracle Brd encoding r E S*A
estimate is of p. such that Pr([ā- ul < <))
7:
Vs E S create a quantum oracle BQ... encoding
Qna E ERA with Br, and BEn.. satisfying
We denote (ME(i]<<p") f.e) as an estimate of f to an error at most with probability at least 1 - 6, obtained via (ME(i} for i E (1. Roughly speaking, QME1 is quantum version of Hoeffding's ss inequality, while QME2 corresponds to the Chebyshev's 's (or Bernstein's 's inequality. For example, for a random variable X E [0, u]. Hoeffding's ' inequality implies that O(²2 samples are required to
(a) + max(ra(s; a) + =n,s(a),
8: E f + QMS, (MM)(()n.(a)) : A}
9: E S: (s) + (*(,
10: end for
I1: Return: म. {
1-1
obtain an e-estimation of [ In comparison, QME1 only requires (u//e) quantum samples when e E (0, u].
sample complexity derived from above informal analysis matches the sample complexity of the algorithm in (Sidford et al., 2023) (up to log-factors).
Next, we will discuss how to apply the quantum subroutines, QME and QMS, into the model-free algorithms for finite- horizon MDPs by (Sidford et al., 2023) and (Sidford et al., 2018), and propose two quantum algorithms QVI-3 and QVI-4 which have significantly less sample complexity than the SOTA classical algorithms (Li al., 2020).
Now, we show how to achieve speedup in A, H and e by using the quantum subroutines QME and QMS. By using quantum mean estimation QME1, it only requires OSSA/ H3 Hz2((2/H²)) = O(SAH?/e) queries to the quantum generative oracle G to obtain e-approximations of Pi Va+1 1 for all pairs (s, a) E S x A at each time step. Hence, the total quantum query complexity in H iterations becomes OSSAH /c). Furthermore, we apply the quan- tum maximum searching QMS in the Bellman recursion to maximize the value on the RHS of Eq. (6). Then, the query complexity further reduces to O(SVAH/ These are the fundamental ideas of Algorithm 4, denoted as QVI- 3. In order to correctly apply QME, we also apply the monotonicity technique in QVI-3 by subtracting the error induced by QME1 so that the V values V/, at each time step are bounded in [0, H) Finally, QVI-3 can obtain not only e-optimal policy Ā but also e-optimal V-value functions (V% ( (Theorem 4.3) with probability at least 1 5, which requires only D(SVAH /e) queries to the oracle G (Theorem 4.4). The rigorous proof of the correctness and complexity of QVI-3 are provided in Appendix B.
4.1. Technical Overview of QVI-3
We first briefly review the main idea of the classical al- gorithm Randomi zedF wniitiiorizoonn proposed in (Sidford et al., 2023). In the standard value iteration al- gorithm (See Algorithm 6), we initialize Vn E R with all zero entries and repeatedly apply the Bellman recursion Vn ("(+++)) starting from the last time step and mov- ing backward to the first, where the Bellman value operator Th: : RS + R is defined as
[T' (V = max(ra(s,a) + PTT Vitth, (6)
REA m
for all s E S. Instead of computing the exact value, they obtain an approximation of [T*(V++))] by estimat- ing PTT P Va+1 via sampling from the classical generative model G and taking maximum over the action space A. In order to obtain e-optimal policies and V-value func- tions, they control the error of estimating pT bls,a Vn+1 to be e/H. If it also holds that V1 I H. then it re- = O(SAH /e2) queries to G
Theorem 4.3 (Correctness of QVI-3). The outputs ñ and (V,, W satisfy that Vù - S Vn, S V S Vū for all h E [M]] with a success probability at least 8.
Theorem 4.4 (Complexity of QVI-3). The quantum query complexity of QVI-3 in terms of the quanium generative oracle G is
quires ASSHH ((SAF?2(*²/H at each time step h to obtain the estimates of Piis.vVn- Vh+1 for all state-action pairs, according to the Hoeffding's 's inequality. Finally, the classical sample complexity of obtaining near optimal policy and values would be OSSAH%/2). The
O Sv SAH' (SAL.5H8))
7

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Algorithm 5 Quantum Value Iteration (VI-4(M,c,6)
1: Require: MDP M. quantum generative model G. maximum error e E (0, v H.. maximum failure probability E (0, 1).
2: Initialize: K= + [log2 (H/c) + 1, t- 6/4KHSA, e = 0.001, b=
3: Initialize: w/ E [ Vo.. < 0: Vs E S, E [M] =0
(0) (s) <- arbitrary action a E A.
4: for k = 0..... K - 1 do
5: EK < H/2², Vs.H + 0, V (0)
k.H + 0
6: V(s,a, h)) 8 x A [ y/,, (8, a) t max (QMEI his.a (V b) -
(QMEI -) (PT Masa k,t+1 H)) 221))22)) ,0} V(
7: ((s,a,h))&&xA1 X [M] (8, + QME2, (PT)
h/os,a k1h+1 Hús VILh + 46)
HT. v Uk a) + 45
or
8: for -or do
9: ((s.a) A: (k,n a) + QME1 <
(P (Ph -Vent V cH cH ex) - cH tek
10:
(( A: (s,((
(2,A max(ra () +
gr,h as,a),
11:
E Vv.(s)) t Vs.n(s) - -V((Q (s, + (s, t [
12: E if V4, (5) S Vi (s). then (s, + V (6) and (s, + Tx (s,
(0)
13: end for
14: vh. E [H] k+ h + Vr,F and गH x (, h) s (:)
15: end for
16: Return: == ===--- (V = (VK- 1 ) 1-1 (Q = 1Qk 1IK
4.2. Technical Overview of QVI-4
(00) 0 S Vi,h+1 k,b+1 I čeş for some constant ē O, it can be done up to error (2H() using only O(H²) clas- sical samples or O(H) quantum samples by the Hoeffd- ing's bound or QME1, respectively. Similarly, for the second estimation, if it holds that 0 S Vi S H, it requires O(H classical samples or O(H2 /cx) quan- tum samples. The overall classical sample complexity is O (KSSA(FF)/& / + H²) = Ö(SAH' /cf), while the quantum sample complexity is O Hc)+
Note that QVI-3 can only obtain e-optimal policy and v- value functions. Below, we will introduce another algorithm, QVI-4 in Algorithm 5, which can obtain not only c-optimll policies and V-value functions, but also Q-value functions. In this setting, although we can no longer attain a speed-up in A, we attain a speed-up in H by utilizing two additional techniques in (Sidford et al., 2018): "variance reduction" and "total variance".
AHH Note that unlike Section 4.1, we do not ex- pect a speedup from A to VA here, since we need to es- timate the Q-values for all actions (instead of finding the action with the highest Q-value). Although the variance reduction technique alone does not achieve speedup in H compared with QVI-3, we will see the advantage when combined with the subsequent total variance technique.
We now introduce the essential ideas of the two new tech- niques and show how to integrate these techniques with the quantum mean estimation QME to reduce the sample complexity. First, the main idea of variance reduction tech- nique is that, instead of using the standard value iteration algorithm (Algorithm 6) directly for a target approxima- tion error e, one repeats the value iteration algorithm for K- = (log((H/c) epochs with decreasing c satisfying < = 122 and ex = In each epoch k, we obtain éς- optimal V-value functions { H-1 Q-value functions H-1
The total variance technique stems from the observation that the actual error propagation across time steps is much smaller than previously assumed. Previously, the error in estimating s.e == PTT s,a Vr,h+1 at each time step was set to c (2H,, ensuring that the total error accumulated over H iterations remains bounded by ex/2. In fact, the per- step error can be further relaxed to k /./k////27 (2.H1. where s.a
[== and policy лд- Note that, at the time step h in epoch k. the second term on the RHS of Eq. (6) can be rewritten as follows
8.0
PT lala, Vi.h+1
PJT
- (2(0) 11)
1) + PT (0)
Als,a k
RA = [an (oVV/oo))ee a). This error value can reach up to < (2VHH. As the cumulative standard deviation Vn o RKA trivially upper-bounded by 1.5 (Lemma B.2), the total er- ror remains c With classical algorithms, Migh can be es- timated with an error eo without explicitly knowing o This requires overall OS 1-5)- -2) = O(SAH3/2) classical samples per time step at each epoch, as guaranteed
(8) A.h+1 E IR$ is defined as an initial V-value function for the time step h 1 from the previous epoch &: 1. Note that there are total S.A of these equations, each of which is corresponding a pair (s, a) E S x A. Rather than directly obtaining / H- -ettimmttion of P.T A/ssa Vk,h+1, V/ls.aV,,.41,, we instead ob-
where (0)
5.a is associated with an expression that can be non-
S.a
tain < (2H) estimations of both PT Pajs,a (Vi,t41 (=(0) 1 and PT (0)
h/s,0 K, For the first estimation, if we have
8

---

5..4 "R ensuring Quantum Algorithms for Finite-horizon Markov Decision Processes
by Chebyshev's (or Bernstein's 's inequality. When combined with the variance reduction technique in estimating the first term on the RHS of Eq. (8), this approach achieves an over- all classical sample complexity of O(SAH* /e",, matching the complexity of the algorithm in (Sidford et al., 2018)'.
tions and Q-value functions for a finite-horizon and time- dependent MDP M. Our proof idea is to reduce infinite- horizon MDP problem to finite-horizon MDP problem. Specifically, we show that, if there is an algorithm that can obtain an c-optimal V-value function for the finite-horizon MDP, it also can give an 2e-optimal V-value function to the infinite- horizon MDP. Therefore, the lower bound of solv- ing fnite-horizen MDP with a quantum generative oracle inherits from that of the infinite-horizon MDP. The full anal- ysis is presented in Appendix B.3. Note that our achievable quantum sample complexities of QVI-3 and QVI-4 differ from the quantum lower bounds only by a factor of H or H up to logarithmic factors.
Inspired by (Wang et al., 2021), we can adapt the total vari- ance technique in the quantum setting. The main challenge that we cannot directly apply the quantum mean esti- mation QME2 like its classical counterpart. First, QME2 4.0 cannot estimate Pk.h to an error of toigh/ (2H1.) with- out prior knowledge of 5. To address this, can use QME1 to obtain an estimate (&x of (o with an error 4b > 0, then use QME2 to estimate Hk.h 8.0 with an er-
Theorem 4.7 (Lower bounds for finite-horizon MDPS). Let S and A be finite sets of states and actions. Let H be a positive integer and E (0, 1/2) be an error parameter. We consider the following time-dependent and funitehhrrizon MDP M (S,A, {Pr [P H- H-- [0, 1|s for all h E [H].
ror - (2H where A := (022)) 4b S 20 to maintain the correctness. Second, QME2 also requires upper bounds C E E on '.h. Observing that its sam- ple complexity O(C/c) can be inefficient for large C, an ideal way is to use k, = /0221)2 + 4b as C. How- ever, this may lead to an unbounded complexity ratio 4b). To resolve this, we es- timate a. with an error proportional to C/okk s.a k. = 1. Although the correctness may not hold due
{ra)
H),, where Tb. E
Given access classical generative oracle G. any algorithm K., which takes M as imput and out- puts e-approximations of {Q H-1 with probability at least 0.9, must call G at least O (log
((0g,)) + 4b) (b))(((),))
(V H-1 Jh=0 or x²
SAH" times on the worst case of input M.
k, + 7b and suppress the extra error by setting b and the parameter in QVI-4 small constants. Ultimately, QVI-4 can ob- tain 6-optimal policies, V-value functions and Q-value func- tions (Theorem 4.5) with OSSAH22 /E) queries to the quan- tmm generative oracle 9 (Theorem 4.6), which holds for == O(L/VH). The proof of the correctness and complex- ity of QVI-4 is presented in Appendix B.2.
to KAA > a.
k,h- we can bound 6.0 S 6.0
Given access to a quantum generative oracle G. any algorithm K. which takes M as an input and outputs e- approximations of (Q1) H-1 with probability at least 0.9, must call G at least O clog SAHLS times on the worst case of input M. Besides, any algorithm K. that ousputs e-approximations of \ or x²" with prob- ability at least 0.9 must call G at least Q SvānLs times the worst case of input M.
H- Th=o
Theorem 4.5 (Correctness of QVI-4). The outputs ft, H satisfy that Hi and {
clogg"((e
V/ c S V/ V S V
(9)
5. Conclusion
Oi - c < Q S Q S Th
(10)
To the best of our knowledge, this is the first work to rigorously study quantum algorithms for solving "time- dependent" and "finite-horizo"" MDPs. In the exact dynam- ies setting, our quantum value iteration algorithm QVI-1 achieves quadratic speedup in the size of the action space (A) for computing the optimal policy and V-value function, while QVI-2 achieves an additional speedup in the size of the state space (S) for computing near-optimal policy and V-value functions. Besides, our classical lower bounds show that no classical algorithm can attain comparable query com- plexities of QV1-1 and QV1-2 in terms of the dependences S and A. In the generative model setting, our algorithms QVI-3 and QVI-4 achieve speedups in A, time horizon (H), and approximation error (e) over the SOTA classical algorithm and are asymptotically optimal, up to log terms, for computing near-optimal policies, V-value functions, and Q-value functions, provided constant time horizon.
for all h E [M] with success probability at least 1 8.
Theorem 4.6 (Complexity of QVI-4). The quantum query complexity of QVI-4 in terms of the quantum generative
oracle G is
2 A
HI.5
+ HJ) log2(
loog (/S)
(11)
4.3. Quantum Lower Bound for Finite-horizon MDPs
We now state the quantum lower bound of the sample com- plexity for obtaining the c-optimal policy, V-value func-
The result in (Sidford et al., 2018) was originally presented for the time-independent case. We adapt here for the time-dependent case with an additional factor H.

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Acknowledgements
the 46th International Colloquium on Automata, Lan- guages, and Programming (ICALP 2019), 33:13-3333:144 Patras, Greece, 2019.
We especially thank Zongqi Wan for providing insightful guidance on quantum subroutines, including quantum maxi- mum searching (Durr & Hoyer, 1999) and quantum mean estimation algorithms (Montanaro, 2015), and for suggest- ing helpful references, including (Cornelissen, 201 8). The work of John C.S. Lui was supported in part by the RGC SRFS2122-4S02.
Chen, Y. and Wang, M. Lower bound the putational complexity of discounted markov decision problems, 2017. URL 1705. 07312.
/
Cherrat, E. A., Kerenidis, L., and Prakash, A. Quantum reinforcement learning via policy iteration. Quantum Machine Intelligence, 5(2):30, 2023.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning and AI via quantum computing. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Cornelissen, A.
Quantum gradient estimation and its ap- plication to quantum reinforcement learning. Master's thesis, Technische Universiteil Delfi, 2018.
Draper, T. G. Addition quantum computer. arXiv preprint arXiv:quant hww::quant-ph00000333 2000.
References
Durr, C. and Hoyer, P. A quantum algorithm for finding the minimum. arXiv preprint wxXiv:quamt-ph/1600014 1999.
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Rein- forcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, United States, Tech. Rep, 32:96, 2019.
Feng, X., Wan, Z., Fu, H., Liu, B., Yang, M., Koushik, G. A., Hu, Z.,, Wen, Y., and Wang, J. Natural language reinforcement learning, arXiv preprint arXiv:2411.14255 2024.
AI, G. Q. et al. Quantum error correction below the surface code threshold. Nature, 2024.
Alsheikh, M. A., Hoang, D. T., Niyato, D., Tan, H.-P., and Lin, S. Markov decision processes with applications in wireless sensor networks: A survey. IEEE Communica- fions Surveys and Tittorials, 7(3):1239-1267) 2015.
Gilyén, A., Arunachalam, S., and Wiebe, N. Optimizing quantum optimization algorithms via faster quantum gra- dient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). pp. 1444, San Diego, CA, United States, 2019.
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G., Buell, D. A., al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):05-5510 2019.
Giovannetti, V., Lloyd, S., and Maccone, L. Quantum ran- dom access memory. Physical Review Letters, 100(16); 160501, 2008
Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eigtth An- nual ACM Symposium on Theory of Computing (STOC 1996), pp. 212-219, Philadelphia, PA, United States, 1996.
Beals, R., Buhrman, H., Cleve, R., Mosca, M., and de Wolf, R. Quantum lower bounds by polynomials. Journal of the ACM, 48(4))778--77777 797, 2001.
Bellman, R. Dynamic programming and stochastic control processes. Information and control, 1(3):228-239, 1958.
He, J.. Yang, F., Zhang, J., and Li, L. Quantum algorithm for online convex optimization. Quantum Science and Technology, 7())0225022, 2022.
Bellman, R. Dynamic programming treatment of the travel- ling salesman problem. Journal of the ACM, (1)x61163, 1962.
He, J., Liu, C., Liu, X., Li, L., and Lui, J. Quantum algorithm for online exp-concave optimization. In Inter- national Conference on Machine Learning, pp. 17946- 17971. PMLR, 2024.
Brassard, G., Hoyer, P., Mosca, M., and Tapp. A. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
Jerrum, M. R., Valiant, L. G., and Vazirani, V. V. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188. 1986.
Chakraborty, S., Gilyén, A., and Jeffery. S. The power of block-encoded matrix powers: Improved regression tech- niques via faster Hamiltonian simulation. In Proceedings
10

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Jordan, S. Fast quantum algorithm for numerical gradient estimation. Physical review letters, (5 2005.
Puterman, M. L. Markov Decision Processes: Discrete
Stochastic Dynamic Programming. John Wiley and Sons, 2014.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Breaking the sample size barrier in model-based reinforcement learning with generative model. In Proceedings of the Advances in Neural Information Processing Systems (NIPS 2020), pp. 12861-12872, Vancouver, BC, Canada, 2020.
Ruiz-Perez, L. and Garcia-Escartin J. C. Quantum arith- metic with the quantum Fourier transform. Quantum Information Processing, 16(6): 152, 2017.
Shor, P. W. Algorithms for quantum computation: Fiscrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994). pp. 124-134, Santa Fe, NM, United States, 1994.
Liu, C., Guan, C., He, J., and Lui, J. Quantum algorithms for non-smooth non-convex optimization. Advances in Neu- ral Information Processing Systems, 37:35288-35311 2024.
Sidford, A. and Zhang, C. Quantum speedups for stochastic optimization. Advances in Neural Information Processing Systems, 36:35300-35330, 2023.
Magniez, F., Nayak, A., Roland, J., and Santha, M. Search via quantum walk. In Proceedings of the Thirty-Ninth Annual ACM Symposium Theory of Computing (STOC 2007), pp. 575-584, San Diego, CA, United States, 2007.
Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. Near- optimal time and sample complexities for solving Markov decision processes with a generative model. In Proceed- ings of the 32nd International Conference on Neural In- formation Processing Systems (NIPS 2018), pp. 5192- 5202, Montréal, QC, Canada, 2018
Matignon, I.., Jeanpierre, I.,, and Mouaddib, A.-I. Coordi- nated multi-robot exploration under communication con- straints using decentralized Markov decision processes. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2012), pp. 2017-2023, Toronto, ON, Canada, 2012.
Sidford, A.. Wang, M., Wu, X., and Ye, Variance reduced value iteration and faster algorithms for solving Markov decision processes. Naval Res. Logist., 70(5):423 442, 2023.
Montanaro, A. Quantum speedup of Monte Carlo meth- ods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, (71(2181):20150035 2015.
Vedral, V., Barenco, A., and Ekert, A. Quantum networks for elementary arithmetic operations. Physical Review A, 54(1):147-153, 1996.
Naguleswaran, S. and White, L. B. Quantum search in stochastic planning. In Noise and Information in Nano- electronics, Sensors, and Standards III, pp. 34-45. Austin, TX, United States, 2005.
Wan, Z., Zhang, Z., Li, T., Zhang. J., and Sun, X. Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 10087- 10094, 2023.
Naguleswaran, S., White, I.., and Fuss, I. Automated plan- ning using quantum computation. In Proceedings of the Sixteenth International Conference International Con- ference on Automated Planning and Scheduling, pp. 418- 421, Cumbria, UK, 2006.
Wang, D., Sundaram, A., Kothari, R., Kapoor, A., and Roetteler, M. Quantum algorithms for reinforcement learning with a generative model. In Proceedings of the 38th International Conference Machine Learning (ICML 2021), J,, pp. 19916-10226, 2021.
Nayak, A. and Wu, F. The quantum query complexity of approximating the median and related statistics. In Proceedings of the Thirty-Fire First Annual ACM Symposium on Theory of Computing (STOC 1999), pp. 384-393, Atlanta, GA, United States, 1999.
Wang. S., Li. X., Lee, W. J. B., Deb, S., Lim, E., and Chattopadhyay, A. A comprehensive study of quantum arithmetic circuits. arXiv preprint arXiv:2406.0388 2024.
Nielsen, M. A. and Chuang, I. L. Quantum Computation and Quantum information. Cambridge University, 2010.
Wiedemann, S., Hein, D., Udluft, S., and Mendl, C. Quan- tum policy iteration via amplitude estimation and Grover search-towards quantum advantage for reinforcement learning, arXiv preprint
Oliveira, D. S. and Ramos, R. V. Quantum bit string com- parator: Circuits and applications. Quantum Computers and Computing, 7(1):17-26 2007.
2022.
Powell, W. B. Approximate Dynamic Programming: Solving the Curses of Dimensionality. John Wiley and Sons, 2007.

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
A. Exact Dynamics Setting
A.1. Classical Algorithm for Finite-horizon MDPs
For the completeness, we restate the classical value iteration (or backward induction) algorithm in (Puterman, 2014).
Algorithm 6 Value Iteration (Backward Induction) Algorithm for Finite Horizon MDPs
Require: MDP M.
2: Initialize: VH <
-1,...,0 do 3: for h:= H
4: for each E S do
5: for each E A do
6: Qn(8, a) = rh(8, (8, + Σ Puls.a6')Vn+1((1
3'ES
7:
end for
8: T(s, h)- = argmax (8, a)
aEA
9: (s(s) = Qn ((,
10: end for
11: end for
Return: n, Vo
A.2. Classical Lower Bounds
Proof. We define two sets hard instances finite-horizon MDP M and M2 which are the same as those in Section 4.1 in (Chen & Wang. 2017). Specifically, suppose that the state space where the cardinalities the sets Sy, SG and Sg satisfy Sy = Sc SB - and sN is single action. Let the action space be A Au U {ax), where the cardinality of the Au satisfies Au A - and o is single action. We now construct two sets of MDP instances Mi and M2 that are hard to distinguish.
be divided into four parts S = St U So USB {sx}.
Let M1 be the set of instances satisfying the following conditions.
- Ps = P E [0, 11sxxAx for all h E [H] and = E [0,1] where H 2 2;
For any (s, a) satisfies Sg U Upp U (sN) and A, the transition probabilities satisfy P(s'ls, 1 if s' and P(s'|s, a) = 0 if s' of s, i... the states in Sg U U {NN} are absorbing states. Besides, the reward functions satisfy
1, if Sc, E A
r(s, a) =
0. if E SB, a a A.
(12)
if = oN, A
For any a E Ay and E Sv, the transition probability satisfies P(s'|8, a) 1 if s' E SB and P(s'(s,a) = 0 otherwise, while the reward satisfies r(s, a) = 0.
For any ax and E Sv, the transition probability satisfies P(s'|s, a) = 1 if s' and P(s'ss,a) 0
otherwise, while the reward satisfies r(s, a) = 0.
Let M2 be the set of instances that different from those in M1 at state-action pair, which denote by (z, E Sy x Ar.
- When (s, (8, a). the transition probability satisfies P(5'l8, a) = for some s' E So and P(s|ss, a) = O otherwise, while the reward satisfies r(s, a) = O.
From the above definitions, we can know that the cardinalities M1 and M2 are [S Ael and |St x x XAul, respectively. We now compute the optimal V-value function Vi,M, for any finite-horizon MDP M E M,.
For Sc, V I.MM,M, (s) maxxesff(ss.d) + P V V 1, because V V..M, 0. Further, since is an absorbing state, Vi,,, (8) = +
V Vi H H-hh Hence, we can compute Vo,M, (8) H.
12

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
For Sg, since r(s, a) 0 for all a E A and is an absorbing state, we can compute Vi,,, (s) 0 for all h (H].
When s = SN, since r(s, a) = for all a E AA and s is also an absorbing state, we can compute Vg,M, (s)
1/2 + I,,,,,,, (s) H and Vo,M, (s) -/2
For s E Su. we can compute V M, (8) = max,ex(((s,a)) = 0. Further, by the Bellman optimality equation (Bellman, 1958), we can compute
Vii 2.M, (8) = max max (r(s,
Σ (1 VVllls.a)VV-1.MM
aEA
E'ES
= max ( (+) E Sn), V (oN)
(13)
= mmax(0, }
The second line comes from the fact that r(s, = 0 for any E A and state will transition to SN if a = aN or transition to some state & E SB if a E Av. By induction, we know that Vi,, (8) = max (Vi+1,M (8)1(8 e Sn); V Vi, (SN)) m0, " " and VoLM, (+) _-1
Similarly, we can compute the optimal V-value function Vo,M2 for any finite-horizon MDP M2 E M2. Since M2 only differs from M₁ on the state-action pair (3, a) E Sy x Ay and the states s E Sg x SB x {sx} } are absorbing states, Vi,Ma (s) only differs from Vi,, (s) on state 3. Specifically, V VH-1M,, max (r(3, a)} = 0 and
Vi.Ma (3) max max((((s,a) + Σ V(Viss,a)VVit.M (s'))
atA
s'ES
= -max (s) E SBh, Vitti.Ms E (s) (oN)
(14)
H h+1
max H h 1
2
= -
The first line comes from the Bellman optimality equation (Bellman, 1958). The second line comes from the fact that r33, a) 0 for all a E A and the state will transition to some state E Sg, s' E SG or s' 3N under the action E Au (a),
av- Hence, it implies that Vo,M, (5) H 1. However, V Vo,M, (5) H-1 Therefore, 2 can see that Vo.M, - Vo Il 2 Using the same proof in Section 5.2 in (Chen & Wang, 2017), we can know that, achieve 11 --1 oottimll Vo with high probability, any algorithm must distinguish Mi from M2, requiring search for two discrepancies in an array of size |Sy Au x Spl S2S A) by quering the classical oracle O.M- Therefore, given the classical oracle OM, the classical lower bound of query complexity for computing an e-optimal Vo for the time-independent and horteehorizonn MDP is ((S² A) for e E (0. --)). This implies the classical lower bound of query complexity for obtaining an e-optimal policy or c-optimal V-value functions for the time-dependent and hinite-horizon MDP 2(5 A).
A.3. Correctness, Complexity and Qubit Cost of QVI-1 (Algorithm 1)
1. CORRECTNESS OF QVI-1 (PROOF OF THEOREM 3.5)
Proof. First, we consider the failure probability of the algorithm to achieve above goal. Every QMS is performed with maximum failure probability Ç (HHS) and QMS is called SH times when running Algorithm I one time. By the union bound, the probability that there exists an incorrect output is at most 6.
Now, we assume the ideal scenario when QMS is always successful to find the action a" = arg maX Qn, i.e., (s, h) = arg max.e.A (a. Note that we assume (s)(s) = 0 for all s E S. Then, we have Qu- = TH 11, for any policy म, indicating that (1)) QH-1((s, (H,1(s,a).
Assume that with our policy (ss h)) = arg m (a) for all s E S, h E [H], we have (a) = (s, Q (s, a) for all E S. E A, h E [H). Besides, we define it f (als) as the probability that the agent choose action a in
the state s at time h. Note that nn (a|s) = 1 if = (s, h) and in (a|s) = otherwise, By Bellman equations, we have
13

---

Quantum Algorithms for Finitc-horizon Markov Decision Processes
V (8) Q (a( and Q% a) rn(5,a) pT Va basa
Then, know that, for all 8 E 8 and
E [
(s) = max max
Σ
(((s,))aa(lss)
Rat1
aEA
Σ a)(s,a)#taall))
max
DEA
(15)
(((,,t((s
= =(no(f(ssh)))
(s).
Besides, since (% (8, b)) (x (s, h)) by the assumption, then (s) (s)(s) for all 8 E 8 and h E [H].
Similarly, assume that with our policy & (s, h) arg max (a) for all s E S, E (H), we have Va(s) = V2,
V (s) for all s E S, E [H] Then, we have
a)( = (n( + max Σ (s)ssa(')VV+1(())
d'ES
= =s) + Σ
Prlsia (++)
e'ES
(16)
=ra(saa)+ + Σ
Phts,a (8 (') (5))
e'ES
= Qn)((a)
Note that we also have V/. = V/ for all h E [H] Then, also holds that Q7, = rh + PT h|s,a VA+1 = rh + PT V N/s.0 h+1 = O Since Q= = Q (s = - a) for all s E S, E A, then we can know that V=-1(s) = V (s) (
V holds for all S, then can deduce that Qn-2,0(0 = Qs) = 2 for all 8 E S and a E A. In the end, we can conclude that vo(s) Vo (s) (s) for all s S which implies à is optimal policy.
(s) for all S. Furthermore, since Vn-
A.3.2. COMPLEXITY OF QVI-1 (PROOF OF THEOREM 3.6)
Proof. We first assume that all QMS are successful to find the optimal actions, up to the specified error, because the probability that this does not hold is at most 6. Let be the complexity of QVI-I(M, 8) as if all QMS are carried out with maximum failure probabilities set to constant. Then, since the actual maximum failure probabilities are set to Ç = 8/(SH), the actual complexity of QVI-I(M,
O(Clog(SH/0))
(17)
Now, we check each line of QVI-I(M, to bound
In line 4, we encode the vector Vh+1 an oracle B This process does not need to query OeM and only needs to access the classical vector V/+1. Therefore, the query complexity of B in terms of OoM is O()).
In line 5, we need to construct the quantum oracle BQn,, with OgM- Since we need to obtain (s)s,a('')) for all s' e and calculate the weighted sum EΣves Pals,a (s') (s')), it requires O(S) query cost of the oracle OgM- Note that the quantum addition and quantum multiplication can be performed by various quantum circuits, such as quantum Fourier transform techniques (Ruiz-Perez & Garcia Garcia-Escartin, 2017; Draper, 2000). Therefore, the query complexity of B in terms of O&M is O(S).
In line 6, we can use quantum maximum searching algorithm QMS in Theorem 3.4, resulting in query cost of order O(VA) to the oracle Ban,, for
each loop h [M].
Therefore, it induces an overall query cost of = Oss VAH) to the oracle Oam Combining with (17), the overall
14

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
quantum query complexity of (VI-I(M, in terms of QMM is
O(5 (SH(8))
(18)
A.3.3. ANALYSIS ON THE COST OF QUBIT RESOURCES
Considering that qubits are still scarce resources in quantum computer, it is necessary to minimize the qubits resources required in a quantum algorithm. Note that the line 5 of Algorithm is the main source of consuming qubits in the whole algorithm. Constructing the oracle BQ for all s E S and h E [H] requires a large number of auxiliary qubits. This is because the process involves storing information about the vector VA+1 E R and the transition probabilities (s") for all s' S, which are obtained by querying the quantum oracles Bynss and OQM- After encoding the classical information into qubits, we need to compute the weighted sum Eves (s')aa+ This process requires (non-modular) quantum adder(Ruiz-PPree) & quantum multiplier (Ruiz-Perez & Carcia-EEsartin, 2017: Vedral al., 1996) compute the additions and multiplications with additional auxiliary qubits. Specifically, with the fixed-point representation, (Ruiz-Perez & Garcia-Escartie 2017) constructs quantum circuits of non-modular quantum adder Ug [Bi(a]), ) [ii(] + [Bi(a]), [Bisa] + Bi(b)) g and a non-modular quantum multiplier UgMut= : [Bi[a]}, [Bi(b]), y 10)2, ~ Bi(aa), Bi bibb),
2017: Draper, 2000; Vedral al., 1996) and non-modular)
which can compute the non-modular sum and multiplication of two non-negative real numbers and b. We refer readers to (Wang et al., 2024) for a
comprehensive overview of the existing work on quantum arithmetic circuits.
Inspired by the quantum circuit for computing the controlled weighted sum proposed in Section 8 in (Ruiz-Perez Garcia- Escartin, 2017), design a QFT-based circuit reduce the qubits consumption in constructing the oracle B We first
prepare the following qubits
|a) |s) (h) 10] +.g+
(19)
where 4- = [log2(S) Then we apply the rotation matrix U2 to transform the (0) to the target state (s'). Since we encode the state space into orthonormal bases, then U2 unitary. Hence, it returns the output state
|a) (8) (b) |s') J0) 844+1
(20)
By applying the unitary oracle OQM and B Bener can obtain the following state
(a) |s) (h) (8') Bilrx(ss a))) Bi(Pkis,a BiilV 10) 18t11
(21)
Then we compute the quantum Fourier transform of (0) @a+1 where
QFT (0) 89+1
(A) = lo(0)),
(22)
22
A=U
we obtain the output state
(a) (8) (4) |s') [Bi(rn(s, a)))
[Bi[Paje, [Bi[V (o(0))
(23)
Then we apply the multiplication block U2- Po) (on defined in the Fig. in (Ruiz-Perez & Garcia-Escartin, 2017) and obtain the output state
(a) |s) (b) |s') Bi(rx((s a)l) [Bi[Pajs,a (s')l [i(( 10(0 Bi(PP)s.a (F)
(24)
By applying the unitary matrix B obtain the following state
Van. olem and Ut in sequence, we can undo the operations auxiliary qubits and
(a) |s) (4) [0) 839-9 1o(0 + Bi[Pa]s, ("))))+
(25)
We can repeat the above operations for all s' E S and obtain
(a) [s} [b) (0) 030+4. 1o(0 +
Σ
Bi PMj (8)
(26)
#E
15

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
By applying the inverse quantum Fourier transform on the state 1o(0 + Eves Bi[Pr]s,a (1)]Biaa we can obtain
aa) |s) (b) (0)
$3
Σ S'ES
(27)
Since Eves (s)), = 1 and (s)) E [o, 1] for all s' E S, there is no overflow when computing the weighted sum. Hence, the weighted sum is non-modular. Further, we apply the rotation matrix Up and the oracle OoM in sequence to obtain the state
(a) (s) (6) (s') [Bi[ra a))> [ 00
04
Σ e'ES
Bi
(28)
Then we apply the quantum adder UqAda obtain the state
aa) s) 1s') (s, a))) [ii[P]jaa(s))] |0) the Bifrx(s,
+ Σ
Bi(PM] M/s (s)V))
(29)
s'ES
Since there are g + 1 qubits in the last register in (28), then the sum of Bifrx(s, a)] and Eves (s') (s') has no overflow and the result is non-modular. Therefore, by applying Oem and UJ, in sequence, we can obtain the state
la) |s) 1b) J0) 03rt4, [if(r(ss,)) + [ii(Ph]sso (s))
(30)
s'ES
Remark:
Since the above operations are unitary, then the oracle BQn.. constructed in this way is unitary. Instead of w0+1
preparing (i(PP)ssaa [i (1)) .... Bi[Pr]s.a [i[V)+1(S]]) |0) and computing the weighted sum on the last register, which requires q22 + 1) + qubits as shown in Section 8 in (Ruiz-Perez. & Garcia-Escartin, 2017), our method significantly reduces the number of required qubits, needing only 3q + 1 qubits to compute the weighted sum, The main idea is to reuse the 2q auxiliary qubits [i((Pa)s,a( [Bi[V++ (+'V++(+'')) by leveraging the invertible property of the unitary matrices ORM and B Byr,, for all h E [H]. However, this comes at the cost of an additional S queries to O'am- We summarize the above results in creating the oracle B in the following Theorem A.1.
Theorem A.1 (Number of Qubits Required for the Construction of Oracle B Ban..) ). The total number qubits required for creating a quantum oracle B BQ.., for each h E [H] and S in Algorithm is 4q + 29, + 9h + 9a + 1, among which 3q + 2q. + qb. are auxiliary qubits, not counting the auxiliary qubits necessary to implement the oracle OQM and B for all h E [H), where 9s- = [log2 5), Qa = [log2 A] and qr. = [log2 H).
Theorem A.2 (Number of Qubits Required for QVI-1 (Algorithm 1)). The total number of qubits required for Algorithm I is 1 11g + 4q, + 2qh, + 4qa + 2, not counting the auxiliary qubits necessary to implement the oracle OoM and B for all h [.) where 9a flog2 $7, qa [log2 A] and qr flog, H.
Proof. In line 6 of Algorithm 1, we apply QMS algorithm to achieve quadratic speedup in searching the optimal action which achieves maximum value of the vector QR.. for all E S and h [H]. In this QMS algorithm, it requires an oracle OoMS to mark the indexes of the vector Q1.e which satisfy Qn, Qa,)laa), where a' is a threshold index, by flipping the phase of the (a). Therefore, the oracle OQMs is defined as
OQMS: : la) la') 1-) - (-1)fa (a) la") 1-),
(31)
where (a) = 1 if Qn..(a) > (a')(aa) and far (a) = otherwise, and |-> = 1/2 (10) - 11)). Figure 8 in (Oliveira & Ramos, 2007) showed way to construct the corresponding unitary quantum circuit of the oracle OQMs based on the quantum bit string comparator (QBSC) UOBSC. Given two real number a and b, UOBSC works as
UQBsc: : [Bi[a]} [Bilb) [0) 03(1-11) 10) 10) + Bi(a]) [Bib]) (V) (x) ly)
(32)
where (1)) is a 3(q - 1)-qub garbage state and the last two qubits store the comparison result. Specifically, we define that if then = y = 0. if a > then
and y = 0, and if a < b then x and y = 1. We restate the construction process under the background of our algorithm here. The first step to construct OQMS is to prepare the following qubits
|a) J0} 04 lay) 10) 04 (o) 13(--1) 10) 10) 1-)
(33)
16

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Then we apply Q created in line 5 to the first and third register and obtain the following state
[a) [a)(Q,..(a)) la') a (a')l) 10) (330-111 (0) 1-).
(34)
Then we apply UOBSC to compare (a) and (a.)
(a) [i)(Q... (a))) la') Bii (Q (a')) ((t) (x) lv) 1-).
(35)
Further, apply the controlled unitary matrix Ue- (I x σi [)T(I 0n @ I) to the last three qubits and obtain the following state
(-1)=(1~>) (a) [ii(Qn.(a))) la') [Bi[Q (a'))) (6) |x) (n)
(36)
where dn is the Pauli-X gate and T the Tofolli gate. By applying Udnsc and B Qn..' we can undo the operations on (a)]) and (a))), and obtain the following state
(-1)=(1->) (a) 00) 84 la') 10) sy 10 63(--1) (0) 1-)
(37)
From the above steps, we can see that the construction of the OoMS requires one query to B&s.. and one query to B
Qa. as
shown in (34) and (37). By Theorem A.I, we know that it requires 4q + 29, 9n + qe + 1 qubits to construct the oracle B Then it requires 2(4q + 2g, + qh + qa + + 2q + 3(g - 1) + 3 = 11q + 4g. + 2q. + 4qa + 2 qubits to construct the oracle OQMs. among which 2(4q + 24. + gn + qa + 1) + 3(q 1) + 1lq 4q. + 2qh + 2qa are auxiliary qubits.
A.4. Correctness and Complexity of QVI-2 (Algorithm 2)
1.4.1. PROOF OF THEOREM A.3
Theorem A.3. Let Z be a finite set with cardinality N, p (pa)zest a discrete probability distribution over Q. Suppose we have access binary oracle Bp (i) (0)
+ lt) Bi(p.]). By using ((1) invocations of the oracle Bp and Bj. we can
implement unitary oracle Up CN
& C
CN
58 C satisfying
Üp (1) 00)
10) +
i) [1).
(38)
N
Proof. First, we need to create the uniform superposition by applying Hadamard gates and query oracle Bp
b 10)
H mm
10) Bg
Σ
())
Bilp!))
(39)
Second, we add a single auxiliary qubit and perform a controlled rotation Rg based on the value stored in BBipx)) defined as Rp Biípp:) 00) Bilpx)) (vPi
(0)
+
/1
pt 1)):
N
R
1 Bilp.)) (vpi (0) + -- ps 11).
(40)
Third, we undo the oracle Bp and drop the auxilliary qubit |0) in Eq. (a) to obtain the desired result.
B¹
1
10)00) (/P: (0)
VI p: (1)
N
N
(
Vpi 1)
10)
+
V
Ps (1) [1]
(41)
1=1
N
N
Σ
10)
Ps
(0) (1)
N
N
-
17

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Lemma A.4 (Powering lemma (Jerrum et al., 1986).. Let K. a classical or quantum algorithm designed to estimate quantity μa, where its output Ji satisfies 1 ju S with probability at least 1 - for some fixed T 1/2. Then, for any 6 > 0, by repeating K. ((log(1/6) times and taking the median of the outputs, can obtain estimate such that j ul < with probability at least 1 5. 5.
Theorem A.5 (Amplitude estimation (Brassard al., 2002)). The amplitude estimation algorithm is designed estimate ((b) P 1b) E [0, 1] of quantum state (1)). It takes the following inputs, quantum state (1b). two unitary operators: U 2 (w) { and V = T - 2P, where P is some suitable projector, and an integer T, which determines the number of repetitions. The algorithm outputs an estimate ā E [0, for the amplitude The estimate satisfies the error
the amplitude
bound:
aall
a s
2T
(42)
T
T
with success probability of at least 8/1². To achieve this, the unitary operators U and V are applied T times each.
A.4.2. COMPLETE VERSION OF QUANTUM MRAN ESTIMATION WITH BINARY ORACLE QMEBO
In Section we provide simplified version of QMEBO by hiding the details of some auxiliary states and operators. For clarity, we provide a complete version in Algorithm Based the Algorithm 7, the auxiliary state in line of QMEBO in Algorithm should be
(()))
Pe (8) 11) Bi(AA) 10)
(43)
N
and the auxiliary state in line satisfies
N
N
(2))
Σ - (o(1-f))l))
Σ
/1 - p 11) (VF f1-f(11)
(44)
VN
A.4.3. PROOF OF THEOREM 3.7
Proof. We first show the correctness of Algorithm 3. Note that we obtain
N
N N
(2))
P pa) 0) (0) (vT + V1- +
(45)
where (b) = M =
Pi
11 03
(0) VT 11)). Besides, we have
N 1 N
(6)2) Plb5(2)
1 N
Σ p.S. (((())a>>p)) p]= N
(46)
where P P= To |000) (000). Hence, by Theorem A.5, we know that obtain μ4 in each loop & [K] such that
N
N
n
Paf
<
2m
(47)
N
T
T2
with probability least 8/7²2 Let N tr, where satisfies
Median(Pun (uus.. .... MK- -1) By Lemma A.4, we know that js = P/N
N
π
Pafe
<
2m
(48)
N
N
T
72
i=1
18

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Algorithm 7 Quantum Mean Estimation with Binary Oracles QMEBO, ( S. Bp, e)
1: Require: B, encoding a probability distribution (pi)ien on a finite set Q with cardinality N, By encoding a function f (fi)sen where f/ E [0, 1]. maximum error maximum failure probability 8 E (0,1).
2: Output: á satisfying j - p' S
3: Initialize: K = O (1))( T 0
N
4: for [K]d do
5: create quantum oracle Up with B, and obtain the following state (2:00) Ü, (0) 10): ( Ü, 10) (0) = v Ei v (i) 10] + V N= Σ ト (i) [1).
6: Attach (0) ((g+1) qubits on ) and apply B, on J0] 84 obtain (;:()) By (e:10)) |0) s(g-1);
1 By (0) 10) 00)
10) Bi(AA) (0)
Ps (b) (1) Bi(A) 10)
=|0b113
7: Apply the controlled rotation R, defined by R Biif (0) + Bi(A) (VF 10) + VI F [1)) and undo the oracle
By:
(1((2)
(B} T)(T R2) (6())
N
N
VP 1) 10) 10) (VFr10) + f11)
V 10) (VF. f(1)
1=1
P.f. 1)) 000)
0000 + VN Σ
p:(1 [Vpil1
fi) (1) 1001) + /1 pa (b) 110) (v fo 10) + - fi))
=|0/2)>
8: Apply T iterations of amplitude estimation by setting (wb) =11)(2)) U = 2//b) (49) I and P = 7 |000) (000) to
obtain fig
9: end for
10: Return: Median (14sian((4))xe(kk)
19

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
with probability least - for any > O. We proceed focus the complexity cost of Algorithm 3. Note that l E [0, 1] because Ja E [0, 1] for all 1, ..... N. Hence, further have that
N
2m
<< π
(49)
T
72
VNT
T2
In order to let j/N be c/N approximation of
Σ Pifis it suffices let
nr2
VNT +
(50)
T
N
which is equivalent to to <T - VVT N 2 0. Then it suffices to let 7 0
NN + +
A/
such that | - E
S
e/N. This implies that AA Σi= fi S E.
By Theorem A.3, we know that the query complexity of Ü, in terms of Bp is O(1). Therefore, Algorithm 3 calls Bp and
By of VNN
(VN + / N log(1/0) times each.
A.4.4. PROOF OF LEMMA A.6
Lemma A.6. QVI-2(M, c, holds that Th (Vh+1) i Vn S (V(Vi+))) for all [H] with a success probability at least 1-
Proof. The analysis on success probability is the same as Theorem 3.8 and hence we omit it here. For all E ES,aa A and E [H] we have that
(a)
PT
Va+1
c
(51)
H
2H2
2H2
This implies that
(a) +
6
PT
Vh+1
(52)
2H
h|s,a
2H
and
PT A|s,a
Vat1
S (0,)(a) S Pf Pi H
(53)
Now, for all E S,a A and h E [M.. we let
(n( (a(s,))==Ahh = r=(sa)) Pil Vh+1
(54)
Note that (T(++))) Qn f(s, h)) ((s,
= (s. h)) + PIT (1s,))). Vh+1. Therefore, for all S, A and h [H]
we have
@n.(a) - (n max (s, + tn (a), 0} (rx(s,a) + Phaaa P Vntz).
(55)
On one hand, since (a) S PT
A/s,0 Vh+1 and Vh+1 2 0, then we have
(a) Qn a) I maxffr + P Vh+1, 03 (rn(s, + PT Vo+1) = ()) + PI Vh+1 (rn(s, a) + Vn+1)
(56)
0.
On the other hand, we also have
(a) @n(s,a) = max(ra + (a). - (ra(s,a) + Ph Vn+1)
2 rn + (a) - (rn(s,a) + Pileaa Vn+1)
(57)
= (a) P Vn+1
2 H
20

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
The last line comes from Eq. (53). In summary, for all & &, and h [H], we have
e S - Qx( S. H
(58)
Hence, by letting = +(s h),, we will have
H S Vn- - (V++1) = (ftss, h1)) - Qn (s, h)) s S0,
(59)
Th (Vn+1)
H S Vn S (
(60)
A.4.5. MONOTONICITY PROPERTY OF THE VALUE OPERATOR ASSOCIATED WITH A POLICY (.) IN DEFINITION 2.
Suppose two vectors and satisfy have, for any fixed policy æ and for all S and h {H],
RRS then it implies that u(s) s u(s) for all E S. Consequently, must
Σ d'ES
Palastssns( = Σ (=lam(ss))()))((())
(61)
s'ES
Further, we can know that
((), + Σ (Nisstan(66)u(s) SEE
+ Σ Palar(sas(s'00ss) SES
(62)
By the definitions of (u) and (v), this implies that (w)] < [T)], for all s E S and h E [H]. In other words, (u) S (v). This implies that the operator T is monotonically increasing for any x and h E [H] in the coordinate- order.
A.4.6. CORRECTNESS OF QVI-2 (PROOF OF THEOREM 3.8)
Proof. We start by examining the failure probability. The approach is similar the analysis in Theorem 3.5, except that we must now account for quantum oracles that can fail. To address this, we use fundamental properties of unitary matrices, particularly a quantum analog of the union bound, which states that the failure probabilities of quantum operators (unitary matrices) combine linearly.
In line 5, since B is constructed using QMEBO with a failure probability Ç, it is within 2AC of its "ideal version." "
Specifically, this means that there exists an ideal quantum oracle Bideal Shie
Vh41 - e/2H, where PT h|s,a Vh+1 encoding H PT h|s.a
< 2AC. Since B B@n.. is formed using one Q By applying the quantum union bound and substituting the definition of Ç. this shows that the quantum operation executed by QMS is (čv log(1/6) 4AA5 = 5/SH)- close to its ideal version. Consequently, the output of QMS is incorrect with a probability of at most 8/SH. Given that QMS is invoked a total of SH times, the overall failure probability is bounded by 6, as ensured by the standard union bound.
satisfies pT N|s,a Vh+1 PT Als,a Vn+1
S {c((2H2), such that Bidcal
B
call each Br... and Bi, BI it is within 4AÇ of its ideal counterpart Bideal
In line 5, we apply QMEBO to obtain an approximate value (o) H of the inner product PT h|s.a Vn+1. Theorem 3.7 guarantees the output in the line 5 satisfying (a) H + c/2H2 - P Vatal S c/2H² for all s S,a E A and h E [H]. This implies that (a) -P Vhtal S E/H. Hence, it holds for all s S and a A in every loop h [H] that
(a) Q7( = (n(ss a) + (a) (s) + PT 1h+1)
(a) P (Vi+1 Vn+1) - PfT Vn-1|
(a) - -Pill Phla,a Pntal + (i - Pntz)l
(63)
max Vi+1 (s)
H
eeS
c
+ Vhtt - Viitz 10
H
21

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Furthermore, we have
|1 1/
nn (s), - max
(%
aEA
00
max aEA
Qn)
max Qh (s,a)
aEA
(64)
max 1 (a) Q% aeA
S max max (a) - Qi sES aed
|h+t - Vi+t1
H
Since it holds that VH(()= = Vit(
for all E S, we can induce that
1 V
H h)c
VH
(H - h)e
(65)
H
Then, we know that [% Vi S c for all h E [H]. In particular, it implies that (s) - cs Vs(s) for all s E S and E [H].
Now, we proceed to prove the (s) < (s) (s) for all s and h E [H]. By Lemma A.6, we know that Vn S &h (Vn+1) for all h E [H]. Therefore, 1 < [T ( = [T H (0)], = r H - 1)) = - By the monotonicity of the operators Th where h E [H], have V., 7 (V++1) I (V S ... V for all
h E [H]. Due to the definition of V2 (s). we must have (s) max VTT 2 (s) for all s E S and h E !].
A.4.7. COMPLEXITY OF QVI-2 (PROOF OF THEOREM 3.9)
Proof. We first assume that all QMS and QMEBO are correct, up to the specified error, because the probability that this does not hold is at most 5. Let be the complexity of QVI-2(M,,, 5) as if all QMS and QMEBO are carried out with maximum failure probabilities set to constant. Then, since the failure probabilities are set to Ç 5/(4cHSA1 log(1/))), the actual complexity of QVI-2(M,,, is
o o (CooogSAA'5 log(1/6)/8))
1/()).
(66)
Now, we check each line of QVI-2(,,,,,))) 6) to bound C.
In line 4, we encode the vector V = V H to an oracle B This process does not need to query OoM and only needs to access the classical vector Vh+1-
In line 5, we implement QMEBO to compute an estimate of pT aaa,a Vi4a with error e/2H22 Besides, the correctness analysis shows that (+) S V (s) S H for all s E and the definition of (a) of QV12 implies that 0 I V%( for all E S, so it also holds that 0 ()) (s) < 1 for all E S and h [H]. By Theorem 3.7, we know that QMEBO needs O (V//(12// /e
OOVO0((/// queries to OΩM for each E S at each time step h E [H]. provided 0 < E < 2 Since we have assumed that e < H on the input e, so this holds.
/H²/e))
In line 6, BQ... needs to call B and Bt Sn.. once. Then the query complexity of B in terms of B is O
In line 7, we use QMS in accelerating the searching for the optimal action its, h) for all E S. By Theorem 3.4, QMS requires OVVA) queries to the oracle B&_.. for all s E S and h E [H]. Therefore, after summing up // iterations, it induces an overall query cost of
VSH²
( VAH
C C-0 S VA. H.
(67)
22

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Combining the above equation with Eq. (66), the overall quantum query complexity of e,
o S VAH log(S Log(SA46H/6)
(68)
B. Generative Model Setting
B.1. Correctness and Complexity of QVI-3 (Algorithm 4)
B.1.1. PROOF OF LEMMA B.1
Lemma B.1. @VI-3(M,,,8) holds that T (Vh+1) least 1 - 8.
Vn T (V++ for all [H] with success probability
Proof. The analysis of success probability is the same as Theorem 4.3 and hence is omitted here. We proceed to show the correctness of the claim. For all s E S, a E A and h E [H] we have that
(a) + 2H
P Phls,a Vn+1
(69)
2H
This implics, for all s E S,a E and h E [H],
PT Vat1
hlaa
H S (0) S PT Piiaaa Vnt1-
(70)
Now, for all E S,a A and h E [H], we let
Qn(s,a) = as) + PT
h|s,a Vata and (4()) = max Qn( aEd
(71)
Note that (V (s, 1:) (s hi)
PT Ma..((a Uh41. Therefore, for all S, A and h [H].
we have
@n,((a) - (s, (rx zn.s (a), (ra(s, + Phla,a Pila,a Vn+1).
(72)
On one hand, since 2/ (a) pT h/s,a Vh41 and Vh+1 O. then we have
(n)(a)) Qn a) I (m, + P.T s.a Pht1, 03 (r)(s, + Phiya Vo+1) = (s) + Ph Vh+1 - (ra(s, a) + P.T Pi Vnt1)
(73)
0.
On the other hand, also have
Qn,a(a) - an = max + (a), (a,
(rn(s, + Po Ph+1),
r)(ss,)) a) + (a) (ra(s, + Phla.a Vn+2),
(74)
(a) h
Vn+1,
H
The last line comes from Eq. (70). In summary, for all s E S,a E A and h [H], we have
E < (n) as) 50,
(75)
H
Hence, by letting a = #(s, hi), we will have
< Vn - T (V++z) (n, - (s, S0,
(76)
H
23

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
(V(++t) - s Vn s (Va+1))
(77)
H
B.1.2. CORRECTNESS OF QVI-3 (PROOF OF THEOREM 4.3)
Proof. We start by examining the failure probability. The analysis is similar to Theorem 3.8 where we need to consider quantum oracles that can fail. Again, we use the quantum union bound for quantum operators here.
In line 5, since B is constructed using QMEI with a failure probability Ç, it is within 2A of its "ideal version." "
Vn+1 - -e/2H, where pT h|a,0 Specifically, this means that there exists an ideal quantum oracle Bideal encoding PT hle,a satisfies
V4+1
I. Nlx,a Vh+1
P.T h|s,a Vn+1
S </(HH,, such that Bidcal Bzz..
2AÇ. Since B is formed using one op
1000
call each to B.n,. and B it is within 4AÇ of its ideal counterpart Bin!! By applying the quantum union bound and
substituting the definition of Ç. this shows that the quantum operation executed by QMS is (ēv (cVAloge log(1/)) -4AÇ = 6/SH)- close to its ideal version. Consequently, the output of QMS is incorrect with a probability of at most 6/SH. Given that QMS is invoked a total of SH times, the overall failure probability is bounded by as ensured by the standard union bound.
In line we apply QME1 to obtain an approximate value zh,s (a) of the inner product PTT Ph|s.a Vh+11 Theorem 4.2 guarantees
the output in the line 5 satisfying (a) Masa Vu+al S e/H for all s E SS E and h E [H]. Hence, it holds for all s E S and a E A in every loop h E [H] that
(a) Q7(ss
= 1n + (a) - (rn a) + PMja,a Vitta)
(a, hisa Phina(Vin (V Vht1) PTT h/s,a Patal
< (a) -Phlea 1n+1| + |Pile. (Vi+z2 - Vn+1)
(78)
E + max Vn+1(s) Vs)
I H
= c
+ | - Vi++1 //
H
Further, we have
1/ - V/
Qn (f(s
- max Q7
EEA
max Qn,((a) aEA
max 07 (s,a)
aEA
max aEd
Qn, (a) (h a))
(79)
< max max Qn, - (2() SES aEA
|h+1 - Vhi+1 ll..
Since it holds that (s) = (s) = for all s E S, we can induce that
| - v
(H h)c
+
VH
V
(H hhe
(80)
H
H
Then, we know that V, V for all h E [H]. In particular, it implies that Vi((s) - e S Vs(ss for all s E S and
E [H]. Now, we proceed to prove the (s)) I V for all s E S and E [H]. By Lemma B. we know that V/1 S
T (Vn+1) for all h E [H] Therefore, 1 < [T H (VV)) = IT = rи (
1)) = V (s). S ... S V for
By the monotonicity of the operators T where [H], we have V/ S (Vh-)) & TT
24

---

Quantum Algorithms for Finitc-horizon Markov Decision Processes
all h [ Due to the definition of V (s). must have (i maxxen Vg (s)(s) for all and h [M].
B. 3. COMPLEXITY OF QVI-3 (PROOF OF THEOREM 4.4)
Proof. We first assume that all QMS and QME1 are correct, to the specified error, because the probability that this does not hold is at most 6. Let C be the complexity of QVI-3 c, 5) as all QMS and QME1 are carried out with maximum failure probabilities set to constant. Then, since the actual failure probabilities are set to ( = 34c4AAAA log(1/6)), the actual complexity of QVI-3(M, c, 6,
o (( (og(1/))/))
H/8)).
(81)
Now, we check each line of eVI-3(M,,,,) to bound C.
In line 4, we encode the vector V to an oracle B This process does not need to query G and only needs to access the classical vector V4+1.
In line 5, we implement QME1 to compute the approximate inner product PT h|s.a Va+1 with error c/H. Besides, the correctness analysis shows that it holds that (s+1(s) I ( & H for all E S and E [H] by Theorem 4.3 and (8) for all S by the definition of itself, (a) and (a) in QVI-3. By Theorem 4.2, we know that QME1 needs O OHH2/E+ /H²/c) O(H2/e)) queries for each s S, provided 0 e H² Since have assumed that H on the input e, so this holds.
In line 7, Br... needs to call B..., and B!., once. Then the query complexity of BQ in terms of B is O(1).
In line 8, we use QMS in accelerating the searching for the optimal action A(s, h) for all s E S. By Theorem 3.4, QMS requires O(vA) queries to the oracle B for all S and [H]. Therefore, it induces an overall query cost of
C c=o S.
412 ) -0
) SVAAl)) (
(82)
in H iterations. Combining the above equation with Equation (81), the overall quantum query complexity of QVI-3(M,,
of SVAH (og(SAA SAA 1-5 H/8)
(83)
B.2. Correctness and Complexity of QVI-4
Lemma B.2 (Upper Bound on Variance (Sidford et al., 2018)). For any policy π S x [H] + it must hold that
I
Σ
II
PMT
(v
S H3/2
(84)
M=A
\=++1
where one (V/+1) PM. (Phr (2.V)441)2
B.2.1. PROOF OF LEMMA B.3 Lemma B.3. For all & E [K] and h E [H), Algorithm 5 holds that
VEL S m < Vr
(85)
Qk E Q < Q
(86)
with probability at least
25

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Proof. We first consider the success probability. Note that all the quantum subroutines QME1 and QME2 are implemented with maximum failure probability Ç 8/4K HSA. In total, QME1 and QME2 are implemented 4K H.S.A times in line 6, 7 and 9. By the union bound, the probability that there exists an incorrect estimate is at most 8,
Now, we proceed to prove the inequalities
V S A S V
(87)
Note that the second inequality is trivial due to the definition of Vi max V Therefore, we only need to prove the inequality Va, S V for all h E [H] and & E [K]. In fact, it suffices to show that for all k E [K]. we have
Ve.k S THy (Vi,
(88)
First, by the definition of 2i,h and Ir.h in line 7 and line 9 respectively, we have, for all (s,a) E x A.
TKA(s, a) PT V(() k,h+1
(89)
(8, a) S Ph 8.0 (Vi,n-1 k,h+1)-
(90)
We continue to prove Eq, (88) by induction on We first consider the base case where 0. For any h E [H]. if there exists some 8 E S such that TA (s, h)) * T (0) (s, h), then we have
(s) = (s)
Qu. (s)
max (e, li)) + Tr, (s, (<(s,))) (s, + ga, (x,
max (s (s,, h)) P (s.h) (0))
PsT Phlosmatadt (V (.(0) vxn+1).03
kh++1
(91)
(6( max nh (s, hi) + P (s)) Ve,+i,00 0}
= (s hi) + PT
(ll. Ve.+11
[T (Vi,t+))s
(0) (s, h). then we have Vs,n(s) V((0(s) (s) = -Vol (s) = 0. Since If there exists some E S such that (s h) = T
ViL (s) 2 ( = 0 (s) 0 for all E S, then we must have Vs, 0 S [T (Ve,4+ )]a- Therefore, when 1e 0, holds that Vk. I T (Ve,t+1) for all h E [H]. We assume that for any k' 0, 1...., . 1, also holds that Vi I T (+1) for all h E [H]. Next, we show the above statement holds for k' = k. In fact, if there exists some E S such that T& h) # (0) (s, h). then we also have (s) S (V )s by following the same analysis in the case of k- 0. If there exists some E S such that T& (s ft) T (s) h),, then we have
(0)
(s) vila (s) Vx- < [T', (V6-1A++)]] = [Th. (VR4+1)), s [Thh (V&.t+1)] = [T (Vi,n+2)]
(92)
The first inequality comes from the induction hypothesis. The second inequality comes from the fact that V.h++ S Vi,4+1- The last equation comes from the fact that (s, h) = (0) (s. h) = (s, Therefore, we already showed that VK S The (V),++1) for the case k' and finish the induction. Since we have Vi.A S Th (Vn,a+1) for all E [K] and E [H] and VI,H(s) = 0, Vs E S, then for any fixed E [K], Vk. S T (... TH-- (V..H) = VT for all h E [H].
Furthermore, since we already proved Vi,A S TTTH for all h E [H] and k E [K], we also have, for all (s,a) E x A.
as I (n(ssa) a) + al VEA+1 S ()) + PsT hlaaa h4t 2 (s. (h,s.)).
(93)
The first inequality follows from Eq. (89) and (90).
26

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
B.2.2. PROOF OF LEMMA B.4 Lemma B.4. For all k E [K] and h E [H], Algorithm 5 holds that
Vi - S Vi,N,
(94)
Vn cu S Qk,k.
(95)
with the probability at least 1--d 6.
Proof. The success probability analysis the same Lemma B.3, we omit it here. We continue use induction on l: prove Eq. (94). First, we consider the base case where k 0 and show (94) holds for all h [H] By the definition of 0k,h and f in line 7 and line 9 of QVI-4, we know that, for all (s,a) E ESxA A.
LA, a) 2 P (-(0)
A/s,a k,++1 2cH 2cH- ev yk, (s, a) + 4b,
(96)
(s, a) 2 Alo.a (Vi,t+I vhh+t) 2cH
pl
(97)
We define (s, = 2cH-1G c + 2cH 1.6 (knA + 4b. Then, we can show that
Q7 - Qk.h Th + PAVEtzI max(ra + The + Ik. 0}
PaVi+1 Ih.h Ik.h
S PAVi++ - PAVentt1 + 2cH cx + 2cH 1.5 1..../..vo Uk - 4b
(98)
=Pa(Vi+1 Vks+1)) EKA
=PAV(Q++)) PAVENT11 Ek,
Since we have V ((x,A++1 I V4,44 then holds that
Qh Qk PAV(Q(41) PA. (.V((k,)+t) + Ek,h
PF Uh+1 (P.V(Qu. Ek.h
(99)
P 1h+1 P Qk.t+1 Ek,
The second line comes from the fact that (s) = i x (s, for all s S and h E [M]. The last line comes from the fact that n" (s, h)) may not be same as arg max.e Qu (8, a) for some s E S. Since must hold that Vi((s) = 0, Vs and we require that V (s) Vs S. then have Vi((s) V*,H( 0, Vs e By solving the recursion on Q7, QK, can obtain
0h -
Σ h
II M1h++
PT
ERNN
(100)
where (s, a) = 2cH--es
Wk. (8, u) + for all (8, a) E A. Note that a product over an empty index set evaluates to 1. Now, we try to bound V (s, a) + 46 for all (s, a) E x A. By the definition of yk. a) in line 6 of QVI-4, we know that there exists b' satisfying |b| < such that
V (s, a) 4b max (Phi)s,a (V
+1 )2
(Ph [0 k,,++1 - + v4b
S (V + 5b + 2bH PT (0(0) 1/2
(101)
(o (V +76) 1/2
Since it holds that ())
1 = for s E and W [H] when 0. then of (v-(0) (v 0. This implies that
27

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
( + +44 4b S 7b. Then we can show that
1-1 h
QUA S
π
Pr
2cHl' lex + 22/l Wh.N 4b
1/=h W11+1
< 20E + 2cH
0.5.v. ev -05
(102)
v 2CEk + 2CEV/T
$ 2c + 4ev 7b Ek
S Ek
The second line comes from the fact that
Σ#= Il P.r
S H - S H for all h E [H). The third line comes
from the fact that H 2 1. The fourth line comes from the fact that E E 2c; = 2eg- = 2H.. The last line comes from the fact that c = 0.001 and 1. Therefore, we have (s, 2 v(Qu,)(()) = maxaE Qa, (8, a) 2 maxae (Q% a) - -xx] Vi (s) EK for the base case k
Now, we assume that for any k' 11...,, k 1, it also holds that (s, (s) c for all h H. Then, proceed to prove the claim for the case of k' = k. In fact, the analysis for the case of k' = k is quite similar to the base case, except for the part of the upper bound for / (),AArss a) + 4b. We can show that there exists a b' satisfying [b'| S b
V (s, a) + 4b s max (Pi (V (0)
k )2 + (Ph 120) kht+1 H/H22 + 4b) 1/2 v 4b
s (o (V((0) k.h++1) 5b + +bH -p (()) 1/2
Pi k.(+1))
S (o
(0) (V +7)) 1/2
(103)
S on (V + vb
S ow + oVVi k, - Vi++1) + VTb.
The third line comes from the fact that (0)
k (s) H for all s S. The fourth line comes from the fact that Va + S Vā + Vb when a, b 2 0. The last line comes from the fact that, for any random variables X and Y, we must
have o² o²(X +Y = Var[X + V] Var[X] + Var[Y] + 2Covv Y & (v Var[X]] / Varl(Y)2 = (a(X) + aV))). Note
that (V +1 Vi++1)= S (v +1 1. = =1|V2-1,441 Vi+1ll. Il 6 = 26 for all h E [H]. Therefore,
we can show that
h II
0h Qk
Σ M=h
P.
(20H c + 22H 1.5 c.5.c.//v/ Vukk 4b
Mzh+1
H-1
N
20ck 2cH -cHH-1.5
1.5
II P.
(o(Vizi)) (
+ VW.4) v7b)
W=h
ii=h11
N
< 20ck 2cH 1.5
II P..) vimh11
PT (OCVREE) 2cx + V7b)
(104)
Wmh
20E# + 20E + 2cH 0.5
(2Ex + VTb)
< 20 1
v7) 242+2++7)
The fourth line comes from the Lemma B.2 and the fact that E (
[ p.
< H h < H for all h E [H].
The fifth line comes from the fact that we require the input 6 (0, / H.. The last line comes from the fact that e = 0.001.
28

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Therefore, we have (*))(s) 2 (+) A (s, (Q - -ex] (V) cg for the case of k = k.
B.2.3. CORRECTNESS OF QVI-4 (PROOF OF THEOREM 4.5)
By combining Lemma B.4 and Lemma B.3, we can obtain that, for all & E [K],
V c S Vi.h S V S V
(105)
Q c I Qk S 0h I Uh
(106)
with probability at least 1 - 8. When k= K 1 flog2 [H)e]] 2 logz ft/e), En = H/2 < e. Therefore, it implies that
V < V/ - 6K-1 & VK = V/ s 1//= = =V;;" S V/n
(107)
0% E S 0% EK-1 S QK-1, = Qn S &Q¹= Q S &Qh
(108)
with probability at least 1-d 8.
B.2.4. COMPLEXITY OF QV1-4 (PROOF OF THEOREM 4.6)
The success probability analysis analogous to Lemma B.3. Hence, we omit here. We first assume that all estimations are correct, up to the specified error, because the probability that this does not hold at most d. Let be the complexity of QVI-4(M, e, 6) as if all estimations are carried out with maximum failure probabilities set to constant. Then, since the actual maximum failure probabilities are set Ç 5S(4 the actual complexity of QVI-4(M,c,0) is
Proof.
(109)
Now, we check each line of QVI-4(M,,, 8) to bound C.
In line 6, since we have 0 < k. (s) Vi-1 S (s) S H for all k > 0 and 0 v( k
(8) = VA-1A41 s
(s) (s) S H for all E S when & = O, therefore, we can use quantum mean estimation algorithm QME1, which induces a total query complexity in the order
KHSA H2/b H2//++H///0 (2/ O(SAHH))
(110)
Now, we focus on line 7. By the definition of yk, a) in line 6, we know that there exists a D' satisfying |b/| S such that
(8, a) 2 max { pT (v
M/s, 2 - 2--
- (P V-10)
k, + HH/HH)² .}}
pf P PV =+++1)²== - b k + HH2
(0)
1(0
(II1)
(V (8.0) (e.0) 6- (2b// HH) hls,a khh+1 (61)
PT ((0)
This implies that
[V (1 S Ik,, + +b+ (2b/H) n|s,a kkht1 + +1/H² S ( a) + 4b.
(112)
The last inequality follows from b- = 1 and (0)0) k (s) = V S 1 (8) S H for all s E S when k 2 1 and (0)
1 (s) 0 for all E S. We also note that, since we have yk (s. a) > 0 (by the definition in line 6), then it holds that 0 < cH5 / n (8, a) + 4b < 4 (8, + 4b. Therefore, we can use quantum mean estimation algorithm
QME2 with error eff 1.5 / M a) + 46 and variance upper bound set to (s, a) + 4b, which induces a total query complexity of order
KH
Σ
w(ss a) log (w(s, a)) O
(113)
(Ma)ESxA
29

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
where w(s a) = (v (,, + 4b) (cH--1., / 4b) = -
In line can bound 0 < (8) V(.0) k S (+) (0) (s) ( 1i+ S ck-1 2 for
all E and & 2 1. When &o since (o 2 vol ( = O, then we also have 0 - Vo,++1 1/ v
(8) ( H co for all s S. Therefore, we can quantum mean estimation algorithm QME1 which
induces total query complexity of order
26k cH-1ck
2
KHSA
+ V
(KSAH))
(114)
cH cc
Therefore, we can show that
= O /e Hd log2 = -(SA(H22 / log" (HL.5/)))
(115)
Then the total query complexity
( /e+ Hd) log (
(116)
B.3. Lower Bounds
B.3.1. INFINITE-HORIZON MDPS
Preliminaries of infinite-horizon MDPs: An infinite-horizon MDP is formally defined as a tuple M == where S is a finite set states representing the possible configurations of the environment, and A is finite set of actions available the agent each state. The transition probability P(s'|s.. |s, a) specifies the likelihood of transitioning to state s' after taking action a in state 8, ensuring that Eves P(s'|s.a) a) for all S and a E A. The reward function r(s, a). bounded within [0, 1], assigns a scalar reward for executing action in state Finally, the discount factor y E [0, 1) determines the relative importance of future rewards compared to immediate ones, with I = T Given such an MDP, the agent's 's objective is to select actions that maximize the expected sum of discounted rewards over an infinite time horizon. The primary goal is to compute a policy π : S + AA that specifies the action = rss) the agent should take in each state s E S to optimize its performance with high probability. For a given policy π, the vtaue function (or V-value) V" > [o, r] and the state-action- value function (or Q-value) Q" :S A [0, r] are defined as follows:
(T(() =
7 Ar(s az)
T, 80 =
(117)
Q= = E Σ r'((se a4)
80 8,00
(118)
policy an optimal policy x² if V max V V"" where is the space of all policies. For simplicity, we denote V = Va and Q" Q"
The primary computational objectives in infinite-horizon MDPs are as follows: given an infinite-horizon MDP M, an approximation error c, and a failure probability 5, the goal is to compute <-estimates म, V, and Q such that v
Optimization goals in Setnite-horizon MDPs:
y I oo Se, [V - V* oo S and Q @' S e with a probability of at least
1-6.
Classical generative model for infinite-horizon MDPs: We denote the classical generative model for infinite-horizon MDPs as G. Assuming access G, one collect N independent samples
L/ itd. P(-18,a), i= 1,..., N,
for each state-action pair (s,a) S A.
30

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
Theorem B.5 (Classical and quantum lower bounds for infinite-horizon MDP (Wang et al., 2021)). Fix any integers S, A 2 2 and & E (0.9,1) Let r (1-7)- 10 and fix any (0,T/4) There exists infinite-horian MDP
M (.T.P, with S states, A actions, and discount parameter such that the following lower bound hold:
Given access to a classical generative oracle G, any algorithm that computes an e-approximation to Q", V or must make Q e- queries.
Given access to quantum generative oracle & defined as
g: 2
8s)
(P(ss , WES
Σ
(119)
where (ex) are arbitrary auxiliary states, any algorithm that computes an e-approximation to Q" must take Di SALLS queries and any algorithm that computes an c-approximation to V or nt must take D2 Svart. queries.
B.3.2. FINITE-HORIZON MDPS
Lemma B.6. Let S and A be finite sets of states and actions. Let H 0 be positive integer and (0, be error parameter. We consider the following finite-horizon MDP M (Ph)iep - H) where Ph = P E AxS and Tı = [0, 1]SA A for all h E [H].
H-11
Gäven access classical generative model, any algorithm K,, which takes M input and outputs value function
Vo such that Vo- Vio 1oo
S e with probability at least 0.9, needs to call the classical generative oracle at least
SAH
Ω
(120)
log (E-1)
times on the worst case of input M.
Given access quanium generative oracle G defined in Definition 4.1 any algorithm K, which takes M input and outputs a value function Vo such that [ - Vo generative oracle least
S with probability at least 0.9, needs to call the quantum
SVAH1.
Ω
(121)
clog (E-1))(e-
times on the worst case of input M.
Proof. We first introduce some definitions about infinite horizon MDPs. Let 80 E S to be a state. Suppose we have an infinite-horizon MDP M = A, P, F, with a quantum generative oracle, where S = S {5o} to be a subset of S and y E [0. 1). For better differentiation on the notations between horizon and mnfinie-hhorizn MDPs, let V R represent the optimal V-value function of M. First, we define a Bellman operator T for the infinite-horizon MDP M satisfying, for any S and S,
T(u), max F(s, a) + ((ss(ss,au(ss)) a
(122)
N'ES
Note that for any E $ satisfying u(s) < u(s) for all s E S, we have T(u), S T(e), for all E S. This is the so-called monotonicity property of T. Besides, it also holds that T(V*), = (s) for all s E S.
Now, we proceed to prove that obtaining an 2<-approximation value of 8 for any infinite horizon MDP M can be reduced obtaining an e-approximation value of Vi2 for finite horizon MDP. We consider the following finite-horizon MDP H-1
k==n H)) where Pt. P E SxXAS and ra [0, SSAA, Besides, the time horizon H satisfies H [2(1 > (og(22-1)) = @((1 - >) -1 log(e Besides, under any action a E A A. there is --7)
M (S. A. (Px k= (rr), H-1
31

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
probability for each state & transition so and > probability follow the original transitions in M. However, when the agent is in so, it can only transition to itself with probability 1, matter which action A it takes. Hence, 80 is an absorbing state in M. Overall, we have the following definitions for the transition probability kernel P in M.
Vs,8' ES, E A, s,a) a) = 7 |8, a); P(sols, a) 7),
(123) (124)
P(s'|so s0, a) 0, P(sols0: a) =
Besides, we define r(sp, a) = 0,,(8, = F(8,a) E [0.1] for all & E $ and a E A.
Now, we proceed to prove that Volls VVls-~v'l ---l__ S c, i.. (s)
(*)) S e for all & E S. First, we note that - max.cerrsss a) S V*. Then, by the monotonicity of the T operator, we have T(V S T(V*)= (*(s) for
all E S. In fact, by the definition of in M, we have
Ys 8, TVV max aEA
F(s, a) +7 E
max aEA
((s a) + Σ
P(suls,a)
(125)
e'ES
max aEA
r(s,a) +
Σ
P(s'ls a) V)
s'ES
The second line above comes from the fact that V ( = maxae r(so, a) = By induction, we have Ví (sn) A(Xo a) + P(sul So. a)Vii (su) = 0 for all h E [H]. Hence, we have V==2(s) I (*(s) for all E S. By induction, we have (s) S (s) for all [H] and S. In particular, we have V/ (s) S V*(() for all s E S. Let
ā* E AS be an optimal policy for the aninite-horizon MDP M. However, मे E (S((HH where oT., h) = a* for all e [H]. may not be an optimal policy for Enite-horizer MDP M. Then we have VO8 (s) S (s) for all S. In fact, for any
E S, we have
(x))) = (s))*(())) + Σ
+...
Σ pd p0 (s)s,
E'ES
eEES
= =(( (r (s)) + Σ
+
Σ
(126)
8'ES
eEES
H
where V is the V-value induced by the policy म" over H iterations. Note that for any policy म for the infinite horizon
MDP M. - - レー
S
x
V0r v= S *
Vo + | s 2exp(-(1 - 7)4) /(1 - 7). The last
- 1/(11 7) and v < 1/(1 - 7). Besides, combining the fact that log(n) S 7 1 for all E 1) and exp(x) is monotonically increasing, we can induce the inequalities k log(n)) < -k(1 7) and n* = cxp(lk log(7)) I exp(-k( - 7)). Then, Vc > 0, it suffices to let k 2 1og((2((1 - 7)()/((1))))) - 7) so that
inequality follows from
V -v- S c. In fact,
2 (1 7)6
1
1
(2)
2
log
log
+ log
7
1 ?
1 1-
1
2
log(1
7) + log
1 γ
(127)
1
2
< 1 7
7 + log
2
2
<
log
1 ?
32

---

Quantum Algorithms for Finitc-horizon Markov Decision Processes
The third line comes from the fact that log(1 - 7) -7, Vy E [0, 1). The last line comes from the fact that (2gg) 1, Ve 1/2). Since we have H- - log ( and #* is optimal policy for M, then we must have (s)
V (s) 2 Fa (8)
(s) - Therefore, we have (*))s) - (s) S (*(s) for all S, which implies
Vills - v- E.
Therefore, an c-approximation of Vi will give an 2c-approximation to V Specifically, we let Vo be an e-approximation of Vo then
Voos v-| < Vols- Volss ac + Voo1s V
< Vo - Vo
+ Volss VM
(128)
2ec
Therefore, obtaining 2e-approximation V for M with a quantum generative oracle reduced to obtaining e-approximation value Vo- for M with a quantum generative oracle. Then, implies that the algorithm K. inherits the lower bound for obtaining 2c-approximation V for M with quantum generative oracle. Note that M is time-independent MDP. Then the quantum generative oracle G is the same as & defined in Theorem B.5. By Theorem B.5, we know that the lower bound for obtaining 2e-approximation V for M with a quantum generative oracle is ( /AS55// This implies the quantum lower bound for finite horizon MDP M to obtain an e-optimal value function Vo is ((Sv 1.5 //sliss////////e ((elog".' (E
Note that the above content also shows that obtaining 2e-approximation V for M with a classical generative oracle reduced to obtaining e-approximation value Vo for M with classical generative oracle. By Theorem B.5, we know that the lower bound for obtaining 2e-approximation V for M with classical generative oracle is ((SAAI//e /e). Therefore, the classical lower bound for finite horizon MDP M to obtain c-optimal value function Vo is R(SAH) ((2 log (e- ()))
Lemma B.7. Let S and A be finite of states and actions. Let H be positive integer and (0, be error parameter. We consider the following finite-horizon MDP M (S.A, (Pa) H-1 H H) where Pa P RSXAS and = E 1JSA for all h E [H].
Given access to a classical generative oracle, any algorithm K., which takes M as an input and oulputs a value function Qo such that Q Qil with probability least 0.9, needs call the classical generative oracle least
SAH 2 log log"
Ω
(129)
(e-1)
times on the worst case of input M.
Given access to quantum generative oracle G defined Definition 4.1 any algorithm K. which takes M as an input and outputs value function Qo such that Qu generative oracle at least
Qi -0
with probability least 0.9, needs call the quantum
SAH
Ω
(130)
e elog 1.5 (E-1)
times on the worst case of input M.
Proof. Following the same idea in Lemma B.6, we consider an infinite-horizon MDP (8, with quantum generative oracle, where = S \ { to be subset of S and 7 E 10, With slight abuse of the notations for the infinite-horizon MDPs, we let V' E R and Q" E SxA be the optimal V-value and Q-value functions of M. Now, we proceed to prove that obtaining an 2c-approximation value of Q' for any infinite horizon MDP M can be reduced to obtaining an e-approximation value of Qī for finite horizon MDP. We consider following finite-horizon MDP H-1 # H) where Ph P RSxAxS and ты
S Besides, the time horizon Hl satisfies H = [2(1 - 7) log(e-)) ')] = @((1 ->) -og'' ')). Besides, under any action a E A = A, there is (1 (1-7) probability for each state s transition to so and y probability to follow the original transitions in M. However, when
M (S, A, (Ph (Ph)A=
33

---

Quantum Algorithms for Finitc-horizon Markov Decision Processes
the agent is in so, it can only transition to itself with probability 1, no matter which action it takes. Hence, 80 an absorbing state in M. Overall, we have the following definitions for the transition probability kernel P in M.
Vs, E S E A,P(s")s,
s, a) = -P(s'(s, a), P(sols, a) = (1 - 7),
(131)
P(s'|so 80, a) 0, P( (()0 = 1.
(132)
Besides, we define r(so, a) = 0, r(,, -((,, F(s, a) [0, 1] for all & (Sndd a E A.
Now, we proceed prove that Q0l6KA- - i.e.e. ()) (s) S for all E 8 and a E À -A. First,
we note that Qir-1 = r(s,a) 5 Q" by the definition of Q", In Lemma B.6, we see that it holds that (s) I V*(s) for all h [H] and s E S, and v 0 for all h [H]. Therefore, we have,
(s, = r((,a)+ + Σ (1o41,
e'ES
= = + Σ
P(5'ss,)) + P(so ls, a)+ (80)
SEE
= + Σ P(d1(s,)\Vi++((3
SES
(133)
=r(ssa) +7 Σ
P(sd
s'Eš
<r(s,a) +7 Σ P((((s,0)v*(())
''E8
= (s,
for all h E [H - 1] and (s) E A. In particular, Qī(s, a) S Q" a) for all a S and a E A. Let E AS be an optimal policy for the infinite-horizon MDP M. However, ASx(H), where #(, = #* for all E [H), may not be an
and
optimal policy for finite-horizon MDP M. Then we have Q (s,aa a) s a)) for all E S and A. In fact, for any E S, we have
=((s,))
+ Σ P(s (() + +... +
Σ
pH (s))s,,
s'ES
"ES
= =((s,a)
Σ
P(s)s, +... + H
Σ
(134)
s'eš
s
Q
where QH is the Q value of the infinite-horizon MDP M induced by the policy 7* over H iterations. Note that for any Q-
policy ă for the infinite horizon MDP M, ||ē
Q Q" 22xpp 7)1)/(1 7). Then, Ve, it
20
suffices let l: 2 1og(2/((11 (((((11)))))) 71 - 7) so that
0%
S c. In fact,
2
1
2
log
log 1 1->) + log
-
1-7 7
(1 - 7)c
1
?
1
2
log(1 7) + log
I 7
(135)
1
(2)
<
7 + log
1 7
2
< 2
log
7
The third line comes from the fact that log - S y, Vy E [0, 1). The last line comes from the fact that log(2/e) >
1, Ye E (0, 1/2). Since H [2 _ log (2)1 and #* an optimal policy for M, then we must have Q (8, 2
34

---

Quantum Algorithms for Finite-horizon Markov Decision Processes
(v) - Q² (8, a) Therefore, we have (x, - S Qā(s,a) (s, for all S A, which implies
- S Therefore, an e-approximation of Q2 will give an 2c-approximation to Q*. Specifically, if we let 2o be an e-approximation of Q6. then
1 0- - - + -ilsss -
- Q0 Qill +loilsxa - 0- 0%100
(136)
S 2e.
Therefore, obtaining 2c-approximation Q" for M with quantum generative oracle reduced to obtaining e-approximation value 2 for M with a quantum generative oracle. Then, implies that the algorithm K. inherits the lower bound for obtaining 2e-approximation Q" for M with a quantum generative oracle. Note that .M is -nneeindependent MDP. Then the quantum generative oracle G same as 9 defined in Theorem B.5. By Theorem B.5, we know that the lower bound for obtaining 2e-approximation Q* for M with a quantum generative oracle is ((SA /e). This implies the lower bound for obtaining c-optimal Q value function Qo of finite horizon MDP M is Q(S /(c log (c-)))
Note that the above content also implies that obtaining 2--approximation Q" for M with a classical generative oracle reduced to obtaining e-approximation value Qi for M with classical generative oracle. By Theorem B.5, we know that the lower bound for obtaining 2c-approximation Q" for M with classical generative oracle is Q(S /c). Therefore, the classical lower bound for finite horizon MDP Q2SAH* log (e=)))) 1))).
B.3.3. LOWER BOUNDS FOR FINITE-IIRRIZON MDPs (PROOF OF THEOREM 4.7)
Proof. Since time-independent and finite-horizon MDP is special case of time-dependent and finite-horizon MDP, know that the lower bound of obtaining an c-approximation Vo of V/ for time-dependent and finite-horizon MDP M with a classical or quantum generative oracle inherits the corresponding lower bound in Lemma B.6. Besides, obtaining c-approximations Vn of Vi is a sub-task of obtaining c-approximations V, of VI for all h E [H]. Therefore, the lower bound of obtaining e-approximations V/, of VA for all h E [H] for time-dependent and finite-horizon MDP M with access classical quantum generative oracle inherits the lower bound of obtaining c-approximations V. of Vi with classical quantum generative oracle. Therefore, algorithm I. has the desired classical and quantum lower bounds for obtaining e-optimal V value functions (V.) With Lemma B.7, similar idea also applies to obtain the classical and quantum lower bound of obtaining e-optimal Q value functions ((=
Suppose KC can output e-optimal policy म for finite horizon and time-dependent MDP M, then the corresponding V-values (V) h= == (V*+) #-1 T==0 induced by ă are c-optimal. Therefore, K. has the desired classical and quantum lower bounds for obtaining the e-optimal policy ă by inheriting the corresponding lower bound for obtaining e-optimal V-value functions 1%, H-1 )==
35


Reviews:
[{"review_id": "FN3FccyUsK", "reviewer": "Reviewer_tc3r", "summary": "This paper explores quantum algorithms designed to improve the efficiency of solving finite-horizon Markov Decision Processes (MDPs) in two settings: exact dynamics and generative models. The main contribution is the introduction of quantum value iteration (QVI) algorithms.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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.", "claims_and_evidence": "The claims made in the paper are generally supported by formal proofs, especially in the complexity and correctness of the proposed quantum algorithms. There are no immediately obvious problematic claims.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are suited to the problem.", "theoretical_claims": "The theoretical claims in the paper, particularly concerning the correctness and complexity of the quantum algorithms, appear solid. The proofs provided for the algorithms seem logically consistent.", "experimental_designs_or_analyses": "The manuscript does not include explicit experimental evaluations but focuses on the theoretical aspects of the algorithms. This is appropriate for the topic, as the aim is to establish the theoretical foundations of quantum speedups in MDPs. The only concern might be the lack of empirical validation for the proposed algorithms, though this is often the case for early theoretical work in quantum algorithms.", "relation_to_broader_scientific_literature": "The paper connects well with prior work in quantum reinforcement learning and quantum algorithms for MDPs.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper is original in its focus on finite-horizon MDPs and provides a clear exploration of quantum speedups in this domain. The algorithms are innovative and mathematically rigorous. One weakness, however, is the lack of empirical validation of the proposed algorithms in real-world applications, which could have provided a clearer understanding of their practical impact.", "other_comments_or_suggestions": "The paper could benefit from a clearer distinction between the classical methods it compares against. While it mentions improvements over classical algorithms, specific examples or comparisons to concrete classical algorithms could strengthen the case for quantum superiority.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wD1AL8Kl4Y", "reviewer": "Reviewer_Xd2s", "summary": "In this submission, the authors presented quantum algorithms for finite-horizon Markov decision processes (MDPs). These quantum algorithms cover MDPS in the exact dynamics setting and in the generative model setting. Polynomial speedups are achieved. In addition, lower bounds on the query complexity for the generative model setting are also proved in this submission, although not tight. The quantum algorithms are based on well-known quantum techniques including quantum maximum finding and quantum mean estimation.\n\n## update after rebuttal\nI appreciate the authors' rebuttal comments to address my concerns. Most of my concerns have been addressed and I have increased my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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.\n\nWe 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.\n\n[1] Bennett, Charles H. \"Logical reversibility of computation.\".\n\n[2] Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. \"Quantum random access memory.\".", "claims_and_evidence": "Theoretical proofs are provided for the claims.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I checked the proofs and they appear to be correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The problems this submission studies may find applications in quantum machine learning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I appreciate the authors' effort on studying quantum speedups for an important machine learning problem. In the generative model setting, the classical lower bounds presented in this submission show a clear separation between quantum and classical algorithms. The quantum lower bounds rule out the possibility of exponential speedups.\n\nThere are a few weaknesses:\n\n1. Technically, the quantum algorithm is presented in the form that simply replaces the maximum finding and mean estimation of the classical algorithm to well-known quantum subroutines. In this sense, these quantum algorithms lack technical contribution in both the quantum and classical regimes.\n\n2. Although it is nice to see the low bounds, they are still not tight. (But I think this is a minor weakness).\n\n3. I am not fully convinced about the quantum generative model shown in Definition 4.1. In general, QSample is considered as a harder model than the classical sampling model. So it might not be fair to compare the quantum generative model with the classical model. It would be nice if some justification of this comparison can be provided.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "How to justify the comparison between the quantum and classical generative models, particularly for MDP?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tSJzXTBiA6", "reviewer": "Reviewer_LjjN", "summary": "In this work, the authors propose quantum algorithms for solving time-dependent, finite-horizon Markov Decision Processes (MDPs). The goal is to estimate the optimal policy that maximizes the expected reward over the finite time horizon, given a finite and discrete state and action space. Equivalently, this task can be viewed as maximizing the V-value function, which represents the sum of all future rewards for a given policy and initial state.\nThe authors present quantum algorithms for estimating the optimal policy and value function in two settings: the exact dynamics setting, where the agent has full knowledge of the transition probabilities for all state-action pairs at each time step, and the generative model setting, where the agent can only sample transition states for specific state-action pairs using a generative model. In both cases, the proposed quantum algorithms achieve a polynomial advantage over the best known classical algorithm in terms of query complexity to the oracle giving the transition probabilities.\nIn the exact dynamics setting, the authors leverage the quantum maximum searching algorithm to achieve a quadratic improvement in query complexity, reducing it from O(A) to O(\\sqrt(A)), where A is the size of the action space. Additionally, they propose a second algorithm that provides a quadratic speedup with respect to the state space dimension when computing an epsilon-approximation of the optimal policy and value function. In the generative model setting, the proposed quantum algorithms achieve polynomial speedups in query complexity with respect to the action space, time horizon interval, and approximation error for the optimal policy, value function (V-value), and state-action value function (Q-value). These speedups are obtained using the quantum mean estimation algorithm.\nFinally, the authors establish a lower bound for quantum algorithms in the generative model setting, indicating that their proposed algorithms are nearly optimal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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.\n\nWe 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}$. \n\nWe 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]. \n\nWe 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. \n\n[1] Jerbi, Sofiene, et al. \"Quantum policy gradient algorithms.\".\n\n[2] Chen, Yichen, and Mengdi Wang. \"Lower bound on the computational complexity of discounted markov decision problems.\".", "claims_and_evidence": "To the best of my knowledge, all the claims appear to be well-supported. In particular, the quantum speedups rely on well-established algorithms, such as Quantum Maximum Search and Quantum Mean Estimation, and it seems reasonable that these contribute to a computational advantage.", "methods_and_evaluation_criteria": "The paper does not include any numerical experiments to support its claims, as it is purely theoretical. However, benchmarking the classical and quantum algorithms based on query complexity to the transition probability function seems reasonable. Additionally, the implementation of the quantum oracle for this function appears well-founded, making the comparison fair.", "theoretical_claims": "I have skimmed the proofs and all seem fine. The claims are consistent what one would expect based on previous literature.", "experimental_designs_or_analyses": "The paper does not contain any experiment.", "relation_to_broader_scientific_literature": "The paper discusses its relation to previous work in the introduction, highlighting that quantum algorithms have already been proposed for infinite-horizon problems with time-invariant value functions [3]. In contrast, this work focuses on finite-horizon and time-dependent scenarios. Additionally, the authors explicitly state where the key query advantage arises from the application of previously known algorithms. (Quantum Maximum Search [1] and Quantum Mean Estimation [2]).", "essential_references_not_discussed": "I am not sure about essential, but https://arxiv.org/pdf/2212.09328 contains results about comparing finite horizon approximations of infinite time settings which I think are important for this discussion.", "other_strengths_and_weaknesses": "Strength: I think the results in the paper are solid and it is an interesting combination of well-known quantum algorithms for MDPs.\nWeaknesses:\n- I am concerned about the novelty of the results. As the authors acknowledge, the use of quantum maximum search and quantum mean estimation for solving MDPs was already introduced in [3] for the infinite-horizon case. However, they do not clearly explain the challenges in adapting these techniques to the finite-horizon setting or what novel contributions they introduced to make this adjustment.\nAlso appendix B of https://arxiv.org/pdf/2212.09328 establishes a rather tight relationship between finite and infinite time horizons. Furthermore if I am not mistaken that paper and related works actually prove results for finite horizons and then show it also implies good performance for infinite horizons.\n-Regarding the time-dependent case, for finite times, one can reduce this to time independent case, by expanding the state space to encode the timestamp. If one does this and applies previous results, do we get something different? \n- The speedup achieved is only polynomial (quadratic) compared to classical algorithms using rather well known techniques. Additionally, in the exact dynamics setting, the improvement is only relative to the best-known classical algorithm. Establishing a lower bound for classical algorithms, as was done in the generative model setting, would strengthen the results.\n- The presentation of the results lacks clarity. In particular, a high-level overview of the proposed algorithms and their workings would significantly improve the readability and understandability of the paper", "other_comments_or_suggestions": "no other comments", "questions_for_authors": "1)\tWhat are the difficulties of extending the results in [3] to the finite horizon case considered in this paper?\n2)\tCould you establish lower bounds on the query complexity for classical methods in the exact dynamics setting?\n3)\tCould you provide a high-level explanation of your algorithms in the main text, in addition to the pseudocode?\n4)    Regarding the time-dependent case, for finite times, one can reduce this to time independent case, by expanding the state space to \n       encode the timestamp. If one does this and applies previous results, do we get something different?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qr7XppeYIj", "reviewer": "Reviewer_FX1s", "summary": "This paper presents four quantum algorithms for time-dependent, finite-horizon Markov Decision processes (MDPs) in both the exact dynamics setting and the generative model setting: \n\n1. In the exact dynamics setting, the algorithm QVI-1 achieves a quadratic speedup in the active space size (A) for computing the optimal policy and V-value. QVI-2 provides a sub-quadratic quantum speedup in the state space (S).\n\n2. In the diffusion model setting, the algorithm QVI-3 and QVI-4 achieves speedups in terms of A (sub-quadratic) and estimation error $\\epsilon$ (quadratic).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nThe 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.\n\nWe 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. \n\nWe 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**.\n\nWe 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. \n\nWe 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. \n\n[1] Clayton, Connor, et al. \"Differentiable Quantum Computing for Large-scale Linear Control.\".\n\n[2] Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. \"Quantum random access memory.\".\n\n[3] Cormen, Thomas H., et al. \"Introduction to algorithms\".", "claims_and_evidence": "The submission claims the correctness and efficiency of the proposed quantum algorithms. Their correctness and complexity bounds are rigorously proved in the manuscript. Meanwhile, the authors also establish a quantum lower bound for finite-horizon MDPs, demonstrating that QVI-3 and QVI-4 are nearly minimax optimal.", "methods_and_evaluation_criteria": "Overall, the proposed methods and evaluation in this submission appear to make sense:\n- The proposed quantum algorithms, including the input (query) models and the input/output (in the form of pseudo code), are clearly stated. They incorporate standard quantum subroutines such as Quantum Mean Estimation and Quantum Maximum Searching to accelerate existing classical algorithms for time-dependent, finite-horizon MDPs.  \n- The correctness and computational complexity are established through rigorous mathematical proof. Technical overviews of the theoretical results are provided for every quantum algorithm, and they look plausible.", "theoretical_claims": "I read the technical overview of the quantum algorithms. The quantum accelerations are identified as follows:\n1. In QVI-1, the optimal action is obtained by taking the maximum over the whole action space in the Bellman recursion, which is accelerated by Quantum Maximum Search (QMS, Theorem 3.3)\n2. In QVI-2, the quantum speedup is achieved by an improved estimation of $P^T_{h|s,a} \\hat{V}_{h+1}$ through the Quantum Mean Estimation with Binary Oracles (QMEBO, Theorem 3.6, proven by the authors)\n3. In QVI-3, the Quantum Mean Estimation (QME, Theorem 4.2) is used to improve an $\\epsilon$-approximation of $P^T_{h|s,a} \\hat{V}_{h+1}$. This can be further accelerated by QMS as like QVI-1.\n4. QVI-4 focuses on the computation of Q-values. It adapts the total variance technique (Wang et al., 2021) to the time-dependent, finite-horizon setting. Quantum speedups are achieved by a sequence of QME subroutines. \n\nThe technical summary is clear and easy to follow. The results appear to be technically solid, although I was not able to verify the proofs in the appendices line by line.", "experimental_designs_or_analyses": "No numerical experiment is presented in this submission.", "relation_to_broader_scientific_literature": "The pursuit of quantum speedups in stochastic control and reinforcement learning has been an active area of research, with finite-horizon MDPs serving as a standard problem in this domain. \n- This submission investigates several quantum algorithms for time-dependent, finite-horizon MDPs and provides rigorous complexity analyses. These algorithms present evidence of quantum speedups for control and RL problems, which is promising for the entire community. \n- In addition, the proof of quantum query lower bounds for finite-horizon MDPs advances our understanding of the computational limits of quantum computers in control and RL.", "essential_references_not_discussed": "A few references are highly relevant to quantum accelerations of optimal control/RL but are not discussed by the author. \n\n- The authors claim that \"However, the quantum algorithm and analysis there cannot be applied to general finite-horizon MDPs.\" This paper (https://arxiv.org/abs/2206.04741) proposes amplitude estimation to estimate the value function of a policy in a finite MDP with a finite horizon.  \n\n- (Cornelissen, 2018) is not the only work that improves policy gradient. This paper (https://arxiv.org/abs/2411.01391) provides a super-quadratic improvement in policy gradient estimation based on the quantum numerical linear algebra (ODE solvers + LCU) technique.", "other_strengths_and_weaknesses": "Strengths:\n- The quantum lower bounds for finite-horizon MDPs are new results in the literature.\n- The quantum mean estimation with binary oracles (QMEBO) subroutine is clearly stated and its efficiency is proved (Theorem 3.6). It can be of independent interest in future research. \n\nWeaknesses:\n- The efficient construction of the query input model (Definitions 3.2 and 4.1) appears highly nontrivial. Is it possible that these input models might be more expensive than the quantum algorithms themselves and thereby nullify the quantum speedups?", "other_comments_or_suggestions": "- Part 1 in Theorem 4.2: please use \\left( and \\right) in the big-O notation.\n- While the paper claims the algorithms QVI-3 and QVI-4 achieve the \"minimax optimal\", this concept is never clearly defined in the main text. It would be nice to discuss the minimax optimality for self consistency.", "questions_for_authors": "1. Throughout this paper, I couldn’t find a clear explanation of the algorithm name ‘QVI.’ Could you clarify what ‘QVI’ stands for?\n2. What are the possible applications/extensions of the techniques presented in the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the theoretical contribution is solid and well-founded. The rebuttal was described by one reviewer as strong and clear.

Overall, no significant points of criticism remain, so I rate the paper as Accept.
Decision: Accept (poster)