03. Markov Decision Process and Dynamic Programming/3.12 Value Iteration - Frozen Lake Problem.ipynb · fzhiy/Hands-On-Reinforcement-Learning-With-Python

轻量养虾，开箱即用！低 Token + 稳定算力，Gitee & 模力方舟联合出品的 PocketClaw 正式开售！点击了解详情~

加入 Gitee

与超过 1400万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

文件

该仓库未声明开源许可证文件（LICENSE），使用请关注具体项目描述及其代码上游依赖。

克隆/下载

3.12 Value Iteration - Frozen Lake Problem.ipynb 8.43 KB

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving Frozen Lake Problem Using Value Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Goal:\n",
    "\n",
    "Imagine, there is a frozen lake from your home to office, you should walk on the frozen lake\n",
    "to reach your office. But oops! there will be a hole in the frozen lake in between, so you have\n",
    "to be careful while walking in the frozen lake to avoid getting trapped at holes.\n",
    "Look at the below figure where, \n",
    "\n",
    "1. S is the starting position (Home)\n",
    "2. F is the Frozen lake where you can walk\n",
    "3. H is the Hole which you have to be so careful about\n",
    "4. G is the Goal (office)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](images/B09792_03_50.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Okay, now let us use our agent instead of you to find the correct way to reach the office.\n",
    "The agent goal is to find the optimal path to reach from S to G without getting trapped at H.\n",
    "How an agent can achieve this? We give +1 point as a reward to the agent if it correctly\n",
    "walks on the frozen lake and 0 points if it falls into the hole. So that agent could determine\n",
    "which is the right action. An agent will now try to find the optimal policy. Optimal policy\n",
    "implies taking the correct path which maximizes the agent reward. If the agent is\n",
    "maximizing the reward, apparently agent is learning to skip the hole and reach the\n",
    "destination."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we import necessary libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import gym\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initialize our gym environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[2018-06-01 11:59:38,953] Making new env: FrozenLake-v0\n"
     ]
    }
   ],
   "source": [
    "env = gym.make('FrozenLake-v0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Let us see how the environment looks like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<ipykernel.iostream.OutStream at 0x7f9e82c4e6a0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we define the function called value_iteration which performs value iteraion i.e it returns the optimal value\n",
    "function (value table)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def value_iteration(env, gamma = 1.0):\n",
    "    \n",
    "    # initialize value table with zeros\n",
    "    value_table = np.zeros(env.observation_space.n)\n",
    "    \n",
    "    # set number of iterations and threshold\n",
    "    no_of_iterations = 100000\n",
    "    threshold = 1e-20\n",
    "    \n",
    "    for i in range(no_of_iterations):\n",
    "        \n",
    "        # On each iteration, copy the value table to the updated_value_table\n",
    "        updated_value_table = np.copy(value_table) \n",
    "        \n",
    "        # Now we calculate Q Value for each actions in the state \n",
    "        # and update the value of a state with maximum Q value\n",
    "        \n",
    "        for state in range(env.observation_space.n):\n",
    "            Q_value = []\n",
    "            for action in range(env.action_space.n):\n",
    "                next_states_rewards = []\n",
    "                for next_sr in env.P[state][action]: \n",
    "                    trans_prob, next_state, reward_prob, _ = next_sr \n",
    "                    next_states_rewards.append((trans_prob * (reward_prob + gamma * updated_value_table[next_state]))) \n",
    "                \n",
    "                Q_value.append(np.sum(next_states_rewards))\n",
    "                \n",
    "            value_table[state] = max(Q_value) \n",
    "            \n",
    "        # we will check whether we have reached the convergence i.e whether the difference \n",
    "        # between our value table and updated value table is very small. But how do we know it is very\n",
    "        # small? We set some threshold and then we will see if the difference is less\n",
    "        # than our threshold, if it is less, we break the loop and return the value function as optimal\n",
    "        # value function\n",
    "        \n",
    "        if (np.sum(np.fabs(updated_value_table - value_table)) <= threshold):\n",
    "             print ('Value-iteration converged at iteration# %d.' %(i+1))\n",
    "             break\n",
    "    \n",
    "    return value_table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Now, we define a function called extract policy for extracting optimal policy from the optimal value function. \n",
    "i.e We calculate Q value using our optimal value function and pick up\n",
    "the actions which has the highest Q value for each state as the optimal policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_policy(value_table, gamma = 1.0):\n",
    " \n",
    "    # initialize the policy with zeros\n",
    "    policy = np.zeros(env.observation_space.n) \n",
    "    \n",
    "    \n",
    "    for state in range(env.observation_space.n):\n",
    "        \n",
    "        # initialize the Q table for a state\n",
    "        Q_table = np.zeros(env.action_space.n)\n",
    "        \n",
    "        # compute Q value for all ations in the state\n",
    "        for action in range(env.action_space.n):\n",
    "            for next_sr in env.P[state][action]: \n",
    "                trans_prob, next_state, reward_prob, _ = next_sr \n",
    "                Q_table[action] += (trans_prob * (reward_prob + gamma * value_table[next_state]))\n",
    "        \n",
    "        # select the action which has maximum Q value as an optimal action of the state\n",
    "        policy[state] = np.argmax(Q_table)\n",
    "    \n",
    "    return policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, We compute the optimal value function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value-iteration converged at iteration# 1373.\n"
     ]
    }
   ],
   "source": [
    "optimal_value_function = value_iteration(env=env,gamma=1.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and we derive the optimal policy from the optimal value function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "optimal_policy = extract_policy(optimal_value_function, gamma=1.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 3. 3. 3. 0. 0. 0. 0. 3. 1. 0. 0. 0. 2. 1. 0.]\n"
     ]
    }
   ],
   "source": [
    "print(optimal_policy)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:universe]",
   "language": "python",
   "name": "conda-env-universe-py"
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

一键复制编辑原始数据按行查看历史

提交于 2018-06-12 02:05 +08:00 . added code

马建仓 AI 助手

尝试更多

代码解读

代码找茬

代码优化

https://gitee.com/fzhiy/Hands-On-Reinforcement-Learning-With-Python.git

git@gitee.com:fzhiy/Hands-On-Reinforcement-Learning-With-Python.git

fzhiy

Hands-On-Reinforcement-Learning-With-Python

master

fzhiy/Hands-On-Reinforcement-Learning-With-Python

简介

发行版

贡献者

近期动态

fzhiy/Hands-On-Reinforcement-Learning-With-Python .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

fzhiy/Hands-On-Reinforcement-Learning-With-Python