第4章-动态规划算法.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1649954819944,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "oXP3ykOT95VF"
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "\n",
    "class CliffWalkingEnv:\n",
    "    \"\"\" 悬崖漫步环境\"\"\"\n",
    "    def __init__(self, ncol=12, nrow=4):\n",
    "        self.ncol = ncol  # 定义网格世界的列\n",
    "        self.nrow = nrow  # 定义网格世界的行\n",
    "        # 转移矩阵P[state][action] = [(p, next_state, reward, done)]包含下一个状态和奖励\n",
    "        self.P = self.createP()\n",
    "\n",
    "    def createP(self):\n",
    "        # 初始化\n",
    "        P = [[[] for j in range(4)] for i in range(self.nrow * self.ncol)]\n",
    "        # 4种动作, change[0]:上,change[1]:下, change[2]:左, change[3]:右。坐标系原点(0,0)\n",
    "        # 定义在左上角\n",
    "        change = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n",
    "        for i in range(self.nrow):\n",
    "            for j in range(self.ncol):\n",
    "                for a in range(4):\n",
    "                    # 位置在悬崖或者目标状态,因为无法继续交互,任何动作奖励都为0\n",
    "                    if i == self.nrow - 1 and j > 0:\n",
    "                        P[i * self.ncol + j][a] = [(1, i * self.ncol + j, 0,\n",
    "                                                    True)]\n",
    "                        continue\n",
    "                    # 其他位置\n",
    "                    next_x = min(self.ncol - 1, max(0, j + change[a][0]))\n",
    "                    next_y = min(self.nrow - 1, max(0, i + change[a][1]))\n",
    "                    next_state = next_y * self.ncol + next_x\n",
    "                    reward = -1\n",
    "                    done = False\n",
    "                    # 下一个位置在悬崖或者终点\n",
    "                    if next_y == self.nrow - 1 and next_x > 0:\n",
    "                        done = True\n",
    "                        if next_x != self.ncol - 1:  # 下一个位置在悬崖\n",
    "                            reward = -100\n",
    "                    P[i * self.ncol + j][a] = [(1, next_state, reward, done)]\n",
    "        return P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "executionInfo": {
     "elapsed": 2012,
     "status": "ok",
     "timestamp": 1649954830279,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "N95QAxfi95VJ"
   },
   "outputs": [],
   "source": [
    "class PolicyIteration:\n",
    "    \"\"\" 策略迭代算法 \"\"\"\n",
    "    def __init__(self, env, theta, gamma):\n",
    "        self.env = env\n",
    "        self.v = [0] * self.env.ncol * self.env.nrow  # 初始化价值为0\n",
    "        self.pi = [[0.25, 0.25, 0.25, 0.25]\n",
    "                   for i in range(self.env.ncol * self.env.nrow)]  # 初始化为均匀随机策略\n",
    "        self.theta = theta  # 策略评估收敛阈值\n",
    "        self.gamma = gamma  # 折扣因子\n",
    "\n",
    "    def policy_evaluation(self):  # 策略评估\n",
    "        cnt = 1  # 计数器\n",
    "        while 1:\n",
    "            max_diff = 0\n",
    "            new_v = [0] * self.env.ncol * self.env.nrow\n",
    "            for s in range(self.env.ncol * self.env.nrow):\n",
    "                qsa_list = []  # 开始计算状态s下的所有Q(s,a)价值\n",
    "                for a in range(4):\n",
    "                    qsa = 0\n",
    "                    for res in self.env.P[s][a]:\n",
    "                        p, next_state, r, done = res\n",
    "                        qsa += p * (r + self.gamma * self.v[next_state] *\n",
    "                                    (1 - done))\n",
    "                        # 本章环境比较特殊,奖励和下一个状态有关,所以需要和状态转移概率相乘\n",
    "                    qsa_list.append(self.pi[s][a] * qsa)\n",
    "                new_v[s] = sum(qsa_list)  # 状态价值函数和动作价值函数之间的关系\n",
    "                max_diff = max(max_diff, abs(new_v[s] - self.v[s]))\n",
    "            self.v = new_v\n",
    "            if max_diff < self.theta: break  # 满足收敛条件,退出评估迭代\n",
    "            cnt += 1\n",
    "        print(\"策略评估进行%d轮后完成\" % cnt)\n",
    "\n",
    "    def policy_improvement(self):  # 策略提升\n",
    "        for s in range(self.env.nrow * self.env.ncol):\n",
    "            qsa_list = []\n",
    "            for a in range(4):\n",
    "                qsa = 0\n",
    "                for res in self.env.P[s][a]:\n",
    "                    p, next_state, r, done = res\n",
    "                    qsa += p * (r + self.gamma * self.v[next_state] *\n",
    "                                (1 - done))\n",
    "                qsa_list.append(qsa)\n",
    "            maxq = max(qsa_list)\n",
    "            cntq = qsa_list.count(maxq)  # 计算有几个动作得到了最大的Q值\n",
    "            # 让这些动作均分概率\n",
    "            self.pi[s] = [1 / cntq if q == maxq else 0 for q in qsa_list]\n",
    "        print(\"策略提升完成\")\n",
    "        return self.pi\n",
    "\n",
    "    def policy_iteration(self):  # 策略迭代\n",
    "        while 1:\n",
    "            self.policy_evaluation()\n",
    "            old_pi = copy.deepcopy(self.pi)  # 将列表进行深拷贝,方便接下来进行比较\n",
    "            new_pi = self.policy_improvement()\n",
    "            if old_pi == new_pi: break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1649954831712,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "yZCGJazo95VK",
    "outputId": "c84ef7a4-7c75-42f6-92ec-bf0c3e4ea167"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "策略评估进行60轮后完成\n",
      "策略提升完成\n",
      "策略评估进行72轮后完成\n",
      "策略提升完成\n",
      "策略评估进行44轮后完成\n",
      "策略提升完成\n",
      "策略评估进行12轮后完成\n",
      "策略提升完成\n",
      "策略评估进行1轮后完成\n",
      "策略提升完成\n",
      "状态价值：\n",
      "-7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 \n",
      "-7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 \n",
      "-7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000 \n",
      "-7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 \n",
      "策略：\n",
      "ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo \n",
      "ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo \n",
      "ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo \n",
      "^ooo **** **** **** **** **** **** **** **** **** **** EEEE \n"
     ]
    }
   ],
   "source": [
    "def print_agent(agent, action_meaning, disaster=[], end=[]):\n",
    "    print(\"状态价值：\")\n",
    "    for i in range(agent.env.nrow):\n",
    "        for j in range(agent.env.ncol):\n",
    "            # 为了输出美观,保持输出6个字符\n",
    "            print('%6.6s' % ('%.3f' % agent.v[i * agent.env.ncol + j]),\n",
    "                  end=' ')\n",
    "        print()\n",
    "\n",
    "    print(\"策略：\")\n",
    "    for i in range(agent.env.nrow):\n",
    "        for j in range(agent.env.ncol):\n",
    "            # 一些特殊的状态,例如悬崖漫步中的悬崖\n",
    "            if (i * agent.env.ncol + j) in disaster:\n",
    "                print('****', end=' ')\n",
    "            elif (i * agent.env.ncol + j) in end:  # 目标状态\n",
    "                print('EEEE', end=' ')\n",
    "            else:\n",
    "                a = agent.pi[i * agent.env.ncol + j]\n",
    "                pi_str = ''\n",
    "                for k in range(len(action_meaning)):\n",
    "                    pi_str += action_meaning[k] if a[k] > 0 else 'o'\n",
    "                print(pi_str, end=' ')\n",
    "        print()\n",
    "\n",
    "\n",
    "env = CliffWalkingEnv()\n",
    "action_meaning = ['^', 'v', '<', '>']\n",
    "theta = 0.001\n",
    "gamma = 0.9\n",
    "agent = PolicyIteration(env, theta, gamma)\n",
    "agent.policy_iteration()\n",
    "print_agent(agent, action_meaning, list(range(37, 47)), [47])\n",
    "\n",
    "# 策略评估进行60轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行72轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行44轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行12轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行1轮后完成\n",
    "# 策略提升完成\n",
    "# 状态价值：\n",
    "# -7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710\n",
    "# -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900\n",
    "# -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000\n",
    "# -7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000\n",
    "# 策略：\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo\n",
    "# ^ooo **** **** **** **** **** **** **** **** **** **** EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "executionInfo": {
     "elapsed": 3,
     "status": "ok",
     "timestamp": 1649954834592,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "qs8Xd7LI95VL"
   },
   "outputs": [],
   "source": [
    "class ValueIteration:\n",
    "    \"\"\" 价值迭代算法 \"\"\"\n",
    "    def __init__(self, env, theta, gamma):\n",
    "        self.env = env\n",
    "        self.v = [0] * self.env.ncol * self.env.nrow  # 初始化价值为0\n",
    "        self.theta = theta  # 价值收敛阈值\n",
    "        self.gamma = gamma\n",
    "        # 价值迭代结束后得到的策略\n",
    "        self.pi = [None for i in range(self.env.ncol * self.env.nrow)]\n",
    "\n",
    "    def value_iteration(self):\n",
    "        cnt = 0\n",
    "        while 1:\n",
    "            max_diff = 0\n",
    "            new_v = [0] * self.env.ncol * self.env.nrow\n",
    "            for s in range(self.env.ncol * self.env.nrow):\n",
    "                qsa_list = []  # 开始计算状态s下的所有Q(s,a)价值\n",
    "                for a in range(4):\n",
    "                    qsa = 0\n",
    "                    for res in self.env.P[s][a]:\n",
    "                        p, next_state, r, done = res\n",
    "                        qsa += p * (r + self.gamma * self.v[next_state] *\n",
    "                                    (1 - done))\n",
    "                    qsa_list.append(qsa)  # 这一行和下一行代码是价值迭代和策略迭代的主要区别\n",
    "                new_v[s] = max(qsa_list)\n",
    "                max_diff = max(max_diff, abs(new_v[s] - self.v[s]))\n",
    "            self.v = new_v\n",
    "            if max_diff < self.theta: break  # 满足收敛条件,退出评估迭代\n",
    "            cnt += 1\n",
    "        print(\"价值迭代一共进行%d轮\" % cnt)\n",
    "        self.get_policy()\n",
    "\n",
    "    def get_policy(self):  # 根据价值函数导出一个贪婪策略\n",
    "        for s in range(self.env.nrow * self.env.ncol):\n",
    "            qsa_list = []\n",
    "            for a in range(4):\n",
    "                qsa = 0\n",
    "                for res in self.env.P[s][a]:\n",
    "                    p, next_state, r, done = res\n",
    "                    qsa += p * (r + self.gamma * self.v[next_state] * (1 - done))\n",
    "                qsa_list.append(qsa)\n",
    "            maxq = max(qsa_list)\n",
    "            cntq = qsa_list.count(maxq)  # 计算有几个动作得到了最大的Q值\n",
    "            # 让这些动作均分概率\n",
    "            self.pi[s] = [1 / cntq if q == maxq else 0 for q in qsa_list]\n",
    "\n",
    "\n",
    "# env = CliffWalkingEnv()\n",
    "# action_meaning = ['^', 'v', '<', '>']\n",
    "# theta = 0.001\n",
    "# gamma = 0.9\n",
    "# agent = ValueIteration(env, theta, gamma)\n",
    "# agent.value_iteration()\n",
    "# print_agent(agent, action_meaning, list(range(37, 47)), [47])\n",
    "\n",
    "# 价值迭代一共进行14轮\n",
    "# 状态价值：\n",
    "# -7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710\n",
    "# -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900\n",
    "# -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000\n",
    "# -7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000\n",
    "# 策略：\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo\n",
    "# ^ooo **** **** **** **** **** **** **** **** **** **** EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 3,
     "status": "ok",
     "timestamp": 1649954837446,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "2ZFlb2dB95VM",
    "outputId": "0d4f2c7a-3589-4bb1-f95a-e9e4696d6201"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "冰洞的索引: {11, 12, 5, 7}\n",
      "目标的索引: {15}\n",
      "[(0.3333333333333333, 10, 0.0, False), (0.3333333333333333, 13, 0.0, False), (0.3333333333333333, 14, 0.0, False)]\n",
      "[(0.3333333333333333, 13, 0.0, False), (0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True)]\n",
      "[(0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False)]\n",
      "[(0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False), (0.3333333333333333, 13, 0.0, False)]\n"
     ]
    }
   ],
   "source": [
    "import gym\n",
    "env = gym.make(\"FrozenLake-v0\")  # 创建环境\n",
    "env = env.unwrapped  # 解封装才能访问状态转移矩阵P\n",
    "env.render()  # 环境渲染,通常是弹窗显示或打印出可视化的环境\n",
    "\n",
    "holes = set()\n",
    "ends = set()\n",
    "for s in env.P:\n",
    "    for a in env.P[s]:\n",
    "        for s_ in env.P[s][a]:\n",
    "            if s_[2] == 1.0:  # 获得奖励为1,代表是目标\n",
    "                ends.add(s_[1])\n",
    "            if s_[3] == True:\n",
    "                holes.add(s_[1])\n",
    "holes = holes - ends\n",
    "print(\"冰洞的索引:\", holes)\n",
    "print(\"目标的索引:\", ends)\n",
    "\n",
    "for a in env.P[14]:  # 查看目标左边一格的状态转移信息\n",
    "    print(env.P[14][a])\n",
    "\n",
    "# SFFF\n",
    "# FHFH\n",
    "# FFFH\n",
    "# HFFG\n",
    "# 冰洞的索引: {11, 12, 5, 7}\n",
    "# 目标的索引: {15}\n",
    "# [(0.3333333333333333, 10, 0.0, False), (0.3333333333333333, 13, 0.0, False),\n",
    "#  (0.3333333333333333, 14, 0.0, False)]\n",
    "# [(0.3333333333333333, 13, 0.0, False), (0.3333333333333333, 14, 0.0, False),\n",
    "#  (0.3333333333333333, 15, 1.0, True)]\n",
    "# [(0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True),\n",
    "#  (0.3333333333333333, 10, 0.0, False)]\n",
    "# [(0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False),\n",
    "#  (0.3333333333333333, 13, 0.0, False)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 7,
     "status": "ok",
     "timestamp": 1649954839116,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "4gf_IaeZ95VM",
    "outputId": "20ba5b95-4481-4b40-8015-54ea7fa0c2cb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "策略评估进行25轮后完成\n",
      "策略提升完成\n",
      "策略评估进行58轮后完成\n",
      "策略提升完成\n",
      "状态价值：\n",
      " 0.069  0.061  0.074  0.056 \n",
      " 0.092  0.000  0.112  0.000 \n",
      " 0.145  0.247  0.300  0.000 \n",
      " 0.000  0.380  0.639  0.000 \n",
      "策略：\n",
      "<ooo ooo^ <ooo ooo^ \n",
      "<ooo **** <o>o **** \n",
      "ooo^ ovoo <ooo **** \n",
      "**** oo>o ovoo EEEE \n"
     ]
    }
   ],
   "source": [
    "# 这个动作意义是Gym库针对冰湖环境事先规定好的\n",
    "action_meaning = ['<', 'v', '>', '^']\n",
    "theta = 1e-5\n",
    "gamma = 0.9\n",
    "agent = PolicyIteration(env, theta, gamma)\n",
    "agent.policy_iteration()\n",
    "print_agent(agent, action_meaning, [5, 7, 11, 12], [15])\n",
    "\n",
    "# 策略评估进行25轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行58轮后完成\n",
    "# 策略提升完成\n",
    "# 状态价值：\n",
    "#  0.069  0.061  0.074  0.056\n",
    "#  0.092  0.000  0.112  0.000\n",
    "#  0.145  0.247  0.300  0.000\n",
    "#  0.000  0.380  0.639  0.000\n",
    "# 策略：\n",
    "# <ooo ooo^ <ooo ooo^\n",
    "# <ooo **** <o>o ****\n",
    "# ooo^ ovoo <ooo ****\n",
    "# **** oo>o ovoo EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6,
     "status": "ok",
     "timestamp": 1649954839117,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "cqPm4jxd95VN",
    "outputId": "ab6bdc64-5a4a-47f0-c6af-08bf4c2aeb0f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "价值迭代一共进行60轮\n",
      "状态价值：\n",
      " 0.069  0.061  0.074  0.056 \n",
      " 0.092  0.000  0.112  0.000 \n",
      " 0.145  0.247  0.300  0.000 \n",
      " 0.000  0.380  0.639  0.000 \n",
      "策略：\n",
      "<ooo ooo^ <ooo ooo^ \n",
      "<ooo **** <o>o **** \n",
      "ooo^ ovoo <ooo **** \n",
      "**** oo>o ovoo EEEE \n"
     ]
    }
   ],
   "source": [
    "action_meaning = ['<', 'v', '>', '^']\n",
    "theta = 1e-5\n",
    "gamma = 0.9\n",
    "agent = ValueIteration(env, theta, gamma)\n",
    "agent.value_iteration()\n",
    "print_agent(agent, action_meaning, [5, 7, 11, 12], [15])\n",
    "\n",
    "# 价值迭代一共进行60轮\n",
    "# 状态价值：\n",
    "#  0.069  0.061  0.074  0.056\n",
    "#  0.092  0.000  0.112  0.000\n",
    "#  0.145  0.247  0.300  0.000\n",
    "#  0.000  0.380  0.639  0.000\n",
    "# 策略：\n",
    "# <ooo ooo^ <ooo ooo^\n",
    "# <ooo **** <o>o ****\n",
    "# ooo^ ovoo <ooo ****\n",
    "# **** oo>o ovoo EEEE"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "第4章-动态规划算法.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}