PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential improvements for quantum-accessible reinforcement learning

Vedran Dunjko, Yi-Kai Liu, Xingyao Wu, Jacob M. Taylor

arXiv:1710.11160v3quant-phcs.AIcs.NE

TL;DR

Reinforcement learning is practically well-motivated and closely linked to robotics and AI tasks, including personal assistants, self-driving cars, and AlphaGo. The paper defines criteria separating interactive RL from oracle problems and constructs quantum-accessible environments encoding Simon’s problem and Recursive Fourier Sampling. Quantum agents achieve optimal behavior in polynomial time, whereas classical learners require exponential time to reach equal efficiency in the constructed environments.

  • Problem

    Reinforcement learning is practically well-motivated and closely linked to robotics and AI tasks, including personal assistants, self-driving cars, and AlphaGo.

    Source: §1 · p. 1

  • Method

    The paper defines criteria separating interactive RL from oracle problems and constructs quantum-accessible environments encoding Simon’s problem and Recursive Fourier Sampling.

    Source: §1 · p. 2, §3 · p. 6

  • Results

    Quantum agents achieve optimal behavior in polynomial time, whereas classical learners require exponential time to reach equal efficiency in the constructed environments.

    Source: §1 · p. 2, §4.2 · p. 10

  • Takeaways & Limitations

    The results suggest quantum agents may gain super-polynomial learning improvements in recursively structured games learned through self-play.

    Source: §1 · p. 2, §5 · p. 12

    The speedups rely on quantum access to environments and specially structured settings that may be artificial or unrealistic.

    Source: §3 · p. 6, §4.3 · p. 10

Abstract

from arXiv · show

Quantum computers can offer dramatic improvements over classical devices for data analysis tasks such as prediction and classification. However, less is known about the advantages that quantum computers may bring in the setting of reinforcement learning, where learning is achieved via interaction with a task environment. Here, we consider a special case of reinforcement learning, where the task environment allows quantum access. In addition, we impose certain "naturalness" conditions on the task environment, which rule out the kinds of oracle problems that are studied in quantum query complexity (and for which quantum speedups are well-known). Within this framework of quantum-accessible reinforcement learning environments, we demonstrate that quantum agents can achieve exponential improvements in learning efficiency, surpassing previous results that showed only quadratic improvements. A key step in the proof is to construct task environments that encode well-known oracle problems, such as Simon's problem and Recursive Fourier Sampling, while satisfying the above "naturalness" conditions for reinforcement learning. Our results suggest that quantum agents may perform well in certain game-playing scenarios, where the game has recursive structure, and the agent can learn by playing against itself.

1 Introduction

Reinforcement learning extends quantum machine learning from data analysis to interactive environments, but prior quantum RL results mainly established quadratic improvements. This paper separates interactive RL from oracle problems and constructs quantum-accessible environments with exponential learning advantages.

1 Introduction

  • Quantum machine learning has largely focused on supervised and unsupervised data analysis, while reinforcement learning studies agents learning through interaction with environments.RL agents perceive states, take actions, receive rewards, and learn optimal behavior.Source: §1 · p. 1
  • Prior quantum RL work considered quantized agent computation or quantum-accessible environments, with established learning improvements limited to quadratic speedups.Amplitude amplification under quantum-accessible interaction provides the earlier quadratic improvement framework.Source: §1 · p. 2
  • The paper defines conditions separating RL tasks from oracle problems and constructs environments where quantum agents learn optimal behavior in polynomial time while classical learners require exponential time.The constructions encode Simon’s problem and Recursive Fourier Sampling while forcing nontrivial interaction.Source: §1 · p. 2
  • The proposed speedups may apply to recursively structured games when agents can simulate environments and learn through self-play.The discussion connects this setting to AlphaGo and AlphaGo Zero [13], recursive sub-games, and game-tree evaluation.Source: §1 · pp. 1–3
  • The paper develops technical background, embeds oracle identification problems into interactive RL tasks, proves the main results, and discusses practical uses.The stated organization covers quantum RL, interactive criteria, exponential separations, and applications.Source: §1 · p. 3

2 Technical background

The paper formalizes classical and quantum reinforcement learning, quantum-accessible environment realizations, and oracle identification tools. It then shows why a direct Simon-problem translation into an MDP is useful but degenerate, motivating richer constructions.

2.1 The setting of reinforcement learning

  • RL models an agent exchanging actions and percepts with an environment, where MDPs specify states, transitions, rewards, and policies.The framework includes finite action and percept sets, stochastic transitions and rewards, and policies assigning action probabilities by state.Source: §2.1 · p. 3
  • Learning efficiency measures how quickly an agent becomes nearly as rewarded as an optimal policy, subject to error and failure parameters.The definitions use finite- or infinite-horizon rewards and characterize (ϵ, δ)-efficiency after a specified number of steps.Source: §2.1 · p. 3

2.2 Framework for quantum reinforcement learning

  • Quantum RL promotes actions and percepts to quantum states and models agent-environment interaction through completely positive trace-preserving maps.Quantum environments can share the same classical MDP behavior while differing on superpositions, so an MDP does not fully specify the quantum realization.Source: §2.2 · p. 4
  • Quantum-accessible environments enable oraculization, simulating an oracle that maps an action sequence and reward register to the accumulated reward value.Each oracle query requires approximately 5η environment interaction steps, allowing quantum oracle-identification techniques to be used for RL.Source: §2.2 · p. 4

2.3 Oracle identification and Simon’s problem

  • Simon’s problem hides a string s in a two-to-one function: classical identification needs Ω(2^(n/2)) queries, whereas quantum access permits O(n) queries.The quantum oracle acts as |x⟩|y⟩ ↦ |x⟩|y ⊕ f(x)⟩ under Simon’s promise.Source: §2.3 · p. 5

2.4 Trivial transformations of oracle problems into MDPs

  • A direct MDP encoding lets an agent query f and receive reward for guessing s, but the resulting environment is highly degenerate rather than genuinely interactive.Its rewards are immediate, transitions are low rank, and it is deterministic, although it supports the relevant quantum oracle and speedup.Source: §2.4 · p. 5

3 Interactive reinforcement learning problems

The paper proposes criteria for inherently interactive RL environments that exclude direct oracle or learning-theory encodings. These criteria require delayed, state-dependent rewards and transitions, while remaining partly informal because “genuine” RL is context-dependent.

3 Interactive reinforcement learning problems

  • The proposed criteria require delayed rewards with a rewarding diameter that grows with instance size.Rewarding diameter measures the relevant path length between rewarding events for near-optimal behavior.Source: §3 · pp. 5–6
  • At each step, actions must influence later states and eventual rewards, preventing meaningless filler transitions from creating artificial interaction length.The criterion excludes cases where many actions induce the same transition or where only every kth move can matter.Source: §3 · pp. 5–6
  • Optimal actions must depend on the current state, so blindly repeating a fixed action sequence is suboptimal.This condition excludes deterministic maze settings whose solution is merely discovering and repeating one sequence.Source: §3 · p. 6
  • The rewarding-diameter criterion focuses on states recurrently reached under optimal policies and measures the shortest worst-case path to a subsequent reward.For deterministic environments it reduces to the minimum number of moves between rewarding events; for probabilistic environments it ignores rare states.Source: §3 · p. 6
  • The criteria are not fully independent and are not completely formalized because the meaning of a genuine RL problem is subjective and context-dependent.The authors state that properties a)-c) remain clearly verifiable for their later constructions despite unspecified growth and dependence thresholds.Source: §3 · p. 6

4 Interactive RL environments that lead to exponential quantum speed-ups

The paper constructs genuinely interactive quantum-accessible MDPs by embedding oracle-identification problems, then proves exponential or super-polynomial quantum learning advantages while discussing practical game-playing settings.

4 Interactive RL environments that lead to exponential quantum speed-ups

  • The constructions satisfy interactive-RL desiderata while quantum access enables exponential improvement over the best classical learner.The framework first converts task environments into quantum oracles and separately establishes efficient quantum learning and classical hardness.Source: §4 · p. 7, §4.1 · p. 7

4.1 From oracles to interactive RL environments

  • M1 unwinds each oracle query into sequential binary actions, making the rewarding diameter m and letting actions influence subsequent states.States encode action substrings so the environment remains observable while the agent’s action sequence determines the queried input.Source: §4.1 · pp. 7–8
  • M2 adds a random-jump action that lands on a random first-half prefix of the secret path, making relevant transitions stochastic and state-dependent.Optimal behavior must account for the jump location rather than blindly follow a fixed action sequence.Source: §4.1 · p. 8, Figure 2 · p. 9

4.2 Exponential speed-up from Simon’s problem

  • Any classical learner achieving (poly(n)^-1, poly(n)^-1)-efficiency in M2 requires at least O(2^n/4/poly(n)) interaction steps.The lower bound is obtained by reducing efficient learning to the hardness of flagged Simon’s problem, including the case of a zero secret string.Source: §4.2 · pp. 8–9
  • Quantum agents can achieve perfect performance in M2 using O(m^2) interaction steps, yielding an exponential classical–quantum separation for constant error and failure parameters.Quantum oraculization realizes Simon’s unitary oracle, with O(m) interaction steps per oracle query.Source: §4.2 · pp. 9–10

4.3 Practical uses of quantum-enhanced RL

  • Quantum oraculization is most plausible for simulated or model-based RL, including self-play systems such as AlphaGo Zero, rather than standard macroscopic environments.Internal game simulations can support coherent interaction, whereas ordinary classical environments effectively prohibit useful oraculization.Source: §4.3 · p. 10
  • RFS-based MDP families provide super-polynomial classical–quantum separations while retaining genuinely interactive properties and recursive, self-similar structure.The construction uses lifting to show that revealing parts of the secret still leaves a smaller hard RFS instance.Source: §4.3 · pp. 10–11

5 Discussion

The discussion balances provable quantum speedups against the need for interactive, genuinely reinforcement-learning-like environments. It highlights nested mazes, transfer learning, and future extensions with larger stochastic components.

5 Discussion

  • Quantum speedup constructions must make environments classically hard, quantum-oracularizable under reasonable concessions, and substantively reinforcement-learning-like.Source: §5 · p. 11
  • Randomness confined to rewarding paths simplifies oraculization but leaves optimal and deterministic strategies relatively close, at (n × l) versus (n × l −n/4) steps between rewards.Source: §5 · p. 12
  • Larger stochastic components remain a future direction, potentially requiring settings beyond standard MDPs and formalizing information transfer between environments.Source: §5 · p. 12
  • Nested mazes model transfer learning: solving smaller mazes can unlock appended constant-size mazes, whereas slower learners face exponentially worsening success probabilities.Source: §5 · p. 12
  • Partially observable extensions may be possible, but their optimal policies can depend on the entire interaction history rather than remain constant.Source: §5 · p. 12

A.1 Constructing the oracle Eq

The paper constructs an effective reward oracle by controlling environmental registers, collecting percept and memory states, and uncomputing unwanted responses. Self-reversible implementations or explicit state labels simplify reversal.

A.1 Constructing the oracle Eq

  • Scavenging collects environmental memory, while hijacking and self-reversibility erase percept responses without uncomputing the reward.Source: §A.1 · p. 15
  • The oracular instantiation maps an action sequence and reward register to the reward obtained by executing that sequence, with each oracle query costing approximately 5η interaction steps.Source: §A.1 · p. 15
  • The construction assumes deterministic environments, because an action sequence must uniquely determine the resulting states and rewards.Source: §A.1 · p. 15
  • Self-inverse controlled unitaries and commuting environmental operations permit reversal by running the environment twice.Source: §A.1 · p. 15, §A.2 · p. 16
  • Constructed environments can directly realize the oracle internally, and environments offering both classical and oracular access are called controllable.Source: §A.1 · pp. 15–16

A.2 Simple techniques for reversing the environment

  • When state labels equal action histories, the agent can delete duplicated state registers itself, avoiding another environment interaction.Source: §A.2 · p. 16

B.1 The flagged Simon’s problem

The flagged Simon’s problem embeds a reward flag for querying the hidden shift while preserving the original problem’s hardness. The paper proves exponential classical lower bounds for deterministic and randomized learners.

B.1 The flagged Simon’s problem

  • The flagged variant augments Simon’s function with a bit that flags when the query equals the hidden shift s.Source: §B.1 · p. 16
  • The flagged Simon’s problem has an exponential classical lower bound, so adding the reward-like flag does not significantly simplify hidden-shift identification.Source: §B.1 · p. 16
  • For zero-error algorithms, the reduction rules out learning the flagged secret in fewer than T ∈O(2n/2−1) queries.Source: §B.1 · p. 16
  • For randomized algorithms, repetition yields a lower bound of Ω(2n/2−1/poly(n)) queries when the failure probability is polynomially bounded.Source: §B.1 · p. 17

B.2 Classical lower bound for the randomized MDP M2 stemming from Simon’s problem

The paper extends Simon-type hardness to an MDP with half of the hidden shift revealed and describes Recursive Fourier Sampling as a recursively structured oracle problem. Both constructions preserve the recursive information dependencies central to the separation.

B.2 Classical lower bound for the randomized MDP M2 stemming from Simon’s problem

  • The construction relies on Simon functions with the same shift being related by output permutations, preserving the hidden-shift promise.Source: §B.2 · p. 17
  • The leaked-information lower bound embeds an n-bit instance into a 2n-bit instance and applies uniformization to obtain average-case hardness.Source: §B.2 · p. 17
  • Flagged Simon’s problem retains an exponential classical lower bound even when half of the secret shift is provided.Source: §B.2 · p. 17

C.1 Recursive Fourier Sampling

  • Recursive Fourier Sampling builds a depth-l tree of hidden strings, with each parent secret requiring information from O(n) children and the root revealing the final bit.Source: §C.1 · pp. 17–18
  • The generalized RFS oracle returns recursively defined values or ⊥, using path labels and hidden-string functions to distinguish valid parent queries.Source: §C.1 · pp. 17–18

C.2 Super-polynomial separation from Recursive Fourier Sampling

The paper constructs MDPs that encode Recursive Fourier Sampling while progressively imposing properties intended to make the environments more like reinforcement-learning tasks. The final construction M3 preserves quantum learnability and classical hardness while satisfying the targeted generic properties.

C.2 Super-polynomial separation from Recursive Fourier Sampling

  • The constructions modify RFS-based MDPs so quantum agents can learn optimally in polynomial time while classical learners require exponential time.The modifications force the quantum agent to interact nontrivially with the environment rather than directly solving an oracle problem.Source: §C.2 · p. 18
  • M1 and M2 progressively restrict actions and lengthen rewarding paths, preparing the construction for generic MDP properties.The paper introduces intermediary MDPs before constructing M3 with the full set of global properties.Source: §C.2 · pp. 18–19

C.3 The basic construction M0

  • M0 directly mirrors RFS but has a constant optimal policy and fails the desired generic MDP properties.Its action set contains complete oracle queries, and the only rewarding action is tied to the root secret.Source: §C.3 · p. 19

C.4 Unwinding the MDP

The MDP is unwound from block-level RFS queries into bit-by-bit actions, increasing the rewarding path length while preserving observability and oracle simulation. The construction also resolves an ambiguity between leaf and penultimate-layer queries.

C.4 Unwinding the MDP

  • Restricting actions to {0, 1, q} makes the agent enter RFS queries bit by bit, with state histories preserving full observability.Illegal query terminations lead to equal-length nonrewarding subtrees that return to the root.Source: §C.4 · p. 19
  • The q action at the root encodes a guess of the secret string, and only a correct guess produces reward.At non-root levels, q terminates an encoded oracle query instead.Source: §C.4 · p. 19, Figure 3 · p. 20
  • The final layer accepts n + 1 actions so the last action distinguishes leaf queries from penultimate-layer queries.This resolves a technical ambiguity because both query types otherwise have the same form.Source: §C.4 · p. 19, Figure 3 · p. 20
  • Reducing a large action set to sequences of smaller actions trades action-space size for rewarding depth, while oraculization reverses that transformation.The paper calls this reciprocal relationship the size-depth trade-off.Source: §C.4 · p. 19

C.5 Quantum learning using M2

The M2 environment can be oraculized into an RFS-type quantum oracle, allowing a quantum agent to learn the optimal policy efficiently. The construction remains compatible with episodic resets and reversible implementation requirements.

C.5 Quantum learning using M2

  • The M2 environment has path lengths ranging from n to n × l, but its query action resets the state independently of the current state after two steps.This supports the scavenging and memory-purging conditions needed for the oraculization procedure.Source: §C.5 · p. 20
  • The environment can be implemented with commuting Hermitian operations, enabling a self-reversible construction compatible with the oracle simulation.Because the MDPs originate from unitary oracles, the oraculization can be simplified.Source: §C.5 · p. 20
  • A quantum agent can learn M2’s optimal policy in expected time O(poly(κRFS)), where κRFS is the quantum query complexity of generalized RFS.The MDP is l×n-episodic, and its oracle construction extends the quantum RFS oracle.Source: §C.5 · p. 20

C.6 Hardness of classical learning in M2

The M2 construction yields a super-polynomial separation between quantum and classical learning, while M3 adds stochasticity so optimal behavior depends on environmental state labels. The M3 quantum learner first identifies the RFS secret, then learns state-action associations and uses a randomized shortcut.

C.6 Hardness of classical learning in M2

  • Any classical learner with polynomially small error and failure requires at least n−log(n) interaction steps, whereas the quantum agent learns in nO(1) steps.The quantum agent achieves (1, 1 −O(exp(−n)) efficiency) in the stated construction.Source: §C.6 · p. 21
  • No classical learning agent achieves (poly(n)−1, poly(n)−1)-efficiency in polynomially many interaction steps in M2.Polynomial repetition and deterministic reward checking extend the hardness argument to small error and failure probabilities.Source: §C.6 · p. 21
  • M2 gives a super-polynomial separation between classical and quantum (ϵ, δ)-efficient learners, including constant error and failure parameters.The classical lower bound follows by simulating M2 from an RFS oracle and reducing any efficient learner to a classical RFS solver.Source: §C.6 · pp. 20–21

C.7 Augmenting the MDP with a stochastic action

  • M3 adds stochastic transitions on states visited by optimal agents, satisfying the requirement that optimal behavior depend on state labels rather than only the interaction step.This modification is necessary because deterministic environments permit blindly repeating a fixed action sequence.Source: §C.7 · p. 21
  • The rg action randomly jumps from a root into the first half of the rewarding path, shortening the expected sequence while requiring the agent to learn the full policy.The agent still must reproduce at least the second half of the rewarding sequence after the jump.Source: Figure 4 · p. 21, §C.7 · p. 22
  • The M3 quantum learner uses three stages: recover s(∅) through RFS oraculization, collect path-state labels classically, then invoke the randomized shortcut.The second stage is needed because state labels are deleted during oraculization.Source: §C.7 · p. 22

C.8 Efficient quantum learning in M3 (and other stochastic MDPs)

M3 contains a deterministic sub-MDP M2 that supports efficient quantum learning, and this structure can extend quantum learning to stochastic environments.

C.8 Efficient quantum learning in M3 (and other stochastic MDPs)

  • M3 contains a deterministic sub-MDP M2 obtained by restricting the randomized-guess action rg.Thus, an agent that avoids rg operates in M2, where deterministic oraculization constructions apply.Source: §C.8 · pp. 22–23
  • If an efficient quantum agent learns an optimal policy for M2 and that policy enables efficient learning in M3, then a quantum agent efficiently learns M3.The construction first trains A′ on M′, then uses its policy representation to act efficiently in M.Source: §C.8 · p. 23
  • For M3, an agent can learn M2, invoke rg, and forward subsequent interaction to the simulated M2 agent to achieve optimal performance.The simulated agent navigates the rewarding prefix and carries the needed secret-string information.Source: §C.8 · p. 23
  • The construction provides no guarantees after actions leave the deterministic sub-MDP, so agents are defined to avoid such behavior.This limitation specifically concerns actions such as rg when the general construction is applied outside its supported sub-MDP.Source: §C.8 · p. 23
  • Further generalizations may handle randomized environments whose stochasticity cannot be influenced by the agent, but these extensions remain future work.Classical hardness depends on the details of the construction; M3 is treated separately for the super-polynomial separation.Source: §C.8 · p. 23

C.9 Hardness of classical learning using M3

The classical-hardness argument embeds smaller Recursive Fourier Sampling instances into larger ones, then uses uniform lifting to show that leaked prefix information does not make learning M3 efficient.

C.9 Hardness of classical learning using M3

  • The M3 construction gives classical agents useful path information through random jumps, but this still leaves learning hard under the paper’s lifting argument.Random jumps can reveal the last state of a half-path in polynomially many steps, while label connectivity can require O(n^2) queries to reconstruct.Source: §C.9 · p. 23
  • For technical simplicity, the hardness proof restricts RFS to instances whose function f is the standard inner product.This limits the class of MDPs to which the result directly applies, although generalized RFS could define further classes.Source: §C.9 · p. 23
  • A lifting embeds an RFS(n) instance into an RFS(2n) instance whose larger secret string contains the smaller secret as a suffix.The paper defines lifting as black-box simulation of the larger oracle using queries to the smaller unknown oracle.Source: §C.9 · p. 24
  • Concatenation constructs a valid 2n-bit RFS instance by combining a known n-bit function with an unknown n-bit function across input prefixes and suffixes.The construction behaves as two RFS(n) instances in parallel with minimal coupling, but initially covers only product-form instances.Source: §C.9 · p. 24
  • Uniform lifting modifies selected labels while preserving root compatibility, allowing every compatible RFS(2n) instance to be realized and sampled uniformly.Independent modifications can be stacked, and the resulting simulator uses the smaller oracles to implement the larger instance.Source: §C.9 · pp. 24–25
  • Uniform lifting implies that solving random RFS(2n) with the half-prefix leaked is no easier than solving random or worst-case RFS(n).A solver for the larger problem would solve the smaller instance by constructing a compatible uniformly distributed larger instance and extracting its suffix.Source: §C.9 · pp. 25–26
  • Consequently, no classical agent achieves (poly(n)−1, poly(n)−1)-efficiency in poly(n) interaction steps in M3.An efficient learner for M3 would yield an efficient learner for M2 with leaked prefix information, contradicting the RFS hardness result.Source: §C.9 · p. 26

C.10 Quantum advantage for learning in M3

M3 combines efficient quantum learning with classical hardness to produce a super-polynomial quantum–classical separation. The recursive structure of RFS also motivates hierarchical-learning interpretations within the supported scope.

C.10 Quantum advantage for learning in M3

  • M3 permits a super-polynomial separation between classical and quantum (ϵ, δ)-efficient learning agents, including constant error and failure parameters.The theorem also states that M3 satisfies all three criteria for MDPs with generic properties.Source: §C.10 · p. 26
  • The quantum result combines classical hardness of M3 with an efficient quantum learner obtained through oraculization and an efficient quantum algorithm for RFS.The quantum algorithm reveals the entire secret string s(∅) on the relevant oracle subspace.Source: §C.10 · p. 26

C.11 RFS as an example of hierarchical learning

  • The paper presents RFS as a possible hierarchical-learning setting suited to quantum learners but not classical learners, leaving its broader relevance for future work.The discussion connects this pattern to information carry-over and cascades of simpler tasks supporting more complex ones.Source: §C.11 · pp. 26–27
  • RFS has a hierarchical structure because higher-level secrets unlock lower-level oracles, while the lower-level secrets need not share correlations across layers.Quantum learning uses consistency between levels without requiring correlations among their secret strings.Source: §C.11 · p. 27
Loading 1710.11160v3…