In this paper, we aim to develop a quantum counterpart to classical Markov decision processes (MDPs), referred to as q-MDPs. We first present a comprehensive formulation of quantum MDPs with state and action spaces in the quantum domain, quantum transitions, and cost functions. The focus then shifts to establishing a verification theorem for Markovian quantum control policies. Subsequently, we introduce classes of open-loop and classical-state-preserving closed-loop policies and present their structural results. Finally, we develop algorithms for computing optimal policies and value functions for both open-loop and classical-state-preserving closed-loop policies using the duality between dynamic programming and semi-definite programming formulations.
Abstract. In this paper, the aim is to develop a quantum counterpart to classical Markov decision processes (MDPs). First, we provide a very general formulation of quantum MDPs with state and action spaces in the quantum domain, quantum transitions, and cost functions. Once we formulate the quantum MDP (q-MDP), our focus shifts to establishing the verification theorem that proves the sufficiency of Markovian quantum control policies and provides a dynamic programming principle. Subsequently, a comparison is drawn between our q-MDP model and previously established quantum MDP models (referred to as QOMDPs) found in the literature. Furthermore, approximations of q-MDPs are obtained via finite-action models, which can be formulated as QOMDPs. Finally, classes of open-loop and classical-state-preserving closed-loop policies for q-MDPs are introduced, along with structural results for these policies. In summary, we present a novel quantum MDP model aiming to introduce a new framework, algorithms, and future research avenues. We hope that our approach will pave the way for a new research direction in discrete-time quantum control.
Abstract In this paper, building on the formulation of quantum Markov decision processes (q-MDPs) presented in our previous work [ N. Saldi, S. Sanjari, and S. Yüksel , Quantum Markov Decision Processes: General Theory, Approximations, and Classes of Policies , SIAM Journal on Control and Optimization, 2024], our focus shifts to the development of semi-definite programming approaches for optimal policies and value functions of both open-loop and classical-state-preserving closed-loop policies. First, by using the duality between the dynamic programming and the semi-definite programming formulations of any q-MDP with open-loop policies, we establish that the optimal value function is linear and there exists a stationary optimal policy among open-loop policies. Then, using these results, we establish a method for computing an approximately optimal value function and formulate computation of optimal stationary open-loop policy as a bi-linear program. Next, we turn our attention to classical-state-preserving closed-loop policies. Dynamic programming and semi-definite programming formulations for classical-state-preserving closed-loop policies are established, where duality of these two formulations similarly enables us to prove that the optimal policy is linear and there exists an optimal stationary classical-state-preserving closed-loop policy. Then, similar to the open-loop case, we establish a method for computing the optimal value function and pose computation of optimal stationary classical-state-preserving closed-loop policies as a bi-linear program.
Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.
Abstract Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.
In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment's dynamics (i.e., transition probabilities), we prove that our
Quantum Value Iteration (QVI) algorithm
QVI-1 achieves a quadratic speedup in the size of the action space
(A) compared with the classical value iteration algorithm for computing the optimal policy (
π∗) and the optimal V-value function (
V0∗). Furthermore, our algorithm
QVI-2 provides an additional speedup in the size of the state space
(S) when obtaining near-optimal policies and V-value functions. Both
QVI-1 and
QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on
S and
A. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms
QVI-3 and
QVI-4 achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of
A, estimation error
(ε), and time horizon
(H). More importantly, we prove quantum lower bounds to show that
QVI-3 and
QVI-4 are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.
Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a
γ-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (
π∗), the optimal value function (
v∗), and the optimal
Q-function (
q∗), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy (
ε) and two main parameters of the MDP: the effective time horizon (
1−γ1) and the size of the action space (
A). Moreover, we show that our quantum algorithm for computing
q∗ is optimal by proving a matching quantum lower bound.