Trading Off Resource Budgets For Improved Regret Bounds
Authors: Thomas Orton
Damon Falck
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Learning
Bandit Algorithms

Abstract: In this work we consider a variant of adversarial online learning where in each round one picks $B$ out of $N$ arms and incurs cost equal to the $\textit{minimum}$ of the costs of each arm chosen. We propose an algorithm called Follow the Perturbed Multiple Leaders (FPML) for this problem, which we show (by adapting the techniques of Kalai and Vempala [2005]) achieves expected regret $\mathcal{O}(T^{\frac{1}{B+1}}\ln(N)^{\frac{B}{B+1}})$ over time horizon $T$ relative to the $\textit{single}$ best arm in hindsight. This introduces a trade-off between the budget $B$ and the single-best-arm regret, and we proceed to investigate several applications of this trade-off. First, we observe that algorithms which use standard regret minimizers as subroutines can sometimes be adapted by replacing these subroutines with FPML, and we use this to generalize existing algorithms for Online Submodular Function Maximization [Streeter and Golovin, 2008] in both the full feedback and semi-bandit feedback settings. Next, we empirically evaluate our new algorithms on an online black-box hyperparameter optimization problem. Finally, we show how FPML can lead to new algorithms for Linear Programming which require stronger oracles at the benefit of fewer oracle calls.

Trading Off Resource Budgets For Improved Regret Bounds
Damon Falck" University of Oxford damon. falck@gmail...... com com
Thomas Orton" University of Oxford thomas. ortonêes. ox ac uk
Abstract
In this work we consider a variant of adversarial online learning where in each round one picks B out of N arms and incurs cost equal the minimum of the costs each arm chosen. We propose an algorithm called Follow the Perturbed Multiple Leaders (FPML) for this problem, which we show (by adapting the techniques of Kalai and Vempala (005) achieves expected regret O(T ø (n(N) F+ over time horizon 7 relative to the single best arm in hindsight. This introduces a trade-off between the budget B and the single-best-arm regret, and we proceed investigate several applications of this trade-off. First, we observe that algorithms which use standard regret minimizers as subroutines can sometimes be adapted by replacing these subroutines with FPML, and we use this generalize existing algorithms for Online Submodular Function Maximization [Streeter and Golovin 2008] in both the full feedback and semi- mini-bandit feedback settings. Next, empirically evaluate our new algorithms on an online black-bor hyperparameter optimization problem. Finally, show how FPML lead to algorithms for Linear Programming which require stronger oracles at the benefit of fewer oracle calls.
Introduction
Adversarial online learning is a well-studied framework for sequential decision making with numerous applications. In each round t 1..... T. an adversary chooses hidden cost function c; : [0. 1] from set of arms A to costs in [o. 1]. An algorithm must then choose an arm 0₂ A. and incurs cost (a:). the full feedback setting (Online Learning with Experts (OLwE)), the algorithm then In the purtial feedback setting (Multi-Armed Bandits (MAB) the
observes the cost function algorithm only observes the incurred cost ot (az). The objective to find algorithms which minimize regret, defined as the difference between the algorithm's 's cumulative cost and the cumulative cost of the single best arm in hindsight.
In this paper we consider search-like variant of these problems where in each round one can pick subset of arms S, C A with |S| 2 and keep the arm with the smallest cost. This variant appears naturally in many settings, including:
1. Online algorithm portfolios [Gomes and Selman 2001] In each round t, one receives problem instance 2,, and can pick a subset S, A of algorithms run in parallel solve Tt. For example, could be a boolean satisfiability (SAT) problem, and A could be collection of different SAT solving algorithms. We let (a = 0 if a solves x; and (a = otherwise. Then if any E S; finds solution to we incur 0 cost in this round. Another example is online hyperparameter optimization (see Section
'qqual contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2. Online bidding [Chen et al. 2016a In each round f, an auctioneer sets up a first-price auction for bidders S, C A. Each bidder a E A has a price 1 1- ca(a) they are willing to pay. and the auctioneer receives maX 1 ca(a) = 1 mitlees (a), and so maximizing revenue is equivalent to minimizing costs.
3. Adaptive network routing [Awerbuch and Kleinberg 2008 In each round t, a network router receives a data packet Z; and can pick a selection of network routes St C A to send to its destination via in parallel. Let the cost o₂ (a) of route be the total time taken for 2 to reach its destination via a; the router receives cost min.es, (((a) equal to the smallest delay.
In many applications the budget B is restricted resource (c.g. compute time or number of cores) we would like to keep small; this paper studies how one can trade off budget resources for better guarantees on the standard regret objective.
Formally, for any randomized algorithm ALG which chooses subset St C A in round f, and thus incurs cost e, (S,) := minggs, C2 (a), define
T Σ (S.))
T Ea(at)
(ALG) = max
E OT
min EEA
to be the worst-case expected regret of ALG relative to the single best arm in hindsight, where the expectation is with respect to the randomness of ALG What guarantees can we give Ri function of our budget B? In the full feedback setting when = 1, this is the standard OLwE problem where it is known that RG D(VT) and there are algorithms which achieve Rr S 2v/Tm((NV [Lttimore and Szepesvári 2020 where N = |A]. When B N the algorithm which chooses S: = A in each round achieves R2 = O. But what bounds on F2 can be achieved in the intermediate regime when 1 B < N? To the best of our knowledge this question has not been directly answered by any prior work.
1.1 Contributions
Theoretical results: We present new algorithm for this learning problem called Follow the Perturbed Multiple Leaders (FPML.), and show that the full feedback setting Rř (FPMI.) S O In(N) ) ) This allows for direct trade-off between the budget B and the regret bound (in particular, allowing resources B Z (ln(TT) leads to regret constant in T) and recovers the familiar ( / In()) bound when B = 1. We then show that the semi-bandit feedback setting (where the algorithm finds only the costs of the arms it chooses) this bound can be converted to R9 (FPML) I O(T B (K In(N)) #4x) if one has unbiased cost estimators bounded in [0, K].
We also consider the more general problem of Online Submodular Function Maximization (OSFM), for which prior work gives an online greedy algorithm OG (Streeter and Golovin 2008 When given budget of per round, OG achieves regret O DTVB (N)) with respect to where OPT(B) is the performance of the best fixed length-B schedule (see Section 3 for a formal definition of OSFM). Note that in this guarantee the regret benchmark is a function of the algorithm budget. By replacing a subroutine in OG with FPML, we generalize OG to new algorithm OG Unlike OG, OGyyrri able to give regret bounds against benchmarks which are decoupled from the algorithm budget. This allows one to more easily quantify the trade-off of increasing the budget against a fixed regret objective. As a special case, we are able to show that having a budget of B B' ['I[TT)²1 per round allows one to achieve regret O(B' In(T") In([V) with respect to OP)(B'). One interpretation of this result is that if you are willing to increase your budget (e.g. runtime) by factor of In(T) 2 you are able to improve your performance guarantee benchmark from -1-ea (1- OPT(BB) to OPT(B'). Likewise, your regret growth rate in terms of the number of rounds changes from (VTT) to ([n(T)).
OPT(BB,
Finally, in Section 5 we show how use FTML to generalize technique for solving linear programs assuming access to an oracle which solves relaxed forms of the linear program. To obtain an s-
approximate solution to the linear program requires (2) (4p) R=1 (1 + In(n)) oracle calls, where
'Here we consider an oblivious adversary model for simplicity, but we believe the results of this paper carry through to adaptive adversaries well.

---

the parameters p) are related to the power of the oracle and n is the number of linear constraints. The case B coincides with known results.
Experimental results: We benchmark both FPML and OGiybrid on an online black-box hyper- parameter optimization problem based on the 2020 NeurlPS BBO challenge [Turner et al. 202T]. We find that both these new algorithms outperform OG for various compute budgets. We are able to explain why this happens for this specific dataset, and discuss the scenarios under which each algorithm would perform better.
Techniques: Minimizing Ry is an important subroutine for large variety of applications including Linear Programming, Boosting, and solving zero sum games [Arora al.] 2012 Traditionally an experts algorithm such as Hedge [Littlestone and Warmuth 1994]. which pulls a single arm per round, will be used as subroutine minimize Ry.. We highlight how in the cases of OSFM and Linear Programming, one can simply replace a single arm Rt minimiziig subroutine with FPML and get performance bounds with little or no alteration the original proofs. The resulting algorithms have improved bounds (due to improved bounds on R2 when B > 1) at the cost of qualitatively changing the algorithm (e.g. requiring larger budget more powerful oracle). This is significant because it highlights the potential of how bounds on R7 when B > 1 can lead to new results in other application areas. In Section 2.1 we also highlight how the proof techniques of Kalai and Vempala [2005] for bounding R7 in the traditional experts setting can naturally be generalized to the case when > 1, which is of independent interest.
1.2 Relation to prior work
One can alternatively formulate more gewe consider as receiving the maximum reward rt(a) = 1- (a) of each arm chosen instead of the minimum cost. In this maximum of rewards formulation, the problem fits within the OSFM framework where (a) all actions are unit-time and (b) the submodular job function is always maximum of rewards. The rewards formulation of the problem has also been separately studied as the K-MAX problem (here K = B) Chen et al. (2016a]. In the OSFM 2008 give an online greedy approximation algorithm which guarantees E[(1 e ()PT(BB Rewardy] I O(TTB In(N)) in the full feedback adversarial setting, where (B)(B) is the cumulative reward of the best fixed subset of B arms in hindsight, and Rewardy is the cumulative reward of the algorithm. A similar bound of ( In (N)) can be given in a semi- feedback setting. Conversely in the full feedback setting, Streeter and Golovin (007] shows that any algorithm has worst-case regret E E(OPT(B) the maximum of rewards in each round. Chen et al. 2216aa] study the K-MAX problem and other non-linear reward functions in the stochastic combinatorial multi-armed bandit setting. Assuming the rewards satisfy certain distributional assumptions, they give an algorithm which achieves distribution- independent regret bounds of [E[(- (B) Rewardy] < O(VTBN In(T)) for E > 0 with semi-bandit feedback. Note however that we consider the adversarial setting in this paper.
setting, Streeter and Golovin
Rewardy > 22 C (NNN N//B)) when one receives
More broadly, these problems fall within the combinatorial online learning setting where an algorithm may pull a subset of arms in each round. Much prior work has focused on combinatorial bandits where the reward is linear in the subset of arms chosen, which can model applications including online advertising and online shortest paths (Cesa-Bianel) and Lugosi 2012] Audibert al. 2014 Combes et al., 2015). The case of non-linear reward is comparatively less studied, but having non-linear rewards (such as max) allows one to model wider variety of problems including online expected utility maximization (Li and Deshpande 2011 Chen et al. 2016a]. As some examples of prior work in the stochastic setting. Gooalan et al. 2014 uses Thompson Sampling to deal with non-lincar rewards of functions of subsets of arms (including the max function), but requires the rewards to come from a known parametric distribution. [Cen et al. (2016b) considers a model where the subset of arms pulled is randomized based on pulling a 'super-arm and the reward is non-linear function of the values of the arms pulled. In the adversarial setting, Han et al. [2021] study the combinatorial MAB problem when rewards can be expressed as d-degree polynomial.
In contrast to prior work which focuses on giving algorithms which compete against benchmarks which have the same budget as the algorithm, this work is concerned with the trade-off between regret bounds and budget size. We focus on giving regret bounds against OPT(1), and we use this result in Section 3 to get regret bounds against OPT(B') for B' < B in OSFM. Decoupling the regret
3

---

benchmark OPT(BB) from the algorithm budget B can be useful when one would like to control the strength of a regret bound against a specific target (B) for theoretical applied reasons. For example Arora et al. [2122 survey a wide variety of applications which rely on bounding Rr. but bounds such as [1 e (oP]O))(B)B) Rewardy] I O(v O(VTBIn(N)) do not immediately imply
useful bounds on (PT(1) Rewardy.
Follow the Perturbed Multiple Leaders
We begin by considering the full feedback setting. We first check that allowing the algorithm to choose > I arms per round, while only competing against the best single fixed arm in hindsight, does not make the problem trivial. We do this by showing that any deterministic algorithm with budget B < still achieves linear regret in the number of rounds. This achieved by setting (a(a) if St, (a) = 0 otherwise.
Proposition 1. the full feedback setting, any deterministic algorithm with arm budget B S N per round has worst-case regret Rÿ 2 21 N)T.
Likewise, can be shown that the algorithm which chooses a uniformly random subset of B arms in B
each round has worst-case expected regret at least 7(1 N ) (achieved by having one arm have cost across all rounds and every other arm having cost 1). These two observations show that any solution for achieving sub-linear regret in T requires randomization which depends in some non-trivial way on the prior observed costs even when B >
2.1 Generalizing Follow the Perturbed Leader
Choosing the current lowest perturbed-cost arm in each round, Follow the Perturbed Leader (FPL) [Kalai and Vempala 2005]. is well-known regret minimization technique which achieves optimal worst-case regret against adaptive adversaries in the OLwE setting. In this section we generalize the FPL algorithm to Follow the Perturbed Multiple Leaders (FPML). In each round, FPML perturbs the cumulative costs of each arm by adding noise, and then picks the B arms with lowest cumulative perturbed cost. This is precisely FPL when B 1. We show how one can extend the proof techniques of Kalai and Vempala (2005) in natural way to prove that FPML achieves worst-case regret (7P(FFL) < 2T (1 In(N) म
Algorithm 1 FP,L((,))
Require: N 2 B > 1 > O. Initialize the cumulative cost Co(a) + for each arm a A.
for round é =,,,..,; do
1. For each arm A, draw noise perturbation pe(a) ~ Exp.
2. Calculate the perturbed cumulative costs for round - (a) + (a) - pe(a).
3. Pull the B arms with the lowest perturbed cumulative costs according to C, Break ties arbitrarily.
4. Update the cumulative costs for each arm, C.(a) < (c-1(a) + c()) end for
Theorem 2. In the full feedback setting, where S. A is the subset of arms chosen by FPML in round t, we have:
T
(1+ (1+In(N)) In(NN)
(1 - BB Σ (S.)) - min Σ Ealaa))
max
E.
Cr
a*EA
1=1
1=1
In particular, for = ((n(N) + 11BT)1/(++1) we have
RG (FPML) < 2T (1 (1
The proof follows the same three high level steps which appear Kalai and Vempala 2005 for FPL. but we extend these ideas to the case where B > 1. We first observe that the algorithm which picks the B lowest cumulative cost arms in each round only incurs regret when the best arm in round not one of the best B arms in round f 1.

---

Lemma 3. Consider fixed sequence of cost functions eT. Let ai be the j lowest cumulative cost arm in hindsight after the first t rounds, breaking ties arbitrarily. Let S = {a j E [B]} be the set of the B lowest cost arms at the end of round t - 1. Then for each i E [T].
R = Σ ((()))
min EA
celaa) S Σ
1aj &
1=1
and R: - R2,1 1aa E Sy--
This is a generalization of the familiar result that when B = 1, following the leader has regret bounded by the number of times the leader is overtaken [Kalai and Vempala 2005].
The second step argue that if the cumulative costs are perturbed slightly, it becomes unlikely that the event {a & 5i} will occur. One way to see this is as follows: fix a round t, and let C²-1 (a) be the cumulative cost of at the end of round & 1- 1. Let M == C C Then every a E S has (a) s M. If is also true that Cr-1(a) < M ((a) for any a S then the event {aī" & S cannot occur. This because C,(a) < - c(()) + ce(a) = -M but any a' E A St has Ca(a') 2 M, so a' * a..1 If we had initially perturbed each C by subtracting independent exponential noise p(a) Expp then conditional on M the event (Ct-1(a) < . 1 caa)) is jointly independent for each a E S,. Moreover the probability of this inequality not holding is equal to Pip(a) < + ca(a))p(a) p(() 2 'ij for v equal to the unperturbed cost of a at round - minus M, which is bounded by (a)(a) (due to the memorylessness property of the exponential distribution).
Lemma 4. Fix sequence of cost functions CI....,CT. Let C:(a) Ei= (a and Ca(a)) Ci(a)- - ((a) be the perturbed cumulative cost of arm the end of round where p(a) e Exp. Let āe be the jth lowest cumulative cost arm in hindsight after the first rounds using these perturbed costs, and let S = (6 1 E [B]}. Then
E a & 5t]
SE <<(< ((())
Again, when B = this argument and bound coincides with the argument given by Kalai and Vempala 2005].
The final step is to combine Lemmas 3 and to argue that FPML achieves expected regret at most E e Σz_ - (5;)) with respect to the perturbed cumulative cost Ör. Since maxac Elp(()) <
I+Ia(N) we can argue we also achieve low expected regret with respect to the unperturbed cost Cr. In the setting of this paper, drawing new random perturbations pt(a) in each round is not strictly necessary (we can take Pe (a) = Pı (a) for t >>> 1), but it necessary to achieve regret bounds when cost functions can depend on prior arm choices of the algorithm (the adaptive adversarial setting). In the setting of this paper where the costs are fixed, the expected regret in either case is the same.
Probabilistic guarantees: One advantage of this proof technique is that the regret is bounded using the positive random variable ΣT1 1 à & 5; This means that one can apply methods like Markov inequality to give probabilistic guarantee of small regret, which is substantially stronger than saying the regret is small in expectation.
Comments on settings of parameters: When B = 1 we recover the standard O VTTTlnn TTT((N) regret bound for the OLwE problem. For B > 1, the regret growth rate function of the number of rounds is T particular, when B ((I(T)) grows slowly with the number of rounds, the expected regret becomes (In(N)) and does not grow with the number of rounds T. If we use a tighter inequality in the proof of Lemma 4 is possible to get constant expected regret when B- In(T)) (n(A) grows slowly with the number of arms and rounds.
Lower bounds: standard technique for constructing lower bounds in the online experts setting with B = 1 is to consider costs which are i.i.d. Bernoulli(p) [Lattimore and Szepesvári, 2020 Unfortunately this technique fails when B because the expected cost of the minimum of B i.i.d. Bernoulii random variables is generally smaller than the expected cost of the best arm in hindsight
5

---

unless is very close to 1. We are able to show very weak lower bounds in the full feedback setting of K ([)) for constant B and T (l)n(N)). but there is a substantial gap between this and the upper bound. We think constructing stronger lower bounds is an interesting problem for future work which may require new analysis techniques.
The semi-bandit feedback setting is a form of partial feedback where the algo- rithm only observes the individual costs of the arms pulls. It can be shown that passing unbiased cost function estimates to FPML results in a similar regret bound in the semi-bandit feedback setting; the result specific to FPML, and using unbiased cost functions does not generally work for any Riz-mnimizzng algorithm when B > because of the non-linearity of the cost function. In the case of FPML this is not an issue because the same bounding technique using Lemma hoolds in expectation when using unbiased cost estimators. A naive way to generate unbiased cost estimates in this setting is to use an additional arm to uniformly sample costs; in Section $ we explore geometric sampling Neu and Bartók 2013 for getting unbiased cost estimates which effective in practice.
Partial feedback:
Proposition 5. Define the algorithm FPML- "PMI-partial which simulates FPML, passing it unbiased cost estimates & [0, K] at round t E [T] and copies the arm choices of FPML. Then we have
R7 (FPML-parria)) S In(NN/E+ T(1 e- KeyB. For E
[I(N) TK
#+1
R4 (FPML-partial) S
O (KI(NN) )
3 Generalized regret bounds for Online Submodular Function Maximization
Streeter and Golovin 2008 considered the more general problem of Online Submodular Function Maximization which captures a number of previously studied problems as special cases. For the sake of emphasizing the key ideas, we restrict attention the full feedback setting where each action has unit duration. The OSFM problem in this setting is as follows:
Definition 1. Define a schedule to be a finite sequence of actions E A, and let S be the set of all schedules; the length ((S) of schedule S E S is the number of actions it contains. Define job to be a function f S + j0, 1] such that for any schedules S1, S2 E S and any action a E A:
1. f(S)) S f($ e S2) and (S2) $ f(1 S2) (monotonicity):
2. f(S @ S2 e (a)) fS1 @ S2) < f(S @ (a)) f(S1) (submodularity).
Definition 2 (Online Submodular Function Maximization). The problem consists of a game with T rounds. We are given some fixed B and at each round E [T] we must choose a schedule S₁ E S with E(S.) < B to be evaluated by job ft which is only revealed after our choice. The goal is to maximize the cumulative output Reward, := ΣT fc(S.).
propose an online greedy algorithm OG which achieves the guarantee (1 e (OPT(B) Rewardy < O( DDVBBlln In(N) in expectation, where (B) is the cumulative reward of the best fixed schedule of length B in hindsight. In this section we explain how to use FPML to extend their algorithm to allow a trade-off between budget resources and regret bounds.
Streeter and Golovin 2008
The algorithm OG has two key ideas. Suppose that we start with an empty schedule So = 0. The first idea is that we knew fi...., , fr in advance, we could greedily construct S; == S + (arg max,, EA Et= f + (a+) (1)) for = 1,..., B, where is the best greedy arm in hindsight for greedy round i. It can be shown that submodularity then implies (1 -e O < ET_ [(S).. Since we don't know /I....,fr fI in advance, the second idea is to run B copies of Rd regret minimizer, where the 7th copy tries to compete with achieving the same improvement of cumulative reward as the best fixed greedy action a, in hindsight. The regret bound on the 7th copy with respect to the best greedy arm in hindsight is O (VTTln In N); across the B copies one can show the net regret compared to the offline greedy solution is bounded by O(VTB In N), which is where
More formally: El(xx() Fi-1] = ce()) where Ft-1 the o-algebra generated by all the randomness up to and including round f 1.
In their original problem definition actions may each have different associated duration.

---

the final bound comes from. In summary, OG works as follows: for each round E [T], run B greedy rounds. In greedy round i I..... .......... B. pull the arm of proposed by the 1th black box R minimizer, set St, == St,i- + (af). and feed back the greedy rewards rr,a (a) = ( + (a)) (S to the 2h black box.
We propose a hybrid version of OG, called OGyybrid. which for any budget B allows us compete asymptotically well against OP)(B') for any chosen B' I B/ (T))... The algorithm OGhyrri is based on the following two changes OG:
1. Instead of having B greedy rounds, we have B' (T) greedy rounds. One can show that the extra factor of (T') allows one to drop the (1 - ") term in the regret bound.
2. Instead of running one-arm-pun som-pulling RS minimizer in each greedy round, we run FPML which pulls /B B' [T"] arms. This allows us to improve the regret bound for each of the B' IT) R7- -i-iimiiiesss and directly translates tighter overall regret bound.
Besides these two changes, the algorithm is identical to that in Streeter and Golovin 2008
More generally, let OGhybria [B B) denote the algorithm where each FPML box has a budget of B and there are B/ B greedy rounds, so that the total number of arms pulled in each round is B. This algorithm is a hybrid of OG and FPML in the sense that OGyybria (B. is OG with Follow the Perturbed Leader the -ii-iimmigg subroutine. On the other hand, OGnybrid (B, B) is FPML. Varying B allows to interpolate between these algorithms by varying the budget we give to the FPML subroutines.
On technical note, because slight strengthening on the monotonicity condition which is common to many practical applications including the experiments
pulling B > arms for each greedy choice, require
consider in the next section:
Assumption 1. In addition monotonicity and submodularity each f [0, 1] also satisfies f(S e S2 + S3) 2 f(S @ S3) for any schedules St, S2, S3 S.
We then give the following bounds:
Theorem 6. For any choices of B', B, under Assumption and with budget B == =BB' (TT)), algorithm OGnybria B, B) experiences expected regret
O B' In(T)T In(N) BN)BB(B
relative the best-in- -iindds-iind fixed schedule of length B'. In particular, if [[n[TT)] (and so B = B3 [In the regret is bounded by O In(T) In(N)).
This bound allows us the flexibility of trading off schedule budget B for how tightly would like to compete with the best fixed schedule of length B' < B in hindsight.
Partial feedback: Streeter and Golovin [2008] extend their algorithm to handle partial feedback by replacing the RS regret minimizers with the bandit algorithm Exp3 [Auer et al.) 2002] which only requires feedback on the arms which are pulled. Likewise, one can replace FPML. with FPML. partial in OGnybrid to get an algorithm which gives regret bounds in a semi-bandit feedback setting (where we can observe (S) for any schedule consisting of actions which were pulled in round t).
We empirically compare the partial feedback versions of OG and OGiybrid in the next section.
4 Experiments: online hyperparameter optimization
The problem of black-box optimization where where hidden function is to be minimized using few evaluations as possible has recently generated increased interest the context of hyperparameter selection in deep learning (Snoek et al. 2012 Liu et al. 2020b Bouthillier and Varoquaux] 2020]. As result, the 2020 NeurlPS BBO Challenge Turner et al.) 2021 invited participants' optimizers to compete to find the best possible configurations of several ML models on a number of common datasets, given a limited budget of training cycles for each. One of the key findings was that
sophisticated new algorithms normally outperformed average by techniques that ensemble
7

---

Table 1: Experimental results for B 6 and 4.
B 6
Algorithm
Mean Reward
StD
(
0.901
NA
FPML-partiaa (6)
0.888
0.0072
Ghybria (6, 3)
0.836
0.0111
Ghyrii (6, 2)
0,814
0.0143
Ghybrid (6, 1)
0.785
0.0137
OG
0.767
0.0157
B = 4
Algorithm
Mean Reward
StD
(4H(4)
0.836
NA
FPML- FPML-partial 4)
0.813
0,0108
Oyyrrii
0.756
0.0149
Ohybrri (4,
0.716
0.0178
(G(4)
0.689
0.0151
existing methods [Luu et 2020a i.e. optimizers tend have varying strengths and weaknesses that are suited to different task types. In scenario where many hyperparameter selection problems are be processed (e.g. in data center) and limited computing resources are available, it may thus be desirable to learn over time how best to choose B optimizers to apply independently to each problem (e.g. to run in parallel on B available CPU cores). This is a natural partial feedback application of bandit algorithms that pull multiple arms per round and receive the best score found across the optimizers which are run.
4.1 Experimental setup
We follow a similar approach to the NeurIPS BBO Challenge; the optimization problem at each round E [Z'] is to choose the hyperparameters of either a multi-layer perceptron (MLP) or lasso classifier for one of 184 classification tasks from the Pembroke Machine Learning Benchmark OOssn et al. 2017 (so T 368). At each round the bandit algorithm must select B Bayesian black-box optimizers from choice of 9 to run in parallel on the current problem; the received reward for each optimizer was calculated as [0, -orrmalleee measure of where the best training loss attained
sits between (a) the expected best loss from a random hyperparameter search and (b) an estimate of the best possible loss attainable (the same approach used by the Bayesmark package [Uber 2020)) ) Rewards are only observed for the optimizers which are run -semi-bandit feedback). For each budget level B = 1, ..., 6, we a benchmarking study comparing the performance of the following bandit algorithms in this setting: (1) UPMM--partial [3) from Section 2.1 using geometric sampling [Neu
and Bartók 2013 to construct unbiased cost estimates (see appendix for details). (2) OGnybrial [B B) from Section with Fartial as subroutine. We do this for varying values of B to see how performance changes. (3) OG B), the partial feedback version the original online greedy algorithm from Sttretter and Golovin 20088 We benchmark performance against BIH B), the score of the Best fixed subset of size B Hindsight. In all cases the s parameter for the bandit subroutines FPML-partial and Exp3 was set to their theoretically optimal values given B, N and T without any fine-tuning (for FPML-partial we use Proposition (5). We run each algorithm setting 100 times to estimate the mean and standard deviation of the performance.
4.2 Results and discussion
As expected, OGhyhria [B 1) has very similar performance to OG(B) in all cases because they implement essentially the same algorithm (the difference being due different choices one-arm pulling R7 minimizers, FPML-partial(() and Exp3). However, we notice that in every instance,
Herr rewards be consistent with the setting of Online Submodular Function Maximization.

---

allocating more budget to the FPML-partial subroutine in OGnybrid (increasing B) while keeping the overall budget constant improved the average score performance. This means that Ghyyrii was always at least as good as OG for all parameter settings, and that FPMI--prrtill outperformed both of these algorithms in all cases. This perhaps surprising. because OG and OGhyhrid are designed to achieve low regret against the stronger benchmark of the best subset of B' 2 1 arms in hindsight, while FPML-partial only designed to achieve low regret with respect to the single best optimizer in hindsight. Towards explaining this observation, we notice that for this particular dataset, the best subset of B arms in hindsight happens to be very similar to the set the individual best performing B arms in hindsight, and FPML achieves low regret with with respect to the latter (see Proposition below). This raises the interesting question of when certain regret objectives might be better than others in practice.
Proposition 7. In the full feedbuck setting, the expected regret of FPML with arms relutive to the set of the individual best performing B arms in hindsight is at most [1 - -B-1- In\(A\/Bi//+++ T(1- ((1-exp(-eB)) exp(-=B)).
Synthetic tasks: We also evaluated these partial feedback algorithms in a number of synthetic environments, exploring examples where (a) the optimal subset of B arms, (b) the subset of B arms chosen greedily, (c) the individual best performing B arms, perform in various ways relative each other; OG approximates (b) and FPMI.-arrtial approximates (c), so the closeness of either of these to (a) determines each algorithm's 's performance. We find that problem instances exist where OG outperforms FPML-partial and vice versa. See the appendix for details.
5 Connections to other problems
Arora et al. solved using& R7. minimizing subroutine in the standard OLwE setting with B 1. The purpose of this section is to highlight the relative ease with which algorithms like FPML can sometimes be plugged in to existing algorithms which use an Rł minimizer as black box subroutine, with little or no alteration to their proofs of correctness. We already saw an example of this in Section 3 where the regret minimizing subroutine was replaced with FPML. The resulting algorithm gave improved regret guarantees at the cost of higher budget requirements, without changing the structure of the original proof given in SStretter and Golovin 2008 In this section we take Linear Programming as an example, and illustrate what its plug-in a algorithm looks like. We are unsure whether the resulting algorithm is necessarily useful because it requires a more powerful oracle than the one supposed in Arora et al. 2012]; but we do think that exploring the algorithms which result from this plug-in -n technique more broadly may be an area interest for future work.
2012 surveys a wide variety of algorithmic problems and shows how they can all be
5.1 Linear Programming
We consider the Linear Programming (LP) problem from Arora al. 2012 Given a convex set P. an n X m matrix A with entries in I. and a vector b E IK, the task is to find an r E P such that Az > b, or determine that no such exists. We assume that we have an oracle which solves the following easier problem (where A, denotes the hhh row of A):
Definition 3. A (p, bb-buudeed oracle for p 2 0 an algorithm, which when given a joint distribu- tion d over [m)] B, finds an P such that
min
A& be 2
(1 Jwdd
LiE (i
or determines that no such x exists. If an x is found, then Vi E [nt], |A,x bil S p.
When B this is simplified version of the oracle defined Arora al. 2012 and it is equivalent to an oracle which can find x E P which satisfies single linear constraint d Az 2 d b (when viewing d as a vector in RR), When B = n, solving this problem can be as hard as solving the original LP problem by jointly choosing i, to have probability mass I on the 7th linear constraint.
1 < B < n represents an intermediate regime where the oracle needs to find an which 'fools' the
joint distribution d. For simplicity, assume that we have access to an oracle which takes input

---

bounded cost functions eI..... and outputs the joint distribution d, over arms of FPML in round after observing cost functions .I....: Ct-1. In practice such an oracle could be achieved by e.g. sampling arm draws from FPML to approximate d,.
Proposition 8. Let > O. Suppose there exists a (p. B)-bounded oracle for the feasibility problem
Er P..t. Ar 2 b. Then there an algorithu which either finds an z E s.t. Vi [n], Arr Z b. ---, E, or correctly concludes that the problem is infeasible. The algorithm makes at most T =
(t) (4p) R+1 " (1 + In(n)) calls to the (p, B) B--bondded oracle and FPML oracle, with total
runtime of (T).
The proof technique for general 2 essentially identical to the proof given in Arora 2202 for B = 1 except that we are able to use stronger bound on R (see appendix for details).
Comment on bound:
When B = 1, we require )2) steps in order to find an which is s-close to satisfying the constraint. The (1)² term comes from the fact that when B the average regret for OLwE is ((VT/T) = T so takes T 2 ( steps for the average regret to be S s. The accuracy parameter is therefore common in many applications which use OLwE with = as subroutine (including Boosting [Schapire 1990] and solving zero sum games
quadratic dependence
Frrennd and Schapire 1999 ). For general B 2 1, we only require ((2) **) steps (suppressing terms related to n and
p) for the average regret to be S e. In the case of Linear Programming, this
at the expense of requiring stronger oracle for the problem.
6 Conclusion
This paper presented a new algorithm, Follow the Perturbed Multiple Leaders, which allows one to directly trade off budget constraints for bounds on regret. We showed how FPML can be used as subroutine to generate new algorithms for Online Submodular Function Optimization and Linear Programming which trade off resources and oracle power for improved performance guarantees.
We also highlight a number of areas for future work: (a) Lower bounds: Can we reduce the gap between the upper and lower bounds of this problem? Improving lower bounds may require new techniques than are traditionally used in the OLwE setting. (b) Plug-in algorithms: Are there other cases where using FPML in existing algorithms can lead new theoretical results? And when are these new algorithms practically useful? (c) Which regret benchmarks are useful in practice: The experiments of Section T showed that algorithms designed minimize regret with respect arm can sometimes in practice outperform algorithms designed to minimize regret with respect to the stronger benchmark of the best subset of arms. Are certain regret objectives better than others in different practical applications?
single
References
Jason Ansel, Shoaib Kamil, Kalyan Veeramachaneni, Jonathan Ragan-Kelley, Jeffrey Bosboom, Una-May O'Reilly, and Saman Amarasinghe. Opentuner: An extensible framework for program autotuning. In Proceedings of the 23rd international conference Parallel architectures and compilation, pages 303-316, 2014.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory Comput.. 1(1):121-164 2012. doi: 10.4086/oc.20112.v00... URL https:://do org/10. 4086/ toc. 2012. v008a006
Jean-Yve Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial op- timization. Math. Oper. Res., 39(1)331445, 2014. doi: 10.11887/mo0r.2013.59988 URL
httpp://doi.orgge www//0../100... 1287 /mormmoooo///////////oo 2013. 0598
Peter Auer, Nicolo Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-71 2002.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences. 74(1)997-114 2008.
10

---

James Bergstra, Brent Komer, Chris Eliasmith, Dan Yamins, and David D Cox. Hyperopt: a python library for model selection and hyperparameter optimization. Computational Science & Discovery, 8(1) 8(1):014008, 2015.
Xavier Bouthillier and Gaël Varoquaux. Survey of machine-learning experimental methods at NeurlPS2019 and ICLR2020. PhD thesis, Inria Saclay Ile de France, 2020.
Nicolò Cesa- Bianchi and Gábor Lugosi. Combinatorial bandits. J. Comput. Syst. Sci., 78(4):1404- 1422, 2012. doi: 10.1016/j. jos.:/f...ss.222..1.... 2012.01.00. URL 01.001
2012
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial multi-armed bandit with gen- eral reward functions. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1651-1659, 6a. URL https: ppwoee/din/ocooo...ooooo..a wwwpeeeddiinnnnnnuui..ee httpaippppccppppe//20/00 /aaaaaaaa99446652222559222222233
Abstract html
Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. J. Mach. Learn. Res., 17:50:1 1-50:33, 2016b. URL
http:///mlr org/ httg:papprs//v1//// 298. html
Richard Combes, Mohammad Sadegh Talebi, Alexandre Proutière, and Mare Lelarge. Combinatorial bandits revisited. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances Neural Information Processing Systems 28: Annual Conference on Neural Information P Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2116-2124, 2015. URLLLttts::/prreeedagg .nerrie httpss.cccpppe///pppppp /tt.h///ccc2ff211ccceeeeeeeeebea Abstract. httml
David Eriksson, David Bindel, and Christine Shoemaker. pysot and poap: An event-driven asynchronous framework for surrogate optimization. arXiv preprint 1xXiv:1908.04400 2019.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Carla P. Gomes and Bart Selman. Algorithm portfolios. Artif. Intell., 126(1-2):43 2001. doi: 10. 016/50004433000000000000
(0000000000000000000000000000000 00081-3
Aditya Gopalan, Shie Mannor, and Yishay Mansour. Thompson sampling for complex online problems. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 2/-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 100-108. JMLR.org, 2014. URL http::/pproceedingg///// mlr www.ppressseee vv2// press//332gopaalnn1 gopalan14 html
Yanjun Han, Yining Wang, and Xi Chen. Adversarial combinatorial bandits with general non- non-linear reward functions. In International Conference on Machine Learning, pages 4030-4039, PMLR, 2021.
Tim Head, MechCoder, Gilles Louppe, Iaroslav Shcherbatyi, fcharras, Zé Vinícius, emmalone, Christopher Schröder, nel215, Nuno Campos, Todd Young, Stefano Cereda, Thomas Fan, rene rex, Kejia (KJ) Shi, Justus Schwabedal, carlosdanielcsantos, Hvass-Labs, Mikhail Pak, SoMany User- namesTaken, Fred Callaway, Loie Estève, Lilian Besson, Mehdi Cherti, Karlson Pfannschmidt, Fabian Linzberger, Christophe Cauet, Anna Gut, Andreas Mueller, and Alexander Fabisch. scikit- optimizee/cikkit-pptiizz. v0.5.2, March 2018. URL https:://olt org 10. 5281/zenodo 1207017
Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71(3) 2005. doi: 2os06//..ss..2044.10.. URL https / //doi.org/// 1016/ jcss. 10044.0..00 016
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

---

Jian Li and Amol Deshpande. Maximizing expected utility for stochastic combinatorial optimization problems. Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 797-806 IEFF Computer Society, 2011. doi: 2000099/FCCS20111..3. URI. http.:ttss:///d ott.:://doooooo////oooooo org 10. 1109/FOCS 2011.33
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2): 212-261, 1994. doi: 10.1006/1mco.1999 1994.19999.999 URL http::ttt////o :/op:::://oi... ott.:oo..or/1...100000... iico0////icoooo 1994 JRt
1009
Jiwei Liu, Bojan Tunguz, and Gilberto Titericz. Gpu accelerated exhaustive search for optimal ensemble of black-box optimization algorithms. arXiv preprini arXiv:2012.0420) 2020a.
Zhengying Liu, Zhen Xu, Shangeth Rajaa, Meysam Madadi, Julio CS Jacques Junior, Sergio Escalera, Adrien Pavao, Sebastien Treguer, Wei-Wei Tu, and Isabelle Guyon. Towards automated deep learning: Analysis of the autodl challenge series 2019. In NeurlPS 2019 Competition and Demonstration Track, pages 242-252. PMLR, 2020b.
Gergely Neu and Gábor Bartók. An efficient algorithm for learning with semi-bandit feedback. In International Conference Algorithmic Learning Theory, pages 234-248, Springer, 2013,
Randal Olson, William La Cava, Patryk Orzechowski, Ryan J Urbanowicz, and Jason H Moore. Pmlb: a large benchmark suite for machine learning evaluation and comparison. BioData mining, 10(1):1-13, 2017.
Robert E. Schapire. The strength of weak learnability. Mach. Learn., 5:197-227, 1990. doi: 10.1007/BFO01 16037. UtLhttps::/
org/ 10. 10010007/BBB /000//F00111037
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Technical Report --U--1--7-171. Carnegie Mellon University, 2007.
Matthew J. Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference
on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11 1, 2008, pages 1577-1584. Curran Associates, Inc., 2008 URL https://t:////ptt 2 http:::///.ooocccn.....oom neurips cc/paper/2008
Abc html
Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Eero Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020. In NeurlPS 2020 Competition and Demonstration Track, pages 3-26. PMLR, 2021.
Uber. Bayesmark documentation, 2020. URL latest/index. httm:lliddx..mmmm
rew.thedocs...eoeeee iooen//
12


Reviews:
[{"review_id": "yZSYssf6gbp", "reviewer": "Reviewer_Gn74", "summary": "This paper considers a new learning with experts' advice setting where the learner could choose B (B\\geq 1) experts and suffers a minimal loss of the chosen exprets. The authors propose an extension of the classical FTPL algorithm for solving the problem, and the basic idea is to choose the top-K perturbed leader at each round. The authors show that the algorithm could trade-off between regret and B, which could reduces to minimax results when B=1 or N. Finally, the authors consider several extensions, including bandit feedback, OSFM, and experiments on real-world datasets.\n", "questions": "I’m not an expert in this area and I was wondering if the authors to clear some of my concerns: 1) what is the exact relationship between the problem considered in this paper and OSFM, and are there any existing methods can solve this problem? 2) Can the authors compare the regrets between OG and OG_hybrid?\n\nI think the authors should also cite the line of work about online submodular minimization, such as [Hazan & Kale., 2012]. \n\nHazan, E., & Kale, S. (2012). Online Submodular Minimization. Journal of Machine Learning Research, 13(10).", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThe proposed setting has a strong relationship with online submodular minimization, and online combinatorial minimization, but to my knowledge the introducing of budget is new and novel. \n\nThe proposed algorithm is a direct extension of the classical FTPL algorithm, and I am bit surprised to see that this version of FTPL (choosing the top K leaders) is not considered by any previous work. Although the proof is not so complicated, I think the idea is novel and the theoretical guarantees on the regret-budget trade-off is also interesting and novel.\n\nThe authors did a solid work and considered several extensions, including the bandit case, application in OSFM, and the also did several experiments to demonstrate the effectiveness of their methods. \n\n\nWeakness: \n\nIt would be great if the authors could get a B related lower bound. \n\nPresentation: in the introduction, the authors give a clear description of the OLwE with budget problem, and also the corresponding Top-K FTPL algorithm. However, the part related to OSFM (start from Line 60) is not easy to read, and I think the readers may have the several  questions, including what is the exact relationship between OLwE with budget and OSFM, and intuitively, What is “best fixed schedule of length B”, and what is the improvement of the proposed algorithm compared to OG in terms of the order of regret (something related to B)? \nI think a rewrite of Lines 60-65 may make the introduction easier to read.\n\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "pElKkgLL8uh", "reviewer": "Reviewer_2itn", "summary": "They propose a new online learning setting which is in each round $[S_t]$ arms are pulled but the learning algorithm only suffers the regret of the arm with the lowest cost among all the pulled arms. They propose a new learning algorithm, Follow the Perturbed Leader (FPL), for it. In addition, both theoretical and practical results are provided.\n\n", "questions": "see above", "limitations": "see above", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness: Comments on the writing:\nThere is no proper section stating the learning problem. Also, I do not understand the feedback model such as whether all arms in $[S_t]$ will be observed or not, based on their Algorithm~1.\n\nBased on my understanding, if all arms in $[S_t]$ are observed at the end of each round, it is more like graphical bandit setting that is shown in (From Bandits to Experts: On the Value of Side-Observations, Shie Mannor, Ohad Shamir, 2011). \n\nAlso, I believe adversarial online learning are quite understood. So, I do not think the proposed learning problem is challenging. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "e5ESkgcEa3a", "reviewer": "Reviewer_AB1a", "summary": "The paper studies a variant of adversarial online learning which has a particular trade-off between budget and regret bounds in adversarial online learning. Standard adversarial online learning is a sequential setting. In each round $t = 1, \\ldots, T$ the learner picks an action out of $N$ possible actions, suffers a loss, which is revealed to the learner afterwards. The goal is to control the regret, which the difference between the cumulative loss of the learner and the cumulative loss of the best fixed action. \nIn the budgeted version that is studied in this paper, the learner gets to choose a set of actions with cardinality $B$ each round and suffers the minimum loss of the actions in the chosen set. The definition of the regret does not change, which means that the learner gets more power compared to the standard version of the game. \n\nFirst, the authors analyse the full feedback setting and present a new algorithm, \\textit{Follow the Top Perturbed Leaders}, and its regret upper bound, which is $O(T^{\\frac{1}{1+B}}\\ln(N)^{\\frac{B}{1+B}})$. Then, they adapt this algorithm and its upper bound to the semi-bandit feedback setting. \n\nThe new algorithm is applied as a subroutine of an online greedy algorithm in Online Submodular Function Maximization. Interestingly, in this application the authors show that one can also prove bounds for a stronger notion of regret, namely against the best fixed set rather than against the best fixed action. Finally, they present experiments for online hyperparameter optimization problems in the partial feedback setting.", "questions": "What type of estimators should be used for the partial information setting and what type of regret bounds do such estimators give?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts\n\n    - The setting is well motivated. The list of possible applications in the introduction is extensive and the application to submodular optimization is elegant. The applications provided by the authors in section 5 of the paper are also relevant. \n    - The authors study the trade-off between budget and regret bounds both in the full feedback and semi-bandit feedback settings. For both settings, they provide the analysis of regret upper bounds, which clearly show how the trade off between budget and regret works in different settings.\n    - The analysis of the algorithm is a natural extension of the analysis of follow the perturbed leader and is well described. The analysis appears to be technically sound, although I have one minor comment, see below.\n    - The paper is well written given space constraints, although it can be a bit dense at times seemingly due to these space constraints. Particularly the section on submodular optimization was difficult to read because it seemed to be quite compressed. \n    - The theory is supported by providing experiments, both on a known public benchmark  and on synthetic data. The experiments even revealed some unexpected behaviour of the algorithms, leading to an interesting future research question. \n\nWeaknesses\n\n    - For me the main weakness of the paper is the partial information bound. While the generality is nice, it also does not seem to give the optimal rate in the standard bandit setting ($B=1$) and the best I can get is a $O(T^{2/3})$ bound, where I hide dependency on $N$. This also makes me believe that the approach does not give satisfactory results in the cases where $B>1$, although I do not have a point of reference for these cases. \n    - The authors show a lower bound only for the full feedback setting and as the authors acknowledge this result is weak. It would have been nice to have a stronger one, to better understand the nature of the problem. \n    - The authors provide a regret bound for \\textit{OG} which uses \\textit{Follow the Top Perturbed Leaders} as a subroutine in the full feedback setting, but they do not for the partial feedback setting. They do give a hint for the adaptation to the partial feedback setting and test its performance in the experiments, but it would have been a more complete work if they also provided the bound. \n    \nMinor comments\n\n    - In lines 156 to 165 I have trouble understanding the role of $S_t$ versus $S_t^*$. I think $S_t$ should be $S_t^*$, or can they be used interchangeably?\n    - Typo for the first character at line 363. \n    - The acronym for follow the top perturbed leader is a bit unfortunate as in literature FTL usually means Follow the Leader. Perhaps a change of acronym is in order. \n    - In line 160, it seems that the second strict inequality should be an equality\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V9fIVu1S3M0", "reviewer": "Reviewer_SYiQ", "summary": "This paper studies adversarial online learning problems where the algorithm chooses a subset of actions of size $B$ (instead of a single action) at each round and incurs the minimum cost among the chosen actions. The goal is to study how this additional `budget' per round leads to better regret bounds for the problem. The authors propose an extension of the FTPL algorithm, called Follow the Top perturbed Leaders, and obtain regret bounds for both full information and semi-bandit feedback settings. Finally, it has been shown how the proposed algorithm can be used as a sub-routine in state-of-the-art algorithms for other problems such as online submodular maximization and linear programming to obtain budget-dependent bounds without changing the previous proofs too much.", "questions": "- Explain the challenges faced when extending the proof of FTPL to the more general setting with a budget of $B$.\n- Explain how the online submodular maximization problem fits the framework introduced in this paper.\n- The distribution Exp has been used several times in the paper without a precise definition. \n- The notation $\\bigoplus$ is used in Section 3 without a precise definition.\n- The name FTL used in the paper is a bit confusing. FTL usually refers to the Follow The Leader algorithm. However, in this paper, FTL refers to the extension of the Follow The Perturbed Leader (FTPL) algorithm.", "limitations": "Yes, the authors have clearly addressed the limitations of their work. The paper is mostly theoretical and does not need a discussion regarding potential negative societal impacts.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Comprehensive set of numerical experiments to verify the theoretical findings.\n- The problem framework is well-motivated via several real-world applications and is quite interesting.\n- Proof sketches provided in the text are quite insightful and provide high-level ideas of the proof without going into details.\n\nWeaknesses:\n- I'm not sure how the idea of choosing $B$ actions per round applies to the online submodular maximization problem. In online submodular maximization, the goal is to pick a subset of cardinality at most $B$ at each round to maximize the overall utility. Given that the rewards functions are monotone, it is natural to compare the performance of the algorithm against a fixed benchmark set with the same cardinality constraint $B$. That's why obtaining regret bounds against benchmark actions with smaller cardinality constraints (i.e., Theorem 6) is not reasonable. Also, the reward at round $t\\in[T]$ for a chosen action $S_t$ ($|S_t|\\leq B$) is $f_t(S_t)$, not the $\\max_{a \\in S_t}f_t(a)$ reward considered in this paper.\n- The algorithm seems like a straightforward extension of the FTPL algorithm to the framework with a budget of $B$ and It is not clear to me how challenging this generalization is. The authors need to highlight the challenges and discuss how they overcame them to obtain regret bounds for the more general setting.\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept