The Statistical Benefits of Multiple Responses for Learning from Demonstrations

arXiv 2609.33291 ↗First posted 27 Sep 2026stat.ML cs.IT cs.LGcited by 0

On the map: Offline RL and imitation learning from data → Imitation learning methods also fits: Inverse reinforcement learning

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.

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.

Builds on

18 of 28 references.

Closest ancestors · 2

Same direction, newest first

Other references · 16

2022Training language models to follow instructions with human feedbackcited by 15,971
2021Evaluating Large Language Models Trained on Codecited by 8,320
2022Competition-Level Code Generation with AlphaCodecited by 1,462
2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
2025Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Modelscited by 138
2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignmentcited by 97
2025Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problemscited by 87
2025Optimizing Language Models for Inference Time Objectives using Reinforcement Learningcited by 53
2022A Characterization of List Learnabilitycited by 22
2021Bandits with many optimal armscited by 17
2023List Online Classificationcited by 16

4 more

2025The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisationcited by 16
2025Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scalingcited by 9
2025Learning to Answer from Correct Demonstrationscited by 7
2026Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Modelscited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way