  We consider model-free reinforcement learning (RL) in non-stationary Markov
decision processes. Both the reward functions and the state transition
functions are allowed to vary arbitrarily over time as long as their cumulative
variations do not exceed certain variation budgets. We propose Restarted
Q-Learning with Upper Confidence Bounds (RestartQ-UCB), the first model-free
algorithm for non-stationary RL, and show that it outperforms existing
solutions in terms of dynamic regret. Specifically, RestartQ-UCB with
Freedman-type bonus terms achieves a dynamic regret bound of
$\widetilde{O}(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}} H
T^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions,
respectively, $\Delta>0$ is the variation budget, $H$ is the number of time
steps per episode, and $T$ is the total number of time steps. We further
present a parameter-free algorithm named Double-Restart Q-UCB that does not
require prior knowledge of the variation budget. We show that our algorithms
are \emph{nearly optimal} by establishing an information-theoretical lower
bound of $\Omega(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}}
H^{\frac{2}{3}} T^{\frac{2}{3}})$, the first lower bound in non-stationary RL.
Numerical experiments validate the advantages of RestartQ-UCB in terms of both
cumulative rewards and computational efficiency. We demonstrate the power of
our results in examples of multi-agent RL and inventory control across related
products.
