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