hw3_v4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Distributed Q-Learning and SARSA\n",
    "\n",
    "The goal of this assignment is to implement both single-core and distributed versions of two temporal difference (TD) reinforcement learning algorithms, Q-Learning and SARSA. In particuar, Q-Learning and SARSA will be run in a Markov Decision Process environment in order to compute policies that optimize expected infinite horizon discounted cummulative reward.\n",
    "\n",
    "The relevant content about Q-Learning and SARSA are in the following course notes from CS533.\n",
    "\n",
    "https://oregonstate.instructure.com/courses/1719746/files/74944693/download?wrap=1\n",
    "\n",
    "\n",
    "## Recap of Q-Learning and SARSA \n",
    "\n",
    "Q-Learning and SARSA appear to be extremely similar algorithms at the code level. In particular, their update formulas are as follows:\n",
    "\n",
    "\\begin{equation}\n",
    "\\mbox{SARSA:  } Q(s,a) \\leftarrow Q(s,a) + \\alpha\\cdot \\left(r + \\beta Q(s',a') - Q(s,a)\\right) \\\\\n",
    "\\mbox{Q-Learning:  } Q(s,a) \\leftarrow Q(s,a) + \\alpha\\cdot \\left(r + \\beta \\max_a' Q(s',a') - Q(s,a)\\right) \n",
    "\\end{equation}\n",
    "where $s'$ and $r$ are the next state and reward after taking action $a$ in state $s$. Further, for SARSA, $a'$ is the action that was taken by the agent in $s'$. \n",
    "\n",
    "While these updates a are similar, the algorithms are different in a fundamental way. SARSA is an on-policy algorithm, which aims to learn the value of the policy that is being used to collect data (we call this the behavior policy). In the case of policy optimization, this behavior policy is an exploration-exploitation policy. This is why $a'$ in the SARSA algorithm is based on the action actually taken by the behavior policy. \n",
    "\n",
    "Rather, Q-Learning is an off-policy algorithm, which can learn from any set of experience tuples, regardless of how they were collected. In particular, notice that Q-Learning is not sensitive to what action (if any) was taken in $s'$, while SARSA must be given the action that was actually taken in $s'$. Even if the exploration policy were completely random, Q-Learning will converge in the limit to an optimal policy under standard assumptions on the learning rate decay. \n",
    "\n",
    "The off-policy versus on-policy difference can lead the algorithms to sometimes learn different policies in practice. The assignment below will give you the opportunity to implement both SARSA and Q-Learning and to observe and explain such differences. After first implementing a single-core version of the algorithms, you will then implement a distributed version of Q-Learning. Note that the off-policy nature of Q-Learning makes it more directly compatible with distributed implementations compared to SARSA, since the experience need not come from a particular behavior policy. \n",
    "\n",
    "To complete the exercise, you need to finish all parts of this notebook. You also need to turn in a report---the notebook exercises will indicate what should be included in the report.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You will need to uncomment the following pip commands if the libraries need to be installed. \n",
    "# You may get some errors related to readchar, but they should not break the project.\n",
    "\n",
    "#!pip install --user numpy\n",
    "#!pip install --user gym\n",
    "#!pip install --user tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import ray\n",
    "import time\n",
    "import math\n",
    "from copy import deepcopy\n",
    "import matplotlib.pyplot as plt\n",
    "from random import randint, choice, uniform\n",
    "import random\n",
    "%matplotlib inline\n",
    "import pickle\n",
    "import numpy as np\n",
    "import tqdm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "## FrozenLake  \n",
    "<span style=\"color:red\">(The game code and transition probability is different from assignment 2)</span>  \n",
    "We will use the FrozenLake environment as the MDP environment for this experiment. This is a type of gridworld environment, whose size (number of states) can be controlled by adjusting the grid dimensions. The environment is intended to model the process of navigating a frozen lake, while avoiding falling into holes with the objective of reaching a goal location. \n",
    "\n",
    "The environment is defined as follows:\n",
    "\n",
    "- The environment is a rectangular grid of states/cells. There are four different types of cells as indicated by the following cell labels: \n",
    "\n",
    "    - S labels the starting/initial cell, always in the top left corner\n",
    "    \n",
    "    - F labels frozen cells that are safe to step on\n",
    "\n",
    "    - H labels holes and if the agent enters a hole cell there is a pentalty of -1000 and the episode ends\n",
    "\n",
    "    - G labels the goal cell and when reached gives a reward of 1000 and the episode ends\n",
    "\n",
    "- There are four possible actions (Left, Right, Down, Up). \n",
    "\n",
    "- The transition function moves the agent in the expected direction with 0.97 probability, and there is a 0.03 probability of transitioning to one of the other randomly selected directions. \n",
    "\n",
    "- There is a reward of -1 for each action taken by the agent, which is intended to encourage the agent to reach the goal as fast as possible. \n",
    "\n",
    "- Episodes end whenever the agent falls in a hole or reaches the goal. An end-of-episode is modeled by transitioning to a zero-reward terminal state (all actions lead to that state). \n",
    "\n",
    "The version we are using for assignment 3 is a modified version of the environment at the following location.   \n",
    "  \n",
    "Source: https://github.com/openai/gym/blob/master/gym/envs/toy_text/frozen_lake.py  \n",
    "\n",
    "Execute the following cell to initialize the MDP environments. (You do not need to change the code in this part.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from contextlib import closing\n",
    "\n",
    "from six import StringIO, b\n",
    "\n",
    "from gym import utils\n",
    "from gym.envs.toy_text import discrete\n",
    "\n",
    "LEFT = 0\n",
    "DOWN = 1\n",
    "RIGHT = 2\n",
    "UP = 3\n",
    "np.set_printoptions(threshold=sys.maxsize, linewidth=sys.maxsize, precision = 2)\n",
    "#TransitionProb = [0.7, 0.1, 0.1, 0.1]\n",
    "#TransitionProb = [1, 0, 0, 0]\n",
    "TransitionProb = [0.97, 0.01, 0.01, 0.01]\n",
    "def generate_row(length, h_prob):\n",
    "    row = np.random.choice(2, length, p=[1.0 - h_prob, h_prob])\n",
    "    row = ''.join(list(map(lambda z: 'F' if z == 0 else 'H', row)))\n",
    "    return row\n",
    "\n",
    "\n",
    "def generate_map(shape):\n",
    "    \"\"\"\n",
    "\n",
    "    :param shape: Width x Height\n",
    "    :return: List of text based map\n",
    "    \"\"\"\n",
    "    h_prob = 0.1\n",
    "    grid_map = []\n",
    "\n",
    "    for h in range(shape[1]):\n",
    "\n",
    "        if h == 0:\n",
    "            row = 'SF'\n",
    "            row += generate_row(shape[0] - 2, h_prob)\n",
    "        elif h == 1:\n",
    "            row = 'FF'\n",
    "            row += generate_row(shape[0] - 2, h_prob)\n",
    "\n",
    "        elif h == shape[1] - 1:\n",
    "            row = generate_row(shape[0] - 2, h_prob)\n",
    "            row += 'FG'\n",
    "        elif h == shape[1] - 2:\n",
    "            row = generate_row(shape[0] - 2, h_prob)\n",
    "            row += 'FF'\n",
    "        else:\n",
    "            row = generate_row(shape[0], h_prob)\n",
    "\n",
    "        grid_map.append(row)\n",
    "        del row\n",
    "\n",
    "    return grid_map\n",
    "\n",
    "MAPS = {\n",
    "    \n",
    "    \"4x4\": [\n",
    "        \"SFFF\",\n",
    "        \"FHFH\",\n",
    "        \"FFFF\",\n",
    "        \"HFFG\"\n",
    "    ],\n",
    "    \"8x8\": [\n",
    "        \"SFFFFFFF\",\n",
    "        \"FFFFFFFF\",\n",
    "        \"FFFHFFFF\",\n",
    "        \"FFFFFHFF\",\n",
    "        \"FFFHFFFF\",\n",
    "        \"FHHFFFHF\",\n",
    "        \"FHFFHFHF\",\n",
    "        \"FFFHFFFG\"\n",
    "    ],\n",
    "    \"Dangerous Hallway\": [\n",
    "        \"SFFFFFFF\",\n",
    "        \"FFFFFFFF\",\n",
    "        \"HFHHHFFF\",\n",
    "        \"HFHHHFFF\",\n",
    "        \"HFHHHFFF\",\n",
    "        \"HFHHHFFF\",\n",
    "        \"HFFFFFFF\",\n",
    "        \"FGFFFFFF\"\n",
    "    ],\n",
    "    \"16x16\": [\n",
    "        \"SFFFFFFFFHFFFFHF\",\n",
    "        \"FFFFFFFFFFFFFHFF\",\n",
    "        \"FFFHFFFFHFFFFFFF\",\n",
    "        \"FFFFFFFFHFFFFFFF\",\n",
    "        \"FFFFFFFFFFFFFFFF\",\n",
    "        \"FFHHFFFFFFFHFFFH\",\n",
    "        \"FFFFFFFFFFFFFFFF\",\n",
    "        \"FFFFFHFFFFFFHFFF\",\n",
    "        \"FFFFFHFFFFFFFFFH\",\n",
    "        \"FFFFFFFHFFFFFFFF\",\n",
    "        \"FFFFFFFFFFFFHFFF\",\n",
    "        \"FFFFFFHFFFFFFFFF\",\n",
    "        \"FFFFFFFFHFFFFFFF\",\n",
    "        \"FFFFFFFFFHFFFFHF\",\n",
    "        \"FFFFFFFFFFHFFFFF\",\n",
    "        \"FFFHFFFFFFFFFFFG\",\n",
    "    ],\n",
    "    \n",
    "    \"32x32\": [\n",
    "        'SFFFFFFFFFFFFFFFFFFFFFFFFFHFFFFF',\n",
    "        'FFFFFFFFHFFFFFFFFFFFFFFFFFHFFFFF',\n",
    "        'FFFHFFFFFFFFHFFHFFFFFFFFFFFFFFFF',\n",
    "        'FFFFFFFFFFFFFFHFHHFHFHFFFFFHFFFH',\n",
    "        'FFFFHFFFFFFFFFFFFFFFHFHFFFFFFFHF',\n",
    "        'FFFFFHFFFFFFFFFFHFFFFFFFFFFHFFFF',\n",
    "        'FFHHFFFFHFFFFFFFFFFFFFFFFFFFFFFF',\n",
    "        'FFFHFFFFFFFFFFHFFFHFHFFFFFFFFHFF',\n",
    "        'FFFFHFFFFFFHFFFFHFHFFFFFFFFFFFFH',\n",
    "        'FFFFHHFHFFFFHFFFFFFFFFFFFFFFFFFF',\n",
    "        'FHFFFFFFFFFFHFFFFFFFFFFFHHFFFHFH',\n",
    "        'FFFHFFFHFFFFFFFFFFFFFFFFFFFFHFFF',\n",
    "        'FFFHFHFFFFFFFFHFFFFFFFFFFFFHFFHF',\n",
    "        'FFFFFFFFFFFFFFFFHFFFFFFFHFFFFFFF',\n",
    "        'FFFFFFHFFFFFFFFHHFFFFFFFHFFFFFFF',\n",
    "        'FFHFFFFFFFFFHFFFFFFFFFFHFFFFFFFF',\n",
    "        'FFFHFFFFFFFFFHFFFFHFFFFFFHFFFFFF',\n",
    "        'FFFFFFFFFFFFFFFFFFFFFFFFFFHFFFFF',\n",
    "        'FFFFFFFFHFFFFFFFHFFFFFFFFFFFFFFH',\n",
    "        'FFHFFFFFFFFFFFFFFFHFFFFFFFFFFFFF',\n",
    "        'FFFFFFFHFFFFFFFFFFFFFFFFFFFFFFFF',\n",
    "        'FFFFFFFFFFFFFFFHFFFFHFFFFFFFHFFF',\n",
    "        'FFHFFFFHFFFFFFFFFHFFFFFFFFFFFHFH',\n",
    "        'FFFFFFFFFFHFFFFHFFFFFFFFFFFFFFFF',\n",
    "        'FFFFFFFFFFFFFFFFFHHFFHHHFFFHFFFF',\n",
    "        'FFFFFFFFFFFFFFHFFFFHFFFFFFFHFFFF',\n",
    "        'FFFFFFFHFFFFFFFFFFFFFFFFFFFFFFFF',\n",
    "        'FFFFFHFFFFFFFFFFFFFFFFHFFHFFFFFF',\n",
    "        'FFFFFFFHFFFFFFFFFHFFFFFFFFFFFFFF',\n",
    "        'FFFFFFFFFFFFFFFFFFFFFFFFHFFFFFFF',\n",
    "        'FFFFFFFFFFFFFFFFFFFFFFFFHFFFFFFF',\n",
    "        'FFFFFFFFFFFFFFFHFFFFFFFFHFFFFFFG',\n",
    "    ]\n",
    "}\n",
    "\n",
    "\n",
    "def generate_random_map(size=8, p=0.8):\n",
    "    \"\"\"Generates a random valid map (one that has a path from start to goal)\n",
    "    :param size: size of each side of the grid\n",
    "    :param p: probability that a tile is frozen\n",
    "    \"\"\"\n",
    "    valid = False\n",
    "\n",
    "    # BFS to check that it's a valid path.\n",
    "    def is_valid(arr, r=0, c=0):\n",
    "        if arr[r][c] == 'G':\n",
    "            return True\n",
    "\n",
    "        tmp = arr[r][c]\n",
    "        arr[r][c] = \"#\"\n",
    "\n",
    "        # Recursively check in all four directions.\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        for x, y in directions:\n",
    "            r_new = r + x\n",
    "            c_new = c + y\n",
    "            if r_new < 0 or r_new >= size or c_new < 0 or c_new >= size:\n",
    "                continue\n",
    "\n",
    "            if arr[r_new][c_new] not in '#H':\n",
    "                if is_valid(arr, r_new, c_new):\n",
    "                    arr[r][c] = tmp\n",
    "                    return True\n",
    "\n",
    "        arr[r][c] = tmp\n",
    "        return False\n",
    "\n",
    "    while not valid:\n",
    "        p = min(1, p)\n",
    "        res = np.random.choice(['F', 'H'], (size, size), p=[p, 1-p])\n",
    "        res[0][0] = 'S'\n",
    "        res[-1][-1] = 'G'\n",
    "        valid = is_valid(res)\n",
    "    return [\"\".join(x) for x in res]\n",
    "\n",
    "\n",
    "class FrozenLakeEnv(discrete.DiscreteEnv):\n",
    "    \"\"\"\n",
    "    Winter is here. You and your friends were tossing around a frisbee at the park\n",
    "    when you made a wild throw that left the frisbee out in the middle of the lake.\n",
    "    The water is mostly frozen, but there are a few holes where the ice has melted.\n",
    "    If you step into one of those holes, you'll fall into the freezing water.\n",
    "    At this time, there's an international frisbee shortage, so it's absolutely imperative that\n",
    "    you navigate across the lake and retrieve the disc.\n",
    "    However, the ice is slippery, so you won't always move in the direction you intend.\n",
    "    The surface is described using a grid like the following\n",
    "\n",
    "        SFFF\n",
    "        FHFH\n",
    "        FFFH\n",
    "        HFFG\n",
    "\n",
    "    S : starting point, safe\n",
    "    F : frozen surface, safe\n",
    "    H : hole, fall to your doom\n",
    "    G : goal, where the frisbee is located\n",
    "\n",
    "    The episode ends when you reach the goal or fall in a hole.\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    metadata = {'render.modes': ['human', 'ansi']}\n",
    "\n",
    "    def __init__(self, desc=None, map_name=\"4x4\"):\n",
    "        if desc is None and map_name is None:\n",
    "            desc = generate_random_map()\n",
    "        elif desc is None:\n",
    "            desc = MAPS[map_name]\n",
    "        self.desc = desc = np.asarray(desc,dtype='c')\n",
    "        self.nrow, self.ncol = nrow, ncol = desc.shape\n",
    "        self.reward_range = (0, 1)\n",
    "\n",
    "        nA = 4\n",
    "        nS = nrow * ncol\n",
    "        self.nS = nS\n",
    "        \n",
    "        isd = np.array(desc == b'S').astype('float64').ravel()\n",
    "        isd /= isd.sum()\n",
    "\n",
    "        rew_hole = -1000\n",
    "        rew_goal = 1000\n",
    "        rew_step = -1\n",
    "        \n",
    "        exit = nrow * ncol\n",
    "        P = {s : {a : [] for a in range(nA)} for s in range(nS + 1)}\n",
    "        \n",
    "        def to_s(row, col):\n",
    "            return row*ncol + col\n",
    "        \n",
    "        def inc(row, col, a):\n",
    "            if a == LEFT:\n",
    "                col = max(col-1,0)\n",
    "            elif a == DOWN:\n",
    "                row = min(row+1,nrow-1)\n",
    "            elif a == RIGHT:\n",
    "                col = min(col+1,ncol-1)\n",
    "            elif a == UP:\n",
    "                row = max(row-1,0)\n",
    "            return (row, col)\n",
    "\n",
    "        for row in range(nrow):\n",
    "            for col in range(ncol):\n",
    "                s = to_s(row, col)\n",
    "                for a in range(4):\n",
    "                    li = P[s][a]\n",
    "                    letter = desc[row, col]\n",
    "                    if letter in b'H':\n",
    "                        li.append((1.0, exit, -1000, True))\n",
    "                    elif letter in b'G':\n",
    "                        li.append((1.0, exit, 1000, True))\n",
    "                    else:\n",
    "                        for b, p in zip([a, (a+1)%4, (a+2)%4, (a+3)%4], TransitionProb):\n",
    "                            newrow, newcol = inc(row, col, b)\n",
    "                            newstate = to_s(newrow, newcol)\n",
    "                            newletter = desc[newrow, newcol]\n",
    "                            rew = rew_step\n",
    "                            li.append((p, newstate, rew, False))\n",
    "\n",
    "        super(FrozenLakeEnv, self).__init__(nS, nA, P, isd)\n",
    "\n",
    "    def render(self, mode='human'):\n",
    "        outfile = StringIO() if mode == 'ansi' else sys.stdout\n",
    "\n",
    "        row, col = self.s // self.ncol, self.s % self.ncol\n",
    "        desc = self.desc.tolist()\n",
    "        desc = [[c.decode('utf-8') for c in line] for line in desc]\n",
    "        if self.s < self.nS:\n",
    "            desc[row][col] = utils.colorize(desc[row][col], \"red\", highlight=True)\n",
    "        else:\n",
    "            outfile.write(\"exit\\n\")\n",
    "        if self.lastaction is not None:\n",
    "            outfile.write(\"  ({})\\n\".format([\"Left\",\"Down\",\"Right\",\"Up\"][self.lastaction]))\n",
    "        else:\n",
    "            outfile.write(\"\\n\")\n",
    "        outfile.write(\"\\n\".join(''.join(line) for line in desc)+\"\\n\")\n",
    "\n",
    "        if mode != 'human':\n",
    "            with closing(outfile):\n",
    "                return outfile.getvalue()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "***\n",
    "## Initializations\n",
    "\n",
    "Run the following cell to initilize maps of different sizes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "#map_4 = (MAPS[\"4x4\"], 4)\n",
    "#map_8 = (MAPS[\"8x8\"], 8)\n",
    "#map_32 = (MAPS[\"32x32\"], 32)\n",
    "#map_50 = (generate_map((50,50)), 50)\n",
    "#map_110 = (generate_map((110,110)), 110)\n",
    "\n",
    "map_DH = (MAPS[\"Dangerous Hallway\"], 8)\n",
    "map_16 = (MAPS[\"16x16\"], 16)\n",
    "\n",
    "MAP = map_DH\n",
    "map_size = MAP[1]\n",
    "run_time = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper Function\n",
    "The following will be used to plot the performance of learning and display the learned value function. Note that both SARSA and Q-Learning produce Q-function tables, which store a value for each state-action pair. Given a Q-function $Q(s,a)$, the corresponding value function is given by $V(s)=\\max_a Q(s,a)$. This relation is used to visualize the value function learned for the environment. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_result(total_rewards, learning_num, legend):\n",
    "    print(\"\\nLearning Performance:\\n\")\n",
    "    episodes = []\n",
    "    for i in range(len(total_rewards)):\n",
    "        episodes.append(i * learning_num + 1)\n",
    "        \n",
    "    plt.figure(num = 1)\n",
    "    fig, ax = plt.subplots()\n",
    "    plt.plot(episodes, total_rewards)\n",
    "    plt.title('performance')\n",
    "    plt.legend(legend)\n",
    "    plt.xlabel(\"Episodes\")\n",
    "    plt.ylabel(\"total rewards\")\n",
    "    plt.show()\n",
    "    \n",
    "def plot_image(q_table, MAP):\n",
    "    \n",
    "    best_value = np.max(q_table, axis = 1)[:-1].reshape((map_size,map_size))\n",
    "    best_policy = np.argmax(q_table, axis = 1)[:-1].reshape((map_size,map_size))\n",
    "    \n",
    "    print(\"\\n\\nBest Q-value and Policy:\\n\")\n",
    "    fig, ax = plt.subplots()\n",
    "    im = ax.imshow(best_value)\n",
    "\n",
    "    for i in range(best_value.shape[0]):\n",
    "        for j in range(best_value.shape[1]):\n",
    "            if MAP[i][j] in 'GH':\n",
    "                arrow = MAP[i][j]\n",
    "            elif best_policy[i, j] == 0:\n",
    "                arrow = '<'\n",
    "            elif best_policy[i, j] == 1:\n",
    "                arrow = 'v'\n",
    "            elif best_policy[i, j] == 2:\n",
    "                arrow = '>'\n",
    "            elif best_policy[i, j] == 3:\n",
    "                arrow = '^'\n",
    "            if MAP[i][j] in 'S':\n",
    "                arrow = 'S ' + arrow\n",
    "            text = ax.text(j, i, arrow,\n",
    "                           ha = \"center\", va = \"center\", color = \"black\")\n",
    "            \n",
    "    cbar = ax.figure.colorbar(im, ax = ax)\n",
    "    \n",
    "    fig.tight_layout()\n",
    "    plt.show() \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulator\n",
    "\n",
    "We now create a simulator corresponding to the environment that we want to train and test the agent in. The simulator always maintains a current state, which changes using the following functions:  \n",
    "- simulator.reset(): Reset the simulator so that the current state is the initial state.   \n",
    "- simulator.step(action): take the specified action in the current state, which returns the tuple (next_state, reward, done, info) and sets the internal current stae to be next_state. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "simulator = FrozenLakeEnv(desc = MAP[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# Non-Distributed RL Agents\n",
    "\n",
    "In this part, you will implement Q-learning and SARSA on two maps: Dangerous Hall and the Size 16 map. \n",
    "\n",
    "$\\epsilon$-greedy exploration will be used as the exploration strategy with a fixed value of $\\epsilon$. \n",
    "\n",
    "- Suggested learning episodes ---  Dangerous Hall map = 30000 and Size 16 map = 100,000\n",
    "\n",
    "A typical way to evaluate the learning performance of an RL agent is as follows. The agent will learning using an explore-exploit policy for \"test_interval\" number of episodes. After each \"test_interval\" learning episodes, exploration is turned off and the performance of the greedy policy is evaluated. This is done by defining the policy as $\\pi(s)=\\arg\\max_a Q(s,a)$ and then running the policy for a specified number of episodes and averaging the results. \n",
    "\n",
    "- Evaluation --- by default testing is done every \"test_interval\" episodes, but testing can be turned off by setting the do_test argument to false. \n",
    "  \n",
    "In this part of the assignment you need to do the following. \n",
    "\n",
    "- Use both SARSA and Q-Learning to learn policies for each of the two maps using learning rates of 0.001 and 0.1 (using the default value of $\\epsilon$). \n",
    "\n",
    "- Use the better of the two learning rates to learning policies using SARSA and Q-Learning on each of the two maps using $\\epsilon$ values of 0.3, 0.05.\n",
    "\n",
    "### Your final report for the asignment should include the following. \n",
    "\n",
    "1. Provide the learning curves for the above experiments. Clearly label the curves by the parameters used. \n",
    "\n",
    "2. Did you observe differences for SARSA when using the two different learning rates? If there were significant differences, what were they and how can you explain them?  \n",
    "\n",
    "3. Repeat (2) for Q-Learning.\n",
    "\n",
    "4. Did you observe differences for SARSA when using different values of $\\epsilon$? If there were significant differences, what were they and how do you explain them?\n",
    "\n",
    "5. Repeat (4) for Q-Learning. \n",
    "\n",
    "6. For the map \"Dangerous Hallway\" did you observe differences in the policies learned by SARSA and Q-Learning for the two values of epsilon (there should be differences between Q-learning and SARSA for at least one value)? If you observed a difference, give your best explanation for why Q-learning and SARSA found different solutions.\n",
    "\n",
    "\n",
    "***\n",
    "## TDagent\n",
    "The parent calss of Q-learning and SARSA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "class agent():\n",
    "    def __init__(self, epsilon, learning_rate, learning_episodes, map_size, \n",
    "                 test_interval = 100, action_space = 4, beta = 0.999, do_test = True):\n",
    "        self.beta = beta\n",
    "        self.epsilon = epsilon\n",
    "        self.test_interval = test_interval\n",
    "        self.batch_num = learning_episodes // test_interval\n",
    "        self.action_space = action_space\n",
    "        self.state_space = map_size * map_size + 1\n",
    "        self.q_table = np.zeros((self.state_space, self.action_space))\n",
    "        self.learning_rate = learning_rate\n",
    "        self.do_test = False\n",
    "        \n",
    "    def explore_or_exploit_policy(self, curr_state):\n",
    "        #INSERT YOUR CODE HERE\n",
    "        \n",
    "        if random.random()>self.epsilon:\n",
    "            return self.q_table[curr_state].argmax()\n",
    "        else:\n",
    "            return np.random.randint(4,size=1)[0]\n",
    "            \n",
    "        \n",
    "        \n",
    "    def greedy_policy(self, curr_state):\n",
    "        #INSERT YOUR CODE HERE\n",
    "        \n",
    "        return self.q_table[curr_state].argmax()\n",
    "        \n",
    "    \n",
    "    def learn_and_evaluate(self):\n",
    "        total_rewards = []\n",
    "        for i in tqdm.tqdm(range(self.batch_num), desc=\"Test Number\"):\n",
    "            #INSERT YOUR CODE HERE\n",
    "            rewards = self.learn()\n",
    "            policy = None\n",
    "            if self.do_test:\n",
    "                policy = {}\n",
    "                for i in range(self.state_space):\n",
    "                    policy[i] = self.greedy_policy(i)\n",
    "                average_reward = self.evaluate(policy)\n",
    "                print(average_reward)\n",
    "            total_rewards.append(rewards)\n",
    "        return total_rewards, self.q_table\n",
    "    \n",
    "    def evaluate(self, policy_func, trials = 100, max_steps = 1000):\n",
    "        \n",
    "        total_reward = 0\n",
    "        for _ in range(trials):\n",
    "            simulator.reset()\n",
    "            done = False\n",
    "            steps = 0\n",
    "            observation, reward, done, info = simulator.step(policy_func[0])\n",
    "            total_reward += (self.beta ** steps) * reward\n",
    "            steps += 1\n",
    "            while not done and steps < 1000:\n",
    "                observation, reward, done, info = simulator.step(policy_func[observation])\n",
    "                total_reward += (self.beta ** steps) * reward\n",
    "                steps += 1\n",
    "        \n",
    "        return total_reward / trials\n",
    "    \n",
    "    def learn(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q-learning Agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QLAgent(agent):\n",
    "    def __init__(self, epsilon, learning_rate, learning_episodes, map_size,\n",
    "                 test_interval = 100, action_space = 4, beta = 0.999, do_test = True):\n",
    "        super().__init__(epsilon, learning_rate, learning_episodes, map_size, \n",
    "                         test_interval = test_interval, action_space = action_space, beta = beta, do_test = do_test)\n",
    "        self.agent_name = \"Q-learning Agent\"\n",
    "        \n",
    "    def learn(self):\n",
    "        total_rewards = 0\n",
    "        for _ in range(self.test_interval):\n",
    "            #INSERT YOUR CODE HERE\n",
    "            \n",
    "            simulator.reset()\n",
    "            state = 0\n",
    "            action = self.explore_or_exploit_policy(state)\n",
    "            done = False\n",
    "            while not done:\n",
    "                s_dash, reward, done, _ = simulator.step(action)\n",
    "                a_dash = self.greedy_policy(s_dash)\n",
    "                self.q_table[state][action] = self.q_table[state][action] + self.learning_rate*(reward + self.beta*self.q_table[s_dash][a_dash]-self.q_table[state][action])\n",
    "                state = s_dash\n",
    "                action = a_dash\n",
    "                total_rewards += reward\n",
    "        return total_rewards/self.test_interval\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Test Number: 100%|██████████| 300/300 [00:04<00:00, 66.51it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Learning time:\n",
      "\n",
      "4.514949083328247\n",
      "\n",
      "Learning Performance:\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<Figure size 432x288 with 0 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZAAAAEWCAYAAABIVsEJAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzsnXmYXFWZ/z9vVXVVdfW+ZessHZJA\nQsJiCLsoqywiICOKMILKiDMqojg67guiozMqiojzY1MQBRVUEJCdyB5ICAnZyL501k7va1VX1/n9\ncZe6VV1VXel0pZvwfp6nn66667l17z3f8y7nHDHGoCiKoij7im+0C6AoiqK8PVEBURRFUYaFCoii\nKIoyLFRAFEVRlGGhAqIoiqIMCxUQRVEUZViogCjKPiAih4nIUhHpFJHPj3Z5FGU0CYx2ARTlbcZX\ngIXGmHeNdkEUZbRRC0RR8kBEnMbWNGDlfh5DUQ4KVECUgx4R2SwiXxORVSLSKiK/EZGwve58EXlD\nRNpE5CUROTJtv/8SkeVAt4g8A5wG3CwiXSJyqIhUiMjdItIkIltE5Jsi4rP3/7iIvCgiN4pIC/Dd\ntGVtIrJRRE6yl28TkT0icqWnDO+3XWYd9vrvetY1iIgRkStFZKuI7BWRb3jW+0Xk6yKywXa5LRGR\nKfa62SLypIi0iMhbIvLhAt8G5WDEGKN/+ndQ/wGbgRXAFKAaeBG4AZgP7AGOB/zAlfa2Ic9+b9j7\nFdvLFgL/5jn23cCDQBnQAKwFrrLXfRyIA9dguYuLPcs+YZ/zBmAr8CsgBLwP6ARK7WOcChyB1dg7\nEtgNXGSvawAMcJt97KOAKDDHXv9l4E3gMEDs9TVACbDNLkPA/h32AnNH+17p39vrTy0Q5Z3CzcaY\nbcaYFuAHwEeBTwH/zxizyBgzYIy5C6sCPsGz3032fr3pBxQRP/AR4GvGmE5jzGbgp8DHPJvtMMb8\n0hgT9xxjkzHmN8aYAeCPWAJ1vTEmaox5AogBMwGMMQuNMW8aYxLGmOXAvcB704ryPWNMrzFmGbAM\nSygA/g34pjHmLWOxzBjTDJwPbLbLEDfGvA48AHxoX39U5Z2N+mSVdwrbPJ+3AJOw4hlXisg1nnVB\ne12m/dKptbffknbs+iH23+353AtgjElfVgogIscDPwLm2ecKAX9OO94uz+ceZ18sYdqQ4fzTgONF\npM2zLAD8LsO2ipIVtUCUdwpTPJ+nAjuwKvcfGGMqPX8RY8y9nm1zDVe9F+jHqpC9x96e5/758Afg\nIWCKMaYC+D8sd1Q+bANmZFn+z7TrLjXG/Md+llV5h6ECorxT+KyITBaRauDrWK6j24B/F5HjxaLE\nDlqX5XNA2wX1J+AHIlImItOA64B7RrDcZUCLMaZPRI4DLtuHfW8Hvi8is+zrO1JEaoCHgUNF5GMi\nUmT/HSsic0aw3Mo7ABUQ5Z3CH4AngI323w3GmMVYcZCbgVZgPVaQe1+4Bui2j/mCfZ47R6bIAHwG\nuF5EOoFvYwlWvvzM3v4JoAO4AysZoBMrWH8pliW2C/gxlntMUfJGjNEJpZSDGxHZjJU59dRol0VR\nDibUAlEURVGGhQqIoiiKMizUhaUoiqIMC7VAFEVRlGFxUHckrK2tNQ0NDaNdDEVRlLcVS5Ys2WuM\nqRtqu4ILiIjciTV0wh5jzDx7WTVWHn4D1nhDHzbGtIqIAL8AzsPqUftxe5gF7AHmvmkf9gZ72Imc\nNDQ0sHjx4pG9IEVRlIMcEdky9FYHxoX1W+CctGVfBZ42xswCnra/A5wLzLL/rgZ+Da7gfAdr0Lvj\ngO+ISFXBS64oiqJkpeACYox5DmhJW3wh4FgQdwEXeZbfbQ/89gpQKSITgbOBJ40xLcaYVuBJBouS\noiiKcgAZrSD6eGPMTgD7/zh7eT2pg8812suyLR+EiFwtIotFZHFTU9OIF1xRFEWxGGtZWJkGiTM5\nlg9eaMytxpgFxpgFdXVDxoAURVGUYTJaArLbdk1h/99jL28kddTUyVhj9WRbriiKoowSoyUgD2HN\n/ob9/0HP8ivskUNPANptF9fjwPtEpMoOnr/PXqYoiqKMEgcijfderGk5a0WkESub6kfAn0TkKqzp\nPC+xN38UK4V3PVYa7ycAjDEtIvJ94DV7u+vtmeUURVGUUeKgHspkwYIFZqz0A1mxvZ3+gQTvmqrZ\nxweaR5bv5MQZNVSXBEe7KIrytkBElhhjFgy13VgLoh+0/PixNXz3oZWjXYx3HLva+/jsH17n2vuW\njnZRFOWgQwXkANHR28/erthoF+MdR0u39Zvv6YiOckkU5eBDBeQA0RWN09qjArK/tHbH+M8/L6Oj\nrz+v7Tvt7UrDmcN9H7tjEfe8kteoDWOC9t5+Tv/JQt7Y1jaix/31wg3c/My6ET3mvhCLJ7jh4VW0\n6TvytkIF5ADRExugJzZAX//AaBflbc1z65q4f0kjr23KL4fCEe3S0GABMcbw8oZmXtqwd0TLWEg2\nNHWxcW83K7a3j+hxf/zYGn7yxNoRPea+8PjKXdz+wiZ++OjqUSuDsu+ogAzBs2v2jEirqCsaB8ho\nhbT39LO1uWe/z3Eg6Y7GefTNnazb3XlAz+v8Ttta8vu9WrptCySDgPTEBognDNtbezPuu3JHOxub\nugYt39DUxcodI1uB54vjiuvsiw/7GMsb27I+b6OVVFPkt6qi1p78LMt8WLe7kx1tvbyxrY01uzpG\n7Lidff0FbXQ8+9YemrveHi5XFZActPf288m7XuPPixv36zjGGHpiluXh+OS93PTMOv71jkX7dY4D\nzafuXsxnfv86PzjALcbNjoBkqfTTaem2XsSSkH/QuvZeq7JqzHKs/3pgOf/9jzWDlv/wkdVc98dl\ng5b/55+XMf1rj+RVruHS1NkHJF1zw+GCm1/kPf/7bJbjj07FFSqyqqKe2PCFMZ2zbnyOk370DBf9\n6kXO+fnzI3bcB5Y0cvnti9hbgEq+vaefT/zmNa659+2R9KECkoPmrijGJCua4RKNJxhIWC271u7B\nx2rtjo3aiztcttoWwP60hIfDluZuYN8tkEw4cZTm7ljGiqu5K5bx3jd1Rdnc3E0ikdpav39JI4Vu\nwO+xn5N8Y0DpDOVC3ZLn7zrS9McTAHRHx76Lt7k7hjGwpQBeg22t1jF3tfeN+LELgQpIDhx3U1c0\nzkdvfYUHlgy2RD77h9f5/aLcQdjuaLJyaumJ8eqmFj7065f4yv1WKzYaT9DbP+CKzFAs29bGv/z6\nJdct5sUYw0vr92KMwRjDi+v3DqroovEBPvz/Xmbp1lZ32dKtrfvUqnUq1pj94n/3oZV87S9v5rXv\nki0t3Pjk8PztTgXnWCA723NbIo4F4pTTS7vHXbKjbfBx2nv7U+5d8pgxovGEW5mn4/zej63Yycd/\n82rO8u0r++vCymZtORSiUsyHPvv+pAt5dzTOghueZOFbezLtlpX4wOD7PRSPrdjJz554a8jtOlzL\ndeR/K6dhVlsa2q/jfOOvbx6Q1HUVkBw4rdc9nX28vLGZL/15WYqPuDsa55HlO/n7stzDcnlbVa3d\nMW59bgOLt7TywOvbAUtAALrzNN9f2djMki2tLMuQifPyxmYuu30Rr29tZdXODi6/fREL16a+fHs6\nory6qcXdPxof4IO3vMRVd+XX6XIgYdwKrK9/gM6+fv7w6lb+tHgbezqGbjk9+MYOfvH0Ovr38SXv\njsZp6oziE2hs6WHNrg5O/O9nWLw5e0C9xRaJ/oHB4uy1LtJdYrF4wk18SKfVdkNuzdJa77Vb+a9s\nbGHhW00ZxWu47HFdWMMTkGyWW9COQWy1LbwDjWMZpVsgq3Z2sLcrxi+e3rcMsfRYSnmWLDwvf1+2\nkz+8unXI7ZznJl8reF9wBLy2bP86vb68sTnjszvSqIDkwGm9es3JZY3J4OlaO4C8YnvHoFa+F6+l\n0NIdc/uDDCQMsXiCaNy60T0ZzPdEwgxqlTkt3+WNgwO5zkO9pyPqusW2taRWjk4F57T6+vqt/69u\narEsmA173Upy5Y72Qb7eDk/F29s/wFOrdxOz3XR/Xbo96+/g4LyAQ/mQY/EEL65PBiudCvvIyZV0\nRuO8sqEZgPV7Bge6HZx7GM1kgXiuY1NTd0rjwFmXbuVF4wN02y/mFk9l67UenYZAtmPsD869H24M\nxPkNi4tSY0IJ+9rzdWF19vWzIUOCwXCJ2s9k+rPuPMM1Q4wisGpHR8rzlJ6sEioaHANz6InFaeuJ\n0dIdy+teddjinf5ejQTO/bEmZx0e3dE4m/Z2M3dS+UgVKysqIDlwLBCvgDy1arf7+a1dloB0ReNs\nztFy874UrT2xlId7b1fUbaFmenj/tHgbJ//omZRW7G67lf/m9sEWyK526yVq7+13H/RdaVaB0zKJ\n2sLhCBjAJ377Gpfdtog7XtiEMYbLb1/ETx5PNevb7IqxuMhPX/8Aj63YxcSKMEfUV/DU6t0MRZvd\nOhyqc9/fl+3g8tsXuZlQb9qCeeph1jD9z6/bm/H6vDgxp1gGa6fD04q//uFV/NSTxupU/j1p96TN\n07L1tkC9lZfTinaOsT8B73TcGEjv8ETJqaCcoDVY7p64LYDZMtLSufnZ9Vx084v7bEVmw2nEdKe1\nmh03UU1JdpdOImE476bnufy2ZCJKc1qn3fT7eM29S7noVy8CcMMjq7nyzldp7YnR158Y0pXsNKC2\nFcCF5TxT6eXdF9bs6sAYmDupYqSKlRUVkBw4Ff1uj6/bW1mt2ZVMYX0zR15+ugXS0hVjWk0EsCoE\n14WV4aFZs6uT1p7+lOwtp+LNdE6nfG29/e6Dvrs9XUCs8zjC4QgJwMK3rEm4mrtjtPb009bTP+g8\nTsU4sSJMb2yAne19HDahjEmV4bwqNmf/3UO4u5wWriPOj6/cRX1lMecfORGA523rZHcOIWp2YyCD\nrbv23n5E4JrTZwKwrLEtZR1AT/9AinXpFX9va93byHDuY1JARsYCGUgYN71zuKLkuEi81q7XOmvJ\nM2V9w55uOqNx1u0eGSvEeRZj8dQK3BE8vz97i3yT/Xy85Ukpd96Xv3/u3Xzm1Bn09A+kWJh/X7bD\n7Yy5tbmHDU3d7j5DuZKdBIZCCMiWFuta9sf9tHKHlbKsFsgo0+xxNTnsThGQDo6oryAU8A3q2PXC\nur0s2WL55p2HoSwUYHdHH53ROIeNLwNgT0efa11kEpAmu8JwKkKA3bYffFtLL63dMR5bsZNP3b2Y\nzr5+t3xtPf3ug+5s7+D4m52KI5N7pycWd1/edbu7Uiwgp2IcXx6mt3+ArmicklCAkmAgrziOI2zZ\ngtAOzvm3NvfQ2dfP8+v2cs68CRxSW0pZKOCWKZsQdUfjbsvW2dYYw/f+vpJXNjbT0dtPWSjAl953\nGGfPHZ8iAk4ZjUm6/CBZMQUDPrcyvvfVrVx112vuNrkEZOnWVq767Wt5t9y7o3G+9Kdl7Grvo7kr\nSsJAKOBzj2mM4RdPreP8Xz7PGT9dmOLyS+cr9y/juXVWAyE2kHSdejOz2nL0w3hgSSNf+8tyIGkZ\nvLnd6mPxy6fXsXJHO999aOWw+pL0eRox3n5XW203UWdfnH+7azHPrW3is394nRfWJa/TqTCn15a4\nyxwhHF8eory4CGNSz+GQSBjXdeVYkZneQy9OI2lHW98+B+s7+/q57LZXWL3TKvNAwnDjk2vZ0dZL\n/0CCHW3WM9jbP8CSLa209cS479WtefdjuenpdXz7wZWUBP1MrAjvU9mGgwpIDtL9qNNrS1LSbdfu\n7mLupHKm15a4/RMcrn94JT9+zHL9OBbItNqI6/aaPdFqHezujLovcrr5DkkfsFNxGWPY3dHnvix/\nXrKNf7/ndZ5ctZvVOzvZaVeC7b0x90FPTwl0BC0pJKnnLQn66epLCkhsIJHi73Ze8AkVYRLGymYq\nCfopDvrpzaPl5LjAhgq4O+b81pZe/rFiF7GBBOfMm4DPJxw5JWmeZ0t5dNxpAZ+4LqyXNzTzmxc3\n86N/rKG9t5/y4iIA6isjbG/rdSu/tt7kvfeKouMSO7K+gk17rVTem59ZnzLOmfP7OpWx1wJ9ds0e\nnl6zZ0jxdLCSLRr51N2L3cZEQ00JXbE4iYShqTPKjU+tJT5g2NDUzQtZBMQYw0PLdjCtOsJZh4+3\nytXnWKLWb1NXFqKtJ5Y1nvePFbv4+7KdGGPcbK7lje189vev89Mn1/L+m17gty9tHlbae18GkYZk\nUL+xtYenVu/mijtf5ZHlO3l4eTJxxenUWV9ZnDyGfT+qSoKUBK34R6bGTYvHpexc9g8fXcOR3308\nqxC29/YzvjzEQMLk9DxkYnljOy9taObKO63svEWbmvnF0+u44ZFVrN/T5TZWu6JxPnrbK9z63Ea+\n8bcV/PbFzUMeu60nxs3PricY8PH+IyfuVxwlX1RAcpDe6W9GXYnb2m3vtdxKh9SVMKmyeJDveGd7\nnxtkdfyZsyeUu373Q8eXIgJNHX05XVjpAtJpt6rfNbUSgEff3OVu29wVTbFAkq6iKMYYlje22UH5\n7BaI3yfMnlhOZzSekpGzym7lbWzqcoPWE+wWTmtPjJJQgEjQP6TpbYxxyzVUJbrFFZAe7nxhE7Mn\nlLFgmjUc/lGTresXSWYmpXPPK1uYVhPhtNnj6I9bL+ZvX9oMwBvb2nh+3V4qHAGpKqYnNuBW+t4U\n35QsOruyWdBQTXtvP0+u3s32tBTgrmgcY4xrxXjdTY32tk6SwkDCsGxbGwMJw4rt7Rx9/RMp6aFO\n/4g3t7e7lfa0mgjGWM9Cs32cz58xiwnlYfbav+na3Z109vWzfk8nHX2WK7KvP8Glx03l7LkTUq7L\nqbwnlFsNgnSXW0t3jG0tPWxr6aErGqepK+qK4pvb24kEUzOc9iVp4K1dnRhj6PM0Ypo9v41zzemN\nBK/72Hk2vVZda0+MsnCAIr/PLV+mJJVd7X2D3vO/L9tBR188Y8pzzE65/8CRkwj4hMdWJt+/gYTh\ndU9qvMPKHe2uMDjXsaczytKtre67VBIMuJbU0VMq2dNhxUaXN1r7DuUu27S3m58/tY5YPMHfPnMy\n//Oho3JuP1KogORgsICU0trTTzQ+4IrDtJoS6iuL2eHpj9ATi9PZF2d3R5TeWDJrZ87EpE+yrjRE\nTUmIPZ3JIPrPn1rL+b9M7THrCIjjTnNa7fPteUW8LaAdnpfBCqInW8BX3PkqF9z8Ig8t2+FaCa6A\neEz7yVXFVEWKXAukpiRIuMjnxgeu/t0SfvnMegDGl1mBzYSxXoDiYIDetJhBOl3RuPsypQvI6p0d\nfPWB5QwkLJFxKvPn1zWxZlcnnzx5utuqOmqKJSCHTyxnb1dsUKrszvZeXtvcyqXHTiVc5Cc2kKA7\nGuep1bu57PipRIJ+9nZFkwJSaYmhIwbtnliOV9idiv/YBuv3/8VT6wgGfBw5OWkR9cQskXesnte3\ntnLzM+swJjlsinNtT6zcxYW/epHTfrKQJ1btpq2nnyVbkpVQZzQpPk66eINtfXb29bvlqS4JUlsW\nZG9XlD2dfbzvxuf41t9WcObPnuPiW15yLdNJFWF3WBfn2M5z4G0QeLng5hc45X+edS3Sldutim5q\ndYQ1uzqZVJnqKslXQJ5YuYuzf/4cj6/cneJeavFkAMazPCtrd3e6z5njDvJaMc3dMTdzyxmFIJMF\nsmlvd0YXLlhZiek4jYEp1RFOnFHD//vnRs7/5fO0dMd4fOUuLr7lJf62dDun/WQhm/Z2s/CtPbz/\nphc47xfPc/T1T6QkmXzwlpf41bPWu1RXFmLF9naKi/zMnVTu/obL7fcuW8bX/zy2hj++tpXP/P51\nfvvSZo6aXMHhByD24TCqAiIiXxSRlSKyQkTuFZGwiEwXkUUisk5E/igiQXvbkP19vb2+odDla/UI\niE+SL25TZ9R1WTXUWBZIW0+y05k3qLu1pYfuaJwivzBzXKm7vLokyLiyUEoQfXNzDyu2J32dPbG4\n+yA5L5Vz7Bl1pZSHAwwkDLMnWPEUpyUGdgzE40pwMpZe39rqycIa7MJqqCmhNBSgK2oJSENtCacd\nNs4VHmcMpUjQ77p/ACIhPxHbVdCXIWDt4HVvpMcuPnbHq9z32jb2dPa57qtJFWGi8QS1pUEuOHqS\nu+3ps8fxvQvmcumxU4DBVohTyR03vYqg30csnmDVzg4SBs6YPc5thTvprPWVVlJDUkC8FkhqR9DS\nUMB1Qa7a2cEpM2v5y3+cxKtfP8PefiBl/3te2cpPnljL1pYe9/iOi8z5Dba29PAHu0Oqt3XttQac\nitJJwOjsS1og1SVBaktD7O2Kcb/d4dU5zvo9XezqsM47oSJMmd0nwrFAXAEpzywgTkvciQU5jZaj\np1QSiycGZTzlmzRw98tb7P+bicYTbl8NJxZx32vbCBf5OHlmjdvoOK6hmitOnEZPbIDG1l46+pLT\nJHit35buqDuBmGuBZBAQ5zfNRCYBcTwI5cUBPnTMZMBK47/vta2ue/rnT61l095ufr1wPU/aWZtv\n7e6kraefJ1btprY0yHNfPo3ptSXu+9zbP8CqHR3MmViWMm6bc77tbb2D4i3LG9u4ZeEGfr1wA6t3\ndvDumbXcdsWQc0CNKKMmICJSD3weWGCMmQf4gUuBHwM3GmNmAa3AVfYuVwGtxpiZwI32dgUjFk/Q\nGY1TFbEqydJQwH3B9nRG2bLXskCmVkfcFpjTm9lbMW5p7qY7GicSDDC1OuIury4JMr48xJ7OvkGt\n5xfW7eUbf30zJc3VqSicluT48hD1VdbxZtSVUhkpcn3BdWUhN403GLBusd8nLJhWxcodHYP6gXhb\nYNNrSygNB+iOxtnW0svU6ghXnNhAW08/v3lpk9uqHkiYlL4EpbYLC3JnkDgVa2WkaFCr0qk4emID\nbmv35Jm1AFx+/DTCnvMV+X1ceVIDk+3fdEtzD99+cAVbm3v4998t4UG7tX7YhHKCAR/ReMJNAz6i\nvsIVIycTx7mH21t7Wb2zI6Vi8V5PW08/VSVFTCwPu9d7+pxxBPw+KiNWhdUdjWeMAyza1OK6MLY0\n9/CHRVtTLB2nInwri4Bs2tuNCEyx73tHb79b2ScFJMofX9sGpN5XR/gnVhRTYldQXbYF4rqwbAsk\nVyAdkgLiWF3pfUe6sgjI9rZePv27xXRF42xptuI19ZXFvLShmTU7O5hUWYzfJzR1Wpb7g0u3c/6R\nk5hQnoxt3PDBeVz0rnrASmLxNmic5/rmZ9axfFu7KyCuBeJxYTnhgZwCsrmF1za3cN0f3+CVjVaf\nI6dRVlFcxIVH17P6+nM4aUYN97y8xZM1aJXpr0u38/tFWznr8PE8fM27qS0NMpAw1FcWM7Umwgft\n63B+s5U72plXX0FxcHCflYGEYdGmFr7z4Ao3UeKmp9ennO/KkxoYV174wLmX0XZhBYBiEQkAEWAn\ncDpwv73+LuAi+/OF9nfs9WdIAaNEjptnvH1DysJF1Nkumz0dfWxu7mFCeZjioN8N3m1v6+W3L27i\nNy9uco+zpbmHrugApaEA9ZXF+MR6eCsjQapLQrR0xQYFsb/21+X8ftFWHnlzp7vM6RD39OrdVJcE\nmVIdcc87pTpCTUnQ7dg4d1I5bT0xOnv7OXlGDWfOGc/jXziFefUVrNrRkQyepmVjvf+IiXzomMmU\nhoro7Iuzq6OPiRVhTjikmslVxfz+lWQv3Wg8QdjzoEeCAVdQcgXSndjCsQ3VNHVGedRzjQ5dfXG3\nor1kwRSOn17Nx06clvF4DTWWVfh//9zA3S9v4aZn1vHYyl38fdkOplZHKA0FCAV8xOIDrNjRTl1Z\niHHlYd5tC5Nz3GrbVbejrZdzf/E8L29spshOHfW6ZHZ39FFdEsLnEw6ps859+uxxgJWZFfT76I4N\nZBSQf7y503XJ3PnCJr7+1zdZtbOdSNDPUR4XmFdAOvr6Cfp91JWFSBioigRdt1tnX9xt/VcWF1Fb\nGrJjb1aF4u2b9M+1Tfh9Ql1ZKOnCSguiZ7NAnF7qDm82tlMWTjaImjqjzBxXygeOskS5M4sL67m1\nTTy+cjcrt7ezeqd1jZ8/w0qhXreni+Kgn5qSIE2dUXZ19NEdG+CkGTUpA2GWh4vcDMZ1e7pcS/Ww\nCWWuhfzTJ9dSWxbigqOtCjrdAokPJNwxy5xyZGJLczcPLGnkL0u3c8Wdr9ITSzYMysPWPSgO+vno\ncVPZ0d6X4p46bno1gvX8nDF7HPPqK1wX9iT7vf3gu+oJ2Q287W29dMcGOKS2xG2YpHP57Yu46+Ut\n/GGR9R6u2N6ekmnldaMeKEZNQIwx24GfAFuxhKMdWAK0GWOcJ7ARcGS6Hthm7xu3t69JP66IXC0i\ni0VkcVNT07DL5/TMdcz9snDAFZM9nVG2NHe7rgTngdjR1sd3/76Kx1daD1K4yMeKHe00dUUpCfkJ\nBnxMrCimsrgIv08oDfnp6IuTHjJwXsyfP2V1bKsoLqK1u5+9XVGeXLWbf5lfT5Hfx+SqYnf7mlKr\ngvH7hCPrK+iODbC3K8qkymJuv3IBM8eVMa++gt7+AddSScZArAr/q+fOZl59BWXhALEBKx+/riyE\niHD4xPJBweJUC8TvtmyzWSCdff1uT/5rTp/J0VMq+eoDy+lLy9Hv7IuzpzNKkV84tqGKP376xKxj\nAzXURJhSXey66BZtanbXOa69YMBHbCDBiu3tHFFvvWRFfh8bf3geXzjzUMDq+VtXFkrpEOgMf+JU\nPMZYge7D7Yrg3TPrOGVWLRMrki3kkpCf7mg84xQAz76VfB4di3JLcw/l4SLm28kBM8eVsr2tNxm/\n6otTFg4wzm68VEWKXNdhR59lgVQUFxHw+6gtTfbWrq8sThnY8dm3mhhXFrKfu1QXVroF4h0GJD6Q\noD+RaiHv6uhjclWEKk/v8GMbqvjm++e4ZR5ImJSe+uAZJaEz6maUzbLFAKz05LqykGuBgFX5e4P0\n5cUBSkIBSkMB9nZFXUt19oQyemID3LNoCz4R7v3UCVxgC1pJMO16PZaZ02+qwuOOdX7nhEmOPBGL\nJ1i9s9MVV6/79qQZNfbvmDzu2XMn8OyXT+Wa02e6wuo8j5M8Db/Xvnkm8+rL3QZTRaRoUFKCL62Z\n3NYbwxhDS0+M02aPQ8TyOowaH+HSAAAgAElEQVQ/wNYHjK4LqwrLqpgOTAJKgHMzbOq8BpmsjUHR\nWmPMrcaYBcaYBXV1dcMun3Ng52UrCweoKQkS8Ak72vrY7BGQ8eVh/D4ZlClxRH0FD76xg+fWNuH3\nWT/11OpI0jdrxxrScSwEpwI7bEIZe7uj/OCR1cQTho/Yfn/HAplaHXErjylVxdTYlW1HXzzlQXc6\nFjmZItF4gj8v3ub6uJ3eySWeFpBTcc8an4zfgCWOXgGJBAOu6d0Ti/Pf/1idMpCgMYbP/P51fvzY\nGve4XzhzFh19VmD7CU8P/65oP02dUepKQ0OmIooIpx82zv3uDTY6Lb4iv9DXn2D9ni638gfwpb2Z\nkSIrCcC5/kPta+6KDvC/j6/hmnuX0tEXd62Fr547m99ddXzqMey+MMmW6uAxmLyXtLm5m4riIk6e\nUYsIXGL71Tc2WZVvpy0gjvVbUxJy3aqtPf0pwWJnG4ATZwxqW7kC4czO2JUWRK8rC+ET+NE/VvPf\nj67mloXr+fx9S10h8oq4k2zhUF5c5L4rXdF+7l+yjTN/9s+URBRnvLE9ndYwOyJwiKfvRrjIbwlI\nV5TefusdKA76KbUtkIBP3GeuoriI9t5+trT0UBUpoq7M6pP0yPKdnD57nHutYMXnINkQyGQhz55Q\nliLAsydYz8lbuzrc5+g7D63g2vvesK43nLz2mtIQs+z4ppMlOH9qJfWVxXzpfYe5DavD7GN6043L\nw5ZgOEJWFioaZIEc6hHZsw4fT3NXjJ7YALF4gmnVEY6sr+C4hupB13QgGHqEscJxJrDJGNMEICJ/\nAU4CKkUkYFsZkwEn4bsRmAI02i6vCiC/aemGQdICScZAHLfFKxub2dsVc2+s3ydMKA8P6kx482Xz\neX1LK4u3tLpZQ18861DXj1qSxVTd22WlB8+eUMaW5h5mjivl1U0tbGzq5ktnHcrMcdZ550+rorY0\nxJyJZe5QD9NrS6j0vtieB91p+TjCtKu9ly/fv9x1XYQCVnlKPfu4AjIu2Zr/x7WnUBIMpLhpSkIB\nN8jXExvgtU0tLGtspzc2QHHQz+Mrd7lWAlgVwIkzaigJ+rn2vjdSOmt29lmpot4KMRenzxnPXS9v\nQcTq+BcJ+jl99jjOO8LqsR70W9eVMKRUEumEg356+61hPS45ZjJfP28O7/r+k2xv7eWeV7a48R/n\nXmaiJOSnxxNEr6+K0LGzg+vOOpTlje2s3NFOSSjgpm/29ScoLw5wxpxxPPfl01wLyHFZdvb1UxYu\nSlogJUWUhy0LtqU7Smt3zLUEnHtVHg64QikC3zhvDjc8stqNqUXsSrgrzQIpLvJTEgzQGY1z+wub\nCAd8bgbhf198BCfNqOGsG58jFk8wuarYjflY57QqPhGrAbSxqZv+AcOu9j63wZS0QPro6I1Tbbvj\n/D5hIGEIB/yUhQO8tavTtWIjQb/bIi8vLnIbFGXhAB291uCaU6sjrrDsbO/l/fZIBe49cSyQtP5P\nxzZU8dpmqzH1H6fOYGtLDz/6xxp6YgPMmVjOyxubSRg4Zlolu9p7UxJcvO8YwPGHVLNuTxf/ceoM\nSkMB3mVnSXo5ekoFIqmCYJUvmf5eXlxEPM3im1RZzIcXTOGoKRXcv2Q7S7e2upZQVUmQuz55HP50\nM+UAMZoxkK3ACSISsWMZZwCrgGeBD9nbXAk8aH9+yP6Ovf4ZU8Dp05wjl7ouLOuBmT2h3A28eluz\nU6sjLN2aOjbV+PIw5x4xkW+df7hrTh83vZoz7Y5c6aaqQ1NnlNqSELdcfgyPfP4UAvbDcdHRk/ic\nPewGwDHTqlj8zTOpKQ1RY1eM02tLU8zx8mKP+R8OpPizHVeF08vd8cd6s0Dq7FFBHQtkYkWYGXWl\nTKgIp1ggJSG/x9c8wLbWXgYShsVbWtjT2WdnnyQFIRL0Ewr4OWVW3aCxhzr7rIohXwE5ZWYtN37k\nKD4032q9zxpXys2XzecwjwvLwSuO6USKLPdTNJ6gvqqYqpIgwYCPvyxtdMWjuMjvtjYzURIK0NoT\n441tbYhYWWRgZU7dfuUCXvrq6a5gO5SHrYpxSnWEKrtSdgLZnX1xSkMBxpVZ+zjxl6pI0BoWpzvm\nVtBJa7GMWtflFeQTJ0/n/CMn8uWzDwMsy6s0FBjUkTBU5HPjFwMJk9Kxdda4UqbVlLhWx5SqCJXF\nqRaIiHXcjr44q+zg9NJtrVz3xzfo6x9w+7c0dUTZazcQRMQ9Trgo6cJy3E3FRX43BuK15iqKi+jo\n7WdrSw9TqiNuqz1hBrujwkU+RJL9sZxguxMjATj1sHFccWKDay3Mnpis5CdWFDPPdn1+/bzZvPqN\nM1ISOgDOmD2eoN/H3EkVHH/IYOsPYOa4Ml74r9M5eWbq+ojnfSsLW+nwkGxgji8P8cl3T+eYadXU\nlQZTBmStjgSpjATd+ulAM2oWiDFmkYjcD7wOxIGlwK3AI8B9InKDvewOe5c7gN+JyHosy+PSApcP\nsIYfgWQs5LAJZWBPRjcnTUBetjM1zpk7gbPnjR/yHJlmyQOr53fEs+7i+ZPp6O3nhxcfkdWl47it\nptdGUvLAvWIgItSWBtmR1inLsUgcASnzvKhOpTSjzur46A3ahYPJirkkGCDqsyqi1p7kBFkfu8Ny\nY73n0DomVYb52YeP4pWNze51XHXKdCojVkbLnxdv4y9Lt1ud1TqjHD0lv6Cgzyd88F2T3Rb2ZE+2\nG6QKSFmOYb2Lg352N1u/jSOOJUE/rT39HDm5gpqSICJCwJ+93VUSDLi9wS89doqbYef4p0VkUOvV\n62as9LinwArgT62OMK7cug/VJdb6mpIgzV2WgDidKh3rata4Uurs+1ZXasU9br5sfso5rVRt24Vl\nV6jeSvHYhipWbE9m7DnPQVUkyO6OKJOrign4fZSFA3T2xd3KvSxkWaZOIsD9SxpZurWNDxw9ya30\nmrqidPbF3QZCRaSI5u6Y68KKJ4w7z0txmgXiUFFcxObmbivpYd7ElMyl9N9XRKzGgS2IjgurvjLs\nWq3e36Wp07q+kqC1z8SKMEdOruDF9Xu54Kh6V8y9nDZ7HG9856ysjUIHr/vKweuJKC8uct3aEyrC\nTKspcTMRATfW6QwwWlUyOsLhMJouLIwx3wG+k7Z4I3Bchm37gEsORLlgcAzEsUTm2C2TCeXhlCDi\n1JpkpfWtDxye8UFJx/uwBXziZugAbksIrHz7n1/6rpzHqrXL0lBbwriyMNdfOJdvP7gyJXUYoLYs\nNEhAwKpknUrdueYiv7itubDdwcnxDQNpFkgAv896MTMNr763M8qEijDvObSO9xyajE0d21DNsbb/\n9sQZNfxjxS67l3/UrQTzxbnW9GtOEZAMc6O71xP0uz57p0KyLIp+LlkwhY8smMJQeX/OfmfOGceP\n/uVIvvPgCoAUq6MqkupG87asLWsE2m0XhRUDSbqwqkuc/0F7wMsY1bZwVEWCvOfQOt43d7xrOWab\nV6LUdgGBxwIJ+PjBB+fRHY3zkQVT2dsd5Yyf/tM+jnVep3KebKcSV0asjD2nci8NB3hze7t7TCdN\n9vEVVo9tn1iDgXZF4+5wPM4z5gTRITkOWiTotUBSLZ5tLb30DxjGlYVSnsXK4sHXHAkF6InF6R9I\nuNln4SI/S791Vkrw27FkKouDTKwsZv2eLiZWFHPGnPGcPnt8Smxl0DmGEI989isLB1LiPHd+/NiU\nbR0hX2sPYpn+LB1oRlVAxjJODKS82PLtTrIzbZwKNL235xRPpZVvxee1DqpLgin9IrLFR7Lx3sPq\n+PLZh3GCbT5fcWIDHzhyUorIQfaZzkIpbp6Au63X4vnTp08k4EtuF04JovvdbBEnnXhSRdgVq3zn\nJygNB9jS3E3CkLcLy8G5B04/CYeQ32uBZG+xFRf5XddR2LVArDTgC46alCJE2XDE89x5lh/eqVi9\nGTK5LBCfzxJtxwLp6OtPCaI7Fkh1aZBFG1voHzBU25WIzyfc/Umr7eVkgWW731YnVuveRPsHELHS\ndS8/PpkuXREpYkJ5mLbemPs8OhXW5Opi9/u2ll63ci8NBXjd48p1KmcnSWL2hHJ2tlspq841VXoa\nKc674/TvcOIy1u+U6sJyraOyUErgOd2FBdb7tGFPN0d+9wkG7He7uMifEseBZMOtIlLExIow6/d0\nMakyTEVxEcdMGxzXGAkcgRSB0mAgWYYM1+G4qtfvsd6x6iHmSSk0KiBZcMzaUMDH4194j+tCmFgR\n5tDxpZwyqzZle6fVW237zfPB+9Bf/Z5D8PuE7/19lb1u325NJBjgs6fNTFmWLh6QPYjsBNAh2UpP\nr3zSy1Tk91HkF4w9QqyjNc4Q37dduYDn1u7lx4+tobd/wG3F5qIsFGCj3UlzXwVk7qRyvnfBXM4/\nKjWIWhRIimBOF5ZHEJ3P755Vy2mzx2V8mTPhCM+ZcywX5qXHTWXmuNIUF4tTCY8vD7G7I5ohhTRI\nW28/iYShK2q5h+bVV/CJkxt4zyzLeqspCboB9/qqwdZuRXERJUG/mziRzoTyMIvsntZ98YR9/wab\nV4dOKGPT3i533cSKYurKQq5gOBVwRbFjqVvLi/xWPMQRwpbuGFWRIk49rI5bFm4Akg0t5xihIr/7\njDgZjcXBZHp4igXi+VxXGkpJA08XaLDctK+mzVyZqcNeiWuBFLnu2kKnxzrvlZOo41pBGawLrwXi\nk9TfYTRQAcmC8zj67OCmg4jwxBffO2j7afY24/ah0vO6qebVW2PYOAKSLT6yv+RjgZS4AjJ06yYc\nsDJvRISg30fAJ2xv66XIL8yeUJ7SJySfeZ5LwwF3psV9FRAR4cqTGgYtd7KwnONnwyvojoB86/zD\n96kMt11xDFuae6iIOGNsFVPvCdYCXHD0JIr8wnPr9vLkqt2DKoGK4iLaemL2HBZWmUMBP9/5wFx3\nG2/Lc2aGoL6I8MdPn5jVlTq+Iszujj4SCUO0fyClAeHlK2cfltI35vNnzOTyE6a6352gumNFOQI9\na1wZCWNS+pRcdvxU1/UFyftb4QmiO593tffh91nPlHNfUmMgqYke3h77mcT+ihOnsXpnB01dUV5c\nb8Uq02dlBOvZD9iV+PuPnERxkX9QwHykcUTL2zkRMl+Ha6HZ49Slp6IfaFRAsuAOCJjn/amMFFEW\nCuzTUALeCisU8Lnplda6wtyammwC4pmhzknHzKcCDwf9bpaYiFAc9NPZF3eHpfAKaj6C5LUQ6kpH\npuWXbxA93SU3HCZXRVIqyUzUlob42IkN7pAgXtcMWJXyjrY+/s9uqWdyuzl9P/w+cXvjp+NkDmVi\nQnmYeMLwL//3Eku3tjG+PPO9Tj9GpZ31kyyr9dmp/Bzrdc7Ecnf8reMaqmnrjXHFiQ0pszg6DYpk\nDMTv3p8OO/tMRDwWiMeF5bEyaktDKfHDTBbIp987A4BfPr0up4DUllod8kSE9x5ax3sPHX5fsnyJ\npCXqRIr8BNM6hjqUFwco8gv9AybjdR5oVECGwJfnaCkiwiULpmRsDWbDa4EEAz4CfmsojNhAYp9j\nIPlSnSVrw9sCFRHOmjM+JfsjG8VF/pQKOmILiJPr7s1YycsCsX+TUMA3aJTX4eItX7aWNqSKRrhA\nv78Xx8WYboFURYI8+1aTO8NeJtFzgunTaiJ5u0y9OILhpJ7n+l1yccIhNWxu7nbFt9QVkDI39fl9\nc8fzb6ccYp83zO1XLOCfa5uYP83KHnMqwnCRj1DAT7jIR19/wm2JV0WCzKsvT+l/U+5xlVkpvZYF\n4u1pnwlvoyjTPb72jFkZrdhCUpKWZRbw+/jjp0/gkLrMluW4sjDb23pHPYAOKiBZcYLo+2IgfvsD\n++buSLVArM/FQT+x3kSKuIwkJVksm1BaJXRrnqN6WiZ+cl+nIegMGVIc9LupnjV5WCClIae/TVnO\ndNl9IX0sp2wUZ3BhFRK39Z7mqqiIDHZppeO4sGZmqGTyId2v7511cV84Z94Ezpk3wf3uuAgPn1Tu\njnCQfq4zDx/v9oUCj4AEkq6cvv6oew+CAR8PX3NKyjGc38RJ9HBSyis9nQ0z4W3EZLrHVSXBjLHD\nQhLJ0M8lU0dEh39/7yF868GVbqbaaKICkgUnJucrYFdLr5vKqcAjQT/tvf0FE5BsrbN0AcmXEs8Y\nWJCcv+QIj+tjfHmYzr6uvCyQMk8FNFLk20LPFEQvJJMqizO6Ch1hmVYT4fsXzuOkGYMtQUeM98Xi\n9ZKejto0xORe+TKpophwkY+5EytYYvfyzpX6CqSkioMlqHs6ozndiI7oOr+d8y6li2863kSOohFq\noOwvrgWSZ0D8X0+YxtrdXa4FN5qogGQhaYEULkjlt8f26e0fcCtwpxU8XB/8UBzTUMX7j5zIUZMr\n+OGja9zloWFWmN/+wFw3BuLF6zsfVxZiY1NXXia3M4igt5Pm/jIsC+QAuLDOmzeBGde8e1AL3WmR\nT62OpPSZ8TK5qpjDxpcN20dfVxpy065zzP+1z3xwfj3vObSOikiRK5CTM2SJeXHcnI6QOP9z3QOv\nBQJJwa8cIltuXxMzDgTOu54rPudFRPj+RfMKWaS8UQHJgjuCY4GTHEpCjoCkCkehLJBQwM+vLpvP\nC+v2pi0fXmvs6CzjQnlf1IkVxdTaPaKHwgmyTssSGB4Ow7FACp15A5ave+6kwYFuZ2iXSRXZK95I\nMMDjX3zPfp27tjREVSToxlpGgiK/z7U4PnDUJA6pK0kZrTgTcyeVc89Vx7uj2jqunFxWoCMgTlaS\n3ycEA76Mqa9eaka530Qm3CSBPFPFxxIqIFlw8soLPTG9ZXrH3EouUmRnYhS4BezNuoLhC0g6v7vq\nuEFzYXzhzFl89Lgpee3/xbMO5et/edMd1XQkyFtADnAMJBtO/4NTDh06iWF/OPPw8UwsD3PdhEML\n8rwFA76cvnwHEeHdnn5VTkWaq0yhgI9JFWEOnZAcsyoS9A9pgRyIhsG+UrKPFshY4u1X4gOE2bcs\n3mHjvCTBNBdWrkySkcB1mRWlWkD7yymzBrtUplRHUvrS5OKkGbUs/PJpI1IWh321QPw+cSeTGg3O\nnjuBf1x7yoi68TLxww8eUdDjD5dkf4js74CI8Mx/npoSx/jUKYfkTF0eq9SWhvj0ew7hrMMnDL3x\nGEMFJAuOXzjfNN7hUhKy8rod907EjYEU9tY4LbGJFWE27u0eZJEcTDgxkKFcaM5vXlzkL7jlmQsR\nKbh4jGWcfjHFQzyT6dZE+kgMbxd8PuFr580Z7WIMCxWQLBgcF1ZhzxMJ+lOCvE4lVqie6A6OBTK+\n3BaQEXJhjUWc33eoa3QskLHo5ngn4VgghWpEPfL5d7sjUCv7hwpIFtw03kIH0YOBlAwopxd4eIRc\nStlwXFaOv32kXFhjEce6+vCC3HGYQmfAKfmRntY70mRKXFCGhwpIFhLu4GyFVZCK4tQpLA+dUMbs\nCeUFH+OmqqSIIydXcPLMWv6ydPtBbYGEi/ws+877howrOQIymgF0Jb8gujI2UAHJwoGyQD53+kw+\nfGyyZfyxE6bxsROm5dhjZAgF/Dz0uXfTbg92N5zhMN5O5DOaruvC0oprVEm6sPQ+jHVUQLLgZmEV\nOAiyLxlKhaC8OMCXzjqUc+e9/TJARhqnL8FQwVulsDhBdI1FjX1G9U0RkUoRuV9E1ojIahE5UUSq\nReRJEVln/6+ytxURuUlE1ovIchGZP9Tx9wcniD7KoyUXHBHhmjNmZRy47Z1IcZFfXVijzPjyMH6f\nFHweDmX/Ge2m1i+Ax4wxs4GjgNXAV4GnjTGzgKft7wDnArPsv6uBXxeyYO5o7ge5gCipRIL+AzKM\niZKd8eVhnvnSezlj9rjRLooyBKMmICJSDrwHuAPAGBMzxrQBFwJ32ZvdBVxkf74QuNtYvAJUishE\nCsSB6omujC1OmVXrztGujB7TakpGfbIkZWhGMwZyCNAE/EZEjgKWANcC440xOwGMMTtFxGmG1APb\nPPs32st2eg8qIldjWShMnTqV4bKP80kpBwn/86GjRrsIivK2YTRdWAFgPvBrY8y7gG6S7qpMZKrL\nB/UGMsbcaoxZYIxZUFe3P7OJqQWiKIqSi9EUkEag0RizyP5+P5ag7HZcU/b/PZ7tvT3BJgM7ClW4\nA5XGqyiK8nZl1ATEGLML2CYih9mLzgBWAQ8BV9rLrgQetD8/BFxhZ2OdALQ7rq5CkHRhqYIoiqJk\nYrT7gVwD/F5EgsBG4BNYovYnEbkK2ApcYm/7KHAesB7osbctGE4QXS0QRVGUzIyqgBhj3gAyTb59\nRoZtDfDZghfKJnFgRjJRFEV52zLa/UDGLMmOhKogiqIomVABycKBmlBKURTl7YoKSBbcLCwNgiiK\nomREBSQLznDuKh+KoiiZUQHJghtDVwVRFEXJiApIFhI6FpaiKEpOVECyoUF0RVGUnKiAZEHTeBVF\nUXKjApKFRML6r/qhKIqSGRWQLDhBdLVAFEVRMqMCkgUniK4oiqJkRgUkC8nh3NUCURRFyYQKSBaS\nU9qOckEURVHGKCogWdAYiKIoSm5UQLKQUAtEURQlJyogWdDReBVFUXIz6gIiIn4RWSoiD9vfp4vI\nIhFZJyJ/tGcrRERC9vf19vqGQpZLhzJRFEXJzZACIiIni0iJ/flfReRnIjJtBMtwLbDa8/3HwI3G\nmFlAK3CVvfwqoNUYMxO40d6u4Kh+KIqiZCYfC+TXQI+IHAV8BdgC3D0SJxeRycD7gdvt7wKcDtxv\nb3IXcJH9+UL7O/b6M6SA5oGm8SqKouQmHwGJ2/ORXwj8whjzC6BshM7/cyxRsgcOoQZoM8bE7e+N\nQL39uR7YBmCvb7e3T0FErhaRxSKyuKmpadgF0/lAFEVRcpOPgHSKyNeAfwUeERE/ULS/JxaR84E9\nxpgl3sUZNjV5rEsuMOZWY8wCY8yCurq6YZdPLRBFUZTc5CMgHwGiwFXGmF1YlsD/jsC5TwYuEJHN\nwH1YrqufA5UiErC3mQzssD83AlMA7PUVQMsIlCMjmsarKIqSmyEFxBizyxjzM2PM8/b3rcaY/Y6B\nGGO+ZoyZbIxpAC4FnjHGXA48C3zI3uxK4EH780P2d+z1zxhTuAGrdEZCRVGU3ASyrRCRTjK4iByM\nMeUFKRH8F3CfiNwALAXusJffAfxORNZjWR6XFuj8gHcoE1UQRVGUTGQVEGNMGYCIXA/sAn6HFYe4\nnJELojvnWggstD9vBI7LsE0fcMlInjd3maz/Kh+KoiiZyScGcrYx5hZjTKcxpsMY82vgXwpdsNEm\noUF0RVGUnOQjIAMicrndY9wnIpcDA4Uu2GjjTGmr+qEoipKZfATkMuDDwG777xJ72UGN68JSAVEU\nRclI1hgIWONUAR80xlx4gMozZnCD6BoFURRFyUhOC8QYM4DVA/0dR3I+kFEthqIoypglpwVi86KI\n3Az8Eeh2FhpjXi9YqcYAiYSm8SqKouQiHwE5yf5/vWeZweo5ftCiFoiiKEpuhhQQY8xpB6IgY42E\n2w9EFURRFCUT+VggiMj7gblA2FlmjLk++x5vf9wg+qhPuaUoijI2yWdCqf/DGlDxGqyO2ZcAIzmh\n1JhEe6IriqLkJp/29UnGmCuwZgP8HnAi9qi4BzPJjoQqIYqiKJnIR0B67f89IjIJ6AemF65IY4Pk\nUCajWw5FUZSxSj4xkIdFpBJrDpDXsRKUbitoqcYARoPoiqIoOcknC+v79scHRORhIGyMaS9ssUYf\nHQtLURQlN0MKiIg8DzwHPA+8+E4QD9CxsBRFUYYinxjIlcBbWEO4vyQii0XkxsIWa/Rx0nh1OHdF\nUZTM5DOl7UbgSeBpLEskAszZ3xOLyBQReVZEVovIShG51l5eLSJPisg6+3+VvVxE5CYRWS8iy0Vk\n/v6WIRcJTeNVFEXJST79QDYAfwPGY00rO88Yc84InDsOfMkYMwc4AfisiBwOfBV42hgzC0u0vmpv\nfy4wy/67Gvj1CJQhK0YnlFIURclJPi6sm4CtwEeBzwNXisiM/T2xMWanMyCjMaYTWA3UY43+e5e9\n2V3ARfbnC4G7jcUrQKWITNzfcmQjYTSIriiKkot8XFi/MMZcApwJLAG+C6wdyUKISAPwLmARMN4Y\ns9M+905gnL1ZPbDNs1ujvSz9WFfbcZrFTU1Nwy6TM5iidiRUFEXJTD4urJ+KyCKsyv0o4NtYbqQR\nQURKgQeALxhjOnJtmmGZGbTAmFuNMQuMMQvq6uqGXS5jjFofiqIoOcinI+ErwP8YY3aP9MlFpAhL\nPH5vjPmLvXi3iEw0xuy0XVR77OWNpA6hMhnYMdJlcjBGA+iKoii5yCcG8gBwloh8C0BEporIcft7\nYrF8Q3cAq40xP/OseggrdRj7/4Oe5VfY2VgnAO2Oq6sQGIwG0BVFUXKQjwXyKyCBNYHU94FOLFE5\ndj/PfTLwMeBNEXnDXvZ14EfAn0TkKqzg/SX2ukeB84D1QA/wif08f04SRgPoiqIouchHQI43xswX\nkaUAxphWEQnu74mNMS+Q3Ut0RobtDfDZ/T1vvhijAXRFUZRc5OPC6hcRP3bAWkTqsCySgxpjjMZA\nFEVRcpBvP5C/AuNE5AfAC8APC1qqMYBBOxEqiqLkIp/ReH8vIkuw3EoCXGSMWV3wko0yiYSm8SqK\nouQip4CIiA9YboyZB6w5MEUaG6gFoiiKkpucLixjTAJYJiJTD1B5xgwJjYEoiqLkJJ8srInAShF5\nFeh2FhpjLihYqcYAxqA9CRVFUXKQj4B8r+ClGIMYox0JFUVRcpFPEP2fB6IgYw2DdiRUFEXJRT5p\nvO9IjNEguqIoSi5UQLKgQXRFUZTcqIBkwXJhqYQoiqJkI2sMRETeJMN8G1i5ScYYc2TBSjUG0PlA\nFEVRcpMriH7+ASvFGMSKgYx2KRRFUcYuWQXEGLPlQBZkrGHFQFRBFEVRspHPlLYniMhrItIlIjER\nGRCRXFPPHhSoBaIois8kbRsAABdbSURBVJKbfILoNwMfBdYBxcC/Ab8sZKHGAgmdD0RRFCUn+fRE\nxxizXkT8xpgB4Dci8lKByzXqmIz5A4qiKIpDPhZIjz0D4Rsi8j8i8kWgpMDlyoqInCMib4nIehH5\nasFOZMCnSc6KoihZyaeK/Ji93eewBlOcAlxcyEJlw54Z8VfAucDhwEdF5PBCnEuD6IqiKLnJR0Au\nMsb0GWM6jDHfM8Zcx+il+B4HrDfGbDTGxID7gAsLcSJrPpBCHFlRFOXgIB8BuTLDso+PcDnypR7Y\n5vneaC9zEZGrRWSxiCxuamoa9ok0iK4oipKbXD3RPwpcBkwXkYc8q8qB5kIXLAuZavSUaLcx5lbg\nVoAFCxYMOxKuPdEVRVFykysL6yVgJ1AL/NSzvBNYXshC5aARKwbjMBnYUYgTGaPzSSmKouQiqwvL\nGLPFGLPQGHMi1nzoZfZfozEmfqAKmMZrwCwRmW5nhl0KPDTEPsPCoBNKKYqi5CKfnuiXAK8ClwAf\nBhaJyIcKXbBM2ML1OeBxYDXwJ2PMykKcK5HQCaUURVFykU9Hwm8Cxxpj9gCISB3wFHB/IQuWDWPM\no8CjBT+PWiCKoig5yScLy+eIh01znvu9rUloR3RFUZSc5GOBPCYijwP32t8/AvyjcEUaGxhN41UU\nRcnJkAJijPmyiFwMvBsrMelWY8xfC16yUcdoR0JFUZQcDCkgIvJjY8x/AX/JsOygxepIONqlUBRF\nGbvkE8s4K8Oyc0e6IGMNYzSIriiKkotcPdH/A/gMcIiIeDsOlgEvFrpgo01COxIqiqLkJJcL6w9Y\nwfL/BrzDpncaY1oKWqoxgEGD6IqiKLnINSd6O9CONRvhOw4dC0tRFCU3B31/juFizYmuCqIoipIN\nFZAsWBNKKYqiKNlQAcmC0TReRVGUnKiAZCFhjAbRFUVRcqACkgWDpvEqiqLkQgUkGxpEVxRFyYkK\nSBYSmsarKIqSExWQLBjUAlEURcnFqAiIiPyviKwRkeUi8lcRqfSs+5qIrBeRt0TkbM/yc+xl60Xk\nq5mPPHKoBaIoipKb0bJAngTmGWOOBNYCXwMQkcOx5jmfC5wD3CIifhHxA7/CGsTxcOCj9rYFQ+cD\nURRFyc2oCIgx5gl7fnOAV4DJ9ucLgfuMMVFjzCZgPXCc/bfeGLPRGBMD7rO3LWQZNQtLURQlB2Mh\nBvJJkjMc1gPbPOsa7WXZlg9CRK4WkcUisripqWnYhbJiIMPeXVEU5aAnnylth4WIPAVMyLDqG8aY\nB+1tvgHEgd87u2XY3pBZ6DLOWm6MuRW4FWDBggXDntlcOxIqiqLkpmACYow5M9d6EbkSOB84wxjj\nVPSNwBTPZpOBHfbnbMsLgtH5QBRFUXIyWllY5wD/BVxgjOnxrHoIuFREQiIyHZgFvAq8BswSkeki\nEsQKtD9UyDJqEF1RFCU3BbNAhuBmIAQ8aVfSrxhj/t0Ys1JE/gSswnJtfdYYMwAgIp8DHgf8wJ3G\nmJWFLKCm8SqKouRmVATEGDMzx7ofAD/IsPxR4NFClisdDaIriqJkZyxkYY1JrPlAVEEURVGyoQKS\nBWPAp7+OoihKVrSKzIJaIIqiKLlRAcmCQWckVBRFyYUKSBY0jVdRFCU3KiBZ0LGwFEVRcqMCkoWE\n0TReRVGUXKiAZMGgY2EpiqLkQgUkC1YMZLRLoSiKMnZRAcmCNZiiKoiiKEo2VECyYIzRGIiiKEoO\nVECykFAXlqIoSk5UQLJgMPhUQRRFUbKiApIFtUAURVFyowKSBe2JriiKkhsVkCxoT3RFUZTcjKqA\niMh/iogRkVr7u4jITSKyXkSWi8h8z7ZXisg6++/KQpdNB1NUFEXJzWhNaYuITAHOArZ6Fp+LNQ/6\nLOB44NfA8SJSDXwHWIBVty8RkYeMMa2FKp+VxqsKoiiKko3RtEBuBL6CJQgOFwJ3G4tXgEoRmQic\nDTxpjGmxReNJ4JxCFi5hUBeWoihKDkZFQETkAmC7MWZZ2qp6YJvne6O9LNvyTMe+WkQWi8jipqam\nYZfRGB0LS1EUJRcFc2GJyFPAhAyrvgF8HXhfpt0yLDM5lg9eaMytwK0ACxYsyLhNPuhYWIqiKLkp\nmIAYY87MtFxEjgCmA8vsFv5k4HUROQ7Lspji2XwysMNefmra8oUjXmgPBjQGoiiKkoMD7sIyxrxp\njBlnjGkwxjRgicN8Y8wu4CHgCjsb6wSg3RizE3gceJ+IVIlIFZb18nghy5nQNF5FUZScjFoWVhYe\nBc4D1gM9wCcAjDEtIvJ94DV7u+uNMS2FLIgx4NPRFBVFUbIy6gJiWyHOZwN8Nst2dwJ3HqBiqQWi\nKIoyBNoTPQtWR0KVEEVRlGyogGTBSuMd7VIoiqKMXVRAsmC0I6GiKEpOVECyoGm8iqIouVEByUJC\nXViKoig5UQHJgs4HoiiKkhsVkAxY2cQaA1EURcmFCkgGbP3QGIiiKEoORr0j4Vgk4Vggqh/KO5z+\n/n4aGxvp6+sb7aIoBSAcDjN58mSKioqGtb8KSAacIXx1JBPlnU5jYyNlZWU0NDRoTPAgwxhDc3Mz\njY2NTJ8+fVjHUBdWBpIWiL4wyjubvr4+ampq9F04CBERampq9su6VAHJgBn2LCKKcvCh4nHwsr/3\nVgUkBxpEVxRFyY4KSAY0iK4oY4fGxkYuvPBCZs2axSGHHMLnPvc5otFoxm0//vGPc//99xe8TCed\ndNKIHu/aa6+lvr6eRCIxosd1+Nvf/saqVatG/LgqIBlIpvGObjkU5Z2OMYaLL76Yiy66iHXr1rFu\n3Tp6e3v5yle+UtDzxuPxnOtfeumlETtXIpHgr3/9K1OmTOG5554bseN6KZSAaBZWBlwLRLsSKorL\n9/6+klU7Okb0mIdPKuc7H5ibdf0zzzxDOBzmE5/4BAB+v58bb7yRadOm8YMf/IDS0tKs+y5ZsoTr\nrruOrq4uamtr+e1vf8vEiRO57bbbuPXWW4nFYsycOZPf/e53RCIRPv7xj1NdXc3SpUuZP38+ZWVl\nbN26lY0bN7J161a+8IUv8PnPfx6A0tJSurq6WLhwId/97nepra1lxYoVHHPMMdxzzz2ICI8++ijX\nXXcdtbW1zJ8/n40bN/Lwww8PKuezzz7LvHnz+MhHPsK9997LqaeeCkBTUxOXXXYZzc3NHHvssTz2\n2GMsWbKE2tpa7rnnHm666SZisRjHH388t9xyC36/n9LSUq699loefvhhiouLefDBB9mwYQMPPfQQ\n//znP7nhhht44IEHmDFjxn7ctSRqgWTAiaGrC0tRRpeVK1dyzDHHpCwrLy+noaGB9evXZ92vv7+f\na665hvvvv58lS5bwyU9+km984xsAXHzxxbz22mssW7aMOXPmcMcdd7j7rV27lqeeeoqf/vSnAKz5\n/+2dfXBU13XAfwdFXwYFAw4eGdmpaRUI1EhCNlCqMi1EIFseUxp/QOMau5kJIaZpGWdiu3FrNHbG\nSZmCm9RuYhEwNFRARaD+AEvEMckgE2NAgghhYhAyIWYENl/CAktBp3/cK3lBuytptavVyuc38+bd\nPfe+d8959+077368e995h4qKCnbt2kVJSQmtra2d8qqurubZZ5+lrq6O+vp6qqqquHTpEgsWLGDr\n1q3s2LGDU6dOhdS1rKyMefPmMWfOHF555ZWOPEpKSpg+fTp79+5lzpw5HDt2DICDBw+yfv16qqqq\nqKmpISkpibVr1wLw0UcfMWXKFPbt28e0adMoLS1l6tSp3HXXXSxdupSampqoOQ+IYw1ERP4BWAT8\nAXhVVb/t5Y8DXwUuA99U1QovLwL+A0gCVqjq92Klm7Z16BirLAwj4QhXU4gVbl2ezv9D7WKo5KFD\nh6itraWwsBCAy5cvk5mZCUBtbS1PPPEEZ8+e5cKFC8yaNavjuHvuuYekpKSO38XFxaSmppKamsrI\nkSNpbGwkKyvrirwmTZrUIcvNzaWhoYEhQ4YwevToju8r5s2bxwsvvNBJz5aWFrZs2cLy5cvJyMhg\n8uTJVFZWUlxczI4dO9i0aRMARUVFDBs2DIDXX3+dPXv2cNtttwFw8eJFRo4cCUBKSgp33nknAPn5\n+Wzbti3sdeotcXEgIvJXwGxggqp+LCIjvXwcMBcYD9wA/FxEvuAPew4oBI4Db4vIS6oa/UY9QH0d\nxPpADCO+jB8/no0bN14hO3/+PI2NjYwZM4aHHnqI6upqbrjhBrZs2dKRRlUZP348O3fu7HTOBx98\nkM2bN5OTk8OLL77I9u3bO+IGDx58RdrU1NSOcFJSUtC+kWBpunJw7bz22mucO3eOW265BYDm5mau\nueYaiouLQ55DVZk/fz7PPPNMp7jk5OQOhxtK32gSryashcD3VPVjAFU96eWzgXWq+rGqHgUOA5P8\ndlhV61W1BVjn08aENl9u5j8MI77MmDGD5uZm1qxZA7iaxCOPPMKiRYtIT09n1apV1NTUXOE8AMaM\nGcOpU6c6HEhraysHDhwAoKmpiczMTFpbWzuafqLN2LFjqa+vp6GhAYD169cHTVdWVsaKFStoaGig\noaGBo0ePUllZSXNzMwUFBWzYsAGAyspKzpw5A7hrUl5ezsmT7rF5+vRp3nvvvbD6ZGRk0NTUFCXr\nPiFeDuQLwF+IyFsi8ksRuc3LRwG/C0h33MtCyTshIl8Tkd0isjtcu2M42j3/IKuCGEZcERE2bdpE\neXk52dnZjBgxgkGDBnX0Z4QiJSWF8vJyHn30UXJycsjNze0YOfXUU08xefJkCgsLGTt2bEz0Tk9P\n5/nnn6eoqIiCggKuv/56hg4dekWa5uZmKioqKC4u7pANHjyYgoICXn75ZZ588kkqKyuZOHEiW7du\nJTMzk4yMDMaNG8fTTz/NzJkzmTBhAoWFhZw4cSKsPnPnzmXp0qXk5eVx5MiR6BmqqjHZgJ8DtUG2\n2X7/A9xL/iTgqA8/B9wfcI6fAF8G7sH1e7TL/w74YVc65OfnayScu9ii3/jpHn3jncaIjjeMgUJd\nXV28VbiCqqoqvemmm3T37t3xVqVLmpqaVFW1ra1NFy5cqMuWLevR8ZcuXdLW1lZVVX3zzTc1Jycn\n6jqqBi9jYLd24zkfsz4QVf1SqDgRWQj8zCu6S0TagOtwNYsbA5JmAe/7cCh51PlsWjLPfWVirE5v\nGEaETJ06tcvmmv5CaWkpq1evpqWlhby8PBYsWNCj448dO8a9995LW1sbKSkplJaWxkjTyInXKKzN\nwHRgu+8kTwE+AF4C/kdEluE60bOBXbjaSbaI3Az8HtfR/rfxUNwwDKM7LF68mMWLF0d8fHZ2NtXV\n1VHUKPrEy4GsBFaKSC3QAsz3tZEDIrIBqMMN731YVS8DiMgioAI3jHelqh6Ij+qG8elCQwylNRIf\n7eXMsXFxIOpGUt0fIu67wHeDyLcAWzofYRhGrEhLS+PDDz+0Kd0HIOrXA0lLS4v4HDaViWEYIcnK\nyuL48eNhv6Q2Epf2FQkjxRyIYRghSU5Ojni1OmPgY3NhGYZhGBFhDsQwDMOICHMghmEYRkRIb4dx\n9WdE5BTQm6+OrsN9nzIQGCi2DBQ7wGzpr5gt8HlV/VxXiQa0A+ktIrJbVW+Ntx7RYKDYMlDsALOl\nv2K2dB9rwjIMwzAiwhyIYRiGERHmQMLTeQmxxGWg2DJQ7ACzpb9itnQT6wMxDMMwIsJqIIZhGEZE\nmAMxDMMwIsIcSBBEpEhEDonIYRF5LN76hEJEGkTkNyJSIyK7vWy4iGwTkXf9fpiXi4j8wNu0X0Qm\nBpxnvk//rojM7yPdV4rIST+lf7ssarqLSL6/Nof9sTGbSjaELUtE5Pe+bGpE5I6AuMe9XodEZFaA\nPOh9JyI3++Wf3xWR9SKSEiM7bhSRN0TkoIgcEJF/9PKEK5cwtiRiuaSJyC4R2edtKQmXv4ik+t+H\nffwfRWpjl3Rn2cJP04Zbb+QIMBq30NU+YFy89QqhawNw3VWyfwMe8+HHgO/78B3AVtziXFOAt7x8\nOFDv98N8eFgf6D4NmAjUxkJ33EJkf+aP2Qrc3se2LAG+FSTtOH9PpQI3+3stKdx9B2wA5vrwj4CF\nMbIjE5jowxnAb72+CVcuYWxJxHIRYIgPJwNv+esdNH/gG8CPfHgusD5SG7varAbSmUnAYVWtV7du\nyTrcOu6JwmxgtQ+vBv46QL5GHb8GrhWRTGAWsE1VT6vqGWAbUBRrJVX1V8DpWOju4z6rqjvV/XPW\nBJyrr2wJxWxgnap+rKpHgcO4ey7ofeff0KcD5f74wOsSVVT1hKru9eEm4CAwigQslzC2hKI/l4uq\n6gX/M9lvGib/wPIqB2Z4fXtkY3d0MwfSmVHA7wJ+Hyf8jRdPFKgUkT0i8jUvu15VT4D7EwEjvTyU\nXf3J3mjpPsqHr5b3NYt8087K9mYfem7LCOCsqv7hKnlM8c0eebi33YQul6tsgQQsFxFJEpEa4CTO\nIR8Jk3+Hzj7+nNc36s8AcyCdCdYm21/HOv+5qk4EbgceFpFpYdKGsisR7O2p7v3Bpv8C/hjIBU4A\n/+7l/d4WERkCbAT+SVXPh0saRNbfbUnIclHVy6qaC2ThagxfDJN/n9liDqQzx4EbA35nAe/HSZew\nqOr7fn8S2IS7sRp9UwF+f9InD2VXf7I3Wrof9+Gr5X2Gqjb6P30bUIorG+i5LR/gmoY+c5U8JohI\nMu6Bu1ZVf+bFCVkuwWxJ1HJpR1XPAttxfSCh8u/Q2ccPxTWxRv0ZYA6kM28D2X6EQwquE+qlOOvU\nCREZLCIZ7WFgJlCL07V91Mt84P98+CXgAT9yZgpwzjdHVAAzRWSYr87P9LJ4EBXdfVyTiEzxbb8P\nBJyrT2h/4Hrm4MoGnC1z/UiZm4FsXMdy0PvO9xW8Adztjw+8LtHWWYCfAAdVdVlAVMKVSyhbErRc\nPici1/pwOvAlXJ9OqPwDy+tu4Bde3x7Z2C3lYjFqINE33OiS3+LaGb8Tb31C6DgaN1piH3CgXU9c\nW+frwLt+P1w/GcnxnLfpN8CtAef6e1yH2mHgoT7SvwzXhNCKewP6ajR1B27FPRyOAP+Jn3WhD235\nb6/rfv9nzAxI/x2v1yECRiGFuu98We/yNv4vkBojOwpwTRf7gRq/3ZGI5RLGlkQslwlAtde5FvjX\ncPkDaf73YR8/OlIbu9psKhPDMAwjIqwJyzAMw4gIcyCGYRhGRJgDMQzDMCLCHIhhGIYREeZADMMw\njIgwB2IY3UBELssnM7jWdDVjqYh8XUQeiEK+DSJyXW/PYxixwIbxGkY3EJELqjokDvk24L6v+KCv\n8zaMrrAaiGH0Al9D+L649Rp2icifePkSEfmWD39TROr8BH7rvGy4iGz2sl+LyAQvHyEilSJSLSI/\nJmCeIhG53+dRIyI/9hPsJYnIiyJSK26djcVxuAzGpxRzIIbRPdKvasK6LyDuvKpOwn1Z/WyQYx8D\n8lR1AvB1LysBqr3sn3FTmwM8CexQ1Tzcl9I3AYjIF4H7cBNo5gKXga/gJgUcpap/qqq3AKuiaLNh\nhOUzXScxDAO46B/cwSgL2C8PEr8fWCsim4HNXlYAfBlAVX/hax5DcYtT/Y2XvyoiZ3z6GUA+8Lab\n5ol03KSGLwOjReSHwKtAZeQmGkbPsBqIYfQeDRFupxg3Z1Q+sMfPkBpuCu1g5xBgtarm+m2Mqi5R\nt2BTDm6G1oeBFRHaYBg9xhyIYfSe+wL2OwMjRGQQcKOqvgF8G7gWGAL8CtcEhYj8JfCBuvUqAuW3\n45aEBTeJ4d0iMtLHDReRz/sRWoNUdSPwL7ildQ2jT7AmLMPoHuniVoRr5zVVbR/Kmyoib+FeyOZd\ndVwS8FPfPCXAclU9KyJLgFUish9o5pPpt0uAMhHZC/wSOAagqnUi8gRuBcpBuJl/HwYu+vO0vww+\nHj2TDSM8NozXMHqBDbM1Ps1YE5ZhGIYREVYDMQzDMCLCaiCGYRhGRJgDMQzDMCLCHIhhGIYREeZA\nDMMwjIgwB2IYhmFExP8D4xtHXIAhJHAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Best Q-value and Policy:\n",
      "\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAEYCAYAAAADCA6iAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xl8VPW9//HXJ5N1BhIIIZCETa8K\nJRQSRbAPt95qLVUL9rYIXn/Xrb9qW6n2V+taW1u81PZWqXZ5aKlasLhcFRFEilqvXpcWwu5SsaJl\nCUsICWSZhJDMfH5/zCQOGpIMOUuWz9PHeSTn5My8vyeRz3zP9j2iqhhjjOm+FL8bYIwxfYUVVGOM\ncYgVVGOMcYgVVGOMcYgVVGOMcYgVVGOMcYgVVGNMnyAiD4vIPhF5J2FZroi8JCIfxL8Oji8XEfm1\niGwVkbdE5OSE11weX/8DEbk8mTZYQTXG9BULgWmfWHYL8LKqngi8HJ8H+DJwYny6GrgfYgUYuAOY\nCkwB7mgtwl1hBdUY0yeo6mtA9ScWzwAWxb9fBFyUsPwRjVkNDBKRAuBLwEuqWq2qB4CX+HSRPqrU\n7mzA0QzOTdHCEa68dadS8OfOryb1Z3sBqlpCvmXX12f5lm2803Kgmkh9WJx6vy/9a0irqiNJvWb9\nW03vAocSFi1Q1QWdvGyYqu4BUNU9IpIfX14E7ExYrzy+7GjLu8SVKlA4IpUnVwx14607lSlRX3I/\naO7yXoHjFld+zrfsN/823rds453d99zr6PtVVUcoe2FUUq8JFHxwSFUnO9SE9j4ctIPlXWK7/MYY\nzykQTfK/Y1QR35Un/nVffHk5MDJhvRHA7g6Wd4kVVGOMD5SIRpOajtFyoPVM/eXAsoTll8XP9p8G\n1MQPDbwAnCcig+Mno86LL+sS/w78GWP6rVgP1dnzHSLyOPB5IE9Eyomdrf858KSIfAPYAcyMr74S\nOB/YCjQAVwKoarWI3Amsja83V1U/eaLrqKygGmN80Y3d+Hap6iVH+dE57ayrwLVHeZ+HgYePpQ1W\nUI0xnlOUSB8ci9kKqjHGF07v8vcEVlCNMZ5TIGIF1RhjnGE9VGOMcYACzXYM1Rhjuk9R2+V3wu9/\nU8fKZY2kBCAlBe742SAmlqZ73QxjjJ8UIn2vnnatoIrINOA+IAA8qKo/P5awTesP89rLh3jq+aGk\nZwgHqiM0N396vZqaKDk5dhOXlyLNEbQlSmpWmt9NcUWkoYFAMGjZPUTswv6+p9OqJSIB4HfExg8c\nD1wiIsc0IkblvgiDclNIz4iNPzA4N0D+sMCn1vvj7+uZPb2SJx8NU1/n7q/9v35Wx+JHGtrm75tf\nx4MLwq5mtnroF/tYsfjjmzAW31fJkgerPMluVfPPg6y/bw3PXbyE2h21rudVP7eC2jfebJs/sOoF\nal551fXcPfPvo/JPj9L4wQeox8fu+mt2x4RIklNv0JVu4BRgq6p+pKqHgSeIjSWYtNPPymDvnggX\nfL6CO394kLWrm9pd73s3ZXPXrwZTviPCzAsq+eENB9iwtv11u+uC6Zk8/1xj2/zKFYc4/4JMV7I+\n6ewLs/nf5+va5l9bWcuZ52e7ntvS2MyHK/7Bi1evYPXP3iBnzCAuWPxVcscOcT07VFpKeNPmtvmG\nTZsJlUxyPbfotpsJnVxK3etvsvvnv+TgSy/TUlPjem5/zu6IAlFNbuoNurLL3974gFM/uZKIXE1s\n5GsKij7d6wQIhlJ4csVQ1pcdpuxvTfxgzgH+383ZXDTz07skx/1LKt+/NZvrbxrIn5c3cu1V1Xzl\n34Lc9tOcLjS564onpFFdFaVib4Tq6tihhsKjtN9pJxRnUlPVQlVFMzXVEQZmB8gvdH+Xe8kFTzD4\nhMFMve0McsYMcj0vUcaIIqJ19bTU1BCtD5OSFSR1sPtDH0pKCsHi8QSLxxOpr+fAipWUz51HwXVz\nyBid3DBylu2M3tLrTEZXCmqXxgeMD/S6AKB4YvpRP08CAWHK5zKY8rkMThqbxrIlDe0WVFWl7K+H\nWfpUA29vOswll4X42mx3jgVNOz+TVSsPUVkZ5cLp3vROW50xbSBv/LmOA/tbOOtC93unAGfd9QW2\nLv8Hr938MmPOO57jzj+RAQUDPMkGCE6aSMPmt4jU1REqLfEsN9rYSHjjZurL1kIghbxZM0krLLBs\nH8Qu7O+fBbVb4wMm+ueHLaSkwOjjYrFb/t7cbm9wxdIGHvh1HSeclMa/zQoy755BBALu/fIv+Eom\nP7yllgPVUR57Mte1nPacfWEO9922h9oDEf7rcW96DAVTiyiYWkRTzSH+uepDXrvpL2TkZDD1tjMY\nUDjQ9fxQaQlVTz5FJBxm+LXfcT0PoHLxYzRt205w0kTyLp1N2lDvBkDvr9mdiWr/LKhrgRNF5Dhg\nFzAb+PdjCWtoiPKzH9dQV6sEUmHU6FR+8vNP78IXjgiw6Kk8huR5s+t90tg0wvXKsOHtnyRz0+iT\nMmgMRxkyLJXcfG/PsGfkZDJuVjHjZhWz/91KxMUPrUTpBcOJNjWRmpNDao43vfJQySTyLpmFBLz9\n+/bn7I702x6qqraIyBxig6wGgIdV9d1jCSv+bDqPLu38E/LkUzOO5e27ZeVLeZ5ntrr/z8f7lt0q\nr9jbnkvRTT/wNC84odjTPMvumCJE+uD49l26DlVVVxIbkNUYYxzRX3f5jTHGUf12l98YY5wnRLSf\n7vIbY4yTYreeWkE1xhhH2C6/McY4QNV2+Y0xxjHRPthD7XsfEcaYHi92lj8lqakzIjJWRDYlTLUi\n8j0R+YmI7EpYfn7Ca24Vka0i8r6IfKm722U9VGOMD5zf5VfV94ESaBt2dBewFLgS+JWq3n1EC2LD\nkM4GioFC4C8icpKqRo61DdZDNcZ4rvUsfzJTks4BPlTV7R2sMwN4QlWbVPWfwFZiw5UeM1d6qC2a\nQkXEu9GLEp2Q5v4gye3JTjnkSy7A638/ybds+0Q2xyqS/J1SeSKyLmF+QXyUu/bMBh5PmJ8jIpcB\n64AbVPUAsaFJVyesUx5fdszs34MxxnOt9/IneQx1v6pOTpjaLaYikg5MB56KL7of+BdihwP2APe0\nrtpu07rBjqEaYzwXe4y0a+Xny8AGVa0AaP0KICJ/AFbEZx0bmrSV9VCNMZ5ThIgmNyXhEhJ290Uk\ncTTtrwLvxL9fDswWkYz48KQnAmXd2S7roRpjfOHGraciEgS+CFyTsPi/RKSEWMd4W+vPVPVdEXkS\n+DvQAlzbnTP8YAXVGOMDVVy5U0pVG4Ahn1j2Hx2sPw+Y51S+FVRjjA+kT94pZQXVGOM5xZ0eqt+s\noBpjfNFvH4FijDFOUsQegWKMMU7piz3UHrNFkRbltqt28dVTtvLP95v8bk6fp5EI++79I+XXzeVw\n+V5PcysWPMiO23/M4T17PMvtz3ri71yBqKYkNfUGnbZSRB4WkX0i8k5n63bHvT+qYMTxadz5+yLu\nvG4PlXua3Yzr96r/9Cxpw4cy9LuXUfXAY7RU13iSW/X0M6Tl55N/1ZVULlpMy8GDnuT2Zz3zdy5E\nkpx6g66U/YXANDcb8ch9VYQGBvjO7flMmJzFDXcN4z+v30t9bbeuse2Su35WxyOLGtrmfzW/jgW/\nD7ue257mw0pjQ9T1nJplfyElK5PBsy8k48Qx5F7xNap+/zjRBncHeDm46kVSMjPJvWg6mccfx5DZ\nM6l85FGijY2u5raqfm4FtW+82TZ/YNUL1Lzyquu5kYaGzldyid+/86Ppqz3UTo+hquprIjLGzUZc\ndv0R1+FSfHIW9z058ihrO+sr0zOZ+5NaLrs8CMCKFYd45E+5nmS32rb1MM89Ucf/vtDAzx7I56Ti\nDFfzcmace8R8xgmjGXbrt1zNBBg07bwj5jPHjKHgumtdz20VKi2l+tllZJ9xOgANmzYz7Jpvup67\nZ/59ZIwexYDTppB5wgmIeNfb8vt33pHe0utMhmMnpUTkauBqgPzC3nOua8KENPZXRanYG6GqOkpO\nTgpFRQHXcxsbovzP82FWPFmHKpz/9YEs+t5gQgN6xydxb5QxoohoXT0tNTVE68OkZAVJHTzY9dyi\n226m8b0t1L3+JtVPLyU0+RQGTJlMak6O69k9lar0ml5nMhyrfPGhtBYAjP1sZreGwPLa+ednsnLl\nISr3RfnK9ExPMqdP3cEJ49K55ed5jP6XdE8yDQQnTaRh81tE6uoIlZZ4kikpKQSLxxMsHk+kvp4D\nK1ZSPnceBdfNIWP0KE/a0BP1xQv7+94WHYPp0zNZvvwQK1ce4vzzvSmo//m7fPKGpXLrNft4+NcH\n2FtuJ+G8ECotIbxxE+HNbxGcNNGz3GhjI3V/Xc2+B/9Ic2UlebNmklZY0PkL+6jYiP2S1NQb9J59\ncxedNDaNcL0ybHiAYcPc390HmHpWkKlnBak5EOGFZ+u5+ep9DMpN4Zaf51EwIs2TNvRH6QXDiTY1\nkZqTQ2pOtieZlYsfo2nbdoKTJpJ36WzShg71JLdn66ePkRaRx4HPE3v8QDlwh6o+5HbDvPbiX/J8\nyc0ZHODiK3O4+Moc/r6piZSU3vFJ3JsV3fQDT/NCJZPIu2QWEvDmw7o3iJ3l73v/r3flLP8lXjTE\nwPgSd8/uG38EJxT73YQeqS/eKWW7/MYYz9m9/MYY4yA3Ruz3mxVUY4znYiP2Ww/VGGMcYbv8xhjj\nAEVo1r531YMVVGOM5/rtZVPGGOO8vnkvf9/bImNMr+DGracisk1E3haRTSKyLr4sV0ReEpEP4l8H\nx5eLiPxaRLaKyFsicnJ3t8kKqjHGc61n+ZOZkvCvqlqiqpPj87cAL6vqicDL8XmALwMnxqergfu7\nu12u7PLveSfIXf/i3cATiRbueMOX3DuOP8WXXID0O/vnvf8toV41qJn5BA93+WcQu30eYBHwKnBz\nfPkjqqrAahEZJCIFqnrMz4mxHqoxxnOtd0olMxEbT2RdwnR1u28NL4rI+oSfD2stkvGv+fHlRcDO\nhNeWx5cdMzspZYzxxTEMybc/YTf+aE5X1d0ikg+8JCJbOli3vQZ0a7fHCqoxxnNuXTalqrvjX/eJ\nyFJgClDRuisvIgXAvvjq5UDis5ZGALu7k2+7/MYYXzj9kD4RCYnIwNbvgfOAd4DlwOXx1S4HlsW/\nXw5cFj/bfxpQ053jp2A9VGOMH9SV0aaGAUvjD0FMBR5T1VUishZ4UkS+AewAZsbXXwmcD2wFGoAr\nu9sAK6jGGM+1PgLF0fdU/QiY1M7yKuCcdpYr4OgjYK2gGmN8YbeeGmOMA+xefmOMcZAVVGOMcYA9\nAsUYYxzk9EmpnqBHXIf6ii49Yn63bmOLbvSpNd7xa7s/nHvrEfO1G8qofO4Z13P9ztZIhIoFD7Lj\n9h9zeE+3Ljc03aUcy62nPV6nBVVERorIKyLynoi8KyLXe9EwY5xW9fQzpOXnk3/VlVQuWkzLwYO+\ntUVbWog2NbmeE2locD3jWLSelOp3BRVoAW5Q1c8ApwHXish4d5vlnXk/q2PRoo//p7tnfh2//33Y\nxxYZNxxc9SIpmZnkXjSdzOOPY8jsmVQ+8ijRxkZP23G4ooLqZcvZddcvaK7c73renvn3UfmnR2n8\n4ANil132HH2xoHZ6DDV+K1brSC11IvIesRFZ/u5UIyJEWK0vtc03c5ihFDr19h2aMT2TO35Sy+WX\nBwFYseIQi/+U60m2X9utzc3s+O09bfPRxgZC44pdz/Uze9C0846YzxwzhoLrHL2m+6iiTU2EN22m\nfk0ZKAyYeiqFN55HSmam69lFt91M43tbqHv9TaqfXkpo8ikMmDKZ1Jwc17M7YielABEZA5QCa9r5\n2dXEBmklk2BSjQgQ4DT5Ytv8bt1GLQeSeo9jNWFCGlVVUfbujVBdHSUnJ4WiIm8eHubXdktaGqPm\n3NA2X7uhjKZd5a7n+p3tl513zCW9sIAhsy4mfVh+5y9wkKSkECweT7B4PJH6eg6sWEn53HkUXDeH\njNGjPG3LJ2l/LqgiMgBYAnxPVWs/+XNVXQAsAMiW3J61b9GJC87P5PmVh6jcF2X6dPd7DaZ/yb/i\nMurWlFH58EJCJ5cw4NTJpOZ6sxcEEG1sJLxxM/VlayGQQt6smaQVFniWf9R29cGz/F0qqCKSRqyY\nPqqq3pyS9dD06ZncdHMt1dVRnn7Ku//RTf+QNW4sWePGEgmHCa/bQMVDCwmEQgyZPZM0lwtr5eLH\naNq2neCkieRdOpu0oUNdzesq1X56Yb/Ehm55CHhPVee73yTvjR2bRn29Mnx4gGHD+t6zwk3PEAiF\nyD77TLLPPpOm7TsQcf+qxVDJJPIumYUEetr/10Ik2iOu2nSUdHbmT0TOAF4H3gai8cW3qerKo70m\nW3J1qnxqcBdP+PVMqStGneFLLsC2Oz/nW7af7JlS3tl9z7007dzpWJdywEkFOuE3VyT1mjXTfr6+\nCyP2+6orZ/nfoP1HBRhjzDGxwVGMMcYpGjuO2tdYQTXG+KLfnuU3xhgnKf38OlRjjHGO3SlljDGO\nsWOoxhjjkL64y9/3rqw1xvR4qrGCmszUmaMNNSoiPxGRXSKyKT6dn/CaW0Vkq4i8LyJf6u52WQ/V\nGOMLF46htg41ukFEBgLrRaR1OLdfqerdiSvHhyGdDRQDhcBfROQkVY0cawOsh2qM8YVqclPn76d7\nVHVD/Ps6oHWo0aOZATyhqk2q+k9gKzClO9vU53qoadL3jst0xs9bMFPD/e/3bZxxDMdQ80RkXcL8\ngvgod5/yiaFGTwfmiMhlwDpivdgDxIrt6oSXldNxAe5UnyuoxpieT+nacdFP2N+Ve/k/OdSoiNwP\n3Ens8tc7gXuAq2j/lvpu9U5sl98Y4wtNcuqK9oYaVdUKVY2oahT4Ax/v1pcDIxNePgLY3Z1tsoJq\njPGeO2f52x1qVEQSR9P+KvBO/PvlwGwRyRCR44ATgbLubJbt8htj/OH8of/Tgf8A3haRTfFltwGX\niEhJPHEbcA2Aqr4rIk8Sez5eC3Btd87wgxVUY4xPnL6wv4OhRo86drOqzgPmOdUGK6jGGF/YrafG\nGOMAG23KGGOcooAVVGOMcYbt8htjjFOsoBpjjBMEjfa9Xf4ecWH/K7r0iPnduo0tutGn1njHr+3e\nfvNtR8zXla2laskzrucCfDj31iPmazeUUfmcN9kaiVCx4EF23P5jDu/Z40mmOQoXLuzvCTotqCKS\nKSJlIrI5PsbgT71omDFOq3r6GdLy88m/6koqFy2m5eBBv5vkC21pIdrU5Hcz3Ln31Gdd6aE2AV9Q\n1UlACTBNRE5zt1neuXNeLX9cFG6b/+U9ddz/+3ofW2TccHDVi6RkZpJ70XQyjz+OIbNnUvnIo0Qb\nG13Prn5uBbVvvNk2f2DVC9S88qrruZ90uKKC6mXL2XXXL2iu3O95/qdJklPP1+kxVFVVoLXCpMUn\nRz8vIkRYrS+1zTdzmKEUOhlxVBfNyOJHd9Ry5eUhAJavOMTji3M9yfZru7W5mV2/bLvVmWhDA8EJ\n413Pbc3e8dt7Ps5ubCA0rtj13EHTzjtiPnPMGAquu9b1XIBQaSnVzy4j+4zTAWjYtJlh13zTk+xo\nUxPhTZupX1MGCgOmnkrhjeeRkpnpSX6HekmvMxldOiklIgFgPXAC8DtVXdPOOlcDVwNkEkyqEQEC\nnCZfbJvfrduo5UBS73GsPjshjf1VEfbujVBVHSUnRxhRFPAk26/tlrQ0im78ftt8XdlaDu/c6Xpu\na/aoOTe0zdduKKNpV7kn2X7JGFFEtK6elpoaovVhUrKCpA4e7En2zjvmkl5YwJBZF5M+LN+TzC7r\ngwW1Syel4kNflRAb3mqKiExoZ50FqjpZVSenkeF0O1114QVZPPf8IZ5d3shF07P8bo7pg4KTJtKw\n+S3CmzYRKi3xLDf/issI5ORQ+fBCDr7wIi3V1Z5ld6j1wv5kpl4gqcumVPWgiLwKTOPjIbB6vYum\nZ3LDTTVUV0d59ukhfjfH9EGh0hKqnnyKSDjM8Gu/41lu1rixZI0bSyQcJrxuAxUPLSQQCjFk9kzS\ncr05tHU0/fLCfhEZCjTHi2kWcC7wC9db5qFxY9Oor1eGDw8wbJg3u/umf0kvGE60qYnUnBxSc7I9\nzw+EQmSffSbZZ59J0/YdiPSAKyb7YEEV7eRjQkQmAouAALFDBE+q6tyOXpMtuTpVznGskcl4dOeb\nna/kgktHnu5LLsDW+f5ddOHnM6X8fJZWf7P7nntp2rnTsT92xpgROvz265N6zY5v3rS+K49A8VNX\nzvK/RexhV8YY4xjpg5+HduupMcZ7vehi/WRYQTXG+KD3nLlPhhVUY4w/rIdqjDEOsYJqjDEOsYJq\njDEO6KOPQOkBV/caY/oj0eSmTt9PZJqIvC8iW0XkFve34NOsoBpj/OHgeKjxAZx+B3wZGA9cIiLe\nDKGWwAqqMaYvmAJsVdWPVPUw8AQww+tG9LljqEFJ87sJ/Uqaj7eeRoL+nNXog4f+fHEMd0rlici6\nhPkFqrog/n0RkDgGZTkw9dhbd2z6XEE1xvQSyX8y7e/gXv723szzT1wrqMYY7zl/62k5MDJhfgSw\n29GELrCCaozxhUQdfbu1wIkichywC5gN/LujCV1gBdUY4w8He6iq2iIic4AXiA01+rCqvutcQtdY\nQTXG+MPhI5yquhJY6ey7JscKqjHGc129WL+3sYJqjPFHH7z+zAqqMcYf1kM1xhhn2C6/McY4pQ8W\n1B5xL/8ruvSI+d26jS260afWeMev7d5+821HzNeVraVqyTOu5wJsufvIQYAOvlXG3heWeJJtepAk\nR5rqLb3ZLhdUEQmIyEYRWeFmg4wx/YSDo031FMn0UK8H3nOrIX750bwD/GFhXdv8z+45yK8fqPWx\nRcYNkYYG37Krn1tB7Rtvts0fWPUCNa+86lt7tKWFaFOTb/kfNyTJqRfo0jFUERkBXADMA77vdCMi\nRFitL7XNN3OYoRQ6HdOur88IcfMdB/jmFQMBeOa5BpY+mu9Jtl/brc3N7Prl/Lb5aEMDwQneDB2p\nLc189NDdbfORQw0MPKHY9dzdv7qPjFGjGHjaFDJPOAER7y7ZCZWWUv3sMrLPOB2Ahk2bGXbNNz3L\nb3W4ooL61WtoeOtthl55BRkjijxvQ6LeshufjK6elLoXuAkYeLQVRORq4GqATIJJNSJAgNPki23z\nu3UbtRxI6j2O1aQJ6VTuj7Bnbwv7q6IMyklhZJE35+r82m5JS6Poxo8/F+vK1nJ4584OXuFgdmoa\nx3/jB23zB98q49Ae97NH3Hozje9tofaNN6laspQBk09hwKmTSc3JcT07Y0QR0bp6WmpqiNaHSckK\nkjp4sOu5ANGmJsKbNlO/pgwUBkw9lcIbzyMlM9OT/P6m08ohIhcC+1R1vYh8/mjrxcclXACQLbm9\n6rPnoguCPPt8IxX7Inx9Rsjv5hgXSEoKweLxBIvHE6mvp/r5ley8cx6F351DxuhRrucHJ02kYfNb\nROrqCJWWuJ7Xaucdc0kvLGDIrItJH+bNnleX9aoq0TVdOYZ6OjBdRLYRGwX7CyKy2NVWeezrM4I8\nvSzMs883cNEFyfWuTe8RbWyk9m+rqXjojzRXVpI3ayZphQWeZIdKSwhv3ER481sEJ030JBMg/4rL\nCOTkUPnwQg6+8CIt1dWeZXeoj57l77SHqqq3ArcCxHuoP1DV/+Nyuzz1mbHp1IeVwuEBhg8L+N0c\n44J9ix+jaft2QpMmMvTfZ5M2dKin+ekFw4k2NZGak0NqTrZnuVnjxpI1biyRcJjwug1UPLSQQCjE\nkNkzScvN9awd7eolRTIZotr1rUooqBd2tF625OpUOaebTTs2S8vLfMn96ogpvuQCbJ1/mm/ZWfv8\nu5T50NCuD6gZfuddgp8ZhwS6/4HZ229Bb9q+g0B2NqmDB3X5NbvvuZemnTsd2/LMwpE65pvJnd9+\nf+7313cwYn+PkNTZF1V9FXjVlZYY46LQBPevJOgtvDhm3Bmh9+zGJ8NuPTXG+MMKqjHGOKAXnWhK\nhhVUY4w/rKAaY4xDrKAaY4wzbJffGGOcoICzj5HuEaygGmN80Rd7qD1igGljTD/k4fB9IvJLEdki\nIm+JyFIRGRRfPkZEGkVkU3x6IOE1p4jI2yKyVUR+LV0YoswKqjHGFx7fy/8SMEFVJwL/IH47fdyH\nqloSn76VsPx+YiPonRifpnUWYgXVGOMPD3uoqvqiqrbEZ1cDIzpaX0QKgGxV/ZvG7s9/BLios5w+\ndww1mJLudxP6leaQfwfCevs99f3asRXJPBFZlzC/ID5saLKuAv47Yf44EdkI1AK3q+rrQBFQnrBO\neXxZh/pcQTXG9HwSn5K0v6PBUUTkL8Dwdn70Q1VdFl/nh0AL8Gj8Z3uAUapaJSKnAM+KSPFRmtfp\nR4AVVGOMPxzeuVHVczv6uYhcDlwInBPfjUdVm4Cm+PfrReRD4CRiPdLEwwIjgN2dtcGOoRpjfOHl\nSSkRmQbcDExX1YaE5UNFJBD//nhiJ58+UtU9QJ2InBY/u38ZsKyzHOuhGmP84e3h998CGcBL8auf\nVsfP6J8FzBWRFiACfEtVWx9r8G1gIZAF/Dk+dcgKqjHGHx4WVFU94SjLlwBLjvKzdcCEZHKsoBpj\nvGfD9xljjIOsoBpjjDOsh2qMMU6xgmqMMc7oiz3UHnEd6iu69Ij53bqNLbrRp9Z4x6/t3n7zbUfM\n15WtpWrJM67nAnw499Yj5ms3lFH5nDfZpgdJ9j7+XlJ8u9RDFZFtQB2x67RaevqzsY3p6bSlBY1E\nSMnIcDUn0tBAIBh0NeOY9ZIimYxkeqj/Gh/eqk8V01v+cz/3L6xpm//p3VXMf+CAjy0ybql+bgW1\nb7zZNn9g1QvUvPKqp204XFFB9bLl7LrrFzRX7nc9b8/8+6j806M0fvAB8bstewTB8+H7PNEjjqFG\niLBaX2qbb+YwQyn0JHvWjIF8/8eVfPuKHACeWl7Pyse8yfZru7W5mV2/nN82H21oIDhhvOu5rdk7\nfnvPx9mNDYTGFXuSHSotpfrZZWSfcToADZs2M+yab7qeG21qIrxpM/VrykBhwNRTKbzxPFIyM13P\nLrrtZhrf20Ld629S/fRSQpPQDQ33AAAS8ElEQVRPYcCUyaTm5Lie3aleUiST0dWCqsCLIqLA79sb\nMktEriY2GCuZJLeLESDAafLFtvnduo1avOklln42g337I+ze20JlVYTBgwKMGpHmSbZf2y1paRTd\n+P22+bqytRzeudP13NbsUXNuaJuv3VBG067yDl7hnIwRRUTr6mmpqSFaHyYlK0jq4MGu5+68Yy7p\nhQUMmXUx6cPyXc9LJCkpBIvHEyweT6S+ngMrVlI+dx4F180hY/QoT9vyqbb1oB6zU7paUE9X1d0i\nkk/sXtgtqvpa4grxIrsAIFtye9Vv6msXDmDJinr27oswa8YAv5tjXBScNJGGzW8RqasjVFriSWb+\nFZdRt6aMyocXEjq5hAGnTiY1N9eTbIBoYyPhjZupL1sLgRTyZs0krbDAs/x29aITTcnoUkFV1d3x\nr/tEZCkwBXit41f1HrMuGsA1P6hkf3WEV57pdAxZ04uFSkuoevIpIuEww6/9jieZWePGkjVuLJFw\nmPC6DVQ8tJBAKMSQ2TNJc7mwVi5+jKZt2wlOmkjepbNJGzrU1bxk9JbjosnotKCKSAhIUdW6+Pfn\nAXNdb5mHisdmUFcfpWh4KgXDesRhZeOS9ILhRJuaSM3JITUn29PsQChE9tlnkn32mTRt34GI+1ct\nhkomkXfJLCQQcD0rWdIHHyMtnZ35i48R2HrBZCrwmKrO6+g12ZKrU+UcZ1qYpBd2b/Il90uF3uw+\ntmfr/NN8y04N+/cckhYfH7/S3+y+516adu507I8dyhupxRf8v6Res/aRG9b39KuMOu2OqepHwCQP\n2mKM6S960aVQybD9W2OMP6ygGmNM97Ve2N/XWEE1xvijH1+HaowxjrIeqjHGOKE/X9hvjDFO64vX\nofaI8VCNMf2Qh+OhishPRGSXiGyKT+cn/OxWEdkqIu+LyJcSlk+LL9sqIrd0Jcd6qMYYX/hwDPVX\nqnr3EW0QGQ/MBoqBQuAvInJS/Me/A74IlANrRWS5qv69owArqMYY7yk95Sz/DOAJVW0C/ikiW4mN\nVQKwNX5jEyLyRHxdK6heWFK+2rfsic9M9S27JeRbtOnljqGHmici6xLmF7Q3lGgH5ojIZcA64AZV\nPQAUAYn/eMvjywB2fmJ5p//QrKAaY/yRfEHd39G9/CLyF2B4Oz/6IXA/cGc89U7gHuAqYvcYtNey\n9s4vddpiK6jGGM+5caeUqp7bpWyRPwAr4rPlwMiEH48Adse/P9ryo7Kz/MYY76kmP3WDiCSOqP1V\n4J3498uB2SKSISLHAScCZcBa4EQROU5E0omduFreWY71UI0xvvD4LP9/iUgJsd32bcA1AKr6rog8\nSexkUwtwrapGAERkDvACEAAeVtV3OwuxgmqM8YeHBVVV/6ODn80DPjXGs6quBFYmk2MF1RjjC7uX\n3xhjnKBAtO9VVCuoxhh/9L16agXVGOMP2+U3xhin9IxbTx1lBdUY4z214ftc84ouPWJ+t25ji270\nqTXGOE8jESoWPMiO23/M4T17/G6O72J3SmlSU2/QpYIqIoNE5GkR2SIi74nI59xumDFOijQ0+Jpf\n9fQzpOXnk3/VlVQuWkzLwYO+tUVbWog2NfmW3yaa5NQLdLWHeh+wSlXHAZOA99xrkrdu+c/93L+w\npm3+p3dXMf+BA55k/3jeQf6wsL5t/q57avjNA3Wu5x5Y9jx1r/21bf7gyhepffl/Xc8FqH5uBbVv\nvPlxW1a9QM0rr7qeu2f+fVT+6VEaP/gA9bi3c3DVi6RkZpJ70XQyjz+OIbNnUvnIo0QbGz1tx+GK\nCqqXLWfXXb+guXK/p9nt6Zc9VBHJBs4CHgJQ1cOq6ujHa4QIq/WltulDOr3DyzGzZgzkyWUfF7Gn\nltfz9QsHeJL9tRlBlj73cc9p6XONXPSVLNdzQyeXEN64uW2+YeNmgqUTXc8FCJWWEt6UkL1pM6GS\nSa7nFt12M6GTS6l7/U12//yXHHzpZVpqajp/oQMGTTuP3BlfaZvPHDOGguuuJSXL/b91tKmJujVl\n7Pn1b6l64inShg2j8MYbyBhR1PmL3ZTsaP29o5526aTU8UAl8EcRmQSsB65X1XDiSiJyNXA1QCbB\npBoRIMBp8sW2+d26jVq86SWWfjaDffsj7N7bQmVVhMGDAowakeZJ9qQJ6VTuj7Jnb4T9VREG5aQw\nssj984TpI4uI1NXTUlNDtC5MSlYWqbmDXc8FyBhRRLQ1uz5MSlaQ1MHuZ0tKCsHi8QSLxxOpr+fA\nipWUz51HwXVzyBg9yvV8v+y8Yy7phQUMmXUx6cPy/W5Ogu4PeNITdeVfbypwMvBdVV0jIvcBtwA/\nSlwpPtDrAoBsye1Vv6mvXTiAJSvq2bsvwqwZ3vROW824IItlzzdQsS/K12Yk90HUHaGSz9Kw8W0i\ntXUETynxLBcgOGkiDZvfIlJXR6jUu+xoYyPhjZupL1sLgRTyZs0krbCg8xf2YvlXXEbdmjIqH15I\n6OQSBpw6mdTcXL+bBfTf61DLgXJVXROff5pYQe0zZl00gGt+UMn+6givPOPtrtDXZgS57sYDVFVH\nWblkqGe5wVNKqH78aSL1YYZd/23PcgFCpSVUPfkUkXCY4dd+x5PMysWP0bRtO8FJE8m7dDZpQ737\nXfspa9xYssaNJRIOE163gYqHFhIIhRgyeyZpfhfW/thDVdW9IrJTRMaq6vvAOXTyXJXepnhsBnX1\nUYqGp1IwzNtLcz8zNo36cJTC4QGGDwt4lpteMJzooSYCg3JIzcn2LLctu6mJ1BzvskMlk8i7ZBYS\n8O533JMEQiGyzz6T7LPPpGn7DkR8vmKyj16H2tXq8V3g0fhAqx8BVzrZiH+Vrx4xXyhjKGSMkxGd\n2vyKf8fR/vZye09tcF/hbTf4kgtQdNMPPM0LTij2NK8n6zHHjPtjDxVAVTcBR32WizHGJK3v1VO7\n9dQY44/ecm1pMqygGmP8YQXVGGMcoPSa20mTYQXVGOM5offcTpoMK6jGGH9YQTXGGIf0wYLaI8ZD\nNcb0M63HUD0avk9E/ltENsWnbSKyKb58jIg0JvzsgYTXnCIib4vIVhH5tYhIZznWQzXG+MLLY6iq\nOqstV+QeIHGosQ9Vtb1BJe4nNuDTamAlMA34c0c51kM1xvhDNbnJAfFe5sXA452sVwBkq+rfNDaA\n7iPARZ29vys91KYRIbbecJobb90Fm3zK9c9JE8p9y/5g80jfsvvinTb9xzEVyTwRWZcwvyA+yl0y\nzgQqVPWDhGXHichGoBa4XVVfB4qIDQzVqjy+rEO2y2+M8Z5yLAV1v6oe9RZ4EfkL0N7AGD9U1WXx\n7y/hyN7pHmCUqlaJyCnAsyJSTOyxV+21ukNWUI0x/nD4wn5VPbejn4tIKvBvwCkJr2kCmuLfrxeR\nD4GTiPVIRyS8fASwu7M22DFUY4wvJBpNanLAucAWVW3blReRoSISiH9/PHAi8JGq7gHqROS0+HHX\ny4Bl7b1pIuuhGmO8p0DU84Pgs/n0yaizgLki0gJEgG+panX8Z98GFgJZxM7ud3iGH6ygGmN84f0z\npVT1inaWLQGWHGX9dcCEZDKsoBpj/NEH75SygmqM8YcVVGOMcYA/x1BdZwXVGOMDBe17A6JaQTXG\n+KMP7vL3++tQKypbuPQ7ezlh6jZOPW8np1+4k6Ur6/1ululjNBKhYsGD7Lj9xxzes6ffZB9V6y5/\nMlMv0GlBFZGxCUNbbRKRWhH5nheNc5uq8m9X7uHMqVlsXTOGtS+O5LH7h7NrT4vfTTN9TNXTz5CW\nn0/+VVdSuWgxLQcP9ovsDvkwOIrbOi2oqvq+qpbEh7c6BWgAlrrdMG1pIdrU5GrG/7zRSHqa8K3L\nc9qWjR6ZxpxvDHI192gOH1bCDf4cV4o2R4g0Nnue68XfGSDS0OB6xtEcXPUiKZmZ5F40nczjj2PI\n7JlUPvIo0cbGPp3dqT5YUJM9hnoOsbEDt7vRGIDDFRXUr15Dw1tvM/TKK8gY0ekAL8fs7+8fpvSz\nGa69f1e9/0EzjzwWZvmfG1n84BAmTUj3LLt+ezW7nn+Hfa9/yKS5F5B9Yr4nuYf3Jvydr3L37wyw\nZ/59ZIwexYDTppB5wgl0Yaxgxwyadt4R85ljxlBw3bV9PrtjvadIJiPZgtrerVsAiMjVxAZjJTB4\ncFJvGm1qIrxpM/VrykBhwNRTKbzxPFIyM5NsXvfMubWSN8tivdY1q9wdli7cEGXpc4386fEwqnDp\nrBB/vSGbgQPcP6wdaWxm76v/YPfKd1GFwi+P53NXnEZq0N1C3vZ3Xl0GwIApp1J4kzd/56Lbbqbx\nvS3Uvf4m1U8vJTT5FAZMmUxqTk7nLzbOU8CZ+/N7lC4XVBFJB6YDt7b38/i4hAsAMkaOTOqjZ+cd\nc0kvLGDIrItJH+ZNDwlg/Nh0nnn+4xNQv71rKPurIkyZttP17LGleyj+TBq/uXswJ52Q5npeov/9\n+oMMPH4I4288l9CoXM9yd/44/nee7e3fGUBSUggWjydYPJ5IfT0HVqykfO48Cq6bQ8boUZ62xcT1\nwR5qMt2hLwMbVLXC6UbkX3EZgZwcKh9eyMEXXqSlurrzFzngC2dkcahJuX/Rx09DaGj05lNz0YIh\nFAwPcOk3qvjFr2rZUe7dibBJPzmfjLwBbP7RCj5ctIbGvbWe5OZfGf87P7SQg6u8+zu3ijY2UvfX\n1ex78I80V1aSN2smaYUFnrbBJOjnx1A/OTCrY7LGjSVr3Fgi4TDhdRuoeGghgVCIIbNnkpbrXg9K\nRHjmjwV8/4793P27AwwdEiAUTOGu24e4ltnqnLMzOefsTKqrI/z3Mw38+5VV5Oam8Ju7BzN6pLuX\nBw85dTRDTh3N4ZpG9r60hU23P0d6ThbjbzyXrOHZruV+6u/84EICA0IMmTWTtCHu9pQrFz9G07bt\nBCdNJO/S2aQNHepqnulM77kUKhld+pcrIkHgi8A1bjYmEAqRffaZZJ99Jk3bdyDi/vHEgmGpPP5A\ne4N8eyM3N8C3/+9Avv1/B7J+42ECHl4ZnJ6TxaivlzLq66XUvLcXSfHmRM2n/s4p7m90qGQSeZfM\nQgIB17NMFyhof71TSlUbAPe7bQn643GtU0q9O7v/STmf8edDxau/c3BCsSc5Jgn9tYdqjDGO6yXH\nRZNhBdUY4z3V/n3ZlDHGOMp6qMYY4wy1Hqoxxjih91xbmgwrqMYY79mI/cYY4wwlNk5rX2MF1Rjj\nPbVHoBhjjGPUdvmNMcYhfbCHKurCmTYRqQSOdRDqPGC/g83pDdn9cZv9zO6P29zd7NGq6tiIMiKy\nKt6eZOxX1WlOtcENrhTU7hCRdao6uT9l98dt9jO7P26z39n9Rb9/6qkxxjjFCqoxxjikJxbUBf0w\nuz9us5/Z/XGb/c7uF3rcMVRjjOmtemIP1RhjeiUrqMYY45AeU1BFZJqIvC8iW0XkFo+zHxaRfSLy\njse5I0XkFRF5T0TeFZHrPczOFJEyEdkcz/6pV9nx/ICIbBSRFR7nbhORt0Vkk4is8zh7kIg8LSJb\n4n/zz3mQOTa+ra1TrYh8z+3c/qpHHEMVkQDwD2IPAiwH1gKXqOrfPco/C6gHHlHVCV5kxnMLgAJV\n3SAiA4H1wEVebLeICBBS1XoRSQPeAK5X1dVuZ8fzvw9MBrJV9UIvMuO524DJqur5xfUisgh4XVUf\nFJF0IKiqBz3MDwC7gKmqeqw33pgO9JQe6hRgq6p+pKqHgSeAGV6Fq+prgLcPiY/l7lHVDfHv64D3\ngCKPslVV6+OzafHJk09XERkBXAA86EVeTyAi2cBZwEMAqnrYy2Iadw7woRVT9/SUgloE7EyYL8ej\nwtJTiMgYoBRY42FmQEQ2AfuAl1TVq+x7gZsAP27mVuBFEVkvIld7mHs8UAn8MX6o40ERCXmYDzAb\neNzjzH6lpxTU9h4I7/+xCI+IyABgCfA9Va31KldVI6paAowApoiI64c7RORCYJ+qrnc76yhOV9WT\ngS8D18YP93ghFTgZuF9VS4Ew4Nm5gvghhunAU15l9kc9paCWAyMT5kcAu31qi6fixy+XAI+q6jN+\ntCG+6/kq4MXAE6cD0+PHMp8AviAiiz3IBUBVd8e/7gOWEjvc5IVyoDxhL+BpYgXWK18GNqhqhYeZ\n/U5PKahrgRNF5Lj4J+lsYLnPbXJd/MTQQ8B7qjrf4+yhIjIo/n0WcC6wxe1cVb1VVUeo6hhif+f/\nUdX/43YugIiE4if/iO9unwd4cmWHqu4FdorI2PiicwBPTrrGXYLt7ruuR4yHqqotIjIHeAEIAA+r\n6rte5YvI48DngTwRKQfuUNWHPIg+HfgP4O34sUyA21R1pQfZBcCi+JnfFOBJVfX0EiYfDAOWxj7H\nSAUeU9VVHuZ/F3g03mn4CLjSi1ARCRK7guYaL/L6sx5x2ZQxxvQFPWWX3xhjej0rqMYY4xArqMYY\n4xArqMYY4xArqMYY4xArqMYY4xArqMYY45D/D3tqlpOVhnlbAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "simulator.reset()\n",
    "\n",
    "#INSERT YOUR CODE FOR INIT PARAMS HERE\n",
    "\n",
    "learning_episodes = 30000\n",
    "learning_rate = 0.1\n",
    "epsilon = 0.3\n",
    "do_test= True\n",
    "test_interval = 100\n",
    "ql_agent = QLAgent(epsilon, learning_rate, learning_episodes, map_size,\n",
    "                   test_interval = test_interval, do_test = do_test)\n",
    "start_time = time.time()\n",
    "total_rewards, q_table = ql_agent.learn_and_evaluate()\n",
    "run_time['Q-learning agent'] = time.time() - start_time\n",
    "print(\"Learning time:\\n\")\n",
    "print(run_time['Q-learning agent'])\n",
    "if do_test:\n",
    "    plot_result(total_rewards ,ql_agent.test_interval, [ql_agent.agent_name])\n",
    "plot_image(q_table, MAP[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SARSA Agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SARSAagent(agent):\n",
    "    def __init__(self, epsilon, learning_rate, learning_episodes, map_size, \n",
    "                 test_interval = 100, action_space = 4, beta = 0.999, do_test = True):\n",
    "        super().__init__(epsilon, learning_rate, learning_episodes, map_size,\n",
    "                         test_interval = test_interval, action_space = action_space, beta = beta, do_test = do_test)\n",
    "        self.agent_name = \"SARSA Agent\"\n",
    "        \n",
    "    def learn(self):\n",
    "        for _ in range(self.test_interval):\n",
    "            #INSERT YOUR CODE HERE\n",
    "            total_rewards = 0\n",
    "            simulator.reset()\n",
    "            state = 0\n",
    "            action = self.explore_or_exploit_policy(state)\n",
    "            done = False\n",
    "            while not done:\n",
    "                s_dash, reward, done, _ = simulator.step(action)\n",
    "                a_dash = self.explore_or_exploit_policy(s_dash)\n",
    "                self.q_table[state][action] = self.q_table[state][action] + self.learning_rate*(reward + self.beta*self.q_table[s_dash][a_dash]-self.q_table[state][action])\n",
    "                state = s_dash\n",
    "                action = a_dash\n",
    "                total_rewards += reward\n",
    "        return total_rewards/self.test_interval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Test Number:  18%|█▊        | 179/1000 [00:09<00:43, 18.94it/s]"
     ]
    }
   ],
   "source": [
    "simulator.reset()\n",
    "#INSERT YOUR CODE FOR INIT PARAMS HERE\n",
    "learning_episodes = 100000\n",
    "learning_rate = 0.1\n",
    "epsilon = 0.3\n",
    "do_test= True\n",
    "test_interval = 100\n",
    "sarsa_agent = SARSAagent(epsilon, learning_rate, learning_episodes, map_size,\n",
    "                         test_interval = test_interval, do_test = do_test)\n",
    "start_time = time.time()\n",
    "total_rewards, q_table = sarsa_agent.learn_and_evaluate()\n",
    "run_time['SARSA agent'] = time.time() - start_time\n",
    "print(\"Learning time:\\n\")\n",
    "print(run_time['SARSA agent'])\n",
    "if do_test:\n",
    "    plot_result(total_rewards, sarsa_agent.test_interval, [sarsa_agent.agent_name])\n",
    "plot_image(q_table, MAP[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# Distibuted Q-Learning\n",
    "***\n",
    "## init Ray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ray.shutdown()\n",
    "ray.init(include_webui=False, ignore_reinit_error=True, redis_max_memory=500000000, object_store_memory=5000000000, temp_dir = '~/ray_tmp')d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Distibuted Q-learning Agent \n",
    "\n",
    "Below you will implement a distributed Q-Learning algorithm, where both the learning and evaluation/testing is done in a distributed way. The goal is to demonstrate a speedup in learning (in terms of wall-clock time) by creating multiple workers to collect data and do the evaluation. We have provided a schema for how to implement this. \n",
    "\n",
    "- Main Agent: Setup all the wokrers and server and turn them on.  \n",
    "- Collector: There is a simulator inside each collector. Their job is collecting exprience from the simulator, and sending the experience the Q-table server.  \n",
    "- Evaluator: There is a simulator inside each evaluator. Their job is taking a Q-table from server, then testing the performace of the greedy policy and sending the results back to the server.  \n",
    "- Server: It maintains the Q-table. It Takes expriences from collector and performs the appropriate learning updates. It also responds to the evaluator periodically when it is time to perform tests/evaluations.   \n",
    "  \n",
    "We have provided the Evaluator code, so you don't need to implement that yourself. However, understanding that code should be helpful for your implementation of other parts. \n",
    "\n",
    "After you complete the coding for this part, you need to peform evaluations on the two maps using the following number of workers: (collector workers, evaluator workers) = (2,4), (4,4), (8,4).  You can use $\\epsilon = 0.1$ and the best of the learning rates that you considered. \n",
    "\n",
    "```python\n",
    "\n",
    "\"\"\"\n",
    "\n",
    " +---------------+\n",
    " |               |\n",
    " |     Agent     |\n",
    " |               | initializes all the wokrers and server.\n",
    " |               |\n",
    " +---------------+\n",
    "                                             \n",
    "                                             \n",
    "            +-----------+         +-----------+       +-----------+         +-----------+  \n",
    "            |           |         |           |       |           |         |           |       \n",
    "            |  Worker   |         |  Worker   |       |  Worker   |         |  Worker   |       \n",
    "            |(Collector)|--------▷|(Collector)|------▷|(Collector)|--------▷|(Collector)|               \n",
    "            |           |         |           |       |           |         |           |       \n",
    "            +-----------+         +-----------+       +-----------+         +-----------+       \n",
    "                  |                     |                   |                     |            \n",
    "                  |                     |                   |                     |             \n",
    "                  +-- batch Exprience --+---------+---------+-- batch Exprience --+             \n",
    "                                                  |                                             \n",
    "                                                  |\n",
    "                                                  ▽\n",
    "                                          +----------------+                                            \n",
    "                                          |                |                                                     \n",
    "                                          |  QL Server     |  \n",
    "                                          |   (learner)    |                   \n",
    "                                          +----------------+                   \n",
    "                                                   |\n",
    "                                                   |\n",
    "                   +-------- Q-tbale -------+---------+---------+-- Q-tbale -------+ \n",
    "                   |                     |                   |                     |              \n",
    "                   |                     |                   |                     | \n",
    "                   ▽                     ▽                   ▽                     ▽\n",
    "            +-----------+         +-----------+       +-----------+         +-----------+  \n",
    "            |           |         |           |       |           |         |           |       \n",
    "            |  Worker   |         |  Worker   |       |  Worker   |         |  Worker   |       \n",
    "            |(Evaluator)|         |(Evaluator)|       |(Evaluator)|         |(Evaluator)|               \n",
    "            |           |         |           |       |           |         |           |       \n",
    "            +-----------+         +-----------+       +-----------+         +-----------+                                                                                                                      \n",
    "\"\"\"\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@ray.remote    \n",
    "class QLAgent_server(agent):\n",
    "    def __init__(self, epsilon, learning_rate, learning_episodes, map_size,\n",
    "                 test_interval = 100, batch_size = 100, action_space = 4, beta = 0.999, do_test = True):\n",
    "        super().__init__(epsilon, learning_rate, learning_episodes, map_size, \n",
    "                         test_interval = test_interval, action_space = action_space, beta = beta, do_test = do_test)\n",
    "        self.collector_done = False\n",
    "        self.evaluator_done = False\n",
    "        self.learning_episodes = learning_episodes\n",
    "        self.episode = 0\n",
    "        self.reuslts = []\n",
    "        self.batch_size = batch_size\n",
    "        self.privous_q_tables = []\n",
    "        self.results = [0] * (self.batch_num + 1)\n",
    "        self.reuslt_count = 0\n",
    "        \n",
    "    def learn(self, experiences):\n",
    "        #INSERT YOUR CODE HERE\n",
    "        \n",
    "        if self.do_test:\n",
    "            if self.episode // self.test_interval + 1 > len(self.privous_q_tables):\n",
    "                self.privous_q_tables.append(self.q_table)\n",
    "        return self.get_q_table()\n",
    "        \n",
    "    def get_q_table(self):\n",
    "        if self.episode >= self.learning_episodes:\n",
    "            self.collector_done = True\n",
    "            \n",
    "        return self.q_table, self.collector_done\n",
    "    \n",
    "    # evalutor\n",
    "    def add_result(self, result, num):\n",
    "        self.results[num] = result\n",
    "    \n",
    "    def get_reuslts(self):\n",
    "        return self.results, self.q_table\n",
    "    \n",
    "    def ask_evaluation(self):\n",
    "        if len(self.privous_q_tables) > self.reuslt_count:\n",
    "            num = self.reuslt_count\n",
    "            evluation_q_table = self.privous_q_tables[num]\n",
    "            self.reuslt_count += 1\n",
    "            return evluation_q_table, False, num\n",
    "        else:\n",
    "            if self.episode >= self.learning_episodes:\n",
    "                self.evaluator_done = True\n",
    "            return [], self.evaluator_done, None\n",
    "    \n",
    "@ray.remote    \n",
    "def collecting_worker(server, simulator, epsilon, action_space = 4, batch_size = 100):\n",
    "    def greedy_policy(curr_state):\n",
    "        #INSERT YOUR CODE HERE\n",
    "\n",
    "    def explore_or_exploit_policy(curr_state):\n",
    "        #INSERT YOUR CODE HERE\n",
    "        \n",
    "    q_table, learn_done = ray.get(server.get_q_table.remote())\n",
    "    while True:\n",
    "        if learn_done:\n",
    "            break\n",
    "        #INSERT YOUR CODE HERE\n",
    "        \n",
    "@ray.remote\n",
    "def evaluation_worker(server, trials = 100, action_space = 4, beta = 0.999):\n",
    "    def greedy_policy(curr_state):\n",
    "        #INSERT YOUR CODE HERE\n",
    "    while True:\n",
    "        q_table, done, num = ray.get(server.ask_evaluation.remote())\n",
    "        if done:\n",
    "            break\n",
    "        if len(q_table) == 0:\n",
    "            continue\n",
    "        total_reward = 0\n",
    "        for _ in range(trials):\n",
    "            simulator.reset()\n",
    "            done = False\n",
    "            steps = 0\n",
    "            observation, reward, done, info = simulator.step(greedy_policy(0))\n",
    "            total_reward += (beta ** steps) * reward\n",
    "            steps += 1\n",
    "            while not done:\n",
    "                observation, reward, done, info = simulator.step(greedy_policy(observation))\n",
    "                total_reward += (beta ** steps) * reward\n",
    "                steps += 1\n",
    "        server.add_result.remote(total_reward / trials, num)\n",
    "\n",
    "class distributed_QL_agent():\n",
    "    def __init__(self, epsilon, learning_rate, learning_episodes, map_size, \n",
    "                 cw_num = 4, ew_num = 4, test_interval = 100, batch_size = 100,\n",
    "                 action_space = 4, beta = 0.999, do_test = True):\n",
    "        \n",
    "        self.server = QLAgent_server.remote(epsilon, learning_rate, learning_episodes, map_size, \n",
    "                                               test_interval = test_interval, batch_size = batch_size, do_test = do_test)\n",
    "        self.workers_id = []\n",
    "        self.epsilon = epsilon\n",
    "        self.batch_size = batch_size\n",
    "        self.cw_num = cw_num\n",
    "        self.ew_num = ew_num\n",
    "        self.agent_name = \"Distributed Q-learning\"\n",
    "        self.do_test = do_test\n",
    "        \n",
    "    def learn_and_evaluate(self):\n",
    "        workers_id = []\n",
    "        \n",
    "        #INSERT YOUR CODE HERE\n",
    "\n",
    "        ray.wait(workers_id, len(workers_id))\n",
    "        return ray.get(self.server.get_reuslts.remote())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simulator.reset()\n",
    "#INSERT YOUR CODE FOR INIT PARAMS HERE\n",
    "\n",
    "start_time = time.time()\n",
    "distributed_ql_agent = distributed_QL_agent(epsilon, learning_rate, learning_episodes, map_size, \n",
    "                                            test_interval = test_interval, batch_size = batch_size,\n",
    "                                            cw_num = 8, ew_num = 4, do_test = do_test)\n",
    "total_rewards, q_table = distributed_ql_agent.learn_and_evaluate()\n",
    "run_time['Distributed Q-learning agent'] = time.time() - start_time\n",
    "print(\"Learning time:\\n\")\n",
    "print(run_time['Distributed Q-learning agent'])\n",
    "if do_test:\n",
    "    plot_result(total_rewards, test_interval, [distributed_ql_agent.agent_name])\n",
    "plot_image(q_table, MAP[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparison of different approachs\n",
    "\n",
    "Run the following cell to compare the running time of different approaches. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "temp_dict = deepcopy(run_time)\n",
    "print(\"All:\")\n",
    "for _ in range(len(temp_dict)):\n",
    "    min_v = float('inf')\n",
    "    for k, v in temp_dict.items():\n",
    "        if v is None:\n",
    "            continue\n",
    "        if v < min_v:\n",
    "            min_v = v\n",
    "            name = k\n",
    "    temp_dict[name] = float('inf')\n",
    "    print(name + \": \" + str(min_v))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Include in your report the following: \n",
    "\n",
    "7. Show the value functions learned by the distributed methods for the best policies learned with $\\epsilon$ equal to 0.3 and compare to those of the single-core method. Run the algorithm for the recommended number of episodes for each of the maps. Did the approaches produce similar results? \n",
    "\n",
    "8. Provide and compare the timing results for the single-core and distributed experiments, including the time to do the evaluations during learning. Describe the trends you observe as the number of workers increases. \n",
    "\n",
    "9. Provide and compare the timing results for the single-core and distributed experiments with the evaluation procedure turned off. That is, here you only want to provide timing results for the learning process without any interleaved evaluation. Compare the results with (8). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 9, 11],\n",
       "       [ 4, 10]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat = np.random.randint(14,size=(2,2))\n",
    "mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat[0].argmax()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 0])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simulator.reset()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(17, -1, False, {'prob': 0.97})"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simulator.step(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (Down)\n",
      "SFFFFFFF\n",
      "FFFFFFFF\n",
      "H\u001b[41mF\u001b[0mHHHFFF\n",
      "HFHHHFFF\n",
      "HFHHHFFF\n",
      "HFHHHFFF\n",
      "HFFFFFFF\n",
      "FGFFFFFF\n"
     ]
    }
   ],
   "source": [
    "simulator.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.randint(4,size=4)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (Intel, 2019 update 2)",
   "language": "python",
   "name": "c009-intel_distribution_of_python_3_2019u2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}