Stochastic differential equations for limiting description of UCB rule for Gaussian multi-armed bandits
This work provides a theoretical analysis for optimizing bandit algorithms in scenarios with close reward distributions, which is incremental as it builds on existing UCB methods.
The authors tackled the problem of describing the upper confidence bound (UCB) strategy for Gaussian multi-armed bandits with known horizon sizes by developing a limiting description using stochastic and ordinary differential equations, and they estimated the minimal horizon size where normalized regret does not exceed the maximum possible, based on Monte-Carlo simulations for close reward distributions.
We consider the upper confidence bound strategy for Gaussian multi-armed bandits with known control horizon sizes $N$ and build its limiting description with a system of stochastic differential equations and ordinary differential equations. Rewards for the arms are assumed to have unknown expected values and known variances. A set of Monte-Carlo simulations was performed for the case of close distributions of rewards, when mean rewards differ by the magnitude of order $N^{-1/2}$, as it yields the highest normalized regret, to verify the validity of the obtained description. The minimal size of the control horizon when the normalized regret is not noticeably larger than maximum possible was estimated.