RUS  ENG
Full version
JOURNALS // Matematicheskaya Teoriya Igr i Ee Prilozheniya // Archive

Mat. Teor. Igr Pril., 2022 Volume 14, Issue 2, Pages 3–30 (Mi mgta299)

Customization of J. Bather UCB strategy for a Gaussian multi-armed bandit

Sergey V. Garbar, Alexander V. Kolnogorov

Yaroslav-the-Wise Novgorod State University

Abstract: We consider the customization of the UCB strategy, which was first proposed by J. Bather for Bernoulli two-armed bandit, to the case of a Gaussian multi-armed bandit describing batch data processing. This optimal control problem has classical interpretation as a game with nature, in which the payment function of the player is the expected loss of total income caused by incomplete information. The goal is stated in minimax setting. For the considered game with nature, we present an invariant description of the control with a horizon equal to one, which allows to perform computations in two ways: using Monte-Carlo simulations and analytically by dynamic programming technique. For various configurations of the considered game with nature, we have found saddle points, which characterize the optimal control and the worst-case distribution of the parameters of the multi-armed bandit.

Keywords: multi-armed bandit problem, Gaussian multi-armed bandit, minimax approach, UCB rule, invariant description, Monte-Carlo simulations, dynamic programming.

UDC: 519.832, 519.245
BBK: 22.18

Received: 10.10.2021
Revised: 03.03.2022
Accepted: 16.05.2022



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024