Hispanopedia Wiki
Articulo de referencia

Programación dinámica estocástica

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 decisione...

Hispanopedia WikiContenido en espanolLectura gratuita

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 ecuación de Bellman . [ 1 ] El objetivo es calcular una política que defina cómo actuar de manera óptima ante la incertidumbre.

Un ejemplo motivador: Los juegos de azar

Una jugadora tiene $2, se le permite jugar un juego de azar 4 veces y su objetivo es maximizar su probabilidad de terminar con al menos $6. Si la jugadora apuesta $b{\displaystyle b}En una jugada del juego, entonces con una probabilidad de 0.4 gana el juego, recupera la apuesta inicial y aumenta su capital en $b{\displaystyle b}; con una probabilidad de 0,6, pierde la cantidad apostada $b{\displaystyle b}; 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. [ 2 ]

La programación dinámica estocástica puede emplearse para modelar este problema y determinar una estrategia de apuestas que, por ejemplo, maximice la probabilidad de que el jugador alcance una riqueza de al menos 6 dólares al final del horizonte de apuestas.

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

Estrategia de apuestas óptima.
Una estrategia de apuestas óptima que maximiza la probabilidad de que el jugador alcance una riqueza de al menos 6 dólares al final del horizonte de apuestas;bt($incógnita){\displaystyle b_{t}(\$x)}representa el monto de la apuesta para el juegot{\displaystyle t}cuando el jugador tiene $incógnita{\displaystyle x}al comienzo de esa obra. Si quien toma la decisión sigue esta política, con una probabilidad de 0,1984 alcanzará una riqueza de al menos 6 dólares.

Antecedentes formales

Consideremos un sistema discreto definido ennorte{\displaystyle n}etapas en las que cada etapat=1,…,norte{\displaystyle t=1,\ldots ,n}se caracteriza por

  • un estado inicialst∈St{\displaystyle s_{t}\in S_{t}}, dóndeSt{\displaystyle S_{t}}es el conjunto de estados factibles al comienzo de la etapat{\displaystyle t};
  • una variable de decisiónincógnitat∈incógnitat{\displaystyle x_{t}\in X_{t}}, dóndeincógnitat{\displaystyle X_{t}}es el conjunto de acciones factibles en la etapat{\displaystyle t}- tenga en cuenta queincógnitat{\displaystyle X_{t}}puede ser una función del estado inicialst{\displaystyle s_{t}};
  • una función de costo/recompensa inmediatapagt(st,incógnitat){\displaystyle p_{t}(s_{t},x_{t})}, que representa el costo/recompensa en la etapat{\displaystyle t}sist{\displaystyle s_{t}}es el estado inicial yincógnitat{\displaystyle x_{t}}la acción seleccionada;
  • una función de transición de estadogramot(st,incógnitat){\displaystyle g_{t}(s_{t},x_{t})}que lleva al sistema hacia el estadost+1=gramot(st,incógnitat){\displaystyle s_{t+1}=g_{t}(s_{t},x_{t})}.

DejarFt(st){\displaystyle f_{t}(s_{t})}representan el costo/recompensa óptimo obtenido al seguir una política óptima a lo largo de las etapast,t+1,…,norte{\displaystyle t,t+1,\ldots ,n}Sin pérdida de generalidad , a continuación consideraremos un escenario de maximización de recompensas. En la programación dinámica determinista , se suele trabajar con ecuaciones funcionales que adoptan la siguiente estructura.

Ft(st)=máximoincógnitat∈incógnitat{pagt(st,incógnitat)+Ft+1(st+1)}{\displaystyle f_{t}(s_{t})=\max _{x_{t}\in X_{t}}\{p_{t}(s_{t},x_{t})+f_{t+1}(s_{t+1})\}}

dóndest+1=gramot(st,incógnitat){\displaystyle s_{t+1}=g_{t}(s_{t},x_{t})}y la condición de contorno del sistema es

Fnorte(snorte)=máximoincógnitanorte∈incógnitanorte{pagnorte(snorte,incógnitanorte)}.{\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 maximicenF1(s1){\displaystyle f_{1}(s_{1})}Dado el estado actualst{\displaystyle s_{t}}y la acción actualincógnitat{\displaystyle x_{t}}, conocemos con certeza la recompensa asegurada durante la etapa actual y – gracias a la función de transición de estadogramot{\displaystyle g_{t}}– el estado futuro hacia el cual transita el sistema.

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 siguiente etapa y la recompensa del período actual suelen ser variables aleatorias que solo se pueden observar al final de la etapa actual.

La programación dinámica estocástica aborda problemas en los que la recompensa del período actual y/o el estado del siguiente período son aleatorios, es decir, sistemas estocásticos multietapa. 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.

Ft(st)=máximoincógnitat∈incógnitat(st){(recompensa esperada durante la etapa t∣st,incógnitat)+α∑st+1Pr(st+1∣st,incógnitat)Ft+1(st+1)}{\displaystyle f_{t}(s_{t})=\max _{x_{t}\in X_{t}(s_{t})}\left\{({\text{recompensa esperada durante la etapa }}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

  • Ft(st){\displaystyle f_{t}(s_{t})}es la recompensa máxima esperada que se puede obtener durante las etapast,t+1,…,norte{\displaystyle t,t+1,\ldots ,n}, dado el estadost{\displaystyle s_{t}}al comienzo de la etapat{\displaystyle t};
  • incógnitat{\displaystyle x_{t}}pertenece al conjuntoincógnitat(st){\displaystyle X_{t}(s_{t})}de acciones factibles en la etapat{\displaystyle t}dado el estado inicialst{\displaystyle s_{t}};
  • α{\displaystyle \alpha }es el factor de descuento ;
  • Pr(st+1∣st,incógnitat){\displaystyle \Pr(s_{t+1}\mid s_{t},x_{t})}es la probabilidad condicional de que el estado al final de la etapat{\displaystyle t}esst+1{\displaystyle s_{t+1}}dado el estado actualst{\displaystyle s_{t}}y acción seleccionadaincógnitat{\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 tiene transiciones de estado que satisfacen la propiedad de Markov .

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

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

  • el estados{\displaystyle s}en períodot{\displaystyle t}representa la riqueza inicial al comienzo del períodot{\displaystyle t};
  • la acción dada estados{\displaystyle s}en períodot{\displaystyle t}es la cantidad de la apuestab{\displaystyle b};
  • la probabilidad de transiciónpagi,ja{\displaystyle p_{i,j}^{a}}del estadoi{\displaystyle i}para declararj{\displaystyle j}cuando la accióna{\displaystyle a}se toma en el estadoi{\displaystyle i}se deriva fácilmente de la probabilidad de ganar (0,4) o perder (0,6) un juego.

DejarFt(s){\displaystyle f_{t}(s)}Sea la probabilidad de que, al final del juego 4, la jugadora tenga al menos $6, dado que tiene $s{\displaystyle s}al comienzo del juegot{\displaystyle t}.

  • el beneficio inmediato incurrido si se actúab{\displaystyle b}se toma en el estados{\displaystyle s}viene dado por el valor esperadopagt(s,b)=0,4Ft+1(s+b)+0,6Ft+1(s−b){\displaystyle p_{t}(s,b)=0.4f_{t+1}(s+b)+0.6f_{t+1}(sb)}.

Para derivar la ecuación funcional , definabt(s){\displaystyle b_{t}(s)}como una apuesta que alcanzaFt(s){\displaystyle f_{t}(s)}, luego al comienzo del juegot=4{\displaystyle t=4}

  • sis<3{\displaystyle s<3}es imposible alcanzar la meta, es decirF4(s)=0{\displaystyle f_{4}(s)=0}paras<3{\displaystyle s<3};
  • sis≥6{\displaystyle s\geq 6}El objetivo se alcanza, es decirF4(s)=1{\displaystyle f_{4}(s)=1}paras≥6{\displaystyle s\geq 6};
  • si3≤s≤5{\displaystyle 3\leq s\leq 5}el jugador debe apostar lo suficiente para alcanzar el objetivo, es decirF4(s)=0,4{\displaystyle f_{4}(s)=0.4}para3≤s≤5{\displaystyle 3\leq s\leq 5}.

Parat<4{\displaystyle t<4}La ecuación funcional esFt(s)=máximobt(s){0,4Ft+1(s+b)+0,6Ft+1(s−b)}{\displaystyle f_{t}(s)=\max _{b_{t}(s)}\{0.4f_{t+1}(s+b)+0.6f_{t+1}(s-b)\}}, dóndebt(s){\displaystyle b_{t}(s)}rangos en0,...,s{\displaystyle 0,...,s}; el objetivo es encontrarF1(2){\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 pueden resolverse de forma óptima mediante algoritmos de recursión hacia atrás o hacia adelante . La memorización se utiliza habitualmente 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, en aplicaciones prácticas se suelen emplear métodos de solución aproximada .

Recursión hacia atrás

Dado un espacio de estados acotado, la recursión hacia atrás ( Bertsekas 2000 ) comienza tabulandoFnorte(k){\displaystyle f_{n}(k)}para cada estado posiblek{\displaystyle k}perteneciente a la etapa finalnorte{\displaystyle n}Una vez tabulados estos valores, junto con las acciones óptimas dependientes del estado asociadasincógnitanorte(k){\displaystyle x_{n}(k)}, es posible pasar a la etapanorte−1{\displaystyle n-1}y tabularFnorte−1(k){\displaystyle f_{n-1}(k)}para todos los estados posibles pertenecientes a la etapanorte−1{\displaystyle n-1}. El proceso continúa considerando de forma regresiva todas las etapas restantes hasta la primera. Una vez que se completa este proceso de tabulación,F1(s){\displaystyle f_{1}(s)}– el valor de una política óptima dado el estado inicials{\displaystyle s}– así como la acción óptima asociadaincógnita1(s){\displaystyle x_{1}(s)}se puede recuperar fácilmente de la tabla. Dado que el cálculo procede de forma inversa, es evidente que la recursión hacia atrás puede llevar al cálculo de un gran número de estados que no son necesarios para el cálculo deF1(s){\displaystyle f_{1}(s)}.

Ejemplo: Juego de azar

Recursión hacia adelante

Dado el estado inicials{\displaystyle s}del sistema al comienzo del período 1, la recursión hacia adelante ( Bertsekas 2000 ) calculaF1(s){\displaystyle f_{1}(s)}mediante la expansión progresiva de la ecuación funcional ( paso hacia adelante ). Esto implica llamadas recursivas para todosFt+1(⋅),Ft+2(⋅),…{\displaystyle f_{t+1}(\cdot ),f_{t+2}(\cdot ),\ldots }que son necesarios para calcular un valor dadoFt(⋅){\displaystyle f_{t}(\cdot )}El valor de una política óptima y su estructura se recuperan 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 queFt{\displaystyle f_{t}}se calcula únicamente para los estados que son relevantes para el cálculo deF1(s){\displaystyle f_{1}(s)}La memorización se emplea para evitar el recálculo de estados que ya han sido considerados.

Ejemplo: Juego de azar

Ilustraremos la recursión hacia adelante en el contexto del ejemplo del juego de azar que se discutió anteriormente. Comenzamos el paso hacia adelante considerando F1(2)=min{bProbabilidad de éxito en los periodos 1, 2, 3 y 400,4F2(2+0)+0,6F2(2−0)10,4F2(2+1)+0,6F2(2−1)20,4F2(2+2)+0,6F2(2−2){\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 calculadoF2(4),F2(3),F2(2),F2(1),F2(0){\displaystyle f_{2}(4),f_{2}(3),f_{2}(2),f_{2}(1),f_{2}(0)}, que son necesarios para calcularF1(2){\displaystyle f_{1}(2)}; procedemos y calculamos estos elementos. Tenga en cuenta queF2(2+0)=F2(2−0)=F2(2){\displaystyle f_{2}(2+0)=f_{2}(2-0)=f_{2}(2)}Por lo tanto, se puede aprovechar la memorización y realizar los cálculos necesarios una sola vez.

Cálculo deF2(4),F2(3),F2(2),F2(1),F2(0){\displaystyle f_{2}(4),f_{2}(3),f_{2}(2),f_{2}(1),f_{2}(0)}

F2(0)=min{bProbabilidad de éxito en los periodos 2, 3 y 400,4F3(0+0)+0,6F3(0−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.}

F2(1)=min{bProbabilidad de éxito en los periodos 2, 3 y 400,4F3(1+0)+0,6F3(1−0)10,4F3(1+1)+0,6F3(1−1){\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.}

F2(2)=min{bProbabilidad de éxito en los periodos 2, 3 y 400,4F3(2+0)+0,6F3(2−0)10,4F3(2+1)+0,6F3(2−1)20,4F3(2+2)+0,6F3(2−2){\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.}

F2(3)=min{bProbabilidad de éxito en los periodos 2, 3 y 400,4F3(3+0)+0,6F3(3−0)10,4F3(3+1)+0,6F3(3−1)20,4F3(3+2)+0,6F3(3−2)30,4F3(3+3)+0,6F3(3−3){\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.}

F2(4)=min{bProbabilidad de éxito en los periodos 2, 3 y 400,4F3(4+0)+0,6F3(4−0)10,4F3(4+1)+0,6F3(4−1)20,4F3(4+2)+0,6F3(4−2){\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.}

Ahora hemos calculadoF2(k){\displaystyle f_{2}(k)}a pesar dek{\displaystyle k}que se necesitan para calcularF1(2){\displaystyle f_{1}(2)}Sin embargo, esto ha dado lugar a recursiones suspendidas adicionales que involucranF3(4),F3(3),F3(2),F3(1),F3(0){\displaystyle f_{3}(4),f_{3}(3),f_{3}(2),f_{3}(1),f_{3}(0)}. Procedemos a calcular estos valores.

Cálculo deF3(4),F3(3),F3(2),F3(1),F3(0){\displaystyle f_{3}(4),f_{3}(3),f_{3}(2),f_{3}(1),f_{3}(0)}

F3(0)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4F4(0+0)+0,6F4(0−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.}

F3(1)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4F4(1+0)+0,6F4(1−0)10,4F4(1+1)+0,6F4(1−1){\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.}

F3(2)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4F4(2+0)+0,6F4(2−0)10,4F4(2+1)+0,6F4(2−1)20,4F4(2+2)+0,6F4(2−2){\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.}

F3(3)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4F4(3+0)+0,6F4(3−0)10,4F4(3+1)+0,6F4(3−1)20,4F4(3+2)+0,6F4(3−2)30,4F4(3+3)+0,6F4(3−3){\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.}

F3(4)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4F4(4+0)+0,6F4(4−0)10,4F4(4+1)+0,6F4(4−1)20,4F4(4+2)+0,6F4(4−2){\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.}

F3(5)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4F4(5+0)+0,6F4(5−0)10,4F4(5+1)+0,6F4(5−1){\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,F4(⋅){\displaystyle f_{4}(\cdot )}representan condiciones de contorno que se calculan fácilmente de la siguiente manera.

Condiciones de contorno

F4(0)=0b4(0)=0F4(1)=0b4(1)={0,1}F4(2)=0b4(2)={0,1,2}F4(3)=0,4b4(3)={3}F4(4)=0,4b4(4)={2,3,4}F4(5)=0,4b4(5)={1,2,3,4,5}F4(d)=1b4(d)={0,…,d−6} para d≥6{\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 mediante un paso hacia atrás que involucra, en primer lugar, la etapa 3.

Paso hacia atrás que implicaF3(⋅){\displaystyle f_{3}(\cdot )}

F3(0)=min{bProbabilidad de éxito en los periodos 3 y 4.00,4(0)+0,6(0)=0{\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.}

F3(1)=min{bProbabilidad de éxito en los periodos 3 y 4.máximo00,4(0)+0,6(0)=0←b3(1)=010,4(0)+0,6(0)=0←b3(1)=1{\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.}

F3(2)=min{bProbabilidad de éxito en los periodos 3 y 4.máximo00,4(0)+0,6(0)=010,4(0,4)+0,6(0)=0,16←b3(2)=120,4(0,4)+0,6(0)=0,16←b3(2)=2{\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.}

F3(3)=min{bProbabilidad de éxito en los periodos 3 y 4.máximo00,4(0,4)+0,6(0,4)=0,4←b3(3)=010,4(0,4)+0,6(0)=0,1620,4(0,4)+0,6(0)=0,1630,4(1)+0,6(0)=0,4←b3(3)=3{\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.}

F3(4)=min{bProbabilidad de éxito en los periodos 3 y 4.máximo00,4(0,4)+0,6(0,4)=0,4←b3(4)=010,4(0,4)+0,6(0,4)=0,4←b3(4)=120,4(1)+0,6(0)=0,4←b3(4)=2{\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.}

F3(5)=min{bProbabilidad de éxito en los periodos 3 y 4.máximo00,4(0,4)+0,6(0,4)=0,410,4(1)+0,6(0,4)=0,64←b3(5)=1{\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.

Paso hacia atrás que implicaF2(⋅){\displaystyle f_{2}(\cdot )}

F2(0)=min{bProbabilidad de éxito en los periodos 2, 3 y 4máximo00,4(0)+0,6(0)=0←b2(0)=0{\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.}

F2(1)=min{bProbabilidad de éxito en los periodos 2, 3 y 4máximo00,4(0)+0,6(0)=010,4(0,16)+0,6(0)=0,064←b2(1)=1{\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.}

F2(2)=min{bProbabilidad de éxito en los periodos 2, 3 y 4máximo00,4(0,16)+0,6(0,16)=0,16←b2(2)=010,4(0,4)+0,6(0)=0,16←b2(2)=120,4(0,4)+0,6(0)=0,16←b2(2)=2{\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.}

F2(3)=min{bProbabilidad de éxito en los periodos 2, 3 y 4máximo00,4(0,4)+0,6(0,4)=0,4←b2(3)=010,4(0,4)+0,6(0,16)=0,25620,4(0,64)+0,6(0)=0,25630,4(1)+0,6(0)=0,4←b2(3)=3{\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.}

F2(4)=min{bProbabilidad de éxito en los periodos 2, 3 y 4máximo00,4(0,4)+0,6(0,4)=0,410,4(0,64)+0,6(0,4)=0,496←b2(4)=120,4(1)+0,6(0,16)=0,496←b2(4)=2{\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.}

Finalmente recuperamos el valorF1(2){\displaystyle f_{1}(2)}de una política óptima

F1(2)=min{bProbabilidad de éxito en los periodos 1, 2, 3 y 4máximo00,4(0,16)+0,6(0,16)=0,1610,4(0,4)+0,6(0,064)=0,1984←b1(2)=120,4(0,496)+0,6(0)=0,1984←b1(2)=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 previamente. Nótese que existen múltiples políticas óptimas que conducen al mismo valor óptimo.F1(2)=0,1984{\displaystyle f_{1}(2)=0.1984}; por ejemplo, en el primer juego se puede apostar 1 dólar o 2 dólares.

Implementación en Python. A continuación se muestra una implementación completa en Python de este ejemplo.

importar functoolsclase 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 = { }​Clase Estado : """El estado del problema de la ruina del jugador"""def __init__ ( self , t : int , wealth : float ): """constructor de estado Argumentos:  t {int} -- período de tiempo  wealth {float} -- riqueza inicial  """ self . t , self . wealth = t , wealthdef __eq__ ( self , other ): return self . __dict__ == other . __dict__def __str__ ( self ): return str ( self . t ) + " " + str ( self . wealth )def __hash__ ( self ): return 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} -- riqueza objetivo  pmf {list[list[tuple[int, float]]]} -- función de masa de probabilidad  """# inicializar variables de instancia self . bettingHorizon , self . targetWealth , self . pmf = ( bettingHorizon , targetWealth , pmf , )# lambdas self.ag = lambda s : [ i for i in range ( 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 if s.wealth - a + a * r > = self.targetWealth else 0 ) # función de valor inmediato​​​​​​self.cache_actions = {} # caché con pares óptimos de estado/ accióndef 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 : Estado ) -> float : # Recursión hacia adelante values ​​= [ sum ([ 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 for p in self . pmf [ s . t ]]) # realizaciones de apuestas for a in self . ag ( s )] # acciones v = max ( valores ) try : self.cache_actions [ str ( s )] = self.ag ( s )[ valores.index ( v ) ] # almacenar la mejor acción except ValueError : self.cache_actions [ str ( s ) ] = None print ( " Error al recuperar la mejor acción " ) return v # devolver el costo total esperadoinstancia = { "horizonte de apuestas" : 4 , "riqueza objetivo" : 6 , "pmf" : [[( 0 , 0.6 ), ( 2 , 0.4 )] para i en rango ( 0 , 4 )], } gr , riqueza_inicial = Ruina de los jugadores ( ** 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 )))# Recuperar la acción óptima para el período 2 cuando la riqueza inicial al comienzo del período 2 es de $1. t , initial_wealth = 1 , 1 print ( "b_" + str ( t + 1 ) + "(" + str ( initial_wealth ) + "): " + str ( gr . q ( t , initial_wealth )) )

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

Programación dinámica aproximada

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

Fuentes

  • Bellman, R. (1957), Programación dinámica , Princeton University Press, ISBN 978-0-486-42809-3{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda ) . Edición de bolsillo de Dover (2003)
  • Bertsekas, DP (2000), Programación dinámica y control óptimo (2.ª  ed.), Athena Scientific, ISBN 978-1-886529-09-0En dos volúmenes.
  • Powell, WB (2009), "Lo que debe saber sobre la 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  

Lecturas adicionales

  • Ross, SM; Bimbaum, ZW; Lukacs, E. (1983), Introducción a la programación dinámica estocástica , Elsevier, ISBN 978-0-12-598420-1.

Véase también

Referencias

  1. ↑ Füllner, Christian; Rebennack, Steffen (2025-08-07). "Programación dinámica dual estocástica y sus variantes: una revisión" . SIAM Review . 67 (3): 415– 539. doi : 10.1137/23M1575093 . ISSN 0036-1445 . 
  2. ↑ Este problema está adaptado de WL Winston, Operations Research: Applications and Algorithms (7.ª edición), Duxbury Press, 2003, cap. 19, ejemplo 3.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Stochastic_dynamic_programming&oldid=1346862997 "
Lecturas relacionadas
6 articulos
Richard E. BellmanRichard E. BellmanRichard Ernest Bellman [2] (26 de agosto de 1920 – 19 de marzo de 1984) fue un matemático aplicado estadounidense , que introdujo la programación d..."El juicio de Paris" de Wagrez: Paris, vestido con librea medieval y sosteniendo la manzana de la discordia, conversa con Atenea, Afrodita y Hera.Teoría de la decisiónEl juicio mitológico de Paris requirió seleccionar entre tres alternativas incomparables (las diosas mostradas). La teoría de la decisión o teoría ...{\displaystyle \min_{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}Programación estocásticaEn el campo de la optimización matemática , la programación estocástica es un marco para modelar problemas de optimización que involucran incertidu...Programación dinámicaProgramación dinámicaLa programación dinámica es a la vez un método de optimización matemática y un paradigma algorítmico . El método fue desarrollado por Richard Bellm...Ecuación de BellmanEcuación de BellmanUna ecuación de Bellman , llamada así en honor a Richard E. Bellman , es una condición necesaria para la optimalidad asociada con el método de opti...Decisión óptimaDecisión óptimaUna decisión óptima es una decisión que conduce a un resultado conocido o esperado al menos tan bueno como todas las demás opciones de decisión dis...