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:
- The Bandit Setting: The graph has no edges. You only learn about what you pull.
- 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:
- Regret Decomposition: Chihao Zhang and Yuchen He introduced a "divide and conquer" framework in Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition. By partitioning a feedback graph into smaller clusters, they solved long-standing problems regarding regret in undirected cycles and bounded-degree graphs.
- Fractional Domination: In Understanding Bandits with Graph Feedback, Houshuang Chen and Zengfeng Huang used linear programming duality to introduce the fractional weak domination number ($\delta^*$), providing even tighter bounds for trees and other specific topologies.
- Best-of-All-Worlds: Real-world environments are rarely purely "stochastic" (predictable) or "adversarial" (worst-case). Liad Erez and Tomer Koren developed algorithms using a hybrid Tsallis-Shannon entropy to perform optimally regardless of the environment type, as detailed in Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs.
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.