1、Foundations of Machine LearningReinforcement Learning2023-11-4Reinforcement LearningLesson 10-1强化学习（Reinforcement learning）概述K-摇臂赌博机贝尔曼（Bellman）方程MDP（Markov decision process）问题建模基于价值迭代（Value iteration）的求解方法策略迭代（Policy iteration）的求解方法比较Value iteration和Policy iterationQ-learning2023-11-4Reinforcement
2、LearningLesson 10-2强化学习（Reinforcement learning）概述强化学习诞生于上世纪 80 年代，最初应用于制造业，特别是工业机器人的自动控制，近年来随着其他机器方法的成熟开始应用于更加”智能”的场景，除了大名鼎鼎的 Alpha GO，google deepmind 团队还应用强化学习实现了计算机自主学习玩 Atari 系列电子游戏并超越了人类玩家的水平。2023-11-4Reinforcement LearningLesson 10 -3强化学习（Reinforcement learning）概述强化学习（Reinforcement learning）的基本
3、内涵是将问题用代理（Agent，有的地方也将其翻译为智能体）和环境进行建模。其中代理能够对环境执行一些特定的动作aA，从而到达某个状态sS，然后我们就可以根据该状态为代理赋予特定的奖励r。强化学习的基本思想如下图所示：2023-11-4Reinforcement LearningLesson 10 -4强化学习（Reinforcement learning）概述强化学习（Reinforcement learning）的基本内涵是将问题用代理（Agent，有的地方也将其翻译为智能体）和环境进行建模。其中代理能够对环境执行一些特定的动作aA，从而到达某个状态sS，然后我们就可以根据该状态为代理赋予
4、特定的奖励r。强代理的目标是最大化未来的奖励总和，它通过将未来可获得的最大奖励添加到当前的奖励来实现这一点（类似于贪心算法），从而通过潜在的奖励影响当前行动。这个潜在奖励（Value）是从当前状态开始的所有未来动作的奖励期望值的加权和。2023-11-4Reinforcement LearningLesson 10-5K-摇臂赌博机探索与利用与一般监督学习不同，强化学习任务的最终奖赏是在多步动作之后才能观察到，这里我们不妨先考虑比较简单的情形:最大化单步奖赏最大化单步奖赏，即仅考虑一步操作.需注意的是，即使在这样的简化情形下，强化学习仍与监督学习有显著不同，因为机器需通过尝试来发现各个动作产生
5、的结果，而没有训练数据告诉机器应当做哪个动作.欲最大化单步奖赏需考虑两个方面:一是需知道每个动作带来的奖赏，二是要执行奖赏最大的动作.若每个动作对应的奖赏是一个确定值，那么尝试一遍所有的动作便能找出奖赏最大的动作.然而，更一般的情形是，一个动作的奖赏值是来自于一个概率分布，仅通过一次尝试并不能确切地获得平均奖赏值.单步强化学习任务对应一个理论模型，即“K-摇臂赌博机”2023-11-4Reinforcement LearningLesson 10-6K-摇臂赌博机探索与利用若仅为获知每个摇臂的期望奖赏，则可采用“仅探索”(exploration Only)法:将所有的尝试机会平均分配给每个摇臂
6、(即轮流按下每个摇臂)，最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计.若仅为执行奖赏最大的动作，则可采用“仅利用(exploitation-only)法:按下目前最优的(即到目前为止平均奖赏最大的)摇臂，若有多个摇臂同为最优，则从中随机选取一个.显然，仅探索法能很好地估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会;仅利用法则相反，它没有很好地估计摇臂期望奖赏，很可能经常选不到最优摇臂.因此，这两种方法都难以使最终的累积奖赏最大化.2023-11-4Reinforcement LearningLesson 10-7K-摇臂赌博机探索与利用-贪心法-贪心法基于一个概率来对探索和利用
7、进行折中:每次尝试时，以 的概率进行探索，即以均匀概率随机选取一个摇臂;以1-的概率进行利用，即选择当前平均奖赏最高的摇臂(若有多个，则随机选取一个).Q(k)记录摇臂k 的平均奖赏2023-11-4Reinforcement LearningLesson 10-8K-摇臂赌博机探索与利用-贪心法Softmax 算法Softmax 算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中.若各摇臂的平均奖赏相当，则选取各摇臂的概率也相当;若某些摇臂的平均奖赏明显高于其他摇臂，则它们被选取的概率也明显更高.Softmax 算法中摇臂概率的分配是基于Boltzmann 分布2023-11-4Reinf
8、orcement LearningLesson 10-9Boltzmann 分布选择分布选择强化学习问题的马尔科夫决策过程描述通常人们用马尔科夫决策过程（马尔科夫决策过程（Markov decision process，MDP）来描述强化学习问题，一个基本的MDP问题可以用一个五元组(S,A,P,R,)来表示，各个符号的含义如下所示：S 表示有限状态集。A 表示有限动作集。P 表示状态转移概率矩阵。Pa(s,s)=P(st+1=s st=s,at=a)表示在状态s下执行动作a后，从状态s转移到s的概率概率。R 表示奖励（Reward）函数。Ra(s,s)表示在状态s下执行动作a后，从状态s转移
9、到s，所得到的奖励奖励。表示折扣因子，该因子主要用于平衡当前的奖励与未来的奖励，可以理解为权重。一般会把未来奖励的权重调低一点。2023-11-4Reinforcement LearningLesson 10-10强化学习问题的马尔科夫决策过程描述2023-11-4Reinforcement LearningLesson 10-11贝尔曼（Bellman）方程2023-11-4Reinforcement LearningLesson 10 -12MDP（Markov decision process）问题建模假设已知了状态转移概率矩阵P和奖励函数R，结合Bellman方程，我们有：2023-1
10、1-4Reinforcement LearningLesson 10 -13基于价值迭代（Value iteration）的求解方法基于价值迭代的求解方法中，迭代过程中仅仅更新价值（Value），其迭代公式如下：2023-11-4Reinforcement LearningLesson 10-14基于策略迭代（Policy iteration）的求解方法与基于价值迭代的求解方法不同，基于策略迭代的方法在迭代过程中要同时更新价值（Value）和策略（Policy）。通常它分为如下两个主要步骤：策略评估：2023-11-4Reinforcement LearningLesson 10-15策略改进
11、：基于策略迭代（Policy iteration）的求解方法2023-11-4Reinforcement LearningLesson 10-16比较Value iteration和Policy iterationPolicy iteration中的两个步骤都与policy直接关联，首先利用一个给定的policy，通过迭代方法对其进行评价，得到value function；接下来利用这个value function去不停地迭代各种policy，最终确定最佳policy。Value iteration则不直接与policy打交道，在这一类方法中，当value最后收敛，其实也相当于得到了最优的po
12、licy。当然，以上两种求解方法也有一些共同点，比如两者在迭代计算过程中都依赖状态转移概率矩阵P和奖励（Reward）函数R。这里需要强调的是状态转移概率矩阵P，如果已知转移概率P也就称为获得了模型 Model，这种通过模型来获取最佳策略的方法也就称为 model-based 的方法。然而，在现实场景下，有很多问题很难获取状态转移概率矩阵P，因此人们需要采用model-free的方法来找到最佳策略，e.g.,Q-learning，Policy Gradient，Actor-Critic，这些方法都属于model-free方法。2023-11-4Reinforcement LearningLes
13、son 10-17Q-learningQ-learning是一种典型的基于价值（Value）函数的强化学习方法，其中的Q是一个数值（可以理解为价值value），通常在初始化时有可能被赋予一个任意数值（因问题场景而异），在迭代时刻t，我们有状态st，此时代理做出动作at，然后得到奖励rt，从而进入到一个更新的状态st+1，从而Q值得到更新，其更新公式为：2023-11-4Reinforcement LearningLesson 10-18Q-learning令=/，将上述公式的右边进行同类项合并同类项合并：2023-11-4Reinforcement LearningLesson 10-19根据
14、强化学习中贝尔曼（Bellman）方程的定义，我们有：Q-learning2023-11-4Reinforcement LearningLesson 10-20Q-learning的一种典型实现方法及示例（Q-table查表法）这里我们用一个经典示例Path-finding来说明Q-learning算法。如下图所示，有一组房间，每个房间的编号为04，其中有的房间之间能够互通，有的不能互通，5号区域为室外。如下图所示：我们期望把Agent放在任何房间，然后它自己能够从那个房间走出大楼（换句话说，目标房间是5号）。2023-11-4Reinforcement LearningLesson 10-2
15、1Q-table查表法现在，我们构造一个连通图，并约定：能够直接到达5号区域的边，其奖励值为100（包括5号自己到达5号）；房间之间彼此连通的边，其奖励值为0；房间之间彼此阻隔的边，其奖励值为-1；房间自己到达自己的边，其奖励值为-1。根据这样的规则，我们可以构造如下连通图（对于互相阻隔的房间，它们之间的边被省略了）：2023-11-4Reinforcement LearningLesson 10-22Q-table查表法定义state和action。我们约定将代理当前所在的区域编号作为state，将代理前往哪一个区域的编号作为action。根据上述连通图中的奖励值，我们可以根据上述连通图构造
16、奖励矩阵R，如下图所示：2023-11-4Reinforcement LearningLesson 10-23Q-table查表法我们再创建一张Q-table，对其进行初始化，将内部所有元素置为0，如下图所示：对Q值进行更新的公式（设定 值为0.8）：2023-11-4Reinforcement LearningLesson 10-24Q-table查表法假定代理当前位于1号房间，查询奖励矩阵R，代理可以到达区域3和区域5，现在随机选择一个动作“前往区域3”，我们通过查询Q-table来更新Q值（具体地，是更新元素Q(1,3)），此时，需要查表获得两类数据：奖励（Reward）。这里特指“从房
17、间1（当前state）前往房间3（采取的action）所获得的即时奖励”，因此需要查询的数据为R(1,3)。未来的价值（Value）。这里特指“进入房间3后（next state）所能获得的最大即时奖励”，因此需要查询的数据为：Q(3,1)、Q(3,2)和Q(3,4)。2023-11-4Reinforcement LearningLesson 10-25Q-table查表法假定代理当前位于1号房间，查询奖励矩阵R，代理可以到达区域3和区域5，现在随机选择一个动作“前往区域5”，我们通过查询Q-table来更新Q值（具体地，是更新元素Q(1,5)），此时，需要查表获得两类数据：奖励（Reward
18、）。这里特指“从房间1（当前state）前往房间5（采取的action）所获得的即时奖励”，因此需要查询的数据为R(1,5)。未来的价值（Value）。这里特指“进入房间5后（next state）所能获得的最大即时奖励”，因此需要查询的数据为：Q(5,1)、Q(5,4)和Q(5,5)。2023-11-4Reinforcement LearningLesson 10-26在得到了Q-table后，我们就可以根据该矩阵让代理独自行走寻找路径了。主要思想是查找当前位置具有最大Q值的action，然后执行，如此反复，直到到达目的地为止。具体算法如下：2023-11-4Reinforcement Le
19、arningLesson 10-27Initialize state swhile the goal state hasnt been reached do Choose an action a which has the max Q value in Q-table corresponding to current s Update state s by execution the choosen action aend whileReinforcement Learning in scikit-learn?Top 7 Python Libraries For Reinforcement L
20、earningPyqlearningKerasRLTensorforceRL_CoachChainerRLMAME RLMushroomRL2023-11-4Reinforcement LearningLesson 10-28Pyqlearningpyqlearning is Python library to implement Reinforcement Learning and Deep Reinforcement Learning,especially for Q-Learning,Deep Q-Network,and Multi-agent Deep Q-Network which
21、can be optimized by Annealing models such as Simulated Annealing,Adaptive Simulated Annealing,and Quantum Monte Carlo Method.This library makes it possible to design the information search algorithm such as the Game AI,web crawlers,or robotics.Installationpip install pyqlearning2023-11-4Reinforcemen
22、t LearningLesson 10-292023-11-4Reinforcement LearningLesson 10-30KerasRLKeras-RL seamlessly implements state-of-the-art deep reinforcement learning algorithms with the deep learning library Keras.Evaluating and playing around with different algorithms is easy,as Keras-RL works with OpenAI Gym out of
23、 the box.Installation:pip install Keras-RLTensorforceTensorforce is an open-source deep reinforcement learning framework,which is relatively straightforward in its usage.Tensorforce is built on top of Googles TensorFlow framework and is compatible with Python 3Installation:pip3 install tensorforce2023-11-4Reinforcement LearningLesson 10-31SummaryK-摇臂赌博机Q-learning2023-11-4Reinforcement LearningLesson 10-32
