Provably Learning from Language Feedback
Wanqiao Xu 1 , Allen Nie 1 , Ruijie Zheng 2 , Aditya Modi 4 , Adith Swaminathan 3 , Ching-An Cheng 4 1 Stanford University 2 University of Maryland, College Park 3 Netflix Research 4 Microsoft Research · 2025
Read Provably Learning from Language Feedback by Wanqiao Xu 1 , Allen Nie 1 , Ruijie Zheng 2 , Aditya Modi 4 , Adith Swaminathan 3 , Ching-An Cheng 4 1 Stanford University 2 University of Maryland, College Park 3 Netflix Research 4 Microsoft Research (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-10341.txt.
Introduction
Wanqiao Xu and co-authors formalize learning from language feedback in a 2025 paper. AI agents increasingly learn from comments, not just scores. Rich comments carry more signal than a bare reward, yet no principled frame described the problem. The team define the setting, state what must hold for learning to work despite hidden rewards, and coin a hardness measure for it.
Their measure ties learning speed to how much information the feedback carries. In some cases language feedback provably beats reward learning by an exponential margin. A no regret algorithm follows from the frame. The theory may guide when to ask teachers for words instead of numbers.
Catalog record
| CREATOR | Wanqiao Xu 1 , Allen Nie 1 , Ruijie Zheng 2 , Aditya Modi 4 , Adith Swaminathan 3 , Ching-An Cheng 4 1 Stanford University 2 University of Maryland, College Park 3 Netflix Research 4 Microsoft Research |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 117 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-10341
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Provably Learning from Language Feedback Wanqiao Xu 1 , Allen Nie 1 , Ruijie Zheng 2 , Aditya Modi 4 , Adith Swaminathan 3 , Ching-An Cheng 4 1 Stanford University 2 University of Maryland, College Park 3 Netflix Research 4 Microsoft Research Abstract Interactively learning from observation and language feedback is an increasingly studied area driven by the emergence of large language model (LLM) agents. While impressive empirical demonstrations have been shown, so far a principled framing of these decision problems remains lacking. In this paper, we formalize the Learning from Language Feedback (LLF) problem, assert sufficient assumptions to enable learning despite latent rewards, and introduce transfer eluder dimension as a complexity measure to characterize the hardness of LLF problems. We show that transfer eluder dimension captures the intuition that information in the feedback changes the learning complexity of the LLF problem. We demonstrate cases where learning from rich language feedback can be exponentially faster than learning from reward. We develop a no-regret algorithm, called HELiX , that provably solves LLF problems through sequential interactions, with performance guarantees that scale with the transfer eluder dimension of the problem. Across several empirical domains, we show that HELiX performs well even when repeatedly prompting LLMs does not work reliably. Our contributions mark a first step towards designing principled interactive learning algorithms from generic language feedback. 1 Introduction Large language models (LLMs) have reshaped the landscape of how machines learn and interact with the world, demonstrating remarkable capabilities across a wide range of tasks ( Bommasani et al. 2021 ; BIG-bench authors 2023 ; Anil et al. 2024 ; Hurst et al. 2024 ; Jaech et al. 2024 ; Guo et al. 2025 ; Yamada et al. 2025 ) . Trained on large corpra of web data, these models can interact with the world through natural language, opening up new settings for sequential decision-making problems. Unlike traditional sequential decision-making approaches where agents learn from scalar reward signals ( Sutton and Barto 2018 ) , LLM can act as agents that interpret and reason with natural language feedback such as critique ( Du et al. 2023 ; Akyürek et al. 2023a ) , guidance ( Branavan et al. 2012 ; Harrison et al. 2017 ; Scheurer et al. 2023 ; Nie et al. 2023 ; Fu et al. 2024 ; Wei et al. 2024 ; Cheng et al. 2024 ) , or detailed explanations ( Andreas et al. 2017 ; Chen et al. 2023 ; Cheng et al. 2023 ) . Consider an LLM agent that produces a summary of a story, and receives feedback: “The summary is mostly accurate, but it overlooks the main character’s motivation.” Such feedback conveys notably richer information than a numerical score, e.g., 0.7 out of 1, as it identifies a specific flaw and suggests a direction for improvement. With LLMs’ abilities to understand and respond in natural language ( Touvron et al. 2023 ) , such feedback can be leveraged to drastically increase learning efficiency. This represents a fundamental shift in how AI systems can learn through continuous, rich interactions beyond rewards only ( Silver and Sutton 2025 ) . Despite early works on this topic pre-LLM ( Gauthier and Mordatch 2016 ; Andreas 2022 ) and promising recent empirical results in utilizing language feedback for sequential decision-making ( Liu et al. 2023 ; Chen et al. 2024 ; Xie et al. 2024 ) , a rigorous theoretical framework remains lacking. Figure 1 : The LLF setup. The environment has a hypothesis \eta^{*} representable via text tokens unknown to the agent. Reward as a function of \eta^{*} is latent and used only to benchmark the agent via regret to an optimal policy. Feedback as a function of \eta^{*} is observed by the agent. Three ingredients are sufficient for no-regret learning: feedback is unbiased ( 3 ), agent can interpret feedback ( 2 ), and agent considers hypotheses \mathcal{H} including \eta^{*} (precursor to 1 ). We introduce a formal framework of Learning from Language Feedback (LLF), the first mathematical model of learning from language feedback in decision making. The LLF paradigm was proposed in ( Cheng et al. 2023 ) as an interface to benchmark LLM agents’ learning ability, which generalizes the classical learning-from-reward reinforcement learning setting to general in-context problem solving by replacing numerical rewards with text feedback. However, it is unclear when LLF is feasible or whether it is harder to learn than the more traditional reward-aware reinforcement learning (RL) setting. Intuitively, one might think language feedback can provide more information to help learning. Indeed, people have empirically found constructive feedback to be more effective for LLM agents to learn from than conveying reward alone in words ( Mu et al. 2022 ; Liu et al. 2024 ; Zhong et al. 2024 ; Xie et al. 2024 ) . The complexity and generality of language make it difficult to formally quantify the information in language feedback. The goal of this paper is to provide constructive answers to all the following questions: For general language feedback, can we precisely define helpful and unhelpful feedback? Can we capture the complexity of LLF based on the information in the feedback? Does helpful feedback indeed lead to a lower problem complexity? Can we design a provably correct algorithm that learns solely from language? To work with the generality of language, we rely on the concept of hypothesis testing and elimination in machine learning ( De Jong et al. 1993 ; Lehmann and Romano 2022 ) except with hypotheses that can be expressed in words. We formalize the interface in which agents sequentially interact while reasoning with feedback produced by an underlying hypothesis (summarized by Fig. 1 ). We also define a verifier which evaluates the semantic consistency between candidate hypotheses and observed feedback. Through the notion of hypothesis and verifier, we give a precise definition of informative feedback and establish conditions such that LLF is feasible and can be efficiently solved. Specifically, we capture the learning difficulty with a new notion of complexity based on eluder dimension ( Russo and Van Roy 2013 ) , which we call transfer eluder dimension . This complexity measure captures how efficiently language feedback can reduce uncertainty about rewards. Building on this concept, we develop HELiX , a provably efficient algorithm for LLF. We prove that HELiX achieves a regret bound that scales gracefully with the transfer eluder dimension and time horizon T , establishing the first formal connection between no-regret learning and language feedback. Crucially, our analysis shows that in certain environments, HELiX can be exponentially more efficient than learning from reward alone. We introduce a meta-algorithm that enables LLM to perform inference-time exploration and exploitation using HELiX , inspired by how thinking tokens are used in large reasoning models (LRMs) ( Guo et al. 2025 ) . Our algorithm selects actions based on multiple thinking traces, treating them as samples from a space of hypotheses, while evolving this hypothesis space using past observations (see Figure 2 ). We empirically validate the efficacy of our implementation on Wordle, Battleship and Minesweeper. We show that HELiX and its variants consistently outperform in-context learning LLM baselines. Altogether, our work contributes a first principled framework for