Quantum Algorithm for Online Learning of MDPs with Continuous State Space
Quantum algorithm;Markov decision processes;Online algorithms;Quantum reinforcement learning
Yes
No ethics review needed.
See Weaknesses
Developing a new reinforcement learning (RL) algorithm within the quantum computing framework holds promise for future advancements, and the improved regret is interesting.
This submission explores quantum reinforcement learning (RL) algorithms for Markov Decision Processes (MDPs) with continuous state spaces (referred to as Lipschitz-MDPs) under an infinite-horizon average-reward framework. The work extends classical reinforcement learning approaches in the same setting and claims an improved regret rate when compared to classical computational settings. Additionally, it introduces a quantum-enhanced version of value iteration, getting some computational speed up.
I think the paper needs to be crystal clear about how the algorithms in the quantum computing setting are differentiated from the classical setting. The current writing does not sufficiently highlight what makes quantum computing interesting in terms of the algorithm design and analysis, and what is an additional layer (novel contribution) that the submission adds on in both settings. 

-	The claim is that the regret rate is improved: it is not clear how this gain comes from the quantum computational setting. 

-	I am not sure section 4.1 has anything to do with the specific constraints of quantum computing setting. I do not clearly see why the approximate value iteration is surprising (as it takes one page to describe that). 

-	I wonder why the focus is specifically on the Lipschitz-MDP. Are there any other quantum results for Tabular/Linear MDPs? What are the benefits for more standard models?


Below are more detailed comments:

-	Line 71-12: Is the improvement in regret-guarantees a fair comparison to classical settings? Bounds given by [18] – does it match the classical lower bound, and quantum setting can break it?

-	Line 108-114: Discussion on KP-trees is so superficial. It doesn’t help at all for non-quantum experts like myself, and I do not think this level of discussion is not useful for quantum experts either. 

-	Lemma 3: Why $\sqrt{S}/\epsilon$ is necessarily better than S^2A that without epsilon dependence?

-	Line 330: “only collect quantum states via quantum-accessible environments” – is this a good thing or bad thing? If it is a bad thing, how can the regret be improved? 

-	Eq (12): what is garbage(x)?

-	Definition 4: why sqrt is over pi? 

-	Algorithm 1: Could you clarify how that is different from UCRL2? 

Overall, I am genuinely interested in what makes algorithms different in quantum computing settings, but the current writing of the paper obscures many important points on what makes “quantum” setting interesting, compared to classical settings. At this moment, I am inclined to rejection.
Yes
No ethics review needed.
Please consider the suggestion in the weaknesses section.
The problem of online learning in continuous-state MDPs is both significant and broadly impactful, and this work introduces a novel quantum algorithm that achieves a quantum speedup on the number of time steps, as well as on the size of state space and action space.

This paper extends the value iteration subroutine into quantum domain, which might be useful in other quantum machine learning algorithms.
In this paper, the authors tackle the problem of online learning in MDPs with continuous state spaces under the average reward model. They propose a quantum algorithm that achieves a regret bound of $\tilde{O}(\sqrt{T})$ in one-dimensional continuous state spaces, representing a quantum speedup over the classical $\tilde{O}(T^{2/3})$ regret bound. Additionally, they establish a $\tilde{O}(T^{1-1/2d})$ upper bound for general d-dimensional state spaces. To accomplish these results, the authors introduce a quantum adaptation of the value iteration method, which provides a subquadratic speedup concerning the state space size and a quadratic speedup for the action space size. They also present a thorough theoretical analysis, demonstrating that the proposed quantum-extended value iteration converges to the optimal average reward within a small additive error.
This paper currently includes minimal preliminaries on quantum computing, which may limit accessibility for readers outside the quantum computing field. A more comprehensive introduction on quantum computing, such as basic concepts of qubits and unitaries, the intuition on quantum speedup, and the rationale for quantum-accessible environments, would enhance comprehension and broaden the paper’s appeal to readers from diverse research backgrounds.
Yes
No ethics review needed.
- In line 113-114, they said "Moreover, (all or part of) the entries of $u$ can be classically updated by writing new values into the KP-tree in
 $\widetilde{O}(S)$ time." I think this could be a little misleading. For example, executing an "initialization" operation which set the vector stored in the KP tree to be a zero vector could be done in $\widetilde{O}(1)$ time. A more formal statement concerning this point could be referred to Theorem 2.11 in the arxiv version of [26].  
- In line 229, "From hereon" -> "From here on".
- Line 828, "ancilla quantum sates" -> "ancillary quantum states"
- In line 843, "Let $W\subset S$ be the set of entries that satisfy some given condition". Could the authors explain more about the conditions for W?
- The authors gave a novel quantum algorithm that achieves a better regret bound in 1-dimensional state space and may have less complexity per iteration compared with formal classical algorithms, suggesting quantum advantages in solving this problem.
- They proposed a quantum extended value iteration subroutine and proved approximate convergence guarantees for an approximate analog of value iteration, theoretically analyzing their algorithm with provable guarantees.
Whether quantum algorithms could speedup machine learning tasks is of great interest in quantum computing.  In this paper, the authors gave a quantum algorithm for learning Markov Decision Processes (MDPs) with continuous state space in the average reward model. Their algorithm achieves a better regret bound in 1-dimensional state space and less complexity per iteration compared with formal classical algorithms. To achieve this, they proposed a quantum extended value iteration subroutine and proved approximate convergence guarantees for an approximate analog of value iteration.
- Althought the paper obtained a better regret bound $O(T^{1/2})$ for $1$-dimensional state space, it seems that this improvement does not hold for state space with higher dimensions (>3). Could the authors explain why this is the case, and explain possible limitations?
- The change of the iteration complexity is from $O(S^2 A)$ (classical) to $O(S^{1.5}\sqrt{A}/\varepsilon)$ (quantum), which is subquadratic. 
- The techniques to obtain quantum speedups are quantum mean estimation and norm estimation, which looks not so novel. Could the author explain their technical novelties from a quantum computing perspective?
This paper proposes a quantum online algorithm for learning Markov Decision processes with continuous state space, achieving a $O(\sqrt T)$ regret, improving upon the best known classical result of $O(T^{2/3})$.
@inproceedings{
anonymous2024quantum,
title={Quantum Algorithm for Online Learning of {MDP}s with Continuous State Space},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=IEnYsFjFzI},
note={under review}
}
We propose a novel quantum online algorithm for learning Markov Decision Processes (MDPs) with continuous state space in the average reward model. Our algorithm is based on the line of work on classical online UCCRL algorithms by Ortner and Ryabko (NeurIPS'12). To the best of our knowledge, our work is the first to consider MDPs with continuous state space in the fault-tolerant quantum setting. In the case where the state space is one-dimensional, we show that, via quantum-accessible environments, our quantum algorithm obtains a $\tilde O(T^{1/2})$ regret, improving upon the $\tilde O(T^{2/3})$ bound of Lakshmanan, Ortner, and Ryabko (PMLR'15), where $T$ is the number of iterations of the algorithm. For a general $d$-dimensional state space, the regret is bounded by $\tilde O(T^{1-1/2d})$. Our quantum algorithm uses quantum extended value iteration as a subroutine, which is our second main contribution, and may be of independent interest. We show that quantum extended value iteration achieves a subquadratic speedup in the size of the discretized state space $\mathcal{S}$ and a quadratic speedup in the size of the action space $\mathcal{A}$, as compared to its classical counterpart. As our third contribution, we study the limiting behaviour of the sequence of value functions generated by quantum extended value iteration. We show that the sequence converges to the optimal average reward $\rho^*$ up to $\epsilon$ additive error, for some small $\epsilon>0$.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Quantum algorithm Markov decision processes Online algorithms Quantum reinforcement learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/1392129bcee485fca4adca851bdb7e3a56cb9a3f.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Quantum Algorithm for Online Learning of MDPs with Continuous State Space
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission