Exp17.ipynb

{
 "metadata": {
  "name": "Exp17"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#All IRL algs on the perturbed Highway\n",
      "from DP import *\n",
      "from stuff import *\n",
      "from pylab import *\n",
      "from random import *\n",
      "import numpy\n",
      "from rl import *\n",
      "P = genfromtxt(\"Highway_perturbed_P.mat\")\n",
      "R = genfromtxt(\"Highway_R.mat\")\n",
      "Gamma_RE = 0.99\n",
      "Gamma_allothers = 0.9\n",
      "ACTION_SPACE = range(0,5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import sys\n",
      "\n",
      "EPISODE_LENGTH_AND_NB_EPISODES=10\n",
      "#EPISODE_LENGTH_AND_NB_EPISODES=int(sys.argv[1])\n",
      "RAND_STRING=str(int(rand()*10000000000))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Highway = MDP(P,R)\n",
      "mPi_E, V_E, Pi_E = Highway.optimal_policy()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "MDP OK3\n",
        "Shape of P (3645, 729)\n",
        "Shape of R (3645,)\n",
        "Card of S 729\n",
        "Card of A 5\n",
        "Card of SA 3645\n",
        "Iteration 0, 1266\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 1, 702\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 2, 178\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 3, 46\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 4, 4\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 5, 0\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rho = lambda : int(rand()*729) #uniform distribtion over S\n",
      "l_D_E = [array(Highway.D_func(Pi_E, 1, EPISODE_LENGTH_AND_NB_EPISODES,  rho)) for i in range(0,EPISODE_LENGTH_AND_NB_EPISODES)]\n",
      "D_E = vstack(l_D_E)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Relative Entropy\n",
      "class GradientDescent(object):\n",
      "   def alpha( self, t ):\n",
      "      raise NotImplementedError, \"Cannot call abstract method\"\n",
      "\n",
      "   theta_0=None\n",
      "   Threshold=None\n",
      "   T = -1\n",
      "   sign = None\n",
      "        \n",
      "   def run( self, f_grad, f_proj=None, b_norm=False, b_best=True ): #grad is a function of theta\n",
      "      theta = self.theta_0.copy()\n",
      "      best_theta = theta.copy()\n",
      "      best_norm = float(\"inf\")\n",
      "      best_iter = 0\n",
      "      t=0\n",
      "      while True:#Do...while loop\n",
      "         t+=1\n",
      "         DeltaTheta = f_grad( theta )\n",
      "         current_norm = norm( DeltaTheta )\n",
      "         if b_norm and  current_norm > 0.:\n",
      "             DeltaTheta /= norm( DeltaTheta )\n",
      "         theta = theta + self.sign * self.alpha( t )*DeltaTheta\n",
      "         if f_proj:\n",
      "             theta = f_proj( theta )\n",
      "         print \"Norme du gradient : \"+str(current_norm)+\", pas : \"+str(self.alpha(t))+\", iteration : \"+str(t)\n",
      "\n",
      "         if current_norm < best_norm or not b_best:\n",
      "             best_norm = current_norm\n",
      "             best_theta = theta.copy()\n",
      "             best_iter = t\n",
      "         if current_norm < self.Threshold or (self.T != -1 and t >= self.T):\n",
      "             break\n",
      "\n",
      "      print \"Gradient de norme : \"+str(best_norm)+\", a l'iteration : \"+str(best_iter)\n",
      "      return best_theta\n",
      "                            \n",
      "class RelativeEntropy(GradientDescent):\n",
      "    sign=+1.\n",
      "    Threshold=0.01 #Sensible default\n",
      "    T=50 #Sensible default\n",
      "    Epsilon = 0.05 #RelEnt parameter, sensible default\n",
      "\n",
      "    def alpha(self, t):\n",
      "        return 1./(t+1)#Sensible default\n",
      "    \n",
      "    def __init__(self, mu_E, mus):\n",
      "        self.theta_0 = zeros(mu_E.shape)\n",
      "        self.Mu_E = mu_E\n",
      "        self.Mus = mus\n",
      "    \n",
      "    def gradient(self, theta):\n",
      "        numerator = 0\n",
      "        denominator = 0\n",
      "        for mu in self.Mus:\n",
      "            c = exp(dot(theta.transpose(),mu))\n",
      "            numerator += c*mu\n",
      "            denominator += c\n",
      "        assert denominator != 0,\"A sum of exp(...) is null, some black magic happened here.\"\n",
      "        return self.Mu_E - numerator/denominator - sign(theta)*self.Epsilon\n",
      "    \n",
      "    def run(self):\n",
      "        f_grad = lambda theta: self.gradient(theta)\n",
      "        theta = super(RelativeEntropy,self).run( f_grad, b_norm=True, b_best=False)\n",
      "        return theta\n",
      "Mu_E = zeros((3645,1))\n",
      "l_mu_E = []\n",
      "for episode in l_D_E:\n",
      "    mu = zeros((3645,1))\n",
      "    for i in range(0,len(episode)):\n",
      "        s = episode[i][0]\n",
      "        a = episode[i][1]\n",
      "        mu[s + a*729] += pow(Gamma_RE,i)\n",
      "    mu /= float(len(episode))\n",
      "    l_mu_E.append(mu)\n",
      "Mu_E = mean(l_mu_E,axis=0)\n",
      "Mu_E.shape\n",
      "random_policy = lambda s: int(rand()*5)\n",
      "Mus = []\n",
      "for i in range(0,100):\n",
      "    D = Highway.D_func(random_policy, 1, 10, rho)\n",
      "    mu = zeros((3645,1))\n",
      "    for i in range(0,10):\n",
      "        s = D[i][0]\n",
      "        a = D[i][1]\n",
      "        mu[s + a*729] += pow(Gamma_RE,i)\n",
      "    mu /= 10.\n",
      "    Mus.append(mu)\n",
      "Mus.append(Mu_E)\n",
      "RE = RelativeEntropy(Mu_E, Mus)\n",
      "reward_RE = RE.run()\n",
      "\n",
      "Highway_RE = MDP(P,reward_RE)\n",
      "mPi_RE, V_RE, Pi_RE = Highway_RE.optimal_policy()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Norme du gradient : 0.135684644586, pas : 0.5, iteration : 1\n",
        "Norme du gradient : 1.43092002124, pas : 0.333333333333, iteration : 2\n",
        "Norme du gradient : 1.49311214861, pas : 0.25, iteration : 3\n",
        "Norme du gradient : 1.43143079236, pas : 0.2, iteration : 4\n",
        "Norme du gradient : 1.4904504263, pas : 0.166666666667, iteration : 5\n",
        "Norme du gradient : 1.47795496669, pas : 0.142857142857, iteration : 6\n",
        "Norme du gradient : 1.44989895461, pas : 0.125, iteration : 7\n",
        "Norme du gradient : 1.45413659115, pas : 0.111111111111, iteration : 8\n",
        "Norme du gradient : 1.50449146761, pas : 0.1, iteration : 9\n",
        "Norme du gradient : 1.47737491622, pas : 0.0909090909091, iteration : 10\n",
        "Norme du gradient : 1.45966171384, pas : 0.0833333333333, iteration : 11\n",
        "Norme du gradient : 1.46795033107, pas : 0.0769230769231, iteration : 12\n",
        "Norme du gradient : 1.48203541288, pas : 0.0714285714286, iteration : 13"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 1.47864346626, pas : 0.0666666666667, iteration : 14\n",
        "Norme du gradient : 1.47590087811, pas : 0.0625, iteration : 15\n",
        "Norme du gradient : 1.47368973705, pas : 0.0588235294118, iteration : 16\n",
        "Norme du gradient : 1.48567595558, pas : 0.0555555555556, iteration : 17\n",
        "Norme du gradient : 1.46345610069, pas : 0.0526315789474, iteration : 18\n",
        "Norme du gradient : 1.48840466223, pas : 0.05, iteration : 19\n",
        "Norme du gradient : 1.46693699831, pas : 0.047619047619, iteration : 20\n",
        "Norme du gradient : 1.48857431242, pas : 0.0454545454545, iteration : 21\n",
        "Norme du gradient : 1.46971101571, pas : 0.0434782608696, iteration : 22\n",
        "Norme du gradient : 1.48373952582, pas : 0.0416666666667, iteration : 23"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 1.46759532088, pas : 0.04, iteration : 24\n",
        "Norme du gradient : 1.48855018921, pas : 0.0384615384615, iteration : 25\n",
        "Norme du gradient : 1.46976400735, pas : 0.037037037037, iteration : 26\n",
        "Norme du gradient : 1.48832154505, pas : 0.0357142857143, iteration : 27\n",
        "Norme du gradient : 1.45765063865, pas : 0.0344827586207, iteration : 28\n",
        "Norme du gradient : 1.49807383983, pas : 0.0333333333333, iteration : 29\n",
        "Norme du gradient : 1.46602382087, pas : 0.0322580645161, iteration : 30\n",
        "Norme du gradient : 1.486487485, pas : 0.03125, iteration : 31\n",
        "Norme du gradient : 1.46435684643, pas : 0.030303030303, iteration : 32\n",
        "Norme du gradient : 1.49435356674, pas : 0.0294117647059, iteration : 33"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 1.45522640848, pas : 0.0285714285714, iteration : 34\n",
        "Norme du gradient : 1.49366046712, pas : 0.0277777777778, iteration : 35\n",
        "Norme du gradient : 1.46234149964, pas : 0.027027027027, iteration : 36\n",
        "Norme du gradient : 1.49523234497, pas : 0.0263157894737, iteration : 37\n",
        "Norme du gradient : 1.45448120352, pas : 0.025641025641, iteration : 38\n",
        "Norme du gradient : 1.50359490282, pas : 0.025, iteration : 39\n",
        "Norme du gradient : 1.44612516817, pas : 0.0243902439024, iteration : 40\n",
        "Norme du gradient : 1.50655965942, pas : 0.0238095238095, iteration : 41\n",
        "Norme du gradient : 1.46520857261, pas : 0.0232558139535, iteration : 42\n",
        "Norme du gradient : 1.49247963873, pas : 0.0227272727273, iteration : 43"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 1.45216235553, pas : 0.0222222222222, iteration : 44\n",
        "Norme du gradient : 1.49848659465, pas : 0.0217391304348, iteration : 45\n",
        "Norme du gradient : 1.463568627, pas : 0.0212765957447, iteration : 46\n",
        "Norme du gradient : 1.49734687784, pas : 0.0208333333333, iteration : 47\n",
        "Norme du gradient : 1.45513240738, pas : 0.0204081632653, iteration : 48\n",
        "Norme du gradient : 1.50391010612, pas : 0.02, iteration : 49\n",
        "Norme du gradient : 1.45104793592, pas : 0.0196078431373, iteration : 50\n",
        "Gradient de norme : 1.45104793592, a l'iteration : 50\n",
        "MDP OK3\n",
        "Shape of P (3645, 729)\n",
        "Shape of R (3645, 1)\n",
        "Card of S 729\n",
        "Card of A 5\n",
        "Card of SA 3645\n",
        "Iteration 0, 1226\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 1, 928\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 2, 582\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 3, 322\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 4, 192\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 5, 58\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 6, 8\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 7, 0\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#SCIRL\n",
      "#Precomputing mu with MC and heuristics\n",
      "def MC_mu(episode):\n",
      "    answer = zeros((729,1))\n",
      "    for i in range(0,len(episode)):\n",
      "        answer[episode[i]] += pow(Gamma_allothers,i)\n",
      "    return answer\n",
      "\n",
      "feature_expectations_MC = {}\n",
      "d_mu_MC = {}\n",
      "for episode in l_D_E:\n",
      "    for start_index in range(0,len(episode)):\n",
      "        data_MC=episode[start_index:,:2]\n",
      "        state_action = data_MC[0,:2]\n",
      "        state = data_MC[0,0]\n",
      "        action = data_MC[0,1]\n",
      "        mu = MC_mu(data_MC[:,0])\n",
      "        try:\n",
      "            d_mu_MC[str(state_action)].append(mu)\n",
      "        except KeyError:\n",
      "            d_mu_MC[str(state_action)] = [mu]\n",
      "        for other_action in [a for a in ACTION_SPACE if a != action]:\n",
      "            state_action=hstack([state,other_action])\n",
      "            try:\n",
      "                d_mu_MC[str(state_action)].append(Gamma_allothers*mu)\n",
      "            except KeyError:\n",
      "                d_mu_MC[str(state_action)]=[Gamma_allothers*mu]\n",
      "for sa in d_mu_MC.keys():\n",
      "    feature_expectations_MC[sa] = mean(d_mu_MC[sa],axis=0)\n",
      "#Structured Classifier\n",
      "class GradientDescent(object):\n",
      "    \n",
      "   def alpha( self, t ):\n",
      "      raise NotImplementedError, \"Cannot call abstract method\"\n",
      "\n",
      "   theta_0=None\n",
      "   Threshold=None\n",
      "   T = -1\n",
      "   sign = None\n",
      "        \n",
      "   def run( self, f_grad, f_proj=None, b_norm=False ): #grad is a function of theta\n",
      "      theta = self.theta_0.copy()\n",
      "      best_theta = theta.copy()\n",
      "      best_norm = float(\"inf\")\n",
      "      best_iter = 0\n",
      "      t=0\n",
      "      while True:#Do...while loop\n",
      "         t+=1\n",
      "         DeltaTheta = f_grad( theta )\n",
      "         current_norm = norm( DeltaTheta )\n",
      "         if b_norm and  current_norm > 0.:\n",
      "             DeltaTheta /= norm( DeltaTheta )\n",
      "         theta = theta + self.sign * self.alpha( t )*DeltaTheta\n",
      "         if f_proj:\n",
      "             theta = f_proj( theta )\n",
      "         print \"Norme du gradient : \"+str(current_norm)+\", pas : \"+str(self.alpha(t))+\", iteration : \"+str(t)\n",
      "\n",
      "         if current_norm < best_norm:\n",
      "             best_norm = current_norm\n",
      "             best_theta = theta.copy()\n",
      "             best_iter = t\n",
      "         if current_norm < self.Threshold or (self.T != -1 and t >= self.T):\n",
      "             break\n",
      "\n",
      "      print \"Gradient de norme : \"+str(best_norm)+\", a l'iteration : \"+str(best_iter)\n",
      "      return best_theta\n",
      "\n",
      "\n",
      "class StructuredClassifier(GradientDescent):\n",
      "    sign=-1.\n",
      "    Threshold=0.01 #Sensible default\n",
      "    T=40 #Sensible default\n",
      "    phi=None\n",
      "    phi_xy=None\n",
      "    inputs=None\n",
      "    labels=None\n",
      "    label_set=None\n",
      "    dic_data={}\n",
      "    x_dim=None\n",
      "    \n",
      "    def alpha(self, t):\n",
      "        return 3./(t+1)#Sensible default\n",
      "    \n",
      "    def __init__(self, data, x_dim, phi, phi_dim, Y):\n",
      "        self.x_dim=x_dim\n",
      "        self.inputs = data[:,:-1]\n",
      "        shape = list(data.shape)\n",
      "        shape[-1] = 1\n",
      "        self.labels = data[:,-1].reshape(shape)\n",
      "        self.phi=phi\n",
      "        self.label_set = Y\n",
      "        self.theta_0 = zeros((phi_dim,1))\n",
      "        self.phi_xy = self.phi(data)\n",
      "        for x,y in zip(self.inputs,self.labels):\n",
      "            self.dic_data[str(x)] = y\n",
      "        print self.inputs.shape\n",
      "    \n",
      "    def structure(self, xy):\n",
      "        return 0. if xy[-1] == self.dic_data[str(xy[:-1])] else 1.\n",
      "        \n",
      "    def structured_decision(self, theta):\n",
      "        def decision( x ):\n",
      "            score = lambda xy: dot(theta.transpose(),self.phi(xy)) + self.structure(xy)\n",
      "            input_label_couples = [hstack([x,y]) for y in self.label_set]\n",
      "            best_label = argmax(input_label_couples, score)[-1]\n",
      "            return best_label\n",
      "        vdecision = non_scalar_vectorize(decision, (self.x_dim,), (1,1))\n",
      "        return lambda x: vdecision(x).reshape(x.shape[:-1]+(1,))\n",
      "    \n",
      "    def gradient(self, theta):\n",
      "        classif_rule = self.structured_decision(theta)\n",
      "        y_star = classif_rule(self.inputs)\n",
      "        #print \"Gradient : \"+str(y_star)\n",
      "        #print str(self.labels)\n",
      "        phi_star = self.phi(hstack([self.inputs,y_star]))\n",
      "        return mean(phi_star-self.phi_xy,axis=0)\n",
      "    \n",
      "    def run(self):\n",
      "        f_grad = lambda theta: self.gradient(theta)\n",
      "        theta = super(StructuredClassifier,self).run( f_grad, b_norm=True)\n",
      "        classif_rule = greedy_policy(theta,self.phi,self.label_set)\n",
      "        return classif_rule,theta\n",
      "single_mu = lambda sa:feature_expectations_MC[str(sa)]\n",
      "mu_E = non_scalar_vectorize(single_mu, (2,), (729,1))\n",
      "SCIRL_MC = StructuredClassifier(D_E[:,:2], 1, mu_E, 729, ACTION_SPACE)\n",
      "void,reward_SCIRL_short = SCIRL_MC.run()\n",
      "\n",
      "def Sgenerator( ):\n",
      "    for v in range(0,3):\n",
      "        for x_b in range(0,9):\n",
      "            for y_r in range(0,9):\n",
      "                for x_r in range(0,3):\n",
      "                    yield [v,x_b,y_r,x_r]\n",
      "\n",
      "S = [s for s in Sgenerator()]\n",
      "\n",
      "A = range(0,5)\n",
      "\n",
      "def s_index( state ):\n",
      "    v = state[0]\n",
      "    x_b = state[1]\n",
      "    y_r = state[2]\n",
      "    x_r = state[3]\n",
      "    index = x_r + y_r*3 + x_b*3*9 + v*3*9*9\n",
      "    return index\n",
      "\n",
      "def sa_index( state, action ):\n",
      "    index = s_index(state) + action*3*9*9*3\n",
      "    return index\n",
      "\n",
      "print reward_SCIRL_short.shape\n",
      "reward_SCIRL=zeros((3645,1))\n",
      "for state in S:\n",
      "    current_indices = [sa_index(state,a) for a in ACTION_SPACE]\n",
      "    reward_SCIRL[current_indices] = reward_SCIRL_short[s_index(state)]\n",
      "print reward_SCIRL.shape\n",
      "Highway_SCIRL = MDP(P,reward_SCIRL)\n",
      "mPi_SCIRL, V_SCIRL, Pi_SCIRL = Highway_SCIRL.optimal_policy()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(100, 1)\n",
        "Norme du gradient : 0.0645454469155, pas : 1.5, iteration : 1"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 1.0, iteration : 2"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.75, iteration : 3"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.6, iteration : 4"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.5, iteration : 5"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.428571428571, iteration : 6"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.375, iteration : 7"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.333333333333, iteration : 8"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.3, iteration : 9"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.272727272727, iteration : 10"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.25, iteration : 11"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.230769230769, iteration : 12"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0645454469155, pas : 0.214285714286, iteration : 13"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0630677180082, pas : 0.2, iteration : 14"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0630677180082, pas : 0.1875, iteration : 15"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0630677180082, pas : 0.176470588235, iteration : 16"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.061728444474, pas : 0.166666666667, iteration : 17"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.061728444474, pas : 0.157894736842, iteration : 18"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.061728444474, pas : 0.15, iteration : 19"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.061728444474, pas : 0.142857142857, iteration : 20"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.061728444474, pas : 0.136363636364, iteration : 21"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0605461438843, pas : 0.130434782609, iteration : 22"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0605461438843, pas : 0.125, iteration : 23"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0560869886312, pas : 0.12, iteration : 24"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0560869886312, pas : 0.115384615385, iteration : 25"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0560869886312, pas : 0.111111111111, iteration : 26"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0550389271475, pas : 0.107142857143, iteration : 27"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0550389271475, pas : 0.103448275862, iteration : 28"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0540508006411, pas : 0.1, iteration : 29"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0540508006411, pas : 0.0967741935484, iteration : 30"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.053105126152, pas : 0.09375, iteration : 31"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.053105126152, pas : 0.0909090909091, iteration : 32"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.053105126152, pas : 0.0882352941176, iteration : 33"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.053105126152, pas : 0.0857142857143, iteration : 34"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.047891203977, pas : 0.0833333333333, iteration : 35"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.047891203977, pas : 0.0810810810811, iteration : 36"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.047891203977, pas : 0.0789473684211, iteration : 37"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0471627075828, pas : 0.0769230769231, iteration : 38"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0471627075828, pas : 0.075, iteration : 39"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.0471627075828, pas : 0.0731707317073, iteration : 40"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Gradient de norme : 0.0471627075828, a l'iteration : 38\n",
        "(729, 1)\n",
        "(3645, 1)\n",
        "MDP OK3\n",
        "Shape of P (3645, 729)\n",
        "Shape of R (3645, 1)\n",
        "Card of S 729\n",
        "Card of A 5\n",
        "Card of SA 3645\n",
        "Iteration 0, 1310\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 1, 554\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 2, 196\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 3, 22\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 4, 0\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#CSI\n",
      "#Classification\n",
      "\n",
      "class BlockOptimizedStructuredClassifier(GradientDescent):\n",
      "    sign=-1.\n",
      "    Threshold=0.01 #Sensible default\n",
      "    T=100 #Sensible default\n",
      "    phi=None\n",
      "    label_set=None\n",
      "    \n",
      "    def alpha(self, t):\n",
      "        return 3./(t+1)#Sensible default\n",
      "    \n",
      "    def __init__(self, psi, actions, nb_actions):\n",
      "        self.label_set=range(0,nb_actions)\n",
      "        self.N,self.K = psi.shape\n",
      "        self.A = nb_actions\n",
      "        self.theta_0 = zeros(self.K*self.A)\n",
      "        self.ExpertDecision = zeros((self.N,self.A))\n",
      "        for i,j in zip( range(0,self.N), actions.reshape(self.N) ):\n",
      "            self.ExpertDecision[i,j] = 1.\n",
      "        self.Structure = array(self.ExpertDecision!=1)\n",
      "        self.ExpertDecision = self.ExpertDecision.reshape(self.N,self.A,1)\n",
      "        self.Psi_3 = array([[p for i in range(0,self.A)] for p in psi])\n",
      "        self.Phi = self.ExpertDecision*self.Psi_3\n",
      "        self.Phi = self.Phi.reshape(self.N,self.K*self.A)\n",
      "        self.Psi = psi\n",
      "    \n",
      "    def gradient(self, theta):\n",
      "        theta_2 = hstack([theta[i*self.K:(i+1)*self.K].reshape((self.K,1)) for i in range(0,self.A)])\n",
      "        score = dot(self.Psi,theta_2)+self.Structure\n",
      "        maxScore = dot(score.max(axis=1).reshape((self.N,1)),ones((1,self.A)))\n",
      "        decision = (score==maxScore).reshape(self.N,self.A,1)\n",
      "        #We restrict ourselves to one arbitrary decision\n",
      "        for i in range(0,self.N):\n",
      "            gotOne = False\n",
      "            for j in range(0,self.A):\n",
      "                if decision[i,j] and not gotOne:\n",
      "                    gotOne = True\n",
      "                elif decision[i,j] and gotOne:\n",
      "                    decision[i,j] = False\n",
      "        phi_star = decision*self.Psi_3\n",
      "        phi_star = phi_star.reshape(self.N,self.K*self.A)\n",
      "        return mean(phi_star-self.Phi,axis=0)\n",
      "    \n",
      "    def run(self):\n",
      "        f_grad = lambda theta: self.gradient(theta)\n",
      "        theta = super(BlockOptimizedStructuredClassifier,self).run( f_grad, b_norm=True)\n",
      "        return theta\n",
      "\n",
      "Psi = zeros((len(D_E),729))\n",
      "for i,j in zip(range(0,len(D_E)),D_E[:,0]):\n",
      "    Psi[i,j]=1.\n",
      "clf = BlockOptimizedStructuredClassifier(Psi, D_E[:,1], 5)\n",
      "theta_C = clf.run()\n",
      "mPi_C = Highway.Q2Pi(theta_C)\n",
      "\n",
      "def single_phi(sa):\n",
      "    answer = zeros((3645,1))\n",
      "    answer[sa[0] + 729*sa[1]] = 1.\n",
      "    return answer\n",
      "phi = non_scalar_vectorize(single_phi, (2,), (3645,1))\n",
      "q = lambda sa: squeeze(dot(theta_C.transpose(),phi(sa)))\n",
      "#pi_c = greedy_policy(theta_C,phi,ACTION_SPACE, s_dim=1)\n",
      "single_pi_c = lambda s : Highway.control(s, mPi_C)\n",
      "pi_c = vectorize(single_pi_c)\n",
      "#Donn\u00e9es pour la regression\n",
      "column_shape = (len(D_E),1)\n",
      "s = D_E[:,0].reshape(column_shape)\n",
      "a = D_E[:,1].reshape(column_shape)\n",
      "sa = D_E[:,:2]\n",
      "s_dash = D_E[:,3].reshape(column_shape)\n",
      "a_dash = pi_c(s_dash).reshape(column_shape)\n",
      "sa_dash = hstack([s_dash,a_dash])\n",
      "hat_r = (q(sa)-Gamma_allothers*q(sa_dash)).reshape(column_shape)\n",
      "r_min = min(hat_r)-1.*ones(column_shape)\n",
      "##Avec l'heuristique : \n",
      "thetas = zeros((5,729))\n",
      "for action in ACTION_SPACE:\n",
      "    X = Psi\n",
      "    hat_r_bool_table = array(a==action)\n",
      "    r_min_bool_table = array(hat_r_bool_table==False) #\"not hat_r_bool_table\" does not work as I expected\n",
      "    Y =  hat_r_bool_table*hat_r + r_min_bool_table*r_min\n",
      "    #if sum(hat_r_bool_table) == 0:\n",
      "    #    thetas[action] = zeros(729)\n",
      "    #else:\n",
      "    thetas[action] = squeeze( dot(dot(inv(dot(X.transpose(),X)+0.1*identity(X.shape[1])),X.transpose()),Y) )\n",
      "theta_CSI = thetas.reshape(3645)\n",
      "fCSI_reward = lambda sa:dot(theta_CSI.transpose(),phi(sa))\n",
      "reward_CSI=zeros((3645,1))\n",
      "for state in S:\n",
      "    for action in ACTION_SPACE:\n",
      "        index = sa_index(state, action)\n",
      "        reward_CSI[index] = fCSI_reward(array([s_index(state),action]))\n",
      "Highway_CSI = MDP(P,reward_CSI)\n",
      "mPi_CSI, V_CSI, Pi_CSI = Highway_CSI.optimal_policy()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Norme du gradient : 0.202977831302, pas : 1.5, iteration : 1\n",
        "Norme du gradient : 0.202977831302, pas : 1.0, iteration : 2\n",
        "Norme du gradient : 0.202977831302, pas : 0.75, iteration : 3\n",
        "Norme du gradient : 0.202977831302, pas : 0.6, iteration : 4\n",
        "Norme du gradient : 0.163707055437, pas : 0.5, iteration : 5\n",
        "Norme du gradient : 0.153622914957, pas : 0.428571428571, iteration : 6\n",
        "Norme du gradient : 0.153622914957, pas : 0.375, iteration : 7"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.153622914957, pas : 0.333333333333, iteration : 8\n",
        "Norme du gradient : 0.134907375632, pas : 0.3, iteration : 9\n",
        "Norme du gradient : 0.134907375632, pas : 0.272727272727, iteration : 10\n",
        "Norme du gradient : 0.134907375632, pas : 0.25, iteration : 11\n",
        "Norme du gradient : 0.134907375632, pas : 0.230769230769, iteration : 12"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.134907375632, pas : 0.214285714286, iteration : 13\n",
        "Norme du gradient : 0.134907375632, pas : 0.2, iteration : 14\n",
        "Norme du gradient : 0.134907375632, pas : 0.1875, iteration : 15\n",
        "Norme du gradient : 0.108627804912, pas : 0.176470588235, iteration : 16\n",
        "Norme du gradient : 0.108627804912, pas : 0.166666666667, iteration : 17"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.157894736842, iteration : 18\n",
        "Norme du gradient : 0.108627804912, pas : 0.15, iteration : 19\n",
        "Norme du gradient : 0.108627804912, pas : 0.142857142857, iteration : 20\n",
        "Norme du gradient : 0.108627804912, pas : 0.136363636364, iteration : 21\n",
        "Norme du gradient : 0.108627804912, pas : 0.130434782609, iteration : 22"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.125, iteration : 23\n",
        "Norme du gradient : 0.108627804912, pas : 0.12, iteration : 24\n",
        "Norme du gradient : 0.108627804912, pas : 0.115384615385, iteration : 25\n",
        "Norme du gradient : 0.108627804912, pas : 0.111111111111, iteration : 26\n",
        "Norme du gradient : 0.108627804912, pas : 0.107142857143, iteration : 27"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.103448275862, iteration : 28\n",
        "Norme du gradient : 0.108627804912, pas : 0.1, iteration : 29\n",
        "Norme du gradient : 0.108627804912, pas : 0.0967741935484, iteration : 30\n",
        "Norme du gradient : 0.108627804912, pas : 0.09375, iteration : 31\n",
        "Norme du gradient : 0.108627804912, pas : 0.0909090909091, iteration : 32"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.0882352941176, iteration : 33\n",
        "Norme du gradient : 0.108627804912, pas : 0.0857142857143, iteration : 34\n",
        "Norme du gradient : 0.108627804912, pas : 0.0833333333333, iteration : 35\n",
        "Norme du gradient : 0.108627804912, pas : 0.0810810810811, iteration : 36\n",
        "Norme du gradient : 0.108627804912, pas : 0.0789473684211, iteration : 37"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.0769230769231, iteration : 38\n",
        "Norme du gradient : 0.108627804912, pas : 0.075, iteration : 39\n",
        "Norme du gradient : 0.108627804912, pas : 0.0731707317073, iteration : 40\n",
        "Norme du gradient : 0.108627804912, pas : 0.0714285714286, iteration : 41\n",
        "Norme du gradient : 0.108627804912, pas : 0.0697674418605, iteration : 42"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.0681818181818, iteration : 43\n",
        "Norme du gradient : 0.108627804912, pas : 0.0666666666667, iteration : 44\n",
        "Norme du gradient : 0.108627804912, pas : 0.0652173913043, iteration : 45\n",
        "Norme du gradient : 0.108627804912, pas : 0.063829787234, iteration : 46\n",
        "Norme du gradient : 0.108627804912, pas : 0.0625, iteration : 47"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.0612244897959, iteration : 48\n",
        "Norme du gradient : 0.108627804912, pas : 0.06, iteration : 49\n",
        "Norme du gradient : 0.108627804912, pas : 0.0588235294118, iteration : 50\n",
        "Norme du gradient : 0.108627804912, pas : 0.0576923076923, iteration : 51\n",
        "Norme du gradient : 0.108627804912, pas : 0.0566037735849, iteration : 52"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.0555555555556, iteration : 53\n",
        "Norme du gradient : 0.108627804912, pas : 0.0545454545455, iteration : 54\n",
        "Norme du gradient : 0.108627804912, pas : 0.0535714285714, iteration : 55\n",
        "Norme du gradient : 0.108627804912, pas : 0.0526315789474, iteration : 56\n",
        "Norme du gradient : 0.108627804912, pas : 0.051724137931, iteration : 57"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.0508474576271, iteration : 58\n",
        "Norme du gradient : 0.108627804912, pas : 0.05, iteration : 59\n",
        "Norme du gradient : 0.108627804912, pas : 0.0491803278689, iteration : 60\n",
        "Norme du gradient : 0.108627804912, pas : 0.0483870967742, iteration : 61\n",
        "Norme du gradient : 0.108627804912, pas : 0.047619047619, iteration : 62"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Norme du gradient : 0.108627804912, pas : 0.046875, iteration : 63\n",
        "Norme du gradient : 0.108627804912, pas : 0.0461538461538, iteration : 64\n",
        "Norme du gradient : 0.108627804912, pas : 0.0454545454545, iteration : 65\n",
        "Norme du gradient : 0.0, pas : 0.044776119403, iteration : 66\n",
        "Gradient de norme : 0.0, a l'iteration : 66\n",
        "MDP OK3"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Shape of P (3645, 729)\n",
        "Shape of R (3645, 1)\n",
        "Card of S 729\n",
        "Card of A 5\n",
        "Card of SA 3645\n",
        "Iteration 0, 1278\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 1, 1106\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 2, 594\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 3, 218\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 4, 38\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 5, 2\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 6, 0\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Highway_R = MDP(P,rand(3645,1))\n",
      "mPi_R, V_R, Pi_R = Highway_R.optimal_policy()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "MDP OK3\n",
        "Shape of P (3645, 729)\n",
        "Shape of R (3645, 1)\n",
        "Card of S 729\n",
        "Card of A 5\n",
        "Card of SA 3645\n",
        "Iteration 0, 1200\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 1, 544\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 2, 216\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 3, 46\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 4, 2\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Iteration 5, 0\tactions changed."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print Highway.evaluate(mPi_R),Highway.evaluate(mPi_C),Highway.evaluate(mPi_RE),Highway.evaluate(mPi_SCIRL),Highway.evaluate(mPi_CSI),Highway.evaluate(mPi_E)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "-1.47725458962 "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "-0.21839052796 "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2.80084442123 "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2.99502187273 "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2.73181745493 "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3.88910961061\n"
       ]
      }
     ],
     "prompt_number": 28
    }
   ],
   "metadata": {}
  }
 ]
}