序贯决策问题

图示：

马尔科夫决策过程

序贯决策，主要的方法是：马尔科夫决策过程。

一个马尔可夫过程叫：MDP。
一个MDP由一个五元组构成：S A P R r

• S 是所有状态的集合
  

• A 是所有动作的集合
  

• P 是某状态S’在某A‘动作下的转移概率
  
  策略P就是在状态S下做A的概率多大。

• R 是奖励
  

• r 是回报有时候也用G标示（gain）
  

当前状态，当前要做的动作，以及下一个状态，三者共同决定环境反馈给智能体，什么样的R（奖励），通常R是标量函数，返回一个标量，标量对应的向量，向量自带方向标量是一个值。

例如：
王者荣耀：R（还有200点血，施展加血魔法magic1，有400点血）=5
当前要做的动作是：施展加血魔法magic1，就是加血，下一个状态，加血.
这个5是自己认为可以设计的。

回报的概念就是：每个动作执行后，所有的R累加。回报是评估当前MDP的一个得分。

model-free和model-based（有模型的方法和无模型的方法）

什么叫有模型的方法呢？

比如百度地图 能够瞬间给出A到B地点的 最短路径 ，是站在上帝视角上 得到了全局的城市交通数据 然后 直接最短路径求解 。

**无模型的方法，往往是用于不可能站在上帝视角，信息不够全的各种即时策略方法 **

蒙特卡罗法（Monte Carlo）

Monte Carlo 方法 适用于工程学 和各个行业领域 以及数学问题 。

用MC去解决问题 主要有经典的三个步骤：

• 构造概率过程
• 实现从已知概率分布中进行抽样
• 建立各种估计量

例如：

算一个不规则的 2D 面积 。

微积分：

用多个长方形切割开 这个不规则凹封闭曲线
只要长方形的宽足够的短，把各个长方形的面积累加 ，就非常接近这个不规则封闭曲线内部的面积 。

用Monte Carlo

直接拿200粒米 ，随机均匀的撒在方块内（撒出方块的不统计），最后 只要分别统计 在封闭曲线内的米的数量 A 和 在方块内 但是不在曲线内的米B ， 这样 A/ (A+B) = 曲线内面积/方块面积，方块面积* A/ (A+B) = 曲线内面积。

我们以上的方法 用了同样的三个步骤：

• 构造概率过程：已知这样的曲线；
• 从已知概率分布抽样：均匀撒米，统计米的多少；
• 建立估计量：用估计量测算目标面积。

AlphaGo 也用到了MC方法：

先是随机走（均匀撒米）
建立概率分布抽样（匹配棋盘结果，生成蒙特卡罗搜+
建立估计量：得到比较好的决策依据

MC方法特别适合 没有明显规律 或者规律很复杂 没有解析解的问题

on-policy off-policy

区分的方式就是：

on-policy ：agent(智能体）从环境学习的策略和它与环境交互的策略，一样。

off-policy：agent（智能体）从环境学习的策略和它与环境交互的策略，不一样。

on-policy例子：

如果每次了解到周围最好的动作值，就直接走过去。并且学习策略也一样（告诉自己的大脑，自己以后也要这样更新自己的价值表）

这种 和环境的交互策略 和 自己学习更新自己的行动决策依据的表 的 方案是一样的 就是on-policy。

off-policy 例子：
眼前有一块红烧肉，我脑中模拟自己吃了一口，模拟吃的时候很好吃，然后更新了一下策略表，告诉自己，吃这块红烧肉会得到奖励。关键是 ： 我只是脑袋里模拟的吃了一口。这不代表和环境交互 ，真正的环境交互是：我实际怎么做了？

如果脑袋里模拟吃了一口后，更新策略表，告诉自己，吃红烧肉可以得到奖励。（这叫【学习】）如果是on-policy，那就会直接和环境交互的过程中，也会实际吃一口红烧肉这个动作。但是如果是off-policy，则可能采取和【学习】的时候模拟的做法不一样，就是说，学习的策略并不用于直接决策用于执行如何和环境交互。这个时候 ，off-policy的做法是，虽然吃红烧肉比当前状态s下做别的动作回报多。但是我不一定选它这叫off-policy ，我保留了 一定的概率 我会随机选 或者其他方法 。

这种方法的robust（鲁棒性）非常强。
大家知道，我们吃红烧肉，立马获得了当前状态下能够获得的最好R（回报），但是不代表吃红烧肉在未来若干个时间内是最好的选择。（比如带来了增肥，脂肪肝，三高)。如果按on-policy ，当前学习的策略可能并不代表未来 。但是智能体如果用on-policy，就会过于相信自己学到的眼前的东西。off-policy的智能体，则会说：虽然吃红烧肉我感觉是当前状态的最佳回报选择，但是我还是保留不吃的可能性，避免后面碰到更多的红烧肉，把我引入了某种深渊(三高和肥胖、亚健康和脂肪肝、肝癌、死亡）。这样 ，就不会一直吃红烧肉，偶尔还会不吃，去做别的事。这样才会有更多的机会学到新的可能性和探索新的优化。

几乎现在所有的深度强化学习应用，都用到了Q-Learning这一类的，off-policy的算法

Q-Learning

Q-Learning 就是一个数学公式 比较简洁。

• S代表当前状态
• a代表了当前状态所采取的行动
• S’代表S在a行动后跳转到的下一个状态
• Q(S,A)代表 Q估值
• γ 决定未来奖励的重要性的程度

由公式看出：

s，a 对应的 Q 值等于 即时奖励 结合 未来奖励的 折扣discount

具体落地到怎么执行 可以用 bellman 公式：

• r是智能体在s状态上采取a行动的奖励
• γ 是 discount度

举例：

第一步：
Q(饿了，吃红烧肉）= Reward(饿了，吃红烧肉) + Discount*max(Q(不饿了,吃红烧肉))
我们定义了如下的 MDP

S={饿了，不饿，很饱，超级胖，三高}
A={吃红烧肉，运动，吃素，看书}
choose_action(饿了，吃红烧肉)=不饿
R(饿了，吃红烧肉)=10
choose_action(不饿，吃红烧肉）=很饱
R(不饿，吃红烧肉）=0
choose_action(很饱，吃红烧肉）=超级胖
R(很饱，吃红烧肉)=-5
choose_action(超级胖，吃红烧肉）=三高
R(超级胖，吃红烧肉)=-20

第二步：
Q(饿了，吃红烧肉）= R(饿了，吃红烧肉) + Discountmax( R(不饿了,吃红烧肉) + Discountmax(Q(很饱，吃红烧肉)) )

再继续展开 就是更进一步 把 Q(很饱，吃红烧肉) 展开，其中 Discount 如果=1 ，那么 未来的所有步骤获得回报值 都会不打折扣的累加到当前的Q。如果Discount =0.6 ，就是说 每往后一步 回报值对当前Q估计决策 的 累加 逐步影响递减。

如何更新Q-Table
Q-Table就是S(s,a)

1. 首先随机初始化S(s,a)表为一些比较小的随机数
2. repeat：（起点）
3. 基于s状态选择一个行动
4. 接受奖励r以及跳转到新的状态s’
5. Q(s,a) <- 老Q(s,a) 值+ alpha*( y- 老Q(s,a)值 )
6. 直到 学习结束

其中y= R + discount*max Q(S’,a)
Q是一张表，所以用Q-table 表示 ，老Q(s,a)值 的意思是 表还没更新的时候 对应的 Q(s,a)值 ，等同于python的 =。

Q-Table的更新 就是agent学习的过程，而agent每一次决策，则是 选取 argmax Q(s, )。
argmax 的意思是 比如 ：集合A={2,5,1,3,6} max (A) = 6。argmax(A) = 4 。因为从0数起 ， 6在序号4 。index=4 。argmax(A)的意思是 A里的最大值对应的 index

完成南理ARPG世界里的游戏

import numpy as np
import pandas as pd
import time 



np.random.seed(2) #reproducible


class QLearning():
    T=10  #target
    W=-2  #wall
    F=1 #flower
    M=0# Moving road
    

    MAP=[[W,W,W,W,W,W,W,W],
         [W,0,0,0,0,0,F,W],
         [W,0,0,0,0,0,F,W],
         [W,0,W,W,W,0,W,W],
         [W,0,W,T,0,0,F,W],
         [W,0,W,W