The Statistical Benefits of Multiple Responses for Learning from Demonstrations

Chandramauli Chakraborty; Cong Ma

stat.MLSep 27, 2026

The Statistical Benefits of Multiple Responses for Learning from Demonstrations

Authors: Chandramauli Chakraborty, Cong Ma

Organizations: Department of Statistics, University of Chicago

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.

Figures & tables

	Standard evaluation	Robust evaluation
pass@ $1$	$\displaystyle\frac{\log N+\log(1/\delta)}{\varepsilon^{2}}$	$\displaystyle\frac{\log N+\log(1/\delta)}{\varepsilon^{2}}$
pass@ $k$ , $k\geq 2$	$\displaystyle\frac{1}{\varepsilon}\left(\frac{\log N}{\log k}+\log\frac{1}{\delta}\right)$	$\displaystyle\frac{\log N+\log(1/\delta)}{\varepsilon}$

Table 1: Sample complexity for arbitrary demonstrators, up to universal constants. See Section 2 and Appendix C for precise statements.

\hat{y}^{(i)}_{t}\in\arg\max_{y\in{\mathcal{Y}}\setminus Y_{i-1}}\sum_{(r,j)\in A_{t}^{y}\backslash\cup_{z\in Y_{i-1}}A_{t}^{z}}w^{(t)}(r,j),\quad Y_{i}\leftarrow Y_{i-1}\cup\{\hat{y}^{(i)}_{t}\}.

Algorithm 1

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

\widehat{\pi}_{t}:{\mathcal{X}}\rightarrow\Delta({\mathcal{Y}}^{k}).

Appendix

Algorithm 2 Online-to-batch conversion for pass@

k

	Standard evaluation	Robust evaluation
pass@ $1$	$\displaystyle\Theta\!\left(\frac{\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon^{2}}\right)$	$\displaystyle\Theta\!\left(\frac{\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon^{2}}\right)$
pass@ $k$ , $k\geq 2$	$\displaystyle\Theta\!\left[\frac{1}{\varepsilon}\left(\frac{\log\|{\mathcal{R}}\|}{\log k}+\log\frac{1}{\delta}\right)\right]$	$\displaystyle\Theta\!\left(\frac{\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon}\right)$

Appendix

Table 2: Minimax PAC sample complexities for arbitrary demonstrators (

\Delta=1

), with universal constants implicit in

\Theta

. Upper bounds hold for every finite reward class, and matching lower bounds hold for suitable classes of the indicated cardinality. Assume

|{\mathcal{R}}|\geq 2

0<\delta\leq 1/64

, and

0<\varepsilon\leq c

, where

c>0

is a sufficiently small universal constant. For standard pass@

1

, assume additionally

|{\mathcal{R}}|\geq(1+1/\varepsilon)^{4}

\delta\leq 1/|{\mathcal{R}}|

. For pass@

k

, standard evaluation requires

|{\mathcal{R}}|\geq 2k

; robust evaluation requires

|{\mathcal{R}}|\geq 2k^{2}

and

\varepsilon\leq c/k

	Standard evaluation	Robust evaluation
pass@ $1$	$\displaystyle\Theta\!\left(\frac{(\Delta+\varepsilon)\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon^{2}}\right)$	$\displaystyle\Theta\!\left(\frac{\Delta\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon^{2}}\right)$
pass@ $k$ , $k\geq 2$	$\displaystyle\Theta\!\left[\frac{1}{\varepsilon}\left(\frac{\log\|{\mathcal{R}}\|}{\log k}+\log\frac{1}{\delta}\right)\right]$	$\displaystyle\Theta\!\left(\frac{\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon}\right)$

Appendix

Table 3: Minimax PAC sample complexities for

0<\Delta\leq 1

. The budget constrains

\Delta_{r^{\star}}\leq\Delta

under standard evaluation and

\Delta_{{\mathcal{R}}}\leq\Delta

under robust evaluation. Assume

|{\mathcal{R}}|\geq 2

0<\delta\leq 1/64

, and

0<\varepsilon\leq c

, where

c>0

is a sufficiently small universal constant. For standard pass@

1

, assume additionally

|{\mathcal{R}}|\geq(1+\Delta/\varepsilon)^{4}

\delta\leq 1/|{\mathcal{R}}|

; robust pass@

1

requires

\varepsilon\leq c\Delta

. For pass@

k

, standard evaluation requires

|{\mathcal{R}}|\geq 2k

; robust evaluation requires

|{\mathcal{R}}|\geq 2k^{2}

and

\varepsilon\leq c\min\{\Delta,1/k\}

. The

\Theta

entries describe matching worst-case bounds over reward classes, with universal constants.

	Standard evaluation	Robust evaluation
pass@ $1$	$\displaystyle\Theta\!\left(\frac{\log(\|{\mathcal{R}}\|/\delta)}{\varepsilon}\right)$	$0$
pass@ $k$ , $k\geq 2$	$\displaystyle\Theta\!\left[\frac{1}{\varepsilon}\left(\frac{\log\|{\mathcal{R}}\|}{\log k}+\log\frac{1}{\delta}\right)\right]$	$0$

Appendix

Table 4: Minimax PAC sample complexities for optimal demonstrators (

\Delta=0

). Under standard evaluation, optimality means

\Delta_{r^{\star}}=0

for the fixed evaluation reward; under robust evaluation, it means

\Delta_{{\mathcal{R}}}=0

, that is, optimality for every reward in the class. The standard entries assume

|{\mathcal{R}}|\geq 2

0<\delta\leq 1/64

, and

0<\varepsilon\leq c

for a sufficiently small universal constant

c>0

, with

|{\mathcal{R}}|\geq 2k

additionally required for pass@

k

. Their

\Theta

rates are worst-case rates over reward classes, with universal constants. The robust entries are exactly zero for every finite non-empty reward class, every

k\geq 1

\varepsilon>0

, and

\delta\in(0,1)

under class-wide optimality.

Explore similar work

Multiscale Reward Hedging from Correct Demonstrations
Aug 7, 2026Pahan Dewasurendra\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Optimality
Johns Hopkins University
Theoretical Foundations of $\max$ @ $k$ Reinforcement Learning
Jul 20, 2026Riccardo Poiani, Martino Bernasconi, Andrea CelliTop-K Theory
Bocconi University
Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach
May 29, 2026Kihyun Kim, Shripad Deshmukh, Nikos Vlassis +1Offline Reinforcement Learning Inverse Design
MIT LIDS · University of Massachusetts, Amherst · Adobe Research +1

Aug 7, 2026, cs.LGJ/K move · Enter open · S save

Multiscale Reward Hedging from Correct Demonstrations

Pahan Dewasurendra

Johns Hopkins University

\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Optimality

Open paper AskPDF arXiv

Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward. Existing reward-hedging guarantees consequently assume a finite reward class. We give the first horizon-free guarantee for continuous classes. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy. This yields the simultaneous tail bound

|\{t:\ell_t>2^{-j}\}|\leq \log_2\mathcal N(\mathcal G,2^{-j-1})+j

, where

\mathcal G

is the class of optimality-gap functions. Integrating the tails gives cumulative hidden gap bounded by a metric-entropy integral, independently of the number of rounds. Polynomial entropy

(A/ε)^d

gives

O(d\log A)

total gap and a fast

O(d/m)

statistical rate. For bounded linear contextual recommendation, the result is

O(d)

regret for arbitrary compact menus. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction. Although the general vote can be expensive, it is exactly polynomial-time for one-dimensional Lipschitz parameter curves. Fixed-radius rank-two recommendation takes

O(KT^2)

time for menus of size

K

. We also prove an

Ω(d)

lower bound, low-rank and bounded ReLU-network corollaries, and a robust theorem that adds only the demonstrator's cumulative suboptimality. A reproducible adaptive stress test illustrates the predicted scale adaptation. After factorization, an exact MovieLens audit runs in 1.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated-rating policy and a proper online baseline. The learner uses only action demonstrations and never observes a reward or a loss.

Abstract

Explore similar work

Multiscale Reward Hedging from Correct Demonstrations

Theoretical Foundations of max⁡\maxmax@kkk Reinforcement Learning

Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach

Theoretical Foundations of $\max$ @ $k$ Reinforcement Learning