Meta-Learning Adversarial Bandit Algorithms
Authors: Mikhail Khodak
Ilya Osadchiy
Keegan Harris
Nina Balcan
Kfir Yehuda Levy
Ron Meir
Steven Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
multi-armed bandits
meta-learning
multi-task learning
bandit linear optimization
TL;DR: We provide the first formal guarantees for meta-learning with adversarial bandit feedback.

Abstract: We study online meta-learning with bandit feedback, with the goal of improving performance across multiple tasks if they are similar according to some natural similarity measure.
  As the first to target the adversarial online-within-online partial-information setting, we design meta-algorithms that combine outer learners to simultaneously tune the initialization and other hyperparameters of an inner learner for two important cases:
  multi-armed bandits (MAB) and bandit linear optimization (BLO).
  For MAB, the meta-learners initialize and set hyperparameters of the Tsallis-entropy generalization of Exp3, with the task-averaged regret improving if the entropy of the optima-in-hindsight is small.
  For BLO, we learn to initialize and tune online mirror descent (OMD) with self-concordant barrier regularizers, showing that task-averaged regret varies directly with an action space-dependent measure they induce.
  Our guarantees rely on proving that unregularized follow-the-leader combined with two levels of low-dimensional hyperparameter tuning is enough to learn a sequence of affine functions of non-Lipschitz and sometimes non-convex Bregman divergences bounding the regret of OMD.

Meta-Learning Adversarial Bandit Algorithms
Mikhail Khodak Carnegie Mellon University @hodak@cmm edu
Ilya Osadchiy"
Keegan Harris CMU
Technion Israel Institute of Technology
osadchiy.1i 1 i. com
Maria-Florina Balcan
Kfir Y. Levy
Ron Meir Technion
Zhiwei Steven Wu CMU
CMU
Technion
Abstract
We study online meta-learning with bandit feedback, with the goal of improving performance across multiple tasks if they similar according to natural similarity measure. As the first to target the adversarial ceiine-wttin-oniie nartialinfforattion setting, we design meta-algorithms that combine outer learners to simultaneously tune the initialization and other hyperparameters of an inner learner for important optimization (BLO). For MAB, the meta-learners initialize and set hyperparameters of the Tsallis-entropy generalization of Exp3, with the task-averaged regret improving the entropy of the optima-in-hindsige is small. For BLO, we learn initialize and tune online mirror descent (OMD) with self-concordant barrier regularizens, showing that task-averaged regret varies directly with an action space- dependent measure they induce. Our guarantees rely on proving that unregularized sellowthhe-lcader combined with two levels of fow-dimensional hyperparameter tuning enough to learn a sequence of affine functions of non-Lipschitz and sometimes non-convex Bregman divergences bounding the regret of OMD.
multi-armed bandits (MAB) and bandit linear
Introduction
Learning-to-leat [51] is an important area of research that studies how to improve the performance initializations, step-sizes, and/or
of a learning algorithm by meta-learning its parameters- representations-acree many similar tasks. The goal is to encode information from previous tasks in order achieve better performance on future ones. Meta-learning has seen great deal of experimental work [24, 49], practical impact [21, 29], and theoretical effort [11, 18, 22, 45, 20]. One important setting is online- within-online meta-learning [19, 31], where the learner performs sequence of tasks, each of which has a sequence of rounds. Past work has studied the mall-infomaaion setting, where the loss for every arm is revealed after each round. This assumption is not realistic in many applications. c.g. recommender systems and experimental design, where often partial or bandit feedback- -only the loss of the action taken-is revealed. Such feedback can be stochastic, e.g. the losses are i.i.d. from some distribution, adversarial, i.e. chosen by an adversary. We establish the first formal guarantees for online withhn---nnnniin letannea with adversarial bandit feedback.
As with past full-information meta-lcarning results, our goal when faced with sequence of bandit tasks will be to achieve low regret on average across them. Specifically, our task-averaged regret should (a) be no worse than that of algorithms for the single-task setting, e.g. if the tasks are not very similar, and should (b) be much better on tasks that are closely related, e.g. the same small set of arms do well on all of them. We show that natural way to achieve both is to initialize and tune online mirror descent (OMD), an algorithm associted with a strictly convex regularizer whose hyperparam-
Denotes equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

eters have a significant impact on performance. Our approach works because it can learn the best hyperparameters in hindsight across tasks, which will recover OMD's worst-case optimal performance if the tasks are dissimilar but will take advantage of more optimistic settings if they are related. As generalized distances, the regularizers also induce interpretable measures of similarity between tasks.
1.1 Main contributions
We design meta- meta-algorithm (Algorithm 1) for learning variants of OMD specifically those with entropic or self-concordant regularizers- are used for adversarial bandits. This meta-algorithm combines three moll-infommatinn optimization (EWOO), and multiplicative weights (MW)-to set the initialization, step-size, and regularizer-specific parameters, respectively. It works by optimizing sequence of functions that each upper-bound the regret of OMD on a single task (Theorem 2.1), resulting in (a) interesting notions of lask-similarity because these functions depend on generalized notions of distances (Bregman divergences) and (b) adaptivity, i.e not needing to know how similar the tasks are beforehand.
(FTL), exponentially weighted online
Our first application is to OMD with the Tsallis regularizer [3], relative of Exp3 [6] that is optimal for adversarial MAB. We bound the task-averaged regret by the Tsallis entropy of the estimated optima- in-hindsight (Corollary 3.1), which we further extend to that of the true optima by assuming a gap between the best and second-hest arms (Corollary 3.2). Both results are the first known consequences of the online learnability of Bregman divergences that non-convex in their second arguments [31], while the latter is obtained by showing that the loss estimators of a modified algorithm identify the opti- mal arm w.h.p. As an example, our average m-round regret across T tasks under the gap assumption is
or (pol((mm)) + min BE(U.1)
H + ol
(1)
where d is the number of actions and H3 is the Tsallis entropy [52, 3] of the distribution of the optimal actions (8 = recovers the Shannon entropy).' ! This entropy is low if all tasks are usually solved by the same few arms, making a natural sask-similarity notion. For example, if only s < d of the arms are ever optimal then Hg = Oss, so using 3 = 1/ log d in (1) yields an asymptotic lask-averaged regret of O sm log d), dropping fast terms. For 8 = Oa(1) this beats the minimax optimal rate of @(v dm) [5]. On the other hand, since H1/2 = O( d). the same bound recovers this rate in the worst-case of dissimilar tasks.
Lastly, we adapt our meta-algorithm to the adversarial BLO problem by setting the regularizer to be a self-concordant barrier function, as in Abernethy et al. [2]. Our bounds yield notions of task-similarity that depend on the constraints of the action space, e.g. over the sphere the measure is the closeness of the average of the estimated optima to the sphere's s surface (Corollary 4.1). We also instantiate BLO on the bandit shortest-path problem (Corollary 4.2) [50, 30).
1.2 Related work
While we are the first to consider meta-learning under adversarial bandit feedback, many have studied meta-learning in various stochastic bandit settings [9, 34, 47, 48, 35, 13, 15, 41, 10]. The latter three study stochastic bandits under various task fask-generation assumptions, e.g. Azizi et al. [10] is in a batch- Mithin-online setting where the optimal arms are adversarial. In contrast, we make no distributional assumptions either within or without, Apart from this difference, the results of Azizi et al. [10] are the ones our MAB results are most easily compared to, which we do in detail in Section 3. Notably, they assume that only 8 & d of the d arms are ever optimal across T tasks and show (roughly speaking) Ó (smm) asymptotic regret; we instead focus on an entropic notion of task-similarity that achieves the same asymptotic regret when specialized to their < d. However, avoiding their explicit assumption has certain advantages, e.g. robustness in the presence of o(T) outlier tasks (c.f. Section 3.3).
A setting that bears some similarity to online-within-oninnn and more generally online learning with dynamic comparators [4, 27, 38, 7, 55). In such problems, instead of using static best arm the comparator we use a piecewise constant sequence of arms, with a limited number of arm switches. The key difference between such work and ours is our assumption that basudouussssies However, while e.g. Exp3.S [6] can indeed be applied to online meta-learning, guarantees derived
bandits is that of switching bandits [6].
known; this makes the other setting more general.
We use (.).) (and on (-)) denote terms with constant (and sub-constant) dependence

---

from switching costs cannot improve upon just running Tsallis-NF on each task [39, Table 1]. Furthermore, these approaches usually quantify difficulty by the number of switches, whereas we focus on task-similarity. While there exists stochastie-setting work that measures difficulty using a notion of average change in distribution across rounds [53], does not lead to improved performance if this average change is (T)), as is the case in e.g. the s-sparse setting discussed above.
There has been a variety of work on full-information including tuning OMD [31, 19]. Doing so for bandit algorithms has many additional challenges, including (1) their inherent and high-variam
seette-wwthnn-oniine
neta-learning [32. 12],
stochasticity, (2) the use of non non- -in-cchccit and even unbounded regularizers, and (3) the lack of access to task oottima in order to adapt to deterministic, algorithm-independerr misk-similarrty measures. Theoretically our analysis draws on the average wwwpuuppppuuuueeeee bound analysis (ARUBA) framework [31]. which observes that OMD can be tuned by targeting its upper bounds, which are affine functions of Bregman divergences, and provide online learning tools for doing so. Our core structural result shows that the distance generating functions the of these Bregman divergences can be tuned without interfering with meta-learning the initialization and step-size; tuning 0 is critical for adapting to settings such as that of small set of optimal arms in MAB. Doing so depends on several refinements of the original approach, including bounding the lask-aveageed-regre via the spectral norm of V and expressing the loss of the meta-comparator using only Ve, rather than via its Bregman divergence as in prior work. Finally, applying our structural result requires setting-specffic analysis, e.g. show regularity w.r.t. 9 or to obtain MAB guarantees in terms of the entropy of the true optimal arms. The latter is especially difficult, as Khodak et al. [31] define task- siss-iiiilartty via full information upper bounds, and involves applying tools from the best- arm-identification literature [1] to show that a constrained variant of Exp3 finds the optimal arm w.h.p.
2 Learning the regularizers of bandit algorithms
We consider the problem of meta-learning over bandit tasks 1. = 1,..., T over some fixed set K. C Rd, a (possibly improper) subset of which is the action space A. On each round: = 1,.... m of task we play action x,, E A and receive feedback l, for some function f,, : A + [-1, Note that all functions we consider will be lincar and so we will also write (x) = (le,,, x). Additionally, we assume the adversary is oblivious within-task, i.c. it chooses losses lr,1...,, ft.m at time f. We will Rd 1C' to be the interior of K., OK its bound- ary, and A to be the simplex on d elements. Finally, note that all proofs can be found in the Appendix.
also denote x(a) be the a-th element of the vector
In online learning, the goal the regret Σx= (xx:() - (x,), where X; E arg min En (x).... Lifting this to the meta-learning setting, our goal as in past work [31, 19] will be to minimize the task-averaged regret: + + Em
single task t is to play actions Xt,1,... Xt.m that minimize
In particular, we want to use multi-task data to improve average performance as the number of tasks T + co. For example, we wish to attain task-averaged regret bound of the form or (poly(m)) + OVV + o( ((m)), where V E R>o is measure of simk-simiy that is small if the tasks are similar but still yields the worst-case single-task performance
- l. (x,,(x
(Vvdm) dm for MAB and (dd/m) for BLO if they are not.
2.1 Online mirror descent base-learner
In meta-learning we are commonly interested in learning within-task algorithm or base-learner; a parameterized method that we run on each task popular approach is to learn the initialization and other parameters of a gradient-based method such as gradient descent [24, 44, 36]. If the task optima are close, the best initialization should perform well after only a few steps on a new task. We take similar approach applied to online mirror descent, a generalization of gradient descent to non non-Euclidean geometries [14]. Given a strictly convex regularizer v KC + IR, step-size r) > O. and initialization x,, E KC, OMD has the iteration
Xt,i+1 arg min ((x||xx,)) Ti
((Ves((X,.)))) jSi
xEK
where - =(x) - (Vb(v)) y) is the Bregman divergence of sb. OMD recovers online gradient descent when (x) = 2 | in which case B(xlly) = | yll:: another example is exponentiated gradient, for which (pp) (p. log p) is the negative Shannon entropy on probability vectors p& E A and B is the KI.-divergence [46]. An important property of B that the sum over functions Bxxell-) is minimized at the mean x of the points X1,...,XT. XT.
3

---

Algorithm 1: Tunes o,D with regularizer we : K2' + R and step-size > 0, which when run over loss estimators fr.1,.... Lu,, yielding task-optima & arg min Σx= (L,,)))).
Input: compact set KC C Rd, initialization x1 E K. ordered subset O₂ E also used to index interval bounds 7.77 E Ri and hyperparameters a E R200 scalar hyperparameters
p > 0 and À 2 0, learners , K + IRS, projections co : K + Ko
for 0 E O do
w (0) - and 1J1 (0) <- m(0)+m(0)
// initialize MW and EWOO
2
for task t 1, ..... T do
sample 9g from O2 w.p. x exp(wI)
// sample from MW distribution
& x m.. .. (co, (x())
// run bandit OMD within-task
X(+1 + EE=18 X,
// FTL update of initialization
for 0 E O₁ do
(o))) exp( (9) Eiss US/ vx)
10) t-
// EWOO step size update
!, exp -a(0) Eisz (x,,,))) (
W1+1 f we( AU,(x,, (1(0)) // MW update of tuning parameter
OMD on loss estimators E.. constructed via partial feedback forms an important class of bandit methods [6, 2, 3]. Their regularizers v are often non-Lipschitz, e.g. the negative entropy, or even unbounded, e.g. the log-barrier. Thus full-information results for tuning OMD, e.g. by Khodak et al. [31] and Denevi et al. [19], do not suffice. We do adapt the former's approach of online learning a sequence Ux 7)0) of affine functions of Bregman divergences from initializations x to known points in K. We are interested in them because the regret of OMD w.r.t. comparator y is bounded by [yy||x//n + (nm) [46, 25]. In our case the comparator is based on the estimated optimum & E arg minxex x), where & E le.i, resulting from running OMD on task t using initialization E IC and hyperparameters r and 6, which we denote OMD,, (x)). Unlike full- inllrrftrmttion meta-learning, we use a parameter E >> 0 to constrain this optimum to lie in a subset K, C KC. Formally, we fix a point x1 E KC' to be the "center"- e.g. X 11/ / when I. is the d-simplex A and define the projection c=(x) = + x-X:
I+E mapping from K. to K., For example, (x) = (1 - e)x + sla/d on the simplex. This projection allows us to handle regularizers vi that diverge near the boundary, but also introduces e-dependent error terms. In the BLO case it also forces us to tune e itself, as initializing too close to the boundary leads to unbounded regret while initializing too far away does not take advantage of task- similaiil Thus the general upper bounds of interest are the following functions of the initialization x, the step-size rj > 0, and a third parameter 0 that is either / or e, depending on the setting (MAB or BLO):
U,(x, n, 0) (e(co(()))l
(g(0)m + f(6mm
(3)
7)
Here Bg is the Bregman divergence of vhe while g(0) > 1 and f(0) 2 0 are tunable constants. We overload 0 to be either 3 or = for notational simplicity, as we will not tune them simultancously: if (for MAB) then (x(x) x1 + X-xI for fixed e, while if 0 E (for BLO) then B& is the Bregman divergence of a fixed vb The reason to optimize this sequence of upper bounds U, is because they di- rectly bound the task-averaged regret while being no worse than the worst-case single-task regret. Fur- thermore, an average over Bregman divergences is minimized at the average X T Σ &r, where it attains the value V/2 = + ΣT= vhe (ca (x,) - the (Co (x)) (c.f. Claim A. We will show that this quantity leads to intuitive and interpretable notions of task- similarity in all the applications we study.
I+E
2.2 A meta-algorithm for tuning bandit algorithms
To learn these functions Ug (x. 17, and thus to meta-learn (x) our algo-ihgo sets x to be the projection Co of the mean of the estimated optima-i.e. follow-the-leader (FTL) over the Bregman divergences in w3ile simultaneously setting v via EWOO and 0 via discrete multiplicative weights (MW). We choose FTI., EWOO, and MW because each is well-suited to the way U, depends on x. 7) and 0, respectively. First, the only effect of x on Ug is via the Bregman
4

---

divergence Bo(ce(8x)]1x) over which FTL attains logarithmic regret [31]. For 1). U2 is exp-concave on 17 so long as the first term is nonzero, but it is also non-Lipschitz; the EWOO algorithm is one of the few methods with logarithmic regret exp-concave losses without a dependence on the Lipschitz constant [26], and we ensure the first term is nonzero by regularizing the upper bounds as follows for some p > O and D = maxx.yEKe (x
U,O0 (x. 17. 0) = Bo(co( & ) + D² + ng(0) + f(0)m
(4)
77
Note that this function is fully defined after obtaining &, by running OMD on task i, which allows us to use full-information MW to tune @ across the grid Ø₁. Showing low regret w.r.t. any A O C O₂ then just requires sufficiently large & and Lipschitzness of U2 w.r.t. 0. Combining all three algorithms together thus yields the guarantee in Theorem 2.1, which is our main structural result. It implies generic approach for obtaining meta-learning algorithms by (I) bounding the task-averaged regret by an average of functions of the form U,, (2) applying the theorem to obtain a new bound (1) + ming,, V. + n9(0)m + f0)m, and (3) bounding the estimated task- similarit V2 by an interpretable quantity. Crucially, since we can choose any 1j > O, the asymptotic regret always as good as the worst-case guarantee for running the base-learner separately on each task.
Theorem 2.1 (c.f. Thm. A.1). Suppose X1 = arg xex Vo(x) V and let D, M, F, and S be maxima over f of Do. Dov g(0)m, f(0), and Voll,, respectively. For each p E (0. 1) we can set n. T7 a and À s.t. the expected average of the losses Ur(co, (xx), ((.)). 81) of Algorithm I is at most
EVZ
Fm
Ln
M min p²T
[D²D= PM J
S T/T
min 0E0.150
+ ((0)))+((0))+)))
(5)
VT
Here V/2 = 1 Et= (c((c(()))) - colco (x)) and Ly bounds the Lipschitz constant w.E.T O at
T
1/2 /n + (9(0) - f(0)m. The same bound plus (M/p Fm)y? log }/2 holds w.p. 2 2116. 8.
We keep details of the dependence on S and other constants as they are important in applying this result, but most cases setting p - - yields Ó(T regret. While a slow rate, the losses U, are non-Lipschitz and non-convex in-general, and learning them allows us to tune & over user-specified intervals and 1) over all positive numbers, which will be crucial later. At the same time, this tuning what leads the slow rate, as without tuning (k = 1, L,, 0) the same P yields Ö(VT) regret. Lastly, while we focus on learning guarantees, we note that Algorithm I is reasonably efficient, requiring a 21 single-dimensional integrals per task; this is discussed in more detail in Section A.3.
3 Multi-armed bandits
We now turn to our first application: the multi-armed bandit problem, where at each round of task t we take action ag.s E [d] and observe loss (a,s() E [0, 1]. As we are sampling actions from distributions x E XC = A on the k-simplex, the inner product (6,,,, is the expected loss and the optimal arm de on task t can be encoded as a vector &, s.t. (a) = Lazd.
We use as a base-learner a generalization of Exp3 that uses the negative Tsallis entropy whe (p) = اーدي (a) for some 3 E (0, 1] as the regularizer; this improves regret from Exp3's 1-3
(Vdmlog d) to the optimal O(vdm) [3]. Note that -W is the Shannon entropy in the limit + 1 and its Bregman divergence (x is non-convex in the second argument. As the Tsallis entropy is non-Lipschitz at the simplex boundary, which is where the estimated and true optima X; and & lie, will project them using C, (x) (1 - E)x ela/d to the set K. K, = (x E A mina x(a) 2 e/d]. We denote the resulting vectors using the superscript (E), e.g. x = = (xt), and also use A (t) = K, to denote the constrained simplex. For MAB we also study two base-learmers: (1) implicit exploration and (2) guaranteed exploration. The former uses low-variance loss under-estimators (a) = fx,(a))
[ for 7 > 0, where (t,((a) is the probability of sampling on task round i, to enable high probability bounds [43]. On the other hand, guaranteed exploration uses unbiased loss estimators (i.e. 7 = 0) but constrains the action space to (E)), which we will use to adapt to fask-similarity determined by the true optima-in optima-in-hindsiee in-hinssight.
5

---

3.1 Adapting to low estimated entropy with high probability using implicit exploration
In our first setting, the base-learner runs n,, (xt,1) on 7-regularized estimators with Tsallis regularizer vs,, step-size Th, and initialization Xt,1 (+), Standard OMD analysis combined with implicit exploration analysis [43] shows (44) that the task-averaged regret is bounded w.h.p. by
T Be,
(x.
xx,1)
nd m
(s + r + o
TT
T)t
Be
[=1
The summands have the desired form of Us (x Te, Bt), so by Theorem 2.1 we can bound their average by
VB
ndd m
( Ly
(2)2-2
min AE "
+ δ
k +
+ p+ PVT + p²T dym
B
ni
where = + ( ths (x is the average difference Tsallis entropies between
the (e-constrained) estimated optima & and their empirical distribution x = ΣT= & while Ly V ?
is the Lipschitz constant of + yd m w.r.t 3 E [3.3]. The specific instantiation of Algorithm 1 that (7) holds for is to do the following at each time t:
1. sample 3, via the MW distribution x exp(w,) over the discretization O2 of [
C [0,
2. run OMDm.,A. using the initialization Xt,1
Σ
+1a+ Σ sct
8 (FTL)
(8)
3. update EWOO at each 3 E O₂ with loss Ba(2( X1 1)
D
+ gd B
where D3 = 2l d
1-9
4. update P++1 using multiplicative weights with expert losses
(2( (Ix.a)
nd
The final guarantee for this procedure, given in full in Theorem B.I, follows by two properties of the Tsallis entropy -bh: (1) its Lipschitzness w.r.t. 8 E [0, (c.f. Lem B.1) and (2) the fact that V/3 is bounded by the entropy H3 b ()) of the empirical distribution of estimated optima (c.f. Lem B.2), which yields our first notion of task-similarity: multi-armed bandit tasks are similar if the empirical distribution of their (estimated) optimal arms has low entropy.
We exemplify the implications of Theorem B.I in Corollary 3.1, where we consider three regimes of the lower bound on the entropy parameter: 3 = 1, i.e. always using Exp3; 3 = 1/2,, which corresponds to the optimal worst-case setting [3]; and B = 1/ log d, below which the OMD regret-upper-boune always worsens (and so it does not make sense to try B < 1/ log
Corollary 3.1 fc.f. Cors. B.1. B.2, and B.3). Suppose 3 = 1 and we set the initialization, step-size, and entropy parameter of Tsallis OMD with implicit exploration via Algorithm as in Theorem B.1.
1. If = and T 2
da we can ensure T
(x..)).) (x.) S 2 H + δ t=
Σ Σ
d3
m
w.h.p
VT
2. If 8 and T >
/222 we can set ls = (TrTT and ensure w. w.h.p. that task-averaged regret is d m/7 d
min 2/ H3d9m/3 3 + 3E
+
(9)
T2/7
VT
3. If log and T > L
can set k VdVT and ensure w.h.p. that task-averaged regret is (3// /33/m/3/4 + d m
min 2 f Ö BE(D.1)
(10)
VT
In all three settings, as T + 0o the regret scales directly with the entropy of the estimated optima-in-hindsighhe which is small if most tasks are estimated to be solved by one of a few arms and large if all arms are used roughly equally. Corollary 3.1 demonstrates the importance of tuning 3: even if tasks are dissimilar, we asymptotically recover the worst-case optimal guarantee dddm)
d'-A On the other hand, a constant s & in cases two and three because the entropy is at most 1-g
actions are always minimizers, i.c. the empirical distribution x is s-sparse, then the last bound (10)

---

implies that Algorithm 1 can achieve task-averaged regret (m(m)) + (v smllood At the same dym
time, this tuning is costly, with the last two results having an extra Ô Furthermore, the bound of 3 = has a slightly better dependence on d, m. and T compared to that
term because of it.
VT
of B logd due to the ( 2-8 term in the bound (7) returned for MAB by our structural result.
We can compare the s-sparse result to Azizi et al. [10], who achieve task-averaged regret Ó(m/ hTm/VT+ + /sm log T) for stochastic MAB. Despite our adversarial setting and no stipulations on how tasks are related, our bounds are asymptotically comparable if the estimated and true optima are roughly equivalent (ignoring their (VVlog T') -factor), as we also have ((ysm) average regret as T - oc. Their rate in the number of tasks is better, but at cost of runtime exponential in s. Apart from generality, we believe a great strength of our results is their adaptiveness; unlike Azizi al. [10], we do not need to know how many optimal arms there are to adapt to there being few of them.
3.2 Adapting to the entropy of the true optima-in--ie in-hindsight using guaranteed exploration
While the entropy of estimated optima-in- iiniiniggghth may be useful in some cases where wish to actually compute the musk-similarity it is otherwise generally more desirable to adapt to an intrinsic and pogrrithm-ineepeddeee
measure, e.g. the entropy of the true optima-in maaaaaii--inniighi However, doing so is difficult without further assumptions, as the optima are both hard to identify and the measure itself may not be fully defined in case of ties. Thus in this section we focus on the setting where we have a nonzero performance gap A > 0 between the best and second- arms:
Assumption 3.1. For some A and all tasks & (T). T7 Σ (,,(a) ((,) 2 A A aa at.
This assumption is common the best-arm identification literature [28, 1]. which we adapt to show that the estimated optimal arms match the true optima, and thus so do their entropies. To do so, we switch to unbiased loss estimators, i.e. 7 0, and control their variance by lower-bounding the probability of selecting an arm to be at least 5: this can alternatively be expressed as running OMD using the regularizer v [a(e, where for any C C Id the function (x) 0 if x C and do otherwise. Guaranteed exploration allows us extend the analysis of Abbasi- Yadkori et al. [1] to show that the estimated arm is optimal w.h.p.:
Lemma 3.1 (c.f. Lem C.I). Suppose for > and any 3 E (0, 1] we run OMD on task E [T] with regularizer 3 + Itte m = (=)2=) then & = X, w.p. 2 1 dee
However, the constraint that the probabilities are at least á does lead to sm additional error on each task, with the upper bound on the task-averaged expected regret becoming
T
T Σ (as(arr)) - (a,) <mm= + T
EBg (x)
(xx.) + medPim m
E
(11)
Th
B,
Moreover, we will no longer set E = or (1), as this would require m to be increasing in T for the best- arm identification result of Lemma C. hold. Thus, unlike in the previous section, our results will contain "fast" temms-term in the task-averaged regret that are o( /m) but not decreasing in T nor affected by the task-similarity. They will still improve upon the 2 dm) MAB lower bound if tasks are similar, but the task-averaged regret will not converge to zero as T + oo if the tasks are identical.
Nevertheless, the tuming-dependent component of the upper bounds in (11) has the appropriate form for our structural result-in fact we can use the same meta-algorithm (8) as for implicit exploration-and and so we can again apply Theorem 2.1 to get bound on the task-averaged regret
in terms of the average difference 1/ = - ΣT= (R(( - (x(+)) of the entropies of the
e-constrained estimated task-optima x(() and their mean (e)) The casiest way to apply Lemma C.1 to bound 1/3 in terms of H₂ Σ th - v (Xx is via union bound all T tasks to show that & x, V w.p. 2 1 - dT (app(2Q(2mmmm// / however, setting a constant failure probability leads to m growing, albeit only logarithmically, in T. Instead, by analyzing the worst-case best-arm identification probabilities, we show in Lemma C.2 that the expectation of 1/2 is bounded by
Hg + 3,8 (d/e)* P-1 1-9 exp (-
Am without resorting to m (1). Assuming m 2 75d log d 28d
= enough (69) to bound the second term by 56 Then the final result (c.f. Thm. C. bounds the dnz
expected task-averaged regret as follows (ignoring terms that become or (1) after setting p and k):
7

---

m 8
Hg +
56
if
m 2 75d log d
ET
min BEl0,8,,n50
"
for he(A))
1-3
9
md
otherwise
(12)
If the gap A is known and sufficiently large, then we can set E ① 33 to obtain an asymptotic task-averaged regret that scales only with the entropy H3 and a fast term that logarithmic in mi
Corollary 3.2 (c.f. Cor. C.3). Suppose we the initialization, step-size, and entropy parameter of Tsallis OMD with guaranteed exploration via Algorithm I as specified in Theorem C.I. 1f Loga 1] and m z
15d
log d. A 3 then setting E ô (x²m) = VaVmr and h = [VdmT
ensures that the expected lask-averaged regret is at most
d
d3m
di m
d T
2/ Had&m// m/3 + RE(0,1)
min
(13)
A
T
Knowing the gap A is a strong assumption, as ideally we could set without Note if S2( m"
for some p E (0, 1) then the condition m 2 zAa log zAz only fails if m S poly( 1) i.e. for gap decreasing in m. We can use this together with the fact that minimizing over 1j and / in our bound allows us to replace them with any value, even gap-dependent one, to derive a gap-independent bound when A is not too small and falls back to
setting of e that ensures a aask-smilarity-adaptee the worst-case optimal guarantee otherwise. Specifically, for indicator is = lmz
75t log ra2
setting
es?
θ
(v
ha(A) 10m/R
in (12) and using 3 = j/ if the condition is fails yields asymptotic regret at most
em + min (E(00,)
LA
Mad m
+ +11+1111))) (1-12)Vdm) em + Ô min
min (E(0,
Had m
vdm
Ave'
(14)
Thus setting = O(vd/m3) yields the desired dependence on the entropy H3 and a fast term in m:
Corollary 3.3 (c.f. Cor. C.4). the setting of Corollary 3.2 but with m ((d and unknown A. using= E = ((v ((Vd/m3 d/m3) ensures expected task-averaged regret at most
2 Hgddm/BB + Ö (d Vm (
dd ddmm
d3 damå
dm3
min
min 8E(0,1)
.88dm dm
+
(15)
A
V
T
T
While not logarithmic, the gap-dependent term is still o() and moreover the asymptotic regret is no worse than the worst-case optimal O (Vdm). Note that the latter is only needed if A = o(1/ m)).
The main improvement in this section is in using the entropy of the true optima, which be much smaller than that of the estimated optima if there are a few good arms but large noise. Our use of the gap assumption for this seems difficult to avoid for this notion of task-similarity We can also compare to Corollary 3.1 (10), which did not require A >> 0 and had no fast terms but had a worse rate in T: in contrast, the O VT rates above match that of the closest stochastic bandit result [10].
As before, for < d "good" arms we obtain O(ysm log d) asymptotic regret, assuming the gap is not too small. Finally, we can also compare to the classic shifting regret bound for Exp3.S [6]. which translated to task-averaged regret is O( dm log(dm This is worse than even running OMD separately each task, albeit under weaker assumptions (not knowing task boundaries). also cannot take advantage of repeated optimal arms, e.g. the case & d good arms.
3.3 Adapting to entropic task similarity implics robustness to outliers
While we considered mainly the s-sparse setting as a way of exemplifying our results and comparing to other work such as Azizi et al. [10]. the fact that our approach can adapt to the Tsallis entropy ming 11, of the optimal arms implies meaningful guarantees for any low-entropy distribution over the optimal arms, not just sparsely- supported ones. One way to illustrate the importance of this is through an analysis of robustness sparsely-supported
outlier tasks. Specifically, suppose that the s-sparsity assumption that optima àe lie in a subset of [T'] of size < d d'only holds for all but ((T)) of the tasks E [T). where p E [0, 1). Then the best can do using asymptotic bound of Ö( ((ysm) e.g. that of Azizi et al.
8

---

[10] in the stochastic case or from naively applying min Had m/5 I esm log d to any of our previous results is to substitute + T instead of s. which will only improve over the single-task bound if d = w(PP), i.e. in the regime where the number of arms increases with the number of tasks.
However, our notion of task-similarity allows to do much better, as can show (c.f. Prop. D.1) that in the same setting H3 = ((s + T for any 3 E log d' 21 Substituting this result into e.g. Corollary 3.3 yields the same asymptotic result of O sm log d), although the rate in T is very slow O v ddm Taggd)) This demonstrates how our entropic notion of task-similarity simultaneously yields strong results in the s-sparse setting and is meaningful in more general settings.
4 Bandit linear optimization
Our last application is bandit linear optimization, in which at task round i we play Xt,i E KC in some convex IC C. Rd and observe loss (ft,.. Xx,1) E [-1, 1]. We will again use a variant of mirror descent, using a self-concordant barrier for e and the specialized loss estimators of Abernethy et al. [2, Alg. Ij. More information on such regularizers can be found in the literature on interior point methods [42]. We pick this class of algorithms because of their optimal dependence on the number of rounds and their applicability to any convex domain K. via specific barriers s which will yield interesting notions of task- similaiiiaarity.. Our ability to handle non-smooth regularizers via the structural result (Thm. 2.1) is even more important here, as barriers are infinite at the boundaries. Indeed, we will nor learn a 39 parameterizing the regularizer and instead focus on tuning a boundary offset > O. Here we make of notation from Section 2, where c₂ maps points in K. to subset KCe defined by the Minkowski function (c.f. Def. E.1) centered at X1 = arg min (x)).
From Abernethy et al. [2] we have an upper bound on the expected task-averaged regret of their algorithm run from initializations Xx,1 E K with step-sizes n/e >> 0 and offsets 6, > 0:
1 T
T
EB(c,, (Xt (xx1) (32m,d + +))m
E
Cla x x1) S
(16)
T
9 where v is the self-concordance
We can show (88) that D2- = yEK, B(xlly)= S
constant of & and S = ((2) is the spectral norm of its Hessian at the center XI of K. Restricting to tuning the estimated optima & are identical-we we can now apply Algorithm via the following instantiation:
[ JJ-whicch is enough to obtain constant task-averaged regret above if
1. sample e, via the MW distribution x exp(w,, over the discretization
2₂ of
2. run OMD using the initialization Xx,
- Σ sct Ca2 (Xx) -x1 + (I+8)((-I)
Excr x (FTL)
3. update EWOO at each e E O2 with loss Bie,, (1ll + 32d for D² g KVS.
"
4. update p++1 using multiplicative weights with expert losses (&,) + em
(17)
Note the similarity to the MAB case (8), with the difference being the upper bound passed to EWOO and MW. Our structural result bounds the expected task-averaged regret as follows (c.f. Thm. E.1):
V2 + (32nd + +)mm +
m² T
+ min {2 do
dm
log k
dm
E min
17
22T
(18)
For p= or()) and k = (1) this becomes or (poly(m)) + ul,n0
022 32nd + em,
where V:2 +IT, (bcc (Xx) (cCc (Rx.) Then by tuning 1) we get an asymptotic (I' + 20) regret of 4dV. /2m + em for any 8 E [1,, 1]. Our analysis removes the explicit dependence on vi that appears in the single-task regret [2]; as an example, v equals the number of inequalities defining a polytope K., as in the bandit shortest-path application below.
The remaining challenge is to interpret V which as we did for MAB we do via specific examples, in this case concrete action domains AC. Our first example is for BLO over the unit sphere K. fx
Rd ||x|] < 1} using the appropriate log- barrierierr regularizer (xx) logg1 ||x

---

Corollary 4.1 (c.f. Cor. E.1), For BLO on the sphere, Algorithm 1 has expected task task-averaged regret
dm
dm
2m log (1 1 1 2: + 8
+
min cE(m.
4d
sm
(19)
T
VT)
The bound above is decreasing in E the expected squared norm of the average of the estimated optima &t We thus say that bandit linear optimization tasks over the sphere are similar if the norm of the empirical mean of their (estimated) optima is large. This makes intuitive sense: if the tasks' optima are uniformly distributed, we should expect || | to be small, even decreasing in d. On the other hand, in the degenerate case where the estimated optima &, are the same across all tasks t E [T], we have E| { 2 1, so the asymptotic task-averaged regret is because we can use 1 Perhaps slightly more realistically, it is w -away from for some power p 2 2 then setting E = v can remove the logarithmic dependence on m. These two regimes illustrate the importance of tuning
1
As a last application, we apply our meta-BLO result to the shortest-path problem in online optimization [50, 30J. In its bandit variant [8, 17]. at each step i = 1.... m the player must choose a path p; from a fixed source u E V fixed sink & E V in directed graph G(V, E). At the same time the adversary chooses edge-weights & E RIEI and the player suffers the sum Eeeps (a(e) of
the weights in their chosen path pt. This can be relaxed as BLO over vectors x in set K. C [0, 1] defined by a set of ((E)) linear constraints (a, b) (a, x) S b enforcing flows from u to v; u to paths can be sampled from any x E K. in an unbiased manner [2, Proposition 1]. On single-instance & /m) regret this problem.
applying the BLO method of Abernethy et al. [2] ensures O E)
In the culti-insstace setting, comprising a sequence t 1..... T of shortest path instances with m adversarial edge-wein weight vectors l,, each, we can attempt to achieve better performance by tuning the same method across instances. Notably, we can view this as the problem of learning predictions [33] in the al algorithms with predictions paradigm from beyond-worst-cas analysis [40], with the OMD initialization on each instance being effectively a prediction of its optimal path. Our meta-learner then has the following average performance across bandit shortest-path instances:
Corollary 4.2 (c.f. Cor. E.2). For multi-task bandit online shortest path, Algorithm I with regularizer (x) Enbbcc log(b - x)) attains the following expected average regret across instances
E 1 T
E 3 m VT
1 + b co T
+ min
4EE
2m
log
+em (20)
<E EE
1 |I b ca.c (8,))
D.EEC
Here the asymptotic regret scales with the sum across all constraints a E C of the log of the ratio between the arithmetic and geometric means across tasks of the distances b b- (a, c, (x,)) from the estimated optimum flow c₂ (xx)) to the constraint boundary. As it is difficult the effect of the offset é, we do not state an explicit task-similarity measure like in our previous settings. Nevertheless, since the arithmetic and geometric means are equal exactly when all entries are equal-and otherwise the former is larger- the bound does show that regret is small when the estimated optimal flows &, for each task are at similar distances from the constraints, i.c. the boundaries of the polytope. Indeed, just as on the sphere, if the estimated optima are all the same then setting e m again yields constant averaged regret.
separate
5 Conclusion and limitations
We develop and apply meta-algorithm for learning to initialize and tune bandit algorithms, obtaining task-averaged regret guarantees for both multi-armed and linear bandits that depend on natural, setting-specife notions of task similarity. For MAB, we meta-learn the initialization, step-size, and entropy parameter of Tsallis-entropic OMD and show good performance if the entropy of the optimal arms is small. For BLO, we use OMD with self-concordan regularizers and meta-learn the initialization, step-size, and boundary- yielding interesting domain-spy seennnn-ppeffic task- similariyy measures. Some natural directions for future work involve overcoming some limitations of our results: can we adapt to a notion of fask-similarrty that depends on the true optima without assuming a gap for MAB, or at all for BLO? Alternatively, can we design meta-learning algorithms that adapt to both stochastic and adversarial bandits, i.e. a soas-oo--oth-worllde guarantee? Beyond this, one could explore other partial information settings, such as contextual bandits or bandit convex optimization.
10

---

Acknowledgments
We thank our anonymous reviewers for helpful suggestions, especially concerning the analysis of robustness to outliers. This material is based on work supported in part by the National Science Foun- dation under grants 191032,,, FAI- 1939606, IIS 1901403, SCC-1952085, and SES-1919453; the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003; Si- mons Investigator Award; an AWS Machine Learning Research Award; an Amazon Research Award; Bloomberg Research Grant; a Microsoft Research Faculty Fellowship; Google Faculty Research Award; a J.P. Morgan Faculty Award; a Facebook Research Award; Mozilla Research Grant; Face- book PhD Fellowship; and an NDSEG Fellowship. KYL supported by the Israel Science Foundation (grant No. 447/20) and the Technion Center for Machine Learning and Intelligent Systems (MLIS). The work of RM was partially supported by the Israel Science Foundation grant number 1693/22.
References
[1] Yasin Abbasi- Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Proceedings of the 31st Conference On Learning Theory, 2018.
[2] Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the International Conference on Computational Learning Theory, 2008
[3] Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with a new kind of smoothness. In Advances in Neural Information Processing Systems, 2015.
[4] Oren Anava and Zohar Karnin. Multi-armed bandits: Competing with optimal sequences. In Advances in Neural Information Processing Systems, 2016.
[5] lean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Minimax policies for combinatorial prediction games. Proceedings of the International Conference on Computational Learning Theory, 2011.
[6] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal of Computing, 32:48-77, 2002.
[7] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number distribution changes. In Proceedings of the 32nd Annual Conference on Learning Theory, 2019.
[8] Baruch Awerbuch and Robert D. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the Thirty-Sixth Annual ACM Symposium Theory of Computing, 2004.
[9] Mohammad Gheshlaghi Azar, Alessandro Lazaric, Emma Brunskill, et al. Sequential transfer in multi-armed bandit with finite set of models. In Advances in Neural Information Processing Systems, 2013.
[10] MohammadJavad Azizi, Thang Duong, Yasin Abbasi-Yadkori András György, Claire Vernade, and Mohammad Ghavamzadeh. Non-stationary bandits and meta-learning with a small set of optimal arms. arXiv, 2022.
(11) Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Proceedings of the 28th Annual Conference on Learning Theory, 2015.
[12] Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to- learn non-convex piccewise-Lipschizz functions. In Advances in Neural Information Processing Systems, 2021.
[13] Soumya Basu, Branislay Kveton, Manzil Zaheer, and Csaba Szepesvári. regrets for learning the prior in bandits. In Advances in Neural Information Processing Systems, 2021.
11

---

[14] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
[15] Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[16] Nicolò Disa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[17] Varsha Dani, Thomas Hayes, and Sham Kakade, The price of bandit information for online optimization. In Advances in Neural Information Processing Systems, 2008
[18] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learning around a common mean. In Advances in Neural Information Processing Systems, 2018 8.
[19] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Unline-withinn-ne meta-lcarning. In Advances in Neural Information Processing Systems, 2019.
[20] Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[21] Yan Duan, Marcin Andrychowicz, Bradly Stadie, Jonathan Ho, Jonas Schneider, Ilya Sutskever, Pieter Abbeel, and Wojeiech Zaremba. One-shot imitation learning. In Advances in Neural Information Processing Systems, 2017.
[22] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, 2020.
[23] Xiequan Fan, Ion Grama, and Quansheng Liu. Hoeffding's inequality for supermartingales. Stochastic Processes and their Applications, 122(10):3545-33) 2012.
[24] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, 2017.
[25] Elad Hazan. Introduction to online convex optimization. In Foundations and Trends in Optimization, volume 2. pages 157-325, now Publishers Inc., 2015.
[26] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69:169-19 192, 2007.
[27] Ali Jadbabaie, Alexander Rakhlin, and Shahin Shahrampour. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference Artificial Intelligence and Statistics, 2015.
(28) Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparame- ter optimization. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, 2015.
[29] Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv, 2019.
[30] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 11:291-307,2000
[31] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive tradient-baseed meta- learning methods. In Advances in Neural Information Processing Systems, 2019.
[32] Mikhail Khodak, Renbo Tu, Tian Li, Liam Li, Maria-Florina Balcan, Virginia Smith, and Ameet Talwalkar. Federated hyperparameter tuning: Challenges, baselines, and connections to weight-sharing. In Advances in Neural Information Processing Systems, 2021.
12

---

[33] Mikhail Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. In Advances in Neural Information Processing Systems, 2022.
[34] Branislav Kveton, Martin Mladenov, Chih-Wei Hsu, Manzil Zaheer, Csaba Szepesvári, and Craig Boutilier. Meta-learning bandit policies by gradient ascent. arXiv, 2020.
[35] Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-Wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvári. Meta-Thompson sampling. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[36] Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-SOr SGD: Learning to learning quickly for few-shot learning. arXiv, 2017.
[37] Haipeng Luo. CSCI 699 Lecture 13, 2017. URL https://haaipng:: luo. net/ courses/CSCI (wSESCI699//0 1tt.e///11c9//eeerrr3.......
[38] Haipeng Luo, Chen- Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits
in non-stationary worlds. In Proceedings of the 31st Annual Conference on Learning Theory, 2018.
[39] Teodor Marinov and Julian Zimmert. The Pareto frontier of model selection for general contextual bandits. In Advances in Neural Information Processing Systems, 2021.
[40] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Rough- garden, editor, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge, UK, 2021.
[41] Ahmadreza Moradipari, Mohammad Ghavamzadeh, Taha Rajabzadeh, Christos Thrampoulidis, and Mahnoosh Alizadeh. Multi-envirrnment meta-learning in stochastic linear bandits. In Proceedings of the 2022 IEEE International Symposium on Information Theory, 2022.
[42] Yurii Nesterov and Arkadii Nemirovskii. Interior-Poid Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied and Numerical Mathematics, 1994.
[43] Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems, 2015.
[44] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv, 2018
[45] Nikunj Saunshi, Yi Zhang, Mikhail Khodak, and Sanjeev Arora. A sample complexity separation between non-convex and convex meta-learning. In Proceedings of the 37th International Conference Machine Learning, 2020.
[46] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2): 2011.
[47] Amr Sharaf and Hal Daumé III. Meta-learning effective exploration strategies for contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[48] Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel J. Hsu, Thodoris Lykouris, Miro Dudik, and Robert E. Schapire. Bayesian decision decision-making under misspecified priors with applications to metannn. In Advances in Neural Information Processing Systems, 2021.
[49] Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning.
In Advances in Neural Information Processing Systems, 2017.
[50] Eiji Takimoto and Manfred K. Warmuth. Path kernels and multiplicative updates. Journal of Machine Learning Research, 4:773-818 2003.
[51] Sebastian Thrun and Lorien Pratt. Learning to Learn. Springer Science & Business Media,
1998.
13

---

[52] Constantino Tsaliis. Possible generalization of Boltzmann-Gibel statistics. Journal of Statistical Physics, 52:479 487, 1988.
[53] Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[54] Takuya Yamano. Some properties of q-logarithm and q-exponential functions in Tsallis statistics. Physica A: Statistical Mechanics and its Applications, 305:486-496, 2002.
[55] Peng Zhao, Guanghui Wang. Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125))1-45, 2021.
14

---

A Structural results
A.1 Properties of the Bregman divergence
Lemma A.1. Let sb C + R be strictly convex function with maxxec (x)]l2 S S over a convex set C C IR over size maxxec ||x||2 I K, and let B(-ll.) be the Bregman divergence generated by v. Then for any points XI,,..,XTT E C the actions yı arg min (x) and Yt T-T Eser X, have regret
T
8SK2
B(x.lly)) - B(x:llyt+)) <
Σ 1=1
21 (1+
(21)
t=1
Proof. Note that
By v (V(())), Vy(Ve(y).)) diag(V" x)
(22)
B(x+ |1)) is -2S--Lipschii
the Euclidean Applying Khodak al. [31, Prop. B.1]
yields the result (note that its assumption of strong convexity the regularizer can be replaced with strict convexity without changing the proof or result).
Claim A.1. Let sb K. + IR be a strictly-conver function with Bregmun divergence B(-lI-) over convex set K. C Rd containing points X1 , XT. Then their mean + Et Xr satisfies
T
Σ
B (xx
(X) = Σ (xx)) ((x)
(23)
Proof.
T
Σ B(x| x
Σ
(xx)) - (xx) (Ve((x,, x1 xX
1=1
(24)
T
T
Σ
(xxx) (xx) (x)(x),
X1 x) = Σ xxxx)) - (xx
[=1
A.2 Tuning the step-size
Lemma A.2. Let ly...., ......,r.. lr E20 Ryo be sequence of functions of form (((z) B2 G2x
for adversarially chosen B, E D) and some G >> 0. Then for any 2 0, the actions of
EWOO 126, Fig. 4] with parameter DC run on the modified losses B²+ D² + G over the domain
20²
PD G V p² achieves regret w.r.t any x of
DDD . T+ DG(1 + log(T + 1)) x
-()))=((x)) min
(25)
2p²
Proof. By Khodak et al. [31, Prop. C.1] the modified functions are exp-concave. Then Khodak al. [31, Cor. C.2] with B, set G. to C a₃ = G and ε σ yields the result.
20
DG
aD
15

---

Lemma A.3. For 81..... .. E OK consider sequence of fumetions of form
Ux(x,n) B((x((x)llx) +n
(26)
7
where B is the Bregman divergence of a strictly convex d.g.f. sb : K + I. and where X1 = arg min (x) defines the projection cz(x) x1 + Ite
x-XI for some 0 Suppose we play
X++1 t Ce (: ( x,)
and set using the actions of EWOO [26, Fig. 4] with parameter 2Ø²
DG for
& D2 V Kig on the functions (l) + +1 over
some P. Dg > S.I.
the domain
DDe Gym
l+p² m
with th being at the midpoint of the domain. Then U2(Xi, m1) S
D.Gym m
/ p2
A t E TT
and
T
T
B(cx((2))1z)
Ul(x),
S
min x>0,xK.
+ +n
7
1=1
D "
.pDDG T+ D&G(1 (Tg(T++1)
8S,K²(1 + log T)
min
2p²
7
(27)
for = =maxxex |xx|2 and S. = maxxek, (x)(l>)22
Proof. The first claim follows by directly substituting the worst-case values of r) into (x 11). For the second, apply Lemma A.2 followed by Lemma A.l:
T
Ue(xi, mc)
T
(()((x))
+ Gm
n
D²D² .DD )
DeG(1 + log(T + +1)
B(cx(x:)lxx)
min min 020
T
Σ
17
2p²
n
1=1
p² D2
.D..G T D&G(1 + log(T + 1))
K2,K((1 + log
min min 0>0
2p2
((,)(())llx))
min xEK,
+ G
(28)
Conclude by noting that the sum of Bregman divergence to c. (xt) minimized on their convex hull, subset of K...
A.3
Computational and space complexity
Algorithm implicitly maintains a separate copy of FTL for each hyperparameter in the continuous space EWOO and the grid O₂ over the domain but explicitly just needs to average the estimated task-optima &;; this is due to the arean-as-minimize property of Bregman divergences and the linear- ity of c.. Thus the memory it uses is Od k),, where l size of the discretization of O and should be viewed as sublinear in T. c.g. for MAB with implicit exploration and BLO = O VTVT). Computa- tionally, each timestep t and for each grid point must compute two finlleddimensionll integrals; the integrands are sums of upper bounds that just need to incremented once per round, leading to a total per-iteration complexity of (k) (ignoring the running of OMD). Although outside the scope of this work, it may be possible to avoid integration by tuning ? with MW as well, rather than EWOO,
but likely at the cost of worse regret because it would not take ad advantage of the exp-concavity of U!!)
16

---

A.4 Main structural result
Theorem A.I. Consider a family of strictly convex functions vo : K2 H R. parameterized by lying in an interval θ C. I of radius Re that are all minimized at the same X1 E KC, and for 8,...., E Ok consider a sequence of functions of form U((x, 17, 8) (3), as well as the associated regularized up-
per bounds U(2) (4). Define the maximum divergence D = maXage Dø, radius K maxxeX | and Ln the Lipschitz constant w.r.t. 0 E of V2 + ng (0) m + f(0).. Then Algorithm I with O₁ C O the uniform discretization of θ s.t. maxgeo mingrea, 0 8' -
Re k
pDy E (0, 1), 2(0) g000m
(0)- Doy
9(0mm (x()) D())
1+
20² and X = (M 1 + vI+ + Fm))
log leads to
sequence (xx, 1/ (O.), 06) s.t. E Et (x( 1/ (0t), 0,) is bounded by
8SK (1 + log T)
V2
Ly Re k
sD²D2
}
E
min 8EB.m
+
(g + 5(0)
min { "1 .MM) T
"
4M
M + log(T + 1))
+ (pr p
+ Fm v TTllog +
2p²
(29)
and E1=1 U2 no (0c), is bounded w.p. > 81421 by
2 + log T) +
V22 + mg()m + f(0mm +
Re
L Re
min { pp22 pM })
min 0g0,120
r
"
k
4M
+ Fm)
(VTlogklaas// log
1
M(1 + log(T + 1))
+
+
2
2p²
(30)
Proof. In the following proof, we first consider online learning U.(.-.0) 0) for fixed 9 E Og. To tune 77, we online learn the one- veeddmmnnsionll losses (o (&,) (x + (9))), where co (x,)) is the (ne -nndepeeen)))) action of FTL. at time As discussed, the corresponding regularized losses t,(0) are exp-concave, and so running EWOO yields Ô (M/p² + min (p²D²/n) pM] } T) regret w.r.t. the original sequence [31, Cor. C.2]. At the same time, we show that FTL has logarithmic regret on the sequence Bg (cg(())) (-)) that scales with the spectral norm of V² (c.f. Lem. A.1), and that the average loss of the optimal comparator is V/3 (c.f. Claim A. Thus, since we only care about a fixed comparator 1), dividing by 1/ yields the first and last terms (5). We run a copy of these algorithms for each 0 O₂; since their losses are bounded by Ó(M p + Fm), textbook results for MW yield (VT k) regret w.r.t. 0 E O₁, which we then extend to θ 3 O₂ using I., .isshiipshistzssss
Formally, we have that
T
E
Ue(xe, (c)
t=1
(co, (8::
E
n((()))(0)) + f(0)
(b()
1=1
Bo(co(2i)lxx)) ()))()(0)) ((0)m (1(()
M
+ v2)
+Fm)
/2 log k E min BEE
P
4M
Bo(co(&:)llx)) + =g((0)m + 5(0m
+ Fm
VTlogk+ k E
min 0E
p
D22
Do Dovo(0)m(1 + +log(T + 1))
8SK (1 + log T)
+ min
pDoo (DDov(00)mL g00mm T
17
2p²
1
(31)
17

---

where the first inequality is the regret of multiplicative weights with step-size À [46, Cor. 2.14] and the second is by applying Lemma A.3 for each A. We then simplify and apply the definition of V/3 via Claim A.1 and conclude by applying Lipschitzness w.r.t. A:
E
Ux (1)
1=1
4M
V?2
+ Fm
/Tlok +
min
+ +g(0)mT + f(0)mT
p
7
D²
M(1 log(? (T + 1)) 8SK log
+ min
.PM
T
17
2p²
8SK2 + T)
V2
+ (0(mm + f(0)m + Re
min {
DD2D2
(ppr pad
77 ....aa))
S
min 0
+
T
k
4M
M(1 log(T + 1))
+
+ Fm
v Took k
2p²
(32)
The w.h.p. guarantee follows by Cesa-Bianchi and Lugosi [16, Lem, 4.1].
B Implicit exploration
B.1 Properties of the Tsallis entropy
Lemma B.1. For any (0, 1] and A s.t. x(a) 2 á a E [d] the 3-Tsallis entropy Hx(x)= 1 1- E. (a) dloog & Lipschit w.r.. 3 e [0. 1].
Proof. Let logg x== 2-0 be the 9-logarithm function and note that by Yamano [54, Equation 6] 1-3
we have log, log x = (1 - (O, log, æ + log, x logx) 2 0 V B E [0. Then we have for 3 E [0,1] that
-11((x)
Σd 1
-a= x (a) (a)log x(a)
[gHH((x)|=
1
x x (a)(0 x(a) log x(a))
1
8
d
1
(a)g x(a)
log ((a)
(33)
1 3
a=1
8
1-9
1
Σ x(a)
Σ (logs x(a) log x(a)
1 8
d
log, x(a) x(a) S I- (log 3 - log d
= s - dlog d
where the fourth inequality follows by Hölder's inequality, the fifth by subadditivity of I² for (0, 1]. the sixth by the fact that 0z (log, I logæ) x)
1/x < 0 8, x [0. 1), and
the last line by substituting 3 = 0 since 03 log, z log 2(
(1-0) log < 0YAB B
a (1- 81
[o, 1), (0, 1/d]. For 1, applying I. Hôpital's rule yields
1 lim 8-21
1 Σ x x(a) log x(a)
lim 03 Hz(x) 8-1
x (a) log x(a)(1 (1 B3 logx(()) -
(34)
which is bounded 1-2d/e2 0).
D
18

---

Lemma B.2. Consider Sinsiderx......... X1...., Xy E A s.t. x,(ai) = 1 for some E [d], and let = 7 Ei=1 X, be their average. For any (0, 1] and (0, 1] we have that for every t [T]
Hx( - (x ) - Hx(x)
(35)
where recall that x(e) C (x) = 1 la/ (1 c)(x la/d) = (1 - 5)x + g/a-
Proof. Assume w.l.o.g. that x(1xx(() S xx2) S ... S x(d and as 1, so that x (c) (e)
ej
We take the
derivative
Hg (1 (1-
+ E
d _ - -o.Ha e
d
1
3
(11-)x(aa) + E/d)L-3 (s/d)1-3
(36)
d
1
(1- + E/d)2-3 ())=))((d) + e/d)2-9
d
{(a) ((1 ((1-s)x(d) + + ((1- =))(())+(d)))
1 1 3
By the assumption that ((a) is non-decreasing in a, each of the summands above become non non-positive. So for e E (0, 1] the derivative is non-positive, and for -> 0 it goes to -o0. Thus the h.h.s. of the bound is monotonically non-increasing in for all [0, 1]. The result then follows from the fact
that for 0 we have H3 ((1 e)x + 12) Ha (e)+) Hz(x).
B.2 Implicit exploration bounds
Lemma B.3. Suppose we play OMDs,n with regularizer 1h the negative Tsallis entropy and initial-
ization x1 E / on the sequence of linear loss functions e,,..., lr [0, 1]0. Then for any A have
T Σ t=1
X1,
x Bx(x
7 x 2-8 (a)(((a)
Σ
d
(37)
B
a=1
Proof. Note that the following proof follows parts of the course notes by Luo [37], which we reproduce for completeness. The OMD update at each step involves the following two steps: set Yt+1 E A s.t. (vbs(++11) = (x,)(x,) n/f, and then set X++1 arg mitxee BB V++1) ) [25, Algorithm 14]. Note that by Hazan [25, Equation 5.3] and nonnegativity of the Bregman divergence we have
Σ (4, x) Bx(x|xx)
1
T
B3(xellye+1)
(38)
" t=1
1=1
To bound the second term, note that when the is the negative Tsallis entropy we have
Bx(xe (
y (a) xx((a)
3
(xr(0) - Se+1(a))
3
(1)
d
(1- B)y (0) (a) +
+ 1-3
B per(a)
xx(a)
(39)
1 3 a=1
x 1--((a)
(a)
(itz (a) - (0) + (o)((()(())
19

---

Plugging the following result, which follows from (1+z)² =1taa 0,0 < 0. into the above yields the desired bound.
Y (0)
=-1
1 1-B
(4) =x](a)
x (a)
1+
1x
(xx-~(())((()))) (a)l((a)
x
3
(0)
B
-xt (axtt-((a)eell 1 (a)e((aa + 1 xx2=2((0)(((0))
(40)
S x (a)
3
- (2) -)xx((()(((()) + o 3 (a)a((a)
= xx
Theorem B.1. In Algoritum 1, let a a be online mirror descent with the Tsallis entropy regularizer Vs over rfoffset loss estimators, O₂ is subset of [3, 3] C <loga 11. and
U((x, q. B8 (2) (x) ndpm
(41)
B
where x(4) (1 =)8; l/d. Note that U.!0) (x, 3) Uc(x, 1/s 9) + 22 P-1).
Then there
mi1 ((1-3) 3)
exists settings of 17, T7. az À s.t. for all P, " E (0, 1) we have w.p. 2 8 that
ΣΣ 1=
(a,()) ((,))
dlog d
5
8d/m m
5k
1 + log(T + +1)
< (E + ydymT +
log
+
1
Tlog
+
8
p
5
16p
8 (1)) 2- (1 + log T)
H3
ndd m
Ln 3)
{ 12
min $E(3,0)1120
+ ddmin
PV
T
r7
B
2k
2n
(42)
for Ly = (Los nm log? d) d.
Proof. In this setting we have g(3) = d /B, f(3) = 0, D3
d'-3_1 1-3
..D DS Vd/2, M dym.
F S (d/e)2-L, and K 1. We have that
T m
(a)()))))) - (āt)
X1,)) - (0,( + Σ (a)((a
#=1
BB, (1x,1)
m
+ Σ
Cles x (c)) (ū,(
1): Ex
(1) + Σ (as(a)
x
Bi a=1
T
BR (X)
(x..1)
Σ (li.,, c(()) - (le,s, x(
<emT +
1=1
1- 8e Li
(a)le,(a)
+ +7 Σ les(a)
1
(43)
where the equality follows similarly to Luo [37] since (Le,s x,,) = (a,s(ar.)) - - Ed= (a)( the first inequality follows by Lemma B.3 and the second by Hölder's inequality and the definitions of
20

---

l and ((e) We next apply the optimality of â, for Ei= la, to get
T
( (q,i(ae)
T.
B3, (x4 (6)
+ - Σ ((,) ((s()s) + E d
< emT
+
Σ
(e,(a)
d
tm1
11
1- --
(a)lma(a) + Elu((a)
3
1+ c
d
+
5
T
Bg, (x, X1,1)
< 5mT +
log
+
27
0
t=1
m
11
1- B: (a)6)
Σ (a((a)
3 i=1
2 +
dlog
Bs, (8:
(xx11)
m). n.ddm m
EmT +
log + ddm +
3g
(44)
where the the second inequality follows by Neu [43, Lemma 1] applied each of the last four terms and the fifth by the definition of l,i and using max [mgaa)) 7(3) S v em log d' Substituting into
Theorem A.I and simplifying yields the result except with V/3 Σl= v)(((()) 3 in
place of Hg. but the former is bounded by the latter by Lemma B.2.
Corollary B.1. Let 3 B 1. Then w.h.p. we can ensure task- regret at most
dd/m + d
2 Hi + O
(45)
V
so long as mT & or alternatively ensure
dd (dim + +dym
d vmm
min 2v il
2 dm log d δ
(46)
VT
vT
so long as mf 2 d.
Proof. Applying Theorem B.1, simplifying, and dividing by T yields task-averaged regret most
2
dog em
5
1 log(T +1)
min 0²
( dym
b))
(d)m +
log
T/
2p
(47)
8dl11 + log T)
min 7>0
+ ndm
ETiT
Set 7 VdiTT
Then set V d² and p
37 and 7) = H1
VanT to get the first result.
Otherwise, set E = V mT and i/. and use the better of 1) v to get the second.
H. dm
+ VamT and 1)
dm
Corollary B.2. Let B and 1 and assume m.T > da.
Then w.hpp we can ensure
lusk-averaged regret at mosl
d ddmm
d/m
min 2 Agd 1 + SE
(48)
T
VT
using k (VVT
21

---

Proof. Applying Theorem 1.1, simplifying, and dividing by T yields task-averaged regret at most
+
dlog
5
8d 8dym
log 5k
1 + log(T +1)
+ +ddmm +
cm
log
+
7
8
P
T
16pT
8d (1 + log
Hg
nd m
log
min 8e(0.8,,200
+
+
+ mpm log d + pdym
ein/T
11
B
4k
"
(49)
d7
B
Set 7 Vdm' 8
and use 1j
to get the result.
(m:T) g.
mad
(dmIT)
Corollary B.3. Let B logd and B and assume m. 2 d. Then w.h.p. we ensure
lusk-averaged regret at most
(dimd + dym
min 2V A33 + SE(U,1]
(50)
VT
using 1s = [avT]]
Proof. Applying Theorem B.1, dividing by T, and simplifying yields
2
d d
5
8d./m
log 5k
+ log(T ( +1)
(e + yd)m
log 8
5
YT
P
T
16pT
(51)
+ min 3e
&d2 + log T)
Mg
nd
m
log d
+ r log d + pdy/m
S21TT
11
2k
11
Note that Hg and B are both decreasing on 3 <
logd so B in the chosen interval optimal over all
(0, 1]. Set
87 and V
get the result. O
VdmT+
mdd
7dmT
C Guaranteed exploration
C.1 Best-arm identification
Lemma C.1. Suppose for > O we rum OMD on task [T] with initialization X1,1 E A regularizer 1b +I for some 3, (0, 1), and unbiased loss estimators (7 0). If Assumpttio 3.1
holds and m > 28glog 3=
then &; = 21 w.p. 2 1 - dR, where k. = exp
28d
Proof. We extend the proof by Abbasi- Yadkori et al. [1, Appendices and F] to arbitrary lower bounds s/d on the probability. First, since < (a) < (e,)(a) we have that
< -15 - -a,(aa) & (c)( (a,(()) < d -1-1) l (1,(a))
(52)
and so (a) (a)( < d. Therefore since the variance of the estimated losses is scaled Bernoulli we have that
(esla) 2
(a(a)
Var(fe.(a) (a))))())))))))))))))))))()))))) Var(fe,(a)) (()(()(1 xx)(a))
S (53)
{a) (a)
22

---

We can thus apply a martingale concentration inequality of Fan et al. [23, Corollary 2.1] to the martingale difference sequence (MDS) ((), - (a)(a)) [- to obtain
mAa 2
EmAe
Pr Σ (a) l2)(0= 2
Pr
4 (a) (2,(aa)
2d
m
sm A
< Pr
max Je(m) d i=j
(a)(a) (a)(aa) z
2d
2 2(
(mmA.
S exp
2t
min (m(1 + e/d)2 (0mmm////m//mmmmmmm / 5mA
(54)
2 5mA_
S exp
2d
4(em/ emAn
3
exp
4d(6 + AAa)
3em
S exp
28d
where A. 1 E (,,(() mina' 2o Ei (,,((a)) is the per-arm loss gap in the last step we
m
apply Ao I 1. For the symmetric MDS - S ((,(a) - (a) I 1 we have
mA,
m4,
Pr
lo) - (,,(a) s
Pr Σ l (a) - (a) 2
2
2 mAn )²
exp
4 dm + mae)
(55)
Aem
S exp
4(6 + eDa/d)
3em
S eexp
28d
We can then conclude that
Pr (Xe+ 7 &x)
m
m
S Pr
3a + det Σ
(as - Σ ((a(as)
1=1
m
m
(àr) + mdar
m
m
mAa
< Pr
(0))
2
V a a de
(,)(a) S
(a,(a)
2
2
1=1
1=1
1=1
< Pr
(a.)
2 Σ (a,(
m
+
mDás
Σ atd
Pr
m
E (a) $
Σ lei(a)
m
mA.
2
2
i=1
1=1
1=1
1=1
A
3emm?
< exp
de
Σ exp
28d
28d
apti0
3EmA²
< dexp
28d
(56)
where the second-to-lass line follows by substituting the bounds (54) and (55) into the left and right terms, respectively.
Lemma C.2. Suppose on each task 1. E [T] we run OMD as in Lemma C. J. Then for any 8 E (0,
we have $ E D (x)() - ( (c) 5 (x)(()
3dx
(5) 1-8 - -1).
1-3
23

---

Proof. We consider the expected divergence of the best initialization under the worst-case distribution of best amm estimation, which satisfies Lemma C.I and (56). We have by Claim A.I and the mean-as-minimizzr property of Bregman divergences that
r
T
(xx - 2 = E min XEA(e)
BB
&
(xx)
T
T
t=1
T Σ
min XEA(t)
E
B3
(x/
T
i=1
T
min xEA(e)
Paa
it) B3
c (ox
T d
max PIEA.VIE 'T) D1 (-dnspp(a)))e((()..==
min xE
ΣΣ PB
(el*
T
1=1a=
(57)
To simplify the last expression, we define p = + Et Pt and again apply the (weighted) mean-as- minimizer property, followed by Claim A.1:
T d
min (EA()
1
Σ B3
min xE
D(a)BB (1x)
Σ BB (p(()))
T
tm1 mlml
a=1
= ( (5) w
(58)
By substituting into the previous inequality, can bound the expected divergence for the worst-case Pe as follows:
(x(( ) - v10(2(6))
S v/s
e
+
max PIE '7) (2) Lapte (=)
(D(e))
< 1/ e1
+
max
(D))
EE E. Pa
(59)
Ee (1)
El -
= t/ (c
min
(p(())
DEA
p(a) -1)2((dd))((),))))
(1 (1
We the shorthand h(x) 1/3 ((1 )x L
We have
Σ x(6) )
-Ox(a) (x)(()) = Ox((a)
(1 - B)
x(b)) 1))
= =xx(a)
Σ x(1) + -8
Σx(b)
(60)
(1 B}
b=1
b=1
B
(x(a))-1 -2t
1 3
and therefore
V
dxia)ths (1 (1- =)=-))x= + E
_11))
max 0= l......d
8
<
1 B
max I....d
((1 - -E)x(a) + = d
(61)
9
d
1-3
-1) = B Blog d
<
1-6
3
5
24

---

Finally, by convexity of h we have
min PEA
h(p) h(x) [VV
max
p
X
PEA
dl (10)
(1-))
(1
(62)
2 h(()) 3dw (h( oc
h(8) 3dx Log,
so we can substitute into (59) to
( w ( (3)
3dxB
d
1-8
-1
(63)
1 B
2
Applying Lemma B.2 completes the proof.
C.2 Guaranteed exploration bounds
Lemma C.3. Suppose we play OMD3.n with initialization X1 E 16),, regularizer v + I (( for some E (0, 1), and unbiased loss estimators (7 = 0) on the sequence of loss functions f,,..., ey E [0, 1]9.
Then for any [d] we have expected regret
EBg (x1)
nd m
E
Σ
((a))-
- (()a)
+ em
(64)
3
E
for & the estimated optimum of the loss estimators l.....,e.. Pr.
Proof.
T
T le(as) -(l,,
E
24())
E
t=1
Ec(ac) (1c, + em
E
Le(ar) (f1, +em
(65)
E
Re(ar) (le, +
d
E
+ 7
((o)x--9(a) B (=1
2())x²
+ +em
7
|xx])
nd m
3 +mm
"
where the second inequality follows by optimality of & for the estimated losses é,, the third by Lemma B.3 constrained to (e),, and the fourth similarly to Theorem B.1 (note both are also effectively shown in Luo [37].
Theorem C.1. In Algorithm 1, let OMD,,9 be online mirror descent with the regularizer vh + Iawe
over unbiased (7 0) loss estimators, Oy is subset of [8, B] C b 11. and
Bg(8 (c)
xx)
md m
Ux(x, 7. 3)
(66)
B
25

---

where x =1 =) + ela/d. Note that U (x, n,,,,,8)..))) Uz(x, 17 pd(d--2111
a(1-B) Then under
Assumption 3.1 there exists settings of T Th Ot X s.1. for all e, E (0, 1) we have that
I m
( ((,e(
1=1
8d m
18 logk
1+ log(( +1)
5 em
16pT
8 (g) 2
+ log T)
hs(A)
nd m
L,
3)
+ min
+
+
+ d mmnn
PV
PVm
m
Be (8,7))0000
1/T
B
2k
221
(67)
for Ln
log + 1pm log d) d and ho(A) (Hg +
dm
56
US +
d'-0-1
1-B
(1 12) for is
1 mn 75d log a ex?
Proof. By Lemma C.3 we have
BBg (x (xx.1)
n.
E ΣΣΣ (a,(( 1=1
l,,())) (.,(aa))) - EmT +E Σ
(68)
Gt
3e
Since we have the same environment--eeeedeeer quantities in Theorem B.1, can substitute the above bound into Theorem A.1 and then apply the Lemma C.2 bound
3dk3
( 1-8
3d
2m
EVG S H3 + 1- B
-
HB
+
exp
8
28d
3eA²
3m
H3 +
cxp
4log
d²
EA
28d
(69)
3=A 2/2
< Hg + 3e
4 4log
d
28d
r4²
56
H1 +
dm
where the last line follows by assuming m 2 apply the default bound of EV3 <= Σー ()) (x)
75d log
=d2- this condition does not hold, then we
d
EAa
d' 1
Li
1-3
Corollary C.1. Let 3= 1. Then for known and assuming m expected task-averaged regret at most
A log we can ensure
2 Hidm + 56 +
75d
W
m
di
d
d
(70)
A
75
T
where W is the Lambert W -ffunction, while for unknown A we can ensure expected task-averaged regret at most
d'm²
dim
dd
m
2 Hidm 56 +
50dm 50g d log
+
+
(71)
150 log d
VT
T
so long as m² 2 150dlogd d.
Proof. Applying Theorem C.I and simplifying yields
Em 8dym(( log(T' 1))
8d(1 + log
hi(A)
dp²
min n>0
+ ndm
(72)
16p2T
n
2m
Then substitute 77
(1(A) dm
and set p Va
dI dT and
75d
W
(for known A)
A
77
150dlog 2
(otherwise).
26

---

Corollary C.2. Let 5 = 2 and = 1. Then for known A and assuming m 2
75d
A
log
A
d
we can
ensure task aiskaavergee regret regret at most
min 2 [Ham+ + 56/d)d9/8 + [c
75d A
W
m
+
d m
+
d m
dA 1
(73)
75
V
T
T
using k [ d2mTT, while for unknown A we ensure expected task-averaged regret most
dm²
d m
da x
d ddm²
min 2 (H [Elg.]]
(H + 56/d)d /3 +
50d log
Ö
A
150A6
VT
T
T
(74)
so long as m 2 5.
Proof. Applying Theorem C.I and simplifying yields
Em + 8dym
log
T + 1 + log(T + +1)
16pT
(75)
d (1 + log T)
ha(A)
nd m
log
dp²
min 3
+
+ 1pm log
n
8
4k:
2n
Then substitute 7
ha(A) /m/BB and set
V
d
and
Am
75d
W
To
(for known A) or
E
150d m
(otherwise).
Corollary C.3. Let 3 a and B = 1. Then for known A and assuming m 2
75d A
log d
we can
ensure aaek-aver regret at most
75d
d m
d dimå
d
min 2 (H (Ham+ 56/d)dd/// $E(0.1]
W
+
(76)
75
VT
T
T
using 1 = (Td2mT while for unknown A we can ensure expected aask-avergged regret at most
3
dm?
d
d m 5
d m
min BE(O.1]
13
50d2m log
Ö
A
150A6
VT
T
T
so long as 5dv6.
Proof. Applying Theorem C.I and simplifying yields
8d/m
(Vogk + + Log(o 1)
Em +
P
16pT
(78)
Sal2 (1 log
ho(A)
md
d
[oog d
dp2
min m
+ mym log d
12T
"
3 2k
"
21j
ha(A) Tm/B and set V/
Then substitute 7
and
m
(for known A) or
d
Am
150d2
(otherwise).
Corollary C.4. Let 3 log and B 1. Then for unknown and assuming m 2 max(d (d2,56)
1
we can ensure task-averaged regret at most
min min (sdmm 2 (Ham+ RE(0.1]
56 d
d3
+
21d
V
m
13
log
dm
+0
d m
d m
mm3
B
T/T
T
T
(79)
using k [ Vddmm.
27

---

Proof. Applying Theorem C.1 and simplifying yields
8dym m
log k
+ log(T +
em +
+
P
T
16pT
(80)
Sd? (1 + log T)
+ ha(A)
nd m
log E + mmm log d )
dp² 21
min (E(
e2'1T
"
B
2k
"
Then substitute rj
ba(A) Pm/B and set p Va dvmm
and
dd
V Vm
D Robustness to outliers
Proposition D.1. Suppose there exists a constant E [0, 1] and a subset S C [T) of size s such that à S for all but ((P)) MAB tasks t. [T). Then if B E loo 2] have H3 O 7P0 p)
d--
Proof. Define the vector eş E [0, 1] s.t. esjal = Loes. Then by Claim A.1 and the mean-as- minimizer property of Bregman divergences we have
Hg (x)
T
1
Σ
5 (3x) - (5x
=
T
+ Σ
()(11118)
min
Σ
(x
A. T
t=1
T Σ
8
8
min 8E(0,1)
B3
&
es
ld
8
d
[=1
T
1
d
8
8
3(2,(a) 1-6
lass ") (81)
min 6E(0.1)
T
3
LEs
+
d
[[aa|
+
(-ا 1 $33
[=1
6=1
1
T
1
8 8)8
8
[[[]]
8
8 [
min 6E(0.1)
T
LaES
+
d
(1 B)
laeS + 9)1
[=l a=
min 5E(0.1)
8188
88 d
8
La=
(1 -1-3TT
B3( 1-4
laes + 1
sI-B
3(2) ((1)1-8
min AE(0.1)
88. +0
3
(1 B)T
-
0
T- p)
where the last line follows by considering 5 = 1/T1-p.
28

---

E
Online learning with self-concordant barrier regularizers
E.1 General results
Lemma E.1. Let K C. I& be a convex set and Φ K H R4 be self-concordant barrier. Suppose e bT are sequence of loss functions satisfying [(t, S LIVx K. Then we run OMD with step-size ni > as in Abernethy et al. (2, Alg. 1] on the sequence of estimators l our estimated regret w.r.t. any Ke for >> 0 will satisfy
(6,x x) B(x "
Σ
+ 1TT
(82)
Proof. The result follows from Abernethy et al. [2] by stopping the derivation on the second inequality below Equation 10.
Definition E.1. For any convex set K and any point y E K. Ty(x)
inf t is the
120. T
Minkowski function with pole y.
C IR and vp KC' R a u-self-concorrlln regularizer with minimum X1 K the quantity (i (x)) is vv 2-2pschtt w.r.t [0, 1].
Lemma E.2. For any
Proof. Consider any E, E [0, 1] s.t. 5' -EE (0, } Note that for E''E have
1+E
cx((x) + cer(x) - cx(x) = xi + x- X1 1+e
X
(83)
so To (ce <
d'=e <e' -E. Therefore by Nesterov and Nemirovskii [42, Prop. 2.3.2] we
ltc
have
- vlog (x) (cr
S v log
1+s- S <u(E'-E)V (84)
where for the last inequality we used - log(1 - 2) S xv for x E [0, 2 The case of e' - E (0.1)
follows by considering g" e'ts and applying the above twice.
29

---

Theorem E.1. In Algorithm 1, let OMDn, be online mirror descent over loss estimators specified in Abemethy et al. [2] with p--self-coccordee barrier regularizer vp : K that satisfies z 1 and 1/ 2 = S1 2 1. Let O₂ be subset of [m and
U,,,,17,5 (()x( + 32nd +m
(85)
7
Note that U1(0 (x, n,.) = U, 1)8) 9u 3 Km
Then there exists settings of 1) 7) a, X s.l. for
all p, (0, 1) we have expected task averaged regret most
512x K S1m² 2 (1 + T)
V22
+ 32nd m Em + VV2/n m
E min 11,0000
T
3p'vi & K /1
3v 3 mimiin
Adpy 2K / (TVTlogk
T
(86)
"
7dm p
1+ log(T + 1)
V
2K v.S
Proof. Letg g = m Nemirovskii [42, Prop. 2.3.2] we have
1 For any & E ls, 1] and x E K. we have xx, (ce())) 1
1 140 so by Nesterov and
+ 3v
64v2S
[V 1x
(87)
xx. (ce (ce(x))
52
Thus S = maxx maxxxyck.ee(s.]) /| [/2
64v2s, 8²
and also
D max xyEE ((c((x))lcxx)))
- V/cck))))-ccc(//)V-Vvvv((((>>>>
max xyek
1
I max v Voo xyek
1 Tx, (cx + VoI - y1l2
(88)
2
KVSI
S v log
9v Kv
where the first inequality follows by Nesterov and Nemirovskii [42, Prop. 2.3.2] and the definition of a self-concordant barrier [2, Def. 5]. addition, we have g(E) = 32d², f(e) = E, M = 12d 22d/2KKm V and F = We have
T
Σ Cl,, X1,i
x,)
E
c Σ (le,,x,,1 - Ce. (Xi))
T
1F
e.m +
Σ (l,,1) X1,1 cr, (x.))
(89)
T
<
E
E. +
Σ
(le,) X -c,, (8e))
1=1
EB
(&c (x.1)
(32m/d + =
1/p
where the first inequality follows by Abernethy et al. [2, Lem. 8), the second by Abernethy et al. [2, Lem. 3), the third by optimality of x,, and the fourth by Lemma E. Substituting into Theorem A.1 and simplifying yields the result.
30

---

E.2
Specialization to the unit sphere
Corollary E.1. Let K. be the unit sphere with the self-concordant barrier 16(x) log(1
xxx12).
Then Algoritim I attains expected task- aask-avergged regret bounded by
dm
dm
1 1
E|
+ min
4d
2m log
+ +m
(90)
T
VT)
sE
25 +
using k
VT
Proof.
Using the fact the = and K = Si = 2, we apply Theorem E.I and simplify to obtain
V2 + 32ndd m + sm + +0
m
+ min { [ (1) (g.0))=
+ dm
dm
E min -
PVT +
1/7
nk
p2T
(91)
Then substitute
V.
Vm JVT
set
and note that
2w2dm
V
1 - (x)]1
1 (1
EV. E
log
E B log
1 - (1++)
(1c)(8))1
(92)
1 1
log 1+
28 +
where we use the fact that | || and the inequality is Jensen's.
F.3 Specialization polytopes, specifically the bandit online shortest-path problem
fx E [0, 1 (a.x) I ba (a, b) E C} be the set of flows from to on graph G(V, E), where C C RIEl x R is a set of O(EE) linear constraints. Suppose we see T instances of the bandit online shortest path problem with m timesteps each. Then sampling from probability distributions over paths from to returned by rumning Algorithu I with regularizer (x) = --Znbee log(b- (a, x)) attains the following expected average regret across instances
Corollary E.2.
a |
m
E 2 m
E b (a, (e(i)
+ min 1|
Σ log a.bEC
+ Em
T
VT
=E
VIT b (a, cx(1))
(93)
[TT]
using l-
Proof. Using the fact that dl = |E) O(E)), K VIE. and S₁ S Eabec
laa ED 6)a
((E)),, we apply Theorem E.1 and simplify obtain
1/
E
min <c|
32m E/2 + em
(94)
EE [E|%m² m2 T)
E
m
+
m min
p² E
E
E m
1
+ 1
1)h
k
17
VT
Then substitute
V.
2
m VT
set p
T m., and note that
4v24m
(a, Ce (2))
T E b (a, C. (Xi))
1
2
Σ log
Σ log a.EEC
(95)
a.bEC
V T
b (a, ca (Xxe)
IT b c,
31


Reviews:
[{"review_id": "IYC8pQiWsP", "reviewer": "Reviewer_eUxe", "summary": "This paper introduces a meta-learning algorithmic framework for adversarial bandits, designed to fine-tune the initialization and hyperparameters of the internal learner, thereby enhancing performance across multiple tasks. The efficacy of this approach is validated via a theoretical analysis on multi-armed bandits and linear bandits. The authors also propose a task-similarity measure with significant implications concerning entropy and proximity to the task boundary.", "questions": "- Could the authors elaborate on the connections to meta-learning in adversarial Reinforcement Learning (RL)? While meta-learning for adversarial bandits appears to be a novel concept, meta-learning in adversarial RL, a generalization of bandits, has been explored in the literature, as evidenced by [1] for example.\n- Could the authors provide insights on how the algorithm's implementation could be optimized for efficiency?\n- Could the authors demonstrate the effectiveness of the model and the algorithm in a well-motivated real-world setting through numerical experiments?\n- Could the authors offer a more intuitive explanation of the task-similarity measure and how it compares to existing methods, beyond comments about being 'distributional assumption-free'?\n\n[1] Lin, Zichuan, Garrett Thomas, Guangwen Yang, and Tengyu Ma. \"Model-based adversarial meta-reinforcement learning.\" Advances in Neural Information Processing Systems 33 (2020): 10161-10173.", "limitations": "The authors have acknowledged the limitations of their work, including the absence of a gap-free task similarity criterion, the assumption of known task boundaries, and the lack of a 'best-of-both-worlds' guarantee.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper addresses meta-learning under adversarial bandit feedback, which is an interesting problem by itself, and the meta-learning approach poses a solid contribution to the bandit community, with a new notion of task-similarity based on entropy.\n- The concrete steps towards building the algorithms is clear and statements in the paper seems solid.\n", "weaknesses": "- The paper does not have any numerical validations of the proposed algorithm. This puts doubts on the practicality of the proposed framework and methods. Synthetic as well as real-world examples should be tested upon, and comparisons against meta learning stochastic bandits should be discussed in the numerical experiments as well.\n- The computational complexity is not adequately addressed within the main body of the paper. Specifically, the computational overhead associated with the Multiplicative Weights (MW) method could be prohibitively high with a large grid and action space.\n- The interpretation of task-similarity lacks a sufficient explanation of its underlying motivation. Even in application cases where the authors justify the task-similarity measure via average entropy or proximity to the decision boundary, it remains unclear why this measure was chosen and how it compares to other task-similarity measures in stochastic bandit scenarios (and/or those with contamination or parameter noise). As it stands, the presentation in the paper makes it seem more like an artifact of the regret proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review; we address your questions and concerns below.\n\nWeaknesses:\n1. [*The paper does not have any numerical validations of the proposed algorithm. [...]*] \n- Our goal in this work was theoretical depth and breadth, with the application of our framework to four different bandit algorithms (Sections 3.1, 3.2, 4, and D.3) across three different geometries (simplex, sphere, and polytope). This puts experimental contributions out of scope for us due to constraints on space and the need for conciseness. As noted by Reviewer qSEU, they are “not mandatory and the paper's contribution is still valuable without them.”\n\n2. [*The computational complexity is not adequately addressed within the main body of the paper. Specifically, the computational overhead associated with the Multiplicative Weights (MW) method could be prohibitively high with a large grid and action space.*] \n- While it is in the appendix due to space constraints, our thorough examination of both computational and space complexity in Section A.3 does discuss the overhead of MW; per-iteration its cost is sublinear in T and d, which we do not view as prohibitively high.\n\n3. [*The interpretation of task-similarity lacks a sufficient explanation of its underlying motivation. [... I]t remains unclear why this measure was chosen and how it compares to other task-similarity measures in stochastic bandit scenarios [...] As it stands, the presentation in the paper makes it seem more like an artifact of the regret proof.*]\n- We view task-similarity measures that arise from distance measures or entropies associated directly with the algorithms being run on those tasks to be inherently natural, rather than simply proof artifacts. For MAB we provide an interpretation of the task-similarity measure below Corollary 3.1 and *directly* compare it to the one that Azizi et al. [10] used for the stochastic bandit setting at the end of Section 3.1. The fact that our results yield meaningful guarantees under their “small set of optimal arms” assumption, which we also highlight in the introduction, is strong evidence of the usefulness of our approach to measuring task similarity. For BLO we provide an interpretation of the task-similarity measure below Corollary 4.1.\n\nQuestions:\n1. [*Could the authors elaborate on the connections to meta-learning in adversarial Reinforcement Learning (RL)? While meta-learning for adversarial bandits appears to be a novel concept, meta-learning in adversarial RL, a generalization of bandits, has been explored in the literature, as evidenced by [1] for example.*]\n- In RL the losses are stochastic and depend on a state in an MDP, whereas in adversarial bandits the losses are chosen adversarially; thus RL does not generalize adversarial bandits. In the referenced work [1], it is the “meta” aspect that is adversarial, not the RL. Specifically, they study a batch setting across tasks and propose that the learner should choose the tasks using adversarial training in order to do well in the case of distribution shift, *but there is no actual adversary*; our work studies an online setting across tasks where an adversary chooses the tasks.\n\n2. [*Could the authors provide insights on how the algorithm's implementation could be optimized for efficiency?*]\n- This is discussed in Section A.3; in-particular, we suggest that replacing our use of EWOO by MW may increase efficiency at the cost of worse regret. Please also see our response to your second weakness above.\n\n3. [*Could the authors demonstrate the effectiveness of the model and the algorithm in a well-motivated real-world setting through numerical experiments?*] \n- Please see our response to your first weakness above.\n\n4. [*Could the authors offer a more intuitive explanation of the task-similarity measure and how it compares to existing methods, beyond comments about being 'distributional assumption-free'?*]\n- Please see our response to your third weakness above. Note also that “distributional assumption-free” is an aspect of our guarantees, rather than of our task-similarity measure."}, {"review_id": "YrqZH6wFax", "reviewer": "Reviewer_yLU7", "summary": "The paper discusses online meta-learning with bandit feedback to enhance performance across multiple tasks that share a natural similarity measure. The study focuses on the adversarial online-within-online partial-information setting and proposes meta-algorithms that combine outer learners to optimize the initialization and other hyperparameters of an inner learner for two cases: multi-armed bandits (MAB) and bandit linear optimization (BLO). For MAB, the meta-learners use the Tsallis-entropy generalization of Exp3, and the task-averaged regret improves when the entropy of the optima-in-hindsight is small. For BLO, the approach involves learning to initialize and tune online mirror descent (OMD) with self-concordant barrier regularizers, where the task-averaged regret is related to an action space-dependent measure induced by these regularizers. The guarantees provided in the study are based on demonstrating that unregularized follow-the-leader combined with two levels of low-dimensional hyperparameter tuning can effectively learn a sequence of affine functions of non-Lipschitz and sometimes non-convex Bregman divergences, which bound the regret of OMD.", "questions": "(1) For the MAB algorithms, there may be only one served task in each round, i.e., observe the loss. In this case, how to run algorithm 1 and do we need to update the parameters of all tasks?", "limitations": ".", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper designs a meta-algorithm combining FTL, EWOO, MW to set the initialization, step-size, and the regularizer. Then, it has to direct applications for MAB and BLO. Then, the authors provide rigorous average regret analysis with Tsallis entropy, which are the first results for online learning with Bregman divergences.", "weaknesses": "It will be better if authors can provide some real-world applications that the designed algorithm can adapt to.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review; we hope to address your questions and concerns below.\n\n1. [*It will be better if authors can provide some real-world applications that the designed algorithm can adapt to.*]\n-  As noted in the introduction, single-task bandits are widely used in applications such as recommender systems and experimental design; multi-task versions of these applications arise naturally. For example, a recommendation engine may face a sequence of different users with multiple interactions each, or a scientist may run a sequence of similar multi-round experiments. \n\n2. [*For the MAB algorithms, there may be only one served task in each round, i.e., observe the loss. In this case, how to run algorithm 1 and do we need to update the parameters of all tasks?*]\n- If we are interpreting your question correctly, it concerns the somewhat different setting of *multi-task* online learning (Dekel, Long, & Singer, COLT 2006), where on each round we see a loss associated with one of T tasks, rather than *meta* online learning, where we see T tasks one-after-another. The multi-task setting has generally required rather different algorithms."}, {"review_id": "uOGPtyVjTS", "reviewer": "Reviewer_qSEU", "summary": "The paper proposes an online mirror descent approach for adversarial bandit feedback-based online meta learning, utilizing FTL for initialization, EWOO for step-size, and MW for regularizer-specific parameters. The proposed method is applied to two widely adopted applications: multi-armed bandits (MAB) with Tsallis regularizer and bandit linear optimization (BLO) with self-concordant barrier function regularizer. The authors provide theoretical analysis on asymptotic task-averaged regret for MAB and BLO.\n\n", "questions": "The reviewer is not very familiar with this topic and would like to see the comments and feedback from other reviewers before asking further questions.", "limitations": "It would be nice to provide empirical results ( it is not mandatory and the paper's contribution is still valuable without them).\n\n\n\n\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and seems to cover an important topic in the community. I check some proofs, and they seems correct.\n", "weaknesses": "While the paper is theoretical in nature, it would be beneficial to include some empirical results to further validate the proposed approach.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review; we are happy to answer additional questions later. With respect to your concern about experiments: our goal was theoretical depth and breadth, with the application of our framework to four different bandit algorithms (Sections 3.1, 3.2, 4, and D.3) across three different geometries (simplex, sphere, and polytope). Thus we view experimental contributions as out of scope for us due to constraints on space and the need for conciseness."}, {"review_id": "5l0fqzTtjR", "reviewer": "Reviewer_zCMR", "summary": "In this paper, the authors consider an online meta-learning problem with the adversarial online-with-online partial information setting,\nwhere a learner selects parameters across T tasks with m rounds and can utilize similarity between tasks to achieve a low regret.\nFirst, the authors propose a meta algorithm which optimizes hyperparameters of the inner loop algorithm (OMD).\nAs an instance of this algorithm, the authors consider OMD for MAB and BLO (bandit linear optimization).\nThen, they prove several upper bounds of the average regret across $T$ tasks using a similarity of optimal parameters across tasks.", "questions": "1. In the related work section, the authors compare their algorithm to algorithm for dynamic regret optimization, but they discuss only the number of switches. There are algorithms whose regret bounds involve total variance of the environment (e.g. $\\Delta$ in Wei, Chen-Yu, and Haipeng Luo. \"Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.\" Conference on learning theory, 2021.). Are these algorithms related to the problem setting in Sec 3.2? Is it possible to provide a comparison?\n2. In the stochastic setting, is there a known lower bound?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. While existing papers considered online-with-online meta-learning in stochastic or full-information setting, this paper considers the adversarial bandit feedback setting, which is practically important.\n2. Although the proposed algorithm is based on one in the full information setting, there is novelty due to the bandit feed back (e.g., estimation of true $H_\\beta$).\n3. The authors provide regret upper bounds under several settings and results seems valid. ", "weaknesses": "1. There is no discussion on lower bounds. Therefore, it is not clear whether the proposed method is optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review; we hope to address your questions and concerns below.\n\nWeaknesses:\n1. [*There is no discussion on lower bounds. Therefore, it is not clear whether the proposed method is optimal.*]\n- While we agree that lower bounds can be informative, our goal in this paper was to demonstrate the potential benefits of meta-learning across a broad number of settings, including four different bandit algorithms (Sections 3.1, 3.2, 4, and D.3) and three different geometries (simplex, sphere, and polytope). See also our response to your question on stochastic lower bounds below.\n\n\n\nQuestions:\n1. [*In the related work section, the authors compare their algorithm to algorithm for dynamic regret optimization, but they discuss only the number of switches. There are algorithms whose regret bounds involve total variance of the environment (e.g. $\\Delta$ in [Wei & Luo (COLT 2021)].). Are these algorithms related to the problem setting in Sec 3.2? Is it possible to provide a comparison?*]\n- Thank you for the reference, which we will add to our related work. Note that Wei & Luo (2021) study several different stochastic settings (from MAB to MDP), whereas we focus on the adversarial setting; thus it is not obvious how to generalize their $\\Delta$ to our setting, as it quantifies changes in the loss distributions over time.  From looking at the dynamic regret bound they highlight in the abstract—$\\tilde{\\mathcal O}(\\min\\{\\sqrt{LT},\\Delta^\\frac13T^\\frac23\\})$, where $L$ is equal to the number of changes in distribution ($T$ in our setting), $T$ corresponds to the number of rounds ($mT$ in our setting), and $\\Delta$ is a type of distributional path length—it seems that their algorithms will have task-averaged regret $\\tilde{\\mathcal O}(\\min\\{\\sqrt m,\\Delta^\\frac13m^\\frac23/T^\\frac13\\})$. This will do well if the average change in distributions across tasks is sublinear in $T$ (i.e. $(\\Delta/T)^\\frac13=o_T(1)$); on the other hand, if the environment switches between a small set of different tasks (the sparse setting where our MAB algorithm does well) then $(\\Delta/T)^\\frac13=\\Theta(1)$ and their approach will not improve upon the baseline of $\\tilde{\\mathcal O}(\\sqrt m)$. Even in this case, of course, their algorithm has the advantage of not needing to know the location of the task switches.\n\n2 [*In the stochastic setting, is there a known lower bound?*]\n- There are known lower bounds for some specific multi-task stochastic bandit settings [1,2,4,5], but to our knowledge the only one in the sequential setting across tasks is in the full information adversarial setting [3]. \n\n[1] Azizi, Kveton, Ghavamzadeh, Katariya. *Meta-learning for simple regret minimization.* AAAI 2023.  \n[2] Cella, Pontil. *Multi-task and meta-learning with sparse linear bandits.* UAI 2021.  \n[3] Khodak, Balcan, Talwalkar. *Provable guarantees for gradient-based meta-learning.* ICML 2019.  \n[4] Simchowitz, Tosh, Krishnamurthy, Hsu, Lykouris, Dudik, Schapire. *Bayesian decision-making under misspecified priors with applications to meta-learning.* NeurIPS 2021.  \n[5] Yang, Hu, Lee, Du. *Impact of representation learning in linear bandits.* ICLR 2021."}, {"review_id": "9kU6nnTLyg", "reviewer": "Reviewer_WoUK", "summary": "This paper focused on online meta-learning with bandit feedback, and developed and applied a meta-algorithm for learning to initialize and tune bandit algorithms, obtaining task-average regret guarantees for both MAB and linear bandits.  Specifically, a meta-algorithm was developed for learning the variants of OMD, which was further applied to OMD with the Tsallis regularizer. Furthermore, the meta-algorithm was adapted to the adversarial BLO problem via setting the regularizer to be a self-concordant barrier function.  ", "questions": "- This paper mainly focused on the pure adversarial settings.  As the authors mentioned, there are extensive works studied the stochastic settings, and given the popularity of \"best-of-both-worlds\" settings in the community, can you envision what is the major challenges to generalize the solutions to the best-of-both-worlds settings, from both the algorithmic and performance analysis perspectives? ", "limitations": "n/a societal impact. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is the first to consider meta-learning under adversarial bandit feedback. \n- A meta-algorithm was designed for learning the variants of OMD, which can simultaneously tune the initialization and other hyperparameters.\n- Strong theoretical performance guarantees were presented for the proposed algorithm.  \n- The paper is well-written and easy to follow though it is heavy in theory. ", "weaknesses": "- This paper mainly focused on the pure adversarial settings.  As the authors mentioned, there are extensive works studied the stochastic settings, and given the popularity of \"best-of-both-worlds\" settings in the community, can you envision what is the major challenges to generalize the solutions to the best-of-both-worlds settings, from both the algorithmic and performance analysis perspectives? \n- As the paper considered the applications of the proposed algorithms, it may be interesting to do some case studies with real-world applications, rather than only on theoretical applications.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review; we hope to address your questions and concerns below.\n\n1. [*[C]an you envision what is the major challenges to generalize the solutions to the best-of-both-worlds settings, from both the algorithmic and performance analysis perspectives?*]\n- One challenge is that the online-within-online setting has two parts, each of which can be either stochastic or adversarial, giving rise to four settings that need to be supported. In order to prove that the solution is “best” for each of these settings, four lower bounds will need to be proved first. Additionally, dependence on the true optima-in-hindsight (Section 3.2) will require a best-arm identification procedure that is best-of-both-worlds and simultaneously works alongside the regret-minimization algorithm. \n\n\n2. [*As the paper considered the applications of the proposed algorithms, it may be interesting to do some case studies with real-world applications, rather than only on theoretical applications.*]\n- We agree that it will be interesting to develop novel real-world algorithms that are inspired by this theoretical framework. However, our goal in this work was theoretical depth and breadth, with the application of our framework to four different bandit algorithms (Sections 3.1, 3.2, 4, and D.3) across three different geometries (simplex, sphere, and polytope). Thus we view real-world applications as out of scope for us due to constraints on space and the need for conciseness, and leave it for future work."}, {"review_id": "qErJZwncD3", "reviewer": "Reviewer_fExn", "summary": "This paper considers learning several adversarial tasks with different loss functions simultaneously, hoping to attain better task-averaged regret if the tasks are \"similar\" enough (e.g., the optimal actions of all tasks concentrate on a small subset). A general meta-learning framework is derived by deploying three different algorithms as meta-learners to optimize the hyper-parameters of the base learners (OMD). It then applies to MABs and BLOs, providing various high-probability or expected regret bounds.", "questions": "See Weakness 1 & 2.", "limitations": "Clearly stated", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is well-motivated. According to the authors, while the stochastic variant of this meta-learning problem is well-studied, the adversarial version tackled by this paper has never been solved.\n2. The algorithmic idea is well-illustrated and thus the framework is easy to understand.\n3. The framework is applied to various base-learners to prove its effectiveness, including MABs with implicit exploration or guaranteed exploration and BLOs with self-concordant barriers.", "weaknesses": "1. The design of the meta-learner does not look pretty exciting. Given the expression of $U_t$ in Eq. (3), it appears unsurprising that the adopted optimizers (FTL, EWOO, and MW) can be applied to their respective objectives.  \nIn other words, it seems that the technical contribution of this paper is not solid enough -- the analyses of meta-learners and base-learners are both not novel. However, I do feel the overall result is interesting.\n2. I am unsure whether the task similarity measure can generalize over the \"support\" of the optimizers.  \nConsider a special case where most of the tasks share the same optimizer but there are a few (say $\\sqrt T$) outliers, would the bound scale with $\\sqrt[4]{T}$ or $\\mathcal O(1)$? In this case, if a meta-learner successfully rules out those outliers, the bound should scale by $\\mathcal O(1)$; but using the sparsity $s$ would only give $\\sqrt[4]{T}$.  \nIntuitively, as $H_\\beta$ is taken to the average of all $\\hat x$'s, such a distribution will be very different from a uniform distribution (i.e., there are $\\sqrt T$ optimizers each associated with $\\sqrt T$ tasks); though I'm not sure whether the current framework can capture this.\n3. (minor) The bounds in the main text contain so many terms that it is hard to interpolate. Informal expressions (like Eq. (13) or Eq. (19)) can be shortened using $o_T(1)$ to highlight the main terms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review; we hope to address your questions below.\n\n1. [*[...] Given the expression of $U_t$ in Eq. (3), it appears unsurprising that the adopted optimizers (FTL, EWOO, and MW) can be applied to their respective objectives. [...] the analyses of meta-learners and base-learners are both not novel. However, I do feel the overall result is interesting.*] \n- While the meta-learning component of our analysis indeed builds upon existing work in the full information setting, we view the applicability of FTL and EWOO as “unsurprising” only in light of this previous work (as $U_t$ can be non-convex in $\\mathbf{x}$ and non-Lipschitz in $\\eta$). Furthermore, the applicability of MW does not follow from past work since it is not obvious that the first term on the RHS of (3) is Lipschitz in $\\theta$; in fact, proving it requires setting-specific analysis (c.f. Lemmas B.1 & D.2). Finally, it does require substantial technical effort (c.f. Section C) in order to prove that these meta-algorithms can adapt to the similarity of true (rather than empirical) task optima, which past work does not consider because it has full information.\n\n2. [*I am unsure whether the task similarity measure can generalize over the \"support\" of the optimizers. Consider a special case where most of the tasks share the same optimizer but there are a few (say $\\sqrt T$) outliers, would the bound scale with $\\sqrt[4]T$ or $\\mathcal O(1)$? In this case, if a meta-learner successfully rules out those outliers, the bound should scale by $\\mathcal O(1)$; but using the sparsity $s$ would only give $\\sqrt[4]T$.*]\n- Thank you for the interesting question. While you are correct that just substituting $1+\\sqrt[4]T$ for $s$ yields an undesirable bound, we *can* use our framework to obtain a result that is better than the single-task baseline of $\\mathcal O(\\sqrt{dm})$. In particular, in the setting you describe $H_\\beta$ can be bounded by $\\tilde{\\mathcal O}(1+d^{1-\\beta}T^{-\\beta/2})$ (c.f. the bottom of this response), so for sufficiently large $T$ the bound will be $\\tilde{\\mathcal O}(\\sqrt m)+o_T(poly(m,d))$, as desired. The caveat here is that the rate in $T$ will be quite slow. We think this is a useful analysis of our result, highlighting the advantage of not simply assuming a small set of optimal arms, and will include it (or a more general version of it, e.g. for $T^p$ outliers, $p\\in[0,1]$) in revision.\n\n3. [*[...] Informal expressions (like Eq. (13) or Eq. (19)) can be shortened using $o_T(1)$ to highlight the main terms.*]\n- In general we agree, although note that keeping the rates in $T$ can be useful for comparison with other works, e.g. Azizi et al. [10].  \n\n### Bound on $H_\\beta$ in the presence of $\\sqrt T$ outliers\n\nSuppose all but $\\sqrt T$ tasks have optimal action $a^\\ast\\in[d]$.\nThen applying Claim A.1 and the mean-as-minimizer property of Bregman divergences we have that\n$$\\begin{align}\nH_\\beta(\\hat{\\bar x})\n&=-\\psi_\\beta(\\hat{\\bar x}) \\\\\\\\\n&=\\frac1T\\sum_{t=1}^T\\psi_\\beta(\\hat x_t)-\\psi_\\beta(\\hat{\\bar x}) \\\\\\\\\n&=\\frac1T\\sum_{t=1}^TB_\\beta(\\hat x_t||\\hat{\\bar x}) \\\\\\\\\n&=\\min_{x\\in\\triangle_d}\\frac1T\\sum_{t=1}^TB_\\beta(\\hat x_t||x) \\\\\\\\\n&\\le\\min_{\\delta\\in(0,1)}\\frac1T\\sum_{t=1}^TB_\\beta(\\hat x_t||(1-\\delta)e_{a^\\ast}+\\delta 1_d/d) \\\\\\\\\n&=\\min_{\\delta\\in(0,1)}\\frac1T\\sum_{t=1}^T\\frac1{1-\\beta}\\sum_{a=1}^d((1-\\delta)1_{a=a^\\ast}+\\delta/d)^\\beta-\\hat x_{t[a]}^\\beta+\\frac{\\beta(\\hat x_{t[a]}-(1-\\delta)1_{a=a^\\ast}-\\delta/d)}{((1-\\delta)1_{a=a^\\ast}+\\delta/d)^{1-\\beta}} \\\\\\\\\n&=\\min_{\\delta\\in(0,1)}\\frac1T\\sum_{t=1}^T\\sum_{a=1}^d((1-\\delta)1_{a=a^\\ast}+\\delta/d)^\\beta-\\frac{\\hat x_{t[a]}^\\beta}{1-\\beta}+\\frac{\\beta\\hat x_{t[a]}^\\beta}{(1-\\beta)((1-\\delta)1_{a=a^\\ast}+\\delta/d)^{1-\\beta}} \\\\\\\\\n&\\le\\min_{\\delta\\in(0,1)}\\delta^\\beta d^{1-\\beta}+\\frac\\beta{(1-\\beta)T}\\sum_{t=1}^T\\sum_{a=1}^d\\frac{\\hat x_{t[a]}^\\beta}{((1-\\delta)1_{a=a^\\ast}+\\delta/d)^{1-\\beta}}\n\\end{align}$$\nFor non-outlier tasks we have $a=a^\\ast$ so the last summation over $a$ is at most $1/(1-\\delta)^{1-\\beta}$, while for outlier tasks it is at most $(d/\\delta)^{1-\\beta}$.\nSince we have $T-\\sqrt T\\le T$ of the former and $\\sqrt T$ of the latter we have the bound\n$$H_\\beta\\le\\min_{\\delta\\in(0,1)}\\delta^\\beta d^{1-\\beta}+\\frac\\beta{(1-\\beta)(1-\\delta)^{1-\\beta}}+\\frac{\\beta(d/\\delta)^{1-\\beta}}{(1-\\beta)\\sqrt T}$$\nAssuming $\\beta\\in[\\frac1{\\log d},\\frac12]$ this means $H_\\beta=\\tilde{\\mathcal O}(1+d^{1-\\beta}T^{-\\beta/2})$."}]

Author rebuttal:
We would like to thank the reviewers for their helpful reviews, which among other things have led to several useful references and an analysis of the robustness of our result to outliers (c.f. [our response to Reviewer fExn](https://openreview.net/forum?id=r6xGZ0XL2g&noteId=hvQFk8uNIu)); we plan to incorporate these into the revision. We hope to address any follow-up questions in the discussion.

To summarize the contributions of our paper: we develop a meta-algorithm for meta-learning the parameters of adversarial bandit methods and apply it to four such procedures (Sections 3.1, 3.2, 4, and D.3) across three different geometries (simplex, sphere, and polytope). This is the first analysis of meta-learning for adversarial bandits, and it yields provable performance improvements for sequences of multiple similar tasks, where performance is measured by task-averaged regret and task similarity is measured by distances between task optima induced by the specific within-task algorithm being studied. As an example, in the case of $T$ multi-armed bandit tasks with $m$ rounds and $d$ arms each where only $s\ll d$ of the arms are ever optimal for any task, the average regret of our approach is $O(\sqrt{sm\log d})$ (ignoring lower order terms in $m$ and $T$), compared to the usual MAB regret of $O(\sqrt{dm})$.

Meta-review: This work studies meta-learning parameters of adversarial bandit algorithms and proposes a regret bound on the average regret of adversarial bandit algorithms for $T$ bandit problems. The regret bound depends on the distribution of optimal arms and is favorable in settings where the total number of optimal arms is significantly smaller than the number of arms for each task. Reviewers are overall positive on the paper and agree that the paper addresses an interesting problem, giving a novel solution with meaningful guarantees. Most reviewers also agree that the paper is well written and the presentation is good. Multiple reviewers have expressed concern about lack of empirical evaluation of the results and while I agree that this is a theory paper, if the authors are able to add experiments, even as part of the appendix, this would strengthen the results. Multiple reviewers have also noted that computational complexity is not discussed in the main paper. Authors are encouraged to have a brief discussion in the camera ready version, space permitting.
Decision: Accept (poster)