Constrained reinforcement learning

Overview

A constrained Markov decision process keeps the usual reward and adds a cost signal with a limit. The learner maximises the expected discounted reward J_r while keeping the expected discounted cost J_c at or below a limit ξ 2508.04811 §3.1 2508.04811 eq. 9.

The standard handle is a Lagrangian, L(θ, λ) = J_r − λ(J_c − ξ), with λ ≥ 0. The policy ascends L in θ, while λ is raised when the cost is over its limit and lowered when it is under 2508.04811 eq. 10 2508.04811 §3.2. The two updates alternate until both settle 2508.04811 eq. 11–2508.04811 eq. 13.

This page rests on one card. The other methods the card compares against (CPO, Lag-TRPO and the multi-agent baselines) have no card here, so they are named below but not described.

Variants

Lagrangian actor with reward and cost critics (Habic)

The card's method, Habic, treats ride-hailing dispatch as a constrained MDP. Each driver is an agent. Training is centralised and execution is decentralised 2508.04811 §3.1. The reward mixes a wait-time term with a fairness term weighted by α 2508.04811 eq. 6. The cost is incurred when a dispatch ends in a region the driver does not prefer, with a limit of 15% in the study 2508.04811 §4.2.3.

The policy is one shared network that scores a short list of candidate drivers for each order, and a softmax over the scores gives the choice probabilities 2508.04811 eq. 14 2508.04811 §3.3.2. It is trained with a PPO-clip objective whose direction for θ is the reward gradient minus λ times the cost gradient 2508.04811 eq. 15. Two critics estimate reward and cost separately, and λ takes a projected step 2508.04811 §3.3.3 2508.04811 eq. 16. Card: HCRide.

Reported results are the authors' own, on a simulator built from two ride-hailing datasets 2508.04811 §4.1. On the NYC setting, the introduction gives gains over Lag-TRPO of 2.02% on efficiency and 10.21% on driver preference 2508.04811 §1. The full table includes CPO and Lag-TRPO as baselines. The method is bold on every NYC metric, and on every Shenzhen metric except driver preference, where a sibling variant is higher 2508.04811 tab. 1. The table's caption conflicts with its values (see Contradictions).

Other variants

No second card lists this concept yet. Methods named as baselines in the card (CPO, Lag-TRPO) are not described on this page.

When to use which

Implementation sketch

One outer iteration of the Lagrangian update. Steps follow the card's equations; the multiplier step uses the sign that raises λ when the cost estimate exceeds the limit.

# One outer iteration of a Lagrangian constrained policy update  [§3.2]
# theta: policy parameters; lam: multiplier kept >= 0; xi: cost limit
def constrained_update(theta, lam, batch, xi, lr_theta, lr_lam):
    # Estimate reward return and cost return on the same batch  [§3.3.3]
    J_r = estimate_reward_return(batch)
    J_c = estimate_cost_return(batch)
    # Ascend the Lagrangian in theta: reward gradient minus lam times cost  [eq. 15]
    grad = grad_reward(theta, batch) - lam * grad_cost(theta, batch)
    theta = theta + lr_theta * grad
    # Projected step on lam: raise it while the cost is over the limit  [eq. 16]
    lam = max(0.0, lam + lr_lam * (J_c - xi))
    return theta, lam

Contradictions

• Paper vs its released code. The paper's θ update includes the cost gradient 2508.04811 eq. 15. The card records that the released actor loss uses only the reward surrogate, and that the code's constraint quantity is an advantage-based estimate rather than the cost return in eq. 9 [see card: Paper vs code, items 5–6]. The two sides are not reconciled here.
• Table 1 caption vs its values. The caption says lower values are better, while the bold marks and the text treat higher as better 2508.04811 tab. 1 2508.04811 §4.2.3. Read each column by its own numbers.
• Discount factors. The paper defines separate γ_r and γ_c 2508.04811 §3.1. The released code uses one value for both [see card: Paper vs code, item 9].

Papers

• HCRide: a constrained-MDP ride-hailing dispatcher (Habic) with a driver-preference cost limit; author-reported gains on its own simulator.