Optimistic posterior sampling for reinforcement learning: worst-case regret bounds

2017-12-01 · NeurIPS 2017 12 · Shipra Agrawal, Randy Jia

We present an algorithm based on posterior sampling (aka Thompson sampling) that achieves near-optimal worst-case regret bounds when the underlying Markov Decision Process (MDP) is communicating with a finite, though unknown, diameter. Our main result is a high probability regret upper bound of $\tilde{O}(D\sqrt{SAT})$ for any communicating MDP with $S$ states, $A$ actions and diameter $D$, when $T\ge S^5A$. Here, regret compares the total reward achieved by the algorithm to the total expected reward of an optimal infinite-horizon undiscounted average reward policy, in time horizon $T$. This result improves over the best previously known upper bound of $\tilde{O}(DS\sqrt{AT})$ achieved by any algorithm in this setting, and matches the dependence on $S$ in the established lower bound of $\Omega(\sqrt{DSAT})$ for this problem. Our techniques involve proving some novel results about the anti-concentration of Dirichlet distribution, which may be of independent interest.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Thompson Sampling

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

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)

Thompson Sampling for Multinomial Logit Contextual Bandits

2019-12-01 · NeurIPS 2019 12 · Min-hwan Oh, Garud Iyengar

We consider a dynamic assortment selection problem where the goal is to offer a sequence of assortments that maximizes the expected cumulative revenue, or alternatively, minimize the expected regret. The feedback here is…

Multi-Armed Bandits Thompson Sampling

Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation

2023-10-29 · NeurIPS 2023 11

Recent studies in reinforcement learning (RL) have made significant progress by leveraging function approximation to alleviate the sample complexity hurdle for better performance. Despite the success, existing provably e…

Computational Efficiency Reinforcement Learning (RL)

Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling

2022-03-15 · Alekh Agarwal, Tong Zhang

Provably sample-efficient Reinforcement Learning (RL) with rich observations and function approximation has witnessed tremendous recent progress, particularly when the underlying function approximators are linear. In thi…

Reinforcement Learning (RL)