Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes
Authors: Bhargav Ganguly
Yang Xu
Vaneet Aggarwal
Venue: ICML 2025 poster (2025)
Keywords: Quantum Machine Learning
Reinforcement Learning
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes

Abstract: This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of $\tilde{\mathcal{O}}(1)$\footnote{$\tilde{\mathcal{O}}(\cdot)$ conceals logarithmic terms of $T$.}, a significant improvement over the $\tilde{\mathcal{O}}(\sqrt{T})$ bound exhibited by classical counterparts, where $T$ is the length of the time horizon.

Quantum Speedups in Regret Analysis of Infinite Horizon Average- Markov Decision Processes
Bhargav Ganguly" 1
Yang Xu 1 Vaneet Aggarwal
Abstract
the capabilities of classical computers.
This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conven- tional interaction paradigm. Our approach in- volves the design of an optimism-driven tabu- lar Reinforcement Learning algorithm that har- nesses quantum signals acquired by the agent through efficient quantum mean estimation tech- niques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforce- ment Learning. Specifically, the proposed Quan- tum algorithm achieves regret bound of Ó(1)) significant improvement over the O( ((VT) bound exhibited by classical counterparts.
In the realm of Reinforcement Learning (RL). an agent embarks on the task of finding an efficient policy for Markov Decision Process (MDP) environment through repetitive interactions (Sutton & Barto, 2018). RL has found notable success in diverse applications, including but not limited to autonomous driving, ridesharing platforms, online ad recommendation systems, and proficient gameplay agents (Silver et al., 2017; Al-Abbasi et al., 2019; Chen et al., 2021; Bonjour et al., 2022). Most of these setups require decision making over infinite horizon, with an objective of average rewards. This setup has been studied in classical reinforcement learning (Auer et al., 2008; Agarwal al., 2022b; Fruit al., 2018), where ((VT) regret across T rounds has been found meeting the theoretical lower bound (Jaksch et al., 2010). This paper embarks an inquiry into the potential utilization of quantum statistical estimation techniques to augment the theoretical convergence speeds of tabular RI. algorithms within the context of infinite horizon learning settings.
A diverse array of quantum statistical estimation primitives has emerged, showcasing significant enhancements in con- vergence speeds and gaining traction within Quantum Ma- chine Learning (QML) frameworks (Brassard et al., 2002; Harrow et al., 2009; Gilyén et al., 2019). Notably, (Hamoudi, 2021) introduces a quantum mean estimation algorithm that yields a quadratic acceleration in sample complexity when contrasted with classical mean estimation techniques. In this work, emphasize the adoption of this particular mean es- timation method pivotal component of our methodology. It strategically refines the signals garnered by the RL agent during its interaction with the enigmatic quantum-classical hybrid MDP environment.
1. Introduction
Quantum Machine Learning (QML) has garnered remark- able interest in contemporary research, predominantly at- tributed the pronounced speedups achievable with quan- tum computers opposed to their classical analogs (Bia- monte et al., 2017; Bouland et al., 2023). The fundamental edge of quantum computing arises from the unique nature of its fundamental computing element, termed a qubit, which can exist simultaneously in states of O and 1, unlike classical bits that are restricted to either 0 or 1. This inherent distinc- tion underpins the exponential advancements that quantum computers bring to specific computational tasks, surpassing
It pertinent highlight fundamental element in the anal- ysis of conventional Reinforcement Learning (RL), which involves the utilization of martingale convergence theorems. These theorems play a crucial role in delineating the inherent stochastic process governing the evolution of states within the MDP. Conversely, this essential aspect lacks parallelism within the quantum setting, where comparable martingale convergence results remain absent. To address this dispar- ity, we introduce innovative approach regret bound
"qqual contribution 'Purdue University, West Lafayette, IN, USA. Correspondence to: Bhargav Ganguly <bgan- guly @ @eruupuuuuuuuu> Yang Xu wouu720@@urdue.edae Vaneet Aggarwal <annett @ murdu..edu>>.
Proceedings of the 4nnd International Conference on Machine Learning, Vancouver. Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
(-) conceals logarithmic terms of

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
analysis for quantum RL. Remarkably, our methodology cir- cumvents the reliance on martingale concentration bounds, staple in classical RL analysis, thus navigating uncharted territories in the quantum realm.
To the best of our knowledge, these are the first results for quantum speedups for infinite horizon MDPs with average reward objective.
Moreover, is important to highlight that mean estimation in quantum mechanics results in state collapse, which makes challenging to perform estimation of state transition prob- abilities over multiple epochs. In this study, we present novel approach to estimating state transition probabilities that explicitly considers the quantum state collapsing upon measurement.
2. Related Work and Preliminaries
Infinite Horizon Reinforcement Learning: Regret analy- sis of infinite horizon RL in the classical setting has been widely studied with average reward objective in both model- based settings and model-free settings (Wei et al., 2020; Bai et al., 2024; Hong et al., 2025; Ganesh et al., 2025a:b). In model-based methods, a prominent principle that underpins al algorithms tailored for this scenario is the concept of "opti- mism in the face of uncertainty" (OFU). this approach, the RL agent nurtures optimistic estimations of value functions and, during online iterations, selects policies aligned with the highest value estimates (Fruit et al., 2018; Auer et al., 2008; Agarwal et al., 2022b). Additionally, it's noteworthy to acknowledge that several methodologies are rooted in the realm of posterior sampling, where the RL agent samples an MDP from a Bayesian Distribution and subsequently enacts the optimal policy (Osband et al., 2013; Agrawal & Jia, 2017: Agarwal et al., 2022a; Agarwal & Aggarwal, 2023). In our study, we follow the model-based approach and embrace the OFU-based algorithmic framework intro- duced in (Agarwal et al., 2022b). and we extend its scope to an augmented landscape where the RI. agent gains access to supplementary quantum information. Furthermore, we render a mathematical characterization of regret, revealing a (1) bound, which in turn underscores the merits of astutely processing the quantum signals within our framework.
To this end, the following are the major contributions of this work:
1. We introduce Quantum-UCRL (Q-UCRL), a model- based, infinite horizon, optimism- driven quantum Re- inforcement Learning (QRL. algorithm. Drawing in- spiration from classical predecessors like the UCRL and UC-CURL algorithms (Auer et al., 2008; Agarwal et al., 2022b; Agarwal & Aggarwal, 2023), Q-UCRL is designed to integrate an agent's ss optimistic policy ac- quisition and an adept quantum mean estimator, and is the first quantum algorithm for infinite horizon average reward RL with provable guarantees.
2. Employing meticulous theoretical analysis, show that the Q-UCRI, algorithm achieves an exponential improvement in the regret analysis. Specifically, it attains a regret bound of Ō(1), breaking through the thcoretical classical lower bound of (2(VT) across T online rounds. The analysis is based on the novel quantum Bellman error based analysis (introduced in classical RL in (Agarwal et al., 2022b) for optimism based algorithm), where the difference between the performance of policy on two different MDPs is bounded by long-term averaged Bellman error and the quantum mean estimation is used for improved Bell- man error. Further, the analysis avoids dependence on martingale concentration bounds and incorporates the phenomenon of state collapse following measurements, crucial aspect in quantum computing analysis.
Quantum Mean Estimation: The realm of mean esti- mation revolves around the identification of the average value of samples stemming from an unspecified distribution. Of paramount importance is the revelation that quantum mean estimators yield a quadratic enhancement when juxta- posed against their classical counterparts (Montanaro, 2015; Hamoudi, 2021). The key reason for this improvement is based on the quantum amplitude amplification, which al- lows for suppressing certain quantum states w.r.t. the states that are desired to be extracted (Brassard et al., 2002). In Appendix B, we present a discussion around Quantum Am- plitude Estimation and its applications in QMI..
3. We design a momentum-basse tions (21)-(25) that fuses each epoch's 's fresh quantum mean estimate with all past estimates using counts- based weights. The resulting algorithm preserves in- formation that would otherwise be lost to quantum collapse, enabling accuracy accumulate epoch-by- epoch and marking the first reuse-of-informatie nique fully compatible with quantum- measuremmnt constraints. This method is essential for integrating quantum speedups into model-based RL frameworks and represents a core technical novelty of our work.
estimator in equa-
In the following, we introduce the definition of key elements and results pertaining to quantum mean estimation that are critical to our setup and analysis. First, we present the definition of a classical random variable and the quantum sampling oracle for performing quantum experiments.
tech-
Definition 1 (Random Variable, Definition 2.2 of (Cornelis- sen et al., 2022)). A finite random variable can be repre- Ω + E for some probability space (9, IP),
sented as where Ω is a finite sample set, IP Ω - [o, 1] is probability mass function and E. C R. is the support of X. (22, IP)
2

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
frequently omitted when referring the random variable X.
Lemma 1 (Quantum multivariate bounded estimator, The-
orem 3.3 of (Comellsssn al., 2022)). Let X be d- dimensional bounded random variable such that ||X||2 S 1. Given three reals L2 E (0, 1]. 5 E (0.1) and n 2 1 such that TE[] [|] S T.z, the multivariate bounded esti- mator QBounded,(X, L2, n, 5) obtained by Algorithm I performs fmm d) O (nv quantum experi- ments and outputs a mean estimate fo of μ = =[[] such that,
To perform quantum mean estimation, we provide the def- inition of quantum experiment. This is analogous to the classical random experiments
Definition 2 (Quantum Experiment). Consider a random variable X on a probability space (St, 2P)P). Let Ho be a Hilbert space with basis states { hwe and fix unitary Uy acting on Ho such that
VT VTzlog(d//)
P P11A-111s 141120 S
2 1 11
(1)
Up : :0) 7 Σ (WW))
n
WE
assuming 0 E S2. We define a quantum experiment as the process of applying the unitary Up or its inverse UF² on any state in Hzg
Algorithm [Boundedu(X, (Algorithm in (Coreelissen et al., 2022))
1: if n S log(d/6) then vLa 2: Output f 0.
The unitiary Up provides the ability to query samples of the random variable in superpositioned states, which is the essence for speedups in quantum algorithms. To perform quantum mean estimation for values of random variables (Comelissen et al., 2022; Hamoudi, 2021; Montanaro, 2015), an additional quantum evaluation oracle would be needed.
3: end if
4: Set a
and
m
v logg( log(400mnvB)
[oR
2
uv/g lostars)
5: Set G { {1
1/2
+ 2m : (0, ..,...,,................... 111" S
Definition 3 (Quantum Evaluation Oracle). Consider a fi- nite random variable X 12 + on a probability space (0, 2 P). Let Ha and F be two Hilbert spaces with ba- sis states bwes and {|x) Jeer respectively. We say that unitary Ux acting Ha He is a quantum evaluation oracle for X if
6: for k = L...., [18log(d/8)] do
7: Compute the uniform superposition (G)
Vidd22 Eueg lu) over G.
8: Compute the state (()) := Px,,,,m in Hc @
Haun. where Ix. is the directional mean or- acle constructed by the quantum evaluation oracle in Proposition 3.2 (Cornelissen et al., 2022) with
Ux : 1)) + (w)))
1/25.
for all w E Ω. assuming 0 E.
9: Compute the state (ø) == -QFT 2 Iauz)
where the unitary QFTc :
(u) +
Unlike a classical sample, which discloses only one succes- sor state, the quantum oracle stores the entire distribution in coherent superposition, offering far greater information richness per query. We note that this above form of quantum oracle, where the agent performs a quantum experiment to query the oracle and obtain a superpositioned quantum sample, is widely adopted in theoretical quantum learn- ing literature, including optimizations (Sidford & Zhang, 2023), searching algorithms (Grover, 1996), and episodic RL (Zhong et al., 2024). These quantum experiment frame- works are key mechanisms that enable quantum speedups in sample complexity and regret analysis. We now present key quantum mean estimation result that will be carefully employed in our algorithmic framework to utilize the quan- tum superpositioned states collected by the RL agent. One of the crucial aspects of Lemma is that quantum mean estimation converges at the rate O L as opposed to clas- for n number of
v /md/2 Evec transform over G.
E 2 (u) is the quantum Fourier
10: Measure the HG register of (d)) in the computational
basis and let (((k) E G denote the obtained result. Set ( (A)
11: end for
12: Output the coordinate-wist median median(w()) (f. ((Isloggd//)))
Quantum Reinforcement Learning: Within the realm of QRL. a prominent strand of previous research show- cases exponential enhancements in regret through amplitude amplification-ber based methodologies applied to the Quantum Multi- Armed Bandits (Q-MAB) problem (Wang et al., 2021; Casalé et al., 2020; Wan et al., 2023; Wu et al., 2023). Never- theless, the theoretical underpinnings of the aforementioned Q-MAB approaches do not seamlessly extend to the QRL context since there is no state evolution bandits.
n sical benchmark convergence rate O vir samples, therefore estimation efficiency quadratically.
3

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
recent surge of research interest has been directed towards Quantum Reinforcement Learning (QRL) (Jerbi al., 2021; Dunjko et al., 2017: Paparo et al., 2014). It is noteworthy to emphasize that the aforementioned studies do not provide an exhaustive mathematical characterization of regret. (Zhong et al., 2024; Ganguly et al., 2023) demonstrated that QRL can provide logrithmic regret in the episodic MDP settings. Ours the first study of infinite horizon MDP with average reward objective.
would collapse to any basis (&x) with probability |xy/ In quantum computing. the quantum states are represented by input or output registers made of qubits that could be in superpositions.
Quantum transition oracle: We utilize the concepts and notations of quantum computing in (Wang et al., 2021; Wiedemann al., 2022; Ganguly et al., 2023; Jerbi et al.. 2022) to construct the quantum sampling oracle of RL environments and capture agent's interaction with the un- known MDP environment. We now formulate the equivalent auantum-accessible RL environments for our classical MDP M. For an agent at step t in state & and with action a, we construct the quantum sampling oracles for variables of the next state P()ss, dt). Specifically, suppose there are two Hilbert spaces S = C and Á ClAl containing the superpositions of the classical states and actions. We repre- sent the computational bases for S and A as (Is) ( and JaEA- We assume that we can implement the quantum sampling oracle Up of the MDP's 's transitions as follows:
3. Problem Formulation
We consider the problem of Reinforcement Learning (RL) in an infinite horizon Markov Decision Process character- ized by M - (S, A, p.r, r, D), wherein S and A represent finite collections of states and actions respectively with |S] S and | A, pertaining to RL agent's interaction with the unknown MDP environment. P(s"|s, a) E [] denotes the transition probability for next state s' E S for a given pair of previous state and RL agent's action, i.e.,
(s, a) E S x A. Further, r : S x A + [o, 1] represents the reward collected by the RL agent for state-action pair (s, a). D is the diameter of the MDP M. In the following, we first present the additional quantum transition oracle that the agent could access during its interaction with the unknown MDP environment at every RL round. Here, we would like to emphasize that unknown MDP environment implies that matrix P which encapsulates the transition dynamics of the underlying RL environment is not known beforehand.
The quantum evaluation oracle for the transition probability (quantum transition oracle) Up which at step L, returns the superposition over s' S according to P(s" st. at). the probability distribution of the next state given the current state (st) and action (at) is defined as:
Up |st) @ la)) @ 10) + (1))
Where (15) = (s)) X aa)) & EveS v P(s st ar)|s").
Quantum Computing Basics: In this section, give brief introduction to the concepts that are most related to our work based on (Nielsen& & Chuang, 2010) and (Wu et al., 2023). Consider an m dimensional Hilbert space Cm" a quantum state (x) = (Zi,..., )mm can be seen as a vector inside the Hilbert space with Σ, lax/2 = 1. Furthermore, for a finite set with m elements { {EI..., Jm J. we can assign each Ea E & with member of an orthonormal basis of the Hilbert space C by
(zb)e
Quantum Transition Orucle for Environment
Quantum Mean Estimator
8t, Ag
P(5141/80)0))
St, at
Environment with Unknown MDP
RL Ageni with Policy
E - (S) =
8t+1,
where e is the ith unit vector for Cm. Using the above notation, we can express any arbitrary quantum state |æ) (f1, Rmm) by elements in & as:
Figure 1. Agent's interaction at round with the MDP Environ- ment and accessible quantum transition oracle
As described in Fig 1, at step f. the agent plays an action a based on current state s; according its policy æ : S + A. Consequently, the unknown MDP Q-environment shares the next state information and reward i.e., (e)) Additionally, the quantum transition oracle first encodes st and a, into the corresponding basis of the quantum Hilbert spaces, producing basis (st) and Ja,), then it encodes the superpositioned quantum state [xb)* from the quantum
(x) = pnlen)
where (x) is the quantum superposition of the basis lEI),.., (mm) and we denote I, as the amplitude of (g.). To obtain a classical information from the quantum state, we perform a measurement and the quantum state

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
transition oracle Up | would be used for the Quantum Mean Estimator, @Rounded, which in turn improves transition probability estimation and leads to exponentially better regret. We note that one copy of |eb) is obtained at each (st, de). Given that a measurement collapses the state, we can only perform one measurement on it. So, the quantum mean estimator will only perform measurements at epoch ends, as will be described in the algorithm.
where Tx, s->s' implies the number of time steps to reach state 8 from initial state by playing some policy n.
Assumption 2. The reward function r(',,) .) is known the RL agent.
We emphasize that Assumption 2 is a commonly used as- sumption in RL algorithm development owing to the fact that in most setups rewards are constructed according to the underlying problem and is known beforehand (Azar et al., 2017; Agarwal al., 2019). Next, we define the cumulative regret accumulated by the agent in expectation across T time steps as follows:
RL regret formulation: Consider the RL agent follow- ing some policy π S - A on the unknown MDP Q- environment M.. Then, as a result of playing policy π, the agent's 's long term average reward is defined next according to (Agarwal et al., 2022b).
T-1 Σ r(st, ai)
R A T.P x - E
(10)
T-1 Σ
rf = lim P
r(st,
(4)
where the agent generates the trajectory {(s,, at hejor by playing policy on M, and x² is the optimal policy that maximizes the long term average reward defined in Eq. (4), Finally, the RL agent's goal is to determine policy π which minimizes R.o.T-1)-
where p[] is the expectation taken over the trajectory (st,, az) he)oo_) by playing policy x on M at every time step. In this context, we state the definitions of value func- tion for MDP M next:
V.P (8; FEaw (0)(8,;7))
4. Algorithmic Framework
(5)
In this section, we first delineate the key intuition behind our methodology followed by formal description of Q-UCRL algorithm. If the agent was aware of the true transition probability distribution P, then it would simply solve the following optimization problem for the optimal policy.
Bows ((s,a)+ + E ((s))s.))
s'ES
(6)
Then, according to (Puterman, 2014), r can be represented as the following:
max (e
Σ
r(8,a)p(s.n) (11)
r lim (1 - (1- (s; YsES,
(7)
(x,0)ESXA
ΣΣ ((s,a))(ssa) SES
(8)
With the following constraints,
Σ Ep(s,a) = 1, 1,,(0,))20 V(s,a) (Sx (12)
wherein, (::): is the discounted cumulative av-
erage reward by following policy T, of is the E = 1). F(s, a) is the steady-
8,0
steady-state occupancy measure (i.e., (s)
p(ss'a)) a)= Σ aEA
ES (13)
[0, 1]. Ees E state long-term average reward of pair (s, a). In the fol- lowing, we introduce key assumptions crucial from the per- spective of our algorithmic framework and its analysis. In this context, we introduce the notations {P+ Tx, e->s' } to denote the time step probability distribution obtained by playing policy æ on the unknown MDP M starting from some arbitrary state s E S; and, the actual time steps to reach s' from by playing policy π respectively. Next, we state an assumption pertaining to ergodicity of MDP M.
8,a
Note that the objective in Eq. (11) resembles the defi- nition of steady-state average reward formulation in Eq. (4). Furthermore, Eq. (12), (13) preserve the properties of the transition model. Consequently, once it obtains {o" (s, ()) by solving Eq. (11), it can compute the optimal policy as:
('(s,a) EaeAp"(s.))
7 <a|ss)
Vs,a a
(14)
Assumption (Finite MDP mixing time). We assume that unknown MDP environment M has finite mixing time, which mathematically implies:
However, in the absence of knowledge pertaining to true P. we propose to solve an optimistic version of Eq. (11) that will update RL agent's policy in epochs. Specifically, at the start of an epoch e, the following optimization problem will be solved:
T Tmix
max ET,,, e+or] 0c, xESx
5

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
estimator obtained using the quantum samples in the latest completed epoch Pa(-Iss; 0:) as follows:
max With the following constraints,
Σ
r(s,a)p(s,a), (15)
(x,a)ESxA
if 1
Pc(1|s; a,) =
Po Pc(-(si;
if 2
Σ [p(s.a)=11,(s...) Exx (16)
10P i.Po-11 1--1(-11 (-1;;, + ()P((-(s...))
if 2 3 (22)
8,0
Σ *'ES
ESxA
where
(17)
N Ne-1 a4)
(23)
Σ AEA
p(ss E
P=(0/s,c)ple.o)) E
N (5t, ai) ve- 1 (8i,
(8.A)ESXA
(18)
1/- 1 (8ix ai)
T N 88, az) + Ve- (8;,a;)
(24)
75 log Att, (P)(-)s,a) - Pa(lls,a)l11
(19)
Na a)}
In particular, given that V/ ( a.) is the maximum num- ber of quantum experiments we can perform in Eq. (21), we set
Observe that Eq. (15) increases the search space for policy in carefully computed neighborhood of certain transition probability estimates P via Eq. (19) at the start of epoch e. Also in Eq. (19), recall that S = [S] is the number of states, A= = |A] is the number of actions, Ne(s, a) is the number of visitations of state-action pair (s, a) upto the end of epoch e. Note that, solving Eq. (15) is equivalent to ob- taining an optimistic policy as it extends the search space of original problem Eq. (11). Furthermore, the computation of Pe is key to our framework design. Since performing quan- tum mean estimation to quantum samples would require measuring and results in quantum samples collapsing, each quantum sample can only be used once. We emphasize that the quantum mean estimator will only run at the end of the epoch, performing measurements to update the transition probability for the next epoch.
Ve-1 ( (4)
8::01 e
(25)
clog' (2TVV))
for e E R satisfying en log (ogg/2(nn) (nv) 2 [nn S) Vn where f(n, S) is defined in Lemma 1. Such choice of c would allow (e a) samples to be used for analysis of our pro- posed algorithm. Note that the choice of is achievable because en / (nv/S S) and (n, are the same order. Since EIII a:)l S 1, we set L2 = 1. Different from the works in classical approaches based on (Jaksch et al., 2010), our algorithm utilizes each quantum sample only once for estimating all P. throughout the entire pro- cess. This strategy fits with our quantum framework since quantum samples would collapse once being measured. In Appendix A, we show that Eq. (15) is a convex optimiza- tion problem, therefore standard optimization solvers can be employed to solve it. Finally, the agent's policy at the start of epoch e is given by:
Details on Quantum Mean Estimator: At the end of the epoch, we use all (s; 0z) observed in the samples, and perform quantum mean estimation on all the samples |ej) obtained for that (st, a.). More precisely, Pe (- a,) the quantum mean estimation for the random variable (- a;) performed by QBounded (Algorithm 1) using the quantum samples {1r5) J observed in the previous epoch with the total number being V/-1 (8%, a:):
(s(
Ta(as EreA Pa (8,
(26)
Next, we formally present Q-UCRL in Algorithm 2.
Algorithm 2 proceeds in epochs, and each epoch contains multiple rounds of RL agent's interaction with the envi- ronment. At each i, by playing action a; for insantaneous state s, through current epoch policy Re- the agent col- lects next state configuration consisting of classical signals $1+1, r(st, az) and quantum sample (t)) Additionally, the agent keeps track of its visitations to the different states via the variables {Va,a= Ms.a.ar). J. Note that new epoch is triggered at the "if" block of Line 15 in algorithm 2, which in turn is aligned to the widely used concept of doubling trick used in model-based RI. algorithm design. Finally, the
(1)) (10) 1 pstart 213 start -1, (St, at) = (si, };)}
(20)
where retart is the starting step of epoch e. Using these samples, the transition probability is obtained as
Pa(-Isi. a:) @oundedd (( az), La, miin sha 8e)
(21)
For a specific state-action pair (s;, a;), we construct an estimator (e( a,) used in epoch e that consists of a weighted average of the estimator Pa-1(-18;, az) and the
6

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
Algorithm 2 Q-UCRL
(21).
1: Inputs: S,A, r(::).
2: Set 1, e 1, 6g f 0,6g + 0, +
Proof. For all (s,a) x A, since Po+1 is obtained by
3: Set pet, (, 8') < -V s') e Ax S.
Eq. (21), we obtain using Lemma 1:
4: Set Po(tss, - a() ESxA.
5: for (s,a) E S x A do
6: Set (x + 0, Ne(s, + 0.
P [|Ie+1((1,, - all 1
(S/(5
2 1 -1-60 6,
7: end for
nc+1
22,00
8: Obtain ne by solving Eq. (15) and Eq. (26).
(28)
9: for = 1.2.... do
10:
Observe state 8t and play action at ~ Tee (-1s))
By switching newds with vo a)/C, Eq. (28) gives:
11:
Observe r de) and quantum samples l16)..
C Clog(S/8)
12:
Update Ve( ae) + Vo (S), +1.
P [| - P(-ss, a) I
2 -1-8 8
Vs(s,a)
13:
Update u($t, (1, (t,,8--1) t- Ve(St, (1,1541)) +1.
(29)
14:
Set te + +t +1
15:
if v. ax) = 1 Ne(t,, a:)} then for (s,a) E S&x A do
Eq. (29) can be transformed into Eq. (27) by taking the entry-wise expression.
16:
17:
No+1(s,a) + Ne(s, a) + ()) end for
18:
19:
Sete + e,, 1, Ve( a) 0, de 5
Note that the choice of C' in Eq. (27) is to ensure that the samples Ve(s, a) are sufficient for performing Algorithm 1. Lemma 3. Execution of Q-UCRI (Algorithm 2) up to the beginning of epoch e + 1 with total e completed epochs comprising = 1, 2.,...,le rounds, guarantees that the following holds for Pe+1:
20:
Sette + +0, tstart + t +1. 1.
21:
Obtain Pe(1)s,)) a) by Eq. (22) v(s, a) E x A
22:
Obtain ne by solving Eq. (15) and Eq. (26).
23:
end if
24:
end for
Pei ((d'ss))))) S eC eClog(eS18) Not1(8,a) 2 1 - 8
empirical visitation counts and probabilities up epoch e, i.., (Ne+1 (s, a). Pa- (s') [s, a)} attributes are updated (line 15-21), and the policy is updated via re-solving from Eq. (15) - (19) and using Eq. (26).
(30)
V(s,a,s) E S A x S, where C clog (TVV) for some e E TR and {ve(s. a)} are the state-action pair visita- tion counts up in epoch e, as depicted in Line 12 of Algo- rithm 2, and (P(''s,, a), Pe+1(8//e ()) are the actual and weighted average of transition probabilities by Eq. (22).
5. Theoretical Results
In this section, we characterize the cumulative regret for T rounds by running Q-UCRL in unknown MDP hybrid Q-Environment. In the following, we first present crucial result bounding the error accumulated till epochs between the true transition probabilities (P(-|s, } and the agent's estimates (-((-s,a))
Proof. Please refer to Appendix C.
Lemma and Lemma 3 provide the acceleration for mean estimation, which further improve global convergence rate.
Lemma 2. Execution of Q-UCRL (Algorithm 2) up to the beginning of epoch e + 1 with total e completed epochs comprising i = 1, ,,.... rounds, guarantees that the following holds for Pot1:
Lemma 4. Execution of Q-UCRL (Aloortnn 2) up to total e epochs comprising = 1,2,...,te rounds, guarantees that the following holds for confidence parameter d. 3AE with probability at least 1 - 1/t6:
(1s)ss,a)1= Cllo(S//)) a)(s,a)
P | P
21-8
|| (P((sss))-P((ss,o)l 78(1 + lo) S² AT) SCelog(eS) max (1, Ne(s,a))
(27)
(31)
8') E S x Ax S, where C == (TT for some e E R defined in Eg. (25) and (ve }}} are the state-action pair visitation counts up in epoch e, as depicted in Line 12 of Algorithm 2, and {P(s') s, a), (e41(5'|s, a)} are the actual and estimated transition probabilities by Eq.
V(s, E S A, where (N(=-)) is the cumulative state- action pair visitation counts up to epoch e, as depicted in Line 17 of Algorithm 2, and [P(- a), Pe(-|s, a)} are the actual and estimated transition probabilities.
7

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
Proof. Please refer to Appendix D.
transition model in Lemma 4 into Eq. (35), we obtain the following result with probability - 1/t8.
Remark 1. Note that for Pa (- a), P(-|s, a) we have the bound: [- a) a(]ls I 2S, in the worst case scenario. However, the probability that bad event (i.c., complementary of Eq. (31)) happens is at most T..
B 7S(1 + log ( + SCe log (eSS (i(())loo, max (1, Ne),aa)
Lemma (Regret Decomposition), Regret of Q-UCRL de-
(36)
fined in Eq. (10) can be decomposed as follows:
Te (I I
Consequently, it is necessary to bound the model bias error term in Eq. (36). We recall that the optimistic MDP P. corresponding to epoch e maximizes the average reward in the confidence set as described in the formulation of Eq. (15). In other words, r > T for every P' in the confi- dence interval. Specifically, the model bias for optimistic MDP can be explicitly defined in terms of Bellman equation (Puterman, 2014), as follows:
-Io,T-11 1]
(32)
Proof. Please refer to Appendix E.
Regret in terms of Bellman Errors: Here, we introduce the notion of Bellman errors B&ae (s, a) at epoch as fol-
lows:
( a) A lim (s 05 r(s,
h(s) _ The (s) XPc (Penc)(ss) T h(.),
(37)
Σ P(s (s:7), (33) S'ES
where the following simplified notations are used: (s) = EnEA Te Ne(als)r(s,a)) (s'lss EeEA (s a). Next, we incorporate the following result from (Agarwal et al., 2022b) stated as Lemma 11 in Appendix F correlating model bias h(.) to the mixing time Taix of MDP M.
which essentially captures the gap in the average rewards by playing action a in state s accordingly to some policy π in one step of the optimistic transition model Pa w.r.t. the actual probabilities P. This leads us to the next result that ties the regret expression in Eq. (32) and the Bellman errors.
h(s)) h(5') S Trixs Vs, 8' E S.
(38)
Lemma 6 (Lemma 5.2, (Agarwal al., 2022b)). The dif- ference in long-ter expected reward by playing optimistic policy of epoch i.e., Te on the optimistic transition model estimates, i.e., 1f, and the expected reward collected by playing ne on the actual model P, i.e D is the long-term average of the Bellman errors. Mathematically, we have:
Using bound of bias term h(-) into Eq. (36), we get the final bound for Bellman error with probability 1 - 1/76 as:
7S(1 + log AT) + SCe log (eS) (eS)
BTe.Pe(s, S
Tmix.
max (1, (s.
D P
Σ Ph (s. (s.
(34)
(39)
Note that Q-UCRL obtains quadratic improvement for the Bellman error over the classical UC-UCRL (Agarwal et al., 2022b). We next present the final regret bound of Q-UCRL.
where B (s. a) is defined in Eq. (33).
Theorem 1. In an unknown MDP environment M & (S, A. P.r, r, D), the regret incurred by Q-URL (Algorithm 2) across T rounds is bounded as follows:
With Eq. (34), it necessary to mathematically bound the Bellman errors. To this end, we leverage the following result from (Agarwal et al., 2022b) which is stated as Lemma 10 from Appendix F characterizing the Bellman errors in terms of h((),, a quantity that measures the bias contained in the optimistic MDP model.
R RoT--1= 0 S
log (TVSS) AT) SA
(40)
Pe (s, a) < |||||| - P(-1s, 11(0) (35)
Proof. Please refer to Appendix G.
where h(-) (defined in (Puterman, 2014)) is the bias of the optimistic MDP P. for which the optimistic policy т, ob- tains the maximum expected reward in the confidence inter- val. Using the bound of the error arising from estimation of
Remark 2. We reiterate that our characterization of regret incurred by Q-UCRL in Theorem is a martingale- free analysis and thus deviates from its classical counterparts (Fruit et al., 2018; Auer et al., 2008; Agarwal al., 2022b).
8

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
6. Conclusions
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International Con- ference Machine Learning, pp. 263-272. PMLR, 2017.
This paper demonstrates that quantum computing helps pro- vide significant reduction in the regret bounds for infinite horizon reinforcement learning with average rewards. This paper not only unveils the quantum potential for bolster- ing reinforcement learning but also beckons further explo- ration into novel avenues that bridge quantum and classical paradigms, thereby advancing the field to new horizons.
Bai, Q., Mondal, W. U., and Aggarwal, V. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 10980-10988, 2024.
promising future direction is parameterized quantum RI,, which has recently shown speedups for discounted settings (Xu & Aggarwal, 2025); achieving similar gains for average- reward problems, where the kate-offHue the-art in non-quantum RL is given by (Ganesh et al., 2025b), remains an open challenge.
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., and Lloyd, S. Quantum machine learning. Nature, 549(7671); 19:1522)) 2017.
Bonjour, T., Haliem, M., Alsalem, A., Thomas, S., Li, H., Aggarwal, V., Kejriwal, M., and Bhargava, B. Decision making in monopoly using hybrid deep reinforcement learning approach. IEEE Transactions Emerging Top- ics in Computational Intelligence, 6(6):1335-134 2022.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bouland, A., Getachew, Y. M., Jin, Y., Sidford, A., and Tian, K. Quantum speedups for zero-sum games via improved dynamic gibbs sampling. In International Conference on Machine Learning, pp. 2932 2952. PMLR, 2023.
References
Brassard, G., Hoyer, P., Mosca, M., and Tapp, A. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Rein- forcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32, 2019.
Casalé, B., Di Molfetta, G., Kadri, H., and Ralaivola, L. Quantum bandits. Quantum Machine Intelligence, 2:1-7, 2020.
Agarwal, M. and Aggarwal, V. Reinforcement learning for joint optimization of multiple rewards. Journal of Machine Learning Research, 24(49): 1-1,, 2023.
Chen, J., Umrawal, A. K., Lan, T., and Aggarwal, V. Deep- freight: model-free deep-reinforcement-eearm -eareeettt-eaain-babbaeeee algorithm for multi-transfer freight delivery. In Proceed- ings of the International Conference on Automated Plan- ning and Scheduling, volume 31, pp. 510-518, 2021.
Agarwal, M., Aggarwal, V., and Lan, T. Multi-objectiin re- inforcement learning with non-linear scalarization. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 9-17, 2022a.
Cornelissen, A., Hamoudi, Y., and Jerbi, S. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pp. 33 43, 2022.
Agarwal, M., Bai, Q., and Aggarwal, V. Concave utility reinforcement learning with zero-constraint violations. Transactions on Machine Learning Research, 2022b.
Agrawal, S. and Jia, R. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Ad- vances in Neural Information Processing Systems, 30, 2017.
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.
Al-Abbasi, A. O., Ghosh, A., and Aggarwal, V. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions Intel-
Farhi, E., Goldstone, J., and Gutmann, S. quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 2014.
ligent Transportation Systems, 20(12):471444727, 2019.
Fruit, R., Pirotta, M., Lazaric, A., and Ortner, R. Elfi- exploration-exploitatio in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1588 PMLR, 2018.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
cient

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
Ganesh, S., Mondal, W. U., and Aggarwal, V. Order- optimal regret with novel policy gradient approaches in infinite horizon average reward mdps. In The 28th International Conference on Artificial Intelligence and Statistics, 2025a.
Lloyd, S., Mohseni, M., and Rebentrost, P. Quantum algo- rithms for supervised and unsupervised machine learning. arXiv preprint
2013.
Montanaro, A. Quantum speedup of monte carlo meth- ods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, (1122111:200103000 2015.
Ganesh, S., Mondal, W. U., and Aggarwal, V. A sharper global convergence analysis for average reward reinforce- ment learning via an actor-critic approach. In Forty- second International Conference on Machine Learning, 2025b.
Nielsen, M. A. and Chuang, I. L. Quantum computation and quantum information. Cambridge university press, 2010.
Ganguly, B., Wu, Y., Wang, D., and Aggarwal, V. Quan- tum computing provides exponential regret improve- ment in episodic reinforcement learning. arXiv preprint arXiv:2302.088. 07 2023.
Osband, I., Russo, D., and Van Roy, B. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Paparo, G. D., Dunjko, V., Makmal, A., Martin-Delgadoe
Gilyén, A., Su, Y., Low, G. H., and Wiebe, N. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Pro- ceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193-204, 2019.
M. A., and Briegel, J. Quantum speedup for active learning agents. Physical Review X, 4(3):03 2014.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley Soons, 2014.
Grover, L. K. A fast quantum mechanical algorithm for
database search. In Proceedings of the twenty-eighth annual ACM symposium Theory of computing, pp- 212-219, 1996.
Rosenberg, A. and Mansour, Y. Online convex optimization in adversarial markov decision processes. In Interna- tional Conference on Machine Learning, pp. 5478-5486. PMLR, 2019.
Hamoudi, Y. Quantum sub-gau gaussian mean estimator. In 29th Annual European Symposium on Algorithms (ESA 2021), pp. 50-1, 2021.
Sidford, A. and Zhang, C. Quantum speedups for stochastic optimization. In Thirry-sevntth Conference on Neural Information Processing Systems, 2023.
Harrow, A. W., Hassidim, A., and Lloyd, S. Quantum algorithm for linear systems of equations. Physical review 2009.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I.. Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676):354-385 2017.
letters,
Hong, K., Chae, W., Zhang, Y., Lee, D.. and Tewari, A. Re- inforcement learning for infinite-horizon average-reward linear mdps via approximation by discounted-rewarr mdps. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Wan, Z., Zhang, Z. Li, T., Zhang, J., and Sun, X. Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets. Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 10087- 10094, 2023.
Jaksch, T. Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11: 111116666600,,, 2010.
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.
Wang. D.,. You, X. Li. and Childs, A. M. Quantum ex- ploration algorithms for multi-armed bandits. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10102-10110, 2021.
Jerbi, S., Cornelissen, A., Ozols, M., and Dunjko, V. Quan- tum policy gradient algorithms. arXiv e-prints, pp. arXiv- 2212, 2022.
Wei, C.-Y., Jahromi, M. J., Luo, H., Sharma, H., and Jain, R. Model-free reinforcement learning in infinite-horizon everage-rewarr markov decision processes. In Interna- tional conference on machine learning, pp. 10170-10180. PMLR, 2020.
Kitaev, A. Y. Quantum measurements and the abelian stabi- lizer problem. arXiv preprint quant-ph/951 1026, 1995.
10

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., and Weinberger, M. J. Inequalities for the 11 deviation of the empirical distribution. Heewlett-Packard Labs, Tech. Rep, 2003.
Wiedemann, S., Hein, D., Udluft, S., and Mendl, C. Quan- tum policy iteration via amplitude estimation and grover scarch-towards quantum advantage for reinforcement learning. Transactions on Machine Learning Research, 2022.
Wu, Y., Guan, C., Aggarwal, V., and Wang, D. Quantum heavy-tailed bandits. arXiv preprint arXiv:2301.09680, 2023.
Xu, Y. and Aggarwal, V. Accelerating quantum reinforce- ment learning with a quantum natural policy gradient based approach. In Forty-second International Confer- ence on Machine Learning, 2025.
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- lional Conference on Machine Learning, 2024.

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
A. Appendix A: Convexity of Optimization Problem
order to solve the optimistic optimization problem Eq. (15) (19) for epoch e, we adopt the approach proposed in (Agarwal al., 2022b; Rosenberg & Mansour, 2019). The key is that the constraint (18) seems non-convex. However, that can be made convex with an inequality as
Σ a(s
Σ
Pc(s(ss,a)p(s.d) As E
(41)
aEA
(s,a)ExxA
This makes the problem convex since zy 2 e convex region the first quadrant.
However, since the constraint region is made bigger, need show that the optimal solution satisfies (18) with equality. This follows since
Σ E Pc( 1 ΣΣ p(s',a)
(42)
s'ES (s.0)ESxA
R'E
Thus, since we have point-wise inequality in (41) with the sum of the two sides being the same, thus, the equality holds for all 6'.
12

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
B. Appendix B: A brief overview of Quantum Amplitude Amplification
Quantum amplitude amplification stands as a critical outcome within the realm of quantum mean estimation. This pivotal concept empowers the augmentation of the amplitude associated with targeted state, all the while suppressing the amplitudes linked to less desirable states. The pivotal operator, denoted Q, embodies the essence of amplitude amplification: Q 2/x) (1²l I, where (v) signifies the desired state and I represents the identity matrix. This operator orchestrates double reflection of the state (vb) initially about the origin and subsequently around the hyperplane perpendicular to |v/) culminating in significant augmentation of the amplitude of (15).
Moreover, the application of this operator can be iterated to achieve a repeated amplification of the desired state's 's amplitude, effectively minimizing the amplitudes of undesired states. Upon applying the amplitude amplification operator a total of / times, the outcome is Q', which duly enhances the amplitude of the desired state by scaling factor of / /N /N/M, where N corresponds to the overall count of states and M signifies the number of solutions.
The implications of quantum amplitude amplification extend across diverse spectrum of applications within quantum algorithms. By bolstering their efficacy and hastening the resolution of intricate problems, quantum amplitude amplification carves a substantial niche. Noteworthy applications encompass:
1. Quantum Search:
the quantum algorithm for unstructured search, known as Grover's algorithm (Grover, 1996), the technique of amplitude amplification is employed enhance the amplitude the target state and decrease the amplitude of the non-target states. As a result, this technique provides quadratic improvement over classical search algorithms.
2. Quantum Optimization: Quantum amplification can be used quantum optimization algorithms, such as Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014), amplify the amplitude of the optimal solution and reduce the amplitude of sub-optimal solutions. This can lead to exponential speedup in solving combinatorial optimization problems.
3. Quantum Simulation: Quantum amplification has also been used in quantum simulation algorithms, such as Quantum Phase Estimation (QPE) (Kitaev, 1995), amplify the amplitude of the eigenstate of interest and reduce the amplitude of other states. This can lead to efficient simulation of quantum systems, which is an intractable problem in the classical domain.
4. Quantum Machine Learning: The utilization of quantum amplification is also evident in quantum machine learning algorithms, including Quantum Support Vector Machines (QSVM) (Lloyd et al., 2013). The primary objective is to amplify the amplitude of support vectors while decreasing the amplitude of non-support vectors, which may result in exponential improvement in resolving particular classification problems.
In the domain of quantum Monte Carlo methods, implementing quantum amplitude amplification can enhance the algorithm's ss efficiency by decreasing the amount of samples needed to compute the integral or solve the optimization problem. By amplifying the amplitude of the desired state, substantial reduction in the number of required samples can be achieved while still maintaining a certain level of accuracy, leading to significant improvements in efficiency when compared to classical methods. This technique has been particularly useful in (Hamoudi, 2021) for achieving efficient convergence rates in quantum Monte Carlo simulations.
13

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
C. Appendix C: Proof of Lemma 3
Lemma (Lemma in the main paper). Execution of Q-UCRL (Algorithm 2) up to the beginning of epoch + with total completed epochs comprising ......t rounds. guarantees that the following holds for P Pa+
cClog(eS/0) (s,
21
(43)
Vs,,,, 8") E S A S, where C = (log2/2(TV/S) for some E R and (Ve(8, a)} are the state-action pair visitation counts in epoch e, as depicted in Line 12 of Algorithm 2, and {P(s'ss, a), Pet (s'lss a}} are the actual and weighted average of transition probabilities by Eq. (22).
Proof. For all (s, (as.as))EES E Ax Pet1(s'|s, a) could be equivalently expressed as:
Pe+1(s'(s,a) Ei= ((8.a))) (5(8,))
(44)
Denote event (P(('ss,a) - P(s'ls, a)) v
Cloog(S/8) va(s,a) as event E,. Thus if events E1,.., Eg all occur, we would have:
| Pe+1(5'1s,a) P(s' s)))
(45)
E vi P(())ss
(46)
Σj (8,0)
Ei miss, a) as) P(s
(47)
Σj (s,,a
Σ k= C log((//0)
(48)
Ej (3(8,a) a)
eC Cllog(S/))
(49)
j= ()(
eC (lo((5/1)) (8,1
(50)
Where Eq. (47) is the result of triangle inequality and Eq. (48) is by Lemma 2. The probability of events E Ee all occurring is:
P[E A... n EzJ,
(51)
1 PIE U... U..,
(52)
2 1 Σ P
(53)
1 eg
(54)
Where Eq. (54) is by Lemma 2. By combing Eq. (50) and Eq. (54) and substituting ed with would obtain Eq. (43)
14

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
D. Appendix D: Proof of Lemma 4
Lemma (Lemma the main paper). Execution of Q-UCRL 2) up to total e epochs comprising = 1, .......... be
rounds. guarantees that the following holds for confidence parameter 5, SAY
with probability least 1/
[P((-1s, a) - P(-Is,
75(1 + Ce) log( S AT) + SCelog(eS) x
(55)
max(1,NNes.dd)
ass E A. where (Nv(a)) } is the cumulative state-action pair visitation counts up epoch depicted in Line 17 of Algorithm 2, and (P(-)s, a), Pe(-)s,a)} are the actual and estimated transition probabilities.
Proof. To prove the claim in Eq. (55), note that for arbitrary pair (s,a) we have:
+ a) P(-ls,))ll: P(
(56)
7S logg At.) max(1,No(s,ai)) + -((ts)ll
P(-|s,a)llı
(57)
75 logg S Ate)
max
(s, a))
+ Σ Pa(s'|s, 8, - ((51ss,a))
(58)
e'ES
(a)
where Eq. (57) is direct consequence of constraint Eq. (19) of optimization problem Eq. (15). Next, in order analyze (a)
in Eq. (58), consider the following event:
(Pc(5'ls,a) ((ss(ss0)
SS Laxx(I,Ne(s,,u V(s,a,s') ('s,,,,') S
(59)
For tuple 8'), by replacing 8 = -e-N((() into Eq. (1) from Lemma 1, we get:
P s, P() Celog(e5) + Cee
P
Ne(s.a)
2 (NNa
(60)
By plugging in log(S A (s.s.a)
into Eq. (60), get:
Celog (cS) + Ce CS At?)
(e(('sss a()1ss,a) P(811.)))
No(
1
(61)
S2 A²
Finally, we sum over all possible values of No (8, a) as well as tuples (s, a, s') to bound the probability in the RHS of (61) that implies failure of event E:
Σ
t
1
S
(62)
S
/6
(=x.
N1(3,)==1
15

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
Here, is critical highlight that obtain this high probability bound for model errors by careful utilization of Lemma I and quantum signals 11)8 via Eq. (55) (62), while avoiding classical concentration bounds for probability norms that martingale style analysis such as in the work (Weissman et al., 2003). Finally, plugging the bound of term (a) as described by event &, we obtain the following with probability 1 - 1/te:
Pa a) P(-18,a)ll
7S (o At.)
Celog (eS) + Co At!)
(63)
max 1. Ne
max ma, a)}
s'ES
75 +
Celog (e.S + 7Ce (2 Ate)
Σ
(64)
max(1, a)}
max (sx
s'ES
7S(1 + Ce) log( (52 At,) + SCelog(eS)
(65)
max {1, (s, a)]
7S(1 + Ce) log ( AT) + SCelog(eS) max [1, (s, })}
(66)
This proves the claim as in the statement of the Lemma.
16

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
E. Appendix E: Proof of Lemma 5
Lemma 9 (Regret Decomposition, Same as Lemma 5 in the main paper), Regret of Q-UCRL defined in Eq. (10) can be decomposed as follows:
E
R R1 S
Σ
Te
(67)
Re
Nx.
Proof.
T-1
RI = T P
r(st, at)
(68)
5
E
E
T-1
=T x P.
T
T
T.P.
r rst, at)
e=1
t=
E
E
T-1
Te
PP
P
+
T
T.P
E
Σ
r av)
(69)
e=1
e=1
1=
(8)
T-1
T.P
r(s2: oz)
(70)
m
E
T-1
P.P
r r ar)
(71)
Tee
e=1
1=0
E
E
T-1
T.P
T.P
T.P.. -E
Σ
a()
(72)
Ne
e=1
e=1
e=1
t=
T T.P
TIP
Bir (st, at)]
(73)
E
Te
[ te
IP
(74)
==1
Firstly, (a) in Eq. (69) is owing to the fact that the agent would have gotten ग exactly the true T in epoch solving for original problem Eq. (11), had it known the true transition model P. Next, Eq. (71) is because {Pe, Fe) are outputs from the optimistic problem Eq. (15) solved at round e, which extends the search space of Eq. (11) and therefore always upper bounds true long-term rewards. Finally, term (b) in Eq. (73) is O in expectation, because the RL agent actually collects rewards by playing policy тe against the true P during epoch e.
17

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
F. Appendix F: Some Auxiliary Lemmas used in this Paper
Lemma 10 (Lemma 5.3, (Agarwal et al., 2022b)), The Bellman errors for any arbitrary state-action pair (8, a) correspond- ing epoch e bounded as follows:
BRe S P(-1s, [lb()
(75)
where h()) (defined in (Puterman, 2014)) is the bias the optimistic MDP Pe for which the optimistic policy ne obtains the maximum expected reward in the confidence interval.
Lemma 11. [Lemma D.5, (Agarwal al., 2022b)] For an MDP with the transition model Pe that generates rewards r(s, a)
on playing policy the difference of biases for states and s' are bounded as:
h(s) h(s') s Taixi Vs, E S.
(76)
18

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
G. Appendix G: Proof of Theorem 1
Theorem (Theorem I in main paper). In an unknown MDP environment M - (,,,,P,r, the regret incurred by Q-URL (Algorithm 2) across T' rounds is bounded as follows:
0
R1.r-11=0
555 A
T
log 12 (TV))) log ( AT)
(77)
SA
Proof. Using the final expression from regret decomposition, i.e., Eq. (74), we have:
E
R10,T-11=
= Σ
Te
(r No
rPP
xo)
(78)
c=1
E
Σ _h Px.
(79)
em tmme
1+1 8,a
E
7S(1 + Cé) log( (22 AT) + SCelog(eS)
Tnixs
(80)
max (1, (8),,)a))
c=1 t=l 1+1
E
Σ
1[s: = s,a;=00
e=1
1= 8,0
7S(1 Ce)
log (5² SCelog(eS)
Tmix)
(81)
max (1,))(
E
Ve a))
c=1
8,0
7,5(1 + Ce) log ( AT) + SCelog(eS)
T mix:
(82)
max L, (s,
Taix (TS((TTTEEEEE + CL2) log S2 AT') + SC log (ES))
8,0
uo(s,a)
(83)
max (sx
CE") ATT SCE" (ES))E,
Tmix E A(E + CE?) log( AT) + 52 ACE2 log (ES)),
= -0 A'A (
T
log 1/2 (TV AT)
(84)
SA
where in Eq. (79), we directly incorporate the result of Lemma 6. Next, we obtain Eq. (80) by using the Bellman error bound in Eq. (39), well unit sum property of occupancy measures (Puterman, 2014). Furthermore, in Eq. (80) note
that we have omitted the regret contribution of bad event (Remark 1) which is atmost δ
25T 7
as obtained below:
2ST
2ST mix
mix
(85)
#6
t
t=
T
2ST
2ST
mix
(86)
55
T
1
19

---

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward MDPs
Subsequently, Eq. (82)- (83) obtaining by using the definition of epoch-wise state-action pair visitation frequencies ve(s,a) and the epoch termination trigger condition in Line 13 of Algorithm 2. Finally, we obtain Eq. (84) by the using Proposition 18 in Appendix C.2 of (Auer et al., 2008).
20


Reviews:
[{"review_id": "lkpQZ6pqur", "reviewer": "Reviewer_ronT", "summary": "The paper addresses regret minimization in infinite-horizon MDPs with average reward optimality criteria. Specifically, the aim of the paper is to show a quantum speedup in the regret by employing quantum mean estimators. The paper presents an optimistic algorithm, a variation of the classical UCRL adapted to the quantum realm, which achieves a regret rate of order $\\log(T)$ and various other factors (possibly unnecessary) of $S, A$. The regret result is given with the corresponding theoretical analysis.", "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 the reviewer for their thoughtful review. We address each point carefully below, hoping to clarify our contributions clearly.\n\n## **Writing style intended for ML community**\n\nIndeed, our intended audience is the ML/RL community, which may not be deeply familiar with quantum computing. To address this, our manuscript provides comprehensive background in Sections 1–2, including:\n\n- Definitions 1–3 (page 2-3): clearly defining classical random variables, quantum experiments, and quantum evaluation oracles.\n- Lemma 1 (pages 3–4): clearly explaining the quantum mean estimation lemma critical for our quantum speedups.\n- Appendix B explicitly details Quantum Amplitude Amplification (QAA), foundational to quantum mean estimation.\n\nThese definitions and explanations are designed specifically for researchers familiar primarily with classical RL.\n\n## **How quantum computing improves statistical complexity**\n\nWe appreciate your insightful hypotheses, all of which correctly capture our quantum RL framework:\n\n- Implicit statistical structure: \n  Quantum computations inherently encode probability distributions within quantum states' amplitudes, adding implicit side information absent in classical samples.\n\n- Computational speedup vs. statistical barriers:  \n  Our framework leverages quantum computation’s unique statistical properties (beyond computational speedup alone), enabling quantum mean estimation with significantly reduced sample complexity.\n\n- More information per sample:  \n  Quantum states carry richer statistical information due to superposition, fundamentally enhancing each quantum sample’s informational content.\n\nQuantum computing fundamentally accelerates mean estimation via Quantum Amplitude Estimation (QAE) [1]. By encoding probability distributions directly into quantum amplitudes, QAE estimates expectations through Grover-like iterations [2], achieving quadratic improvement in the required number of samples compared to classical methods. Thus, our quantum approach translates quadratic mean-estimation improvements directly into regret improvements from classical $ \\tilde{O}(\\sqrt{T}) $ to quantum $ \\tilde{O}(1) $.\n\n## **Concrete illustrative example**\n\n\nConsider an infinite horizon RL scenario for dynamic resource allocation in large-scale communication networks, a classical RL application. At each time step, the RL agent decides resource allocations (bandwidth, routing paths, etc.) based on observed network states, including current node congestion and usage levels. Classically, accurately estimating next-state transition probabilities (e.g., likelihood of congestion patterns given certain actions) typically requires extensive repeated sampling and interaction with the network, causing delays and inefficient resource utilization.\n\nIn our quantum setting, imagine a scenario where a quantum oracle—consistent with standard quantum oracles extensively studied in quantum optimization and Grover algorithms [2]—encodes the entire probability distribution of next network states into quantum states as a superposition. Such quantum oracles could realistically be implemented via quantum sensors or quantum-assisted sampling techniques that inherently exploit quantum mechanical effects (e.g., interference, coherence). By using Quantum Amplitude Estimation (QAE), our quantum RL agent directly accesses these encoded probability distributions, rapidly and accurately estimating expected state transitions using significantly fewer interactions compared to classical sampling.\n\nThis quantum-enhanced method fundamentally reduces statistical complexity and significantly accelerates policy learning, leading to improved real-time decisions in critical scenarios (e.g., minimizing congestion, maximizing throughput). Such quantum-assisted techniques align with emerging research trends in quantum technology, where quantum-based sensors and simulators increasingly enable access to rich statistical data through quantum sampling.\n\n\n## **Regret reporting clarification**\n\nThank you for highlighting this point. Our regret bound is explicitly reported as $ \\tilde{O}(1) $, where $ \\tilde{O} $ hides logarithmic factors in $T$. As defined in footnote 1 on page 1, the growth is at most logarithmic in  $T$.\n\n##\nWe hope this clarifies our work clearly and kindly ask for reconsideration of your evaluation.\n\n\n**References:**\n\n[1] Quantum Sub-Gaussian Mean Estimator, 2021.  \n\n[2] A fast quantum mechanical algorithm for database search, 1996.", "claims_and_evidence": "I could not understand most of the claims made in the paper.", "methods_and_evaluation_criteria": "Evaluating the efficiency of a learning algorithm through a regret upper bound is standard in the RL theory literature.", "theoretical_claims": "I did not check the proofs of the claims. The reported regret result looks reasonable once the reader accepts the faster mean estimation rate, although the latter may be hard to conceive.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This paper follows the literature on regret minimization for average reward MDPs, introducing quantum tools in the regret analysis. To the best of my knowledge, the latter addition is novel.", "essential_references_not_discussed": "I am not familiar with the literature of quantum machine learning. The references provided for regret minimization in average reward MDPs look fine.", "other_strengths_and_weaknesses": "General comment:\n\nFirst, I shall mention that I come from an RL background, with knowledge of RL theory, but I know nothing of quantum computing and quantum machine learning. That said, if the intended audience of the paper is the RL community, then the presentation shall arguably be adapted to be accessible to RL researchers, as the current explanations of quantum aspects may result hard to grasp. If the intended audience is something else, then fine.\n\nHowever, I have one main comment to share, which is the main reason behind my confusion and corresponding evaluation. How can a (new) model of computation of any kind improve the *statistical complexity* of reinforcement learning? From my understanding, the statistical barriers of average-reward MDPs (i.e., regret lower bound) do not depend on the choice of computation model. Thus, I do not understand how quantum computing can break the statistical barriers in this sense. I am formulating some (potentially dumb) hypotheses below:\n- There is an additional implicit statistical structure/side information added to the standard RL model. Then, the general regret barrier does not hold anymore, and speedups can be achieved. If this is the case, this additional structure/information shall be explained and discussed with clarity.\n- Quantum computing provides faster *computation*, which can speedup the regret rate of \"tractable\" algorithms (a.k.a. algorithms that were considered computationally intractable are now tractable thanks to quantum computing). However, the regret barriers do not refer to computationally tractable algorithm, but to any algorithm. Thus, they cannot be overcome with computation speedup only.\n- The quantum perspective allows to carry more information in a single sample, which leads to a better sample complexity/regret. However, this sounds like changing the problem and the corresponding result shall not be compared with traditional results (a.k.a. we have a small regret, but for a different problem!). If this is the case, then it makes sense to say that there are applications that admit this new problem formulation, in which the efficiency of learning algorithm fundamentally change. This leads to the following comment.\n- Can the authors help me processing the contribution through an example? Let us take an arbitrary application: Learning a policy to trade stocks on the market to maximize profits. At every step, the algorithm collects a sample of the price of some stocks of interest, which constitutes the state information together with the owned stocks and their value. The current policy decides whether to buy/sell stocks at the collected prices. How can quantum computing speedup learning in this scenario?\n\nWhile I am providing a negative evaluation, it shall be noted that I could not understand the contribution here, so my score can be weighed accordingly.", "other_comments_or_suggestions": "Reporting the regret as $O(1)$ is kind of odd since the regret actually depends on $\\log T$. Why not reporting $O(\\log T)$ then?", "questions_for_authors": "See above.\n\n\n------\n\nAfter reading the authors' responses, I have a better understanding of the contribution of this submission. I am increasing my score to weak accept, although I believe the presentation shall be heavily edited to avoid confusion about the setting considered 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": {}}, {"review_id": "3vkk8sRTKz", "reviewer": "Reviewer_UqgN", "summary": "Summary\nThe authors study the problem of regret analysis—specifically, finding the policy that minimizes regret—when navigating Markov Decision Processes (MDPs) with simultaneous quantum and classical access to the environment. They propose a concrete quantum protocol based on the quantum mean estimation algorithm, employing a tabular approach to identify an optimal policy for navigating an MDP. Through thorough theoretical analysis, they demonstrate that their policy achieves an exponential improvement in regret scaling with respect to the parameter T (the horizon or number of rounds).\nBeyond utilizing both quantum and classical access to the environment, the authors introduce two key assumptions: (i) The MDP has finite mixing time. (ii) The reward function is known.\nThe first assumption ensures that the state-action pair table is sufficiently populated through the exploration performed by the learning algorithm.", "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 thank the reviewer for their positive feedback and valuable suggestions. We address each point carefully and explicitly below:\n\n## **Comparison with [1]**\n\nWe clarify that the problem studied in [1] is fundamentally different from our setting:\n\n- **Episodic vs. Infinite Horizon:**  \n  Reference [1] focuses on episodic RL with a finite horizon, whereas our work investigates infinite-horizon average-reward RL. Infinite-horizon RL is generally considered a more challenging setting because the optimal policy needs to sustain performance indefinitely without episodic resets, requiring different theoretical frameworks, convergence analyses, and stability considerations.\n\n- **Technical Differences:**  \n  The techniques in [1] depend heavily on episode-wise decomposition, and their quantum acceleration leverages lazy updating with episodic resets. Conversely, our infinite-horizon scenario necessitates a novel momentum-based updating framework (Eqs. 21–25) to avoid repeated quantum measurement collapse. Unlike the episodic case, infinite-horizon settings cannot directly leverage the lazy episodic updating; thus, our work introduces entirely novel analytical tools (Lemma 2–3, Eqs. 34–38).\n\nOur contribution is the first to achieve quantum RL speedup in infinite-horizon average-reward settings, filling a significant theoretical gap distinct from [1].\n\n\n## **Scalability and tabular approach**\n\nWe fully acknowledge the limitation identified by the reviewer regarding the reliance on a tabular approach. Indeed, scalability to large state-action spaces is challenging, and addressing this limitation is an important direction for future work. We explicitly mention this limitation and highlight that extending our quantum RL framework beyond tabular methods (e.g., using function approximation methods or linear mixture models) is an essential next step, deserving further exploration.\n\n\n## **Conceptual and technical novelty compared to classical methods**\n\nWe appreciate the reviewer highlighting this critical point. We emphasize our conceptual and technical novelties:\n\n- Our work is the first to provide a quantum RL framework and regret analysis for infinite-horizon average-reward settings, a distinct and more challenging problem than episodic RL.\n- Unlike classical methods, our work uses quantum amplitude estimation (QAE) techniques that fundamentally enhance statistical complexity, achieving exponential improvement ($ \\tilde{O}(1) $ regret) over classical $ \\tilde{O}(\\sqrt{T}) $.\n- The momentum-based updating scheme (Eq. 21–25) developed particularly to avoid quantum state collapse is novel and uniquely necessary for infinite-horizon RL. The absence of martingale techniques—ubiquitous in classical regret analysis—further differentiates our analytical approach (Lemma 2–3, Eqs. 34–38).\n\nOur contribution not only establishes theoretical quantum RL foundations in an unexplored domain but also provides novel tools essential for future research in quantum RL.\n\n\nWe sincerely hope this addresses your concerns and clearly clarifies our contributions and novelties. We kindly ask you to reconsider and possibly improve your evaluation in light of these clarifications.\n\n\n**References:**\n\n[1] Provably Efficient Exploration in Quantum Reinforcement Learning\nwith Logarithmic Worst-Case Regret, 2024.", "claims_and_evidence": "Yes, the claims are clearly stated in well-formulated lemmas and theorems, and the provided proofs appear to be sound and convincing.", "methods_and_evaluation_criteria": "All statements are supported by rigorous lemmas and theorems.", "theoretical_claims": "All theoretical claims are clearly stated, and the provided proofs appear solid and well-structured.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The authors provide a thorough review of the classical setting of the problem and offer a well-structured overview of the quantum methods and generalizations built upon it.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "-This work highlights a significant exponential speedup in regret scaling with respect to T. The authors employ a well-structured tabular approach, leveraging clever exploration and the quantum mean estimation algorithm to efficiently collect the necessary information to solve for the optimal policy.\n-The results seem to be both conceptually, and technically close to the series of works cited including https://arxiv.org/pdf/2205.14988 and especially https://arxiv.org/pdf/2302.10796 where the latter obtains an exponential improvement in regret (w.r.t T) for exploration in reinforcement learning. It is not clear to me in what sense is the present manuscript an improvement? What does it achieve that was not achieved there? Are the techniques different?\n- In terms of overall applicability a weakness is the reliance on a tabular approach, which limits scalability when the number of states becomes large—a common challenge in reinforcement learning applications. However, this work could serve as an important foundation for extending these methods to model-free approaches.", "other_comments_or_suggestions": "The main comment/suggestion is to clearly explain in what conceptual and technical sense does this work go beyond the lines of works which achieved the sqrt T ->log T improvement.\nSince this types of work have mostly if not exclusively theoretical relevance (I would be happy to be corrected here), the relevance of this work higes on novel conceptual or technical contributions. \nWithout this being clarified I cannot be confident in giving this paper a high score.", "questions_for_authors": "See comments and suggestions", "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": "4OkkxlU2or", "reviewer": "Reviewer_nttZ", "summary": "This paper leverages the result in Cornelissen et al. for quantum acceleration of the mean estimation problem for $d$ dimensional random variable when the number $n$ of quantum experiments is larger than the dimension $d$.\nLeveraging this fact the authors can reproduce the standard UCRL proof for Jaksch et al. 2010 with a tighter confidence radius for the estimated transition. This leads to logarithmic regret as opposed to the classic $\\sqrt{T}$ regret bound.\n\n#### After rebuttal\n\nMy opinion about the paper did not change", "questions": "", "limitations": "", "rating": 2, "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 thank the reviewer for the insightful comments and valuable suggestions. Below we carefully address each of your concerns:\n\n## **Bound on epochs $E$ in Equation (84)**\n\nWe appreciate your careful review. Indeed, your observation is correct that the bound on the number of epochs $E$ as $E \\leq poly(SA\\log T)$ is essential. This bound follows directly from Proposition 18 in Appendix C.2 of [1], explicitly mentioned right after equation (86) in our manuscript. We will further clarify and explicitly reference this in the revised version for clarity.\n\n\n## **Missing references in classical regret minimization**\n\nThank you for suggesting these essential references [2] and [3]. We  agree that these works provide essential context and relevance to classical regret minimization. We will incorporate them explicitly in the revised manuscript to improve completeness.\n\n\n## **Definition and example of quantum experiment in RL**\n\nWe clarify that a \"quantum experiment\" in reinforcement learning corresponds exactly to performing a state-action transition and obtaining the next state encoded as a quantum state $|\\psi\\rangle$. Specifically, given classical state-action pairs $(s,a)$, our method obtains quantum samples by leveraging a quantum oracle that prepares the superposition state $|\\psi\\rangle = \\sum_{s'} \\sqrt{P(s'|s,a)}|s'\\rangle$, representing the probability distribution of transitioning to the next state. Each quantum sample preparation constitutes precisely one quantum experiment in our RL setting.\n\n## **Interaction protocol between learner and environment**\n\nWe agree with the reviewer on their interpretation. Our learner performs one quantum experiment at each step. Specifically, after observing a classical state-action pair, the agent queries the quantum oracle, performing a quantum experiment to obtain the next state as a quantum superposition. Thus, at each interaction step, one trajectory step is sampled quantum-mechanically rather than classically.\n\nWe will clearly describe this interaction protocol in our revision to eliminate any confusion.\n\n## **Technical novelties in the algorithms and proofs**\n\nWe respectfully highlight our technical and conceptual novelties:\n\n- Our paper provides the first quantum RL framework for infinite-horizon average-reward MDPs, a notably more challenging setting compared to finite-episode or discounted problems. The quantum infinite-horizon setting introduces complexities (e.g., convergence analysis without episodic resets, the inability to directly apply classical martingale techniques and the quantum measurement-collapse issue) not encountered in classical analyses or in finite-horizon analyses.\n\n- To handle the critical quantum measurement-collapse issue (absent in classical RL), we developed a novel momentum-based updating scheme (Eq. 21–25). In addition, unlike [1], our analytical approach avoids classical martingale-based arguments and introduces entirely novel analytical techniques (Lemma 2–3, Eqs. 34–38).\n\n- Thus, our proofs, while building upon foundational results such as [1] and [4], involve substantial technical novelties tailored specifically to quantum infinite-horizon RL, beyond straightforward combination of known results.\n\nWe sincerely believe these novel contributions significantly enrich the theoretical landscape of quantum RL.\n\nWe hope these clarifications address your concerns, highlighting our work's relevance, novelty, and contribution clearly. We kindly request reconsideration of your evaluation in light of these clarifications.\n\n**References:**\n\n[1] Near-optimal Regret Bounds for Reinforcement Learning, 2008.\n\n[2] Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs, 2024.\n\n[3] Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes, 2020.\n\n[4] Near-optimal quantum algorithms for multivariate mean estimation, 2022", "claims_and_evidence": "The theorems are clearly proven", "methods_and_evaluation_criteria": "Not applicable since there are no experiments", "theoretical_claims": "Yes, I checked them.\nI don't know where the last bound in equation(84). It seems that the author use a bound on the number of epochs which is polynomial in $S,A$ but logarithmic in $T$, that is $E \\leq poly( S A \\log(T))$. However, this bound seems to be not proven in the text.", "experimental_designs_or_analyses": "There are not experiments", "relation_to_broader_scientific_literature": "I am not qualified to assess the quantum computing related literature, I think that there are some missing references in classical \nregret minimization approaches in infinite horizon reinforcement learning such as\n\nHong et al., 2024 Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs\n\nWei et al. 2020, Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes", "essential_references_not_discussed": "see above", "other_strengths_and_weaknesses": "The paper has the potential to be an interesting contribution but there are significant motivation issues in my opinion.\n\nFirst of all, it should be clear what the consequences of this exponential improvement in regret are.\nThe author should say that having access to $\\mathcal{O}(1/\\epsilon)$ quantum experiments it is enough to learn an optimal policy ( up to $\\epsilon$ precision) while in the classical setting $\\mathcal{O}(\\epsilon^{-2})$ samples are needed.\n\nHowever, it should be made clear what is a quantum experiment in the context of reinforcement learning. The author just report the standard definition but an RL example is needed to convince the RL audience that this result is worth being published.\n\nMy recommendation is weak reject because the proof is trivial once endowed with the result from Cornelissen et al. 2022 and Jaksch et al. 2010. This is not a problem per se but it makes the technical contribution of the paper not very interesting.\nI am willing to raise my score if the author clarifies the learning problem considered and provide an example of what is a quantum experiment in the context of sampling a trajectory from the MDP.", "other_comments_or_suggestions": "See above", "questions_for_authors": "What is a quantum experiment in reinforcement learning? Please provide an example.\n\nMoreover, the interaction protocol between the learner and the environment is not clear does the agent collect a trajectory\nand perform a quantum experiment at each step ?", "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: This work considers the online reinforcement learning problem of controlling an unknown MDP to optimize the long-term average reward. As opposed to the classical setting, they consider a quantum framework (where quantum states carry richer information) and proposed an optimistic-based approach. In this setting, they demonstrate a (at first surprising) regret guarantee of order $\log(T)$, in shark contrast with the classical $\sqrt{T}$ rate (for which there exists both upper and lower bounds). 

On the technical side, this work extends the result for quantum MDP from episodic to infinite horizon with average reward and leverages the seminal UCRL approach. Reviewers acknowledged the novelty and interest of some of the technical derivations, in particular the momentum-based updates. 

The paper also suffers from several shortcomings: 
1) the motivation behind the « quantum » MDP framework and its real-world applicability - counterbalanced by the theoretical nature of the contribution.  
2) the presentation/positioning of the paper which somehow compares the result in the classical setting and the quantum setting. While there is no superiority of one result over the other, it demonstrates how richer information (of the quantum states) can translate in better learning rates. 
3) the incrementality of the derivation compared to previous works. Yet, some aspects has been recognized novel and of independent interest. 

Given the author engagement during the discussion phase, I am relatively confident than the above weaknesses can be addressed in a revised version. Thus, I recommend acceptance if the authors can 1) strengthen the pedagogical introduction to quantum concepts and stress the difference of information richness compared to the classical setting 2) detail the comparison with previous works and highlight clearly the technical challenges and novelty in extending them.
Decision: Accept (poster)