Embodiment-Induced Coordination Regimes in Tabular Multi-Agent Q-Learning

Abstract:Centralized value learning underlies a broad class of multi-agent reinforcement learning methods, but its claimed advantage is typically evaluated in settings that confound coordination structure with function approximation and partial observability. We isolate coordination structure in a fully tabular 8x8 predator-prey gridworld with explicit speed and stamina constraints, comparing all four pairings of Independent and Centralized Q-Learning across three kinematic regimes over 10 seeds. Fully independent learning (IQL-IQL) yields shorter episodes and higher predator returns than the fully centralized configuration (CQL-CQL) in every regime and every seed (Wilcoxon p = 0.00195, Cliff's delta = 1.0). Asymmetric IQL-CQL pairings produce coordination breakdowns that persist across the 40,000 episode training budget rather than resolving as transient instability. A best-response test against frozen IQL-IQL predators shows that even the strongest configuration has not converged to equilibrium at 40k episodes, so between-configuration differences reflect learning dynamics under a shared budget rather than end-state performance. We propose a mechanism we call temporal synchronization lock: a shared value function couples all agent decisions, so when one agent is stamina-limited the joint Q-value forces capable partners into suboptimal waits, while independent learners continue asynchronous pursuit. Because this pathology arises from credit assignment rather than function approximation, we conjecture analogous effects may arise in deep MARL methods that centralize credit during training. Centralized coordination is not uniformly beneficial; its advantage over independent learning shrinks or disappears under embodiment constraints, and mixed centralized-independent pairings can perform worse than either uniform choice.

Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)

arXiv:2601.17454 [cs.MA]

(or arXiv:2601.17454v2 [cs.MA] for this version)

https://doi.org/10.48550/arXiv.2601.17454 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.