(More) Efficient Reinforcement Learning via Posterior Sampling

2013-06-04 · NeurIPS 2013 12 · Ian Osband, Daniel Russo, Benjamin Van Roy

Most provably-efficient learning algorithms introduce optimism about poorly-understood states and actions to encourage exploration. We study an alternative approach for efficient exploration, posterior sampling for reinforcement learning (PSRL). This algorithm proceeds in repeated episodes of known duration. At the start of each episode, PSRL updates a prior distribution over Markov decision processes and takes one sample from this posterior. PSRL then follows the policy that is optimal for this sample during the episode. The algorithm is conceptually simple, computationally efficient and allows an agent to encode prior knowledge in a natural way. We establish an $\tilde{O}(\tau S \sqrt{AT})$ bound on the expected regret, where $T$ is time, $\tau$ is the episode length and $S$ and $A$ are the cardinalities of the state and action spaces. This bound is one of the first for an algorithm not based on optimism, and close to the state of the art for any reinforcement learning algorithm. We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.

📄 PDF Abstract BibTeX arXiv:1306.0940

Code (0)

등록된 구현이 없습니다.

Tasks

Efficient Explorationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

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

Efficient Model-Free Reinforcement Learning Using Gaussian Process

2018-12-11 · Ying Fan, Letian Chen, Yizhou Wang

Efficient Reinforcement Learning usually takes advantage of demonstration or good exploration strategy. By applying posterior sampling in model-free RL under the hypothesis of GP, we propose Gaussian Process Posterior Sa…

model reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Posterior Sampling for Deep Reinforcement Learning

2023-04-30 · Remo Sasso, Michelangelo Conserva, Paulo Rauber

Despite remarkable successes, deep reinforcement learning algorithms remain sample inefficient: they require an enormous amount of trial and error to find good policies. Model-based algorithms promise sample efficiency b…

Computational Efficiency Deep Reinforcement Learning Model-based Reinforcement Learning reinforcement-learning+3

An Empirical Evaluation of Posterior Sampling for Constrained Reinforcement Learning

2022-09-08 · Danil Provodin, Pratik Gajane, Mykola Pechenizkiy, Maurits Kaptein

We study a posterior sampling approach to efficient exploration in constrained reinforcement learning. Alternatively to existing algorithms, we propose two simple algorithms that are more efficient statistically, simpler…

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

Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning

2023-10-11 · Mirco Mutti, Riccardo De Santi, Marcello Restelli, Alexander Marx 외

Posterior sampling allows exploitation of prior knowledge on the environment's transition dynamics to improve the sample efficiency of reinforcement learning. The prior is typically specified as a class of parametric dis…

reinforcement-learning Reinforcement Learning