Report.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Collaboration and Competition\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!pip -q install ./python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The environment is already saved in the Workspace and can be accessed at the file path provided below. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:unityagents:\n",
      "'Academy' started successfully!\n",
      "Unity Academy name: Academy\n",
      "        Number of Brains: 1\n",
      "        Number of External Brains : 1\n",
      "        Lesson number : 0\n",
      "        Reset Parameters :\n",
      "\t\t\n",
      "Unity brain name: TennisBrain\n",
      "        Number of Visual Observations (per agent): 0\n",
      "        Vector Observation space type: continuous\n",
      "        Vector Observation space size (per agent): 8\n",
      "        Number of stacked Vector Observation: 3\n",
      "        Vector Action space type: continuous\n",
      "        Vector Action space size (per agent): 2\n",
      "        Vector Action descriptions: , \n"
     ]
    }
   ],
   "source": [
    "from unityagents import UnityEnvironment\n",
    "import numpy as np\n",
    "\n",
    "env = UnityEnvironment(file_name=\"data/Tennis_Linux_NoVis/Tennis\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Environments contain **_brains_** which are responsible for deciding the actions of their associated agents. Here we check for the first brain available, and set it as the default brain we will be controlling from Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TennisBrain\n"
     ]
    }
   ],
   "source": [
    "# get the default brain\n",
    "brain_name = env.brain_names[0]\n",
    "brain = env.brains[brain_name]\n",
    "print(brain_name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Examine the State and Action Spaces\n",
    "\n",
    "Run the code cell below to print some information about the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of agents: 2\n",
      "Size of each action: 2\n",
      "There are 2 agents. Each observes a state with length: 24\n",
      "The state for the first agent looks like: [ 0.          0.          0.          0.          0.          0.\n",
      "  0.          0.          0.          0.          0.          0.\n",
      "  0.          0.          0.          0.         -6.65278625 -1.5\n",
      " -0.          0.          6.83172083  6.         -0.          0.        ]\n"
     ]
    }
   ],
   "source": [
    "# reset the environment\n",
    "env_info = env.reset(train_mode=True)[brain_name]\n",
    "\n",
    "# number of agents \n",
    "num_agents = len(env_info.agents)\n",
    "print('Number of agents:', num_agents)\n",
    "\n",
    "# size of each action\n",
    "action_size = brain.vector_action_space_size\n",
    "print('Size of each action:', action_size)\n",
    "\n",
    "# examine the state space \n",
    "states = env_info.vector_observations\n",
    "state_size = states.shape[1]\n",
    "print('There are {} agents. Each observes a state with length: {}'.format(states.shape[0], state_size))\n",
    "print('The state for the first agent looks like:', states[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Take Random Actions in the Environment\n",
    "\n",
    "In the next code cell, you will learn how to use the Python API to control the agent and receive feedback from the environment.\n",
    "\n",
    "Note that **in this coding environment, you will not be able to watch the agents while they are training**, and you should set `train_mode=True` to restart the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# for i in range(5):                                         # play game for 5 episodes\n",
    "#     env_info = env.reset(train_mode=False)[brain_name]     # reset the environment    \n",
    "#     states = env_info.vector_observations                  # get the current state (for each agent)\n",
    "#     scores = np.zeros(num_agents)                          # initialize the score (for each agent)\n",
    "#     while True:\n",
    "#         actions = np.random.randn(num_agents, action_size) # select an action (for each agent)\n",
    "#         actions = np.clip(actions, -1, 1)                  # all actions between -1 and 1\n",
    "#         env_info = env.step(actions)[brain_name]           # send all actions to tne environment\n",
    "#         next_states = env_info.vector_observations         # get next state (for each agent)\n",
    "#         rewards = env_info.rewards                         # get reward (for each agent)\n",
    "#         dones = env_info.local_done                        # see if episode finished\n",
    "#         scores += env_info.rewards                         # update the score (for each agent)\n",
    "#         states = next_states                               # roll over states to next time step\n",
    "#         if np.any(dones):                                  # exit loop if episode finished\n",
    "#             break\n",
    "#     print('Total score (averaged over agents) this episode: {}'.format(np.mean(scores)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When finished, you can close the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. It's Your Turn!\n",
    "\n",
    "Now it's your turn to train your own agent to solve the environment!  A few **important notes**:\n",
    "- When training the environment, set `train_mode=True`, so that the line for resetting the environment looks like the following:\n",
    "```python\n",
    "env_info = env.reset(train_mode=True)[brain_name]\n",
    "```\n",
    "- To structure your work, you're welcome to work directly in this Jupyter notebook, or you might like to start over with a new file!  You can see the list of files in the workspace by clicking on **_Jupyter_** in the top left corner of the notebook.\n",
    "- In this coding environment, you will not be able to watch the agents while they are training.  However, **_after training the agents_**, you can download the saved model weights to watch the agents on your own machine! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis of this task\n",
    "\n",
    "I played with the environment using manual input actions to understand the environment. There are several key observations:\n",
    "\n",
    "* There is no or very little momentum on the rackets. The movement of rackets reflects the input action vectors instantly.\n",
    "* In most time the reward is 0 for both agents, and non-zero rewards are only granted occasionally at the steps in which the ball flies over the net or hits the ground (in or out of bounds). In addition, there is a delay from hitting the ball to getting rewards. If the ball goes over the net successfully, it may take 5~8 steps to receive the positive reward. This makes advantage estimation hard in actor-critic paradigm because we expect the actor to receive proper guidance when hitting the ball (especially for the steps right before it).\n",
    "* The two agents are mostly in collaboration. The punishment of missing the ball is very small (-0.01) compared to hitting the ball over the net (+0.1). For each agent, if its opponent misses the ball, it stops from getting more rewards. There is very little competition.\n",
    "\n",
    "### Algorithm and optimization strategies\n",
    "\n",
    "##### Multi-agent deep deterministic policy gradient\n",
    "\n",
    "To solve this task I implemented the multi-agent deep deterministic policy gradient (MADDPG) algorithm described in the paper [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://arxiv.org/pdf/1706.02275.pdf). In this paper the algorithm is described as following:\n",
    "\n",
    "![MADDPG](img/maddpg.png)\n",
    "\n",
    "In this model the actors are feed-forward networks with 3 hidden layers, each layer with 256 hidden unites. The activation function for the hidden layers is `ReLU` and the activation function for the output layer is `tanh`. `tanh` activation provides more nonlinearity and normalizes the output action to (-1, 1). The critics are feed-forward networks with 3 hidden layers, each layer with 512 hidden units. The hidden layers has `ReLU` as activation and the output layer doesn't have activation. The weights of the networks are initialized as orthogonal vectors (with `nn.init.orthogonal_`) and multipled by a scaling factor (0.1 in the final run).\n",
    "\n",
    "With the stats from `torchsummary`, each actor network has 138,498 parameters and each critic network has 552,961 parameters. \n",
    "\n",
    "My actual implementation is a little different from the one described in the paper, in order to apply other strategies at the same time. These differences will be covered in the following sections.\n",
    "\n",
    "##### Generalized advantage estimation\n",
    "\n",
    "The Generialized advantage estimation (GAE) is described in paper [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://arxiv.org/pdf/1506.02438.pdf). In this task, for most steps the agents get zero rewards and there is an obvious delay between the meaningful action (the racket hits the ball) and the non-zero rewards (the ball flies over the net or hits the ground). One potential way is the N-step estimation, but considering the number of steps in the delay is not constant (5~8 steps in good case, could be longer), we directly go with GAE.\n",
    "\n",
    "In the implementation, the experiences are not recorded each step. Instead, after a whole episode, a smoothed version of the rewards are calculated and put into the replay buffers. With a hyper-parameter $\\lambda$, for each agent, the smoothed reward at step $i$ is calculated as\n",
    "\n",
    "$r^{smooth}_{i} = r_i + \\lambda r_{i+1} + \\lambda^2 r_{i+2} + ... = \\sum_{k=i}^{N} \\lambda^{k-i} r_{k} $\n",
    "\n",
    "Then in the experience replay we don't need to change anything to get the same results as GAE. One drawback of this implementation strategy is that the experiences only updated after the whole episode is done, in other words, the replayed experiences are all from previous episodes but not the current episodes. This shouldn't be a big issue since DDPG is already an off-policy algorithm. And the experiences from the same episode is very unlikely to be sampled because of long historical experiences.\n",
    "\n",
    "In the final training we set the $\\lambda$ as 0.8. A non-zero reward contributes $0.8^5 \\approx 32.8\\%$ of its value to the smoothed reward 5 steps earlier, $0.8^{10} \\approx 10.7\\%$ to 10 steps earlier, and $0.8^{15} \\approx 3.5\\%$ to 15 steps earlier (almost ignorable if there is another non-zero reward 15 steps earlier).\n",
    "\n",
    "\n",
    "##### Prioritized experience replay\n",
    "\n",
    "The prioritized experience replay (PER) described in the paper [Prioritized Experience Replay](https://arxiv.org/pdf/1511.05952.pdf) is applied to train the agents more reliably. In the early exploration period, in most of time the racket doesn't hit the ball. As a proof, in the warmup steps with random actions, the average reward over 100 episodes is less than 0.03. That means on average the agents hit the ball less than 0.3 times in each episode, making most of experiences less worthy of learning from. We hope to update the agents with experiences around the step when the racket hits the ball (either by the agent itself or its opponent). The assumption is that each time when the racket hits the ball (or at least when the ball is near to the racket), there is a larger TD error that makes the corresponding experiences worthy of learning.\n",
    "\n",
    "In this solution I borrowed the implementation of PER from [rlcode/per](https://github.com/rlcode/per) project. To make it simpler I only used the prioritized sampling results but ignored the weights of samples calculated from probabilities (otherwise I will need to change the DDPG implementation). In the multi-agent setting, I use the sum of absolute values of TD errors from all agents. This requires change to the MADDPG algorithm. In the original algorithm, a batch of experiences are sampled and replayed independently when updating *each* agent. In my implementation a batch of experiences are sampled once and used to update *all* agents. After updating all agents and collecting their corresponding TD errors, the priorities of the sampled experiences are updated accordingly.\n",
    "\n",
    "\n",
    "This strategy very important. I made some lazy tries with similar intuition but they didn't work. These failed attempts include (1) adding the episode to memory only if there is positive reward granted, and (2) using a relatively small heap to store the experiences with largest TD-errors. PER is much more effective than these simple hacks.\n",
    "\n",
    "##### Other attempts\n",
    "\n",
    "I also tried some other strategies during the development but they didn't work at that time. Probably it is because my implementation was buggy, or I just didn't find the proper combination of hyper parameters.\n",
    "\n",
    "* Action repeat. Since the velocities are already in the states and the environment does not involve the momentum, high order relations between adjacent states doesn't seem to helpful. I tried 2 and 3 but they didn't improve the training stability or final performance. In the final run I set it back to 1, meaning that each action is only taken once.\n",
    "\n",
    "* Learning intervals and batch sizes. It seems it's quite normal that there is a period of time when the agents perform very bad with 0 reward over hundreds of episodes. I thought it was because the networks are updated too frequently (the gradients are already clipped), or the small batches of replayed experiences brought too much variance. I tried to update the networks less frequently with larget batches (e.g. update every 16 step with batch size of 1024). But this didn't change the trajectory.\n",
    "\n",
    "* Batch normalization on the input vector. For the critics, the action range is (-1, 1) but the observations can reach (0, 8). However this didn't help. Maybe this is still not a large different.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The script to train the agents is located at `test_agents.py`. In this report we will only take a look at the hyperparam configurations. The configurations and hyper-parameters are copied in the following block with detailed comments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "config = {\n",
    "    # Configs about the env.\n",
    "    'agent_num': 2,\n",
    "    'state_size': 24,\n",
    "    'action_size': 2,\n",
    "    'out_low': -1.,\n",
    "    'out_high': 1.,\n",
    "    \n",
    "    # Configs for the individual DDPG agent.\n",
    "    # The coefficient in soft update of target networks.\n",
    "    'tau': 3e-4,\n",
    "    # The estimation discount.\n",
    "    'gamma': 0.98,\n",
    "    # The scaling factor for the initial network weights.\n",
    "    'init_weight_scale': .1,\n",
    "    # Clip the gradient in each updating step.\n",
    "    'grad_clip': 1.,\n",
    "    # The actor network has 3 hidden layers each with 256 units.\n",
    "    'actor_hidden': [256, 256, 256],\n",
    "    # The initial learning rate for Adam optimizer for actor networks.\n",
    "    'actor_lr': 1e-4,\n",
    "    # The critic network has 3 hidden layers each with 512 units.\n",
    "    'critic_hidden': [512, 512, 512],\n",
    "    # The initial learning rate for Adam optimizer for critic networks.\n",
    "    'critic_lr': 1e-4,\n",
    "    # The repeat times of each action. I tried 2 and 3 but they didn't help\n",
    "    # so just set it as 1, i.e. do not repeat actions.\n",
    "    'action_repeat': 1,\n",
    "    \n",
    "    # Configs for the training process.\n",
    "    # The discount of OU noise. After about 92k steps the noise factor\n",
    "    # is reduced to less 1%.\n",
    "    'noise_discount': 0.99995,\n",
    "    # The seed for all random processes.\n",
    "    'seed': 1317317,\n",
    "    # The size of replay buffer.\n",
    "    'buffer_size': int(1e5),\n",
    "    # The batch size of each update.\n",
    "    'batch_num': 32,\n",
    "    # The lambda in generalized advantage estimation. I also tried 0.9\n",
    "    # but it was too large and the final performance was not good enough.\n",
    "    'lambda_return': 0.8,\n",
    "    \n",
    "    # The directory to save the best model.\n",
    "    'model_dir': './saved_model',\n",
    "    # The maximum episode number for training. Actually I early stopped the\n",
    "    # training process so it didn't make any difference.\n",
    "    'max_episode_num': 1e6,\n",
    "    # The maximum step number for training. Actually I early stopped the\n",
    "    # training process so it didn't make any difference.\n",
    "    'max_step_num': 1e8,\n",
    "    # The step interval to update the model. No interval by setting as 1.\n",
    "    'learn_interval': 1,\n",
    "    # The number of warmup steps with purely random actions.\n",
    "    'warmup_step': 10000,\n",
    "    \n",
    "    # Configs for logging.\n",
    "    'log_file': './log.pickle',\n",
    "    'window_size': 100,\n",
    "    'log_interval': 100,\n",
    "    'tensorboard_log_dir': './tblog',\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The results\n",
    "\n",
    "Finally it comes to the exciting part. The following figure shows the average rewards over 100 consecutive episodes. The figure is generated by tensorboard with no smoothing. The horizontal axis stands for the number of episodes.\n",
    "\n",
    "![rewards](img/rewards.png)\n",
    "\n",
    "After training for ~23 minutes the average rewards go above 0.5 at about 2000 episodes, or 80k steps. Then in the next 7 hours the reward fluctuates between 0.6 and 1.8. Note that the number of episodes is far not linear with wall time. Higher reward means longer episodes and longer training time per episode. I also kept a screenshot of the first 2300 episodes:\n",
    "\n",
    "![early rewards](img/early_rewards.png)\n",
    "\n",
    "After the warmup with slightly positive average reward between 0.015 to 0.025, the model performance drops to zero for a while and then suddenly learned to hit the ball (the average reward goes above 0.1), and then hit the ball multiple times (the average reward rockets to 0.9).\n",
    "\n",
    "The model performance does not reach a stable point, probably due to the nature of multi-agent setting. However the policy loss (the reverse of advantage) seems to come to a stable status. The following figure shows the policy losses of two agents over the steps. The figure is generated by tensorboard with smoothing factor of 0.9, and the horizontal axis stands for the number of steps. From the figure we can see that the two agents have very similar losses and they become stable after ~600k steps. However in later stages one of them starts to outperform the other, maybe this explains the fluctuation of the overall reward. \n",
    "\n",
    "![policy loss](img/policy_loss_smooth_09.png)\n",
    "\n",
    "Unlike the rewards and policy losses, the estimation losses of critics do not show any clear trends. The following figure shows the estimation losses of the two agents (sorry the colors are similar and hard to distinguish). This figure is generated by tensorboard, similar to the policy losses, with smoothing factor of 0.9 and number of steps as horizontal axis.\n",
    "\n",
    "![critic_loss](img/critic_loss_smooth_09.png)\n",
    "\n",
    "\n",
    "### Potential improvements\n",
    "\n",
    "In this solution there are many hyper-parameters and tuning them is a big challenge. With properly tuned parameters the agents may learn faster and reach to better performance.\n",
    "\n",
    "* The final performance is sensitive to $\\lambda$ in GAE which decides the trade-off between bias and variance for advantage estimation. I tried 0.9 but it was too large and brought too high bias; the final performance was about (0.3, 0.5).\n",
    "\n",
    "* I didn't paid too much attention to the network structures, just picked a reasonably large model. Maybe we can add more nonlinearity and reduce the model size to prevent over-fitting.\n",
    "\n",
    "* For the optimization, the agents may learn faster with higher learning rates and gradient clips.\n",
    "\n",
    "Besides parameter tuning, there are some other strategies that may help.\n",
    "\n",
    "* Use different initial weights of agents. In my implementation the networks of agents are initialized in the identical way. Probably if they are initialized with different values the early exploration phase could be more efficient.\n",
    "\n",
    "* Smoothing the reward of one agent with the reward of its opponent. Considering there is almost no competition between the two agents, intuitively, if an agent hits the ball in a way that makes its opponent easier to hit it back, it should receive some positive reward, to encourage more collaboration. Probably this could help to make the final performance more stable.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "drlnd",
   "language": "python",
   "name": "drlnd"
  },
  "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}