arXiv：cs.LG· Chandramauli Chakraborty, Cong Ma·· 16 小时前
多响应样本对从演示中学习的统计优势：非最优演示下的 pass@k 收益分析
The Statistical Benefits of Multiple Responses for Learning from Demonstrations
AI 导读
研究发现，当演示者并非最优时，从 pass@1 提升到任意 pass@k（k≥2）可将最坏情况下对目标精度的依赖从 1/ε² 降至 1/ε，且这一改进对演示者质量一致成立。在标准评估下，增大 k 还能将奖励类大小 N 的最优依赖从 log N 改善到 log N/log k，但该收益在鲁棒评估下可能消失，而 1/ε 依赖仍然保持。
正文
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\ge2$ changes the worst-case dependence on target accuracy from $1/\varepsilon^2$ 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.
| Subjects: | Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST) |
| Cite as: | arXiv:2609.33291 [stat.ML] |
| (or arXiv:2609.33291v2 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2609.33291 arXiv-issued DOI via DataCite |
Submission history
From: Chandramauli Chakraborty [view email]
[v1]
Sun, 27 Sep 2026 06:53:01 UTC (48 KB)
[v2]
Tue, 13 Oct 2026 23:43:02 UTC (64 KB)
来源：arXiv：cs.LG · arxiv.org