Read-back: multi_agent_decomposition_error

Setting and data

Fix a natural number $N$ (this includes $N = 0$) and, for each agent index $i \in \{0,1,\dots,N-1\}$, a type $S_i$ that is assumed finite and to have decidable equality. Write

$$\mathcal{J} \;=\; \prod_{i} S_i$$

for the joint state–action space: an element $p \in \mathcal{J}$ is a tuple assigning to each agent $i$ a local state–action pair $p_i \in S_i$. ($\mathcal{J}$ is itself finite.) The declaration then takes as given, with no relation among them beyond the hypotheses listed below:

• a real matrix $P$ indexed by $\mathcal{J} \times \mathcal{J}$;
• a real-valued function $\mu : \mathcal{J} \to \mathbb{R}$;
• a real number $\gamma$;
• a real-valued function $r^{\max} : \{0,\dots,N-1\} \to \mathbb{R}$, written $r^{\max}_i$;
• for each $i$, a real-valued function $r_i : S_i \to \mathbb{R}$;
• a real-valued function $Q : \mathcal{J} \to \mathbb{R}$;
• for each $i$, a real matrix $P^{\mathrm{loc}}_i$ indexed by $S_i \times S_i$;
• for each $i$, a real-valued function $Q_i : S_i \to \mathbb{R}$.

All of these are ordinary total functions; no positivity, normalisation, or measurability is built into their types.

The non-standard notions, unfolded

Every notion used below is a definition from this bundle, not a library notion; here is what each one literally means.

Transition matrix. For a finite index type $\iota$ and $M$ a real $\iota \times \iota$ matrix, "$M$ is a transition matrix" means

$$M_{xy} \ge 0 \ \text{ for all } x,y \in \iota, \qquad \text{and} \qquad \sum_{y \in \iota} M_{xy} = 1 \ \text{ for all } x \in \iota .$$

(Rows are the distributions. If $\iota$ is empty both clauses are vacuously true.)

Strictly positive distribution. "$\mu$ is a positive distribution on $\iota$" means

$$\mu(x) > 0 \ \text{ for every } x \in \iota, \qquad \text{and} \qquad \sum_{x \in \iota} \mu(x) = 1 .$$

Stationarity. "$\mu$ is stationary for $M$" means

$$\sum_{x \in \iota} \mu(x)\, M_{xy} \;=\; \mu(y) \qquad \text{for every } y \in \iota .$$

Bellman fixed point. "$V$ is a Bellman $Q$-function for transition matrix $M$, reward $\rho$, discount $\gamma$" (on index type $\iota$) means the exact fixed-point identity

$$V(x) \;=\; \rho(x) \;+\; \gamma \sum_{y \in \iota} M_{xy}\, V(y) \qquad \text{for every } x \in \iota .$$

It is an equality at every point, not an approximation, and it is stated as a property of $V$, not as a definition of $V$.

Agent-$i$ marginal of the joint transition. For $p \in \mathcal{J}$ and $t \in S_i$,

$$\bigl(\mathrm{marg}_i P\bigr)(p, t) \;=\; \sum_{\substack{q \in \mathcal{J} \\ q_i = t}} P_{pq},$$

i.e. the total mass the row of $P$ at the joint point $p$ puts on all joint successors whose $i$-th coordinate equals $t$.

$\mu$-weighted agent-wise total variation distance. For a candidate local matrix $M$ on $S_i$,

$$D_i(\mu, P, M) \;=\; \sum_{p \in \mathcal{J}} \mu(p) \cdot \frac{1}{2} \sum_{t \in S_i} \Bigl| \bigl(\mathrm{marg}_i P\bigr)(p,t) \;-\; M_{p_i\, t} \Bigr| .$$

Note this is a $\mu$-average over joint points, not a supremum over them.

Agent-wise measure of Markov entanglement. For each $i$,

$$e_i \;:=\; \inf\bigl\{\, c \in \mathbb{R} \;:\; \exists\, M \text{ a transition matrix on } S_i,\ c = D_i(\mu, P, M) \,\bigr\}.$$

So $e_i$ is the infimum, over transition matrices $M$ on $S_i$, of the $\mu$-averaged agent-wise total variation distance between $P$'s $i$-marginal and $M$. It depends on both $\mu$ and $P$. (It is an infimum of a set of reals; under the hypotheses below this set is nonempty and bounded below by $0$, so $e_i \ge 0$ and the infimum is a genuine one rather than a default value.)

$\mu$-norm. For $x : \mathcal{J} \to \mathbb{R}$,

$$\|x\|_\mu \;=\; \sum_{p \in \mathcal{J}} \mu(p)\, |x(p)| .$$

This is a $\mu$-weighted $\ell^1$ quantity (a norm when $\mu$ is strictly positive), not a supremum norm.

Hypotheses

1. $0 \le \gamma$.
2. $\gamma < 1$. (Strict; so $(1-\gamma)^2 > 0$ and the division in the conclusion is by a nonzero number.)
3. $P$ is a transition matrix on $\mathcal{J}$: nonnegative entries, every row summing to $1$.
4. $\mu$ is a strictly positive probability distribution on $\mathcal{J}$: $\mu(p) > 0$ for all $p$, and $\sum_p \mu(p) = 1$.
5. $\mu$ is stationary for $P$: $\sum_p \mu(p) P_{pq} = \mu(q)$ for all $q$.
6. For every agent $i$ and every $s \in S_i$: $\;|r_i(s)| \le r^{\max}_i$.
7. $Q$ satisfies the joint Bellman equation for $P$, discount $\gamma$, and the additively decomposable joint reward $p \mapsto \sum_i r_i(p_i)$:

$$Q(p) \;=\; \sum_i r_i(p_i) \;+\; \gamma \sum_{q \in \mathcal{J}} P_{pq}\, Q(q) \qquad \text{for every } p \in \mathcal{J}.$$

8. For every $i$, $P^{\mathrm{loc}}_i$ is a transition matrix on $S_i$.
9. For every $i$, $P^{\mathrm{loc}}_i$ attains the entanglement infimum exactly:

$$D_i\bigl(\mu, P, P^{\mathrm{loc}}_i\bigr) \;=\; e_i .$$

10. For every $i$, $Q_i$ satisfies the local Bellman equation for that minimiser, the local reward $r_i$, and the same discount $\gamma$:

$$Q_i(s) \;=\; r_i(s) \;+\; \gamma \sum_{t \in S_i} \bigl(P^{\mathrm{loc}}_i\bigr)_{st}\, Q_i(t) \qquad \text{for every } s \in S_i .$$

Nothing else is assumed. In particular there is no assumption that $P$ is separable, product-form, irreducible, or aperiodic; no assumption that $\mu$ is the unique stationary distribution; no assumption relating $\mu$ to the marginals of $\mu$; and no assumption that $r^{\max}_i$ is the least bound on $|r_i|$.

Conclusion

$$\sum_{p \in \mathcal{J}} \mu(p) \left| Q(p) - \sum_i Q_i(p_i) \right| \;\;\le\;\; \frac{4\,\gamma \left( \sum_i e_i \, r^{\max}_i \right)}{(1-\gamma)^2}.$$

Reading the right-hand side literally as it is parenthesised: the numerator is $4$ times $\gamma$ times the single sum $\sum_i e_i r^{\max}_i$ (one sum of products, not a product of two sums), and the whole numerator is divided by $(1-\gamma)^2$. The inequality is non-strict ($\le$). The left-hand side is the $\mu$-weighted average of the absolute decomposition error, not its maximum over $p$.

Status of every variable occurring in the conclusion

• $\mu$ — constrained: hypotheses 4 and 5 force it to be a strictly positive probability distribution stationary for $P$. It appears on both sides (it weights the left-hand sum and it enters the definition of each $e_i$).
• $P$ — constrained: hypotheses 3 and 5. It does not appear syntactically on the left but determines $Q$ (via 7) and each $e_i$.
• $\gamma$ — constrained: $\gamma \in [0,1)$ by hypotheses 1 and 2. Appears on the right only.
• $Q$ — constrained: hypothesis 7 pins it down completely. Since $P$ is row-stochastic and $0 \le \gamma < 1$, the Bellman operator is a $\gamma$-contraction in the sup-norm, so hypothesis 7 determines $Q$ uniquely from $P$, $\gamma$ and the $r_i$; it is not a free parameter.
• $Q_i$ (each $i$) — constrained: hypothesis 10 determines $Q_i$ uniquely from $P^{\mathrm{loc}}_i$, $r_i$, $\gamma$ (same contraction argument). However, $Q_i$ inherits whatever freedom $P^{\mathrm{loc}}_i$ has.
• $P^{\mathrm{loc}}_i$ (each $i$) — constrained by hypotheses 8 and 9, but not necessarily uniquely: hypothesis 9 only says $P^{\mathrm{loc}}_i$ is a minimiser of $D_i(\mu, P, \cdot)$ over transition matrices. If the minimiser is not unique, the statement is asserted for every admissible choice, and different minimisers generally give different $Q_i$ and hence a different left-hand side. This is the one genuine residual degree of freedom in the conclusion, and it is only partially pinned down. Note also that $D_i(\mu, P, M)$ is insensitive to the rows of $M$ indexed by coordinate values $s \in S_i$ that no joint point in the support of $\mu$ reaches — but since $\mu$ is strictly positive on all of $\mathcal{J}$ (hypothesis 4), every $s$ arising as some $p_i$ is reached, so the only unconstrained rows are those indexed by $s \in S_i$ that are not the $i$-th coordinate of any $p \in \mathcal{J}$ — and there are none when all $S_j$ are nonempty. So the residual freedom is exactly the freedom of choosing among genuine minimisers.
• $e_i =$ entanglement of agent $i$ (each $i$) — not a variable of the declaration: it is a defined quantity, fully determined by $\mu$ and $P$, both of which are constrained. Under hypothesis 4 each $e_i \ge 0$.
• $r^{\max}_i$ (each $i$) — constrained only from below, by hypothesis 6: $r^{\max}_i \ge |r_i(s)|$ for all $s \in S_i$. It is bounded above by nothing. Since $e_i \ge 0$ and $\gamma \ge 0$, enlarging $r^{\max}_i$ can only enlarge the right-hand side, so this one-sided freedom cannot be used to falsify the statement; but note that when $S_i$ is empty hypothesis 6 is vacuous for that $i$ and $r^{\max}_i$ may be any real, including a negative one (see the degenerate cases below for why this situation cannot actually arise here).
• $r_i$ (each $i$) — appears in the conclusion only indirectly, through $Q$ (hypothesis 7) and $Q_i$ (hypothesis 10); constrained by hypothesis 6.
• $N$ and the family $S$ — universally quantified over all $N \in \mathbb{N}$ and all families of finite types with decidable equality, including $N = 0$ and including singleton or empty $S_i$ (subject to the remark below).

So: no variable appearing in the conclusion is entirely free. $\gamma$, $\mu$, $P$, $Q$, and each $r_i$ are constrained; $r^{\max}_i$ is constrained only from below in the direction that weakens the claim; the only genuinely underdetermined data are the minimisers $P^{\mathrm{loc}}_i$ and, through them, the $Q_i$, and the claim is asserted for all admissible choices of these.

Degenerate and edge cases

• Some $S_i$ empty. If any $S_i$ is empty then $\mathcal{J}$ is empty, and hypothesis 4 requires $\sum_{p \in \emptyset} \mu(p) = 1$, i.e. $0 = 1$. So hypothesis 4 rules this out: under the hypotheses every $S_i$ is nonempty and $\mathcal{J}$ is nonempty. (Hypothesis 3 alone would not have ruled it out, being vacuous on an empty index type.)
• $N = 0$. Then $\mathcal{J}$ is a one-point type (the empty product). Hypothesis 3 forces $P$ to be the $1 \times 1$ matrix $(1)$, hypothesis 4 forces $\mu \equiv 1$ at that point, the joint reward is the empty sum $0$, and hypothesis 7 gives $Q = \gamma Q$, hence $Q = 0$ since $\gamma < 1$. Both sides of the conclusion are then $0$, and the sums $\sum_i$ over agents are empty. The statement is therefore non-vacuous but trivial at $N = 0$.
• $\gamma = 0$. Permitted by hypothesis 1. Then $Q(p) = \sum_i r_i(p_i)$ and $Q_i = r_i$, so the left-hand side is $0$; the right-hand side is also $0$. The inequality is an equality.
• All $e_i = 0$. Then the right-hand side is exactly $0$, so the conclusion asserts $\sum_p \mu(p)\,|Q(p) - \sum_i Q_i(p_i)| = 0$, and since $\mu$ is strictly positive this is the pointwise identity $Q(p) = \sum_i Q_i(p_i)$ for every $p \in \mathcal{J}$ — an exact value decomposition, not an approximate one.
• Division. $(1-\gamma)^2 \ne 0$ because $\gamma < 1$ strictly, so no division-by-zero convention is invoked.
• The infimum defining $e_i$. The set over which it is taken is nonempty (the uniform matrix on the nonempty finite $S_i$ is a transition matrix) and bounded below by $0$ (all summands are nonnegative once $\mu \ge 0$), so $e_i$ is an honest real infimum in $[0,\infty)$.

Joint satisfiability of the hypotheses

The hypotheses are jointly satisfiable, and satisfiable non-trivially, so the statement is not vacuous. For instance:

• Take any $N \ge 1$ with each $S_i$ a singleton. Then $\mathcal{J}$ is a singleton, $P = (1)$, $\mu \equiv 1$ is stationary and strictly positive, any $r_i$ works with $r^{\max}_i = |r_i(\ast)|$, $Q = \bigl(\sum_i r_i(\ast)\bigr)/(1-\gamma)$, $P^{\mathrm{loc}}_i = (1)$ is the unique transition matrix (so hypothesis 9 holds with $e_i = 0$), and $Q_i = r_i(\ast)/(1-\gamma)$. All ten hypotheses hold simultaneously.
• More generally, hypothesis 9 (attainment of the entanglement infimum) is not an extra restriction on $P$ and $\mu$: for each $i$ the set of transition matrices on the finite set $S_i$ is a nonempty compact subset of a finite-dimensional space and $M \mapsto D_i(\mu, P, M)$ is continuous, so a minimiser always exists. Likewise hypotheses 7 and 10 are always solvable (uniquely) because $0 \le \gamma < 1$ and the matrices are row-stochastic. The only hypotheses that genuinely restrict the data are 1–6, and these are simultaneously satisfiable by any finite-state chain with a strictly positive stationary distribution together with any bounded local rewards.

No claim is made here about whether the stated bound is correct, tight, or a faithful rendering of any external result; the above is only what the declaration asserts.