Research map / Bandits and online learning / Online convex optimization and games
Provable Interactive Learning with Hindsight Instruction Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies interactive learning from hindsight instruction labels (teacher describes the agent's response with an instruction), proves a sqrt(|Y|T)-type lower bound in general, and gives the LORIL algorithm with sqrt(T) regret under a low-rank teacher model.
Problem
Interactive learning where an agent generates a response to an instruction and context, but receives only hindsight instruction labels from a teacher rather than expert responses or rewards; the goal is provable regret guarantees.
Approach
Model the teacher's instruction distribution as a low-rank decomposition P(x|y,s)=f*(x)^T g*(y,s) and apply optimism with an elliptic bonus over responses, using MLE for the instruction-side features, to obtain regret that scales with the intrinsic rank d and sqrt(T) rather than the response-space size.
Key results
- LORIL achieves regret 12.3% smaller than the next best baseline on the synthetic low-rank task.
- On the image selection task LORIL achieves 4.8% less regret than the next best baseline even though the low-rank assumption does not hold.
- The paper proves a general lower bound of order sqrt(|Y|T) (Omega(sqrt(KT))) and an upper bound of O(B sqrt(Td log(1+TB)) + ...) for LORIL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LORIL instead of the next-best baseline | Synthetic task · Synthetic task | cumulative regret: 12.3% smaller | Helped |
| Add exploration compared with the greedy baseline | Synthetic task · Synthetic task | cumulative regret | Helped |
| Use elliptic-bonus exploration instead of epsilon-greedy exploration | Synthetic task · Synthetic task | cumulative regret | Helped |
| Use LORIL instead of the next-best baseline | Image selection task · Image selection task | regret: 4.8% less regret | Helped |
Limitations
- Regret bound requires known response embedding g* and realizability of the model class.
- Computational efficiency for exponentially large response spaces is left for future work.
- Experiments are small-scale with simple baselines and modest exploration challenges.
Experimental setup
Datasets: synthetic low-rank teacher matrices template-generated instructions over rendered object images
Benchmarks: synthetic low-rank teacher task image selection task with template instructions
Metrics: cumulative regret
Baselines: Random epsilon-Greedy Greedy
Builds on: LinUCB elliptic bonus low-rank bandits hindsight experience replay
Closest papers by meaning
- From Outcomes to Actions: Leveraging Hindsight for Long-Horizon Language Agent Training (ICML 2026 · similarity 0.86)
- The Wisdom of Hindsight Makes Language Models Better Instruction Followers (ICML 2023 · similarity 0.86)
- Hindsight policy gradients (ICLR 2019 · similarity 0.86)
- Spinning Straw into Gold: Relabeling LLM Agent Trajectories in Hindsight for Successful Demonstrations (ICLR 2026 · similarity 0.85)
- Sequential Decision Making with Expert Demonstrations under Unobserved Heterogeneity (NeurIPS 2024 · similarity 0.85)
- SD-Search: Hindsight Self-Distillation for Search-Augmented Reasoning (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.