Concurrent PAC RL

By Zhaohan Daniel Guo, Emma Brunskill. 2015

34 citations recorded by the source corpus.

In many real-world situations a decision maker may make decisions across many separate reinforcement learning tasks in parallel, yet there has been very little work on concurrent RL. Building on the efficient exploration RL literature, we introduce two new concurrent RL algorithms and bound their sample complexity. We show that under some mild conditions, both when the agent is known to be acting in many copies of the same MDP, and when they are not the same but are taken from a finite set, we can gain linear improvements in the sample complexity over not sharing information. This is quite exciting as a linear speedup is the most one might hope to gain. Our preliminary experiments confirm this result and show empirical benefits.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Reinforcement Learning in Healthcare: A Survey (2019, background): “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].”
Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization (2020, background): “One may consider previously proposed semi-batch RL algorithms (Ernst et al., 2005; Lange et al., 2012; Singh et al., 1994; Roux, 2016) or theoretical analysis of switching cost under the tabular PAC-MDP settings (Bai et al., 2019; Guo & Brunskill, 2015) as approaching this issue.”
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.”
Efficient PAC-Optimal Exploration in Concurrent, Continuous State MDPs with Delayed Updates (2016, background): “A recent paper has demonstrated that it is possible to explore in multiple MDPs simultaneously (Guo and Brunskill 2015).”
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).”