PaperlayerView exact revision on arXiv

Source-linked AI summary

Parametrized quantum policies for reinforcement learning

Sofiene Jerbi, Casper Gyurik, Simon C. Marshall, Hans J. Briegel, Vedran Dunjko

arXiv:2103.05577v2quant-phcs.AIcs.LGstat.ML

TL;DR

Reinforcement learning lacked PQC-based methods that solved standard benchmarks or demonstrated learning advantages over classical models. The paper introduces hybrid PQC policies trained classically, shows comparable benchmark performance, and constructs empirical and provable quantum advantages under the assumed classical hardness of discrete logarithms.

  • Problem

    PQC-based reinforcement learning had not solved standard benchmarking tasks or shown a theoretical learning advantage over classical algorithms.

  • Method

    The paper develops hybrid RL agents using RAW-PQC and SOFTMAX-PQC policies, trained with classical policy-gradient methods, and constructs PQC-generated environments for advantage comparisons.

  • Results

    The agents achieve performance comparable to standard DNN policies on classical benchmarks and exhibit empirical and provable learning separations in constructed RL environments.

  • Takeaways & Limitations

    PQC policies can solve several standard RL environments and can outperform classical learners on selected tasks, including environments linked to the discrete logarithm problem.

  • Takeaways & Limitations

    RAW-PQC policies lack directly adjustable greediness, while overly general trainable observables can make SOFTMAX-PQC learning rely trivially on observables rather than the circuit.

Abstract

from arXiv · show

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 for classical models, including current state-of-art deep neural networks, under the widely-believed classical hardness of the discrete logarithm problem.

1 Introduction

Parametrized quantum circuits offer hybrid quantum-classical hypothesis families, but their application to reinforcement learning had not yet solved standard benchmarks or established learning advantages. This work addresses both gaps through new PQC policies and theoretically motivated RL environments.

  • Hybrid quantum machine-learning models combine parametrized, data-dependent quantum computations with classical optimization for training.
  • Existing PQC-based RL approaches had not solved classical benchmark environments or established a learning advantage over classical algorithms.
  • The proposed hybrid agent uses a PQC policy evaluated on a QPU and trained classically with sample interactions and policy gradients.
  • The paper proposes PQC policies, training algorithms, and design analyses, showing comparable performance to simple DNN policies on OpenAI Gym benchmarks.
  • The authors construct RL environments with empirical advantages over standard DNN policies and provable separations from efficient classical learners.

2 Parametrized quantum policies: definitions and learning algorithm

The paper defines RAW-PQC and SOFTMAX-PQC policies from input-encoding and variational quantum circuits, then trains them with REINFORCE and policy-gradient estimates. Scaling parameters, weighted observables, and adjustable softmax temperature expand policy flexibility, while training requires repeated QPU executions.

  • PQC architecture: A hardware-efficient PQC alternates input-encoding unitaries with variational unitaries built from single-qubit rotations and entangling Ctrl-Z gates.
  • Policy definitions: RAW-PQC policies assign action probabilities to expectation values of projection operators associated with disjoint action subspaces.
  • Policy definitions: RAW-PQC lacks a directly adjustable greediness parameter, limiting explicit control of the transition between exploration and exploitation.
  • Policy definitions: SOFTMAX-PQC policies apply adjustable softmaxβ activation to observable expectation values and add trainable observable weights.
  • Policy definitions: The general SOFTMAX-PQC observable family can let trainable observables dominate learning, so experiments restrict observables to Pauli products or computational-basis projections.
  • PQC architecture: Trainable scaling parameters rescale encoded inputs, allowing shallow PQCs to represent functions with a wider and richer frequency spectrum.
  • Learning algorithm: REINFORCE estimates value functions from interaction batches and updates policy parameters using gradients of the log-policy.
  • Learning algorithm: Expectation-value derivatives for rotation and scaling parameters can be estimated with the parameter-shift rule, with scaling derivatives additionally requiring the chain rule.

3 Performance comparison in benchmarking environments

The paper evaluates PQC policies in three OpenAI Gym benchmarks and examines how SOFTMAX-PQC architecture choices affect learning. SOFTMAX-PQC is compared with RAW-PQC, while depth, input scaling, observable weights, and evaluation noise are considered.

  • Benchmark evaluation: SOFTMAX-PQC and RAW-PQC agents are evaluated in CartPole-v1, MountainCar-v0, and Acrobot-v1 using REINFORCE.The experiments use 20 agents per learning curve; MountainCar-v0 and Acrobot-v1 include value-function baselines.
  • Benchmark evaluation: The benchmark experiments test whether shallow PQCs acting on very few qubits can achieve good performance and whether SOFTMAX-PQC outperforms RAW-PQC.The study evaluates average learning performance for both policy constructions.
  • Architectural choices: Figure 4 varies PQC depth, input-scaling parameters λ, and observable weights w to assess their effects on SOFTMAX-PQC learning.The modified agents are compared with the reference learning curves from Figure 3.
  • Architectural choices: Training input-scaling parameters generally benefits learning, while fixing observable weights generally decreases performance and/or convergence speed.The authors associate the scaling effect with increased expressivity and the observable-weight effect with trainable greediness.
  • Architectural choices: Increasing PQC depth generally improves agent performance, although the improvement is not strictly monotonic.The maximum tested depth was Denc = 10.
  • Experimental scope: The numerical simulations omit noise in PQC evaluations, leaving simulated or hardware-induced noise as an untested factor.The paper identifies assessing noise effects as an interesting research direction.

4 Quantum advantage of PQC agents in RL environments

The paper constructs RL environments designed to separate quantum and classical learning, using reductions from discrete-logarithm classification and PQC-generated tasks. It reports theoretical separations for random, partially random, and deterministic environments, plus empirical advantages for SOFTMAX-PQC over DNNs on PQC-generated tasks.

  • Theoretical separation: The paper constructs RL environments with provable quantum–classical learning separations in attainable value functions.The construction includes fully random, partially random, and fully deterministic environment families.
  • SL-DLP: The DLP-based classification task is classically hard under the widely believed intractability of discrete logarithms, while non-trivial classical accuracy would imply an efficient DLP algorithm.The stated threshold is 1/2 + 1/poly(n) using poly(n) examples.
  • SL-DLP: The SL-DLP construction embeds supervised classification into RL by treating states as datapoints, actions as label guesses, and rewards as correctness indicators.The resulting value function is directly related to supervised-testing accuracy.
  • Cliffwalk-DLP: Cliffwalk-DLP adds chain-structured transitions and termination actions while retaining stochastic next-state sampling with probability δ.The construction introduces temporal structure beyond the fully random SL-DLP setting.
  • PQC realization: PQC policies can match the power of quantum-kernel SVM agents for DLP environments, and a polynomial-size training procedure yields near-optimal PQC classifiers with high probability.The classifier can be used to construct close-to-optimal quantum agents.
  • PQC-generated environments: PQC-generated environments use labels from a depth-4 RAW-PQC, and SOFTMAX-PQC agents learn close-to-optimal policies while tested DNN policies remain limited.The comparison covers both uniformly sampled states and cliffwalk dynamics; the separation is boosted by the temporal structure.

5 Conclusion

The paper develops PQC-based quantum RL agents and reports comparable performance to standard DNNs on benchmarks, rigorous separations from classical learners in DLP-based environments, and poor DNN performance on PQC-generated tasks.

  • Conclusion: SOFTMAX-PQC combines PQC expectation values with trainable observable weights and input-scaling parameters, enhancing policy expressivity and flexibility.The model achieves benchmark performance comparable to standard DNNs.
  • Conclusion: The paper constructs PQC-generated RL environments where SOFTMAX-PQC policies perform well while DNN agents perform poorly.These environments are presented as natural for PQC agents.
  • Conclusion: Several RL environment families exhibit rigorous separations between PQC agents and classical learners under the widely believed classical hardness of discrete logarithms.The families differ in their degree of degeneracy relative to supervised learning.

6 Broad impact

The paper discusses possible societal benefits of quantum reinforcement learning, including reduced resource demands and broader applications, alongside risks involving interpretability and unequal access to quantum computing.

  • Potential benefits: Quantum learning advantages could potentially reduce the energy consumption associated with resource-heavy reinforcement learning.The paper compares this possibility with computational advantages reported for quantum supremacy experiments.
  • Potential benefits: Quantum reinforcement learning could potentially make existing RL applications more technologically and economically accessible and enable new applications.The paper mentions quantum information and quantum chemistry as possible areas.
  • Potential risks: Quantum RL may worsen interpretability concerns because limited access to quantum Hilbert spaces could make models more opaque than classical models.The paper presents this as a possible consequence rather than an established outcome.
  • Potential risks: Private and selective access to quantum computers could reinforce existing inequalities in developing and using AI.The concern parallels unequal access to current state-of-the-art ML and RL compute resources.

Supplementary Material for: Parametrized Quantum Policies for Reinforcement Learning

The supplementary material proves that SOFTMAX-PQC policies can be sampled and differentiated efficiently when expectation values and their derivatives are estimated with bounded error.

  • Supplementary results: The supplementary material derives the log-policy gradient and proves efficient sampling and gradient estimation for SOFTMAX-PQC policies.These results are organized around Lemmas 1–3 and their proofs.
  • Efficient policy sampling: Expectation-value errors of at most ε induce total variation distance O(βε) between approximate and exact SOFTMAX-PQC policies.This establishes efficient approximate policy sampling because quantum computers can efficiently estimate expectation values to additive error.
  • Efficient policy gradients: Derivative and expectation-value approximations yield a bounded error in the approximate log-policy gradient.The stated bound is βε→0+ 3βε + O(βε^3) for every parameter index i.

C.1 Training the eigenbasis and the eigenvalues of an observable

This section explains how variational unitaries and observable weights separately control an observable’s eigenbasis and eigenvalues, while noting restrictions in the simulations.

  • Observable parametrization: A variational unitary transforms a measured observable into an equivalent observable with identical measurement probabilities and unchanged eigenvalues.The transformation is O → V†(θ)OV(θ), so the unitary changes the measurement basis without changing possible outcomes.
  • Observable parametrization: A universal variational unitary with computational-basis projections spans all Hermitian observables, separating eigenbasis parameters from eigenvalue parameters.The eigenbasis is controlled by θ, while the eigenvalues are controlled independently by α.
  • Simulation setting: The restricted observables and input encodings used in the simulations still allow the variational PQC parameters to serve a non-trivial role in learning policies.The cited passage states that these degrees of freedom can make such PQCs universal function approximators.
  • Function approximation: Expressive data-dependent quantum states combined with weighted observables can approximate arbitrary functions of the input.The construction uses expectation values of weighted Hermitian observables on sufficiently expressive quantum feature states.

D Environments specifications and hyperpameters

The supplementary material specifies the benchmark, PQC-generated, and CognitiveRadio environments, their training settings, and additional policy-shape and DLP-task analyses.

  • Environment specifications: The simulations cover OpenAI Gym benchmarks, PQC-generated environments, and the CognitiveRadio environment.Table 1 provides the environment specifications, while the MountainCar reward differs from the standard OpenAI Gym specification.
  • Architectural choices: For RAW-PQC agents, increasing circuit depth and training input-scaling parameters λ both improve learning performance.The effects are reported as more pronounced than for SOFTMAX-PQC agents.
  • Architectural choices: Even at greater depth, RAW-PQC agents remain limited in final performance and convergence speed relative to SOFTMAX-PQC agents.Figure 6 uses the learning curves from Fig. 3 as blue reference curves.
  • Hyperparameters: Table 2 distinguishes learning rates for rotation angles φ, observable weights w, and scaling parameters λ, while defining depth and width separately for PQCs and DNNs.SOFTMAX-PQCs additionally use linear annealing of β from 1 to its final value.
  • Policy shapes: In PQC-generated environments, SOFTMAX-PQC policies form wide-margin red-blue regions, whereas DNN policies typically use up to 2 or 3 regions with near-linear boundaries.Figure 10 compares prototypical policies in SL-PQC and Cliffwalk-PQC environments.
  • Additional numerical simulations: The CognitiveRadio experiment averages performance over 20 SOFTMAX-PQC agents for system sizes and qubit counts n = 2 to 5.In this environment, agents select radio channels to avoid collisions with occupied channels and receive ±1 collision rewards.
  • DLP task: The DLP construction defines a concept class from discrete logarithms over a finite multiplicative group, with labeling functions assigning positive and negative labels.The discrete logarithm problem is computing log_g x for x in Z*_p.

G Proof of Theorem 1

The proof constructs three DLP-based reinforcement-learning environments and establishes classical hardness alongside quantum learnability, with the strength of the separation depending on the environment structure.

  • Fully random: SL-DLP: The SL-DLP environment embeds classification into reinforcement learning by using datapoints as states, labels as actions, and rewards for correct guesses.Its value function is directly related to classification accuracy, while transitions remain state-independent and uniformly random.
  • Partially random: Cliffwalk-DLP: The Cliffwalk-DLP construction adds chain structure and slipping probability δ, yet for δ ∈[0.86, 1] and γ ∈[0, 0.9], classical and quantum performance remain separated.Classical learners are bounded by Vrand(s0) + 0.1, whereas quantum agents reach at least Vopt(s0) − 0.1 with probability above 2/3.
  • Fully deterministic: Deterministic-DLP: The Deterministic-DLP POMDP provides polynomially many labeled training states before testing the agent on one unlabeled point, with failure leading permanently to a limbo state.The construction uses a chain of length k + 2, where k is polynomial in n, and rewards only a correct action at the test state.
  • Fully deterministic: Deterministic-DLP: In Deterministic-DLP, a classical learner achieving value 1/2 + 1/poly(n) would yield an efficient classical DLP solver, while quantum agents attain the optimal value 1 with probability at least 0.98.The claim applies over exponentially many environment instances generated for a given DLP concept.
  • Theorem 1: Theorem 1 combines the three lemmas, while noting that value and classification accuracy coincide in SL-DLP but value can be weaker in Deterministic-DLP.For Cliffwalk-DLP, performance on deterministic portions is conservatively upper-bounded by 0 because its relation to testing accuracy is less direct.

H.3.1 Proof of classical hardness

The classical-hardness proof bounds Cliffwalk-DLP performance whenever policy accuracy is near random guessing, then applies this bound across the allowed slipping and discount-factor ranges.

  • Bounding the value gap: The proof defines g(x, δ, γ) as the policy value bound above the random baseline, with x denoting classification accuracy.The expression is g(x, δ, γ) = (x − 1)/(1 − δγx) + 1/(2 − γ).
  • Bounding the value gap: Because g is increasing in x, accuracy x ≤ 0.51 implies g(x, δ, γ) is bounded by its value at x = 0.51.The proof establishes the needed monotonicity through the derivative with respect to x.
  • Parameter ranges: At δ = 0.86 and γ = 0.9, g(0.51, δ0, γ1) ≈ 0.0995 < 0.1, yielding the required classical bound throughout δ ∈[0.86, 1] and γ ∈[0, 0.9].The monotonicity arguments extend the inequality from the selected boundary pair to the full parameter rectangle.
  • Quantum learnability: For quantum learnability, a classifier with accuracy at least 0.99 directly gives Vπ(s0) ≥ −0.1 = Vopt − 0.1 when γ ≤ 0.9.The classifier is obtained by collecting polynomially many random interactions and applying the DLP learning algorithm.

I.1 Proof of classical hardness

The proof reduces classical success in Deterministic-DLP to a DLP classifier, while constructing explicit quantum classifiers whose majority-vote predictions yield optimal-agent performance.

  • Classical hardness: A classical agent with value at least 1/2 + 1/poly(n) can be converted into a classifier by majority voting over actions after observing the training states.On successful instances, the resulting classifier labels the test point correctly with probability at least 1 − ε.
  • Classical hardness: If the converted classifier achieved accuracy 1/2 + 1/poly(n) with probability at least 2/3, it would provide an efficient classical algorithm for solving DLP.The proof obtains this probability through a counting argument over training-state sets and the assumed success probability of the agent.
  • Quantum learnability: Quantum classifiers trained on polynomially many samples achieve accuracy at least 0.99, and majority voting across independent classifiers raises the success probability to 1 − δ′.The concatenated training set remains polynomial in n even when divided into M independent segments.
  • Quantum learnability: The resulting quantum agent attains value Vq(x0) = 1 with probability at least (1 − δ′) × 0.99, giving probability at least 0.98 after setting 1 − δ′ = 0.98/0.99.This value is optimal and also implies Vq(s0) = 1.
  • Explicit quantum SVM construction: The paper implements the quantum classifier as an explicit quantum SVM: feature encoding U(x) is followed by a variational circuit V(θ) and measurement of an observable.This construction transforms the implicit quantum SVMs into explicit models while preserving the ability to represent optimal DLP policies.

K Proof of trainability of our PQC agent in the SL-DLP environment

The section develops an efficient optimization procedure for training the PQC classifier despite noisy circuit evaluations. It proves that the resulting noisy classifier approaches the optimal DLP-task accuracy with high probability under polynomial training and evaluation resources.

  • The optimization algorithm trains the variational parameter using noisy classifier evaluations and a loss function defined over a polynomial-size training set.The procedure is designed to operate directly with noisy analogues of the training loss.
  • Noise can perturb the loss landscape, shift its global minimum, and reduce testing accuracy, while the analysis addresses these effects through concentration and union-bound arguments.
  • Under the stated logarithmic parameter and sampling conditions, the resulting noisy classifier has a provable testing-accuracy guarantee for the DLP classification task.The theorem applies when the training-set exponent, noise-control parameter, and per-inner-product evaluation count satisfy the specified bounds.
  • The algorithm requires only |X|^2 evaluations of the noisy classifier, making its evaluation cost efficient in the training-set size.
  • With sufficiently large training sets and circuit-evaluation budgets, the algorithm returns a variational parameter within ε of the optimum with probability 1−δ.
Loading 2103.05577v2…