背景
Reinforcement Learning, an Introduction 第二版 4.1 Policy Evaluation (Prediction)中提到两种求value的算法。
当我们已知环境模型时，我们可以根据状态值函数的Bellman方程得到v(s)和v(s')的关系，也就是当前状态下的value和下一状态下value的关系，表达如下:
对于实际问题，我们通常已知环境信息，已知optimal最优的状态，也就是我们要达到的目标Goal，目的往往是要找到达到optimal policy的最佳路径。如公式所示，在k+1 -> ∞的时候，理论上我们能得到所有可能的状态下的value的收敛值，以及对应的optimal policy。
算法 ( P75 )
实现的方式有两种：
- 两个数组 v[]old, v[]new
-
一个数组 v 不断迭代更新（in-place algorithm）
算法概述
example ( P76 Example 4.1 )
算法设计
- 动态规划就是去计算最优策略的一系列算法。
- 4.1 给出最基础的算法，就是根据环境模型，按照其计算value。实现方式有两种，一种是持有两个数组，另一种是操作一个数组。下面分别实现。
- 需要定义的：
- 常量ACTIONS TOP DOWN LEFT RIGHT
- 三维数组 environment[state][action][1:reward]/[2:statep]/[3:prob]
- 算法函数输入输出：
- 输入：环境的信息
environment[][][] - 输出： 实现optimal policy所花费的时间、步数、流程
- 输入：环境的信息
-
inspaceAlgorithm()函数
操作一个数组value[state]根据算法更新数组内容 -
noninspaceAlgorithm()函数
操作两个数组value_old[state]value_new[state]根据算法更新数组内容
算法实现
noninspaceAlgorithm()
def noninspaceAlgorithm():
global value_new, value_old
i = 0
while True:
smallvalue_ = 0
i += 1
value_old = value_new.copy()
# 注意这个数组要有置空操作
value_new = np.zeros(16)
for state in range(1, 15):
for action in [TOP, DOWN, LEFT, RIGHT]:
p = environment[(state, action)][0] + discount * value_old[int(environment[(state, action)][1])]
value_new[state] += environment[(state, action)][2] * p
smallvalue_ = max(smallvalue_, abs(value_new[state] - value_old[state]))
if smallvalue_ < smallvalue:
break
print(value_new.reshape(4, 4))
print(i, " time steps before converged in noninspaceAlgorithm")
inspaceAlgorithm()
def inspaceAlgorithm():
global value
i = 0
while True:
i += 1
# smallvalue_ = 0 应该在每个时间片循环之初就置为0 因为只是在当前时间片之中比较
smallvalue_ = 0
for state in range(1, 15):
v = 0
for action in [TOP, DOWN, LEFT, RIGHT]:
p = environment[(state, action)][0] + discount * value[int(environment[(state, action)][1])]
v += environment[(state, action)][2] * p
smallvalue_ = max(smallvalue_, abs(v - value[state]))
value[state] = v
if smallvalue_ < smallvalue:
break
print(value.reshape(4, 4))
print(i, " time steps before converged in inspaceAlgorithm")
结果
在精度smallvalue = 0.0000000000001的情况下，执行两个函数直到收敛，输出收敛的结果和达到收敛的步数（time steps），结果如下：
- 可以看出表示状态下value的值最终收敛，而这个值代表的是当前状态下，之后所有可能的路线轨迹以及其对应的value（reward之和）的期望
- 收敛速率 in-place算法收敛速度更快。可以看出当精度设置为0.0000000000001时，收敛时经过的步数 ( time steps ) 分别为非in-place算法：552；in-place算法：351。
- 在很早的时候，我们就已经得到了optimal policy，optimal policy也就是在每一个状态下，选择value最大的action。（可以尝试输出前6个timesteps得到的结果）
总结
算法是相对很简单的算法，只是手动计算比较复杂，书上的例子给出了收敛结果（但我看的时候没注意到那是收敛了的结果），想自己实现一遍，一来体会一下算法实现的过程，二来比较一下二者收敛的速度，想看看每一个time steps后value值的变化，三来也想熟悉一下python编程。
编程还是花了一定的时间，虽然很简单。再接再厉吧。不过这一个过程，也让我对value的计算能有了更巩固的认知，毕竟实践出真知。
纰漏还是有的。我用了dict存储(state, action)对应环境下的s', r, pi信息，但是p信息应该是p(s, a, s', r)，这个例子中这个值为1，所以没有考虑，但再更复杂的情况下，是不是要再加一个dict来存储这个信息？
加油加油。
