Thinking Beyond Visibility: A Near-Optimal Policy Framework for Locally Interdependent Multi-Agent MDPs

Decentralized control under partial observability is central to robotics, autonomous driving, UAV swarms, and distributed navigation, but classical Dec-POMDP formulations are notoriously intractable. The earlier LIMMDP framework from DeWeese & Qu (2024) captured local interaction structure more faithfully: only agents within distance R contribute to rewards, and communication is induced by a larger visibility radius V. That work produced three closed-form stationary policies and proved they are exponentially close to optimal in visibility, with matching lower bounds. The present paper extends that line by asking whether low visibility can be handled not just asymptotically, but behaviorally.

The core problem is that small, fixed visibility breaks the implicit memoryless assumption of the original closed-form policies. When agents disconnect, the policy may lose track of where they were, which can trigger oscillations, deadlocks, or repeated collision-avoidance maneuvers—the Penalty Jittering phenomenon. The challenge is to design a policy family that is still broadly applicable to any LIMMDP instance, remains theoretically near-optimal, and yet uses historical information well enough to avoid these failures in practical small-visibility regimes.

1) Extended Cutoff Policy Class: a new family of partially observable policies that keeps track of agents beyond current visibility. Why needed: fixed visibility can be too short for stable coordination. Difference: unlike the original stationary policies, the class has explicit memory.

2) Cutoff Multi-Agent MDP: states are augmented with a partition P, and disconnected groups cannot reconnect. Why needed: this makes subgroup values separable. Difference: it turns local interaction into a tractable, permanent decomposition.

3) Solve-then-execute with expanded planning visibility: use V_comp>V_exec only during computation. Why needed: it creates a richer planning graph while preserving execution constraints. Difference: it is a theoretical analogue of centralized training/decentralized execution, but with tunable connectivity.

4) Generalized LIMMDP: allows transition dependence and extended reward dependence. Why needed: some real tasks have richer local coupling. Difference: it preserves the paper’s main guarantees beyond the independent-transition case.

• �� Start from a LIMMDP with agents in a metric space, local interaction radius R, and execution visibility V_exec. The objective is the discounted return V^\pi(s)=E[\sum_t \gamma^t r(s(t),a(t))].
• �� Define a Cutoff MDP whose state is (s,P), where P is a partition finer than the communication partition Z(s). Once agents split, the transition updates the partition by intersection with the next visibility partition, so disconnected groups never reconnect.
• �� Restrict policies to proper cutoff policies of the form \pi(a|(s,P))=\prod_{p\in P}\pi_p(a_p|s_p). This makes the control problem decomposable at the level of groups.
• �� Compute on an expanded visibility V_comp=V_exec+\xi and horizon c+\eta, where c=\lfloor (V_exec-R)/2 \rfloor. The larger planning graph serves as the policy’s “thinking radius.”
• �� Use subgroup Bellman equations such as V_h^*(s_p,{p})=max_{a_p}Q_h^*((s_p,{p}),a_p), so the algorithm only stores and updates values for subgroup states rather than the full joint state.
• �� Execute the derived policy back in the original LIMMDP with V_exec, but retain memory of previously observed agents, enabling decisions based on past observations as well as current neighborhood structure.

The excerpt is primarily theoretical; it does not report standard benchmark tables, datasets, or success rates. The empirical evidence mentioned is illustrative: a large square-grid example under Chebyshev distance, and the Appendix A.8 ‘Random Navigation With Many Agents’ scenario, where the authors discuss tractability for 100 agents without deep learning. The paper also derives a state-count upper bound using \ell=2(n-1)V+1 and m=\ell^2, showing how group-state storage scales more favorably than the full joint state space M^n when local groups are small.

The key result is a near-optimality theorem: policies in the Extended Cutoff class are exponentially close to the fully observable joint optimum as a function of visibility, and the rate is tight up to constants against the prior lower bound. A second result is practical: in small, fixed visibility settings, the new class addresses the memoryless failure mode that made the earlier three closed-form policies prone to Penalty Jittering. A third result is structural: the theory extends to a generalized model with transition dependence and extended reward dependence, suggesting the method is robust to richer local couplings.

Immediate use cases include multi-robot warehouse navigation, where robots must avoid local collisions while sharing only neighborhood information, and UAV formation flight, where agents need to preserve shape under limited sensing. The framework is also relevant to obstacle avoidance, with obstacles modeled as agents with singleton action sets. In industry, the main value is a principled decentralized controller that is computationally tractable, interpretable, and backed by near-optimality guarantees rather than purely empirical tuning.

The framework assumes strong locality: bounded interaction radius, bounded movement, and partition-based communication. Those assumptions are sensible for many robotic systems but not for tasks with long-range dependencies or globally coupled rewards. The provided excerpt also lacks broad experimental benchmarks, so the practical gain over competing methods is mostly inferred from theory and a small set of illustrative simulations. Finally, computational visibility V_comp can be larger than execution visibility, so the planning step may become expensive when groups are large; heuristics remain necessary in large-scale settings.