Non capisco l'iterazione del valore

Question

Non capisco l'iterazione del valore

#1 da (2 voti)

1

In classe sto imparando problemi di iterazione del valore e decisione markov, stiamo facendo attraverso il progetto UC Berkley pac-man, quindi sto cercando di scrivere il valore iteratore per esso e, a quanto ho capito, l'iterazione del valore è quella per ogni iterazione si sta visitando ogni stato, e quindi il monitoraggio di uno stato terminale per ottenere il suo valore.

Ho la sensazione che non abbia ragione, perché quando provo che in python ho una profondità ricorsiva superiore. Così torno allo pseudo-codice, e c'è un Vk[s] e Vk-1[s'] , che avevo pensato significasse valore di stato, e valore di newState , ma mi manca qualcosa.

Quindi qual è il significato di k e k-1 ?

Il mio codice:

 def val(i, state):
        if mdp.isTerminal(state) or i == 0:
            return 0.0
        actionCost = {}
        for action in mdp.getPossibleActions(state):
            actionCost[action] = 0
            for (nextState, probability) in mdp.getTransitionStatesAndProbs(state, action):
                reward = mdp.getReward(state, action, nextState)
                actionCost[action] += probability * reward + discount * val(i - 1, nextState)        
        return actionCost[max(actionCost, key=actionCost.get)]

    for i in range(iterations):
        for state in mdp.getStates():  
            self.values[state] = val(i, state)

Pseudo codice:

k ←0 
repeat
      k ←k+1 
      for each state s do 
          Vk[s] = maxa ∑s' P(s'|s,a) (R(s,a,s')+ γVk-1[s']) 
until ∀s |Vk[s]-Vk-1[s]| < θ

python artificial-intelligence

posta EasilyBaffled 17.03.2013 - 00:15

fonte

1 risposta

Leggi altre domande sui tag python artificial-intelligence

Silverlight5 fornisce qualcosa di nuovo per WCF Progettazione di un'API per operazioni di servizio con parametri strettamente correlati

score 2 · Answer 1

Vk e Vk-1 sono diverse iterazioni dell'approssimazione di V. Puoi riscrivere lo pseudo codice come:

V ← 0
V' ← 0
while true
  for each state s do
      V ← V'
      V = maxa ∑s' [ P(s'|s,a) R(s,a,s')+ γV'[s'] ]
  if ∀s |V[s]-V'[s]| < θ
      return V

Si noti che lo pseudo-codice non è ricorsivo. Questa è l'idea di value-iteration / dyanmic-programming che la rendono efficiente:

Calcola la funzione del valore ottimale per il passo 0: V0 = 0
quindi calcola la funzione del valore ottimale per 1 passo temporale: V1 = H (V0)
quindi calcola la funzione del valore ottimale per 2 intervalli temporali: V2 = H (V1)
quindi calcola la funzione del valore ottimale per 3 intervalli temporali: V3 = H (V2)
...
quindi calcola la funzione del valore ottimale per n passi temporali: Vn = H (Vn-1)

con H definito come:

 H(V) = max_a ( Pa [ Ra + γ V ] )

Il tuo codice è ricorsivo (val call val) che attiva qualche errore di overflow dello stack. L'iterazione del valore non è ricorsiva ma iterativa. La tua funzione "eval" lo rende:

actionCost[action] += probability * reward + discount * val(i - 1, nextState)

che ricalcola ricorsivamente i valori che hai già calcolato alla precedente iterazione (k-1). val (i - 1, nextState) è in effetti:

 self.previous_values[nextState]

(assumendo che tu mantenga una copia di previousValue).