mlsanityData to 14 Oct 2026

Provably Efficient Algorithm for Nonstationary Low-Rank MDPs

arXiv 2308.05471 ↗First posted 10 Aug 2023cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) under changing environment models many real-world applications via nonstationary Markov Decision Processes (MDPs), and hence gains considerable interest. However, theoretical studies on nonstationary MDPs in the literature have mainly focused on tabular and linear (mixture) MDPs, which do not capture the nature of unknown representation in deep RL. In this paper, we make the first effort to investigate nonstationary RL under episodic low-rank MDPs, where both transition kernels and rewards may vary over time, and the low-rank model contains unknown representation in addition to the linear state embedding function. We first propose a parameter-dependent policy optimization algorithm called PORTAL, and further improve PORTAL to its parameter-free version of Ada-PORTAL, which is able to tune its hyper-parameters adaptively without any prior knowledge of nonstationarity. For both algorithms, we provide upper bounds on the average dynamic suboptimality gap, which show that as long as the nonstationarity is not significantly large, PORTAL and Ada-PORTAL are sample-efficient and can achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 30 of its 41 references that are in the map. First posted on arXiv 10 Aug 2023.

Builds on

30 of 41 references.

References · 30

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2016End to End Learning for Self-Driving Carscited by 1,009
  3. 2015End-to-End Training of Deep Visuomotor Policiescited by 875
  4. 2019Introduction to Online Convex Optimizationcited by 803
  5. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  6. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  11. 2013Non-stationary Stochastic Optimizationcited by 175
  12. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
18 more
  1. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  6. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  7. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  8. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  9. 2019DEAR: Deep Reinforcement Learning for Online Advertising Impression in Recommender Systemscited by 44
  10. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  11. 2020Reinforcement Learning for Autonomous Driving with Latent State Inference and Spatial-Temporal Relationshipscited by 37
  12. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 33
  13. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 30
  14. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  15. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  16. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  17. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  18. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 1.

2 papers.

  1. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  2. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0