Efficient Learning in Non-Stationary Linear Markov Decision Processes
This addresses the challenge of learning in changing environments for reinforcement learning practitioners, though it is incremental as it builds on prior work in non-stationary linear bandits.
The paper tackles the problem of episodic reinforcement learning in non-stationary linear Markov Decision Processes, where rewards and transitions evolve over time, and proposes OPT-WLSVI, an optimistic model-free algorithm that achieves a regret bound of O~(d^{5/4}H^2 Δ^{1/4} K^{3/4}).
We study episodic reinforcement learning in non-stationary linear (a.k.a. low-rank) Markov Decision Processes (MDPs), i.e, both the reward and transition kernel are linear with respect to a given feature map and are allowed to evolve either slowly or abruptly over time. For this problem setting, we propose OPT-WLSVI an optimistic model-free algorithm based on weighted least squares value iteration which uses exponential weights to smoothly forget data that are far in the past. We show that our algorithm, when competing against the best policy at each time, achieves a regret that is upper bounded by $\widetilde{\mathcal{O}}(d^{5/4}H^2 Δ^{1/4} K^{3/4})$ where $d$ is the dimension of the feature space, $H$ is the planning horizon, $K$ is the number of episodes and $Δ$ is a suitable measure of non-stationarity of the MDP. Moreover, we point out technical gaps in the study of forgetting strategies in non-stationary linear bandits setting made by previous works and we propose a fix to their regret analysis.