mlsanityData to 14 Oct 2026

Efficient Learning in Non-Stationary Linear Markov Decision Processes

arXiv 2010.12870 ↗First posted 24 Oct 2020cs.LG stat.MLcited by 26

Not on the map. Why?

Abstract (arXiv)

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 widetildeO(d5/4H2 Delta1/4 K3/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.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). First posted on arXiv 24 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 4; 2023: 8; 2024: 4; 2025: 1; 2026: 3.

26 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  4. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  5. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  6. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  7. 2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
  8. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  9. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  10. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  11. 2024Jointly Training and Pruning CNNs via Learnable Agent Guidance and Alignmentcited by 9
  12. 2023The complexity of non-stationary reinforcement learningcited by 7
14 more
  1. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  2. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 6
  3. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  4. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  5. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  6. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4
  7. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  8. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  9. 2023MNL-Bandit in non-stationary environmentscited by 1
  10. 2023Revisiting Weighted Strategy for Non-stationary Parametric Banditscited by 0
  11. 2023Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Banditscited by 0
  12. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  13. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  14. 2026Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Correctionscited by 0