In standard sequential decision-making, an agent aims to maximize an expected cumulative reward over time. When the environment is modeled as a Markov Decision Process (MDP), this problem is elegantly solved using dynamic programming and the Bellman optimality principle. The core assumption of the Bellman equation is local: the optimal action from any given state depends solely on that state, allowing us to break a long-horizon problem into recursive, step-by-step subproblems.
However, real-world deployment introduces a fundamental tension. What if the agent must maximize rewards while guaranteeing it will not run out of fuel, violate safety thresholds, or exceed a strict risk budget?
When we introduce these global constraints, the foundational assumption of dynamic programming shatters. If an agent has a hard resource constraint—such as limited battery life, as explored by Dmitri A. Dolgov et al.—the optimal action at a specific state is no longer local. It depends heavily on the agent's history—specifically, how much budget has already been consumed. Tracking this remaining budget forces an explosion of the state space, rendering standard recursive solutions intractable.
To solve Constrained Markov Decision Processes (CMDPs) efficiently, we must shift our perspective entirely: away from recursive value functions, and toward global occupancy measures optimized via Linear Programming (LP).
The Shift to Occupancy Measures
Instead of tracking the remaining budget dynamically at every step, we can look at the agent's behavior globally across the entire time horizon. We do this by defining an occupancy measure (also known as an occupation measure or flow distribution).
Intuitively, the occupancy measure $\mu(s, a)$ represents the total discounted time or long-run frequency that an agent spends in a specific state-action pair $(s, a)$ under a given policy.
This shift changes everything because expectation is a linear operator. If we know how often an agent visits each state-action pair, calculating the total expected reward becomes a simple linear combination:
$$\text{Expected Reward} = \sum_{s, a} \mu(s, a) R(s, a)$$
Crucially, global constraints—such as safety budgets, operational costs, or risk limits—can also be expressed as linear combinations of these exact same occupancy measures:
$$\text{Expected Cost} = \sum_{s, a} \mu(s, a) C(s, a) \le \beta$$
As Krishna C. Kalagarla et al. and Andreas Schlaginhaufen et al. demonstrate, formulating the problem around occupancy measures allows the direct integration of global constraints that are otherwise fundamentally incompatible with standard recursive optimization. By placing linear bounds directly on the occupancy distribution, we bypass the need to expand the state space.
The Geometry of Flow Conservation
For this formulation to work, the occupancy measures cannot be arbitrary numbers; they must correspond to a valid, physically realizable policy within the environment's transition dynamics. This validity is enforced through flow conservation equations.
Think of the agent's trajectory as a fluid flowing through a network of states. For every state $s$, the total fluid leaving that state (the sum of $\mu(s, a)$ across all actions) must equal the total fluid entering it. The entering fluid consists of two parts: the initial state distribution and the fluid transitioning into $s$ from other states $s'$ via actions $a'$.
Rafal Wisniewski et al. show how these evolution equations map state occupation measures directly to hitting probabilities. By combining these flow conservation rules with our safety constraints, the entire sequential decision problem consolidates into a single, static Linear Program:
$$\begin{aligned} \max_{\mu \ge 0} \quad & \sum_{s, a} \mu(s, a) R(s, a) \\ \text{subject to} \quad & \sum_{a} \mu(s, a) = \rho_0(s) + \gamma \sum_{s', a'} \mu(s', a') P(s \mid s', a') \quad \forall s \\ & \sum_{s, a} \mu(s, a) C(s, a) \le \beta \end{aligned}$$
Geometrically, the flow conservation equations define a convex polytope of all valid occupancy measures. The safety constraints act as linear hyperplanes that slice through this polytope, isolating a safe sub-region. Finding the optimal policy simply means finding the point within this restricted polytope that pushes furthest in the direction of the reward vector.
Valid Occupancy Polytope
+--------------------+
| / |
| / | <- Safety Constraint Slices Polytope
| / Optimal |
| / Safe Point |
| / * |
| / |
+--------------------+
Unsafe Region
Once the optimal occupancy measure $\mu^*(s, a)$ is found using standard polynomial-time LP solvers, the optimal policy $\pi^*$ is recovered by normalizing the flow at each state:
$$\pi^*(a \mid s) = \frac{\mu^*(s, a)}{\sum_{a'} \mu^*(s, a')}$$
This geometric perspective reveals a key property of constrained optimal control: the optimal solution often lands exactly on the boundary created by the safety hyperplanes. As a result, as Guangyao Shi et al. point out, the derived policies naturally utilize randomized actions at the boundaries of safety constraints to perfectly balance risk tolerances against reward maximization.
Optimizing for Complex Risk and Multi-Metric Objectives
The true power of the linear programming framework lies in its flexibility. Because the underlying optimization space is a convex polytope defined by occupancy measures, we can layer on multiple, heterogeneous constraints without altering the core solution mechanism.
Multi-Objective and Chance Constraints
Often, an agent must balance average performance with strict probabilistic guarantees—such as ensuring the probability of failure remains below a threshold. Zuzana Komárková et al. demonstrate that maximizing expected rewards while simultaneously satisfying multiple probabilistic satisfaction constraints can be elegantly encoded within a single unified LP. This allows the framework to capture intricate trade-offs between average-case performance and worst-case safety boundaries.
Tail-Risk and Conditional Value-at-Risk (CVaR)
In high-stakes environments, minimizing expected cost is insufficient if the tail-end risk involves catastrophic failure. To protect against these low-probability, high-severity events, the framework can incorporate Conditional Value-at-Risk (CVaR). Tobias Meggendorfer et al. show that LP formulations can characterize the flow of a control strategy to simultaneously satisfy expectations, Value-at-Risk (VaR), and tail-risk. In the context of imitation learning, Daniel S. Brown et al. leverage this capability to transform risk-aware policy derivation into a standard convex optimization task, balancing expected returns with tail-end risks when the true reward function is uncertain.
Stochastic Dominance
For the most comprehensive risk management, an agent might require its reward distribution to stochastically dominate a baseline target distribution. William B. Haskell et al. prove that even these infinite-dimensional stochastic dominance constraints can be reformulated as linear programs via occupation measures, making risk-averse decision-making over entire reward distributions computationally tractable.
Scaling to Large Spaces and Partial Observability
While the global LP approach is highly efficient for discrete, fully observable environments, solving a global linear program becomes challenging when the state space is massive or when states are only partially observable (POMDPs). To handle these complexities, the core LP mechanism is adapted into local, heuristic, or structural approximations.
- Local LP Optimization: Rather than solving an LP over an intractable global state space, algorithms can solve localized linear programs on the fly. For instance, Krishnendu Chatterjee et al. and Krishnendu Chatterjee et al. demonstrate that action selection can be performed by solving a local LP over a sampled Monte Carlo Tree Search subtree. This allows an agent to dynamically compute a randomized action distribution that maximizes immediate rewards while ensuring the estimated risk remains within a specified budget.
- Admissible Heuristics and Bounds: Linear programming can also provide structural bounds to guide search algorithms. Dileep George et al. derive a concave LP formulation that provides a tractable upper bound on the optimal expected reward, serving as an admissible heuristic for planning in complex, factored environments. When actions have temporal duration, Majid Khonji et al. extend this to an Integer Linear Programming (ILP) framework to handle chance constraints alongside durative actions in POMDPs.
- Distributional and Contextual Simplifications: In some scenarios, the focus shifts from individual trajectories to the safety of the entire state distribution. S. Akshay et al. show that verifying "existential safety"—determining if a state distribution can be guided to remain within a safe region—can be solved in polynomial time via a system of linear inequalities. Similarly, in multi-armed bandit settings, Ahmed Ben Yahmed et al. utilize an LP framework to optimize expected rewards subject to global aggregated revenue constraints across varying contexts.
By translating sequential, history-dependent safety budgets into static, geometric constraints on occupancy flow, linear programming provides a mathematically rigorous and computationally efficient foundation for risk-aware artificial intelligence.
Key Foundational Work
Stochastic Dominance-Constrained Markov Decision Processes (2013) — contributed 2 concept elements to this direction.
Approximating Optimal Policies for Agents with Limited Execution Resources (2003) — contributed 1 concept elements to this direction.