Multi-Agent LLMs Fail to Explore Each Other

Abstract 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.

Introduction. Large language models are increasingly deployed not only as isolated assistants, but as autonomous agents embedded in multi-agent systems: communicating, delegating, and making decisions in a decentralized fashion to accomplish complex tasks (Du et al., 2024; Gao et al., 2024; Hong et al., 2023; Li et al., 2023; Qian et al., 2024; Wu et al., 2024). This paradigm is rapidly expanding: open-world platforms now instantiate heterogeneous agent populations that interact autonomously to discuss problems, divide labor, and collectively reason toward shared goals (Jiang et al., 2026; Park et al., 2023; Piao et al., 2025; Zhang et al., 2026). Such systems implicitly rely on the assumption that agents are capable of autonomous decision-making, and that meaningful collective behavior can emerge from agent-to-agent interactions. But what is required for agents to act autonomously in a reliable manner? A large body of literature in intrinsic motivation and reinforcement learning has demonstrated that exploration is foundational to autonomous behavior (Burda et al., 2019; Pathak et al., 2017).

Discussion / Conclusion. In this work, we showed that LLM agents often fail to explore effectively in multi-agent environments, leading to premature commitment, poor peer selection, and higher regret. We formalized this as the Multi-Agent Exploration problem and introduced Multi-Agent Contextual Exploration (MACE), a lightweight framework that explicitly induces exploration through structured peer selection. Across diverse settings, MACE improves both exploration and downstream performance, with gains that transfer to unseen tasks. Our theory further shows that the value of exploration grows with agent diversity. Overall, reliable multi-agent autonomy may require explicit exploration rather than expecting it to emerge on its own.