Originalmente introduzida por Richard E. Bellman em ( Bellman 1957 ), a programação dinâmica estocástica é uma técnica para modelar e resolver problemas de tomada de decisão sob incerteza . Intimamente relacionada à programação estocástica e à programação dinâmica , a programação dinâmica estocástica representa o problema sob escrutínio na forma de uma equação de Bellman . O objetivo é calcular uma política que prescreva como agir de forma otimizada diante da incerteza.
Um exemplo motivador: jogo de azar
Um jogador tem $ 2, ele pode jogar um jogo de azar 4 vezes e seu objetivo é maximizar sua probabilidade de terminar com pelo menos $ 6. Se o apostador aposta $ em uma jogada do jogo, então com probabilidade 0,4 ele ganha o jogo, recupera a aposta inicial e aumenta sua posição de capital em $ ; com probabilidade 0,6, ela perde o valor da aposta $ ; todas as jogadas são independentes entre pares . Em qualquer jogada do jogo, o apostador não pode apostar mais dinheiro do que tem disponível no início dessa jogada.
A programação dinâmica estocástica pode ser empregada para modelar esse problema e determinar uma estratégia de aposta que, por exemplo, maximize a probabilidade do apostador de atingir uma riqueza de pelo menos $ 6 ao final do horizonte de apostas.
Observe que, se não houver limite para o número de jogos que podem ser jogados, o problema se torna uma variante do conhecido paradoxo de São Petersburgo .
Contexto formal
Considere um sistema discreto definido em estágios em que cada estágio é caracterizado por
- um estado inicial , onde é o conjunto de estados possíveis no início do estágio ;
- uma variável de decisão , onde é o conjunto de ações viáveis no estágio - observe que pode ser uma função do estado inicial ;
- uma função de custo / recompensa imediata , representando o custo / recompensa no estágio se for o estado inicial e a ação selecionada;
- uma função de transição de estado que conduz o sistema ao estado .
Deixe representar o custo / recompensa ideal obtido seguindo uma política ótima ao longo dos estágios . Sem perda de generalidade no que se segue, consideraremos uma configuração de maximização de recompensa. Na programação dinâmica determinística geralmente lida com equações funcionais tomando a seguinte estrutura
onde e a condição de limite do sistema é
O objetivo é determinar o conjunto de ações ótimas que maximizam . Dado o estado atual e a ação atual , sabemos com certeza a recompensa assegurada durante o estágio atual e - graças à função de transição de estado - o estado futuro para o qual o sistema faz a transição.
Na prática, porém, mesmo que conheçamos o estado do sistema no início do estágio atual, bem como a decisão tomada, o estado do sistema no início do próximo estágio e a recompensa do período atual são frequentemente variáveis aleatórias que pode ser observado apenas no final da fase atual.
A programação dinâmica estocástica lida com problemas em que a recompensa do período atual e / ou o estado do próximo período são aleatórios, ou seja, com sistemas estocásticos de vários estágios. O objetivo do tomador de decisão é maximizar a recompensa esperada (com desconto) ao longo de um determinado horizonte de planejamento.
Em sua forma mais geral, os programas dinâmicos estocásticos lidam com equações funcionais tomando a seguinte estrutura
Onde
-
é a recompensa máxima esperada que pode ser obtida durante os estágios , dado o estado no início do estágio ;
-
pertence ao conjunto de ações viáveis no estágio dado o estado inicial ;
-
é o fator de desconto ;
-
é a probabilidade condicional de que o estado no início de fase é dado estado actual e acção seleccionada .
O processo de decisão de Markov representa uma classe especial de programas dinâmicos estocásticos em que o processo estocástico subjacente é um processo estacionário que apresenta a propriedade de Markov .
O jogo de azar como um programa dinâmico estocástico
O jogo de azar pode ser formulado como um Programa Dinâmico Estocástico da seguinte forma: há jogos (ou seja, estágios ) no horizonte de planejamento
- o estado no período representa a riqueza inicial no início do período ;
- a ação determinada no período é o valor da aposta ;
- a probabilidade de transição de um estado para outro quando a ação é realizada no estado é facilmente derivada da probabilidade de ganhar (0,4) ou perder (0,6) um jogo.
Seja a probabilidade de que, ao final do jogo 4, o apostador tenha pelo menos $ 6, visto que ele tem $ no início do jogo .
- o lucro imediato incorrido se a ação for realizada no estado é dado pelo valor esperado .
Para derivar a equação funcional , defina como uma aposta que atinge , então, no início do jogo
- se é impossível atingir a meta, ou seja, para ;
- se a meta for atingida, ou seja, para ;
- se o jogador deve apostar o suficiente para atingir o objetivo, ou seja, para .
Pois a equação funcional é , onde varia em ; o objetivo é encontrar .
Dada a equação funcional, uma política de apostas ideal pode ser obtida por meio de algoritmos de recursão para frente ou recursão para trás, conforme descrito abaixo.
Métodos de solução
Os programas dinâmicos estocásticos podem ser resolvidos até a otimização usando algoritmos de recursão para trás ou de recursão para frente . A memorização é normalmente empregada para aprimorar o desempenho. No entanto, como a programação dinâmica determinística, também sua variante estocástica sofre da maldição da dimensionalidade . Por esta razão , métodos de solução aproximados são normalmente empregados em aplicações práticas.
Recursão para trás
Dado um espaço de estado limitado, a recursão para trás ( Bertsekas 2000 ) começa tabulando para cada estado possível pertencente ao estágio final . Uma vez que esses valores são tabulados, junto com as ações dependentes do estado ideais associadas , é possível mover para o estágio e tabular para todos os estados possíveis pertencentes ao estágio . O processo continua considerando de forma reversa todos os estágios restantes até o primeiro. Uma vez que este processo de tabulação esteja completo, - o valor de uma política ótima dado o estado inicial - assim como a ação ótima associada podem ser facilmente recuperados da tabela. Uma vez que o cálculo prossegue de forma regressiva, é claro que a recursão retroativa pode levar ao cálculo de um grande número de estados que não são necessários para o cálculo de .
Exemplo: jogo de azar
Recursão para frente
Dado o estado inicial do sistema no início do período 1, a recursão direta ( Bertsekas 2000 ) calcula expandindo progressivamente a equação funcional ( passagem para a frente ). Isso envolve chamadas recursivas para tudo o que é necessário para calcular um dado . O valor de uma política ótima e sua estrutura são recuperados por meio de uma ( passagem para trás ) na qual essas chamadas recursivas suspensas são resolvidas. Uma diferença importante da recursão para trás é o fato de que é calculado apenas para estados que são relevantes para o cálculo de . Memoização é empregada para evitar recomputação de estados que já foram considerados.
Exemplo: jogo de azar
Devemos ilustrar a recursão direta no contexto da instância do jogo Gambling discutida anteriormente. Começamos o passe para frente considerando
Neste ponto, ainda não calculamos , o que é necessário para calcular ; procedemos e calculamos esses itens. Observe que , portanto, pode-se alavancar a memoização e realizar os cálculos necessários apenas uma vez.
- Cálculo de
Agora calculamos tudo o que é necessário para calcular . No entanto, isso levou a recursões adicionais suspensas envolvendo . Prosseguimos e calculamos esses valores.
- Cálculo de
Como o estágio 4 é o último estágio em nosso sistema, represente as condições de contorno que são facilmente calculadas como segue.
- Condições de limite
Nesse ponto, é possível prosseguir e recuperar a política ótima e seu valor por meio de um retrocesso envolvendo, em primeiro lugar, o estágio 3
- Passe para trás envolvendo
e, então, o estágio 2.
- Passe para trás envolvendo
Finalmente recuperamos o valor de uma política ótima
Esta é a política ideal que foi ilustrada anteriormente. Observe que existem várias políticas ideais que conduzem ao mesmo valor ideal ; por exemplo, no primeiro jogo pode-se apostar $ 1 ou $ 2.
Implementação de Python. O que se segue é uma implementação Python completa deste exemplo.
from typing import List, Tuple
import memoize as mem
import functools
class 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 = {}
class State:
'''the state of the gambler's ruin problem
'''
def __init__(self, t: int, wealth: float):
'''state constructor
Arguments:
t {int} -- time period
wealth {float} -- initial 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.wealth)
def __hash__(self):
return hash(str(self))
class GamblersRuin:
def __init__(self, bettingHorizon:int, targetWealth: float, pmf: List[List[Tuple[int, float]]]):
'''the gambler's ruin problem
Arguments:
bettingHorizon {int} -- betting horizon
targetWealth {float} -- target wealth
pmf {List[List[Tuple[int, float]]]} -- probability mass function
'''
# initialize instance variables
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)] # action generator
self.st = lambda s, a, r: State(s.t + 1, s.wealth - a + a*r) # state transition
self.iv = lambda s, a, r: 1 if s.wealth - a + a*r >= self.targetWealth else 0 # immediate value function
self.cache_actions = {} # cache with optimal state/action pairs
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:
#Forward recursion
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])) # future value
for p in self.pmf[s.t]]) # random variable realisations
for a in self.ag(s)]) # actions
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]))
for p in self.pmf[s.t]]) == v
q = [k for k in filter(opt_a, self.ag(s))] # retrieve best action list
self.cache_actions[str(s)]=q[0] if bool(q) else None # store an action in dictionary
return v # return value
instance = {"bettingHorizon": 4, "targetWealth": 6, "pmf": [[(0, 0.6),(2, 0.4)] for i in range(0,4)]}
gr, initial_wealth = GamblersRuin(**instance), 2
# f_1(x) is gambler's probability of attaining $targetWealth at the end of bettingHorizon
print("f_1("+str(initial_wealth)+"): " + str(gr.f(initial_wealth)))
#Recover optimal action for period 2 when initial wealth at the beginning of period 2 is $1.
t, initial_wealth = 1, 1
print("b_"+str(t+1)+"("+str(initial_wealth)+"): " + str(gr.q(t, initial_wealth)))
Implementação Java. GamblersRuin.java é uma implementação Java 8 autônoma do exemplo acima.
Programação dinâmica aproximada
Uma introdução à programação dinâmica aproximada é fornecida por ( Powell 2009 ).
Leitura adicional
-
Bellman, R. (1957), Dynamic Programming , Princeton University Press, ISBN 978-0-486-42809-3. Edição de bolso de Dover (2003).
-
Ross, SM; Bimbaum, ZW; Lukacs, E. (1983), Introduction to Stochastic Dynamic Programming , Elsevier, ISBN 978-0-12-598420-1.
-
Bertsekas, DP (2000), Dynamic Programming and Optimal Control (2ª ed.), Athena Scientific, ISBN 978-1-886529-09-0. Em dois volumes.
-
Powell, WB (2009), "What you should know about aproximado dynamic programming", Naval Research Logistics , 56 (1): 239–249, CiteSeerX 10.1.1.150.1854 , doi : 10.1002 / nav.20347
Veja também
Referências
