Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret

We appreciate the thoughtful review and have carefully considered the concerns raised. We would like to address the primary issue of perceived lack of novelty by providing a detailed clarification of the unique contributions of our work.

Regarding lack of novelty. Our work acknowledges its relationship with [1], extensively discussed in the related work and main paper, particularly in Remark 5.1. While it is true that multi-armed bandits and linear bandits are special cases of tabular and linear mixture MDPs, respectively, learning MDPs with multi-step decision-making introduces substantial complexity beyond bandit scenarios. We highlight the technical difficulties and our novel contributions.

Algorithm design novelties:

• One can regard the bandits as the MDPs satisfying (i) the state space only contains a single dummy state $s_{\mathrm{dummy}}$; (ii) $H=1$; and (iii) the reward only depends on the action chosen by the learner, i.e., $r(s_{\mathrm{dummy}}, a) = r(a)$. In this case, the learner can repeatedly pull a particular arm $a$ to collect sufficient samples to estimate $r(s_{\mathrm{dummy}}, a)$. However, in online RL, the state will transit according to the transition kernel, preventing repeated arm pulls for the desired estimator. To address this, we introduce a novel adaptive lazy-updating rule, quantifying the uncertainty of the visiting state-action pair (covariance matix in linear setting) and updating the model infrequently through the doubling trick. This algorithm design, absent in previous works on quantum bandits [1] and quantum RL with a generative model [2], connects online exploration in quantum RL with strategic lazy updating mechanisms, inspiring subsequent algorithm design in online quantum RL.

Technical novelties:

• In the tabular setting, a significant technical challenge is obtaining a high probability regret bound, as vanilla regret decomposition (e.g., the one used in UCBVI) leads to a martingale term of order $\mathcal{O}(H\sqrt{T})$. Though it is not the dominating term in the classical setting, it would become the dominating term in our setting. We found that another regret decomposition (i.e., the one used in EULER) based on the expected Bellman error cleverly bypasses such martingale terms in the regret, thus achieving the desired regret bound.
• In the linear setting, the algorithm requires a novel design to leverage the advantage of quantum mean estimation. Classical linear RL analysis heavily relies on martingale concentration, such as the well-known self-normalized concentration bound for vectors. However, in quantum RL, there is no direct counterpart to martingale analysis. Consequently, we redesign the lazy updating frequency and propose an entirely new technique to estimate features for building the confidence set for the model. Notably, previous works on quantum bandits [1] do not need to take this step since there is no unknown transition kernel in their setting. Moreover, estimating the features poses a subtle technical challenge, as elaborated in Equation (5.5). Our proposed algorithm (Algorithm 2), which features binary search and quantum mean estimation, successfully addresses this technical challenge. Meanwhile, the quantum samples used in feature estimation approximately equal the number of quantum samples in each phase, eliminating extra regret for this additional feature estimation. This algorithm design (Algortihm 2) and theoretical analysis are entirely new in the literature on (classical and quantum) RL theory. We sincerely hope the reviewer can reconsider the novelty of this part. We believe that introducing a new algorithm design and novel techniques with interesting results is sufficient for the first theoretical study in online quantum RL (with function approximation).

Significance of our results:

• Beyond our novelties in algorithm design and techniques, the paramount significance lies in the message that quantum computing can potentially provide a speedup for online sequential decision-making problems under the framework of MDPs. The logarithmic regret obtained is markedly different from classical $\sqrt{T}$ regret, providing a theoretical guarantee for the potential superiority of quantum RL over classical RL. As the first rigorously theoretical work on online quantum RL, our research is deemed significant, paving the way for future investigations in the realm of quantum RL.

According to your concerns, we have made a thorough revision of our description of novelties. Please refer to the introduction section, Remark 5.1, the proof sketch of Theorem 5.2, and Appendix B.2 for details, as highlighted in blue.

Regarding regret lower bound. Please see our general response for details.

[1] Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets.

[2] Quantum algorithms for reinforcement learning with a generative model.

Thanks for your review and positive feedback. We will try to address your concerns in the following.

Q1: The discussion on sample complexity is not enough. For example, it would be better to discuss why the $\sqrt{T}$ factor is removed. Is that because of Lemma 3.1 and Lemma 3.2 such that the previous $\epsilon^{-2}$ sample complexity can be reduced to $\epsilon^{-1}$ sample complexity so that the exploration can be more aggressive?

A1: Yes, the logarithmic regret in our work is primarily attributed to the speedup of quantum mean estimation (Lemma 3.1 and Lemma 3.2). Simultaneously, the $\epsilon^{-1}$ sample complexity leads to more conservative exploration instead of aggressive, as we can make more accurate estimations. This conservatism is further reflected in the bonus term; our bonus term $1/n_h^k(s, a)$ is smaller than the classical $1/\sqrt{n_h^k(s, a)}$, resulting in a more cautious exploration strategy. We appreciate your valuable insights and comments, and we have incorporated these discussions into the introduction, highlighted in blue.

Moreover, the strategic combination of the speedup in quantum mean estimations and exploration in online quantum RL is the central focus of our algorithm design and analysis. Please refer to our introduction section and other parts of the main paper for a detailed elaboration of this aspect.

Q2: Besides the previous comment, I'm also looking for discussions about the lower bounds (or at least some conjectures). For example, if the dependency on $d, H$ within the lower bounds still match (Zhou et al., 2021) or not?

A2: Please see our general response for details.

Q3: Can one directly covert the observation in classical RL to a quantum-accessible RL? (e.g., changing the Atari games to quantum). If the quantum RL can be used in classical RL tasks, then how would the current $\log T$ bound break the classical $\sqrt{T}$ regret bound?

A3: We can run classical RL on quantum computers as a special case. For instance, we can play classical Atari games on quantum computers when they become universal and have enough number of qubits to execute the programs. That is, quantum computers can simulate classical RL environments. Moreover, quantum accessible environments empower the agent to hold the quantum superpositions over states and actions, which encode the stochasity of the envrionments. In contrast, classical environment only returns random samples from the environment.

Q4: If the current algorithm can only be used in quantum-accessible RL, and we cannot convert a classical RL task into quantum, then how will this algorithm contribute to real-world RL tasks?

A4: Same as A3, we can regard a classical RL task as a quantum RL task but never uses superposition. The algorithm proposed in this paper is a quantum RL algorithm and can only be executed on quantum computers. In terms of the contribution to real-world RL tasks, due to the limitation of current quantum computers we have to focus on theoretical research of quantum RL. Nevertheless, our result is fundamental as we proved the first poly-log regret results for quantum RL, and we believe that our work will have real-world impact after the capability of quantum computers significantly grows.

Thanks for your review and positive feedback. We will try to address your concerns in the following.

Q1: Regret lower bound.

A1: Please see our general response for details.

Q2: The introduction/description of the Quantum UCRL algorithm is not clear enough. For example, the notation $\bar{\varphi}_{h+1}, \mathcal{D}_h(s_h^k, a_h^k)$ appeared in Algorithm 4 is not defined clearly.

A2: We greatly appreciate the reviewer's suggestion to clarify the confusing notations/definitions in our paper. To be specific, the place $\bar{\varphi}\_{h+1}$ appeared in Algorithm 4 (i.e., Line 7 of Algorithm 4) is exactly the definition of $\bar{\varphi}\_{h+1}$. According to the context, $\bar{\varphi}\_{h+1}$ is defined as the output of the oracle $\bar{\mathcal{P}}\_h$ (defined by Eqn. (3.2)) queried on input $\left|s_h^k, a_h^k\right\rangle|0\rangle$. We should use $\ket{\bar{\varphi}\_{k, h+1}}$ to represent this output because it is a quantum superposition obtained in episode $k$. Similarly, the definition of $\bar{\varphi}\_{h+1}^{-1}$ is $\bar{\varphi}\_{h+1}^{-1} := \bar{\mathcal{P}}\_h^{-1} \left|s_h^k, a_h^k\right\rangle|0\rangle$ (we will also use $\ket{\bar{\varphi}\_{k,h+1}^{-1}}$ instead of $\bar{\varphi}\_{h+1}^{-1}$ in the revised version of the paper).

The notation $\mathcal{D}_h(s_h^k, a_h^k)$ is defined at Line 2 of Algorithm 4 (the third bullet point). It is defined as the collection (i.e., the multiset) of all the quantum samples obtained for the state-action pair $(s_h^k, a_h^k)$ at step $h$. We will use multiset $\mathcal{D}_h(s_h^k, a_h^k)$ as input to call the quantum multi-dimensional amplitude estimation algorithm (Lemma 3.1).

Q3: $\bar{\varphi}\_{h+1}$ is a quantum state in superposition. How could Algorithm 4 line 9 update the counter according to the superposition? Please correct me if I missed anything.

A3: According to the definition, $\bar{\varphi}\_{h+1} = \bar{\mathcal{P}}\_{h} \ket{s_{h}^k, a_{h}^k} \ket{0}$ is indeed a quantum superposition, with which we cannot update the counter. Fortunately, $(s_h^k, a_h^k)$ is a classical state-action pair instead of a quantum superposition, and $\ket{s_h^k, a_h^k}$ is a standard basis vector of Hilbert space $\bar{S} \times \bar{A}$ (defined at the beginning of the second paragraph of Section 3.2) encoded by $(s_h^k, a_h^k)$. This is because $s_h^k$ is the output of Algorithm 3, which always outputs a classical state sampled from some distribution. $a_h^k$ is also a classical action since $a_h^k := \pi_h^k(s_h^k)$. Therefore, we can update the counter according to $(s_h^k, a_h^k)$. Moreover, this is a key reason why we need to design a complicated phase-based "sampling" procedure in Algorithm 4 to obtain valid quantum samples, which is a dramatic difference between quantum RL and classical RL.

Q4: Why the binary oracle is not considered in the tabular setting? What is the main difficulty in generalizing the result of Lemma 3.1 to binary oracle?

A4: We can definitely generalize the results of Lemma 3.1 to Lemma 3.2 with binary oracle in the tabular setting. This is done in the following way. For a fixed $(s, a)$ pair, we define the binary oracle $U_{s, a} : \ket{s, a} \ket{s'} \ket{0} \to \ket{s, a} \ket{\vec{1}[s']}$, where $\vec{1}[s']$ is an $S$-dimensional standard basis vector encoded by $s'$ (i.e., a one-hot vector with non-zero entry at the $s'$ position). Combined with the probability oracle $\bar{\mathcal{P}}\_h: \ket{s, a} \ket{0} \to \sum_{s'} \sqrt{\mathcal{P}\_h(s' \mid s, a)} \ket{s'}$, we can estimate the $S$-dimensional vector $(\mathcal{P}\_h(s_1 \mid s, a), \mathcal{P}\_h(s_2 \mid s, a), ..., \mathcal{P}\_h(s_{S} \mid s, a))^\top \in \mathbb{R}^S$ suppose $s'$ is enumerated from the state space $\{s_1, s_2, ..., s_{S}\}$ using Lemma 3.2. Since we hope the $l_1$ estimation error to be bouned by $\epsilon$, the sample complexity of such estimation is $\mathcal{O}(S \log (S/\delta) / \epsilon)$, the same as Lemma 3.1. Since the target vector $(\mathcal{P}\_h(s_1 \mid s, a), \mathcal{P}\_h(s_2 \mid s, a), ..., \mathcal{P}\_h(s_{S} \mid s, a))$ is actually a distribution over the state space, we can also encode this vector as the amplitude of a quantum superposition and use Lemma 3.1 to estimate the amplitude. We choose Lemma 3.1 mainly because the quantum multi-dimensional amplitude estimation subroutine is conceptually simpler without requiring an additional binary oracle, so it is more efficient in implementation.

Thanks for the authors' detailed response to my questions. I would encourage the authors to add into the paper the discussions about updating sample counters (as reviewer XG1J also has a similar concern) and generalizing binary oracle to tabular setting to make the paper more complete.

The reviewer thanks the authors for providing the regret lower bounds, converted from sample complexity lower bounds. However, in sequential decision-making, the number of decision rounds $T$ is usually the largest factor. As $T$ does not appear in the given regret lower bounds, it is hard to use the lower bound to access the upper bounds provide in this paper.

BTW, can the authors further explain how one could obtain a regret lower bound from $f(\epsilon)>g(\epsilon)$ in A sample complexity upper bound implies a regret lower bound guarantee? and it would be great if the author could provide some references for this statement.

A1: Thank you for your question. According to our established regret lower bound, we can claim that our regret is optimal in $T$ up to logarithmic terms. While this assertion may seem trivial given that our regret bounds only have a logarithmic dependency in $T$, it is crucial to highlight that the inclusion of an additional logarithmic dependency in the upper bound is a common feature in existing RL theory literature. For instance, the regret lower bound for classical tabular MDPs is ${\Omega}(\sqrt{SAH^2T})$ [1, 2]. The regret upper bound for UCBVI [3] is $\mathcal{O}(\sqrt{SAH^2T} \cdot \mathrm{log}(T))$, which is considered nearly minimax optimal. Here, minimax optimal means that the upper bound matches the lower bound, ignoring logarithmic terms. We also want to emphasize that in both classical bandits/RL and quantum bandits/RL, establishing a regret lower bound with logarithmic dependency is widely open. Given this context, it becomes particularly challenging to foresee the establishment of a $\Omega(\sqrt{S^2AH^3} \cdot \log T)$ or $\Omega(\sqrt{dH^3} \cdot \log T)$ regret lower bound.

To demonstrate the sharpness of our results, one can also examine the comparison between the sample complexity upper bound and the sample complexity lower bound to gain insights into the sharpness of the $\epsilon$ dependency, which corresponds to the dependency on $T$ in some sense (both quantify the number of episodes). Ignoring other problem parameters such as $S, A, d, H$, our regret upper bound implies a sample complexity upper bound $\mathcal{O}(\frac{1}{\epsilon}\cdot \log(\frac{1}{\epsilon}))$, and the sample complexity lower bound is $\Omega(\frac{1}{\epsilon})$. Hence, we can conclude that our sample complexity upper bound is optimal in $\epsilon$ up to logarithmic factors.

A2: There is a typo in this statement. The correct statement is that a sample complexity lower bound implies a regret lower bound guarantee. Thank you for pointing this out, and we have revised the original response and paper accordingly. We also want to emphasize that our previous reduction statement argument still holds. To illustrate our reduction more, let us delve into the following specific scenario. Suppose there is a hard instance where every algorithm necessitates $C/\epsilon$ (resp. $C/\epsilon^2$) sample complexity to obtain the $\epsilon$ optimal policy, where $C$ involves certain problem parameters (e.g., $S, A, H, d$) and sufficiently large constants. Now, assume the existence of an algorithm that achieves regret $o(C)$ (resp. $o(\sqrt{CT})$). This implies an $o(C/\epsilon)$ (resp. $o(C/\epsilon^2)$) sample complexity, which contradicts the sample complexity lower bound. Hence, we can conclude that in this hard instance, every algorithm incurs a regret at least $\Omega(C)$ (resp. $\Omega(\sqrt{CT})$). Intuitively, regret appears to be a more "challenging" notion than sample complexity, as each regret upper bound has the potential to imply a sample complexity upper bound. Consequently, establishing a regret lower bound is intuitively considered to be a relatively "easy" task compared to the sample complexity lower bound.

Regarding the reference, given the elementary nature of this result, we do not find the same form of statement in recent papers or books. However, we also do not want to claim this reduction as our new result and contribution. Moreover, we find that [2] shares a similar spirit with our reduction arguments. They provide (i) the reduction from the regret upper bound to the sample complexity upper bound; and (ii) an intuitive regret lower bound proof. In their lower bound proof, ignoring problem parameters, identifying the underlying MDP requires at least $\Omega(1/\epsilon^2)$ samples, and each will incur at least $\epsilon$ regret. Regarding $\Omega(1/\epsilon^2)$ as $T$, the final is at least $\Omega(1/\epsilon^2) \cdot \epsilon = \Omega(1/\epsilon) = \Omega(\sqrt{T})$ classical regret. Combining this proof paradigm and the sample complexity lower bound analysis in quantum RL with a generative model [5], identifying the underlying MDP requires $\Omega(1/\epsilon)$ quantum samples, and each will incur at least $\epsilon$ regret, further indicating the $\Omega(1)$ regret bound as desired. Notably, the core of this proof also implicitly converts the sample complexity lower bound to the regret lower bound. Despite slight differences from the proof paradigm in [2], we believe that our reduction statement is self-consistent and rigorous.

In response to your inquiries, we have made revisions to Appendix B.1 to provide clarification on these issues. We hope these revisions adequately address your concerns.

Thanks for your review. We would like to address your concerns as follows.

Q1: Motivating examples: It is unclear if the assumptions (access to quantum oracles and their inverse, quantum state) made in the paper are practical or not. Adding a few motivating examples where these assumptions (will) hold will make the contribution even more significant.

A1: Sure, thanks for the suggestion.

Intuitively, as long as a classical RL task can be written as a computer program with source code, the quantum oracles we assumed can be instantiated. This is because classical programs with source code can in principle be written as a Boolean circuit whose output follows the distribution p(·|s, a), and it is known that any classical circuit with N logic gates can be converted to a quantum circuit consisting of O(N) logic gates that can compute on any quantum superposition of inputs (see for instance Section 1.5.1 of [1]). For instance, Atari games can be played with our quantum oracles when quantum computers become universal and have enough number of qubits to execute the programs. On the other hand, we also need to point out that the quantum oracle assumption does not apply to every MDP. For instance, we cannot instantiate a quantum oracle for the position of robot arms because robot arms can only exist in the classical world, and their positions cannot be queried in superposition. This is further clarified in the revised version of the paper (see the blue lines between Eq. (3.3) and (3.4)).

We would also like to mention that our assumptions about quantum oracles (i.e, transition oracle, reward oracle, and policy oracle) are standard in the literature of quantum RL and quantum computing. For instance, Ref. [2] assumes access to oracle $O\_x:|0\rangle \rightarrow \sum\_{\omega \in \Omega_x} \sqrt{P\_x(\omega)}|\omega\rangle|y^x(\omega)\rangle$ in equation (5), where $y^x:\Omega \rightarrow \mathbb{R}$ is the random reward associated with arm $x$ of multi-armed bandit. This is similar to our transition oracle $\bar{P}\_h$. In the multi-armed bandit problems, the reward of pulling arm $x$ is $y^x(\omega)$ with probability $P_x(\omega)$. Similarly, in the MDP problems, the agent is transferred to $s_{h+1}$ from $s_h$ by doing action $a_h$ with probability $P\_h(s_{h+1}|s_h,a_h)$, and we encode this transition as a probability oracle $\bar{P}\_h:|s_h,a_h\rangle|0\rangle\rightarrow|s_h,a_h\rangle\otimes\sum_{s_{h+1}}\sqrt{P_h(s_{h+1}|s_h,a_h)}|s_{h+1}\rangle$. Ref. [3] discusses quantum-accessible environments in section 2.3 and it defines transition oracle (8), reward oracle (9), and quantum evaluation of a policy (10) in definition 2.5 and 2.6. These definitions are completely the same as ours. Besides, Ref. [4] defines a quantum generative model of an MDP in definition 3, which is similar and of the same principle as our transition oracle $\bar{P}_h$.

In addition, assuming the inverse of an oracle is natural and standard in quantum computing. Every oracle in quantum computing is a unitary and thus naturally reversible. After implementing a quantum oracle as a quantum circuit (which consists of only a series of basic quantum gates), the inverse can be implemented by directly implementing the inverse of every quantum gate in inverted order. For quantum states, we only assume access to initial state $|0\rangle^{\otimes n}$ and prepare other quantum states by basic quantum gates and our assumed oracles.

Q2: The doubling trick to design lazy-updating algorithms with quantum estimators is already used in existing work (e.g., Wan et al., 2022), so saying this is a novel technique proposed in the paper is an overclaim (Last paragraph on Page 2). However, I agree adapting this idea to MDPs is not that straightforward.

A2: We acknowledge that the algorithmic design of lazy-updating (e.g., the doubling trick) has been explored in the literature of classical online RL, and we have discussed these in our paper. We also appreciate that the reviewer agrees that adapting this idea to MDPs is not that straightforward. In our paper, we have detailed the distinctions between quantum bandits and quantum RL in Appendix B.2. For the reviewer's convenience, we provide the details below.

A2 (continued):

• One can regard the bandits as the MDPs satisfying (i) the state space only contains a single dummy state $s_{\mathrm{dummy}}$; (ii) $H=1$; and (iii) the reward only depends on the action chosen by the learner, i.e., $r(s_{\mathrm{dummy}}, a) = r(a)$. In this case, the learner can repeatedly pull a particular arm $a$ to collect sufficient samples to estimate $r(s_{\mathrm{dummy}}, a)$. However, in online RL, the state will transit according to the transition kernel, preventing repeated arm pulls for the desired estimator. To address this, we introduce a novel adaptive lazy-updating rule, quantifying the uncertainty of the visiting state-action pair (covariance matrix in linear setting) and updating the model infrequently through the doubling trick. This algorithm design, absent in previous work on quantum RL with a generative model [4], connects online exploration in quantum RL with strategic lazy updating mechanisms, inspiring subsequent algorithm design in online quantum RL.

Since the algorithmic design of the doubling trick is ubiquitous, the term 'novel' in our context denotes a nontrivial adaptation of such designs to our model, specifically tailored for quantum-accessible tabular MDPs and linear mixture MDPs. In response to the reviewer's concern, we have revised our paper to highlight that the primary contribution in this aspect lies in establishing a connection between online exploration in quantum RL and strategic lazy updating mechanisms

Regarding technical novelty, we want to bring our linear mixture MDP part to the reviewer's attention. In the linear setting, the algorithm requires a novel design to leverage the advantage of quantum mean estimation. Classical linear RL analysis heavily relies on martingale concentration, such as the well-known self-normalized concentration bound for vectors. However, in quantum RL, there is no direct counterpart to martingale analysis. Consequently, we redesign the lazy updating frequency and propose an entirely new technique to estimate features for building the confidence set for the model. Notably, previous works on quantum bandits [2] do not need to take this step since there is no unknown transition kernel in their setting. Moreover, estimating the features poses a subtle technical challenge, as elaborated in Equation (5.5). Our proposed algorithm (Algorithm 2), which features binary search and quantum mean estimation, successfully addresses this technical challenge. Meanwhile, the quantum samples used in feature estimation approximately equal the number of quantum samples in each phase, eliminating extra regret for this additional feature estimation. This algorithm design (Algorithm 2) and theoretical analysis are entirely new in the literature on (classical and quantum) RL theory. Please refer to the introduction section, Remark 5.1, the proof sketch of Theorem 5.2, and Appendix B.2 for more details, as highlighted in blue.

Q3: Since the learner does not observe the next state, it is unclear how the number of quantum samples ($n_h(s,a)$) is tracked by the learner. It is important as tracking $n_h(s,a)$ is needed to update the estimate of the transition kernel.

A3: This is a great question. First, we would like to clarify that tracking the number of quantum samples $n_h(s, a)$ does not require the agent to know the next state, whether it is a classical state or a quantum state. Tracking $n_h(s, a)$ only requires knowing the classical state $(s, a)$ at step $h$, which is achieved by Algorithm 3 (CSQA) in Appendix C. This algorithm returns a classical state $(s, a)$ at step $h$ according to the given roll-out policy. When we use $(s, a)$ to query the transition oracle at step $h$, it is equivalent to apply $\bar{\mathcal{P}}_h$ on the input state $\ket{s, a} \ket{0}$, since $\ket{s, a}$ denotes the quantum representation of $(s, a)$ in the Hilbert space of quantum superpositions. A quantum sample is returned after the query, so we can increase the counter $n_h(s, a)$ by 1 since we gain a new independent quantum sample $\bar{\mathcal{P}}_h$ or its inverse queried on $\ket{s, a} \ket{0}$. We appreciate your valuable question, and to address this, we have incorporated a discussion in Remark C.4 in our revised manuscript, as highlighted in blue.

Q4: Page 6, paragraph before 'Lazy updating via doubling trick': Is there any connection between phase length (H) and episode horizon (H)?

A4: Yes, the phase length should be equal to the episode horizon. This is because Algorithm 3 (CSQA) only returns one classical sample at a given step $h$ according to a given roll-out policy in an episode, which means only one quantum sample is obtained in a single episode. Therefore, we need at least $H$ episodes in a phase to obtain a quantum sample of the roll-in policy at each step $h \in [H]$, so the model estimation can be updated with these quantum samples according to the lazy-updating scheme.