Provably Learning from Language Feedback

This research introduces a formal framework called Learning from Language Feedback (LLF), where AI agents learn from natural language interactions instead of numerical rewards. The authors propose "transfer eluder dimension" to measure the complexity and efficiency of learning in LLF problems, demonstrating that rich language feedback can lead to exponentially faster learning than traditional reward-based methods. They develop HELiX, a no-regret algorithm designed to provably solve LLF problems by maintaining a confidence set of hypotheses and strategically choosing actions that balance exploration and exploitation. Empirical results on games like Wordle and Battleship showcase HELiX's superior performance over existing large language model baselines, highlighting the potential for principled interactive learning from generic language.