Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs

This study considers online learning with general directed feedback graphs. For this problem, we present best-of-both-worlds algorithms that achieve nearly tight regret bounds for adversarial environments as well as poly-logarithmic regret bounds for stochastic environments. As Alon et al. [2015] have shown, tight regret bounds depend on the structure of the feedback graph: strongly observable graphs yield minimax regret of \tilde{\Theta}( \alpha {1/2} T {1/2}), while weakly observable graphs induce minimax regret of \tilde{\Theta}( \delta {1/3} T {2/3}), where \alpha and \delta, respectively, represent the independence number of the graph and the domination number of a certain portion of the graph. This result resolves an open question raised by Erez and Koren [2021]. We also provide an algorithm for weakly observable graphs that achieves a regret bound of \tilde{O}( \delta {1/3}T {2/3}) for adversarial environments and poly-logarithmic regret for stochastic environments.