Ученые Новгородского государственного университета решили математическую «задачу о двуруком бандите». Это стало вкладом в фундаментальную проблему — результаты применимы для оптимизации пакетной обработки больших данных.
«Двурукий бандит» — это автомат с двумя рукоятками, нажатие на каждую из которых дает случайный выигрыш с неизвестной вероятностью. Обе они фиксированы, различны, но неизвестны игроку. Основная сложность для игрока состоит в необходимости определить, какая из двух рукояток более выгодна. Цель игры — максимизировать суммарный выигрыш.
Несмотря на свой теоретический характер, «задача о двуруком бандите» обладает уже устоявшимся спектром практических реализаций. В частности, ее алгоритмические решения активно задействуются в интернет-рекламе для автоматического подбора и демонстрации коммерческих предложений, которые наиболее точно соответствуют невыявленным поведенческим паттернам пользователей.
Научная работа нацелена на расширение области применения этих подходов путем их адаптации к задачам оптимизации пакетной обработки больших данных, где требуется принятие решений для крупных групп объектов одновременно.
Представим себе группу из 1000 пациентов, для лечения которых имеются 2 альтернативных лекарства. Применение каждого лекарства к лечению пациента дает с некоторой вероятностью единичный доход, если пациент поправился, и ничего, если продолжает болеть. Процесс лечения всех пациентов можно рассматривать как игру против двурукого бандита, а лекарства — как рукоятки, которые можно нажимать 1000 раз. Целью игры является максимизация среднего количества поправившихся пациентов. Проблема в том, что пациентов нельзя лечить по очереди, так как результат действия лекарства требует значительного времени. К примеру, если он проявится через неделю, то на лечение 1000 пациентов потребуется 1000 недель, или около 19 лет. Но можно поступить другим образом: сначала дать оба лекарства двум сравнительно небольшим группам, допустим, из 100 пациентов. Посчитать через неделю, в какой группе поправилось больше людей. И дать целительное лекарство остальным 800 людям. В итоге все лечение займет 2 недели. Причем при правильном выборе размеров начальных групп эффективность такой пакетной обработки достаточно высока.
Несмотря на то, что «задача о двуруком бандите» относительно молода в математическом контексте, ее исторические корни восходят к середине XX века. Формулировка этой проблемы появилась практически одновременно, но независимо друг от друга, в работах двух выдающихся ученых: американского математика Герберта Роббинса и советского кибернетика Михаила Цетлина. Сегодня открытия в этой области используют в исследованиях искусственного интеллекта.
Ранее Наука Mail писала о том, что российские математики решили 50-летнюю задачу.
