acceptodds
Under review as a conference paper at ICLR 2027

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@ can reduce the sample complexity of learning from demonstrations by a logarithmic factor in . 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@ to any pass@ with changes the worst-case dependence on target accuracy from to , uniformly over demonstrator quality. Under standard evaluation, where an unknown reward is fixed before training, increasing provides an additional and distinct benefit: the optimal dependence on a reward class of size improves from to . 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 dependence persists, while the 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.

Primary area:
learning theory
Keywords:
demonstrations, pass@k, stochastic policy

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_FtMmOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

A theoretical analysis of sample complexity of a learner which is evaluated using pass@k metric is conducted. This is compared to existing results for pass@1, under both standard and robust evaluation. In contrast to previous work, the demonstrator is allowed to be suboptimal.

Critical strengths
  • The new bounds with pass@k show that the how the sample complexity class improves with introduction of pass@k i.e. 1/ϵ1/\epsilon instead of 1/ϵ21/\epsilon^2, which is useful for settings where pass@k might be used in place of pass@1. Not all problem settings allow use of pass@k, but many do, so pass@k analysis remains important.
  • A suboptimal demonstrator has not been considered in prior work, which is a very practical consideration as demonstrator's are rarely optimal in real world. This work allows the demonstrator to be arbitrarily suboptimal.
Critical weaknesses
  • All of these bounds depend on log⁡∣R∣=Θ(∣X∣∣Y∣)\log|\mathcal{R}|=\Theta(|\mathcal{X}||\mathcal{Y}|) which can significantly limits the applicability of these results. For continuous rewards or continuous ∣X∣|\mathcal{X}| or ∣Y∣|\mathcal{Y}| these results are not applicable, but even for binary rewards, these might become vacuous very quickly in some settings.

However, this is at least partly commented upon near the end of the paper.

Minor Errors

  • line 138. A leftover 't'
  • line 348. says "Figure" instead of "Algorithm"
Questions for authors

None

1 comment

We thank the reviewer for the useful and insightful comments. We will correct the minor errors you suggested and include them in the camera-ready version of this paper.

Reviewer_Qn5YOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the sample complexity of learning from demonstrations when a learner can return multiple responses and is evaluated on the best one. The paper provides upper and lower bounds and a greedy coverage algorithm with multiplicative weight updates.

Critical strengths
  1. The paper extends the analysis beyond optimal demonstrations.

  2. The results distinguish two benefits of multiple responses: the faster accuracy rate and the improved dependence on reward-class size.

  3. The analysis is somewhat detailed.

Critical weaknesses
  1. The learner jointly selects responses to cover different reward possibilities, rather than sampling independently from one policy.

  2. The algorithm assumes access to every reward function in the class and exact maximization of a weighted coverage objective. These operations may be expensive for large reward classes or structured responses.

  3. The paper is somewhat hard to follow.

Questions for authors

see weakness

1 comment

We thank the reviewer for the useful and insightful comments.

  • To answer your first question, we did few exploration on this aspect and found out that when a single-response learner generates kk independent responses (a special case of the joint responses, implying the lower bounds, Theorems 4 and 7 still hold), the fast sample complexity of 1/ε1/\varepsilon and log⁡k\log k (with a small constant of the order log⁡log⁡\log\log) improvements still hold for the robust and standard evaluations, respectively, but the trade-off should be to choose large k≥2log⁡(2/ε)k\ge 2\log(2/\varepsilon), while for small values of kk the rates are similar to those of pass@1. We will include this in the camera-ready version of the paper.
  • To answer your second concern, we agree with you that the algorithm is difficult to implement in practice, but the algorithm is given to justify the upper bound on the sample complexity of a PAC-learnable algorithm.
  • To answer your third comment, we would be very happy to hear from you about changing some aspects of the paper to make it readable to a larger audience.
Reviewer_fxEhOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The current submission has two main contributions:

  1. It considers Theorem 7 of Joshi et al. which studies pass@k under optimal demonstrations and extends this result to suboptimal demonstrators. Interestingly, for the pass@1 case, when the demonstrations do not come from an optimal policy, the rate degrades to 1/ϵ21/\epsilon^2 while the same deterioration does not happen for pass@k with k≥2k\geq 2.
  2. The authors then study the robust evaluation setting in which the learner is tasked with outputting a policy which is simultaneously as good as the demonstrator in pass@k metric for all the rewards in the class. While the transition from 1/ϵ21/\epsilon^2 to 1/ϵ1/\epsilon rate survives the change of setting. The dependence on log⁡N/log⁡k\log N/\log k becomes log⁡N\log N. In words, increasing k does not help to avoid the dependence on the complexity of the reward class.

Both results are attained by the same algorithm which is based on a variant exponential-weight over the reward class. Moreover, all the upper bounds presented are shown to be tight in the worst case via matching lower bounds.

Critical strengths
  1. I think that studying training procedure for the pass@k metric is important as it is becoming a more and more common evaluation criterion in LLMs practice.

  2. The results are sound, novel and surprising to the best of my knowledge. The fact that under suboptimal demonstrators learning at a 1/ε1/\varepsilon rate is possible for pass@k while it is not for pass@1 it is a nice finding.

Critical weaknesses
  1. The algorithm is not implementable in an efficient manner for large reward classes.

  2. The analysis is limited to single-step decision making problems. In other words, the analysis only applies to contextual bandits and not to Markov Decision Processes.

Questions for authors
  1. The authors base their work on the framework of imitation learning in which we are willing to pay only the complexity of the reward class and not, for example, the complexity of a policy class realizing the demonstrators. The authors could do a better job at discussing why it is important to study pass@k in this reward-based IL scenario rather than in the more traditional policy based scenario. It is perhaps worth to mention in the conclusions which kind of pass@k benefits the authors would expect for more traditional IL methods such as Behavioural Cloning.

  2. Can the authors obtain the same statistical benefits with an algorithm which can be easier to implement? For example, with one that only needs an maximization oracle over R\mathcal{R} rather than maintaining an exponential weight learner over the class? By optimization oracle I mean the possibility to compute argmaxr∈Rf(r)\text{argmax}_{r \in \mathcal{R}} f(r) for one or some functions $f : \mathcal{R} \rightarrow \mathbb{R} $.

  3. Can the authors discuss what are the difficulties in extending the current methods to Markov Decision Processes?

  4. Can the authors prove pass@1 guarantees for their algorithm on top of the guarantees for pass@k proven in the submission? I am asking this because in practice people use pass@k but pass@1 is often times monitored as well.

2 comments

We thank the reviewer for the useful and insightful comments.

  • To answer your first question, the reward-based IL scenario is more general in contrast to the policy-based class, this has already been shown by Joshi et al. (2026), where they have shown that with a low-cardinality policy class, the MLE is minimax optimal, whereas the same does not hold for the reward-based scenario, infact the MLE fails to learn when the reward class is binary (Joshi et al. 2026). We will include a short paragraph on this in the camera-ready version. We would expect a similar improvement of 1/log⁡k1/ \log k for the traditional policy-class based scenario.
  • To answer your second concern, we do not have a satisfactory answer to this at this moment, but we will try to find a good answer to this question.
  • To answer your third query, we feel in general it is difficult to formulate an MDP involving the pass@kk metric, there are few works in this aspect, few of them which are worth mentioning are https://arxiv.org/pdf/2505.15201 and https://proceedings.neurips.cc/paper_files/paper/2007/file/ca3ec598002d2e7662e2ef4bdd58278b-Paper.pdf.
  • To answer your fourth question, the rates are same as those of the pass@1 (Tables 2 and 3) mentioned in the paper, except for the online-regret bound (Theorem 9) which will be O(log⁡∣R∣+T+T/L)\mathcal O(\log|\mathcal R|+T+T/L). We will include this in the camera-ready version of the paper.

Thank you for your response. I keep my positive score.

Reviewer_9s3sOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the sample complexity of learning from demonstrations when the learner is evaluated by pass@k, i.e., it returns k (possibly dependent) responses and is scored by the best one. The learner observes m i.i.d. context–response pairs from an unknown demonstrator, knows a finite reward class R of size N, and receives no reward feedback. Performance is measured as the gap between the demonstrator's single-response value and the learner's pass@k value. Building on Joshi et al. (2026), who studied optimal demonstrators, the paper removes the optimality assumption and considers two evaluation modes: standard (a fixed, unknown target reward r ∈ R) and robust (the learner must match the demonstrator simultaneously for every r ∈ R).

The main results, for arbitrary demonstrators and up to constants, are:

  • Slow-to-fast transition. For pass@1 the worst-case rate is (log N + log 1/δ)/ε², and this is shown to be unimprovable; for any k ≥ 2 the rate becomes 1/ε, independent of demonstrator quality. The intuition is that multiple responses turn a small-bias estimation problem into a coverage problem.
  • Standard evaluation: the optimal rate for k ≥ 2 is (log N / log k + log 1/δ)/ε, with matching upper and lower bounds; the lower bound already holds for optimal demonstrators, so suboptimality incurs no additional cost.
  • Robust evaluation: the fast 1/ε rate persists, but the 1/log k improvement disappears in the high-accuracy regime (ε ≲ min{Δ, 1/k}, N ≥ 2k²), where (log N + log 1/δ)/ε is tight.
Critical strengths
  1. The paper provides matching upper and lower bounds in each regime considered, and the summary in Table 1 makes the landscape easy to grasp. Separating the two benefits of multiple responses (the 1/ε² → 1/ε transition and the log k reduction in reward-class dependence) via the standard/robust distinction is a nice conceptual contribution.
  2. The paper is clearly structured, the definitions are precise, and the limitations and open problems are stated honestly in the discussion.
Critical weaknesses

1.The learner's pass@k value is compared with the demonstrator's single-response value. Against a suboptimal demonstrator, a learner allowed k ≥ 2 attempts competes against a benchmark that gets only one, and the 1/ε² → 1/ε transition follows directly from this asymmetry, as the paper's own two-response example illustrates: pass@2 can simply return both candidates. This makes the main "qualitatively stronger benefit" less surprising than the framing suggests. The paper should justify this benchmark choice more carefully (e.g., why it is the right notion of "performing comparably to the demonstrator" in pass@k settings), and discuss what happens under symmetric benchmarks, such as the demonstrator's own pass@k value (k independent demonstrator samples) or the optimal value V*_r. Even a discussion of whether the separation persists under these benchmarks would considerably strengthen the paper. 2. The paper is purely theoretical. This is acceptable, but a small simulation (e.g., synthetic finite reward classes comparing pass@1 and pass@k learners, or comparing joint selection with independent sampling) would help readers see when the asymptotic separations matter at realistic sample sizes and would make the paper more accessible to the ICLR audience.

Questions for authors
  1. Why compare the learner's pass@k value to the demonstrator's pass@1 value rather than the demonstrator's pass@k value or the optimal value? Do the separations persist under these alternative benchmarks?
  2. Does the 1/ε rate hold for pass@k with k independent samples from a single learned policy? If not, what is the best known rate in that case?
1 comment

We thank the reviewer for the useful and insightful comments.

  • To answer your first question, we compare against the demonstrator's pass@11 value because our objective is to achieve the demonstrator's expected reward, as in standard apprenticeship learning. Keeping this target fixed as kk varies allows us to isolate the statistical benefit of generating multiple responses: how much can additional inference computation reduce the number of demonstrations needed to reach the same reward level? Comparing against the demonstrator's pass@kk value instead introduces a stronger, kk-dependent target.
  • To answer your second concern, we did few exploration on this aspect and found out that when a single-response learner generates kk independent responses (a special case of the joint responses, implying the lower bounds, Theorems 4 and 7 still hold), the fast sample complexity of 1/ε1/\varepsilon and log⁡k\log k (with a small constant of the order log⁡log⁡\log\log) improvements still hold for the robust and standard evaluations, respectively, but the trade-off should be to choose large k≥2log⁡(2/ε)k\ge 2\log(2/\varepsilon), while for small values of kk the rates are similar to those of pass@1. We will include this in the camera-ready version of the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.