Escaping Coordination Traps by Sequencing Team Decisions at Macro-Action Boundaries

When a team of learning agents must coordinate, each agent usually improves its own behavior while treating its teammates as fixed. This tends to stall in "good enough" joint behaviors. A standard example is two robots that each learn to push small boxes alone because trying to push the big box together is punished whenever the partner doesn't show up. One known fix is to rewrite the team problem as a single agent that picks each teammate's action in turn. The Transformation and Distillation approach (TAD) does this and recovers guarantees of reaching the best joint behavior. Its cost is that every clock tick becomes $N$ decisions, so the horizon grows $N$-fold. Meanwhile, practical team tasks are increasingly posed with macro-actions, multi-step behaviors such as "go to the box" or "fetch the tool" that run for different, unpredictable durations. Macro-action methods shorten the horizon, but they inherit the same coordination traps. They also execute each macro-action blindly, so one robot's slip quietly derails its teammates.

We propose to apply the turn-by-turn rewrite only at the moments when some agent actually has to choose a new macro-action, rather than at every clock tick. We add one more trigger: a learned detector that declares a macro-action failed mid-execution. That failure becomes a new decision moment at which every teammate may choose to continue or switch, so the episode is not aborted. The bet is that one construction addresses three problems together. It keeps TAD's escape from coordination traps. It shrinks the decision horizon instead of multiplying it. And it turns cascading execution errors into extra, cheap decision points instead of wasted episodes. If the bet holds, it should show up as fewer environment samples needed to reach the coordinated optimum on asynchronous benchmarks.

Core Claim

A cooperative team with variable-duration macro-actions can be trained as a single sequential decision-maker whose "turns" occur only at decision events. A decision event is any moment where at least one agent finishes, fails, or times out on its macro-action. At each event, the agents that are free choose one after another, each conditioned on the choices already made in this event and on the macro-actions their busy teammates are still running.

Under centralized training, the process observed at these events is Markov. Here "Markov" means that the joint state plus each agent's ongoing macro-action and its elapsed time summarizes everything relevant. Single-agent policy optimization over this process therefore inherits TAD's argument for reaching the best joint behavior. That optimum is defined relative to the given macro-action set and the interruption rule, not over all primitive policies, and we state that restriction openly. The number of sequential decisions per episode drops from TAD's $N \cdot T$ to roughly

$$D \approx \sum_{i=1}^{N} \frac{T}{\bar H_i} + F,$$

where $T$ is the episode length in clock ticks, $\bar H_i$ is agent $i$'s average macro-action duration, and $F$ is the number of failure-triggered events. The form comes from counting one turn per macro-action start plus one round per detected failure.

The proposal stands or falls on whether this smaller, event-driven sequential problem actually escapes traps that asynchronous value-factorization methods fall into. It must do so with fewer samples, and without failure interrupts either exploding $F$ or truncating learning the way hard episode aborts do.

How This Relates to Existing Work

Three lines of prior work each cover part of this.

The first supplies the method. TAD proves that gradient descent on decentralized policies causes suboptimality. It fixes this by converting the team problem into a sequential single-agent problem, then distilling the result into per-agent policies. It operates on primitive steps with a fixed agent order and an $N\times T$ horizon. We keep its transformation-plus-distillation structure but move it from clock ticks to macro-action events. FOP reaches global optima through a factorization that is likewise defined only for simultaneous one-step actions.

The second line motivates the gap. ToMacVF and ACAC handle asynchronous macro-actions properly. ToMacVF uses segmented replay and attention-generated mixing weights. ACAC uses agent-centric encoders and an advantage estimate discounted over decision points instead of ticks. Both still rely on factorized or monotonic value structures with no optimality argument. Neither can interrupt a macro-action that is going wrong. We borrow ACAC's event-indexed discounting and agent-centric encoding as the encoder of our sequential policy, and we change the decision structure on top of it.

The third line constrains the failure-handling design. Strict Subgoal Execution shows that hindsight relabeling hides infeasible subgoals. Its "reach-it-or-fail" episode termination fixes this for a single agent, reaching nearly 100% on AntDoubleKeyChest where HIRO and HIGL got 0%. The research file itself flags that aborting whole team episodes would be ruinous for sample efficiency. We keep SSE's unmasked failure labels, but we spend each failure as a new decision event rather than as a termination. GMAH triggers early subgoal updates from state-change and policy-divergence signals over a hand-built task tree. Our interrupt instead comes from a learned completion predictor, and it reopens decisions for the whole team, not only the agent that failed.

HMASD learns team and individual skills and runs them open-loop for fixed intervals. Its finding that only about 24% of discovered skills contribute to winning is one reason we start from given macro-actions. That choice separates the coordination question from the skill-discovery question.

Research Program

The system has three parts.

The first is the event-driven sequential policy. At every decision event, a centralized model enumerates the agents who must act. These are free agents, plus all agents if the event was a failure. The model has them choose in an order produced by a small learned scorer, so the order is not fixed as in TAD. Each choice is conditioned on the shared state, on the ongoing macro-actions and elapsed times of busy agents, and on choices already made in this round. For busy agents, "continue" is an explicit action. The policy is trained with PPO, discounting rewards over elapsed clock time between events in the manner of ACAC. Implementation details follow the MAPPO recipe: value normalization, bounded data reuse, and clip $\le 0.2$.

The second is a completion predictor. This is a head that estimates, for each running macro-action, the probability that it finishes successfully given the current state. It is trained on unrelabeled outcome labels (success, failure, timeout), following SSE's argument. When the predicted probability falls below a threshold, a failure event fires. We sweep that threshold, and we also report how many failure events fire per episode, because a predictor that fires constantly would destroy the horizon savings.

The third is distillation. As in TAD, the sequential team policy is distilled into decentralized per-agent policies that act from local histories at each agent's own decision points. Each agent also runs its own copy of the completion predictor for interrupts. We measure the gap between the centralized and the distilled policy directly. Under partial observability, this gap is where the optimality story could leak.

The analysis component is a statement and proof sketch. It covers the Markov property of the event-indexed process with the augmented state, and the resulting optimality relative to the macro-action set. It also gives an empirical check of the horizon count $D$ against TAD's $N\cdot T$ on every benchmark.

Baselines

The naive reference point is MAPPO with observation padding on macro-actions: hold each busy agent's last observation until it decides again, then run standard synchronous training. ACAC reports that padding baselines fail to learn coordination on Overcooked-Large. Including this baseline confirms that our task variants reproduce that failure. Beating it is necessary but uninteresting.

The strongest competitors on the actual question are ACAC and ToMacVF. Both are designed for exactly these asynchronous benchmarks, and both reportedly lead their comparisons. ToMacVF stays stable from bp6 to bp14 where AVF collapses. ACAC is "often the only algorithm" to reach near-optimal returns on Overcooked-Large. The file gives no exact scores for either: no reported result was found on Lacuna for ACAC's absolute return on Overcooked-Large or for ToMacVF's success rates on BoxPushing. We will therefore rerun both from their released configurations. Each method gets the same environment-step budget and the same macro-action sets. Hyperparameter tuning is matched at the same number of trials per method, tuned on bp10 and held fixed elsewhere. Beating them means three things. Our method must reach the coordinated optimum (the big box in BoxPushing) on a larger fraction of seeds. It must need fewer environment steps to reach a fixed success threshold. And the gap must widen as map size grows.

The third baseline is TAD-PPO on primitive actions, because it holds the optimality guarantee we are trying to keep. It is run with the same budget, and in a second variant with fixed action repeat of $H$ ticks, $H$ set to the median macro-action length. Beating it means matching its optimum-finding on the didactic games while needing substantially fewer samples on the long-horizon maps.

Two ablations isolate our ingredients. The first keeps everything identical, including the encoder, event discounting, and completion predictor, but lets free agents choose simultaneously from a factorized policy instead of sequentially. This tests whether the sequential rewrite, rather than the architecture, is what escapes traps. The second varies failure handling: no interrupt, interrupt that re-plans only the failed agent, interrupt that re-plans the whole team (ours), and SSE-style episode abort.

Why not just…?

Why not just tune ACAC or ToMacVF harder, with more exploration? This is the real threat. The benchmarks where they shine may contain no trap deep enough to matter. If they match us on standard BoxPushing, that is a genuine negative result. For that reason we add task variants in which the miscoordination valley is explicit and can be adjusted. The simultaneous-choice ablation then tells us whether any advantage comes from sequencing or merely from our encoder. We also give the competitors an entropy bonus sweep within the shared tuning budget, so "more exploration" is actually tried rather than dismissed.

Why not just run TAD-PPO with frame-skipping? Fixed action repeat does shrink TAD's horizon. It also forces every agent onto the same rhythm and cuts macro-actions at arbitrary points. In Warehouse and Overcooked, task durations vary, so a fixed $H$ either truncates fetches or idles agents. Asynchronous credit assignment fails in exactly this way: ToMacVF reports that coarse, unsegmented macro-action replay collapses on large BoxPushing maps. The fixed-repeat TAD variant tests this directly. If it matches us, the event-driven construction is unnecessary and we will say so.

Why not just add an intrinsic exploration bonus such as episodic-memory incentives to flat MAPPO? EMU does pull agents out of plateaus on SMAC. Bonuses still push a decentralized gradient learner, which TAD argues is the structural cause of suboptimal equilibria. They also add nothing against execution drift. We include an EMU-style bonus on the padded MAPPO baseline in the didactic game to check whether it alone crosses the valley.

Why not just abort the episode on failure, as SSE does? In a team, one agent's temporary blockage would end everyone's episode. We expect that to waste most samples under injected execution noise. The failure-handling ablation measures this directly as steps-to-threshold for abort versus re-plan.

Proposed Experiments

The didactic test is an asynchronous version of the non-monotonic matrix game, using the rewards described in the FOP and TAD papers: $+10$ for coordinated $(2,2)$, $+5$ for $(1,1)$, and $-100$ for miscoordination. Each "action" is a macro-action of random duration, so agents must commit asynchronously. Both TAD and FOP report finding the global optimum in the synchronous version, with no numeric rates given. We report the fraction of 20 seeds converging to $+10$.

The main benchmarks are BoxPushing bp6 through bp14, Warehouse, and Overcooked-Large, the macro-action environments used by ToMacVF and ACAC. To create a valley we can adjust, we add a BoxPushing variant whose small-box reward rises toward the big-box reward. Separately, we stress all tasks with injected execution noise: random slips and transient teammate blockages at controlled rates. The primary metrics are three. The first is the fraction of seeds reaching the coordinated optimum. The second is environment steps to a fixed return threshold. The third is final return with confidence intervals. Secondary metrics are decision events per episode, compared against TAD's $N\cdot T$; failure events per episode; and the centralized-to-distilled performance gap.

Three outcomes are decisive. First, on the adjustable-valley BoxPushing variant, our method should keep finding the big-box solution at small-box rewards where ACAC, ToMacVF, and the simultaneous-choice ablation switch to the small-box equilibrium. Second, it should need clearly fewer samples than primitive TAD-PPO on bp14 and Overcooked-Large. Third, under rising execution noise, whole-team re-planning should degrade more gracefully than no-interrupt, failed-agent-only re-planning, or episode abort.

Any of these can falsify the proposal. If the simultaneous-choice ablation matches the full method, sequencing is not the active ingredient. If fixed-repeat TAD matches it, the event-driven construction is unnecessary. If failure events grow large enough that $D$ approaches $N\cdot T$, the horizon savings disappear exactly when they are needed.