Все эти проблемы объединяет то, что все они представляют собой "последовательные процессы принятия решений". В последовательном процессе принятия решений есть что-то, что нужно максимизировать: прием пациентов, производство товаров, получение денег, отправка заказов. И для этого можно предпринять различные шаги. Задача состоит в том, чтобы определить, какой набор шагов следует предпринять. Как достичь максимума? Как лучше всего подняться на гору?
Не имея особых наработок в этой области, Беллман обратился к проверенной стратегии в математике: он формализовал интуицию.2 Математический вывод, к которому он пришел, теперь известен как уравнение Беллмана, а простая интуиция, которую оно отражает, заключается в том, что лучший план действий - это тот, в котором все шаги являются наилучшими из возможных. Как бы очевидно это ни казалось, но, будучи сформулированным в математике, даже банальные утверждения могут иметь силу.
Чтобы понять, как Беллман использовал эту интуицию, нам нужно понять, как он сформулировал проблему. Сначала Беллман решил определить, насколько хорош тот или иной план, с точки зрения того, какое вознаграждение - деньги, виджеты, поставки и т. д. - он, скорее всего, принесет. Допустим, у вас есть план из пяти шагов. Общее вознаграждение - это сумма вознаграждений, которые вы получаете на каждом из этих пяти шагов. Но после того как вы сделали первый шаг, у вас теперь есть план из четырех шагов. Поэтому можно сказать, что общее вознаграждение по первоначальному пятишаговому плану - это вознаграждение, полученное за первый шаг, плюс общее вознаграждение по четырехшаговому плану. А общая награда от четырехшагового плана - это награда от первого шага плюс награда от результирующего трехшагового плана. И так далее, и так далее.
Определяя вознаграждение одного плана в терминах вознаграждения другого, Беллман сделал свое определение рекурсивным. Рекурсивный процесс - это процесс, который содержит сам себя. Рассмотрим, например, алфавитную систему. Если вы хотите составить список имен в алфавитном порядке, то начните с сортировки всех имен по первой букве. После этого вам нужно будет снова применить тот же процесс сортировки ко всем именам, начинающимся на одну и ту же букву, чтобы отсортировать их по второй букве, и так далее. Таким образом, алфавитная система становится рекурсивной.
Рекурсия - распространенный прием в математике и информатике отчасти потому, что рекурсивные определения гибкие: их можно сделать длинными или короткими, как это необходимо. Например, формулу для расчета общего вознаграждения по плану можно с одинаковым успехом применить как к плану из пяти шагов, так и к плану из 500 шагов. Рекурсия - это еще и концептуально простой способ добиться чего-то потенциально сложного. Подобно поворотам винтовой лестницы, каждый шаг в рекурсивном определении знаком, но не идентичен, и нам нужно только следовать по ним один за другим до конца.
В формулировке Беллмана есть еще две идеи, которые помогли сделать его стратегию эффективной для применения в реальных проблемах. Первая заключается в том, что он включил в свою стратегию тот весьма убедительный факт, что вознаграждение, которое вы получаете немедленно, стоит больше, чем вознаграждение, которое вы получаете позже. Для этого он ввел в рекурсивное определение коэффициент дисконтирования. Таким образом, если в первоначальной формуле вознаграждение от пятишагового плана было равно вознаграждению от первого шага плюс полное вознаграждение от четырехшагового плана, то в уравнении с дисконтированием оно будет равно вознаграждению от первого шага плюс, возможно, 80 процентов от вознаграждения от четырехшагового плана. Дисконтирование - это способ соизмерять немедленное удовлетворение с отложенным; это "птица в руке стоит двух в кустах", кодифицированное в математике.
Второе понимание было более концептуальным и более радикальным. Это был переход от фокусировки на вознаграждениях к фокусировке на ценностях.
Чтобы понять эту подмену, давайте рассмотрим владельца малого бизнеса - очень малого бизнеса. Анжела - бродяга в нью-йоркском метро. Она знает, что может играть на своей электрической скрипке в течение 20 минут на определенных станциях метро, прежде чем ее прогонят власти, и тогда ей не разрешат вернуться. На разных станциях, однако, выплачиваются разные суммы. Туристические районы могут быть очень прибыльными, в то время как остановки для коренных ньюйоркцев приносят гораздо меньше пожертвований. Она выходит из своего дома на Гринпойнт-авеню в Бруклине и хочет оказаться рядом с домом подруги на Бликер-стрит. Какой путь ей выбрать, чтобы заработать больше всего денег по дороге к месту назначения?
До сих пор мы замечали, что, начав с одной позиции и сделав шаг по плану, мы оказываемся в обстоятельствах, в целом схожих с теми, с которых начинали, - только начинаем мы с другой позиции и имеем другой план. В последовательном принятии решений различные позиции, через которые мы можем пройти, называются состояниями, а шаги в плане часто называют действиями. В случае с Анжелой состояния - это различные станции метро , на которых она может оказаться. Каждый раз, когда Анжела совершает действие (например, переходит со станции А на станцию Б), она оказывается в новом состоянии (станция Б), которое одновременно приносит ей определенное вознаграждение (количество пожертвований, которые получает ее игра) и предоставляет ей новый набор возможных действий (другие станции, на которые можно перейти). Таким образом, состояния определяют, какие действия доступны (например, вы не можете сразу отправиться с Гринпойнт-авеню на Таймс-сквер), а действия определяют, какими будут следующие состояния.
Это взаимодействие - когда действия, предпринятые в рамках плана, влияют на то, какие действия будут доступны в будущем, - является частью того, что делает последовательные процессы принятия решений такими сложными. Что сделал Беллман, так это взял это созвездие состояний, действий и вознаграждений и перевернул его с ног на голову. Вместо того чтобы говорить о вознаграждении, ожидаемом от серии действий, он сосредоточился на ценности, которую имеет любое данное состояние.
Ценность, в разговорном смысле, - понятие туманное. Оно вызывает мысли о деньгах и стоимости, а также о более глубоких понятиях смысла и пользы, которые бывает трудно определить. Уравнение Беллмана, однако, дает точное определение ценности. Используя ту же рекурсивную структуру, которая была представлена ранее, Беллман определил ценность состояния как вознаграждение, которое вы получаете в этом состоянии, плюс дисконтированная стоимость следующего состояния. Заметьте, в этом определении нет явного понятия плана; ценность определяется другими ценностями.
Тем не менее, это уравнение опирается на знание следующего состояния. Без плана, в котором указано, какое действие будет предпринято, как мы узнаем, каким будет следующее состояние? Именно здесь в игру вступает первоначальная интуиция - идея о том, что лучший план складывается из лучших действий. Чтобы рассчитать стоимость в следующем состоянии, достаточно предположить, что будет предпринято наилучшее возможное действие. А наилучшее возможное действие - это то, которое ведет к состоянию с наибольшей ценностью! Если говорить языком ценности, то сам план исчезает.