Вестник НовГУ

Вестник НовГУ > 2018 > 3 (109) Технические науки > Колногоров А.В. Гауссовский однорукий бандит и оптимизация пакетной обработки

Колногоров А.В. Гауссовский однорукий бандит и оптимизация пакетной обработки

УДК 519.865
К о л н о г о р о в А. В. Гауссовский однорукий бандит и оптимизация пакетной обработки // Вестн. Новг. гос. ун-та. Сер.: Технические науки. 2018. № 3 (109). С.20–24. Библиогр. 10 назв.

К л ю ч е в ы е с л о в а: задача о двуруком бандите, задача об одноруком бандите, управление в случайной среде, минимаксный и байесовский подходы, пакетная обработка

В минимаксной постановке рассматривается задача об одноруком бандите, т.е. о двуруком бандите с известным распределением одношагового дохода за выбор первого действия. Распределение одношагового дохода за выбор второго действия предполагается нормальным (гауссовским) с неизвестным математическим ожиданием и дисперсией. Такая постановка задачи естественно возникает при оптимизации пакетной обработки, если для обработки имеются два альтернативных метода с известной априори эффективностью первого метода. Показано, что минимаксные стратегия и риск могут быть найдены как байесовские, вычисленные относительно наихудшего априорного распределения параметра, и получено рекуррентное интегро-разностное уравнение для их нахождения. Установлено, что пакетная обработка практически не влияет на величину минимаксного риска, если количество обрабатываемых пакетов достаточно велико.
-----------------------------------------------------------------------------
UDC 519.865
K o l n o g o r o v A. V. Gaussian one-armed bandit and optimization of batch processing // Vestnik NovSU. Issue: Engineering Sciences. 2018. № 3 (109). P.20–24. The reference list 10 items.

K e y w o r d s: two-armed bandit problem, one-armed bandit problem, control in a random environment, minimax and Bayesian approaches, batch processing

In the minimax setting, one-armed bandit problem is considered, i.e. the two-armed bandit problem with a known distribution of one-step income corresponding to the first action. Distribution of one-step income, corresponding to the second action, is assumed to be normal (Gaussian) with unknown mathematical expectation and variance. This setting naturally arises if the batch processing is optimized and there are two alternative processing methods available with a priori known efficiency of the first method. We show that minimax strategy and minimax risk can be determined as Bayesian ones calculated with respect to the worst-case prior distribution of the parameter, and obtain a recursive integro-difference equation for their determination. We prove that batch processing virtually does not influence the minimax risk if the number of batches is large enough.

Загрузить (630 КБ)