Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс Страница 14

Общие принципы, которые я открыл и которые сделали решение предельно простым, я назвал – как назвал бы только «ботаник» – принципами минимизации сожалений. Я представил себя в возрасте 80 лет и сказал: «О'кей, вот я оглядываюсь на прожитую мною жизнь. Хотел бы я свести к минимуму те сожаления, которые мне пришлось испытать!» Я знал, что, когда мне стукнет 80, я точно не пожалею о том, что попробовал сделать это. Я не пожалею о том, что ввязался в то, что называется интернетом, и я знал, что это будет великая вещь. Я знал, что в случае неудачи я не буду сожалеть об этом, но я всегда буду сожалеть о том, что даже не попытался. Я знал, что это будет преследовать меня каждый день, поэтому, когда я взглянул на все с этой точки зрения, принять решение оказалось весьма легко.

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

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

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

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

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

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

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