Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
Authors: Haolin Liu
Artin Tajdini
Andrew Wagenmaker
Chen-Yu Wei
Venue: NeurIPS 2024 poster (2024)
Keywords: corruption-robust
linear bandits
misspecification
reinforcement learning
Primary area: bandits
TL;DR: We obtain minimax optimal bounds for corruption-robust linear bandits, and show that they can be used to obtain novel gap-dependent misspecification bounds in bandits and RL.

Abstract: In linear bandits, how can a learner effectively learn when facing corrupted rewards? While significant work has explored this question, a holistic understanding across different adversarial models and corruption measures is lacking, as is a full characterization of the minimax regret bounds. In this work, we compare two types of corruptions commonly considered: strong corruption, where the corruption level depends on the learner’s chosen action, and weak corruption, where the corruption level does not depend on the learner’s chosen action. We provide a unified framework to analyze these corruptions. For stochastic linear bandits, we fully characterize the gap between the minimax regret under strong and weak corruptions. We also initiate the study of corrupted adversarial linear bandits, obtaining upper and lower bounds with matching dependencies on the corruption level. Next, we reveal a connection between corruption-robust learning and learning with gap-dependent misspecification—a setting first studied by Liu et al. (2023a), where the misspecification level of an action or policy is proportional to its suboptimality. We present a general reduction that enables any corruption-robust algorithm to handle gap-dependent misspecification. This allows us to recover the results of Liu et al. (2023a) in a black-box manner and significantly generalize them to settings like linear MDPs, yielding the first results for gap-dependent misspecification in reinforcement learning. However, this general reduction does not attain the optimal rate for gap-dependent misspecification. Motivated by this, we develop a specialized algorithm that achieves optimal bounds for gap-dependent misspecification in linear bandits, thus answering an open question posed by Liu et al. (2023a).

Corruption-Robust Linear Bandits: Minimax
Optimality and Gap-Dependent Misspecification
Haolin Liu'
Artin Tajdini University of Washington artinêcs. washington edu
University of Virginia ers8rh@virginia.
Andrew Wagenmaker University of California, Berkeley ajwagendberkelly. edu
Chen- Yu Wei University of Virginia chenyu. Sleeyy.wei@virrinnaa.ee edu
Abstract
linear bandits, how can learner effectively learn when facing corrupted re- wards? While significant work has explored this question, holistic understanding across different adversarial models and corruption measures is lacking, as is a full characterization of the minimax regret bounds. In this work, compare two types of corruptions commonly considered: strong corruption, where the corruption level depends the learner's 's chosen action, and weak corruption, where the corrup- tion level does not depend on the learner's ' chosen action. We provide a unified framework analyze these corruptions. For stochastic linear bandits, we fully characterize the gap between the minimax regret under strong and weak corruptions. We also initiate the study of corrupted adversarial linear bandits, obtaining upper and lower bounds with matching dependencies on the corruption level.
Next, we reveal connection between corruption-robus. learning and learning with gap-dependent misspecification
setting first studied by Liu et al. (2023a), where the misspecification level of an action or policy is proportional its suboptimality. We present a general reduction that enables any corruption- handle gap-dependent misspecification. This allows to recover the results of Liu et al. (2023a) in a black-box manner and significantly generalize them to settings like linear MDPs, yielding the first results for gap-deper sup-dependent misspecification in reinforcement learning. However, this general reduction does not attain the optimal rate for dep-deeendent misspecification. Motivated by this, develop special- ized algorithm that achieves optimal bounds for gap-dependent misspecification linear bandits, thus answering open question posed by Liu al. (2023a).
algorithm
Introduction
The real world is rarely truly stochastic-in practice, our observations are often corrupted- furthermore, rarely the modeling assumption typically made in theory-that the true data- generating process lives in our model class-met in reality. Therefore, robustly handling these deviations from idealized assumptions is crucial. These challenges are particularly pronounced in interactive decision-making settings, where deviations from idealized assumptions could lead an algorithm to take unsafe severely suboptimal actions. In this work, seek to address these challenges, and develop a unified understanding for robust learning in corruption-robust and misspecified settings.
Authors are listed in alphabctical order by last name.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

We first consider the corruption-roe robustt learning setting. Robust learning in the presence of corruptions requires designing algorithms whose guarantee have a tight scaling in the corruption level. That is. although some amount of suboptimality is inevitable if our observations are corrupted, we would hope to obtain the minimum amount of suboptimality possible at a given corruption level. While much work has been done on learning with corrupted observations, existing work has failed to yield a tight characterization of this scaling in the corruption level, even in simple settings such as linear bandits. We address this shortcoming, and develop an algorithm which achieves the optimal scaling in the corruption level, and further extend this to a novel corrupted adversarial linear bandit setting, where in addition to corrupted observations, the rewards themselves may be adversarially chosen from round to round. We obtain the first provably efficient bounds in this setting.
Model misspecification. another extensively studied problem in the literature, can be thought of as a form of corruption, where the corruption level is the amount of misspecification between the "closest" model in the model class and the true environment. Standard discussions assume that the misspecification for every action has a uniform upper bound, and the final regret guarantee scales linearly with the amount of misspecification. The work of Liu et al. (2023a) initiated the study on the gap-dependent misspecification setting, where the misspecification level for a given action scales with the suboptimality of that action. They demonstrated that the linear scaling in regret is not necessary in this case. We revisit this problem, and show a general reduction from the gap-dependent misspecified setting to the corruption setting. We utilize this reduction to show that settings previously not known to be learnable- for example, linear MDPs with policy gap- gap-dependent misspecification in fact efficiently learnable with existing corruption robust algorithms.
misspecification usually
Together, our results present a unified picture of optimally learning in the presence of observation corruption, and (certain types of) model misspecification. We summarize our contributions as follows (see Section and Section 3 for formal definitions of the mentioned quantities):
1. In Section 4, develop stochastic linear bandit algorithm with ((vTT + min (CC, vdC }) regret, where is the feature dimension, T is the number of rounds, C' is the strong corruption measure, and Co is the weak corruption measure. These bounds are unimprovable.
2. In Section 5, we initiate the study of adversarial linear bandits with corruptions. We obtain
ÖldVT + vdCxc) and Ö(vdsT + dC') regret for weak and strong corruptions, respectively. We prove general reduction that efficiently handles gap-dependent misspecification with corruption-robus' algorithms. We apply our reduction to show that linear MDPs with gap- dependent misspecification are efficiently learnable (Section 6).
4. Finally, while the reduction in item 3 is general, it is unable to obtain the tightest possible rate for gap-dependent misspecification. We thus develop a specialized algorithm which, in the linear bandit setting, obtains the optimal rate. This resolves the open problem of Liu et al. (2023a).
In Section 2 we present our problem setting, and in Section 3, compare the corruption notions in previous and our work. More related works are discussed in Appendix A. In Section 4-Section 6, we present our main results outlined above.
2 Problem Setting and Preliminaries
We consider the corrupted linear bandit problem. The learner interacts with the environment for T rounds. The learner is given an action set A C. Rd. At the beginning of round f, the environment determines a reward vector 0r E Rdd and a corruption function c(()) A -> [-1, 1). which are both hidden from the learner. The learner then selects an action Gt E A. Then reward value
r; = a. 8, + (a,) + &, is revealed to the learner, for some zero-mean noise Ç, E [-1, 1J2. We
assume that ||a]|2 < 1, ||0:112 & Vd, and a 0g E [-1, 1] for any a E AA and any = 1, ......... T. We define 6, A |e (a)).
In the stochastic setting, the environment is restricted to choose 0, = 8* for all t, while in the adversarial setting, 6, can arbitrarily depend on the history up to round t - 1. The regret of the learner defined as
Regr max.6 A ΣT u
T B, ΣT
a.
"We assume both the corruption function and the noise are bounded for simplicity. All our results can be generalized to the case where the corruption is unbounded and the noise is sub- Gaussian. See the "additional note corruption" in Page 5 of Wei et al. (2022) for reducing this case to the bounded case.

---

Note that although the non- -on-staiionartty of 0e in the adversarial setting captures a certain degree of corruption, this form of corruption is limited to a linear form a (0, - 8*), which not as general as <a(a) that could be an arbitrarily function. Therefore, the corrupted linear bandit problem cannot be reduced to an adversarial linear bandit problem.
Let A(A) be the set of distribution over A. For any m). (1.2.....,,) p A(A), define the lifted covariance matrix Cov(p) = Bay a
Notation.
We denote [n]]
Taa"
(2d++) For A, B E Raxd define (A, B) Tr(ABT). E.[-] is the expectation conditioned on history up to t 1.
G-Optimal Design. A G-optimal design over A is a distribution p E (AA) such that || S d for all a E A. where G Eae p(a)aaT. Note that such distribution is guaranteed to exist, and can be efficiently computed (Pukelsheim, 2006; Lattimore and Szepesvári, 2020).
3 Two Equivalent Views: On Adversary Adaptivity and Corruption Measure
Previous works have studied corruption with various assumptions on the adaptivity of the adversary and different measures for the corruption level. In this work, consider both the strong and weak guarantees, which can cover different notions of corruptions studied in previous works. We provide two different viewpoints understand them. In the first viewpoint, the weak and strong guarantee differ by the adaptivity of the adversary, while in the second viewpoint, the two guarantees differ in the measure of corruption. Then we argue that the two viewpoints are equivalent.
Adversary Adaptivity (AA) Viewpoint. In this viewpoint, the corruption is specified only for the chosen action. That is, in each round I, the adversary only decides a single corruption level e, E Rzo and ensures [E[r,] (a,,8")
4G- We consider two kinds of adversary: strong adversary who decides &, after seeing the chosen action a, and weak adversary who decides & before seeing at. The robustness of the algorithm is measured by how the regret depends on > Et.
Corruption Measure (CM) Viewpoint. In this viewpoint, the corruption is individually specified for every action. That is, at each round t, the adversary decides (a) for all action A and ensures Eira la; = a] - (a, 8") = (a( for all a. The adversary always decides (-))) before seeing a, To evaluate the performance,
consider two different measures of the total corruption: the strong
measure Σ' [<<(a)) and the weak measure D max.c. (a)).
We argue that the two viewpoints are equivalent in the sense that the performance guarantee of an algorithm under strong/weak adversary in the AA viewpoint measure in the CM viewpoint, respectively. This is by the following observation. A strong adversary in the AA viewpoint who decides the corruption level 6 after seeing at can be viewed as deciding the corruption (a(a) for all action a before seeing a; and set c, = (c{(a)) after seeing 4, In other words, (a) is the corruption planned (before seeing a,) by strong adversary assuming 4, a, and the adversary simply carries out its plan after seeing dz It is clear that this is equivalent to the CM viewpoint with Σ (a=)) as the corruption measure. See Appendix B for more details. On the other hand, a weak adversary in the AA viewpoint has to decide an upper bound of the corruption level no matter which action a, is chosen by the learner. This can be viewed as deciding the corruption (a) for every action a before seeing de with the restriction [c.(a)] S G, for all a. Therefore, this is equivalent to using E max, [a] to measure total corruption in the CM viewpoint.
the same those under strong/weak
In this work, we adopt the CM viewpoint described in Section 2. With the CM viewpoint, for both strong and weak settings, the power of the adversary remains the same as the standard "adaptive adversary" (i.e., deciding the corruption function e-(-) based the history up to time t 1), and we only need to derive regret bounds with different corruption measures. All our results can also be interpreted in the AA viewpoint, the above argument suggests.
With this unified viewpoint, we categorize in Table previous works on linear (contextual) bandits based on the corruption measure, all under the same type of adversary. According to the definitions in Table 1, C and Coo correspond to the strong measure and weak measure mentioned above, respectively. It is easy to see that C' < {C'.,, } I Coq.00
Cms, where Coo and Csq are incomparable.
3

---

Table 1: Classification of previous works based on the corruption measure. Foster et al. (2020), Takemura et al. (2021), and He et al. (2022) studied the more general linear contextual bandit setting where the action set can chosen by an adaptive adversary every round. Foster al. (2020) and Takemura et al. (2021) reported their bounds in Csq and Cms, respectively, though one can make minor modifications their analysis and show that their algorithms actually ensure the Csq bound.
Measure
Definition
Work
Cms
T max (E((a)
Lattimore et al. (2020), Neu and Olkhovskaya (2020)
ss
(T E 1=1 max, ({)))) y (T Eラ=
Liu et al. (2024)
Csq
2a)
Foster et al. (2020), Takemura et al. (2021)
Coo
Σ x-1 maxa (ex(a)
Li al. (2019), Bogunovic al. (2020)
C
> ć |Ea(ar))
Bogunovic et al. (2021, 2022), He et al. (2022)
Table 2: Regret bounds under corruption measure C and Co.. See Table for their definitions. He et al. (2022) studied the more general linear contextual bandits setting, though it also gives the state-of-the-art C bound for linear bandits.
Setting
C.o bound
C bound
dVT + vdCxo (Algorithm 1)
dvT + dC
Stochastic LB
(He et al., 2022)
Upper bound
dV VdC (Algorithm 2)
VdT + dC (Algorithm 3)
Adversarial LB
d/T VdC (Lattimore et al., 2020)
dvT + dC (Bogunovic et al., 2021)
Lower bound
For stochastic linear bandits, considering the relations among different corruption measures, the Pareto frontiers of the existing upper bounds are OldVT + /dC'sa) by Foster et al. (2020) and Takemura et al. (2021), and Odv/ + dC) by He et al. (2022). The lower bound frontiers are 2(dvT VdCms) by Lattimore al. (2020) and Q(dv + dC) by Bogunovic et al. (2020). These results imply an O(d'T dCoe) upper bound and an (dd T + v xd lower bound, which still have a gap. In this work, we close the gap by showing an (dv + vdCx>) upper bound.
For adversarial linear bandits, we are only aware of upper bound σdd'T + VdCCq.so) by Liu et al. (2024), and not aware of any upper bounds related to Coc or C. In this work, show Ö(dVT+ + vdC,o) and Ö(VFT + dC)) upper bounds. The results are summarized in Table As in most previous work, we assume that Coc and C' (or their upper bounds) are known by the learner when developing the algorithms. The case of unknown Co or C' discussed in Appendix C.
We emphasize that before our work, for both stochastic and adversarial linear bandits, was unknown how to achieve Ödd'T + vdCx2) regret. To see how Coo is different from other notions such as C'ms and Csq. observe that for stochastic lincar bandits, while Ö(dVT + VdCsq) can be achieved via deterministic algorithms, it is not case for Ö(d'T + vdC.)). The reason that for deterministic algorithms, the adversary can control C'so to be the same as C, for which 2(dvT dC) is unavoidable. We formalize this in Proposition 1, with the proof given in Appendix D. This precludes the possibility of many previous algorithms to actually achieve the Ö(dVT + 2dC upper bound, e.g., Lattimore et al. (2020), Takemura et al. (2021), Bogunovic et al. (2020, 2021), He al. (2022).
Proposition 1. For stochastic linear bandits, there exists a deterministic algorithu achieving Reg, = Ö(dVT+ + VdCos), while any deterministic algorithm must suffer Reg, I(dvT + dCxc).

---

Algorithm 1: Randomized Phased Elimination (for stochastic Coo and C bounds)
Input: Z = vdC or dC, action space A C Rd confidence level 8.
2 Let A₁ = A and L - d /T)
for k = .... .d0..... do
Compute G-optimal design (defined in Section 2) over Aç. and let Gi = Ea Ph(a)aa". Define 4 = [(2 1)L + (2* 1)L] and my = | 2 L. for 1 E I. do Draw de ~ P& and receive v2 where E[rr] - ae 0 + cr( Define reward vector estimator O2 (m&Gi) " arr; and active action set:
Ast1 = {a E As: max b. bT0z 02 S 58
d log (LAT///)//)
DEAz
mg
my
4 Stochastic Linear Bandits
In this section, we introduce Algorithm 1, which achieves optimal regret for both C' and Coo.
Algorithm 1 is elimination- based algorithm. At each epoch k, it samples actions from fixed distribution Pk E ((AA), which is a G-optimal design over the active action set As. (Line 4). At the end of epoch k. only actions that are within the error threshold will be kept in the active action set of the next epoch (Eq. (1)). While previous works by Lattimore et al. (2020) and Bogunovic et al. (2021) have used similar elimination framework to obtain O(dv VdCms) and Odd + c) bounds, respectively, we note that their algorithms only specify the number of times the learner should sample for each action in each epoch. This is different from our algorithm that requires the learner exactly use the distribution ps sample actions in every round epoch As argued in Proposition 1, if their algorithms are instantiated as deterministic algorithm, then the regret will be at least ( dCxc). Thus, this subtle difference is important.
Note that to achieve the tight Co (or C) bound, Z = VdC.o (or Z = dC) has to be input to the algorithm to decide the error threshold. The guarantee Algorithm is stated Theorem 4.1.
Theorem 4.1. With input 7 = zo or = dC, Algorithm ensures with probability at least + Z log.). T).
1 that Reg, &
Algorithm 1 can also be shown to ensure that Reg, I O( dT log( (og((//)))))) Z log T), which could be smaller than the bound given Theorem 4.1 when |A| is small.
5 Adversarial Linear Bandits
In this section, we consider corrupted adversarial linear bandits. Although adversarial linear bandits have been widely studied, robustness under corruption is under-explored topic: there is no prior work obtaining regret bounds that linearly depends on either C.o or C.
5.1 C.c bound Adversarial Linear Bandits
Our algorithm (Algorithm 2) is based on sallo--the-regllriieedde Similar to previous works (Foster et al., 2020; Zimmert and Lattimore, 2022; Liu et al., 2024, 2023b) that utilize logdet regularizer, the feasible set is in [(d+1)x(d+1) which is the space of the covariance matrix for distributions over the lifted action space (Line 2-Line 3). At round f. the algorithm obtains covariance matrix H, by solving the FTRL objective (Eq. (2)). The action distribution is such that the induced covariance matrix is equal to H; (Eq. (3)). After sampling aj Pt and obtaining the reward rt, the algorithm constructs reward vector estimator 0 (Line 8) and feeds it to FTRL. The reader may refer to Zimmert and Lattimore (2022) for more details.
(FTRL) with logdet regularizer.
In typical corruption-free adversarial linear bandits, the learner would construct an unbiased reward vector estimator. However, in the presence of corruption, the learner can no longer construct an unbiased estimator. To compensate the bias, adopt the idea of "adding exploration bonus" inspired
5

---

Algorithm 2: FTRL with log-determinant barrier regularizer (for adversarial Coc bound)
Parameters: a max
Coe (Tlog(T)
log(T) T
and = VT.
2 Let Letp ((A) be G-optimal design over A. and let (A = (1-))= YP, p' A(A)).
Define feasible H Cov(p) E (A)). (Cov(p) is defined in Section 2)
Define G(H) log (H) and B = 0.
5 for / -= 1,2.... do
Solve the fixed-point problem Eq. (2)-Eq. (5).
aB 2 5=
E 00
H.- = argmaax (n (H, A,-1) G(H) where A, HEH
(2)
Pr E (A) be such that H. = Cov(
(3)
Σ. = Pi()aaa
(4)
B. = (B.,, E.).
(Defined in Figure la)
(5)
Sample Observe reward r; with E[rr] = a, 0r + c((a))
Construct reward estimator 0, = -- atr..
Function B' BONUS B, E): if B 3 then return B' = --1
8--1
27
else
Perform eigen-decomposition: B - B Ei=1 Aoae where {e i=1 are unit eigenvectors.
return B' = Bt (Een max Jus0,) Bi.
(b) Illustration for B, = BONUS E.). A psd matrix with eigenvalues (A,) 1 rep- resented as ellipsoid with radius (Vi.)
(a) The bonus function
Figure 1: The bonus function and its illustration
by previous work high-probability adversarial linear bandits (Lee et al., 2020; Zimmert and Lattimore, 2022). In the regret analysis, the exploration bonus creates a negative term that cancels the bias of the loss estimator. The bonus is represented by the B, in Eq. (5).
To decide the form of B,, we first analyze the bias. With the standard construction of the reward estimator, the bias on the benchmark action u can be calculated as (with 6, == max, (<)(a))
|u (E,(2, 0.) = =Iu a.
(a)) S Ex T
Ex[aaa] [aaaaaTTE,1100 ec ee|lullz, (6)
where E, the feature covariance matrix induced by Pt (defined in Eq. (4)). Below, we compare different bonus designs in previous and our work.
Bonus design previous work. Zimmert and Lattimore (2022), which is also based on logdet- FTRL but where the goal is only to get prob-broba bound, the bonus introduces an additional regret the form -ai||u I + a E. pe (a)allaal This can be used cancel off the bias in Eq. (6):
Etn e fe 1x-
Dt |u]| 1 a DE EmEapi(a))al E
odT, (7)
where we use AM-GM. Unfortunately, with the optimal a. this only leads to additive regret / E. VdCCs > VdC.o. which does not meet goal.

---

Bonus design in our work. To obtain the tighter vdC = vdΣ, c bound, our idea is to construct a positive-definite matrix B, such that B, = د for all 5 E [t] and add bonus B, B at round t. This way, the total negative regret on becomes -allu] Br and the cancellation becomes
T (E
Σ <r|lulls,- crllu| Br + a Σ Σ aEA
pr(o)laalB
S
E
a
CE, Br B
(8)
where we use BT 2 E for all and AM-GM. With this, it suffices to find B, satisfying our condition B, - . for r S t, and bound the overhead Σ (E,, B, - B(-1) by ((d).
turns out that there exists a way to inductively construct B, so that B, > ΣT¹ for all t S t and E (,e B, 1) S log (Br) = {dd). This is by letting B, to be minimal matrix such that B, = B and B₁ = Σ, By induction, this ensures B, ł Σ for all 5 S. f. The function B. = BONus(B,-1. Σ₂) is formally defined in Figure la. The geometric interpretation is finding the minimal ellipsoid that contains both ellipsoids induced by B and Σ," An illustration figure is given in Figure lb.
We adopt the fixed-point formulation in Zimmert and Lattimore (2022) (see their FTRL-FB) that includes the bonus for round t (i.e., B,) in the FTRL objective when calculating the policy at round t (Eq. (2)). Notice that Br, in turn, depends on the policy at round t (Eq. (5), where Σ. depends on Pt), and thus this forms a fixed-point problem. In the regret analysis, this avoids the "stability term" of the bonus appear in the regret bound. While the fixed-point solution always exists, it may not be computationally efficient to find. For completeness, in Algorithm 4 (Appendix F), we present a version that does not require solving fixed point but has a suboptimal dv/logTC additive regret. The guarantee of Algorithm 2 is stated in Theorem 5.1, with its proof deferred to Appendix F.
Theorem 5.1. Algorithm 2 ensures with probability of 1 8, Regr Ö(dVT + VdC,o), where Ö() hides log(T /8) factors.
5.2 C' bound in Adversarial Linear Bandits
To see how to obtain a C bound, we perform the bias analysis again. Similar but slightly different from Eq. (6), with the standard loss estimator, the bias action u's reward is bounded by
|u" (E, - - 0.) = (E[[="aaG S ||01 Ee [[<eels;-1e<<aa]]]]
Unlike in Eq. (6), we do not relax (at(a)) to E, max, [a) because we want the final bound to depend on C = E, (at)]. The idea to ensure that the sum of Eq. (9) over t can be related to C' to make ||ae ll s bounded by a constant poly (d), which allows us further bound Eq. (9) by poly(d) [d)]== |ee (-+))- Such a property holds in standard linear bandit algorithms that operate in the continuous action space where a, is a point in the convex hull of A, and utilize a more concentrated action sampling scheme. Algorithms that are of this type include SCRiBLe (Abernethy et al., 2008) and continuous exponential weights (CEW) (Ito et al., 2020).
For SCRiBLe and CEW, the work by Lee et al. (2020) and Zimmert and Lattimore (2022) developed techniques that incorporate bonus terms to get high probability regret bounds. The bonus terms introduced by Zimmert and Lattimore (2022) is similar to that discussed in Eq. (7), which only allows us to get Csu bound. The bonus terms introduced by Lee et al. (2020) allows us to obtain C bound, but the overhead introduced by the bonus terms is much larger, resulting sub-optimal regret bound. Indeed, as shown in Appendix J. adopting their bonus construction results in an additional regret of C. With several attempts, we are only able to obtain the tight corruption dependency dC using the bonus in Section 5. To use that bonus, however, it necessary to lift the problem to (d + 1)2 1)2 dimeennsil space. Unfortunately. existing SCRiBLe and CEW algorithms only operate in the original d-dimensional space, and as discussed above, we need them to ensure ||ae]]. I - (oly
highly
In order to combine these two useful ideas (i.e., our bonus design in Section 5.1, and the concentrated sampling scheme by SCRiBLe or CEW), we end up with the algorithm that runs CEW over the lifted action space (Algorithm 3). In order to simplify the exposition, assume without loss of generality
7

---

Algorithm 3: Continuous exponential weights (for adversarial C' bound)
Parameters: 7 1/TT, vdT + C 4 log((0d)"", /d/T. 2 for 1 === 1, ,....,7 do
Solve the fixed-point problem Eq. (10)-Eq. (13).
exp (n/h, ((A,-)))
aB
2 - 0,
(h) =
where A =
JIEECH exp (n(N', o (AA-))))
0.
(10)
Let E AHH) and E ((A) be the distributions of H E H and a E A, respectively, generated by the following (Z is a x (d 1) matrix):
0
0
0 1
0
h~ th H =
a
Heat1 = ZHeat1-
(11)
1
P=(a)1([aalls;1 S vd3}
(r(a)= SWEAP pr(aa)]((la")l) S vdB3da"
where E, = Eampe [aa J.
(12)
B: = BoNUs(B.-1,) Ex), where En = II Eawp. (aa [.
(13)
Sample pr, and observe reward with E(re] = a, O2 + cx(ae) Construct reward estimator 0, = En -
that A = (A). The lifted action space is H (Cov(p) : p A(A)) c (dd+1)x(4+1), The price of the lifting is that the "regularization penalty term" in the regret analysis now grows from (d/n)) (dd which gives the Vd8T sub-optimal regret.
Note that CEW requires the assumption that the feasible set a convex body with non-zero volume, but the effective dimension of H is strictly smaller than (d+1)² and thus have zero volume in (d+ To correctly write the algorithm, we introduce an invertible linear transformation (d(+1)² - R that maps an (d - 1)2 -i-ddimensioaal action set H to an m-dimensional one, where m the effective dimension of H. In Appendix we formally define this ø. The algorithm uses to map all lifted actions and reward estimators from I (d+ 1)x (d+1) to R
The exponential weights over the space of ((H) (see Eq. (10)). A point h ((H) sampled from the exponential weights can be linearly mapped to an action a E A according to Eq. (11). We use of to denote the exponential weight distribution in d(H). and use pt to denote the corresponding distribution in A. Instead of sampling a, from Pt, we sample it through rejection sampling that rejects samples with ||eel s-1 > θ(vd) (Eq. (12)). This technique was developed by Ito et al. (2020), and
this guarantees ||a, |x_ < ((Vd) O(vd)-which which is our goal as discussed in Eq. (9i-e keeping the clipped distribution P; close enough to the original distribution pt. This last property heavily relies the exponential weight distribution (Ito et al., 2020). The definition of the
on the log-concavity bonus term is similar that in Algorithm (Eq. (13)). The construction of the reward estimator (Line 7) and the way of lifting (Eq. (10)) are also similar to those in Algorithm 2. Again, we adopt the fixed-poime formulation where the calculation of the policy at time involves the bonus time t, which, in turn, depends on the policy at time I. It is unlikely that this algorithm can be polynomial time. As remedy, we provide polynomial time algorithm (Algorithm 6) in Appendix with much worse regret bound of ( VT + d The regret guarantee of Algorithm 3 given in the following theorem.
Theorem 5.2. Algorithm ensures with probability least 1 5, Regr Ö(Vd'T + dC). where O(-) hides polylog(T/6) factors..

---

6 Gap-Dependent Misspecification
Intimately related to corrupted settings are misspecifted settings, settings where our model class is unable to capture the true environment we are working with. For example, we might consider a stochastic linear bandit problem where the underlying reward function f(-) is nearly linear, i.e., there exists some 0 and e (-) such that (f(a) a aTO) S (a)) for each a. Indeed, in such settings, playing on our true (nearly linear) environment is equivalent to playing on the environment with reward mean 0 and with corruption e at each step. Thus, if we can solve corruption settings, it stands to reason that we can solve misspecified settings.
Here we are particularly interested in obtaining bounds on misspecified decision-making that scale precisely with action-dependers misspecification, e (a). While is relatively straightforward to obtain bounds on learning in misspecified settings for a uniform level of misspecification c 2 max.e e quis (a), obtaining bounds on learning with action-dependent misspecification have proved more elusive. To formalize this, we consider, in particular, the following gap-dependent notion of misspecification defined in Liu et al. (2023a).
Assumption 1 that some p > 0, denoting (a) max f(a') fa), we have for any a E A,
Misspecification (Liu et al., 2023a)). There exists some @ E IRd such
(f(a) - T 0| S p A(a).
We let M denote the original environment with reward function f(a) (with Reg? the corresponding regret), and Mo the environment with linear reward, a 0, (with Reg, the corresponding regret).
Assumption allows the reward to be misspecified, but the misspecification level for an action scales with how suboptimal that action is. This could correspond to real-world settings where, for example, significant attention has been given to modeling near-optimal behavior, such that it is accurately represented within our model class, but much less attention has been given to modeling suboptimal behavior. We assume access to a generic corruption-robut algorithm.
Assumption 2. with probability at least has regret bounded on Mo as
We have access to regret minimization algorithm which takes as input some C' and
Regt Mo S <C( + C2(,,T)
ifC 2 & E constants C,,, which may scale at most logarithmically with T and 1
eii (at). and by T otherwise, for C as defined above and (problem-dependen))
Assumption is essentially the guarantee of a corruption-robust algorithm in terms of strong corrup- tion measure (defined in Section 3). Note, in particular, that Assumption 2 only needs to obtain sub-linear regret guarantee in the known-corruption setting, and can have linear regret in the setting where the corruption level is unknown. We then have the following result.
Theorem 6.1. Assume our environment satisfies Assumption and that we have access to a corruption- robust algorithm satisfying Assumption 2. Then as long S. min (C2(4:T) -1),,, with proba- bility at least 28 we can achieve regret bounded as:
Reg M
< (TVT + 4/ log(1/1))) +
Theorem 6.1 states that, assuming our environment exhibits gap-dependent misspecification with tolerance p min (C, then achieve regret on the true environment bounded as the leading-order term of our corruption-robut oracle, Ci ( TV,, with additional overhead of only Ö(VT). This reduction is almost entirely box: it requires knowledge of C₁ (8, T) and (8, T), but does not require knowledge of p or any other facts about the corruption- roruust algorithm.
Remark 1 (Anytime Algorithm). The oracle of Assumption 5 must be anytime, achieving the above regret guarantee for any I' not given as an input. Though many existing corruption-rol algorithms take T as imput, the standard doubling trick can convert them into an anytime algorithm.
6.1 Optimal Misspecification Rate for Linear Bandits
We are particularly interested in how stringent condition on the misspecification level-how small a value of p-Theorem 6.1 requires. As we have shown, Theorem obtains the optimal misspecification level of dC', We then have the following corollary.

---

Corollary 6.1.1, Assume our environment is a misspecified linear bandit satisfying Assumption 1 with p S O (ToTg) Then instantiating Assumption with the algorithm of Theorem 4.1, we can achieve regret bounded with probability 6 as Reg M' 0 log(T/)))
While the regret bound of Corollary 6.1.1 achieves scaling of (ddvT), which is tight for linear bandits (Lattimore and Szepevvári, 2020), it is unclear its requirement on p of p I O(2) is optimal. The result below shows that it is not optimal because p S (a) suffices for OdvVT) regret.
Theorem 6.2. Assume our environment is a misspecified linear bandit satisfying Assumption I with Then there exists an algorithm that achieves, w.p. 1- 8: Regt M' S O(dy/Tlog() (og(()))))
Theorem 6.2 relies on a specialized algorithm for the gap-dependent misspecification setting, and improves on the best-known bound for gap-dependent misspecification in linear bandits, which va adapting the lower-bound instance from Lattimore et al. (2020), we show that achieving sub- sub-linear regret is not possible (Theorem K.2). These results jointly show that p = v is the best we can hope for. This disproves the conjecture of Liu al. (2023a) that p = (1) is possible.
requires p S ( (Liu et al., 2023a). Morcover, for p CT Ja for some logarithmic term cr.
Note that the reduction in Theorem 6.1 is not able to achieve a tight p-while reducing from gap- dependent misspecification corruption allows for black-box usage of existing algorithms, it requires more stringent conditions on the misspecification level than specialized algorithms for this setting.
6.2 SaapDeepnndent Misspecification in Reinforcement Learning
Theorem 6.1 is a corollary of a more general result, Theorem L.I, which applies to misspecified rein- forcement learning, where we there assume a generalized notion of gap-dependent misspecifiiction: for each policy n, EEM' . [_>= ch an)] S p- (Vo- Vo"). for Vū"" the expected reward of policy ग, and ég (s, a) measure of the misspecification at step ht state 8, and action a. To illustrate this general reduction, we consider the following setting, generalization of linear MDPs (Jin et al., 2020).
Assumption 3 (Gap-Dependent Misspecified Linear MDPs). Let (fs a) S A + Rd denote some feature map and P4n S Ee some measure which satisfy [|o(s, S 1, Vs, a, and J. (duu (s)ll2 I vd. Assume that the transitions Pa(: 8, a) on our true environment satisfy:
||Pa(- 8, a) - (Ø(s,a), a), pn (-)) S ch (s,aa)
for some (s.i 2 0 and I|P Ql the total variation distance between P and Q. Furthermore, assume that for any policy n, we have E (> ch emis (sn.
(sh. an) $ p -Vo Vo
We then have the following result. Corollary 6.2.1. Assume our environment satisfies Assumption 3 with p S Ō dh ). Then there exists an algorithm that achieves regret bounded with probability 1 - as Reg S <H(VBHTT)
To the best of our knowledge, Corollary 6.2.1 is the first result showing that it possible to efficiently learn in linear MDPs with gap-dependent misspecification. Note that under Assumption our MDP could be far from a linear MDP-we we simply assume that if we play a "good" policy, it appears as approximately linear. This result is almost immediate by instantiating our reduction with a known corruption-robet robust algorithm for linear MDPs (Ye et al., 2023).
Open Problems
remains open how to achieve d dC regret in corrupted adversarial linear bandits. The tight Coo bound for corrupted linear contextual bandits, where the action set can be chosen by an adaptive adversary in every round, also remains open. The best known upper and lower bounds for this setting are (d + dCx.) by He et al. (2022) and 2(dvT + vdC..) by Lattimore and Szepesvári (2020).
With the AA viewpoint in Section 3, our work first shows the separation between the achievable regret under weak adversary and strong adversary in corrupted linear bandits. An interesting future direction is to investigate similar separation in general decision making (Foster et al., 2021).
10

---

References
Abernethy, J. D., Hazan, E., and Rakhlin, A. (2008). Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263-274. Citescer.
Auer, P., Gesa-Bianchi N., Freund, Y., and Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32847778777.
Auer, P. and Chiang. C.-K. (2016), An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory.
Bogunovic, I., Krause, A., and Scarlett, J. (2020). Corruption-toleram gaussian process bandit optimization. In International Conference on Artificial Intelligence and Statistics, pages 107 1- 1081. PMLR.
Bogunovic, I., Li, Z., Krause, A., and Scarlett, J. (2022). robust phased elimination algorithm for corruption-tolerant gaussian process bandits. Advances in Neural Information Processing Systems, 35:23951-2399
Bogunovie, I., Losalka, A., Krause, A., and Scarlett, J. (2021). Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR.
Bubeck, S., Cesa- Biass-Bianch,,, N., and Kakade, M. (2012). Towards minimax policies for online linear optimizatiio with bandit feedback. In Conference Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings.
Bubeck, S. and Slivkins, A. (2012). The best of both worlds: Stochastic and adversarial bandits. In Conference Learning Theory.
Chewi, S. (2023). The entropic barrier is n-self-concordant. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2020-2022, pages 209-222. Springer.
Dann, C., Lattimore, T., and Brunskill, E. (2017). Unifying pac and regret:
Uniform pac bounds for
episodic reinforcement learning. Advances in Neural Information Processing Systems, 30.
Dann, C., Wei, C.-Y., and Zimmert, (2023). A blackbox approach best of both worlds in bandits and beyond. In The Thirty Sixth Anmual Conference on Learning Theory, pages 5503-5570. PMLR.
Du, S. S., Kakade, S. M., Wang, R., and Yang, L. F. (2019). Is good representation sufficient for sample efficient reinforcement learning? urXiv preprint arXiv: 1910.0301..
Foster, D. J., Gentile, C., Mohri, M., and Zimmert, J. (2020). Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33:11478-1144
Foster, J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arX.v:2112.13487.
Hajiesmaili, M., Talebi, M. S., Lui, J., Wong, W. S., al. (2020). Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. Advances in Neural Information Processing Systems, 33:19943-19952.
He, J., Zhou, D., Zhang, T., and Gu, Q. (2022). Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in Neural Information Processing Systems, 35:34614- 34625.
Ito, S. (2021). Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference Learning Theory.
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 2038.
Ito, S. and Takemura, K. (2023). Best-of-three worlds linear bandit algorithm with variance-adaptivy regret bounds. The Thirty Sixth Annual Conference on Learning Theory, pages 2653-2677. PMLR.

---

Ito, S. and Takemura, K. (2024). An linear bandits. Advances Neural Information Processing Systems, 36.
approach to best of both worlds in
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In International Conference Machine Learning, pages 1704-1713, PMLR.
Jin, C., Yang, Z., Wang. Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. Conference on learning theory, pages 2137-2143, PMLR.
Jin, T., Liu, J., Rouyer, C.,, Chang, W., Wei, C.-Y., and Luo, H. (2024). No-regret online reinforcement learning with adversarial losses and transitions. Advances in Neural Information Processing Systems, 36.
Kong, F., Zhao, C., and Li, S. (2023). Best-of-thre-woordd analysis for linear bandits with follow-the- regularized-leade algorithm. In The Thirty Sixth Annual Conference on Learning Theory, pages 657-673. PMLR.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Lattimore, T., Szepesvari, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in rl with generative model. In International conference on machine learning, pages 5662-5670. PMLR.
Lee, C.-W., Luo, H., Wei, C.-Y., and Zhang, M. (2020). Bias no more: high high-probability data- dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33: 15522-15533.
Lee, C.-W., Luo, H., Wei, C.-Y., Zhang, M., and Zhang. X. (2021). Achieving near instance- optimality and minimax- optiimlllyy stochastic and adversarial linear bandits simultaneously. In International Conference Machine Learning, pages 6142-6151. PMLR.
Li, Y., Lou, E. Y., and Shan, L. (2019). Stochastic linear optimization with adversarial corruption. arXiv preprint 1909:0099002009
Li, Y. and Yang, L. (2024). On the model--iiseeciiicaaiion in reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 2764 2772. PMLR.
Liu, C., Yin, M., and Wang, Y.-X. (2023a). No-regret linear bandits beyond realizability. arXiv preprint ar 13252
Liu, H., Wei, C.-Y., and Zimmert, J. (2023b). Towards optimal regret in adversarial linear mdps with bandit feedback. arXiv preprint arXiv:2310.1
Liu, H., Wei, C.-Y., and Zimmert, J. (2024). Bypassing the simulator: Near-optimal adversarial linear contextual bandits. Advances Neural Information Processing Systems, 36.
Nesterov, Y. and Nemirovskii, A. (1994). Interior-point polynomial algorithms in convex program- ming. SIAM.
Neu, G. and Olkhovskaya, J. (2020). Efficient and robust algorithms for adversarial linear contextual bandits. In Conference Learning Theory, pages 0069-3068. PMLR.
Pukelsheim, F. (2006). Optimal design of experiments. SIAM.
Seldin, Y. and Lugosi, G. (2017). An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory.
Seldin, Y. and Slivkins, A. (2014). One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning.
Takemura, K., Ito, S., Hatano, D., Sumita, H., Fukunaga, T., Kakimura, N., and Kawarabayashi, K.-i. (2021). parameter-free free algorithm for misspecified linear contextual bandits. In International Conference Artificial Intelligence and Statistics, pages 3367-3375. PMLR.
12

---

Wang, R., Salakhutdinov, R. R., and Yang, L. (2020). Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135
Wei, C.-Y., Dann, C., and Zimmert, J. (2022). A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096, PMLR.
Wei, C.-Y. and Luo, H. (2018). More adaptive algorithms for adversarial bandits. In Conference On Learning Theory.
Ye, C.. Xiong, W., Gu, Q. and Zhang, T. (2023). Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International Conference on Machine Learning, pages 39834 33863. PMLR.
7anette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978- 10989. PMLR.
Zhang, W., He, J., Fan, Z., and Gu, Q. (2023). On the interplay between misspecification and sub-optimality gap in linear contextual bandits. In International Conference on Machine Learning pages 41111 11-41132. PMLR.
Zimmert, J. and Lattimore, T. (2022). Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pages 3285-3312. PMLR.
Zimmert, J.. Luo. H., and Wei, C.-Y. (2019). Beating stochastic and adversarial semi-bandie optimally and simultaneously. In International Conference Machine Learning.
Zimmert, J. and Seldin, Y. (2019). An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 467-475. PMLR.
13

---

Appendices
Related Work
15
B Equivalence Between AA and CM Viewpoints for Strong Corruption
16
The Case of Unknown Co., or
16
D Proof of Proposition
16
Proof of Theorem 4.1
17
F Proof of Theorem 5.1
20
Computationally Efficient Algorithm for Adversarial Co Bound
25
H Proof of Theorem 5.2
26
Dimension Reduction for Continuous Exponential Weights
J Computationally Efficient Algorithm for Adversarial C' Bound
30
J.1 Preliminaries for Entropic Barrier
J.2 Auxiliary Lemmas
31
J.3 Regret Analysis
32
Gap-dependent Misspecification
35
L General Reduction from Corruption- Robust Algorithms to Misspecification
38
M Auxiliary Lemmas
42
14

---

A Related Work
Model Misspecification Theoretical works on bandits or RL often assume that the underlying world is well-specifted by a particular model. Algorithms that are purely built this assumption are vulnerable to potential misspecifications. Therefore, some works, besides proposing the main results, also discuss the case where the model is misspecified, such as Jiang et al. (2017); Jin et al. (2020); Zanette et al. (2020); Wang et al. (2020); Li and Yang (2024). These discussions, however, usually assume that the amount of misspecification has uniform upper bound for all actions/ / states / policies, and the performance degradation is proportional to this uniform upper bound.
For settings like stochastic linear bandits and stochastic linear contextual bandits, it was also found that some widely used algorithm such as LinUCB cannot achieve the tightest guarantee under misspecification (Du et al., 2019). Therefore, a line of work developed better algorithms that have optimal robustness against misspecification, such as Lattimore et al. (2020); Foster et al. (2020); Takemura et al. (2021).
While most work focus on the stochastic setting, Neu and Olkhovskaya (2020) took a first step in studying misspecification in linear contextual bandits with stochastic contexts and adversarial rewards. They established near-optimal regret dependencies on the amount of misspecification.
Gap-dependent Misspecification Gap-dependent misspecification is setting where the amount of misspecification for an action is bounded by a constant times that action's 's sub-optimality gap. To our knowledge. this setting is first studied by Liu al. (2023a) for linear bandits. Another related work is Zhang et al. (2023), which assumes that the misspecification is bounded by constant times the minimal sub-optimality gap among all actions. Although this assumption is more restrictive, they handle the more general linear contextual bandit setting, and derive instance instance-dependent logarithmic regret bounds.
Corruption-rouust Bandits The guarantees on model misspecification is rather pessimistic in the sense that if the misspecification is time-varying, and large misspecification only appears in a few rounds, then the existing guarantees for misspeicifcatioon still scale with the largest misspeicification. To refine such guarantee, previous works have consider different notions of time-varying corruption, and established more fine-grained regret guarantees. These include So. Csq. Coc, and discussed in Section 3. Among them, Csq. and Coo are usually studied under the "wwak adversary" framework where the adversary decides the corruption before seeing the action chosen by the learner. On the other hand, Csq and C' are usually studied under the "strong adversary" framework where the adversary decides the corruption after seeing the action chosen the learner. In Section 3, we provide a unified view for them so that they can both be regarded as weak adversarial setting but with different corruption measure.
The algorithms of Foster et al. (2020) and Takemura et al. (2021) achieved the optimal bound with respect to Csq for stochastic linear contextual bandits (i.e., dvT - VdCsq), and He et al. (2022) showed the optimal bound with respect to C' (i.e., dvT + dC'). However, it is still unclear whether the tight dependency on Coc is vdC,o dCoc.. In this paper, answer it for the context-free free linear bandit setting, showing that dvT + vdC.o is achievable. However, the question remains open for linear contextual bandits.
For the adversarial setting, Liu et al. (2024) showed dP + VdC bound for linear contextual bandits with stochastic contexts and adversarial rewards, which can be improved to d + VdCsq when specialized to adversarial linear bandits. To our knowledge. no Co or C' bound has been shown for adversarial linear bandits, and our work make the first attempts on them.
We remark that for A-armed adversarial bandits, it is easy to see that v VTT + bound is achievable simply by running standard adversarial multi-armed bandit algorithm that handles adaptive adversary (e.g., EXP3 P by Auer et al. (2002)). The work of Hajiesmaili et al. (2020) is the only one that we know to obtain C' bound for adversarial bandits. They showed a VTT + AC' bound for A-armed bandits, which is tight.
The study of the best-of-both-woot world problem was initiated by Bubeck and Sliykins (2012) and extended by Seldin and Slivkins (2014); Auer and Chiang (2016); Seldin
Best-of-both-worldd Bounds
15

---

and Lugosi (2017); Wei and Luo (2018): Zimmert and Seldin (2019); Zimmert et al. (2019); Ito (2021); Ito and Takemura (2023, 2024); Dann et al. (2023); Kong et al. (2023). The goal of this line of work is to have single algorithm that achieves a Õ(VT) regret when the reward is adversarial and (log T) when the reward is stochastic, without knowing the type of reward in advance. These results should be viewed as refinements of the standard adversarial setting but not the corruption setting considered in our work, though they also used the term "corruption" in their work.
For example, Lee et al. (2021); Ito and Takemura (2024, 2023, 2024); Dann et al. (2023); Kong et al. (2023) studied the best-of-botte sotoof--ooh-worldd linear bandits problem. The underlying world could be stochastic (0;- = 0* for all 1) or adversarial (0, 's are arbitrary). Their algorithm achieves bound of (dd (og(T)) (T) A in the former case, where A is the reward gap between the best and the second-best arm, and (dd/T) in the latter phase. They also define the corruption C' Eg max, la T T0, - 0+) and show that their algorithm achieves a regret of (dl log(T))A + v di (og(T)C"/A), Compared to our setting, their corruption is in a more limited form, but their target regret bound in the stochastic setting is tighter than ours.
B Equivalence Between AA and CM Viewpoints for Strong Corruption
We show that strong corruption in both definitions is equivalent, that is, for any adversary having strong corruption = E, [el from AA viewpoint, there exists an adversary using the equal amount of strong corruption De G (ax) from CM viewpoint, where |<a| = (<)(a)) for all 1, and vice versa.
Assume that < cHHr1,, a,) is the function used by AA strong adversary to decide the corruption at time f, where H4-1 is the history up to time -- and ae is the chosen action at time t. Then we -H,,,1, a), Va for the CM viewpoint, thus |ez| = |e( (e 1, az)] = [a)() Note that the function (-) only depends on the history up to time t 1, so the definition of e is known to
define (a) _
adversary before observing ae The other direction of this equivalence is achieved by setting the
corruption in AA viewpoint as & = (ot). Note that since a, known to a strong adversary in AA viewpoint, 62 is also known.
C The Case of Unknown Co or C
In the corrupted stochastic setting, Wei al. (2022) developed black-box reduction that can turn any algorithm achieving 31 /T + 82 + 8gCoc regret with the knowledge of C.o into algorithm achieving (T) ( + 32 + 3zCoz) regret without knowledge of Coc. This reduction directly applied to our stochastic C.. bound result (Theorem 4.1), which allows us to achieve almost the same regret bound without knowledge of Coc. The idea of Wei et al. (2022) has been extended to the adversarial setting by Jin et al. (2024) (see their Section 4). Similarly, for the adversarial setting, one can turn any algorithm achieving 31 T + B2 + 8o regret with known Coo into one achieving log(T") x (8, B + 32 + o0) regret without knowing Co.. This can be directly applied to our adversarial Coo result (Theorem 5.1).
be
The case of unknown C' is quite different. It has been proven by Bogunovic et al. (2021) that is impossible to achieve a bound that has linear scaling in C' (c.g., 31 VT + B3 + 3gCC) for all C simultaneously if C' is not known by the learner. This is also mentioned in He et al. (2022) again. Hence, almost all previous work studying C bound assumes knowledge on C. If C is unknown, simply setting C = VT as an upper bound of C' yields a bound of O(VT+ if < VT indeed holds, then C' is correct upper bound, so the regret can be bounded by O(VT + C) = O(VT): if
C> T, then simply bound the regret by T < OCC2).
D Proof of Proposition
First, we argue that there exists deterministic algorithm achieving Õ(dVT + vdCaa) upper bound. The algorithm of Takemura et al. (2021) is such an algorithm, although they only showed an upper bound of (dvT + VdCms). To argue the stronger O'd'T + vdCsg) bound, we only need to slightly modify their analysis: In their proof of Lemma 2 (in their Page 6), the original proof bound
16

---

the per-step regret due to the misspecification as the following (the calculation below uses their original notation):
Σ
c (r, Σ
(V
TEVEM
TEVe,
- <v I (e (i..l V2
EV 1
- Ō(VVd).
(by their Lemma
We tighten their analysis by doing the following:
Σ ((1))=+(1+) ( Vi1)) $
Σ
G(G))2
Σ TEV.,.
rEVt
rEvi.
Σ ((t))
v:(i)TVi11,,000
rEWia
Σ cr(6)) FEVia
222
Σ cx(t)3 TEV,,,
(by their Lemma 1)
Since the regret for every step in t.. can be bounded by this value, when summing the regret over Frs,, one can get a regret of order
( JayTriaa
Σ cr
TEWT+I,
Further summing this over (there are logarithmically many different s) and using that [7] U. V1+1, and using Schwar,, we get / /dTT ET ci)) = /dCisa bound.
To argue that any deterministic algorithm must suffer least 2(dvT dC&c) regret, we only need to use the lower bound instance of ((d/T + dC). At the beginning of round the adversary simply change the corruptions (a) to be zero for all of (the adversary knows what a, since the algorithm is deterministic). This makes C Coc. and thus the lower bound Q(dvT + dCoo) holds.
E
Proof of Theorem 4.1
Lemma F.I.
With probability at least 26, for all for all E Ak.
1(b, - -0)1 s 0011544 dlog(IA[T/))
min VdC',
m.
Proof. Let E.[-] be the expectation conditioned on the history up to round 1. We fix and and consider
X, = bT (maGr))taa
17

---

fort E Ip. Notice that ΣiE,, Xe = b 0 and
Σ 1
E,
[i,] Σ b" (m, 'B lalaa 0" + +a(a)))
= b 0r + b (m²Gk)
Σ SEI,
Es [are:(at)].
Also, by the definition of Gk, have X b (m& S ma
| |1 laalaa"'
d
my
Thus, by Freedman's inequality, with probability at least
| the following holds:
(b, Og 0-) 0²>|=
Σ RELL
X
Ex Xx] + b (mmmaaa)
Σ BEI
Ee [(rer(ar)]]
LEIA
[A[T
d
|
log
Be [X?] +
log
+
b (m+GG)
Σ Eg [are((as)]
8
mp
8
TET.
TET
term,
term:
We bound term; by
term
log( log((A(T/5)
Σ
E, [b (m+
aaaa (m,GG)-
tET
log([ [og((((1//)
1
Σ G dlog([AA]]])
m
my
EEIx
and term, by
Σ Σ (a)())c(a)b Go'a
term
mi
LEZI aE
Σ (a(a)c((a2
Σ
pa(a) (bT Gx a)))²
m&
TET,
nE.AL
aeAr
Vdc
max max (a')va
mA
EEIx
1
term
E, [er(ar) bb G ail
mk T.
Σ
ce(ar) |bTTG GZtatl +
log
Ee (e((:)) 1 G a
mk SEIx
mi
DEI2
(ex(ur))
G as
[AI[T)
+
log
(Freedman's 's inequality)
8
d
[AlT
AAT
Σ <c(at)
+
log
E, GT G a G +
log
773 IEI
mk
ma
FEZx
dC
1
log
[A[T 5
Σ 6t GTG
d m&
log
|
m
mi
8
tEI.
dC
dl Alog(AA[TT))
d
AATT
log
m.
m.
mi
18

---

Thus, for any b E Ak. with probability at least
TAIT
(b,0x 0 - 2/
(log(1AAT//)
2d
log log(1A(T/8) + m&
1
min { (Tarracy
mh
mh
- $VV
log( (og((_A(7/8)
min {vac', daC",.c].
(m, 2 dlog((AA/0)
me
Taking a union bound over and E A4 finishes the proof.
Lemma E.2. Let a* = argmax a' 0* Then with probability at least 1 - 26, a" Au for all k.
Proof. Suppose that the high-probability event in Lemma E.1 holds. For any k. if a" As, then for any E Ak.
b 02 a² 02 6 - aa- 0 + (+. 0+) + aa (0 -00)
dloog(
(AT/( mint Sin(vad',,o ,dc}
51+2 41/
m&
mg
By the definition of As+1 in Eq. (1), we have a* E As+1 The lemma is then proven by an induction argument.
Proof of Theorem 4.1. We first calculate the regret in epoch & > Lemma E.2 holds.
assuming that the event in
Σ T
max a 0- - a,
maxa 0 a, 04-1)
2m max Ta (0k-1 00) -0)) acAr
aEA
REIn
(v
dlog(( (ATT/8)
min min(Vad',,de mk-1
$ my O
mx-1
=o(ydma (oog(A////) minf (VTC) ,dC)).
(ViC",dc)).
Summing this over and using that m² d dllo((AA(T/8), we get
T
Σ
- aT so ( (
+ min(VddC, ,C) log T)
max aeA
Notice that without loss of generality we can assume d T (otherwise the right-hand side is vacuous). Using this fact gives the desired bound.
From Exercise 27.6 Lattimore and Szepesvári (2020), the e-covering number of bounded by
(6d) Let C(A, be the c-net of A, then have JC(A, 6d] < T Thus, when [A] 2 T use C(A, + as Ai Algorithm to conduct phase elimination. In that case, following above proof, we have
(1 aTiog ( (c(4, T
6d
max T a, 0r ())
0
T/8) + min minnVVcc",de dC) log T
< 0 (d (Tooog(T/)) + min(/aC dC) log log
19

---

From the definition of covering number, there exists a a. E C(A, 6d
such that
maxa T - (a.) T 0" v 6d
aEA
T
We have
T
T
max a T0 0+ REA
max T aEC(A, T
(a,)](r 0 (at) T
Σ
(a (a:)
max a TT
max asd
+
aEC(A, 77)
1=1
t=1
$ 6d.
Thus,
maxa aEA
a0
+ min(VdC' dC3 logT)
F Proof of Theorem 5.1
In this section, we use the following notation:
0
1
aB.
aB 0
7: =
D:
0
Algorithm is equivalent to the FTRL update:
{
G(H)
H.
argmax HEH
H.> 7. DD.
H.
D.
(14)
11
1=1
Algorithm 4 is equivalent to
G(H) (1.5 +D)
argmax H
(15)
HEH
n
By the standard analysis for FTRL algorithms (e.g., Theorem 2 in Zimmert and Lattimore (2022)), the regret bounds of Eq. (14) and Eq. (15) are given by the following lemmas, respectively.
Lemma F.1. The update rule Eq. (14) (Algorithm 2) ensures for any U E H.
Σ
U H
G(U) mingen G(H)
T Σ
H, H.)
CU-HA H. D.) -
Σ
max
H
H,
HEH
1=1
Lemma F.2. The update rule Eq. (15) (Algorithm 4) ensures for any U H.
T
Σ
U Ha9d
1
GUU) minHem G(H)
Do Do (, H,
Σ U H H.
Σ HEH
max
(H- (H-H H. +D)
"
1)
consider an arbitrary comparator p. E ((A) with u, Ea-p, [a]. Define p = (1 - 7-pp + 7p.
We have p (A),,, and define Ea and U Cov(p). The regret with respect to p, be
20

---

decomposed as the following: With probability at least - 6,
Reg, (p.)
(16)
(U+ aes 0t)
T
Σ
(u a2, 01) + 27T
1=1
T
(u - Te, O₂) + (VTlog(1/5)
+ +2y
(Azuma's inequality)
T
Σ
Or E.(0.l)
+
+
u Lt, E, 01) 0z
Σ
U H. 7o) +0 (VTlog(1/)) + +xT)
Deviation
FTRL
(17)
By Lemma F.I, the FTRL term can further be bounded by
FTRL < G(U) min G(H)
T
T
HH(H, H.)
Σ
U
D
max HH H,, MEH
E=1
Penalty
Bonus
Stability
(18)
In the following five lemmas, we bound the five terms Bias, Deviation, Penalty, Bonus, and Stability. Lemma F.3.
Bias I Coc max |ulls, + vdC.o.
8
Proof.
E, [(u- It, (rftacc((at)) S E, V (u x²)) T ( (E, (u xz)
(u x1) T 25 Er [ara c?(at) M; (u xz))
$ | xells,
s 4 - + ||11|151
s de: + E ||u||x
(2e )xre
Thus,
E. E ara [al)) +E. Σ u Dz Ex -E,'a acce(ai)
Bias
Nz, 0,
$ C. max |ullx, VdC.o.
Lemma E4, With probability of least 5, we have
12V/log(T/6)
12d (Tg()/8)
Deviation < max ||ا|ا
12 12 122/lloge (ogg(T/)
+ 12 dT (Tg(6))) +
V
v
21

---

Proof. Notice that
(u 22,01) 0r)
< [u xt) T 12yya
1 u xzl Eell i|leelxx,
u sells.-
By the strengthened Freedman's 's inequality (Lemma M.3), with probability at least - 6,
Tt, [e] 0.) u
Deviation
1=1
+ Σ Ee (u- 22. 22. log(d4T4/0) +
Vd
33
max ||u xı11,, log(d"T**0))
V7
+ 12 12vdlog(T/5) < max ||u xe 11s 12 [lggT/o(
v7
I max ||u||s (2V/Tlog(T/))- 12vdlog(T/0)
+ 12 dl log(T/ō) + 12d (Tg()
Lemma F.5.
Penalty < (d+ l)log(()
aa a
Proof. Define Ho Eawp
By the definition of the feasible set H. for any H H.
H Ho d+1 Ho and H
(d + H) Thus, Penalty can be upper bounded by
T
G(U) minHem G(H)
G (
d+1 Ho) G G(d + 1)H T
det ((d + +1)Ho) 1 log
(d 1) log(T))
<
17
det (2) Ho)
Lemma F.6.
Bonus < 33d a max -
t
Proof. Given Earopo [aa] J] > Eampo [a] La]lEarpp [a] T uu? we have
T
Σ
U. D.) = (Eanpu laa 1, 2 (uu" aBBr) = allulla..
1=1
Recall that B = Dj and for > 2,
B
Σ
B
(wuld unit eigenvectors)
d
B,
B
Upi
B²-1"
En 1152 = I)
1=1
B, B
Σ
max Des 1 Berehh
B
(19)
22

---

which ensures B₁ = B1-1 and B, = ET! By induction, it leads to By 2 _r for any t. This implies
|ull 2 max ||
Thus, (U,)) 2 max, ||ul
Next, we upper bound Ei=1 (H,, Di). First, notice that Hi,Di - aTr(E,B.) = Tr(I) = ad. For t 2 2,
(,. D.) aTr (M, (B.--(-1))
-1
B Σ Anerii
B BR
Σ maxtArc - 1, Oerrus B (by Eq. (19))
= =TT
Σ max - 1, 1.00mu07
aTr
d
0
0
max
des"
im
<
max dei 0}.
We also have
log det (By) log (Bt-1)
det (B,_1) det (Ei max Aes, 1owees det (B
log
det B det (Et- (oek) det B det Edd max 100ei log
det Σ Di=z Uestit)
maxflog decr 0}.
Thus.
Σ (., & ad log det (Br) a log det (B,) I ad log det (Br).
(20)
Finally, we bound log det (Br). Since E, = E. pa(aaaa 2 77 p(a)aa by Theorem of Bubeck et al. (2012), we have Σ, > 3/ and Σx 1 $1 for all t. Thus, B, = Ej1 3 S.. Below, we use induction to show that B, = id I. Assume B, 1 (t-1)d I. Then,
B = B
Σ max Aei Berees
B
3 B
Σ (Aes 1)ureu T
B
d I
(1- 1)d
= td
Σ-1
B x q
I.
7
7
23

---

By induction, we get Br 3 Id I and log det (Br) I 2d by setting
d VT
Overall, by
Eq. (20), have
T
Σ
H Di) S 3od)og(T)
Combining the upper bound for Ei=1 (H Dz) and the lower bound for Ei (U, D,) finishes the
proof.
Lemma E77 With probability at least
Stability SO diiT nd log(11))
7
Proof. For any ps define (p)) Ba-pla] and
Cov(p) + ((D)u(p) u(p)
Cov(p) Earpl(a --(p)(aa ((p))()-(p))))
Cov(p) Eawp
u(()
+ hh For any
h
Cov(pr) + x250
Dtt
given H.
we have
hd
1
It.
DG H, ( H.)
11:re hll(oo(p.))-
H Ht)
H He, (1)
(Lemma M.1)
211
27
112 -hllCov(p.))
h 5t, 0.)
21
I 1ll 0110r11e 011l
(AM-GM)
mrra a Ex Cov(p:)
S 1/|aa 1| -ل-
(rd S and Cov(p:) 3 E,)
By Freedman's inequality, since E,
||ax |رية
d, and nlleel?2.. s nd with probability at least
1 6, we have
T
50 (driT++ ndlog(1/0)
2 Eイ
7
at
Proof of Theorem 5.1. Using Lemma Le3-m F.7 in Eq. (17) and Eq. (18), we get
Regr
s o dlog(T)
ndT + lol)g) + v dT (ogg(()
+ un Idloo(1/0) dllo((T/))
+ VdC +T))
12 12 Tlo((//)) 12Vdlog(T/o)
+ max ||ul|s
Coo
max |
V7
< O ddlog(T)
ndT + add + dI (T/) dlog(T/5)
+ myd 1og(1/1)
7
(Coo)2 Tlog(T/8) +
(T/8)
VdCco + t
(AM-GM)
ax a
7a
Therefore, the choice
d .
max
Co
VT)
and 17 Vlogg())
and
/lgg(T) gives
(Tlog(TT)
Regr 5 (dVTlog(T/8) + Coc Volog(())
24

---

Algorithm 4: FTRL with log-determinant barrier regularizer
Parameters: a max
C.c (Tlog(T)
VT f.
min
log(T)
.V /loe(T) } aaand y= VT
160x
2 Let E ((A) be John's exploration over A, and let (,(A) - {p:p- = (1 - ->)p'- + +op, 1' E A(1)].
3 Define feasible set H = Cov(p) : (p (4))
Define G(H) log det (H) and Bg =.
for f 1,2........ do
Compute
a
- 0,
H. argmax (n (H, G(H)) where θ
HEH
2
1
-
01
0
Pt E ,, (A) be such that H, = Cov(pr);
Σ,
Σ pila)aa
aEA
BONUS(B Eg). (defined in Figure la)
7
Sample a ~ Pt. Observe reward ra with E[ra] = a, 0, + c((a)).
Construct reward estimator 0, E, 0.r.
end
G
Computationally Efficient Algorithm for Adversarial Coo Bound
Most proof is the same Appendix F. Namely, we follow Eq. (17) in Appendix F together with different decomposition
T
T
T
Regr (p+) S
Σ
Tt. O2 - Br (O.))
+
Σ
E.
O2
U H H,, +0 ( (VTlgg(10)) + +TT)
2m1
Deviation
FTRL
(21)
By Lemma F.2, we can further bound FTRL by
G(U) minHEN G(H)
FTRL
U H D.)
Penalty
Bonus
T
Do(H,HO H.)
Do Do(H, H.)
max HEH
H H H.)
max MEH
(H, H. - D
2m
21
Stability-1
Stubility-2
(22)
Among the terms above, Bias, Penalty, Deviation, Bonus, and Stability-1 follow the same bounds as Lemma F3, Lemma F.5, Lemma F.6, and Lemma F.7, respectively. remains to bound Stability-2.
Lemma G.1. If < 16vdo then
Stability-2 < Sna²d d.
Proof. From the analysis of bias term and H, and D, are both positive semi-definite, we have
(T.(H.D,H.D) = ay Tr (B, B, E, (B, B,- s avd
25

---

where the last inequality is due to E,1 = B₁ BL-1- Since S 1 probability of at least 6, we have
by Lemma M.2, with
16vda
Stability-2 < 8n
Tr (HD,D,
t=1
S 8n02
Σ
Tr (E, (B. E4 B,-1))
< 8na2d
where the last step follows the similar analysis in Lemma F.6.
Proof of Theorem 5.1 (Option II). Using Lemma F.3-Lemma G.1 in Eq. (21) and Eq. (22), we get
Regr = O (dlog(T) + ndT + da log(T) + v df (og((T/))) + dllo((//)
+ 1dlog(1/0)
+ na 2d
V7
(Coo)² Tlo((T/6) d log (T/6)(T/))
vdC + yT
a
aa
By choosing max
Con (T)
VT and min
Vlg((T) 160
loR(T) and y vT
could ensure
This gives the final regret O (d + dCoc v vlog'o 7
The
16v
additional dd factor comes from the additional condition for the Stability-2 term
H Proof of Theorem 5.2
Similar to before, we define
0
0
aaB;
BB 0
k: =
D, =
10
0
0]
and 2t = Earpp [a], 8, Bung [a]. We perform the regret decomposition as the following.
T Σ (u a4, 0z)
Regr
1=1
(u Fz. 0,) + Σ
(x. Br, 0.) + Σ (5. or, 0,)
1=1
(u Fr. 01) + (
/ T Tlog(1/8)
T
T
T
Σ
u Zt. 02 -0, Er(Oa)
+
u
Ft, E. 0.
0.
Σ
u - J4, 8.) +0(TT + T (Tog(11)5))
Bius
Deviation
FTRI.
(23)
26

---

The FTRL term can be further bounded as the following.
FTRL
T
Kr Ku-a, a, 8.)
Banpi
1=1
T
Σ
EH rq:
IU -
-HH,7. H.7H
1=1
d log T
1
+
En Rngq (exp (n7 (H,5)) 17 (H,7.)
1] +
Σ
R B [ UD)
11 1=1
(by Theorem 1.2)
d² log T
Eacop
exp -
E Eanp
|aalie B
| 2
71
Stability
Bonus
(24)
In the following four lemmas, we bound the four terms Bias, Deviation, Bonus, Stability. Lemma H.1.
Bias < (max ||=; -ullz;))
(VdrT++ Tlogo((1 + vd3c).
t
Proof.
Bias
Tt, 00 -E((0.)
u 23, 0: - -E,'En EE [ara,]] ] 0, + +- E, (are((a)))
T
T
uu Iz, Σ +
Σ
2t, - -E, E, (are((oo)))
(E, = >I + E.(a,a ))
1=1
Σ t=1
| u/1 |لا5ا 110 11a15 +
Σ
|| u| بلاااا Es |la 1ss [ea(ai]]
t=1
d
T
|ate ulbs.
(7V/
Eg ||at Ils lec(ar)]
max
② 7I and 1101122 s Vi)
max |a wlls,1)
VaNT vd3 Σ E. [lea(a))]]
T
< max |ate ulls,))
VoNl 2 Tlg((1/)) + Vd. Σ
les [es(ar))
(Azuma's inequality)
Lemma H.2.
Deviation < 0 (axx |/u 24 1s d3vT 1og(T/6))
27

---

Proof. Notice that
(u - 21, 0i)
- (u xt) T "Ejtay ac
< 1|u x 11oelss,1
S vd rells-".
By the strengthened Freedman's ' inequality (Lemma M.3), with probability at least 6,
T
Deviation
1
It, [r] 0.)
E=1
50
3
3,
Σ
(u Ies 8 log(T"/0) 2V max | - xells, log(2 /8)
1=1
s 0
max I|u xz l|s id3 .d3V log(T16))
(using the assumption d S T)
Lemma H.3.
Bonus
3ad a max ||ul
Proof.
The proof the as in the logdet case. See the proof of Lemma F.6.
Lemma H.4.
Stability I (O('' log T).
Proof.
exp (a. - -n
Stability
Eacpp
Since of is a log-concave distribution, so are and pt, which further implies that 17 (a.0.) follows log-concave distribution. Furthermore,
Eaxpi 2 [1, 0.)² < Eunpp 1,a aa Ex a s 27 1 2x2 <
<a<(,,)))
100'
where we use Lemma J.2 in the second-last inequality. By Lemma of Ito al. (2020), we have
T
T
T
Banpi
exp
(o(a.:)) - n (a. -1 1
s 17
Eanps (a.
2n
|
1 S
2m dT.
Proof of Theorem 5.2. Combining Eq. (23), Eq. (24), and Lemma H.1, Lemma H.2, Lemma H.3, Lemma H.4, we see that the regret is bounded by
c
ndl + max 1/u xolls, (dVT VdC) + dC' + ad al| alluii2
11
δ ndT + ad) + TT+
df
(AM-GM inequality)
11
a
Choosing optimal and leads to d dC).
28

---

I Dimension Reduction for Continuous Exponential Weights
First, the intrinsic dimension of X' can be defined as the following:
Definition 1. The intrinsic dimension of X is defined
dim (2) dim (span (X X)),
where X X' (ar xf x0, x.).
convex region X' R can be translated and rotated that it entirely lies in RM where dim(X') and has non-zero volume in R We more precisely define this transformation below.
Definition 2. Let X C Rd be a corvex region with dim(X') m. We define @ R - R as the following linear transformation:
(lx) 2 ZMx,
where M E R is a rotation matrix (i.e., orthogonal matrix) such that for any v E X X, Mu has non-zero elements only in the first coordinates (this is always possible by the definition of dim(X) in Definition 1), and
0
0
1
0
0
Z =
E Rmxn
extracts the first m coordinates of given n-dimensional vector. Lemma 1.1. For any X and any 0 R
(or, 0) = (0(x), x(0) + f(0 0),
where f(0,0) IR some quantity that only depends on & and 0 but not
Proof. Let x. x' E X. By the definition o. we have
(p(x) ((x'),()))))))))())) ((x'). 6(0)) (7M(x x'), ZM0))
By the choice of M in Definition 2, .M x') only has non-zero elements in the first m coordinates. Furthermore, since Z extracts the first m coordinates, we have
m
(ZM(z (x - 2'), ZMB) = Σ (M - (M)
Σ (M x (M)O),
(M(x x²), MO)
(x x',00 x²,0).
(MT M because M is a rotation matrix)
Thus,
(c, 0) (6(x), (()) = (2.00 (0(x') 6(0))
meaning that the value of (ar 0) (d(x), (0)) is shared by all X. Defining this value f 0) finishes the proof.
We consider the continuous exponential weight algorithm (Algorithm 5) running o(X) C Rm
29

---

Algorithm 5: Exponential Weights
Let A' C R", and let ((2) & (x(x) x 2 for 1 1, 2......o ......d do
Define for y E (()),
we(y) [VEoX we ()y)dd
(v( = exp 11 Σ (v (0,)) +n
WU (bb))) and pr(y)
for some bonus term by. Sample yt Pt, and play = ((1),, where x- is the inverse mapping of ø. Receive 0₁ E I2"
In Algorithm 5, require that the inverse mapping of ò exists. This is true because for any x' X, we have [Ø(x) - 6(x')l = MZ - r')ll = [I x')ll = || - x'Il. and thus ó cannot map I, x' X' with
x' the same point.
Theorem I.2 Let q: (X) be the distribution such that x ~ qi is equivalent to first drawing ~ and then taking = Φ (v). Algorithm 5 ensures for any z E X,
m mogo? T
1
(x, 8, + bi)
Σ
B 10, ba)l
E Beng fexp (1 (z.0,)) 17 (x, (x, 1].
1
17
Note that Algorithm 5 is a standard continuous exponential weight algorithm over reward vectors ((0,) and in the space of ((X) c R By the standard analysis (see, e.g., Ito et al. (2020); Zimmert and Lattimore (2022)), we have for any sequence A...... Ar E R and any o(X))
Proof.
Σ 1=1
(y (01) + o(be)) Σ Evp [(,, 0(0,) + o(b))))
mlog T
(2, yyp, (exp (n A1) (g. ((0)) + +1a) 1]
By Lemma 1.1, the above implies
(y),0, ba)
Byrop [(0 + bb)
1 T
log T
Σ
Eynna exp (x) 0.) 0.) +1a) - (0)) n5(, N1) -1].
+ 1)
which further implies that for any X.
(x, O2 + bb) Ev [x, 0: bb)l < m log T
Σ
Erng (exp (n (z. 02) 7 (x, 01) 1]
by the definition of q, and by letting \ = ( 0c)
Computationally Efficient Algorithm for Adversarial C Bound
In this section, we present Algorithm 6, polynomial-time algorithm that ensures Ö(d VT dic) regret. The algorithm is based on the continuous exponential weight algorithm in the original feature space (Ito al., 2020; Zimmert and Lattimore, 2022), with the bonus construction similar Lee et al. (2020).
30

---

J.1 Preliminaries for Entropic Barrier
Entropic barrier For any convex body A, the family of exponential distribution is
(x) = exp(w xx) 11 ty E A}
IA exp(w yddy
For any I E A. there a unique wxx) such that Eyrpuce) (v] x. The entropic barrier F(x) is the
negative entropy of Pwlx)) Namely
F(x)= = (wla)(u) log (Pu(z) (1)) dy
We have VF(x)= w(x)) and (2) = Ey-rote [(y x) =) We know that F(x) is diself-concordan barrier on A.
The equivalence of mean-oriented FTRL and continuous exponential weights with entropic barrier as the regularizer that solves Iy for round E [T] following
Consider FTRL
F(x)
1z+1 argmax JEA
0g
17c
This is equivalent to
VF((++1) = 7) Σ 0.-
s=1
Given that Eyr-Porets)) [9] 24+1 and VF(*++1) w(1+11, playing 2++1 yields the same expected reward as playing according distribution Pw(Fer1) where w(x++1) me E. 0.. Thus, we have Pu[aa (z) & exp nn (z. Ei 0.)) for x E A.
J.2 Auxiliary Lemmas
Lemma J.1 (Lemma of Ito et al. (2020)). !f follows a log-concave distribution over Red and have
Egzg [re ]]
Pr || 2 d s dexp(1 3).
for arbitrary 3 > 0. Lemma J.2. With the choice of 3 2 4log(10dT), we have
Bure [f(a]] Eawp, [f(a]] s 10dexp(-3) - 27
for any f: A:A 1-1, 1] and
3
4
4 Barni [aa T] Earn, (aa ] Bampp [aa T..
Bampi
Proof. The proof follows that of Lemma 4 of Ito et al. (2020), with the observation that pe is log-concave distribution.
Lemma J.3 (Lemma 14 of Zimmert and Lattimore (2022)). Let be v-self-concordont barrier for A C TRd. Then for any u, x A.
u - x||v=f(m)) S - (u x, ff(x)) 4
7 6V
where 7
(T' E [1, volovv11 1).
3V3
Minkowsky Functions. The Minkowsky function of convex boday A with the pole at int(.A)
a function Tee A defined as
कt (u) inf t t>
w
w t
A
(25)
31

---

Algorithm 6: Continuous exponential weights (for adversarial C' bound)
Let A C Re be convex body and F its entropic barrier.
2 Parameters: 7
log(T/6)
@( dvT), min LooerT' 32vda
7
3 fo ,,,....,T do
Define w,(a) exp (n -
0g b.)) and (v)dy), De(a) (t(a)= = wel))/ (B((a)/(SSeAA
pr(a)1f[aalls-- S Vd3a
(Sne wr
Sa'e (ad' vd
where Σ, Bampi aaa
Play a2 Pt, and observe reward with E/r.] a; 0: c((a)). Construct reward estimator 0. Σ, E a,,, where Eg = 7 + Bamp laa J.
-5,- 2, E, x FEI Ba) 0 then
Define B: 1 +
where 2, Ea [a].
21 Ex
if Amax B. Σ
I + IU (t).
F where 2, Eamp, [a] and VF(x)) = =n (0= -b)).
10
else b, = O.
Lemma J.4 (Proposition 2.3.2 in Nesterov and Nemirovskii (1994)). Let f be v-self-conccrddant barrier on A C Rd, and u, w E in)( Then
f(u) - f(w) S vlog
1 Th
J.3 Regret Analysis
We perform regret decomposition. For regret comparator u" A, define x min F(x) and = (1 # )u" + tx*. With probability at least 1 - 6,
T
Regr =
Σ
(u- -a, 01)
t=1
Σ
{u aq, 01) + Σ fu" x²,00 x0)
T
E (u 3z. 01) o
+2
(define S. Ra-p, (a] and by Azuma's inequality)
T
Σ
(u - It. 0.) + Σ
(+n Zz 0.) + O (OOOVVoTlgg Tlog(1/)))
T
w It, O2 - Er(0al) + Σ " De, E, [0c] 0,
+ Σ
u Nt, O, + by
Bius
Deviation
FTRL
(u Ne, bi) +7T O ( (Toog(1/8)
(26)
Bonus
32

---

By standard FTRL analysis, we have
F(u) min F(x)
r (x (--01 2t, 02 + b1)
- Dr
FTRL
max ZEA
(27)
Penally
Stability
The individual terms Bias, Deviation, Bonus, Penalty, Stability terms are bounded in Lemma J.6, Lemma J.7, Lemma J.9, Lemma J. 1.10, Lemma J.12.
Lemma J.5. For any E [T], if Pr, then with probability of at least
3d 8
Mallx, S vdlog
Proof. Define y ET aa Then E, [vv En
En (aa 1 = I. Since pt log-
concave distribution, and log-concavity is preserved under liner transformation, is also log-concave. Applying Lemma on leads to
Pr | |a 2 d3d) = Pr [lvl2 2 dB²] & dexp(1 -B) - 3dexp(-3))
Setting 8 = -ddxxp(-)), we conclude that with probability at least 1 1-8, ||a||3 S d log (24)
Lemma J.6. With probability at least 1 - 0()),
Bias
Tlog(1/8) maxx ||,; ullz, 1) (v 2 2/TT++11////// + vasc).
Proof. The proof the same as that of Lemma H.1.
Lemma J.7.
Deviation S O (max ||u 24
(6))
Proof. The proof is the same as that of Lemma H.2.
Lemma J.8.
4T
Z < d log2
Proof. Our proof is similar to Lemma B.12 in Lee al. (2020). Let (ti, ,tu41] be the rounds
such that b, * Define A, Σÿ= B For any i 1, since Amax (Br, AA-1) > O, there exists
vector y E RR++1 such that y B.,y > y T A. Thus, AA 2 2y A;- Let = =A 1 A
have 2 A A 2 21|=112- This implies Amax
A 2 Moreover, have
Amnin A A $
because
A A (A B.) B., 11 I.
Thus, det(A.) = det AA > 2. By induction, we have det (An+1) 2 2n det (A1). We dct(A.-1)
[
now give upper bound for det(An.1) det(A,)
Define a
By AM-GM inequality, we have
i
Σ B, B ))
n+1
det (An+1A = det
Σ
B B
Tr
33

---

Notice that for any t, B, = I and Tr(B,) Tr(1) + Tr(E; + 1 -
2(d+1) Thus, we can
upper bound the last expression further by
n+
))
2(d + 1) +)
d
47
Σ
Big
dy
Overall, have 2 $
det(A
(4T/7)", and thus n S 2llog((4)) (4T/7))
det(A1)
Lemma J.9.
Bonus S max ||u 24 "|s.- + O (ad log T)
Proof. Let p = max; |u - zells-- and to = argmax, I/u xell xells,,1, We discuss two conditions:
If 1 E I, then p² S ErEz ||u xrl Šー-..
If $ I, then Br, 3 ETEZ Br. Letu A
This implies
1
0² |u Ft. بي-5
1|211
|ulli
B,
Σ
x.
TET
TEZ
where use the definitions of B, and in the second and the last equality.
Thus, max, I/u- Jells, S ErEr 1|u 2z 17
(xt u, bb)
(et u, br)
TEI
(x, vF(xx))
||u - x. 1l + 4od|Z + 20
a
7EI
(Lemma J.3 and F is d-self-concordant barrier) (V²F(z))) = E, ž 15,1 and Lemma J.8)
a
Σ |/ x. x-1|s-- Oaa l)
27
TEI
max ||u xell xellsp1 + O log T).
2
Lemma J.10.
Penalty < dloo(T))
Proof. Since r² minzeA F(x) and Ne. (u) 5
from Eq. (25). We have from Lemma J.4
F(u) F(Ø*)
11 I dlog(T)
Penalty
71
34

---

Lemma J.11 (Lemma 17 in Zimmert and Lattimore (2022)). Let F be the entropic barrier and |
then [ S Ion''
(x (x-2x) B2, w) 1 Dr (2) 2n/ <2nllell 1
max
#EA
Lemma J.12. With probability at least - 6.
Stability 2 O (n dT + +naa dl log
Proof. Since F a d-self-concorrdant barrier (Chewi, 2023), have
[kelvv=F(e.)- By Lemma J.2, we have E 3 [aa -1 2 and thus
S avd.
| ( |ا arrell - 2a, Σ az S 2d52.
Thus, 10, bellver S BV2d + av d. If S 16(BV2d+aVa) by Lemma J.11, we have
T
Stability S 21
Σ
10 + bell =
1=1
T
<
4n Σ
100 [3=)) + 47
Σ (6
1=1
TEZ
0 (n n
(n132 dT + +na 2 log T)
Theorem J.13.
Algorithm ensures with probability at least 6, Reg, = O where (-) hides polylog(T/6) factors.
Proof. Putting Lemma J.6. Lemma J.7, Lemma J.9, Lemma J.10, Lemma J.12 into Eq. (26) and Eq. (27), with 7 < 16(3/2d+ava) and y
1. 7 we have with probability least 1 O(8),
Reg S max I|u ---aall,. (oldvT+ vao) - g) + ad + + na²d + ndT + vT)
(add
By setting = Ö(dVT VaC), we have
+ Reg 2ō ( dàc + naTT + ndd022)
17
Setting 1) 160dv/+32av'd we get
Reg =0(v(T+d&CC)
K
Gap-dependent Misspecification
We consider the same setting Liu et al. (2023a), but remove assumption for it. Consider bandit learning with general reward function fu where for any action F, E X C Rd at round t, the learner get reward y fu( (2)) + 77 where 7ıs zero mean, E-sub-Gaussia noise. We assume there exists a linear function 0 z that could approximate fo(x)) in the following manner.
35

---

Definition 3.
x x So(x) f0 fo(
sup
S
where max fo( and 0 S 1. =Ex
The algorithm in Liu et al. (2023a) only gets O S Va by using elimination-basel methods in Algorithm 7. For any design action set A, define
(VT) regret when S dylog and we improve it to
G(x)
Σ REA
xaa)aa
g(T) max aεA ||a|
Algorithm 7: Phased Elimination for Misspecification
Input: Action set Ar = A. Initialize m. [64d log d log (121) + 16.
2 for {=
do
Find the approximate G-optimal design क. A with g(T) S 2d and [Supp(T)] I 4d log log d +-16- 16
Compute ze (a) [a)] and ue EMEA, ue(a)
Take each action Ae exactly u(a) times with reward y(a).
Calculate
02 = G Σ u(a)ay(a) where
Ge = Σ u(a)aa T
aEAc
aεAc
Update active action set
4d m
(A4)
A4+1
a E Ar : max (0t,a) s
log
+
bEAd
2
11+1
4m
Define Gap(z) = fi - fo(z) as the suboptimal gap at point x. Definition implies the true value function fo(x) 00 x + ((x) where [xxx] S p(5á - fo(x)) = pG)((z). We further assume that [a(x] pGap(z) which captures both standard uniform misspecification and the gap-dependent misspecification. With this assumption, our main result is summarized in Theorem K.1.
Theorem K.1. For action o, assume y(a) fo(a) + na where na is zero-mean sub sub-gaussian noise and fo(a) A A(a) with A(a)) pGap(a). If S sava. with probability at least 1 5.
we have
Reg 00 ( dT log [AI/8)
Proof. First, with probability at least - 8, for any and E As, we have
16.0e 8)
b G.G: Σ u(a)ay(a) tT
b bTG Σ u(a)aa) T na +bG Σ u(a)as(a)
aeAc
aEAc
4d V
[AI]
log
+
b (TG Σ u(a)aa(a)
mg
aEAr
where in the last step, we use standard concentration by Equation (20.2) of Lattimore and Szepesvári (2020) and the apply union bound for all actions.
36

---

For the last term, we have
< u(a)
b GT Σ u(a)a
S max ((c)
b bTG
Σ
u(a)aa T mg
Ta b
cEAr
aE.dj
LaEdi
aEAr
(Cauchy-Schwarcy
2du m
max (cc) nEAc
u /u/bia
S max (c)) cEA:
S max A(c) 2vd. rEA:
G,
Thus, for any b E As.
(b. 0 8) 0
4d
log
A i
+ +2vd max
A(a)
-
4d
log
( 8
+ 2 dp max Gap(a) aeAr
my
aEAt
m
When e = 1, since my [256d log log d'log
[A]] 1+16, have
4d
log
( (
24 Moreover,
mi
by trivial bound, max Gap(a) < 2 and a² A
We will jointly do two inductions. Assume for round E, we have at E As and max.eA, Gap(a) S We first show a" E Aet1. Thus, for any b E Ar, given S 1 since me = 4 m1, we
1 2--2-
64/7
have
4d log ((A)
(b, -0:
03
s V
+ 2V 2V max Gap(a) S 2 24 +
me
aEAr
2 2
From the induction hypothesis, let ae arg maxbEA; (0e, b) we have
07 04 - 0Ja² a" < 50 - 0 a. + 0 ai 0 TJ
+ 0
a---0
-0, a*
S
< fo(āe) fola") + + (ā=)
2
1 S @Gap(aa) + 2e+1
For + 1, the remaining actions E Ae+1 satisfy
max max b) -0ee, a) S V
log me
4d
[
+
1
<
+
BEAr
2
26+3
2
This implies A Moreover, since a* E Ar, for A we have
Gap(a) fo -f((a) = 0T at - - a + laa))
07 a" 0f + pGap(a) + (0 0z) To) a" (0: 0)
< 0, a" 0, + pGap(a) + (0 - 01) T a" + (0g 0) a
0, a' 0. a + 0 a 0. + pGap(()) + 2
50 given EAAe
22040
Given P 64/a S
this implies
64.
1
1
Gap(a) <
2
21+1
20+3
64
2
21+1
2
2
The above arguments show that as l increases, max Gap(a) will shrink by 2 at every step. Since for a E Ag, Gap(a)= I - =0
(v
Ad
log (44))
me
37

---

Finally, given L = log(T), we have
Reg
Σ ua(a)Gap(a)
4
S mey log
4d my
AA 8
S 50
50(v
(Va d7 log (A1/))
1=1 oE
t=1
When 2 2 T4, we can apply similar covering number arguments as Appendix E, replacing A with -et of A. Combined with Theorem K.1, this yields the result in Theorem 6.2.
Using the hard instance for c-misspecified linear bandits setting in Lattimore et al. (2020), show that p (2) for algorithm to achieve sub-linear regret, proving the above algorithm is optimal in terms of p assumption.
Theorem K.2. Pf 2
(37) d-1
then there exists an instance that Ry = 2(pT).
Proof. Using Theorem F.5 in Lattimore al. (2020), there exist discrete Lime-invarian action space {az E IR313 Ji=1 that satisfies these two conditions:
1. ||ss|| = Vi
2. (ai;ay) S
1og
Vi サ
and let 0" 8 (og(33)) 60gg for some i*, and let misspecification at each round for all non-optimal
d-
arms be c to make the true expected reward zero. Defining 7 max(tli, * 1" Vs S t), we have E[RT]] 2 d-1 [B(r]. Since the observed rewards are independent of az- before time т, and i is chosen randomly, have B[r] 2 min 3T-1) }. So,
R cT
(lgg(3T)
Finally, we have p completes the proof showing linear regret when p is large enough.
log(3T)
choosing min(y
8 33T 37)
d-1
d
L General Reduction from Corruption-Robust Algorithms to Misspecification
In this section, we extend the results of Section to the reinforcement learning setting. We consider episodic MDPs, denoted by tuple M = (S,A, (P.)" frn 1h21 1 81) for S the set of states, A the set actions, Pa.
A As the transition kernel, Ta S A - A the reward, and the starting state. We assume each episode starts in state 81, where the agent takes action an transitions to 82 ~ P- 81, .a) and receives reward rı Ti (1). This proceeds for steps at which point the episode terminates and the process resets. We assume that Σ Th E [0, 1] almost surely (note that the linear bandit setting with rewards [-1,1] can be incorporated into this with simple rescaling).
We let denote policy, Th S - As, mapping from states to actions. We denote the value of policy æ MDP M V,M, 1.M. h=== rn]. We assume access to some function class F C (S x A R). In the MDP setting, we define regret on MDP M as:
T
Reg M = sup M.a
M.a.
0
t=1
In the MDP setting, consider the following notion of misspecification.
38

---

Definition (Misspecification). For our environment of interest M there exists some environment Mo such that, for each fh+1 F, n, and (s, a, h). we have:
B. * (rn fh+t1 (8 01+11) 8h 8, a)
E MM (rn + f1+1(99++.. an+1) Sh ab = =a]
mis (s, a) S ch
and
3f4 F s.t. fn(s, BMoorr + max fh+1 f1+1((+++,, 8h S, 04 a]
e (8, a) > O. for some
We make the following assumption on gap-dependent misspecification. Assumption 4 (Gap-Dependee) Dependent Misspecification). For any policy we have
H
EMC.. S
Σ
mis (Sh, an)
Sp.
h
for some 2 (0,1). 1).
We are interested in relating the above misspecification setting to the corruption-robust setting. In the MDP setting, we allow both the reward and transitions to be corrupted. For some MDP M, define the corruption episode t and step as:
sup (r. o/h) (E(SxA-)0.8)
I(T To" g5 af)1
where
T',(8,a) = [M + max g(sx+1,d)) 8h. = 8, an = =a] o'
denotes the Bellman operator, and T denotes the corrupted Bellman operator, i.e. Ty² denotes the expected reward and next state under the corrupted reward and transition distribution. We denote the total corruption level
C
ΣΣΣ EL a 1=1
Note that this definition of corruption encompasses both bandits and RL. with function approximation.
Now assume we have access the following oracle.
Assumption We have access to a regret minimization algorithm which takes as imput F and some C' and with probability at least 8 has regret bounded on Mo
Reg <C(6,T))T++ + C2(5,
(28)
if 2 C. and by HT otherwise, for C as defined above and for (problem-dependent) constants C2( T) which may scale most logarithmically with T and 3.
Before stating our main reduction from corruption-robutt to gap-dependent misspecification, we require the following assumption.
Assumption 6. For any n. have that there exists some f E F such that for all (s, h), (.Mo. a) a).
We then have the following result.
Theorem L.l. Assume our environment satisfies Assumption Then under Assumption and Assumption 6, long pol4.T) bounded as:
I-p 1/2,, with probability least 28 achieve regret
2. TV+ + I-p" (1 log (10)) 21v/21og((/00 11)
M Reg.
< 1-p C,(.,
39

---

Proof of Theorem L.I. First, note that by Assumption 4, we can bound
E M"
mis (sn
(s))aa)
Σ P (m)) S p Regr
where abbreviate Regr Regr"* M' M is equivalent to interacting with Mo but where the rewards and transitions are corrupted up to level ex (s, a) at (s, ht.
Furthermore, note that under Assumption 4 interacting with
Relating Regret on Mo to M Define the regret on Mo as
H
H Σ rb
Reg Mo T sup M.,
Σ
rh
E
Mo
Under Assumption 4, we have that R.M', ,x
-ha=l h= "h
( an)
= 0. Lemma L.2 then implies that
1
BM',
Σ
E.Ma.
Σ
rh
rh
1=1
and so
H1
R-M xx*
Σ Th
sup R.Mo
sup
Σ rh
Furthermore, Lemma L.2 also implies
H
H
H Σ
Mo
Th
M
Te
Σ
Th
I E.M m
ch
mis
(sh, an)
Putting these together we can bound
H Σ
Regr & Reg Ma Σ
R.M. m
mis %
an)
Reg
Mo + p Regry
1=1
k=1
where the last inequality holds by Assumption 4. Rearranging this gives
Regr < 1-p
Regg
Mo.
Bounding the Regret. Consider running the algorithm of Assumption on M and assume we run with parameter C" + B which we will choose shortly. From the above observation, this is equivalent to running on M1 with corruption level e (s. a) at (s, a, h). Then by Assumption with probability at least - 5 we have regret on Mo bounded as
Reg S C, C2(5,T)3
3 2 EL E chiss af)), and by HT otherwise. Furthermore, by the above argument this then immediately implies regret bound on Reg
Eii en (s (sh af)).. Let Eg denote the event that for all Let ε1,t denote the event that {B 2 Ei=
t < T,, we have
Reg, 1-p CGlf,TTV+++c
TH 1-p I(EE,r)
and note that by the above and under Assumption 5 we then have that &g occurs with probability at least 8. For simplicity, for the remainder of the proof we abbreviate C₁ := C,(4 (47T) T) and C2 == C2,
40

---

Note that eN (s), a/h E [0, H] by construction. It follows that, with probability at least 1 - 6, via
Azuma-Hoeffding
T
H
H mis (s) a/p
mis (sh
o/,)) -
E
+ H 2T 1/6 S Regr + H V 2T log 1/6.
1=1 1=1
t=1
h=1
Denote this event as E3.
Now consider choosing
8
(1 1 1-p) p)
pC2
-1
-1- C.VT H 1/6 + H
P
so that
P P.
(CIVT+Ca3) H 2T 1/6 H.
8
-
On Eg n E3, assume that
<<p Reg, + H HV log 1/6.
(29)
Let t* denote the minimum time such that
Σ PA(T) + H 2 log 1/6
> 8 and Σ [=1
(A(TT) + H l2 1/0 S
and note that such a time is guaranteed to exist under (29) and since 3 2 H log by construction (Ti) H /2T log 1/6 s H + H /2T log 1/6 I B. Furthermore, since (T) < H, we have here that Σi=1 p (T))
1/8 + H
> 3 - pH H v 2T log 1/6. We then have
Reg
((T))
t=1
H 12T
1
(G.VT C2B
1- p
1
(CIVi- 1
However, since by assumption Σ(-1 (A(TT) H /2T log 1/8 s 3, on Eg E1 holds so on Eg ( Eg we have that
1 Reg S 1-p (CIVi-1 1+
This contradicts the above. Therefore, on Eg E3 must have that 3 2 p Reg, + H. 2T log 1/8, so Egr holds on Eg, and so on Eg n
1-p (GVT+C,2)
1
Regr
From our setting of 3 we can bound this as
< 1-p
1 - ---
1-p C2
pls
P
CCVT + H 22 1/6 + H))
1-
The result follows from some simplification.
Lemma L.2. For MDPs M .Mo satisfying Definition 4, under Assumption 6 we have
H
V.M.. V.M', < M.M' .
Σ
mis
(sh an)
41

---

Proof. Let r' denote the reward function on Mo. and note that under Assumption 6 we have that there exists f E F such that V.Mo. al. (2017) gives that
h (s) = fi,(s, Th (s)) for all h. Then Lemma E.15 of Dann
11
V/ Vo Voli EM :
Σ h=1
(rh- - rn)
EM IV (sh+1) sn]
EM "MM"""Vn (TV (sn+1) snl
By Definition 4, we can bound this
H
I EM
Σ
mis (5hs (sh an)
h
Proof of Corollary 6.2.1. First, note that under Assumption 3, we have that Assumption holds for FF the set of functions linear in Φ, F ={ a) a)Tu
Rd s.t. Φ(s,a) w [o, H), Vs, a), and ef (s, a) of Assumption set to Hch. (s, a) for cf (s. a) of Assumption 3. To see this, let MM be the MDP with transitions (Ø(s,, a), 14r(()); and note that this the immediately implies linear realizability on Mo (and furthermore that Assumption 6 holds). Furthermore, since the total reward take ch mii (s, a) He (s,
most H, it is easy
that under Assumption 3,
Next, note that Theorem 4.2 of Ye et al. (2023) gives an algorithm on .Mo satisfying Assumption with C HV and C2 O(H)) (assuming that Σ 1 Th E [0, 1] almost surely). We can then apply Theorem L.11 obtain the result.
M Auxiliary Lemmas
X + xx
x
Lemma M.1 (Lemma 16 of Zimmert and Lattimore (2022)). Let
and Y
1
Y + yy T
y
Then
9
1
Dx(X,Y) = Do(X, - 2 1|-- Bll
Lemma M.2 (Lemma 34 of Liu et al. (2023b)). Let G be the log- dee-dtterminnn barrier. For any
matrix D. if V (T,HH, I 1 then 16n"
H H. H, Do(H,H.) < 8T/r (H,DH,D). HEH
max
17
Lemma M.3 (Strengthened Freedman's inequality (Theorem 9 of Zimmert and Lattimore (2022))). Let X1, X2...., ......,y XT be a martingale difference sequence with a filtration Fi F C ... such that
B[X, Fc] = 0 and E E[|X, Fi) < almost surely. Then with probubility at least 1 - 8,
T
log (2max[Ur: (Vr)) + 2U, log mmaxx (Ua, VVT)
X1
3
1=1
where Vr ΣT
E
Fi] and Up max max [X(]}.
42

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. The claims validated by detailed proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 as long as 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].
43

---

Justification:
The paper discuss the limitations of the work when introducing the algorithms.
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 separate "Limitations" section in 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 vell-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 few datasets 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 or 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 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 be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes].
Justification:
The paper provides detailed assumptions and proofs.
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 proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 be 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 whether the code and data are provided or not)?
Question:
Answer: [NA].
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
44

---

If the paper includes experiments, a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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 new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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 describe the particular way they provide for reproducibility. 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?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ Souiides/ooeSSumiiee
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 NeurlPS code and data submission guidelines (https: / //nips. //wips.cc/publll/// https//cpppbclcguueeeeeee http://oooSSSSmssseeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to 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. 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).
45

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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?
Question:
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, 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: This 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 accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
46

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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 NeurIPS Code of Ethics https: sttpps://eerips... ctpps.ccppppe hppppli//tticscuuiiii ines?
Answer: [Yes].
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical work. There is no societal impact of the work performed.
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 socictal 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.
The conference expects that many papers will be foundational research and tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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 such risks.
Guidelines:
47

---

The answer NA means that the paper poses no 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 challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA].
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA that the paper does 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 used and, possible, include URL.
The name of the license (e.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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 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:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA].
48

---

Justification:
This paper does not involve crowdsourcing nor 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 in the main paper.
According to the NeurIPS Code of Ethics, workers involved 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: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 we expect authors to adhere to the NeurIPS 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.
49


Reviews:
[{"review_id": "EOjQ7aQNxC", "reviewer": "Reviewer_QWPG", "summary": "This paper studied the corrupted linear bandits. The authors propose four different metrics to evaluate the total corruption in Eq. (1). Many settings are considered in this paper. For stochastic LB, the proposed algorithm achieves a regret bound of $d\\sqrt{T}+\\sqrt{d} C_{\\infty}$. For adversarial LB, the proposed algorithm achieves a regret bound in the order of $d\\sqrt{T}+\\sqrt{d} C_{\\infty}$ or $d^{3}\\sqrt{T}+d^{5/2} C$. The authors also consider the gap-dependent misspecification, where the misspecification level of an arm $a$ can be evaluated by $\\rho$ times the gap of arm $a$.", "questions": "See weaknesses.", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "See summary.", "weaknesses": "**Weaknesses and Questions:**\n1. At lines 107-109, the authors claim that the strong adversary is equivalent to the CM viewpoint. This doesn't seem right. For regret, the strong adversary is harder than the CM viewpoint. Thus, it is unfair and wrong to compare He et al. (2022) in the same way.\n2. At line 131, adversarial linear bandits are discussed. However, no problem definition of this problem is introduced before line 131.\n3. This paper studies the fixed action set, while the previous works He et al. (2022) and Foster et al. (2020) allow the action set to be chosen by an adaptive adversary, which is much harder than this paper. Table 1 is not fair. He et al. (2022) is for the adaptive adversarial viewpoint, which is totally different from the stochastic LB. For a fixed action set, the optimal regret without $C$ should be $\\sqrt{d T \\log k}$, where $k$ is the number of arms.\n4. Assumption 1 is not very reasonable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. Your questions are answered below.\n\n**Q1**: The strong adversary (AA) seems not equivalent to the CM viewpoint.\n\n**A**: The equivalence between the \"strong adversary\" in the AA viewpoint and the \"strong measure'\" in the CM viewpoint is based on the equivalence between the following two processes (note that the discussion here only concerns the adversary in choosing the \"corruption\"; the discussion about the adversary in choosing the \"action set\" is discussed in **Q3**): \n\nProcess 1 (AA viewpoint):  In every round $t$, the learner first chooses an action $a_t$, then the adversary chooses the corruption $\\epsilon_t$. The learner observes $r_t = a_t^\\top \\theta_t + \\epsilon_t + \\zeta_t$, where $\\zeta_t$ is a zero-mean noise.  Define $C=\\sum_{t=1}^T |\\epsilon_t|$. \n\nProcess 2 (CM viewpoint): In every round $t$, the adversary first chooses the corruption $\\epsilon_t(a)$ for every action $a$, then the learner chooses an action $a_t$. The learner observes $r_t = a_t^\\top \\theta_t +  \\epsilon_t(a_t) + \\zeta_t$, where  $\\zeta_t$ is a zero-mean noise. Define $C=\\sum_{t=1}^T |\\epsilon_t(a_t)|$. \n\nIn Process 1, the adversary chooses the corruption based on the learner's action $a_t$. In Process 2, although the adversary specifies the corruption \"before\" seeing the learner's action, it captures the same effect as Process 1 because the applied corruption depends on the chosen action $a_t$. In other words, the amount $\\epsilon_t(a)$ in Process 2 is a \"plan\" of the adversary (set before seeing the learner's action $a_t$) for the amount of corruption under the assumption that the learner chooses $a$. After seeing $a_t$, the adversary simply applies the planned corruption $\\epsilon_t(a_t)$. \n\nThe AA viewpoint is adopted by most previous works on linear bandits (Bogunovic et al., 2021) and linear contextual bandits (He et al., 2022). In this work, we argue that such results are equivalent to the standard adversary (i.e., adaptive adversary) with a fine-grained corruption measure (i.e., $C=\\sum_{t=1}^T |\\epsilon_t(a_t)|$) in the analysis. We believe this leads to a more unified treatment for the strong and weak adversary widely studied in the literature, which are usually separately discussed.\n\nWe hope this clarifies the equivalence between the two viewpoints. If there are still concerns, we would appreciate it if the reviewer could elaborate on the potential mismatch in the difficulty between the two viewpoints.\n\n**Q2**:  No definition of adversarial linear bandits before line 131.\n\n**A**:  The general linear bandit problem is introduced in lines 71-76. Then, in lines 77-79, we describe the stochastic and adversarial settings of it. The term \"adversarial linear bandits\" in line 131 simply refers to the adversarial setting of linear bandits. We will make this more clear.\n\n**Q3**: This paper studies the fixed action set, while He et al. (2022) and Foster et al. (2020) allow adversarially chosen action set, which is much harder. Table 1 is not fair. He et al. (2022) is for the adaptive adversarial viewpoint, which is different from the stochastic LB.\n\n**A**: In this paper, we focus on linear bandits with fixed action sets. Note that even in this simpler setting, for the stochastic case, there is no prior work achieving $\\sqrt{d}C_{\\infty}$ regret; for the adversarial case, there is no prior study on \n$C_\\infty$ bound. Our work obtains tight $\\sqrt{d}C_{\\infty}$ regret in both cases.\n\nThe purpose of Table 1 is to summarize known $C_{\\infty}$ and $C$ bounds in linear bandits. He et al. (2022) is included because their algorithm gives the best $C$ bound in linear bandits, even though it works for the more general linear contextual bandit setting with adversarially chosen action sets. We will clarify this in our next version. In other related work discussions (e.g. Line 120-130), we will also make similar clarification that Foster et al. 2020, Takemura et al. 2021 study the more challenging linear contextual bandit setting.\n\n**Q4**: For a fixed action set, the optimal regret without $C$ should be $\\sqrt{dT\\log(k)}$, where $k$ is the number of arms.\n\n**A**: Technically, there are two widely adopted lower bounds for linear bandits with fixed action sets. One is $\\sqrt{dT\\log k}$, which is tight for $k\\leq 2^d$; the other is $d\\sqrt{T}$, which is tight for $k>2^d$ (see, e.g., Section 24.1, 24.2 of Lattimore and Szepesvari, 2020, for the second lower bound). For simplicity, we adopt the second lower bound. Our analysis for the stochastic setting (Theorem 4.1) can also give the $\\sqrt{dT\\log k}$ bound straightforwardly. For the adversarial setting, however, we do not obtain $\\sqrt{dT\\log k}$ though due to the limitation of our base algorithms. \n\n(Lattimore and Szepesvari, 2020)  Bandit Algorithms.\n\n**Q5**: Assumption 1 is not very reasonable.\n\n**A**: Assumption 1 comes from Liu et al. (2023a), with more motivation provided in its Introduction. Existing work on misspecification tends to assume the misspecification level is uniform over all actions, which typically yields overly pessimistic results (a regret linear in the misspecification level).  Assumption 1 is the only known assumption beyond realizability that is sufficient to obtain the minimax $d\\sqrt{T}$ regret, as in the unmisspecified case. Understanding precisely what conditions on misspecification are necessary to achieve $d\\sqrt{T}$ regret is an interesting open question.\n\nWe also believe that this assumption is often reasonable in real-world applications. In practice, approximating a decision-making problem as a linear bandit typically requires extensive modeling and feature selection to choose the linearization. In settings that are not perfectly linear, one would naturally focus on obtaining an accurate linearization for \"good\" or \"typical\" users, and would likely be willing to tolerate a less accurate model for \"bad\" or \"atypical\" users. This is precisely the intuition that is captured in Assumption 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6RsE2wCqwx", "reviewer": "Reviewer_TGCM", "summary": "In this work, the authors characterize the problem of learning the presence of reward corruption in the linear bandit setting. They provide matching upper and lower bounds in the corrupted stochastic setting, and initiate the study on the corrupted adversarial setting, for which they obtain optimal scaling in the corruption level.\n\nNot only that, the authors prove a general reduction that efficiently handles gap-dependent misspecification with corruption-robust algorithms. They were able to show that linear MDPs with gap-dependent misspecification are efficiently learnable. While this reduction is general, interestingly they denied the possibility to obtain the tightest rate for gap-dependent misspecification. This observation leads them to develop a specialized algorithm which, in the linear bandit setting, obtains the optimal rate. According to their argument, this resolves the open problem of Liu et al. (2023a).", "questions": "- Unclear points in the weakness section.\n\n- It would be great if authors could explain why the gap-dependent misspecification assumption (Assumption 1) is necessary.\n\n### Minor\n\n- Theorem G.1 in line 296 - is it correct?\n\n- Corollary 6.2.1 in line 209 - it seems like it is the result for the MDP...", "limitations": "The authors adequately addressed the limitations. It would be great if authors provide possible future works. \nThere is no potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Interesting results\n    - Deterministic algorithm cannot avoid suboptimal regret (Proposition 1)\n    - Matching upper and lower bound on the stochastic setting, by just changing deterministic sampling to stochastic.\n    - Solving an open problem of instance-dependent misspecified setting.\n\n- Clearly state the limitations of previous works and their technical novelties.\n    - Easy to understand their contributions.", "weaknesses": "- (Minor) The algorithms are not seriously different from the previous works as they mentioned, but this is just a minor point - every theoretical improvement is important. \n\n- Not clear what they tried to say on page 9\n    - Why Theorem 6.2 shows that $\\rho \\leq \\frac{1}{d}$ is not optimal?\n    - Impossibility result (from line 304): so basically what authors are trying to say is, that 'their' reduction is not applicable for a tighter result, right? It is not about any reduction from corruption to misspecification. \n\n- No future works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. The global response includes potential future works, which we will incorporate into the future version. Your questions are answered below.\n\n**Q1**: The algorithms are not seriously different from the previous works as they mentioned\n\n\n**A**: Although our algorithmic framework inherits from previous works, the corresponding modifications offer new insights. For example, the impossible results in Proposition 1 for the deterministic algorithm lead to our randomized design in Algorithm 1. Moreover, our geometric-inspiring bonus design in Algorithm 2 does not appear in previous papers and it is the key to the tight $\\sqrt{d} C_{\\infty}$ regret. We believe such bonus design ideas could also inspire future work.\n\n**Q2**: Why Theorem 6.2 shows that $\\rho \\leq \\frac{1}{d}$ is not optimal?\n\n**A**: In Theorem 6.2, we show that there exists an algorithm with which $\\rho \\leq \\frac{1}{\\sqrt{d}}$ suffices to ensure $d\\sqrt{T}$ regret. This implies that the requirement $\\rho \\leq \\frac{1}{d}$ is \"too strong\", and thus not optimal. The $\\frac{1}{\\sqrt{d}}$ factor, on the other hand, is optimal because of the lower bound given in Theorem G.2 (discussed in line 296-303). \n\n\n**Q3**:  Impossibility result (from line 304): so basically what authors are trying to say is, that 'their' reduction is not applicable for a tighter result, right? It is not about any reduction from corruption to misspecification.\n\n**A**: Yes, the impossibility result only shows our reduction is not optimal. However, we generally believe that no reductions can guarantee $\\rho \\le \\frac{1}{\\sqrt{d}}$ suffices for $d\\sqrt{T}$ regret, due to the $dC$ lower bound for corruption. This will be clarified in our revision. \n\n**Q4**: Why the gap-dependent misspecification assumption (Assumption 1) is necessary?\n\n**A**: Assumption 1 comes from Liu et al. (2023a), with more motivation provided in its Introduction. Existing work on misspecification tends to assume the misspecification level is uniform over all actions, which typically yields overly pessimistic results (a regret linear in the misspecification level).  Assumption 1 is the only known assumption beyond realizability that is sufficient to obtain the minimax $d\\sqrt{T}$ regret, as in the unmisspecified case. Understanding precisely what conditions on misspecification are necessary to achieve $d\\sqrt{T}$ regret is an interesting open question.\n\nWe also believe that this assumption is often reasonable in real-world applications. In practice, approximating a decision-making problem as a linear bandit typically requires extensive modeling and feature selection to choose the linearization. In settings that are not perfectly linear, one would naturally focus on obtaining an accurate linearization for \"good\" or \"typical\" users, and would likely be willing to tolerate a less accurate model for \"bad\" or \"atypical\" users. This is precisely the intuition that is captured in Assumption 1.\n\n**Q5**: Theorem G.1 in line 296 - is it correct?\n\n**A**: Thank you for pointing that out. It is a typo and should be Theorem 6.2. We have fixed it.\n\n**Q6**: Corollary 6.2.1 in line 290 - it seems like it is the result for the MDP...\n\n**A**: Thank you for pointing that out. It is a typo and should be Corollary 6.1.1. We have fixed it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eE05dTrizm", "reviewer": "Reviewer_DxTV", "summary": "This paper studies corruption-robust linear bandit optimization and characterizes the regret bound in terms of both weak and strong corruption measures. Under the stochastic setting, this paper proposes a phased elimination algorithm, and the regret bounds match the lower bound. Under the adversarial setting, the paper proposes two individual algorithms for the two corruption measures respectively. In addition, this paper studies gap-dependent misspecification setting through reduction, and discusses a use case for linear MDPs.", "questions": "What is the computational cost of the proposed algorithms?", "limitations": "Some limitations are discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The regret bounds in terms of both corruption measures are provided, where the regret bound depending on $C_\\infty$ is first introduced in this paper.\n- The theoretical results are supported with detailed proof.\n- This paper is generally well-written.", "weaknesses": "- The algorithms are efficient regarding regret bound, but the computational complexity is not discussed.\n- A conclusion section could be added.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. The global response includes a summary of our paper and potential future work, which we will incorporate as a conclusion in the future version. Your questions are answered below.\n\n\n**Q1**:  What is the computational cost of the proposed algorithms?\n\n**A**:  All our proposed algorithms could be computed in polynomial time except Algorithm 2 because it requires solving a fixed point optimization defined in Line 6 of Algorithm 2. As a remedy, we propose Algorithm 4, which gives a computationally efficient counterpart of Algorithm 2 with a worse $dC_{\\infty}$ regret. \n\nTo be more specific, the main computational cost in Algorithm 1 is to get the G-optimal design and the per-step computational complexity roughly has order $|\\mathcal{A}| d^2$ from lemma 3.9 of [1] (also discussed after Theorem 4.3 of [2]).  \n\nFor Algorithm 3, the main computational cost is solving the continuous exponential weights defined in Line 4. Assuming we get access to linear optimization oracle, the per-step computational complexity has order $poly(dT)$ as discussed on Page 6 of [3].\n\nFor Algorithm 4, the main computational cost is solving the logdet optimization in Line 6 and the per-step computational complexity has order $d^4|\\mathcal{A}|$ from proposition 1 of [4]. \n\nNote that the $|\\mathcal{A}|$ dependence is common in most linear bandit algorithms including LinUCB and phase elimination. More discussion on the $|\\mathcal{A}|$-dependent computational complexity for existing linear bandit algorithms can be found in Section 1.2 of [5].\n\n\n**References**:\n\n[1] M. J. Todd. Minimum-volume ellipsoids: Theory and algorithms, volume 23. SIAM, 2016.\n\n[2] Lattimore, T., Szepesvari, C., and Weisz, G. Learning with good feature representations in bandits and in RL with a generative model. ICML, 2020.\n\n[3] Zimmert, J. and Lattimore, T. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. COLT, 2022.\n\n[4] Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. NeurIPS, 2020\n\n[5] Liu, H., Wei, C.-Y., and Zimmert, J. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. NeurIPS,2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## Global Response:
We thank all reviewers for their time and valuable feedback. As suggested, we summarize our paper here together with possible future directions. We will incorporate them into our future versions.

Our paper contributes to three research lines.

1. For stochastic linear bandits with corruption, we design an algorithm that achieves $\sqrt{d}C_{\infty}$ regret for the first time, filling a gap in the existing literature. We also construct a lower bound demonstrating that such regret is unattainable by any deterministic algorithm, which leads to our randomized design.

2. For adversarial bandits with corruption, previous works only focus on multi-armed bandits while we move forward to the more challenging linear bandit settings. We achieve the tight $\sqrt{d}C_{\infty}$ regret and also show it is possible to get $poly(d)C$ regret. The novel geometric-inspiring bonus design in Algorithm 2 does not appear in previous papers and it is the key to the tight $\sqrt{d}C_{\infty}$ regret. We believe such a bonus design idea could also inspire future work.

3. For gap-dependent misspecification in linear bandits, Liu et al. (2023a) give an algorithm showing that $\rho \le \frac{1}{d}$ is sufficient to achieve $d\sqrt{T}$ regret, and ask what is the optimal rate of $\rho$. We fully resolve this open problem by designing an algorithm that achieves $d\sqrt{T}$ regret with $\rho \le \frac{1}{\sqrt{d}}$ (Theorem 6.2), and provide a matching lower bound (Theorem G.2). Going beyond linear bandits, we show that such gap-dependent misspecification could be generalized to RL and also give a reduction from corruption to gap-dependent misspecification. Our reduction ensures that $\rho \le \frac{1}{d}$ is sufficient for $\sqrt{T}$ regret in linear MDPs. This is the first RL misspecification assumption beyond realizability that leads to $\sqrt{T}$ regret bound without any additional misspecification term.


There are many future works based on our paper. Firstly, the current $C$ bound for adversarial linear bandits is $d^3\sqrt{T} + d^{\frac{5}{2}}C$ while the lower bound is $d\sqrt{T} + dC$, leaving a gap to be addressed.  Secondly, getting tight $\sqrt{d}C_{\infty}$ bound beyond linear bandit (e.g. linear contextual bandits, general contextual bandits, and RL) is interesting. Thirdly, for gap-dependent misspecification, designing algorithms that achieve $\sqrt{T}$ regret for RL with $\rho \le \frac{1}{\sqrt{d}}$ could be a future direction. Moreover, finding other misspecification assumptions beyond realizability that lead to $\sqrt{T}$ regret without any additional term is also an interesting area to explore.


[Liu et al, 2023a] Liu, C., Yin, M., and Wang, Y.-X. (2023a). No-regret linear bandits beyond realizability. UAI.

Meta-review: This paper resolved several important problems in the literature regarding bandit learning and corruption, including stochastic linear bandit and gap-dependent misspecification in linear bandits. It also considers the challenging setting of adversary linear bandit with corruption. After rebuttal, the authors successfully addressed the reviewers' concerns. I also find this paper solid, especially the connection between the two viewpoints of corruption.  

One suggestion for the camera-ready version is to include the rebuttal's discussion (detailed explanation) on why the two viewpoints are equivalent in the appendix.
Decision: Accept (poster)