Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints

Jie Fu; Anamika Dubey

eess.SYOct 8, 2026

Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints

Authors: Jie Fu, Anamika Dubey

Organizations: Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL 32611, USA · School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA

Abstract

Consider a finite population of agents with decoupled Markov transition dynamics and empirical-density feedback, subject to the following constraints: with probability at least $1-δ_r$ , at least a fraction $α_r$ of agents must reach a target region at some time $t^*$ , while, at each time up to $t^*$ , the unsafe population fraction must remain below $β_u$ with probability at least $1-δ_u$ . However, standard mean-field methods enforce these constraints only in expectation, which fails to account for stochastic fluctuations at finite fleet size $N$ . To address this control problem, we propagate the second-order moment (variance) of the empirical density alongside the mean-field trajectory via a discrete-time Lyapunov recursion, and apply the Cantelli inequality to convert chance constraints into tractable deterministic conditions on the moments of the empirical density. We then incorporate these moment-based surrogate constraints into a gradient-based sequential convex approximation procedure for density-feedback policy synthesis. We further introduce additional moment-error bounds to construct a rigorous finite- $N$ certificate. The method is evaluated on a gridworld environment and a power-system EV-charging aggregation problem and compared with a standard deterministic population-level LP baseline.

Figures & tables

Fig. 1: The

6\times 6

gridworld environment. Start (red,

S

) at

(5,0)

; wall at

x=2

with three impassable cells (black) and three open gap cells

s_{1},s_{2},s_{3}

(orange) that every route must cross; three reach targets (green,

T

) and one reward-only target (blue,

R

), both past the wall.

	MF-LP (baseline)				SCA (proposed)
$N$	$\hat{J}$	$\hat{P}_{\rm r}$	$\hat{P}_{\rm v}$	emp. met?	$\hat{J}$	$\hat{P}_{\rm r}$	$\hat{P}_{\rm v}$	$r_{m}$ / $a_{m}$
10	9.39	0.91 ✓	0.38 ✓	$\checkmark$	9.38	1.00 ✓	0.40 ✓	$-.108^{\times}/-.194^{\times}$
20	9.38	0.95 ✓	0.39 ✓	$\checkmark$	8.97	1.00 ✓	0.12 ✓	$+.029/+.000$
50	9.37	1.00 ✓	0.44 ×	$\times$	9.23	1.00 ✓	0.08 ✓	$+.000/+.000$
100	9.38	1.00 ✓	0.47 ×	$\times$	9.28	1.00 ✓	0.12 ✓	$+.090/+.000$

TABLE I: Gridworld results.

r_{m}

a_{m}

: surrogate Cantelli margins (

\geq 0

indicates that the surrogate condition is satisfied).

\hat{J}

: empirical mean total reward.

\hat{P}_{\rm r}

: empirical reach probability.

\hat{P}_{\rm v}

: maximum empirical per-cell avoid violation rate. Emp. met? indicates whether both empirical reach and avoid requirements are met.

	MF-LP (baseline)				SCA (proposed)
$N$	$\hat{J}$	$\hat{P}_{\rm r}$	$\hat{P}_{\rm v}$	emp. met?	$\hat{J}$	$\hat{P}_{\rm r}$	$\hat{P}_{\rm v}$	$r_{m}$ / $a_{m}$
20	19.11	1.00 ✓	0.45 ×	$\times$	17.62	1.00 ✓	0.27 ✓	$+.138^{\checkmark}/{-}.134^{\times}$
50	19.09	1.00 ✓	0.49 ×	$\times$	17.56	1.00 ✓	0.06 ✓	$+.196^{\checkmark}/{+}.000^{\checkmark}$
100	19.09	1.00 ✓	0.52 ×	$\times$	17.99	1.00 ✓	0.08 ✓	$+.199^{\checkmark}/{+}.000^{\checkmark}$
200	19.09	1.00 ✓	0.51 ×	$\times$	18.31	1.00 ✓	0.07 ✓	$+.200^{\checkmark}/{+}.000^{\checkmark}$

TABLE II: EV-charging results.

r_{m}

a_{m}

: surrogate Cantelli margins (

\geq 0

indicates that the surrogate condition is satisfied), with

a_{m}

computed using ( 39 ).

\hat{J}

: empirical mean total reward.

\hat{P}_{\rm r}

: empirical reach probability.

\hat{P}_{\rm v}

: maximum empirical per-timestep marginal avoid violation rate. Emp. met? indicates whether both empirical requirements (

\hat{P}_{\rm r}\geq 0.90

and

\hat{P}_{\rm v}\leq 0.30

) are met.

Fig. 2: Aggregate fast-charging, slow-charging, and idle fractions over time (summing to 1 at every

t

), MF-LP’s optimal solution (top) versus the SCA solution at

N=100

(bottom). MF-LP saturates the

\beta_{u}=0.5

cap at every timestep and avoids slow-charging until the departure deadline forces it (

t=9

–

11

); SCA holds a margin below the cap throughout.

Explore similar work

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs
Sep 8, 2026Xiangwu Wang, Chengwei Cao, Hongyuan TangMulti-Agent System Optimization Multi-Agent Coordination
University of Hong Kong · University of California, San Diego · Carnegie Mellon University
Mean Field Reinforcement Learning
Jul 1, 2026René Carmona, Mathieu LaurièreReinforcement Learning Q-Learning
Department of Operations Research and Financial Engineering & Program in Applied and Computational Mathematics, Princeton NJ 08544, USA · Shanghai Frontiers Science Center of Artificial Intelligence and Deep Learning; NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai; NYU Shanghai, 567 West Yangsi Road, Shanghai, 200126, People’s Republic of China
Randomized Transport Maps for Model-Free Policy-Gradient Mean-Field Control
Oct 8, 2026Adonis Jamal, Samy Mekkaoui, Yadh Hafsi +1Policy Gradient Methods Model-Free RL
École Polytechnique

Sep 8, 2026, cs.MAJ/K move · Enter open · S save

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

Xiangwu Wang, Chengwei Cao, Hongyuan Tang

University of Hong Kong · University of California, San Diego · Carnegie Mellon University

Multi-Agent System Optimization Multi-Agent Coordination Multi-Agent Planning

Open paper AskPDF arXiv

Persistent communication limits force a multi-agent system to decide which agents may coordinate throughout a rollout. Current proximity alone is insufficient: separated agents may interact later, whereas a large pair reward may remain unreachable until it is heavily discounted. We introduce Reachability-Certified Subteam Decomposition (RCSD) for finite multi-agent Markov decision processes with factorized physical dynamics, finite-range ordered pair rewards, and almost-sure motion bounds. RCSD combines a speed-limit lower bound on pairwise contact time with a reward envelope to form a current-state affinity. For any capacity-valid persistent partition, the sum of cut affinities bounds the reward-deletion error of every unchanged stationary Markov state-feedback policy. A product of team-optimal policies for the resulting cut MDP incurs at most twice this certificate in regret against the centralized optimum. Both bounds are worst-case tight. On a controlled five-agent family, RCSD-Exact reduces aggregate normalized execution regret by 56.0%, 28.8%, and 25.3% relative to uniform, distance-only, and envelope-only partitions. A separate stochastic two-dimensional study finds no bound violation over 384 exact-partition and 1,440 restricted-controller evaluations. Exact four-agent evidence favors RCSD over uniform and distance-only grouping; raw evidence for current contact is borderline and envelope-only is unresolved. Across balanced 8-20-agent strata, controller-library utility is mixed: pointwise paired intervals favor RCSD over distance and current contact, include zero for uniform, and favor envelope-only and Value-MIP over RCSD. Partition construction remains subsecond in median up to 100 agents; this last result does not include affinity formation or MDP planning.

Abstract

Explore similar work

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

Mean Field Reinforcement Learning

Randomized Transport Maps for Model-Free Policy-Gradient Mean-Field Control