Quantum Algorithm for Apprenticeship Learning

Andris Ambainis, Debbie Lim · 2025

Read Quantum Algorithm for Apprenticeship Learning by Andris Ambainis, Debbie Lim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07492.txt.

Introduction

Andris Ambainis and Debbie Lim present a quantum algorithm for learning a task by watching an expert, in a paper from 2025. Apprenticeship learning infers the hidden reward behind expert behavior, which suits tasks that are hard to specify directly. Their work builds on a classic framework for the problem.

As a stepping stone, they give a classic approximate algorithm with proven convergence, then quantize it. The quantum version keeps the same guarantees with faster steps. The speedup grows with the size of the feature space and the number of actions, improving per step cost by a quadratic factor on both counts. The authors present the result as a clean quantum gain for a core learning problem.

Catalog record

CREATORAndris Ambainis, Debbie Lim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07492

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Algorithm for Apprenticeship Learning Andris Ambainis, Debbie Lim Abstract Apprenticeship learning is a method commonly used to train artificial intelligence systems to perform tasks that are challenging to specify directly using traditional methods. Based on the work of Abbeel and Ng (ICML’04), we present a quantum algorithm for apprenticeship learning via inverse reinforcement learning. As an intermediate step, we give a classical approximate apprenticeship learning algorithm to demonstrate the speedup obtained by our quantum algorithm. We prove convergence guarantees on our classical approximate apprenticeship learning algorithm, which also extends to our quantum apprenticeship learning algorithm. We also show that, as compared to its classical counterpart, our quantum algorithm achieves an improvement in the per-iteration time complexity by a quadratic factor in the dimension of the feature vectors k k and the size of the action space A A . 1 Introduction Machine learning has emerged as a pivotal discipline, focusing on the development of algorithms and models that enable computers to learn from data and make decisions or predictions without explicit programming. This field encompasses a spectrum of approaches, such as supervised learning, unsupervised learning, and reinforcement learning, each suited to different learning scenarios and objectives [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] . Apprenticeship learning is associated with the concept of learning by observing and imitating an expert. It consists of a range of techniques aimed at enabling autonomous agents to acquire skills and knowledge through interaction with a demonstrator or mentor. Unlike traditional supervised learning approaches, apprenticeship learning emphasizes learning from demonstration, where an agent seeks to replicate experts’ behaviors by observing examples provided by a knowledgeable source. This learning framework has gained traction in various domains, including robotics and autonomous driving due to its ability to handle complex, real-world tasks and environments [ 10 , 11 , 12 , 13 , 14 ] . By leveraging apprenticeship learning, autonomous systems can effectively acquire and refine their capabilities, paving the way for more adaptive and versatile intelligent agents capable of performing tasks with human-like proficiency. Reinforcement learning is another subfield of machine learning focused on training agents to make sequential decisions in dynamic environments by maximizing cumulative rewards. Interactions between the agent and the environment can be modelled as a Markov Decision Process (MDP) [ 15 ] . There are various MDP models with different assumptions that have been widely studied [ 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 ] . A closely related framework to reinforcement learning is inverse reinforcement learning. While an agent focuses on learning optimal policies from explicit rewards in reinforcement learning, an agent in inverse reinforcement learning seeks to infer the underlying reward function from observed demonstrations or expert trajectories. By leveraging on inverse reinforcement learning, agents can learn to imitate human-like decision-making processes and preferences, even in complex and uncertain environments. This approach is particularly useful in scenarios where the reward function is not explicitly provided, allowing for more flexible and adaptive learning strategies [ 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 ] . Quantum computing has been a focal point of intense research and development efforts driven by its potential to revolutionize various fields from business, drug discovery and materials science to optimization and machine learning. From Shor’s algorithm [ 33 ] for integer factorization to Grover’s algorithm [ 34 ] for unstructured database search, quantum computing has showcased its prowess in solving computationally demanding tasks with unprecedented efficiency [ 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 ] . Seeing the power of quantum computing, a natural question is “how can apprenticeship learning take advantage of quantum algorithms to enhance the capabilities of intelligent agents, enabling them to acquire expertise through observation and imitation in quantum-enhanced environments?”. In this work, we study the problem of apprenticeship learning in the quantum setting by exploring how quantum algorithms can facilitate the acquisition of expert-level knowledge, paving the way for more capable and versatile quantum agents. 1.1 Markov decision processes and apprenticeship learning A Markov Decision Process (MDP) can be represented as a 5-tuple (\mathcal{S},\mathcal{A},R,P,\gamma) , where \mathcal{S} is a finite set of states with |\mathcal{S}|=S ; \mathcal{A} is a finite set of actions with |\mathcal{A}|=A ; R:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R} is a reward function; P=\{p(s^{\prime}|s,a)\}_{s,a} is a set of transition probabilities, i.e. p(s^{\prime}|s,a) denotes the probability of transiting to state s^{\prime} after choosing action a at state s ; \gamma\in[0,1) is a discount factor. We let MDP \backslash R denote an MDP without a reward function, i.e. (\mathcal{S},\mathcal{A},P,\gamma) . A policy \pi is a mapping from states to a probability distribution over actions. The value of a policy on an MDP is called the value function . For a given policy \pi , the value function V^{\pi}:\mathcal{S}\rightarrow\left[0,\frac{1}{1-\gamma}\right] is defined by V^{\pi}(s)=\mathbb{E}\left[\displaystyle\sum_{t=0}^{\infty}\gamma^{t}R\left(s^{(t)},a^{(t)}\right)\Big|\pi,s^{(0)}=s\right] , where the expectation is taken over the random sequence of states drawn. It is known that any discounted MDP admits an optimal policy \pi^{*} such that V^{\pi^{*}}(s)\geq V^{\pi}(s) for all \pi\in\Pi,s\in\mathcal{S} , where \Pi is the set of all policies [ 43 ] . On the other hand, for some small \epsilon\in(0,1) , a policy \tilde{\pi} is said to be \epsilon -optimal if V^{\pi^{*}}(s)\geq V^{\tilde{\pi}}(s)-\epsilon for all s\in\mathcal{S} . Often, when the state-action space is too large, the value function of an MDP can be approximated. A common class of approximators for value function approximation is the class of linear architectures [ 44 , 45 , 46 , 47 , 48 ] . Such an approximation corresponds to the use of linear parametric combination of basis functions, also known as feature vectors [ 16 , 49 , 50 , 51 ] . In this paper, we are given feature vectors \phi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]^{k} over the state-action pairs. The collection \left\{\phi(s,a)\right\}_{s,a} of feature vectors are stored in a feature matrix \Phi\in\mathbb{R}^{SA\times k} , where we assume query access to its entries. Without loss of generality, it is assumed that \sup_{s\in\mathcal{S},a\in\mathcal{A}}\left\|\phi(s,a)\right\|_{2}\leq 1 . In this work, we consider linear reward functions, i.e. the “true” reward function is given by R^{*}(s,a)=w^{*}\cdot\phi(s,a) , where w^{*}\in\mathbb{R}^{k} . It is also assumed that for all s\in\mathcal{S},a\in\mathcal{A} , |R(s,a)|\leq 1 1 1 1 The same assumption was made in Ref. [ 10 ] . In order for this assumption to hold, we assume that \|w^{*}\|_{1}\leq 1 . By linearity of the reward function, we can express the value function as \displaystyle V^{\pi}(s) \displaystyle=\mathbb{E}\left[\displaystyle\sum_{t=0}^{\infty}\gamma^{t}R\left(s^{(t)},a^{(t)}\right)\Big|s^{(0)}=s,\pi\right] \displaystyle=\mathbb{E}\left[\displaystyle\sum_{t=0}^{\infty}\gamma^{t}w\cdot\phi\left(s(t)),a^{(t)}\right)\Big|s^{(0)}=s,\pi\right] \displaystyle=w\cdot\mathbb{E}\left[\displaystyle\sum_{t=0}^{\infty}\gamma^{t}\phi\left(s^{(t)}),a^{(t)}\right)\Big|s^{(0)}=s,\pi\right], where the expectation is taken over the random sequence of states drawn by first starting from some initial state distribution \mathcal{D} and choosing actions according to \pi . A feature expectation is defined as the expected discounted accumulated feature value vector, i.e. \displaystyle\mu(\pi|s)=\mathbb{E}\left[\displaystyle\sum_{t=0}^{\infty}\gamma^{t}\phi\left(s^{(t)},a^{(t)}\right)\Big|s^{(0)}=s,\pi\right]\in\mathbb{R}^{k}. Using this definition, one can rewrite \displaystyle V^{\pi}(s)=w\cdot\mu(\pi|s). (1) From now on, we shall drop the initial state s in \mu(\pi|s) and use the notation \mu(\pi) instead when the initial state is irrelevant in the context. In the apprenticeship learning setting, the algorithm (apprentice) is required to “learn” in an MDP where the reward function is not explicitly given. The algorithm is allowed to “observe” demonstrations

Read the complete text