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
难度：★★☆☆☆
1700539175
1700539176
分析与解答
1700539177
1700539178
上一问已经把强化学习问题形式化为马尔可夫决策过程。下面我们介绍如何利用价值迭代求解马尔可夫决策过程。那么什么是价值呢？我们将当前状态s的价值V(s)定义为：从状态s=(x,y)开始，能够获得的最大化奖励。结合图11.3可以非常直观地理解价值迭代。
1700539179