Adaptive Concentration Inequalities for Sequential Decision Problems
A key challenge in sequential decision problems is to determine how many samples are needed for an agent to make reliable decisions with good probabilistic guarantees. We introduce Hoeffding-like concentration inequalities that hold for a random, adaptively chosen number of samples. Our inequalities are tight under natural assumptions and can greatly simplify the analysis of common sequential decision problems. In particular, we apply them to sequential hypothesis testing, best arm identification, and sorting. The resulting algorithms rival or exceed the state of the art both theoretically and empirically.
The authors obtain Hoeffding type inequalities for stopped sequences. The classical Hoeffding inequality is a decaying exponential bound on the probability of a rare events for a sum of iid random variables. But this inequality is valid for a fixed number of random variables. The authors claim that it is of interest to obtain similar inequalities for random number of random variables. The authors appear to succeed in obtaining such an inequality (Thm 1 and Cor 1). The bound is valid for subgaussian random variables. The authors then claim that they can use this inequality and the idea behind it to obtain competing algorithms for some popular problems in statistics and machine learning (MAB etc, Thm 5). 
The paper is very well written, is easy to follow, and the contributions are stated clearly and the problem is well motivated. I think the paper is a good contribution to the literature. I do have few comments that the authors may use to improve the paper.   1. Algorithm 1: The way it is written makes the concepts confusing. f_\alpha is defined such that its value depends on the knowledge of alpha^*. The latter is not known. So, how do you "draw a sample from the arm with largest value of f_\alpha", and also how do you implement the next line: remove from A ...? You cannot compare the inequality because alpha^* is not known. Perhaps the authors have made a mistake here in terms of notations?   2. Defintion 4 should be stated as an Algorithm?   3. The authors may wish to add few lines on how their inequalities obtained are not just a rewording of the law of iterated logarithm (LIL), or is not just a simple implication. I mean if you provide some intuition on the nontrivially of these results given LIL, it would make the paper complete.