Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the multi-arm bandit problem. It starts from the observation (already present in the literature) that classical bandit algorithms such as UCB or TS estimate the mean rewards of the arms by simple empirical averages without taking into account the fact that they are adaptively sampled and are therefore biased. The paper thus proposes to make these estimators unbiased by using importance weighting (inverse propensity score weighting) as well as variance reduction tools (adaptive doubly robust estimator and clipping). Applying it to TS, they empirically demonstrate that their algorithm significantly outperforms classical TS and UCB while maintaining a theoretical worst-case regret bound of order $O(\sqrt{T})$. 
main_review: The empirical contribution of the paper is interesting and having bandit algorithms with improved performance is significant. The simulation results in this paper seem compelling to me. While the application of the inverse propensity score is not new in the bandit literature, variance reduction techniques have been shown to perform very well in counterfactual learning and optimization and I am not aware of any previous work applying it to TS or UCB. It is instructive that this also applies to multi-armed bandits. 


On the negative side of the paper:
1. I did not find it so well written. 
	- Probably because of the page constraint, the heavy use of inline formulas makes the reading sometimes difficult. 
	- In addition, I would have liked more explanations and informal proofs for some of the claims: why is the standard empirical average biased and what is the bias? I agree that the authors explain that this is due to adaptive sampling and that this has been shown in previous work. But this statement is important to the message of the paper and would make the paper more self-contained. Similarly, a simple formula that shows that the new doubly robust adaptive estimator is indeed unbiased and that its variance is less than that of DR or IPW might help the reader who is not familiar with counterfactual learning. At least the latter claims could probably be illustrated in a figure with synthetic data.

2. Also, the regret bound is suboptimal in the number of arms K (of order $K^2\sqrt{T}$ instead of $\sqrt{KT}$). Some parts of the analysis could probably be improved. For example, the upper bound of $N_a$ by $T_a$ in the last equation of p16 seems very suboptimal and gives an extra K factor. Is it not possible to improve this?

Other comments:
- I agree that the method seems more suitable to TS to compute inverse propensity scores. But do you think that it could also be applied to UCB based algorithm to improve their estimates?
- I would also write in the main text that you also provide distribution dependent regret bound in $O(\log T / \Delta)$
- For best-arm identification simulations, it could be interesting to show the frequency of success of all algorithms. It is supposed to be approximately 0.95 in theory, but what is it in practice?
- What motivates the default choice gamma = 0.01 for the algorithm? Doesn't it yield linear regret? Shouldn't it depend on K in practice?
- TS and UCB are not the standard algorithm for best arm identification. It could be interesting to apply the techniques to best-arm identification algorithms. 
- How is exactly AB implemented in the simulations?
- I suspect that the regret bound of Thm. 1 should be $\sqrt{T}log T$ and not $\sqrt{T log T}$. Indeed, $T_0$ as defined in line 514 is of order $(\log T / \Delta)^2$ and not $\log(T)/Delta^2$ as stated in line 303.
- Since the bound is of order $\sqrt{T}$, I do not find Cor. 1 very interesting since it is a straightforward application of Azuma-Hoeffding inequality to Thm. 1. I would replace it with a single-line comment in the text stating that the bound also holds with h.p. 


Typos:
- l92: a dot is missing
- l78: I would define IPW there
- l307: a T should not be there
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper investigates stochastic MAB algorithms, UCB and Thompson sampling, where the usual choice for estimating the means of arms, importance weighting, is replaced with a "doubly adaptive" estimator. This estimator, proposed by Leudtke and Van Der Laan 2016, is self-normalized in that the weight of each sample in the mean estimator is not uniform but rather proportional to the inverse square root propensity weight; it also uses an AIPW-style estimator with these weights.

The authors claim that this new estimator can have better practical performance, since the variance of the mean estimates is greatly reduced, and this claim is verified with empirical simulations. Additionally, the authors provide an upper bound on the worst case performance of O(K^2 sqrt{T log T}), which captures the correct dependence in T.

main_review: This is a great paper. First, it studies a archetypal NeurIPS problem, the stochastic MAB, and asks an important and very neglected question: what can we say beyond worst-case performance? Second, it brings in powerful and well developed ideas from other literature that are ignored by our community. Third, it is well written, cohesive, and easy to follow. The inclusion of the two-arm upper-bound proof in the main body is appreciated, since it gets the main points of the analysis across without taking up too much space.

There are a few weaknesses, besides the K^2 term in the upper bound. There is no theory supporting the central hypothesis that DATS can have improved sample complexity. Maybe a particular instance where a gap can be shown between the IPW and a DATS-based algorithm is possible?

What is the point of the \Phi is algorithm 1 (it is monotonic)?

post-rebuttal: my opinion of this paper remains high and my score unchanged.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors propose a Thompson Sampling (TS) based cumulative regret-minimsation algorithm for stochastic MAB. Their approach pivots on the unbiased estimator of mean using inverse propensity score, and then it applies weighted averaging scheme [Luedtke and Van Der Laan, 2016] to reduce the variance of the estimate. Further, they establish theoretical worst-case upper bound on the expected cumulative regret, and present multiple simulations to show empirical efficiency of their proposed algorithm.
main_review: below is the list of strengths ad weaknesses of the paper:

Strengths:
1) The proposed algorithm is empirically efficient.
2) Use of propensity score along with weighted averaging for a better estimation of the mean is a god idea.


Weaknesses:
1)  It seems that to hold the proposed approach, the reward distribution of the individual arms has to be Gaussian; however, there is no explicit mention of the same. There is no discussion on the family of sub-gaussian reward distribution.
2) The scope of this proposed idea for sample averaging by propensity score, does not seem to hold for paradigm like UCB, wherein, given the history, the next arm to be pulled is obtained deterministically.
3) The problem-independent upper bound on cumulative regret presented in Theorem 2 is far from the optimal rate O(\sqrt(KT)).

Overall the contribution appears to be marginal.

Minor Comment:
There is only a single subsection 1.1 under the section 1.
limitations_and_societal_impact: Mention of limitation of the proposed approach is not apparent.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a Thompson Sampling-based online algorithm for the stochastic K-armed bandit problem, which exhibits improved numerical performance in terms of the expected cumulative regret and its variance, and smaller stopping times for best arm identification. The improvement is over the popular UCB and Thompson Sampling baselines common in literature. Although, the improved empirical performance of the proposed algorithm does not translate to provably better regret guarantees vis-a-vis the aforementioned benchmarks (a sub-optimal K-dependent scaling factor is present in the upper bound). The improved numerical performance is primarily attributed to a new estimator for the true arm-means (as opposed to the standard sample-average approximation used by vanilla UCB/TS), which is provably unbiased, and at the same time, offers a better variance control compared to other unbiased estimators popular in ex post (adaptive) causal inference literature. The punchline, in my understanding, is that it is possible to improve and (better) control the numerical performance of bandit algorithms by employing sophisticated estimators from adaptive inference literature, without compromising on rate-optimality in the regret upper bound (order of dependence on the sampling horizon, modulo multiplicative constants). 
main_review: The paper is well-written overall with intuitive explanations, and an accessible proof of the main theoretical result. The technical development occurs at the intersection of adaptive inference with the traditional regret viewpoint in the learning literature, and certainly seems to be of practical significance (numerics are promising). Also, extant literature in this space is relatively recent and sparse (to the best of my knowledge), making this work even more appealing. The literature review seems reasonably complete, although the following paper is missing: https://arxiv.org/pdf/2106.02126.pdf. This is a recent paper that answers some long standing open questions regarding the distribution of arm-pulls under UCB, TS and can significantly shape/alter the discussion in the current paper regarding asymptotic-normality (or lack thereof) under vanilla UCB/TS. Cited paper, I think, might be able to provide a more comprehensive and theoretically grounded justification for why it may be advisable to move towards a greater level of sophistication in estimator design in bandit settings.
limitations_and_societal_impact: Some broad remarks and minor typographical errors are noted below:

1. Line 34: It should be "..... uncertainty," (the order of " and , should be flipped). There are other occurrences too.

2. Line 37,38: This is a bit ambiguous; gap-dependent bounds are not the same as "worst-case" bounds in standard bandit parlance. 

3. Footnote 2: Also state the $O\left( \sqrt{KT\log K} \right)$ bound for the Gaussian prior-based version of TS from the same reference, for a comprehensive picture (the stated bound corresponds to the Beta prior-based version of TS).

4. Footnote 3: This is not true for UCB. Previously cited paper dispels this myth (Refer to Theorem 1 and 4 therein).  

5. Line 114: Policy-dependence of regret should be made explicit on the RHS. 

6. Line 144-145: Same as above, i.e., claim re asymptotic-(non)normality needs to be revisited and corrected for UCB.

7. In Algorithm 1 "arm elimination step," the first update needs to happen for each $a\in\mathcal{A}_t$. 

8. In Algorithm 1 "propensity score computation" step, it should be $\tilde{r}_{t+1,a}$ after "argmax."

9. Line 200: "s" should be "t," and it should be "a" in place of $\tilde{r}_{t,a}$.
review_title: null

Meta-review: Three of the four reviewers recommended accepting the paper and I am happy to accept it. I encourage the authors to include in the final version the additional material that they mentioned in the rebuttal.
Decision: Accept (Poster)