<jupyter_start><jupyter_text>Markov Decision ProcessAssume that we have the following grid world:![grafik.png](attachment:grafik.png)The goal of the agent whose position is at the bottom left corner is to maximize the expected future reward.The top right (reward +1) and the middle right cell (reward -1) are terminal states.There are four different actions the agent can choose, namely go up, down, left and right.However, there is a chance that the agent will result in a wrong grid cell by accident.If the action is going up, there is a chance of 0.8 that the agent moves up, a chance of 0.1 that he moves left and a chance of 0.1 that he moves right.All other actions behave accordingly.If the agent would bounce on a wall it stays at the current position.Note that the agent cannot move through the grayed-out grid cell.Assume a gamma value of $\gamma=0.9$. Assume that the following utility values are given:![grafik.png](attachment:grafik.png)  Environment Definition:<jupyter_code>import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns
class MDP:
    
    "0: up, 1: right, 2: left, 3: down"
    _transitions = np.array([
        [[4, 0.8], [-1, 0.1], [1, 0.1]],
        [[1, 0.8], [-4, 0.1], [4, 0.1]],
        [[-1, 0.8], [-4, 0.1], [4, 0.1]],
        [[-4, 0.8], [-1, 0.1], [1, 0.1]]
        ])
    
    def __init__(self, gamma=0.9):
        self.reward = np.zeros(3*4)
        self.reward[-1] = +1
        self.reward[5] = -1
        self.reward[7] = -1
        self.gamma = gamma
        
    def rewards(self, state):
        """
        Returns the reward for the given state as scalar.
        """
        return self.reward[state]
    
    def _bounces(self, state, s):
        return np.sum(
            np.abs(np.array(np.where(np.arange(12).reshape((3,4)) == state)) 
                   - np.array(np.where(np.arange(12).reshape((3,4)) == s)))
        ) > 1
    
    def transition(self, state, action):
        """
        Returns a list of follow states including their probabilities.
        If a state has zero probability, it will be skipped.
        Example:
        Suppose we have state action pair where we have two follow states 
        (4 and 6) with probability 0.4 and 0.6 respectively (all other states have 0 probability) our result ist:
        [[4, 0.4], [6, 0.6]]
        """
        if state == 7 or state == 11:
            return np.zeros((0,2))
        trans = MDP._transitions[action].copy()
        trans = trans.T
        trans[0,:] += state
        trans = trans.T
        for i, (s, prob) in enumerate(trans):
            if s < 0 or s >= 3*4 or s == 5 or self._bounces(state, s):
                trans[i,0] = state
        return trans
def print_utilities(utilities):
    plt.figure()
    reshaped = utilities.reshape((3,4))
    reshaped[1,1] = -1
    ax = sns.heatmap(reshaped, annot=True)
    ax.invert_yaxis()
mdp = MDP()

utilities = np.array([0.5,0.4,0.3,0.,0.5,-1.,0.5,-1.,0.6,0.7,0.8,1])
print_utilities(utilities)<jupyter_output><empty_output><jupyter_text>Policy ImprovementImplement a policy improvement step in order to compute the policy that is defined by the given utility values.<jupyter_code>def q(mdp, state, action, utilities):
    trans = mdp.transition(state, action)
    return np.sum(utilities[trans.T[0].astype(int)] * trans.T[1])

def policy_improvement(mdp, utilities):
    # TODO implement
    policy = np.zeros(len(utilities))
    for state in range(len(utilities)):
        policy[state] = np.argmax([ q(mdp, state, a, utilities) for a in range(4) ])
    return policy

# Prints the computed policy
policy = policy_improvement(mdp, utilities).astype(int)
print_utilities(policy)<jupyter_output><empty_output><jupyter_text>Policy EvaluationImplement a policy evaluation step in order evaluate the utility values of the improved policy.<jupyter_code>def policy_evaluation(mdp, policy):
    # TODO implement
    states = len(policy)
    reward = [mdp.rewards(s) for s in range(states)]
    prob_matrix = np.eye(states)
    for state in range(states):
        trans = mdp.transition(state, policy[state])
        for i, (s, prob) in enumerate(trans):
            prob_matrix[state,int(s)] -= mdp.gamma * prob
    return np.linalg.solve(prob_matrix, reward)
# Prints the starting utilities and the utilities of the improved policy
print_utilities(utilities)
print_utilities(policy_evaluation(mdp, policy))<jupyter_output><empty_output><jupyter_text>Policy IterationImplement the policy iteration algorithm by using the policy improvement and evaluation function defined above.<jupyter_code>def policy_iteration(mdp):
    # TODO implement
    policy = np.zeros(12, dtype=int)
    while True:
        utilities = policy_evaluation(mdp, policy)
        next_policy = policy_improvement(mdp, utilities).astype(int)
        if np.sum(next_policy != policy) == 0:
            break
        policy = next_policy
    return policy
# prints the optimal policy and the optimal utility values
policy = policy_iteration(mdp)
print_utilities(policy)
print_utilities(policy_evaluation(mdp, policy))<jupyter_output><empty_output><jupyter_text>Value IterationImplement the value iteration algorithm.<jupyter_code>def value_iteration(mdp, utilities):
    utilities_next = np.zeros(len(utilities))

    delta = np.inf
    while delta > 1e-10:
        for state in range(len(utilities)):
            utilities_next[state] = mdp.rewards(state) + mdp.gamma * np.max( [ q(mdp, state, a, utilities) for a in range(4) ] )

        delta = np.max(np.abs(utilities - utilities_next))
        utilities = utilities_next.copy()
    
    return utilities 4
# prints the optimal utility from Value Iteration
optimal = value_iteration(mdp, utilities)
print_utilities(optimal)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11257588898525585, 'fraction_numerical': 0.02237640936686904, 'mean_word_length': 3.22108345534407, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '546766', 'license': 'MIT', 'n_tokens_mistral': 1894, 'n_tokens_neox': 1811, 'n_words': 570, 'path': 'week10/mdp.ipynb', 'repo_name': 'changkun/ws-18-19-deep-learning-tutorial', 'size': '5765'}