Multiple responses improve learning from imperfect demonstrations
The Statistical Benefits of Multiple Responses for Learning from Demonstrations
Information TheoryMachine Learning
Summary
Learning from examples can be harder if the examples aren't perfect. This paper studies how giving several possible answers at once helps learning in that case. The authors show that having multiple tries can make the learning process much more efficient, even when the examples are not ideal. They also explain how these benefits differ depending on how the quality of the examples is judged. Their findings come with mathematical proofs and a practical learning method that works without needing perfect examples.
What this means in practice
- •For machine learning engineers: Design training protocols that use multiple candidate outputs per demonstration to reduce sample needs when the training data is imperfect.
- •For automated decision system developers: Improve reliability of learned policies under uncertain or varying reward criteria by considering multiple candidate responses during learning.
A theory result. No direct application yet.
Authors
Chandramauli Chakraborty, Cong Ma
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.