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

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

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

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

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

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

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

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

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

• ан начальное состояние ${\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 t,t+1,\ldots ,n}$. Без потери общности в дальнейшем мы рассмотрим настройку максимизации вознаграждения. В детерминированном динамическое программирование обычно имеют дело с функциональные уравнения принимая следующую структуру

${\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{expected reward during stage }}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 t,t+1,\ldots ,n}$, учитывая состояние ${\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_{i,j}^{a}}$ от государства ${\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 t<4}$ функциональное уравнение ${\displaystyle f_{t}(s)=\max _{b_{t}(s)}\{0.4f_{t+1}(s+b)+0.6f_{t+1}(s-b)\}}$, куда ${\displaystyle b_{t}(s)}$ колеблется в ${\displaystyle 0,...,s}$; цель найти ${\displaystyle f_{1}(2)}$.

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

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

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

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

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

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

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

Учитывая начальное состояние ${\displaystyle s}$ системы в начале периода 1, прямая рекурсия (Бертсекас 2000 ) вычисляет ${\displaystyle f_{1}(s)}$ путем постепенного расширения функционального уравнения (пас вперед). Это включает рекурсивные вызовы для всех ${\displaystyle f_{t+1}(\cdot ),f_{t+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{success probability in periods 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{success probability in periods 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{success probability in periods 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}}\right.}$

${\displaystyle f_{2}(2)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 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{success probability in periods 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{success probability in periods 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}(k)}$ для всех ${\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{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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{ for }}d\geq 6\end{array}}}$

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

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

${\displaystyle f_{3}(0)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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}}\right.}$

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

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

${\displaystyle f_{2}(0)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 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{success probability in periods 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{array}}\right.}$

${\displaystyle f_{2}(2)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 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{success probability in periods 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{success probability in periods 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{success probability in periods 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 реализация приведенного выше примера.

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

Введение в приблизительное динамическое программирование предоставляется (Пауэлл 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

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

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

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

1. Эта проблема адаптирована из W. L. Winston, Operations Research: Applications and Algorithms (7th Edition), Duxbury Press, 2003, chap. 19, пример 3.