  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$.
