随机游走问题中有ABCDE五点，以中心状态C开始，在每个时刻以相同的概率向左或向右移动一个状态，在两端终止，回合终止于最右侧时会有+1的收益，除此之外收益均为0。编写MRP、DP、MC、SARSA和QLearning算法代码计算随机游走过程每个状态的价值。假定折扣系数为1，中间状态的转移概率为0.5。

以下是Python代码实现：

首先定义状态转移概率和状态收益：

import numpy as np

# 状态转移概率矩阵
P = np.array([[0.5, 0.5, 0, 0, 0],
              [0.5, 0, 0.5, 0, 0],
              [0, 0.5, 0, 0.5, 0],
              [0, 0, 0.5, 0, 0.5],
              [0, 0, 0, 0.5, 0.5]])

# 状态收益
R = np.array([0, 0, 0, 0, 1])

MRP算法：

# MRP算法
def MRP(P, R):
    # 计算每个状态的收益
    V = np.linalg.inv(np.eye(len(P)) - P) @ R
    return V

print("MRP算法结果：", MRP(P, R))

DP算法：

# DP算法
def DP(P, R):
    # 初始化价值函数
    V = np.zeros(len(P))
    # 迭代更新
    while True:
        V_new = R + P @ V
        if np.max(np.abs(V_new - V)) < 1e-6:
            break
        V = V_new
    return V

print("DP算法结果：", DP(P, R))

MC算法：

# MC算法
def MC(P, R, n_episodes=1000, alpha=0.1):
    # 初始化价值函数和状态计数器
    V = np.zeros(len(P))
    N = np.zeros(len(P))
    # 多次迭代
    for i in range(n_episodes):
        S = 2
        G = 0
        episode = []
        # 生成一次回合
        while True:
            A = np.random.choice([-1, 1])
            S_new = S + A
            if S_new < 0 or S_new >= len(P):
                episode.append((S, A, G))
                break
            R_new = R[S_new]
            episode.append((S, A, R_new))
            S = S_new
        # 更新价值函数
        for j, (S, A, G) in enumerate(episode):
            V[S] += alpha * (G - V[S])
    return V

print("MC算法结果：", MC(P, R))

SARSA算法：

# SARSA算法
def SARSA(P, R, n_episodes=1000, alpha=0.1, epsilon=0.1):
    # 初始化价值函数和Q函数
    V = np.zeros(len(P))
    Q = np.zeros((len(P), 2))
    # 多次迭代
    for i in range(n_episodes):
        S = 2
        A = eps_greedy(Q[S], epsilon)
        while True:
            S_new = S + A
            if S_new < 0 or S_new >= len(P):
                Q[S, A] += alpha * (R[S_new] - Q[S, A])
                break
            A_new = eps_greedy(Q[S_new], epsilon)
            Q[S, A] += alpha * (R[S_new] + Q[S_new, A_new] - Q[S, A])
            S = S_new
            A = A_new
        # 更新价值函数
        V = np.max(Q, axis=1)
    return V

# epsilon-greedy策略
def eps_greedy(Q, epsilon):
    if np.random.rand() < epsilon:
        return np.random.choice([0, 1])
    else:
        return np.argmax(Q)

print("SARSA算法结果：", SARSA(P, R))

QLearning算法：

# QLearning算法
def QLearning(P, R, n_episodes=1000, alpha=0.1, epsilon=0.1):
    # 初始化价值函数和Q函数
    V = np.zeros(len(P))
    Q = np.zeros((len(P), 2))
    # 多次迭代
    for i in range(n_episodes):
        S = 2
        while True:
            A = eps_greedy(Q[S], epsilon)
            S_new = S + A
            if S_new < 0 or S_new >= len(P):
                Q[S, A] += alpha * (R[S_new] - Q[S, A])
                break
            Q[S, A] += alpha * (R[S_new] + np.max(Q[S_new]) - Q[S, A])
            S = S_new
        # 更新价值函数
        V = np.max(Q, axis=1)
    return V

print("QLearning算法结果：", QLearning(P, R))