机器学习一共有三个分支，有监督学习、无监督学习和强化学习。强化学习是系统从环境学习以使得奖励最大的机器学习。强化学习和有监督学习的不同在于教师信号。强化学习的教师信号是动作的奖励，有监督学习的教师信号是正确的动作。

1. 马尔科夫决策过程

要说强化学习，就必须说说马尔科夫决策过程 (Markov Decision Processes, MDP)。马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的决策过程，其分五个部分：

和一般的马尔科夫过程不同，马尔科夫决策过程考虑了动作，即系统下个状态不仅和当前的状态有关，也和当前采取的动作有关。还是举下棋的例子，当我们在某个局面（状态s）走了一步 (动作 a )。这时对手的选择（导致下个状态 s’ ）我们是不能确定的，但是他的选择只和 s 和 a 有关，而不用考虑更早之前的状态和动作，即 s’ 是根据 s 和 a 随机生成的。
下图是一个机器人从任意一个状态出发寻找金币的例子。找到金币则获得奖励 1，碰到海盗则损失 1。找到金币或者碰到海盗则机器人停止。

我们可以把这个问题建模成马尔科夫决策过程。图中不同位置为状态，因此 S = {1,...,8}。机器人采取动作是向东南西北四个方向走，因此A={'n','e','s','w'}。转移概率方面，当机器人碰到墙壁，则会停在原来的位置；当机器人找到金币时获得奖励 1，当碰到海盗则损失 1, 其他情况不奖励也不惩罚。因此除了 R1,s=−1 , R3,s=1 ， R5,s=−1 之外，其他情况 R∗,∗=0 。衰减因子 γ 在后面介绍。写成代码下面所示：

    class Mdp():
        def __init__(self):
            self.states = [1, 2, 3, 4, 5, 6, 7, 8]

            self.terminal_states = dict()
            self.terminal_states[6] = 1
            self.terminal_states[7] = 1
            self.terminal_states[8] = 1

            self.actions = ['e', 'w', 's', 'n']

            self.rewards = dict()
            self.rewards['1_s'] = -1.0
            self.rewards['3_s'] = 1.0
            self.rewards['5_s'] = -1.0

            self.t = dict()
            self.t['1_s'] = 6
            self.t['1_e'] = 2
            self.t['2_w'] = 1
            self.t['2_e'] = 3
            self.t['3_s'] = 7
            self.t['3_w'] = 2
            self.t['3_e'] = 4
            self.t['4_w'] = 3
            self.t['4_e'] = 5
            self.t['5_s'] = 8
            self.t['5_w'] = 4

            self.gamma = 0.8

    def transform(self,state,action):
        if state in self.terminal_states:
            return True, state, 0

        key = '%d_%s'%(state,action)
        if key in self.t:
            next_state = self.t[key]
        else:
            next_state = state
        is_terminal = False
        if next_state in self.terminal_states:
            is_terminal = True

        if key not in self.rewards:
            r = 0.0
        else:
            r = self.rewards[key]
        print(is_terminal,next_state,r)
        return is_terminal, next_state, r

import random

demo = Mdp()
is_terminal=False
init_state = 1

while(is_terminal==False):
    action = random.randint(0,3)
    is_terminal,state,r = demo.transform(init_state,demo.actions[action])

马尔科夫决策过程是强化学习的理论基础。不管我们是将强化学习应用于五子棋游戏、星际争霸还是机器人行走，我们都假设背后存在了一个马尔科夫决策过程。只不过有的时候我们知道马尔科夫决策过程所有信息(状态集合，动作集合，转移概率和奖励)，有的时候我们只知道部分信息 (状态集合和动作集合)，还有些时候马尔科夫决策过程的信息太大无法全部存储 (比如围棋的状态集合总数为 319×19 )。强化学习算法按照上述不同情况可以分为两种: 基于模型 (Model-based) 和非基于模型 (Model-free)。基于模型的强化学习算法是知道并可以存储所有马尔科夫决策过程信息，非基于模型的强化学习算法则需要自己探索未知的马尔科夫过程。

2、策略和价值

强化学习技术是要学习一个策略 (Policy)。这个策略其实是一个函数，输入当前的状态 s，输出采取动作 a 的概率 π(s,a) 。有监督学习希望分类器正确地对实例分类，那么强化学习的目标是什么呢？强化学习希望把策略训练什么样呢？ 假设我们的系统在一个状态 s 中，我们不会选择当前奖励 Rs,a 最大的动作 a。因此这个动作可能导致系统进入死胡同，即系统之后会受到很大的处罚。为了避免这种情况，策略要考虑到后续的影响。因此我们最大化递减奖励的期望：

其中 γ 是马尔科夫决策过程的第五个部分：衰减因子。 γ 用于平衡当前奖励和远期奖励的重要性，也是用来避免计算结果无穷。 Rk 是系统在当前策略下第 k 步之后获得的奖励。这种目标既考虑了当前奖励又考虑了远期奖励，避免了下一个状态是死胡同的问题。
根据上面的目标，人们提出了价值的概念。一个策略下的一个状态的价值定义：这个状态下，按照这个策略，系统能够获得的递减奖励期望。

上面机器人找金币的例子中，设定衰减因子 γ
等于 0.5。如果策略是一直往西走碰壁之后立马向南，那么状态 2 的价值 v(2)=0+0.5∗−1.0=−0.5
。如果策略是随机一个方向，那么所有状态的价值如下图所示。

3、最优策略存在性和贝尔曼等式

根据上面的介绍，我们发现强化学习的目标是找到一个策略 π , 使得这个策略下每个状态的价值最大。但是这里有一个问题啊。对于两个策略，有可能出现：策略 π1 状态 a 的价值大于策略 π2 状态 b 的价值，但策略 π2 状态 c 的价值大于策略 π1 状态 d 的价值。因此我们不确定，是否存在一个策略 pi 的所有状态价值大等于其他策略的状态价值。如果不存在这么一个策略，我们的目标是迷茫的。
但是万幸啊，下面的定理保证了这么一个策略存在。这么一个所有状态价值大等于其他所有的状态价值，我们可以称之为最优策略。强化学习算法的目标就是找到最优策略。

另外一个重要的点是贝尔曼等式。贝尔曼登等式表明了当前状态的值函数与下个状态的值函数的关系，具有很简明的形式。

关于贝尔曼等式中的各个部分，可以看下面的解释：