Ученые решили фундаментальную математическую проблему — «задачу о двуруком бандите»

В Новгородском университете решили математическую «задачу о двуруком бандите» и внесли вклад в решение фундаментальной математической проблемы. Полученные результаты научного исследования можно применять в оптимизации пакетной обработки больших данных.

Фундаментальное исследование — это экспериментальное или теоретическое исследование, направленное на получение новых знаний. Такие исследования не преследуют цель немедленного практического применения и ориентированы на долгосрочную перспективу развития. Например, когда-то давно английский министр финансов спросил у физика Майкла Фарадея, для чего могут быть полезны его исследования по электричеству. На это ученый ответил, что однажды результаты его исследований будут обложены налогами.

Что касается задачи о двуруком бандите, то это сравнительно новая математическая проблема. Она поставлена в середине XX века независимо друг от друга американским математиком Гербертом Роббинсом и советским кибернетиком Михаилом Львовичем Цетлиным. И принадлежит к науке, которая называется reinforcement learning (в переводе с англ «подкрепляемое обучение»). Открытия в этой области сегодня напрямую относятся к исследованиям в области искусственного интеллекта.

Чем опасен «двурукий бандит»?
Суть проблемы решения «задачи о двуруком бандите» лежала в следующем.

Двурукий бандит — это игральный автомат с двумя рукоятками. Нажатие на каждую рукоятку приносит игроку единичный случайный выигрыш. Например, с некоторыми вероятностями он может выиграть один рубль при нажатии на каждую рукоятку. Обе вероятности фиксированы, различны, но неизвестны игроку.

Теперь поясним, что значит случайный выигрыш. Скажем, пусть вероятность выигрыша на первой рукоятке равна 0,7, а в игре можно нажимать рукоятки 10 раз. Если все 10 раз нажимать только первую рукоятку, то выигрыш может быть самым разным — от 0 до 10 рублей. Но если этот эксперимент повторить много раз, то выигрыш составит в среднем семь рублей за одну игру. Точно так же, если на второй рукоятке вероятность выигрыша равна 0,5, то средний выигрыш за выбор этой рукоятки 10 раз составит пять рублей за одну игру.

Целью игрока является максимизация именно этого среднего выигрыша за одну игру против автомата. При этом он может чередовать рукоятки в процессе игры. Если бы обе вероятности были известны, то оптимальной стратегией игрока было бы всегда выбирать рукоятку, которой соответствует большая вероятность единичного выигрыша. Однако, поскольку эти вероятности неизвестны, в процессе игры надо как-то сравнить обе рукоятки и обеспечить преимущественное применение лучшей.

Бандит выходит за пределы игрального зала
У задачи о двуруком бандите уже есть различные практические применения. Например, в интернете ее алгоритмы используют для продвижения товаров, подстраиваясь под неизвестные предпочтения пользователей. Исследование же, проведенное в Новгородском университете, направлено на оптимизацию так называемой пакетной обработки больших данных.

— Представим себе группу из 1000 пациентов, для лечения которых имеются два альтернативных лекарства, — объясняет на примере использования математического решения в Big Data автор проекта, Александр Колногоров, профессор кафедры прикладной математики и информатики, главный научный сотрудник Научно-исследовательского центра НовГУ.

— Применение каждого лекарства к лечению пациента дает с некоторой вероятностью единичный доход, если пациент поправился, и ничего, если продолжает болеть. Процесс лечения всех пациентов можно рассматривать как игру против двурукого бандита, а лекарства – как рукоятки, которые можно нажимать 1000 раз. Целью игры является максимизация среднего количества поправившихся пациентов.

Проблема в том, что пациентов нельзя лечить по очереди, так как результат действия лекарства требует значительного времени (к примеру, если он проявится через неделю, то на лечение 1000 пациентов потребуется 1000 недель, или около 19 лет). Но можно поступить другим образом: сначала дать оба лекарства двум сравнительно небольшим группам (допустим, из 100 пациентов). Посчитать через неделю, в какой группе поправилось больше людей. И дать целительное лекарство остальным 800 людям. В итоге все лечение займет две недели. Причем при правильном выборе размеров начальных групп эффективность такой пакетной обработки достаточно высока.

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

Для решения математической задачи использовались продвинутые математические методы. Были найдены оптимальные алгоритмы управления обработки данных, разбитых на большое число пакетов, и их точное математическое описание. Этого удалось добиться благодаря решению уравнений динамического программирования и дифференциальных уравнений в частных производных. Все это позволило построить ряд намного более простых с точки зрения реализации алгоритмов пакетной обработки, которые лишь немного (примерно на 10%) уступают в эффективности оптимальным.

Результаты исследования представлены на международных научных конференциях (по стохастическим методам и теории оптимизации и исследованию операций). Опубликованы в научных журналах: «Проблемы передачи информации», «Автоматика и телемеханика», «Математическая теория игр и ее приложения». Рекомендации по возможному практическому применению раскрыты в отчетах по проекту.

В данный момент ученые продолжают работу над обобщением результатов на случай «многорукого бандита». Или игрального автомата с числом рукояток больше двух. Потому что результаты, полученные для двурукого бандита, могут быть автоматически перенесены для решения многорукого.

Научное исследование новгородских ученых было проведено на средства гранта Российского фонда фундаментальных исследований, полученного в 2020 году, и Министерства образования и науки, полученного в 2014 году. Средства пошли на закупку оборудования и оплату научной деятельности рабочей группы.