Efficient PAC-Optimal Exploration in Concurrent, Continuous State MDPs with Delayed Updates

By Jason Pazis, Ronald E. Parr. 2016

27 citations recorded by the source corpus.

We present a new, efficient PAC optimal exploration algorithm that is able to explore in multiple, continuous or discrete state MDPs simultaneously. Our algorithm does not assume that value function updates can be completed instantaneously, and maintains PAC guarantees in realtime environments. Not only do we extend the applicability of PAC optimal exploration algorithms to new, realistic settings, but even when instant value function updates are possible, our bounds present a significant improvement over previous single MDP exploration bounds, and a drastic improvement over previous concurrent PAC bounds. We also present TCE, a new, fine grained metric for the cost of exploration.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture

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 Computational Theory and Mathematics

In Hardware and Architecture

Citations in the corpus

Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “While there have been attempts to extend these techniques to large state spaces [Kakade et al., 2003, Jong and Stone, 2007, Pazis and Parr, 2016], these approaches fail to be a good ﬁt for practical scenarios where the environment is typically perceived through complex sensory observations such as…”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, critical): “The less widely used TCE (total cost of exploration) bounds [13] and KWIK guarantees [14] suffer from the same issueand for conciseness are not discussed in detail.”
On Oracle-Efficient PAC RL with Rich Observations (2018, neutral): “[14] Jason Pazis and Ronald Parr.”
PAC Reinforcement Learning with Rich Observations (2016, background): “, polynomial in the number of functions [22] or the size of the observation space [23]).”
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.”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, background): “However, save for some recent work in continuous state spaces for which a good metric is given (Pazis and Parr, 2016), there has not yet been a thoroughly convincing attempt at generalizing counts.”