O problema do jogador (The Gambler's Problem)

Question

Este problema foi retirado do livro Reinforcement Learning de Sutton
and Barto. É o exemplo 4.3 da seção sobre iterações da função valor.

Um jogador tem a oportunidade de fazer apostas nos resultados de uma seqüência de lançamentos de moeda. Se a moeda surgir, então ele ganha tantos dólares como ele apostou naquele flip, mas se for coroa, ele perde sua aposta. O jogo termina quando o o jogador ganha ao atingir sua meta de 100 dólares, ou perde ficando sem dinheiro. Em cada Por outro lado, o apostador deve decidir que parte de seu capital apostará, em números inteiros de dólares. Este problema pode ser formulado como um MDP finito.

O estado é o capital do jogador, que ele usará para as suas apostas e pode ser descrito como: \(s\epsilon\{1,2,3,...,99\}\) e as ações são as apostas (stakes), \(a\epsilon\{0,1,...,min(s,100-s\}\).

A recompensa é zero em todas as transições, exceto aquelas em
que o jogador atinge seu objetivo, quando é \(+1\). A função de valor de estado fornece então a probabilidade de ganhar de cada estado. Uma política é um mapeamento de níveis de capital para estacas. A política ótima maximiza a probabilidade de atingir o objetivo. Deixe \(p\) denotar a probabilidade da moeda dar CARA. Se \(p\) é conhecido, então todo o problema é conhecido e pode ser resolvido, por exemplo, por iteração de valor. A figura 4., abaixo, retirada do livro, mostra a mudança na função de valor conforme vamos iterando. E acabamos descobrindo a final polciy para quando \(p=0.4\).

Answer 1

Abaixo faço uma implementação do problema e ploto os gráficos das soluçoes

from __future__ import print_function
import numpy as np
import matplotlib.pyplot as plt  
# meta de estados
GOAL = 100
#todos os estados
   states = np.arange(GOAL + 1)
   # probabilidade de ara
   headProb = 0.4
   # definindo a nossa politica otima
   policy = np.zeros(GOAL + 1)
   # valores de estado
  stateValue = np.zeros(GOAL + 1)
  stateValue[GOAL] = 1.0

# iteração da value function
while True:
delta = 0.0
for state in states[1:GOAL]:
    # todas as ações possiveis para o estado atual
    actions = np.arange(min(state, GOAL - state) + 1)
    actionReturns = []
    for action in actions:
        actionReturns.append(headProb * stateValue[state + action] + (1 - headProb) * stateValue[state - action])
    newValue = np.max(actionReturns)
    delta += np.abs(stateValue[state] - newValue)
    # atualizando o estado atual
    stateValue[state] = newValue
if delta < 1e-9:
    break

# calculando a politica otima (optimal policy)
for state in states[1:GOAL]:
actions = np.arange(min(state, GOAL - state) + 1)
actionReturns = []
for action in actions:
    actionReturns.append(headProb * stateValue[state + action] + (1 - headProb) * stateValue[state - action])

policy[state] = actions[np.argmax(actionReturns)]

# plotando os resultados
   plt.figure(1)
   plt.xlabel('Capital')
   plt.ylabel('Valores estimados')
   plt.plot(stateValue)
   plt.figure(2)
   plt.scatter(states, policy)
   plt.xlabel('Capital')
   plt.ylabel('Politica final (stake)')
   plt.show()

Seguem as figuras plotadas no código acima:

Comments

Victor, acho que teve algum problema de convergencia. Não chequei com cuidado o código, mas veja que não faz sentido para o capital 1,2 e 3 estar em cima da linha e depois o valor cair para zero em capital igual a 4. De fato, para p=0.4, vc deveria ter encontrado exatamente a figura que vc copiou do livro. Desculpe se não entendi algo.  Já resolvi no passado (usando matlab) e encontrei exatamente a figura do livro. A solução é intuitiva. Em cada interação reduz a sua chance de chegar ao resultado de 100 como desejado. Logo, ele faz o melhor que pode usando o esquema apresentado na figura do livro. Sobre a solução, aparentemente o que vc fez faz sentido, deve ser algo bem sutil.