acceptodds
Under review as a conference paper at ICLR 2027

Minimum Certified Exploration for Contextual Bandits

Abstract

We present an algorithm that explores only as much as a regret guarantee actually requires, for general contextual bandits with a regression oracle. We introduce a one-step regret certificate: a closed-form test of whether the one-step inequality behind the regret analysis holds at the current predictions, so that every certified allocation inherits the full regret guarantee. The certified allocations have a least element, one distribution that minimizes every nongreedy probability at once, and our algorithm MinCE (Minimum Certified Exploration) computes it in a few sweeps of scalar inversions, with no additional oracle call or hyperparameter and with every intermediate allocation certified. MinCE matches the best existing first-order regret bound and the minimax rate while performing minimal exploration. In simulations MinCE attains the lowest regret, and on 130 OpenML classification datasets it achieves the lowest loss on 112 of them, outperforming the baselines.

Primary area:
learning theory
Keywords:
contextual bandits, exploration

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_x8nHOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper asks how little exploration a regression-oracle contextual bandit really needs while keeping a first-order regret bound. The authors turn the one-step inequality behind FastCB into a certificate on the action distribution, show that the certified set has a coordinatewise least element, and give a finite sweep algorithm for finding it. They also give a regret bound and experiments on synthetic problems plus 130 OpenML datasets.

Critical strengths

The certificate idea is clean and useful. It turns something that is normally just an analysis device into an explicit allocation problem, and the least-element property gives a concrete object to compute. I also like that the method needs no extra oracle call and that the finite procedure is designed to stay certified at every sweep.

Critical weaknesses

My main concern is what “minimum exploration” means here. The paper proves minimality inside the allocations satisfying this particular certificate. It does not show that no policy with the same regret guarantee can explore less, and the regret bound itself is the same as FastCB. This should be stated much more carefully; otherwise the abstract sounds stronger than the theorem.

The empirical section also does not isolate the allocation rule. MinCE and FastCB get different feedback because each learner follows its own actions, and the reported baselines appear to use quite different exploration budgets. A fixed prediction sequence replayed through MinCE, FastCB, and a matched-greedy-rate baseline would be much more convincing than the 112/130 count. As written, the large gain on OpenML may come from the tuning or from the baselines being nearly uniform, not from the new certificate.

Questions for authors
  1. Is there a lower bound over all policies that keep the stated regret guarantee, or only over allocations satisfying this certificate?
  2. Can you replay one fixed prediction trajectory through FastCB, MinCE, and a pure-greedy or matched-greedy-rate baseline?
  3. How were the budget parameters for SquareCB and SpannerIGW chosen, and why do their greedy probabilities look so low?
  4. What was the selection rule for the 130 OpenML datasets, and can you report paired uncertainty for the 112/130 count?
7 comments

We sincerely thank the reviewer for the time and the assessment that the certificate idea is "clean and useful". We have uploaded a revised manuscript. It is strengthened in response to the reviews: a characterization of the exploration minimum over all prediction-based rules (Appendix F), Greedy, ϵ\epsilon-greedy and tuned-γ\gamma baselines (Appendices I.4 and I.5), an analysis of MinCE's allocation during learning (Appendix I.6), and an OpenML evaluation extended to 300 datasets with paired statistics against every method.

Every question in the review is answered with a theorem or an experiment. The minimum is a theorem over all rules that act on the oracle's predictions (Appendix F). The allocation rule is isolated by the fixed-prediction replay the review asks for, by a result that holds at every prediction vector, by an experiment with a provable shared oracle in which nothing is tuned, and by every matched baseline the review mentions.

QuestionAnswer
Main concern and Q1: is the minimum only over allocations that satisfy this certificate?No. We prove that a prediction-based rule keeps the one-step guarantee if and only if it is certified (Corollary 23), so MinCE explores least among all prediction-based algorithms that keep this guarantee. Our exploration lower bounds are not specific to MinCE or to the certificate: they hold for every prediction-based algorithm that keeps the regret bound (Corollary 23(b), Proposition 24).
Q2: replay one fixed prediction trajectory through FastCB, MinCE and a matched-greedy-rate baselineWe ran it. At identical predictions MinCE removes 96% of FastCB's exploration, keeps the certificate on every round, and has lower regret than FastCB (nine times) and than the baseline matched to its greedy probability. End to end, a shared provable oracle with nothing tuned gives the same ordering, and no matched baseline improves on MinCE.
Q3: budgets of SquareCB and SpannerIGWThey follow the formulas of their own papers. With γ\gamma raised by up to 100 times, and with a provable oracle for which SquareCB's γ\gamma is 190 to 380, neither overtakes MinCE.
Q4: dataset selection and paired uncertaintyThe datasets were chosen by criteria that do not involve any method's result, and the collection is extended to 300. Paired statistics are given against all five comparators: MinCE is lower than each method with a guarantee on at least 268 datasets (p<10−9p < 10^{-9} in every case).

Main concern and Q1. "Minimum exploration" is proved over all prediction-based rules

Thanks to the reviewer's feedback, we are very glad to share that minimality is proved over every rule that maps the oracle's predictions to an action distribution and keeps the one-step guarantee of inverse-gap weighting (IGW), not only over "allocations satisfying this particular certificate". The key result (Corollary 23, Appendix F) is an equivalence: such a rule keeps the guarantee for every environment and every oracle if and only if it is certified at every prediction vector. The certified set is therefore not an artifact of our analysis. It is exactly the set of rules with the guarantee, and MinCE is its least element in every nongreedy coordinate.

Call a rule an interface rule if it sees the contexts and the function class only through the oracle's predictions, and stationary if pt=ϕ(y^t)p_t = \phi(\hat y_t). FastCB, SquareCB, ϵ\epsilon-greedy, Greedy and MinCE are all stationary interface rules. The results of Appendix F are:

ResultStatement
Lemma 21, exact accountingFor any predictor and any allocation, the one-step analysis is an identity. Its only slack is the gap between Ψ\Psi at the true means and its maximum Ct(pt)C_t(p_t).
Theorem 22, necessityIf Cy(p)C_y(p) exceeds the threshold κy\kappa_y at some prediction vector yy, an explicit realizable instance makes the expected regret exceed the bound by exactly T(Cy(p)−κy)/(1−ρ)T (C_y(p) - \kappa_y) / (1 - \rho). A second instance does so with oracle regret independent of TT.
Corollary 23(a), characterizationA stationary interface rule keeps the one-step guarantee of IGW for every environment and every predictor if and only if it is certified at every prediction vector. Every such rule therefore puts at least MinCE's probability on each nongreedy action.
Corollary 23(b), regret bound onlyA stationary interface rule keeps the regret bound (10) for every environment and every oracle satisfying Assumption 2 in expectation if and only if Cy(ϕ(y))≤0C_y(\phi(y)) \le 0 everywhere. Every such rule obeys the lower bounds of Theorem 6.
Proposition 24, all interface rulesAny interface rule that keeps (10), stationary or not, must first try nongreedy action jj within expected time 1+Lj/(rh)1 + L_j / (r h), even against oracles whose regret is a constant on every sequence.
Proposition 26, other constantsFor any constants in the one-step inequality and any threshold, the certified set has a least element and the same necessity holds.

Here ρ=5A/γ\rho = 5A / \gamma, r=(1−ρ)/(14γ)r = (1 - \rho) / (14 \gamma), hh is the greedy prediction and Lj=log⁡(1/(1−y^j))L_j = \log(1 / (1 - \hat y_j)).

Answer to Q1. There are lower bounds at every level at which a lower bound can exist.

  • Rules that keep IGW's one-step guarantee: an exact minimum. By Corollary 23(a) this class coincides with the certified rules, so MinCE is the coordinatewise least-exploring rule in it. The statement does not depend on our particular analysis.
  • Rules that keep only the final regret bound (10): matching lower bounds. Every such stationary rule obeys the lower bounds of Theorem 6 (Corollary 23(b)). In the confident regime of Theorem 6, MinCE's total exploration is within a factor 15.1 of the least possible for any such rule, and within 2.01 asymptotically. For rules that are not stationary, Proposition 24 gives a lower bound on how soon each nongreedy action must be tried.
  • "All policies" is not the right class for any method in this literature. Exploration is defined relative to the oracle's greedy action, and what forces it is the oracle interface. An algorithm with direct access to a class that contains a single function needs no exploration at all, so no nontrivial lower bound over all policies exists for FastCB, SquareCB or any other method. Within the oracle interface, which is the model of the regression-oracle literature, our characterization is complete.

The abstract states exactly this. It says that MinCE explores only as much as is needed to preserve the one-step regret guarantee of IGW, and that no rule mapping predictions to an action distribution can preserve it while exploring less. This is Corollary 23(a). Section 4.4 and Appendix F state the scope.

"The regret bound itself is the same as FastCB": this is the point of the paper. FastCB's first-order bound already matches the minimax rate up to a lower-order additive term, so the leading-order rate cannot be improved. What can be improved is the exploration paid for that rate, and this matters both in theory and in practice. In theory, Theorem 2 shows that removing the exploration costs nothing in the bound, Appendix F shows that nothing more can be removed, and Theorem 6 says when the saving exceeds a constant factor. In practice, the saving is what drives regret: with the same oracle and the same γ\gamma, MinCE's regret is 51% to 95% below FastCB's across our synthetic experiments.

Q2. The allocation rule is isolated: the requested replay, a theorem, and three end-to-end controls

We ran the replay the review asks for. Identical prediction vectors are passed, round by round, through FastCB, MinCE and a baseline matched to MinCE's greedy probability.

Protocol. The prediction trajectories come from the four realizable tasks of the provable-oracle experiment (linear or logistic rewards, fixed or noisy features, A=5A = 5, d=4d = 4, T=5,000T = 5{,}000, ten seeds; the setup is given under Control 2 below). At every round all rules receive the same saved prediction vector and the same γ\gamma, the value prescribed by the theory. Replayed actions do not update the oracle and probabilities are evaluated exactly, so there is no difference in feedback and no sampling noise. The matched baseline rescales FastCB's nongreedy probabilities so that its greedy probability equals MinCE's at every round, which is a stricter match than an average rate. The table uses the predictions generated by FastCB (40 trajectories, 200,000 prediction vectors). Entries are mean ± SD over 10 seeds, averaged over the four tasks:

Allocation ruleProbability on nongreedy actions (%)Rounds on which the certificate holds (%)Conditional regret on the replay
FastCB17.01 ± 8.8210089.21 ± 20.81
FastCB matched to MinCE's greedy probability0.64 ± 0.340.0310.27 ± 7.95
MinCE0.64 ± 0.341009.87 ± 7.91

Conditional regret by task, on the same predictions (mean ± SD over ten seeds):

Features / rewardFastCBFastCB matched to MinCE's greedy probabilityMinCE
Fixed / linear95.31 ± 20.5411.61 ± 13.2911.04 ± 13.27
Fixed / logistic82.04 ± 26.589.04 ± 8.948.66 ± 8.91
Noisy / linear99.91 ± 17.1614.15 ± 9.9213.78 ± 9.86
Noisy / logistic79.59 ± 25.516.29 ± 2.945.99 ± 2.85
  • At identical predictions, MinCE removes 96% of FastCB's exploration and keeps the certificate on every round. Its probability on nongreedy actions is 0.64% against 17.01%, and its conditional regret is 9.87 against 89.21, nine times lower. With the predictions, the feedback and γ\gamma held fixed, this difference can only come from the allocation rule.
  • At exactly the same greedy probability, MinCE's allocation is better, and it alone keeps IGW's one-step guarantee. The matched baseline has higher conditional regret in all four tasks. It also fails the certificate, which characterizes IGW's one-step guarantee (Corollary 23), on 99.97% of rounds, whereas MinCE satisfies it on every round.
  • The matched baseline cannot be run without MinCE. It takes MinCE's greedy probability at every round as an input, and that probability is the output of the certificate. A fixed γ\gamma, a fixed ϵ\epsilon or a schedule cannot follow it round by round (Control 3).
  • The result does not depend on which learner generated the predictions. Replaying the predictions generated by Greedy and by MinCE gives the same ordering in all 12 combinations of source and task. The conditional regrets of FastCB / matched FastCB / MinCE are 125.41 / 49.75 / 49.41 on Greedy's predictions and 102.51 / 23.65 / 23.27 on MinCE's.

The same comparison holds at every prediction vector, by Theorem 4. The theorem gives pt(a)≤qt(a)p_t(a) \le q_t(a) for every nongreedy action at every prediction vector, so on any trajectory MinCE explores no more than FastCB, in every coordinate and at every round. The size of the gap, at A=10A = 10, γ=10A\gamma = 10A, greedy prediction 0.5 and the other nine at 0.5+g0.5 + g, in total probability on nongreedy actions:

Predicted gap gg00.0010.010.1
FastCB0.900.880.750.30
MinCE0.900.400.0580.007

Control 1: everything except the allocation rule is shared. One learning rate is shared by all methods, so tuning cannot favor a method. FastCB and MinCE share the network, initialization, loss, learning rate, γ=10A\gamma = 10A, seeds, context sequence and action-randomization stream. The only difference is the map from predictions to ptp_t.

Control 2: a provable oracle, with nothing to tune. In this experiment the network and the optimizer are replaced by an oracle with a proved regret bound, so no learning rate, clipping level or tuning seed exists.

Realizable classes. Linear costs fθ(x)=0.5−0.45⟨x,θ⟩f_\theta(x) = 0.5 - 0.45 \langle x, \theta \rangle and logistic costs fθ(x)=σ(−3⟨x,θ⟩)f_\theta(x) = \sigma(-3 \langle x, \theta \rangle), with θ∈Θ={−1/2,+1/2}4\theta \in \Theta = \lbrace -1/2, +1/2 \rbrace^4, so the class has M=16M = 16 functions. The true parameter is drawn uniformly from Θ\Theta and is unknown to the learner. There are A=5A = 5 actions with features in d=4d = 4 dimensions. Features are either fixed over the run or perturbed at every round by Gaussian noise of SD 0.1. Feedback is a Bernoulli cost of the selected action only.

Reviewer_36JTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks how little exploration a contextual bandit algorithm needs while keeping its regret guarantee. It treats the regret analysis as a constraint, shows that a single least exploring allocation satisfies it, and proposes MinCE, which plays that allocation and acts nearly greedily with the same guarantees as prior methods.

Critical strengths
  1. A new and reusable idea: treating the regret inequality as a hard constraint on exploration.

  2. A least element result, with no tradeoff among non-greedy actions.

  3. There is not a lot hyperparameters in the algorithm.

  4. Exploration laws that explain when large reductions are possible.

  5. Consistent average gains over FastCB.

Critical weaknesses
  1. No greedy or ϵ\epsilon greedy baseline, and γ is untuned for all baselines, so it is unclear whether certification matters.

  2. The experiments violate Assumption 2: the oracle budgets are vacuous, so the theory does not cover them.

  3. The clipping level ε effectively controls exploration, with no sensitivity study.

  4. I believe that “Minimum exploration” is overstated because it is the minimum relative to one chosen inequality.

My main objection is about the experiments and the practical usage of the method. If my questions are resolved, I would happily raise my score.

Questions for authors
  1. How does MinCE compare to a purely greedy and to ϵ\epsilon greedy (for example ϵ\epsilon in {0.01,0.05,0.1}\{0.01, 0.05, 0.1\}) using the same neural oracle, learning rate grid, and seeds?

  2. If γ is tuned for FastCB and SquareCB on the tuning seed, over a grid such as {10A, 30A, 100A, 300A, 1000A}, does MinCE still outperform them on the synthetic tasks and on OpenML?

  3. Could you run FastCB with γ chosen to match MinCE’s average greedy probability? This would show whether MinCE’s gains come from how it allocates exploration or simply from exploring less.

  4. What would happen if you just explore in the first steps and then try to be greedy in your experiments?

15 comments

We sincerely thank the reviewer for the time and for the concrete, testable questions. We have uploaded a revised manuscript. It is strengthened in several respects in response to the reviews: Greedy and ϵ\epsilon-greedy baselines (Section 5.2, Appendix I.4), a γ\gamma study for the baselines (Appendix I.5), an analysis of MinCE's allocation during learning (Appendix I.6), additional theory on minimality (Appendix F), and an OpenML evaluation extended to 300 datasets.

Every question is answered with the experiment it asks for, and every weakness with a result. In all of them MinCE, at its untuned default γ=10A\gamma = 10A, is the best method or matches the best baseline after that baseline has been tuned in hindsight. The table lists each request and its outcome, and the evidence follows.

RequestWhat we ran or provedOutcome
Q1: Greedy and ϵ\epsilon-greedy (ϵ\epsilon in 0.01, 0.05, 0.1) with the same neural oracle, learning rate grid and seedsExactly suggested settingsGreedy locks in. The best ϵ\epsilon has 2.4 to 3.6 times MinCE's regret.
Q2: γ\gamma tuned over {10A,30A,100A,300A,1000A}\lbrace 10A, 30A, 100A, 300A, 1000A \rbrace for FastCB and SquareCB, on synthetic tasks and on OpenMLThe suggested grid of γ\gamma, with regret reportsThe best tuned FastCB only reaches the level of untuned MinCE. SquareCB is above MinCE at all 15 synthetic entries and on all 12 OpenML datasets.
Q3: FastCB with γ\gamma matched to MinCE's greedy probabilityGreedy probabilities measured, and the matched γ≈300A\gamma \approx 300A identifiedThe matched FastCB does not improve on MinCE and has a larger variance.
Q4: explore first, then act greedilyCompare Explore-then-commit (ETC) with MinCEETC has at least twice MinCE's regret in all 24 comparisons, and its exploration length cannot be tuned online.
W2: Assumption 2 and vacuous oracle budgetsAn experiment with a provable oracle (regret at most log⁡16\log 16), and Lemma 21The assumptions hold exactly, the oracle budget is the constant log⁡16\log 16, and MinCE is the best method with a guarantee in all 8 settings.
W3: the clipping level ϵ0\epsilon_0Clarificationϵ0=10−6\epsilon_0 = 10^{-6} is only a numerical-stability threshold. It was never active, and γ=10A\gamma = 10A for every ϵ0∈(0,1/2)\epsilon_0 \in (0, 1/2).
W4: "minimum exploration" relative to one inequalityCorollary 23, Theorem 22 and Proposition 26 (Appendix F)The minimum holds over all rules that act on predictions and keep the guarantee.

Important Note

One point should be kept in mind when reading the tuning results below: the exploration parameter of a bandit algorithm cannot be tuned the way a supervised learner's hyperparameters are.

  • There is no criterion to tune by. Regret is never observed by the learner, because it is measured against the optimal action, which the learner does not know. There is no validation set, and a deployed learner cannot rerun the sequence: once a round has been played with one value of the exploration parameter, it cannot go back and play it with another.
  • For an exploration parameter, the cost that is observed is misleading. Each setting sees only the cost of the actions it chose itself. Selecting by observed cost favors the setting that explores least in the short run, which is the one that can lock into a wrong action (Q1).
  • Tuning is not free. To try a parameter value, the learner has to act with it, so every round played with a poor value costs real regret. Even an initial run does not solve this for an exploration parameter for free: over the first rounds the observed cost favors the value that explores least, and the price of that choice, lock-in, appears only later (Q1). The best value also changes from problem/instance to problem/instance (100A100A to 1000A1000A in Q2), so it cannot be carried over from an earlier problem. The best value of a grid is known only after every value has been run on the same problem. It is therefore an idealized reference, not an algorithm that a learner could actually run.

The argument that a baseline "can always be tuned" is therefore very misleading for bandit algorithms (we are sure that the reviewer already understands this, but explicitly state this for general readers). Experienced researchers and practitioners know this well, but it is worth stating explicitly: when an exploration parameter is tuned in hindsight, the reported numbers no longer tell us which algorithm would work once deployed, and good algorithms become hard to tell from bad ones. An algorithm that needs no tuning has a real advantage, and MinCE is such an algorithm: at the default prescribed by the theory, γ=10A\gamma = 10A, it already removes the exploration that the guarantee does not need.

Q1 (W1). Greedy and ϵ\epsilon-greedy with the same oracle, learning rate and seeds

Greedy and ϵ\epsilon-greedy fail where exploration matters, and MinCE has the lowest regret in every setting. We ran both as specified. All methods share the 3×32 tanh network, the initialization, one learning rate from the same grid, and the ten seeds.

The instances punish under-exploration: fixed features, A=d=10A = d = 10, T=5,000T = 5{,}000, one optimal action and highly correlated features, so a learner that initially undervalues the optimal action must explore to find it. Final regret, mean ± SD over 10 repetitions:

MethodLinear rewardLogistic rewardExponential reward
Greedy952.37 ± 1.20279.88 ± 0.35751.96 ± 0.95
ϵ\epsilon-greedy (ϵ=0.01\epsilon = 0.01)398.19 ± 279.19203.83 ± 76.15396.14 ± 227.57
ϵ\epsilon-greedy (ϵ=0.05\epsilon = 0.05)144.23 ± 59.78101.73 ± 28.67134.08 ± 47.89
ϵ\epsilon-greedy (ϵ=0.1\epsilon = 0.1)148.07 ± 38.5483.04 ± 22.07139.00 ± 37.89
SquareCB465.26 ± 4.47206.24 ± 1.09410.25 ± 2.75
SquareCB.L463.92 ± 4.56204.75 ± 0.96408.21 ± 2.73
SpannerIGW379.78 ± 7.25135.60 ± 6.82315.12 ± 7.68
FastCB94.41 ± 7.6775.49 ± 4.3488.04 ± 6.80
MinCE40.44 ± 17.5734.36 ± 12.5043.34 ± 17.59
  • Greedy never recovers. It never plays the optimal action.
  • No value of ϵ\epsilon is good. With ϵ=0.01\epsilon = 0.01 it escapes late and erratically, and with ϵ=0.1\epsilon = 0.1 it keeps paying for random actions. Its best value per column, chosen in hindsight, has 2.4 to 3.6 times MinCE's regret.
  • MinCE has the lowest regret in all three settings: 88–96% below Greedy, 59–72% below the best ϵ\epsilon-greedy, and 51–57% below FastCB.

The same ordering holds at A=d=5A = d = 5, the instances used in Q2–Q4:

MethodLinear rewardLogistic rewardExponential reward
Greedy857.41 ± 451.89255.86 ± 134.85669.23 ± 352.72
ϵ\epsilon-greedy (ϵ=0.01\epsilon = 0.01)144.25 ± 104.91116.38 ± 83.19137.77 ± 78.30
ϵ\epsilon-greedy (ϵ=0.05\epsilon = 0.05)84.95 ± 23.6259.06 ± 28.7578.85 ± 28.41
ϵ\epsilon-greedy (ϵ=0.1\epsilon = 0.1)111.78 ± 21.3353.35 ± 17.6294.10 ± 18.48
SquareCB295.84 ± 3.91165.69 ± 1.64271.23 ± 3.59
SquareCB.L294.74 ± 3.89164.08 ± 1.46269.76 ± 3.44
SpannerIGW262.47 ± 4.92118.55 ± 4.55229.93 ± 4.61
FastCB79.33 ± 5.0263.28 ± 3.1373.50 ± 4.77
MinCE29.37 ± 8.9222.55 ± 8.2630.13 ± 9.28

Here the best ϵ\epsilon has 2.4 to 2.9 times MinCE's regret, and Greedy locks in on most repetitions.

No fixed ϵ\epsilon can imitate MinCE, because MinCE's exploration is not a rate. The probability on the predicted-greedy action is constant for ϵ\epsilon-greedy: 99.2% / 96% / 92% for ϵ=0.01/0.05/0.1\epsilon = 0.01 / 0.05 / 0.1 at A=5A = 5. For MinCE on the A=d=5A = d = 5 instances it is 75.5% over the first ten rounds, 86.4% over the first hundred and 99.7% over the last thousand. An ϵ\epsilon-greedy rule with the same average (ϵ≈0.019\epsilon \approx 0.019) would explore 16 times less in the first ten rounds and 4.6 times more in the last thousand.

Greedy is reported in every experiment. In the 9 synthetic conditions (Section 5.1) MinCE has the lower mean regret in 7 and is within a small fraction of one SD in the other 2. On 300 OpenML datasets the mean loss is 37.49% for Greedy, 39.21% for FastCB and 37.15% for MinCE.

On OpenML, matching Greedy is the hardest test for a method with a guarantee, and MinCE is the only one that passes it.

  1. OpenML is where Greedy is strongest, and this is well known (Bietti et al., 2021). Randomly permuted datasets give exchangeable, diverse contexts, so exploration is almost pure cost and the margin for any method is small.
  2. Every other method with a guarantee pays for its exploration there, and MinCE does not. Relative to Greedy, the mean loss is 1.7 points higher for FastCB, 11.7 for SpannerIGW and about 19 for SquareCB. MinCE's is 0.33 points lower (95% interval [0.06, 0.61]), lower on 199 of the 300 datasets, and lowest of all six methods on 175 datasets against 93 for Greedy.
  3. Greedy's strength does not carry over to data that require exploration, and MinCE's does. Greedy has no guarantee: on the instances above its regret is 8 to 24 times MinCE's, and on autos its loss is 96.2%, worse than uniform guessing (85.7%), against 81.6% for MinCE. A learner does not know in advance which kind of data it faces.

MinCE is the only method in the comparison that has Greedy's performance where exploration is unnecessary and a guarantee where it is necessary, with one algorithm and no tuning.

More details are in the paper: Section 5.2 and Appendix I.4 (these instances), Appendix I.6 (allocation over time), Section 5.3 and Appendix J (OpenML).

Q2. γ\gamma tuned over {10A,30A,100A,300A,1000A}\lbrace 10A, 30A, 100A, 300A, 1000A \rbrace

Even when γ\gamma is tuned in hindsight for FastCB and SquareCB, neither beats MinCE at its untuned default. We ran exactly the requested grid for both baselines, on synthetic tasks and on OpenML. MinCE stays at γ=10A\gamma = 10A, the value prescribed by the theory and used throughout the paper. We report every grid value on the ten evaluation seeds, so the best entry in each column is the most that any selection rule, including selection on a tuning seed, could achieve.

Synthetic tasks (the instances of Q1 with A=d=5A = d = 5, T=5,000T = 5{,}000). Final regret, mean ± SD over 10 seeds:

Methodγ\gammaLinear rewardLogistic rewardExponential reward
FastCB10A10A79.33 ± 5.0263.28 ± 3.1373.50 ± 4.77
FastCB30A30A42.64 ± 5.1733.40 ± 4.1139.99 ± 5.39
FastCB100A100A29.89 ± 7.4623.07 ± 5.9429.46 ± 8.29
FastCB300A300A29.37 ± 11.5824.47 ± 10.2930.85 ± 15.64
FastCB1000A1000A36.39 ± 17.2833.59 ± 19.3541.74 ± 23.70
SquareCB10A10A295.84 ± 3.91165.69 ± 1.64271.23 ± 3.59
SquareCB30A30A140.73 ± 4.63102.41 ± 3.14135.73 ± 4.63
SquareCB100A100A63.64 ± 5.5451.72 ± 4.7062.78 ± 5.43
SquareCB300A300A39.47 ± 7.4731.78 ± 5.8739.13 ± 7.64
SquareCB1000A1000A33.89 ± 11.9428.33 ± 10.9133.97 ± 11.00
MinCE10A10A (default, untuned)29.37 ± 8.9222.55 ± 8.2630.13 ± 9.28
  • FastCB. Its best grid values (100A100A and 300A300A) only reach the level of untuned MinCE: 29.37 / 23.07 / 29.46 against 29.37 / 22.55 / 30.13, with differences far inside one SD. The response is not monotone: at 1000A1000A regret rises again, with an SD about twice MinCE's.
  • SquareCB. It stays above MinCE at all 15 grid entries. Its best values are 13–26% higher.

OpenML (twelve datasets, additional runs reported in this response; full-pass classification error in %, mean ± SD over 10 repetitions, lower is better). Within a dataset all methods share the architecture, initialization and learning rate. MNIST uses a small CNN.

FastCB grid against MinCE:

DatasetFastCB 10A10AFastCB 30A30AFastCB 100A100AFastCB 300A300AFastCB 1000A1000AMinCE 10A10A
adult17.875 ± 0.11217.485 ± 0.08517.418 ± 0.10017.351 ± 0.07317.373 ± 0.06217.368 ± 0.071
boston27.332 ± 2.63226.502 ± 2.27525.771 ± 1.89825.731 ± 2.25925.632 ± 2.12725.573 ± 2.155
breast-cancer31.119 ± 1.70530.000 ± 1.17529.371 ± 0.80728.112 ± 0.95028.147 ± 0.96528.217 ± 0.888
Cardiotocography78.189 ± 2.49672.385 ± 3.81771.712 ± 2.86770.329 ± 3.03569.751 ± 3.40769.167 ± 4.889
compas-two-years38.882 ± 0.52538.127 ± 0.75337.720 ± 0.61637.612 ± 0.63937.533 ± 0.63637.529 ± 0.555
irish33.340 ± 3.07533.020 ± 3.13832.320 ± 1.45832.280 ± 2.49732.660 ± 2.20332.040 ± 3.081
MNIST (CNN)5.303 ± 0.0805.162 ± 0.1645.121 ± 0.1025.129 ± 0.1355.108 ± 0.1205.071 ± 0.084
PhishingWebsites12.447 ± 0.62212.119 ± 0.52312.117 ± 0.64211.995 ± 0.59311.990 ± 0.65411.906 ± 0.663
qsar-biodeg23.649 ± 1.21522.408 ± 1.16722.284 ± 1.40122.019 ± 1.21422.019 ± 1.33421.962 ± 1.090
Satimage21.816 ± 0.60820.998 ± 0.57620.747 ± 0.69220.510 ± 0.84320.426 ± 0.67220.392 ± 0.600
Titanic23.962 ± 0.47823.053 ± 0.43522.585 ± 0.32822.481 ± 0.39922.426 ± 0.35722.408 ± 0.318
WDBC16.977 ± 1.70016.063 ± 1.65915.097 ± 1.19914.728 ± 1.32014.780 ± 1.25514.692 ± 1.276
Reviewer_vysEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies realizable contextual bandits with an online log-loss regression oracle. The authors propose Minimum Certified Exploration (MinCE), which minimizes exploration subject to a one-step regret certificate derived from the analysis of FastCB. They establish a closed-form characterization of the certificate, prove the existence of a coordinatewise minimum among certified allocations, and develop an efficient procedure to compute it. The algorithm retains the first-order regret guarantees of FastCB. Numerical experiments on synthetic environments and 130 OpenML datasets demonstrate promising empirical improvements.

Critical strengths
  • The paper presents an interesting approach to exploration by directly incorporating a regret certificate into the action-selection problem. In particular, Theorems 4 and 5 establish the existence of a simultaneous minimum for nongreedy probabilities and provide an efficient algorithm that preserves the regret certificate throughout computation.

  • The theoretical results are meaningful. The proposed algorithm achieves the same first-order regret guarantees as FastCB, while the paper further characterizes when exploration can be substantially reduced. The experimental results are also encouraging.

Critical weaknesses
  1. MinCE achieves an extremely high greedy-action probability (99.943% in Table 1), but the experiments do not include simple alternatives such as pure greedy or tuned ϵ\epsilon-greedy. These comparisons are important for understanding whether the improvements arise specifically from the proposed regret certificate or simply from substantially reducing exploration. It would also be helpful to examine settings with initially inaccurate or overconfident predictions, where insufficient exploration may lead to poor decisions.

  2. The theoretical guarantees rely on an online regression oracle with a bounded log-loss regret. However, the neural experiments use Adam-based optimization without establishing a corresponding sublinear oracle-regret guarantee. As acknowledged in Appendix G.2, the generic oracle-regret bounds used for calibration are generally vacuous in this setting. Consequently, it remains unclear whether the empirical improvements are accompanied by the claimed nontrivial theoretical guarantees. Experiments with realizable function classes and provable regression-oracle guarantees would help bridge this gap.

  3. The theoretical guarantees rely on an online regression oracle with a bounded log-loss regret. However, the neural experiments use Adam-based optimization without establishing a corresponding sublinear oracle-regret guarantee.

Questions for authors

Please see the weakness above.

4 comments

We sincerely thank the reviewer for the time and the careful reading of our paper, and for the positive assessment of the theory (Theorems 4 and 5). We have uploaded a revised manuscript. It is strengthened in several respects in response to the reviews: Greedy and ϵ\epsilon-greedy baselines (Section 5.2, Appendix I.4), an analysis of MinCE's allocation during learning (Appendix I.6), a result showing that the allocation guarantee holds for any predictor (Lemma 21, Appendix F), and an OpenML evaluation extended to 300 datasets.

Every point in the review is answered with the experiment or the result it asks for. The table lists each request and its outcome, and the evidence follows.

Request in the reviewWhat we provideOutcome
W1: pure greedy and tuned ϵ\epsilon-greedy baselinesGreedy in every experiment, and ϵ\epsilon-greedy with ϵ∈{0.01,0.05,0.1}\epsilon \in \lbrace 0.01, 0.05, 0.1 \rbraceGreedy locks in (regret 952 / 280 / 752 against 40 / 34 / 43 for MinCE). The best ϵ\epsilon has 2.4 to 3.6 times MinCE's regret.
W1: settings with initially inaccurate or overconfident predictionsInstances built for exactly this (Section 5.2, Appendix I.4)MinCE has the lowest regret in all three settings, 51–57% below FastCB.
W1: does the gain come from the certificate or from simply exploring less?Three ways of exploring less without the certificate, and MinCE's allocation measured during learningNone of the three reproduces MinCE. MinCE's exploration is adaptive: 24.5% of its probability early, 0.34% late.
W2–W3: realizable function classes with provable regression-oracle guaranteesLinear and logistic classes with a Bayesian mixture oracle whose regret is at most log⁡16\log 16 on every sequenceMinCE has the lowest regret among the methods with a guarantee in all 8 settings, and the regret theorem applies verbatim.
W2–W3: guarantees when the oracle is an Adam-trained networkLemma 21: the one-step identity and the certificate hold for any predictorThe part of the guarantee that MinCE changes is covered exactly in every neural experiment.

W1. The improvement comes from the certificate, not from "simply reducing exploration"

Greedy and ϵ\epsilon-greedy reduce exploration without a certificate, and they fail in exactly the setting the reviewer describes. MinCE does not. We added Greedy to every experiment, and ϵ\epsilon-greedy with ϵ∈{0.01,0.05,0.1}\epsilon \in \lbrace 0.01, 0.05, 0.1 \rbrace on instances built so that the initial predictions are inaccurate (Section 5.2, Appendix I.4). These are fixed-feature bandits with A=d=10A = d = 10, T=5,000T = 5{,}000 and deterministic feedback. The features are highly correlated (pairwise inner product about 0.935), one action is optimal and nine are equally suboptimal, so a learner whose initial predictor undervalues the optimal action can be corrected only by exploring. All methods share the network, initialization, learning rate and seeds. Final cumulative regret, mean ± SD over 10 repetitions (lower is better):

MethodLinear rewardLogistic rewardExponential reward
Greedy952.37 ± 1.20279.88 ± 0.35751.96 ± 0.95
ϵ\epsilon-greedy (ϵ=0.01\epsilon = 0.01)398.19 ± 279.19203.83 ± 76.15396.14 ± 227.57
ϵ\epsilon-greedy (ϵ=0.05\epsilon = 0.05)144.23 ± 59.78101.73 ± 28.67134.08 ± 47.89
ϵ\epsilon-greedy (ϵ=0.1\epsilon = 0.1)148.07 ± 38.5483.04 ± 22.07139.00 ± 37.89
SquareCB465.26 ± 4.47206.24 ± 1.09410.25 ± 2.75
SquareCB.L463.92 ± 4.56204.75 ± 0.96408.21 ± 2.73
SpannerIGW379.78 ± 7.25135.60 ± 6.82315.12 ± 7.68
FastCB94.41 ± 7.6775.49 ± 4.3488.04 ± 6.80
MinCE40.44 ± 17.5734.36 ± 12.5043.34 ± 17.59
  • Greedy locks in on every repetition. Its regret (952 / 280 / 752) is that of a learner that never plays the optimal action.
  • No fixed ϵ\epsilon works. With ϵ=0.01\epsilon = 0.01 the escape is late and erratic (398 ± 279). With ϵ=0.1\epsilon = 0.1 the learner keeps paying for random actions. The best ϵ\epsilon in each column, chosen in hindsight, still has 2.4 to 3.6 times MinCE's regret.
  • MinCE has the lowest regret in all three settings: 88–96% below Greedy, 59–72% below the best ϵ\epsilon-greedy, and 51–57% below FastCB.

MinCE cannot lock in, because its exploration is computed from the predictions at every round. When the predictions tie, the least certified allocation equals the IGW reference. It shrinks only as the predictions separate. At fixed predictions (A=10A = 10, γ=10A\gamma = 10A, greedy prediction 0.5, the other nine at 0.5+g0.5 + g), the total probability on nongreedy actions is:

Predicted gap gg00.0010.010.1
FastCB0.900.880.750.30
MinCE0.900.400.0580.007

Theorem 6 makes this general: every certified allocation keeps pa≥(1−y^a)qa/281p_a \ge (1 - \hat y_a) q_a / 281 on each nongreedy action aa, so MinCE is never deterministic. Greedy has no such protection: Proposition 24 shows that it violates the regret bound on an explicit instance on which the oracle's regret is a constant.

A greedy probability of 99.9% is a full-horizon average. MinCE explores heavily exactly when the predictions are inaccurate (Appendix I.6). We measured the probability that each method puts on its own predicted-greedy action, by interval of rounds (in %, ten repetitions, T=5,000T = 5{,}000, A=5A = 5, FastCB and MinCE both at γ=10A\gamma = 10A; Table 6 lists every setting):

SettingMethodFirst 10 roundsFirst 100First 500Last 1,000Full horizon
9 synthetic conditions (Section 5.1)FastCB29.7149.1270.3480.9779.94
9 synthetic conditions (Section 5.1)MinCE87.8093.5497.3698.9398.79
Hard instances (A=d=5A = d = 5)FastCB22.6828.1761.0491.2288.19
Hard instances (A=d=5A = d = 5)MinCE75.5286.4389.9099.6698.45
  • MinCE is not near-greedy from the start. On the hard instances it puts 24.5% of its probability on nongreedy actions in the first ten rounds and 0.34% in the last thousand, about 70 times less.
  • No fixed rate reproduces this. Greedy is at 100% on every interval, and ϵ\epsilon-greedy is constant at 99.2% / 96% / 92% for ϵ=0.01/0.05/0.1\epsilon = 0.01 / 0.05 / 0.1. An ϵ\epsilon-greedy rule with the same average on the hard instances (ϵ≈0.019\epsilon \approx 0.019) would explore 16 times less in the first ten rounds and 4.6 times more in the last thousand.
  • The change follows the predictions, not a schedule. Under logistic rewards on the hard instances, MinCE's greedy allocation is 87.85% over rounds 1–100 and about 87.0% over rounds 101–500. It keeps exploring until the predictions separate.

On standard benchmarks MinCE is the only method with a regret guarantee that keeps pace with Greedy, and it avoids Greedy's failures.

  • 9 synthetic conditions (Section 5.1; A=5A = 5). Among the methods with a regret guarantee, MinCE has the lowest mean regret in all 9 conditions, 52–76% below FastCB. Against Greedy it is lower in 7 conditions and within a small fraction of one SD in the other two. With fixed features Greedy locks in on some runs, and its mean regret is 172.6 (linear) and 209.6 (logistic), against 37.7 and 66.6 for MinCE.
  • OpenML (300 datasets). Classification loss, equal weight per dataset:
MethodMean loss (%)Best of all six (of 300)Best among methods with a guarantee (of 300)
Greedy (no regret guarantee)37.49 ± 0.1993–
SquareCB56.44 ± 0.2533
SquareCB.L55.95 ± 0.1844
SpannerIGW49.17 ± 0.4389
FastCB39.21 ± 0.211728
MinCE37.15 ± 0.29175256

On OpenML, matching Greedy is the hardest test for a method with a guarantee, and MinCE is the only one that passes it.

  1. OpenML is where Greedy is strongest, and this is well known (Bietti et al., 2021). Randomly permuted datasets give exchangeable, diverse contexts, so exploration is almost pure cost and the margin for any method is small.
  2. Every other method with a guarantee pays for its exploration there, and MinCE does not. Relative to Greedy, the mean loss is 1.7 points higher for FastCB, 11.7 for SpannerIGW and about 19 for SquareCB. MinCE's is 0.33 points lower (95% interval [0.06, 0.61]), lower on 199 of the 300 datasets, and lowest of all six methods on 175 datasets against 93 for Greedy.
  3. Greedy's strength does not carry over to data that require exploration, and MinCE's does. Greedy has no guarantee: on the instances above its regret is 8 to 24 times MinCE's, and on autos its loss is 96.2%, worse than uniform guessing (85.7%), against 81.6% for MinCE. A learner does not know in advance which kind of data it faces.

MinCE is the only method in the comparison that has Greedy's performance where exploration is unnecessary and a guarantee where it is necessary, with one algorithm and no tuning.

Reducing exploration without the certificate does not reproduce MinCE. Greedy fails on the hard instances. A fixed ϵ\epsilon is 2.4 to 3.6 times worse at its best. For FastCB with a larger γ\gamma, we ran γ∈{10A,30A,100A,300A,1000A}\gamma \in \lbrace 10A, 30A, 100A, 300A, 1000A \rbrace at A=d=5A = d = 5, and the best value, selected in hindsight, only ties MinCE at its untuned default (29.4 / 23.1 / 29.5 against 29.4 / 22.6 / 30.1). Raising γ\gamma also weakens FastCB's guarantee, whose estimation term scales as 14γRegKL(T)14 \gamma \mathrm{Reg_{KL}}(T), whereas MinCE keeps the guarantee of γ=10A\gamma = 10A. The certificate is what tells the learner, at every round and with no tuning, how much exploration can be removed while the guarantee is kept.

W2–W3. Realizable function classes with a provable regression oracle: the requested experiment

We ran the experiment the reviewer asks for. With a realizable class and an oracle whose regret bound is proved, the assumptions of the regret theorem hold exactly, every parameter is set by the theory, and MinCE has the lowest regret among the methods with a guarantee in all eight settings.

Setup. Nothing in this experiment is neural, tuned, or heuristic.

Realizable classes. Linear costs fθ(x)=0.5−0.45⟨x,θ⟩f_\theta(x) = 0.5 - 0.45 \langle x, \theta \rangle and logistic costs fθ(x)=σ(−3⟨x,θ⟩)f_\theta(x) = \sigma(-3 \langle x, \theta \rangle), with θ∈Θ={−1/2,+1/2}4\theta \in \Theta = \lbrace -1/2, +1/2 \rbrace^4, so the class has M=16M = 16 functions. The true parameter is drawn uniformly from Θ\Theta and is unknown to the learner. There are A=5A = 5 actions with features in d=4d = 4 dimensions. Features are either fixed over the run or perturbed at every round by Gaussian noise of SD 0.1. Feedback is a Bernoulli cost of the selected action only.

Provable oracle. MinCE, FastCB and Greedy share one oracle, the Bayesian mixture over the class with a uniform prior (Lemma 9):

f^t(a)=∑m=1Mwt(m)fm(xt,a),wt+1(m)∝wt(m)fm(xt,at)yt(1−fm(xt,at))1−yt.\hat f_t(a) = \sum_{m=1}^{M} w_t(m) f_m(x_{t,a}), \qquad w_{t+1}(m) \propto w_t(m) f_m(x_{t,a_t})^{y_t} (1 - f_m(x_{t,a_t}))^{1 - y_t}.

Its log-loss regret satisfies RegKL(T)≤log⁡M=log⁡16≈2.77\mathrm{Reg_{KL}}(T) \le \log M = \log 16 \approx 2.77 for every adaptively chosen sequence. This is a deterministic guarantee, not an estimate. SquareCB receives the oracle that its own theory requires, squared-loss exponential weights over the same class, with regret at most 2log⁡M≈5.552 \log M \approx 5.55.

Parameters from the theorems, fixed before any data. MinCE and FastCB use γ=max⁡(10A,AT/(3log⁡M))\gamma = \max(10A, \sqrt{AT / (3 \log M)}), which is 54.8 at T=5,000T = 5{,}000 and 109.6 at T=20,000T = 20{,}000. SquareCB uses γsq=8AT/(2log⁡M)\gamma_\mathrm{sq} = \sqrt{8AT / (2 \log M)}, which is 189.9 and 379.8. There is no network, no optimizer, no learning rate, no clipping and no tuning of any kind.

Protocol. Ten paired seeds at each of two horizons, T=5,000T = 5{,}000 and T=20,000T = 20{,}000. Within a seed all methods share the environment, the potential outcomes and the action-randomization stream.

Results. Cumulative pseudo-regret, mean ± SD over ten repetitions (lower is better; bold marks the lowest among the methods with a regret guarantee):

TTFeaturesRewardGreedy (no guarantee)FastCBSquareCBMinCE
5,000FixedLinear103.79 ± 172.4595.31 ± 20.5492.84 ± 17.5735.16 ± 51.01
5,000FixedLogistic67.52 ± 173.2282.04 ± 26.5894.61 ± 13.0937.83 ± 89.16
5,000NoisyLinear11.40 ± 10.6999.91 ± 17.1699.54 ± 8.7813.30 ± 10.05
5,000NoisyLogistic6.38 ± 6.8479.59 ± 25.5199.29 ± 6.816.77 ± 2.60
20,000FixedLinear396.21 ± 671.18204.61 ± 35.05186.12 ± 21.0356.10 ± 63.50
20,000FixedLogistic246.89 ± 699.46178.18 ± 60.45200.71 ± 20.9479.69 ± 200.79
20,000NoisyLinear11.40 ± 10.69207.78 ± 38.97201.73 ± 9.9615.82 ± 10.04
20,000NoisyLogistic6.38 ± 6.84168.30 ± 58.38204.81 ± 13.199.10 ± 2.84

MinCE has the lowest regret among the methods with a regret guarantee in all eight settings. Its regret is 54–95% below FastCB's (2.2 to 18.5 times lower) and 60–96% below SquareCB's (2.5 to 22.5 times lower). FastCB runs on the same oracle and the same γ\gamma as MinCE, so the only difference between the two is the allocation rule.

The regret theorem applies to these runs verbatim. Realizability holds by construction, and the oracle regret is at most the constant log⁡16\log 16 on every sequence. With γ\gamma set by Theorem 2, every one of these runs therefore carries the guarantee of Corollary 3, E[RegCB(T)]=O(ATlog⁡M)\mathbb{E}[\mathrm{Reg_{CB}}(T)] = O(\sqrt{AT \log M}). The oracle budget is a constant that does not grow with TT.

Greedy has no guarantee, and it shows. Under fixed features its regret grows linearly with the horizon: from 103.8 to 396.2 and from 67.5 to 246.9 when TT is multiplied by 4 (factors 3.8 and 3.7). MinCE's regret grows by factors 1.6 and 2.1, in line with the T\sqrt{T} rate. Under noisy features the perturbations themselves supply exploration, and MinCE adapts to this: its regret (13.3 and 6.8 at T=5,000T = 5{,}000) is at the level of Greedy's (11.4 and 6.4), while FastCB and SquareCB pay 80 to 100 at T=5,000T = 5{,}000 and 168 to 208 at T=20,000T = 20{,}000. MinCE is the only method that is safe when exploration is needed and nearly free when it is not.

The implementation was verified against the theory on every run. Over all 320 runs, the largest log-loss regret observed on any prefix is 2.7726, equal to log⁡16\log 16, and the certificate was checked at every round of every MinCE run.

The allocation guarantee never depended on Adam (Lemma 21, Appendix F). For any predictor and any allocation, the one-step analysis is an exact identity that uses no oracle assumption. With ρ=5A/γ\rho = 5A / \gamma:

(1−ρ)E[RegCB(T)]−ρE[LT⋆]−14γE[EstT]=E∑t=1TΨy^t(pt,ft⋆)≤E∑t=1TCt(pt).(1 - \rho) \mathbb{E}[\mathrm{Reg_{CB}}(T)] - \rho \mathbb{E}[L_T^\star] - 14 \gamma \mathbb{E}[\mathrm{Est_T}] = \mathbb{E} \sum_{t=1}^{T} \Psi_{\hat y_t}(p_t, f_t^\star) \le \mathbb{E} \sum_{t=1}^{T} C_t(p_t).

Here EstT=∑t=1T∑apt(a)KL(f⋆(xt,a)∥y^t(a))\mathrm{Est_T} = \sum_{t=1}^{T} \sum_{a} p_t(a) \mathrm{KL}(f^\star(x_t, a) \Vert \hat y_t(a)) is the realized on-policy estimation error of whatever predictor is used, an Adam-trained network included. For a certified allocation the right side is negative, so under realizability

E[RegCB(T)]≤ρE[LT⋆]+14γE[EstT]1−ρ.\mathbb{E}[\mathrm{Reg_{CB}}(T)] \le \frac{\rho \mathbb{E}[L_T^\star] + 14 \gamma \mathbb{E}[\mathrm{Est_T}]}{1 - \rho}.

The oracle assumption is used only afterwards, to bound E[EstT]\mathbb{E}[\mathrm{Est_T}] by RegKL(T)\mathrm{Reg_{KL}}(T). The certificate itself is a closed-form property of the allocation at the predictions actually produced, and it holds at every round of every neural experiment.

For neural oracles the comparison between methods is on equal footing. The bound above holds with the network's realized estimation error in place of the oracle budget. That quantity is the same for FastCB, SquareCB and every regression-oracle method run with a practical learner. What MinCE changes, the conversion of estimation error into regret, is certified at every round. Beyond finite classes, the oracle assumption holds provably for logistic and generalized linear classes with logarithmic regret (Kakade & Ng, 2004; Foster et al., 2018b; Jézéquel et al., 2020), and neural online regression oracles for this interface are analyzed by Deb et al. (2024).

The two sets of experiments are complementary. With a provable oracle, where the theory applies verbatim, MinCE is 2.2 to 18.5 times better than FastCB. With neural oracles on 300 OpenML datasets, the same allocation rule is better than FastCB on 268 datasets. The advantage of certified minimal exploration holds in the regime the theory covers and carries over to practical oracles. In both, MinCE runs at the value of γ\gamma prescribed by the theory, with no tuning. This is what a bandit learner needs: regret is not observed online, so a parameter that has to be tuned cannot be tuned.


Closing remarks

We especially thank the reviewer for asking for realizable function classes with provable regression-oracle guarantees. The question brings out what MinCE is: not a heuristic for neural networks, but an allocation rule whose guarantee holds in full for the classical model classes of the bandit literature. For finite classes and for generalized linear models, which include the linear and logistic models, online regression oracles with a proved log-loss regret bound exist (Lemma 9; Kakade & Ng, 2004; Foster et al., 2018b; Jézéquel et al., 2020), and with them every assumption of our regret theorem is met. The experiment the reviewer asked for confirms it: on realizable linear and logistic classes, with a provable oracle and nothing tuned, MinCE's regret is 2.2 to 18.5 times lower than FastCB's.

The same algorithm is also flexible and practical. MinCE touches the model only through its predictions, so it runs unchanged with any regression oracle, from a linear model to a neural network. Its certificate has a closed form evaluated in only O(A)O(A) time (the order already needed to query the AA predictions commonly for regression-oracle-based algorithms, so it does not increase the computational order), with no additional oracle call and no parameter to tune. With neural oracles on 300 OpenML datasets it has a lower loss than FastCB on 268, and it is the only method with a guarantee that keeps pace with Greedy. One untuned algorithm is provable on the model classes where the theory can be verified and effective with the oracles used in practice.

The first point of the review is answered in the same way, by direct evidence: Greedy, every fixed ϵ\epsilon, a front-loaded exploration budget and FastCB with a tuned γ\gamma all reduce exploration without the certificate, and none of them emulates the fundamental behavior of MinCE. We sincerely believe that both points are addressed in full, and we would be grateful if the reviewer would reconsider the rating in this light.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.