Near-Bayesian exploration in polynomial time

By J. Kolter, Andrew Y. Ng. 2009

303 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning (2016, background): “• BEB (Kolter & Ng, 2009): this is a model-based optimistic algorithm that adds an exploration bonus to (thus far) infrequently visited states and actions.”
Learning Parameterized Skills (2012, methodology): “Finally, Kolter and Ng [35] present a method for constructing a belief state for the transition probabilities and obtaining a greedy approximation to an optimal Bayesian policy.”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, background): “Kolter and Ng (2009) showed that no algorithm based on a bonus upper bounded by βNn(x) for any β > 0 can guarantee PAC-MDP optimality.”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “Both PAC-MDP algorithms such as MBIE-EB [1] and Bayesian algorithms such as Bayesian Exploration Bonuses (BEB) [2] have managed this tradeoff by assigning exploration bonuses to novel states.”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “In addition to the results already presented we also investigate the scaling of similar Bayesian learning algorithms BEB [17] and BOLT [1].”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “05), against principled exploration strategies RLSVI [39], UCBVI [7], optimistic Q-learning (OQL) [23], BEB [24], Thompson sampling [38] and two variants of K-learning, one using the τt schedule (9) and the other using the optimal choice τ t from solving (10).”
Hindsight Experience Replay (2017, methodology): “Moreover, we compare against DDPG with count-based exploration5 (Strehl and Littman, 2005; Kolter and Ng, 2009; Tang et al., 2016; Bellemare et al., 2016; Ostrovski et al., 2017).”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, neutral): “Bayesian RL methods [9, 11, 16, 35], which keep track of a distribution over MDPs, are an alternative to optimism-based methods.”
Safe Exploration in Markov Decision Processes (2012, methodology): “In this article we do not focus on the exploration objective and use existing ones.”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, methodology): “We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, background): “The limited prior research on upper bound PAC results for finite horizon MDPs has focused on different settings, such as partitioning a longer trajectory into fixed length segments [4, 1], or considering a sliding time window [9].”
EX2: Exploration with Exemplar Models for Deep Reinforcement Learning (2017, methodology): “Count-based bonuses and novelty estimation has been shown to provide substantial speedups in classic reinforcement learning (Strehl & Littman, 2009; Kolter & Ng, 2009), and several recent works have proposed information-theoretic or probabilistic approaches to exploration (Houthooft et al., 2016;…”
DORA The Explorer: Directed Outreaching Reinforcement Action-Selection (2018, methodology): “However, to ensure these theoretical guarantees this algorithm uses a conservative exploration which might be impractical (see also (Kolter & Ng, 2009) and Appendix B).”
Some Considerations on Learning to Explore via Meta-Reinforcement Learning (2018, background): “There exists a large body of RL work addressing this problem [10, 5, 11].”
Evolved Policy Gradients (2018, background): “Prior works add auxiliary reward terms that emphasize exploration (4; 12; 21; 40; 2; 22) and entropy loss terms (20; 29; 9; 15).”
Neural Predictive Belief Representations (2018, background): “…can also be useful for learning policies that efﬁciently explore partially observable environments by acting to reduce uncertainty on the agent’s belief (as in Bayes-optimal exploration; Wilson et al., 2007; Kolter & Ng, 2009; Sorg et al., 2010; Asmuth & Littman, 2012; Ghavamzadeh et al., 2015).”
Bounded Optimal Exploration in MDP (2016, methodology): “In the appendix of the extended version, we present the results for a problem with low-probability high-consequence transitions, in which PAC-RMDP(8) produced the best result. ter δ. BEB and BOLT are near-Bayes optimal algorithms whose parameters β and η are fully specified by their analyses, namely”
Counting to Explore and Generalize in Text-based Games (2018, methodology): “The ﬁrst is inspired by (Kolter & Ng, 2009), where we deﬁne the cumulative counting bonus as r + ( o t ) = β · n ( o t ) − 1 / 3 , where n ( o t ) is the num-Figure The second approach is the episodic discovery bonus , which encourages the agent to discover unseen states by assigning a positive…”