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

Sep 8, 2026cs.MA

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

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.

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

Ask PDF

Jul 1, 2026math.OC

Mean Field Reinforcement Learning

This monograph provides an introduction to mean field reinforcement learning through the lens of Markov decision processes arising from large-population stochastic control with mean field interactions and common noise. Starting from the connection between multi-agent reinforcement learning and mean field control, it develops the probabilistic, mathematical, and control-theoretic framework needed to formulate representative-agent learning problems, analyze their relationship with finite-population systems, and study both general and linear-quadratic models. The presentation includes dynamic programming principles, propagation-of-chaos limits, and theoretical analyses of tabular Q-learning and policy-gradient methods. It also discusses numerical implementations, including tabular schemes and deep reinforcement learning methods such as deep deterministic policy gradient. The goal is to give readers a coherent bridge between mean field control theory and reinforcement learning methodology, emphasizing the mathematical structure of the problems and the design of tractable learning approaches for large stochastic populations.

René Carmona, Mathieu Laurière

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

Reinforcement Learning Q-Learning Policy Gradient Methods Policy Learning

Ask PDF

Oct 8, 2026math.OC

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

We develop a model-free policy gradient method for discrete-time mean-field control (MFC). In MFC, the policy affects the objective both through the controlled dynamics and through the population distribution. Standard REINFORCE estimators capture the first effect but not the second. We introduce Transport REINFORCE, a transport map-based approach that perturbs a suitable transformation of the population distribution to estimate this missing mean-field contribution. The method applies to both finite and continuous state spaces. In finite state spaces, we perturb the population distribution directly on the probability simplex through a convex combination of the current population weights and random weights. In continuous state spaces, we project the population distribution onto the manifold of Gaussian mixtures, and then randomize it via a transport map that ensures the perturbed law remains within this manifold. We prove consistency of the perturbed objective and gradient as the perturbation vanishes, and derive bias and mean-square error bounds for the resulting sample-based gradient estimator. Numerical experiments on several MFC benchmarks show that Transport REINFORCE improves over standard REINFORCE.

Adonis Jamal, Samy Mekkaoui, Yadh Hafsi +1

École Polytechnique

Policy Gradient Methods Model-Free RL

Ask PDF