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

Shinji Ito, Taira Tsuchiya, Junya Honda

Abstract

This study considers online learning with general directed feedback graphs. For this problem, we present best-of-both-worlds (BOBW) 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$ represent the independence number and the domination number of a certain portion of the graph, respectively. Our proposed algorithm for strongly observable graphs achieves a regret bound of $\tilde{O}( \alpha^{1/2} T^{1/2} ) $ for adversarial environments and $ {O} ( \frac{\alpha (\ln T)^3 }{\Delta_{\min}} ) $ for stochastic environments, resolving 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.

Introduction

In the framework of online learning, a player iteratively selects actions and incurs associated losses. The information revealed to the player—the "feedback"—is critical to determining the difficulty of the learning task. Two classic paradigms define the spectrum of feedback: Prediction with Expert Advice, where the losses of all actions are revealed, and Multi-Armed Bandits (MAB), where only the loss of the chosen action is observed.

Feedback graphs provide a powerful generalization of these scenarios. In this model, actions are represented as nodes in a directed graph; when a player selects a node, they observe the losses of all neighboring nodes. Historically, algorithms were optimized for either adversarial environments (worst-case) or stochastic environments (i.i.d. losses). The "Best-of-Both-Worlds" (BOBW) challenge is to design a single algorithm that achieves optimal regret in both settings without knowing the environment type in advance. This paper introduces the first BOBW algorithms for general feedback graphs that achieve nearly optimal performance across both regimes.

Methodology

The research utilizes the Follow-the-Regularized-Leader (FTRL) framework, introducing two primary innovations to handle the complexities of feedback graphs:

1. Adaptive Learning Rates for Shannon Entropy

For "strongly observable" graphs—where every node is either self-looped or observable from a neighbor—the authors employ Shannon entropy regularization. While Shannon entropy is a standard tool, the authors developed a sophisticated new update rule for the learning rate ($\beta_t$). This rule adapts dynamically based on the cumulative entropy of past distributions, allowing the algorithm to bridge the gap between adversarial and stochastic analysis.

2. Hybrid Regularization for Weakly Observable Graphs

"Weakly observable" graphs are more challenging because they contain nodes that do not have self-loops and are not easily observed. To address this, the authors propose a novel hybrid regularizer. The graph is partitioned into a "weakly dominated" set and a "non-dominated" set. The algorithm then applies Shannon-entropy regularization to the former and Tsallis-entropy regularization to the latter, balancing the different exploration-exploitation trade-offs required for each set.

To establish the stochastic bounds, the authors utilize the self-bounding technique. This marks the first time Shannon entropy has been successfully integrated into this technique to provide robust BOBW guarantees.

Key Insights and Theoretical Contributions

Independence Number vs. Clique Cover

A significant contribution of this work is the refinement of regret bounds in relation to graph theory metrics. Previous research often relied on the clique cover number ($\theta$), which can be significantly larger than the independence number ($\alpha$). This paper proves that regret can be bounded by $\alpha$, resolving an open question from Erez and Koren (2021). This ensures the algorithm is minimax optimal for strongly observable graphs.

Versatility of Shannon Entropy

While recent BOBW literature has favored Tsallis entropy or log-barriers due to their easier "self-bounding" properties, this study demonstrates that Shannon entropy remains highly effective. With the proposed adaptive learning rate, Shannon entropy can achieve optimal adversarial regret while maintaining the stability needed for stochastic environments.

Robustness to Corruption

The proposed algorithms are not limited to pure environments; they are robust to "adversarially-corrupted stochastic environments." In these scenarios, the losses are primarily stochastic but can be manipulated by an adversary for a limited number of rounds. The algorithms maintain their performance guarantees despite such perturbations.

Results

The paper establishes new state-of-the-art regret bounds for general directed feedback graphs:

Graph Type Environment Regret Bound
Strongly Observable Adversarial $\tilde{O}(\alpha^{1/2} T^{1/2})$
Stochastic $O\left(\frac{\alpha (\ln T)^3}{\Delta_{min}}\right)$
Weakly Observable Adversarial $\tilde{O}(\delta^{1/3} T^{2/3})$
Stochastic $O\left(\frac{\delta (\ln T)^2}{\Delta_{min}^2} + \frac{K' \ln T}{\Delta_{min}}\right)$

These results represent the first instance where nearly optimal adversarial bounds and poly-logarithmic stochastic bounds have been achieved simultaneously for general directed feedback graphs.

Limitations and Future Directions

Despite the advancements, several areas for future research remain:

  • Gap Dependency: The stochastic bounds currently depend on the minimum suboptimality gap ($\Delta_{min}$). Future work could aim for bounds that depend on individual gaps ($\Delta_i$), which would be more efficient when many actions are highly suboptimal.
  • Logarithmic Factors: The stochastic regret includes a $(\ln T)^3$ factor. Reducing this to $(\ln T)^1$ or $(\ln T)^2$ would bring the results closer to specialized, non-BOBW algorithms.
  • Dynamic Graphs: The current model assumes a fixed feedback graph $G$. Extending these BOBW guarantees to time-varying or "uninformed" feedback graphs (where the graph is unknown to the player) is a significant remaining challenge in the field.

Summary updated

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.
BibTeX
@inproceedings{ito2022nearly,
  author = {Shinji Ito and Taira Tsuchiya and Junya Honda},
  title = {{Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=rF6zwkyMABn},
}
Figure