网易公开课，第16课
notes，12
前面的supervised learning，对于一个指定的x可以明确告诉你，正确的y是什么
但某些sequential decision making问题，比如下棋或直升机自动驾驶
无法确切知道，下一步怎么样是正确的，因为这是一个连续和序列化的决策，比如直到最终直升机crash或下棋输了，你才知道之前的选择是不好的，但中间那么多步决策，到底是哪部分出了问题，可见这是个比较复杂的问题
强化学习，基本思路就是，既然不知道怎样是正确的，那就随便try，然后根据反馈好坏来，逐步强化得到正确结果的行为
挺有意思的，想想人学习的过程，
比如大家都学过自行车，这个不是别人和你说下步怎么做，你就能会的，开始你也不知道如何骑
只能试，如果摔倒了，潜意识的就会改变步骤，如果可以骑起来了，就会强化刚才的步骤，慢慢身体就学会了骑车，这就是典型的强化学习
Markov decision processes
A Markov decision process is a tuple 
, where:
马尔可夫决策过程，可以表示成5元组
S，set of states. 状态集合，对于直升机驾驶，就是当前的位置和方向
A，set of actions. 行为集合，对于直升机驾驶，就是下一步采取的操控，上，下，左右，前后等
，state transition probabilities. 状态迁移的概率分布，因为在s状态采取a行为，最终达到的状态是有一定随机性的，这个体现出markov过程
比如，你让直升机像右移动，但是比如因为风或其他noise，它移动到右前方向，或右后方，或前方，都是有可能的，所以要用概率来表示。
，discount factor. 后面会看到，这个参数用于调整，当前决策和未来决策之间的权重
，reward function. 表示在s状态做a行为得到的反馈，回报函数。
，常常回报函数仅仅以状态为参数，理解为转移到当前状态，对于最终达到好的结果有多大的作用
大家可以想象，Markov决策过程应该就是如图这个过程
那么这个过程中reward function的和为，这里看到发挥左右，往往取值0.99，后面的reward function乘上
，像是做discount
表达的意思，越早的决策越重要，是不是比较合理
即，
那么我们强化学习的目标就是，maximize the expected value of the total payoff
这个不难理解，reward function的值越大，表示越正确
比如看NG的例子，12格，其中一格为障碍，最终到达+1格（4，3）为成功，到达-1格（4，2）为失败
假设起始点为图中的（3，1），采取的action为N，即朝北走，图中就是上方，有
朝上走，
到达（3，2）的概率最大，0.8
作为扰动noise，也有0.1的概率会到达（4，1），或（2，1）
到达其他格的概率为0
看看如何设置reward function的值？
到达（4，3），即成功，reward function为1
（4，2）为失败，reward function为-1
其他格的reward function都设置为-0.02
这是一个技巧，把剩余的格都设为很小的负面奖励，对于导航或机器人，每多走一步意味着耗费更多的电或能源
如果要reward function和最大，必须尽量最小step数
Bellman equations
，定义从S到A的映射关系的函数，即在某个状态下对应哪个action，称为policy
那么显然我们的目的，就是找到使total payoff最大的那个policy函数
那么定义，起点为s，policy为
，最终过程的total payoff为
，称为的value function，值函数
上面这个式子，可以写成下面这种递归的形式，
其中s1，即
是未知的，有多种可能性，上面的式子写成
这就称为Bellman equation
分为两部分，
其中R(s)，为immediate reward，即刻回报
第二部分，future discounted rewards，也可以写成
Bellman equation的用处是，可以求出
在reward function R(s)已知的情况下，直接求，比较困难，因为在马尔可夫决策过程中，每步的s是不确定的
而用Bellman等式，可以为每个s列出这样一个等式，
把作为变量，对于n个状态，就会有n个变量，通用有n个bellman等式，通过解方程组，就可以解出每个
还是看上面的例子，
下图表示一个policy，可以看到画出每一格上，选择移动的方向，即action
现在为状态（3，1）列出bellman等式，其中画框的都是变量
当为每个状态都列出上面这样的等式时，就可以通过解方程组，解出变量值
从而求得， 如下图
好，继续定义
我们的目的是找到使最大的那个
即，因为R(s)是常数，所以得到Bellman等式的另一种表示
那么我们定义，
，使得，
这就是我们要找的最佳的policy
Value iteration and policy iteration
那么现在介绍算法来求解上面的最优问题，介绍的算法只针对有限的状态和actions的MDPs
Value iteration
算法挺简单，就是用Bellman等式不断去更新V，可以证明V是会收敛于V*的
在得到V*后，用
就可以求出
如图，还是上面的例子在（3，1），如何定policy？根据上面的式子分别算出往W或往N的值，发现往w是更优的policy
其中更新V的有异步和同步两种，
同步是把所有s的新的V都算出来后，一次性更新所有的V
异步是算一个更新一个，那么后面s的V的计算就会用到前面更新的V
Policy iteration
随机指定，然后通过Bellman等式的方程组解出，根据新的来更新。。。。。。
这两个算法都是会收敛的，
Policy iteration在状态比较少的时候会收敛更快，但是不能用于huge状态集的MDP，因为需要求解方程组来得到，开销太大
所以对于比较大的状态集的MDP，往往使用，value iteration
Learning a model for an MDP
前面的算法都是基于一个假设，即，state transition probabilities and rewards function是已知的
但是很多情况下，它们是未知的，所以我们需要去estimate出它们
其中rewards function一般也是已知的，因为这个是你提供的，你应该知道，除了些特例
所以下面就特别看下state transition probabilities是如何预估的，
其实很简单，多试几次，然后根据实际情况统计即可，
并且这个P应该可以线上不断更新，会更为准确
并且对于0/0的case，用1/|s|替代
Using a similar procedure, if R is unknown, we can also pick our estimate of the expected immediate reward R(s) in state s to be the average reward
observed in state s.
如果R未知，也可以用实验中观察到的均值来作为估计值，我不太明白，实验中怎么能观察到reward function的值？
本文章摘自博客园，原文发布日期：2014-08-21
