Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition

By Zihan Zhang, Yuanshuo Zhou, Xiangyang Ji. 2020

181 citations recorded by the source corpus.

We study the reinforcement learning problem in the setting of finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and episode length $H$. We propose a model-free algorithm UCB-Advantage and prove that it achieves $\tilde{O}(\sqrt{H^2SAT})$ regret where $T = KH$ and $K$ is the number of episodes to play. Our regret bound improves upon the results of [Jin et al., 2018] and matches the best known model-based algorithms as well as the information theoretic lower bound up to logarithmic factors. We also show that UCB-Advantage achieves low local switching cost and applies to concurrent reinforcement learning, improving upon the recent results of [Bai et al., 2019].

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Chi Jin
2. Lin F. Yang
3. Kaiqing Zhang
4. Tamer Basar
5. Yu Bai
6. Tiancheng Yu
7. Qinghua Liu
8. Csaba Szepesvari

In Management Science and Operations Research

1. Chi Jin
2. Qinghua Liu
3. Kaiqing Zhang
4. Tamer Basar
5. Lin F. Yang
6. Tiancheng Yu
7. Yu Bai
8. Brendan O'Donoghue

Citations in the corpus

• Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “There is a parallel strand of work deriving regret and complexity bounds for model-free algorithms, primarily based on extensions of Q-learning [23, 58, 26].”
• Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “Two concurrent works Zhou et al. (2020) and Touati & Vincent (2020) consider non-stationary RL in linear MDPs, but their regret bounds, (cid:101) O ( S ) when reduced to the tabular RL setting, respectively, are less competitive than ours.”
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “, 2017) and policy optimization problems (Sidford et al., 2018b,a; Yang & Wang, 2019; Wainwright, 2019; Sidford et al., 2020; Li et al., 2020; Zhang et al., 2020).”
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, methodology): “In the episodic setting with non-stationary dynamics, the best regret bound Õ( √ H2|S||A|T ) is achieved by both model-based [27] and modelfree [30] algorithms.”
• Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “2017, 2018; Agrawal & Jia 2017), and model-free methods (e.g., Jin et al. 2018; Russo 2019; Zhang et al. 2020), both for the time-homogeneous case (i.”
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, methodology): “For the tabular episodic setting with nonstationary dynamics and no simulators, the best sample complexity is Õ(H3SA/ 2), achieved by the model-based algorithm in Azar et al. (2017) and the model-free algorithm in Zhang et al. (2020c).”