Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the problem of identifying the arm with smallesst CVaR and VaR. The lower bound for the specific structured best-arm identification problem is studied. The paper also proposed an algorithm that achieves asymptotic optimality in sample size. 
main_review: The paper provides asymptotically matching upper and lower bounds for the best-arm identification methods for CVaR and VaR etc. I appreciate the efforts the authors have made for organizing all the content. However, the presentation and clarity of the paper are the major obstacles for understanding the whole paper, along with some technical incorrectness and ambiguity. I'm listing all my concerns as below:

1. Although it might be trivial, it's indeed unclear to me how standard arguments in best arm identification lead to Equation (4) and (8). First, it is better to indicate where the equations come from in the standard references. For example, (4) seems to come from a direct result of Theorem 33.5 in [1]. However, even with the results there, it is unclear why the results of best arm identification can be directly applied to a different problem of identifying the arm with smallest CVaR and VaR. It would be better if the authors can make the proof of (4) and (8) explicit.

2. Furthermore, Equation (4) and (8) make me even confused since they're suggesting that the problem of identifying the arm with smallest CVaR is exactly the same as the original best-arm identification problem in both upper and lower bounds. And the follow-up analysis (Lemma 3.1) is mostly simplification that does not depend on the structure of CVaR. If (4) and (8) turns our to be a simple application of the known result, it would be better if the authors can be clear on their own technical contributions.

3. With the above point said, I believe one of the most important contribution of this paper is a statistically and (maybe) computationally efficient algorithm. However, the proof in Appendix F appears to be wrong. In particular, the authors only show that $G_z$ has its $(1+\epsilon)$ moment bounded. However, the authors fail to show that among all the distributions that has moment bound, the way $G_z$ moves the mass is the optimal way such that $d_K(F, G_z)$ is minimized. Indeed, this is definitely wrong: the authors suggest that one shall move the mass on the left and right tail equally to point 0. However, in a highly asymmetric distribution, it would incur a much smaller distance if we only move one side of the mass that has a really long tail. The authors also didn't discuss whether the step of stopping rule is computationally efficient or not. 

4. There are many ambiguities in the paper that is not rigorously defined, which makes it hard to understand the paper. My suggestions for improving the presentation of the paper are listed as below:

(a). In Section 4 when you describe the algorithm, it is better to write it in a formal algorithmic environment and be explicit on all the procedures. It is unclear to me how 'any reasonable tracking rule' are applied, how 'empirically-minimal CVaR arm' are selected. These might appear trivial but are not rigorously defined. One shall replace the languages there with equations. 

(b). Similar issues also happen in other places, e.g. the notation $\mathcal{\epsilon}$ in line 301, the notation $\mathcal{L}$ in line 285 (although it is defined as the set of moment bounded distributions in introduction, later it is also used to refer to any set of distributions in line 150 and 199 etc.), and the notion of $\delta$-correctness in the paper. 



[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.


**Update based on author responses:

The authors resolved the questions I had and the proof of Lemma F.1 looks good to me after the clarification. I have adjusted the score accordingly.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the problem of identifying the arm with the minimum CVaR, VaR, or a conic combination of the mean and CVaR. It provides an \delta-correct algorithm that operates on possibly heavy-tailed arm distributions and matches the asymptotic lower bound on the expected number of samples needed as delta approaches 0. The paper also provides a result of separate interests, i.e., an anytime-valid confidence interval for CVaR estimation, which is tighter than truncation-based intervals (under certain conditions). Finally, the empirical studies show that the asymptotic sample complexity result of the proposed algorithm is indicative of its performance in practice. 
main_review: The authors have provided a clear exposition of the motivation and the theoretical results of the work. In particular, the KL_inf-based anytime-valid confidence intervals for CVaR are (to the best of my knowledge) very novel. In addition, the empirical results show that the asymptotic optimality of the proposed algorithm is indicative of the performance of the algorithm in practice. 

- In general, the paper will benefit from more detailed discussions on interpreting some of the defined quantities (especially the ones defined in L235-239 for the dual formulation and the ones defined in L252-256). In their current forms, the readers are hard to gain intuitions on them. 
- Could the authors comment on differences between this paper and "Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits" (https://arxiv.org/pdf/2008.13629.pdf)? 
- Empirically, what is the performance of the algorithm for identifying the best arm under VaR? 


limitations_and_societal_impact: Yes, the authors have adequately discussed the limitations and societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses the multi-armed bandit best arm identification problem which aims to identify the arm with the minimum tail risk measured by VaR, CVaR, or a weighted sum of CVaR and the mean. It proposes an optimal $\delta$-correct algorithm that works with a mild restriction on the arm distributions for CVaR and works with any arm distributions for VaR. In particular, the paper develops a lower bound for the problem and shows that the proposed optimal $\delta$-correct algorithm has the sample complexity that matches the lower bound asymptotically (as $\delta \rightarrow 0$). Additionally, the paper also suggests a solution to control the trade-off between the time computational complexity and the sample complexity, which is useful in practical applications.
main_review: The paper makes an important contribution to the multi-armed bandit best arm identification problem by considering 3 risk measures: VaR, CVaR, and a weighted sum of CVaR and the mean (mean-CVaR), all of which are well-motivated in the introduction. The proposed optimal $\delta$-correct algorithm is capable of handling a large class of arm distributions (with only mild assumption when the risk measure is CVaR and mean-CVaR). Moreover, its sample complexity exactly matches the lower bound as $\delta \rightarrow 0$. I think it is a good paper, so I tend towards acceptance. There are only several minor questions as follows:
1. What are the advantages/disadvantages between existing solutions in the ($\epsilon$,$\delta$)-PAC setting and the proposed optimal $\delta$-correct algorithm in this paper, e.g., how large $\epsilon$ should be such that existing PAC solutions are more favourable than the proposed algorithm in terms of sample complexity/computational complexity?
2. When the arm distributions are parametric but not from canonical SPEF, what are the implications when we apply the proposed algorithm (which is designed for non-parametric arm distributions)? For example, the knowledge of the parametric arm distribution may not be fully utilized.
3. I think that paper will be easier to read for people without much background if references and some brief explanations are included. For example, including a brief explanation of the intuition behind $KL_{\inf}^{U}$ and $KL_{\inf}^{L}$ in equation (1); references in lines 189-190 and 413-414; more details in lines 278-280; the derivation of equation (4) (or mentioning the specific chapter in the book [40]); the derivation of the GLRT in line 294. 
4. Why are there only heavy-tailed arm distributions in the experiments? Maybe the experiments with light-tailed arm distributions should also be demonstrated.
5. The experiments in figure 3 in Appendix K contain arm distributions whose CVaR values are quite far apart (-0.1428 vs. 2.4439), so I suspect it is easy for the algorithm to identify the best arm with a small sample complexity in this case. Thus, the linear relationship between the empirical sample complexity and the number of arms will be more persuasive if we consider similar arm distributions as those in Figure 2 where the sample complexity is roughly 200 for $\delta = 0.1$ and only $3$ arms (compared with figure 3 where the sample complexity is only around 150 for $\delta = 0.05$ and $20$ arms).

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the problem of multi armed bandits with the goal of identifying the arm with smallest (i) CVaR (ii) VaR or (iii) conic combination of CVaR and mean. This problem has applications in finance and clinical trials and captures a notion of risk sensitivity towards undesirable outcomes. The authors show that in the parametric case where the arm reward distributions follow a canonical SPEF, the problem reduces to best arm identification.

The authors study the VaR problem without any assumptions on the distributions, and study the CVaR problem assuming that distributions satisfy bounded $(1+\epsilon)$ moments. The proposed algorithm projects the empirical distribution to the considered family of distributions and considers an exploratory transform that guides the arm sampling distribution. At each time the empirical reward distribution suggests an arm with empirical minimum CVaR - this is the null hypothesis which is tested against all alternatives using GLRT. The algorithm upon satisfying the termination condition outputs the arms with the empirical minimum CVaR.

The authors show that the proposed algorithm asymptotically achieves the optimal sample complexity as the error threshold $\delta \to 0$.
The results are supported by numerical simulations demonstrating good performance on instances with Bernoulli arms. The performance of the algorithm hinges on the asymptotic convergence of the track-and-stop exploration protocol which is often fast even when the error parameter delta is moderate.
main_review: Overall the paper is well written and discusses prior work in sufficient detail, to the best of my knowledge. The considered notion of CVaR and VaR minimization have been studied in prior work, but the optimal rates have not been established for any regime of error tolerance, $\delta$ until this paper. I think this paper presents an important stepping stone towards exactly characterizing the minimax rates in best arm identification problems beyond the standard notion of mean. The algorithm presented in the paper is new and its proof uses novel analytical tools, which are of independent value.
- The only suggestion I can provide in terms of the writing of the paper is: it might help to define the CVaR and VaR problems informally in the introduction instead of referring the reader to Section 2. The contents of the introduction would be more interpretable that way.
- In financial settings, I can imagine more than best arm identification (which may take exponentially long in K if the gap is small), regret minimization with stochastic / adversarially chosen rewards is also of interest. Does the analysis here provide any intuition as to what to expect for the regret minimization setting as $T\to\infty$?
- Are there instances where the best arm and the arm with minimum CVaR are very different from each other? This would provide more justification for proposing algorithms specific for CVaR minimization and mean-CVaR minimization.
- Is there any intuition about the tightness of the algorithm in the non-asymptotic regime? It might help to include a discussion in the body of the paper as to the challenges of extending to the case when delta does not $\to 0$.

limitations_and_societal_impact: Yes, I believe the authors have sufficiently addressed such concerns
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers best CVaR arm identification in a fixed confidence setting. They can also deal with conic combinations of mean and CVaR, as well as VaR based criteria.

Main contributions include a lower bound which involves optimization over reals, and an algorithm which is asymptotically optimal in terms of expected sample complexity.
main_review: This paper considers the CVaR optimisation problem in a multi-armed bandit setting. Similar works exist in the context of mean [2] and for fixed budget best CVaR arm[39]. However, the CVaR optimisation problem over the distribution space L^K involves more intricate analysis. This paper carries out an involved analysis for obtaining the explicit KL characterisation of the lower bound. The authors also propose an algorithm that meets the lower bound asymptotically as the confidence δ goes to zero. Numerical results indicate that the average sample complexity matches the lower bound well at moderate values of δ.

Overall, the paper studies a problem which has been studied a lot in the recent years, but proposes a sophisticated analysis technique which is worth recording and could be reusable for other settings.

Could similar techniques be used for other convex risk measures? For example, utility based shortfall?
limitations_and_societal_impact: No major societal impact
review_title: null

Meta-review: This paper studies the multi-armed bandit problem with the goal of identifying the arm with the smallest CVaR/VaR/conic combination of CVaR and the mean. It is a significant question with applications in various domains. This paper proposes an algorithm that projects the empirical distribution to the considered family of distributions and considers an exploratory transform that guides the arm sampling distribution. It shows that the algorithm asymptotically achieves the optimal sample complexity. I agree with the reviewers that this paper has made interesting technical contributions and I am happy to recommend acceptance. 
Decision: Accept (Poster)