Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of constructing tight non-asymptotic confidence intervals for sub-gaussian random variables. To achieve this, the authors propose to use a sub-gaussian intrinsic moment norm, which can be robustly estimated using a simple plug-in approach. The paper then applies the analysis for multi-armed bandits, derives  matching regret upper bounds. 
strength_and_weaknesses: The paper is well-written. I try to check the derivations as much as I can given the limited time, and I don't find any major problem. 

However, I am not an expert on statistics and therefore I cannot judge the paper in terms of novelty and how significant the contribution is. I sincerely apology for this. Also, if the authors want to submit this paper to a machine learning conference, I think ICLR might not be the best place, maybe it’s more suitable for COLT, ALT and AISTATS? 

My major concern is how significant the contribution is to the machine learning community. I have the following questions. 

1. In the experiment the reward gaps are fixed. Maybe it’s better to show the performance under different reward gaps? It’s especially interesting to see how the algorithm performs with different minimum reward gap.

2. How does the proposed algorithm compare to common baselines such as UCB and Thompson Sampling? 

3. Could the proposed method be applied to linear bandits? Or can it be applied to problems where UCB and TS have limitations? 

4. From the theoretical perspective, how does Theorem 4 improve over the regret bound of UCB? I believe it’s at most a constant improvement as UCB is both minimax and instance-dependent optimal. It’s still great to see the regret bound of the proposed method if it achieves better practical results than UCB and Thompson Sampling, but the author needs to show that. 
clarity,_quality,_novelty_and_reproducibility: Please see the detailed comments in the previous section. 
summary_of_the_review: My decision is mostly based on how significant the contribution is for the machine learning community. I recommend rejecting this paper as I am not convinced that proposed method has significant contribution to multi-armed bandit setting, which is the application this paper considers. Please correct me if I missed anything important. I am happy to adjust my score based on how well the authors answer the questions in the rebuttal.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper shows that finite-sample bounds on sub-Gaussian random variables can be derived in terms of a particular norm -- the intrinsic moment norm.  They present (consistent and robust) estimators for the intrinsic moment norm and use these as plug-in estimates to obtain (approximate) confidence intervals.  They use this approach in an upper-confidence bound approach to multi-armed bandits, where it seems to work better than some baseline methods.
strength_and_weaknesses: Strengths:
* The intrinsic moment norm is very interesting, and its connection to finite-sample bounds for sub-Gaussians is an underexplored area.
* Some of the results in the paper come with rigorous theoretical guarantees.

Weaknesses:
* Overall, I found the paper difficult to follow.  A lot of technical results are presented with relatively few explanations.  I understand the space limitations of this venue, but even still the material in the main text jumps around considerably.  For example, the first figure referenced in the main text is Figure 3.  
* Finite-sample bounds are, in my opinion, mainly useful if they can give concrete guarantees.  For example, if we _know_ a variable is bounded, we may use Hoeffding's inequality to generate confidence intervals that are guaranteed to have at least our desired coverage.  In contrast, we generally do not know the intrinsic moment norm of data, and hence need to estimate it from the data.  Then, the main result of the paper in terms of using the intrinsic moment norm for tail bounds relies on Theorem 3.  Theorem 3 guarantees consistency (an asymptotic property) but for finite samples is only quantitative in terms of the $g$ sequences, which seem difficult to know a priori.   This ends up causing the tail bounds to have an asymptotic flavor -- they are correct up to a (unknowable) factor that shrinks as the sample size gets large.  Unless I am missing something, this seems to undercut the main point of using finite-sample bounds.
* Along a similar line as the previous comment, I was confused by the motivation for having a robust estimator of the intrinsic moment norm.  I suppose the assumption is that outliers are somehow corrupted data that we want to ignore.  If instead, outliers are actually a part of the data generating mechanism then the examples  in Figure 3 (mixtures with a Cauchy) are no longer sub-Gaussian.  It would be good to better motivate why, if we do not know the intrinsic moment norm and need to estimate it from the data, we would also be confident enough to make assumptions M.1 and M.2, and hence decide that any outliers in our data are true outliers and not just heavy tails.
* I found the sub-Gaussian plots a nice and intuitive way of visualizing sub-Gaussian distributions, but I am not sure how useful they are in practice.  As above, finite-sample guarantees are nice for small samples, but to judge whether a plot looks linear or not would require many, many observations from the distribution.  Even in Figure 2, I'm not entirely sure that I would be able to say whether the left or right figures look linear if the red dotted lines were not present.  I also think that the axis labels (Value and sqrt_log_j) in Figure 2 could be improved.
* There were numerous typos throughout the paper and appendix (too many to list here, but e.g., "the Hoeffding's inequality" in the main text, and "varinace" in Figure 6).  These, overall, did not interfere with my understanding of the material, but the paper would certainly benefit from some copy editing.
* It would be good to include empirical results about the coverage properties of confidence intervals produced using estimated intrinsic moment norms.
clarity,_quality,_novelty_and_reproducibility: The clarity of the writing could be significantly improved.  The paper does a good job of referencing where various theorems come from, but once previous theorems are removed, there is not a substantial amount of novel material -- the constants in Theorem 1b are improved by about 10%, and the application of their approach to the multi-armed bandit setting is -- I think -- novel.  I am not qualified to comment on the novelty or significance of the multi-armed bandit application, but the improvement provided here seems marginal to me.
summary_of_the_review: The paper has some interesting ideas, but the main results are not really non-asymptotic guarantees.  The paper would benefit from an explanation of how to use these results in practice to get finite-sample guarantees.  Also, the presentation could be made more clear.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper provides a method to estimate a sub-Gaussian distribution's variance-type parameters. 
strength_and_weaknesses: * Strength

This paper addresses the problem of estimating a sub-Gaussian distribution's variance-type parameters, which is less studied.

* Weakness

This paper attempts to estimate a distribution's sub-Gaussian variance-type parameters. But how do we know if the distribution is not heavy tailed to begin with? What happens if the method is used (incorrectly) on a heavy tailed distribution (e.g. completely Cauchy)?
clarity,_quality,_novelty_and_reproducibility: Overall the paper is well written. 
summary_of_the_review: I think the missing paper is missing a part on how to determine whether the distribution is sub-Gaussian do begin with, which seems rather important.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: - Summary:

This paper shows that finite-sample bounds on sub-Gaussian random variables can be derived in terms of a particular norm -- the intrinsic moment norm. They present (consistent and robust) estimators for the intrinsic moment norm and use these as plug-in estimates to obtain (approximate) confidence intervals. They use this approach in an upper-confidence bound approach to multi-armed bandits, where it seems to work better than some baseline methods.

- Strengths

Findings of the paper include:

1. The reviewers found that the intrinsic moment norm is an interesting construction, and its connection to finite-sample bounds for sub-Gaussians is an underexplored area.
2. Some reviewers found the rigor of some theoretical results satisfying. 
3. Overall, the fact that the problem is less studied is encouraging to continue working on this subject.

- Weaknesses

1. Analysis is non-asymptotic, which makes it less practical. Finite-sample analysis is more useful and give concrete guarantees.
2. The fact that several parts of the part require revision makes this discussion stage hard to handle and make good decisions: it would be better if the paper was further polished (better presentation) + include new results to be a more complete story. 
3. A reviewer considered the following point important: ``But how do we know if the distribution is not heavy tailed to begin with? What happens if the method is used (incorrectly) on a heavy tailed distribution (e.g. completely Cauchy)?''

- What would be missing:

Handling the weakness above could be a good start: non-asymptotic analysis, more empirical justification, better presentation. 
justification_for_why_not_higher_score: See weaknesses
Decision: Reject