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 \(\widetilde\{\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

Stats

• citations7
• S2 citations—
• github stars0
• HF likes0
• heat score6.77
• arxiv keytouati2020efficient

Related papers

• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00
• Online Sparse Reinforcement Learning (2020)0.00
• Efficient Policy Learning For Non-stationary Mdps Under Adversarial Manipulation (2019)0.00
• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00
• Near-optimal Policy Optimization Algorithms For Learning Adversarial Linear Mixture Mdps (2021)0.00
• Optimistic Policy Optimization Is Provably Efficient In Non-stationary Mdps (2021)0.00