强化学习入门之智能走迷宫-价值迭代算法

0x01 价值迭代算法基础概念

0x01.1 奖励

若要实现价值迭代，首先要定义价值，在迷宫任务中，到达目标将获得奖励。

• 特定时间t给出奖励Rt称为即时奖励
• 未来获得的奖励总和Gt被称为总奖励
• Gt=R(t+1)+R(t+2)+R(t+3)
• 考虑时间因素，需要引入折扣率，这样可以在最后拟合时获得时间最短的策略。
• Gt=R(t+1)+yR(t+2）+y^2R(t+3)....

0x02 动作价值与状态价值

在迷宫中，当我们的智能体走到终点时设置奖励R(t+1)=1

0x02.1 动作价值

如果状态s=S7且动作a=向右，则意味着S7→S8移动，这样就可以在下一步中达到目标并获得奖励Rt+1=1。

动作价值可以用动作价值函数Qπ(s,a)表示。有4种类型的动作（向上、向右、向下、向左），在动作索引为a=1时向右移动，所以有：
Qπ(s=7,a=1)=Rt+1=1

若此时在S7的智能体下一步动作是向上，那么S7->S4 远离了目标,这样要想最快到达终点需要啊 S7->S4->S7->S8 可以看到S7会重复2次
此时获得的奖励就被打了折扣
Qπ(s=7,a=0)=γ2*1
依此类推，如果方向一直不对，那么奖励就一直被打折扣，也就越来越少。
这里因为奖励是根据智能体的动作变化而变化的，所以被称为动作价值。

0x02.2 状态价值

状态价值是指在状态s下遵从策略π行动时，预计在将来获得的总奖励Gt。将状态s的状态价值函数写为Vπ(s)

若智能体在S7状态，向右移动即可获得奖励 存在 Vπ(s=7)=1

若智能体在S4，向下移动到S7，再向右移动到S8， 存在 Vπ(s=4)=y1
也可表示为 Vπ(s=4)=R(t+1)+yVπ(s=7)=0+y*1=y

0x03 贝尔曼方程和马尔可夫决策过程

状态价值函数最后可通过这个方程表达 -》
这个方程被称为贝尔曼方程

• VΠ(s) 表示在状态s时的状态价值V

• 该状态价值是通过右侧具有最大值动作的期望的价值，如果我们想要拟合一个最大的价值状态，那么在迷宫中，最短路径就能实现最大价值期望。

• R(s'a) 是在状态s下采用动作a移动后的新状态的即时奖励R(t+1)

• VΠ()中的s(s,a)表示在状态s下采用动作a移动后的新状态s+1

• 方程表达的是 新状态的状态价值V时间折扣率加上现在的即使奖励的和的最大值就是当前的状态价值。
  举个例子，比如在S8的时候设置了即时奖励 1 ，所以根据公式，在S7的时候 状态价值就是 1
  而在S4时 状态价值是 0+1y
  在S3时， 状态价值是 0+1yy
  方向用概率表示， 从S3->S4->S7->S8 假设方向为a 上右下左随机的概率 a11y^2+a21y+a31 可以得到最大价值期望。
  **如果我们可以通过一个函数使得 a11y^2+a21y+a31 收敛于一个最大值， 就能不断改变a的概率， 使的a1中向右概率大大增加，a2中向下概率大大增加，a3中向右概率大大增加。**

作为贝尔曼方程成立的前提条件，学习对象必须是满足马尔可夫决策过程的，即下一步的状态由当前状态和采用的动作决定。

0x04 使用Sarsa算法与epsilon贪婪法实现策略

epsilon贪婪法 简单理解就是 以 一定概率p随机行动， 以剩下的1-p的概率采用动作价值Q最大的行动。 随着实验次数的增加，p的概率会减小，原因是不管怎么走都会走一条固定的最短路径到达终点。

由于初始状态不清楚每个状态的动作价值 所以需要随机定义

[a,b]=theta_0.shape # 获取行，列数
Q=np.random.rand(a,b)*theta_0 # 将theta_0乘到各个元素上，使Q墙壁方向为nan

然后定义随机方向策略

def simple_convert_into_pi_from_theta(theta):
    ''' 简单计算比率'''
    [m,n]=theta.shape # 读取theta矩阵
    pi=np.zeros((m,n))
    for i in range(0,m):
        pi[i,:]=theta[i,:]/np.nansum(theta[i,:]) # 计算比率
    pi=np.nan_to_num(pi) # 将nan转换为0
    return pi

定义epsilon贪婪算法,使得一部分随机走，一部分按照求最大价值函数Q的方向去走

# 实现epsilon贪婪算法
def get_action(s,Q,epsilon,pi_0):
    direction=["up","right","down","left"]
    # 确定行动
    if np.random.rand()<epsilon:
        next_direction=np.random.choice()
    else:
        # 采用让Q获得最大值的动作
        next_direction=direction[np.nanargmax(Q[s,:])]

    # 为每个动作设置索引
    if next_direction=="up":
        action=0
    if next_direction=="right":
        action=1
    if next_direction=="down":
        adcion=2
    if next_direction=="left":
        action=3
    return action
# 设置状态索引
def get_s_next(s,a,Q,epsilon,pi_0):
    direction = ["up", "right", "down", "left"]
    next_direction=direction[a] # 动作a的方向
    # 根据动作确定下一步状态
    if next_direction=='up':
        s_next=s-3 # 向上移动 状态数-3
    if next_direction=="right":
        s_next = s + 1
    if next_direction=="down":
        s_next = s + 3
    if next_direction=="left":
        s_next = s - 1
    return s_next

如果获得动作价值函数Q(s,a)的正确值，则贝尔曼方程
Q(st,at)=Rt+1+γQ(st+1,at+1)
所表示的关系成立。
然而，由于在学习过程中尚未正确求得动作价值函数，因此该等式是不成立的。
此时，上述等式两边之间的差Rt+1+γQ(st+1,at+1)-Q(st,at)是TD误差（时间差，Temporal Difference error）。如果此时TD误差为0，则表示已正确学习到了动作价值函数。Q的更新公式是：
Q(st,at)=Q(st,at)+η*(Rt+1+γQ(st+1,at+1)-Q(st,at)
其中η是学习率，η后面是TD误差。遵循此更新公式的算法称为Sarsa算法

基于Sarsa算法去更新策略

def Sarsa(s,a,r,s_next,a_next,Q,eta,gamma):
    if s_next==8:
        Q[s,a]=Q[s,a]+eta*(r-Q[s,a])
    else:
        Q[s,a]=Q[s,a]+eta*(r+gamma*Q[s_next,a_next]-Q[s,a])
    return Q

通过该算法去求解

def goal_maze_ret_s_a_Q(Q,epsilon,eta,gamma,pi):
    s=0
    a=a_next=get_action(s,Q,epsilon,pi)
    s_a_history=[[0,np.nan]] # 记录移动体序列
    while (1):
        a=a_next # 动作更新
        s_a_history[-1][-1]=a
        # 将动作放在当前状态
        s_next=get_s_next(s,a,Q,epsilon,pi)
        # 有效的下一个状态
        s_a_history.append([s_next,np.nan])
        # 代入下一个状态 动作未知则为nan
        if s_next==8:
            r=1 # 给奖励
            a_next=np.nan
        else:
            r=0
            a_next=get_action(s_next,Q,epsilon,pi)
            # 求得下一个动作
        # 更新价值函数
        Q=Sarsa(s,a,r,s_next,a_next,Q,eta,gamma)

        # 终止判断
        if s_next==8:
            break
        else:
            s=s_next
    return [s_a_history,Q]

设置初始值

# 求解
    eta=0.1 # 学习率
    gamma=0.9 # 时间折扣率
    epsilon=0.5 # epsilon贪婪算法
    v=np.nanargmax(Q,axis=1) # 根据 状态求最大价值
    is_continue=True
    episode=1
    while is_continue:
        print("当前回合：",str(episode))
        # epsilon贪婪法的值变小
        epsilon=epsilon/2
        # 通过Sarsa求解迷宫问题
        [s_a_history,Q]=goal_maze_ret_s_a_Q(Q,epsilon,eta,gamma,pi_0)
        # 状态价值变化
        new_v=np.nanmax(Q,axis=1) # 各状态求最大价值
        print(np.sum(np.abs(new_v-v))) # 输出状态价值变化
        v=new_v
        print("求解迷宫问题所需步骤：",str(len(s_a_history)-1))
        episode=episode+1
        if episode>50:
            break

完整代码

# 引入库函数
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import animation
# 画图
def plot():
    fig=plt.figure(figsize=(5,5))
    ax=plt.gca()
    # 画墙壁
    plt.plot([1,1],[0,1],color='red',linewidth=3)
    plt.plot([1,2],[2,2],color='red',linewidth=2)
    plt.plot([2,2],[2,1],color='red',linewidth=2)
    plt.plot([2,3],[1,1],color='red',linewidth=2)
    # 画状态
    plt.text(0.5,2.5,'S0',size=14,ha='center')
    plt.text(1.5,2.5,'S1',size=14,ha='center')
    plt.text(2.5,2.5,'S2',size=14,ha='center')
    plt.text(0.5,1.5,'S3',size=14,ha='center')
    plt.text(1.5,1.5,'S4',size=14,ha='center')
    plt.text(2.5,1.5,'S5',size=14,ha='center')
    plt.text(0.5,0.5,'S6',size=14,ha='center')
    plt.text(1.5,0.5,'S7',size=14,ha='center')
    plt.text(2.5,0.5,'S8',size=14,ha='center')
    plt.text(0.5,2.5,'S0',size=14,ha='center')
    plt.text(0.5,2.3,'START',ha='center')
    plt.text(2.5,0.3,'END',ha='center')
    # 设置画图范围
    ax.set_xlim(0,3)
    ax.set_ylim(0,3)
    plt.tick_params(axis='both',which='both',bottom='off',top='off',labelbottom='off',right='off',left='off',labelleft='off')
    # 当前位置S0用绿色圆圈
    line,=ax.plot([0.5],[2.5],marker="o",color='g',markersize=60)
    # 显示图
    plt.show()
def simple_convert_into_pi_from_theta(theta):
    ''' 简单计算比率'''
    [m,n]=theta.shape # 读取theta矩阵
    pi=np.zeros((m,n))
    for i in range(0,m):
        pi[i,:]=theta[i,:]/np.nansum(theta[i,:]) # 计算比率
    pi=np.nan_to_num(pi) # 将nan转换为0
    return pi
# 实现epsilon贪婪算法
def get_action(s,Q,epsilon,pi_0):
    direction=["up","right","down","left"]
    # 确定行动
    if np.random.rand()<epsilon:
        next_direction=np.random.choice(direction,p=pi_0[s,:])
    else:
        # 采用让Q获得最大值的动作
        next_direction=direction[np.nanargmax(Q[s,:])]

    # 为每个动作设置索引
    if next_direction=="up":
        action=0
    if next_direction=="right":
        action=1
    if next_direction=="down":
        action=2
    if next_direction=="left":
        action=3
    return action
# 设置状态索引
def get_s_next(s,a,Q,epsilon,pi_0):
    direction = ["up", "right", "down", "left"]
    next_direction=direction[a] # 动作a的方向
    # 根据动作确定下一步状态
    if next_direction=='up':
        s_next=s-3 # 向上移动 状态数-3
    if next_direction=="right":
        s_next = s + 1
    if next_direction=="down":
        s_next = s + 3
    if next_direction=="left":
        s_next = s - 1
    return s_next

# Sarsa算法更新策略
def Sarsa(s,a,r,s_next,a_next,Q,eta,gamma):
    if s_next==8:
        Q[s,a]=Q[s,a]+eta*(r-Q[s,a])
    else:
        Q[s,a]=Q[s,a]+eta*(r+gamma*Q[s_next,a_next]-Q[s,a])
    return Q

# 使用Sarsa算法求解迷宫问题
def goal_maze_ret_s_a_Q(Q,epsilon,eta,gamma,pi):
    s=0
    a=a_next=get_action(s,Q,epsilon,pi)
    s_a_history=[[0,np.nan]] # 记录移动体序列
    while (1):
        a=a_next # 动作更新
        s_a_history[-1][-1]=a
        # 将动作放在当前状态
        s_next=get_s_next(s,a,Q,epsilon,pi)
        # 有效的下一个状态
        s_a_history.append([s_next,np.nan])
        # 代入下一个状态 动作未知则为nan
        if s_next==8:
            r=1 # 给奖励
            a_next=np.nan
        else:
            r=0
            a_next=get_action(s_next,Q,epsilon,pi)
            # 求得下一个动作
        # 更新价值函数
        Q=Sarsa(s,a,r,s_next,a_next,Q,eta,gamma)

        # 终止判断
        if s_next==8:
            break
        else:
            s=s_next
    return [s_a_history,Q]



if __name__=="__main__":
    theta_0=np.array([[np.nan,1,1,np.nan], #S0
                      [np.nan,1,np.nan,1], #S1
                      [np.nan,np.nan,1,1], #S2
                      [1,1,1,np.nan], #S3
                      [np.nan,np.nan,1,1], #S4
                      [1,np.nan,np.nan,np.nan], #S5
                      [1,np.nan,np.nan,np.nan], #S6
                      [1,1,np.nan,np.nan],  #S7
                      ])   # S8位目标 不需要策略
    print(theta_0)
    #plot()
    # 设置初始的动作价值函数
    [a,b]=theta_0.shape # 获取行，列数
    Q=np.random.rand(a,b)*theta_0 # 将theta_0乘到各个元素上，使Q墙壁方向为nan
    pi_0=simple_convert_into_pi_from_theta(theta_0) # 设置移动方向初始策略
    # 求解
    eta=0.1 # 学习率
    gamma=0.9 # 时间折扣率
    epsilon=0.5 # epsilon贪婪算法
    v=np.nanargmax(Q,axis=1) # 根据 状态求最大价值
    is_continue=True
    episode=1
    while is_continue:
        print("当前回合：",str(episode))
        # epsilon贪婪法的值变小
        epsilon=epsilon/2
        # 通过Sarsa求解迷宫问题
        [s_a_history,Q]=goal_maze_ret_s_a_Q(Q,epsilon,eta,gamma,pi_0)
        # 状态价值变化
        new_v=np.nanmax(Q,axis=1) # 各状态求最大价值
        print(np.sum(np.abs(new_v-v))) # 输出状态价值变化
        v=new_v
        print("求解迷宫问题所需步骤：",str(len(s_a_history)-1))
        episode=episode+1
        if episode>50:
            break

运行效果