# Bounded Regret for Finitely Parameterized Multi-Armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2020.

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

- [Information-directed sampling for bandits: a primer](https://mlsanity.com/paper/2512.20096/) (2025)

## Abstract (arXiv)

We consider the problem of finitely parameterized multi-armed bandits where the model of the underlying stochastic environment can be characterized based on a common unknown parameter. The true parameter is unknown to the learning agent. However, the set of possible parameters, which is finite, is known a priori. We propose an algorithm that is simple and easy to implement, which we call Finitely Parameterized Upper Confidence Bound (FP-UCB) algorithm, which uses the information about the underlying parameter set for faster learning. In particular, we show that the FP-UCB algorithm achieves a bounded regret under some structural condition on the underlying parameter set. We also show that, if the underlying parameter set does not satisfy the necessary structural condition, the FP-UCB algorithm achieves a logarithmic regret, but with a smaller preceding constant compared to the standard UCB algorithm. We also validate the superior performance of the FP-UCB algorithm through extensive numerical simulations.