Provably Efficient Maximum Entropy Exploration

Abstract

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.

Updated experiment results; minor revisions in writing

Cited by in corpus (66)

• Review: Deep Learning in Electron Microscopy
• Efficient Exploration via State Marginal Matching
• Skew-Fit: State-Covering Self-Supervised Reinforcement Learning
• A Game Theoretic Framework for Model Based Reinforcement Learning
• Reinforcement Learning with Convex Constraints
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Fast active learning for pure exploration in reinforcement learning
• State Entropy Maximization with Random Encoders for Efficient Exploration
• Learning latent state representation for speeding up exploration
• Exploration-Enhanced POLITEX
• Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Improving Robot Dual-System Motor Learning with Intrinsically Motivated Meta-Control and Latent-Space Experience Imagination
• Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills
• PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training
• Entropy Regularization for Mean Field Games with Learning
• Beyond Fine-Tuning: Transferring Behavior in Reinforcement Learning
• SMiRL: Surprise Minimizing Reinforcement Learning in Unstable Environments
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Behavior From the Void: Unsupervised Active Pre-Training
• Adaptive Reward-Free Exploration
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint
• Diversity Actor-Critic: Sample-Aware Entropy Regularization for Sample-Efficient Exploration
• Geometric Entropic Exploration
• Adversarial Soft Advantage Fitting: Imitation Learning without Policy Optimization
• Autonomous exploration for navigating in non-stationary CMPs
• Marginalized State Distribution Entropy Regularization in Policy Optimization
• Entropy Regularization with Discounted Future State Distribution in Policy Gradient Methods
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• Leveraging Non-uniformity in First-order Non-convex Optimization
• Reinforcement Learning by Guided Safe Exploration
• A Max-Min Entropy Framework for Reinforcement Learning
• A Survey of Exploration Methods in Reinforcement Learning
• Weakly-Supervised Reinforcement Learning for Controllable Behavior
• MARL with General Utilities via Decentralized Shadow Reward Actor-Critic
• Hamilton-Jacobi-Bellman Equations for Maximum Entropy Optimal Control
• Generalized Decision Transformer for Offline Hindsight Information Matching
• Adversarial Intrinsic Motivation for Reinforcement Learning
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Active Model Estimation in Markov Decision Processes
• Variational Empowerment as Representation Learning for Goal-Based Reinforcement Learning
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Exploration by Maximizing Rényi Entropy for Reward-Free RL Framework
• The Information Geometry of Unsupervised Reinforcement Learning
• Concave Utility Reinforcement Learning with Zero-Constraint Violations
• A Unified Off-Policy Evaluation Approach for General Value Function
• Regularized Policies are Reward Robust
• Exploring Unknown States with Action Balance
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Reward is enough for convex MDPs
• Action Redundancy in Reinforcement Learning
• Leveraging the Variance of Return Sequences for Exploration Policy
• Imitation with Neural Density Models
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs
• Adaptive Multi-Goal Exploration
• Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent
• Adaptive Sampling for Estimating Multiple Probability Distributions
• Maximum Entropy Model-based Reinforcement Learning
• More Efficient Exploration with Symbolic Priors on Action Sequence Equivalences