强化学习算法复现：n步自举法的价值预测能力_随机游走问题

【马尔可夫收益过程(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