C тех пор как был разработан индекс Гиттинса, этот подход заставил ученых-компьютерщиков и статистиков искать более простые и гибкие стратегии обращения с многорукими бандитами. Эти стратегии более удобны людям (и автоматам) для применения в различных ситуациях, чем напряженные подсчеты индекса Гиттинса, и при этом они обеспечивают сравнительно хорошие показатели работы. Кроме того, они борются с одним из главных человеческих страхов относительно принятия решений о том, какой шанс нельзя упустить.

Если индекс Гиттинса слишком сложен или ситуация, в которой вы оказались, не располагает к геометрическому дисконтированию, у вас есть еще один вариант: сосредоточиться на сожалении. Когда мы выбираем, что съесть на ужин, с кем провести время или в каком городе жить, на горизонте появляются сожаления: имея набор отличных вариантов, легко замучить себя мыслями о последствиях неправильного выбора. Обычно мы сожалеем о том, что нам не удалось сделать, о возможностях, которые мы упустили. Как гласит памятная фраза бизнес-теоретика Честера Барнарда, «пробовать и ошибаться – значит хотя бы учиться; ошибиться, не попробовав, – значит пережить невосполнимую потерю того, что могло бы быть».

Сожаление, впрочем, может стать отличной мотивацией. Прежде чем создать Amazon.com, Джефф Безос занимал спокойную и хорошо оплачиваемую должность в инвестиционной компании D. E. Shaw & Co в Нью-Йорке. Запуск книжного онлайн-магазина должен был стать большим скачком – именно тем, что его босс (тот самый D. E. Shaw) советовал Джеффу тщательно обдумать. Безос рассказывает:

Информатика не обеспечит вам жизнь, целиком лишенную сожалений. Однако она может предложить то, чего так добивался Безос: жизнь с минимумом сожалений.

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

В 1985 году Герберт Роббинс предпринял вторую попытку решения проблемы многорукого бандита, спустя 30 лет после его первой работы по «победил – закрепи успех, проиграл – переключись». Ему и его коллеге из Колумбийского университета математику Цзе Люн Лаю удалось доказать несколько ключевых моментов, касающихся сожалений. Во-первых, предполагая, что вы не всезнайка, можно сказать, что число ваших сожалений никогда не перестанет расти, даже если вы будете выбирать наилучшую стратегию действий. Потому что даже наилучшая стратегия не может быть каждый раз совершенной. Во-вторых, сожаление будет расти меньшими темпами, если вы будете предпочитать лучшую стратегию всем прочим; более того, с хорошей стратегией уровень сожаления будет падать по мере более глубокого изучения проблемы и выбора лучших решений. В-третьих и в-главных, минимально возможное количество сожалений – снова не допуская всеведения – это сожаление, которое растет логарифмически выверенно с каждым рывком рычага.

Логарифмически растущее сожаление означает, что мы совершим столько же ошибок за первые десять рывков, сколько мы совершим за последующие девяносто, и столько же ошибок за первый год, сколько за оставшиеся девять из декады. (Количество ошибок в первой декаде, в свою очередь, совпадет с количеством ошибок за последующие 90 лет.) Это в какой-то мере утешает. В целом мы не можем ожидать, что в один прекрасный день сожаления вовсе исчезнут. Но если следовать алгоритму минимизации сожалений, то с каждым годом мы можем ожидать меньше сожалений, чем в предыдущем году.

После Лая и Роббинса исследователи последние десятилетия искали алгоритмы, которые могли бы гарантировать минимальное количество сожалений. Из всех обнаруженных самый популярный получил название алгоритма верхнего доверительного предела.

Иллюстрированные статистические показания часто включают в себя так называемые планки погрешностей, которые идут вверх и вниз от любой точки графика, указывая на погрешность измерений; планки погрешностей показывают диапазон вероятных значений, которых измеряемая величина может достигать. Этот диапазон также известен как доверительный интервал, и чем больше информации мы соберем о чем-либо, тем сильнее будет сокращаться доверительный интервал, отражая все более точную оценку. (Например, игровой автомат, выдавший выигрыш один раз из двух, будет иметь более широкий доверительный интервал, хотя и такую же ожидаемую выгоду, как и тот, который выдал выигрыш 5 раз из 10.) Согласно алгоритму верхнего доверительного предела, в задаче с многоруким бандитом достаточно выбрать тот автомат, у которого верхняя точка доверительного интервала будет самой высокой.

Как и индекс Гиттинса, алгоритм верхнего доверительного предела определяет единое число для каждого рычага многорукого бандита. И это число устанавливается равным наибольшему значению, которого автомат мог бы объективно достичь, основываясь на доступной нам до сих пор информации. Таким образом, алгоритм верхнего доверительного предела не учитывает, какой из автоматов был доселе лучшим; вместо этого он выбирает автомат, который объективно мог бы стать лучшим в будущем. Если вы, к примеру, никогда не были в некоем ресторане, он может оказаться гораздо лучше всех тех, что вы знаете. И даже если вы бывали в нем раз-другой и пробовали пару предлагаемых в нем блюд, вы все равно не будете достаточно информированы, чтобы исключить вероятность того, что он может оказаться лучше вашего любимого местечка. Так же, как и индекс Гиттинса, верхний доверительный предел всегда больше ожидаемой выгоды, но становится меньше и меньше по мере того, как мы накапливаем опыт работы с выбранным объектом. (Ресторан, получивший одну-единственную посредственную оценку, по-прежнему сохраняет потенциал превосходства, в отличие от ресторана, получившего сотни таких оценок.) Рекомендации, которые дает алгоритм верхнего доверительного предела, будут такими же, как и у индекса Гиттинса, но их значительно легче выработать, и они не требуют предположения о геометрическом дисконтировании.