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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 1 scientific paper (total in 1 paper)

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
Received: 06.04.2020
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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:116
    References:3
    First page:4

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021