On the convergence of projective-simulation-based reinforcement learning in Markov decision processes

Abstract

In recent years, the interest in leveraging quantum effects for enhancing machine learning tasks has significantly increased. Many algorithms speeding up supervised and unsupervised learning were established. The first framework in which ways to exploit quantum resources specifically for the broader context of reinforcement learning were found is projective simulation. Projective simulation presents an agent-based reinforcement learning approach designed in a manner which may support quantum walk-based speed-ups. Although classical variants of projective simulation have been benchmarked against common reinforcement learning algorithms, very few formal theoretical analyses have been provided for its performance in standard learning scenarios. In this paper, we provide a detailed formal discussion of the properties of this model. Specifically, we prove that one version of the projective simulation model, understood as a reinforcement learning approach, converges to optimal behavior in a large class of Markov decision processes. This proof shows that a physically-inspired approach to reinforcement learning can guarantee to converge.

arXiv comment20 pages, 2 figures, v3: a few minor updates to match journal version. Order of authors changed

References in corpus (11)

• Quantum Machine Learning
• The quest for a Quantum Neural Network
• Quantum-enhanced machine learning
• Active learning machine learns to create new quantum experiments
• Optimizing Quantum Error Correction Codes with Reinforcement Learning
• Projective simulation for classical learning agents: a comprehensive investigation
• Projective simulation with generalization
• Meta-learning within Projective Simulation
• Benchmarking projective simulation in navigation problems
• Robotic Playing for Hierarchical Complex Skill Learning
• Quantum machine learning with glow for episodic tasks and decision games

Cited by in corpus (6)

• Operationally meaningful representations of physical systems in neural networks
• Learning how to find targets in the micro-world: The case of intermittent active Brownian particles
• Hybrid discrete-continuous compilation of trapped-ion quantum circuits with deep reinforcement learning
• Optimal foraging strategies can be learned
• Run-and-Tumble Particles Learning Chemotaxis
• Multi-Excitation Projective Simulation with a Many-Body Physics Inspired Inductive Bias