Chapter04/MDP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 3\n",
    "m2 = m ** 2\n",
    "q = np.zeros(m2)\n",
    "q[m2 // 2] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_P(m, p_up, p_down, p_left, p_right):\n",
    "    m2 = m ** 2\n",
    "    P = np.zeros((m2, m2))\n",
    "    ix_map = {i + 1: (i // m, i % m) for i in range(m2)}\n",
    "    for i in range(m2):\n",
    "        for j in range(m2):\n",
    "            r1, c1 = ix_map[i + 1]\n",
    "            r2, c2 = ix_map[j + 1]\n",
    "            rdiff = r1 - r2\n",
    "            cdiff = c1 - c2\n",
    "            if rdiff == 0:\n",
    "                if cdiff == 1:\n",
    "                    P[i, j] = p_left\n",
    "                elif cdiff == -1:\n",
    "                    P[i, j] = p_right\n",
    "                elif cdiff == 0:\n",
    "                    if r1 == 0:\n",
    "                        P[i, j] += p_down\n",
    "                    elif r1 == m - 1:\n",
    "                        P[i, j] += p_up\n",
    "                    if c1 == 0:\n",
    "                        P[i, j] += p_left\n",
    "                    elif c1 == m - 1:\n",
    "                        P[i, j] += p_right\n",
    "            elif rdiff == 1:\n",
    "                if cdiff == 0:\n",
    "                    P[i, j] = p_down\n",
    "            elif rdiff == -1:\n",
    "                if cdiff == 0:\n",
    "                    P[i, j] = p_up\n",
    "    return P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P = get_P(3, 0.2, 0.3, 0.25, 0.25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.matmul(q, P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 1\n",
    "Pn = np.linalg.matrix_power(P, n)\n",
    "np.matmul(q, Pn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 3\n",
    "Pn = np.linalg.matrix_power(P, n)\n",
    "np.round(np.matmul(q, Pn), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10\n",
    "Pn = np.linalg.matrix_power(P, n)\n",
    "np.round(np.matmul(q, Pn), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 100\n",
    "Pn = np.linalg.matrix_power(P, n)\n",
    "np.round(np.matmul(q, Pn), 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### Ergodic MC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from scipy.stats import itemfreq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 4\n",
    "n = 10 ** 6\n",
    "visited = [s]\n",
    "for t in range(n):\n",
    "    s = np.random.choice(m2, p=P[s, :])\n",
    "    visited.append(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "itemfreq(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# MRP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modify P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "P = np.zeros((m2 + 1, m2 + 1))\n",
    "P[:m2, :m2] = get_P(3, 0.2, 0.3, 0.25, 0.25)\n",
    "for i in range(m2):\n",
    "    P[i, m2] = P[i, i]\n",
    "    P[i, i] = 0\n",
    "P[m2, m2] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10 ** 5\n",
    "avg_rewards = np.zeros(m2)\n",
    "for s in range(9):\n",
    "    for i in range(n):\n",
    "        crashed = False\n",
    "        s_next = s\n",
    "        episode_reward = 0\n",
    "        while not crashed:\n",
    "            s_next = np.random.choice(m2 + 1, p=P[s_next, :])\n",
    "            if s_next < m2:\n",
    "                episode_reward += 1\n",
    "            else:\n",
    "                crashed = True\n",
    "        avg_rewards[s] += episode_reward\n",
    "avg_rewards /= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.round(avg_rewards, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(1 + 2.45) * 0.25 + (1 + 2.44) * 0.25 + 0.2 * (1+2.81) + 0.3*(1+2.12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### Analytically calculate the state values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "R = np.ones(m2 + 1)\n",
    "R[-1] = 0\n",
    "inv = np.linalg.inv(np.eye(m2 + 1) - 0.9999 * P)\n",
    "v = np.matmul(inv, np.matmul(P, R))\n",
    "print(np.round(v, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### Estimating State Values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def estimate_state_values(P, m2, threshold):\n",
    "    v = np.zeros(m2 + 1)\n",
    "    max_change = threshold\n",
    "    terminal_state = m2 \n",
    "    while max_change >= threshold:\n",
    "        max_change = 0\n",
    "        for s in range(m2 + 1):\n",
    "            v_new = 0\n",
    "            for s_next in range(m2 + 1):\n",
    "                r = 1 * (s_next != terminal_state)\n",
    "                v_new += P[s, s_next] * (r + v[s_next])\n",
    "            max_change = max(max_change, np.abs(v[s] - v_new))\n",
    "            v[s] = v_new\n",
    "    return np.round(v, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "estimate_state_values(P, m2, 0.005)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (py37rl)",
   "language": "python",
   "name": "py37rl"
  },
  "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}