Preface

这里开始强化学习的理论内容。虽然比较简单，但是强化学习的入门基础。在有监督学习里面，我们有明确的目标变量y作为每个样本x的标签并一一对应。通过这样一一对应的y->x的关系，我们就可以通过有监督学习算法学习到问题的模型并对新输入的样本x做出预测。然而，对于一些序列做出决策和控制，像机器人在房间里面行走，我们很难又或者明确给出y告诉机器人它的动作是否正确。所以有监督类学习算法不能处理这类的问题。强化学习可以利用在智能机器人，自动驾驶等。机器通过摸索不停修正自己错误的动作，从而学习到当中规则并在之后的做出更好的动作。在摸索的过程中，我们对机器人的每一个动作给予奖励或者惩罚，就像训练宠物一样。机器人需要尽可能拿到更多奖励，就需要修正自己的动作并尽快拿到更多的奖励。

---

MDP（Markov Decision Process）马尔科夫决策过程

• Definition

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

1. S 表示状态集 (States)；
2. A 表示动作集 (Actions)；
3. P(s′ | s, a) 表示状态 s 下采取动作 a 之后转移到 s' 状态的概率；
4. R(s, a) 表示状态 s 下采取动作 a 获得的奖励；
5. γ 是衰减因子，在0-1之间。

我们定义起始状态s_{0}并执行动作a_{0}，通过一定的随机状态转移概率，从状态s_{0}转移到s_{1}并且我们定义P(s_{1} | s_{0}, a_{0})。接下来，在状态s_{1}并执行动作a_{1}，通过一定的随机状态转移概率，从状态s_{1}转移到s_{2}并且我们定义P(s_{2} | s_{1}, a_{1})。如此类推，如下图所示：

图1：MDP的动作状态转移过程

• Reward Function

如之前所说一样，在机器人每执行一个动作到达另一个状态的时候，我们应该给予一些奖励或者惩罚，直到机器顺利达到目的地。到达目的地的时候，我们就获得了机器在这个过程的总回报。
接着我们就开始定义我们的回报函数：

图2：状态-动作回报函数

又或者是状态回报函数：

图3：状态回报函数

一般而言，我们都是使用状态回报函数，很少使用状态-动作回报函数。

我们使用强化学习目标就是让机器人通过完成一系列的动作获得最大回报，所以这里就存在一个求最大期望值的最优化问题：

图4：期望回报

这里的gamma是衰退因子，其目的是让机器人尽快获得高的回报，尽量晚的或者高的惩罚。gamma越小越要求机器人快速得到回报。

• Policy

在强化学习当中，我们通过优化期望回报函数来优化动作策略，从而使得机器人习得最优策略到达目的地。正式的，我们定义π为状态集合映射到动作集合A的策略，即S -> A。也就是在某个状态s中，我们通过最优策略π选择最好的动作a（即a = π(s)），获得更好的回报。

• Value Function

回到刚刚说的回报函数，我们在创建回报函数（图4）所示。我们需要获取机器人在活动过程中的每个状态才能得出我们回报函数。然而，这些状态-动作都来源策略。此时我们就可以定义个值函数：

图5：值函数

其中，π为固定的某一个策略，s_{0}作为起始状态。根据给出的起始状态和策略，我们可以逐步生成动作，从而去到不同的状态。

• Bellman equations

我们有了策略就可以根据当前的状态求得下一步的动作，这样我们也可以获得状态转移概率P(s′ | s, a)。这样我们就可以将图5的值函数展开，得到Bellman equations：

图6：Bellman equations

其中，R(s)为当前状态即使获得的奖励-惩罚，s′ 为下个状态，P为转移概率，V(s′ )为下个状态的值函数。如此一来我们就得到一个递归式子。

也就是说，我们需要最优化图4的期望回报，就是优化π策略使得图5值函数最大化：

图7：优化π策略的值函数

也就是优化图6的Bellman equations：

图8：优化Bellman equations

可以看到，优化Bellman equations就是一个最优子结构，这样我们就可以使用动态规划去求解最优策略π（或最大化期望回报）

假如不懂动态规划，可以看看我之前写的：强化学习[理论前奏]——动态规划

Value iteration and policy iteration

• Value iteration

根据动态规划的算法，我们就是递归求解图6的Bellman equations最优解。值迭代就是这个如此直观的原理：

图9：值迭代算法

• Policy iteration

而策略迭代则是先根据给定的策略算出每个状态的值函数，然后再优化策略，接着又根据刚刚得到的新策略再计算每个状态的值函数，再优化策略.....直到收敛。

图10：策略迭代 图11：策略迭代算法

相对而言，值迭代更加直观（动态规划），而策略迭代则是迭代贪心算法来优化期望回报直到收敛（个人认为）

Example

这里举个例子，我们在一个4×3的方格里面寻求最优的路径:

图12

其中(0, 0), (0, 3)两个位置为结束位置且reward为+1，(1, 3)的reward为-1，(1, 1)为不可行的位置，其余空格的rewards为-0.2（如机器人没走一步都会浪费汽油）。

import numpy as np

class Env(object):
    def __init__(self, row, column):
        self.rewards = np.full((row, column), -0.2)
        self.states = np.ones((row, column), dtype=np.int)
        self.states[1, 1] = -1

        self.index_list = [index for index, x in np.ndenumerate(self.states) if x > 0]
        self._init_next_state_table()

        self.rewards[0, column - 1] = 1
        self.rewards[0, 0] = 1
        self.rewards[1, column - 1] = -1

        self.terminal = [(0, column - 1), (0, 0)]

    def _init_next_state_table(self):
        self.ns_table = dict()
        for i, j in self.index_list:
            next_states = list()
            if (i - 1, j) in self.index_list:
                next_states.append((i - 1, j))
            if (i + 1, j) in self.index_list:
                next_states.append((i + 1, j))
            if (i, j - 1) in self.index_list:
                next_states.append((i, j - 1))
            if (i, j + 1) in self.index_list:
                next_states.append((i, j + 1))
            self.ns_table[(i, j)] = next_states

    def get_reward(self, i, j):
        return self.rewards[i, j]

    def get_states(self):
        return self.states

class Robot(object):

    def __init__(self, env, gamma):
        self._env = env
        self._gamma = gamma
        self.values = np.zeros_like(env.get_states(), dtype=np.float32)

    def best_value_func(self, i, j):
        if (i, j) in self._env.terminal:
            return self._env.get_reward(i, j)
        else:
            return self._env.get_reward(i, j) + self._gamma * max(self.next_states_expected_value(i, j))

    def update_values(self):
        for i, j in self._env.index_list:
            self.values[i, j] = self.best_value_func(i, j)

    def next_states_expected_value(self, i, j):
        next_values = []
        ns_num = len(self._env.ns_table[(i, j)])

        if ns_num == 1:
            ps = [1]
        elif ns_num == 2:
            ps = [0.9, 0.1]
        elif ns_num == 3:
            ps = [0.8, 0.1, 0.1]
        elif ns_num == 4:
            ps = [0.7, 0.1, 0.1, 0.1]
        else:
            raise Exception("we must has state transition probability")

        for next_index in self._env.ns_table[(i, j)]:
            other_index = [index for index in self._env.ns_table[(i, j)] if index != next_index]
            ns_index = [next_index] + other_index
            values = [self.values[i, j] for i, j in ns_index]
            next_values.append(np.multiply(values, ps).sum())
        return next_values

    def best_policy(self, i, j):
        if (i, j) not in self._env.terminal:
            print("(%d, %d)" % (i, j), end=" -> ")
            next_states = self._env.ns_table[(i, j)]
            best_state_index = np.argmax(self.next_states_expected_value(i, j))
            best_state = next_states[best_state_index]
            return self.best_policy(best_state[0], best_state[1])
        print("(%d, %d)" % (i, j))
        return

gamma = 0.9
env = Env(3, 4)
robot = Robot(env, gamma)

for _ in range(10):
    robot.update_values()

print(robot.values)
print("-------------------------")
robot.best_policy(2, 3)

最后得到结果：

最后结果

---

References

• http://cs229.stanford.edu/notes/cs229-notes12.pdf
• https://zhuanlan.zhihu.com/p/21378532
• https://en.wikipedia.org/wiki/Markov_decision_process