Reinforcement Learning Exercise

1import mdp, util
2
3from learningAgents import ValueEstimationAgent
4import collections
5
6class ValueIterationAgent(ValueEstimationAgent):
7    """
8        * Please read learningAgents.py before reading this.*
9
10        A ValueIterationAgent takes a Markov decision process
11        (see mdp.py) on initialization and runs value iteration
12        for a given number of iterations using the supplied
13        discount factor.
14    """
15    def __init__(self, mdp, discount = 0.9, iterations = 100):
16        """
17          Your value iteration agent should take an mdp on
18          construction, run the indicated number of iterations
19          and then act according to the resulting policy.
20
21          Some useful mdp methods you will use:
22              mdp.getStates()
23              mdp.getPossibleActions(state)
24              mdp.getTransitionStatesAndProbs(state, action)
25              mdp.getReward(state, action, nextState)
26              mdp.isTerminal(state)
27        """
28        self.mdp = mdp
29        self.discount = discount
30        self.iterations = iterations
31        self.values = util.Counter() # A Counter is a dict with default 0
32        self.runValueIteration()
33
34    def runValueIteration(self):
35        # Write value iteration code here
36        for _ in range(self.iterations):
37            newValues = util.Counter()
38            for state in self.mdp.getStates():
39                if self.mdp.isTerminal(state):
40                    continue
41                bestAction = self.computeActionFromValues(state)
42                if bestAction is not None:
43                    newValues[state] = self.computeQValueFromValues(state, bestAction)
44            for state in self.mdp.getStates():
45                self.values[state] = newValues[state]
46    def getValue(self, state):
47        """
48          Return the value of the state (computed in __init__).
49        """
50        return self.values[state]
51
52
53    def computeQValueFromValues(self, state, action):
54        """
55          Compute the Q-value of action in state from the
56          value function stored in self.values.
57        """
58        qValue = 0
59        for nextState, prob in self.mdp.getTransitionStatesAndProbs(state, action):
60            reward = self.mdp.getReward(state, action, nextState)
61            qValue += prob * (reward + self.discount * self.values[nextState])
62        return qValue
63
64    def computeActionFromValues(self, state):
65        """
66          The policy is the best action in the given state
67          according to the values currently stored in self.values.
68
69          You may break ties any way you see fit.  Note that if
70          there are no legal actions, which is the case at the
71          terminal state, you should return None.
72        """
73        if self.mdp.isTerminal(state):
74            return None
75
76        bestAction = None
77        bestQValue = float("-inf")
78
79        for action in self.mdp.getPossibleActions(state):
80            qValue = self.computeQValueFromValues(state, action)
81            if qValue > bestQValue:
82                bestQValue = qValue
83                bestAction = action
84
85        return bestAction
86
87    def getPolicy(self, state):
88        return self.computeActionFromValues(state)
89
90    def getAction(self, state):
91        "Returns the policy at the state (no exploration)."
92        return self.computeActionFromValues(state)
93
94    def getQValue(self, state, action):
95        return self.computeQValueFromValues(state, action)