- Rating
- 4(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies off-policy evaluation of BoN policies, which is particular important in the LLM/generative-AI setting. Here we have access to a base model \pi_b and there is as unknown reward function \mu, and we want to estimate the value (expected reward) of the BoN policy induced by \pi_b, with sampling budget N. Traditionally this is solved via importance weighting, but in the gen-AI setting we don't have access to the importance weights. Thus, the first key insight of the paper is that, by exploiting the structure of the BoN policy, one can use U-statistics to get an unbiased estimator for the importance weights. This leads to consistent value estimator, with a "standard" doubly-robust guarantee. The paper also considers the model- or estimator-selection problem, where specifically you want to choose the sampling budget N in the BoN; they give two estimators with asymptotic guarantees. Finally the paper conducts experiments, both synthetic and in an real LLM setting, as validation.
Critical strengths
The paper studies a real and interesting problem, has somewhat non-trivial technical insights, is comprehensive (with detailed theoretical statements and empirical validation), and is well-presented.
Critical weaknesses
I wouldn't call this critical, but I think there is one main point for the authors to think about:
- Although asymptotic guarantees are useful, finite sample guarantees are the gold standard for off-policy evaluation, as they provide a much more fine-grained measure of estimator quality (see e.g., https://arxiv.org/pdf/1511.03722 or https://arxiv.org/abs/1612.01205, or many other related papers). In this particular setting, there are two main concerns. 1a. We do not see the role of M or N in the basic bound (Theorem 4.2). Although we get a \sqrt{n} rate, it's plausible that the pre-multiplier scales exponentially with N; indeed the g_N term has exponential-in-N quantities, and this could mean that the estimator is actually still quite poor in finite sample. This would not be super surprising, because intuitively the importance weights for BoN-N explode as N increases, as the BoN policy moves further an further away from \pi_b, but it would be a good thing to point out explicitly. 1b. The asymptotic guarantees hide a lot of interesting behavior in the estimator selection problem. To me (and as pointed out in several prior works: https://arxiv.org/abs/2002.07729v2, https://jonathannlee.com/files/tucker2021improved.pdf) the estimator selection problem is much more interesting in finite sample. Particularly, here it's natural to expect that both BoN policy value and finite-sample variance are increasing with N, which means that asymptotically we would select the largest N, but in finite sample we probably would not (too high variance). The point is that doing everything in finite sample would capture more of the nuance of the problem and also lead to some non-trivial conceptual points. At the same time, I think it is extremely doable. There are concentration inequalities for U-statistics, which seem directly applicable. I think including this, possibly in the appendix would be great!
(Also I think it would be worthwhile to cite some of the papers on estimator selection. There are a bunch more: https://arxiv.org/abs/1604.00923, https://arxiv.org/abs/2502.08021v3, the two mentioned above, and possibly others!)
Questions for authors
Can you look into finite sample guarantees?
3 comments
Awesome!
This is great! I appreciate you taking the time to look into these things and the updated results look very nice. I'll increase my score.
Thank you very much for your kind reply and for increasing your score! We are really grateful for your suggestion of finite-sample guarantees, which nicely complement our asymptotic results and clearly strengthen our paper.
Thank you very much for your thoughtful review and your helpful comments! Below, we address all your comments and suggestions. We have incorporated all new results into the revised version of our paper.
> W + Q: Finite-sample guarantees
Thank you for this suggestion! We followed your suggestion and derived finite-sample guarantees to provide additional insights into the dependence on the BoN budget and the behavior of budget selection, which are especially relevant for high Nmax. We have addressed your comments as follows:
O(nNlog(J/δ)+nNlog(J/δ)),
and explicit dependence on the auxiliary sample size M. Importantly, the dependence on N is polynomial rather than exponential. Intuitively, despite the powers appearing in gN, the BoN importance weights (and their U-statistic estimates) are bounded by N.
Empirical evaluation: We have also added new experiments to evaluate both results on GSM8K (new Appendix F.1, Tables 9 and 10). The finite-sample intervals cover the oracle value in every run, and the finite-sample rule never selects a harmful budget. As expected, both are conservative: the rule selects much smaller budgets (mean 1.0 to 4.1, compared with 24.0 to 106.7 for the asymptotic rule) and thus gives up part of the gain.
Action: We have added the finite-sample guarantees and their empirical evaluation to our new Appendix F, and we cross-reference them in the main text.
> Additional references
Thank you also for pointing us to the relevant literature on finite-sample OPE (Jiang & Li, 2016; Wang et al., 2017) and estimator selection (Thomas & Brunskill, 2016; Su et al., 2020; Tucker & Lee, 2021; Liu et al., 2025). We have incorporated these references and discussed them in our extended related work.
Action: We have included the suggested references in our extended related work.