Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
Authors: Dylan J Foster
Akshay Krishnamurthy
Venue: NeurIPS 2021 Oral (2021)
Keywords: contextual bandits
reinforcement learning
statistical learning
learning theory
fast rates
adaptivity
sequential probability assignment
conditional density estimation
logarithmic loss

Abstract: A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise, often quantified by the performance of the best hypothesis; such results are known as first-order or small-loss guarantees. While first-order guarantees are relatively well understood in statistical and online learning, adapting to low noise in contextual bandits (and more broadly, decision making) presents major algorithmic challenges. In a COLT 2017 open problem, Agarwal, Krishnamurthy, Langford, Luo, and Schapire asked whether first-order guarantees are even possible for contextual bandits and---if so---whether they can be attained by efficient algorithms. We give a resolution to this question by providing an optimal and efficient reduction from contextual bandits to online regression with the logarithmic (or, cross-entropy) loss. Our algorithm is simple and practical, readily accommodates rich function classes, and requires no distributional assumptions beyond realizability. In a large-scale empirical evaluation, we find that our approach typically outperforms  comparable non-first-order methods.

On the technical side, we show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees, and we combine this observation with new refinements to the regression oracle reduction framework of Foster and Rakhlin (2020). The use of triangular discrimination yields novel results even for the classical statistical learning model, and we anticipate that it will find broader use.

Efficient First-Order Contextual Bandits:
Prediction, Allocation, and Triangular Discrimination
Dylan J. Foster
Akshay Krishnamurthy Microsoft Research, NYC
Microsoft Research, New England dylanfoster@mi wtw.omt..ooooooooooooooooooo com
akshaykr@miccosoof..co
Abstract
A recurring theme in statistical learning, online learning, and beyond is that faster
convergence rates are possible for problems with low noise, often quantified by the performance of the best hypothesis; such results are known first-order
small-loss guarantees. While first-order guarantees are relatively well understood in statistical and online learning, adapting to low noise in contextual bandits (and more broadly, decision making) presents major algorithmic challenges. 2017 open problem, Agarwal et al. [5] asked whether first-order guarantees are even possible for contextual bandits and if so whether they can be attained by efficient algorithms. We give resolution to this question by providing optimal and efficient reduction from contextual bandits to online regression with the logarithmic (or, cross-entropy) loss. Our algorithm is simple and practical, readily accommodates rich function classes, and requires no distributional assumptions beyond realizability. In large-scale empirical evaluation, we find that approach typically outperforms comparable non-first-order methods.
COLT
On the technical side, we show that the logarithmic loss and an information- theoretic quantity called the triangular discrimination play fundamental role in obtaining first-order guarantees, and we combine this observation with new refinements the regression oracle reduction framework of Foster and Rakhlin [29]. The use of triangular discrimination yields novel results even for the classical statistical learning model, and we anticipate that it will find broader use.
Introduction
In the contextual bandit problem, learning agent repeatedly makes decisions based on contextual information, with the goal of learning a decision-making policy that minimizes their total loss over time. This model captures simple reinforcement learning tasks in which the agent must learn to make high-quality decisions in uncertain environment, but does not need to engage in long-term planning or credit assignment. Owing the availability of high-quality engineered reward metries, contextual bandit algorithms are now routinely deployed in production for online personalization systems [4, 61].
Contextual bandits encompass both the general problem of statistical learning with function approx- imation (specifically, cost-sensitive classification) and the classical multi-armed bandit problem, yet present algorithmic challenges greater than the sum of both parts. In spite of these difficulties, extensive research effort over the past decade has resulted in efficient, general-purposs algorithms, as well as a sharp understanding of the optimal worst-case sample complexity [9, 12, 3, 29, 58].
While the algorithmic and statistical foundations for contextual bandits beginning take shape, we still lack an understanding of adaptive or date-dependent algorithms that can go beyond the worst case and exploit nice properties of real-world instances for better performance. This is in stark contrast to supervised statistical learning, where adaptivity has substantial theory, and where standard
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

algorithms (e.g., empirical risk minimization) are known to automatically adapt to nice data [17]. For contextual bandits, adaptivity poses new challenges that seem to require algorithmic innovation, and major research frontier is to develop algorithmic principles for adaptivity and an understanding of the fundamental limits.
To highlight the lack of understanding for adaptive and data-dependent algorithms, a COLT 2017 open problem posed by Agarwal, Krishnamurthy, Langford, Luo, and Schapire [S] asks whether there exist contextual bandit algorithms that achieve a certain data-dependent, first-order regret bound, which fiarppernnentffss-orreeee
scales with the cumulative loss L* of the best policy, rather than with the time horizon T. For multi- armed bandits, first-order regret bounds (also known as small-loss bounds or fast rates) typically scale as VL* and imply faster convergence for "easy" problems, interpolating between the optimal vT rate for worst-case instances and constan//loarrthmii regret for noise-free instances [7, 31 Agarwal et al. [5] observed that existing techniques appear to be inadequate to achieve this type of guarantee in contextual bandits. Beyond simply asking whether first-order regret can be achieved, they also asked whether it can be achieved efficiently, which is essential for real-worke deployment. Subsequently, Allen-Zhu, Bubeck, and Li [6] gave an inefficient algorithm with an optimal first-order regret guaran- tee, resolving the former question, but the existence of efficient first-order algorithms remained open.
Contributions. We give the first optimal and efficient contextual handit algorithm with a first-order regret guarantee, providing resolution to the second open problem raised by Agarwal et al. [5]. Our algorithm, FastCB, builds on recent line of research that develops efficient contextual bandit algorithms based on the computational primitive of (online/oftline supervised regression [43, 32, 29, 58], and is efficient in terms of queries to an online oracle for regression with the logarithmic loss. Beyond attaining first-order regret, FastCB inherits all of the benefits of recent algorithms based on regression: it is simple and practical, accommodates flexible function classes, requires no statistical assumptions beyond realizability, and enjoys strong empirical performance.
Technical highlights. By invoking the framework of regression oracles, our algorithm design approach deviates sharply from prior approaches to first-order regret and necessitates the use of techniques that are novel even in the context of statistical learning. At high-level, the design of FastCB leverages two key techniques:
1. First-order regret for plug-in in classification via logarithmic loss: We show that algorithms based on regression with least-squares, as used in prior work [29, 58, 68, 34, 23], fail to attain first-order regret, even for the simpler problem of cost-sensitive classification in statistical learning. In spite of this apparent setback, we show that regression with the logarithmic loss does lead to first-order regret for statistical learning. This is established through a new analysis based on an information-theorrti quantity called the triangular discrimination [66, 44, 62).
2. Reweighted inverse gap weighting: Moving from statistical learning to contextual bandits, transform predictions into distributions over actions using a sensitive refinement to the inverse-gap gap weighting scheme used in the SquareCB algorithm [1, 29]. Our new scheme is tailored to small losses, and we show that its error is controlled by the triangular discrimination.
Summarizing, our approach leverages prediction via the logarithmic loss, allocation via reweighted inverse gap weighting, and triangular discrimination as the bridge from prediction to allocation.
Empirical results. In Section 5, we evaluate FastCB on the large-scale contextual bandit henchmark of Bietti et al. [13] and find that it typically outperforms SquareCB and other non-adaptive baselines [35]. Interestingly, we observe that most of the performance improvement can be attributed to the use of the logarithmic loss, while the reweighted allocation scheme provides modest additional benefit. These findings raise natural question as to whether simply moving to the logarithmic loss can yield performance improvements in production contextual bandit deployments.
On the regression oracle model. As a disclaimer, we caution that our algorithm is efficient in terms of oracle for online regression, while Agarwal et al. [5] originally asked for an algorithm that is efficient in terms of a cost-sensitive classification oracle capable of solving the policy optimization problem argmin I (<((x))). Hence, while FastCB is the first algorithm with first-order regret that is efficient in any oracle model, it does not formally solve the original open problem. Nonetheless, there are strong reasons to prefer a solution based on regression over one based on classification. First, cost-sensitive classification is intractable to implement even for simple function classes for which regression can be solved efficiently [29]. Setting this issue aside, (online)

---

Algorithm/ FastCB ("Fast Rates for Contextual Bandits")
1: parameters:
Learning rate >> O.
Online regression oracle Alga.
2: for = I,..., do
3: Receive context Zz--
// Compute oracle's predictions (Eq. (4)).
4: For each action a E A, compute (e() = Algkl (lgh(((0o (2e,
((r a, ((a:)))
5: Let b, E argmin Dt,c-
// Reweighted inverse gap weighting. (x(.)))))
6: For each bt, define Pt.e bi -( Let Pt.b. =1 EEftr Pra.-
7: Sample a2 ~ and observe loss ((()).
8: Update Algat with example (xt, ar, (at)).
9:
end for
regression- based algorithms are typically simpler and faster than classification -aasei algorithms. and multiple empirical evaluations have shown that algorithms based on regression dominate those based on classification [32, 13, 35].
Organization. Section 2 contains our algorithm and main theorem. Section describes the moti- vation and analysis ideas behind FastCB, beginning from new techniques for statistical learning with regression-basee classifiers. Examples for the main theorem are given in Section 4, and experimental results are given in Section 5. Detailed discussion of related work is deferred Appendix A.
2 Main Result: An Efficient First-Order Algorithm for Contextual Bandits
We begin by formally introducing the contextual bandit model. At each round t E [T]. the learner observes context Ø; E X. selects an action a E A,, then observes a loss (a()) E [0, 1] for the action they selected. We assume that A = |A| is finite and that each loss function la A ~ [0, 1] is drawn independently from a fixed distribution ( (t), where Pe.,..., Pey and I1, Pr are selected by potentially adaptive adversary.
We make standard realizability assumption [24, 2, 32, 29]. Namely, we assume that the learner has access to a class of value functions F C (X x - [0, 1J) (e.g., neural networks, kernels, or forests) that models the mean of the loss distribution.
Assumption 1 (Realizabilitt). There exists f* F such that for all t, fx(xxa)) = (a) | o x].
The aim of the learner to minimize their regret to the optimal policy x xxx) argmin (rr a):
Regce (T) Σ (aa))
Σ le(T (x,)).
For each f F. we let (x) argmin A f(z, a) be the induced policy. We let II (Ty f E F} be the induced policy class.
Further notation. We adopt standard big-oh notation, and write = Ö to denote that ʃ Ogg max (1, polylog(g)}). We use Z only in informal statements to highlight the most salient elements of an inequality. We use V maxfa, b) and A b min(a,b).
2.1 Algorithm and Main Result
FastCB builds on the SquareCB algorithm of Foster and Rakhlin [29], which provides an efficient, minimax-optima reduction from contextual bandits to online regression with the square loss. Com- pared to SquareCB and other subsequent algorithms based on online regression [34, 23], the first twist here is that rather than working with the square loss, we build on the computational primitive of online regression with the logarithmic loss. While this point is inconsequential for worst-case guarantees, we show that it is fundamental distinction for first-order guarantees.

---

Online regression oracles. In more detail, an online regression oracle, which we denote by A (for Daillback-eibbeer" operates in the following protocol: For each time t. the algorithm receives a context-action pair (Zi, dt), produces a prediction Yr E [0, 1]. then receives a response yt- The algorithm's 's prediction error is measured through the binary logarithmic/eros-entno
loss,
boog (T, v) := log(1/0) + (1 y) log(1/(1 - 7)
(2)
The algorithm's goal is to ensure that the log loss regret to F is minimized for all sequences.
Assumption 2. The algorithm A Algn, guarantees that for every (possibly adaptively chosen) sequence IT.T, 01 Urr,, the log loss regret is bounded by known function RegkL (T):
Σ Bog (Dt, Me)
Σ (for, ut) EEF
inf
Wr) S ReggL (T),
Online regression with the logarithmic loss (or, sequential probability assignment) is a fundamental and well-studied problem in online learning, and there are efficient algorithms available for many function classes of interest [25, 67, 40, 37, 52, 55, 33, 48]; see Section for examples. While log loss regret is a more stringent notion of performance than square loss regret, it nonetheless has relatively mature theory characterizing optimal rates [57, 51, 20, 14].
The algorithm. FastCB (Algorithm 1) is reduction that efficiently transforms any online regression oracle satisfying Assumption 2 into a contextual bandit algorithm with an optimal first-order regret bound. At each round I, the algorithm first computes the estimated loss
(4) predicted by the regression oracle for each action a (Line 4); see Appendix C.1 for a more detailed formal description of the oracle model. Next, FastCB uses these estimates to assign probability of being played to each action a via a scale-sensitive refinement to the inverse gap weighting strategy used in SquareCB [1, 29], which we call reweighted inverse gap weighting (Line 6). Letting by == argmin Di (14, a) the greedy action according to the predicted losses, we define
(1) To ( a)= Algk (z,, a; {(z,, a,, (a))))
(T,, b:)
Ya * be, and Ptb. == 1 Σ Pt.a: (5)
Pr. A br) + 7 (Te, a) Hr (x,, b.))
oz
where y > 0 is learning rate parameter. Given this distribution, FastCB simply samples a, Pt then updates the oracle with the resulting tuple (Ie, 0e ((a))). Our main theorem shows that this leads to optimal first-order regret bound.'
Theorem (Main theorem). Suppose Assumptions I and 2 hold. Then Algorithm I guarantees that for all sequences with E E le(m (x+))] S T.*, by choosing 7 = /AL* /3RegkL V 10A, Regecs (T)] < 40 L ARegkL (T) + 600.ARegkL (T).
(6)
The dominant term in this regret bound scales with vT.² whenever the oracle Algat attains a fast log( -tyye regret bound. As simple example, whenever F is finite, we can instantiate Algaa so that RegkL (T) & log[F] [67], whereby FastCB enjoys optimal [2] first-order regret:
E E(RegcB(T)) (T) s [(VI*
A log| + A Alog.F))
Beyond first-order regret, FastCB inherits all of the advantages of online regression- based algorithms:
Efficiency and simplicity. The memory and runtime used by the algorithm on top of what is required by the regression oracle- scales only as ((A) per step; implementation is trivial.
Flexibility. Working with regression as primitive means that the algorithm easily accomodates rich, potentially nonparametric function classes, and we can instantiate Theorem I to get provable end-to-end regret guarantees for concrete classes of interest. For example, for linear models Rd we can efficiently attain RegkL(T) (T)) < Old Odlog)T) [25, 40], which yields a first-order regret bound Regce (T) S VT. Ad; our result is new even for this simple special case. Similar guarantees are available for kernels, generalized linear models, and many other nonparametric classes. On the not available, regression is amenable to practical heuristics (e.g., gradient descent). See Section 4 for detailed examples.
other hand, even for function classes where provable algorithms
While we assume that an upper bound on the optimal loss is known for simplicity, one can extend to the unknown case by running the algorithm in epochs, setting in terms of the algorithm's 's estimated loss L, E l- (a(a), ). and applying the doubling trick. Theorem also readily extends high probability.

---

3 Overview of Analysis
We now outline the algorithmic principles and analysis ideas behind FastCB. First, in Section 3.1, take step back and consider the sub-problem of cost-sensitive classification in statistical learning. We establish that approaches based on least-squares fail to attain first-order regret (Theorem 2) for cost-sensitive classification, then show how to fix this problem using log loss regression (Theorem 3); this analysis serves an introduction the triangular discrimination. With this result in hand, we move to the contextual bandit setting and transform predictions into distributions over actions using the reweighted inverse-gat gap weighting scheme in (5), which exploits small losses. Our main result here shows that this scheme satisfies a first-order variant of the per-round minimax inequality of Foster and Rakhlin [29]. which links the instantancous contextual bandit regret to the triangular discrimination for the regression oracle on per-round basis (Theorem 4). Full proofs are deferred to Appendices and C.
3.1 Warmup: First-Order Regret Bounds for Plug-In Classifiers
For the simpler problem of cost-sensitive classification in statistical learning, the literature on plug-in in classification shows that whenever realizability conditions such as Assumption 1 hold, obtain optimal worst-case regret by taking the greedy policy/classifier induced by a least-squares estimator. We first show that this approach fails to attain first-order regret.
The statistical learning setting we consider as follows. We receive a dataset Dn consisting of
context-loss pairs (It, Ee) ~ D ii.d., where the entire loss function l, A + [0, 1] is observed.
Analogously to Assumption I, we assume access to a function class F C (X' x A + [o, 1]) such
that (f(a] x]] (Ir a) for some f E F, and take II := { f F} as the induced class of policies. Our goal is to learn policy मे X + A such that the regret (or, excess risk)
L(
is small, where L(r) [x(((T(z)) and L L(x*), with .'" == :y Formally, this easier problem than contextual bandits, since any algorithm with a regret bound for contextual bandits yields bound the cost-sensitive classification regret (7) via online-to-batch conversion.
classical result in statistical learning [65, 54, 59] shows that if we compute the policy/classifier म := argmin Σx= (x(())) that minimizes the empirical risk, obtain first-order regret bound of the form?
log F
lo
E[[(R)] L' -
(8)
This is an optimal first-order guarantee, but computing से is typically computationally intractable, even for relatively simple policy classes. As alternative, the approach of plug-in classification aims to use the realizability assumption to develop algorithms based on the more tractable primitive of regression. Here, another classical result (e.g., Audibert and Tsybakov [8]*), shows that if we perform least-squares via
T2
LL = argmin Σ -
JEF
aEA
and take iis == The as our classifier, then under the realizability assumption we are guaranteed
Alog.F
E[L(fs)) L' L'
n
While this result rate-op is not first-order, and first-order regret bounds for plug-in classifi- cation are conspicuously absent from the literature. We show that this is fundamental.
Theorem 2 (Failure of least-squares for plug-in classification). Let = 2 and X = (1, For every > 10 there exists function class F C (X' x A + [0, 1) with [F = 2, and realizable
distribution D such that L* < 27 1. yet (( L 2 2 2-5 5 V with probability least 1/10.
Following the convention in contextual bandit literature, focus finite classes with |F oo in this discussion, but one can extend our observations to general classes, e.g., using the machinery of Zhang [71]. 'This result is well-known in the binary setting. We are not aware of reference for the multiclass/cost- sensitive version here, though it is implicit in many recent works contextual bandits.
5

---

log! X we conclude that plug-in classification Since the instance in this theorem has / // AlolA
with teast-squares fails to attain the first-order regret bound in (8) with constant probability; lower bound expectation follows immediately.
3.1.1 Fast Rates for Plug-In Classifiers: Triangular Discrimination and Logarithmic Loss
would appear we are at an impasse, as Theorem 2 shows that square loss regression oracles of the type used in Foster and Rakhlin [29] are unlikely attain first-order regret bounds on their own. However, the plug-in classification approach is not completely doomed. All we need to do to fix this issue is change the loss function and instead perform regression with the logarithmic loss.
To understand why plug-in least-squares fails and how it can be improved, it will be helpful to review the key steps in the analysis leading the rate (9).
Step 1, First, using generic regret decomposition based on realizability, for any f we have L(T,) - L 2 S
max [x)s( -Mx) =E(x),=)
(10)
Step 2. Next, by Cauchy-Schwarz, for any policy have
ED - (",, (()) ( (()))))))))))))))))))))))) 1/2
(11)
which may further upper bound by ED f(x, -(. 1/2
Step 3. Finally, under realizability, standard concentration argument based on Bernstein's inequality implies that the least-squares estimator satisfies
A log|FF
E
Σ LAEA
()) -
(12)
Combining this bound with Step 2, we conclude that E[L(f(s)] L' S /Alog| Fl/n.
The issue here is that even in the presence of low noise, the squared error in (12) shrinks faster than + This holds even if L* ε n. as in the lower bound construction for Theorem 2. Consequently, we apply Cauchy-Sehwart
Step 2, we lose all hope of attaining a first-order bound.
Our starting point toward improving this result a refined application Cauchy-Schwarz, by which can replace the right hand side of (11) with
(( 1/2
ED
(13)
The ratio term above is closely related to the triangular discrimination, an information-theoreticc divergence measure which we define for q E R$ as*
(pa 9p)
Da(plla) = Σ
(14)
Pa + Ya
The triangular discrimination-an known as the symmetric >dvdieeeeee and Vineze-Le Cam distance- is fundamental, often-overlooked quantity in information theory [66, 44, 62). Since readers may unfamiliar, we record some basic facts.
Proposition (Topsøe [62]). The triangular discrimination Da, over the domain A i) is the f-divergence given by f(t) (t-1)² ti) is the square a distance metric, and iii) is equivalent (up to multiplicative constant) to both Hellinger distance and Jensen-Shannon divergence.
'The triangular discrimination is traditionally defined over the simplex As. but for our application it is useful work with the entire positive orthant.

---

The triangular discrimination turns out to be "just right" for our purposes, in that it is both i) large enough to facilitate the scale-sensitive application of (compared to the more standard x x²-divergence) to facilitate minimizing from samples.
Schwarz in (13), and ii) small enough
Returning to (13), self-bounding property that it satisfies to arrive at the following improvement on Step 1/Step 2. Lemma (Regret decomposition for triangular discrimination). For any J X A + [0, 1].
upper bound with the triangular discrimination and leverage certain
[ T. < 8(L (P f(x, )) 17Ep[Pa(S [x, (o,, -)]
(15)
Lemma 1 shows that low triangular discrimination (i.e. Ep Ep (l x 1/n) suffices for an optimal first-order regret bound. What remains is to find an estimator f that minimizes this quantity given only samples. Our key observation here is that the triangular discrimination satisfies a refined variant of Pinsker's inequality (originally due to Topsøe [62]), which allows to bound it by the Kullback-Leibler divergence:
(z, (1 +) Σ (((,,a)
del ((r,
(16)
((z.a)+f
where (p 2) := plog(p//)))+++//pp
(1) (1) is the binary KL.divergence, Note
that the triangular discrimination is critical here, as the opposite inequality holds for x -iveeeggeee This bound suggests that we should minimize the logarithmic loss, since-under the realizability assumption- loss closely related to the KL-divergence. In particular, we show (Theorem in Appendix B), that by taking the estimator
fr.: argmin ΣΣ log (f(2,, ((()))
jeF t=
guaranteed that with high probability, ED [D(ff(<r -) II (xx, )) 2 Alog|F] Putting everything together, we arrive at first-order regret bound for the plug-in classifier 7KL f
Theorem 3 (First-order regret bound for plug-in classification). Let (0, 1). Suppose that Assump- tion 3 holds. Then with probability at least 1 5, we have
L A (log F log(A/8)) + 68
A (log [F + log(A/6))
( L' S 161
n
Interestingly, applications of the triangular discrimination similar to Lemma 1 have recently been discovered across number of branches of mathematics, including theoretical computer science (communication complexity lower bounds), probability, and group theory (e.g.. construction of group homomorphisms) [70, 28, 11, 53]. Additionally, Bubeck and Sellke [18] use related non-negative x2 -iivergencce to provide first-order Bayesian regret bounds for Thompson sampling for the multi-armed bandit.
3.2 Moving to Contextual Bandits: Inverse Gap Weighting meets Triangular Discrimination
FastCB builds on the development for plug-in classifiers in Section 3. but with two key differences. First, since we need make decisions the fly for arbitrary sequences of contexts, the algorithm timates losses using an online regression oracle for the logarithmic loss, as described Assumption 2. Second, and more importantly, since the algorithm receives partial feedback, the strategy for selecting actions is critical. Here our main technical result shows that the reweighted inverse gap weighting strategy (5) satisfies certain per-round inequality that links the instantaneous contextual bandit error to the triangular discrimination between the oracle's prediction &r and the true loss function f*
Theorem 4 (First-order per-round inequality). Let [0. 1| be given and E argmin, ya- Define Eazs Pa- If 2 2A, then for all E [0, 1] and
Po Aystryy.-uu for a f b, and ps
2b
a" E arginin, Ja. we have
5A Σ pafa + + Pa (Ya fa)
Palaf - fa-
(17)
+ fa
CB regret
bias from exploring
error from exploiting
'The dependence on A in this result can be improved under additional assumptions on the loss distribution. As example, in Appendix B remove the leading A factor for the special case of multiclass classification.
7

---

The inequality (17) may be thought of as an algorithmic analogue of the refined Sauchy-Schward lemma (15), with the learning rate y modulating the tradeoff between exploration and exploitation. Applying the inequality for each step L. (with Pt. y = De (e -), and = 1===((an (Ttt and using the Pinsker-type inequality (16), we are guaranteed that
5AA [[LT] + 147- RegkL (T),
E3 [eeece S
(18)
7
where LT = E/-1 ((a)). By standard argument, this implies the main result in Theorem 1.
Compared the per-round inequality used to analyze the original version of SquareCB in Foster and Rakhlin [29], the main improvement given by Theorem 4 is that, by reweighting-wwi whhic leads to less exploration when the optimal loss small-we are able replace a constant exploration bias of order A incurred by SquareCB with the scale-sensitive bias term 4 Pafa in (17), leading to first-order bound. The price for this improvement is that we must now minimize the triangular discrimination rather than the squared error used by SquareCB, but this taken care of by the log loss oracle.
Pa
4 Examples
In this section we take advantage of the extensive literature on regression with the logarithmic loss [25, 67, 40, 37, 52, 55, 33, 48] and instantiate Theorem give provable and efficient first-order regret bounds for a number of function classes of interest. To the best of our knowledge, our results are new for each of these special cases.
Example 1 (Finite function classes). If F is a finite class, Vovk's aggregating algorithm [67] guarantees that RegkL(T) (T) < log| With this choice, FastCB satisfies E|Regce S OVT Alg + A Alg]FF))
Example 2 (Low-dimensiooal linear functions). Suppose that F takes the form F. {(x, a) + (w, ((ra))))))))))))))))))))))))(( w E Aa), where (xx, a) E R4, is a fixed feature map with [ a) S. Then the continuous exponential weights algorithm ensures that RegKL (T) S Odllog( /d)], and can be implemented in poly(d, T) time per step using log- log-concave sampling [25, 40J.? With this choice, FastCB satisfies E Reggaa S <O(LL* Adlog(T/o)) + Ad Adlo/(//d))
Beyond attaining first-order regret, the bound in this example is minimax optimal when the number of actions is constant [46]. A natural direction for future work to extend the result to large action spaces. Another more practical choice for the oracle in this setting is the algorithm of Luo et al. [48], which has slightly worse regret RegkL (T) I (df), but runs in time OTT22 per step.
While first-order regret bounds for contextual bandits have primarily been investigated for finite classes prior to this work, an advantage of working within the regression oracle framework is that we can easily lift our first-order g guarantees to rich, nonparametrie function classes.
Example 3 feigh//nfiiite-dmenniin {(.,a) a) - (1 + (w, 6(x, a))) [|l|ll $1}. where [|ő(1, a)llz S 1 is a fixed feature map. For this setting. Rakhlin and Sridharan [55, Section 6.1] show that the FTRL algorithm with log tog-barrier regularization has RegkL (T) S ((TTloo(T)) This algorithm can be implemented in time (dd) per step, and satisfies the dimension dimension-independenn rate [E[Regc (T') S ((AL+))/2T + AVT).
linear functions). Suppose that F takes the form F
Let us interpret the bound in Example 3. First, we recall that the minimax optimal rate for this setting A1/273/4 which the bound above always achieves in the worst case [1, 29]; this "worse-than- - "T" rate is the price we pay for working with expressive function class. On the other hand, if L is constant, the bound in Example 3 improves to O(AVT), which beats the worst-case rate. While one might hope that tighter rate of the form, e.g., (L*)3/4, might be possible, by adapting lower bound in Srebro et al. [59, Section 4], one can show that this result cannot be improved.
Lastly, we highlight that the logarithmic loss is well-suited to generalized linear models.
"See Proposition 6 for a proof that the loss lagg( u) is mixable over the domain j0, 1].
"Our setup directly reduces universal portfolio selection follows: When y is binary, we reduce by using features o(2,, at) when be = 1. and using features 1, d(Ie, Qt) when ys The case where ye [0, 1] can reduced to this setting by sampling from Ber(y:).
*This is technically only proven for the case where y {0, but the proof easily extends y E [0, 1).
8

---

Example 4 (Generalized linear models), Let {2,,a)+++++ (w o(z, w E Rd, 11lll2 S 1] where (t) = 1/(1 + + case, the map w + biog(a((uu ((x, a))) y) is equivalent to the standard logistic loss function applied to (w, ((I, a)), and we can use the algorithm from Foster et al. [33] to obtain RegKL (T) I
) is the logistic link function and ő(x, a) is a fixed feature map. In this
Old ((gloo()/d) and Regce (T) S OVT Ad + Ad).
Beyond the algorithmic examples above, for general function classes Bilodeau et al. [14] provide a tight characterization for the minimax optimal rates for online regression with the logarithmic loss in terms of sequential covering numbers [55] for the class F. We can use this result in tandem with Theorem to give new regret bounds for general classes.
5 Experiments
We compared the performance of FastCB to that of the de-facto alternative, SquareCB [29] in the large-scale contextual bandit evaluation suite ( ("bake-off"") of Bietti et al. [13]. We found that FastCB typically enjoys improved performance, particularly on datasets where the optimal loss L is small. As a secondary observation, we found that using generalized linear models with the logarithmic loss rather than linear model with the square loss (as in prior work [13, 35)) leads to substantial improvements, even without changing the SquareCB allocation rule. We summarize results here; further details are given in Appendix E.
Datasets.
The contextual bandit bake-off is a collection of over 500 multiclass, multilabel, and cost-sensitive classification datasets available on the openml org platform [64]. The collection was introduced in Bietti et al. [13] for the purpose of benchmarking oracle- contextual bandit algorithms. Following Bietti et al. [13]. we use the multiclass classification datasets from the collection (each context x has a "correct" label y associated with it) to simulate bandit feedback by assigning loss 0 if the learner predicts the correct label and otherwise.
Algorithms and oracle. We use the standard implementation of SquareCB in the Vowpal Wabbit (VW) online learning library," as used by Foster et al. [35]. We also implement FastCB in VW.
For both algorithms, we instantiate the oracle as performing online logistic regression with fixed dataset-dependent feature map. This choice is convenient because i) it naturally produces predictions in [0, 1], as required by FastCB, and ii), formally meets our oracle requirements, since is equivalent to online log loss regression with generalized linear model. It can also be viewed as an admissible online square loss oracle, as required by SquareCB (see Appendix E for further discussion). We additionally instantiate SquareCB with linear model and the square loss, which was shown to be the strongest non-adaptive method prior evaluations
[35]. We do not compare with nigh-performing adaptive algorithms like RegCB and AdaCB [13, 35] as these algorithmic modifications are somewhat complementary, and we expect they can be incorporated into FastCB. All oracles are trained with the default VW learning rule, which performs online gradient descent with adaptive updates [27, 41, 56).
For both FastCB and SquareCB, we apply inverse gap weighting (the reweighted and original version, respectively) with time-varying learning rate schedule in which we set 7 = % in Line 6 of Algorithm round t, and likewise for SquareCB. Following Foster et [35], we set Yt = Yut". where E {10, 50, 100, 400, 700, 1 and p E {.25,.5) .5 are hyperparameters.
Evaluation. We evaluate the performance of each algorithm using progressive validation (PV) loss, defined as LP)(T)= = + E.= (a,) [15]. Following Bietti al. [13], we define given algorithm as beating another algorithm significantly on given dataset using an approximate Z-test. For each pair (a, b) of algorithms, Figure I (top row) displays the number of datasets where a beats b significantly. minus the number of datasets where b beats significantly. Figure (bottom row) shows the progressive validation loss for the best-perforning hyperparameter configuration for each algorithm as function of the number of examples. We consider 10 replicates for each dataset, where each replicate has the example order randomly permuted, and plot the average progressive validation loss across the replicates. Error bands in each plot correspond to significance p < 0.05 under the Z-test (cf. (41)). See Appendix E for details.
Results. We find (Figure 1, top row) that FastCB with the logistic loss oracle (FastCB.L) has a positive win-loss difference against SquareCB with both logistic and square loss oracles

---

$ vs +
S.S
S.L
FL
S.S
S.L
FL
SquareCB.
-55
-66
SquareCB.s
-54
-64
SquareCB.L
55
-11
SquareCB.L
54
FastCB.1.
66
11
F.stCB.I
64
3
gina-prior2 (#1041)
kddcup99 (#1113)
covertype (#293)
Progressive val. loss
0.8
0.6
0.4
%
10a
10
10.
10*
10a
1.0 10a
10
10a
Number of examples
FastCB.L
SquareCB.L
Supervised
Figure 1: Top: Head-to-head win-loss differences. Each entry indicates the statistically significant win- loss difference between the row algorithm and the column algorithm. Top-Left: All hyperparameters are optimized on each dataset. Top-Right: Best fixed hyperparameter configuration across all datasets; only the oracle's learning rate optimized per-dataset. Bottom: Progressive validation results for representative datasets depicting significant wins for FastCB.L (left, center) and a loss (right).
(SquareCB.L/SuareCBB. indicating the strongest overall performance. This holds both when hyper- parameters are optimized on a per-dataset basis and for the best global hyperparameter configuration.
Perhaps surprisingly, our results suggest that the largest gains come from switching from the square loss oracle to the logistic loss oracle (SquareCB.S vs. SquareCB.L), while the gains from switching from the original inverse gap weighting strategy to our reweighted version (SquareCB.L vs. FastCB.L) are more marginal. Inspecting the results in more detail, we find that when we compare FastCB.L and SquareCB.L with hyperparameters optimized on per-dataset basis, FastCB.L wins on 14/17 of the datasets in which either algorithm wins significantly, and that all but two of these 14 datasets have L' S 0.2. This suggests that the reweighted inverse gap weighting strategy is indeed helpful when L is small. Figure (bottom row) displays progressive validation performance for L and SquareCB.L for three representative datasets which illustrate this phenomenon.
The fact that FastCB.L does not strictly improve over SquareCB.L on every dataset. in spite of being very similar, might be attributed the fact that the constants the per-round inequality (17) are worse than those in the corresponding inequality for SquareCB.L, suggesting worse performance when L* is not small. Thus, fruitful future direction might be to find strategy with optimal constants for (17).
Discussion
We have given the first efficient algorithm with optimal first-order regret for contextual bandits, resolving a variant of the open problem posed by Agarwal et al. [5]. Let us briefly mention some extensions. First, we believe that techniques can also be used to obtain first-order guarantees for stochastic contextual bandits with an offline log loss oracle (à la Simchi-Levi and Xu with more technical analysis. As another extension, in Appendix D show how to to efficiently obtain first-order regret bound when working with rewards rather than losses. Such guarantee useful when no policy accumulates much reward, as is common in personalization applications. Several other extensions appear to be straightforward, including accommodating infinite action spaces [34].
albeit method
We close with some directions for future work. Directly relevant to our theoretical results to continue the investigation into adaptivity in contextual bandits and reinforcement learning. More broadly, while triangular discrimination has been used in various mathematics disciplines, we are not aware of many applications in algorithm design. Are there other uses for the triangular discrimination in machine learning? We look forward to pursuing these directions.
10

---

Acknowledgments and Disclosure of Funding
We thank Sivaraman Balakrishnan, John Langford, Zakaria Mhammedi, and Sasha Rakhlin for helpful discussions. We also thank Sasha Rakhlin for providing Google Cloud credits used for experiments.
References
[1] N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts. In International Conference Machine Learning, 1999.
[2] A. Agarwal, M. Dudík, S. Kale, J. Langford, and R. E. Schapire. Contextual bandit learning with predictable rewards. International Conference on Artificial Intelligence and Statistics, 2012.
[3] A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning. 2014.
[4] A. Agarwal, S. Bird, M. Cozowicz, L. Hoang, J. Langford, S. Lee, J. Li, D. Melamed, G. Oshri, O. Ribas, S. Sen, and A. Slivkins. Making contextual decisions with low technical debt.
arXiv: 1606.03966, 2016.
[5] A. Agarwal, A. Krishnamurthy, J. Langford, H. Luo, and R. E. Schapire. Open problem: First-order regret bounds for contextual bandits. In Conference on Learning Theory, 2017.
[6] Z. Allen-Zhu, S. Bubeck, and Y. Li. Make the minority great again: First-order regret bound for contextual bandits. International Conference on Machine Learning. 2018.
[7] C. Allenberg, P. Auer, L. Györfi, and G. Ottucsák. Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. International Conference on Algorithmic Learning Theory, 2006.
[8] J.-Y. Audibert and A. B. Tsybakov. Fast learning rates for plug-in in classifiers. The Annals of statistics, 2007.
[9] Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 2002.
[10] Auer, N. Cesa-Bianchi, and C. Gentile. Adaptive and self-confident on-line learning algo- rithms. Journal of Computer and System Sciences, 2002.
[11] I. Benjamini, H. Duminil-Copin G. Kozma, and A. Yadin. Disorder, entropy and harmonic functions. Annals of Probability, 2015.
[12] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. Schapire. Contextual bandit algorithms with supervised learning guarantees. In International Conference on Artificial Intelligence and Statistics, 2011.
[13] A. Bietti, A. Agarwal, and J. Langford. A contextual bandit bake-off. arXiv:1802.04000 2018.
[14] B. Bilodeau, D. J. Foster, and D. Roy. Tight bounds on minimax regret under logarithmic loss via self-concordance. International Conference on Machine Learning, 2020.
[15] A. Blum, A. Kalai, and J. Langford. Beating the hold-out: Bounds for K-fold and progressive cross-validation. In Conference on Computational Learning Theory, 1999.
[16] S. Boucheron, G. Lugosi, and Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
[17] O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. In Summer School on Machine Learning, 2003.
[18] S. Bubeck and M. Sellke. First-order bayesian regret analysis of thompson sampling. In International Conference on Algorithmic Learning Theory, 2020.
[19] R. J. Carroll. Adapting for heteroscedasticity linear models. The Annals of Statistics, 1982.
[20] N. Cesa-Bianchi and G. Lugosi. Minimax regret under log loss for general classes of experts.
In Conference on Computational Learning Theory, 1999.
[21] N.
and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press,
2006.

---

[22] N. Cesa-Bianchi, Y. Mansour, and G. Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 2007.
[23] S. Chen, F. Koehler, A. Moitra, and M. Yau. Online and distribution free robustness: Regression and contextual bandits with Huber contamination. arXiv:2010.04157 2020.
[24] W. Chu, L. Li, L. Reyzin, and R. E. Schapire. Contextual bandits with linear payoff functions. In International Conference on Artificial Intelligence and Statistics, 2011.
[25] T. M. Cover. Universal portfolios. Mathematical Finance, 1991.
[26] L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition. Springer Science & Business Media, 2013.
[27] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011.
[28] A. Erschler and A. Karlsson. Homomorphisms to R constructed from random walks. Annales de I' I'Institut Fourier, 2010.
[29] D. J. Foster and A. Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, 2020.
[30] D. J. Foster, A. Rakhlin, and K. Sridharan. Adaptive online learning. In Advances in Neural Information Processing Systems, 2015.
[31] D. J. Foster, Z. Li, T. Lykouris. K. Sridharan, and É. Tardos. Learning in games; Robustness of fast convergence. In Advances in Neural Information Processing Systems, 2016.
[32] D. J. Foster, A. Agarwal, M. Dudík, H. Luo, and R. E. Schapire. Practical contextual bandits with regression oracles. International Conference on Machine Learning, 2018.
[33] D. J. Foster, S. Kale, H. Luo, M. Mohri, and K. Sridharan. Logistic regression: The importance
of being improper. Conference on Learning Theory, 2018.
[34] D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert. Adapting to misspecificatiin in contextual bandits. Advances in Neural Information Processing Systems, 2020.
[35] D. J. Foster, A. Rakhlin, D. Simchi-Levi, and Y. Xu. Instance-dependent complexity of contex- tual bandits and reinforcement learning: A disagreement-basee perspective. In Conference on Learning Theory, 2021.
[36] Y. Freund and R. F. Schapire. A decision-theoretto generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 1997.
[37] E. Hazan and S. Kale. An online portfolio selection algorithm with regret logarithmic in price variation. Mathematical Finance, 2015.
[38] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimiza- tion. Machine Learning, 2007.
[39] S. Ito, S. Hirahara, T. Soma, and Y. Yoshida. Tight first-and second-order regret bounds for adversarial linear bandits. Advances in Neural Information Processing Systems, 2020.
[40] A. Kalai and Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research, 2002.
[41] N. Karampatziakis and J. Langford. Online importance weight aware updates. In Conference on Uncertainty in Artificial Intelligence, 2011.
[42] W. M. Koolen and T. van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory, 2015.
[43] A. Krishnamurthy, A. Agarwal, T.-K. Huang, H. Daumé III, and J. Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, 2017.
[44] L. Le Cam. Asymptotic methods in statistical decision theory. Springer, 1986.
[45] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandi approach to personalized news article recommendation. In International Conference on the World Wide Web, 2010.
[46] Y. Li, Y. Wang, and Y. Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, 2019.
[47] H. Luo and R. F. Schapire. Achieving all with no parameters: AdaNormalHedge. In Conference on Learning Theory, 2015.
12

---

[48] H. Luo, C.-Y. Wei, and K. Zheng, Efficient online portfolio with logarithmic regret. In Advances in Neural Information Processing Systems, 2018.
[49] Lykouris, K. Sridharan, and É. Tardos. Small-loss bounds for online learning with partial information. Conference on Learning Theory, 2018.
[50] G. Neu. First-order regret bounds for combinatorial semi-bandits. In Conference on Learning Theory, 2015.
[51] M. Opper and D. Haussler. Worst case prediction over sequenees under log loss. In The Mathematics of Information Coding, Extraction and Distribution, 1999.
[52] L. Orseau, T. Lattimore, and S. Legg. Soft-bayes: Prod for mixtures experts with log-loss. In International Conference Algorithmic Learning Theory, 2017.
[53] N. Ozawa. functional analysis proof of Gromov's polynomial growth theorem. Annales Scientifiques de I' l'École Normale Supérieure, 2018.
[54] D. Panchenko. Some extensions of inequality of Vapnik and Chervonenkis. Electronic Communications in Probability, 2002.
[55] A. Rakhlin and K. Sridharan. Sequential probability assignment with binary alphabets and large classes of experts. arXiv:/501.072: 1501007300 2015.
[56] S. Ross, P. Mineiro, and J. Langford. Normalized online learning. In Uncertainty in Artificial Intelligence, 2013.
[57] Y. M. Shtar' kov. Universal sequential coding of single messages. Problemy Peredachi Informat- sii, 1987.
[58] D. Simchi-Levi and Y. Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. arXiv:2003. 12699, 2020.
[59] N. Srebro, K. Sridharan, and Tewari. Smoothness, low noise and fast rates. Advances in Neural Information Processing Systems, 2010.
[60] A. Takeshi. Advanced econometrics. Harvard university press, 1985.
[61] A. Tewari and S. A. Murphy. From ads to interventions: Contextual bandits in mobile health.
In Mobile Health, 2017.
[62] F. Topsøe. Some inequalities for information divergence and related measures of discrimination.
IEEE Transactions on Information Theory, 2000.
[63] S. A. van de Geer. Empirical Processes M-Estimation. Cambridge University Press, 2000.
[64] J. Vanschoren, J. N. Van Rijn, B. Bischl, and L. Torgo OpenML: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 2014.
[65] V. N. Vapnik and A. A. Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. Measures of Complexity, 1971.
[66] I. Vincze. On the concept and measure of information contained in an observation. In Contribu- tions to Probability. Elsevier, 1981.
[67] V. Vovk. A game of prediction with expert advice. In Conference on Computationnl Learning Theory, 1995.
[68] Y. Xu and A. Zeevi. Upper counterfactual confidence bounds: A new optimism principle for contextual bandits. arXiv:2007.07876 2020.
[69] Y. Yang. Minimax nonparametric classification. I. Rates of convergence. IEEE Transactions Information Theory, 1999.
[70] A. Yehudayoff. Pointer chasing via triangular discrimination. Combinatorics, Probability and Computing, 2020.
[71] Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 2006.
[72] Z. Zhang, Yang, X. Ji, and S. Du. Variance-awan confidence set: Variance-deepndeent bound for linear bandits and horizon- free bound for linear mixture MDP. Neural Information Processing Systems (NeurIPS), 2021.
[73] D. Zhou, Q Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576.
PMLR, 2021.
13


Reviews:
[{"review_id": "xhfPS2Y4lvH", "reviewer": "Reviewer_JNTi", "summary": "Optimal first-order regret bound for contextual bandits.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper built on the recent SquareCB paper and derived an optimal first-order regret bound for contextual bandits. The main change of the algorithm is to use a cross-entropy loss instead of square loss. It's interesting that the authors claim that SquareCB can not achieve the optimal first-order bound which means cross-entropy loss improves a lot. I nearly have no complaint about this work since the contribution is clear and the new technique used is highlighted. Experiments are included which is appreciated for a theory paper. One minor point is that if it is possible to design experiments to verify your conjecture or argument about the sub-optimality of SquareCB in terms of the first-order regret. Or is there any way to design experiments to justify the first-order regret is a strong measure? \n\n======\n\nI have read the response.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ubBRNmjpFe9", "reviewer": "Reviewer_iChz", "summary": "This work is about contextual bandits in the low noise regime. It introduces the first efficient algorithm with a small loss bound. The latter is close to a previous algorithm SquareCB. However, the main idea is to use an online regression oracle working with a log-loss instead of a square loss. They also show that this change is fundamental as SquareCB can not achieve small loss bound. Some experiments have also been done.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of paper is to have design the first efficient algorithm for contextual bandits with small loss bound under the realizability assumption. The algorithm relies on a regression oracle using the log-loss. The authors show that using the log-loss is key to achieve the small loss bound.\n\nThe paper is very well written. I particularly appreciate the effort to explain the main ideas that make the proof work.\nTheorem and assumptions are well stated. The proofs are easy to follow. I have only checked the core of the proof of Theorem 1 which seems correct.\n\nThe results seems important both in theory and practice. Moreover, the theoretical tools used like triangular discrimination are promising to be used in future works.\n\nTo conclude, this work is clearly a good paper.\n\nI have only few remarks :\n- It may interesting to give real computational complexity for several cases. Indeed, the efficiency of the algorithm may relativized because some regression algorithms for log-loss are not so cheap e.g. exponential forecaster.\n- In example 2 (p.23), the references given suggest that the log-loss with linear function could be seen as a portfolio selection problem. However, it is not completely clear to me that it is true. For example, the loss induced by d=2, \\phi(x,a) = [1,0], y =1/2 does not seem to correspond to a portfolio selection loss.\n\nTypos/omissions:\n- l.113 definition of z_t ?\n- l.216 oft = often ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "gEnmh-Y8LT4", "reviewer": "Reviewer_8uE8", "summary": "The authors establish first-order regret guarantees for contextual bandits, that is, the $\\sqrt{T}$ dependence on the horizon is replaced by the total loss incurred by the optimal policy. This requires the algorithm to adapt to \"low noise\".\nThe proposed algorithm, called FastCB, is a variant of SquareCB by Foster et al, which is based on a reduction to online regression. These kind of algorithms have two components: an online \"regression oracle\" that learns to predict rewards, and an allocation rule that selects actions based on these predictions. The main innovation w.r.t. SquareCB is replacing the loss of the regression oracle, from square to logarithmic. The allocation rule is also modified to exploit this change. The authors derive first-order regret bound for FastCB.\nThe change of loss is further motivated by analyzing the off-line cost-sensitive classification setting, which could be of independent interest. The authors show that a plug-in classifier optimizing the squared loss cannot achieve first-order guarantees in general, while the latter is possible by using the logarithmic loss. The argument is two steps: first the excess risk is bounded by the triangular discrimination between true and predicted loss. Then they show that, by minimizing the logarithmic loss, the algorithm also makes the triangular discrimination small. The authors conjecture that triangular discrimination could be a useful tool for studying plug-in classification and contextual bandits in general.\nExtensive experiments show that FastCB improves over SquareCB. Ablation shows that the gain is mostly due to the change of loss.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this seems a solid contribution to the contextual bandit literature.\nI checked the proofs and found no major problems.\nThe paper is also well written, clear, and well organized. The authors make a good job in communicating the key ideas and the logic behind the theoretical analysis.\nOriginality is limited, since the proposed algorithm is a variant of SquareCB. The main elements of novelty are in the theoretical methodology. The way triangular discrimination is used to derive upper bounds could indeed be a useful addition to the bandit theory tool set (however, see my issue below)\nThe results are nonetheless significant: in fact, this paper solves (a variant of) a COLT open problem by Agarwal et al.\n\nMy main issue/question is on the importance given to the triangular discrimination. Although it does appear in key theoretical passages, it is only to be bounded by other divergences. The key concept of Appendix B seems to be the Hellinger divergence, not the triangular discrimination (in Theorem 5 the triangular discrimination is even completely bypassed with a Hellinger bound).\nIn appendix C, the same happens with the KL divergence. The final algorithm has no trace of this concept, only implicitly making the triangular discrimination small.\nWhat motivates the importance this paper assigns to the triangular discrimination, besides proof techinques? Does it have an intuitive meaning in the context of plug-in classification and contextual bandits? Can we gain something by using triangular discrimination in a more explicit way in algorithms?\n\nMinor issues:\n1. You should state up front that what you solve is a variant (albeit small) of the original COLT open problem\n2. In the proof of Theorem 6, I think the key point is the following (lines 741-746): since the regressor is minimizing the log loss, and you are assuming realizability, the empirical log loss of the regressor is less or equal than that of the true function. This appears in the proof as $C_a(\\widehat{f},D)\\ge 0$. I think the logic behind this passage should be made more explicit since it's the point where you show that optimizing the log loss is important.\n3. The appendix tends to be less organized, with ancillary results appearing suddenly in the main proofs, sometimes with in-place and sometimes with dislocated proofs. A better organization would make the proofs easier to follow.\n4. Experiments: you should report the number of independent runs and the meaning of the confidence areas in the main paper too\n5. I would mention that $A=|\\mathcal{A}|$ at the beginning of Section 2\n6. Using \"regret\" also for the offline setting is a bit confusing. \"Excess risk\" would be more clear. For the same reason, I would replace $L^\\star$ with a different notation in Section 3.1\n7. Line 273 \"even for SquareCB\": this is not very clear. Do you mean \"without changing the allocation rule\"?\n8. Line 742: what is $y_i(a)$?\n9. In the proof of Lemma 3, I think $\\pi^\\star$ should be $\\pi$", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned by the authors, the work is mostly theoretical, hence of little immediate impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "d-3bkN4Vs7R", "reviewer": "Reviewer_KdtT", "summary": "The authors propose a novel algorithm for contextual bandits in the adversarial setting, where the loss functions belong to some parametric class. They show that their algorithm achieves the same \"first order bound\" (where the regret is upper bounded by a function of the loss of the optimal arm) as known algorithms, while being, in some cases, easier to implement. Overall the paper is well written although quite technical in some places. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) The algorithm requires the value of the loss of the best arm as an input. How is one supposed to know this information in practice ? Knowing this information certainly is possible once all of the losses have been observed, but otherwise it seems difficult.\n\n2) The authors discuss \"computational efficiency\" only by discussing how many times the prediction subroutine must be called. However, while this might be of theoretical interest (if for some reason one only wants to consider algorithms that are based on a prediction subroutine as described by the authors), what matters most is the actual amount of time and space required to implement the whole algorithm. A discussion of this and a comparison with existing algorithms would make the argument that the proposed algorithm is computationally faster more convincing.\n\n3) The paper contains numerical experiments, which is very good. What is perhaps missing is the comparison of running times of different algorithms (since the main claim of the authors is the design of computationally efficient algorithms).\n\nMinor Remarks:\n- Isn't Assumption 2 always true providing that $Reg_{KL}(T)$ is chosen large enough ? Isn't this simply a definition ?\n- In equation (3) what is $z_t$ ? And why is it that function $f$ now only takes one argument ? It was defined as a function of two arguments.\n- the way that the algorithm is presented in the introduction makes it sound more complex than it actually is, and the algorithm operates as do all adversarial bandit algorithms: they predict the loss of each arm using some estimation procedure, and then draw a distribution where the probability to select an action is some simple decreasing function of the loss estimate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper advances the state of the art in contextual bandits by proposing an interesting extension of the SquareCB algorithm of Foster and Rakhlin (ICML 2020), and showing that this method efficiently achieves optimal first-order regret guarantees under realistic conditions. This solves a COLT open problem.

The paper has received uniformly positive reviews, with the reviewers praising the solid theoretical contributions and the thorough experimental evaluation. I myself have found the contribution to be significant and the techniques to be highly original. Overall, I believe that this outstanding paper is likely to have a long-lasting impact in the contextual-bandit literature, and clearly it should be accepted for publication at NeurIPS 2021.
Decision: Accept (Oral)