Formalizing Learning from Language Feedback with Provable Guarantees

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 measure to characterize the hardness of LLF problems. We formalize the intuition that information in the feedback governs the learning complexity of LLF problems. 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 an important step towards designing principled interactive learning algorithms from generic language feedback.

Modern AI agents are increasingly expected to learn not only from trial-and-error rewards, but also from natural language feedback: for example, a user might tell an agent why its action was wrong, what it should have considered, or how to improve next time. This kind of feedback can be much richer than a simple score, but it is also harder to use systematically. We wanted to understand when language feedback can actually help an agent learn faster, and how to design algorithms with reliable guarantees. We introduce a mathematical framework for studying Learning from Language Feedback. Our framework captures interactive settings where the agent acts, observes outcomes, and receives language feedback that gives indirect information about what good behavior should look like. We also introduce a new complexity measure, called transfer eluder dimension, which describes how difficult it is to transfer information from language feedback into better decisions. Our results show that rich language feedback can sometimes make learning exponentially faster than learning from rewards alone. We also develop an algorithm, HELiX, that learns effectively through sequential interactions and performs well in experiments, including cases where repeatedly prompting large language models is unreliable. This work provides a step toward principled learning algorithms that can use general language feedback, rather than treating it as an ad hoc prompt-engineering tool.