04_Reinforcement_Learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 强化学习\n",
    "\n",
    "## 强化学习简介\n",
    "- 偏向性学习\n",
    "- 奖励和惩罚\n",
    "- Markov决策过程\n",
    "- game theroy and multi agent interactions\n",
    "- 强化学习的工作流程\n",
    "- 如何评价强化学习的学习结果\n",
    "- 强化学习与先前学习的监督学习、非监督学习的不同点\n",
    "- course project is desing smart car"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Markov 决策过程\n",
    "### 决策与强化学习\n",
    "- 监督学习-函数逼近（拟合）\n",
    "- 非监督学习-聚类描述\n",
    "- 强化学习-类似监督学习，但又有所不同，增强学习是制定的一个机制，其中一个特点是循环\n",
    "- Reinforcement learning is a science of decision making.\n",
    "### 世界\n",
    "- 引入不确定性\n",
    "### Markov决策过程\n",
    "- state\n",
    "- model: physics of world\n",
    "- actions\n",
    "- reward\n",
    "- policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 参考文献：\n",
    "- 下面的笔记源自这份[材料](https://github.com/mpatacchiola/dissecting-reinforcement-learning)。\n",
    "- 补充参考材料[强化学习入门](https://zhuanlan.zhihu.com/sharerl)，该材料参考David Silver的[强化学习视频讲义](https://www.bilibili.com/video/av9930653/?from=search&seid=2152572399658035750)。\n",
    "- [总结文。](https://zhuanlan.zhihu.com/p/27711452)\n",
    "- [强化学习简明教程](http://blog.csdn.net/pi9nc/article/details/27649323)\n",
    "\n",
    "## Dissecting Reinforcement Learning-Part.1\n",
    "\n",
    "### Andrey Markov\n",
    "- systems that follow a chain of linked events.\n",
    "- discrete processes that he called chain.\n",
    "\n",
    "- A Markov Chain has a set of states S={s0,s1,...,sm}\n",
    "- a process that can move successively from one state to another\n",
    "- Each move is a single step and is based on a transition model T\n",
    "\n",
    "**Markov chain is defined by:**\n",
    "\n",
    "1. Set of possible States: S={s0,s1,...,sm}\n",
    "2. Initial State: s0\n",
    "3. Transition Model: T(s,s’)\n",
    "\n",
    "**The Markov property** states that given the present, the future is conditionally independent of the past. namely, the state in which the process is now it is dependent only from the state it was at t−1.\n",
    "\n",
    "Our system is composed of two states and we can model the initial distribution as a vector with two elements, the first element of the vector represents the probability of staying in the state s0 and the second element the probability of staying in state s1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Markov Decision Process\n",
    "- A Markov Decision Process (MDP) is a reinterpretation of Markov chains which includes an agent and a decision making process.\n",
    "\n",
    "A MDP is defined by these components:\n",
    "\n",
    "1. Set of possible States: S={s0,s1,...,sm}\n",
    "2. Initial State: s0\n",
    "3. Set of possible Actions: A={a0,a1,...,an}\n",
    "4. Transition Model: T(s,a,s′)\n",
    "5. Reward Function: R(s)\n",
    "\n",
    "- Problem the agent has to maximise the reward avoiding states which return negative values and choosing the one which return positive values.\n",
    "- Solution find a policy π(s) which returns the action with the highest reward.\n",
    "- optimal policy, denoted by $π^∗$\n",
    "\n",
    "The main characteristics of the world are the following:\n",
    "- Discrete time and space\n",
    "- Fully observable\n",
    "- Infinite horizon\n",
    "- Known Transition Model\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### The Bellman equation\n",
    "The utility(value) of the states history \n",
    "h：\n",
    "$U_h=R(s_0)+\\gamma R(s_1)+\\gamma^2 R(s_2)+...+\\gamma^n R(s_n)$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "the utility of a state s is correlated with the utility of its neighbours at s′ meaning:\n",
    "\n",
    "$ U(s) = R(s)+ \\gamma \\max \\limits_{a}\\sum\\limits_{s'}T(s,a,s')U(s')$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The value iteration algorithm\n",
    "- Our objective is to find the utility (also called value) for each state.\n",
    "- **Bellman update:** calculate the utility of a state using the Bellman equation and we assign it to the state\n",
    "- Applying the Bellman update infinitely often we are **guaranteed to reach an equilibrium.**\n",
    "\n",
    "**stopping criteria**:\n",
    "\n",
    "$||U_{k+1}-U_k||<\\epsilon \\frac{1-\\gamma}{\\gamma}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The policy iteration algorithm\n",
    "- use the policy iteration algorithm to find an optimal policy\n",
    "- Policy iteration is guaranteed to converge and at convergence, the current policy and its utility function are the optimal policy and the optimal utility function.\n",
    "\n",
    "simplified version of the Bellman equation:\n",
    "\n",
    "$ U(s) = R(s)+ \\gamma  \\sum\\limits_{s'}T(s,\\pi(s),s')U(s')$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy evaluation using linear algebra\n",
    "\n",
    "how to reach the same conclusion using a linear algebra approach. In the Bellman equation we have a linear system with n variables and n constraints. Remember that here we are dealing with matrices and vectors. Given a policy p and the action associated to the state s, the reward vector r, the transition matrix T and the discount factor gamma, we can estimate the utility in a single line of code:\n",
    "```python\n",
    "u[s] = np.linalg.solve(np.identity(12) - gamma*T[:,:,p[s]], r)[s]\n",
    "```\n",
    "\n",
    "We can derive this value starting from the simplified Bellman equation:\n",
    "\n",
    "$u=r+\\gamma Tu$\n",
    "\n",
    "$(I-\\gamma T)u=r$\n",
    "\n",
    "$u=(I-\\gamma T)^{-1}r$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dissecting Reinforcement Learning-Part.2\n",
    "\n",
    "### Beyond dynamic programming\n",
    "\n",
    "**model-free reinforcement learning:** In model-free reinforcement learning the first thing we miss is a transition model. **In fact the name model-free stands for transition-model-free.**\n",
    "\n",
    "The second thing we **miss is the reward function R(s)** which gives to the agent the reward associated to a particular state.\n",
    "\n",
    "**Monte Carlo (MC) predition:** In state s the agent always produce the action a given by the policy π. The goal of the agent in passive reinforcement learning is to learn the utility function $U^{\\pi}(s)$.\n",
    "\n",
    "In this case we are in an active case and using the words of Sutton and Burto we will say that we are applying **MC for control estimation.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "To summarise, in the passive case this is what we have:\n",
    "1. Set of possible States: S={s0,s1,...,sm}\n",
    "2. Initial State: s0\n",
    "3. Set of possible Actions: A={a0,a1,...,an}\n",
    "4. The policy π\n",
    "\n",
    "In passive reinforcement learning our objective is to use the available information to estimate the utility function. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first thing the robot can do is to estimate the transition model, moving in the environment and keeping track of the number of times an action has been correctly executed.\n",
    "\n",
    "Once the transition model is available the robot can use either value iteration or policy iteration to get the utility function.\n",
    "\n",
    "The problem of this approach should be evident: **estimating the values of a transition model can be expensive.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Monte Carlo method\n",
    "\n",
    "> The idea behind MC is simple: using randomness to solve problems.\n",
    "\n",
    "In artificial intelligence we can use MC tree search to find the best move in a game.The DeepMind AlphaGo defeated the Go world champion Lee Seedol using MC tree search combined with convolutional networks and deep reinforcement learning.\n",
    "\n",
    "The **advantages of MC methods over the dynamic programming approach are the following:**\n",
    "\n",
    "1. MC allow learning optimal behaviour **directly from interaction** with the environment.\n",
    "2. It is easy and efficient to **focus** MC methods on small subset of the states.\n",
    "3. MC can be used with **simulations** (sample models)\n",
    "\n",
    "At each step it records the reward obtained and saves an history of all the states visited until reaching a terminal state. **We call an episode the sequence of states from the starting state to the terminal state.**\n",
    "\n",
    "Each occurrence of a state during the episode is called **visit.**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python implementation\n",
    "\n",
    "As I told you this is a problem because we cannot estimate those values but at the same time it is an advantage. In a very big grid world **we can estimate the utilities only for the states we are interested in**, saving time and resources and focusing only on a particular subspace of the world."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Monte Carlo control\n",
    "\n",
    "> The MC methods for control (active) are slightly different from MC methods for prediction (passive).\n",
    "\n",
    "In some sense the MC control problem is more realistic because we need to estimate a policy which is not given.\n",
    "\n",
    "**Generalised Policy Iteration or GPI:** The GPI is well explained by the policy iteration algorithm of the first post. The policy iteration allowed finding the utility values for each state and at the same time the optimal policy.\n",
    "\n",
    "The approach we used in policy iteration included two steps:\n",
    "1. Policy evaluation: $U \\rightarrow U^{\\pi}$\n",
    "2. Policy improvement: $\\pi \\rightarrow greedy(U)$\n",
    "\n",
    "The first step makes the utility function consistent with the current policy (**evaluation**). The second step makes the policy $\\pi$ greedy with respect to the current utility function (**improvement**).\n",
    "\n",
    "A greedy algorithm makes the local optimal choice at each step. **In our case greedy means to take for each state the action with the highest utility and update the policy with that action.**\n",
    "\n",
    "How can the greedy strategy work? It works because the local choice is evaluated using the utility function which is adjusted along time. At the beginning the agent will follow many sub-optimal paths but after a while the utilities will start to converge to the true values and the greedy strategy will lead to positive rewards.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Action Values and the Q-function\n",
    "\n",
    "Until now we used the function U called the utility function (aka value function, **state-value function**) as a way to estimate the utility (value) of a state. More precisely we used $U^{\\pi}(s)$ to estimate the value of a state s under a policy $\\pi$.\n",
    "\n",
    "Now it is time to introduce a new function called Q (aka action-value function) and define as follow:\n",
    "\n",
    "$Q^{\\pi}(s, a)=E\\{Return_t|s_t=s, a_t=a\\}$\n",
    "\n",
    "Q-function takes the action a in state s under the policy π and it returns the utility of that state-action pair."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Dissecting Reinforcement Learning-Part.3\n",
    "\n",
    "> 蒙特卡罗的方法使用的是值函数最原始的定义，该方法利用所有回报的累积和估计值函数。DP方法和TD方法则利用一步预测方法计算当前状态值函数。其共同点是利用了bootstrapping方法，不同的是，DP方法利用模型计算后继状态，而TD方法利用试验得到后继状态。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "- **Offline Policy** 游戏开始前就制定好了策略（异步策略），如q-learning中的max(Q(s'))\n",
    "- **Online Policy** 游戏中同步制定的策略，如SARSA中更新部分的Q(s',a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:mlnd]",
   "language": "python",
   "name": "conda-env-mlnd-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}