# Learning in Markov Decision Processes under Constraints

arXiv: https://arxiv.org/abs/2002.12435 · HTML: https://mlsanity.com/paper/2002.12435/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2020.

## Built on by (most cited first, 20 of 20)

- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [Provably Safe Reinforcement Learning with Step-wise Violation Constraints](https://mlsanity.com/paper/2302.06064/) (2023)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation](https://mlsanity.com/paper/2301.11547/) (2023)
- [Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time](https://mlsanity.com/paper/2403.15928/) (2024)
- [Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization](https://mlsanity.com/paper/2602.08000/) (2026)
- [Markov Decision Processes with Long-Term Average Constraints](https://mlsanity.com/paper/2106.06680/) (2021)
- [Online Selection of Diverse Committees](https://mlsanity.com/paper/2105.09295/) (2021)
- [Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling](https://mlsanity.com/paper/2405.19017/) (2024)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Logic-informed reinforcement learning for cross-domain optimization of large-scale cyber-physical systems](https://mlsanity.com/paper/2511.00806/) (2025)
- [Provably Safe Reinforcement Learning for Stochastic Reach-Avoid Problems with Entropy Regularization](https://mlsanity.com/paper/2601.08646/) (2026)
- [Multi-Objective Constraint Inference using Inverse reinforcement learning](https://mlsanity.com/paper/2605.06951/) (2026)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## Abstract (arXiv)

We consider reinforcement learning (RL) in Markov Decision Processes in which an agent repeatedly interacts with an environment that is modeled by a controlled Markov process. At each time step t, it earns a reward, and also incurs a cost-vector consisting of M costs. We design model-based RL algorithms that maximize the cumulative reward earned over a time horizon of T time-steps, while simultaneously ensuring that the average values of the M cost expenditures are bounded by agent-specified thresholds cubi,i=1,2,ldots,M. In order to measure the performance of a reinforcement learning algorithm that satisfies the average cost constraints, we define an M+1 dimensional regret vector that is composed of its reward regret, and M cost regrets. The reward regret measures the sub-optimality in the cumulative reward, while the i-th component of the cost regret vector is the difference between its i-th cumulative cost expense and the expected cost expenditures Tcubi. We prove that the expected value of the regret vector of UCRL-CMDP, is upper-bounded as tildeOleft(T2slash 3right), where T is the time horizon. We further show how to reduce the regret of a desired subset of the M costs, at the expense of increasing the regrets of rewards and the remaining costs. To the best of our knowledge, ours is the only work that considers non-episodic RL under average cost constraints, and derive algorithms that can~tune the regret vector according to the agent's requirements on its cost regrets.