acceptodds
Under review as a conference paper at ICLR 2027

Test-Time Policy Improvement for Coordination with Unseen Partners

Abstract

Cooperative multi-agent reinforcement learning prepares an agent for unseen partners by training it against a diverse population, so that one policy, fixed before deployment, generalises to partners it never trained with. But a policy committed before the partner is met must compromise whenever plausible partners call for incompatible responses, a gap no training-time diversity can close. We address this gap by introducing test-time best response (TTBR): after a short observation phase (16 episodes per seat), the agent forms an exact posterior over an explicit class of partner programs and policies and improves its own policy against it in the simulator. We show that the regret of the exact posterior response is bounded by the conflict among candidate partners, the cross-best-response regret that underlies minimum coverage sets, times the residual posterior odds, a guarantee that also predicts when partner identification cannot help. The resulting algorithm (i) responds to the partner actually present rather than to a population, (ii) retains its in-class skill, and (iii) applies to any self-play policy and pays its compute once. On Overcooked and level-based foraging, against held-out partners from the modelled family, TTBR recovers a large share of the coordination lost with strangers and beats a generalist trained on the whole partner family where responses conflict. Where nothing conflicts a generalist suffices, and outside the modelled family TTBR degrades gracefully but has no edge, while planning keeps one.

Primary area:
reinforcement learning
Keywords:
zero-shot coordination, ad hoc teamwork, few-shot coordination, multi-agent reinforcement learning, test-time adaptation, test-time compute, Bayesian partner identification, best response, policy improvement, decision-time planning, regret bound, Overcooked, level-based foraging

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_FfJSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper presents Test-time best response (TTBR) which is considering the problem of cooperation with an unseen partner after a brief observation phase. The method idea is to use the observed actions for infering the class of the observed policy from a family and then fine tune the learned policy in simulation. The paper gives theorectical analysis and proofs regarding the usefulness of the individuation of the cooperating agent class as well as the bounds over the regrets based on the confidence uppon the cooperating agent class. The method has been tested on three Overcooked layouts and level-based foraginf showing substantial gains over the blueprint.

Critical strengths
  • Relevance to the conference: the topic of the paper is relevant to the ICLR community.
  • Theoretical analysis: The theoretical analysis proposes a solution that defines a conditional threshold, which incorporates both the conflict between responses and residual uncertainty; this sheds light on the extent to which - from a theoretical standpoint - it is necessary (or unnecessary) to identify the strategy class of a competing agent. This finding is supported by empirical evidence, which compares the TTBR method with a generalist approach.
  • Technical soundness: I do not have found any specific technical issue, the paper looks technically sound.
Critical weaknesses
  • Writing quality and paper organization: The paper is hard to read. No clear algorithm is defined and explained in the main paper, while a lot of material is just put into the appendix. The method section (sec 3) does not actually present the method but answers some questions providing a sort of theoretical analysis without having clearly defined the method before. This makes very hard to me understanding the actual method, without checking the appendix. Also the results section answers some questions but it does not clearly compare the performance of the proposed algorithm with that of a recognised algorithm in the literature.
  • Novelty: The proposed pipeline combines established components: Bayesian partner-type inference, response selection or improvement conditioned on the inferred belief, and simulator-based test-time fine-tuning. The clearest original contribution appears to be the finite-observation regret analysis linking cross-best-response conflict to residual posterior odds. Since the conflict measure builds on cross-best-response regret used in the minimum-coverage-set literature (Rahman et al., 2024), the paper should clarify what is technically new in this analysis. It also does not compare against its acknowledged alternative of selecting among precomputed best responses using the same posterior. Given that MAP fine-tuning performs similarly to posterior fine-tuning on three of the four layouts, the experiments leave the added value of on-demand response computation unclear.
  • Gap between the formal conflict measure and how the experiments interpret it: The main theoretical results - Proposition 1, Corollary 1, Lemma 1, Theorem 1, and the misspecification corollary - appear mathematically correct under their stated assumptions. However, the experiments estimate conflict using finite PPO fine-tunes rather than exact best responses, so the claimed relation h <=kappa is not guaranteed for those measurements; even with exact best responses, observing small h would not establish zero conflict. This weakens the claim that the control layouts are conflict-free, and the theorem’s guarantee also does not directly cover the deployed finite-PPO policy because its optimization error is unbounded.
  • Limited performance increase: The comparison with published ad hoc teamwork baselines is difficult to assess from the main paper: the ICRL4AHT result is only briefly summarized in RQ5, while the detailed comparison appears in the appendix. Moreover, this comparison covers only one wide-layout benchmark and two published in-context baselines. TTBR scores +2.7, matching the generalist, and trails the search baseline (+17.0). These results provide limited evidence that TTBR outperforms strong ad hoc teamwork methods; a clearer main-text comparison across more settings and methods would strengthen this claim.
  • Lack of a comparisons with baseline algorithms: I find that a key baseline is missing. The current approach involves defining a method that performs fine-tuning on a set of simulations, weighted according to the computed posterior probabilities - as opposed to fine-tuning solely on the simulation with the highest probability. The paper itself acknowledges a limitation: one could instead develop a distinct policy for each member of the family and dynamically select the appropriate policy - without further fine-tuning - based on the specific agent encountered at runtime. The absence of this baseline is a significant shortcoming.
  • An acknowledged limitation is the use of agents that belong to the same family. The method’s performance drops when it encounters agents it has not seen before, becoming equivalent to a generalist baseline - which, unlike this method, does not require a set of trajectories from the concurrent agent (as is the case for TTBR), nor does it necessitate a fine-tuning phase that assumes access to a simulator. This is acknowledged but it seems to be an important weakness of the method.
  • Scalability: The method’s scalability to large or continuous state and action spaces is unclear: all experiments use small discrete environments, and TTBR relies on a tractable partner hypothesis class with computable action likelihoods and simulator support.
  • Reproducibility: the code seems not to be available, which hinders reproducibility.
  • Missing related work section.
Questions for authors
  1. Which is the most similar algorithm to TTBR in the literature? What is the methodological original contribution that TTBR introduces w.r.t. that algorithm? How much does TTBR improves performance w.r.t. that algorithm? 2. Please clarify on the issues identified in the section "Critical Weaknesses".
Reviewer_fbxpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TTBR, which infers a partner model from observed interactions and fine-tunes a pretrained policy against the inferred partner distribution using PPO in a simulator. The paper provides a regret-based analysis and evaluates the approach on cooperative multi-agent tasks.

Critical strengths
  • The paper studies an important problem: how agents can adapt and coordinate effectively with previously unseen partners.
Critical weaknesses

As mentioned in Crtitical Strengths, the paper addresses an important problem. The proposed approach is reasonable, particularly its aim to preserve coordination with previous partners while adapting to a new one. However, I have the following concerns:

  • Insufficient comparison with existing adaptation methods. The experiments include train-time baselines, planning, and several variants of the proposed method, but comparisons with existing partner-adaptation and test-time fine-tuning approaches are missing. Relevant examples include TALENTS [1], CooT [2], and RL Search [3]. Comparing against every method is unnecessary, but a few representative comparisons under comparable conditions are needed to establish the additional benefit of TTBR. The program-generalist and internal MAP or true-program fine-tuning variants do not sufficiently answer this question.

  • Unclear practicality of the adaptation cost. The default adaptation procedure requires approximately 6.6 million simulator steps and 70 minutes on eight CPU cores for each partner. This constitutes substantial partner-specific fine-tuning, raising concerns about its practicality as a test-time adaptation method. Although the paper analyzes computational cost relative to planning, it remains unclear in which deployment settings this substantial adaptation phase would be acceptable and whether the resulting benefits justify the cost.

[1] Li et al. “Adaptively Coordinating with Novel Partners via Learned Latent Strategies.” NeurIPS, 2025.

[2] Wang et al. “CooT: Learning to Coordinate In-Context with Coordination Transformers.” ICML, 2026.

[3] Fickinger et al. “Scalable Online Planning via Reinforcement Learning Fine-Tuning.” NeurIPS, 2021.

Questions for authors
  • How does TTBR compare with representative existing partner-adaptation and test-time fine-tuning methods under comparable information and computational budgets?

  • What evidence supports the practical value of performing substantial fine-tuning for each new partner, and under what deployment conditions would this adaptation cost be justified?

Reviewer_tGL4OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the limitation of zero-shot coordination (ZSC) against unseen teammates whose optimal best responses conflict, where any single fixed policy trained before deployment is forced to compromise. The authors propose Test-Time Best Response (TTBR), a few-shot coordination protocol in which an unadapted self-play blueprint observes 16–32 interaction episodes with an unknown partner, computes an exact Bayesian posterior over an explicit hybrid hypothesis class combining parameterized heuristic programs and stored self-play checkpoints, and fine-tunes its policy via PPO in a simulator against that posterior—anchored by self-play and a uniform checkpoint floor to prevent catastrophic forgetting of in-class skill. Theoretically, the authors prove that the regret of a posterior best response is bounded by the pairwise cross-best-response conflict among candidate partners times the residual posterior odds (which decay exponentially with accumulated Bhattacharyya evidence), characterizing when partner identification is necessary (high conflict and informative observations) versus vacuous (zero conflict or passive partners). Empirically, across three OvercookedV2 layouts and Level-Based Foraging using pre-registered decision rules, TTBR recovers a substantial fraction of the coordination gap with off-grid heuristic and neural strangers, outperforms a generalist trained directly on the full program family specifically on layouts with measured partner conflict, extracts higher returns than matched-posterior decision-time rollout planning when adaptations require episode-long horizon commitments, and degrades gracefully without edge against out-of-family teammates on the ICRL4AHT benchmark.

Critical strengths
  • Principled Theoretical and Empirical Resolution of When Partner Identification Matters: The paper cleanly connects the structural ceiling of train-time population diversity to pairwise best-response conflict κ(j→k)\kappa(j \to k) and proves an assumption-light finite-sample regret bound (Regτθ(πb)≤κˉθON\text{Reg}_{\tau_\theta}(\pi_b) \le \bar{\kappa}_\theta O_N) that decomposes posterior response regret into partner conflict times residual posterior odds. This is highly consequential because the authors empirically measure the 400-pair cross-best-response conflict matrix across layouts and verify both directions of their theory: test-time identification significantly outperforms a program-family generalist exactly on layouts with non-zero conflict (Cramped Room and Wide) and offers zero advantage over a generalist or uniform prior where best responses do not conflict (Asymmetric Advantages and LBF).

  • Rigorous, Matched-Information Dissection of Test-Time Policy Improvement vs. Planning: By holding the exact Bayesian posterior fixed after the observation phase, the paper delivers a controlled comparison between spending test-time simulator compute once on PPO policy improvement (TTBR) versus per-step on decision-time rollout search. This is consequential because it reveals their exact, complementary failure regimes—TTBR excels on long-horizon spatial and signaling conventions where bounded-horizon search (H≤64H \le 64) is myopic, whereas search rescues passive partners where the unadapted blueprint's observation phase fails to elicit distinguishing actions (DN=0D_N = 0)—backed by exemplary scientific rigor (pre-registered decision rules, confidence intervals over distinct behavioral equivalence classes, and transparent negative/out-of-family boundary tests).

Critical weaknesses
  • Heavy Reliance on an In-Family Hypothesis Class (Assumption A2) and Vanishing Edge Out-of-Family: TTBR's core identification and adaptation advantages rely on the unseen partner belonging to (or closely matching) the hand-crafted parameterized heuristic program family P\mathcal{P}. When evaluated against genuinely out-of-family partners—the 20 external heuristic teammates of the ICRL4AHT benchmark under its standard protocol—TTBR's return (+2.7) is statistically indistinguishable from a zero-test-cost program-generalist (+2.7) and a uniform-prior best response (+2.4), while decision-time rollout search achieves a substantial lead (+17.0). Against held-out neural self-play seeds, most of TTBR's gain transfers across unobserved seeds, indicating generic cross-play regularization rather than partner-specific identification.
  • Omission of an Offline Precomputed Best-Response Selection Baseline Despite Heavy Test-Time Compute Cost: TTBR requires 6.6×1066.6 \times 10^6 simulator steps (~70 minutes on 8 CPU cores) of PPO fine-tuning per partner after observing 16–32 episodes. However, RQ3 reveals that fine-tuning against the single MAP program performs just as well as fine-tuning against the full posterior mixture on three of four layouts (with the difference on Wide statistically inconclusive). Consequently, as the authors acknowledge in Section 5 and Appendix H, a standard type-based baseline that precomputes best responses offline for the finite grid P\mathcal{P} (or its behavioral equivalence classes) and selects the MAP response online would incur zero test-time RL compute while plausibly matching TTBR in-family—leaving unproven whether test-time policy synthesis is actually superior to offline policy selection.
Questions for authors

Questions Affecting Assessment (Experimental & Methodological):

  • Offline Precomputed Best-Response Selection vs. Test-Time RL Synthesis: Given that RQ3 shows fine-tuning against the single MAP program matches fine-tuning against the full posterior mixture on three of four layouts (with the difference on Wide statistically inconclusive), how does TTBR compare to a classic type-based baseline (e.g., PLASTIC / HBA style) that precomputes best responses offline for the representative behavioral equivalence classes of P\mathcal{P} and selects the MAP response online? Clarifying or empirically testing whether test-time PPO synthesis outperforms offline best-response selection—especially on the off-grid noisy strangers—would directly resolve whether the 70 CPU-minute test-time compute cost is necessary.

  • Prioritized vs. Uniform Sampling in the MEP Baseline: In your experimental setup, the MEP ego baseline is trained using uniform FCP-style sampling rather than MEP's prioritized sampling. Could this simplification explain why MEP severely underperforms the self-play blueprint on Cramped Room (58 vs. 121), and would a prioritized-sampling MEP (or a minimum-coverage-set policy selector) close more of the conflict gap without test-time PPO?

Clarification Requests:

  • Centralized Observation Logging in Partially Observable Layouts: In Section 2, the game is formulated as a Dec-POMDP where τi(at∣ht)\tau_i(a_t \vert{} h_t) depends on the partner's private history hth_t. On partially observable layouts like test_time_wide (view radius 2), evaluating Equation (1) exactly requires access to the simulator state or the partner's private observations during the EE observation episodes. Could you explicitly state in Section 2 that the observation phase assumes full state/observation logging before transitioning to decentralized execution at deployment?

Suggestions for Future Work:

  • Active Exploration During the Observation Phase: Since Appendix G traces TTBR's failure on the 5 Wide cook-seat strangers to the unadapted blueprint π0\pi_0 failing to elicit distinguishing partner actions (DN=0D_N = 0), running decision-time search or an exploratory policy during the E=16E=16 observation episodes would be a natural extension to break passive deadlocks before running TTBR.

Comments on the paper

1 comment

I thank the authors for the explanations and answers. I'll take this into account in the discussion with other reviewers.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.