# Strategist: Self-improvement of LLM Decision Making via Bi-Level Tree Search

arXiv: https://arxiv.org/abs/2408.10635 · HTML: https://mlsanity.com/paper/2408.10635/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in Self-play RL for reasoning, one of 13 directions in Synthetic data and self-improvement for LLMs.
- Builds on 25 of its 53 references that are in the map.
- First posted on arXiv 20 Aug 2024.

## Placed in

- Synthetic data and self-improvement for LLMs / [Self-play RL for reasoning](https://mlsanity.com/synth/self-play-rl-for-reasoning/)

## Builds on (most cited first, 25 of 25)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [FEVER: a large-scale dataset for Fact Extraction and VERification](https://mlsanity.com/paper/1803.05355/) (2018)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Eureka: Human-Level Reward Design via Coding Large Language Models](https://mlsanity.com/paper/2310.12931/) (2023)
- [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (2022)
- [Language to Rewards for Robotic Skill Synthesis](https://mlsanity.com/paper/2306.08647/) (2023)
- [Exploring Large Language Models for Communication Games: An Empirical Study on Werewolf](https://mlsanity.com/paper/2309.04658/) (2023)
- [Improving Language Model Negotiation with Self-Play and In-Context Learning from AI Feedback](https://mlsanity.com/paper/2305.10142/) (2023)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [Language Agents with Reinforcement Learning for Strategic Play in the Werewolf Game](https://mlsanity.com/paper/2310.18940/) (2023)
- [Avalon's Game of Thoughts: Battle Against Deception through Recursive Contemplation](https://mlsanity.com/paper/2310.01320/) (2023)
- [Cooperation, Competition, and Maliciousness: LLM-Stakeholders Interactive Negotiation](https://mlsanity.com/paper/2309.17234/) (2023)
- [Agent-Pro: Learning to Evolve via Policy-Level Reflection and Optimization](https://mlsanity.com/paper/2402.17574/) (2024)
- [KoLA: Carefully Benchmarking World Knowledge of Large Language Models](https://mlsanity.com/paper/2306.09296/) (2023)
- [Self-playing Adversarial Language Game Enhances LLM Reasoning](https://mlsanity.com/paper/2404.10642/) (2024)
- [AvalonBench: Evaluating LLMs Playing the Game of Avalon](https://mlsanity.com/paper/2310.05036/) (2023)
- [Enhance Reasoning for Large Language Models in the Game Werewolf](https://mlsanity.com/paper/2402.02330/) (2024)
- [Werewolf Arena: A Case Study in LLM Evaluation via Social Deduction](https://mlsanity.com/paper/2407.13943/) (2024)
- [Skill Set Optimization: Reinforcing Language Model Behavior via Transferable Skills](https://mlsanity.com/paper/2402.03244/) (2024)

## Built on by (most cited first, 17 of 17)

- [Agent-R: Training Language Model Agents to Reflect via Iterative Self-Training](https://mlsanity.com/paper/2501.11425/) (2025)
- [A Survey on Large Language Model-Based Social Agents in Game-Theoretic Scenarios](https://mlsanity.com/paper/2412.03920/) (2024)
- [Planning without Search: Refining Frontier LLMs with Offline Goal-Conditioned RL](https://mlsanity.com/paper/2505.18098/) (2025)
- [DISC: Dynamic Decomposition Improves LLM Inference Scaling](https://mlsanity.com/paper/2502.16706/) (2025)
- [Actor-Curator: Co-adaptive Curriculum Learning via Policy-Improvement Bandits for RL Post-Training](https://mlsanity.com/paper/2602.20532/) (2026)
- [ReflecSched: Solving Dynamic Flexible Job-Shop Scheduling via LLM-Powered Hierarchical Reflection](https://mlsanity.com/paper/2508.01724/) (2025)
- [Cardiverse: Harnessing LLMs for Novel Card Game Prototyping](https://mlsanity.com/paper/2502.07128/) (2025)
- [The Stackelberg Speaker: Optimizing Persuasive Communication in Social Deduction Games](https://mlsanity.com/paper/2510.09087/) (2025)
- [Random Policy Enables In-Context Reinforcement Learning within Trust Horizons](https://mlsanity.com/paper/2410.19982/) (2024)
- [Shall We Play a Game? Language Models for Open-ended Wargames](https://mlsanity.com/paper/2509.17192/) (2025)
- [Constraints-of-Thought: A Framework for Constrained Reasoning in Language-Model-Guided Search](https://mlsanity.com/paper/2510.08992/) (2025)
- [Harness as a Language: A Minimalist Agent Framework With Maximal Expressivity](https://mlsanity.com/paper/2609.26891/) (2026)
- [Agentmandering: A Game-Theoretic Framework for Fair Redistricting via Large Language Model Agents](https://mlsanity.com/paper/2511.04076/) (2025)
- [Avalon-ToM-Bench: Evaluating Fine-Grained Theory of Mind via Asymmetric Game Mechanics](https://mlsanity.com/paper/2608.09638/) (2026)
- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)
- [SAGE: Structured Strategic Reasoning for Efficient LLM Game Playing](https://mlsanity.com/paper/2609.34342/) (2026)
- [Shockingly Simple Self-retrospection Improves Agentic Models Without RL](https://mlsanity.com/paper/2609.35741/) (2026)

## Abstract (arXiv)

Traditional reinforcement learning and planning typically requires vast amounts of data and training to develop effective policies. In contrast, large language models (LLMs) exhibit strong generalization and zero-shot capabilities, but struggle with tasks that require detailed planning and decision-making in complex action spaces. We introduce STRATEGIST, a novel approach that integrates the strengths of both methods. Our approach leverages LLMs to search and update high-level strategies (as text), which are then refined and executed by low-level Monte Carlo Tree Search (MCTS). STRATEGIST is a generalizable framework to optimize the strategy through population-based self-play simulations without the need for any training data. We demonstrate the effectiveness of STRATEGIST in learning optimal strategies for competitive, multi-turn games with partial information, including Game of Pure Strategy (GOPS) and multi-agent, hidden-identity discussion games like The Resistance: Avalon. Our results show that agents equipped with STRATEGIST outperform those trained with traditional RL methods, other LLM-based skill acquisition techniques, pre-existing LLM agents across both game environments and achieves comparable performance against human players.