В НовГУ решили математическую «задачу о двуруком бандите»
09 октября 2025, 12:00 696
В Новгородском университете решили математическую «задачу о двуруком бандите» и внесли вклад в решение фундаментальной математической проблемы. Полученные результаты научного исследования можно применять в оптимизации пакетной обработки больших данных.
Суть проблемы решения «задачи о двуруком бандите» лежала в следующем. Двурукий бандит — это игральный автомат с двумя рукоятками. Нажатие на каждую рукоятку приносит игроку единичный случайный выигрыш. Например, с некоторыми вероятностями он может выиграть 1 рубль при нажатии на каждую рукоятку. Обе вероятности фиксированы, различны, но неизвестны игроку.
У задачи о двуруком бандите уже есть различные практические применения. Например, в интернете её алгоритмы используют для продвижения товаров, подстраиваясь под неизвестные предпочтения пользователей. Исследование, проведённое в Новгородском университете, направлено на оптимизацию так называемой пакетной обработки больших данных.
— Представим себе группу из 1000 пациентов, для лечения которых имеются 2 альтернативных лекарства, — объясняет на примере использования математического решения в Big Data автор проекта, Александр Колногоров, профессор кафедры прикладной математики и информатики, главный научный сотрудник Научно-исследовательского центра НовГУ. — Применение каждого лекарства к лечению пациента даёт с некоторой вероятностью единичный доход, если пациент поправился, и ничего, если продолжает болеть. Процесс лечения всех пациентов можно рассматривать как игру против двурукого бандита, а лекарства – как рукоятки, которые можно нажимать 1000 раз. Целью игры является максимизация среднего количества поправившихся пациентов. Проблема в том, что пациентов нельзя лечить по очереди, так как результат действия лекарства требует значительного времени. Кк примеру, если он проявится через неделю, то на лечение 1000 пациентов потребуется 1000 недель, или около 19 лет. Но можно поступить другим образом: сначала дать оба лекарства двум сравнительно небольшим группам, допустим, из 100 пациентов. Посчитать через неделю, в какой группе поправилось больше людей. И дать целительное лекарство остальным 800 людям. В итоге всё лечение займет 2 недели. Причём при правильном выборе размеров начальных групп эффективность такой пакетной обработки достаточно высока.
Задача о двуруком бандите – сравнительно новая математическая проблема. Она поставлена в середине XX века независимо друг от друга американским математиком Гербертом Роббинсом и советским кибернетиком Михаилом Львовичем Цетлиным. Открытия в этой области сегодня напрямую относятся к исследованиям в области искусственного интеллекта.
Полный текст на Газон Медиа
Материал подготовлен при поддержке гранта Минобрнауки России, в рамках Десятилетия науки и технологий
