强化学习-如何计算MRP中的这些状态值？

Question

这是RL简介书中的一个问题，第125页，示例6.2。

该示例比较了TD(0)和常数\alpha MC在以下马尔可夫奖励过程中的预测能力(图像是从书中复制的)：

在上面的MRP中，所有的事件都从C状态开始，然后在每一步中都可以左转或右转(概率相等)。

剧集终止于极左或极右。当一集在右边结束时，就会出现+1的奖励；所有其他奖励都为零。例如，一个典型的插曲可能由以下状态和奖励序列组成: C，0，B，0，C，0，D，0，E，1。因为这个任务是不打折的，所以每个状态的真实值是从那个状态开始在右边终止的概率。

书中提到V(A)=1/6，V(B)=2/6，V(C)=3/6，V(D)=4/6和V(E)=5/6；请您帮助我理解这些值是如何计算的吗？谢谢。

Answer 1

由于它是如此小的MRP，因此可以使用基于Bellman方程的联立方程快速和解析地求解它：

v(s) = \sum_{r,s'} p(r,s'|s)(r + v(s'))

在每一个州轮流替代。使用变量a,b,c,d,e来表示v(A), v(B), v(C), v(D), v(E)可以更容易地阅读：

a = \frac{1}{2}(0 + b)

b = \frac{1}{2}(a+c)

c = \frac{1}{2}(b+d)

d = \frac{1}{2}(c+e)

e = \frac{1}{2}(d+1)

它需要多个替换来解决任何单个值，至少一开始是这样的。但是，可以通过反复替换a的次数来解决这些项，然后继续到下一个方程，得到每个变量：

a = \frac{1}{2}(0 + b) \therefore b = 2a

b = \frac{1}{2}(a+c) \rightarrow 2a = \frac{1}{2}(a + c) \therefore c = 3a

c = \frac{1}{2}(b+d) \rightarrow 3a = \frac{1}{2}(2a + d) \therefore d = 4a

d = \frac{1}{2}(c+e) \rightarrow 4a = \frac{1}{2}(3a + e) \therefore e = 5a

e = \frac{1}{2}(d+1) \rightarrow 5a = \frac{1}{2}(4a+1) \therefore a = \frac{1}{6}

最后一个解决了所有问题，并给出了预期的答案。你也可以在这里看到一个非常强大的模式，它可以直观地保持任意长度的一维随机游动，且具有相等的p=0.5 --对于更一般的情况，有一个证据可以消除对每个长度进行详细替换的需要，但这就更复杂了。

另一个简单的直觉:每个状态值依次是它的任何一方的两个状态值的平均值，无一例外。这意味着取任意三个相邻的值，它们应该是共线性的；两个值越高越低，两者之间的平均值。由于这适用于所有有重叠的值，按顺序绘制值应该将所有的点都放在同一条线上。这就意味着，随机游动中的位置与状态值之间存在着简单的线性关系。