Information Directed Sampling for Stochastic Bandits with Graph Feedback

Understand

We consider stochastic multi-armed bandit problems with graph feedback, where the decision maker is allowed to observe the neighboring actions of the chosen action.

• We allow the graph structure to vary with time and consider both deterministic and Erd\H{o}s-R\'enyi random graph models.
• For such a graph feedback model, we first present a novel analysis of Thompson sampling that leads to tighter performance bound than existing work.
• Next, we propose new Information Directed Sampling based policies that are graph-aware in their decision making.