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

By Shipra Agrawal, Randy Jia. 2022

240 citations recorded by the source corpus.

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, although unknown, diameter. Our main result is a high probability regret upper bound of [Formula: see text] for any communicating MDP with S states, A actions, and diameter D. 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 closely matches the known lower bound of [Formula: see text]. Our techniques involve proving some novel results about the anti-concentration of Dirichlet distribution, which may be of independent interest.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, neutral): “We refer the readers to (Kakade et al., 2018; Dann et al., 2017; Szita & Szepesvári, 2010; Kearns & Singh, 2002; Jaksch et al., 2010; Agrawal & Jia, 2017) and the reference therein.”
Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning (2018, background): “, dynamics and expected reward) and, at each step, samples an MDP and executes the corresponding optimal policy (e.g., Osband et al., 2013; Abbasi-Yadkori and Szepesvári, 2015; Osband and Roy, 2017; Ouyang et al., 2017; Agrawal and Jia, 2017).”
Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition (2020, methodology): “For the tabular setting, there are plenty of recent works on model-based algorithms under various settings (e.g., [Jaksch et al., 2010, Agrawal and Jia, 2017, Azar et al., 2017, Ouyang et al., 2017, Fruit et al., 2019, Simchowitz and Jamieson, 2019, Zanette and Brunskill, 2019, Zhang and Ji, 2019]).”
Is Q-learning Provably Efficient? (2018, methodology): “1 Jaksch et al. [10] and Agrawal and Jia [1] apply to the more general setting of weakly communicating MDPs with S 0 states and diameter D ; our episodic MDP is a special case obtained by augmenting the state space so that S 0 = SH and D ≥ H .”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, background): “RL in stationary (discounted and un-discounted reward) MDPs has been widely studied in (Burnetas & Katehakis, 1997; Bartlett & Tewari, 2009; Jaksch et al., 2010; Agrawal & Jia, 2017; Fruit et al., 2018a;b; Sidford et al., 2018b;a; Wang, 2019; Zhang & Ji, 2019; Fruit et al., 2019; Wei et al., 2019).”
Variance Reduction Methods for Sublinear Reinforcement Learning (2018, background): “This question has been widely studied with various upper bounds on the regret having been established (see [JOA10, AJ17, AOM17]).”
Bandit Algorithms (2020, methodology): “We refer the interested reader to the papers by Allenberg et al. [2006], Abernethy et al.”
Dueling Posterior Sampling for Preference-Based Reinforcement Learning (2019, background): “Previous work on posterior sampling in RL (Osband et al., 2013; Gopalan and Mannor, 2015; Agrawal and Jia, 2017; Osband and Van Roy, 2017) is focused on learning from absolute rewards, while we extend posterior sampling to both elicit and learn from trajectory-level preference feedback.”
Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, background): “Recently, regret bounds of Õ(D √ SAT ) have been claimed in [1], however there seems to be a gap in the proof, cf.”
Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs (2018, background): “In a recent study, (Agrawal and Jia, 2017) propose an algorithm based on posterior sampling for the class of communicating MDPs.”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “…see e.g., Strehl et al. (2006); Jaksch et al. (2010); Osband et al. (2014); Osband and Van Roy (2016); Azar et al. (2017); Dann et al. (2017); Agrawal and Jia (2017); Jin et al. (2018); Russo (2019); Rosenberg and Mansour (2019a,b); Jin and Luo (2019); Zanette and Brunskill (2019);…”
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “Tabular RL concerns MDPs with a small number of states and actions, which has been thoroughly studied in recent years (see, e.g., Brafman and Tennenholtz, 2002; Jaksch et al., 2010; Dann and Brunskill, 2015; Agrawal and Jia, 2017; Azar et al., 2017; Zanette and Brunskill, 2019; Jin et al., 2018; Zha”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “…setting where S and A are ﬁnite sets, there exist algorithms that achieve asymptotic regret O ( |S||A| T ) (e.g. (Jaksch et al., 2010; Osband and Van Roy, 2016; Osband et al., 2017; Agrawal and Jia, 2017; Azar et al., 2017; Dann et al., 2018; Jin et al., 2018)), where T is the number of time steps.”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “posterior over a class of transition models given the observations (e.g., Strens, 2000; Osband and Van Roy, 2014; Abbasi-Yadkori and Szepesvári, 2015; Ouyang et al., 2017; Agrawal and Jia, 2017).”
Influence-Based Multi-Agent Exploration (2019, methodology): “Provably efﬁcient methods are proposed, such as upper conﬁdence bound (UCB) (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018) and posterior sampling for reinforcement learning (PSRL) (Strens, 2000; Osband et al., 2013; Osband & Van Roy, 2016; Agrawal & Jia, 2017).”
Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function (2019, methodology): “A Mistake in the Analysis of Previous Work In this section we mainly analysis the mistake in the proof of Lemma C.2 and Lemma C.1 [Agrawal & Jia, 2017].”