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:
- Multi-Armed Bandits (MAB): The player only observes the loss of the specific action chosen.
- 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.
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