Hyeong Kyu Choi, Jiatong Li, Wendi Li, Xin Eric Wang, Sharon Li
4 min
Reliable autonomy in multi-agent systems requires agents to proactively explore their peers to identify effective collaborators and uncover complementary information. While exploration is a foundational concept in reinforcement learning, this paper investigates whether modern Large Language Models (LLMs) possess an innate ability to balance exploration and exploitation when interacting with other agents. The authors find that even highly capable models, such as GPT-4 and GPT-5, fail to explore effectively, often locking onto a single peer early in the interaction process and persisting with that choice even when it is suboptimal.
The authors formalize this challenge as a Multi-Agent Exploration problem, modeled as a Partially Observable Stochastic Game (POSG). In this setting, agents must navigate uncertainty regarding the latent capabilities of their peers. Because agents operate in a decentralized manner and possess only partial, evolving information, the failure to explore leads to polarized interaction patterns and increased cumulative regret. The authors demonstrate that this is a structural limitation of current LLM agents rather than a simple capacity deficit, as even advanced models fail to converge to optimal peer selection in controlled bandit experiments.
To address this, the authors introduce Multi-Agent Contextual Exploration (MACE), a lightweight framework that decomposes the complex joint problem into independent, per-agent decision-making tasks. MACE utilizes a contextual bandit approach where peer selection is guided by relational features—such as response diversity and peer distinctiveness—rather than raw selection counts. By incorporating an uncertainty bonus (based on the LinUCB algorithm), MACE explicitly incentivizes agents to query under-tested peers within specific relational contexts. Empirical results show that MACE consistently outperforms standard prompting strategies and random peer selection across both contextual and parametric diversity settings.
As LLMs are increasingly deployed in decentralized, heterogeneous multi-agent systems, the ability to autonomously discover effective collaboration strategies becomes critical. This paper highlights that current agents lack the algorithmic structure necessary for reliable exploration, suggesting that future multi-agent architectures must incorporate explicit mechanisms for guided exploration to achieve robust, autonomous coordination.
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
Alex: So the failure isn't a lack of intelligence—it's a lack of curiosity.
Sam: That's a good way to put it. The agents have what the paper calls "latent capabilities"—hidden strengths that never get discovered because no one tests them. MACE builds in the curiosity that the agents lack on their own.
Alex: Did it actually make a measurable difference?
Sam: The results were significant. MACE outperformed standard approaches across every test the researchers ran. And one pattern stood out: the more specialized and diverse the team, the bigger the advantage. When agents have very different strengths, the cost of not exploring properly is much higher—because the gap between a mediocre match and the right match is much wider. MACE is designed precisely for that situation.
Alex: So the benefit scales with how different the agents are from each other.
Sam: Exactly. A team of identical agents doesn't need much exploration—any partner will do. But a team where each agent has a distinct specialty? You need to actively search to find the right fit. That's where structured exploration earns its keep.
Alex: It sounds like MACE is essentially teaching the system to be a better team player over time.
Sam: In a sense, yes. By treating peer selection as a series of decisions rather than a single choice, agents learn to value the information they gain from trying new things. It turns a group of isolated models into something more like a cohesive, cooperative team. And the study suggests that for multi-agent systems to reach their potential, this kind of structured exploration has to be built directly into the math—not bolted on afterward as an instruction.
Alex: Curiosity, it turns out, is a measurable, mathematical advantage.
Sam: That's exactly the takeaway. Thanks for listening to ResearchPod.