Technical Summary: Utility-Constrained Policy Optimization

Problem Definition

The paper addresses the limitations of Constrained Markov Decision Processes (CMDPs) in Reinforcement Learning (RL). While CMDPs are the standard framework for incorporating safety constraints, they enforce risk-neutral constraints, meaning constraints are only satisfied in expectation. This risk-neutrality permits optimal policies that occasionally incur catastrophic constraint violations as long as they are infrequent, leading to unreliable behavior. Conversely, overly conservative policies may be adopted to avoid these rare violations.

Prior attempts to address risk sensitivity (e.g., via chance constraints or CVaR) often result in policies that are history-dependent and intractable to learn, or they rely on ad-hoc modifications like early termination or penalty schedules without a unified theoretical framework. The authors propose Utility-Constrained MDPs (UCMDPs) as the natural framework for risk-sensitive constraints but note that practical solutions for UCMDPs have historically been lacking due to the intractability of optimal history-dependent policies.

Methodology: Utility-Constrained Policies (UCP)

The authors introduce Utility-Constrained Policies (UCP), a practical Lagrangian deep RL algorithm designed to solve UCMDPs. The methodology relies on three core components:

1. Stock-Augmented Formulation

To make UCMDPs solvable with Markov policies, the authors adopt a stock-augmented state formulation, building on the work of Ávila Pires et al. [2025].

• Stock ($Z_t$): A cumulative variable tracking the history of rewards/costs. Unlike previous formulations that used discounted stock, UCP employs an undiscounted stock defined as $Z_{t+1} = Z_t + R_{t+1}$.
• Rationale: The undiscounted stock aligns the agent's internal state with the standard evaluation metric of cumulative episode cost. It prevents the exponential inflation of early costs seen in reverse-discounted updates, making the learning problem more stable.
• Policy Input: The constraint limits are encoded as the initial stock value ($Z_0$). Consequently, the policy $\pi(a|s, z)$ takes the initial stock (and thus the constraint budget) as an input alongside the environment state. This allows the same trained policy to operate under different constraint limits without retraining.

2. Algorithmic Architecture (Lagrangian Actor-Critic)

UCP utilizes a primal-dual actor-critic approach to solve the constrained optimization problem:
$$\inf_{\lambda_z \ge 0} \sup_{\pi} \left( \mathbb{E}[f(Z_0 + G^\pi_0)] - \lambda_z \mathbb{E}[g(Z_0 + G^\pi_0)] \right)$$
Where $f$ is the objective utility and $g$ is the constraint utility.

• Critic: The agent uses a distributional critic (specifically using quantile regression) to estimate the full distribution of returns (cumulants), rather than just the expected value. This is essential for evaluating utility functions that are non-linear (risk-sensitive).
• Actor: The actor is trained to maximize the expected utility of the return distribution, rather than the standard Q-value. The objective function for the actor is modified from standard Soft Actor-Critic (SAC) to:
  $$L^{UO}_{actor} = \mathbb{E}[u(z + G_\psi(s, z, A_\theta))] - \alpha \log \pi_\theta(A_\theta|s, z)$$
  where $u(x) = f(x) - \lambda_z g(x)$.
• Lagrange Multiplier Update: The multiplier $\lambda_z$ is updated periodically based on the observed constraint violation over episodes, using a tolerance $\epsilon$ to handle cases where strict feasibility is difficult.

3. Training Strategy: Stock Randomization

To enable generalization across different constraint budgets, the initial stock $Z_0$ is sampled uniformly at random from a range of values during training (e.g., $[-30, 0]$). This forces the policy to learn a mapping from various budget levels to optimal actions, allowing the agent to adapt to new budgets at test time without retraining.

Key Contributions

1. Practical UCMDP Solution: The paper introduces a modification to UCMDPs that supports optimal Markov policies via stock augmentation, making the problem practically solvable.
2. UCP Algorithm: The proposal of UCP, a Lagrangian deep RL agent that combines distributional critics, stock-augmented states, and expected utility optimization.
3. Flexible Constraint Limits: The framework allows constraint limits to be set after training by varying the initial stock input, eliminating the need for retraining when safety budgets change.
4. Empirical Validation: Extensive evaluation on the Safety Gymnasium benchmark demonstrating that UCP matches or outperforms existing baselines.

Experimental Results

The authors evaluated UCP on the Safety Gymnasium benchmark, specifically the Safety Velocity and Safety Navigation task suites.

• Performance vs. Baselines: UCP consistently matches or outperforms state-of-the-art baselines (including PPO-Lag, SAC-Lag, PID-Lag, Sauté RL, and Early Terminated MDPs).
  • In Safety Velocity tasks, UCP achieves comparable or higher returns while satisfying cost constraints.
  • In Safety Navigation tasks, UCP significantly outperforms all baselines in terms of return while maintaining safety.
• Risk Sensitivity: Compared to a risk-neutral variant, the risk-sensitive UCP significantly reduces the "tail" of the cost distribution. It minimizes the probability of exceeding the cost budget and reduces the expected excess cost ($\mathbb{E}[\max(X, b)]$) to near zero, whereas risk-neutral methods often incur costs significantly higher than the budget in violation episodes.
• Generalization: The ablation study confirms that stock randomization is critical. Policies trained with random initial stocks can generalize to unseen budget levels (e.g., budgets of 0, 5, 15, 25) without retraining, whereas policies trained on a single budget level cannot.
• Undiscounted Stock: The use of undiscounted stock was found to be superior to discounted stock, leading to better performance and stability.

Significance and Claims

The paper claims that UCP provides a simple yet powerful methodology for constrained RL that overcomes the risk-neutrality of standard CMDPs. By incorporating risk-sensitive constraints directly into the problem formulation via utility functions and stock augmentation, the authors demonstrate that:

1. Safety and Performance can be balanced: Stricter, risk-sensitive constraints can lead to improved performance even under risk-neutral evaluation metrics, likely by preventing catastrophic failures that force overly conservative behavior.
2. Operational Flexibility: The ability to adjust constraint limits post-training without retraining offers significant practical value for real-world deployment where safety budgets may vary.
3. Distributional Necessity: The results highlight the importance of modeling return distributions (via distributional critics) rather than just expectations when dealing with non-linear utility constraints.

The authors acknowledge that while empirical results are strong, the work lacks a complete theoretical analysis regarding the optimality guarantees of Lagrangian dynamic programming in UCMDPs and the principled justification for using undiscounted stock, identifying these as areas for future theoretical work.