# Stop Wandering, Find the Keys: LLMs Discriminate Key States for Efficient Multi-Agent Exploration

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 49 of its 78 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 30 of 49)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Eureka: Human-Level Reward Design via Coding Large Language Models](https://mlsanity.com/paper/2310.12931/) (2023)
- [Chain-of-Verification Reduces Hallucination in Large Language Models](https://mlsanity.com/paper/2309.11495/) (2023)
- [Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?](https://mlsanity.com/paper/2011.09533/) (2020)
- [Ghost in the Minecraft: Generally Capable Agents for Open-World Environments via Large Language Models with Text-based Knowledge and Memory](https://mlsanity.com/paper/2305.17144/) (2023)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Reward Design with Language Models](https://mlsanity.com/paper/2303.00001/) (2023)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Grounding Large Language Models in Interactive Environments with Online Reinforcement Learning](https://mlsanity.com/paper/2302.02662/) (2023)
- [Guiding Pretraining in Reinforcement Learning with Large Language Models](https://mlsanity.com/paper/2302.06692/) (2023)
- [Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11251/) (2021)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Survey on Large Language Model-Enhanced Reinforcement Learning: Concept, Taxonomy, and Methods](https://mlsanity.com/paper/2404.00282/) (2024)
- [State Entropy Maximization with Random Encoders for Efficient Exploration](https://mlsanity.com/paper/2102.09430/) (2021)

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

- [EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration](https://mlsanity.com/paper/2410.06238/) (2024)
- [Latent Reward: LLM-Empowered Credit Assignment in Episodic Reinforcement Learning](https://mlsanity.com/paper/2412.11120/) (2024)
- [Doubly Mild Generalization for Offline Reinforcement Learning](https://mlsanity.com/paper/2411.07934/) (2024)
- [Offline Reinforcement Learning with OOD State Correction and OOD Action Suppression](https://mlsanity.com/paper/2410.19400/) (2024)
- [Small Generalizable Prompt Predictive Models Can Steer Efficient RL Post-Training of Large Reasoning Models](https://mlsanity.com/paper/2602.01970/) (2026)
- [Fast and Robust: Task Sampling with Posterior and Diversity Synergies for Adaptive Decision-Makers in Randomized Environments](https://mlsanity.com/paper/2504.19139/) (2025)
- [Fly-CL: A Fly-Inspired Framework for Enhancing Efficient Decorrelation and Reduced Training Time in Pre-trained Model-based Continual Representation Learning](https://mlsanity.com/paper/2510.16877/) (2025)
- [Curriculum-Based Multi-Tier Semantic Exploration via Deep Reinforcement Learning](https://mlsanity.com/paper/2509.09356/) (2025)
- [MIRA: Memory-Integrated Reinforcement Learning Agent with Limited LLM Guidance](https://mlsanity.com/paper/2602.17930/) (2026)

## Abstract (arXiv)

With expansive state-action spaces, efficient multi-agent exploration remains a longstanding challenge in reinforcement learning. Although pursuing novelty, diversity, or uncertainty attracts increasing attention, redundant efforts brought by exploration without proper guidance choices poses a practical issue for the community. This paper introduces a systematic approach, termed LEMAE, choosing to channel informative task-relevant guidance from a knowledgeable Large Language Model (LLM) for Efficient Multi-Agent Exploration. Specifically, we ground linguistic knowledge from LLM into symbolic key states, that are critical for task fulfillment, in a discriminative manner at low LLM inference costs. To unleash the power of key states, we design Subspace-based Hindsight Intrinsic Reward (SHIR) to guide agents toward key states by increasing reward density. Additionally, we build the Key State Memory Tree (KSMT) to track transitions between key states in a specific task for organized exploration. Benefiting from diminishing redundant explorations, LEMAE outperforms existing SOTA approaches on the challenging benchmarks (e.g., SMAC and MPE) by a large margin, achieving a 10x acceleration in certain scenarios.