# The Statistical Benefits of Multiple Responses for Learning from Demonstrations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 18 of its 28 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models](https://mlsanity.com/paper/2508.10751/) (2025)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems](https://mlsanity.com/paper/2505.15201/) (2025)
- [Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning](https://mlsanity.com/paper/2407.15007/) (2024)
- [Optimizing Language Models for Inference Time Objectives using Reinforcement Learning](https://mlsanity.com/paper/2503.19595/) (2025)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisation](https://mlsanity.com/paper/2510.23393/) (2025)
- [Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling](https://mlsanity.com/paper/2510.03199/) (2025)
- [Learning to Answer from Correct Demonstrations](https://mlsanity.com/paper/2510.15464/) (2025)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)

## Abstract (arXiv)

Many generative systems return multiple candidate responses and are evaluated according to the best one. Recent work shows that, when demonstrations are optimal, pass@k can reduce the sample complexity of learning from demonstrations by a logarithmic factor in k. We ask what happens when the demonstrator is not assumed to be optimal. We find that multiple responses provide a qualitatively stronger benefit in this setting. In a finite reward-class model with no reward feedback, moving from pass@1 to any pass@k with k≥2 changes the worst-case dependence on target accuracy from 1/varepsilon2 to 1/varepsilon, uniformly over demonstrator quality. Under standard evaluation, where an unknown reward is fixed before training, increasing k provides an additional and distinct benefit: the optimal dependence on a reward class of size N improves from log N to log N/log k. We further show that these two effects can be separated. Under robust evaluation, where one learned policy must compete with the demonstrator simultaneously for every reward in the class, the fast 1/varepsilon dependence persists, while the 1/log k improvement can disappear. We establish matching upper and lower bounds in the corresponding regimes and give a greedy multiplicative-weights learner achieving the upper bounds without any assumption on demonstrator quality.