1700539125
百面机器学习：算法工程师带你去面试 [:1700532233]
1700539126
百面机器学习：算法工程师带你去面试 第11章 强化学习
1700539127
1700539128
强化学习近年来在机器学习领域越来越火，也受到了越来越多人的关注。强化学习是一个20世纪80年代兴起的，受行为心理学启发而来的一个机器学习领域，它关注身处某个环境中的决策器通过采取行动获得最大化的累积收益。和传统的监督学习不同，在强化学习中，并不直接给决策器的输出打分。相反，决策器只能得到一个间接的反馈，而无法获得一个正确的输入/输出对，因此需要在不断的尝试中优化自己的策略以获得更高的收益。从广义上说，大部分涉及动态系统的决策学习过程都可以看成是一种强化学习。强化学习的应用非常广泛，包括博弈论、控制论、优化等多个不同领域。这两年，AlphaGo及其升级版横空出世，彻底改变了围棋这一古老的竞技领域，在业界引起很大震惊，其核心技术就是强化学习。与未来科技发展密切相关的机器人领域，从机器人行走、运动控制，到自动驾驶，都是强化学习的用武之地。
1700539129
1700539130
1700539131
1700539132
1700539133
百面机器学习：算法工程师带你去面试 [:1700532234]
1700539134
百面机器学习：算法工程师带你去面试 01 强化学习基础
1700539135
1700539136
1700539137
1700539138
场景描述
1700539139
1700539140
假设我们有一个3×3的棋盘，其中有一个单元格是马里奥，另一个单元格是宝藏，如图11.1所示。在游戏的每个回合，可以往上、下、左、右四个方向移动马里奥，直到马里奥找到宝藏，游戏结束。在这个场景中，强化学习需要定义一些基本概念来完成对问题的数学建模。
1700539141
1700539142
1700539143
1700539144
1700539145
图11.1 超级玛丽找宝藏
1700539146
1700539147
知识点
1700539148
1700539149
强化学习，马尔可夫决策过程，价值迭代（Value Iteration），策略迭代
1700539150
1700539151
问题1 强化学习中有哪些基本概念？在马里奥找宝藏问题中如何定义这些概念？
1700539152
1700539153
难度：★☆☆☆☆
1700539154
1700539155
分析与解答
1700539156
1700539157
强化学习的基本场景可以用图11.2来描述，主要由环境（Environment）、机器人（Agent）、状态（State）、动作（Action）、奖励（Reward）等基本概念构成。一个机器人在环境中会做各种动作，环境会接收动作，并引起自身状态的变迁，同时给机器人以奖励。机器人的目标就是使用一些策略，做合适的动作，最大化自身的收益。
1700539158
1700539159
1700539160
1700539161
1700539162
图11.2 强化学习基本场景
1700539163
1700539164
整个场景一般可以描述为一个马尔可夫决策过程（Markov Decision Process，MDP）。马尔可夫决策过程是马尔可夫过程与确定性的动态规划相结合的产物，指决策者周期地或连续地观察具有马尔可夫性的随机动态系统，序贯地做出决策的过程，以俄罗斯数学家安德雷·马尔可夫的名字命名。这个过程包括以下几个要素：
1700539165
1700539166
1700539167
1700539168
1700539169
1700539170
动作：所有可能做出的动作的集合，记作A（可能是无限的）。对于本题，A=马里奥在每个单元格可以行走的方向，即{上、下、左、右}。 状态：所有状态的集合，记作S。对于本题，S为棋盘中每个单元格的位置坐标{(x,y); x=1,2,3; y=1,2,3}，马里奥当前位于（1,1），宝藏位于（3,2）。 奖励：机器人可能收到的奖励，一般是一个实数，记作r。对于本题，如果马里奥每移动一步，定义r=−1；如果得到宝藏，定义r=0，游戏结束。 时间（t=1,2,3…）：在每个时间点t，机器人会发出一个动作at，收到环境给出的收益rt，同时环境进入到一个新的状态st。 状态转移：S×A→S满足，也就是说，从当前状态到下一状态的转移，只与当前状态以及当前所采取的动作有关。这就是所谓的马尔可夫性。 累积收益：从当前时刻0开始累积收益的计算方法是，在很多时候，我们可以取T=∞。 强化学习的核心任务是，学习一个从状态空间S到动作空间A的映射，最大化累积受益。常用的强化学习算法有Q-Learning、策略梯度，以及演员评判家算法（Actor-Critic）等。
1700539171
1700539172
问题2 根据图11.1给定的马里奥的位置以及宝藏的位置，从价值迭代来考虑，如何找到一条最优路线？
1700539173
1700539174
难度：★★☆☆☆