Parametrized Quantum Policies for Reinforcement Learning
Year: 2021

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.

heading: 1 Introduction
text: Hybrid quantum machine learning models constitute one of the most promising applications of near-term quantum computers [1, 2]. In these models, parametrized and data-dependent quantum computations define a hypothesis family for a given learning task, and a classical optimization algorithm is 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 on widely believed complexity-theoretic 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 a 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 at 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 (NeurIPS 2021).
Contributions In this work, we demonstrate the potential of policies based on PQCs in solving classical RL environments. To do this, we first propose new model constructions, describe their learning 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íček et al. [6], conjectured to be classically hard by the authors, we construct analogous RL environments where we show an empirical learning advantage of our PQC policies over standard DNN policies used in deep RL. In the same direction, we construct RL environments with a provable gap in performance between a family of PQC policies and any efficient classical learner. These environments essentially build upon the work of Liu et 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 OpenAI 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.e., data re-uploading circuits [28] with trainable observable weights and input scaling parameters), one can also solve these environments using a value-based approach. An actor-critic approach to QRL was introduced in Ref. [22], using both a PQC actor (or policy) and a PQC critic (or value-function approximator). In contrast to our work, these are trained in quantum environments (e.g., quantum-control environments), that provide a quantum state to the agent, which acts back with a continuous classical action. These aspects make it a very different learning setting to ours. Ref. [23] also describes a hybrid quantum-classical algorithm for value-based RL. The function-approximation models on which this algorithm is applied are however not PQCs but energy-based neural networks (e.g., deep and quantum Boltzmann machines). Finally, our work provides an alternative approach to take advantage of quantum effects in designing QRL agents compared to earlier approaches [29–33], which are mainly based on (variations of) Grover’s search algorithm [34] or quantum annealers [35] to speed up sampling routines.
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]

heading: 2 Parametrized quantum policies: definitions and learning algorithm
text: In this section, we give a 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].

heading: 2.1 Quantum computation: a primer
text: A quantum system composed of n qubits is represented by a 2n-dimensional complex Hilbert space H = (C2)⊗n. Its quantum state is described by a vector |ψ⟩ ∈ H of unit norm ⟨ψ|ψ⟩ = 1, where we adopt the bra-ket notation to describe vectors |ψ⟩, their conjugate transpose ⟨ψ| and inner-products ⟨ψ|ψ′⟩ inH. Single-qubit computational basis states are given by |0⟩ = (1, 0)T , |1⟩ = (0, 1)T , and their tensor products describe general computational basis states, e.g., |10⟩ = |1⟩ ⊗ |0⟩ = (0, 0, 1, 0). A quantum gate is a unitary operation U acting on H. When a gate U acts non-trivially only on a subset S ⊆ [n] of qubits, we identify it to the operation U ⊗ 1[n]\S . In this work, we are mainly interested in the single-qubit Pauli gates Z, Y and their associated rotations Rz, Ry:
Z = ( 1 0 0 −1 ) , Rz(θ) = exp ( −iθ 2 Z ) , Y = ( 0 −i i 0 ) , Ry(θ) = exp ( −iθ 2 Y ) , (1)
for rotation angles θ ∈ R, and the 2-qubit Ctrl-Z gate = diag(1, 1, 1,−1). A projective measurement is described by a Hermitian operator O called an observable. Its spectral decomposition O = ∑ m αmPm in terms of eigenvalues αm and orthogonal projections Pm defines the outcomes of this measurement, according to the Born rule: a measured state |ψ⟩ gives the outcome αm and gets projected onto the state Pm |ψ⟩ / √ p(m) with probability p(m) = ⟨ψ|Pm |ψ⟩ = ⟨Pm⟩ψ .
The expectation value of the observable O with respect to |ψ⟩ is Eψ[O] = ∑ m p(m)αm = ⟨O⟩ψ .

heading: 2.2 The RAW-PQC and SOFTMAX-PQC policies
text: At the core of our parametrized quantum policies is a PQC defined by a unitary U(s,θ) that acts on a fixed n-qubit state (e.g., |0⊗n⟩). This unitary encodes an input state s ∈ Rd and is parametrized by a trainable vector θ. Although different choices of PQCs are possible, throughout our numerical experiments (Sec. 3 and 4.2), we consider so-called hardware-efficient PQCs [40] with an alternatinglayered architecture [28, 41]. This architecture is depicted in Fig. 2 and essentially consists in an alternation of Denc encoding unitaries Uenc (composed of single-qubit rotations Rz, Ry) and Denc + 1 variational unitaries Uvar (composed of single-qubit rotations Rz, Ry and entangling Ctrl-Z gates ).
For any given PQC, we define two families of policies, differing in how the final quantum states |ψs,θ⟩ = U(s,θ) |0⊗n⟩ 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 Pa to each of these subspaces. The projective measurement associated to the observable O = ∑ a aPa then defines our RAW-PQC policy πθ(a|s) = ⟨Pa⟩s,θ. A limitation of this policy family however is that it does not have a directly adjustable greediness (i.e., a control parameter that makes the policy more peaked). This consideration arises naturally in an RL context where an agent’s policy needs to shift from an exploratory behavior (i.e., close to uniform distribution) to a more exploitative
behavior (i.e., a peaked distribution). To remedy this limitation, we define the SOFTMAX-PQC model, that applies an adjustable softmaxβ non-linear activation function on the expectation values ⟨Pa⟩s,θ measured on |ψs,θ⟩. Since the softmax function normalizes any real-valued input, we can generalize the projections Pa to be arbitrary Hermitian operators Oa. 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 n qubits, taking as input a state s ∈ Rd, rotation angles ϕ ∈ [0, 2π]|ϕ| and scaling parameters λ ∈ R|λ|, such that its corresponding unitary U(s,ϕ,λ) produces the quantum state |ψs,ϕ,λ⟩ = U(s,ϕ,λ) |0⊗n⟩, we define its associated RAW-PQC policy as: πθ(a|s) = ⟨Pa⟩s,θ (2) where ⟨Pa⟩s,θ = ⟨ψs,ϕ,λ|Pa|ψs,ϕ,λ⟩ is the expectation value of a projection Pa associated to action a, such that ∑ a Pa = I and PaPa′ = δa,a′ . θ = (ϕ,λ) constitute all of its trainable parameters. Using the same PQC, we also define a SOFTMAX-PQC policy as:
πθ(a|s) = eβ⟨Oa⟩s,θ∑ a′ e β⟨Oa′ ⟩s,θ (3)
where ⟨Oa⟩s,θ = ⟨ψs,ϕ,λ| ∑ i wa,iHa,i|ψs,ϕ,λ⟩ is the expectation value of the weighted Hermitian operatorsHa,i associated to action a, β ∈ R is an inverse-temperature parameter and θ = (ϕ,λ,w).
Note that we adopt here a very general definition for the observables Oa of our SOFTMAX-PQC 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 ϕ,λ and render the role of the PQC in learning trivial. However, in practice, as well as in our numerical experiments, we only consider very restricted observables Oa = ∑ i wa,iHa,i, where Ha,i 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 λ, used in every encoding gate to re-scale its input components. This modification to 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.

heading: 2.3 Learning algorithm
text: 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 Vπθ (s0) = Eπθ [∑H−1 t=0 γ trt ] , γ ∈ [0, 1], using batches of interactions with the
environment, and updating the policy parameters θ via a gradient ascent on Vπθ (s0). The resulting updates (see line 8 of Alg. 1) involve the gradient of the log-policy ∇θ log πθ(a|s), which we therefore need to compute for our policies. We describe this computation in the following lemma. Lemma 1. Given a SOFTMAX-PQC policy πθ, the gradient of its logarithm is given by:
∇θ log πθ(a|s) = β ( ∇θ ⟨Oa⟩s,θ − ∑ a′ πθ(a ′|s)∇θ ⟨Oa′⟩s,θ ) . (4)
Partial derivatives with respect to observable weights are trivially given by ∂wa,i⟨Oa⟩s,θ = ⟨ψs,ϕ,λ|Ha,i|ψs,ϕ,λ⟩ (see Def. 1), while derivatives with respect to rotation angles ∂ϕi⟨Oa⟩s,θ and scaling parameters1 ∂λi⟨Oa⟩s,θ can be estimated via the parameter-shift rule [46, 42]:
∂i ⟨Oa⟩s,θ = 1
2
( ⟨Oa⟩s,θ+π2 ei − ⟨Oa⟩s,θ−π2 ei ) , (5)
i.e., using the difference of two expectation values ⟨Oa⟩s,θ′ with a single angle shifted by ± π 2 . For a RAW-PQC policy πθ, we have instead: ∇θ log πθ(a|s) = ∇θ ⟨Pa⟩s,θ / ⟨Pa⟩s,θ (6)
where the partial derivatives ∂ϕi⟨Pa⟩s,θ and ∂λi⟨Pa⟩s,θ can be estimated similarly to above. 1Note that the parameters λ do not act as rotation angles. To compute the derivatives ∂λi,j ⟨Oa⟩s,θ , one should compute derivatives w.r.t. sjλi,j instead and apply the chain rule: ∂λi,j ⟨Oa⟩s,θ = sj∂sjλi,j ⟨Oa⟩s,θ .
Algorithm 1: REINFORCE with PQC policies and value-function baselines
Input: a PQC policy πθ from Def. 1; a value-function approximator Ṽω 1 Initialize parameters θ and ω; 2 while True do 3 Generate N episodes {(s0, a0, r1, . . . , sH−1, aH−1, rH)}i following πθ; 4 for episode i in batch do 5 Compute the returns Gi,t ← ∑H−t t′=1 γ t′r (i) t+t′ ; 6 Compute the gradients∇θ log πθ(a(i)t |s (i) t ) using Lemma 1;
7 Fit { Ṽω(s (i) t ) } i,t to the returns {Gi,t}i,t;
8 Compute ∆θ = 1
N N∑ i=1 H−1∑ t=0 ∇θ log πθ(a(i)t |s (i) t ) ( Gi,t − Ṽω(s(i)t ) ) ;
9 Update θ ← θ + α∆θ;
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].

heading: 2.4 Efficient policy sampling and policy-gradient evaluation
text: A natural consideration when it comes to 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 can be done with a single execution (and measurement) of the PQC: the projective measurement corresponding to the observable O = ∑ a aPa naturally samples a basis state associated to action a with probability ⟨Pa⟩s,θ. However, as Eq. (6) indicates, in order to train these policies using REINFORCE, one is nonetheless required to estimate the expectation values ⟨Pa⟩s,θ, along with the gradients ∇θ ⟨Pa⟩s,θ. Fortunately, these quantities can be estimated efficiently up to some additive error ε, using only O(ε−2) repeated executions and measurements on a quantum computer.
In the case of our SOFTMAX-PQC policies, it is less clear whether similar noisy estimates ⟨Õa⟩s,θ of the expectation values ⟨Oa⟩s,θ are sufficient to evaluate policies of the form of Eq. (3). We show however that, using these noisy estimates, we can compute a policy π̃θ that produces samples close to that of the true policy πθ . We state our result formally in the following lemma, proven in Appendix B. Lemma 2. For a SOFTMAX-PQC policy πθ defined by a unitary U(s,θ) and observables Oa, call ⟨Õa⟩s,θ approximations of the true expectation values ⟨Oa⟩s,θ with at most ε additive error. Then the approximate policy π̃θ = softmaxβ(⟨Õa⟩s,θ) has total variation distance O(βε) to πθ = softmaxβ(⟨Oa⟩s,θ). Since expectation values can be efficiently estimated to additive error on a quantum computer, this implies efficient approximate sampling from πθ.
We also obtain a similar result for the log-policy gradient of SOFTMAX-PQCs (see Lemma 1), that we show can be efficiently estimated to additive error in ℓ∞-norm (see Appendix B for a proof).

heading: 3 Performance comparison in benchmarking environments
text: In the previous section, we have introduced our quantum policies and described several of our design choices. We defined the RAW-PQC and SOFTMAX-PQC 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 OpenAI 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, as well as 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.

heading: 3.1 RAW-PQC v.s. SOFTMAX-PQC
text: In our first set of experiments, presented in 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, to 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 a similar approach for each of our benchmarking environments, in 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 Denc, 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-PQC and RAW-PQC agents.

heading: 3.2 Influence of architectural choices
text: The results of the previous subsection however do not indicate whether other design choices we have made in Sec. 2.2 had an influence on the performance of our quantum agents. To address this, we run a second set of experiments, presented in Fig. 4. In these simulations, we evaluate the average performance of our SOFTMAX-PQC 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-scaling parameters λ to 1, or fix the observable weights w to 1. By comparing the performance of these agents with that of the agents from Fig. 3, we can make the following observations:
• Influence of depth: Increasing the depth of the PQC generally improves (not strictly) the performance of the agents. Note that the maximum depth we tested was Denc = 10.
• Influence of scaling parameters λ: 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 w: our final consideration relates to the importance of having a policy with “trainable greediness” in RL scenarios. For this, we consider SOFTMAX-PQC agents with fixed observables βOa 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 β (or equivalently, a large observable norm β∥Oa∥) tend to have a poor learning performance, likely due to their lack of exploration in the RL environments.
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-induced) noise on the learning performance of PQC agents.

heading: 4 Quantum advantage of PQC agents in RL environments
text: The proof-of-concept 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 a provable separation in learning performance between quantum and any classical (polynomial-time) learners, and b) environments where our PQC policies of Sec. 2 show an empirical learning advantage over standard DNN policies.

heading: 4.1 Quantum advantage of PQC policies over any classical learner
text: 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 a labeling fs of integers between 0 and p − 2 (for a large prime p), where the integers are labeled positively if and only if they lie in the segment [s, s+ (p− 3)/2] (mod p− 1). Since this labeling is linearly separable, the concept class {fs}s is then easy to learn. To make it hard, the input integers x (now between 1 and p− 1) are first encrypted using modular exponentiation, i.e., the secure operation performed in the Diffie–Hellman key exchange protocol. In the encrypted problem, the logarithm of the input integer logg(x) (for a generator g of Z ∗ p, see Appendix F) hence determines the label of x. Without the ability to decrypt by solving DLP, which is widely believed to be classically intractable, the numbers appear randomly labeled. Moreover, Liu et al. show that achieving non-trivial labeling accuracy 1/2+1/poly(n) (for n = log(p), i.e., slightly better than random guessing) with a classical polynomial-time algorithm using poly(n) examples would lead to an efficient classical algorithm that solves DLP [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 environments, 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 RL environments [50]: for a given concept fs, the states x are datapoints, an action a is an agent’s guess on the label of x, an immediate reward specifies if it was correct (i.e., fs(x) = 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-DLP 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),
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 δ (common in RL 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 classical-quantum separation.
Deterministic-DLP In the two families constructed above, each environment instance provided the randomness needed for a 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-DLP) that a 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 exponentially-many randomly generated (but otherwise deterministic) environments, implies the existence of a 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 deterministic; such that there exists a separation in the value functions achievable by a given quantum polynomial-time agent and any classical polynomial-time agent. Specifically, the value of the initial state for the quantum agent Vq(s0) is ε−close to the optimal value function (for a chosen ε, and with probability above 2/3). Further, if there exists a classical efficient learning agent that achieves a value Vc(s0) better than Vrand(s0) + ε′ (for a chosen ε′, and with probability above 0.845), then there exists a classical efficient algorithm to solve DLP. Finally, we have Vq(s0) − Vc(s0) 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, 7]. Nonetheless, using a connection between these quantum SVMs and PQCs [7], we construct PQC policies which are as powerful in solving the DLP environments as 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 a PQC classifier on the DLP task of Liu et al. of 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-optimal quantum agents in our DLP environments, as prescribed by Theorem 1.

heading: 4.2 Quantum advantage of PQC policies over DNN policies
text: 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 Havlíček et al. [6], who, in order to test their PQC classifiers, define a learning task generated by similar quantum circuits.

heading: 4.2.1 PQC-generated environments
text: We generate our RL environments out of random RAW-PQCs. To do so, we start by uniformly sampling a RAW-PQC that uses the alternating-layer architecture of Fig. 2 for n = 2 qubits and depth Denc = 4. We use this RAW-PQC to generate a labeling function f(s) by assigning a label +1 to the datapoints s in [0, 2π]2 for which ⟨ZZ⟩s,θ ≥ 0 and a label −1 otherwise. We create a dataset S of 10 datapoints per label by uniformly sampling points in [0, 2π]2 for which | ⟨ZZ⟩s,θ | ≥ ∆ 2 = 0.15.
This dataset allows us to define two RL environments, similar to the SL-DLP and Cliffwalk-DLP environments of Sec. 4.1:
• SL-PQC: this degenerate RL environment encodes a classification task in an episodic RL environment: at each interaction step of a 20-step episode, a sample state s is uniformly sampled from the dataset S, the agent assigns a label a = ±1 to it and receives a reward δf(s),a = ±1.
• Cliffwalk-PQC: this environment essentially adds a temporal structure to SL-PQC: each episode starts from a fixed state s0 ∈ S, and if an agent assigns the correct label to a state si, 0 ≤ i ≤ 19, it moves to a fixed state si+1 and receives a +1 reward, otherwise the episode is instantly terminated and the agent gets a −1 reward. Reaching s20 also causes termination.

heading: 4.2.2 Performance comparison
text: Having defined our PQC-generated environments, we now evaluate the performance of SOFTMAXPQC 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 θ), 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-PQCs, that learn close-to-optimal 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 to move farther in the cliffwalk, the policy family should allow learning new labels without “forgetting” the labels of earlier states. In these particular case studies, the SOFTMAX-PQC policies exhibited sufficient flexibility in this sense, whereas the DNNs we considered did not (see Appendix E for a 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.

heading: 5 Conclusion
text: 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 on learning performance. In particular, we introduced the SOFTMAX-PQC model, where a softmax policy is computed from expectation values of a 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 to 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 a rigorous separation between a class of PQC agents and any classical learner, based on the widely-believed 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.

heading: 6 Broad impact
text: We expect our work to have an 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 to be very resource-heavy 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 RL, making it more economically appealing and environmentally-friendly.
• Aside from the game-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, our 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, it 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-art ML/RL requires supercomputers that are not accessible to 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:W1259-N27 and SFB BeyondC F7102. SJ also acknowledges the Austrian Academy of Sciences as a 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.037). VD and SM acknowledge the support by the project NEASQC funded from the European Union’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.

Review summaries:
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.  ---  The 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. 

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.  

## Summary   The 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].   The introduction and related work parts are good covering most of the important references in the field.   The 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.   - Noted I am not sure how fair is the selection DNN-based RL method in terms of model capacity according to the current version.   The authors further discuss some points included of (1) Efficient policy sampling and (2) quantum advantages.   Overall, the paper is well-written and motivated. The major weakness is on the baseline selection and some scalable discussion on quantum advantages.   - baseline selection  The 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?  - scalable discussion  I 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.   If the author could provide experimental supports or discussion versus that existing analysis on the QA on parameters, the discussion could be more comprehensive.