Provably Efficient Maximum Entropy Exploration

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

Abstract

Suppose an agent is in a (possibly unknown) Markov Decision Process (MDP) 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 defined solely as functions of the state-visitation frequencies induced by agent behavior. A natural, intrinsically defined objective is to learn a policy that induces a distribution over state space as uniform as possible, measured in an entropic sense. We provide an efficient algorithm to optimize such objectives, given access to a black-box planning oracle. In the tabular setting with sample-based access to the MDP, our proposed algorithm is provably efficient in both sample and computational complexities. Key to our methodology is the conditional gradient method (Frank-Wolfe algorithm), which utilizes an approximate MDP solver.

Introduction

Most Reinforcement Learning (RL) successes rely on well-defined reward signals. However, many real-world scenarios present "sparse" or non-existent rewards. In such cases, an agent must engage in intrinsic exploration to learn what is possible in a new environment before a specific goal is defined. A common objective for exploration is to maximize the entropy of the state-visitation distribution, encouraging the agent to visit all states with roughly equal frequency.

While entropy is a concave function in the space of state-visitation distributions, it is non-convex in the space of policies. This non-convexity makes direct optimization using standard gradient methods computationally difficult. This paper addresses how to efficiently optimize such non-convex objectives in policy space.

Methodology: The MaxEnt Algorithm

The authors propose a meta-algorithm based on the Conditional Gradient Method (Frank-Wolfe algorithm). The core idea is to decompose the complex, non-convex entropy maximization problem into a sequence of standard RL sub-problems:

  1. Distribution Estimation: The agent tracks its current state-visitation frequencies ($\hat{d}_\pi$).
  2. Intrinsic Reward Computation: A synthetic reward function is calculated based on the gradient of the entropy objective. This reward encourages the agent to visit under-explored states.
  3. Planning Oracle: A "black-box" RL solver finds a new policy maximizing this synthetic reward.
  4. Update Policy Mixture: The final solution is a mixture of policies. Each iteration adds a new policy to the set, and the agent's overall behavior becomes a weighted combination of all policies found so far.

This approach is "oracle-efficient," meaning it can leverage any approximate MDP solver to achieve efficient exploration.

Key Insights: Convexity and Mixtures

A critical insight of this work is that while the problem is non-convex in "policy space," it is convex in "distribution space." By shifting the optimization focus to distributions, powerful tools like Frank-Wolfe become applicable.

Furthermore, a single stationary policy may be insufficient to visit all states uniformly. A mixture of policies (e.g., alternating between different strategies) can achieve significantly higher entropy than any single policy could alone.

Figure 1: A visualization of why entropy is non-convex in policy space. Even if two policies $\pi_1$ and $\pi_2$ have high entropy (uniform distributions), their average $\pi_0$ results in a distribution that is less uniform.

Empirical Evaluation

The MaxEnt algorithm was evaluated on three standard RL benchmarks: MountainCar, Pendulum, and the high-dimensional Ant (MuJoCo) environment. For the Ant environment, the focus was on exploring the $xy$-plane.

Key Results

  • Theoretical Guarantees: The algorithm is proven to converge to an $\epsilon$-optimal exploration policy in $O(\frac{1}{\epsilon} \log \frac{1}{\epsilon})$ iterations, a bound independent of the state space size.
  • Exploration Performance: In experiments, the MaxEnt agent significantly outperformed random exploration. In the Ant environment, it visited far more unique $xy$ coordinates over time. Across all environments, the entropy of the state distribution increased monotonically and much faster than the random baseline.

Conclusion and Future Work

While the MaxEnt algorithm provides a principled framework for exploration, some challenges remain. The current implementation relies on simple discretization for density estimation, which may not scale to high-dimensional raw sensory inputs like pixels. Future work could integrate neural density estimators. Additionally, while mixture policies are theoretically optimal, executing them can be less convenient than a single stationary policy in certain practical deployments. Finally, extending the provable sample complexity bounds from the tabular setting to deep RL with function approximation remains an open research direction.

Summary updated

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.
BibTeX
@inproceedings{hazan2019provably,
  author = {Elad Hazan and Sham M. Kakade and Karan Singh and Abby Van Soest},
  title = {{Provably Efficient Maximum Entropy Exploration}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=ByNN_nZ_WB},
}
Figure