Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states

Abstract

We initiate the study of tradeoffs between exploration and exploitation in online learning of properties of quantum states. Given sequential oracle access to an unknown quantum state, in each round, we are tasked to choose an observable from a set of actions aiming to maximize its expectation value on the state (the reward). Information gained about the unknown state from previous rounds can be used to gradually improve the choice of action, thus reducing the gap between the reward and the maximal reward attainable with the given action set (the regret). We provide various information-theoretic lower bounds on the cumulative regret that an optimal learner must incur, and show that it scales at least as the square root of the number of rounds played. We also investigate the dependence of the cumulative regret on the number of available actions and the dimension of the underlying space. Moreover, we exhibit strategies that are optimal for bandits with a finite number of arms and general mixed states.

arXiv comment36 pages, 3 figures

References in corpus (11)

• Experimental Quantum State Tomography of Optical Fields and Ultrafast Statistical Sampling
• Unknown Quantum States and Operations, a Bayesian View
• On quantum Renyi entropies: a new generalization and some properties
• Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
• Quantum POMDPs
• Online Learning of Quantum States
• Quantum exploration algorithms for multi-armed bandits
• Quantum Bandits
• Quantum algorithms for hedging and the learning of Ising models
• Bandit Phase Retrieval
• On the Complexity of Bandit Linear Optimization

Cited by in corpus (5)

• Quantum Logic Gate Synthesis as a Markov Decision Process
• Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search
• Quantum contextual bandits and recommender systems for quantum data
• Adaptive Online Learning of Quantum States
• Online learning of a panoply of quantum objects