Model-based reinforcement learning with nearly tight exploration complexity bounds

By Istvan Szita, Csaba Szepesvari. 2010

161 citations recorded by the source corpus.

Subfields: Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

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

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

When to Trust Your Model: Model-Based Policy Optimization (2019, methodology): “Prior work has also constructed complexity bounds for model-based approaches in the tabular setting (Szita & Szepesvari, 2010) and for the linear quadratic regulator (Dean et al., 2017), whereas we consider general non-linear systems.”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “Another line of work of model-based reinforcement learning is to learn a dynamic model in a hidden representation space, which is especially necessary for pixel state spaces (Kakade et al., 2018; Dann et al., 2017; Szita & Szepesvári, 2010; Kearns & Singh, 2002; Jaksch et al., 2010).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “These provably eﬃcient algorithms (see, e.g., [16, 5, 15, 23, 26, 14, 8]) predominantly address the exploration-exploitation trade-oﬀ via optimism in the face of uncertainty (OFU): when at a state, the agent assigns to each action an optimistically biased while statistically plausible estimate of…”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “ptimisminthefaceofuncertainty ,wherebythe agent searches for a value function that is a high-probability upper bound on the true value function, then follows the greedy policy for that value function [57, 103, 100]. This process may involve, for example, constructing an upper-bound on the reward fun”
PAC Bounds for Discounted MDPs (2012, methodology): “Many previous algorithms have been shown to be PAC with varying bounds (Kakade, 2003; Strehl and Littman, 2005; Strehl et al., 2006, 2009; Szita and Szepesvári, 2010; Auer, 2011).”
Fairness in Reinforcement Learning (2016, background): “E3 [13] was the first learning algorithm with a polynomial learning rate, and subsequent work improved these bounds (see Szita and Szepesvári [26] and references within).”
On the Sample Complexity of Reinforcement Learning with a Generative Model (2012, neutral): “Therefore, we did not 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…”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, methodology): “We therefore follow existing sample complexity analyses [6, 7] and assume known rewards for simplicity.”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, methodology): “Previously MoRMax [17] also used the idea of directly bounding the transition and value function, but in a very different algorithm that required discarding data and had a less tight bound.”
Combating the Compounding-Error Problem with a Multi-step Model (2019, background): “…well-understood in theory in settings such as value-function estimation [Azar et al. , 2012], exploration in discounted and ﬁnite-horizon Markov decision processes (MDPs) [Szita and Szepesv´ari, 2010; Dann and Brunskill, 2015], and exploration in contextual decision processes [Sun et al. , 2018].”
Provably Efficient Maximum Entropy Exploration (2018, methodology): “In theory, for the case of tabular Markov decision processes, the balance of exploration and exploitation has been addressed in that there are a number of methods which utilize conﬁdence based reward bonuses to encourage exploration in order to ultimately behave near optimally [KS02, Kak03, SLW + 06”
Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, background): “Although this is obviously harder, there are bounds for the discounted case where the dependence with respect to S, A, and ε is the same as for the case with a generative sampling model [25].”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, background): “There is also a line of works studying the sample complexity of obtaining a value or policy that is at most ǫ -suboptimal (Kakade, 2003; Strehl et al., 2006, 2009; Szita and Szepesv´ari, 2010; Lattimore and Hutter, 2014; Azar et al., 2013; Dann and Brunskill, 2015; Sidford et al., 2018).”
Safe Reinforcement Learning (2015, unknown): “There are many PAC RL algorithms and lower bounds on the sample complexity of an arbitrary RL algorithm (Auer et al., 2010, Brunskill and Li, 2014, Guo and Brunskill, 2015, Strehl and Littman, 2005, 2008, Strehl et al., 2009, 2006, Szita and Szepesvári, 2010).”
Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes (2019, unknown): “Efficient RL algorithms have been successfully developed to very general settings such as Markov decision processes (MDPs) [30, 11, 32], where a finite state is statistically sufficient to summarize the treatments and covariates’ history.”
PAC Optimal Exploration in Continuous Space Markov Decision Processes (2013, methodology): “Its bounds have since been improved upon by a model based algorithm (Szita and Szepesvári 2010).”