Structural Equivalence and Learning Dynamics in Delayed Cooperative Multi-Agent Reinforcement Learning
Jules Sintes, Ana Bušić, Jiamin Zhu · 2026
Read Structural Equivalence and Learning Dynamics in Delayed Cooperative Multi-Agent Reinforcement Learning by Jules Sintes, Ana Bušić, Jiamin Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04345.txt.
Introduction
Jules Sintes, Ana Bušić, and Jiamin Zhu study delays in groups of cooperating agents that each see only part of their world. A delay can sit in sensing, so agents act on old observations, or in action, so choices take effect late, and the two are often treated as different problems.
The authors prove the two settings are fully equivalent. They allow the same policies and produce the same behaviour. They also share the same best solutions, in any mixed form too. Yet their experiments show learning dynamics differ sharply in practice, so methods tuned for one delay type may not transfer directly to the other.
Catalog record
| CREATOR | Jules Sintes, Ana Bušić, Jiamin Zhu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.04345
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structural Equivalence and Learning Dynamics in Delayed Cooperative Multi-Agent Reinforcement Learning Jules Sintes, Ana Bušić, Jiamin Zhu Abstract We formally establish the equivalence between Observation Delay (OD) and Action Delay (AD) in cooperative partially observable multi-agent systems using observation-action histories. We show that both systems generate identical admissible joint-policy sets, and their induced state-action-observation trajectories are identical in distribution, leading to identical optimal solutions in Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs). This formally generalizes existing infinite-horizon single-agent results to any-horizon partially observable cooperative multi-agent problems with decentralized policy execution, and allows any mixed-delay configuration to be reduced to a pure OD system. We further prove that in Transition-Independent MDPs (TI-MDPs), the observation-action history reduces to a tractable minimal local augmented state. However, we show through numerical experiments that although the optimal solution spaces are structurally isomorphic, the practical learning dynamics are fundamentally different. First, using the minimal local augmented state, the equivalence no longer holds when transitions are not independent. Second, operational constraints and causal credit-assignment errors in Temporal Difference (TD) algorithms induce different learning behaviors across regimes. Finally, leveraging this structural equivalence to bypass these learning challenges, we demonstrate successful multi-agent zero-shot policy transfer from OD to AD, paving the way for unified, efficient solution methods in complex delayed systems. Keywords Reinforcement Learning, Multi-Agent, Dec-POMDP, Delays, Theory 1 Introduction Delay is a central challenge in controllable systems. In robotics and its applications, such as autonomous driving, control delay arises from computational or sensor latency ( 15 ; 7 ) . This problem is even more prevalent in decentralized multi-agent systems, where each controlled agent may have a different delay. This increases the difficulty of coordinated control due to communication delays in network systems ( 8 ; 24 ; 22 ) or physical inertia of the environment, such as in Wind Farms ( 16 ) . Reinforcement Learning (RL) has emerged as a powerful tool for efficient control of increasingly complex systems. While it has demonstrated impressive empirical results in many domains, learning under delay remains highly difficult. Formally, delays can be introduced in RL problems described through the Markov Decision Process (MDP) framework. In this context, 12 showed that OD and AD are formally equivalent in single-agent infinite-horizon problems with asynchronous cost collection. They approached delay equivalence through the lens of state augmentation and cost reshaping. Their method constructs a surrogate MDP where the optimal policy order is preserved. In this paper, we propose a stronger form of equivalence based on observation-action histories , effectively separating the structural equivalence from the learning problem. We show that under a proper initialization, the effective information set available to an agent at the moment of decision for an action is identical in both delay regimes. Consequently, the two regimes generate statistically identical trajectories, establishing a structural isomorphism. This implies that the equivalence holds for any horizon, any cooperative reward objective and structure (e.g., average reward, sparse reward), and under partial observability. Our results strengthen and extend the existing equivalence claim in single-agent scenarios and hold in cooperative multi-agent settings with decentralized policy execution. Consequently, we provide corollaries regarding the additivity of OD and AD when agents are subject to both delays, and show that any system with mixed-regime heterogeneous delays reduces to a pure OD system. Additionally, we propose sufficient statistics for Transition Independent dec-MDP (TI dec-MDP), enabling a more tractable reduction to an undelayed MDP, extending the augmented-state method from the single-agent to the multi-agent case. However, we demonstrate that structural equivalence of the solution space does not imply symmetric learning dynamics. While convergence towards equivalent policy holds, we empirically identify specific operational constraints, such as initialization constraints or causal credit-assignment errors, that render the AD regime harder to learn under standard Temporal Difference algorithms. Furthermore, we provide an empirical counter-example where a tractable augmented state leads to a different optimal policy when breaking Transition Independence. Finally, we demonstrate that the equivalence of policy set still has some practicality by effectively performing zero-shot transfer from OD regime learned policy to AD, on a complex multi-agent coordinated control environment (Multiwalker). The paper is organized as follows. First, we give a comprehensive overview of existing results in the field of delayed reinforcement learning, introducing the core concepts used in this paper. Second, we derive the structural equivalence results and the associated corollaries. Then, we study the practical gap in the learning dynamics under OD and AD through experiments and additional theoretical results. 2 Related Work To the best of our knowledge, there are very few theoretical results regarding delays in Multi-Agent Reinforcement Learning (MARL). Thus, unless explicitly mentioned, results cited in this section are derived for single-agent RL. This work focuses on Observation Delay (OD) and Action Delay (AD). Hence, our theory sets aside the reward collection delay problem. As highlighted by 13 , the problem of reward collection delay mainly affects the performance during the learning phase. It is widely discussed theoretically in terms of regret in the bandit literature ( 11 ) . Here, we only focus on delay regimes as part of the environment that affects the performance of the policy execution. However, we shall discuss some practicality regarding reward collection when dealing with OD or AD. Delays in RL often remain an applied problem in the literature, and most of the existing work focuses on methods to effectively handle delays. RL algorithms for handling delayed systems fall into three categories: Model-based ( 21 ; 5 ; 6 ) , memoryless ( 18 ; 10 ) , and augmented state. The latter is the most straightforward and at the core of OD and AD’s equivalence claim. In single-agent settings, 1 shows that an MDP with constant OD reduces to an undelayed MDP with an augmented space taking into account past decided actions. These results have been extended to AD, and stochastic delay regimes with asynchronous cost collection by 12 . A direct consequence of their augmented state method is the functional equivalence of OD and AD. However, they assume infinite-horizon and a cost collection delay larger than the OD (or AD). In single-agent, 2 propose a delay-aware model-based method for continuous control and use the equivalence argument to justify focusing on AD regime, arguing that their results hold for OD but omitting any discussion regarding the underlying assumption for 12 equivalence to hold in their settings. The method is extended to multi-agent systems, both competitive and cooperative, with the same argument ( 3 ) . In 14 , they use the same argument and choose to develop their algorithm for problems formulated with AD. However, applying this equivalence to multi-agent settings is risky. The original proof relies on specific cost-discounting mechanics that do not trivially extend to decentralized policies or finite-horizon cooperative tasks. It remains an open question whether a rigorous structural equivalence holds in decentralized multi-agent systems. Overall, this work provides a theoretical backbone for the equivalence of OD and AD in cooperative decentralized multi-agent systems, also giving a stronger isomorphism for the single-agent case. Furthermore, we clarify existing claims from the literature, using the equivalence as well as superset arguments to justify applied work on delayed systems. 3 Background 3.1 Cooperative Multi-agent Reinforcement Learning The general framework