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