马尔可夫决策过程（Markov Decision Process, MDP）
马尔可夫决策过程（Markov Decision Processes,MDPs）
MDPs
简单说就是一个智能体（Agent）采取行动（Action）从而改变自己的状态（State）获得奖励（Reward）与环境（Environment）发生交互的循环过程。
绝大多数的增强学习都可以模型化为MDP的问题。MDP 的策略完全取决于当前状态，这也是它马尔可夫性质的体现，根据当前的状态来决定动作。元组表示为：
状态的好坏其实等价于对未来回报的期望。因此，引入回报来表示某个时刻t的状态将具备的回报，我们的目标是选择一组最佳的action，使得全部的回报加权和期望最大：
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131117427831.png>
从上式可以发现，在t时刻的回报值被打了
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131117427897.png>
的折扣，是一个逐步衰减的过程，越靠后的状态对回报和影响越小。
定义在当前状态下，执行某个策略
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131117592471.png>
后，出现的结果的好坏，需要定义值函数（value function）
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118004174.png>
然而，在当前状态下，一个动作
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118042194.png>
可以产生不同的结果，由Bellman等式，根据转移概率从上式得到，其中s’表示下一个状态：
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118093528.png>
当然，我们求V的目的就是想找到一个当前状态s下，最优的行动策略
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118116234.png>
，定义最优的V*，即从可选择的策略
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118128842.png>
挑选一个最优策略，如下：
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118114315.png>
上式的Bellman等式形式如下，第二项是一个
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118147088.png>
就决定了每个状态s的下一步动作a，执行a后，s’按概率分布的回报概率和的期望：
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118126399.png>
定义了最优的V*，我们再定义最优的策略
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118156140.png>
如下：
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118157809.png>
选择最优的
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118163731.png>
，也就确定了每个状态s的下一步最优动作a，根据以上式子，我们可以知道
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118175990.png>
当前状态的最优的值函数V*，是由采用最优执行策略
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118178008.png>
的情况下得出的，采用最优执行方案的回报显然要比采用其他的执行策略
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118189502.png>
要好。
这里需要注意的是，如果我们能够求得每个s下最优的a，那么从全局来看，
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118224915.png>
的映射即可生成，而生成的这个映射是最优映射，称为
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118263359.png>。
<http://images.cnblogs.com/cnblogs_com/jerrylead/201105/201105131118272030.png>
针对全局的s，确定了每一个s的下一个行动a，不会因为初始状态s选取的不同而不同。
Exploration and Exploitation 探索与利用
在上面的算法中，我们可以看到需要使用某一个policy来生成动作，也就是说这个policy不是优化的那个policy，所以Q-Learning算法叫做Off-policy的算法。另一方面，因为Q-Learning完全不考虑model模型也就是环境的具体情况，只考虑看到的环境及reward，因此是model-free的方法。
回到policy的问题，那么要选择怎样的policy来生成action呢？有两种做法：
* 随机的生成一个动作
* 根据当前的Q值计算出一个最优的动作，这个policy ππ称之为greedy policy，也就是
π(St+1)=argmaxaQ(St+1,a)π(St+1)=argmaxaQ(St+1,a)
使用随机的动作就是exp成loration，也就是探索未知的动作会产生的效果，有利于更新Q值，获得更好的policy。而使用greedy
policy也就是target
policy则是exploitation，利用policy，这个相对来说就不好更新出更好的Q值，但可以得到更好的测试效果用于判断算法是否有效。
将两者结合起来就是所谓的ϵ−greedyϵ−greedy policy,ϵϵ一般是一个很小的值，作为选取随机动作的概率值。可以更改ϵ
的值从而得到不同的exploration和exploitation的比例。
Q-learning
Q-learning的核心是Q-table。Q-table的行和列分别表示state和action的值，Q-table的值Q(s,a)
Q Learning的思想完全根据value iteration得到。但要明确一点是value
iteration每次都对所有的Q值更新一遍，也就是所有的状态和动作。但事实上在实际情况下我们没办法遍历所有的状态，还有所有的动作，我们只能得到有限的系列样本。因此，只能使用有限的样本进行操作。那么，怎么处理？Q
Learning提出了一种更新Q值的办法：
Q(St,At)←Q(St,At)+α(Rt+1+λmaxaQ(St+1,a)−Q(St,At))
虽然根据value iteration计算出target
Q值，但是这里并没有直接将这个Q值（是估计值）直接赋予新的Q，而是采用渐进的方式类似梯度下降，朝target迈近一小步，取决于αα
,这就能够减少估计误差造成的影响。整个训练过程其实就是原始Q值向目标 Q 值逼近的过程。类似随机梯度下降，最后可以收敛到最优的Q值。
具体的算法如下：
初始化Q(s,a),∀s∈S,a∈A(s)Q(s,a),∀s∈S,a∈A(s), 任意的数值，并且Q(terminal−state,⋅)=0
Q(terminal−state,⋅)=0
重复（对每一节episode）:
初始化 状态S
重复（对episode中的每一步）：
使用某一个policy比如（ϵ−greedyϵ−greedy)根据状态S选取一个动作执行
执行完动作后，观察reward和新的状态S′S′
Q(St,At)←Q(St,At)+α(Rt+1+λmaxaQ(St+1,a)−Q(St,At))
Q(St,At)←Q(St,At)+α(Rt+1+λmaxaQ(St+1,a)−Q(St,At))
S←S′S←S′
循环直到S终止
Deep-Q-learning
q-table存在一个问题，真实情况的state可能无穷多，这样q-table就会无限大，解决这个问题的办法是通过神经网络实现q-table。输入state，输出不同action的q-value。
<>Experience replay
强化学习由于state之间的相关性存在稳定性的问题，解决的办法是在训练的时候存储当前训练的状态到记忆体MM，更新参数的时候随机从MM
中抽样mini-batch进行更新。
具体地，MM中存储的数据类型为 <s,a,r,s′><s,a,r,s′>，MM有最大长度的限制，以保证更新采用的数据都是最近的数据。
<>Exploration and Exploitation 探索与利用
在上面的算法中，我们可以看到需要使用某一个policy来生成动作，也就是说这个policy不是优化的那个policy，所以Q-Learning算法叫做Off-policy的算法。另一方面，因为Q-Learning完全不考虑model模型也就是环境的具体情况，只考虑看到的环境及reward，因此是model-free的方法。
回到policy的问题，那么要选择怎样的policy来生成action呢？有两种做法：
* 随机的生成一个动作
* 根据当前的Q值计算出一个最优的动作，这个policy ππ称之为greedy policy，也就是
π(St+1)=argmaxaQ(St+1,a)π(St+1)=argmaxaQ(St+1,a)
使用随机的动作就是exploration，也就是探索未知的动作会产生的效果，有利于更新Q值，获得更好的policy。而使用greedy
policy也就是target
policy则是exploitation，利用policy，这个相对来说就不好更新出更好的Q值，但可以得到更好的测试效果用于判断算法是否有效。
将两者结合起来就是所谓的ϵ−greedyϵ−greedy policy,ϵϵ一般是一个很小的值，作为选取随机动作的概率值。可以更改ϵϵ
的值从而得到不同的exploration和exploitation的比例。
<>算法