Best-of-Both-Worlds Linear Contextual Bandits
Authors: Masahiro Kato
Shinji Ito
Venue: Accepted by TMLR ()

Abstract: This study investigates the problem of $K$-armed linear contextual bandits, an instance of the multi-armed bandit problem, under an adversarial corruption. At each round, a decision-maker observes an independent and identically distributed context and then selects an arm based on the context and past observations. After selecting an arm, the decision-maker incurs a loss corresponding to the selected arm. The decision-maker aims to minimize the cumulative loss over the trial. The goal of this study is to develop a strategy that is effective in both stochastic and adversarial environments, with theoretical guarantees. We first formulate the problem by introducing a novel setting of bandits with adversarial corruption, referred to as the contextual adversarial regime with a self-bounding constraint. We assume linear models for the relationship between the loss and the context. Then, we propose a strategy that extends the {\tt RealLinExp3} by \citet{Neu2020} and the Follow-The-Regularized-Leader (FTRL). The regret of our proposed algorithm is shown to be upper-bounded by $O\left(\min\left\{\frac{(\log(T))^3}{\Delta_{*}} + \sqrt{\frac{C(\log(T))^3}{\Delta_{*}}},\ \ \sqrt{T}(\log(T))^2\right\}\right)$, where $T \in\mathbb{N}$ is the number of rounds, $\Delta_{*} > 0$ is the constant minimum gap between the best and suboptimal arms for any context, and $C\in[0, T] $ is an adversarial corruption parameter. This regret upper bound implies $O\left(\frac{(\log(T))^3}{\Delta_{*}}\right)$ in a stochastic environment and by $O\left( \sqrt{T}(\log(T))^2\right)$ in an adversarial environment. We refer to our strategy as the {\tt Best-of-Both-Worlds (BoBW) RealFTRL}, due to its theoretical guarantees in both stochastic and adversarial regimes.

Published in Transactions on Machine Learning Research (06/2024)
Best-of-Both- Linear Contextual Bandits
Masahiro Kato
The University of Tokyo
Shinji Ito
shinji@misst..u-tokkpo
The University of Tokyo RIKEN AIP
NEC Corporation (affiliation upon submission)
Reviewed on OpenReview: Attps: // openreview. net/ pormfo id= a...aaAANN..leeeeerrr...
Abstract
This study investigates the problem of K-armed linear contextual bandits, instance of the multi-armed bandit problem, under an ad adversarial corruption. At each round, decision- maker observes an independent and identically distributed context and then selects an arm based on the context and past obscrvations. After selecting an arm, the decision-maker incurs a loss corresponding to the selected arm. The decision-maker aims to minimize the cumulative loss over the trial. The goal of this study is to develop strategy that effective in both stochastic and adversarial enviromments, with theoretical guarantees. We first formulate the problem by introducing novel setting of bandits with adversarial corruption, referred to as the contextual ad adversarial regime with a self-bounding constraint. We assume linear models for the relationship between the loss and the context. Then, we propose a strategy that extends the RealLinExp3 by Neu & Olkhovskaya (2020) and the Follow-Tha Hatee-Rgguarizee--Leee (FTRL). The regret of our proposed algorithm shown to be upper-bounded by min log
A. + V Clogg(T) A.AA VTlog((T))) where T TED N the
number of rounds, A, > 0 is the constant minimum gap between the best and suboptimal arms for any context, and C E [0, is an adversarial corruption parameter. This regret upper bound implies (Tg in a stochastic environment and by O (VTlog?(T) in an (BoBW)
A. adversarial environment. We refer to our strategy as the Best-of-Both-Wae RealFTRL, due its theoretical guarantees in both stochastic and adversarial regimes.
1 Introduction
This study considers minimizing the cumulative regret in the multi-armed bandit (MAB) problem with contextual information. The MAB problem is formulation of sequential decision-making, In this study, we develop an algorithm that utilizes side information called contextual information. We focus on linear contextual bandits and aim to design an algorithm that performs well both stochastic and adversarial environments.
In problem setting of contextual bandits, perision-maker observes an independent and identically distributed (ii.d.) context each round, draws an arm accordingly, and incurs loss associated with the chosen arm. Additionally, we assume lincar models between the loss and contexts, which is known as the linear contextual bandit problem. The contextual bandit problem is widely studied in fields such as sequential treatment allocation (Tewari & Murphy 2017), personalized recommendations (Beygelzimer et al. 2011), and online advertising (Li al.] 2010)) Basod on these demands, existing studics explore the methods. For example, Abe & Long (1999) studies linear contextual bandits. Li al. (2021) provides lower bounds. There
numerous other studies in this field (Chen et al. 2020 Ding et al. 2022

---

Published in Transactions on Machine Learning Research (06/2024)
The settings of linear contextual bandits are divided into stochastic, with fixed contextual and loss distri- butions, and adversarial environments, with fixed contexts but adversarially chosen losses Most existing
studies focus on algorithms for either stochastic (Abe & Long, 1999 Rusmevichientong & Tsitsiklis 2010;
Chu et al. 2011 Abbasi-yadkori et al., 2011 Lattimore & Szepesvari 2017) or adversarial linear contextual
bandits Neu Olkhovskaya 2020).
Thus, optimal algorithms typically differ between the stochastic and adversarial environments. However, cost-of-both-worldee framework exists, aiming for algorithms that are competent in both stochastic and
adversarial environments (Bubeck & Slivkins, 2012 Seldin & Slivkins 2014 Auer & Chiang 2016 Seldin &
Lugosi 2017
Zimmert & Scldin [021] Lee et al. 2021.. Building on existing work, we propose best-of- borh-worlds algorithm for stochastic and adversarial linear contextual bandits.
1.1 Main Contribution
In Section 2 we first introduce the setting of linear contextual bandits with adversarial corruption by defining the linear contextual adversarial regime with a self- luff-boundig constraint. This setting is a generalization of the adversarial regime with a self-bounding constraint proposed by Zimmert & Seldin 2021 Under this regime, we bridge the stochastic and adversarial environments by an adversarial corruption parameter C' 0, where C corresponds to stochastic environment and C corresponds to an adversarial environment.
Then, in Section inspired by the RealLinEXP3 proposed by Neu & Olkhovskaya 2020 for adversarial con- texts, our algorithm uses the Pollow-the- Rollow--ee--eeguuariieeee enviromment. Our algorithm design also follows existing studies in best-of- bottooo-oooo-oeoooe wotbbbothhwwllree worlds (BoBW) studies, such as Ito et al. 2022). We refer to our algorithm as the BoBW- RealFFRL..
(FTRL) approach to adapl well to the stochastic
In Section
we show the following upper bound of the BoBW-RealFTRL.
K log(T) (Iog(T)
log((T)
CK (Klog(T) (log(T) + d dllo(())) log((TT)))))
0 min
A.
A.
(og(K))TKKog()) (log(T) + d dloog( ()) log (KTg
where 7' the number of rounds, d the dimension of a context, and K is the number of arms, when there exists constant minimum gap A. between the conditional expected rewards of the best and suboptimal arms for any context when consider a stochastic enviromment. Note that this regret upper bound holds both for stochastic and adversarial environments. As a specific case, under a stochastic environment, the regret upper bound is given as
(Klog((T K log(T) (Tog(T) + dloog(K) log( log KTT)
A
When there does not exist such gap A., we show that the regret upper bound is given as (Vlog( log(T) (Tog(T) + dlog(K)) log(
Note that our regret upper bound is O min
(Tr
+
(T) A.
T log (m)) when focusing on the or-
4.
der with respect to T. Furthermore, in a stochastic environment, the regret is upper bounded by O (log2 and in an adversarial environment, the regret is upper bound by O (VTlog
A.
We define adversarial linear contextual bandits different ways. For example, there studies that consider contextual bandits with adversarial contexts and fixed losses (Chu al. 2011 Abbasi-yadkori et al. 2011). On the other band, several
studics address contextual bandits with adversarial contexts and adversarial losses (Kanade & Steinke 2014 Hazan et al.
2016). This study only focuses contextual handits with i.i.d. contexts and adversarial losses, which
studied by
Rakhlin & Sridharan) 2016) and Syrgkanis al. (016).
2

---

Published in Transactions on Machine Learning Research (06/2024)
In summary, we contribute to the field of linear contextual bandits by providing BoBW algorithm. Our proposed algorithm and theoretical analysis draw partial inspiration from New & Olkhovskaya (2020) and Ito et al. (2022). However, we introduce several novel techniques to adapt these methodologies to our setting, such as specifying adaptation weights based on an cstimation algorithm for the covariance matrix of contexts. It. is important to nole that our primary contribution lies not in theoretical advancements but in the proposition of novel algorithm tailored to a unique setting. Our study significantly enriches the domains of linear contextual bandits and BoBW algorithms.
1.2 Related Work
In adversarial bandits, the RealLinExp3, the algorithm proposed by Neu & Olkhovskaya (2020) yields
O KoT In Table 1 we compare our regret upper bounds with the upper bounds of Neu &
Olkhovskaya 2020).
Regret upper bounds in a stochastic setting are categorized into problem-dependent and problem-inddependent upper bounds, where the former utilizes some distributional information, such as the gap parameter A., lo bound the regret, while the latter does not. Additionally, problem- -epeedent regret upper bounds in the stochastic bandits depend on the margin condition characterized by parameter
[0, +oo] (for the detailed definition, see Remark 1. Our case with A, corresponds lo case with = +00. Note that in the adversarial bandits, the margin condition usually does not affect the upper bounds. Dani et al. 2008) proposes the ConfidenceBAll, and Abbasi-yadkori et al. (2011) proposes OFUL. They both present upper bound with and without the assumption of the existence of A As mentioned above, the regret upper bound under the assumption of the existence of A, corresponds to case with a = +00 the margin condition. In contrast, Goldenshluger & 'Zeevi (2013) Wang et al. 2018). and Bastani Bayati (2020) propose algorithm in case with = 1. Furthermore, Li al. (2021 propose the L (--ConfidenceBall based algorithm whose upper bound tightly depends on unknown a. Note that their setting of linear contextual bandits slightly differs from the one presented in Neu & Olkhovskaya (2020). While/Neu & Olkhovskaya (2020) considers a scenario where contexts remain constant across arms but the coefficients of linear models vary, other studies typically adopt a setting where each arm has its specific context, but the coefficients are the same. In this latter context, Abbasi--ydkorii et al. (201I) demonstrates that their OFUL algorithm achieves an O (d (T) A regret upper bound. It is important to note that due to these differing scttings, we do not compare compare their regret bounds ours directly and omit it from Table [
There are several related studies for linear contextual bandits with adversarial corruption, including Lykouris & Vassilvtiskii (2018). Gupta et al. (2019), Zhao et al. (2021) and He ct al. (2022). Lykouris & Vassilvtiskii (2018), Gupla el al. (2019), and Zhao el al. (2021) consider other corruption Trameworks characterized by constant C' E [0, TJ which is different but related to our linear contextual adversarial regime with self- bounding constraint. He et al. (2022) uses another constant Čt E [0, different but closely related to Ö. For the detailed definitions, see Remark 2 The essential difference between our and their settings is the existence of the gap A.. Furthermore, while our regret upper bound achieves the polylogarithnic order, those studics show roughly vT-order regret upper bounds. He et al. (022) presents Ô (dvK + ddt) regret
under an adversarial corruption characterized by constant C1
The use of the FTRL approach for adversarial linear bandits is also independently explored by Liu et al. 2023) to relax the assumption used in Neu & Olkhovskaya (2020). In addition to the difference in con- trnb while our algorithm utilizes the Shannon entropy in the regularization of the FTRL, Liu el al. willyield
(2023) employs the log-determinant barrier. We expect that combining these two methods will yield a BoBW algorithm with relaxed assumptions, and is future work.
To establish our BoBW regret bounds, we utilize the sell-bounding technique (Zimmert, & Seldin 2021 Wei & Luo 2018 which yields poly-logarithmic regret bounds in stochastic environments. This is achieved by integrating regret upper bounds that are contingent on the arm-selection distributions gr, and lower
'Regret upper hounds with the assumption the existence of A, are called problem-dependent.
3

---

Published in Transactions on Machine Learning Research (06/2024)
Table 1: Comparison of the regret. We compared the regret upper bound of our proposed BoBW-RealFTRL. with the RealLinExp3 Neu & Olkhovskaya 2020
Regret
Adversarial/Soochattie
Ours (BoBW-RealFTRL)
o min
D
V A. (lo((KTTTD)
CD
Both
A.
where D = K (Tg(T)
(log(T) + d dogg ()) log(KT)
0
(TTg())
Adversarial
D
(C==0) =0=)
Stochastic
A.
RealLinExp3
o (o(TT)KKH
Adversarial
bound known as self-bound constraints. The qedeepndent regret bounds are obtained using FTRL with a negative-entropy regularizer, which is also referred to as the exponential weight method.
Our approach includes an entropy-adaptive update rule for learning rates, originally developed for online learning in feedback graph contexts (Ito et al.) 2022). This strategy has been proven effective in providing BoBW guarantees for seponential-weiihtt-bssss lems, such as multi-armed bandits [Jin et al. 2023), partial monitoring (Tsuchiya et al. 2023a),, linear bandits (Kong et al.] 2023). episodic Markov Decision Processes (MDPs) (Dann et al. (023b)) and sparse multi-armed bandits (Tsuchiya et al., 2023b). However, common limitation of these results, stemming from the negative-entropy regularization, is the additional log factors in the regret bounds.
algorithms across various sequential decision- mabiinnnnakingg prob-
Our obtained regret upper bounds are not O(log(T)), and we assume the uniqueness of the optimal arm. A promising future direction to address these issues could be the exploration of alternative regularizers like Tsallis entropy. Utilizing such regularizers might allow us to lighten the regret upper bound and relax the assumption that the optimal arm unique. Zimmert & Seldin (2021) proposes the use of Tsallis entropy, and Masoudian & Scldin (2021) enhances this approach, yiclding tighter upper bounds with respoct to T. We antieipate that by employing such regularizers, we could achieve log(T) log"(T)) regret upper bounds, similar to the OFUL algorithm in (Abbbbb-aaddaooo et al. (2011). We expect that the regret upper bounds will be worse than the one in Abbasii-yadkori et al. (2011) due to the estimation of the inverse covariance matrix. While alternative regularization could be applicable in our context, it may require additional assumptions to derive desired regret upper bounds. Concerning the number of optimal arms, [to (2021) and [Jin et al. (2023) introduce BoBW algorithms for scenarios where the optimal arm is not unique in standard multi- armed bandits. However, the analysis is complex, and extensions to combinatorial semi-bandits, or lincar bandits, which are arguably simpler than contextual linear bandits, are yet to be seen. Thus, although their methods hold promise for linear contextual bandits, their straightforward application in our setting presents significant challenges.
Independently of us, Kuroki et al. (2024) proposes several STRL-based BoBW algorithms for linear con- textual bandits with adversarial corruptions. One of their proposed algorithms is also a BoBW algorithm based on FTRL with Shannon entropy, which coincides with our proposed algorithm. As another approach, they employ the black-box framework proposed by Dann et al. (2023a). They show that under the black-box framework, we can obtain BoBW reduction of RealEXP3 with regret of order (log(T') in the stochastic regime. They also present another algorithm by combining the black-box framework with the continuous ex- ponential weights algorithun in Olkhovskaya et al. (2023). While this algorithm incurs regret of O(log"(T) in the stochastic regime, it incurs a regret of (T) VA+) in the adversarial regime, where A denotes the cumulative second moment of the losses incurred by the algorithm. Although the black-box framework provides a tight Olog(T)) regret regarding T, limitations have been reported in practical implementation. As well as Kuroki et al. (2024) mentions, "FTRL with Shannon entropy regularization a much more practical algorithm."
2 Problem Setting
Suppose that there are T rounds and K arms. In each round t E [T] (1,2...., T). a decision-man maker observes context X, X c Rdd where X' is context space. Then, the decision-maker chooses arm
4

---

Published in Transactions on Machine Learning Research (06/2024)
A E [K] (1,2...., K} based the context X, and past observations. Each arm [K] is linked to loss fe(a, Xt), which depends X and round 1. After choosing arm A, in round 1, the decision-maker incurs the loss (A,, X²). Our goal is minimize the cumulative loss Ei=& (At, setting in more detail in the following part.
We introduce the
Contextual distribution. Let distribution of X, be D, which is invariant across [T). We also decision-maker.
assume that D is known to the decision maker.
Assumption 2.1 (Contextual distribution). D is known to the decision-maker,, and the covariance matriz 2 = E [x,x,] is positive definite with its smallest eigenvalue Amia > 0. We also assume that Amin is known.
The contert X is an iid. random variahle, whose distribution
2.1 Linear Contextual Bandits
This study assumes linear models between (t(a,X,) and X as follows. Assumption 2.2 (Linear models). For each (a Xi), the sollowing holds:
b(a, X.) x,T0(aa) 0c(a) + Ex(a).
where (a(a) E ④ is d-dimensional porometer with a parameter space θ Rd and sr(a) the error term independent of the sequence {XI)
In each round / E [T), context is sampled from D and the enviromment chooses (0 [a((k)) based the past observations Ft-1 AI, X1) A 44
For linear models and variables, we make the following assumptions.
Assumption 2.3 (Bounded variables). We assume the following:
There erists an universal constant Cx such that for each X, || 122 S Cx holds.
2. There erists an universal constant Ce > 0 such that for each 0 E O, |101]2 - Ce holds.
3. There erists universal constant Cg 0 such that [Ea(a)] Ce holds.
Under this assumption, there exists C₁ = C(Ox,Ce, Cc) such that for all lı x), the following holds for each a E [K] and X:
(((ax)) S Ct.
For simplicity, we assume Ct
We consider general framework where [0((a)) is generated in both stochastic and adversarial ways. See Section 2.5 for details.
2.2 Policy
We refer to function that determines the draw policy. Let IT be set of all possible policies x X + P = (u) U2 ... T [0, E un =1}. Let T(a x)) be the a-th element of x(x).
The goal of the mecision-maker to minimize the cumulative loss Σt (e(A,, X,) incurred through rounds by learning policy II.
2.3 Data-Generate Process
In each round trial, the decision-maker first observes context and then chooses an action based on the context and past observations obtained until the round. Specifically, we consider sequential decision-male making with the following steps in each round E [T]:
5

---

Published in Transactions on Machine Learning Research (06/2024)
1. The environment decides [Q((K) based Fi-1-
The decision-maker observes the context Xt, which generated from a known distribution D.
3. Based on the context Xt, the decision-maker chooses a policy (x().) E P.
4. The decision-maker chooses action A, [K] with probability aa(a x2).
The decision-maker incurs the loss (At,
The goal of the decision-maker to choose actions in a way that the total loss is as small as possible.
2.4 Regret
This section provides the definition the regret, a relative measure of the cumulative loss. We evaluate the performance of the decision or policy of the decision-maker by using regret. Tet be set of all possible p : X + [K]. The quality of a decision by the decision-maker measured by its total expected regret, defined as
RT max E PER
Σ ((),, - -
((((()), x
max PER
Σ Xx. (((A)) (((())))(((()))
where the expectation is taken over the randomness of policies of the decision-maken as well as the sequence of random contexts, (Xihetr) and losses, ( (e))
Let Xo be an i.idd random variable from the distribution of Xx. Then, because X₁ an ii.d. random variable from D, we have
X (xx =E
T
Xu. Oc 0l(((x0)))
Xo. E (0(()))))
E
E
min KE|K]
Based on this inequality, we define an optimal policy af as
T
(x) arg min aE(K]
x, Lr, (,,a)l(a))).
t=1
Then, we have
X1, (,(o) -b((a))))((((()))))))
RT < E
Neu & Olkhovskaya (2020) refers to P as linear-classffier policies, while m, called stochastic policies. our study, docision-makon compare their stochastic policies m, to the optimal lincar-classifier policy a" using the regret.
2.5 Linear Contextual Adversarial Regime with a Self-Bounding Constraint
Then, we define the framework of linear conteztual adversarial regime with self- bolndioundig constraint, which is generalization of adversarial and stochastic bandits.
Definition 2.4 (Linear contextual adversarial regime with self-bounding constraint). We say that environment is in lincar contextual adversarial regime with (A., C, self-bounding constraint for some A., C> 0 if Rt is lower bounded as
T
क. (at( 1x6)) -
RT > A.
E
Σ
6

---

Published in Transactions on Machine Learning Research (06/2024)
The contextual adversarial regime with self- constraint includes several important settings. Among them, we raise linear contextual bandits in stochastic bandits and adversarial bandits below. Both correspond to cases with C = 0 (linear contextual adversarial regime with a (A., 0, self-bounding con- straint) and C' = 2T (linear contextual adversarial regime with a (A., 24,,T, self-bounding constraint); respectively. The parameter C determines the degree of an adversarial corruption: as larger, the adversarial corruption is also larger.
Example (Linear contextual bandits in stochastic bandits.). We consider a lincar contextual adversar- ial regime with (A,,0. 0, self- bofddinnning constraint, which corresponds a stochastic environment. In stochastic bandits, the bandit. models fixed; that is, (X,,&(1, x.)...., ........ (.l.....,KKKK,, X+)) generated from fixed distribution Po. Let (a(a) ... (a) Oo(a). Note that when considering stochastic bandits, we have E [a)] = (a) and
(x) = arg min dE[K]
x, E. (.O(Or(a))
arg min (c,Dool)) dE[K]
Va E X.
Let (x) be 07(x).
In this setting, we assume that for each Po. there exist positive constraints A, such that for all x E EX
min bxog( (2) (r.00(0))
(2,,)) 2A..
(1)
Then, the regret can be lower bounded as Rr 2 A, E Ei (1- (1- Te(a | (See Appendix
A
Example 2 (Linear contextual bandits in adversarial bandits). We consider lincar contextual adversarial regime with a (A., 27, sell-bounding constraint, which corresponds lo a stochastic environment In ad- versarial bandits, we do not assume any data-generating process for the Xi), and the loss decided to increase the regret based on the past obsorvations Ft-1-
Remark 1 (Margin conditions). In linear contextual bandits, we often employ the margin condition to characterize the difficulty of the problem instance. The margin condition is defined follows (Li et al.
2021 there exist A., C1, a", and a E [0, +oo), such that for h log(d) A
Civ
p ((x,)(((a)) min (x,,,(())) - h S bsa
h
A,
Our definition of the linear contextual adversarial regime with self-bounding constraint corresponds to case with = In existing studies of linear contextual bandits under adversarial environment, the margin condition with a = 0 is assumed in Abbasi-yadkori et al. 22011), which demonstrates O -(yT))-regre.. On the other hand, the margin condition with a E (0. is considered in works by Goldenshluger & Zeevi
2009 2013) Wang et al. (0188) and Bastani & Bayati (2020) Goldenshluger & Zeevi (2009) establishes O ( a)/ regret for a E (0, 1), while Goldenshluger Zeevi (013)) proves O (og()) -regret for a = Furthermore, Abbasi-yadkori
al. (2011) explores scenario with a 30 and demonstrates O (log(T)/A.)- regret. Li et al. (2021) presents general lower bound that is applicable for various Extending results to encompass more general values of a constitutes future work. We anticipate that an ideal BoBW algorithm would perform comparably to the existing studies, such as those by Abbasi-yadkori el al. and Goldenshluger & Zeevi 2009 2013). in a stochastic environment.
2011
Remark 2 (Lincar contextual bandits with corruption in existing studies). Lykouris & Vassilvtiskii 2018 Gupta et al. (2019), Zhao et al. (2021), and He et al.) (2022) propose another definition of linear contextual contextual bandits with corruption. In their work, instead of our defined ((),,)), they define a loss as
t,,, (a X.) + (((a),
where (a) is an adversarial corruption term. For simplicity, let Za(a) 1-111. In Zhao et al. (202 the degree of the corruption is determined by Ō E [0, T] defined as C Σt max.e(K) (a((a). In Lykouris &
7

---

Published in Transactions on Machine Learning Research (06/2024)
and He et al. 2022 the corruption level is determined by another - |cr (At)). Here, C Ct holds. Note that the adversarial corruption while the adversarial corruption determined irrelevant A in Lykouris & Vassilvtiskii (2018) Gupta et al. (2019), and He et al. (022). Unlike ours, they do not assume In this sense, our results and their results are complementary.
Vassilvtiskii [2018) Gupta et al.
2019
parameter C [0. 2] defined Σ
depends on A, in Zhao al.
2021);
the existence of A, defined in equation
3
Algorithm
This section provides an algorithm for our defined problem. Our proposed algorithm is a generalization of the RealLinEXP3 algorithı proposed by Neu & Olkhovskaya 2020). We extend the method by employing the Follow-Ther Becee-eeglariiedd-eeeee
(FTRL) approach with roundvaryyng arm-drawing probabilities. Our design of the algorithm is also motivated by existing studies about Best-of-Both- Both--olBt (BoBW) algorithms in different Multi-Armed Bandit (MAB) problems, such as Ito et al. (002)).
In our setting, we first observe a context and then draw an arm based on that context. We consider stochastically drawing an arm. Therefore, in designing the algorithm, our interest lies in appropriately defining the arm-drawing probability. In the FTRL approach, we define this probability by utilizing an unbiased estimator of the loss function.
We refer to our proposed algorithm BoBW-RealFTRL because it modifies the RealLinEXP3 for a best- of-bldthwoorlds algorithm using the FTRL framework. The pseudo-code is shown in Algorithm [ In the following part, we explain the algorithm.
Unbiased loss estimator. For each E [K], let us define an estimator of regression parameters as 0.(a) = xx 1A, a]x,,t((r,,) Xt),
Then, the loss can be estimated as where Et is an estimator of E,' = [1[A - a) x|x, Xe Fi-1]" E)(axz) (z,0c(a))
In analysis of adversarial bandits, the bias of 2((a,z) plays an important role. If D
E [L[A, a,x,TL X, Fi-1] then this loss estimator is unbiased for x Oo(a) because
E xa, Fi-1 =x E (a) F--1] = Tx B [[A a|x,e F. = =x T E [1[A: = X] X (o(a) + +c(()) [F-1] = x lo(a).
Note that our algorithm, Σ/_ just an estimator of Σ and Σ/ = Σx¹ does not hold in general. Therefore, (( not unbiased. However, we can show that the bias can be ignored bocause it is sufficienlly small to evaluate the regret in depth. We also define a vector of loss estimators as (xx) = (E.(1,x)) (2(2,x) Ee(K,z))
Estimation of Σ,' Our remaining task estimate Σ, The difficulty of this task stems from the dependency Ae; which varies across rounds. To address this issue, employ the Matrix Geometric Resampling (MGR) proposed by Neu & Olkhovskaya (2020). The MGR assumes that have access to the distribution D of X, and estimates Σ, by using simulations. We introduce the algorithm in Algorithm 2
In Algorithm g we define Wkj,a so that E[WKaja Fc-1) = Σ,a holds for each k E ( M2} and
j E 21,2..... k). Let define Vk, - SWaj.a). Here, from the independence of the context W Wajaa from each other, we also have
A
VKK
Fi-1] = E
8Wk.Ja)
F = II (I
SE Wasja [(-1)) (I --EE,a)*
1=1
8

---

Published in Transactions on Machine Learning Research (06/2024)
Therefore, E(,a = = Mr
Vk works good estimator of Dí on expectations when M, because
00
St Lta Ft-1
87 +
(T 8E
5 (T & 8(8E),a) -1= = Σ k=0
holds, where we used Σ k=0 A (1 A)- for diagonalizable square matrix A whose all eigenvalues are greater than -1 and less than 1. In implenentation, M, is usually finite, which causes an estimation error. Therefore, Neu & Olkhovskaya (2020) performs estimation error analysis of Eg, with finite M2 in Lemma B55
Our proposed algorithm: BoBW-RealFTRL. Then, we define our policy, called the RoBW-RealFee as
(X,) (1 (x,)) Vt where is K-dimensional vector = (11 ...1)T,
(2)
K
Σ (2((0))(()) + ) (
(x(x) E arg min
for 12 qi(x) = (1/K1/K ... 1/K)T,
gell
vr((())) -,H(((())), H(((x)) E
a(a log
(3)
g(a x))
aE(K]
B1 V 1 (log(K))
log(T)
Bet1 = 3e +
: = C
Klog(T)
8dmin / llg(K) + dl
(4)
E. (g.())))
K
log(T) C log(T), % = min (1, T..
7t
(5)
28 mtmmin
Am
1
Me = (28 1), 8 ==
2CeCx
Note that an FTRL algorithm with the Shannon entropy is generalization of the exponential weighting algorithms. Indeed, (x(x)) has an analytical solution given as
1-1 (a x) exp (-
(x(x) EdE[K] exp
E (b(b, x)33
The parameters 3r and "t adaptively adjust the regularization and exploration based on the past observations up to the t-th round. Appropriately chosen fixed parameters for these can lead to the RealLinEXPS algorithm proposed by (Neu & Olkhovskaya] 2020), which tailored for adversarial environments but does not achieve logarithmic regret upper bounds. Therefore, our algorithm extends RealLinEXP3 and FTRL. In the realm of BoBW algorithms, FTRL-based methods are commonly utilized, linking approach to existing literature. It is crucial to note the balance among 3e, Yh, and M, (a parameter in the MGR algorithm) is vital for ensuring desirable regret upper bounds. For instance, the exploration rate influences Σ, and M, is consequently affected as it is used in estimating X Since M, also impacts the regret upper bound, parameter selection is meticulously conducted to tighten the bound considering the interplay among Br, Tts and Mc-
4 Regret Analysis
This section provides upper bounds for the regret of our proposed BoBW-RealFTRL algorithm.
For notational simplicily, let us denote at by a". To derive upper bounds, we define the following quantities:
T
Q(a" ()) = {1 ge
11 (1- (a
Q(a") = EQ(("") Xo)]
1=1
9

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm BoBW-RealFTRL.
Parameter: Learning rate 31, .2...., .a....,,p.1 Br > and exploration parameter Y E (0, (0,1), which depend Amin: Ce. Cx, K, d, and T. Initialization: Set (o(a) = for all a E [K].
for I.....T do Observe X,, Draw A, [K] following the policy mx(x,) (1 - (X,) + R defined equation 2 Observe the loss (A,,, Xt). Compute (e(a) for all E [K].
end for
Algorithm 2 Matrix Geometric Resampling (Neu & Olkhovskaya 2020).
Input: Context distribution D, policy Te. action [K].
for k: I,..., Mj do for = =;....., k do
Draw XR.j ~ D and Vay ~ Tel. (x,).. Compute Wk,jaa = [Vx. = a) X XA.s" k.j" end for Compute Vi.a- = 11 -1-8 8Wajja. end for
Me Vk.a- Return: 22a = ST + EML,
St
Then, we show the following upper bound, which holds for general cases such as adversarial and stochastic environments. We show the proof in Sections B.1 and B.2
Theorem 4.1 (Genoral regret bounds). If the environment generates losses under the contertual adversarial regime with a self-bouneeeee rolf-bounding constroint (Definition 2.4), the BoBW-Ree ReaFFRR with Et incurs the total regret
RT 00=0
(
(llo(() 31
+ d + 8Amin (og(K))
log(T)
+ 31 (ooloo(k)) Vlog(KT) max (0))
For each situation, such adversarial environments and lincar contextual adversarial regimes with self- bounding constraint, we derive a specific upper bound.
First, from Ø(a")= S T, the following regret bound holds without any assumptions on the loss; that is, it holds for an adversarial enviroument.
Then, under an adversarial environment, the Corollary 4.2. Assume the same conditions in Theorem
regret salisfies
(((((()))))) (Klog(TT
RT =
8dmin v log(K) + d + B1 (log()) vIog(KT]V)
log(T))
B1
that is, from Br = Co Klog(T)
log(T)) &Amii / (log(K) + dd)
Rr 0 (Igg(KT) K log(K)) log(T)
log(T)
Ddmin v Tog K)
holds.
Furthermore, we derive regret bound under the linear contextual adversarial regime with self-bounding constraint.
10

---

Published in Transactions on Machine Learning Research (06/2024)
Corollary 4.3 (Regret bounds under the linear contextual adversarial regime with self self-bounding con- straint). Suppose that the same condilions in Theorem 4. hold. Then, under the contertual adversarial regime with self-bore bouldbounning constraints, the regret satisfies
RT of
=0
K (Kloo() B1
( log(T)
2
d =a)
B1 (lo(KK)
log(KT)/A.
8Amia /log(K)
c (lg((T)
log(T)
+ d +d) B1 (log(K)) log log(KT)/44 /A
V
B1
8Amin v log(K)
that is, from B1 = CoOC2// K Klog(T)
log(T) 8 8dmin v log(K)
+ d
K log(K) log(T)
log(T) Amin / /lo((K)
+d d log(KT)
CK (oK((()) log(T)
6Amin v (lo((K + d (TT)
log(T)
Rr = 0
A.
holds.
The result in Corollary 4.3 implies Rr = O
(T
+
Colog (2)
regarding T.
A.
Proof. From the definition the contextual adversarial regime with a self-bounding constraint, we have
T
ग. (Xoo x
Rr A.
Σ
A. -((a') C.
Therefore, from Lemma B.7 for any X > 0, we have
Rx= (1 R) XRT
A)
(Vllog(TT)
E ((((((X)))
-AR
(1+AAJ
co/lo((T))
HH (xx(()))))
-AA, ((a')((a) + AC,
where
K log(T) (T)
log(T)
+ d
31 v /log(K)
31
JAmin log( K)
Here, as well as the proof of Theorem llo((K)) and otherwise, we have Σ/ H (q.(=))
4.1 from Lomma B.8 if Q(a" 2) S we have ΣT H(g((z)) 5
Q(a" x) log (KT). Hence, we have Σt H(q(())
log(KT) max(e, Q(a" x)). Here, upper bound Rr, it is enough only consider case with Q(a" (x) and we obtain
o (Ha+N)off Vlog(KT)
Ry < (1 + 2)0 (V/og((T)//((a))) log(k)
AA. Q(aa)))) + AC
+ AA..
214,
where the second inequality follows from avb 5b e² holds for any a, b, > 0. By choosing
log (T)
/
c2 log KT)
20
A,
A.
11

---

Published in Transactions on Machine Learning Research (06/2024)
Then, we obtain Rr - (02221000) (log(KT)//A. + (ogK))
In the Appendix
B
show the proof procedure of Theorem
5
Conclusion
We developed BoBW algorithm for linear contextual bandits. Our proposed algorithm is based on the FTRL approach. In our theoretical analysis, we show that the upper bounds of the proposed algorithm are given as O min D + CCD Voo.ooogg))))) where D= K log(T) (log(T) + d K)) log( This re- V
gret upper bound implics O min V. Vlog(KT)TD)) regret in an adversarial environment and O (2.)
regret in an adversarial environment and O ( I. regret in a stochastic environment. This result also implies regret in stochastic regime and O (ogToo(())) regret in an adversarial regime with respect
O (r) to T.
A.
There are four directions for future work this study. The first direction is develop an algorithm that does not require contextual distribution while maintaining the BoBW property. We expect this extension can be accomplished by applying our proposed method method proposed by Liu et al. (2023), based on the FTRL approach with the log-determinant barrier. We note that standard linear contextual bandits in stochastic environment do not require the contextual distribution to be known, but it is required for dealing with an adversarial environment.
The second direction to provide lower bounds in our adversarial regimes. In existing studies, Li et al. (0021 provides general upper bound that holds for a high-dimensional setting with various margin conditions. We can incorporate such results derive a lower bound in our problem setting.
The third extension is to develop an algorithm that works for linear contextual bandits without assuming specific minimum gap constant A.. To address this issue, might use the margin condition to generalize the minimum gap assumption. Lastly, tightening our regret upper bound is also an open problem.
References
Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Newral Information Processing Systems (NewrIPS), 2011.
Naoki Abe and Philip M. Long. Associative reinforcement learning using linear probabilistic concepts. International Conference on Machine Learning (ICML), 1999.
Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pscudo-regret for both stochastic and adversarial bandits. Conference on Leurning Theory (COLT), 2016.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensions covariates. Operations Research, 68(1), 2020.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algo- rithms with supervised learning guarantees. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. Conference on Learning Theory (COLT), 2012.
Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust high dine-simeniinaal linear contextual bandits. In International Joint Conference on Artificial Intelligence (IJCAT), 2020.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. International Conference on Artificial Intelligence and Stalistics (ATSTATS), 2011.
12

---

Published in Transactions on Machine Learning Research (06/2024)
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Annual Conference Compulational Learning Theory (COL.T) 2008.
Chris Dann, Chen- Yu Wei, and Julian Zimmert. A blackbox approach best of both worlds in bandits and beyond, In Gergely Neu and Lorenzo Rosasco (eds.), Conference on Learning Theory (COLT), volume PMLR, 2023a.
195, pp.
Christoph Dann, Chen- Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In International Conference on Machine Learning (ICML), 2023b.
Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adver- sarial attacks. In International Conference on Artificial Intelligence and Slalistics (AISTATS), 2022.
Alexander Goldenshluger and Assal Zeevi. Woodroofe's 's one-armed bandit problem revisited. The Annals of Applied Probability, 19(4):1603 1603--33333,,,,, 2009.
Alexander Goldenshluger and Assaf Zeevi. A linear response bandit problem. Stochastic Systems, 2013.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory (COLT), 2019.
Elad Hazan, Tomer Koren, Roi Livni, and Yishay Mansour. Online learning with low rank experts. Tn Conference on Learning Theory (COLT), 2016.
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandils with adversarial corruptions. In Advances in Newral Information Processing Systems (NeurIPS), 2022.
Shinji Ito. Parameter-fie free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, volume 134, pp.
2021.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-hoth-worlds algorithms for online learning with feedback graphs. In Advances in Newral Information Processing Systems (NeurIPS), 2022.
Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved best-of-both-worldd guarantees for multi-armed bandits: Ftrl with general regularizers and multiple optimal arms. In Advances in Newral Information Processing Systems (NeurIPS), 2023.
Varun Kanade and Thomas Steinke. Learning hurdles for sleeping experts. ACM Transactions on Compu- tation Theory, 6(3), 2014.
Fang Kong, Canzhe Zhao, and Shuai Li. Best--ofthrreewwrldds analysis for linear bandits with follow-the- regularized-leader algorithm. In Conference on Learning Theory (COLT), 2023.
Yuko Kuroki, Alberto Rumi, Taira Tsuchiya, Fabio Vitale, and Nicolò Cesa-Biance gorithms for linear contextual bandits. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 238, pp. 2216-1224. PMLR, 2024.
al-
Tor Lattimore and Csaba Szepesvari. The End of Optimism? An Asymptotic Analysis of Sinite-Aree Linear Bandits. Tn International Conference Artificial Intelligence and Stotistics (AISTATS), 2017.
Chung-We Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance- optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. In Inter- national Conference on Machine Learning (ICML), 2021.
Ke Li, Yun Yang, and Naveen N. Narisctty. Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit. Electronic Journal of Statistics, 15(2):5652 - 5695, 2021.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In International Conference World Wide Web (WWW), 2010.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Haolin Liu, Yu Wei, and Julian Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. In Advances in Neural Information Processing Systems (NewrIPS), 2023.
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In Interna- tional Conference on Machine Learning (ICML., 2018.
Saeed Masoudian and Yevgeny Seldin. Improved analysis of the tsallis-inf algorithm in stochastically con- strained adversarial bandits and stochastic bandits with adversarial corruptions. In Conference on Learning Theory, volume 134, pp. 3330-3350 2021.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory (COLT), 2020.
Julia Olkhovskaya, Jack Mayo, Tim van Erven, Gergely Neu, and Chen- Yu Wei. First- and sccond-order bounds for adversarial linear contextual bandits. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Alexander Rakhlin and Karthik Sridharan. Bistro: An efficient relaxation- method for contextual bandits. In International Conference on Machine Learning (ICML), 2016.
Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3+ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory (COLT), 2017.
Yevgeny Seldin and Alcksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning (ICML), 2014.
Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E Schapire. Improved regret bounds for oracle- based adversarial contextual bandits. In Advonces in Neural Information Processing Systems (NeurIPS), 2016.
Ambuj Tewari and Susan A. Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health: Sensors, Analytic Methods, and Applications, pp. 495 517, 2017.
Taira Tsuchiya, Shinji Ito, and Junya Honda. west-of-both-worlds algorithms for partial monitoring. In International Conference on Algorithmic Learning Theory (ALT), 2023a.
Taira Tsuchiya, Shinji Ito, and Junya Honda. stabilty-penally--aaaiiiee follow-hherreullriieeeeeeeerr Spar- sity, game-dependency, and best-of-botte worlss..ds. In Advances én Neural Information Processing Systems (NeurIPS), 2023b.
Xue Wang, Mingeheng Wei, and Tao Yao. Minimax concave penalized multi-armed bandit model with high-dimensional covariates. In International Conference on Machine Learning (ICML), 2018.
Chen-Yn Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory (COLT), 2018
Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Linear contextual bandits with adversarial corruptions, 2021. URL
t1o0Taa
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(1), 2021.
14

---

Published in Transactions on Machine Learning Research (06/2024)
A Details of Example
1
(4) (z. (2,00(6)) When (4)
(z (2, (ol(((())))) 2 A. holds for all x E R, have
T
Σ ((a)((x)), x.)
RT = E
4AA,, X1)
T
E
X₁ (0((a) (x((a( ( Xx)
1=1 aE|K]
T
E
Σ
X (bb(a)) - (0((5((x))) =z(a Xx)
(=1 (Xi)
T
2 A.
Σ
Σ
Ta(a Xi)
tm atting
(1 (e)((Xo)))))) xo))
2 A, E
B Proof of Theorem 4.1
B.1 Preliminaries for the Proof of Theorem 4.1
Let Xy be a sample from the context distribution D independent of Fr. Let De(p.g) denote the Bregman divergence of p.q E with respect the that is,
Dr(p, = vh(()) -be(g) (Ver(g), 1).
Let us define x² II as (x) x) = 1 and x² (a 2)) 0 for all [K] (x))
Then, the following lemma holds. The proof is shown in Appendix C Lemma B.1. If A₁ is chosen our proposed method, the regret is bounded by
T
R1 < E
Σ 1=1
Y +
(Xx) -9+1(Xx))
(Xo) + (((()+1((o)) - (e41
+ (X+)((((Xo)) (1(
2 aE|K]
+2
max
E -c)))
To show Lemma B.1 use the following proposition from Neu & Olkhovskaya 2020
Proposition B.2. Suppose that ne F and that E [o))) 0,(a) for all I, hold. Then, the following holds:
Te(a X,) (a xxi) X1, (xa
Te(a Xo) (a Xo) ( (o)))xx, (x,0((a))
E
Σ [E[K]
=E E
Σ Σ
1=1
aE[K]
This proposition plays an important role throughout this study.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Bounding the stability term. For the stability term
(((o)) - 9u+1
D we use the following proposition from Ito al. (2022).
Proposition B.3 (From Lemma 8 in [to al. (2022)). ) If the is given as equation and p.g II, we have
for any l: X R.K
(e(w))p(s) -((x)) De(g(z), S 3 Σ p(a x){ ((((,x))
Br
aE[K]
for any x E X, where E(x) exp( (pp(-)))a x
For x), if Fdlama) B 2 -1 holds, then Proposition B.3 implies
(((()) - (++(()) - (1))+(()), S
Σ
me(a (a)
3
KEIK]
For the RHS, we apply the following proposition from Neu & Olkhovskaya 2020 Proposition B.4 (From Lemma in Neu & Olkhovskaya (2220)) For each t EE [T), our strotegy satisfies
Σ [E[K]
(a (o, Fi-1 < 3Kd.
Estimation error of the design matrix. Next, we bound E max E [((x,,0(aa) -o(aa) { An
upper bound of Etm m K] (Xe, 0c(a) (((a)) is given as the following lemma.
Lemma B.5. For all such that 7t = nt we have (Xa, -((a)) CxCe/T.
(X 0c(a) 0((a))] x
Proof of Lemma B.5 From Lemma in Neu & Olkhovskaya (2020), we have E
CxC exp (- Amin M.). Then, when = Tt, we have
exp
(-
no K
Amin Mr exp
(-&Amt 2/8 K
(-
K log(T) 8Ammn Mi)
8Amin
K log(T))
8Amin
1
exp
Me exp (- log(T)) T
8dmin
(2 1)
K
where recall that defined M, 2,3, - 1.
B.2 Proof of Theorem
Then, we show the following lemma. The proof is shown in Appendix D Lemma B.6. The regret for the BoBW-RealFTRL with Et is bounded
+ (B141 Br) ((a))( } 31 log(K) + 20x
3Kd B.
Ry E
Tt +
From this result, obtain the following lemma. We provide the proof in Appendix
Lemma B.7. Assume the conditions in Theorem B.6 Suppose that Br and satisfy equation and equation Then, we have
Ry <
E
Σ H(((X)))
+ + + 2C
16

---

Published in Transactions on Machine Learning Research (06/2024)
where
K (og
(T) 8dmiu log K)
+ BI vlog(k))
0
+
$1
K log
To
Σ H()((x.))
28 31 v (og(K)
Next, we consider bounding ET= 1 H1 (x) by (a" x) as shown in the following lemma..
Lemma B.8 (From Lemma 4 in Ito et al. 2022 ). For any a' X + [K], the following holds:
eKT
((g())) s Q(a" ax) log
Q(a" x:)
where is Napier's constant.
By using the above lemmas and propositions, we prove Thcorem
Proof of Theorem
4.1 From Lemma
B.8 Q(a" x) S e, we have Σ
1= (q)())) S elog(KT) and other-
T
wise, we have Σ
H (x)()) & Q(a" z) logí KT). Hence, we have Σt=1 H (Q: I log(KT) max(f, Q(a"
}.} From Lemma
B.7
we have
T
Rr 2
Σ
E ((()(X)))) CC
1-1
=0
((x)
((log(())
log(T)
log(T)
+ d + 31 Voogo)())
Vlog(KT) max {Q! .1
B1
8 8Amin /lo(KK)
C Proof of Lemma B.1
Let us define
Rr(x) Σ Σ
Telaa 2) xa(a=))) ( (z,0
1=1 oE[K]
Then, the following holds:
Rr E
Rr (xx() + >
E. (()))((a) (()))
aE(K]
Then, we prove Lemma B.1 as follows.
Proof of Lemma
From the definition of our algorithm, we have
T (AA,, X,) elaarr x)
RT E
E
(lr(X)), (Xi) - -x
17

---

Published in Transactions on Machine Learning Research (06/2024)
T
T
1
E (G(x), - (X,)) + Σ
((x)):
K²
1=1
T
$ E
((())). ((0l))=x((,)) =(x))
+ Σ
m
1=1
E
(((X)).((Xo) r'(6o) +C+ Σ "1
1=1
T
(4(X)) - ((oo)) - x ((6))
(E((Xo) -x((oo)) + Σ 7t
E
+
T
T
WM
E
(x(o)).((X))) (xxo) + Ce
7t
+ 2
Σ
max ØE[K]
E
(
(0)
1=1
Then, from the definitions of qt for each x E X, we also have
(x(=)) (s)) + (T+)(=(()))
(2((), + (1+1++++11) (T+1(0++(x))
+ (v++(+((x))) (VW)lor=1())), x (x) qr+1(x))
(())))))++1())))a1)))))))))))( (()) (1)))))))+++ (rr1((+111))) + Dr+1 (x),
where we used that (V (x+1(2)) 2 0 holds for a convex function v/. Then, it holds that
(()), x (w)) + +
(B(0)) +
Σ (((lo)) + ()(()(())
(2(0m+1()) + +
(T-1(0++(())
Σ (((t))))rH11))) + (x(((()))
(2110) (z( + (p))
- -xx10+1)))))(((((1 + 0741((441()))
(1)))) + ()((r(1))
+ Dr((0= (r)())
+ DT+1( (x), (z)))++(())) (T(0T+1 (-)r--r))( (7H1((+1(1))
Σ ((()))
(e(()+()) Σ (v(()+1(z)) (++1((++()))) (1)()())))
Therefore, we have
T Σ ((()), -x))
18

---

Published in Transactions on Machine Learning Research (06/2024)
(()()) - - (+1(x)) - Dr ((() + ve(((+1(x)) ()+1(9++1
+ + (x)) - (1)
Combining this with equation
obtain
RT S
Σ ((((X)). - -x+) (xx
+ vh (()+)((Xo)) (x),
(2+1
T
T
+ WT++(TT(XXo) (1(1)(Xo)) + Ce
Σ
+
max [E[K]
E
(xox - -b((a))]
1=1
D Proof of Lemma B.6
Proof of Lemma B. From Lemma B.1
we have
RT S
E
Σ T7 + (). me ( (Xo)
1=1
+ (x vet1(4+1 + ( (Xo)) (2)(e(
T + 2
>
E (Xe, - -
max aE t=1
First, show
E (((()))) (())) -x+1((o)) - (Xo)
3Kd
(7)
B3
2 11, which is necessary to derive an upper bound from Proposition f((ax) 3r
To show this, we confirm
B.3.
We have
(xo.
x ET Ei X, X,, 0r, 114,, = =a
C.
Xo
X,
3r
3
3r
M
2
C |
C
1
1+
Σ
Vi..ollp
(M, + 1),
B
Br
23
k=1
E(a..) = -1 holds.
where we used that 8 = Then, we have
Here, recall that we defined M, as 23z - 1. Therefore,
20a0
(((x)) )(1(1)) ()((+110):
(x(a,x) x)
< 3, [E[K]
Σ me(a x)
Σ
Ti(a 2)
Br
3.
aE(K]
Then, from Proposition we have equation
From v)((())) (g(e), have
T
(vr(gr+1 2h--1 - + ( - th (2)())
19

---

Published in Transactions on Machine Learning Research (06/2024)
T
B141 - (6) (((+1()))) + B1 log K).
t=1
From Bt+1
81
we obtain
V | (lgg())))) -1 E... 11 (s.(x.))
1-1
11
1.1
3/ = 31
+ (log(K))~>E -E. (()((x)))
VI+ (log(K))
-E. E H(c(())))
Here, we have
K
(T) S
log(T)
1 1 (Iog(K))
Σ H(a((x))
28 2t
26 26 1
T
K
log(T)
Σ H(a(Xx)))
28 28 1,11 v Tog(K)
Therefore, 7e S 1 holds for all 2 To such that
K log(T)
To
Σ ((aa(x)))
20 31 / [og(KK
From Lemma B.5
if there exists To E N such that 7/ holds for all t 2 To, we have
T
T
Σ
max [E[K]
- (1.00(aa-00(0)))
STo + Σ
CxCo =2o + CxCo,
1
t=1
where we used (a) -((a)) 2
E
Proof of Lemma B.7
Proof of Lemma B. 7 Firstly, we note that the following equality holds:
E
(8t+ 3₂) 11 (10++1(Xex))))
E
-8) (9- Fil
T
E
(Be+1 Bc) E. (M (Xo)) Fil
E
(Be+1 Bc) H (((+1(()))
We show the following two inequalities:
T
3Kd
log(T)
log (
T
+
0
+ d
Σ
H(((()))
(8)
3r
Bi
ôAmin log(K) K)
t=1
1=1
20

---

Published in Transactions on Machine Learning Research (06/2024)
(341 B6) (X++)(())))= = ( ( Blvlog(K) K)
Σ H(x((.))
(9)
From 9 min { 10 U4
log (T) }.
First, show equation &
obtain
T
+
3Kd
K
log(T)+ +
3Kd
K
log(T) + 3Kd
Σ
T
3r
20
3r
2 2Ca 8dmia
Be
From Bet1 = Br +
91
we obtain
v |+ (10((K)))
-1 E._ ((x(x.))
B1
1
B: = 31 +
(log( -1 'E> H(x((x)))
VI+ (log(K)) K3) - "EE ((x((x.))
Therefore, we have
1 + (log(K)) -1 "E.= (X.())
1 + log(T))
1+ (log(K)) Σ H ((x(xx))
81
By using H (z)) log(K), we obtain
T
3Kd
(
K (og(T)
log(?) (T)
+
= 0
+ d
Σ 1=1
H H(x+((a)))
31
B1
JAmin v /lg((F) K)
Next, we show equation 9
From the definitions of 8r and ne, we have
T
(Bi+1 - 30) H (((+1(X(+1))) Σ
31
H(4+1(X(+1))
1=1 + (log(K)) -1 E.= H (g.(x))
1=1
((++1(X++1))
= 231 v /log(K)
log(K) E._ H (X.)) + (log(K) + (X)))
H H(9e+1(Xe+1))
231 /log(K)
/lo((K) + Σit1 H (g. (X,)) + v Log(K)) + +
H (gitt(Xe+)))
$ 231 /log(K)) K)
E+H H (go(X))) + E H (qc(x)))
231 (o)(K)
(X4x))((+1))
Σ H((x(Xx))
Σ H (go(Xe))
(((41((((41))
#+1
231 v (lg(())
Σ H ((a((x)))
Σ ((x(Xx))
T+1 Σ
= 2311 Vlog(K
H (x.( (VHX))))(H((((() (H(((())))
21

---

Published in Transactions on Machine Learning Research (06/2024)
s 231 log K)
H (x,())),
where we used / +((0r++(Xx44)) S ((())(x)))
From Be+1 B5
81
we obtain
(1(())())) -1 "Ei (m.(x)))
B1
t
3t 31 +
+ (log(K)) -1 E (x,().))
V1+ - H ((x)
==1
Inequalities equation
g and equation
y combined with the inequality in Lemma
B.6 yield
3Kd
RT E
7t
(Bt41 - Be) (90++((00))
+ 31 log(K) 2Tb 2CxCe
3e
3Kd
}
+
+ (B141 - Be) H (((0+1(X(4a))
+ B1 log(() + 2To + 2CxCs
St
K Klog(T) (log(T) + Smmin d)
T
E
Σ H())1(X)))
+0 B BiVlog(K)
Σ
((g)(X))
31 31d2min / /log(K)
+ B1 log(K) + 2To + 20x
T
K loo(()) (log(T) ddmin
T
Σ
Σ
H (X++(())))))
+0 B1 BlVlog(K),
Σ
[H()(X))))
8182min v (lg(K)
+ 31 (K) + 2T. + C
Thus, we obtain the regret bound in Lemma B.7
22


Reviews:
[{"review_id": "6CQVxUJfWd", "reviewer": "Reviewer_YTsy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The problem of best-of-both-worlds for linear bandits with stochastic context is not studied before and is well motivated.\n- I checked the proofs and the proofs in general look correct to me, with some concerns included in the \"weakness\" and \"requested changes\".\n- The proposed algorithm is intuitive and easy to implement.\n\nWeakness:\n- The main issue is the novelty of the proposed algorithm. While this problem is not studied, the proposed algorithm is a combination of RealLinExp3 [Neu & Olkhovskaya, 2020] and FTRL with adaptive learning rate [Ito et al., 2022], which also does not seem to incur much challenge based on my understanding.\n- The results for stochastic setting require several assumptions that may be restrictive. First, the algorithm requires the knowledge of the context distribution as well as the minimum eigenvalue that is used in the tuning of the algorithm, which may not be available (this issue also appears in the adversarial setting). Second, while it is not explicitly mentioned in this paper, the algorithm should only work when the optimal action is unique, which is also assumed in [Ito et al., 2022]. There are many follow-up works trying to relax this assumption including [1,2] with different types of regularizers including log-barrier and Tsallis-INF. I wonder whether other regularizers can be incorporated into RealLinExp3 and combining with these algorithms may lead to better regret bounds with milder assumptions?\n- The regret rate obtained may not be ideal, especially for the stochastic environment. Specifically, the rate depends on the minimum suboptimality gap and there is cubic \\log T dependency, which are both important for stochastic environment.\n- There are some places that are unclear in the writing of the paper in the current version. See \"Requested Changes\" for detail.\n\n\n[1] Jin et al., Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms, NeurIPS 2023\n\n[2] Shinji Ito, Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds, COLT 2021", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors studied the problem of achieving best-of-both-world guarantees for linear bandits with stochastic context. Concretely, given then context $X_t$, at each round $t$, the loss of action $a\\in [K]$ is defined as $X_t^\\top\\theta_t(a)+\\epsilon_t(a)$. The authors consider three cases: (1) \\theta_t is stochastic and there is a unique optimal action and a minimum suboptimality gap $\\Delta_*$. (2) stochastic \\theta_t with corruption $C$; (3) adversarial $\\theta_t$. The authors propose an algorithm based on a combination of RealLinExp3 [Neu & Olkhovskaya, 2020] and FTRL with adaptive learning rate [Ito et al., 2022], and achieve $O(\\log^3 T/\\Delta_*)$ regret in the stochastic case, $O(\\sqrt{dKT\\log^3(KT)})$ regret in the adversarial case, and corresponding results in the stochastic corrupted case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Questions in \"weakness\" section.\n- Can the authors include more discussions on other related literatures about BOBW for MAB, including using various other regularizers under different assumptions? This may be related to the question on whether the uniqueness of the optimal action can be removed and whether better than $K/\\Delta_*$ can be obtained for the stochastic case.\n- There are several places that are unclear to me in the writing:\n  - In Remark 2, it is unclear whether results in [Lykouris & Vassilvtiskii, 2018], [Gupta et al, 2019] and [He et al., 2022] depend on the actual played action or not. The sentences are contradicting with each other. \n  - In Appendix A, $Q_t^2$ is not defined clearly.\n  - In the definition of $\\Sigma^{\\dagger}_{t,a}$, $X_0$ needs to be $X_t$ since $A_t$ is dependent on $X_t$ instead of $X_0$.", "broader_impact_concerns": "I do not see concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gRjqVtzjko", "reviewer": "Reviewer_o8Wq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My main concern regarding the setting is the following. The paper introduces the new setting with margin condition and changing loss function. (Definition 2.4, Remark 1).  The statement of Definition 2.4 is not clear to me, as no explanation on what \\pi_t are not given. Does it has to hold for any policy?\n\nThe proof looks correct to me. Given the novelty of the result, I lean towards recommending accepting the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the linear contextual bandit problem in two regimes: one setting (adversarial) with i.i.d. context and loss vector chosen by the adversary and the other setting where the loss vector is only perturbed by the adversary C times, and the margin condition is assumed. This work provides the algorithm that simultaneously achieves nearly optimal regret bound in both regimes. The algorithm is based on the FTRL with entropy regulariser.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Remarks: \n1.\tPage 4, procedure in a trial: in 1., should it be that \\theta_{t,a} are chosen at each time step, but not just values for each loss? Or is it equal?\n2.\tDefinition 2.4: in what practical application this assumption holds? Can you motivate it by example?\n3.\tExpectation operator on the top of page 7: Condition on F_{t-1} need to be added.\n4.\tPage 7, the proof of unbiasedness of estimate of the inverse of \\Sigma_{t,a} in the middle of the page: there is unneeded inverse of Sigma in last equality.\n5.\tConclusion: discussion of removing of \\Delta^*. How would the regret looks like, as some margin for the stochastic case is still needed?", "broader_impact_concerns": "This is a theoretical work and mentioned concerns are not applied.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h7OyYW2NOR", "reviewer": "Reviewer_FccE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) Studying the BOBW setting under stochastic and adversarial settings with a self-bounding constraint is an important area of study.\n\n2) The algorithm looks sound. Using the Matrix Geometric Resampling (MGR) to estimate the design matrix for calculating the $\\widehat{\\theta}_t$ is a standard approach used by Neu & Olkhovskaya (2020). Similarly, using the entropy adaptive rule for exploration is a standard approach for the adversarial setting used in Ito et al., 2022. Studying this in the context of BOBW leads to new insight into a unified framework for both settings.\n\n3) They derive the regret bound for the BOBW-RealFTRL algorithm in Corollary 4.2 and 4.3 which prima-facie looks sound, but I have some questions on these (see weakness). They give a proof overview of their main theorem 4.1 which relies on standard techniques from Neu & Olkhovskaya (2020) but is adapted to the setting for the contextual adversarial regime with a self-bounding constraint.\n\nWeakness:\n1) The paper needs some re-writing as several definitions, implicit assumptions, and the algorithm parameters are not defined properly (see requested changes).\n\n2) In the regret bound of Theorem 4.1 it is strange that the dimension $d$ is not a significant factor (see requested changes). \n\n3) The significant of $\\Delta_*$ is not clear to me. \n\n4) Some parameter choices need to be explicitly stated and discussed in section 4 (see requested changes).\n\n5) The key technical novelty for proving Theorem 4.1 seems to be marginal (see requested changes).\n\n6) No experiments are conducted for testing BOBW-RealFTRL algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the Best-of-Both-Worlds (BOBW) setting for contextual bandits for the stochastic and adversarial regimes. They propose a new regime called the linear contextual adversarial regime with a self-bounding constraint that depends on the corruption parameter C and minimum gap $\\Delta_*$. Previous works in this setting have studied adversarial corruption without the existence of such a minimum gap $\\Delta_*$. They propose an algorithm BOBW-RealFTRL that incorporates the Matrix Geometric Resampling (MGR) to estimate the design matrix for calculating the $\\widehat{\\theta}_t$ and the entropy adaptive rule for exploration. This algorithm is shown to have a regret of $O(\\min[\\frac{D}{\\Delta\\_{\\star}}+\\sqrt{\\frac{C D}{\\Delta\\_{\\star}}}, \\sqrt{\\log (K T) T D}])$ which results in $O(\\frac{D}{\\Delta\\_{\\star}})$ for stochastic setting (C=0), and $O(\\sqrt{\\log (K T) T D})$ in the adversarial regime. Their main theorem 4.1 combines the proof technique of Neu & Olkhovskaya (2020) and Ito et al. (2022). They conduct no experiments to show the efficacy of their algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper needs to explain these things in more detail\n\n1) Why the dimension $d$ is subsumed by other factors in $D = K \\log (T)(\\log (T)+d \\log (K)) \\log (K T)$. In a similar work of RealLinExp3, there is the dimension $d$ in the regret bound that scales as $O(\\log (T) \\sqrt{K d T})$. \n\n2) Is there a particular significance as to why the $\\Delta_*$ is important and should be considered as opposed to other works in your related area that do not work with this $\\Delta_*$? Probably this paper is dealing with problem-dependent bound for the BOBW setting, but this needs to be clarified and stated more clearly.\n\n3) Your algorithm needs to $\\lambda_\\min$, and this was not specified in Assumption 2.1. This should be clearly specified also in the parameter line of Alg 1. This is very important, in the sense knowledge of the $\\lambda_\\min$ ensures us to quantify what is the minimum information we can gather from sampling in every informative direction.\n\n4) In section 3 the (sort of) exploration parameter $\\psi_t(q(x))$ is introduced without explanation. This is related to the entropy adaptive rule. It requires more discussion as to why the entropy shows up. Also, more discussion is needed as to why this specific nature of \\beta_t?\n\n5) The Algorithm 1 needs to be written more clearly. The calling of MGR in Algorithm 2 is not clear. Of course, it is used to estimate theta_t but this needs to be stated more clearly in the algo 1.\n\n6) I haven't looked into the appendix of the proof of Theorem 4.1, but reading the proof overview in section 4.1 it is not clear to me what is the key technical novelty. The key novelty that seems to me is the regret decomposition of Lemma 4.4. After that the individual components of this decomposition seem to be handled by using existing results from Neu & Olkhovskaya (2020) and Ito et al (2022). Therefore to me, it seems that the key technical contribution in the main Theorem 4.1 is marginal and needs to be stated more clearly.\n\n7) I understand that the paper is mainly theoretical in nature. Yet it is possible to show some experiments on simulated settings (similar to https://proceedings.mlr.press/v75/abbasi-yadkori18a/abbasi-yadkori18a.pdf). This would greatly increase the strength of the paper.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "c1c1xSDiBw", "reviewer": "Reviewer_94HA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The problem is important and it is first studied by the authors.\n\n2. The algorithm and proof sketch are clear.\n\n\n\nWeaknesses:\n\n1. The regret bound for the stochastic setting is not instance-optimal. It is beneficial to mention it in the paper and briefly discuss some instance-optimal algorithms (such as [1] and [2]).\n\n2. The technical contributions of this paper are limited. The algorithm and analysis combine [3] and [4].\n\n3. Knowing the context distribution is a strong assumption, although the authors discuss possible solutions to relax it.\n\n4. Some descriptions in the paper could be refined. For example,\n\n* It is better to add some instance-dependent bounds for stochastic setting in Table 1\n\n * In the third paragraph of section 1.1, the sentence \"Combining them, ...... , without any assumption on the existence of $\\Delta_*$\" seems repeated compared with previous sentences. \n\n* The citations in Remark 2 seem confusing. The author first shows the corruption In Lykouris &Vassilvtiskii (2018) and Gupta et al. (2019) depends on $A_t$ but then says their corruption is determined irrelevant to $A_t$.\n\n\n[1] Hao B, Lattimore T, Szepesvari C. Adaptive exploration in linear contextual bandit[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2020\n\n[2] Tirinzoni A, Pirotta M, Restelli M, et al. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits[J]. Advances in Neural Information Processing Systems, 2020\n\n[3] Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits.\nIn Conference on Learning Theory (COLT), 2020.\n\n[4] Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worlds algorithms for online\nlearning with feedback graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes the first best-of-both-worlds algorithm for K-armed linear contextual bandits. To achieve this, the authors first introduce a setting called linear contextual adversarial regime with a self-bounding constraint, which generalizes previous settings and captures both stochastic and adversarial cases. Based on this setting, the authors combine the RealLinEXP3 algorithm with a novel learning rate update rule to achieve best-of-both-worlds regret.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses.", "broader_impact_concerns": "I did not find any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers acknowledged the importance of the studied problem, and think the paper introduces novel algorithms and provides theoretical guarantees for the proposed methods. Although using technique similar to [Neu & Olkhovskaya, 2020] and [Ito et al., 2022], the theoretical analysis has some significance. There are some concerns about the algorithm's requirement of knowing the context distribution and a suboptimal regret bound (than O(log T)), but these are understandably challenging to address. 

Two requests to the authors for the final version: 
- As discussed, can the authors discuss concurrent work https://arxiv.org/abs/2312.15433 in the final version?
- It was mentioned by the authors that some preliminary experimental results are provided in Section 5, but the AE cannot find it. Can the authors include them in the final version?
Decision: Accept (poster)