Index policies have sublinear value decomposition error (Cor. 1)

The declaration asserts the following. Fix a finite type $S$ equipped with decidable equality, together with:

• 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$;
• a function $\nu : S \to \mathbb{R}$ assumed to be injective;
• a real number $\alpha$ with $0 < \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$ (note that this last equation is what forces $S$ to be nonempty; $S$ is not otherwise assumed nonempty);
• a real number $\gamma$ with $0 \le \gamma < 1$, and an arbitrary real number $r_{\max}$, on which no sign assumption is placed.

Two hypotheses are imposed on the mean-field map $\varphi = \varphi_{P_0,P_1,\nu,\alpha}$, which is the map sending $m : S \to \mathbb{R}$ to the function

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

where the activated fraction is $f_m(x) = \min\!\big(m(x),\ \max(0,\ \alpha - h_m(x))\big)$ and the higher-priority mass is $h_m(x) = \sum_{y \,:\, \nu(x) < \nu(y)} m(y)$. The two hypotheses are:

• Uniform global attractor: $\varphi(m^\star) = m^\star$, and for every $\varepsilon > 0$ there exists $T \in \mathbb{N}$ such that for every $t \ge T$ and every configuration $m$ (any $m$ with $m \ge 0$ pointwise and $\sum_x m(x)=1$), the iterate $\varphi^{t}(m)$ satisfies $\sup_{x \in S} \big|\varphi^{t}(m)(x) - m^\star(x)\big| < \varepsilon$ (the supremum is a real supremum over $S$).
• Mean-field non-degeneracy: there exists $x \in S$ with $m^\star(x) > 0$, $\ \alpha - h_{m^\star}(x) > 0$, and $\ \alpha - h_{m^\star}(x) < m^\star(x)$ — all three inequalities strict.

Under exactly these assumptions, the claim is that there exists a real constant $C$ with $C \ge 0$ (only nonnegativity is claimed; $C$ may be $0$, and $C$ is permitted to depend on all of the data fixed above, including $S$, $P_0$, $P_1$, $\nu$, $\alpha$, $m^\star$, $\gamma$ and $r_{\max}$, but is chosen once and for all before $N$ and everything that follows), such that for every $N \in \mathbb{N}$ with $N > 0$, the following holds. Write $M = \lfloor \alpha N \rfloor$ (the natural-number floor; for small $N$ this can be $0$, e.g. $N=1$ with $\alpha = \tfrac12$). Then for every function $\pi : (\text{Fin }N \to S) \to (\text{Fin }N \to \{\mathrm{tt},\mathrm{ff}\}) \to \mathbb{R}$ that is an index policy with budget $M$ — meaning all three of:

1. $\pi(s,a) \ge 0$ for all $s,a$ and $\sum_{a} \pi(s,a) = 1$ for every joint state $s$;
2. whenever $\pi(s,a) \ne 0$, the action profile $a$ is budgeted: $\#\{i : a_i = \mathrm{tt}\} = M$ exactly;
3. for every joint state $s$ and every agent $i$, the marginal activation probability $\sum_{a} \mathbf{1}[a_i = \mathrm{tt}]\,\pi(s,a)$ equals $\operatorname{iap}(s, s_i)$, where $\operatorname{iap}(s,x) = 0$ if $c_s(x) = 0$ and otherwise $\operatorname{iap}(s,x) = \min\!\big(c_s(x),\ M \dot- H_s(x)\big)/c_s(x)$, with $c_s(x) = \#\{i : s_i = x\}$, $H_s(x) = \sum_{y \,:\, \nu(x)<\nu(y)} c_s(y)$, and $\dot-$ truncated natural-number subtraction (so the numerator is $0$ whenever $H_s(x) \ge M$);

and for every function $\mu$ on the joint state–action space $\Omega_N := \prod_{i=1}^{N}(S \times \{\mathrm{tt},\mathrm{ff}\})$, whose elements $p$ we write as $p_i = (s_i(p), a_i(p))$, such that

• $\mu$ is a distribution: $\mu(p) \ge 0$ for all $p$ and $\sum_{p} \mu(p) = 1$;
• $\mu$ is exchangeable: $\mu(p \circ \sigma) = \mu(p)$ for every permutation $\sigma$ of $\{1,\dots,N\}$ and every $p$;
• $\mu$ is stationary for the induced transition matrix $T$ on $\Omega_N$, i.e. $\sum_{p} \mu(p)\,T(p,q) = \mu(q)$ for every $q$, where

$$T(p,q) \;=\; \Big(\prod_{j=1}^{N} K_{a_j(p)}\big(s_j(p),\, s_j(q)\big)\Big)\cdot \pi\big(s(q),\, a(q)\big), \qquad K_{\mathrm{tt}} = P_1,\ K_{\mathrm{ff}} = P_0;$$

and for every family of per-agent reward functions $r_i : S \times \{\mathrm{tt},\mathrm{ff}\} \to \mathbb{R}$ satisfying $|r_i(x)| \le r_{\max}$ for all $i$ and all $x$ (note: since $N > 0$ and $S$ is nonempty, such an $r$ exists only if $r_{\max} \ge 0$; for negative $r_{\max}$ everything from this point on is vacuous), and for every $Q : \Omega_N \to \mathbb{R}$, every family of matrices $P^{(i)} \in \mathbb{R}^{(S\times\{\mathrm{tt},\mathrm{ff}\})\times(S\times\{\mathrm{tt},\mathrm{ff}\})}$ and every family $Q_i : S \times \{\mathrm{tt},\mathrm{ff}\} \to \mathbb{R}$, such that

• $Q$ satisfies the global Bellman equation for $T$ with the additive reward $R(p) = \sum_{i} r_i(p_i)$: $\ Q(p) = R(p) + \gamma \sum_{q} T(p,q)\,Q(q)$ for every $p$;
• every $P^{(i)}$ is a transition matrix (nonnegative entries, rows summing to $1$);
• every $P^{(i)}$ is a local transition of agent $i$ for $T$ under $\mu$: for all $u, v \in S \times \{\mathrm{tt},\mathrm{ff}\}$,

$$\Big(\sum_{q} \mathbf{1}[q_i = u]\,\mu(q)\Big)\cdot P^{(i)}(u,v) \;=\; \sum_{p} \mathbf{1}[p_i = u]\,\mu(p)\cdot \sum_{q} \mathbf{1}[q_i = v]\,T(p,q)$$

(in particular, at a local state $u$ whose $\mu$-marginal is $0$ this condition says nothing about the row $P^{(i)}(u,\cdot)$ beyond forcing the right-hand side to vanish);

• every $Q_i$ satisfies the local Bellman equation for $P^{(i)}$ with reward $r_i$ and the same $\gamma$: $\ Q_i(u) = r_i(u) + \gamma \sum_{v} P^{(i)}(u,v)\,Q_i(v)$ for every $u$;

the conclusion is the inequality

$$\sum_{p \in \Omega_N} \mu(p)\,\Big|\, Q(p) \;-\; \sum_{i=1}^{N} Q_i\big(p_i\big) \Big| \;\;\le\;\; \frac{4\,C\,\gamma\,\sqrt{N}\,r_{\max}}{(1-\gamma)^2}.$$

Several features of the quantifier structure are worth stating explicitly: the constant $C$ is required to be independent of $N$, $\pi$, $\mu$, $r$, $Q$, $P^{(i)}$ and $Q_i$, but not of $r_{\max}$ or $\gamma$, both of which are fixed before $C$ is produced and both of which also appear on the right-hand side; the numerator is $4C\gamma\sqrt{N}\,r_{\max}$ and the whole product is divided by $(1-\gamma)^2$; when $\gamma = 0$ (permitted, since only $0 \le \gamma$ is assumed) the right-hand side is exactly $0$, so the assertion in that case is that the weighted $\ell^1$ error is $\le 0$; the mean-field hypotheses are stated for the exact fraction $\alpha$, whereas the index policy is required to have the integer budget $\lfloor \alpha N\rfloor$; no irreducibility, aperiodicity, positivity or uniqueness assumption is placed on $\mu$, on $T$, or on the solutions $Q$, $Q_i$ of the Bellman equations; and the left-hand side is a $\mu$-weighted sum of absolute deviations over the whole joint state–action space, not a supremum.