Simulation of the mirror descent algorithm on distributions with different variances

In this article, we consider the operation of the mirror descent algorithm in a random environment in which the distributions of one-step incomes have close expectations and different variances. Particular attention is paid to the version of the algorithm for batch processing which allows one to achieve better processing time without increasing losses. The results of numerical modeling of the operation of the algorithms are presented.


Introduction
Consider the task of processing an incoming data stream, for example, the arrival of computational tasks on a server. Having received the task, the server has to decide which executive machine to send it to. There can be several such machines and each of them works better on tasks of a certain type. We consider the flow of tasks to be uniform but the type of tasks is not known to the server in advance. Choosing a server is considered successful if the executor managed to complete the task at the scheduled time. Thus, the main task of the server is to maximize the number of successful executions when processing a stream of a fixed size.
In the literature, this problem is described as «n-armed bandit» [1][2], where n is the number of available actions. In case of a server, n is the number of different executive machines. Server operation is considered as control in a random environment with n available actions on a fixed horizon.
In this study, we restrict the number of available actions to two and consider a two-alternative random environment. Let's consider a random process n  , N n ,..., 1  , which values are interpreted as random incomes and depend only on the choice of the current action n x , . We introduce the loss function over the control horizon N as follows where  is the vector of mathematical expectations of incomes when choosing both actions.
In previous papers [3], [5] we considered the case of binary incomes, known as the Bernoulli distribution. Upon successful processing, we get 1, otherwise 0, i.e., It turned out in [3], [5] that one has to study operation of the algorithms only at close values of the mathematical expectations of both actions. Otherwise, determining the best action is not difficult. Hence, is the maximum possible variance of one-step income of Bernoulli two-armed bandit.. In this case, with close mathematical expectations, we had almost equal variances of distributions of incomes for both actions. However, in real-world problems, variances can vary. In this study, we consider the operation of algorithms on specially selected distributions of incomes with close mathematical expectations but with different variances. A description of these distributions can be seen in section 4. Section 2 describes the mirror descent algorithm for one-by-one data processing (Algorithm 1) for the task of minimizing the loss function. Section 3 provides two versions of the algorithm for batch processing (Algorithm 2 and Algorithm 3). Section 5 contains the results of numerical modeling of the operation of algorithms on various distributions of incomes.

Algorithm for one-by-one data processing
This algorithm is based on the algorithm from [4] but has some differences. In particular, the problem statement of the algorithm differs.
2) Get the amount of income n  for the use of action according to the following formula For the resulting loss function, normalization is performed as follows:

Algorithms for batch processing
If one sends tasks to executors in groups, he (or she) can get a significant gain in processing speed. In batch processing, the overall control horizon is divided into M is the size of the group. Thus, the total processing time no longer depends on the control horizon but depends only on the number of stages T . The effectiveness of the method also increases when using the same type of executors with the possibility of parallel execution. Consider the first version of the algorithm for batch processing. The probability of applying a specific action to each task in the group is selected by the value of the vector according to the following formula Let's consider one more variant of the algorithm for group processing. It involves dividing the group into two parts, in proportion to the current value of n p , and then performs the corresponding action for each of the parts. Let ) ; ( the nearest integers to

Algorithm 3
For all T t , , 1   perform the following actions: 1) Calculate for which part of the batch the first action should be used and for which the second one The projection operator is used because

Results of numerical simulation
This section presents the results of numerical modeling of the operation of algorithms in various cases. Consider the operation of the Algorithm 3 on distributions with different variances. To this end, we use three types of distributions: Bernoulli  On figure 1 one can see that Algorithm 3 works in a similar way regardless of the variance of the distribution as it was theoretically shown in [6].

Conclusion
This article examined the operation of the mirror descent algorithm in a random environment in which the distributions of incomes have close mathematical expectations but different variances. Algorithms were presented for one-by-one data processing (Algorithm 1) and for group processing (Algorithm 2 and Algorithm 3).
It was shown that group processing using Algorithm 3 not only allows to optimize the total control time due to the parallel execution of tasks in each group, but also ensures the independence of the resulting losses from the variance of the distribution of income.
Algorithm 2 does not have the independence property of the resulting losses from the variance but it demonstrates convergence to Algorithm 1 with a decrease in the size of the processed group on distributions with different variances in the same way as on Bernoulli distributions.