Research map / Multi-agent systems and games / LLM agents
Do LLM Agents Have Regret? A Case Study in Online Learning and Games
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.
Empirically tests whether LLM agents (GPT-4, GPT-4 Turbo, GPT-4o, GPT-3.5) are no-regret in online learning and repeated games, gives a hypothetical quantal-response explanation, and proposes an unsupervised regret-loss that trains transformers toward no-regret (FTRL-like) behavior.
Problem
Whether LLM agents achieve sublinear regret in online learning and multi-agent repeated games, which has not been quantitatively characterized, and how to promote no-regret behavior without optimal-action labels.
Approach
Measure LLM regret directly in non-stochastic online learning and repeated games with finite-horizon statistical trend tests and log-log regression; explain the behavior via a pre-training model yielding quantal response (FTPL-like); and train transformers with an unsupervised max-regret surrogate loss (regret-loss) that provably yields FTRL when using single-layer linear self-attention.
Key results
- GPT-4o on T=500 randomly generated uniform losses gives regression slope 0.85 (p=0.0), compared with 0.6 for FTRL and 0.52 for FTPL, indicating sublinear regret for GPT-4o but a slope above FTRL/FTPL.
- On the adaptive loss sequence and the FTL counterexample variants, GPT-4 and GPT-4 Turbo cannot be rejected as having linear regret.
- Regret-loss trained single-layer linear self-attention is shown theoretically to recover FTRL with L2 regularizer under diagonal covariance; experiments show trained transformers match FTRL and GPT-4 on random losses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GPT-4o on uniform, Gaussian, linear-trend, and sine-trend loss sequences through T=500 | GPT-4o · Online learning, T=500 | regret exponent: 0.85, 0.86, 0.83, 0.28 | Helped |
| Replace raw history with summarized history (ablation) | GPT-4 on the second canonical FTL counterexample · Adversarial loss sequence, T=500 | regret | Hurt |
| Train a Transformer using regret-loss instead of relying on the pre-trained GPT-4 | Transformer online learner · Noisy alternating and adaptive loss sequences | regret | Helped |
| Add re-weighting to GPT-4o's bandit input | GPT-4o · Hard MAB instance, T=100 | SuffFailFreq(T/2): $0.2$ -> $0.00$ | Helped |
| Add re-weighting to GPT-4's bandit input | GPT-4 · Hard MAB instance, T=100 | n*MinFrac: $0.38$ -> $0.27$ | Helped |
| Add re-weighting to GPT-4o's bandit input | GPT-4o · Hard MAB instance, T=100 | median reward: $0.455$ -> $0.475$ | Helped |
| Add re-weighting to GPT-4's bandit input | GPT-4 · Hard MAB instance, T=100 | median reward: $0.46$ -> $0.46$ | No clear effect |
Surprising findings
- GPT-4 and GPT-4 Turbo can have linear regret under simple adaptive adversarial loss sequences, showing that no-regret behavior is not universal.
- Summary-based history input can perform much worse than raw history input in the adversarial setting, reversing the prior finding from stochastic bandits.
Limitations
- Theoretical explanation based on hypothetical pre-training assumptions that may not hold for real LLMs.
- Only modest-scale transformers trained; no larger-scale language model training with regret-loss.
- Focuses on external regret with numeric payoffs; swap and policy regret not studied.
Experimental setup
Benchmarks: canonical FTL counterexamples noisy alternating loss sequence adaptive loss sequence six representative general-sum games randomly generated multi-player games hard MAB instance (Krishnamurthy et al.)
Metrics: external regret dynamic regret trend-test p-value log-log regression slope median reward SuffFailFreq
Baselines: FTRL FTPL EXP3 Restart FTRL/FTPL Thompson Sampling UCB
Builds on: follow-the-regularized-leader follow-the-perturbed-leader quantal response model in-context learning theory for transformers
Closest papers by meaning
- From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systems (ICML 2024 · similarity 0.90)
- From Player to Master: Enhancing Test-Time Learning of LLM Agents via Reinforcement Learning over Memory (ICML 2026 · similarity 0.89)
- EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration (ICML 2025 · similarity 0.88)
- On the Modeling Capabilities of Large Language Models for Sequential Decision Making (ICLR 2025 · similarity 0.88)
- MEMO: Memory-Augmented Model Context Optimization for Robust Multi-Turn Multi-Agent LLM Games (ICML 2026 · similarity 0.88)
- Can large language models explore in-context? (NeurIPS 2024 · similarity 0.88)
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.