Стохастическое динамическое программирование - Stochastic dynamic programming

Первоначально представленный Ричард Э. Беллман в (Беллман 1957 ), стохастическое динамическое программирование это методика моделирования и решения проблем принятие решений в условиях неопределенности. Близко к стохастическое программирование и динамическое программирование, стохастическое динамическое программирование представляет исследуемую задачу в виде Уравнение беллмана. Цель состоит в том, чтобы вычислить политика предписывая, как действовать оптимально в условиях неопределенности.

Наглядный пример: азартная игра.

У игрока есть 2 доллара, ему разрешается сыграть в азартную игру 4 раза, и ее цель - максимизировать вероятность того, что она закончит с минимум 6 долларами. Если игрок ставит $${ displaystyle b}$ в ходе игры, то с вероятностью 0,4 она выигрывает игру, возвращает первоначальную ставку и увеличивает свою позицию капитала на $${ displaystyle b}$; с вероятностью 0,6 она проигрывает сумму ставки $${ displaystyle b}$; все пьесы попарно независимые. При любом ходе игры игрок не имеет права ставить больше денег, чем он имел в начале этой игры.^[1]

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

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

Оптимальная стратегия ставок, которая максимизирует вероятность игрока достичь состояния не менее 6 долларов к концу горизонта ставок; ${ Displaystyle B_ {т} ( $ х)}$ представляет собой сумму ставки на игру ${ displaystyle t}$ когда у игрока есть $${ displaystyle x}$ в начале пьесы. Если лицо, принимающее решения, будет следовать этой политике, с вероятностью 0,1984 он достигнет состояния не менее 6 долларов.

Формальный фон

Рассмотрим дискретную систему, заданную на ${ displaystyle n}$ этапы, в которых каждый этап ${ Displaystyle т = 1, ldots, п}$ характеризуется

• ан начальное состояние ${ displaystyle s_ {t} in S_ {t}}$, куда ${ displaystyle S_ {t}}$ набор возможных состояний в начале этапа ${ displaystyle t}$;
• а переменная решения ${ displaystyle x_ {t} in X_ {t}}$, куда ${ displaystyle X_ {t}}$ набор возможных действий на этапе ${ displaystyle t}$ - Обратите внимание, что ${ displaystyle X_ {t}}$ может быть функцией начального состояния ${ displaystyle s_ {t}}$;
• ан функция немедленных затрат / вознаграждения ${ displaystyle p_ {t} (s_ {t}, x_ {t})}$, представляющий стоимость / вознаграждение на этапе ${ displaystyle t}$ если ${ displaystyle s_ {t}}$ начальное состояние и ${ displaystyle x_ {t}}$ выбранное действие;
• а функция перехода между состояниями ${ displaystyle g_ {t} (s_ {t}, x_ {t})}$ что ведет систему к состоянию ${ Displaystyle s_ {t + 1} = g_ {t} (s_ {t}, x_ {t})}$.

Позволять ${ displaystyle f_ {t} (s_ {t})}$ представляют собой оптимальную стоимость / вознаграждение, полученное при соблюдении оптимальная политика по этапам ${ Displaystyle т, т + 1, ldots, п}$. Без потери общности в дальнейшем мы рассмотрим настройку максимизации вознаграждения. В детерминированном динамическое программирование обычно имеют дело с функциональные уравнения принимая следующую структуру

${ displaystyle f_ {t} (s_ {t}) = max _ {x_ {t} in X_ {t}} {p_ {t} (s_ {t}, x_ {t}) + f_ {t +1} (s_ {t + 1}) }}$

куда ${ Displaystyle s_ {t + 1} = g_ {t} (s_ {t}, x_ {t})}$ а граничное условие системы

${ displaystyle f_ {n} (s_ {n}) = max _ {x_ {n} in X_ {n}} {p_ {n} (s_ {n}, x_ {n}) }.}$

Цель состоит в том, чтобы определить набор оптимальных действий, которые максимизируют ${ displaystyle f_ {1} (s_ {1})}$. Учитывая текущее состояние ${ displaystyle s_ {t}}$ и текущее действие ${ displaystyle x_ {t}}$, мы знать с уверенностью вознаграждение, полученное на текущем этапе, и - благодаря функции перехода между состояниями ${ displaystyle g_ {t}}$ - будущее состояние, к которому переходит система.

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

Стохастическое динамическое программирование имеет дело с проблемами, в которых вознаграждение текущего периода и / или состояние следующего периода являются случайными, то есть с многоступенчатыми стохастическими системами. Цель лица, принимающего решения, - максимизировать ожидаемое (дисконтированное) вознаграждение в течение заданного горизонта планирования.

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

${ displaystyle f_ {t} (s_ {t}) = max _ {x_ {t} in X_ {t} (s_ {t})} left {({ text {ожидаемое вознаграждение на этапе}} t mid s_ {t}, x_ {t}) + alpha sum _ {s_ {t + 1}} Pr (s_ {t + 1} mid s_ {t}, x_ {t}) f_ { t + 1} (s_ {t + 1}) right }}$

куда

• ${ displaystyle f_ {t} (s_ {t})}$ это максимальная ожидаемая награда, которую можно получить на этапах ${ Displaystyle т, т + 1, ldots, п}$, учитывая состояние ${ displaystyle s_ {t}}$ в начале этапа ${ displaystyle t}$;
• ${ displaystyle x_ {t}}$ принадлежит набору ${ displaystyle X_ {t} (s_ {t})}$ возможных действий на этапе ${ displaystyle t}$ данное начальное состояние ${ displaystyle s_ {t}}$;
• ${ displaystyle alpha}$ это коэффициент дисконтирования;
• ${ Displaystyle Pr (s_ {t + 1} mid s_ {t}, x_ {t})}$ - условная вероятность того, что состояние в начале этапа ${ displaystyle t}$ является ${ displaystyle s_ {t + 1}}$ учитывая текущее состояние ${ displaystyle s_ {t}}$ и выбранное действие ${ displaystyle x_ {t}}$.

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

Азартная игра как стохастическая динамическая программа

Азартную игру можно сформулировать как стохастическую динамическую программу следующим образом: есть ${ displaystyle n = 4}$ игры (т.е. этапы) в горизонте планирования

• то государственный ${ displaystyle s}$ в период ${ displaystyle t}$ представляет собой начальное богатство в начале периода ${ displaystyle t}$;
• то действие данное состояние ${ displaystyle s}$ в период ${ displaystyle t}$ это сумма ставки ${ displaystyle b}$;
• то вероятность перехода ${ displaystyle p_ {я, j} ^ {а}}$ от государства ${ displaystyle i}$ заявить ${ displaystyle j}$ когда действие ${ displaystyle a}$ принимается в состоянии ${ displaystyle i}$ легко выводится из вероятности выигрыша (0,4) или проигрыша (0,6) игры.

Позволять ${ displaystyle f_ {t} (s)}$ - вероятность того, что к концу игры 4 у игрока будет не менее 6 долларов, при условии, что у него есть${ displaystyle s}$ в начале игры ${ displaystyle t}$.

• то немедленная прибыль понесено, если действие ${ displaystyle b}$ принимается в состоянии ${ displaystyle s}$ дается ожидаемым значением ${ displaystyle p_ {t} (s, b) = 0,4f_ {t + 1} (s + b) + 0,6f_ {t + 1} (s-b)}$.

Чтобы получить функциональное уравнение, определять ${ displaystyle b_ {t} (s)}$ как ставка, которая достигает ${ displaystyle f_ {t} (s)}$, затем в начале игры ${ displaystyle t = 4}$

• если ${ displaystyle s <3}$ невозможно достичь цели, т.е. ${ displaystyle f_ {4} (s) = 0}$ за ${ displaystyle s <3}$;
• если ${ displaystyle s geq 6}$ цель достигнута, т.е. ${ displaystyle f_ {4} (s) = 1}$ за ${ displaystyle s geq 6}$;
• если ${ displaystyle 3 leq s leq 5}$ игрок должен сделать ставку, достаточную для достижения цели, т.е. ${ displaystyle f_ {4} (s) = 0,4}$ за ${ displaystyle 3 leq s leq 5}$.

За ${ Displaystyle т <4}$ функциональное уравнение ${ displaystyle f_ {t} (s) = max _ {b_ {t} (s)} {0.4f_ {t + 1} (s + b) + 0.6f_ {t + 1} (sb) } }$, куда ${ displaystyle b_ {t} (s)}$ колеблется в ${ displaystyle 0, ..., s}$; цель найти ${ displaystyle f_ {1} (2)}$.

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

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

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

Обратная рекурсия

Учитывая ограниченное пространство состояний, обратная рекурсия (Бертсекас 2000 ) начинается с табулирования ${ displaystyle f_ {n} (к)}$ для каждого возможного состояния ${ displaystyle k}$ принадлежащий к финальной стадии ${ displaystyle n}$. После того, как эти значения занесены в таблицу вместе с соответствующими оптимальными действиями, зависящими от состояния ${ Displaystyle х_ {п} (к)}$, можно перейти на сцену ${ displaystyle n-1}$ и свести в таблицу ${ displaystyle f_ {n-1} (к)}$ для всех возможных состояний, принадлежащих сцене ${ displaystyle n-1}$. Процесс продолжается рассмотрением в назад модифицируйте все оставшиеся этапы вплоть до первого. После завершения процесса табуляции ${ displaystyle f_ {1} (s)}$ - значение оптимальной политики при начальном состоянии ${ displaystyle s}$ - а также соответствующее оптимальное действие ${ displaystyle x_ {1} (s)}$ можно легко извлечь из таблицы. Поскольку вычисление происходит в обратном порядке, очевидно, что обратная рекурсия может привести к вычислению большого количества состояний, которые не являются необходимыми для вычисления ${ displaystyle f_ {1} (s)}$.

Пример: азартная игра.

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Январь 2017 г.)

Прямая рекурсия

Учитывая начальное состояние ${ displaystyle s}$ системы в начале периода 1, прямая рекурсия (Бертсекас 2000 ) вычисляет ${ displaystyle f_ {1} (s)}$ путем постепенного расширения функционального уравнения (пас вперед). Это включает рекурсивные вызовы для всех ${ Displaystyle е_ {т + 1} ( cdot), е_ {т + 2} ( cdot), ldots}$ которые необходимы для вычисления данного ${ displaystyle f_ {t} ( cdot)}$. Затем значение оптимальной политики и ее структура извлекаются через (обратный проход), в котором разрешаются эти приостановленные рекурсивные вызовы. Ключевым отличием от обратной рекурсии является то, что ${ displaystyle f_ {t}}$ вычисляется только для состояний, релевантных для вычисления ${ displaystyle f_ {1} (s)}$. Мемоизация используется, чтобы избежать пересчета состояний, которые уже были рассмотрены.

Пример: азартная игра.

Мы проиллюстрируем прямую рекурсию в контексте ранее обсужденного экземпляра азартной игры. Мы начинаем пас вперед С учетом${ displaystyle f_ {1} (2) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 1,2,3,4}} hline 0 & 0. 4f_ {2} (2 + 0) + 0.6f_ {2} (2-0) 1 & 0.4f_ {2} (2 + 1) + 0.6f_ {2} (2-1) 2 & 0.4f_ { 2} (2 + 2) + 0.6f_ {2} (2-2) end {array}} right.}$

На данный момент мы еще не вычислили ${ displaystyle f_ {2} (4), f_ {2} (3), f_ {2} (2), f_ {2} (1), f_ {2} (0)}$, которые необходимы для вычисления ${ displaystyle f_ {1} (2)}$; мы продолжаем и вычисляем эти элементы. Обратите внимание, что ${ displaystyle f_ {2} (2 + 0) = f_ {2} (2-0) = f_ {2} (2)}$, поэтому можно использовать мемоизация и выполнить необходимые вычисления только один раз.

Расчет ${ displaystyle f_ {2} (4), f_ {2} (3), f_ {2} (2), f_ {2} (1), f_ {2} (0)}$

${ displaystyle f_ {2} (0) = min left {{ begin {array} {rr} b & { text {вероятность успеха за периоды 2,3,4}} hline 0 & 0.4f_ { 3} (0 + 0) + 0.6f_ {3} (0-0) end {array}} right.}$

${ displaystyle f_ {2} (1) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периоды 2,3,4}} hline 0 & 0.4f_ { 3} (1 + 0) + 0.6f_ {3} (1-0) 1 & 0.4f_ {3} (1 + 1) + 0.6f_ {3} (1-1) end {array}} верно.}$

${ displaystyle f_ {2} (2) = min left {{ begin {array} {rr} b & { text {вероятность успеха за периоды 2,3,4}} hline 0 & 0.4f_ { 3} (2 + 0) + 0,6f_ {3} (2-0) 1 & 0,4f_ {3} (2 + 1) + 0,6f_ {3} (2-1) 2 & 0,4f_ {3} (2 + 2) + 0.6f_ {3} (2-2) end {array}} right.}$

${ displaystyle f_ {2} (3) = min left {{ begin {array} {rr} b & { text {вероятность успеха за периоды 2,3,4}} hline 0 & 0.4f_ { 3} (3 + 0) + 0.6f_ {3} (3-0) 1 & 0.4f_ {3} (3 + 1) + 0.6f_ {3} (3-1) 2 & 0.4f_ {3} (3 + 2) + 0.6f_ {3} (3-2) 3 & 0.4f_ {3} (3 + 3) + 0.6f_ {3} (3-3) end {array}} right .}$

${ displaystyle f_ {2} (4) = min left {{ begin {array} {rr} b & { text {вероятность успеха за периоды 2,3,4}} hline 0 & 0.4f_ { 3} (4 + 0) + 0.6f_ {3} (4-0) 1 & 0.4f_ {3} (4 + 1) + 0.6f_ {3} (4-1) 2 & 0.4f_ {3} (4 + 2) + 0.6f_ {3} (4-2) end {array}} right.}$

Мы вычислили ${ displaystyle f_ {2} (к)}$ для всех ${ displaystyle k}$ которые необходимы для вычисления ${ displaystyle f_ {1} (2)}$. Однако это привело к дополнительным приостановленным рекурсиям, связанным с ${ displaystyle f_ {3} (4), f_ {3} (3), f_ {3} (2), f_ {3} (1), f_ {3} (0)}$. Мы продолжаем и вычисляем эти значения.

Расчет ${ displaystyle f_ {3} (4), f_ {3} (3), f_ {3} (2), f_ {3} (1), f_ {3} (0)}$

${ displaystyle f_ {3} (0) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0.4f_ {4} (0 + 0) + 0.6f_ {4} (0-0) end {array}} right.}$

${ displaystyle f_ {3} (1) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0.4f_ {4} (1 + 0) + 0.6f_ {4} (1-0) 1 & 0.4f_ {4} (1 + 1) + 0.6f_ {4} (1-1) end {array}} right .}$

${ displaystyle f_ {3} (2) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0.4f_ {4} (2 + 0) + 0,6f_ {4} (2-0) 1 & 0,4f_ {4} (2 + 1) + 0,6f_ {4} (2-1) 2 & 0,4f_ {4} (2 +2) + 0.6f_ {4} (2-2) end {array}} right.}$

${ displaystyle f_ {3} (3) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0.4f_ {4} (3 + 0) + 0,6f_ {4} (3-0) 1 & 0,4f_ {4} (3 + 1) + 0,6f_ {4} (3-1) 2 & 0,4f_ {4} (3 +2) + 0.6f_ {4} (3-2) 3 & 0.4f_ {4} (3 + 3) + 0.6f_ {4} (3-3) end {array}} right.}$

${ displaystyle f_ {3} (4) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0.4f_ {4} (4 + 0) + 0.6f_ {4} (4-0) 1 & 0.4f_ {4} (4 + 1) + 0.6f_ {4} (4-1) 2 & 0.4f_ {4} (4 +2) + 0.6f_ {4} (4-2) end {array}} right.}$

${ displaystyle f_ {3} (5) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0.4f_ {4} (5 + 0) + 0.6f_ {4} (5-0) 1 & 0.4f_ {4} (5 + 1) + 0.6f_ {4} (5-1) end {array}} right.}$

Поскольку этап 4 - последний этап в нашей системе, ${ displaystyle f_ {4} ( cdot)}$ представлять граничные условия которые легко вычисляются следующим образом.

Граничные условия

${ displaystyle { begin {array} {ll} f_ {4} (0) = 0 & b_ {4} (0) = 0 f_ {4} (1) = 0 & b_ {4} (1) = {0 , 1 } f_ {4} (2) = 0 & b_ {4} (2) = {0,1,2 } f_ {4} (3) = 0,4 & b_ {4} (3) = {3 } f_ {4} (4) = 0,4 & b_ {4} (4) = {2,3,4 } f_ {4} (5) = 0,4 & b_ {4} (5 ) = {1,2,3,4,5 } f_ {4} (d) = 1 & b_ {4} (d) = {0, ldots, d-6 } { text {для }} d geq 6 end {массив}}}$

На этом этапе можно продолжить и восстановить оптимальную политику и ее значение с помощью обратный проход включающий, в первую очередь, этап 3

Обратный проход с участием ${ displaystyle f_ {3} ( cdot)}$

${ displaystyle f_ {3} (0) = min left {{ begin {array} {rr} b & { text {вероятность успеха в периодах 3,4}} hline 0 & 0,4 (0) +0,6 (0) = 0 end {array}} right.}$

${ displaystyle f_ {3} (1) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 3,4}} & { mbox {max}} hline 0 & 0,4 (0) +0,6 (0) = 0 & leftarrow b_ {3} (1) = 0 1 & 0,4 (0) +0,6 (0) = 0 & leftarrow b_ {3} (1) = 1 end {array}} right.}$

${ displaystyle f_ {3} (2) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 3,4}} & { mbox {max}} hline 0 & 0,4 (0) +0,6 (0) = 0 1 & 0,4 (0,4) +0,6 (0) = 0,16 & leftarrow b_ {3} (2) = 1 2 & 0,4 (0,4) +0,6 (0) = 0,16 & leftarrow b_ {3} (2) = 2 end {array}} right.}$

${ displaystyle f_ {3} (3) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 3,4}} & { mbox {max}} hline 0 & 0,4 (0,4) +0,6 (0,4) = 0,4 & leftarrow b_ {3} (3) = 0 1 & 0,4 (0,4) +0,6 (0) = 0,16 2 & 0,4 (0,4) +0,6 (0) = 0,16 3 & 0,4 (1) +0,6 (0) = 0,4 & leftarrow b_ {3} (3) = 3 end {array}} right.}$

${ displaystyle f_ {3} (4) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 3,4}} & { mbox {max}} hline 0 & 0,4 (0,4) +0,6 (0,4) = 0,4 & leftarrow b_ {3} (4) = 0 1 & 0,4 (0,4) +0,6 (0,4) = 0,4 & leftarrow b_ {3} ( 4) = 1 2 & 0,4 (1) +0,6 (0) = 0,4 & leftarrow b_ {3} (4) = 2 end {array}} right.}$

${ displaystyle f_ {3} (5) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 3,4}} & { mbox {max}} hline 0 & 0,4 (0,4) +0,6 (0,4) = 0,4 1 & 0,4 (1) +0,6 (0,4) = 0,64 & leftarrow b_ {3} (5) = 1 end {array}} верно.}$

а затем этап 2.

Обратный проход с участием ${ displaystyle f_ {2} ( cdot)}$

${ displaystyle f_ {2} (0) = min left {{ begin {array} {rrr} b & { text {вероятность успеха за периоды 2,3,4}} & { mbox {max}} hline 0 & 0,4 (0) +0,6 (0) = 0 & leftarrow b_ {2} (0) = 0 end {array}} right.}$

${ displaystyle f_ {2} (1) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 2,3,4}} & { mbox {max}} hline 0 & 0,4 (0) +0,6 (0) = 0 1 & 0,4 (0,16) +0,6 (0) = 0,064 & leftarrow b_ {2} (1) = 1 end {массив }}верно.}$

${ displaystyle f_ {2} (2) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периоды 2,3,4}} & { mbox {max}} hline 0 & 0,4 (0,16) +0,6 (0,16) = 0,16 & leftarrow b_ {2} (2) = 0 1 & 0,4 (0,4) +0,6 (0) = 0,16 & leftarrow b_ {2 } (2) = 1 2 & 0,4 (0,4) +0,6 (0) = 0,16 & leftarrow b_ {2} (2) = 2 end {array}} right.}$

${ displaystyle f_ {2} (3) = min left {{ begin {array} {rrr} b & { text {вероятность успеха за периоды 2,3,4}} & { mbox {max}} hline 0 & 0,4 (0,4) +0,6 (0,4) = 0,4 & leftarrow b_ {2} (3) = 0 1 & 0,4 (0,4) +0,6 (0,16) = 0,256 2 & 0,4 ( 0,64) +0,6 (0) = 0,256 3 & 0,4 (1) +0,6 (0) = 0,4 & leftarrow b_ {2} (3) = 3 end {array}} right.}$

${ displaystyle f_ {2} (4) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 2, 3, 4}} & { mbox {max}} hline 0 & 0,4 (0,4) +0,6 (0,4) = 0,4 1 & 0,4 (0,64) +0,6 (0,4) = 0,496 & leftarrow b_ {2} (4) = 1 2 & 0,4 ( 1) +0,6 (0,16) = 0,496 & leftarrow b_ {2} (4) = 2 end {array}} right.}$

Наконец-то восстанавливаем значение ${ displaystyle f_ {1} (2)}$ оптимальной политики

${ displaystyle f_ {1} (2) = min left {{ begin {array} {rrr} b & { text {вероятность успеха в периодах 1,2,3,4}} & { mbox {max }} hline 0 & 0,4 (0,16) +0,6 (0,16) = 0,16 1 & 0,4 (0,4) +0,6 (0,064) = 0,1984 & leftarrow b_ {1} (2) = 1 2 & 0. 4 (0,496) +0,6 (0) = 0,1984 & leftarrow b_ {1} (2) = 2 end {array}} right.}$

Это оптимальная политика, которая была проиллюстрирована ранее. Обратите внимание, что существует несколько оптимальных политик, ведущих к одному и тому же оптимальному значению. ${ displaystyle f_ {1} (2) = 0,1984}$; например, в первой игре можно поставить либо 1 доллар, либо 2 доллара.

Реализация Python. Следующее - полное Python реализация этого примера.

из набор текста импорт Список, Кортежимпорт запоминать в качестве мемимпорт functools учебный класс запоминать:         def __в этом__(себя, func):         себя.func = func         себя.памятный = {}         себя.method_cache = {}     def __вызов__(себя, *аргументы):         возвращаться себя.cache_get(себя.памятный, аргументы,             лямбда: себя.func(*аргументы))     def __получать__(себя, объект, objtype):         возвращаться себя.cache_get(себя.method_cache, объект,             лямбда: себя.__учебный класс__(functools.частичный(себя.func, объект)))     def cache_get(себя, тайник, ключ, func):         пытаться:             возвращаться тайник[ключ]         Кроме KeyError:             тайник[ключ] = func()             возвращаться тайник[ключ]         def перезагрузить(себя):        себя.памятный = {}         себя.method_cache = {} учебный класс Состояние:    '' состояние проблемы разорения игрока    '''    def __в этом__(себя, т: int, богатство: плавать):        '' 'конструктор состояний        Аргументы:            t {int} - период времени            богатство {float} - начальное богатство        '''        себя.т, себя.богатство = т, богатство    def __eq__(себя, Другой):         возвращаться себя.__dict__ == Другой.__dict__    def __str__(себя):        возвращаться ул(себя.т) + " " + ул(себя.богатство)    def __hash__(себя):        возвращаться хэш(ул(себя))учебный класс GamblersRuin:    def __в этом__(себя, ставкиГоризонт:int, targetWealth: плавать, pmf: Список[Список[Кортеж[int, плавать]]]):        проблема разорения игрока        Аргументы:            bettingHorizon {int} - горизонт ставок            targetWealth {float} - целевое богатство            pmf {List [List [Tuple [int, float]]]} - функция массы вероятности        '''        # инициализировать переменные экземпляра        себя.ставкиГоризонт, себя.targetWealth, себя.pmf = ставкиГоризонт, targetWealth, pmf        # лямбды        себя.аг = лямбда s: [я за я в классифицировать(0, мин(себя.targetWealth//2, s.богатство) + 1)] # генератор действий        себя.ул = лямбда s, а, р: Состояние(s.т + 1, s.богатство - а + а*р)                       # переход состояния        себя.iv = лямбда s, а, р: 1 если s.богатство - а + а*р >= себя.targetWealth еще 0      # функция немедленного значения        себя.cache_actions = {}  # кеш с оптимальными парами состояние / действие    def ж(себя, богатство: плавать) -> плавать:        s = Состояние(0, богатство)        возвращаться себя._f(s)    def q(себя, т: int, богатство: плавать) -> плавать:        s = Состояние(т, богатство)        возвращаться себя.cache_actions[ул(s)]    @memoize    def _f(себя, s: Состояние) -> плавать:        # Прямая рекурсия        v = Максимум(            [сумма([п[1]*(себя._f(себя.ул(s, а, п[0]))                   если s.т < себя.ставкиГоризонт - 1 еще себя.iv(s, а, п[0]))   # будущая стоимость                  за п в себя.pmf[s.т]])                                     # реализация случайных величин             за а в себя.аг(s)])                                             # действие        opt_a = лямбда а: сумма([п[1]*(себя._f(себя.ул(s, а, п[0]))                                если s.т < себя.ставкиГоризонт - 1 еще себя.iv(s, а, п[0]))                                за п в себя.pmf[s.т]]) == v                  q = [k за k в фильтр(opt_a, себя.аг(s))]                              # получить список лучших действий        себя.cache_actions[ул(s)]=q[0] если bool(q) еще Никто                    # сохранить действие в словаре                возвращаться v                                                                # возвращаемое значениепример = {"bettingHorizon": 4, "targetWealth": 6, "pmf": [[(0, 0.6),(2, 0.4)] за я в классифицировать(0,4)]}гр, initial_wealth = GamblersRuin(**пример), 2# f_1 (x) - вероятность игрока достичь $ targetWealth в конце ставки.Распечатать("f_1 ("+ул(initial_wealth)+"): " + ул(гр.ж(initial_wealth))) # Восстановите оптимальное действие для периода 2, когда начальное богатство в начале периода 2 составляет 1 доллар.т, initial_wealth = 1, 1Распечатать("b_"+ул(т+1)+"("+ул(initial_wealth)+"): " + ул(гр.q(т, initial_wealth)))

Реализация на Java. GamblersRuin.java автономный Java 8 реализация приведенного выше примера.

Примерное динамическое программирование

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Январь 2017 г.)

Введение в приблизительное динамическое программирование предоставляется (Пауэлл 2009 ).

дальнейшее чтение

• Беллман, Р. (1957), Динамическое программирование, Издательство Принстонского университета, ISBN  978-0-486-42809-3. Дуврское издание в мягкой обложке (2003 г.).
• Росс, С. М .; Bimbaum, Z. W .; Лукач, Э. (1983), Введение в стохастическое динамическое программирование, Эльзевьер, ISBN  978-0-12-598420-1.
• Бертсекас, Д. П. (2000), Динамическое программирование и оптимальное управление (2-е изд.), Athena Scientific, ISBN  978-1-886529-09-0. В двух томах.
• Пауэлл, В. Б. (2009), "Что следует знать о приблизительном динамическом программировании", Логистика военно-морских исследований, 56 (1): 239–249, CiteSeerX  10.1.1.150.1854, Дои:10.1002 / nav.20347

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

• Динамическое программирование
• Стохастический процесс
• Стохастическое программирование
• Теория управления
• Стохастический контроль
• Обучение с подкреплением

Рекомендации