Adaptive Regret for Bandits Made Possible: Two Queries Suffice
Authors: Zhou Lu
Qiuyi Zhang
Xinyi Chen
Fred Zhang
David Woodruff
Elad Hazan
Venue: ICLR 2024 poster (2024)
Keywords: adaptive regret
multi arm bandit
Primary area: learning theory

Abstract: Fast changing states or volatile environments pose a significant challenge to online optimization, which needs to perform rapid adaptation under limited observation. In this paper, we give query and regret optimal bandit algorithms under the strict notion of strongly adaptive regret, which measures the maximum regret over any contiguous interval  $I$. Due to its worst-case nature, there is an almost-linear $\Omega(|I|^{1-\epsilon})$ regret lower bound, when only one query per round is allowed [Daniely el al, ICML 2015]. Surprisingly, with just two queries per round, we give Strongly Adaptive Bandit Learner (StABL) that achieves $\widetilde{O}(\sqrt{n|I|})$ adaptive regret for multi-armed bandits with $n$ arms. The bound is tight and  cannot be improved in general. Our algorithm leverages a  multiplicative update scheme of varying stepsizes and a carefully chosen observation distribution to control the variance. Furthermore, we extend our results and provide optimal algorithms in the bandit convex optimization setting. Finally, we empirically demonstrate the superior performance of our algorithms under volatile environments and for downstream tasks, such as algorithm selection for hyperparameter optimization.

Published as a conference paper at ICLR 2024
ADAPTIVE REGRET FOR BANDITS MADE POSSIBLE: TWO QUERIES SUFFICE
Zhou Lu" Princeton University
Qiuyi Zhang*
Xinyi Chen
Google Deepmind
Google Deepmind
Princeton University
Fred Zhang UC Berkeley
David P. Woodruff Google Research
Elad Hazan
Google Deepmind
Carnegie Mellon University!
Princeton University
ABSTRACT
Fast changing states or volatile environments pose a significant challenge to online optimization, which needs to perform rapid adaptation under limited observation. In this paper, we give query and regret optimal bandit algorithms under the strict notion of strongly adaptive regret, which measures the maximum regret over any contiguous interval I. Due to its worst-case nature, there is an almost- linear 2((7)²==) regret lower bound, when only one query per round is allowed [Daniely el al, ICML 2015). Surprisingly, with just two queries per round, we give Strongly Adaptive Bandit Learner (StABL) that achieves Ö(Vr)T) adaptive regret for multi-armed bandits with n arms. The bound is tight and cannot be improved in general. Our algorithm leverages multiplicative update scheme of varying stepsizes and a carefully chosen observation distribution to control the variance. Furthermore, we extend our results and provide optimal algorithms in the bandit convex optimization setting. Finally, we empirically demonstrate the superior performance of our algorithms under volatile environments and for downstream tasks, such as algorithm selection for hyperparameter optimization.
INTRODUCTION
In online optimization, a player iteratively chooses a point from decision set, and receives loss from an adversarially chosen loss function. The classic metric for measuring the performance of the player is regret: the difference between her total loss and that of the best fixed comparator in hindsight.
However, as pointed out by Hazan and Seshadhri Hazan & Seshadhri (2009), regret incentivizes static behavior and is not the correct metric in changing environments. They instead proposed the notion of adaptive regret, defined as the maximum regret over any continuous interval in time. This notion intuitively captures adaptivity the environment, and is studied later by Daniely al. (2015) which gives an algorithm with near-optimal ((v log T') adaptive regret for any interval / simultaneously.
Most algorithms for minimizing adaptive regret, such as Hazan & Seshadhri (2009); Daniely et al. (2015), work by running Ollog 7' independent copies of online learning schemes and using meta- learner to aggregate them. Therefore, they make (log 7') queries per round. In practice, oftentimes it expensive to evaluate the arms. For example, an arm corresponds to set of hyperparameter values of large machine learning model, and playing an arm amounts to evaluating the model performance and fully training the model. This motivates the study of query-efficieet adaptive regret algorithms. Recently, Lu and Hazan Lu & Hazan (2023) give an improved algorithm with only Ollg log T') queries per round. However, the known lower bound Daniely et al. (2015) only shows that in the bandit setting, near-optimal adaptive regret is impossible with one query. This leaves the following question:
Equual contribution
1 Part of this work was done while visiting the Simons Insitute for the Theory of Computing

---

Published as a conference paper at ICLR 2024
Can we design algorithms with near-optimal adaptive regret using fewer queries?
In this paper we give an affirmative answer, showing that two queries per round is enough to guarantee an O ( adaptive regret bound. The key ingredient of our algorithm is using the additional query for exploration under special distribution on arms, which serves to construct unbiased loss estimators with small variance for both experts and the meta-learner.
1.1
OUR RESULTS
We design adaptive regret minimization schemes with the power to query additional arms. In the adversarial multi-arm bandit (MAB) problem, the algorithm selects and plays one arm per round. In our setting the algorithm can pick additional arms to query in parallel to selecting which arm to play, then the loss values of both the queried and played arms will be revealed, but the algorithm only suffers the loss of the arm played. This is similar to, but still different from the multi-point feedback model Agarwal et al. (2010), which suffers the average loss of the arms. The query complexity counts the total arm observations received, including the one played.
First, we prove that two queries suffice for Ö(v ((VT)) adaptive regret in the MAB setting (we slightly abuse the notation / denote its length \t. Our algorithm runs an EXP3-type meta-algorithm on top of black-box bandit learners A which are EXP3. It uses the additional query to perform exploration every round for constructing a bounded unbiased loss estimator. Then each bandit algorithm together with the meta-algorithm gets updated according the loss estimator. Together with the lower bound in Daniely et al. (2015), our algorithm gives a tight characterization of the query efficiency of adaptive regret minimization. Such Ollog T) improvement in the number of queries needed is significant for computational efficiency, for applications such as hyperparameter optimization in expensive settings.
Table 1: Adaptive regret bounds and query efficiency in the adversarial
bandits setting.
Algorithm
Adaptive regret bound
Number of queries
FLH Hazan & Seshadhri (2009)
VnT
O T')
SAOL Daniely et al. (2015)
Vnllog
(log T)
EFLH Lu Hazan (2023)
1b+c log
0
log log
This paper (Theorem 1)
Vn/logn n. T.T
Next, extend our MAB method to the bandit convex optimization (BCO) setting, proving that three queries suffice for Ö(vT) adaptive regret. We use one of the additional queries to do uniform exploration, which gets us the loss value of some expert i's prediction &, (A:(()). This value is used to construct both a bounded unbiased loss estimator to the meta EXP3 algorithm, and an unbiased sparse gradient estimator with bounded variance by leveraging another query to get l (A, + p)) where a is small random perturbation term.
Finally, we show empirically the advantage of using our adaptive algorithms in changing environments on synthetic and downstream tasks, such as algorithm selection during hyperparameter optimization.
1.2 RELATED WORK
Adaptive Regret Minimization Motivated by early work on shifting experts Herbster & Warmuth (1998); Bousquet& & Warmuth (2002), the notion of adaptive regret was first proposed by Hazan & Seshadhri (2009). They gave an algorithm called Haallo-tth-Leddin--Hiiseee adaptive regret for online optimization on strongly convex functions. The bound on the adaptive regret for general convex cost functions, however, is O(VT log T). This question has been further studied by sequence of work Daniely et al. (2015); Jun et al. (2017); Lu et al. (2022) which aims to improve the regret bound. In partieular, Daniely al. (2015) proposed the algorithm Strongly- Saaeee-OOnnn--amann (SAOL) achieving near-optimal O(v[log T') bound. Later, Jun al. (2017) improved this bound by a Vlog T factor and Lu et al. (2022) attained a second-order bound. Crucially, note that all the algorithms use O(log T') queries per round.
(FLH) with Olog² T)
2

---

Published as a conference paper at ICLR 2024
Recently, Lu & Hazan (2023) initiated study improving the efficiency of adaptive regret minimization. They showed a trade-off between adaptive regret and computational complexity, that an Ö(rb+t) +r) regret bound is achievable with log log base algorithms,each with one query per round. This result differs from ours in two aspects: (i) Lu & Hazan (2023) studied the computational complexity (number of base algorithms), while we consider the query complexity and achieve a better bound; and (ii) Lu & Hazan (2023) focused on improving the classic
saaneential-sstor--looo technique Hazan Seshadhri (2009); Daniely et al. (2015) itself, by showing an regret upper bound with doubly exponential lookback. However, they also showed matching lower bound that the history-lookbut technique must use (log log T') experts to achieve non-vacuous regret. Instead, our work bypasses such limitations by incorporating the EXP3 method into the classic framework, using only constant number of queries.
For adaptive regret in the BCO setting, Zhao et al. (2021) showed that an Ö( adaptive regret bound achievable under the two-point feedback model. However, the result is weaker than ours in two aspects. First, our result provides a strongly adaptive regret bound Ö(VT) which depends on the interval-length, and is stronger notion than adaptive regret. Second, our regret bound is independent of the condition number K, while their regret bound is O(dGDRVT). We will discuss the comparison in more details later.
Dynamic Regret Dynamic regret another related notation to handle changing environments in OCO, which aims to capture comparators with bounded total movement instead. Starting from Zinkevich (2003) which provided an Ó(P dynamic regret bound of vanilla OGD where PP denotes the path length, there have been many works on improving and applying dynamic regret bounds. Zhao al. (2020): Zhang et al. (2017) achieved improved dependence assumptions. Baby & Wang (2021; 2022) focused on the setting of exp-concave and strongyly-onnva loss, showing that the classic adaptive regret algorithm FLH Hazan & Seshadhri (2009) guarantees Ö( P dynamic regret. Some works study the relationship between adaptive regret and dynamic regret, for example Zhang et al. (2018; 2020).
P under further
Bandit Convex Optimization The study on BCO was initiated by Flaxman et al. (2005), which showed how to construct an approximate gradient estimator with bandit feedback, providing an O(T3/4) regret bound. If multi-point feedback is allowed, the regret bound can be improved to O(VT) shown in Agarwal et al. (2010). Later, Bubeck al. (2017) used a kernel-based algorithm to achieve the optimal O(VT) regret bound. Nevertheless, none of the prior works considered adaptive regret in the BCO setting.
SETTINGS AND PRELIMINARIES
We study adaptive regret in limited information model, for both the multi-armed bandit (MAB) and the continuous bandit convex optimization (BCO) problems. In the MAB problem, a decision maker A plays game of T rounds, she pulls an arm 2, round and chooses an additional set of arms X₂ to query. Then an adversary reveals the values of the loss vector & on { U.X, The goal is to minimize the (strongly) adaptive regret, which examines all contiguous intervals I [j s| E [T]: (we will omit when it's clear from the context)
SA-regre((AA
= max s-j=1
CF.
min
c e
For the BCO setting, similarly the decision maker chooses v, K. C Rd at each time along with a set of points X,, where K. is some convex domain, then the adversary reveals the loss values on (xr) X,, The player aims minimize the (strongly) adaptive regret as well: (notice for expected regret, it contains the above definiton for MAB as a special case when KC is simplex)
SA-regret(AA max
Σ (((x)) - min
(x)
マードー
3

---

Published as a conference paper at ICLR 2024
The decision maker has limited power to query 4, For every round she has a query budget X < N for some small constant E N In particular, we will only consider the case = 1 for the MAB problem and N = 2 for the BCO problem. We emphasize the choice of which arms query is made before any information of the loss is revealed, thus differentiates our setting from the stronger "Bandit with Hints" setting Bhaskara al. (2023). Our setting is stronger than the vanilla MAB setting, but weaker than the full-information setting or the hint setting.
We make the following assumption on the loss l, and domain K, which is standard in literature. Assumption 1. For the MAB problem, the loss vector & is assumed to have each of its coordinate bounded in [0, 1]. For the BCO problem, we assume the loss & is convex, G-Lipschitz and non- negative. The convex domain K. is sandwiched by two balls centered at origin: rB C K. C DB, we denote the condition number K D/r.
2.1 THE QUERY MODEL
Our query model is similar to the multi-point feedback model Agarwal et al. (2010), with slight difference. Both models specify a set of arms to query beforehand, then after the adversary reveals the loss, both models receive loss information on the set of chosen arms. Here, the definition (evaluation of the loss function a given point) and complexity (number of evaluations) of query are the same for both models, and the only difference is that our model only incurs loss of the actually played arm, while the multi-point feedback model incurs the average loss the set of chosen arms. Notice that neither model strictly implies the other model. As a result, it's fair to compare the query efficiency of our result with previous works under the multi-point feedback model.
2.2 THE EXP3 ALGORITHM
The EXP3 algorithm for adversarial MAB Auer et al. (2002) is based the multiplicative update method, and performs a weight update according to an unbiased loss estimator using bandit feedback. Denote wel (k) the weight of arm & at time t, the EXP3 algorithm samples the F according to the weights we (k:). Ideally, we would like to update each weight based on full information of the loss:
(k+ = wx(k) (1 Tp4 ex)
In the bandit setting, we have only the value of eT Ez,- Let 1 denote the all-ones vector. The EXP3 algorithm instead constructs an unbiased estimator & to replace f,:
Oz
(1(1)
i== we (k)
This pseudo loss has bounded variance. In particular, Blw, 271 < algorithm an Ö(VnT) regret bound.
which gives the EXP3
2.3 STANDARD FRAMEWORK FOR MINIMIZING ADAPTIVE REGRET
We briefly review the standard framework of adaptive regret minimization. Since adaptive regret asks for small regret over all intervals, a simple idea is to construct, for any interval J, base learner Ar that achieves optimal regret O(VT) on There are O(T2) contiguous intervals between [1, T]. Thus, naive procedure is to these ( experts, and this leads to an ((V log T') adaptive regret.
meta-learner, such as multiplicative weights (MW) update, on
Unfortunately, although the regret bound is near optimal, the naive algorithm is inefficient. In particular, for any there are (2"))) number of intervals containing t, and the naive algorithm needs to maintain and update Q(T') number of base learners per round. To resolve this issue, the key technique is to consider only a subset S' all intervals Hazan Seshadhri (2009); Daniely et al. (2015):
S = {s2* (s 1)2* 1] 0 S S log T, E N (s + 1)2* - TT
The set S, known as the geometric interval set, contains all successive intervals with length equal to some power of two. In particular, the kth expert will only need to optimize the series of intervals 2 ... one by one. With this technique, the algorithm only needs to hold a running set of base algorithms with size Ollog while maintaining a near-optimal Ö(VT) adaptive regret bound.
[2*, 2 2² 1). [2 x 2*
4

---

Published as a conference paper at ICLR 2024
3 ADAPTIVE REGRET IN MULTI-ARMED BANDITS
In this section, we study efficient adaptive regret minimization in the adversarial multi-armed bandit (MAB) setting. We propose procedure (Algorithm 1) that achieves Ó(vnI) adaptive regret, using only two queries. high level, the algorithm maintains set of instances of the EXP3 algorithm (i.e., base learners) and aggregates them via a MWU meta-algorithm.
Algorithm Strongly Adaptive Bandit Learner (StABL)
1: Input: general EXP3 algorithm A and horizon T.
log log S k S TogT, N 3: Construct B log T - (1 log log T) independent instances of EXP3 algorithm Ax, where
2: Construct interval set S {[s2*, (s + 1)2 - 1]
As optimizes each {I E S [/]} one after another since they don't overlap.
4: Denote wy (k) to be the weight assigned to A₃ at time by the metu-algorithm.
5: Denote k) RR" to be the distribution over arms by Ak time i, and u(t, k); to be the
probability of sampling arm by A& at time f.
6: Define 7/2: min 1/2 1/ n [k] and initialize wi (ks) 7s all k E [B].
7: for 1...... T do
8: Let W Σx wy (1)) and p(t)
1 W. (..., we(k)....) be the distribution over the base learners.
9: For all i E [n]], let
maxt vlt, k)
Σn v(1
P(() 2E, maxi k)?
2B
// This defines a probability distribution over n arms. Sample 24 ((t)uut k), and in parallel sample x P(t).
10:
// Only the second sample ay will be used for wei weight updating.
11: Play 2t, suffer loss f, ez, and observe loss Ef ext. Compute loss estimator
b = 1i=z P(I); 4 ex!.
12: Update the weight v(t + k) of each EXP3 instance with loss estimator E, via Algorithm 2. Update the meta-algorithm's weights over base learners via the loss estimator l.. For each update (k) as follows,
(k) = {{
Tl (k) (1 + m+F(())
2 +
else
where Fz(k)= 27 Σx p(1)a((1, vlt,
end for
Algorithm Sub-routine: EXP3 with a General Loss Estimator
1: Input: horizon T, learning rate y and wi
2: for = I,...,
3: Play i Wt.
4: Get unbiased estimator of loss E.
5: Update (t) = w. (i)e -vē(()) wt+1 1
ge+1
6: end for
Theorem (Adaptive regret minimization for multi-armed bandits). For the multi-armed bandits problem with n arms and rounds, Algorithm achieves an expected adaptive regret bound of O (Vnl logn log 1.5 T), using two queries per round.
The main idea is use EXP3-type algorithms for both the black-box base learners and the meta- algorithm in the typical adaptive regret framework. Directly using EXP3 in the MAB setting will fail, because the weight distribution might become unbalanced over time and the unbiased estimator of
5

---

Published as a conference paper at ICLR 2024
the loss will have huge variance. When the unbiased estimator is propagated to the meta algorithm, it serves now as the value of "arm" which leads to a sub-optimal regret.
The remedy is to an additional evaluation to create unbiased estimators of the loss vector with controllable variance, for updating both experts and the meta-algorithm. A naive (but sub-optimal) choice is to sample uniformly over the arms to observe s', and update both experts and the meta- algorithm (line 10 Algorithm 1). By doing this, the loss estimator & not only unbiased, norm bounded by As a result, the variance term in the classical EXP3 analysis is bounded by n². Thus, the regret of the base learners, as well as the meta-algorithm, are vn factor worse than optimal.
also
Instead of the naïve uniform exploration, we choose the distribution of the additional query to be the average of a uniform exploration among all base learners' choices and a near-optimal distribution for the mlgo--aloor.hmm. Below we briefly explain the design of this importance sampling P(t), (line 9 in Algorithm 1). Pt is the average of two distributions, the first one controlling the regret of the meta learner while the second one controlling the regret of base learners. If P. is merely the second distribution, it achieves near-optimal regret for base learners, with the excessive term v improved to Vlog T. However, the second distribution alone will make the regret of the meta learner unbounded, thus we mix it with the first distribution which is designed to control the regret of the meta learner. Such mixing known only affect the regret by constant for EXP-3 type algorithms.
3.1 PROOF SKETCH
In the following, we slightly abuse notation and let f, = f, ez for x E [n]. The proof consists of three steps: decomposing the randomness of playing zt. bounding the base learners' regret, and analyzing the regret of the meta-algorithm.
There two sources of randomness in the algorithm, namely, randomness pl in sampling which arm æ, to play, and ob in sampling which arm xy to observe and update weights. The key observation is that pl is independent of ob. Thus, have the following equivalence via linearity and the tower property of expectations, for any fixed interval and arm x",
Step 1:
Epl.ab
ΣET d4
EET EE1
Eob
Σ Σ Ep(DaolL,) ΣE LIEI
IES
SEI
which decouples the randomness of playing 24 from observing 24-
Step 2: We prove the following lemma EXP3 algorithms with general unbiased loss estimators, which gives a regret guarantee for Algorithm 2.
Lemma 2 (Regret for EXP3). Given e, an unbiased estimator of l, such that for some distribution zt. (1) 2.te5&2 and ((())= = 0 for + i with probubility (i). Suppose zt satisfies we(i) S Cz)(i) for all where (i) represents the weight of the ith expert at time t. Algorithm using L with log
has regret bound 2/Onl TnC
As a result, noticing = log T in our algorithm, we have that for any expert As, its regret on interval I can be bounded by O(vnl log T).
Step 3: We analyze the regret of the meta-learner, which is Ept. ob [Ere/ E, xt E1El Et v(t, = Emb EEEE Fe (l))) Define the eseudo-weight (kk to be wi(k) = we(k) and W. = E. Wy (k),, we
first prove W, S fllog + 1) using induction, which leads to the following estimate
Eaa
F((k))
< Eob
Σ (K))
+
2 2 T
m7
LET
LEET
Then we show the term Ead F7 (k)] can be bounded by:
(ee ((T)))) P(t);
Eab [R)] < Eob.et
Σ
mmxxe] vlt, o(t,Ak)
< 2n log

---

Published as a conference paper at ICLR 2024
which implies the regret of our algorithm any interval I S, can be bounded by Ollog TV / n).. Finally, such regret can be extended to any interval at the cost an addi- tional Vlog I term, by Cauchy-Schhae Schhha- (each arbitrary interval can be decomposed into disjoint union of Olog T) geometric intervals as in Daniely et al. (2015)).
ADAPTIVE REGRET IN THE BCO SETTING
The result from the previous section inspires similar approach to achieve near-optimal adaptive regret in the bandit convex optimization (BCO) setting with constant number of queries? The answer yes, that near-optimal adaptive regret is achievable with three queries, at the cost of extra logarithmic terms in the regret.
consider the following question: we use
The algorithm for adaptive regret in the BCO setting (see appendix) has similar spirit as Algorithm 1. At time t, each expert & asks for gradient estimation at point (t),, and we only randomly sample one expert to get the gradient estimation. If we sample expert k,, the estimation for As, is (rru(l((An (1) + ò.u) le (AR, (())
and the gradient estimation for the rest of experts O, where m is the number of experts, ö is a small constant and u is random unit vector. Such estimation is classic in the two-point feedback BCO setting Agarwal et al. (2010), fact all we need is (nearly) unbiased estimation of loss with bounded absolute value. Then
use the same approach as the MAB case make unbiased estimation of the experts' losses, by setting
(t)) ml, (t))
We have the following regret guarantee for Algorithm The proof delayed the appendix.
Theorem 3. In the BCO setting, Algorithm with 6, = < uses three queries per round and achieves an expected adaptive regret bound of
O (dGIDVILOg'T)
Theorem also directly applies to the full-information setting, improving the query complexity of all previous works in adaptive regret from O T)) to a constant, while preserving the optimal regret.
Compared to Zhao et al. (2021), note that though their algorithm uses one fewer query, they considered only the weaker notion of adaptive regret, failing to achieve dependence on interval length which leads to worse vT dependence on horizon. We discuss how further reduce the required number of queries by one for strongly-adapiic regret in the appendix, by using the linear surrogate loss idea of Zhao al. (2021) in our algorithm.
5 EXPERIMENTS
In this section, we evaluate the proposed algorithms on synthetic data and the downstream task of hyperparameter optimization. We note that even though the algorithms are stated in terms of losses, we find that in practice, using rewards instead of losses lead to better performance.
5.1 LEARNING FROM EXPERT ADVICE
Experimental Setup We first consider the learning with expert advice setting with linear rewards, and demonstrate the advantage of using an adaptive algorithm in changing environments. For simplicity, the arms and experts are equivalent arms, indexed from 0 to N - 1, and there are N experts, where the i-th expert (zero-indexed) always suggests pulling the arm We take N 30, time horizon = 4096, and for each time step, we randomly generate a baseline reward F; E g where 7., is drawn from the uniform distribution over [0, 0.5). To simulate the volatile nature of the environment, we divide the time horizon into 4 intervals, and add an additional reward to the baseline reward of different expert in each interval. In particular, for t E [0, 1023), we set the reward ft,0 = Fe,0 + 0.5 and r2 = Tt,s for * 0; for t E [1024, 2047], we do the same for expert 1, and so on. The reward at each time step is r It. where 27 is the point played.
our construction. More specifically, there are N
7

---

Published as a conference paper at ICLR 2024
Adapthye Ensembling
Adaptbi Ensembling
Rolli unoll CCA
06-
00-
0.4
0.3
300
1000
1500
2000
2300
2003
2000
4330
3000 1500
1000
2000
2500
2000
20100
4000
Figure 1: Comparison plots of the algorithm rewards in the learning with expert advice setting. The right subfigure shows the performance of the algorithms when the best arm changes random intervals, and demonstrates the advantage of using base algorithms with varying history lengths
Analysis In the first experiment, we compare the performance of the non-adaptive EXP3 algorithm with uniform exploration, StABL., and the StABL algorithm with naive exploration. In BL. with naive exploration, the observation query sampled with the uniform distribution (Line 10 in Algorithm is replaced with the uniform distribution). We run all algorithms 5 times and plot the moving average of their reward with a window of size 50 in the left subfigure of Figure 1. Both StABL and and StABL Naive can adapt to changing environments and recover after the best arm has changed. In contrast, EXP3 is optimal in the first interval, but its performance quickly degrades in the subsequent intervals. Compared StABL, StABL Naive is worse in most intervals, reflecting the suboptimal performance resulting from the naive observation sampler.
To understand the importance of having base algorithms with varying history lengths, also compare StABL with a variant, StABL Single Scale, where the base algorithm only has one history length of 1024. Such a variant would perform well in the previous experiment, since the intervals have the same length. In this experiment, we randomly generated time steps at which the best arm changes, and they are 1355, 1437, 1798, 3249, for time horizon of 4096. As before, we run each algorithm times and compare the moving average reward in the right subfigure of Figure 1. In this experiment, StABI. Single Scale struggles in intervals that do not conform to length of 1024. Thus, even though StABL requires more memory and compute by running log T base algorithms, it is more robust to volatile environments that can have irregular changes.
5.2 ALGORITIM SELECTION FOR HYPERPARAMETER OPTIMIZATION
Algorithm as Arms We compare the effectiveness of bandit-feedbace regret minimization algo- rithms for the downstream task of choosing the best algorithms for minimizing blackbox function. Specifically, we view each round as a selection process between an ensemble of evolutionary strate- gies, each with different algorithm parameters, such as perturbation, gravity, visibility and pool size Yang& & He (2013). Therefore each arm represents a specific evolutionary algorithm and the rewards of each arm are observed per-round in a bandit fashion, indicating the performance of the algorithm at that round, given all of the data observed so far.
Benchmark and Reward Signal The reward is determined by the underlying task of blackbox optimization, which is done on Black- Optimization Benchmark (BBOB) functions (Tušar et al., 2016). BBOB functions are usually non -eggatvte and we are in the simple regret setting, in which we want to find some x such that f(x is minimized. Therefore we use the decrease of the objective, upon evaluation of the algorithm's 's suggestion, as the reward. Specifically, if Dj (zi, fxxx)) are all the evaluations so far in round k. then each algorithm A, suggests x; = (D,,) and the corresponding fxz)), 0). Note that this reward is always positive and we normalize our BBOB functions so that it is within Jo, 1]. Note that this reward signal is sparse, so we also add regularization term of (2f(z,) with À = 0.01 of the negative objective into the reward.
reward is r3 max(min; (xx:))
In addition to normalization, we also apply random vectorized shifts and rotations on these functions, as well adding observation noise to the evaluations.
8

---

Published as a conference paper at ICLR 2024
Analysis We ran the four algorithms: the uniform random algorithm, classic EXP3 al- gorithm, the EXP3 algorithm with uniform exploration, and StABL with history lengths (20, 40, 80, 160, 320, 640, 1280, 2560]. We rum each of our algorithms in dimensions d = 32, 64 and optimize for 1000, 2000 iterations with 5 repeats. For metrics, we use the log objective curve, as well as the performance profile score, gold standard in optimization benchmarking (higher is better) Dolan & Moré (2002). Our full results are in the appendix and here, we focus on the SPHERE function (Fig. 2), where we see that StABL generally performs better adaptation than the EXP3 algorithms leading to better optimization throughout. Specifically, for the first half of optimization, both StABL and EXP3-Uniform enjoy a consistent performance advantage in performance, with respect to the Uniform strategy. However, this advantage sharply drops after around 600 Trials, after which the EXP3 strategy is no longer competitive against Uniform and ends up worse, as its performance curve abruptly stops at Trial 700. StABI. generally tracks with the EXP3 strategy throughout this process but is noticeably better at adapting and maintaining its advantage after the critical turning point.
Dim: Exp:
Exp:
1436
1635
1210
SAALL
0901
oo3_unitom unifoom
0757
0.344
0331
uniform
0.74
-0.47
0.374
-0.66
026
-0.887
-1002
-1279
-1555
-1.528
-1731
-1957
-1.549
SAAL
121
ep3 uniform
-2440
uniform
-2.852
200
400
600
800
1000
200
400
600
800
1000
of Thais
# of Thats
Figure 2: Algorithm comparison plots of the log objective (lower is better) and the performance profile score against the Uniform baseline (higher is better) for minimizing the 32-dimensional SPHERE across 1000 trials.
6 CONCLUSIONS
We study adaptive regret in the limited observation model. By making merely one additional query with carefully chosen distribution, bound in the multi-arm bandit setting. This result not only improves the state-of-the-art query efficiency of Olog log T) in Lu & Hazan (2023), but matches the lower bound in the bandit setting Daniely et al. (2015), thus providing a sharp characterization of the query efficiency of adaptive regret. As an extension, we prove that the optimal Õ(VT) adaptive regret can be achieved in the bandit convex optimization setting, with only two additional queries. We also conduct experiments to demonstrate the power of our algorithms under changing environments and for downstream tasks. We list some limitations of this work and potential directions for future research, elaborated below.
algorithm achieves the optimal Ö(VnI) adaptive regret
Reduce the logarithmic dependence in T: Although regret bound is tight in the leading parameters n, I, it involves a worse dependence on log T. For the full-information setting, the best known result in Orabona & Pál (2016) only contains an vlog T dependence. The main open question is thus: can the log-.5. 1.5 T factor be improved in general?
Fewer queries for BCO: Our BCO A Algorithm uses two additional queries to achieve the optimal adaptive regret bound, however for the MAB setting Algorithm I requires only one query. Though BCO is harder problem than MAB, and the lower bound of Daniely et al. (2015) was designed for MAB, we wonder whether an algorithm can use even fewer queries in the BCO setting.
Extension to dynamic regret: In the full-information setting, any advance in adaptive regret of exp-concave loss implies improved dynamic regret bounds via a black-box reduction, shown in Lu & Hazan (2023). However, it seems harder in the bandit setting. The fundamental difficulty is, for the meta-learner, how to exploit exp-concavity (or strong convexity) of the loss in the MAB setting.

---

Published as a conference paper at ICLR 2024
REFERENCES
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Conference on Learning Theory (COLT), 2010.
Peter Auer, Nicolo Jesa-Bianchi Yoav Freund, and Robert E Schapire. The non-stochastic multi- armed bandit problem. SIAM Journal on Computing, 32(1):48-777 2002.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Conference on Learning Theory (COLT), 2021.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, and Kamesh Munagala. Online learning and bandits with queried hints. In 14th Innovations in Theoretical Computer Science Conference (ITCS), 2023.
Olivier Bousquet and Manfred K Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3:363-396, 2002.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex opti- mization. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing (STOC), 2017.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning (ICML), 2015.
Elizabeth D Dolan and Jorge J Moré. Benchmarking optimization software with performance profiles. Mathematical programming, 91:201-213, 2002.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. Proceedings of the Sixteenth Anmual ACM-SIAM Symposium Discrete Algorithmss (SODA), 2005.
Elad Hazan and Comandur Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th Annual International Conference Machine Learning (ICML), 2009.
Mark Herbster and Manfred K Warmuth. Tracking the best expert. Machine learning, 32(2):151-178. 1998.
Kwang-Sung Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Zhou Lu and Elad Hazan. On the computational efficiency of adaptive and dynamic regret minimiza- tion. arXiv preprint, 2023. URL https: /aaxivivvvv/.../////i///aa/aa/aa wwwo/orrss........o.... 2207.00 64
Zhou Lu, Wenhan Xia, Sanjeev Arora, and Elad Hazan. Adaptive gradient methods with local guarantees. arXiv preprint arXiv:2203.01400 2022.
Francesco Orabona and Dávid Pál. Coin betting and parameter-frre online learning. Advances in Neural Information Processing Systems (NIPS), 2016.
Tea Tušar, Dimo Brockhoff, Nikolaus Hansen, and Anne Auger. Coco: the bi-objective black box optimization benchmarking (bbob-biobj) test suite. ArXiv e-prints, 2016.
Xin-She Yang and Xingshi He. Firefly algorithm: recent advances and applications. International journal of swarm intelligence, 1(1):36-50, 2013.
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi- Zhou. Improved dynamic regret for non-degenerate functions. Advances in Neural Information Processing Systems (NIPS), 2017.
10

---

Published as a conference paper at ICLR 2024
Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In International Conference on Machine Learning (ICML), 2018.
Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simulta- neously. International Conference on Artificial Intelligence and Statistics, pp. 309-319, PMLR, 2020.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. The Journal of Machine Learning Research, 22(1):5562- 5606,, 2021.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Machine Learning (ICML), 2003.


Reviews:
[{"review_id": "nurwJ5w0rl", "reviewer": "Reviewer_wKMs", "summary": "The authors show strongly adaptive regret bounds for the algorithmic problems of prediction with experts and online convex optimization in a limited information setting. They specifically consider two problem settings:\n\n1. A generalization of adversarial MABs (decision space is $\\mathcal{K} = [n]$ set of arms) where, at each step $t \\in [T]$, the learning algorithm chooses an arm $x_t \\in [n]$ and suffers loss $\\ell_t(x_t)$, but also is allowed to query the losses for an additional set of arms $X_t \\subset [n]$ with $|X_t| \\leq N$. $x_t$ and  $X_t$ are chosen in parallel, and the adversary chooses the losses after seeing $x_t, X_t$. So the learner gets the $(N+1)$-dim loss vector $[\\ell_t(x) : x \\in X_t \\cup \\\\{x_t\\\\}]$ while suffering only the loss $\\ell_t(x_t)$.\n2. A generalization of Bandit Convex Optimization (BCO) where the regret is against points from a well-conditioned convex decision space $\\mathcal{K} \\subset \\mathbb{R}^d$, where the learner again chooses $x_t \\in \\mathcal{K}$ and suffers the corresponding loss $\\ell_t(x_t)$, but receives the loss values $[\\ell_t(x) : x \\in X_t \\cup \\\\{x_t\\\\}]$ for some set $X_t$ with $|X_t| \\leq N$.\n\nIn both settings, they bound the SA regret: $\\text{SA-Regret}(\\mathcal{A}, I) = \\max_{[r,s] : s - r = I} \\left[\\sum_{t=r}^{s} \\ell_t(x_t) - \\min_{x \\in \\mathcal{K}} \\sum_{t=r}^{s} \\ell_t(x)\\right]$\n\nTheir query-feedback model is very similar to multi-point bandit feedback (Agarwal et al, 2010), but with the crucial difference that the learner suffers loss $\\ell_t(x_t)$ for the chosen arm rather than the average of the losses for all the queried arms.\n\nThey then show two main theoretical results:\n1. A $2$-query algorithm ($N = 1$) for MABs with SA regret bound of $O(\\sqrt{n I \\log n} \\cdot \\log^{1.5} T) = \\tilde{O}(\\sqrt{nI})$.\n2. A $3$-query algorithm ($N = 2$) for BCO with SA regret bound of $O(d G D \\sqrt{I} \\log^2 T) = \\tilde{O}(\\sqrt{I})$, where $\\ell_t$s are $G$-Lipschitz and $\\mathcal{K}$ is contained in the radius $D$ $\\ell_2$-ball centred at the origin.\n\nThey also have basic experimental results with the implementations of the algorithm in synthetic, changing environments. \n\nReferences\n----------------\n(Agarwal et al, 2010) Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.\n(Daniely et al 2015) Strongly Adaptive Online Learning", "questions": "(i) In page 3, paragraph 6, I believe that the \"special case when $\\mathcal{K}$ is a simplex\" is a bit stronger than MAB (since it would effectively consider all convex combinations of arms).\n\n(ii) In the description/pseudocode of Algorithm I, calling Algorithm 2 as a subroutine seems slightly ambiguous, since Algorithm 2 is written as a full learning loop (whereas the actual operation seems to be an update $v(t+1,k) \\leftarrow v(t,k)$ for each $k$).\n\n(iii) In page 6, end of section 3, \"can be extended to any interval .... by Cauchy-Schwarz\" seems very opaque. I would suggest at least mentioning that each arbitrary interval can be decomposed into a disjoint union of $O(\\log T)$ geometric intervals as in (Daniely, 2015).\n\n(iv) Including the code as supplementary material/link in the final version would enhance the value of having the experiments.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* For MABs, the query complexity per round (2 queries) is optimal for getting sublinear adaptive regret (lower bound from (Daniely 2015)). It is also a significant improvement on earlier work (Lu and Hazan 2023), from $O(\\log \\log T)$ to $2$. In the regret bound, the dependence on $I$ is tight, whereas the dependence on $n$ is, I believe, tight up to a $\\sqrt{\\log n}$ factor. The query complexity is exactly optimal (for sublinear SA regret), and a significant improvement on earlier work.\n* For BCO, both the query complexity and the regret together give substantial improvements on earlier work (query complexity improved from $\\log T$ to $3$ for the existing $\\tilde{O}(\\sqrt{T})$-regret full-information algorithms, substantial improvement in the dependence of regret on $\\sqrt{T}$ (weak) versus $\\sqrt{I}$ (strong) when compared to the $2$-query adaptive regret algorithm of (Zhao et al 2021)).\n* The algorithms innovatively combine existing techniques --- such as the geometric interval sets used by (Hazan and Seshadhri, 2009) and later work, as well as the SAOL-meta-learning approach used by (Daniely et al, 2015) --- with the Exp3 framework.", "weaknesses": "* The experimental results are a bit weak. For MABs, the $N (= 30)$ and $T (=4096)$ values are too small, and each algorithm is run only $5$ times to average out the reward curves. The experiments also compare their algorithm (StABL) with handicapped variants (StABL Naive and StABL Single Scale, which do illustrate certain requirements on the structure of StABL) as well as Exp3 (which is of course expected to perform badly in a changing environment). It would be interesting to see the practical tradeoff in the reward curve vs. computational efficiency, for say StABL and Full-EFLH from (Lu and Hazan 2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FY8M5zzJnv", "reviewer": "Reviewer_kZqs", "summary": "This paper shows that strongly adaptive regret is possible in bandit setting if one allows 2 queries in the MAB setting and 3 queries in the BCO setting. The regret is measured wrt only one of the queried points. In the MAB setting, the second query point is used as a free ticket for exploring the base learners: free ticket because, the authors don't care about the loss suffered by the exploration query.", "questions": "see above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors uncover a previously unknown  phenomenon in the bandit setting.\n\n- The presentation is clear.\n\n- Experiments are conducted to validate theory.", "weaknesses": "- The main weakness (and hence the low score)  is due to a confusion I have regarding the paper. In the middle of page 15 in the supplementary material, the authors state that the weights are positive to get the inequality $\\tilde W_t \\ge \\tilde w_t(k)$. Is the positivity proved somewhere in the paper? If not, can you provide the arguments for positivity of the weights?\n\nI think this is a really interesting paper and I would be happy to recommend acceptance if the authors can clear this confusion.\n\n- If we care about the average loss of both query points as in the multi-point feedback model of Agarwal et al 2010, does the pessimistic lowerbound on strongly adaptive regret still hold? A discussion on this can be helpful to readers. Also a discussion on the practical applications where your feedback model can be inadequate helps to understand the limitations of the work.\n\nOther comments:\n- In section 1.1, the authors say that their algorithm is run over black-box base bandit learners. Then in the description of Algorithm 1, they take the base learners to be EXP3, essentially not viewing the base learners as a black-box. This seems self-contradictory.\n\n- Line 13, algorithm 1, unclear what $2^k | t+1$ means. I assumed that these are the inactive base learners\n\n- Line 3 of algorithm 2, $w_{t}$ must be $x_{t}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i8zzegD19Q", "reviewer": "Reviewer_gNKg", "summary": "This paper studies strongly adaptive online learning with bandits feedback.\nInstead of making algorithms close to optimal over the whole time periods $1,\\dots, T$, strongly adaptive algorithms ensures that the performance on every time interval is close to optimal.\nThis paper achieves $\\mathcal{O}(\\sqrt{n |I|})$ adaptive regret for multi armed bandits setting.\nEspecially, the proposed algorithms only require $2$ queries per round, which improves previous results requiring $O(\\log T)$ queries.\nThe authors also extend their results to bandit convex optimization setting, and conduct experiments to show empirically the advantage of their algorithms.", "questions": "In the proof of Theorem 1, the author uses inequality $log(1+x)\\ge x-x^2$ for $x\\ge-1/2 (page 15).\nIs there any proof to show $\\eta_k \\widetilde r_t(k)\\ge -1/2$ for every $t$ and $k$?\nIntuitively, $\\widetilde r_t(k)\\$ could be of order $v(t,k)_i/P(t)_i = O(log T)$, which implies that $\\eta_k$ should be scaled $O(1/ log T)$.\nThis may leads to another $O(log T)$ term in the regret.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea is solid. Instead of reducing the number of base algorithms, the authors try to reduce the total number of interactions between the base algorithms and the environment. This setting makes sense when the cost of running base algorithms is less than the cost of interacting with the environment.\n- Experimental results demonstrate the advantage of the design and show a remarkable improvement over the trivial EXP3 algorithm with uniform exploration.\n- The paper is well writen. The proof in the appendix is well organized and mainly correct.", "weaknesses": "The main weaknesses is that there is essentially no difference between $2$ queries and $O(log T)$ queries: the high level idea of bounding the base learners regret is to use query $Uniform(A_1,\\dots, A_B)$ instead of using $A_1,\\dots, A_B$ independently.\nGiven that $B=\\log T$, this method will at most scale the regret by O(log T) (as the results indeed show the regret scaling in this order), making it a trivial idea.\nBoth of $2$ queries and $O(log T)$ queries separate exploration and exploitation, which goes against the original intention of the bandits setting.\n\nBesides, the authors should discuss the tradeoff of $O(log T)$ terms between regret and number of queries.\nNote that in this problem the order of $O(log T)$ is not trivial: the number of base algorithms is only $O(log T)$.\nBased on the current results, the cost of reducing the number of queries by $O(log T)$ times is an increase in regret by $O(log T)$ times (possibly more, see the Questions parts below).\nThis should be well specified in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ESqscJxU2f", "reviewer": "Reviewer_EXm4", "summary": "The paper investigated strongly adaptive regret under the multi armed bandit set up. In addition to standard multi arm bandit framework that the learner pulls a single arm and suffers a loss generated by the chosen arm, if the learner is allowed to query one extra arm at each iteration free of charge, then the proposed algorithm `StABL` achieves $O(\\log T \\sqrt{n I \\log n} )$ strongly adaptive regret over any interval $I$ for a game consistent of $n$ expert span over a time horizon $T$. \n\nIn addition, a mirroring design of  `StABL`  can also be applied to solve bandit convex optimization problem if the learner has access to query two additional arms free-of-charge. This resultant to $O(dGD\\sqrt{I} \\log T )$ regret for $G$-Lipschitz loss and $d$-dimensional convex domain $\\mathcal{K}$ that can be sandwiched between two $\\ell_2$ ball with diameter $r, D$, respectively.", "questions": "No", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is good at gathering key ingredients needed from previous literature, the intuition of the algorithm construction, and the necessity of the second query in order to achieve desired result.\n\nThe result is novel. Given previous lower bound on showing strongly adaptivity for bandit is impossible, this paper considers the nearly identical set-up to the impossible scenario and the presented result is optimal. Overall, in order to achieve the optimal regret in comparison to previous works which generally require $O(\\log T)$ requires, the presented algorithm only require two queries for multi armed bandit set-up, three queries for the bandit convex optimization set-up. For the later case, it is also possible to achieve with two queries.\n\nThe experiment on synthetic data supports the construction of the algorithm adapts to changing environment. The proposed algorithm also excel in practical downstream tasks is demonstrated.\n\nOverall, this paper is technical solid. The investigated problem is interesting, and the presented result is strong. It should be accepted provided the clarity of the write-up needs to be improved.", "weaknesses": "pg 4: sec2.2 second equation, LHS is a scalar, RHS is a vector \n\npg 4: sec 3. The abbreviation 'MWU' appeared the first time\n\nIn general, clarity of the write-up for section 3 needs to be improved. \n\nAlgo1: some part of the algorithm is ambiguous. For example, it might be more concise to gather all initialization parameters of exp3 base algorithms $\\mathcal{A}_k$ together: ( Initialize $\\mathcal{A}_k$ as algorithm 2 with learning rate ... and time horizon... ). Currently it is not immediately clear how $\\mathcal{A}_k$ was initialized, and $v(t,k)$ is the $t^{th}$ output from $\\mathcal{A}_k$ (a copy of algorithm 2) to the meta-algorithm. In addition, due to the preceding ambiguities, it causes confusion with $\\eta_k$ defined in Algorithm 1 given Theorem 1 does not specify learning rate and time horizon for $\\mathcal{A}_k$. \n\nAlgo 2: iterates are inconsistent, varying between $w$ and $x$. Also Lemma 4 is a general analysis for Algo2, it should quote algorithm 2 in stead of using `The EXP-3 algorithm`, which is even not consistent with the algorithm name itself.\n\nLemma 2: In the main text, given the context of Algorithm 2 $\\mathcal{A}_k$, $w_t(i)$ is the probability for picking the $i^{th}$ arm. This is $v(t,k)_i$ defined in Algorithm 1. Not what was stated as the weight of the ith expert at time $t$. Due to this confusion, it is hard to see $C = 2\\log T$. It only can be deduced after reading appendix at page 14. \n\nIt is also necessary to show the expressions of regret of expert k: $ \\sum_{t \\in I } \\hat{ \\ell}_t^T v(t,k) -  \\hat{\\ell}_t^T x^* $ in the main text instead of the appendix. Then it will become apparent why the quantity in Step 3 is needed, because `the regret of the Meta-learner` does not justify the quantity of interests in step 3.\n\nAppendix B: pg15  first line. $\\mathcal{A}_1$ by definition in Algorithm 1 line 3 optimizes interval with length of $2$. The index needs to be fixed.\n\nAppendix C: paragraph starting after the first equation, 'Algorithm 3 is feasible'", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)