Bounded Regret for Finitely Parameterized Multi-Armed Bandits

Abstract

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.

15 pages, 7 figures, Reinforcement Learning, Multi-armed Bandits, Sequential Decision Making

References in corpus (6)

• Bounded Regret for Finite-Armed Structured Bandits
• Minimal Exploration in Structured Stochastic Bandits
• Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays
• Leveraging Side Observations in Stochastic Bandits
• Bounded regret in stochastic multi-armed bandits
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits

Cited by in corpus (1)

• Bounded Regret for Finitely Parameterized Multi-Armed Bandits