Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach
Authors: Yang Xu
Vaneet Aggarwal
Venue: ICML 2025 poster (2025)
Keywords: Quantum Machine Learning
Reinforcement Learning
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach

Abstract: We address the problem of quantum reinforcement learning (QRL) under model-free settings with quantum oracle access to the Markov Decision Process (MDP). This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classical Natural Policy Gradient (NPG) estimators with a deterministic gradient estimation approach, enabling seamless integration into quantum systems. While this modification introduces a bounded bias in the estimator, the bias decays exponentially with increasing truncation levels. This paper demonstrates that the proposed QNPG algorithm achieves a sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-1.5})$ for queries to the quantum oracle, significantly improving the classical lower bound of $\tilde{\mathcal{O}}(\epsilon^{-2})$ for queries to the MDP.

Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach
Yang Xu Vaneet Aggarwal
Abstract
2025; Zhong et al., 2024). This work aims to explore po- tential quantum speedups for reinforcement learning with general parameterized policies.
We address the problem of quantum reinforce- ment learning (QRL) under model-free settings with quantum oracle access to the Markov De- cision Process (MDP). This paper introduces a Quantum Natural Policy Gradient (QNPG) algo- rithm, which replaces the random sampling used in classical Natural Policy Gradient (NPG) esti- mators with deterministic gradient estimation approach, enabling seamless integration into quan- tum systems, While this modification introduces a bounded bias in the estimator, the bias decays ex- ponentially with increasing truncation levels. This paper demonstrates that the proposed QNPG algo- rithm achieves sample complexity of Ó(e -1.s) for queries to the quantum oracle, significantly improving the classical lower bound of Ö(E for queries to the MDP.
A key enabler of quantum speedups is the quantum evalua- tion oracle, which leverages quantum parallelism, amplitude amplification, and entanglement. This powerful concept has been utilized in foundational algorithms such Grover's s search (Grover, 1996). In this work, we assume access to quantum transition oracle and a quantum initial state oracle, which serve as quantum analogs for sampling from the clas- sical environment and the initial state distribution, respec- tively. Using these quantum oracles, we aim to demonstrate the speedups that quantum computing can provide in the context of reinforcement learning.
Quantum computing principles have shown significant im- provements in areas such as quantum mean estimation (Hamoudi, 2021) and quantum stochastic convex optimiza- tion (Sidford & Zhang, 2024). However, quantum reinforce- ment learning (RL) presents unique challenges. Unlike clas- sical algorithms, quantum methods rely on deterministic op- erations, complicating the design of unbiased estimators for policy gradients. This paper addresses the trade-off between bias and unbiased estimation by introducing a novel deter- ministic algorithm that facilitates quantum-compatible gra- dient estimation. While this approach introduces a bounded bias, achieves orders reduction in sample complexity com- pared to its classical counterparts.
1. Introduction
Reinforcement Learning (RL) is foundational framework for sequential decision-making, with applications spanning robotics, finance, transportation, and healthcare (Al-Abbasi et al., 2019; Gonzalez et al., 2023; Tamboli et al., 2024; Wang et al., 2023). The goal of an RL agent is derive policy that maximizes the discounted sum of expected re- wards through interactions with the environment. A promi- nent approach to solving this problem is the policy gradi- ent (PG) method, which optimizes directly in the policy space. In classical RL, the optimal sample complexity of this approach has been established as Ö( (Mondal & Aggarwal, 2024a). Quantum computing has shown potential for speedups in areas such mean estimation (Hamoudi, 2021), multi-armed bandits (Wan et al., 2023; Wu et al., 2023), and tabular reinforcement learning (Ganguly et al.,
1.1. Challenges and Contributions
In this work, we introduce the first quantum model-free re- inforcement learning (RL) algorithm with theoretical guar- antees, addressing the challenges posed by large state and action spaces. To our knowledge, this is the first work to coherently embed the entire Natural Policy Gradient (NPG) into a quantum state by leveraging only the standard envi- ronment oracles from reinforcement learning. This novel construction allows subsequent quantum subroutines to uti- lize these NPG gradients directly in superposition, enabling potential accelerations in policy optimization. Extending classical model-free RL algorithms to the quantum domain is nontrivial. Specifically, classical model-free algorithms (Mondal & Aggarwal, 2024a; Liu et al., 2020; Agarwal
'Purdue University, West Lafayette, IN, USA. Correspondence to: Yang Xu <xul720@ pud, Vaneet Aggarwal <va- neet purdue.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Accelerating Quantum RL with Quantum NPG Based Approach
al., 2021) typically rely on sampling trajectories of ran- dom lengths following a geometric distribution for policy gradient estimation. However, encoding such trajectories with random lengths into quantum systems is challenging. To address this, we propose a novel deterministic sampling algorithm that uses truncation to estimate both the Fisher matrix and the policy gradient. We further develop a mini- batch strategy to incorporate quantum variance reduction into the Natural Policy Gradient (NPG) update. By carefully analyzing the bias introduced by the truncation, we show that our approach achieves a sample complexity of ((e-1.)) surpassing the classical lower bound of (0(=)). To the best of our knowledge, this is the first work to demonstrate quan- tum speedups for parameterized model-free infinite-horiza Markov Decision Processes (MDPs).
1.3. Related Work and Preliminaries
Quantum Mean Estimation: Mean estimation focuses on determining the average value of samples drawn from an unknown probability distribution. Notably, quantum mean estimation provides quadratic improvement over classical methods (Montanaro, 2015; Hamoudi, 2021). This enhance- ment arises from the utilization of quantum amplitude am- plification, which facilitates the suppression of undesired quantum states relative to the target states to be extracted (Brassard et al., 2002).
In what follows, we define the key concepts and results related to quantum mean estimation that are central to our analysis. Specifically, we introduce the definition of a classi- cal random variable alongside the quantum sampling oracle, which used to perform quantum experiments.
It should be noted that SGD-based approaches have been shown to achieve a sample complexity of Ó(e-1.5) for stochastic convex optimization (Sidford & Zhang, 2024). However, reinforcement learning (RL) presents fundamen- tally different set of challenges compared to stochastic con- vex optimization. While insights from the literature suggest that Ó(e-1.5) is likely the best achievable sample complex- ity for SGD-based approaches, this limitation arises because quantum computing can accelerate the inner loop but not the outer loop of such algorithms. To achieve better sample complexity guarantees, stochastic cutting-plane methods have been proposed in (Sidford & Zhang, 2024). Extending these methods to RL, however, would require an entirely new algorithmic framework. This is due to the non-convex nature of RL with general parameterization, which makes direct adaptation infeasible. Moreover, the techniques used in (Agarwal et al., 2021) to transition from local to global convergence are not applicable in this context, preventing similar guarantees for such methods in RL.
Definition 1 (Random Variable, Definition 2.2 of (Comelis- sen et al., 2022)). A finite random variable can be repre- sented as X S2 - E for some probability space (St, IP), where 52 is finite sample set, IP : Ω - [o, 1J is a probability mass function and E C R is the support of X. (2, is frequently omitted when referring to the random variable X.
To perform quantum mean estimation, we provide the defi- nition of quantum experiment. This is analogous to classical random experiments
Definition (Quantum Experiment). Consider a random variable on a probability space (52, 2 ,P). Let Hg be a Hilbert space with basis states {Iw)) wwes and fix unitary Ue acting Hi such that
Up : 10) H Σ EVPI VP(WW))))
WESt
assuming 0 E Ω. We define a quantum experiment as the process of applying the unitary Up or its inverse Up on any state in Hz-
1.2. Contributions
The main contributions of this paper are summarized as follows:
The unitary operator Up enables the query of samples of the random variable in superposition, forming the basis for the speed-ups achieved in quantum algorithms. To perform quantum mean estimation for random variable values (Cor- nelissen et al., 2022; Hamoudi, 2021; Montanaro, 2015), the implementation of an additional quantum evaluation oracle is required.
We construct quantum oracle for NPG gradient estima- tion by leveraging fundamental oracles from the Markov Decision Process (MDP), ensuring efficient computation in quantum environments.
We modify the classical Natural Policy Gradient (NPG) algorithm into a deterministic setting, enabling seam- less integration into quantum systems while maintaining bounded gradient estimation bias.
Definition 3 (Quantum Evaluation Oracle). Consider fi- nite random variable X Ω + E on a probability space (2, 22, IP). Let He and H be two Hilbert spaces with ba- sis states [[w)eer and {|z) Jeer respectively. We say that a unitary Ux acting on Ho & HE is a quantum evaluation oracle for X if
Our proposed approach achieves a sample complexity of Ô(c--((5)) which surpasses the classical lower bound of Ō(e ?), demonstrating a significant improvement in efficiency.
Ux (w) + (w)X(())
for all E Z assuming E E.
2

---

Accelerating Quantum RL with Quantum NPG Based Approach
Next, we present key quantum mean estimation result that will be carefully employed in our algorithmic framework to utilize the quantum superpositioned states collected by the RL agent. One of the crucial aspects of Lemma 1 is that quantum mean estimatiion converges at the rate ( as opposed to classical benchmark convergence rate O for n number of samples, therefore estimation efficiency increases quadratically.
(1 "i.....,Tmm. )"r can be represented as vector within this
space, satisfying the normalization condition Σ; |2x/2 1. For finite set & = {Ei,.... fm of m elements, each & E g can be mapped to an element of an orthonormal basis in Cm
as follows:
& + (ct) = ei.
(I)
where e, represents the ith unit vector in C.m. Utilizing this notation, any arbitrary quantum state (x) = um)" can be expressed in terms of the elements of as:
Lemma 1 (Quantum multivariate bounded estimator, Theorem 3.5 of (Cornelissen et al., 2022)). Given ac- cess to the quantum sampling oracle Ux and let d be the dimension of X, for any σ,8 2 there a procedure quantunNeanEstimation (X, that queries and ouiputs an esti- mate ji of the expectation μ of any d-dimensional ran- dom variable X satisfying Var[X] I L² with er- for |1 اll I los S L and success probabil- ity - 5. Furthermore, if d < LVdlog(1/8)/ QuantumMennEstimatai (X,ō,6) 6) can be implemented using Algorithm 2 in (Cornelissen et al., 2022).
EnlEa>>
(2)
where (z) is a quantum superposition of the basis states KI), .i),....le ..)m) and zn, denotes amplitude corresponding to (En). To extract classical information from the quantum state, a measurement is performed, causing the state to col- lapse to one of the basis states (<s) with probability (2;]², In quantum computing, quantum states are typically repre- sented using input or output registers composed of qubits, which may exist in superposition.
uses
Quantum Reinforcement Learning: In recent years, Quan- tum Reinforcement Learning (QRL) has garnered substan- tial interest from the research community (Dong et al., 2008; Paparo et al., 2014; Dunjko et al., 2017; Jerbi et al., 2021). Within this field, studies on the Quantum Multi-Armed Ban- dits (Q-MAB) problem have demonstrated exponential re- ductions in regret by leveraging amplitude amplification techniques (Wang et al., 2021b; Casalé et al., 2020). How- ever, the theoretical foundations of Q-MAB approaches are not directly applicable to QRL, primarily due the lack of state transitions in bandit problems.
2.2. MDP Formulation
We analyze a Markov Decision Process (MDP) represented by the tuple MM = AS, r, P.7, p). where S and A denote the state space and action space, respectively. The reward function r S x AA- + [0. 1] assigns a reward to each state- action pair, and the state transition kernel P S - A defines the probabilities of transitioning between states (with l denoting the probability simplex over [S] states). The discount factor 7 E (0, 1) determines the importance of future rewards, while E A $I specifies the initial state dis- tribution. A policy π. : S > A lAl provides the probability distribution over actions for a given state. The Q-function for a policy n,, corresponding to a state-action pair (s, a), defined follows:
Although interest in QRL has been growing, most existing works are still limited to the tabular setup. For instance, (Zhong et al., 2024; Ganguly et al., 2025) showed that log- arithmic regret is achievable in episodic/average reward Markov Decision Processes (MDPs) using model-based ap- proaches, while (Wang et al.. 20) investigated the infinite horizon discounted MDP framework with tabular model- free setups. However, the results don't directly extend to large state spaces, where a parameterized policy is used. Further, the problem becomes non-convex due to the use of general parameterization. To the best of our knowledge, ours is the first work to address infinite horizon MDPs with general parameterized policies.
("(ssa) A
Σ ('rr(s,, 8o 8, ag
Here, the expectation is taken over all trajectories {(se: 12 induced by π, where $1 ~ P(s-11, a;-1) 1) and ar ~ i (8t) for all 2 1. Similarly, the V-function associ- ated with the policy π is defined as:
V E
rr(s
at) so= = = Σ (sals)Q=(s.aa)
==
aEA
The advantage function is then given by:
2. Formulation
A5 a) = Q (s, - (s), v(s,a) E x
2.1. Quantum Computing Basics:
The primary objective is to maximize the following function over all possible policies:
In this section, we provide a concise overview of the key concepts relevant to our work, drawing from (Nielsen & Chuang. 2010) and (Wu et al., 2023). Let C denote an m-dimensional Hilbert space. A quantum state (x) =
J 2 Eaup [V*(s)] = Σ (((e)))((ab))r(ss)
8.0
3

---

Accelerating Quantum RL with Quantum NPG Based Approach
Here, the state occupancy dx A is defined as:
We also assume the ability to construct unitary II that coherently implements policy ne:
Σ y PPr(s s|50 ~ p. T), YsES d5 (0) ( - (1 7)
Let me S - [0, 1] be a reinforcement learning policy acting in state-action space S x A and parametrized by a vector 0 E Rd (that can be encoded with finite precision as (0)). We say that the policy is -evauuuueeallutablle if we can construct a unitary satisfying:
The state-action occupancy vp E AISxAl is similarly de- fined as v/ (s, a) a (s)t((()) for all (s,a) E S x A. In practical applications, the size of the state space often neces- sitates parameterizing policies using deep neural networks with d-dimensional parameters. Let To represent policy parameterized by 0 E IRd. Under this parameterization, the optimization problem can be reformulated as:
II [0) + 10) Σ
(6)
.E
This construction is particularly intuitive for certain quan- tum policies, such as RAW-PQC which is introduced in (Jerbi et al., 2023). However, any policy that can be clas- sically computed can also be converted into such a unitary operation through quantum simulation of the classical com- putation of (To(als) methods to encode this probability vector into the ampli- tudes of a quantum state (Grover & Rudolph, 2002). With access to quantum oracles for both the environment and the policy in (4)-(6), it becomes possible to design subrou- tines capable of generating superpositions of trajectories with fixed length within the environment and calculating the returns associated with these trajectories. We can further utilize Ur, Up and IT defined above to construct unitary MDP
max J
BER
For simplicity, we denote J as (0) throughout the re- mainder of this paper.
A) and leveraging established
2.3. Quantum access to an MDP
We adopt the framework and notations of quantum com- puting from (Zhong et al., 2024; Wiedemann et al., 2022; Ganguly et al., 2025; Jerbi et al., 2023) to design the quan- tum sampling oracle for reinforcement learning (RL) envi- ronments, enabling the modeling of an agent's interactions with an unknown MDP environment, We proceed to define quantum- acccessbbe RL environments corresponding to the classical MDP M. For an agent at step in state 8, and per- forming action dz, we construct quantum sampling oracles for the transition probabilities of the next state, P(-[s,, a,). To this end, let two Hilbert spaces, S = ClSl and A = CLAi, represent the superpositions of classical states and actions, respectively. The computational bases for these Hilbert spaces are denoted as {[s) hees and {(a) We assume the ability to implement the following quantum sampling oracles:
Up(ex) as follows: Let M be a quantum-access/ie with oracles Up as above, and let wo be a quantum- evaluatable policy with its unitary implementation II as defined above. Given a fixed number N, the unitary MP(Tx) that prepares a coherent superposition of all trajectories TN = (8o; (80,00, "0,-...,8y -1, of length N (without their rewards) is defined as
Up((w): : 0) 62N
10) Σ V Po((T)]TN)
(7)
for Pe(TN) = p(5o) Im P(sc)1))))))+ az). The details of constructing Up(rx) using Ur, Up and IT are char- acterized Appendix A.
Quantum transition oracle Upp : The quantum evaluation oracle for the transition probability (quantum transition oracle) Up which at step t, returns the superposition over s' S according to P(s'|st, at), the probability distribu- tion of the next state given the current state (sz) and action lax) is defined as:
3. Proposed Algorithm
A common way to solve the maximization (3) in clas- sical methods is via updating the policy parameters by applying the gradient ascent: 0x+1 = 0x + J,
Up : |s))aa)))) + (se)la)) SES
((,s (4) Σ
k E {0, 10,1, ........ starting with an initial parameter, 6g. Here, n > denotes the learning rate, and the policy gradients (PG) are given as follows (Sutton et al., 1999).
Quantum initial state oracle Up The quantum sampling of the initial state distribution (quantum initial state oracle) Up which when queried, returns superposition over E
1 I- Breaaro (s (s, loggmm(())))))
1
VoJ
S according to p is defined as:
(8)
Up:10) 10) + Σ ss)
(5)
This paper uses the natural policy gradient (NPG) to update the policy parameters. In particular, Yk E {1,2, ... we
#ES
4

---

Accelerating Quantum RL with Quantum NPG Based Approach
Algorithm 1 Quantum Natural Policy Gradient
have knowledge of the state transition probabilities, making it difficult directly calculate w In the following, clarify how one can get its sample-based estimates. Note that the gradient of 1 (-,0) can be obtained as shown below for any arbitrary 0.
1: Input: Policy Parameter lo. State distribution p. Run- time Parameters K, N,N, og. op, Learning Parameters (1,0),, NPG initialization wig
2: for & <- {0, 1. K ----1 1 do
3: Xo, 4-4-0 0
VuLugo oo (w. 0)
(13)
4: for h E {0,..... H 1} do
We now present an estimation procedure for obtaining quan- tum estimators for V.LL,, (w. based on the provided oracles in Section 2.3. Different from the commonly used unbiased estimators in (Agarwal et al., 2021; Mondal & Ag- garwal, 2024a) which requires sampling from geometric dis- tribution with mean r we construct deterministic algo- rithm which can be implemented using the quantum oracles in Section 2.3. For fixed N, let TN = (so, ao...... 8N, ax) be trajectory with length N generated by taking policy my with so sampled from p. we construct the policy gradient estimator (p(TN/ (0) and Fisher information matrix estimator F Pp(TN (0) as follows:
5: (Mini-Batch Quantum SGD}
6: Ih wewariinnceeeuuueeeeee 0s)), Ob-
tain gradient estimator
7: Fn + QV @VarianceReduceef (Fp(TN) 0p)
Obtain Fisher estimator
8:
V.,, TN) < FAw- - Ih
9:
NPG update: Wh+1 = Wh - a VWVVL(W..T)
end for
11:
Wi = WH
12:
Policy Parameter Update:
0 02 + mwck
(11)
13: end for Output: k=
(o(TN(0)
N-1
Σ
Σ t=0
Ve log TO (alls))
(7"" an))
14:
n=0
(14)
N-1
have,
(x( =
Σ n=0
Vo log y"h
(15)
0 0% + (1pp((0)))) (o.)))))
(9)
V log To(anlsn))
where i the Moore-Penross pseudoinverse operator, and F, is called the Fisher information matrix which is defined as follows 40 Rdd
Note that (7) and (TN (0) are truncated estimators deterministically obtained from TN- Our goal then to obtain the above estimators in quantum superpositioned forms from the quantum trajectories in (7). Assume that a quantum state (V)) (0) E (Po(TN]TTN) represents a superposition of all possible values of TN generated from the MDP under the parameterized policy my. We can construct quantum operators Ur and Mg such that
(0) A ((..))uN3
[V log (alls) V log no (a [
(10)
where @ denotes the outer product. In particular, for any
a E Rd. a a aa
Ur (1 (o)) @ 10)) 14%)
Let w/ A (O))).) Notice that we have removed the dependence of w on p for notational convenience. In- voking (8), the term w can be written quadratic optimization (Peters & Schaal, 2008). Specifically, wß = arg min (w,0) ()) where L,," (w, 0) is the compat- ible function approximation error and it is mathematically defined as,
= 10) Σ &
solution of
N
(16)
Ug (1W)) @ 10)) =1dg)
= |0) Σ (Po(T)) Tx) @ @0o(TN)))) (17)
1 E ((,))~u3))
1 AT (s,
Luz0 (w, 0) A
where [0) is an auxiliary state, (Tx(())) and (Tx(())) represent the quantum states encoding the function value Fo(TN (0) and (TN(0)) for each basis state in the superpo- sition (TT). The detailed construction for oracles Up and Uy are described in Appendix A.
(12)
w T Vo Vologoo(aas))
Using the above notations, NPG updates can be written as 9x41 = 0g + nwž, & E {1,2,... where w = wā.- However, in most practical scenarios, the learner does not
Our quantum NPG algorithm is described in Algorithm 1, which can be segregated into a classical outer loop and
5

---

Accelerating Quantum RL with Quantum NPG Based Approach
novel quantum inner loop. In its outer loop, the pol- icy parameters are updated K number of times following (II), where (ws))= -1 denote the estimates of {wt Jk= K-1 For the inner loop, the estimates K=) are calculated by iterating the quantum SGD algorithm H number of times. Each quantum SGD iteration consists of a quan- tum mini- batiib approach, where the stochastic gradients are obtained via quantum mean estimation using quantum samples. We utilize QvarianceRReduce Zhang. 2024) that leverages QuantumMeanEsting Lemma as a subroutine. For each 0g and each h, to per- form
The Lipschitz continuity and smoothness of the score func- tion are widely assumed in the literature (Liu al., 2020; Agarwal et al., 2020), and can be validated for basic param- eterized policies, such as Gaussian policies. Under Assump- tion 1, the following lemma holds.
Lemma If Assumption holds, then Jp()) defined in (3)
satisfies the following properties 40 E IR.
G
(Sidford & in
(a) [VDJ,(0)1l
(1 11-77 7)2
B
+ 2G2
(b) J,(-)) Ls -smooth, L
multiple quantum samples for (V,,) are drawn to obtain variance-reduced estimators Frj and gh.
(1- (1-7)² (1 7)3
Proof. Statement (a) can be proven by combining Assump- tion ((a) with (8) whereas statement (b) follows directly
from Proposition 4.2 of (Xu et al., 2019).
9h = [VVrrienceeeeuueee(((((1..... (18)
Lemma implies the Lipschitz continuity and smoothness for function Jp(.), which are critical properties for the fur- ther analysis. The following Assumption 2 states that the class of parameterized policies is sufficiently expressive such that, for any policy parameter 0, the error in the trans- ferred compatible function approximation, represented by the left-hand side of equation (23), is bounded by a positive constant, Cbias-
FA = Q/arilacceRdduce(((((O1).
(19)
Note that o% and 8² are the pre-defined target variances, which are specified later in Theorem 3. qvarianceRdduce offers a quadratic speedup in terms of sample complexity compared with classical mean esti- mation methods, and the details are specified in Appendix B. Note that in this paper, for random variable X with di- mension d, we denote the variance of X as the trace of its covariance matrix. With the above quantum variance- reduced estimators, the NPG gradient foor a given policy parameter 0 is calculated and updated as follows:
Assumption 2. The compatible function approximation error defined in (12) satisfies the following v0 E Rd.
Luz (wg, 0) S Ebias
(23)
where n" is the optimal policy i.e., 'T" = arg max, J and wg is defined as follows.
VwiLW,,T = Fnw- In
(20)
Wh+1 = w/ (.,, TN) TX) wamn
(21)
w _ arg max Lypp (w;, 0)
(24)
4. Global Convergence Analysis
It has been shown that for softmax parameterization, Chis is equal to zero (Agarwal et al., 2021). Moreover, in the case of expressive neural network-based parameterization, ébias is observed be relatively small (Wang al., 2019).
In this section, we discuss the convergence properties of Algorithm 1. We first present the standard analysis proce- dures of the classical outer loop, and then delve into the results of the quantum inner loop, which contributes to the polynomial speedup in the final result.
Assumption 3. There exists a constant μ4f > 0 such that F₂(0) Ta is positive semidefinite where Ta denotes an identity matrix of dimension d and (0) is defined in (10). Equivalently, (0) > uyla-
4.1. Outer Loop Analysis
Assumption 3 asserts that the Fisher information function should not be too small, condition commonly adopted in classical policy gradient literature (Liu et al., 2020; Bai et al., 2023; Zhang et al., 2020). This assumption holds for Gaussian policies with linearly parameterized means. The set of policies that satisfy Assumption 3 is referred to as the Fisher Non-degeneracy (FND) set. It is important to note that (0) L2,,, =0 (). Therefore, Assumption es- sentially implies that the function Ly (+ 0) exhibits strong convexity with parameter jep. With the above assumption, the following lemma holds:
We start with the assumptions commonly used in classical parameterized RL.
Assumption 1. The score function is G-Lipschitz and B-smooth. Mathematically, the following relations hold 40, 01 0g E IRd, a) E x A.
(a) V (o G
(b) V log Te, (als) - Vo log no, (a|s)]l < Bll@1 - 621
(22)
where and G are some positive reals.
6

---

Accelerating Quantum RL with Quantum NPG Based Approach
Lemma 3 (Corollary 1 of (Mondal & Aggarwal, 2024a)). Let, the parameters {0s: K= be updated via (11), x² be the optimal policy and J be the optimal value of the function JoL.). If asssuptioons 1-3 hold, then the following inequality 2²
E [||F((Tx10) - Fo(O)) -F(o)) S vaG + +8g
(29)
dG²
Var(āo(TN 10]) (1 7344 and Var( Var(Fo(TN) (0)) S dG (30)
Where 8, = G( + (1-a))))" N and 8p G2yy
is satisfied for 11 1G"L.
While classical algorithms produce unbiased estimators of (0))(0) and F2 via sampling from geometric distribu- tions, our deterministic approach in (14) and (15) utilizes truncation to allow integration into quantum systems. The proof of Theorem (in Appendix C) analyzes the truncation- based estimators by comparing them to their following horiite-horizon counterpart as an intermediate step:
K-1
J
B[J [1))(
K
k=
VEbias
Σ
E
[[ [w]] - wflll
K_
k=0
1 K-1
+ 4L
B
+ c²)
Σ
E 1wo -
g(T
Σ 1==
Va log Ro (alls))) (7" (7"r((n:
G
K
k=0
n=
G
(
B
+ 4L ayy - [KL (o]5)] (+1))]
K y
F(r = (1-m)
7 Vo log (ongss log
log To (anl))))
(25)
Eig(T [[]]] and [[] [T]((]))]] quantifies the truncation error, showing that the truncation introduces an exponentially de- caying bias of order ((>*) while maintaining a bounded variance. This is achieved by leveraging properties of the geometric series and analyzing the dependence on the dis- count factor y. Given the above, we can formally state the bias and variance bounds for the gradient estimator In and Fisher estimator F) for each h, along with expected number of quantum samples (w-ge)) and | used in (18) and (19).
Analyzing the error bounds ||
where LL---l)) is the Kellback-Leibler divergence.
Lemma decomposes the optimality gap in a way that achieves the order-optimal sample complexity of O(e in the classical setting. Notice that both the first-order ap- proximation error, EE [[ [0] -wfill ]I and the second-order error, E ||W wlll are both dependent on H, the number
of iterations in the inner loop.
4.2. Inner Loop Analysis
Theorem 2. For any @ and h, (18) and (19) satisfy E(ğu] = (T [0)] and B[ = E[EE(TN [0)] with reduced vari- ance Var(ğn) = 0² and Var(Fn) = oz.- Moreover, (18) and (19) perform ((o')) queries uy and Ö (1-7)-99)
The sample complexity of the quantum inner loop is char- acterized by the total quantum state-action pairs needed in the algorithm, which is equivalent to the total queries of Up and II. Recall that each iteration in the inner loop consists of one operation of (18) and (19), which performs quantum mean estimations of quantum samples wg)) and (ei)) queried from Up and Uy. The complexities of these quantum samples are as follows:
queries ug in expectations.
The proof of Theorem 2 (in Appendix B) leverages Lemma to achieve variance reduction by applying quantum mean estimation techniques to the truncated estimators, ensuring unbiased estimates of the policy gradient and Fisher matrix with reduced variance. Note that although ğn and ğn are unbiased with respect to 9p (Tx/ (0) and (TN [0), they are still biased with respect to the actual policy gradient and Fisher information matrix. Theorem 2 demonstrates that quantum variance reduction methods achieve a quadratic speedup in complexity compared to classical methods such as averaging, when reducing to the same variance. This step is crucial to achieve the overall polynomial speedup in the final result. We thus are now able to describe the first and second order errors for the quantum estimators F₁ and ğn.
Lemma 4. One call of and Ug each requires one call of Up and ON) calls to Up and II.
The proof of Lemma 4 is in Appendix A. Lemma 4 states that obtaining a single sample of (w)) in (16) and (vg) in (17) requires a sample complexity of (NN) with respect to the quantum state-action pairs. We next provide the biases and variances for âp (TN (0) and (N (0). which are the random variables for the quantum samples (w))) and lug).
Under assumption for a fixed O, we have the following results on Fp(TN 0) and (T 0).
Theorem 1.
Lemma 5. Under assumption 1, for a fixed O, we have the following results on F, and 9h-
[[ - VoJr(01| S 6,
(26)
VdG
E El - - VeJ,(e)ll <- [1 7)² + ón
(27)
[[ VoJz(0)] 2 82
(31)
[ - S dr
(28)
E [1|@ - VoJo(0))1]] S + 82
(32)
g
7

---

Accelerating Quantum RL with Quantum NPG Based Approach
|| - (0)11 < 83
(33) Lemma 6 shows that the bias terms ((7*) from the gradi- ent and Fisher matrix estimators would accumulate across iterations, leading to a total error contribution of the form
E ||| - [x(1))1 s 566 + 87
(34)
Where 82 G2 + 1-y + ()-a)=)2 )272N and 83 G
H1 Σ 2N
2N
O
= =0
1 e Hapf
Note that 82 and 83 in Lemma 5 characterizes the exponen- tially decaying bias by truncation. The proof of Lemma 5 (in Appendix D) decomposes the second order error into the sum of bias and variance terms, which are futher bounded by Theorem and Theorem 2 respectively. Compared with the classical NPG algorithms in (Mondal & Aggarwal, 2024a; Liu et al., 2020), the extra bias terms requires a more careful analysis. We derive the error bound for the first-order and second-order approximation of wi as follows:
g
while the learning rate is chosen appropriately to ensure exponential decay, eventually leading to the terms Co and C1- We next combine the outer loop and inner loop analysis with the quantum speedup results to form the final result.
4.3. Final Result
Combining Lemma 6 and the fact that the last term in (25) is (1/K). Thus, by taking H = ()lo((e")) )) N = O(log(=))), K = O(c-), og = -c) and 07 = O((1 - -)),,, we guarantee the optimality gap to be at most Vebias + E. By Theorem 2, Ö( (1-5% queries Gd
Lemma 6. Consider the NPG-finding loop (21) with a S ue and G2 S Hr for a fixed 0%. if asssmmptions 1-3 56G3 hold,
8
G'd
E [| wtll I exp (-Houp)) - w011 + Co
of U. and Ö ( (1- queries of Ug. This results in sample complexity of Ó(HKN. (1-))/2) O(1/cLa) and an iteration complexity of is formalized in the following theorem.
(35)
Additionally, we also have
The result
[B[u]] will S exp (- -HapF) [[wo] - =1 C1
(36)
Theorem 3. Let {0x] be the policy parameters gen- erated by Algorithm 1, n²" be the optimal policy and J denote the optimal value of Jp(-) corresponding initial distribution p. Assume that assumptions 1 - 3 hold and the learning parameters are chosen as stated in Lemma 3 and Lemma 6. For all sufficiently small c, and H = (logg( N = O(log(=1)), K = O(+
where
up 0²
an
Co= = 4uF
+ })
(1 7)4
+ +64fF
HP G²
(078%)
+ (0, }
(37)
(1 - 7}²
07
0 2N
- 7)5 + 07
03 = (c) and 07 = ((1 7)),), the following holds.
6
1
K-1 1
C1 #F
a
87 E [lwo - -
J K
Σ B[JA(OA)
Vebias +e
(39)
mr)
aRo + Rig } + MF G² G2 87. 82]
(38)
(1 7)
This results in ((--1.5 sample complexity and 1) it- eration complexity.
= 0 (?2N) (?mm)
while Ry = 6FF T==²0²
0z + +8))
+ (0² 002+ + }
The resulting sample complexity -(55 is due to the quantum speedup in the inner loop while the outer loop maintained as in the classical settings. This aligns with the results of quantum stochastic optimizations (Sidford & Zhang, 2024) due to the same double-loop algorithm structure with classical outer loop and quantum inner loop. Note that H is chosen to be logarithmically dependent on the total samples to account for the exponentially decaying bias term of the truncation error.
(1-7)a
R1 4/F² -2 28 up G²
(1-9)a + {2
The proof of Lemma 6 (in Appendix E) proceeds by first expressing the error between the estimated gradient and the ideal gradient as a recursive update from the inner-loop iteration. It then demonstrates that each update contracts the error exponentially, meaning the error shrinks by fixed multiplicative factor with each iteration. Subsequently, the proof carefully bounds the additional errors introduced by truncation bias and estimator variance, leading to explicit residual terms. Finally, these contraction and residual terms are combined through a recursive argument to establish the overall error guarantees.
5. Conclusion
This paper introduces the Quantum Natural Policy Gradient (QNPG) algorithm, which utilizes quantum mean estimation and a deterministic gradient sampling approach to address
8

---

Accelerating Quantum RL with Quantum NPG Based Approach
sample efficiency challenges in infinite-horizon reinforce- ment learning. By adapting the sampling method in the classical state-of-the-art result to quantum-compatible de- terministic procedure, we achieve a sample complexity of O(e-1.5) improving upon the ()) result of the classical state-of-the-art result. The algorithm balances the trade-off between deterministic encoding and bounded bias, demon- strating the feasibility of leveraging quantum acceleration in policy optimization.
deep reinforcement learning. IEEE Transactions on Intel- ligent Transportation Systems, 20(12):471
Bai, Q.. Bedi, A. S., and Aggarwal, V. Achieving zero constraint violation for constrained reinforcement learn- ing via conservative natural policy gradient primal-dual algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp- 6737-6744, 2023.
Baxter, J. and Bartleu, P. L. Infinite-horizon policy-gradient estimation. journal of artificial intelligence research, 15: 319-350, 2001.
While our study focuses on policy gradient methods, quan- tum actor-critt critic algorithms remain largely unexplored. Re- cent classical results offer order-optimal sample complexity guarantees (Gaur et al., 2024; Ganesh et al., 2025), mak- ing the search for quantum speedups in this setting a key open direction. Another open direction is extending the constrained setup studied in (Mondal & Aggarwal, 2024b)
Brassard, G., Hoyer, P., Mosca, M., and Tapp. A. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 74, 2002.
Casalé, B., Di Molfetta, G., Kadri, H., and Ralaivola, L. Quantum bandits. Quantum Machine Intelligence, 2:1-7, 2020.
to the quantum setting.
Acknowledgment
Cornelissen, A., Hamoudi, Y., and Jerbi, S. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 33 43, 2022.
This work is supported in part by the National Center for Transportation Cybersecurity and Resiliency (TraCR) (a U.S. Department of Transportation National University Transportation Center) headquartered at Clemson Univer- sity, Clemson, South Carolina, USA. Any opinions, findings, conclusions, and recommendations expressed in this mate- rial are those of the author(s) and do not necessarily reflect the views of TraCR, and the U.S. Government assumes no liability for the contents or use thereof.
Dong, D., Chen, C.,, Li, H., and Tarn, T.-J. Quantum rein- forcement learning. IEEE Transactions on Systems, Man, and Cybernetiss, Part B (Cybernetics), 38(5): 2008.
Dunjko, V., Taylor, J. M., and Briegel, H. J. Advances in quantum reinforcement learning. In 2017 IEEE Inter- national Conference on Systems, Man, and Cybernetics (SMC), pp. 282-287, IEEE, 2017.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Ganesh, S., Chen, J., Mondal, W. U., and Aggarwal, V. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In The 4/st Conference on Uncertainty in Artificial Intelligence, 2025.
References
Ganguly, B., Xu, Y., and Aggarwal, V. Quantum speedups in regret analysis of infinite horizon average-reward markov decision processes. In Forty-second International Con- ference on Machine Learning. 2025.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. Optimality and approximation with policy gradient meth- ods in markov decision processes. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Confer- ence on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 64-66. PMLR, 09-12 Jul 2020.
Gaur, M., Bedi, A., Wang. D., and Aggarwal, V. Closing the gap: Achieving global convergence (last iterate) of actor- critic under markovian sampling with neural network parametrization. In International Conference on Machine Learning, pp. 15153-15179. PMLR, 2024.
Agarwal, A., Kakade, M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Gonzalez, G., Balakuntala, M., Agarwal, M., Low, T., Knoth, B., Kirkpatrick, A. W., McKee, J., Hager, G., Aggarwal, V., Xue, Y., et al. Asap: A semi-autonomous precise system for telesurgery during communication de- lays. IEEE Transactions on Medical Robotics and Bion- ics, 5(1 78. 2023.
Al-Abbasi, A. O., Ghosh, A., and Aggarwal, V. Deeppool: Distributed model-free algorithm for ride-sharing using

---

Accelerating Quantum RL with Quantum NPG Based Approach
Grover, L. and Rudolph, T. Creating superpositions that cor- respond to efficiently integrable probability distributions. quant-ph/02081 12, 2002.
Sidford, A. and Zhang, C. Quantum speedups for stochastic optimization. Advances in Neural Information Processing Systems, 36, 2024.
Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp- 212-219, 1996.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Tamboli, D., Chen, J., Jotheeswaran, K. P., Yu, D., and Aggarwal, V. Reinforced sequential decision-making for sepsis treatment: The posnegdm framework with mortal- ity classifier and transformer. IEEE Journal of Biomedical and Health Informatics, 2024.
Hamoudi, Y. Quantum
mean estimator. In 29th Annual European Symposium on Algorithms (ESA 2021). . Schloss Dagstuhl-LabbiizzZennrnm für Informatik, 2021.
Jerbi, S., Trenkwalder, L. M., Nautrup, H. P., Briegel, H. J.,, and Dunjko, Quantum enhancements for deep rein- forcement learning in large spaces. PRX Quantum, 2(1): 010328, 2021.
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.
Jerbi, S., Cornelissen, A., Ozols, M., and Dunjko, V. Quan- tum policy gradient algorithms. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2023.
Wang, D., Sundaram, A., Kothari, R., Kapoor, A., and Roet- teler, M. Quantum algorithms for reinforcement learning with a generative model. In International Conference on Machine Learning, pp. 10916-10926. PMLR, 2021a.
Liu, Y., Zhang, K., Basar, T., and Yin, W. An improved analysis of (verience-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7634 2020.
Wang. D.,. You, X., Li, T., and Childs, A. M. Quantum ex- ploration algorithms for multi-armed bandits. Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10102-10110, 2021b.
Mondal, W. U. and Aggarwal, V. Improved sample com- plexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes. International Con- ference on Artificial Intelligence and Statistics, pp. 3097- 3105. PMLR, 2024a.
Wang, D., Gao, N., Liu, D., Li, J., and Lewis, F. L. Re- cent progress in reinforcement learning and adaptive dy- namic programming for advanced control applications. JEEE/CAA Journal of Automatica Sinica, 2023.
Wang. L.,, Cai, Q., Yang, Z., and Wang. Z. Neural pol- icy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Mondal, W. U. and Aggarwal, V. Sample-efficient con- strained reinforcement learning with general parameteri- zation. Advances in Neural Information Processing Sys- 2024b.
Wiedemann, S., Hein, D., Udluft, S., and Mendl, C. B. Quan- tum policy iteration via amplitude estimation and grover search- towards quantum advantage for reinforcement learning. Transactions on Machine Learning Research, 2022.
tems,
Montanaro, A. Quantum speedup of monte carlo meth- ods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471 47102181):001503001 2015.
Wu, Y., Guan, C., Aggarwal, V., and Wang, D. Quantum heavy-tailed bandits. arXiv preprint arXiv:2301.09688 2023.
Nielsen, M. A. and Chuang, L. Quantum computation and quantum information. Cambridge university press, 2010.
Xu, P., Gao, F., and Gu, Q. Sample efficient policy gradient methods with recursive variance reduction. In Interna- tional Conference on Learning Representations, 2019.
Paparo, G. D., Dunjko, V., Makmal, A., Martin-Delgado, M. A., and Briegel, H. J. Quantum speedup for active learning agents. Physical Review X, 4(3):031002, 2014.
Zhang, K., Koppel, A., Zhu, H., and Basar, T. Global con- vergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimiza- tion, 55565666335663311,, 2020.
Peters, J. and Schaal, S. Natural actor-critic. Neurocomput- ing, 71(7-9):1180. 180-1190, 2008
10

---

Accelerating Quantum RL with Quantum NPG Based Approach
Zhong, H., Hu, J., Xue, Y., Li, T., and Wang. L.. Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret. In Forty-first Interna- tional Conference on Machine Learning, 2024.

---

Accelerating Quantum RL with Quantum NPG Based Approach
A. Proof of Lemma 4
A.I. Quantum Superpositioned Trajectories
We first explain the construction of the required unitary UP((>) step by step, showing it uses one call to the initial-state oracle Up and O(N) calls to the transition oracle Up and policy oracle
Initial registers. We start with the following (quantum) registers:
A register (0) containing the policy parameters (which will remain untouched except as control for IT).
state registers (0.s...... 10)s SN-1
action registers A0) :....
(0) AN-1
Thus the total initial state is
(0) 22N
(0)
Load the initial state.
We apply Up (see (5)) to the first state register So. which transforms
10)
Me
Σ
Vp(5o) s0)so
So
#oES
The other registers remain in the all-zero state. Therefore, the global state becomes
(0) x Σ
so)s 2 10)s, ... 10100ss o 10) ... 10) AN
#
Iterate over & O....,N .....NN..
For each time step we perform two sub-steps:
1. Policy oracle IT. By definition (see (6)), IT implements
I::
(0) (8) 10)
-
10) (8)
V (als)) (a.
GEA
We apply 11 to 10), the state register S,, and the action register A.. This sends
(s))s. ()),.
|st)s.
To(aa)s)) V=l(alls)laa))n
a.EA
2. Transition oracle Up. By definition (see (4)), Up implements
Ur (8x) (az) 10)
Ise) las)
Σ
v P(se+ ar) (s(t1)-
We apply this to registers S., Ar, and S,+1, which transforms
st., ac, 0)
+ |st, (t)
Σ
(((st+lls, at) s241))
51-1E8
After applying II and Up at each step the amplitudes multiply to give
To((ae(s)) x v (())
12

---

Accelerating Quantum RL with Quantum NPG Based Approach
Final state.
After these N steps, the global state is
N-
0
Σ
v
II
v (T((a)))) P(5 50, do: 81, 01 SN-1.ON-1)
90. 90 on #N-1, -N-1
t=
Observe that the squared amplitude of each trajectory oN matches exactly Po(TN). Hence,
Up((x):
(0) 10)
(0) Σ
Po(TN) (T).
TN
Query complexity.
We call Up once to load in the register Su-
For each step ................................ N 1, we call IT once and Up once.
Thus, the total number of queries for one sample of Uo) to the "environment policy" oracles is 1 1+ 2N = O(N).
A.2. Quantum NPG Estimators
1. Constructing the superposition (Va). By A.I, we have unitary
Up(s)) (0) [0) 10)
(0) Σ (PP(TN)(TN))
implemented via one call to Up and ((N) queries to the transition oracle Up and the policy oracle II. Hence we can prepare
( 10) Σ
(Po(TN)(TN)
coherent superposition over all length-N trajectories TN with amplitudes / Po(TN).
2. Defining the estimators F and 9p-
We recall the definitions in (14) and (15):
(p( Σ
Va log (a(()s))) (7" an)a)
N-1
OT( = (1-
Σ ==0
ymh
Vo log (anlls))) @ Voo log To (2o0aa To(allsn))
Because To(-I-), r(.)), -), and discounting can be computed classically in polynomial time, these functions are straightforwardly computable given full knowledge of TN-
3. Quantum evaluation of classical fuunction. A standard result in quantum computing states that any efficiently computable function fIx admits a polynomial-size quanturm circuit implementing
(x) 10) - |x) lx()))
in coherence. Applying this principle:
Let Up be the unitary that computes (TN (0) given Concretely:
Ur (TN) [0) (TN) (Tv((0))
Let Uy be the unitary that computes (Tx () similarly.
These circuits require no additional calls to the environment oracles, since they merely read off the classical data (st, oz) in the registers and perform the classical computations needed for Vo log no, discounting, and rewards.
13

---

Accelerating Quantum RL with Quantum NPG Based Approach
4. Acting on the superposition (o).. Once we have (Vo) E0 (o((TN) (Ty), append auxiliary register (0) and apply Up or Mg in superposition. By linearity:
(Td s Ur) (IWo) 10)) 103 Σ v Po(TN) (Tw) [F(()])))
Analogousty for Ug. This precisely shows
UF (oo) @10) = E
(P)(TN)) @ (Tx()))))
TM
and similarly for (T(
Query complexity.
Preparing the superposition (e)): This needs ((N) queries to Up (the transition oracle) and II (the policy oracle), plus one query to Upp-
Computing Fg or 9p in superposition: The unitaries Ur and Mg are classical function simulations that do not require extra queries Up. They simply the (st, ar) registers directly.
Hence, the overall cost in environment queries remains O(N) for a length-N trajectory.
B. Details of Quantum Variance Reduction
Algorithm 2 @Varianceeeeucc.. (Algorithm 2 in (Sidford & Zhang, 2024))
1: Input: Random variable X, target variance 6², Quant unteattstmmaatttttiaa. from Algorithm 3
2: Output: An unbiased estimate ja of X with variance at most o²
3: Set juo <-uant L0MuantttMMeEnEe imat inn (X,
4: Randomly sample j Goom (2) E N
5: ïá < --QunntumMeanEsttiiieene ima on (X,2-3//4// 100
6: ĀJ-1 Q stteetaaMtaataaaiiiioo
(X, 2-j 30)13)11443)3 110)
7: A - +222 1))
8: Return: A
Algorithm 3 QuanttueeannESttimeeei
(Algorithm in (Sidford & Zhang, 2024))
Input: Random variable X, target variance 8² < L?, QuarttmmeennEstmmatiooo from Lemma 1, parameters
= / and D = & + 167
a²
2: Output: An estimate ja satisfying E [[X]] g2
3: Set X1 E-QuantumMeantee
(aa.iinnt.io/./.aaaaaa.aa 0/4,))
4: Randomly draw a classical sample X2 of X
5: if ||X,, Xxlll < D then
6: Return: X₁
7: else
8: Randomly draw one classical sample X3 of
9: Return: X3
10: end if
Algorithm is the detailed description of QVarianceRedice, which provides a quadratic sample complexity speedup shown in the following Lemma:
Lemma 7 (Thcorem of (Sidford & Zhang, 2024)). Algorithm returns the desired result using expected Ó(L queries, with random variable X having dimension and variance bounded by T.?.
14

---

Accelerating Quantum RL with Quantum NPG Based Approach
B.1. Proof of Theorem
This is direct result of combining Lemma with the variance bounds of (0(TN(() and Fo(TN (0) in (30).
C. Proof of Theorem 1
For fixed 0, we first note that ((T(0) and F(r(0) constructed as below would be an unbiaed estimator for VoJa(0) and (0):
g(T Σ
Vo log mo(aals)) (f"r(sn, an)),
(40)
R=0
t=
= (1-
Σ
V log Te(an) @ log (a(nl)))))
(41)
n=0
where 7 (50, do....., 8k. ag...... is an infinite length trajectory, generated by taking policy with so sampled from p. (40) is a standard expression of the policy gradient unbiased estimator used in (Baxter & Bartlett, 2001; Liu et al., 2020). To prove that (41) is an unbiased estimator of F (0)), note that
E, [F([]]]] (p,
7)
Σ ?" V log (an (n)) @ V log (e Sn))
(42)
(1 - 7)
Σ
"Er Vo log lonlls))) & laggmalnllsn)
(43)
n=
= (1 7)
n
Pr(sn =
@ Vo Tols)
(44)
==0
5,a
Pr(ss s) Logg @ Vo (og
(45)
n=0
Vol (aals)
V lo
(46)
Σ
(o(8sa)VologTT(ab)) @ Vo log (a|s)
(47)
(0)
(48)
Therefore we have
|| [ = [[ 0)] - E[g((T 0)]l
V log )o((a))s) (m)))
E
12
20
< G Σ
(n + 1)>"11
N=N
N
+ ?
(1- 7/ )
(49)
1-7
Furthermore, we have
E [lg (0)] < E (TN (0) (TN [0)] + E [ (o)
(50)
Since we also have [TN)(TN S (1->)= from Lemma 2, we further have
dG²
Var(g, E (Tx ETG.
(51)
(1 71-
15

---

Accelerating Quantum RL with Quantum NPG Based Approach
Since E (T (0) [Tgg((Tx()) S /B Bll 0) (l and (51) we obtain (27). Similarly,
[0] due Jensen's inequality, combining (49), (50)
[[ -,00))1;(00011011 = [| (TN -
= B (1 (1-7) Σ
(Ve log (e(n)())) @ Volog mon
n=N
- G2
(52)
Furthermore, we have
[[| - (o)) S 1BII 0) (T [0]III + DEI [[I (x(
(53)
Since [0]] < G?, which is by the definition of (T (0). we further have
Var(Fx(TN10)) E F1 E(,, dG
(54)
Since E EI (Tv)(( &
due to Jensen's 's inequality, combining (52), (53) 110 - -
and (54) we obtain (29).
D. Proof of Lemma 5
Since Algorithm 2 outputs an unbiased estimate of the input, we have that for any 0, (E[F((TN()) Flön] and EL = El Thus, (31) and (33) directly follow from (26) and (28). For (32) and (34), we note that
[10x Jo (0)1 = IE [llø> E(gx) + (()))) - VOJa( = [l F(O)) + B(rr) - (o)I (55)
since the cross term contain [E|gn - B(Gh)). )}, which equals to zero. We further have
N+
B(x)) - vaJa(0)11 < G2
2N and E [ll., - E(gh) [1 S o
(56)
1-7
(1-
Combining the above two equation we obtain (32). (34) can be derived by the same procedure. We have
[ (0) E [I|Ai E(Fx) + ((F.) (0)1 E [1] E(F.) + [(F) (1)11
(57)
since the cross term contain EE - E..F which equals to zero. We further have
2422N
- [F(0)) < (1 7] and EE [1] I0 1( <
(58)
Combining the above two equation we obtain (34).
E. Proof of Lemma 6
Throughout the proof. we assume a fixed th iteration of outer loop with the fixed policy parameter 0z. Let V.Ln LWw, TN) TN) = Fr,ux - gh. To prove the first statement, observe the following relations.
||-+11 - wf1l2
|| - a V Ln - wfll?
||ا/ wžll2 - -2alwn - wt. V. L.) a² IV
||~ wxll²- 2a(wun -tt, (0k) ) (wh wii))
2ar(un - -tt v.Ln - F2 (wn - wF)) + a² a In
||w w - 20 1|w will - 2a(wn wt. vuin F,(02) - wx))
+ 22 Ln (,(0))(un w2)11 + 2a²2 F,(()) (0x) - wl)ll
||w w - 22/4F |w/ - w/ll 22 - w/. V.LLn - (Ox wF))
2222|1 In (0x) wf)ll 2 a² 222lwh wI1l
16

---

Accelerating Quantum RL with Quantum NPG Based Approach
where (a) and (b) follow from pe - [|Fp(00)]l S G². Taking conditional expectation on both sides, we obtain
B [Wh+1 - wutl"] $1 - 2apr + 2G²aa )|wn - wEll? - 2axwin - wh IE V Ln - Fo(Ox)(wn - wxt))
+ 20 2 E V In - (w) - wiill
(59)
Observe that the third term in (59) can be bounded as follows.
In - (w( - w;)
|1 Pi. (o(0)))(un - w/) + (Fr - (o(0)))uu + -v) =1)
S 3|| Fn Ex(0))111Kk> - will + 3 Fn
+ o./ - 3%
S F/ 1o(04)11111n - = + 3 2 6²
|1 12 + VoJ 91
(1- 7)
Mウ [[- where the last inequality follows from ||w||²= (0-(00)--00,,(000 S
Taking expectation yields
E L - (wn - w2,)11
$3E |F Fp(0k)11 |wn - will + 3 G2
E F 22 (. 1
(1 1-77) 7)
|| - will + 3/FF 2 G2 ( (0z + 8x) + (35² و
3 07 + 8%
+ 38²)
(60)
(1 7)4
The second term in (59) can be bounded as
(Wh wh:
V. (ww)) will)
PP
|w~ wāll2
1
B In (w - -+ti]( ||
4
Pr
Pr
{E(FN) - -F((OL) wn + (VoJo(O)) - E [ā
|w - -will +
4
HF
(20%) + 288)) ) 1wal12 + (203 + 26²)
PP
|w -wll? +
4
NF
46% + 403) |w - ww]ll + (107, + 48%)
Me
+ (20² + 28g)
$ PF
|ا - wxll2
(61)
4
pr 22 where the last inequality follows from || - (e))2(001 2 (1-.5.. Substituting the above bounds in (59). we have
E [[la++ - =
< 1 3aFF
8a07
+ 6a² (0z +8²) + 20²
1w - wfll+++ +
4a Pe
20 MF 2 G2
+
82
PF
(1 7)
MF 2 G2
(0) + 82)) + (0² 88)
+ 2
[1 7)
For 8r S 1r/88, and a S /= + 68% + )G we can modify the above inequality to the following.
El|la]1- - wf]l < (1 (upr) ||a 2|12 2 + 4a
28
IF
202
+
83
+
6a²
11 0=
(0%+833
+ 83)) +063 + +8?)
up
(1 - 7)2
11-
17

---

Accelerating Quantum RL with Quantum NPG Based Approach
Taking expectation on both sides and unrolling the recursion yields
B||lw wxll")
< - auu) " B IWO wwil" +
Σ (1 - a0)))))))
{ [4x
28% G2
(1 (1-7)] 88g
+ 6a²
Mp G2
(0% + +3+) + (8x + 83
}
HP
(1 71-
exxp (-HHur) E|/00 - will
4a
28' Pp C2
+ 89
+ 6aa
1F G2
(07 + 8/) (o) + 8
aper
(1 7);
7)5
Mp G²
G²
(0z + 83) + (6² + 82) }
exp ((l - will +
1ppp 2
20
+
82 g
+ 6app
(62)
(1 73
7)8
To prove the second statement, observe that we have the following recursion.
[[ wgll = || [[[n]] - a EVVLLll - wIl?
[[wn] will - 20 (TEnn] wh. E(g. + E LLII?
|| [[/r]] wžl? - 20 (E[wn] wh. F,((0) wi))
2a<B[un] w W.V Ln] (((O)) - wF)) + a² V LAl1
(a)
S B[[a]] - wfll - 20 B(wn] - w|ll - [0(1[[N] wh. E w Ln] - F (O)) w2))
+ B - (Ox)) (W)) - wB)1l + 2a || (0 (0x) [E[wh] 12
N || [[[w]] - w/ll 2 2 B[wn] - will= -
- w B V Ln] Fg (OW)(NN - wF))
+ 2a22 E [.]] - (0x (B[W)) - -w + 2G a3|l B[wm] wîll
$ (1 2apr + 22G [[[]] wfll2 - (E(wa) wt, E V (0x))) wF))
2a²
in! (0,( - -
(63)
where (a) and (b) follow from μr S [1 S G2. The third term in the last line of (63) can be bounded as follows.
E ~ [m] - (B( - -6]11
[ (Fr - FF(())) - w + (B[FA) - (0x))u + (VoJ.(0)) - E[GhD)
< 3
[[ (x(O))1 || - ud[[]] +3E [| - (=(0))1)] ( + (()))((0)) E[
3 87. + +302
< 38% E
[[ww = + (1 [1-7)" 7)1
(0)
I 38%
[|WW w || + aRo + RR }
+ 3pF² 2 G2
87 + 353
(1- ---
where Ro = .
+ + (63 +82)
R1 4uF²
[1- + [3] and (a) follows from (62). The
28 up 6²
second term in the last line of (63) can be bounded as follows.
[E[[n]
w
E
[.n]
(p((0)) (O) [Wn] - -wiil w
MF
[[wn]
E
w
2
+
1
EV In] (B(())) - -
E
μr
pr <
2X|l++
w
+
3
[3
[wo wxll aallo + 181 }
+ Mr G22
83, + 82 (1- 7)
4
18

---

Accelerating Quantum RL with Quantum NPG Based Approach
Substituting the above bounds in (63), we obtain the following recursion.
E [[wa+1] wtll?
+ 2
|| [[[[wa] wtll
+ 6a (a+
8/
E Ilwo - w1ll3] + aRo + Rı
Pp G2
8P + 89
(1 71-
MP
If <
J.P. 4G the above bound implics the following.
[[wn+i] w1ll < (1 (upF) B[wr]] - wfll
E [l[w - - + aRo + Rí R1} + Pr G2
+ 6a
(a+ pe
8%
87 82
(1 - 7) 7)-
Unrolling the above recursion, obtain
[[wu] will
S (1 aFF) H
|| B[waol whll
+ Σ 6 - (11-) a a PF
#-1
1
[|w will + a + R1 a + (1- 7)4 87 + 84
G2
h=0
exp exx((HHau)) [[[oo] will+
6
(a+
_
82
E [[lwo =1lli] aRo Raj ) )
(1 - 7) 83 + 87)
PF
pr
This concludes the result.
F. Proof of Theorem 3
Combining Lemma 6 with Lemma we get the following bound for appropriate choices of the learning rates as mentioned in the theorem.
K J
HafFF
[[Jp(0s)] S Vehias + Gexp
[[[]]] w01 + C2
K
2
(64)
B +
+
G²
exp (-HouFF E Iwo - w01 Cs C4
AT.
B
2 G
G2
B 4LE [KL( (K
with C2 GVC1, C3
G
Co and C2
Where
4L
k2P
2 K
1 y
Co and C1 are defined in Lemma 6. By replacing C₁ = 0 (
we can express (64) as follows:
1
[[J,(Ok) Vibias + 1(c-#)++0 +0(120
o7. (1 (1- 89
+ +0 K
J
(65)
K k=0
To obtain the optimality gap most VEbias e, we choose H (log(E 1)), Olog(E 1)) 0, 0(e)
and 0z- O(11 -)). By Theorem 2, Ö sample complexity of Ö(HKN- (1-9PV)) (11/c155 and an iteration complexity of O(K) Ö(1/c).
Gdd
queries of Ur and Ö ( Gd
( queries of Uy. This results in
(1-4)²-
19


Reviews:
[{"review_id": "yYrClDwCa5", "reviewer": "Reviewer_iAMi", "summary": "This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm aimed at accelerating quantum reinforcement learning. The key idea is to replace the classical random sampling in natural policy gradient estimation with a deterministic gradient estimation method that can be integrated into quantum systems via quantum oracles. The authors claim that by doing so, they can achieve a sample complexity of O ̃(ϵ^(-1.5) ), which improves over the classical lower bound of O ̃(ϵ^(-2) ). The paper presents a thorough theoretical analysis, including convergence proofs and bias–variance trade-off evaluations, and provides detailed constructions of the required quantum oracles.", "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": "Thank you for your detailed feedback and constructive comments. We address your concerns and questions clearly below:\n\n## **Response to Weaknesses 1, 4, and Question 1:**\n\n**Practicality of Quantum Oracle Implementations and Experimental Validation**:  \nWe acknowledge the reviewer’s valid concerns about the real-world implementation of quantum oracles and experimental validations. Our current work is primarily theoretical, and extensive numerical experiments and implementations are planned as future work. Importantly, the quantum oracles required by our algorithm can be implemented with polynomial cost on quantum computers as shown in [1]-[3], posing no conceptual barriers. However, classically simulating these oracles is NP-hard. We can ofcourse simulate for a very small scale, but that will not help validate in a larger example.   Future studies will aim to implement and validate our methods on quantum simulators or quantum hardware.\n\n## **Response to Weakness 2:**\n\nGiven additional page in the final version, we will work on adding explanations. Further, we appreciate the reviewer’s suggestion regarding the complexity of Lemma 6's proof. While we have provided detailed explanations and derivations for each steps of the proof in the Appendix, we agree that further clarification could help readers that are unfamiliar with the specific concepts involved understand better. To clarify, we summarize the high-level idea of the proof as follows, which we will incorporate into the final draft:\n\n \"The proof of Lemma 6 proceeds by first expressing the error between the estimated gradient and the ideal gradient as a recursive update from the inner-loop iteration. It then demonstrates that each update contracts the error exponentially, meaning the error shrinks by a fixed multiplicative factor with each iteration. Subsequently, the proof carefully bounds the additional errors introduced by truncation bias and estimator variance, leading to explicit residual terms. Finally, these contraction and residual terms are combined through a recursive argument to establish the overall error guarantees.\"\n\nIf you can provide some specific comments for confusing symbols, we would appreciate that so that we can revise them in the final version. \n\n## **Response to Weakness 3:**\n\n**Comparison with Existing Quantum RL Algorithms**:  \nWe clarify that, to our knowledge, there are currently no quantum reinforcement learning algorithms with provable guarantees for general parameterization setting in the existing literature. Thus, our approach introduces significant novelty in providing theoretical foundations and complexity improvements as compared to classical and prior quantum algorithms.\n\n## **Response to Question 2:**\n\n**Validity of Score Function Assumptions**:  \nWe note as we stated after the assumption, regarding Lipschitz continuity and smoothness of the score function, this assumption is common in reinforcement learning literature, and can indeed be verified for commonly used parameterized policies, such as softmax policies [4] and Gaussian policies, where the action is modeled as a Gaussian distribution, with parameters (mean and standard deviation) learned from the environment [5]. The assumption is necessary since without this,  we would have unbounded gradients.\n\nThank you again for your thoughtful comments. We hope these clarifications enhance the clarity and impact of our contributions.\n\n\n## **References**\n[1] Implementing Grover oracles for quantum key search on AES and LowMC, 2019\n\n[2] Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures, 2021\n\n[3] Verified Compilation of Quantum Oracles, 2022\n\n[4] On the Theory of Policy Gradient Methods:\nOptimality, Approximation, and Distribution Shift, 2021\n\n[5] An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods, 2020", "claims_and_evidence": "Most of the submission's claims are supported by relatively clear and convincing evidence. The paper first builds on established concepts in quantum computing and reinforcement learning, such as quantum mean estimation and MDP formulations. For the QNPG algorithm, the authors derive the estimators for the policy gradient and Fisher information matrix and analyze their biases and variances. A series of lemmas and theorems derives the sample complexity and convergence results.\n\nHowever, the assumption of access to quantum oracles might be a bit idealized. Implementing these quantum oracles could be extremely challenging in real-world scenarios. The paper claims that any classically computable policy can be converted into a quantum-evaluatable unitary operation, but it doesn't fully address the practical difficulties and overheads associated with this conversion.", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem at hand. Using quantum oracles to sample from the environment and initial state distribution and constructing quantum-compatible estimators for policy gradients are innovative ways to apply quantum computing to reinforcement learning. The evaluation criteria, mainly based on sample complexity and convergence analysis, are appropriate for measuring the algorithm's performance in the context of policy optimization.", "theoretical_claims": "I have checked the correctness of the proofs for the theoretical claims. The proofs of lemmas and theorems are generally well-structured. For example, in the proof of Theorem 1, the authors compare the truncated estimators with their infinite - horizon counterparts to analyze the bias introduced by truncation. The use of Jensen's inequality and other mathematical techniques is appropriate.\n\nHowever, in some of the proofs, the steps could be made more explicit. For instance, in the proof of Lemma 6, the bounding of some terms might be a bit difficult to follow for readers who are not extremely familiar with the specific notations and concepts in the paper. Some additional explanations about the inequalities used and how they are derived would be beneficial.", "experimental_designs_or_analyses": "Since the paper is mainly theoretical, there are no traditional experimental designs in the sense of running experiments on physical quantum systems. The analysis is mainly based on theoretical derivations of sample complexity and convergence. The soundness of these analyses depends on the validity of the assumptions made, such as the smoothness and Lipschitz continuity of the score function. If possible, some numerical simulations on quantum simulators to demonstrate the practical performance of the QNPG algorithm would strengthen the paper. Also, sensitivity analyses of the parameters in the algorithm (e.g., the discount factor γ, the learning rate η ) could be included to show how they affect the performance.", "relation_to_broader_scientific_literature": "In the area of quantum computing, the paper builds on the concept of quantum mean estimation, which has shown quadratic improvement over classical methods. In reinforcement learning, it extends the classical Natural Policy Gradient algorithm to the quantum domain. Compared to previous works, this paper is the first to coherently embed the entire NPG into a quantum state using standard RL environment oracles. It also demonstrates quantum speedups for parameterized model-free infinite-horizon MDPs, while most existing QRL works are limited to tabular setups.", "essential_references_not_discussed": "There are no obvious essential references that are not discussed in the paper. The authors have cited a comprehensive set of related works in the fields of quantum computing, reinforcement learning, and quantum reinforcement learning.", "other_strengths_and_weaknesses": "Strengths\n\n1: It introduces a deterministic gradient estimation in quantum RL, offering a new way to use quantum computing in RL, which is different from traditional methods.\n\n2: Conducts thorough convergence, sample complexity, and bias-variance analyses.\n\n3: It has an extensive literature review that effectively positions the research within the existing knowledge in quantum computing and RL.\n\n4: The QNPG algorithm may enhance RL-based decision-making in various fields, like robotics and finance, due to its improved sample complexity.\n\n5: It integrates quantum computing concepts well, leveraging quantum features through oracles and exploring a new area of quantum-enhanced RL.\n\nWeaknesses\n\n1: Assumes accessible quantum oracles without discussing real-world implementation challenges.\n\n2: Some sections, especially those with proofs and complex math, are hard to follow. Simplifying notations and adding explanations is needed. \n\n3: Mainly compares with classical algorithms, lacking sufficient comparison with modern quantum RL algorithms to show relative performance. \n\n4: Lacks experimental validation", "other_comments_or_suggestions": "Some symbols in the Markov Decision Process (MDP) and in quantum oracles are confusing. They may be unified or require more explanations.", "questions_for_authors": "1. Given quantum oracle implementation challenges, how can the QNPG algorithm be made more practical in real-world scenarios? \n\n2. In convergence analysis, score function assumptions may not hold for all policies. How would the QNPG algorithm performance change if so?", "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": "EPRTA3VBYf", "reviewer": "Reviewer_xwF3", "summary": "The paper introduces a novel Quantum Natural Policy Gradient (QNPG) algorithm aimed at accelerating reinforcement learning (RL) in quantum computing environments. The authors introduce QNPG, a quantum-compatible variant of the classical Natural Policy Gradient (NPG) algorithm. The key innovation involves replacing the classical stochastic gradient estimators with deterministic gradient estimators based on truncation methods. The sample complexity is improved from $\\mathcal{O}(\\epsilon^{-2})$ to $\\mathcal{O}(\\epsilon^{-1.5})$.", "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 thoughtful comments and valuable feedback. We address the main points and questions raised as follows:\n\n## **Response to Weakness 1 and Questions 1-3:**\n\n**Why Quantum Computing Accelerates Mean Estimation (Lemma 1)**:  \nQuantum computing fundamentally accelerates mean estimation through the Quantum Amplitude Estimation (QAE) algorithm [1]. Quantum states inherently encode probability distributions directly into their amplitudes, allowing QAE to estimate probabilities and expectations using methods similar to Grover iterations [2]. This results in a quadratic speedup in terms of accuracy and the required number of queries or experiments compared to classical sampling methods.\n\n**Quantum Acceleration in Convergence Analysis (Lemma 5)**:  \nWe agree that Lemma 5 is central to the speedup presented in our paper. Specifically, quantum computing provides variance-reduced estimators for $F_h$ and $g_h$. Compared with classical NPG, our quantum estimators achieve quadratically reduced variance. However, this reduction introduces a bias-variance trade-off absent from classical NPG, which traditionally provides unbiased gradient estimators.\n\n**Key Novelties**:  \nWe thus sum up our key novelties. The introduction of biased estimators in our quantum NPG algorithm is due to the use of truncated estimators for the Fisher information and policy gradients, which are necessary for compatibility with quantum RL oracles (Equations 16-17). This truncation introduces a bias absent in classical estimators. Specifically:\n\n- Classical NPG methods rely on stochastic algorithms that sample the NPG gradient from trajectories of random length, typically following a geometric distribution. However, we cannot achieve quantum superpositions of trajectories with random lengths due to fundamental quantum computational constraints. Consequently, we adapt the classical algorithm to deterministically truncate trajectory lengths.\n- This deterministic truncation changes the classical unbiased estimation approach into one that inherently introduces bias. Therefore, we modify the methods of estimating the Fisher information and gradient estimators, replacing geometric distribution sampling with deterministic truncation.\n- To rigorously address the bias introduced by truncation, we significantly adjust the analytical framework. Specifically, Lemma 4 quantifies complexities associated with obtaining quantum superpositions, and Theorem 1 explicitly bounds the biases and variances resulting from truncation. Lemmas 5 and 6 subsequently utilize these bounds, meticulously handling bias accumulation and variance reduction through modified analytical techniques and recursive error bounding methods.\n\nThese methodological adaptations and theoretical analyses represent substantial novelty over classical NPG algorithms and are crucial to achieving our main theoretical results.\n\n## **Response to Weakness 2 and Question 4:**\n\n**Numerical Experiments**:  \nWe acknowledge the reviewer's concern regarding the absence of numerical results. The primary objective of this paper is theoretical, and thus detailed numerical experimentation is intended as future work. While implementing quantum oracles on an actual quantum device would be of polynomial complexity and presents no conceptual challenges, simulating these oracles classically is NP-hard. We can ofcourse simulate for a very small scale, but that will not help validate in a larger example.    \n\n\nThank you again for your valuable comments. We hope these clarifications clearly articulate the novelty and significance of our contributions.\n\n## **References**\n[1] Quantum Sub-Gaussian Mean Estimator, 2021\n\n[2] A fast quantum mechanical algorithm for database search, 1996", "claims_and_evidence": "The sample complexity is supported by proofs.", "methods_and_evaluation_criteria": "Using quantum computing to accelerate classical NPG algorithm makes\nsense for RL.", "theoretical_claims": "I have roughly checked the proof of Theorem 1 and Lemma 5, and it looks\nreasonable and correct.", "experimental_designs_or_analyses": "No experimental designs.", "relation_to_broader_scientific_literature": "This paper is related to application of quantum computing in RL.", "essential_references_not_discussed": "This paper has discussed essential references.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Application of quantum computing in RL may a new trend in these years. The method of this paper looks applicable for real-world problems.\n\nWeaknesses:\n\n1. One possible weakness is the lack of novelty. It seems that quantum computing is only used in estimating $g_h$ and $F_h$ in algorithm 1, and the quantum computing algorithm (Lemma 1) is also the result in previous literature. The proof also follows the proofs of classical NPG with application of Lemma 1.\n2. The paper lacks numerical results. As the paper is about accelerating algorithm with quantum computing,  the numerical experiments is important to show the accelerating effects.", "other_comments_or_suggestions": "It would be better to explain why quantum computing can accelerate the mean estimating. And I suggest you add more explanation about the notations of quantum computing in section 2.3.", "questions_for_authors": "1. Could you explain why quantum computing can accelerate mean estimating in Lemma 1?  It seems that it is the key step to improve the sample complexity, right?\n2. In the aspect of convergence analysis, could you mention how quantum computing improves the complexity? If I understand correctly, it only appears in Lemma 5, right? \n3. Based on previous two questions, could you explain more on the novelty? It looks like that quantum computing algorithm is old and the proof just follows NPG.\n4. Could you add numerical results to show the accelerating effects?\n## update after rebuttal: I raise the score from 2 to 3. Please refer to the comment below for reason.", "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": "o4BT85YnKF", "reviewer": "Reviewer_XwLv", "summary": "In this paper, the authors introduce a novel algorithm called Quantum Natural Policy Gradient (QNPG). In QNPG the classical Natural Policy Gradient (NPG) estimators are replaced with a deterministic gradient estimation approach. Theoretically they show that QNPG achieves a lower sample complexity for queries to the quantum oracle/MDP in comparison to the classical lower bound for queries to the classical MDP.", "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": "Thank you for your positive feedback and valuable insights. We address your primary concerns clearly below:\n\n## **Clarification on the \"Model-Free\" Nature of QNPG:**\n\nWe appreciate the insightful discussion about whether our Quantum Natural Policy Gradient (QNPG) algorithm should be considered \"model-free\". Indeed, we agree with the reviewer that we explicitly assume the existence of a quantum transition oracle. However, our use of the term \"model-free\" aligns with the standard distinctions within reinforcement learning literature:\n\n- Classical **model-based** reinforcement learning algorithms explicitly attempt to learn or estimate the transition dynamics (state-action probabilities) of the environment from sampled data. This learning process typically introduces a complexity that scales directly with the size of the state-action space \\(|S||A|\\), making it computationally expensive for large environments.\n\n- In contrast, our QNPG algorithm does not explicitly attempt to estimate the environment's transition probabilities. Instead, we directly use the provided quantum transition oracle to sample trajectories and estimate gradients without explicitly estimating or storing transition dynamics. Consequently, the sample complexity for parameterized model-free methods (like our proposed QNPG) does not scale with \\(|S||A|\\). Instead, it depends primarily on mixing times and related properties, reflecting a fundamentally different complexity structure from traditional model-based methods.\n\nWe note that the use of quantum transition oracle is like the use of generative models in classical decision making, and thus unless the transition dynamics is learnt, the algorithm is denoted model-free. This important distinction will be further emphasized in the final version of the manuscript.\n\n## **Regarding Numerical Results:**\n\nWe acknowledge the reviewer's point regarding numerical experimentation. The current focus of our work is theoretical, and comprehensive numerical experiments are planned for future studies. We clarify that while implementing quantum oracles in actual quantum computers is feasible with polynomial complexity and no fundamental conceptual barriers, simulating these oracles classically is NP-hard.\n\nWe greatly appreciate your constructive comments and hope these clarifications clearly address your points.", "claims_and_evidence": "The authors state that their method is a quantum analog to classical NPG, which is a model-free RL method:\n“In this work, we introduce the first quantum model-free reinforcement learning (RL) algorithm with theoretical guarantees, addressing the challenges posed by large state and action spaces. To our knowledge, this is the first work to coherently embed the entire Natural Policy Gradient (NPG) into a quantum state by leveraging only the standard environment oracles from reinforcement learning.”\nAs I understood the approach, the claim “model-free RL algorithm” is only valid if the environment of the RL problem is the actual “quantum transition oracle”. For any classical real-world RL problem QNPG could not be used in a model-free way, since the transition oracle U_P would have to be created from prior knowledge or existing data to produce meaningful transition probabilities. However, this would make the method a model-based RL method for nearly every known RL usecase. Creating U_P as surrogate of the real environment from data and optimizing policy parameters in an N step rollout sounds like PILCO (Gaussian processes) or MOOSE (neural networks). And of course, no one would say that PILCO is a model-free algorithm under the assumption that your environment is actually a provided Gaussian process.", "methods_and_evaluation_criteria": "No experiments on benchmarks are conducted. However, I think it would be very helpful to show at least a small example how QNPG is applied and whether empirical results support the theoretic bounds.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Finding novel QRL algorithms with actual advantages over classical ones is of huge interest. I’m not convinced that QNPG can be considered a model-free method, since a quantum transition oracle is needed, which can be considered a model.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "It is an important topic and an interesting new method.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "2i0BjDZFjq", "reviewer": "Reviewer_PwjN", "summary": "This paper presents a method for quantum based NGD for RL that improves the asymptotic scaling of the sample complexity. Building on previous work that analyze quantum mean estimation and variance reduction, this paper shows proves its algorithms achieves O(eps^-1.5) sample complexity (over the classical -2).", "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": "Thank you for your constructive feedback and insightful comments. Below we clarify and address the points raised in your review:\n\n## **Regarding Novelty:**\n\nWe appreciate the reviewer’s concern regarding the novelty of our work. To clarify, our paper is indeed the first in quantum parameterized reinforcement learning to provide a rigorous sample complexity analysis with concrete bounds that surpass classical asymptotic limits. To achieve this, we introduce a novel quantum algorithm incorporating truncated NPG estimators (Algorithm 1), along with a detailed and novel theoretical analysis of the bias-variance tradeoff (specifically Lemma 5 and Lemma 6). This thorough analytical framework constitutes a significant step forward compared to previous quantum reinforcement learning literature.\n\n## **Regarding Integration with raw-PQC:**\n\nThe reviewer’s suggestion on integrating our QNPG approach with raw-PQC is indeed interesting. We note, however, that the policy parameterizations of QNPG and raw-PQC differ fundamentally: QNPG utilizes classical parameterization, whereas raw-PQC explicitly leverages quantum circuit parameterization. Despite this difference, exploring integration or hybrid approaches between these two setups could be an intriguing direction for future research, which we will mention in the future work directions.\n\n## **Regarding Formatting Issues:**\n\nWe carefully re-examined our LaTeX source file following the reviewer's comment on the line spacing discrepancies. Upon checking, we find no use of any command that reduces the line spacing. We believe this formatting inconsistency is likely due to LaTeX's inherent compilation behavior. One thing we see is that $\\hat{g}_\\rho$ is in text, and seems to be taking more space than the text, and thus the space seems to be less due to in-line Math text. \n\n\n## **Regarding Essential References:**\n\nWe sincerely thank the reviewer for highlighting the additional  references. These valuable references will be explicitly cited and discussed in the final version of our related work section. The mentioned RL paper does not study sample complexity guarantee. Further, will describe the literature on Quantum Multi-Armed Bandits where speedup is shown.\n\nThank you once again for your insightful feedback, which significantly strengthens our manuscript.", "claims_and_evidence": "The main claim of the paper is supported by a proof, given its theoretical nature, this is sufficient evidence.", "methods_and_evaluation_criteria": "There are no benchmarks or evaluation criteria. The only method of evaluating the result is what is theoretically derived (which is expected given the nature of the paper).", "theoretical_claims": "I did not find any issue with the theoretical proofs, however, I was not able to check them meticulously.", "experimental_designs_or_analyses": "There were no experiments.", "relation_to_broader_scientific_literature": "The key contribution is the idea that you can take these quantum mean estimation policies and build something that has a provable advantage with it. This is also more relevant than some theory work, since recent developments in the parameterized quantum RL world have shown that this quantum enabled policy is a feasible idea.", "essential_references_not_discussed": "Although much of modern quantum RL focuses on parameterized quantum circuits as the focus, some of the early work of quantum RL is missing (e.g. https://arxiv.org/pdf/0810.3828) which would be worth discussing. Additionally some more recent MAB quantum work would be worth highlighting in the discussion on MAB (e.g. https://arxiv.org/abs/2007.07049).", "other_strengths_and_weaknesses": "A central question for me is the novelty. While originality does arise from creative combinations of existing ideas, the main algorithm is heavily based on the existing literature, and I wonder how much this paper adds to those works which also had asymptotic bounds.", "other_comments_or_suggestions": "Some of the paragraphs look like their line separation is smaller than the others, e.g. 250 right side of page. Additionally, although I recognize this is out of scope for the paper, an integration of the algorithm with something like raw-PQC would be exceedingly interesting.", "questions_for_authors": "N/A", "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 rebuttal was able to resolve most of the reviewers' concerns, the paper's contribution to QRL is considered important and the claims well-founded.

One regret is that no experiments were carried out.
Decision: Accept (poster)