Optimal cross-learning for contextual bandits with unknown context distributions
Authors: Jon Schneider
Julian Zimmert
Venue: NeurIPS 2023 poster (2023)
Keywords: bandits
first-price auction
sleeping bandits
contextual bandits

Abstract: We consider the problem of designing contextual bandit algorithms in the ``cross-learning'' setting of Balseiro et al., where the learner observes the loss for the action they play in all possible contexts, not just the context of the current round. We specifically consider the setting where losses are chosen adversarially and contexts are sampled i.i.d. from an unknown distribution. In this setting, we resolve an open problem of Balseiro et al. by providing an efficient algorithm with a nearly tight (up to logarithmic factors) regret bound of $\widetilde{O}(\sqrt{TK})$, independent of the number of contexts. As a consequence, we obtain the first nearly tight regret bounds for the problems of learning to bid in first-price auctions (under unknown value distributions) and sleeping bandits with a stochastic action set.

At the core of our algorithm is a novel technique for coordinating the execution of a learning algorithm over multiple epochs in such a way to remove correlations between estimation of the unknown distribution and the actions played by the algorithm. This technique may be of independent interest for other learning problems involving estimation of an unknown context distribution.

Optimal cross-learning for contextual bandits with unknown context distributions
Jon Schneider Google Research j jschnei @google com
Julian Zimmert Google Research zi zimmert@google.com
Abstract
We consider the problem of designing contextual bandit algorithms in the "cross- learning" setting of Balseiro et al., where the learner observes the loss for the action they play in all possible contexts, not just the context of the current round. We specifically consider the setting where losses chosen adversarially and contexts are sampled i...d. from an unknown distribution. In this setting, we resolve an open problem of Balseiro al. by providing efficient algorithm with nearly tight (up to logarithmic factors) regret bound of Ö(VTK). independent of the number of contexts. As consequence, we obtain the first nearly tight regret bounds for the problems of learning to bid in first-price auctions (under unknown value distributions) and sleeping bandits with stochastic action set.
At the core of our algorithm is novel technique for coordinating the execution of a learning algorithm over multiple epochs in such way to remove correlations between estimation of the unknown distribution and the actions played by the algorithm. This technique may be of independent interest for other learning problems involving estimation of an unknown context distribution.
Introduction
In the contextual bandits problem, a learner repeatedly observes a context, chooses an action, and observes a reward for the chosen action only. The goal is to learn a policy that maximizes the expected reward over time, while taking into account the fact that the context can change from one round to the next. Algorithms for the contextual bandits problem are extensively used across various domains, such as personalized recommendations in e-commerce, dynamic pricing, clinical trials, and adaptive routing in networks, among others.
Traditionally, in contextual bandits problems, the learner only observes the reward for the current action and the current context. However, in some applications, the learner may be able to deduce the reward they would have received from taking this action other contexts and attempt to make use of this additional information. For example, if a learner is repeatedly bidding into an auction (where their context their private value for the item, and their action is the bid), they can deduce their net utility under different counterfactual values for the item.
This form of "cross-learning" between contexts first introduced by Balseiro al. [2019], who showed that with this extra information is possible to construct algorithms for this problem with regret guarantees (compared the best fixed mapping from contexts actions) that are independent of the total number of contexts C' - in contrast, without this cross-lcarning information it is necessary to suffer at least S(VCKT regret against such a benchmark. In particular, when contexts are drawn i.i.d. from known distribution and losses are chosen adversarially, Balseiro et al. [2019] present an efficient algorithm that achieves Ō (TT expected regret compared the best fixed mapping from contexts to actions. However, this learning algorithm crucially requires knowledge of the distribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

over contexts (knowledge which is unrealistic to have in many of the desired applications). Balseiro al. [2019] present an altematt algorithm in the case where unknown, albeit with significantly worse regret bound of O(K1/312/3).
Our main contribution in this paper is to close this gap, providing an efficient algorithm (Algorithm 1) which does not require any prior knowledge of v, and attains ((vKT) KT) regret (where the Ô hides logarithmic factors in K and T' but not C), Since there is an ((vKT) regret bound from ordinary (non-contextual) bandits, this bound is optimal up to logarithmic factors in K and T.
Techniques At first glance, it may seem misleadingly simple to migrate algorithms from the known context distribution setting to the unknown context distribution setting. After all, we are provided one sample from this context distribution every round, and these samples are unbiased and unaffected by the actions we take. This suggests the idea of just replacing any use of the true context distribution in the original algorithm by the current empirically estimated context distribution.
Unfortunately, this does not easily work as stated. We go into more detail about why this fails and the challenges of getting this to work in Section 2.1 after we have introduced some notation, but at high level the algorithm of Balseiro et al. [2019] requires computing certain expectation over y when computing low-variance unbiased loss estimates. In particular, this expectation appears in the denominator of these estimates, meaning tiny errors in evaluating it can lead to large changes in algorithm behavior. Even worse, the quantity we need to take the expectation of depends on the previous contexts and therefore can be correlated with our empirical estimate of v, preventing us from applying standard concentration bounds.
We develop new techniques to handle both of these challenges. First, we present new method of analysis that sidesteps the necessity of proving high probability bounds on each of the denominators individually, instead bounding their expected sum in aggregate. Secondly, we present method of scheduling the learning algorithm into different epochs in a way which largely disentangles the correlation between learning y and solving the bandit problem.
As final note, we remark that dealing with unknown context distributions a surprising challenge in many other contextual learning problems. For example, Neu and Olkhovskaya [2020] study variant of linear contextual bandits where they can only prove their strongest regret bounds in the setting where they know the distribution over contexts. It would be interesting to see if the techniques we develop in this paper provide a general method for handling such issues we leave this as an interesting future direction.
1.1 Applications
As an immediate consequence of our bounds for Algorithm 1, we obtain nearly tight regret bounds for a number of problems of interest. We focus on two such applications in this paper: bidding in first-price auctions, and sleeping bandits with stochastic action sets.
Learning to bid in first-price auctions [Balseiro et al., 2019, Han et al., 2020b,a, Zhang et al., 2021, 2022, Badanidiyuru et al., 2023]. In a first-price auction, an item is put up for sale. Simulta- neously, several bidders each submit a hidden bid for the item. The bidder with the highest bid wins the item and pays the value of their bid. Over the last few years, first-price auctions have become an increasingly popular format for variety of lcage-scale advertising auctions [Chen, 2017].
Unlike second-price auctions (where the winning bidder pays the second- bid), first-price auctions non-truthful, meaning that it is not the incentive of the bidder to bid their true value for the item - indeed, doing so guarantees the bidder will gain no utility from winning the auction. Instead, the optimal bidding strategy in first-price auction is complex and depends the bidders estimation of the other players' values and bids. As such, it is a natural candidate for learning over time (especially since advertising platforms run these auctions millions of times a day).
This problem was a motivating application for Balseiro et al. [2019], who proved an 0(T3/4) regret bound for bidders with an unknown (but stochastic iid and bounded) value distribution participating in adversarial first-price auctions with no feedback aside from whether they won the item. Later, several works studied variants of this problem under more relaxed feedback models (for example, Han et al. [2020b] introduced "winning-bid" feedback, where the bidder can always the winning

---

Algorithm
Regret
Computation
Exp4 Auer et al. [2002]
K KVT
2
Saha et al. [2020]
V2eT (K3 (T)
KT
Algorithm
VKT
K
Table 1: Related works in the sleeping bandits framework ignoring all logarithmic terms. The improved regret bound of Saha et al. [2020] is restricted to problem instances where availability of all arms are independent.
bid, and Zhang et al. [2022] study this problem in the presence of machine-learned advice), but none improve over the ( bound in the binary feedback setting.
In Section 4,1, we show that Algorithm leads to an efficient Ö(T2/3) regret algorithm for the setting of Balseiro et al. [2019]. This nearly (up to logarithmic factors) matches an 1(T2233) lower bound proved by Balseiro et al. [2019].
Sleeping bandits [Kanade al., 2009, Kleinberg et al., 2010, Neu and Valko, 2014, Kanade and Steinke, 2014, Kale et al., 2016, Saha et al., 2020]. Sleeping bandits are variant of the classical multi-armed bandit problem, motivated by settings where some actions or experts might not be available in every round. For instance, some items in retail stores might be out of stock, certain servers in load balancing might be under maintenance. When both losses and arm availabilities are adversarial, the problem is known to be NP-hard [Kleinberg et al., 2010] and EXP4 obtains the optimal Ö(K (T) regret. However, when losses are adversarial but availabilities it is unknown what the minimax optimal K K-dependency is and whether it can be obtained by a computationally efficient algorithm. The state of the art for efficient algorithm is either ((KTT)) [Neu and Valko, 2014] O(v2KT [Saha al., 2020]. The latter work provides improved algorithm with (K2VT) regret when the arm availabilities are independent, however, in the general case, the computational complexity scales with T'
stochastic,
In Section 4.2, we show that Algorithm 1 leads to an efficient (O(K) time per round) Ö(vKT) regret algorithm for the sleeping bandits problem with arbitrary stochastic arm availabilities. Again, this nearly matches the 22( KT) lower bound inherited from standard bandits.
Other applications. Finally, we briefly point out that our algorithm extends to the other applications mentioned in Balseiro et al. [2019], including multi-armed bandits with exogenous costs, dynamic pricing with variable costs, and learning to play in Bayesian games. In all cases, applying Algorithm allows us to get nearly the same regret bounds in the unknown context distribution setting as Balseiro et al. [2019] can obtain in the known distribution setting.
2 Preliminaries
Notation
For any natural number N, we use [N] =
We study a contextual K K-armed bandit problem over T rounds, with contexts belonging to some set C. At the start of the problem, an oblivious adversary selects a bounded loss function & C (0, 1] for every round E [T] and every arm & E [K]. In each round then begin by sampling context er ~ v i.i.d. from an unknown distribution P over C, and we reveal this context to the learner. Based on this context, the learner selects an arm A, E [K] to play. The adversary then reveals the function L.A,, and the learner suffers loss l,,,, (c.). Notably, the learner observes the loss for every context E C, but only for the arm A, they actually played.
We would like design learning algorithms that minimize the expected regret of the learner with respect to the best fixed mapping from contexts to actions. In particular, letting IT {Tr [C] + [K]]. we define
T Σ
Reg max E
C.A, (ct) (e,xx
n" ell
3

---

Note that here, the expectation is defined both over the randomness of the algorithm and the random- ness of the contexts.
Non-uniform action sets For some applications (specifically, for sleeping bandits), will find useful to restrict the action set of the learner as a function of the context. To do so, we associate every context C with a fixed non-empty set of active arms Ae S [K]. In round we then restrict the learner to playing an action A₁ in Ac, and measure the regret with respect to policies in the restricted class Il = { : [K] + [C] (c)) E Ac). All the analysis we present later the paper will apply to the non-uniform action set case (which includes the full action set case above as a special case).
2.1 Challenges to extending existing algorithms
is not priori obvious that any learning algorithm in this setting can obtain regret independent of the size of C. Indeed, without the ability to cross-learn between contexts (i.e., only observing the loss for the current action and the current context), one can easily prove a lower bound of 52( / [C K) by choosing an independent hard bandits instance for each of the contexts in C. With the ability to cross-learn between contexts, we side-step this lower bound by being able to gain a little bit of information about each context in each round - however, this information may not be equally useful for every context (e.g., it may be the case that arm 1 is useful arm to explore for context C₁, but is already known to be very sub-optimal in context C2).
In Balseiro et [2019], the authors provide an Ō(v (T) regret algorithm for this problem in the setting where the learner is aware of the context distribution This algorithm essentially runs one copy of EXP3 per context using the following unbiased estimator of the loss (which takes advantage of the cross-learning between contexts);
(ea(c) EeR (c) Bew Pex((c) (c)
T(Ar k),
where in this expression, (c) is the probability that the algorithm would choose arm k in round t if the context was c. straightforward analysis this algorithm (following the analysis of EXP3, but using the reduced variance of this estimator) shows that it obtains Ö(VKT) regret.
The only place knowledge of is required in this algorithm is in computing the denominator natural, then, to attempt to extend this algorithm to
f(x (c)] of our estimator. work in the unknown distribution setting by replacing the distribution y with the empirical observed distribution of contexts far; that replacing (xx(p) with (p) = = Σ (ck(c.). Unfortunately, this approach runs into the following two challenges.
First, since this quantity appears in the denominator, small differences between fex (p) and Fex. (p) can lead big differences in the estimated losses. This can be partially handled by replacing the denominator with a high probability upper bound (p) + C, for some confidence constant C.. However, doing so also introduces a bias penalty of ((CTT) into the analysis. Tuning this constant leads to another 2 algorithm.
Secondly, when we compute the estimator (r)(p) = - (c.) we have the issue that Pt is not independent from the previous contexts G. This can cause the gap between (x) and sex (x) to be larger than what we would expect via concentration inequalities. Avoiding this issue via union bounds leads to a polynomial dependency on JC).
2.2 Our techniques
Avoiding high-probability bounds. While prior work ensured that (p) + +C 2 (p) with high probability, the analysis only requires this to hold in expectation. The following lemma shows that this relaxation allows for smaller confidence intervals. While we don't use this specific lemma in our later proofs, we believe that this result might be of independent interest.

---

Lemma 1. Let ., be i..dd samples from a distribution over [0, 1] with mean μ4, and let
Ā= } - Xg denote the empirical mean. Then
E
E
16/t
This implies that we only need order VT many ii.d. samples for estimating ft,((p) with sufficient precision.
Increasing the number of i.i.d. samples. In order for to samples from the context distribu- tion theorems like Lemma 1, these samples must be independent and must not have already been used by the algorithm to compute the current policy. We increase the number of independent samples via the idea of decoupling the estimation distribution from the playing distribution.
To elaborate, consider the setting of slightly different environment that helps us in the following way: instead of observing the loss of the action we played from our distribution Pt. the environment instead reveals to us the loss of fresh "cxploration action" sampled from snapshot of our action distribution from a previous round. the environment takes a new snapshot of our policy every L rounds (i.e., Pez for some integer e) then this reduces the number of times we need estimate the importance weighting factor in the denominator of (1) to once every epoch, since the importance weighting factor stays the same throughout the epoch. At the same time, we have L fresh i.i.d. samples of the context distribution available at the start of every new epoch.
We present technique operate in the same way without such change in the environment. Instead of the environment taking snapshots of our policy, the algorithm will responsible for taking snapshots itself. In order to generate unbiased samples from (while actually playing pt in round t), we decompose the desired action distribution Pt into an equal mixture of the snapshot s and an exploitation policy gr: Ps {s + gt). We implement this mixture by tossing fair coin of whether to sample from or qt, and only create a loss estimation for when we sample from s. This approach fails when de is not valid distribution over arms, but show that this is low probability failure event by ensuring stability in the policy pt.
Equipped with these two high level ideas, we now drill down into the technical details of our algorithm.
3
Main result and analysis
3.1 The algorithm
We will present efficient algorithm for the unknown distribution setting which achieves Ö(v KT)) regret. We begin by describing this algorithm, which is written out in Algorithm
At the core of our algorithm an instance of the Follow the Regularized Leader (FTRL) algorithm with entropy regularization (i.c., EXP3), In each each round we will generate distribution over actions Pt.c, for the current context & via
Pt. arg zea(())
I, ( -(=),
#=1
where
- ΣK I; log( is the unnormalized neg-entropy, is a learning rate and the ? are loss estimates be defined later.
= =(x)=
We will not sample the action A, we play in round directly from Pt. Instead, we will sample our action from modified distribution de that will construct in such way so that the probability qt of playing a specific action is not correlated with every single previous context c, (for < t). construct loss estimates in way that bypasses the second obstacle in
This will then allow Section 2.1.
To do we will divide the time horizon into epochs of equal length L (where L = @(v to be specified exactly later). Without loss of generality, we assume even and that an integer multiple of L. We let Tg to denote the set of rounds in the e-th epoch.
5

---

1,...: 1,... 21, 2L + 3L, 3L + ...... 4T, 4L ..... 5L.....
Ti fix 83
T2 fix 84
T3
fix a5
T4
fix 86
Ts fix 87
compute
compute fa
compute fa
compute
compute fo
apply l2
apply Is
apply F4
apply Js
sample with 82
sample with s3
sample with 84
sample with 86
Figure 1:
Illustration of the timeline of Algorithm 1. At the end of epoch Te. the snapshot 8642 is fixed. The contexts within epoch T. are used to compute loss estimators for epoch Te+1, which are fed to the FTRL sub-algorithm.
At the end of each epoch, we take single snapshot of the underlying FTRL distribution for each context and arm; that is, we let
i
Se+2,c,k = Pel,c,k where $1,c. = $2,c,k
A
otherwise.
During epoch e, the learner has two somewhat competing goals. First, they would like to play actions drawn from distribution close to Pr,c, (as this allows to bound the learner's regret from the guarantees of FTRL). But secondly, the learner would also like to compute estimators of the true losses fe, with small variance and sufficiently small bias. To do this, the learner requires good estimation of the probability of observing each loss (which in turn depends on both the context distribution and the distribution of actions they playing).
We avoid the problems inherent estimating a changing distribution by committing observe the (Seck/ 2 for any t E Te- This is guaranteed by the following rejection sampling procedure: we first play an arm according to the distribution
loss function of arm & with probability fek = E (Sckk/
Pt.c
i
if E [K] Pt,c,, 2 80,0
qr.c
Se,es
otherwise.
After playing arm according to It.c,, the learner samples Bernoulli random variable Se probability Secuh If S. = 0, they ignore the feedback from this round; otherwise, they use this loss. This 29re,t
subsampling ensures that the probability of observing the loss for given arm is constant over each epoch. To address the first goal and avoid paying large regret due to the mismatch of pt and qe. we tune the FTRL algorithm to satisfy p: qe with high probability at all times.
To actually construct these loss estimates, we need accurate estimates of the fek- To do this we use contexts from epoch correlations. For similar technical reasons, we will also want to use different sets of rounds for computing estimators fek of fek and estimators Ees of the losses l To achieve this, we group all timesteps into consecutive pairs. In each pair of consecutive timesteps, we play the same distribution and randomly use one to calculate a loss estimate, and the other estimate the sampling frequency.
that were not used to compute 8ec. and are thus free of potential
To be precise, let T! denote the time-steps selected for estimation the sampling frequency and T the time-steps to estimate the losses. Then we have
Fex
Σ
Seaek
Ts
2
LET!
which is an unbiased estimator of fek. The loss estimators are
2ltx
(A: = (A:=KASSAIET)
fer +
where y is a confidence parameter (which again, we will specify later).
This concludes our description of the algorithm. In the remainder of this section, we will show that for appropriate settings of the parameters 7), 7. and L., Algorithm achieves Ö(vKT) regret (the parameter in the following theorem a parameter solely of the analysis and determines the failure probabilities of various concentration inequalities).

---

Algorithm Contextual cross-learning algorithm for the unknown distribution setting.
Input: Parameters 7,7 and I. < T.
f2 5
for tur=1e = 1,...,,. do
Observe Ct
Play A $1,0t
f2 - f2 + 52.01
for E ..... T/ do
se+1 +- 0
for = (e 1)L + 1,t (e-
eL - 1 do
Set Pt.c arg minKEA((KK) (z., (x. (c( 17 -----((()) F(2))
for =111, do
Observe Cy' if Pt,cyrk 2 Se,aykk/ 2 for all le E [K] then
Set qu'yy Pr,ce else
Set yer 80,04
Play Ae o Qu.op Observe A,,
t t RandPerm(t, & 1)
Fet1 + fet1 +
Setlicy
2(1/2)
Ase
Sample Se BB 24r.eee Are
Set Eee
(Ac k, 1)
Se+2 + Pt.
2 L 1 log(8K/7), Algorithm 1 satisfies Theorem 1. For any S 2(21+to)'
16c
Reg 0 ((7 + L + n exp -1) T
KT log(K)
L.
11
Tuning 2log(88T), L
KT log(K)
((VKT))
E ((1/ and 1 2(21)+1)
((1/VKT) yields regret bound of
Reg = (og=ō(VKT)
Computational efficiency. In general, the computational complexity is min(tK, |C]} and the memory complexity min(t, [C]K). where the agent is either keeping table of all K x [C] losses in memory, which are updated for all contexts in every round, or the agent keeps all previous loss functions in memory and recomputes the losses of all actions for the context they observe. (This is assuming that we can store and evaluate the loss function with O(1) memory and compute.) In special cases, this can be significantly more efficient. In both sleeping bandits as well as bidding in first-price auctions, we can store the accumulated loss functions in O(1), which means that we have a total per-step runtime and memory complexity of O(K). This is par with the O(T2/3) regret algorithm of Balseiro et [2019], which also has per-step runtime and memory complexity of O(K).
7

---

3.2 Analysis overview
We begin with high-level overview of the analysis. Fix any [C] + [K], and let for each E C, let ue E A([]). We can then write the regret induced by this policy π in the form
Reg(u)
Σ At.e. Uegt (eac)
We would like to upper bound this quantity (for an arbitrary u). To do so, we would like to relate it to (Ptro Ue, ) which we can bound through the guarantees of FIRL. To do so, we will introduce two proxy random variables le RKK and Ptc A([K] which have the property that they are independent of fa conditioned on the snapshot at the end epoch e
Specifically, recall that &a is the snapshot determined at the end of e 2. Then, conditioned on 8c (and in particular, writing E. [-] denote IB|- seD. we define:
Je = (Bew/ 2). Note that the Je used by Algorithm is an unbiased estimator of fe-
Bek Lettz deterministic function of fex. f2
For each t E Te, we let lock Bsck = 2lick I = k = = Leck is loss Sext7
estimator independent of Je such that IR [Pook] Jecty lok leck Since Sek is a determistic
function of se, is independent fex conditioned on Se.
For each & Te, we let pto- = arg min (E((K) (I:; E Esc E
1) F(()) Se+1,c Exp(-nErETTann
Eve). P can be thought of as the action played by FTRL algorithm which consumes the loss estimators i up through epoch 1, but uses pseudo-estimators & during epoch Like E, p independent of fek conditioned on Se-
We perform all our analysis conditioned on the following two events occurring with high probability. First, that our context frequency estimators fek concentrate - i... that [fex - -fekl is small w.h.p. Second, that our loss proxies & concentrate in aggregate over epochs, i.e. that ΣtET, loo is never too large. Both conditions together are sufficient to guarantee that the aggregation of ELeT, frok is also never large, which is crucial in guaranteeing d: Pt.
Conditioned on these two concentration events holding, we can strongly bound many of the quantities. Most notably, can show that, with high probability, qt.c, Pt.c, for all rounds t. This allows us to replace the qt.e, terms in (2) with Pt...- We then split Reg(u) (u) into four terms and label them as follows:
Reg(u) =
Σ Pi.s uea lea -Eecs
E
Σ
Pr.ei Ues tra - -eaer)
bins
biasz
Pr,a Tra tnca
Ua Pare))
+ E
Pi.a
+
Pr,ce
blass
ftri
We then show (again, subject to these concentration bounds holding) that each of these terms is at most Ō(v KTT). Very briefly, this for the following reasons:
bias; and biasg: Here we use the independence structure we introduce by defining ? and p (along with scheduling the different pieces of the algorithm across different epochs). For example, conditioned on Se, know that E, is independent of Pe, safely replace

---

the & in bias; with its expectation. Similarly, Pr is independent of both & and & conditioned on Sc.
biasg: Here we do not have independence between the two sides of the inner product. But fortunately, we can directly bound the magnitude of the summands in this case, since we can show that litc - Ptel and 1e Excl are both small with high probability (in fact, for all c C simultaneously).
ftrl: Finally, this term is bounded from the standard analysis of FTRL.
The full proof of Theorem I can be found in the Appendix (Section C) of the Supplementary Material.
4
Applications
4.1 Bidding in first-price auctions with unknown value distribution
We formally model the first-price auction bidding problem as follows. A bidder participates in T repeated auctions. In auction t, they have a value e2 E [0, 1] for the current item being sold, with Ut being drawn i.dd. from some unknown distribution 1/ supported on [0. 1). They submit bid be [0, 1] into the auction. We let m, [0. 1] denote the highest other bid of any other bidder into this auction (and allow the adversary to choose the sequence of m, obliviously in advance). If be 2 m,, the bidder wins the auction and receives the item (and net utility e4 be); otherwise, the bidder loses the auction and receives nothing. In both cases, the bidder only observes the binary feedback of whether or not they won the item they do not observe the other bids or m,.
The bidder would like to minimize their regret with respect to the best fixed mapping b* ; :0, [0, from values to bids, i.e.,
T
T (ve- - b,) 2 me).
Reg- = max (or- - 6"' (I())) 2 me) Σ
t=1
In [Balseiro et al., 2019], the authors prove a lower bound of ((T2233 for this problem (based on related pricing lower bound of Kleinberg and Leighton [2003]). By applying their algorithm for cross-learning between contexts, they show that it possible to match this in the case where the buyer knows their value distribution v, but only achieve an upper bound of Ö(T3/4) in the unknown distribution case. By applying Algorithm 1, we show that it is possible to achieve a regret bound of O(T2/3) in this setting, nearly (up to logarithmic factors in 7) matching the lower bound.
Corollary 1. There exists an efficient learning algorithm that achieves a regret bound of ((32)3) for the problem of learning to bid in a first-price auction with an unknown value distribution.
Proof. Let K 7 We first discretize the set of possible bids multiples of 1/K 1/3
Note that this increases the overall regret by at most T K = T2/3, in particular, bidding results in expected utility U for bidder with some fixed value bidding any b' > b results in utility at least (b' bb.
Now, we have an instance of the contextual bandits problem with cross-learning where C= [0, 1]. is the distribution over contexts, the arms correspond to the K possible bids, and (v)( 1 - (v- () 2 m,). This setting naturally has cross-learning: after bidding into an auction and receiving (or not receiving) the item, the agent can figure out what net utility they would have received under any value they could possibly have for the item. From Theorem 1, this implies there is an algorithm which gets ÖVVTK) = (33333) regret.
4.2 Sleeping bandits with stochastic action set
In the sleeping bandits problem, there are K arms. Each round / (for T rounds), a non-empty subset S, C [K] of the arms is declared to be "active". The learner must select one of the active arms & E S., upon which they receive some loss lux- We assume here that the losses are chosen by an oblivious adversary, but the S, are sampled independently every round from unknown distribution v. The

---

learner would like low regret compared to the best fixed policy x [2x] - [K] mapping St to an action (S,) to play.
Note that this fits precisely within the contextual bandits with cross-learning framework, where the contexts ea the sets St, we have non-uniform action sets A, = = [K], and cross-learning is possible since the loss leck of arm & in context с in round t does not depend on as long as k belongs the corresponding the context (and if does not, we cannot even play k).
Corollary 2. There exists an efficient learning algorithm that achieves regret bound of (( KT) for the sleeping bandits problem with stochastic action sets drawn from an unknown distribution.
Conclusion
We resolved the open problem of Balseiro al. [2019] with respect to optimal cross-context learning when the distribution of contexts is stochastic but unknown. As side result, we obtained an almost optimal solution for adversarial sleeping bandits with stochastic arm-availabilities. Not only is this algorithm the first to obtain optimal polynomial dependencies in the number of arms and the time horizon, it also the first computationally efficient algorithm obtaining reasonable bound. Finally, we closed the gap between upper and lower bounds for bidding in first-price auctions.
References
Peter Auer, Nicolò
Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1), 2002.
Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. Learning to bid in contextual first price auctions. In Proceedings of the ACM Web Conference 2023, WWW '23, page 3489-3497 New York, NY. USA, 2023. Association for Computing Machinery. ISBN 978 0781450334461. doi: 00.1145/3543307.3588444 URL attpps:/doot http:///ooooooo////// 10. 0111/1144//1000 3583427..
Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32, 2019.
Yuyu Chen. Programmatic advertising is preparing for the first-price auction era. https///tiiida..commmakeeeeee programmatic- sectttiiinn-radyinge first-price- ppicc--uction-era. Octo- ber 2017. Accessed: 2020-01-29.
Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. Learning to bid optimally and efficiently in adversarial first-price auctions. arXiv preprint X0i::2007.04563 2020a.
Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. Optimal no-regret learning in repeated first-price auctions. arXiv preprint (xXi::2003.09795, 2020b.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Opti- mization, 2(3-4):157-325, 2016. 2016.
Satyen Kale, Chansoo Lee, and Dávid Pál. Hardness of online sleeping combinatorial optimization problems. Advances in Neural Information Processing Systems, 29, 2016.
Varun Kanade and Thomas Steinke. Learning hurdles for sleeping experts. ACM Transactions on Computation Theory (TOCT), 6(3):1-16, 2014.
Varun Kanade, H Brendan McMahan, and Brent Bryan. Sleeping experts and bandits with stochastic action availability and adversarial rewards. In Artificial Intelligence and Statistics, pages 272-279. PMLR, 2009.
Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594-605 IEEE, 2003.
10

---

Robert Kleinberg, Alexandru Niculescu-Minn and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2-3):45-272, 2010.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Conference Learning Theory, pages 0049-3068. PMLR, 2020.
Gergely Neu and Michal Valko. Online combinatorial optimization with stochastic decision and adversarial losses. Advances in Neural Information Processing Systems, 27, 2014.
Aadirupa Saha, Pierre Gaillard, and Michal Valko. Improved sleeping bandits with stochastic action sets and adversarial rewards. In International Conference on Machine Learning, pages 8357-8366. PMLR, 2020.
Wei Zhang, Brendan Kitts, Yanjun Han, Zhengyuan Zhou, Tingyu Mao, Hao He, Shengjun Pan, Aaron Flores, San Gultekin, and Tsachy Weissman. Meow: A space-efficient nonparametric bid shading algorithm. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 3928-32222 3936, 2021.
Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman. Leverag- ing the hints: Adaptive bidding in repeated first-price auctions. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neu- ral Information Processing Systems, volume 35, pages 21329-21341. Curran Associates, sills//aaeer/222/Eiie. 2e611a4466ate100000000000000--00 coapperrrooofeeneeeppp pdf.
Inc., 2022. URL httpss://proceeddnggg wwwpurip..cpppppppe.e

---

A
Auxiliary lemmas
We will make use of following existing results from the literature in our proof of Theorem 1. First, we present two concentration results (one for negatively correlated random variables that show in the analysis of bandit algorithms, and a slight generalization of the standard Bernstein inequality).
Lemma (Lemma 12.2 [Lattimore and Szepesvári, 2020]). Ler (Fi) be a filtration and for i [K] let (Yis), ) be I F-adapted such that:
for any S [k] with |S| > >1 MIe |i-1 S 0; and
2. E Yu Fi- you for all E [T] and i [k].
Furthermore, let (ass)ss and (deeles be real-valued F F-predictable random sequences such that for all t,i it holds that 0 S Yu S 22t.. Then, for all ô E (0,
T
k
Yri
Yei 2 log }) S 6.
Σ
Oiti
1+
Lemma (Bernstein type inequality [Lattimore and Szepesvári, 2020] exercise 5.15). Let
X1, X2.... Xn be a sequence of random variables adapted the filtrationn IF (Fi).. Abbreviate E+1 = E1-1 Fi] and define = Ex-1[Xe]. IfC > 0 and C(X, pa) s 1 almost surely, then for all 6 E (0,1)
Xx Σ
n
md) 2 Σ F R - --) + log( (3) 5o.
We will also need the following regret guarantee for FTRL/ multiplicative weights. Lemma 4 ([Hazan et al., 2016], Theorem 1.5). Let & f2.... ..... lrr be sequence of losses in 20" and fix an v) > O. Then, if we let
Pt arg minmminaaa mig
I, ΣEe, l
F(x))
(where F(x) is the unnormalized neg-entropy function), then we have that
T
T
log
T
Pps Ee)
min x' ('EA([
(x 41)
+ Σ (pr,lt)
t=1
Here ef denotes the vector formed by squaring each component of Et. Lemma 5. For any lo 2 16:
[k/4]
f(k) = Σ
i+1
re $2 16/(k+1)
$2.
1)/k)+
Proof. For any 200, we have
[k/4]
Σ
i+1
- (k + 1)3
k/16 <2
k/16] (1-2 (1 1)/k) 16/(k+1]
64
where this statement can be verified by showing that the derivative is negative for A > 200 and numerically computing the value. Finally to show the original claim, sufficient to compute the function values for & E [16, 200), which are all below 2.
D
12

---

B Proof of Lemma
Proof. Let d then
t
パー πt (u d)²
(u / (ū d) d)2
E
=
+ E
+
p+d] d
11 d
=0
To bound the quadratic term, let h = [m/( (we can assume 2 16 or the Lemma holds by d 2 10),
then for any i E [0, k] by Lemma 3 using Ç = V we have
ip sea
P T MSS 1 1 2 VVk) SP ū 1- 221
Decomposing the quadratic terms yields
(n
7 s E I [ 112)
4/1= 13)21 p(p + d)2
E
(ā d)( d)2
[R/4]
Σ
E
( - 2
11
1 - 2v
i+1
(n - A32
h
( + d) + dj²
-= [k/16
[R/4]
4(1 2
4
i+1
< E
Σ
مl + d)2
k(u + d)²
(1- 21 /k/] 16/ +
(=[4/16]
4p
16/z
k( + d)2 S
(Lemma 5)
(μ + d)
(μ + d)
Combining everything
1
16p
1
d
+ 16p/t 1
E
(d= 16p/t)
T
+
1 + d
(n + d)2t
nl + d)
(1 + d)2
1
C Detailed proof of Theorem
C.1 High probability events
We begin our proof by establishing two sequences of events (one per epoch e) that will hold with high probability, representing that our estimation of context frequencies and losses both "concentrate" an appropriate sense.
The first we event we define Fe, represents the event that our estimator far diverges greatly from its expectation fek-
Definition 1. Let F. be the indicator of the event such that at episode e the following inequality holds for all k [K]
fakt
Fecn feul S max
L'LS"
The second event we define, Le, represents the event that the average "proxy" loss is much larger fat
than 1. Note that since [[[[cc]] Tea Teuta Lick I 1, we expect this not to be the case.
Definition 2. Le is the event such that
Eleck Eick s I+ ?
KE|CT,KE|K]
13

---

We present the two concentration arguments below in Lemma 6 and Lemma 7.
Lemma 6. For any E [T/ > event Fg holds with probability least - 2K exp(-
Proof. Fix a & E [K]. Consider random variable defined via X = sc,ck where c ~ V (so
B[X] fek) Note that fek is distributed according Σt' X,
L/2' where the X, are i.idd copies of
X. Then Σ [[(X; - {ex)²] S
Let, since (X; - fas) E
[-1/22,122
Now, for any Ç 1 2, we have by Lemma 3 with probability at least exp(-t)
X; L/2 fer Sfek 2t CL
Σ
Set Ç = min ( Ject which shows that with probability at least exp(-1)
{
Sakt L {VZ
Jex Sak S max
(VL'T L
Repeating the same argument for E; -X; and taking a union bound completes the proof.
Lemma 7, For any E [T/ e > 1, event The holds with probability at least K exx((11).
Proof. We have
21 (A = St 1,te ffek
Σ
Eick
CEIC] TET
1 1+ //f/
TET.
21 (A
The random variable ZeA E| Fi-1] Setting Oak = ? and dek
satisfies the conditions of Lemma 2 and
fek
fek Lemma 2 implies that with probability
1 - exp( (-t, we have
EūSL+
EE
Taking a union bound over E [K] completes the proof.
We will condition the event that all the events F. and Tae hold. To do so, introduce combined indicator variable G.
Definition 3. We define the indicator that all concentrations Fe and Le hold by
G= TTTTL Fal..
Note that by Lemma 6 and Lemma 7, the event G occurs with probability at least (K(T/L) exp(-t). Since we will eventually take 2 log(KT), the probability that G will be negligible.
C.2 Implications of G
We now explore some of the implications of conditioning all of our concentration bounds holding. start by showing that this allows us bound the range of Ptck and Prok. and as a consequence, show that = for all rounds 1. To do so, will be helpful to first use our concentration of f (i.e.,
the event F.) to bound the range of Bek = (fek + (f.(f + 3 x.).
Lemma 8. Let 2 4c I.
then under event G. we have that
$ Bek 2
2
and
11 Bakl S 3 fest. + VLL
4Vifet
for all t E Te.k [K] simultaneously.
14

---

Proof. The first statement is equivalent to showing that
1 3.k
-
1 E
[- 1].
Using the facts that
{v Lake
2 max
L
2:
21 F. and y z t. we have
1
Fek fek + 22 2
-2 - 21
22
1
1 =
L
2 2-2 2
Bek
f+
7
1
Fex fek t
+ z/2 1
1
1,,
Bek
f+?
f f+
which proves that Bek E [1/ If fek S t, then the second condition follows directly from the first. Otherwise we have
Bek - - 2
Let 1 L
2v
Lakt L
Lake I
1
S 3/
fek
2/
lakt
+227
fek 2/
lett + 2%
Sak
fekL
L.
2
lake + +
L
VVL
1 Bek S
S
fek + 2
font
I. + 227
V
fecL
4viffek
We now apply Lemma 8 to bound the range of x and T.
Lemma 9. I 4; and n log(2) then under event G, we have for all E Te, [K],C [C] simultaneously
28eck 2 Pick 2 Beck/
and
28eck 2 Prck 2 Beck/2.
This implies that
Enwelptckl 4fck and In addition, this implies that qi for all E Te-
Eaoel S 4fck
expl Sepl-n(En Sep(-WEEeT. (ecck)) and Ptck x exp(-r(ErET..) Pyrek + Ever (oc)) By definition, G implies that La-1 L Hence for any l E [ [C],
Proof. We have that Ptck x
Eeck S 2(L + +)
5 s
L. 2
ITET-IUT
Furthermore, by Lemma 8, we can bound sums via
Σ Back = =E B Be- + Σ
BekFerk S 5L
UTTT-IUTa
METe-1
PET.
Σ Piok Dinc < STb.
VET.
METe
Finally, this implies for any h that
exp (-5nL) Sek I Ptck exp (5nL) Sek
and for Peek accordingly. Using 1) S log(2) completes the first part of the proof. The second statement follows directly from the definition of 2/4 fek. Finally, the last statement follows from the definition of qe since Itc = Ptc whenever Pick 2 Seck/2 / for all l [K].
We now bound two additional quantities. We start with proving an upper bound on E. [1 Sek]. This helpful a quantity which naturally appears as we try to bound the bias, term; in particular, since Eg Eelck, A. = Ee [e - ee = E. [ Bex] E. [fe,e.k (with the last inequality holding since Bek is independent from le,c conditioned sc).
15

---

16c Lemma 10. y 2 16s and exp(
S
7 8K then
0 < Be [11 Bak) Fel S
fek
Proof. Since Fe {0,1), we have
(1
fek +
-fx)- + 322 -1 Fo)
(1- Bck
Fe.
fek + 37)
set + (Fen -ex + -/
2sch 37
The second term in expectation bounded by
72
E
7 25ch + +37 (1 Fe)
S 2K exp(-1)
2fex 37
4(2fek + 337
remains to bound the first term. Denote Cek
max V L :.) The random variable (fet
Fe is bounded in (-Cck- Cek) due to the indicator Fe. Let = [eex - Fel and assume for now that 1a E t,, d7) which show later. By Jensen's inequality have
- + 117
+
7
E
fex + - Fe T
fek + fek
On the other hand, again due to convexity, the smallest expected value is obtained for the distribution that takes values in -Cek. Ceke} such that it conforms with mean μs. Hence
- fex + 1
C 20ck
+
+ $1
Cek 14)
- Cek + 1
Eg
+
Sek + (Fek - Fex) + xr
fek + Cek + +22
20ck
fek - Cek + 3/
(Sex + 37)(7 + 2/) - 17// 20%p,
2(Sex + Cek + (Jex Cek + (7))
fefc + +22 -20
1
2 2(fex + 3-
2(fek + 2/2
where the last inequality uses the fact that Y + 2/2² 2 20 since 2
I.
Finally need to verify
[-.. We begin by bounding the expectation of By construction Fex fek E 1 31 and Eg-1((1 Fe)l s
E. (fex -fex-feh) fex) (1)()))F)) F -e))
2K exp(-1) S 1/2. Hence due Eelfex - feul O, we have μ Ee [ fck)(1 Fa)] 1.7.71
The last quantity we would like to bound En Prek - -Peck . - Bek (simultaneously for all e E C).
This is quantity which arises when handling bias3. We begin by proving the following auxiliary lemma bounding the coordinate-wise change in x under a multiplicative weights update.
Lemma 11. Let z E [- 1 K x E A([K) and 5 o a o exp(=). Then for all & [K]:
Jt exp(x= 2 (a, |=()) < 3p S I exp(2* + (=))
Proof. We have
K F xx exp(2x) exp( log( xe exp(zx)))
#=1
We only need to bound the last factor. Note that by Jensen's 's inequality, have
K
ay exp(=x) 2 exp((x,z)).
16

---

hence
K
exp(- 1opp-
Σ
The exp(xx))) s exp(( (x, z))
='=1
In the other direction, we have by |2| 1 1
K
by exp(=x) $ +1+ (0,2) + (x,
hence
log(1 + (2, + (x, - -xx,2) -(x, x2)
Lemma 12. Assume 1) < 2
Then under event G. for all & Te and have that
K
K
Fr.ck Pe,aul 1haul-11- Bokl S
Pr.c, (1 Bex))
k=1
Proof. By definition, Ptck & Pick exp(-1) Ever.velllud Elct)). We can simplify the argument of the exponential via
Σ -vds)) Bek) Σ Erek.
VET
VET,,t'st
By Lemma and the definition of Le, we have
Σ
- - Eeckt) =n(1 Bek) Σ
Erck S nl(+ 1
2 2
P'
Lemma 11 now implies that
2s 20
Ptck - Pecke S ePrck!l
[1 Bokl +
Preil Sial
(
?
i=1
K
c <
Pick
-1- Bekl +
Photl |1 - Bsse
1=1
Hence
K
Prak - Pr.c.dl .11 Bool 5
Σ Prek( Bex)2
Σ
Prot (1 Bek
K
< 6
Prek(1 (1 - Brx
(Jensen's 's inequality)
17

---

C.3
Combining the pieces
Proof. We begin by decomposing the regret similarly the high level overview (but explicitly showing the dependence on the indicator G).
Reg(u)=
E
(gte
Ua (osltaa)
1=1
TYL
(pt. Mest (ea G
+ +B KT
c=2 TET
T
T/L
< E
Pr.ce un work kea l1,0s G
+E
Pra ter -iic--raa lea) Gi
2= TET
e=2 TET
biasy
bius
T/L Σ
T/L
Proce
Pt.car Pr,or Erre
)
+E
Pr.es uor Proa) G
IET.
blass
ftrl
+ = + L.
Note that the first inequality follows in part from Lemma 9, since when G 1, Pt.c, = (t.c. We now bound the remaining four terms individually. We start with bias Since & is conditionally independent of pe. by the tower rule of expectation
T/L Σ
bias
Pi.e
Ee Eellhal)
e TE
T/L
(prcesh (oenk) Peecec G Sek +7
E
T/L
PiccY G fexk +
E
(0 4 1)
TE
k=1
4KyT.
(Lemma 9)
Similarly, in biasz, & and & are independent of pr conditioned on episode e. We thus have
T/LL
bias:
E
Σ
Uey Belle, - ((col) Pt.a
TET.
T/L
E
Σ
(Pr.c k) [Ee((1 Bek) (e.eee) G
e=2 TET
T/LL
E
Σ
Ve
Prc G
(Lemma 10 and 0 - E. < 1)
fekk k=1
TET
T/LL
E VeSe,cAA G
< E
Σ
(Lemma 9)
Seck
TET.
1=
< 4K*T,
Finally, the term needs to bounded differently, because Pt is not independent of 3z. Instead, we will expand out the inner product and directly bound the maximum value of (Pook -roo Bex)
18

---

over all via Lemma 12.
T/L
Pt.a Pe,c., Belleer - -Racl) G
bias; E3'
c=2 TET
TyLL
E
Σ
(ptakk Pt.ce,))1 - Beak) Bee Pe
e= tET. k=1
T/L
S E
Pt.c. Pt.c,kk -1 B
e=2 TET. kml
TyL
K
< E
3usPrcc - B
(Lemma 12)
2=2 LE T. c= k=1
98KTL
2 LKT
(Lemma 8 and Lemma 9)
L
Finally the ftrl term is bounded according to Lemma 4
TyL
Pr.a - Ues Pasee)
ftrl
c=2 LET
T/L
log(K) K)
+ +
Σ Vc EE
Σ
Pick Pick
(Lemma 4)
cE[C]
e=2 TE KE[K]
T/L
log(K)
Sek G (Pek 37)2
+ E
ΣΣ
Σ
VePtck
IET kE[K] cE|C]
T/L ΣΣ
log(K)
4n
PaGG
(Lemma 9)
1 ke(K)
log(K) K)
16nKT.
(Lemma 8)
1
Combining everything, we have that
Reg(u) = 1000000((00 ((++++ L
I +1) KT + log(K) + +
19


Reviews:
[{"review_id": "DsxVPUMKWg", "reviewer": "Reviewer_Z4YZ", "summary": "The paper proposes an efficient contextual bandit algorithm in the cross-learning setting, introduced in Balseiro et al., in the case of contexts sampled from an unknown distribution and where losses are chosen adversarially. In contextual bandits, the learner only utilizes the reward associated with an action for the current context. In contrast, in the cross-learning setting, the learner also exploits the reward associated with different contexts, which results in regret bounds that are independent of the total number of contexts. This approach can be employed in scenarios where that extra information is actually available such as bidding in nontruthful auctions, multi-armed bandits with exogenous costs, or repeated Bayesian games with private types.\n\nThe proposed algorithm results in an optimal regret bound of $\\tilde{O}(\\sqrt{KT})$, with $K$ the number of arms and $T$ the number of rounds, thereby closing the existing regret bound gap in the literature. Building upon this optimal regret bound, the authors derived nearly tight regret bounds for two applications: bidding in first-price auctions, and sleeping bandits with arbitrary stochastic arm availabilities.\n\nThe proposed approach bypasses the existing challenges in extending cross-learning contextual bandit to the unknown distribution setting by: 1) constructing an estimator with an in-built upper bound on the expected sum 2) introducing a novel technique for scheduling the learning algorithm that removes the correlation between the empirical estimate of the unknown distribution and the actions chosen by the algorithm, which is an obstacle for employing concentration inequalities.", "questions": "How does the computational efficiency of Algorithm 1 compare to existing approaches?", "limitations": "The limitations of the proposed approach are not entirely clear.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written, and the setup is clear. The limitations for extending existing algorithms are clearly explained, and the approach employed to overcome them is novel. To the best of my knowledge, the authors' result is new and shows a clear improvement over the state-of-the-art for cross-learning contextual bandits with unknown distributions. Thus, I recommend acceptance.", "weaknesses": "Although the paper is technically solid, the contribution seems incremental, and the actual impact of extending the work of Balseiro et al. to the unknown distribution setting is not entirely clear.\n\nThe computational efficiency aspect of the algorithm is not compared with what seems to be the most obvious baseline, i.e., the algorithm of Balseiro et al. that tackles the unknown distribution case.\n\nLastly, I feel that the paper could benefit from numerical experiments that support the derived theoretical results.\n\nL. 117: “the we begin”\n\nL. 161: “we’d” → “we would”\n\nL.152/159: $\\widehat{f_{tk}}(p) = \\frac{1}{t} \\sum_{s=1}^{t} p_{tk}(c_{t})$ → $\\widehat{f_{tk}}(p) = \\frac{1}{t} \\sum_{s=1}^{t} p_{sk}(c_{s})$ ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for spotting the typos, the correction in L.152/159 is correct.\nWe will add a comparison for the computational efficiency. The $T^{2/3}$ baseline of Balseiro et al. has the same computational complexity."}, {"review_id": "RRdinr4y3V", "reviewer": "Reviewer_4dhq", "summary": "This paper studies the sequential learning problem with the presence if context, where the context is drawn iid from some unknown distribution and the losses are chosen by the adversary.  The feedback, that learner observes, is the loss for any context for the chosen action. This paper improves the previous result in this setting, by showing the $\\tilde{O}(\\sqrt{KT})$ regret upper bound for the algorithm with running time that scales with the number of context at each time step.\nAuthors demonstrate a range of real-world applications where such feedback model is useful.", "questions": "Line 495, could you please give more details on the application of Lemma 3? It is not straightforward that this Lemma gives the inequality that is used in that sequence of inequalities. Loss estimation is only defined for steps $t_l$, so the fact that the algorithm ignores the half of the observations should affect this lemma. \n\nThese quantities are not defined:\n- Equation after line 193, $p_{eL,c,k}$\n- line 201, $s_{eck}$\n\nAlgorithm 1: \n- computation of $p_{t,c}$ defined using all loss estimates up to t-1, but there are no loss estimate for half of them.\n- 2(L/2) is confusing", "limitations": "I hope that my question can be answered, so I could verify the correctness of the analysis.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Authors improve the previously known result for the unknown distribution setting, by proposing the new technique on the estimation of the loss for this problem that allows remove the dependence between the data from which the losses and the context distribution are estimated.", "weaknesses": "Some steps of the proof are omitted, so I could not verify the correctness of the proof. See Questions. \n\nFor proposed applications, issues of the computation efficiency were not discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$p_{eL,c,k}$ is $p_{t,c,k}$ at time $t=eL$, i.e. the last timestep of epoch e. $s_{e,c,k}$ is defined after line 193, it determines the rate at which we use observations in epoch e via downsampling.\n\nThe loss estimate for $t_f$ is simply 0. We scale the loss estimate for $t_{\\ell}$ by a factor two, which ensures that $\\widehat\\ell_{t_\\ell}$ is an unbiased estimate of $\\ell_{t_\\ell}+\\ell_{t_f}$.\n\nWe can use Lemma 3 as follows:\n$\\sum_{t \\in T_{\\ell}}\\langle p_{tc} - u,\\widehat\\ell_{t,c}\\rangle \\leq \\frac{\\log(K)}{\\eta} +\\eta\\sum_{t\\in T_{\\ell}}\\langle p_{tc}, \\widehat\\ell_{t,c}^2\\rangle$.\n\n``For proposed applications, issues of the computation efficiency were not discussed.\n‘’\nWe mention the computation efficiency for sleeping bandits and first-price auctions in line 230-232. \n\n"}, {"review_id": "JwQaOXlSId", "reviewer": "Reviewer_WAx4", "summary": "This manuscript studies the following missing piece in [Balserio et al. 2019]: in contextual bandits with cross learning (i.e. with a complete feedback graph across contexts), suppose that the contexts are stochastic with an unknown distribution, is there an algorithm that achieves a \\tilde{\\Theta}(\\sqrt{KT}) regret? Note that when the context distribution is known, an EXP3-type algorithm in [Balserio et al. 2019] achieves the above bound. The key difficulty in this manuscript is to estimate the sampling probability when carrying out the EXP3 algorithm. \n\nThere are two main ingredients in this manuscript: \n\n1. Bypassing the high-probability UCB. Specifically, when \\hat{f} is an estimate of f with |\\hat{f} - f| \\le a with high probability, the naive argument tells that 1 / (\\hat{f} + a) \\le 1/f with high probability. By leveraging the curvature of 1/x, the authors improved this result by showing that if in addition |E[\\hat{f}] - f|\\le b, then E[1/(\\hat{f} + b)] \\le 1/f provided that a \\le \\sqrt{f*b}. The final inequality is further ensured by the Bernstein concentration. This observation shows that one can use a smaller confidence bound (b instead of a), and essentially implies that the estimation of sampling probability is a much simpler problem and requires only sqrt(T) samples. This is the key to the success of the proposed algorithm. Significance: high. \n\n2. Dealing with the dependence issue. To this end, the authors applied several tricks. First, decouple the rounds for loss estimation and sampling probability estimation. Second, use the target sampling distribution given two epochs before. Third, use the sampling probability estimates one epoch before. This involves additional technical analysis for the continuity of EXP3-type probability updates. Significance: medium. \n\nThis result is applied to two problems. The first is the bidding in first-price auctions in [Balserio et al. 2019] with binary feedback, where this manuscript complements the result of [Balserio et al. 2019] by establishing a T^{2/3} regret when the private value distribution is unknown. Significance: medium. \n\nThe second application is sleeping bandits with stochastic availabilities, where a sqrt{KT} regret is shown. This result greatly improves the existing ones in the literature in the sense that both the regret and the computation time are polynomial in (K, T). Significance: high. ", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "As summarized above, I really like two components of this manuscript: \n\n1. An improved bound of |E[1/(\\hat{f}+b)] - 1/f| taking into account both the L_infty and L_1 norm of |\\hat{f} - f|. \n\n2. Formulating the sleeping bandits as a cross-learning problem and its application. ", "weaknesses": "I do not see a major weakness for this manuscript. At the beginning I felt that this manuscript is a bit narrow in scope (i.e. finish a small missing piece in [Balserio et al. 2019]), but the application to sleeping bandits is very interesting. \n\nHowever, I still have to say that the writing quality is poor and the presentation of high-level ideas is obscure. I strongly urge the authors to improve the writing, including: \n\n1. The explanation of the first technique on Page 4. Could you formulate it in a similar way to my point 1 in the summary? Also this result could be stated as a standalone lemma. In the paragraph, C_N is undefined too, and I don't know what N is. \n\n2. There are lots of notations in the algorithm description, including p, q, s, f. The most confusing quantity to me is s, for which I spent quite a bit of time understanding its role. For an algorithm with several components, my general suggestion is to explain them piece by piece. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the suggestions on improving the writing. "}, {"review_id": "IPgPiT14Vc", "reviewer": "Reviewer_Eqpa", "summary": "This paper studies contextual bandits in the ``cross-learning' setting. They propose an algorithm that attains nearly tight regret of $\\tilde{\\mathcal{O}}(\\sqrt{TK})$. They achieves this by carefully separating the horizon into blocks of fixed size and coordinate the estimation of unknown distribution and the action played by the algorithm to remove the correlations. They apply their methods in first-price auctions and sleeping bandits and obtain nearly tight bounds.", "questions": "1. What do the authors expect their algorithms, and regret bounds become if the cross-learning condition is dropped? Is there any reason essential to keep the conditions, other than making the regret bounds tighter?\n2. In practice, how do you choose $L$? This length seems to be fixed for all time, and the algorithm is designed to deal with various unknown distributions. I wonder (1) how to tune $L$ apriori and (2) why a fixed $L$ could work for a large family of unknown distributions? \n\n\nMinor thing:\nIn the proof of Lemma 6 on page 13, there seems to be an error in upper bounding $\\beta_{e k}-1$, namely $4/\\frac{7}{8} > 3$.", "limitations": "I don't see any limitations or potential negative societal impact of this work.\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is in general well-written. The considered setting is hard yet the theoretical bounds are nearly tight. The algorithm is carefully designed to decouple the distribution of the estimated unknown context and actions chosen and is nicely presented. ", "weaknesses": "The cross-learning setting is not so meaningful to me. At least, I think the authors are not doing a good job in motivating this setting. The only example provided is bidding in an auction, where different counterfactual values of the items. However, the context here is only one-dimensional, and the loss monotonously depends on the values, as a result, the cross-learning setting is more likely a byproduct of the specific one-dimensional structure rather than something common in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Re: dropping the cross-learning condition, this paper is fundamentally focused on designing algorithms under this cross-learning assumption, so our algorithms only make sense in this setting. Without a cross-learning assumption, the regret bounds can be far worse (in particular, we must pay a factor depending on the number of contexts, which can be huge). Cross-learning is not a necessary consequence of one-dimensional settings, and neither does it only apply to one-dimensional settings: in many of the applications we mention the context can be multidimensional (e.g. in sleeping bandits, the context is a subset of [K] and has exponentially many values). See also the reply to all reviewers above. \n\nWe can tune L independently from the unknown distribution, because it relies on the fact that certain FTRL variants (EXP3 with high probability bounds on the loss estimates) are stable in the sense that the playing distribution $p_t$ changes slowly over time. \nIf the horizon $T$ is unknown, one can either use doubling or most likely derive a schedule for L such that it grows with approximately $\\sqrt{t}$ over time.\n"}, {"review_id": "fEP8jMtgSs", "reviewer": "Reviewer_JZMx", "summary": "The paper studies the cross-learning problem in contextual bandits, and proposes a $\\sqrt{KT}$ regret algorithm.", "questions": "For the main algorithm: \n1. Why divide epochs into length $\\sqrt{T}$? \n2. What exactly is the use of the 'rejection sampling' procedure, and how can this help with estimation? \n3. line 212, what is 'same distribution' referring to? \n\nIn line 200, what does changing distribution refer to? \n\nIn line 238, is $\\tilde{l}_{ckt} \\in R^{K}$ or $R$?  \n\nSimilar question for $ \\tilde{p}_{ckt} $.", "limitations": "The authors did not address limitations.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper proposes an algorithm achieving $\\sqrt{KT}$ regret using an epoch-based schedule. The algorithm achieves optimal regret without requiring knowledge of the context distribution.", "weaknesses": "In applications (section 1.1 and section 4), it might be better to point out the explicit connection between cross-learning and bidding in 1st price auction / sleeping bandits. E.g. what is the context here in 1st price auction? \n\nThe technical part was very hard to follow. I have doubts about the soundness of the technical approach, see questions below. \n\nThe writing contains noticeable grammatical errors, e.g. line 214, line 237...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "``In applications (section 1.1 and section 4), it might be better to point out the explicit connection between cross-learning and bidding in 1st price auction / sleeping bandits. E.g. what is the context here in 1st price auction?''\n\nIn 1st price auction, the context is the personal value $v_t$ for the item being sold.\n\n\n``The technical part was very hard to follow. I have doubts about the soundness of the technical approach, see questions below.''\n\nSee our replies below. Please let us know if you have other questions.\n\n``Why divide epochs into length $\\sqrt{T}$?\nWhat exactly is the use of the 'rejection sampling' procedure, and how can this help with estimation?''\n\nThe reason for both is to overcome the challenges described in section 2.1 (line 159 - 162).\nRejection sampling ensures that the unknown importance weighting factor $\\widehat f$ does not need to be estimated in every round $t$, but only once for every epoch $e$. The length of an epoch is $\\sqrt{T}$, because that is the longest interval one can ensure that the distribution $p_t$ stays within a constant factor, without sacrificing regret.\n\n\n``line 212, what is 'same distribution' referring to?''\n\nIn every two consecutive time-steps $2k, 2k+1$, we are drawing an action from the distribution $p_{2k}$.\n\n``In line 200, what does changing distribution refer to?''\n\nIt refers to the distribution $E_{c \\sim \\nu}[p_{t}(c)]$, which would be the straightforward importance weighting factor. This is a moving target because $p_{t}$ is changing in every round.\n\n``In line 238, ... $\\tilde\\ell_{tck}$[...]$\\tilde p_{tck}?$''\n\nThank you for spotting these typos, it is supposed to be\n$\\tilde\\ell_{tc}\\in\\mathbb{R}^K$, $\\tilde p_{tc}\\in \\Delta([K])$.\n"}]

Author rebuttal:
Several reviewers questioned the motivation of the cross-context learning. This setting is of interest because it generalizes several distinct problems in the literature. Besides bidding in first-price auctions and sleeping bandits, this also includes dynamic pricing with variable costs, where each arm is associated with an adversarially chosen cost of playing in every round, as well as convergence to equilibria in repeated Bayesian games with private types. We included only the first two applications because this is where our algorithm significantly improves state-of-the-art regret bounds.

We believe that the sleeping bandit result alone is already a contribution of high impact on its own.

We received the feedback that the presentation of the results can be improved and will take your suggestions into account when improving the writing.


Meta-review: After discussions with the authors, the reviewers have converged to a positive view of this paper. Everyone agrees that the bound is a significant improvement and I do agree about the importance of cross-learning (esp for practical scenarios, like auctions). The reviewers have pointed out some writeup changes and I am satisfied that the authors can address them easily. Overall, the changes needed are within the scope of a final version revision and I recommend acceptance.
Decision: Accept (poster)