Venue: NeurIPS 2022 Conference

Reviews:

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 studied hyperparameter tuning for contextual bandits. The authors proposed a two-layer bandit structure to tune the exploration parameter where the top layer applies EXP3 to select a hyperparameter as adversarial MAB and the bottom layer is the contextual bandits to be tuned. The authors then generalized it to Syndicated Bandits to tune multiple hyperparameters. The proposed method achieve $O(T^{2/3}+\sum_l\sqrt{n_l T})$ regret for tuning UCB and TS based algorithms. Empirical evaluations show that proposed method outperforms baselines.

strengths_and_weaknesses: Strength:

Hyperparameter tuning for contextual bandits is an important and interesting problem. The idea of using adversarial bandits to select best hyperparameter is simple yet very intuitive. The proposed method has a non-trivial (although may not be optimal) regret guarantee and could be also of interest to practice. The paper is also well written and the main paper is easy to follow. 

Weakness:

I have two concerns regarding the paper:

1. The regret is only analyzed for UCB and TS based generalized linear bandits and is not general. The proof technique heavily relies on analyzing confidence ellipsoid of generalized linear bandits. Is it possible to extend the two-layer method for tuning other specific algorithms such as elimination based algorithm or adversarial bandits such as EXP3 or even general bandit algorithm, just like other model selection baselines? 


2. The $O(T^{2/3})$ regret seems not optimal. The key challenge and novelty in the proof is bounding Quantity (A) where the history depends on the sequences of pulled hyperparameters instead of contextual bandits using a consistent hyperparameter. However, corralling idea can achieve $O(\sqrt{T})$ regret as discussed in related work and is strictly better if only tuning one hyperparameter. Does the author suspect this $O(T^{2/3})$ is tight and inevitable in general case, if not allowing exponential dependency on the number of hyperparameters?

3. A minor suggestion is the proof is a bit hard to follow as it mixed UCB and TS and I would suggest the authors make a better presentation.

---------------After rebuttal---------------
Most of my questions are answered and I increased my score accordingly.  I suggest the authors clearly discuss the regret dependency on dimension $d$ in the final version.
questions: Besides the questions in weakness, I have two clarification questions: 

1. Is expect regret upper bound for tuning TS based algorithm defined as Bayesian regret or frequentist regret? I tried to follow the proof of Theorem 1 and it looks like frequentist regret to me, but the proof mixed UCB and TS and is not very clear. 

2. What is the dependency of regret on feature dimension $d$? Do they the same as bottom layer algorithm, e.g., linear for UCB and $d^{1.5}$ for TS?
limitations: See weakness.
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 work studies the problem of hyperparameter tuning for contextual bandit algorithms.  Due to the unique properties of contextual bandits (no pre-collected dataset, and the decision have to be made online), offline tuning methods can not be directly applied. The authors proposed a two-layer framework to automatically tune the exploration hyperparameter in the process of bandit learning. A upper regret bound of $\tilde O(T^{2/3})$ is proved for the proposed method in general. A $\tilde O(T^{1/2})$ is derived for the UCB-based algorithm when the theoretical exploration parameter is no bigger than any elements in the tuning set. 
strengths_and_weaknesses: Strength:
- The hyperparameter tuning problem is quite important and the proposed method is reasonable.
- The theoretical analysis is sound to me.

Weakness:

- The empirical evaluation is quite toy.  (1) Why not also tuning more advanced bandit models, e.g., NeurUCB?  (2) In addition to the Movielens dataset, performing the evaluation on the Yahoo news recommendation dataset will be more convincing. 
- The   $\tilde O(T^{2/3})$ upper regret bound is quite weak. 
- About the underlying assumptions on the search space of hyperparameter configurations is not clearly discussed. For example, the candidate hyperparameter set must be finite?  If it must be finite, how large it can be? Can it be larger than T? In the experiments, the size of the set is pretty small. It would be helpful and interesting if the author can add more discussions on more on the requirements of the candidate hyperparameter set, both theoretically and theoretically.

questions: - Why not perform the tuning for NeurUCB?
- What are the  requirements of the candidate hyperparameter set, both theoretically and theoretically
limitations: See weakness.
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 proposed a two-layer bandits framework for automatic tuning of multiple hyper-parameters in contextual bandits algorithms. The bottom layer hosts the original bandits algorithm (UCB or TS-based), and the top layer is a set of EXP3 bandits algorithm, each of which is responsible for tuning one of the hyper-parameter in the parameter set. By sending the same global reward signals from the bottom layer to each of the top-layer bandits algorithm, the paper shows that the resulting regret bound has a linear (and not exponential) dependency on the number of hyper-parameters to be tuned. Experiments on synthetic and real-world data are performed for benchmarking and showing the advantage of the proposed framework in terms of cumulative regrets.
strengths_and_weaknesses: Strengths
- This paper can be of significant practical interest to a broad audience group who are interested in and using bandits algorithms. The auto-tuning algorithm for single and multiple hyper-parameters with a desirable regret bound provides a very useful tool for successful deployment of bandits algorithms.

- The proposed algorithm comes with a regret bound analysis that offers assurance that its learning efficiency is much better than naively treating the multiple hyper-parameters as a single parameter with more options.

Weaknesses
- Besides theoretical analysis of the regret bound, it is also important to provide intuition on why the change from using a single top-layer bandit to multiple parallel bandits can allow us to avoid the exponential dependency of regret on the number of hyper-parameters. 

- The experiments were all conducted on test cases with only two parameters. It would be great to have concrete examples of more hyper-parameters and associated empirical results.
questions: - The syndicated bandits share similarity to a multi-agent setting, where each agent performs its dedicated task but the agents share the same global reward signals so as to act cooperatively. I wonder if you could draw any connection here to explain why it works much better in regret bound than using a single agent to tune the multiple parameters.

- In the experiments, there are only two hyper-parameters with 15 possible combinations. Is the advantage seen in the plot from Syndicated  over TL-combined is due to the limited number of iterations? It would be better and more convincing to demonstrate the advantage of Syndicated if there were a test case with more hyper-parameters.
limitations: N.A.
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: This paper addressed an important and practical problem for bandit algorithms: how to auto-tune the exploration parameter to automate exploration-exploitation tradeoff to release the full power of bandit algorithms. The authors contributes knowledge on bandit hyperparameter auto-tuning with a bandit-over-bandit framework, applicable to important bandit algorithms class including LinUCB and LinTs. The proposed framework shares same flavor of EXP3 algorithms, in the sense that the superiority of a candidate exploration parameter is captured by a quantity as weight and then competes with other candidates. The validity of presented approach is backed by regret analysis and experiments.
strengths_and_weaknesses: Strengths:

The writing is clear and easy to follow. 
The authors did great job on presenting evidences of their claims, and the message is clear conveyed. 


Weaknesses:

I am satisfied with the submitted version. 
questions: 
I have one question came from my personal interest. It would be of my great appreciation if the authors share their insights.

My question came from picking "one" class of bandit algorithms from a pool of candidate bandit algorithms". You may already share same experience that, in your Algorithm 1 and 2, the " time horizon T and warm up length T1" are typically subject to change in practice. We may pick T and T1 subjectively, and I think we don't have a good strategy to find a pair of "great (T , T1)" to pick the "best bandit algorithms from candidate pool". 

Your framework invites to think about the possibility of "bandit-ovet-bandit-over-bandit" flavor framework to do automatic decision making. It would be great if you can share your thoughts on this point, if you also feel this is an interesting problem.
limitations: 
The only interesting limitation came to my mind is the problem "bandit algorithm candidate auto selection" I elaborated in the questions section. This is not count as a limitation of current submission.
review_title: null

Meta-review: metareview: Thank you for submitting your paper to NeurIPS! This paper studies the important practical challenge of parameter tuning in real-world contextual bandit implementations. The authors propose a bandit-over-bandit framework: the bottom layer is the original bandit algorithm (e.g. LinUCB or LinTs), and the top layer is an adversarial EXP3 algorithm for choosing the best hyperparameter. The resulting regret bound has a linear (and not exponential) dependence on the number of hyper-parameters. There was consensus that the algorithm is intuitive and novel, and the experiments support its promise. I am pleased to recommend acceptance.
confidence: Certain
Decision: Accept