date
type
status
slug
summary
tags
category
password
icon
强化学习笔记
 
每一组(出发点,动作,到达点,奖励)被称为一个’sample’,而从起点到终点的一组sample序列被称为一个’episode’
  • 基于模型的学习(Model-Based Learning)
    • 在基于模型的学习中,算法尝试学习并构建环境的模型,包括状态转换函数和奖励函数的模型。通过这个模型,算法能预测在给定状态和动作下,环境的下一个状态和即将获得的奖励。
    • 在建立起模型后,agent可以对模型(一个MDP问题)用value iteration或policy iteration求解。
  • 非基于模型的学习(Model-Free Learning)
    • 在非基于模型的学习中,算法不尝试学习环境的模型,而是直接通过与环境的交互来学习最优策略或者值函数。
    •  
  • Exploitation (开发):
    • Exploitation是指在决策过程中利用现有的知识来做出选择,以期获得最大的奖励。在这个过程中,算法倾向于选择过去经验中表现良好的动作。
    • 例如,如果在一个多臂老虎机问题中,某个臂在过去的尝试中给予了较高的奖励,那么在exploitation模式下,算法将倾向于再次选择这个臂。
  • 与Exploration的对比:
    • Exploration是指在决策过程中尝试新的、未知的选项,以期发现可能的更好解决方案。与exploitation相对,exploration可能会牺牲短期的奖励以获得长期的收益。
    • 在强化学习中,通常需要在exploitation和exploration之间找到一个合适的平衡,以确保算法既能发现新的、有效的解决方案,又能充分利用现有的知识来获得奖励。
    •  
       

Model-Free Learning

Direct Evaluation

在这种学习方法中,我们简单的遵循策略π,不断从起点走到终点,并在每一个这样的episode结束后记录下每个经过state获取的总收益,更新经过的state的被经过次数,最后取平均即可算出每个state的价值V.
 
这种方法的问题是,我们没有利用到两个state之间的转移关系。比方说,如果从A能到达B,而B有很高的价值,一般来说,A也会有较高的价值。而Direct Evaluation没有利用这一点。因此,Direct Evaluation所得到的价值函数V收敛到满足Bellman方程的速度较慢。
 
为此,我们介绍新方法
 

Temporal Difference Learning

我们考虑用以下两个公式来更新每个state的价值,以利用state间的状态转移。(α是给定的在(0, 1)间的常数, 也被称作“学习率”。)
最终我们会得到
观察这个公式,我们会发现:
sample_k的系数随k的减小而减小!
这也就是说,对于较老的(通常也是不那么精确的)sample,我们降低它的权值,而对于较新的sample,我们加大它的权值。从而,我们能够更快地让V收敛到满足Bellman方程的状态。
 
但这两种方法都只是算出了V的值,而没有计算出Q的值(还记得Q(s, a)是什么吗?),从而不利于我们找到一个新策略。为此,我们介绍:
 

Q-Learning

 
Q-Learning的强大之处在于,它直接尝试去更新Q的值而不需要知道任何前置知识。这主要基于MDP中的这个公式:
这个公式👆🏻被称作q-value iteration.
[注意,这个公式并不是我们实际在Q-Learning的学习过程中使用的公式,因为我们并不知道状态转移方程T(还记得吗, 我们在介绍Model-Free Learning),从而无法使用这个公式来更新Q。]
 
下面是我们在Q-Learning中实际使用的公式,注意它们和TD learning中使用的公式的相似之处:
ChatGPT对Q-Learning的公式解释
这两个公式实际上描述了同一个Q-learning的更新过程,但是在不同的角度和粒度。这两个公式共同体现了Q-learning的核心思想:基于当前状态和行动的即时奖励,以及下一个状态的最大Q值,来更新当前状态和行动的Q值。 1. 第一个公式:
这个公式是更通用的Q-learning更新公式。它在一个环境中考虑了所有可能的状态转移,并用转移概率T来加权每种转移的贡献。这是一个期望值形式的更新,通常在已知环境动态的情况下使用。 2. 第二个公式:
这个公式描述了在实际在线学习中,如何基于样本(sample)来更新Q值。这里的“sample”是从实际经验中得到的一个样本奖励和下一状态的最大Q值之和。
由于实际在线学习中,每次只观测到一个转移,所以不需要考虑所有可能的状态转移和加权它们。这个公式使用了一个学习率α来控制旧Q值和新样本之间的权重。
 
Q-Learning很有效,但并非尽善尽美。Q-Learning试图把每个都计算出来,然而在应用中,我们有时并没有那么大的储存空间用于存储每个Q的值。如果新的算法能在学习完一种情况后有处理相似情况的能力, 那么就能减少占用的储存空间。为此, 我们介绍:
 

Approximate Q-Learning

对于给定的状态s, 我们可以尝试用一些特征函数(feature function)来衡量一个状态的特征(feature), 再用这些函数的线性组合来估计价值函数的值。对于不同状态, 特征函数是通用的, 因此我们只需要学习线性组合它们的方法即可。
考虑以下两个公式:
 
如果我们成功的找到了合适的特征函数, 并找到了合适的权重, 那我们就可以用这两个公式来计算任何一个状态, 或是状态动作对的价值了。
在Approximate Q-Learning中, 我们用以下两个公式来进行对权重的学习。
 
第一个公式:
是根据当前的sample的回报和到达状态估计的新的Q值(可以看作), 是模型原本估计的Q值。在第二个公式中,我们需要利用difference来更新权重.
(还记得什么是sample吗?sample学习过程中的某一组(出发点,动作,到达点,奖励))
 
第二个公式:
 
回顾一下我们对Q-Learning的更新, 我们可以发现, 在Q-Learning中的更新公式与下面这个公式等价:
事实上, 这个difference也被称为TD误差。更多具体信息请读者自己查阅相关资料。
 
 

Exploration and Exploitation

之前提到的所有的Learning方法都需要有样本(sample)才能进行。为此, 我们来讨论怎样获取样本。在之前, 我们已经介绍过exploitation和exploration. 让我们再复习一下这两个概念:
 
  1. 利用 (Exploitation): 智能体基于其已有的知识选择当前认为最优的行动。例如,如果智能体认为向右移动会获得更高的奖励,它会选择这个行动。此时,智能体是在“利用”它的已有知识。
  1. 探索 (Exploration): 智能体尝试其他不太熟悉或不确定的行动,以获取新的信息。在这种情况下,即使智能体认为向右移动可能是最佳选择,它仍然可能选择向左移动,只是为了看看会发生什么。
 
换句话说, agent要抉择:是探索新的食堂, 还是去已经知道的那个便宜好吃的食堂?
为了让agent能够作出这个抉择, 我们需要用一些小策略。
 

-Greedy Policies

这是一种简单的策略。我们给定一个在(0, 1)间的常数, 让agent随机地决定是探索(explore)还是利用(exploit), 具体来说, 有(1−ε)的概率选择利用。
 
这个策略的问题在于, 如果ε的值过大, 即使agent已经学习出了最优策略, 它仍然不会遵循最优策略来行动。如果ε的值过小, 学习速度会很慢。因此, 我们要时常手动改变ε的值。
 
另外一种更聪明的策略是:

Exploration Functions

在这里, 我们要对的更新方法做一点修改:
其中, 函数有多种定义方法, 一个常见的定义如下
在这里, k是给定的常数, 表示agent到达q-state的总次数。
 
我们让处于状态 s 的智能体总是选择能最大化的动作,因此永远不必在探索和利用之间做出抉择。我们可以发现, 越小, 越大, 也就是说, 那些没被探索过的节点被额外赋予了一些“奖励”。而当足够大, 会很接近, 从而让agent的行为接近于选择最大化的动作,即倾向于最优解。
 
 
如文章有错误, 或读者有建议、疑问, 请发邮件到[email protected], 我会尽快回复。
费马小定理的组合证明LeetCode 周赛 365 解析