frozenlake-part2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  FrozenLake\n",
    "Today you are going to learn how to survive walking over the (virtual) frozen lake through discrete optimization.\n",
    "\n",
    "<img src=\"http://vignette2.wikia.nocookie.net/riseoftheguardians/images/4/4c/Jack's_little_sister_on_the_ice.jpg/revision/latest?cb=20141218030206\" alt=\"a random image to attract attention\" style=\"width: 400px;\"/>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import gym\n",
    "\n",
    "#create a single game instance\n",
    "env = gym.make(\"FrozenLake-v0\")\n",
    "\n",
    "#start new game\n",
    "env.reset();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# display the game state\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### legend\n",
    "\n",
    "![img](https://cdn-images-1.medium.com/max/800/1*MCjDzR-wfMMkS0rPqXSmKw.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gym interface\n",
    "\n",
    "The three main methods of an environment are\n",
    "* __reset()__ - reset environment to initial state, _return first observation_\n",
    "* __render()__ - show current environment state (a more colorful version :) )\n",
    "* __step(a)__ - commit action __a__ and return (new observation, reward, is done, info)\n",
    " * _new observation_ - an observation right after commiting the action __a__\n",
    " * _reward_ - a number representing your reward for commiting action __a__\n",
    " * _is done_ - True if the MDP has just finished, False if still in progress\n",
    " * _info_ - some auxilary stuff about what just happened. Ignore it for now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print \"initial observation code:\",env.reset()\n",
    "print 'printing observation:'\n",
    "env.render()\n",
    "print \"observations:\",env.observation_space, 'n=',env.observation_space.n\n",
    "print \"actions:\",env.action_space, 'n=',env.action_space.n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print \"taking action 2 (right)\"\n",
    "new_obs, reward, is_done, _ = env.step(2)\n",
    "print \"new observation code:\",new_obs\n",
    "print \"reward:\", reward\n",
    "print \"is game over?:\",is_done\n",
    "print \"printing new state:\"\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "action_to_i = {\n",
    "    'left':0,\n",
    "    'down':1,\n",
    "    'right':2,\n",
    "    'up':3\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Play with it\n",
    "* Try walking 5 steps without falling to the (H)ole\n",
    " * Bonus quest - get to the (G)oal\n",
    "* Sometimes your actions will not be executed properly due to slipping over ice\n",
    "* If you fall, call __env.reset()__ to restart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "env.step(action_to_i['up'])\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy\n",
    "\n",
    "* The environment has a 4x4 grid of states (16 total), they are indexed from 0 to 15\n",
    "* From each states there are 4 actions (left,down,right,up), indexed from 0 to 3\n",
    "\n",
    "We need to define agent's policy of picking actions given states. Since we have only 16 disttinct states and 4 actions, we can just store the action for each state in an array.\n",
    "\n",
    "This basically means that any array of 16 integers from 0 to 3 makes a policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def get_random_policy():\n",
    "    \"\"\"\n",
    "    Build a numpy array representing agent policy.\n",
    "    This array must have one element per each of 16 environment states.\n",
    "    Element must be an integer from 0 to 3, representing action\n",
    "    to take from that state.\n",
    "    \"\"\"\n",
    "    return <your code>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(1234)\n",
    "policies = [get_random_policy() for i in range(10**4)]\n",
    "\n",
    "assert all([len(p) == 16 for p in policies]), 'policy length should always be 16'\n",
    "assert np.min(policies) == 0, 'minimal action id should be 0'\n",
    "assert np.max(policies) == 3, 'maximal action id should be 3'\n",
    "action_probas = np.unique(policies,return_counts=True)[-1] /10**4. /16.\n",
    "print \"Action frequencies over 10^4 samples:\",action_probas\n",
    "assert np.allclose(action_probas,[0.25]*4,atol=0.05), \"The policies aren't uniformly random (maybe it's just an extremely bad luck)\"\n",
    "print \"Seems fine!\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's evaluate!\n",
    "* Implement a simple function that runs one game and returns the total reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sample_reward(env,policy,t_max=25):\n",
    "    \"\"\"\n",
    "    Interact with an environment, return sum of all rewards.\n",
    "    If game doesn't end on t_max (e.g. agent walks into a wall), \n",
    "    force end the game and return whatever reward you got so far.\n",
    "    \"\"\"\n",
    "    s = env.reset()\n",
    "    total_reward = 0\n",
    "    \n",
    "    <play & get reward>\n",
    "    return total_reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print \"generating 10^3 sessions...\"\n",
    "rewards = [sample_reward(env,get_random_policy()) for _ in range(10**3)]\n",
    "assert all([type(r) in (int,float) for r in rewards]), 'sample_reward must return a single number'\n",
    "assert all([0 <= r <= 1 for r in rewards]), 'total rewards should be between 0 and 1 for frozenlake'\n",
    "print \"Looks good!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def evaluate(policy,n_times=100):\n",
    "    \"\"\"Run several evaluations and average the score the policy gets.\"\"\"\n",
    "    rewards = <your code>\n",
    "    return np.mean(rewards)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def print_policy(policy):\n",
    "    \"\"\"a function that displays a policy in a human-readable way\"\"\"\n",
    "    lake = \"SFFFFHFHFFFHHFFG\"\n",
    "    \n",
    "    # where to move from each tile\n",
    "    arrows = ['<v>^'[a] for a in policy]\n",
    "    \n",
    "    #draw arrows above S and F only\n",
    "    signs = [arrow if tile in \"SF\" else tile for arrow,tile in zip(arrows,lake)]\n",
    "    \n",
    "    for i in range(0,16,4):\n",
    "        print ' '.join(signs[i:i+4])\n",
    "\n",
    "print \"random policy:\"\n",
    "print_policy(get_random_policy())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Random search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "best_policy = None\n",
    "best_score = -float('inf')\n",
    "\n",
    "from tqdm import tqdm\n",
    "for i in tqdm(range(10000)):\n",
    "    policy = get_random_policy()\n",
    "    score = evaluate(policy)\n",
    "    if score > best_score:\n",
    "        best_score = score\n",
    "        best_policy = policy\n",
    "        print \"New best score:\",score\n",
    "        print \"Best policy:\"\n",
    "        print_policy(best_policy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Genetic algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def crossover(policy1,policy2,p=0.5):\n",
    "    \"\"\"\n",
    "    for each state, with probability p take action from policy1, else policy2\n",
    "    \"\"\"\n",
    "    <your code>\n",
    "    return <your code>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(1234)\n",
    "policies = [crossover(get_random_policy(),get_random_policy()) \n",
    "            for i in range(10**4)]\n",
    "\n",
    "assert all([len(p) == 16 for p in policies]), 'policy length should always be 16'\n",
    "assert np.min(policies) == 0, 'minimal action id should be 0'\n",
    "assert np.max(policies) == 3, 'maximal action id should be 3'\n",
    "print \"Seems fine!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "n_epochs = 100 #how many cycles to make\n",
    "pool_size = 100 #how many policies to maintain\n",
    "n_crossovers = 50 #how many crossovers to make on each step\n",
    "n_mutations = 10 #how many mutations to make on each tick\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print \"initializing...\"\n",
    "pool = <spawn a list of pool_size random policies>\n",
    "pool_scores = <evaluate every policy in the pool, return list of scores>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert type(pool) == type(pool_scores) == list\n",
    "assert len(pool) == len(pool_scores) == pool_size\n",
    "assert all([type(score) in (float,int) for score in pool_scores])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#main loop\n",
    "for epoch in range(n_epochs):\n",
    "    print \"Epoch %s:\"%epoch\n",
    "    \n",
    "    crossovered = <crossover random guys from pool, n_crossovers total>\n",
    "    mutated = <add several new policies at random, n_mutations total>\n",
    "    \n",
    "    assert type(crossovered) == type(mutated) == list\n",
    "    \n",
    "    #evaluate new scores\n",
    "    new_policies = crossovered + mutated\n",
    "    new_scores = <evaluate all of new policies, get a list of scores>\n",
    "    \n",
    "    assert type(new_scores) is list and len(new_scores) == len(new_policies)\n",
    "    \n",
    "    \n",
    "    #add new sessions to the pool\n",
    "    pool = pool + new_policies\n",
    "    pool_scores = pool_scores + new_scores\n",
    "    \n",
    "    #select pool_size best policies\n",
    "    selected_indices = np.argsort(pool_scores)[-pool_size:]\n",
    "    pool = [pool[i] for i in selected_indices]\n",
    "    pool_scores = [pool_scores[i] for i in selected_indices]\n",
    "    \n",
    "    #print the best policy so far (last in ascending score order)\n",
    "    print \"best score:\",pool_scores[-1]\n",
    "    print_policy(pool[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## moar\n",
    "\n",
    "The parameters of the genetic algorithm aren't optimal, try to find something better. (size, crossovers and mutations)\n",
    "\n",
    "Try alternative crossover and mutation strategies\n",
    "* prioritize crossover over higher-scores\n",
    "* only mutate several random actions from existing policy, not the whole.\n",
    "* try to select a more diverse pool, not just best scorers\n",
    "\n",
    "See which combination works best!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}