Constrained Markov Decision Processes

By Eitan Altman. 1999

INTRODUCTION Examples of Constrained Dynamic Control Problems On Solution Approaches for CMDPs with Expected Costs Other Types of CMDPs Cost Criteria and Assumptions The Convex Analytical Approach and Occupation Measures Linear Programming and Lagrangian Approach for CMDPs About the Methodology The Structure of the Book PART ONE: FINITE MDPS MARKOV DECISION PROCESSES The Model Cost Criteria and the Constrained Problem Some Notation The Dominance of Markov Policies THE DISCOUNTED COST Occupation Measure and the Primal LP Dynamic Programming and Dual LP: the Unconstrained Case Constrained Control: Lagrangian Approach The Dual LP Number of Randomizations THE EXPECTED AVERAGE COST Occupation Measure and the Primal LP Equivalent Linear Program The Dual Program Number of Randomizations FLOW AND SERVICE CONTROL IN A SINGLE-SERVER QUEUE The Model The Lagrangian The Original Constrained Problem Structure of Randomization and Implementation Issues On Coordination Between Controllers Open Questions PART TWO: INFINITE MDPS MDPS WITH INFINITE STATE AND ACTION SPACES The Model Cost Criteria Mixed Policies, and Topologic Structures The Dominance of Markov Policies Aggregation of States Extra Randomization in the Policies Equivalent Quasi-Markov Model and Quasi-Markov Policies THE TOTAL COST: CLASSIFICATION OF MDPS Transient and Absorbing MDPs MDPs With Uniform Lyapunov Functions Equivalence of MDP With Unbounded and bounded costs Properties of MDPs With Uniform Lyapunov Functions Properties for Fixed Initial Distribution Examples of Uniform Lyapunov Functions Contracting MDPs THE TOTAL COST: OCCUPATION MEASURES AND THE PRIMAL LP Occupation Measure Continuity of Occupation Measures More Properties of MDPs Characterization of Achievable Sets of Occupation Measure Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program THE TOTAL COST: DYNAMIC AND LINEAR PROGRAMMING Non-Constrained Control: Dynamic and Linear Programming Superharmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP State Truncation A Second LP Approach for Optimal Mixed Policies More on Unbound Costs THE DISCOUNTED COST The Equivalent Total Cost Model Occupation Measure and LP Non-negative Immediate Cost Weak Contracting Assumptions and Lyapunov Functions Example: Flow and Service Control THE EXPECTED AVERAGE COST Occupation Measures Completeness Properties of Stationary Policies Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program The Contracting Framework Other Conditions for the Uniform Integrability The Case of Uniform Lyapunov Conditions EXPECTED AVERAGE COST: DYNAMIC PROGRAMMING AND LP The Non-Constrained Case: Optimality Inequality Non-Constrained Control: Cost Bounded Below Dynamic Programming and Uniform Lyapunov Function Super-Harmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP A Second LP Approach for Optimal Mixed Policies PART THREE: ASYMPTOTIC METHODS AND APPROXIMATIONS SENSITIVITY ANALYSIS Introduction Approximation of the Values Approximation and Robustness of the Policies CONVERGENCE OF DISCOUNTED CONSTRAINED MDPS Convergence in the Discount Factor Convergence to the Expected Average Cost The Case of Uniform Lyapunov Function CONVERGENCE AS THE HORIZON TENDS TO INFINITY The Discounted Cost The Expected Average Cost: Stationary Policies The Expected Average Cost: General Policies STATE TRUNCATION AND APPROXIMATION The Approximating sets of States Scheme I: the Total Cost Scheme II: the Total Cost Scheme III: the Total Cost The Expected Average Cost Infinite MDPs: on the Number of Randomizations APPENDIX: CONVERGENCE OF PROBABILITY MEASURES REFERENCES LIST OF SYMBOLS AND NOTATION INDEX

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Constrained Policy Optimization (2017, background): “A standard and well-studied formulation for reinforcement learning with constraints is the constrained Markov Decision Process (CMDP) framework (Altman, 1999), where agents must satisfy constraints on expectations of auxil-liary costs.”
Safe Policy Improvement with Baseline Bootstrapping (2017, background): “…is an overloaded term, as it may be considered with respect to parametric uncertainty (Thomas et al., 2015a; Petrik et al., 2016), internal uncertainty (Altman, 1999; Carrara et al., 2019), interruptibility (Orseau & Armstrong, 2016; Guer-raoui et al., 2017), or as exploration in a hazardous…”
Safe Exploration in Markov Decision Processes (2012, background): “In general, it is NP-hard to decide whether there exist δ -safe policies with respect to a home state, s 0 , and a stopping time, T , for some belief, β .”
Challenges of Real-World Reinforcement Learning (2019, background): “Recent work in RL safety (Dalal et al., 2018; Achiam et al., 2017) has cast safety in the context of Constrained MDPs (CMDPs) (Altman, 1999), and we will concentrate on pre-deﬁned constraints on the environment in this context.”
Exact finite approximations of average-cost countable Markov decision processes (2007, neutral): “We now outline the extension to constrained MDPs, where a detailed description of the model may be found in [A2].”
Recovery RL: Safe Reinforcement Learning With Learned Recovery Zones (2020, methodology): “This setting exactly corresponds to the CMDP formulation from [3], but with constraint costs limited to binary indicator functions for constraint violating states.”
A Review of Safe Reinforcement Learning: Methods, Theories, and Applications (2024, unknown): “A CMDP problem [77] is an extension of a standard Markov decision process (MDP) M with a constraint set C .”
Safe RLHF: Safe Reinforcement Learning from Human Feedback (2023, unknown): “Then, the primary objective of reinforcement learning is to maximize the objective function, Safe RL is formulated as a Constrained MDP (CMDP) extending the standard MDP M with an additional constraint set C (Altman, 2021).”
The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate (2011, background): “Let P π ∈ I R m×m be the column stochastic matrix corresponding to a policy π, that is, the ith column of P π be the probability distribution p πi (i, i ), i = 1, · · · , m. * ≤ c π , ∀π, (2) where the ith entry of vector c π ∈ I R m equals the expected immediate cost i p πi (i, i )c πi (i, i ) for ”
Mean-Variance Optimization in Markov Decision Processes (2011, methodology): “Nevertheless, E[W (2)] and E[W ] are linear functions, and as such can be addressed simultaneously using methods from multicriteria or constrained Markov decision processes (Altman, 1999).”
Projection-Based Constrained Policy Optimization (2020, methodology): “We define CMDP as the tuple < S,A, T,R,C >, where S is the set of states, A is the set of actions that the agent can take, T : S ×A×S → [0, 1] is the transition probability of the CMDP, R : S ×A → R is the reward function, and C : S × A → R is the cost function.”
Approximate dynamic programming via iterated Bellman inequalities (2015, background): “In fact, in certain special cases, the Bellman inequality approach can also be interpreted as a simple application of Lagrange duality [35].”
Reinforcement Learning with Trajectory Feedback (2020, methodology): “Also, recall that the set of the average occupancy measures, denoted by K(P ), is a convex set (Altman 1999).”
Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, background): “…or penalty functions to integrate the constraints to the reward function [172]; 2) modeling as a chance constraint (i.e., the probability of constraint violation is no larger than a predeﬁned threshold) [173], [174] or a budget constraint (such as the constraint in model (32)) [175], [176].”
Challenges of real-world reinforcement learning: definitions, benchmarks and analysis (2021, background): “Recent work in RL safety (Dalal et al. 2018; Achiam et al. 2017; Tessler et al. 2018; Satija et al. 2020) has cast safety in the context of Constrained MDPs (CMDPs) (Altman 1999), and we will concentrate on pre-defined constraints on the environment in this context.”
Drift rate control of a Brownian processing system (2005, background): “Altman [1] develops a general approach to solving constrained Markov decision problems in a discrete-time framework.”
MuZero with Self-competition for Rate Control in VP9 Video Compression (2022, methodology): “…to obtain a policy which maximizes the expected sum of discounted rewards (JRπ ). max π JRπ (s) := E a∼π,s∼P [∑ t γtR(st, at) ] A Constrained Markov Decision Process (CMDP) [Altman, 1999] extends the MDP formulation by introducing k constraint functions ck : S ×A→ R and corresponding thresholds βk.”