11. 深度学习——强化学习

机器学习面试题汇总与解析——强化学习

本章讲解知识点

1. 什么是强化学习
1. 围棋举例
1. 强化学习的两个特点和一个核心
1. 最简单的强化学习算法
1. 一个完整的强化学习问题
1. 进一步深入强化学习的核心

本专栏适合于Python已经入门的学生或人士，有一定的编程基础。
本专栏适合于算法工程师、机器学习、图像处理求职的学生或人士。
本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵
如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。
相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。

关于机器学习算法书籍，我强烈推荐一本《百面机器学习算法工程师带你面试》，这个就很类似面经，还有讲解，写得比较好。
关于深度学习算法书籍，我强烈推荐一本《解析神经网络——深度学习实践手册》，简称 CNN book，通俗易懂。

1. 什么是强化学习

1.1 基本概念

强化学习（Reinforcement Learning）是机器学习的一个分支，通过智能体（Agent）与环境的交互学习最优策略来解决问题。在强化学习中，智能体通过观察环境的状态，采取特定的行动，并从环境中获得奖励或惩罚。智能体的目标是通过与环境的交互，学习出使累计奖励最大化的最优策略。

简而言之，强化学习，是智能体在与环境的互动当中，为了达成一个目标而进行的学习过程。

强化学习在许多领域都有广泛的应用，例如机器人控制、游戏智能、自动驾驶等。它能够在面对复杂、未知或动态的环境中进行决策，并能够通过与环境的交互不断改进策略，具有很强的适应性和灵活性。

1.2 强化学习基本元素（第一层结构）

1.Agent（智能体）：

智能体是强化学习系统中的决策主体，可以是一个机器学习算法、机器人或其他人工智能实体。
智能体通过与环境进行交互来学习和改进自己的策略。

2.Environment（环境）：

环境是智能体所处的外部世界，可以是真实的物理环境、虚拟环境或模拟器。
环境可以对智能体的动作做出响应，提供反馈信息（奖励或惩罚）和更新状态。

3.Goal（目标）：

目标是强化学习的最终目标或任务，智能体需要通过学习和决策来达到或优化目标。
目标可以是预定义的，也可以是根据智能体与环境的交互动态设定的。

1.3 强化学习主要元素（第二层结构）

1.State（状态）：

状态表示环境在某一时刻的特定情况或特征。如机器人的坐标、敌人的坐标。
状态可以是离散的（如迷宫中的位置）或连续的（如机器人的传感器读数）。

2.Action（动作）：

动作是智能体基于当前状态所选择的行为或决策。
动作可以是离散的（如向左或向右移动）或连续的（如机器人的速度控制）。

3.Reward（奖励）：

奖励是环境提供给智能体的即时反馈，用于评估智能体的行为。
奖励可以是正数（奖励）、负数（惩罚）或零（中性）。

1.4 强化学习核心元素（第三层结构）

1.Policy（策略）

在某一个状态下应该采取什么样的行动。简单来说，在数学上，策略就是一个函数，输入当前状态，输出对应动作。很显然，强化学习需要达到的目的就是学习到一个好的策略。

2.Value（价值）

价值同样是一个函数，并且策略函数就取决于价值函数。

价值函数分为两种，一种是状态价值函数，顾名思义，就是输入当前状态，输出状态对应的实数，这个实数就称为对应状态的价值，价值的概念很重要，它指的是预期将来会得到的奖励之和，即处于当前状态下，玩家将来预期得到的所有奖励的一个期望值，玩家的目标就是得到的奖励之和尽可能大，因此通过状态价值函数，玩家应选择进入价值尽可能大的状态，而这是通过特定的行动来实现的，这就是状态价值函数决定了玩家的策略。

另一种价值函数则是状态-行动价值函数，顾名思义，它不单单是指一个状态对应的价值，而是在特定状态下，采取某种行动对应的价值，根据状态-行动价值函数，玩家应该选择价值最大的那一个行动。

1.5 总结

强化学习需要学习的一个东西就是好的价值函数，一个好的价值函数决定了一个好的策略。所有元素之间的关系可以用下图表示：

alt

2. 围棋举例

我们以围棋举例强化学习的过程：

首先第一层结构：

首先 Agent 就是“我”，Environment（环境） 包括了这个棋盘和“我”的对手；Goal（目标） 就是赢得围棋胜利。

然后第二层结构：

State（状态），在围棋中很简单，也就是棋盘中棋子的分布情况，那么我们目前处于棋盘上没有棋子的状态，我们称之为 State1：

alt

现在假如我执白先行，“我”作为一个玩家，即 Agent，在当前状态下，需要做出某种行动 Action（动作），“我”首先在星位落子，这就是一个行动，我们不妨称之为 Action1：

alt

在“我”采取了该行动之后，我会得到一个即时的反馈，也就是 Reward（奖励） ，对于围棋来说，一个好的强化学习模型，奖励应该是 0，除非达到赢棋的最终状态，所以在这里，Reward1=0。这样就是一个完整的二层结构。

有了行动，对应即时的奖励，同时环境会对这个行动做出响应，比如“我”的对手落子在小目，这就进入了下一个状态 State2，一颗黑棋落在了左下方的星位，一颗白棋落在了右上方的小目。

alt

接下来再进入 Action2、Reward2，再进入 State3，如此下去，直到棋局结束。这就是第二层结构

接下来我们看第三层结构，Policy（策略） 和 Value（价值） 。

我们前面讲了，价值函数分为两种，一种是状态价值函数，另一种价值函数则是状态-行动价值函数，这里我们采取更直接一点的状态-行动价值函数。

让我们回到刚开始的 State1，最为玩家 Agent，“我”在当前状态下应该在哪里落子呢？这就是一个策略问题，在一个状态下采取什么行动，这就是一个 Policy，而策略是由价值决定的，比如，在 State1，我可以落子的位置有 361 种，这 361 种行动对应各自的价值，在一个状态下，可能的行动对应的价值，这就是状态行动价值。

那么这个可能的行动对应的价值是多少呢？我们前面说过价值指的是预期将来会得到的奖励之和的期望值，在围棋中，如果我们规定赢棋的奖励为 1，输棋与和棋的奖励为 0，那么价值实际上就是赢棋的概率，因此，我的策略是选择价值最大，即赢棋概率最大的行动。这就是第三层结构。

这样我们就通过围棋这个例子梳理了强化学习的组成元素以及它们之间的关系。剩下的问题其实就只有一个了，如何学习一个好的价值函数和一个好的策略？这也就是这个强化学习领域最重要的内容。我们会在接下来的内容中详细讲解。而在次，我们还需要了解强化学习的两个特点，和一个核心问题。

3. 强化学习的两个特点和一个核心

3.1 第一个特点

第一个特点叫做 Trial and Error，即试错。强化学习是一种试错学习，也就是在不断的尝试中去学习。现在我们学习围棋，我们会拿着一本棋谱书，这本棋谱书会告诉我们应该在哪里落子，这是一种监督学习，而棋谱告诉我们的其实就是一种策略，这个策略怎么来的？就是古往今来的围棋先辈们通过不断的尝试和不断的对弈总结出来的经验，这就是一种强化学习。在不断下棋的过程中，去学习哪一步棋的价值最大，在不同的情况应该怎么落子，AlphaGo经历的也是同样的过程，这是强化学习的第一大特点，Trial and Error。

3.2 第二个特点

第二个特点则是，Delayed Reward，即延迟奖励。这个特点在围棋中就特别明显，玩家在对弈的过程中，落子得到的奖励都为 0，直到最后获得胜利得到大的奖励，也就是说在下棋过程中，行动没有对应即时的奖励，但是每一步棋对于最后的胜利都是有贡献的，这就导致一个行动可能没有奖励，但是它一定有价值，不过一个行动的价值，只有在得到了奖励后才真正得到体现，而这个奖励可能发生在一段时间之后，在玩家采取了很多其他的行动之后。这就称之为延迟奖励。

在实际得到奖励后，我们知道以前所采取的行动都对这个奖励有贡献，那么如何学习过去的行动所具有的价值，这就涉及到一个 Credit Assignment 和 Backpropagation 的问题，在具体的强化学习算法中我们就可以看到。而在围棋中呢也有同样的过程，我们称之为“复盘”，一局棋结束之后，一方赢，一方输，那么到底哪一步棋起到了关键的作用？哪一步棋的影响不是很大？这时通过“复盘”研究来学习的。实际上，这就是学习每一个动作对应的价值的过程。

3.3 一个核心

在强化学习中，有一个核心问题，就是 Exploration and Exploitation。

Exploitation 就是利用，利用的是强化学习所学到的价值函数，比如我们已经有了一个状态行动价值函数，想当然的应该采取价值最高的行动。但是呢，我们学习到的价值函数不一定是最优的函数，有一些看起来价值不是很高的行动，有可能真实价值是很高的，所以我们不仅仅要利用已有的价值函数，还应该去尝试不同的行动，从而优化我们的价值函数，这就是 Exploitation，即探索。

Exploration and Exploitation 之间的权衡是强化学习中的一个核心问题。在围棋中，就有一个很好的例子，那就是 AlphaGo 的出现给围棋界带来了很多前所未有的新定式，甚至是骚操作。比如开局白棋先行下星位，黑棋小飞挂角，这种情况下，白棋应该怎么应对？通过四千年来的经验总结，定式通常会告诉你，小飞、大飞、单关，压上，或者夹一个都是常见的走法，但是很少会去尖顶，也就是说，人类通过四千多年的学习，认为尖顶这一行动的价值不大，但是我们发现 AlphaGo 常常使用尖顶守角，这也就是说，AlphaGo 通过自己的强化学习，认为这一个行动对应的价值很大，那为什么我们没有发现这一步的价值呢？就是因为我们总是利用已有的价值函数（定式书籍），很少去尖顶，也就是缺乏 Exploitation。

4. 最简单的强化学习算法

4.1. 问题分析

前面我们铺垫了基本知识，剩下的问题其实就只有一个了，如何学习一个好的价值函数和一个好的策略？这也就是这个强化学习领域最重要的内容。

本节我们就要介绍强化学习的具体学习过程，也即算法。我们讲一个最简单的强化学习算法——多臂老虎机。

多臂老虎机是了解强化学习的一个经典问题。老虎机(slot machine)有一个拉杆，每次拉下拉杆，老虎机会随机给出不同数量的硬币。玩家希望尽可能获得多的硬币。怎么获取尽可能多的硬币就是要解决的问题。

alt

强化学习的目标就是学习一个好的策略，做出最优的选择和行动，从而最大化得到的奖励。

我们从强化学习的角度来分析这个问题，Agent 玩家就是“我”，环境 Environment 就是老虎机，现在假设我们有两个老虎机，为什么说这是强化学习中最简单的例子呢？最主要的原因是只有一个状态，老虎机摆在哪里位置不会有任何的改变，这只有一个状态的情况下，玩家只需要在不同的行动中选择一个，即拉动哪一个老虎机的拉杆？另一个原因是没有延迟奖励，因为行动得到的奖励是即时的，拉动老虎机的拉杆就会得到对应奖励，不会对以后的事情产生影响。那么我们只需要学习不同的行动对应的价值即可，即 State-Action Value，状态行动价值，这其中有一个状态，是为了强调行动所具有的价值是和所处的状态有关的，而在老虎机这个问题中，只有一个状态，所以我们可以简化为 Action Value，即行动价值，这个行动价值函数就是最简单的函数了，只有一个输入和输出，输入一个行动，对应输出价值。

我们再来分析下奖励的机制，我选择了一个老虎机后，它随机给了我一个奖励，从本质上来说，我们可以认为这个奖励是一个服从一定概率分布的随机变量，这两个老虎机可能对应的概率分布不一样，但是这两个概率分布是固定不变的，这就是我们所说的状态只有一个。概率分布有一个期望值，那么最优的行动就是选择当时期望值最大的行动，但是玩家并不知道老虎机对应的概率分布是多少，这就是强化学习要做的事情，学习这个概率分布，即学习价值函数。

4.2. 评估老虎机的价值

注意，在真正的现实复杂问题中，应用强化学习是需要去学习价值函数的，即学习价值对应的概率分布，而在老虎机问题中，为了简化问题，我们将直接给出概率分布，即给出了价值函数。但是每一次选择的最大期望价值如何计算呢？

如果有两台老虎机a和b，共给1000次机会，怎么获取更多的硬币呢。

假设已经知道它们给出不同硬币对应的概率如下：

老虎机 a

硬币数 0 1 5 10

概率

0.7

0.15

0.12

0.03

老虎机 b

硬币数 0 1 5 10

概率

0.5

0.4

0.09

0.01

可以计算出老虎机 a 获得硬币的期望值为：

$0 * 0.7 + 1 * 0.15 + 5 * 0.12 + 10 * 0.03 = 1.05$

老虎机 b 获得硬币的期望值为：

$0 * 0.5 + 1 * 0.4 + 5 * 0.09 + 10 * 0.01 = 0.95$

老虎机 a 的期望高于老虎机 b 的期望，每次选择玩老虎机 a 可以获取更多的硬币。

但是现实中不知道每个老虎机的期望，怎么选择玩哪台呢。概率中以样本均值估计期望值。假设玩某台老虎机 $n$ 次，获得硬币数分别为 $R_1,R_2,...R_n$ ，用 $Q_n$ 表示玩了 $n$ 次时对期望的估计值。则：

Q_n = \frac{R_1+R_2+...+R_n}{n} \tag{.}

根据大数定律，当 $n$ 越大，样本均值与期望值越接近。

由公式(1)可以推出以下：

Q_{n-1} = \frac{R_1+R_2+...+R_{n-1}}{n-1} \\ R_1+R_2+...+R_{n-1}=(n-1)Q_{n-1} \tag{.}

改写 $Q_n$ 的表示方法：

Q_n = \frac{R_1+R_2+...+R_n}{n} \\ =\frac{1}{n}(R_1+R_2+...+R_{n-1}+R_n) \\ =\frac{1}{n}((n-1)Q_{n-1}+R_n) \\ =Q_{n-1} -\frac{1}{n}Q_{n-1}+\frac{1}{n}R_n \\ =Q_{n-1} + \frac{1}{n}(R_n - Q_{n-1}) \tag{.}

最后有：

Q_n =Q_{n-1} + \frac{1}{n}(R_n - Q_{n-1}) \tag{.}

4.3. 策略

假设现在对每个机器都有了期望值的估计，那么可以选择当前估计期望值最大的机器(Exploitation, 利用)。有了价值函数后，我们如何选择行动，当然是选择对应价值最大的那一个行动（贪婪法则）。但是这里会存在一个问题，已知价值函数，那我们每一次岂不是都只玩一个老虎机了？由于实验次数有限，期望的估计值与真实期望值有偏差，当前期望估计值最大的机器可能不是真实期望值最大的机器。如果每次固定选择估计期望值最大的机器，可能难以获取最多的硬币。因此也需要选择那些目前期望估计值不是最大的机器（Exploration, 探索）。什么时候选择目前期望估计值最大的机器，什么时候选择其他机器，这就是权衡利用与探索的问题。做好利用与探索是强化学习的一个关键。

这当然不符合我们的预期，因为我们没有足够探索，已知的价值函数不一定是最优的。这里我们介绍 $\epsilon$ -贪婪法则。

$\epsilon$ -贪婪法则是一个经典的权衡利用与探索的算法。它以 $\epsilon$ 的概率进行探索（Exploration），即随机选择一个老虎机，以 $1-\epsilon$ 的概率进行利用（Exploitation）。

4.4. 实现多臂老虎机算法

简化以上老虎机模型，假设一个老虎机有多个拉杆，每个拉杆被拉下时老虎机以一定概率给出1个硬币或0个硬币。老虎机的建模如下：

import numpy as np

class Bandit:
    def __init__(self, arms=10):
        self.probs = n