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