Nonstationary Reinforcement Learning with Linear Function Approximation
  We consider reinforcement learning (RL) in episodic Markov decision processes
(MDPs) with linear function approximation under drifting environment.
Specifically, both the reward and state transition functions can evolve over
time, as long as their respective total variations, quantified by suitable
metrics, do not exceed certain \textit{variation budgets}. We first develop the
$\texttt{LSVI-UCB-Restart}$ algorithm, an optimistic modification of
least-squares value iteration combined with periodic restart, and establish its
dynamic regret bound when variation budgets are known. We then propose a
parameter-free algorithm, $\texttt{Ada-LSVI-UCB-Restart}$, that works without
knowing the variation budgets, but with a slightly worse dynamic regret bound.
We also derive the first minimax dynamic regret lower bound for nonstationary
MDPs to show that our proposed algorithms are near-optimal. As a byproduct, we
establish a minimax regret lower bound for linear MDPs, which is unsolved by
\cite{jin2020provably}. In addition, we provide numerical experiments to
demonstrate the effectiveness of our proposed algorithms. As far as we know,
this is the first dynamic regret analysis in nonstationary reinforcement
learning with function approximation.
