PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning Using Quantum Boltzmann Machines

Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, Pooya Ronagh

arXiv:1612.05695v3quant-phcs.AIcs.LGcs.NEmath.OC

TL;DR

Reinforcement learning seeks good policies early, but balancing exploration and exploitation is difficult. This paper simulates DBM- and QBM-based learning with SQA under an assumed annealer-native network layout. The simulations report better learning than RBM-based reinforcement learning, with QBM-RL slightly improving on DBM-RL.

  • Problem

    Reinforcement learning aims to generate good policies early while balancing exploration and exploitation, and the paper investigates whether quantum annealing can improve learning.

    Source: §1 · pp. 1–2

  • Method

    The paper uses SQA to simulate reinforcement learning with DBM-like networks and quantum Boltzmann machines, assuming the network is a near-future annealer’s native connectivity.

    Source: §1 · pp. 1, 4

  • Results

    DBM-RL outperforms RBM-RL in training-sample fidelity, and QBM-RL is on par with or slightly improves on DBM-RL; QBM-RL with SQA performs best at Γf = 2.00.

    Source: §5 · pp. 20–21

  • Takeaways & Limitations

    In the reported experiments, DBM-RL and QBM-RL train agents to traverse larger mazes, while RBM-RL approaches random-policy performance as maze size grows.

    Source: §5 · p. 21

    The approach assumes the DBM network itself is the native connectivity graph of a near-future quantum annealer.

    Source: §1 · p. 4

Abstract

from arXiv · show

We investigate whether quantum annealers with select chip layouts can outperform classical computers in reinforcement learning tasks. We associate a transverse field Ising spin Hamiltonian with a layout of qubits similar to that of a deep Boltzmann machine (DBM) and use simulated quantum annealing (SQA) to numerically simulate quantum sampling from this system. We design a reinforcement learning algorithm in which the set of visible nodes representing the states and actions of an optimal policy are the first and last layers of the deep network. In absence of a transverse field, our simulations show that DBMs are trained more effectively than restricted Boltzmann machines (RBM) with the same number of nodes. We then develop a framework for training the network as a quantum Boltzmann machine (QBM) in the presence of a significant transverse field for reinforcement learning. This method also outperforms the reinforcement learning method that uses RBMs.

1. Introduction

Reinforcement learning must produce good policies early while balancing exploration and exploitation. This paper uses SQA simulations to investigate DBM- and QBM-based reinforcement learning, assuming the DBM-like network is a near-future annealer’s native layout.

1. Introduction

  • The proposed network places state and action nodes among its visible nodes, with training capturing state–action correlations in edge weights.The DBM layout places state-visible nodes on the left and action-visible nodes on the right.Source: Figure 1 · p. 2
  • RL must generate good policies early while balancing exploration and exploitation, rather than merely converging eventually to an optimal policy.Neither exploration nor exploitation can be pursued exclusively without penalty or task failure.Source: §1 · p. 2
  • RBMs may require exponentially many hidden variables to approximate some desired joint distributions, while DBMs can model higher-order dependencies.Boltzmann-distribution sampling is a bottleneck for graphical models other than RBMs, motivating investigation of alternative models and sampling efficiency.Source: §1 · p. 3
  • SQA can approximate sampling from a quantum Boltzmann machine with a non-negligible transverse field, whereas classical simulated annealing applies only without that field.With a negligible final transverse field, SQA is expected to approach the classical sampling limit.Source: §1 · p. 4
  • SQA simulations indicate that DBM- and QBM-based reinforcement learning may improve learning over classical RBM methods, with the experiments suggesting an advantage over thermal sampling.The study assumes the network itself is the native connectivity graph of a near-future quantum annealer.Source: §1 · pp. 4–5
  • The paper proposes reinforcement learning using quantum annealing and SQA simulations, assuming a DBM connectivity graph maps directly to a feasible annealer’s native layout.The paper presents this as the first proposal for reinforcement learning using adiabatic quantum computation.Source: §1 · pp. 1, 4, 5

2. Preliminaries

The preliminaries motivate quantum annealing as a way to sample from quantum Hamiltonians, while noting that practical annealers may freeze out before reaching the final Hamiltonian. The paper therefore investigates transverse-field sampling for free-energy-based reinforcement learning.

2.1. Adiabatic Evolution of Open Quantum Systems.

  • For open-system evolution, the instantaneous stationary states form ker(L(s)), and under stated conditions the dynamics are parallel-transported along this manifold as ε approaches zero.The cited result requires a contraction-semigroup generator with closed complementary range and kernel, smooth dependence on s, and constancy near the endpoints; the endpoint deviation is O(ε^k).Source: §2.1 · pp. 5–6
  • Under the KMS condition, the Gibbs state of H(s) lies in ker(L(s)); the cited result requires ε to decrease at O(λ^2) to keep the endpoint solution δ-close to the instantaneous steady state.λ is the smallest nonzero eigenvalue in L.Source: §2.1 · p. 6
  • Practical quantum-annealer samples may correspond more closely to an intermediate freeze-out Hamiltonian than to the final Hamiltonian, motivating tests of significant-transverse-field sampling for reinforcement learning.The paper focuses on sampling from a transverse-field Ising model for free-energy-based reinforcement learning.Source: §2.1 · p. 6

2.2. Simulated Quantum Annealing.

Simulated quantum annealing approximates transverse-field Ising-model sampling by mapping the quantum partition function to a classical model with one additional dimension. The experiments vary the final transverse field to represent classical or quantum sampling regimes.

2.2. Simulated Quantum Annealing.

  • SQA uses Suzuki–Trotter expansion to approximate a transverse-field Ising model’s partition function with a classical Hamiltonian in one higher dimension.The method uses single-spin-flip quantum Monte Carlo and Metropolis acceptance probabilities; the replicas represent Trotter slices.Source: §2.2 · pp. 6–7
  • The SQA simulations use 25 replicas per spin, 300 sweeps, and 150 runs per input, with the transverse field decreasing linearly from 20.00 to either 0.01 or 2.00.The inverse temperature is fixed at 2.00; 20.00 was chosen above the training-generated coupling strengths.Source: §2.2 · p. 7
  • SQA samples the effective Hamiltonian’s Boltzmann distribution; a near-zero final transverse field represents classical sampling, while a non-negligible field represents quantum-Hamiltonian sampling.The paper distinguishes this from simulated annealing, which samples the classical Ising model through thermal fluctuations.Source: §2.2 · p. 7

2.3. Markov Decision Process.

An MDP models decisions through states, actions, transitions, rewards, and discounting, with the goal of finding an optimal policy. The paper instantiates this framework as maze traversal, where actions move an agent through cells with rewards, penalties, or obstacles.

2.3. Markov Decision Process.

  • An MDP has finite state and action sets, a transition kernel, an immediate reward function, and a discount factor γ in [0, 1).A stationary policy chooses an action for each state independently of time.Source: §2.3 · p. 7

2.3.1. Maze Traversal as a Markov Decision Process.

  • Maze traversal seeks an action in each cell that maximizes total reward while avoiding walls and pits and favoring rewards.The agent’s position is the state, and it can choose among five actions; moves into walls or beyond the maze are inadmissible.Source: §2.3.1 · p. 8
  • A clear maze transitions deterministically to the state specified by an admissible action, while a windy maze can transition elsewhere.The transition kernel is allowed to be non-time-homogeneous in general, though the stated MDP definition suffices for this work.Source: §2.3 · p. 7, §2.3.1 · p. 8
  • The maze model uses γ = 0.8, reward R = 200, penalty P = 0, and neutral value 100; stochastic rewards are simulated as 200 Ber(0.5).The stochastic reward’s expected value is 100, equal to the neutral value, so the depicted solutions also apply to that maze.Source: §2.3.1 · p. 9

2.4. Value Iteration.

Value iteration computes the optimal value function as the fixed point of the Bellman optimality operator. Its use requires full knowledge of transition probabilities and reward distributions, and its computational burden depends heavily on the sizes of the state and action sets.

2.4. Value Iteration.

  • V* is the unique fixed point of the Bellman optimality operator, and iterating that contraction converges uniformly to V*.Numerical computation of this limit is called value iteration.Source: §2.4 · p. 9
  • Value iteration depends heavily on the cardinalities of S and A, suffers from the curse of dimensionality, and requires full transition and reward-distribution knowledge.These requirements apply even to ε-optimal algorithms for this approach.Source: §2.4 · pp. 9–10

2.5. Q-functions.

The Q-function assigns an expected reward value to a state-action pair under a policy. The optimal Q-function determines an optimal policy and is itself characterized as a fixed point of a Bellman optimality operator.

2.5. Q-functions.

  • For a stationary policy, Q(π, s, a) is the expected reward from starting at s with action a and then following π.The optimal action-value function is Q*(s, a) = maxπ Q(π, s, a) = Q(π*, s, a).Source: §2.5 · p. 10
  • Computing Q*(s, a) reduces the Markov decision problem to finding the fixed point of a Bellman optimality operator on L∞(S × A).The optimal policy can be retrieved from Q*.Source: §2.5 · p. 10

2.6. Temporal-Difference Gradient Descent.

The section develops Q-learning as a sample-based alternative when transition or reward distributions are unknown, and describes gradient updates for parametrized Q-functions. It also introduces clamped Boltzmann machines as relevant to the paper’s reinforcement-learning setup.

2.6. Temporal-Difference Gradient Descent.

  • A gradient approach parametrizes functions in L∞(S × A) by θ and updates θ in the direction that minimizes the squared temporal difference.TD(0) treats the target marked (*) as constant with respect to θ.Source: §2.6 · pp. 10–11
  • Q-learning replaces expected next-state values and rewards with sampled transitions and rewards when the transition kernel or reward distribution is unknown.The next state is sampled from P(s′|s, a), and the reward is replaced by a sample of r(s, a).Source: §2.6 · p. 11
  • The paper turns next to Boltzmann-machine weights as parameters and introduces clamped Boltzmann machines for reinforcement learning.Source: §2.6 · p. 11

2.7. Clamped Boltzmann Machines.

Classical Boltzmann machines use binary visible and hidden variables connected by weighted edges, while a general Boltzmann machine permits weights between any nodes. Clamping fixes visible variables, and the quantum version replaces node variables with qubits; its free energy is defined from the equilibrium state.

2.7. Clamped Boltzmann Machines.

  • A general Boltzmann machine permits weighted edges between any two nodes, unlike RBMs and DBMs.Its visible and hidden nodes represent binary random variables.Source: §2.7 · p. 11
  • Clamping fixes a visible-variable assignment and removes visible nodes whose effects become constant coefficients in the energy.The resulting network is a subgraph.Source: §2.7 · p. 11
  • A clamped QBM associates a qubit with each node and substitutes a quantum Hamiltonian for the energy function; at Γ = 0 it is equivalent to the classical model.The equilibrium free energy uses the clamped QBM partition function and density matrix, with −tr(ρ_v ln ρ_v) as its entropy term.Source: §2.7 · pp. 11–12

2.8. Reinforcement Learning Using Clamped Boltzmann Machines.

The section derives Q-learning with clamped Boltzmann machines by using negative free energy to approximate the Q-function. State and action encodings are visible variables, and TD(0) updates use model expectations, which require sampling for general architectures.

2.8. Reinforcement Learning Using Clamped Boltzmann Machines.

  • Negative free energy of a Boltzmann machine is used to approximate the Q-function in a Q-learning method.The authors present this derivation for a general Boltzmann machine, drawing on ideas in and [38].Source: §2.8 · p. 12
  • Visible nodes are partitioned into state and action nodes, whose binary encodings represent each admissible state–action pair.The Boltzmann machine weights are the trainable parameters in the TD(0) update.Source: §2.8 · p. 12
  • For a QBM, SQA approximates observables and the Q-function through a one-dimension-higher classical Ising model.The effective classical model is used to estimate observables and free energy.Source: §2.8 · p. 13
  • For a classical Boltzmann machine, hidden-variable expectations in the TD(0) update can be approximated using SA or SQA as Γ → 0.The update includes the TD error multiplied by expected hidden-node products.Source: §2.8 · p. 13
  • For general clamped Boltzmann machines, hidden nodes are not independent, making free-energy calculation intractable.Unlike RBMs, their free energy and derivatives do not have the stated closed-form calculation.Source: §2.8 · p. 14

3. Algorithms

The algorithms adapt TD(0) Q-learning to RBMs, DBMs, and QBMs, using negative free energy to estimate Q-values. The DBM places states and actions at opposite ends of hidden layers, while the QBM uses SQA with a significant transverse field.

3. Algorithms

  • All three algorithms use the TD(0) Q-learning method, with separate procedures detailed for RBMs, DBMs, and QBMs.Their pseudocode is provided in Algorithms 1, 2, and 3.Source: §3 · p. 14

3.1. Reinforcement Learning Using RBMs.

  • RBM-RL updates an RBM using its explicit hidden-node activation formulas, avoiding Boltzmann-distribution sampling for those activations.The algorithm estimates Q-values from free energy and selects the best action by maximizing Q.Source: §3.1 · pp. 14–15

3.2. Reinforcement Learning Using DBMs.

  • DBM-RL connects state nodes to the first hidden layer and action nodes to the last, sampling hidden configurations with SA or SQA.Its weight updates include hidden-to-hidden weights; the reported SA and SQA results have no significant differences.Source: §3.2 · p. 16

3.3. Reinforcement Learning Using QBMs.

  • QBM-RL uses SQA to estimate QBM free energy through an effective classical Ising model with one additional dimension.Its transverse field decreases from 20.00 to Γ_f = 2.00, and its weight updates follow the DBM algorithm.Source: §3.3 · pp. 16–17

4. Numerical Results

The numerical experiments compare RBM-RL, DBM-RL, and QBM-RL using policy fidelity across maze settings and maze sizes. DBM sampling with SQA closely matches sampling with SA, while the reported figures organize training fidelity and scaling comparisons.

4. Numerical Results

  • Fidelity compares learned policies with the optimal policy, and each algorithm is run for 1440 trials of 500 training samples.Figure 3 plots fidelity curves across two clear mazes, a uniform-sampling version, and a windy maze; shaded regions show standard deviation.Source: §4 · p. 18, Figure 3 · p. 19
  • DBM-RL fidelity results with SQA coincide closely with those using SA, so the SA curves are omitted.QBM-RL uses SQA; RBM-RL is trained classically, and the DBM curves use Γ_f = 0.01.Source: §4 · p. 18
  • Figure 4 compares average fidelity across n × 5 mazes with one deterministic reward, two stochastic rewards, one pit, and n − 2 walls.The plotted average covers the last ℓ training samples and includes uniformly random actions as a baseline.Source: §4 · pp. 18–19, Figure 4 · p. 20

5. Discussion

DBM-RL outperforms RBM-RL in training samples, while QBM-RL with significant transverse-field sampling slightly improves on DBM-RL. The results extend to larger mazes and more-complicated transition kernels, but practical scaling remains uncharacterized.

5. Discussion

  • QBM-RL is on par with DBM-RL and slightly improves upon it, while DBM-RL outperforms RBM-RL in training samples.The authors identify QBM-RL using SQA as the best algorithm in their experiments.Source: §5 · pp. 20–21
  • The authors frame the results as evidence that quantum-device sampling may benefit machine learning, while noting that quantum annealing is not expected to sample the classical Hamiltonian's Boltzmann distribution.They propose an open-system annealer coupled to a heat bath as a possible sampler of an instantaneous Hamiltonian earlier in the anneal.Source: §5 · pp. 20–21
  • DBM-RL with SQA at Γf = 0.01 matches simulated annealing in each experiment, consistent with the expected classical limit as Γ approaches zero.In that limit, both samplers approximate the classical Ising model's Boltzmann distribution.Source: §5 · p. 21
  • QBM-RL outperforms DBM-RL, which outperforms RBM-RL, and this ordering persists with more-complicated transition kernels.The same ordering of fidelity curves is observed in Fig. 3d.Source: §5 · p. 21
  • When m < 2n, a two-hidden-layer DBM has fewer weights to train than an RBM; a fully connected hidden-layer GBM requires more weights than either model.The passage gives the DBM count as 1/4 m(2n+m), versus mn for an RBM.Source: §5 · p. 21
  • DBM-RL and QBM-RL train agents to traverse larger mazes, while RBM-RL with the same number of hidden nodes fails to beat a random policy.RBM-RL also shows a faster average-fidelity decay as maze size increases.Source: §5 · p. 21
  • The experiments do not characterize practical scaling: runtime and computational resources were not compared, and larger state-action spaces and more-complex environments remain to be studied.The authors describe the maze results as a rudimentary attempt to investigate scaling.Source: §5 · p. 22

Related papers

Loading 1612.05695v3…