# Provable Interactive Learning with Hindsight Instruction Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 14 Apr 2024.

## Builds on (most cited first, 27 of 27)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Overcoming Exploration in Reinforcement Learning with Demonstrations](https://mlsanity.com/paper/1709.10089/) (2017)
- [Speaker-Follower Models for Vision-and-Language Navigation](https://mlsanity.com/paper/1806.02724/) (2018)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Mapping Instructions to Actions in 3D Environments with Visual Goal Prediction](https://mlsanity.com/paper/1809.00786/) (2018)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Grounded Language Learning Fast and Slow](https://mlsanity.com/paper/2009.01719/) (2020)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [Generalized Hindsight for Reinforcement Learning](https://mlsanity.com/paper/2002.11708/) (2020)
- [Exploration via Elliptical Episodic Bonuses](https://mlsanity.com/paper/2210.05805/) (2022)
- [Listen, Attend, and Walk: Neural Mapping of Navigational Instructions to Action Sequences](https://mlsanity.com/paper/1506.04089/) (2015)
- [Learning to Map Natural Language Instructions to Physical Quadcopter Control using Simulated Flight](https://mlsanity.com/paper/1910.09664/) (2019)
- [Goal Representations for Instruction Following: A Semi-Supervised Language Interface to Control](https://mlsanity.com/paper/2307.00117/) (2023)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Interactive Learning from Activity Description](https://mlsanity.com/paper/2102.07024/) (2021)
- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)

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

- [Aligning LLM Agents by Learning Latent Preference from User Edits](https://mlsanity.com/paper/2404.15269/) (2024)

## Abstract (arXiv)

We study interactive learning in a setting where the agent has to generate a response (e.g., an action or trajectory) given a context and an instruction. In contrast, to typical approaches that train the system using reward or expert supervision on response, we study learning with hindsight instruction where a teacher provides an instruction that is most suitable for the agent's generated response. This hindsight labeling of instruction is often easier to provide than providing expert supervision of the optimal response which may require expert knowledge or can be impractical to elicit. We initiate the theoretical analysis of interactive learning with hindsight labeling. We first provide a lower bound showing that in general, the regret of any algorithm must scale with the size of the agent's response space. We then study a specialized setting where the underlying instruction-response distribution can be decomposed as a low-rank matrix. We introduce an algorithm called LORIL for this setting and show that its regret scales as √T where T is the number of rounds and depends on the intrinsic rank but does not depend on the size of the agent's response space. We provide experiments in two domains showing that LORIL outperforms baselines even when the low-rank assumption is violated.