如下图所示：
初始点在 S0， 终点在S8， 其中红线的部分是墙，不能通过，绿色的圆圈是此刻所在位置。
每次实验的初始策略，是在任一的状态时可以选的动作其概率都是均等的，如果三个动作可以选就各为0.333333，如果是两个动作可以选就各是0.5。
每次实验通过不断的根据策略采样探索路径，并根据探索的路径修正策略从而达到策略迭代的目的，从而求得优化策略。
原书中已经提供代码，但是感觉看起来不是很明晰，于是修改了一下：
https://gitee.com/devilmaycry812839668/maze_policygradient
-------------------------------------------------------------------
书中对所给出的策略迭代方法的说明是该方法中的更新公式是由REINFORCE方法推导出来的公式。（对此有些不解，找了些关于REINFORCE方法的描述，怎么看都不像这个更新公式）
main.py 是一次实验使用策略迭代方法进行求解：
根据书中给出的10**-8的策略精度进行求解，结果如上两图。
如果是10**-4 的策略精度如下：
可以发现使用该方法迭代的次数还是比较高的，学习率为0.1 。
-----------------------------------------------
main_hist.py 是进行10000次实验，策略精度为10**-4 ， 学习率为0.1。
可以看到在设定下不同实验所需的迭代次数大致像一个高斯分布。
对10000次的实验做一下统计：
可以看到在10**-4的策略精度下，0.1的学习率下，进行10000次实验全部求得最优解（4步走迷宫），每次实验的平均策略迭代次数为4255.8307次，方差为127337.3106 。
可以看到书中给的reinforce方法虽然全部求得到了最优解，但是迭代次数还是很多的，计算花费很大。
感觉这个参数更新的方法才是这个策略迭代方法的核心，如果不从数学角度来看这个参数更新公式，而是只从表面意义来看怎么解释这个公式，这个公式可不可以再改进呢？
在状态i的访问个数 N_i 不为零的情况下，上面的参数更新公式可以写为：
如果把上面的括号内的内容看为一部分，那么上面的公式可以分为三部分：
第一部分可以看做是采样中状态 i 下 动作 j 的实际选择个数与状态i的访问比例，也可以说是实际采样中 状态 i 下动作 j 的选择概率，_pi[i, j] 可以看做是策略中状态 i 下动作 j 的选择概率。也就是说这个部分可以看做 采样中的状态 i 下动作 j 的选择概率 减去 策略中的状态 i 下动作 j 的选择概率。
N_ij/N_i 一定是一个小于1的数值，那么把其换成1效果如果呢，于是有了下面的实验：
更新公式换为：
超参数不变，依旧是10000次实验：
从直方图的形状上来看都是像高斯分布的。
进行10000次实验全部求得最优解（4步走迷宫），每次实验的平均策略迭代次数为5378.3984，比原公式的4255.8307次多了不少，方差为126794.2589 和原公式的127337.3106 相差不大。最值得注意的是在这实验下，共有432个实验没有取得最优解4，而是取得了次优解6，而且方差为0，说明这432个实验全部结果为6。
可以说采用新的参数更新公式后仍然可以进行求解，但是运算效率和最终性能上都有所下降，最值得注意的是有432个实验没有取得最优解。也就是这个说不出道理的改动还是可以得出一定的解，虽然效率和性能下降了。
那么把第一部分改为 _pi[i, j] 呢？
10000次实验：
神奇的发现该更新公式下，迭代的次数降低了， 平均值为569， 方差为350, 但是未取得最优解的实验次数为319，未取得最优解的迭代次数均值为6， 方差为0.012 。
分析了一下虽然迭代次数减少了，但是有一些策略并没有原公式得出的好，拿出一次的没有得到最优解的实验，最终解为6，可以看到其中有两个状态下的动作比最优解下策略的动作选择概率高， 从0.0001变成了0.0006，于是导致了部分实验中最终的解为6而不是4， 当然这个改动的更新公式也是完全说不出道理的，只是想试试这么好用不。
本着胡乱尝试的态度又试了试下面5种改变更新公式的方法：
发现都不是很可行，从中发现了个规律，可行的更新公式都是一个小于1的数值 乘以 N_ij 除以 T , 那么再试试下面的更新公式呢？
最优解的平均迭代次数为451， 方差为264， 其中有555次实验没有取得最优解（均值6.24， 方差3.5）。
可以看到该中更新公式，迭代次数最少，但是最终的结果不能达到最优解的个数也是最多， 分析没有达到最优解的策略，可以看到上图：
有四个动作的选择概率明显有差距， 其中三个有较大差距：0.0001变为0.0003， 0.0001变为0.0005， 0.0001变为0.0011 。
这里对参数更新公式的改动没有任何道理，完全是随意改动试试的，虽然所不清道理为什么会有这个现象，但是可以清晰的看到这个更新公式中最主要的部分就是
N_ij/T ， 这里的改动公式只要带有这一项的更新公式取得效果都还可以。
PS:这里之所以胡乱试验了这些改动公式，就是为了分析原公式，试着找出该公式是如何从reinforce中推导出来的， 这一通改动虽然仍旧没有弄清这个原更新公式于reinforce的关系，但是发现了 N_ij/T 的重要性， 下一步还是得再继续研究研究reinforce算法，看看两者之间的关系。
----------------------------------------------------------------
在网上找了一些 reinforce 算法的介绍，发现一个讲的不错的：
https://tigerneil.wordpress.com/2016/05/23/reinforce-algorithm/
其中对reinforce的大致描述如下（详细内容参见上网址）：
还是上面的那个走迷宫问题， 其中 T 是最终到终点后的走的步数（上面伪代码的T为走的第几步数，当然总步数也是T），那么每一个动作的奖励回报（Reward）可以看成是 1/T ， 由于实际算法中是可以采取随机梯度更新的，不是像上面伪代码中的小批次的更新（mini-batch）,那么久没有N这个变量什么关系了，
剩下的项就是 
不好解释。
在原公式中的参数可以看做是偏好函数，但是如果我们把这个参数看做是策略的拟合参数， 比如状态 i 下面有三个动作可以选择，分别是1 ， 2， 3， 参数为θ1，θ2，θ3 ， 每一个状态的表示为x_i, 这里面全部看做是1 。
那么动作1的策略为：p1=exp(θ1)/(exp(θ1)+exp(θ2)+exp(θ3)) ,动作2：p2=exp(θ2)/(exp(θ1)+exp(θ2)+exp(θ3)) ， 动作3：p3=exp(θ3)/(exp(θ1)+exp(θ2)+exp(θ3)) 。
那么上面的那项（状态 i 动作 j ）
可以看做是
log(exp(θ1)/(exp(θ1)+exp(θ2)+exp(θ3))) , 即 log(p1) 对 θ1 ， θ2， θ3 进行求导。
log(p1)对θ1 求导 为 1-p1 ,
log(p1)对θ2 求导 为 -p2 ,
log(p1)对θ2 求导 为 -p3 。
根据reinforce公式
，我们可以得到 回报期望中状态i动作j这一项 对θ1 的导数（一次采样过程中状态i动作j的个数为N_ij, 回报为1/T）：
(1-p1)*N_ij / T ,
对θ2 的导数：
-p2*N_ij / T ,
对θ3 的导数：
-p3*N_ij / T 。
在状态i下动作j=1时候如上面公式，当j=2, j=3时也是如此。那么在一次路径中对θ1 导数之和可以看做 j=1时的 (1-p1)*N_ij / T 和j=2,j=3时候的 ( -p1)*(Ni-N_ij) / T 的和。
(1-p1)*N_ij / T 与 ( -p1)*(Ni-N_ij) / T 的和可以写成 （N_ij- pj）*Ni / T 。
（N_ij- pj）*Ni / T 正好和原书中的所谓从reinforce算法推导出来的公式一致了。
把原书中公式
展开：
该公式就是将j=1时对θ1 的更新和j=2,j=3时对θ1 的更新全部放在了一起进行。
如果把这个再拆开，就是j=1是对 θ1 ，θ2， θ3 更新一次，j=2是对 θ1 ，θ2， θ3 更新一次，j=3是对 θ1 ，θ2， θ3 更新一次，可以修改更新公式：
更改后的 update_theta 函数：
def update_theta(s_a_history): global theta_0 eta = 0.1 # 学习率 T = len(s_a_history) - 1 # 总步数 [m, n] = theta_0.shape # theta shape值 delta_theta = np.zeros_like(theta_0) # Δtheta theta的copy zeros temp=dict() # temp.setdefault(int) # delta_theta for i in range(0, m): for j in range(0, n): if not(np.isnan(theta_0[i, j])): # theta 中不为nan的部分 temp[(i,j)]=s_a_history.count([i, j]) for (s,a), c in temp.items(): for j in range(0, n): if not(np.isnan(theta_0[s, j])): # theta 中不为nan的部分 if a==j: delta_theta[s, j]+=(1.0-_pi[s, j])*c/T # else: delta_theta[s, j]+=(-_pi[s, j])*c/T new_theta = theta_0 + eta * delta_theta #更新 参数 theta_0 theta_0=new_theta
当然这两个都是等价的。
比如在状态s下，可以选择动作1 ，2， 3， 参数为θ1，θ2 ，θ3 ， 在一次路径中s下动作1,2,3全部出现那么原书中公式和上面这个修改公式显然等价，
只出现动作1时， N_i 等于 N_ij , 显然下面的公式相等，θ1的更新可以看到是相同的：
这里下面公式为0：
但是对θ2 ，θ3 的更新需要在j=2 , j=3 时：此时 N_ij=0, 可以看到下面第一个公式为0，第二个公式对θ2 ，θ3 的更新也是与展开的公式相同的。
此时在j=2, j=3时，对θ2 ，θ3 的更新可以写成 -pi[i, j]*N_i/T , 与展开后的更新公式相同。
-------------------------------------------------------------------------
给出原书中的参数更新方式：
def update_theta(s_a_history): global theta_0 eta = 0.1 # 学习率 T = len(s_a_history) - 1 # 总步数 [m, n] = theta_0.shape # theta shape值 delta_theta = theta_0.copy() # Δtheta theta的copy # delta_theta for i in range(0, m): for j in range(0, n): if not(np.isnan(theta_0[i, j])): # theta 中不为nan的部分 SA_i = [SA for SA in s_a_history if SA[0] == i] # 探索路径中为i的状态 SA_ij = [SA for SA in s_a_history if SA == [i, j]] # 探索路径中状态为i的动作为j的列表 N_i = len(SA_i) # N_ij = len(SA_ij) # #更新公式 delta_theta[i, j] = (N_ij - _pi[i, j] * N_i) / T new_theta = theta_0 + eta * delta_theta # print(new_theta) #更新 参数 theta_0 theta_0=new_theta
---------------------------------