Learning on the Edge: Online Learning with Stochastic Feedback Graphs

Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven, Nicolò Cesa-Bianchi

Abstract

In sequential decision-making, the quality and quantity of feedback significantly influence a learner's performance. While traditional models assume either limited bandit feedback or complete information, real-world scenarios often fall into a middle ground described by feedback graphs. This paper, presented at NeurIPS 2022, addresses a realistic extension of this model: stochastic feedback graphs where edge probabilities are unknown. We present two novel algorithms, EdgeCatcher and otcG, which provide the first nearly optimal regret bounds for this setting, effectively balancing exploration of the graph structure with the exploitation of available side-information.

Introduction

In the standard Multi-Armed Bandit (MAB) problem, a learner only observes the loss of the action they choose. Conversely, in the "Full Information" setting, the learner observes the losses of all possible actions. Feedback graphs generalize these extremes: a directed graph determines which actions' losses are revealed based on the chosen action.

However, most existing literature assumes these graphs are deterministic and known. In practice, feedback is often stochastic and unreliable—for example, in sensor networks where transmissions fail due to environmental factors or hardware limitations. This paper tackles the challenge of online learning where edges are stochastic, probabilities are unknown, and losses are chosen by an adversary.

The Challenge of Stochasticity

The core difficulty in learning with stochastic graphs lies in a "thresholding" trade-off. If a learner attempts to utilize every piece of feedback, including very rare edges (low-probability signals), the variance of their estimators can skyrocket, leading to poor performance. Conversely, ignoring too many edges results in a loss of valuable information. The learner must find an optimal threshold $\varepsilon$ to decide which feedback signals are reliable enough to use.

Proposed Algorithmic Frameworks

The authors introduce two primary algorithms to navigate these challenges:

1. EdgeCatcher: The Explore-then-Commit Approach

EdgeCatcher is designed for scenarios where the learner has minimal information about the graph structure. It operates in two distinct phases:

  • Exploration: The algorithm uses a "RoundRobin" procedure to estimate the unknown edge probabilities $p(i, j)$ between actions.
  • Commitment: After gathering sufficient estimates, it selects an optimal threshold $\varepsilon$. Edges with probabilities lower than $\varepsilon$ are treated as non-existent. The algorithm then simulates a deterministic feedback graph by grouping time into "blocks" of size $\approx 1/\varepsilon$. By waiting for a block to conclude, the learner ensures that a stochastic edge appears at least once with high probability, allowing the use of standard deterministic algorithms like Exp3.G.

2. otcG (OptimisticThenCommitGraph)

otcG is a more sophisticated algorithm applicable when the learner can observe the realized graph (which edges actually appeared) at the end of each round.

  • UCB Estimation: It employs Upper Confidence Bounds (UCB) to maintain optimistic estimates of edge probabilities.
  • Importance-Weighted Estimators: It uses a novel estimator for losses that accounts for the probability of observing an action's loss through any currently active edge.
  • Adaptive Strategy: The algorithm starts by assuming the graph is "strongly observable" (easier to learn) and adaptively switches to a "weakly observable" strategy if it determines that the latter will minimize regret more effectively.

Theoretical Insights: Weighted Graph Parameters

A significant contribution of this work is the formalization of "weighted" graph parameters. Traditional online learning relies on the independence number ($\alpha$) or the weak domination number ($\delta$) of a graph. The authors introduce weighted versions of these metrics—$\alpha^*$ and $\delta^*$—which weight nodes by the reciprocal of their feedback probabilities. These parameters provide a much tighter measure of the learning difficulty in a stochastic environment, balancing topological complexity against the sparsity of feedback.

Key Results and Regret Bounds

The paper establishes that for an unknown stochastic graph, the achieved regret is roughly $\tilde{O}(\sqrt{(\alpha^*/\varepsilon^*)T})$ for strongly observable supports and $\tilde{O}((\delta^*/\varepsilon^*)^{1/3}T^{2/3})$ for weakly observable ones. The authors provide matching lower bounds, proving these rates are optimal up to logarithmic factors.

In empirical benchmarks using synthetic "hard instances," such as the "Faulty Bandits" case (where each arm provides feedback only on itself with some probability $\varepsilon_i$), the refined otcG algorithm significantly outperforms previous general-purpose bounds, demonstrating its ability to handle heterogeneous feedback probabilities.

Limitations and Conclusion

While the paper provides a robust theoretical foundation, it notes certain computational hurdles. Calculating parameters like the independence number is NP-hard, necessitating the use of greedy approximations in large-scale applications. Additionally, the high-performance otcG algorithm requires visibility of the realized graph, which may not be available in all decentralized systems.

By bridging the gap between bandit and full-information settings through the lens of stochastic graphs, this research offers a more nuanced and realistic framework for sequential decision-making in uncertain environments.

Summary updated

BibTeX
@inproceedings{esposito2022learning,
  author = {Emmanuel Esposito and Federico Fusco and Dirk van der Hoeven and Nicolò Cesa-Bianchi},
  title = {{Learning on the Edge: Online Learning with Stochastic Feedback Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=TfxI8l8_AL},
}
Figure