- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies contextual apple tasting, where the learner must decide whether to accept or reject, the true label is only observed when accepting. The paper proposes two algorithms: LogCBPSide-AT, which is based confidence-bound methods to logistic models, and LogCB-AT, which uses an online log-loss regression oracle. They establish sublinear regret guarantees, including an instance-dependent bound for the first algorithm, and evaluate both methods on adaptive LLM cascading.
Critical strengths
The paper proposes two algorithms for contextual apple tasting: LogCBPSide-AT, a confidence-bound approach for logistic models, and LogCB-AT, a reduction-based method using an online log-loss regression oracle. The authors establish sublinear regret upper bounds, including an instance-dependent guarantee for LogCBPSide-AT, and evaluate the proposed methods on adaptive LLM cascading.
Critical weaknesses
The theoretical contribution would benefit from a clearer discussion of lower bounds. The paper describes its regret guarantee as minimax-optimal by referring to known lower bounds for apple tasting and partial monitoring, but it is unclear whether these lower bounds directly apply under the specific logistic realizability assumptions considered here.
My main concern is that the paper does not demonstrate sufficient novelty or significance relative to the existing literature. Both proposed algorithms closely follow established frameworks, and the theoretical improvements are not convincingly distinguished from prior results. In addition, important related work on online selective classification and learning to defer is missing, while the experimental evaluation is limited and does not directly validate the claimed accuracy–cost trade-off. Taken together, these issues substantially weaken the paper's contribution and motivate my recommendation for rejection.
The experimental evaluation is also quite limited. The authors compare their methods against only two baselines, SquareCB.G-AT and PG-TS, without considering relevant approaches from the learning-to-defer, online selective classification, or LLM cascading literature. This makes it difficult to assess whether the proposed methods offer meaningful improvements over existing alternatives.
Gangrade, A., Kag, A., Cutkosky, A., & Saligrama, V. (2021). Online Selective Classification with Limited Feedback. NeurIPS
Tavor Z Baharav, Spyros Dragazis, and Aldo Pacchiano. The good, the bad, and the sampled: a no-regret approach to safe online classification. International Conference on Artificial Intelligence and Statistics, 2026
Zhang, M., Zhang, Y., Vrousgou, O., Luo, H., & Mineiro, P. (2023). Practical Contextual Bandits with Feedback Graphs. NeurIPS.
Mozannar, H., & Sontag, D. (2020). Consistent Estimators for Learning to Defer to an Expert. ICML 2020.
Questions for authors
Given the extensive prior work on contextual apple tasting, partial monitoring, and online selective classification, what are the main conceptual and technical contributions that distinguish this paper from existing approaches, particularly CBPSide and SquareCB.G?
How does the proposed formulation differ from existing learning-to-defer and online selective classification frameworks, such as Gangrade et al. (NeurIPS 2021), which already study online decisions under one-sided label feedback?
Why all this related literature was not included ?
Are the bounds truly minimax optimal?
What additional baselines and benchmarks can be considered ?
7 comments
Q2
2. How does the proposed formulation differ from ~:
Thanks for bringing our attention on online classification with one-sided feedback!
First, on Gangrade et al. (2021). Indeed, their paper has the same feedback structure and can be applied to our LLM application. However, a critical difference is that their algorithm is not cost-aware. In apple tasting, The loss matrix can be parameterized by the willingness to pay for an improvement in accuracy. That is, let be the cost difference between LLM and SLM, we can designate and set . Then, for large enough , the outcome distribution estimator becomes accurate (i.e., outcome will indeed follow ). This leads to the action being . So, here exactly controlls how much we want to trade off the accuracy with cost. If , then we will never query LLM, and if , we will always try to query LLM. Such a behavior is exactly what lacks from Gangrade et al. (2021).
Relatedly, the target error metric there is also simply the number of mistakes and the excess abstains. Our error metric is regret, which can be written as where and are the number of false positives and negatives up to time . This exactly reflects how we tradeoff FP and FN.
For the implementation, unfortunately, Gangrade et al. (2021) assume finite hypothesis space. Inspecting their experiments, they really use a finite number of classifiers, and thus cannot be applied to our experiment suite.
About Baharav et al. (2026), SCOUT also shares the one-sided feedback structure, but it solves a different decision problem, so it cannot be plugged into our evaluation without changing the algorithm itself.
First, SCOUT has three actions (test, predict 0, predict 1): its optimal rule tests only on a band around the Bayes boundary and predicts labels elsewhere without feedback. In LLM cascading, predicting a disagreement without invoking the LLM yields no answer; SCOUT would count such rounds as correct, whereas they are exactly the missed escalations penalized by .
Second, like Gangrade et al. (2021), SCOUT is not cost-aware: it minimizes the number of tests subject to a symmetric misclassification-rate budget , rather than trading off accuracy against cost through . In general, no choice of recovers our rule , and its regret (excess tests over an oracle that knows and the context distribution) is not comparable to ours.
Third, its guarantees require i.i.d. contexts with a bounded density, whereas our analysis makes no distributional assumption on contexts.
Regarding Mozannar and Sontag (2020), the difference lies in the learning setting, because their training does not involve one-sided feedback. In their main setting, they train a classifier and a rejector offline, on a pre-collected i.i.d. sample annotated with ground-truth labels and expert predictions, and they establish the consistency of a surrogate loss. We instead consider a realistic online deployment, in which our routing algorithm starts without ground-truth answers or pre-collected LLM responses and must route from the first query. In this deployment, model disagreement is observed only when the algorithm invokes the LLM. Each observation is therefore obtained at the cost of an LLM invocation, and the feedback that the algorithm receives depends on its own decisions. For this setting, we provide algorithms with cumulative regret guarantees.
Gangrade, A., Kag, A., Cutkosky, A., & Saligrama, V. (2021). Online Selective Classification with Limited Feedback. NeurIPS.
Baharav, T. Z., Dragazis, S., & Pacchiano, A. (2026). The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification. AISTATS.
Mozannar, H., & Sontag, D. (2020). Consistent Estimators for Learning to Defer to an Expert. ICML.
Q3,4,5
3. Why all this related literature was not included?:
Zhang et al. (2023), Practical Contextual Bandits with Feedback Graphs, is already discussed in Section 3 (Related Work), and its apple tasting specialization is used as an experimental baseline in Section 6. Section 5 includes a dedicated comparison between LogCB-AT and SquareCB.G, and Appendix B further compares their regret bounds.
For the other papers, please refer to our response to Question 2 (“How does the proposed formulation differ from…”).
Zhang, M., Zhang, Y., Vrousgou, O., Luo, H., & Mineiro, P. (2023). Practical Contextual Bandits with Feedback Graphs. NeurIPS.
4. Are the bounds truly minimax optimal?: We should also clarify the scope of our claim: we formulate apple tasting as a locally observable partial monitoring game, and our optimality claim concerns the order of only, in line with the classification theorem for finite partial monitoring games (Bartók et al., 2011). Yes this lower bound is applicable even with realizability condition. Moreover, We make no claim of optimality in .
Apart from this, apple tasting can be cast as a contextual bandit problem through a column-wise transformation of the loss matrix, so the contextual bandit lower bound of applies here as well. LogCB-AT attains this rate given a suitable estimation oracle.
For LogCBPSide-AT the additional factor arises for the same reason it does in confidence-based contextual bandit algorithms: LinUCB (Chu et al., 2011) likewise incurs rather than . We expect that a SupLinUCB-style (Chu et al., 2011) adaptation would remove it, though we have not pursued this.
Chu, W., Li, L., Reyzin, L., & Schapire, R. E. (2011). Contextual Bandits with Linear Payoff Functions. AISTATS.
Bartók, G., Pál, D., & Szepesvári, C. (2011). Minimax regret of finite partial-monitoring games in stochastic environments. COLT.
5. What additional baselines and benchmarks can be considered?:
We included all directly applicable and implementable contextual apple tasting baselines known to us. Among the suggested related works, SquareCB.G (Zhang et al., 2023) is directly applicable and is already included as the SquareCB.G-AT baseline. As explained in our response to Question 2 (“How does the proposed formulation differ from…”), the other suggested works differ in their learning settings and objectives, so we do not consider them directly suitable as baselines for our evaluation. However, our current evaluation primarily focuses on cumulative regret, and we are conducting additional experiments to examine the accuracy–cost trade-off.
Zhang, M., Zhang, Y., Vrousgou, O., Luo, H., & Mineiro, P. (2023). Practical Contextual Bandits with Feedback Graphs. NeurIPS.
Q1
1. Given the extensive prior work on contextual apple tasting, ~: Both LogCB-AT and SquareCB.G build on SquareCB, but their apple-tasting policies differ. SquareCB.G (Zhang et al., 2023, Eq. 7) always accepts when Accept is greedy, whereas LogCB-AT randomizes between both actions on every round. This parallels the distinction between deterministic UCB selection (Auer et al., 2002) and randomized Thompson sampling (Agrawal & Goyal, 2012).
The analyses also substantially differ. SquareCB.G uses a graph-aware DEC-based regret analysis. Our key technical contribution is a case-wise regret decomposition that directly accounts for the asymmetric feedback. We first partition rounds by the greedy action and, when Reject is greedy, further distinguish by the true optimal action. By applying case-specific inequalities, we bound the regret in each case using prediction-error terms weighted by the Accept probability, which correspond to the expected prediction errors over Accept rounds and can thus be directly controlled by the oracle guarantee. Crucially, we avoid the growing Reject-to-Accept probability ratio arising in a direct application of the standard SquareCB analysis to account for the discrepancy between Reject and Accept rounds, as feedback is observed only in Accept rounds, and establish the regret guarantee for our fully randomized policy.
The learning oracle also differs. SquareCB.G uses a square-loss oracle for action-loss prediction, whereas LogCB-AT uses a log-loss oracle for a shared binary outcome. For logistic-linear models, log-loss is convex in the parameters, while squared loss applied to the same sigmoid predictor need not be convex. We connect the log-loss guarantee to the revealing-probability-weighted prediction errors through KL divergence, obtaining O(TRegKL(T)) expected regret.
In addition, LogCBPSide-AT provides a polylogarithmic regret bound under a uniform gap condition in the logistic setting.
Zhang, M., Zhang, Y., Vrousgou, O., Luo, H., & Mineiro, P. (2023). Practical Contextual Bandits with Feedback Graphs. NeurIPS.
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-Time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47, 235–256.
Agrawal, S., & Goyal, N. (2012). Analysis of Thompson Sampling for the Multi-armed Bandit Problem. COLT.