Summary
Two classical learning problems are learning with experts and multi-armed bandits. In both problems, a learner interacts during $T$ rounds with a set of $K$ actions by selecting an action at each round. After each round, the loss/reward at that step is revealed for all actions (resp. only for the selected action) in the expert (resp. bandit) problem. Mannor and Shamir [24] provided a convenient interpolation between the two problems by considering a generalization via feedback graphs. At each step $t$, losses are observed only at neighbor actions to the selected one, according to a graph $G_t$. The expert case corresponds to the clique, while the bandit case corresponds to graphs without edges. In this context, it is known that if the graphs have independence number $\alpha$, the minimax regret lies between $O(\sqrt{\alpha T\log K})$ and $\Omega(\sqrt{\alpha T})$. Further, the lower (resp. upper) bound is tight for learning with experts (resp. multi-armed bandits) for which $O(\sqrt{KT})$ regret is achievable (resp. a lower bound $\Omega(\sqrt{KT\log K})$ is known).
This paper investigates the corresponding $\sqrt{\log K}$ gap between the case $\alpha=1$ (clique/experts) and $\alpha=K$ (multi-armed bandits) and gives interpolating upper bound $O(\sqrt{\alpha T(1+\log K/\alpha)})$ on the regret provided that the graphs are undirected and strongly observable (each vertex has either a self-loop or neighbor to all other actions), with the same algorithm---FTRL with $q$-Tsallis entropy---run with appropriate parameter $q(\alpha)$ and loss estimates. Via a doubling trick, they show that one can achieve this bound up to an additive $\log \alpha$ term without prior knowledge on $\alpha$ (and can be further extended to the case when graphs $G_t$ do not share the same independence number).
Last, the authors provide an improved interpolating lower bound $\Omega(\sqrt{\alpha T \log K/\log \alpha})$, which requires the graphs $G_t$ to vary over time (but with same independence number), showing that when $\alpha$ is sub-polynomial in $K$, learning with feedback graphs requires an extra factor compared to the known lower bound $\Omega(\sqrt{\alpha T})$. This is shown via a reduction to the multitask bandit problem (different tasks are simulated by changing the graph over time).
Strengths
The paper is very well-written and pleasant to read. The question is well posed, and motivated by the fact that improving the $\sqrt{\log K}$ factor for learning with experts, from $O(\sqrt{KT\log K})$ to $O(\sqrt{KT})$ remained open for a significant amount of time in the literature. Hence, interpolating the regret bounds in terms of the remaining factor $\sqrt{\log K}$ between the known bounds $O(\sqrt{\alpha T\log k})$ and $\Omega(\sqrt{\alpha T})$ seems an important question.
The upper bounds use the same algorithm (FTRL with $q$-Tsallis entropy) with adapted parameters $q$, which also interpolates between known approaches for the extreme cases $\alpha=1$ or $\alpha=K$, giving new insights on the impact of this parameter on the learning behavior.
Weaknesses
Although the paper presents new contributions to interpolate between experts and bandits, the proofs follow classical arguments in the literature and seem to bring limited original ideas. In particular, it was known that the $q$-Tsallis entropy specifically allows achieving the minimax entropy in both end cases. The main difficulty in the generalization to feedback graphs is in a novel bound for the variance term in the FTRL analysis (Lemma 3), which itself is a generalization of known results in the literature for $q=1$. The rest of the proof follows standard analysis.
The lower bound heavily relies on the fact that graphs are allowed to vary over time. It seems that the approach cannot be extended to the important case of interest of a fixed graph (which seemed to be the main case studied in the previous literature on feedback graph bandits). The paper would also be significantly strengthened if the lower bound could be improved to match the upper bound when e.g. the independence number $\alpha$ grows as a polynomial in $K$---in that case, the present paper does not provide improvements in terms of rates compared to the existing literature. As such, the gap left by this paper seems to remain quite important.
Questions
- Does the analysis carry over for adaptive adversaries, or is the oblivious assumption important?
- l.97 the independence number is the cardinality of such a set, right?
- What happens if we assume that the graph is constant over time? Would you expect similar lower bounds to hold?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The limitations were very well addressed by the authors, who clearly identify the new bound on the variance (Lemma 3) as the key added technical contribution for the upper bounds.