Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Starting from the hypothesis that smaller variance estimators of mean rewards result in better bandit performance, the authors leverage Control Variate (CV) theory to propose a bandit algorithm under the presence of auxiliary information about arm rewards.

The authors provide theoretical regret bounds of the proposed control variate based UCB algorithm (under the multivariate normal distribution assumption) and experimentally validate the performance on Gaussian and other distribution based assumptions.

The authors show that, as expected, the attained regret reduction is a function of how strongly correlated the reward samples and the observed control variates are.
main_review: The contribution of this work is on the combination of Control Variate theory (well-known in the statistics community) with a state of the art bandit algorithm (UCB), along with its corresponding regret bounds. The experimental evaluation section however can be significantly improved.

The analysis of the confidence intervals is challenging and novel in the context of the bandit literature, because the optimal (linear) control variate parameters need to be estimated from the observed reward samples (as determined by the bandit algorithm). The authors present in Section 4 the regret bound of the proposed algorithm for multivariate Gaussian rewards and leave for Section 5 the adaption of the algorithm (via jackknifing, splitting, and batching methods) for general distributions.

Lemma 1 and Lemma 2, where control variate theory is used to design confidence intervals of the proposed control variate mean reward estimators, are key for their regret bound in Theorem 1, where the regret reduction induced by control variates is reflected via the correlation parameter $\rho$. The authors provide a very informative discussion in Remarks 1-3 and Figure 1 on the non-trivial dependency between number of covariates $q$ and the constants appearing in Theorem 1.

The proposed algorithm assumes knowledge of the mean $w$ of the control variates per-arm (a limitation only discussed in their conclusion).
- The paper could be significantly improved if a theoretical analysis of the error introduced by estimates of the control variate mean $\widehat{w}$ were to be provided.

In order to extend their control variate based approach to non-Gaussian distributions (where the properties of t-distributions can not be used to obtain analytical confidence intervals), the authors resort to well-known resampling methods to develop (approximate and/or asymptotic) confidence intervals.

Finally, to illustrate the performance of the proposed algorithm and the validity of the presented regret bound, synthetic evaluations are presented in Section 6. However, the results would be more convincing if the following suggestions were to be incorporated:

1. The proposed algorithm assumes knowledge of the mean of the control variates $w$, which is an unreasonable assumption in practice. As such, it would be informative to show, empirically, how much the performance of the proposed algorithm degrades with the quality of the control variate mean estimates $\widehat{w}$.

2. The studied bandit instances can be posed as linear contextual bandits:
   - $y=x^\top \theta + \epsilon$, with $y_{t}=X_{t}$, $x_{t}=(1, W_{t})$ and $\theta=(\mu_{v}, 1)$, where $\theta$ are the unknown parameters, $x_t$ the observed context (with a bias term) and $\epsilon \sim N(0, \sigma_{v}^2)$.
   - A set of experiments where their proposed algorithm is compared to linear Gaussian Thompson sampling and UCB algorithms would be very insightful to better illustrate the benefits of control variates in the linear-Gaussian setting. 

3. The authors state that "We observe that Thomson Sampling has a large regret". Given the successful performance presented by many in the literature with Thompson sampling for Gaussian bandit rewards, I encourage the authors to clarify what mean and variance priors they used for their Gaussian Thompson sampling implementation, and whether adjusting them improves the observed performance. 

Other minor comments/suggestions:

- Line 15: "the arms rewards" -> "the arm rewards"
- Line 165: "CVs have follow multivariate" -> "CVs follow a multivariate"
- Line 276: "regret bound with" -> "and regret results with"?

limitations_and_societal_impact: The authors discuss in their conclusion section the fact that the proposed algorithm assumes knowledge of the mean of the control variates per-arm.

The analysis (at least empirically) of the impact of estimating these control variate means on regret performance would significantly strengthen their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper tackles a bandit setting similar to contextual bandits, where the feedback consists of the reward obtained from playing an arm, but also an additional random variable (the control variate) which is correlated with the reward but whose mean is known to the decision maker. Unlike in contextual bandits, the value of this control variate is not available at decision time but it is only revealed after the arm's play and can thus only be used to produce better estimates of the rewards of arms. The paper proposes the UCB-CV algorithm that builds confidence intervals that exploit this additional information to produce lower regret. The algorithm is accompanied by a regret analysis and experiments demonstrating the algorithm's performance and the decrease in regret that can be achieved based on the correlation coefficient between the reward and the control variates.
main_review: Overall I found the paper well written and presented. I appreciate the effort put into the experimental section as well as the Section 2 offering introduction to the area. My main concerns surround the practical relevance of the setting (and algorithm - relative to Splitting for instance), the unclear distinction of the results here from prior work (a fence between the problem tackled here and contextual bandits, and MABs with covariates). Detailed review below:

**Originality**:\
To the best of my knowledge this setting is original for the bandit setting. I do however have a few questions regarding the practical relevance of the problem studied here. First, the control variates would be available at decision time in most practical scenarios (the job "size" is usually known ahead of time, similarly wouldn't the pilot signals be sent in advance of the packet?). Secondly, from the historic data used to estimate the means of the control variates, we can also estimate the variance. What is the reason why the variance of the control variate ${\sigma^2_{w,i}}_{i \in [K]}$ is left unknown?\
I think there is a bit of room for improvement when it comes to separating the setting here from contextual bandits. If the control variates were revealed at the begining of the round (like contexts are revealed in contextual bandits), would this setting be a specific instance of contextual bandits?\
I am also missing how this setting compares to the MAB problem with covariates (see [1], [2]).

**Quality**:\
I have not checked the proofs in the Appendix. The paper seems technically sound and the algorithm well-grounded in theory. The authors also point out several remarks offering insights into the bound presented in Theorem 1. I would have liked to see a bit more detail as to where the upper bound on $(V^{(2)}_{T,T,q})^2$ is obtained. Possibly also include larger time horizon T in the plot (order of thousands or tens of thousands).\
I appreciate the effort put into the experiments section and implementing a good number of baselines. I would like to know more about why Splitting outperforms all algorithms and why would UCB-CV be preferable?\
A further question surrounds what is the impact of the hyperparameter $\alpha$ that is fixed to $\alpha=2$ throughout the majority of the paper. Is this the optimal value for this parameter? If not, how sensitive is the algorithm to the choice of $\alpha$?

**Clarity**:\
I found the paper well presented with sufficient attention given to aspects that cause confusion (I particularly appreciate the clarifying remarks following Theorem 1.) I would appreciate more clarifications surrounding the novelty of the setting and the advantages of the proposed method relative to just using Splitting which appears to outperform UCB-CV in the experiments (an example of a problem instance where Splitting would fail would present a convincing argument).

**Significance**:\
The significance of the results should be stated more clearly in the paper. As is, I believe the setting studied here has limited connection to practical applications, though I do see the potential of future study into the theory of exploiting control variates (I liked the ranking example in Section 7). 

limitations_and_societal_impact: The paper does a decent job addressing limitations of their work in the 3 remarks at the end of Section 4, though this might not be comprehensive.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers low regret learning in stochastic multi-armed bandits in the presence of control variables. For jointly Gaussian reward and control variables, and linear control variates, the authors show a factor 1-ρ^2 reduction in the regret.
main_review: The paper focuses on reducing regret in multiarmed bandits using control variates. The authors derive the regret under linear control variates for the joint Gaussian case, and show that the regret reduces by a multiplicative factor 1-ρ^2 .

For general reward and CV distributions, the authors utilise jackknifing and splitting resampling to obtain estimators with smaller bias and sharper confidence intervals. For the general case, the confidence intervals are only asymptotic and hold approximately for finite samples.

Overall, the paper is reasonably well written, and seems technically sound. It takes a well-known technique of CVs and applies it in the context of MABs using standard techniques. The innovativeness of the work can be characterised as “moderate” in my opinion. 

Minor:

(I) Line 165: Please clarify why \bar{X}_i are correlated
(II) Line 176: It is not clear how lemma 2 is analogous to Hoeffding from the way you have written it in terms of the t-distribution. Please elucidate by comparing to the exponential decay in Hoeffding
(III) Line 322: “our the bounds”
limitations_and_societal_impact: 
No negative social impact.

One of the shortcomings is that the motivating examples are sketchy and weak. The authors speak about examples from queueing and wireless fading channels, but they do not give concrete examples where such CVs are available, or can be used to improve learning performance.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the (stochastic) multi-armed bandit problem, and proposes to use control variates to improve estimates of the reward for each arm. The case of Gaussian reward and control variates is studied in detail from a theoretical viewpoint, and the more general case is studied empirically. 
main_review: I should clarify before starting my review that my knowledge of reinforcement learning is fairly limited, but that I have significant experience with the use of control variates for Monte Carlo methods more generally. My comments should therefore be interpreted with this in mind.


Main comments
----------------

- I found the paper to be well written and argued. This made it easier for me to read given I am not an expert in reinforcement learning.
- The literature review seems fairly thorough to me. A large number of relevant papers are discussed, and comparisons are made with the present paper. I have nevertheless suggested a number of other papers from the statistics literature which could be interesting to discuss, mostly as I believe they could potentially bring further gains. See the "literature" section below. 
- Section 4: It is very much unclear to me whether assuming that the reward and control variate of each arm have a multivariate normal distribution is something reasonable in practice. From the literature review (Section 1.1.), it seems like a range of assumptions are used in practice, with Auer et al 2002 being the closest to this setting. Looking at some of the papers cited, it does however seem overly restrictive. For example, the Bubeck and Cesa-Bianchi paper from 2012 uses much less restrictive assumptions on the reward. I would find it particularly useful for the authors to provide a much more detailed discussion of this point. For example, what if the reward and control variates are only sub-Gaussian? What if the reward has a heavier tail distribution than the control variate or vice versa? I can understand why using Gaussian assumptions is useful for the theory (since it is then simply a linear regression problem with Gaussian variables), but it would be interesting to understand the limitations of this assumption for deriving the theoretical results and whether any of the assumption could be relaxed.
- The numerical experiments section is interesting, but left me wondering how realistic it is to actually use this approach in practice. This is mostly because it did not contain any practical example (as opposed to a synthetic simulation study) where a control variate is actually available. I think the paper would strongly benefit from such an example as otherwise it is difficult to see this actually being a practical method. 
- Also, as pointed out in the conclusion, one of the biggest issue will be getting a control variate with known mean. I again struggle to see situations where this would be the case in applied problems. If it is not possible to know the mean exactly, what would be the impact on the estimated reward? Could the bias introduced somewhat lead to sub-optimal results relative to not using a control variate?


Literature review:
-------------------
- There are a number of papers on the use of control variates in reinforcement learning that could be discussed, including: 
https://jmlr.csail.mit.edu/papers/volume5/greensmith04a/greensmith04a.pdf
https://arxiv.org/abs/1908.03263
https://arxiv.org/abs/1906.08868
https://openreview.net/pdf?id=H1mCp-ZRZ
Although it is not applied to the same set of RL algorithms, it might still be useful to tell the reader about this for context. Note that I have just listed the first few that come up on Google, but a more complete literature review could help.

- Control variates are also very common in Monte Carlo methods; for example:
https://link.springer.com/article/10.1007/s11222-012-9344-6
https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssb.12185
https://projecteuclid.org/journals/bernoulli/volume-25/issue-2/Convergence-rates-for-a-class-of-estimators-based-on-Steins/10.3150/17-BEJ1016.short
These are constructed somewhat differently from the control variates in here, and it might be interesting to discuss the advantages and disadvantages of each approach.

Minor comments
---------------
- line 93: "which could then used as side information"
- Eq 4 and line 161: slightly inconsistent use of * or \star
limitations_and_societal_impact: There was no discussion of societal impact. I have also highlighted above a number of limitations which should be discussed in more details.
review_title: null

Meta-review: The committee has appreciated the involved and detailed response to their questions and comments and agreed that this work should be accepted. One reviewer raised the question of the knowledge of the variance of the control variate $\sigma_{w,i}^2$ and would encourage the authors to investigate and discuss this question in their final version.
Decision: Accept (Poster)