Bandits with graph feedback

Overview

The learner faces an unknown graph of d nodes. Each round it picks one node and observes the set of nodes that node influences. The goal is to maximise the total number of influences over n rounds, measured against an oracle that always plays the most influential node 2605.00489 §2.1. Node i influences node j with an unknown probability, so the feedback is about a neighbourhood, not about a single arm 2605.00489 §2.1.

The setting builds on the MOSS bandit and on graph bandits with side observations 2605.00489 §1 2605.00489 §2.2.

If the learner sees only a count of influenced nodes, the graph cannot be used. The problem then reduces to a plain bandit over d arms, with regret of order min(r* n, r* d + sqrt(r* n d)) up to constants 2605.00489 §2.2.

The variants share one aim: make the regret depend on how many nodes are close to the best in dual influence (the detectable dimension), rather than on d 2605.00489 §3. Nodes are ranked by dual influence, while regret is measured with primal influence; the two agree only for undirected graphs 2605.00489 §2.1.

Variants

BARE: explore to detect, then bandit

BARE works in two phases 2605.00489 §3 2605.00489 alg. 2.

1. Global exploration. Pick nodes uniformly at random and record the influenced set each time. Keep a shrinking candidate set of nodes whose estimated dual influence is near the best. Stop when a horizon-dependent test fails. The stopping time and the surviving set are the phase outputs 2605.00489 alg. 2.
2. Bandit on the candidates. Run a minimax-style bandit on the surviving nodes for the remaining rounds. The algorithm names the bandit only as an example; the experiments use GraphMOSS 2605.00489 §5 2605.00489 alg. 2.

The analysed regret is of order min(r* n, D* r* + sqrt(r* n D*) + n ε*), with D* the detectable dimension and ε* the influential-influenced gap 2605.00489 §3. For undirected graphs the n ε* term is absent 2605.00489 §3. A matching lower bound holds for d ≥ Cn 2605.00489 §3. Card: Revealing graph bandits for maximizing local influence.

Baseline: GraphMOSS on all nodes

A MOSS-style bandit with a variance-aware width, run over all d nodes and ignoring the graph. It is the no-structure comparison and also the bandit inside BARE 2605.00489 §2.2 2605.00489 alg. 1. In the experiments it is the baseline that BARE is compared against [arxiv:2605.00489 §5].

When to use which

Implementation sketch

Our own pseudocode of the common core. Notes on variants follow the block.

# Phase 1: explore uniformly until the horizon test fails  [alg. 2] [§3]
# Input: d nodes, horizon n
def explore(d, n):
    mean = zeros(d)                  # running estimate of dual influence
    t = 1
    while not stop_test(t, n, d, mean):   # horizon-dependent test [alg. 2]
        k = random_node(d)           # uniform sample [§4]
        s = observe_influenced_set(k)     # 0/1 vector over the d nodes
        mean = running_average(mean, d * s, t)  # see caveats [§4]
        t = t + 1
    width = keep_width(t, n, d, mean)     # [alg. 2]
    keep = max(mean) - mean <= width      # candidate mask [alg. 2]
    return keep, t

# Phase 2: any minimax-style bandit on the kept nodes [alg. 2] [§5]
keep, t_hat = explore(d, n)
bandit = GraphMOSS(arms = where(keep))   # e.g. in [alg. 2]
for step in range(t_hat, n):
    arm = bandit.choose()
    influenced = observe_influenced_set(arm)
    bandit.update(arm, reward = size(influenced))   # [§2.1]

Notes. The stop test and the keep width both use n and d through log(nd) alg. 2; the experiments scale these terms by 0.01 §5. The paper does not state a warm start: whether exploration samples seed the bandit is not given alg. 1 §5. A conservative reading is to start the bandit fresh on the kept set.

Contradictions

None known across cards; only one card lists this concept. Inside the paper, the analysed constants and the experimental constants differ. The experiments multiply the BARE confidence terms by 0.01, so the plots test a modified version of the algorithm, not the one the bounds cover 2605.00489 §5 2605.00489 §3.

Caveats

• Single source. Every result comes from one paper. The regret results are theoretical, with constants not given. The empirical results are plots, with no numeric regret values 2605.00489 §5.
• Estimator form. The printed update divides by t + 1, while the proof uses the average over the t exploration samples 2605.00489 alg. 2 2605.00489 §4. Implement the one you are testing against.
• Unused confidence level. The experiments set δ = 0.01, but the algorithm takes no δ input; the widths use log(nd) only 2605.00489 §5 2605.00489 alg. 2.
• Definition of T*. Definition 1 and Remark 1 disagree on whether T* must be greater than 0 or greater than 1 2605.00489 §3.
• Bandit variance estimate. GraphMOSS's variance estimator is not given 2605.00489 alg. 1.
• Minimax claim. Corollary 1 calls the bound minimax optimal in terms of D*. The argument is sketched only 2605.00489 §3 2605.00489 §4.1.
• Cost. Each exploration step updates all d nodes, so per-round work is at least linear in d. No complexity bound is stated 2605.00489 alg. 2.
• Edge probabilities. The experiment text sets p = 0.8 "for all i and j" but describes neighbours only. Edges-only is the likely reading, but it is not stated 2605.00489 §5.
• Code. No official code is known for the paper; see its card.

Papers

• Revealing graph bandits for maximizing local influence: introduces BARE, a detect-then-bandit method whose regret scales with a detectable dimension, with author-reported experiments on four graphs.