PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum reinforcement learning

Daoyi Dong, Chunlin Chen, Hanxiong Li, Tzyh-Jong Tarn

arXiv:0810.3828v1quant-phcs.AIcs.LG

TL;DR

The paper addresses RL’s difficulty balancing exploration and exploitation and its slow learning in large state-action spaces. It proposes QRL using quantum superposition, collapse-based action selection, and probability-amplitude updates, with simulated experiments reporting effective learning and favorable exploration–exploitation behavior. The authors also discuss convergence, optimality, and future implementation and complexity challenges.

  • Problem

    Reinforcement learning struggles with exploration–exploitation balance and slow learning when state-action spaces become very large.

  • Method

    QRL represents states and actions as quantum superpositions, samples eigenstates through measurement collapse, and updates probability amplitudes according to rewards.

  • Results

    QRL simulations report effective learning, a good exploration–exploitation tradeoff, and improved performance over traditional RL as the simulated state space grows.

  • Takeaways & Limitations

    Probability-based action selection and quantum-parallel updating provide the paper’s proposed route to searching broadly while speeding learning, especially for larger problems.

  • Takeaways & Limitations

    The work mainly simulates QRL on traditional computers, leaving theoretical work on algorithm complexity, representation, and computation for future research.

Abstract

from arXiv · show

The key approaches for machine learning, especially learning in unknown probabilistic environments are new representations and computation mechanisms. In this paper, a novel quantum reinforcement learning (QRL) method is proposed by combining quantum theory and reinforcement learning (RL). Inspired by the state superposition principle and quantum parallelism, a framework of value updating algorithm is introduced. The state (action) in traditional RL is identified as the eigen state (eigen action) in QRL. The state (action) set can be represented with a quantum superposition state and the eigen state (eigen action) can be obtained by randomly observing the simulated quantum state according to the collapse postulate of quantum measurement. The probability of the eigen action is determined by the probability amplitude, which is parallelly updated according to rewards. Some related characteristics of QRL such as convergence, optimality and balancing between exploration and exploitation are also analyzed, which shows that this approach makes a good tradeoff between exploration and exploitation using the probability amplitude and can speed up learning through the quantum parallelism. To evaluate the performance and practicability of QRL, several simulated experiments are given and the results demonstrate the effectiveness and superiority of QRL algorithm for some complex problems. The present work is also an effective exploration on the application of quantum computation to artificial intelligence.

I. INTRODUCTION

Traditional reinforcement learning learns state-to-action policies through reward-driven interaction, but large state-action spaces make exploration and learning speed difficult. The paper motivates quantum reinforcement learning as a framework using quantum computation to address these challenges.

  • I. INTRODUCTION: Reinforcement learning learns mappings from states to actions through trial-and-error interaction with an environment, using scalar rewards to evaluate outcomes.
  • I. INTRODUCTION: Large state-action spaces create the curse of dimensionality, with the number of parameters growing exponentially with problem dimension.
  • I. INTRODUCTION: Quantum computation offers mechanisms such as superposition and quantum parallelism that can process multiple states and accelerate some difficult computations.
  • I. INTRODUCTION: The paper formalizes quantum reinforcement learning by representing state and action spaces with quantum states, using collapse for exploration, and proposing a QRL algorithm.
  • I. INTRODUCTION: Standard RL is commonly formulated with discrete-time, finite-state Markov decision processes, where policies select actions probabilistically to maximize expected discounted rewards.

B. State superposition and quantum parallelism

Quantum superposition represents multiple basis states within one quantum state, while unitary transformations act on all components simultaneously. This quantum parallelism motivates processing many state values together, although measurement directly exposes only one outcome.

  • B. State superposition and quantum parallelism: A qubit can occupy a superposition of the basis states |0⟩ and |1⟩, with complex coefficients called probability amplitudes.
  • B. State superposition and quantum parallelism: Measuring a superposed qubit collapses it into one basis state, with occurrence probabilities determined by the squared magnitudes of its amplitudes.
  • B. State superposition and quantum parallelism: A unitary transformation acts on every basis vector in a superposition and produces a new superposition containing the corresponding transformed results.
  • B. State superposition and quantum parallelism: The quantum black-box formulation maps joint inputs |z, 0⟩ to outputs |z, f(z)⟩, producing information associated with multiple function evaluations in superposition.
  • B. State superposition and quantum parallelism: An n-qubit system can simultaneously process 2^n states, but direct measurement generally provides only one state’s function value.

C. Quantum Gates

Quantum gates implement transformations required by quantum computation and are central to the paper’s QRL construction. The Hadamard gate creates superpositions, while the phase gate supports Grover iterations for reinforcing favorable decisions.

  • C. Quantum Gates: Quantum gates perform computational tasks analogously to classical logic gates, and the paper focuses on Hadamard and phase gates for QRL.
  • C. Quantum Gates: The Hadamard gate transforms |0⟩ into an equally weighted superposition of |0⟩ and |1⟩.
  • C. Quantum Gates: Applied to |1⟩, the Hadamard transformation produces equal amplitude magnitudes while inverting the phase associated with |1⟩.
  • C. Quantum Gates: The phase gate performs a conditional phase shift and serves as an important element of Grover iteration for reinforcing good decisions.

III. QUANTUM REINFORCEMENT LEARNING (QRL)

Quantum reinforcement learning retains the policy, reward function, and environment model of reinforcement learning while changing the representation, policy, parallelism, and updating operation through quantum characteristics.

  • III. QUANTUM REINFORCEMENT LEARNING (QRL): A QRL system contains a policy, reward function, and environment model, paralleling the three main subelements of traditional reinforcement learning.
  • III. QUANTUM REINFORCEMENT LEARNING (QRL): QRL differs intrinsically from traditional RL in its representation, policy, parallelism, and updating operation.

A. Representation

QRL represents traditional states and actions as eigen states and eigen actions within quantum superpositions. Measurement yields practical eigen states or actions probabilistically, with amplitudes encoding their occurrence probabilities.

  • Representation: QRL identifies traditional states and actions with orthogonal eigen states and eigen actions in a Hilbert-space representation.The eigen state or eigen action corresponds to the state or action in traditional reinforcement learning.
  • Representation: A QRL state or action may occupy a linear superposition of its eigen states or eigen actions.The superposition is a representation method for exploiting quantum characteristics during learning.
  • Representation: Measurement collapses a superposed state or action into an eigen state or eigen action with probability equal to the squared amplitude magnitude.For actions, the occurrence probability is |C_a|^2.
  • Representation: Multiple qubits encode the eigen state and eigen action sets, with m and n selected according to the numbers of states and actions.The paper uses m qubits for states and n qubits for actions.

B. Action selection policy

QRL selects actions by measuring a superposition and updates their amplitudes through Grover iterations. Rewards and successor-state values determine the update amount, while an iteration cap avoids probability over-rotation.

  • B. Action selection policy: The action policy measures a superposed action state and randomly collapses it into an eigen action according to its amplitude probability.This provides action selection without setting separate exploration parameters.
  • B. Action selection policy: TD(0) value updating can operate simultaneously over 2^m represented states through quantum parallelism.The update uses V(s) ← V(s) + α(r + γV(s′) − V(s)).
  • D. Probability amplitude updating: Grover iteration combines reflections that rotate the represented action vector by 2θ in the plane defined by the selected action and its orthogonal complement.The rotation updates action probability amplitudes.
  • D. Probability amplitude updating: The executed action’s amplitude is updated using L = int(k(r + V(s′))) Grover iterations, with k controlling the reward-value dependence.The parameter k is selected experientially in this paper and its optimization remains open.
  • D. Probability amplitude updating: QRL can reinforce an action from probability 1/2^n to sin^2[(2L + 1)θ], but caps L because excessive iterations can reduce the resulting probability.The cap uses the smaller of the reward-based iteration count and a π-dependent bound.
  • D. Probability amplitude updating: Unlike Grover search, QRL amplitude updating amplifies or shrinks amplitudes for good or bad actions rather than driving one action’s probability almost to one.The same amplitude-amplification technique serves different objectives in the two procedures.

E. QRL algorithm

The standard QRL algorithm initializes quantum representations, measures an action, executes it, and uses the resulting transition information to update values and amplitudes. Its representation supports exploration through collapse and computation through quantum parallelism.

  • E. QRL algorithm: After initialization, QRL observes the action superposition, obtains an eigen action, executes it, and receives the next state, reward, and successor value.The state value is updated using TD(0), while reward and successor value determine Grover iteration count.
  • E. QRL algorithm: The algorithm stores eigen states, state values, repeated eigen-action registers, and classical reward and iteration information.Two action registers preserve the known action while another register is measured and collapsed.
  • E. QRL algorithm: QRL represents the whole state-action space as a quantum superposition and uses amplitude probabilities to balance exploration and exploitation.Eigen actions are sampled by measurement, and amplitudes are updated using rewards and value functions.
  • E. QRL algorithm: QRL is presented both as a simulation algorithm for traditional computers and as a representation compatible with quantum parallelism for quantum computation.The paper describes these as two complementary merits of the approach.

IV. ANALYSIS OF QRL

The paper analyzes convergence, optimality, exploration–exploitation balance, and physical realization, and reports better performance when the search space becomes very large.

  • IV. ANALYSIS OF QRL: QRL’s theoretical analysis covers asymptotic convergence, optimality, stochastic behavior, exploration–exploitation balance, and physical realization.These are identified as four major analysis results.
  • IV. ANALYSIS OF QRL: QRL shows much better performance than other methods when the searching space becomes very large.This is the paper’s stated large-search-space comparison.

A. Convergence of QRL

QRL retains convergence under the same stochastic-iteration conditions as traditional reinforcement learning while changing exploration and updating through quantum-inspired mechanisms. Its exploration uses quantum measurement collapse, and quantum parallelism updates all states simultaneously.

  • Exploration: Exploration is based on the collapse postulate of quantum measurement when the quantum state is observed.The policy is therefore selected through the measurement-based mechanism rather than a conventional exploration rule.
  • Parallel updating: Quantum parallelism updates all states simultaneously, making QRL a synchronous learning algorithm.This is the principal computational distinction identified between QRL and traditional reinforcement learning.
  • Convergence: QRL is treated as a stochastic iterative algorithm, so its modification of reinforcement learning does not alter the convergence characteristic when equation (41) holds.The proof sketch connects QRL to established convergence results for stochastic iterative algorithms.

B. Optimality and stochastic algorithm

QRL obtains policies stochastically through quantum-system collapse rather than guaranteeing every individual strategy is optimal. Repeated computation increases the probability of selecting an optimal strategy, while classical simulation cannot realize exponential quantum speedups.

  • Policy optimality: QRL policies are acquired by collapse of the quantum system, and the resulting decision is probabilistic rather than guaranteed optimal on every run.The strategy is determined according to the probability amplitude of the corresponding quantum system.
  • Repeated computation: Repeating computation d times changes an optimal-strategy probability of 1 − ε into 1 − ε^d after the value function has converged.The single-run error probability ε becomes ε^d under repetition.
  • Policy representation: QRL defines optimal value functions and policies as in traditional reinforcement learning, but represents the policy probabilistically through probability amplitudes.The paper characterizes this representation as more effective and safer, while retaining the traditional definitions of optimality.
  • Physical realization: Classical simulation of QRL cannot speed learning on an exponential scale because quantum parallelism is not physically executed.The paper states that greater computational power could improve learning and motivates eventual physical quantum realization.

C. Balancing between exploration and exploitation

QRL selects actions by measuring a quantum-superposition representation, using probability amplitudes to balance exploration and exploitation. In gridworld experiments, it explores more initially, then learns faster and converges under suitable learning rates.

  • Exploration strategy: Unlike ǫ-greedy exploration, which samples all exploratory actions equally, QRL uses action probabilities to search the state-action space more selectively.The paper reports that this probability-based policy makes a good exploration–exploitation tradeoff and speeds learning.
  • Collapse action selection: QRL replaces deliberate action selection with collapse-based sampling, where measuring a superposition produces an eigen action probabilistically.The action probabilities are determined by probability amplitudes that are updated according to rewards and value functions.
  • Gridworld comparison: In the gridworld, QRL explores more than TD initially but learns faster and balances exploration and exploitation better in their respective good cases.The comparison uses TD with α = 0.01 and QRL with α = 0.06; Fig. 5 plots episodes against steps required.
  • Learning-rate effects: With 0.02 ≤ alpha ≤ 0.10, QRL learns fast and steadily converges to the optimal policy costing 36 steps to reach G.Learning becomes faster as the learning rate increases from 0.02 to 0.09.
  • Learning-rate effects: At alpha ≤ 0.01, QRL explores more but learns slowly, whereas at alpha = 0.11 or above it fails to converge because the policy vibrates near the optimum.The paper states that QRL's convergence range is larger than that of traditional TD(0).
  • Quantum implementation: Quantum parallelism updates probability amplitudes through superposition-based representations, with greater expected prominence when practical quantum apparatus becomes available.The proposed physical operations use superposition initialization and Grover iterations implemented with Hadamard and phase gates.

VI. DISCUSSION

The discussion presents QRL as a quantum-mechanics-inspired reinforcement-learning framework whose simulated implementation is effective, while identifying substantial theoretical, representational, application, and physical-implementation challenges.

  • QRL integrates quantum-mechanical characteristics with reinforcement learning as a novel learning framework.
  • The simulated QRL implementation is reported effective and superior to standard RL in several aspects, although physical implementation remains difficult.
  • Representations: QRL is mainly discussed for discrete states and actions, leaving extension to continuous states and actions as an open representation problem.
  • Function approximation and generalization: Function approximation and generalization remain challenging because they must accommodate QRL's special computation mode.
  • Theory: Further theory is needed to analyze QRL complexity and improve its representation and computation.
  • Applications: Simulated experiments demonstrate feasibility and reported superiority for learning problems with huge state spaces in unknown probabilistic environments, while broader applications are still needed.
Loading 0810.3828v1…