High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
Authors: Ruiyuan Huang
Zengfeng Huang
Venue: ICML 2025 poster (2025)
Keywords: bandit
contextual bandit
cross-learning
high probability bounds
Primary area: theory->online_learning_and_bandits
TL;DR: We give a nearly optimal high probability bound for the cross-learning contextual bandits with unknown context distributions.

Abstract: Motivated by applications in online bidding and sleeping bandits, we examine the problem of contextual bandits with cross learning, where the learner observes the loss associated with the action across all possible contexts, not just the current round’s context. Our focus is on a setting where losses are chosen adversarially, and contexts are sampled i.i.d. from a specific distribution. This problem was first studied by Balseiro et al. (2019), who proposed an algorithm that achieves near-optimal regret under the assumption that the context distribution is known in advance. However, this assumption is often unrealistic. To address this issue, Schneider & Zimmert (2023) recently proposed a new algorithm that achieves nearly optimal expected regret. It is well-known that expected regret can be significantly weaker than high-probability bounds. In this paper, we present a novel, in-depth analysis of their algorithm and demonstrate that it actually achieves near-optimal regret with high probability. There are steps in the original analysis by Schneider & Zimmert (2023) that lead only to an expected bound by nature. In our analysis, we introduce several new insights. Specifically, we make extensive use of the weak dependency structure between different epochs, which was overlooked in previous analyses. Additionally, standard martingale inequalities are not directly applicable, so we refine martingale inequalities to complete our analysis.

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
Ruiyuan Huang' Zengfeng Huang" 12
Abstract
1. Introduction
In the contextual bandits problem, a learner repeatedly ob- serves a context, chooses an action, and incurs a loss specific to that action. The goal of the learner is to minimize the cumulative loss over the time horizon. The contextual ban- dits problem is fundamental problem in online learning having broad applications in fields like online advertising, personalized recommendations, and clinical trials (Li et al., 2010; Kale et al., 2010; Villar et al., 2015).
Motivated by applications in online bidding and sleeping bandits, we examine the problem con- textual bandits with cross learning, where the learner observes the loss associated with the ac- tion across all possible contexts, not just the cur- rent round's context. Our focus is on a setting where losses are chosen adversarially, and con- texts are sampled i.i.d. from a specific distribution. This problem was first studied by Balseiro et (2019), who proposed algorithm that achieves near-optimal regret under the assumption that the context distribution is known in advance. How- ever, this assumption is often unrealistic. To ad- dress this issue, Schneider & Zimmert (2023) re- cently proposed a new algorithm that achieves nearly optimal expected regret. is well-known that expected regret can be significantly weaker than high-proc probability bounds. In this paper, we present a novel, in-depth analysis of their algo- rithm and demonstrate that it actually achieves near-optimal regret with high probability. There are steps in the original analysis by Schneider & Zimmert (2023) that lead only to an expected bound by nature. In our analysis, we introduce several new insights. Specifically, we make ex- tensive use of the weak dependency structure be- tween different epochs, which was overlooked in previous analyses. Additionally, standard martin- gale inequalities are not directly applicable, so we refine martingale incqualities to complete our analysis.
We consider the cross-learning contextual bandits problem. In this setting, the learner not only observes the loss for the current action under the current context, but also observes the loss for the current action under all other contexts. This problem models many interesting scenarios. One such ex- ample is the problem of learning to bid in first-price auctions. In this problem the context the bidder's private value for the item, while the action the bid. The cross-learning structure comes from the fact that the bidder can deduce the utility of the bid under all contexts (i.e., the utility of the bid under different private valuations for the item). Other examples include multi-armed bandits with exogenous costs, dynamic pricing with variable costs, and learning to play in Bayesian games (Balseiro et al., 2019).
Technically, the most interesting setting for the cross- learning contextual bandits problem is when the losses chosen adversarially but the contexts are i..d. samples from an unknown distribution v. Recently, Schneider & Zim- mert (2023) gave an algorithm achieving nearly optimal Ö(v /T) expected regret in this scenario.
Schneider & Zimmert (2023) designed a sophisticated algorithm that operates over multiple epochs to achieve near-optimal regret. A key technique in their analysis is to sidestep high-probability bounds and instead focus on bounding the expected summation to improve their results. As a consequence, their analysis only provides a bound that holds in expectation. It is not immediately clear whether this due to limitations in the analysis or if the algorithm is inherently suboptimal. In any case, if we aim for high- probability bound, fundamentally new insights are required.
'School of Data Science, Fudan University, Shanghai, China "Shanghai Innovation Institute. Correspondence to: Zengfeng Huang <huangzf@@ bwaanngz@@uuannccu.ccom fudan.cdu.cn"..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this paper, we show that the algorithm indeed achieves nearly optimal Ö(V KT) regret with high-probability. The

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
key contribution of our paper is the following theorem.
We overcome this difficulty and show that their algorithm actually achieves high-probability bound. Our key ob- servation is that different epochs in their algorithm are only weakly dependent on each other. Thus, the bias f.(a) T-(a) for each epoch e is also only weakly depen- dent on each other. Therefore, although we cannot estab- lish a small enough bound for the bias of a single epoch f=(a) [a(a)' we can give a small enough bound for the
Theorem 1 (Informal). The algorithm in Schneider & Zim- mert (2023) yields a regret bound of order O(V with high probability for any policy n.
In this section we only give the informal version of Theo- rem 1. The formal version can be found in Section 4.
1 1
1.1. Technical Overview
cumulative bias across all epochs Ee f.(a) f.(a)" then use the bound on the cumulative bias to bound the cumulative regret.
1
We
Our theorem is built new and more in-depth analysis of the algorithm in Schneider & Zimmert (2023). This new analysis introduces several new insights. In particular, we exploit the weak dependency structure between different epochs, which was overlooked in previous work. One diffi- culty of doing so is that standard martingale inequalities are not directly applicable, so we refine martingale inequalities to complete our analysis.
In addition to utilizing the weak dependency structure be- tween different epochs, we also address two further techni- cal difficulties to establish our result. The first difficulty is that the existing regret decomposition is too crude to yield probbbbbbbbbb bound. Schneider & Zimmert (2023) es- tablish an O(vKT) expected regret by decomposing the regret into different parts and bounding each part separately. Although their decomposition gives an Ö( KT) expected regret bound, it is too crude to derive a tight high-probabiling regret bound, even after utilizing the weak dependency struc- ture. We carefully rearrange the regret decomposition to address this difficulty.
To prepare the readers for our new analysis, we first briefly introduce the algorithm in Schneider & Zimmert (2023). The algorithm in Schneider & Zimmert (2023) is an EXP3- type algorithm. The key novelty in their algorithm is the construction of the loss estimates E used in the FTRL sub- routine. Due to some technical problems we detail later, the algorithm decomposes the time horizon into epochs of equal length. In each epoch e, the algorithm first es- timates the probability" [e(a) of observing the reward of each arm a in epoch e by an estimator (a), which is con- structed exclusively from samples in epoch e 1. Note that thanks to the cross-learning structure, the probability of observing the reward of each arm is independent of the contexts. The algorithm then constructs the loss esti- mates as an importance-weighted estimator with [.( as the importance weight.
Secondly, we cannot simply apply standard martingale con- centration inequalities to Ee 1 fa(a) f.(a) to bound its deviation. The main problem is that the random variable fe(a) f.(a) is not almost surely bounded by constant, which makes standard martingale concentration inequalities inapplicable. We introduce a surrogate sequence of random variables as a bridge to address this problem. We bound the sum over the surrogate sequence, and show that the sum over the real sequence is equal to the surrogate sequence with high probability.
Schneider & Zimmert (2023) showed that the performance of the algorithm depends on how well the empirical impor- concentrates around the expected impor-
1.2. Related Works
tance weight [a)
The cross-learning contextual bandits problem was first pro- posed in Balseiro al. (2019). They achieve the nearly optimal O(VKT) regret under two scenarios: (1) when both losses and contexts stochastie, and (2) when losses are adversarial and contexts are stochastic with a known distribution. When losses are adversarial and contexts are stochastic with an unknown distribution, they only achieve the suboptimal 1 regret. More recently, Schnei- der & Zimmert (2023) gave new algorithm that achieves the nearly optimal Ö(v KT) regret in expectation under adversarial losses and stochastic contexts with an unknown
tance weight a. Since the estimator fa is constructed exclusively from samples in single epoch rather than the is not tight enough. To achieve the desired Ö(V KT) regret un- der a not tight enough concentration, Schneider & Zimmert (2023) bounds only the expected bias of importance estima- tor 15 [_] F.( bias bound. Bounding only the expected bias gives a small enough bound, however, they can achieve a bound only on the expected regret from bound on the expected bias.
entire time horizon, the concentration |. T.(a)
- rather than providing high-probability
"The term "weakly dependent" is an informal term commonly used in the context of concentration inequalities. It generally refers to sequence of random variables that, while not fully independent, forms a martingale, allowing us to derive concentration incqualities akin to those for independent random variables.
For technical reasons, in the actual algorithm, the value (a) actually represents the probability of observing the reward of each arm in epoch + 2. For ease of understanding, here we instead let it represent the probability of observing the reward of each arm a each epoch e.
2

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
distribution.
lem to a single-context problem. Unfortunately, their ap- proach cannot be directly applied our problem for two reasons. First, their method is designed for stochastic ban- dits, whereas we deal with adversarial bandits. Second, their approach is limited to linear contextual bandits. Whether it can be adapted, with certain modifications, to address our problem remains an intriguing question.
An important application of the cross-lcarning contextual bandits problem, which is also the primary motivation for proposing this problem in Balseiro et al. (2019), is to solve the problem of learning to bid in first-price auctions. In this problem the context is the bidder's private value for the item, while the action is the bid. The cross learning structure comes from the fact that the bidder can deduce the utility of the bid under all contexts (i.e., the utility of the bid under different private valuations for the item).
2. Problem Statament
We study contextual K-armek bandit problem over T rounds, with contexts belonging to the set [C]. At the be- ginning of the problem, an oblivious adversary selects a sequence of losses (a,(()) E [0, 1] for every round E (7], every context c E [C]. and every arm a E [K]. In each round t, we begin by sampling a context c i.i.d. from unknown distribution over [C], and we reveal this con- text to the learner. Based on this context, the learner selects an arm E [K] to play. The adversary then reveals the function ). and the learner suffers loss le,e, (ax). No- tably, the learner observes the loss for every context e E [C], but only for the arm ae they actually played.
Balseiro et al. (2019) used the cross-lcarning contextual bandits problem to model the bidding problem and obtained an O(T5/1) regret bound for bidders with an unknown value distribution participating adversarial first-price auctions, where the only feedback is whether the bidder wins the auction. Later, many works studied different settings of the bidding in first price auctions problem. For example, Han et al. (2020b) considered the problem with censored feedback, where each bidder observes the winning bid. Han et al. (2020a) considered the scenario when the value is also adversarial. Ai al. (2022); Wang et al. (2023) considered the problem under budget constraints. In all these scenarios, the cross learning structure between different values is essential component of the analysis.
We aim to design learning algorithms that minimize regret. Fix policy : [C] + [K]. With a slight abuse of notation, we also denote Te = c2 E A[K]) for each e E [C]. The (unexpected) regret with respect to policy т is
Another interesting application of the cross-learning contex- tual bandits problem is the sleeping bandits problem (Klein- berg et al., 2010; Neu & Valko, 2014; Kale et al., 2016; Saha et al., 2020). In this problem, certain set of arms is unavailable in each round. The sleeping bandits problem is motivated by instances like some items might go out of stock in retail stores or on a certain day some websites could be down. When losses are adversarial and availabilities are stochastic, previous work either requires exponential com- puting time (Kleinberg et al., 2010; Neu & Valko, 2014) or results in suboptimal regret (Kale et al., 2016; Saha al., 2020). The first computationally efficient algorithm with optimal regret Ö D(VKK') (T) is proposed in Schneider & Zim- mert (2023) by modeling the problem as a cross-learning contextual bandit.
Reg(I)) = Σ (a. (Te.).
Schneider & Zimmert (2023) designed an algorithm that achieves an expected regret bound of E [Reg(T)] S Ö(VKT) for any policy л. We will show that the algo- rithm in Schneider & Zimmert (2023) actually provides a high-probability regret bound.
3. The Algorithm in Schneider and Zimmert (2023)
In this section, we briefly recap the intuition behind the algorithm proposed in Schneider & Zimmert (2023) and redescribe the algorithm formally to prepare the readers for our new analysis.
We also note that handling unknown context distributions is a common and challenging problem across various contex- tual bandit problems. For example, in the adversarial linear contextual bandits problem (Neu & Olkhovskaya, 2020), the linear MDP problem (Dai et al., 2023), and the oracle-based adversarial contextual bandits problem (Syrgkanis et al., 2016), existing algorithms often rely on knowledge of the context distribution. Removing the reliance on knowledge of the context distribution is typically non-trivial (Liu et al., 2023; Dai et al., 2023).
3.1. Intuition behind Schneider and Zimmert (2023)
The algorithm proposed in Schneider & Zimmert (2023) is EXP3-type algorithm. Similar to the well-known EXP3 algorithm, at each round t, the algorithm generates a distri- bution using an FTRL subroutine
Recently, Hanna et al. (2023) proposed method for stochas- tic linear contextual bandits that maps multi-context prob-
1
Pt. arg min (E]((]) P.
Σ
F(w) "
sml
3

---

High Probability Bound for Cross-Lcarning Contextual Bandits with Unknown Context Distribations
for each context e, where F(p) Σx= P; log(p;) is the unnormalized negative entropy, is a learning rate, and are loss estimates to be defined later. The algorithm then essentially samples the action az to be played in round from distribution Pt,ex
losses (,,(()) And this concentration is achieved because the algorithm constructs the estimator using only samples from epoch + 1, which are independent of the estimand.
3.2. A Formal Description of the Algorithm in Schneider and Zimmert (2023)
The key novelty in Schneider & Zimmert (2023) lies in the construction of the loss estimates E. An intuitive construc- tion is defined as follows:
In this subsection we describe the algorithm in Schneider & Zimmert (2023) formally for the sake of completeness. Readers familiar with Schneider & Zimmert (2023) can skip this subsection safely.
(ecla)
(a) = (eowe(pe
I(a: = a).
In each round t, the algorithm generates distribution from FTRL subroutine:
That is, it uses the classic importance- weighted estimator with Eoww (P) as the importance". A straightforward analysis shows that this estimator yields regret bound of Ö( OVKTT.. However, the denominator term Re [a). is uncomputable because we do not know the distribution of contexts V. One may attempt to circumvent this issue by replacing the expected importance (pe,))pt,(aa) with the empirical importance 1 E Pt.c, (a). It is not hard to see that whether we achieve the desired (()KT) re- gret depends on how well the empirical importance weight EE (4) concentrates around the expected impor- tance weight (P.caa))) However, the empirical im- portance weight TE (t.c, may not concentrate well around the expected importance weight [a]] This is because the probability vector Pt.c is not independent of the previous contexts c,, which makes standard concentration inequalities inapplicable.
p. Σ Ea,c 1 F())
Pr,c arg min
(EA((]]
for each context c, where F(p) = E Ps log(p:) is the unnormalized negative entropy, 17 is the learning rate, and { are loss estimates to be defined later. The algorithm will not sample the action as played in round t directly from pr but from a distribution qt to be defined later.
To construct loss estimates É, the algorithm divides the time horizon into epochs of equal length L. We let Te to denote the set of rounds in the e-th epoch. At the end of each epoch, the algorithm takes a single snapshot of the underly- ing FTRL distribution pa for each context and arm. That is, the algorithm takes
Sc42,(aa) = PeL,e(a)
To address this difficulty, Schneider & Zimmert (2023) di- vides the time horizon into epochs of equal length L. At the end of each epoch e, the algorithm stores the FTRL distribu- tion at the current time t = eL in a new distribution se; that is, it takes (a) = Pt.c( (a) for each context e and each arm a. The algorithm further decouples the distribution played by the algorithm and the distribution used to estimate the loss vector. For each time t in epoch + 2, the algorithm observes the loss (a) for each arm and context e with probability fa) A Ee-u(se,c (c.,(()e.(a)) (a)e)a(aa22) The algorithm then estimates the expected importance sa(a) using empiri- cal importance fe(a) constructing solely from contexts in epoch e + 1. Finally, the algorithm constructs (a) as an importance-weiihheed estimator with fa(a) serving as the importance.
and takes
$1,0(a) = 82,0(a) = K
The index of the snapshot s.+2 for epoch is 2 because we use the snapshot 8e42 in epoch + 2.
For each round E Te the algorithm observes the loss func- tion of arm a with probability fe(a) = Ene [se.e(u)/2) /2). This is guaranteed by the following rejection sampling pro- cedure: we first play an arm according to the distribution
-{ Price
if E [K] Pr,ce (a) 2 S0,00 (a)/2
It,ce =
$e,ez otherwise.
A After playing arm a according to It,e the learner samples Bernoulli random variable S₁ with probability S; O, the learner ignores the feedback from this round; otherwise, they use this loss.
Se,or (a) 24 (a) If
The advantage of their construction is that the empirical importance weight [aj concentrates around the expected importance weight J.(a) now. This concentration ensures that the loss estimates (a) are good estimates of the true
The only remaining unspecified part is how to construct the loss estimates. We group all timesteps into consecutive pairs of two. In each pair of consecutive timesteps, we sample from the same distribution and randomly use one to calcu- late a loss estimate and the other to estimate the sampling
In this paper we call terms like 3em (ewe)pt.c(o)) as the importance weight and call terms like Fe (a)) as the importance.
4

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
frequency. To be precise, let T.' denote the timesteps lected for estimating the sampling frequency and To denote
e(v KT log f)) 7 T. ①
log(1/8) KT
and 7
202 - 6(1/ WKw.oog///// yields regret bound of
the timesteps used to estimate the losses. Then we define
fc(a)
1
$e,0, (a)
(VKTTOO 1
Reg(T) =
LET?
which is an unbiased estimator of fe(a). The loss estimators are defined as follows:
with probability at least 1 - 8 for any policy n.
In what follows, we briefly overview our proof of Theorem 1. The full proof can be found in the appendix.
(ax 1 (A. (a) [a(a) 3
= (A, =0A
27 27
4.1. Regret Decomposition
where y is confidence parameter to be specified later.
Denote the set of all timesteps used to estimate the frequency as T and denote the set of all timesteps used to estimate the losses as T For each t E Te. we define (,,((a) (0) fa(a) (A₁ = a ALETT) We decompose regret Reg(T) = Σr le,ea (at) - -l,ec (Te as follows:
The algorithm is summarized in Algorithm 1. Furthermore, Schneider & Zimmert (2023) showed that the algorithm achieves an expected regret bound of (VVTT).
The algorithm for the cross-learning problem in Schneider & Zimmert (2023)
Algorithm 1
Input: Parameters 7/ and L < T.
Reg(T)
f2 0 for f = 1...,, do
((e) be (Te Σ
(a1,c(at)) le (Tee))
Observe Ct
DET
Play A, $1.ct
82 - 82 + 27.
P2.11
blasi
for E = 2, ...... T/ do
+2 Σ
(a.a(a))) - (e (TTC)
Σ
Proc)(pro-Tokkn Tor ka,)
Sa+1 +- 0
1E77
for f = (e - 11,)), (e 11-1)L+ e...,,L-- do
blasg
Pt.c + arg min
E. (c( - -1 -1((F(p))
+ Σ
Pr(c) - Te, Pr,c)
pEA((K])
LET
for 1' =,, + do
Observe Cr Pt,c, (a) 2 Se,e, 2 all a E [K] then
+2 Σ Σ TET
Pr(c) (prorlec- lec -tho)
Set Atieay Pr.ce
else
blass
Set qi'co Se.cu Play A ~ qe.cp Observe Ar
+2 Σ Σ Pr(c) (preoter - Proo) 1ET
tg.te= RandPerm(t, +)
bias;
Fet1+ + Fet1
set1iry
+2 1E
Σ Pr(c) Ten Pe le,)
2(1/2)
snice (Aee)
Sample St ~ B
24c.re (Aae)
blass
Set (a))((a= = 12(
(a)
[AA = S₁ 1)
In our decomposition, the bias; term refers to the bias in- troduced by replacing the regret over the entire time horizon with that over T and the bias? term refers the bias introduced by replacing regret with its linearization. Both of these terms are not hard to bound using standard concen- tration incqualities. Furthermore, the f'rll and bias; terms are standard in the analysis of high-probabie bandit algorithms. These two terms are not hard to bound using techniges from EXP3-IX (Neu, 2015; Schneider
Set2 < Pt
4. Main Result and Analysis
The main result of our paper is the following theorem. Theorem 1 (Formal). For any 5 E (0, 1), Algorithm 1 with parameters choice = 2 log ( L V log(K)
bounds for
KKT
5

---

High Probability Bound for Cross-Lcarning Contextual Bandits with Unknown Context Distributions
Zimmert, 2023). The bias, and bias; terms correspond to the bias introduced by constructing the importance estimator fa(.. These two terms are the terms of interest to bound.
we will use the key observation mentioned at Section 1.1: different epochs in Algorithm are only weakly dependent each other. To use this observation rigorously, we in- troduce an important technical tool. With a slight abuse of notation, we define a filtration {He]ee in which for each epoch e, the o-algebra H. is generated by all randomness in epochs I,.... E and the randomness Te That is, the o-algebra H. generated precisely by the context et, the random seed used in sampling at Qt,c, and the random
Our decomposition is different from the decomposition in Schneider & Zimmert (2023), This difference is es- sential for deriving high-prot probabbbbyy bound. The key difference lies in the biass term here. This term saves ΣIET: E. Pr(() ( Tee fa,e- - (a.)) term from the bias? term in the decomposition given by Schneider & Zimmert (2023), which is crucial for deriving a high-probability bound.
seed used in sampling S B Se.ce (at) fort S (e-1)L
2qr,e, (mx)
and E T Note that for each epoch e, the o-algebra He excludes the randomness in Te This exclusion is crucial for characterizing the weak dependence structure between epochs.
4.2. Identifying a Prototypical Term
The terms of interest to bound are bias, and biass. These two terms can be bounded using similar methods. Here we take the bias; term as a prototypical term and give sketch of its analysis. Details can be found in the appendix.
Given this filtration, we consider the cumulative bias in each epoch. For each epoch e, we define a random variable
Bias5_ - ΣΣPr(e
Pr(c) (E [TL.((T) ph--1]
( - E, (r.(
To bound biass, define filtration {He such that the o-algebra Hr for each time step t is generated by all randomness before time t. Next, we decompose bias; as
1ET. c
Then
the
prototypical
term
EIETe Ee Pr(c) E (T)((T)) Ho-1 (T,((T))
is
ΣV Σ Pr(c) ( (Te, -l.e) E
exactly E. Bias5g. Our key observation is that, not only
Σ Pr(() (Rra(Te)= - (T.c
Σ Σ Pr(c) (EE [(o((TT) He-1] bLo((ei))
E
EET'
LET
ΣV
Σ Pr(c)
TE [ [e-11] (s,((Te))
as shown in Schneider & Zimmert (2023), but also
TET'
+ Σ
Pr(c) (Pro(Te)- - E { [ProlTe)) Hlmm))
Σ E [Bias,, [Ho] ~ Σ Sa(me)+
E +
Y
BE
This key observation improves the incquality in Schneider & Zimmert (2023) in two ways. Firstly, our bound holds for conditional expectations across epochs, which opens the door to applying martingale concentration inequalities across epochs. Secondly, our new decomposition improves the upper bound from 0 to - Ee T(.-) This improve- ment is essential for deriving a high probability bound.
In this decomposition, the two terms correspond to different components of the bias of the estimator le,e- The first term
ΣIET: Ee Pr(c) (R [Tac [ - (T)) corresponds to the bias introduced by constructing the importance estimator (a). The second term Eiere Pr(c) (Pe,c(TTe= E (T.) He-1) corre- sponds to the bias introduced from the randomness in sampling at from lt- Once again, the analyses of these two terms follow the same principle. We take the first term
Given the new bound Σ. E [Bia55, H.] Ee 7 J. we only need to bound the devi-
ation Σ. Bia55, E [Bias5, | to get an upper bound on Σ. Bias5.. However, we cannot directly apply standard martingale concentration inequalities to E. Bias5, - E [Bias5, He]. This is because we need to assume that the random variable BBas5, < 2L almost surely get a tight enough concentration bound when applying standard martingale concentration inequalities. However, this is not the case. The random variable Bias5, exceeds the constant 2L with a small but positive probability. This unboundness prevents us from getting a tight enough concentration bound when applying standard martingale concentration inequalities.
ΣΣ Pr(c) (E (()c(TTe) Ho-1] ((.((TT)) 1E
as a prototypical term and give a sketch of its analysis for the sake of simplicity. Details can be found in the appendix.
4.3. Analysis of the Prototypical Term
To bound the term
Σ 1E
Σ Pr(c)
EE (T)o(TT)) He-1] (To(
6

---

High Probability Bound for Cross-Lcarning Contextual Bandits with Unknown Context Distribations
To overcome this problem, we consider the indicator func- tion
6. Conclusions
We reanalyze the algorithm proposed by Schneider Zim- mert (2023) and show that it actually achieves near-optimal regret with high probability for the cross-learning contextual bandits problem when the losses are chosen adversarially but the contexts are i.i.d. sampled from an unknown distri- bution. Our key technique is utilizing the weak dependency structure between different epochs for an algorithm exe- cuting over multiple epochs. It is of interest to investigate that whether this techniques is applicable for deriving high probability bounds for algorithms executing over multiple epochs in other problems.
{
Jelaje
Pe 1 Ya, [c(aa [c(aa)
S 2ama
L
defined in Schneider & Zimmert (2023). We show that we also have Ee E. [Biasō, Fel Hc.] ~ - >e Ta( and that the random variable [Bias5, Fel S 2L almost surely. Thus, we can use standard martingale concentra- tion inequalities to get a tight enough concentration bound
Impact Statement
on Ee Bias5, Fe E [Bias5, Fel Hel] and further bound Ee Bias5, Fe. Finally, we have that E. Bias5, F. = Bias5, with high probability. Thus, a high probabil- ity bound on E. Bias5, Fe transfers high probability bound on E. Bias5..
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
5. Experiments
References
Ai, R., Wang, C., Li, C., Zhang, J., Huang, W., and Deng, X. No-regret learning in repeated first-price auctions with budget constraints, 2022.
We conduct a simple experiment to show the robustness and efficiency of Algorithm 1. We consider the following adversarial contextual bandit instance. In round t e [2]. the loss (a) for arm E [K] under context e E [C] is sampled from Bernoulli distribution with expectation cos(a + e)t sin al where a, c, and f are treated as integer- valued inputs to the trigonometric function.
Balseiro, S., Golrezaei, N., Mahdian, M., Mirrokni, V., and Schneider, J. Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32, 2019.
We compare Algorithm 1 against the standard One-Bandit- per-Context (OBPC) algorithm (Lattimore Szepesvári, 2020) on this problem instance. The OBPC baseline algo- rithm is standard algorithm for vanilla adversarial con- textual bandit problems. This baseline algorithm maintains C' independent instances of the standard Exp3 bandit al- gorithm, one for each of the C' contexts. When a context & is observed, the baseline algorithm consults the specific bandit instance associated with & to choose an arm and subsequently updates only that instance. This approach does not share information across different contexts. De- spite its simplicity, the OBPC baseline algorithm is already minimax-opiimal on vanilla adversarial contextual bandit problems.
Dai, Y., Luo, H., Wei, C., and Zimmert, J. Refined regret for adversarial mdps with linear function approximation. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference on Ma- chine Learning, 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 6726-6759. PMLR, 2023.
Han, Y., Zhou, Z., Flores, A., Ordentlich, E., and Weissman, T. Learning to bid optimally and efficiently in adversarial first-price auctions. ArXiv, 0atp20007.05666 2020a.
Han, Y., Zhou, Z., and Weissman, T.
Optimal no- regret learning in repeated first-price auctions. ArXiv, abs/2003.09799. 2020b.
The parameters for our experiments were set as follows. We set the time horizon T 10a, the number of arms K 9, the number of contexts C 1000. The contexts sampled uniformly at random from [C] in each round, i.e., G ~ Uniform((C)). Our results are shown in Figure 1.
Hanna, O. A., Yang, L., and Fragouli, C. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning The- ory. volume 195 of Proceedings of Machine Learning Research, pp. 1791-1821. PMLR, 12-15 Jul 2023.
The results depicted in Figure clearly show that, compared with the OBPC baseline algorithm, Algorithm consistently achieves a significantly lower average cumulative loss and also more robust.
Kale, S., Reyzin, L., and Schapire, R. E. Non-stochastic ban- dit slate problems. In Lafferty, J., Williams, C., Shawe-
7

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
Our Algorithm
Baseline
95% CI (Our Aigorithm)
95% CI (Baseline)
500
Cumulative Loss
1000
1500
2000
2500
2000
4000
6000
8000
10000
Time
Figure 1. Comparison of average cumulative loss for Algorithm and the OBPC baseline algorithm. The x-axis time E [T], and the y-axis is cumulative loss. The bar indicates + standard deviation over 10 runs. Higher curves indicate better performance.
Taylor, J., Zemel, R., and Culotta, A. (eds.), Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
Liu, H., Wei, C.-Y., and Zimmert, J. Bypassing the simula- tor: Near-optimal adversarial linear contextual bandits. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Informa- tion Processing Systems, volume 36, pp. Curran Associates, Inc., 2023.
Kale, S., Lee, C., and Pál, D. Hardness of online sleep- ing combinatorial optimization problems. In Lee, D. Sugiyama, M., von Luxburg, U., Guyon, I,, and Garnett, R. Advances in Neural Information Processing Sys- tems 29: Anmual Conference on Neural Information Pro- cessing Systems 2016, December 5-10, 2016, Barcelona, Spain. pp. 2181 2181-2189, 2016.
Neu, G. Explore no more:
Improved high-prohability re- gret bounds for non-stochastic bandits. In Cortes, C., Lawrence, D., Lee, D., Sugiyama, M., and Garnett, (eds.), Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, December 7-12, 2015, Mon- treul, Quebec, Canada, pp. 3168-3176 2015.
Kleinberg, R. D., Vieulessu-MMzhh A., and Sharma, Y. Re- gret bounds for sleeping experts and bandits. Machine Learning, 80:245-272 2010.
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cam- bridge University Press, 2020.
Neu, G. and Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Con- ference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3049-3068. PMLR. 09-12 Jul 2020.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandii approach to personalized news article recommendation. In Proceedings of the 19th Interna- tional Conference on World Wide Web, WWW '10 661-670, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 7781605587998 doi: 10.1 14/11727690 1772758.
Neu, G. and Valko, M. Online combinatorial optimization with stochastic decision sets and adversarial losses. In Ghahramani, Z.., Welling, M., Cortes, C., Lawrence, N.,
8

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
and Weinberger, K. (eds.), Advances in Neural Informa- fion Processing Systems, volume 27. Curran Associates, Inc., 2014.
Saha, A., Gaillard, P., and Valko, M. Improved sleeping ban- dits with stochastic actions sets and adversarial rewards. In Proceedings of the 37th International Conference Machine Learning, ICML'20. JMLR.org, 2020.
Schneider, J. and Zimmert, Optimal cross-learning for contextual bandits with unknown context distributions. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M.. and Levine, S. (eds.), Advances in Neural Informa- tion Processing Systems, volume 36, pp. 51862-51888 Curran Associates, Inc., 2023.
Syrgkanis, V., Luo, H., Krishnamurthy, A., and Schapire, R. E. Improved regret bounds for oracle-based adversarial contextual bandits. In Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3135- 3143, 2016.
Villar, S. S., Bowden, J., and Wason, J. Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Bene- fits and Challenges. Statistical Science, 30(2):199 215, 2015. doi: 10.1214/14-STSSUW
Wang, Q. Yang, Z., Deng, X., and Kong, Y. Learning to bid in repeated first-price auctions with budgets. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th Interna- tional Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 36494 36513. PMLR, 23-29 Jul 2023.

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
A. Useful Lemmas
Lemma (Freedman's Inequality). Fix any > 0 and E (0, 1). Let X, be a random process with respect to a filtration Fe such that μ E [X, Ft-1] and [ Fr-1]. and satisfying XX; S Then, with probability at least 1 8. we have for all
log(1/0g (//)
Σ X Ma 8=1
The next lemma is about the following family indicator functions.
Definition 1. For each epoch e, we define the following two indicator functions:
Va, Va. [clla) - So(a) max {
Sela)e
2 L
Fe 2
and
Le 1
max cE(C),aC(K)
We further define the following indicator function:
T/L
G F.L.
Lemma (Lemma and Lemma 7, Schneider & Zimmert (2023)). For any epoch e, the event Fe holds with probability at least - 2K exp(-t). and the event Le holds with probability least exp(-t). Furthermore, the event G holds with probability at least 1 - exp(-i).
Lemma (Lemma 8, Schneider & Zimmert (2023) Let 2 7, then under event Fe, we have that
< fe(a) +7 2. (a(a) + +
The next lemma is about the following auxiliary probability vector.
Definition 2. For each epoch e and each time step Tex we define
e-1 1
Pt. arg min PEA(K])
p.
Σ
Σ V'ET.U
Tre 17
F((p)
e'=1
where F(p) = EK log(p:) is the unnormalized negative entropy.
It is easy to see that Pr,c Setl, exp (-n EveT_.ee Eve.)
Lemma 4 (Lemma 9, Schneider & Zimmert (2023) ). If 2 4: and <
log(2) 5L
then under event G, we have for all
t E Te. a E [K],c [C] simultaneously
(a) 2 Pt.o(a) 2 sa)c and
(s),((a) 2 Pr.o(a) 2 (a,
This implies that
Bea (t, S 4fc(a). (env(pe,((a)] 4f)(a) and
In addition, this implies that qi Pt for all Te- Definition 3. We define pr(a) A (eoww(pr,c(a)) and (a) & Rown (a)) for each time step and each arm a.
10

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
Lemma (Lemma 10, Schneider & Zimmert (2023) ). !f 16s and exp(-1) 8k then
fe (a) - (a) - 1 Fe He-1 0.
? fela)
S E
Se (a) + y
Lemma 6. For any 202 ?
10c I, 2 Log(8K/7)) we have
Σ TET'
Pr(c) PL. pr Pe -
98KTr
L + LKT
Proof. The proof of Lemma is contained in the analysis of the bias; term in Schneider Zimmert (2023).
Lemma 7. Decomposing all time steps into consecutive pairs, specifically, decomposing (1.2...., T into
Constructing surrogate loss sequence {L,) such that for each surrogate time step the loss vector Eg is uniformly sampled from the pair of true loss vector (125-1, l2s). Denote the time step sampled from the pair (2s - 1, 2s) st. For any constant ò E (0, 1) and any bandit algorithm such that in each pair of time steps (t - t), the algorithm takes actions a and from the same distribution Pt- Pt. we have
{(1,2 (3,44) (t.,....
T
Σ
(caa(a)) be (T, $2 Σ aml
(Paca (ase) - Eaco (Trcse + 2/ T Tlog(
with probability at least 1 5.
$ Proof of Lemma 7. Consider the sequence of random variable {Y,).=, such that
Y. 1120-1102-110222 l2-- 1,0211 (Te
+ l2s.0r (a2e) l20,020 (Tezr)
2 (Ca.cup (asz) Earcn (TTes))
Consider the filtration { such that for each s the o-field H. generated by the randomness within e and a; for
2
t 5 2s and the randomness within sampling from pair (2r- 1,2 for each S s. is easy to see that the sequence [Y) forms martingale difference sequence adapted the filtration { Moreover, it is also easy to see that Y. S 2. Using Azuma-Hoefiding' 's inequality, for any constant å (0, 1), have
z Σ Y. 2 T log(
with probability at least 5. This completes the proof of the lemma.

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
B. Detailed Proof of Theorem 1
B.1. Decomposition
As we mentioned in Section 4, we decompose the regret as
Reg(a)
Σ
(at)
EE - -2
Σ
le (0r) le (Tei)
1=1
IET'
bins:
+2
Σ
la - lalaaatee (Tec) Σ Pr(c)(pic Tes luo)
IET
biasz
Σ Pr(c)(p.c Te, Re,e)+ +2
Σ
Σ
Pr(c) (prce - Rao)
+2
1ET
1ET
Arl
biusg
Pr(c) (prcotra Pas Baa) +2
Σ Σ
Pr(c) Thes Eee (xc)
IET'
IET'
bin84
biass
We bound these terms one by one.
The bias,, biasg, ftrl, and bias; terms are not hard to bound. The terms of interest to bound are bias, ans biass- We first bound these two terms. In these two terms, the bias; term the one easier to bound. first bound bias; to provide some intuition for our readers.
B.2. Upper Bounding biass
We first bound the fifth term ΣIETi E. Pr(() ( (Ter ).o). We decompose the fifth term into two components:
Σ Σ Pr(c) ( (Tester k1,0)
AET!
Σ Σ Pr(c) (Beo(Te) lec((Te))
ET
Σ Pr(c) E [(c((TT)) He-s] ((c((T)) ST
Pr(c) (Pe.a(Te) - E ( Hoel))Hee)))))
tE
We bound these two components separately.
For each epoch e, we define a random variable
Bias5, -ΣΣP((e Pr(c) (B (ea((Ta He- (
1ET.
We rewrite the term ΣIeT: E. Pr(c) IF (e)((T)))
(e)(Te)) as ΣT/L Biass Recall our key observation:
different epochs are only weakly dependent on each other. We bound the summation over epochs -T/4 Bias5, by leveraging the weak dependence structure between (Bias5a)..
The sequence of random variables (Bias5.) e has the following properties:
1. For each epoch e, the random variable Biasã, is measurable under a-algebra He.
12

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
2. For each epoch e, have
E2
Biasse -Fe He-1]
fo(TT) (c( + + -1 Fe He-1
Σ Pr(c) Σ AE
(TT)(TT)
We further have
To)
E
-1
Fe Ha-1
Fe (TT) + 5
(c(
(a(TTe)
fc(TT)
E
- 1
Fel He-1
(TT + +3 fc(Te) +9 fe((e) t
(fe(Te)) - fc(TT)) - -
fT(TT)
E
Fel He-l
7
E [Fal He-1]
Jo(Fa) +7
fa(TT) + 37
[a(TT) +
s fT() +y
E [Foc He-1
(Lemma 5)
S fT( +y
7
(1 2K exp(-
(Lemma 2)
Thus we have
E Biass -Fel He-1]
Pr(() Σ (e.c(Te) fe(TT)) +
7 (1- 2K exp(-
LET!
3. For each epoch we have
Bias5, Fe S
Σ Pr(c) Σ
(r.((Ta)) He-1 Fe
DET!
Σ Pr(c) Σ (T((TTT) fo( Fe
fo(TTe) + 37
RET!
(Te(
$ Pr(c) Σ (T((TT)
(Lemma 3)
fc( +
LET!
32i.
2L
'Readers familiar with Schneider & Zimmert (2023) may wonder why we do not directly consider Bias5, G but consider Bias5, F. instead. This is because there is small flaw in the argument of Schneider & Zimmert (2023). Schneider & Zimmert (2023) essentially argues that TE Bias,, G He-1] B[Bias5_ He-1] E[G] He-1]. However, this equality may hold since the indicator G depends on Bias5, and these two terms are not conditionally independent given He-1- This why we consider Bias5, F. here instead.
13

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
4. For each epoch e, have
E (Bias5e Fo)2|He.
2
fo(To) - (o(TTT) - 3 Pe.
= E Σ Pr(c) Σ
(ea(FF)
|
Hoo-1
Se(Te) + -/17
IET
fc( - -P((Te)
3
B B
Σ
((,)(TT))
Fe
Ha-l
fe fe( + -/27
IET.
Sa(TTo) - -e((TT) 3r
Pr(C)( Σ 2
Fe
He-1
Fe( + 2
IET!
fc(TT)) f(((Te) -27 Pr.
L Pr(c) Σ
C E
HHn-1
[e( + +227
LETS
fe(TT)= - ((() fe( +7
-
2
S 4L Σ Pr(C) Σ
ELEEE
Fe
l
(Lemma 3)
1ET
Pr(C) (TT( +7)²
4L
Σ (ee(TT) E
(f((Tc) - (((e)))(TTT)) - 2²² He-1
3 3) 2
IETO
AT.
(f((TT)) - Sc(TTo)) 2 H 1
Pr(C) (Fe(TT)) +7)²
Σ
(no(TT)
E
+ 11)
IET!
4L
[fe(Te) (TT)
+ 9 41²²
PT(C) (Te) +7)²
Σ
L
1ET! 1ET!
91.7
< Pr(c) Σ (i((Fe)
[e(TT) +7 4(Sa(TT) + 77)
IET!
361
<4> Σ Pr(c) Σ (1,e(Te)
fe(
IET!
Given these properties, use Freedman's inequality get that for any 0 < X 3 with probability at least 5, have
Σ Bias5, F. - -iiis,,, Fel He-1] S 4A Epr(c) Σ (e,(TT)
Pr(c)
36c
log(1/0)
(T +
27
A
TET!
We further have that event 1 Bias5 F. = Ee Biasō.} holds if event G holds. Combining these two facts, we get that the inequality
36c
log( (//))
Σ Bias5.- B[Biass Fel He- < 41 Σ Pr(c) Σ
(T,
[o( +7
TET!
holds with probability at least Pr(G)- - 8. We now bound the second component
ΣΣ Pr(c) (Beo(TT)) E [Tnn(Tee) He-1))
1ET
The second term ΣIETo Ee Pr(c) (Ric(Tr)) - E (ea((T)) pl--1) ((e
has the following properties:
14

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
1. The sequence of random variables Pr(c) (ProlTee) - E (Fo) (e-1l))
forms a martingale difference
LETE
sequence with respect to the tfiltration {-
2. Each random variable Ee Pr(c) (PLA(TT)) E (CnolTe) Ho-il) satisfies Ee Pr(c) (Rro(Tee) EE [Caol(te) Ho-1))
3. Each random variable E. Pr(c) (Puc(Te) - E [Rlc(te)l H1-1) satisfies
Var Σ
Pr(c)lec(TTO) Hi-1
S Σ Pr(() Var ((eo(TTo) H
Σ Pr(c) Salma) [2( 222
(fe(Te) + 27)
Σ Pr(c) So(Fe)
2lba((Te)
(fe(Te) + z/))
Applying Freedman's inequality to the sequence of random variables {E. Pr(c) (Fec(Te) - E [eo(Tee) ((-1)) IETT.
get that for each 5 E (0, 1) and each 0 < À < 7, with probability least have
E Pr(c) (Pao(TT) EE [[ro(Te)) Hl--)) ( IET'
< Pr(c) Se(TTo) pleco(Tee + x log(5)) 1ET
(Fa(Te) + 37)
By assuming that event holds, we further get that with probability at least Pr(G) 8, the following inequality holds:
ΣΣ Pr(c) (Beo(TT) - ((((F Ho-1l)
1ET
Pr(c) fe(TT)
1 1
<41
(Se(Te) + +7) + pllco(Te)
x log(
(Lemma 3)
Combining all previous inequalities, we get that for any < A1 < 322
and < d2 < 7 the following inequality holds with
15

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
probability least Pr(G) -2::
Σ
Σ Pr(c) To (Toste--ee (ea)
TET! e
Σ Epr(c)
Pr(c) (B (TTal(TTe)) H ((p((Te))
1ET
Pr(c) (Prollte)= - E (eraltee Her-))
+
1E
Bias5, - B[Biase Fel HHe-1l
+
Biass Fel He-11
Σ Σ Pr(c) (CaalTT))= - E (((a((tt)) He- 1 1)
+
1T
36
log(1/0)
<4>1
Σ Pr(c) Σ (T()
fe(TTe +7
A1
IET1
Σ Pr(c) Σ (T(((T))
7
(1 - 2K exp(
Se(TTe) +
IET!
4
Σ Pr(c)
Se((T)
logl 1 g).
(Fe(Te) + t))
Xa
LET7
Note that in the previous analysis, we combined two good events each happening with probability at least Pr(G) 8. The combined good event happens with probability Pr(G)- - 25 rather than the vanilla union bound 2(1 Pr(G) + 5). This is because, in both events, the Pr(G) term comes from assuming event G happens. Thus, in the combined event, we can simply assume event G happens and count the corresponding bad event G only once. We will use this small trick repeatedly in the following analysis.
We pick X 8.36c and A2- I to get that the following inequality holds with probability at least Pr(G) -25:
ΣΣ
Pr(() ( (Ter Bi, - lec)
1ET!
36c
log(1/8)
<4x1
Pr(c)) (lee(Te) fe(
+
d1
TET?
Σ Pr(c) Σ (e.e(TT)
(1 - (1-2K exp(-())
fe( +
tET
+ 4 Σ Σ Pr(c)
(Se(TT)) + + (lo
fe(TTe)
1 1 +
Aez 10g(
ET
8: 361
+ -) log(1/0) + EPr(c)
8
Pr(c) Σ (Te
7
2K exp(-()
Le [e( +
7
8. 361
8
<(
) log(1/8)+ KT exp--))..
+ 7
7
16

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
B.3. Upper Bounding bias,
We then bound the forth term EIET' Ee Pr(c) (uicstu Eeo) follows:
Similar to the previous analysis, decompose it as
ΣΣ
Pr(c) ( (prcstec-uus Rmc)
1ET'
ΣV
Pr(c) (pros B [Peo ( (He-ll)
Ee,ol
ET
Σ
Σ
Pr(c) Precoees Paac--i -Re -Be [1u Ee, He-1)
LET
We bound these two components separately.
Similar to the previous anlaysis, we decompose the first component
EPio [Tu.c - Eel H6-1)
BET
ΣΣΣrree Pr(c) (e(()((proo) (heer [eeo Ped He-1l)
TET!
For each epoch e we define a random variable
Bias4 Σ
Pr(c) pt,es B [e - Ee,ll (el Hb-1))
IET!
We need bound E. Bias4c.
We decompose Ee Bias4, Ee Bias4 F. + Ee (1 - Fe As usual we have that E. Bias4. F.L.)) 0 whenever event G holds. Thus we can focus on bounding D. Bias4, Febe. Firstly we bound
Σ E Bias4, Feboo Ho-1].
We have
Σ E Bias4 Fabel He-rl
Σ
E
Pr(c) (pror E [2o0 - Paoo Ho-1) 1) Fe FeLe He-l
LET!
e
Σ
E
Pr(c) (r, Pr,c, TE [Teo - Pe,c (o--1) Fetro Ha-1
e
LET!
By Lemma 6, the latter term
Σ E Σ Σ Pr(c) (p.c Pr,cs E Peo Eee Hi- 1) Febe Ha-
bounded by 98AТT 7 LKT Furthermore, condition on Ha-1, the indicator function is effected only by randomness
17

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
within time steps E Te thus the indicator function Pe conditional independent with the probability vector Pe.e- We have
Σ E
Σ Pr(c) (Pr.c [ha-- -h.c (l--1) Fel He-l
LET
Pr(c) E
[prcc He-1] E (lea Pe.c He-1
1ET
Pr.cla)) fela)
Pr(c) Σ
(Lemmaa 5)
1ET
By Lemma 4, whenever event G holds, the ratio Pa.la) T.(a)
< 4. Thus we have
Σn E
Σ Σ LETT
Pr(c) (Prer TE [he Ee,al Ho-1l) Pe Ha-l
S K4yKT
whenever event G holds.
We further have (pr.cr E [e.0-
End He-1)) 2. Thus we have
Σ E
Pr(c) (pr.cr B [T. - Real He-1) FalLe 1) He-1
FET!
E
Pr(c) FelLe - -1]/ He-1
IET!
Pr(c) Lee 11 Ho-l
IET
K Kexp( 1)T
(Lemmaa 2)
Thus we have
Σ E
Pr(c) (pr.c: F. [Tco - Peol -Red Ho Ho-1)) Fetrel He-1
TET!
<4 + K eexp(-1)1
whenever event holds.
Thus have
Σ EE Bias4, FeLel Ho-1] < 4K+T K <exp(-1)T
98KT: 3 LKT
whenever event holds.
then only need to bound the concentration term
Σ Bias4_ F.L.- E [Bis4 Febee Ha-1]
For each random variable Bias4, F Felse we have
18

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
B FeLe
ΣE LET!
Σ Pr(c) (peco E [2200 - -Raol Hom1) 1)
Fele
Σ 1ET.
Σ Pr(c) E [pro(W)sola)leoooo [T(a)+ +7 fe(a) + +
FeLe
- [(aa-f((a)) + +
ΣV IET!
Σ Pr(c) [mnclofee(()aoo
FeLe.
(fe(a) +7)((((a) + +12))
Thus we have
Bias4 Fe FeT.el
Pe(a) Se(a) + +
Σ Pr(c) Σ [(rcla)(((()hcaa))) (fe(a)+ + (c) + +1))) IET!
Febe
Fa(a) - fe(a) + +
(a(a)
Febe
fe(a) + 1
1ET
fe(a)c L L
<8
max
(ET!
Ki Ki
<8L(\
L
L
=8(vKLe + Kt).
Applying Azuma-Hooffding's inequality to
Σ Bias4 FeLe- E [Bias4, Felel Ho-1]
we get that for any 8 >>0 0, with probability at least - 8, we have
Σ Bias4, Fale - E [iiss Fe Feel Ho-1]
T <8(V Ko) \ 2 log(
8 2
=8 (VeRT.boR 1ogT
TK2
2) + 1+12
1 log (
L
Thus we have
Σ BiasA FeLe
<4KYT + Kexp(-1IT 98KTi LKT
L
+8 (V2KTolosr (2gT
+ V2 TK²
clog(
(
8
L
19

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations with probability at least Pr(G) 8.
We then bound the second term
ΣΣ Pr(c) ( (prci Pe, - -e,c E [e, Endll H1-1))
For each time step E Te we define an indicator function
J 1 (a) s 4fe(a)).
By Lemma 4, event G implies J,. Similar to previous analysis, we decompose the first term as
Σ
E Pr(e) (pics Eec - Ebe E [leec - Ee,ol (o-1))
ET
Σ
Σ Pr(c) (presfes Pe.c Eep E [Teo Pe, He-1 FeJs
ET
Pr(c) (pror Be, - Peo - IR lec Pe H1 (4-411111) (1 Fedi).
1E
Since the auxiliary probability vector Pt.e is determined time the indicator function J/ is also determined time t 1. Furthermore, the indicator function F. is determined epoch 1. Thus the product of indicator functions F.J, is measurable under filtration H--1. We have
Σ Pr(c) (pros Pen -2,c- E [Tro End (H--)) FaJel Hh-l
E
Σ Pr(c) (pecoteee - -ec)) -B [(te Te,c) He-1) He-1
= F.J. EE
=0.
Thus the sequence of random variables
Σ
Pr(c) Prccee.c - -2,,- - E 12.00 - Zeed He-_1) Fodl
IET
forms martingale difference sequence under the filtration (He tc- We further have that the term
Σ Pr(c) (pros Ee,0 - -r,o - E Eno Rencl Ho--l) FaJe
20

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
satisfies
Σ Pr(c) ( (pe.o lec - Ee, - E [1.c - Eeo HeddH FeJe
1(a:= = a) (e((a) +7 [C(a) + FeJe
fe(a)
x Σ Pr(c) Σ Pric(a)(ro(a)
1(a+= =a]
Sc(a) _
Σ Pr(c) Σ (pro(a)le,(a)))
FaJe
Po(a)+ + + Pe(a) + ///
Pr(()p(,((a)) ((((at)) FeJe
fe(at) +7
Pr(c) Σ (t.o(a)eeaaa)) Sc(a) F.Js
FeJ.
(a(a) +
Σ Pr(c)prolar) (g((ar)) F.J. fe(ar) + 37
Σ Pr(c) Σ P(.((a)(ec(a)) fe(a) FeJe
fc(a) 3n
(((e)) +1+ pi(as) Σp((a) fe(a)
Fej
felat) +7 fe(ai) + 3
fe(a) + //
14+1+ 8 15.
(Lemma 3)
Applying zzuma-Hoeffdiig inequality to the sequnece random variables
Σ
Ert(c) Pr(c) (prcs Eec -2,e - -e,c--B E [2o0 - Eeell Ho-1)) Fede
LET1
we get that for any 8 > 0, the inequality
ΣΣ
Pr(c) (proo - -B B[Tro End H(-l) FeJr S 15 Tlog(
LET'
holds with probability at least - 8. On the other hand, note that event G implies event FeJr, we get that
Σ PI(c) Pr(()
(pr Eio - Dra E Tec - Ear Ho- (1 F.J.) 0
LET
whenever event holds. Thus we get that for any 8 > 0, inequality
ΣΣ
(r - - [ho - Prool H1-1l) s 1 T Tlog( 1
EET!
holds with probability at least Pr(G)- 25.
21

---

High Probability Bound for Cross-Lcarning Contextual Bandits with Unknown Context Distributions
Combining previous results, get that the following inequality holds with probability least Pr(G) -20:
Σ
Σ Pr(c) (pr.s Ee.e - Rec)
1E
Σ
Σ Pr(c) (prco E [TL6 - (ecc)Hle11)
1E
Pr(c) ( (prootta beaa -lep - E [Fe - Peool Hel-1)
IET1
K Kexp(-1)
7 + 98KTL
LLKT
<4KYT+ +
L
V V2KTolog( () + +/22 2 :log( (
TK²
+ 8
1 T Toog(
B.4. Upper Bounding Remaining Terms
The remaining terms are the bias1. bias2, ftrl, and bias; terms. These terms are not hard to bound using techniques in standard EXP3-IX analysis (Neu, 2015). We write down these analyses in the sake of completeness.
B.4.1. UPPER BOUNDING bias
Applying Lemma on the loss sequence used in calculating loss estimates, we get that
(as) le,es (Te:)) -2 Σ
(aie le,ce 2 T Tlog(
SET!
B.4.2. UPPER BOUNDING bias?
Here we bound the bias, term
Σ
(as))as)) (eoc(Tee) Σ Pr(c)(Pre Te, norlao)
TE
Whenever event G holds, we have Pt. Thus we assume event G holds and replace the bias, term by
(a,a - (F, Σ Pr(c)(atc - Teg (cee
RE
The new term have the following properties:
The sequence of random variables
{
(hoalar) - le,0r (Tx))
- Pr(c)(aroo Tested)
rET
adapts to the filtration (Hihere.
The sequence random variables satisfies
E
le (us) be (FTe)
Σ
Pr(c)(arc Tes ledl He-l
0.
22

---

High Probability Bound for Cross-Lcarning Contextual Bandits with Unknown Context Distributions
Each random variable satisfies f,,e, (ue) f1,cc (Fee) E. Pr(c) Ter (,,)) E [-
By applying Azuma-Hoefdding inequality, we get that for any å E (0, 1), the following inequality holds with probability at least 1 - 6:
(ac((a)) le (Tei)
Σ Pr(c)(at.c
- Tes lee)
LET'
/ Tlog( )
Thus the following inequality holds with probabiity at least Pr(G) 6:
Σ
(aa((a))) - (Te)) Σ Pr(c))pte Te, (eeeee) s (lo
TET
B.4.3. UPPER BOUNDING FTRL
Here bound the ftrl term
ΣΣ Pr(c)(Pte LET1
Exrreeepns - Tas Reod-
By the standard analysis of FTRL algorithms, the ftrl term satisfies
Pr(c)(p(.c - Te, Pec)
1ET!
1 log K 17 Σ (prosPec))
Here Rg denotes the vector formed by squaring each component of Le,c-
By Lemma 3, under event G, we have &,,0 S 20,.c- Thus assuming event G holds, we can focus on upper bounding
loogk+2 + +2
Σ (pecs Riel)
Σ
ET
suffices to upper bound Σ. Pr(c) ELETe (prer P.o) We have
Pr(e) Σ (Prcr Pice
Pr(c) Σ
Pr.caat)
*ET!
Enio(a ((((ar)
Pr(c)
(Sa(ar) + +r)²
LET'
Pr(c)pe,c(ar) (fo +7)²
1T7
pe(ar) (fe(ar) + 7)
Σ
ET
23

---

High Probability Bound for Cross-Lcarning Contextual Bandits with Unknown Context Distribations
By Lemma 4, under event G, we have
pr((e) 22 EET (Se(m)) +7²
Σ
Σ TET! fc(ar)+7'
We then focus on upper bounding EIET! Iela))7'
We have
The sum of conditional expectations ELETe E folai)ty
1 Hy-1 S KT.
Each term Ja(a))+y 7
The sum of conditional quadratic expectations
(Folat)t)
2 fela)) +7
Σ ET
1
fela)
+7))
TET'
fe(a) +r
TE
By Freedman's 's inequality, we have that for any x E (0, 70 and any 8 E (0, 1), the following inequality holds with probability at least 1 - 6:
< <.ΣΣ +
1
log( 1 ( + KT.
TET' a fe(a) +7 x
TET
We pick À = y to get that
1 0
Σ IET!
fc(as) + < 2KT + log( log(
with probability at least 8.
Substituting this inequality back, get that the folowing inequality holds with probability at least Pr(G) 6:
Epr(o)
- log
K
17 Σ 2
Precs Pio)
17
ET
log K + 4n
Σ
Solae) +7
1)
LET1
< log + an 2KT + 1
108(
B.4.4. UPPER BOUNDING biasg
Here we bound the biass term
Σ ΣΣPr(e Pr(c) (pres le, Chessaa--eed -tn)) 1TT
We decompose
Σ
Σ Pr(c) (prosfeo t.o)
TET
Σ Σ
Pr(c) Sereeree E 1ed B[eed
H(-1))
IET'
+
Σ
Σ
Pr(c) (PLc. B [ee No-1] - te.))
1T
c
24

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
The first component satisfies
E
Σ Pr(c)
(pr le, E
[r,l Ho-1)
NE
E 1E
Σ
7 Pr(c) Σ (ptcla)lec(()) fc(a)
Σ Pt(a) 7
+7
Assuming event G holds, we have
Σ Σ Pc(a)
fe(a) +7
1E a
2KT
(Lemma 4)
EET'
We then bound the second component EIero E. Pr(c) (prcs E [dcll He-1] - -ao) an indicator function
For each time step E T we define
L - 1 (Va, - 4fc(a))
By Lemma 4, event G implies event Lt Thus we have
Σ
E Pr(c) (pc.: 1E [1. He-1] E1.))
TE
Σ
Pr(c)
(pr.c. E
- E1,c Lt.
TET'
under event G. We then assume event G holds and focus on upper bounding
Σ Σ Pr(c)
(p... E Te. Ne-1] Eec)) Lr.
1ET
Since the probability vector Pt.c is determined at time t 1, the indicator function Le is also determined at time 1. Thus the summand random variable
Σ Pr(c) (prcs E. [eccl He-1] teo) T.
satisfies
Pr(c) (pres F. [Tro (P tea) Tue Ha-1
Σ Pr(c) (pres E [Erel [4 t,c) | L
Thus the sequence of random varialbes
Σ Pr(c) (prer E Eeel N4-1] - teo) Lg
SETe
forms martingale difference sequence with respect to the filtration (Hi
25

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distribations
The summand random variable further satísfies
Epr(e (proo tec) Lt
-E Pr(c)pnc(a)) leclas)) L felai) +7 1
Σ Pr(())p,c(a)) fe(ai) +9 Lt
pr(as) Lt
[e(a;) +7
54.
Then by Azuma- Hoena--g inequality, the following inequality holds with probability at least 1 - 8:
Σ TET'
Σ Pr(c)
(prer E3 [ccol pl--1] - Eso) La s 4v Tlogl
Thus we have
Σ
Σ Pr(() (pees E [add Ho-1] Ee.) S 4v Tlog(
1E
with probability at least Pr(G)- 6.
Combining the first component and the second component, we get that
Σ
Pr(c) EPrc)) (pr.ores lec - (
-Ee) S 44 1 2KT
LET
with probability at least Pr(G)- - 6.
B.5. Combining the pieces Combining all previous arguments, we get that
Reg(T)
<2
7 log(
8
Tlog( 1 8)
+41
log ())
+2
log K + 817 2KT + 7
+8
Tlog( 5) + 4KTT
K Teep(-10
+2 98KTT
+2 - LKT
+8K7T +2
7
TK2 ② + +2
+16
22T log(
L 1logl
2
+30
Tlog( 8
8 36x
+2(
+ 2- log(1/0) - 2KT 2KTexp((-))
7
26

---

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
with probability at least Pr(G) 86.
Taking = 2log(8KT)).
KTT K)
-6( V6 KT log ()), 7 = 16s (1 RT
@(v
and 1 2(2
I
6(1/v KT (Tog((//)))))) it is easy to that Reg(T) = Ō(V KT {) with probability at least Pr(G) - 86 N 1 96 for any policy and any ā E (0,
The final step is rescaling the probability constant by a factor of 1/9, which gives that Reg(T) =O(V KT log {)) with probability least 1 and ends the proof of Theorem 1.
27


Reviews:
[{"review_id": "PgtRpGCP9o", "reviewer": "Reviewer_Kzo3", "summary": "The submission studies contextual bandits with cross-learning, where the feedback information is the loss of the chosen action in all contexts. The main result is a regret bound that holds in high probability, which improves on a previous bound that holds only in expectation (Schneider & Zimmert 2023).\n\n\n## Update after rebuttal\n\nThe authors' reply addressed my concerns. In light of this, I have revised my recommendation to weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Kzo3,\n\nWe sincerely appreciate your valuable suggestions and thoughtful feedback. Below, we address each of your concerns in detail.\n\n---\n\n**Question: The impact of our results on the theoretical community**\n\nThe reviewer noted that “the result seems to be a specific treatment to a specific algorithm and seems to be incremental.” We respectfully disagree with this assessment. We would like to emphasize that in the field of adversarial bandit research, providing high-probability bounds is a widely recognized and significant contribution in its own right (e.g., [1, 2, 3]). From a technical perspective, our argument for the high-probability bound is novel. Specifically, we decompose the regret across different epochs and leverage the weakly dependent structures between these epochs—a method that, to the best of our knowledge, is not commonly employed in existing high-probability bounds for adversarial bandits.\n\n---\n\n**Question:  the suggestion for empirical verification on realistic datasets**\n\nWe thank the reviewer for raising this point, as it highlights an opportunity to strengthen our work. In response, we will include experimental data in the revised version of the paper to reinforce the need for a deeper theoretical understanding and to complement our theoretical findings.\n\n---\n\n**Question: the mathematical definition of cross-learning in Section 2 [110R]**\n\nWe are grateful to the reviewer for pointing out this oversight. While we provided an explanation of cross-learning in [122R], we acknowledge that a clearer presentation is warranted. Based on your suggestion, we will introduce a standalone definition of cross-learning in the revised version to ensure this concept is explicitly and effectively conveyed.\n\n---\n\n**Question: What is the mathematical meaning of \"weakly dependent\" [110R]? Where is it used in the derivation (which inequality in the appendix)?**\n\n\"Weakly dependent\" is an informal term commonly used in the context of concentration inequalities([4]). It generally refers to a sequence of random variables $X_i$ that, while not fully independent, forms a martingale, allowing us to derive concentration inequalities akin to those for independent random variables. In our work, it means that we can decompose the regret into epochs and  the regrets of different epochs form an martingale sequence.\n\nThis property is utilized wherever epoch-based decomposition appears in our proofs. For example, it is applied in bounding $\\sum_e \\text{Bias5}_e$ in Appendix B.2 and $\\sum_e \\text{Bias4}_e$ in Appendix B.3.\n\n---\n\nOnce again, we express our gratitude to the reviewer for their insightful and valuable feedback. These comments have greatly assisted us in refining the presentation of our paper and better articulating its contributions. We hope that our responses adequately address your concerns and that you will consider increasing your support for our work in light of these revisions.\n\n---\n\nReferences:\n\n[1] Luo, H., Tong, H., Zhang, M., & Zhang, Y. (2022). Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs. International Conference on Algorithmic Learning Theory.\n\n[2] Neu, G. (2015). Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Neural Information Processing Systems.\n\n[3] Bartlett, P.L., Dani, V., Hayes, T.P., Kakade, S.M., Rakhlin, A., & Tewari, A. (2008). High-Probability Regret Bounds for Bandit Online Linear Optimization. Annual Conference Computational Learning Theory.\n\n[4] Pelekis, C., & Ramon, J. (2015). Hoeffding's inequality for sums of weakly dependent random variables. arXiv: Probability.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The technical contributions are as follows.\n - The submission proposed a novel way to decompose the regret. The new term contributes a negative term (lines 297R and 637) to make the high probability bound possible.\n - The newly introduced term is unbounded, hence, a surrogate indicator function (lines 324R and 452) is designed to make the sequence of epoch values a martingale difference sequence. \n\nWith the two modifications above, Freedman’s inequality can be applied to provide a high probability bound.", "theoretical_claims": "I have read appendices A, B1, and B2 and browsed through the rest of Appendix B.", "experimental_designs_or_analyses": "There is no experimental result; the submission is a theoretical paper.", "relation_to_broader_scientific_literature": "The way the unbounded sequence is handled, which makes martingale concentration analysis possible, could benefit concentration analysis.", "essential_references_not_discussed": "I am fine with the related work discussed in Section 1.2.", "other_strengths_and_weaknesses": "Weaknesses\n- Although clever, the impact of the techniques developed is unclear. Currently, it seems to be a specific treatment to a specific algorithm and seems to be incremental (from the perspective of the result). That is, the impact of the proposed technique on the theoretical community is unclear.\n- The main context mentioned several practical cross-learning applications. It is not clear whether the algorithm developed in this line of research (Schneider & Zimmert 2023) outperforms conventional contextual bandit algorithms. An empirical verification on realistic datasets would reinforce the need to develop a deeper theoretical understanding.\n- Cross-learning is not defined mathematically in section 2 [110R].", "other_comments_or_suggestions": "Please see the comments in the above parts.", "questions_for_authors": "What is the mathematical meaning of \"weakly dependent\" [110R]? Where is it used in the derivation (which inequality in the appendix)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jf5Q7OGvvR", "reviewer": "Reviewer_JF8C", "summary": "This paper provides a high probability bound for the cross-learning problem in Schneider & Zimmert, 2023, where a regret bound is provided in expectation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JF8C,\n\nThank you for your positive feedback. We answer your question below.\n\n---\n\n**Question: the significance of this term $\\sum \\sum Pr(c)  <\\pi_c, \\tilde{l} _{t, c} -  l_{t, c} >$**\n\nTo achieve a high-probability bound, saving this term is essential. In Schneider & Zimmert (2023), this term is not saved. Thus they need to bound the term $\\sum\\sum Pr(c) < \\pi_c, \\hat{l}_{t, c} - \\tilde{l}_{t, c} >$ (implicitly in their $\\text{bias}_2$ term). As a result, their approach yields a bound in expectation only. In our work, saving the term $\\sum \\sum Pr(c) < \\pi_c, \\tilde{l}_{t, c} - l_{t, c} >$ allows us to counteract the random deviation, thereby strengthening the expectation bound into a high-probability bound.\n\n---\n\nOnce again, we sincerely thank you for your positive review. We hope our response addresses your concern.", "claims_and_evidence": "N/A", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n1. I appreciate the detailed description of the literature and I think the current presentation is almost clear (but see my comments below). \n\nWeakness:\n1. On line 275, the authors mentioned that a term of $\\sum\\sum Pr(c) \\langle \\pi_c, \\tilde{l}_{t, c} - l_{t, c}\\rangle$ is saved. However, the significance of this term is not discussed. If the same technique in Schneider & Zimmert, 2023 is used to derive the high probability regret bound, will this term be of non-trivial order that will lead to a term worse than sqrt(KT) and eventually lead to a nonoptimal bound? Or is this term hard to bound given the technique in Schneider & Zimmert, 2023? Or is there any other terms that cause difficulty for the technique in the prior literature? Some discussions would be helpful for me to understand.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PLt3Z9NcZa", "reviewer": "Reviewer_m6dx", "summary": "This paper considers contextual bandits with cross learning, where the learner observes the loss associated with the action across all possible contexts. The losses are adversarial, but the contexts are stochastic.\nThe authors improve the analysis of Schneider & Zimmert (2023) to prove high probability regret bound, rather than the known expected regret bound, to the same algorithm. They do that by making use of the weak dependency structure between different epochs, which was overlooked innprevious analyses. Additionally, they refine martingale inequalities to complete their analysis.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer m6dx,\n\nThank you for your positive feedback. We answer your question below.\n\n---\n\n**Question: the novelty and the broader impact**\n\nThe reviewer questioned the novelty of our work, particularly noting that our contribution appears to be “only the analysis.” We would like to clarify this point. First, in the field of adversarial bandit research, providing a high-probability bound alone is often regarded as a substantial contribution. Second, we respectfully argue that enhancing the results of an existing algorithm through novel analysis—achieving the same outcome with a simpler approach—can, in a certain sense, be considered an advantage over proposing a more complex algorithm. Finally, our work demonstrates technical novelty, as decomposing regret by epochs is a relatively uncommon approach in high-probability bound studies.\n\nRegarding the broader impact of our work, the reviewer asked, “Are those techniques useful in other settings?” This is an excellent question and aligns with the direction we aim to explore next. We believe our techniques could be beneficial to other algorithms that involve epoch-based subroutine and exhibit weakly dependent relationships between epochs. We are committed to further investigating this question.\n\n---\n\nOnce again, we sincerely thank you for your positive review. We hope our response addresses your concern.", "claims_and_evidence": "Yes, they prove high probability regret gurantee.", "methods_and_evaluation_criteria": "The authors consider context regret, which is appropriate measure of perfirmance.", "theoretical_claims": "I read the analysis sketch appears in the main paper, seems OK.", "experimental_designs_or_analyses": "I read the analysis sketch appears in the main paper, seems OK.", "relation_to_broader_scientific_literature": "Not sure that exists relation to broader literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tThe authors present novel and improved analysis to a known algorithm.\n2.\tResults seems sound.\n3.\tWell-written paper.\n\nWeakness:\n\nMy worries are about the novelty – which is only the analysis; and about the broader impact of this work – are those techniques will be useful in other settings?", "other_comments_or_suggestions": "Line 319 left – overflow in inline equation.", "questions_for_authors": "See weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "VOf4lXcyDG", "reviewer": "Reviewer_McaC", "summary": "The paper studies the setting of cross-learning contextual bandit problem and provides a new analysis to the algorithm in Schneider & Zimmert (2023), showing the algorithm can achieve near optimal bound in high probability. They utilizes the weak dependency structure between different epochs and this approach might have chance to generalize to other analysis of algorithm.\n\n## update after rebuttal\nI thank the authors for the response. Nothing major has changed, and I keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear review McaC:\n\nThank you for your positive feedback. We answer your question below.\n\n---\n\n**Question: The line 319 seems overfull**\n\nThanks for pointing this out. We will fix it in the new version.\n\n---\n\n**Question:  whether this analysis approach can be applied to other bandit algorithms**\n\nThis is an good question. We believe that this analysis could potentially be applied to other algorithms that have an epoch-based execution structure and have weakly dependent structures between epochs. We will further investigate this question in future research.\n\n---\n\nOnce again, we sincerely thank you for your positive review. We hope our response addresses your concern.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I check the main theorem and its proof.", "experimental_designs_or_analyses": "They don’t have an experiment part.", "relation_to_broader_scientific_literature": "The paper provided theoretical improvement for an algorithm. If the technique can generalize to other algorithms, then the paper can be considered as a good contribution.", "essential_references_not_discussed": "Nothing particular.", "other_strengths_and_weaknesses": "They provide a new analysis and improve the previous result, from expectation bound to a high probability bound.", "other_comments_or_suggestions": "The line 319 seems overfull.", "questions_for_authors": "The paper gives us a new analysis of algorithm in Schneider & Zimmert (2023) and I wonder whether this analysis approach can be applied to other bandit algorithms.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper gives a refined analysis for a recent algorithm on contextual bandits with cross-context feedback. This kind of problem subsumes for example sleeping bandits.

Using a novel martingale analysis to deal with weakly dependent traces over the epochs in the algorithm allows them to show high probability bounds instead of in-expectation bounds.

Overall, all reviewers agree that this is a nice contribution and that the proofs are sound. None of them is overly excited and gives a strong vote for acceptance. The application is somewhat niche and it is unclear how much interest there is from the broader community.
Decision: Accept (poster)