acceptodds
Under review as a conference paper at ICLR 2027

Efficient Algorithms for Contextual Apple Tasting with Log-Loss

Abstract

This paper introduces two novel algorithmic approaches designed for the Contextual Apple Tasting problem, where the learner faces an asymmetric feedback structure by observing binary labels only upon an 'Accept' action. To address the inherent decision bias and exploration challenges, we propose two distinct but complementary strategies. First, we introduce LogCBPSide-AT, an algorithm leveraging Confidence Bounds for Partial monitoring (CBP) to explicitly quantify predictive uncertainty and effectively balance the exploration-exploitation trade-off. Second, we present LogCB-AT, an approach that reduces the apple tasting problem to an online regression oracle. This reduction-based strategy offers a computationally efficient and scalable alternative that fundamentally bypasses the complex, often intractable confidence bound constructions required by traditional methods. Theoretically, we prove that both algorithms achieve sublinear regret bounds for losses associated with the binary outcomes, guaranteeing robust performance even under fundamentally restricted feedback. The practical utility of our methods is empirically validated through adaptive Large Language Model (LLM) cascading, where they effectively optimize the trade-off between inference cost and response accuracy.

Primary area:
learning theory
Keywords:
contextual bandit, apple tasting, llm cascading

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RqC8OpenReview ↗
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

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(TReg⁡KL(T))O(\sqrt{T\operatorname{Reg}_{\mathrm{KL}}(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.

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 Δc\Delta c be the cost difference between LLM and SLM, we can designate λ>Δc\lambda > \Delta c and set (ℓ01,ℓ10,ℓ11)=(λ,Δc,Δc)(\ell_{01}, \ell_{10}, \ell_{11}) = (\lambda, \Delta c, \Delta c). Then, for large enough TT, the outcome distribution estimator f^(x)=σ(xt⊤θ^)\hat f(x)= \sigma(x_t^\top \hat\theta) becomes accurate (i.e., outcome will indeed follow y∼Bernoulli(f^(x))y\sim \mathrm{Bernoulli}(\hat f(x))). This leads to the action being 1f^(x)>Δc/λ\mathbf{1}\\{\hat{f}(x) > \Delta c / \lambda\\}. So, λ\lambda here exactly controlls how much we want to trade off the accuracy with cost. If λ=Δc\lambda = \Delta c, then we will never query LLM, and if λ→∞\lambda \rightarrow \infty, 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 ℓ10FPT+(ℓ01−ℓ11)FNT\ell_{10} FP_T + (\ell_{01}-\ell_{11}) FN_T where FPTFP_T and FNTFN_T are the number of false positives and negatives up to time TT. 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 ∣x⊤θ∗∣≤τ∗|x^\top \theta^* | \leq \tau^* 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 ℓ01\ell_{01}.

Second, like Gangrade et al. (2021), SCOUT is not cost-aware: it minimizes the number of tests subject to a symmetric misclassification-rate budget ϵ\epsilon, rather than trading off accuracy against cost through λ\lambda. In general, no choice of ϵ\epsilon recovers our rule 1f^(x)>Δc/λ\mathbf{1}\\{\hat{f}(x) > \Delta c/\lambda\\}, and its regret (excess tests over an oracle that knows θ∗\theta^* 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.

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 TT 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 dd.

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 Ω(dT)\Omega(\sqrt{dT}) applies here as well. LogCB-AT attains this rate given a suitable estimation oracle.

For LogCBPSide-AT the additional d\sqrt{d} factor arises for the same reason it does in confidence-based contextual bandit algorithms: LinUCB (Chu et al., 2011) likewise incurs O~(dT)\tilde{O}(d\sqrt{T}) rather than O~(dT)\tilde{O}(\sqrt{dT}). 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.

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

This paper studies contextual apple tasting with log-loss, where the feedback is only available at the revealing action. The author considered two setting and provided two corresponding algorithms. The first algorithm is an upper confidence bound-based algorithm and the paper indicates that the algorithm has an regret upper bound of O~(dT)\tilde{O}(d\sqrt{T}) minimax lower bound and an O~(d2log⁡2T/Δ)\tilde{O}(d^2 \log^2 T/\Delta). The paper further consider the setting where a log-loss regression oracle is available. Under this setup, the paper proposed a reduction that leads to an regret upper bound of O(TRegret(T))O(\sqrt{T\text{Regret}(T)}), which realized to O(dTlog⁡T)O(\sqrt{dT\log T}) under certain regression oracles. The paper further verified proposed algorithms on LLM cascading tasks.

Critical strengths
  1. The paper proposes two algorithms with both theoretical guarantees and empirical advantage.
  2. The paper provides detailed illustrations of certain algorithmic design ideas.
Critical weaknesses

I do not see any major weakness of this paper. Some minor issues and my questions are listed as follows

  1. The paper focuses on apple tasting, but is largely restricted to log-loss, making the scope of the paper relatively narrow.
  2. The paper provides little discussion about why log-loss is interesting, and how it change the behavior of the problem.
    1. While log-loss is indeed a natural objective for modeling binary objectives, it might not be the default objective for specific tasks. The introduction does provide several example tasks, but all focuses on the how these tasks leads to apple tasting feedback, lacking a illustration of why log-loss should be considered in these cases.
    2. The paper does not mention how the log-loss changes the decision making problem. A comparison with the result of contextual apple tasting with standard objective will enhance the paper
  3. The paper does not provide a regret lower bound on this problem. Moreover, it looks like that Algorithm is loose from the optimal regret by at least a factor of Ω(d)\Omega(\sqrt{d}). It would be helpful if the paper could provide some explanation on how such extra dependence might be removed or if there is any substantial difficulties.
Questions for authors

See Weakness.

2 comments

Thank you for your thoughtful review and constructive feedback.

1. The paper focuses on apple tasting, ~, 2. The paper provides little discussion about why log-loss is interesting, ~: While the paper focuses on log-loss, our algorithmic frameworks and analyses can readily accommodate square-loss oracles for continuous outcomes. For LogCB-AT, the modification is straightforward as well, as the algorithm builds upon the SquareCB framework, and can naturally accommodate a square-loss oracle. Importantly, this yields a fully randomized algorithm that is distinct from the existing SquareCB.G algorithm. Thus, our contributions are not fundamentally restricted to log-loss. We are running additional experiments to evaluate this square-loss variant of LogCB-AT as a baseline.

Meanwhile, our focus on log-loss is motivated by the inherently binary nature of apple-tasting feedback and its relevance to modern applications of interest. For example, in LLM routing, the relevant feedback is whether the SLM and LLM responses agree, while in digital healthcare, the outcome often indicates the presence or absence of a disease. Although such binary outcomes can also be modeled using square loss, log-loss provides a natural objective for probabilistic modeling of binary outcomes and imposes an increasingly severe penalty on confidently incorrect predictions, unlike the bounded square loss. Moreover, analyzing log-loss introduces additional theoretical challenges compared to square loss, making our results of independent theoretical interest.

Log-loss determines how the predictor is trained, while the loss matrix determines how its predictions are used to make decisions. Varying the matrix entries changes the relative costs of acceptance and rejection and the resulting decision threshold α=ℓ10/(ℓ10+ℓ01−ℓ11)\alpha=\ell_{10}/(\ell_{10}+\ell_{01}-\ell_{11}), allowing different cost settings. LogCB-AT also supports general realizable function classes whenever a suitable online log-loss oracle is available.

We agree that these motivations and the applicability of our frameworks beyond log-loss should be better highlighted, and will expand the discussion in the introduction accordingly.

3. The paper does not provide a regret lower bound on this problem. ~: Thank you for raising 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 Ω(dT)\Omega(\sqrt{dT}) applies here as well. LogCB-AT attains this rate given a suitable estimation oracle.

For LogCBPSide-AT the additional d\sqrt{d} factor arises for the same reason it does in confidence-based contextual bandit algorithms: LinUCB (Chu et al., 2011) likewise incurs O~(dT)\tilde{O}(d\sqrt{T}) rather than O~(dT)\tilde{O}(\sqrt{dT}). We expect that a SupLinUCB-style (Chu et al., 2011) adaptation would remove it, though we have not pursued this.

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 TT only, in line with the classification theorem for finite partial monitoring games (Bartók et al., 2011). We make no claim of optimality in dd.

Chu, W., Li, L., Reyzin, L., & Schapire, R. E. (2011). Contextual Bandits with Linear Payoff Functions. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 15, pp. 208–214.

Bartók, G., Pál, D., & Szepesvári, C. (2011). Minimax regret of finite partial-monitoring games in stochastic environments. In Sham M. Kakade and Ulrike von Luxburg (eds.), Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pp. 133–154, Budapest, Hungary, 09–11 Jun 2011. PMLR.

I thank the author for the detailed responses. I do not have any remaining concerns.

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

The paper studies contextual apple tasting, a sequential decision problem with asymmetric feedback: the learner accepts or rejects each instance but observes its binary outcome only upon acceptance. The goal is to minimize cumulative regret under asymmetric losses.

The authors propose two algorithms:

  1. LogCBPSide-AT adapts confidence-bound methods from contextual partial monitoring to logistic models. It achieves an instance-independent regret bound of O~(dT)\widetilde O(d\sqrt T) and a polylogarithmic instance-dependent bound under a uniform separation condition.
  2. LogCB-AT reduces the problem to online regression with log loss, supporting general realizable function classes with a suitable regression oracle. Its expected regret is O(TReg⁡KL(T))O(\sqrt{T\operatorname{Reg}_{KL}(T)}).

The algorithms are evaluated on adaptive LLM cascading, where a policy routes queries to a small or larger language model. Across four question-answering datasets, both methods achieve lower cumulative experimental loss than SquareCB.G and Pólya–Gamma Thompson Sampling, with LogCBPSide-AT performing best.

Critical strengths

Strength 1: A general oracle-based reduction with a substantive regret analysis

LogCB-AT is the paper’s strongest contribution, providing an oracle-based approach to contextual apple tasting without explicit confidence sets.

The analysis addresses a key difficulty: the online regression oracle does not directly control prediction errors for the non-revealing action. A case-wise regret decomposition accounts for the revealing-action probability and yields expected regret of O(TReg⁡KL(T))O(\sqrt{T\operatorname{Reg}_{KL}(T)}).

This reduction could allow apple tasting algorithms to benefit from advances in online probabilistic prediction beyond logistic-linear models.

Strength 2: Complementary worst-case and instance-dependent guarantees

The two algorithms offer complementary modeling and theoretical benefits. LogCBPSide-AT achieves an instance-independent O~(dT)\widetilde O(d\sqrt T) regret bound and a polylogarithmic bound under a positive uniform gap condition, while LogCB-AT supports broader function classes through an online regression oracle.

Together, they clarify the trade-off between exploiting parametric structure for stronger instance-dependent guarantees and accommodating more general predictive models.

Critical weaknesses

Weakness 1: The experimental objective does not establish improved LLM accuracy

The experiments define the binary outcome as disagreement between the small and large language models. Yet disagreement does not establish that the larger model is more accurate, and agreement does not establish correctness.

When the smaller model is correct and the larger model is wrong, the evaluation still favors invoking the larger model on a disagreement instance, potentially reducing task accuracy. Thus, minimizing the reported cumulative loss need not improve the claimed inference cost–accuracy trade-off.

Because LLM cascading is the main practical motivation and empirical application, this limits the conclusions: the experiments demonstrate effective routing based on model disagreement, but not improved answer correctness or actual inference efficiency. Ground-truth correctness, measured inference costs, and accuracy–cost curves would strengthen the evaluation.

Weakness 2: The experiments do not fully align with the theory or support efficiency claims

Hyperparameters are selected by minimizing final cumulative regret on the evaluated datasets rather than through independent validation, potentially making the comparisons optimistic.

LogCBPSide-AT also uses a tuned confidence-width parameter, cw=0.01c_w=0.01, while its guarantees require a specifically constructed confidence radius. It is therefore unclear whether the implementation meets the theoretical conditions.

Finally, the paper reports cumulative regret without wall-clock runtime, per-round update costs, or scalability comparisons. These measurements matter because LogCBPSide-AT repeatedly fits regularized logistic models, while LogCB-AT assumes an efficient online regression oracle. The current evidence therefore provides limited support for the claimed practical efficiency and scalability.

Questions for authors
  1. Evaluation objective: Can the authors evaluate routing using ground-truth correctness and actual inference costs? Does the advantage persist under an accuracy–cost objective rather than a model-disagreement proxy?

  2. Hyperparameter selection and implementation: Were hyperparameters tuned on the datasets and runs used for the reported comparisons? Can the authors provide results with independent validation and clarify how the tuned confidence width relates to the theoretical confidence radius?

  3. Theoretical assumptions: Appendix C, Lemma 5 appears to need further restrictions on λ\lambda or a modified elliptical potential bound. What justifies its use for arbitrary λ>0\lambda>0? How does δt=1/t\delta_t=1/t satisfy the strict conditions of Proposition 1?

  4. Computational efficiency: Can the authors report per-round update times and total runtimes for both algorithms and the baselines? Which online log-loss oracle was used, and how does its complexity scale with the model class?

5 comments

Thank you for your thoughtful review and constructive feedback.

1. Evaluation objective: We are running additional experiments to evaluate ground-truth answer accuracy at different LLM invocation rates and will share the results as soon as the experiments are complete. In the additional evaluation, ground-truth answers are used only to measure accuracy; the routing algorithm learns from model disagreement alone. We use the LLM invocation rate as a proxy for inference cost.

However, our main contribution is theoretical, with LLM cascading as an application. We chose the original evaluation objective to match the asymmetric loss studied in the paper: it penalizes invoking the LLM when the models agree and keeping the SLM answer when they disagree. In a realistic online deployment, the correctness of a response cannot be immediately verified, whereas model disagreement can be readily observed upon invoking the LLM. Thus, learning from disagreement rather than ground-truth correctness makes our algorithm more practical for online deployment. Therefore, we believe the weakness of the agreement based routing is not the weakness of our formulation but rather a real-world constraint.

2. Hyperparameter selection and implementation: We selected hyperparameters by grid search on the evaluated datasets, using the lowest mean final cumulative routing loss over ten seeds. We consider our comparison fair because we tuned only one hyperparameter per algorithm using the same selection criterion, and our aim was to compare each method’s best achievable performance.

Furthermore, the same protocol is used in related online-bandit experiments. SquareCB.G (Zhang et al., 2023) grid-searches its exploration coefficient and oracle learning rate, and its released code confirms that the exploration coefficient is selected by minimizing the final cumulative loss on the evaluated data. NeuralUCB (Zhou et al., 2020) likewise reports choosing the best grid-searched parameters without describing a separate validation split, and uses a fixed, tuned confidence scaling factor instead of the time-dependent factor specified in its theoretical analysis.

For LogCBPSide-AT, we likewise tuned cwc_w for empirical performance rather than using the theoretically prescribed confidence width directly. The value cw=0.01c_w=0.01 was selected through the same grid-search procedure.

In fact, outside online learning literature, the same is true for the step size of stochastic gradient descent in deep learning -- the right choice of step size is studied by theory but people tune the learning rate with test set all the time.

Zhang, M., Zhang, Y., Vrousgou, O., Luo, H., & Mineiro, P. (2023). Practical Contextual Bandits with Feedback Graphs. NeurIPS.

Zhou, D., Li, L., & Gu, Q. (2020). Neural Contextual Bandits with UCB-based Exploration. ICML.

3. Theoretical assumptions: We thank the reviewer for catching this. The condition should indeed read λ≥1\lambda \geq 1 rather than λ≥0\lambda \geq 0; this is a typo, and we will correct it in the revised manuscript.

Regarding the choice of δt\delta_t: the reviewer is right that our analysis also requires δt≤min⁡1,d/e\delta_t \leq \min\\{1, d/e\\}, which we did not state. The correct choice is δt=min⁡1/t,,d/e\delta_t = \min\\{1/t,\\, d/e\\}. We note that 1/t1/t violates this constraint only when t≤2t \leq 2, since 1/t≤d/e1/t \leq d/e holds for every t≥3t \geq 3 and every d≥1d \geq 1. The first two rounds contribute at most a constant to the regret and can be bounded separately, so the theorem statement is unaffected. We will make both the corrected choice of δt\delta_t and this remark explicit in the revision.

4. Computational efficiency: We will report per-round update times and total runtimes for both proposed algorithms and the baselines once the additional experiments are complete. We also note that by “efficient” in LLM cascading, we meant reducing LLM invocations.

Our log-loss oracle is L2L_2-regularized logistic regression fitted using L-BFGS-B, and was used for both LogCBPSide-AT and LogCB-AT to isolate the effects of the bandit algorithms from differences in oracle implementation. The log-loss regret of this regularized MLE can also be shown to be O(dlogT)O(d \mathrm{log}T), mathching the order of ONS-GLM. (The proof leverages the Lemma 2.10 of Shalev-Shwartz (2025), curvature of the regularized logistic loss function, the Lipschitz continuity of logistic loss, and the elliptical potential lemma.)

Shalev-Shwartz, S. (2025). Online learning and online convex optimization. Foundations and Trends® in Machine Learning, 4(2), 107-194.

Please see our comment to all reviewers titled Additional Experiments for the accuracy–cost and runtime results.

Thank you for the detailed response.

Re Q1, I agree that model disagreement is a reasonable feedback signal. My concern is primarily whether minimizing disagreement-based loss translates into improved answer accuracy. Even if correctness is hard to verify, there are other ways to get surrogate signals that are at least as good as model disagreement. And additional results on accuracy-cost does not seem to be very strong.

Re Q2 & Q3 & Q4: this detail clarification sounds good to me. the theory correction also appears reasonable. the added results on computation efficiency also makes sense.

Overall, my concern remains: optimizing against disagreement does not seem to be the best strategy here. I lean to keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Additional Experiments

Dear all reviewers,

Due to time and resource constraints, we report accuracy–cost results only on ARC-Challenge. Ground-truth answers were used only for evaluation; the algorithms learned from model disagreement alone. SquareCB-AT is a variant of LogCB-AT that replaces log-loss with square loss in oracle training, inspired by Reviewer LAD1’s suggestion.

We fixed the algorithm parameters at the values used for the regret comparison in Table 1 of the paper and varied Lmiss=ℓ01−ℓ11L_{\mathrm{miss}}=\ell_{01}-\ell_{11}, the additional loss of retaining the SLM answer when the models disagree. Larger values encourage more LLM calls; smaller values favor fewer. The original regret experiments fixed Lmiss=0.5L_{\mathrm{miss}}=0.5.

The table reports accuracy (%) over 5 seeds at different LLM invocation rates, with standard deviations in parentheses. We linearly interpolated between neighboring observed points when exact target invocation rates were unavailable.

AlgorithmParameter25% calls50% calls75% calls
LogCBPSide-ATc_w = 0.0135.06 (0.27)40.56 (0.41)45.48 (0.23)
LogCB-ATgamma = 6435.37 (0.49)40.96 (0.50)45.38 (0.38)
SquareCB-ATgamma = 6435.38 (0.49)40.77 (0.33)45.31 (0.40)
SquareCB.G-ATgamma = 6435.06 (0.55)40.70 (0.34)45.21 (0.27)
PG-TSM = 1534.69 (0.53)39.97 (0.48)45.07 (0.34)
Random cascading-34.1938.9543.71
  • LogCB-AT achieves higher mean accuracy than SquareCB.G-AT at all three invocation rates and than SquareCB-AT at 50% and 75% calls, and LogCBPSide-AT attains the highest mean accuracy among all methods at 75% calls. Although the differences are within the reported standard deviations, these trends suggest potential benefits from log-loss-based learning and our fully randomized rule.
AlgorithmMean runtime per execution (minutes, mean ± SD)
LogCBPSide-AT0.182 ± 0.145
LogCB-AT0.0403 ± 0.0372
SquareCB-AT0.00362 ± 0.00217
SquareCB.G-AT0.00554 ± 0.00290
PG-TS8.61 ± 7.46
  • The runtime gap may reflect oracle differences: LogCBPSide-AT, LogCB-AT use iterative L-BFGS-B fitting because logistic regression lacks a closed-form solution, whereas SquareCB-AT and SquareCB.G-AT use incremental ridge updates.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.