Geodesic
Two-armed bandit problem and batch version of the mirror descent algorithm
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 13 (2021) no. 2, pp. 9-39

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the minimax setup for the two-armed bandit problem as applied to data processing if there are two alternative processing methods with different a priori unknown efficiencies. One should determine the most efficient method and provide its predominant application. To this end, we use the mirror descent algorithm (MDA). It is well-known that corresponding minimax risk has the order of $N^{1/2}$ with $N$ being the number of processed data and this bound is unimprovable in order. We propose a batch version of the MDA which allows processing data by packets that is especially important if parallel data processing can be provided. In this case, the processing time is determined by the number of batches rather than by the total number of data. Unexpectedly, it turned out that the batch version behaves unlike the ordinary one even if the number of packets is large. Moreover, the batch version provides significantly smaller value of the minimax risk, i.e., it considerably improves a control performance. We explain this result by considering another batch modification of the MDA which behavior is close to behavior of the ordinary version and minimax risk is close as well. Our estimates use invariant descriptions of the algorithms based on Gaussian approximations of incomes in batches of data in the domain of “close” distributions and are obtained by Monte-Carlo simulations.
Keywords: two-armed bandit problem, minimax approach, mirror descent algorithm, batch processing.
Mots-clés : EXP3 
@article{MGTA_2021_13_2_a1,
     author = {Alexander V. Kolnogorov and Alexander V. Nazin and Dmitry N. Shiyan},
     title = {Two-armed bandit problem and batch version of the mirror descent algorithm},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {9--39},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a1/}
}
TY  - JOUR
AU  - Alexander V. Kolnogorov
AU  - Alexander V. Nazin
AU  - Dmitry N. Shiyan
TI  - Two-armed bandit problem and batch version of the mirror descent algorithm
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2021
SP  - 9
EP  - 39
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a1/
LA  - ru
ID  - MGTA_2021_13_2_a1
ER  - 
%0 Journal Article
%A Alexander V. Kolnogorov
%A Alexander V. Nazin
%A Dmitry N. Shiyan
%T Two-armed bandit problem and batch version of the mirror descent algorithm
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2021
%P 9-39
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a1/
%G ru
%F MGTA_2021_13_2_a1
Alexander V. Kolnogorov; Alexander V. Nazin; Dmitry N. Shiyan. Two-armed bandit problem and batch version of the mirror descent algorithm. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 13 (2021) no. 2, pp. 9-39. http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a1/