Exploration in Metric State Spaces

By Sham M. Kakade, Michael Kearns, J. Langford. 2003

137 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Doubly Robust Policy Evaluation and Optimization (2014, positive): “We prove the lemma by induction and the triangle inequality (essentially following Kakade, Kearns and Langford, 2003).”
MOReL : Model-Based Offline Reinforcement Learning (2020, background): “Such a hard partitioning was considered in early works like E(3) [55], R-MAX [56], and metric-E(3) [57], but was not used to encourage pessimism.”
Informing sequential clinical decision-making through reinforcement learning: an empirical study (2010, background): “In the reinforcement learning literature, Bayesian approaches have also been explored for similar reasons (Dearden et al. 1999 ;S trens2000 ;W ang et al.2005; Engel et al. 2005); other methods targeting efficient exploration have also been explored ( Kakade et al. 2003; Strehl et al. 2006; Brunskil”
Safe Exploration in Markov Decision Processes (2012, background): “Exploration in MDPs has also been addressed before [2, 9, 10, 11, 12, 13], but most methods tend to rely on the assumption of ergodicity and, consequently, explore too aggressively.”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “the exploration-exploitation trade-off has been deeply investigated in RL literature for both continuous and discrete MDPs (Kearns and Singh, 2002; Brafman and Tennenholtz, 2003; Asmuth et al., 2009; Kakade et al., 2003; Ortner and Ryabko, 2012; Osband and Van Roy, 7 2014a,b). Jaksch et al. (2010) i”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “While there have been extensions to large state spaces (Kakade et al., 2003; Jong & Stone, 2007; Pazis & Parr, 2016), these approaches fail to be a good fit for practical scenarios where the environment is typically perceived through complex observations such as image, text, or audio signals.”
EX2: Exploration with Exemplar Models for Deep Reinforcement Learning (2017, methodology): “Ex-ploring in such state spaces has typically involved strategies such as introducing distance metrics over the state space (Pazis & Parr, 2013; Kakade et al., 2003), and approximating the quantities used in classical exploration meth-ods.”
On Oracle-Efficient PAC RL with Rich Observations (2018, background): “To extend the theory to the more practical settings of large state spaces, typical approaches include (1) distance-based state identity test under smoothness assumptions [e.g., 11–14], or (2) working with factored MDPs [e.g. , 24].”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “Among these, methods such as C-PACE [18] and metric-E(3) [19] require a good metric on the state space that satisfies the assumptions of the algorithm.”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, background): “With rich observations, many prior works either focus on structured control settings like LQRs (Abbasi-Yadkori and Szepesvári, 2011; Dean et al., 2018) or Lipschitz-continuous MDPs (Kakade et al., 2003; Ortner and Ryabko, 2012; Pazis and Parr, 2013; Lakshmanan et al., 2015).”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, background): “For MDPs with continuous state-action space, the sample complexity (e.g., Kakade et al., 2003; Kearns & Singh, 2002; Lattimore et al., 2013; Pazis & Parr, 2013) or regret have been studied under structural assumptions.”
Algorithms for Reinforcement Learning (2010, methodology): “Jong and Stone (2007) proposed a method that can be interpreted as a practical implementation of the ideas in Kakade et al. (2003), while Nouri and Littman (2009) experimented with multi-resolution regression trees and fitted Q-iteration.”
Sample Complexity Bounds of Exploration (2012, methodology): “It is worth mentioning that the analyses of E 3 family of algorithms (Kakade et al, 2003; Kearns and Koller, 1999; Kearns and Singh, 2002) use slightly different deﬁnitions of efﬁ-cient learning.”
Exploration and apprenticeship learning in reinforcement learning (2005, unknown): “The state-of-the-art answer to this problem is the E 3 -algorithm (Kearns & Singh, 2002) (and variants/extensions: Kearns & Koller, 1999; Kakade, Kearns & Langford, 2003; Brafman & Tennenholtz, 2002).”
Knows what it knows: a framework for self-aware learning (2008, methodology): “…the core of recent reinforcement-learning algorithms that have polynomial sample complexity guarantees (Kearns & Singh, 2002; Kearns & Koller, 1999; Kakade et al., 2003; Strehl et al., 2007) lies the idea of distinguishing between instances that have been learned with su.cient…”
An Introduction to Deep Reinforcement Learning (2018, unknown): “Directed exploration is, however, not trivially applicable in highdimensional state spaces (e.g., Kakade et al., 2003).”
Planning and Execution using Inaccurate Models with Provable Guarantees (2020, methodology): “[17], which proposes a method for exploration in metric state spaces, serves as an inspiration for the covering number bounds given in Theorem 4.”
PAC Reinforcement Learning With an Imperfect Model (2018, background): “While it is possible to extend the analyses to accommodate continuous Xξ-inc by a covering argument (Kakade, Kearns, and Langford 2003; Pazis and Parr 2013), such arguments incur dependence on the covering numbers, which are typically exponential in the dimension.”