Online Learning with Structured Feedback Graphs

This direction is merged into another direction: graph-theoretic regret bounds. Its last version stays readable and citable here.

Version 1 of 130 papers39 conceptsfrozen 2026-10-04

In the classical multi-armed bandit problem, a learner chooses an action and observes only the reward for that specific choice. However, in many real-world scenarios—like social networks, recommendation engines, or sensor arrays—choosing one action provides "side information" about others. This relationship is modeled as a feedback graph, where nodes represent actions and edges represent the flow of information.

The central goal of this research direction is to design algorithms that leverage these graph structures to minimize regret—the difference between the learner's total reward and the reward of the best possible fixed strategy.

The Intuition of Side Information

Imagine you are recommending movies to users in a social network. If two users have very similar tastes, observing that User A liked a movie gives you a strong hint about whether User B would like it. In this case, the "action" of recommending to User A provides feedback for the "action" of recommending to User B.

As Nicolò Cesa-Bianchi and Ohad Shamir demonstrate in Bandit Regret Scaling with the Effective Loss Range, this side information can drastically reduce the search space. Instead of exploring every arm independently, the learner can "see" across the graph, effectively turning a difficult bandit problem into something closer to the "expert advice" setting, where all rewards are visible.

Bridging the Gap Between Experts and Bandits

The complexity of learning with graph feedback lies in where the graph falls on the spectrum between two extremes:

  1. The Bandit Setting: The graph has no edges. You only learn about what you pull.
  2. The Expert Setting: The graph is complete. Pulling any arm reveals the rewards for all arms.

Researchers like Khaled Eldowa and Nicolò Cesa-Bianchi have worked to bridge this gap. In On the Minimax Regret for Online Learning with Feedback Graphs, they show that by tuning specific mathematical tools called regularizers (specifically $q$-Tsallis entropy), an algorithm can automatically adapt its learning rate to match the optimal theoretical bounds for whatever graph structure it encounters.

Graph Parameters as Complexity Measures

To understand why some graphs are harder to learn than others, researchers look at specific graph-theoretic properties:

  • Independence Number ($\alpha$): This represents the largest set of nodes where no two nodes are connected. If a graph has a high independence number, the learner gets very little side information, making the problem harder.
  • Clique Cover Number ($\chi$): This is the minimum number of fully connected subgraphs (cliques) needed to cover all nodes. If you pull one arm in a clique, you learn about everyone else in that clique.

A recurring challenge identified by Fang Liu and Ness Shroff in Information Directed Sampling for Stochastic Bandits With Graph Feedback is the "theoretical gap" between these two. While lower bounds on regret often scale with $\alpha$, many existing algorithms only achieve upper bounds that scale with the larger $\chi$. Closing this gap is a major focus of the field.

Advanced Strategies for Complex Networks

As the networks grow more complex, simple algorithms struggle. Several researchers have proposed hierarchical or specialized approaches:

Applications in Influence and Inference

This theoretical framework extends into practical domains like Influence Maximization. Po-Ling Loh and Justin Khim apply these concepts to spreading information in networks where the rules of spread are unknown or adversarial (Adversarial Influence Maximization).

Similarly, in massive probabilistic models, Jay Pujara and Lise Getoor use graph-based "budgeted inference" to update only the most critical variables, maintaining accuracy without the computational cost of a full re-computation (Budgeted Online Collective Inference).

By treating the feedback structure as a first-class citizen in the learning process, these researchers have moved online learning from isolated decisions to a globally informed strategy.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_online_learning_with_structured_feedback_f966dda8,
  title = {Online Learning with Structured Feedback Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-with-structured-feedback-graphs/rdr_f966dda8f9aa44db8d0786482b9dacca},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_learning_with_structured_feedback_f966dda8_v1,
  title = {Online Learning with Structured Feedback Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-with-structured-feedback-graphs/rdr_f966dda8f9aa44db8d0786482b9dacca/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}