홈 › Papers

Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees

2022-09-28 · Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, Pierre Menard

We consider reinforcement learning in an environment modeled by an episodic, finite, stage-dependent Markov decision process of horizon $H$ with $S$ states, and $A$ actions. The performance of an agent is measured by the regret after interacting with the environment for $T$ episodes. We propose an optimistic posterior sampling algorithm for reinforcement learning (OPSRL), a simple variant of posterior sampling that only needs a number of posterior samples logarithmic in $H$, $S$, $A$, and $T$ per state-action pair. For OPSRL we guarantee a high-probability regret bound of order at most $\widetilde{\mathcal{O}}(\sqrt{H^3SAT})$ ignoring $\text{poly}\log(HSAT)$ terms. The key novel technical ingredient is a new sharp anti-concentration inequality for linear forms which may be of independent interest. Specifically, we extend the normal approximation-based lower bound for Beta distributions by Alfers and Dinges [1984] to Dirichlet distributions. Our bound matches the lower bound of order $\Omega(\sqrt{H^3SAT})$, thereby answering the open problems raised by Agrawal and Jia [2017b] for the episodic setting.

📄 PDF Abstract BibTeX arXiv:2209.14414

Code (1)

d-tiapkin/optimistic-psrl-experiments 공식 구현

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

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)

Coordinated Exploration in Concurrent Reinforcement Learning

2018-02-05 · ICML 2018 7 · Maria Dimakopoulou, Benjamin Van Roy

We consider a team of reinforcement learning agents that concurrently learn to operate in a common environment. We identify three properties - adaptivity, commitment, and diversity - which are necessary for efficient coo…

Diversity reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Concave Utility Reinforcement Learning with Zero-Constraint Violations

2021-09-12 · Mridul Agarwal, Qinbo Bai, Vaneet Aggarwal

We consider the problem of tabular infinite horizon concave utility reinforcement learning (CURL) with convex constraints. For this, we propose a model-based learning algorithm that also achieves zero constraint violatio…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity

2022-06-15 · Alekh Agarwal, Tong Zhang

We propose a general framework to design posterior sampling methods for model-based RL. We show that the proposed algorithms can be analyzed by reducing regret to Hellinger distance in conditional probability estimation.…

Variational Bayesian Optimistic Sampling

2021-10-29 · NeurIPS 2021 12 · Brendan O'Donoghue, Tor Lattimore

We consider online sequential decision problems where an agent must balance exploration and exploitation. We derive a set of Bayesian `optimistic' policies which, in the stochastic multi-armed bandit case, includes the T…

Thompson Sampling