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: The authors study the best-of-both-worlds guarantees for model selection in linear bandits. The paper proposes a novel algorithm called Arbe, which achieves the first high probability regret bound for adversarial model selection. In addition, the paper proposes a two-stage algorithm called Arbe-Gap, which achieves best-of-both-worlds high probability regret bounds.
strengths_and_weaknesses: Strength:

1. The writing is mostly clear.
2. The best-of-both-worlds guarantees for model selection is an interesting and important problem.
3. The proposed algorithms are novel. It is the first algorithm that achieves high probability best-of-both-worlds regret bounds for linear bandits with nested model classes.

Weakness:

1. Both stochastic and adversarial regret bounds are suboptimal with respect to the dimension of the reward vectors.
2. The paper does not contain numerical experiments for the proposed algorithms.


questions: 1. Can the proposed algorithms be extended to the infinite arm setting? If not, what is the main difficulty?
2. Does Arbe-Gap work for the stochastic rewards with adversarial corruptions?
limitations: Since the paper does not provide any empirical comparisons, it is still unknown whether the proposed algorithms are practical.
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 work studies the problem of model selection with bandit feedback in the presence of a sequence of policy classes, in other words, a monotonically increasing sequence of sets of polices. The goal is to achieve the "best of both worlds" high-probability guarantee between the stochastic world and the adversarial world, in other words, ensuring $polylog(T)$ regret for stochastic setting and $\sqrt{T}$ regret for the adversarial setting. It follows similar ideas of Lee et al. (2021) and Wei et al. (2021) and applies the idea of regret balancing technique discussed in Cutkosky et al. (2021) to design the algorithm Arbe for model selection. To achieve this, the authors extend the techniques to adversarial rewards: they have a few necessary constraints on the algorithms, and enhance the test for mis-specification. 
strengths_and_weaknesses: This work provides the first algorithm which achieves the best of both worlds high-probability guarantees for model selection within (linear) bandit scenarios. The problem is well-defined and very general (for h-stability and extendability). The techniques which are further improved from the previous work of Lee et al. (2021) and Wei et al. (2021) following the idea of regret balancing are very interesting, and may be applied in solving other problems. 

Overall, this work does not have any other specific weakness. The paper is clearly written and easy to understand. 
questions: 1. The idea is very similar to the pervious work of Lee et al. (2021) and Wei et al. (2021). I wonder if the authors could emphasize the specific adjustment they made to achieve the best of both worlds guarantee in this setting and what's the specific difficulty this new problem has. 

2. Would like to confirm that line 6 of Arbe-GapExploit means that the whole algorithm would only deal with "adversarial" setting and would not go to ArbeGapExploit phase anymore. 

3. Can we extend this approach to achieve results in an intermediate setting (e.g., corruption setting)? 
limitations: None.
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 work considers model selection from a set of contextual bandit algorithms with nested policy classes. Each of these base learners has a known regret guarantee, that may or may not hold. The environment may be either stochastic with a reward gap or adversarial, and a best-of-both-worlds high-probability bound is provided for the proposed meta-algorithm. On each round this meta-algorithm chooses a base learner with probability that depends on their known bounds. It then performs mis-specification tests and eliminates the learners that violate their regret bounds. Additionally, it performs a test to reliably detect the stochastic environment and switch to exploitation mode in this case. An important building block is extension of the policy class of each of the base learners to include special actions that delegate the decision to another base learner (with a larger policy class). This allows the elimination test to work in the adversarial environment. In the case that the environment is known to be adversarial, the algorithm can run without the stochastic detection test, in which case it achieves a tighter bound. This bound is a high-probability version of the one known from prior art.
strengths_and_weaknesses: **Originality** To the best of my knowledge, this is the first work to provide best-of-both-worlds guarantees for bandit model selection. It extends the idea of regret balancing to the adversarial environment by modification of the base learners and carefully designed tests.

**Quality** The proofs are provided in the appendix, but I did not verify their soundness. The proof sketches in the main paper seem reasonable. The dependence of the stochastic case bound on the complexity of the largest policy class is justified by proving a lower bound.

**Clarity** This work is highly theoretical, and therefore it is not surprising that it is not easy to understand. However, some improvements to the clarity and the organization would be helpful. For example, the detailed example in lines 46-65 is too technical to be part of the introduction, and is better suited for section 2. Subsection 2.1 feels out of scope for section 2. The extension of the policy space and linking of the base learner performances need more explanation. For example, before the definition of extendability, linking of the learners can be mentioned to explain how the extendability will be used by the meta-algorithm.

**Significance** Demonstration of best-of-both-worlds bounds is important for the understanding of the underlying relations between different settings and eventually designing practical algorithms that can optimally exploit the properties of the environment. On the other hand, switching between operation modes based on tests is intuitively less generic than a framework that tunes its parameters continuously. 

Some more discussion on future directions would help to realize the significance of this work. Can it be potentially generalized to other partial information settings? Can some additional assumptions improve the stochastic regret bound?

questions: Can you provide an example of contextual base algorithms (that actually use the context) that are suitable for this framework?
limitations: The assumptions are clearly stated. A lower bound for stochastic case is provided.
review_title: null

Meta-review: metareview: This work advances the direction on model selection for bandit problems with nested model classes. Reviewers all agree that the results are significant, the contribution is solid, and the paper is well written. Clear accept.
confidence: Certain
Decision: Accept