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
1700539180
1700539181
1700539182
1700539183
图11.3 迭代过程
1700539184
1700539185
首先，初始化所有状态的价值V(s)=0。然后，在每一轮迭代中，对每个状态s依次执行以下步骤。
1700539186
1700539187
1700539188
1700539189
1700539190
逐一尝试{上、下、左、右}四个动作a，记录到达状态s′和奖励r。 计算每个动作的价值q(s,a)=r+V(s′)。 从四个动作中选择最优的动作。 更新s状态价值。 在第一轮迭代中，由于初始状态V(s)均为0，因此对除宝藏所在位置外的状态s均有V(s)=r+V(s′)=−1+0=−1，即从当前位置出发走一步获得奖励r=−1。
1700539191
1700539192
在第二轮迭代中，对于和宝藏位置相邻的状态，最优动作为一步到达V(s′)=0的状态，即宝藏所在的格子。因此，V(s)更新为r+V(s′)=−1+0=−1；其余只能一步到达V(s′)=−1的状态，V(s)更新为r+V(s′)=−1+(−1)=−2。
1700539193
1700539194
第三轮和第四轮迭代如法炮制。可以发现，在第四轮迭代中，所有V(s)更新前后都没有任何变化，价值迭代已经找到了最优策略。最终，只需要从马里奥所在位置开始，每一步选择最优动作，即可最快地找到宝藏。
1700539195
1700539196
上面的迭代过程实际上运用了贝尔曼方程（Bellman Equation），来对每个位置的价值进行更新
1700539197
1700539198
1700539199
．