Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes

2023/10/18 by Bhargav Ganguly, Ganguly, Bhargav, Xu, Yang +1
Computer Science · Physics and Astronomy · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2310.11684

openalex publication_date 2023/10/18 · openalex created_date 2023/10/21 · openalex updated_date 2026/07/28

Abstract

This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of O(1), a significant improvement over the O(√(T)) bound exhibited by classical counterparts.

Related

• Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning
• A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
• Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret
• Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning