Provably Efficient Maximum Entropy Exploration
  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.
