Markov Decision Processes with Long-Term Average Constraints
Not on the map. Why?
Abstract (arXiv)
We consider the problem of constrained Markov Decision Process (CMDP) where an agent interacts with a unichain Markov Decision Process. At every interaction, the agent obtains a reward. Further, there are K cost functions. The agent aims to maximize the long-term average reward while simultaneously keeping the K long-term average costs lower than a certain threshold. In this paper, we propose CMDP-PSRL, a posterior sampling based algorithm using which the agent can learn optimal policies to interact with the CMDP. Further, for MDP with S states, A actions, and diameter D, we prove that following CMDP-PSRL algorithm, the agent can bound the regret of not accumulating rewards from optimal policy by TildeO(poly(DSA)√T). Further, we show that the violations for any of the K constraints is also bounded by TildeO(poly(DSA)√T). To the best of our knowledge, this is the first work which obtains a TildeO(√T) regret bounds for ergodic MDPs with long-term average constraints.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 12 of its 30 references that are in the map. First posted on arXiv 12 Jun 2021.
Builds on
12 of 30 references.
References · 12
- 2015End-to-End Training of Deep Visuomotor Policiescited by 875
- 2018Is Q-learning Provably Efficient?cited by 487
- 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
- 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
- 2020Exploration-Exploitation in Constrained MDPscited by 149
- 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
- 2020Constrained Upper Confidence Reinforcement Learningcited by 46
- 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
- 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
- 2019Variational Regret Bounds for Reinforcement Learningcited by 32
- 2019Active Exploration in Markov Decision Processescited by 27
- 2020Learning in Markov Decision Processes under Constraintscited by 20
Built on by
Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 0; 2026: 1.
3 papers.