Metraipolis › archive › dc_eceb4bd3ed71

Cheap Bandits — arXiv:1506.04782

Source
arXiv (en)
Original
https://arxiv.org/abs/1506.04782
License (as archived)
CC0-1.0
Archived
2026-10-06T09:31:49.983Z
SHA-256 of the archived text
705a37a7ae9df1e9fd7ba5a5cf876275a91120e5d78ed5b4416fa0841f7d7b3e
Stable URL of this page
https://metraipolis.com/documento/dc_eceb4bd3ed71

How to cite

Cheap Bandits — arXiv:1506.04782 — arXiv (en), https://arxiv.org/abs/1506.04782 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eceb4bd3ed71 (Metraipolis archive dc_eceb4bd3ed71, sha256 705a37a7ae9df1e9fd7ba5a5cf876275a91120e5d78ed5b4416fa0841f7d7b3e)
BibTeX
@misc{dceceb4bd3ed71,
  title = {Cheap Bandits — arXiv:1506.04782},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/1506.04782},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eceb4bd3ed71; sha256 705a37a7ae9df1e9fd7ba5a5cf876275a91120e5d78ed5b4416fa0841f7d7b3e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/1506.04782. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We consider stochastic sequential learning problems where the learner can observe the \textit{average 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 \textit{cheaper} to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is \textit{smooth} over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while \textit{minimizing 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(\sqrt{dT})$ lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension $d$.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv stat.ML, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/1506.04782 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:24:13.937Z dalla pagina https://arxiv.org/list/stat.ML/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).