<jupyter_start><jupyter_text>Checklist for submissionIt is extremely important to make sure that:1. Everything runs as expected (no bugs when running cells);2. The output from each cell corresponds to its code (don't change any cell's contents without rerunning it afterwards);3. All outputs are present (don't delete any of the outputs);4. Fill in all the places that say ` YOUR CODE HERE`, or "**Your answer:** (fill in here)".5. Never copy/paste any notebook cells. Inserting new cells is allowed, but it should not be necessary.6. The notebook contains some hidden metadata which is important during our grading process. **Make sure not to corrupt any of this metadata!** The metadata may for example be corrupted if you copy/paste any notebook cells, or if you perform an unsuccessful git merge / git pull. It may also be pruned completely if using Google Colab, so watch out for this. Searching for "nbgrader" when opening the notebook in a text editor should take you to the important metadata entries.7. Although we will try our very best to avoid this, it may happen that bugs are found after an assignment is released, and that we will push an updated version of the assignment to GitHub. If this happens, it is important that you update to the new version, while making sure the notebook metadata is properly updated as well. The safest way to make sure nothing gets messed up is to start from scratch on a clean updated version of the notebook, copy/pasting your code from the cells of the previous version into the cells of the new version.8. If you need to have multiple parallel versions of this notebook, make sure not to move them to another directory.9. Although not forced to work exclusively in the course `conda` environment, you need to make sure that the notebook will run in that environment, i.e. that you have not added any additional dependencies.**FOR HA1, HA2, HA3 ONLY:** Failing to meet any of these requirements might lead to either a subtraction of POEs (at best) or a request for resubmission (at worst).We advise you to perform the following steps before submission to ensure that requirements 1, 2, and 3 are always met: **Restart the kernel** (in the menubar, select Kernel$\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\rightarrow$Run All). This might require a bit of time, so plan ahead for this (and possibly use Google Cloud's GPU in HA1 and HA2 for this step). Finally press the "Save and Checkout" button before handing in, to make sure that all your changes are saved to this .ipynb file.  Fill in name of notebook fileThis might seem silly, but the version check below needs to know the filename of the current notebook, which is not trivial to find out programmatically.You might want to have several parallel versions of the notebook, and it is fine to rename the notebook as long as it stays in the same directory. **However**, if you do rename it, you also need to update its own filename below:<jupyter_code># nb_fname = "XXX.ipynb"<jupyter_output><empty_output><jupyter_text>Fill in group number and member names (use NAME2 and GROUP only for HA1, HA2 and HA3):<jupyter_code>NAME1 = "" 
NAME2 = ""
GROUP = ""<jupyter_output><empty_output><jupyter_text>Check Python version<jupyter_code>from platform import python_version_tuple
assert python_version_tuple()[:2] == ('3','7'), "You are not running Python 3.7. Make sure to run Python through the course Conda environment."<jupyter_output><empty_output><jupyter_text>Check that notebook server has access to all required resources, and that notebook has not moved<jupyter_code>import os
nb_dirname = os.path.abspath('')
assignment_name = os.path.basename(nb_dirname)
assert assignment_name in ['IHA1', 'IHA2', 'HA1', 'HA2', 'HA3'], \
    '[ERROR] The notebook appears to have been moved from its original directory'<jupyter_output><empty_output><jupyter_text>Verify correct nb_fname<jupyter_code>from IPython.display import display, HTML
try:
    display(HTML(r'<script>if("{nb_fname}" != IPython.notebook.notebook_name) {{ alert("You have filled in nb_fname = \"{nb_fname}\", but this does not seem to match the notebook filename \"" + IPython.notebook.notebook_name + "\"."); }}</script>'.format(nb_fname=nb_fname)))
except NameError:
    assert False, 'Make sure to fill in the nb_fname variable above!'<jupyter_output><empty_output><jupyter_text>Verify that your notebook is up-to-date and not corrupted in any way<jupyter_code>import sys
sys.path.append('..')
from ha_utils import check_notebook_uptodate_and_not_corrupted
check_notebook_uptodate_and_not_corrupted(nb_dirname, nb_fname)<jupyter_output><empty_output><jupyter_text>Home Assignment 3This home assignment is about reinforcement learning and deep reinforcement learning. In Section 1, we introduce a small grid world that we will use in some of the examples. Section 2, then briefly covers model-based reinforcement learning techniques (policy evaluation, policy iteration and value iteration), whereas Section 3 touches upon model-free reinforcement learning techniques (Q-learning). Finally, we turn our attention to model-free deep reinforcement learning (DQN), i.e., neural networks as function approximators, in Section 4.   Section 1: Grid-World IntroductionWe first describe our standard grid world, which we will use in Sections 1, 2 and 3. As illustrated in the figure below, we have a 5x3 grid world with 15 cells. Each cell is color-coded to represent the characteristics of the cell. There are 11 white and two black cells along with one red and one green cell. We also have an indigo colored Terminal State (T.S.) cell outside our 5x3 grid. All cells represent reachable states except for the two black cells that represent walls that the agent cannot enter. For simplicity, we write, e.g., "the red state" when referring to the state that corresponds to a red cell.![Grid World](./grid_world.png)  1.1 Environment DynamicsThe agent can choose between one of the four available actions: Up, Down, Left or Right. The set of all actions is called an action space and we can write our action space as $\cal{A}$ $=\{↑, →, ↓, ←\}$. We will use the words $\{\text{Up}, \text{Right}, \text{Down}, \text{Left}\}$ and the symbols $\{↑, →, ↓, ←\}$ interchangeably.If the agent is in a white state and moves in the direction of a wall, either the boundary of the grid world or the black wall, the agent remains in its current state until the next time step. The red and green states are special states where any action taken by the agent takes it to the Terminal State (T.S.) in the next time step, and the episode ends.We will use both deterministic and stochastic transition/dynamics models for the white states. When the transition model is deterministic, taking an action $a$ (e.g., Up) takes the agent in the intended direction (e.g., Up) with probability 1. When the transition model is stochastic, taking an action $a$ takes the agent in the intended direction with probability $p$, and with probability $1-p$, the agent goes in a different direction depending on the specification of the stochastic transition model. 1.2 Reward FunctionThe immediate reward $R_{t+1}$ is 0 with probability 1 in the white states for any action. For the green state, the reward is always 1, and for the red state, always -1, regardless of the action. 1.3 State RepresentationThe notations used to define the states are illustrated in the figure below.![title](./state_rep.png)Each state has been given an integer number from 0 to 15, as illustrated in the figure. We note that the green state is 4, the red state is 9, the terminal state is 15 whereas 6 and 7 are unreachable states. One might argue that the black cells are not states at all, but for the sake of convenience in the code implementation, these cells have been numbered as states 6 and 7. In your computations, you can treat these values as terminal states and the values of these states will therefore be always 0. Strictly speaking, we never take any actions in a terminal state, but in our visualizations we assume the default action Up for these states, which is an arbitrary choice.   1.4 Markov Decision ProcessFormally, we describe our problem as a Markov decision process (MDP). An MDP consists of the following tuple: $$(\cal S, \cal A, \cal P, \cal R, \gamma),$$ where $\cal S$ is the set of all states, and $S_{t}$ is the state of the agent at time $t$,\$\cal A$ is the set of all actions and $A_{t}$ is the action taken in $S_{t}$ by the agent,\$\cal P$ is the transition model, defined as $\cal{P}_{ss'}^a$ $=\mathbb{P}[S_{t+1}=s'\big|S_t=s,A_t=a]$, which gives the probability to transition from state $s$ to $s'$ given action $a$,\$\cal R$ is the reward model, defined as $\cal{R}_s^a$ $= \mathbb{E}[R_{t+1} | S_t = s, A_t=a]$, which gives the expected reward for taking the action $a$ from the state $s$,\$\gamma$ is the discount factor used to discount future rewards. **Task 1.4.1: (4 Points)**Suppose the agent starts in the top left corner of the grid world with a deterministic policy, that is, at the state $s=0$, and takes the action $a=\text{Right} \ $ five times until the episode ends. Write the reward $R_t$ and the return $G_t$ for every time step. You can assume that the agent starts in $s=0$ at $t=0$ such that it reaches the terminal state at $t=5$. (Note that we only receive rewards at the time steps 1, 2, 3, 4 and 5.) **Your answer:** (fill in here)  Section 2: Model-based Reinforcement LearningIn this section, we explore model-based reinforcement learning algorithms including Policy Evaluation, Policy Iteration and Value Iteration.  2.1 Policy EvaluationThe ability to evaluate a policy is essential in reinforcement learning. Formally, this means that we compute the value function $v_{\pi}(s)$ (or the action-value function $q_{\pi}(s,a)$) for a given policy $\pi$. We will now study how this can be done in a model-based setting, that is, when the models in our Markov decision problem are known. Remark: The policy evaluation algorithm is also known as the Iterated policy evaluation algorithm in, e.g., the book 'Reinforcement Learning: An Introduction' by Sutton and Barto.  **Task 2.1.1: (5 Points)** Assume we have a deterministic transition model such that if the agent takes an action $a$, it will move in that direction with probability 1. You are given a stochastic policy $\pi$ shown in the figure below, that takes each of the four actions with equal probability (uniformly random) in all states, $$\pi(a \mid s) = 0.25, \quad \text{for all states} \ s \in {\cal S} \ \text{and actions} \  a \in {\cal A}.$$ Assume $\gamma = 0.9$.![title](./random_policy.png)Compute the state-value updates by hand for the first three iterations of the Policy Evaluation algorithm, that is, the state-values $\hat{v}_{\pi}^{(1)}(s)$, $\hat{v}_{\pi}^{(2)}(s)$ and $\hat{v}_{\pi}^{(3)}(s)$ for all states $s$ under the policy $\pi$. Assume $\gamma = 0.9$ and $\hat{v}_{\pi}^{(0)}(s) = 0$ for all states $s$.$\hat{v}_{\pi}^{(k)}(s)$:|$\hat{v}_{\pi}^{(k)}(0)$|$\hat{v}_{\pi}^{(k)}(1)$|$\hat{v}_{\pi}^{(k)}(2)$|$\hat{v}_{\pi}^{(k)}(3)$|$\hat{v}_{\pi}^{(k)}(4)$||------------------------|------------------------|------------------------|------------------------|------------------------||$\hat{v}_{\pi}^{(k)}(5)$|$\hat{v}_{\pi}^{(k)}(6)$|$\hat{v}_{\pi}^{(k)}(7)$|$\hat{v}_{\pi}^{(k)}(8)$|$\hat{v}_{\pi}^{(k)}(9)$||$\hat{v}_{\pi}^{(k)}(10)$|$\hat{v}_{\pi}^{(k)}(11)$| $\hat{v}_{\pi}^{(k)}(12)$|$\hat{v}_{\pi}^{(k)}(13)$|$\hat{v}_{\pi}^{(k)}(14)$|Note $\hat{v}_{\pi}^{(k)}(6)$ and $\hat{v}_{\pi}^{(k)}(7)$ are always 0 for all iterations.<jupyter_code>#Answer:

# Write your values in the following format for the variables v_0, v_1, v_2, v_3
# v_k = [[v(0) , v(1) , v(2) , v(3) , v(4) ],
#        [v(5) , v(6) , v(7) , v(8) , v(9) ],
#        [v(10), v(11), v(12), v(13), v(14)]]
# After filling in all the values, run this cell to see your values in a table format

# YOUR CODE HERE

# Code to print the values in a nice format
import numpy as np

def print_value_table(values):
    v= np.ravel(values)
    if (len(v)==16):
        v = v[:-1]
    assert len(v) == 15, "Some values are missing from your input. Make sure you have entered values for all states."
    indecies = np.arange(0, 15, 5)
    hor_delimiter = "___________________________________________________"
    print('State Values: ')
    print(hor_delimiter)
    for i in indecies:
        print("| ", '%-6.3f' % v[i] , "| ", '%-6.3f' % v[i+1] , "| ", '%-6.3f' % v[i+2] ,
              "| ", '%-6.3f' % v[i+3] , "| ", '%-6.3f' % v[i+4] , "| ")
        print(hor_delimiter) 


print("\n v_0:")
print_value_table(v_0)
print("\n v_1:")
print_value_table(v_1)
print("\n v_2:")
print_value_table(v_2)
print("\n v_3:")
print_value_table(v_3)<jupyter_output><empty_output><jupyter_text>**Task 2.1.2: (2 Points)** Describe the steps you took to arrive at the value $\hat{v}_{\pi}^{(3)}(8)$ for the state $s = 8$ in the third iteration. You do not have to explain how $\hat v_{\pi}^{(2)}(s)$ was computed.  **Your answer:** (fill in here)  2.2 Policy IterationTo find the optimal policy $\pi_*$, when the models in our MDP are given, we can use policy iterations, where we iterate between the two steps: 1. Policy evaluation2. Policy improvementIn the **Policy Evaluation**, we evaluate our current policy $\pi$ and find $v_{\pi}(s)$.In the **Policy Improvement**, we update our policy to the greedy policy with respect to the state values $v_{\pi}(s)$ obtained in the Policy Evaluation step $$\pi \leftarrow \pi_{greedy}(v_{\pi}(s)).$$ **Task 2.2.1: (1 Point)** If we continue performing iterations of Policy Evaluation in Task 2.1.1, after iteration 49, our values converge to the following values for $v_{\pi}(s)$:| $0.023$  | $0.059$  | $0.121$  | $0.237$  | $1$      ||----------|----------|----------|----------|----------|| $-0.003$  | $0$      | $0$      | $-0.303$ | $-1$    || $-0.031$ | $-0.072$ | $-0.145$ | $-0.282$ | $-0.525$ |  Find the greedy policy $\pi = greedy(v_{\pi}(s))$. Double-click this cell and use the following grid and symbols to write the policy you found in the answer..Actions = ↑, →, ↓, ←| ↑  | ↑  | ↑  | ↑  | ↑  ||----|----|----|----|----|| ↑  | ↑  | ↑  | ↑  | ↑  || ↑  | ↑  | ↑  | ↑  | ↑  |   **Your answer:** (fill in here) **Task 2.2.2: (4 Points)** Let $\pi$ be the policy that you obtained in the solution to Task 2.2.1. Compute $v_{\pi}(s)$. Note that both the MDP and the policy are now deterministic, which means that the values can be obtained directly (the rewards are deterministic functions of the states).<jupyter_code>#Answer:

# Write your state values in the following format.
# v = [[v(0) , v(1) , v(2) , v(3) , v(4) ],
#        [v(5) , v(6) , v(7) , v(8) , v(9) ],
#        [v(10), v(11), v(12), v(13), v(14)]]
# After filling in all the values, run this cell to see your values in a table format

# YOUR CODE HERE

# Code to print the values in a nice format
print("\n v:")
print_value_table(v)<jupyter_output><empty_output><jupyter_text>**Task 2.2.3: (1 Points)**  Compute the greedy policy with respect to the state values that you obtained in Task 2.2.2. Double-click this cell and use the following grid and symbols to write the policy you found in the answer..Actions = ↑, →, ↓, ←| ↑  | ↑  | ↑  | ↑  | ↑  ||----|----|----|----|----|| ↑  | ↑  | ↑  | ↑  | ↑  || ↑  | ↑  | ↑  | ↑  | ↑  |  **Your answer:** (fill in here)   2.3 Value Iteration**Value Iteration** is another algorithm used for model-based reinforcement learning. Value iteration is an iterative algorithm used to compute the optimal value function $\hat{v}_*(s)$. Each iteration starts with a guess of what the value function is and then uses the Bellman optimality equations to improve this guess iteratively. We can describe one iteration of the algorithm as$\textbf{For all} ~ s \in {\cal S}:\qquad  \\\quad \hat{v}_{k+1}(s) = \underset{a \in {\cal A}}{\text{max}}~ \left( \mathcal{R}_s^a + \gamma \underset{{s'\in \mathcal{S}}}{\sum} \mathcal{P}_{ss'}^a \cdot \hat{v}_k(s') \right)$where $\mathcal{P}_{ss'}^a=\mathbb{P}[S'=s'\big|S=s,A=a]$ is the probability to transition from state $s$ to $s'$ given action $a$. In the next task, we will implement the value iteration algorithm, and find the optimal policy $\pi_*$ for our grid world. We have defined an MDP Python class and some helper functions, which are described below.  The MDP Python classThe Markov Decision Process you will work with is defined in `gridworld_mdp.py`. In the implementation, the actions are represented by integers as, Up = 0, Left = 1, Down = 2, and Right = 3.To interact with the MDP, you need to instantiate an object as: ```pythonmdp = GridWorldMDP()```At your disposal there are a number of instance-functions implemented for you, and presented below:<jupyter_code>from gridworld_mdp import *
import numpy as np

help(GridWorldMDP.get_states)
# The constructor
help(GridWorldMDP.__init__)
help(GridWorldMDP.get_actions)
help(GridWorldMDP.state_transition_func)
help(GridWorldMDP.reward_function)<jupyter_output><empty_output><jupyter_text>To visualize the state values you can use the function **print_value_table(values)** from task 2.1.1. We also provide a helper function for visualizing the policies you obtain below.<jupyter_code># Function for printing a policy pi
def print_policy(pi):
    print('\n Policy: ')
    indencies = np.arange(1, 16)
    txt = '| '
    hor_delimiter = '---------------------'
    print(hor_delimiter)
    for a, i in zip(pi, indencies):
        txt += mdp.act_to_char_dict[a] + ' | '
        if i % 5 == 0:
            print(txt + '\n' + hor_delimiter)
            txt = '| '<jupyter_output><empty_output><jupyter_text>**Task 2.3.1: (3 Points)** Now it's time for you to implement your own version of value iteration to solve for the optimal value function $v_*(s)$, and the optimal policy $\pi_*(s)$.<jupyter_code>#Answer:
def value_iteration(gamma, mdp):
    """
    Returns:
        V - state value table, numpy array of shape (16,)
        pi - greedy policy table, numpy array of shape (16,)
    """
    V = np.zeros([16]) # state value table

    # YOUR CODE HERE
    
    return V, pi<jupyter_output><empty_output><jupyter_text>Run your implementation for the deterministic version of our MDP. Check whether the optimal values and the optimal policy look appropriate.<jupyter_code>mdp = GridWorldMDP(trans_prob=1.)
v, pi = value_iteration(.9, mdp)
print_value_table(v)
print_policy(pi)<jupyter_output><empty_output><jupyter_text>Once the optimal values and the optimal policy look appropriate, run it for the stochastic case, such that when the agent takes an action $a$ there is 0.8 probability that it will move in the intended direction and 0.2 probability that it will move in one of the orthogonal directions to the intended with equal probability. Use $\gamma = .99$.<jupyter_code># Run for stochastic MDP, gamma = .99
mdp = GridWorldMDP(trans_prob=.8)
v, pi = value_iteration(.99, mdp)
print_value_table(v)
print_policy(pi)<jupyter_output><empty_output><jupyter_text>**Task 2.3.2: (2 Points)** For the Stochastic case, does the policy that the algorithm found look reasonable? Provide a brief description for your answer. In particular, what's the policy for state $s=8$? Is that a good idea? Why? **Your answer:** (fill in here) Test your implementation using this function.<jupyter_code>test_value_iteration(v, pi)<jupyter_output><empty_output><jupyter_text>Run value iteration for the same scenario as above, but now with $\gamma=.9$<jupyter_code># Run for stochastic MDP, gamma = .9
mdp = GridWorldMDP(trans_prob=.8)
v, pi = value_iteration(.9, mdp)
print_value_table(v)
print_policy(pi)<jupyter_output><empty_output><jupyter_text>**Task 2.3.3: (1 Point)** Do you notice any difference between the greedy policy for the two different discount factors. If so, what's the difference, and why do you think this happened? **Your answer:** (fill in here)  Section 3: Model-free Reinforcement Learning In most of Reinforcement Learning (RL) problems, we do not have access to the transition/dynamics model and the reward model. To evaluate a policy in such problems, we use model-free policy evaluation algorithms which rely on interactions with the environment to estimate the state and action values, e.g., Monte Carlo policy evaluation, TD-learning. To find the optimal values and optimal policy in a model-free RL problem, algorithms like Monte Carlo policy iterations, SARSA and Q-learning can be used. In this section, we cover the Q-learning algorithm. 3.1 Q-learningIn the previous section, you solved for $v_*(s)$ and the greedy policy $\pi_*(s)$, with the entire model of the MDP being available to you. Now we consider the model-free case, where we do not have the transition model or the reward model available to us. In this section, you will implement the Q-learning algorithm, an alternative that learns $q$-values from experience, without the need of a model. Q-learning algorithm$\text{Initialize}~\hat{q}(s,a), ~ \forall~ s \in {\cal S},~ a~\in {\cal A} \\\textbf{Repeat}~\text{(for each episode):}\\\quad \text{Initialize}~s\\\qquad \textbf{Repeat}~\text{(for each step in episode):}\\\qquad\quad \text{Choose $a$ from $s$ using policy derived from $\hat{q}$ (e.g., $\epsilon$-greedy)}\\\qquad\quad \text{Take action a, observe r, s'}\\\qquad\quad \hat{q}(s,a) \leftarrow \hat{q}(s,a) + \alpha \left(r + \gamma~\underset{a'}{\text{max}}~\hat{q}(s',a') - \hat{q}(s,a) \right) \\\qquad\quad s \leftarrow s' \\\qquad \text{Until s is terminal}$ **Task 3.1.1: (2 Points)**  Implement an $\epsilon$-greedy policyThe goal of the Q-learning algorithm is to find the optimal policy $\pi_*$, by estimating the state action value function under the optimal policy, i.e., $\hat{q}_*(s, a)$. From $\hat{q}_*(s,a)$, the agent can follow $\pi_*$ by choosing the action that yields the largest expected value for each state, i.e., $\text{argmax}_a~\hat{q}_*(s, a)$. However, when training a Q-learning model, the agent typically follows another policy to explore the environment (instead of the one that maximizes the current Q-values). In reinforcement learning this is known as off-policy learning. Your task is to implement a widely popular exploration policy, known as  the $\epsilon$-greedy policy, in the cell below.An $\epsilon$-greedy policy should:* with probability $\epsilon$ take an uniformly-random action.* otherwise choose the best action according to the estimated state action values.*Hint:* The $\epsilon$-greedy policy can be implemented extra elegantly by calculating the actual resulting sampling distribution.<jupyter_code># Answer:
def eps_greedy_policy(q_values, eps):
    '''
    Creates an epsilon-greedy policy
    :param q_values: set of q-values of shape (num actions,)
    :param eps: probability of taking a uniform random action 
    :return: policy of shape (num actions,)
    '''
    # YOUR CODE HERE
    return policy<jupyter_output><empty_output><jupyter_text>Run the cell below to test your implementation<jupyter_code>import math
mdp = GridWorldMDP()

# Test shape of output
actions = mdp.get_actions()
for eps in (0, 1):
    foo = np.zeros([len(actions)])
    foo[0] = 1.
    eps_greedy = eps_greedy_policy(foo, eps)
    assert foo.shape == eps_greedy.shape, "wrong shape of output"
actions = [i for i in range(10)]
for eps in (0, 1):
    foo = np.zeros([len(actions)])
    foo[0] = 1.
    eps_greedy = eps_greedy_policy(foo, eps)
    assert foo.shape == eps_greedy.shape, "wrong shape of output"

# Test for greedy actions
for a in actions:
    foo = np.zeros([len(actions)])
    foo[a] = 1.
    eps_greedy = eps_greedy_policy(foo, 0)
    assert np.allclose(foo, eps_greedy, rtol=1e-03), "policy is not greedy"

# Test for uniform distribution, when eps=1
eps_greedy = eps_greedy_policy(foo, 1)
assert all(math.isclose(p, eps_greedy[0], rel_tol=1e-03) for p in eps_greedy),\
    "policy does not return a uniform distribution for eps=1"
assert math.isclose(np.sum(eps_greedy), 1.0, rel_tol=1e-03), "policy distribution is not normalized"


print('Test passed, good job!')<jupyter_output><empty_output><jupyter_text>Now it's time to actually implement the Q-learning algorithm. Unlike the Value iteration where there are no direct interactions with the environment, the Q-learning algorithm builds up its estimates by interacting and exploring the environment. To enable the agent to explore the environment a set of helper functions are provided:<jupyter_code>help(GridWorldMDP.reset)
help(GridWorldMDP.step)<jupyter_output><empty_output><jupyter_text>**Task 3.1.2: (4 Points)** Implement your version of Q-learning in the cell below. **Hint:** It might be useful to study the pseudocode provided above.<jupyter_code># Answer:
def q_learning(eps, gamma, mdp):
    q_hat = np.zeros([16, 4]) # state action value table
    pi = np.zeros([16]) # greedy policy table
    alpha = .01

    # YOUR CODE HERE
    return pi, q_hat<jupyter_output><empty_output><jupyter_text>Run Q-learning with for the stochastic MDP with $\epsilon = 1, \gamma=0.99$.<jupyter_code>mdp = GridWorldMDP()
pi, q_hat = q_learning(1, .99, mdp)
print_policy(pi)<jupyter_output><empty_output><jupyter_text>Test your implementation by running the cell below<jupyter_code>test_q_learning(q_hat)<jupyter_output><empty_output><jupyter_text>Run Q-learning with for the stochastic MDP with $\epsilon = 0, \gamma=0.99$.<jupyter_code>mdp = GridWorldMDP()
pi, q_hat = q_learning(0, .99, mdp)
print_policy(pi)<jupyter_output><empty_output><jupyter_text>**Task 3.1.3: (2 Points)** You ran your implementation with $\epsilon$ set to both 0 and 1. Did both values yield the same solution? Why? **Your answer:** (fill in here)  Section 4: Deep Q-learning In this section, you will implement a deep Q-learning network (DQN) to solve one of the problems of the OpenAI gym. Before we get to the implementation, let's first review DQN theory.As we saw in the video lectures, using a neural network as a state action value approximator is a great idea. However, if one tries to use this approach with Q-learning, it's very likely that the optimization will be very unstable. To remediate this, two main ideas are used.- First, we use experience replay, in order to decorrelate the experience samples we obtain when exploring the environment.- Second, we use two networks instead of one, in order to fix the optimization targets. Each of these ideas are explained below. 4.1 Experience replaySince Q-learning is an off-policy algorithm, we may collect data by navigating in the environment using some choice of behavioral / exploratory policy $\mu$ (e.g. $\epsilon$-greedy), while still learning the $\hat{q}$ values for an optimal policy. Experience replay exploits this even further, and re-uses old data, which was collected using whatever exploratory policy we used at that moment (e.g. $\epsilon$-greedy w.r.t. to that data approximate $\hat{q}$ values).Except for re-using already collected data, another advantage of experience replay is that it allows us to decorrelate the data, by sampling experience from very different parts of the environment, rather than using the samples for training in the order they were collected when walking around in the environment.Decorrelating the data is essential for training neural networks. 4.2 Fixing the optimization targetFor a given minibatch sampled from the replay buffer, we'll optimize the weights of only one of the networks (commonly denoted as the "online" network), using the gradients w.r.t a loss function. This loss function is computed as the mean squared error between the current action values, computed according to the **online** network, and the Q targets, computed using the other, **offline network** (which we'll also refer to as the fixed network or target network).That is, the loss function is $$ L(\theta) = \frac{1}{N}\sum_{i=1}^N \left(\hat{q}(s_i,a_i; \theta\right) - y_i)^2~,$$where $N$ is the number of samples in your minibatch, $\hat{q}(s,a;\theta)$ is the state action value estimate, according to the online network (with parameters $\theta$), and $y_t$ is the Q target, computed as$$ y_i = r_i +  \gamma ~\underset{a}{\text{max}}~\hat{q}(s_i', a; \theta^-)~, $$where $\hat{q}(s', a;\theta^-)$ is the action value estimate, according to the offline network (with parameters $\theta^-$).Finally, so that the offline parameters are also updated, we periodically copy the parameters from the online to the offline network. 4.3 Training loop essentialsThe following key components are repeated for every time step $t$ in an episode:1. Sample an action $a_t$ from the $\epsilon$-greedy policy w.r.t. the current estimated $\hat{q}$ values (online network), and execute the action in the environment.1. The current transition $(s_t, a_t, r_{t+1}, s_{t+1})$ which refers to a sequence of the current state, action, immediate reward and next state is stored in the replay buffer.1. An entire mini-batch of transitions is sampled from the replay buffer, and a gradient step is taken to improve the online network. 4.4 Target notationSeveral different optimization targets which are estimated with some $q$ function are often jointly referred to as "TD targets".We strive to be consistent and separate on-policy "TD(0) targets" and off-policy "Q targets" but in other places this distinction may be less clear.  4.5 EnvironmentThe problem you will solve for this task is the inverted pendulum problem. On [Open AIs environment documentation](https://gym.openai.com/envs/CartPole-v0) , the following description is provided:*A pole is attached by an un-actuated joint to a cart, which moves along a frictionless track. The system is controlled by applying a force of +1 or -1 to the cart. The pendulum starts upright, and the goal is to prevent it from falling over. A reward of +1 is provided for every time step that the pole remains upright. The episode ends when the pole is more than 15 degrees from vertical, or the cart moves more than 2.4 units from the center.*Furthermore, the episode will automatically end if 200 steps are reached, as explained [here](https://github.com/openai/gym/wiki/CartPole-v0episode-termination).![title](./cartpole.jpg)  Run the cell below to see a video illustration of the environment<jupyter_code>from IPython.lib.display import YouTubeVideo
YouTubeVideo('46wjA6dqxOM')<jupyter_output><empty_output><jupyter_text>4.6 ImplementationWe'll solve this task using a DQN. Most of the code is provided for you, in the file **dqn_model.py**. This file contains the implementation of a neural network, which is described in the table below (feel free to experiment with different architectures).|Layer 1: units, activation | Layer 2: units, activation | Layer 3: units, activation | Cost function ||---------------------------|----------------------------|----------------------------|---------------|| 100, ReLu                 | 60, ReLu                   | number of actions, linear | MSE           |There are however a few key parts missing from the code, that are to be implemented in the following three functions:- `calc_q_and_take_action`- `calculate_q_targets`- `sample_batch_and_calculate_loss`These will then be called from the function `train_loop_dqn`, which runs the main loop for training the model in the cart-pole environment. **Task 4.6.1: (2 Points)** Calculate Q-values for the current state, and decide on which action to take. Use an epsilon-greedy behavioral policy, and feel free to re-use the `epsilon_greedy_policy` function that you defined for the Q-learning part.This function will be used to control the agent's behavior in the environment, but the actual training will be done later, for entire mini-batches sampled from the replay buffer.<jupyter_code>#Answer:
def calc_q_and_take_action(dqn, state, eps):
    '''
    Calculate Q-values for current state, and take an action according to an epsilon-greedy policy.
    Inputs:
        dqn   - DQN model. An object holding the online / offline Q-networks, and some related methods.
        state  - Current state. Numpy array, shape (1, num_states).
        eps    - Exploration parameter.
    Returns:
        q_online_curr   - Q(s,a) for current state s. Numpy array, shape (1, num_actions) or  (num_actions,).
        curr_action     - Selected action (0 or 1, i.e., left or right), sampled from epsilon-greedy policy. Integer.
    '''
    # FYI:
    # dqn.online_model & dqn.offline_model are Pytorch modules for online / offline Q-networks, which take the state as input, and output the Q-values for all actions.
    # Input shape (batch_size, num_states). Output shape (batch_size, num_actions).

    # YOUR CODE HERE
    return q_online_curr, curr_action<jupyter_output><empty_output><jupyter_text>**Task 4.6.2: (2 Points)** For following task, you will calculate the temporal difference target used for the loss in the deep Q-learning algorithm. Your implementation should adhere to the equation defined above for the Q target of DQNs, with one exception: when s' is terminal, the Q target for it should simply be $ Y_i = r_i$. Why is this necessary? **Your answer:** (fill in here) **Task 4.6.3: (1 Points)** Implement your function which calculates Q target in the following cell.<jupyter_code># Answer:
def calculate_q_targets(q1_batch, r_batch, nonterminal_batch, gamma=.99):
    '''
    Calculates the Q target used for the loss
    : param q1_batch: Batch of q_hat(s', a) from target network. FloatTensor, shape (N, num actions)
    : param r_batch: Batch of rewards. FloatTensor, shape (N,)
    : param nonterminal_batch: Batch of booleans, with False elements if state s' is terminal and True otherwise. BoolTensor, shape (N,)
    : param gamma: Discount factor, float.
    : return: Q target. FloatTensor, shape (N,)
    '''
    # YOUR CODE HERE
    return Y<jupyter_output><empty_output><jupyter_text>Test your implementation by running the cell below<jupyter_code>import torch
import dqn_model
dqn_model.test_calculate_q_targets(calculate_q_targets)<jupyter_output><empty_output><jupyter_text>**Task 4.6.4: (2 Points)** Use the online & offline Q-networks to calculate the Q-values for a minibatch. These will then be used to calculate the mini-batch loss by the end of the function.You will need to define two tensors:- `q_online_curr`: $\hat{q}(s,a; \theta), \ \forall a$- `q_offline_next`: $\hat{q}(s',a; \theta^-), \ \forall a$Take great care to make sure gradient computation is enabled / disabled where it should. `torch.no_grad()` is your friend here (see [Pytorch docs](https://pytorch.org/docs/stable/torch.htmllocally-disabling-gradient-computation)).<jupyter_code># Answer:
def sample_batch_and_calculate_loss(dqn, replay_buffer, batch_size, gamma):
    '''
    Sample mini-batch from replay buffer, and compute the mini-batch loss
    Inputs:
        dqn          - DQN model. An object holding the online / offline Q-networks, and some related methods.
        replay_buffer - Replay buffer object (from which samples will be drawn)
        batch_size    - Batch size
        gamma         - Discount factor
    Returns:
        Mini-batch loss, on which .backward() will be called to compute gradient.
    '''
    # Sample a minibatch of transitions from replay buffer
    curr_state, curr_action, reward, next_state, nonterminal = replay_buffer.sample_minibatch(batch_size)

    # FYI:
    # dqn.online_model & dqn.offline_model are Pytorch modules for online / offline Q-networks, which take the state as input, and output the Q-values for all actions.
    # Input shape (batch_size, num_states). Output shape (batch_size, num_actions).

    # YOUR CODE HERE
    
    q_target = calculate_q_targets(q_offline_next, reward, nonterminal, gamma=gamma)
    loss = dqn.calc_loss(q_online_curr, q_target, curr_action)

    return loss<jupyter_output><empty_output><jupyter_text>Test your implementation by trying to solve the reinforcement learning problem for the Cartpole environment. The `train_loop_dqn` function defined below will be called later.<jupyter_code># Import dependencies
import torch
import numpy as np
import gym
from collections import namedtuple
from dqn_model import DeepQLearningModel, ExperienceReplay
# CPU should be enough, but feel free to play around with this if you want to.
device = torch.device("cpu")
# device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
def train_loop_dqn(dqn, env, replay_buffer, num_episodes, enable_visualization=False, batch_size=64, gamma=.94):        
    Transition = namedtuple("Transition", ["s", "a", "r", "next_s", "t"])
    eps = 1.
    eps_end = .1 
    eps_decay = .001
    tau = 1000
    cnt_updates = 0
    R_buffer = []
    R_avg = []
    for i in range(num_episodes):
        state = env.reset() # Initial state
        state = state[None,:] # Add singleton dimension, to represent as batch of size 1.
        finish_episode = False # Initialize
        ep_reward = 0 # Initialize "Episodic reward", i.e. the total reward for episode, when disregarding discount factor.
        q_buffer = []
        steps = 0
        while not finish_episode:
            if enable_visualization:
                env.render() # comment this line out if you don't want to / cannot render the environment on your system
            steps += 1

            # Take one step in environment. No need to compute gradients,
            # we will just store transition to replay buffer, and later sample a whole batch
            # from the replay buffer to actually take a gradient step.
            q_online_curr, curr_action = calc_q_and_take_action(dqn, state, eps)
            q_buffer.append(q_online_curr)
            new_state, reward, finish_episode, _ = env.step(curr_action) # take one step in the evironment
            new_state = new_state[None,:]
            
            # Assess whether terminal state was reached.
            # The episode may end due to having reached 200 steps, but we should not regard this as reaching the terminal state, and hence not disregard Q(s',a) from the Q target.
            # https://arxiv.org/abs/1712.00378
            nonterminal_to_buffer = not finish_episode or steps == 200
            
            # Store experienced transition to replay buffer
            replay_buffer.add(Transition(s=state, a=curr_action, r=reward, next_s=new_state, t=nonterminal_to_buffer))

            state = new_state
            ep_reward += reward
            
            # If replay buffer contains more than 1000 samples, perform one training step
            if replay_buffer.buffer_length > 1000:
                loss = sample_batch_and_calculate_loss(dqn, replay_buffer, batch_size, gamma)
                dqn.optimizer.zero_grad()
                loss.backward()
                dqn.optimizer.step()

                cnt_updates += 1
                if cnt_updates % tau == 0:
                    dqn.update_target_network()
                
        eps = max(eps - eps_decay, eps_end) # decrease epsilon        
        R_buffer.append(ep_reward)
        
        # Running average of episodic rewards (total reward, disregarding discount factor)
        R_avg.append(.05 * R_buffer[i] + .95 * R_avg[i-1]) if i > 0 else R_avg.append(R_buffer[i])

        print('Episode: {:d}, Total Reward (running avg): {:4.0f} ({:.2f}) Epsilon: {:.3f}, Avg Q: {:.4g}'.format(i, ep_reward, R_avg[-1], eps, np.mean(np.array(q_buffer))))
        
        # If running average > 195 (close to 200), the task is considered solved
        if R_avg[-1] > 195:
            return R_buffer, R_avg
    return R_buffer, R_avg<jupyter_output><empty_output><jupyter_text>The following cell performs the actual training. A working implementation should start to improve after 500 episodes. An episodic reward of around 200 is likely to be achieved after 800 episodes for a batchsize of 128, and 1000 episodes for a batchsize of 64.**Note:** The `enable_visualization` flag controls whether a visualization of the cart-pole environment will be plotted. In many environments, this is however not working properly, for which reason it is disabled by default.<jupyter_code># Create the environment
env = gym.make("CartPole-v0")

# Enable visualization? Does not work in all environments.
enable_visualization = False

# Initializations
num_actions = env.action_space.n
num_states = env.observation_space.shape[0]
num_episodes = 1200 
batch_size = 128
gamma = .94
learning_rate = 1e-4

# Object holding our online / offline Q-Networks
dqn = DeepQLearningModel(device, num_states, num_actions, learning_rate)

# Create replay buffer, where experience in form of tuples <s,a,r,s',t>, gathered from the environment is stored 
# for training
replay_buffer = ExperienceReplay(device, num_states)

# Train
R, R_avg = train_loop_dqn(dqn, env, replay_buffer, num_episodes, enable_visualization=enable_visualization, batch_size=batch_size, gamma=gamma)
# close window
if enable_visualization:
    env.close()<jupyter_output><empty_output><jupyter_text>According to the code above, the code in the provided .py file, and the documentation of the environment, answer the following questions: **Task 4.6.5: (2 Points)** What is the state for this problem? **Your answer:** (fill in here) **Task 4.6.6: (2 Points)** How often is the offline network updated to match the online one? Why do we need to do this? **Your answer:** (fill in here) **Optional Questions**There may be three reasons for the episode to end:1. The cart slides too far away1. The pendulum falls too low1. 200 time steps have passedAs mentioned before, we replace the Q target with the immediate reward only in case 1 and 2. In the third case however, the Q target remains untouched.Please answer the following questions:**Task 4.6.7: (3 Points)** How we treat this matter will have an influence on the Q-values being learned, and how they may be interpreted. Assuming we treat it as explained, and that we have managed to converge successfully, describe (in words and/or with mathematical expressions) what the Q-values we have learnt represent. **Your answer:** (fill in here) **Task 4.6.8: (2 Points)** If we would treat case 3 the same as case 1 and 2, we would actually end up with a Partially Observable Markov Decision Process (POMDP). What would we need to add to our observations, in order to obtain an observable MDP again? **Your answer:** (fill in here) Run the cell below to visualize your final policy (the greedy rather than epsilon-greedy one) in an episode from this environment.**Note:** In order to visualize, the env.render() command needs to work out on your system (see comment a few cells above).<jupyter_code>import time
num_episodes = 10
env = gym.make("CartPole-v0")

if enable_visualization:
    for i in range(num_episodes):
            state = env.reset() #reset to initial state
            state = state[None,:]
            terminal = False # reset terminal flag
            while not terminal:
                #env.render()
                time.sleep(.05)
                with torch.no_grad():
                    q_values = dqn.online_model(torch.tensor(state, dtype=torch.float, device=device)).cpu().numpy()
                policy = eps_greedy_policy(q_values.squeeze(), .1) # greedy policy
                action = np.random.choice(num_actions, p=policy)
                state, reward, terminal, _ = env.step(action) # take one step in the evironment
                state = state[None,:]
    # close window
    env.close();<jupyter_output><empty_output><jupyter_text>Plot the episodic rewards obtained throughout the optimization, together with a moving average of it (since the episodic reward is usually very noisy).<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt

rewards = plt.plot(R, alpha=.4, label='R')
avg_rewards = plt.plot(R_avg,label='avg R')
plt.legend(bbox_to_anchor=(1.01, 1), loc=2, borderaxespad=0.)
plt.xlabel('Episode')
plt.ylim(0, 210)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10874113152628706, 'fraction_numerical': 0.014053119883572858, 'mean_word_length': 4.005919180421173, 'pattern_counts': {'":': 0, '<': 128, '<?xml version=': 0, '>': 132, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '31', 'dir': 'jupyter-structured-clean-dedup', 'id': '316375', 'license': 'MIT', 'n_tokens_mistral': 13221, 'n_tokens_neox': 12432, 'n_words': 5571, 'path': 'home-assignments/HA3/HA3.ipynb', 'repo_name': 'JulianoLagana/deep-machine-learning', 'size': '43976'}