蒙特卡罗策略迭代

用蒙特卡罗方法来实现策略评估，即给定一个策略，找出价值函数。

重点是：

    for _ in range(100):
        # generate an episode using pi
        states, rewards = play_game(grid, policy)
        G = 0
        T = len(states)
        for t in range(T - 2, -1, -1):
            s = states[t]
            r = rewards[t + 1]
            G = r + GAMMA * G  # update return

            # we'll use first-visit Monte Carlo
            if s not in states[:t]:
                returns[s].append(G)
                V[s] = np.mean(returns[s])

描述：蒙特卡罗解决的是，不知道环境的状态转移概率分布的问题。

实际上从过去的经验里学习。更符合强化学习实际上的定义。

play_game函数相当于玩游戏玩一次。返回整个游戏过程的状态序列和奖励序列。

接下来通过收获的期望公式来更新收获。

为了避免重复进入相同的状态，可以设置重复的状态不再添加到收获字典里。

总的来说，每玩一次游戏，得到一个完整的回合，接着评估这个回合所有状态的收获，然后存入字典的值列表里最后用np.mean()计算均值。

重复玩游戏的次数越多，得到的价值函数越准确。

那这是怎么起作用的？
不断的迭代，准确的值不断变多

G = r + GAMMA * G  # update return

因为我们知道终止状态的奖励为0，收获也为0，那么在一次回合结束后得到的状态序列中，终止状态之前的状态的价值通过一次迭代后一定是准确的，于是知道了这个新的价值，然后再迭代，越来越准确。最后收敛。

总结

原理基本上和迭代策略评估差不多，都是这样逐渐收敛，实现方法不同。这个不需要知道状态转移概率分布。

用那个方程也是递归。求的是准确的。不过需要多个回合才能得出价值函数。

控制问题

强化学习中的控制问题，即找出最佳的策略。
在动态规划中可以使用价值迭代和策略迭代。二者速度不一样，但是本质一样。
策略迭代，是将策略随机初始化，然后通过迭代策略评估方法来找出这个策略的价值函数，再迭代每一个状态的所有行为，通过贝尔曼方程找出它的价值，然后通过与原来得到的价值相比较，如果新的更大就换，再把造成更大价值的action与之前的策略中的action更换。如此循环一段时见，直到价值变化小于一定门槛，则中断循环。

价值迭代的不同之处在于，它直接找出最好的价值函数。然后通过价值函数来找action。用的是最优贝尔曼方程。