jack_car_problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#############################################################################################\n",
    "# Copyright (C)\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t#\n",
    "# 2019 Aditya Rastogi(r.aditya0824@gmail.com)\t\t\t\t\t\t\t\t\t\t\t\t#\n",
    "# Permission given to modify the code as long as you keep this declaration at the top \t\t#\n",
    "#############################################################################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IMPORTS\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from scipy.stats import poisson\n",
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Problem Parameters\n",
    "class jcp:\n",
    "    @staticmethod\n",
    "    def max_cars():\n",
    "        return 20\n",
    "    \n",
    "    @staticmethod\n",
    "    def γ():\n",
    "        return 0.9\n",
    "    \n",
    "    @staticmethod\n",
    "    def credit_reward():\n",
    "        return 10\n",
    "    \n",
    "    @staticmethod\n",
    "    def moving_reward():\n",
    "        return -2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class poisson_:\n",
    "    \n",
    "    def __init__(self, λ):\n",
    "        self.λ = λ\n",
    "        \n",
    "        ε = 0.01\n",
    "        \n",
    "        # [α , β] is the range of n's for which the pmf value is above ε\n",
    "        self.α = 0\n",
    "        state = 1\n",
    "        self.vals = {}\n",
    "        summer = 0\n",
    "        \n",
    "        while(1):\n",
    "            if state == 1:\n",
    "                temp = poisson.pmf(self.α, self.λ) \n",
    "                if(temp <= ε):\n",
    "                    self.α+=1\n",
    "                else:\n",
    "                    self.vals[self.α] = temp\n",
    "                    summer += temp\n",
    "                    self.β = self.α+1\n",
    "                    state = 2\n",
    "            elif state == 2:\n",
    "                temp = poisson.pmf(self.β, self.λ)\n",
    "                if(temp > ε):\n",
    "                    self.vals[self.β] = temp\n",
    "                    summer += temp\n",
    "                    self.β+=1\n",
    "                else:\n",
    "                    break    \n",
    "        \n",
    "        # normalizing the pmf, values of n outside of [α, β] have pmf = 0\n",
    "        \n",
    "        added_val = (1-summer)/(self.β-self.α)\n",
    "        for key in self.vals:\n",
    "            self.vals[key] += added_val\n",
    "        \n",
    "            \n",
    "    def f(self, n):\n",
    "        try:\n",
    "            Ret_value = self.vals[n]\n",
    "        except(KeyError):\n",
    "            Ret_value = 0\n",
    "        finally:\n",
    "            return Ret_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#A class holding the properties of a location together\n",
    "\n",
    "class location:\n",
    "    \n",
    "    def __init__(self, req, ret):\n",
    "        self.α = req                             #value of lambda for requests\n",
    "        self.β = ret                             #value of lambda for returns\n",
    "        self.poissonα = poisson_(self.α)\n",
    "        self.poissonβ = poisson_(self.β)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Location initialisation\n",
    "\n",
    "A = location(3,3)\n",
    "B = location(4,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Initializing the value and policy matrices. Initial policy has zero value for all states.\n",
    "\n",
    "value = np.zeros((jcp.max_cars()+1, jcp.max_cars()+1))\n",
    "policy = value.copy().astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def apply_action(state, action):\n",
    "    return [max(min(state[0] - action, jcp.max_cars()),0) , max(min(state[1] + action, jcp.max_cars()),0)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expected_reward(state, action):\n",
    "    global value\n",
    "    \"\"\"\n",
    "    state  : It's a pair of integers, # of cars at A and at B\n",
    "    action : # of cars transferred from A to B,  -5 <= action <= 5 \n",
    "    \"\"\"\n",
    "    \n",
    "    \n",
    "    ψ = 0 #reward\n",
    "    new_state = apply_action(state, action)\n",
    "    \n",
    "    # adding reward for moving cars from one location to another (which is negative) \n",
    "    \n",
    "    ψ = ψ + jcp.moving_reward() * abs(action)\n",
    "    \n",
    "    \n",
    "    #there are four discrete random variables which determine the probability distribution of the reward and next state\n",
    "    \n",
    "    for Aα in range(A.poissonα.α, A.poissonα.β):\n",
    "        for Bα in range(B.poissonα.α, B.poissonα.β):\n",
    "            for Aβ in range(A.poissonβ.α, A.poissonβ.β):\n",
    "                for Bβ in range(B.poissonβ.α, B.poissonβ.β):\n",
    "                    \"\"\"\n",
    "                    Aα : sample of cars requested at location A\n",
    "                    Aβ : sample of cars returned at location A\n",
    "                    Bα : sample of cars requested at location B\n",
    "                    Bβ : sample of cars returned at location B\n",
    "                    ζ  : probability of this event happening\n",
    "                    \"\"\"\n",
    "\n",
    "                    # all four variables are independent of each other\n",
    "                    ζ = A.poissonα.vals[Aα] * B.poissonα.vals[Bα] * A.poissonβ.vals[Aβ] * B.poissonβ.vals[Bβ]\n",
    "                    \n",
    "                    valid_requests_A = min(new_state[0], Aα)\n",
    "                    valid_requests_B = min(new_state[1], Bα)\n",
    "                    \n",
    "                    rew = (valid_requests_A + valid_requests_B)*(jcp.credit_reward())\n",
    "                    \n",
    "                    #calculating the new state based on the values of the four random variables\n",
    "                    new_s = [0,0]\n",
    "                    new_s[0] = max(min(new_state[0] - valid_requests_A + Aβ, jcp.max_cars()),0)\n",
    "                    new_s[1] = max(min(new_state[1] - valid_requests_B + Bβ, jcp.max_cars()),0)\n",
    "                    \n",
    "                    #Bellman's equation\n",
    "                    ψ += ζ * (rew + jcp.γ() * value[new_s[0]][new_s[1]])\n",
    "                    \n",
    "    return ψ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy_evaluation():\n",
    "    \n",
    "    global value\n",
    "    \n",
    "    # here policy_evaluation has a static variable ε whose values decreases over time\n",
    "    ε = policy_evaluation.ε\n",
    "    \n",
    "    policy_evaluation.ε /= 10 \n",
    "    \n",
    "    while(1):\n",
    "        δ = 0\n",
    "        \n",
    "        for i in range(value.shape[0]):\n",
    "            for j in range(value.shape[1]):\n",
    "                # value[i][j] denotes the value of the state [i,j]\n",
    "                \n",
    "                old_val = value[i][j]\n",
    "                value[i][j] = expected_reward([i,j], policy[i][j])\n",
    "                \n",
    "                δ = max(δ, abs(value[i][j] - old_val))\n",
    "                print('.', end = '')\n",
    "                sys.stdout.flush()\n",
    "        print(δ)\n",
    "        sys.stdout.flush()\n",
    "    \n",
    "        if δ < ε:\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "#initial value of ε\n",
    "policy_evaluation.ε = 50"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy_improvement():\n",
    "    \n",
    "    global policy\n",
    "    \n",
    "    policy_stable = True\n",
    "    for i in range(value.shape[0]):\n",
    "        for j in range(value.shape[1]):\n",
    "            old_action = policy[i][j]\n",
    "            \n",
    "            max_act_val = None\n",
    "            max_act = None\n",
    "            \n",
    "            τ12 = min(i,5)       # if I have say 3 cars at the first location, then I can atmost move 3 from 1 to 2\n",
    "            τ21 = -min(j,5)      # if I have say 2 cars at the second location, then I can atmost move 2 from 2 to 1\n",
    "            \n",
    "            for act in range(τ21,τ12+1):\n",
    "                σ = expected_reward([i,j], act)\n",
    "                if max_act_val == None:\n",
    "                    max_act_val = σ\n",
    "                    max_act = act\n",
    "                elif max_act_val < σ:\n",
    "                    max_act_val = σ\n",
    "                    max_act = act\n",
    "                \n",
    "            policy[i][j] = max_act\n",
    "            \n",
    "            if old_action!= policy[i][j]:\n",
    "                policy_stable = False\n",
    "    \n",
    "    return policy_stable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def save_policy():\n",
    "    save_policy.counter += 1\n",
    "    ax = sns.heatmap(policy, linewidth=0.5)\n",
    "    ax.invert_yaxis()\n",
    "    plt.savefig('policy'+str(save_policy.counter)+'.svg')\n",
    "    plt.close()\n",
    "    \n",
    "def save_value():\n",
    "    save_value.counter += 1\n",
    "    ax = sns.heatmap(value, linewidth=0.5)\n",
    "    ax.invert_yaxis()\n",
    "    plt.savefig('value'+ str(save_value.counter)+'.svg')\n",
    "    plt.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "save_policy.counter = 0\n",
    "save_value.counter = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................190.7422667431856\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................132.3288138607936\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................89.66201097313652\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................67.09773710887819\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................53.22356224698336\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................41.38141600199123\n",
      "5\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................108.30002833852905\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................28.974428595453105\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................23.301431489076776\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................20.452321093917305\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................17.305046535861663\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................14.35883699154698\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................11.830718566822725\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................9.727345084821081\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................7.992788393132344\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................6.565837073517741\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................5.39290507462033\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................4.429149938857279\n",
      "0.5\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................5.27798779239663\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................3.4563343004468834\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................2.5400992522864954\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................2.0670104857206297\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................1.7127413369539113\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................1.4164878188423131\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................1.168489933004082\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.9618834855778573\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.7906651923405548\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.6493223316146555\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.5329349582031568\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.43724800909018313\n",
      "0.05\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.7818828680955221\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.3787490167374017\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.2764653228040288\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.23946757047491474\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.2010214703025781\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.1662931285351874\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.1368437068649655\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.1124063070358261\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.09226489483307887\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.07570329361703898\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.06209984291916726\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.05093306754395144\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.041770115662586704\n",
      "0.005\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.04458665883657886\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.028088069227294454\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.023031838464646626\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.018885455994336553\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.015485388445540593\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.012697469661475225\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.01041157577441254\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.008537290004767328\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.007000437207864252\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.005740224176975062\n",
      ".........................................................................................................................................................................................................................................................................................................................................................................................................................................................0.004706838868685281\n"
     ]
    }
   ],
   "source": [
    "while(1):\n",
    "    policy_evaluation()\n",
    "    ρ = policy_improvement()\n",
    "    save_value()\n",
    "    save_policy()\n",
    "    if ρ == True:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "ex = poisson_(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.α"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.β"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 0.05127513134990861,\n",
       " 1: 0.15084926808563653,\n",
       " 2: 0.2255298706374324,\n",
       " 3: 0.2255298706374324,\n",
       " 4: 0.1695194187235855,\n",
       " 5: 0.10230687642696924,\n",
       " 6: 0.051897469704506906,\n",
       " 7: 0.023092094434528487}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.λ"
   ]
  },
  {
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}