Comprendre l'algorithme d'itération de la valeur des processus de décision de Markov

Question

En apprendre plus sur MDP J'ai des problèmes avec value iteration. Conceptuellement cet exemple est très simple et logique:

Si vous avez un dé face 6, et vous lancez un 4 ou un 5 ou 6 vous garder ce montant en $ mais si vous lancez un 1 ou un 2 ou 3 vous perdez votre bankroll et mettez fin à la partie.

Au début, vous avez $0 donc le choix entre le laminage et non roulant est:

k = 1 
If I roll : 1/6*0 + 1/6*0 + 1/6*0 + 1/6*4 + 1/6*5 + 1/6*6 = 2.5 
I I don't roll : 0 
since 2.5 > 0 I should roll 

k = 2: 
If I roll and get a 4: 
    If I roll again: 4 + 1/6*(-4) + 1/6*(-4) + 1/6*(-4) + 1/6*4 + 1/6*5 + 1/6*6 = 4.5 
    If I don't roll: 4 
    since 4.5 is greater than 4 I should roll 

If I roll and get a 5: 
    If I roll again: 5 + 1/6*(-5) + 1/6*(-5) + 1/6*(-5) + 1/6*4 + 1/6*5 + 1/6*6 = 5 
    If I don't roll: 5 
    Since the difference is 0 I should not roll 

If I roll and get a 6: 
    If I roll again: 6 + 1/6*(-6) + 1/6*(-5) + 1/6*(-5) + 1/6*4 + 1/6*5 + 1/6*6 = 5.5 
    If I don't roll: 6 
    Since the difference is -0.5 I should not roll 

Ce que je ne parviens pas à convertir avec est que dans le code python. Pas parce que je ne suis pas bon avec Python, mais peut-être ma compréhension de la pseudocode est erronée. Même si le Bellman equation a du sens pour moi.

Je borrowed le code Berkley pour value iteration et modifié à:

isBadSide = [1,1,1,0,0,0] 

def R(s): 
    if isBadSide[s-1]: 
     return -s 
    return s 

def T(s, a, N): 
    return [(1./N, s)] 

def value_iteration(N, epsilon=0.001): 
    "Solving an MDP by value iteration. [Fig. 17.4]" 
    U1 = dict([(s, 0) for s in range(1, N+1)]) 
    while True: 
     U = U1.copy() 
     delta = 0 
     for s in range(1, N+1): 
      U1[s] = R(s) + max([sum([p * U[s1] for (p, s1) in T(s, a, N)]) 
             for a in ('s', 'g',)]) 

      delta = max(delta, abs(U1[s] - U[s])) 

     if delta < epsilon: 
      return U 

    print(value_iteration(6)) 
    # {1: -1.199845679, 2: -2.3996913580246915, 3: -3.599537037037037, 4: 4.799382716049383, 5: 5.999228395061729, 6: 7.199074074074074} 

Quelle est la mauvaise réponse. Où est le bug dans ce code? Ou est-ce un problème de compréhension de l'algorithme?

Answer 1

Soit B être votre solde actuel.

Si vous choisissez de lancer, la récompense attendue est 2.5 - B * 0.5.

Si vous choisissez de ne pas lancer, la récompense attendue est 0. Donc, la politique est la suivante: Si B < 5, roulez. Sinon, ne le faites pas.

Et la récompense attendue à chaque étape en suivant cette politique est V = max(0, 2.5 - B * 0.5). Maintenant, si vous voulez l'exprimer en termes de l'équation de Bellman, vous devez incorporer la balance dans l'état.

Laissez l'état <Balance, GameIsOver> se composer du solde actuel et du drapeau qui définit si le jeu est terminé.

• action stop:
  • transforme en l'état <B, false><B, true>
• action roll:
  • tours <B, false> en <0, true> avec la probabilité 1/2
  • tourne <B, false> en <B + 4, false> avec la probabilité 1/6
  • tourne <B, false> en <B + 5, false> avec la probabilité 1/6
  • tourne <B, false> en <B + 6, false> avec la probabilité 1/6
• Aucune action ne peut transformer <B1, true> en <B2, false>

En utilisant la notation de here:

π(<B, false>) = "roll", if B < 5

π(<B, false>) = "stop", if B >= 5

V(<B, false>) = 2.5 - B * 0.5, if B < 5

V(<B, false>) = 0, if B >= 5