REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

By Peter L. Bartlett, Ambuj Tewari. 2009

305 citations recorded by the source corpus.

We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of O(HS√AT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

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 Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Surprising Negative Results for Generative Adversarial Tree Search (2018, methodology): “The regret analysis of MDPs (Jaksch et al., 2010; Bartlett & Tewari, 2009) is investigated, where the Optimism in the Face of Uncertainty ( OFU ) principle is applied to guarantee a high probability regret upper bound.”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “Previous theoretical work on model-based RL mostly focuses on either the ﬁnite-state MDPs (Jaksch et al., 2010; Bartlett & Tewari, 2009; Fruit et al., 2018; Lakshmanan et al., 2015; Hinderer, 2005; Pirotta et al., 2015; 2013), or the linear parametrization of the dynamics, policy, or value function…”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “This would include some discussion of ﬁnite vs inﬁnite horizon problems [4, 3], regret vs sample complexity [15] and Bayesian vs frequentist guarantees[17].”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, methodology): “We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.”
On the Sample Complexity of Reinforcement Learning with a Generative Model (2012, neutral): “…compare our results with the-state-of-the-art of PAC-MDP (Strehl et al., 2009; Szita & Szepesv´ari, 2010) and upper-conﬁdence bound based algorithms (Bartlett & Tewari, 2009; Jaksch et al., 2010), in which the choice of the exploration policy has an inﬂuence on the behavior of the learning…”
Generalization and Exploration via Randomized Value Functions (2014, background): “A growing body of work has produced reinforcement learning algorithms with statistical and computational efficiency guarantees [Kearns and Singh, 2002, Brafman and Tennenholtz, 2002, Auer and Ortner, 2006, Strehl et al., 2006, Bartlett and Tewari, 2009, Jaksch et al., 2010].”
Dynamic policy programming (2010, background): “, 2000), or upper-confidence bounds methods which address the exploration-exploitation dilemma (Jaksch et al., 2010; Szita and Szepesvári, 2010; Bartlett and Tewari, 2009; Strehl et al., 2009).”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, neutral): “When comparing UBEV’s regret bound to the ones of UCRL2 [8] and REGAL [26] requires care because (a) we measure the regret over entire episodes and (b) our transition dynamics are time-dependent within each episode, which effectively increases the state-space by a factor of H .”
Minimax Regret Bounds for Reinforcement Learning (2017, methodology): “…factors (Osband & Van Roy, 2016a).1 This positive result is the first of its kind and helps to address an ongoing question about where the fundamental lower bounds lie for reinforcement learning in finite horizon MDPs (Bartlett & Tewari, 2009; Dann & Brunskill, 2015; Osband & Van Roy, 2016a).”
Deep Exploration via Randomized Value Functions (2017, background): “Subsequent papers proposed and analyzed alternative tabular algorithms that carry out deep exploration with varying degrees of efficacy [3, 4, 5, 6, 7, 8, 9, 10].”
Near-optimal Reinforcement Learning in Factored MDPs (2014, methodology): “There is an optimistic algorithm REGAL [5] which formally replaces the UCRL2 D with and retains the high probability guarantees.”
On Lower Bounds for Regret in Reinforcement Learning (2016, methodology): “(2010); Bartlett and Tewari (2009); Dann and Brunskill (2015).”
Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning (2018, methodology): “A similar result was originally derived by Bartlett and Tewari (2009) for REGAL.”
Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, methodology): “The only possible improvement is a replacement of tmix by a parameter that may be smaller for some MDPs, such as the diameter [13] or the bias span [7, 11].”
Reinforcement Learning of POMDPs using Spectral Methods (2016, background): “Related Work In last few decades, MDP has been widely studied (Kearns and Singh, 2002; Brafman and Tennenholtz, 2003; Bartlett and Tewari, 2009; Jaksch et al., 2010) in different setting.”
Regularization in reinforcement learning (2011, methodology): “Nevertheless, the main proof technique is essentially the same as used in the proof of Theorem 3 of Bartlett et al. [2002]. For further similar results on complexity regularization, see Barron [1991]; Lugosi and Wegkamp [2004].”