First- and Second-Order Bounds for Adversarial Linear Contextual Bandits
Authors: Julia Olkhovskaya
Jack Mayo
Tim van Erven
Gergely Neu
Chen-Yu Wei
Venue: NeurIPS 2023 poster (2023)
Keywords: contextual bandits
bandits
sequential learning
regret bounds

Abstract: We consider the adversarial linear contextual bandit setting, which
allows for the loss functions associated with each of $K$ arms to change
over time without restriction. Assuming the $d$-dimensional contexts are
drawn from a fixed known distribution, the worst-case expected regret
over the course of $T$ rounds is known to scale as $\tilde O(\sqrt{Kd
T})$. Under the additional assumption that the density of the contexts
is log-concave, we obtain a second-order bound of order $\tilde
O(K\sqrt{d V_T})$ in terms of the cumulative second moment of the
learner's losses $V_T$, and a closely related first-order bound of order
$\tilde O(K\sqrt{d L_T^*})$ in terms of the cumulative loss of the best
policy $L_T^*$. Since $V_T$ or $L_T^*$ may be significantly smaller than
$T$, these improve over the worst-case regret whenever the environment
is relatively benign. Our results are obtained using a truncated version
of the continuous exponential weights algorithm over the probability
simplex, which we analyse by exploiting a novel connection to the linear
bandit setting without contexts.

First- and Second-Order Bounds for Adversarial Linear Contextual Bandits
Julia Olkhovskaya
Jack Mayo²
Tim van Erven
Gergely Neu
Chen-Yu Wei
Deppartment of Intelligent Systems, Delft University Technology, Delft, The Netherlands Korteweg- de Vries Institute for Mathematics, University of Amsterdam, Amsterdam, The
Netherlands
Al group. DTIC, Universitat Pompeu Fabra, Barcelona, Spain A MIT Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, MA, USA
Abstract
We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of K arms to change over time without restriction. Assuming the d-dimensional contexts drawn from fixed known distribution, the worst-case expected regret over the course of rounds is known to scale as Ó(v (Kd)). Under the additional assumption that the density of the contexts is log-concave, we obtain a second-order bound of order Ö(K vdVT) in terms of the cumulative second moment of the learner's losses Vr, and a closely related first-order bound of order Ö(K /dp) in terms of the cumulative loss of the best policy Lý. Since Vr or LÝ may be significantly smaller than T' these improve over the worst-case regret whenever the environment is relatively benign. Our results are obtained using a truncated version of the continuous exponential weights algorithm over the probability simplex, which we analyse by exploiting a novel connection to the linear bandit setting without contexts.
Introduction
The contextual bandit problem is generalization of the multi-armed bandit setting in which learner observes relevant contextual information before choosing an arm. The goal of the learner is to minimize the excess cumulative loss of the chosen arms compared to the best fixed policy for mapping contexts to arms. This framework addresses a broad range of important real-world problems like sequential treatment allocation (Tewari and Murphy, 2017), online recommendation (Beygelzimer et al., 2011 1) or online advertising (Li et al., 2010), and is actively used in practice (Agarwal et al., 2016). Numerous variants of the setting have been studied, which differ in the assumptions they make about the losses and the contexts. In this paper, we focus on the recently introduced setting of Neu and Olkhovskaya (2020) where the contexts are dinee-dimensionall i.i.d. random vectors, and the losses are time-varying linear functions of the context that may potentially be generated by an adversary. In this setting, the worst-case rate for the expected regret is known to be Õ(VT) for time horizon T' (Neu and Olkhovskaya, 2020).
Our main contribution is to replace the worst-case rate by adaptive bounds. Specifically, we obtain a bound Ō( Ö(VVr) in terms of a quadratic measure variance Vr for the losses of the algorithm, and a bound of Ô( LT)), where L is the cumulative loss incurred by the optimal policy. Such bounds in terms of L VT generally referred as first-order and second-order bounds, respectively,
WWrk was done when the author affiliated with Vrije Universiteit Amsterdam.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and have been extensively studied in the bandit literature. They can lead to much stronger guarantees in the often realistic case when T is large, but the losses vary little or when there exists policy with very low cumulative loss.
Worst-case guarantees in terms of T have first been proved for the contextual bandit problem with finite policy classes by Auer et al. (2002b), with further improvements by Beygelzimer et al. (201 1). These methods can deal with adversarial losses and contexts, but only work for finite policy classes and have run-time scaling linearly with the size of the class-which is generally unacceptable in practice. This latter challenge has been addressed by a line of work culminating in Agarwal et al. (2014), which only requires access to an optimization oracle over the policy class. Their results, however, remain restricted to i.i.d. contexts and losses. An alternative line of work has been initiated by Auer (2002); Chu et al. (2011), 1); Abbasi Yadkori et al. (2011), who studied the special case of i..dd linear loss functions with changing decision sets. The case of i.i.d. contexts and adversarial linear losses has first been studied by Neu and Olkhovskaya (2020).
Improvements of worst-case guarantees of order vT to first-order bounds scaling with /Lg have been known for a variety of bandit settings since the works of Stoltz (2005); Allenberg al. (2006), and Neu (2015). Regarding contextual bandits, the COLT 2017 open problem of Agarwal et al. (2017) asks for efficient algorithms that achieve first-order bounds for large. but finite, policy classes, either when both contexts and losses are i.i.d. or when both are fully adversarial. First to answer the open problem were Allen-Zhu et al. (2018), who obtained an optimal first-order regret guarantee for adversarial losses and contexts, but with an algorithm that is inefficient for large policy classes. Foster and Krishnamurthy (2021) provide the first efficient algorithm for the non-adversarial setting where the loss function is fixed over time and one has access to an oracle that can solve various optimization tasks over the policy class. We improve on these works in terms of the computational efficiency of our algorithm and by allowing the loss function to vary adversarially over time, although we do rely on the extra assumption that the loss functions are linear.
Another relevant framework is the adversarial linear bandit setting (without contexts), where there also exist adaptive results (Bubeck et al., 2019; Lee et al., 2020; Ito et al., 2020). While conceptually related, an important distinction is that the linear bandit setting assumes a fixed decision set, whereas reducing the linear contextual bandit problem to linear bandit problem requires the use of decision sets that change as a function of the contexts.
Main Contributions. We consider a K K-armed linear contextual bandit problem with di d-dimensional contexts over 7 rounds. The contexts are assumed to be drawn i.i.d., but the linear loss functions mapping contexts to losses for the arms are chosen by an adaptive adversary. The aim of the learner is to minimize their regret, which is the gap between the expected cumulative loss of the learner and the expected cumulative loss of the best fixed policy x.j chosen in full knowledge of the sequence of losses. In this setting, Th. is known to be linear classifier, i.e. it chooses the arm with smallest predicted loss, where the predictions are fixed linear functions of the context (see Section 2). The goal is therefore to compete with all linear classifiers. We first obtain the following second-order bound on the expected regret
RI = ((KKVV)))
where Vr is defined in (5) as measure of the cumulative second moments of the losses for the arms played by the algorithm. Following Ito et al. (2020), we allow these moments to centered around optimistic estimates that can further improve the bound when available or can simply be set to zero when they are not. We further obtain a first order bound of the form
(T( = Ö VdL
(2)
The second-order bound is obtained using truncated version of the continuous exponential weights algorithm over the probability simplex, similar to the algorithm for linear non-contextual bandits of Ito et al. (2020), and the first-order bound may be obtained as a corollary. As discussed in Section 3.3, the computational complexity of this method is dominated by two steps that together require Ö(K5)= (d)))o(1)) per round for approximation up to precision e > O, which is computationally feasible for moderate K and e. Both results are not strict improvements on the worst-case rate of Ō(VKdT) by Neu and Olkhovskaya (2020): first, they have a slightly worse dependence on K. We consider this price worth paying for the first adaptive bounds in this setting. Second, they require the extra
2

---

assumption that the distribution of the contexts is log log-concave. Although log concavity is weaker than assuming the contexts follow e-g. (truncated) Gaussian distributions, we conjecture that it may not be necessary to obtain a computationally efficient algorithm. This conjecture is based on the observation that there exists fact an easy way to obtain least the first-order bound (2) without the log-concaving assumption, but with an algorithm that has no hope of being efficiently implemented. As described in Section 2.2, this is possible by running the MYGA algorithm (Allen-Zhh et al., 2018) 8) on O ( )kd experts that cover the set of linear classifiers to sufficient precision. The run-time of this approach is prohibitive, because it scales linearly with the number of experts, which is a large polynomial in T.
Techniques. The LinExp3 method of Neu and Olkhovskaya (2020) is based on adaptation of the classic Exp3 algorithm for regular multi-armed bandits (Auer et al., 2002a). A natural approach would therefore be to replace the Exp3 component in LinExp3 by method with first-order guarantees for the multi-armed bandit setting, but, as discussed in Section D, this leads to difficulties controlling the variance. Instead of building Exp3, therefore follow the perhaps surprising approach of building our algorithm on continuous exponential weights over the probability simplex (van der Hoeven al., 2018) In particular, approach is based combination of the recently proposed techniques of Ito et al. (2020) for linear bandits with tools designed by Neu and Olkhovskaya (2020) deal with the contextual case.
Outline. The rest of the paper is organized as follows. After describing the setting in the next section, we state formal version of the simple first-order bound that can be obtained using the MYGA algorithm (Theorem 2.1). This is followed by Section 3, which states our main results corresponding to the regret bounds in Equations and 2. Section 4 then gives high-level overview of the proofs, with pointers provided to the details in the appendix. Finally, Section 5 concludes with discussion.
Preliminaries
Notation Let A (w E RK [w) 2 0,..., wK 2 0, Exn Wa = 1} denote the (K 1)- dimensional probability simplex. For any positive semi-definite matrix M Rdxd ||l]|ar
V Mu denotes the corresponding Mahalanobis norm, and for any positive integer we abbreviate [n] .n..
2.1 Setting
We consider the setting of (Neu and Olkhovskaya, 2020), in which there is an interaction between learner and an unknown environment. This interaction proceeds in rounds indexed by & [T], such that for each t:
1. The environment commits to [K] parameter vectors Or,,,..., Oc, E Rd without revealing any to the learner.
2. A context vector X, Rd is drawn i.i.d. from some fixed distribution D according
X, ~ DD and revealed to the learner.
3. The learner commits an action At E [K], and incurs the loss (X,,, Ar), where ((X, a) (X, O,.)).
The environment is allowed to randomize its choices of 6.a. These must be independent from the context X, in round f, but they may depend on previous contexts X, and actions A, for < t.
We write Ne Ta(a)Xi, ) for the policy of the learner in round conditional observing context X.. that A, ~ Te (Xx), and we use the following notation for the expected cumulative losses of the algorithm and policy æ,, respectively:
T Σ
T Σ (X,, x(x))
LT E
(x,, Ar)
LI = E
3

---

Let II be the set of all all stationary deterministic policies т. IR + [K], we define the optimal policy I as π² arg min LT. Then the learner's goal compete with policy π², measured by the expected regret:
T Σ
R T.p
E
0r,, 0e.r -
where the expectation is taken over each X2 ~ D. and any randomness applied by the learner or environment in their respective choices. Using the linearity of the loss functions it can be shown that the optimal policy is always a linear classifier (Neu and Olkhovskaya, 2020):
T (x)
arg min
We may therefore restrict attention to competing with policies of the form
T arg min (a,, Sa)
(B E RR Kxd).
(3)
For deriving our technical results, will be useful define the filtration Fi o((X,, Ag s t)). and the notations E, [:] = E Fi-1] and P. [ = IP F(-1)-
Assumptions Following Neu and Olkhovskaya (2020), assume that ||x,|| S o, ||0 R
and (1x a) E [-1, almost surely. addition, the covariance matrix E - X X of the context
distribution is assumed to be positive definite, with smallest eigenvalue Amin (Σ) 0.
2.2 An Inefficient Algorithm
first order bound for our problem can obtained by instantiating the MYGA algorithm of Allen- Zhu et al. (2018) for set of O( T )Kd experts that cover the parameter space of policies of the (<z))
form (3), which guaranteed to contain the optimal policy mं.
Theorem 2.1. Suppose that 0 S Xi) S 1 almost surely for all a E [K]. Then, by instantiating Kd experts, it obtains the following first-order bound for the adversarial linear MYGA with O (T<=a)& contextual bandit problem:
RT /dL logT
dLi
K dlogg)
(4)
Although this provides a quick way to see that first-order bounds are possible, the resulting algorithm completely impractical, because its run-time proportional to the number of experts, which grows as large polynomial in T. The proof, including a more detailed description of the experts, can be found in Appendix A.
3 First- and Second-Order Bounds
In this section we present an algorithm using a novel adaptation of method developed for the adversarial linear bandit to be suitable for use in the adversarial linear contextual bandit setting. The method proposed is based on form of continuous exponential weights that has been shown to lead first-order bound in the former (Ito al., 2020). The algorithm allows for optimistic estimates m4,a E Rdd for the environment's s choices 0r... which can always be set to 0 when they are not available. We show two types of guarantees. First, Theorem 3.1, we obtain second-order regret bound in terms of the cumulative squared error of the estimates m.,a:
T (X,, - -M,,,),,
VT = E
Σ
(5)
Taking Mi,a = 0, this provides a second-order regret bound in terms of the squared losses. Al- ternatively, My,a may be estimated using an online regression algorithm, as described by Ito et al. (2020). As our second result, we show in Theorem 3.2 that a first-order bound can be derived for the same algorithm with a different choice of hyperparameters and the assumption that the losses are non-negative.

---

Algorithm CONTEXTEW
Parameters: 7> 0, 2 ... 2 mT > 0, Mı,..... MT
For t I....,T:
1. Observe X,.
2. Repeat:
Pick Qi from the distribution defined in (8), until
K
Σ
1Q 12 s dky
(6)
a=1
where Σt,a is defined in (9).
3. Set Q: = Qs equal to the last sample of Qt, which caused the loop to exit, and choose an arm according to A, Qt-
4. Observe the loss (X,, A,) and estimate o., for all according to (12).
3.1 Algorithm Description
Our full algorithm is shown in Algorithm 1. As it is adaptation of continuous exponential weights for the contextual bandits setting, we refer to it as CONTEXTEW. It runs a two-stage sampling procedure: after observing context X,, the first stage of the algorithm samples random policy Q A and then the second stage consists of drawing an arm At randomly from Qt. The distribution of Q, constructed as follows: first we sample different policy Q: from the exponential weights distribution over the probability simplex with density proportional to
We Xi) exp(- Tr Ta (X,,
Σ
0s.a + mz,a)):
where Ma is function that is measurable with respect to F The sum Et=1 0a.)) estimates the cumulative loss that the policy q would have incurred Ex Ya
it had been played in all previous rounds. It relics on estimates 0z.0 of the loss vectors 0s.a. which will be defined below, and time-varying learning rate 1) O, which is hyperparameter of the algorithm. The normalized density function corresponding to the weights in (7) is:
We ( Xt)
(r X.)
JAN we (g)xx)
Following Ito et al. (2020), we then introduce a rejection sampling step (6) to reduce the variance, which is based the following covariance matrices Ex,a corresponding Q::
Σ,, E. [Q [xX,].
so that Q. ends up being sampled according to the following truncated exponential weights density:
(g)x)) X.)
[K 11 X.1E, S dk?2)
(10)
P.
K
1e S d
with truncation level hyperparameter ạ >> O. We will show that all Dt,a are invertible, their analogues in which Q; replaced by Qc:
Σ E. x
(11)
It remains specify our estimators for or,.. which are defined follows:
ma,)) 0ro- Mi,a + Q.o ((Xe, (Xe, ( (A. a}.
(12)
5

---

These estimates can be shown to be unbiased:
m2, + Le ( QraXix11144 (A: (A: =a] (Or,a - mmra)
Mi,a + Ey (ixx (0r,a mea) = 01.a.
3.2 Results
We instantiate CONTEXTEW with adaptive learning rates T/, For our second-order result, these are defined in terms of the empirical counterpart V₁: V2 = =EE. (Xs; Ss,A, - -ssA.) and we
abbreviate G. -8V V (2T + 144 T + 176 T. Then we set
(100dK>² + d + Gr-1))
(13)
This leads the following second-order bound:
Theorem 3.1 SSecond-Orders Suppose 'D has log-concave density. Then, for = 4log(10dKT), Ne as in (13) and any Fi-1-measurabe estimates my the expected regret of CONTEXTEW most RT = /aVr).
To tune тソ adaptively for our first-order bound, we define it using the algorithm's empirical cumulative loss I, = E.= ((x,, As), which acts self-confident empirical estimate of L7- We further abbreviate
8//22., 2I, In + 40hn2 In H. = 8/ 82=88/7
(14)
and then set
(100dy² + dK (I,- +1 H,-1) 1122
(15)
This leads the following first-order bound:
Theorem 3.2 (First-Order). Suppose that 'D has a log-concave density and that 0 S l, (a X.) <
almost surely for all a E [K). Then, for 7 = 4 (o0(K))))), q as in (15) and m, = 0, the expected
regret of CONTEXTEW is at most Rr = Ö(K /dLT).
3.3
Computational Efficiency
The two computational bottlenecks in the algorithm are the cost of sampling from the output distribu- tion (g Xx) and computation of the covariance matrices Mr,a in each round.
Due to the log-linearity of our method, there exists several practical methods of sampling. As mentioned in Ito et al. (2020), one can employ the methods of Lovász and Vempala (2007), which was shown in Lovász and Vempala (2006) to enjoy bound of O K (lo(lll (where is bound on the total variation distance between the output distribution and the target), but this still requires knowledge of a density dominating the target distribution on all but set with total starting mass S c/2. In Narayanan and Rakhlin (2017), method is developed for general log-concave distributions which, specialized to log-linear distributions (and without additional assumptions the initial distribution) yields an O(K3 + log(1/c)) method when the geometry admits v-self concordant barrier. Since there always exists K K-self-concordant barrier for K- Kddimensional convex body, and thus the running time this method for our problem is O(K' 3 + log(')) up to precision e 7
+ for some 3 O. As referred to in Ito et al. (2020), the covariance matrix Lt, is computable in ((d/e))(1) sampling steps drawing upon the results of Lovász and Vempala (2007).
Analysis
In this section we provide the analysis of CONTEXTEW from which Theorems 3.1 and 3.2 fol- low. Throughout the analysis, we will extensively using the following property of log-concave distributions:
Lemma 4.1. If x follows a log- log-concave distribution over Id and E [xx"] < I, we have, for any > 0:
[110112 2 do? S dexp(1 - a).
(16)

---

This result was proven in Lemma I in Ito et al. (2020), and also follows from Lemma 5.7 in Lovász and Vempala (2007).
First, we need to introduce some notation which will be useful for the reduction to the linear bandit setting and for the accompanying proofs. We denote ze za(g, x) qat and z(g,z) (z1 [g.z), z (g, x))". We also define Σn = diagag[R] (Na.a) as a block diagonal arrangement of the covariance matrices per arm. Using this notation, the distribution of the sampling algorithm (10) may be rewritten
Pe(gla)1 (1<(q,))) = dk
pe(g/=)
(17)
Pe [1 2 S dk
Let (z) ~ ()) Q+(x) ~ (glaa)) and (x) = z (1) x), Zz(x) = =(Q((z). (z)
2( (z), (xx) And we denote the aggregated loss parameter 0g (01...., 00k] and its estimate
0. = (0),-. ...,0O))) Then we can express the regret as follows:
(x(x)))77xxx,,00 (x(x)),))
RT E
E Exx, A.) - (x,,,,='(( (xxi)
E
Σ
(18)
The crucial observation is that the log-concavity of the distribution of Zz(X,) follows from that of the distribution of X;:
Lemma 4.2. Suppose z(q. x) = E. 909(x, a) for p(x,((x))))) = (ÖT....,zI! .T....) such that æ is on the da 'th co-ordinate and (xx) ~ Po(-(zr) for p)(- defined in (8). If (x and px(-) is log- log-concave and Z(x) = x(Qu(z), I), then (X) also follows a log-concave distribution.
The proof of this result is a rather straightforward computation of the density of (x())) and can be found in Appendix C. To proceed, we write regret as a sum of two terms
T
T
R2 = E
-
+ E
Σ
(z - (000)--((Xx) (x(X),,)))
(19)
L(=1
(=11
Having shown that (X, is log- concave, and since the log-concavity is preserved under linear transformations, for x (X,) we can see that E [uv"] I, and thus by Lemma 4.1 it immediately follows that the probability that (6) is not satisfied is small for proposed choice of 7 loog(1 (10dKT):
1
P. ||,(X,)) > dk < dK exp(1 7) S 3dK exp(->) -
67
Using this observation, we show that the first term of (19) is just ((1), which is formally proved in Lemma C.2 in the appendix.
To control the second term of the regret decomposition (19), consider the reduction of the contextual bandit problem to a combination of auxiliary online learning problems that are defined separately for each context, proposed in Neu and Olkhovskaya (2020), Lemma 3. More details and full proof can be found in Appendix C.
Lemma 4.3. Let x² be any fixed stochastic policy and let Xo 'D be a sample from the context distribution independent from Fr. Suppose that p. E Fi-1, such that pe ([(xx) ) is a probability density with respect to Lebesgue measure with support A and let Qx(x) pe(- (-12z) Then,
Eg [X.) z*(,),,,., - = E. (2x(X))) - 2" (Xo). (xo). 0.)]
(20)
To see why this would be useful further in the proof. we interpret the right- hand side of (20) as follows. Consider the online learning problem for a fixed æ with the decision set to be A and
losses le(z, 9) = (z(g, x). 02) and consider running version of contextual bandit problem with a fixed context x, such that the probability of an action defined as in Equation 8, so (((g)) xc
exp (-Th ΣK Qu Ei=10s.))) Then, the regret for the fixed against x (xx) can be written as:
RT(x)) = Σ (2(01)) (=((((()) (1( =<>==<=),,))))>>'>'))<<))) (z),
7

---

Then it easy see that the right-hand side of (20) is equal to E (Xo) Thus, we first show
bound on (x) that holds almost surely for any x and then take an expectation with respect to Xo- We control the regret Ry (2r) by following the general schema of the optimistic mirror descent
analysis developed in (Rakhlin and Sridharan, 2013; Ito et al., 2020). With this analysis, we get the following bound for any X:
Lemma 4.4. Assume that 7h+1 S Tt for all t, let qo be a uniform distribution over [K] and (v) = exp(y) - y - 1. Then, the regret [x( of CONTEXTEW almost surely satisfies
1 T RT(x)= S
=(00 x" (x), σ.) + K log
VT
[Q((a))p((1z)) ( (=m
(21)
for (v) = exp(v) 1.
We place the derivation of the this bound in the appendix. The crucial ingredient is to show that the square of the estimated loss can be bounded by the square the true loss. Using the definition of lz. denoting Var, tr
_ Zo (X)) Zx.
we get
Eg (-m (Z)x))( (x())),, 0, ((m))) ) = E, nn (l((A), - X)m,, Vanl Vari
(22)
As additional corollary of the concentration result for log-concave random variables, show the following relation between matrices M, and Σn:
E E4
(23)
which we prove in Lemma C.2 in the appendix. Then we can show that, almost surely:
Ex, [Var,]
Ex,
(x,
= tr
=3 ((x)) (x,, - (x, S dk?
(24)
where the first inequality follows from (23) and the second inequality is immediate from (23) and the fact that for symmetric positive definite matrices A m B follows from B-! A-1. The last inequality follows from (6) in the CONTEXTEW. So, from (22) and (35), we get
E, (- (x(x)))...mm))) )²
< 2 [2 (G(A,, -M))))),A))mmM) Xime,a)²
which, as we stated above, is the key step to prove Theorem 3.
First-order regret bound To prove result of Theorem 3.2, we show that the bound in the Theo- rem 3.1 can instantiated obtain first-order regret bound with different choice of the learning rate Mi- Going along the same lines with regard to the concentration of T, for V., by setting m. and noticing that then Vr & Lop we get
RT < 21
Σ mll(A, x,)
+ +V(K <
Since Ry = L, Li by solving the quadratic inequality with respect to Li,, we get that Ly S Li + Ö(K Vd), yiclding the final bound.

---

5 Discussion
In conclusion, by applying the approach of (Ito et al., 2020) we have constructed the first scheme achieving Ô (K Vdl.,) regret with a runtime of O ((K + log?") gx), where gx: is the time taken to construct the covariance matrix per round a potentially large polynomial improvement over the O (TK2) runtime of MYGA. The application of linear bandit algorithms to the contextual bandit the best of our knowledge, a novel approach. In doing so we've found
problem constitutes, number of positive aspects, including efficiency, but also the direct applicability of other properties enjoyed by the algorithm such second order bounds (Ito et al., 2020).
Our approach is based on reducing the linear contextual bandit problem to a linear bandit problem. as opposed to multi- bandit problem as in (Neu and Olkhovskaya, 2020). While the specifics of this reduction heavily relied on the joint log-concavity of the context distributions and the exponential- weights posterior over the simplex of actions, we wonder if such approaches can be successfully applied to achieve other types of improvements for linear contextual bandits. In particular, it is curious to what extent other recent advances in the linear bandit problem can be translated to the linear contextual bandit setting. Note that, while the truncation step in Algorithm I has an insignificant computational cost as the condition is satisfied with probability O(1 1/TT), it can be removed by paying a log(1/ Amin (E)) multiplicative term in the regret by implementing additional exploration with probability 1/T. It is natural ask whether or not approaches based on other instantiations of online mirror descent would also yield first-order bounds, and possibly improve the dependence on K. The answer is not obvious: for an example of how naive application of an instantiation of FTRL fails to achieve a first-order bound, see Appendix D.
A relevant question pertains whether or not such an application of algorithms for linear bandits is necessary at all, but standard approaches such as direct adaptation of Exp3, and first-order adaptations thereof such as GREEN Allenberg et al. (2006) do not seem to give the desired In addition, thresholding the worst performing arms inevitably biases the loss estimator due to undersampling of those arms for which the threshold has been applied, and the resulting additional bias term picked up in the regret scales with 1/Amin (Lt,a), which may be arbitrarily large. Another standard approach of finding an optimistic estimator yielded no fruit during the course of this study due to the lack of the existence of such an estimator without saving all previous losses explicitly.
Our algorithm achieves the regret bound OKK vdVr), while the worst case guarantee of LINEXP3 of Neu and Olkhovskaya (2020) is O OVdKTT). This discrepancy is not surprising as the Algorithm 1 of Ito et al. (2020) scales as (T) (n being the dimension of the action space for the linear bandit), which arises from the deployment of continuous exponential weights. MYGA achieves the same O K / /dL.)) bound due to the number of experts needed to cover the joint set of additive loss parameters. It is worth here emphasising that no known algorithm achieves better dependence on K than O(K OK /dL.,) for the linear adversarial contextual bandit problem. Meanwhile, if the linear bandit is played on the n-simplex, an improvement to VnT is possible. For further discussion of this point, see Section 28.5 of Lattimore and Szepesvári (2020). It is thus still unclear whether not the extra factor of V VK is necessary if one aims for first-order bound.
An additional point that while the MYGA algorithm Allen-Zhu al. (2018) allows for adversarially chosen contexts, the analysis of MYGA for our setting relies heavily on the assumption that contexts are drawn i.i.d. at each iteration. A natural question is then whether or not a similar result is achievable in the adversarial context case. It is known that achieving sub-linear regret is not possible even for full-information online learning of one-dimensional threshold classifiers when both contexts and losses are adversarial (Ben-David et al., 2009; Syrgkanis et al., 2016), which renders sub-linear regret similarly impossible to guarantee for the even harder setting that we consider in this paper. However, we do conjecture that we could overcome the assumption that the distribution is known that can sample from it by employing a more claborate algorithm to estimate the distribution from the data. Indeed, it is not obvious if the distributional assumption of a lower bound to the covariance matrix eigenvalues is entirely necessary, since the regret does not depend on this.
Lastly, it would be an interesting challenge to see if brobbbrobability regret bound could be obtained in the form stated in the COLT 2017 open problem Agarwal et al. (2017) for this setting, but since a high-prod coab-prbbbbility OVVT) has not yet been proved for the problem here considered, the latter may be more worthy of focus in the short term.

---

6
Acknowledgments
Tim van Erven and Jack Mayo were supported by the Netherlands Organization for Scientific Research (NWO) under grant number VI. Vidi. 192.095. Gergely Neu was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 950180). Chen- Yu Wei would like to acknowledge the support from Research Fellowship.
References
Abbasi-Yaue Yadkori, Y., Pal, D., and Szepesvári, Cs. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems (NIPS).
Agarwal, A., Bird, S., Cozowicz, M., Hoang, L.,, Langford, J., Lee, S., J., Melamed, D., Oshri, G., Ribas, O., Sen, S., and Slivkins, A. (2016). Making contextual decisions with low technical debt.
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L.,, and Schapire, R. (2014). Taming the monster: A fast and simple algorithm for contextual bandits. In Xing, E. P. and Jebara. T., editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1638-1646, Bejing, China. PMLR.
Agarwal, A., Krishnamurthy, A., Langford, J., Luo, H., and Schapire, R. E. (2017). Open problem: First-order regret bounds for contextual bandits. In Kale, S. and Shamir, O., editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 4-7. PMLR.
Allen-Zhu, Z., Bubeck, S., and Li, Y. (2018). Make the minority great again: First-order regret bound for contextual bandits. In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 186-194. PMLR.
Allenberg, C., Auer, P., Györfi, L., and Ottuesák, G. (2006). Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In Balcázar, L., Long, P. M., and Stephan, F., editors, Algorithmic Learning Theory, pages 2292243, Berlin, Heidelberg. Springer Berlin Heidelberg.
Auer, P. (2002). Using confidence bounds for exploitation-exploratio trade-offs. Journal of Machine Learning Research, 3:397 422.
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002a). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002b). The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(())48-71
Bartlett, P., Dani, V., Hayes, T., Kakade, S., Rakhlin, A., and Tewari, A. (2008). High-probability regret bounds for bandit online linear optimization. pages 335-342.
Ben-David, S., Pál, D., and Shalev-Shwartz, S. (2009). Agnostic online learning.
Beygelzimer, A., Langford, J., Li, L., Reyzin, L.. and Schapire, R. (2011). Contextual bandit algorithmss with supervised learning guarantees. In Gordon, G., Dunson, D.,, and Dudík, M., editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 19-26, Fort Lauderdale, FL, USA. PMLR.
Bubeck, S., Li, Y., Luo, H., and Wei, C.-Y. (2019). Improved path-length regret bounds for bandits. In Beygelzimer, A. and Hsu, D., editors, Proceedings of the Thirty-Sconnd Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 008-528.77 PMLR.
Chu, W. Li, L., Reyzin, L.,, and Schapire, R. (2011). Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214,
10

---

Foster, D. J. and Krishnamurthy, A. (2021). Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. volume 23, page 18907 18919.
Freedman, D. A. (1975). On Tail Probabilities for Martingales. The Annals of Probability, 3(1):100- 118.
Ito, S., Hirahara, S., Soma, T., and Yoshida, Y. (2020). Tight first- and second-order regret bounds for adversarial linear bandits. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 0028-2038. Curran Associates, Inc.
Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
Lee, C.-W,, Luo, H., Wei, C.-Y.. and Zhang, M. (2020). Bias no more:
high-probability data- dependent regret bounds for adversarial bandits and mdps. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 15522-15533, Curran Associates, Inc.
Li, L., Chu, W., Langford.. J., and Schapire, R. E. (2010). A contextual contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference World wide web, pages 661-670. ACM.
Lovász, L. and Vempala, S. (2006). Hit-and-run from a comer. SIAM Journal on Computing, 35(4))985-1005.
Lovász, and Vempala, S. (2007). The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307-335
Narayanan, H. and Rakhlin, A. (2017). Efficient sampling from time-varying log-concave distribu- tions. Journal of Machine Learning Research, 18(112):1-29.
Neu, G. (2015). First-order regret bounds for combinatorial semi-bandits. Conference on Learning Theory, pages 1375. PMLR.
Neu, G. and Olkhovskaya, J. (2020). Efficient and robust algorithms for adversarial linear contextual bandits. In Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020), pages 3049-3068.
Rakhlin, and Sridharan, K. (2013). Optimization, learning, and games with predictable sequences. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, NIPS' 13, page 3066-3074, Red Hook. NY, USA. Curran Associates Inc
Stoltz, G. (2005). Incomplete information and internal regret in prediction of individual sequences. PhD thesis, Université Paris Sud-Paris XI.
Syrgkanis, V., Krishnamurthy, A., and Schapire, R. (2016). Efficient algorithms for adversarial contextual learning. In Balcan, M. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2159-2168, New York, New York, USA. PMLR.
Tewari, A. and Murphy, S. A. (2017). From ads to interventions: Contextual bandits in mobile health. In Mobile Health Sensors, Analytic Methods, and Applications.
van der Hoeven, D., van Erven, T., and Kotlowski, W. (2018). The many faces of exponential weights in online learning. In Conference On Learning Theory, pages 2067-2092
11

---

A First-order Bound by Reduction to MYGA
Proof. The MYGA algorithm of Allen-Zhu et al. (2018) competes with class of experts E, where each expert E E provides a stochastic prediction & E Ax in each round t. It provides the following expected regret bound with respect the best expert:
(V Klog( E) + +TL + Klog(LE) + 27)
R -0
(25)
Losses for the arms be adversarial, and assumed take values in [0, 1].
We will instantiate the experts to cover the parameter space {,3 E Ix maxa 1| < RT) of potentially optimal parameters for deterministic policies of the form (3), which we know must contain the optimal policy z with corresponding parameters = E 0z]- The covering number for ball of radius RT at precision
between [ and 3RT) so by taking the Cartesian
product of this covering with itself K times we can cover all [3 with
(ITT)
E (3RT)
points 8¹ ....... 3 Fl Let / E {(8...... 3 be the closest point in the covering to the optimal
parameters 8 Then its expected approximation error can be upper bounded as follows:
T
T
X (ong())))) - (xx
E
Xo. Olngg(x)))
- (o.00, (X0))
1=1
12
Xux 8"
(X()
Xus 8t (T (No)
E
Xu, B (xg(Xo)
Xu, 3 P (Xo)
E
min Xo. 3a
90 Xos Tao (Xo)
06
E
Xo B Baa- (mo)
X0:1 (ma)
E
{ (oo, B (mo)
Xo,
3 x (mr)
20e
2nc.
Adding this to (25), instantiated with |E| proof.
<
(RT Kd
and choosing
dk² completes the
B Auxiliary lemmas
To ensure that step 2 in CONTEXTEW is defined correctly, we show that the matrix E, is full rank: Lemma B.1. Let the distribution of X, be such that Amin (E [X, > O. Then, we can show
Amin ( (E,,a) >
(26)
for any a E [K], and consequently
Amin EE))
(27)
Proof. To show that Σr, is full rank, it suffices to show that there is no v E Rd such that of E
0. Suppose, to the contrary, that such a does exist. Then 0 = E, (X.)x,XX E, [Q (x))) which implies that Qe, X, 0 almost surely. Since Qr.e almost surely, follows that in fact v" X, = almost surely and therefore = E, [(t X,) = v E,, [X,X]] v. But this contradicts our assumption that Amin (E, [X,X]) 0.
We will use simple corollary of Freedman's inequality Freedman (1975) that was introduced in Lemma 2 in Bartlett al. (2008):
Lemma B.2. Let Y1 ...... Y, be a martingale difference sequence with respect to filtration Fi C Fe such that [Y, [F&] = O. Suppose that Y, S b holds almost surely. Then with probability
at least - 8 we have El= Y, < 2 max Σ E b/ (on1///nn())))) (n(5/)).
12

---

In our analysis, we will use some results from Ito et al. (2020). We will make use of the following concentration property of log-coneave distributions, Lemma from Ito al. (2020): Lemma B.3. If follows tog-concave distribution p over IR and Bywp lyv'l have
P
IIvl22 2 da²) I dexp(1- aa))
for arbitrary 2 O.
The lemma presented below introduces property that will be instrumental in analyzing the variance of loss estimates, presented as Lemma in Ito et al. (2020): Lemma B.4. If follows a log- log-concave distribution over R, and if [ - 1/100, we have
(-
1
E [((())] S E [v²] + 30exp
S 2 [v-] where vxxx) exp(x) - x 1.
V /
C Proof of Theorem 3.1
The proof of Theorem 3.1 proceeds in a sequence of lemmas. First, we need to show that the distribution of Z,(X, ) is log-concave for all t [2], and after we follow the analysis of Algorithm of Ito et al. (2020). bounding both components of (19) taking into account the required alterations to incorporate contextual structure
Lemma C.1. Suppose 2(q,2) = =E qap((z a) for p(z, a) = =OT ....) such that x is the da 'hh co-ordinate and Q(x) ~ p([[2)( ((-2() log- log-concave. X ~ px(x) and px(.) is log-concave
IT.
and (x)) (1) x), then (X) also follows log-concave distribution.
Proof. Assume that |x'|| > 0 for all é E [d]. Set (21,..., 2 1, x) = o)), where h BdK + Rak and 2 = (..., 2/. )" for each i E {l..... K 1}. Thus 2 = (4 x²) = q. (xx)) and (x(x)) = x. The Jacobian h
OK
can be expressed as the block matrix
Ar T' [(h ((11()) Oax(K-1) Idaxd]
where Ar (R(K-I)x(K is diagonal with (Ax)a = + and T Z.n E RR(K-)xxd with (Tz.r)is
Since J (z1...., is upper-triangular, (et (2k_,,,)))2. =
( +
K-1
The joint distribution of Z; and X can thus be written
d
PZ 2x 1.X (x211)))) -QQ.x (2
(2,.,,,,,, ..-,.,,..--111))
with the joint distribution between Q and X of the form
PQ,x (2),..,,2x11.... =
px (x)
Spece "/EK- d. 1) dd
where (1/22, x, p)); = - 1 (1, + (1 -K-1 # p(I, K)' has been defined for read-
ability. We can reabsorb the factor (II 1 x² the denominator to rewrite the normalization constant as a in terms random variable Z(x), and so
8-1
PZ..... Zg (21, , 2k-
px (a). JvEZ(a)e (VM 1)
(x(x).
Define a new function 9 Bdxk - RdxK such that y g(21,...,22% 2K-,,, (2..... ...,, 21,, where for i E [1.K 1]. g.(2....., 2K-1,, and
13

---

(e(21...,,,K-.... (..., (1 (1- - K- 20 x² ......). Then for i E {I...., K 13, 9i (1)
and 9x (v) = -oom ya- The determinant (g Jet = 1, so
py( pZr, 2x 2 (9 2x.,,,x-11 (v)) (v)) e (
K Σ
SWEY(() e =n 1) dy
Px
ya
Since both px and
Syer n/y dy are both log-concave, the lemma follows.
Having shown the log- concaviiy of ((x,), we may safely proceed.
We state the analog of Lemma 4 in Ito et al. (2020) adapted to our setting, leading to a bound on the first term of (19) as well as providing useful relation between De and Σ,, Lemma C.2.
B (2(()))
-.00)) S 272
(28)
and we have
4
Ex Eイ 3 E,
(29)
4
Proof. From definition of pr, for any
X, 0 E θ, we have
E. { (Z(()))))) 0)
Pe [12((x)) S <dkg / / (z(a,)),)) 1) x s dkg pe pc(clz)p(z)dadg
8 / (z(g,0), 0) 1 [|=(0,,0)1; S sdkz² pa polglo)p(a)ddd
1
E, ((z,()))) 01] SSA / (z(q, x), 0) 1 [|a(q, > dk p(lal))p())dddd))
1-8
where 8 = IP, [12x(X))) > dk>2 Plugging this into the lh..s of (28) yields
(Z((X)) Zx(x)), 81)1
E,
1
SE. (X,) 0,11+ SAx / (z(g,2), 1 {1a(0,,)) > dk po (o(g)r)p(z)dddd
1-8
1
(++ / / 1 (1le(,,=)1E, > dk p((g)=)p(=)dxdq) 8-8
28
<
1-8
Since the distribution of (X.) is log-coneave (Lemma C. we can apply Lemma I of Ito et al. (2020) to r Σ, 1/2 Z, (Xt). The assumptions of Lemma of Ito et al. (2020) hold since we have E [x=] and since log-concavity is preserved under linear maps. Using Lemma of Ito et al. (2020), we have
8 = P. [1x( > dk?? < dK exp(1 -7) s 3dK exp( (p) < 67
1
where the last inequality follows from 2 4 log(1d))T), which obtains (28). We proceed to showing (29). For any dBd we have
EEy= = E (w 2, (x.))²
= E, Z(x,)) (1ZZ(x))11 S sdkr]] < Es [10 (xx))
{
1
1 1-8 Eyy-
14

---

Since this holds for all y Ra and have
1 S 3 the second inequality in (29) holds. Furthermore, we
I-8
D'y 3 y'Eny= = En [(00 (xx))) - T E. (v'z ( [1,x),,) E
1
s E. (w' (x.)) { (122((X))1 >
s y'EE, || [x, 1 (12)(x))3, dk
(30)
where the last inequality follows from Cauchy- Schwarz:
(x,z) (1=,",,,,, y.
-
/
y
2
1/2 1
y E,y ||=|ا
2
The right-hand side of (30) can be bounded using Lemma B.3 as follows:
Ex [x,)) [2.((.)) > dk*²))
(n + 1)²dK> [n²dk*² S 12 I (m
==1
(n + ()3 exp(1 -ny)
n=1
2
cxp(3 7) exp(2 + - m7) (dK)??² exeppp - 7)
1
s 2d
5
(31)
4'
Combining (31) and (30) get the first inequality of (29).
Lemma C.3. Let n" be any fixed stochastic policy and let Xo ~ D be a sample from the context distribution independent from Fr. Suppose that p. E Fi-1, such that pel pe(-(z) ) a probability density with respect to Lebesgue measure with support A K and let Qe(x) ~ Pe(-(z)) Then,
E
Σ (2((.(()),,
2 (X)),
E
x(Qr(X))) 2(1 (Xo),, Xo: (Xo),
Proof. For any t, we have
E, ( (Xo) - (xx)). = Er E. [ -xxo)))) 0.) Xo
= E. E (Zx(X)) 2" (Xoo), 0.) Xall E, (Zz( 2 (x).
Then, we prove the almost sure regret bound for any x and then take an expectation over Xo- We further proceed with an adaptation of the analysis of the continuous exponential weights algorithm, which was stated in Ito et al. (2020) as Lemma 16, but we include it here for the clarity. Let (v)) = exp(y) y 1. For any X, we show the following:
Lemma C.4. Assume that M S ne for all i, let go be uniform distribution over [K] and (v) exp(y) y 1-11 1. Then, the regret Rr (x) for any X of CONTEXTEW almost surely satisfies
T 22(9 - x" (x),,x, T.) +
T
K log T
E EQ, (o ( (=)()(())))) -ma))] m1
(x) <
+
T
1T
Proof. Note that we can write (x)
as
T Σ6
((aaralala)) polgla)) (aaan)))(eee (z(() 0.), dg =( =)(T"(x),, (2),
Ro(xx)
0,
t=1
15

---

Define We(x) Sax wo(glz)dq, u1(9/z) exp (-m L. 90 ( (z, E.=1 Baaa)) Ut(x)
(i=10aaa))
SaN urlgko)dg and ve(glz)) - exp (-1++1 En 4a (z; )/=10aa)) Vi(x)) SaN ve(glz)dgg We have
U1(2) = - wi wi(glx) exp (-ne (2(g,0), 8. - -ma) dg do= Wi(x)) / pe(gl0)) exp (-Th 2(q1 (ma)m dq -mm)))))))) mi)))
Ak
-w,(1) / JA pe(glz) (1-m((s(.x0)) mi) + w0 (z(g,z), (e
da.
Taking the logarithm of both sides, we get
(x)) = log(W((x)) + log (allla (1 ?7 (1
+ 1/( sh(-n: ( (=(g,2), 0, (8ammaa)) dg
- log(W((x)) + / pilgto) (-m (2(9, - -mmm + w--n (z)
1)), 0r - -ma) dg.
(32)
where we used the inequality log(1 + x)) S x for > -1
(=-((x)= = 1 wr(glz))
T1e E ya (x, mua) dg Wx(x)) SSa. pr(glz) exp " Σ ga (a, mea)) dg
exp
2 Wi(x) exp " / Ax pe(glx) Σ qa (or, (1,) )
(33)
using Jensen's 's inequality. It holds that
S pc(g/z) Σ qa (2., me,)) dq
log Vi-1(x) n We(x)
Then, we get
Σ/
pelglz) (z(a, 0.) dg
Vi-1(z) U((x)
+ S polglo) (2( m. mi))da)
log
AK
Noting that Vo = Up, we have
1 Vi-1(z)
log
Σ
1
log
Vi-1(z)
log Uo
Ui(x)
7
Ue(x)
Vo
T-1
V((x)
U1(1)
Ur(x)
log
log
log
7h+1
Vo
Uo
Uo
To bound the first term, we use that 7741 I le and an additional application of Jensen's 's inequality:
log
Vi(x)
log
exp
---111
Σ
0., =((r,
7h+1
Vo
7ht1
==1
Me+1 76
1
log
E
exp
-Th
0., 2(Qr,z))
7h+1
1
}
Ue(x)
<
log E
exp
-7
0. z (Q (Q,, x))
T/
log
Un
Set Qr-(2) := ((1 f) (z) + t E AK) ). and denote go as the uniform distribution over K
arms. We then have
UT(x) 2 1
exp -IIT x(g,
0, dg
Qm1(z)
16

---

1 Ax
T
T
exp
- 2((1 - 7) (x)
(x)) + T.9. x),
Σ 0g
dg
r
2 T x Uo(x)
--mr 12((1 - ) (x) + T 90. x),
0,
1=1
where the first inequality constitutes change of variables and the second follows from Jensen's s bound. After rearranging and taking the logarithm, we get
1
Ur(x) log Uo(
1 |
1 20, x), 0,
K log T
<(11 7
(x) +
T
T/T
'/T
K log T (900 x'()),)),0
2( (z) x), Σ
0.
+
nT
Combining everything together, we get
Σ (1s+ AN
T
0: ))
pi(glz) ( (z(g.x).0) 0.) dg =((T(x)),
Σ
8
Σ
nt Jsk. p((gl))((- no (2(1,2),0. (0ammmm) mma) ma))ddo
1
S
1=1
t=1
t=l
K log T
(2(00- x (s), 0.)
T
1pr
From Lemma 4.3 and Lemma 4.4, we get bound the second term of (19):
7x() (x(o)). (1)
E
(X,( - (x))
E
1 wb (-m (x -0:000mmm) -m²)) + T Σ = - x xXo),, Xo), 0.) +
T
K log T 1/r
S E
1]
(34)
We first find a bound on the first term using Lemma B.4. To satisfy the assumptions of Lemma B.4,
we need to show that B, (-m (Z((o)) m.) m.)) 21
Es [(-n (((x)))..m))))
= Ee ni (f((A,, XTmLA. ( (5724110000000000742400000000000
= n [(G(A).))) XTmLA) ir [X," (3:1133312000010000)00
S w 3
E,
[C((A,, X,) - XTmL,,,) 2'1r (5,-5,5,,
n 3
4
E, [((A,,,)) X,) - X7m., Z,
S nE [(G(A, X,) - -X7m,A, Zz(X,, E2,,)(
S ?K
((c(Ac, (,) X.m.A,,
(35)
(36)
100
where the first inequality follows from l, S and (29), the second is immediate from (29) and the fact that for symmetric positive definite matrices A > B follows from B-1 t A The third
17

---

inequality follows from the truncation in the algorithm and the last is immediate from plugging in the definition of T/.- So. by applying Lemma B.4 and (35), we get:
db (-n (z(X))), mi)) = Z (-n -ma)) 2dK (l((AA,
B
1
"7
(37)
For the second term of (34), we simply get from -1 S 4 S 1 and is unbiased:
T
T
200 x² (Xo), 0.)
(g0 - " (Xo), 01) 22 (38)
The expression that we use for the learning rate is the following:
7 (100dK,² d(V +1 G.)))-
where G. 8/22.. InT 144 176 T. We show that with probability at least - ô the following holds for all [Z]]:
V₁ s V, 8V V2 + 721122776)) + 88 88In(T/6)
(39)
Let Yg Eg (l((A,),) Xime,A.? (A,, X.m,,A.)². Then, Y, I almost surely, since L (r(Ar Xt) X/mr,A. 2. Similarly we bound the second moment of Y,, using Jensen's inequality:
E, Y = Eg (E. (l)(A) -X. -X(ma)))))) - (1) - X3 x.,,,..)) 27
s 21E [(((Ac: X7mL,A.) )² +2E, (Lo(Ar, Xi) XIme,A))
S 16E, [l((Ar, X7 X.me.A.)²
By Lemma B.2, the following holds for some 8' (0,
Ve S V + 8 max 2VV2. vlm(1/0) VIn(1/8")
(40)
Note that this inequality can be rearranged as
S V + 8V V, In In(1180)) 72 In
Then, taking a union bound over E [T] and taking = 8 we get that (39) holds for E [T].
Let Ey be event that for all E [1, [1. (39) holds with 8 = 1/T. From (37), (38), and the choice of Tht we get:
T
K log T
RT <
2dK 2
The (A), X,mi,,,)² +2
(41)
1/r
~2
Σ
Th (G((A, 2 2
K log T 1/
+ 2L
Σ The (lo(A,, - 2
+
Vi Vi-1
+ 1
K Klog T N/r
<2/dK>
2Vd 2T +
VV.
(VVi
(VV. V
K log 1/r
-V/dK>
+ 2/dK + 2
VV.
18

---

K log T
S <VdKk> ((VV vV-1) + 2vdK2² +2+
1/7
S <4Vak> +V +2+ K log
1/7
which implies the result of Theorem 3.1. In the equation above, 1/z (100dK + d(V,-1 + G))))= and G² = /V2Vi- In 144 + 17 In line we used that E [1/m)]] S
E [1/m/]] by Jensen's s inequality to show that
1 E [100ddk>
- (100dly ((Vouur(tt((_-++tGGG)) 7/T
Proof of Theorem 3.2 learning rate
As it was done in the proof of Theorem 3.1 we control the deviation of the
n (100dk + d(Lr-1+ +1+ H,)))
where He is as detined in (14). Using Lemma B.2, we show that with probability at least 1 - ô the following holds for all E [T]]
Le S L. + 8V L, ln(1/)) 20 ln + 36 In(27/6)
(42)
D, = E, (X,,, O,, (X,, O A.A.). Then, D, s 2 almost surely and by Jensen's inequality
E. [D = E, (E. [(X,, 0,.A, - (X., 02 (,, < 2E, [(x,, 0n,,,1 + 2E, [1X., 0x.,1)))
< 4E, (e,( Ad)
By Lemma B.2, the following holds for some 8' (0, 1):
L S T. 4 max 2 Tn, vn((1/8)) vin(1/0")
(43)
which can be rearranged as
L < L. + 8V L, In(1/8)) + 20
Then, taking a union bound over t E [T] and taking = we get that (42) holds for all E [T]. Let Er be event that for all t [1, (42) holds with 8 = 1/T.. From (37), (38), the choice of 1/c- my = and since 0 I l S 1, we get:
T
K log T
log T Mpr
RT < E
2d
2
me X.) +2+
2dK 2
(A X,)
+2+
K log T
>T
Σ Melo X.)1 (8r}
+ 2TE
Σ me X,) (8r}
+2+B E
T/T
L, 41-1 1
2VaKKTT +2+
K KlogT
VLn
T/r
(VL, VL--i)(VL + L1-1)
K Klog? T n/r
2VdKk
2vdK +2
VLn
1=1
T
K log T 1/1
< <AVak> 2
(VVi Tu -TT--Vh-i I + 2v +2
S <AVak VTr 2v +2+ K KlogT
1/r
where in the equation above, Ti = (100dK>² + d(L,-1 + 1 H(-1)))-122 and Hi 2 In 4 + Tn. By solving the quadratic equation Lÿ. we obtain the statement of the theorem.
19

---

D On the difference between LINEXP3 and CONTEXTEW
Consider the LINEXP3 algorithm of Neu and Olkhovskaya (2020), that draws actions after observing the context X₁ with probability
We wr(Xe,a) a) Ty (a) = (1-7) En (i a²) +
K
where we (x =exp (-1 E= 1-1 (Xe, 02.0)) and using the estimator
07 - 1 (A: a ST (Xe,0,,)).
where Sr.e By
Since LINEXP3 uses implicit exploration with probability 7- Amin ( (raa) 2 Amin (2) K But then, setting = 0, St.a is still invertible as no actions have
Te (a) O. But still, the smallest eigenvalue Xmin (St.a) can be arbitrary small. Then, the analysis
of the variance term in LINEXP3 looks as:
K (a) (x at)
E
Σ
Te(alXo)((o 0(a))
E (X, A.) (MTG
We can define Var, for LINEXP3 direct analogy to Var, for CONTEXTEW above, which gives (almost surely):
Ex. [Vari] Ex, [tr (oX
Ex, [tr (I = X, X
which can be arbitrary large.
Meanwhile, the smallest eigenvalue Amin (Et,a) can be arbitrary small too. But, as we showed above in the analysis of CONTEXTEW, Var is bounded by dK2² because of the log-concavity of (X,) and step (6) of CONTEXTEW.
20


Reviews:
[{"review_id": "WLdMwS9aOL", "reviewer": "Reviewer_hPEo", "summary": "Addressing to the K-armed linear contextual adaptive adversary bandit problem with d-dimensional contexts over T rounds, using a truncated version of the continuous exponential weights algorithm over the probability simplex, the expected regret about the cumulative second moments of the losses is obtained. and then the first order bound is derived.", "questions": "1 if the distribution for contexts is time-vary or need to be estimated from data, what will the situation be like? \n2 the analysis is all based on the assumption that they can access the distribution for contexts, which is not the case for practical case.  How to handle this difficulty, please give further discussion.", "limitations": "the authors adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "generalizing the results of tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits to First- and Second-Order Bounds for Adversarial Linear Contextual Bandits.", "weaknesses": "1 The results of the paper heavily rely on a combination of the recently proposed techniques of Ito et al. (2020) for linear bandits with tools designed by Neu and Olkhovskaya (2020) to deal with the contextual case.\n2 The conclusion only applies to the scenario of the joint log-concavity of the context distributions and the exponential weights posterior over the simplex of actions, results may not be generalizable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see our general reply for\nanswers to some of the points you raised. Here we only respond to the\nremaining points.\n\nRegarding time-varying distributions: it is common in contextual bandits\nto assume that both the contexts and the losses for the online recommendation arms are i.i.d.\nIt is an important strength of our setting to relax this to allow for\nadversarial (linear) losses for the arms. On the other hand, it is known to be impossible to fully remove the i.i.d.~\nassumption on the contexts: if the contexts are adversarial, then sublinear regret cannot be achieved, since one can map\nthe problem to that of classification with threshold functions at zero margin (see Corollary 6 from Ben-David, \nS., Pál, D., and Shalev-Shwartz, S. (2009). Agnostic online learning. with $\\mu =\nO(\\sqrt{T})$, and the matching lower bounds). The intermediate regime of\ne.g.\\ bounded step-wise divergence between successive context\ndistributions leaves an interesting question worthy of further study,\nbut is likely nontrivial."}, {"review_id": "KZWNE43FHb", "reviewer": "Reviewer_QEEf", "summary": "The authors explore the adversarial linear contextual bandit problem, where  the context is i.i.d. drawn from a known fixed log-concave distribution, and the linear loss functions are adaptive adversaries. \nThey provide first adaptive bounds for this setting, including a first-order bound based on the cumulative loss of the optimal policy and a second-order bound based on the squared losses of the algorithm. These bounds demonstrate improvements over the worst-case bound in scenarios where the environment is  'nice'.", "questions": "Please see the points mentioned in the weaknesses above and provide comments on them.", "limitations": "I don't see any issue on societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors first provide the adaptive bound for adversarial linear contextual bandits, which improves the worst case bound in benign environments. \nThe computational complexity of the algorithm is commendable, particularly in moderate environments. \nThe results and the addressed problem hold substantial significance and are likely to capture the interest of a broad audience in Neurips. \nFurthermore, the authors thoroughly discuss future directions, which have the potential to inspire further research aimed at improved adaptive bounds in linear bandits setting. ", "weaknesses": "I have two primary concerns regarding this work and would like to request the authors to provide additional clarifications. \n\n==Weakness 1==\n\nIt appears that the results and techniques heavily rely on previous work, such as\n\nIto, S., Hirahara, S., Soma, T., and Yoshida, Y. (2020). Tight first- and second-order regret bounds for adversarial linear bandits,\n\nwhich first introduce adaptive bounds for adversarial linear bandits. \nIn comparison to the adversarial linear bandits setting, the authors in this paper consider the case with i.i.d. contexts and introduce some additional assumptions, such as known context distribution and log-concavity. These assumptions may simplify the problem and restrict the practical application of the proposed algorithms. I suggest the authors emphasize the technical contribution of their paper, as this aspect is not clearly highlighted in the \"Techniques\" subsection in the Introduction.\n\n==Weakness 2==\n\nThere does not seem to be any experiments of any type. \nNeither the first-order bound nor the second-order bound demonstrate strict improvements over the worst-case bound.\nIn other words, they may not be tight enough. \nIn this case, I kindly recommend that the authors provide numerical results, which would enable readers to gain a better understanding of the algorithm's behavior.  While numerical evaluations may not significantly enhance the primary theoretical message of the paper, they would improve the overall completeness of the work, considering that linear bandits are closely related to practical applications. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to emphasize that algorithms designed\nfor solving the linear bandit problem cannot be applied to the\ncontextual bandit problem, and thus there is no previous method that\ncould simply yield the result that we claim in this paper. For a comparison with Ito et al., please see our general reply to all\nreviewers.\n\nWhile this work is primarily theoretical, we understand the allure of supporting experiments. However, given our main contribution is theoretical in nature, this paper remains comprehensive even in the absence of experiments well within the standards of this line of work. \n"}, {"review_id": "RAs7PKgFjm", "reviewer": "Reviewer_zjgE", "summary": "The submission considers semi-adversarial contextual bandit setting --- where d-dimensional contexts x_t are drawn iid, where some opponent picks K loss functions that are linear in the contexts at the beginning of each round, before the actual context x_t is drawn, and where he learner picks one of the K loss functions and suffers the corresponding linear loss. This setting was introduced by Neu and Olkhovskaya (COLT 2020), who provided 'zero-order' regret bounds of order \\sqrt{K d T}. The present submission refines the regret bounds into first-order (for non-ngative losses, as usual) and second-order regret bounds, involving respectively the cumulative loss of the best static policy and the expected sum of instantaneous variances of the rewards obtained by the algorithms (and generalizations thereof). This is achieved by considering a continuous version of exponential weights, à la Cover (1991), and by leveraging techniques introduced by Ito, Hirahara, Soma, and Yoshida (Neurips 2020) for such refined first-order and second-order bounds in the setting of non-contextual adversarial linear bandits. \n\nThe key to the results is the reduction (18) of this semi-adversarial contextual bandit problem into a linear bandit problem, as underlined in lines 285-288.\n", "questions": "Please comment on the main two weaknesses that I listed. ", "limitations": "The authors are clear about the limitations, and in particular, on dependency of their regret bounds on K, which does not match, in the worst-case, the known \\sqrt{d K T} regret bound. The discussion on page 9 is complete and upfront about the scope of their contribution.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The submission has a clear technical focus, and combines in a neat way techniques from Neu and Olkhovskaya (COLT 2020) and Ito, Hirahara, Soma, and Yoshida (Neurips 2020). The proof sketch provided on pages 6--8 is well structured. Up to some typos and some unclear pieces of notation, I can only praise the writing.\n", "weaknesses": "My main issue is with the algorithm, which relies on distributions that are difficult to compute exactly---as always with continuous exponential weights (see articles from Vempala and co-authors at the end of the 90s, commenting on Cover's original contributions). Allowing \\epsilon--approximations reduces the computational burden (see Section 3.3) but the effect of using these \\epsilon--approximations on the regret bounds is not discussed. Would this add some \\epsilon T terms? Then, it would probably be wise to pick \\epsilon = 1/T, not to kill with this extra term the possible fast rates of convergence yielded by first- and second-order bounds. (Also, it is not clear to me from Section 3.3 whether these \\epsilon--errors propagate and get worse and worse as t increases, or if for each t, we may and should compute an \\epsilon--approximation from scratch, not based on previous probability distributions.)\n\nAnother issue would be that I am unsure of what the second-order bound of Theorem 3.2 brings: it is highly general, and no corollary or example for the functions m_t are provided (except, I guess, the choices m_t \\equiv 0). More generally, I am unsure of how important it is to get refined bounds with a rather non-practical algorithm based on continuous exponential weights. \n\nA more minor issue is about the assumption of log-concavity. It is satisfied by many distributions (see https://en.wikipedia.org/wiki/Logarithmically_concave_function#Log-concave_distributions, and the submission could give examples) but is also not satisfied by other important ones.\n\nTypos / Remarks\n- Lines 96-97: rather cite Cover (1991) or to the very least the monograpu by Cesa-Bianchi and Lugosi (2006), instead of a 2018 reference \n- Line 123: I believe you refer to it as \\pi(X_t) and never use \\pi(a|X_t)\n- Line 131: Yes, this seems clear indeed\n- Line 134: I would rather have written E_{t-1} instead of E_t \n- Line 144 / Eq. (4); see also later occurrences like in Th.3.2: Is L^*_T the same as L_T^{\\pi^*}?\n- Algorithm 1: Say that each m_s is a function that is measurable w.r.t. \\mathcal{F}_{s-1}\n- Eq.(6): Somewhere earlier than in lines 291 and following, discuss the number of steps needed to achieve (6), i.e., geometric distribution with a parameter that you anyway bound in the proof---but mention it early, at latest on page 5 or in Section 3.3\n-  Line 185: Define somewhare what log-concavity of a distribution is, and provide examples\n- Eq. (18) and comments in lines 285-288: This is the key step and it's somewhat hidden, I'd suggest to put it more in front\n- Lemma 4.2: Notation is heavy and the result is extremely difficult to read, is there any way to make it smoother? That part and Eq. (19) should also be put more in front. \n- Line 291: Missing word before 1 ('Algorithm' I guess) \n- Appendices: Cauchy-Schwarz without a 't'", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nIndeed, we did omit a discussion of the epsilon approximations in the regret bound. As you note, one would require $\\epsilon = O(1/T)$ to ensure that the contribution of the additive approximation sums over rounds to a constant. It is also correct that the epsilon approximation should be recalculated per round as the covariance matrix depends on the current policy. The assumption of log-concavity is a restrictive one, and we are making efforts to remove it in further work on this topic.\n\n\nWith regard the choice of $m_{t}$ for $t\\in[T]$, any sequence of $m_{t}$ will satisfy the bounds we've given (note that $m_{t}$ is in the definition of $V_{T}$), but some choices are better than others. The obvious choice being $m_{t}=0$ for all $t\\in[T]$, which leads to a first-order bound. In case we have some prior information about the losses, we have room to encode this in $m_{t}$, and if not, we can use $\\mathcal{F}_{t-1}$-measurable mean estimates, or ridge regression as described by Ito to obtain a second-order result. Since the ridge regression regret is $O(\\mathrm{log}(T))$, this does not affect the rate significantly.\n\nMany thanks for your careful reading, and consequent identification of typos/points of improvement for the camera-ready version. "}, {"review_id": "N9fG6ldV6p", "reviewer": "Reviewer_pxmm", "summary": "This paper studies the adversarial linear contextual bandit setting, an online learning problem with $K$ arms, stochastic contexts in $\\mathbb{R}^d$, and adversarial rewards (which are assumed to be a linear function of the context for each arm). Previous work proves a worst-case regret guarantee that is $\\sqrt{KdT}$. They obtain regret guarantees which instead of scaling with $\\sqrt{T}$ can scale with other quantities that are smaller: a certain \"second-order\" quantity called $V_T$, and a first-order or (small loss) bound of $L_T^\\star$.\n\nThis is accomplished using a new algorithm called ContextEW which is a continuous exponential weight style algorithm, inspired by previous work of [Ito et al. '20]. They show that it achieves the aforementioned regret guarantees and can be efficiently implemented.", "questions": "1. In the equation after line 131, what exactly is $\\mathbb{E} \\theta_{t,a}$? The $\\theta$ are assumed to be adversarially selected, under some choices of actions selected by a learner, so what does it mean to take the expectation here?\n2. What is the intuition for the truncation/rejection sampling step? It is mentioned that it is used to reduce the variance. What would the final bound look like if there was no truncation/rejection sampling step?\n3. Typo: in (10), $P_t$ should be $\\mathbb{P}_t$ to be consistent with the rest of the notation.\n4. Computational complexity: \n    - I don't really understand how one should calculate $\\tilde{\\Sigma}$. This requires a sampling oracle to $\\mathcal{D}$ in order to use the [Lovasz-Vempala '07] results right?  My understanding is that one can try to approximate (9) using draws from $\\mathcal{D}$. Can the authors explain how to (approximately) calculate  $\\tilde{\\Sigma}_{t,a}$? \n    - A follow up to the previous question is how does the error in sampling/computing the covariances propagate to the final error bound? \n    - One can try to pick $\\epsilon = 1/\\mathrm{poly}(T)$. Is computing the covariance still \"computationally efficient\" since the computational complexity seems to scale polynomially with the total length of the problem $T$?\n5. At a high level, what is the motivation for studying second-order bounds? When would we expect these to be small in practice?\n6. Questions about proof details:\n    - typo: I believe in Lemma C.1 there should not be a subscript of $Q_t$ in line 447.\n    - In the last inequality after line 468, where did the integration over $x$ go?\n    - I'm a bit confused about why the quantity $m_t$ appears in the Proof of Lemma C.4. For example, in the first equality after 495, how does the $-m_t$ appear? I'm not able to follow this. Is there some relationship between $\\hat{\\theta}_t$ and $m_t$ that is being exploited in this proof?\n    - I didn't follow (38), how is the unbiasedness of $\\hat{\\theta}_t$ used?\n7. It would be nice if the relevant lemmas from [Ito et al. '20] were restated in the appendix, to make the proof self contained. For example, Lemma 6 of their paper is used in the proof.\n", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well written and explains the problem statement and results well.\n- The paper provides a new algorithm for adversarial linear contextual bandits which achieves first and second order bounds, a standard object of study in bandit literature.", "weaknesses": "- It is a bit unclear from me how much of the work is original, or whether it is a straightforward exercise to modify the results from [Ito et al. '20] and [Neu-Olkhovskaya '20]. Perhaps this can be made clearer in the proof sketch and technical sections to delineate what techniques/results are new.\n- The discussion on computational complexity could be improved (see questions below).\n- The key intuitions for the algorithm and analysis are unclear to me (see questions below).\n- The results rely on the assumption that the distribution of the contexts is log-concave (which is a limitation that comes from building upon previous work). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To emphasize the above, an application of an algorithm designed to solve the linear bandit problem cannot be applied directly to the linear contextual bandit, and there are no such examples for this setting.\nWith regard to your questions:\n\n1.\tThe meaning of the expectation is with respect to the filtration (i.e. the adversary can pick the parameter $\\theta$ based on previous random events), or any randomness the adversary may add. Note that our ability to derive a first-order bound is an implicit assumption that the adversary may not be worst-case.\n\n2.\tAs we state in the discussion section, without the rejection sampling step,  it can be removed by paying a $\\log(1/\\lambda_{\\min}(\\Sigma))$ multiplicative\nterm in the regret by implementing additional exploration with probability $1/T$. \n\n3.\tThanks for spotting the typo, we will fix it.\n\n4. You are correct - it is required to have an oracle for taking samples of $\\mathcal{D}$, but we have assumed that the distribution is known to the learner, and that the learner has oracle access. $\\tilde\\Sigma_{t,a}$ can be calculated by drawing samples from the joint distribution of $\\mathcal{D}$ and $\\tilde{\\pi}_{t}(\\cdot|X)$ $m \\geq 100 \\frac{dK}{\\epsilon^{2}}\\mathrm{log}^{3}\\frac{dK}{\\epsilon^{2}}$ times (Theorem 2.6 and Corrolary 2.7 from L. Lovász and S. Vempala. (2007)). This is where log-concavity of both $\\mathcal{D}$ and $\\tilde{\\pi}$ helps us considerably, as their proof heavily relies on this assumption. Indeed this gives us a computational complexity of $O(dKT^{2})$ per round; a vast improvement over the MYGA algorithm which achieves the same regret bound (and the best achieved by any algorithm for this problem setting; our Theorem 2.1), which has a complexity of $O(T^{dK})$ per round, and bringing our algorithm well within the reaches of implementation.\n\n5.\tThe variance-dependent bound is advantageous when a good prediction of the losses are available, and thus \nthe actual regret incurred by the algorithm is small. Another example is when the losses are stochastic and have small \nvariance. \n\n6. \nR: Typo: I believe in Lemma C.1 there should not be a subscript of $Q_t$ in line 447: \n\nThis is right, we will fix this typo.\n\nR: In the last inequality after line 468, where did the integration over $x$ go? \n\n There is a typo - sign of integration over X and dx are missing. \n\nR: I'm a bit confused about why the quantity $m_t$\n\tappears in the Proof of Lemma C.4. For example, in the first equality after 495, how does the $-m_t$\n\tappear? I'm not able to follow this. Is there some relationship between $\\hat{\\theta}_t$\n\tand $m_t$\n\tthat is being exploited in this proof? \n\n Indeed, there is  a typo in our definition of $w_t$. The correct definition is $w_t(q|x) = \\exp(- \\eta_t \\sum_{a=1}^K q_a \\langle X_t, \\sum_{s=1}^{t-1}\\hat{\\theta}_{s,a} + m_{t,a}\\rangle)$.\n\nR: I didn't follow (38), how is the unbiasedness of $\\hat{\\theta}_t$ used? \n\nWe use $\\mathbb{E}[\\langle z(q_0 - \\pi^*(X_0), X_0), \\hat{\\theta}_t\\rangle ] = \\mathbb{E}[\\langle z(q_0 - \\pi^*(X_0), X_0), \\theta_t\\rangle ]  \\le 2$, where in the last step we used that the loss values are $\\ell_t \\in [-1,1]$. We will add this explanation to the analysis. \n\n7. We will add the corresponding lemmas to the analysis. \n"}]

Author rebuttal:

To all reviewers:

We thank all reviewers for their insightful comments.

Comparison to Neu \& Olkhovskaya (2020): We note that our approach is
not a straight-forward extension of Neu \& Olkhovskaya (2020), which
would lead to discrete exponential weights over arms (i.e.\ the corners
of the simplex) rather than continuous exponential weights over the full
simplex. In fact, it was a breakthrough in our investigations to make
this switch to the continuous version, because all variants of the
discrete approach that we tried ended up having too large variance to
obtain first- or second-order bounds.


Comparison to Ito et al. 2020:  It's crucial to note that algorithms for the linear bandit problem are not 
universally applicable to the contextual bandit problem, rendering the method used in this paper unique. Our idea of drawing 
the distribution over arms from a context-adapted version of continuous exponential weights, and only then sampling an 
action from the resulting simplex element is clearly not a trivial modification of the linear bandit algorithm, and has 
not been done before in the existing literature. To restate, we are proposing a conditional reduction of linear 
contextual bandits to the linear bandit scenario when contexts are i.i.d. We establish the effectiveness of this 
reduction by demonstrating that the former can take on the data-dependent regret bound of the latter. This may pave the way for an area of inquiry within the bandit literature, as 
this could also be extended to broader function approximation scenarios where adaptive regret bounds are crucial. Consequently, this approach could have potential applications across several subfields of decision-theoretic 
learning.

Assumptions: While our log-concave assumption on the distribution may not be ideal, we find it remarkable that such a simple assumption can result in such a big improvement in the regret guarantees. While we agree that this assumption is arguably strong, we also wish to point out that it encompasses many natural distributions such as Gaussian or uniform on a convex set. Making such (and even more specific) assumptions about otherwise unknown distributions is not uncommon in learning theory (see, e.g., the numerous papers that have been written about stochastic multi-armed bandits with Gaussian rewards), so we feel that our result may very well be interesting enough for the bandit community, especially given the attention that the problem has been receiving recently. Indeed, we wish to reiterate our main point that obtaining first-order regret bounds for contextual bandits is a highly nontrivial problem that has been considered by many research groups over the past years, and thus any progress made on the topic is of potentially significant interest. We hope that our contributions may inspire future progress on this problem, and that our assumptions can eventually be relaxed.

Regarding the known context distribution: this is an assumption that is
present already in the work of Neu \& Olkhovskaya, and this is still an open problem to get rid of this assumption in 
order to obtain $\tilde O(\sqrt{dKT})$ regret bound.  It can be justified
in cases where labels/losses are expensive to obtain, but obtaining unlabeled contexts is cheap (as can be the case, 
e.g., in online advertising).  As discussed in Section 3.3, it is sufficient to have sampling access to
the context distribution. 


Meta-review: The authors make a substantial theoretical contribution to the area of contextual bandits, proving stronger regret bounds for the case of adversarial linear contextual bandits, that depend on adaptive properties of the realized sequence of losses. 

The reviewers all agree that this is an interesting and new theoretical results. There is only one concern regarding incrementality to prior work in terms of techniques. The authors offered several dimensions in which their techniques differ in their rebuttal responses. It would be great if these clarifications could be made more vivid in their paper if the paper gets accepted.
Decision: Accept (poster)