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
运行效果
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
