Stochastic differential equations for limiting description of UCB rule for Gaussian multi-armed bandits^††thanks: The reported study was funded by RFBR, project number 20-01-00062.

We consider a multi-armed bandit (MAB) problem. MAB can be viewed as a slot machine with $J$ arms. Each one of the arms can be selected for play, which yields some random income (reward). It is suggested that a number of times that a gambler can play is known beforehand. This number $N$ is called the control horizon size. Formally MAB is a controlled stochastic process $\xi(n),n=1,2,\ldots,N$. Value $\xi(n)$ only depends on the chosen arm. Gambler’s task is to maximize the total cumulative expected reward during the time of control.

MABs and corresponding algorithms are thoroughly analyzed in [13]. This is a reinforcement learning problem that exemplifies the exploration–exploitation tradeoff dilemma, so it is also studied in machine learning [1][3]. This problem is also known as the problem of adaptive control in a random environment [15] and the problem of expedient behavior [16]. MABs have also been used to model problems such as managing research projects in a large organization like a science foundation or a pharmaceutical company [9][2].

Further we consider a Gaussian MAB, when rewards are normally distributed with probability density functions

We assume that mean rewards $m_{1},m_{2},\ldots,m_{J}$ are unknown. In [11, 6] it is shown that incorrect values for variances only slightly affect overall rewards, therefore they can be estimated during the initial steps of control. That is the reason we assume that the variances of rewards $D_{1},D_{2},\ldots,D_{J}$ are assumed to be known. Therefore, the considered MAB can be described with vector parameter $\theta=(m_{1},\ldots,m_{J})$.

Gaussian MAB can be useful in a batch processing setting [14, 4, 10]. In that scenario gambler can only change the choice of the arm after they have used it for a given number of times (a batch). According to the central limit theorem, the sum of rewards for a batch will have a normal distribution (if batch size is relatively large) for a wide range of distributions of single-step rewards (if variances of rewards are finite). Batch processing can be also performed in parallel.

When some control strategy $\sigma$ is used, the expected cumulative reward will be lower than the maximally possible. That happens due to the fact that some number of steps will be spent to explore the distributions of arms’ rewards. Maximal cumulative reward would be obtained if the most lucrative arm was known and used on every step of the control. The expected difference between the maximal possible and the obtained rewards is called the regret and can be expressed as

$E_{\sigma,\theta}(\cdot)$ denotes the expected value calculated with respect to measure generated by strategy $\sigma$ and parameter $\theta$. Therefore, the goal of control is to minimize the regret.

Regret is dependent on the horizon size. To compare the strategies for different horizon sizes it is reasonable to consider the scaled regret

for $D=\max_{J}{D_{J}}$.

Single-step income on step $n$ can be expressed as

where $\eta_{l,n}$ is a standard normal random variable, and $l=1,2,\ldots,J$, $n=1,2,\ldots,N$.

Then cumulative reward for using $l$-th arm on step $n$ can be expressed as

where $\sqrt{n_{l}D_{l}}\eta$ is a normal random variable zero mean and variance $n_{l}D_{l}$ which we obtain when add up all of the rewards for the arm, $n_{l}$ is the number of times the $l$-th arm was used, $l=1,2,\ldots,J$; $n_{1}+\ldots+n_{J}=n$.

UCB strategy (as described by Lai [12]) with the parameter $a$ is defined as selection of arm maximizing the value

Strategy prescribes to use each of the arms once in the beginning of control to make the initial estimations regarding the mean rewards.

Presence of slowly growing term $\sqrt{2D_{l}\log(n/n_{l})/n_{l}}$ ensures the necessity to use every arm from time to time even if the estimated mean reward $X_{l}(n_{l})/n_{l}$ from its usage so far was lower than from the other arms due to some reason. That is the way the UCB strategy negotiates the exploration–exploitation dilemma: the gambler strives to maximize his or her reward by using the arm with the highest estimated mean, but also collects the information about the less explored arms.

We aim to build a limiting description (with a system of stochastic differential equations) of UCB strategy for a Gaussian multi-armed bandit when $N\to\infty$.

First, we give a limiting description for the case of two-armed bandit.

In [5, 7] an invariant description of a UCB strategy for a MAB was given. Invariant description scales the control horizon to a unit size by scaling the step number to smaller values (proportional to $N$). If $N\rightarrow\infty$, then step value is infinitely small.

Differentials of cumulative reward for using $l$-th arm can be expressed as

Here $W_{1},W_{2}$ are independent Wiener processes, $t_{l}$ is a continuous variable that corresponds to the usage ratio of each arm. Each of those equations correspond to a Wiener process with a constant drift. At each moment only one of values $t_{1},t_{2}$ can be increased as only one of the arms is used. Therefore, we consider two areas: in the first $t_{1}$ increases with time $t$, in the second $t_{2}$ increases. We’ll use indicators $I_{1}\left(t\right),I_{2}\left(t\right)$ for convenience.

If the first arm is chosen, then

$\begin{cases}dt_{1}=dt,\\ dt_{2}=0,\end{cases}$ and $\begin{cases}I_{1}(t)=1,\\ I_{2}(t)=0.\end{cases}$

If the second arm is chosen, then

$\begin{cases}dt_{1}=0,\\ dt_{2}=dt,\end{cases}$ and $\begin{cases}I_{1}(t)=0,\\ I_{2}(t)=1.\end{cases}$

We’ll take notice that $I_{2}\left(t\right)=1-I_{1}\left(t\right)$ and $dt_{2}=dt-dt_{1}$. Also remember that $t_{2}=t-t_{1}$: one and only one arm is chosen at every moment.

Each of the areas is determined according to the chosen strategy. UCB rule can be rewritten as

The area where the first arm is chosen will be defined by the condition $U_{1}\left(t,t_{1}\right)>U_{2}\left(t,t_{2}\right)$. Otherwise the second arm is chosen. To write this condition formally we use the Heaviside step function $H(\cdot)$ notation. Its value is zero for negative arguments and one for positive arguments.

For the UCB rule the indicator $I_{1}\left(t\right)$ will be the function of arguments $t,t_{1},X_{1},X_{2}$:

Using this notation, we write the system of two Itô stochastic differential equations and one ordinary differential equation equations to describe the UCB strategy for Gaussian two-armed bandit as

A series of Monte-Carlo simulations was performed to verify how the obtained system of equations describes the behavior of the Gaussian two-armed bandit when the UCB strategy is used. Without the loss of generality, we consider a Gaussian two-armed bandit with the zero mean reward for the first arm $m_{1}=0$. We observe how the normalized regret depends on the value of the mean reward for the second arm. Also, we assume $D_{1}=D_{2}=D=1$: in [7] it is shown that the maximum normalized regret is observed when the variances of the arm rewards are equal. Also, we set $a=1$.

Further we consider the case of “close” distributions of rewards as it is when the highest values of regret are observed [17]. Its definitive feature is that the difference of mean rewards has order $N^{-1/2}$:

Without the loss of generality we set $c_{1}=0$.

For the Gaussian multi-armed bandit simulations, we consider the cases of horizon sizes $N=200,\ 400$. Figure 1 contains the plots of normalized regret vs different values of $c_{2}$. Data for the plots are averaged over 10000 simulations. Figure 1 also shows the normalized regrets calculated for numerical solutions of presented stochastic differential equations for different values of $c_{2}$, averaged over 10000 simulations. We used the Euler–Maruyama method with step sizes of ${10}^{-3}$ and $5\cdot{10}^{-4}$.

We see that normalized regret is about the same for different horizon sizes. Also, the obtained system of equations gives the fitting description of the UCB strategy. We note that maximal normalized regret (approximately 0.73) in these simulations is observed when $c_{2}\approx 3.6$.

Having the limiting description allows to answer the question at what horizon size $N$ the normalized regret will not be noticeably larger than found maximal normalized regret. This question is of importance as the batch version of the algorithm (reported in [5, 7]) allows to vary the batch sizes. Parallel processing is possible in that case, and it can result in shorter processing times.

Figure 2 shows maximum normalized regret (in domain of close distributions of rewards) vs the control horizon size (left plot shows $N\in\left[3,100\right]$, right plot shows $N\in\left[36,100\right]$). Data is averaged over 10000 simulations.

We see that after $N=45$ the normalized regret exceeds the value found via the limiting description by no more than $2\%$. That means that for the batch processing (including parallel), the batch size may be chosen fairly large as long as the number of processed batches stays small of moderate (i.e. 50 or more).

Further we obtain a limiting description with a system of stochastic differential equations for the UCB strategy for Gaussian multi-armed bandit with $J$ arms using the similar reasoning as before. Considered MAB has unknown mean rewards $m_{1},\ldots,m_{J}$ and known variances of rewards $D_{1},\ldots,D_{J}$.

First, we express $t_{J}$ as

Indicator for the arm will be equal to one if the corresponding upper confidence bound is greater than the confidence bounds for all other arms. We express it as the product of step functions

for $l=1,\ldots,J-1$.

Then the system of $J$ stochastic differential equations and $J-1$ ordinary differential equations that describes the UCB strategy takes form

Presented system of equations also can be used to determine the horizon size at which the normalized regret converges. That can be used as the number of processed batches for the batch version of strategy, described in [5].

We consider a case of three-armed bandit as an example. We also consider the case of close distribution of rewards, described in section 3. The highest normalized regret is observed when $c_{1}=c_{2}=0$ and $c_{3}\approx 4.5$ [8]. This happens as in this situation the strategy must distinguish between the best arm and two competing arms with fairly similar but lower rewards. Simulations show that the normalized regret converges at horizon size $N=70$, i.e. is no more than $2\%$ greater than its value for larger horizon sizes.

We built and examined a limiting description (for horizon size $N\rightarrow\infty$) with a system of stochastic differential equations for the UCB strategy for the Gaussian multi-armed bandit.

A series of Monte-Carlo simulations was performed to verify the validity of obtained results for the case of two-armed bandit in the case of “close” distributions of rewards. Maximum normalized regret for the case $N\rightarrow\infty$ was determined. The minimal size of the control horizon when the normalized regret is not noticeably larger than maximum possible was estimated.