Index policies are asymptotically separable (Thm. 7)

Fix a finite type $S$ with decidable equality (the per‑agent state space). The statement asserts, for every choice of the following data:

• two matrices $P_0, P_1 \in \mathbb{R}^{S\times S}$, each assumed to be a transition matrix, i.e. $P_k(x,y)\ge 0$ for all $x,y$ and $\sum_{y} P_k(x,y)=1$ for every $x$ (for $k=0,1$);
• a function $\nu : S \to \mathbb{R}$ (a priority index) assumed injective, so distinct states get distinct priorities;
• a real number $\alpha$ with $0 < \alpha$ and $\alpha < 1$;
• a function $m^\star : S \to \mathbb{R}$ assumed to be a configuration, i.e. $m^\star(x)\ge 0$ for all $x$ and $\sum_{x} m^\star(x) = 1$;

subject to two further hypotheses spelled out below, the following conclusion.

Hypothesis (uniform global attractor). Write, for a vector $m : S\to\mathbb{R}$ and $x\in S$,

$$H_\nu(m,x) \;=\; \sum_{\,y \,:\, \nu(x)<\nu(y)\,} m(y),\qquad A_{\nu,\alpha}(m,x)\;=\;\min\!\big(m(x),\;\max(0,\;\alpha - H_\nu(m,x))\big),$$

and let $\varphi$ be the map sending $m : S\to\mathbb{R}$ to the vector

$$\varphi(m)(y)\;=\;\sum_{x\in S}\Big[\big(m(x)-A_{\nu,\alpha}(m,x)\big)\,P_0(x,y)\;+\;A_{\nu,\alpha}(m,x)\,P_1(x,y)\Big].$$

(This $\varphi$ is defined on all of $S\to\mathbb{R}$, not just on the simplex, and does not involve $N$.) Let $\varphi^t$ denote $t$‑fold iteration, with $\varphi^0(m)=m$, and let $\lVert v\rVert_\infty = \sup_{x\in S}|v(x)|$. The hypothesis is the conjunction of:

1. $\varphi(m^\star) = m^\star$ (as functions on $S$), and
2. for every $\varepsilon>0$ there exists $T\in\mathbb{N}$ such that for every $t\ge T$ and every configuration $m$ (i.e. every $m$ with $m(x)\ge0$ for all $x$ and $\sum_x m(x)=1$), $\;\lVert \varphi^t(m)-m^\star\rVert_\infty < \varepsilon$.

Hypothesis (mean‑field non‑degeneracy). There exists a state $x\in S$ with

$$0 < m^\star(x),\qquad 0 < \alpha - H_\nu(m^\star,x),\qquad \alpha - H_\nu(m^\star,x) < m^\star(x).$$

Conclusion. There exists a real number $C$ with $C \ge 0$ such that for every natural number $N$ with $N>0$, every function

$$\pi : (\mathrm{Fin}\,N \to S) \;\to\; (\mathrm{Fin}\,N \to \mathrm{Bool}) \;\to\; \mathbb{R}$$

satisfying the index‑policy property at budget $M := \lfloor \alpha N\rfloor$ (natural‑number floor of $\alpha N$; since $0<\alpha<1$ and $N\ge1$ this lies in $\{0,1,\dots,N-1\}$ and may be $0$), and every function $\mu$ on $\mathrm{Fin}\,N \to (S\times\mathrm{Bool})$ satisfying three further properties, and every index $i \in \mathrm{Fin}\,N$, the quantity $E_i$ defined below satisfies

$$E_i \;\le\; \frac{C}{\sqrt{N}}.$$

The constant $C$ is chosen before $N$, $\pi$, $\mu$ and $i$, so it is uniform in all of them (it may depend on $S$, $P_0$, $P_1$, $\nu$, $\alpha$, $m^\star$).

Unfolding the four properties and the quantity:

• $\pi$ is an index policy at budget $M$: (a) $\pi(s,a)\ge 0$ for all $s\in S^{N}$, $a\in\mathrm{Bool}^{N}$, and $\sum_{a\in\mathrm{Bool}^N}\pi(s,a)=1$ for every $s$; (b) for all $s,a$, if $\pi(s,a)\neq 0$ then $\#\{j : a_j = \text{true}\} = M$ exactly; and (c) for every $s$ and every $i$,

$$\sum_{a\in\mathrm{Bool}^N}\mathbf{1}[a_i=\text{true}]\;\pi(s,a)\;=\;\rho_{\nu,M}(s,s_i),$$

where, with $c(s,x)=\#\{j : s_j = x\}$ and $h(s,x)=\sum_{y:\nu(x)<\nu(y)} c(s,y)$,

$$\rho_{\nu,M}(s,x)\;=\;\begin{cases}0 & \text{if } c(s,x)=0,\\[2pt] \dfrac{\min\big(c(s,x),\; M \dot- h(s,x)\big)}{c(s,x)} & \text{otherwise,}\end{cases}$$

and $M \dot- h(s,x)$ is truncated natural subtraction, equal to $0$ whenever $h(s,x)\ge M$.

• $\mu$ is a distribution: $\mu(p)\ge 0$ for every $p \in (S\times\mathrm{Bool})^{N}$ and $\sum_{p}\mu(p)=1$. (Strict positivity is not required.)

• $\mu$ is exchangeable: for every permutation $\sigma$ of $\mathrm{Fin}\,N$ and every $p:\mathrm{Fin}\,N\to S\times\mathrm{Bool}$, $\;\mu(p\circ\sigma)=\mu(p)$.

• $\mu$ is stationary for the induced chain. The induced chain is the matrix $\mathcal{P}$ on the state‑action product space $(S\times\mathrm{Bool})^{N}$ given by

$$\mathcal{P}\big((s,a),(s',a')\big)\;=\;\Big(\prod_{j=1}^{N} K\big(s_j, a_j, s'_j\big)\Big)\cdot \pi(s',a'),\qquad K(x,b,y)=\begin{cases}P_1(x,y)&b=\text{true}\\ P_0(x,y)&b=\text{false,}\end{cases}$$

where a point $p$ of $(S\times\mathrm{Bool})^N$ is read as the pair $(s,a)$ with $s_j=(p_j)_1$, $a_j=(p_j)_2$; note the policy factor is evaluated at the destination pair $(s',a')$, not the source. Stationarity is: for every $q$, $\;\sum_{p}\mu(p)\,\mathcal{P}(p,q)=\mu(q)$.

• The bounded quantity $E_i$ is the "agent‑$i$ entanglement" of $\mu$ and $\mathcal{P}$: the infimum (in $\mathbb{R}$) of the set

$$\Big\{\, r \in\mathbb{R} \;:\; \exists\, \Pi \in \mathbb{R}^{(S\times\mathrm{Bool})\times(S\times\mathrm{Bool})} \text{ a transition matrix, } r = \sum_{p}\mu(p)\cdot\tfrac12\!\!\sum_{t\in S\times\mathrm{Bool}}\!\big| \mathcal{P}_i(p,t) - \Pi(p_i,t)\big| \Big\},$$

where $\mathcal{P}_i(p,t)=\sum_{q}\mathbf{1}[q_i=t]\,\mathcal{P}(p,q)$ is the marginal one‑step law of coordinate $i$ from $p$, and "$\Pi$ a transition matrix" means $\Pi(u,v)\ge0$ and $\sum_v \Pi(u,v)=1$ for all $u$. In words: the smallest $\mu$‑averaged total‑variation distance between agent $i$'s true marginal transition law and any single Markov kernel on $S\times\mathrm{Bool}$ depending only on agent $i$'s own state‑action pair.

Degenerate cases the quantifiers silently include. If $S$ is empty the configuration hypothesis $\sum_x m^\star(x)=1$ and the non‑degeneracy hypothesis (which asserts the existence of a state) cannot hold, so the hypotheses force $S$ nonempty. For a given $N$ the inner statement is vacuous if no $\pi$ meets the index‑policy conditions at budget $\lfloor\alpha N\rfloor$, or if no $\mu$ is simultaneously a distribution, exchangeable and stationary for $\mathcal{P}$; in particular the case $M=0$ (all $\lfloor\alpha N\rfloor = 0$, e.g. $N=1$) is included, where the budget condition forces $\pi$ to be supported on the all‑false action profile. The bound is stated with $\le$, not $<$, and asserts only $C\ge0$, not $C>0$. The infimum defining $E_i$ is the real infimum of the displayed set, taken over transition matrices on the full pair space $S\times\mathrm{Bool}$ (not on $S$ alone). Finally, $\sqrt{N}$ is the real square root of $N$, positive since $N>0$, so the right‑hand side is an ordinary quotient.