Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret

2023-02-21 · Han Zhong, Jiachen Hu, Yecheng Xue, Tongyang Li, LiWei Wang

While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration-exploitation trade-off. To this end, we propose a novel UCRL-style algorithm that takes advantage of quantum computing for tabular Markov decision processes (MDPs) with $S$ states, $A$ actions, and horizon $H$, and establish an $\mathcal{O}(\mathrm{poly}(S, A, H, \log T))$ worst-case regret for it, where $T$ is the number of episodes. Furthermore, we extend our results to quantum RL with linear function approximation, which is capable of handling problems with large state spaces. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with $d$-dimensional linear representation and prove that it enjoys $\mathcal{O}(\mathrm{poly}(d, H, \log T))$ regret. Our algorithms are variants of UCRL/UCRL-VTR algorithms in classical RL, which also leverage a novel combination of lazy updating mechanisms and quantum estimation subroutines. This is the key to breaking the $\Omega(\sqrt{T})$-regret barrier in classical RL. To the best of our knowledge, this is the first work studying the online exploration in quantum RL with provable logarithmic worst-case regret.

📄 PDF Abstract BibTeX arXiv:2302.10796

Code (0)

등록된 구현이 없습니다.

Tasks

Efficient Explorationreinforcement-learning Reinforcement Learning (RL)

Worst-Case Regret Bounds for Exploration via Randomized Value Functions

2019-06-07 · NeurIPS 2019 12 · Daniel Russo

This paper studies a recent proposal to use randomized value functions to drive exploration in reinforcement learning. These randomized value functions are generated by injecting random noise into the training data, maki…

Efficient Exploration reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

2022-05-30 · Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang 외

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon $T$ suffer $\Omega(\sqrt{T})$ regret.…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Exploration in Model-based Reinforcement Learning with Randomized Reward

2023-01-09 · Lingxiao Wang, Ping Li

Model-based Reinforcement Learning (MBRL) has been widely adapted due to its sample efficiency. However, existing worst-case regret analysis typically requires optimistic planning, which is not realistic in general. In c…

Efficient Exploration Model-based Reinforcement Learning reinforcement-learning Reinforcement Learning+1

A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning

2022-08-23 · NeurIPS 2021 12 · Christoph Dann, Mehryar Mohri, Tong Zhang, Julian Zimmert

Thompson Sampling is one of the most effective methods for contextual bandits and has been generalized to posterior sampling for certain MDP settings. However, existing posterior sampling methods for reinforcement learni…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach

2024-06-06 · Filippo Lazzati, Mirco Mutti, Alberto Maria Metelli

In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve its estimate of the reward function. Since IRL suffers from identifiability issues, many th…