Problemy Peredachi Informatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

 Probl. Peredachi Inf., 2020, Volume 56, Issue 3, Pages 86–111 (Mi ppi2323)

Automata Theory

Gaussian two-armed bandit: limiting description

A. V. Kolnogorov

Department of Applied Mathematics and Information Science, Yaroslav-the-Wise Novgorod State University, Novgorod, Russia

Abstract: For a Gaussian two-armed bandit, which arises when batch data processing is analyzed, the minimax risk limiting behavior is investigated as the control horizon $N$ grows infinitely. The minimax risk is searched for as the Bayesian one computed with respect to the worst-case prior distribution. We show that the highest requirements are imposed on the control in the domain of “close” distributions where mathematical expectations of incomes differ by a quantity of the order of $N^{-1/2}$. In the domain of “close” distributions, we obtain a recursive integro-difference equation for finding the Bayesian risk with respect to the worst-case prior distribution, in invariant form with control horizon one, and also a second-order partial differential equation in the limiting case. The results allow us to estimate the performance of batch processing. For example, the minimax risk corresponding to batch processing of data partitioned into $50$ batches can be only $2%$ greater than its limiting value when the number of batches grows infinitely. In the case of a Bernoulli two-armed bandit, we show that optimal one-by-one data processing is not more efficient than batch processing as $N$ grows infinitely.

Keywords: Gaussian two-armed bandit, minimax and Bayesian approaches, batch processing, asymptotic minimax theorem.

 Funding Agency Grant Number Russian Foundation for Basic Research 20-01-00062 Supported in part by the Russian Foundation for Basic Research, project no. 20-01-00062.

DOI: https://doi.org/10.31857/S0555292320030055

Full text: PDF file (387 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2020, 56:3, 278–301

Bibliographic databases:

UDC: 621.391.1 : 519.713 : 517.977.5
Revised: 02.06.2020
Accepted:02.06.2020

Citation: A. V. Kolnogorov, “Gaussian two-armed bandit: limiting description”, Probl. Peredachi Inf., 56:3 (2020), 86–111; Problems Inform. Transmission, 56:3 (2020), 278–301

Citation in format AMSBIB
\Bibitem{Kol20} \by A.~V.~Kolnogorov \paper Gaussian two-armed bandit: limiting description \jour Probl. Peredachi Inf. \yr 2020 \vol 56 \issue 3 \pages 86--111 \mathnet{http://mi.mathnet.ru/ppi2323} \crossref{https://doi.org/10.31857/S0555292320030055} \elib{https://elibrary.ru/item.asp?id=45219337} \transl \jour Problems Inform. Transmission \yr 2020 \vol 56 \issue 3 \pages 278--301 \crossref{https://doi.org/10.1134/S0032946020030059} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000579453900005} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85092777395} 

• http://mi.mathnet.ru/eng/ppi2323
• http://mi.mathnet.ru/eng/ppi/v56/i3/p86

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Aleksandr V. Kolnogorov, Aleksandr V. Nazin, Dmitrii N. Shiyan, “Zadacha o dvurukom bandite i paketnaya versiya algoritma zerkalnogo spuska”, MTIP, 13:2 (2021), 9–39
•  Number of views: This page: 116 References: 3 First page: 4