Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a variance-aware framework for stochastic sparse linear bandit problems.  The performance (as captured by regret bounds) bridges the general stochastic reward setting and the deterministic reward setting, which can be efficiently solved by a divide-and-conquer method.  The proposed framework employs variance-aware linear bandit methods (i.e. methods that did not assume or exploit sparsity of the coefficient vector), using repeated ‘explore’ steps and ‘commit’ steps with a adapting threshold.  The authors prove regret bounds using two example variance-aware linear bandit methods as sub-routines and achieve ambient dimension free bounds for the deterministic case.
strength_and_weaknesses: Strengths
- The authors show that variance-aware methods for linear bandits can be adapted variance-aware methods in the sparse linear bandit setting.  
- While the authors employ standard explore-then-commit style approach in identifying large coefficients for sparse linear bandits, for the variance aware setting the authors use loop over explore-then-commit steps adaptively changing the threshold.
- The presentation and writing were mostly clear and easy to follow.

Weaknesses
- (minor) Some experiments (even for a few toy samples) could help clarify whether empirically (a) the variance-aware linear bandit methods perform poorly in sparse settings compared to the proposed framework’s adaptation of those methods, (b) whether the dependence on $s$ in the bound is tight (i.e. would a new algorithm be needed or possibly just an alternative proof), and (c) if the empirical regret incurred by the proposed framework when actually applied to (nearly) deterministic settings is close to what could be achieved by a divide-and-conquer method designed specifically for the deterministic setting.

clarity,_quality,_novelty_and_reproducibility: Clarity - overall the writing was clear

Novelty - while there has been work on variance-aware linear bandits and separately work on sparse linear bandits, this work appears novel in studying variance-aware methods for sparse linear bandits.

Reproducibility -- the authors include proof sketches in the main paper and appendices with technical details 


summary_of_the_review: The problem is novel (though related to studied problems), the approach extends strategies (explore-then-commit for sparse linear bandits; variance-aware linear bandit methods) in a non-trivial manner.  The paper is well-written.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes the first variance aware algorithms for sparse linear bandits, which interpolates between the $\sqrt{dT}$ bound in worst case when variances are constant, and the bound independent of $d$ in the deterministic case where variances are 0.
The authors achieved this by an explore-then-commit framework that can be applied to existing variance-aware linear bandit algorithms, and showed that by plugging in VOFUL, it can match the regret lower bound for the worse case by a factor of $\sqrt{s}$, and attain regret upper bound $O(s^3)$ in the deterministic case, i.e., removed the dependence on d and T.
strength_and_weaknesses: Strength

The idea of extending variance-aware algorithm to sparse linear bandit is well-motivated.
The proposed techniques to make explore-then-commit framework to work when the desired regret is unknown (as the regret for variance-aware algorithms depends on the variances, which are unknown) may are intuitive and technically interesting.

Weakness

1. The description in Section 3.1 can be further improved. Its current form is a bit hard to follow, e.g., maybe first define what is arm $i$ in the first paragraph on page 6.

2. I would appreciate it if the authors can provide more explanations about the fundamental reasons for requiring action set to be unit sphere for all time steps, while Abbassi et. al. (2012) does not? It seems footnote 3 only provides an extreme case, where $\Omega(d)$ is unavoidable, i.e., unit sphere is only a sufficient condition to help avoid this. Is it possible to further relax this action set assumption, and allow for drifting action set?

3. The authors mentioned the data-poor regimes where $d>>T$ is beyond the scope of this paper. Can the authors elaborate on what are the possible difficulties in this case, and the reason why the proposed framework does not apply?

4. The authors mentioned the $O(\sqrt{s})$ gap to the regret lower bound can be improved if better variance aware linear bandit algorithm exists. Can the author provide more justification for this, e.g. why this is due to the sub-optimality of the adopted variance aware linear bandit algorithm, instead of the proposed explore-then-commit framework. And is it possible to derive a regret for the proposed framework (in variance aware sparse bandit), that depends on the regret of the adopted variance aware linear bandit, so that, it directly shows with an optimal variance aware linear bandit, the proposed framework is able to close the $O(\sqrt{s})$ gap?

clarity,_quality,_novelty_and_reproducibility: The motivation and technical contribution is clearly stated, and most part of the paper is easy to follow.
The theoretical results look intutive and sound, though I didn't carefully check the proof.
summary_of_the_review: Variance aware algorithm for sparse linear bandit algorithm is well-motivated, and this paper provides the first solution via a explore-then-commit framework that converts existing variance aware algorithm to the sparse setting. However, there is still an $O(\sqrt{s})$ gap to the regret lower bound in the worst case, and it is not very clear to me whether this gap can be closed under the current framework.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides a black-box conversion from variance-aware linear bandit algorithm to its corresponding variance-aware sparse linear bandit algorithm. The regret framework is applied to two recent algorithms and obtain quite compelling regret bounds.
strength_and_weaknesses: 
   Pros:

   (A) The generic formulation uses gap-dependent rounds split into commit and explore rounds to delicately balance exploration while minimizing the resulting regret. The resulting regret terms are almost tight except for a square root sparsity (s) factor which is typically small in practice.
   (B) Quite a few state-of-the-art algorithms such as VOFUL2 and Weighted OFUL are considered in the framework and their regret are rigorously derived for both the
framework and the corresponding algorithm components.

Cons:

   (i) Experiments show-casing the proposed regret bounds on datasets would have made the paper much more compelling.
   (ii) As noted in the paper, there is still a gap with respect to the lower bounds and the obtained bounds.


clarity,_quality,_novelty_and_reproducibility: The paper is well written with the key ideas and proof sketches shown in the main body of the paper . It proposes a novel black-box framework for plugging in linear bandit algorithms and obtain sparse ones. Also, it is self-contained with all the relevant results.
summary_of_the_review: Overall, a good theoretical paper for providing new algorithms for the variance-aware sparse linear bandits and would be of great interest to the community.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studied sparse linear bandits with noise variance appearing in the regret bound.
strength_and_weaknesses: It is interesting to study sparse linear bandits from variance-aware prospective. However, I feel the regime that variance-aware algorithm can improve for sparse linear bandits is not sufficiently interesting. For the current regret bound, it will be dimension-free only for the deterministic case (sigma=0) or nearly deterministic case (sigma=1/sqrt{d}). Sparse linear models or bandits are motivated by the use of high-dimensional features so d is typically very large. The requirement for sigma=1/sqrt{d} is very restricted and does not match any practical application. Thus, the novelty beyond variance-aware linear bandits is limited.
 
Second, I feel a variance-aware or problem-dependent lower bound is missing. I would like to see how this problem depends on noise-variance fundamentally. Existing minimax lower bound cannot explain this. 

clarity,_quality,_novelty_and_reproducibility: good.
summary_of_the_review: Although a new prospective for sparse linear bandits is proposed, the improved regime is less interesting. A lower bound to fully characterize the problem is missing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a variance-aware framework for sparse linear bandits. The framework follows explore-then-commit method and employs existing variance-aware linear bandit algorithms using repeated ‘explore’ steps and ‘commit’ steps with an adapting threshold. The authors proved tighter regret bounds of the proposed framework with two example variance-aware linear bandit methods, VOFUL2 and Weighted OFUL. Specifically, the regret bounds are dimension-free when the environment is nearly deterministic. All reviewers appreciate the novel perspective of variance-aware sparse linear bandits. One shared concern by the reviewers is the unit sphere assumption of action set: this assumption is acceptable from a theoretical perspective but can be very restrictive in practice. The authors are suggested to further discuss this assumption in the final version. The authors are also encouraged to include additional discussion on $O(\sqrt{s})$ gap between regret lower and upper bound and the problem-dependent lower bound. Overall, I am happy to recommend acceptance.


justification_for_why_not_higher_score: While the reviewers mostly agree with the novelty of proposed method and its theoretical contribution, there is one remaining concern shared by reviewers regarding the restricted and impractical assumption of unit sphere action set.
justification_for_why_not_lower_score: All reviewers agree that studying sparse linear bandits from the variance-aware perspective is novel and interesting. The improved regret is a good theoretical contribution.
Decision: Accept: poster