Continuous Mean-Covariance Bandits
Authors: Yihan Du
Siwei Wang
Zhixuan Fang
Longbo Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: risk-aware bandits
mean-covariance metric

Abstract: Existing risk-aware multi-armed bandit models typically focus on risk measures of individual options such as variance. As a result, they cannot be directly applied to important real-world online decision making problems with correlated options. 
In this paper, we propose a novel Continuous Mean-Covariance Bandit (CMCB) model to explicitly take into account option correlation. Specifically, in CMCB, there is a learner who sequentially chooses weight vectors on given options and observes random feedback according to the decisions. The agent's  objective is to  achieve the best trade-off between reward and risk, measured with option covariance. To capture different reward observation scenarios in practice, we consider three feedback settings, i.e., full-information, semi-bandit and full-bandit feedback. 
We propose novel algorithms with optimal regrets (within logarithmic factors), and provide matching lower bounds to validate their optimalities. The experimental results also demonstrate the superiority of our algorithms.  
To the best of our knowledge, this is the first work that considers option correlation in risk-aware bandits and explicitly quantifies how arbitrary covariance structures impact the learning performance.
The novel analytical techniques we developed for exploiting the estimated covariance to build concentration and bounding the risk of selected actions based on sampling strategy properties can likely find applications in other bandit analysis and be of independent interests. 

Continuous Mean-Covariance Bandits
Yihan Du
Siwei Wang CST, Tsinghua University
MSS, Tsinghua University
Beijing, China
Beijing, China
duyh1 1oyy1880mils tsinghua. edu.
wangsw20200mail wtt.imaa...tstnnnaaaeeaa tsinghua.een edu. en
Zhixuan Fang
Longbo Huang"
III.. Tsinghua University, Beijing, China Shanghai Qi Zhi Institute, Shanghai, China zfang@mail tsinghua, edu. on
IIIS, Tsinghua University
Beijing, China
longbohuang@mail. tsinghua. edu,
Abstract
Existing risk-aware multi-armed bandit models typically focus risk measures of individual options such as variance. As result, they cannot be directly applied important real-world online decision making problems with correlated options. In this paper, we propose a novel Continuous Mean-Covariance Bandit (CMCB) model explicitly take into account option correlation. Specifically, in CMCB, there a learner who sequentially chooses weight vectors on given options and observes random feedback according the decisions. The agent's objective is to achieve the best trade-off between reward and risk, measured with option covariance. To capture different reward observation scenarios in practice, we consider three feedback settings, i.e., full-information, semi-bandit and full-bandin feedback. We propose novel algorithms with optimal regrets (within logarithmic factors), and provide matching lower bounds to validate their optimalities. The experimental results also demonstrate the superiority our algorithms. To the best of our knowledge, this is the first work that considers option correlation in risk-aware bandits and explicitly quantifies how arbitrary covariance structures impact the learning performance. The novel analytical techniques we developed for exploiting the estimated covariance to build concentration and bounding the risk selected actions based sampling strategy properties can likely find applications in other bandit analysis and be independent interests.
Introduction
The stochastic Multi-Armed Bandit (MAB) [3, 28, 2) problem is classic online learning model, which characterizes the opplorationeexlloitatoonn trade-off in decision making. Recently, due to the increasing requirements of risk guarantees in practical applications, the Mean- Mean-Variamt Variance Bandits (MVB) [26, 30, 34] which aim at balancing the rewards and performance variances have received extensive attention. While MVB provides successful risk-aware model, it only considers discrete decision space and focuses on the variances individual arms (assuming independence among arms).
However, in many real-world scenarios, a decision often involves multiple options with certain correlation structure, which can heavily influence risk management and cannot be ignored. For instance, in finance, investors select portfolios multiple correlated assets, and the investment risk is closely related to correlation among the chosen assets. The well-known "risk diversification" strategy [4] embodies the importance of correlation investment decisions. In clinical trials,
*Correpooning author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

treatment often consists of different drugs with certain ratios, and the correlation among drugs plays an important role the treatment risk. Failing handle the correlation among multiple options, existing MVB results cannot be directly applied to these important real-world tasks.
Witnessing the above limitation of existing risk-aware results, in this paper, propose novel Continuous Mcan-Covariance Bandit (CMCB) model, which considers a set of options (base arms) with continuous decision space and measures the risk of decisions with the option correlation. Specifically, in this model, a learner is given d base arms, which are associated with an unknown joint reward distribution with a mean vector and covariance. At each timestep, the environment generates an underlying random reward for each base arm according to the joint distribution. Then, the learner selects weight vector of base arms and observes the rewards. The goal of the learner is minimize utilities
the expected cumulative regret, i.e., the total difference of the reward- between the chosen actions and the optimal action, where the optimal action defined as the weight vector that achieves the best trade-off between the expected reward and covariance based risk. To capture important observation scenarios in practice, we consider three feedback settings in this model, i.e., full-information (CMCB-FI), semi-bandit (CMCB-SB) and full-bandit (CMCB-FB feedback, which vary from seeing rewards of all options to receiving rewards of the selected options to only observing weighted sum of rewards.
The CMCB framework finds a wide range of real-world applications, including finance [23]. company operation [24] and online advertising [27]. For example, in stock markets, investors choose portfolios based on the observed prices of all stocks full-information feedback), with the goal of earning high returns and meanwhile minimizing risk. In company operation, managers allocate investment budgets to several correlated business and only observe the returns of the invested business (semi-bandit feedback), with the objective of achieving high returns and low risk. In clinical trials, clinicians select a treatment comprised of different drugs and only observe an overall therapeutic effect (full-bandit feedback), where good therapeutic effects and high stability are both desirable.
For both CMCB-FI and CMCB-SB, we propose optimal algorithms (within logarithmic factors) and establish matching lower bounds for the problems, and contribute novel techniques in analyzing the risk of chosen actions and exploiting the covariance information. For CMCB-FB, we develop a novel algorithm which adopts a carefully designed action set to estimate the expected rewards and covariance, with non-trivial regret guarantees. Our theoretical results offer an explicit quantification of the influences of arbitrary covariance structures on learning performance, and our empirical evaluations also demonstrate the superior performance of our algorithms.
Our work differs from previous works on bandits with covariance [32, 33, 11, 25] in the following aspects. (i) We consider the reward-risk objective under continuous decision space and stochastic environment, while existing works study either combinatorial bandits, where the decision space discrete and risk not considered in the objective, or adversarial online optimization. (ii) We do not assume prior knowledge or direct feedback on the covariance matrix as in [32, 33, 11]. (ii) Our results for full-information and full-bandit feedback explicitly characterize the impacts of arbitrary covariance structures, whereas prior results, e.g., [11, 25], only focus on independent or mositively-correlat cases. These differences pose new challenges in algorithm design and analysis, and demand new analytical techniques.
We summarize the main contributions as follows.
We propose a novel risk-aware bandit model called continuous mean mncan-covariance bandit (CMCB), which considers correlated options with continuous decision space, and char- acterizes the trade-off between reward and covariance- based risk. Motivated by practical reward observation scenarios, three feedback settings are considered under CMCB, i.e., full-information (CMCB-FI), remi-bandit (CMCB-SB, (BB and full-bandit (CMCB-FB).
We design an algorithm MC- VC-EEmirrical for CMCB-FI with an optimal O(VT) regret (within logarithmic factors), and develop novel analytical technique to build relationship on risk between chosen actions and the optimal one using properties of the sampling strategy. We also derive matching lower bound, by analyzing the gap between hindsight knowledge and available empirical information under a Bayesian environment.
For CMCB-SB, we develop MC-UCB, an algorithm that exploits the estimated covariance information to construct confidence intervals and achieves the optimal O(VT) regret (up to

---

logarithmic factors). A matching regret lower bound is also established, by investigating the necessary regret paid to differentiate two well-chosen distinct instances.
We propose novel algorithm MC-ETE for CMCB-FF which employs a well-designed action set to carefully estimate the reward means and covariance, and achieves an O regret guarantee under the severely limited feedback.
To our best knowledge, our work is the first to explicitly characterize the influences of arbitrary covariance structures on learning performance in risk-aware bandits. Our results shed light into optimal risk management in online decision making with correlated options. Due to space limitation, we defer all detailed proof' the supplementary material.
Related Work
(Risk-aware Bandits) Sani et al. [26) initiate the classic mean-variance paradígm [23, 14] in bandits, and formulate the mean-variance bandit problem, where the learner plays a single arm each time and the risk is measured by the variances of individual arms. Vakili & Zhao [29, 30] further study this problem under a different metric and complete the regret analysis. Zhu & Tan [34] provide Thompson Sampling-band -ased algorithm for mean-variance bandits. In addition to variance, several works consider other risk criteria. The VaR measure is studied in [10]. and CVaR is also investigated to quantify the risk in [13, 16]. Cassel al. [5] propose general risk measure named empirical distributions performance measure (EDPM) and present an algorithmic framework for EDPM. All existing studies on among arms, and thus they cannot be applied to our CMCB problem.
bandits only consider discrete decision space and assume independence
(Bandits with Covariance) In the stochastic MAB setting, while there have been several works [1] 25] on covariance, they focus on the combinatorial bandit problem without considering risk. Degenne & Perchet [11] study the combinatorial semi-bandit, with correlation, which assume a known upper bound on the covariance, and design an algorithm with this prior knowledge of covariance. Perrault al. [25] further investigate this problem without the assumption on covariance under the sub- exponential distribution framework, and propose an algorithm with a tight asymptotic regret analysis. In the adversarial setting. Warmuth & Kuzmin [32, 33] consider an online variance minimization problem, where at each timestep the learner chooses weight vector and receives a covariance matrix, and propose the exponentiated gradient based algorithms. Our work differs from the above works in the following aspects: compared to [11, 25], we consider a continuous decision space instead of combinatorial space, study the reward-risk objective instead of only maximizing the expected reward, and investigate two more feedback settings other than the semi-bandit feedback. Compared to [32, 33], we consider the stochastic environment and in our case, the covariance cannot be directly observed and needs to be estimated.
3 Continuous Mean-Covariance Bandits (CMCB)
Here we present the formulation for the Continuous Mcan-Covariance Bandits (CMCB) problem. Specifically, a learner is given base arms labeled 1,..., and decision (action) space D C Da where A. = (w E Rdd : S wy < 1, Vi E [d], Σ, wi = 1} denotes the probability simplex in Rd The base arms are associated with an unknown d-dimensional joint reward distribution with mean vector 0* and positive meni-defintte covariance matrix E", where Σ; < 1 for any E [d] without loss of generality. For any action w e D, which can be regarded as a weight vector placed on the base arms, the instantancous reward-risk utility is given by the following meva-covariance function
f(w) = w T 0" pw Σ'w,
(1)
where w 0" denotes the expected reward, w Σ represents the risk, i.e., reward variance, and >> 0 is risk-aversion parameter that controls the weight placed on the risk. We define the optimal action as w² = argmaxwec p fw). Compared to linear bandits [1, 17], the additional quadratic term in fww raises significant challenges in estimating the covariance, bounding the risk of chosen actions and deriving covariance-dependen regret bounds.
At each timestep I, the environment generates an underlying (unknown to the learner) random reward vector 0, = 0 7h according to the joint distribution, where T7 is zero-mean noise vector and it is
3

---

Algorithm 1 MC-Empirical
1: Input: Risk-aversion parameter p 0.
4:
w. argmax w 00;- pw E 1W) wEAd
2: Initialization: Pull action wh = 7: ... 2)
and observe 0 (01,1....,, 0,,1) __ 87,4 t
5:
Pull we observe O. = (0,,1, 0c,a)
81,6, Vi E [d]. Σ1,3 = (f1,: 0 (01.)
6:
Oi \ 22 Osii, Vi E [d]
01,5). Vi,j E [d].
-
- 5((+,, 0 (r.,0 07 Vii.j Eld]
3: for = 2, 3, do
8: end for
independent among different timestep Note that here we consider an additive vector noise the parameter 0" instead of the simpler scalar noise added in the observation (i.e., Vr = w 0 m))
as in linear bandits [1. 17]. Our noise setting better models the real- scenarios where distinct actions incur different risk, and enables to explicitly quantify the correlation effects. Following the
standard assumption in the bandit literature [22, 11, 34], we assume the noise is sub-Gaussian, i.e.,
Vu E IRd, E[exp(u :7:] S exp(' E),), where E* is unknown. The learner selects an action we E DD and observes the feedback according to a certain structure (specified later). For any time horizon T >> 0, define the expected cumulative regret as
E R
[T)
Σ E [f(w*)) f(w:)).
The objective of the learner is minimize E (T)) Note that our mean-covariance function Eq. (1) extends the popular mean-variance measure [26, 30, 34) to the continuous decision space.
In the following, we consider three feedback settings motivated by reward observation scenarios in practice, including (i) full-information (CMCB-FI), observing random rewards of all base arms after pull, (ii) semi-bandit (CMCB-SB), only observing random rewards of the selected base arms, and (ii)) full-bandit (CMCB-FB). only seeing a weighted sum of the random rewards from base arms. We will present the formal definitions of these three feedback settings in the following sections.
Notations. For action w E DD, an be a diagonal matrix such that Ju,i T(w; > 0}. For a matrix A, let A AT and A be diagonal matrix with the same diagonal as A.
4 CMCB with Full-Information Feedback (CMCB-FI)
We start with CMCB with full-information feedback (CMCB-FI), In this setting, at each timestep f, the learner selects w, E As and observes the random reward ot,, for all i E: [d]. CMCB- F-FI provides an online learning model for the celebrated Markowitz [23, 14) problem in finance, where investors select portfolios and observe the prices of all stocks at the end of the trading days.
Below, we propose an optimal Mean-Covane Covarinnee Empirical algorithm (MC-Empirical) for CMCB-FI, and provide a novel regret analysis that fully characterizes how an arbitrary covariance structure affects the regret performance. We also present a matching lower bound for CMCB-FI to demonstrate the optimality of MC- HC-mmairica..
4.1 Algorithm for CMCB-FI
Algorithm shows the detailed steps of NC-Empirical. Specifically, at each timestep t, we use the empirical mean 0, and covariance Er to estimate 0' and Σ*, respectively. Then, we form fi(w) = w 0, pw T "i.. an empirical mean-covariance function of w E Da. and always choose the action with the maximum empirical objective value.
Although MC-Empirical appears to be intuitive, its analysis is highly non-trivial due to covariance- based risk in the objective. In this case, naive universal bound cannot characterize the impact of covariance, and prior gap-dependent analysis (e.g., [11, 25]) cannot be applied solve our continuous space analysis with gap approximating to zero. Instead, we develop two novel techniques to handle the covariance, including using the actual covariance to analyze the confidence region of the expected rewards, and exploiting the empirical information of the sampling strategy to bound the

---

risk gap between selected actions and the optimal one. Different from prior works [11, 25]. which assume a prior knowledge on covariance or only focus on the independent and positively-relate cases, our analysis does not require extra knowledge of covariance and explicitly quantifies the effects of arbitrary covariance structures. The regret performance of MC-Empirical summarized in Theorem 1.
Theorem (Upper Bound for CMCB-FI). Consider the continuous mean-covariance bandits with full-information feedback (CMCB-FI). For any T > 0, algorithm MC-Empirical (Algorithm I) achieves an expected cumulative regret bounded by
of (((min (Vo"" ""'"" + +p +== VV Ominn Dmax +D) InTVV)
0maxx
where 0max = m18X)e[[d] 0,, Oiin - mingela 0, and Eiaxx = max Ei.-
Proof sketch. Let Dr be the diagonal matrix which takes value at each diagonal entry. We first build confidence intervals for the expected rewards of actions and the covariance as |w" 0 w 0 S
Pe(w) cI Vind// wT DJ (AAz- D.-1 + - D' and M Σng,-1l S 2 02 -
lnt
Here A "0" Ty: wt. and cı, C2 are positive constants. Then, we obtain the confidence interval Xim
of f(w) as (ww) - f(w)) I rr(w) - (ww) + pw Q,w, where Qe is a matrix with all entries equal to gt. Since algorithm MC- MC-Empirical always plays the empirical best action, we have f(w)) fw,) S fi-1 (wo) ) (rr(w))-f( Plugging the definitions of f(w) and r: (ww), we have
I f(-1(w)) +r((w") f(we) S re(w") (ww)).
-p ww E"w, w Σ Enw²" < <((w") ((w)) @ ezlnt (Vw" E + VV/ w, Σ En
(3)
V--
where Ag. 0 om and 03 is positive constant. Since our goal is to bound the regret f(w") - f(w, and in inequality (a) only the / E" term is a variable, the challenge falls on bounding w. E, Note that the left-hand-side of Eq. (3) is linear with respect to w, E'w, and the right-hand-side only contains Vw, E' Then, using the property of sampling strategy on w.. i.e. Eq. (3), again, after some algebraic analysis, we obtain w, E"w, S <cl(w" E'"w" + -
Inf (²(c-1)) for some constant C4. Plugging into inequality (a) and doing summation over we obtain the theorem.
Viw En + Int Int t-1
VI-I +
Remark 1. As we will show in Section 4.2, this O(VT) regret matches the lower bound up to logarithmic factor. Moreover, Theorem fully characterizes how an arbitrury covariance structure impacts the regret bound. To see this, note that in Eq. (2), under the min operation, the first Ve= 2-ww-reeated term dominates under reasonable p. and shrinks from positive to negative correlation, which implies that the more the base arms are negatively (positively) correlate, the lower (higher) regret the learner suffers. The intuition behind is that the negative (positive) correlation diversifies (intensifies) the risk of estimation error and narrows (enlarges) the confidence region for the expected reward an action, which leads to a reduction (an increase) of regret.
Also note that when = 0, the CMCB-FI problem reduces to a d-armed bandit problem with full-information feedback, and Eq. (2) becomes Ō Er EEnay T). For this degenerated case, the optimal
gap-dependent regret is 0 =iii)))) for constant gap A > 0. By setting A V /Emax/ T at this gap-dependent result, one obtains the optimal gap-independent regret O ( Eiaax T). Hence, when p Eq. (2) still offers a tight gap- inddieddeendent regret bound.
4.2 Lower Bound for CMCB-FI
Now we provide a regret lower bound for CMCB-FI, which demonstrates that the O(VT) regret of MC-Empirical is in fact optimal (up to logarithmic factor).
Since CMCB-FI considers full-information feedback and continuous decision space where the reward gap A (between the optimal action and the nearest optimal action) approximates to zero, existing lower bound analysis for linear [8, 9] or discrete [19, 11, 25] bandit problems cannot be applied to this problem.
5

---

Algorithm 2 MC-UCB
1: Input: 0, (0, } and regularization
6:
wif argmax 0 -prii Ixw) wEbs
parameter 0.
2: Initialize: Vi [d]. pull e, that has 1 at the i-th entry and 0 elsewhere. Vi,j E [d], * pull Gij that has the j-th entries, and O elsewhere. Update (d)( Vi,j E [d]. Og and Exe.
7:
Pull we and observe all O2, s.t. We,i >
8:
Jr,ú5 < I[ Wt,j > 0}, Vi.j E [d]
the i-th and
9:
Noy(t) Nos(t - 1) Je.s Vi.j E [d]]
0 t Sinhen Vi E [d] Ni(())
10:
3: for = dl + +1... do
Errrs(00, X (..)
11: E1,i'
Wi.jeld
4: Eng t Σi-1. - 9ty(t)
No)
5: Egg t Em-1. + (t)
12: end for
To tackle this challenge, we contribute a new analytical procedure to establish the lower bound for continuous and full-information bandit problems from the Bayesian perspective. The main idea is to construct an instance distribution, where 0* is drawn from a well-chosen prior Gaussian distribution. After pulls the posterior of 0* is still Gaussian with mean vector u, related to sample outcomes. Since the hindsight strategy simply selects the action which maximizes the mevn-covariance function with respect to O while feasible strategy can only utilize the sample information (u;), we show that any algorithm must suffer 1((VT) regret due the gap between random 0 and its mean un Theorem below formally states this lower bound.
Theorem 2 (Lower Bound for CMCB-FI). There exists an instance distribution of the continu- ous mean-covariance bandits with full-information feedback problem (CMCB-FI), for which any algorithm has an expected cumulative regret bounded by Si( SI(TT).
Remark 2. This parameter-free lower bound demonstrates that the regret upper bound (Theorem 1) of MC-Empirical is optimal (within a logarithmic factor), since under the constructed instance distribution, Theorem also implics a matching Õ(VT) parameter-free result, i.c., when p = 1/VT, Eq. (2) becomes Ó Dimax + +1/VT)/T) = - Ó(VT). Unlike discrete bandit problems [19, 11, 25]
where the optimal regret is usually lo for constant gap A 0, CMCB-FI has continuous decision space with gap - 0 and polylogarithmic regret not achievable in general. such continuous bandit literature [18, 8, 9], the parameter (0", E' and p) dependent lower bound is open problem.
5 CMCB with Semi-Bandit Feedback (CMCB-SB)
In many practical tasks, the learner may not be able to simultaneously select (place positive weights on) all options and observe full information. Instead, the weight of each option is usually lower bounded and cannot be arbitrarily small. As a result, the learner only selects a subset of options and obtains their feedback, e.g., company investments [12] on multiple business.
Motivated by such tasks, in this section we consider the CMCB problem with semi-bandit feedback (CMCB-SB), where the decision space is restricted probability simplex A = {wr E Rdd w; = 0 or e S S Vi E [d] and E, W/ = }} for some constant 0 < < timestep f, the learner selects w. E AS and only observes the rewards {0r,: w, 2 c} from the base arms that are placed positive weights on. Below, we propose the Mean-Covariance Upper Confidence Bound algorithm (MC-UCB) for CMCB-SB, and provide a regret lower bound, which shows that MC-UCB achieves the optimal performance with respect to T.
12 In this scenario, at 2-
5.1 Algorithm for CMCB-SB
Algorithm MC-UCB for CMCB-SB is described in Algorithm The main idea is to use the optimistic covariance to construct a confidence region for the expected reward of an action and calculate an upper confidence bound of the mean-cove covarrinee function, and then select the action with the maximum optimistic covariance value.
WWhen e > }. the learner can only place all weight one option, and the problem trivially reduces to the mean-variance bandit setting [26, 34]. In this case, Theorem 3 still provides tight gap-int independent bound.

---

In Algorithm 2, No5 (t) denotes the number of times Wa Way > 0 occurs among timestep E [t]. Je,y is an indicator variable that takes value if Wr,i, Wt, > and otherwise. D, diagonal matrix such that D, (t). ). In Line we update the number of observations by [u(c 2d-1 for all E [d] and Niy(d) + 2 for all i,j E [d], # j (due the initialized d? pulls), and calculate the empirical mean f/ and empirical covariance Egz using the equations in Lines 10,11.
For any > 1 and i,j E [d]. we define the confidence radius of covariance Σig as (1)(1) -
3 f 16(
V
31nt (t-1-
+ (Gg(t-1),,(t-1
48in2t
36 Wu(l-1)N,(t-1) and the confidence region
No (f-1)
for the expected reward w 0* of action
t-1
E((w)= A 28(5.) w TT TODDi-1 AAg, D +
E D Dillw)
where À > 0 is the regularization parameter, 3(6,) = ln( + In Int (n+++))+)))+++++++++))++)))++ (n is the confidence term and 6 2 is the confidence parameter. At each timestep i, algorithm MC-UCB calculates the upper confidence bound of f (ww) using (ty(t) and (w)) and selects the action wi that maximizes this upper confidence bound. Then, the learner observes rewards 8G,, with Wt,i > 0 and update the statistical information according to the feedback.
In regret analysis, unlike [11] which uses a universal upper bound to analyze confidence intervals, we incorporate the estimated covariance into the confidence region for the expected reward of an action, which enables us to derive tighter regret bound and explictly quantify the impact of the covariance structure algorithm performance. We also contribute challenge raised by having different numbers of observations among base arms, in order to obtain an optimal OVVT) regret (here prior eap-dependent analysis [11, 25] still cannot be applied to solve this continuous problem). Theorem 3 gives the regret upper bound of algorithm MC-UCB.
technique for handling the
Theorem 3 (Upper Bound for CMCB-SB), Consider the continuous mean-covariance bandits with semi-bandic feedback problem (CMCB-SB). Then, for any T > O, algorithm MC-UCB (Algorithm 2) with regularization parameter À >> O has expected cumulative regret bounded by
(V L(XIE ||+ +2 In T. T pd TVT).
where L(A) = (A + (I + + + 1) and || Ex (Mgy V 0) for any i,j E [d].
Remark 3. Theorem 3 captures the effects of covariance structures in CMCB-SB, i.e., positive correlation renders a larger || ||+ factor than the negative correlation or independent case, since the covariance influences the rate of estimate concentration for the expected rewards of actions. The regret bound for CMCB-SB has a heavier dependence on d than that for CMCB-FL. This matches the fact that information than cull-nnformaiin feedback in terms observable dimensions.
feedback only reveals rewards of the queried dimensions, and provides less
5.2 Lower Bound for CMCB-SB
In this subsection, we establish lower bound for CMCB-SB, and show that algorithm MC-UCB achieves the optimal regret with respect to T up to logarithmic factors.
The insight of the lower bound analysis is to construct two instances with gap in the expected reward vector 0*, where the optimal actions under these two instances place positive weights on different base arms. Then, when the gap is set to T/T,, any algorithm must suffer 52 (VThn In regret for differentiating these two instances. Theorem 4 summarizes the lower bound for CMCB-SB.
Theorem (Lower Bound for CMCB-SB), There exists an instance distribution of the continuous mean-covatee mhea--ovarrinnee bandits with semi-banda feedback (CMCB-SB) problem, for which any algorithm has an expected cumulative regret bounded by Ω (VedT)
Remark 4. Theorem demonstrates that the regret upper bound (Theorem 3) of MC-UCB optimal with respect to T (up logarithmic factors). Similar to CMCB-FI, CMCB-SB SB considers continuous
7

---

Algorithm 3 MC-ETE
1: Input: p 0, d(d+1) and design action
12:
VN. (8) (YN. (8), (N)())))
set πT = ( vdl.
EN Me
2: Initialize: (0) 0. 1
13:
9: + N+(e)
3: Repeat lines 4-22:
14:
&1, = ENG - Be.e)²
.4k E [d]
4: if (4 - 18 1 then
No
15:
2, f- ( 2,,
5: wt argmax (w 0 1-1 pro
E
wEAd
16:
0 B yt
6: t ++
17:
o, t C &t
7:
else
18:
Reshape 8; to d x d matrix Σ, end if
8:
(t) + (t- 1)+1
19:
9:
for k = 1,... do
20:
t++
10:
Pull Us and observe (0)
21:
end for
if k d then
22:
end if
decision space with A 0. and thus the lower bound differs from those gap-dependent results log in discrete bandit problems [19, 11, 25]. Our lower bound shows that for CMCB-SB, no improvement upon O(VT) regret is possible in general.
CMCB with mall-Bandit Feedback (CMCB-FB)
In this section, further study the CMCB problem with full-bandit feedback (CMCB-FB), where timestep t. the learner selects w; E Aa and only observes the weighted sum of random rewards, i.c. y/ w, O,. This setting models many real-world decision making tasks, where the learner can only attain an aggregate feedback from the chosen options, such as clinical trials [31].
6.1 Algorithm for CMCB-FB
We propose the Covariine Exploration- www---hhee----tttieee algorithm (MC-ETE) for CMCB- FB in Algorithm 3. Specifically, we first choose a design action set क (.,,..., 02) which contains d = d(d + 1)/2 actions and satisfies that B = (v] :.......].. and Cx (vf. 20,,1 10 2.. 20 Vd 20 vd,a) are of full column rank. We also denote their Moore-Penrose inverses by B and C#. and it holds that B B2 Idxd and C+C, C₂ páxd There exist more than one feasible æ, and for simplicity and good performance choose vı, Va standard basis vectors in R.d and (da+1,-.-g v2) the set of all (t) vectors where each vector has two entries equal to 1 and others equal to 0.
In an exploration round (Lines 8-21), we pull the designed actions in π and maintain their empirical rewards and variances. Through linear transformation by B and C obtain the estimators of the expected rewards and covariance of base arms (Lines 16-17). When the estimation confidence is high enough, we exploit the attained information select the empirical best action (Lines 5). Theorem presents the regret guarantee of MC-ETE.
Theorem (Upper Bound for CMCB-FB), Consider the continuous mean-covariance bandits with full-bandit feedback problem (CMCB-FB). Then, for any T > O, algorithm MC-ETE (Algorithm 3) achieves an expected cumulative regret bounded by
O (Z T) / /d0' + d2)
d'max T 3
where ((p, π) maxweAd wD B$ (B+ u Tw E diag(e) " "' " v.) ||C max E C and Amax f(w") min As f(w)
The choice of π will affect the regret factor Σ; contained in Z(p. .). Under our construction, Σx can be regarded uniform representation of covariance Σ", and thus our regret bound demonstrates how the learning performance influenced by the covariance structure, i.e., negative (positive) correlation shrinks (enlarges) the factor and leads to lower (higher) regret.
Remark 5.

---

Cumulative Regret
Cumulative Regret
Cumulastve Regret
10
10%
MC MNCEEpirical tours)
MC-UCB (ours)
MC-ETE (ours) OGD-ETE
OND
MCAICR-
30090
2000
30003
40390
DOCCO
Time
(a) FI, synthetic, d = 5. = 0.1
(b) SB, synthetic, d 5, 0.1 (c) FB, synthetic, d 5, 10
Cumulative Regret
Cuumulative Regret
Curulattvv Regret.
60
(ours)
OGD
MC-UCB-F 1
OGD ETE
Linearii
OLS-UCB-C
UnearfB
20330
occco
59030
20668
20020
5900
56660
66002
100030
Time
Time
Time
(d) real-world, d= 5, 0.1 SB, real-world, p 0.1 FB, real-world, = 5, p 10
Figure 1: Experiments for CMCB-FI, CMCB-SB and CMCB-FB on the synthetic and real-world datasets.
Discussion on the ETE strategy. In contrast to common ETE-type algorithms, MC-ETE requires novel analytical techniques in handling the transformed estimate concentration while preserving the covariance information in regret bounds. In analysis, we build a novel concentration using key matrices B and C+ to adapt to the actual covariance structure, and construct super-martinge which takes the aggregate noise in an exploration round as analytical basis to prove the concentration. These techniques allow us to capture the correlations in the results, and are new compared to both the former FI/SB settings and covariance-related bandit literature [33, 11, 25J.
In fact, under the full-bandi, feedback, it is highly challenging estimate the covariance without using a fixed exploration (i.c., ETE) strategy. Note that even for its simplified offline version, where one uses given (non-fixed) full-bandit data estimate the covariance, there is no available solution in the statistics literature to our best knowledge. Hence, for such online tasks with severely limited feedback, ETE is the most viable strategy currently available, as used in many partial observation works [21, 6, 7]. We remark that our contribution in this setting focuses on designing practical solution and deriving regret guarantees which explicitly characterize the correlation impacts. The lower bound for CMCB-FB remains open, which we leave for future work.
Experiments
In this section, we present experimental results for our algorithms on both synthetic and real-world
[20] datasets. For the synthetic dataset, we set 0" = [0.2, 0.3, 0.2, 0.2, 0.2] " and Σ" has all diagonal entries equal to 1 and all off-diagonal entries equal open dataset US Funds from Yahoo Finance on Kaggle [20], which provides financial data of 1680 ETF funds 2010-2017.
-0.05. For the real-world dataset, we use an
select five funds and generate a stochastic distribution (0* and Σ*) from the data of returns (since we study stochastic bandit problem). For both datasets, we set d = 5 and p E 10.1, 10). The random reward 0, is drawn i.i.d. from Gaussian distribution A(0 E+). We perform 50 independent runs for each algorithm and show the average regret and 95% confidence interval across runs, with logarithmic y-axis for clarity of magnitude comparison.
"In some cases, since algorithms are doing similar procedures (e.g.. in Figures (1), the algorithms are exploring the designed actions) and have low performance variance, the confidence intervals are narrow and indistigguishable

---

(CMCB-FI) We compare our algorithm MC- JC-Empirical with two algorithms OGD [15] and LinearFI. OGD (Online Gradient Descent) [15] is designed for general online convex optimization with also a O(vT) regret guarantee, but its result cannot capture the covariance impacts as ours. LinearFI is a linear adaption of NC-Empirical that only aims to maximize the expected rewards. Figures I(a), show that our MC- IiC-Emirrical enjoys multiple orders of magnitude reduction in regret compared the benchmarks, since it efficiently exploits the empirical observations to select actions and well handles the covariance-based risk. In particular, the performance superiority of MC- Empirical over OGD demonstrates that our sample strategy sufficiently utilize the observed information than conventional gradient descent based policy.
(CMCB-SB) For CMCB-SB, we compare MC-UCB with two adaptions of OLS-UCE [11] (state-of-the- art for combinatorial bandits with covariance), named MC-UCB-I and OLS-UCB-C. MC-UCB-I uses the confidence region with a universal covariance upper bound r, instead of the adapting one used in our MC-UCB. OLS-UCB-C directly adapts OLS-UCB [11] to the continuous decision space and only considers maximizing the expected rewards in its objective. As shown in Figures ((b), MC-C),,MUUGG MC-UCB achieves the lowest regret since utilizes the covariance information to accelerate the estimate concentration. Due to lack of a covariance- adapttnng confidence interval, MC-UCB-I" shows an inferior regret performance than MC-UCB, and OLS-UCB-C suffers the highest regret due its ignorance of risk.
(CMCB-FB) We compare MC-ETE with two baselines, OGD-ETE, which adopts OGD [15] during the exploitation phase, and LinearFB, which only investigates the expected reward maximization. From Figures (()) one can see that, MC-ETE achieves the best regret performance due to its effective estimation of the covariance- based risk and efficiency in exploitation. Due to the inefficiency of gradient descent based policy in utilizing information, OGD-ETE has a higher regret than MC-ETE, whereas LinearFB shows the worst performance owing the unawareness of the risk.
8 Conclusion and Future Work
In this paper, we propose a novel continuous mean-covariance bandit (CMCB) model, which investi- gates the reward-risk trade-off measured by option correlation. Under this model, consider three feedback settings, i.e., full-information, semi-bandit and full-bandit feedback, to formulate different real-world reward observation scenarios. We propose novel algorithms for CMCB achieve the optimal regrets (within logarithmic factors), and provide lower bounds for the problems to demon- strate our optimality. We also present empirical evaluations show the superior performance of our algorithms. To our best knowledge, this is the first work to fully characterize the impacts of arbitrary covariance structures on learning performance for risk-aware bandits. There are several interesting directions for future work. For example, how to design an adaptive algorithm for CMCB- FB is challenging open problem, and the lower bound for CMCB- also worth further investigation.
Acknowledgments and Disclosure of Funding
The work of Yihan Du and Longbo Huang is supported in part by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 20004400008000 and 2020AAA0108403.
References
[1] Yasin Abbasi- Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for lincar stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-2320, 2011.
[2] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39-1, 2012.
[3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-256, 2002.
[4] Kirt Butler and Dale L Domian. Risk, diversification, and the investment horizon. Journal of Portfolio Management, 17(3)41, 1991.
[5] Asaf Cassel, Shie Mannor, and Assaf Zeevi. general approach to multi-armed bandits under risk criteria. In Conference on Learning Theory, pages 1295-1306, 2018.
10

---

[6] Sougata Chaudhuri and Ambuj Tewari. Phased exploration with greedy exploitation in stochastic combinatorial partial monitoring games, In Advances in Neural Information Processing Systems, pages 2433-2441. 2016.
[7] Lixing Chen, Jie Xu, and Zhuo Lu. Contextual combinatorial multi-armed bandits with volatile arms and submodular reward. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[8] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory, 2008.
[9] Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008
[10] Yahel David and Nahum Shimkin. Pure exploration for max-quantile bandits. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 556-571. Springer, 2016.
[11] Rémy Degenne and Vianney Perchet. Combinatorial semi-bandit with known covariance. In Advances in Neural Information Processing Systems, pages 2972-2980, 2016.
[12] A Diadin. Analysis of a trade company investment project. Business and Economics, page 104, 2019.
[13] Nicolas Galichet, Michele Sebag, and Olivier Teytaud. Exploration vs exploitation vs safety: Risk-aware multi-armed bandits. In Asian Conference on Machine Learning, pages 245-260,, 2013.
[14] Stephan Gasser, Margarethe Rammerstorfer, and Karl Weinmayer. Markowitz revisited: Social portfolio engineering. European Journal of Operational Reseurch, 181-1119, 2017.
[15] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, (9(2-3):199-199) 2007.
[16) Anmol Kagrecha, Jayakrishnan Nair, and Krishna Jagannathan. Distribution oblivious, risk- aware algorithms for multi-armed bandits with unbounded rewards. Advances in Neural Information Processing Systems, 32: 1271 2019.
[17] Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi-Yadkorf and Benjamin Van Roy. Conservative contextual linear bandits. In Advances in Neural Information Processing Systems, pages 3913-3922, 2017. 2017.
[18] Robert Kleinberg. Nearly tight bounds for the continuun-armed bandit problem. In Advances Neural Information Processing Systems, volume 17. MIT Press, 2005.
[19] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, 6(1):4-22, 1985.
[20] Stefano Leone. Dataset: US funds dataset from yahoo finance. Kaggle, 2020. https:
/ //www. http///teeaaameeeeee///mmaauaaaa funds- and wtwe-eeesseeeeeEEFeeeeee csv.
[21] Tian Lin, Bruno Abrahao, Robert Kleinberg, John Lui, and Wei Chen. Combinatorial partial monitoring game with linear feedback and its applications. In International Conference Machine Learning, pages 2014.
[22] Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In International Conference on Machine Leurning, pages 1690-1698. PMLR, 2016.
[23] Harry M Markowitz et al. Portfolio selection. Journal of Finance, 7(1):77911, 1952.
[24] Joanne McInnerney and Tim Roberts. Online learning: Social interaction and the creation of sense of community. Journal of Educational Technology & Society, 7(3):73-81, 2004.

---

[25] Pierre Perrault, Michal Valko, and Vianney Perchet. Covariance-adapple algorithm for semi- bandits with application sparse outcomes. In Conference on Learning Theory, pages 3152-
3 3184, 2020.
[26] Amir Sani, Alessandro Lazaric, and Rémi Munos. Risk-aversion in multi-armed bandits. In Advances in Neural Information Processing Systems, pages 3275-3283, 2012.
[27] Eric M Schwartz, Eric Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500- 522, 2017.
[28] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):255-294, 1933.
[29] Sattar Vakili and Qing Zhao. Mean-variance and value at risk in multi- bandit problems. The 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1330-1335. IEEE, 2015.
[30] Sattar Vakili and Qing Zhao. Risk-averse multi- armed bandit problems under mean- mean-variance variance measure. IEEE Journal of Selected Topics in Signal Processing, 10161;109-1111,, 2016.
[31] Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical Science: A Review Journal of the Institute of Mathematical Statistics, 30(2): 199, 2015.
[32] Manfred K Warmuth and Dima Kuzmin. Online variance minimization. In International Conference on Computational Learning Theory, pages 514 518. Springer, 2006.
[33] Manfred K Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning. 87(1):1-32, 2012.
[34] Qiuyu Zhu and Vincent YF Tan. Thompson sampling algorithms for mean-variance bandits. International Conference on Machine Learning. 2020.
12


Reviews:
[{"review_id": "uF1FEG8CtVy", "reviewer": "Reviewer_7HJc", "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: \n\n1. 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. \n\n2. 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. \n\n3. 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. \n\nExperimental results are also given at the end. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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: \n\n1. 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). \n\n2. 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. \n\n3. 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. \n\n4. 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... \n\nPost-rebuttal feedback: \n\nThanks 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: \n\n1. 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. \n\n1.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. \n\n1.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. \n\n2. 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. \n\n3. 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. \n\n4. 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. \n\n5. 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. \n\n6. 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$. \n\nIn summary, the reviewer regrets not being able to recommend acceptance in the current form, and decides to keep my score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "sP_xNsB5jt", "reviewer": "Reviewer_1ysV", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\n\nOverall, this paper considers a good problem and is competently executed. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Ge38EDSttR_", "reviewer": "Reviewer_u6Hw", "summary": "Existing literature on risk-aware bandits focuses on risk measures of individual \noptions such as variance. The paper considers decision making problems with correlated\noptions. A novel Continuous Mean-Covariance Bandit (CMCB) model is proposed. Agent chooses\nweight vectors on given options and observes noisy feedback. The agent's\nobjective is to balance reward and risk, which is measured by option covariance.\nThree settings are considered: full-information, semi-bandit, and full-bandit. \nAlgorithms and regret upper bounds are provided for all the three settings. Lower bounds \nare proved for the full-information and semi-bandit setting. The results are validated \nusing numerical experiments.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The problem considered is interesting and difficult. There is novelty in the \ntechnical analysis of the problem. It is clear how this work differs from previous work\non risk-aware bandit problems. Related work seems to be adequately cited.     \n\nQuality: The submission is technically sound. The claims are well supported by the theoretical\nanalysis and experiments. The authors also provide enough commentary on the\nintuition behind their analysis and the results. This is a complete piece of work. The authors\nare honest about the limitations and weaknesses of their results.  \n\nClarity: The paper is well written. It is well organized and it adequately informs the reader. \nI do have some minor queries in Limitations section and their redressal could make the paper \nmore informative.  \n\nSignificance: The results are compelling. The risk-aware bandit literature has been growing\nin the past few years and I think this paper has nice techniques as well as open problems \nthat would be interesting to other researchers. In particular, the paper addresses the \nvector analogue of standard mean-variance bandit problem and I think that is non-trivial.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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 \nhas an interesting dependence on $c$ and $d.$ When $c$ is small, the problem is almost like \nthe full information setting and the lower bound also has that flavor. The regret upper bound\ndoesn't seem to take this into consideration. Do you have ideas on how the regret bound can be\nimproved? More importantly, it might be good to provide intuition on setting the \nregularization parameter and how it depends on $c.$\n\n2. Please explain what $\\Delta_{\\max}$ is in Theorem~5. From the appendix, it seems that is a consequence\nof the exploration phase but I couldn't find a definition or an explanation.     \n\n3. Is it possible to extend your results to the case where the noise is sub-exponential or heavy-tailed\nwith bounded covariance? You have used results from [1] for covariance concentration and the results\nproved there hold for distributions satisfying a particular definition of sub-Exponential \ndistribution which is more general than sub-Gaussian.\n\n[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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "BBrvbveQYgZ", "reviewer": "Reviewer_kCrL", "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)).\nThe 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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:  This paper considers a new risk-aware multi-armed bandits model named continuous mean-covariance bandit\n(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. \nThe authors have adequately cited the prior work and differentiated their work from previous contributions.\n\nQuality: 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.\n\nClarity: 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): \n1. Could you explain how the updates happen in the 'Initialize' part (last line in Step 2) of MC-UCB?\n2. I think $c$ should be input to MC-UCB. Right?\n3. $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}$.\n4. Could you give intuition about how the estimation of rewards and covariance in MC-ETE works? \n5. 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.\n\nSignificance: This work is a good contribution to risk-aware multi-armed bandits literature. \nTo 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.\nOther researchers can use the techniques and policies developed in the paper for their future work on similar problems.\n\n\nPost-rebuttal feedback: After reading other reviewers' comments and responses from authors, I am inclined to keep my score as is.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since this work is a theoretical paper, I do not find any direct negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not find any ethical issue with the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "11"}, "extra_text": {}}]

Author rebuttal:

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)