Abstract:
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.
