ddp_performance-2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "import numpy as np\n",
    "from quantecon.markov import random_discrete_dp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Performance Comparison"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Regarding the representation of the transition probability array `Q`:\n",
    "0. current states $\\times$ actions $\\times$ next states\n",
    "0. current state-action pairs $\\times$ next states (dense matrix)\n",
    "0. current state-action pairs $\\times$ next states (sparse matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def compare_performance(num_states, num_actions, beta, k,\n",
    "                        suppress_vi=False, random_state=0):\n",
    "    labels = ['n x m x n', 'n*m x n (dense)', 'n*m x n (sparse)']\n",
    "    flags = [(False, False), (False, True), (True, True)]  # (sparse, sa_pair)\n",
    "    ddps = {}\n",
    "    for label, flag in zip(labels, flags):\n",
    "        ddps[label] = \\\n",
    "            random_discrete_dp(num_states, num_actions, beta, k=k,\n",
    "                               sparse=flag[0], sa_pair=flag[1],\n",
    "                               random_state=random_state)\n",
    "\n",
    "    if suppress_vi:\n",
    "        methods = ['pi', 'mpi']\n",
    "    else:\n",
    "        methods = ['vi', 'pi', 'mpi']\n",
    "    results = {}\n",
    "    max_iter = 1000\n",
    "    for ddp in ddps.values():\n",
    "        ddp.max_iter = max_iter\n",
    "    k_mpi = 20\n",
    "\n",
    "    for label in labels:\n",
    "        results[label] = {method: ddps[label].solve(method=method, k=k_mpi)\n",
    "                          for method in methods}\n",
    "\n",
    "    print('(num_states, num_actions) = ({0}, {1})'\n",
    "          .format(num_states, num_actions))\n",
    "    print('Number of possible next states for each (s, a) =', k)\n",
    "    print('beta =', beta)\n",
    "    print('=====')\n",
    "    print('Whether the results by pi agree:',\n",
    "          all([np.array_equal(results[labels[i]]['pi'].sigma,\n",
    "                              results[labels[2]]['pi'].sigma)\n",
    "               for i in [0, 1]]))\n",
    "    print('Whether the answer is correct ({0}, {1}, {2}):'.format(*labels))\n",
    "    for method in methods:\n",
    "        if method != 'pi':\n",
    "            print(method.ljust(3) + ':',\n",
    "                  [np.array_equal(results[label][method].sigma,\n",
    "                                  results[label]['pi'].sigma)\n",
    "                   for label in labels])\n",
    "    print('Number of iterations ({0}, {1}, {2}):'.format(*labels))\n",
    "    for method in methods:\n",
    "        print(method.ljust(3) + ':',\n",
    "              [results[label][method].num_iter for label in labels])\n",
    "    print('=====')\n",
    "\n",
    "    print('Speed comparison ({0}, {1}, {2}):'.format(*labels))\n",
    "    for method in methods:\n",
    "        print('***', method, '***')\n",
    "        for label in labels:\n",
    "            global ddps, label, method\n",
    "            %timeit ddps[label].solve(method=method)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "seed = 1234  # Set random seed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (100, 20)\n",
      "Number of possible next states for each (s, a) = 3\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [219, 219, 219]\n",
      "pi : [4, 4, 4]\n",
      "mpi: [6, 6, 6]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "10 loops, best of 3: 30.5 ms per loop\n",
      "100 loops, best of 3: 10 ms per loop\n",
      "100 loops, best of 3: 9.41 ms per loop\n",
      "*** pi ***\n",
      "1000 loops, best of 3: 1.6 ms per loop\n",
      "1000 loops, best of 3: 1.07 ms per loop\n",
      "100 loops, best of 3: 3.91 ms per loop\n",
      "*** mpi ***\n",
      "100 loops, best of 3: 2.06 ms per loop\n",
      "1000 loops, best of 3: 1.61 ms per loop\n",
      "100 loops, best of 3: 3.71 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=100, num_actions=20, beta=0.95, k=3,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (500, 20)\n",
      "Number of possible next states for each (s, a) = 3\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [220, 220, 220]\n",
      "pi : [5, 5, 5]\n",
      "mpi: [7, 7, 7]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 625 ms per loop\n",
      "1 loop, best of 3: 239 ms per loop\n",
      "10 loops, best of 3: 21.2 ms per loop\n",
      "*** pi ***\n",
      "10 loops, best of 3: 33.1 ms per loop\n",
      "10 loops, best of 3: 20.5 ms per loop\n",
      "10 loops, best of 3: 25.3 ms per loop\n",
      "*** mpi ***\n",
      "10 loops, best of 3: 28 ms per loop\n",
      "100 loops, best of 3: 14.2 ms per loop\n",
      "100 loops, best of 3: 5.59 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=500, num_actions=20, beta=0.95, k=3,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (1000, 20)\n",
      "Number of possible next states for each (s, a) = 3\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [219, 219, 219]\n",
      "pi : [5, 5, 5]\n",
      "mpi: [7, 7, 7]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 2.36 s per loop\n",
      "1 loop, best of 3: 866 ms per loop\n",
      "10 loops, best of 3: 37 ms per loop\n",
      "*** pi ***\n",
      "10 loops, best of 3: 167 ms per loop\n",
      "10 loops, best of 3: 123 ms per loop\n",
      "10 loops, best of 3: 129 ms per loop\n",
      "*** mpi ***\n",
      "10 loops, best of 3: 100 ms per loop\n",
      "10 loops, best of 3: 46.9 ms per loop\n",
      "100 loops, best of 3: 6.67 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=1000, num_actions=20, beta=0.95, k=3,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (1000, 50)\n",
      "Number of possible next states for each (s, a) = 3\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [223, 223, 223]\n",
      "pi : [5, 5, 5]\n",
      "mpi: [6, 6, 6]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 5.93 s per loop\n",
      "1 loop, best of 3: 2.12 s per loop\n",
      "10 loops, best of 3: 72.4 ms per loop\n",
      "*** pi ***\n",
      "1 loop, best of 3: 266 ms per loop\n",
      "10 loops, best of 3: 155 ms per loop\n",
      "10 loops, best of 3: 131 ms per loop\n",
      "*** mpi ***\n",
      "10 loops, best of 3: 186 ms per loop\n",
      "10 loops, best of 3: 74.1 ms per loop\n",
      "100 loops, best of 3: 6.96 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=1000, num_actions=50, beta=0.95, k=3,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (500, 20)\n",
      "Number of possible next states for each (s, a) = 100\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [218, 218, 218]\n",
      "pi : [3, 3, 3]\n",
      "mpi: [4, 4, 4]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 619 ms per loop\n",
      "1 loop, best of 3: 237 ms per loop\n",
      "1 loop, best of 3: 199 ms per loop\n",
      "*** pi ***\n",
      "10 loops, best of 3: 21.5 ms per loop\n",
      "100 loops, best of 3: 13.6 ms per loop\n",
      "10 loops, best of 3: 64.4 ms per loop\n",
      "*** mpi ***\n",
      "100 loops, best of 3: 15.9 ms per loop\n",
      "100 loops, best of 3: 8.07 ms per loop\n",
      "100 loops, best of 3: 9.92 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=500, num_actions=20, beta=0.95, k=100,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (500, 20)\n",
      "Number of possible next states for each (s, a) = 50\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [218, 218, 218]\n",
      "pi : [2, 2, 2]\n",
      "mpi: [4, 4, 4]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 622 ms per loop\n",
      "1 loop, best of 3: 240 ms per loop\n",
      "10 loops, best of 3: 103 ms per loop\n",
      "*** pi ***\n",
      "100 loops, best of 3: 15.7 ms per loop\n",
      "100 loops, best of 3: 9.67 ms per loop\n",
      "10 loops, best of 3: 42 ms per loop\n",
      "*** mpi ***\n",
      "100 loops, best of 3: 15.9 ms per loop\n",
      "100 loops, best of 3: 8.08 ms per loop\n",
      "100 loops, best of 3: 6.45 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=500, num_actions=20, beta=0.95, k=50,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (500, 20)\n",
      "Number of possible next states for each (s, a) = 500\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [218, 218, 218]\n",
      "pi : [1, 1, 1]\n",
      "mpi: [3, 3, 3]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 625 ms per loop\n",
      "1 loop, best of 3: 235 ms per loop\n",
      "1 loop, best of 3: 1.01 s per loop\n",
      "*** pi ***\n",
      "100 loops, best of 3: 9.67 ms per loop\n",
      "100 loops, best of 3: 5.66 ms per loop\n",
      "10 loops, best of 3: 52.3 ms per loop\n",
      "*** mpi ***\n",
      "100 loops, best of 3: 11.9 ms per loop\n",
      "100 loops, best of 3: 6.02 ms per loop\n",
      "10 loops, best of 3: 27.7 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=500, num_actions=20, beta=0.95, k=500,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (1000, 100)\n",
      "Number of possible next states for each (s, a) = 1\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [True, True, True]\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "vi : [230, 230, 230]\n",
      "pi : [11, 11, 11]\n",
      "mpi: [15, 15, 15]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** vi ***\n",
      "1 loop, best of 3: 12.2 s per loop\n",
      "1 loop, best of 3: 4.33 s per loop\n",
      "10 loops, best of 3: 105 ms per loop\n",
      "*** pi ***\n",
      "1 loop, best of 3: 879 ms per loop\n",
      "1 loop, best of 3: 437 ms per loop\n",
      "100 loops, best of 3: 18 ms per loop\n",
      "*** mpi ***\n",
      "1 loop, best of 3: 876 ms per loop\n",
      "1 loop, best of 3: 326 ms per loop\n",
      "10 loops, best of 3: 19.4 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=1000, num_actions=100, beta=0.95, k=1,\n",
    "                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(num_states, num_actions) = (1000, 200)\n",
      "Number of possible next states for each (s, a) = 1\n",
      "beta = 0.95\n",
      "=====\n",
      "Whether the results by pi agree: True\n",
      "Whether the answer is correct (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "mpi: [True, True, True]\n",
      "Number of iterations (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "pi : [8, 8, 8]\n",
      "mpi: [16, 16, 16]\n",
      "=====\n",
      "Speed comparison (n x m x n, n*m x n (dense), n*m x n (sparse)):\n",
      "*** pi ***\n",
      "1 loop, best of 3: 1.15 s per loop\n",
      "1 loop, best of 3: 492 ms per loop\n",
      "10 loops, best of 3: 18.9 ms per loop\n",
      "*** mpi ***\n",
      "1 loop, best of 3: 1.82 s per loop\n",
      "1 loop, best of 3: 643 ms per loop\n",
      "10 loops, best of 3: 29.4 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compare_performance(num_states=1000, num_actions=200, beta=0.95, k=1,\n",
    "                    suppress_vi=True, random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Darwin-15.6.0-x86_64-i386-64bit\n"
     ]
    }
   ],
   "source": [
    "import platform\n",
    "print(platform.platform())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.5.2 |Anaconda 4.1.1 (x86_64)| (default, Jul  2 2016, 17:52:12) \n",
      "[GCC 4.2.1 Compatible Apple LLVM 4.2 (clang-425.0.28)]\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "print(sys.version)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.11.1\n"
     ]
    }
   ],
   "source": [
    "print(np.__version__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.17.1\n"
     ]
    }
   ],
   "source": [
    "import scipy\n",
    "print(scipy.__version__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.26.0\n"
     ]
    }
   ],
   "source": [
    "import numba\n",
    "print(numba.__version__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}