Invariant Description of Control in a Gaussian One-Armed Bandit Problem

Рассматривается задача об одноруком бандите в приложении к пакетной обработке данных, если имеются два альтернативных метода обработки с разной эффективностью, причем эффективность второго метода априори неизвестна. В процессе обработки необходимо определить наиболее эффективный метод и обеспечить его преимущественное использование. Обработка выполняется пакетами, поэтому распределение доходов является гауссовским. Мы рассматриваем случай априори неизвестных математического ожидания и дисперсии одношагового дохода, соответствующих второму действию. Этот случай описывает ситуацию, когда сами пакеты и их количество имеют умеренные или небольшие объемы. Получены рекуррентные уравнения для вычисления байесовского риска и функции потерь, которые затем представлены в инвариантном виде с горизонтом управления, равным единице. Это позволяет получить оценки байесовского и минимаксного рисков, которые справедливы для всех горизонтов управления, кратных количеству обработанных пакетов.

Ключевые слова

однорукий бандит; пакетная обработка; байесовский и минимаксный подходы; инвариантное описание.

Литература

1. Berry D.A., Fristedt B. Bandit Problems: Sequential Allocation of Experiments. London, New York, Chapman and Hall, 1985.
2. Presman E.L., Sonin I.M. Sequential Control with Incomplete Information. New York, Academic Press, 1990.
3. Tsetlin M.L. Automaton Theory and Modeling of Biological Systems. New York, Academic Press, 1973.
4. Sragovich V.G. Mathematical Theory of Adaptive Control. Singapore, World Scientific, 2006.
5. Gittins J.C. Multi-Armed Bandit Allocation Indices. Chichester, John Wiley and Sons, 1989.
6. Lattimore T., Szepesvari C. Bandit Algorithms. Cambridge, Cambridge University Press, 2020.
7. Kolnogorov A.V. One-Armed Bandit Problem for Parallel Data Processing Systems. Problems of Information Transmission, 2015, vol. 51, no. 2, pp. 177-191. DOI: 10.1134/S0032946015020088
8. Perchet V., Rigollet P., Chassang S., Snowberg E. Batched Bandit Problems. The Annals of Statistics, 2016, vol. 44, no. 2, pp. 660-681. DOI: 10.1214/15-AOS1381
9. Vogel W. An Asymptotic Minimax Theorem for the Two-Armed Bandit Problem. The Annals of Mathematical Statistics, 1960, vol. 31, no. 2, pp. 444-451.
10. Kolnogorov A. Gaussian One-Armed Bandit Problem. 2021 XVII International Symposium "Problems of Redundancy in Information and Control Systems". Moscow, Institute of Electrical and Electronics Engineers, 2021, pp. 74-79. DOI: 10.1109/REDUNDANCY52534.2021.9606464
11. Bradt R.N., Johnson S.M., Karlin S. On Sequential Designs for Maximizing the Sum of n Observations. The Annals of Mathematical Statistics, 1956, vol. 27, pp. 1060-1074. DOI: 10.1214/aoms/1177728073
12. Chernoff H., Ray S.N. A Bayes Sequential Sampling Inspection Plan. The Annals of Mathematical Statistics, 1965, vol. 36, pp. 1387-1407. DOI: 10.1214/aoms/1177699898
13. Kolnogorov A.V. Gaussian One-Armed Bandit with Both Unknown Parameters. Siberian Electronic Mathematical Reports, 2022, vol. 19, no. 2, pp. 639-650. Available at: http://semr.math.nsc.ru/v19n2ru.html