一、强化学习
强化学习和遗传算法优胜劣汰的思想类似，通过奖惩机制不断强化好的行为（action），弱化坏的行为。至于什么是好的行为，什么是坏的行为，跟你要解决的具体问题有关，比如路径规划问题，走距离目标点较近的路线就是好的行为，走距离目标点较远的路线就是坏的行为。
强化学习包含四要素：agent、环境状态、动作和奖励，目标是获得最多的累计奖励。
二、强化学习原理
2.1 贝尔曼方程
强化学习是基于贝尔曼方程构建的。
贝尔曼方程说的是：如果从最佳路径的开头截除一小部分，那么余下的路径仍然是最佳路径。
例如，你从香港乘车到北京，选择了最便宜的路线，此路线经过 10 个车站，第二站是深圳：如果除去出发点香港站，那么由第二站深圳到最后的北京站：
仍然应该是最便宜的路线。
用数学语言表达就是：
2.2 从机器学习的角度上，表述贝尔曼方程
根据经验，我们知道，机器学习中的最优值永远都不是一蹴而就，而是朝着最优值的方向一步一步的迭代更新而来。
Delta rule
这是在机器学习中经常出现的更新规则。假设我们有一个目标，我们现在要逐步调整当前状态，令它慢慢趋近这个目标。方法是：其中 𝛼 叫学习速率，是一个 0 到 1 之间的小数。Delta(Δ) 指的是目标和现状的差异。显然，反复执行上式，当前状态就会逐步逼近目标。
应用了Delta rule和衰减因子的贝尔曼方程
其中 𝛾 同样是一个 0 到 1 之间的小数，为什么会有这个衰减因子的存在呢？因为在实际中，有些情况需要重视长远的收益，而有些情况则需要更重视眼前的收益。
例如我们玩这个游戏时，就应该把主要精力放在眼前的两个关卡上。
我们知道，越是靠近目标状态的状态，其到目标状态之间最大奖励就越容易计算。例如天津到北京的最便宜路线，肯定比香港到北京的最便宜路线更容易计算。所以在强化学习的训练过程后续状态先收敛到最优值
。
然后根据贝尔曼方程就可以把后续状态的最优值反馈给当前状态，这样不断的迭代下去，所有的状态都可以收敛到最优值。
三、Q learning
Q learning 最重要的数据结构为 Q 表，Q 是 quality 的缩写。算法最终就是要学习到一张好的 Q 表，这样我们就可以根据 Q 表对环境中的任何情况（状态）都能给出一个好的反应（动作）。具体的，就是每次都选择 Q 表中对应状态下具有最大 Q 值的动作。
动作可以看作是状态之间转换的桥梁。
0 代表不能向对应方向移动的地形边缘。
-greedy 策略
伪码中说，按照一定的策略选择动作，那为什么不是每次按照 Q 表选择对应 Q 值最大的动作呢？
一般在训练时，通过 epsilon（）参数控制 agent 的贪婪程度，例如 epsilon = 0.9，表示 90% 的时间使用 Q 表做决策，10% 的时间随机选择动作来探索未知的环境。
java 实现的小例子
问题：最短路径，寻找起始点A到目标点D的最短路径。
package main;
import java.util.Arrays;
public class Qlearning {
public static void main(String[] args) {
double[][] Q = new double[][] {
{-1, 0, 0, -1},
{-1, -1, -1, 0},
{-1, -1, -1, 0},
{-1, -1, -1, -1}
};
int[][] graph = new int[][] {
{0, 3, 2, 0},
{0, 0, 0, 1},
{0, 0, 0, 4},
{0, 0, 0, 0}
};
double epsilon = 0.8;
double alpha = 0.2;
double gamma = 0.8;
int MAX_EPISODES = 400; // 一般都通过设置最大迭代次数来控制训练轮数
for(int episode = 0; episode < MAX_EPISODES; ++episode) {
System.out.println("第"+episode+"轮训练...");
int index = 0;
while(index != 3) { // 到达目标状态，结束循环，进行下一轮训练
int next;
if(Math.random() < epsilon) next = max(Q[index]); // 通过 Q 表选择动作
else next = randomNext(Q[index]); // 随机选择可行动作
int reward =5 - graph[index][next]; // 奖励
Q[index][next] = (1-alpha)*Q[index][next] + alpha*(reward+gamma*maxNextQ(Q[next]));
index = next; // 更新状态
}
}
System.out.println(Arrays.deepToString(Q));
}
private static int randomNext(double[] is) { // 蓄水池抽样，等概率选择流式数据
int next = 0, n = 1;
for(int i = 0; i < is.length; ++i) {
if(is[i] >= 0 && Math.random() < 1.0/n++) next = i;
}
return next;
}
private static int max(double[] is) {
int max = 0;
for(int i = 1; i < is.length; ++i) {
if(is[i] > is[max]) max = i;
}
return max;
}
private static double maxNextQ(double[] is) {
double max = is[0];
for(int i = 1; i < is.length; ++i) {
if(is[i] > max) max = is[i];
}
return max;
}
}
Q 表的更新过程：
第三个 Q 表其实已经收敛。
(1-0.2)*4.56 + 0.2*(2+0.8*3.2)=4.56
(1-0.2)*3.16 + 0.2*(3+0.8*0.2)=3.16
(1-0.2)*3.2 + 0.2*(4-0.8)=3.2
(1-0.2)*0.2 + 0.2*(1-0.8)=0.2
对照着公式，通过手工计算可以看到所有的 Q 值已经趋于稳定，继续迭代，Q 值也不会发生更新。
对比 Q 表的更新过程可以发现，刚开始时，还会选择 A->C 这条路径，因为短期从 A->C 能够获得更多的奖励，但是当接受到未来奖励的反馈后，开始逐渐倾向于 A->B，并最终选择 A-> B 路径，因为从 B->D 会获得比从 C->D 大得多的奖励。这也体现了强化学习延迟反馈的特征。
参数设置对模型的影响：
- epsilon 过大，模型不容易收敛。
- alpha 过小，模型不容易收敛。
- gamma 改变最终的收敛结果也会改变。
代码中用到了蓄水池抽样技术，可以等概率的选择流式数据，如果对蓄水池抽样感兴趣可以看看这篇文章。
文中部分图片非原创。
参考：
https://www.zhihu.com/question/41775291/answer/93276779
