Paper deep dive
Bayesian Partner Modelling enables Adaptive Replanning for LLM Coordination
Harsh Goel, Aditya Sai Ellendula, Vaishnav Tadiparthi, Ehsan Moradi Pari, Hossein Nourkhiz Mahjoub, Sandeep P. Chinchali
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/20/2026, 3:45:28 AM
Summary
The paper introduces BayesBeliefAgent, a multi-agent coordination framework for Large Language Model (LLM) agents that addresses the 'belief-action gap' where agents fail to replan despite having accurate partner models. It employs a Bayesian tracking module to infer a teammate's latent skill from observed actions and triggers selective replanning only when observed actions contradict the current skill estimate. This approach significantly reduces the belief-action gap and replanning frequency compared to heuristic or periodic replanning methods in Overcooked environments.
Entities (6)
Relation Signals (5)
BayesBeliefAgent → evaluatedin → Overcooked
confidence 95% · Across benchmark Overcooked environments, contradiction-conditioned control drastically narrows this belief-action gap
BayesBeliefAgent → uses → Bayesian Tracking Module
confidence 95% · BayesBeliefAgent, which pairs a hierarchical LLM planner with a Bayesian tracking module.
BayesBeliefAgent → reduces → Belief-Action Gap
confidence 92% · BayesBeliefAgent reduces the gap between what the agent believes and how it acts.
BayesBeliefAgent → outperforms → heuristic methods
confidence 90% · requiring an order of magnitude fewer replans than heuristic methods
BayesBeliefAgent → evaluatedin → Burrito
confidence 85% · We evaluate BayesBeliefAgent in Overcooked and Burrito
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-agent Large Language Model (LLM) systems often struggle to collaborate with new teammates whose strategies shift mid-task. Because agents execute multi-step or temporally extended skills, they frequently continue executing outdated plans long after public evidence shows that a partner has changed its skill. Existing methods either treat partner tracking as passive context-leaving the agent aware of the shift but slow to act-or replan indiscriminately. We introduce BayesBeliefAgent, which pairs a hierarchical LLM planner with a Bayesian tracking module. Rather than replanning constantly, our agent interrupts its current skill only when a partner's actions directly contradict the inferred skill. Beyond standard reward, we evaluate performance using replanning efficiency and the belief-action gap: the fraction of total decisions where an agent with a correct partner estimate executes a non-complementary skill. Across benchmark Overcooked environments, contradiction-conditioned control drastically narrows this belief-action gap while requiring an order of magnitude fewer replans than heuristic methods
Tags
Links
- Source: https://arxiv.org/abs/2608.18490v1
- Canonical: https://arxiv.org/abs/2608.18490v1
Trouble viewing inline? Open PDF directly →
Full Text
83,038 characters extracted from source content.
Expand or collapse full text
Bayesian Partner Modelling enables Adaptive Replanning for LLM Coordination Harsh Goel Aditya Sai Ellendula Vaishnav Tadiparthi Ehsan Moradi Pari Hossein Nourkhiz Mahjoub Sandeep P. Chinchali Abstract Multi-agent Large Language Model (LLM) systems often struggle to collaborate with new teammates whose strategies shift mid-task. Because agents execute multi-step or temporally extended skills, they frequently continue executing outdated plans long after public evidence shows that a partner has changed its skill. Existing methods either treat partner tracking as passive context—leaving the agent aware of the shift but slow to act—or replan indiscriminately. We introduce BayesBeliefAgent, which pairs a hierarchical LLM planner with a Bayesian tracking module. Rather than replanning constantly, our agent interrupts its current skill only when a partner’s actions directly contradict the inferred skill. Beyond standard reward, we evaluate performance using replanning efficiency and the belief–action gap: the fraction of total decisions where an agent with a correct partner estimate executes a non-complementary skill. Across benchmark Overcooked environments, contradiction-conditioned control drastically narrows this belief–action gap while requiring an order of magnitude fewer replans than heuristic methods. 1 Introduction Imagine a student who realizes that their professor has changed the direction of a joint project, yet continues carrying out an analysis that is no longer useful instead of stopping and replanning new experiments. Large language model (LLM) agents face an analogous challenge when collaborating in sequential decision-making tasks: they must coordinate with teammates, whose behavior may change during execution (41; 1). In such settings, coordination failures do not always arise because an agent misunderstands its partner’s intent: a capability commonly associated with Theory of Mind (24; 4; 29; 8). Rather, they arise because the agent fails to replan at the right time. Figure 1: Belief alone is not enough. An LLM agent may correctly model its teammate yet still act redundantly if it does not revise its plan when partner behavior changes. BayesBeliefAgent addresses this by maintaining a Bayesian posterior over latent teammate coordination skills, detecting visible contradictions, and triggering replanning when the current plan becomes stale. This turns teammate belief into coordinated, complementary action. LLM agents in collaborative settings often continue executing an obsolete plan even after public evidence indicates that a teammate’s strategy has shifted. Recent LLM-based coordination methods address this problem by incorporating inferred partner roles into the planning context at inference time (41; 32; 33). However, accurate partner inference does not necessarily translate into effective coordination. As observed by 26, LLM agents can exhibit a literal–functional Theory of Mind gap: they may correctly infer a partner’s role or goal yet fail to adapt their own behavior accordingly. In sequential tasks, this failure can arise when an agent updates its belief about a teammate’s new role but continues executing a skill selected under its previous belief. Its partner model has changed, but its control policy remains committed to an obsolete course of action. This exposes a belief-to-control gap: understanding what a partner is doing does not by itself provide a principled mechanism for deciding whether and when to interrupt ongoing execution. The central challenge is therefore not only to infer a teammate’s intent, but also to determine when new evidence is sufficiently consequential to trigger replanning. Effective coordination thus requires selective replanning: interrupting an ongoing skill when public observations contradict the assumptions under which it was selected, while avoiding the excessive churn caused by reacting to every behavioral change. Our experiments further show that generic interruption rules are insufficient to make this decision reliably. We address this gap with BayesBeliefAgent, which tracks the skill the partner is likely executing and uses that estimate to decide when to replan. For each possible partner skill, the agent predicts the low-level actions the partner would take and compares those predictions with the observed public behavior. This comparison updates its estimate of the partner’s skill. When the partner takes actions that conflict with the current estimate, the agent interrupts its ongoing skill and replans. We evaluate BayesBeliefAgent in Overcooked and Burrito with previously unseen partners exhibiting diverse behavioral preferences (36). Because episodic reward is noisy and can obscure coordination failures, we additionally report four process-level metrics: the belief-action gap rate, defined as the fraction of decision points at which the agent has a correct teammate-skill estimate but nevertheless selects or continues a non-complementary skill; contradiction-conditioned recovery, which measures how quickly the agent selects a complementary skill after contradictory evidence; the duplicate-skill rate, which measures how often both agents pursue the same skill; and replan efficiency, which captures the amount of replanning required to coordinate effectively. We compare against baselines that replan (i) periodically, (i) after specific public events, or (i) whenever an LLM judge recommends it, as well as a hypothesis-based partner-modeling method (7). Across Open and Ring layouts, BayesBeliefAgent reduces the gap between what the agent believes and how it acts. Simple triggers can achieve similar reward, but only by replanning more than 100 times per episode: roughly two orders of magnitude more often than BayesBeliefAgent. Our key contributions are as follows: • Method. We introduce BayesBeliefAgent, a hierarchical LLM coordination agent that uses likelihood-based contradictions under the current teammate-skill estimate to selectively interrupt and replan. • Diagnostics. We propose a diagnostic evaluation protocol that measures the belief–action gap, contradiction-conditioned recovery, and replanning efficiency, revealing coordination failures that aggregate reward obscures. • Evidence. Across Open and Ring layouts, we show that posterior-gated interruption turns partner beliefs from passive planning context into an active control signal. It reduces the belief–action gap and improves recovery after teammate strategy shifts while requiring substantially fewer replans than periodic, event-triggered, and LLM-judge baselines. We also identify the settings in which selective replanning provides limited benefit. 2 Related Work Ad hoc teamwork and zero-shot coordination. Multi-agent Reinforcement Learning (MARL) methods for coordination have traditionally emphasized learning specialized roles (21; 16; 35; 10). The problem of coordinating with unseen partners without prior joint training is the classical ad hoc teamwork setting (30), and Overcooked-AI (6) has become its standard testbed for human-AI coordination. Prior work improves performance through training-time partner diversity: arbitrary conventions (12), population-based play (31; 43), and open-ended partner generation (18; 34). These methods require environment-specific training (9; 27). Our work is complementary and inference-time: given a fixed LLM agent and an unseen partner, we ask when an updated partner belief should interrupt the agent’s plan. LLM agents for multi-agent coordination. LLM agents have increasingly been used in cooperative tasks because they can interpret shared goals, reason about teammate behavior, and generate high-level plans. Related works (41; 20; 7) uses teammate-intent reasoning and hierarchical planning to support proactive cooperation in Overcooked. Recent methods incorporate partner models into decision-making, either as retrieved context (33) or as constraints on actions (23). However, broader evaluations across cooperative environments show that strong task understanding does not necessarily translate into robust coordination (1; 22). In particular, recent studies find that LLM agents often struggle to sustain collaboration and adapt as teammate behavior changes (32; 26). In contrast, our work studies how updated partner beliefs should control when an agent interrupts an ongoing skill and replans. Theory of mind and partner belief modeling. Modeling a partner’s latent state has a long lineage in Bayesian inverse planning (2) and Bayesian theory of mind (3) with learned variants that predict agents from behavior (25) and Bayesian delegation (37). Explicit belief representation in LLMs helps but is bounded by long-horizon context and hallucinated state (17), and hypothesis-based agents generate and refine natural-language conjectures about partner strategy (7). Unlike belief estimators based on LLMs, we introduce a lightweight, non-LLM Bayesian method that infers which skill a teammate is currently executing from their publicly observable actions, to selectively interrupt the ego agent’s ongoing skill. The belief-action gap in LLM agents. Our framing builds on the distinction between literal Theory of Mind (predicting a partner) and functional Theory of Mind (adapting behavior accordingly) (26). Because LLM agents can fail to translate updated beliefs into action (39; 38), we define the belief-action gap: maintaining an accurate belief about a teammate’s role while continuing to execute an outdated skill. We introduce process-level metrics to measure this gap and evaluate whether belief-conditioned selective replanning reduces it. Replanning and plan invalidation in hierarchical agents. LLM agents replan from task failure, self-reflection, or environment feedback (40; 28) while more recent works trigger replanning for goal-state consistency or execution verification (14). In these methods, replanning is primarily driven by task-level execution signals such as failed actions. We study a complementary setting in multi-agent coordination, where an executing skill may become obsolete before any task-level failure occurs because newly observed teammate behavior contradicts the current partner model. BayesBeliefAgent therefore uses these contradictions as the trigger for selective replanning. 3 Problem Formulation Modeling. We model the problem as a hierarchical partially observable stochastic game in which agents act through temporally extended skills. The game is defined by the tuple ⟨,,,,,Ω,R,Ψ,low,,ρ0s,γ⟩ ,S,A,O,T, ,R, , π_low, β, _0^s,γ . Here, =0,…,n−1N=\0,…,n-1\ is the set of agents, S is the global state space, =0×⋯×n−1A=A_0×·s×A_n-1 is the joint primitive-action space, and =0×⋯×n−1O=O_0×·s×O_n-1 is the joint observation space. At time t, the environment is in state st∈s_t , and agent k receives observation otk∈ko_t^k _k sampled according to the observation model otk∼Ωk(⋅∣st).o_t^k ^k(· s_t). Each agent executes a primitive action atk∈ka_t^k _k, forming the joint action t=[at0,…,atn−1]a_t=[a_t^0,…,a_t^n-1]. The transition model T determines the next state from st+1∼(⋅∣st,t)s_t+1 (· s_t,a_t), and the team receives the shared reward R(st,t)R(s_t,a_t). The finite skill library is denoted by Ψ , the collection of low-level action controllers by low π_low, and the skill termination conditions by β, as defined in the next paragraph. Finally, the initial state is sampled from ρ0s _0^s, and γ∈[0,1]γ∈[0,1] is the discount factor. The ego agent is denoted by i and an unseen teammate by j≠ij≠ i. Temporally Extended Skills. The skill library Ψ , where each ψ∈Ψψ∈ represents a temporally extended task-level behavior. The teammate selects its skill ψtj∼πhighj(⋅∣τtj) _t^j π^j_high (· _t^j ) using an unknown high-level policy πhighjπ^j_high conditioned on its interaction history τtj=(o0j,a0j,…,ot−1j,at−1j,otj) _t^j= (o_0^j,a_0^j,…,o_t-1^j,a_t-1^j,o_t^j ). Conditioned on its current skill ψtj _t^j, the teammate executes a low level primitive action atj∼πlowj(⋅∣otj,ψtj).a_t^j π^j_low (· o_t^j, _t^j ). While the ego agent observes the teammates’ low-level actions at−1ja_t-1^j as part of its own observations otio_t^i, it does not know πhighjπ^j_high, or ψtj _t^j. Therefore, the ego agent selects its skill ψti∼πhighi(⋅∣τti,bt(ψtj)) _t^i π^i_high (· _t^i,b_t( _t^j) ) using its high-level policy πhighiπ^i_high, conditioned on its trajectory τti=(o0i,a0i,…,ot−1i,at−1i,oti)τ^i_t= (o_0^i,a_0^i,…,o_t-1^i,a_t-1^i,o_t^i ) and belief btb_t (defined in the next section) over the teammate’s active skill. Conditioned on this skill, the ego agent’s primitive action is ati∼πlowi(⋅∣oti,ψti)a_t^i π^i_low (· o_t^i, _t^i ). Finally, each agent also has a termination rule βkβ^k, which determines when its current skill ends. The collection of termination rules is denoted by β. The termination function βk:k×Ψ→[0,1]β^k:O_k× →[0,1] gives the probability that the skill terminates after time step t: βk(ot+1k,ψtk)∈[0,1]β^k (o_t+1^k, _t^k )∈[0,1]. Online Partner-Skill Belief. Because the teammate’s active skill ψtj _t^j is not directly observable, the ego agent maintains a belief bt∈Δ(Ψ)b_t∈ ( ), where Δ(Ψ) ( ) denotes the probability simplex over the skill library. For each ψ∈Ψψ∈ , the belief is defined as bt(ψ)=Pr(ψtj=ψ∣τti).b_t(ψ)\,=\, \! ( _t^j=ψ _t^i ). (1) Since otio_t^i includes the teammate’s publicly observable primitive actions, btb_t summarizes which teammate skill best explains the evidence up to time t. The belief provides a probabilistic estimate of the teammate’s current task-level behavior, which the ego agent uses to choose a complementary skill and decide whether to interrupt and replan its own skill. Objective. The ego policy consists of a fixed hierarchical LLM planner, skill-conditioned low-level controllers, and an online partner-skill estimator. Therefore, the evaluation objective of the ego-agent’s policy with the estimated partner’s skill is to maximize the total expected return: J(πhighi) J(π^i_high) =s0∼ρ0s,t∼Ω(⋅∣st),ψt∼πhigh,t∼πlow,st+1∼(⋅∣st,t)[∑t=0TγtR(st,t)]. =E_ subarraycs_0 _0^s,\;o_t (· s_t),\; _t _high,\\ a_t _low,\;s_t+1 (· s_t,a_t) subarray\! [ _t=0^Tγ^tR(s_t,a_t) ]. (2) Figure 2: BayesBeliefAgent overview. From the teammate’s publicly observed primitive actions and the ego agent’s observation history, the agent maintains a posterior over the teammate’s active skill. Each newly observed teammate action is first evaluated under the previous MAP teammate-skill estimate. The posterior is then updated using the new observation. If the action is contradictory and the previous estimate is stable and sufficiently confident while the ego agent is mid-skill and out of cooldown, the current skill is interrupted and the LLM planner is queried using the updated posterior and MAP estimate. Otherwise, the agent continues executing its current skill. 4 Method We present BayesBeliefAgent, a hierarchical ego agent that coordinates with an unseen teammate by maintaining an online posterior over the teammate’s active skill. The ego agent observes the teammate’s primitive actions and their effects on the public environment, but does not directly observe the skill being executed. We first estimate the teammate’s active skill through a recursive Bayesian update. As described in Section 4.1, the estimator tracks whether the teammate’s skill may persist or change and then incorporates newly observed public evidence to obtain a posterior belief over the skill library. Once this posterior estimate is obtained, the ego agent uses it as coordination context for its high-level LLM planner. While an ego skill is already being executed, the agent may interrupt that skill and invoke the planner again when newly observed evidence is inconsistent with the current partner-skill estimate, as described in Section 4.2. 4.1 Bayesian Partner-Skill Belief Update The ego agent maintains a recursive belief bt(ψ)b_t(ψ) over the teammate’s active skill ψtj∈Ψ _t^j∈ , as introduced in Section 3. Because the teammate’s skill is not directly observable, the belief is updated from public evidence contained in the ego agent’s observation history. We estimate the teammate’s active skill through Bayesian inverse planning (13). The ego agent treats the teammate’s skill ψtj∈Ψ _t^j∈ as a latent variable and infers it from the primitive actions observed through its own interaction history. Let τti=(o0i,a0i,…,ot−1i,at−1i,oti) _t^i= (o_0^i,a_0^i,…,o_t-1^i,a_t-1^i,o_t^i ) denote the ego agent’s observation–action history. Because the teammate’s publicly visible primitive action at−1ja_t-1^j is contained in the ego observation otio_t^i, this history provides the behavioral evidence used to infer the teammate’s current skill. For a candidate teammate skill ψ∈Ψψ∈ , the desired posterior is given in Eq. 1. Applying Bayes’ rule over a recent inference window from timestep t′<t <t, where the partner agent either completes its last skill or is a fixed window of k timesteps P(ψtj=ψ∣τti)= P ( _t^j=ψ _t^i )= P(τt′+1:ti∣ψtj=ψ,τt′i)P(ψtj=ψ∣τt′i)∑ψ′∈ΨP(τt′+1:ti∣ψtj=ψ′,τt′i)P(ψtj=ψ′∣τt′i) P ( _t +1:t^i _t^j=ψ, _t ^i )\,P ( _t^j=ψ _t ^i ) _ψ ∈ P ( _t +1:t^i _t^j=ψ , _t ^i )\,P ( _t^j=ψ _t ^i ) ∝ P(τt′+1:ti∣ψtj=ψ,τt′i)bt′(ψ), P ( _t +1:t^i _t^j=ψ, _t ^i )\,b_t (ψ), (3) where τt′+1:ti _t +1:t^i denotes the new trajectory segment observed after the prior history τt′i _t ^i, and bt′(ψ)≜P(ψtj=ψ∣τt′i)b_t (ψ) P ( _t^j=ψ _t ^i ) is the prior belief over the teammate’s active skill. In practice, we assume that the teammate’s skill remains fixed within the inference window that is capped to k steps. Initializing the Prior. Therefore, the prior bt′b_t is initialized from the observed history of completed partner skills. We use an add-α smoothed count model: bt′(ψ)=Cm(ψ∣τt′i)+α∑ψ′∈Ψ(Cm(ψ′∣τt′i)+α).b_t (ψ)\,=\, C_m (ψ _t ^i )+α _ψ ∈ (C_m (ψ _t ^i )+α ). (4) where α>0α>0 is a smoothing hyperparameter. We use α=1α=1, corresponding to a uniform Dirichlet-style initialization. This smoothing assigns nonzero prior probability before the start of the current episode. We update the episode-level counts after each inferred completed partner skill ψ^mj ψ_m^j at any completion timestep m via Cm(ψ)=Cm−1(ψ)+[ψ^mj=ψ].C_m(ψ)\,=\,C_m-1(ψ)+ 1\! [ ψ_m^j=ψ ]. (5) The resulting prior provides a lightweight episode-level memory of the teammate’s previously inferred behavior. Skills repeatedly supported in earlier segments receive greater prior probability, while the likelihood term in Eq. (4.1) can still rapidly shift the posterior when the teammate’s newly observed actions are more consistent with a different skill. Simplifying the Belief Update. The trajectory likelihood P(τt′+1:ti∣ψtj=ψ,τt′i)P ( _t +1:t^i _t^j=ψ, _t ^i ) in Eq. (4.1) contains both the teammate’s primitive actions from its action policy πlowjπ^j_low and the resulting observations and can be factorized as ∏l=t′+1tπlowj(alj∣olj,ψ)P(ali∣τli)P(ol+1i∣τli,ali,alj). _l=t +1^tπ^j_low (a_l^j o_l^j,ψ )P (a_l^i _l^i )P (o_l+1^i _l^i,a_l^i,a_l^j ).\ Therefore, the partner-skill belief update in Eq.4.1 can be written as bt(ψ)=ηbt′(ψ)∏l=t′+1tπlowj(alj∣olj,ψ),b_t(ψ)=η b_t (ψ) _l=t +1^tπ^j_low (a_l^j o_l^j,ψ ), (6) where the normalization constant is η−1=∑ψ′∈Ψbt′(ψ′)∏l=t′+1tπlowj(alj∣olj,ψ′).η^-1= _ψ ∈ b_t (ψ ) _l=t +1^tπ^j_low (a_l^j o_l^j,ψ ). (7) In practice, the true teammate observation oljo_l^j and low-level controller πlowjπ^j_low are not available to the ego agent. We therefore approximate the action likelihood using the ego agent’s own observations of its partner from its own history τli _l^i and its low-level action controller πlowiπ^i_low as πlowj(alj∣olj,ψ)≈πlowi(alj∣τli,ψ).π^j_low (a_l^j o_l^j,ψ )≈π^i_low (a_l^j _l^i,ψ ). (8) 4.2 Belief-Guided Skill Interruption The posterior belief over the teammate’s skill is used both as context for the high-level planner and to decide when the ego agent should interrupt its current skill. First, the ego agent obtains a point estimate of the teammate’s active skill ψ^t−1j ψ_t-1^j from the previous belief: ψ^t−1j=argmaxψ∈Ψbt−1(ψ). ψ_t-1^j\;=\; _ψ∈ \,b_t-1(ψ). (9) Then, the ego agent evaluates the likelihood of teammate actions under this estimated skill. Because the teammate’s true low-level controller and observation are unavailable, we use the same approximate action model introduced in Eq. (8): ℓt=∏l=t′+1t−1πlowi(alj∣τtl,ψ^t−1j). _t= _l=t +1^t-1π^i_low (a_l^j _t^l, ψ_t-1^j ). (10) Finally, this likelihood measures how well the current partner-skill estimate explains the teammate’s newly observed behavior to determine whether to interrupt the ego agent’s ongoing skill. A low value indicates that the teammate’s action is inconsistent with the behavior expected under ψ^t−1j ψ_t-1^j. We define the resulting contradiction signal as Ct=[ℓt<θobs],C_t= 1 [ _t< _obs ], (11) where θobs _obs is a likelihood threshold. The contradiction test is evaluated before the new action is incorporated into the posterior in Eq. 6. This ordering is important because, after the belief update, the posterior may shift toward a different skill that better explains atja_t^j. Evaluating the likelihood before this update allows the ego agent to detect when its previous partner-skill estimate has been contradicted by new evidence. Gated Skill Interruption. A single unlikely action may result from noise or temporary motion rather than a meaningful change in the teammate’s skill. We therefore combine the contradiction signal with additional conditions before interrupting the ego agent’s current skill: Replant=[ _t= 1 [ Ct=1∧stable(ψ^t−1j) C_t=1\; \;stable ( ψ_t-1^j ) (12) ∧bt−1(ψ^t−1j)≥Γconf \;b_t-1 ( ψ_t-1^j )≥ _conf ∧midSkillt∧cooldownt=0]. \;midSkill_t\; \;cooldown_t=0 ]. Here, stable(ψ^t−1j)stable ( ψ_t-1^j ) requires the MAP skill estimate to have remained unchanged over a fixed number of recent belief updates. This prevents the agent from interrupting its skill while the partner estimate is still changing. The confidence threshold Γconf _conf requires the current estimate to have sufficient posterior probability. The condition midSkilltmidSkill_t ensures that interruption is only considered while the ego agent is executing a skill, and cooldowntcooldown_t prevents repeated replanning over a short period. We present the sensitivity of the planner to these gates and outline hyperparameters in the Appendix. To summarize, the ego agent replans only when a newly observed teammate action is unlikely under a stable, confident partner-skill estimate. Therefore, the mechanism does not need the complementary ego skill; it detects when the teammate’s behavior is inconsistent with the stable, committed skill estimate held before the new observation, and uses that contradiction to trigger replanning. 4.3 Replanning When Eq. (12) is satisfied, the ego agent interrupts its current skill and invokes the high-level LLM planner. The planner receives the current observation history, the updated posterior belief btb_t, the resulting MAP teammate-skill estimate ψ^tj=argmaxψ∈Ψbt(ψ), ψ_t^j= _ψ∈ b_t(ψ), (13) and the set of currently feasible ego skills. The planner πhighiπ^i_high, which is an LLM selects a new ego skill. Consequently, the partner-skill belief affects planning in two ways. First, the posterior and its MAP estimate are provided to the LLM planner as coordination context. Second, the likelihood of newly observed behavior under the current skill estimate determines whether the planner should be invoked while an ego skill is already in progress. This allows the agent to continue executing its current skill when the teammate behaves as expected, while still responding when new evidence contradicts the current partner-skill estimate. We provide the complete algorithm in the Appendix. 5 Experiments Our experiments answer the following research questions: RQ1. Coordination Performance. How does BayesBeliefAgent perform when paired with diverse, preference-specialized partners (Sec. 5.2)? RQ2. Literal–Functional ToM Gap. Does solely maintaining an accurate belief about a teammate’s skill suffice to prevent coordination failures (Sec. 5.3)? RQ3. Posterior-Guided Control Ablation. Does only using the teammate posterior as a control signal to interrupt an executing skill close the belief-action gap more effectively than using the same posterior only as context in the planner prompt (Sec. 5.4)? RQ4. Selective Replanning. Is contradiction-based interruption more efficient at improving coordination than generic replanning heuristics (Sec. 5.5)? 5.1 Setup Environments and partners. We evaluate in the Overcooked/Burrito domain across three layouts (Open, Ring, and Forced Coordination (FC)), and three partner groups, yielding nine settings. The evaluation population contains 12 Behavior Preference (BP) agents (36) that favor distinct task subgoals through reward shaping. We divide them into three groups of four: Logistics/G1 (Plating and Washing), Cooking/G2 (Chopping and Potting), and Sourcing/G3 (Mushroom and Rice dispensing). Within each group, the four agents correspond to the 222^2 combinations of their two preferences. Rewards for Delivering Dishes (+20)(+20), Grilling Meat (+20)(+20), and Taking Meat (+10)(+10) are fixed across all partners to maintain task competence while preserving behavioral diversity. Each reported layout-group result aggregates five seeds across four partners. Full partner-generation details are provided in the Appendix. Baselines and conditions. We compare BayesBeliefAgent against ProAgent (41), a hierarchical LLM planner without online belief revision; Hypothetical Minds (7), a hypothesis-based partner-modeling method; GAMMA (19), an RL-based ad hoc teaming agent; and TALENTS (15), a zero-shot coordination baseline. All LLM-based conditions use either GPT-4o or GPT-5.2. Table 1: Coordination performance (mean reward ± std. dev.) across all three BP partner groups. FC = Forced Coordination. Best LLM-based result per cell in bold; best overall underlined. BayesBeliefAgent outperforms all LLM-based agents. Group 1 (Logistics) Group 2 (Cooking) Group 3 (Sourcing) Agent FC Ring Open FC Ring Open FC Ring Open BP 95 (116) 927 (406) 1625 (457) 84 (159) 622 (246) 484 (179) 76 (130) 793 (228) 792 (334) GAMMA 46 (79) 1124 (225) 1189 (415) 64 (111) 649 (159) 360 (114) 54 (77) 864 (216) 692 (167) TALENTS 53 (91) 1019 (307) 1212 (193) 34 (60) 935 (298) 398 (158) 38 (49) 1237 (308) 1101 (321) Hypothetical-Minds 11 (19) 388 (361) 608 (274) 0 (0) 188 (64) 369 (164) 0 0 275 (124) 480 (239) ProAgent 0 (0) 313 (252) 732 (310) 0 (0) 161 (143) 388 (253) 9 (15) 271 (234) 549 (327) ProAgent (GPT-5.2) 0 (0) 200 (182) 629 (252) 0 (0) 172 (80) 392 (140) 9 (16) 337 (239) 569 (257) Ours (GPT-4o) 14 (21) 663 (468) 1533 (410) 9 (16) 231 (232) 337 (270) 18 (25) 506 (161) 1420 (390) Ours (GPT-5.2) 0 (0) 705 (302) 1485 (340) 9 (16) 285 (114) 395 (234) 45 (40) 470 (173) 1360 (306) Metrics. We report episodic team rewards as measures of task performance. To evaluate literal Theory of Mind, we additionally report teammate-skill prediction accuracy. To evaluate functional Theory of Mind, we report the complementary-skill rate within three steps of a detected contradiction (Comp@3), and the duplicate-skill rate. The ground truth complementary skill for coordination scenarios is determined by humans (See Appendix). Our primary diagnostic metric is the belief-action gap rate. At each high-level decision point, we first determine whether the agent’s committed estimate of the teammate’s skill is correct, or satisfies a specified confidence criterion. Among these points, the belief-action gap rate measures the fraction for which the ego agent nevertheless selects or continues a stale, duplicate, or non-complementary macro-action. Thus, this metric assesses whether that belief is translated into appropriate control. A lower rate indicates a smaller divergence between literal and functional Theory of Mind. Additionally, we measure the replan rate per episode to quantify the computational cost of each interruption strategy. 5.2 RQ1: Benchmarking Coordination Table 1 reports coordination performance across the three partner clusters and three layouts. BayesBeliefAgent outperforms ProAgent and Hypothetical Minds in every layout. In the Open and Ring layouts, BayesBeliefAgent improves performance relative to ProAgent, with the largest gains against Group 1 and Group 3 partners. Qualitatively, these improvements arise because BayesBeliefAgent anticipates large partner skill switches (e.g., to plating or washing in Group 1, or mushroom dispensing in Group 3) and selects a complementary skill in response. However, the RL-based baselines, particularly TALENTS and GAMMA, remain stronger than the LLM-based methods in most environments. This gap suggests that, although online teammate-belief adaptation improves coordination via the hierarchical LLM agent, the underlying LLM-based high-level skill planner remains a major performance bottleneck and requires substantial improvement. Improving the underlying high-level LLM planner is an important direction that we leave to future work. 5.3 RQ2: Literal-Functional ToM Gap Table 2: Mechanism metrics averaged across partner groups G1–G3. Despite nearly identical teammate-skill prediction accuracy, BayesBeliefAgent reduces the belief–action gap and duplicate-skill rate and improves contradiction-conditioned recovery relative to ProAgent, with the largest gains in Open and Ring. Arrows indicate the improving direction. Metric Method Open Ring FC Skill acc. (↑ ) BayesBeliefAgent 0.79 0.71 0.61 ProAgent 0.78 0.71 0.60 Gap rate (↓ ) BayesBeliefAgent 0.20 0.28 0.42 ProAgent 0.41 0.38 0.47 Comp@3 (↑ ) BayesBeliefAgent 0.66 0.54 0.31 ProAgent 0.39 0.43 0.26 Dup. skill (↓ ) BayesBeliefAgent 0.15 0.23 0.37 ProAgent 0.30 0.30 0.41 Table 2 shows that BayesBeliefAgent (GPT-4o) and ProAgent achieve nearly identical predicted teammate-skill accuracy across all layouts, yet differ substantially in functional coordination. The posterior-gated interruption in BayesBeliefAgent reduces the belief-action gap from 0.410.41 to 0.200.20 in Open and from 0.380.38 to 0.280.28 in Ring, while also improving Comp@3 and reducing duplicate-skill behavior. The gains are smaller in Forced Coordination, where limitations of the underlying planner remain more pronounced. These results reveal a literal-functional Theory-of-Mind gap: accurately inferring the teammate’s skill is insufficient if the ego agent remains committed to a skill selected under an outdated belief. Thus, BayesBeliefAgent addresses a key coordination bottleneck not by further improving belief accuracy, but by translating updated teammate beliefs into timely control decisions to bridge the literal-functional ToM gap. 5.4 RQ3: Posterior-Guided Control Ablation We next examine whether the teammate’s skill posterior is more effective as planner context or as a control signal. We present four ablations in Table 3 that test posterior prompting and posterior-gated interruption: Full (equivalent to BayesBeliefAgent) uses both pathways, No replan uses only prompting, No prompt uses only posterior-guided interruption, and No belief uses neither. Thus, the comparison between No prompt and No replan contrasts control-only and context-only use of the same posterior, while Full and No replan isolate the additional effect of interruption when posterior context is held fixed. Table 3: We report the mean reward ± standard deviation across posterior-guided control ablations. Posterior-gated interruption generally outperforms posterior prompting alone, indicating its effectiveness as a control signal. Setting Full No prompt No replan No belief Open G1 1533±4101533±410 1405±4301405±430 1190±4551190±455 1080±4701080±470 Open G2 337±270337±270 305±250305±250 263±152263±152 274±290274±290 Open G3 1420±3901420±390 1325±4201325±420 1110±4401110±440 1015±4651015±465 Ring G1 663±468663±468 610±430610±430 566±348566±348 212±206212±206 Ring G2 231±232231±232 225±215225±215 264±218264±218 215±227215±227 Ring G3 506±161506±161 475±185475±185 439±177439±177 607±582607±582 FC G1 14±2114±21 13±1913±19 11±1811±18 9±179±17 FC G2 9±169±16 8±158±15 8±148±14 7±137±13 FC G3 18±2518±25 17±2417±24 15±2215±22 13±2113±21 Table 3 shows that No prompt generally outperforms No replan. This indicates that the critical contribution of the posterior is not merely to inform the planner, but to trigger replanning when the current skill becomes inconsistent with updated teammate behavior. Even without posterior context in the prompt, posterior-gated interruption enables better coordination than providing the same posterior only as planner context. The comparison between Full and No replan further supports this conclusion. Moreover, the added interruption while holding posterior prompting fixed reduces the belief–action gap in five of seven settings (see Appendix). Overall, RQ3 shows that directly coupling teammate beliefs to replanning is more effective than relying on the planner to translate those beliefs into control decisions. 5.5 RQ4: Selective Replanning A natural alternative explanation is that coordination improves simply because the agent replans more often, rather than because behavioral surprise identifies informative decision points for interruption. We compare contradiction-based interruption against three generic replanning heuristics. Periodic-10 interrupts and replans every ten environment steps. Completion/held-item triggers replanning whenever the partner completes a skill or is observed holding a task-relevant item. LLM-judge uses a separate LLM-based decision module that observes the partner’s public behavior and determines whether the ego agent should replan. Table 4 shows that the generic triggers can attain rewards comparable to Full, but only by replanning far more frequently. On Open G1, Periodic-10, Completion/held-item, and LLM-judge invoke 4343, 169169, and 119119 replans per episode, respectively, compared with only 2.02.0 for BayesBeliefAgent, while achieving similar rewards (14901490, 15101510, and 14801480 versus 15331533). This pattern holds broadly across settings: the generic heuristics typically trigger tens to more than one hundred replans per episode, whereas contradiction-based interruption operates with low single-digit replan counts in most cases. Although some generic triggers achieve higher numerical reward in individual settings, none does so consistently across environments, and these gains come at substantially greater replanning cost. These results indicate that the benefit of contradiction-based interruption is not simply more frequent replanning, but greater selectivity in identifying when an executing skill should be revised. Table 4: We report the mean reward / replans per episode to compare replanning triggers. All LLM-planner conditions receive identical public observations and belief prompt; they differ only in the interruption signal. BayesBeliefAgent (Full) attains comparable reward with far fewer replans than the heuristic or LLM-based triggers. Setting Full Periodic-10 Compl./held LLM-judge Open G1 1533 / 2.0 1490 / 43.0 1510 / 169.0 1480 / 119.0 Open G2 337 / 1.8 515 / 15.0 304 / 50.4 403 / 34.0 Open G3 1420 / 3.0 1395 / 51.0 1370 / 115.0 1400 / 98.0 Ring G1 663 / 1.6 695 / 66.9 629 / 107.1 721 / 97.1 Ring G2 231 / 7.5 218 / 76.3 202 / 87.5 201 / 110.6 Ring G3 506 / 9.3 416 / 52.8 455 / 110.9 558 / 103.3 FC G1 14 / 0.5 12 / 78.0 16 / 8.0 11 / 92.0 FC G2 9 / 0.3 8 / 81.0 10 / 6.0 7 / 96.0 FC G3 18 / 0.6 15 / 76.0 19 / 10.0 14 / 89.0 6 Future Work and Conclusion Limitations. A key limitation is that BayesBeliefAgent reasons over a fixed set of coarse, manually specified skills. A natural next step is to learn this skill space and represent finer-grained structure, including subgoal dependencies and open-ended skill discovery. Posterior-gated interruption is also less effective in tightly coupled environments such as Forced Coordination. Improvements in these settings will likely require stronger LLM-based planners, as well as methods that jointly adapt belief estimation and action selection. Additionally, evaluations across a larger number of partners and human partners whose strategies change within an episode remain an important direction for future work. Conclusion. In this work, we introduce BayesBeliefAgent, a hierarchical LLM agent that maintains an online Bayesian belief over a teammate’s skills and uses unexpected observations to decide when an ongoing skill should be interrupted and revised. This design directly addresses the belief–action gap: an agent may correctly infer what its teammate is doing while continuing to execute a stale or duplicative skill. By connecting partner belief to selective replanning, BayesBeliefAgent reduces duplicate-role behavior, improves recovery after contradictory observations, and achieves rewards comparable to generic replanning with substantially fewer replans. Ablations further show that the posterior is most useful as a control signal rather than merely as additional planner context. These findings suggest that collaborative theory of mind should be leveraged for timely changes in behavior. References Agashe et al. (2025) S. Agashe, Y. Fan, A. Reyna, and X. E. Wang LLM-coordination: evaluating and analyzing multi-agent coordination abilities in large language models. External Links: 2310.03903, Link Cited by: §1, §2. Baker et al. (2009) C. L. Baker, R. Saxe, and J. B. Tenenbaum Action understanding as inverse planning. Cognition 113 (3), p. 329–349. Cited by: §2. Baker et al. (2017) C. L. Baker, J. Jara-Ettinger, R. Saxe, and J. B. Tenenbaum Rational quantitative attribution of beliefs, desires and percepts in human mentalizing. Nature Human Behaviour 1. External Links: Link Cited by: §2. Byom and Mutlu (2013) L. Byom and B. Mutlu Theory of mind: mechanisms, methods, and new directions. Frontiers in Human Neuroscience 7, p. 413. External Links: Document Cited by: §1. Carroll et al. (2019) M. Carroll, R. Shah, M. K. Ho, T. Griffiths, S. Seshia, P. Abbeel, and A. Dragan On the utility of learning about humans for human-AI coordination. In Advances in Neural Information Processing Systems, Vol. 32. Cited by: §9.1. Carroll et al. (2020) M. Carroll, R. Shah, M. K. Ho, T. L. Griffiths, S. A. Seshia, P. Abbeel, and A. Dragan On the utility of learning about humans for human-ai coordination. External Links: 1910.05789, Link Cited by: §2. Cross et al. (2024) L. Cross, V. Xiang, A. Bhatia, D. L. Yamins, and N. Haber Hypothetical minds: scaffolding theory of mind for multi-agent tasks with large language models. External Links: 2407.07086, Link Cited by: §1, §2, §2, §5.1. Gao et al. (2024) Q. Gao, Y. Li, H. Lyu, H. Sun, D. Luo, and H. Deng Vision language models see what you want but not what you see. arXiv preprint arXiv:2410.00324. Cited by: §1. Gessler et al. (2025) T. Gessler, T. Dizdarevic, A. Calinescu, B. Ellis, A. Lupu, and J. N. Foerster OvercookedV2: rethinking overcooked for zero-shot coordination. External Links: 2503.17821, Link Cited by: §2. Goel et al. (2025) H. Goel, M. Omama, B. Chalaki, V. Tadiparthi, E. M. Pari, and S. Chinchali R3DM: enabling role discovery and diversity through dynamics models in multi-agent reinforcement learning. arXiv preprint arXiv:2505.24265. Cited by: §2. Goel et al. (2023) H. Goel, Y. Zhang, M. Damani, and G. Sartoretti SocialLight: distributed cooperation learning towards network-wide traffic signal control. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’23, Richland, SC, p. 1551–1559. External Links: ISBN 9781450394321 Cited by: §11.6. Hu et al. (2021) H. Hu, A. Lerer, A. Peysakhovich, and J. Foerster "Other-play" for zero-shot coordination. External Links: 2003.02979, Link Cited by: §2. Jin et al. (2024) C. Jin, Y. Wu, J. Cao, J. Xuan, Z. Hu, T. D. Ullman, J. B. Tenenbaum, and T. Shu MMToM-QA: multimodal theory of mind question answering. arXiv preprint arXiv:2401.08743. Cited by: §4.1. Kim et al. (2025) J. Kim, S. Rhee, M. Kim, D. Kim, S. Lee, Y. Sung, and K. Jung ReflAct: world-grounded decision making in llm agents via goal-state reflection. External Links: 2505.15182, Link Cited by: §2. Li et al. (2025) B. Li, S. Shi, L. Romero, H. Li, Y. Xie, W. Kim, S. Nikolaidis, M. Lewis, K. Sycara, and S. Stepputtis Adaptively coordinating with novel partners via learned latent strategies. arXiv preprint arXiv:2511.12754. Cited by: §5.1. Li et al. (2021) C. Li, T. Wang, C. Wu, Q. Zhao, J. Yang, and C. Zhang Celebrating diversity in shared multi-agent reinforcement learning. Advances in Neural Information Processing Systems 34, p. 3991–4002. Cited by: §2. Li et al. (2023a) H. Li, Y. Chong, S. Stepputtis, J. Campbell, D. Hughes, C. Lewis, and K. Sycara Theory of mind for multi-agent collaboration via large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, p. 180–192. External Links: Link, Document Cited by: §2. Li et al. (2023b) Y. Li, S. Zhang, J. Sun, Y. Du, Y. Wen, X. Wang, and W. Pan Cooperative open-ended learning framework for zero-shot coordination. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 19837–19854. Cited by: §2. Liang et al. (2024) Y. Liang, D. Chen, A. Gupta, S. S. Du, and N. Jaques Learning to cooperate with humans using generative agents. External Links: 2411.13934, Link Cited by: §5.1. Liu et al. (2024) J. Liu, C. Yu, J. Gao, Y. Xie, Q. Liao, Y. Wu, and Y. Wang LLM-powered hierarchical language agent for real-time human-ai coordination. External Links: 2312.15224, Link Cited by: §2. Liu et al. (2023) S. Liu, Y. Zhou, J. Song, T. Zheng, K. Chen, T. Zhu, Z. Feng, and M. Song Contrastive identity-aware learning for multi-agent value decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 11595–11603. Cited by: §2. Mandi et al. (2023) Z. Mandi, S. Jain, and S. Song RoCo: dialectic multi-robot collaboration with large language models. External Links: 2307.04738, Link Cited by: §2. Nguyen et al. (2025) M. H. Nguyen, V. D. Do, D. Nguyen, T. Nguyen, and H. Le CausalPlan: empowering efficient llm multi-agent collaboration through causality-driven planning. External Links: 2508.13721, Link Cited by: §2. Premack and Woodruff (1978) D. Premack and G. Woodruff Does the chimpanzee have a theory of mind?. Behavioral and Brain Sciences 1 (4), p. 515–526. Cited by: §1. Rabinowitz et al. (2018) N. C. Rabinowitz, F. Perbet, H. F. Song, C. Zhang, S. M. A. Eslami, and M. Botvinick Machine theory of mind. External Links: 1802.07740, Link Cited by: §2. Riemer et al. (2025) M. Riemer, Z. Ashktorab, D. Bouneffouf, P. Das, M. Liu, J. D. Weisz, and M. Campbell Position: theory of mind benchmarks are broken for large language models. External Links: 2412.19726, Link Cited by: §1, §2, §2. Ruhdorfer et al. (2025) C. Ruhdorfer, M. Bortoletto, A. Penzkofer, and A. Bulling The overcooked generalisation challenge: evaluating cooperation with novel partners in unknown environments using unsupervised environment design. External Links: 2406.17949, Link Cited by: §2. Shinn et al. (2023) N. Shinn, F. Cassano, A. Gopinath, K. R. Narasimhan, and S. Yao Reflexion: language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: §2. Shu et al. (2021) T. Shu, A. Bhandwaldar, C. Gan, K. A. Smith, S. Liu, D. Gutfreund, E. Spelke, J. B. Tenenbaum, and T. D. Ullman AGENT: a benchmark for core psychological reasoning. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 9614–9625. Cited by: §1. Stone et al. (2010) P. Stone, G. A. Kaminka, S. Kraus, and J. S. Rosenschein Ad hoc autonomous agent teams: collaboration without pre-coordination. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, p. 1504–1509. Cited by: §2. Strouse et al. (2021) D.J. Strouse, K. R. McKee, M. Botvinick, E. Hughes, and R. Everett Collaborating with humans without human data. In Advances in Neural Information Processing Systems, Vol. 34, p. 14502–14515. Cited by: §2. Sun et al. (2025) H. Sun, S. Zhang, L. Niu, L. Ren, H. Xu, H. Fu, F. Zhao, C. Yuan, and X. Wang Collab-overcooked: benchmarking and evaluating large language models as collaborative agents. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, p. 4922–4951. External Links: Link, Document Cited by: §1, §2. Wallace et al. (2025) C. Wallace, U. Siddique, and Y. Cao ReCollab: retrieval-augmented llms for cooperative ad-hoc teammate modeling. External Links: 2512.22129, Link Cited by: §1, §2. Wang et al. (2025) C. Wang, A. Rahman, J. Cui, Y. Sung, and P. Stone ROTATE: regret-driven open-ended training for ad hoc teamwork. arXiv preprint arXiv:2505.23686. Cited by: §2. Wang et al. (2020) T. Wang, H. Dong, V. Lesser, and C. Zhang Roma: multi-agent reinforcement learning with emergent roles. arXiv preprint arXiv:2003.08039. Cited by: §2. Wang et al. (2024) X. Wang, S. Zhang, W. Zhang, W. Dong, J. Chen, Y. Wen, and W. Zhang Zsc-eval: an evaluation toolkit and benchmark for multi-agent zero-shot coordination. Advances in Neural Information Processing Systems 37, p. 47344–47377. Cited by: §1, §5.1, §8.1. Wu et al. (2021) S. A. Wu, R. E. Wang, J. A. Evans, J. B. Tenenbaum, D. C. Parkes, and M. Kleiman-Weiner Too many cooks: bayesian inference for coordinating multi-agent collaboration. Topics in Cognitive Science 13 (2), p. 414–432. External Links: Document Cited by: §2. Xiao et al. (2025) Y. Xiao, J. Wang, Q. Xu, C. Song, C. Xu, Y. Cheng, W. Li, and P. Liu Towards dynamic theory of mind: evaluating LLM adaptation to temporal evolution of human states. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), Vienna, Austria, p. 24036–24057. External Links: Link, Document, ISBN 979-8-89176-251-0 Cited by: §2. Xu et al. (2025) R. Xu, H. Lin, X. Han, J. Zheng, W. Zhou, L. Sun, and Y. Sun Large language models often say one thing and do another. External Links: 2503.07003, Link Cited by: §2. Yao et al. (2023) S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. R. Narasimhan, and Y. Cao ReAct: synergizing reasoning and acting in language models. In Proceedings of the Eleventh International Conference on Learning Representations, Cited by: §2. Zhang et al. (2024) C. Zhang, K. Yang, S. Hu, Z. Wang, G. Li, Y. Sun, C. Zhang, Z. Zhang, A. Liu, S. Zhu, X. Chang, J. Zhang, F. Yin, Y. Liang, and Y. Yang ProAgent: building proactive cooperative agents with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. Cited by: §1, §1, §2, §5.1. Zhang et al. (2025) Y. Zhang, H. Goel, P. Li, M. Damani, S. Chinchali, and G. Sartoretti Coordlight: learning decentralized coordination for network-wide traffic signal control. IEEE Transactions on Intelligent Transportation Systems 26 (6), p. 8034–8049. Cited by: §11.6. Zhao et al. (2023) R. Zhao, J. Song, Y. Yuan, H. Hu, Y. Gao, Y. Wu, Z. Sun, and Y. Wei Maximum entropy population-based training for zero-shot human-AI coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 6145–6153. Cited by: §2. Appendix 7 Full Algorithm Specification Algorithm 1 gives the complete per-step operation of BayesBeliefAgent. To keep the pseudocode compact, we introduce the following notation. Let Lt(ψ)≜πlowi(alj∣τli,ψ).L_t(ψ) π^i_low (a_l^j _l^i,ψ ). denote the implemented action likelihood corresponding to the approximate teammate controller in Eq. (8). The operator Prior(Nm) Prior(N_m) returns the smoothed count-based distribution in Eq. (4), where the algorithmic count array NmN_m corresponds to CmC_m in the method. We write the normalized one-step Bayesian correction as Correct(b,lt)(ψ)=lt(ψ)b(ψ)∑ψ′∈Ψlt(ψ′)b(ψ′), Correct(b,l_t)(ψ)= l_t(ψ)b(ψ) _ψ ∈ l_t(ψ )b(ψ ), where ltl_t is defined in Eq. (10). Applying this correction recursively within a partner-skill segment accumulates the likelihood product in Eqs. (6)–(7), using the approximation in Eq. (8). The operator Gate implements Eq. (12), with stable(ψ^t−1j)≡[u≥K]stable( ψ_t-1^j)≡[u≥ K] and midSkillt≡[μ≠null∧¬complete(μ)], _t≡[μ≠ null (μ)], and cooldownt=0cooldown_t=0 represented by c=0c=0. Finally, Plan constructs the planner prompt, queries the high-level LLM, and parses a skill from the currently feasible macro-skill set. Algorithm 1 BayesBeliefAgent: per-step belief update and selective replanning 1: partner-skill set Ψ , ego macro-skill set ℳM, planner πhighiπ^i_high, controller πlowiπ^i_low 2: smoothing α, thresholds θobs _obs and Γconf _conf, stability window K, inference window k, cooldown duration CcoolC_cool 3: N0(ψ)←0N_0(ψ)← 0 for all ψ∈Ψψ∈ ; b0←Prior(N0)b_0← Prior(N_0) 4: r←1r← 1; μ←nullμ← null; c,u←0c,u← 0; ψ^0j,ψ−1j←argmaxψ∈Ψb0(ψ) ψ^j_0,ψ^j_-1← _ψ∈ b_0(ψ) 5: for t=1,2,…t=1,2,… until the episode terminates do 6: Observe otio^i_t and infer a^t−1j a_t-1^j from otio^i_t 7: ψ^t−1j←argmaxψ∈Ψbt−1(ψ) ψ^j_t-1← _ψ∈ b_t-1(ψ) 8: u←1+[ψ^t−1j=ψ^t−2j]u← 1+ 1[ ψ^j_t-1= ψ^j_t-2]u 9: ℓt←∏l=maxr,t−kt−1Ll(ψ^tj) _t← _l= \r,t-k\^t-1L_l( ψ^j_t) 10: Ct←[ℓt<θobs]C_t← 1[ _t< _obs] 11: Replant←Gate(Ct,u,bt−1(ψ^t−1j),μ,c)Replan_t← Gate(C_t,u,b_t-1( ψ^j_t-1),μ,c) 12: b~t←Correct(bt−1,lt) b_t← Correct(b_t-1,l_t) 13: if the teammate visibly completes a skill ψtcomp _t^comp then 14: Nt(ψ)←Nt−1(ψ)+[ψ^tcomp=ψ]N_t(ψ)← N_t-1(ψ)+ 1[ ψ_t^comp=ψ] for all ψ∈Ψψ∈ 15: bt←Prior(Nt)b_t← Prior(N_t); r←tr← t; u←0u← 0 16: else 17: bt←b~tb_t← b_t 18: end if 19: if complete(μ)∨Replantcomplete(μ) _t then μ←nullμ← null 20: if ReplantReplan_t then c←Ccoolc← C_cool else c←max(c−1,0)c← (c-1,0) 21: if μ=nullμ= null then 22: ψ^tj←argmaxψ∈Ψbt(ψ) ψ_t^j← _ψ∈ b_t(ψ) 23: μ←Plan(oti,bt,ψ^tj,ℳfeasible(st))μ← Plan(o^i_t,b_t, ψ_t^j,M_feasible(s_t)) 24: end if 25: Execute one low-level controller step conditioned on μ 26: end for 7.1 Algorithm Walkthrough Lines 1–2 initialize the episode-level completed-skill counts, the smoothed prior in Eq. (4), the current partner-skill segment, the ego macro-skill, the cooldown, and the stable-MAP counter. Lines 3–4 begin the per-step loop, observe the public state, and infer the teammate’s latest primitive action from consecutive observations. Lines 5–7 compute the pre-correction MAP skill estimate, update its stability counter, evaluate the recent action likelihood in Eq. (10), form the contradiction signal in Eq. (11), and apply the gated interruption rule in Eq. (12). Line 8 then incorporates the newly observed action through the Bayesian correction defined by Eqs. (6)–(7), using the approximate controller in Eq. (8). Lines 9–15 handle partner-skill boundaries: when a visible completion occurs, the agent infers the completed skill, updates its count using Eq. (5), reinitializes the prior, and begins a new segment; otherwise, it retains the corrected within-segment posterior. Lines 16–17 clear the ego macro-skill after either ordinary completion or contradiction-triggered interruption and update the replanning cooldown. Finally, Lines 18–21 query the high-level planner whenever no macro-skill is active, using the updated posterior, its MAP estimate, and the currently feasible skills, while Lines 22–23 execute one low-level controller step and continue to the next timestep. 8 Partner Population and Baseline Implementations 8.1 Behavior-Preferring Partner Population We train a population of 12 behavior-preferring (BP) partner policies. Following the event-based reward construction of 36, each BP policy is optimized using a shaped reward rBP(st,t)=rtask(st,t)+∑f∈ℱwfϕf(st,t),r^BP_w(s_t,a_t)=r_task(s_t,a_t)+ _f w_f _f(s_t,a_t), (14) where rtaskr_task is the original team reward, ϕf(st,t) _f(s_t,a_t) indicates whether behavior feature f occurred at step t, and wfw_f is its shaping weight. Retaining the task reward encourages the BP policy to express its assigned preference while continuing to contribute to task completion. The population is divided into three groups representing logistics, cooking, and ingredient-sourcing preferences. Within each group, two behavior features have two possible reward weights and a third feature has a fixed positive weight. We train all four combinations of the two variable weights, producing four BP policies per group and twelve policies in total. All twelve policies use the same PPO architecture and optimization procedure, described in Appendix 8.3. 8.2 Behavior-Preferring Reward Configurations Table 5 specifies the event-weight space used for each BP group. A set such as −30,+20\-30,+20\ denotes two alternative weights. Within each group, the two non-fixed weight sets are crossed to obtain four reward configurations. Table 5: Event-weight configurations used to train the 12 BP partner policies. Within each group, the two non-fixed weights are crossed, producing four policies; the third weight is fixed across those four policies. Group Behavior Feature Reward(s) Group 1 (Logistics) Plating Ingredients −30,+20\-30,+20\ Washing Plates −30,+20\-30,+20\ Delivering Dishes +20+20 (fixed) Group 2 (Cooking) Chopping Ingredients −30,+20\-30,+20\ Potting Rice −30,+20\-30,+20\ Grilling Meat +20+20 (fixed) Group 3 (Sourcing) Taking Mushroom −15,+10\-15,+10\ Taking Rice −15,+10\-15,+10\ Taking Meat +10+10 (fixed) 8.3 Behavior-Preferring Policy Training Each reward configuration is trained independently using RLlib PPO. All policies use the same observation representation, policy network, optimizer, and training schedule. We train each policy for 3 million environment steps using a learning rate of 5e-5, discount factor γ=0.999γ= 0.999, GAE parameter λ=0.999λ= 0.999, PPO clipping parameter ϵ=0.2ε=0.2, train batch size 8192, minibatch size 768, and entropy coefficient 0.02. For each reward configuration, we select the best checkpoint according to evaluation rewards, yielding exactly 12 evaluation partners. 8.4 ProAgent We implement ProAgent using the authors’ released codebase.11 1 https://github.com/PKU-Alignment/ProAgent We retain its default system prompts, interaction history, teammate-intention prediction, and hierarchical LLM planning. We replace the original Overcooked interface with our Burrito-AI state serializer, feasible-action mask, macro-skill vocabulary, and shared low-level controller. The planner is queried when the current macro-skill completes, becomes invalid, or reaches its timeout; it does not interrupt an active skill solely because the teammate’s behavior changes. 8.5 Hypothetical Minds We adapt the authors’ implementation of Hypothetical Minds.22 2 https://github.com/locross93/Hypothetical-Minds We replace its Melting Pot observation interface with our symbolic Burrito-AI state representation while retaining its memory and generate–evaluate–refine Theory-of-Mind procedure. The highest-rated hypotheses about the teammate condition high-level strategy generation; the resulting high-level action is mapped to our macro-skill space and executed using the same low-level controller as the other LLM agents. 8.6 Shared RL Baseline Infrastructure The RL baselines use the Burrito environment and training infrastructure released with TALENTS.33 3 https://github.com/benji-li/talents-zsc In particular, they share the environment wrapper, state encoding, 27-action macro-skill space, action masking, PPO implementation, and evaluation interface. Consequently, TALENTS and GAMMA differ in partner generation and adaptation rather than in their underlying environment or controller implementation. 8.7 TALENTS We use the released TALENTS implementation.44 4 https://github.com/benji-li/talents-zsc TALENTS trains a sequential VAE on partner trajectories, clusters the learned latent strategies using k-means, and trains a strategy-conditioned PPO cooperator against partners generated from those clusters. During evaluation, it compares observed teammate actions with the cluster-conditioned predictions and uses fixed-share regret minimization to update the strategy estimate conditioning its policy. 8.8 GAMMA and Other RL Baselines We run GAMMA in the shared TALENTS Burrito infrastructure, following the authors’ released GAMMA implementation.55 5 https://github.com/lych1233/GAMMA-human-ai-collaboration GAMMA learns a continuous latent generative model of partner trajectories and samples latent codes to generate diverse partners for PPO cooperator training. Unlike TALENTS, it does not partition the latent space into discrete strategy clusters or perform fixed-share partner-type inference during evaluation. 8.9 BayesBeliefAgent Variants All variants use the same LLM, prompt base, state representation, action mask, macro-skill set, and low-level controller. no_belief removes the Bayesian estimator, belief prompting, and contradiction-based interruption. no_prompt maintains the belief and interruption mechanism but does not expose the belief to the LLM. no_replan provides the belief to the planner but disables mid-skill interruption. full combines Bayesian tracking, belief-conditioned prompting, and contradiction-triggered replanning. 9 Reproducibility Details 9.1 Environment and Episode Configuration Experiments use Burrito-AI v1.1.0, an extension of Overcooked-AI (5). We evaluate the Open, Ring, and Forced Coordination layouts. The ego agent observes only the public environment state and infers the teammate’s primitive actions from consecutive observations; the teammate’s active skill and policy are not directly observed. BP partners are loaded from fixed RLlib PPO checkpoints supplied with the code. All evaluation episodes use horizon T=2400. 9.2 Evaluation Protocol We evaluate each ego agent against the 12 BP partners described in Appendix 8.1, with the ego assigned to Player 0 and the partner to Player 1. All main comparisons use seeds 0,1,2,3,4\0,1,2,3,4\. We report the mean and standard deviation across seeds. 9.3 Experimental Hyperparameters Table 6 reports the principal inference, replanning, and execution hyperparameters used in the experiments. Table 6: Experimental hyperparameters. Parameter Value Prior smoothing α 11 Contradiction threshold θobs _obs 0.040.04 Stability window K 33 updates Replanning cooldown CcoolC_cool 66 steps Macro-skill timeout 3030 steps Pass/PutDown likelihood weight 0.350.35 LLM temperature 0.00.0 Planner history 33 turns Confidence threshold (Γconf _conf) 0.65 Inference window (k) 10 9.4 LLM Inference Configuration We evaluate gpt-4o and gpt-5.2 through the OpenAI API with temperature 0.00.0 for deterministic runs. The planner receives the three most recent interaction turns. Its response is parsed against the currently feasible macro-skill set, with up to three retries when the returned action is invalid. The complete system prompts and output formats are provided in Appendix 10. 9.5 Macro-Skill Vocabulary and Low-Level Controllers All LLM-based agents use the same 27 macro-skills, indexed from 0 to 26, together with the same Burrito-AI action mask and skill-conditioned low-level controller. The action mask removes skills whose object, hand-state, or station preconditions are not satisfied. A selected skill remains active until it completes, becomes invalid, is interrupted, or reaches its action-specific timeout. Fire-handling actions (indices 3, 6, 14, and 24) and Stay (index 4) are excluded from partner-belief updates. Because Pass and PutDown can support several latent skills, their likelihood contributions are tempered by a weight of 0.350.35. 10 System Prompts and Planner Inputs Unless noted otherwise, all LLM agents below share the same Burrito scene encoding in the user message: layout station list, timestep, both players’ positions/orientations/held objects, active orders, map objects (with cooking tags), optional urgency flags, and a mask-filtered VALID ACTIONS list. Placeholders such as agent_id are filled at runtime (ego player index; teammate is 1−agent_id1- agent\_id). 10.1 ProAgent System Prompt The evaluated burrito ProAgent (BurritoProAgent) uses the following system prompt exactly (inline default; no layout-specific planner file is loaded). ⬇ 1 You are an expert planner for the Burrito variant of Overcooked. 2 Your job is to control the current player and cooperate with the teammate to maximize score. 3 The teammate cannot communicate, so infer their likely intent from their position, held object, and nearby stations. 4 5 Game dynamics: 6 - The active orders are shown in ‘orders:‘. The first listed order is the highest-priority order and gives the in-order bonus, but other listed orders are still deliverable. 7 - There are two burrito recipes: 8 - steak_burrito_dish = chopped_steak + boiled_rice + tortilla. 9 - mushroom_burrito_dish = fried_mushroom + boiled_rice + tortilla. 10 - Meat and mushroom are raw ingredients. They must be chopped at the chopping board first, then finished on the grill. 11 - Rice is cooked in the pot. 12 - Tortilla is never cooked in the pot or grill. It is assembled onto a plate or ingredient plate. 13 - A clean plate is needed to collect finished rice from the pot and finished steak or mushroom from the grill. 14 - Burritos are assembled by combining the plated ingredients and tortilla in any legal order supported by the environment. 15 - Deliver only a completed burrito (‘steak_burrito‘ or ‘mushroom_burrito‘) at serving. 16 17 Objects and stations: 18 - ‘M‘ meat dispenser, ‘Z‘ mushroom dispenser, ‘R‘ rice dispenser, ‘T‘ tortilla dispenser. 19 - ‘B‘ chopping board, ‘G‘ grill, ‘P‘ pot, ‘W‘ sink, ‘D‘ dirty plate source, ‘S‘ serving, ‘X‘ counter, ‘U‘ trash. 20 - Each player can hold exactly one object. 21 - Counters hold one object and are useful for staging and passing items. 22 - Dirty plates must usually be taken from ‘D‘, washed at ‘W‘, and then used as clean plates. 23 24 State interpretation: 25 - The scene lists player positions, held objects, active orders, and current objects on the map. 26 - Object tags may include ‘cooking‘, ‘ready‘, ‘waiting‘, ‘warning‘, or ‘BURNT‘. 27 - ‘ready‘ or ‘waiting‘ means the ingredient can be picked up now. 28 - ‘warning‘ means a cooked ingredient has been left too long and is urgent. 29 - ‘BURNT‘ means the pot or grill output is on fire; use a fire extinguisher before normal pickup. After extinguishing, charcoal usually should be trashed. 30 31 Planning heuristics: 32 - Prefer the shortest useful step that advances an active order or prevents a loss. 33 - When a cooked ingredient is in ‘warning‘ state or a fire exists, treat it as highly urgent. 34 - Avoid duplicating the teammate when complementary work is better, such as preparing a plate, tortilla, or another missing ingredient. 35 - If the layout is partitioned, ‘PASS_OBJECT‘ is for handing items across shared counters; otherwise ‘PUT_DOWN_OBJECT‘ is the normal staging action. 36 - If you cannot make immediate progress, choose the least wasteful action from the VALID ACTIONS list. 37 38 Think through the scene silently, including likely teammate intent, but do not reveal your reasoning. 39 Output exactly one high-level action as either: 40 - an integer in [0,26], or 41 - one action name from VALID ACTIONS. 42 Do not output explanations, analysis, or extra text. Planner user message template. Joined as a single user string (heuristic teammate-intent line included): ⬇ 1 Layout=<layout>. <station>:<locations> ... Scene <t>. 2 Pego pos=... or=... hold=.... 3 Ptm pos=... or=... hold=.... 4 orders: <upto 4 active orders> 5 objects: (name@pos [tags...]) ... 6 Teammate intent: Ptm at <pos> facing <ori> holds <held> — <heuristic>. 7 [URGENCY: <fire/warning alerts>] 8 VALID ACTIONS -> <idx>:<NAME>; ... 9 Return one action only (index or name). 10.2 Hypothetical Minds Prompts Burrito Hypothetical Minds reuses the ProAgent system prompt, then appends the following planner system suffix (player indices filled at runtime): ⬇ 1 You are a Hypothetical Minds Burrito agent. Maintain hypotheses about the teammate’s strategy, 2 predict their next behavior from observations, and choose a complementary action. 3 When asked for a final action, choose exactly ONE item from VALID ACTIONS. 4 Use this final format: 5 Teammate strategy hypothesis: <short hypothesis for Player other_id> 6 Predicted next behavior for Player other_id: <short behavior prediction> 7 Plan for Player agent_id: "<one action index or action name>" 8 No extra text after the plan line. Each planning step issues up to four LLM calls. Hypothesis-evaluation prompt. ⬇ 1 Evaluate these teammate behavior predictions for Burrito in one batch. 2 Observed teammate actions since last evaluation: <recent_actions> 3 4 Predictions: 5 h<ID>: <predicted_next_behavior> 6 ... 7 8 For each hypothesis, decide whether its prediction matched the observed teammate actions. 9 Return exactly one line per hypothesis in this format: 10 h<ID>: True 11 or 12 h<ID>: False 13 Do not include explanations. Hypothesis-generation prompt. Skipped when a hypothesis value exceeds 0.70.7; otherwise: ⬇ 1 Based on the Burrito scene and observed teammate actions, infer the teammate’s current strategy. 2 <state_prompt> 3 4 Observed teammate actions: <last 12 events> 5 Existing hypotheses: 6 <best_hypothesis_summary> 7 Return one concise teammate strategy hypothesis. Behavior-prediction prompt. ⬇ 1 Predict the teammate’s next useful Burrito behavior from this strategy. 2 Teammate strategy hypothesis: <strategy> 3 <state_prompt> 4 5 Observed teammate actions: <last 12 events> 6 Return one concise predicted next behavior. Final planning (action) prompt. ⬇ 1 <state_prompt> 2 3 Hypothetical Minds context: 4 - Teammate strategy hypothesis for Player other: <strategy> 5 - Predicted next behavior for Player other: <prediction> 6 - Top teammate hypotheses: 7 <best_hypothesis_summary> 8 9 Choose a complementary Burrito high-level action for yourself. 10 Avoid duplicating the predicted teammate behavior when another valid action advances the order. 11 Return exactly: 12 Teammate strategy hypothesis: <strategy> 13 Predicted next behavior for Player other: <prediction> 14 Plan for Player agent_id: "<one action index or action name from VALID ACTIONS>" Memory format. Hypothetical Minds maintains an explicit store of teammate hypotheses across timesteps. Each entry records a natural-language strategy, a predicted next behavior, a scalar reliability score, and the creation timestep. After each evaluation call, the score is updated with a Rescorla–Wagner rule (v←v+α(±1−v)v← v+α(± 1-v) with α=0.3α=0.3), using +1+1 when the predicted behavior matches recent teammate actions and −1-1 otherwise. If any hypothesis exceeds a reliability threshold of 0.70.7, generation is skipped and the highest-scoring strategy is reused. Observed teammate events are logged as (step, action, position, holding) and provided to the evaluation and generation prompts. The top-m hypotheses are rendered into later prompts as: ⬇ 1 Existing hypotheses: 2 - h1: value=0.42, strategy=<short teammate strategy>, predicted_next_behavior=<short prediction> 3 - h2: value=0.18, strategy=<short teammate strategy>, predicted_next_behavior=<short prediction> If the store is empty, the injected text is instead No prior teammate strategy hypotheses. 10.3 BayesBeliefAgent Prompt At evaluation time, BurritoBayesBeliefAgent appends the following system prompt to the ProAgent System prompt. ⬇ 1 You are an expert Burrito cooperative cooking agent controlling Player agent_id. 2 You must cooperate with Player other_id to maximize burrito deliveries. 3 4 GAME RULES (brief): 5 - Two recipes: steak_burrito (chopped_steak + boiled_rice + tortilla) 6 mushroom_burrito (fried_mushroom + boiled_rice + tortilla) 7 - Each player holds one item at a time. 8 - Fire is an emergency: grab fire_ext (14), then put out fire (3), then trash charcoal (6). 9 - A Bayesian filter tracks your teammate’s coordination role in real time. 10 Use the belief summary to AVOID duplication and choose complementary actions. 11 12 OUTPUT FORMAT (one line each, required): 13 Teammate role belief: <description of teammate’s likely coordination role> 14 Intention for Player other_id: "<action_index_or_name>" 15 Plan for Player agent_id: "<action_index_or_name>" 16 17 <burrito_rules_prompt> 18 19 Return one action only (index or name) on the Plan line. Bayesian belief block (user prefix). Roles: prep_protein, prep_rice, plate_hygiene, assemble, serve, stage_pass. ⬇ 1 === TEAMMATE BELIEF (Bayesian Filter) === 2 MAP role : <role> (confidence=<c>, commitment=<k>) 3 Heading to : <station hint | unknown (low confidence)> 4 Posterior : 5 <role>: <p> <bar> 6 ... 7 → Teammate in ’<role>’ — consider: <complements> 8 OR → Posterior uncertain — act on game-state needs, do NOT wait. 9 ========================================= Urgency / advisory flags (appended when applicable). ⬇ 1 [LOW CONFIDENCE — teammate role unclear. Act on game-state needs, do NOT choose STAY.] 2 [MODERATE CONFIDENCE — prefer complementary actions.] 3 CURRENT PRIORITY ORDER: <top_order> 4 FIRE ACTIVE — override normal planning. 5 COOKING TIMER LOW: retrieve the cooked item NOW. 6 CHARCOAL on grill — clear it: GRAB_CHARCOAL (24) then GO_TO_TRASH_AND_THROW (6). ... State prompt. Same burrito scene encoding as ProAgent (including heuristic teammate-intent and URGENCY: fire/warning lines). User message = belief block + state prompt. 10.4 Prompt Changes in the Ablations Ablations share identical system prompts. Only belief injection and replanning change: Ablation Belief in prompt Replan full injected enabled no_replan injected disabled no_prompt omitted ("") enabled no_belief omitted; tracking off disabled Thus no_belief is prompt-equivalent to a plain planner with no ToM context, while no_prompt keeps internal tracking/replanning but hides belief text from the LLM. 11 Extended Results This section reports additional mechanism analyses, paired uncertainty estimates, hyperparameter sensitivity, backbone comparisons, and zero-shot cross-play results. 11.1 Gate and Likelihood Sensitivity Table 7 varies one parameter at a time on Open G1 while holding the remaining parameters at their default values. This ablation is conducted to show the influence of the proposed gating mechanism in detecting a posterior shift in the partner’s skill in Eq. 12. Increasing the observation threshold or likelihood scale produces more replans, whereas increasing the confidence floor or cooldown suppresses them. The default setting attains the highest reward and lowest gap rate among the tested values. Both more permissive and more restrictive settings perform worse, indicating a useful intermediate operating region. This experiment is a local sensitivity analysis and does not establish global optimality. Table 7: One-at-a-time sensitivity analysis on Open G1. Defaults are shown in bold. Parameter Value Reward Replans/ep. Gap rate Obs. threshold 0.02 1450 0.8 0.23 0.04 (default) 1533 2.0 0.17 0.06 1490 5.6 0.19 Conf. floor 0.55 1475 4.8 0.20 0.65 (default) 1533 2.0 0.17 0.75 1460 0.9 0.22 Cooldown 3 1495 3.7 0.19 6 (default) 1533 2.0 0.17 12 1468 1.2 0.21 Likelihood scale 0.5×0.5× 1470 1.1 0.22 1.0×1.0× (default) 1533 2.0 0.17 1.5×1.5× 1482 4.2 0.20 11.2 Paired Bootstrap Comparisons Table 8 reports paired Full−-No replan differences. Positive reward differences and negative gap-rate differences favor the full agent. The reward interval excludes zero in Open G1 and Open G3, while the gap-rate interval excludes zero in five of the seven settings. The remaining settings have intervals containing zero and therefore do not support a reliable difference under this analysis. Because the table reports bootstrap intervals rather than multiplicity-corrected p-values, we restrict the interpretation to whether each interval excludes zero. Table 8: Paired Full−-No replan differences with 95%95\% bootstrap confidence intervals. Setting Δ Reward (95% CI) Δ Gap (95% CI) Open G1 +343[+75,+601]+343\ [+75,\ +601] −0.26[−0.35,−0.16]-0.26\ [-0.35,\ -0.16] Open G2 +74[−92,+231]+74\ [-92,\ +231] −0.15[−0.26,−0.04]-0.15\ [-0.26,\ -0.04] Open G3 +310[+42,+566]+310\ [+42,\ +566] −0.21[−0.31,−0.11]-0.21\ [-0.31,\ -0.11] Ring G1 +98[−131,+322]+98\ [-131,\ +322] −0.13[−0.23,−0.03]-0.13\ [-0.23,\ -0.03] Ring G2 −33[−165,+102]-33\ [-165,\ +102] −0.05[−0.14,+0.04]-0.05\ [-0.14,\ +0.04] Ring G3 +67[−58,+190]+67\ [-58,\ +190] −0.12[−0.21,−0.03]-0.12\ [-0.21,\ -0.03] FC agg. +2[−5,+9]+2\ [-5,\ +9] −0.05[−0.13,+0.03]-0.05\ [-0.13,\ +0.03] 11.3 Mechanism Metrics Across Settings We extend the results from Table 2 and show their detailed breakdown across all behavior-preferred groups. Table 10 compares BayesBeliefAgent with the ProAgent across layouts and partner groups. Predicted skill accuracy differs by at most 0.010.01, indicating that both methods obtain similar skill accuracies. In contrast, the full agent consistently reduces the belief-action gap and duplicate-skill rate while increasing Comp@3. The differences are largest in the Open settings and smaller in Ring G2 and Forced Coordination. 11.4 Zero-Shot Cross-Play Table 11 evaluates each agent in both the ego and partner positions. TALENTS achieves the highest average as an ego agent and as a partner in both layouts. Among the LLM-based ego agents, BayesBeliefAgent has the higher Open and Ring average. The latter is also the second-best Ring partner by column average. Performance varies substantially across individual pairings. In particular, BayesBeliefAgent scores 1917.01917.0 with a TALENTS partner in Open and 1791.71791.7 in Ring, but performs less strongly with ProAgent in Ring (inclusive of standard deviation over performance). The large standard deviations in several LLM pairings further indicate that cross-play outcomes depend on both the partner and the layout. 11.5 Sensitivity to the Base LLM Table 9 compares GPT-4o and GPT-5.2 while holding the remaining agent components fixed. GPT-5.2 obtains higher reward and a lower gap rate in Open G2, Ring G1, and Ring G2, whereas GPT-4o performs better on the other three settings. The differences are therefore non-monotone, and neither backbone consistently dominates. We use GPT-4o as the primary configuration and treat the GPT-5.2 results as a backbone-sensitivity check. Table 9: Reward and belief–action gap rate with GPT-4o and GPT-5.2 as the high-level planner backbone. Setting 4o reward 5.2 reward 4o gap 5.2 gap Open G1 1533 1485 0.17 0.19 Open G2 337 395 0.24 0.22 Open G3 1420 1360 0.20 0.21 Ring G1 663 705 0.25 0.23 Ring G2 231 285 0.32 0.29 Ring G3 506 470 0.27 0.28 Table 10: Mechanism metrics for the full agent and the No replan variant. Forced Coordination aggregates Groups 1–3. Arrows indicate the preferred direction. Setting Method Skill acc. (↑ ) Gap rate (↓ ) Comp@3 (↑ ) Dup. Skill (↓ ) Open G1 BayesBeliefAgent 0.82 0.17 0.71 0.12 ProAgent 0.81 0.43 0.36 0.31 Open G2 BayesBeliefAgent 0.76 0.24 0.61 0.18 ProAgent 0.75 0.39 0.42 0.29 Open G3 BayesBeliefAgent 0.79 0.20 0.66 0.15 ProAgent 0.78 0.41 0.39 0.30 Ring G1 BayesBeliefAgent 0.74 0.25 0.59 0.20 ProAgent 0.73 0.38 0.43 0.28 Ring G2 BayesBeliefAgent 0.68 0.32 0.49 0.27 ProAgent 0.68 0.37 0.43 0.31 Ring G3 BayesBeliefAgent 0.72 0.27 0.55 0.23 ProAgent 0.71 0.39 0.42 0.30 FC G1–G3 BayesBeliefAgent 0.61 0.42 0.31 0.37 ProAgent 0.60 0.47 0.26 0.41 Table 11: Zero-shot cross-play reward, reported as mean with standard deviation in parentheses. Rows identify the P0P_0 ego agent and columns identify the P1P_1 partner. Agent (P0↓P_0 , P1→P_1→) Bayes Pro GAMMA TALENTS Mean over P1P_1 Open Bayes 720.3 (256.8) 853.0 (738.8) 779.3 (373.9) 1917.0 (529.6) 1067.4 (474.8) Pro 827.0 (582.2) 561.3 (675.2) 853.0 (372.5) 1934.0 (677.6) 1043.8 (576.9) GAMMA 608.3 (86.1) 1698.7 (531.5) 440.7 (61.6) 1262.3 (74.1) 1002.5 (188.3) TALENTS 1034.0 (195.4) 1305.0 (149.3) 1160.0 (216.1) 1390.7 (157.8) 1222.4 (179.6) Mean over P0P_0 797.4 (280.1) 1104.5 (523.7) 783.2 (256.0) 1625.8 (359.8) – Ring Bayes 636.7 (161.7) 448.7 (293.1) 1269.7 (176.4) 1791.7 (216.5) 1034.2 (211.9) Pro 382.7 (330.0) 107.7 (98.4) 384.3 (230.7) 721.3 (521.2) 399.0 (295.1) GAMMA 1243.7 (295.7) 619.3 (481.3) 958.0 (163.6) 1069.7 (338.7) 972.7 (319.9) TALENTS 1520.7 (360.9) 752.0 (440.7) 1141.0 (320.2) 1108.3 (186.2) 1133.0 (327.0) Mean over P0P_0 945.9 (287.1) 481.9 (328.4) 938.2 (222.7) 1172.8 (315.6) – 11.6 Ground-truth complementary mapping. Construction. Our evaluation ground truth is a deterministic lookup table (not trajectory annotations) authored from the recipe production graph prior to evaluation. Given the teammate’s current skill (or the role that skill belongs to), the complementary set is fixed and does not depend on layout, timestep, or annotator judgment. Scoring rule. Because the table is authored once and then applied programmatically, there are no independent raters, no disagreement cases, and no adjudication protocol. An ego-selected skill is counted as complementary if and only if it appears in the set associated with the teammate’s current skill. The mapping is many-valued (multiple ego skills may be complementary to the same teammate skill), and duplicating the teammate’s pipeline is never complementary. Fire-control, trash, and STAY are excluded from scoring. Burrito. High-level actions are first mapped to six roles, then to complementary roles: • prep_protein ↦ prep_rice, plate_hygiene, assemble • prep_rice ↦ prep_protein, plate_hygiene, assemble • plate_hygiene ↦ prep_protein, prep_rice, assemble • assemble ↦ prep_protein, prep_rice, plate_hygiene, serve • serve ↦ prep_protein, prep_rice, plate_hygiene • stage_pass ↦ prep_protein, prep_rice, assemble An ego action is complementary iff its role lies in the teammate’s complementary set. An ego action is complementary iff its role lies in the teammate’s complementary set. 11, 42