PAC Optimal Exploration in Continuous Space Markov Decision Processes

By Jason Pazis, Ronald E. Parr. 2013

82 citations recorded by the source corpus.

Current exploration algorithms can be classified in two broad categories: Heuristic, and PAC optimal. While numerous researchers have used heuristic approaches such as epsilon-greedy exploration successfully, such approaches lack formal, finite sample guarantees and may need a significant amount of fine-tuning to produce good results. PAC optimal exploration algorithms, on the other hand, offer strong theoretical guarantees but are inapplicable in domains of realistic size. The goal of this paper is to bridge the gap between theory and practice, by introducing C-PACE, an algorithm which offers strong theoretical guarantees and can be applied to interesting, continuous space problems.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

Citations in the corpus

Reinforcement Learning in Healthcare: A Survey (2019, methodology): “proposed, such as PAC guaranteed exploration methods targeting at continuous spaces [150], [151], concurrent exploration mechanisms [318], [319], [320] and exploration in deep RL [321], [322], [323].”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, background): “Extensions to continuous state space have been proposed by Pazis & Parr (2013) and Osband et al. (2016b).”
Generalization and Exploration via Randomized Value Functions (2014, methodology): “Our experiments focus on learning over episodes of a finite-horizon Markov decision process and use a version of RLSVI designed for that task, but we also propose a version of RLSVI that addresses continual learning in an infinite-horizon discounted Markov decision process.”
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.”
Deep Exploration via Randomized Value Functions (2017, background): “In terms of concrete algorithms, there is optimistic constraint propagation (OCP) (Wen and Van Roy, 2013), a provably efficient reinforcement learning algorithm for exploration and value function generalization in deterministic systems, and C-PACE (Pazis and Parr, 2013), a provably efficient reinfor”
Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning (2017, background): “C-PACE [18] provides a theoretical foundation for PAC-optimal exploration in MDPs with continuous state spaces, but it requires a metric on state spaces.”
On Oracle-Efficient PAC RL with Rich Observations (2018, neutral): “[12] Jason Pazis and Ronald Parr.”
Efficient PAC-Optimal Exploration in Concurrent, Continuous State MDPs with Delayed Updates (2016, background): “C-PACE (Pazis and Parr 2013), a ﬁxed point based algo-rithm, was the ﬁrst concrete PAC-optimal exploration algo-rithm for online, discounted, continuous state-action MDPs. DGPQ (Grande, Walsh, and How 2014), is the ﬁrst Q - learning inspired algorithm for PAC-optimal exploration in continuous…”
Lipschitz Continuity in Model-based Reinforcement Learning (2018, background): “…1995; Littman & Szepesv ´ ari, 1996; M ¨ uller, 1996; Ferns et al., 2004; Hinderer, 2005; Rachelson & Lagoudakis, 2010; Szepesv´ari, 2010; Pazis & Parr, 2013; Pirotta et al., 2015; Pires & Szepesv ´ ari, 2016; Berkenkamp et al., 2017; Bellemare et al., 2017) and bandits (Kleinberg et…”
Sample Efficient Reinforcement Learning with Gaussian Processes (2014, methodology): “This representation is also used in C-PACE (Pazis & Parr, 2013) but here it simply stores the optimistic Q-function; we do not perform a fixed point operation.”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, background): “Pazis and Parr [26] gave a nearest-neighbor-based algorithm for exploration in continuous state space.”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, methodology): “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.”
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.”
Curiosity-driven Exploration in Deep Reinforcement Learning via Bayesian Neural Networks (2016, methodology): “For small tasks, this trade-off can be handled effectively through Bayesian RL [1] and PAC-MDP methods [2–6], which offer formal guarantees.”
Incorporating causal factors into reinforcement learning for dynamic treatment regimes in HIV (2019, background): “This is a critical problem since HIV treatment has long been recognized as a well-known testbed for evaluating advanced exploration algorithms in RL research [18, 19].”
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.”
Q-learning with Nearest Neighbors (2018, background): “We also note that the work on PAC-MDP methods [34] explores the impact of exploration policy on learning performance.”
Non-Stationary Markov Decision Processes a Worst-Case Approach using Model-Based Reinforcement Learning (2019, methodology): “Utilizing Lipschitz continuity to infer bounds on a function is common in the RL, bandit and optimization communities [Kleinberg et al., 2008, Rachelson and Lagoudakis, 2010, Pirotta et al., 2015, Pazis and Parr, 2013, Munos, 2014].”
Coordinated Exploration in Concurrent Reinforcement Learning (2018, background): “In concurrent reinforcement learning [Silver et al., 2013, Pazis and Parr, 2013, Guo and Brunskill, 2015, Pazis and Parr, 2016], multiple agents interact with the same unknown environment, share data with one another, and learn in parallel.”
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).”