An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits
Authors: Kiarash Banihashem
MohammadTaghi Hajiaghayi
Suho Shin
Max Springer
Venue: NeurIPS 2023 poster (2023)
Keywords: contextual bandits
adversarial bandits
oracle-efficient online learning
TL;DR: We improve the regret bound for oracle-efficient adversarial contextual bandits.

Abstract: We present an oracle-efficient relaxation
  for the adversarial contextual bandits problem,
  where the contexts are sequentially drawn i.i.d from a known distribution and the cost sequence is chosen by an online adversary.
  Our algorithm has a regret bound of $O(T^{\frac{2}{3}}(K\log(|\Pi|))^{\frac{1}{3}})$ and makes at most $O(K)$ calls per round to an offline optimization oracle,
  where $K$ denotes the number of actions, $T$ denotes the number of rounds and $\Pi$ denotes 
  the set of policies.
  This is the first result to improve the prior best bound of $O((TK)^{\frac{2}{3}}(\log(|\Pi|))^{\frac{1}{3}})$ as obtained by 
  Syrgkanis et al.
  at NeurIPS 2016, and the first to match the original bound of 
  Langford and Zhang at NeurIPS 2007
  which was obtained for the stochastic case.

An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits
Kiarash Banihashem University of Maryland, College Park ki arash@umd, edu
MohammadTTghi Hajiaghayi University of Maryland. College Park haj i iagha@umd. edu
Suho Shin
Max Springer
University of Maryland, College Park suhoshin@umd..
University of Maryland, College Park mss4230umd.co
Abstract
We present oracle-efficient relaxation for the adversarial contextual bandits problem, where the contexts are sequentially drawn i.i.d from known distribution and the cost sequence chosen by online adversary. Our algorithm has regret bound of O (K log(( ( and makes most O(K) calls per round an offline optimization oracle, where K denotes the number of actions, T denotes the number of rounds and II denotes the of policies. This is the first result improve the prior best bound O(T K) (log( { as obtained by Syrgkanis et al. at NeurIPS 2016, and the first to match the original bound of Langford and Zhang at NeurIPS 2007 which was obtained for the stochastic case.
Introduction
One of the most important problems in the study of online learning algorithms is the contextual bandits problem. As a framework for studying decision making in the presence of side information, the problem generalizes the classical multi-armed bandits problem and has numerous practical applications spanning across clinical research, personalized medical care and online advertising, with substantial emphasis placed on modern recommender systems.
In the classical multi-armed bandits problem, decision maker is presented with K actions (or arms) which it needs choose from over sequence of T rounds. In each round, the decision maker makes its (possibly random) choice and observes the cost of its chosen action. Depending on the setting, this cost is generally assumed be either stochastic or adversarial. In the stochastic setting, the cost of each action is sampled i.i.d. from fixed, but priori unknown, distribution. In the more general adversarial setting, no such assumption is made and the costs in each round can be controlled by an online ad adversary. The goal of the learner is to minimize its regret, defined as the absolute difference between its total cost and the total cost the best fixed action in hindsight.
The contextual bandits problem generalizes this by assuming that each round, the learner first X' and chooses its action based on this
sees side information, referred to context, information. As in prior work (Rakhlin and Sridharan 2016 Syrgkanis et al., (0166), we assume that the æ are sampled i.i.d. from a fixed distribution D. and that the learner can generate samples from D as needed. In addition, the learner has access to a set of policies, II, where a policy is defined as mapping from contexts actions. As before, the goal of the learner we here define as the absolute difference between its total cost and the total cost of the best policy of in hindsight.
minimize its regret, which
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

It is well-known that by viewing each policy as an expert, the problem can be reduced to the bandits with experts problem where, even in the adversarial setting, the ExP4 (Auer et al., [995] algorithm achieves the optimal regret bound of O( O(yTK (T) Computationally however, the reduction is inefficient as the algorithm's 's running time would be linear in [IT]. Since the size of the policy set, II,
can be very large (potentially exponential), the utility of this algorithm is restricted in practice.
Given the computational challenge, there has been a surge of interest in oracle-efficient algorithms. In this setting, the learner is given access to an Empirical Risk Minimization (ERM) optimization oracle which, for any sequence of pairs of contexts and loss vectors, returns the best fixed policy in II. This effectively reduces the online problem to an offline learning problem, where many algorithms (e.g., SVM) are known to work well both in theory and practice. This approach was initiated by the seminal work Langford and Zhang (007)), who obtained a regret rate of (TT2/3 (K log II) for stochastic rewards, using an e-greedy algorithm. This was later improved to the information- theoretically optimal O( V 'KK log [II] (Dudik et al., 2011]. Subsequent works have focused on improving the running time of these algorithms (Beygelzimer et al. [011]] Agarwal et al.) [2014] Simehi-Levi and Xu 2022), and extending them to a variety of problem settings such as auction
design (Dudik et al.
2020). minimizing dynamic regret (Luo et al., 2018 Chen et al. 2019). ban-
dits with knapsacks (Agrawal et al., 2016), semi-bandits (Krishnamurthy et al. 2016). corralling bandits (Agarwal et al.)
2017), smoothed analysis (Haghtalab et al. 2022 Block et al. 2022). and
reinforcement learning (ooterr et al. 2021).
Despite the extensive body of work, progress for adversarial rewards has been slow. Intuitively, approaches for the stochastic setting do not generalize adversarial rewards because they try to "learn the environment" and in the adversarial setting, there is no environment to be learnt. This issue can be seen in the original multi-armed bandits problem as well. While the regret bounds for the adversarial setting and the stochastic setting are the same, the standard approaches are very different.
| In the stochastic setting, the most standard approach is the UCB1 algorithm (Auer et al.. 2002). which is intuitive and has a relatively simple analysis. In the adversarial setting however, the standard approach is considerably more complex: the problem is first solved in the "full feedback" setting, where the learner observes all of the rewards in each iteration, using the Hedge algorithm. This is then used as a black box to obtain an algorithm for the partial (or bandit) feedback setting by constructing unbiased estimates for the rewards vector. The analysis is also much more involved compared to UCBI; a standard analysis of the black box reduction leads to the suboptimal bound of 73/4 K1/2, and further obtaining the optimal VTK bound requires a more refined second moment analysis (see Chapter 6 of [Slivkins (2019) for more detailed overview).
As a result, oracle-efficient algorithms for the adversarial setting were first proposed by the inde- pendent works Rakhlln and Sridharan (2016) and [Syrgkanis et al. (2016a) in ICML 2016, who obtained a regret bound of O(7 1/2 (Tg((T)))/4 and left obtaining improvements as an open problem. This was subsequently improved to (((T))2/3 2/3 log((11))/33 by Syrgkanis et al. 2016b) at NeurlPS 2016.
1.1 Our contribution and techniques
In this work, we design an oracle-efficient algorithm with regret bound of 2 log (I) Our result is the first improvement after that of SSrgkanis et al. (2016b), and maintains the best regret upper bound to the extent of our knowledge. This is also the first result to match the bound of Langford and Zhang] (2007), the original baseline algorithm for the stochastic version of the problem. We state the informal version of our main result (Theorem 7 in the following.
Theorem (Informal). For large enough T there exists an algorithm (Algorithm I that achieves expected regret on the order of ( (K log 113) ) for the adversarial contextual bandits problem using most OK) calls per round to ERM oracle.
In order to compare this result with prior work, it is useful to consider the regime of K = T for a constant a > O. In this regime, our work leads to a sublinear regret bound for any a 1, while
WWe note that any approach for the adversarial setting works for the stochastic setting well. However, both theory and practice, specialised approaches are more commonly used.
"When 2' is small, our improvement compared to prior work is more significant; we focus on the large T setting to obtain fair comparison.
2

---

prior work (Rakhlin and Sridharan 2016 Syrgkanis et al. 2016b) can only obtain sublinear regret for a < 1/2.
Our improved dependence on K is important practically since, for many real-world implementations such as recommender systems, the number of possible actions is very large. Additionally, many bandits algorithms consider "fake" actions as part of a reduction. For example, a large number of actions may be considered as part of a discretization scheme for simulating a continuous action space (Slivkins, 2009). In such cases, the improved dependence on K could potentially imply an overall improvement with respect to T, as the parameters in the algorithm are often chosen in such way that optimizes their trade-off.
From technical standpoint, our result builds on the existing works based on the aalax-and-randooe framework of RRakhlin et al. (2012) Rakhlin and Sridharan (2015) used this framework, together with the "random playout" method, to study online prediction problems with evolving constraints under the assumption of a full feedback model. [Rakhlin and Sridharan (2016) extended these techniques to the partial (bandit) feedback model, and developed the BISTRO algorithm which achieves O(T3/4K' log( II (4+) regret bound for the adversarial contextual bandits problem. Subsequently, Syrgkanis et al. (2016b) used a novel distribution of hallucinated rewards as well as a sharper second moment analysis to obtain a regret bound of (((K)) 2/3 log(( We further improve the regret rate to ((T2// K log((1)))
by reducing the support of the hallucinated rewards vector to single random entry. We note the previous approaches of Rakhlin and Sridharan (2016); SSrgkannis et al. (2016b), as well as the closely related work of Rakhlin and Sridharan (2015). Set all the entries of the hallucinated cost to i.i.d Rademacher random variables.
We show that our novel relaxation preserves the main properties required for obtaining a regret bound, specifically, it is admissible. We then prove that the Rademacher averages term that arises from our new relaxation improves by factor of K, which consequently leads to a better regret bound. We further refer to Section 3 for a more detailed description of our algorithm, and to Section for the careful analysis.
1.2 Related work
Contextual bandits. There three prominent problem setups broadly studied in the contextual bandits literature: Lipschitz contextual bandits, linear contextual bandits, and contextual bandits with policy class. Lipschitz contextual bandits (Lu et al., 2009: Cutkosky and Boahen 2017) and linear contextual bandits (Chu et al., 2011) assume a structured payoff based on a Lipschitz or linear realizability assumption, respectively. The strong structural assumptions made by these works however make them impractical for many settings.
To circumvent this problem, many works consider contextual bandits with policy classes where the problem is made tractable by making assumptions on the benchmark of regret. In these works, the learner is given access to a policy class II and competes against the best policy in II. This approach also draws connections to offline machine learning models that in recent years have had a huge impact on many applications. In order for an algorithm to be useful in practice however, it needs to be computationally tractable, thus motivating the main focus of this work.
work is the online learning with experts problem where, in each round, the learner observes a set of N experts making recommenda- tions for which action take, and decides which action to choose based on these recommendations. The goal of the learner is to minimize its regret with respect to the best expert in hindsight. In the full feedback setting, where the learner observes the cost of all actions, the well-known Hedge (Cesa- Bianchi et al.) 1997) algorithm based on randomized weighted majority selection rule achieves the best possible regret bound of O(VT'n In N). Correspondingly, in the partial feedback setting, ExP4 (Auer et al. 1995) exploits Hedge by constructing unbiased "hallucinated" costs based on the inverse propensity score technique, and achieves the optimal regret bound of O(VKT In N). By considering an expert for each policy, the contextual bandits problem can be reduced to this problem. This reduction suffers from computational intractability however due to the linear dependence on [IT] in the running time. Since the number of policies can be very large in practice, this poses major bottleneck in many cases. We alleviate this intractability issue through computationally feasible oracle-based algorithm with improved regret bound.
Online learning with adversarial rewards. Closely related
3

---

Oracle efficient online learning, Stemming from the seminal work of Kalai and Vempala (200)) there has been a long line of work investigating the computational barriers and benefits of online learning in variety of paradigms. Broadly speaking, the bulk of online algorithms are designed on the basis of two popular frameworks in this literature:
weww--hh-perturbeee -eadeeeer (Kalai and Vempala, 2005 Suggala and Netrapalli 2020; Dudik et al. [2020] Hagghtaab et al. (2022) and relax- and-randomize [Rakhlin et al. 2012). Both frameworks aim to inject random noise into the input set before calling an oracle to construct more robust sequence of actions to be played against an adversary, but differ in how they introduce such noise to the system. Our algorithm builds on the relax-and- raddmmmmoiie technique and improves upon the previous best result of Syrgkanis et al. (2016b).
Despite their computational advantages, it is known that oracle efficient algorithms have fundamental limits and, in some settings, they may not achieve optimal regret rates (Hazan and Koren 2016). Whether this is the case for the adversarial contextual bandits problem remains open problem.
Preliminaries
In this section, we explain the notation and problem setup, and review the notion of relaxation based algorithms in accordance with prior work (Rakhlin and Sridharan 2016 Syrgkanis et al.) 2016b).
2.1 Notation and problem setup
Given an integer K, we use [K] to denote the set (1..... K} and 01:K to denote { (aj,-.., ag }. We similarly use (a, 6, c) K to denote the set of tuples (a1, b1, ci)...., (ax, bec,bK,,K, ex) J. The vector of zeros is denoted as 0, and similarly, the vector of ones is denoted 1.
We consider the contextual bandits problem with [T] rounds. In each round E [T], context z; is shown to the learner, who chooses an action ÿt E [K] and incurs a loss of c; (D+)). where or E [0, 1jk denotes the cost vector. The choice of the action Yt be randomized and we assume that the learner samples i/ from some distribution qt- The cost vector is chosen by an adversary who knows the cost vector 2t and the distribution q but, crucially, does not know the value of ÿt-
As in prior work (Rakhlin and Sridharan 2016 Syrgkanis et al. 2016b), we operate in the hybrid i.i. iidd-adversaril model where H, is sampled from some fixed distribution D. and the learner has sampling access to the distribution D. We additionally assume that the feedback to the learner is partial, i... the learner only observes c, (ft) and not the full cost vector C..
The learner's goal to minimize its total cost compared set of policies II, where policy is defined as mapping from contexts to actions. Formally, the learner aims to minimize its regret, which we define
REG Σ (gt, c.)
inf Σ c(((()))) TEll
where (gt, ca) denotes the dot product of q: and ct, and inf denotes the infimum.
We assume that the learner has access to a value-of-ERN, optimization oracle that takes as input sequence of contexts and cost vectors (x, c)1st. and outputs the minimum cost obtainable by a policy II, i.e., infren Σt= e- (T(())))
2.2 Relaxation Based Algorithms
In each round E [T] after selecting an action and observing the adversarial cost, the learner obtains an information tuple, which we denote by [e( ge: Gt, (D.)) (.).), St). Here, ÿ ~ 9r is the action chosen from the learner's 's distribution, and S, is the internal randomness of our algorithm, which can also be used in the subsequent rounds.
Given the above definition, the notions of admissible relaxation and admissible strategy are defined as follows.
Definition 2. A partial information relaxation REI(() a mapping from the information sequence (4 (4,....I1 12) to a real value for any t E [T]. Moreover, cartial-nfformatio relaxation is deemed

---

admissible for any such t, and for all I1.... I6-1:
E [inf, supa, Eara,,s, (cx(0)) + REI((1a)]] I (EI((T1-11)
(1)
and for all 21.T, Cut and qu:r
I P [REI( - Σ (((((x)))
A randomized strategy qur is admissible if certifies the admissibility conditions 7 and (2)
Intuitively, relaxation functions allow us to decompose the regret across time steps, and bound each step separately using Equation (T. The following lemma formalizes this idea.
Lemma 3 (Rakhlin and Sridharan 2016)). Let REL be admissible relaxation and qur be corresponding admissible strategy. Then, for any CLT, we have the bound
E [REG] S REL(0).
Contextual Bandits Algorithm
We here define admissible strategy in correspondence with the relaxation notion from the prior section, and use to outline our contextual bandits algorithm. As mentioned in Section [II our algorithm is based the BISTRO+ algorithm of Syrgkamiss et al. (2016b) and our improvement is obtained by defining a new relaxation function, which we discuss below. We discuss how this improves the regret bound in Section 4
Unbiased cost vectors. In order to handle the partial feedback nature the problem, we use the standard technique of forming unbiased cost vector from the observed entry, together with the discretization scheme of Syrgkanis et al. (2016b). Let y < 1 be parameter be specified later. Using the information I, collected round set estimator be the random vector whose elements are defined by Bernoulli random variable
Ky 1 1 9tl with probability y c((0.) (Xe)
(1))
otherwise
We note that this is only defined for min; (1) 2 X/K, K, thus imposing constraint that must be ensured by our algorithm. It is easy to verify that this vector is indeed an unbiased estimator:
(i(i)
Egoan [2((1] = (e( -7 Kgg
-y--= (i).
Relaxation function. We first construct ooe-hot Rademacher random vector by randomly sampling an action i E [K] and setting (j) = 0 for * and et( to Rademacher random variable in
1). We additionally define Z, (0, Kn Ky-1) that takes value Ky-1 with probability y and otherwise. Using the notation for the random variable tuple (x, e, Z)41: we define our relaxation REL as
REL( B,, ((),,,)))
where R((I, (e) Pt) is defined to be
TT () - inf Σ ((T(x,)))
Σ 27, (m(22,))
T=H11
We note the contrast between the above definition and the relaxation frameworks used in prior work (Rakhlin and Sridharan| 2015) 2016 Syrgkanis et al. 2016b): These works all set every entry in E, to Rademacher random variables, while we only single (randomly chosen) entry to Rademacher random variable and set the rest the entries to zero.
The changes in the relaxtion function are motivated by the algorithm analysis (see Section Specifically, in order to ensure admissibility, the symmetrization step the Relax and randomize framework applies only to single (random) action. Applying noise to all the entries, is done in

---

prior work, leads to valid upper bound but is not tight. As we show in Lemma applying noise to single entry is sufficient, as long as this entry is chosen uniformly at random. The reduced noise leads to an improved Rademacher averages term (see Theorem 6 which in turn leads to a better regret bound.
Randomized strategy. As in prior work (Rakhlin and Sridharan, 2015 2016 Syrgkanis et al. 2016b), we use the "random playout" technique to define our strategy. We use hallucinated future cost vectors, together with unbiased estimates of the past cost, to choose a strategy that minimizes the total cost across T rounds.
Define D = [Ky- ee E (0), where e; is the i-th standard basis vector in K dimensions. We further define AD. the set of distributions over D, and D S Ap to be the set
{p DD max p(i) 1 7 }. iE[K]
(5)
K
Recall that or denotes the random variable tuple (Ir, e, Z) 1.7. We sample Pr and define of (px) as:
qe (pt) = min sup Berwi Kg 2)) + R((x, C) Pt)).
(6)
geáx M.E.'
We than sample the action dr from the distribution (p:) defined as
ge = (1 7) (p:) + K 1.
In order to calculate (p:).. we use water-filling argument similar to Rakhlin and Sridharan (2016) and (Sygkkanis et al. (2016b). Formally, we will use the following lemma, the proof of which is in Appendix [
Lemma 4, There exists a water-filling algorithm that computes the value of (pt) for any given in time OK) with only K + accesses to value-of-ERM oracle in every round.
A full pseudocode of our approach is provided in Algorithm
Algorithm 1: Contextual Bandits Algorithm
for f == 1. T do
Observe context 2t
Draw random variable tuple (x, e, Z) Z)+
Compute qe (pt) via Equation
Draw action Jt ~ 4: (Pt) and observe ea (f:)
Estimate cost vector é, via Equation]
end
4 Analysis
In this section, we provide the formal statement of our theoretical guarantees and discuss their proofs. Due to space constraints, some of the proofs are deferred to the supplementary material.
As mentioned in the introduction, our main novelty is the use of a new relaxation function, which we discussed in Section 3 that uses less variance in the hallucinated cost vectors. Our initial result verifies that the our novel relaxation is indeed admissible and, as result, we can leverage the prior work demonstrating the expected regret of these algorithms.
Theorem 5. The relaxation function defined in (4. and the corresponding strategy 7 are admissible (Definition
Theorem 5 contrasts with existing admissible relaxations in that it only uses a single Rademacher variable for each time step, while prior work - Lemma Rakhlin and Sridharan| (2015). Theorem in Rakhlin and Sridharan (2016) and Theorem 3 in SSyrgkanis et al. (2016b) all use k independent Rademacher variables. To our knowledge, this is the first work in which the number of Rademacher variables used in the relaxation does not grow with the number of arms. As we discuss below, this

---

allows us to reduce the variance of the hallucinated costs, leading to better regret bound. The proof of Theorem is provided in Section |4. and is based on novel symmetrization step (Lemma 9 which may be of independent interest.
As highlighted in Section 2.2 admissible relaxations powerful framework for upper bounding the expected regret in online learning through Lemma 3 and the value of (EL( Formally, Lemma
3 implies
T Σ
E REG] < (EL( = 7 + Epo
sup
mell
In order to bound the regret of our algorithm, it suffices to bound the Rademacher averages term above, which we formally do in the following Theorem.
Theorem 6. For any
K +
log /2, the following holds:
KT log III
E (Z,c)rr
sup sEll t=1
Z(((((())))
2
7
The above theorem can be thought of as an improved version of Lemma 2 from SSrgkanis al.) (2016b), where we improve by factor of K. Our improvement comes from the use of the new Rademacher vectors that only contain a single non-zero coordinate, together with a more refined analysis. We refer to Section 4.2 for a formal proof of the result.
Combining Lemma Equation g and Theorem we obtain the main result of our paper which state here.
Theorem 7. The contextual bandits algorithm implemented in Algorithm has expected regret upper bounded by
TKlog log II)
4
+TT,
for any
< S751, which implies the regret order of O((K log /T/333///33 when T > 4K log([T]) Furthermore, the Algorithm makes at most K + calls to calue-ofEERM oracle in each round.
K log [|]
2T
We refer to Appendix A for the proof of this result.
4.1 Proof of Theorem
In order to prove Theorem we need to verify the final step condition (2). and show that the ge defined in Equation 7 certifies the condition (T) i.e..
E,,, sup Eg (c.(0r) + REL((T.))] (EL(()..-)).
where d sampled from 9e and I1 denotes 11. le qt- Gt, Ct, S,)). Verifying condition
standard and we do this in Appendix D It remains to prove Equation (9). Since most admissibility
proofs in the literature (Rakhlin al.] 2012, Rakhlin and Sridharan, 2015 2016 [Syrgkanis al.)
2016b) follow the framework of the original derivation of Rakhlin et al. (2012). in order to emphasize based on existing
our novelty, we divide the proof into two parts. The first part (Lemma techniques (in particular, the proof of Theorem 3 in Syrgkannss et al. (2016b)) and its proof is provided in [ The second part (Lemma()) uses new techniques and we present its proof here.
Lemma 8. For any t E [T], define Ar, and Ce as
Ax,t - EG(((())))) Σ 27. (7T5)(((x+)), C. (T==(T-1+1])
T=t+1
Letting 8 denote Rademacher random variable independent of pt and êt the following holds for any value of ZtZ
sup (286) + Ani) well
sup Eg.s, (c((e) + REL([1a)] $ Ep, Gt
Eep P.EAD
sup
+ +Cr.
7

---

Lemma 9. Defining An, as in Lemma 8 the following bound holds for any t E [T]:
sup
E..p sup (T(EE) + An.1) s B.
sup
(2Z, =c(T((()) An,))
(10)
p.EA'b
LTell
Lell
Combining the above lemmas we obtain Equation ( by definition of REL:
Eg,
sup Bg..s. (cc(0r) + REL((L
s Exi,pt
sup
E
sup (262,(T((1)) + Anoi Lxlll
+ +
piEAAb
Emg Bi Zori
sup (2Z+ (x((1)) + Ams)) + C
Lell
pp--
sup (27z cx(((x=))) Art) +
TEll
REL(I1:111..
Proof of Lemma 9 For any distribution Pt E A' the distribution of the each coordinate of é has
support on {0, 7 K} and equal y with probability at most 7/ Using pt(1) denote P(a(i) =
e, we can rewrite the LHS (left hand side) of Equation (T0 as
sup (256(( An.)) Lxell
sup p.EAp
Eéippi
2K5 (1- Σ pc(t)) sup Ar, + Ei((E) sup An, ?
(1
(T(2A) =il] a1)
sup mEd.
2K6 (1- pr(i)) sup Ar, P.)(E) sup A + 1 [T() =0]] .11
sup 05Pr
where the first equality follows from expanding the expectation with respect to êr and the second equality follows from the definition of D' We argue that this value is maximized when each pe (i) takes on its maximum value, i.e., 7/ K. It suffices to observe that
2K8 Es sup A +
2K6 1 [m(2.)
a1) sup Ar,
[T(xx) = 2 sup An,
Es
where the inequality follows from the fact that supremum of expectation is less than expectation of supremum, and the equality uses the fact that E [8] = 0. Therefore, maximize the LHS of
Equation (10) via selecting pt that satisfies pr( R for i 2 1. It follows that
sup B E.E
sup (T(x)) + Ar,1)
tell
2K8 (m(x;) =1]]
(1-7) sup An,t Σ Es
sup An,
E,,., sup (2Z, ex(m (x(T)xx)) Art)
-ell
finishing the proof.

---

4.2 Proof of Theorem 6
start with following standard inequalities for handling the supremum using the moment generating function.
T
Ein Ze51 )
B(z,e)ir
sup TEll 1=1
Σ
Zesr (T(x))
= Ezir
BeEr
log
sup e TEll
Ezur
E
log
Di ((c((T((s))
TEll
EZz
1
log
BELr
Σ
e EE (((((((a)))
X
Lxell
(80)
EZLT
log
Σ
II
Ee
well
(=1
Inequality (i) holds due the concavity of log and (ii) follows from the independence of eg. We will additionally assume that is upper bounded by yv2/KK in the remaining analysis.
By our construction of the random variable &t. for any fixed x, (x(T(x))) takes the value 0 with probability 1 and the values -1 and 1 each with probability 1 We therefore have that
2K
Es, [Znsr((((ss]]]
1
+
AZ.
+
1
e -AZ,
K
2K
2K
1
22/7/2
$
+
K
K
e (e 2222/111-13
The first inequality above uses ex + = < 20 12 while the second inequality uses ex 2 + x for E R. This further yields
1 Ā
EII r=
T Ee, ((llealt(aa))
)]
22
EE 1
log
E EZZr
log
1
T
x² 22,22
Ezzr
log([[I))
+
AK
t=l
log([11)
1222//2 -
Bzur
XK
Recall that Z, takes the values 0 and
K
with probabilities y and respectively. It follows that
7
c 12 = =
1²k² 27
X²
E Ezir
-1 <
72
where the inequality follows from the fact that ex 1 7/2/KK Therefore,
2x for E (0, 1) and the assumption
T EI E.
log III
TKA
E Ez
loo
A +
A 1=
By taking derivative with respect to À we obtain
log IT]
+ TKK/ / O.
2

---

and compute that the equation above is minimized at X assumption À S 1v2/KK because this is equivalent to of the lemma. Plugging this again yields
/
log(
We note that À satisfies the
TK
log(
which holds by the assumption
27
TK
TK
log [T]
log( MI)
2 TK log [1)/%
7 7log(
7
TK
which is the desired bound.
5 Conclusion
In this paper, we presented a novel efficient relaxation for the adversarial contextual bandits problem and proved that its regret is upper bounded by O log [I]))//3) This provides marked improvement with respect to the parameter K as compared to the prior best result and matches the original baseline of Langford and Zhang (2007) for the stochastic version of the problem. As mentioned earlier, non-efficient algorithms can obtain regret bound of O(V log( which is information theoretically optimal. While oracle-efficient algorithms can obtain the optimal regret bound in the stochastic setting (Dudik al., 2011). they do not always achieve optimal regret rates (Hazan and Koren, 2016). Whether or not optimal regret can be obtained in our setting using efficient algorithms remains an open problem and improving both the upper and lower bounds are interesting directions for future work. Additionally, while our work operates in the same setting as prior work (Rakhlin and Sridharan 2016 Syrgkanis al. 2016b), it would be interesting to relax some of the assumptions in the setting, most notably the sampling access to the context distribution.
Acknowledgements
This work is partially supported by DARPA QuICC NSF AF:Small #2218678, and NSF AF:Small 14269,, We thank Alex Slivkins for pointing us to the problem and initial fruitful discussions.
References
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. 2014. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning. PMLR, 1638-188 1646.
Alckh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. 2017. Corralling band of bandit algorithms. In Conference on Learning Theory. PMLR, 12-38.
Shipra Agrawal, Nikhil R Devanur, and Lihong Li. 2016. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Conference on Learning Theory. PMLR, 4-18.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. 2002. Finite-time analysis of the multiarmed bandit problem. Machine learning 47 (2002), 235-256.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 1995. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual joundations of computer science. IEEE, 322-331.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire, 2011. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth Inter- national Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 19-26.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. 2022. Smoothed online learning is as easy as statistical learning. arXiv preprint arXiv:2202.04690 (2022).
Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth, 1997. How to use expert advice. Journal of the ACM (JACM) 44, 3 (1997), 427-485.
10

---

Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen- Yu Wei. 2019. A new algorithm for non- stationary contextual bandits: Efficient, optimal and parameter-free In Conference on Learning Theory. PMLR, 696-726.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. 2011. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Stalistics, JMLR Workshop and Conference Proceedings, 208-214.
Ashok Cutkosky and Kwabena Boahen. 2017. Online learning without prior information. In Confer- ence on Learning Theory. PMLR, 643-677.
Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jen- nifer Wortman Vaughan. 2020. Oracle-efficient online learning and auction design. Journal of the ACM (JACM) 67, (2020), 1-57.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. 2011. Efficient optimal learning for contextual bandits. arXiv preprini arXiv: 106.2399 (2011).
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. 2021. The statistical complexity of interactive decision making. arXiv preprint vrXiv221/2.1348) (2021).
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. 2022. Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries. arXiv preprint arXiv:2202.08544 (2022).
Elad Hazan and Tomer Koren. 2016. The computational power of optimization in online learning. In
Proceedings of the firth-eighth annual ACM symposium on Theory of Computing. 128-141.
Adam Kalai and Santosh Vempala. 2005. Efficient algorithms for online decision problems. J.
Comput. System Sci. 71, (2005), 291-307.
Akshay Krishnamurthy, Alekh Agarwal, and Miro Dudik. 2016. Contextual semibandits via super- vised learning oracles. Advances In Neural Information Processing Systems 29 (2016).
John Langford and Tong Zhang. 2007. The epoch-greeds algorithm for contextual multi-armed bandits. Advances in neural information processing systems 20, (2007), 96-1.
Tyler Lu, Dávid Pál, and Martin Pál. 2009. Showing relevant ads via context multi-armed bandits. In Proceedings of AISTATS.
Haipeng Luo, Chen Yu Wei, Alekh Agarwal, and John Langford. 2018. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory. PMLR, 1739-1776.
Alexander Rakhlin and Karthik Sridharan. 2015. Hierarchies of relaxations for online prediction problems with evolving constraints. In Conference on Learning Theory. PMLR, 1457-1479.
Alexander Rakhlin and Karthik Sridharan. 2016. Bistro: An efficient iiaicaationbasee method for contextual bandits. In International Conference on Machine Learning. PMLR, 1977-1985.
Sasha Rakhlin, Ohad Shamir, and Karthik Sridharan. 2012. Relax and randomize: From value algorithms. Advances in Neural Information Processing Systems 25 (2012).
David Simchi-Levi and Yunzong Xu. 2022. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research 47, (2022), 1904-1931.
Aleksandrs Slivkins. 2009. Contextual Bandits with Similarity Information. CoRR abs/0907.3988 (2009). arXiv:0907.399 httpp://axivv. http://aaxii.orrr//////000//// wtg//bs///a//./////////////// 3986
Aleksandrs Slivkins. 2019. Introduction to multi-armed bandits. Foundations and Trends@ in
Machine Learning 12, 1-2 (2019), 1-286.
Arun Suggala and Praneeth Netrapalli. 2020. Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games. Advances Neural Information Processing Systems 33 (2020), 22316223326
11

---

Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. 2016a. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning. PMLR, 2159- 2168.
Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E Schapire. 2016b. Improved regret bounds for oracle-based adversarial contextual bandits. Advances in Neural Information Processing Systems 29 (2016).
12

---

A Proof of Theorem 7
Combining Equation g and Theorem
we obtain
TK log
REGT S VV
+ YT.
Setting the derivative with respect y of RHS zero, obtain
T T log | 3/2 0,
which is equivalent to
Note however that needs to satisfy 7 > KTT* and y 1. To verify the first condition, we should have T > K log( (log((I1))(22 (I)(()22))))
4K log [1
1/3
Putting our designated y implies that T should satisfy
T
T
T> K Io)
1133 1/2
T > K log ((II)
1/8
4K log([IT)
4K log(
K2 log"
III
log
T
T
32
4v2
which holds by assumption. To verify the second condition of y S 1, we need to have T > 4K log([]]), which again holds by assumption.
Plugging y the regret bound, have
O(T2/3(K log 1/))
completing the proof.
B Proof of Lemma
The proof is based on Lemma 4 in Syrgkanis et al. (001bb) and is provided for completeness. The pseudocode of our algorithm is provided in Algorithm
Compute qf Algorithm 2:
Input: value-of-ERM oracle, (I, é) 1a-1, and Output: of (Pr) as in Equation
Compute for all i E [K], th inf xen of
K Σ (-(xz)) - (((()))))
Σ 2 (T(2T)
using the value-of-ERR oracle
Compute 7/1 = 7(1)--9o) for all i E [K]
K
Set m 1,9 0
for k = 1, ...,. K do
q(i) t min(().) m). m + m mig(i)
end
m 0, distribute remaining m uniformly across coordinates of
Proof. We prove the result by rewriting the minimizer equation to be composed of only calls to our value-of-ERM oracle. For i [K], we define th be
T
inf WEI
Σ
+ (n +
Σ +=
22, + (

---

where = 0. We can thus write the definition of 97 (Pt) as
Kq(t)
arg inf sup Σ pe(i) gEAK PIEDD t=1
v5.) -p(0)
10
and note that the values of d can be computed via single call to the value-of-ERM oracle, and moreover we require K + calls to compute all the th
Now to compute the minimizer of the above, we first let Kq(i) the minimax value
1/1 and 1/o and rewrite
7
arg inf sup gEAp M.EDD 1=1
Σ Pt(1) 24 Pc(0) 20-
We reiterate that each (i) < 7/K for > O and thus we must distribute maximal probability across the 2; coordinates of largest value, i.e. we will put as much probability weight as permitted on arg [[[] 2,, and proceed to do the same for the second largest value, repeating the process until we exhaust the probability distribution or reach the terminal 2o. At this point, we can put the remainder of the probability weight on this final coordinate ensure summation
To proceed in analyzing the above water- filling argument, sort the coordinates 2, such that 2(1) 2 2(2) ... 2(K) for i and further define index be the smallest index such that 2(2) 2 20- By the probability weight distribution argument above, we can reduce the supremum over pt to be
water-filling
Σ K (() (1
K 1)
Σ
I K (2()) 20) + 20-
since we maximize p(i) for the z(z) in order and set p(t) = 0 for terms less than which would otherwise yield an addition of negative terms in the above summation. Thus, by definition of μ. we have for > f
K
(=()) - 20) + 20
7 K
(#(s) - 20) + 20.
K
where the + superscript denotes the RELU operator, (x)+ maxfx,00 0}. Therefore, the minimax expression is reformulated as
K (z(a) - 20)+ + 20.
arg inf gEAp 1=1
K
which is equivalent to minimizing the RELU term
arg inf qEAD
(2(() =0)
arg inf QEAD
(10))
K -1bx vbo)) r²o))
Simplify notation by setting 7(1:
so that the expression becomes
K
K [((i) +
arg inf DEAD d=1
We argue the minimization procedure as follows: select i E [K] such that < 0. Any positive probability weight on q(i) will yield an increase the expression, whereas for πι: we experience no increase in the objective until the value of 7); surpasses q(i). Thus, the minimizer will weight the actions with min s.m, >0 77s, 1} on the coordinates with 7), and distribute the remaining weight (if nonzero) arbitrarily among [K] This is more precisely outlined the pseudocode of Algorithm
2
14

---

C Proof of Lemma g
Denote by di = B,, [47 (pe)]. We note that since are drawing from pr. cal- culating qi (pt), and then drawing from di (pt), our algorithm effectively sampling from gi even though we do not calculate 9i explicitly. Now note that
Proof of Lemma 8
Birrg [cc( (gt, ca) (g) ai) + R..O/ ct Bynce Ro Cx)l + 7.
holds by definition of (pt) and the assumed bounds ca. Thus, it further holds that sup Eg.à (0t) + REL( s [
sup crE[0.1|K
Eg 19 2) + REL((1:)
By expansion of the second term on the right hand side, we rewrite the relation as
sup & Kg Gx) + (EL()
qE[0.1]
sup Eg, K &1) + Ep, [R((2, 1): pr)
(-Ce(T((x)) + AnD)] + +7(T -t)
sup Ege,é ( + Epp
sup LTell
sup Ega,e,
Ep. (pe),, sup (-à + + (TT
t).
aE|0.1]
xell
Furthermore, the symmetric construction of è implies that é takes the value Ke;/7 with probability most >/ Therefore, we know that è is sampled from a Pe A'D where A defined in Equation (5) Taking the maximum over all possible Pt, we bound the supremum term above with
(at). 21) + sup (-a(T(<x;) An.)) ]]
sup E Eg. 6.
Bp.
mell
S sup p.eAp
Ep,
(gT(P), sup (-)((x())) + Am.1)
xell
S Ep,
sup P.EAD
(p)), (,)
sup (-4(T((x)) Ar.1)
nell
where the second inequality is application of Jensen's inequality. We first replace the optimized oe by the corresponding infimum operator over qt, thus the term inside the expectation is equivalent to
inf sup Ee,op (g. d) + sup (-C((T(()) + An.)) yEAN P.EA
#ell
conditioned on Pr. By the minimax theorem, can interchange the infimum and supremum operators without decreasing the quantity, and this is further upper bounded as
inf sup Eisepe (q. (.) + sup (- + Anz)) gEAx MED'
=ell
sup inf Banpi (a..6) + sup (-&( + An.)) mEA. gEAR
*ell
and moreover, since the objective is linear with respect qe instead work with
(1) + sup (-a(T(())) An.))
sup min Eerope P.EAY, sE[K]
nell
15

---

Symmmetrization permits us to rewrite the above as
sup min Ea rpp
(()) + sup (-Q((T(x)) + Ana))
P.EA
(E[K]
well
= sup Eaepp piE
sup
min Berp [2(1) (((((=)))) + ATa [E|K]
TET
I sup p. p.EArb
sup
(Beppp, [[(((()))] (x<(=)))) + Am
sup (x(()) (=()))) + An.i)
$ sup E mpp D.EA/b
where the last inequality is an additional application of Jensen's inequality. Since èe 2g are sampled from the same distribution, this can be rewritten as
sup (c(()()))) - (T((1)) An.t)
sup E/ meD
LE
sup Ce p.ED'
sup (5(() - (TT(()))) + AT.1)
Tell
sup Ep
sup (0((()((z)) ((x(T()))) Axxe)
p.E.ip
Leel
and further split the term within the inner supremum to obtain
sup (+((()(()))) - (c((T(())) + An.))
sup B & m.E./
TEll
Ax.
(0((T((2)) + Ar.
)
= sup Ba, up.ió p.EA',
(c((T(x))) +
TEll
2
2
Ar.t
(8ā((((2))) + Aree 2 )
I sup p.EA/p
Ba
sup
((((T(()))) +
+ sup Fell
TEll
2
sup (202, (T (x;))) Am.i)
sup Banpie P.EA/b
sell
D Proof of the final step condition
Lemma 10. The relaxation function 44 satisfies the final step condition ②
Proof. By setting T in our relaxation (EI(( and definition of our unbiased estimator of
Ct
T
Eg.r [ = Eg.rr
sup mell
(x(xT))
r=1
sup
- E
Σ (x((x)))
*ell
sup xell
()((x)))
16


Reviews:
[{"review_id": "lecoWqnN5A", "reviewer": "Reviewer_D6vD", "summary": "This paper proposed a new algorithm for Oracle-Efficient Adversarial Contextual Bandits that achieves the best known regret bound and improve upon the previous best bound in its dependency on the action set size $K$.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The algorithm is elegant. The paper is well-written and pleasant to read. The theoretical result is sound. ", "weaknesses": "The theoretical results are sound, but I believe for any work that make effort towards some type of computational efficiency, oracle-efficiency being one of them, experimental evaluation is always appreciated. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are glad that you found the paper well-written and that you believe our algorithm is elegant.\nPlease find below our response to the questions and comments mentioned in your review.\n\n> any work that make effort towards some type of computational efficiency ... experimental evaluation is always appreciated.\n\nOur main focus on this paper was\non the theoretical aspects of the problem.\nWe note that the other existing works for adversarial contextual bandits\n(Rakhlin and Sridharan, 2016; Syrgkanis et al. 2016a, Syrgkanis et al., 2016b),\nalso do not present experimental evaluation. Given the similarities between our\nframeworks, we intuitively expect our algorithm to outperform Bistro\n(Rakhlin and Sridharan 2016) and Bistro+ (Syrgkanis et al. 2016b) in practice\nsince our main difference is in the construction of the relaxation function and\nwe reduce the variance of the Rademacher vectors in each round.\nWe agree however that exploring the practical challenges of the problem and comparing\nalgorithms designed for different settings (stochastic, adversarial, bounded difference, non-stationary, ... )\nis an important direction for future work and will further emphasize this point in the conclusion section.\n"}, {"review_id": "zLqmxbZQJq", "reviewer": "Reviewer_yx68", "summary": "The paper studies the problem of minimizing regret for online adversarial contextual bandits using an ERM oracle. If one doesn't care about oracle efficiency, then the well known EXP4 algorithm achieves the optimal rate. However, the best previous oracle-efficient result is due to [Syrgkanis et al. '16]. This paper improves a factor of $K^{1/3}$ in the regret for this problem over prior work, where $K$ is the number of arms. The algorithm uses $O(K)$ calls to the oracle in every round.\n\nTheir proof relies on a new relaxation under the relax-and-randomize framework of [Rakhlin-Sridharan] which has reduced variance compared to prior works.", "questions": "I have checked almost all of the proofs of the paper. I had a few questions, ranging from questions on the technical details to more higher-level questions.\n\n1. What is the oracle complexity for prior works? Can some discussion on this be included (if it is interesting)?\n2. What can be done if the learner does not have sample access to the distribution $\\mathcal{D}$? Is learning possible here? EXP4 does not require this additional assumption.\n3. Line 191: what is meant by the \"discretization scheme\"?\n4. Any intuition for what the parameter $\\gamma$ controls? Should we expect any improvements in the final bound with a changing $\\gamma_t$?\n5. While I understand the construction of the relaxation function (specifically the design of $\\epsilon_t$ and $Z_t$), it is still quite mysterious. I see how it is used in Lemma 9. Perhaps the authors could include more intuition on this.\n6. In theorem 6, what is the quantifier over the $x_t$? Are we also taking expectation wrt $x_t$?\n7. writing comment: In Lemma 9, perhaps $\\delta$ should be properly defined. It is defined in the previous lemma, but as is, Lemma 9 cannot be read \"independently\" Maybe state the definition of $\\delta$ before the statements of Lemma 8 and 9?\n8. writing comment: In appendix, you write Theorem 4, but in the main text, it is stated as Lemma 4.\n9. In line 398, the derivation here could include more explanation.\n10. line 403: \"We reiterate that each $p_t(i) \\le \\gamma$\" I thought by construction we had $p_t(i) \\le \\gamma/K$, so we can't put $\\gamma$ mass on any arm $i\\in [K]$ (as stated in line 211). Am I missing something here?\n11. line 432: I did not understand why the probability of $\\hat{c}_t$ taking the value $Ke_i/\\gamma$ is at most $\\gamma/K$. By Eq (6), don't we have the probability is at least $\\gamma/K$?\n\nMore speculative, for my own understanding:\n- Do you think that this relax/randomize strategy has limitations? It seems like we cannot substantially improve this bound to get $\\sqrt{T}$-style regret.\n- Can the arguments from [Hazan-Koren '16] be used to get lower bounds against oracle-efficient algorithms?\n- Superficially, the guarantee that you get seems to be what one would expect if they adapted a \"PAC\" algorithm that got $K/\\epsilon^2$ sample complexity using an online2batch conversion (of course, here in the adversarial setting \"PAC\" doesn't make sense because the costs are adversarial). Does this hint at a limitation of oracle-efficient algorithms?", "limitations": "None.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is exceptionally well written. The problem statement, relationship to prior works, explanation of the main contributions, and technical aspects of the proof are all very clear. As such, it was easy for me to follow and understand.\n- The relaxation function that is used to improve the dependence on $K$ seems to be novel.\n", "weaknesses": "- The only weakness is that I'm not sure how significant the contribution/impact of the paper is: it only amounts to a $K^{1/3}$ improvement in the regret. There is still a substantial gap between the upper bound and lower bounds. The paper also doesn't really touch upon whether their rate is improvable for oracle efficient algorithms (we know EXP4 attains the optimal regret if we don't care about oracle efficiency), potentially hinting at some sort of separation result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\nWe are glad that you found our paper to be \"exceptionally well written\". \nPlease find below our response to the questions and comments mentioned in your review.\n\n**Questions**\n\nQ1: The oracle complexity is equivalent to that of Syrgkanis et al. 2016 and\nour main result is in the improved relaxation, not the leveraged\noracle. We will make this more explicit in the final version of our paper.\n\nQ2: Currently our techniques rely on knowing D for constructing the\nhallucinated reward vectors and it is unclear if this can be easily relaxed. We\nbelieve that obtaining results that relax the assumption, even with a\npotentially worse regret rate, is an interesting direction for future research and will\ndiscuss this in the conclusion section (see also \"Relaxing the assumption of the setting\" in our general response).\nWe note that the sampling access assumption is also made in both of the papers\nthat operate in our setting (Rakhlin and Sridharan, 2016; Syrgkanis et al.\n2016). \n\nQ3: Discretization here refers to the approximation of a continuous set\nwith a discrete set (e.g., see chapter 8.2 in Slivkins (2019)).\n\nQ4: The main purpose of $\\gamma$ is to ensure that each arms is pulled with some\nnon-negligible probability and, through Equation (3), the parameter intuitively\naffects the variance of the rewards. Our current techniques do not seem to\nbenefit from varying $\\gamma$ with time as we require the same bound on the variance of\nrewards through time.\n\nQ5:\nWe will expand on the intuition of these variables\nfor both our novel aspects and the aspects based on prior work\nin our revision.\nDue to the space constraints of the rebuttal, we focus on the novelty aspect here.\nThe intuition of the change has two parts: the admissibility of the change\nand why it helps obtain a better regret bound:\n- Admissibility: The main intuition for why only a single Rademacher variable is sufficient\n  for ensuring admissibility\n  is that the symmetrization step of the Relax and randomize framework\n  applies only to a single (random) action (see Lines 440-443 as well as the LHS\n  of Lemma 9). Applying noise to all the entries leads to valid upper bound (as is done\n  by prior work), but is not tight.\n  The main reason these works apply this bound is (in our understanding) that the distribution\n  of the noise is not known (as it depends on $c$ and the algorithm), and therefore they\n  take the upper bound of applying it everywhere.\n  Our main insight here is that knowing this distribution is not necessary.\n  Since the variance of the reward vector is maximized when\n  $\\hat{c}_t$ is largest, we can effectively consider the case of $c_t$ taking its\n  maximum value (as formalized in lines 273-277).\n  Focusing on this case however, the distribution of $\\hat{c}_t$ is known because,\n  regardless of what $q_t$ is, it takes the value\n  $K\\gamma^{-1}e_i$ with probability $\\gamma / K$ (see Equation 3).\n- Why it helps: The reason the change helps can be seen by looking at the LHS of Theorem 6.\n  Consider fixed values for $Z_{1:T}$.\n  If we put random noise on all the coordinates, then the supremum\n  leads to a policy function $\\pi$ that assigns $x_t$ to coordinates\n  with noise values equal to 1. By restricting the noise, we are restricting\n  the power of the supremum.\n\nQ6: The values of $x_t$ are fixed; since the claim holds for any fixed $x_t$, it also\n  holds for a random choice of $x_t$ by iterated expectation.\n\nQ7, 8: Thank you for pointing out these issues; we will apply your comments in the revised version of our paper.\n\nQ9: The rewrite is more easily seen by recalling the definition of\n$q_t^*(\\rho_t)$ from line 213 and expanding the expectation while substituting\nthe equation on line 201 for $R((x, c_t)_{1:t}, \\rho_t)$ and further leveraging\nthe definition of $\\psi_i$ from line 397. We will expand on this substitution\nof variables for the full version of our result to be more clear.\n\nQ10: Thank you for pointing out this typo. The upper bound on $p_t(i)$ should be $\\gamma / K$ as you correctly noted.\n  We will fix this in our revision.\n\nQ11: Equation 6 ensures that the action $i$ is chosen with probability at least $\\gamma/K$. However,\n  choosing the $i$-th action does not necessarily lead to $\\hat{c}_i$ being set to\n  $Ke_i/\\gamma$ however because of the extra noise in Equation (3).\n  Given this Equation, the probability of $\\hat{c}_t(i)=Ke_i/\\gamma$ for\n  $\\hat{y}_t \\sim q_t$ equals $c_t(i) \\gamma/K$ which is at most $\\gamma/K$ given\n  $c_t(i) \\le 1$.\n\nLower bounds / Limitations of oracle-efficient algorithms:\nOur intuition is similar and\n  it seems to us that at least the existing techniques used for relax and randomized are insufficient\n  for improving the bound.\n  While we were not able to prove any improved lower bounds, we consider this to be an important direction for future work and\n  we agree that the arguments from [Hazan and Koren] are a\n  good starting point for exploring this direction.\n  (see also \"Gap between upper and lower bounds\" in our general response)\n\n**Weaknesses**\n\n> not sure how significant the contribution/impact ... only amounts to a $K^{1/3}$ improvement in the regret\n\nPlease see \"Importance of the improvements\" in our general response.\n\n> There is still a substantial gap between the upper bound and lower bounds … potentially hinting at some sort of separation result.\n\nPlease see \"Gap between upper and lower bounds\" in our general response.\n\n\n"}, {"review_id": "mtwoCn16Bs", "reviewer": "Reviewer_gZc2", "summary": "In this paper, the authors consider a classic contextual bandit problem with adversarial loss and stochastic context. Specifically, they proposed a relaxation-based algorithm which achieves $O(K^{1/3}T^{2/3}\\log^{1/3}|Pi|)$ expected regret bound, improving upon the best known $O(K^{2/3}T^{2/3}\\log^{1/3}|Pi|)$ obtained by Syrgkanis et al., 2016 under the same assumption. The algorithm is oracle-efficient, which requires $K+1$-number of call to the ERM oracle. The main improvement upon the algorithm proposed in [Syrgkanis et al., 2016] is a new relaxation expression. Specifically, they replace the random vector $\\epsilon_t$ with all entries a Radamacher random variable by a random vector with a uniformly chosen entry being the Radamacher random variable. The reason for this improvement I think is due to the fact that the loss for each action has a uniform $\\frac{\\gamma}{K}$ probability to be observed and recorded in the loss estimator construction, which is missed in the construction of [Syrgkanis et al., 2016].", "questions": "- I wonder whether it is possible to further generalize this relaxation-based algorithm to achieve $O(\\sqrt{T})$ type result?\n- In addition, the current algorithm requires fresh samples of the stochastic context distribution, which is the same as what is assumed in [Syrgkanis et al., 2016]. I wonder whether it is possible to remove this assumption, since in some applications, this assumption may not hold.\n", "limitations": "See Weakness and Questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper considers a classic contextual bandit problem with a provable better theoretical guarantee in the expected regret bound.\n- The writing of this paper is clear.\n- The proposed algorithm is clear, which is mainly based on the relaxation-based algorithm proposed in [Syrgkanis et al., 2016] but with a better construction on the relaxation function $Rel$.\n- The proofs also look correct to me. Although the modification compared with [Syrgkanis et al., 2016] is not that much, the new construction on this relaxation function looks interesting to me.", "weaknesses": "- One concern is the significance of the obtained results. Compared with [Syrgkanis et al., 2016], the improvement is a factor of $K^{1/3}$. Although the author argued that this improvement can be significant when considering continuous action space with a discretization, I think the order on $T$ may be more important. The main difficulty from obtaining the $\\sqrt{T}$ regret bound seems to be the fact that the loss estimator is meaningful only when the algorithm explore, which also appears in the BISTRO+ algorithm proposed in [Syrgkanis et al., 2016].\n- Minor part: I think the algorithm actually does not require the context distribution to be known but instead require sampling from the context distribution. So I think the abstract description is not accurate, meaning that the result is stronger.\n- Minor typo: \n(1) Line 160: minimizes -> minimize\n(2) Line 266-267: missing a right bracket\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are glad that you found the writing of our paper to be clear.\nPlease find below our response to the questions and comments mentioned in your review.\n\n**Questions**\n\nQ1: We note that \n  the regret lower bound of $\\sqrt{TK\\log(|\\Pi|)}$ holds for all (not necessarily efficient) algorithms.\n  It is not known whether such a regret bound can be obtained efficiently\n  as oracle-efficient algorithms\n  do not always obtain optimal regret rates (Hazan and Koren, 2016).\n  Whether or not this is the case for our problem remains an open problem.\n  We will further expand on our discussions of this point in the conclusion section.\n  (see also \"Gap between upper and lower bounds\" in our general response)\n\nQ2:\nOur focus on this paper was improving the existing regret bounds in\n  the setting based on prior work as the problem is already difficult.\n  We agree however that the mentioned relaxation of the assumption is an interesting direction\n  for future work and will add a discussion in the conclusion section for our revision.\n  (see also \"Relaxing the assumption of the setting\" in our general response)\n\n**Weaknesses**\n\n> One concern is the significance of the obtained results,\n\nPlease see \"Importance of the improvements\" in our general response\n\n> I think the algorithm actually does not require the context distribution to be known but instead require sampling from the context distribution\n\nThank you for pointing this out. This is correct and we will further emphasize this in the paper.\n\nTypos:\nThank you for pointing out the typos; we will fix them for our revision.\n\n"}, {"review_id": "VFFN0rv2q8", "reviewer": "Reviewer_2pq4", "summary": "This paper investigates the contextual bandit problem where the contexts are sequentially sampled from a known i.i.d. source, and losses are generated adversarially. The primary focus is on developing oracle-efficient algorithms that minimize the expected regret (the expectation over both the context's randomness and the algorithm's internal randomness). Specifically, the paper demonstrates that for any finite policy set $\\Pi$ with an value-ERM oracle (capable of finding the minimal policy loss given any sequence of losses), one can achieve an oracle-efficient regret bound of the order $T^{2/3}(K\\log|\\Pi|)^{1/3}$, where $K$ is the number of arms. This finding surpasses the previous bound of  order $(TK)^{2/3}(\\log |\\Pi|)^{1/3}$ in Syrgkanis (2016).\n\nThe proof technique essentially follows the relaxation-based argument from Rakhlin and Sridharan (2016) and Syrgkanis (2016). However, a distinguishing feature of this paper is the introduction of novel Rademacher vectors when defining the relaxation. The authors successfully incorporate these new Rademacher vectors into the analysis framework established by Syrgkanis (2016), thereby advancing the current state of the art.", "questions": "I have a couple of questions for the authors:\n\n1. The paper currently focuses on the finite policy set. Could the techniques developed in this paper be utilized to enhance the Rademacher complexity-based bounds, as discussed in Rakhlin and Sridharan (2016)?\n\n2. Could the i.i.d. assumption be relaxed? For instance, could it accommodate smooth adversaries as proposed in Haghtalab et al. (2022)?", "limitations": "No issue with negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strength of this paper is the oracle-efficient regret bound that improves the state of the art. The authors also introduces several new ideas and techniques that is of independent interests.", "weaknesses": "The submission does not seem to have any significant weaknesses. However, I have a few minor comments concerning the presentation:\n\n1. The paper contains several typographical errors, including:\n    - line 1: \"for for\"\n    - line 284: isn't  (ii) follows from the independence of $\\epsilon_t$?\n    - line 394: should be \"Proof of Lemma 4\"\n\n2. It would be better if the authors could reference the corresponding appendix section in the main text where proof is provided.\n\n3. For a more direct comparison with previous bounds, it would be beneficial to consider some specific values for $K$, such as setting $K=T^{\\alpha}$, where $\\alpha<1$. This would provide more tangible examples and help in understanding the practical implications of the bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\nWe are glad that\nyou think our ideas and techniques are of independent interests.\nPlease find below our response to the questions and comments mentioned in your review.\n\n**Questions**\n\nQ1: We initially obtain a \"Rademacher style\" bound (Equation 8 in our paper) in our proofs,\n  but we upper bound this using Theorem 6.\n  The bounds in Equation 8 are similar to the bounds of Rakhlin and Sridharan (Equation 8 in their paper) but\n  do not seem to be directly comparable given the existence of the $Z_t$ term (see Equation 4 of their paper for their definition of $\\mathcal{R}$).\n\nQ2: Our main focus in this paper was improving the existing regret bounds in\n  the setting based on prior work as the problem is already difficult.\n  We agree however that the mentioned relaxation of the assumption is an interesting direction\n  for future work and will add a discussion in the conclusion section for our revision.\n  (see also \"Relaxing the assumption of the setting\" in our general response)\n\n**Weaknesses**\n\n> The paper contains several...\n\nThank you for pointing out these errors. We will fix them for the revised version of our paper.\n\n> It would be better if the authors...\n\nWe agree that this helps improve the readability of the paper and will add the section numbers for the revised version of our paper.\n\n> For a more direct comparison with previous bounds,...\n\nThanks for a great suggestion. By setting $K = T^{\\alpha}$, the suggested\nbounds by Rahklin and Sridharan 2016 and independently by Syrgkanis et al. 2016a\nequal $O(T^{3/4+\\alpha/2} \\log(|\\Pi|)^{1/4})$. This is further improved by\nSyrgkanis et al. 2016b to the ratio of $O(T^{2/3+2/3\\cdot \\alpha}\n\\log(|\\Pi|)^{1/3})$, which has been state-of-the-art before our work. Our\ntechnique guarantees $O(T^{2/3+1/3\\cdot \\alpha} \\log(|\\Pi|)^{1/3})$. For\nexample, putting $\\alpha = 1/2$ yields a vague regret bound of $O(T\n\\log(|\\Pi|)^{1/3})$ for Syrgkanis et al. 2016b, whereas we obtain $O(T^{5/6}\n\\log(|\\Pi|)^{1/3})$ which is still sub-linear for $K = T^{1/2}$ with respect to\n$T$. Moreover, the upper bound of Syrgkanis et al. 2016b hold upon the\ncondition $T \\ge K^2 \\log (|\\Pi|)$, thus their result does not apply if $K =\n\\Omega(T^{1/2})$.\n"}]

Author rebuttal:
We thank the reviewers for their comments.
We here respond to the concerns that were shared by
more than one reviewer.

**Relaxing the assumption of the setting (Reviewers yx68, gZc2, and 2pq4)**

Our focus on this paper was improving the existing regret bounds in
the setting based on prior work (Rakhlin and Sridharan, 2016; Syrgkanis et al., 2016) because the problem is already difficult.
As pointed out the reviewers, the problem setting
can be generalized 
by removing the sample access to the context distribution.
We agree that this is an interesting direction for future work
and we will discuss this in the conclusion section for our revision.

**Importance of the improvements (Reviewers yx68 and gZc2)**

In our view, the improved dependence on the number of arms (i.e., $K$)
is significant because $K$ can be large in many applications
such as recommender systems.
Additionally, the value can be large if the bandit algorithm
is used as part of a *reduction* that defines "fake" or "synthetic" arms for a given
problem.
In our view, for large values of $K$, our improvement can be very significant.
Indeed, if we consider the regime of $K=T^{\alpha}$ as suggested by Reviewer
2pq4, then we can see that our results can still imply sub-linear regret bounds for
$\alpha > 1/2$, while the results in prior work cannot.
Finally, given the importance of obtaining oracle-efficient algorithms as
evidenced by the large body of work (see lines 44-50)
and the lack of progress for the problem after 
the work of Syrgkanis et al. (2016), we consider our result to be significant.

**Gap between upper and lower bounds (Reviewers yx68 and gZc2)**

Currently, there is a gap between the upper and lower bounds known for our problem.
The best upper bound is $O(T^{2/3}(K\log(\Pi))^{1/3})$ as shown by our paper while the best known lower bound is
$\Omega(\sqrt{TK\log(\Pi)})$ which holds
for all (including non-efficient) algorithms. 
This lower bound may not be tight 
for oracle-efficient algorithms however as these algorithms do not always obtain optimal regret rates (Hazan and
Koren, 2016). 
As mentioned correctly by the reviewers, there can potentially be be a strict
separation in the regret rates obtained by efficient and non-efficient
(e.g., EXP4) algorithms for adversarial contextual bandits. 
Whether or not this
is the case remains open.
We briefly discuss this in the end of Section 2 and the conclusion section and will further expand on our discussion for our revised version. 


Meta-review: All reviewers agree that the paper makes a substantial theoretical contribution to an open problem in the area of adversarial contextual bandits.
Decision: Accept (poster)