Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the risk-aware multi-armed bandits problem where arms (options) can be correlated. The authors consider different feedback settings of the problem: full-information (learner observes reward from all arms), semi-bandit (learner only observes reward from a subset of arms), and full-bandit (learner observed only single reward for selected arms)).
The goal is to learn a policy for sequentially selecting a weights vector for different arms (options) that achieves the best trade-off between reward and covariance-based risk.

The authors develop and analyze three algorithms (MC-Empirical (full-information setting), MC-UCB (semi-bandit setting), and MC-ETE (full-bandit setting)) for the risk-aware multi-armed bandits problem with correlated arms. The authors have shown that the problem-independent regret of MC-Empirical and MC-UCB matches with their lower bounds (up to a logarithmic factor), and MC-ETE has sub-linear regret ($O(T^{2/3} )$). Experimental results verify the performance of the proposed algorithms.
main_review: Originality:  This paper considers a new risk-aware multi-armed bandits model named continuous mean-covariance bandit
(CMCB), which considers correlated arms with continuous decision space (selecting weights for different arms). The authors have developed three algorithms for the CMCB problems with different feedback structures with theoretical guarantees. 
The authors have adequately cited the prior work and differentiated their work from previous contributions.

Quality: I find the paper technically sound, but I have not checked all the theoretical proofs in the Appendix.  The authors' claims are supported by theoretical analysis and experimental results.

Clarity: The paper is well-organized and well written. But I have a few questions for the authors (based on your response, I may increase my score): 
1. Could you explain how the updates happen in the 'Initialize' part (last line in Step 2) of MC-UCB?
2. I think $c$ should be input to MC-UCB. Right?
3. $N_i(t)$ and $J_{t,i}$ is not defined in algorithm. To completeness and avoid confusion, it can be $N_{ii}(t)$ and $J_{t,ii}$.
4. Could you give intuition about how the estimation of rewards and covariance in MC-ETE works? 
5. In bandits literature, the 'bandit' feedback means the same as 'full-bandit' feedback. I thought that the 'full-bandit' feedback is different than 'bandit' feedback. So using the 'full-bandit' instead of 'bandit' may cause some confusion.

Significance: This work is a good contribution to risk-aware multi-armed bandits literature. 
To the best of my knowledge, the authors are the first to consider risk-aware multi-armed bandits problem with correlated arms. They have given optimal (up to logarithmic factor) algorithms for full-information and semi-bandit setting and an algorithm with sub-linear regret for full-bandit setting.
Other researchers can use the techniques and policies developed in the paper for their future work on similar problems.


Post-rebuttal feedback: After reading other reviewers' comments and responses from authors, I am inclined to keep my score as is.
limitations_and_societal_impact: Since this work is a theoretical paper, I do not find any direct negative societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studied the mean-variance bandit (i.e. the reward function of choosing an action w is $w^\top \theta^\star - \rho w^\top \Sigma^\star w^\top$) with a continuous action space on the probability simplex. The authors considered three settings: 

1. Full-information setting, where a noisy observation of $\theta^\star$ could be observed at each round. Here a sqrt(T) regret (up to log factors) is proved, with both upper and lower bounds. The algorithm is simple: collect past observations and purely exploit at every round. 

2. Semi-bandit setting, where w can only take a few non-zero entries, and only the noisy entries of $\theta^\star$ chosen according to w are observed. Here a sqrt(dT) regret (up to log factors) is proved, with both upper and lower bounds. The algorithm is a manifestation of the UCB idea: find confidence bounds of $\theta^\star$ and $\Sigma^\star$, then play the action which maximizes the UCB of the reward. 

3. Full-bandit setting, where only a noisy version of $w^\top \theta^\star$ could be observed. Here the authors proved an upper bound of the order O(d*T^{2/3}), and the algorithm is to first explore on O(d^2) properly chosen basis vectors to estimate the mean and covariance, and then exploit after gathering sufficiently many observations. 

Experimental results are also given at the end. 
main_review: The mean-variance bandit is of relevance in practical scenarios (also listed by the authors under each feedback model), and a continuous decision space is natural. So this problem is of sufficient theoretical and practical interest. However, despite the contributions listed in the summary, I think this paper suffers from the following problems: 

1. Both the idea and the analysis are too simple. Both the pure-exploitation algorithm in the full-information scenario and the UCB-type algorithm in the semi-bandit scenario are very standard, also with standard proof techniques. I have to say that there are some nice points in the technical argument (such as the arguments after Eqn. (3)), but those are not sufficient for a solid contribution. The most challenging part is the full-bandit setting, which is the part I wish the authors to do the best job, is not very satisfactory (see next point). 

2. The regret analysis for the full-bandit setting is potentially loose without a matching lower bound. This point is important to me, mainly because of my expectation that the current upper bound may not be tight. Currently an explore-then-exploit algorithm is employed, but it is widely known in the bandit literature that this type of algorithm may give a loose regret bound; for example, even for the vanilla multi-armed bandit problem, a naive explore-then-commit policy suffers from the O(T^{2/3}) regret. Therefore, in my opinion it is unfortunate that the authors can only analyze such type of policies, leaving an important question on the tight behavior of the optimal regret. 

3. The proof of the lower bound in Theorem 4 is incorrect. At my first looking I was very surprised that the log T factor is also in the lower bound, but after checking the proof I found the mistake in the argument. The main mistake is the assumption above Eqn. (18): the authors essentially used the proof of the gap-dependent lower bound, and assumed that the expected regret under one instance is o(T^a) for any a>0. However this is not the case in the proof of Theorem 4 - a proof by contradiction in Theorem 4 can only make the above assumption for a > 1/2, because a polynomial regret with low degree is still okay. The argument used by the authors is to establish the logarithmic regret lower bound, which cannot be directly applied to argue a polynomial regret lower bound. Also, the little o notation here is very dangerous, because it hides the dependence on other parameters such as c and d. Consequently, now I also don't know of the correct dependence on (c,d) in corrected Theorem 4 now. 

4. Continuing on the point of lower bounds, the proof of Theorem 2 seems to be over-complicated. Even for the static version of this problem where we only care about finding a near-optimal action at time T+1, a simple Le Cam's two-point method could result in an \Omega(1/sqrt(T)) lower bound, so they add up to \Omega(sqrt(T)). I do not understand why the current argument involves so much computation and spans several pages... 

Post-rebuttal feedback: 

Thanks to the authors for the detailed feedback, especially pasting full revised proof in the rebuttal - I appreciate it. However, many of my concerns are not satisfactorily addressed, and I also have some comments on the rebuttal: 

1. The authors mentioned a few times in the rebuttal that they achieve *tight* regret bounds that *fully* capture the influences of covariance. However, this is a strong statement and does not seem to be the case to me. 

1.1. Tightness. The current regret bounds are provably tight *only* in terms of the dependence on $T$, and even this dependence may not be tight in the most interesting case with fully bandit feedback. In terms of other parameters, such as $d, c$ or some properties of $\theta^*, \Sigma^*$, the tightness is still unknown. So in my opinion I cannot fully appreciate the claimed tightness of the results. 

1.2. Influence of covariance. The authors only derived *upper bounds* of the regret involving the influence of covariance. The tightness of these upper bounds is unknown - so in principle these bounds could even be said to be a bit arbitrary. Overall it is too strong a claim to say that this influence is fully captured. 

2. Comparison to [Degenne and Perchet 2016] seems a bit problematic. In the rebuttal, the authors mentioned that Theorem 1 improves over the result in [Degenne and Perchet 2016]. However, based on my own reading, I believe that [Degenne and Perchet 2016] considered the semi-bandit setting, while Theorem 1 is on the full information setting. So this comparison is a bit unfair. 

3. Contribution of Theorem 2: the authors mentioned in the rebuttal that this is a novel lower bound analysis procedure under the Bayesian environment. However, to the reviewer's expertise, this is mostly a standard Bayes computation, and much simpler (also standard) analysis could also lead to the $\Omega(\sqrt{T})$ lower bound. 

4. Contributions of Theorems 1 and 3: I agree with the authors that some steps in the upper bound analysis are nice technical contributions - this is also reflected in my original review. Nevertheless, currently these steps are hidden in the proof, and one cannot fully appreciate these steps unless he/she reads the proof carefully. If these are solid contributions of independent interest, the authors should extract them and present them independently in the main text, in order for the reviewer to assess its significance. 

5. Full-bandit setting: in my understanding, this should be the most important part of the paper, as the previous fully-exploit and UCB-type algorithms are somewhat light ideas. The reviewer thinks that a tight dependence on $T$ should at least be obtained in this setting, and the explore-then-commit idea are a little bit too light - bandit is an art of combining exploration and exploitation, so algorithms separating these parts (without sufficient motivation, i.e. optimality guarantees of doing so) are often questionable. 

6. Corrected proof of Theorem 4: thank you for providing the detailed proof steps - I did a high-level check and they all seem correct. But as I said in my original review, this is still a standard bandit lower bound analysis, especially when only the right dependence on $T$ is obtained. The authors should at least try to find the right dependence on other parameters including $c$ and $d$. 

In summary, the reviewer regrets not being able to recommend acceptance in the current form, and decides to keep my score. 

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies continuous mean covariance bandits under three feedback scenarios, and proposes three algorithms. For full information (FI) and semi-bandit (SB) feedback, the authors also derive matching lower bounds up to logarithmic factors, showing that the proposed algorithms are  essentially optimal. For the full bandit (FB) setting, they propose an Explore then Exploit algorithm, which has a T^(2/3) regret, and lower bound is left open. The experimental section validates the performance of the proposed algorithms for various correlation structures.
main_review: The problem considered is well motivated and challenging, and the ability to work with arbitrary correlation structure is welcome. The noise is restricted to sub-Gaussian, which is okay for now.

The paper does a good job of presenting the upper and lower bounds and highlighting the analytical novelties involved in the proof. One gets an impression that for the FB setting, there should be a better algorithm than ETE, but the challenges involved are non-trivial.


Overall, this paper considers a good problem and is competently executed. 
limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Existing literature on risk-aware bandits focuses on risk measures of individual 
options such as variance. The paper considers decision making problems with correlated
options. A novel Continuous Mean-Covariance Bandit (CMCB) model is proposed. Agent chooses
weight vectors on given options and observes noisy feedback. The agent's
objective is to balance reward and risk, which is measured by option covariance.
Three settings are considered: full-information, semi-bandit, and full-bandit. 
Algorithms and regret upper bounds are provided for all the three settings. Lower bounds 
are proved for the full-information and semi-bandit setting. The results are validated 
using numerical experiments.  
main_review: Originality: The problem considered is interesting and difficult. There is novelty in the 
technical analysis of the problem. It is clear how this work differs from previous work
on risk-aware bandit problems. Related work seems to be adequately cited.     

Quality: The submission is technically sound. The claims are well supported by the theoretical
analysis and experiments. The authors also provide enough commentary on the
intuition behind their analysis and the results. This is a complete piece of work. The authors
are honest about the limitations and weaknesses of their results.  

Clarity: The paper is well written. It is well organized and it adequately informs the reader. 
I do have some minor queries in Limitations section and their redressal could make the paper 
more informative.  

Significance: The results are compelling. The risk-aware bandit literature has been growing
in the past few years and I think this paper has nice techniques as well as open problems 
that would be interesting to other researchers. In particular, the paper addresses the 
vector analogue of standard mean-variance bandit problem and I think that is non-trivial.
limitations_and_societal_impact: 1. I think there is a $d^{3/2}$ dependence in the upper bound in SB case while the lower bound 
has an interesting dependence on $c$ and $d.$ When $c$ is small, the problem is almost like 
the full information setting and the lower bound also has that flavor. The regret upper bound
doesn't seem to take this into consideration. Do you have ideas on how the regret bound can be
improved? More importantly, it might be good to provide intuition on setting the 
regularization parameter and how it depends on $c.$

2. Please explain what $\Delta_{\max}$ is in Theorem~5. From the appendix, it seems that is a consequence
of the exploration phase but I couldn't find a definition or an explanation.     

3. Is it possible to extend your results to the case where the noise is sub-exponential or heavy-tailed
with bounded covariance? You have used results from [1] for covariance concentration and the results
proved there hold for distributions satisfying a particular definition of sub-Exponential 
distribution which is more general than sub-Gaussian.

[1] Perrault, Pierre, Michal Valko, and Vianney Perchet. "Covariance-adapting algorithm for semi-bandits with application to sparse outcomes." Conference on Learning Theory. PMLR, 2020.
review_title: null

Meta-review: This paper considers the mean-variance bandit setting with a continuous action space on the probability simplex. They considered three settings: the full information setting, the semi-bandit setting, and the full-bandit setting. 

This problem is interesting, and the authors and reviewers have engaged in detailed technical discussions. After reading all the discussions, I regretfully have to say that I cannot recommend acceptance. The major reason is that the technical contribution of this paper is too weak. 

Bandit has a very rich literature, and the bar of a good paper in this literature has become very high since it is already very standard to apply well-known techniques to obtain some bounds, and usually in the literature people focus on very refined questions such as getting the best instance dependent bound, getting the exact exponent of the logarithmic factor, etc. It would not cross the threshold if one just has some sublinear rate. 

In particular, for this paper, it is quite clear that the authors are not familiar with the general bandit literature, have made mistakes in their claims, and have used overly sophisticated arguments to show simple results. What is more, in the most interesting full-bandit case, the authors only analyzed an extremely simple algorithm with a suboptimal rate. 

I would recommend that the authors slow down and study the bandit literature more carefully, and investigate the full-bandit setting with more patience. This is a good question, but the current contribution is not enough for a NeurIPS paper. I believe the authors have the ability to do it, and after it is done, this could be a much stronger submission. 
Decision: Accept (Poster)