Markov Decision Processes with Long-Term Average Constraints

2021/06/12 by Mridul Agarwal, Agarwal, Mridul, Qinbo Bai +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning and Algorithms #Reinforcement Learning in Robotics #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2106.06680

openalex publication_date 2021/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Constrained Markov Decision Processes
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Active Exploration in Markov Decision Processes
• Exploration-Exploitation in Constrained MDPs
• A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints

Related

• Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints
• Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints
• A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraints
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
• Large Scale Markov Decision Processes with Changing Rewards