PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent LLMs Fail to Explore Each Other

Hyeong Kyu Choi, Jiatong Li, Wendi Li, Xin Eric Wang, Sharon Li

arXiv:2607.11250v1cs.MAcs.AI

TL;DR

LLM agents often fail to explore peers effectively in multi-agent environments, limiting reliable coordination. The paper introduces MACE, which uses structured peer selection to promote exploration, and finds improved exploration and downstream performance across diverse settings.

  • Problem

    It remains unclear whether LLM agents can balance exploration and exploitation when selecting heterogeneous peers under partial observability.

    Source: §2 · p. 3, §3.2 · p. 6

  • Method

    MACE decomposes multi-agent exploration into contextual bandit decisions using relational features and explicit uncertainty-driven exploration incentives.

    Source: §1 · p. 2, §4 · p. 7

  • Results

    MACE improves exploration and downstream performance across diverse settings, with gains persisting during exploitation and transferring to unseen tasks.

    Source: §1 · p. 2, §5.3 · p. 10, §8 · p. 13

  • Takeaways & Limitations

    Reliable multi-agent autonomy may require explicit exploration rather than relying on exploration to emerge from LLM agents alone.

    Source: §8 · p. 13

    Experiments focus on small- to medium-scale systems and do not empirically establish MACE’s behavior in very large agent populations.

    Source: F. Limitations and Future Directions · p. 51

Abstract

from arXiv · show

Exploration is essential for reliable autonomy in multi-agent systems, yet it remains unclear whether large language model (LLM) agents can explore effectively when interacting with one another. We show that modern LLM agents fail to do so, often exhibiting myopic and polarized interaction patterns that lead to suboptimal coordination and increased regret. We formalize this challenge as the Multi-Agent Exploration problem, modeling it as a partially observable stochastic game (POSG) problem in which agents must probe peers to infer their capabilities and identify effective interaction strategies. To address this, we introduce Multi- Agent Contextual Exploration (MACE), a lightweight framework that explicitly promotes exploration through structured peer selection. Across both contextual and parametric diversity settings, MACE substantially improves exploration behavior and downstream task performance. We further show theoretically that the value of exploration increases with agent diversity. Overall, our results highlight a fundamental limitation of current LLM agents and underscore the importance of explicitly guided exploration for reliable multi-agent autonomy. Code will be released in https://github.com/deeplearning-wisc/mace

1. Introduction

The introduction argues that reliable multi-agent autonomy requires strategic exploration of heterogeneous peers, yet current LLM agents often commit prematurely instead. It formalizes this challenge and introduces MACE, which uses contextual-bandit peer selection to promote exploration and improve performance, especially as agent diversity grows.

Motivation

  • Exploration is foundational to autonomy because it enables agents to discover novel states, self-generate goals, and acquire reusable strategies without external guidance.Its importance increases in multi-agent environments shaped by heterogeneous peer capabilities and behaviors.Source: §1 · p. 1

Problem formulation

  • Multi-agent exploration requires strategically probing adaptive, heterogeneous peers under decentralized partial information, because effective collaborators and interaction strategies are revealed through ongoing interactions.Unlike stationary bandits, peer responses evolve with accumulated experience, and exploration failures can compound across agents and rounds.Source: §1 · pp. 1–2

Motivation

  • Current LLM agents prematurely commit to one peer in a two-armed bandit, including GPT-4 (Achiam et al., 2023) and GPT-5, rather than reliably identifying the better peer.This failure appears structural rather than merely attributable to limited model capacity.Source: §1 · p. 2

Method

  • MACE decomposes the intractable joint problem into contextual-bandit decisions, encoding relational interaction structure to distinguish globally under-tested peers from peers under-tested for the current task context.This contextual representation provides finer-grained exploration through explicit algorithmic guidance.Source: §1 · p. 2

Contributions

  • MACE substantially outperforms existing baselines across contextual and capability diversity, with gains persisting during frozen-parameter exploitation and transfer to unseen benchmarks.In-context exploration prompting can underperform random peer selection, indicating that algorithmic structure—not prompting alone—is necessary.Source: §1 · p. 2
  • MACE achieves O(√Tlog T) cumulative regret, whereas greedy non-exploration incurs Ω(𝛿T), so exploration benefits grow without bound with capability diversity.The theory identifies agent specialization as the condition under which exploration becomes increasingly valuable.Source: §1 · p. 2

2. Can LLMs Explore in Multi-Agent Environments? A Motivating Example

A two-armed delegation task tests whether LLM agents can explore peers with unknown reliability rather than prematurely exploiting early evidence. Unlike UCB, which balances exploration and exploitation, the evaluated LLM agents frequently commit to one peer too early and fail to identify the better option reliably.

Motivation

  • The motivating problem is choosing which peers to trust under capability uncertainty, requiring agents to probe their environment for better collaborators and strategies.The delegation scenario isolates peer selection with unknown reliability as the core decision problem for reliable multi-agent autonomy.Source: §2 · p. 3

Setup

  • In the two-peer delegation setup, each observed success or failure informs whether to test the less-known peer or exploit the peer performing better so far.The task instantiates the exploration-exploitation dilemma through repeated delegations to two peers with unknown abilities.Source: §2 · p. 3
  • The bandit experiment assigns peers A and B fixed unknown accuracies of p_A=0.6 and p_B=0.5, making exploration necessary before exploiting the better peer.At each round, the agent observes historical performance and delegation counts; additional probability settings appear in Appendix A.2.Source: §2 · p. 3

Behavioral reference

  • UCB provides an algorithmic behavioral reference by selecting the peer with the highest optimistic success-rate estimate, thereby encouraging under-tested peers before exploitation.The comparison includes Qwen2.5-7B-Instruct (Yang et al., 2024), GPT-4 (Achiam et al., 2023), and GPT-5, all prompted using in-context histories.Source: §2 · p. 3

Results

  • LLM agents show polarized peer-selection behavior, unlike UCB’s effective exploration followed by exploitation of the better peer.Across 30 runs of 50 rounds, UCB concentrates on higher counts of selecting peer A, whereas all LLM agents produce bimodal distributions near 0 or 50 selections; Figure 1 shows the selection-count distributions.Source: §2 · pp. 3–4, Figure 1 · p. 4

3. The Multi-Agent Exploration Problem: A Formalization

The paper formalizes multi-agent exploration as a partially observable stochastic game in which heterogeneous agents probe peers to infer capabilities and choose effective interaction strategies. Agents must balance exploration of diverse peers against exploitation of expected rewards while minimizing regret over repeated rounds.

3.1. Problem Formalization

  • Multi-agent exploration involves N agents interacting over T timesteps to solve a sequence of tasks.Source: §3.1 · p. 4
  • Agents have heterogeneous but latent capabilities, so each must actively probe peers using partial interaction histories.Source: §3.1 · p. 4
  • The process is modeled as a Partially Observable Stochastic Game with latent states containing task information and unknown agent capabilities.Source: §3.1 · p. 5
  • At each round, every agent selects a peer, and joint decisions determine information propagation through a dynamically evolving interaction graph.Source: §3.1 · p. 5, Figure 2 · p. 5
  • Agents observe queried peers’ responses and accumulated histories rather than the full state, then receive rewards reflecting task performance or intermediate utility.Source: §3.1 · p. 5

3.2. Regret

  • Each agent should minimize cumulative regret relative to the best peer in hindsight over the interaction horizon.Source: §3.2 · p. 6
  • The central challenge is balancing exploration of diverse peers to reduce uncertainty and regret against exploitation of peers expected to yield high rewards.Source: §3.2 · p. 6

4. Multi-Agent Contextual Exploration (MACE)

MACE makes multi-agent exploration tractable by decomposing peer selection into independent contextual learning decisions. It combines relational features, uncertainty-driven exploration, and performance-based updates to avoid premature commitment among adaptive peers.

Contextual bandit formulation

  • MACE treats peer selection as an independent contextual bandit problem, adaptively choosing which peer to query from past observations and contextual signals.This decomposition avoids complex coordination protocols while addressing the NEXP-hard finite-horizon POSG formulation.Source: §4 · p. 6

Relational feature design

  • Relational features encode response diversity, peer distinctiveness, historical performance, and interaction round to represent information gain, network structure, exploitation, and time-varying exploration.The feature design captures non-stationary, relational peer behavior that scalar performance summaries may miss.Source: §4 · pp. 6–7

Exploration via optimism

  • MACE uses LinUCB’s uncertainty bonus over relational features, distinguishing peers under-tested globally from those under-tested in the current task context.This yields finer-grained exploration than scalar UCB by encouraging optimism in relationally specific situations.Source: §4 · p. 7

Sufficient statistic updates

  • After each interaction, MACE updates sufficient statistics using a reward averaging performance and response improvement after incorporating information from the selected peer.The reward therefore reflects both absolute task performance and the magnitude of improvement.Source: §4 · p. 7

5. Experiments

Experiments evaluate exploration under contextual and parametric heterogeneity, showing that LLM agents often explore poorly while MACE improves interaction quality, regret, downstream performance, and transfer to an unseen task. The evaluation compares MACE with in-context, random, and fixed-connectivity baselines across trial-and-error and exploitation phases.

5.1. Agent Heterogeneity Setup

  • The experiments model two complementary forms of heterogeneity: agents with different contextual information and agents with different intrinsic reasoning abilities.Contextual diversity uses 10 Qwen2.5-7B-Instruct agents over five discussion rounds on HotpotQA distractor contexts, while parametric diversity uses GPT-5, Qwen2.5-7B-Instruct, Llama3.1-8B-Instruct, and Mistral-7B-v0.3 over three rounds on Math500 and GPQA.Source: §5.1 · pp. 7–8

5.2. Experimental Details

  • Evaluation compares MACE with in-context, random, and pre-defined peer selection across trial-and-error and exploitation phases.HotpotQA uses hard samples with EM, F1, and regret, while parametric diversity uses Level 4–5 Math500 problems and GPQA’s Diamond split; datasets are split evenly between phases.Source: §5.2 · p. 8

5.3. Results and Diagnosis

  • In-context exploration produces poorly calibrated peer-selection concentration, whereas MACE distributes selections more broadly and supports more systematic exploration.Under contextual diversity, agents often lock onto a single peer despite randomized relevant context; under parametric diversity, GPT-5 selects Qwen-7B in 294 out of 297 interactions while rarely querying others.Source: §5.3 · pp. 8–9, Figure 3 · p. 9
  • MACE substantially outperforms all baselines across contextual and parametric diversity during both exploration and exploitation, while in-context exploration can perform worse than random selection.These gains hold on HotpotQA, Math500, and GPQA, and persist after MACE parameters are frozen for exploitation; even GPT-5 benefits from the proposed exploration mechanisms.Source: §5.3 · pp. 9–10, Figure 4 · p. 9
  • MACE transfers strategies learned on HotpotQA to unseen 2WikiMultihopQA and outperforms all baselines despite operating only in exploitation mode with frozen parameters.The transfer result suggests that the learned interaction strategies capture generalizable structure rather than task-specific artifacts.Source: §5.3 · p. 10, Figure 5 · p. 10

6. Theoretical Analysis

The theoretical analysis proves that MACE achieves sublinear regret while greedy non-exploration incurs linear regret, making exploration increasingly valuable as agent capability diversity grows. Empirical results further align with these theoretical predictions.

Capability Diversity

  • Capability diversity δ measures average deviation from the pool mean, with larger values indicating specialized agents and greater costs from selecting unsuitable peers.When δ ≈ 0, agents are approximately interchangeable and peer selection has limited performance impact; when δ ≫ 0, exploration becomes indispensable.Source: §6 · pp. 10–11

Regret Guarantees

  • MACE achieves sublinear cumulative regret with high probability under mild assumptions and exploration coefficient α > 0.This is established by Theorem 1 over T interaction rounds.Source: §6 · pp. 10–11
  • A greedy non-exploring policy incurs cumulative regret growing at least linearly, formalizing the cost of premature peer-selection commitment.The policy selects peers by maximizing estimated rewards without an exploration bonus.Source: §6 · pp. 10–11

Exploration Benefit

  • The exploration benefit scales as Ω(δT), because non-exploration has linear regret while MACE grows as √T log T.Here, δ denotes capability diversity; the comparison holds under the stated mild assumptions.Source: §6 · p. 11

Empirical Validation

  • Figure 6 compares the theoretical regret bounds and shows that Qwen2.5-7B-Instruct with MACE follows the predicted empirical trend.The left panel compares MACE’s upper bound with the lower bound for non-exploring policies, while the right panel tests the prediction empirically.Source: §6 · p. 11

7. Related Works

Related work spans autonomous multi-agent LLM architectures and the emerging study of LLM exploration. Existing systems provide coordination and autonomy mechanisms, while exploration research shows persistent limitations and highlights delegation, trust, and explicit algorithmic support as relevant factors.

7.1. Autonomous Multi-Agent LLM Systems

  • Recent overviews organize autonomous multi-agent LLM systems around agent profiling, communication structure, collaboration protocols, and system evolution.Source: §7.1 · pp. 11–12
  • Coordination frameworks support role-based orchestration, programmable interaction, dynamic networks, resource allocation, aggregation, and debate, but usually assume externally specified roles, rules, or capabilities.CAMEL (Li et al., 2023), AutoGen, ChatDev (Qian et al., 2024), MetaGPT (Hong et al., 2023), and related systems establish engineering foundations without learning whom to interact with from experience.Source: §7.1 · p. 12
  • Autonomy-focused work enables agents to communicate, design roles, assign sub-agents, orchestrate workflows, and solve domain-specific tasks autonomously.Examples include iAgents (Liu et al., 2024b), HALO (Hou et al., 2025), Puppeteer (Dang et al., 2025), MegaAgent (Wang et al., 2025), and AgentVerse (Chen et al., 2023).Source: §7.1 · pp. 12–13

7.2. LLM Exploration Capabilities

  • Single-agent studies find robust exploration rare, with premature decisions and inefficient exploration-exploitation tradeoffs, while algorithmic support, distillation, fine-tuning, and explicit PSRL can improve behavior.These findings span in-context bandits, open-ended exploration, standard multi-armed bandits, and quantifiable exploration-exploitation errors.Source: §7.2 · p. 13
  • Delegation research shows that effective partner selection requires assessing reliability and calibrating trust, because verbalized confidence may poorly reflect behavioral trustworthiness.Tomašev et al. (2026) frame delegation as adaptive task allocation and trust decisions, while Buyl et al. (2025) find self-reported trust weakly or negatively aligned with behavioral measures; Debnath et al. (2025) study fostering trust in dyads.Source: §7.2 · p. 13

8. Conclusion · Appendix · A. Appendix for the Delegation Experiment

The paper concludes that LLM agents often fail to explore effectively in multi-agent environments, motivating explicit exploration through MACE. Across diverse settings, MACE improves exploration and downstream performance, while theory shows that exploration becomes more valuable as agent diversity increases.

8. Conclusion

  • MACE improves exploration and downstream performance across diverse multi-agent settings, with gains transferring to unseen tasks.The framework explicitly induces exploration through structured peer selection.Source: §8 · p. 13
  • LLM agents often fail to explore effectively, causing premature commitment, poor peer selection, and higher regret.Source: §8 · p. 13
  • The paper formalizes ineffective peer probing as the Multi-Agent Exploration problem.Source: §8 · p. 13
  • MACE is presented as a lightweight framework that promotes exploration through structured peer selection.Source: §8 · p. 13
  • The theory shows that the value of exploration grows with agent diversity.Source: §8 · p. 13
  • Reliable multi-agent autonomy may require explicit exploration rather than relying on exploration to emerge spontaneously.Source: §8 · p. 13

A.1. Experimental Setup … C. Appendix for the Main Experiments

The experiments show that LLM delegation agents often collapse into polarized, near-deterministic peer choices, unlike UCB’s balanced exploration, while MACE uses relational features and blended rewards to guide adaptive interaction. The setup spans arithmetic delegation, contextual peer representations, task-aware rewards, and LinUCB-based updates.

A.1. Experimental Setup

  • Delegated questions are randomly generated integer arithmetic expressions, and each peer answers correctly with probability p_i.The tasks use addition, subtraction, and multiplication over integers in [1, 100].Source: §A.1 · p. 20
  • LLM delegation prompts expose peer histories and explicitly request balancing exploitation of accuracy against exploration of under-sampled peers in a constrained choice format.The history includes prior delegations, correct responses, and empirical success rates.Source: §A.1 · p. 20

A.2. Histograms for All 𝑝A Values

  • LLM agents overwhelmingly commit to one peer, producing selections near 0 or 50 even when p_A = p_B = 0.5, unlike UCB’s smooth allocations.Figure 7 compares p_A values from 0.1 to 0.9 with p_B fixed at 0.5; the full histogram comparison is reported across these settings.Source: §A.2 · p. 21, Figure 7 · p. 22
  • Qwen2.5-7B-Instruct sometimes allocates nearly all selections to inferior Peer A when p_A=0.1 and p_B=0.5, while GPT-5 explores somewhat more but remains far from UCB.The models’ failures are attributed to overreacting to noisy early outcomes and insufficient trial-and-error recovery.Source: §A.2 · p. 21
  • LLM selection-rate CDFs show sharp jumps near 0 and 1, whereas UCB increases smoothly with little mass at extremes across p_A settings and 30 runs.The CDF summarizes Peer A selection rates over p_A values 0.1 through 0.9.Source: §A.2 · p. 21, Figure 8 · p. 23

B.1. Feature Design

  • MACE represents each agent–peer interaction with normalized relational and utility features, including response diversity, peer distinctiveness, historical performance, interaction round, and a bias term.Response diversity uses n-gram similarity, while peer distinctiveness measures the peer’s share of population-wide response divergence.Source: §B.1 · pp. 21–24

B.2. Reward Function

  • MACE blends score improvement with absolute post-interaction quality so preserving an already-correct answer receives credit.Task scores use token-level F1 for question answering and binary exact match for multiple-choice and mathematical reasoning tasks.Source: §B.2 · p. 24

B.3. Algorithm

C.1. Dataset Details … D.2. Sensitivity Analysis of Exploration Coefficient 𝛼

The experiments span contextual and parametric agent diversity, transfer, round-wise performance, and exploration-coefficient sensitivity, using varied benchmarks, backbones, prompts, and computational resources. MACE improves performance across interaction rounds and transfers across tasks, while moderate exploration coefficients best balance exploration and exploitation.

C.1. Dataset Details

  • The evaluation covers contextual diversity with shared Qwen2.5-7B-Instruct agents and parametric diversity with heterogeneous model families, scales, and reasoning capabilities.Contextual agents receive different task-relevant contexts, while parametric agents use GPT-5, Qwen2.5-7B-Instruct, Llama3.1-8B-Instruct, and Mistral-7B-v0.3.Source: §C.1 · p. 25, §C.2 · pp. 26–27
  • Datasets include HotpotQA, Math500, GPQA, and 2WikiMultihopQA, with trial-and-error and exploitation phases used to evaluate learning, generalization, and parameter transfer.The settings use hard or expert-level examples, multiple interaction rounds, and Exact Match, token-level F1, or binary exact-match metrics.Source: §C.1 · pp. 25–26

C.2. Backbone Model Details

  • Contextual experiments use stochastic Qwen2.5-7B-Instruct agents, while parametric experiments assign one heterogeneous backbone per agent with specified decoding settings.Contextual runs use temperature 1.2 and top_p=0.95; parametric runs combine four model types with model-specific temperature and nucleus-sampling values.Source: §C.2 · pp. 26–27

C.3. Resources

  • Experiments run on one NVIDIA RTX A6000 GPU for contextual diversity and three NVIDIA RTX A6000 GPUs for parametric diversity, with GPT-5 accessed through Azure APIs.Source: §C.3 · p. 27

C.4. Prompt Templates

  • Prompted agents generate concise tagged answers, review their previous and selected peers’ responses, and select peers using histories containing rewards, diversity, centrality, and exploration features.Math500 and GPQA use dataset-specific answer formats; invalid peer selections fall back to the pre-defined neighboring-peer protocol.Source: §C.4 · pp. 27–29

D.1. Round-wise Performance

  • MACE consistently improves task performance across interaction rounds on HotpotQA, Math500, and GPQA, separating from all baselines and retaining gains during frozen-parameter exploitation.The learned policy converts additional communication into stronger performance, while In-Context Exploration often improves only marginally and can remain near or below Random.Source: §D.1 · p. 29, Figure 9 · p. 30
  • MACE also outperforms all baselines across rounds on 2WikiMultihopQA, showing that exploration learned on HotpotQA transfers to a different multi-hop question-answering environment.Parameters are transferred without further training, supporting a reusable exploration policy rather than source-benchmark overfitting.Source: §D.1 · p. 30, Figure 10 · p. 30

D.2. Sensitivity Analysis of Exploration Coefficient 𝛼

  • Intermediate exploration coefficients α=0.5 to α=1.0 achieve the strongest regret reduction, whereas α=0.1 behaves greedily and excessive α delays convergence through over-exploration.The coefficient controls LinUCB’s uncertainty bonus: weak exploration causes premature commitment to noisy peers, while excessive exploration continues prioritizing uncertain peers after evidence is sufficient.Source: §D.2 · p. 41, Figure 11 · p. 41

D.3. Experiments on Stronger LLMs … E.2. Proof of Theorem 1

Across stronger and homogeneous LLM pools, exploration’s regret benefits diminish as capability diversity shrinks, while MACE can retain downstream accuracy gains. MACE-TD models delayed interaction value and induces broader peer coverage, while feature analyses and the theoretical proof characterize its selection behavior and regret guarantee.

D.3. Experiments on Stronger LLMs

  • MACE achieves the best final-round mean accuracy on stronger models in both phases—0.7475 versus 0.7273 during Trial-and-Error and 0.7652 versus 0.7222 during Exploitation for In-Context Exploration—despite similar regret trends.These results indicate that structured exploration can improve information exchange and predictions even when strong agents have relatively homogeneous capabilities.Source: §D.3 · p. 42, Table 17 · p. 42

D.4. Fully Homogeneous Agent Setup

  • In the fully homogeneous Qwen2.5-7B-Instruct setup, MACE’s regret advantage is modest, but it still attains the best final-round mean accuracy: 0.4779 in Trial-and-Error and 0.5053 in Exploitation.As capability diversity approaches zero, regret benefits largely vanish while small coordination and prediction gains remain.Source: §D.4 · p. 43, Table 18 · p. 44

D.5. MACE-TD: A Temporal-Difference Extension

  • MACE-TD extends MACE to finite-horizon sequential peer selection by estimating delayed interaction value with temporal-difference targets while retaining optimistic uncertainty-based action selection.The extension uses interaction histories, reward observations, and γ = 0.9 to account for early queries that improve later information states.Source: §D.5 · pp. 43–44
  • MACE-TD does not consistently improve cumulative regret: it is broadly comparable to MACE on HotpotQA and Math500 but accumulates noticeably higher regret on GPQA.Despite this GPQA regret disadvantage, its multi-round performance is similar to or slightly better than MACE, whereas HotpotQA shows lower exploration-phase F1.Source: §D.5 · pp. 44–45, Figure 15 · p. 45, Figure 16 · p. 46
  • MACE-TD produces sharper peer-selection distributions and higher peer-selection coverage than In-Context Exploration, consistent with specialization across peer subsets and broader collective information flow.The evidence suggests, but does not establish, that sequential credit assignment encourages interaction structures favorable to information sharing.Source: §D.5 · pp. 44–46, Figure 14 · p. 45, Figure 17 · p. 46

D.6. Feature Importance

  • MACE assigns positive weights to n-gram diversity features, favoring peers whose responses differ, while distinctiveness features matter near-zero in contextual diversity but more under parametric diversity.Response disagreement can signal complementary information, but distinctiveness is less reliable when differences primarily reflect access to different contexts.Source: §D.6 · p. 47, Figure 18 · p. 47

E.1. Assumptions

  • The theoretical analysis assumes bounded contextual features and parameters, sub-Gaussian reward noise, and capability diversity that lower-bounds the expected penalty for selecting a suboptimal peer.The final assumption formalizes that selecting the wrong peer is more costly when agents are specialized and task requirements align differently with peer capabilities.Source: §E.1 · p. 48

E.2. Proof of Theorem 1

  • Under these assumptions, confidence-set concentration, the UCB rule, and the elliptical potential lemma yield the cumulative-regret bound stated in Theorem 1.The proof derives instantaneous regret from the confidence radius, sums over T rounds and N peers, and concludes the theorem.Source: §E.2 · pp. 49–50

E.3. Proof of Theorem 2 · Regret𝑖=∑︁Δ𝑖,𝑎𝑁𝑖,𝑎, · E.4. Discussion

Theorem 1 establishes sublinear regret for MACE, whereas a greedy non-exploring policy can incur linear regret after prematurely committing to a suboptimal peer. The value of explicit exploration increases with capability diversity because peer-selection mistakes become more consequential.

E.3. Proof of Theorem 2

  • Theorem 2 constructs a stochastic instance where noisy finite observations initially rank a suboptimal peer above the optimal peer with probability at least ρ > 0.This establishes a constant-probability event on which the greedy policy begins with an incorrect ranking.Source: §E.3 · p. 50
  • Without explicit exploration, greedy selection gathers no corrective observations from the optimal peer, so the initial misranking persists across all T rounds.The policy consequently continues selecting the suboptimal peer throughout the horizon.Source: §E.3 · p. 50

Regret𝑖=∑︁Δ𝑖,𝑎𝑁𝑖,𝑎,

  • Using the standard regret decomposition, the persistent selection of the suboptimal peer yields a linear regret bound with constant probability.The proof concludes that non-exploration can incur regret growing linearly in the interaction horizon.Source: §E.3 · p. 50, Regret𝑖=∑︁Δ𝑖,𝑎𝑁𝑖,𝑎 · p. 50

E.4. Discussion

  • MACE achieves sublinear regret, while greedy non-exploration can produce linear regret in T after premature commitment to a suboptimal peer.The average regret per round therefore vanishes for MACE as T grows, unlike the greedy policy.Source: §E.4 · p. 51
  • When capability diversity δ is near zero, peers are nearly interchangeable, making wrong-peer selection inexpensive and explicit exploration less beneficial.In this low-diversity regime, the cost of selecting the wrong peer is small.Source: §E.4 · p. 51
  • As δ becomes large, agents specialize and peer selection becomes consequential, increasing the regret gap between exploring and non-exploring policies.The discussion attributes this gap to the greater cost of selecting an unsuitable peer in a diverse agent pool.Source: §E.4 · p. 51
  • The regret analysis shows that the value of exploration increases directly with the diversity of the agent pool.This conclusion follows from the diversity-dependent regret gap described by Corollary 1.Source: §E.4 · p. 51

F. Limitations and Future Directions · G. Broader Impact

The paper’s evaluation is limited to small- and medium-scale systems, motivating scalable MACE variants for massive populations. It also frames socially reliable multi-agent AI as requiring both beneficial coordination and safeguards against emerging collective risks.

F. Limitations and Future Directions

  • MACE has not yet been empirically evaluated in very large populations with hundreds or thousands of agents.Such deployments include digital workforces, distributed tool ecosystems, robotic fleets, and open agent platforms.Source: F. Limitations and Future Directions · p. 51
  • Large agent populations may make exploration more critical because useful collaborators can be rare, specialized, or dynamically changing, while poor routing can propagate inefficiency.Source: F. Limitations and Future Directions · p. 51
  • Scaling to large N introduces communication bottlenecks, delayed or partial feedback, expanding interaction spaces, and stronger non-stationarity from simultaneous updates.Future work should investigate scalable MACE variants and whether explicit exploration produces specialization, robust collective behavior, and self-organizing coordination.Source: F. Limitations and Future Directions · p. 51

G. Broader Impact

  • Reliable multi-agent AI must integrate agents that communicate, delegate, negotiate, and coordinate within broader human social and organizational environments.The paper identifies insufficient exploration of peers and interaction strategies as a fundamental obstacle to reliable multi-agent autonomy.Source: G. Broader Impact · p. 51
  • Improved partner discovery, adaptation, and communication allocation could support scientific collaboration, digital workforces, education, healthcare coordination, public-service decision support, and mixed human-AI teams.Source: G. Broader Impact · pp. 51–52
  • Stronger autonomous coordination may enable scalable manipulation, collusion, disinformation, and opaque collective behavior, requiring controllable protocols, fairness-aware objectives, governance, safety mechanisms, and human oversight.These safeguards are especially important in high-stakes settings as multi-agent capabilities improve.Source: G. Broader Impact · p. 52
  • The work broadens AI reliability from individual models to trustworthy societies of interacting models embedded in real-world social environments.Source: G. Broader Impact · p. 52

Related papers

Loading 2607.11250v1…