Read-back: cooperative_decomposition_error_with_reward_entanglement

The setting and all the data

Fix a natural number $N$ (implicit) and a family of types $S_0, S_1, \dots, S_{N-1}$ (implicit), each of which is finite and has decidable equality. Write

$$\mathcal{J} \;=\; \prod_{i=0}^{N-1} S_i$$

for the joint space: an element $p \in \mathcal{J}$ is a tuple assigning to each agent $i$ a point $p_i \in S_i$. $\mathcal{J}$ is finite. The following data are given, all explicitly quantified over (the theorem asserts its conclusion for every choice of them satisfying the hypotheses below):

• $P \in \mathbb{R}^{\mathcal{J} \times \mathcal{J}}$, a matrix on the joint space;
• $\mu : \mathcal{J} \to \mathbb{R}$, a weight function on the joint space;
• $\gamma \in \mathbb{R}$, a scalar;
• $r_{\max} : \{0,\dots,N-1\} \to \mathbb{R}$, one real number per agent;
• $r : \mathcal{J} \to \mathbb{R}$, a function on the joint space;
• $r^{\mathrm{loc}}_i : S_i \to \mathbb{R}$ for each agent $i$ (a family of local functions);
• $Q : \mathcal{J} \to \mathbb{R}$;
• $P^{\mathrm{loc}}_i \in \mathbb{R}^{S_i \times S_i}$ for each agent $i$;
• $Q_i : S_i \to \mathbb{R}$ for each agent $i$.

The non-standard notions, expanded

All of the following are definitions from this bundle; they are unfolded here so the statement can be read without them.

• Row-stochastic ("IsTransitionMatrix") for a square matrix $M$ indexed by a finite set: $M_{xy} \ge 0$ for all $x, y$, and $\sum_y M_{xy} = 1$ for every $x$. Nothing is required of columns.
• Strictly positive distribution ("IsPositiveDist") for $\mu$: $\mu(p) > 0$ for every $p \in \mathcal{J}$, and $\sum_{p \in \mathcal{J}} \mu(p) = 1$.
• Stationarity ("IsStationary") of $\mu$ for $P$: for every $q \in \mathcal{J}$, $\sum_{p} \mu(p)\,P_{pq} = \mu(q)$.
• $\mu$-norm ("muNorm") of a function $x$ on a finite index set: $\|x\|_\mu = \sum_{p} \mu(p)\,\lvert x(p)\rvert$. (The weights $\mu(p)$ enter without an absolute value of their own; here they are positive by hypothesis.)
• Agent-$i$ marginal of the joint matrix ("marginalN"): for $p \in \mathcal{J}$ and $t \in S_i$,

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

i.e. the total mass that row $p$ of $P$ puts on joint points whose $i$-th coordinate is $t$. Note this depends on the whole tuple $p$, not only on $p_i$.

• $\mu$-weighted agent-wise total variation distance ("muAgentTVDistN") between the joint matrix $P$ and a candidate local matrix $M \in \mathbb{R}^{S_i\times S_i}$:

$$D_i(\mu, P, M) \;=\; \sum_{p \in \mathcal{J}} \mu(p)\cdot \tfrac12 \sum_{t \in S_i} \bigl\lvert (\operatorname{marg}_i P)(p,t) - M_{\,p_i\, t} \bigr\rvert .$$

It is a $\mu$-weighted average over joint points, not a maximum.

• Agent-wise measure of Markov entanglement ("entanglementN") for agent $i$:

$$E_i(\mu, P) \;=\; \inf \bigl\{\, D_i(\mu, P, M) \;:\; M \in \mathbb{R}^{S_i\times S_i} \text{ row-stochastic} \,\bigr\},$$

the greatest lower bound of the above distance over all row-stochastic local candidates.

• Measure of reward entanglement ("rewardEntanglement"):

$$R(\mu, r) \;=\; \inf \Bigl\{\, \bigl\| \,p \mapsto r(p) - \textstyle\sum_i f_i(p_i)\, \bigr\|_\mu \;:\; f_i : S_i \to \mathbb{R} \text{ for each } i \,\Bigr\},$$

the greatest lower bound, over all families of local functions, of the $\mu$-weighted average absolute deviation of $r$ from a sum of local functions.

• Bellman fixed point ("IsBellmanQ") for a square matrix $M$ on a finite set $X$, a function $g : X \to \mathbb{R}$, a scalar $\gamma$, and a function $V : X \to \mathbb{R}$: $V(x) = g(x) + \gamma \sum_{y} M_{xy} V(y)$ for every $x \in X$.

The bundle also defines separability of a joint matrix, tensor products of local matrices, product-form transitions, local-transition compatibility, decomposable rewards, and value decomposition. None of those notions occurs in this statement; the only entanglement quantities used are $E_i(\mu,P)$ and $R(\mu,r)$ as expanded above.

The hypotheses

1. $0 \le \gamma$.
2. $\gamma < 1$ (strict).
3. $P$ is row-stochastic on the joint space.
4. $\mu$ is a strictly positive probability distribution on the joint space.
5. $\mu$ is stationary for $P$.
6. For every agent $i$ and every $s \in S_i$: $\lvert r^{\mathrm{loc}}_i(s)\rvert \le r_{\max}(i)$. (This bounds the local functions $r^{\mathrm{loc}}_i$; it says nothing about $r$.)
7. $\bigl\| p \mapsto r(p) - \sum_i r^{\mathrm{loc}}_i(p_i) \bigr\|_\mu = R(\mu, r)$ — i.e. the given family $r^{\mathrm{loc}}$ exactly attains the reward-entanglement infimum.
8. $Q$ is the Bellman fixed point for $P$, $r$, $\gamma$: for every $p \in \mathcal{J}$, $Q(p) = r(p) + \gamma \sum_{q} P_{pq} Q(q)$.
9. Each $P^{\mathrm{loc}}_i$ is row-stochastic.
10. For every agent $i$: $D_i(\mu, P, P^{\mathrm{loc}}_i) = E_i(\mu, P)$ — i.e. each $P^{\mathrm{loc}}_i$ exactly attains the agent-wise entanglement infimum.
11. For every agent $i$, $Q_i$ is the Bellman fixed point for $P^{\mathrm{loc}}_i$, $r^{\mathrm{loc}}_i$, $\gamma$: $Q_i(s) = r^{\mathrm{loc}}_i(s) + \gamma \sum_{t \in S_i} (P^{\mathrm{loc}}_i)_{st} Q_i(t)$ for every $s \in S_i$.

The conclusion

$$\sum_{p \in \mathcal{J}} \mu(p)\, \Bigl\lvert\, Q(p) - \sum_{i=0}^{N-1} Q_i(p_i) \,\Bigr\rvert \;\;\le\;\; \frac{R(\mu, r)}{1-\gamma} \;+\; \frac{4\,\gamma\,\displaystyle\sum_{i=0}^{N-1} E_i(\mu, P)\, r_{\max}(i)}{(1-\gamma)^2}.$$

The grouping is as displayed: the whole sum over agents is multiplied by $4\gamma$ and then divided by $(1-\gamma)^2$; the first term is $R(\mu,r)$ divided by $(1-\gamma)$ (first power). It is a non-strict inequality ($\le$).

Every variable of the conclusion: constrained or free

• $N$ and the family $(S_i)$ — free, apart from finiteness and decidable equality. In particular $N = 0$ is permitted. Each $S_i$ is forced to be nonempty, but only indirectly: hypothesis 4 requires $\sum_{p \in \mathcal{J}} \mu(p) = 1$, which is impossible if $\mathcal{J}$ is empty, and $\mathcal{J}$ nonempty forces every $S_i$ nonempty. (This matters for $r_{\max}$; see below.)
• $\mu$ — constrained: strictly positive, sums to $1$, stationary for $P$ (hyps. 4, 5).
• $P$ — constrained: row-stochastic with $\mu$ stationary (hyps. 3, 5); it also feeds hypotheses 8 and 10. Otherwise arbitrary; nothing forces it to be separable, product-form, or close to any local dynamics.
• $\gamma$ — constrained to $0 \le \gamma < 1$ (hyps. 1, 2). Both denominators $1-\gamma$ and $(1-\gamma)^2$ are therefore strictly positive, so no division-by-zero junk value can arise.
• $r$ — entirely free: no bound, no sign condition, no decomposability condition is imposed on $r$. It is not itself controlled by $r_{\max}$. It appears on both sides of the conclusion: it determines $Q$ through hypothesis 8, and it determines $R(\mu,r)$ on the right.
• $r^{\mathrm{loc}}$ — constrained by hypothesis 7 to be an exact minimizer of the reward-entanglement objective (and by hypothesis 6 to be bounded by $r_{\max}$). Minimizers need not be unique (for instance, a constant may be shifted between two agents' local functions without changing the objective); the conclusion is asserted for every minimizer, together with the $Q_i$ it induces.
• $r_{\max}$ — constrained only from below: hypothesis 6 forces $r_{\max}(i) \ge \max_{s \in S_i} \lvert r^{\mathrm{loc}}_i(s)\rvert \ge 0$ (using that $S_i$ is nonempty, as forced by hypothesis 4). Any larger value is legal, so $r_{\max}$ is free upward. Because $E_i(\mu,P) \ge 0$ and $\gamma \ge 0$, enlarging $r_{\max}(i)$ can only enlarge the right-hand side; it appears nowhere on the left. Had some $S_i$ been empty, hypothesis 6 would have been vacuous for that $i$ and $r_{\max}(i)$ could have been taken arbitrarily negative, which — given a strictly positive $E_i$ — would drive the right-hand side to $-\infty$ while the left-hand side stayed fixed; hypothesis 4 is what blocks this.
• $Q$ — constrained and in fact uniquely determined by hypothesis 8: the equation $(I - \gamma P)Q = r$ has a unique solution because $P$ is row-stochastic and $0 \le \gamma < 1$.
• $P^{\mathrm{loc}}_i$ — constrained: row-stochastic and an exact minimizer of $D_i(\mu,P,\cdot)$ (hyps. 9, 10). Such a minimizer always exists (the row-stochastic matrices on a nonempty finite $S_i$ form a nonempty compact set and $D_i$ is continuous in its matrix argument), but it need not be unique; the conclusion is asserted for every choice.
• $Q_i$ — constrained and uniquely determined by hypothesis 11, given $P^{\mathrm{loc}}_i$, $r^{\mathrm{loc}}_i$ and $\gamma$, for the same invertibility reason.
• $E_i(\mu,P)$ and $R(\mu,r)$ are not free variables: they are determined by $\mu, P, r$.

On falsification by a free variable. The two data with genuinely unbounded freedom are $r$ and $r_{\max}$. $r_{\max}$ occurs only on the right, with the nonnegative coefficient $4\gamma E_i(\mu,P)/(1-\gamma)^2$, so increasing it only weakens the claim, and hypothesis 6 together with the nonemptiness of $S_i$ prevents it from being negative. $r$ occurs on both sides. The residual freedom — the choice of $P$, $\mu$, $r$, and of which minimizers $r^{\mathrm{loc}}$, $P^{\mathrm{loc}}$ are taken — is not resolved by inspection of the statement: no variable appears solely on the left-hand side in a way that a sign or scaling argument alone would exploit. I therefore report no explicit falsifying instantiation.

Joint satisfiability, and degenerate cases

• The hypotheses are jointly satisfiable, including non-degenerately. Take any $N \ge 1$ and any nonempty finite $S_i$; let $P$ be the matrix all of whose entries equal $1/\lvert\mathcal{J}\rvert$ and $\mu$ the uniform distribution on $\mathcal{J}$. Then hypotheses 3, 4, 5 hold. Take $\gamma$ anywhere in $[0,1)$ and $r$ arbitrary; a minimizing family $r^{\mathrm{loc}}$ exists (the objective is the $\mu$-norm distance from $r$ to a fixed finite-dimensional linear subspace of functions on $\mathcal{J}$, so the infimum is attained), giving hypothesis 7; set $r_{\max}(i) = \max_s \lvert r^{\mathrm{loc}}_i(s)\rvert$ for hypothesis 6; take $P^{\mathrm{loc}}_i$ uniform on $S_i$, which makes $D_i = 0 = E_i(\mu,P)$, giving hypotheses 9, 10; and let $Q$, $Q_i$ be the (unique) Bellman solutions. So the statement is not vacuous.
• $N = 0$. Permitted. Then $\mathcal{J}$ is a one-point set (the empty tuple), every sum over agents is $0$, $\mu$ of that point is $1$, $P$ is the $1\times1$ matrix $(1)$, $R(\mu,r) = \lvert r(\star)\rvert$, hypothesis 7 holds automatically, and $Q(\star) = r(\star)/(1-\gamma)$. Both sides of the conclusion equal $\lvert r(\star)\rvert/(1-\gamma)$, so it holds with equality.
• $\gamma = 0$. Permitted. Then $Q = r$ and $Q_i = r^{\mathrm{loc}}_i$, the second term on the right vanishes, and both sides equal $R(\mu,r)$ by hypothesis 7 — equality again.
• Empty $S_i$ / empty joint space. Ruled out by hypothesis 4, as noted above.
• The infima are genuine. Both defining sets are nonempty (for $R$: take all $f_i = 0$; for $E_i$: take any row-stochastic $M$, which exists since $S_i$ is nonempty and finite) and are bounded below by $0$, since $\mu > 0$ and the summands are absolute values. Hence $R(\mu,r) \ge 0$ and $E_i(\mu,P) \ge 0$, and neither infimum falls back on the convention that assigns the value $0$ to the infimum of an empty or unbounded-below set of reals.
• Both attainment hypotheses (7 and 10) are equalities, not inequalities: the given $r^{\mathrm{loc}}$ and $P^{\mathrm{loc}}_i$ must sit exactly at the respective infima, not merely near them.