# Thresholding Graph Bandits with GrAPL

arXiv: https://arxiv.org/abs/1905.09190 · HTML: https://mlsanity.com/paper/1905.09190/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2019.

## Built on by (most cited first, 5 of 5)

- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem](https://mlsanity.com/paper/2403.06230/) (2024)
- [Learning the Structure of Large Networked Systems Obeying Conservation Laws](https://mlsanity.com/paper/2206.07083/) (2022)
- [A Finite-Horizon Approach to Active Level Set Estimation](https://mlsanity.com/paper/2310.11985/) (2023)

## Abstract (arXiv)

In this paper, we introduce a new online decision making paradigm that we call Thresholding Graph Bandits. The main goal is to efficiently identify a subset of arms in a multi-armed bandit problem whose means are above a specified threshold. While traditionally in such problems, the arms are assumed to be independent, in our paradigm we further suppose that we have access to the similarity between the arms in the form of a graph, allowing us gain information about the arm means in fewer samples. Such settings play a key role in a wide range of modern decision making problems where rapid decisions need to be made in spite of the large number of options available at each time. We present GrAPL, a novel algorithm for the thresholding graph bandit problem. We demonstrate theoretically that this algorithm is effective in taking advantage of the graph structure when available and the reward function homophily (that strongly connected arms have similar rewards) when favorable. We confirm these theoretical findings via experiments on both synthetic and real data.