# Formalizing Learning from Language Feedback with Provable Guarantees

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 84 references that are in the map.
- First posted on arXiv 12 Jun 2025.

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

- [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)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs](https://mlsanity.com/paper/2503.01307/) (2025)
- [Can LLMs Generate Novel Research Ideas? A Large-Scale Human Study with 100+ NLP Researchers](https://mlsanity.com/paper/2409.04109/) (2024)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [Large Language Models are Better Reasoners with Self-Verification](https://mlsanity.com/paper/2212.09561/) (2022)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models](https://mlsanity.com/paper/2310.10505/) (2023)
- [Chain of Hindsight Aligns Language Models with Feedback](https://mlsanity.com/paper/2302.02676/) (2023)
- [Supervised Pretraining Can Learn In-Context Reinforcement Learning](https://mlsanity.com/paper/2306.14892/) (2023)
- [DiffCSE: Difference-based Contrastive Learning for Sentence Embeddings](https://mlsanity.com/paper/2204.10298/) (2022)
- [Language Models as Agent Models](https://mlsanity.com/paper/2212.01681/) (2022)
- [Training Language Models with Language Feedback at Scale](https://mlsanity.com/paper/2303.16755/) (2023)
- [Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.07572/) (2025)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [RL4F: Generating Natural Language Feedback with Reinforcement Learning for Repairing Model Outputs](https://mlsanity.com/paper/2305.08844/) (2023)
- [LongEval: Guidelines for Human Evaluation of Faithfulness in Long-form Summarization](https://mlsanity.com/paper/2301.13298/) (2023)
- [The Optimal Reward Baseline for Gradient-Based Reinforcement Learning](https://mlsanity.com/paper/1301.2315/) (2013)

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

- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [Expanding the Capabilities of Reinforcement Learning via Text Feedback](https://mlsanity.com/paper/2602.02482/) (2026)
- [RetroAgent: From Solving to Evolving via Retrospective Dual Intrinsic Feedback](https://mlsanity.com/paper/2603.08561/) (2026)
- [Understanding the Challenges in Iterative Generative Optimization with LLMs](https://mlsanity.com/paper/2603.23994/) (2026)
- [Learning from Language Feedback via Variational Policy Distillation](https://mlsanity.com/paper/2605.15113/) (2026)
- [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025)
- [DIVE: Unlocking Self-Improvement in Frozen Language Models Through Diversity-Driven Skill Evolution](https://mlsanity.com/paper/2608.12486/) (2026)
- [Inference-time Unlearning Using Conformal Prediction](https://mlsanity.com/paper/2602.03787/) (2026)
- [POLCA: Stochastic Generative Optimization with LLM](https://mlsanity.com/paper/2603.14769/) (2026)
- [Learning to Learn from Language Feedback with Social Meta-Learning](https://mlsanity.com/paper/2602.16488/) (2026)
- [Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback](https://mlsanity.com/paper/2602.08307/) (2026)
- [Inductive Feedback for Mixed-Policy Distillation](https://mlsanity.com/paper/2609.35390/) (2026)
- [Learning What to Investigate Next: Meta-Reasoning for Long-Horizon Research Agents](https://mlsanity.com/paper/2610.02525/) (2026)
- [Constraint Tree Exploration for Learning from Language Feedback](https://mlsanity.com/paper/2610.09107/) (2026)
- [Reflective Prompt Optimization of a Deep-Research Agent: A Topic-Disjoint, Multi-Seed Protocol for Measuring Transferable Gains and Prompt-Level Overfitting](https://mlsanity.com/paper/2610.12601/) (2026)

## Abstract (arXiv)

Interactively learning from observation and language feedback is an increasingly studied area driven by the emergence of large language model (LLM) agents. Despite impressive empirical demonstrations, so far a principled framing of these decision problems remains lacking. We formalize the Learning from Language Feedback (LLF) problem, assert sufficient assumptions to enable learning despite latent rewards, and introduce textittransfer eluder dimension as a measure to characterize the hardness of LLF. We formalize the intuition that information in the language feedback governs the learning complexity, and demonstrate cases where learning from rich language feedback can be exponentially faster than learning from reward. We develop a no-regret algorithm, called textttHELiX, that provably solves LLF problems through sequential interactions, with performance guarantees that scale with the transfer eluder dimension. Across several empirical domains, we show that textttHELiX performs well even when repeatedly prompting LLMs does not work reliably. Our contributions mark an important step towards designing principled interactive learning algorithms using generic language feedback.