  We investigate online Markov Decision Processes (MDPs) with adversarially
changing loss functions and known transitions. We choose dynamic regret as the
performance measure, defined as the performance difference between the learner
and any sequence of feasible changing policies. The measure is strictly
stronger than the standard static regret that benchmarks the learner's
performance with a fixed compared policy. We consider three foundational models
of online MDPs, including episodic loop-free Stochastic Shortest Path (SSP),
episodic SSP, and infinite-horizon MDPs. For these three models, we propose
novel online ensemble algorithms and establish their dynamic regret guarantees
respectively, in which the results for episodic (loop-free) SSP are provably
minimax optimal in terms of time horizon and certain non-stationarity measure.
Furthermore, when the online environments encountered by the learner are
predictable, we design improved algorithms and achieve better dynamic regret
bounds for the episodic (loop-free) SSP; and moreover, we demonstrate
impossibility results for the infinite-horizon MDPs.
