Ex4.1A Policy Evaluation 2 Arrays.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DAT257x: Reinforcement Learning Explained\n",
    "\n",
    "## Lab 4: Dynamic Programming\n",
    "\n",
    "### Exercise 4.1A Policy Evaluation with 2 Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Policy Evaluation calculates the value function for a policy, given the policy and the full definition of the associated Markov Decision Process.  The full definition of an MDP is the set of states, the set of available actions for each state, the set of rewards, the discount factor, and the state/reward transition function.\n",
    "\n",
    "Implement the algorithm for Iterative Policy Evaluation using the 2 array approach in the below code cell.  In the 2 array approach, one array holds the value estimates for each state computed on the previous iteration, and one array holds the value estimates for the states computing in the current iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Testing: Policy Evaluation (two-arrays)\n",
      "passed test: return value is list\n",
      "passed test: length of list = 15\n",
      "passed test: values of list elements\n",
      "PASSED: Policy Evaluation (two-arrays) passcode = 9986-145\n"
     ]
    }
   ],
   "source": [
    "import tester       # required for testing and grading your code\n",
    "import numpy as np\n",
    "\n",
    "def policy_eval_two_arrays(state_count, gamma, theta, get_policy_actions, get_transitions):\n",
    "    \"\"\"\n",
    "    This function uses the two-array approach to evaluate the specified policy for the specified MDP:\n",
    "    'state_count' is the total number of states in the MDP. States are represented as 0-relative numbers.\n",
    "    'gamma' is the MDP discount factor for rewards.\n",
    "    'theta' is the small number threshold to signal convergence of the value function (see Iterative Policy Evaluation algorithm).\n",
    "    'get_policy_actions' is the stochastic policy function - it takes a state parameter and returns list of tuples, \n",
    "        where each tuple is of the form: (action, probability).  It represents the policy being evaluated.\n",
    "    'get_transitions' is the state/reward transiton function.  It accepts two parameters, state and action, and returns\n",
    "        a list of tuples, where each tuple is of the form: (next_state, reward, probabiliity).  \n",
    "    \"\"\"\n",
    "    V = state_count*[0]\n",
    "    \n",
    "    while True:\n",
    "        delta = 0\n",
    "        V_prev = V\n",
    "        V = state_count*[0]\n",
    "        for s in range(state_count):\n",
    "            actions = get_policy_actions(s)\n",
    "            for a in actions:\n",
    "                trans_tuple = get_transitions(s, a[0])\n",
    "                V[s] += (a[1] * sum(tran[2] * (tran[1] + gamma * V_prev[tran[0]]) for tran in trans_tuple))\n",
    "        delta = np.amax(np.absolute(np.subtract(V_prev, V)))\n",
    "        if delta < theta:\n",
    "            break\n",
    "        \n",
    "    # insert code here to evaluate the policy using the 2 array approach \n",
    "    return V\n",
    "\n",
    "tester.policy_eval_two_arrays_test(policy_eval_two_arrays)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}