Optimistic Posterior Sampling For Reinforcement Learning With Few Samples And Tight Guarantees

Abstract

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keytiapkin2022optimistic

Related papers

• Why Is Posterior Sampling Better Than Optimism For Reinforcement Learning? (2016)0.00
• Breaking The Sample Complexity Barrier To Regret-optimal Model-free Reinforcement Learning (2021)0.00
• Provably Efficient Exploration In Constrained Reinforcement Learning:posterior Sampling Is All You Need (2023)0.00
• Posterior Sampling-based Online Learning For Episodic Pomdps (2023)0.00
• Model-based Reinforcement Learning For Continuous Control With Posterior Sampling (2020)0.00
• Minimax Regret Bounds For Reinforcement Learning (2017)0.00
• Posterior Sampling For Reinforcement Learning: Worst-case Regret Bounds (2017)0.00
• Posterior Sampling For Large Scale Reinforcement Learning (2017)0.00