The Statistical Benefits of Multiple Responses for Learning from Demonstrations
Abstract
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/ε2 to 1/ε, 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/ε 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.
Related
- Statistical Testing for Multiple Instance Learning via Selective Inference with Applications to Computational Pathology
- Statistical Benefits of Fine-Tuning from Pretrained Initialization in Diagonal Linear Networks
- Statistical Learning of Conditional Single-Index U-Processes Under Local Stationarity and Missing-At-Random Functional Responses
- Statistical Methods for Multiple Language Model Comparison on a Shared Evaluation
- Data-Driven MPC with Adaptively Sampled Non-Expert Demonstrations: Performance Guarantees and Sample Complexity
BibTeX
@misc{chakraborty2026statistical,
title = {{The Statistical Benefits of Multiple Responses for Learning from Demonstrations}},
author = {Chandramauli Chakraborty and Cong Ma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.33291},
eprint = {2609.33291},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33291},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Statistical Benefits of Multiple Responses for Learning from Demonstrations
AU - Chandramauli Chakraborty
AU - Cong Ma
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2609.33291
UR - https://arxiv.org/abs/2609.33291
AB - 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/ε^2 to 1/ε, 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/ε 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.
ER -