Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
Authors: Haolin Liu
Chen-Yu Wei
Julian Zimmert
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial linear contextual bandits
log-determinant barrier

Abstract: We consider the adversarial linear contextual bandit problem, 
where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from a fixed distribution. Existing methods for this problem either require access to a simulator to generate free i.i.d. contexts, achieve a sub-optimal regret no better than $\tilde{\mathcal{O}}(T^{\frac{5}{6}})$, or are computationally inefficient. 
We greatly improve these results by achieving a regret of $\tilde{\mathcal{O}}(\sqrt{T})$ without a simulator, while maintaining computational efficiency when the action set in each round is small. 
In the special case of sleeping bandits with adversarial loss and stochastic arm availability, our result answers affirmatively the open question by [SGV20]  on whether there exists a polynomial-time algorithm with  $poly(d)\sqrt{T}$ regret. Our approach naturally handles the case where the loss is linear up to an additive misspecification error, and our regret shows near-optimal dependence on the magnitude of the error.

Bypassing the Simulator:
Near-Optimal Adversarial Linear Contextual Bandits
Haolin Liu"
Chen-Yu Wei
Julian Zimmert" Google Research
University of Virginia ers@zhevirgimia.
University of Virginia chenyu.. wwievirginaa edu
zimmert@google..o
Abstract
We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) drawn from fixed distribution. Existing methods for this problem either require access to a simulator to generate free i.i.. contexts, achieve sub-optimal regret no better than (TT%)), or are computationally inefficient. We greatly improve these results by achieving regret of ((VT) without a simulator, while maintaining computational efficiency when the action set in each round is small. In the special case of slceping bandits with adversarial loss and stochastic arm availability, result answers affirmatively the open question by Saha et al. [2020] on whether there exists polynomial-time algorithm with poly(d) VT) regret. Our approach naturally handles the where the loss is linear up additive misspecification error, and our regret shows mear-optimal dependence on the magnitude the error.
Introduction
Contextual bandit is a widely used model for sequential decision making. The interaction between the learner and the environment proceeds rounds: each round, the environment provides context; based on it, the learner chooses an action and receive reward. The goal is to maximize the total reward across multiple rounds. This model has found extensive applications fields such as medical treatment [Tewari and Murphy, 2017], personalized recommendations [Beygelzimer et al., 2011], and online advertising [Chu et al., 2011].
Algorithms for contextual bandits with provable guarantees have been developed under various assumptions. In the linear regime, the most extensively studied model is the stochastic linear contextual bandit, in which the context can be arbitrarily distributed in each round, while the reward determined by fixed linear function of the context-action pair. Near-optimal algorithms for this setting have been established in, e.g., [Chu et al., 2011, Abbasi-Yadken et al., 2011, 1, Li et al., 2019, Foster al., 2020]. Another model, which is the focus of this paper, is the adversarial linear contextual bandit, in which the context is drawn from a fixed distribution, while the reward is determined by a time-varying linear function of the context-action pair. A computationally efficient algorithm for this setting is first proposed by Neu and Olkhovskaya [2020]. However, existing research for this setting still faces challenges in achieving near-optimal regret and sample complexity when the context distribution is unknown.
"The authors are listed in alphabctical order.
1 Thii was done when Chen- Wei was MIT Institute for Data, Systems, Society. Apparently, the stochastic and adversarial linear contextual bandits defined here are incomparable, and their do not fully capture their underlying assumptions. However, these the terms commonly used in the literature (c.g., [Abaasi- Yadkori al., 201 I, Neu and Olkhovskaya, 2020]).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The algorithm by Neu and Olkhovskaya [2020] requires the learner to have knowledge on the context distribution, and access to an exploratory policy that induces feature covariance matrix with a smallest eigenvalue at least X. Under these assumptions, their algorithm provides regret guarantee of ([V/loog( A where d is the feature dimension, |AA] is the maximum size of the action set, and T is the number of rounds. These assumptions are relaxed in the work of Luo et al. [2021], who studied more general linear MDP setting. When specialized to linear contextual bandits, Luo et al. [2021] only requires access to a simulator from which the learner can draw free i.idd contexts. Their algorithm achieves a ((d ((dlogg() log((_A)) (a)) regret. The regret is further improved to the near-optimal one Olydlog([AI)T) by Dai et al. [2023] through refined loss estimator construction.
All results that attain (374)) or (VVT) regret bound discussed above rely on access to the simulator. In their algorithms, the number of calls to the simulator significantly exceeds the number of interac- tions between the environment and the learner, but this is concealed from the regret bound. Therefore, their regret bounds do not accurately reflect the sample complexity of their algorithms. Another set of results for linear MDPs [Luo al., 2021, Dai al., 2023, Sherman et al., 2023, Kong et al., 2023] also consider the simulator-fee free scenario, essentially using interactions with the environment to fulfill the original purpose of the simulator. When applying their techniques to linear contextual bandits, their algorithms only achieve a regret bound of ((7% at best (see detailed analysis and comparison in Appendix G).
Our result significantly improves the previous ones: without simulators, we develop an algorithm that ensures a regret bound of order (T) and it is computationally efficient as long as the size of the action set is small in each round (similar to all previous work). Unlike previous algorithms which always collect new contexts (through simulators or interactions with the environment) to estimate the feature covariance matrix, we leverage the context samples the learner received in the past to do this. Although natural, establishing a near-tight regret requires highly efficient use of context samples, necessitating novel way to construct the estimator of feature covariance matrix and tighter concentration bound for it. Additionally, to address the potentially large magnitude and the bias of the loss estimator, we turn to the of log-determinant (logdet) barrier in the follow-the- regularized-leader (FTRL) framework. Logdet accommodates larger loss estimators and induces a larger bonus term to cancel the bias of the loss estimator, both of which are crucial for our result.
Our setting subsumes sleeping bandits with stochastic arm availability [Kanade et al., 2009, Saha et al., 2020] and combinatorial semi-bandin with stochastic action sets [Neu and Valko, 2014]. Our result answers affirmatively the main open question left by Saha et al. [2020] on whether there exists a polynomial-tine -time algorithm with poly(d)v7 regret for sleeping bandits with adversarial loss and stochastic availability.
As side result, give a computationally inefficient algorithm that achieves improved ((dVT) regret without a simulator. While this is a direct extension from the EXP4 algorithm [Auer et al., 2002], such a result has not been established to our knowledge, so we include it for completeness.
1.1 Related work
We review the literature of various contextual bandit problems, classifying them based on the nature of the context and the reward function, specifically whether they are stochastic/fixed or adversarial.
Contextual bandits with i.i.d. contexts and fixed reward functions (S-S) Significant progress has been made in contextual bandits with i.i.d. contexts and fixed reward functions, under general reward function classes or policy classes [Langford and Zhang, 2007, Dudik et al., 2011, Agarwal et al., 2012, 2014, Simchi-Levi and Xu, 2022, Xu and Zeevi, 2020]. In the work by Dudik al. [2011], Agarwal et al. [2012, 2014], the algorithms also use previously collected contexts to estimate the inverse probability of selecting actions under the current policy. However, these results only obtain regret bounds that polynomially depend on the number of actions. Furthermore, these results rely on having fixed reward function, making their techniques not directly applicable to our case.
"The linear contextual bandit problem formulation in Neu and Olkhovskaya [2020] is different from ours. However, it can he reduced to our setting with dimension d], where [A] is the maximum number of actions in each round. The Õ Vl bound reported here is obtained by adopting their techniques to our setting.

---

Table 1: Related works in the "S-A" calegory. CB stands for contextual bandits and SB stands for semi-bandils. The relations among setlings ure as follows: Sleeping Bandit C Contextual SB C Linear CB, Linear CB C Linear MDP, and Linear CB C General CB. The table compares our results with the Pareto frontier of the literature. For algorithms dealing more general settings, have carefully translated their techniques to Linear CB and reported the resulting hounds. 7n denotes the feature covariance matrix induced hy policy m. |A| and [T] are sizes of the action set and the policy set.
Target Setting
Algorithm
Regret
Simulator
Computation
Assumption
General CB
Syrgkanis et al. [2016b]
(log [T] ) V3 (
poly([A), log M1 T)
ERM Oracle
Dai et al. [2023]
vdll log [AA
poly(IA), d')
Linear MDP
Dai et al. [2023]
d(log (AI) //
poly(IA),, d,
Sherman et al. [2023]
Kong et al. [2023]
(d"T4)Vo + poly (+)
T
3x, Fx 2 AT
Algorithm 1
d'vT
poly([AA), d, 7) T
Linear CB
Algorithm 2
d/T
Contextual SB
Neu and Valko [2014]
(dT
poly(d, poly(d, 7) (IA) S d)
Sleeping Bandit
Saha ct al. [2020)
V2²T
Contextual bandits with veresaaia contexts and fixed reward functions (A-S) In this category, the most well-known results are in the linear setting [Chu et al., 2011, Abbasi- Yadkori et al., 201 1, Zhao et al., 2023]. Besides the linear case, previous work has investigated specific reward function classes [Russo and Van Roy, 2013, Li et al., 2022, Foster et al., 2018J. Recently, Foster and Rakhlin [2020] introduced general approach to deal with general function classes with a finite number of actions, which has since been improved extended by Foster and Krishnamurthy [2021]. Foster et al. [2021], Zhang [2022]. This category of problems is not directly comparable to the setting studied in this paper, but both capture a certain degree of non-stationarity of the environment.
Contextual bandits with i.i.d. contexts and adversarial reward functions (S-A) This is the category which our work falls into. Several oracle efficient algorithms that require simulators have been proposed for general policy classes [Rakhlin and Sridharan, 2016, Syrgkanis et al., 2016b]. The oracle they use (i.c., the empirical risk minimization, or ERM oracle), however, is not generally implementable in an efficient manner. For the linear case, the first computationally efficient algorithm by Neu and Olkhovskaya [2020], under the assumption that the context distribution is known. This is followed by Olkhovskaya et al. [2023] to obtain refined data-dependent bounds. A series of works [Neu and Olkhovskaya, 2021, Luo et al., 2021, Dai al., 2023, Sherman al., 2023] apply similar techniques to linear MDPs, but when specialized to linear contextual bandits, they all assume known context distribution, or access to a simulator, or only achieves a regret no better than 5(T%)s). The work of Kong et al. [2023] also studies linear MDPs; when specialized to contextual bandits, they obtain a regret bound of O + (oly(+) ()) without simulator but with a computationally inefficient algorithm and undesired inverse dependence on the smallest eigenvalue of the covariance matrix. Related but simpler settings have also been studied. The sleeping bandit problem with stochastic arm availability and adversarial reward [Kleinberg al.. 2010, Kanade et al., 2009, Saha et al., 2020] is special case of our problem where the context is always a subset of standard unit vectors. Another special case is the combinatorial semi-bandit problem with stochastic action sets and adversarial reward [Neu and Valko, 2014). While these are special cases, the regret bounds in these works are all worse than (d) Therefore, our result also improves upon theirs. 5
Contextual bandits with adversarial contexts and adversarial reward functions (A-A) When both contexts and reward functions are adversarial, there are computational [Kanade and Steinke, 2014] and oracle-call [Hazan and Koren, 2016] lower bounds showing that no sublinear regret is achievable unless the computational cost scales polynomially with the size of the policy set, Even for the linear case, Neu and Olkhovskaya [2020] argued that the problem is at least hard as online learning a one- -ie-imensional threshold function, for which sublinear regret is impossible. For this
For combinatorial semi- bandit problems, our algorithm is not as computationally efficient as Neu and Valko [2014], which can handle exponentially large action sets.
3

---

challenging category, besides using the inefficient EXP4 algorithm, previous work makes stronger assumptions on the contexts [Syrgkanis al., 2016a] or resorts alternative benchmarks such as dynamic regret [Luo et al., 2018, Chen et al., 2019] and approximate regret [Emamjomeh-77ddeh al., 2021].
Lifting and exploration bonus for high-probability adversarial linear bandits Our technique is related to those obtaining proh-prbbbbilityy bounds for linear bandits. Early development in this line of research only achieves computational efficiency when the action set size is small [Bartlett et al., 2008] or only applies to special action sets such two-norm balls [Abernethy and Rakhlin, 2009]. Recently, near-optimal bigh-probability bounds for general convex action sets have been obtained by lifting the problem higher dimensional one, which allows for computationally efficient way to impose bonuses [Lee et al., 2020, Zimmert and Lattimore, 2022]. The lifting and the bonus ideas we use inspired by them, though for different purposes. However, due the extra difficulty arising in the contextual case, currently we only obtain a computationally efficient algorithm when the action set size is small.
1.2 Computational Complexity
Our main algorithm is based on log-determinant barrier optimization similar to Foster et al. [2020], Zimmert and Lattimore [2022]. Computing its action distribution is closely related to computing the D-optimal experimental design [Khachiyan and Todd, 1990]. Per step, this is shown to require O(AA, poly(d)) computational and (Iog([AA.] poly(d)) memory complexity [Foster et al., 2020, Proposition 1], where |AAel the action set size round t. The computational bottleneck comes from (approximately) maximizing a quadratic function over the action set. It is an open question whether linear optimization oracles or other type of oracles can lead to efficient implementation of our algorithm for continuous action sets.
In the literature, there are few linear context bandit algorithms that provably avoid |.A| computation per round. The LinUCB algorithm [Chu et al., 201 1, Abbasi- Yadkori et al., 2011] suffers from the same quadratic function maximization issue, and therefore is computationally comparable to our algorithm. The SquareCB.La Lin algorithm by Foster et al. [2020] is based on the same log-determinant barrier optimization. Another recent algorithm by Zhang [2022] only admits an efficient implementation for continuous action sets in the Bayesian setting but not in the frequentist setting (though they provided an efficient heuristic implementation in their experiments). The Thompson sampling algorithm by Agrawal and Goyal [2013], which has efficient implementation, also relies on well-specified Gaussian prior. The only work that we know can avoids |A computation in the frequentist setting is Zhu et al. [2022], but their technique is only known to handle the A-S setting.
2 Preliminaries
We study the adversarial linear contextual bandit problem where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from fixed distribution. The learner and the environment interact in the following way. Let TB& be the 1.2-norm unit ball in Rd
For t = 1, ,,
1. The environment decides an adversarial loss vector yr Bg, and generates random action set (i.e., context) A, C BB& from a fixed distribution D independent from anything else.
2. The learner observes A,, and (randomly) chooses action d, e Ar.
3. The learner receives the loss 4 E [[1, 1] with [[4]] = (ac. st).
A policy is a mapping which, given any action set A C Rd, maps it to an element in the convex hull of A. We use π (AA) to refer to the element that it maps A to. The learner's regret with respect to policy π is defined as the expected performance difference between the learner and policy n:
T
T
Reg(T)) =
Σ
(aes v1)
(TT (A:), m1)

---

where the expectation is taken over all randomness from the environment (yr and Ar) and from the learner (a,). The pseudo-regrer (or just regret) is defined as Reg max, Reg(T)) where the maximization is taken over all possible policies.
Notations For any matrix A, use (A) and Xmin (A) to denote the maximum and minimum cigenvalues of A, respectively. We use Tr(A) to denote the trace of matrix A. For any action set A, let (AA) be the space probability measures on A. Let J, - (AA,, Os Vs S t) be the r-algebra at round t. Define [ [[-] Given a differentiable convex function F R - R U {oo), the Bregman divergence with respect to F' is defined as Dy(z, y) = F(x) F(y) - (VF(y), x y)- Given positive semi-definite (PSD) matrix A, for any vector x. define the norm generated by A as ||=]|a Vx Ar. For any context A gd and p E A(A), define μτр)
Eapp[a] and
Cov(p) Ex~pl(a ((p)) T. For any a, define the lifted action a = (a, 1) and the lifted
aaa a Cov(p) + #(p))(p)) m(p) Eavp a
covariance matrix (pv(p) Eap Iaa ]
1
p(p)
1
We use bold matrices to denote matrices in the lifted space (e.g., in Algorithm and Definition 1).
3 gollow-the-Regularizee----
with the Log-Determinatt Barrier
In this section, present main algorithm, Algorithm 1. This algorithm be viewed as instantiating an individual Bellow-The-Regulaiizee---- (Line 2), with all FTRLs sharing the same loss vectors. This perspective has been taken by previous works Neu and Olkhovskaya [2020], Olkhovskaya et al. [2023] and simplifies the understanding of the problem. The rationale comes from the following caleulation due to Neu and Olkhovskaya [2020]: for any policy that may depend on F;-1,
(FTRL) algorithm on each action set
E. [(TT (At),, 3131 = EA. [,, ((T( 36) F(-1ll = EA, [. ((T(()) ye [i-1]] E, (<))))),, y0l
where Au is a sample drawn from D independent of all interaction history. This allows us to calculate the regret as
T Σ (T. ((44))=((A))..))) x(Ac). 31)
T Σ (me(A))) - TTA)), ve)
E
E
(1)
where is the policy used by the learner at time f. Note that this view does not require the learner to simultancously "run" an algorithm on every action set since the learner only needs to calculate the policy on A whenever A, = A. In the regret analysis, in view of Eq. (1), it suffices to consider a single fixed action set Ao drawn from D and bound the regret on it, even though the learner may never execute the policy on it. This An is called "ghost sample" in Neu and Olkhovskaya [2020].
3.1 The lifting idea and the execution of Algorithm
Our algorithm is built on the logdet-FTRI. algorithh developed by Zimmert and Lattimore [2022] for high-probabiite adversarial linear bandits, which lifts the original d-dimensional problem over the feature space to a (d + 1) x (d 1) one over the covariance matrix space, with the regularizer being the negative log-determinant function. In our case, we instantiate an individual logdet-FTRL on each action set. The motivation behind Zimmert and Lattimore [2022] lift the problem to the space of covariance matrix is that it casts the problem to one in the positive orthant, which allows for an easier way to construct the bonus term that crucial to compensate the variance of the losses, enabling a bigh-probability bound in their case. In our case, we use the same technique to introduce the bonus term, but the goal is to compensate the bias resulting from the estimation error in the covariance matrix (see Section 3.4). This bias only appears in our contextual case but not in the linear bandit problem originally considered in Zimmert and Lattimore [2022].
As argued previously, we can focus on the learning problem over a fixed action set A, and our algorithm operates in the lifted space of covariance matrices H {Cov(p) P A(A)) C
(( For this space, we define the lifted loss " = 1 0
E R(d+1 (d++1) so
that (Cov(p),n) = Ea-pla TaT yol (u(p), vi) and thus the loss value in the lifted space (i.c.. (Cov(p), 7 is the same as that in the original space (i.c., (n()).
5

---

Algorithm Logdet-FTRL for linear contextual bandits
Definitions: F(H) log det (H), 1p= 64d//'' at 3r 100(d+1) log
8-1
for ( 1.2....d .o
For all A, define H.A argmin
E (H, a, 1.,5) F(H)
MEHA
n
For all A, define pi (A)) such that H.* Cov(pg!)
Receive As and sample at ~ p
Observe & [1 with B(G,] ai V/1 and construct ūı Ex (a. -be)e,, where
1-1 B Ba
tt
A [a],
He
E Bapp [(a st)(aa [] E, H. 3.1.
T=1
0 5
Define H. i-1 Ersl H.A. and E = H. + Bil and 91
(Ift 1, define _ and E-1 as zeros).
In each round I, the FTRL on A outputs lifted covariance matrix H²A E H-A that corresponds to probability distribution pt ((A) such that Cov(p(") H (Line and Line 3). Upon receiving
A, the learner samples an action from pf and the agent constructs the loss estimator Òr (Line 5).
Zhh
Similarly to the construction of "it define the lifted loss estimator 5t
which
2.0
0
makes (Cov(p), 91) = Eu-pla" 0rl = (m(P), Dt). The lifted loss estimator, along with the bonus term Ea -1 then fed the FTRL on all A's. The purpose of the bonus term will be clear in Section 3.4.
the following notation in addition to those defined in Algorithm 1. ((t)- T, H: (A-D[HA)) H, EAAD [..) Let p (AA) be the action distribution used by the benchmark policy on A, and define a Europ [a], u EA-D(uA], U Ea-p, Iaa U EA-D (U Notice that the x and A defined here is equivalent to the (e()) and ((A) in Eq. (1), respectively.
In the rest of this section, Definition 1. Define x.A = E an [a], EAND(EA], H.A = Ba-py ((a =t) -
3.2 The construction of loss estimators and feature covariance matrix estimators
Our goal is make 인t in Line 5 an estimator of y, with controllable bias and variance. If the context distribution known (as Neu and Olkhovskaya [2020]), then a standard unbiased estimator of ye is
Σ agle,
where Σ = EANDE [aa" ']
(2)
To see its unbiasedness, notice that Efa,e EANDEa-pp (aa yr] and thus Elg.] y:- This dc- however, can have variance that inversely related the smallest eigenvalue of the covariance matrix E., which can be unbounded in the worst case. This is the main reason why Neu and Olkhovskaya [2020] does not achieve the optimal bound, and requires the ilaasvariance-tradeoo techniques Dai al. [2023] to close the gap. When the context distribution unknown but the learner has access to a simulator [Luo al., 2021, Dai et al., 2023, Sherman al., 2023, Kong et al., 2023], the learner accuracy without interacting with the environment, making the problem close to the case known context distribution.
draw free contexts to estimate the covariance matrix Σ, up to very high
Challenges arise when the learner has no knowledge about the context distribution and there is no simulator. In this case, there are two natural ways to estimate the covariance matrix under the current policy. One is to draw new samples from the environment, treating the environment like a simulator. This approach is essentially taken by all previous work studying linear models in the "S-A" category. However, this is very expensive, and it causes the simulator-cquipper bound vT in Dai et al. [2023]

---

to deteriorate to the simulator-fiee free bound 7 at best (see Appendix G for details). The other is to use the contexts received in time t to estimate the covariance matrix under the policy at time This demands very high efficiency in reusing the contexts samples, and existing ways of constructing the covariance matrix and the accompanied analysis by Dai et al. [2023], Sherman et al. [2023] are insufficient to achieve the near-optimal bound even with context reuse. This necessitates our tighter construction of the covariance matrix estimator and tighter concentration bounds for it.
Our construction of the loss estimator (Line 5) is
U+ E (a+ ft)ee
where Σ, E ALD. B Baupy (0)-sa)(a-- = 3.T
where D. = Uniform{ A2,
A--1), A, = BB Bempy [a], and B, - O(d/))) Comparing Eq. (3) with Eq. (2), we see that besides using the empirical context distribution D in place of the ground truth D and adding a small term B,I to control the smallest eigenvalue of the covariance matrix, we also centralize the features by ct. an estimation of the mean features under the current policy. The centralization is important in making the bias Br Or appear in nice form that can be compensated by a bonus term. The estimator might seem problematic on first sight, because pf is strongly dependent on D., which rules out canonical concentration bounds. We circumvent this issue by leveraging the special structure of pt in Algorithm 1, which allows for a union bound over a sufficient covering of all potential policies (Appendix C.3). The analysis on the bias of this loss estimator is also non-standard, which is the key to achieve the near-optimal bound. In the next two subsections, we explain how to bound the bias of this loss estimator (Section 3.3), and how the bonus term can be used to compensate the bias (Section 3.4).
3.3 The bias of the loss estimator
Since the true loss vector is yt and we use the loss estimator de in the update, there is bias term emerging the regret bound at time t:
Eg (arto An, yr - 0c) = Ex Krre - u, Vt - Dc)l = Ee (xx - -u)" u)² (1- E - 22)a, Vi
where definitions of wz u Wi, u can be found in Definition and use the definition of ÿr in Eq. (3) in the last equality. Now taking expectation over Ar and az conditioned on Ft we can further bound the expectation in the last expression by
(It 1- w) (I- H.) y (Ire TT, (xt - Gt) a yt
S || - uواا 11(s, H1)vells + |0, ulls, 1 11,, Ze Rells,
-ull,lls,
(4)
(see Definition 1 for the definition of H.). The two terms I|(E, Ho)yolls. and || Rells, in Eq. (4) are related to the error between the empirical context distribution D, (I. 1- and the true distribution D. We handle them through novel analysis and bound both of them by O ( /t). See Lemma 13, Lemma 14, Lemma 18, and Lemma 19 for details. The techniques we use in these lemmas surpass those in Dai et al. [2023], Sherman et al. [2023]. As a comparison, a similar term as || (E,- H.)yells;- is also presented in Eq. (16) of Dai et al. [2023) and
Lemma B.5 of Sherman et al. [2023] when bounding the bias. While their analysis uses off-the-shelf matrix concentration incqualities, our analysis expands this expression by its definition, and applies concentration inequalities for scalars on individual entries. Overall, our analysis is more tailored for this specific expression. Previous works ensure that this term can be bounded by O after collecting O new samples (Lemma 5.1 of Dai et al. [2023] and Lemma B.1 of Sherman et al. [2023]), we are able to bound it by (1/vV)) only using samples that the learner received up to time This essentially improves their 0(8 sample complexity bound to ((8-1). See Appendix G for detailed comparison with Dai et al. [2023] and Sherman et al. [2023].
Now we have bounded the regret due to bias of jt by the order of / d /t|/ - w|ls, The next problem is how to mitigate this term. This is also problem in previous work [Luo et al., 2021, Dai et al., 2023, Sherman et al., 2023], and has become clear that this can be handled by incorporating bonus in the algorithm.
7

---

3.4 The bonus term
To handle bias term in the form of || ulls, we resort the idea of bonus. To illustrate this, suppose that instead of feeding de to the FTRLS, we feed Út by for some by. Then this would give us regret bound of the following form:
T
T
Reg- E
Fe
D1
bi)
+ E
u, 3/t
Dt)
+ E
Σ
bu)
d3
x O(d
E
ullss
+
Σ
[x) u1 be)
(5)
where we assume that FTRL can give us (T) bound for the loss sequence Or - by Our hope here is to design b, such that (æt u, by) provides negative term that can be used to cancel the bias term v /d 20 - u in the following manner:
d3
bias + bonus
t Iaze ulls,, + (xe u, bi) s
(6)
which gives us O(d VT) overall regret by Eq. (5). This approach relies on two conditions to be satisfied. First, we have to find b, that makes Eq. (6) hold. Second, we have to ensure that the FTRL algorithm achieves a ((d bound under the loss sequence OL- - bt-
To meet the first condition, we take inspiration from Zimmert and Lattimore [2022] and lift the problem to the space of covariance matrix in [(4+1)x(d+1) Considering the bonus term a, in the lifted space, we have
H, U.-U,a o, TH
04 1)
Using Lemma 17 and Corollary 22, we can upper bound Eq. (7) by O (dex) 2 | tx 5. gives
This
T
d3
bias + bonus
- u||x,
+ do
at
|i
-uls
4
T
d 11,
2x 11s
+ Σ
d3
||
u
Ot
1|
u
t
4
mml
Using Lemma 18 to bound the second term above by o d3/t)//=///oot ((d)). and AM-GM bound the third term by Õ(Σ. /(tor) )) O(d VT), we get Eq. (6), through the help of lifting.
To meet the second condition, we have analyze the regret of FTRL under the loss ÿ. by The key show that the bonus ب introduces small stability term overhead. Thanks to the use of the logdet regularizer and its self colf-concordance property, the extra stability term introduced by the bonus
can indeed be controlled by the order VT. The key analysis is in Lemma 27.
Previous works rely on exponential weights [Luo al., 2021, Dai al., 2023, Sherman al., 2023] rather than logdet-FTRL, which comes with the following drawbacks. 1) In Luo et al. [2021], Sherman al. [2023] where exponential weights combined with standard loss estimators, the bonus introduces large stability term overhead. Therefore, their bound only be 7/3 at best even with simulators. 2) In Dai et al. [2023] where exponential weights is combined with magnitude- loss estimators, the loss estimator for action a
longer be represented a ÿt- Instead, it becomes a complex non-linear function. This restricts the algorithm's 's potential to leverage linear optimization oracle over the action set and achieve computational efficiency.
simple linear function
3.5 Overall regret analysis
With all the algorithmic elements discussed above, now we give a formal statement for our regret guarantee and perform a complete regret analysis. Our main theorem is the following.
8

---

Theorem 2. Algorithm 1 ensures Reg & O(dPVTlog])
Proof sketch. Let Ao be drawn from D independently from all the interaction history between the learner and the environment. Recalling the definitions in Definition 1, we have
T
Reg-
E
(a wA, .01))
E
H UA m2)
=
Σ
H.
Ao
U
,1))
T
T
T
S E
H Ao
U
Ao
7t -1)
+
Σ
H Ao U art 1
+
Σ
H U f2 o1
Bias
Bonus
FTRI-Ree
Each can be bounded as follows:
Bias < Odd log 7) + Ei= oillu xz 221 (discussed in Section 3.3).
Bonus (T T) Ei= arllu 2211 (discussed in Section 3.4).
FTRL-Reg Odd log
Combining all terms gives the desired bound. The complete proof is provided in Appendix D.
Handling Misspecification
In this subsection, we show how approach naturally handles the case when the expectation of the loss cannot be exactly realized by a linear function but with a misspecification error. In this case, we assume that the expectation of the loss is given by E[l,la, = al = (a) for some fa Rd :-1, 1]. and the realized loss & still lies in [-1, 1]. We define the following notion of misspecification (slightly more refined than that in Neu and Olkhovskaya [2020]):
inf Assumption (misspecificaaioon. / E inf yEns sup AEsupp(D) SUPae (a, u))
Based on previous discussions, the design idea of Algorithm is to 1) identify the bias of the loss estimator, and 2) add necessary bonus to compensate the bias. When there is misspecification, this design idea still applies. The difference is that now the loss estimator ÿ1 potentially has more bias due to misspecification. Therefore, the bias becomes larger by an amount related to e. Consequently, we need enlarge bonus (raising (2)) to compensate it. Due to the larger bonus, down the learning rate 7/ to make the algorithm stable. Overall, to handle misspecification, when is known, it boils down using the same algorithm (Algorithm I) with adjusted a, and 77-- The case of unknown & can be handled by the standard meta-learning technique Corral [Agarwal et al., 2017, Foster et al., 2020, Luo al., 2022]. We defer all details Appendix E and only state the final bound here.
further need to tune
Theorem 3. Under misspecification, there is an algorithm ensuring Reg S 0 + VdsT), without knowing in advance.
4
Linear EXP4
To tighten the d-dependence in the regret bound, we can use the computationally inefficient algorithm EXP4 [Auer et al., 2002]. The original regret bound for EXP4 has polynomial dependence on the number of actions, but here we take the advantage of the linear structure to show bound that only depends on the feature dimension d. The algorithm is presented in Algorithm 2.

---

Algorithm 2 Linear EXP4
input: %
for t 1,2,... do
Receive Ar Rd
Construct 14 A(A,) such that E. |aall I d, where G. Bawer laa 7. Set
-1 ====1 E0,t
-
1-1 (-1) Ex=1 Es,
exp
Pt,x
Even exp
and define Pt.o = => P at.
Sample 04 ~ Pt = 7)pt + 7 and receive & E [-1, with E[ee] = (at, ye). Construct VT II: l,,x (=,,,, H. a,l), where H, Ba-pi |aa ]
To rum Algorithm 2, restrict ourselves to finite policy class. The policy class use in the algorithm is the set of linear policies defined as
II
Th BE (o(A) argmin a
(8)
acA
where θ is an 1-net of [-T, Tjd. The next theorem shows that this suffices give near-optimal bounds for our problem. The proof is given in Appendix F.
Theorem 4. With 7 (log T//T and 1 / (logT)/TT Algorithm 2 with the policy class defined in Eq. (8) guarantees Reg = O (dV (dyTlog T)
Note that this result technically also holds in the "A-A" category with respect the policy class defined in Eq. (8). However, this policy class is not necessarily sufficient cover of all policies of interest when the contexts and losses are adversarial.
Conclusions
We derived the first algorithm that obtains vT regret in contextual linear bandits with stochastic action sets in the absence of a simulator or prior knowledge on the distribution. As side result, we obtained the first computationally efficient poly VT algorithm for adversarial sleeping bandits with general stochastic arm availabilities. We believe the techniques in this paper will be useful for improving results for simulator-free linear MDPs as well.
References
Yasin Abbasi-Yadkond Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-233 22200, 2011.
Jacob Abernethy and Alexander Rakhlin. Beating the adaptive bandit with high probability. In 2009 Information Theory and Applications Workshop, pages 280-289. IEEE, 2009.
Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Conference on Learning Theory, 2009.
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646. PMLR, 2014.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
10

---

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
Peter Auer, Nicolo masa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(())48-77) 2002.
Peter L Bartlett, Varsha Dani, Thomas P Hayes, Sham M Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. COLT, pages 335-342, 2008.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourleenth Inte Internationa Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
Yifang Chen, Chung-Waz Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non non-stationary contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pages 696-726. PMLR, 2019.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011.
Yan Dai, Haipeng Luo, Chen- Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. In International Conference Machine Learning. 2023.
Christoph Dann, Chen- Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In International Conference Machine Learning, 2023a.
Christoph Dann, Chen-Ye Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In Conference Learning Thheory, 2023b.
M Dudik, D Hsu, Kale, N Karampatziakis. Langford, L Reyzin, and Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the 27th Conference Uncertainty in Artificial Intelligence, UAI 2011, page 169, 2011.
Ehsan Emamjomeh-Zadeh, Chen- Yu Wei, Haipeng Luo, and David Kempe. Adversarial online learning with changing action sets: Efficient algorithms with approximate regret bounds. In Algorithmic Learning Theory, pages 599-618. PMLR, 2021.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning. pages 1539-1548. PMLR, 2018.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependens com- plexity of contextual bandits and reinforcement learning: A disagreement- perspective. In Conference on Learning Theory, pages 2059-2059 PMLR, 2021.
Dylan Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction. allocation, and triangular discrimination. In Advances in Neural Information Processing Systems, 2021.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances Neural Information Processing Systems, 33:1 1478-118111 1489, 2020.
Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the firty-eighth annual ACM symposium on Theory of Computing, pages 128-141, 2016.
11

---

Tiancheng Jin, Junyan Liu, Chloé Rouyer, William Chang, Chen Yu Wei, and Haipeng Luo. No- regret online reinforcement learning with adversarial losses and transitions. arXiv preprint arXiv:2305. 17380, 2023.
Varun Kanade and Thomas Steinke. Learning hurdles for sleeping experts. ACM Transactions Computation Theory (TOCT), 66)):1-1,, 2014.
Varun Kanade, H Brendan McMahan, and Brent Bryan. Sleeping experts and bandits with stochastic action availability and adversarial rewards. Artificial Intelligence and Statistics, pages 272-279. PMLR, 2009.
Leonid G Khachiyan and Michael Todd. On the complexity of approximating the maximal inscribed ellipsoid for a polytope. Technical report, Cornell University Operations Research and Industrial Engineering, 1990.
Robert Kleinberg, Alexandru Niculescu-Mize and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2-3):245 272, 2010.
Fang Kong, Xiangcheng Zhang, Baoxiang Wang, and Shuai Li. Improved regret bounds for linear adversarial mdps via linear optimization. arXiv preprint arXiv: 068344 2023.
John Langford and Tong Zhang. The epoch-greedy algorithm for contextual aunti-armed bandits. Advances in neural information processing systems, 20(1):96-1, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-Wei Lee, Haipeng Luo, Chen-Yu Yu Wei, and Mengxiao Zhang. Bias no more: high- data-dependent regret bounds for adversarial bandits and mdps. In Advances in Neural Information Processing Systems, 2020.
Gene Li, Pritish Kamath, Dylan J Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35:23737-2311 2022.
Yingkai Li, Yining Wang, and Yuan Zhou, Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173-2174. PMLR, 2019.
Tzon-Tze Tzer Lu and Sheng-Hua Shiou. Inverses of 2 block matrices. Computers Mathematics with Applications, (3(1-2):119-1111 2002.
Haipeng Luo, Chen- Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pages 1739-1776. PMLR, 2018.
Haipeng Luo, Chen- Yu Wei, and Chung- Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931- 22942, 2021.
Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou. Corralling larger band of bandits: A case study on switching regret for linear bandits. In Conference on Learning Theory, pages 3635-3684. PMLR, 2022.
Arkadi Nemirovski. Interior point polynomial time methods convex programming. Lecture notes, 42(16))3215-322 2004.
Gergely Neu and Julia Olkhovskaya, Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory, pages 3049-3068. PMLR, 2020.
Gergely Neu and Julia Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. Advances Neural Information Processing Systems, 1440-11111,, 2021.
Gergely Neu and Michal Valko. Online combinatorial optimization with stochastic decision sets and adversarial losses. Advances in Neural Information Processing Systems, 27, 2014.
Julia Olkhovskaya, Jack Mayo, Tim van Erven, Gergely Neu, and Chen- Yu Wei. First-and second- order bounds for adversarial lincar contextual bandits. arXiv preprint arX0v:3305.00832, 2023.
12

---

Alexander Rakhlin and Karthik Sridharan. Bistro: An efficient relaxation based method for contextual bandits. In International Conference on Machine Learning, pages 1977-1985. PMLR, 2016.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Aadirupa Saha, Pierre Gaillard, and Michal Valko. Improved sleeping bandits with stochastic action sets and adversarial rewards. In International Conference on Machine Learning, pages 8357-8366.
PMLR, 2020.
Uri Sherman, Tomer Koren, and Yishay Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference on Machine Learning, 2023.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 1743),1904-1911, 2022.
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages 1159-2168. PMLR, 2016a.
Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E Schapire. Improved regret bounds for oracle-based adversarial contextual bandits. Advances Neural Information Processing Systems, 29, 2016b.
Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pages 495-517, 2017.
Chen-Ye Yu Wei and Haipeng Luo, More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, pages 1263-1291. PMLR, 2018
Chen- Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096, PMLR, 2022.
Yunbei Xu and Assaf Zeevi. Upper counterfactual confideeee bounds: new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07876 2020.
Tong Zhang, Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834 -007833-557,0 2022.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In Conference on Learning Theory, 2023.
Yinglun Zhu, Dylan J Foster, John Langford, and Paul Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference on Machine Learning, pages 27428-222 274533. PMLR, 2022.
Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pages 3285-3312. PMLR, 2022.
Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the efficiency pareto frontier for online learning of portfolios and quantum states. In Conference on Learning Theory, pages 182-226. PMLR, 2022.
13

---

Appendices
Summary of Notation
15
B Auxiliary Lemmas
15
Concentration Inequalities
16
C.1 General Concentration Inequalities
16
C.2 Concentration Inequalities under Fixed Policy p
17
C,3 Union Bound over Policies
D Regret Analysis
26
D.I Bounding the Bias term
26
D.2 Bounding the Bonus term
27
D.3 Bounding the Penalty term
30
D.4 Bounding the Stability- term
30
D.5 Bounding the Stability-2 term
32
D.6 Bounding the Error term
33
D.7
Finishing up
33
Handling Misspecification
E.1 Known misspecification.
34
E.2 Unknown misspecificatioon
36
Analysis for Linear EXP4
42
G Comparison with Dai et al. [2023] and Sherman et al. [2023]
43
G.1 Regret Analysis Sketch
44
14

---

A Summary of Notation
We summarize the notations that have been defined Algorithm and Definition
+ 1)3 (T/)
B. = θ
t t-1
2,
E B [a]
H t-1
Σ
E Bangat Ar
[(a it)((a [
1-1
Taa
a
ii, + f.
H. t- Σ
E
Ar
a
1
Σ. = H. + B.1
ΣS + 2G
it
Σ A, + 3,I
2n
1 1+ 8:]
á = EA [a]
H, EANDEE
((a 81)(a -tt)
aa T a)
H, = EAND
T
B
Auxiliary Lemmas
Lemma 5 (FTRL regret bound, Lemma 18 of Dann et al. [2023a]). Let Ω C. Rd be a convex set, .h.....9T E Rdd, and ....... 1/r > Then the FTRL update
t-1
arginin wEn
Jr
+
=b(w)
T)
r=1
ensures for any u Ω and n7o 0.
(wa Mt)
(uu) min (w)
1
1
Dis Dww w:)
(v(u)
- vww))
max(w:
w. 9t)
To
T--1
wen
Penally
Stability
When IJo, M. or non-increasing, the penalty term can further be upper bounded by
Penalty S (b()) min (ww)
TT
Lemma 6 (Bernstein's incquality). Let Xi.... .nn be iid random variables; let E[X] be the expectation and (X)(X) be the variance of these random variables. ffr any |X; - [X],,]] < R. then with probability of at least -. 8.
4 Var log
4R log x
X B[X]
S
3m
15

---

Lemma 7 (Hoeffding's s inequality). Let ,,,..., be iid random variables; let a S X, S b and let [[X] be the expectation. Then with probability of least 8.
-
n x,
log 2 2n 8
$ - [[X]
a/
n
Given F(X) = - log det(X), D2F(X) = X-1 2 X-1
where @ is the Kronecker prod-
uct. For any matrix A
a1
an let vec(AA =
which vectorizes matrix
On
to a column vector by stacking the columns The second order directional derivative for F is D2F(X)(A, A] = vec(A)² (X- & X-1) (e) =
We define pseudo-norm and more discussion can be found in Appendix of Zimmert al. [2022]. In the following analysis, we will only use one property of this pseudo-norm shown below which similar to the Holder inequality.
[[Al]==F(X) = X
and |||| | = XXXX
Lemma 8. For any two symmetric matrices A, B and positive definite matrix X,
(A, B) $ || |
Proof. Since 2 xXxx)-1=X* = X from Holder inequality, we have
= - =1 (A, B) (vec(A), vec(B)) < |
C
Concentration Inequalities
The goal of this section is show Lemma 18 and Lemma 19, which key bound the bias term. We first introduce useful lemma from Dai et al. [2023], which will used later to prove our concentration bounds.
C.1 General Concentration Inequalities
Lemma (Lemma A.4 in Dai et al. [2023]). Let H H2.... Hy i..d PSD matrices such that B[H,] H, H, = I almost surely and H = dn loog 8 I. Then with probability 1 8,
H. H
log 12
Corollary 10. Let H1, H2...., Hn be i..dd PSD matrices such that E.H.) = and H; I el almost surely for some positive constant c. Let Å Em= H4, then with probability
3c d
d 1
ń + 2 log
1
H
(9)
Proof. A simple corollary of Lemma 9 under the condition of Lemma 9 is that
d
H
-V
log
112
log
7
n
2n
d
d 1 H.
H
log
(10)
2n
where we use that H
f H
for any k > 0.
26
16

---

Now consider the condition of this corollary. We first consider the case where S log( S 1. In this apply Eq. (10) with Hi H3 2n. log( & I, which satisfies the condition for Eq. (10) to hold. This gives
1
)))
d
H;
+
log
+
log
1 2 2c
H
log
2c
2n
2n
2n
8
i=
3c
d
H
log
I = H
with probability at least - 5. When log(5) 1. Eq. (9) is trivial because 1 N 2 44.
dl n
C.2 Concentration Inequalities under a Fixed Policy p
In this subsection, we establish concentration bounds for a fixe policy p (with p E ((A) denoting the action distribution it uses over A) over i..d. contexts. The results in this subsection preparation for Appendix C.3 where we take union bounds over policies.
The setting and notation to be used in this subsection are defined in Definition 11.
Definition 11.
Let (Ai....,, An) be i..dd context samples drawn from D. Let D be the uniform distribution over (AI....,Anl
Over this set of context samples, define for any policy p.
x(p) EAAD D E Bampa [a],
é(p) TE A^D D E Ba [a),
(p)) EAAD Banpp
[(a (ap))((a =(p))
(p) = E AA~ D BanDA
[aa a(p))(a =[p))
(p)) AA E EupopA
[aa
(p) IE EA BaNpA
aa
E(p) (1() + B1,
Epp) (p) + 3I,
where 3
5d (og
Lemma 12. Under the setting of Definition 11, for any fixed with probability at least 1 - 6,
((p) + 4d 4dlog(6d/5))
n 2 H(p),
(Ø)+ 3dlog(d/0) H())
Proof. this proof, we use à, x, H, H, A, to denote x(p),x(p) H()), H(p), Hp) H(p) since is fixed throughout the proof.
Since ||a|| < 1, H < 27 and Å z 2T. Thus, we can directly apply Corollary 10 with 2 to with probability 1
3d log(3/10))
A + n
H.
17

---

To prove the first inequality, we first decompose H and H
EA-DBarph [(a ((a==)(a - =
EANDBauph
[[a- - + x - 2)(a - x + = [[a x))a- 2) []
EANDEa
+ (x a) =)²
(because EANDBeupAl (a
0)
(11)
H AnD Bampa
[aa-))(e - ] [(a + I i)(a - - xz
[(a 2a(a z) ] (z 2) T) E AaBaaa
(because E A. (a (a-x) xx) = E x)
(12)
From Hoeffding inequality (Lemmaa 7) and union bound, with probability 1 3. for all ls E [d]. we have
1
6d
lex r 2/ S
V
2n
log
6
which implies that of (x 6x - -T)Tcp 1 $ log( of) for all k, and thus
2m
6d
(x (x-a) () - -t) = log
I.
(13)
2n
By directly applying Corollary 10 with c = 2. we get with probability at least $
3d 3d log(3//0) I Ea-nBanpa [[a - xx) - x)) "]
E PA-DEarp [(a - xa - x)) [ +
n
Further using Eq. (11), Eq. (12) and Eq. (13), we get with probability at least 1 3
4d 4d log(6d/0)
2
n
Taking union bound for both inequality finishes the proof.
Lemma 13. Under the setting of Definition 11, for any fixed policy p. with probability at least 1 O()),
|k<(p) - = So (dlogdd/))
Proof. In this proof, we use a, x. H, H. A. H. E.Σ denote 2(p), x()), (p), (p), H(p). E(p), E(p) since p is fixed throughout the proof.
We first rewrite H.
H BAADBaapph
[(a 8)(a ( =
EawDBarph
[(a - 2 x - (a x - xx =]
= EANDBErpA [(a x)(a x) | + (x - (x T (because EAND (a xx) 0)
(14)
To simplify analysis, we perform diagonalization. Suppose that EANDE - - x²
admits the following digooddccomposition:
EA-DEE.pee (a (a - T VAVT
where V is orthogonal matrix and A is diagonal matrix. By Lemma 12 and the definition of B in Definition 11, we have with probability 5,
Σ - H + pl 2 , VAV + pl
2
2
18

---

with some p= O [ where the second inequality by Eq. (14). Thus,
| 2 - (x -)) - T (x -)
S (x -0) (
(5.1VAV (AVV + +pl)
(x (e-))
2
(0 - x) TV ( pl)
VT x).
Define
A o (0
V - 2)
Ck V B Barpsi [a]
o V BANDBorp (a)
Define 2/
Define Zi,
Since EALD [2(00]
2u by Bernstein's inequality, with probability at least 8, we have
A S (1)
log(d/)) log((/)))) log(d/8)
(15)
for all k, where
Var (1()) EAND ( Banpsla [a] et V xx))
On the other hand,
Ask DAND IV z)(a 2) Vie
(cr VT v [Tx) 2)²
= =ENDDBanpt
From Jensen's inequality,
ARk = Eaanna
(eT VT a- ex V s)
2 EAND (ez V V Bangal [a] e vT)) Var(2,
Thus,
1
||0 | S (0 - x) TV
VT xx)
2
(ax)²
ARk + p
log (d/5)
Var( (2,0)) + log(d/8)
(by Eq. (15))
n
Auk +
dloo(d/5)
(Ast 2 Var(Z(") and p = @(dloR(d/0)
<
Lemma 14. Under the setting of Definition 11, for any fixed policy p. with probability at least 1 O()).
[(($p)) (p)))ll 50 (dlog(d/o)
7
for any y E Bd
Proof. In this proof, we use 3, r. f1, H. A H, E, to denote z(p), x(p), (1), H(p). H H(p). E(p), E(p) since p is fixed throughout the proof.
19

---

First, we we-write H and H:
BADD [(a (aaa - =]]
EANDBarph
[ - x 2)(a x _
EANDBanpA
[(a (a-=x)(a- 2) [] + (x a) =)
(because BANDBeupal (a xx) 0)
(16)
H AnD Bampa [a--))(e - ]
= E Ann
[(a + I - i)(a - -
[[a 2)(a z) ] - (z 2) T) E BaD
(because E B.b xa-x) xx)= xx)
Then, by definition (in Definition 11) and the calculation above,
5-h H
f1 -H-H- +
1
B Barpa 1(a ==)aa=))) 2 BANDBaRDt [(a ((===)(a- [[](--=)]]11 -2(x 8)(x =) BI.
11
define this as r
Using |la + b + cli2 < 3||a|| 3 311 + 3||c|| we have
-(É- H)yll - 3 T y| f 12 8)( 2) u 1yll
= T 3- + 12 - = + 0(3).
(17)
The second and third term are bounded by O dloogd/66) using Lemma 13 and the definition of B with probability at least 1 (5). Below, we further deal with the first term. To simplify analysis, we perform diagonalization. Suppose that EA-DLE
xa(a x) admits the following
eigen-decompooition:
BA [[a - (a - x) x) VAVT
where V is an orthogonal matrix and A is diagonal matrix. Then
Tol y TT TTy = (V 8)
v).
(18)
Below, we further deal with the V TV and T AV terms in Eq. (18). By Lemma 12, with probability least 1 6,
$ 7 + =
VAV +pI,
for some ④ (dlog(d/6)) where we use Eq. (16) in the second inequality. Therefore,
VTEV z 1 A
(19)
Next, denote A VTV. By definition, it can be written the following:
1
E BangAi [v x)) vv V
EANDBanDA [v - xa x)T Vv]
defining A
with ( being i.i.d. samples with mean E[A (1) = A. While these are d d matrices, we will apply concentration inequalities to individual entries.
Let AgRA eT_ (0e,, be the (k:, h)-th entry of (0) Notice that E [[(an]] = e_Aer Agho the (k,, h)-th entry of A.
20

---

By Bernstein's 's inequality, with probability at least - 8, we have
(Aas Ass) s s0 50(v Var(Auas) log(d/)) log(d/6)
A
(20)
With the manipulations and notations above, we continue to bound Eq. (18) by
|| - A(V -
(let y = VT ")
S 2y A (A p1) Auj
(by Eq. (19))
2T (A pl) A)
By direct expansion and the fact that diagonal,
d
Tr + (((+pp))1A)
AA p1) 2) kk
==1
Aun
Aph +
k= h=1
(ar(ANa))ogg((()
log (d/8)
Anh +p
n
n²
A=1
(by Eq. (20))
d
B(A log(d/))
log(d/8) de logo22d/1 (d/6)
0
+
(21)
Anh +p
n
pnd
k=1
By definition,
Aph = Bangt
leoV (a x)(aa x) Ven
and thus
d
d
Ags I E Bamppri
Σ
(ex (a-VTa--s(e x) Ve)))
k=1
Bangrrts
Σ ToT V (a z)(a T V x) Ten
Bangars
V (a z)(a x) T(a (a x)((a x) Ven]
< E Bangra
(e V (a z)(a x) T Ve..
Aihh
and Ed E[22an] E[Ainn] Anh- Continuing from Eq. (21) and using that p O [dlog(d/61
Anh (d/()
d llog2(d/b))
(dlog(d/0)
Tr (A(A+ pf)
< 0
(Apa + p)n
n²
This gives a bound on | and finishes the proof after combining Eq. (17).
C.3
Union Bound over Policies
In Lemma 12, Lemma 13, and Lemma 14, we have obtained the desired concentration inequalities under fixed policy p. this subsection, we proceed to take union bound over all policies that are possibly used by Algorithm I.
21

---

The set of policies that could be generated by Algorithm is the following:
P p: Cov(p argmin
{ (H, F(H) for Z E
HEHA
where = [-T2, Te](++)x((+1)) nS with S denoting the set of symmetric matrices. To see this, notice that Algorithm at round t corresponds to the policy defined above with Z 17s Σ (9- a. ".
Our goal is to construct a e-cover P' so that every policy p P can find a policy p' E P making -el 3 Cov(r=) Cov(p'A) I el on every action set A. The size of such cover is bounded in the Proposition below.
Lemma 15. There exists an e-cover P' of with size log [P'| O (df log 2) such that for any
p E P. there exists an pl E P' satisfying
(ov(pA) - Cor(p!d) -Co((/)) SE
for all A.
Proof. is straightforward to construct an {-cover C for [T] in Frobenius
norm with size |C| = (24/d112) ((++ (Exercise 27.6 of Lattimore and Szepesvári [2020]). Now
define p' as
P' { pp: Cov(pA) argmin (HH F(H)) for Z Ec}
(22)
НEиA
Below, we show that this is a e-cover for P.
Consider two policies and p2 defined as the following:
Cov(pT)
argmin 21) + F(H))
HEHA
Cov(p2) = argmin (2) + F(H))
НERA
with || - < 5. Consider an arbitrary A and define H = (o)( H2 = Cov(pg)) Below show H H2lFF Sc
Since F F(H) is convex for H, from the first-order optimality condition for convex function, we have
( ) + ( < HH, Z1) + (H2) (r Hi)
Z2) + (H, Z2) + F(H2) D,(H2,HH) H,) H2 2 + F( S Z2) + +(H,) - (H,H,,H,)
(H, + (H,, Z2 Z1) F Dr H2)
Adding up these the two inequalities, we get
2 min ( p 1 H2), (H, H))) S H H2) + Dp H H < Z Z2, H Hi)
Since the second order directional derivative for F is F X X = Tr symmetric matrix X, from the Taylor series, there exists H' that a line segment between H. and H. such that
for any
H H 2 min (D Dr H.. (2) Zz H
H
< 1 Zg 7211~~2F( H H₂ (2ll"F((")
(Lemma 8)
Thus have H H2 F(H))) S 2 Z 32||v==((H)) Since ||a S 1, H 3 2I.110 The left-hand side and right-hand side can be bounded as follows.
H H Tr (H, H2) - -2) > ,/ H - H2l1F
2: 2211 /Ir (1z((1 (2, 22) 21|2 - S
22

---

Combining the three inequalities above, we conclude that
H H2llF S H F2 Z Z2llv-2F(BY) S <4
Z2lla S..
I = H H el.
Lemma 16. Suppose that p. p'p' are policies such that for all action set A.
[oo(lAA) Cov(p'A) Se
(23)
Then all quantities defined in Definition 11 under and p' are close. That is,
|m<(p) - z²p')ll < [(((p) - =(p')l E
(24)
(25)
(p) (p'')l Te
(26)
(p) (p'))l Te
(27)
[H H(y')lF S
(28)
( (p''ll Se
(29)
[E(p) E(p')lsss 7e
(30)
(31)
Proof. Eq. (28) and Eq. (29) are direct consequences of Eq. (23) since (p) and Á (p) are expec- tations of Cov(p^) over distributions over A. Eq. (31) is directly implied by Eq. (29) because {p)) = (p) + SI.
To show Eq. (24) and Eq. (25), observe that by the definition of x(p) and (p).
aa a 1
EANDE Faa 1
EANDBarpall [a]
H BEADBBuphh
EANDEE [
a
EADD Banpa [aa x(p)
x(p) T
Therefore, ||-(p) x(y')l S (p) Hp''llr S e. Similarly, |(((p) - i(p')l s ((A(p)) (F))lF Se. If remains to show Eq. (26), Eq. (27) and Eq. (30), Next, we show Eq, (26):
H(p) H('')) EAND Eunps I(a (()))(a (()(aa--p))]]] Baaagaalaa -loo
EAND Banpa (aa 1 -E Bang'a (aa ]]
=(p))(p)T T ((p)x(p) T + +x(1))a(0) + (x1))=()/) (using EA Bampu [a]= = =x(p))
+ +p())((p) - -á(p')((p')
(32)
Using the property
|labT edl ||F 5 |lab ob || 1lob edl 1| S I|a -c|l|bl|| + |cll| dIl
we continue from Eq. (32) and bound
(p) - H(p')ll
(H(p) (x)))l=++ 2(( #(p')l + 11x(())))
-(0' (|+(p) 2(y')1
7e.
Eq. (27) can be shown in the same manner, which further implies Eq. (30) by the definition of Epp
23

---

Lemma 17. With probability 1 8. for all t = 1, ... .T,
H, 50(d + 1) log (ogg(3//00
1 Hi:
-- 1
2
H 50(d + 1) log(())) (3T/ 1z H
t
Proof. Notice that H., H., H,, H, corresponds to H(p)), H (pt), (p:)), (p:) defined in Defini- tion 11 with n = 11-1 1. To show the lemma, our strategy is to argue the following two facts: 1) the two desired incqualities hold for all policies in the cover P' (defined in Eq. (22)) with high probability. This is simply by applying Lemma 12 with union bound over policies in P'. 2) p: is sufficiently close to the nearest element in P' so the desired incqualities still approximately hold.
By Lemma 15, we can find p' P' such that for all A.
(ov(pp)) -or(pp+)) Sc.
By Lemma 16, it holds that
(p:)) H(D)ll $ 7c, (pt) H(D)Il s,
[[f((p.) (ll' S Te (p() - (p''')l Se
(33)
(34)
On the other hand, using Lemma 12 and union bound, with probability 1 - 8, we have
Hp')) + 4d |ogd
n = HD'),
(35)
3d log(d (p') +
I Hp').
(36)
Combining Eq. (35) and Eq. (33), we get
H(p)) + Tel + 4d 4d 6dd P' 10)) 1 H1'p)+++++ 4d (olo((dd
1 H(:)) cl 2
n I H(')) =
n
which implies the first inequality in the lemma by plugging in the choice of 7 and the upper bound of log [P| in Lemma 16. The second inequality in the lemma be obtained similarly by combining Eq. (34) and Eq. (36).
L
Lemma 18. With probability least 8, for all 1,....
1|.. 2el S O (d loggo(()) (dT/8)
t
Proof. Notice that zt, 2g, E, corresponds to x(Pt), (p:),, E(p) defined in Definition 11 with n t 1. To show the lemma, our strategy to argue the following two facts: 1) the two desired inequalities hold for all policies in the cover P' with high probability. This is simply by applying Lemma 13 with an union bound over policies P'. 2) Pt is sufficiently close the nearest element in P' so the desired inequalities still approximately hold.
By Lemma 15, can find p' p' such that for all A.
(ov(xe) - -Cov(' Se.
By Lemma 16, have
||x(p') x(p:)l S, ||²()) - M(pt)ll Sc,
[((p') - E(p.)l S 7e
(37)
24

---

Thus,
|x<(p)) - (ppe)l 1(p (
(IIxo(p)) =(vr) S(p)) -
1|x((1)) -||x(00)) -500 (1000)112200 11(0)))))) |<(p') =(p')) ((2')112(0>>
+ O [dog (d
= (lI((r) =((e)) ((p))) 1|x(11) =(p') 133
(by Lemma 13 with union bound over P')
0.p()))) -0" -0 "'6'''--1 +0 (log(d)P11/8)
t-1
(define 0, x(x)) i(px) and 0' - x((') =(p'))
(P(p())))))
E(6/) (0.- 0¹) (((() 02 + T (S(p))) (((0)))---()))00 00 0
0 (1//)=((111000(0 +T00(/)))) (0, -0') +
1-1
dlog( (d) P 118)
(0, 0²) (pp))) 0, + Epp' )) + 0 Epp' ($(p') - (pp)) (p: 02 + o
The first two terms above can be bounded by the order of Oeet²) by Eq. (37). Using the choice e = アr and recalling that log P = Olf log(d/e)) finishes the proof.
Lemma 19. With probability of at least 6. for all = 1........77 T,
d log (dT) /8)
II Ho) 3 so
Proof. Notice that Tt, 2r En corresponds to x(p)), (p:)), E(p,) defined in Definition 11 with n = t - 1. To show the lemma, our strategy is to argue the following two facts: 1) the two desired inequalities hold for all policies in the cover P' with high probability. This is simply by applying Lemma 13 with an union bound over policies in P'. 2) Pt is sufficiently close to the nearest element in P' so the desired inequalities still approximately hold.
By Lemma 15, we can find y/ E P' such that for all A.
(ov(pp)) - Cov(p' ||| SC.
By Lemma 16, we have
||>(p') - x(px)l Se, ||x(y/) - a(pi)l Se. |8(0')) - E(px)) Se
(38)
Thus, for any 1/ I 1,
[(({(p)) H HI::) 11 B(pp)
-(I(((p)) - H H(p:)) (1 -((((p)) (00()))-((p'))))) H('')) 1 ) 11(E(p') - Hpp')))ull
(1 Se( + (dlo((d[P1/5))
(I((S())) - (( 1((2('')
(by Lemma 14 with an union bound over P')
(px)))))1 -0.- - - + dlog(d[("\/0))
t t-1
(define 0, = (51(p.) - H(p:)) and = (5:(y)) (1))))
(dlog( (dlog((|P)))) (PP')/0))
(0. 8¹) (TT(pp)-111 0.0++ + TT (S(()) 110-))))---))-1----110-1111 0: + T ((T((p))
00)) 1(p')-((0 -1 0
S (0: 8 (((p)) + - + 0 E(p') - -(p)))((pp))))) E(p.) -10
10, + +
ddlogddP'))
t t-1
The first two terms above can be bounded by the order of ( by Eq. (38). Plugging in the choice of = 75 and recalling that log P'| = (dl log(d/e)) finishes the proof.
25

---

D Regret Analysis
Consider the regret decomposition in Section 3.5.
Reg(u)= = E
Σ at u 11.)
E
H U.u E
H U
.x0)
T
T H U-u 9r artt.)
E
H Uo -tt 11)
H U a.Str
E
Bias
Bonus
FTRL-Reg
where Ao is drawn from D and is independent from the interaction between the learning and the environment. Recall that our algorithm is FTRL:
F(H) N
H Ao argmin
Σ
H. H - (a.t
HEHAD
The FTRL-Reg term can be handled by the standard FTRL analysis (Lemma 5). In order to deal with the issue that F can be unbounded on the boundary of H- apply Lemma 5 with the regret comparator A defined as
T
(1 T
1 U + T
H.A
where HAA A argmingeHA F(H). Thus,
FTRL-Reg
H U ftt - ar 1111)
U Ao
U-A 5r - -a-rst 1
E
+
F Ao EH F(H)
T
D(H H:A0)
E
+E
max H HEH
H - H1,
1/T
21/r
Penalty
Stability-1
+ E
max HEH-A
H
H. a.
A-1
O(HHH.M.
E
U Ao Uo ft w1
217
Stability-2
Error
(39)
In the rest of this section, we bound the following terms individually: Bias, Bonus, Penalty. Stability-1, Stability-2, Error.
For any 2, T, let E be the event that the high- probability event in Lemma 17, Lemma 18, and Lemma 19 happens for all 1.... t and E,-1 be the opposite event of ε any of these three lemmas fails for any 1, , 1). We have P[E,-1] [- E be the conditional expectation that event E happens and let Ef = E[. E--1,
O and P( = 0 Let
D.1 Bounding the Bias term
Lemma 20.
Σ H.A Au - Ao ,70 96)
1 T
d log (T/))
Bias E
S
Σ
arl le
-
+0 87 + Σ
a,t
t=l
t=1
26

---

Proof.
For any i, we have
E (H U - 14>l
E [(H: U, 71 - 9c)
(taking expectation over AA)
1 [(ar u, 1/1 Kc)
(by the definition of lifting) (by the definition of ğs)
E (ar - u) T Yt E (at 81)a, 31)
F (1x u)T T (tt 5ty 1 (aa - fat - (x)) 81
T1) )] Ry ( - u) - 2 yt
E (xx u) T Sig " BLADDArr ~pt [[a: - ft)(a; - =t) Vi
Ex (o) - u) T - (EADBB App las] &1) 2. vv (taking expectation over A, and ag)
(12
u) T " (Et - (Ex-
(ae-HH) wh - E [1re - u) T En-² (xt - 2x) & yt
(by the definition of H₃ and 2τ)
$ 3
(r) u) T E (Ix, Hi) Va
+ + [1 u) "Ix (x+ - #e)
(5 yul - 1)
$ E
11
u|| م||اا (1(E, H₂, Vells
+ 1 Ze (ss
d3 log(T/0) t
$ 0
| - |
(Lemma 19 and Lemma 18 given E
01 | u1l O
d log(T/6)
(AM-GM inequality)
aut
On the other hand, since Ex - t ž +l, for any 1 = 1,,... I,..,,
l |E, (ar 2 )a yella I |E,'(a: ft)ll2 - O(T)
Thus, we have trivial bound
E. ( (1 UA n - 71)
E E. (H, U 310) E E, (xx,
u, yr -(1) 1 S O(T)
Therefore, we have
H Au - U__, - -5ii
Bias E
Σ
1=1
Hoo0 - Uno no $t))]
E
E
By
(H,40 Un_, 7 - 51) E-ع T(E
+ E
Σ F2 (
U ,0,,, 7/ - 71) E
T(E-11}
T
T
d log(T//)
<
aul|> - -ul +
Σ
+ 8T
4
axt
D.2 Bounding the Bonus term
We first prove the following useful technique lemma to bound the inner product of lifted matrices.
[ + gg" T
9
H
hh
h
Lemma 21. Let G
H
where G and H are positive semi-
h
0
definite, and H' .. + vo where v
Rd+11
Then we have
/B
27

---

1. Tr (H- = Tr G) + 119 - -hl 1 +
2. Tr (G)
11g
h11 H
g²
|1ll
2 1+ I1 1 Ø-1
(I+3)2
A
Proof. From Theorem 2.1 of Lu and Shiou [2002], for any block matrix R =
if A is
C
invertible and its Schur complement SA = D - CA--CAA-BAB B is invertible, then
A 1 + A A
-A
R
CAA
S
Using above equation, for the first equation, Since Schur complement of H + hh" is hT H-IHH h. Thus
H
4T' The inverse
1-NH-'K
[I H hh (H + hhT)
-H -H-1
H-1
-H
H-1
H-
1+hTH-11
-h H- 1+HTH~1h
and
Tr( (G) Tr - - 99 H -H hg
h h + +1+ H
- 9 2g H h + h
= G) 11g - h 1/ + 1.
For the second equation, observe that
H' = H + hhT h
(H + ,
1 h
H' + +h'hT 1d ha
= (1 + 3)
1+8
1+8
(1 + (3
hT
1
1 h
1
1+8
where h/ = 1tsh and H' Applying the first equality, we have
I+3 H
(1+3)) )hh T
1
H + (1+37 (1+3yzhh hh" 2 0.
1+B
143
Tr((H)) = 1 ++ 8
(Tr((H)) G) + l1g - W + 2 1+ 3 11 M1
Below, we continue to lower bound this term. By the same formula above, we have
1 H
3 hh -1+ 1 1
31 hh H
H'-1
+
1 3 (1
3)2
1 HTH
Thus
1 l1g 11117p--1
1
1
2 2(1 + 3)
l1g - hbll H1
11 - h'1l2--1
(using |la b112 < 2/|a|1 + 2/16113)
1 1+ 3
200
1
TT)
H
I+B
8
1hh T H-1
h9- - (h- -
H
I+B
8 H H-1hhh T H-1
(h (h- 11)
+ h4 hT 1h
1 1+ 1+3 h H H-1
1
I+0 ((g h) 21
B
119
(1 3)2 1111
(using h - h' - h)
2
+ 1+ [
2
1
11g 1
I+3
8
||b| -1
11g - -hl?
132
|A
(Cauchy-Schwarg
2
2 (1
+ T [11111/-1)
(1 3)2
1
182
11g -1ll
|| 11
2
1
+
-
[1:
(1 + 3)3
28

---

Using Lemma 21, we are able to show Corollary 22 which bound part of the second term
Corollary 22. TrUU,, ) 1 ||uu 2. 4.
Proof. From Lemma 21, we have
18
Tr(US;))
1/u Bell3,
8 13
Be I+p. 1 +
|| (8.1
(1 + 3,)3
Since E, - B,I, $-1 1 D.
I. Since ||æzl22 I 1. we have ||āx|l
I 1 Then B.
3
TUUU 2
1|u
(1 + 3.)
+ 14...
Be
Ste 1
(B. 202
(2)
1
4
Lemma 23.
H - Uno an
Bonus
E
1=1
2(d 2)
Σ
a4
1
rrll u - 24 2
L log (T/6)
+ 8T
at
4
Proof. For any 1, we have
E H Ao UAo UA,,, |
E Th
at (H, U) 0){;,1)
(taking expectation over AA)
H H - at Tr (UŠ,1)]
at Tr
oz Tr
[Ef [H(] E
_
|/u
+
4 ax
1
(Corollary 22)
20, (d 2) E
a4
fell3, ]]
4
20, (d +2) E
04
||u
r2113
1
at ||00
Iza
12
4
ai
d' an log (T/5)
S 2a, (d + 2)
||
zz
21133 +
(Lemma 18)
4
On the other hand, since Σ, > tI 2 $1, we have trivial bound
B, H U Un, a.
E O(a.T)
29

---

Therefore, we have
I
H U-A, ,
Bonus
T
H - - -,,,,,0 -
E2
T
E
Σ E2
H Ao - Un , (
E 11
+ E
Σ
Br
H
U
an
E--
1(E-11)
(1 (1-8) 8)
a log(T/6)
2
at
04 |u - =ellzr- +
5T
Σ
a
aan log (T/6)
S 2(
Σ 00 Ot Iu 3el13--1 0
+ 8T
Σ at
D.3 Bounding the Penalty term
Lemma 24. U we have
Ao min 4 F(H)
F(U
2d (T)
V/T
T/r
Proof. Since A (1 ) U H H we have U
7 A Then
F(U A0 F(U min F(H)
det(HAA))
log(T(
log
det det(U Ao)
1/T
m/
WT
D.4 Bounding the Stability-1 term
Zimmert and Lattimore [2022] gave a useful identity to bound the Bregman divergence. We restate in Lemma 25 for completeness.
G +
9g
g
H + hhT
h
Lemma 25. Let
and
we have
g
1
h
1
D(G, = D(G, H) + 11g hll2
2 l1g - -1122--
Proof.
DG.. F(G) - F(H) - (VF(H), H
(ee((H)
log
+ +Tr(H - H))
det
(ee((H)
log
+ +TTHH- d-1
det(G))
det(HH)
log
Tr(H -T(H-'G) d-1
(G)
(e)
log
Tr(H + 11g M1 d
(Lemma 21)
det(G)
D(G, H1) + |1g - A
2 ||g - h H-1
30

---

Lemma 26. For any H E HAr we have
D(H, H1,40)
T
Stability-1 = E
H Ao H, (1.1
S 2d
11: + O
21/r.
[ p(p)
[Cov(p) + p(D)u(o)
m(p)
Proof. Recall that H (ov(PE and Cov(p)
we have
1
11(()) x 11012
D(H, H(A))
H Ao H. 911)
3 1 - -M(p), B1)
(Lemma 25)
21
21/e
[Mm(p) 2
Co
1 110
-1
2Tp..
71
llūa
1 (oo((r/0)
(AM-GM inequality)
2
1h
1 (ar
3i Rs 2e Cov(p,
2
1A
(a:
-11) " " ) (a: -1)
((6l s 1)
2
11
Th (a- (i--;))(a: ix.) T (ov(p1
2
Since EANDBanpr [(a- ((a--ip) -ie)(a 2.) on E,-1, we have
He, taking expectations over Ar, at and Ao conditioned
D(H, Ho
E
( H,
?e Tr (a, (a;- ae) "E, Cov(pE ) '
217.
2
Tee
-H BAOND [Cov(ptto)] Ei )
Tr
2
Notice that given E1-1,
Σ ス 2 H. = 2 EAND (Cov(p;)) + 2 (a: - xz) Tz)T== = BAND
Hence continue to upper bound the last expression by
H, - '1 E n Tr (H s 2nd.
E ne
Tr
On the other hand, since Σ,
= t ž +T, we have trivial bound
D(H,H
E4 H
H (1
E1-1
< 50(
21/1
Combining everything, we get
T
D(H H.A
Stability-1 = E
H Ao H.H))
2T
D(H, D(H.HAA0) H.A0)
H.Ao H,hh)
E
E2
27
D(H H()))
E
AoA
H,,,)
E
[(8-11}
27
T
D(H, Ao)
+ E
Σ Ey
HHA00
H 11,
E 1(
21p
1=1
T
< 2d
n) + O(8T2).
t=1
31

---

D.5 Bounding the Stability-2 term
Note that Lemma does not require matrix A, to be positive semi-definite. We will use it to prove the following lemma based on Lemma 34 in Dann et al. [2023b].
Lemma 27. If moa S 642
then
T
D(H,H, D(H, H,!)))
T
Stability-2 = =
Σ
max HEHAD
H.A H, -0,t,
<
24 + (
217
t=1
Proof.
We first show that
max HEHAO
HH.. H. -0,200
10-1
((H
2
2mp
Define
D(H Ho
G(H)
H -H -0,i
A-1
21/.
and X = |la,E,t1l 2F(HAOy Since Ex ビ 1, H.A 21, m1:0
645 we have
nd= m n || 17:04 Tr TH HAA " 2moat 1
32
Let H' be the maximizer of G. Since G(H:A0) O, have G(H)) > 0. It suffices show
H H.A0 ([<=pp1A S 16m, because from Lemma 8, it leads to
G(H') S | H I - | " S 16, 1 = a: || '1 (1 2/2
To show |H H1o00 ( 167, it suffices show that for all U such that IU H. (eF(HH)0) = 16nd, G(U) S 0. This is because given this condition, |
H.A (EF(H,40) > 16 then there is a in the line segment between H and H' such that IU - (0 = 167AA From the condition, G(U) - 0 S miH G(H') which contradicts the strictly concave of G.
Now consider any U such that IU - -H A6 A. By Taylor expansion, there exists U in the line segment between U and H.A0 such that
1 U H 11
G(U) S U H ( 1 E. "I (o--a((
417:
We have IIU H.aa Ao 1)) < U H. P( = 16m < 1.2 From the Equation 2.2 in page 23 of Nemirovski [2004] (also appear in Eq. of Abernethy et al. [2009]) and log det is seff-concordant function, have ||U 11
+ A 10 VoP(H//0) Thus, have
U H 12 (0 16 (16m;
G(U) < HH ( Mar & 1l 2 167,
16m,
We have 1 2r(""") = V 1H
V ( Observe the fol- lowing two facts: 1) all eigenvalues of HAr are non-negative since H:A and E are both positive semi-definite, 2) for a square matrix A with all non-negative eigenvalues, Tr(A²) < Tr(A)²
because Tr(A²) >; (AP) E, (A)² (, (A))2 We have
(H 111) Tr(H H E, )
32

---

This allows us to conclude
E
at [ 1 ( 2
at E
Tr(H, (
111 aadd
2
where we use that E. Ag D [ given E-1 On the other hand, since Σ, = i = II, for any 1,.., we have trivial bound
DHH.H,
Ex
ma8 HEHAD
H:A0 - H, -O, E
E1-1
S OTT
2/1t
Overall,
T
D(H,H
Stability-2
E
max HEHAD
H,,00
H, -O,
2111
T
D(H, H.A)
E
Eg
max HEH-Ao
HH:0 H. -a,
217.
T
D(H, D(H.H,A
E
E2
max HE--Ao
H H H.71)
EL-1
1(8--1
277
D(H, H,
+
E
E2
H H, 1.91)
E11
1(E-11
HEHAD
2n
1=1
S d
Ot O (8T2)
D.6 Bounding the Error term
Lemma 28.
T
Error = E
Σ
U - - < 0(1).
Proof. Since U (1 - 7/2 U
H, and E, 2 $1, ł # we have
T
T - U - -
Error =
T
Ao HA00 31 - (
=
T
t=1
I 01).
D.7
Finishing up
Recall the regret decomposition at the beginning of Appendix D. From Lemma 24, Lemma 26,
Lemma 27, and Lemma 28, we have
FTRL-Reg Penalty
+ Stability-1 + Stability-2 + Error
d dog((T)
T Σ
T
< 0
d
n: + d Σ + 8T
1/
t=1
tml
33

---

From Lemma 20 and Lemma 23, we can cancel out the additional regret induced by bias through the well-designed bonus term. Namely,
de
(og(T/6)
Bias
Bonus
Σ Ore 12z - w
+ -1
Σ
+ 87
Orl
T
T
T
a log I
T
+ 2(d + 2)
Σ
arllu
- 2z
11 +0
Σ
+ Σ
arT
1=1
t=1
log(T/0)
a log (T/o)
0
d
+ 87
att
1=1
1=1
1=1
Thus, we have
Reg
Bias
Bonus
-TRL--Reg
=o ( (dllog()
T
T
T
d
log(T/8)
La log (T/6) T
n
+
a0
+
t + 87
TT
axt
Recall that we have an additional condition in Lemma 27 such that for any t, ma, S Picking
Ot
d / M
6advE and ō TT, get
Reg O (& (Tlg())) d log(T)) (logTT)))(
where we assume d² < T without loss of generality (otherwise the bound is vacuous).
E Handling Misspecification
In this section, we discuss how handle misspecification defined in Section 3.6. In Appendix E. we study the case where the amount of misspecification is known by the learner. In Appendix E.2, we use blackbox approach to turn it into an algorithm that achieves almost the same regret bound (up to log T factors) without knowning
F.1 Known misspecification
As discussed Section 3.6, when the amount of misspecification is known, we still use Algorithm 1, but with different a and 77. Throughout this subsection, let az
d Vt Va and Me 61(dvi+
and point the modifications of the analysis from Appendix D.
We start with the regret decomposition similar to that in Appendix D, but here we define
y/ argmin max max [f((a) (a, w) EE AEsupp( D) aEA
max (f((a) (a, v.)l
AEsupp(D) aEA
(()) = f( - (a, v.).
34

---

The regret decomposition goes as follows:
T
Reg(u) = E
(fi(er) -s((urt)))
E
(as uni, .00
+
+5.
1=1
H U , 20)
T
H (pbom))) ET
+ ET
E
I
H Ao U 7t - 31
H do U Udo, as
$ E
+E
Blas
Bonus
H Ao U fo artt
TET.
FTRL-Rog
Now Dr = (a; Le with [EL,] = at ye ce(a)).
For the Bias term, the proof is almost the same as Lemma 20. The only difference is that from the fourth line, have
E, [ T)T (ye - E (a. -i)) (a, yi + (a)))
for some ee (ax) such that (a{(a)) | S st. This leads to an additional term of
E
- (2= u) TE, (at (a))
< E
(xr u) T - c,,a,) - aa)(a, - 2.) TT)TE, - "xx - u)
- E
V (nr - u) 1 A (a(a))2(()) - at) xz.) Six (Iz w)
1 E
(x, u) u), (E (la - (z)(ar - =x) 1 (x, 4)
< E
Et (oe u) TS, H. - u)
$ E | ul|s;-'
Plugging into the proof of Lemma 20, we have
E
( (H
Ao , - 26 -
so
(v
d @log(T/0))
+ t
| -ulls,"
d logg
Log((T/))
E?
01
+
att
al
Other parts of the proof follow those in Lemma 20. Finally, we get
T
Bias
H.a
Uo 71 91
a4 |r, - u113 + 0
Σ d log(T/8)
Σ + 8T
T
2
a,t
t=l
35

---

algorithm (formally defined later) that still operates The Bonus term will not be affected, according to Lemma 23, we have
1 T
+ O L log (T/6)) + 57
Bonus s 2(d + 2)
Σ a2
au Il xe 13
1=1
The Penalty term will not be affected, according to Lemma 24, we have
F(U HEH F(H)
2d (T)
S
Tpr
Stability-1 term is also unchanged, as we assume that still lies [-1, 1] even under misspecifica- tion. We still have
Stability-1 So
87
The Stability-2 term will not be affected as long as 7/a S
According to Lemma 27, we have 64r
1
T
Stability-2 <
Σ
at + 8T
t=1
The Error term is also unaffected. We still have Error = 0(1)
Adding these terms together, the regret caused by bias and the negative term induced by bonus cancel out. We have
Reg O (log(T) d
T
I
d log(T/5)
as log (T/5)
T
Σ
(1) + an)
Σ
+
8T
'/r
arl
at
1=1
t=l
Recall that we pick 04
3/
_ 1/:
and 7tz This gives
Vd
64dv1+64 val
Reg = Odd (Tdd(TTlog(TT) + d lTg(T) + Vd=T) = / (dd])=og + VdeT)
where we assume d² < VT without loss of generality.
E.2 Unknown misspecification
In this subsection, requires knowledge on into an algorithm that achieves a similar regret bound without knowing e. Such procedure handle unknown misppeifiiatinn/ccrupion has appeared in several previous works [Foster et al., 2020, Wei et al., 2022], though we adopt the technique in Jin et al. [2023) to handle the adversarial case.
model selection technique to convert the algorithm in Appendix E. which
The idea here a black-box reduction which turns an algorithm that only deals with known e to one that handles unknown More specifically. the reduction has two layers. The bottom layer takes as input an arbitrary misspecification-rouu algorithm that operates under known (e.g., Algorithm 1), and outputs stable misspecification-robie
under known E. The top layer follows the standard Corral idea and takes as input a stable algorithm that operates under known e, and outputs algorithm that operates under unknown Below, explain these two layers of reduction in details.
Bottom Layer (from an Arbitrary Algorithm to Stable Algorithm) The input of the bottom layer is an arbitrary misspecification-roiii
algorithm, formally defined as: Definition 29. An algorithu is misspecificttion-rouss if it takes 0 as input, and achieves the following regret for any random stopping time t' < T and any policy u.
E
Σ (f(la) f((uA)))) -(((at)
SB aB[CvV + cz8)
Pr[e1, > 0 T
for problem-dependent and factors C1 2 1 and E131" 1 VrEr
36

---

Algorithm 3 STable Algorithm By Independent Learners and Instance SElection (STABILISE)
Input: and base algorithm satisfying Definition 29. Initialize: [log2 7 instances of the base algorithm ALG ALG floRa T), where ALG, is config- ured with the parameter
0 0- 2Tolog T + (log(T).
for 1 1, 1.2.....d do Receive Wt--
if we S + then play an arbitrary policy Te
continue (without updating any instances)
Let je be such that wy E (2 12-ji_1,2 2-11..
Let क.e be the policy suggested by ALGje-
Output Te-
If feedback is received, send it to ALGü, with probability 2 24 we
and discard it otherwise.
In our case, = (d log 7') and = O(v)). While the regret bound in Definition 29 might look cumbersome, is in fact fairly reasonable: if the guess 0 is not smaller than the true amount of &i:e' the regret should be of order VV' + vd0; otherwise, the regret bound vacuous since T is its largest possible value. The only extra requirement is that the algorithm needs to be anytime (i.e., the regret bound holds for any stopping time E'), but even this is known to be easily achievable by using a doubling trick over a fixed-time algorithm. It is then clear that Algorithm (together with doubling trick) indeed satisfies Definition 29.
As mentioned, the output of the bottom layer is a stable robust algorithm. To characterize stability, we follow Agarwal et [2017] and define a new learning protocol that abstracts the interaction between the output algorithm of the bottom layer and the master algorithm from the top layer:
Protocol 1. In every round f, before the learner makes decision, probability wy E [o, 1] is revealed to the learner. After making a decision, the learner sees the desired feedback from the environment with probability wt, and sees nothing with probability Wt.
One can convert any misspecificationnnrouun algorithm (defined in Definition 29) into stable misspecification-robuss algorithm (characterized in Theorem 30).
This conversion is achieved by procedure that called STABILISE (see Algorithm 3 for details). The high-level idea STABILISE is as follows. Noticing that the challenge when learning in Protocol I is that wi varies algorithm to deal with one possible discretized value, so that is learning in Protocol but with a fixed Wt, making it straightforward to bound its regret based on what it promises in Definition 29.
time, discretize the value of w, and instantiate one instance of the input
More concretely, STABILISE instantiates (logz 7') instances {ALG, } T of the input algorithm that satisfies Definition 29, each with different parameter 0j. Upon receiving w, from the environ- ment, it dispatches round t to the j-th instance where j is such that w, (2-j-1,2-)) "], and uses the policy generated by ALG, to interact with the environment (if w, S 7. simply ignore this round). Based on Protocol 1, the feedback for this round is received with probability wy. To equalize the probability of ALG, receiving feedback as mentioned the high-level idea, when the feedback is
actually obtained, STABILISE sends it ALG, only with probability 2 (and discards it other- wise). This way, every time ALG, is assigned to round, it always receives the desired feedback with probability wi 2-5-1 = 2 This equalization step allows us to use the original guarantee of the base algorithm (Definition 29) and run it as it is, without requiring it to perform extra importance weighting steps in Agarwal et al. [2017].
The choice of 03 is crucial in making sure that STABILISE only has ef regret overhead instead of :T Since ALG, only receives feedback with probability 2 j-j-1, the expected total misspeci- miinzelr
fication experiences is on the order of 2-1-1g7. Therefore, its input parameter 0, only needs to be of this order instead of the total amount of misspecification <T.
37

---

The formal guarantee of the conversion is stated in the following Theorem 30.
Theorem 30. If an algorithm is misspecification robust according to Deffmition 29 some constants (2), then Algorithm 3 ensures
S 50 RR c Pp + c2ET)
Reg
under Protocol I, where PT minue/Tr with dj = 0((c) - logT)
Proof of Theorem 30. Define indicators
9t.j = II E (2 (---1,2-11]
he.j [[AG receives the feedback for episode t}.
Now we consider the regret of ALG,. Notice that ALG, makes update only when geghe. 1. By guarantee of the base algorithm (Definition 29), we have
T
E
(felar) - fe(ux())))
T 0j
<
B
C1
Σ gaghis + e20g max His
Pr
Σ
giathes
Σ
T.
1S
(40)
We first bound the last term: Notice that [R(,,,, 19t5]] 2-1-1 ge. by Algorithm Therefore,
ge.s
T
2
t.. 1 Bhe = 2-111
e 22-5-2627
(41)
91. E Bhe 19 2-
Mi.j S 2-
(42)
By Freedman's inequality, with probability at least 1 72
Σ
Eig. hus
Eig,,EEhee, 99.5
T
<
2
(Et)
Eeh "9,,,, 19n log(T') + 4 log(T")
-=1
T
< 4
Σ
E
log(?)) + llg((T)
T
gt 13 1h + 8log(T)
(AM-GM inequality)
1=1
which gives
T Elh + (ogg(()) <2-'er++ log
Eignhhe hiss S 2
> 1=1
with probability at least
for using Eq. (41). Similarly,
T Σ tm1
heg < >
Ir. E(h,, + 8 (og((T)<221)) <2- + (log(T))
[=1
38

---

with probability at least
1 72.
Therefore, with probability at least 1 -
2
7
T
T
Σ
gishes
Σ
Eiggshes
$ 2 2 + 16 26 64 64 T
< ET + 4v 4 2- +
0j
Therefore, the last term Eq. (40) is bounded by 7rz T S 7. Next, we deal with other terms in Eq. (40). Again, by El 19 = -- gr.s Eq. (40) implies
T
T
2
2 2 E
((llaa)-((utt S E
2-1-1
Mr. + 020g max Ihi Σ
KS
T
which implies after rearranging:
(f((a.) fe(uth))gn)
E
C1
2 2-j-1
1
Σ 1=1
Ii.j +
22-j-1
c20j
max It.j 1ST
+
T2-5-1
2
T
2gen
T Tlog' T 2-1
2
E
C1
Wt
+ 402
ET +
+ log
max St.i 1ST
72-1-1¹
(using that when gr.j
2-
and the definition of 0,)
wy
Now, summing this inequality over all j E {0,,,...., [log, }. we get
T
E
Σ
(felas)
fa(ut1))1 -
Wi
}}
1
T Toog T minisT wi + e2 Na.Noog Mlog T
O
E
N
No2ST T + eo
+1)
w4
O
R
(ar (2)
T log(())p)
+ 02e7 c227log77) T)
where N < Olog T) is the number of ALG, that has been executed at least once.
On the other hand,
-
- Se(w Wt 1 TE (pr T
E
Combining the two parts and using the assumption C2 2 finishes the proof.
Unknown E) In this subsection, we use the algorithm that we construct in Theorem 30 as a base algorithm, and further construct an algorithm with vT + & regret under unknown e. The idea is run multiple base algorithms, each with different hypothesis on on top of them, run another multi-armed bandit algorithm to adaptively choose among them. The goal is to let the top-level bandit algorithm perform almost well the best base algorithm. This is the Corral idea outlined in Agarwal et al. [2017], Foster et al. [2020], Luo et al. [2022], and the algorithm is presented in Algorithm 4.
Top Layer (from Known
Theorem 31. Using an algorithm constructed in Theorem 30 as base algorithm, Algorithm ensures Reg O (
(4VTTlogg) log" T + GGET) without knowing e.
39

---

Algorithm 4 (A Variant of) Corral
Initialize: log-barrier algorithm with each arm being instance of algorithm satisfying the
guarantee in Theorem 30. The hypothesis on e'T' is set to 2 for arm (i = 1, M [log2 T))
Initialize: Pa, M, Vi.
for f 2....... do
Let
t-1
Wt argmin
W1
Σ
2r
r7)
log W/
WE mM
where 1e, VT
For all send Wess to instance Draw is Wt.
Execute a, output by instance is Receive the loss Zr,ú for action (whose expectation is fa())) and send it to instance i. Define for all
3,, = 21, =
Wei
Pt. min rst Wr,i
Tt = di (Vprit -VP--V-p
The top-level bandit algorithm is FTRL with log-barrier regularizer. We first state the standard regret bound of FTRL under log-barrier regularizer, whose proof can be found in, e.g., Theorem 7 of Wei and Luo [2018].
Lemma 32, The FTRL algorithm over convex subset ft of the (M 1)-dimensional simplex A (MM):
f-1
M
argmin
w. e
log
Wi
ensures for all ?
T
Mlog
M
Σ
w
+ 1 Σ Σ
n
t=1
t=1 i=1
as long as leadl < for all i,
Proof of Theorem 31. The Corral algorithm is essential FTRL with log-barrier regularizer. To apply Lemma 32, we first verify the condition 1e,, < where l,, = 2,,5 Tt.i. By our choice of 7)
1 me,,l2a, S 122, S 7' mWe.see = ncc VTuis ( (ppri 1.)
(because & 2 1)
40

---

The right- hand side of the last equality is non-zero only when Pe.: > Pt-1,6, implying that Pt, Therefore, further bound by
1
1
T S nnd nNIVT VT
(VPt.
1,
Pt.
VP
= =nd VT
Peç
1
S n
1 for a b 0)
1,
VPr
Va
vb
va
(43)
ndVT
(pt.i 1)
(definition of m)
which can be combined to get the desired property ne,,, - re,al S 1 Hence, by the regret guarantee of log-barrier FTRL (Lemma 32), we have
Σ (zr, 21,5+)
M log
T
M
)
T
M We.frs Th.i
< O
+ ry
W
t (2t - r2,
+
17
where i" is the smallest i such that 2 upper bounds the true total misspecification amount eT. Bounding term1:
M
term
S 2m
w (
+r.
El
where
M
27
W 2,,
27
2 Hi = - O(I))
[=1 1=1
1=1 1=1
and
2m
3 < 4n Σ
(c 2
(continue from Eq. (43))
PP--1
VPt.
1=1
M
1
s AndfT
PP-11
VPt.
VP., I 1 and S an
< AncfTM
(telescoping and using Po. M and Pr.s 5 T)
Bounding term2:
T M
T
Σ
Σ rt.
term
Wri
1ml
M
SdvT
(4 V Vvpo.-.
/pt-1,
VPt,1
i=
(continue from Eq. (43) and using 1 - a In
(o((VTMM)
- -
41

---

Combining the two terms and using ?) = (3 ccVT-c//
M @elog T), we get
E
(f((a)) - 2450r)
= E
(1, - 22,0))
ci V 7 log T - E Pr.ss
(44)
On the other hand, by the guarantee of the base algorithm (Theorem 30) and that eT E (2" 122",, have
E
Σ (a.
f((uAt)) < ddVvr. ChTT.
(45)
Combining Eq. (44) and Eq. (45), we get
E
Σ
T
( f((AA)))
50 <0(4VTlog'T)
T cheT,
which finishes the proof.
Proof of Theorem 3. As shown in Appendix E.I, our Algorithm 1 can be adapted to satisfy Defini- tion 29 with 6 = (d log T) and C2 = @(va). By concatenation Theorem 30 and Theorem 31, conclude that there is algorithm that achieves
o ((c + +o)oTTlog T C2E' log T) =O(PVTlog' T + Vd doTllogT)
regret under unknown
F Analysis for Linear EXP4
Proof of Theorem 4. We first show that
Σ a Vt Σ T(Ar) 31 50 50(
In |11
Vx II: Reg(T)) 2 The magnitude of the loss is bounded by
ndT
(46)
16,,11
( T (Ae), H1 -
$ [|= || ||..ll
d
$ |T ||dll
I 2 2dn, then we have / S 1 and we can use the standard regret bound of exponential weights:
In III
VT E II:
Reg(T) S TT
17
E Easrop
PL
22
1
1=1
LaEET
Let H, Eanpi saa J.
Then we have H, 1 1 1-7
1 H.¹ and thus
Earope
Σ Piree 22
Europe
Σ Pes (T(Ai), H. ax)²
Tell
LTEll
Earrp Eampe [(a, H. aa)
(by the definition of Pt.a)
1
Tr (Hill, 11:l1, (H)t)) O(d).
7)3
42

---

Combining all proves Eq. (46). Next, show that there exists 0 E @ such that
T
- -x())) 31 1 < 011)
A~D
Σ
(47)
Let Ô be the closest element in O to Ei Mr. By the definition of θ and the assumption that ||ya|| S 1,
we have - >t Vt
Se. Thus, for any A.
Σ (T((A) (A))) D1 Σ (ma(A)) ( (A)) ++
(((A))=((AA)
where the last inequality is by the fact that Tz(A) = argmin uE a 0. Taking expectation over A gives Eq. (47).
log Finally, combining Eq. (46) and Eq, (47), choosing and 7 2dr 2dg
T
we get
Reg
ag Vt
T
Σ
(At) T 111
T
Σ
ag Ut
Σ
Ta (A()) 1/1
+ EAND
Σ aT (Tb(A) *AA))
y0
1=1
o (T+ + In((27)g)
+ noT +1)
"
O (d
finishing the proof.
G
Comparison with Dai et al. [2023] and Sherman et al. [2023]
state the exponential weight algorithm adopted by Luo et al. [2021], Dai et al. [2023], Sherman al. [2023] in Algorithm 5, which is an algorithm that we know to achieve the prior-art regret bound our setting (though they studied a more general MDP setting).
Their algorithm proceeds in epochs (indexed by k),, where every epoch consists of W rounds. The policy on action set in the k-th epoch defined as
(a exp -n (a úe (a()))
where Ut is the loss estimator for epoch k, and (a) is a (non-linear) bonus. In all W rounds in epoch i; the same policy is executed. The samples obtained in these W rounds are randomly divided into two halfs. One half used estimate the covariance matrix Eg,, and the other half is used to construct the loss estimator ON (see Line 5 of Algorithm 5).
43

---

Algorithm 5 Exponential weights with magnitude-reduced loss estimators
for k = 1, 1... T do
W
For all A, define
117 k (a 10 -0,-6,000 -b,(a))
exp
(a)
for all E A.
En'EA exp
-m (a' "e ba(a'))
Randomly partition {(k: 1)W + -,...,, kW} into two equal parts Thi Tg-
.. do for = (k - 1)W + 1,..., kWW
receive A,, sample at ~ Pk A.
and receive &..
Define
Σx BI +
Σ
ata
T
[Tk
BETR
ON Ex
arls
ITH
TET
(a) allal1s,
G.1 Regret Analysis Sketch
The regret analysis starts with a standard decomposition that similar to ours. We abuse the notation by defining = w (I= Dr.
Then
T/W
Reg- WE
Σ
Pk
Ao (a) (do,,n)
k=
T/W
T/W
WE
Σ k=
Pk
Ao
(aa. bala)) (urto be(ert)))
+ WE
Σ
Pk
Ao
(a)bb(a) bu (urtu)
EW-Res
T/W
+ WE
Pk
Ao (a)(a A
Ok)
Bias
Bounding the regret term follows the standard analysis of exponential weight:
T/W
T/W (a) 01 12 + n Σ
In Ao
EW-Reg < WE
7
Σ
Σ
Pk
Σ aEAD
PK
Ao
(a)bu(a)²
71
k=
AE
T/W
T/W
In Ao
a²
< WE
Σ
Σ
Pk Au
(a)a T
T5-1
--
n
17
8
k=
aE
where H2 = LEADD (aa) J. Then they the following fact to bound the stability term: as
long W > d it holds with high probability that ΣS1 H2 E 3 2 Thus EW-Reg can be zr,
44

---

further bounded by
T/W
In Aul
az B
EW-Reg S W
Σ
Σ
Pk
Ao
(a)llal
+
11
W
"1
aEADo
W In (Apl
+ qd' + 1/
"
By the definition of the bonus function by, it holds that
T/W
T/W
Bonus WE
Σ
Σ Pk
(a)laals
WE
1 I|s
k= aE
R=1
Finally, the bias term can be bounded as follows:
T/W
Bias WE
Pk (a)(a- - uAO)T(UX Ex HayK)
T/W
WE
Σ
pk (a) ( (Ex Hx)DR
k=1
T/W
< WW
Σ
Pk
Ao
(a)lla
u 1|, 11(Ex Ha)wells,
The bias here has a similar form as in our case. They use the following fact to bound the bias: as long W 2 32, it holds that ||[E Ha)uulls, /3d. Therefore, the bias can further be upper bounded by
T/W Σ
T/W
Bias S WE
Σ pt (a)laals, + B
| Ao ||ا
aεAo
Combining the three parts, get that the overall regret is of order
W In |ul + ndT n a + W(a 3dd)
T/W
T/W
Σ Σ
oo (a)llallss
W( a)
Σ
||
B
aE.Ao
Choosing s /Bd, we further bound it by
T/W
W In |oal
E
+ ndT + W
3d Σ
Σ
Ph (a)laalls
17
k= aEAD
T/W
W Au
< E
+ +ndT + W
3d
Pk
Ao
(a)llal
ae.Ao
W In An
+ +nd + VBdT.
"
Recall the constraint W
Choosing W /
gives
dn [Aul
ndT BBT
(48)
which gives d(In (Aol) 1 with the optimally chosen 7) and B.
45

---

Remark Due to the restrictions on the magnitude of the loss estimator required by the exponential weight algorithm, there is actually another constraint S 1, which makes Eq. (48) be diIn |AAo] () 7 at best. This is exactly the bound obtained by Sherman et al. [2023]. A more sophisticated way to construct ýk developed by Dai et al. [2023] removes this additional requirement and allows bound of d((n Aol)) + The sub-optimal bound 7 reported in Dai et al. [2023] is due to issues related to MDPs, which are not presented in the contextual bandit case here.
46


Reviews:
[{"review_id": "UsxJt26Tlx", "reviewer": "Reviewer_He1a", "summary": "This paper studied the contextual bandits with i.i.d. contexts and adversarial linear loss functions without simulators and proposed a follow-the-regularized-leader with log-determinant  barrier (Logdet-FTRL) algorithm with a carefully designed covariance matrix estimator that is computationally efficient given small contexts set and achieves order-optimal (in T) regret \\tilde{O}(d^2 \\sqrt{T}). Previous algorithms achieving \\sqrt{T} regret either require the knolwedge of contexts distribution or a simulator from which the learner can learn the contexts distribution by drawing free i.i.d. contexts. The proposed algorithm estimates the key covariance matrix via previously observes contexts with centralization and ridge regularizer. \n\nThe setting contains stochastic sleeping bandits as special case and the proposed algorithm  answers the open problem in stochastic sleeping bandits affirmtively. A computationally inefficient algorithm that achieves regret with improved d factor is also proposed. ", "questions": "Minor typos:\nLine 164, has been taken\nThe second equality between line 796 and line 797, U^{\\Ac_0} instead of \\bar{U}^{\\Ac_0}.", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The analysis is novel and the contribution is significant to linear adversarial bandits with i.i.d. contexts without simulator. \nMultiple related scenarios and extentions are discussed. \nI went over the proofs of the main regret analysis in App. D and several technical lemmas. The proofs are sound to me.", "weaknesses": "I do not see perticular weaknesses of the current version. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the support and valuable feedback. We have changed the typos you mentioned in our new version."}, {"review_id": "YhewGnYsuE", "reviewer": "Reviewer_V7BF", "summary": "Summary: \nThis paper presents a near-optimal computationally efficient simulator-free algorithm in contextual bandits setting with i.i.d contexts and adversarial reward functions. Most of the past work on this setting either requires a simulator that allows them to draw a large number of contexts from a distribution, or is computationally inefficient. Existing algorithms that do not require a simulator and are computationally efficient only achieve a regret of O(T^{5/6}). This work greatly improves the dependence on T, achieving a regret of O(d^2 \\sqrt{T}), while still computationally efficient without a simulator. Their algorithm is based on FTRL with a log-determinant barrier. They also present an algorithm that improves the dependence on d, achieving a regret of O(d \\sqrt{T}) but is only computationally efficient for a finite policy class. \n", "questions": "1. To analyze the first term |\\hat{Sigma}_t - H_ty_t|_hat{Sigma}_t^{-1} in line 242 did you need to use any kind of matrix concentration? If so, did you need control of the minimal eigenvalue of H_t? If not, how were you able to avoid it?\n2. The linear EXP4 algorithm looks very much similar to the original EXP4 algorithm. Could you provide more explanation of why we cannot directly use other computationally inefficient benchmark algorithms to get the same regret, i.e. why it’s necessary to present and prove linear EXP4? \n3. The computationally efficient algorithm, Algorithm 1, achieves a O(d^2\\sqrt{T}) regret while having a squared dependence on d; while the algorithm that achieves O(d\\sqrt{T}) regret is optimal but computationally inefficient. Do you believe algorithm 1 could achieve a O(d\\sqrt(T)) regret?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I think this paper makes a solid theoretical contribution to the field. The improvement from O(T^{5/6}) to O(\\sqrt{T}) is substantial and simulator-free computationally efficient algorithms are important. The authors exploit the algorithmic ideas of ZL22, the ghost sample trick of NO20, along with novel analysis to provide an improved regret bound. I am slightly concerned about the originality of the algorithmic approach - but this is made up for with the improved analysis and improved regret bound \n\nThe paper was clearly well written and the contributions clearly stated. I enjoyed how the authors decomposed the regret and the analysis of the estimator in 3.2-3.4.\n", "weaknesses": "The main weakness is that the paper was challenging to read inplaces, especially for readers not already familiar with the ideas of ZL22. There were other places where a bit of extra detail could have helped the exposition greatly. I have tried to remark on these in the list below.\n\nRemarks/Comments\n1. On bottom of page 5, you mention the loss in the “original space”, can you explain precisely what that loss is? For readers not familiar with ZL22, Line 2 in the algorithm may be opaque - in particular the sequence H_s^{-1} is chosen to control the bias. Moving a bit of the discussion from 3.4/3.5 up - or even simply remarking that it will be explained later may help.\n2. The discussion on line 188-189 is similar to 193-194. You can drop one.\n3. In equation 2, you use a \\hat{Sigma} - however the point of this equations seems to be that Sigma is known! Maybe remove the empirical hat?\n4. Is it possible to elaborate a bit more in the paper how your methods “surpass those in [DLWZ23,SKM23]” as described in line 246?\n5. \\gamma_t should be defined in algorithm for readability\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for providing suggestions on improving the readability of the paper. We will incorporate them in the final version. \n\n$\\textbf{Q1:}$ To control the term $||(\\hat{\\Sigma}_t - H_t) y_t||\\_{\\hat{\\Sigma}_t^{-1}}$, did you need to use any kind of matrix concentration? If so, did you need control of the minimal eigenvalue of $H_t$? If not, how were you able to avoid it?\n\n$\\textbf{Reply: }$ We elaborate on the main idea of our proof here and more detail can be found in the proof of Lemma 14 in the full version of our paper. To control this term, we do not use any off-the-shelf matrix concentration inequality. Instead, we expand $\\text{Tr}\\left((\\hat{\\Sigma}_t - H_t)^\\top\\hat{\\Sigma}_t^{-1}(\\hat{\\Sigma}_t - H_t)\\right)$ by its definition and use the standard Bernstein’s inequality for scalars to handle it. \n\nMore details are below. First, we show $\\text{Tr}\\left((\\hat{\\Sigma}\\_t - H_t)^\\top\\hat{\\Sigma}\\_t^{-1}(\\hat{\\Sigma}\\_t - H_t)\\right) \\leq 8\\text{Tr}\\left((\\hat{\\Sigma}\\_t - H_t)^\\top(H_t + \\beta_t I)^{-1}(\\hat{\\Sigma}\\_t - H_t)\\right)$ where $\\beta_t=\\Theta(\\text{poly}(d)/t)$ by some simple concentration inequality. Below, for simplicity, we assume that $H_t$ is a diagonal matrix (otherwise, we can diagonalize it as in the formal proof of Lemma 14). Recall that $\\hat{\\Sigma}\\_t$ is equal to  $\\beta_t I$ plus a covariance matrix estimated from the empirical context distribution. Therefore, we have $\\hat{\\Sigma}\\_t - H_t = \\Delta_t + \\beta_t I$, where $\\Delta_t$ is the covariance matrix estimation error related to the difference between the empirical and the true context distribution at time $t$. By direct expansion and the assumption that $H_t$ is diagonal, we have $\\text{Tr}\\left((\\hat{\\Sigma}\\_t - H_t)^\\top(H_t + \\beta_t I)^{-1}(\\hat{\\Sigma}\\_t - H_t)\\right)=\\sum_{i=1}^d \\left(\\frac{(\\Delta_t(i,i) + \\beta_t)^2}{H_t(i) + \\beta_t} +  \\sum_{j \\neq  i} \\frac{\\Delta_t(i,j)^2}{H_t(i) + \\beta_t}\\right)\\leq 2\\sum_{i=1}^d \\sum_{j=1}^d \\frac{\\Delta_t(i,j)^2}{H_t(i)+\\beta_t} + 2d\\beta_t$, where $\\Delta_t(i,j)$ is the $(i,j)$-th entry of $\\Delta_t$ and $H_t(i)$ is the $(i,i)$-th entry of $H_t$.\n\n\nFinally, we argue that with high probability $\\sum_{j=1}^d \\Delta_t(i,j)^2\\leq \\text{poly}(d)\\times\\tilde{O}(\\frac{H_t(i)}{t} + \\frac{1}{t^2})$, which, when combined with the argument above, gives the desired bound. The key calculations for this inequality are in Line 610-620. To establish this inequality, we have to use the fact that $\\Delta_t(i,j)$ is an average of a martingale difference sequence and so we can use Bernstein's inequality to relate it to the variance of individual terms.  On the other hand, $H_t(i)$ is related to the variance of the individual terms in this martingale difference sequence. The inequality can be shown by combining these two components. \n\nFrom a high level, the key we are able to avoid the minimal eigenvalue of $H_t$ is the fact that in those directions where $H_t + \\beta_t I$ has small eigenvalues, the error term $\\hat{\\Sigma}_t- H_t=\\Delta_t + \\beta_t I$ is also small.  \n\n\n$\\textbf{Q2:}$ The linear EXP4 algorithm looks very much similar to the original EXP4 algorithm. Could you provide more explanation of why we cannot directly use other computationally inefficient benchmark algorithms to get the same regret, i.e. why it’s necessary to present and prove linear EXP4?\n\n$\\textbf{Reply:}$ We want to emphasize that we do not claim linear EXP4 as an important contribution of this paper, as this is indeed a fairly straightforward adaptation of the classical EXP4. \nVanilla EXP4 and all benchmark algorithms we are aware of would suffer regret of $\\sqrt{KT\\ln(|\\Pi|)}$, where $|\\Pi|=\\Theta(T^d)$ is the $1/T$-net of policies and $K$ the maximal number of actions. Since we want to handle the setting $K\\gg d$, we have to present a modification that utilizes the linear feedback structure of the actions.\n\n\n$\\textbf{Q3:}$ Algorithm 1 achieves a $O(d^2\\sqrt{T})$ regret. Do you believe algorithm 1 could achieve a $O(d\\sqrt{T})$ regret?\n\n$\\textbf{Reply: }$ We are unsure whether the additional $d$ dependence can be removed. The additional $d$ dependence comes from a union bound over $(1/\\epsilon)^{O(d^2)}$ policies when dealing with the covariance matrix estimation error, since the policy used by the algorithm is parameterized by $O(d^2)$ parameters. Due to the strong dependency between the contexts received in previous rounds and the the current policy, we do not believe that such a union bound can be avoided. We suspect that it might be possible to improve the bound to $\\tilde{O}(\\sqrt{d^3T})$. Recall that the reason we have $(1/\\epsilon)^{O(d^2)}$ is because we lift the problem to $(d+1)^2$ dimension and the bonus term is a $(d+1)\\times(d+1)$ matrix. However, there are other ways of imposing bonus in $\\textit{linear bandits}$ that allows the bonus term to be in $(d+1)$ dimension ([LLWZ20] and [ZL22]), which potentially only requires a union bound over $(1/\\epsilon)^{O(d)}$ policies. To achieve the optimal $\\tilde{O}(d\\sqrt{T})$ bound, we might need a very different algorithm design that does not rely on concentration arguments. \n\n[DLWZ23] Yan Dai, Haipeng Luo, Chen-Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. arXiv preprint arXiv:2301.12942,374 2023. \n\n[LLWZ20] Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. NeurIPS 2020. \n\n[ZL22] Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. COLT 2022. "}, {"review_id": "owxlhT9atX", "reviewer": "Reviewer_f8CU", "summary": "The paper studies an adversarial linear bandit problem. At each round, the adversary selects a hidden loss vector $y_t$, the environment 'stochastically generates' an action set $A_t$, and the learner chooses an action in the action set. The learner is able to observe noisy loss $\\ip{y_t}{a_t}$.", "questions": "First, I did not fully understand the problem setting studied in this paper and would need some clarifications. \n\n1. In this work context vectors = actions, I have never seen this formulation in previous literature. The action set $A_t$ is generated from the distribution $D$. What exactly is distribution $D$? Is it defined over the power set of $B_2^d$? What assumption do you make on the size of $A_t$? \n\n2. The formulation does not align with previous work (e.g. NO20). In NO20, they assume the action is chosen by an adversary for each arm in $[K]$ (action for arm $a$ is $\\theta_{t,a}$), and the context $x_t$ is drawn from (known) distribution and revealed to the learner. The learner chooses one of the arms and observes the noisy loss centered at ${x_t^T}\\cdot{\\theta_{t, A_t}}$. Regret is compared to best policy, which is mapping from context to action. \nThis current work assumes the loss vector is chosen adversarially and the action set is drawn 'stochastically' (which I don't completely understand, see point above. ) Regret is compared to best policy, which is mapping from action set to a distribution over action set. \nGiven the different formulations, I do not believe the claims in this work, stating they improve over prior work, are accurate. \n\nBased on my understanding of this work, if the action set $A_t$ were constant each round, then this is the bandit linear optimization problem, as in (competing in the dark, abernethy et al. ). Hence this paper really seems to be solving a bandit linear optimization problem where the action set is changing each round, and not the 'adversarial linear contextual bandit' problem as introduced in the intro section.", "limitations": "The author did not address limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Update after rebuttal. This paper proposed an optimal algorithm for the adversarial contextual linear bandit problem. The algorithm consists of OMD with logdet barrier as well as the lifting technique.", "weaknesses": "Update after rebuttal. \nCan dependence on d be improved?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for raising concerns about the clarity of the setting. We will clarify them in the new version. \n\n$\\textbf{Q1:}$ In this work context vectors = actions, I have never seen this formulation in previous literature. The action set $A_t$ is generated from the distribution $D$. What exactly is the distribution $D$? Is it defined over the power set of $B_2^d$? What assumption do you make on the size of $A_t$?\n\n\n$\\textbf{Reply:}$ Condensing the context into a time-varying action set is common in the literature of contextual linear bandits. See page 239 of [LS20], page 1 of [HYF23], or other previous works [CLRS11, LWCZ21] that also take this view. Furthermore, the alternative linear contextual bandit setting of [NO20] reduces to our setting as well (see the response for Q2).\n$D$ is a distribution over subsets of $B_2^d$. In other words, $D$ is a distribution over the power set of $B_2^d$. We only assume $A_t \\subset B_2^d$ without any additional assumption on its size, so it can be infinite. The reviewer can also refer to [HYF23] for more characterization on $D$, which is the same as ours.   \n\n[LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.\n\n[HYF23] Osama Hanna, Lin Yang, Christina Fragouli. Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms. COLT 2023.\n\n[CLRS11] Wei Chu, Lihong Li, Lev Reyzin, Robert Schapire. Contextual Bandits with Linear Payoff Functions. AISTAT 2011.  \n\n[LWCZ21] Yingkai Li, Yining Wang, Xi Chen, Yuan Zhou. Tight Regret Bounds for Infinite-armed Linear Contextual Bandits. AISTAT 2021. \n\n\n$\\textbf{Q2:}$ The formulation does not align with previous work (e.g. NO20). I do not believe the claims in this work, stating they improve over prior work, are accurate.\n\n$\\textbf{Reply: }$ In fact, the setting of [NO20] is a special case of our setting. [NO20] assume that at every round $t$, the environment picks an adversarial loss vector $\\theta_{t,a}$ for any action $a \\in [K]$, and a random context $X_t\\in\\mathbb{R}^d$ is drawn from a fixed distribution. The learner chooses an action $a_t\\in[K]$ based on $X_t$ and the final observed loss is $\\ell_t = \\langle X_t, \\theta_{t,a_t} \\rangle$. To convert this to our formulation, define $\\theta_t = \\left[\\theta_{t,1}, \\cdots, \\theta_{t,K}\\right] \\in \\mathbb{R}^{d \\times K}$. Then we have $\\ell_t = \\langle X_t, \\theta_{t,a_t} \\rangle = X_t^\\top \\theta_t e_{a_t} = \\text{Tr}(e_{a_t}X_t^\\top \\theta_t)  = \\langle X_te_{a_t}^\\top,  \\theta_t \\rangle = \\langle \\text{Vec}(X_te_{a_t}^\\top),  \\text{Vec}(\\theta_t) \\rangle $ where $\\text{Vec}(X)$ is the column vector generating by stacking the columns of matrix $X$, and $e_i$ is the $i$-th standard basis. Then by defining the action set $A_t = ${$\\text{Vec}(X_te_{i}^\\top), i \\in [K]$} and adversarial loss vector $y_t =  \\text{Vec}(\\theta_t)$, their setting becomes a special case of our setting with dimension $dK$. Our formulation is more flexible than that in [NO20] because in their formulation, the number of parameters always scales with the number of actions (i.e., $d\\times K$), while in our formulation, the number of parameters is always $d$. Thus, our formulation is able to capture problems with large number of actions but small intrinsic dimension, while theirs cannot. \n\nBased on the discussion above, if we apply our algorithm to their problem, our $d$ becomes $dK$, and the regret bound is $\\tilde{\\mathcal{O}}\\left(d^2K^2\\sqrt{T}\\right)$, which has worse $d$ and $K$ dependences than [NO20], but removes an inverse smallest eigenvalue of the covariance matrix in their bound.  However, we emphasize that our goal is not to improve the regret bound in [NO20], but to remove strong assumptions made in previous work on the knowledge of context distribution. Actually, as discussed in the introduction, [DLWZ23] has already strictly improved [NO20] (simultaneously improving the regret bound, considering a more general setting, and weakening assumptions), and got a near-optimal bound $\\tilde{\\mathcal{O}}\\left(\\sqrt{dT\\log K}\\right)$ (or $\\tilde{O}(\\sqrt{dKT\\log K})$ in the formulation of [NO20]) with simulators. Therefore, in Table 1, we only compare our results with [DLWZ23]. \n\n [DLWZ23] Yan Dai, Haipeng Luo, Chen-Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. arXiv preprint arXiv:2301.12942,374 2023."}, {"review_id": "JdGVnrfhDH", "reviewer": "Reviewer_6s4U", "summary": "The paper addresses the problem of adversarial linear contextual bandits, where loss vectors are selected adversarially and the context for each round is drawn from a fixed distribution; traditional approaches require access to a simulator for generating free i.i.d. contexts or achieve a sub-optimal regret no better than $\\widetilde O(T^{5/6})$.\n\nThe authors significantly improve on these methods by achieving a regret of $\\widetilde O(\\sqrt{T})$ without the need for a simulator, while maintaining computational efficiency when the action set per round is small. The results affirmatively answer an open question about the existence of a polynomial-time algorithm with $\\mathrm{poly}(d)\\sqrt{T}$ regret. The approach allows for the case where the loss is linear up to an additive misspecification error, showing a near-optimal dependence on the magnitude of this error. \n\nThe paper also presents a computationally inefficient algorithm that provides an improved $\\widetilde O(d\\sqrt{T})$ regret without a simulator, expanding on the EXP4 algorithm.", "questions": "How might these estimators handle high-dimensional data? Are there potential ways to improve their performance in such scenarios in future work?\n\nCould the presented estimators be generalized to other types of bandit problems, such as non-linear contextual bandit problems?", "limitations": "The authors adequately addressed the limitations as I could tell.\n\n\n\n==================================================\n\nPost-Rebuttal:\n\nI appreciate the response from the authors, and it addresses most of my concerns. Though I still believe the empirical experiments and the comparisons to other existing methods should be an important part of the work, this is still a strong theoretical paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents an algorithm that innovatively instantiates an individual Follow-The-Regularized-Leader (FTRL) algorithm on each action set. This development has a wide range of implications for fields. It promises more efficient and effective optimization algorithms in the face of adversarial environments.\n\nOne of the major strengths of the paper lies in the construction of loss estimators and feature covariance matrix estimators, especially in challenging situations where the learner has no knowledge about the context distribution and there is no simulator available.\n\nThe paper manages to achieve an improved bound on the bias. The techniques used surpass those used in previous studies [DLWZ23, SKM23], leading to a significant improvement in the algorithm's performance and making it more effective in practice.\n\nThe introduction of feature centralization is also a notable strength. By centralizing the features by $\\hat x_t$, an estimation of the mean features under the current policy, the bias $y_t - \\hat y_t$ appears in a nice form that can be compensated by a bonus term. This approach provides an elegant solution to handling bias in the estimator.\n\nThe paper successfully handles the issue of strong dependence between the policy and the empirical context distribution, Dˆt, which typically rules out canonical concentration bounds.\n\nThe paper addresses the need for high efficiency in reusing the context samples, which is a challenging problem often not adequately handled by existing methods.", "weaknesses": "A notable weakness of the paper is the absence of empirical or numerical experiments to validate the theoretical results. Without practical implementation and testing of the proposed estimators on different datasets, it becomes difficult to assess their efficacy and performance. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable feedback. We agree that empirical validation is important to prove the efficacy of the algorithm. It will be an important future work to experimentally compare our algorithm to other existing linear contextual bandit algorithms.  \n\n$\\textbf{Q1:}$ How might these estimators handle high-dimensional data? Are there potential ways to improve their performance in such scenarios in future work?\n\n$\\textbf{Reply:}$ We do not have any constraint on the dimension $d$, so our algorithm can also be applied when $d$ is large. In general, a $\\text{poly}(d)$ regret is inevitable. In some special case, a $\\text{poly}(d)$ regret can be avoided. For example, for the case where the number of actions and the size of the policy set are small, the algorithm in [SLKS16] can be used to achieve a regret of $\\tilde{\\mathcal{O}}\\left((\\log|\\Pi|)^{\\frac{1}{3}}(|\\mathcal{A}|T)^{\\frac{2}{3}}\\right)$, where $|\\mathcal{A}|$ and $|\\Pi|$ are the sizes of the action set and the policy set, respectively. Their algorithm relies on simulators though, and it would be an interesting direction to try to remove it. \n\n[SLKS16] Vasilis Syrgkanis, Haipeng Luo,Akshay Krishnamurthy, and Robert E Schapire. Improved regret bounds for oracle-based adversarial contextual bandits. Advances in Neural Information Processing Systems, 29, 2016.\n\n\n$\\textbf{Q2:}$ Could the presented estimators be generalized to other types of bandit problems, such as non-linear contextual bandit problems?\n\n$\\textbf{Reply:}$ The current algorithmic framework, including the estimator and the regularizer designs, is heavily tailored for the linear case. To generalize the problem to the non-linear case, we notice that even for the generalized linear bandit *without context*, there is no known computationally efficient algorithm that handles adversarial losses and has a regret bound of $\\text{poly}(d)\\times o(T)$. The difficulty exactly lies in the the construction of an unbiased low-dimensional loss estimator that can be shared among actions. The study of an efficient algorithm for particular non-linear bandit problems (e.g., generalized linear bandits) with adversarial loss is indeed an interesting direction. \n"}]

Author rebuttal:

Meta-review: All reviewers agree that this is a good theoretical contribution to the bandit literature with a good motivation.
Decision: Accept (poster)