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

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

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

А вот «проиграл – переключись» – это уже совсем другая история. Менять рычаг каждый раз, как проиграешь, – довольно опрометчивый шаг. Допустим, вы посетили некий ресторан сто раз и всегда оставались довольны вкусной едой. Неужели одного-единственного разочарования будет достаточно, чтобы вы перестали туда ходить? Хорошие варианты не должны слишком строго караться за возможные несовершенства.

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

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

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