# Cheap Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2015.

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

- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [Spectral bandits](https://mlsanity.com/paper/2604.25272/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

We consider stochastic sequential learning problems where the learner can observe the textitaverage reward of several actions. Such a setting is interesting in many applications involving monitoring and surveillance, where the set of the actions to observe represent some (geographical) area. The importance of this setting is that in these applications, it is actually textitcheaper to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is textitsmooth over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while textitminimizing the sensing cost. In this paper we propose CheapUCB, an algorithm that matches the regret guarantees of the known algorithms for this setting and at the same time guarantees a linear cost again over them. As a by-product of our analysis, we establish a Omega(√dT) lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension d.