Efficient Policy Learning for Non-Stationary MDPs under Adversarial
  Manipulation
  A Markov Decision Process (MDP) is a popular model for reinforcement
learning. However, its commonly used assumption of stationary dynamics and
rewards is too stringent and fails to hold in adversarial, nonstationary, or
multi-agent problems. We study an episodic setting where the parameters of an
MDP can differ across episodes. We learn a reliable policy of this potentially
adversarial MDP by developing an Adversarial Reinforcement Learning (ARL)
algorithm that reduces our MDP to a sequence of \emph{adversarial} bandit
problems. ARL achieves $O(\sqrt{SATH^3})$ regret, which is optimal with respect
to $S$, $A$, and $T$, and its dependence on $H$ is the best (even for the usual
stationary MDP) among existing model-free methods.
