Q-Learning Delusion.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from rl_glue import RLGlue\n",
    "import agent\n",
    "from environment import BaseEnvironment\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Environment(BaseEnvironment):\n",
    "    \"\"\"Implements the environment for an RLGlue environment\n",
    "\n",
    "    Note:\n",
    "        env_init, env_start, env_step, env_cleanup, and env_message are required\n",
    "        methods.\n",
    "    \"\"\"\n",
    "\n",
    "    # def __init__(self):\n",
    "\n",
    "\n",
    "    def env_init(self, env_info={}):\n",
    "        \"\"\"Setup for the environment called when the experiment first starts.\n",
    "\n",
    "        Note:\n",
    "            Initialize a tuple with the reward, first state observation, boolean\n",
    "            indicating if it's terminal.\n",
    "        \"\"\"\n",
    "        self.start = 0\n",
    "        self.current_state = None\n",
    "        self.rand_generator = np.random.RandomState(env_info.get(\"seed\"))\n",
    "\n",
    "    def env_start(self):\n",
    "        \"\"\"The first method called when the episode starts, called before the\n",
    "        agent starts.\n",
    "\n",
    "        Returns:\n",
    "            The first state observation from the environment.\n",
    "        \"\"\"\n",
    "        self.current_state = self.start \n",
    "\n",
    "        self.reward_obs_term = (0.0, self.observation(self.current_state), False)\n",
    "\n",
    "        return self.reward_obs_term[1]\n",
    "\n",
    "    def env_step(self, action):\n",
    "        \"\"\"A step taken by the environment.\n",
    "\n",
    "        Args:\n",
    "            action: The action taken by the agent\n",
    "\n",
    "        Returns:\n",
    "            (float, state, Boolean): a tuple of the reward, state observation,\n",
    "                and boolean indicating if it's terminal.\n",
    "        \"\"\"\n",
    "\n",
    "        if action == 0:\n",
    "            if self.current_state == 0:\n",
    "                if self.rand_generator.rand() < 0.1:\n",
    "                    new_state = 3\n",
    "                    reward = 0\n",
    "                else:\n",
    "                    new_state = 4\n",
    "                    reward = 0.3\n",
    "            else:\n",
    "                new_state = 4\n",
    "                reward = 0\n",
    "\n",
    "        else:\n",
    "            if self.current_state == 3:\n",
    "                reward = 2\n",
    "            else:\n",
    "                reward = 0\n",
    "            new_state = self.current_state + 1\n",
    "\n",
    "        self.current_state = new_state\n",
    "        is_terminal = (new_state > 3)\n",
    "\n",
    "        self.reward_obs_term = (reward, self.observation(self.current_state), is_terminal)\n",
    "        # print(action, self.reward_obs_term)\n",
    "\n",
    "        return self.reward_obs_term\n",
    "\n",
    "    # NOTE\n",
    "    # The observation is two-dimensional in this environment.\n",
    "    # Each row in the observation is the observation for an action.\n",
    "    # The agent implementations in the next cells work with these two-dimensional observations.\n",
    "    def observation(self, state):\n",
    "        if state == 0:\n",
    "            obs = np.array([[0,1],[.8,0]])\n",
    "        elif state == 1:\n",
    "            obs = np.array([[0,0],[.8,0]])\n",
    "        elif state == 2:\n",
    "            obs = np.array([[0,0],[-1,0]])\n",
    "        elif state == 3:\n",
    "            obs = np.array([[0,1],[-1,0]])\n",
    "        else:\n",
    "            obs = np.zeros((2,2))\n",
    "        return obs\n",
    "\n",
    "    def env_cleanup(self):\n",
    "        \"\"\"Cleanup done after the environment ends\"\"\"\n",
    "        pass\n",
    "\n",
    "    def env_message(self, message):\n",
    "        \"\"\"A message asking the environment for information\n",
    "\n",
    "        Args:\n",
    "            message (string): the message passed to the environment\n",
    "\n",
    "        Returns:\n",
    "            string: the response (or answer) to the message\n",
    "        \"\"\"\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Agents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q-Learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q-Learning agent\n",
    "class QLearningAgent(agent.BaseAgent):\n",
    "    def agent_init(self, agent_init_info):\n",
    "        \"\"\"Setup for the agent called when the experiment first starts.\n",
    "        \n",
    "        Args:\n",
    "        agent_init_info (dict), the parameters used to initialize the agent. The dictionary contains:\n",
    "        {\n",
    "            num_params (int): num_params,\n",
    "            num_actions (int): The number of actions,\n",
    "            epsilon (float): The epsilon parameter for exploration,\n",
    "            step_size (float): The step-size,\n",
    "            discount (float): The discount factor,\n",
    "        }\n",
    "        \n",
    "        \"\"\"\n",
    "        self.num_actions = agent_init_info[\"num_actions\"]\n",
    "        self.num_params = agent_init_info[\"num_params\"]\n",
    "        self.epsilon = agent_init_info[\"epsilon\"]\n",
    "        self.step_size = agent_init_info[\"step_size\"]\n",
    "        self.discount = agent_init_info[\"discount\"]\n",
    "        self.theta = np.zeros((self.num_params))\n",
    "        \n",
    "        self.rand_generator = np.random.RandomState(agent_info.get(\"seed\"))\n",
    "\n",
    "        \n",
    "    def agent_start(self, observation):\n",
    "        \"\"\"The first method called when the episode starts, called after\n",
    "        the environment starts.\n",
    "        Args:\n",
    "            observation (Numpy array): the state observation from the\n",
    "                environment's evn_start function.\n",
    "        Returns:\n",
    "            action (int): the first action the agent takes.\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        current_q = observation.dot(self.theta.T)\n",
    "        if self.rand_generator.rand() < self.epsilon:\n",
    "            action = self.rand_generator.randint(self.num_actions)\n",
    "        else:\n",
    "            action = self.argmax(current_q)\n",
    "        self.prev_state = observation\n",
    "        self.prev_action = action\n",
    "        return action\n",
    "    \n",
    "    def agent_step(self, reward, observation):\n",
    "        \"\"\"A step taken by the agent.\n",
    "        Args:\n",
    "            reward (float): the reward received for taking the last action taken\n",
    "            observation (Numpy array): the state observation from the\n",
    "                environment's step based, where the agent ended up after the\n",
    "                last step.\n",
    "        Returns:\n",
    "            action (int): the action the agent is taking.\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        current_q = observation.dot(self.theta.T)\n",
    "        if self.rand_generator.rand() < self.epsilon:\n",
    "            action = self.rand_generator.randint(self.num_actions)\n",
    "        else:\n",
    "            action = self.argmax(current_q)\n",
    "        \n",
    "        self.theta += self.step_size * (reward + self.discount * \\\n",
    "            current_q.max() - self.theta.dot(self.prev_state[self.prev_action].T))*self.prev_state[self.prev_action]\n",
    "        self.prev_state = observation\n",
    "        self.prev_action = action\n",
    "        return action\n",
    "        \n",
    "    \n",
    "    def agent_end(self, reward):\n",
    "        \"\"\"Run when the agent terminates.\n",
    "        Args:\n",
    "            reward (float): the reward the agent received for entering the\n",
    "                terminal state.\n",
    "        \"\"\"\n",
    "        \n",
    "        self.theta += self.step_size * \\\n",
    "            (reward - self.theta.dot(self.prev_state[self.prev_action].T))*self.prev_state[self.prev_action]\n",
    "        \n",
    "    def argmax(self, q_values):\n",
    "        \"\"\"argmax with random tie-breaking\n",
    "        Args:\n",
    "            q_values (float): the array of action-values\n",
    "        \"\"\"\n",
    "        best_actions = np.flatnonzero(q_values == q_values.max())\n",
    "        return self.rand_generator.choice(best_actions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sarsa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sarsa agent\n",
    "class SarsaAgent(agent.BaseAgent):\n",
    "    def agent_init(self, agent_init_info):\n",
    "        \"\"\"Setup for the agent called when the experiment first starts.\n",
    "        \n",
    "        Args:\n",
    "        agent_init_info (dict), the parameters used to initialize the agent. The dictionary contains:\n",
    "        {\n",
    "            num_params (int): The number of states,\n",
    "            num_actions (int): The number of actions,\n",
    "            epsilon (float): The epsilon parameter for exploration,\n",
    "            step_size (float): The step-size,\n",
    "            discount (float): The discount factor,\n",
    "        }\n",
    "        \n",
    "        \"\"\"\n",
    "        \n",
    "        self.num_actions = agent_init_info[\"num_actions\"]\n",
    "        self.num_params = agent_init_info[\"num_params\"]\n",
    "        self.epsilon = agent_init_info[\"epsilon\"]\n",
    "        self.step_size = agent_init_info[\"step_size\"]\n",
    "        self.discount = agent_init_info[\"discount\"]\n",
    "        self.theta = np.zeros((self.num_params))\n",
    "        \n",
    "        self.rand_generator = np.random.RandomState(agent_info.get(\"seed\"))\n",
    "\n",
    "        \n",
    "    def agent_start(self, observation):\n",
    "        \"\"\"The first method called when the episode starts, called after\n",
    "        the environment starts.\n",
    "        Args:\n",
    "            observation (Numpy array): the state observation from the\n",
    "                environment's evn_start function.\n",
    "        Returns:\n",
    "            action (int): the first action the agent takes.\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        current_q = observation.dot(self.theta.T)\n",
    "        if self.rand_generator.rand() < self.epsilon:\n",
    "            action = self.rand_generator.randint(self.num_actions)\n",
    "        else:\n",
    "            action = self.argmax(current_q)\n",
    "        self.prev_state = observation\n",
    "        self.prev_action = action\n",
    "        return action\n",
    "        \n",
    "    \n",
    "    def agent_step(self, reward, observation):\n",
    "        \"\"\"A step taken by the agent.\n",
    "        Args:\n",
    "            reward (float): the reward received for taking the last action taken\n",
    "            observation (Numpy array): the state observation from the\n",
    "                environment's step based, where the agent ended up after the\n",
    "                last step.\n",
    "        Returns:\n",
    "            action (int): the action the agent is taking.\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        current_q = observation.dot(self.theta.T)\n",
    "        if self.rand_generator.rand() < self.epsilon:\n",
    "            action = self.rand_generator.randint(self.num_actions)\n",
    "        else:\n",
    "            action = self.argmax(current_q)\n",
    "        \n",
    "        self.theta += self.step_size * (reward + self.discount * \\\n",
    "            current_q[action] - self.theta.dot(self.prev_state[self.prev_action].T))*self.prev_state[self.prev_action]\n",
    "        self.prev_state = observation\n",
    "        self.prev_action = action\n",
    "        return action\n",
    "        \n",
    "    \n",
    "    def agent_end(self, reward):\n",
    "        \"\"\"Run when the agent terminates.\n",
    "        Args:\n",
    "            reward (float): the reward the agent received for entering the\n",
    "                terminal state.\n",
    "        \"\"\"\n",
    "        \n",
    "        self.theta += self.step_size * \\\n",
    "            (reward - self.theta.dot(self.prev_state[self.prev_action].T))*self.prev_state[self.prev_action]\n",
    "        \n",
    "  \n",
    "    def argmax(self, q_values):\n",
    "        \"\"\"argmax with random tie-breaking\n",
    "        Args:\n",
    "            q_values (float): the array of action-values\n",
    "        \"\"\"\n",
    "        best_actions = np.flatnonzero(q_values == q_values.max())\n",
    "        return self.rand_generator.choice(best_actions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experiment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 1/1 [00:03<00:00,  3.05s/it]\n",
      "100%|██████████| 1/1 [00:02<00:00,  2.86s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Q-learning\n",
      "Q(s,a):\n",
      "[[ 0.26584002 -0.17848127]\n",
      " [ 0.         -0.17848127]\n",
      " [ 0.          0.22310159]\n",
      " [ 0.26584002  0.22310159]]\n",
      "Theta:\n",
      "[-0.22310159  0.26584002]\n",
      "---\n",
      "Sarsa\n",
      "Q(s,a):\n",
      "[[ 0.31008856 -0.4971869 ]\n",
      " [ 0.         -0.4971869 ]\n",
      " [ 0.          0.62148362]\n",
      " [ 0.31008856  0.62148362]]\n",
      "Theta:\n",
      "[-0.62148362  0.31008856]\n",
      "---\n",
      "CPU times: user 5.92 s, sys: 0 ns, total: 5.92 s\n",
      "Wall time: 5.92 s\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "agents = {\n",
    "    \"Q-learning\": QLearningAgent,\n",
    "    \"Sarsa\": SarsaAgent\n",
    "}\n",
    "env = Environment\n",
    "all_thetas = {}\n",
    "all_qs = {}\n",
    "agent_info = {\"num_actions\": 2, \"num_params\": 2, \"epsilon\": 0.5, \"step_size\": 0.001, \"discount\": 1.0}\n",
    "env_info = {}\n",
    "num_runs = 1 # The number of runs\n",
    "num_episodes = 100000 # The number of episodes in each run\n",
    "\n",
    "for algorithm in [\"Q-learning\", \"Sarsa\"]:\n",
    "    all_thetas[algorithm] = []\n",
    "    all_qs[algorithm] = []\n",
    "    for run in tqdm(range(num_runs)):\n",
    "        agent_info[\"seed\"] = run\n",
    "        env_info[\"seed\"] = run\n",
    "        rl_glue = RLGlue(env, agents[algorithm])\n",
    "        rl_glue.rl_init(agent_info, env_info)\n",
    "\n",
    "        for episode in range(num_episodes):\n",
    "            rl_glue.rl_episode(0) \n",
    "            \n",
    "        all_thetas[algorithm].append(rl_glue.agent.theta)\n",
    "        \n",
    "        q = np.zeros((4,2))\n",
    "        for s in range(4):\n",
    "            obs = rl_glue.environment.observation(s)\n",
    "            q[s,:] = obs.dot(rl_glue.agent.theta.T)\n",
    "        all_qs[algorithm].append(q)\n",
    "\n",
    "for algorithm in [\"Q-learning\", \"Sarsa\"]:\n",
    "    print(algorithm)\n",
    "    print('Q(s,a):')\n",
    "    print(np.array(all_qs[algorithm]).mean(axis=0))\n",
    "    print('Theta:')\n",
    "    print(np.array(all_thetas[algorithm]).mean(axis=0))\n",
    "    print('---')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that for Q-learning, Q(S4,A1)>Q(S4,A2) so its policy will choose A1 in S4.\n",
    "\n",
    "The best achievable policy chooses A2 in S4 and matches the action values found by Sarsa."
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}