Efficient Learning in Non-Stationary Linear Markov Decision Processes

Abstract

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 $\tilde{\mathcal{O}}(d^{5/4}{H}^2{\Delta }^{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 $\Delta$ 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.

References in corpus (4)

• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• A Simple Approach for Non-stationary Linear Bandits
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Nonstationary Reinforcement Learning with Linear Function Approximation

Cited by in corpus (4)

• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Regret Bounds for Generalized Linear Bandits under Parameter Drift