Ученые НовГУ решили математическую «задачу о двуруком бандите» и внесли вклад в решение фундаментальной математической проблемы. Полученные результаты имеют широкий спектр практического применения в сферах, где необходима эффективная обработка больших объемов данных: от медицинской диагностики до современных информационных технологий.
Чем опасен «двурукий бандит»?
Задача была сформулирована в середине XX века двумя выдающимися учеными — американским математиком Гербертом Роббинсом и советским кибернетиком Михаилом Цетлиным. Это математическая модель, основанная на игровом автомате с двумя рукоятками. При нажатии на каждую из них игрок получает случайный выигрыш. Вероятности выигрыша для каждой рукоятки фиксированы, но неизвестны игроку. Основная цель — найти оптимальную стратегию для максимизации общего выигрыша.
Для решения задачи исследователи НовГУ использовали комплекс математических методов — динамическое программирование (разбиение сложных задач на простые) и дифференциальные уравнения в частных производных.
Как это работает?
Предположим, вероятность выигрыша на первой рукоятке составляет 0,7, а на второй — 0,5. Если игрок будет нажимать только первую рукоятку в течение 10 попыток, его средний выигрыш составит 7 единиц. При выборе второй рукоятки средний выигрыш будет равен 5 единицам. Необходимо определить более «выгодную», не зная этих вероятностей заранее.
Ученые приводят аналогию:
Представим группу из 1000 пациентов, для лечения которых имеются два альтернативных лекарства. Цель — максимизировать число выздоровевших. Пациентов нельзя лечить по очереди, так как результат действия требует значительного времени (если он проявится через неделю, то на лечение 1000 пациентов потребуется около 19 лет).
Исследователи НовГУ предложили новый подход, разделив всех пациентов на три группы:
- Группа №1 (100 человек) получает первое лекарство
- Группа №2 (100 человек) получает второе лекарство
- Группа №3 (800 человек) ожидает результатов
Через неделю после начала лечения врачи оценивают результаты в первых двух группах и подсчитывают количество выздоровевших пациентов. На основе этих данных определяется наиболее эффективное лекарство, его назначают оставшимся 800 пациентам. Таким образом, весь процесс лечения укладывается всего в две недели.
Александр Колногоров, автор проекта, профессор кафедры прикладной математики и информатики, главный научный сотрудник Научно-исследовательского центра НовГУ, отмечает, что при правильном выборе размеров начальных групп эффективность такой «пакетной» обработки оказывается достаточно высокой.
Сейчас ученые работают над решением более сложной версии задачи — «многорукого бандита», где рассматривается автомат с несколькими рукоятками. Это позволит применять полученные результаты к более широкому спектру реальных задач.
Исследование выполнено при поддержке Российского фонда фундаментальных исследований и Министерства науки и высшего образования РФ.
Исследование продолжает линию научных инициатив, развиваемых в рамках Десятилетия науки и технологий. Ключевым событием Десятилетия является Конгресс молодых ученых, на котором презентуются и обсуждаются результаты исследований. V Конгресс молодых ученых состоится в Научно-технологическом университете «Сириус» 26–28 ноября.