---
kind: concept
slug: bandits-with-graph-feedback
title: Bandits with graph feedback
summary: >-
  Bandit setting where a pull reveals the set of nodes the chosen node influences, not just a count. BARE explores uniformly to shortlist candidates, then runs a standard bandit on them; its regret scales with a detectable dimension, not the node count. One paper so far; guarantees and experiments are author-reported.
tags: [bandits, graphs, influence-maximisation, regret-bounds]
papers: ["2605.00489"]
related: [multi-armed-bandit, no-regret-learning]
status: draft
updated_at: 2026-11-08
---

## 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 [arxiv: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 [arxiv:2605.00489 §2.1].

The setting builds on the MOSS bandit and on graph bandits with side
observations [arxiv:2605.00489 §1] [arxiv: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 [arxiv: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
[arxiv:2605.00489 §3]. Nodes are ranked by dual influence, while regret is
measured with primal influence; the two agree only for undirected graphs
[arxiv:2605.00489 §2.1].

## Variants

### BARE: explore to detect, then bandit

BARE works in two phases [arxiv:2605.00489 §3] [arxiv: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
   [arxiv: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 [arxiv:2605.00489 §5]
   [arxiv: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
[arxiv:2605.00489 §3]. For undirected graphs the n ε* term is absent
[arxiv:2605.00489 §3]. A matching lower bound holds for d ≥ Cn
[arxiv:2605.00489 §3]. Card: [Revealing graph bandits for maximizing local
influence](/papers/2605.00489).

### 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 [arxiv:2605.00489 §2.2] [arxiv:2605.00489 alg. 1]. In the
experiments it is the baseline that BARE is compared against [arxiv:2605.00489
§5].

## When to use which

| Situation | Use | Why |
|---|---|---|
| You observe only a count of influenced nodes | Plain bandit over d arms, e.g. GraphMOSS | The graph cannot be exploited; regret is of the plain-bandit order [arxiv:2605.00489 §2.2] |
| Hidden graph, large d, one node probed per round, undirected | BARE | Bound scales with D* and has no n ε* term [arxiv:2605.00489 §3] |
| Same, but directed | BARE, with caution | Bound adds an n ε* term, and the algorithm does not correct for it [arxiv:2605.00489 §3] |
| Horizon n known in advance | BARE | BARE takes n as input and is not anytime [arxiv:2605.00489 alg. 2] [arxiv:2605.00489 §3] |
| Many nodes are near the best in dual influence | Expect smaller gains | The bound grows with D*. The paper reports a much smaller gain on Gnutella (empirical D̂ = 3916) than on Enron (D̂ = 564) or Facebook (D̂ = 125). The card does not establish the cause [arxiv:2605.00489 fig. 1] [arxiv:2605.00489 §5] |
| Influence probabilities are high (p near one) | Expect the problem to be easier | The paper says p near one makes the problem easier, and that BARE and GraphMOSS perform similarly when p is near zero [arxiv:2605.00489 §5] |

## Implementation sketch

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

```pseudocode
# 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 [arxiv:2605.00489 §5]
[arxiv: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 [arxiv:2605.00489 §5].
- **Estimator form.** The printed update divides by t + 1, while the proof
  uses the average over the t exploration samples [arxiv:2605.00489 alg. 2]
  [arxiv: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 [arxiv:2605.00489 §5]
  [arxiv: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 [arxiv:2605.00489 §3].
- **Bandit variance estimate.** GraphMOSS's variance estimator is not given
  [arxiv:2605.00489 alg. 1].
- **Minimax claim.** Corollary 1 calls the bound minimax optimal in terms of D*.
  The argument is sketched only [arxiv:2605.00489 §3] [arxiv: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 [arxiv: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 [arxiv:2605.00489 §5].
- **Code.** No official code is known for the paper; see its card.

## Papers

- [Revealing graph bandits for maximizing local influence](/papers/2605.00489):
  introduces BARE, a detect-then-bandit method whose regret scales with a
  detectable dimension, with author-reported experiments on four graphs.