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...tstnnnaaaeeae 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 2r.,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 Covarianee 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 "... 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 Dmaxx +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) ) (ro(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, Σ Enwit))
(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'm, 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 EEnax T). For this degenerated case, the optimal
gap-dependent regret is 0 =iiia))) for constant gap A > 0. By setting A V /Emax/ T at this gap-dependent result, one obtains the optimal gap-independent regret O ( Eiiax T). Hence, when p Eq. (2) still offers a tight gap-indepe 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 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 mean-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 mnea-covarrinnee 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 > 0, 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 wtte-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": "iyFPbWPUdn8", "reviewer": "Reviewer_nzbx", "summary": "The focus of this paper is the management of risk in stochastic multi-armed bandits, specifically when the reward distributions of the arms are correlated (as can happen in practical portfolio management scenarios). This problem requires a solution that takes into account covariances. The authors devise solutions under three different forms of feedback, and provide algorithms, lower and upper bounds on the risk-incorporated regret in each case (except for a lower bound in the CMCB-FB setting). They also validate their algorithms empirically on a suite of synthetic problem instances.", "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 is well-motivated. The paper is well-written. The contributions are significant. My only critical comment is that the paper does not test the proposed algorithms on real data sets. Given the setting, it seems conceivable that stock prices or other such time-series data from the financial domain will exhibit the characteristics (correlated signals) that are explicitly being addressed by the paper. It will reinforce the foundational assumption of the paper to show real data on which traditional notions of risk (based on variance alone) are unsatisfactory. Moreover, it would make a compelling case for the paper to demonstrate on the same data set that the proposed approaches indeed deal much better with the correlations.\n\nPost-rebuttal: I appreciate that the authors have provided a new set of results, as requested. The submission becomes stronger; I change my score from 6 to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any substantive negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issue.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "2nzthPqQRS", "reviewer": "Reviewer_S7fm", "summary": "The paper presents a novel set of methodologies to deal with the minimization of a regret where the goal is to maximize the revenue and, at the same time, not to have large risk on the reward realization. The authors analyses three interesting setting, the full information one, the semi-bandit information one and the bandit one. Three algorithms have been proposed, analysed an experimented empirically.", "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": "I think that the paper is well written, propose a novel framework and some interesting solutions, as well as insights and comments on the provided theoretical results. The experiments are convincing, even if they are on a synthetically generated dataset. I think that overall the paper is a solid contribution to the MAB field.\n\n\nI would like to have an estimates and/or an analysis of the computational complexity of the optimization procedure required at each time step by the algorithms. Indeed, it is common that algorithms which are optimal in terms of regret requires long processing time in the full feedback setting.\n\nI think that the experiments have been commented in a short and concise way. More insights on what is shown by them could have added a more value to the paper.\nFinally, i would have expected the author to also test their algorithm on a real-world dataset about financial assets. This would have further strenghten the validity of the contribution you provided.\n\nPost rebuttal: \nI acknolwledge I read the rebuttal. My ratings stays the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any drect societal impact of this work. Maybe it might be used to reduce the risk in the investment, therefore it might provide a positive impact on the field of portfolio optimization.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "1jJvB7JOnK2", "reviewer": "Reviewer_DREH", "summary": "Overall, this paper introduces continuous mean-covariance bandits, a new variant of risk-aware bandit problem in which the arms are taken from continuous action spaces and share high levels of correlation in between. The paper considers 3 respective types of feedback settings in the model: full-information, semi-bandit and full-bandit, providing respective algorithms for each and deriving corresponding matching upper and lower regret bounds for the first two cases as well as an upper regret bound for the third case under additional assumptions. It is the first to explore the covariance structures on learning performances in risk-aware bandits.   ", "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": "Strengths:\n1. The paper is well-written, with most of the sections and contents well-presented. The authors are the first to define and explore the problem of covariance arising in bandits with continuous settings, which finds applications in many settings.\n\n2. All the algorithms in different settings have been clearly presented, with clear descriptions and steps stated clearly. The sketches of proofs provided are adequate for understanding of the overall analysis, and the upper bounds provided by the Upper Confidence Bound-motivated algorithms are order-optimal to the information theoretical lower bounds.  \n\n3. Proper experiments have been conducted, and the outcomes seem to corroborate with the theoretical conclusions.  \n\nWeaknesses:\n1. The motivation of the CMCB problem is unclear. Other than brief descriptions of possible application, it is unclear why the covariance factor should be a part of risk-measure. Why is such construction of interest? Are there any prior works justifying definition (1)? \n\n2. Some terms are not properly explained after their introduction. Exactly what is meant by full-information/semi-bandit/full-bandit feedback? Why are these setups relevant? The upper bounds for CMCB-FI and CMCB-SB seem to be of the same order, and it is not clear how much additional insight CMCB-SB carries compared to the case of FI.\n\n3. The choices of bandit algorithms to solve respective cases seem a bit arbitrary. Is there any motivation for using the MC-Empirical/UCB/ETE algorithms in the three respective cases? Would an adaptation of algorithms built on UCB-principles be just as effective? Better explanations on motivations of algorithmic choice would be more helpful. \n\nOverall, my recommendation would be ‘5, marginally below threshold’. I’d be happy to revise my score, if the authors address my concerns accordingly.\n\n---------------\n\nI'm now raising my recommendation to '6' as the authors have addressed my questions in their review. It would be ideal if the final version of the paper could contain more detailed descriptions on the motivations of the algorithms. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: One limitation is that the authors have not completed the analysis of CMCB in three respective cases, as the lower bounds for CMCB-FB algorithms remain unknown. \n\nSocietal Impact: Not applicable. The paper is largely algorithmic and centers on theoretical justification of an abstract model. If any, the societal impact would be beneficial as it provides an insightful model for risk-aware decision making in the case of continuous action spaces. \n", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of regret minimization on bandits with continuous arms. The key idea is to use the correlation between arms. It shows matching upper and lower regret bounds for full information and semi-bandit settings, and upper bound for the full bandit setting.

Three expert reviewers considered the strengths and weaknesses of the paper. In the author rebuttal, the authors additionally provided evidence on a non-synthetic dataset, in response to two reviewers' comments. The authors engaged with reviewer questions, and the reviewers appreciated this engagement, with two scores increasing. A brief discussion post rebuttal confirmed that all reviewers thought that the paper is novel and provides interesting results. Therefore it is great pleasure for me to recommend that the paper is accepted for publication at NeurIPS.
Decision: Accept (Poster)