强化学习入门——说到底研究的是如何学习
自机器学习重新火起来，深度强化学习就一直是科研的一大热点，也是最有可能实现通用人工智能的一个分支。然而对于没有强化学习基础的同学们，如果直接去学习深度强化学习，想必会碰到很多问题。本文尝试普及一些最基础的强化学习算法，并以一个小例子来辅助大家理解。
强化学习究竟研究的是一个什么样的问题，让其具有实现通用人工智能的潜力？
这个问题与我们认识世界的方式相关。我们都知道这个世界时刻在变化着，而每件事物的变化，势必是由其他一系列事物导致的。这就是我们所普遍认识的世界，一个由因果律定义的世界。由于因果律的存在，我们就有可能根据某个当前世界的状态，计算后一时刻世界的状态。
而我们人类，作为一个智能体，通过观察这个世界，并进行各种各样的自主行动，在这个世界中生存，并对其产生影响。通用人工智能的实现，就是期望能通过计算机模拟人类这样的智能体进行各种各样的行动决策。
为了简化问题，我们可以像下面这样建模这个世界和智能体。我们可以认为在某一个时刻整个世界处于状态S1，当智能体进行了某一个行动之后，这个世界的状态变化为了S2。智能体之所以能够做出这一行动，是因为其心中有一个目标，并且从这个世界中得到了一定的反馈。
举个例子。比如我们想要喝水（目标），身边有一个杯子和一个饮水机（状态S1），我们会观察杯子和饮水机的位置，再伸手去拿取杯子（行动），然后将杯子靠近（反馈）饮水机，到达饮水机出水位置之后（状态S2），饮水机开始出水，之后我们再将杯子举到嘴边就能喝到水了。这个简单的模型可以图示如下：
智能体（Agent）通过观察这个世界（Environment）的状态（State: s），经过智能决策，开展了一些行动（Actions: a），这些行动进而引起了这个世界的状态变化。智能体从这些变化的状态中获得关于之前行动的反馈（Reward: r），从而指导后续的行动决策。就这样，整个世界周而复始的一直循环下去。
从这个模型出发，由于因果律的存在，是不是知道了S1这个初始状态及智能体做出的行动A之后，我们就可以直接计算下一状态S2了呢？理论是可行的，但实际情况要更复杂一些，因为状态实在太多太多了，我们通常无法直接建模所有的状态。这时，我们可以用统计学的方式来解决这个问题。我们可以认为在我们做出某一行动之后，这个世界的状态只是有一定概率会转换为S2，同时也有一定的概率会转换为S2_1等等。这样就算我们建模的状态不全，也可以相对较好的描述这个系统。
引入统计学的思维，也就引入了不确定性，虽然如此，但是却带来了更合理的描述系统的方式和系统层面的确定性。
以上描述的这一模型，在强化学习的世界里，我们称作Markov决策过程，简称MDP（Markov Decision Process）。这里面的不确定性也就是Markov特性。
有了这个模型之后，我们就可以从数学上来研究这个问题了。强化学习研究的正是如何在这样的一个数学模型的基础上去实现一个有效的算法，进而实现智能决策。
一个小例子
我们可以设计一个简单的小游戏来辅助解决这个问题。
如上图，机器人（智能体）可以在这样的网格中移动：
绿色格子代表机器人可以移动到的位置 灰色格子表示有障碍物，机器人不能移动到那个位置 红色格子表示一个陷阱，如果机器人移动到此，游戏失败 黄色格子代表一个出口，如果机器人移动到此，游戏成功
系统状态：格子位置，机器人位置 机器人可执行的动作：向上下左右四个方向移动 状态转换概率：如果机器人向某个方向移动，它移动到对应方向的格子的概率假设为0.7（如果无法移动到对应方向的位置，则留在原格子的概率为0.7），移动到其他位置的概率为0.3/n，n为其他可转换到的状态的数量。
假设机器人在位置A2，如果其向上移动，有70%的概率会移动到A1，分别有15%的概率会移动到A2（留在原位）和A3 假设机器人在位置A2，如果其向左或向右移动，有70%的的概率会留在原位A2，分别有15%的概率会移动到A1和A3
向右移动：0.7 * 1 = 0.7 向上/下/左移动：0.1 * 1 = 0.1
向右移动：0.7 * (0 + 0.7) = 0.49 向上/下/左移动：0.1 * (0 + 0.7) = 0.07 格子价值：max([0.49, 0.07, 0.07, 0.07]) = 0.49
（表示每个动作的价值，其中：s表示当前状态；a表示动作；s'表示下一个状态；T(s, a, s')表示在状态s，执行动作a转换到状态s'的概率；R(s, a, s')表示表示在状态s，执行动作a转换到状态s'得到的奖励）
var values = m.zeroArray([this.states.length]);
var valuesNew = values;
var iterations = 0;
do {
var qValuesAll = [];
values = valuesNew;
valuesNew = [];
for (var i = 0; i < this.states.length; i++) {
var state = this.states[i];
var qValues = this.qValues(values, state);
qValuesAll.push(qValues);
var value = this.value(qValues);
valuesNew.push(value);
}
console.log('finished iteration ' + (++iterations));
// console.log('values: ', values);
} while(!this.converged(values, valuesNew));
...
}
这里我已经实现了上述的游戏的一个Demo，见这里（http://brightliao.com/examples/mdp/grid-world.html），完整代码见这里（https://github.com/gmlove/gmlove.github.io/blob/source/source/examples/mdp/grid-world.js）865行到890行。
计算在当前策略下，哪一个行动能得到最大价值 选择价值最大的行动作为新策略的行动
MDPPISolver.solve = function () { var policy = this.randomPolicy(); var policyNew = policy; do { policy = policyNew; values = this.solveForPolicy(policy); policyNew = this.improvePolicy(values, policy); } while (!this.converged(policy, policyNew)); ...}
完整代码见这里（https://github.com/gmlove/gmlove.github.io/blob/source/source/examples/mdp/grid-world.js）932行到1024行。
扩展
状态空间降维
离最近的豆子的方向和距离 离每个敌人的方向和距离 敌人的移动速度和方向