  In online reinforcement learning (RL), efficient exploration remains
particularly challenging in high-dimensional environments with sparse rewards.
In low-dimensional environments, where tabular parameterization is possible,
count-based upper confidence bound (UCB) exploration methods achieve minimax
near-optimal rates. However, it remains unclear how to efficiently implement
UCB in realistic RL tasks that involve non-linear function approximation. To
address this, we propose a new exploration approach via \textit{maximizing} the
deviation of the occupancy of the next policy from the explored regions. We add
this term as an adaptive regularizer to the standard RL objective to balance
exploration vs. exploitation. We pair the new objective with a provably
convergent algorithm, giving rise to a new intrinsic reward that adjusts
existing bonuses. The proposed intrinsic reward is easy to implement and
combine with other existing RL algorithms to conduct exploration. As a proof of
concept, we evaluate the new intrinsic reward on tabular examples across a
variety of model-based and model-free algorithms, showing improvements over
count-only exploration strategies. When tested on navigation and locomotion
tasks from MiniGrid and DeepMind Control Suite benchmarks, our approach
significantly improves sample efficiency over state-of-the-art methods. Our
code is available at https://github.com/tianjunz/MADE.
