Programación dinámica estocástica

Técnica de 1957 para modelar problemas de toma de decisiones en condiciones de incertidumbre

Introducida originalmente por Richard E. Bellman en (Bellman 1957), la programación dinámica estocástica es una técnica para modelar y resolver problemas de toma de decisiones en condiciones de incertidumbre . Estrechamente relacionada con la programación estocástica y la programación dinámica , la programación dinámica estocástica representa el problema en cuestión en forma de una ecuación de Bellman . El objetivo es calcular una política que prescriba cómo actuar de manera óptima ante la incertidumbre.

Un ejemplo motivador: el juego de azar

Un jugador tiene $2, puede jugar un juego de azar 4 veces y su objetivo es maximizar su probabilidad de terminar con al menos $6. Si el jugador apuesta $ en una jugada del juego, entonces con una probabilidad de 0,4 gana el juego, recupera la apuesta inicial y aumenta su posición de capital en $ ; con una probabilidad de 0,6, pierde el monto apostado $ ; todas las jugadas son independientes por pares . En cualquier jugada del juego, el jugador no puede apostar más dinero del que tiene disponible al comienzo de esa jugada. ^[1] ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$

Se puede emplear la programación dinámica estocástica para modelar este problema y determinar una estrategia de apuestas que, por ejemplo, maximice la probabilidad del jugador de alcanzar una riqueza de al menos $6 al final del horizonte de apuestas.

Téngase en cuenta que si no hay límite en el número de juegos que se pueden jugar, el problema se convierte en una variante de la conocida paradoja de San Petersburgo .

Una estrategia de apuestas óptima que maximiza la probabilidad del jugador de obtener una riqueza de al menos $6 al final del horizonte de apuestas; representa el monto de la apuesta para el juego cuando el jugador tiene $ al comienzo de ese juego. Si el que toma la decisión sigue esta política, con una probabilidad de 0,1984 obtendrá una riqueza de al menos $6. ${\displaystyle b_{t}(\$x)}$ ${\displaystyle t}$ ${\displaystyle x}$

Antecedentes formales

Consideremos un sistema discreto definido en etapas en el que cada etapa se caracteriza por ${\displaystyle n}$ ${\displaystyle t=1,\ldots ,n}$

• un estado inicial , donde es el conjunto de estados factibles al comienzo de la etapa ; ${\displaystyle s_{t}\in S_{t}}$ ${\displaystyle S_{t}}$ ${\displaystyle t}$
• una variable de decisión , donde es el conjunto de acciones factibles en la etapa – tenga en cuenta que puede ser una función del estado inicial ; ${\displaystyle x_{t}\in X_{t}}$ ${\displaystyle X_{t}}$ ${\displaystyle t}$ ${\displaystyle X_{t}}$ ${\displaystyle s_{t}}$
• una función de costo/recompensa inmediata , que representa el costo/recompensa en la etapa si es el estado inicial y la acción seleccionada; ${\displaystyle p_{t}(s_{t},x_{t})}$ ${\displaystyle t}$ ${\displaystyle s_{t}}$ ${\displaystyle x_{t}}$
• una función de transición de estado que conduce al sistema hacia el estado . ${\displaystyle g_{t}(s_{t},x_{t})}$ ${\displaystyle s_{t+1}=g_{t}(s_{t},x_{t})}$

Sea la ecuación costo/recompensa óptima que se obtiene al seguir una política óptima a lo largo de las etapas . Sin perder generalidad, en lo que sigue consideraremos una configuración de maximización de recompensa. En la programación dinámica determinista, normalmente se trabaja con ecuaciones funcionales que adoptan la siguiente estructura: ${\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})\}}$

donde y la condición de contorno del sistema es ${\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})\}.}$

El objetivo es determinar el conjunto de acciones óptimas que maximizan . Dado el estado actual y la acción actual , sabemos con certeza la recompensa asegurada durante la etapa actual y, gracias a la función de transición de estado , el estado futuro hacia el que transita el sistema. ${\displaystyle f_{1}(s_{1})}$ ${\displaystyle s_{t}}$ ${\displaystyle x_{t}}$ ${\displaystyle g_{t}}$

En la práctica, sin embargo, incluso si conocemos el estado del sistema al comienzo de la etapa actual, así como la decisión tomada, el estado del sistema al comienzo de la etapa siguiente y la recompensa del período actual son a menudo variables aleatorias que solo se pueden observar al final de la etapa actual.

La programación dinámica estocástica se ocupa de problemas en los que la recompensa del período actual y/o el estado del período siguiente son aleatorios, es decir, con sistemas estocásticos de múltiples etapas. El objetivo del responsable de la toma de decisiones es maximizar la recompensa esperada (descontada) durante un horizonte de planificación determinado.

En su forma más general, los programas dinámicos estocásticos tratan con ecuaciones funcionales que toman la siguiente estructura

${\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\}}$

dónde

• ${\displaystyle f_{t}(s_{t})}$es la recompensa máxima esperada que se puede obtener durante las etapas , dado el estado al inicio de la etapa ; ${\displaystyle t,t+1,\ldots ,n}$ ${\displaystyle s_{t}}$ ${\displaystyle t}$
• ${\displaystyle x_{t}}$pertenece al conjunto de acciones factibles en una etapa dada del estado inicial ; ${\displaystyle X_{t}(s_{t})}$ ${\displaystyle t}$ ${\displaystyle s_{t}}$
• ${\displaystyle \alpha }$es el factor de descuento ;
• ${\displaystyle \Pr(s_{t+1}\mid s_{t},x_{t})}$es la probabilidad condicional de que el estado al final de la etapa tenga el estado actual y la acción seleccionada . ${\displaystyle t}$ ${\displaystyle s_{t+1}}$ ${\displaystyle s_{t}}$ ${\displaystyle x_{t}}$

Los procesos de decisión de Markov representan una clase especial de programas dinámicos estocásticos en los que el proceso estocástico subyacente es un proceso estacionario que presenta la propiedad de Markov .

El juego de azar como programa dinámico estocástico

El juego de apuestas se puede formular como un programa dinámico estocástico de la siguiente manera: hay juegos (es decir, etapas ) en el horizonte de planificación ${\displaystyle n=4}$

• el estado en el periodo representa la riqueza inicial al comienzo del periodo ; ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$
• La acción dada en el estado del período es el monto de la apuesta ; ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle b}$
• La probabilidad de transición de un estado a otro cuando se realiza una acción en el estado se deriva fácilmente de la probabilidad de ganar (0,4) o perder (0,6) un juego. ${\displaystyle p_{i,j}^{a}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle a}$ ${\displaystyle i}$

Sea la probabilidad de que, al final del juego 4, el jugador tenga al menos $6, dado que tenía $ al comienzo del juego . ${\displaystyle f_{t}(s)}$ ${\displaystyle s}$ ${\displaystyle t}$

• El beneficio inmediato que se obtiene si se toma una acción en el estado viene dado por el valor esperado . ${\displaystyle b}$ ${\displaystyle s}$ ${\displaystyle p_{t}(s,b)=0.4f_{t+1}(s+b)+0.6f_{t+1}(s-b)}$

Para derivar la ecuación funcional , defina como una apuesta que alcanza , entonces al comienzo del juego ${\displaystyle b_{t}(s)}$ ${\displaystyle f_{t}(s)}$ ${\displaystyle t=4}$

• si es imposible alcanzar el objetivo, es decir para ; ${\displaystyle s<3}$ ${\displaystyle f_{4}(s)=0}$ ${\displaystyle s<3}$
• si se alcanza el objetivo, es decir para ; ${\displaystyle s\geq 6}$ ${\displaystyle f_{4}(s)=1}$ ${\displaystyle s\geq 6}$
• si el jugador debe apostar lo suficiente para alcanzar el objetivo, es decir , . ${\displaystyle 3\leq s\leq 5}$ ${\displaystyle f_{4}(s)=0.4}$ ${\displaystyle 3\leq s\leq 5}$

Para la ecuación funcional es , donde varía en ; el objetivo es encontrar . ${\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)}$

Dada la ecuación funcional, se puede obtener una política de apuestas óptima mediante algoritmos de recursión hacia adelante o hacia atrás, como se describe a continuación.

Métodos de solución

Los programas dinámicos estocásticos se pueden resolver de manera óptima mediante algoritmos de recursión hacia atrás o hacia adelante. La memorización se emplea normalmente para mejorar el rendimiento. Sin embargo, al igual que la programación dinámica determinista, su variante estocástica también sufre la maldición de la dimensionalidad . Por este motivo, los métodos de solución aproximada se emplean normalmente en aplicaciones prácticas.

Recursión hacia atrás

Dado un espacio de estados acotado, la recursión hacia atrás (Bertsekas 2000) comienza tabulando para cada estado posible perteneciente a la etapa final . Una vez que estos valores se tabulan, junto con las acciones dependientes del estado óptimas asociadas , es posible pasar a la etapa y tabular para todos los estados posibles pertenecientes a la etapa . El proceso continúa considerando de manera regresiva todas las etapas restantes hasta la primera. Una vez que se completa este proceso de tabulación, el valor de una política óptima dado el estado inicial , así como la acción óptima asociada , se pueden recuperar fácilmente de la tabla. Dado que el cálculo se realiza de manera regresiva, está claro que la recursión hacia atrás puede conducir al cálculo de una gran cantidad de estados que no son necesarios para el cálculo de . ${\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)}$

Ejemplo: Juego de apuestas

Recursión hacia adelante

Dado el estado inicial del sistema al comienzo del período 1, la recursión hacia adelante (Bertsekas 2000) calcula expandiendo progresivamente la ecuación funcional ( paso hacia adelante ). Esto implica llamadas recursivas para todo lo que es necesario para calcular un determinado . El valor de una política óptima y su estructura se recuperan luego a través de un ( paso hacia atrás ) en el que se resuelven estas llamadas recursivas suspendidas. Una diferencia clave con la recursión hacia atrás es el hecho de que se calcula solo para los estados que son relevantes para el cálculo de . La memorización se emplea para evitar el recálculo de estados que ya se han considerado. ${\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)}$

Ejemplo: Juego de apuestas

Ilustraremos la recursión hacia adelante en el contexto de la instancia del juego de apuestas discutida anteriormente. Comenzamos el pase hacia adelante considerando ${\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.}$

En este punto, aún no hemos calculado los elementos necesarios para calcularlos ; procedemos a calcularlos. Tenga en cuenta que , por lo tanto, se puede aprovechar la memorización y realizar los cálculos necesarios solo una vez. ${\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)}$

Cálculo de ${\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.}$

Ya hemos calculado todo lo necesario para calcular . Sin embargo, esto ha dado lugar a recursiones suspendidas adicionales que involucran . Procedemos y calculamos estos valores. ${\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)}$

Cálculo de ${\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.}$

Dado que la etapa 4 es la última etapa de nuestro sistema, representamos condiciones de contorno que se calculan fácilmente de la siguiente manera. ${\displaystyle f_{4}(\cdot )}$

Condiciones de contorno

${\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}}}$

En este punto es posible proceder y recuperar la política óptima y su valor a través de un pase hacia atrás que involucra, en primer lugar, la etapa 3.

Pase hacia atrás que involucra ${\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.}$

y luego, la etapa 2.

Pase hacia atrás que involucra ${\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.}$

Por fin recuperamos el valor de una política óptima ${\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.}$

Esta es la política óptima que se ha ilustrado anteriormente. Nótese que existen múltiples políticas óptimas que conducen al mismo valor óptimo ; por ejemplo, en el primer juego se puede apostar $1 o $2. ${\displaystyle f_{1}(2)=0.1984}$

Implementación en Python. La siguiente es una implementación completa en Python de este ejemplo.

desde  escribir  import  List ,  Tuple import  functoolsclase  memoize :  def  __init __ ( self ,  func ) :  self.func = func self.memoized = { } self.metodo_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 ,  clave ,  func ):  try :  devolver  cache [ clave ]  excepto  KeyError :  cache [ clave ]  =  func ()  devolver  cache [ clave ] def  reset ( self )  : self.memoized = { } self.method_cache = { }​     Clase  Estado : """el estado del problema de la ruina del jugador"""  def  __init__ ( self ,  t :  int ,  wealth :  float ): """constructor de estado  Argumentos:  t {int} --  riqueza del período de tiempo {float} -- riqueza inicial  """  self . t ,  self . wealth  =  t ,  wealth def  __eq__ ( self ,  other ):  devuelve  self . __dict__  ==  other . __dict__ def  __str __ ( self ) :  devuelve  str ( self.t ) + " " + str ( self.riqueza )​     def  __hash__ ( self ):  devuelve  hash ( str ( self ))clase  GamblersRuin :  def  __init__ (  self ,  bettingHorizon :  int ,  targetWealth :  float ,  pmf :  List [ List [ Tuple [ int ,  float ]]],  ): """El problema de la ruina del jugador  Argumentos:  bettingHorizon {int} -- horizonte de apuestas  targetWealth {float} --  función de masa de probabilidad de riqueza objetivo {List[List[Tuple[int, float]]]}  """ # inicializar las variables de instancia  self . bettingHorizon ,  self . targetWealth ,  self . pmf  =  (  bettingHorizon ,  targetWealth ,  pmf ,  )  # lambdas self.ag = lambda s : [ i para i en rango ( 0 , min ( self.targetWealth // 2 , s.wealth ) + 1 ) ] # generador de acciones self.st = lambda s , a , r : State ( s.t + 1 , s.wealth - a + a * r ) # transición de estado self.iv = ( lambda s , a , r : 1 si s.wealth - a + a * r > = self.targetWealth de lo contrario 0 ) # función de valor inmediato​​​​                                                           self . cache_actions  =  {}  # caché con pares estado/acción óptimos def  f ( self ,  riqueza :  float )  ->  float :  s  =  Estado ( 0 ,  riqueza )  return  self . _f ( s ) def  q ( self ,  t :  int ,  riqueza :  float )  -  > float :  s  =  Estado ( t ,  riqueza )  return  self.cache_actions [ str ( s ) ] @memoize  def  _f ( self ,  s :  State )  ->  float :  # Recursión hacia adelante  values  ​​=  [ suma ( [ p [ 1 ] * ( self._f ( self.st ( s , a , p [ 0 ] ) ) if s.t < self.bettingHorizon - 1 else self.iv ( s , a , p [ 0 ] ) ) # función de valor para p en self.pmf [ s.t ] ] ) # realizaciones de apuestas para a en self.ag ( s ) ] # acciones                         v  =  max ( values )  try :  self.cache_actions [ str ( s )] = self.ag ( s ) [ values.index ( v ) ] # almacena la mejor acción excepto ValueError : self.cache_actions [ str ( s )] = None print ( "Error al recuperar la mejor acción" ) return v # devuelve el costo total esperado        instancia  =  {  "bettingHorizon" :  4 ,  "targetWealth" :  6 ,  "pmf" :  [[( 0 ,  0.6 ),  ( 2 ,  0.4 )]  para  i  en  el rango ( 0 ,  4 )], } gr ,  riqueza_inicial  =  GamblersRuin ( ** instancia ),  2# f_1(x) es la probabilidad del jugador de alcanzar $targetWealth al final de bettingHorizon print ( "f_1("  +  str ( initial_wealth )  +  "): "  +  str ( gr . f ( initial_wealth )))# Recupere la acción óptima para el período 2 cuando la riqueza inicial al comienzo del período 2 es $1. t ,  initial_wealth  =  1 ,  1 print (  "b_"  +  str ( t  +  1 )  +  "("  +  str ( initial_wealth )  +  "): "  +  str ( gr . q ( t ,  initial_wealth )) )

Implementación de Java. GamblersRuin.java es una implementación independiente de Java 8 del ejemplo anterior.

Programación dinámica aproximada

Powell (2009) ofrece una introducción a la programación dinámica aproximada .

Lectura adicional

• Bellman, R. (1957), Programación dinámica , Princeton University Press, ISBN 978-0-486-42809-3Edición de bolsillo de Dover (2003).
• Ross, SM; Bimbaum, ZW; Lukacs, E. (1983), Introducción a la programación dinámica estocástica , Elsevier, ISBN 978-0-12-598420-1.
• Bertsekas, DP (2000), Programación dinámica y control óptimo (2.ª ed.), Athena Scientific, ISBN 978-1-886529-09-0. En dos volúmenes.
• Powell, WB (2009), "Lo que debe saber sobre programación dinámica aproximada", Naval Research Logistics , 56 (1): 239–249, CiteSeerX  10.1.1.150.1854 , doi :10.1002/nav.20347, S2CID  7134937

Véase también

• Portal de ciencia de sistemas
• Portal de matemáticas

• Teoría de control  – Rama de la ingeniería y las matemáticas
• Programación dinámica  – Método de optimización de problemas
• Aprendizaje por refuerzo  : campo del aprendizaje automático
• Control estocástico  – Control probabilístico óptimo
• Proceso estocástico  – Conjunto de variables aleatorias
• Programación estocástica  : marco para modelar problemas de optimización que involucran incertidumbre

Referencias

1. Este problema está adaptado de WL Winston, Investigación de operaciones: aplicaciones y algoritmos (7.ª edición), Duxbury Press, 2003, capítulo 19, ejemplo 3.