An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
Authors: Tim van Erven
Jack Mayo
Julia Olkhovskaya
Chen-Yu Wei
Venue: NeurIPS 2025 poster ()
Keywords: Online learning
contextual bandits
linear bandits
Primary area: theory
TL;DR: We present an efficient algorithm for linear contextual bandits with adversarial losses and stochastic action sets.

Abstract: We present an efficient algorithm for linear contextual bandits with adversarial losses and stochastic action sets. Our approach reduces this setting to misspecification-robust adversarial linear bandits with fixed action sets. Without knowledge of the context distribution or access to
a context simulator, the algorithm achieves $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3T\log K}\})$ regret and runs in $\mathrm{poly}(d,C,T)$ time, where $d$ is the feature dimension, $C$ is an upper bound on the number of linear constraints defining the action set in each round, $K$ is an upper bound on the number of actions in each round, and $T$ is number of rounds.  This resolves the open question by Liu et al. (2023) on whether one can obtain $\mathrm{poly}(d)\sqrt{T}$ regret in polynomial time independent of the number of actions.  For the important class of combinatorial bandits with adversarial losses and stochastic action sets where the action sets can be described by a polynomial number of linear constraints, our algorithm is the first to achieve $\mathrm{poly}(d)\sqrt{T}$ regret in polynomial time, while no prior algorithm achieves even $o(T)$ regret in polynomial time to our knowledge. When a simulator is available, the regret bound can be improved to $\tilde{O}(d\sqrt{L^\star})$, where $L^\star$ is the cumulative loss of the best policy.

An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
Tim van Erven"
Jack Mayo
Julia Olkhovskayal
Chen-Yu Wej
Abstract
We present an efficient algorithm for linear contextual bandits with adversar- ial losses and stochastic action sets. Our approach reduces this setting misspecification-roon
adversarial linear bandits with fixed action sets. With- out knowledge of the context distribution access to context simulator, the algorithm achieves Omin VT, / Vd log K}) regret and runs in poly(d, C, time, where d is the feature dimension, C' is an upper bound on the number of linear constraints defining the action set in each round, K is upper bound on the number of actions in each round, and T is number of rounds. This resolves the open question by Liu et al. (2023) on whether one can obtain poly(d)v/I regret in polynomial time independent of the number of actions. For the important class combinatorial bandits with adversarial losses and stochastic action sets where the action sets can be described by a polynomial number of linear constraints, our algorithm is the first to achieve poly(d) (d) VT regret in polynomial time, while no prior algorithm achieves even o(T) regret in polynomial time to our knowledge.
When simulator is available, the regret bound can be improved to (dvTT*) where L is the cumulative loss of the best policy.
Introduction
consider the following linear contextual bandit problem: each round / I,..., T, the environment generates hidden loss vector 0, E Rd and action set A, Rd. The learner observes Ar, selects an action a, E Ar. and incurs loss a, 0,. The goal is to compete with the best fixed policy-defined as mapping from an action set to an element in it. This setting generalizes the classical linear bandit model by allowing the action sets A, to vary stochastically over time, Crucially, each Ar encodes the context based which the learner makes decisions, In this work, A, is called context or action set interchangeably.
This framework is applicable in settings such as healthcare and recommendation systems, where decisions must be made conditional on context. Prior work on contextual bandits has studied variety of assumptions on how losses and contexts are generated. While much of the literature assumes i..dd. losses and arbitrarily chosen action sets (for which a knol- algorithm is LinUCB (Li et al. 2010)), we focus on the complementary regime: the action sets are drawn i.i.d. from fixed distribution D, while the losses may be chosen adversarially.
A first computationally efficient algorithm for this setting was proposed by Neu and Olkhovskaya (2020) under the assumption that the context (i.e., action set) distribution known. Since an action set is a subset of Idd (i.c., it lies in the space 2x") the distribution over action sets is in the space
"University of Amsterdam. Email: cim@timvanerven.nm ml 1 University of Amsterdam; airtos.a. Email:
com Delft University of Technology. Email: jul a o kkovskaya@@maii com 6 University of Virginia. Email: chenyu. wei @vi ng n eddu
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison with state-of-the results in adversarial linear contextual bandits. d is the feature dimension, K' is an upper bound on the number of actions, and C an upper bound on the number of linear constraints to describe the convex hull of each action set. It holds that C - K + 1 and many combinatorial problems we have C poly(d) and K = 20(d), The run time of the linear optimization oracle of Neu and Valko (2014) is bounded by poly(d, C*) but could also be smaller.
Algorithm
Regret (omitting log(dT) factors) vdT for the special case A (e),...,ed)
Computation
Simulator
Feedback
Schneider and Zimmert
2023)
poly(d, 7)
no
handit
Neu and Valko
2014)
(dT)
poly(d, plus
semi-handit
T oracle calls
Dai ct al.
2023
minfdyT, /dT lollogg K}
poly(d, K, T)
yes
bandit
Liu et al.
2023
dvT
K k
bandit
Liu et al.
2023)
d'V min(d' VT, / d log K}
poly(d, K,
no
bandit
Ours
poly(d, C,T)
no
bandit
Ours
dvL'
poly(d,
yes bandit
A A(2*), which is generally intractable to represent efficiently. This assumption was later removed by subsequent efficient algorithms (Luo al. 202 Sherman et al. [023 Dai et al., 2023 Liu et al.) 2023). In the setting where the learner has access to a simulator that can generate free contexts (i.c., the learner is able to sample contexts from D as many times they want without incurring cost), Dai et al. (023) shows that a near-optimal regret bound of Omin (dVT,, VdT log K) K)) ) is achievable, where k = max, |Agl- When the learner has neither knowledge of the context distribution nor simulator access to random context samples, the best known results are by Liu al. (2023): they provide an algorithm with near- near-optimal regret (dd'T) with run time (=(d)) and another algorithm with regret VT) with run time poly(d, K, T). Notably, while the regret bound of this last algorithm is independent of the number of actions K, its computational complexity scales polynomially in K. In fact, this is the case for all previous algorithms as well (Luo et al., [022] Shherann et al. 2023 Dai al. 2023 Liu et al. 2023 2024b). This makes them unsuitable for many important combinatorial problems (e.g.. m7-set, shortest path, flow, bipartite matching), where K is usually exponentially large the dimension d.
Our work gives the first algorithm whose computational complexity does not explicitly scale with the number of actions, making adversarial linear contextual bandits applicable much wider range of problems. Without simulator access, our method achieves regret Ommin(d2VT /d²T log K})
and with simulator access this can be improved to ŌdvL.*) where L, = O(T) is the cumulative loss of the best policy. Our algorithm runs in Odd, C, T) time, where C is the number of linear constraints to describe the convex hull of each action set. Notice that C < + 1 in general, as linear program with most K +
the convex hull of an action set of size K can be written constraints. On the other hand, in many combinatorial problems. C = poly(d) while K = 20()) For example, in a shortest path problem with d edges, the set of all paths can be described by a linear program with (dd) constraints, while the number of paths could be of order 2n(d), For combinatorial problems with stochastic action sets and adversarial losses, we are only aware Ne and Valko (2014) who studied the case where the learner has semi-bandit feedback. Their algorihm achieves O ((dT)//3) regret with one call to the linear optimization oracle of the action set per round. Compared to their work, our work weakens the assumption on the feedback (from semi-bandits to full-bandits) and improves the regret bound, but our method is computationally heavier- are action sets where linear optimization can be solved in polynomial time while having an exponentially large number of constraints, such as spanning trees. How to further improve our computational complexity to match theirs left as future work. It also remains open how to efficiently achieve the near-optimal bound Omin (dvT, VdT log K)) without simulators, even when the learner willing to pay (dly K) computation. This has only been resolved in the special case where action sets

---

are subsets of the standard basis fei...., eu), which is also known as the sleeping bandits problem (Schneider and Zimmert, 2023).
Our result is achieved by establishing novel and computationally efficient reduction from adversarial linear contextual bandits to adversarial linear bandits with misspecification. Linear bandits can be viewed as linear contextual bandits with fixed context and is therefore less challenging than linear contextual bandits. This reduction scheme is related to the work of Hanna al. (2023), which reduces stochastic linear contextual bandits (with both stochastic contexts and stochastic losses) to misspecified stochastic linear bandits. Compared to Hanna al. (2023), we make two key advances: First. our reduction is polynomial-ting ttme, and we also provide polynomial-ting algorithm for the problem we reduce to, whereas Hanna et al. (2023) focus solely on the regret bound and remains open how their reduction can be implemented in polynomial time. Second, we study the strictly more general setting with adversarial losses. more detailed comparison with Hanna et (0023) provided in Appendix A
Finally, regarding results in terms of L*, we remark that our bound of Ö(d/L*) can be specialized the setting of Olkhovskaya et al. (2023) (a slightly different formulation of adversarial contextual bandits). We then obtain a slightly worse rate but, importantly, remove their unrealistic assumption that the context distribution log-concave.
Problem Description and Main Results
Notation Suppose A Rd is set of vectors. Then the convex hull of A is denoted conv(AA)
{z = - A:a; l E N. Σ A 1, 2 0, a, A}. If A is a polytope, we denote its set of vertices as vert(A), and denote the normal cone of A at vertex E vert(AA as Ni u) = E Rd. maxxeA (y. x - u) < 0}.
2.1 Linear Contextual Bandits
For simplicity, we consider an oblivious adversary Before any interaction with the learner, the adversary secretly chooses T loss vectors (ft) where 0r E Rd for all t. For each round iid. 1 1= 1, T, an action set Ar C Rd is drawn according to Ar ~ D and revealed to the learner. The learner then chooses action de Ar and observes loss l E [o, 1] with E, [&] a, Ot, where E, denotes the expectation conditioned on the history up to time 1 and ag. The expected regret against a fixed policy is defined as
T
Regy (T) E
(a- (A)).
where policy т maps an action set A c Rdd to a point क (AA E conv (A) 6 Note that the policy that minimizes the total expected loss is
( (AA), Σ
0, )
arg min E TEN
Σ (m(A)).
arg min EAND TEnl
which is attained by the policy π (AA) = arg min A (a, Er= 0²). Thus, to minimize the expected regret, suffices to compare the learner to the class of linear classifier policies
Tim { To & E [Rd} where (AA = arg min (a, Φ)) aeA
(1)
where ties can be broken arbitrarily.
*There are two kinds results we can get: 1) regret compared to the best policy the full policy set under oblivious adversary, and 2) regret compared to the hest policy in the linear policy set Tha under adaptive adversary. To achieve 2), suffices to use musspecifccttion-rouuss linear bandit algorithms with high probabiiyy bounds in reduction. This can be achieved by standard techniques of getting grob-probbbblityy bounds (Lee)
2020 Zimmert and Lattimore 2002)) ) To simplify the exposition, we only focus on the first case.
Defining ((A) E (Anv(.A) instead of ((A) E A only makes the guarantee more general and simplifies the notation. Equivalently, it defines randomized policy: execute x (A), sample E A such that E/a] = x (AA).
3

---

2.2 Linear Bandits and e-Misspecified Linear Bandits
The adversarial linear bandit problem with oblivious adversary is the case in which the adversary decides (6s (M)) before any interaction with the learner. The learnr is given fixed action set á C R4. At every round E [T], the learner chooses an action Y/: E Ω and receives &t E [0, 1] as feedback with Ee[cr] = (ye, 0z)- The regret with respective to a fixed action y E 5 is defined as
T Σ
Regr (y) =
(we ys 02)
misspecified linear bandit problem is the case where the learner, instead of receiving an unbiased sample of (ye, 0t) as feedback, receives with [R, [cx] (vi, 0²) S for some known to the algorithm.
2.3 Results Overview
In this section, we present a general framework that can reduce the adversarial contextual bandit problem a misspecification-rooe robust linear bandit algorithm defined as the following.
Definition 1 (a-misspecificattion -t robust adversarial linear bandit algorithm). A a-misspecíficatinn robust linear bandit algorithm over action set f C IR has the following property: with a given and the guarantee that every time the learner chooses yt E Q the loss received Ct E [0, 1] satisfies
[B([c]] - (1t, 0.) se
the algorithm ensures
Σ
(ye 0e)
S min Σ (w) +
(2)
Notice that there is an parameter in D that specifies the dependence of the regret on the misspecification level e. It is known that a = the statistically optimal dependence. However, for specific algorithms, we might have > 1.
We establish the following reduction:
Theorem 1. Given access a-miisppeeffcattonn-obbsst adversarial linear bandit algorithm, can achieve min Regr(m) & Ö(dvT aog K)) in adversarial linear contextual bandits without access to a simulator.
We remark that the ad Tog K term in Theorem comes from the misspecification term a deT in (2). When the learner has access to a simulator that generates free contexts, the can be made arbitrarily small, allowing us achieve the optimal dependence. This will be discussed in Section
3 Reduction from Linear Contextual Bandits to Linear Bandits
Let ग denote a policy, which maps any given action set AA to randomized action in conv(A). Let II denote the of all possible policies. We define the following map
(() (x))(=(AA)),
which is the mean action n. Applying Y to all म E II, the set = (V(T)) æ E 11) is induced. Note that, under this map, the expected loss under actions drawn such that E [a, (AA) may be written as
Ka, 0.)] EA,-D (A.)),, 0.1] (V))).))))
Accordingly, if the learner draws a, from policy स. in round t, the expected regret may written as
T
T
(T) E
Σ (a: T (A.),
=
Σ
(m. - (AA),,
= E
(v)))) ((T)...))

---

3.1 Approximating ?
Since cannot be accessed directly without full knowledge of the context distribution D, we cannot work with & directly. Instead, we will therefore approximate f by its empirical counterpart Q based from D:
on N iid. samples
N
② ((())
ZEERR
dj a, conv(Ai), aj when Ai = -
(3)
where (T) = E (AA).
We proceed to show that the empirical cumulative loss of any linear classifier policy on the sample A AN is close to its expected cumulative loss, as long as N is large enough:
Lemma 1 (Uniform Convergence), Consider any loss vector E R. and suppose that |A| S K and max (a, 1)| I b almost surely. Then, for any 5 E (0.1) uniformly over all linear classifier policies nh the difference in performance of as on the sample AI...., AN and its expected
performance is at most
2dln(NK2 N
2 In (4/6)
sup
(V(T)) (b())), =bb 2
+bV
dERd
N
with probability al least 1 - 5.
The proof is provided in Appendix C Its key idea is to rephrase the result as an equivalent statement about uniform convergence for linear multiclass classifiers with K classes in the batch setting, with an unusual loss function. We can then obtain a concentration inequality that holds uniformly over all linear classifiers using standard tools. Specifically, go via Rademacher complexity and bound on the growth function the class multiclass línear classifiers in terms of its Natarajan dimension, which is known to be at most d.
3.2 Connection between Linear Contextual Bandits and Linear Bandits
Algorithm 1: Adversarial Linear Contextual Bandits
Input: An adversarial linear bandit algorithm ALG and set Sx of N action sets drawn from D. Initiate an instance of ALG over action set Ω constructed from Sy.
2
3 for marl=1 1,.,.... do Obtain Yr from ALG.
Find distribution a E A ((ver(([t)) such that Exp-, [+]] y/-
Sample ti ~ a and let de be an arbitrary element the interior of -N(Ω,, v/e). Receive action set Ar, choose action arg minge (a, Φr), and receive loss la E [0, 1].
Send &, to ALG.
The procedure that reduces linear contextual bandits to linear bandits outlined Algorithm We also provide a visual illustration ②2 and the main variables in the algorithm in Figure In the following discussion, let assume for simplicity that the learner has perfect knowledge of Ω
ie., assume for now that Ô = Ω. Then, according Section 3 we can view the problem as linear bandits over Ω < d But when the linear bandit algorithm tells us to sample point E S2 what corresponding policy π. should we use order to guarantee that (m;) = EE IT. (AA] yt? This might be theoretically achievable if we knew D exactly, but even then the support of D might be too large to make this computationally tractable. following Lemma 2 In Lemma 2 we assume that D has finite support and thus Ω is polytope with a finite number of vertices. However, we do not really need this assumption our setting, }. which naturally has a finite support, and the set Ω built on it according to 3p. The error between the empirical distribution D and the true distribution D will be analyzed in Section 3.3
resolve this, we make a key observation stated the
as we will eventually apply Lemma 2 on the empirical distribution D = Uniform{AA......
5

---

# (G.
Y'
Figure 1: Illustration of Q ye, thr and the normal cone -N 1/)..
Lemma Fix any finite-uuport action-set distribution D and its corresponding linear bandit feasible set Ω (EAAD[[(AA) all possible policies T)- For any vertex db of Ωt can find linear classifier policy Te such that E (o( = vb. In fact, this holds for any interior point o of -N(2, 1)).
Proof of Lemma Let tb be vertex of Ω and ø be an interior point of -W(S, v)) Then there exists such that for any v/ E S2 vi
+ th (v/ - v, Φ) > O.
Let + = EAND [AA), and let æ be a policy that ab corresponds to under distribution (i.c., (AND] = .)) Then
min (a (aT BAND [=(A) Ø] (1,
(5,0) 0 EAND (A), .)) BAND
aEA
Thus, it must be that vp- = vb. This finishes the proof.
Based on Lemma 2 we have the following strategy to execute Yt- First, decompose yt as convex combination of extreme points Q i.e., decompose Y/ as Σ, a,t4; where 1/1, t/2,... ... are vertices of f2 and (01, .. is a distribution over them. Then for each thi find the corresponding Φi E -V v) according Lemma 2 Finally. let n, be the policy that mixes Toi To2s.... ... with weights (a), (2, This way, we have by Lemma
Σ OU (A)
= Σ ai RRRBAND (A)) = Σ aath Vt-
EAND (m) = AADD
This allows us execute policy n. such that BAND[TT(AA) = Ye without explicit knowledge of D E A(2*") but only knowledge f2 C Rd. Notice that we do not have perfect knowledge St, but only the estimated feasible set Ω2 However, exactly the same approach can be applied to Ω resulting in the design of Algorithm I
3.3 Bounding the error due to the discrepancy between Ω and Ω
we know how to execute the linear contextual bandit algorithm by leveraging a linear bandit procedure in Ω. However, there are errors due to the discrepancy between Ω2 and Ω which contribute to the final regret.
From Section 3.2
First, the loss estimator constructed will be biased. Suppose that D is the empirical distribution based on N action sets that are drawn independently from D, and ② is constructed from them based on When we sample a point V1 Ω and execute the corresponding policy m, such that Vt E A Te (A)), the expected loss the learner observes is EAwD (F (A), a (yt, 0z). This

---

means that from the viewpoint of the linear bandit problem on Ω. the feedback is misspeciffed. This motivates us develop a misspecification robust linear bandit algorithm (Definition I which allows the feedback to not fully follow the standard linear bandit protocol. We elaborate more about this in Section 3.4
The second source of eπrоr comes from difference between the action sets S2 and Q. With the misspecification-rouus linear bandit algorithm on S2, the learner has good regret bound on f2 However, the real regret we care about is on Q. This requires us to bound the difference between the two regret definitions:
Real regret on ! that care about: EA~DI( 0.) - EANDl(T(A 0c)l
Regret on it that the robust linear bandit algorithm can bound: E (A) 0.)] - E E 0.)
Both errors
discussed above can be related to the difference sup, | A-D (A(A), 0.) - END (A), 0-]]- This can further be bounded using Lemma
where we establish uniform convergence over the set of all linear policies. According Lemma we have with probability at least 1 5, for all linear policies n.
dlog([VK/o) N
E AND (A), 0.) - EAND (A)), VV
This allows to bound the two sources of errors mentioned above.
3.4 Robust Linear Contextual Bandits
we would like to develop a linear bandit algorithm that tolerates misspecification. Although there is rich related literature, most prior results for the stochastic linear bandit problem and do not apply here. For adversarial linear bandits with misspecification robustness, we only aware of the work by Neu and Olkhovskaya (2020) and Liu et al.) (2024a). However, the bound in Neu and Olkhovskaya (2020) has worse T2/3 regret, while the algorithms Liu et al. (2024a) are either computationally inefficient or highly sub-optimal. Fortunately, our problem is slightly easier than that studied by Liu et al. (2024a), our learner has knowledge of the amount of misspecification c, and this amount remains the same in all rounds. This allows us to design the computationally efficient Algorithm 2 with improved dependence the amount of misspecification.
As discussed in Section 3.3
Algorithm 2 is adaptation of the clipped continuous exponential weight algorithm if et al. (2020): The de in Line 3 Algorithmm2is is the standard continuous exponential weights, while the q. in Line 5 confines the support of 9t within ellipsoid centered around the mean. This is helpful in obtaining a first-order bound (Ito et al., 2020). Sampling from 9e can be done with standard techniques for sampling from log-concave distribution (to sample from q:) plus rejection sampling (to correct the distribution to q:). which admits a poly (d, T) computational complexity, provided that we have access to an efficient linear optimization oracle for Ω. See Ito et al. (2020)'s 's Section 4.4 for a discussion on the computational complexity. We discuss how construct such an efficient linear optimization oracle with poly(d, C)T) computational complexity in Section
The key addition compared to (Ito et al.) 2020) is the bonus term b, that ensures misspecification robustness. This bonus encourages additional exploration, preventing the learner from being misled by misspecified feedback. The form of the bonus for adversarial linear bandits was first developed in the series of work (Lee et al.) 2020 Zimmert and Lattimore 2022) aimed at obtaining high- probability bounds. Our use of the bonus is similar to Liu et al. (2024b), which tackles corruption and misspecification. In the regret analysis, this bonus term creates a negative regret term that offsets the regret overhead due misspecification.
The guarantee of Algorithm 2 is given in the following theorem.
Theorem 2. Algorithm 2 is /ddmisppectfecation--obbe robusst linear bandit algorithm defined in Defini-
tion 7
We remark that while there exist algorithms that are 1-misspeciffcttion-robss (Liu et al. 2024a). their run time scales at least with the number of actions. Aggorithmmaaccie acchieee a-robustness with the smallest are aware of among algorithms that run in poly(d, C,T") time.
7

---

Algorithm 2: MisspeciiicatioonRRouus Continuous Exponential Weights
Parameters: 7 10 (10dT) T
for i = 1.2...., do
Define
-11 11,0, -br))
exp
(v(v)=
at Ey Ee Ey 1ov.l(1 zz)(y) 21)
In exp
(-1Erer (2,0r bz)) dz
Define
(r(w)= ( 111 zel1 xT1 S dr2)
E. Ey Lirvill--aue xx) xx)
Ja (x)II || z بل S dy2 [ dz
Sample yt q. and receive loss c E [0. 1].
Define 0. (BI Σt) (5,)"1 (yc - 21 21)a and bt = 8nj (e 7t) Er b,).
In fact, Algorithm aatiieeeeee
favorable small-loss regret bound, which be leveraged to obtain a small-loss bound for linear contextual bandits when the simulator is available. We discuss this in Section 5
3.5 Combining Everything and Using the Doubling Trick
Combining everything above, we are able to establish the regret bound for the linear contextual bandit problem. The proof of the following theorem is in Appendix [.2]
Theorem 3. Algorithm
7 with ALG instantiated as o--misppeeffccation-rbue linear bandit algo-
rithm ensures
Σ (m(()))..) +o ddTT (OTTT+ oTdy
(og(NKT)) N
E
(at 0x) min E sEll
Corollary 1 (Restatement of Theorem D. Given access to a a-misspecifectiion-bbbee adversar- with doubling trick achieves max+en Regr(m) s
ial linear bandit algorithm ALG, Algorithm !
ÓddT + add/T K) in adversarial linear contextual bandits without access to simulators.
Proof. We will use the doubling trick and restart Algorithm at times 2, 4,8, 16, ... each time using the contexts received so far to estimate Ω. Thus, in the k-th epoch, Q constructed by N O2* contexts, allowing us to bound the regret in epoch i as
ò dv22 a2
(NT(N Ō (dv22 + ady 2 log( KT)
2
using Theorem
Summing the regret over all epochs allows us to bound
IoRa
(d + ad log(K)T) Ö (dvT ad oTg log
max Regy HEll
By instantiating ALG Algorithm 2 (which an -u-miispecifiaatoon-ouuuu algorithm by The- orem 2) and invoking Corollary we get the final regret bound as ((vdBT log K). As we can assume K < dd without loss of generality (any action set can be discretized into no more than dd points and incurs a negligible regret of d/T due to discretization error), the regret bound can be further improved to Óminn 2 /T, / d log K)).

---

4 Computational Complexity
In this section we discuss how to construct the poly(d, C, N) time linear optimization oracle needed in Section 3.4 to make Seoorithm@efficieee we also consider two steps from Algorithm [] lines 5 and [6] for which it is not obvious how they can be implemented efficiently. We will describe an approach to implement both steps in poly(d, C, N) time, provided that conv(A is polytope that can be described by at most C' linear constraints for D-almost all A.
Constructing Linear Optimization and Separation Oracles. By Corollary 14.1a of |Schriyeer (1986) (restated in Lemma 4). we can obtain poly(d, N) time linear optimization oracle for Q from a poly(d, C, N) time separation oracle for f2. We proceed to construct such a separation oracle for f2. To this end, let us assume, without loss of generality, that no two sets A, and A, in the construction of Ω are equal; otherwise we can replace them by a single set 2AA,, which will only decrease N. Thus, Ω2 is the Minkowski sum of N convex polytopes that, by assumption, can all be described by at most C' constraints. For any x E IRd let
g( = TTx x m Φ x''x'= =
Ei= E o xz.
If ((b) > 0 for some o, then @ gives a hyperplane that separates z from Ω and if ((0) S 0 for all ø. then x E f2. Since 9 concave, and we can solve every subproblem mäXx, E.A. o x4 in poly(d, C) time, we can maximize y in poly(d, C, N) time to obtain our separation oracle.
To implement line 5 need to be able to take any point yr E l2 and find a distribution an supported on the vertices of Ω that can sample from efficiently. By Carathéodory's theorem, any yr E Ω can be represented
Implementing line 5 of Algorithm 1
convex combination of at most + 1 vertices of Ω2 y/+ = Σk= 0yy for < d + 1 where all i/ are vertices of Ω. and 01 Og 2 with Σ, oz 1 can be interpreted the probabilities of selecting the vertices. This is categorical distribution on at most d + points, from which we can sample in (dd) time (assuming we have access to oracle that provides samples from the uniform distribution on [0. 1)). Thus the main challenge is to compute the vertices ty and the probabilities og- By Corollary 14.1g) of [Schrijver ( (1986) (restated in Lemma 3). there exists algorithm that do both in time poly h) for any set l given access to a separation oracle that runs in time (h)). As discussed above, we have h of order (oly(d, C, N), from which it follows that we can also find the probabilities on and vertices tn in poly(d, C, N) time.
After the sampling procedure has chosen a particular vertex We E [(u,,..,, ), we need to find an interior point of the corresponding normal cone - v/x) in line 6 To achieve this, suppose are given vertex t/2 E Ω. By Lemma 5 there exists unique N E H3 where x; is a vertex of (AA) for all i E [N]. We can find {z, JaiNie by solving a linear program with O(CC) constraints: E (onv(A,) for all i E [N] and I
Implementing of Algorithm 1
decomposition th 1
+ Fi = v/2
N
Let Nr N (conv(A)) 2.) be the normal cone of con)(A:) at the vertex x,. It is the conic hull of
the active constraint normals: M₁ = cone(T) (Tx = (Euer, di,u Ai, 2 0 for all u E T.), where T is the set of normal vectors corresponding to the constraints u. x + S 0 that are active at ay T can be constructed by enumerating all constraints of conv(A,) and checking which are tight at a.
By Lemma (â, vb) = DEEINI M. MG To find a point strictly inside -V((2, 1/), we solve the following linear program with O(NC)) constraints:
max EER, ARR 0ER4
subject to & = Σ Ninu for all E [N],
(ø E -N; for all i)
uET
8 < Ai, 51 for all i E [N] and u E T. (Make ò bounded and strictly inside -N))
By the assumption that th, is vertex, (② wh) always has an non-empty interior. Therefore, solution with E >> 0 exists, and the optimal è provides desired interior point.

---

Small-Loss Bound with Access to Simulator
The sub-optimal rate VT obtained in Section comes from the misspecification term a deT in the regret bound of robust linear bandits (Definition Dp. While it is unclear how to further improve C, we demonstrate the power of our reduction by further assuming access to simulator: not only allows bound d- T.* when losses non-negative, where T. the cumulative loss of the best policy.
recover the minimax optimal regret dyT T but also allows
obtain a first-order
By the black-box nature of our reduction, what we additionally need is just a misppecificationn-rbuus linear bandit algorithm with small-loss regret bound guarantee, formally defined as follows:
Definition (a-mil ce-misspecification -orbuuutttooouuuutttt adversarial linear bandit algorithm with small-loss bounds).
A misspecification-rebee robusst linear bandit algorithm with small-loss bounds over action set S C R has the following property: with given O and the guarantee that every time the learner chooses Yt E St the loss received Ct [0, satisfies [Ra[ce] (yy, 0x)
S c, the algorithm ensures
E
(ul, 06)
I min DEn?
w 01) +Ō d
Σ yy 02) +av
(5)
The next theorem shows that Algorithm 2 satisfies Definition with = Vd.
Theorem 4. Algorithm 2 is Vi-misspeciiicaation-oooa linear bandit algorithm with small-loss bound defined in Definition 2
With access misspecificattinn-robuss linear bandit algorithm with small-loss bounds, we have Theorem 5. Given access to simulator that can generate free contexts, and access to an a- misspecification-rrbuss udversarial linear bandit algorithmm with small-loss regret bound guarantee, we can achieve min E [Regr s O(dvL=) in adversarial linear contextual bandits, where
T
L min E sell
Σ
(T(()))
is the expected total loss of the best policy. This is achieved with ( calls to the simulator.
The proof of Theorem 5 is very similar to Theorem 3
except that now, with access to the simulator, we are able to make in Theorem large enough that the second term in Theorem 3 is negligible. We provide the omitted proofs in Appendix
Conclusion and Open Questions
We have provided general framework that reduces adversarial linear contextual bandits to misseciification-rouust linear bandits in black-box manner. It achieves (dd2 regret with- out simulator, and is the first algorithm we know of that handles combinatorial bandits with stochastic action sets and adversarial losses efficiently. The requirement of misspecification robust- ness stems from our need to use an approximate feasible set Ω because we do not have direct access to the exact feasible set Ω which depends on the action set distribution D.
Three open questions left by work: First, the computation match that of Neu and Valko (2014), who only require a linear optimization oracle for each action set, and do not require a polynomial number of constraints? Second, can the regret be further improved the near-optimal Ö (dvT) bound with a polynomial-tine algorithm without simulators? Third, can we achieve poly(d) (d)v L regret without simulator? For the second question, one may try to generalize the approach of Schneider and Zimmert (2023). For the third question, one idea is to establish Bernstein-tye counterpart of Lemma] potentially drawing ideas from Bartlett et al. (2005 Liang
be improved further to
et al. (015))
We expect that our approach has wider applications than adversarial linear contextual bandits. For example, our approach may be generalized to linear MDPs with fixed transition and adversarial losses
(Luo et al., 2021; [Sherman et al.) 2023) Dai et al.) 2023] Kong al., 2023 Liu al. 2024b) and facilitate learning with exponentially large or continuous action sets.
10

---

Acknowledgments and Disclosure of Funding
Mayo and Van Erven were supported by the Netherlands Organization for Scientific Research (NWO) under grant number VI. Vidi. 192.095.
References
Bartlett, L., Bousquet, O., and Mendelson, (2005). Local rademacher complexities. The Annals of Statistics, 33(4): 1497-157.
Bubeck, S. and Eldan, (2015). The entropic barrier: simple and optimal universal self-concordant barrier. In Conference Learning Theory, pages 279-279. PMLR.
Dai, Y., Luo, H., Wei, C.-Y., and Zimmert, J. (2023). Refined regret for adversarial MDPs with linear function approximation. In International Conference Machine Learning, pages 9726-6759) PMLR.
Hanna, O. A.. Yang, L., and Fragouli, C. (2023). Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In The Thirty Sixth Annual Conference on Learning Theory, pages 1791-1821. PMLR.
Ito. S., Hirahara, S., Soma, T., and Yoshida, Y. (2020). Tight first-and second-order regret bounds for adversarial linear bandits. Advances in Neural Information Processing Systems, 33:2028-20333 2033..
Kong, F., Zhang, X., Wang, B., and Li, S. (2023). Improved regret bounds for linear adversarial MDPs via linear optimization. Transactions on Machine Learning Research.
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. Advances in neural information processing systems, 33: 33:15522-15533
Li, L., Chu, W., Langford. J., and Schapire, R. E. (2010). A contextual-band bandit approach to personalized news article recommendation. In Proceedings the 19th international conference World wide web, pages 661-670.
Liang, T., Rakhlin, A., and Sridharan, K. (2015). Learning with square loss: Localization through offset rademacher complexity. In Conference on Learning Theory, pages 1260-1285. PMLR.
Liu, H., Tajdini, A., Wagenmaker, A., and Wei, C.-Y. (2024a). Corrutiion-robust linear bandits: Minimax optimality and gap-dependent misspecification. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.
Liu, H., Wei, C.-Y., and Zimmert, J. (2023). Bypassing the simulator: Near-optimal adversarial linear contextual bandits. Advances Neural Information Processing Systems, 36.
Liu, H., Wei, C.-Y., and Zimmert, J. (2024b). Towards optimal regret in adversarial linear MDPs with bandit feedback. In The Twelfth International Conference on Learning Representations.
Luo, H., Wei, C.-Y., and Lee, C.-W. (2021). Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931 22942.
Natarajan, B. K. (1989). On learning sets and functions. Machine Learning, 4:67-97.
Neu, G. and Olkhovskaya, (2020). Efficient and robust algorithms for adversarial linear contextual bandits. In Abernethy, J. and Agarwal, S.. editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3049-3068. PMLR.
Neu, G. and Valko, M. (2014). Online combinatorial optimization with stochastic decision sets and adversarial losses. Advances in Neural Information Processing Systems, 27.
11

---

Olkhovskaya, J.. Mayo, J., van Erven, T., Neu, G., and Wei, C.-Y. (2023). First-and second-order bounds for adversarial linear contextual bandits. Advances in Neural Information Processing Systems, 36.
Schneider, J. and Zimmert, J. (2023). Optimal cross-learning for contextual bandits with unknown context distributions. Advances in Neural Information Processing Systems, 36:51862- 51880.
Schrijver, A. (1986). Theory of Linear and Integer programming. Wiley-Interscience.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Sherman, U., Koren, T., and Mansour, (2023). Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference on Machine Learning. pages 31 117-31 150. PMLR.
Weibel, C. (2007). Minkowski sums of polytopes: combinatorics and compulation. Phl) thesis, éicole Polytechnique Fédérale de Lausanne.
Zimmert, J. and Lattimore, T. (2022). Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference Learning Theory, pages 2285-3312. PMLR.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims made in the abstract and introduction either have formal proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations and trade-offs for our results compared to the state-of-the-ar are provided in Table and the introduction. Computational efficiency is discussed in Section 4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

all theorems are backed up by formal proofs, either in the main paper or in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This is theory paper without experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[NA]
Justification:
The paper does not include experiments requiring data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips... cc/
pub i gui Codeeubmies aasionooliii icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/
wwwbliccguideee / //odiddee/Cdeeeeeeee Cooeeeooeeeeeeeeee SodeSuumiiee Swwmissiiiii wsssnoooiccyyyyooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://s///rrrssss..c/pppll////a l
Answer: [Yes]
Justification: This is theoretical work, which did not require human subjects or participants, and involved no data. It contributes to the fundamental understanding of contextual bandits, without any direct foreseeable negative societal impact. Mitigation measures were therefore not applicable.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This is theoretical work, which contributes the fundamental understanding of contextual bandits. The long term societal impact is too unpredictable to provide meaningful discussion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaettettt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
The method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ht /tte:///neuripa http://ppppp.ccoooofeeeeeee////p 2025/ LLM) for what should or should not be described.
19

---

A Comparison with Hanna et al. (2023)
Our work and Hanna et al. (2023) both reduce linear contextual bandits to linear bandits with misspecification. The linear bandits the two works reduce to are slightly different. For comparison, let AI,.... AN be empirical action sets drawn from D, and define
= { (T) T II.
Duin - {M(TT π Unn 1im).
- ( Mim (6)
where (TT) - & Σi π (Ai), Ihi the set of linear policies defined ( and
- To Φ e-net of the unit ball in R=).
holds that D2in C San 5 because fi C Iln C II. The relation among the three sets in (6) is the following: Qin is the boundary of ② (Lemma and Qi is a discretized subset of Ω It has been shown that there must exist an optimal policy in Im (see our arguments in Section 2.1. and that I
must contain an c-near-optimal policy (see (47) Liu et al. (2023)).
Our work reduces the linear contextual bandit problem to linear bandits in Ω while Hanna et al. (2023) reduces it to linear bandits in Di. According to the discussion above, both suffice to establish no regret guarantees against the optimal policy. The key difference lies the computational efficiency. As discussed in Section 4 a polytope whose separation oracle can be implemented in poly(d, C, T) time, while in Hanna et al. 2023), Di is set containing (2) (t))(())))))))))() discrete points with chosen as (g))) remains open whether Di can be represented efficiently and whether Hanna et al.] (2023)ss algorithm can be implemented in polynomial time. In addition, our work operates on the adversarial-lows setting, strictly generalizing Hanna et al. (2023)'s 's stochastic-loss setting.
A technical question related to the discussion above is whether we can apply the discretization idea from Hanna al. (2023) purely in the analysis but not in the algorithm, i.c., bounding the regret overhead by the discretization error without restricting the learner's policy to the discretized linear policies. This would allow us avoid the Rademacher complexity analysis (Lemmal (1) and instead use Hoeffding's 's or Bernstein's inequality combined with a union bound, possibly leading to an improved regret bound. However, there is key technical challenge: the mapping V/ (TT,) is not continuous in Φ, which prevents from bounding || (TT)) ( ]| by constant times || d'Il, where & is an arbitrary point and ø' is a point in the discretized set. This would leave us no control on the performance of policies outside the set of discretized linear policies Ii As result, we are unable to derive uniform convergence result analogous to Lemma [using this approach.
B Lemmas for Linear Programming
Lemma 3 (Corollaries 14.1f and 14.1g of Schrijver (1866). Suppose P C Rdd is bounded polytope defined by rational inequalities of size at most a, and for which there exists a separation oracle SEP. There exists algorithm that solves the following problem: for any rational x E P, find vertices
To, I1.--..... .. E P and Xo; A1...,, da ' O such that x. Ei Aaaz and Ei \ 1, in time polytomially bounded by d, Or, the running time SEP, and the size of the input x.
Lemma 4 (Corollary 14.1a la of Schrijver (1986). Suppose P C Rdd is polytope defined by rational inequalities of size most a, and for which there exists a separation oracle SEP. Then there exists an algorithm that solves the linear optimization problem arg max=ep 3 x x.for any rational vector B in time polynomially bounded by a, the running time of SEP, and the size of the input B.
Lemma 5 (Theorem 3.1.2 of Weibel (2007). Let Pi,..., PN be polytopes in Rdd Let F be a face of the Minkowski sum ΣN P.. Then there are faces F2.... FN of PI. P2..... PN respectively such that F EN F.. What's 's more, this decomposition is unique.
Lemma (Corollary 3.1.3 of Weibel (200))) Let P= EN P. be a Minkowsky sum of polytopes Rdd. let F be nonempty face of P. and let Fi,...; FN be its decomposition. Then N(,, F) = F). ( (NN Fx).
20

---

C Proof of Lemma 1
Lemma 1 (Uniform Convergence). Consider any loss vector 0 E R., and suppose that |A| S K and A Ha, 0)1 S. b almost surely. Then, for any å E (0,1), uniformly over all linear classifier policies nh, the difference in performance of as on the sample A AN and its expected performance is at most
2dln(N22)
(l/6))
sup (V(TO). (8(=)). =bb1 2
+bV
dERA
N
with probability at least
Proof. We will first reduce the result statement about uniform convergence for linear multiclass classifiers with classes and an unusual loss function. To this end, note first that we can assume without loss of generality that A {V1,.... VK}. J. where the Vi,..., VK are random vectors in IR (If A has fewer than K elements, then consider it as a multiset and add repetitions of one of its elements.) We can assume all randomness in A is determined by an underlying random variable Z and that v, - gl Z, y) for each 'class" E [K], where g is class-sensitive feature map in the sense Shaley- Shwartz and Ben- David (2014) Section 17.2). Defining the linear multiclass classifier
(2) arg max (g( (),
wE(K)
we then obtain the correspondence
T (A) = Vz)
For any multiclass classifier c, let f(Z, = (Vazz), 0) be our "loss function'. Then
(V(T))))) - (Z))
((T)))))) Σ f(Z.
We therefore need to show the following uniform convergence result, with probability at least 1 8,
N Σ f(Z,, c) s 2by
2d 2d
2 2ln(4/))
sup
Blf(Z,c)
+ by
<EC
N
N
for the class of linear multiclass classifiers
C C= cos 1 E Rd)
with loss function f. order to establish Rademacher complexity
let S = (Zi.... ZN), and consider the empirical
Rad(C, oi...o
E
sup CEC
o, oz.
where the are independent Rademacher random variables with Pr(a: = 11 = Pr(a; +1)
1/2. Since [f( < b for E C by assumption, standard concentration bounds in terms of Rademacher complexity imply that
N E [(Zz, < |2 + by
ln((4/) N
sup <EC
B [[((2,c)
(8)
N
with probability at least 5. (This follows, for instance, by observing that
N
sup 3Ec
cZ
N Σ f(Z,, c)
N f(Zz, c). sup sup [(-((Z,,)))
= -max sup B[f(Z,c) - N Σ
CEC 7
dEC
N
im
21

---

and applying part 1 of Theorem 26.5 of SShalev-Swwarzz and Ben- Devid (2014) separately to f and -f to control both parts in the maximum separately using a union bound; then noting that f and - have the same Rademacher complexity.)
We proceed bound the Rademacher complexity the right-hand side of (8). First, let Cs (1.(z,,,.....(N... C} denote the restriction of to the sample S. Then
2 In CCpl
Rad(C, S) Rad(Cs, 8) S bV
by Massart's s lemma SShalev -Swaarz and Benn-Daill 2014). As discussed by Shalev-Shwarr and Ben- David (0144 Chapter 29), one possible generalization of the Sopnik-Chervonenkis dimension to
multiclass classification is Natarajan's dimension NCtDim(C). Natarajan's 's lemma (Natarajan 1989
p. 93), "Shale-Shwart and Ben-David 2014 Lemma 29.4) shows that
CCsl S NNtaii((C) K2 NatDim(C))
and, for linear multiclass classifiers, it is also known (Shalev-Shwal Sawlar-Shwartz and Ben David 2014 Theo- rem 29.7) that
NatDim(C) S d.
Putting all inequalities together, it follows that
N
2d InnNN'
2ln(4/5)
sup CEC
[l)
((Zi,c) S 2bp
+ by
N
N
N
with probability at least - 8, required.
D Omitted Details in Section
D.1 Robust Linear Bandits
Lemma (Lemma 14 of Zimmert and Lattimore (2022)). Let F be u-self-concortant barrier for A c Rd for some v 2 1. Then for any x, u E A.
| - u(( S 5 u, VF(z))+
where 7
( E [1r 2 11.
3/3
6v33
It is known that the continuous exponential weight algorithm is equivalent to FTRL with entropic barrier as the regularizer together with a particular sampling scheme (Bubeck and Eldan 2015) Zimmert and Lattimore, 2022). We summarize the equivalence in the following lemma, the details of which can be found Zimmert and Lattimore (2022).
Lemma 8 (Facts from Bubeck and Eldan (015), Zimmert and Lattimore 2022 Consider Algo-
rithm 2
Let 34 = Eyg- y] and let F:; A be the entropic barrier on A. Then we have
Tt arg min veñ
y/ Σ T<E
00- b.)
F(y)
Furthermore,
VF(#:) 11 Σ (0- by)
and F²F(I)) (By-gi 1(y ze)(y 1)
Lemma 9 (Lemma 4, Ito et al. (2020)) Let qt, Ct. E,, Enx be defined in Algorithml Then for any f(y) : A [-1,1].
E y.. [f(v]] Ey [f()]] < 10dexp( 1TT10
Furthermore,
Σ, < E 1 3
Σ,.
4
22

---

Proof of Theorem 2
First, we decompose the regret as follows:
r
E
y u, 0²)
E
BB By [8) - u, 0r)
+ 0(1)
E
u, 02 - bi)
E
Dt u, 8₁ 01)
E
Σ
(ot: u, ba)
+0(1).
FTRL
Bias
Bonus
Bounding FTRL term The analysis for the FTRL term follows that in Ito et al. 2020). Specifically. directly following their Lemma 5, Lemma 6, and the analysis below Lemma 6, we have the following: as long as v/10, bel1s, S 1, we have
dlog T
T
FTRL S
+ nl
Σ
10,
- 6.112.
+ 0(1)
t=1
d dloog T
+ 2n
|10c113, + |1b.l #F(wz)
+0(1.
(by Lemma g
11
For the two middle terms, we have
10 12. s (y) - x1)T
(31 +E.) Ex (31+ +Z,+ (y: - xx))
S 2(y rz) T2, (yr -x))c
(by Lemma 9
s 2d.
(by the truncation in the algorithm)
and
1 |V so 50 @ + bb ((.))) = (2Vd7e+
1
T
T
where we used the fact that F(.) is (d) self-concordant barrier and thus [V( S (d). Thus, since 7) S T we have
dlog T
FTRL
+0
ndy
ci + nldd2
"
Bounding Bias term Let B[ea] = v/ 0; + e, (31), where e, (v) is the amount of misspecification
when choosing y. By assumption, we have (c) I for any y.
E, [0]]] E. [8I Σ.) 3,)-1(( 'y: x2) (v. 0. ()())))
E, (BT + +5,) -1 2²) ((ur xx.) TT)Te. 0, + ca(v))) E. (ST (2.)+ -1,)- xre )or O2
- B(31 + -0,
0, E, (08 + - 2x)) + (81+ + Ex) ( xn )zr 0c.
Using this we get
( (z1 u, E.(0ii)
< B (xt - T) (BI + -10 + (xt u) [(T Ex) 2:)ce(u))
(4)
+ (xx w) ((TT + 5t
xz 2x) 0z
(9)
23

---

We handle (*) as follows:
E (oz u)T -2,- -B)
214(11 TBT E..) -10 (y))
V (I+ u) ( T(I1 -.)- (c(v)) xzz) (B1 Σx) - u)
ev (xx - w) (T1(31
I - (3((0))
Continuing from we get
Kmz- - u, - 1
</11222 u|l 110 cl|a2 ul((ar+5))- 1 (1( xellger+5t.)-
1 V where in the last inequality we use that 1ly we 20ll(31+10= assumption that |02 S Vd.
v d3ll -ulluru + e|| ull (11+
3/3 Dt ull(er+5.) 1 xell2.
211v+ zells. by Lemma 9 and the
By Lemma we have ||,, E.ll [Byng [y] = d- we can bound the expectation of the sum of the last expression as
Ey bulll S 50 By the choice of
c+ T ]
Bias
E
||= ulll (8145))))))
Bounding Bonus term be can also be written as
Notice that with the equivalence established in Lemma our bonus term
6 = -8 (e (+ 72 VF(x.),
where F()) is the entropic barrier on A. Using Lemma 7 and the fact that F(-) is Odd)-self- concordant barrier, we can bound
(8e + 8/722)
(xt - u, be) $
100 ul(v=F(m.) + 6cv
4
2E +
||,; (--uullvr(rm) + O(de)
T
2c +
|| - =1|اا=1 + O(de)
T
1
<
+ T
||ا| ul | + O(de).
(by Lemma 9
Thus,
Bonus
< E
Σ
c
| To
1
|| -
ulls -
(dTe)
Adding up all terms
Adding up the three terms, we get
s dlog T
T
E Σ (ve u, 0,)
+
o
dTe
n
By the assumption e right-hand side by
[0, 1] and the assumption E, [ce]
vi 0, S e, can further bound the
o dlogg T
dlogg
T
+ 1 2
Σ
+ dI'
50
(we, 0z)
+ (d r)dr2)Ie
17
24

---

Then, by rearranging, we find that
T
dloog T
T
(u, 0e) ddTe)
E
Σ
yt u, Oz)
+ n117
Σ
Choosing the optimal v, we further bound
T (dv (log T)
E
Σ (1/- ur 0.) =0 dr
Σ
(u, 02) + dle
=ō (dV' + ddTe).
(10)
By Definition
a Vddmisppeciffctiionnrobust algorithm.
this a
D.2 Regret bound of LCB
Proof of Theorem 3 Let fî be the set of linear policies created from the vertices of Ω and let be set of all linear policies.
The regret bound guaranteed by the a-misspecificaiion-robus linear bandit problem
E
Wee Oz)
s min Σ ven 1=1
y 0, + + (aVT + avdde)
(
(11)
for some 2 1. By Lemma have
yt = E AND [Te]
We further define
21 EAND (T)),
x EADD (A)],
3" = BAND (A)],
where x² E II is the final regret comparator. Define
dlog(NKT//)
E E=4Y 4V
N
where is the number of contexts used to construct 2. Then by Lemma we have
(V,, 0.) (2e, 0,) S and (yy" 01) (2* 0c)l with probability at least 1 - 8 for all f. Choosing
fo. we obtain
T
E
Ez 0z)
< E
We, 0z)
+ +Te
(y", 02) (dVVT=
(by 11
(2",0) +0 :d(TV :o(vV++avai) +avile))
(2", 01) +0 (
+0 (AVT + adT
log(NKT)
N
This proves the theorem.
E Omitted Details in Section 5
Proof of Theorem This is by the same proof Theorem just noticing that it actually achieves
small-loss bound in 10
25

---

Proof of Theorem
This is similar to the proof of Theorem
B except that we replace
11 by
E
(ye 0z)
min Σ NEL t=1
y 02
Ô
Σ (y. 01) + avdeT)
(12)
Following the same steps, we get
T
log( (og(NTT) KT)
E
(zz, O1) - Σ (1) +0
d,
Σ
(2*,0s) + adT
(13)
N
where 2, EAND (A)) and AND (A)].
Since the learner given simulator access, she can draw N (((27d222) samples and make the last term
13 be a constant. This will give a final regret bound of Ö(d Ei= (2 (2+, .0,
=
OddLL*)
O
26


Reviews:
[{"review_id": "SDmbtkPVhD", "reviewer": "Reviewer_aqgX", "summary": "The paper studies the adversarial linear contextual bandits problem with stochastic action sets.\nIn this problem, in each round, an adversary chooses a loss vector $\\theta_t \\in R^d$ \nand a random action set (here also referred to as \"context\")\n$A_t \\subseteq R^d$ is chosen via sampling from some fixed (but unknown) distribution.\nThe algorithm can then choose some vector $a_t \\in A_t$, incurring\nthe loss $\\ell_t(a_t) = <a_t, \\theta_t>$.\nThe goal is to compete with the set of mappings from\ncontext (aka action sets) to actions;\n\nThe paper obtains an algorithm with\n$\\tilde{O}(d^2\\sqrt{T})$ regret\nthat runs in time $poly(d, T, C)$ time where\n$C$ is the number of linear constraints defining $A_t$.\nImportantly, the running time does not depend on the number of actions,\nwhich was a major limitation of the prior work.\nAs a special case, this gives the first polynomial-time\nalgorithm with sublinear regret for combinatorial bandits with adversarial losses and stochastic action sets.\nThis can further be improved to $\\tilde{O}(d\\sqrt{L^*})$ when\ngiven access to a simulator for sampling $A_t$.\n\nThe paper obtains the result by providing a reduction to \nthe linear bandits with misspecification (where the action set is fixed).\nThe problem is misspecified in that the feedback received\nby the learner is not unbiased; they receive a feedback\nthat is at most $\\epsilon$ away from the inner product of $\\theta_t$\nand the chosen action.", "questions": "Questions:\n- In the definition of linear bandits, does the learner\n  incur the loss they see as feedback or do they incur $<y_t, \\theta_t>$?\n- The definition of regret in line 84 seems wrong; there should be an expectation over $A_t$?\n  Prior work (e.g., see Liu et al.) also take expectation.\n  Without expectations, assuming $A_t$ comes from a distribution that is not discrete,\n  there are likely going to be different $A_t$ values across all $t$.\n- Line 90: \"learner decides\": I think you mean adversary decides?\n- The reduction seems fairly generic. Are their similar problems in which the authors believe\n  such approaches would work? Alternatively, are there similar examples known in the literature the authors are aware of?\n  If so it would be good to discuss them in more detail.\n- It would be good if you provide a more detailed comparison of your reduction with that of Hanna et al.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper addresses a computational limitation of existing work.\n  As such, it fits in nicely with a larger (and growing) body of literature which have attempted to do this\n  for many statistical problems.\n- The approach is based on a reduction to a simpler problem, which in my opinion is nice.\n\nWeaknesses:\n- The regret does not match that of the existing works which are not computationally efficient, though\n  in my opinion this is fine.\n- The paper has quiet a few typos (e.g., see below) and could benefit from proofreading.", "was_revised": true, "final_justification": "The authors have answered my questions and I still lean towards acceptance.", "rebuttal": "We thank the reviewer for their time and for providing an insightful review. Please see our responses below. \n\n**Q1**:  In the definition of linear bandits, does the learner incur the loss they see as feedback or do they incur $\\langle y_t, \\theta_t\\rangle$?\n\n**A1**:   Our Eq.(2) assumes the learner incurs the loss $\\langle y_t, \\theta_t\\rangle$. However, if instead the learner incurs the observed loss, the regret bounds differ by at most $2\\epsilon T$ under our misspecification assumption—a difference that can be absorbed by the last term in Eq.(2). Thus, both interpretations work.  \n\n&nbsp;  \n\n**Q2**:  The definition of regret in line 84 seems wrong; there should be an expectation over $\\mathcal{A}_t$? \n\n**A2**:  Thank you for pointing this out. You are right—the regret definition in line 84 should include an expectation over $\\mathcal{A}_t$.  We will correct this in the revision. Note that our theoretical analysis indeed takes expectation over $\\mathcal{A}_t$.\n\n&nbsp;  \n\n**Q3**:  Line 90: \"learner decides\": I think you mean adversary decides?\n\n**A3**:  Thank you for catching this.  Yes, it should be \"adversary decides\".  \n\n&nbsp;  \n\n**Q4**:  The reduction seems fairly generic. Are there similar problems in which the authors believe such approaches would work? Alternatively, are there similar examples known in the literature the authors are aware of? \n\n**A4**:  Yes, our reduction approach has broader applicability. We will discuss two relevant examples: \n\nFirst, our problem setting is a special case of MDPs with fixed transitions and adversarial losses, which has been extensively studied recently. Our approach provides a potential solution for such settings when dealing with continuous or exponentially large action spaces. \n\nSecond, recent work on linear Markov games (Wang et al. 2023; Dai et al. 2024) reduces the problem to adversarial linear contextual bandits with stochastic action sets. While their regret guarantees are independent of the number of actions $K$, their computational complexity still scales with $K$. Our approach could potentially eliminate this computational dependence on $K$ in their setting as well. \n\nWang, Liu, Bai, Jin.  Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. 2023. \n\nDai, Cui, Du.  Refined Sample Complexity for Markov Games with Independent Linear Function Approximation. 2024.  \n\n&nbsp;  \n\n**Q5**: It would be good if you provide a more detailed comparison of your reduction with that of Hanna et al.\n\n**A5**:  Thanks for the suggestion. We will add an extensive comparison with Hanna et al. in our final version.  While the reductions are conceptually related, the key difference lies in our primary focus on computational efficiency. Their work only focuses on regret bounds, and there are still gaps in making their algorithm polynomial time.\n\nSpecifically,  we reduce the problem to linear bandits with domain $\\hat{\\Omega}$ — the image under $\\Psi$ of all policies $\\pi$ — which is a polytope with poly($d$, $C$, $T$) linear constraints that allows for linear programming tools.  On the other hand, Hanna et al. reduce the problem to linear bandits with domain $\\mathcal{X}$ — the image under $\\Psi$ of linear policies $\\pi_\\phi$ where $\\phi$ comes from an $\\epsilon$-net of $\\mathbb{R}^d$ — which has $T^d$ discretized points. It remains unclear how their algorithm efficiently: 1) constructs and maintains these points and 2) runs a linear bandit over them. While they mention Phased Elimination, this algorithm has computational complexity scaling with the number of actions ($T^d$ in their case). \n\nDealing with the polytope requires novel techniques, including our method of mapping a point in $\\hat{\\Omega}$ to policies (Section 3.2), and our analysis that bounds the estimation error using Rademacher complexity (Section 3.3) rather than discretization plus Hoeffding’s inequality and a union bound as in Hanna et al.\n\nFinally, we operate on the adversarial setting while they on the stochastic setting, a strict generalization."}, {"review_id": "aXs8TbuXlV", "reviewer": "Reviewer_Aqe6", "summary": "The work investigates the problem of adversarial linear contextual bandits, where in each round a set $\\mathcal{A}_t$ of $K$ actions is drawn i.i.d. from an unknown but fixed distribution over $\\mathbb{R}^d$. The randomized learner picks $a_t \\in \\mathcal{A}_t$ and observes a noisy loss whose expectation is $\\langle a_t,\\theta_t \\rangle \\in [-1,1]$, where $\\theta_t\\in\\mathbb{R}^d$ is a loss vector chosen by an oblivious adversary. The regret is defined with respect to the optimal policy, which is known to be linear. The authors prove regret bounds of the order of $d^2\\sqrt{T}$ using an algorithm whose running time is polynomial in $d$, $T$, and the number of linear constraints sufficient to define the convex hull of each action set. This is the best regret among all known efficient algorithms with full bandit feedback, no access to simulators, and no dependence on $K$. The lack of dependence on $K$ is useful for applications to certain instances of combinatorial bandits such as shortest paths. When a simulator for the distribution is available, the regret can be improved to order of $d\\sqrt{L^\\star}$ (up to log factors), where where $L^\\star$ is the cumulative loss of the best policy.", "questions": "1. The optimal regret $d\\sqrt{T}$ is currently achieved either inefficiently or with a polynomial number of calls to a simulator. The question whether the optimal regret could be achieved in poly time (even allowing a dependence on $K$) and without using a simulator seems rather fundamental and is not directly addressed by your work. Could your techniques provide any insight on this question?\n\n2. Is your algorithm the first one working in the convex hull of the action set? What did prevent previous approaches to depend on $C$ rather than $K$?\n\n3. There is a large body of literature proposing algorithms that simultaneosly achieve optimal (or near-optimal) stochastic and adversarial regret bounds for bandits (best of both worlds). Could your techniques be applied to obtain results in this direction?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The result is obtained by a novel and technically involved extension to an adversarial setting of a reduction previously proposed for the stochastic setting. As the reduction is to adversarial linear bandits with fixed action set and misspecification, the authors also design a new algorithm for this setting with the required tolerance and runnning time. The lack of the dependence on $K$ allows to obtain the first efficient algorithm with $\\sqrt{T}$ regret for combinatorial bandits with random action sets.\n\nWeaknesses: The paper is not particularly easy to understand unless one has a good prior knowledge of the setting and its basic properties (the quality of the writing could also be improved). The abstract suggests that the proposed algorithm allows to solve any combinatorial bandit problem in polytime, whereas this seems true only for those action sets whose convex hull can be described by a polynomial number of linear constraints. Despite the rather impressive technical effort, the overall significance of the contribution remains a bit unclear. The algorithm is neither simple nor practical.\n\nA rather typical NeurIPS contribution that privileges technical prowess over conceptual novelty. It is nevertheless a solid contribution that advances the state of the art. I am therefore supporting acceptance.", "was_revised": true, "final_justification": "I had an initial positive opinion on this submission. The opinion did not change after the rebuttal, which clarified some of the aspects in the manuscript. If accepted, I would encourage the authors to use the extra space to add the clarifications provided in the rebuttal.", "rebuttal": "We thank the reviewer for their time and for providing an insightful review. Please see our responses below. \n\n**Q1**:  The optimal regret $d\\sqrt{T}$  is currently achieved either inefficiently or with a polynomial number of calls to a simulator. The question whether the optimal regret could be achieved in poly time (even allowing a dependence on $K$) and without using a simulator seems rather fundamental and is not directly addressed by your work. Could your techniques provide any insight on this question?\n\n**A1**:  This is indeed a fundamental question. Unfortunately, our techniques don't directly resolve the gap between the regret with and without simulators. \n\nThe suboptimality in both our bound and Liu et al. (2023) stems from the same core issue: we approximate the true context distribution using empirical samples collected before time $t$, then evaluate the learner's policy on this empirical distribution. Since the empirical samples and the learner's policy are correlated, we must use a uniform convergence bound over all policies, which introduces the extra $d$ factor.  \n\nFor the special case where action sets are subsets of the standard basis in $\\mathbb{R}^K$ (i.e., sleeping bandits), Schneider and Zimmert (2023) developed a sophisticated algorithm to avoid this correlation and achieve the optimal $\\sqrt{KT}$ bound. It is not yet clear how to generalize their approach to our setting.  We will add this reference and discuss it in our revision.\n\nSchneider and Zimmert. Optimal cross-learning for contextual bandits with unknown context distributions. 2023. \n\n&nbsp;\n\n**Q2**:  Is your algorithm the first one working in the convex hull of the action set? What did prevent previous approaches to depend on $C$ rather than $K$? \n\n**A2**:  Yes, our algorithm is the first to achieve computational complexity depending only on $C$ rather than $K$.\n\nAll previous works studying this problem are built on the approach of (Neu and Olkhovskaya, 2020), which runs an individual linear bandit algorithm on each possible action set, with the loss estimators shared between action sets.  Except for Liu et al. (2023), all works use exponential weights over actions, whose computational complexity scales with $K$. \nLiu et al. (2023) uses FTRL with a log-determinant barrier (logdet-FTRL), whose computational complexity still scales polynomially with $K$.  \n\nWe initially attempted to modify Liu et al. (2023)'s approach by substituting logdet-FTRL with a linear bandit algorithm whose computation does not scale with K (e.g., SCRiBLe and continuous exponential weights), but that failed: for technical reasons, these algorithms do not seem to allow using shared loss estimators among action sets. \n\nIn this paper, we adopt a different approach that runs linear bandit over a \"single action set\" constructed by averaging up the empirical contexts. This allows us to run SCRiBLe or continuous exponential weights on it without incurring the previous issue. \n\n&nbsp;\n\n**Q3**:  There is a large body of literature proposing algorithms that simultaneously achieve optimal (or near-optimal) stochastic and adversarial regret bounds for bandits (best of both worlds). Could your techniques be applied to obtain results in this direction?\n \n**A3**:  For adversarial contextual bandits with stochastic contexts, there is indeed work investigating best-of-both-worlds guarantees under the assumption of known context distribution or access to a simulator (Kato and Ito, 2023; Kuroki et al., 2024). In this case, our approach can also achieve best-of-both-worlds results by simply reducing our problem to a linear bandit algorithm with best-of-both-worlds guarantees.\n\nHowever, when the context distribution is unknown and there is no simulator, our current technique faces a limitation: the misspecification parameter $\\epsilon=\\tilde{\\Theta}(1/\\sqrt{t})$ introduced in our reduction to linear bandits causes the regret to scale as $\\sqrt{T}$ even in stochastic environments, preventing us from achieving the $\\log(T)$ regret characteristic of the stochastic setting. Resolving this would be an interesting future direction. \n\nKato, Ito. Best-of-Both-Worlds Linear Contextual Bandits. 2023.\n\nKuroki, Rumi, Tsuchiya, Vitale, Cesa-Bianchi.  Best-of-Both-Worlds Algorithms for Linear Contextual Bandits.  2024."}, {"review_id": "z1D0QWYEpZ", "reviewer": "Reviewer_Jz1R", "summary": "This paper focuses on the problem of adversarial linear bandits with stochastic action set (as context). Specifically, without the knowledge of the context distribution, the authors provide an algorithm achieving $O(d^2\\sqrt{T})$ regret with runtime polynomial in the dimension $d$ and the horzion $T$ (independent of the number of action $K$ in each action set). Moreover, with the knowledge of the context distribution, the authors further show that an improved first-order bound $O(d\\sqrt{L_0})$ is achievable, where $L_0$ is the expected loss of the best policy in hindsight. The algorithm is motivated by the recent advance in reducing contextual linear bandits to non-contextual bandits by Hanna et al., 2023. However, the reduction introduced in this paper is slightly different from the one in Hanna et al., 2023 in the sense that Hanna et al., 2023 only considers the stochastic loss case.", "questions": "- Based on my understanding, the reason why first-order regret bound is not obtained for the unknown context distribution setting is that the action set approximation error can not be related to the loss of the algorithm. I wonder whether there are some methods to address this?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The problem is well-motivated and this paper provides the first algorithm that achieves $O(\\sqrt{T})$ regret with runtime independent of the number of action without the knowledge of the context distribution. The paper is also well-written in general.\n- The proposed algorithm is intuitive and easy to follow. Specifically, this paper proposes a variant of contextual-to-non-contexutal reduction from Hanna et al., 2023 to handle the adversarial linear loss, which is interesting to me. In addition, to achieve the efficiency improvements, the authors also proposed an algorithm for non-contextual linear bandits with known misspecification, which utilizes the nice property of this reduction.\n- With the knowledge of the context distribution, the algorithm does not need to approximate the non-contextual action set and achieves a better $d\\sqrt{L_0}$ regret.\n\nWeaknesses:\n- As the authors mentioned, the $d$ dependency in the regret bound when the context distribution is unknown is still suboptimal.\n- Maybe the authors can add more explanations to Algorithm 2 in the main text. Currently, it seems that the authors just list Algorithm 2 and its guarantee without introducing more about the intuition and the procedure.\n\nIn general, I do not find more major concerns.", "was_revised": true, "final_justification": "I read the rebuttal as well as the other reviewers' comment. I decide to maintain my positive score.", "rebuttal": "We thank the reviewer for their time and for providing an insightful review. Please see our responses below.  \n\n**Q1**:   Maybe the authors can add more explanations to Algorithm 2 in the main text. Currently, it seems that the authors just list Algorithm 2 and its guarantee without introducing more about the intuition and the procedure.  \n\n**A1**:  Thanks for the suggestion. We will add more explanation for Algorithm 2 in the revision. While its guarantee is new, its main algorithmic elements are from prior work.  It is a simplified and improved version of Liu et al. (2024)’s Algorithm 3 (the simplification and the improvement in the bound are possible because in our case the amount of misspecification $\\epsilon$ is the same in all rounds). Liu et al. (2024)’s algorithm, in turn, is a combination of the clipped continuous exponential weights of Ito et al. (2020) that guarantees optimal small-loss bound with polynomial computational complexity, and the bonus design in Zimmert and Lattimore (2022) that ensures misspecification robustness (though their original goal is high-probability bound). \n\nLiu, Tajdini, Wagenmaker, Wei.  Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification. 2024.  \n\nIto, Hirahara, Soma, Yoshida.  Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits.  2020.  \n\nZimmert and Lattimore.  Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits.  2022.  \n\n&nbsp;\n\n**Q2**:   Based on my understanding, the reason why first-order regret bound is not obtained for the unknown context distribution setting is that the action set approximation error can not be related to the loss of the algorithm. I wonder whether there are some methods to address this?\n\n**A2**: To make the action set approximation error related to the loss of the algorithm, we essentially need a counterpart of Bernstein inequality for our Lemma 1 (the concentration bound based on Rademacher complexity). There are some related tools in the literature, such as local Rademacher complexity (Bartlett et al., 2005) and offline Rademacher complexity (Liang et al., 2015).  However, we haven’t found a way to integrate them into our framework and left it as a future work.  We will provide more discussions on this in the revision. \n\nBartlett, Bousquet, Mendelson.  Local Rademacher complexities. 2005. \n\nLiang, Rakhlin, Sridharan. Learning with Square Loss: Localization through Offset Rademacher Complexity.  2015."}, {"review_id": "FdXivIyQuQ", "reviewer": "Reviewer_VCk3", "summary": "This paper studies the linear contextual bandit problem, where contexts (action sets) are generated stochastically and linear losses are selected adversarially. The main contribution is an efficient algorithm that achieves a regret bound of $\\tilde O(d^2\\sqrt{T})$ for the dimensionality $d$ of action sets and time horizon $T$. The algorithm runs in polynomial time in $d$, $T$, and the number of constraints that specify the action sets, thereby allowing for efficient learning in large action spaces. Moreover, given access to the context simulator, the bound is improved to $\\tilde O(d\\sqrt{L^*})$, where $L^*$ is the cumulative loss of the best policy. The main technical idea is to reduce the problem to the adversarial linear bandit problem with misspecification. Combing this with a uniform convergence argument and the complexity analysis techniques known in linear programming leads to the desired result.", "questions": "1. In equation (1), how to detail with possibly multiple minimizers?\n2. In the equation after line 121, what is the rightmost expectation taken about?\n3. I could not understand the rightmost expression of $\\hat \\Omega$ after line 125. Why does it contain neither $\\pi$ nor $\\Pi$?\n4. In line 194, what is the specific amount of the misspecification $\\varepsilon$? Does it come from the uniform convergence bound?\n\nMinor comment:\n- In line 121, $y_t$ should be $a_t$ for the consistency with the subsequent equation.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. This paper provides the first efficient $\\mathrm{poly}(d)\\sqrt{T}$-regret algorithm for the adversarial linear contextual bandit problem that can handle large action spaces, resolving the open question raised by Liu et al. (2023).\n2. The main reduction idea appears novel and interesting, which may inspire future research in this area.\n\n### Weaknesses\n1. The details of the misspecification-robust adversarial linear bandit algorithm are deferred to the appendix, and little intuition regarding the proof of Theorem 2 is provided in the main text. This makes it difficult to assess the significance of the adversarial linear bandit algorithm, particularly for readers unfamiliar with the misspecification-robust setting, such as myself.\n2. I do not consider this a major weakness, but the algorithm relies on somewhat costly operations such as the ellipsoid method. Additionally, the complexity also depends on the number of constraints, which may be large in some cases. The authors are aware of these points and have discussed them in the paper.", "was_revised": true, "final_justification": "The paper presents the first $\\mathrm{poly}(d)\\sqrt{T}$-regret algorithm for the adversarial linear contextual bandit problem, based on a novel reduction to corruption-robust adversarial linear bandits. I believe this contribution is significant enough to be accepted, although the efficiency in practice appears to have room for improvement.", "rebuttal": "We thank the reviewer for their time and for providing an insightful review. Please see our responses below. \n\n**Q1**:   The details of the misspecification-robust adversarial linear bandit algorithm are deferred to the appendix, and little intuition regarding the proof of Theorem 2 is provided in the main text. This makes it difficult to assess the significance of the adversarial linear bandit algorithm, particularly for readers unfamiliar with the misspecification-robust setting.  \n\n**A1**:  Thanks for the suggestion. We will add more explanation for Algorithm 2 in the revision. While its guarantee is new, its main algorithmic elements are from prior work.  It is a simplified and improved version of Liu et al. (2024)’s Algorithm 3 (the simplification and the improvement in the bound are possible because in our case the amount of misspecification $\\epsilon$ is the same in all rounds). Liu et al. (2024)’s algorithm, in turn, is a combination of the clipped continuous exponential weights of Ito et al. (2020) that guarantees optimal small-loss bound with polynomial computational complexity, and the bonus design in Zimmert and Lattimore (2022) that ensures misspecification robustness (though their original goal is high-probability bound). \n\nLiu, Tajdini, Wagenmaker, Wei.  Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification. 2024.  \n\nIto, Hirahara, Soma, Yoshida.  Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits.  2020.  \n\nZimmert and Lattimore.  Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits.  2022.  \n\n&nbsp;\n\n**Q2**:   In equation (1), how to detail with possibly multiple minimizers? \n\n**A2**:   Our results allow ties to be broken arbitrarily. The regret analysis is agnostic to the tie-breaking rule used. We will clarify this in the revision.\n\n&nbsp;\n\n**Q3**:   In the equation after line 121, what is the rightmost expectation taken about? \n\n**A3**:   The rightmost expectation is taken over the randomness in $\\pi_t$ (i.e., the random policy selected by the algorithm at time $t$).  \n\n&nbsp;\n\n**Q4**:  I could not understand the rightmost expression of $\\hat{\\Omega}$ after line 125. Why does it contain neither $\\pi$ nor $\\Pi$?   \n\n**A4**:  This can be seen by the following equalities.  For simplicity, let’s first assume $\\mathcal{A}_1, \\ldots, \\mathcal{A}_N$, which are drawn i.i.d. from $\\mathcal{D}$, are all distinct.  \n\n$\\hat{\\Omega}$ \n\n$= \\lbrace \\hat{\\Psi}(\\pi) \\mid   \\pi\\in\\Pi \\rbrace$  \n\n$= \\lbrace \\mathbb{E}_{\\mathcal{A}\\sim \\tilde{D}} [\\pi(\\mathcal{A})]  \\mid  \\pi\\in\\Pi  \\rbrace$  &nbsp;&nbsp; &nbsp;&nbsp;  // by the definition of $\\hat{\\Psi}$, where $\\tilde{D}$ is the empirical context distribution \n\n$= \\lbrace \\frac{1}{N} \\sum_{i=1}^N   \\pi(\\mathcal{A}_i)  \\mid  \\pi\\in\\Pi  \\rbrace$ \n\n$=  \\lbrace \\frac{1}{N} \\sum_{i=1}^N   a_i   \\mid  a_i \\in \\text{conv}(\\mathcal{A}_i)  \\rbrace$\n \nThe key is in the last inequality:  Recall that $\\pi$ is a mapping from an action set $\\mathcal{A}$ to an element in conv($\\mathcal{A}$), and $\\Pi$ contains all such mappings. When $\\mathcal{A}_1, \\ldots, \\mathcal{A}_N$ are all different, we can freely choose $\\pi(\\mathcal{A}_i)$ as an element $a_i \\in \\text{conv}(\\mathcal{A}_i)$ for every $i$. This is essentially the last expression.  \n\nIf there exist $i\\neq j$ such that $\\mathcal{A}_i=\\mathcal{A}_j$, then we have the additional constraint that $a_i= \\pi(\\mathcal{A}_i) = \\pi(\\mathcal{A}_j)=a_j$.\n\n&nbsp;\n\n**Q5**:  In line 194, what is the specific amount of the misspecification $\\epsilon$? Does it come from the uniform convergence bound?\n\n**A5**:   Yes, $\\epsilon$ comes from the uniform convergence bound.  Its value is essentially the right hand side of Line 132 with $b=1$ and $N=\\Theta(t)$ (the number of contexts the learner has collected up to time $t$). \n\n&nbsp;\n\nThank you for pointing out the typo in the minor comment."}]

Author rebuttal:

Meta-review: This paper provides an efficient algorithm for adversarial linear bandits with a stochastic arm set, which runs in polynomial time and does not depend on the number of arms. This is achieved by a reduction from adversarial linear contextual bandits to misspecification-robust linear bandits. Although the dependence on $d$ is not yet optimal, all reviewers appreciate the technical contributions of the paper and have given positive evaluations. The authors are encouraged to incorporate the reviewers’ constructive feedback into the revised manuscript.
Decision: Accept (poster)