Warum wird seichte Kopie benötigt, damit mein Wertwörterbuch korrekt aktualisiert wird?

Question

Ich arbeite an einer Agent Klasse in Python 2.7.11, die eine Markov Decision Process (MDP) verwendet, um nach einer optimalen Richtlinie π in einem GridWorld zu suchen. Ich bin ein Grundwert Iteration für 100 Iterationen aller GridWorld Staaten die Umsetzung der folgenden Bellman Gleichung:

• T (s, a, s') ist die Wahrscheinlichkeitsfunktion von erfolgreich Übergang in den Nachfolgestatus s ' vom aktuellen Zustand s durch Ergreifen von Maßnahmen a.
• R (s, a, s ') ist die Belohnung für von s zu s Übergang'.
• γ (gamma) der Diskontfaktor wo γ .
• V _k (s ') ist ein rekursiver Aufruf der Berechnung einmal s zu wiederholen' erreicht ist.
• V _{k + 1} (e) ist repräsentativ dafür, wie nach genug k Iterationen aufgetreten sind, die V _k Iterationswert konvergieren und äquivalent werden zu V _{k + 1}

Diese Gleichung wird von der Einnahme des Maximums eines Wert Q abgeleiteten Funktion, das ist, was ich in meinem Programm verwende:

Als mein Agent Konstruktion ist es ein MDP geführt, die eine abstrakte Klasse ist, die folgenden Methoden enthalten:

# Returns all states in the GridWorld 
def getStates() 

# Returns all legal actions the agent can take given the current state 
def getPossibleActions(state) 

# Returns all possible successor states to transition to from the current state 
# given an action, and the probability of reaching each with that action 
def getTransitionStatesAndProbs(state, action) 

# Returns the reward of going from the current state to the successor state 
def getReward(state, action, nextState) 

Meine Agent wird auch ein Rabattfaktor und eine Anzahl von Iterationen übergeben. Ich benutze auch eine dictionary, um meine Werte zu verfolgen. Hier ist mein Code:

class IterationAgent: 

    def __init__(self, mdp, discount = 0.9, iterations = 100): 
     self.mdp = mdp 
     self.discount = discount 
     self.iterations = iterations 
     self.values = util.Counter() # A Counter is a dictionary with default 0 

     for transition in range(0, self.iterations, 1): 
      states = self.mdp.getStates() 
      valuesCopy = self.values.copy() 
      for state in states: 
       legalMoves = self.mdp.getPossibleActions(state) 
       convergedValue = 0 
       for move in legalMoves: 
        value = self.computeQValueFromValues(state, move) 
        if convergedValue <= value or convergedValue == 0: 
         convergedValue = value 

       valuesCopy.update({state: convergedValue}) 

      self.values = valuesCopy 

    def computeQValueFromValues(self, state, action): 
     successors = self.mdp.getTransitionStatesAndProbs(state, action) 
     reward = self.mdp.getReward(state, action, successors) 
     qValue = 0 
     for successor, probability in successors: 
      # The Q value equation: Q*(a,s) = T(s,a,s')[R(s,a,s') + gamma(V*(s'))] 
      qValue += probability * (reward + (self.discount * self.values[successor])) 
     return qValue 

Diese Implementierung ist richtig, obwohl ich nicht sicher bin, warum ich valuesCopy brauchen ein erfolgreiches Update zu meinem self.values Wörterbuch zu erreichen.Ich habe folgendes versucht, das Kopieren zu unterlassen, aber es nicht funktioniert, da es leicht falsche Werte zurückgibt:

for i in range(0, self.iterations, 1): 
    states = self.mdp.getStates() 
    for state in states: 
     legalMoves = self.mdp.getPossibleActions(state) 
     convergedValue = 0 
     for move in legalMoves: 
      value = self.computeQValueFromValues(state, move) 
      if convergedValue <= value or convergedValue == 0: 
       convergedValue = value 

     self.values.update({state: convergedValue}) 

Meine Frage ist, warum ist zusammen mit einer Kopie meines self.values Wörterbuch notwendig, um meine Werte korrekt aktualisiert, wenn valuesCopy = self.values.copy() erstellt eine Kopie des Wörterbuchs sowieso jede Iteration? Sollten die Werte im ursprünglichen Ergebnis nicht im selben Update aktualisiert werden?

Answer 1

Es gibt einen algorithmischen Unterschied in mit oder ohne die Kopie mit:

# You update your copy here, so the original will be used unchanged, which is not the 
# case if you don't have the copy 
valuesCopy.update({state: convergedValue}) 

# If you have the copy, you'll be using the old value stored in self.value here, 
# not the updated one 
qValue += probability * (reward + (self.discount * self.values[successor]))