# Bounded Regret for Finite-Armed Structured Bandits

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2014.

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

- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Thompson Sampling with Diffusion Generative Prior](https://mlsanity.com/paper/2301.05182/) (2023)
- [Thompson Sampling for Bandits with Clustered Arms](https://mlsanity.com/paper/2109.01656/) (2021)
- [Causally Abstracted Multi-armed Bandits](https://mlsanity.com/paper/2404.17493/) (2024)
- [Experiment Planning with Function Approximation](https://mlsanity.com/paper/2401.05193/) (2024)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [Quantum contextual bandits and recommender systems for quantum data](https://mlsanity.com/paper/2301.13524/) (2023)
- [Bad-Policy Density: A Measure of Reinforcement Learning Hardness](https://mlsanity.com/paper/2110.03424/) (2021)
- [Best Arm Identification under Additive Transfer Bandits](https://mlsanity.com/paper/2112.04083/) (2021)
- [A Classification View on Meta Learning Bandits](https://mlsanity.com/paper/2504.04505/) (2025)
- [TSEC: a framework for online experimentation under experimental constraints](https://mlsanity.com/paper/2101.06592/) (2021)
- [Latent Order Bandits](https://mlsanity.com/paper/2605.07304/) (2026)

## Abstract (arXiv)

We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.