Research map / Multi-agent systems and games / LLM agents
Strategist: Self-improvement of LLM Decision Making via Bi-Level Tree Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes STRATEGIST, a bi-level framework where an LLM evolves high-level strategies (as Python value heuristics or dialogue guides) via population-based self-play, refined at low level by MCTS, and evaluated on GOPS and The Resistance: Avalon.
Problem
LLM agents struggle to learn effective policies in adversarial, multi-agent, partial-information games requiring long-horizon planning, and data- or training-heavy RL is costly.
Approach
Use an LLM to generate and revise high-level strategies (value heuristics as code, or chain-of-thought dialogue guides) organized in a strategy tree with an idea queue sampled by UCB, scored by population-based self-play with MCTS refinement at inference time, requiring no training data or gradient updates.
Key results
- On GOPS, STRATEGIST's value heuristic reached 1.5 points average advantage versus -0.47 to 0.092 for line search, greedy search and BFS baselines (Table 2).
- Against AlphaGo-style RL with a similar number of self-play episodes, STRATEGIST achieved 0.38 Avalon win rate vs 0.30 for AlphaGo, and 1.14 vs -0.56 point difference vs DeepRole on GOPS.
- In six-player Avalon vs ten human participants, STRATEGIST achieved a 0.333 win rate compared with 0.367 for humans.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Strategist instead of the human player | Avalon agents · Avalon vs human | win rate: 0.367 -> 0.333 | No clear effect |
| Use idea-queue-guided strategy improvement instead of BFS with thought | LLM strategy improvement · GOPS | point difference: -0.48 ± 0.375 -> 1.5 ± 0.99 | Helped |
| Use idea-queue-guided strategy improvement instead of BFS with thought | LLM strategy improvement · Avalon | win rate: 0.55 ± 0.065 -> 0.59 ± 0.11 | Helped |
| Use idea-queue-guided strategy improvement instead of the strongest listed baseline | LLM strategy improvement · Merlin dialogue guide | improvement score: 0.62 ± 0.13 -> 0.88 ± 0.063 | Helped |
| Use idea-queue-guided strategy improvement instead of BFS with thought | LLM strategy improvement · Assassin dialogue guide | improvement score: 1.89 ± 0.063 -> 1.98 ± 0.042 | Helped |
| Use Strategist instead of AlphaGo | GOPS agents · GOPS vs AlphaGo | point difference: -0.39 ± 0.22 -> 0.33 ± 0.38 | Helped |
| Use Strategist instead of DeepRole | GOPS agents · GOPS vs DeepRole | point difference: -0.56 ± 0.18 -> 1.14 ± 0.09 | Helped |
| Use Strategist instead of AlphaGo | Avalon agents · Avalon vs AlphaGo | win rate: 0.30 ± 0.03 -> 0.38 ± 0.04 | Helped |
| Use Strategist instead of DeepRole | Avalon agents · Avalon vs DeepRole | win rate: 0.33 ± 0.04 -> 0.44 ± 0.02 | Helped |
| Use population-based self-play instead of fixed-opponent feedback | Strategist feedback collection · GOPS | point difference: 0.089 ± 0.86 -> 0.87 ± 1.5 | Helped |
| Use population-based self-play instead of fixed-opponent feedback | Strategist feedback collection · Avalon | win rate: 0.62 ± 0.13 -> 0.88 ± 0.06 | Helped |
| Use Strategist instead of ReAct | Avalon agents · Avalon vs ReAct | win rate: 47.5 ± 2.5 -> 52.5 ± 2.5 | Helped |
Surprising findings
- STRATEGIST uses only about 100 transition steps for training versus roughly 3,840 for RL baselines on GOPS, while outperforming them.
- Against ReCon, STRATEGIST's learned strategies were roughly comparable in performance, with win rates of 61.1 vs 38.9 reported in the table.
Limitations
- High variance across runs due to noisy multi-agent feedback that grows with player count.
- Only tested on adversarial multi-agent games; not evaluated on question answering or non-adversarial settings.
- Avalon improvement requires separate optimization of dialogue and move components before integration.
Experimental setup
Datasets: GOPS self-play simulations Avalon self-play simulations
Benchmarks: GOPS The Resistance: Avalon
Metrics: point difference win rate
Baselines: AlphaGo DeepRole ReAct ReCon Line search Greedy search Best first search LLM-critic
Builds on: AlphaGo MuZero DeepRole ReAct ReCon
Closest papers by meaning
- Strat-Reasoner: Reinforcing Strategic Reasoning of LLMs in Multi-Agent Games (ICML 2026 · similarity 0.89)
- Monte Carlo Planning with Large Language Model for Text-Based Game Agents (ICLR 2025 · similarity 0.89)
- TowerMind: A Tower Defence Game Learning Environment and Benchmark for LLM as Agents (AAAI 2026 · similarity 0.88)
- MARSHAL: Incentivizing Multi-Agent Reasoning via Self-Play with Strategic LLMs (ICLR 2026 · similarity 0.88)
- Expanding LLM Agent Boundaries with Strategy-Guided Exploration (NeurIPS 2026 · similarity 0.88)
- StraTA: Incentivizing Agentic Reinforcement Learning with Strategic Trajectory Abstraction (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.