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

А Уравнение беллмана, названный в честь Ричард Э. Беллман, это необходимое условие для оптимальности, связанной с математическим оптимизация метод, известный как динамическое программирование.^[1] Он записывает «ценность» проблемы решения в определенный момент времени в терминах выигрыша от некоторых начальных выборов и «ценности» оставшейся проблемы решения, которая является результатом этих первоначальных выборов.^{[нужна цитата ]} Это разбивает задачу динамической оптимизации на последовательность из более простых подзадач, как «Принцип оптимальности» Беллмана предписывает.^[2]

Уравнение Беллмана впервые было применено в технике. теория управления и другим темам прикладной математики, и впоследствии стал важным инструментом в экономическая теория; хотя основные концепции динамического программирования предустановлены в Джон фон Нейман и Оскар Моргенштерн с Теория игр и экономического поведения и Авраам Вальд с последовательный анализ.^{[нужна цитата ]}

Практически любая проблема, которую можно решить с помощью теория оптимального управления также может быть решена путем анализа соответствующего уравнения Беллмана.^{[Почему? ]}^{[требуется дальнейшее объяснение ]} Однако термин «уравнение Беллмана» обычно относится к уравнению динамического программирования, связанному с дискретное время проблемы оптимизации.^[3] В задачах оптимизации с непрерывным временем аналогичным уравнением является уравнение в частных производных это называется Уравнение Гамильтона – Якоби – Беллмана..^[4]^[5]

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

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

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

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

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

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

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

Вывод

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

Пусть государство на время ${ displaystyle t}$ быть ${ displaystyle x_ {t}}$ . Для решения, которое начинается в момент времени 0, мы принимаем начальное состояние ${ 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.)^[6]^[7]^[8]

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

Как было предложено принцип оптимальности, мы рассмотрим первое решение отдельно, отложив в сторону все будущие решения (мы начнем заново с момента 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}).}

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

Пока что кажется, что мы только усугубили проблему, отделив сегодняшнее решение от будущих решений. Но мы можем упростить, заметив, что внутри квадратных скобок справа находится Значение времени 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)) }.}

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

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

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

В качестве конкретного примера из экономики рассмотрим бесконечно живущего потребителя с начальным богатством. ${ 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 + г) (а-с)) },}

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

Теперь, если процентная ставка меняется от периода к периоду, потребитель сталкивается с проблемой стохастической оптимизации. Пусть интерес р следовать Марковский процесс с вероятностной переходной функцией ${ 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)}.}

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

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

При некотором разумном предположении результирующая оптимальная функция политики грамм(а,р) является измеримый.

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

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

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

В метод неопределенных коэффициентов, также известный как «угадай и проверь», можно использовать для решения некоторого бесконечного горизонта, автономный Уравнения Беллмана.^[9]
Уравнение Беллмана может быть решено с помощью обратная индукция, либо аналитически в некоторых особых случаях или численно на компьютере. Числовая обратная индукция применима к широкому кругу задач, но может оказаться невыполнимой, когда есть много переменных состояния из-за проклятие размерности. Приближенное динамическое программирование было введено Д. П. Бертсекас и Я. Н. Цициклис с использованием искусственные нейронные сети (многослойные персептроны ) для аппроксимации функции Беллмана.^[10] Это эффективная стратегия смягчения последствий для уменьшения влияния размерности за счет замены запоминания полного отображения функций для всего пространственного домена запоминанием отдельных параметров нейронной сети. В частности, для систем с непрерывным временем был представлен приближенный подход динамического программирования, сочетающий обе итерации политики с нейронными сетями.^[11] В дискретном времени был представлен подход к решению уравнения HJB, объединяющий итерации значений и нейронные сети.^[12]
Вычислив условия первого порядка, связанные с уравнением Беллмана, а затем используя теорема о конверте чтобы исключить производные функции цены, можно получить систему разностные уравнения или же дифференциальные уравнения называется 'Уравнения Эйлера '.^[13] Стандартные методы решения разностных или дифференциальных уравнений затем могут использоваться для расчета динамики переменных состояния и управляющих переменных задачи оптимизации.

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

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

Известное экономическое приложение уравнения Беллмана: Роберт С. Мертон основополагающая статья 1973 г. модель межвременного ценообразования капитальных активов.^[15] (Смотрите также Проблема портфеля Мертона Решение теоретической модели Мертона, в которой инвесторы выбирают между доходом сегодня и будущим доходом или приростом капитала, является формой уравнения Беллмана. Поскольку экономические приложения динамического программирования обычно приводят к уравнению Беллмана, которое является разностное уравнение, экономисты называют динамическое программирование "рекурсивным методом" и подполе рекурсивная экономика теперь признано в экономической науке.

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

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

Пример

В Марковские процессы принятия решений, уравнение Беллмана - это рекурсия за ожидаемые награды. Например, ожидаемая награда за нахождение в определенном состоянии. 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 *}}$ относится к функции ценности оптимальной политики. Приведенное выше уравнение описывает вознаграждение за действие, дающее наивысший ожидаемый доход.

Уравнение Беллмана - Википедия - Bellman equation

Содержание

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

Вывод

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

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