Аннотация:
Рассматривается задача о многоруком бандите в приложении к пакетной обработке больших данных, если имеется более двух альтернативных методов обработки с различными, априори неизвестными, эффективностями. В процессе обработки требуется определить наиболее эффективный метод и обеспечить его преимущественное использование. Управление осуществляется на основе суммарных доходов в пакетах, которые в силу центральной предельной теоремы имеют приблизительно гауссовское распределение. Важной особенностью пакетной обработки является то, что она почти не приводит к увеличению максимальных потерь полного ожидаемого дохода, т.е. к увеличению минимаксного риска, если количество обрабатываемых данных и пакетов, на которые они разбиты, достаточно велико. Это означает, что гауссовский многорукий бандит обеспечивает универсальный подход к оптимальному управлению обработкой больших данных, если одношаговые доходы удовлетворяют центральной предельной теореме. Согласно этому подходу минимаксные стратегия и риск ищутся с использованием основной теоремы теории игр как байесовские, вычисленные относительно наихудшего априорного распределения, на котором байесовский риск максимален. Для этого дана характеризация наихудшего априорного распределения и получены рекуррентные уравнения в обычной и инвариантной форме с горизонтом управления, равным единице. В предельном случае, когда количество обрабатываемых пакетов бесконечно растет, получено дифференциальное уравнение в частных производных второго порядка. Приведен численный пример нахождения минимаксного риска и стратегии для трехрукого бандита.
Ключевые слова:
гауссовский многорукий бандит, игра с природой, байесовский и минимаксный подходы, основная теорема теории игр, пакетная обработка.
Полный текст:
PDF файл (331 kB)
Первая страница:
PDF файл