Paper deep dive
A Unified Framework for Locality in Scalable MARL
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 7/21/2026, 12:48:33 AM
Summary
This paper presents a unified framework for establishing value-locality in scalable multi-agent reinforcement learning (MARL) within the average-reward setting. It decomposes the policy-induced interdependence matrix into environment sensitivity and policy sensitivity components. By analyzing the spectral radius of this decomposed matrix, the authors derive a stricter locality certificate than traditional Dobrushin row-sum bounds. The work demonstrates that for softmax policies, the temperature parameter directly controls locality, enabling exponential decay of truncation bias in block-coordinate policy improvement algorithms.
Entities (10)
Relation Signals (6)
Spectral Radius → controls → Poisson Solution Decay
confidence 93% · The spectral radius of H^pi ... then controls the decay of the average-reward Poisson solution
Softmax Temperature → controls → Locality
confidence 92% · For temperature-tau softmax policies we get Pi(pi) <= L/(2 tau), so the softmax temperature directly controls locality.
Dobrushin Row-Sum Bound → isoutperformedby → Spectral Radius Certificate
confidence 90% · the spectral certificate rho(H^pi)<1 is strictly weaker than the row-sum condition ... and applies in regimes where policy-independent action-supremum bounds used in prior Dobrushin-style work cannot.
Message-Passing Radius → determinesdecayrateof → Truncation Bias
confidence 89% · truncation bias decays exponentially in the message-passing radius kappa
Environment Sensitivity Matrix → iscomponentof → Interdependence Matrix
confidence 85% · We split C^pi into pieces that separately track environment sensitivity and policy sensitivity, C^pi <= E^s + E^a Pi(pi)
Policy Reactivity Matrix → iscomponentof → Interdependence Matrix
confidence 85% · We split C^pi into pieces that separately track environment sensitivity and policy sensitivity, C^pi <= E^s + E^a Pi(pi)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Scalable methods for networked multi-agent reinforcement learning let each agent plan using only a small neighborhood of the agent graph. This works only when the system is value-local, meaning a perturbation at one agent affects the long-run value at another agent weakly when the two are far apart. In the average-reward setting, the standard way to certify locality is the Dobrushin row-sum bound on a single matrix $C^\pi$ that captures how each agent's next state depends on each other agent's current state. To make this matrix easy to work with, prior work bounds it by a supremum over joint actions. The resulting bound is independent of the policy, but it is loose whenever the policy never picks the worst-case action. We split $C^\pi$ into pieces that separately track environment sensitivity and policy sensitivity, $C^\pi \preceq E^{\mathrm s}+E^{\mathrm a}\Pi(\pi)$, where $E^{\mathrm s}$ measures how the next state moves with the current state, $E^{\mathrm a}$ measures how it moves with the current action, and $\Pi(\pi)$ measures how reactive the policy is to changes in state. The spectral radius of $H^\pi := E^{\mathrm s}+E^{\mathrm a}\Pi(\pi)$ then controls the decay of the average-reward Poisson solution, and the spectral certificate $\rho(H^\pi)<1$ is strictly weaker than the row-sum condition $\|H^\pi\|_\infty<1$ on the same matrix and applies in regimes where policy-independent action-supremum bounds used in prior Dobrushin-style work cannot. For temperature-$\tau$ softmax policies we get $\Pi(\pi)\le L/(2\tau)$, so the softmax temperature directly controls locality. We use this decay result to give a deterministic oracle guarantee for a block-coordinate KL-proximal policy-improvement template whose truncation bias decays exponentially in the message-passing radius $\kappa$.
Tags
Links
- Source: https://arxiv.org/abs/2602.16966v2
- Canonical: https://arxiv.org/abs/2602.16966v2
Trouble viewing inline? Open PDF directly →
Full Text
96,648 characters extracted from source content.
Expand or collapse full text
A Unified Framework for Locality in Scalable MARL Chakraborty† .chakraborty@colorado.edu Kiran Rege†111Equal Contribution with S. Chakraborty. .rege@colorado.edu Monteleoni†‡ .monteleoni@colorado.edu Chen† .chen@colorado.edu †University of Colorado Boulder USA. ‡INRIA Paris France Abstract Scalable methods for networked multi-agent reinforcement learning let each agent plan using only a small neighborhood of the agent graph. This works only when the system is value-local, meaning a perturbation at one agent affects the long-run value at another agent weakly when the two are far apart. In the average-reward setting, the standard way to certify locality is the Dobrushin row-sum bound on a single matrix CπC^π that captures how each agent’s next state depends on each other agent’s current state. To make this matrix easy to work with, prior work bounds it by a supremum over joint actions. The resulting bound is independent of the policy, but it is loose whenever the policy never picks the worst-case action. We split CπC^π into pieces that separately track environment sensitivity and policy sensitivity, Cπ⪯Es+EaΠ(π)C^π E^s+E^a (π), where EsE^s measures how the next state moves with the current state, EaE^a measures how it moves with the current action, and Π(π) (π) measures how reactive the policy is to changes in state. The spectral radius of Hπ:=Es+EaΠ(π)H^π:=E^s+E^a (π) then controls the decay of the average-reward Poisson solution, and the spectral certificate ρ(Hπ)<1ρ(H^π)<1 is strictly weaker than the row-sum condition ‖Hπ‖∞<1\|H^π\|_∞<1 on the same matrix and applies in regimes where policy-independent action-supremum bounds used in prior Dobrushin-style work cannot. For temperature-τ softmax policies we get Π(π)≤L/(2τ) (π)≤ L/(2τ), so the softmax temperature directly controls locality. We use this decay result to give a deterministic oracle guarantee for a block-coordinate KL-proximal policy-improvement template whose truncation bias decays exponentially in the message-passing radius κ. keywords: Multi-agent Reinforcement Learning 1 Introduction Cooperative multi-agent reinforcement learning on networked systems faces a curse of dimensionality: the joint state and action spaces grow exponentially in the number of agents n, so even when the model factors into local interactions, centralized planning is infeasible (complexity_blondel2000survey; complexity_papadimitriou1999complexity). Scalable networked MARL methods address this by letting each agent plan using only a κ-hop neighborhood of the agent graph (qu_scalabale_marl_2020; qu2019scalable; lin2020distributed). Their complexity scales with neighborhood size rather than network size. They are sound, though, only when the system itself is local, meaning that a perturbation at one agent affects the long-run value at a distant agent by an amount that decays exponentially in their graph distance. We call this property value-locality. When it holds, κ-hop truncation costs an error that vanishes exponentially in κ. So the question is when value-locality holds. In the standard γ-discounted setting it is automatic, because the discount factor γ<1γ<1 multiplies every step of the Bellman backup and produces decay regardless of the agent interaction structure. The average-reward setting (γ=1γ=1) has no such temporal multiplier. The role of the value function there is played by the bias function hπh^π, which measures, for each starting state s, the long-run advantage of starting in s relative to starting from the stationary distribution of π. It is defined up to an additive constant by the average-reward Poisson equation hπ−Tπhπ=rπ−r¯πh^π-T^πh^π=r^π- r^π, where TπT^π is the one-step expectation operator under π and r¯π r^π is the average reward. Whatever decay hπh^π has must come from the decay of one-step influence under TπT^π. Existing average-reward guarantees (qu_scalabale_marl_2020) get this via a Dobrushin coupling condition. The idea is to build an n×n× n matrix CπC^π whose entry Cj←iπC^π_j← i is the largest change a perturbation of sis_i can cause in the next-state distribution of agent j. If every row sum of CπC^π is below one, then TπT^π is a contraction in the seminorm ‖δ(f)‖∞=maxisupx−i=y−i|f(x)−f(y)|\|δ(f)\|_∞= _i _x_-i=y_-i|f(x)-f(y)|, the largest single-coordinate oscillation of f, and iterating the contraction gives exponential decay of hπh^π in graph distance. The Dobrushin condition is convenient because the bound on CπC^π does not depend on the policy: one takes a supremum over joint actions when measuring how much an action change moves the next state. That is also why the condition is conservative. Consider two agents in which agent 22’s next state copies agent 11’s last action, regardless of state. The worst-case action move is maximal, so the supremum says the system is globally coupled. But if agent 11’s policy barely reacts to its own state, then flipping s1s_1 only weakly moves the distribution of a1a_1, which only weakly moves the next-state marginal of agent 22. In closed loop, s1s_1 and s2′s _2 are nearly independent, so the system is value-local. The Dobrushin test cannot see this because it threw the policy away. To recover that information, we decompose the policy-induced one-step interdependence matrix into an environment piece and a policy piece. Using the total variation distance TV(μ,ν)=12∑x|μ(x)−ν(x)|TV(μ,ν)= 12 _x|μ(x)-ν(x)|, define Ej←isE^s_j← i as the worst-case TV between Pj(⋅∣s,a)P_j(· s,a) and Pj(⋅∣s′,a)P_j(· s ,a) over pairs (s,s′)(s,s ) that differ only on coordinate i, with the action fixed. Define Ej←iaE^a_j← i the same way for an action change with the state fixed. Define Πk←i(π) _k← i(π) as the TV-sensitivity of agent k’s action distribution to a change in sis_i. Of these, EsE^s and EaE^a depend only on the environment; Π(π) (π) depends on the policy. Our first result (Proposition 3.1) is the entrywise bound Cπ⪯Es+EaΠ(π).C^π\ \ E^s+E^a\, (π). The product EaΠ(π)E^a (π) makes the cancellation visible. The action channel EaE^a can be large, but if the policy is smooth (Π(π) (π) small) the closed-loop influence is small anyway. Write Hπ:=Es+EaΠ(π)H^π:=E^s+E^a (π). Our second result (Theorem 3.3) is that whenever the spectral radius ρ(Hπ)ρ(H^π) (the largest eigenvalue magnitude of HπH^π) is below one, the Poisson solution has δ(hπ)≤(I−(Hπ)⊤)−1δ(rπ)δ(h^π)≤(I-(H^π) )^-1δ(r^π), where the right-hand side is the matrix-geometric (Neumann) series ∑t≥0((Hπ)⊤)tδ(rπ) _t≥ 0((H^π) )^tδ(r^π). Our certificate is strictly weaker than prior ones in two senses. First, on the same comparison matrix, replacing the row-sum condition by the spectral-radius condition is strictly weaker since ρ(M)≤‖M‖∞ρ(M)≤\|M\|_∞ for any nonnegative M. Second, HπH^π is policy-dependent and can be much smaller than the policy-independent action-supremum bounds used in prior Dobrushin-style guarantees, so the resulting certificate applies in regimes where those prior conditions are silent. The policy factor Π(π) (π) is something a learning algorithm has control over. For temperature-τ softmax policies (Geist2019ATO; HaarnojaZAL18), the policy class used in entropy-regularized control and KL-proximal updates, Lemma 4.3 gives Πk←i(π)≤min1,Lk←i/(2τ) _k← i(π)≤ \1,\,L_k← i/(2τ)\, where Lk←iL_k← i is the coordinatewise Lipschitz constant of the logit. Raising τ therefore directly tightens the certificate on HπH^π, and Section 4 works out the tradeoff between certifying locality (higher τ) and approaching the unregularized optimum (lower τ). Section 5 uses the decay result to give a deterministic oracle guarantee for a block-coordinate KL-proximal improvement template. The same Neumann tail λκ+1λ^κ+1 appears in two places: in the locally computable certificate an agent uses to decide whether κ hops are enough, and in the per-step improvement bound. The certificate is genuinely local. The truncated Poisson surrogate used in the analysis is an oracle object in the general model; turning it into something locally computable needs additional structure on observation scopes or function approximation, which we leave to follow-up work. We summarize related work next; the appendix has more. Related work. Exponential decay of value on networked MDPs was first studied in the scalable networked MARL line of work (qu_scalabale_marl_2020; qu2019scalable; lin_scalable_marl_stochastic_2021; lin2020distributed), which proves discounted and average-reward locality results under a graph-local transition assumption Pi(si′∣sNi,ai)P_i(s _i s_N_i,a_i) and a Dobrushin row-sum bound on CπC^π. Our setting allows PiP_i to depend on the full (s,a)(s,a) and assumes no graph upfront, since we derive a graph from the support of HπH^π after the fact. Older work on factored MDPs (kearns1999efficient; factor_guestrin2003efficient) and weakly coupled MDPs (weakly_mdp_meuleau1998solving) uses different forms of locality, typically asking for local rewards or independent transitions. The policy-dependent angle here parallels work that ties decay rates to policy regularization in single-agent control, but to our knowledge gives the first policy-dependent spectral certificate of value-locality for average-reward networked MARL. Function-approximation MARL methods (zhang2018fully; lowe2017multi) and independent learners (tan1993multi; matignon2012independent) attack scalability differently and do not certify locality. Appendix A expands on this. 2 Setup and preliminaries Consider a system of n agents. Each agent i∈[n]i∈[n] has a finite state space iS_i and a finite action space iA_i. The joint spaces are =∏iS= _iS_i and =∏iA= _iA_i, with elements written s=(s1,…,sn)s=(s_1,…,s_n) and a=(a1,…,an)a=(a_1,…,a_n), and s−is_-i, a−ia_-i for the profiles that exclude agent i. At time t the joint state is sts^t, a joint action at∼π(⋅∣st)a^t π(· s^t) is drawn, and the next state st+1∼P(⋅∣st,at)s^t+1 P(· s^t,a^t). We assume the kernel factors as P(s′∣s,a)=∏i=1nPi(si′∣s,a)P(s s,a)= _i=1^nP_i(s _i s,a), so that given (s,a)(s,a) the next-state coordinates are conditionally independent across agents. Each PiP_i is still allowed to depend on the full (s,a)(s,a). This is more permissive than the typical networked-MARL assumption Pi(si′∣sNi,ai)P_i(s _i s_N_i,a_i) used in (qu_scalabale_marl_2020; lin_scalable_marl_stochastic_2021), which fixes a graph NiN_i ahead of time. We do not, since we want the locality structure to come out of the analysis rather than the modeling assumptions. Policies are of product form π(a∣s)=∏i=1nπi(ai∣sOi)π(a s)= _i=1^n _i(a_i s_O_i), where the observation scope Oi⊆[n]O_i [n] is the set of state coordinates agent i’s policy actually depends on. Taking Oi=[n]O_i=[n] recovers globally conditioned product policies; smaller OiO_i models agents that observe only locally. The kernel induced by π is Pπ(s′∣s)=∑a∈(∏i=1nPi(si′∣s,a))(∏j=1nπj(aj∣sOj)).P^π(s s)= _a ( _i=1^nP_i(s _i s,a) ) ( _j=1^n _j(a_j s_O_j) ). Average reward and the Poisson equation. For the average-reward analysis we restrict to policies π under which PπP^π is irreducible on S, so that it has a unique stationary distribution dπd^π. Given a per-step reward r:×→ℝr:S×A , write rπ(s)=∑ar(s,a)∏kπk(ak∣sOk)r^π(s)= _ar(s,a) _k _k(a_k s_O_k) for the expected one-step reward in state s and r¯π=∑sdπ(s)rπ(s) r^π= _sd^π(s)r^π(s) for the average reward under π. The object that plays the role of the value function in this setting is the bias function hπh^π, which measures the long-run advantage of starting in s relative to starting from stationarity and is defined up to a constant by the Poisson equation hπ−Tπhπ=rπ−r¯π,Tπf(s):=S′∼Pπ(⋅∣s)[f(S′)].h^π-T^πh^π\ =\ r^π- r^π, T^πf(s):= *E_S P^π(· s)[f(S )]. This hπh^π is used by policy-gradient and policy-improvement updates the same way the discounted value function is. When we say the system is value-local, we mean exactly that the coordinatewise oscillations of hπh^π decay quickly in graph distance. Discounted-setting corollaries are in the appendix. Coordinatewise oscillations. The natural way to quantify how much an agent’s reward or value depends on every other agent is the coordinatewise oscillation. For a bounded f:→ℝf:S , the i-oscillation δi(f)=supx,y∈:x−i=y−i|f(x)−f(y)| _i(f)\ =\ _x,y :\,x_-i=y_-i|f(x)-f(y)| is the largest change f can undergo when only coordinate i changes; equivalently, it is the Lipschitz constant of f under a single-coordinate Hamming change. Write δ(f)=(δi(f))i=1nδ(f)=( _i(f))_i=1^n for the vector of oscillations and ‖δ(f)‖∞=maxiδi(f)\|δ(f)\|_∞= _i _i(f) for its maximum. The seminorm ‖δ(⋅)‖∞\|δ(·)\|_∞ is the standard object in Dobrushin-type arguments for interacting particle systems and Glauber dynamics (Dobruschin1968TheDO; Martinelli1999); basic properties are in Appendix E.3. Spatial truncation works precisely when the entries of δ(hπ)δ(h^π) are small at agents far from any source of reward variation. Three sensitivity matrices. We measure one-step coupling with three n×n× n nonnegative matrices. The first two depend only on the environment; the third depends on the policy. Ej←is E^s_j← i =sups,s′∈:s−i=s−i′a∈TV(Pj(⋅∣s,a),Pj(⋅∣s′,a)), \ =\ _ subarraycs,s :\,s_-i=s _-i\\ a subarrayTV\! (P_j(· s,a),\,P_j(· s ,a) ), (state channel) Ej←ia E^a_j← i =sups∈a,a′∈:a−i=a−i′TV(Pj(⋅∣s,a),Pj(⋅∣s,a′)), \ =\ _ subarraycs \\ a,a :\,a_-i=a _-i subarrayTV\! (P_j(· s,a),\,P_j(· s,a ) ), (action channel) Πj←i(π) _j← i(π) =sups,s′:s−i=s−i′TV(πj(⋅∣sOj),πj(⋅∣sOj′)). \ =\ _s,s :\,s_-i=s _-iTV\! ( _j(· s_O_j),\, _j(· s _O_j) ). (policy reactivity) In words, Ej←isE^s_j← i is the largest jump in j’s next-state law that a change of sis_i can cause with the action held fixed; Ej←iaE^a_j← i is the corresponding quantity for an action change at i with the state held fixed; and Πj←i(π) _j← i(π) is the largest jump in j’s action distribution that a change of sis_i can cause. The last is zero whenever i∉Oji∉ O_j. The policy-induced closed-loop influence of i on the next-state marginal of j is Cj←iπ=sups,s′:s−i=s−i′TV(Pjπ(⋅∣s),Pjπ(⋅∣s′)),Pjπ(⋅∣s)=∑aPj(⋅∣s,a)∏kπk(ak∣sOk),C^π_j← i= _s,s :\,s_-i=s _-iTV\! (P^π_j(· s),P^π_j(· s ) ), P^π_j(· s)= _aP_j(· s,a) _k _k(a_k s_O_k), and CπC^π is the matrix that prior work bounds by Dobrushin row sums. The next section decomposes it into the environment and policy pieces and replaces the row-sum bound with a spectral one. 3 Policy-induced influence and locality This section gives the decomposition of CπC^π that powers everything else, the spectral condition that controls how the Poisson solution decays, and the resulting locality of the average-reward bias function. Proofs are in the appendix. A perturbation of sis_i reaches the next-state marginal of j along two routes in one step. The first is direct through the environment: even with the action fixed, a change in sis_i can move Pj(⋅∣s,a)P_j(· s,a). The second is indirect, through the policy and back into the environment, since changing sis_i shifts the action distribution of each agent k, and a change in aka_k can in turn move j’s next-state law. The direct route is bounded by Ej←isE^s_j← i. The indirect route factors as ∑kEj←kaΠk←i(π) _kE^a_j← k _k← i(π), picking up the action-channel weight Ej←kaE^a_j← k from the policy-action-state hop and the policy weight Πk←i(π) _k← i(π) from the state-policy hop. Proposition 3.1 (Decomposition of policy-induced influence). For any product policy π and any factorized synchronous dynamics on a finite state space, Cπ⪯Es+EaΠ(π)C^π E^s+E^a (π) entrywise. Equivalently, Cj←iπ≤Ej←is+∑kEj←kaΠk←i(π)C^π_j← i≤ E^s_j← i+ _kE^a_j← k _k← i(π) for every i,ji,j. The proof inserts an intermediate distribution that uses the new policy weights but the old kernel. It then bounds the two halves separately, once by a TV-convexity step (which gives the EsE^s term) and once by a maximal coupling on the actions (which gives the EaΠE^a term). Full details are in Appendix B.1. A two-agent example. Take n=2n=2 binary agents, i=i=0,1S_i=A_i=\0,1\. Let P1P_1 be constant (agent 11’s next state is independent of everything), and let agent 22’s next state copy agent 11’s action: P2(s2′=1∣s,a)=a1=1P_2(s _2=1 s,a)=1\a_1=1\. Then Es=0E^s=0 and E2←1a=1E^a_2← 1=1 with all other entries of EaE^a equal to zero. An action-supremum bound stops here and reports the system as globally coupled, since E2←1a=1E^a_2← 1=1 is as large as it can be. Now suppose agent 11’s policy changes by at most α in TV when s1s_1 flips, and that π1 _1 does not observe s2s_2 (so Π1←2=0 _1← 2=0). Then Π1←1(π)=α _1← 1(π)=α, and Proposition 3.1 gives C2←1π≤E2←1s+E2←1aΠ1←1+E2←2aΠ2←1=α.C^π_2← 1\ ≤\ E^s_2← 1+E^a_2← 1 _1← 1+E^a_2← 2 _2← 1\ =\ α. The closed-loop coupling is as small as the policy. The same bound handles the failure mode: if π1 _1 is sharp in s1s_1 (α near 11), it returns α and recovers the action-supremum answer. Smoothing the policy only helps when there is policy reactivity to smooth out. Appendix E.1 works through a complementary instance. We now convert the entrywise decomposition into a one-step contraction. Lemma 3.2 (Oscillation bound via HπH^π). Let Tπf(s)=[f(St+1)∣St=s]T^πf(s)= *E[f(S_t+1) S_t=s] under the synchronous update with product policy and factorized kernel. Then δi(Tπf)≤∑jHj←iπδj(f) _i(T^πf)≤ _jH^π_j← i _j(f) for every i and every bounded f, where Hπ≔Es+EaΠ(π)H^π E^s+E^a (π). In vector form, δ(Tπf)≤(Hπ)⊤δ(f)δ(T^πf)≤(H^π) δ(f). Iterating Lemma 3.2 turns a spectral bound on HπH^π into global decay of TπT^π, which in turn bounds the Poisson solution. Theorem 3.3 (Policy-uniform contraction and Poisson decay). Let Πpol _pol be a compact class of product policies, set Hπ≔Es+EaΠ(π)H^π E^s+E^a (π) and λ⋆≔supπ∈Πpolρ(Hπ) _ _π∈ _polρ(H^π), and assume λ⋆<1 _ <1. For every π∈Πpolπ∈ _pol, every bounded f, and every t≥0t≥ 0, δ((Tπ)tf)≤((Hπ)⊤)tδ(f),δ ((T^π)^tf )≤ ((H^π) )^tδ(f), and for every λ¯∈(λ⋆,1) λ∈( _ ,1) there exists Cλ¯≥1C_ λ≥ 1 independent of t,πt,π such that ‖δ((Tπ)tf)‖∞≤Cλ¯λ¯t‖δ(f)‖∞\|δ((T^π)^tf)\|_∞≤ C_ λ λ^t\|δ(f)\|_∞. If PπP^π is irreducible for every π∈Πpolπ∈ _pol, with stationary distribution dπd^π, then the Poisson equation hπ−Tπhπ=rπ−r¯πh^π-T^πh^π=r^π- r^π has a solution unique up to an additive constant, and every solution satisfies δ(hπ)≤∑t=0∞((Hπ)⊤)tδ(rπ)≤(I−(Hπ)⊤)−1δ(rπ).δ(h^π)≤ _t=0^∞ ((H^π) )^tδ(r^π)≤ (I-(H^π) )^-1δ(r^π). Theorem 3.3 does not assume any agent graph upfront. A graph does emerge, though, through the directed support graph GHπG_H^π of HπH^π, in which i→ji→ j is an edge whenever Hj←iπ>0H^π_j← i>0 (agent i’s state directly affects agent j’s next state in one step under π). The matrix power ((Hπ)⊤)t((H^π) )^t then has a clean path interpretation: ((Hπ)⊤)ijt((H^π) )^t_ij is a path-weighted sum, where each contributing path runs from i to j in exactly t edges of GHπG_H^π and has weight equal to the product of HπH^π entries along it. Three consequences follow. • Path accumulation. δi(hπ) _i(h^π) is bounded by a sum over all directed paths in GHπG_H^π starting at i and ending at any agent j where the reward varies, weighted by HπH^π along the path. • Exponential attenuation. The contribution of paths of length t is O(λ¯t)O( λ^t), so agents far downstream of i in GHπG_H^π matter exponentially less. • Truncation error. Ignoring agents more than κ hops downstream of i drops the tail of the Neumann series, which is bounded by C1−λλ¯κ+1‖δ(rπ)‖∞ C1-λ λ^κ+1\|δ(r^π)\|_∞. If Es,Ea,Π(π)E^s,E^a, (π) are each local with respect to some underlying graph G, then GHπG_H^π is a finite-radius closure of G. It need not equal G, because EaΠ(π)E^a (π) can create new closed-loop edges. An action of agent k that affects j, combined with a policy at k that reacts to sis_i, produces a closed-loop edge i→ji→ j even when i and j are not graph-neighbors in G. Theorem 3.3 recovers and strengthens the locality results of (qu_scalabale_marl_2020; lin_scalable_marl_stochastic_2021): the spectral-radius condition is strictly weaker than the row-sum one on any single comparison matrix, and the policy-dependent matrix HπH^π can be much smaller than the policy-independent action-supremum bounds those works use, so ρ(Hπ)<1ρ(H^π)<1 can hold in regimes where their row-sum conditions fail. The two-agent example above is one such case; Appendix B.4 works out the formal embedding. The reward enters Theorem 3.3 only through δ(rπ)δ(r^π), so a reward that decomposes locally produces a sparse δ(rπ)δ(r^π) and tightens the bound automatically; no separate local-reward assumption is needed. A small numerical instance of the gap. The gap between ρ(Hπ)ρ(H^π) and ‖Hπ‖∞\|H^π\|_∞ can be large even on small matrices, and it is easy to build closed-loop matrices that our condition certifies but the Dobrushin row-sum bound does not. For n=2n=2 agents, take Hπ=(0.600.60.6).H^π\ =\ pmatrix0.6&0\\ 0.6&0.6 pmatrix. With our convention Hj←iπ=Hπ[j,i]H^π_j← i=H^π[j,i], this models a system in which agent 11 influences agent 22’s next state (H2←1π=0.6H^π_2← 1=0.6) but agent 22 does not influence agent 11 (H1←2π=0H^π_1← 2=0). The row sums are 0.60.6 and 1.21.2, so ‖Hπ‖∞=1.2\|H^π\|_∞=1.2 and the row-sum condition is violated. The eigenvalues are both 0.60.6, so ρ(Hπ)=0.6ρ(H^π)=0.6 and Theorem 3.3 certifies locality with decay rate arbitrarily close to 0.60.6. A κ-hop truncation costs error O(0.6κ+1)O(0.6^κ+1), so κ=10κ=10 already drives the truncation error below 10−210^-2 while the row-sum diagnostic offers no guarantee at any κ. The asymmetry is what creates the gap: closed-loop influence flows one way (1→21→ 2) and decays in one hop in the reverse direction, even though one row sum is above one. sis_isj′s _jdirect route: Ej←isE^s_j← iaka_kΠk←i(π) _k← i(π)Ej←kaE^a_j← kindirect route, summed over k: ∑kEj←kaΠk←i(π) _kE^a_j← k\, _k← i(π) Figure 1: The decomposition Cj←iπ≤Ej←is+∑kEj←kaΠk←i(π)C^π_j← i≤ E^s_j← i+ _kE^a_j← k _k← i(π), written as two routes from a perturbation of sis_i to the next-state marginal of j. The direct route through the environment has weight Ej←isE^s_j← i. The indirect route passes through each intermediate action aka_k, picking up a factor Πk←i(π) _k← i(π) for the state-to-action hop and Ej←kaE^a_j← k for the action-to-next-state hop, then sums over k. Discounted setting. For the standard γ-discounted Bellman operator TγπT^π_γ, the one-step bound becomes δ(Tγπf)≤γ(Hπ)⊤δ(f)δ(T^π_γf)≤γ(H^π) δ(f), so locality is certified whenever γρ(Hπ)<1γρ(H^π)<1. The decay rate is set jointly by the temporal factor γ and the structural factor ρ(Hπ)ρ(H^π). With γ=0.99γ=0.99 and ρ(Hπ)=0.5ρ(H^π)=0.5, for instance, taking λ~=0.5 λ=0.5 as a certificate gives a neighborhood of order 77 to reach error 10−210^-2, against roughly 458458 from a γ-only bound. The same analysis carries over to the asynchronous Glauber-style update; see Appendix B.6. 4 Controlling policy sensitivity via softmax temperature The decay rate in Theorem 3.3 is ρ(Hπ)=ρ(Es+EaΠ(π))ρ(H^π)=ρ(E^s+E^a (π)). The environment terms Es,EaE^s,E^a are fixed once the MDP is given. The policy term Π(π) (π) is set by the policy class, so it is what a learning algorithm can change. A natural way to keep Π(π) (π) small is to restrict the policy class to state-to-action maps that are smooth. The temperature-τ softmax class (Geist2019ATO; HaarnojaZAL18) is the standard such class, and it is the policy class used in entropy-regularized control, soft actor-critic, and KL-proximal updates, where τ is a hyperparameter of the algorithm. We show in this section that the same τ that controls the reward-versus-entropy tradeoff in those methods also bounds Π(π) (π) entrywise, and so bounds the locality certificate of Theorem 3.3. All proofs are in Appendix C. Setup. The entropy-regularized average-reward objective is Jτ(π)=s∼dπ,a∼π(⋅∣s)[r(s,a)−τ∑k=1nlogπk(ak∣sOk)],J_τ(π)\ =\ *E_s d^π,\ a π(· s)\! [r(s,a)-τ _k=1^n _k(a_k s_O_k) ], the average-reward analogue of the discounted soft-Bellman objective. We study the temperature-τ softmax policy class commonly used in entropy-regularized and KL-proximal methods. Definition 4.1 (Softmax policy). A policy π is a temperature-τ softmax policy if for each agent k there is a logit function gk:Ok×k→ℝg_k:S_O_k×A_k such that πk(ak∣sOk)∝exp(gk(sOk,ak)/τ) _k(a_k s_O_k) (g_k(s_O_k,a_k)/τ). How reactive a softmax policy is to its state input is controlled by τ together with how reactive the logit itself is. Definition 4.2 (Logit Lipschitz constant). For a logit function gkg_k, the one-coordinate logit constant with respect to state i is Lk←i:=sups−i=s−i′‖gk(sOk,⋅)−gk(sOk′,⋅)‖∞L_k← i\ :=\ _s_-i=s _-i\|g_k(s_O_k,·)-g_k(s _O_k,·)\|_∞. Lk←iL_k← i is a property of the logit parameterization alone and does not involve τ. For a linear logit gk(s,a)=⟨wk,a,ϕ(s)⟩g_k(s,a)= w_k,a,φ(s) with features ϕφ of single-coordinate oscillation δi(ϕ) _i(φ), one can take Lk←i≤supa2‖wk,a‖δi(ϕ)L_k← i≤ _a2\|w_k,a\| _i(φ), so L is set entirely by the feature design and the weight magnitudes and can be precomputed. Lemma 4.3 (Softmax temperature controls Π(π) (π)). For a temperature-τ softmax policy, Πk←i(π)≤min1,Lk←i/(2τ) _k← i(π)\ ≤\ \1,\,L_k← i/(2τ)\ for all k,i∈[n]k,i∈[n]. The proof bounds the TV distance between two softmax distributions by a sigmoidal function of the difference of their logits, then linearizes at zero with Lipschitz constant 1/(2τ)1/(2τ). The cap at 11 is the trivial TV bound. Writing L=[Lk←i]L=[L_k← i] for the matrix of logit constants and applying the lemma entrywise gives Π(π)⪯min,L/(2τ) (π) \1,L/(2τ)\. The spectral radius ρ(M)ρ(M) of a nonnegative matrix M is entrywise monotone (Perron–Frobenius), so an entrywise upper bound on HπH^π gives an upper bound on ρ(Hπ)ρ(H^π): Hπ⪯Es+EaL2τ⟹ρ(Hπ)≤ρ(Es+EaL2τ).H^π\ \ E^s+E^a\, L2τ ρ(H^π)\ ≤\ ρ\! (E^s+E^a\, L2τ ). The right-hand side is the quantity a practitioner actually computes. It is built from the (known) environment matrices Es,EaE^s,E^a and the (designed) logit constants L, and its spectral radius is monotone nonincreasing in τ. Locality–optimality tradeoff. The behavior at the two ends of the temperature range is easy to describe. As τ→∞τ→∞, the softmax policy approaches uniform on every state, Π(π)→0 (π)→ 0, and Hπ→EsH^π→ E^s. Whenever ρ(Es)<1ρ(E^s)<1, a high enough τ certifies locality regardless of how strong the action channel is. The cost is that the policy is far from greedy and the objective JτJ_τ deviates from the unregularized average reward by O(τlog||)O(τ |A|). As τ→0τ→ 0 the policy becomes deterministic, Π(π) (π) saturates near 11 wherever the logit ordering is sensitive to the state, and ρ(Hπ)ρ(H^π) can cross one and break the certificate. In an algorithmic loop this gives a clean recipe. Pick a minimum temperature τmin _ at which ρ(Es+EaL/(2τmin))<1ρ(E^s+E^aL/(2 _ ))<1 holds with margin, run the entropy-regularized improvement at τ=τminτ= _ with a truncation radius κ chosen to push the bias below the desired accuracy, and either stop there (accepting the regularization bias) or anneal τ downward in stages, increasing κ at each stage to compensate. Appendix E.2 works through a quantitative instance. 5 An oracle framework for localized evaluation and block-coordinate improvement We now use the decay result of Section 3 to give a deterministic oracle guarantee for a block-coordinate KL-proximal improvement template. The section deliberately separates the structural effect of locality from the orthogonal issues of statistical estimation and function approximation, since the latter can be addressed by standard tools once the structural picture is clear. The only object in our framework that is guaranteed to be locally computable is the certificate below; the truncated Poisson surrogate is an oracle quantity used to bound bias. Recall the support graph GHπG_H^π of Hπ=Es+EaΠ(π)H^π=E^s+E^a (π), with edge i→ji→ j whenever Hj←iπ>0H^π_j← i>0. When HπH^π is sparse, the κ-hop neighborhoods in GHπG_H^π are small. Phase 1: locality certificate. Set bπ=δ(rπ)b^π=δ(r^π). Theorem 3.3 gives δ(hπ)≤∑t≥0((Hπ)⊤)tbπδ(h^π)≤ _t≥ 0((H^π) )^tb^π. Truncating this Neumann series at depth κ yields the computable certificate δ^(κ)≔∑t=0κ((Hπ)⊤)tbπ. δ^(κ) _t=0^κ ((H^π) )^tb^π. The i-th component δ^i(κ) δ^(κ)_i is a sum over directed paths in GHπG_H^π of length at most κ starting at i (weighted by HπH^π entries along the path) and accumulating bjπb^π_j at each endpoint j. It depends only on the κ-hop out-ball of i in GHπG_H^π (the agents reachable from i in at most κ directed edges) and is computable in κ rounds of message passing along the reverse edges of that ball. For the bias analysis we also use the truncated Poisson surrogate h^κπ≔∑t=0κ(Tπ)t(rπ−r¯π) h_κ^π _t=0^κ(T^π)^t(r^π- r^π). Theorem 5.1 (Localized certificate and truncation bias). Let π be a product policy with PπP^π irreducible, and suppose ‖((Hπ)⊤)t‖∞→∞≤Cλt\|((H^π) )^t\|_∞→∞≤ Cλ^t for some C≥1C≥ 1, λ∈(0,1)λ∈(0,1). Let R(κ)=∑t>κ((Hπ)⊤)tbπR^(κ)= _t>κ((H^π) )^tb^π. Every solution hπh^π of the Poisson equation satisfies δ(hπ)≤δ^(κ)+R(κ)δ(h^π)≤ δ^(κ)+R^(κ) with ‖R(κ)‖∞≤C1−λλκ+1‖bπ‖∞\|R^(κ)\|_∞≤ C1-λ^κ+1\|b^π\|_∞, and the oracle bias of h^κπ h_κ^π satisfies Bκπ≔infc∈ℝ‖h^κπ−hπ−c‖∞≤12‖R(κ)‖1≤nC2(1−λ)λκ+1‖bπ‖∞.B_κ^π _c \| h_κ^π-h^π-c1\|_∞\ ≤\ 12\,\|R^(κ)\|_1\ ≤\ nC2(1-λ)λ^κ+1\|b^π\|_∞. The two bounds play different roles. ‖R(κ)‖∞\|R^(κ)\|_∞ is the residual error of the certificate the agent actually computes. BκπB_κ^π is the oracle-side bias of the truncated Poisson surrogate, which appears only in the proof of the improvement step below. Both decay at the same rate λκ+1λ^κ+1. Phase 2: block KL-prox improvement. We use the surrogate h^κπ h_κ^π to drive a one-agent policy update. The KL-proximal (or mirror-descent) update is a standard step in entropy-regularized policy gradient, NPG, and TRPO-style methods: it picks a new policy that maximizes the predicted improvement (a linearized advantage) minus η times the KL divergence from the old policy, where the temperature η>0η>0 controls how aggressive the step is. We apply this update one agent at a time. This per-step η is separate from the softmax temperature τ of Section 4, which is a property of the policy class. Fix a baseline product policy π and an agent k. The exact advantage and its truncated counterpart are Aπ(s,a)=r(s,a)−r¯π+∑yP(y∣s,a)hπ(y)−hπ(s),A^κπ=Aπ|hπ→h^κπ.A^π(s,a)=r(s,a)- r^π+ _yP(y s,a)h^π(y)-h^π(s), A_κ^π=A^π |_h^π→ h_κ^π. The exact and approximate block logits for agent k are gk,⋆π(s,ak)=a−k∼π−k(⋅∣s)[Aπ(s,(ak,a−k))],g^k,κπ(s,ak)=a−k∼π−k(⋅∣s)[A^κπ(s,(ak,a−k))],g_k, ^π(s,a_k)= *E_a_-k _-k(· s)\! [A^π(s,(a_k,a_-k)) ], g_k,κ^π(s,a_k)= *E_a_-k _-k(· s)\! [ A_κ^π(s,(a_k,a_-k)) ], and the KL-prox update is μk(⋅∣s)∝πk(⋅∣s)exp(g^k,κπ(s,⋅)/η) _k(· s) _k(· s) ( g_k,κ^π(s,·)/η) with μ−k=π−k _-k= _-k. Theorem 5.2 (One-block oracle improvement with logit error). Under the assumptions of Theorem 5.1, and assuming additionally that π has full action support at every state so that PμP^μ inherits irreducibility from PπP^π (the KL-prox update preserves the action support of π), the update μ above satisfies r¯(μ)−r¯(π)≥ηS∼dμ[KL(μk(⋅∣S)∥πk(⋅∣S))]−2nC1−λκ+1∥bπ∥∞. r(μ)- r(π)\ ≥\ η\, *E_S d^μ\! [KL ( _k(· S)\, \|\, _k(· S) ) ]\ -\ 2nC1-λ^κ+1\|b^π\|_∞. The same Neumann tail λκ+1λ^κ+1 appears in the certificate of Theorem 5.1 and in the improvement bound, so a single truncation radius κ controls both. The bound is additive in the KL-prox step (first term) and the truncation bias (second term), so the proximal temperature η and the radius κ can be tuned independently. Algorithm LABEL:alg:lpi interleaves the two phases over outer iterations and inner agents, recomputing H and b at every step. Using stale (H,b)(H,b) over a full pass is also valid at the cost of a staleness term we omit. What is local, what is oracle. The framework separates two layers of approximation that scalable MARL methods often conflate. The certificate δ^(κ) δ^(κ) is genuinely local: each δ^i(κ) δ^(κ)_i depends only on entries of HπH^π and of bπb^π supported on the κ-hop out-ball of agent i in GHπG_H^π. The surrogate h^κπ h_κ^π and the truncated logit g^k,κπ g_k,κ^π, by contrast, are oracle objects, since in the general model they depend on the full reward vector and on global action sums. The improvement bound treats them as accessible because the analysis only compares the truncated logit to the exact one. Making the surrogate locally computable needs either (i) restricted observation scopes OiO_i that turn rπr^π and the action expectations into κ-local sums, or (i) function approximation of h^κπ h_κ^π on a parametric family with locality structure, in the spirit of the localized critic in (qu_scalabale_marl_2020; lin_scalable_marl_stochastic_2021). The analysis here gives the structural part of the bound; an additional approximation-error term then enters additively. Algorithm 1 Oracle block-coordinate improvement with locality certificates 1: Input: baseline π(0)π^(0), radius κ, prox temperature η 2: for ℓ=0,1,… =0,1,… do 3: π(ℓ,0)←π(ℓ)π^( ,0)←π^( ) 4: for k=1,…,nk=1,…,n do 5: compute b(ℓ,k−1)=δ(rπ(ℓ,k−1))b^( ,k-1)=δ(r^π^( ,k-1)) and H(ℓ,k−1)=Es+EaΠ(π(ℓ,k−1))H^( ,k-1)=E^s+E^a (π^( ,k-1)) 6: certificate δ^(κ,ℓ,k−1)=∑t=0κ((H(ℓ,k−1))⊤)tb(ℓ,k−1) δ^(κ, ,k-1)= _t=0^κ ((H^( ,k-1)) )^tb^( ,k-1)(κ rounds message-pass) 7: oracle surrogate h^κ(ℓ,k−1)=∑t=0κ(Tπ(ℓ,k−1))t(rπ(ℓ,k−1)−r¯π(ℓ,k−1)) h_κ^( ,k-1)= _t=0^κ(T^π^( ,k-1))^t(r^π^( ,k-1)- r^π^( ,k-1)) 8: block logit g^k,κ(ℓ,k−1) g_k,κ^( ,k-1) via Phase 2 with hπ→h^κ(ℓ,k−1)h^π→ h_κ^( ,k-1) 9: update πk(ℓ,k)(⋅∣s)∝πk(ℓ,k−1)(⋅∣s)exp(g^k,κ(ℓ,k−1)(s,⋅)/η) _k^( ,k)(· s) _k^( ,k-1)(· s) ( g_k,κ^( ,k-1)(s,·)/η); πj(ℓ,k)=πj(ℓ,k−1) _j^( ,k)= _j^( ,k-1) for j≠kj≠ k 10: end for 11: π(ℓ+1)←π(ℓ,n)π^( +1)←π^( ,n) 12: end for 6 Conclusion We gave a policy-dependent spectral certificate of value-locality, ρ(Hπ)<1ρ(H^π)<1 for Hπ=Es+EaΠ(π)H^π=E^s+E^a (π), that is strictly weaker than the row-sum condition on the same matrix and that applies in regimes where the policy-independent action-supremum bounds used in prior Dobrushin-style work cannot. The decomposition splits the closed-loop influence into an environment piece (Es,EaE^s,E^a) and a policy piece (Π(π) (π)). The split makes precise the intuition that a smooth policy can neutralize a strong action channel, since EaΠ(π)E^a (π) shrinks linearly in policy smoothness even when EaE^a is large. For temperature-τ softmax policies the bound Π(π)≤L/(2τ) (π)≤ L/(2τ) makes τ a direct way to tighten the certificate, and the same Neumann tail λκ+1λ^κ+1 that governs the decay of the bias function also governs the truncation bias of an oracle block-coordinate KL-prox improvement template, whose decentralized realization is the natural next step. References Appendix A Related work Our work addresses the curse of dimensionality in multi-agent reinforcement learning (MARL). The challenge is that the global state and action spaces (=∏iS= _iS_i, =∏iA= _iA_i) grow exponentially with the number of agents, n. This problem falls into the category of “succinctly described” MDPs (complexity_blondel2000survey), which are known to be computationally intractable in the general case, even with structural assumptions (complexity_papadimitriou1999complexity). To achieve scalability, researchers have explored various structural assumptions. One common approach in general MARL is to use function approximation (zhang2018fully; lowe2017multi) or assume independent learners (tan1993multi), though the latter can suffer from non-stationarity (matignon2012independent). Other related areas include Factored MDPs (kearns1999efficient; factor_guestrin2003efficient), which assume local states but typically a global action, and Weakly Coupled MDPs (weakly_mdp_meuleau1998solving), which assume agents’ transitions are independent and coupling only occurs through the reward. Our work differs from these by focusing on systems with local, coupled transitions, which is common in networked systems. This paper is most related to the line of work on scalable Networked MARL (qu_scalabale_marl_2020; qu2019scalable; lin_scalable_marl_stochastic_2021). These foundational papers were the first to show that if the system’s local transitions and rewards depend only on a local graph neighborhood, the system exhibits an Exponential Decay Property (EDP). This property, where influence decays exponentially with graph distance, justifies κ-hop truncation and enables scalable algorithms. In the average-reward setting these works establish the EDP via a Dobrushin coupling condition (qu_scalabale_marl_2020), which bounds environment influence by a supremum over joint actions and asks ‖C‖∞<1\|C\|_∞<1 for the resulting policy-independent matrix C. This bound is tight only when the policy realizes the worst-case action; it fails to certify locality whenever the action channel is strong but the policy in use does not excite it. The present paper replaces this row-sum condition with the spectral condition ρ(Hπ)<1ρ(H^π)<1 for Hπ=Es+EaΠ(π)H^π=E^s+E^a (π), which is policy-dependent, recovers the prior condition as a special case, and certifies locality in regimes where the prior one cannot. Appendix B Proofs from Section 3 This appendix contains complete proofs of the results in the main text and an extension to asynchronous updates. All total variation distances are normalized: for probability measures μ and ν on a finite set, TV(μ,ν)=12∑x|μ(x)−ν(x)|TV(μ,ν)= 12 _x|μ(x)-ν(x)|. For a bounded function f on a product space, the coordinatewise oscillations are δi(f)=supx,y∈,x−i=y−i|f(x)−f(y)| _i(f)= _x,y ,\ x_-i=y_-i|f(x)-f(y)| and δ(f)δ(f) is the vector with entries δi(f) _i(f). B.1 Proof of Proposition 3.1 Given i,j∈[n]i,~j∈[n] and two states s,s′s,s that agree off coordinate i, define μj=∑a∈(∏kπk(ak∣sOk))Pj(⋅∣s,a),νj=∑a∈(∏kπk(ak∣sOk′))Pj(⋅∣s′,a). _j= _a ( _k _k(a_k s_O_k) )P_j(· s,a), _j= _a ( _k _k(a_k s _O_k) )P_j(· s ,a). We claim TV(μj,νj)≤Ej←is+∑kEj←kaΠk←i(π).TV( _j, _j)\ ≤\ E^s_j← i\ +\ _kE^a_j← k\, _k← i(π). The decomposition uses the triangle inequality and a coupling argument. Define an intermediate distribution μ~j=∑a∈(∏kπk(ak∣sOk′))Pj(⋅∣s,a). μ_j= _a ( _k _k(a_k s _O_k) )P_j(· s,a). By the triangle inequality, TV(μj,νj)≤TV(μj,μ~j)+TV(μ~j,νj).TV( _j, _j)\ ≤\ TV( _j, μ_j)\ +\ TV( μ_j, _j). We bound TV(μ~j,νj)TV( μ_j, _j) first. The measures μ~j μ_j and νj _j are mixtures with the same mixing weights w(a)=∏kπk(ak∣sOk′)w(a)= _k _k(a_k s _O_k). By convexity of total variation, TV(μ~j,νj) ( μ_j, _j) ≤∑a∈w(a)TV(Pj(⋅∣s,a),Pj(⋅∣s′,a)) ≤ _a w(a)\,TV (P_j(· s,a),P_j(· s ,a) ) ≤supa∈TV(Pj(⋅∣s,a),Pj(⋅∣s′,a))≤Ej←is. ≤ _a TV (P_j(· s,a),P_j(· s ,a) )\ ≤\ E^s_j← i. We now bound TV(μj,μ~j)TV( _j, μ_j). This is the difference between two mixtures with the same components and different mixing weights p(a∣s)=∏kπk(ak∣sOk)p(a s)= _k _k(a_k s_O_k) and p(a∣s′)=∏kπk(ak∣sOk′)p(a s )= _k _k(a_k s _O_k), but the components Pj(⋅∣s,a)P_j(· s,a) can be far apart for different a. We upper bound this difference by a coupling that changes actions along one coordinate at a time and uses the action sensitivity of the kernel. Let (A,A′)(A,A ) be a coupling of p(⋅∣s)p(· s) and p(⋅∣s′)p(· s ) constructed as follows. For each agent k, couple the marginals πk(⋅∣sOk) _k(· s_O_k) and πk(⋅∣sOk′) _k(· s _O_k) by a maximal coupling so that ℙ[Ak≠Ak′]=TV(πk(⋅∣sOk),πk(⋅∣sOk′))≤Πk←i(π).P[A_k≠ A _k]\ =\ TV ( _k(· s_O_k), _k(· s _O_k) )\ ≤\ _k← i(π). Take these couplings independent across k, which is possible because the policy is of product form and the coordinates are independent under each product marginal. Conditional on (A,A′)(A,A ), couple next–state coordinates for agent j by a maximal coupling of Pj(⋅∣s,A)P_j(· s,A) and Pj(⋅∣s,A′)P_j(· s,A ). Then ℙ[S′(j)≠S~′(j)∣A,A′]=TV(Pj(⋅∣s,A),Pj(⋅∣s,A′)).P[S (j)≠ S (j) A,A ]\ =\ TV (P_j(· s,A),P_j(· s,A ) ). Taking expectation, TV(μj,μ~j)≤TV(Pj(⋅∣s,A),Pj(⋅∣s,A′)).TV( _j, μ_j)\ ≤\ E\,TV (P_j(· s,A),P_j(· s,A ) ). For any a,a′a,a differing on a set D⊆[n]D [n] of action coordinates, the triangle inequality and the definition of EaE^a imply TV(Pj(⋅∣s,a),Pj(⋅∣s,a′))≤∑k∈DEj←ka.TV (P_j(· s,a),P_j(· s,a ) )\ ≤\ _k∈ DE^a_j← k. Applying this bound with the random pair (A,A′)(A,A ) and taking expectations yields TV(μj,μ~j)≤∑k=1nEj←kaℙ[Ak≠Ak′]≤∑k=1nEj←kaΠk←i(π),TV( _j, μ_j)\ ≤\ _k=1^nE^a_j← k\,P[A_k≠ A _k]\ ≤\ _k=1^nE^a_j← k\, _k← i(π), where the last inequality uses ℙ[Ak≠Ak′]≤Πk←i(π)P[A_k≠ A _k]≤ _k← i(π) from the maximal coupling above. Combining the two pieces finishes the proof: TV(μj,νj)≤Ej←is+∑k=1nEj←kaΠk←i(π).TV( _j, _j)\ ≤\ E^s_j← i\ +\ _k=1^nE^a_j← k\, _k← i(π). By the definition of Cj←iπC^π_j← i as a supremum over s,s′s,s with s−i=s−i′s_-i=s _-i, the same bound holds for Cj←iπC^π_j← i. B.2 Proof of Lemma 3.2 Fix i and two states s,s′s,s with s−i=s−i′s_-i=s _-i. We will couple one synchronous step from s and from s′s . First couple the actions. For each k∈[n]k∈[n], let (Ak,Ak′)(A_k,A _k) be a maximal coupling of πk(⋅∣sOk) _k(· s_O_k) and πk(⋅∣sOk′) _k(· s _O_k), chosen independently across k. Then (A,A′)=((Ak)k,(Ak′)k)(A,A )=((A_k)_k,(A _k)_k) is a coupling of the product measures π(⋅∣s)π(· s) and π(⋅∣s′)π(· s ), and ℙ[Ak≠Ak′]=TV(πk(⋅∣sOk),πk(⋅∣sOk′))≤Π(π)k←i.P[A_k≠ A _k]\ =\ TV\! ( _k(· s_O_k), _k(· s _O_k) )\ ≤\ (π)_k← i. Next, conditional on (A,A′)=(a,a′)(A,A )=(a,a ), draw the next state coordinates independently across j: let Xj∼Pj(⋅∣s,a)X_j P_j(· s,a) and Yj∼Pj(⋅∣s′,a′)Y_j P_j(· s ,a ), and couple (Xj,Yj)(X_j,Y_j) by a maximal coupling of these two marginals. By construction, ℙ[Xj≠Yj∣A=a,A′=a′]=TV(Pj(⋅∣s,a),Pj(⋅∣s′,a′)).P[X_j≠ Y_j A=a,A =a ]\ =\ TV\! (P_j(· s,a),P_j(· s ,a ) ). Taking expectation over (A,A′)(A,A ) gives ℙ[Xj≠Yj]=A,A′[TV(Pj(⋅∣s,A),Pj(⋅∣s′,A′))].P[X_j≠ Y_j]\ =\ E_A,A [TV\! (P_j(· s,A),P_j(· s ,A ) ) ]. For any a,a′a,a , apply the triangle inequality: TV(Pj(⋅∣s,a),Pj(⋅∣s′,a′))≤TV(Pj(⋅∣s,a),Pj(⋅∣s,a′))⏟action change at fixed s+TV(Pj(⋅∣s,a′),Pj(⋅∣s′,a′))⏟state change at fixed a′.TV\! (P_j(· s,a),P_j(· s ,a ) )\ ≤\ TV\! (P_j(· s,a),P_j(· s,a ) )_action change at fixed $s$\ +\ TV\! (P_j(· s,a ),P_j(· s ,a ) )_state change at fixed $a $. By the definitions of EaE^a and EsE^s, TV(Pj(⋅∣s,a),Pj(⋅∣s,a′))≤∑k:ak≠ak′Ej←ka,TV(Pj(⋅∣s,a′),Pj(⋅∣s′,a′))≤Ej←is.TV\! (P_j(· s,a),P_j(· s,a ) )\ ≤\ _k:\,a_k≠ a _kE^a_j← k, \! (P_j(· s,a ),P_j(· s ,a ) )\ ≤\ E^s_j← i. Therefore, ℙ[Xj≠Yj]≤Ej←is+∑k=1nEj←kaℙ[Ak≠Ak′]≤Ej←is+∑k=1nEj←kaΠ(π)k←i.P[X_j≠ Y_j]\ ≤\ E^s_j← i\ +\ _k=1^nE^a_j← k\,P[A_k≠ A _k]\ ≤\ E^s_j← i\ +\ _k=1^nE^a_j← k\, (π)_k← i. We now relate |f(X)−f(Y)||f(X)-f(Y)| to the coordinate-disagreement indicators. Define a sequence Z0=X,Z1,…,Zn=YZ_0=X,\ Z_1,…,Z_n=Y by changing coordinates one at a time, with ZjZ_j obtained from Zj−1Z_j-1 by replacing its j-th coordinate with YjY_j. Then Zj−1Z_j-1 and ZjZ_j agree off coordinate j, so by definition of δj(f) _j(f), |f(Zj−1)−f(Zj)|≤δj(f) 1Xj≠Yj.|f(Z_j-1)-f(Z_j)|\ ≤\ _j(f)\,1\X_j≠ Y_j\. Summing along the chain and using the triangle inequality, |f(X)−f(Y)|≤∑j=1nδj(f) 1Xj≠Yj.|f(X)-f(Y)|\ ≤\ _j=1^n _j(f)\,1\X_j≠ Y_j\. Taking expectations, |(Tπf)(s)−(Tπf)(s′)|≤∑j=1nδj(f)ℙ[Xj≠Yj]≤∑j=1nδj(f)(Ej←is+∑k=1nEj←kaΠ(π)k←i).|(T^πf)(s)-(T^πf)(s )|\ ≤\ _j=1^n _j(f)\,P[X_j≠ Y_j]\ ≤\ _j=1^n _j(f)\, (E^s_j← i+ _k=1^nE^a_j← k\, (π)_k← i ). Taking the supremum over all s,s′s,s that agree off i yields δi(Tπf)≤∑jHj←iπδj(f) _i(T^πf)≤ _jH^π_j← i\, _j(f), and the vector form follows. The multi-step bound follows by induction. The base case t=0t=0 is trivial. For the inductive step, applying the one-step bound to g=(Tπ)tfg=(T^π)^tf gives δ(Tπg)≤(Hπ)⊤δ(g)≤(Hπ)⊤((Hπ)⊤)tδ(f)=((Hπ)⊤)t+1δ(f)δ(T^πg)≤(H^π) δ(g)≤(H^π) ((H^π) )^tδ(f)=((H^π) )^t+1δ(f), using the inductive hypothesis δ(g)≤((Hπ)⊤)tδ(f)δ(g)≤((H^π) )^tδ(f) and entrywise nonnegativity of (Hπ)⊤(H^π) . B.3 Proof of Theorem 3.3 We note that the map π↦Hπ=Es+EaΠ(π)π H^π=E^s+E^a (π) is continuous on the finite-state finite-action setting: Π(π) (π) is a finite maximum of total variations between π-marginals, which are continuous in π. Therefore ρ(Hπ)ρ(H^π) is upper semicontinuous on π, and the supremum λ⋆=supπ∈Πpolρ(Hπ) _ = _π∈ _polρ(H^π) is attained on the compact class Πpol _pol. By Lemma 3.2, for every π∈Πpolπ∈ _pol and every bounded f, δ(Tπf)≤(Hπ)⊤δ(f).δ(T^πf)\ ≤\ (H^π) δ(f). Iterating gives δ((Tπ)tf)≤((Hπ)⊤)tδ(f),t≥0.δ ((T^π)^tf )\ ≤\ ((H^π) )^tδ(f), t≥ 0. Fix any λ¯∈(λ⋆,1) λ∈( _ ,1), where λ⋆=supπ∈Πpolρ(Hπ)<1. _ = _π∈ _polρ(H^π)<1. For each π∈Πpolπ∈ _pol, define wπ≔(λ¯I−(Hπ)⊤)−1∈ℝ++n.w^π ( λI-(H^π) )^-11 _++^n. This is well-defined because ρ((Hπ)⊤)=ρ(Hπ)<λ¯ρ((H^π) )=ρ(H^π)< λ. Moreover, (Hπ)⊤wπ=λ¯wπ−≤λ¯wπ.(H^π) w^π= λw^π-1\ ≤\ λw^π. Define the weighted sup norm on ℝnR^n by ‖x‖wπ,∞≔maxi∈[n]|xi|wiπ.\|x\|_w^π,∞ _i∈[n] |x_i|w_i^π. We claim that for every nonnegative vector x∈ℝ+nx _+^n, ‖(Hπ)⊤x‖wπ,∞≤λ¯‖x‖wπ,∞.\|(H^π) x\|_w^π,∞\ ≤\ λ\,\|x\|_w^π,∞. Indeed, for each i, ((Hπ)⊤x)i ((H^π) x )_i =∑jHj←iπxj=∑jHj←iπwjπ⋅xjwjπ≤‖x‖wπ,∞∑jHj←iπwjπ = _jH^π_j← i\,x_j\ =\ _jH^π_j← i\,w_j^π· x_jw_j^π\ ≤\ \|x\|_w^π,∞ _jH^π_j← i\,w_j^π =‖x‖wπ,∞((Hπ)⊤wπ)i≤‖x‖wπ,∞λ¯wiπ, =\|x\|_w^π,∞\, ((H^π) w^π )_i\ ≤\ \|x\|_w^π,∞\, λ\,w_i^π, where the last step uses (Hπ)⊤wπ≤λ¯wπ(H^π) w^π≤ λw^π from above. Dividing by wiπw_i^π and taking the max over i gives the claim. By induction, ‖((Hπ)⊤)tx‖wπ,∞≤λ¯t‖x‖wπ,∞,t≥0. \| ((H^π) )^tx \|_w^π,∞\ ≤\ λ^t\,\|x\|_w^π,∞, t≥ 0. Because the state and action spaces are finite, the map π↦Hπ H^π is continuous. Hence π↦wπ w^π is continuous on the compact set Πpol _pol, so mλ¯≔infπ∈Πpolminiwiπ>0,Mλ¯≔supπ∈Πpolmaxiwiπ<∞.m_ λ _π∈ _pol _iw_i^π>0, M_ λ _π∈ _pol _iw_i^π<∞. Therefore, for every nonnegative vector x, ‖x‖wπ,∞≤1mλ¯‖x‖∞,‖x‖∞≤Mλ¯‖x‖wπ,∞,\|x\|_w^π,∞≤ 1m_ λ\|x\|_∞, \|x\|_∞≤ M_ λ\|x\|_w^π,∞, and thus ‖((Hπ)⊤)tx‖∞≤Mλ¯mλ¯λ¯t‖x‖∞. \| ((H^π) )^tx \|_∞\ ≤\ M_ λm_ λ\, λ^t\,\|x\|_∞. Applying this with x=δ(f)x=δ(f) yields ‖δ((Tπ)tf)‖∞≤Cλ¯,Πpolλ¯t‖δ(f)‖∞,Cλ¯,Πpol≔Mλ¯mλ¯.\|δ((T^π)^tf)\|_∞\ ≤\ C_ λ, _pol\, λ^t\,\|δ(f)\|_∞, C_ λ, _pol M_ λm_ λ. Now assume in addition that, for each π∈Πpolπ∈ _pol, the Markov chain with kernel PπP^π is irreducible, and let dπd^π be its stationary distribution. Define gπ≔rπ−r¯π,r¯π=∑s∈dπ(s)rπ(s).g^π r^π- r^π1, r^π= _s d^π(s)\,r^π(s). Since δ(gπ)=δ(rπ)δ(g^π)=δ(r^π), the bound above implies ∑t=0∞‖δ((Tπ)tgπ)‖∞<∞. _t=0^∞\|δ((T^π)^tg^π)\|_∞<∞. To handle the additive-constant ambiguity, work on the quotient space ℬ0()≔B()/span,B_0(S) B(S) /span\1\, and write [f][f] for the equivalence class of f. Define ‖[f]‖δ≔‖δ(f)‖∞.\|[f]\|_δ \|δ(f)\|_∞. Because δ(f)=0δ(f)=0 if and only if f is constant, this is a well-defined norm on ℬ0()B_0(S). The operator TπT^π induces a linear map T~π[f]≔[Tπf] T^π[f] [T^πf] satisfying ‖(T~π)t[f]‖δ≤Cλ¯,Πpolλ¯t‖[f]‖δ.\|( T^π)^t[f]\|_δ\ ≤\ C_ λ, _pol\, λ^t\,\|[f]\|_δ. Hence the Neumann series converges in operator norm on ℬ0()B_0(S), and we may define [hπ]≔∑t=0∞(T~π)t[gπ].[h^π]\ \ _t=0^∞( T^π)^t[g^π]. Then (I−T~π)[hπ]=[gπ].(I- T^π)[h^π]=[g^π]. Equivalently, for any representative hπh^π of the class [hπ][h^π], there exists a constant c such that hπ−Tπhπ=gπ+c.h^π-T^πh^π=g^π+c1. Applying the stationary distribution dπd^π to both sides gives 0=dπ(gπ)+c=c,0=d^π(g^π)+c=c, since dπ(gπ)=0d^π(g^π)=0 by definition of r¯π r^π. Therefore hπ−Tπhπ=gπ=rπ−r¯π.h^π-T^πh^π=g^π=r^π- r^π. Uniqueness up to an additive constant follows similarly: if h−Tπh=0h-T^πh=0, then (I−T~π)[h]=0.(I- T^π)[h]=0. Since I−T~πI- T^π is invertible on the quotient space, [h]=0[h]=0, so h is constant. Finally, using the triangle inequality for the oscillation seminorm and the multi-step bound, δ(hπ)≤∑t=0∞δ((Tπ)tgπ)≤∑t=0∞((Hπ)⊤)tδ(gπ)=∑t=0∞((Hπ)⊤)tδ(rπ).δ(h^π)\ ≤\ _t=0^∞δ((T^π)^tg^π)\ ≤\ _t=0^∞ ((H^π) )^tδ(g^π)\ =\ _t=0^∞ ((H^π) )^tδ(r^π). Since (Hπ)⊤(H^π) is entrywise nonnegative and ρ(Hπ)<1ρ(H^π)<1, the Neumann series converges entrywise and ∑t=0∞((Hπ)⊤)t=(I−(Hπ)⊤)−1. _t=0^∞ ((H^π) )^t= (I-(H^π) )^-1. Hence δ(hπ)≤(I−(Hπ)⊤)−1δ(rπ).δ(h^π)\ ≤\ (I-(H^π) )^-1δ(r^π). This completes the proof. B.4 Spatial decay as a corollary of sparsity Suppose there is an underlying undirected graph G on [n][n] such that the environment and the policy are local with respect to G in the following sense: • Ej←is=0E^s_j← i=0 unless i lies in a fixed-radius neighborhood of j in G; • Ej←ka=0E^a_j← k=0 unless k lies in a fixed-radius neighborhood of j in G; • Π(π)k←i=0 (π)_k← i=0 unless i∈Oki∈ O_k, and each observation scope OkO_k is contained in a fixed-radius neighborhood of k in G. In general, the product EaΠ(π)E^a (π) need not have exactly the same sparsity pattern as G; rather, it induces a derived directed support graph GHπ:i→jwheneverHj←iπ>0,Hπ=Es+EaΠ(π).G_H^π: i→ j\ whenever\ H^π_j← i>0, H^π=E^s+E^a (π). This graph captures one-step closed-loop influence. Under the locality assumptions above, GHπG_H^π is a sparse finite-radius closure of the underlying graph. For any pair of coordinates i,ji,j, the entry [((Hπ)⊤)t]ij [ ((H^π) )^t ]_ij can be nonzero only if there is a directed path of length at most t from i to j in GHπG_H^π, where edges are oriented as i→ji→ j whenever Hj←iπ>0H^π_j← i>0. Hence the Neumann-series bound δ(hπ)≤∑t=0∞((Hπ)⊤)tδ(rπ)δ(h^π)\ ≤\ _t=0^∞ ((H^π) )^t\,δ(r^π) shows that the contribution of coordinates outside a κ-hop neighborhood in GHπG_H^π is controlled by the tail ∑t=κ+1∞((Hπ)⊤)tδ(rπ), _t=κ+1^∞ ((H^π) )^t\,δ(r^π), which decays exponentially whenever ρ(Hπ)<1ρ(H^π)<1. B.5 Average-reward localized certificates and oracle truncation (synchronous) Under the sparsity conditions above, the truncated certificate δ^(κ)=∑t=0κ((Hπ)⊤)tδ(rπ) δ^(κ)= _t=0^κ ((H^π) )^tδ(r^π) from Theorem 5.1 is computable by local message passing on κ-neighborhoods in the support graph of HπH^π. The associated oracle truncated Poisson series h^κπ h_κ^π has bias modulo constants bounded by the same exponentially decaying Neumann tail. Using this oracle surrogate in a block KL-prox update yields the one-block improvement guarantee of Theorem 5.2. Establishing a fully local policy-improvement algorithm requires an additional approximation or projection step beyond the present structural analysis and is left to future work. B.6 Asynchronous updates For completeness we state the analogue of the main results when, at each step, all agents keep their states except for a randomly selected coordinate JtJ_t which is updated according to a site–selection distribution ν with full support. In this model the one–step operator is Kπf(s)=π[f(St+1)∣St=s]K^πf(s)=E_π[f(S_t+1) S_t=s] with ℙ[St+1=s(j→y)∣St=s]=νj∑a(∏kπk(ak∣s))Pj(y∣s,a)for y∈j.P[S_t+1=s^(j→ y) S_t=s]= _j _a ( _k _k(a_k s) )P_j(y s,a) y _j. Define EsE^s, EaE^a, and Π(π) (π) as before and set Mπ=(I−diagν)+diagν(Es+EaΠ(π)).M^π=(I-diag\,ν)+diag\,ν\,(E^s+E^a (π)). Then for all bounded f, δ(Kπf)≤(Mπ)⊤δ(f).δ(K^πf)≤(M^π) δ(f). Consequently, if λ⋆async≔supπ∈Πpolρ(Mπ)<1, _ ^async _π∈ _polρ(M^π)<1, then for every λ¯∈(λ⋆async,1) λ∈( _ ^async,1) there exists a constant Cλ¯C_ λ such that ‖δ((Kπ)tf)‖∞≤Cλ¯λ¯t‖δ(f)‖∞.\|δ((K^π)^tf)\|_∞≤ C_ λ λ^t\|δ(f)\|_∞. Under the same irreducibility assumptions as in Theorem 3.3, the average-reward Poisson equation has a solution satisfying δ(hπ)≤(I−(Mπ)⊤)−1δ(rπ).δ(h^π)≤ (I-(M^π) )^-1δ(r^π). The entrywise bound follows by conditioning on the selected coordinate J∼νJ ν. Fix i and s,s′s,s that agree off coordinate i, and couple the actions A,A′A,A exactly as in the proof of Lemma 3.2. If J=iJ=i, then St+1S_t+1 and St+1′S _t+1 inherit all coordinates other than i from s,s′s,s , which already agree, so they differ only at coordinate i, with ℙ[St+1,i≠St+1,i′]≤Hi←iπP[S_t+1,i≠ S _t+1,i]≤ H^π_i← i by the same maximal-coupling argument used in Lemma 3.2, and |f(St+1)−f(St+1′)|≤δi(f)Hi←iπ|f(S_t+1)-f(S _t+1)|≤ _i(f)\,H^π_i← i in expectation. If J=j≠iJ=j≠ i, then coordinate i is not updated, so St+1,i=si≠si′=St+1,i′S_t+1,i=s_i≠ s _i=S _t+1,i, contributing δi(f) _i(f); and coordinate j is updated, contributing Hj←iπδj(f)H^π_j← i\, _j(f) in expectation. Averaging over J∼νJ ν gives δi(Kπf)≤(1−νi)δi(f)+νiHi←iπδi(f)+∑j≠iνjHj←iπδj(f)=∑j=1nMj←iπδj(f), _i(K^πf)≤(1- _i)\, _i(f)+ _iH^π_i← i\, _i(f)+ _j≠ i _jH^π_j← i\, _j(f)= _j=1^nM^π_j← i\, _j(f), which is the entrywise form of δ(Kπf)≤(Mπ)⊤δ(f)δ(K^πf)≤(M^π) δ(f). The remaining steps (Poisson decay, exponential bound on iterates) repeat the proof of Theorem 3.3 with HπH^π replaced by MπM^π. B.7 Extension of Theorem 3.3 to the weighted case The same argument also yields weighted oscillation bounds. We record the statement because it is often useful for certifying spectral-radius conditions through weighted norms. Fix w∈ℝ++nw _++^n and W=diag(w)W=diag(w). For any bounded f and i∈[n]i∈[n], δiw(Tπf)=wiδi(Tπf)≤wi∑j=1nHj←iπδj(f)=∑j=1n(W−1HπW)j←iδjw(f). _i^w(T^πf)\ =\ w_i\, _i(T^πf)\ ≤\ w_i _j=1^nH^π_j← i\, _j(f)\ =\ _j=1^n (W^-1H^πW )_j← i\, _j^w(f). This is the entrywise weighted one–step contraction. Iterating gives the multi–step bound. For the Poisson resolvent, one repeats the quotient-space proof of Theorem 3.3 with the seminorm ‖f‖δw=‖δw(f)‖∞\|f\|_δ^w=\|δ^w(f)\|_∞. Let H~π,w≔W−1HπW. H^π,w W^-1H^πW. With our convention Hj←iπ=Hπ[j,i]H^π_j← i=H^π[j,i], the entrywise bound above becomes the vector inequality δw(Tπf)≤(H~π,w)⊤δw(f)δ^w(T^πf)≤( H^π,w) δ^w(f), with a transpose for the same reason as in the unweighted Lemma 3.2. The Neumann series ∑t≥0((H~π,w)⊤)t _t≥ 0(( H^π,w) )^t converges entrywise when ρ(H~π,w)<1ρ( H^π,w)<1 (noting ρ((H~π,w)⊤)=ρ(H~π,w)ρ(( H^π,w) )=ρ( H^π,w)), and δw(hπ)≤∑t=0∞((H~π,w)⊤)tδw(rπ)=(I−(H~π,w)⊤)−1δw(rπ).δ^w(h^π)\ ≤\ _t=0^∞ (( H^π,w) )^tδ^w(r^π)\ =\ (I-( H^π,w) )^-1δ^w(r^π). Since H~π,w=W−1HπW H^π,w=W^-1H^πW is similar to HπH^π, the spectral radius is unchanged: ρ(H~π,w)=ρ(Hπ)ρ( H^π,w)=ρ(H^π). The weighted version is therefore useful for sharpening operator-norm certificates, not for changing the spectral condition itself. The truncated series bound and the uniform power bound over a compact policy class are identical to the unweighted case after replacing HπH^π by H~π,w H^π,w. Appendix C Proofs from Section 4 We bound the policy sensitivity matrix Π(π) (π) for entropy-regularized (temperature-τ) softmax policies in terms of per-agent logit Lipschitz constants. Throughout, total variation is normalized: TV(μ,ν)=12‖μ−ν‖1TV(μ,ν)= 12\|μ-ν\|_1. Lemma C.1 (Softmax Lipschitz constant in total variation). Fix m∈ℕm and τ>0τ>0. For u,v∈ℝmu,v ^m, define softτ(u)a≔exp(ua/τ)∑b=1mexp(ub/τ),a∈[m].soft_τ(u)_a\ \ (u_a/τ) _b=1^m (u_b/τ)\,, a∈[m]. Then TV(softτ(u),softτ(v))≤12τ‖u−v‖∞.TV (soft_τ(u),\ soft_τ(v) )\ ≤\ 12τ\,\|u-v\|_∞. The constant 1/(2τ)1/(2τ) is optimal: for m≥2m≥ 2, the supremum of TV(softτ(u),softτ(v))/‖u−v‖∞TV(soft_τ(u),soft_τ(v))/\|u-v\|_∞ over u≠vu≠ v equals 1/(2τ)1/(2τ), approached (but not attained) as ‖u−v‖∞→0\|u-v\|_∞→ 0 along a balanced ±1± 1 direction starting from a uniform softmax. Sharpness in this asymptotic sense is exactly what makes 1/(2τ)1/(2τ) the best uniform Lipschitz constant. Proof C.2. Write p=softτ(u)p=soft_τ(u) and q=softτ(v)q=soft_τ(v). By the mean value theorem on the line segment w(t)=v+t(u−v)w(t)=v+t(u-v), t∈[0,1]t∈[0,1], ‖p−q‖1=‖∫01dtsoftτ(w(t))dt‖1≤∫01‖Dsoftτ(w(t))(u−v)‖1dt,\|p-q\|_1\ =\ \| _0^1 ddtsoft_τ(w(t))\,dt \|_1\ ≤\ _0^1 \|Dsoft_τ(w(t))\,(u-v) \|_1dt, where Dsoftτ(w)Dsoft_τ(w) is the Jacobian. For w∈ℝmw ^m with r=softτ(w)r=soft_τ(w), Dsoftτ(w)=1τ(diag(r)−rr⊤).Dsoft_τ(w)\ =\ 1τ\, (diag(r)-r ). Hence, using the induced operator norm from ℓ∞ _∞ to ℓ1 _1, ‖p−q‖1≤1τ(supt∈[0,1]‖diag(r(t))−r(t)r(t)⊤‖∞→1)‖u−v‖∞,r(t)=softτ(w(t)).\|p-q\|_1\ ≤\ 1τ\, ( _t∈[0,1] \|diag(r(t))-r(t)r(t) \|_∞→ 1 )\,\|u-v\|_∞, r(t)=soft_τ(w(t)). We claim that for every probability vector r, ∥diag(r)−r⊤∥∞→1≤ 1.(⋆) \|diag(r)-r \|_∞→ 1\ ≤\ 1. ( ) This yields ‖p−q‖1≤1τ‖u−v‖∞\|p-q\|_1≤ 1τ\|u-v\|_∞ and therefore TV(p,q)≤12τ‖u−v‖∞TV(p,q)≤ 12τ\|u-v\|_∞. It remains to prove (⋆)( ). Let J(r)=diag(r)−rr⊤J(r)=diag(r)-r and fix δ∈ℝmδ ^m with ‖δ‖∞≤1\|δ\|_∞≤ 1. Then (J(r)δ)i=ri(δi−⟨r,δ⟩),i∈[m],(J(r)δ)_i\ =\ r_i ( _i- r,δ ), i∈[m], hence ‖J(r)δ‖1=∑i=1mri|δi−μ|=I∼r[|δI−μ|],μ≔⟨r,δ⟩∈[−1,1].\|J(r)δ\|_1\ =\ _i=1^mr_i\, | _i-μ |\ =\ E_I r [\,| _I-μ|\, ], μ r,δ ∈[-1,1]. Let X=δIX= _I with I∼rI r; then X∈[−1,1]X∈[-1,1] and [X]=μE[X]=μ. By Jensen’s inequality and the variance bound for bounded random variables, |X−μ|≤Var(X)≤1−μ2≤ 1,E\,|X-μ|\ ≤\ Var(X)\ ≤\ 1-μ^2\ ≤\ 1, where the middle step uses Var(X)≤[X2]−μ2≤1−μ2Var(X) [X^2]-μ^2≤ 1-μ^2 since X2≤1X^2≤ 1. Therefore ‖J(r)δ‖1≤1\|J(r)δ\|_1≤ 1 for all δ with ‖δ‖∞≤1\|δ\|_∞≤ 1, proving (⋆)( ). The bound is tight in the limit μ→0μ→ 0 with X taking values ±1± 1 equally. We now translate Lemma C.1 into a bound on the policy sensitivity matrix Π(π) (π) for product-form, temperature-τ softmax policies with local logits. Definition C.3 (Local logits and per-coordinate logit Lipschitz constants). For each agent k, suppose there is a logit function gk:Ok×k→ℝg_k:S_O_k×A_k such that πk(ak∣sOk)∝exp(gk(sOk,ak)/τ),ak∈k, _k(a_k s_O_k)\ \ \! (g_k(s_O_k,a_k)/τ ), a_k _k, with temperature τ>0τ>0. For i∈[n]i∈[n], define the one-coordinate logit Lipschitz constant Lk←i≔sups−i=s−i′‖gk(sOk,⋅)−gk(sOk′,⋅)‖∞,L_k← i\ \ _s_-i=s _-i\ \|g_k(s_O_k,·)\ -\ g_k(s _O_k,·) \|_∞, where the sup is over s,s′∈s,s that differ only on coordinate i. Lemma C.4 (Softmax temperature controls Π(π) (π)). Under the setup above, for all k,i∈[n]k,i∈[n], Πk←i(π)≤min 1,Lk←i2τ. _k← i(π)\ ≤\ \! \\,1,\ L_k← i2τ\, \. In particular, if i∉Oki∉ O_k then Lk←i=0L_k← i=0 and Πk←i(π)=0 _k← i(π)=0. Proof C.5. Fix k and i. If i∉Oki∉ O_k then gk(sOk,⋅)g_k(s_O_k,·) is unchanged when sis_i varies, hence Lk←i=0L_k← i=0 and πk(⋅∣sOk)=πk(⋅∣sOk′) _k(· s_O_k)= _k(· s _O_k) for all s−i=s−i′s_-i=s _-i, giving Πk←i(π)=0 _k← i(π)=0. Assume i∈Oki∈ O_k. For s,s′s,s with s−i=s−i′s_-i=s _-i, apply Lemma C.1 with u=gk(sOk,⋅)u=g_k(s_O_k,·) and v=gk(sOk′,⋅)v=g_k(s _O_k,·) to obtain TV(πk(⋅∣sOk),πk(⋅∣sOk′))≤12τ∥gk(sOk,⋅)−gk(sOk′,⋅)∥∞≤Lk←i2τ.TV ( _k(· s_O_k),\ _k(· s _O_k) )\ ≤\ 12τ\, \|g_k(s_O_k,·)-g_k(s _O_k,·) \|_∞\ ≤\ L_k← i2τ. Taking the supremum over such s,s′s,s yields Πk←i(π)≤Lk←i/(2τ) _k← i(π)≤ L_k← i/(2τ). The bound is trivially capped by 11 because total variation lies in [0,1][0,1]. Remark C.6 (Sharpness). The constant 1/(2τ)1/(2τ) inherited from Lemma C.1 is optimal in the asymptotic sense described there: it cannot be improved as ‖gk(sOk,⋅)−gk(sOk′,⋅)‖∞→0\|g_k(s_O_k,·)-g_k(s _O_k,·)\|_∞→ 0. Consequently, controlling Π(π) (π) uniformly over a policy class amounts to lower-bounding the entropy temperature τ and upper-bounding the one-coordinate logit oscillations Lk←iL_k← i. Appendix D Proofs from Section 5 All state and action spaces are finite. Total variation is normalized as TV(μ,ν)=12∑x|μ(x)−ν(x)|TV(μ,ν)= 12 _x|μ(x)-ν(x)|. Coordinatewise oscillations are δi(f)=sup|f(x)−f(y)|:x−i=y−i _i(f)= \|f(x)-f(y)|:x_-i=y_-i\ and δ(f)=(δi(f))i=1nδ(f)=( _i(f))_i=1^n. We use Theorem 3.3 from the main text. D.1 Proof of Theorem 5.1 Fix a policy π. Let gπ≔rπ−r¯π,bπ≔δ(rπ)=δ(gπ),Hπ≔Es+EaΠ(π).g^π r^π- r^π, b^π δ(r^π)=δ(g^π), H^π E^s+E^a (π). By Theorem 3.3, δ(hπ)≤∑t=0∞((Hπ)⊤)tbπ.δ(h^π)\ ≤\ _t=0^∞ ((H^π) )^t\,b^π. Define δ^(κ)≔∑t=0κ((Hπ)⊤)tbπ,R(κ)≔∑t=κ+1∞((Hπ)⊤)tbπ. δ^(κ) _t=0^κ ((H^π) )^t\,b^π, R^(κ) _t=κ+1^∞ ((H^π) )^t\,b^π. Then immediately δ(hπ)≤δ^(κ)+R(κ),δ(h^π)\ ≤\ δ^(κ)+R^(κ), which proves the certificate statement. For the tail bound, ‖R(κ)‖∞≤∑t=κ+1∞‖((Hπ)⊤)t‖∞→∞‖bπ‖∞≤∑t=κ+1∞Cλt‖bπ‖∞=C1−λλκ+1‖bπ‖∞.\|R^(κ)\|_∞\ ≤\ _t=κ+1^∞ \| ((H^π) )^t \|_∞→∞\,\|b^π\|_∞\ ≤\ _t=κ+1^∞Cλ^t\,\|b^π\|_∞\ =\ C1-λ^κ+1\|b^π\|_∞. For locality, let GHπG_H^π be the support graph of HπH^π (edge i→ji→ j when Hj←iπ>0H^π_j← i>0). Expanding the matrix power, [((Hπ)⊤)tbπ]i=∑i=k0,k1,…,ktHk1←k0πHk2←k1π⋯Hkt←kt−1πbktπ, [ ((H^π) )^tb^π ]_i\ =\ _i=k_0,k_1,…,k_tH^π_k_1← k_0\,H^π_k_2← k_1\,·s\,H^π_k_t← k_t-1\,b^π_k_t, which sums over directed length-t paths k0=i→k1→⋯→ktk_0=i→ k_1→·s→ k_t in GHπG_H^π. The contribution is nonzero only when every Hkℓ+1←kℓπH^π_k_ +1← k_ is positive, i.e. when ktk_t is reachable from i in t steps. Hence the truncated sum δ^i(κ) δ_i^(κ) depends only on entries of HπH^π and bπb^π supported on the κ-hop out-ball of i in GHπG_H^π (agents reachable from i in at most κ directed edges), and it can be computed by κ rounds of message passing along the reverse edges of that ball. For the oracle truncation bias, define h^κπ≔∑t=0κ(Tπ)tgπ. h_κ^π _t=0^κ(T^π)^tg^π. From the quotient-space construction used in the proof of Theorem 3.3, [hπ]=∑t=0∞(T~π)t[gπ],[h^κπ]=∑t=0κ(T~π)t[gπ],[h^π]= _t=0^∞( T^π)^t[g^π], [ h_κ^π]= _t=0^κ( T^π)^t[g^π], where T~π T^π denotes the induced operator on B()/spanB(S)/span\1\. Therefore [h^κπ−hπ]=−∑t=κ+1∞(T~π)t[gπ].[ h_κ^π-h^π]=- _t=κ+1^∞( T^π)^t[g^π]. Applying the oscillation bound gives δ(h^κπ−hπ)≤∑t=κ+1∞((Hπ)⊤)tbπ=R(κ).δ( h_κ^π-h^π)\ ≤\ _t=κ+1^∞ ((H^π) )^t\,b^π=R^(κ). Now use the standard identity infc∈ℝ‖f−c‖∞=12osc(f),osc(f)≤∑i=1nδi(f)=‖δ(f)‖1. _c \|f-c1\|_∞= 12\,osc(f), (f)≤ _i=1^n _i(f)=\|δ(f)\|_1. Applying this to f=h^κπ−hπf= h_κ^π-h^π yields Bκπ=infc∈ℝ‖h^κπ−hπ−c‖∞≤12‖δ(h^κπ−hπ)‖1≤12∑i=1nRi(κ).B_κ^π= _c \| h_κ^π-h^π-c1\|_∞\ ≤\ 12\,\|δ( h_κ^π-h^π)\|_1\ ≤\ 12 _i=1^nR_i^(κ). Finally, ∑i=1nRi(κ)≤n‖R(κ)‖∞≤nC1−λλκ+1‖bπ‖∞, _i=1^nR_i^(κ)≤ n\|R^(κ)\|_∞≤ nC1-λ^κ+1\|b^π\|_∞, which gives Bκπ≤nC2(1−λ)λκ+1‖bπ‖∞.B_κ^π≤ nC2(1-λ)λ^κ+1\|b^π\|_∞. This completes the proof. D.2 Preliminaries for the block-improvement step Throughout this subsection, fix a baseline product policy π and write Aπ(s,a)=r(s,a)−r¯π+∑yP(y∣s,a)hπ(y)−hπ(s).A^π(s,a)=r(s,a)- r^π+ _yP(y s,a)h^π(y)-h^π(s). Lemma D.1 (Advantage perturbation via value perturbation modulo constants). Let h h be any function on S and define A^(s,a)=r(s,a)−r¯π+∑yP(y∣s,a)h^(y)−h^(s). A(s,a)=r(s,a)- r^π+ _yP(y s,a) h(y)- h(s). Then sups∈,a∈|A^(s,a)−Aπ(s,a)|≤ 2infc∈ℝ‖h^−hπ−c‖∞. _s ,\ a | A(s,a)-A^π(s,a)|\ ≤\ 2 _c \| h-h^π-c1\|_∞. Proof D.2. For any constant c∈ℝc , replacing h h by h^+c h+c1 does not change A A, because the additive constant cancels between the transition term and the state term. Hence, for every c, |A^(s,a)−Aπ(s,a)| | A(s,a)-A^π(s,a)| =|∑yP(y∣s,a)(h^(y)+c−hπ(y))−(h^(s)+c−hπ(s))| = | _yP(y s,a) ( h(y)+c-h^π(y) )- ( h(s)+c-h^π(s) ) | ≤∑yP(y∣s,a)|h^(y)+c−hπ(y)|+|h^(s)+c−hπ(s)| ≤ _yP(y s,a)\,| h(y)+c-h^π(y)|+| h(s)+c-h^π(s)| ≤2‖h^−hπ−c‖∞. ≤ 2\| h-h^π-c1\|_∞. Taking the supremum over (s,a)(s,a) and then the infimum over c proves the claim. Lemma D.3 (Per-state KL-prox duality). Fix a finite action set A, a reference distribution q∈Δ()q∈ (A) with q(a)>0q(a)>0 for all a (or, equivalently, restrict the maximization to distributions absolutely continuous with respect to q), a score vector g∈ℝg ^A, and η>0η>0. Then maxp∈Δ()⟨p,g⟩−ηKL(p∥q)=ηlog∑a∈q(a)eg(a)/η, _p∈ (A) \ p,g -η\,KL(p\|q) \=η _a q(a)e^g(a)/η, attained uniquely at p⋆(a)∝q(a)eg(a)/η.p (a) q(a)e^g(a)/η. Moreover, ⟨p⋆−q,g⟩≥ηKL(p⋆∥q). p -q,\ g \ ≥\ η\,KL(p \|q). Proof D.4. The maximization is the standard log-sum-exp / Donsker–Varadhan variational formula. The Lagrangian for the constraint ∑ap(a)=1 _ap(a)=1 has gradient g(a)−ηlog(p(a)/q(a))−η−λ=0g(a)-η (p(a)/q(a))-η-λ=0, which gives p(a)∝q(a)eg(a)/ηp(a) q(a)e^g(a)/η. The value of the objective at p⋆p is ηlog∑aq(a)eg(a)/η _aq(a)e^g(a)/η by direct substitution, and uniqueness follows from strict convexity of KL(⋅∥q)KL(·\|q) on the simplex. For the final inequality, evaluate the objective at p=qp=q: ⟨q,g⟩−ηKL(q∥q)=⟨q,g⟩ q,g - (q\|q)= q,g . By optimality of p⋆p , ⟨p⋆,g⟩−ηKL(p⋆∥q)≥⟨q,g⟩, p ,g - (p \|q)\ ≥\ q,g , which rearranges to ⟨p⋆−q,g⟩≥ηKL(p⋆∥q) p -q,g ≥ (p \|q). Lemma D.5 (One-block performance difference). Let π be a product policy and let μ be another product policy such that μ−k=π−k _-k= _-k for some agent k. Assume the Markov chain under μ is irreducible with stationary distribution dμd^μ. Define gk,⋆π(s,ak)≔a−k∼∏j≠kπj(⋅∣s)[Aπ(s,(ak,a−k))].g_k, ^π(s,a_k) *E_a_-k _j≠ k _j(· s) [A^π(s,(a_k,a_-k)) ]. Then r¯(μ)−r¯(π)=S∼dμ[⟨μk(⋅∣S)−πk(⋅∣S),gk,⋆π(S,⋅)⟩]. r(μ)- r(π)= *E_S d^μ [ _k(· S)- _k(· S),\ g_k, ^π(S,·) ]. Proof D.6. Using the Poisson equation for hπh^π, hπ−Tπhπ=rπ−r¯π,h^π-T^πh^π=r^π- r^π, one obtains the standard average-reward performance-difference identity r¯(μ)−r¯(π)=S∼dμ,A∼μ(⋅∣S)[Aπ(S,A)]. r(μ)- r(π)= *E_S d^μ,\ A μ(· S) [A^π(S,A) ]. Indeed, dμ,μ[Aπ] *E_d^μ,μ[A^π] =dμ,μ[r(S,A)−r¯π+∑yP(y∣S,A)hπ(y)−hπ(S)] = *E_d^μ,μ\! [r(S,A)- r^π+ _yP(y S,A)h^π(y)-h^π(S) ] =dμ,μ[r(S,A)]−r¯π+S′∼dμ[hπ(S′)]−S∼dμ[hπ(S)] = *E_d^μ,μ[r(S,A)]- r^π+ *E_S d^μ[h^π(S )]- *E_S d^μ[h^π(S)] =r¯(μ)−r¯(π), = r(μ)- r(π), where the middle two terms cancel by stationarity of dμd^μ under μ. Now use μ−k=π−k _-k= _-k: A∼μ(⋅∣s)[Aπ(s,A)]=∑akμk(ak∣s)gk,⋆π(s,ak)=⟨μk(⋅∣s),gk,⋆π(s,⋅)⟩. *E_A μ(· s)[A^π(s,A)]= _a_k _k(a_k s)\,g_k, ^π(s,a_k)= _k(· s),g_k, ^π(s,·) . Likewise, ⟨πk(⋅∣s),gk,⋆π(s,⋅)⟩=A∼π(⋅∣s)[Aπ(s,A)]=0. _k(· s),g_k, ^π(s,·) = *E_A π(· s)[A^π(s,A)]=0. Therefore A∼μ(⋅∣s)[Aπ(s,A)]=⟨μk(⋅∣s)−πk(⋅∣s),gk,⋆π(s,⋅)⟩. *E_A μ(· s)[A^π(s,A)]= _k(· s)- _k(· s),\,g_k, ^π(s,·) . Averaging over S∼dμS d^μ proves the claim. D.3 Proof of Theorem 5.2 Fix π, k, and κ. First, by Lemma D.1 with h^=h^κπ h= h_κ^π, sups,a|A^κπ(s,a)−Aπ(s,a)|≤2Bκπ. _s,a| A_κ^π(s,a)-A^π(s,a)|≤ 2B_κ^π. Taking expectation over a−k∼∏j≠kπj(⋅∣s)a_-k _j≠ k _j(· s) preserves the sup norm, so ‖g^k,κπ−gk,⋆π‖∞≤2Bκπ.\| g_k,κ^π-g_k, ^π\|_∞≤ 2B_κ^π. Now consider the policy μ defined by μk(⋅∣s)∝πk(⋅∣s)exp(g^k,κπ(s,⋅)/η),μ−k=π−k. _k(· s) _k(· s) \! ( g_k,κ^π(s,·)/η ), _-k= _-k. For each fixed state s, Lemma D.3 with q=πk(⋅∣s),g=g^k,κπ(s,⋅),p⋆=μk(⋅∣s)q= _k(· s), g= g_k,κ^π(s,·), p = _k(· s) gives ⟨μk(⋅∣s)−πk(⋅∣s),g^k,κπ(s,⋅)⟩≥ηKL(μk(⋅∣s)∥πk(⋅∣s)). _k(· s)- _k(· s),\ g_k,κ^π(s,·) ≥η\,KL ( _k(· s)\,\|\, _k(· s) ). Subtract and add the exact logit: ⟨μk−πk,gk,⋆π⟩ _k- _k,\ g_k, ^π =⟨μk−πk,g^k,κπ⟩+⟨μk−πk,gk,⋆π−g^k,κπ⟩ = _k- _k,\ g_k,κ^π + _k- _k,\ g_k, ^π- g_k,κ^π ≥ηKL(μk∥πk)−‖μk−πk‖1‖g^k,κπ−gk,⋆π‖∞ ≥η\,KL( _k\| _k)-\| _k- _k\|_1\,\| g_k,κ^π-g_k, ^π\|_∞ ≥ηKL(μk∥πk)−2‖g^k,κπ−gk,⋆π‖∞ ≥η\,KL( _k\| _k)-2\| g_k,κ^π-g_k, ^π\|_∞ ≥ηKL(μk∥πk)−4Bκπ, ≥η\,KL( _k\| _k)-4B_κ^π, where all distributions are evaluated at the same state s and we used ‖μk−πk‖1≤2\| _k- _k\|_1≤ 2. Finally, average over S∼dμS d^μ and apply Lemma D.5: r¯(μ)−r¯(π)=S∼dμ[⟨μk(⋅∣S)−πk(⋅∣S),gk,⋆π(S,⋅)⟩] r(μ)- r(π)= *E_S d^μ [ _k(· S)- _k(· S),\ g_k, ^π(S,·) ] ≥ηS∼dμ[KL(μk(⋅∣S)∥πk(⋅∣S))]−4Bκπ.≥η\, *E_S d^μ [KL ( _k(· S)\,\|\, _k(· S) ) ]-4B_κ^π. Substituting the bound from Theorem 5.1, Bκπ≤nC2(1−λ)λκ+1‖bπ‖∞,B_κ^π≤ nC2(1-λ)λ^κ+1\|b^π\|_∞, yields r¯(μ)−r¯(π)≥ηS∼dμ[KL(μk(⋅∣S)∥πk(⋅∣S))]−2nC1−λκ+1∥bπ∥∞. r(μ)- r(π)≥η\, *E_S d^μ [KL ( _k(· S)\,\|\, _k(· S) ) ]- 2nC1-λ^κ+1\|b^π\|_∞. This proves the theorem. Appendix E Miscellaneous Results E.1 Example: A Coupled System where Policy Smoothing is Ineffective Our framework also captures the failure mode where policy smoothing cannot create locality because the environment itself has strong direct state-to-state feedback. Consider two agents with binary states and arbitrary actions. Suppose the next states deterministically copy each other: P1(s1′=1∣s,a)=s2=1,P2(s2′=1∣s,a)=s1=1.P_1(s _1=1 s,a)=1\s_2=1\, P_2(s _2=1 s,a)=1\s_1=1\. Actions have no effect on the next state. Hence Ea=0,Es=(0110),E^a=0, E^s= pmatrix0&1\\ 1&0 pmatrix, where rows and columns are indexed by the influence convention j←ij← i. Therefore Hπ=Es+EaΠ(π)=Es,ρ(Hπ)=1.H^π=E^s+E^a (π)=E^s, ρ(H^π)=1. The policy sensitivity matrix Π(π) (π) is irrelevant because the action-coupling channel is absent. Thus no amount of policy smoothing can make ρ(Hπ)<1ρ(H^π)<1 in this example. This illustrates the complementary failure mode to the policy-induced locality examples: if the environment has an unstable direct state-feedback loop, the policy cannot remove it unless actions actually mediate that coupling. E.2 Example: policy-induced locality in a nonlocal-looking system. Consider a hub–and–spoke system with n≥3n≥ 3 agents. Let P1P_1 be constant and, for j>1j>1, Pj(sj′=1∣s,a)=a1=1P_j(s _j=1 s,a)=1\a_1=1\. Then Es=0E^s=0 and Ej←1a=1E^a_j← 1=1 for all j>1j>1 (others zero). A policy-independent, action-supremum certificate declares the system non-local (‖C‖∞=1\|C\|_∞=1) (qu_scalabale_marl_2020). Under a temperature-τ softmax for agent 1 with logit Lipschitz constants L1←i\L_1← i\, Lemma 4.3 gives Π1←i≤L1←i/(2τ) _1← i≤ L_1← i/(2τ) and hence ρ(Hπ)≤ρ(EaL2τ)=12τ∑i>1L1←i≤(n−1)Lmax2τ,ρ(H^π)\ ≤\ ρ\! (E^a L2τ )\ =\ 12τ _i>1L_1← i\ ≤\ (n-1)L_ 2τ, Thus locality is certified whenever τ>(n−1)Lmax/2τ>(n-1)L_ /2, and if the hub ignores its inputs (L≡0L≡ 0) then ρ(Hπ)=0ρ(H^π)=0. This illustrates how locality can be policy-induced, while worst-case, policy-independent tests cannot detect it. E.3 Properties of the Coordinatewise Oscillation Seminorm Let V=B()V=B(S) be the vector space of all bounded real-valued functions on the finite state space =∏i=1niS= _i=1^nS_i. Definition E.1 (Coordinatewise Oscillation). For a function f∈Vf∈ V and a coordinate i∈[n]i∈[n], the i-oscillation is: δi(f)=sup|f(x)−f(y)|:x,y∈,x−i=y−i. _i(f)= \\,|f(x)-f(y)|:x,y ,\ x_-i=y_-i\, \. We define the function p:V→ℝp:V as the maximum oscillation: p(f)=‖δ(f)‖∞=maxi∈[n]δi(f).p(f)= δ(f) _∞= _i∈[n] _i(f). Proposition E.2. The function p(f)=‖δ(f)‖∞p(f)= δ(f) _∞ is a seminorm on the vector space V. Proof E.3. To prove that p(f)p(f) is a seminorm, we must verify three properties: 1. Non-negativity: p(f)≥0p(f)≥ 0 for all f∈Vf∈ V. 2. Absolute Homogeneity: p(cf)=|c|p(f)p(cf)=|c|p(f) for all f∈Vf∈ V and scalar c∈ℝc . 3. Subadditivity (Triangle Inequality): p(f+g)≤p(f)+p(g)p(f+g)≤ p(f)+p(g) for all f,g∈Vf,g∈ V. 1. Non-negativity: The absolute value |f(x)−f(y)||f(x)-f(y)| is always non-negative. The supremum of a set of non-negative numbers, δi(f) _i(f), is also non-negative. The maximum of a set of non-negative numbers, p(f)p(f), is therefore non-negative. 2. Absolute Homogeneity: For any f∈Vf∈ V and c∈ℝc : δi(cf) _i(cf) =supx−i=y−i|(cf)(x)−(cf)(y)| = _x_-i=y_-i|(cf)(x)-(cf)(y)| =supx−i=y−i|c⋅(f(x)−f(y))| = _x_-i=y_-i|c·(f(x)-f(y))| =|c|⋅supx−i=y−i|f(x)−f(y)|=|c|⋅δi(f). =|c|· _x_-i=y_-i|f(x)-f(y)|=|c|· _i(f). Taking the maximum over all i: p(cf)=maxi∈[n]δi(cf)=maxi∈[n](|c|⋅δi(f))=|c|⋅maxi∈[n]δi(f)=|c|⋅p(f).p(cf)= _i∈[n] _i(cf)= _i∈[n] (|c|· _i(f) )=|c|· _i∈[n] _i(f)=|c|· p(f). 3. Subadditivity: For any f,g∈Vf,g∈ V: δi(f+g) _i(f+g) =supx−i=y−i|(f+g)(x)−(f+g)(y)| = _x_-i=y_-i|(f+g)(x)-(f+g)(y)| =supx−i=y−i|(f(x)−f(y))+(g(x)−g(y))| = _x_-i=y_-i|(f(x)-f(y))+(g(x)-g(y))| ≤supx−i=y−i(|f(x)−f(y)|+|g(x)−g(y)|)(by the triangle inequality for ℝ) ≤ _x_-i=y_-i (|f(x)-f(y)|+|g(x)-g(y)| ) (by the triangle inequality for $ R$) ≤supx−i=y−i|f(x)−f(y)|+supx−i=y−i|g(x)−g(y)|(by a standard property of suprema) ≤ _x_-i=y_-i|f(x)-f(y)|+ _x_-i=y_-i|g(x)-g(y)| (by a standard property of suprema) =δi(f)+δi(g). = _i(f)+ _i(g). Now, taking the maximum over all i: p(f+g)=maxi∈[n]δi(f+g)≤maxi∈[n](δi(f)+δi(g)).p(f+g)= _i∈[n] _i(f+g)≤ _i∈[n]( _i(f)+ _i(g)). For any i, we know δi(f)≤maxjδj(f)=p(f) _i(f)≤ _j _j(f)=p(f) and δi(g)≤maxjδj(g)=p(g) _i(g)≤ _j _j(g)=p(g). Thus: p(f+g)≤maxi∈[n](p(f)+p(g))=p(f)+p(g).p(f+g)≤ _i∈[n](p(f)+p(g))=p(f)+p(g). This completes the proof. Remark E.4 (Why it is a seminorm, not a norm). A norm requires p(f)=0⇔f=0p(f)=0 f=0. For our p(f)p(f), if f(x)=cf(x)=c for some non-zero constant c, then f≠0f≠ 0. However, for any i and any pair x,yx,y with x−i=y−ix_-i=y_-i, f(x)=cf(x)=c and f(y)=cf(y)=c, so |f(x)−f(y)|=0|f(x)-f(y)|=0. This implies δi(f)=0 _i(f)=0 for all i, and thus p(f)=0p(f)=0. Since p(f)=0p(f)=0 for non-zero constant functions, p(f)p(f) is a seminorm. In fact, p(f)=0⇔f is a constant function.p(f)=0 f is a constant function. Proposition E.5. The value p(f)=‖δ(f)‖∞p(f)= δ(f) _∞ is the (best) Lipschitz constant of f with respect to the Hamming distance dH(⋅,⋅)d_H(·,·) on S. Proof E.6. Let K=p(f)K=p(f). We must show that for any x,z∈x,z , |f(x)−f(z)|≤K⋅dH(x,z)|f(x)-f(z)|≤ K· d_H(x,z). Case 1: dH(x,z)=1d_H(x,z)=1. If dH(x,z)=1d_H(x,z)=1, then x and z differ in exactly one coordinate, say j. This means x−j=z−jx_-j=z_-j. By the definition of δj(f) _j(f): |f(x)−f(z)|≤supx−j′=y−j′|f(x′)−f(y′)|=δj(f).|f(x)-f(z)|≤ _x _-j=y _-j|f(x )-f(y )|= _j(f). By the definition of p(f)p(f), δj(f)≤maxiδi(f)=p(f)=K _j(f)≤ _i _i(f)=p(f)=K. Therefore, |f(x)−f(z)|≤K=K⋅dH(x,z)|f(x)-f(z)|≤ K=K· d_H(x,z). This also shows that K is the best Lipschitz constant for pairs at distance 1. Case 2: dH(x,z)=k>1d_H(x,z)=k>1. Let the coordinates where x and z differ be I=i1,…,ikI=\i_1,…,i_k\. We can construct a path from x to z by changing one coordinate at a time. Let z(0)=xz^(0)=x, and let z(t)z^(t) be the state obtained by changing the first t coordinates in I from their values in x to their values in z. For example, z(1)z^(1) is identical to x except zi1(1)=zi1z^(1)_i_1=z_i_1. In general, z(t)z^(t) and z(t+1)z^(t+1) differ only in coordinate it+1i_t+1. Thus, dH(z(t),z(t+1))=1d_H(z^(t),z^(t+1))=1. The full path is x=z(0),z(1),…,z(k)=zx=z^(0),z^(1),…,z^(k)=z. Using the triangle inequality, we “telescope” the sum: |f(x)−f(z)| |f(x)-f(z)| =|f(z(0))−f(z(k))| =|f(z^(0))-f(z^(k))| =|∑t=0k−1(f(z(t))−f(z(t+1)))| = | _t=0^k-1 (f(z^(t))-f(z^(t+1)) ) | ≤∑t=0k−1|f(z(t))−f(z(t+1))|. ≤ _t=0^k-1|f(z^(t))-f(z^(t+1))|. For each term in the sum, z(t)z^(t) and z(t+1)z^(t+1) differ in exactly one coordinate, so dH(z(t),z(t+1))=1d_H(z^(t),z^(t+1))=1. From Case 1, we know: |f(z(t))−f(z(t+1))|≤p(f)=K.|f(z^(t))-f(z^(t+1))|≤ p(f)=K. Substituting this into the sum: |f(x)−f(z)|≤∑t=0k−1K=k⋅K.|f(x)-f(z)|≤ _t=0^k-1K=k· K. Since k=dH(x,z)k=d_H(x,z), we have shown: |f(x)−f(z)|≤K⋅dH(x,z).|f(x)-f(z)|≤ K· d_H(x,z). This holds for all x,z∈x,z , so p(f)p(f) is the Lipschitz constant of f w.r.t. dHd_H. Optimality. Let L be any constant such that |f(x)−f(y)|≤L|f(x)-f(y)|≤ L, dH(x,y)d_H(x,y) for all x,yx,y. Fix i and x,yx,y with x−i=y−ix_-i=y_-i; then dH(x,y)=1d_H(x,y)=1, so |f(x)−f(y)|≤L|f(x)-f(y)|≤ L. Taking the supremum over such pairs gives δi(f)≤L _i(f)≤ L, hence p(f)=maxiδi(f)≤Lp(f)= _i _i(f)≤ L. Therefore p(f)p(f) is the least Lipschitz constant.