Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
Year: 2021

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 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 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 informationtheoretic 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 [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.

heading: 1 Introduction
text: In the contextual bandit problem, a 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 an uncertain environment, but does not need to engage in long-term planning or credit assignment. Owing to the availability of high-quality engineered reward metrics, 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 approximation (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-purpose 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 are beginning to take shape, we still lack an understanding of adaptive or data-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 (NeurIPS 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 a 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 [5] asks whether there exist contextual bandit algorithms that achieve a certain data-dependent first-order regret bound, which scales with the cumulative loss L? of the best policy, rather than with the time horizon T . For multiarmed bandits, first-order regret bounds (also known as small-loss bounds or fast rates) typically scale as √ L? and imply faster convergence for “easy” problems, interpolating between the optimal √ T rate for worst-case instances and constant/logarithmic 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-world deployment. Subsequently, Allen-Zhu, Bubeck, and Li [6] gave an inefficient algorithm with an optimal first-order regret guarantee, resolving the former question, but the existence of efficient first-order algorithms remained open.
Contributions. We give the first optimal and efficient contextual bandit algorithm with a first-order regret guarantee, providing a resolution to the second open problem raised by Agarwal et al. [5]. Our algorithm, FastCB, builds on a recent line of research that develops efficient contextual bandit algorithms based on the computational primitive of (online/offline) 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 a high-level, the design of FastCB leverages two key techniques:
1. First-order regret for plug-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-theoretic quantity called the triangular discrimination [66, 44, 62].
2. Reweighted inverse gap weighting: Moving from statistical learning to contextual bandits, we transform predictions into distributions over actions using a scale-sensitive refinement to the inverse-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 benchmark 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 a 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 an 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π∈Π ∑T t=1 `t(π(xt)). 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 1 FastCB (“Fast Rates for Contextual Bandits”) 1: parameters:
Learning rate γ > 0. Online regression oracle AlgKL.
2: for t = 1, . . . , T do 3: Receive context xt.
// Compute oracle’s predictions (Eq. (4)).
4: For each action a ∈ A, compute ŷt(xt, a) := Alg(t)KL (xt, a ; {(xi, ai, `i(ai))} t−1 i=1). 5: Let bt ∈ argmina∈A ŷt,a. // Reweighted inverse gap weighting.
6: For each a 6= bt, define pt,a = ŷt(xt,bt)Aŷt(xt,bt)+γ(ŷt(xt,a)−ŷt(xt,bt)) . Let pt,bt = 1− ∑ a6=bt pt,a. 7: Sample at ∼ pt and observe loss `t(at). 8: Update AlgKL with example (xt, at, `t(at)). 9: end for
regression-based algorithms are typically simpler and faster than classification-based 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 3 describes the motivation and analysis ideas behind FastCB, beginning from new techniques for statistical learning with regression-based 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 to Appendix A.

heading: 2 Main Result: An Efficient First-Order Algorithm for Contextual Bandits
text: We begin by formally introducing the contextual bandit model. At each round t ∈ [T ], the learner observes a context xt ∈ X , selects an action at ∈ A, then observes a loss `t(at) ∈ [0, 1] for the action they selected. We assume that A := |A| is finite and that each loss function `t : A → [0, 1] is drawn independently from a fixed distribution P`t(· | xt), where P`1 , . . . ,P`T and x1, . . . , xT are selected by a potentially adaptive adversary.
We make a standard realizability assumption [24, 2, 32, 29]. Namely, we assume that the learner has access to a class of value functions F ⊂ (X ×A → [0, 1]) (e.g., neural networks, kernels, or forests) that models the mean of the loss distribution. Assumption 1 (Realizability). There exists f? ∈ F such that for all t, f?(x, a) = E[`t(a) | xt = x].
The aim of the learner is to minimize their regret to the optimal policy π?(x) := argmina∈A f ?(x, a):
RegCB(T ) := T∑ t=1 `t(at)− T∑ t=1 `t(π ?(xt)). (1)
For each f ∈ F , we let πf (x) := argmina∈A f(x, a) be the induced policy. We let Π := {πf | f ∈ F} be the induced policy class.
Further notation. We adopt standard big-oh notation, and write f = Õ(g) to denote that f = O(gmax{1,polylog(g)}). We use . only in informal statements to highlight the most salient elements of an inequality. We use a ∨ b = max{a, b} and a ∧ b = min{a, b}.

heading: 2.1 Algorithm and Main Result
text: FastCB builds on the SquareCB algorithm of Foster and Rakhlin [29], which provides an efficient, minimax-optimal reduction from contextual bandits to online regression with the square loss. Compared 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 a fundamental distinction for first-order guarantees.
Online regression oracles. In more detail, an online regression oracle, which we denote by AlgKL (for “Kullback-Leibler”) operates in the following protocol: For each time t, the algorithm receives a context-action pair (xt, at), produces a prediction ŷt ∈ [0, 1], then receives a response yt. The algorithm’s prediction error is measured through the binary logarithmic/cross-entropy loss ,
`log(ŷ, y) := y log(1/ŷ) + (1− y) log(1/(1− ŷ)). (2) The algorithm’s goal is to ensure that the log loss regret to F is minimized for all sequences. Assumption 2. The algorithm AlgKL guarantees that for every (possibly adaptively chosen) sequence x1:T , a1:T , y1:T , the log loss regret is bounded by a known function RegKL(T ):
T∑ t=1 `log(ŷt, yt)− inf f∈F T∑ t=1 `log(f(xt, at), yt) ≤ RegKL(T ), (3)
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 4 for examples. While log loss regret is a more stringent notion of performance than square loss regret, it nonetheless has a relatively mature theory characterizing optimal rates [57, 51, 20, 14].
The algorithm. FastCB (Algorithm 1) is a 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 t, the algorithm first computes the estimated loss
ŷt(xt, a) := Alg (t) KL (xt, a ; {(xi, ai, `i(ai))} t−1 i=1) (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 a 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 bt := argmina∈A ŷt(xt, a) be the greedy action according to the predicted losses, we define
pt,a := ŷt(xt, bt)
Aŷt(xt, bt) + γ(ŷt(xt, a)− ŷt(xt, bt)) ∀a 6= bt, and pt,bt := 1− ∑ a6=bt pt,a, (5)
where γ > 0 is a learning rate parameter. Given this distribution, FastCB simply samples at ∼ pt, then updates the oracle with the resulting tuple (xt, at, `t(at)). Our main theorem shows that this leads to an optimal first-order regret bound.1
Theorem 1 (Main theorem). Suppose Assumptions 1 and 2 hold. Then Algorithm 1 guarantees that for all sequences with E [∑T t=1 `t(π ?(xt)) ] ≤ L?, by choosing γ = √ AL?/3RegKL(T ) ∨ 10A,
E[RegCB(T )] ≤ 40 √ L? ·ARegKL(T ) + 600ARegKL(T ). (6)
The dominant term in this regret bound scales with √ L? whenever the oracle AlgKL attains a fast log(T )-type regret bound. As a simple example, whenever F is finite, we can instantiate AlgKL so that RegKL(T ) ≤ log|F| [67], whereby FastCB enjoys optimal [2] first-order regret:
E[RegCB(T )] ≤ O (√ L? ·A log|F|+A log|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 O(A) per step; implementation is trivial.
• Flexibility. Working with regression as a primitive means that the algorithm easily accomodates rich, potentially nonparametric function classes, and we can instantiate Theorem 1 to get provable end-to-end regret guarantees for concrete classes of interest. For example, for linear models in Rd we can efficiently attain RegKL(T ) ≤ O(d log(T )) [25, 40], which yields a first-order regret bound RegCB(T ) . √ L? ·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 other hand, even for function classes where provable algorithms are not available, regression is amenable to practical heuristics (e.g., gradient descent). See Section 4 for detailed examples.
1While 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 estimated loss Lt = ∑t τ=1 `τ (aτ ), and applying the doubling trick. Theorem 1 also readily extends to high probability.

heading: 3 Overview of Analysis
text: We now outline the algorithmic principles and analysis ideas behind FastCB. First, in Section 3.1, we take a 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 as an introduction to 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-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 instantaneous contextual bandit regret to the triangular discrimination for the regression oracle on a per-round basis (Theorem 4). Full proofs are deferred to Appendices B and C.

heading: 3.1 Warmup: First-Order Regret Bounds for Plug-In Classifiers
text: For the simpler problem of cost-sensitive classification in statistical learning, the literature on plug-in classification shows that whenever realizability conditions such as Assumption 1 hold, we can 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 is as follows. We receive a dataset Dn consisting of n context-loss pairs (xt, `t) ∼ D i.i.d., where the entire loss function `t : A → [0, 1] is observed. Analogously to Assumption 1, we assume access to a function class F ⊆ (X × A → [0, 1]) such that ED[`(a) | x] = f?(x, a) for some f? ∈ F , and take Π := {πf | f ∈ F} as the induced class of policies. Our goal is to learn a policy π̂ : X → A such that the regret (or, excess risk)
L(π̂)− L? (7) is small, where L(π) := ED[`(π(x))] and L? := L(π?), with π? := πf? . Formally, this an easier problem than contextual bandits, since any algorithm with a regret bound for contextual bandits yields a bound on the cost-sensitive classification regret (7) via online-to-batch conversion.
A classical result in statistical learning [65, 54, 59] shows that if we compute the policy/classifier π̂ := argminπ∈Π ∑n t=1 `t(π(xt)) that minimizes the empirical risk, we obtain a first-order regret bound of the form2
E[L(π̂)]− L? . √ L? · log|F|
n + log|F| n . (8)
This is an optimal first-order guarantee, but computing π̂ is typically computationally intractable, even for relatively simple policy classes. As an 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]3), shows that if we perform least-squares via
f̂LS := argmin f∈F n∑ t=1 ∑ a∈A (f(xt, a)− `t(a))2,
and take π̂LS := πf̂LS as our classifier, then under the realizability assumption we are guaranteed E[L(π̂LS)]− L? . √ A log|F|
n . (9)
While this result is rate-optimal, it is not first-order, and first-order regret bounds for plug-in classification are conspicuously absent from the literature. We show that this is fundamental. Theorem 2 (Failure of least-squares for plug-in classification). Let A = {1, 2} and X = {1, 2}. For every n > 108, there exists a function class F ⊆ (X ×A → [0, 1]) with |F| = 2, and a realizable distribution D such that L? ≤ 2 7
n < 1, yet L(π̂LS)− L ? ≥ 2−5 √ 1 n with probability at least 1/10.
2Following the convention in contextual bandit literature, we focus on finite classes with |F| <∞ in this discussion, but one can extend our observations to general classes, e.g., using the machinery of Zhang [71].
3This result is well-known in the binary setting. We are not aware of a reference for the multiclass/costsensitive version here, though it is implicit in many recent works on contextual bandits.
Since the instance in this theorem has √
L?·A log|F| n . 1 n , we conclude that plug-in classification
with least-squares fails to attain the first-order regret bound in (8) with constant probability; a lower bound in expectation follows immediately.

heading: 3.1.1 Fast Rates for Plug-In Classifiers: Triangular Discrimination and Logarithmic Loss
text: It 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 to 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 to the rate (9).
Step 1. First, using a generic regret decomposition based on realizability, for any f we have
L(πf )− L? ≤ 2 max π∈{πf ,π?}
ED ∣∣f(x, π(x))− f?(x, π(x))∣∣. (10)
Step 2. Next, by Cauchy-Schwarz, for any policy π we have
ED ∣∣f(x, π(x))− f?(x, π(x))∣∣ ≤ (ED∣∣f(x, π(x))− f?(x, π(x))∣∣2)1/2, (11)
which we may further upper bound by (∑ a∈A ED ∣∣f(x, a)− f?(x, a)∣∣2)1/2.
Step 3. Finally, under realizability, a standard concentration argument based on Bernstein’s inequality implies that the least-squares estimator satisfies
E [∑ a∈A ED ∣∣f̂LS(x, a)− f?(x, a)∣∣2] . A log|F| n . (12)
Combining this bound with Step 2, we conclude that E[L(π̂LS)]− L? ≤ √ A log|F|/n.
The issue here is that even in the presence of low noise, the squared error in (12) shrinks no faster than 1n . This holds even if L
? ∝ 1n , as in the lower bound construction for Theorem 2. Consequently, once we apply Cauchy-Schwarz in Step 2, we lose all hope of attaining a first-order bound.
Our starting point toward improving this result is a refined application of Cauchy-Schwarz, by which we can replace the right hand side of (11) with(
ED[f(x, π(x)) + f?(x, π(x))] · ED
[( f(x, π(x))− f?(x, π(x)) )2 f(x, π(x)) + f?(x, π(x)) ])1/2 . (13)
The ratio term above is closely related to the triangular discrimination, an information-theoretic divergence measure which we define for p, q ∈ RA+ as4
D∆(p ‖ q) := ∑ a (pa − qa)2 pa + qa . (14)
The triangular discrimination—also known as the symmetric χ2-divergence and Vincze-Le Cam distance—is a fundamental, often-overlooked quantity in information theory [66, 44, 62]. Since readers may be unfamiliar, we record some basic facts.
Proposition 1 (Topsøe [62]). The triangular discrimination D∆, over the domain ∆A, i) is the f -divergence given by f(t) = (t−1) 2
t+1 , ii) is the square of a distance metric, and iii) is equivalent (up to a multiplicative constant) to both Hellinger distance and Jensen-Shannon divergence.
4The triangular discrimination is traditionally defined over the simplex ∆A, but for our application it is useful to 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 Cauchy-Schwarz in (13), and ii) small enough (compared to the more standard χ2-divergence) to facilitate minimizing from samples.
Returning to (13), we can upper bound with the triangular discrimination and leverage a certain self-bounding property that it satisfies to arrive at the following improvement on Step 1/Step 2. Lemma 1 (Regret decomposition for triangular discrimination). For any f : X ×A → [0, 1],
L(πf )− L? ≤ 8(L? · ED[D∆(f?(x, ·) ‖ f(x, ·))])1/2 + 17ED[D∆(f?(x, ·) ‖ f(x, ·))]. (15)
Lemma 1 shows that low triangular discrimination (i.e. ED[D∆(f?(x, ·) ‖ f(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 us to bound it by the Kullback-Leibler divergence:
D∆(f ?(x, ·) ‖ f(x, ·)) = ∑ a (f(x, a)− f?(x, a))2 f(x, a) + f?(x, a) ≤ 2 ∑ a dKL(f ?(x, a) ‖ f(x, a)), (16)
where dKL(p ‖ q) := p log(p/q) + (1− p) log((1− p)/(1− q)) is the binary KL-divergence. Note that the triangular discrimination is critical here, as the opposite inequality holds for χ2-divergence. This bound suggests that we should minimize the logarithmic loss, since—under the realizability assumption—this loss is closely related to the KL-divergence. In particular, we show (Theorem 6 in Appendix B), that by taking the estimator
f̂KL := argmin f∈F n∑ t=1 ∑ a∈A `log(f(xt, a), `t(a)),
we are guaranteed that with high probability, ED [ D∆(f ?(x, ·) ‖ f̂KL(x, ·)) ] . A log|F|n . Putting everything together, we arrive at a first-order regret bound for the plug-in classifier π̂KL := πf̂KL . 5 Theorem 3 (First-order regret bound for plug-in classification). Let δ ∈ (0, 1). Suppose that Assumption 3 holds. Then with probability at least 1− δ, we have
L(π̂KL)− L? ≤ 16 √ L? ·A (log |F|+ log(A/δ))
n + 68 A (log |F|+ log(A/δ)) n .
Interestingly, applications of the triangular discrimination similar to Lemma 1 have recently been discovered across a 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 a related non-negative χ2-divergence to provide first-order Bayesian regret bounds for Thompson sampling for the multi-armed bandit.

heading: 3.2 Moving to Contextual Bandits: Inverse Gap Weighting meets Triangular Discrimination
text: FastCB builds on the development for plug-in classifiers in Section 3.1 but with two key differences. First, since we need to make decisions on the fly for arbitrary sequences of contexts, the algorithm estimates losses using an online regression oracle for the logarithmic loss, as described in 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 a certain per-round inequality that links the instantaneous contextual bandit error to the triangular discrimination between the oracle’s prediction ŷt and the true loss function f?. Theorem 4 (First-order per-round inequality). Let y ∈ [0, 1]A be given and b ∈ argmina ya. Define pa =
yb Ayb+γ(ya−yb) for a 6= b, and pb = 1 − ∑ a6=b pa. If γ ≥ 2A, then for all f ∈ [0, 1]A and
a? ∈ argmina fa, we have∑ a
pa(fa − fa?)︸ ︷︷ ︸ CB regret
≤ 5A γ ∑ a
pafa︸ ︷︷ ︸ bias from exploring
+ 7γ ∑ a pa (ya − fa)2
ya + fa︸ ︷︷ ︸ error from exploiting
. (17)
5The dependence on A in this result can be improved under additional assumptions on the loss distribution. As an example, in Appendix B we remove the leading A factor for the special case of multiclass classification.
The inequality (17) may be thought of as an algorithmic analogue of the refined Cauchy-Schwarz lemma (15), with the learning rate γ modulating the tradeoff between exploration and exploitation. Applying the inequality for each step t (with p = pt, y = ŷt(xt, ·), and f = f?(xt, ·)), and using the Pinsker-type inequality (16), we are guaranteed that
E[RegCB(T )] ≤ 5A
γ E[LT ] + 14γ ·RegKL(T ), (18)
where LT := ∑T t=1 `t(at). By a standard argument, this implies the main result in Theorem 1.
Compared to 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—which leads to less exploration when the optimal loss is small—we are able to replace a constant exploration bias of order A γ incurred by SquareCB with the scale-sensitive bias term A γ · ∑ a pafa in (17), leading to a 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 is taken care of by the log loss oracle.

heading: 4 Examples
text: 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 1 to 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 that6 RegKL(T ) ≤ log|F|. With this choice, FastCB satisfies E[RegCB(T )] ≤ O (√ L? ·A log|F|+A log|F| ) .
Example 2 (Low-dimensional linear functions). Suppose that F takes the form F = {(x, a) 7→ 〈w, φ(x, a)〉 | w ∈ ∆d}, where φ(x, a) ∈ Rd+ is a fixed feature map with ‖φ(x, a)‖∞ ≤ 1. Then the continuous exponential weights algorithm ensures that RegKL(T ) ≤ O(d log(T/d)), and can be implemented in poly(d, T ) time per step using log-concave sampling [25, 40].7 With this choice, FastCB satisfies E[RegCB(T )] ≤ O (√ L? ·Ad log(T/d) +Ad log(T/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 is 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 ) ≤ Õ(d2), but runs in time O(Td2.5) 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 guarantees to rich, nonparametric function classes. Example 3 (High/infinite-dimensional linear functions). Suppose that F takes the form F ={
(x, a) 7→ 12 (1 + 〈w, φ(x, a)〉) | ‖w‖2 ≤ 1 }
, where ‖φ(x, a)‖2 ≤ 1 is a fixed feature map. For this setting, Rakhlin and Sridharan [55, Section 6.1] show that the FTRL algorithm with log-barrier regularization has8 RegKL(T ) ≤ O( √ T log(T )). This algorithm can be implemented in timeO(d)
per step, and satisfies the dimension-independent rate E[RegCB(T )] ≤ O ( (AL?)1/2T 1/4 +A √ T ) .
Let us interpret the bound in Example 3. First, we recall that the minimax optimal rate for this setting is A1/2T 3/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 an expressive function class. On the other hand, if L? is constant, the bound in Example 3 improves to O(A √ T ), which beats the worst-case rate. While one might hope that a tighter rate of the form, e.g., (L?)3/4, might be possible, by adapting a 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. 6See Proposition 6 for a proof that the loss `log(ŷ, y) is mixable over the domain [0, 1]. 7Our setup directly reduces to universal portfolio selection as follows: When yt is binary, we reduce by using features φ(xt, at) when yt = 1, and using features 1d − φ(xt, at) when yt = 0. The case where yt ∈ [0, 1] can be reduced to this setting by sampling from Ber(yt).
8This is technically only proven for the case where y ∈ {0, 1}, but the proof easily extends to y ∈ [0, 1].
Example 4 (Generalized linear models). Let F = { (x, a) 7→ σ(〈w, φ(x, a)〉) | w ∈ Rd, ‖w‖2 ≤ 1 }
, where σ(t) = 1/(1 + e−t) is the logistic link function and φ(x, a) is a fixed feature map. In this case, the map w 7→ `log(σ(〈w, φ(x, a)〉), y) is equivalent to the standard logistic loss function applied to 〈w, φ(x, a)〉, and we can use the algorithm from Foster et al. [33] to obtain RegKL(T ) ≤ O(d log(T/d)) and RegCB(T ) ≤ Õ( √ L? ·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 1 to give new regret bounds for general classes.

heading: 5 Experiments
text: 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 a 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-based 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 1 otherwise.
Algorithms and oracle. We use the standard implementation of SquareCB in the Vowpal Wabbit (VW) online learning library,9 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 a fixed dataset-dependent feature map. This choice is convenient because i) it naturally produces predictions in [0, 1], as required by FastCB, and ii), it formally meets our oracle requirements, since it is equivalent to online log loss regression with a 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 a linear model and the square loss, which was shown to be the strongest non-adaptive method in prior evaluations [35]. We do not compare with high-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 a time-varying learning rate schedule in which we set γ = γt in Line 6 of Algorithm 1 at round t, and likewise for SquareCB. Following Foster et al. [35], we set γt = γ0tρ, where γ0 ∈ {10, 50, 100, 400, 700, 103} and ρ ∈ {.25, .5} are hyperparameters. Evaluation. We evaluate the performance of each algorithm using progressive validation (PV) loss, defined as LPV(T ) = 1T ∑T t=1 `t(at) [15]. Following Bietti et al. [13], we define a given algorithm as beating another algorithm significantly on a given dataset using an approximate Z-test. For each pair (a, b) of algorithms, Figure 1 (top row) displays the number of datasets where a beats b significantly, minus the number of datasets where b beats a significantly. Figure 1 (bottom row) shows the progressive validation loss for the best-performing hyperparameter configuration for each algorithm as a 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
9https://vowpalwabbit.org
(SquareCB.L/SquareCB.S), indicating the strongest overall performance. This holds both when hyperparameters 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 a 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? ≤ 0.2. This suggests that the reweighted inverse gap weighting strategy is indeed helpful when L? is small. Figure 1 (bottom row) displays progressive validation performance for FastCB.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 to the fact that the constants in 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, a fruitful future direction might be to find a strategy with optimal constants for (17).

heading: 6 Discussion
text: 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 our 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 [58])—albeit with a more technical analysis. As another extension, in Appendix D we show how to use our method to efficiently obtain a first-order regret bound when working with rewards rather than losses. Such a guarantee is 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].
We close with some directions for future work. Directly relevant to our theoretical results is 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.
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.

Review summaries:
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. 

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.

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". The 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. The 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. Extensive experiments show that FastCB improves over SquareCB. Ablation shows that the gain is mostly due to the change of loss.