Source-linked AI summary
Provably Efficient Maximum Entropy Exploration
Elad Hazan, Sham M. Kakade, Karan Singh, Abby Van Soest
TL;DR
The paper asks how agents can explore an MDP without rewards by optimizing objectives based on induced state-visitation frequencies. It develops a Frank-Wolfe method using black-box approximate planning, showing provable efficiency and near-optimal entropy exploration under stated oracle assumptions.
Problem
Reward-free exploration requires learning useful behavior in possibly unknown MDPs, where state-space size, unknown transitions, and nonlinear policy classes make entropy optimization difficult.
Method
The method applies conditional gradient optimization to state-visitation objectives using approximate planning and state-distribution estimation oracles.
Results
The algorithm produces a policy with entropy close to optimal, with a planning-oracle call bound independent of the MDP state-space size.
Takeaways & Limitations
The framework extends beyond maximum entropy to any continuous and smooth objective over state-visitation frequencies, including other entropic measures.
Takeaways & Limitations
For the non-smooth entropy functional, the resulting sub-optimality bound incurs extraneous factors from smoothing via Hσ.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies reward-free exploration objectives defined by state-visitation frequencies, focusing on entropy and broader concave objectives. It proposes a provably efficient Frank-Wolfe method using approximate planning and state-distribution estimation oracles.
- Reward-free exploration asks what an agent can learn about an environment when no reward signal is available.
- The objective class consists of functions of induced state-visitation frequencies, including maximizing state-distribution entropy and more generally optimizing concave distribution functionals.
- Large or unknown MDPs and nonlinear policy classes make entropy maximization non-convex and computationally difficult.
- The proposed method uses an approximate planning oracle and the conditional gradient, or Frank-Wolfe, algorithm to optimize exploration objectives.The framework assumes access to approximate planning and state-distribution estimation oracles.
- The algorithm generates reward signals whose sequential optimization yields a policy with entropy close to optimal.The main theorem bounds planning-oracle calls independently of the MDP state-space size, while tabular constructions provide sample and computational complexity guarantees.
2 Preliminaries
The preliminaries define discounted MDPs, policies, values, induced state distributions, and mixtures of stationary policies. They distinguish mixture behavior from stationary policies while relating state distributions to exploration objectives.
- An infinite-horizon discounted MDP is specified by states, actions, rewards, transitions, a discount factor, and an initial-state distribution.
- A policy maps histories to actions, while a stationary policy maps the current state to an action distribution independently of time.
- A policy’s discounted value is the expected cumulative reward collected over trajectories generated by that policy.
- The discounted state distribution summarizes state visitation across time and serves as an infinite-horizon analogue of a stationary distribution.
- A mixture samples one stationary policy initially and follows it thereafter, inducing a mixture of the component policies’ state distributions.Such a mixture need not be representable as a stationary stochastic policy because its actions are not conditionally independent given states.
3 The Objective: MaxEnt Exploration
The paper formulates maximum-entropy exploration as optimizing concave reward functionals over induced state distributions, while showing the corresponding policy-space problem is generally non-concave. It then recasts the search as convex optimization over achievable distributions and establishes that stationary policies suffice.
- 3.1 Examples of reward functionals: Maximum-entropy exploration seeks a policy whose induced state distribution maximizes a concave reward functional.Entropy is a motivating example, and the objective can be generalized to other entropic measures.
- 3.1 Examples of reward functionals: The framework also covers relative and cross-entropy objectives, with uniform-reference cross entropy potentially enforcing more uniform coverage than entropy.The same techniques are described as applicable to other entropic measures.
- 3.2.1 Non-convexity in the policy space: The entropy objective is not concave in the policy because state distributions are not affine functions of policies.Lemma 3.1 states H(dπ) is not concave in π, with a construction comparing policies π0, π1, and π2.
- 3.2.2 Convexity in the distribution space: The set of achievable induced distributions forms a convex optimization domain in which the max-ent policy search can be recast.Every feasible distribution in K corresponds to a policy, and every policy induces a distribution in K.
- 3.2.3 Sufficiency of Stationary Policies: Stationary Markov policies suffice for optimizing induced state-distribution objectives because they achieve the same set of state distributions as possibly non-Markovian policies.Lemma 3.3 establishes this equivalence of achievable induced state distributions.
4 Algorithms & Main Results
The paper optimizes smooth objectives over state-visitation distributions using policy mixtures, approximate planning, and distribution-estimation oracles. Its guarantees extend from entropy maximization to unknown tabular MDPs, with smoothing needed to obtain bounds for the non-smooth entropy objective.
- Algorithmic framework: The algorithm maintains a mixture over policies, adding policies to its support and reweighting them through two distribution and planning oracles.The planning oracle supplies approximately optimizing policies, while the distribution oracle estimates induced state distributions.
- Main theorem: For any β-smooth, B-bounded reward functional satisfying the stated assumptions, Theorem 4.1 sets ε1 = 0.1ε, ε0 = 0.1β−1ε, and η = 0.1β−1ε.The iteration count is specified through T = η−1 log 10Bε−1.
- Entropy objective: The entropy objective is handled through the smoothed functional Hσ, which yields sub-optimality guarantees for the true entropy H.The extra factors of |S| arise from imposed smoothing and are unnecessary for naturally smooth objectives.
- Oracle construction: The tabular oracle construction assumes a γ-discounted episodic environment with resets and uses sampled episodes to learn transition information.Known MDPs instead permit exact planning methods such as value iteration or linear programming.
- Unknown MDPs: In unknown tabular MDPs, sample-based planning and distribution-estimation oracles make Algorithm 1 run in polynomial sample and computational complexity.The construction reuses transition information across reward-function invocations, while total sampled episodes scale as n(T + m|S||A|).
5 Proof of Concept Experiments
The experiments evaluate MaxEnt exploration across MountainCar, Pendulum, and Ant using discretized state representations and approximate planning agents. The agent expands state coverage and increases entropy, while larger policy mixtures reach more distinct Ant positions within the same time.
- The MaxEnt agent reaches the set of reachable states within a small number of iterations while monotonically increasing the entropy of its induced state distribution.
- State representation and reward: The experiments estimate state distributions with a simple count-based estimator over discretized state spaces, though neural density estimators are also possible.Ant’s 29-dimensional state space is reduced to dimension 7 using xy grid coordinates and a random projection.
- For Ant, increasing the number of policies in the mixture lets the agent reach more distinct xy states in the same amount of time.Results were averaged over N = 20 executions.
- Reward function: Each planning agent is trained to maximize a KL divergence objective function.
- MountainCar and Pendulum: MountainCar and Pendulum use REINFORCE planning agents with single-hidden-layer neural networks, trained on 400 and 200 episodes per epoch, respectively.The baseline agent chooses actions randomly at every time step.
- Ant: Ant uses a Soft Actor-Critic planning agent with a two-hidden-layer neural network, trained for 30 episodes of 5000-step roll-outs.The mixed policy is evaluated over 10 trials of T = 10000 steps after each epoch to estimate its policy distribution and compute the next reward function.