Sequential learning with feedback graphs is a natural extension of the
multi-armed bandit problem where the problem is equipped with an underlying
graph structure that provides additional information - playing an action
reveals the losses of all the neighbors of the action. This problem was
introduced by \citet{mannor2011} and received considerable attention in recent
years. It is generally stated in the literature that the minimax regret rate
for this problem is of order $\sqrt{\alpha T}$, where $\alpha$ is the
independence number of the graph, and $T$ is the time horizon. However, this is
proven only when the number of rounds $T$ is larger than $\alpha^3$, which
poses a significant restriction for the usability of this result in large
graphs. In this paper, we define a new quantity $R^*$, called the \emph{problem
complexity}, and prove that the minimax regret is proportional to $R^*$ for any
graph and time horizon $T$. Introducing an intricate exploration strategy, we
define the \mainAlgorithm algorithm that achieves the minimax optimal regret
bound and becomes the first provably optimal algorithm for this setting, even
if $T$ is smaller than $\alpha^3$.

本论文主要介绍了一种基于反馈图的顺序学习问题，提出了一个名为 problem complexity 的新概念，并创建了一个既定算法，实现了对此设置的最小化失望度量的最优解。

反馈图网络在线学习：损失函数的真实形态

Online Learning with Feedback Graphs: The True Shape of Regret

In this work, we improve on the upper and lower bounds for the regret of
online learning with strongly observable undirected feedback graphs. The best
known upper bound for this problem is $\mathcal{O}\bigl(\sqrt{\alpha T\ln
K}\bigr)$, where $K$ is the number of actions, $\alpha$ is the independence
number of the graph, and $T$ is the time horizon. The $\sqrt{\ln K}$ factor is
known to be necessary when $\alpha = 1$ (the experts case). On the other hand,
when $\alpha = K$ (the bandits case), the minimax rate is known to be
$\Theta\bigl(\sqrt{KT}\bigr)$, and a lower bound $\Omega\bigl(\sqrt{\alpha
T}\bigr)$ is known to hold for any $\alpha$. Our improved upper bound
$\mathcal{O}\bigl(\sqrt{\alpha T(1+\ln(K/\alpha))}\bigr)$ holds for any
$\alpha$ and matches the lower bounds for bandits and experts, while
interpolating intermediate cases. To prove this result, we use FTRL with
$q$-Tsallis entropy for a carefully chosen value of $q \in [1/2, 1)$ that
varies with $\alpha$. The analysis of this algorithm requires a new bound on
the variance term in the regret. We also show how to extend our techniques to
time-varying graphs, without requiring prior knowledge of their independence
numbers. Our upper bound is complemented by an improved
$\Omega\bigl(\sqrt{\alpha T(\ln K)/(\ln\alpha)}\bigr)$ lower bound for all
$\alpha > 1$, whose analysis relies on a novel reduction to multitask learning.
This shows that a logarithmic factor is necessary as soon as $\alpha < K$.

本文针对具有强可观测无向反馈图的在线学习问题，在回报上下界方面进行了改进，并使用 FTRL 与 q-Tsallis 熵对结果进行了证明；同时扩展了该技术应用于时间变化图的情形，并提供了适用于所有 alpha>1 的改良下界。