Provably Efficient Model-Free Algorithms for Non-stationary CMDPs

Honghao Wei, Arnob Ghosh, Ness Shroff, Lei Ying, Xingyu Zhou

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


We study model-free reinforcement learning (RL) algorithms in episodic non-stationary constrained Markov Decision Processes (CMDPs), in which an agent aims to maximize the expected cumulative reward subject to a cumulative constraint on the expected utility (cost). In the non-stationary environment, reward, utility functions, and transition kernels can vary arbitrarily over time as long as the cumulative variations do not exceed certain variation budgets. We propose the first model-free, simulator-free RL algorithms with sublinear regret and zero constraint violation for non-stationary CMDPs in both tabular and linear function approximation settings with provable performance guarantees. Our results on regret bound and constraint violation for the tabular case match the corresponding best results for stationary CMDPs when the total budget is known. Additionally, we present a general framework for addressing the well-known challenges associated with analyzing non-stationary CMDPs, without requiring prior knowledge of the variation budget. We apply the approach for both tabular and linear approximation settings.

Original languageEnglish (US)
Pages (from-to)6527-6570
Number of pages44
JournalProceedings of Machine Learning Research
StatePublished - 2023
Externally publishedYes
Event26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain
Duration: Apr 25 2023Apr 27 2023

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Provably Efficient Model-Free Algorithms for Non-stationary CMDPs'. Together they form a unique fingerprint.

Cite this