Уравнение Беллмана - Bellman equation

Уравнение Беллмана , названное в честь Беллмана , является необходимым условием оптимальности , связанной с математической оптимизацией методой , известной как динамическое программирование . Он записывает «ценность» проблемы решения в определенный момент времени в терминах выигрыша от некоторых начальных выборов и «ценности» оставшейся проблемы решения, которая является результатом этих первоначальных выборов. Это разбивает задачу динамической оптимизации на последовательность более простых подзадач, как предписывает «принцип оптимальности» Беллмана.

Уравнение Беллмана впервые было применено к инженерной теории управления и к другим темам прикладной математики, а впоследствии стало важным инструментом экономической теории ; хотя основные концепции динамического программирования прообразом в Джона фон Неймана и Оскара Моргенштерна «s Теория игр и экономическое поведение и Abraham Wald » s последовательного анализа . Термин «уравнение Беллмана» обычно относится к уравнениям динамического программирования, связанным с задачами оптимизации с дискретным временем . В задачах оптимизации с непрерывным временем аналогичное уравнение является уравнением в частных производных , которое называется уравнениемУравнение Гамильтона – Якоби – Беллмана .

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

Аналитические концепции в динамическом программировании

Чтобы понять уравнение Беллмана, необходимо понять несколько основных концепций. Во-первых, любая задача оптимизации имеет некоторую цель: минимизировать время в пути, минимизировать затраты, максимизировать прибыль, максимизировать полезность и т. Д. Математическая функция, описывающая эту цель, называется целевой функцией .

Динамическое программирование разбивает задачу многопериодного планирования на более простые шаги в разные моменты времени. Следовательно, это требует отслеживания того, как ситуация принятия решений меняется с течением времени. Информация о текущей ситуации, необходимая для принятия правильного решения, называется «состоянием». Например, чтобы решить, сколько потреблять и тратить в каждый момент времени, людям необходимо знать (среди прочего) свое первоначальное богатство. Следовательно, богатство будет одной из переменных их состояния , но, вероятно, будут и другие. ${\ Displaystyle (W)}$

Переменные, выбранные в любой данный момент времени, часто называют контрольными переменными . Например, с учетом своего текущего благосостояния люди могут решить, сколько потреблять сейчас. Выбор управляющих переменных сейчас может быть эквивалентен выбору следующего состояния; в более общем случае, на следующее состояние влияют другие факторы в дополнение к текущему элементу управления. Например, в простейшем случае сегодняшнее богатство (состояние) и потребление (контроль) могут точно определять завтрашнее богатство (новое состояние), хотя обычно другие факторы также будут влиять на завтрашнее богатство.

Подход динамического программирования описывает оптимальный план путем нахождения правила, которое сообщает, какими должны быть элементы управления при любом возможном значении состояния. Например, если потребление ( c ) зависит только от богатства ( W ), мы будем искать правило, которое определяет потребление как функцию богатства. Такое правило, определяющее элементы управления как функцию состояний, называется функцией политики (см. Bellman, 1957, Ch. III.2). ${\ displaystyle c (W)}$

Наконец, по определению, оптимальное правило принятия решений - это правило, которое позволяет достичь наилучшего возможного значения цели. Например, если кто-то выбирает потребление, учитывая богатство, чтобы максимизировать счастье (предполагая, что счастье H может быть представлено математической функцией, такой как функция полезности, и является чем-то определенным богатством), то каждый уровень богатства будет связан с какой-то наивысший возможный уровень счастья . Наилучшее возможное значение цели, записанное как функция состояния, называется функцией значения . ${\ displaystyle H (W)}$

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

Вывод

Проблема динамического решения

Пусть состояние на время будет . Для решения, которое начинается в момент времени 0, мы принимаем начальное состояние заданным . В любой момент набор возможных действий зависит от текущего состояния; мы можем записать это как , где действие представляет одну или несколько управляющих переменных. Мы также предполагаем, что состояние изменяется с на новое состояние, когда выполняется действие , и что текущий выигрыш от выполнения действия в состоянии равен . Наконец, мы предполагаем нетерпение, представленное дисконтным фактором . ${\ displaystyle t}$${\ displaystyle x_ {t}}$${\ displaystyle x_ {0}}$${\ displaystyle a_ {t} \ in \ Gamma (x_ {t})}$${\ displaystyle a_ {t}}$${\ displaystyle x}$${\ Displaystyle Т (х, а)}$${\ displaystyle a}$${\ displaystyle a}$${\ displaystyle x}$${\ Displaystyle F (х, а)}$ ${\ displaystyle 0 <\ beta <1}$

При этих предположениях проблема принятия решений с бесконечным горизонтом принимает следующий вид:

${\ Displaystyle V (x_ {0}) \; = \; \ max _ {\ left \ {a_ {t} \ right \} _ {t = 0} ^ {\ infty}} \ sum _ {t = 0 } ^ {\ infty} \ beta ^ {t} F (x_ {t}, a_ {t}),}$

с учетом ограничений

${\ Displaystyle a_ {t} \ in \ Gamma (x_ {t}), \; x_ {t + 1} = T (x_ {t}, a_ {t}), \; \ forall t = 0,1, 2, \ точки}$

Обратите внимание, что мы определили обозначение для обозначения оптимального значения, которое может быть получено путем максимизации этой целевой функции с учетом предполагаемых ограничений. Эта функция является функцией значения . Это функция переменной начального состояния , поскольку наилучшее достижимое значение зависит от начальной ситуации. ${\ Displaystyle V (x_ {0})}$${\ displaystyle x_ {0}}$

Принцип оптимальности Беллмана

Метод динамического программирования разбивает эту проблему решения на более мелкие подзадачи. Принцип оптимальности Беллмана описывает, как это сделать:

Принцип оптимальности: Оптимальная политика обладает тем свойством, что независимо от начального состояния и первоначального решения, остальные решения должны составлять оптимальную политику в отношении состояния, вытекающего из первого решения. (См. Bellman, 1957, гл. III.3.)

В информатике считается, что проблема, которую можно разбить на части, имеет оптимальную подструктуру . В контексте теории динамических игр этот принцип аналогичен концепции идеального равновесия в подиграх , хотя то, что составляет оптимальную политику в этом случае, зависит от того, что оппоненты лица, принимающего решения, выбирают одинаково оптимальную политику со своей точки зрения.

Согласно принципу оптимальности , мы рассмотрим первое решение отдельно, отложив в сторону все будущие решения (мы начнем заново с момента 1 с новым состоянием ). Собирая будущие решения в скобки справа, вышеупомянутая проблема принятия решений с бесконечным горизонтом эквивалентна: ${\ displaystyle x_ {1}}$

${\ displaystyle \ max _ {a_ {0}} \ left \ {F (x_ {0}, a_ {0}) + \ beta \ left [\ max _ {\ left \ {a_ {t} \ right \} _ {t = 1} ^ {\ infty}} \ sum _ {t = 1} ^ {\ infty} \ beta ^ {t-1} F (x_ {t}, a_ {t}): a_ {t} \ in \ Gamma (x_ {t}), \; x_ {t + 1} = T (x_ {t}, a_ {t}), \; \ forall t \ geq 1 \ right] \ right \}}$

с учетом ограничений

${\ displaystyle a_ {0} \ in \ Gamma (x_ {0}), \; x_ {1} = T (x_ {0}, a_ {0}).}$

Здесь мы выбираем , зная, что в результате нашего выбора будет состояние time 1 . Это новое состояние затем повлияет на проблему принятия решения с момента 1. Вся проблема будущего решения отображается в квадратных скобках справа. ${\ displaystyle a_ {0}}$${\ displaystyle x_ {1} = T (x_ {0}, a_ {0})}$

Уравнение Беллмана

Пока что кажется, что мы только усугубили проблему, отделив сегодняшнее решение от будущих решений. Но мы можем упростить, заметив, что то, что находится внутри квадратных скобок справа, - это значение задачи принятия решения за время 1, начиная с состояния . ${\ displaystyle x_ {1} = T (x_ {0}, a_ {0})}$

Следовательно, мы можем переписать задачу как рекурсивное определение функции значения:

${\ Displaystyle V (x_ {0}) = \ max _ {a_ {0}} \ {F (x_ {0}, a_ {0}) + \ beta V (x_ {1}) \}}$, с учетом ограничений: ${\ displaystyle a_ {0} \ in \ Gamma (x_ {0}), \; x_ {1} = T (x_ {0}, a_ {0}).}$

Это уравнение Беллмана. Его можно упростить еще больше, если мы отбросим временные индексы и подставим значение следующего состояния:

${\ Displaystyle V (x) = \ max _ {a \ in \ Gamma (x)} \ {F (x, a) + \ beta V (T (x, a)) \}.}$

Уравнение Беллмана классифицируется как функциональное уравнение , поскольку его решение означает нахождение неизвестной функции , которая является функцией цены . Напомним, что функция ценности описывает наилучшее возможное значение цели как функцию состояния . Вычисляя функцию ценности, мы также найдем функцию, которая описывает оптимальное действие как функцию состояния; это называется функцией политики . ${\ displaystyle V}$${\ displaystyle x}$${\ Displaystyle а (х)}$

В стохастической задаче

В детерминированной установке для решения указанной выше проблемы оптимального управления могут быть использованы другие методы, помимо динамического программирования . Однако уравнение Беллмана часто является наиболее удобным методом решения задач стохастического оптимального управления.

В качестве конкретного примера из экономики рассмотрим бесконечно живущего потребителя с начальным запасом благосостояния в определенный период . У них есть функция мгновенной полезности, где обозначает потребление и скидку на полезность следующего периода по ставке . Предположим, что то, что не потреблено в периоде, переносится на следующий период с процентной ставкой . Тогда задача максимизации полезности потребителя состоит в том, чтобы выбрать план потребления, который решает ${\ displaystyle {\ color {красный} a_ {0}}}$${\ displaystyle 0}$ ${\ Displaystyle и (с)}$${\ displaystyle c}$${\ displaystyle 0 <\ beta <1}$${\ displaystyle t}$${\ displaystyle r}$${\ displaystyle \ {{\ color {OliveGreen} c_ {t}} \}}$

${\ displaystyle \ max \ sum _ {t = 0} ^ {\ infty} \ beta ^ {t} u ({\ color {OliveGreen} c_ {t}})}$

при условии

${\ displaystyle {\ color {Red} a_ {t + 1}} = (1 + r) ({\ color {Red} a_ {t}} - {\ color {OliveGreen} c_ {t}}), \; {\ color {OliveGreen} c_ {t}} \ geq 0,}$

а также

${\ displaystyle \ lim _ {t \ rightarrow \ infty} {\ color {Red} a_ {t}} \ geq 0.}$

Первое ограничение - это закон накопления капитала / движения, определяемый проблемой, в то время как второе ограничение - это условие трансверсальности , при котором потребитель не несет долгов в конце своей жизни. Уравнение Беллмана имеет вид

${\ Displaystyle В (а) = \ макс _ {0 \ Leq с \ Leq а} \ {и (с) + \ бета V ((1 + г) (ас)) \},}$

В качестве альтернативы можно решить проблему последовательности напрямую, используя, например, гамильтоновы уравнения .

Теперь, если процентная ставка меняется от периода к периоду, потребитель сталкивается с проблемой стохастической оптимизации. Пусть процентная ставка r следует марковскому процессу с функцией перехода вероятности, где обозначает вероятностную меру, управляющую распределением процентной ставки в следующем периоде, если текущая процентная ставка равна . В этой модели потребитель принимает решение о потреблении в текущий период после объявления процентной ставки текущего периода. ${\ Displaystyle Q (г, д \ му _ {г})}$${\ displaystyle d \ mu _ {r}}$${\ displaystyle r}$

Вместо того, чтобы просто выбирать одну последовательность , потребитель теперь должен выбрать последовательность для каждой возможной реализации так, чтобы их ожидаемая полезность в течение всего срока службы была максимальной: ${\ displaystyle \ {{\ color {OliveGreen} c_ {t}} \}}$${\ displaystyle \ {{\ color {OliveGreen} c_ {t}} \}}$${\ displaystyle \ {r_ {t} \}}$

${\ displaystyle \ max _ {\ left \ {c_ {t} \ right \} _ {t = 0} ^ {\ infty}} \ mathbb {E} {\ bigg (} \ sum _ {t = 0} ^ {\ infty} \ beta ^ {t} u ({\ color {OliveGreen} c_ {t}}) {\ bigg)}.}$

Математическое ожидание берется относительно соответствующей вероятностной меры, заданной Q на последовательностях r . Поскольку r управляется марковским процессом, динамическое программирование значительно упрощает задачу. Тогда уравнение Беллмана просто: ${\ displaystyle \ mathbb {E}}$

${\ Displaystyle V (a, r) ​​= \ max _ {0 \ leq c \ leq a} \ {u (c) + \ beta \ int V ((1 + r) (ac), r ') Q (r , d \ mu _ {r}) \}.}$

При некотором разумном предположении результирующая функция оптимальной политики g ( a , r ) измерима .

Для общей стохастической последовательной задачи оптимизации с марковскими шоками и где агент сталкивается с их решением экс-постом , то уравнение Беллмана имеет очень сходную форму

${\ Displaystyle V (Икс, Z) = \ max _ {с \ in \ Gamma (x, z)} \ {F (x, c, z) + \ бета \ int V (T (x, c), z ') d \ mu _ {z} (z') \}.}$

Методы решения

• Метод неопределенных коэффициентов , также известные как «угадать и проверяйте», может быть использован для решения какого - то бесконечный горизонта, автономные уравнения Беллмана.
• Уравнение Беллмана может быть решено обратной индукцией либо аналитически в некоторых частных случаях, либо численно на компьютере. Числовая обратная индукция применима к широкому кругу задач, но может оказаться невыполнимой при большом количестве переменных состояния из-за проклятия размерности . Приближенное динамическое программирование было введено Д. П. Бертсекасом и Ю. Н. Цициклисом с использованием искусственных нейронных сетей ( многослойных персептронов ) для аппроксимации функции Беллмана. Это эффективная стратегия смягчения последствий для уменьшения влияния размерности путем замены запоминания полного отображения функций для всего пространственного домена запоминанием единственных параметров нейронной сети. В частности, для систем с непрерывным временем был представлен приближенный подход динамического программирования, сочетающий обе итерации политики с нейронными сетями. В дискретном времени был представлен подход к решению уравнения HJB, объединяющий итерации значений и нейронные сети.
• Вычисляя условия первого порядка, связанные с уравнением Беллмана, а затем используя теорему об огибающей для исключения производных функции цены, можно получить систему разностных уравнений или дифференциальных уравнений, называемую « уравнениями Эйлера ». Стандартные методы решения разностных или дифференциальных уравнений затем можно использовать для расчета динамики переменных состояния и управляющих переменных задачи оптимизации.

Приложения в экономике

Первое известное применение уравнения Беллмана в экономике принадлежит Мартину Бекманну и Ричарду Муту . Мартин Бекманн также много писал о теории потребления с использованием уравнения Беллмана в 1959 году. Его работа, в частности, оказала влияние на Эдмунда С. Фелпса .

Знаменитым экономическим применением уравнения Беллмана является основополагающая статья Роберта К. Мертона 1973 года о модели межвременного ценообразования капитальных активов . (См. Также проблему портфеля Мертона. ) Решение теоретической модели Мертона, в которой инвесторы выбирают между доходом сегодня и будущим доходом или приростом капитала, является формой уравнения Беллмана. Поскольку экономические приложения динамического программирования обычно приводят к уравнению Беллмана, которое является уравнением разностей , экономисты называют динамическое программирование «рекурсивным методом», и в настоящее время в экономической науке признается подполе рекурсивной экономики.

Нэнси Стоки , Роберт Э. Лукас и Эдвард Прескотт довольно подробно описывают стохастическое и нестохастическое динамическое программирование и развивают теоремы о существовании решений проблем, удовлетворяющих определенным условиям. Они также описывают множество примеров моделирования теоретических проблем экономики с использованием рекурсивных методов. Эта книга привела к тому, что динамическое программирование использовалось для решения широкого круга теоретических проблем в экономике, включая оптимальный экономический рост , добычу ресурсов , проблемы принципала-агента , государственные финансы , инвестиции в бизнес , ценообразование на активы , предложение факторов производства и организацию производства . Ларс Юнгквист и Томас Сарджент применяют динамическое программирование для изучения множества теоретических вопросов денежно-кредитной политики , налоговой политики , налогообложения , экономического роста , теории поиска и экономики труда . Авинаш Диксит и Роберт Пиндик продемонстрировали ценность этого метода для анализа капитального бюджета . Андерсон адаптировал эту технику для оценки бизнеса, в том числе частного.

Использование динамического программирования для решения конкретных задач осложняется информационными трудностями, такими как выбор ненаблюдаемой ставки дисконтирования. Существуют также вычислительные проблемы, главная из которых - проклятие размерности, возникающее из-за огромного количества возможных действий и потенциальных переменных состояния, которые необходимо учитывать, прежде чем можно будет выбрать оптимальную стратегию. Подробное обсуждение вычислительных вопросов см. В Miranda, Fackler и Meyn 2007.

Пример

В марковских процессах принятия решений уравнение Беллмана представляет собой рекурсию для ожидаемых вознаграждений. Например, ожидаемое вознаграждение за нахождение в определенном состоянии s и следование некоторой фиксированной политике имеет уравнение Беллмана: ${\ displaystyle \ pi}$

${\ Displaystyle V ^ {\ pi} (s) = R (s, \ pi (s)) + \ gamma \ sum _ {s '} P (s' | s, \ pi (s)) V ^ {\ пи} (s '). \}$

Это уравнение описывает ожидаемое вознаграждение за действие, предписанное некоторой политикой . ${\ displaystyle \ pi}$

Уравнение оптимальной политики называется уравнением оптимальности Беллмана :

${\ Displaystyle V ^ {\ pi *} (s) = \ max _ {a} \ {{R (s, a) + \ gamma \ sum _ {s '} P (s' | s, a) V ^ {\ pi *} (s ')} \}. \}$

где - оптимальная политика и относится к функции ценности оптимальной политики. Приведенное выше уравнение описывает вознаграждение за действие, дающее наивысший ожидаемый доход. ${\ displaystyle {\ pi *}}$${\ Displaystyle V ^ {\ pi *}}$

Смотрите также

• Псевдоспектральный метод Беллмана
• Динамическое программирование  - метод оптимизации задачи.
• Уравнение Гамильтона – Якоби – Беллмана.
• Марковский процесс принятия решений
• Теория оптимального управления
• Оптимальная подконструкция
• Рекурсивное конкурентное равновесие
• Стохастическое динамическое программирование

использованная литература