PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jie Fu, Anamika Dubey

arXiv:2610.12028v1eess.SYcs.MAcs.SY

TL;DR

Finite-population occupancy fluctuations mean that satisfying mean-field constraints alone does not ensure reach–avoid chance constraints. The paper propagates empirical-density moments and uses Cantelli-based conditions with moment-error bounds in policy synthesis; in both case studies, the mean-only baseline's violation probability approaches approximately 50% while SCA uncertainty penalties decrease as O(1/N).

  • Problem

    Mean-field methods enforce aggregate constraints on the nominal trajectory, but finite-N empirical-density fluctuations can leave reach–avoid chance constraints unsatisfied.

    Source: §I · p. 1

  • Method

    The method propagates empirical-density mean and covariance, applies Cantelli-based deterministic surrogates with moment-error bounds, and optimizes density-feedback policies using sequential convex approximation.

    Source: §I · p. 2, B. SOCP Subproblem · p. 5, APPENDIX VARIANCE OF AGGREGATE… · p. 8

  • Results

    In both case studies, the MF-LP baseline’s violation probability approaches approximately 50% as N increases, while SCA standard-deviation penalties decrease at rate O(1/N).

    Source: §VII · p. 7

  • Takeaways & Limitations

    The standard-deviation penalties reduce conservatism as populations grow, while the framework provides a finite-N certificate based on moment-approximation error bounds.

    Source: §I · p. 2, §VII · p. 7

Abstract

from arXiv · show

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-\delta_r$, at least a fraction $\alpha_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 $\beta_u$ with probability at least $1-\delta_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.

I. INTRODUCTION

Finite populations can violate reach–avoid chance constraints even when their mean-field trajectories satisfy the corresponding average constraints. The paper models this finite-N problem and proposes moment-based policy synthesis with a finite-N certificate.

I. INTRODUCTION

  • For finite N, empirical-density fluctuations of order O(1/N) mean that satisfying a constraint on the mean-field trajectory may still leave a non-negligible violation probability.Source: §I · p. 1
  • Prior safety methods constrain deterministic population distributions or mean-field limits, while safe MFRL addresses transition-model uncertainty rather than finite-N empirical-density fluctuations.Source: §I · p. 1
  • Other variability methods address individual-system noise or continuum-density dispersion, whereas this paper targets the O(1/N) sampling covariance of finite empirical occupancy.Source: §I · p. 1
  • The method propagates empirical-density means and covariances, uses Cantelli bounds for deterministic sufficient conditions, and adds moment-error bounds for rigorous finite-N certificates.Source: §I · p. 2

A. Swarm MDP and Empirical Density

B. Reach-Avoid Chance Constraints

  • Given αr, βu, δr, δu ∈(0, 1), Problem 1 seeks policy parameters θ* and reach time t*∈[T], bounding reach and avoid violation probabilities separately, with the avoid guarantee at each time t ≤t*.Source: B. Reach-Avoid Chance Constraints · p. 2

III. MEAN-FIELD DYNAMICS AND COVARIANCE PROPAGATION

The section defines a nominal mean-field trajectory and distinguishes it from the true expected empirical density at finite population size. That distinction matters when density feedback makes the conditional-mean map nonlinear.

III. MEAN-FIELD DYNAMICS AND COVARIANCE PROPAGATION

  • The nominal mean-field trajectory follows the flow equation, applying the transition matrix F to the occupation flow z_t.Source: A. Mean-Field Trajectory · pp. 2–3
  • The finite-population process has an exact conditional-mean update, but the nominal trajectory is not generally the exact finite-N expectation under nonlinear density feedback.Source: A. Mean-Field Trajectory · p. 2
  • The mean-field trajectory is a leading-order approximation to the finite-N mean, and the stated analysis assumes a fixed horizon and specified regularity and initial-concentration conditions.Source: A. Mean-Field Trajectory · pp. 2–3

B. Exact Conditional Moments and First-Order Covariance Propagation

The empirical density is a finite-state Markov process under density feedback. Its covariance recursion separates conditional action-and-transition noise from the propagation of existing density fluctuations, then approximates the latter by linearization.

B. Exact Conditional Moments and First-Order Covariance Propagation

  • Given the current empirical density, agents randomize actions independently and make conditionally independent physical transitions, yielding an exact conditional next-state covariance identity.Source: B. Exact Conditional Moments and… · p. 3
  • Under density feedback, the covariance includes propagated state-density fluctuations; when the policy is density independent, this additional term vanishes.Source: B. Exact Conditional Moments and… · p. 3
  • The first-order covariance approximation linearizes the conditional-mean map around the nominal trajectory under fixed-horizon, initial-concentration, and smoothness assumptions.Source: B. Exact Conditional Moments and… · p. 3
  • The recursion starts from the initial covariance, which is zero for deterministic initialization, and propagates prior density fluctuations to the next step.Source: B. Exact Conditional Moments and… · p. 3

IV. CANTELLI CHANCE-CONSTRAINT CERTIFICATION

Mean-field constraints alone do not guarantee finite-N chance constraints. This section derives moment-based Cantelli conditions and shows how bounds on approximation errors make the resulting test a rigorous finite-N certificate.

IV. CANTELLI CHANCE-CONSTRAINT CERTIFICATION

  • Mean-field reach and unsafe-region constraints alone do not imply the corresponding finite-N chance constraints.Source: §IV · p. 3
  • Cantelli’s inequality converts the exact finite-population mean and variance of regional occupancy into deterministic sufficient conditions for reach and avoid probabilities.Source: §IV · p. 3
  • Validated bounds on mean and variance approximation errors make the surrogate conditions sufficient for the exact finite-N chance constraints.Source: §IV · p. 4
  • The resulting surrogate constraints depend nonlinearly on policy parameters through the mean-field and covariance recursions.Source: §IV · p. 4

V. CHANCE-CONSTRAINED MEAN-FIELD POLICY SYNTHESIS

The synthesis problem uses mean-field and first-order covariance approximations, with the approximate problem subject to constraints (27), (26), (9), and (19). Because it is nonconvex, the paper solves it with sequential convex approximation.

V. CHANCE-CONSTRAINED MEAN-FIELD POLICY SYNTHESIS

  • The approximate synthesis problem combines mean-field and first-order covariance approximations, subject to constraints (27), (26), (9), and (19).The occupancy measure is z_t.Source: §V · p. 4
  • At each SCA iteration, the method linearizes the mean-field trajectory and solves a trust-region SOCP for a policy-improvement step subject to Cantelli reach-avoid constraints.The sequential convex approximation is used because the problem is nonconvex.Source: §V · p. 4

A. Linearization of the objective function

This subsection develops a first-order objective expansion and the sensitivities needed to account for policy parameters affecting both the policy and the mean-field density. The mean-density sensitivity is propagated through a linear recursion.

A. Linearization of the objective function

  • The objective is expanded to first order around the policy parameters at iteration k.The expansion is taken at θ(k).Source: A. Linearization of the objective… · p. 4
  • The occupation measure z_t depends on θ through both the parameterized policy and the mean-field density, so differentiating f_t uses the chain rule.The passage identifies both direct dependence on θ and dependence through the mean-field trajectory.Source: A. Linearization of the objective… · pp. 4–5
  • Because the flow matrix F is independent of θ, differentiating the mean-density update yields a linear recursion in D(k), whose first term propagates density sensitivity and second term captures direct policy-parameter effects.The time-indexed sensitivity is then recovered from D(k).Source: A. Linearization of the objective… · p. 5

B. SOCP Subproblem

The SOCP subproblem linearizes the mean trajectory and freezes covariance bounds to keep policy-step constraints affine. A trust-region merit test and candidate reach-time search govern updates and termination.

B. SOCP Subproblem

  • The subproblem uses the first-order covariance recursion at the current iterate and certified upper bounds on the Cantelli standard deviation to impose robust conditions.The resulting objective and constraints are affine in the policy step, with a second-order-cone trust-region constraint; the SOCP is solvable in polynomial time.Source: B. SOCP Subproblem · p. 5
  • Freezing the covariance bound while linearizing the mean keeps the constraints affine in the policy step and preserves the SOCP form.The covariance is recomputed after each accepted step, and the trust region keeps the approximation local.Source: B. SOCP Subproblem · p. 5
  • A candidate step is evaluated with a nonlinear L1-penalty merit function because improving the objective can still violate robust constraints after linearization.The bounds are recomputed or validated at the candidate policy, and the trust-region radius is updated following the acceptance test.Source: B. SOCP Subproblem · p. 5
  • If the SOCP is infeasible, the trust region is increased up to its maximum; persistent infeasibility ends that run and advances to the next candidate reach time.A rejected candidate instead causes the trust-region radius to be reduced.Source: B. SOCP Subproblem · p. 5
  • The method tests candidate reach times in descending order of initial reach margins and stops at the first time satisfying both reach and avoid margins.If none succeeds, it returns the infeasible result with the largest merit value; stopping at the first feasible candidate may yield a suboptimal reward.Source: B. SOCP Subproblem · p. 5

VI. EXPERIMENTAL VALIDATION

The algorithm is validated in two case studies against a mean-field LP baseline. That baseline optimizes over occupation measures while enforcing only mean constraints.

VI. EXPERIMENTAL VALIDATION

  • The validation uses two case studies and compares the proposed algorithm with a mean-field LP baseline.The baseline solves the mean-field relaxation directly over occupation measures rather than policy parameters.Source: §VI · p. 6
  • The baseline enforces only mean constraints and solves a separate LP for each candidate reach time, retaining the best feasible reward.The objective and constraints are linear in the occupation measure, so each LP is solved exactly.Source: §VI · p. 6
  • The baseline recovers a policy from the optimized occupation measure.The stated recovery rule uses uniform action probabilities where the optimized mean density is zero.Source: §VI · p. 6

A. Gridworld Environment

The gridworld evaluation routes agents through narrow wall openings to reach designated targets while limiting congestion at each opening. SCA satisfies its surrogate margins and stays within the empirical avoid budget for N≥20, while MF-LP violations increase with fleet size.

A. Gridworld Environment

  • A 6 × 6 grid routes agents from (5, 0) through one of three wall gaps to three reach targets and a separate reward-only target.The reward-only target is not included in the reach set.Source: A. Gridworld Environment · p. 6, Figure 1 · p. 6
  • The gridworld applies separate per-opening avoid constraints (βu,i=0.30, δu,i=0.40) and requires αr=0.3 with δr=0.1 for reach.The avoid constraint limits the probability that more than 30% of agents occupy an opening at once to 40%; the reach requirement is at least 30% with probability at least 90%.Source: A. Gridworld Environment · p. 6
  • For N≥20, SCA has positive Cantelli margins, ˆPv≤0.12, and reward within 5% of MF-LP.The gridworld target is ˆPv≤0.40.Source: A. Gridworld Environment · pp. 6–7
  • At N=10, empirical reach rate is 100% and empirical per-cell violation rate is 40%, although rm=-0.108 and am=-0.194 fail Cantelli.The authors attribute this gap to the conservatism of the distribution-free Cantelli bound.Source: A. Gridworld Environment · p. 7
  • MF-LP's violation rate rises from 0.38 at N=10 to 0.47 at N=100 because its mean occupancy sits at the 0.30 cap.Source: A. Gridworld Environment · p. 7

B. EV-Charging Aggregator

The EV-charging case uses density-feedback control to meet a reach target while limiting simultaneous fast charging. Its results contrast the mean-only LP baseline with SCA’s variance-aware constraints, then state the framework’s broader scope and extensions.

B. EV-Charging Aggregator

  • The EV case targets at least 80% SOC for 80% of the fleet by T = 12, while limiting simultaneous fast charging to βu = 0.5 with probability at least 1−δu.The policy uses bias, normalized SOC, and the fleet fraction already at the target as features.Source: B. EV-Charging Aggregator · p. 7
  • MF-LP's maximum per-time-step violation rate is 0.45–0.52, while SCA satisfies surrogate conditions for N ≥50 and observed violation rates remain at or below 0.08.The reported SCA violation rates are for N = 50, 100, and 200.Source: B. EV-Charging Aggregator · p. 7
  • Replacing the scalar target-density feature with the full density vector increased the policy from 1,188 to 5,148 parameters, with similar results.The full-density results are omitted.Source: B. EV-Charging Aggregator · p. 7

VII. CONCLUSION

  • The framework optimizes density-feedback policies through sequential convex approximation over SOCPs for constrained policy-gradient updates.It is presented for chance-constrained reach–avoid control of finite-N swarms on discrete MDPs.Source: §VII · p. 7
  • The mean-only MF-LP baseline lies on the active constraint boundary, with violation probability approaching approximately 50% rather than vanishing as N increases.The SCA standard-deviation penalties decrease at rate O(1/N), reducing conservatism for larger populations.Source: §VII · p. 7
  • Future work includes extending the approach to mean-field-type MDPs with density-coupled transitions and rewards, and to finite-N MDPs with common noise.Source: §VII · pp. 7–8

B. EV-Charging Aggregator

  • At N = 100, MF-LP saturates the βu = 0.5 cap each timestep and delays slow charging until t = 9–11; SCA stays below the cap and uses more slow charging earlier.The lower average fast-charging fraction means SCA relies more on slow charging to satisfy the reach constraint.Source: B. EV-Charging Aggregator · p. 7, Figure 2 · p. 8

APPENDIX VARIANCE OF AGGREGATE OCCUPATION MEASURES

The occupation-measure variance approximation estimates variability in an aggregate action quantity by combining action-sampling variance with propagated state-density fluctuations.

APPENDIX VARIANCE OF AGGREGATE OCCUPATION MEASURES

  • For an empirical occupation measure, c selects a linear aggregate quantity; in the EV example, c = cF selects the fraction taking the fast-charging action.Source: APPENDIX VARIANCE OF AGGREGATE… · p. 8
  • The approximation applies total variance and linearizes the conditional mean hc around the mean-field density to account for action and state-density variability.Source: APPENDIX VARIANCE OF AGGREGATE… · p. 8
  • Its two terms represent conditional action-sampling variance and propagated state-density fluctuations, with the latter using the state-density covariance approximation.Source: APPENDIX VARIANCE OF AGGREGATE… · p. 8
Loading 2610.12028v1…