УДК 519.83 + 519.244
MSC: 91A35, 62L05, 62C10
https://doi.org/10.21538/0134-4889-2025-31-3-fon-06
Исследование выполнено в ходе реализации НИР “Математическое моделирование природных процессов”, выполняемой в рамках государственного задания в сфере научной деятельности. Исследование выполнено с использованием инфраструктуры Центра коллективного пользования “Высокопроизводительные вычисления и большие данные” (ЦКП “Информатика”) ФИЦ ИУ РАН (г. Москва).
Рассматривается задача о многоруком бандите в приложении к пакетной обработке больших данных, если имеется более двух альтернативных методов обработки с различными, априори неизвестными, эффективностями. В процессе обработки требуется определить наиболее эффективный метод и обеспечить его преимущественное использование. Управление осуществляется на основе суммарных доходов в пакетах, которые в силу центральной предельной теоремы имеют приблизительно гауссовское распределение. Важной особенностью пакетной обработки является то, что она почти не приводит к увеличению максимальных потерь полного ожидаемого дохода, т. е. к увеличению минимаксного риска, если количество обрабатываемых данных и пакетов, на которые они разбиты, достаточно велико. Это означает, что гауссовский многорукий бандит обеспечивает универсальный подход к оптимальному управлению обработкой больших данных, если одношаговые доходы удовлетворяют центральной предельной теореме. Согласно этому подходу минимаксные стратегия и риск ищутся с использованием основной теоремы теории игр как байесовские, вычисленные относительно наихудшего априорного распределения, на котором байесовский риск максимален. Для этого дана характеризация наихудшего априорного распределения и получены рекуррентные уравнения в обычной и инвариантной форме с горизонтом управления, равным единице. В предельном случае, когда количество обрабатываемых пакетов бесконечно растет, получено дифференциальное уравнение в частных производных второго порядка. Приведен численный пример нахождения минимаксного риска и стратегии для трехрукого бандита.
Ключевые слова: гауссовский многорукий бандит, игра с природой, байесовский и минимаксный подходы, основная теорема теории игр, пакетная обработка.
СПИСОК ЛИТЕРАТУРЫ
1. Berry D.A., Fristedt B. Bandit problems: sequential allocation of experiments. London, NY: Chapman and Hall, 1985. 275 p. https://doi.org/10.1007/978-94-015-3711-7
2. Lattimore T., Szepesvari C. Bandit algorithms. Cambridge: Cambridge Univ. Press, 2020. 586 p. https://doi.org/10.1017/9781108571401
3. Пресман Э.Л., Сонин И.М. Последовательное управление по неполным данным. М.: Наука, 1982. 256 с.
4. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969. 316 с.
5. Срагович В.Г. Адаптивное управление. М.: Наука, 1981. 384 с.
6. Perchet V., Rigollet P., Chassang S., Snowberg E. Batched bandit problems // Ann. Statist. 2016. Vol. 44, no. 2. P. 660–681. https://doi.org/10.1214/15-aos1381
7. Slivkins A. Introduction to multi-armed bandits. 184 p. https://arxiv.org/pdf/1904.07272
8. Kolnogorov A.V. Determination of the minimax risk for the normal two-armed bandit // IFAC Proceedings Volumes. 2010. Vol. 43, no. 10. P. 231–236. https://doi.org/10.3182/20100826-3-TR-4015.00044
9. Feldman D. Contributions to the ‘two-armed bandit’ problem // Ann. Math. Stat. 1962. Vol. 33. P. 847–856. https://doi.org/10.1214/aoms/1177704454
10. Заборскис А.А. Последовательный байесовый план выбора лучшего метода лечения // Автоматика и телемеханика. 1976. № 11. С. 144–153.
11. Rodman L. On the many-armed bandit problem // Ann. Probabil. 1978. Vol. 6, no. 3. P. 491–498. https://doi.org/10.1214/aop/1176995533
12. Fabius J., van Zwet W.R. Some remarks on the two-armed bandit // Ann. Math. Statist. 1970. Vol. 41. P. 1906–1916. https://doi.org/10.1214/aoms/1177696692
13. Колногоров А.В. К предельному описанию робастного параллельного управления в случайной среде // Автоматика и телемеханика. 2015. № 7. С. 111–126.
14. Lai T.L., Robbins H. Asymptotically efficient adaptive allocation rules // Adv. Appl. Math. 1985. Vol. 6. P. 4–22. https://doi.org/10.1016/0196-8858(85)90002-8
15. Vogel W. An asymptotic minimax theorem for the two-armed bandit problem // Ann. Math. Stat. 1960. Vol. 31, P. 444–451. https://doi.org/10.1214/aoms/1177705907
16. Juditsky A., Nazin A.V., Tsybakov A.B., Vayatis N. Gap-free bounds for stochastic multi-armed bandit // Proc. 17th World Congress IFAC. 2008. P. 11560–11563. https://doi.org/10.3182/20080706-5-KR-1001.01959
17. Ershov M.A., Voroshilov A.S. UCB strategy for Gaussian and Bernoulli multi-armed bandits // Commun. in Comp. and Inform. Sci. 2023. Vol. 1881. P. 67–78. https://doi.org/10.1007/978-3-031-43257-6_6
18. Russo D., Van Roy B. Learning to optimize via posterior sampling // Math. Oper. Research. 2014. Vol. 39, no. 4. P. 1221–1243. https://doi.org/10.1287/moor.2014.0650
19. Колногоров А.В. Гауссовский двурукий бандит и оптимизация групповой обработки данных // Пробл. передачи информации. 2018. Т. 54, № 1. С. 93–111.
Поступила 12.05.2025
После доработки 16.06.2025
Принята к публикации 23.06.2025
Опубликована онлайн 26.06.2025
Колногоров Александр Валерианович
д-р физ.-мат. наук, профессор
Новгородский государственный университет им. Ярослава Мудрого
г. Великий Новгород
e-mail: kolnogorov53@mail.ru
Ссылка на статью: А.В. Колногоров. Минимаксный подход к задаче о гауссовском многоруком бандите // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 3. С. 150–166.
English
A.V. Kolnogorov. Minimax approach to the Gaussian multi-armed bandit
We consider the multi-armed bandit problem in an application to batch processing of big data if there are more than two alternative processing methods with different a priori unknown efficiencies. During processing, it is necessary to determine a more effective method and ensure its preferential use. Control is performed on the basis of cumulative incomes in batches, which, by virtue of the central limit theorem, have approximately Gaussian distributions. An important feature of batch processing is that it almost does not lead to an increase in maximum losses of the total expected income, i.e., to an increase in minimax risk if the numbers of processed data and batches into which the data is divided are large enough. This means that Gaussian multi-armed bandit provides universal approach to optimal control of big data when one-step incomes satisfy the central limit theorem. According to this approach, minimax strategy and risk are sought using the main theorem of game theory as Bayesian ones calculated relative to the worst-case prior distribution at which the Bayesian risk is maximal. For this purpose, the characterization of the worst-case prior distribution is given and recursive equations in a usual and invariant form with a control horizon equal to one are obtained. In the limiting case when the number of processed batches grows infinitely, a second-order partial differential equation is obtained. A numerical example of finding minimax risk and strategy for a 3-armed bandit is given.
Keywords: Gaussian multi-armed bandit, Game with nature, Bayesian and minimax approaches, Main theorem of game theory, Batch processing.
Received May 12, 2025
Revised June 16, 2025
Accepted June 23, 2025
Published online June 26, 2025
Funding Agency. 1. The research was conducted as part of the scientific research project “Mathematical Modeling of Natural Processes”, implemented under the state assignment in the field of scientific activity. 2. The study was carried out using the infrastructure of the Shared Use Center “High-Performance Computing and Big Data” (SUC “Informatics”) of the Federal Research Center for Information Technology and Control of the Russian Academy of Sciences (Moscow).
Alexander Valerianovich Kolnogorov, Dr. Phys.-Math. Sci., Prof., Yaroslav-the-Wise Novgorod State University, Veliky Novgorod, 173003 Russia, e-mail: kolnogorov53@mail.ru
Cite this article as: A.V. Kolnogorov. Minimax approach to the Gaussian multi-armed bandit. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 150–166.
[References -> on the "English" button bottom right]
