state-value estimation for 3-queue system in a 2 × 2 switch.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialize threshold/capacity c\n",
    "\n",
    "c = 4 # in all queues, we make sure that there are no more than c customers at the end of each time interval [t - 1, t]\n",
    "\n",
    "def elementWiseMin(a1, a2):\n",
    "    output = np.array([0, 0, 0])\n",
    "    for i in range(3):\n",
    "        output[i] = min(a1[i], a2[i])\n",
    "    return output\n",
    "\n",
    "# initialize average arrival rates\n",
    "\n",
    "a1_avg = 0.3 # average arrival rate for queue 1 (input 1 to output 2)\n",
    "a2_avg = 0.3 # average arrival rate for queue 2 (input 2 to output 1)\n",
    "a3_avg = 0.69 # average arrival rate for queue 3 (input 2 to output 2)\n",
    "\n",
    "def anArrivalVector(a1_avg, a2_avg, a3_avg):\n",
    "    return np.array([np.random.poisson(a1_avg), np.random.poisson(a2_avg), np.random.poisson(a3_avg)])\n",
    "\n",
    "def elementWiseMax(a1, a2):\n",
    "    output = np.array([0, 0, 0])\n",
    "    for i in range(3):\n",
    "        output[i] = max(a1[i], a2[i])\n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Estimate the values $v$ of the states $\\vec{q}$ under policy 1 (maxWeight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# estimate the values v of the states q under policy 1 (maxWeight)\n",
    "\n",
    "def chooseMaxWeightServiceConfiguration(s, q):\n",
    "    if q[0] + q[1] >= q[2]:\n",
    "        s[0] = s[1] = 1\n",
    "        return\n",
    "    s[2] = 1\n",
    "\n",
    "# initialize current states q, past average reward m, and value estimates v at time t = 0\n",
    "\n",
    "q = np.array([0, 0, 0])\n",
    "m = 0\n",
    "v = np.zeros((c + 1, c + 1, c + 1))\n",
    "\n",
    "# update v 10,000,000 times (with the first one being trivial)\n",
    "\n",
    "for t in range(1, 10000001):\n",
    "    # right now we've got q(t - 1)\n",
    "    s = np.array([0, 0, 0])\n",
    "    chooseMaxWeightServiceConfiguration(s, q) # compute service configuration s(t - 1) for the interval [t - 1, t]\n",
    "    a = anArrivalVector(a1_avg, a2_avg, a3_avg) # generate arrival configuration a(t - 1) for the interval [t - 1, t]\n",
    "    r = sum(q) # compute current reward r(t - 1)\n",
    "    m_t_minus_1 = m # store m(t - 1)\n",
    "    m = (1 - 1 / t) * m + (1 / t) * r # compute past average reward m(t) based on t, m(t - 1), and current reward r(t - 1)\n",
    "    q_t_minus_1 = q # store q(t - 1)    \n",
    "    q = elementWiseMin(elementWiseMax(q + a - s, np.array([0, 0, 0])), np.array([c, c, c])) # compute current state q(t)\n",
    "    \n",
    "    # update value estimate v(q(t - 1)) based on v(q(t - 1)), t, r(t - 1), m(t - 1), and v(q(t))\n",
    "    v[q_t_minus_1[0], q_t_minus_1[1], q_t_minus_1[2]] += (1 / t) * (r - m_t_minus_1 + v[q[0], q[1], q[2]] - v[q_t_minus_1[0], q_t_minus_1[1], q_t_minus_1[2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For maxWeight, the state-value estimates are summarized in\n",
      "v =\n",
      " [[[-2.47056969e+00 -2.21383351e+00 -1.30474699e+00 -3.00307022e-01\n",
      "    1.32831055e-01]\n",
      "  [-2.74487439e-01 -7.62950897e-01 -3.69093025e-01  2.24174280e-01\n",
      "    3.58285945e-01]\n",
      "  [-3.38080518e-02 -8.22869090e-02  1.08597718e-01  3.71459687e-01\n",
      "    7.30122235e-01]\n",
      "  [-1.63329156e-03 -6.80675407e-04  7.22980856e-02  3.76243346e-01\n",
      "    8.90208689e-01]\n",
      "  [-1.05746876e-05  1.32745190e-03  2.37450251e-02  1.36673948e-01\n",
      "    2.62177520e-01]]\n",
      "\n",
      " [[-3.18756939e-01 -8.34359154e-01 -4.44401582e-01  1.78536030e-01\n",
      "    3.20353824e-01]\n",
      "  [-6.18776476e-02 -1.12418528e-01 -4.44593563e-02  3.72613112e-01\n",
      "    7.16645362e-01]\n",
      "  [ 3.52925013e-01 -5.46390022e-04  1.71798447e-01  6.78144167e-01\n",
      "    8.64555567e-01]\n",
      "  [-1.31897472e-06  2.64371449e-03  4.42926195e-02  1.91425745e-01\n",
      "    6.84820420e-01]\n",
      "  [ 1.05715312e-05  6.82660595e-03  5.22889978e-03  6.56535860e-02\n",
      "    9.02007279e-02]]\n",
      "\n",
      " [[-3.92732034e-02 -9.28227581e-02  2.74776757e-02  3.80198800e-01\n",
      "    6.01066045e-01]\n",
      "  [-3.74653279e-03 -6.01495303e-03  1.35563510e-01  3.92869874e-01\n",
      "    6.47925400e-01]\n",
      "  [-5.65344733e-06  5.81835111e-03  4.25009450e-02  2.50297732e-01\n",
      "    3.34690688e-01]\n",
      "  [ 3.78926891e-05  7.14464644e-04  3.00865097e-02  8.20641796e-02\n",
      "    1.35122309e-01]\n",
      "  [ 3.26873649e-06  1.07575183e-04  2.02301555e-02  1.04715258e-02\n",
      "    1.97388652e-02]]\n",
      "\n",
      " [[-1.88051519e-03 -9.22750699e-04  1.00267909e-01  3.89872331e-01\n",
      "    5.89265090e-01]\n",
      "  [-4.58219588e-05  2.04861220e-03  3.88693711e-02  2.38480231e-01\n",
      "    2.63990655e-01]\n",
      "  [ 1.55948470e-05  8.05318061e-04  1.12930467e-02  6.40083705e-02\n",
      "    8.37380341e-02]\n",
      "  [ 1.33450854e-06  1.07774348e-04  3.05971390e-03  1.17170582e-02\n",
      "    3.56753395e-02]\n",
      "  [ 4.31642171e-06  2.38509565e-06  8.91427858e-05  2.31321748e-03\n",
      "    3.90295777e-03]]\n",
      "\n",
      " [[-1.43235983e-05  1.23554891e-03  2.17408205e-02  1.16840790e-01\n",
      "    2.05983321e-01]\n",
      "  [ 1.58261025e-05  1.20724011e-03  5.50665994e-03  4.92719963e-02\n",
      "    7.06293675e-02]\n",
      "  [ 3.82459139e-07  1.13590662e-04  2.01108301e-03  1.18129747e-02\n",
      "    2.06304114e-02]\n",
      "  [ 0.00000000e+00  4.99860191e-04  4.98249847e-04  3.36833291e-03\n",
      "    1.51100426e-02]\n",
      "  [ 0.00000000e+00  0.00000000e+00  4.69099087e-05  1.59883867e-04\n",
      "    2.09292465e-03]]] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('For maxWeight, the state-value estimates are summarized in')\n",
    "print('v =\\n', v, '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Estimate the values $v$ of the states $\\vec{q}$ under policy 2 (MSC)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# estimate the values v of the states q under policy 2 (maxSizeCenter)\n",
    "\n",
    "def chooseServeNonzeroQueuesConfiguration(s, q):\n",
    "    if q[2] == 0:\n",
    "        s[0] = s[1] = 1\n",
    "        return\n",
    "    if q[0] == 0 or q[1] == 0:\n",
    "        s[2] = 1\n",
    "        return\n",
    "    s[0] = s[1] = 1\n",
    "    #chooseMaxWeightServiceConfiguration(s, q)\n",
    "\n",
    "# initialize current states q, past average reward m, and value estimates v at time t = 0\n",
    "\n",
    "q = np.array([0, 0, 0])\n",
    "m = 0\n",
    "v = np.zeros((c + 1, c + 1, c + 1))\n",
    "\n",
    "# update v 10,000,000 times (with the first one being trivial)\n",
    "\n",
    "for t in range(1, 10000001):\n",
    "    # right now we've got q(t - 1)\n",
    "    s = np.array([0, 0, 0])\n",
    "    chooseServeNonzeroQueuesConfiguration(s, q) # compute service configuration s(t - 1) for the interval [t - 1, t]\n",
    "    a = anArrivalVector(a1_avg, a2_avg, a3_avg) # generate arrival configuration a(t - 1) for the interval [t - 1, t]\n",
    "    r = sum(q) # compute current reward r(t - 1)\n",
    "    m_t_minus_1 = m # store m(t - 1)\n",
    "    m = (1 - 1 / t) * m + (1 / t) * r # compute past average reward m(t) based on t, m(t - 1), and current reward r(t - 1)\n",
    "    q_t_minus_1 = q # store q(t - 1)\n",
    "    q = elementWiseMin(elementWiseMax(q + a - s, np.array([0, 0, 0])), np.array([c, c, c])) # compute current state q(t)\n",
    "    \n",
    "    # update value estimate v(q(t - 1)) based on v(q(t - 1)), t, r(t - 1), m(t - 1), and v(q(t))\n",
    "    v[q_t_minus_1[0], q_t_minus_1[1], q_t_minus_1[2]] += (1 / t) * (r - m_t_minus_1 + v[q[0], q[1], q[2]] - v[q_t_minus_1[0], q_t_minus_1[1], q_t_minus_1[2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For MSC, the state-value estimates are summarized in\n",
      "v =\n",
      " [[[-2.45230825e+00 -1.56738034e+00 -3.39941787e-01 -1.60306882e-01\n",
      "    4.41802813e-02]\n",
      "  [-8.11796271e-01 -4.78158022e-01  1.31018945e-02  7.26024668e-02\n",
      "    3.03177304e-01]\n",
      "  [-3.16679183e-01 -8.06860615e-02  5.80752490e-02  4.55404765e-01\n",
      "    3.83584094e-01]\n",
      "  [-1.04954221e-01  2.22312687e-01  4.71293079e-01  3.00751176e-01\n",
      "    3.62500173e-01]\n",
      "  [ 1.69563055e-01  2.13784576e-01  3.53496996e-01  3.85231192e-01\n",
      "    3.62806898e-01]]\n",
      "\n",
      " [[-9.19142693e-01 -4.08083441e-01 -2.69987528e-01  2.55172895e-02\n",
      "    2.45564183e-01]\n",
      "  [ 1.61575250e-02 -1.66146989e-01  3.72264486e-02  1.92170845e-01\n",
      "    3.28678099e-01]\n",
      "  [-3.89052804e-02  1.43710321e-02  1.04884223e-01  1.65555057e-01\n",
      "    2.69003661e-01]\n",
      "  [ 9.18464518e-02  4.63118550e-02  4.33043564e-01  1.56491302e-01\n",
      "    2.16522835e-01]\n",
      "  [ 2.78919654e-02  7.23355149e-02  1.26612517e-01  1.52447683e-01\n",
      "    1.68798504e-01]]\n",
      "\n",
      " [[-4.01731072e-01 -2.13503475e-01  2.30459141e-02  2.14011685e-01\n",
      "    3.71249141e-01]\n",
      "  [-4.95258636e-02 -1.74965211e-03  7.18057614e-02  1.82831738e-01\n",
      "    2.34963176e-01]\n",
      "  [-5.12032217e-04  1.81018197e-02  4.13999323e-02  1.83151725e-01\n",
      "    1.91916220e-01]\n",
      "  [ 3.75093994e-03  1.94999623e-02  2.68661219e-02  3.89660454e-02\n",
      "    4.07121270e-02]\n",
      "  [ 1.14263707e-01  1.28354297e-02  2.07412975e-02  2.48889670e-02\n",
      "    1.76626290e-02]]\n",
      "\n",
      " [[-1.47835244e-01  1.29015602e-02  1.98851475e-01  3.07747503e-01\n",
      "    3.67134640e-01]\n",
      "  [ 3.35236453e-03  5.28861298e-02  9.42215140e-02  2.65238149e-01\n",
      "    1.61220652e-01]\n",
      "  [ 6.99669224e-03  3.00304349e-02  3.04883128e-02  3.70375495e-02\n",
      "    2.53854370e-01]\n",
      "  [ 1.55515961e-03  4.89883911e-03  7.15970132e-03  5.30079802e-03\n",
      "    1.65533897e-02]\n",
      "  [ 9.21544111e-04  2.73415335e-03  2.40220387e-03  2.90180603e-03\n",
      "    2.51169641e-03]]\n",
      "\n",
      " [[ 4.47174088e-03  1.67401565e-01  3.02461859e-01  3.60464112e-01\n",
      "    3.08650586e-01]\n",
      "  [ 3.80451182e-02  9.89417047e-02  1.08046803e-01  1.45828126e-01\n",
      "    1.32540447e-01]\n",
      "  [ 5.65546967e-03  1.56144202e-02  1.04154188e-01  1.87134908e-02\n",
      "    1.02624265e-01]\n",
      "  [ 4.02256715e-03  1.75552284e-03  9.40415745e-03  2.28483159e-03\n",
      "    3.19709235e-03]\n",
      "  [ 2.04876685e-04  2.38062668e-04  3.72241353e-04  3.29592352e-04\n",
      "    7.69871060e-04]]] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('For MSC, the state-value estimates are summarized in')\n",
    "print('v =\\n', v, '\\n')"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}