Combinatorial semi-bandit with known covariance
The combinatorial stochastic semi-bandit problem is an extension of the classical multi-armed bandit problem in which an algorithm pulls more than one arm at each stage and the rewards of all pulled arms are revealed. One difference with the single arm variant is that the dependency structure of the arms is crucial. Previous works on this setting either used a worst-case approach or imposed independence of the arms. We introduce a way to quantify the dependency structure of the problem and design an algorithm that adapts to it. The algorithm is based on linear regression and the analysis develops techniques from the linear bandit literature. By comparing its performance to a new lower bound, we prove that it is optimal, up to a poly-logarithmic factor in the number of pulled arms.
This paper studies a online linear optimization problem with combinatorial action sets and 'semi-bandit' feedback. At any given time, the reward noise of individual arms is correlated. The paper provides a regret bound for a linear UCB algorithm that scales with the degree of correlation and interpolates between two extreme cases studied in the prior literature: the case with no correlation, and the case where observations on different arms may be perfectly correlated. 
This paper makes an interesting contribution. It's natural for there be correlation between arm outcomes, e.g. the realized time to traverse neighboring edges on a graph, and it's valuable to pin down the dependence of regret bounds on this correlation. This result helps link and unify separate results in the literature.   There are few limitations to the results. First, the proposed algorithm requires solving an optimization problem that can be NP hard. It's not clear the algorithm is implementable. Second, it seems this UCB approach may be statistically suboptimal in some settings. When possible, the most efficient way to gather information would be to select base arms with relatively uncorrelated outcomes. The algorithm won't do this. Finally, the regret bounds depend on the inverse mean-gaps that can be incredibly small. (e.g. the difference between the shortest and second shortest path in a graph) Gap-independent results would be nice here.    -- Here are some additional comments---  • It would be nice to provide a better motivation for the problem, and better intuition for the results. For example, it's very natural that one attains m times more information with no correlation than under perfect correlation.  • Do you need to depend on the largest correlation coefficient? Presumably, the reward of two base arms could be perfectly correlated without performance degrading substantially. The issue arises when there is a great deal of correlation on average.   • The proof looks familiar from other UCB analyses, but I find it very hard to read. I'm not sure this is necessary.   • The lower bound statement is not precise. It's not clear precisely what it means that "there exists a problem with gaps Delta" (all gaps = Delta? Is a gap a formal term? ). Also arms cannot  be sub-Gaussian, you mean that their reward noise is sub-Gaussian.