Закрепи победу
Поиск оптимальных алгоритмов, которые подсказали бы нам, как укротить «многорукого бандита», оказался весьма сложной задачей. Как рассказывает Питер Уиттл, в ходе Второй мировой войны попытки решить данную задачу «настолько подорвали силы и умы союзников… что было выдвинуто предложение подкинуть Германии эту проблему как самый действенный способ интеллектуальной диверсии».
Первые шаги к решению были предприняты годы спустя после войны, когда колумбийский математик Герберт Роббинс продемонстрировал, что существует простая стратегия, которая хоть и не идеальна, но дает некоторые гарантии. Роббинс предметно рассмотрел тот случай, когда у нас ровно два игровых автомата, и предложил способ под названием «победил – закрепи результат, проиграл – переключись»: выберите наугад любой рычаг и дергайте его до тех пор, пока автомат выдает деньги. Если после определенного рывка автомат не выдал выигрыш, стоит перейти к другому автомату. И хотя эта простая стратегия далека от оптимального решения, Роббинс в 1952 году доказал, что работает она куда лучше случайности.
Вслед за Роббинсом некоторые исследователи дальше занялись изучением принципа «оставайся победителем». Ясно, что если вы и так собирались дернуть за рычаг именно этого автомата, а он вдруг еще и выдал вам выигрыш, это немедленно увеличит его ценность в ваших глазах и вам будет хотеться и дальше дергать рычаг. И действительно, данный принцип оказывается элементом оптимальной стратегии балансирования между исследованием и использованием в широком диапазоне условий.
А вот «проиграл – переключись» – это уже совсем другая история. Менять рычаг каждый раз, как проиграешь, – довольно опрометчивый шаг. Допустим, вы посетили некий ресторан сто раз и всегда оставались довольны вкусной едой. Неужели одного-единственного разочарования будет достаточно, чтобы вы перестали туда ходить? Хорошие варианты не должны слишком строго караться за возможные несовершенства.
Что важно, принцип «победил – закрепи результат, проиграл – переключись» не имеет никакого отношения к промежутку времени, который вы пытаетесь оптимизировать. Если ваш любимый ресторан разочаровал вас в последнее посещение, данный алгоритм гласит, что вы должны отправиться на ужин в другое место – даже если это ваша последняя ночь в городе.
Таким образом, работа Роббинса о проблеме многорукого бандита дала старт появлению значительного количества прочей литературы на эту тему, и за последние годы исследователи добились существенного прогресса. Ричард Беллман, математик из корпорации РЭНД (RAND), нашел верное решение для случаев, когда мы заранее точно знаем, сколько всего шансов и возможностей у нас будет. Как и в ситуации с полной информацией в проблеме секретаря, трюк Беллмана заключался в том, чтобы на самом деле действовать от обратного, представив вначале последний рывок и предположив, какой из автоматов выбрать, учитывая все возможные результаты предыдущих решений. Выяснив это, уже можно переходить к предпоследнему варианту, потом к третьему с конца и т. д. до исходной точки старта.
Выводы, проистекающие из метода Беллмана, неоспоримы, но при большом количестве вариантов и длительном визите в казино он потребует головокружительного – или попросту невозможного – объема работы. Более того, даже если нам удастся просчитать все возможные расклады, мы все равно не будем знать точно, сколько возможностей (или хотя бы сколько способов) нам будет дано. По этим причинам проблема многорукого бандита так и остается нерешенной. По словам Уиттла, «она быстро стала классикой и синонимом неуступчивости».
Индекс Гиттинса
Как обычно бывает в математике, частное – это путь к общему. В 1970-х годах корпорация Unilever попросила молодого математика Джона Гиттинса помочь им оптимизировать некоторые клинические испытания их препаратов. И неожиданно получилось, что вместе с этим Гиттинс нашел ключ к математической загадке, которая оставалась нерешенной целым поколением.
Гиттинс, сегодня – профессор статистики в Оксфорде, размышлял над задачей, поставленной Unilever. При наличии нескольких химических соединений как быстрее всего определить, какое из них будет наиболее эффективным в борьбе с болезнью? Гиттинс попытался решить эту задачу наиболее общим способом: множественные варианты следования, разная вероятность вознаграждения за каждый из них и определенное количество усилий (или денег, или времени), которые будут между этими вариантами распределены. Это было, по сути, иное воплощение проблемы многорукого бандита.
И некоммерческие фармацевтические компании, и медицинские работники постоянно сталкиваются с противоречивыми требованиями соотношения «исследовать/эксплуатировать». Компании хотят вкладывать средства, выделяемые на научно-исследовательскую работу, в открытие новых лекарств, но в то же время желают быть уверены, что их уже существующие прибыльные производственные линии процветают. Доктора же хотят выписывать лучшие из существующих лекарств, чтобы их пациенты получали соответствующее лечение, но также хотят стимулировать экспериментальные разработки с тем, чтобы были созданы препараты, которые будут еще лучше.
В обоих случаях, кстати, не совсем ясно, каким должен быть релевантный промежуток. В некотором смысле и фармацевтические компании, и врачи заинтересованы в неопределенном будущем. Компании теоретически хотят присутствовать на рынке всегда, и прорыв в медицине может в будущем помочь людям, которые еще даже не родились! Но при этом у настоящего приоритет выше: вылеченный сегодня пациент гораздо более ценен, чем вылеченный через неделю или через год, и то же самое можно сказать и о прибылях. Экономисты называют «дисконтированием» эту идею ценить настоящее выше, чем будущее.
В отличие от своих предшественников, Гиттинс подошел к проблеме многорукого бандита с этой точки зрения. Он поставил своей целью максимизацию прибылей не в течение ограниченного временного интервала, а в бесконечном необозримом будущем, хотя и дисконтированном.
С этим дисконтированием мы не раз сталкивались в жизни. В конце концов, если вы приезжаете в город на 10 дней, вы будете принимать решение о выборе ресторана, держа в уме именно этот временной промежуток; но если вы живете здесь постоянно, то это теряет смысл. Вместо этого вы можете представить себе ценность выгод, уменьшающихся в будущем: вас больше заботит, что съесть на ужин сегодня, а не что будет на ужин завтра, а завтрашний ужин – больше, чем тот, что состоится через год, особенно в зависимости от лично вашей «дисконтной функции». Гиттинс в свою очередь предположил, что ценность, приписываемая выгодам, уменьшается в геометрической прогрессии: каждый ваш визит в ресторан стоит некой относительной доли вашего предыдущего визита. Если, к примеру, вы допускаете, что ваш шанс в любой день быть сбитым автобусом равен 1 %, то вам нужно оценить ваш завтрашний ужин на 99 % от ценности сегодняшнего, потому что есть вероятность его не съесть.
В работе над этим предположением о дисконтировании в геометрической прогрессии Гиттинс изучал стратегию, которая, как он думал, «была бы по меньшей мере хорошим приближением»: думать о каждой «руке» многорукого бандита по отдельности и попытаться вычислить ее самостоятельную ценность. Объяснял он это на весьма забавном примере – на взятках.
