Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.


strengths_and_weaknesses: Weakness: Comments on the writing:
There 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.

Based 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). 

Also, I believe adversarial online learning are quite understood. So, I do not think the proposed learning problem is challenging. 
questions: see above
limitations: see above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths: 

The 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. 

The 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.

The 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. 


Weakness: 

It would be great if the authors could get a B related lower bound. 

Presentation: 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)? 
I think a rewrite of Lines 60-65 may make the introduction easier to read.



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?

I think the authors should also cite the line of work about online submodular minimization, such as [Hazan & Kale., 2012]. 

Hazan, E., & Kale, S. (2012). Online Submodular Minimization. Journal of Machine Learning Research, 13(10).
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
In 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. 

First, 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. 

The 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.
strengths_and_weaknesses: Strenghts

    - 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. 
    - 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.
    - 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.
    - 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. 
    - 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. 

Weaknesses

    - 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. 
    - 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. 
    - 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. 
    
Minor comments

    - 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?
    - Typo for the first character at line 363. 
    - 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. 
    - In line 160, it seems that the second strict inequality should be an equality

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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
- Comprehensive set of numerical experiments to verify the theoretical findings.
- The problem framework is well-motivated via several real-world applications and is quite interesting.
- Proof sketches provided in the text are quite insightful and provide high-level ideas of the proof without going into details.

Weaknesses:
- 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.
- 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.


questions: - Explain the challenges faced when extending the proof of FTPL to the more general setting with a budget of $B$.
- Explain how the online submodular maximization problem fits the framework introduced in this paper.
- The distribution Exp has been used several times in the paper without a precise definition. 
- The notation $\bigoplus$ is used in Section 3 without a precise definition.
- 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.
review_title: null

Meta-review: metareview: The paper considers the experts problem when the online player is allowed to choose B arms instead of 1 and is rewarded according the best arm within the set it chose. The comparator considered in the first result of the paper is standard best single arm. The paper shows that the regret scales in this setting as ~ T^(1/(B+1)) -- recovering and extending the standard result. The paper uses this result to then further get another result when the set wise function is max. Here existing result in the comparator compared with fixed size B, i.e. max size allowed, where as they present a result that allows comparison with any budget B'. They also play a ln(T) factor more arms in each round which allows them to compare with OPT as opposed to (1 - 1/e) OPT. 

The paper according to reviews is well written, but I found section 3 hard to read, especially the notations of B' and tilde{B}. I also think the regret statement in that theorem is not well defined, you should state clearly it is with respect to B' sized sets. There are other shortcomings of the paper like the bandit results dont match the optimal in the case of B=1 (as discussed with a reviewer), which points to suboptimality of presented bound. The lower bounds presented are also unfortunately weaker. These are not shortcomings per se but desiderata to make the paper very strong. I also find the fact that they ln(T) factor more arms in OSFM is not stressed appropriately. 

Overall the results in the paper are good as presented, but the shortcomings listed above the paper put it right on the borderline. Overall there is general appreciation of the results by the reviewers and as such according to that it puts it slightly above the borderline according to me. I am recommend a marginal accpet for the paper. I would like to urge the authors to look at the paper critically irrespective of the outcome and definitely look to improve presentation at the minimum. Other lingering questions if answered will be a great bonus.   
confidence: Less certain
Decision: Accept