Policy Optimization in Adversarial MDPs: Improved Exploration via
  Dilated Bonuses
  Policy optimization is a widely-used method in reinforcement learning. Due to
its local-search nature, however, theoretical guarantees on global optimality
often rely on extra assumptions on the Markov Decision Processes (MDPs) that
bypass the challenge of global exploration. To eliminate the need of such
assumptions, in this work, we develop a general solution that adds dilated
bonuses to the policy update to facilitate global exploration. To showcase the
power and generality of this technique, we apply it to several episodic MDP
settings with adversarial losses and bandit feedback, improving and
generalizing the state-of-the-art. Specifically, in the tabular case, we obtain
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret where $T$ is the number of episodes,
improving the $\widetilde{\mathcal{O}}({T}^{2/3})$ regret bound by Shani et al.
(2020). When the number of states is infinite, under the assumption that the
state-action values are linear in some low-dimensional features, we obtain
$\widetilde{\mathcal{O}}({T}^{2/3})$ regret with the help of a simulator,
matching the result of Neu and Olkhovskaya (2020) while importantly removing
the need of an exploratory policy that their algorithm requires. When a
simulator is unavailable, we further consider a linear MDP setting and obtain
$\widetilde{\mathcal{O}}({T}^{14/15})$ regret, which is the first result for
linear MDPs with adversarial losses and bandit feedback.
