Dynamic Regret of Policy Optimization in Non-stationary Environments
  We consider reinforcement learning (RL) in episodic MDPs with adversarial
full-information reward feedback and unknown fixed transition kernels. We
propose two model-free policy optimization algorithms, POWER and POWER++, and
establish guarantees for their dynamic regret. Compared with the classical
notion of static regret, dynamic regret is a stronger notion as it explicitly
accounts for the non-stationarity of environments. The dynamic regret attained
by the proposed algorithms interpolates between different regimes of
non-stationarity, and moreover satisfies a notion of adaptive
(near-)optimality, in the sense that it matches the (near-)optimal static
regret under slow-changing environments. The dynamic regret bound features two
components, one arising from exploration, which deals with the uncertainty of
transition kernels, and the other arising from adaptation, which deals with
non-stationary environments. Specifically, we show that POWER++ improves over
POWER on the second component of the dynamic regret by actively adapting to
non-stationarity through prediction. To the best of our knowledge, our work is
the first dynamic regret analysis of model-free RL algorithms in non-stationary
environments.
