【马尔可夫收益过程(Markov reward process , MRP)】是指不包含动作的马尔可夫决策过程，在只关心预测问题时使用的模型。
问题描述：
以中心状态C开始，在每个时刻以相同的概率向左或向右移动一个状态，在两端终止，episode终止于最右侧时会有+1的收益，除此之外收益均为0。
对于19个状态的随机游走问题，其左端收益为-1，右端收益为+1，其真实的价值应为[ 0. , -0.9, -0.8, -0.7, -0.6, -0.5, -0.4, -0.3, -0.2, -0.1, 0. , 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0. ]
导入所需要的包：
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from tqdm import tqdm
plt.rcParams['font.sans-serif'] = ['SimHei'] # 正确显示中文
plt.rcParams['axes.unicode_minus'] = False # 正确显示正负号
问题描述：
# 共有19个状态
N_STATES = 19
# 折扣系数
GAMMA = 1
# 状态合计【1，2，3，4，……，19】
STATES = np.arange(1, N_STATES + 1)
# 起始状态_中间位置开始
START_STATE = (N_STATES+1)/2
# 两个终止状态
# S=0时，左边终止 reward=-1
# S=20时，右边终止 reward=1
END_STATES = [0, N_STATES + 1]
# 随机游走问题中真实的价值函数，用来通过误差评比各种算法的预测能力
TRUE_VALUE = np.arange(-20, 22, 2) / 20.0
TRUE_VALUE[0] = TRUE_VALUE[-1] = 0 #第一个和最后一个都是0
环境交互函数：（随机action）
def env_step(state):
# 随机游走,更新state
if np.random.binomial(1, 0.5) == 1:
next_state = state + 1
else:
next_state = state - 1
# 根据state ，反馈回reward
if next_state == 0:
reward = -1
elif next_state == 20:
reward = 1
else:
reward = 0
done = False
if next_state in END_STATES:
done = True # 到达终点
info=' '
return next_state,reward,done,info
一、n-steps TD method（n步自举法）预测随机游走问题的状态价值
def temporal_difference(value, n, alpha):
# @value: 更新对象——状态价值评估结果
# @n: 每相隔几步进行更新
# @alpha: 学习率
state = START_STATE # 初始化state,出发
time = 0
# 储存一个episode中的state and reward
states = [state]
rewards = [0]
T = float('inf') # 幕序列时长到正无穷
while True: # episode开始
time += 1
if time < T:
next_state, reward, done, info = env_step(state)
states.append(next_state)
rewards.append(reward)
if done:
T = time # 到达终点
#更新第update_num个状态
update_num = time - n
if update_num >= 0:
returns = 0.0
# 计算累计收益
for t in range(update_num + 1, min(T, update_num + n) + 1):
returns += pow(GAMMA, t - update_num - 1) * rewards[t]
# 加入折后回报
if time <= T:
s=int(states[(update_num + n)])
returns += pow(GAMMA, n) * value[s]
state_to_update = int(states[update_num])
if state_to_update not in END_STATES: #两个终端状态不进行估计
value[state_to_update] += alpha * (returns - value[state_to_update])
if done:
break# episode结束
state = next_state # 更新state
选择一组超参数，观察算法收敛性
# 超参数选择
n = 8 # 自举数
alpha = 0.2 # 步长
episode_num = 100 #玩几局游戏
episodes = np.arange(1, episode_num+1)
value = np.zeros(N_STATES + 2) #初始化
errors = []
error = 0.0
for ep in range(0,episode_num):
value = temporal_difference(value, n, alpha) # 更新价值
error += np.sqrt(np.sum(np.power(value - TRUE_VALUE, 2)) / N_STATES)
error_a = error / (ep+1)
errors.append(error_a)
plt.plot(episodes, errors)
plt.xlabel('游戏环节数')
plt.ylabel('与真实价值的误差为')
plt.show()
对比不同步长与不同学习率对预测能力的影响
def figure7_2():
# 步长分别为：[ 1, 2, 4, 8, 16, 32, 64, 128]
steps = np.power(2, np.arange(0, 8))
# 学习率分别为：[0. , 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1. ]
alphas = np.arange(0, 1.1, 0.1)
# 进行20次游戏
episodes = 20
# 进行10次独立实验测试
runs = 10
# errors数组存储每个steps和每个alpha对应的error
errors = np.zeros((len(steps), len(alphas)))
for run in tqdm(range(0, runs)):#进度条
for step_ind, step in enumerate(steps):
for alpha_ind, alpha in enumerate(alphas):
value = np.zeros(N_STATES + 2) #初始化21个value
for ep in range(0, episodes):
temporal_difference(value, step, alpha)
errors[step_ind, alpha_ind] += np.sqrt(np.sum(np.power(value - TRUE_VALUE, 2)) / N_STATES)
errors /= episodes * runs
for i in range(0, len(steps)):
plt.plot(alphas, errors[i, :], label='n = %d' % (steps[i]))
plt.xlabel('不同学习率α')
plt.ylabel('19个状态前10幕经验的均方误差')
plt.ylim([0.2, 0.6])# 纵轴坐标范围
plt.legend()
plt.savefig('figure_7_2.png')
plt.show()
figure7_2()
n为1时是单步TD、n为正无穷时是MC预测。
由此可见，n去中间值时的预测效果更好，这也证明了将单步TD和MC方法推广至N步自举法能够得到更好的结果。其中学习率的调节也应随着n的调节变化。
本文地址：https://blog.csdn.net/qq_42138927/article/details/110504483
黄山市民网：https://www.huangshanshimin.com/
