{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": true
},
"source": [
"Table of Contents
\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Reinforcement Learning "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introduction\n",
"\n",
"\n",
"\"[Reinforcement learning (RL)](https://en.wikipedia.org/wiki/Reinforcement_learning)\" is a very interesting sub-field of Machine Learning. There have been many new developments in RL in the last 5 years. Publication of \"[Deep Q-Networks](https://deepmind.com/research/dqn/)\" from DeepMind in particualr ushered in a new era for RL. An important concept in all RL algorithms is the tradeoff between exploration and exploitation. In this post we will simulate a problem called \"[Multi-armed bandit](https://en.wikipedia.org/wiki/Multi-armed_bandit#The_multi-armed_bandit_model)\" and understand the details of this tradeoff. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Goals of the post\n",
"* Share some good resources on RL.\n",
"* Simulate K-Armed bandit problem\n",
"* Understand the tradeoff between Exploration and Exploitation in RL"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Resources"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are several great resources on RL. Below are some of the best ones I found for practitioners like myself. These are good starting points for understanding the foundations and learning by doing. Richard Sutton and Andrew Barto's \"[second edition](https://www.amazon.com/Reinforcement-Learning-Introduction-Adaptive-Computation/dp/0262039249/ref=sr_1_1_sspa?ie=UTF8&qid=1544374069&sr=8-1-spons&keywords=reinforcement+learning&psc=1)\" is beautifully written. I really like how they provide intuitive explanation of algorithms and the pseudo-code. The pseudo-code is proving to be invaluable when I want to code up an algorithm and understand the details. Andrej Karpathy wrote an \"[excellent post](http://karpathy.github.io/2016/05/31/rl/)\" almost two years ago. It's a great general introduction and also a good starting point for a type of RL aglorithms called Policy gradient methods. Finally I found \"[this](http://rail.eecs.berkeley.edu/deeprlcourse/)\" course from Berkeley that is very recent with full lecture notes and videos available. I have only reviewed one lecture so far, but it looks very promising. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Code**: \n",
"1. All of the code for this post can be found here https://github.com/manifoldai/reinforcement_learning_public\n",
"2. Jupyter notebook corresponding to this blog post can be found at https://github.com/manifoldai/reinforcement_learning_public/blob/master/notebooks/Multi-armed%20bandit.ipynb"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following resources can be helpful in understanding the code.\n",
"Introduction to OpenAI gym can be found here. \n",
"https://www.oreilly.com/learning/introduction-to-reinforcement-learning-and-openai-gym\n",
"\n",
"We will using this library that is built on top of openai gym to simulate 10-armed bandit problem.\n",
"https://github.com/JKCooper2/gym-bandits"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Multi-armed bandit problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## General RL problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before we look at the Multi-armed bandit problem, lets take a quick look at the general RL problem setting. The picture below captures the general RL problem. There are two entities - agent and environment. At time t, the Agent observes state $S_t$ from the environment and also receives a reward $R_t$. The agent then takes an action $A_t$. In response to action $A_t$, the environment provides the next state and reward pair and the process continues. This setup represents what is called a Markov Decision Process. The goal of the agent is to maximize the cumulative reward it receives from the environment. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](\"images/rl_env_agent.png\")
![]()
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The most distinguishing feature of RL compared to supervised learning is that there are no labels associated with actions; there is only reward for each action taken. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Multi-armed bandit problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Multi-armed bandit problem is a simple RL problem. At every time step, the agent can choose one of K actions. The agent tehn receives a reward that is drawn from an unknown (to the agent) probability distribution corresponding to the said action. The goal of the agent is to choose actions such that the total reward received within a certain number of timesteps is maximized. The environements state remains unchanged for all time steps. This simplifies the the problem considerably and makes the successive time steps IID. This can be represented as shown below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](\"images/multi-armed-badit.png\")
![]()
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Where\n",
"$A_t \\in {1,2,3....K}$\n",
"and the reward \n",
"$ \n",
"R_t \\sim \\mathcal{N}(\\mu_k,\\,\\sigma^{2})\\,\n",
"$ where k is the action taken. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can estimate the reward distribution for each action by simulating an agent that takes random actions at every time step. This is shown below for K=10"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The autoreload extension is already loaded. To reload it, use:\n",
" %reload_ext autoreload\n"
]
},
{
"data": {
"text/html": [
""
],
"text/vnd.plotly.v1+html": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# imports\n",
"%load_ext autoreload\n",
"%autoreload 2\n",
"import sys\n",
"sys.path.append(\"../\")\n",
"\n",
"import gym\n",
"import gym_bandits\n",
"import logging\n",
"import numpy as np\n",
"import os\n",
"import pandas as pd\n",
"from dotenv import load_dotenv, find_dotenv\n",
"from src.visualization.visualize import plot_rewards, plot_actions, dist_plots\n",
"from src.models.k_armed_bandit import Agent, play_wrapper\n",
"import plotly.offline as pyoffline\n",
"pyoffline.init_notebook_mode()\n",
"import plotly.plotly"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[33mWARN: Environment '' has deprecated methods '_step' and '_reset' rather than 'step' and 'reset'. Compatibility code invoked. Set _gym_disable_underscore_compat = True to disable this behavior.\u001b[0m\n"
]
},
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"load_dotenv(find_dotenv())\n",
"env = gym.make(\"BanditTenArmedGaussian-v0\")\n",
"env.reset()"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"# epsilon = 1 => Explore at every time step by taking a random action\n",
"agent = Agent(env, 1)\n",
"df = play_wrapper('random agent', env, agent)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our simulation runs for 3000 steps. We can see below our random agent chose the actions approximately evenly."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"scrolled": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" | \n",
" r | \n",
" e | \n",
" random agent avg reward | \n",
"
\n",
" \n",
" | random agent action | \n",
" | \n",
" | \n",
" | \n",
"
\n",
" \n",
" \n",
" \n",
" | 0 | \n",
" 273 | \n",
" 273 | \n",
" 273 | \n",
"
\n",
" \n",
" | 1 | \n",
" 294 | \n",
" 294 | \n",
" 294 | \n",
"
\n",
" \n",
" | 2 | \n",
" 311 | \n",
" 311 | \n",
" 311 | \n",
"
\n",
" \n",
" | 3 | \n",
" 289 | \n",
" 289 | \n",
" 289 | \n",
"
\n",
" \n",
" | 4 | \n",
" 311 | \n",
" 311 | \n",
" 311 | \n",
"
\n",
" \n",
" | 5 | \n",
" 268 | \n",
" 268 | \n",
" 268 | \n",
"
\n",
" \n",
" | 6 | \n",
" 321 | \n",
" 321 | \n",
" 321 | \n",
"
\n",
" \n",
" | 7 | \n",
" 327 | \n",
" 327 | \n",
" 327 | \n",
"
\n",
" \n",
" | 8 | \n",
" 282 | \n",
" 282 | \n",
" 282 | \n",
"
\n",
" \n",
" | 9 | \n",
" 324 | \n",
" 324 | \n",
" 324 | \n",
"
\n",
" \n",
"
\n",
"