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

Source: [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](<https://www.sota2.com/research/paper/68fa6e481e209131cea3ef6a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-12-25T16:47:46.999Z

Authors: Shinji Ito, Taira Tsuchiya, Junya Honda

Published: 2022-06-02T05:01:40.000Z

## Abstract

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. Our proposed algorithm for strongly observable graphs has a regret bound of $\\tilde{O}( \\alpha^{1/2} T^{1/2} ) $ for adversarial environments, as well as of $ {O} ( \\frac{\\alpha (\\ln T)^3 }{\\Delta\_{\\min}} ) $ for stochastic environments, where $\\Delta\_{\\min}$ expresses the minimum suboptimality gap. 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. The proposed algorithms are based on the follow-the-regularized-leader approach combined with newly designed update rules for learning rates.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Regret Minimization on Contextual Combinatorial Bandits](<https://www.sota2.com/research/sota/regret-minimization-on-contextual-combinatorial-bandits.md>): Regret Minimization; Contextual Combinatorial Bandits; Stochastic Regret: 3.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2206.00873>)

[PDF](<https://arxiv.org/pdf/2206.00873.pdf>)
