Parametrized Quantum Policies for Reinforcement Learning
Authors: Sofiene Jerbi
Casper Gyurik
Simon Callum Marshall
Hans J Briegel
Vedran Dunjko
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
quantum computing
parametrized quantum circuits
quantum neural networks
policy gradient
quantum machine learning
quantum reinforcement learning
quantum
variational quantum circuits

Abstract: With the advent of real-world quantum computing, the idea that parametrized quantum computations can be used as hypothesis families in a quantum-classical machine learning system is gaining increasing traction. Such hybrid systems have already shown the potential to tackle real-world tasks in supervised and generative learning, and recent works have established their provable advantages in special artificial tasks. Yet, in the case of reinforcement learning, which is arguably most challenging and where learning boosts would be extremely valuable, no proposal has been successful in solving even standard benchmarking tasks, nor in showing a theoretical learning advantage over classical algorithms. In this work, we achieve both. We propose a hybrid quantum-classical reinforcement learning model using very few qubits, which we show can be effectively trained to solve several standard benchmarking environments. Moreover, we demonstrate, and formally prove, the ability of parametrized quantum circuits to solve certain learning tasks that are intractable to classical models, including current state-of-art deep neural networks, under the widely-believed classical hardness of the discrete logarithm problem.

Parametrized Quantum Policies for Reinforcement Learning
Sofiene Jerbi
Casper Gyurik LIACS, Leiden University
Simon C. Marshall LIACS, Leiden University
Institute for Theoretical Physics, University of Innsbruck sof ac.
Hans J. Briegel
Vedran Dunjko LIACS, Leiden University
Institute for Theoretical Physics, University of Innsbruck
Abstract
With the advent of real-world quantum computing, the idea that parametrized quantum computations can be used as hypothesis families in a auantum-classical machine learning system is gaining increasing traction. Such hybrid systems have already shown the potential to tackle real-world tasks in supervised and generative learning, and recent works have established their provable advantages in special artificial tasks. Yet, in the case of reinforcement learning. which arguably most challenging and where learning boosts would be extremely valuable, no proposal has been successful in solving even standard benchmarking tasks, nor in showing a theoretical learning advantage over classical algorithms. In this work, we achieve both. We propose a hybrid quantum-classical reinforcement learning model using very few qubits, which show be effectively trained to solve several standard benchmarking environments. Moreover, we demonstrate, and formally prove, the ability of parametrized quantum circuits to solve certain learning tasks that are intractable to classical models, including current state-of-art deep neural networks, under the videly-believed classical hardness of the discrete logarithm problem.
Introduction
Hybrid quantum machine learning models constitute of the most promising applications of near-term quantum computers [1, 2]. In these models, parametrized and data-dependent quantum computations define hypothesis family for given learning task, and classical optimization algorithm used to train them. For instance, parametrized quantum circuits (PQCs) [3] have already proven successful in classification [4-8]. generative modeling [9, 10] and clustering [11] problems. Moreover, recent results have shown proofs of their learning advantages in artificially constructed tasks [6. 12], some of which are based widely believed cumplexity-thhoreee assumptions [12-15]. All these results, however, only consider supervised and generative learning settings.
Arguably, the largest impact quantum computing can have is by providing enhancements to the hardest learning problems. From this perspective, reinforcement learning (RL) stands out as a field that can greatly benefit from powerful hypothesis family. This is showcased by the boost in learning performance that deep neural networks (DNNs) have provided to RL [16], which enabled systems like AlphaGo [17], among other achievements [18, 19). Nonetheless, the true potential of near-term quantum approaches in RL remains very little explored. The few existing works [20-23] have failed so far solving classical benchmarking tasks using PQCs and left open the question of their ability to provide a learning advantage.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Hybrid RL agent
State
Task environment
QPU
0
0
5,
Action a
TT (als)
10)
Update parameters
(0]
(0 (0
V log
CPU
Policy gradient algorithm
1010 1010
1010
egg., REINFORCE (see Alg. 1) 1010 1010
Reward Environment dynamics c.g. an MDP
Figure 1: Training parametrized quantum policies for reinforcement learning. We consider drantum-enhaneee RL scenario where hybrid crantum-classical agent learns by interacting with classical environment. For each state it perceives, the agent samples its next action a from its policy To(a)s) and perceives feedback on its behavior in the form of a reward r. For our hybrid agents, the policy Tg is specified by a PQC (see Def. 1) evaluated (along with the gradient Vo log )&) on quantum processing unit (QPU). The training of this policy is performed by a classical learning algorithm, such as the REINFORCE algorithm (see Alg. 1), which uses sample interactions and policy gradients to update the policy parameters 0.
Contributions this work, we demonstrate the potential of policies based on PQCs solving classical RL enviromments. To do this, first propose new model constructions, describe their learn- ing algorithms, and show numerically the influence of design choices on their learning performance. In our numerical investigation, we consider benchmarking environments from OpenAI Gym [24], for which good and simple DNN policies are known, and in which we demonstrate that PQC policies can achieve comparable performance. Second, inspired by the classification task of Havlíček et al. [6], conjectured to be classically hard by the authors, we construct analogous RL environments where show an empirical learning advantage of our PQC policies standard DNN policies used in deep RL. In the same direction, we construct RL environments with a provable gap in performance between family of PQC policies and any efficient classical learner. These environments essentially build upon the work of Liu el al. [14] by embedding into a learning setting the discrete logarithm problem (DLP), which is the problem solved by Shor's celebrated quantum algorithm [25] but widely believed to be classically hard to solve [26].
Related work Recently, a few works have been exploring hybrid quantum approaches for RL. Among these, Refs. [20, 21] also trained PQC-based agents in classical RL environments. However, these take a value-based approach to RL, meaning that they use PQCs as value-function approximators instead of direct policies. The learning agents in these works are also tested on OpenAl Gym environments (namely, a modified FrozenLake and CartPole), but do not achieve sufficiently good performance to be solving them, according to the Gym specifications. Ref. [27] shows that, using some of our design choices for PQCs in RL (i.c., data re-uploading circuits [28] with trainable observable weights and input scaling parameters), one also solve these environments using value-based approach. An actor-critic approach to QRL was introduced in Ref. [22], using both a PQC actor (or policy) and PQC critic (or value- value-function approximator). In contrast to work, these environments), that provide quantum state the agent, which acts back with a continuous classical action. These aspects make it very different learning setting to ours. Ref. [23] also describes a hybrid quantum-classical algorithm for value-based RL. The function-approximation models which this algorithm is applied are however not PQCs but energy-based neural networks (c.g., deep and quantum Boltzmann machines). Finally, our work provides an alternative approach take advantage of quantum effects in designing QRL agents compared to earlier approaches [29-33], which are mainly based on (variations of) Grover's s search algorithm [34] or quantum annealers [35] to speed up sampling routines.
are trained in quantum environments (e.g., quantum
Code An accompanying tutorial [36], implemented as part of the quantum machine learning library TensorFlow Quantum [37], provides the code required to reproduce our numerical results and explore different settings. It also implements the Q-learning approach for PQC-based RL of Skolik et al. [27]

---

Uva (80))
enn (8, 20)
(0)
H
R² ((0,0)
2))
Ry(Ao,
R2 (20,888)))
Uva((
[0)
H
Ry( 1
R (20,881)
Figure 2: PQC architecture for n = 2 qubits and depth Denc = 1. This architecture is composed of alternating layers of encoding unitaries (s, A,) taking input a state vector (so, (so.-..> -.-0----.. $2-1) and scaling parameters X; (part of vector À RIAl of dimension [A]), and variational unitaries (+i) taking input rotation angles Φi (part of vector Φ E [0, 20,22x] | of dimension (g)).
Parametrized quantum policies: definitions and learning algorithm
In this section, give detailed construction of our parametrized quantum policies and describe their associated training algorithms. We start however with a short introduction to the basic concepts of quantum computation, introduced in more detail in [38, 39].
2.1 Quantum computation: a primer
quantum system composed n qubits is represented by a 2n j1-dimensional complex Hilbert space H = =(*2)a* ga Its quantum state is described by vector (15) E H of unit norm (vb ()) 1, where we
adopt the bra-ket notation to describe vectors |v²), their conjugate transpose (1) and inner-products
(wl)") in H. Single-qubit computational basis states given by [0] = (1, 0) [1] (0. 1) and their tensor products describe general computational basis states, c.g. [10) = (1) @ 0) = (0, 0, 0).
A quantum gate is a unitary operation U acting on H. When gate U acts non-trin non-trivially only on subset 5 S [n]] of qubits, we identify interested in the single-qubit Pauli gates Z, Y and their associated rotations Rz, Ry:
the operation U @ [n]ys- In this work, we are mainly
z -)) (o) exp (-i9
0 -
0 (-2Z):
Y = 0
(-1er) (- (I)
Ry R2( exp
for rotation angles R, and the 2-qubit Ctrl-Z gate = diag 1,,,,,
A projective measurement is described by a Hermitian operator O called an observable. Its spectral decomposition = Σn Om Pm in terms of eigenvalues O. and orthogonal projections Pm defines the outcomes of this measurement, according to the Born rule: a measured state (μ) gives the outcome am and gets projected onto the state Pm (v) / /P((m) with probability p(m) (1b Pm (t) = (Pm)) * The expectation value of the observable O with respect (5) is [0 - p(m)am (0),
2.2 The RAW-PQC and SOFTMAX- PQC policies
At the core of our parametrized quantum policies is a PQC defined by unitary (s, 0) that acts on a fixed n--uuii state (c.g.. (0 This unitary encodes an input state E Rd and is parametrized by a trainable vector 0. Although different choices of PQCs are possible, throughout our numerical experiments (Sec. 3 and 4.2), we consider so-called hardware-cfficien PQCs [40] with an alternating- layered architecture [28, 41]. This architecture is depicted in Fig. and essentially consists in an alternation of Dene encoding unitaries Uene (composed of single-qubit rotations R,,, Ry, and Dene + variational unitaries Uvar (composed of single-qubit rotations R,, R. and entangling Ctrl-Z gates I).
For any given PQC, we define two families of policies, differing in how the final quantum states lv>s.o) = (ss, 0) (0@m) are used. In the RAw-PQC model, we exploit the probabilistic nature of quantum measurements to define an RL policy. For |A| available actions to the RL. agent, we partition H. in A| disjoint subspaces (e.g., spanned by computational basis states) and associate a projection P. to each of these subspaces. The projective measurement associated to the observable O Σ, aP. then defines our RAW-PQC policy (a(a))) = (Pa) A limitation of this policy family however is that it does not have directly adjustable greediness (i.e., control parameter that makes the policy more peaked). This consideration arises naturally in an RI. context where an agent's 's policy needs to shift from exploratory behavior (i.c., close to uniform distribution) to more exploitative
3

---

behavior (i.e., peaked distribution). To remedy this limitation, we define the SOFTMAX- NOFTMAX-PQC model, that applies an adjustable softmax,; non-linear activation function on the expectation values (Pa),.o measured on (v,.,)). Since the softmax function normalizes any real-valued input, we can generalize the projections Pa to be arbitrary Hermitian operators O.. We also generalize these observables one step further by assigning them trainable weights. The two models are formally defined below.
Definition 1 (RAW- and SOFTMAX-PQC). Given a PQC acting on qubits, taking as input state E Rd, rotation angles & E [0, 2T] 2-](o) and scaling parameters X E RR IR) such that its corresponding unitary (s, Φ, X) produces the quantum state (..b). = (s, Φ, X) (0 define its associated RAW-PQC policy as:
To (a(a (Pa)
where (Pa) s.0 P (.A) is the expectation value of projection Pa associated to action such that Eo Pa and Pa 80,a' 0 = (Φ. constitute all of its trainable parameters. Using the same PQC, we also define a SOFTMAX- PQC policy as:
3(00),,0
Ta(a|s) Ense (l(O))..
(3)
where (Oz) (1s,b.xlE, Wa Ha, ...) is the expectation value of the weighted Hermitian operators Ha, associated to action a, 3 E R is an inverse-temperaturee parameter and = (Φ) X, w).
Note that we adopt here a very general definition for the observables Og of our COFC policies. As we discuss in more detail in Appendix C, very expressive trainable observables can in some extreme cases take over all training of the PQC parameters Φ X and render the role of the PQC learning trivial. However, in practice, as well as in our numerical experiments, we only consider very restricted observables O₂ >; Wo, Wa,HH., where Ha,; are (tensor products of) Pauli matrices or high-rank projections on computational basis states, which do not allow for these extreme scenarios.
In our PQC construction, we include trainable scaling parameters X, used in every encoding gate to re-scale its input components. This modification the standard data encoding in PQCs comes in light of recent considerations on the structure of PQC functions [42]. These additional parameters allow to represent functions with a wider and richer spectrum of frequencies, and hence provide shallow PQCs with more expressive power.
2.3 Learning algorithm
In order to analyze the properties of our PQC policies without the interference of other learning mechanisms [43], we train these policies using the basic Monte Carlo policy gradient algorithm REINFORCE [44, 45] (see Alg. 1). This algorithm consists in evaluating Monte Carlo estimates of
the value function VTo
E.o Σn''' >'r.)- [0, 1], using batches of interactions with the
enviromment, and updating the policy parameters 0 via a gradient ascent on V (su). The resulting
updates (see line 8 of Alg. involve the gradient of the log-policy Vo log mo (als), which therefore need to compute for our policies. We describe this computation in the following lemma.
Lemma 1. Given SOFTMAX-POC policy no, the gradient of its logarithm is given by:
Vo (a)ss = (Vo (On) E..=o(a'ss) (oo(dlssVVo (Oa')s.0).
(4)
Partial derivatives with respect to observable weights are trivially given by (Oa)
(W o. Ha (e.. (see Def. 1), while derivatives with respect to rotation angles 0g. (Oa)
and scaling parameters' 0x, (Oa)s, can be estimated via the parameter-shift rule [46, 42]:
1
o (Oa)
(Oa),,0-zez)
(5)
2
i.e. using the difference of two expectation values (Ou)..or with a single angle shifted by =
For a RAW-PQC policy ne. we have instead:
Volog (o(a)) Vo (Pa) (Pa)..0
where the partial derivatives 0o, (Pa)..o and 0x, (Pa) can be estimated similarly to above.
Note that the parameters do not act as rotation angles. To compute the derivatives 2x., a0.)).0. one should compute derivatives w.r.t. sj A instead and apply the chain rule: (O,,, = -5,0,,h. (Oa)s.0.

---

Algorithm 1: REINFORCE with PQC policies and value-function baselines
Input: a PQC policy To from Def. value-function approximator V. Initialize parameters and w:
while True do
;10,,,,,,,11111111 Generate N episodes {(00 ao Fly..., -1, 01 ",,,,, following mo: for episode in batch do
Compute the returns G. EV=1 7th et0
5
Compute the gradients Vo log To (1) 10 using Lemma I;
6
Fit (Vo (
(0) ) the returns (
1
Σ Vo log ro ( (o(-)) (Gu Vosss"))
Compute A0
N
Update + aΛ#;
In some of our environments, we additionally rely on a linear value-function baseline to reduce the variance of the Monte Carlo estimates [47]. We choose it to be identical to that of Ref. [48].
2.4 Efficient policy sampling and policy-gradient evaluation
natural consideration when comes the implementation of our PQC policies is whether one can efficiently (in the number of executions of the PQC on a quantum computer) sample and train them.
By design, sampling from our RAW-PQC policies surement) of the PQC: the projective measurement corresponding to the observable O >. aP, naturally samples basis state associated to action with probability (Pa)..o- However, Eq. (6) indicates, in order train these policies using REINFORCE, one is nonetheless required to estimate the expectation values (Pa)..o s.0 along with the gradients Vo (Pa) Fortunately, these quantities can be estimated efficiently up to some additive error using only O(s repeated executions and measurements on quantum computer.
be done with single execution (and mea-
In the case of our SOFTMAX-PQC policies, it less clear whether similar noisy estimates (Ö.) s.9 of the expectation values (Oa),, se are sufficient to evaluate policies of the form of Eq. (3). We show however that, using these noisy estimates, that of the true policy Te. We state our result formally the following lemma, proven in Appendix B.
compute policy 7ee that produces samples close to
Lemma For a SOFTMAX-PQC policy no defined by unitary U(s, O) and observables Oa. call (On)s.o approximations of the true expectation values (Oa) with at most e additive error. Then the approximate policy = = softmax, ş( (Oa)),.) has total variation distance ((3)) to m = softmax s( (.)), Since expectation values can be efficiently estimated additive error on quantum computer, this implies efficient approximate sampling from no-
We also obtain a similar result for the log-policy gradient of SOFTMAX-POE PQCCs (see Lemma 1), that show be efficiently estimated to additive error in -nom (see Appendix for proof).
3 Performance comparison in benchmarking environments
In the previous section, we have introduced our quantum policies and described several of our design choices. We defined the RAW-PQC and SOFTMAX-POS models and introduced two original features for PQCs: trainable observables at their output and trainable scaling parameters for their input. In this section, we evaluate the influence of these design choices on learning performance through numerical simulations. We consider three classical benchmarking environments from the OpenAl Gym library [24]: CartPole, MountainCar and Acrobot. All three have continuous state spaces and discrete action spaces (see Appendix D for their specifications). Moreover, simple NN-policies, well simple closed-form policies, are known to perform very well in these environments [49], which makes them an excellent test-bed to benchmark PQC policies.
5

---

Average collected rewards
5cu
CartPole-vI (n Des.
MountainCar-v0 Denc
400
Acrobot-vl Denc
400-
-150
200
300-
-000
250
-120
300
-140
3150
100-
softmax- PQC
softmax-- PQC
softmax- PQC raw-PQC
raw-PQC
raw-PQC
0
-180
1000
1250 1750
2000
1000
1250 1750 2000
Episode
Episode
Episode
Figure 3: Numerical evidence of the advantage of SOFTMAX- over RAW-PQC in bench- marking environments. The learning curves (20 agents per curve) of randomly-initiaiized SOFTMAX- PQC agents (green curves) and RAW-PQC agents (red curves) in OpenAl Gym environments: CartPole-vl, MountainCar-vO, and Acrobot-vl. Each curve is temporally averaged with a time window of 10 episodes. All agents have been trained using the REINFORCE algorithm (see Alg. 1), with value-function baselines for the MountainCar and Acrobot environments.
CartPole softmax-POO
MountainCar softmax-POC
Acrobot softmax-PQC
Averuge collected rewarts
s00
401
-100
-150
-00
200
-20
200
350
Depth
100
Reference
(deptth
-00
(depth 2)
Fixed lambdis
Fixed lambili
Fised lambidaa
Ficed weights, =5 2,10
Fixed weights, /1 2, 2010
Fixed weights, ( 10
1350
1200 1350
Episode
Episode
Episode
Figure 4: Influence of the model architecture for SOFTMAX-PQC agents. The blue curves in each plot correspond to the learning curves from Fig. and are taken as a reference. Other curves highlight the influence of individual hyperparameters. For RAW-PQC agents, see Appendix E.
3.1 RAW-PQC v.s. SOFTMAX-PQC
In our first set of experiments, presented Fig. 3, we evaluate the general performance of our proposed policies. The aim of these experiments is twofold: first, to showcase that quantum policies based on shallow PQCs and acting on very few qubits can be trained to good performance in our selected environments; second, test the advantage of SOFTMAX-PQC policies over RAW-PQC policies that we conjectured in the Sec. 2.2. To assess these claims, we take similar approach for each of our benchmarking environments, which we evaluate the average learning performance of 20 RAW-PQC and 20 SOFTMAX-PQC agents. Apart from the PQC depth, the shared hyperparameters of these two models were jointly picked as to give the best overall performance for both; the hyperparameters specific to each model were optimized independently. As for the PQC depth Dene. the latter was chosen as the minimum depth for which near-optimal performance was observed for either model. The simulation results confirm both our hypotheses: quantum policies can achieve good performance on the three benchmarking tasks that we consider, and we can see a clear separation between the performance of SOFTMAX-POR PCC and RAW-PQC agents.
3.2 Influence of architectural choices
The results of the previous subsection however do not indicate whether other design choices we have made Sec. 2.2 had an influence on the performance of our quantum agents. To address this, we run second set of experiments, presented in Fig. 4. In these simulations, we evaluate the average performance of our SOFTMAX-POE agents after modifying one of three design choices: we either increment the depth of the PQC (until no significant increase in performance is observed), fix the input-sealing parameters to 1, or fix the observable weights w 1. By comparing the performance of these agents with that of the agents from Fig. 3, we make the following observations:

---

Influence of depth: Increasing the depth of the PQC generally improves (not strictly) the perfor- mance of the agents. Note that the maximum depth we tested was Denc 10.
Influence of scaling parameters A: We observe that training these scaling parameters in general benefits the learning performance of our PQC policies, likely due to their increased expressivity.
Influence of trainable observable weights wt our final consideration relates to the importance of having a policy with "trainable greediness" in RL scenarios. For this, we consider SOFTMAX-PON PPC agents with fixed observables 30,, throughout training. We observe that this has the general effect of decreasing the performance and/or the speed of convergence of the agents. We also see that policies with fixed high 3 (or equivalently, a large observable norm 31 II) learning performance, likely due to their lack of exploration in the RL environments.
tend to have a poor
Finally, note that all the numerical simulations performed here did not include any source of noise in the PQC evaluations. It would be an interesting research direction to assess the influence of (simulated or hardware- (nnuurer--ndeed) noise on the learning performance of PQC agents.
Quantum advantage of PQC agents in RL environments
The proof-of-concepp oo-ccte experiments of the previous section show that our PQC agents can learn in basic classical environments, where they achieve comparable performance to standard DNN policies. This observation naturally raises the question of whether there exist RL environments where PQC policies can provide a learning advantage over standard classical policies. In this section, we answer this question in the affirmative by constructing: a) environments with provable separation in learning performance between quantum and any classical (polynomial-time, learners, and b) environments where our PQC policies of Sec. 2 show empirical learning advantage over standard DNN policies.
4.1 Quantum advantage of PQC policies over any classical learner
In this subsection, we construct RL environments with theoretical guarantees of separation between quantum and classical learning agents. These constructions are predominantly based on the recent work of Liu et al. [14], which defines a classification task out of the discrete logarithm problem (DLP), i.e. the problem solved in the seminal work of Shor [25]. In broad strokes, this task can be viewed as an encryption of an easy-to-learn problem. For an "un-encrypted" version, one defines labeling fa of integers between and p- 2 (for large prime p), where the integers are labeled positively if and only if they lie in the segment [s, 8 + (p- 3)/2] (mod p 1). Since this labeling is linearly separable, the concept class {f.}, is then easy to learn. To make it hard, the input integers (now between and 1) are first encrypted using modular exponentiation, i.e., the secure operation performed in the Dielic-Hellman key exchange protocol. In the encrypted problem, the logarithm of the input integer log, (x) (for generator g of Z see Appendix F) hence determines the label of x. Without the ability decrypt by solving DLP, which is widely believed be classically intractable, the numbers appear randomly labeled. Moreover, Liu et al. show that achieving non con-tiivial labeling accuracy 1/2+ + 1/poly(n) (for n log(p). i.e., slightly better than random guessing) with a classical polynomial-ting time algorithm using (nly(n) examples would lead to an efficient classical algorithm that solves DI.P [14]. In contrast, the same authors construct a family of quantum learners based on Shor's algorithm, that can achieve a labeling accuracy larger than 0.99 with high probability.
SL-DLP Our objective is to show that analogous separations between classical and quantum learners can be established for RL enviromments, in terms of their attainable value functions. We start by pointing out that supervised learning (SL) tasks (and so the classification problem of Liu et al.) can be trivially embedded into RI. environments [50]: for given concept Sa. the states are datapoints, an action an agent's 's guess on the label of xr an immediate reward specifies
was correct. (i.e., fx( a), and subsequent states are chosen uniformly at random. In such settings, the value function is trivially related to the testing accuracy of the SL problem, yielding a direct reduction of the separation result of Liu et al. [14] to an RL setting. We call this family of environments SL-DLP.
Cliffwalk-Di - In the SL-DLP construction, we made the environment fully random in order to simulate the process of obtaining i.i.d. samples in an SL. setting. It is an interesting question whether similar results can be obtained for environments that are less random, and endowed with temporal structure, which is characteristic of RL. In our second family of environments (Cliffwalk-DLP),
7

---

we supplement the SL-DLP construction with next-state transitions inspired by the textbook "cliff walking" environment of Sutton & Barto [44]: all states are ordered in a chain and some actions of the agent can lead to immediate episode termination. We keep however stochasticity in the environment by allowing next states to be uniformly sampled, with a certain probability 6 (common in RI. to ensure that an agent is not simply memorizing a correct sequence of actions). This allows us to show that, as long as sufficient randomness is provided, we still have a simple Mlassiall-quatuun separation.
Deterministic-DI.P In the two families constructed above, each environment instance provided the randomness needed for reduction from the SL problem. This brings us to the question of whether separations are also possible for fully deterministic environments, In this case, it is clear that for any given environment, there exists an efficient classical agent which performs perfectly over any polynomial horizon (a lookup-table will do). However, we show in our third family of environments (Deterministic-DLe DLP) that separation can still be attained by moving the randomness to the choice of the environment itself: assuming an efficient classical agent is successful in most of appnentially-mmm randomly generated (but otherwise deterministic) environments, implies the existence of classical efficient algorithm for DLP.
We summarize our results in the following theorem, detailed and proven in Appendices G through I.
Theorem 1. There exist families of reinforcement learning environments which are: i) fully random (i.e,, subsequent states are independent from the previous state and action); ii) partially random (i.e., the previous moves determine subsequent states, except with a probability at least 0.86 where they are chosen uniformly at random), and iii fully deterministie; such that there exists a separation in the value functions achievable by a given quantum polynomial-time agent and any classical polynomial-ting
agent. Specifically, the value of the initial state for the quanium agent Vg is e clooee to the optimal value function (for a chosen e, and with probubility above 2/3). Further, if there exists a classical efficient learning agent that achieves value Vo(sa) better than Vinaa (8o) + e' (for a chosen E', and with probability above 0.845), then there exists a classical efficient algorithm to solve DLP. Finally, we have Vg(5o) Vo(so) larger than some constant, which depends on the details of the environment.
The remaining point we need to address here is that the learning agents of Liu et al. do not rely on PQCs but rather support vector machines (SVMs) based on quantum kernels [6. 7J. Nonetheless, using a connection between these quantum SVMs and PQCs [7]. we construct PQC policies which powerful in solving the DLP environments the agents of Liu et al. (even under similar noise considerations). We state our result in the following informal theorem, that we re-state formally, along with the details of our construction in Appendices J and K.
Theorem 2 (informal version). Using a training set of size polynomial in n log(p) and a number of (noisy) quantum circuit evaluations also polynomial in n, we can train PQC classifier on the DLP task of Liu al. size n that achieves a testing accuracy arbitrarily close to optimal, with high probability. This PQC classifier can in turn be used to construct close-to-ope close-to-pptimal quantum agents in our DLP environments, as prescribed by Theorem 1.
4.2 Quantum advantage of PQC policies over DNN policies
While the DLP environments establish a proof of the learning advantage PQC policies can have in theory, these environments remain extremely contrived and artificial. They are based on algebraic properties that agents must explicitly decrypt in order to perform well. Instead, we would like to consider environments that are less tailored to a specific decryption function, which would allow more general agents to learn. To do this, we take inspiration from the work of Havlfčck et al. [6], who, in order to test their PQC classifiers, define learning task generated by similar quantum circuits.
4.2.1 PQC-generated environments
We generate our RL environments out of random RAW-PQCs. To do so, we start by uniformly sampling R RAC that uses the alternating-laye architecture Fig. 2 for n = 2 qubits and depth
Demc 4. We use this RAW-PQC to generate a labeling function f(s) by assigning a label +1 to the datapoints in [0, 2T for which (ZZ).. a.0 Z 0 and a label -1 otherwise. We create a dataset S of
10 datapoints per label by uniformly sampling points in [0, 2T for which (ZZ),. a.0
2 2 0.15.
8

---

(a) POC labeling function
(b) SL-POC
(c) Cliffwalk-POC
2x
Average collected rewartie
20.0
20.0
17.5
15.00
12.5
12.5
10.0-
10.0
5.0
2.5
softmaxx PQC
2.5
softmax-POO
DNN
0.0
DNN
200
400
600
800
1000
200
400
600
800
1000
2x
Episode
Episode
Figure 5: Numerical evidence of the advantage of PQC policies over DNN policies PQC- generated environments. (a) Labeling function and training data used for both RL environments. The data labels (red for +1 label and blue for -1 label) are generated using a RAW-PQC of depth Denc 4 with margin A 0.3 (white areas). The training samples uniformly sampled from the blue and red regions, and arrows indicate the rewarded path of the cliffwall environment. (b) and (c) The learning curves (20 agents per curve) of mandomly-iittilizze SOFTMAX-PQC agents and DNN agents in RL environments where input states are (b) uniformly sampled from the dataset and (c) follow cliffwalk dynamics. Each curve temporally averaged with time window of 10 episodes.
This dataset allows us to define two RL environments, similar to the SL-DLP and Cliffwalk-DLP environments of Sec. 4.1:
SL-PQQ: this degenerate RI. environment encodes classification task in an episodic RL environ- ment: each interaction step 20-step episode, a sample state is uniformly sampled from the dataset S, the agent assigns a label +1 to it and receives a reward f())). +11
Cliffwalk-POC: this environment essentially adds temporal structure to SL-PQC: each episode starts from a fixed state So E S. and if an agent assigns the correct label to state st. S i 19. moves to a fixed state 8:+1 and receives a +1 reward, otherwise the episode is instantly terminated and the agent gets a reward. Reaching 820 also causes termination.
4.2.2 Performance comparison
Having defined our POC-generated environments, we now evaluate the performance of SOFTMAX- PQC and DNN policies in these tasks. The particular models we consider are SOFTMAX-PQCs with PQCs sampled from the same family as that of the RAW-PQCs generating the environments (but with re-initialized parameters 0), and DNNs using Rectified Linear Units (ReLUs) in their hidden layers. In our hyperparameter search, we evaluated the performance of DNNs with a wide range of depths (number of hidden layers between 2 to 10) and widths (number of units per hidden layer between 8 and 64), and kept the architecture with the best average performance (depth 4, width 16).
Despite this hyperparametrization, we find (see Fig. 5, and Fig. 8 in Appendix E for different environment instances) that the performance of DNN policies on these tasks remains limited compared to that of SOFTMAX OOFMMAX-POCs, that learn close-to- glose-to-optimes to-tmimaal policies on both tasks. Moreover, we observe that the separation in performance gets boosted by the cliffwalk temporal structure. This is likely do to the increased complexity of this task, as, in order move farther in the cliffwalk, the policy family should allow learning new labels without "forgetting" the labels of earlier states. these particular case studies, the SOFTMAX-POR policies exhibited sufficient flexibility in this sense, whereas the DNNs we considered did not (see Appendix for visualization of these policies). Note that these results do not reflect the difficulty of our tasks at the sizes we consider (a look-up table would perform optimally) but rather highlight the inefficacy of these DNNs at learning PQC functions.

---

5 Conclusion
In this work, we have investigated the design of quantum RL agents based on PQCs. We proposed several constructions and showed the impact of certain design choices learning performance. In particular, we introduced the SOFTMAX-PQC model, where a softmax policy is computed from expectation values of PQC with both trainable observable weights and input scaling parameters. These added features to standard PQCs used in ML (e.g., as quantum classifiers) enhance both the expressivity and flexibility of PQC policies, which allows them achieve a learning performance on benchmarking environments comparable to that of standard DNNs. We additionally demonstrated the existence of task environments, constructed out of PQCs, that are very natural for PQC agents, but on which DNN agents have a poor performance. To strengthen this result, we constructed several RL environments, each with a different degree of degeneracy (i.e., closeness to a supervised learning task), where we showed rigorous separation between a class of PQC agents and any classical learner, based on the widely- classical hardness of the discrete logarithm problem. We believe that our results constitute strides toward a practical quantum advantage in RL using near-term quantum devices.
6 Broad impact
We expect our work to have overall positive societal impact. Notably, we believe that our approach to QRL could be beneficial in the two following ways:
Modern-day RL is known be very resource-heavs in terms of compute power and energy consumption (see, e.g., the resources needed to train AlphaGo Zero [17)). In other computational problems, e.g., the quantum supremacy problem of Google [51], it was shown that, because of their computational advantages. quantum computers could save many orders of magnitude in energy consumption compared to classical supercomputers [52]. Therefore, a quantum learning advantage as showcased in our work could potentially alleviate the computational demands of RI., making more economically appealing and envirommentally--rienddd
Aside from the game-based based problems that we consider in our work, the areas of application of RL are constantly increasing [53-55]. The learning advantages of QRL could potentially make these existing applications more accessible technologically and economically, but also unlock new applications, e.g., in problems in quantum information [56, 22] or quantum chemistry [57].
At the same time, work may have certain negative consequences. Notably, QRL will inherit many of the problems that are already present in classical RL and ML in general. For instance, is not clear whether the question of interpretability of learning models [58] will be negatively or positively impacted by switching to quantum models. One could argue that the inability to fully access the quantum Hilbert spaces in which quantum computers operate can turn learning models even further into "black-boxes" than existing classical models. Also, similarly to the fact that current state-of-the-an ML/RL requires supercomputers that are not accessible everyone, private and select access to quantum computers could emphasize existing inequalities in developing and using AI.
Acknowledgments and Disclosure of Funding
The authors would like to thank Srinivasan Arunachalam for clarifications on the testing accuracy of their quantum classifier in the DLP classification task. The authors would also like to thank Andrea Skolik and Arjan Cornelissen for helpful discussions and comments. CG thanks Thomas Moerland for discussions in the early phases of this project. SJ and HJB acknowledge support from the Austrian Science Fund (FWF) through the projects DK-ALM W 1259-N27 and SFB BeyondC F7 102. SJ also acknowledges the Austrian Academy of Sciences as recipient of the DOC Fellowship. This work was in part supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium program (project number 024.003.0000 024.003.037). VD and SM acknowledge the support by the project NEASQC funded from the European Union's 's Horizon 2020 research and innovation programme (grant agreement No 951821). VD and SM also acknowledge partial funding by an unrestricted gift from Google Quantum AI. The computational results presented here have been achieved in part using the LEO HPC infrastructure of the University of Innsbruck.
10

---

References
[1] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018.
[2] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug. Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kotimann, Tim Menke, et al. Noisy intermediate- scale quantum (nisq) algorithms. arXiv preprint arXiv:210I. 00040884,, 2021.
[3] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4(4):043001, 2019.
[4] Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv preprint arXiv: (ee.000020000,, 2018.
[5] Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe. Circuit-centric quantum classifiers. Physical Review A, 101(3))033308, 2020.
[6] Vojtech Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 2077777))20--222, 2019.
[7] Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces.
Physical review letters, 122(4):040004, 2019.
[8] Evan Peters, Joao Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni, Hartmut Neven, Panagiotis Spentzouris, Doug Strain, and Gabriel N Perdue. Machine learning of high dimen- sional data on a noisy quantum processor. arXiv preprint 0rXiv:2101.0958/ 2021.
[9] Jin-Guo Liu and Lei Wang. Differentiable learning of quantum circuit born machines. Physical Review A, 98(6):062324, 2018.
[10] Daiwei Zhu, Norbert M Linke, Marcello Benedetti, Kevin Landsman, Nhung Nguyen,
C Huerta Alderete, Alejandro Perdomo-Ortiz Nathan Korda, A Garfoot, Charles Brecque, et al. Training of quantum circuits on hybrid quantum computer. Science advances, 5(10)eaaaw9915 18, 2019.
[11] IS Otterbach, R Manenti, N Alidoust, A Bestwick, M Block, B Bloom, S Caldwell, N Didier, E Schuyler Fried, S Hong, al. Unsupervised machine learning on a hybrid quantum computer. arXiv preprini arXiv: 17.007771, 2017.
[12] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hart- mut Neven, and Jarrod R McClean. Power of data in quantum machine learning. Nature communications, 12(1):1 2021.
[13] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2(3):033 2020.
[14] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 109):1013-101 2021.
[15] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Fisert. On the quantum versus classical learnability of discrete distributions. Quantum, 5:417, 2021.
[16] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 51 518(7540):529-53) 2015.
[17] David Silver, Julian Schritwieserr, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):355) 2017.
[18] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 192.06600,, 2019.
[19] Piotr Mirowski, Matt Grimes, Mateusz Malinowski, Karl Moritz Hermann, Keith Anderson, Denis Teplyashin, Karen Simonyan, Andrew Zisserman, Raia Hadsell, et al. Learning to navigate in cities without a map. Advances in Neural Information Processing Systems, 31: 2419-2430, 2018
[20] Samuel Yen-Chi Chen, Chao-Har Huck Yang. Jun Qi. Pin-Yu Chen, Xiaoli Ma, and Hsi- Sheng Goan. Variational quantum circuits for deep reinforcement learning. IEEE Access, 8: 141007-141024, 2020.
[21] Owen Lockwood and Mei Si. Reinforcement learning with quantum variational circuit. In Pro- ceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 16, pages 241-251, 2020.
[22] Shaojun Wu, Shan Jin, Dingding Wen, and Xiaoting Wang. Quantum reinforcement learning in continuous action space. arXiv preprint 10X1v 2020.
11

---

[23] Sofiene Jerbi, Lea M. Trenkwalder, Hendrik Poulsen Nautrup, Hans J. Briegel, and Vedran Dunjko. Quantum enhancements for deep reinforcement learning in large spaces. PRX Quantum, 2:010328, Feb 2021.
[24] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: /tt.:///00./44500 2016.
[25] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer. SIAM review, 41(2):003-332, 1999.
[26] Manuel Blum and Silvio Micali. How generate cryptographically strong sequences of pseudorandom bits. SIAM journal on Computing, 13(4):850-864, 1984.
[27] Andrea Skolik, Sofiene Jerbi, and Vedran Dunjko. Quantum agents the gym: a variational quantum algorithm for deep q-learning, arXiv preprint arXiv:2103. 15084, 2021.
[28] Adrián Pérez-Salinas, Alba Cervera-Lierta, Elies Gil-Fuster, and José Latorre. Data re- uploading for universal quantum classifier. Quantum, 4:226, 2020.
[29] Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tarn. Quantum reinforcement
IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)), 3865):1207-1220, 2008.
[30]
Giuseppe Davide Paparo, Vedran Dunjko, Adi Makmal, Miguel Angel Martin-Delgade and
Hans Briegel. Quantum speedup for active learning agents. Physical Review X, 4(3):031002. 2014.
[31] Vedran Dunjko, Jacob M Taylor, and Hans J Briegel. Quantum-enhanced machine learning.
Physical review letters, 117(11):130555) 2016.
[32] Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S Oberoi, and Pooya Ronagh. Rein- forcement learning using quantum boltzmann machines. Quantum Information Computation, 18(1-2):51-74, 2018.
[33] Florian Neukart, David Von Dollen, Christian Seidel, and Gabriele Compostella. Quantum- enhanced reinforcement learning for finite-episode games with discrete state spaces. Frontiers in Physics, 5:71, 2018.
[34] Lov Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eigtth annual ACM symposium on Theory of computing. pages 212-219, 1996.
[35] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew Berkley, Jan Johansson, Paul Bunyk, al. Quantum
annealing with manufactured spins. Nature, 473(7346) 2011.
[36]
TensorFlow Quantum. Parametrized quantum circuits for reinforcement learning. reinforcement learning, 2021.
URL: tensorftow.org// http:o//gggguuuuuuuuuuuuuuuuuuue
[37]
Michael Broughton, Guillaume Verdon, Trevor McCourt, Antonio J Martinez, Jae Hyeon Yoo, Sergei V Isakov, Philip Massey, Murphy Yuezhen Niu, Ramin Halavati, Evan Peters, al. Tensorflow quantum: A software framework for quantum machine learning. arXiv preprint arXiv:2003.022 0.299,, 2020.
[38] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information.
Cambridge University Press, 2000.
[39] Ronald De Wolf. Quantum computing: Lecture notes. arXiv preprint vrXiv:1907.094111 09415, 2019.
[40] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-efficiem variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671):242 22222226666222 2017.
[41] Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of variational 032430, 2021.
models. Physical Review A, 103(3):
[42] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating quantum hardware. Physical Review A, 99(3):032331, 2019. [43] Lilian Weng. Policy gradient algorithms. URL: wtwpaawwnnnggttubio//oooooo
analytic gradients
2018.
[44]
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction. 1998.
[45] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce-
ment learning. Machine learning, 8(3-4):229-25 1992.
[46] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit
learning. Physical Review A, 98(3):032309 2018.
[47] Evan Greensmith, Peter I. Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5(Nov): 1471-1530, 2004.
12

---

[48] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning. pages 1329-1322 1338. PMLR, 2016.
[49] OpenAI. Leaderboard of openai gym environments. URL::
2020.
[50] Vedran Dunjko, Yi-Kai Liu, Xingyao Wu, and Jacob M Taylor. Exponential improvements for quantum-accessible reinforcement learning. arXiv preprint arXiv: 1600,, 2017.
[51] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David Buell, et al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):505-5100 2019.
[52] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, and Salvatore Mandrà. Establishing the quantum supremacy frontier with a 281 pftop/s simulation. Quantum Science and Technology, 5(3):034003, 2020. [53] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in roboties: A survey. The International Journal of Robotics Research, 12(11):223811244 2013.
[54] Mufti Mahmud, Mohammed Shamim Kaiser, Amir Hussain, and Stefano Vassanelli. Appli- cations of deep learning and reinforcement learning to biological data. IEEE transactions on neural networks and learning systems, 29(6):2033-2079, 2018.
[55] Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning in healthcare: A survey.
arXiv preprint arXiv: 1900. 087968 2019.
[56] Francisco Albarrán- Albarrán-Arriaaada Juan C Retamal, Enrique Solano, and Lucas Lamata. Measurement- based adaptation protocol with quantum reinforcement learning. Physical Review
A, 98(4):042315, 2018
[57] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung. Xiao-Qi Qi Zhou, Peter Love, Alán Aspuru-Guzii Guzuk, and Jeremy L. O'brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):1-7, 2014.
[58] Pantelis Linardatos, Vasilis Papastefanopoulos, and Sotiris Kotsiantis. Explainable ai: A review of machine learning interpretability methods. Entropy, 23(1):18, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes] See Sec. 4.2, where we mention
that our constructed environments are artificial and comment on the limitations of our comparison to deep neural networks.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In the broad impact section. See Sec. 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Lemma Lemma 2, Lemma 3, Theorem (derived from Lemmas 5, 6) and Theorem (derived from Lemmas and 8).
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices A, B,
G, H, I and K.
3. If you ran experiments...
(a) Did you include the code. data, and instructions needed reproduce the main perimental results (either in the supplemental material or as a URL.) [Yes] See last paragraph of Sec. and the supplementary material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Sec. 3.1, 3.2 and 4.2.2, and Appendix D.
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [Yes] See Fig. 3, 4, 5, and
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix D.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "iOVgeGxBKV-", "reviewer": "Reviewer_e14U", "summary": "## Summary \n\nThe paper proposes a policy-based training framework with variational quantum circuits (VQC). Although the VQC-based deep reinforcement learning algorithm has been first studied in [20] and [23], this paper further addresses a policy-based optimization instead of a value-based method (e.g., DQN) in [20]. \n\nThe introduction and related work parts are good covering most of the important references in the field. \n\nThe paper further discusses two variants of the parameterized quantum circuit (PQC), raw-PQC and softmax-PQC to compared with a DNN-based RL method in three DRL environments from OpenAI gym. \n\n- Noted I am not sure how fair is the selection DNN-based RL method in terms of model capacity according to the current version. \n\nThe authors further discuss some points included of (1) Efficient policy sampling and (2) quantum advantages. \n\nOverall, the paper is well-written and motivated. The major weakness is on the baseline selection and some scalable discussion on quantum advantages. \n\n- baseline selection\n\nThe works in [22] using a continuous quantum Deep RL method, called Quantum DDPG. What is the advantage between the proposed softmax PQC compared with Quantum DDPG?\n\n- scalable discussion\n\nI just notice that the value-based method paper [20] uses a simple tangible radio RL environment to discuss the trade-off between parameter complexity (Figure 11 in [20]) versus different classical and quantum RL methods. \n\nIf the author could provide experimental supports or discussion versus that existing analysis on the QA on parameters, the discussion could be more comprehensive. \n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "## Pros\n\n- The paper provides a policy-based method for quantum deep reinforcement learning.\n\n- The discussion and related works are of good quality. \n\n- The results show the capability of Quantum DRL working on new challenges environment as Mountains Car (initial with negative values) and Acrobot-v1.\n\n## Points to Improve\n\n- The quantum advantage needs some empirical analysis [Ref 1] or learning complexity analysis (PAC theory) to have a full claim. \nPlease refer to the potential scalable discussion in the summary to have parameter complexity improvement. \n\n- The DNN policies in Figure 5 are associated with the same amount of trainable parameters or? This would need more clarification. List or provide a parameter table for each baseline would be a solution. \n\n\n## Addtional Disccusion \n\n- There is less discussion on the full checklist, such as potential energy consumption (CPU-simulated or using QPU batch directly) corresponding to the NeurIPS policy. \n\n- If the proposed method could also benefit from a decentralized framework as the recent studies [Ref 2] in a hybrid classical-quantum A2C policy? \n\n\nOverall, the paper is around the borderline acceptance threshold. \n\nI give my recommendation to borderline acceptance considering its pros, weaknesses, and detailed supplementary report. I would consider modifying my score based on the additional baseline studies and discussion in a revised version.\n\n\n\n\nRef 1. A Grover-search based quantum learning scheme for classification, New Journal of Physics, 2021\n\nRef 2. Decentralizing feature extraction with quantum convolutional neural network for automatic speech recognition, IEEE ICASSP 2021\n\nRef 3. Quantum-enhanced machine learning, Physical review letters 2016", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The checklist is not fully satisfied on 1. (c) Did you discuss any potential negative social impacts of your work? [No]\n\nThe authors may consider adding a board impact section in their revised supplementary. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "T1_yZ1WzDu", "reviewer": "Reviewer_3zS5", "summary": "I thank the authors for their response. I think the empirical results are encouraging and the idea is reasonably novel, so will keep the score as is.\n\n--- \nThe paper discusses a parametrized quantum computations as a policy trained via policy gradient. The policy is parametrized with a quantum computer whereas parameter updates are done by a classical computer. Situations where the quantum policy can have advantage over classical ones are discussed and evaluated. In PQC-generated environments, PQC-policies have a significant advantage over classical ones. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Originality: The approach taken is generally a standard one taken with quantum machine learning -- a quantum circuit is parametrized and optimized via a classical update algorithm. Since gradients of the quantum circuit can be evaluated using e.g. the parameter shift trick, it is not entirely surprising for a policy gradient algorithm to be developed. \n\nThe paper mentioned some recent related work on this front, but it would also be interesting to discuss older related works (https://arxiv.org/abs/0810.3828, https://arxiv.org/abs/1401.4997, https://arxiv.org/abs/1612.05695). One contribution is the introduction of softmax-PQC which clearly outperforms raw-PQC policies.\n\nApplicability: The PQC-constructed environment is largely an MDP-extension of Liu et al., and it does not seem that the action in the PQC-cliffwalk affects the trajectory other than episode termination. The PQC policy is limited to discrete actions and a comparison with classical algorithms is not included.\n\nClarity: the paper is written very well and is about readable as it can get for an audience that knows ML but not quantum computing. \n\nMinor questions and or comments:\n- How does the TensorFlow quantum environment simulate quantum noise (or does it)? I would suppose a larger noise would hinder learning progress even though policy gradient should be able to learn with more episodes.\n- It seems to me that the major advantage of PQC is the ability to learn a map for DLP -- are there other more realistic examples where PQC policies are needed?\n- It seems that the softmax-PQC is not limited to reinforcement learning. Do you expect it to achieve similar improvements in supervised learning?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.\n\nNo negative societal impact is discussed, but I don't think it is necessary for this paper.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "Fb5QnMv9mZG", "reviewer": "Reviewer_fBf5", "summary": "The article titled ‘Parametrized Quantum Policies for Reinforcement Learning’ presents a hybrid quantum-classical learning model, which the author claims that can be effectively trained to solve several standard benchmarking environments. The learning model is based on parametrized quantum circuits (PQC), where the parameters can be adjusted during the training process. By defining RAW- and SOFTMAX-PQC, the author shows the detailed learning methods corresponding each of the cases. The work also displays the result of this two methods, which we can see a moderate learning process is happening. In the end, the author also argues the ability of parametrized quantum circuits to solve certain learning tasks that are intractable to classical models. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The article is written nicely and the it is easy to follow the construction. However, I think there are two major drawbacks in this work. Firstly, in the RAW-PQC design, the policy is output of the quantum circuit. The probabilities of different strings are first evaluated and the an action is sampled from this distribution. This is redundant in my opinion because a quantum circuit is already a good sampler. Even though the author proves it is efficient to sample in this case, one can just use the measurement result each time as the sample of the distribution. So I do not see an obvious reason why the author need to evaluate the probability distribution first and then do the sampling. Secondly, in the SOFTMAX-PQC design, the policy is determined by the weighted mean value in line 112. It seems nice but there is a fatal drawback here. With this design, it may happen that the classical optimizer can optimize the weight \\omega to get whatever probability distribution, even with the quantum circuit always producing the same output at all times. In this sense, the information that the quantum circuit is supposed to convey is absorbed into the classical parameters \\omega.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As for the limitations and societal impact, the author argues that there exist RL environments where PQC policies can provide a learning advantage over standard classical policies. However, it looks like the argument is mostly change of narratives based on previous results and the contribution is rare. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a quantum reinforcement learning regime that utilizes a parameterized quantum circuit. The paper is clearly written. There are a few concerns with the scientific contributions and side points from the reviewers, especially why the PQC plays an essential role in the learning model. However, the authors have replied explicitly the concerns in the discussion and the reviewers and the authors have reached consensus. The authors also explain in detail on possible applications of the work and the questions on the complexity analysis. In short, I would recommend this work to be accepted. 

Decision: Accept (Poster)