Provably Efficient Maximum Entropy Exploration

By Elad Hazan, Sham M. Kakade, Karan Singh, Abby Van Soest. 2018

369 citations recorded by the source corpus.

Suppose an agent is in a (possibly unknown) Markov Decision Process in the absence of a reward signal, what might we hope that an agent can efficiently learn to do? This work studies a broad class of objectives that are defined solely as functions of the state-visitation frequencies that are induced by how the agent behaves. For example, one natural, intrinsically defined, objective problem is for the agent to learn a policy which induces a distribution over state space that is as uniform as possible, which can be measured in an entropic sense. We provide an efficient algorithm to optimize such such intrinsically defined objectives, when given access to a black box planning oracle (which is robust to function approximation). Furthermore, when restricted to the tabular setting where we have sample based access to the MDP, our proposed algorithm is provably efficient, both in terms of its sample and computational complexities. Key to our algorithmic methodology is utilizing the conditional gradient method (a.k.a. the Frank-Wolfe algorithm) which utilizes an approximate MDP solver.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, Reinforcement Learning

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

In Reinforcement Learning

Citations in the corpus

On Reinforcement Learning and Distribution Matching for Fine-Tuning Language Models with no Catastrophic Forgetting (2022, background): “Yet another approach with apparent similarity to KL-control and DPG is state marginal matching (SMM) (Hazan et al., 2018; Lee et al., 2019).”
DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, methodology): “Another way to interpret this step is to modify the objective in Problem 9 to maximize entropy-augmented VCF: VCF(k) +H(dπk) as is common in a number of prior works, albeit with entropy over different distributions such as [40, 7].”
Diagnosing Bottlenecks in Deep Q-learning Algorithms (2019, background): “In the sampled setting, this observation motivates exploration algorithms that maximize state coverage (for example, Hazan et al. (2018) solve an exploration objective which maximizes state-space entropy).”
SMiRL: Surprise Minimizing Reinforcement Learning in Unstable Environments (2021, background): “Several works aim to maximize state entropy to encourage exploration (Lee et al., 2019; Hazan et al., 2019).”
Efficient Exploration via State Marginal Matching (2019, methodology): “While the state marginal matching objective is also considered in Hazan et al. (2018), our work builds upon this prior work in a number of dimensions.”
PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training (2021, background): “Es⇠p(s) [log p(s)] as an intrinsic reward (Hazan et al., 2019; Lee et al., 2019; Hao & Pieter, 2021; Seo et al., 2021).”
Reward-Free Exploration for Reinforcement Learning (2020, background): “The last point of comparison is a recent result of Hazan et al. [2018], that gives an efﬁcient algorithm for ﬁnding a certain exploratory policy.”
Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills (2020, methodology): “Despite the existence of strong theoretical results (Hazan et al., 2019), these approaches involve the optimization of reward functions that are challenging for current algorithms (Ecoffet et al., 2019).”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, background): “…for the tabular case, while the reward-free setting is ﬁrst formalized in Jin et al. [2020], algorithms in earlier works also guarantee to collect a polynomial-size dataset with coverage guarantees [Brafman and Tennenholtz, 2002, Hazan et al., 2018, Du et al., 2019a, Misra et al., 2019].”
Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills (2020, background): “This worked well in our experiments, but exponential sampling strategies might be needed in other environments to avoid oversampling states collected by the initially random policies (Hazan et al., 2019).”
Skew-Fit: State-Covering Self-Supervised Reinforcement Learning (2019, methodology): “Similarly, methods that provably maximize state entropy without using goal-directed exploration (Hazan et al., 2019) or methods that define new rewards to capture measures of intrinsic motivation (Mohamed & Rezende, 2015) and reachability (Savinov et al.”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, methodology): “As notation, we typically write ν(x) ∈ RZ with coordinates ν(x)[z] = ν(x | z) and we call ψ, ν the simplex features, following the example described by Jin et al. (2019). When considering H-step MDPs, this representation allows us to augment the trajectory τ with the latent variables τ = (x0, a0, z1”