Online First 2025
УДК 519.83 + 519.244
MSC: 91A35, 62L05, 62C10
https://doi.org/10.21538/0134-4889-2025-31-3-fon-06
(Full Text)
Рассматривается задача о многоруком бандите в приложении к пакетной обработке больших данных, если имеется более двух альтернативных методов обработки с различными, априори неизвестными, эффективностями. В процессе обработки требуется определить наиболее эффективный метод и обеспечить его преимущественное использование. Управление осуществляется на основе суммарных доходов в пакетах, которые в силу центральной предельной теоремы имеют приблизительно гауссовское распределение. Важной особенностью пакетной обработки является то, что она почти не приводит к увеличению максимальных потерь полного ожидаемого дохода, т. е. к увеличению минимаксного риска, если количество обрабатываемых данных и пакетов, на которые они разбиты, достаточно велико. Это означает, что гауссовский многорукий бандит обеспечивает универсальный подход к оптимальному управлению обработкой больших данных, если одношаговые доходы удовлетворяют центральной предельной теореме. Согласно этому подходу минимаксные стратегия и риск ищутся с использованием основной теоремы теории игр как байесовские, вычисленные относительно наихудшего априорного распределения, на котором байесовский риск максимален. Для этого дана характеризация наихудшего априорного распределения и получены рекуррентные уравнения в обычной и инвариантной форме с горизонтом управления, равным единице. В предельном случае, когда количество обрабатываемых пакетов бесконечно растет, получено дифференциальное уравнение в частных производных второго порядка. Приведен численный пример нахождения минимаксного риска и стратегии для трехрукого бандита.
Ключевые слова: гауссовский многорукий бандит, игра с природой, байесовский и минимаксный подходы, основная теорема теории игр, пакетная обработка.
Поступила 12.05.2025
После доработки 16.06.2025
Принята к публикации 23.06.2025
Опубликована онлайн 26.06.2025
Колногоров Александр Валерианович
д-р физ.-мат. наук, профессор
Новгородский государственный университет им. Ярослава Мудрого
г. Великий Новгород
e-mail: kolnogorov53@mail.ru
Ссылка на статью: А.В. Колногоров. Минимаксный подход к задаче о гауссовском многоруком бандите // Тр. Ин-та математики и механики УрО РАН. 2025. https://doi.org/10.21538/0134-4889-2025-31-3-fon-06
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. https://doi.org/10.21538/0134-4889-2025-31-3-fon-06
