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

2020-04-21 · Zihan Zhang, Yuan Zhou, Xiangyang Ji

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].

📄 PDF Abstract BibTeX arXiv:2004.10019

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition

2020-12-01 · NeurIPS 2020 12 · Zihan Zhang, Yuan Zhou, Xiangyang Ji

We study the reinforcement learning problem in the setting of finite-horizon1episodic Markov Decision Processes (MDPs) with S states, A actions, and episode length H. We propose a model-free algorithm UCB-ADVAN…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost

2024-05-29 · Zhong Zheng, Haochen Zhang, Lingzhou Xue

In this paper, we consider model-free federated reinforcement learning for tabular episodic Markov decision processes. Under the coordination of a central server, multiple agents collaboratively explore the environment a…

Q-Learning

Augmenting Unsupervised Reinforcement Learning with Self-Reference

2023-11-16 · Andrew Zhao, Erle Zhu, Rui Lu, Matthieu Lin 외

Humans possess the ability to draw on past experiences explicitly when learning new tasks and applying them accordingly. We believe this capacity for self-referencing is especially advantageous for reinforcement learning…

Attribute reinforcement-learning Reinforcement Learning Unsupervised Reinforcement Learning

Omega-Regular Objectives in Model-Free Reinforcement Learning

2018-09-26 · Hahn Ernst Moritz, Perez Mateo, Schewe Sven, Somenzi Fabio 외

We provide the first solution for model-free reinforcement learning of {\omega}-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of {\omega}-r…

model reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes

2023-06-28 · Zihan Zhang, Qiaomin Xie

We develop several provably efficient model-free reinforcement learning (RL) algorithms for infinite-horizon average-reward Markov Decision Processes (MDPs). We consider both online setting and the setting with access to…

reinforcement-learning Reinforcement Learning (RL)