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

1957 Метод моделирования проблем принятия решений в условиях неопределенности

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

Мотивирующий пример: Азартная игра

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

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

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

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

Официальное происхождение

Рассмотрим дискретную систему, определенную на этапах, в которой каждый этап характеризуется ${\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}$
• Вероятность перехода из состояния в состояние при совершении действия в состоянии легко выводится из вероятности выигрыша (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)}$

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

Мы проиллюстрируем прямую рекурсию в контексте ранее обсуждавшегося экземпляра игры Gambling. Мы начинаем прямой проход , рассматривая ${\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 этого примера.

от  ввода  import  List ,  Tuple import  functoolsкласс  memoize :  def  __init__ ( self ,  func ) :  self.func = func self.memoized = { } self.method_cache = { }​​​         def  __call__ ( self ,  * args ):  return  self . cache_get ( self . memoized ,  args ,  lambda :  self . func ( * args )) def  __get__ ( self ,  obj ,  objtype ):  return  self . cache_get (  self . method_cache ,  obj ,  lambda :  self . __class__ ( functools . partial ( self . 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 = { }​     класс  Состояние : """состояние проблемы разорения игрока"""  def  __init__ ( self ,  t :  int ,  wealth :  float ): """конструктор состояний  Аргументы:  t {int} -- период времени  wealth {float} -- начальное wealth  """  self . t ,  self . wealth  =  t ,  wealth def  __eq__ ( self ,  other ):  return  self .__ dict__  ==  other .__ dict__ def  __str__ ( self ) :  return  str ( self.t ) + " " + str ( self.weather )​​     def  __hash__ ( self ):  возвращает  хэш ( str ( self ))class  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 , self.pmf = ( bettingHorizon , targetWealth , pmf , )​​​         #  лямбда - выражения self.ag = lambda s : [ i for i in range ( 0 , min ( self.targetWealth // 2 , s.wealth ) + 1 ) ] # генератор действий self.st = lambda s , a , r : State ( s.t + 1 , s.wealth - a + a * r ) # переход между состояниями self.iv = ( lambda s , a , r : 1 if s.wealth - a + a * r > = self.targetWealth else 0 ) # функция немедленного получения значения​​​​​                                                           self . cache_actions  =  {}  # кэш с оптимальными парами состояние/действие def  f ( self ,  wealth :  float )  -  > float :  s  =  State ( 0 ,  wealth )  return  self._f ( s )​ def  q ( self ,  t :  int ,  wealth :  float )  ->  float :  s  =  State ( t ,  wealth )  return  self . cache_actions [ str ( s )] @memoize  def  _f ( self ,  s :  State )  ->  float : #  Значения прямой рекурсии  = [ sum ([ p [ 1 ] * ( self . _f ( self . st ( s , a , p [ 0 ])) if s . t < self . bettingHorizon - 1 else self . iv ( s , a , p [ 0 ])) # функция значения для p в self . pmf [ s . t ]]) # реализации ставок для a в self . ag ( s )] # действия                            v  =  max ( values )  try :  self.cache_actions [ str ( s )] = self.ag ( s ) [ values.index ( v ) ] # сохранить лучшее действие , кроме ValueError : self.cache_actions [ str ( s )] = None print ( " Ошибка при получении лучшего действия" ) return v # вернуть ожидаемую общую стоимость        экземпляр  =  {  "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).
• Росс, SM; Бимбаум, ZW; Лукач, E. (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, S2CID  7134937

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

• Портал системной науки
• Математический портал

• Теория управления  – Раздел инженерии и математики
• Динамическое программирование  – Метод оптимизации задач
• Обучение с подкреплением  – Область машинного обучения
• Стохастическое управление  – Вероятностное оптимальное управление
• Стохастический процесс  – совокупность случайных величин
• Стохастическое программирование  – фреймворк для моделирования задач оптимизации, которые включают неопределенность.

Ссылки

1. Эта задача адаптирована из книги WL Winston, Operations Research: Applications and Algorithms (7-е издание), Duxbury Press, 2003, глава 19, пример 3.