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

Shinji Ito, Taira Tsuchiya, Junya Honda

Introduction

This paper introduces the first nearly optimal "Best-of-Both-Worlds" (BOBW) algorithms for online learning with general directed feedback graphs. By using novel adaptive learning rate update rules and hybrid regularization techniques, the authors achieve minimax optimal regret in adversarial environments while simultaneously securing poly-logarithmic regret in stochastic settings. This resolves a significant open question in the field of online learning.

The Problem: Bridging Adversarial and Stochastic Learning

In online learning, a player repeatedly chooses actions and incurs losses. The "feedback graph" model generalizes two classic problems:

  1. Multi-Armed Bandits (MAB): The player only observes the loss of the specific action chosen.
  2. Prediction with Expert Advice: The player observes the losses of all possible actions, regardless of the choice made.

A feedback graph defines exactly which losses are revealed based on the player's choice. These graphs are broadly categorized into two types:

  • Strongly observable: Every node is easily "covered" or observed by at least one action.
  • Weakly observable: Some nodes are harder to learn about, making the environment inherently more challenging.

The primary challenge in this domain is that most algorithms are highly specialized. They perform well if losses are adversarial (worst-case, actively working against the player) OR stochastic (drawn from a fixed, stable distribution), but rarely both. Previous BOBW attempts for feedback graphs were limited—they either only worked for specific graph types or produced sub-optimal bounds based on the "clique covering number" ($\theta$) rather than the more efficient "independence number" ($\alpha$).

Proposed Methods

The authors utilize the Follow-the-Regularized-Leader (FTRL) framework but introduce two major algorithmic innovations to handle different graph structures:

1. Strongly Observable Graphs

For strongly observable graphs, the authors use Shannon entropy regularization paired with a brand-new adaptive update rule for learning rates ($\beta_t$ and $\gamma_t$). Unlike previous methods that relied on fixed parameters, this algorithm adjusts its learning schedule based on the cumulative entropy of the action distributions. This allows the algorithm to "self-bound" and perform significantly better in stochastic environments without sacrificing adversarial robustness.

2. Weakly Observable Graphs

For weakly observable graphs, they employ a hybrid regularization strategy. The graph is conceptually split into two parts:

  • A "dominated" part, handled with Shannon entropy.
  • A "non-dominated" part, handled with Tsallis entropy.

This hybrid approach is intuitive because the non-dominated parts behave more like a standard bandit problem, where Tsallis entropy is known to be highly effective.

Key Insights

  • $\alpha$ over $\theta$: A major breakthrough in this work is the realization that regret bounds can depend on the independence number ($\alpha$) instead of the clique covering number ($\theta$). Since $\theta$ can be significantly larger than $\alpha$ (sometimes as large as the total number of actions $K$ while $\alpha=1$), this shift makes the algorithm much more efficient for many graph structures.
  • The Power of Adaptivity: By making the learning rate sensitive to the "shape" of the loss history via entropy, the algorithm automatically slows down or speeds up its learning to match the difficulty of the environment.
  • Handling Corruption: The algorithms are robust not just to pure stochastic or adversarial cases, but also to adversarially-corrupted stochastic environments, where a limited "budget" of adversarial interference is allowed in an otherwise stable stochastic system.

Key Results

The paper provides two main theorems that establish new state-of-the-art regret bounds ($R_T$), effectively bridging the gap between the theoretical limits of the feedback graph model and the practical need for adaptable algorithms.

Comparison of regret bounds achieved by the proposed algorithms against prior work.

As summarized in the table above, the new bounds are:

  • Strongly Observable Case:
    • Adversarial: $\tilde{O}(\alpha^{1/2}T^{1/2})$ — This achieves the minimax optimal rate.
  • Stochastic: $O\left(\frac{\alpha (\ln T)^3}{\Delta_{\min}}\right)$ — This provides the desired poly-logarithmic growth, resolving the open question by Erez and Koren (2021).
  • Weakly Observable Case:
    • Adversarial: $\tilde{O}(\delta^{1/3}T^{2/3})$ — Matches the known minimax rate for this harder class of graphs.
  • Stochastic: Poly-logarithmic regret, specifically $O\left(\frac{\delta (\ln T)^2}{\Delta_{\min}^2} + \frac{K' \ln T}{\Delta_{\min}}\right)$.

Limitations and Future Work

While this paper makes significant theoretical strides, the authors note a few areas for future refinement:

  • Logarithmic Factors: The stochastic bound for strongly observable graphs contains a $(\ln T)^3$ factor. Future work could aim to reduce this to a single $\ln T$ to match the tightest possible bounds for simpler bandit problems.
  • Unique Optimum Assumption: The current "self-bounding" analysis assumes a unique optimal action. Extending this to handle multiple optimal actions—a common occurrence in real-world scenarios—remains an open challenge.
  • Complexity of Weakly Observable Bounds: The regret terms for the weakly observable case are quite complex, involving $K'$ (the number of non-dominated vertices). While nearly tight, there may be room to simplify these expressions or the underlying algorithm in future iterations.

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