Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification

Authors: haolin  liu
artin  tajdini
andrew  wagenmaker
chen-yu  wei
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:30:42

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).

Main paper: 
 introduction: 
 The real world is rarely truly stochastic-in practice, our observations are often corrupted-and furthermore, rarely are the modeling assumption typically made in theory-that the true datagenerating 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 or severely suboptimal actions. In this work, we seek to address these challenges, and develop a unified understanding for robust learning in corruption-robust and misspecified settings.We first consider the corruption-robust 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 on misspecification usually 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-dependent misspecification-are in fact efficiently learnable with existing corruption robust algorithms.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 2 and Section 3 for formal definitions of the mentioned quantities):1. In Section 4, we develop a stochastic linear bandit algorithm with O(d √ T + min{dC, √ dC ∞ }) regret, where d is the feature dimension, T is the number of rounds, C is the strong corruption measure, and C ∞ 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 O(d √ T + √ dC ∞ ) and O( √ d 3 T + dC) regret for weak and strong corruptions, respectively. 3. We prove a general reduction that efficiently handles gap-dependent misspecification with corruption-robust algorithms. We apply our reduction to show that linear MDPs with gapdependent 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 as outlined above. 
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 ⊂ R d . At the beginning of round t, the environment determines a reward vector θ t ∈ R d and a corruption function ϵ t (•) : A → [-1, 1], which are both hidden from the learner. The learner then selects an action a t ∈ A. Then a reward value r t = a ⊤ t θ t + ϵ t (a t ) + ζ t is revealed to the learner, for some zero-mean noise ζ t ∈ [-1, 1]2 . We assume that ∥a∥ 2 ≤ 1, ∥θ t ∥ 2 ≤ √ d, and a ⊤ θ t ∈ [-1, 1] for any a ∈ A and any t = 1, 2, . . . , T . We define ϵ t = max a∈A |ϵ t (a)|.In the stochastic setting, the environment is restricted to choose θ t = θ ⋆ for all t, while in the adversarial setting, θ t can arbitrarily depend on the history up to round t -1. The regret of the learner is defined asReg T = max u∈A T t=1 u ⊤ θ t - T t=1 a ⊤ t θ t .Corruption Measure (CM) Viewpoint. In this viewpoint, the corruption is individually specified for every action. That is, at each round t, the adversary decides ϵ t (a) for all action a ∈ A and ensures E[r t |a t = a] -⟨a, θ ⋆ ⟩ = ϵ t (a) for all a. The adversary always decides ϵ t (•) before seeing a t . To evaluate the performance, we consider two different measures of the total corruption: the strong measure T t=1 |ϵ t (a t )| and the weak measure T t=1 max a∈A |ϵ t (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 are the same as those under strong/weak measure in the CM viewpoint, respectively. This is by the following observation. A strong adversary in the AA viewpoint who decides the corruption level ϵ t after seeing a t can be viewed as deciding the corruption ϵ t (a) for all action a before seeing a t , and set ϵ t = |ϵ t (a t )| after seeing a t . In other words, ϵ t (a) is the corruption planned (before seeing a t ) by a strong adversary assuming a t = a, and the adversary simply carries out its plan after seeing a t . It is clear that this is equivalent to the CM viewpoint with T t=1 |ϵ t (a t )| 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 ϵ t no matter which action a t is chosen by the learner. This can be viewed as deciding the corruption ϵ t (a) for every action a before seeing a t with the restriction |ϵ t (a)| ≤ ϵ t for all a. Therefore, this is equivalent to using T t=1 max a |ϵ t (a)| to measure total corruption in the CM viewpoint. In this work, we adopt the CM viewpoint as 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 ϵ t (•) based on 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, as the above argument suggests.With this unified viewpoint, we categorize in Table 1 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 C ∞ correspond to the strong measure and weak measure mentioned above, respectively. It is easy to see that C ≤ {C ∞ , C sq } ≤ C sq,∞ ≤ C ms , where C ∞ and C sq are incomparable.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 be chosen by an adaptive adversary in every round. Foster et al. (2020) and Takemura et al. (2021) reported their bounds in C sq,∞ and C ms , respectively, though one can make minor modifications to their analysis and show that their algorithms actually ensure the C sq bound. 2 . As in most previous work, we assume that C ∞ and C (or their upper bounds) are known by the learner when developing the algorithms. The case of unknown√ T + √ dC ∞ (Algorithm 1) d √ T + dC (He et al., 2022) Adversarial LB d √ T + √ dC ∞ (Algorithm 2) √ d 3 T + dC (Algorithm 3) Lower bound d √ T + √ dC ∞ (Lattimore etC ∞ or C is discussed in Appendix C.We emphasize that before our work, for both stochastic and adversarial linear bandits, it was unknown how to achieve O(d √ T + √ dC ∞ ) regret.√ T + √ dC ∞ ).The reason is that for deterministic algorithms, the adversary can control C ∞ to be the same as C, for which Ω(dT + 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 O(dT + √ dC ∞ ) upper bound, e.g., Lattimore et al. (2020) , Takemura et al. (2021) , Bogunovic et al. (2020 Bogunovic et al. ( , 2021)) , He et al. (2022) .Proposition 1. For stochastic linear bandits, there exists a deterministic algorithm achieving Reg T = O(d √ T + √ dC sq ), while any deterministic algorithm must sufferReg T = Ω(d √ T + dC ∞ ).Algorithm 1: Randomized Phased Elimination (for stochastic C ∞ and C bounds)Input: Z = √ dC ∞ or dC, action space A ⊂ R d , confidence level δ. Let A 1 = A and L = d log(|A|T /δ). for k = 1, 2, . . . doCompute a G-optimal design (defined in Section 2) p k over A k , and let G k = a p k (a)aa ⊤ .DefineI k = [(2 k-1 -1)L + 1, (2 k -1)L] and m k = |I k | = 2 k-1 L.for t ∈ I k do Draw a t ∼ p k and receive r t where E[r t ] = a ⊤ t θ ⋆ + ϵ t (a t ).Define reward vector estimator θ k = (m k G k ) -1 t∈I k a t r t and active action set:A k+1 = a ∈ A k : max b∈A k b ⊤ θ k -a ⊤ θ k ≤ 8 d log(|A|T /δ) m k + 2Z m k . (1)4 Stochastic Linear BanditsIn this section, we introduce Algorithm 1, which achieves optimal regret for both C and C ∞ .Algorithm 1 is an elimination-based algorithm. At each epoch k, it samples actions from a fixed distribution p k ∈ ∆(A k ), which is a G-optimal design over the active action set A k (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 a similar elimination framework to obtain O(d√ T + √ dC ms ) and O(d √ T + d 3 2 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 to exactly use the distribution p k to sample actions in every round in epoch k. As argued in Proposition 1, if their algorithms are instantiated as a deterministic algorithm, then the regret will be at least Ω(dT + dC ∞ ). Thus, this subtle difference is important.Note that to achieve the tight C ∞ (or C) bound, Z = √ dC ∞ (or Z = dC) has to be input to the algorithm to decide the error threshold. The guarantee of Algorithm 1 is stated in Theorem 4.1.Theorem 4.1. With input Z = √ dC ∞ or Z = dC, Algorithm 1 ensures with probability at least 1 -δ that Reg T ≤ O(d T log(T /δ) + Z log T ).Algorithm 1 can also be shown to ensure that Reg T ≤ O( dT log(|A|T /δ) + Z log T ), which could be smaller than the bound given in Theorem 4.1 when |A| is small. 
adversarial linear bandits: 
 In this section, we consider corrupted adversarial linear bandits. Although adversarial linear bandits have been widely studied, robustness under corruption is an under-explored topic: there is no prior work obtaining regret bounds that linearly depends on either C ∞ or C.Our algorithm (Algorithm 2) is based on follow-the-regularized-leader (FTRL) with logdet regularizer. Similar to previous works (Foster et al., 2020; Zimmert and Lattimore, 2022; Liu et al., 2024 Liu et al., , 2023b) ) that utilize logdet regularizer, the feasible set H is in R (d+1)×(d+1) , which is the space of the covariance matrix for distributions over the lifted action space (Line 2-Line 3). At round t, the algorithm obtains a covariance matrix H H H t by solving the FTRL objective (Eq. ( 2)). The action distribution p t is such that the induced covariance matrix is equal to H H H t (Eq. ( 3)). After sampling a t ∼ p t and obtaining the reward r t , the algorithm constructs reward vector estimator θ t (Line 8) and feeds it to FTRL. The reader may refer to Zimmert and Lattimore (2022) for more details.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, we adopt the idea of "adding exploration bonus" inspired Algorithm 2: FTRL with log-determinant barrier regularizer (for adversarial C ∞ bound)Parameters: α = max C∞ √ d log(T ) , √ T , η = log(T ) T and γ = d √ T . Let ρ ∈ ∆(A) be a G-optimal design over A, and let ∆ γ (A) = p : p = (1 -γ)p ′ + γρ, p ′ ∈ ∆(A) . Define feasible set H = Cov(p) : p ∈ ∆ γ (A) . ( Cov(p) is defined in Section 2) Define G(H H H) = -log det(H H H) and B 0 = 0. for t = 1, 2, . . . doSolve the fixed-point problem Eq. (2)-Eq. ( 5).EQUATIONEQUATIONB t = BONUS(B t-1 , Σ t ). (Defined in Figure 1a) (5) Sample a t ∼ p t . Observe reward r t with E[r t ] = a ⊤ t θ t + ϵ t (a t ).Construct reward estimator θ t = Σ -1 t a t r t .Function B ′ = BONUS(B, Σ): if B ⪯ Σ -1 then return B ′ = Σ -1 . else Perform eigen-decomposition: B -1 2 Σ -1 B -1 2 = d i=1 λ i v i v ⊤ i , where {v i } d i=1 are unit eigenvectors. return B ′ = B 1 2 d i=1 max{λ i , 1}v i v ⊤ i B 1 2 .(a) The bonus function𝐵 𝑡-1 Σ 𝑡 -1 𝐵 𝑡 (b) Illustration for Bt = BONUS(Bt-1, Σt).A psd matrix with eigenvalues (λi) d i=1 is represented as an ellipsoid with radius ( √ λi) d i=1 .Figure 1 : The bonus function and its illustration by previous work on 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 t in Eq. (5).To decide the form of B t , 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 ϵ t := max a |ϵ t (a)|)EQUATIONwhere Σ t is the feature covariance matrix induced by p t (defined in Eq. ( 4)). Below, we compare different bonus designs in previous and our work.Bonus design in previous work. In Zimmert and Lattimore (2022) , which is also based on logdet-FTRL but where the goal is only to get a high-probability bound, the bonus introduces an additional regret the form -α∥u∥ 2Σ -1 t + α a p t (a)∥a∥ 2 Σ -1 t. This can be used to cancel off the bias in Eq. ( 6):EQUATIONwhere we use AM-GM. Unfortunately, with the optimal α, this only leads to an additive regret dT t ϵ 2 t = √ dC sq,∞ > √ dC ∞ , which does not meet our goal.Bonus design in our work. To obtain the tighter √ dC ∞ = √ d t ϵ t bound, our idea is to construct a positive-definite matrix B t such that B t ⪰ Σ -1 τ for all τ ∈ [t], and add bonus B t -B t-1 at round t. This way, the total negative regret on u becomes -α∥u∥ 2 B T and the cancellation becomesEQUATIONwhere we use B T ⪰ Σ -1 t for all t and AM-GM. With this, it suffices to find B t satisfying our condition B t ⪰ Σ -1 τ for τ ≤ t, and bound the overheadT t=1 ⟨Σ t , B t -B t-1 ⟩ by O(d).It turns out that there exists a way to inductively construct B t so that B t ⪰ Σ -1 τ for all τ ≤ t andT t=1 ⟨Σ t , B t -B t-1 ⟩ ≲ log det(B T ) = O(d). This is by letting B t to be a minimal matrix such that B t ⪰ B t-1 and B t ⪰ Σ -1 t . By induction, this ensures B t ⪰ Σ -1 τ for all τ ≤ t. The function B t = BONUS(B t-1 , Σ t ) is formally defined in Figure 1a . The geometric interpretation is finding the minimal ellipsoid that contains both ellipsoids induced by B t-1 and Σ -1t . An illustration figure is given in Figure 1b .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 t ) in the FTRL objective when calculating the policy at round t (Eq. ( 2)). Notice that B t , in turn, depends on the policy at round t (Eq. ( 5), where Σ t depends on p t ), and thus this forms a fixed-point problem. In the regret analysis, this avoids the "stability term" of the bonus to 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 d √ log T C ∞ 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 -δ,Reg T = O(d √ T + √ dC ∞ ), where O(•) hides log(T /δ) factors.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 on action u's reward is bounded byEQUATIONUnlike in Eq. ( 6), we do not relax |ϵ t (a t )| to ϵ t = max a |ϵ t (a)| because we want the final bound to depend on C = t |ϵ t (a t )|. The idea to ensure that the sum of Eq. ( 9) over t can be related to C is to make ∥a t ∥ Σ -1 t bounded by a constant poly(d), which allows us to further bound Eq. ( 9) by poly(d)∥u∥ Σ -1 t |ϵ t (a t )|. Such a property holds in standard linear bandit algorithms that operate in the continuous action space where a t 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 a C sq bound. The bonus terms introduced by Lee et al. (2020) allows us to obtain a C bound, but the overhead introduced by the bonus terms is much larger, resulting in a highly sub-optimal regret bound. Indeed, as shown in Appendix J, adopting their bonus construction results in an additional regret of d 5 2 C. With several attempts, we are only able to obtain the tight corruption dependency dC using the bonus in Section 5.1. To use that bonus, however, it is necessary to lift the problem to (d + 1) 2 -dimensional space. Unfortunately, existing SCRiBLe and CEW algorithms only operate in the original d-dimensional space, and as discussed above, we need them to ensure ∥a t ∥ Σ -1 t ≤ poly(d).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, we assume without loss of generality Algorithm 3: Continuous exponential weights (for adversarial C bound)Parameters: γ = 1/T , α = √ dT + C, β = 4 log(10dT ), η = d/T . for t = 1, 2, . .Solve the fixed-point problem Eq. (10)-Eq. ( 13).EQUATIONLet q t ∈ ∆(H) and p t ∈ ∆(A) be the distributions of H H H ∈ H and a ∈ A, respectively, generated by the following (Z Z Z is a d × (d + 1) matrix):EQUATION)EQUATIONSample a t ∼ pt , and observe reward r t with E[r t ] = a ⊤ t θ t + ϵ t (a t ).Construct reward estimator θ t = Σ -1 t a t r t .that A = conv(A). The lifted action space is d+1) . The price of the lifting is that the "regularization penalty term" in the regret analysis now grows from O(d/η) to O(d 2 /η), which gives us the √ d 3 T sub-optimal regret.H = { Cov(p) : p ∈ ∆(A)} ⊂ R (d+1)×(Note that CEW requires the assumption that the feasible set is a convex body with non-zero volume, but the effective dimension of H is strictly smaller than (d+1) 2 and thus have zero volume in R (d+1) 2 . To correctly write the algorithm, we introduce an invertible linear transformation ϕ : R (d+1) 2 → R m that maps an (d + 1) 2 -dimensional action set H to an m-dimensional one, where m is the effective dimension of H. In Appendix I, we formally define this ϕ. The algorithm uses ϕ to map all lifted actions and reward estimators from R (d+1)×(d+1) to R m . The exponential weights runs 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 ∈ A according to Eq. (11). We use q ′ t to denote the exponential weight distribution in ϕ(H), and use p t to denote the corresponding distribution in A. Instead of sampling a t from p t , we sample it through rejection sampling that rejects samples with 12)). This technique was developed by Ito et al. (2020) , and∥a t ∥ Σ -1 t > Θ( √ d) (Eq. (this guarantees ∥a t ∥ Σ -1 t ≤ O( √ d)-which is our goal as discussed in Eq. ( 9)-while keeping the clipped distribution pt close enough to the original distribution p t . This last property heavily relies on the log-concavity of the exponential weight distribution (Ito et al., 2020) . The definition of the bonus term is similar to that in Algorithm 2 (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-point formulation where the calculation of the policy at time t involves the bonus at time t, which, in turn, depends on the policy at time t. It is unlikely that this algorithm can be polynomial time. As a remedy, we provide a polynomial time algorithm (Algorithm 6) in Appendix J with a much worse regret bound of O(d 3 √ T + d 5 /2 C). The regret guarantee of Algorithm 3 is given in the following theorem. Question: Does the paper provide open access to the data and code, with sufficient instructions 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/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. 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 on corruption" in Page 5 ofWei et al. (2022) for reducing this case to the bounded case.2 C) regret. The algorithm is based on the continuous exponential weight algorithm in the original feature space(Ito et al., 2020;Zimmert and Lattimore, 2022), with the bonus construction similar toLee et al. (2020). 
gap-dependent misspecification: 
 Intimately related to corrupted settings are misspecified 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 θ and ϵ mis (•) such that |f (a) -a ⊤ θ| ≤ ϵ mis (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 a ⊤ θ and with corruption ϵ mis (a) 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-dependent misspecification, ϵ mis (a). While it is relatively straightforward to obtain bounds on learning in misspecified settings for a uniform level of misspecification ϵ ≥ max a∈A ϵ mis (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 (Gap-Dependent Misspecification (Liu et al., 2023a) ). There exists some θ∈ R d such that some ρ > 0, denoting ∆(a) = max a ′ f (a ′ ) -f (a), we have for any a ∈ A, |f (a) -a ⊤ θ| ≤ ρ • ∆(a).We let M ⋆ denote the original environment with reward function f (a) (with Reg M ⋆ T the corresponding regret), and M 0 the environment with linear reward, a ⊤ θ, (with Reg M0 T the corresponding regret).Assumption 1 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-robust algorithm. Assumption 2. We have access to a regret minimization algorithm which takes as input some C ′ and with probability at least 1 -δ has regret bounded on M 0 asReg M0 T ≤ C 1 (δ, T ) √ T + C 2 (δ, T )C ′ if C ′ ≥ C ≜ T t=1ϵ mis (a t ), and by T otherwise, for C as defined above and for (problem-dependent) constants C 1 (δ, T ), C 2 (δ, T ) which may scale at most logarithmically with T and 1 δ . Assumption 2 is essentially the guarantee of a corruption-robust algorithm in terms of strong corruption measure (defined in Section 3). Note, in particular, that Assumption 2 only needs to obtain a 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 1 and that we have access to a corruptionrobust algorithm satisfying Assumption 2. Then as long as ρ ≤ min{ 1 2 , 1 4 C 2 ( δ T , T ) -1 }, with probability at least 1 -2δ we can achieve regret bounded as:Reg M ⋆ T ≤ 6C 1 ( δ T , T ) √ T + 4 2T log(1/δ) + 4.Theorem 6.1 states that, assuming our environment exhibits gap-dependent misspecification with tolerance ρ ≤ min{ 1 2 , 1 4 C 2 ( δ T , T ) -1 }, then we can achieve regret on the true environment bounded as the leading-order term of our corruption-robust oracle, C 1 ( δ T , T ) √ T , with additional overhead of only Õ( √ T ). This reduction is almost entirely black-box: it requires knowledge of C 1 (δ, T ) and C 2 (δ, T ), but does not require knowledge of ρ or any other facts about the corruption-robust algorithm. Remark 1 (Anytime Algorithm). The oracle of Assumption 5 must be anytime, achieving the above regret guarantee for any T not given as an input. Though many existing corruption-robust algorithms take T as input, the standard doubling trick can convert them into an anytime algorithm.We are particularly interested in how stringent a condition on the misspecification level-how small a value of ρ-Theorem 6.1 requires. As we have shown, Theorem 4.1 obtains the optimal misspecification level of dC. We then have the following corollary. While the regret bound of Corollary 6.1.1 achieves a scaling of O(d √ T ), which is tight for linear bandits (Lattimore and Szepesvári, 2020) , it is unclear its requirement onρ of ρ ≤ O( 1 d ) is optimal. The result below shows that it is not optimal because ρ ≤ O( 1 √ d ) suffices for O(d √ T ) regret.Theorem 6.2. Assume our environment is a misspecified linear bandit satisfying Assumption 1 withρ ≤ O( 1 √ d ).Then there exists an algorithm that achieves, w.p. 1 -δ:Reg M ⋆ T ≤ O(d T log(T /δ)).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 requires ρ ≤ O( 1 d ) (Liu et al., 2023a) . Moreover, for ρ > c T 1 √ d for some logarithmic term c T , adapting the lower-bound instance from Lattimore et al. (2020) , we show that achieving sub-linear regret is not possible (Theorem K.2). These results jointly show that ρ ≈ 1 √ d is the best ρ we can hope for. This disproves the conjecture of Liu et al. (2023a) that ρ = Θ(1) is possible.Note that the reduction in Theorem 6.1 is not able to achieve a tight ρ-while reducing from gapdependent misspecification to corruption allows for black-box usage of existing algorithms, it requires more stringent conditions on the misspecification level than specialized algorithms for this setting.Theorem 6.1 is a corollary of a more general result, Theorem L.1, which applies to misspecified reinforcement learning, where we there assume a generalized notion of gap-dependent misspecification: for each policy π,E M ⋆ ,π [ H h=1 ϵ mis h (s h , a h )] ≤ ρ • (V ⋆ 0 -V π 0 ), for V π 0 the expected reward of policy π, and ϵ mis h (s, a) a measure of the misspecification at step h, state s, and action a. To illustrate this general reduction, we consider the following setting, a generalization of linear MDPs (Jin et al., 2020) . Assumption 3 (Gap-Dependent Misspecified Linear MDPs). Let ϕ(s, a) : S × A → R d denote some feature map and µ h • S → R d some measure which satisfy ∥ϕ(s, a)∥ 2 ≤ 1, ∀s, a, and∥ s |dµ h (s)|∥ 2 ≤ √ d.Assume that the transitions P h (• | s, a) on our true environment satisfy:∥P h (• | s, a) -⟨ϕ(s, a), µ h (•)⟩∥ TV ≤ ϵ mis h (s, a)for some ϵ mis h (s, a) ≥ 0 and ∥P -Q∥ TV the total variation distance between P and Q. Furthermore, assume that for any policy π, we haveE π [ H h=1 ϵ mis h (s h , a h )] ≤ ρ • (V ⋆ 0 -V π 0). We then have the following result. Corollary 6.2.1. Assume our environment satisfies Assumption 3 with ρ ≤ O( 1 dH ). Then there exists an algorithm that achieves regret bounded with probability 1 -δ asReg M ⋆ T ≤ O( √ d 3 H 2 T ).To the best of our knowledge, Corollary 6.2.1 is the first result showing that it is possible to efficiently learn in linear MDPs with gap-dependent misspecification. Note that under Assumption 3, our MDP could be far from a linear MDP-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-robust algorithm for linear MDPs (Ye et al., 2023) . T + dC ∞ ) by He et al. (2022) and Ω(d Lattimore and Szepesvári (2020) . 
open problems: 
 √ T + √ dC ∞ ) byWith 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) . Li and Yang (2024) . These discussions, however, usually assume that the amount of misspecification has a 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 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 a setting where the amount of misspecification for an action is bounded by a constant times that action's sub-optimality gap. To our knowledge, this setting is first studied by Liu et al. (2023a) for linear bandits. Another related work is Zhang et al. (2023) , which assumes that the misspecification is bounded by a 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-dependent logarithmic regret bounds.Corruption-robust 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 misspeicifcation 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 C sq,∞ , C sq , C ∞ , and C discussed in Section 3. Among them, C sq,∞ and C ∞ are usually studied under the "weak adversary" framework where the adversary decides the corruption before seeing the action chosen by the learner. On the other hand, C sq 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. T + √ dC sq,∞ bound for linear contextual bandits with stochastic contexts and adversarial rewards, which can be improved to dT + √ dC sq,∞ when specialized to adversarial linear bandits. To our knowledge, no C ∞ 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 thatAT + C ∞ 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 aAT + AC bound for A-armed bandits, which is tight.The study of the best-of-both-world problem was initiated by Bubeck and Slivkins (2012) and extended by Seldin and Slivkins (2014) ; Auer and Chiang (2016) ; Seldin 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 a single algorithm that achieves a O( √ T ) regret when the reward is adversarial and O(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-both-world linear bandits problem. The underlying world could be stochastic (θ t = θ ⋆ for all t) or adversarial (θ t 's are arbitrary). Their algorithm achieves a bound of O(d 2 log(T )/∆) in the former case, where ∆ is the reward gap between the best and the second-best arm, and O(d √ T ) in the latter phase. They also define the corruption C ′ = t max a |a ⊤ (θ t -θ ⋆ )| and show that their algorithm achieves a regret of O(d 2 log(T )/∆ + d 2 log(T )C ′ /∆). 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.We show that strong corruption in both definitions is equivalent, that is, for any adversary having strong corruption C = t |ϵ t | from AA viewpoint, there exists an adversary using the equal amount of strong corruption t |ϵ ′ t (a t )| from CM viewpoint, where |ϵ t | = |ϵ ′ t (a t )| for all t, and vice versa. Assume that ϵ(H t-1 , a t ) is the function used by an AA strong adversary to decide the corruption at time t, where H t-1 is the history up to time t -1 and a t is the chosen action at time t. Then we define ϵ ′ t (a) ≜ ϵ(H t-1 , a), ∀a for the CM viewpoint, thus|ϵ t | = |ϵ(H t-1 , a t )| = |ϵ ′ t (a t )|.Note that the function ϵ ′ t (•) only depends on the history up to time t -1, so the definition of ϵ ′ t is known to adversary before observing a t . The other direction of this equivalence is achieved by setting the corruption in AA viewpoint as ϵ t = ϵ ′ t (a t ). Note that since a t is known to a strong adversary in AA viewpoint, ϵ t is also known.In the corrupted stochastic setting, Wei et al. (2022) developed a black-box reduction that can turn any algorithm achieving β 1√ T + β 2 + β 3 C ∞ regret with the knowledge of C ∞ into an algorithm achieving log(T ) × (β 1 √ T + β 2 + β 3 C ∞ ) regret without knowledge of C ∞ .This reduction can be directly applied to our stochastic C ∞ bound result (Theorem 4.1), which allows us to achieve almost the same regret bound without knowledge of C ∞ . 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 β 1√ T + β 2 + β 3 C ∞ regret with known C ∞ into one achieving log(T ) × (β 1 √ T + β 2 + β 3 C ∞ ) regret without knowing C ∞ .This can be directly applied to our adversarial C ∞ result (Theorem 5.1).The case of unknown C is quite different. It has been proven by Bogunovic et al. (2021) that it is impossible to achieve a bound that has linear scaling in C (e.g., β 1 √ T + β 2 + β 3 C) for all C simultaneously if C is not knownτ ∈Ψt,s ϵ τ (i τ )x τ (i τ ) ⊤ V -1 t-1,s x t (i) ≤ ϵ |Ψ t,s | τ ∈Ψt,s x τ (i τ ) ⊤ V -1 t-1,s x t (i) 2 , ≤ ϵ |Ψ t,s |x t (i) ⊤ V -1 t-1,s x t (i) ≤ ϵ |Ψ t,s |c -2s ≤ O(ϵ √ d).(by their Lemma 1)We can tighten their analysis by doing the following:τ ∈Ψt,s ϵ τ (i τ )x τ (i τ ) ⊤ V -1 t-1,s x t (i) ≤   τ ∈Ψt,s ϵ τ (i τ ) 2     τ ∈Ψt,s x τ (i τ ) ⊤ V -1 t-1,s x t (i) 2   , ≤   τ ∈Ψt,s ϵ τ (i τ ) 2   x t (i) ⊤ V -1 t-1,s x t (i) ≤   τ ∈Ψt,s ϵ τ (i τ ) 2   c -2s ≤ O    d |Ψ t,s | τ ∈Ψt,s ϵ τ (i τ ) 2    .(by their Lemma 1)Since the regret for every step in Ψ t,s can be bounded by this value, when summing the regret over Ψ T +1,s , one can get a regret of orderO   d|Ψ T +1,s | τ ∈Ψ T +1,s ϵ τ (i τ ) 2   .Further summing this over s (there are logarithmically many different s) and using that [T ] = s Ψ T +1,s and using Cauchy-Schwarz, we get a dTT t=1 ϵ t (i t ) 2 = √ dC sq bound.To argue that any deterministic algorithm must suffer at least Ω(d √ T + dC ∞ ) regret,∈ A k , |⟨b, θ k -θ ⋆ ⟩| ≤ 4 d log(|A|T /δ) m k + min{ √ dC ′ , dC} m k .Proof. Let E t [•] be the expectation conditioned on the history up to round t -1. We fix k and b and considerX t = b ⊤ (m k G k ) -1 a t r t for t ∈ I k . Notice that t∈I k X t = b ⊤ θ k and t∈I k E t [X t ] = t∈I k b ⊤ (m k G k ) -1 E t a t (a ⊤ t θ ⋆ + ϵ t (a t )) = b ⊤ θ ⋆ + b ⊤ (m k G k ) -1 t∈I k E t [a t ϵ t (a t )] .Also, by the definition of G k , we have|X t | = b ⊤ (m k G k ) -1 a t r t ≤ 1 m k ∥b∥ G -1 k ∥a t ∥ G -1 k ≤ d m k .Thus, by Freedman's inequality, with probability at least 1 -δ |A|T , the following holds:b, θ k -θ ⋆ = t∈I k X t - t∈I k E t [X t ] + b ⊤ (m k G k ) -1 t∈I k E t [a t ϵ t (a t )] ≤ log |A|T δ t∈I k E t [X 2 t ] term1 + d m k log |A|T δ + b ⊤ (m k G k ) -1 t∈I k E t [a t ϵ t (a t )] term2 .We bound term 1 byterm 1 = log(|A|T /δ) t∈I k E t b ⊤ (m k G k ) -1 a t a ⊤ t (m k G k ) -1 b = log(|A|T /δ) 1 m 2 k t∈I k b ⊤ G -1 k b ≤ d log(|A|T /δ) m k ,and term 2 byterm 2 = 1 m k t∈I k a∈A k p k (a)ϵ t (a)b ⊤ G -1 k a ≤ 1 m k t∈I k a∈A k p k (a)ϵ t (a) 2 a∈A k p k (a) b ⊤ G -1 k a 2 ≤ 1 m k t∈I k max a ′ ϵ t (a ′ ) √ d ≤ √ dC ′ m k .orterm 2 ≤ 1 m k t∈I k E t ϵ t (a t ) b ⊤ G -1 k a t ≤ 1 m k t∈I k ϵ t (a t ) b ⊤ G -1 k a t + 1 m k log |A|T δ t∈I k E t ϵ t (a t ) 2 b ⊤ G -1 k a t 2 + ϵ t (a t )b ⊤ G -1 k a t m k log |A|T δ (Freedman's inequality) ≤ d m k t∈I k ϵ t (a t ) + 1 m k log |A|T δ t∈I k E t b ⊤ G -1 k a t a ⊤ t G -1 k b + d m k log |A|T δ ≤ dC m k + 1 m k log |A|T δ t∈I k b ⊤ G -1 k b + d m k log |A|T δ ≤ dC m k + d log(|A|T /δ) m k + d m k log |A|T δ .Thus, for any b ∈ A k , with probability at least1 -δ |A|T , b, θ k -θ ⋆ ≤ 2 d log(|A|T /δ) m k + 2d m k log(|A|T /δ) + 1 m k min √ dC ′ , dC ≤ 4 d log(|A|T /δ) m k + 1 m k min √ dC ′ , dC . (m k ≥ d log(|A|/δ))Taking a union bound over k and b ∈ A k finishes the proof.Lemma E.2. Let a ⋆ = argmax a∈A a ⊤ θ ⋆ . Then with probability at least 1 -2δ, a ⋆ ∈ A k for all k.Proof. Suppose that the high-probability event in Lemma E.1 holds. For any k,if a ⋆ ∈ A k , then for any b ∈ A k , b ⊤ θ k -a ⋆ ⊤ θ k ≤ b ⊤ θ ⋆ -a ⋆ ⊤ θ ⋆ + b ⊤ ( θ k -θ ⋆ ) + a ⋆ ⊤ ( θ k -θ ⋆ ) ≤ 0 + 2   4 d log(|A|T /δ) m k + min{ √ dC ′ , dC} m k   .By the definition of A k+1 in Eq. ( 1), we have a ⋆ ∈ A k+1 . The lemma is then proven by an induction argument.Proof of Theorem 4.1. We first calculate the regret in epoch k > 1 assuming that the event in Lemma E.2 holds.t∈I k max a∈A a ⊤ θ ⋆ -a ⊤ t θ ⋆ ≤ t∈I k max a∈A a ⊤ θ k-1 -a ⊤ t θ k-1 + 2m k max a∈A k a ⊤ θ k-1 -θ ⋆ ≤ m k • O d log(|A|T /δ) m k-1 + min{ √ dC ′ , dC} m k-1 = O dm k log(|A|T /δ) + min{ √ dC ′ , dC} .Summing this over k and using that m 1 = d log(|A|T /δ), we getT t=1 max a∈A a ⊤ θ ⋆ -a ⊤ t θ ⋆ ≤ O dT log(|A|T /δ) + d log(|A|T /δ) + min{ √ dC ′ , dC} log T .Notice that without loss of generality we can assume d log(|A|T /δ) ≤ T (otherwise the right-hand side is vacuous). Using this fact gives the desired bound.From Exercise 27.6 in Lattimore and Szepesvári (2020), the ϵ-covering number of A is bounded by T ) as A 1 in Algorithm 1 to conduct phase elimination. In that case, following above proof, we haveT t=1 max a∈C(A, 6d T ) a ⊤ θ ⋆ -a ⊤ t θ ⋆ ≤ O dT log C A, 6d T T /δ + min{ √ dC ′ , dC} log T ≤ O d T log(T /δ) + min{ √ dC ′ , dC} log T .From the definition of covering number, there exists a a ⋆ c ∈ C(A, 6d T ) such thatmax a∈A a ⊤ θ ⋆ -(a ⋆ c ) ⊤ θ ⋆ ≤ 6d T .We haveT t=1 max a∈A a ⊤ θ ⋆ -max a∈C(A, 6d T ) a ⊤ θ ⋆ ≤ T t=1 max a∈A a ⊤ θ ⋆ -(a ⋆ c ) ⊤ θ ⋆ + T t=1 (a ⋆ c ) ⊤ θ ⋆ -max a∈C(A, 6d T ) a ⊤ θ ⋆ ≤ 6d.Thus,T t=1 max a∈A a ⊤ θ ⋆ -a ⊤ t θ ⋆ ≤ O d T log(T /δ) + min{ √ dC ′ , dC} log T .F Proof of Theorem 5.1In this section, we use the following notation:γ γ γ t = 0 1 2 θ t 1 2 θ ⊤ t 0 , D D D t = αB t -αB t-1 0 0 0 .Algorithm 2 is equivalent to the FTRL update:EQUATION)Algorithm 4 is equivalent toEQUATION)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 U U ∈ H,T t=1 ⟨U U U -H H H t , γ γ γ t ⟩ ≤ G(U U U ) -min H H H∈H G(H H H) η - T t=1 ⟨U U U -H H H t , D D D t ⟩ + T t=1 max H H H∈H ⟨H H H -H H H t , γ γ γ t ⟩ - D G (H H H, H H H t ) η .Lemma F.2. The update rule Eq. ( 15) (Algorithm 4) ensures for any U U U ∈ H,T t=1 ⟨U U U -H H H t , γ γ γ t ⟩ ≤ G(U U U ) -min H H H∈H G(H H H) η - T t=1 ⟨U U U -H H H t , D D D t ⟩ + T t=1 max H H H∈H ⟨H H H -H H H t , γ γ γ t + D D D t ⟩ - D G (H H H, H H H t ) η .We consider an arbitrary comparator p ⋆ ∈ ∆(A) with u ⋆ = E a∼p⋆ [a] . Define p = (1 -γ)p ⋆ + γρ.We have p ∈ ∆ γ (A), and define u = E a∼p [a] and U U U = Cov(p). The regret with respect to p ⋆ can be decomposed as the following: With probability at least 1 -δ,EQUATIONBy Lemma F.1, the FTRL term can further be bounded byEQUATIONIn the following five lemmas, we bound the five terms Bias, Deviation, Penalty, Bonus, and Stability.Lemma F.3.Bias ≤ C ∞ max t ∥u∥ Σ -1 t + √ dC ∞ .Proof.E t u -x t , -Σ -1 t a t ϵ t (a t ) ≤ E t (u -x t ) ⊤ Σ -1 t a t a ⊤ t ϵ 2 t (a t )Σ -1 t (u -x t ) ≤ (u -x t ) ⊤ Σ -1 t E t a t a ⊤ t ϵ 2 t (a t ) Σ -1 t (u -x t ) ≤ ϵ t ∥u -x t ∥ Σ -1 t ≤ ϵ t ∥x t ∥ Σ -1 t + ϵ t ∥u∥ Σ -1 t ≤ √ dϵ t + ϵ t ∥u∥ Σ -1 t . (Σ t ⪰ x t x ⊤ t )Thus,Bias = T t=1 u -x t , θ t -E t Σ -1 t a t a ⊤ t θ t =0 +E t T t=1 u -x t , -Σ -1 t a t ϵ t (a t ) ≤ C ∞ max t ∥u∥ Σ -1 t + √ dC ∞ .Lemma F.4. With probability of at least 1 -δ, we haveDeviation ≤ max t ∥u∥ Σ -1 t 12 T log(T /δ) + 12 √ d log(T /δ) √ γ + 12 dT log(T /δ) + 12d log(T /δ) √ γ Proof. Notice that ⟨u -x t , θ t ⟩ ≤ (u -x t ) ⊤ Σ -1 t a t ≤ ∥u -x t ∥ Σ -1 t ∥a t ∥ Σ -1 t ≤ √ d √ γ ∥u -x t ∥ Σ -1 t .By the strengthened Freedman's inequality (Lemma M.3), with probability at least 1 -δ, Deviation = T t=1 u -x t , E t [ θ t ] -θ t ≤ 3 T t=1 E t u -x t , θ t 2 log(d 4 T 4 /δ) + 2 • √ d √ γ max t ∥u -x t ∥ Σ -1 t log(d 4 T 4 /δ) ≤ max t ∥u -x t ∥ Σ -1 t 12 T log(T /δ) + 12 √ d log(T /δ) √ γ ≤ max t ∥u∥ Σ -G(U U U ) -min H H H∈H G(H H H) η ≤ G d+1 T H H H 0 -G ((d + 1)H H H 0 ) η = 1 η log det ((d + 1)H H H 0 ) det d+1 T H H H 0 = (d + 1) log(T ) η .Lemma F.6.Bonus ≤ 3αd log(T ) -α max t ∥u∥ 2 Σ -1 t . Proof. Given E a∼p0 [aa ⊤ ] ⪰ E a∼p0 [a]E a∼p0 [a] ⊤ = uu ⊤ , we have T t=1 ⟨U U U , D D D t ⟩ = E a∼p0 [aa ⊤ ], αB T ≥ uu ⊤ , αB T = α∥u∥ 2 B T .Recall that B 1 = Σ -1 1 and for t ≥ 2,EQUATIONwhich ensures B t ⪰ B t-1 and B t ⪰ Σ -1 t . By induction, it leads to B T ⪰ Σ -1 t for any t. This implies∥u∥ 2 B T ≥ max t ∥u∥ 2 Σ -1 t . Thus, T t=1 ⟨U U U , D D D t ⟩ ≥ α max t ∥u∥ 2 Σ -1 t .Next, we upper boundT t=1 ⟨H H H t , D D D t ⟩. First, notice that ⟨H H H 1 , D D D 1 ⟩ = αTr(Σ t B t ) = Tr(I) = αd. For t ≥ 2, ⟨H H H t , D D D t ⟩ = αTr (Σ t (B t -B t-1 )) = αTr   B -1 2 t-1 d i=1 λ ti v ti v ⊤ ti -1 B -1 2 t-1 B 1 2 t-1 d i=1 max{λ ti -1, 0}v ti v ⊤ ti B 1 2 t-1   (by Eq. (19)) = αTr   d i=1 λ ti v ti v ⊤ ti -1 d i=1 max{λ ti -1, 0}v ti v ⊤ ti   = α d i=1 max 1 - 1 λ ti , 0 ≤ α d i=1 max{log λ ti , 0}.We also haveEQUATIONFinally, we bound log det (B T ). Since Σ t = a p t (a)aa ⊤ ⪰ γ a ρ(a)aa ⊤ , by Theorem 3 of Bubeck et al. (2012) , we haveΣ t ⪰ γ d I and Σ -1 t ⪯ d γ I for all t. Thus, B 1 = Σ -1 1 ⪯ d γ I. Below, we use induction to show that B t ⪯ td γ I. Assume B t-1 ⪯ (t-1)d γ I. Then, B t = B 1 2 t-1 d i=1 max{λ ti , 1}v ti v ⊤ ti B 1 2 t-1 ⪯ B 1 2 t-1 d i=1 (λ ti + 1)v ti v ⊤ ti B 1 2 t-1 = Σ -1 t + B t-1 ⪯ d γ I + (t -1)d γ I = td γ I.By induction, we get B T ⪯ T d γ I and log det (B T ) ≤ 2d log(T ) by setting γ = d √ T . Overall, by Eq. ( 20), we have Proof. For any p, define µ(p) = E a∼p [a] andT t=1 ⟨H H H t , D D D t ⟩ ≤ 3αd log(T ).Cov(p) = E a∼p [(a -µ(p))(a -µ(p)) ⊤ ], Cov(p) = E a∼p Cov(p) + µ(p)µ(p) ⊤ µ(p) µ(p) ⊤ 1 .For anyH H H = H + hh ⊤ h h ⊤ 1 , given H H H t = Cov(p t ) + x t x ⊤ t x t x ⊤ t 1, we have⟨H H H -H H H t , γ γ γ t ⟩ - D G (H H H, H H H t ) 2η ≤ ⟨H H H -H H H t , γ γ γ t ⟩ - ∥x t -h∥ 2 Cov(pt) -1 2η (Lemma M.1) = h -x t , θ t - ∥x t -h∥ 2 Cov(pt) -1 2η ≤ η∥ θ t ∥ 2 Cov(pt) (AM-GM) = ηr 2 t a ⊤ t Σ -1 t Cov(p t )Σ -1 t a t ≤ η∥a t ∥ 2 Σ -1 t .( ∥a t ∥ 2 Σ -1 t ≤ O dηT + ηd log(1/δ) γ .Proof of Theorem 5.1. Using Lemma F.3-Lemma F.7 in Eq. ( 17) and Eq. ( 18), we get Let ρ ∈ ∆(A) be John's exploration over A, and letReg T ≤ O d log(T ) η + ηdT + αd log(T ) + dT log(T /δ) + d log(T /δ) √ γ + ηd log(1/δ) γ + √ dC ∞ + γT + max t ∥u∥ Σ -1 t 12 T log(T /δ) + 12 √ d log(T /δ) √ γ + C ∞ -α max t ∥u∥ 2 Σ -1 t ≤ O d log(T ) η + ηdT + αd log(T ) + dT log(T /δ) + d log(T /δ) √ γ + ηd log(1/δ) γ + (C ∞ ) 2 α + T log(T /δ) α + d log 2 (T /δ) γα + √ dC ∞ + γT . (AM-GM) Therefore, the choice γ = d √ T , α = max C∞ √ d log(T ) , √ T and η = log(T ) T gives Reg T ≤ O d √ T log(T /δ) + C ∞ d log(T ) .∆ γ (A) = p : p = (1 -γ)p ′ + γρ, p ′ ∈ ∆(A) . Define feasible set H = Cov(p) : p ∈ ∆ γ (A) . Define G(H H H) = -log det(H H H) and B 0 = 0. for t = 1, 2, . . . do Compute H H H t = argmax H H H∈H {η ⟨H H H, Θ Θ Θ t-1 ⟩ -G(H H H)} where Θ Θ Θ t-1 = αB t-1 1 2 t-1 s=1 θ s 1 2 t-1 s=1 θ ⊤ s 0 , p t ∈ ∆ γ (A) be such that H H H t = Cov(p t ), Σ t = a∈A p t (a)aa ⊤ , B t = BONUS(B t-1 , Σ t ).(defined in Figure 1a )Sample a t ∼ p t . Observe reward r t with E[r t ] = a ⊤ t θ t + ϵ t (a t ).Construct reward estimatorθ t = Σ -1 t a t r t . end G Computationally Efficient Algorithm for Adversarial C ∞ BoundMost proof is the same as Appendix F. Namely, we follow Eq. ( 17) in Appendix F together with a different decompositionEQUATIONBy Lemma F.2, we can further bound FTRL byFTRL ≤ G(U U U ) -min H H H∈H G(H H H) η Penalty + T t=1 ⟨U U U -H H H t , -D D D t ⟩ Bonus + T t=1 max H H H∈H ⟨H H H -H H H t , γ γ γ t ⟩ - D G (H H H, H H H t )Stability-1EQUATION)Among the terms above, Bias, Penalty, Deviation, Bonus, and Stability-1 follow the same bounds as Lemma F.3, Lemma F.5, Lemma F.6, and Lemma F.7, respectively. It remains to boundStability-2. Lemma G.1. If η ≤ 1 16 √ dα , then Stability-2 ≤ 8ηα 2 d.Proof. From the analysis of bias term and H H H t and D D D t are both positive semi-definite, we haveTr (H H H t D D D t H H H t D D D t ) = α Tr (Σ t (B t -B t-1 ) Σ t (B t -B t-1 )) ≤ α √ dwhere the last inequality is due toΣ -1 t ⪰ B t -B t-1 . Since η ≤ 1 16√ dα , by Lemma M.2, with probability of at least 1 -δ, we haveStability-2 ≤ 8η T t=1 Tr (H H H t D D D t H H H t D D D t ) ≤ 8ηα 2 T t=1 Tr (Σ t (B t -B t-1 ) Σ t (B t -B t-1 )) ≤ 8ηα 2 dwhere 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 H Proof of Theorem 5.2Reg T = O d log(T ) η + ηdT + dα log(T ) + dT log(T /δ) + d log(T /δ) √ γ + ηd log(1/δ) γ + ηα 2 d + (C ∞ ) 2 α + T log(T /δ) α + d log 2 (T /δ) γα + √ dC ∞ + γT By choosing α = maxSimilar to before, we defineγ γ γ t = 0 1 2 θ t 1 2 θ ⊤ t 0 , D D D t = αB t -αB t-1 0 0 0 , and x t = E a∼pt [a], xt = E a∼ pt [a].We perform the regret decomposition as the following.EQUATION)The FTRL term can be further bounded as the following.FTRL = T t=1 E a∼pt u -a, θ t = T t=1 E H H H∼qt [⟨U U U -H H H, γ γ γ t ⟩] ≤ d 2 log T η + 1 η T t=1 E H H H∼qt [exp (η ⟨H H H, γ γ γ t ⟩) -η ⟨H H H, γ γ γ t ⟩ -1] + T t=1 E H H H∼qt [⟨H H H -U U U , D D D t ⟩](by Theorem I.2)EQUATION)In the following four lemmas, we bound the four terms Bias, Deviation, Bonus, Stability.Lemma H.1.Bias ≤ max t ∥x t -u∥ Σ -1 t dγT + 2 T log(1/δ) + √ dβC .Proof.Bias = T t=1 u -x t , θ t -E t [ θ t ] = T t=1 u -x t , θ t -Σ -1 t E t a t a ⊤ t θ t + Σ -1 t E t [a t ϵ t (a t )] = γ T t=1 u -x t , Σ -1 t θ t + T t=1 u -x t , -Σ -1 t E t [a t ϵ t (a t )] ( Σ t = γI + E t [a t a ⊤ t ]) ≤ γ T t=1 ∥x t -u∥ Σ -1 t ∥θ t ∥ Σ -1 t + T t=1 ∥x t -u∥ Σ -1 t E t ∥a t ∥ Σ -1 t |ϵ t (a t )| ≤ max t ∥x t -u∥ Σ -1 t γ d γ T + T t=1 E t ∥a t ∥ Σ -1 t |ϵ t (a t )| ( Σ t ⪰ γI and ∥θ t ∥ 2 ≤ √ d) ≤ max t ∥x t -u∥ Σ -1 t dγT + √ dβ T t=1 E t [|ϵ t (a t )|] ≤ max t ∥x t -u∥ Σ -1 t dγT + 2 T log(1/δ) + √ dβ T t=1 |ϵ t (a t )| . (Azuma's inequality) Lemma H.2. Deviation ≤ O max t ∥u -x t ∥ Σ -1 t dβ √ T log(T /δ) . Proof. Notice that ⟨u -x t , θ t ⟩ ≤ (u -x t ) ⊤ Σ -1 t a t ≤ ∥u -x t ∥ Σ -1 t ∥a t ∥ Σ -1 t ≤ √ dβ∥u -x t ∥ Σ -1 t .By the strengthened Freedman's inequality (Lemma M.3), with probability at least 1 -δ,Deviation = T t=1 u -x t , E t [ θ t ] -θ t ≤ O   3 T t=1 E t u -x t , θ t 2 log(T d /δ) + 2 √ dβ max t ∥u -x t ∥ Σ -1 t log(T d /δ)   ≤ O max t ∥u -x t ∥ Σ -1 t dβ √ T log(T /δ) . (using the assumption d ≤ T ) Lemma H.3. Bonus ≤ 3αd log(T ) -α max t ∥u∥ 2 Σ -1 t .Proof. The proof the same as in the logdet case. See the proof of Lemma F.6.Lemma H.4.Stability ≤ O(ηdT log 2 T ).Proof.Stability = 1 η T t=1 E a∼pt exp η a, θ t -η a, θ t -1Since q ′ t is a log-concave distribution, so are q t and p t , which further implies that η a, θ t follows a log-concave distribution. Furthermore,E a∼pt η 2 a, θ t 2 ≤ E a∼pt η 2 a ⊤ t Σ -1 t aa ⊤ Σ -1 t a t ≤ 2η 2 ∥a t ∥ 2 Σ -1 t ≤ 2η 2 dβ 2 ≤ 1 100 ,where we use Lemma J.2 in the second-last inequality . By Lemma 6 of Ito et al. (2020) , we have1 η T t=1 E a∼pt exp η a, θ t -η a, θ t -1 ≤ η T t=1 E a∼pt a, θ t 2 ≤ 2η T t=1 ∥a t ∥ 2 Σ -1 t ≤ 2ηβ 2 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 byO d 2 η + ηdT + max t ∥u -x t ∥ Σ -1 t (d √ T + √ dC) + dC + αd -α∥u∥ 2 B T ≤ O d 2 η + ηdT + αd + d 2 T + dC 2 α (AM-GM inequality)Choosing optimal α and η leads to O( √ d 3 T + dC).First, the intrinsic dimension of X can be defined as the following:Definition 1. The intrinsic dimension of X is defined asdim(X ) = dim (span (X -X )) ,where X -X ≜ {x -x ′ : x, x ′ ∈ X }.A convex region X ⊂ R n can be translated and rotated so that it entirely lies in R m where m = dim(X ) and has non-zero volume in R m . We more precisely define this transformation below.Definition 2. Let X ⊂ R n be a convex region with dim(X ) = m. We define ϕ : R n → R m as the following linear transformation:ϕ(x) ≜ ZM x,where M ∈ R n×n is a rotation matrix (i.e., orthogonal matrix) such that for any v ∈ X -X , M v has non-zero elements only in the first m coordinates (this is always possible by the definition of dim(X ) in Definition 1), andZ =     1 0 • • • 0 0 • • • 0 0 1 • • • 0 0 • • • 0 . . . . . . . . . . . . . . . • • • . . . 0 0 • • • 1 0 • • • 0     ∈ R m×nextracts the first m coordinates of a given n-dimensional vector.Lemma I.1. For any x ∈ X and anyθ ∈ R n , ⟨x, θ⟩ = ⟨ϕ(x), ϕ(θ)⟩ + f (ϕ, θ),where f (ϕ, θ) ∈ R is some quantity that only depends on ϕ and θ but not x.Proof. Let x, x ′ ∈ X . By the definition of ϕ, we have⟨ϕ(x) -ϕ(x ′ ), ϕ(θ)⟩ = ⟨ZM (x -x ′ ), ZM θ⟩ .By the choice of M in Definition 2, M (x -x ′ ) only has non-zero elements in the first m coordinates. Furthermore, since Z extracts the first m coordinates, we have⟨ZM (x -x ′ ), ZM θ⟩ = m i=1 (M (x -x ′ )) i (M θ) i = n i=1 (M (x -x ′ )) i (M θ) i = ⟨M (x -x ′ ), M θ⟩ = ⟨x -x ′ , θ⟩ . (M ⊤ = M -1 because M is a rotation matrix) Thus, ⟨x, θ⟩ -⟨ϕ(x), ϕ(θ)⟩ = ⟨x ′ , θ⟩ -⟨ϕ(x ′ ), ϕ(θ)⟩ ,meaning that the value of ⟨x, θ⟩ -⟨ϕ(x), ϕ(θ)⟩ is shared by all x ∈ X . Defining this value as f (ϕ, θ) finishes the proof.We consider the continuous exponential weight algorithm (Algorithm 5) running on ϕ(X ) ⊂ R m :Algorithm 5: Exponential Weights Let X ⊂ R n , and let ϕ(X ) ≜ {ϕ(x) : x ∈ X }. for t = 1, 2, . . . do Define for y ∈ ϕ(X ),w t (y) = exp η t-1 s=1 ⟨y, ϕ(θ s )⟩ + η t s=1⟨y, ϕ(b s )⟩ and p t (y) = w t (y)y ′ ∈ϕ(X ) w t (y ′ )dy ′for some bonus term b t .Sample y t ∼ p t , and play x t = ϕ -1 (y t ), where ϕ -1 is the inverse mapping of ϕ.Receive θ t ∈ R n .In Algorithm 5, we require that the inverse mapping of ϕ exists. This is true because for any x, x ′ ∈ X , we have ∥ϕ(x) -ϕ(x ′ )∥ = ∥ZM (x -x ′ )∥ = ∥M (x -x ′ )∥ = ∥x -x ′ ∥, and thus ϕ cannot map x, x ′ ∈ X with x ̸ = x ′ to the same point.Theorem I.2. Let q t ∈ ∆(X ) be the distribution such that x ∼ q t is equivalent to first drawing y ∼ p t and then taking x = ϕ -1 (y). Algorithm 5 ensures for any x ∈ X ,T t=1 ⟨x, θ t + b t ⟩ - T t=1 E x∼qt [⟨x, θ t + b t ⟩] ≤ m log T η + 1 η T t=1 E x∼qt [exp (η ⟨x, θ t ⟩) -η ⟨x, θ t ⟩ -1] .Proof. Note that Algorithm 5 is a standard continuous exponential weight algorithm over reward vectors ϕ(θ t ) and in the space of ϕ(X ) ⊂ R m . By the standard analysis (see, e.g., Ito et al. (2020) ; Zimmert and Lattimore ( 2022)), we have for any sequence λ 1 , . . . , λ T ∈ R and any y ∈ ϕ(X ),T t=1 ⟨y, ϕ(θ t ) + ϕ(b t )⟩ - T t=1 E y∼pt [⟨y, ϕ(θ t ) + ϕ(b t )⟩] ≤ m log T η + 1 η T t=1 E y∼pt exp η ⟨y, ϕ(θ t )⟩ + λ t -η ⟨y, ϕ(θ t )⟩ + λ t -1 .By Lemma I.1, the above impliesT t=1 ϕ -1 (y), θ t + b t - T t=1 E y∼pt ϕ -1 (y), θ t + b t ≤ m log T η + 1 η T t=1 E y∼pt exp η ϕ -1 (y), θ t -ηf (ϕ, θ t ) + λ t -η ϕ -1 (y), θ t -ηf (ϕ, θ t ) + λ t -1 ,which further implies that for any x ∈ X ,T t=1 ⟨x, θ t + b t ⟩ - T t=1 E x∼qt [⟨x, θ t + b t ⟩] ≤ m log T η + 1 η T t=1 E x∼qt [exp (η ⟨x, θ t ⟩) -η ⟨x, θ t ⟩ -1]by the definition of q t and by letting λ t = ηf (ϕ, θ t ).In this section, we present Algorithm 6, a polynomial-time algorithm that ensures O(d 3 √ T + dEntropic barrier For any convex body A, the family of exponential distribution isp w (x) = exp(w ⊤ x)1{y ∈ A} A exp(w ⊤ y)dy .For any x ∈ A, there is a unique w(x) such that E y∼p w(x) [y] = x. The entropic barrier F (x) is the negative entropy of p w(x) . NamelyF (x) = p w(x) (y) log p w(x) (y) dy We have ∇F (x) = w(x) and ∇ 2 F (x) = E y∼p w(x) (y -x)(y -x) ⊤ . We know that F (x) is a d-self-concordant barrier on A.The equivalence of mean-oriented FTRL and continuous exponential weights Consider FTRL with entropic barrier as the regularizer that solves x t for round t ∈ [T ] followingx t+1 = argmax x∈A x, t s=1 θ s - F (x) η t .This is equivalent to∇F (x t+1 ) = η t t s=1 θ s .Given that E y∼p w(x t+1 ) [y] = x t+1 and ∇F (x t+1 ) = w(x t+1 ), playing x t+1 yields the same expected reward as playing according to distribution p w(xt+1) where w(x t+1 ) = η t t s=1 θ s . Thus, we have p w(xt+1) (x) ∝ exp η t x, |E a∼pt [f (a)] -E a∼ pt [f (a)]| ≤ 10d exp(-β) ≤ 1 2T 2 for any f : A → [-1, 1] and 3 4 E a∼pt [aa ⊤ ] ⪯ E a∼ pt [aa ⊤ ] ⪯ 4 3 E a∼pt [aa ⊤ ].Proof. The proof follows that of Lemma 4 of Ito et al. (2020) , with the observation that p t is a log-concave distribution.Lemma J.3 (Lemma 14 of Zimmert and Lattimore (2022) ). Let f be a ν-self-concordant barrier forA ⊂ R d . Then for any u, x ∈ A, ∥u -x∥ ∇ 2 f (x) ≤ -γ ′ ⟨u -x, ∇f (x)⟩ + 4γ ′ ν + 2 √ ν where γ ′ = 8 3 √ 3 + 7 3 2 6 √ 3ν (γ ′ ∈ [1, 4] for ν ≥ 1).Minkowsky Functions. The Minkowsky function of a convex boday A with the pole at w ∈ int(A) is a function π w : A → R defined asEQUATIONAlgorithm 6: Continuous exponential weights (for adversarial C bound)Let A ⊂ R d be a convex body and F be its entropic barrier.Parameters: γ = log(T /δ) T , α = Θ( √ dC + d √ T ), η = min 1 160 √ d 3 T , 1 32 √ dα . for t = 1, 2, . . . , T do Define w t (a) = exp η t-1 s=1 ⟨a, θ s -b s ⟩ and p t (a) = w t (a) y∈A w t (y)dy , pt (a) = p t (a)1{∥a∥ Σ -1 t ≤ √ dβ} a ′ ∈A p t (a ′ )1{∥a ′ ∥ Σ -1 t ≤ √ dβ}da ′ ,whereΣ t = E a∼pt [aa ⊤ ].Play a t ∼ pt , and observe rewardr t with E[r t ] = a ⊤ t θ t + ϵ t (a t ).Construct reward estimator θ t = Σ -1 t a t r t , whereΣ t = γI + E a∼ pt [aa ⊤ ]. Define B B B t = I + Σ -1 t -Σ -1 t x t -x ⊤ t Σ -1 t x ⊤ t Σ -1 t x t, where Nesterov and Nemirovskii (1994) ).x t = E a∼pt [a]. if λ max (B B B t -τ ∈I B B B s ) > 0 then I ← I ∪ {t}. b t = -α∇F (x t ) where x t = E a∼pt [a] and ∇F (x t ) = η t-1 s=1 ( θ s -b s ). else b t = 0. Lemma J.4 (Proposition 2.3.2 inLet f be a ν-self-concordant barrier on A ⊆ R d , and u, w ∈ int(A). Thenf (u) -f (w) ≤ ν log 1 1 -π w (u).We perform regret decomposition. For regret comparator u ⋆ ∈ A, define x ⋆ = min x∈A F (x) and u = (1 -1 T )u ⋆ + 1 T x ⋆ . With probability at least 1 -δ,Reg T = T t=1 ⟨u ⋆ -a t , θ t ⟩ = T t=1 ⟨u -a t , θ t ⟩ + 1 T T t=1 ⟨u ⋆ -x ⋆ , θ t ⟩ = T t=1 ⟨u -xt , θ t ⟩ + O T log(1/δ) + 2 (define xt = E a∼ pt [a]and by Azuma's inequality)EQUATIONBy standard FTRL analysis, we haveEQUATIONThe individual terms Bias, Deviation, Bonus, Penalty, Stability terms are bounded in Lemma J.6, Lemma J.7, Lemma J.9, Lemma J.10, Lemma J.12. Lemma J.5. For any t ∈ [T ], if a ∼ p t , then with probability of at least 1 -δ,∥a∥ Σ -1 t ≤ √ d log 3d δ . Proof. Define y = Σ -1 2 t a. Then E y yy ⊤ = Σ -1 2 t E a∼pt [aa ⊤ ]Σ -1 2 t = I.Since p t is a logconcave distribution, and log-concavity is preserved under liner transformation, y is also log-concave. Applying Lemma J.1 on it leads toPr ∥a∥ 2 Σ -1 t ≥ dβ 2 = Pr ∥y∥ 2 2 ≥ dβ 2 ≤ d exp(1 -β) ≤ 3d exp(-β).Setting δ = 3d exp(-β), we conclude that with probability at least 1-δ, ∥a∥ 2Σ -1 t ≤ d log 3d δ 2 .Lemma J.6. With probability at least 1 -O(δ),Bias ≤ max t ∥x t -u∥ Σ -1 t dγT + 2 T log(1/δ) + √ dβC .Proof. The proof is the same as that of Lemma H.1.Lemma J.7. Deviation ≤ O max t ∥u -x t ∥ Σ -1 t dβ √ T log(T /δ) .Proof. The proof is the same as that of Lemma H.2.Lemma J.8.|I| ≤ d log 2 4T γ .Proof. Our proof is similar to Lemma B.12 in Lee et al. (2020) . Let {t 1 , • • • , t n+1 } be the rounds such that b t ̸ = 0. Define A A A i = i j=1 B B B tj . For any i > 1, since λ max (B B B ti -A A A i-1 ) > 0, there exists a vector y ∈ R d+1 such that y ⊤ B B B ti y > y ⊤ A A A i-1 y. Thus, y ⊤ A A A i y ≥ 2y ⊤ A A A i-1 y. Let z = A A A 1 2 i-1 y, we have z ⊤ A A A -1 2 i-1 A A A i A A A -1 2 i-1 z ≥ 2∥z∥ 2 2 . This implies λ max A A A -1 2 i-1 A A A i A A A -1 2 i-1 ≥ 2. Moreover, we have λ min A A A -1 2 i-1 A A A i A A A -1 2 i-1 ≥ 1 because A A A -1 2 i-1 A A A i A A A -1 2 i-1 = A A A -1 2 i-1 (A A A i-1 + B B B ti ) A A A -1 2 i-1 ⪰ I. Thus, det(A A Ai) det(A A Ai-1) = det A A A -1 2 i-1 A A A i A A A -1 2 i-1 ≥ 2.By induction, we have det (A A A n+1 ) ≥ 2 n det (A A A 1 ). We now give a upper bound for det(A A An+1) det(A A A1) . Define a a a = a 1 . By AM-GM inequality, we havedet A A A n+1 A A A -1 1 = det   n+1 j=1 B B B tj B B B -1 t1   ≤   1 d Tr   n+1 j=1 B B B tj B B B -1 t1     d .Notice that for any t, B B B t ⪰ I and Tr(B B B t ) = Tr(I) + Tr(Σ -1 t ) + ∥x t ∥ 2 Σ -1 t ≤ 2(d+1)γ . Thus, we can upper bound the last expression further by  1 d Tr   n+1 j=1 B B B tj     d ≤ 2(d + 1)(n + 1) dγ d ≤ 4T γ d .Overall, we have 2 n ≤ det(A A An+1) det(A A A1) ≤ (4T /γ) d , and thus n ≤ d log 2 (4T /γ).Lemma J.9.Bonus ≤ -α 8 maxt ∥u -x t ∥ Σ -1 t + O αd 2 log T . Proof. Let ρ = max t ∥u -x t ∥ Σ -1 t and t * = argmax t ∥u -x t ∥ Σ -1 t, We discuss two conditions:• If t * ∈ I, then ρ 2 ≤ τ ∈I ∥u -x t ∥ 2 Σ -1 τ . • If t * / ∈ I, then B B B t ⋆ ⪯ τ ∈I B B B τ . Let u u u ≜ u 1. This impliesρ 2 = ∥u -x t * ∥ 2 Σ -1 t * = ∥u u u∥ 2 B B B t ⋆ ≤ τ ∈I ∥u u u∥ 2 B B Bτ = τ ∈I ∥u -x τ ∥ 2 Σ -1 τ ,where we use the definitions of B B B t and u u u in the second and the last equality.Thus, max t ∥u -x t ∥ Σ -1 t ≤ τ ∈I ∥u -x τ ∥ Σ -1 τ . T t=1 ⟨x t -u, b t ⟩ = τ ∈I ⟨x τ -u, b τ ⟩ = α τ ∈I ⟨x τ -u, -∇F (x τ )⟩ ≤ - α γ ′ τ ∈I ∥u -x τ ∥ ∇ 2 F (xτ ) + 4αd|I| + 2α √ d|I| γ ′ (Lemma J.3 and F is d-self-concordant barrier) ≤ - α 2γ ′ τ ∈I ∥u -x τ ∥ Σ -1 τ + O(αd 2 log T ) (∇ 2 F (x τ ) = Σ -1 τ ⪰ 1 4 Σ -1 τ and Lemma J.8) ≤ - α 2γ ′ max t ∥u -x t ∥ Σ -1 t + O(αd 2 log T ).Lemma J.10.Penalty ≤ d log(T ) η .Proof. Since x ⋆ = min x∈A F (x) and π x ⋆ (u) ≤ 1 -1 T from Eq. ( 25). We have from Lemma J.4Penalty = F (u) -F (x ⋆ ) η ≤ d log(T ) η .Lemma J.11 (Lemma 17 in Zimmert and Lattimore (2022) ). Let F be the entropic barrier and∥w∥ ∇ 2 F (xt) -1 ≤ 1 16η , then max x∈A ⟨x -x t , w⟩ - 1 η D F (x, x t ) ≤ 2η∥w∥ 2 ∇ 2 F (xt) -1 .Lemma J.12. With probability at least 1 -δ,Stability ≤ O ηβ 2 dT + ηα 2 d 2 log T .Proof. Since F is a d-self-concordant barrier (Chewi, 2023) , we have∥b t ∥ ∇ 2 F (xt) -1 = α∥∇F (x t )∥ ∇ 2 F (xt) -1 ≤ α √ d.By Lemma J.2, we haveΣ -1 t ⪯ E a∼ pt [aa ⊤ ] -1 ⪯ 2Σ -1t , and thus d) , by Lemma J.11, we have Proof. Putting Lemma J.6, Lemma J.7, Lemma J.9, Lemma J.10, Lemma J.12 into Eq. ( 26) and Eq. ( 27), with η ≤ d) and γ = 1 T , we have with probability at least 1 -O(δ),EQUATIONStability ≤ 2η T t=1 ∥ θ t + b t ∥ 2 ∇ 2 F (xt) -1 ≤ 4η T t=1 ∥ θ t ∥ 2 ∇ 2 F (xt) -1 + 4η τ ∈I ∥b τ ∥ 2 ∇ 2 F (xτ ) -1 ≤ O ηβ 2 dT + ηα 2 d|I| ≤ O ηβ 2 dT + ηα 2 d 2 logEQUATIONReg ≤ max t ∥u -x t ∥ Σ -1 t O(d √ T + √ dC) - α 8 + O αd 2 + d η + ηα 2 d 2 + ηdT + √ T .By setting α 8 = Θ(d√ T + √ dC), we have Reg ≤ O d 3 √ T + d 5 2 C + d η + ηd 4 T + ηd 3 C 2 . Setting η = 1 160d √ T +32α √ d , we get Reg ≤ O d 3 √ T + d 5 2 C .We consider the same setting as Liu et al. (2023a) , but remove an assumption for it. Consider bandit learning with general reward function f 0 where for any action x t ∈ X ⊂ R d at round t, the learner get reward y t = f 0 (x t ) + η t where η t s are zero mean, σ-sub-Gaussian noise. We assume there exists a linear function θ ⊤ x that could approximate f 0 (x) in the following manner.Definition 3.sup x∈X θ ⊤ x -f 0 (x) f ⋆ 0 -f 0 (x) ≤ ρ where f ⋆ 0 = max x∈X f 0 (x) and 0 ≤ ρ < 1.The algorithm in Liu et al. (2023a) Proof. First, with probability of at least 1 -δ, for any ℓ and b ∈ A ℓ , we haveA ℓ+1 = a ∈ A ℓ : max b∈A ℓ ⟨ θ ℓ , b⟩ -⟨ θ ℓ , a⟩ ≤ 4d m ℓ log |A| δ + 1 2 ℓ m ℓ+1 ← 4m ℓ Define Gap(x) = f ⋆ 0 -f 0 (x)⟨b, θ ℓ -θ⟩ = b ⊤ G -1 ℓ a∈A ℓ u(a)ay(a) -b ⊤ θ = b ⊤ G -1 ℓ a∈A ℓ u(a)aa ⊤ η a + b ⊤ G -1 ℓ a∈A ℓ u(a)a∆(a) ≤ 4d m ℓ log |A| δ + b ⊤ G -1 ℓ a∈A ℓ u(a)a∆(a)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.For the last term, we haveb ⊤ G -1 ℓ a∈A ℓ u(a)a ≤ max c∈A ℓ ∆(c) • a∈A ℓ u(a) b ⊤ G -1 ℓ a∈A ℓ u(a)aa ⊤ Σ -1 ℓ b (Cauchy-Schwarz) = max c∈A ℓ ∆(c) • u∥b∥ 2 G -1 ℓ ≤ max c∈A ℓ ∆(c) • 2du m ℓ ≤ max c∈A ℓ ∆(c) • 2 √ d.Thus, for any b ∈ A ℓ ,⟨b, θ ℓ -θ⟩ ≤ 4d m ℓ log |A| δ + 2 √ d max a∈A ℓ ∆(a) = 4d m ℓ log |A| δ + 2 √ dρ max a∈A ℓ Gap(a) When ℓ = 1, since m 1 = ⌈256d log log d log |A| δ ⌉+16, we have 4d m1 log |A| δ ≤ 1 2 4 .Moreover, by trivial bound, max a∈A1 Gap(a) ≤ 2 and a ⋆ ∈ A 1 .We will jointly do two inductions. Assume for round ℓ, we have a ⋆ ∈ A ℓ and max a∈A ℓ Gap(a) ≤ 1 2 ℓ-2 . We first show a ⋆ ∈ A ℓ+1 . Thus, for anyb ∈ A ℓ , given ρ ≤ 1 64 √ d , since m ℓ = 4 ℓ-1 m 1 , we have ⟨b, θ ℓ -θ⟩ ≤ 4d m ℓ log |A| δ + 2 √ dρ max a∈A ℓ Gap(a) ≤ 1 2 ℓ-1 1 2 4 + 1 2 ℓ+3 = 1 2 ℓ+2From the induction hypothesis, let a ℓ = arg max b∈A ℓ ⟨ θ ℓ , b⟩we haveθ ⊤ ℓ a ℓ -θ ⊤ ℓ a ⋆ ≤ θ ⊤ a ℓ -θ ⊤ a ⋆ + θ ⊤ ℓ a ℓ -θ ⊤ a ℓ ≤ 1 2 ℓ+2 + θ ⊤ a ⋆ -θ ⊤ ℓ a ⋆ ≤ 1 2 ℓ+2 ≤ f 0 ( a ℓ ) -f 0 (a ⋆ ) ≤0 +|∆( a ℓ )| + 1 2 ℓ+1 ≤ ρGap( a ℓ ) + 1 2 ℓ+1 ≤ 1 2 ℓ For ℓ + 1, the remaining actions a ∈ A ℓ+1 satisfy max b∈A ℓ ⟨ θ ℓ , b⟩ -⟨ θ ℓ , a⟩ ≤ 4d m ℓ log |A| δ + 1 2 ℓ ≤ 1 2 ℓ+3 + 1 2 ℓ This implies a ⋆ ∈ A ℓ+1 . Moreover, since a ⋆ ∈ A ℓ , for a ∈ A ℓ+1 , we have Gap(a) = f ⋆ 0 -f 0 (a) = θ ⊤ a ⋆ -θ ⊤ a + |∆(a)| ≤ θ ⊤ ℓ a ⋆ -θ ⊤ ℓ a + ρGap(a) + (θ -θ ℓ ) ⊤ a ⋆ + ( θ ℓ -θ) ⊤ a ≤ θ ⊤ ℓ a ⋆ -θ ⊤ ℓ a + ρGap(a) + (θ -θ ℓ ) ⊤ a ⋆ + ( θ ℓ -θ) ⊤ a ≤ θ ⊤ ℓ a ⋆ -θ ⊤ ℓ a ℓ ≤0 given a ⋆ ∈A ℓ + θ ⊤ ℓ a ℓ -θ ⊤ ℓ a ≤ 1 2 ℓ+3 + 1 2 ℓ +ρGap(a) + 1 2 ℓ+1 Given ρ ≤ 1 64 √ d ≤ 1 64 , this implies Gap(a) ≤ 1 1 -ρ ( 1 2 ℓ + 1 2 ℓ+1 + 1 2 ℓ+3 ) ≤ 63 64 ( 1 2 ℓ + 1 2 ℓ+1 + 1 2 ℓ+3 ) ≤ 1 2 ℓ-1The above arguments show that as ℓ increases, max a∈A ℓ Gap(a) will shrink by 1 2 at every step. Since for a∈ A ℓ , Gap(a) ≤ 1 2 ℓ-1 = O 4d m ℓ log |A| δ Finally, given L = log(T ), we have Reg = L ℓ=1 a∈A ℓ u ℓ (a)Gap(a) ≤ L ℓ=1 m ℓ 4d m ℓ log |A| δ ≤ O dT log |A|/δWhen |A| ≥ T d , we can apply similar covering number arguments as in Appendix E, replacing A 1 with a 1 T -net of A. Combined with Theorem K.1, this yields the result in Theorem 6.2. Using the hard instance for ϵ-misspecified linear bandits setting in Lattimore et al. (2020) , we now show that ρ = Ω( 1 √ d ) for an algorithm to achieve sub-linear regret, proving the above algorithm is optimal in terms of ρ assumption.Theorem K.2. If ρ ≥ 8 log(3T ) d-1then there exists an instance that R T = Ω(ρT ).Proof. Using Theorem F.5 in Lattimore et al. (2020) , there exist a discrete time-invariant action space{a i ∈ R d } 3Ti=1 that satisfies these two conditions:1. ∥a i ∥ = 1 ∀i 2. ⟨a i , a j ⟩ ≤ 8 log(3T ) d-1 ∀i ̸ = j and let θ * = d-18 log(3T ) ϵa i * for some i * , and let misspecification at each round for all non-optimal arms be ϵ to make the true expected reward zero. Defining τ := max(t|i s ̸ = i * ∀s ≤ t), we haveE[R T ] ≥ d-1 8 log(3T ) ϵE[τ ].Since the observed rewards are independent of a i * before time τ , and i * is chosen randomly, we have E[τ ] ≥ min{T, 3T -1 2 }. So, E[R T ] ≥ ϵT d -1 8 log(3T )Finally, we have ρ ≥ In this section, we extend the results of Section 6 to the reinforcement learning setting. We consider episodic MDPs, denoted by a tuple M = (S, A, {P h } H h=1 , {r h } H h=1 , s 1 ) for S the set of states, A the set of actions, P h : S × A → △ S the transition kernel, r h : S × A → △ [0,1] the reward, and s 1 the starting state. We assume each episode starts in state s 1 , where the agent takes action a 1 , transitions to s 2 ∼ P 1 (• | s 1 , a 1 ) and receives reward r 1 ∼ r 1 (s 1 , a 1 ). This proceeds for H steps at which point the episode terminates and the process resets. We assume that H h=1 r h ∈ [0, 1] almost surely (note that the linear bandit setting with rewards in [-1,1] can be incorporated into this with a simple rescaling).We let π denote a policy, π h : S → △ S , a mapping from states to actions. We denote the value of a policy π on MDP M as V M,π 0:= E M,π [ H h=1 r h ].We assume access to some function class F ⊆ {S × A → R}. In the MDP setting, we define regret on MDP M as:Reg M T := T • sup π V M,π 0 - T t=1 V M,πt 0 .In the MDP setting, we consider the following notion of misspecification.Definition 4 (Misspecification). For our environment of interest M ⋆ , there exists some environment M 0 such that, for each f h+1 ∈ F, π, and (s, a, h), we have:E M ⋆ ,π [r h + f h+1 (s h+1 , a h+1 ) | s h = s, a h = a] -E M0,π [r h + f h+1 (s h+1 , a h+1 ) | s h = s, a h = a] ≤ ϵ mis h (s, a)and∃f h ∈ F s.t. f h (s, a) = E M0 [r h + max a ′ f h+1 (s h+1 , a ′ ) | s h = s, a h = a] for some ϵ mis h (s, a) > 0.We make the following assumption on gap-dependent misspecification.Assumption 4 (Gap-Dependent Misspecification). For any policy π, we haveE M ⋆ ,π H h=1 ϵ mis h (s h , a h ) ≤ ρ • ∆(π)for some ρ ≥ [0, 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 at episode t and step h as:ϵ t,h (s t h , a t h ) := sup g∈{S×A→[0,H]} |(T h g -T h b g)(s t h , a t h )|whereT h g(s, a) := E M [r h + max a ′ g(s h+1 , a ′ ) | s h = s, a h =a] denotes the Bellman operator, and T h b denotes the corrupted Bellman operator, i.e. T h b denotes the expected reward and next state under the corrupted reward and transition distribution. We denote the total corruption level asC := T t=1 H h=1 ϵ t,h (s t h , a t h ).Note that this definition of corruption encompasses both bandits and RL with function approximation. Now assume we have access to the following oracle. Assumption 5. We have access to a regret minimization algorithm which takes as input F and some C ′ and with probability at least 1 -δ has regret bounded on M 0 asEQUATIONif C ′ ≥ C, and by HT otherwise, for C as defined above and for (problem-dependent) constants C 1 (δ, T ), C 2 (δ, T ) which may scale at most logarithmically with T and 1 δ . Before stating our main reduction from corruption-robust to gap-dependent misspecification, we require the following assumption. Assumption 6. For any π, we have that there exists some f ∈ F such that for all (s, a, h), Q M0,π h (s, a) = f h (s, a).We then have the following result. Theorem L.1. Assume our environment satisfies Assumption 4. Then under Assumption 5 and Assumption 6, as long as ρC2( δ T ,T ) 1-ρ ≤ 1/2, with probability at least 1 -2δ we can achieve regret bounded as:Reg M ⋆ T ≤ 3 1 -ρ • C 1 ( δ T , T ) √ T + 2 1 -ρ • H 2T log(1/δ) + H .Proof of Theorem L.1. First, note that by Assumption 4, we can boundT t=1 E M ⋆ ,πt H h=1 ϵ mis h (s h , a h ) ≤ T t=1 ρ • ∆(π t ) ≤ ρ • Reg Twhere we abbreviate Reg T := Reg M ⋆ T . Furthermore, note that under Assumption 4 interacting with M ⋆ is equivalent to interacting with M 0 but where the rewards and transitions are corrupted up to level ϵ mis h (s, a) at (s, a, h).Relating Regret on M 0 to M ⋆ . Define the regret on M 0 asReg M0 T := T • sup π E M0,π H h=1 r h - T t=1 E M0,πt H h=1 r h .Under Assumption 4, we have thatE M ⋆ ,π ⋆ H h=1 ϵ mis h (s h , a h ) = 0. Lemma L.2 then implies that E M ⋆ ,π ⋆ H h=1 r h = E M0,π ⋆ H h=1 r hand soE M ⋆ ,π ⋆ H h=1 r h ≤ sup π E M0,π H h=1 r h .Furthermore, Lemma L.2 also impliesE M0,πt H h=1 r h -E M ⋆ ,πt H h=1 r h ≤ E M ⋆ ,πt H h=1 ϵ mis h (s h , a h ) .Putting these together we can boundReg T ≤ Reg M0 T + T t=1 E M ⋆ ,πt H h=1 ϵ mis h (s h , a h ) ≤ Reg M0 T + ρ • Reg T ,where the last inequality holds by Assumption 4. Rearranging this givesReg T ≤ 1 1 -ρ • Reg M0 T .Bounding the Regret. Consider running the algorithm of Assumption 5 on M ⋆ and assume we run with parameter C ′ ← β which we will choose shortly. From the above observation, this is equivalent to running on M 0 with corruption level ϵ mis h (s, a) at (s, a, h). Then by Assumption 5, with probability at least 1 -δ we have regret on M 0 bounded asReg M0 T ≤ C 1 (δ, T ) √ T + C 2 (δ, T )β if β ≥ T t=1 H h=1 ϵ mis h (s t h , a t h ), and by HT otherwise. Furthermore, by the above argument this then immediately implies a regret bound on Reg T .Let E 1,t denote the event that {β ≥t t ′ =1 H h=1 ϵ mis h (s t ′ h , a t ′ h )}. Let E 2 denote the event that for all t ≤ T , we have Reg t ≤ 1 1 -ρ • C 1 ( δ T , T ) √ t + C 2 ( δ T , T )β + T H 1 -ρ • I{E c 1,t },and note that by the above and under Assumption 5 we then have that E 2 occurs with probability at least 1 -δ. For simplicity, for the remainder of the proof we abbreviate C 1 := C 1 ( δ T , T ) and C 2 := C 2 ( δ T , T ). t ⋆ -1 = t ⋆ -1 t=1 ∆(π t ) > β ρ -H - H ρ 2T log 1/δ = 1 1 -ρ • C 1 √ T + C 2 β ≥ 1 1 -ρ • C 1 √ t ⋆ -1 + C 2 β .However, since by assumption t ⋆ -1 t=1 ρ∆(π t ) + H 2T log 1/δ ≤ β, on E 3 E 1,t ⋆ -1 holds so on E 2 ∩ E 3 we have thatReg t ⋆ -1 ≤ 1 1 -ρ • C 1 √ t ⋆ -1 + C 2 β .This contradicts the above. Therefore, on E 2 ∩ E 3 we must have that β ≥ ρ • Reg T + H 2T log 1/δ, so E 1,T holds on E 3 , and so on E 2 ∩ E 3 ,Reg T ≤ 1 1 -ρ • C 1 √ T + C 2 β .From our setting of β we can bound this as≤ 1 1 -ρ • C 1 √ T + 1 1 -ρ • C 2 • 1 - ρC 2 1 -ρ -1 • ρ 1 -ρ • C 1 √ T + H 2T log 1/δ + H .The result follows from some simplification.Lemma L.2. For MDPs M ⋆ , M 0 satisfying Definition 4, under Assumption 6 we haveV M0,π 0 -V M ⋆ ,π 0 ≤ E M ⋆ ,π H h=1ϵ mis h (s h , a h ) .Proof. Let r ′ denote the reward function on M 0 , and note that under Assumption 6 we have that there exists f ∈ F such that V M0,π h (s) = f h (s, π h (s)) for all π, s, h. Then Lemma E.15 of Dann et al. (2017) gives thatV M0,π 0 -V M ⋆ ,π 0 = E M ⋆ ,π H h=1 (r ′ h -r h ) + H h=1 E M0,π [V M0,π h (s h+1 ) | s h ] -E M ⋆ ,π [V M0,π h (s h+1 ) | s h ] .By Definition 4, we can bound this as≤ E M ⋆ ,π H h=1ϵ mis h (s h , a h ) .Proof of Corollary 6.2.1. First, note that under Assumption 3, we have that Assumption 4 holds for F the set of functions linear in ϕ, F = {ϕ(s, a) ⊤ w : w ∈ R d s.t. ϕ(s, a) ⊤ w ∈ [0, H], ∀s, a}, and ϵ mis h (s, a) of Assumption 4 set to Hϵ mis h (s, a) for ϵ mis h (s, a) of Assumption 3. To see this, let M 0 be the MDP with transitions ⟨ϕ(s, a), µ h (•)⟩, and note that this the immediately implies linear realizability on M 0 (and furthermore that Assumption 6 holds). Furthermore, since the total reward is at most H, it is easy to see that under Assumption 3, we can take ϵ mis h (s, a) ← Hϵ mis h (s, a). Next, note that Theorem 4. • 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 a 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 a 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 to 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 to 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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$.
strength_weakness: strength_weakness: **Weaknesses and Questions:**
1. 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.
2. At line 131, adversarial linear bandits are discussed. However, no problem definition of this problem is introduced before line 131.
3. 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.
4. Assumption 1 is not very reasonable.
questions: questions: See weaknesses.
limitations: limitations: N.A.
paper_summary: paper_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.

Not 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).
strength_weakness: strength_weakness: - (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. 

- Not clear what they tried to say on page 9
    - Why Theorem 6.2 shows that $\rho \leq \frac{1}{d}$ is not optimal?
    - 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. 

- No future works.
questions: questions: - Unclear points in the weakness section.

- It would be great if authors could explain why the gap-dependent misspecification assumption (Assumption 1) is necessary.

### Minor

- Theorem G.1 in line 296 - is it correct?

- Corollary 6.2.1 in line 209 - it seems like it is the result for the MDP...
limitations: limitations: The authors adequately addressed the limitations. It would be great if authors provide possible future works. 
There is no potential negative societal impact of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The algorithms are efficient regarding regret bound, but the computational complexity is not discussed.
- A conclusion section could be added.
questions: questions: What is the computational cost of the proposed algorithms?
limitations: limitations: Some limitations are discussed.

Comments: title: Response to Rebuttal
comment: Thanks for your positive feedback and the adjustment for the score. We will make efforts to reduce the confusion to the reader.
Thank you for the detailed response. I recommend focusing solely on the Corruption Measure (CM) Viewpoint, as the AA Viewpoint introduces some confusion. The concepts would be more clearly presented without it. This paper makes a valuable contribution to the understanding of corruption across various metrics and presents solid regret bounds. One potential weakness of this paper is that it focuses solely on a fixed action set. I will be increasing the score to 6. Good luck!
We thank the reviewer for the feedback. 

Notice that in our previous response, we do not assume the type of algorithm the learner uses (i.e., whether it's deterministic or randomized). Therefore, the points we make still hold even when the learner uses a randomized algorithm. 

Below we demonstrate that in the example you gave (i.e., the learner chooses $a_t=e_i$ with probability $1/2$), the corruption levels are the same in the two viewpoints. 

**AA viewpoint:** 

Adversary strategy:  If $a_t=e_i$ is observed, then set $\epsilon_t=c$. If $a_t\neq e_i$ is observed, then set $\epsilon_t=0$.  
Corruption level:  $C=\sum_{t=1}^T |\epsilon_t|=\sum_{t=1}^T |c|\mathbf{1}\\{a_t=e_i\\}$.  
Thus, $\mathbb{E}[C]=\mathbb{E}\big[\sum_{t=1}^T |c|\mathbf{1}\\{a_t=e_i\\}\big]=\frac{T|c|}{2}$, where in the last equality we use $\Pr\\{a_t=e_i\\}=1/2$. 

**CM viewpoint:**

Adversary strategy:  Set $\epsilon_t(e_i)=c$, and $\epsilon_t(e_j)=0$ for $j\neq i$ before seeing $a_t$.   
Corruption level:  $C=\sum_{t=1}^T |\epsilon_t(a_t)|=\sum_{t=1}^T |c|\mathbf{1}\\{a_t=e_i\\}$.   
Thus, $\mathbb{E}[C]=\mathbb{E}\big[\sum_{t=1}^T |c|\mathbf{1}\\{a_t=e_i\\}\big]=\frac{T|c|}{2}$, where in the last equality we use $\Pr\\{a_t=e_i\\}=1/2$. 

This shows that the corruption levels are the same in the two viewpoints. 

**Potential source of confusion:**  We point out that in the CM viewpoint, although there could be ``non-zero corruption function'' in every round (e.g.., $\epsilon_t(e_i)=c$ for all $t$ in our previous example),  the corruption measure we consider is $C = \sum_{t=1}^T |\epsilon_t(a_t)|$, which only depends on $a_t$. Thus, even though $\epsilon_t(e_i) = c$ for every round $t$, such corruption only contributes to $C$ when $a_t = e_i$, and it will not contribute to $C$ when $a_t\neq e_i$. This makes it equivalent to the strong AA adversary whose corruption adapts to the choice of the learner.  

We guess that the reviewer might be thinking about another corruption measure $C_\infty=\sum_{t=1}^T \max_a |\epsilon_t(a)|$, which accounts for the corruption for *every* (no matter chosen or unchosen) action.  However, this is not what we want to show equivalence for with the strong AA adversary.
Thank you for your response. 

**Regarding the first concern,** I disagree with your statement. I believe the second point you made is incorrect. For example, with a probability of 1/2, the algorithm selects $a_{t} = e_i$. Assuming both AA and CM have the same influence on the algorithm, and CM has a corruption level $C$, then, since AA only corrupts the algorithm with a probability of 1/2, the corruption level of AA would be $C/2$. I look forward to your reply.
Thanks for your response, and I have no further questions.
Thank you for your details. Now I understand the points of the authors. I will keep my score as it is.
We thank the reviewer for the time and effort spent reviewing our paper. As the discussion phase is about to end, we would like to make sure our responses have sufficiently addressed your concerns. We look forward to your feedback.
We thank the reviewer for the time and effort spent reviewing our paper. As the discussion phase is about to end, we would like to make sure our responses have sufficiently addressed your concerns. We look forward to your feedback.
We thank the reviewer for the time and effort spent reviewing our paper. As the discussion phase is about to end, we would like to make sure our responses have sufficiently addressed your concerns. We look forward to your feedback.
Thank you for the comments! We would like to elaborate more as follows.

**Regarding the first concern:** 

Our AA and CM viewpoints are exactly what you describe. However, we would like to draw the reviewer's attention to the definition of the corruption measure in the CM viewpoint: $C=\sum_{t=1}^T |\epsilon_t(a_t)|$. This definition only accounts for the corruption for the "chosen action" $a_t$, but not that for other actions $a\neq a_t$. 

How does this property allow us to simulate a strong adversary in the AA viewpoint? Below, we illustrate it through a concrete example as in your response (below, we use "he" for the adversary and "she" for the learner). Consider a $d$-dimensional linear bandit with the action set being the canonical basis $e_{1:d}$. From the AA viewpoint, suppose the adversary wants to corrupt the $i$-th dimension of $\theta^*$, and his strategy can be described as the following: 

*If $a_t=e_i$ is observed, then set $\epsilon_t=c$*;

*If $a_t\neq e_i$ is observed, then set $\epsilon_t=0$*.

Clearly, this is a strong adversary in the AA viewpoint since the adversary decides whether he wants to corrupt $a_t$, and to what extent he wants to corrupt it, after observing the chosen action $a_t$. 


From the CM viewpoint, the equivalent adversary would specify the following "corruption function" $\epsilon_t(\cdot)$ *before* seeing $a_t$:

*$\epsilon_t(e_i)=c$, and $\epsilon_t(e_j)=0$ for $j\neq i$*.

After the learner chooses $a_t$, the learner experiences a corruption of $\epsilon_t(a_t)$. 

We clarify two points: 

1. The learner has exactly the same observations in the two viewpoints: if she chooses $a_t=e_i$, then she suffers a corruption of $c$; if she chooses $a_t\neq e_i$, then she suffers no corruption. 

2. The total corruption $C$ is the same in the two viewpoints: In the AA viewpoint, $C=\sum_{t=1}^T |\epsilon_t|=\sum_{t=1}^T |c|\mathbf{1}\\{a_t=e_i\\}$. In the CM viewpoint, $C=\sum_{t=1}^T |\epsilon_t(a_t)|=\sum_{t=1}^T |c|\mathbf{1}\\{a_t=e_i\\}$. 

One key observation is that: in the CM viewpoint, even though the corruption function might be a non-zero function (i.e., $\epsilon_t(a)\neq 0$ for some $a$), the amount of corruption counted towards $C=\sum_{t=1}^T |\epsilon_t(a_t)|$ is zero as long as $\epsilon_t(a_t)=0$. In other words, it is possible that $\epsilon_t(a)=0$ and $\epsilon_t(b)\neq 0$ for some arms $a,b$, which could simulate the AA strong adversary who decides NOT TO corrupt after observing $a_t=a$, but decides TO corrupt after observing $a_t=b$.

This might address the reviewer's concern, "*If $a_t$ is not known, the only option for the adversary is
to add corruption to each arm and hope the algorithm picks the arm that has
a high influence on the dimension it wants to corrupt.*" From the discussion above, we know that a CM adversary can simply do the following: set high corruption for the actions with high influence on the dimension, and set low/zero corruption for the actions with low influence on the dimension. Then, after $a_t$ is decided by the learner, the corruption level $|\epsilon_t(a_t)|$ will naturally adapt to the choice of $a_t$, i.e., the corruption will be high if $a_t$ has high influence on the dimension, and will be low/zero if $a_t$ has low influence on the dimension. 

A mathematical conversion between the two viewpoints is as follows. Assume that the strategy of the AA strong adversary can be decribed as a function $\epsilon_t = f(h_{t-1}, a_t)$, where $h_{t-1}$ is the history up to time $t-1$ and $a_t$ is the chosen action at time $t$. Then in the CM viewpoint, the "corruption function" would be defined as $\epsilon_t(a) = f(h_{t-1}, a)$ for every $a$. Notice that the function $\epsilon_t(\cdot)$ depends only on the history up to time $t-1$. 


**Regarding the second concern:** 

If the corruption is always zero, our formulation (Line 74 - 79) is the same as the standard adversarial linear bandit setting formulated in Section 27 of Lattimore and Szepesvari (2020), where the linear reward vector $\theta_t$ changes over time. The only extension we make is that we consider additional reward corruption. We can refer to it as "adversarial linear bandits with corruption" to make things even clearer. 

(Lattimore and Szepesvari, 2020) Bandit Algorithms. 

**Regarding the third concern:** 

 Thanks for your suggestions. We will add the bound $\sqrt{dT \log k}$ to our Theorem 4.1. We will also discuss more about our bounds compared with previous works.
Thanks for your rebuttal. 
---

Regarding A1: I disagree. In the AA perspective, the adversary can first observe the chosen arm $A_t$ and then decide whether $A_t$ is the arm it wants to corrupt or not. For instance, if the adversary aims to corrupt a specific dimension of $\theta^*$, it can choose to do so to maximize its profit, given that it knows $A_t$ beforehand. If $A_t$ is not known, the only option for the adversary is to add corruption to each arm and hope the algorithm picks the arm that has a high influence on the dimension it wants to corrupt.

---

Regarding A2, the term "adversarial linear bandits" in the bandit literature refers to a different setting. Please consider changing the name of "adversarial linear bandits".

---

Regarding A4, I believe that $\sqrt{dT \log k}$ is significantly better than $d\sqrt{T}$ regret. It might be beneficial to present the $\sqrt{dT \log k}$ results in your main theorem and clearly discuss the differences in settings and results compared with previous work.