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

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

Наглядный пример: азартная игра [ править ]

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

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

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

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

Официальный фон [ править ]

Рассмотрим дискретную систему, определенную на этапах, в которой каждый этап характеризуется${\ 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 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}$
• вероятность перехода из состояния в состояние , когда действие берется в состоянии легко вывести из вероятности выигрыша (0.4) или проигрыша (0.6) игры.${\displaystyle p_{i,j}^{a}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle a}$${\displaystyle i}$

Пусть будет вероятностью того, что к концу игры 4 у игрока будет не менее 6 долларов, при условии, что у нее есть доллар в начале игры . ${\displaystyle f_{t}(s)}$${\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)}$

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

Способы решения [ править ]

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

Обратная рекурсия [ править ]

Учитывая ограниченное пространство состояний, обратная рекурсия ( Bertsekas 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)}$

Пример: азартная игра [ править ]

Прямая рекурсия [ править ]

Учитывая начальное состояние системы в начале периода 1, прямая рекурсия ( Bertsekas 2000 ) вычисляется путем постепенного расширения функционального уравнения ( прямой проход ). Это включает в себя рекурсивные вызовы всего, что необходимо для вычисления данного . Затем значение оптимальной политики и ее структура извлекаются посредством ( обратного прохода ), в котором эти приостановленные рекурсивные вызовы разрешаются. Ключевым отличием от обратной рекурсии является тот факт, что она вычисляется только для состояний, релевантных для вычисления . Мемоизация используется, чтобы избежать повторного вычисления состояний, которые уже были рассмотрены.${\displaystyle s}$${\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.}$

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

Реализация Python. Ниже приводится полная реализация этого примера на языке Python .

от  типизации  импорта  списка ,  Кортеж импорт  memoize ,  как  мем импорт  functools  памятка класса :   def  __init__ ( self ,  func ):  себя . func  =  func  self . memoized  =  {}  self . method_cache  =  {}  def  __call__ ( self ,  * args ):  вернуть  себя . cache_get ( self . memoized ,  args ,  lambda :  self . func ( * args ))  def  __get__ ( self ,  obj ,  objtype ):  вернуть  себя . cache_get ( самостоятельно . method_cache ,  OBJ ,  лямбда :  самостоятельно . __class__ ( functools . частичная ( самостоятельно . FUNC ,  OBJ )))  def  cache_get ( self ,  cache ,  key ,  func ):  try :  return  cache [ key ]  except  KeyError :  cache [ key ]  =  func ()  return  cache [ key ]   def  reset ( self ):  self . memoized  =  {}  self . method_cache  =  {} class  State :  '' 'состояние проблемы разорения игрока  ' '' def  __init__ ( self ,  t :  int ,  богатство :  float ):  '' 'конструктор состояния  Аргументы:  t {int} - период времени  богатство {float} - начальное богатство  ' '' self . т , сам . богатство = т , богатство       def  __eq__ ( self ,  other ):  вернуть  себя . __dict__  ==  другое . __dict__ def  __str__ ( self ):  return  str ( self . t )  +  ""  +  str ( собственное . богатство ) def  __hash__ ( self ):  вернуть  хэш ( str ( self ))класс  GamblersRuin : def  __init__ ( self ,  bettingHorizon : int ,  targetWealth :  float ,  pmf :  List [ List [ Tuple [ int ,  float ]]]):  '' 'проблема разорения игрока  Аргументы:  bettingHorizon {int} - горизонт ставок  targetWealth {float} - целевое богатство  pmf {List [List [Tuple [int, float]]]} - функция массы вероятности  '' '  # инициализировать переменные экземпляра  self . bettingHorizon ,  self . targetWealth ,  сам . pmf  =  bettingHorizon ,  targetWealth ,  pmf # lambdas  self . аг  =  лямбда  s :  [ я  для  я  в  диапазоне ( 0 ,  мин ( самостоятельно . targetWealth // 2 ,  ев . Богатство )  +  1 )]  # действие генератора  самостоятельно . st  =  лямбда  s ,  a ,  r :  состояние ( s . t  +  1 ,  s . богатство -  a  +  a * r )  # переход состояния  self . iv  =  лямбда  s ,  a ,  r :  1,  если  s . богатство  -  а  +  а * г  > =  себя . targetWealth  else  0  # функция немедленного значения я . cache_actions  =  {}  # кеш с оптимальными парами состояние / действие def  f ( self ,  богатство :  float )  ->  float :  s  =  State ( 0 ,  богатство )  return  self . _f ( s ) def  q ( self ,  t :  int ,  богатство :  float )  ->  float :  s  =  State ( t ,  богатство )  return  self . cache_actions [ str ( s )] @memoize  def  _f ( self ,  s :  State )  ->  float : #  Прямая рекурсия  v  =  max (  [ sum ([ p [ 1 ] * ( self . _f ( self . st ( s ,  a ,  p [ 0 ]))  if  s . t  <  self . bettingHorizon  -  1  else  self. IV ( ев ,  , р [ 0 ])) # будущее значение для р в себя . pmf [ s . t ]]) # реализация случайной величины для a in self . ag ( s )]) # действия             opt_a  =  lambda  a :  sum ([ p [ 1 ] * ( self . _f ( self . st ( s ,  a ,  p [ 0 ])),  если  s . t  <  self . bettingHorizon  -  1  else  self . iv ( s ,  a ,  p [ 0 ]))  для  p  в  self .pmf [ s . t ]])  ==  v  q  =  [ k  for  k  in  filter ( opt_a ,  self . ag ( s ))]  # получить список лучших действий  self . cache_actions [ str ( s )] = q [ 0 ]  if  bool ( q )  else  None  # сохранить действие в словаре  return  v  # возвращаемое значениеinstance  =  { "bettingHorizon" :  4 ,  "targetWealth" :  6 ,  "pmf" :  [[( 0 ,  0.6 ), ( 2 ,  0.4 )]  для  i  в  диапазоне ( 0 , 4 )]} gr ,  initial_wealth  =  GamblersRuin ( ** экземпляр ),  2# f_1 (x) - вероятность игрока достичь $ targetWealth в конце ставки Horizon print ( "f_1 (" + str ( initial_wealth ) + "):"  +  str ( gr . f ( initial_wealth ))) # Восстановите оптимальное действие для периода 2, когда начальное богатство в начале периода 2 составляет 1 доллар. t ,  initial_wealth  =  1 ,  1 print ( "b_" + str ( t + 1 ) + "(" + str ( initial_wealth ) + "):"  +  str ( gr . q ( t ,  initial_wealth )))

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

Примерное динамическое программирование [ править ]

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

Дальнейшее чтение [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]