Evolving in the Agent Jungle via History-Informed Opponent Awareness

Zhaofeng Zhang, Linhan Xia, Rui Liu, Yihao Wang, Binrui Shen, Shengxin ZhuarXiv 2026 · arXiv

TL;DR

When multiple LLM agents adapt simultaneously in a shared environment, they face a "moving target" problem where an opponent's shifting strategy can make good skill revisions look bad, and vice versa. To solve this, the authors introduce OASE (Opponent-Aware Selective Evolution), a framework that anchors agent evaluation using historical opponent snapshots and paired counterfactual rollouts. This evidence-gated approach drastically reduces harmful strategy drift, allowing LLM agents to adapt stably and efficiently in competitive multi-agent games.

What Problem Does This Paper Address?

In single-agent settings, LLM agents can easily optimize their prompts or "skill libraries" because the environment remains static. However, in multi-agent strategic environments—like markets or auctions—the environment is largely defined by the other agents.

When all agents attempt to learn and revise their skills at the same time, it creates a revision-level credit assignment problem. If an agent changes its strategy and its payoff drops, is it because the new strategy is inherently worse, or because the opponents simultaneously grew stronger? Standard LLM self-reflection methods (like Reflexion) update blindly based on raw trajectory feedback from the latest round. This often leads to agents chasing transient opponent configurations or reacting to environmental randomness, causing chaotic strategy churn and drift away from game-theoretic equilibria.

Figure 1: An example of the four-agent first-price sealed-bid auction. Each agent i privately observes a valuation vi and submits a sealed bid bi. The highest bidder wins, pays its own bid, and receives utility ui = (vi −bi)1{i wins}. Because each agent’s payoff depends on the bids of the other agents, those agents form part of its effective environment.

Methods

The authors propose OASE (Opponent-Aware Selective Evolution), which treats any proposed skill library modification as a hypothesis that must pass a strict, controlled evaluation before being adopted.

The OASE workflow operates in three distinct stages within each generation:

  1. Proposal: An editor LLM suggests a set of local modifications (ADD, EDIT, or DELETE operations) to an agent's current text-based skill library.
  2. Paired Counterfactual Evaluation: Instead of testing candidates against the volatile, live population, OASE evaluates them against a frozen distribution of historical opponent snapshots. Crucially, it uses Common Random Numbers (CRN): the candidate library and the current incumbent library are tested under identical conditions—sharing the exact same opponent snapshot and environmental random seed.
  3. Selective Replacement: A candidate is only adopted if its estimated payoff improvement over the incumbent exceeds a predefined acceptance threshold ($\delta$). If multiple candidates qualify, they are ranked using a diversity-aware score based on textual novelty to prevent redundant strategy profiles.
Overview of the OASE framework, detailing the proposal, paired counterfactual evaluation, and gated replacement steps.

Datasets

The framework was evaluated using two classic game-theoretic economic simulations that provide clear analytical benchmarks:

  • First-Price Sealed-Bid Auction: A 4-agent environment where risk-neutral bidders receive private valuations and must submit hidden bids.
  • Private-Cost Cournot Competition: A continuous-action market simulation where 4 firms simultaneously decide on production quantities based on their private marginal costs.

No new external datasets were introduced, as the focus was on measuring how closely the text-driven agent behaviors aligned with known mathematical Bayesian Nash Equilibria (BNE).

Key Insights and Ideas

  • Revisions as Hypotheses: Moving away from the assumption that LLM self-reflections are inherently beneficial, OASE treats edits as unverified hypotheses. If the data doesn't support the change, the agent safely retains its incumbent skills.
  • Stabilizing the Target via History: Drawing inspiration from classical game theory concepts like Fictitious Play and Policy Space Response Oracles (PSRO), OASE creates a temporarily stable evaluation reference by mixing historical opponent profiles. This prevents agents from overfitting to an opponent's most recent, potentially transient strategy.
  • Isolating Noise with Paired Testing: By enforcing identical random seeds and opponent states for both the candidate and incumbent, OASE effectively isolates the true performance delta of a textual change from environmental luck.

Key Results

  • Closer Equilibrium Alignment: In first-price auctions, OASE successfully kept agents within a tight neighborhood of the optimal Bayesian Nash Equilibrium. Conversely, the Reflexion baseline drifted significantly. Ultimately, OASE achieved a 2.3× lower final equilibrium distance than Reflexion.
Equilibrium distance over generations, demonstrating OASE's stability compared to Reflexion's upward drift.
  • Suppressed Strategy Churn: OASE accepted significantly fewer updates (~0.75 edits per generation across the 4-agent population) compared to Reflexion, which blindly updated nearly every agent every generation (~4.0 edits). This confirms that filtering out unsupported edits prevents harmful strategy drift.
  • 50% Variance Reduction: The paired CRN evaluation design cut the estimator variance by 49.7% compared to an unpaired approach, proving that shared randomness provides a much cleaner learning signal.

Limitations and Future Work

  • Local Search Constraints: OASE optimizes within a local textual neighborhood generated by an editor LLM. It cannot guarantee a globally optimal best response if the editor fails to propose it.
  • Computational Overhead: Running paired simulations ($m=64$ rollouts per candidate) against historical archives increases the computational and token budget required during the evaluation phase.
  • Ablation Isolation: While lower update churn strongly correlated with better equilibrium tracking, the authors note that future work should include more controlled isolation studies to fully decouple the impacts of the acceptance gate from the historical sampling distribution.

Summary updated

Abstract

Learning to adapt strategies through interaction is a key step toward more general and autonomous LLM agents. Existing approaches typically achieve behavioral adaptation by revising skill libraries. However, in multi-agent environments, opponents may simultaneously update their strategies, causing the environment itself to evolve continuously. Applying skill-revision methods designed for static environments in such settings therefore amounts to updating against an obsolete reference. To address this challenge, we introduce OASE (Opponent-Aware Selective Evolution), which identifies and adopts genuinely beneficial skill revisions in dynamic multi-agent environments. Specifically, OASE conducts paired comparisons between a candidate skill and the incumbent under identical conditions anchored by historical snapshots of opponent strategies, and adopts the candidate only when its estimated payoff gain exceeds an acceptance threshold. We evaluate OASE in two decision-making scenarios: first-price auctions and private-cost Cournot competition. Experimental results show that, compared with a Reflexion-style baseline, OASE achieves a lower final equilibrium distance in both environments while accepting substantially fewer skill revisions, thereby suppressing strategy changes that lack sufficient payoff support. OASE therefore replaces blind updating with evidence-anchored selection, allowing agents to adapt stably and efficiently even as opponents continuously evolve.
BibTeX
@misc{zhang2026evolving,
  author = {Zhaofeng Zhang and Linhan Xia and Rui Liu and Yihao Wang and Binrui Shen and Shengxin Zhu},
  title = {{Evolving in the Agent Jungle via History-Informed Opponent Awareness}},
  year = {2026},
  eprint = {2608.02005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.02005},
}
Figure