Considere un sistema discreto definido en etapas en las que cada etapa Es caracterizado por
- un estado inicial , dónde es el conjunto de estados factibles al comienzo de la etapa ;
- una variable de decisión , dónde es el conjunto de acciones factibles en la etapa - tenga en cuenta que puede ser una función del estado inicial ;
- 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;
- una función de transición de estado que lleva al sistema hacia el estado .
Dejar representar el costo / recompensa óptimo obtenido al seguir una política óptima en etapas. Sin pérdida de generalidad en lo que sigue, consideraremos un escenario de maximización de recompensas. En la programación dinámica determinista , uno suele tratar con ecuaciones funcionales que adoptan la siguiente estructura
dónde y la condición de frontera del sistema es
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 obtenida durante la etapa actual y, gracias a la función de transición de estado - el estado futuro hacia el que 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 etapa siguiente y la recompensa del período actual son a menudo variables aleatorias que solo se puede 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 varias etapas. El objetivo del tomador de decisiones es maximizar la recompensa esperada (descontada) durante un horizonte de planificación dado.
En su forma más general, los programas dinámicos estocásticos tratan con ecuaciones funcionales tomando la siguiente estructura
dónde
- es la recompensa máxima esperada que se puede obtener durante las etapas , estado dado al comienzo de la etapa ;
- pertenece al conjunto de acciones factibles en etapa dado el estado inicial ;
- es el factor de descuento ;
- es la probabilidad condicional de que el estado al comienzo de la etapa es dado el estado actual y acción seleccionada .
El proceso de decisión de Markov representa 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
- el estado en período representa la riqueza inicial al comienzo del período ;
- la acción dada el estado en período es el monto de la apuesta ;
- la probabilidad de transición del estado a estado cuando la acción se toma en estado se deriva fácilmente de la probabilidad de ganar (0,4) o perder (0,6) un juego.
Dejar será la probabilidad de que, al final del juego 4, el jugador tenga al menos $ 6, dado que tiene $ al comienzo del juego .
- el beneficio inmediato incurrido si la acción se toma en estado viene dado por el valor esperado .
Para derivar la ecuación funcional , defina como una apuesta que logra , luego al comienzo del juego
- Si es imposible alcanzar la meta, es decir por ;
- Si se alcanza la meta, es decir por ;
- Si el jugador debe apostar lo suficiente para alcanzar el objetivo, es decir por .
Para la ecuación funcional es , dónde rangos en ; el objetivo es encontrar.
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.
Los programas dinámicos estocásticos se pueden resolver de manera óptima mediante el uso de algoritmos de recursividad 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, también su variante estocástica sufre la maldición de la dimensionalidad . Por esta razón , los métodos de solución aproximada se emplean típicamente en aplicaciones prácticas.
Recursividad hacia atrás
Dado un espacio de estado limitado, la recursividad 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 óptimas dependientes del estado asociadas, es posible pasar al escenario y tabular para todos los estados posibles pertenecientes al escenario . El proceso continúa considerando al revés todas las etapas restantes hasta la primera. Una vez que se complete este proceso de tabulación, - el valor de una política óptima dado el estado inicial - así como la acción óptima asociada se puede recuperar fácilmente de la mesa. Dado que el cálculo avanza hacia atrás, está claro que la recursividad hacia atrás puede conducir al cálculo de un gran número de estados que no son necesarios para el cálculo de.
Ejemplo: juego de apuestas
Recursión hacia adelante
Dado el estado inicial del sistema al comienzo del período 1, la recursividad hacia adelante ( Bertsekas 2000 ) calculaampliando progresivamente la ecuación funcional ( pase directo ). Esto implica llamadas recursivas para todos. que son necesarios para calcular un determinado . El valor de una política óptima y su estructura se recuperan a través de un ( pase hacia atrás ) en el que se resuelven estas llamadas recursivas suspendidas. Una diferencia clave con la recursividad 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 volver a calcular los estados que ya se han considerado.
Ejemplo: juego de apuestas
Ilustraremos la recursividad hacia adelante en el contexto de la instancia de juego de Apuestas discutida anteriormente. Comenzamos el pase hacia adelante considerando
En este punto aún no hemos calculado , que son necesarios para calcular ; procedemos y calculamos estos elementos. Tenga en cuenta que, por lo tanto, se puede aprovechar la memorización y realizar los cálculos necesarios solo una vez.
- Computación de
Ahora hemos calculado para todos que son necesarios para calcular . Sin embargo, esto ha llevado a recurrencias suspendidas adicionales que involucran. Procedemos y calculamos estos valores.
- Computación de
Dado que la etapa 4 es la última etapa de nuestro sistema, representan condiciones de contorno que se calculan fácilmente de la siguiente manera.
- Condiciones de borde
En este punto es posible proceder y recuperar la póliza óptima y su valor mediante un retroceso que involucra, en un primer momento, la etapa 3
- Pase hacia atrás que involucra
y luego la etapa 2.
- Pase hacia atrás que involucra
Finalmente recuperamos el valor de una política óptima
Esta es la política óptima que se ha ilustrado anteriormente. Tenga en cuenta que hay varias políticas óptimas que conducen al mismo valor óptimo; por ejemplo, en el primer juego se puede apostar $ 1 o $ 2.
Implementación de Python. El que sigue es una implementación Python completa de este ejemplo.
de tipificación de importación de lista , tupla importación memoize como mem importar functools clase 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__ ( funciones . parcial ( self . func , obj ))) def cache_get ( self , cache , key , func ): try : return cache [ key ] excepto KeyError : cache [ key ] = func () return cache [ key ] def reset ( self ): self . memoized = {} self . method_cache = {} Estado de clase : '' 'el estado del problema de ruina del jugador ' '' def __init__ ( self , t : int , riqueza : float ): '' 'constructor del estado Argumentos: t {int} - período de tiempo riqueza {float} - riqueza inicial ' '' self . t , yo . riqueza = t , riqueza def __eq__ ( self , other ): return self . __dict__ == otro . __dict__ def __str__ ( self ): return str ( self . t ) + "" + str ( self . riqueza ) def __hash__ ( self ): return hash ( str ( self ))clase Jugadores Ruina : def __init__ ( self , BettingHorizon : int , targetWealth : float , pmf : List [ List [ Tuple [ int , float ]]]): '' 'el problema de la ruina del jugador Argumentos: BetHorizon {int} - horizonte de apuestas targetWealth {float} - objetivo de riqueza pmf {List [List [Tuple [int, float]]]} - función de masa de probabilidad '' ' # inicializar las variables de instancia self . BettingHorizon , self . targetWealth , uno mismo . pmf = BettingHorizon , targetWealth , pmf # lambdas self . ag = lambda s : [ i para i en rango ( 0 , min ( self . targetWealth // 2 , s . riqueza ) + 1 )] # generador de acciones self . st = lambda s , a , r : Estado ( s . t + 1 , s . riqueza - a + a * r ) # estado transición self . iv = lambda s , a , r : 1 si s . riqueza - a + a * r > = yo . targetWealth else 0 # función de valor inmediato yo . cache_actions = {} # caché con pares de acción / estado óptimos def f ( yo , riqueza : flotar ) -> flotar : s = Estado ( 0 , riqueza ) retorno yo . _f ( s ) def q ( yo , t : int , riqueza : flotar ) -> flotar : s = Estado ( t , riqueza ) retorno yo . cache_actions [ str ( s )] @memoize def _f ( self , s : State ) -> float : #Recursión hacia adelante v = max ( [ sum ([ p [ 1 ] * ( self . _f ( self . st ( s , a , p [ 0 ])) if s . t < self . BettingHorizon - 1 else self . iv ( s , a , p [ 0 ])) # valor futuro para p en self . pmf [ s . t ]]) # realizaciones de variables aleatorias para a en self . ag ( s )]) # acciones opt_a = lambda a : sum ([ p [ 1 ] * ( self . _f ( self . st ( s , a , p [ 0 ])) if s . t < self . BettingHorizon - 1 else self . iv ( s , a , p [ 0 ])) para p en self . pmf [ s . t ]]) == v q = [ k para k en filtro ( opt_a , self . ag ( s ))] # recuperar la mejor lista de acciones self . cache_actions [ str ( s )] = q [ 0 ] if bool ( q ) else None # almacena una acción en el diccionario return v # valor de retornoinstancia = { "BettingHorizon" : 4 , "targetWealth" : 6 , "pmf" : [[( 0 , 0.6 ), ( 2 , 0.4 )] para i en el rango ( 0 , 4 )]} gr , initial_wealth = GamblersRuin ( ** instancia ), 2# f_1 (x) es la probabilidad del jugador de alcanzar $ targetWealth al final de la apuestaHorizon 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 sea $ 1. t , riqueza_inicial = 1 , 1 print ( "b_" + str ( t + 1 ) + "(" + str ( riqueza_inicial ) + "):" + str ( gr . q ( t , riqueza_inicial )))
Implementación de Java. GamblersRuin.java es una implementación independiente de Java 8 del ejemplo anterior.
Programación dinámica aproximada
( Powell 2009 ) proporciona una introducción a la programación dinámica aproximada .