强化学习（Reinforcement Learning, RL）是机器学习的一个分支，它致力于让智能体（Agent）在与环境（Environment）交互的过程中学习如何做出最优的决策。强化学习的核心目标是使智能体学会在给定的环境中通过尝试和错误来最大化其累积奖励。这一学习过程涉及到智能体观察环境状态（State），根据某种策略（Policy）采取行动（Action），并接收环境给予的奖励（Reward）或惩罚，以此来调整其行为。

0.基本概念

  1. 智能体（Agent）：在强化学习框架中，智能体是执行动作以影响环境的实体。
  2. 环境（Environment）：智能体所处并与之交互的外部世界，环境根据智能体的行动反馈奖励和新的状态。
  3. 状态（State）：环境在任何给定时间点的具体情况或属性，通常表示为智能体可以观察到的环境信息的集合。
  4. 动作（Action）：智能体在给定状态下可以采取的决策或行为。
  5. 奖励（Reward）：当智能体执行动作后，环境根据动作的效果给予的反馈，奖励是驱动智能体学习的关键信号。
  6. 策略（Policy）：从状态到动作的映射，定义了在给定状态下智能体应采取的动作。策略可以是确定性的（每个状态对应一个动作）或随机性的（在状态下根据某种概率分布选择动作）。
  7. 值函数（Value Function）：评估某状态或状态-动作对好坏的函数，通常是从该点出发未来可以获得的累积奖励的期望值。
  8. 模型（Model）：环境的模型预测环境如何响应智能体的动作，即给定状态和动作后预测下一个状态和奖励。在模型无关的强化学习中，智能体无需此模型即可学习。

【学习范式】


强化学习主要包括以下几种学习范式：

  • 模型无关的强化学习：智能体通过与环境的直接交互学习，不需要对环境的模型有任何先验知识。
    • 基于价值：通过求解一个状态或者状态下某个动作的估值为手段，从而寻找最佳的价值函数，找到价值函数后，再提取最佳策略。代表算法包括Q学习（Q-Learning）、Sarsa、Deep Q-Networks（DQN）等。
    • 基于策略优化：直接在策略空间中进行搜索和优化，以找到最优策略。代表算法包括Actor-Criti、策略梯度（Policy Gradient）、TRPO（Trust Region Policy Optimization）、PPO（Proximal Policy Optimization）等。
  • 模型基的强化学习：智能体利用对环境的模型进行决策和学习。这种方法需要一个环境模型来预测下一个状态和奖励，可以是显式建模也可以是智能体自行学习的模型。

【交互过程】

强化学习的交互过程通常遵循以下步骤：

  1. 智能体观察当前环境状态。
  2. 根据当前策略，智能体选择并执行一个动作。
  3. 环境根据智能体的动作转移到新的状态，并给予相应的奖励。
  4. 智能体根据奖励和新的状态更新其策略。
  5. 重复上述过程，直到达到某个终止条件，如达到目标状态或超过最大步数。

强化学习是一个动态的、试错的学习过程，其目标是使智能体能够通过学习如何在特定环境中做出最优决策来最大化累积奖励。通过不断的实践和调整，智能体能够改善其策略，逐步提升性能。

1.RL的前世

强化学习其实是一个马尔可夫决策过程(Markov decision process，MDP)，我们先看看什么是MDP。讲MDP前先简单的讲一些基本知识。

【随机过程】

随机过程就是单个随机现象在时间维度上的延展。比如基础概率论中讨论的扔骰子等都是一个静态的事件，现在如果我是每分钟都扔一下这个骰子，想研究随着事件变化扔到点数的总和，这个就变成一个动态（和时间相关）的事件了，我们用随机过程去定义这个动态的事件。

举一个比较经典的随机过程：排队。比如每天咖啡店从开门开始，陆续有人来买咖啡，假如来人的速率是λ\lambda人/小时，那么t时刻前来过的人总数可以用一个Poisson过程（参数为λ\lambda）来近似。Poisson过程有一些比较好的性质，可以借助这些特性来分析这个过程中某段时间内前来买咖啡的人数的分布，以此来分析可能的排队情况。

【马尔可夫过程】

设想一个天气变化的场景：
如果昨天是晴天，那么今天是晴天的概率为0.6，是多云的概率为0.275，是雨天的概率为0.125；
如果昨天是多云，那么今天是晴天的概率为0.3，多云的概率0.5，雨天的概率0.2；
如果昨天是雨天，那么今天是晴天的概率为0.1，多云的概率0.35，雨天的额概率0.55。
那么我们可以用一个状态转移矩阵来表示这种转移的概率：

今晴今云今雨\begin{matrix} \qquad & 今晴 & 今云 & 今雨 \\ \end{matrix}

昨晴昨云昨雨[0.60.2750.1250.30.50.20.10.350.55]\begin{matrix} 昨晴 \\ 昨云 \\ 昨雨 \end{matrix} \quad \begin{bmatrix} 0.6 & 0.275 & 0.125\\ 0.3 & 0.5 & 0.2\\ 0.1 & 0.35 & 0.55 \end{bmatrix}

天气的随事件的变化，这是一个随机过程。假设我们现在知道S0,S1,…,St−1S_0,S_1,\dots,S_{t-1}的所有信息，我们想知道StS_t的天气状态，那么在该场景的假设下，我们可以很容易的发现我们不需要这么多的历史信息，我们只需要St−1S_{t-1}的信息就足够了（因为不管以前出现了多少晴天雨天多云天，只要昨天是晴天，那么今天是晴天的概率就一定是0.6）：即P(St∣S0,S1,…,St−1)=P(St∣St−1)\mathbb{P}(S_t | S_0,S_1,\dots,S_{t-1})=\mathbb{P}(S_t | S_{t-1})。像这种类似的场景，如果某一个时刻的状态只取决于上一时刻的状态，那么我们称它是具有马尔可夫性质的。具有马尔可夫性质的随机过程我们称为马尔可夫过程。

【马尔可夫奖励过程】

在马尔可夫过程的基础上加入奖励函数和折扣因子，就可以得到马尔可夫奖励过程(Markov reward process，MRP)。

定义奖励函数表示某个状态ss的奖励Rt(s)R_t(s)，是指转移到该状态时可以获得奖励的期望，有Rt(s)=E[Rt+1∣St=s]R_t(s)=\mathbb{E}[R_{t+1}|S_t=s]

此外，实际中，因为一个状态可以得到的奖励是持久的，所有奖励的衰减之和称为回报，可用GG表示当下即时奖励和所有持久奖励等一切奖励的加权和(考虑到一般越往后某个状态给的回报率越低，经济学直觉：人总是偏好短期反馈），也即奖励因子或折扣因子越小，用γ\gamma表示)，从而有

Gt=Rt+1+γRt+2+γ2Rt+3+…=Rt+1+γ(Rt+2+γRt+3+… )=Rt+1+γGt+1\begin{aligned} G_t & = R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \\ & = R_{t+1}+\gamma(R_{t+2} + \gamma R_{t+3} + \dots ) \\ & = R_{t+1}+\gamma G_{t+1} \end{aligned}

而一个状态的期望回报就称之为这个状态的价值，所有状态的价值则组成了所谓的状态价值函数，用公式表达为V(s)=E[Gt∣St=s]V(s)=\mathbb{E}[G_t|S_t=s]，展开一下可得：

Vt(s)=E[Gt∣St=s]=E[Rt+1+γGt+1∣St=s]=E[Rt+1∣St=s]+γE[Gt+1∣St=s]=E[Rt+1∣St=s]+γE[Vt+1(S)∣St=s]\begin{aligned} V_t(s) & = \mathbb{E}[G_t|S_t=s] \\ & = \mathbb{E}[R_{t+1}+\gamma G_{t+1} | S_t = s] \\ & = \mathbb{E}[R_{t+1}|S_t=s] + \gamma \mathbb{E}[G_{t+1}|S_t=s] \\ & = \mathbb{E}[R_{t+1}|S_t=s] + \gamma \mathbb{E}[V_{t+1}(S)|S_t=s] \\ \end{aligned}

最后的等式里，前半部分为当前状态得到的即时奖励E[Rt+1∣St=s]=Rt(s)\mathbb{E}[R_{t+1}|S_t=s]=R_t(s)；后半部分表示当前状态得到的所有持久奖励γE[V(St+1∣St=s)]\gamma \mathbb{E}[V(S_{t+1}|S_t=s)]，可以根据从状态s出发的转移概率得到：γ∑s′∈SP(s′∣St=s)Vt+1(s′)\gamma \sum_{s'\in S} \mathbb{P}(s'|S_t=s)V_{t+1}(s')。

所以，综合两部分，可得：

Vt(s)=Rt(s)+γ∑s′∈SP(s′∣St=s)Vt+1(s′)V_t(s) = R_t(s) + \gamma \sum_{s'\in S} \mathbb{P}(s'|S_t=s)V_{t+1}(s')

这就是经典的贝尔曼方程（bellman equation）。直观的理解，就是当前状态的价值等价于达到当前状态所得到的即时奖励以及下一状态价值的条件期望（已知当前状态下下一时刻达到各状态的概率乘以各状态的价值）的贴现。
贝尔曼方程的计算根据全量状态的多少复杂度会有较大区别，求解其价值函数是比较重要的部分，有几大类方法：动态规划、蒙特卡洛、时序差分方法等。

【马尔可夫决策过程】

马尔可夫决策过程（MDP，Markov decision process）是在马尔可夫奖励过程的基础上再增加了一个来自外界的刺激比如智能体的动作。在MDP中，StS_t(S是状态的集合)和RtR_t(R是奖励的集合)的每个可能的值出现的概率只取决于前一状态St−1S_{t-1}和前一动作At−1A_{t-1}(A是动作的集合)，并且与更早之前的状态和动作完全无关。

状态s在a动作下转移到状态s'的状态转移概率可以表示如下：

Pss′a=P(St+1=s′∣St=s,At=a)=p(s′∣s,a)P_{ss'}^a = \mathbb{P}(S_{t+1}=s'|S_t=s, A_t=a) = p(s'|s, a)

假定在当前状态和动作已经确定后，其对应的奖励为r，那么加上奖励项的转移概率可以表示为：

p(s′,r∣s,a)=P(St+1=s′,Rt+1=r∣St=s,At=a)p(s',r|s,a) = \mathbb{P}(S_{t+1}=s', R_{t+1}=r|S_t=s, A_t=a)

从而奖励函数可以表示成：

R(s,a)=E[Rt+1∣St=s,At=a]=∑s′∈S∑r∈Rp(s′,r∣s,a)r\begin{aligned} R(s,a) & = \mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ & = \sum_{s'\in S}\sum_{r\in R}p(s',r|s,a)r \end{aligned}

如果R是确定的，那么也等价于∑s′∈Sp(s′,r∣s,a)r\sum_{s' \in S}p(s',r|s,a)r。

至于过程采取什么样的动作就涉及到策略policy，策略函数一般用π\pi表示，把状态映射到动作：a=π(s)a=\pi(s)或者a=πθ(s)a=\pi_{\theta}(s)（其中θ\theta表示策略函数的参数）。不过更常见的情况是状态映射到动作也是随机的，某种状态下有多少概率采取某种动作，所以π\pi在这种情况下用来表示概率测度，即π(a∣s)=P(At=a∣St=s)\pi(a|s) = \mathbb{P}(A_t=a|S_t=s)。

引入动作之后我们重新来梳理一下价值函数

  • 首先通过状态价值函数对当前状态进行估计

Vπ(s)=Eπ[Gt∣St=s]=Eπ[Rt+1+γGt+1∣St=s]=Eπ[Rt+1+γVπ(St+1)∣St=s]\begin{aligned} V_{\pi}(s) &= \mathbb{E}_{\pi}[G_t|S_t=s]\\ &=\mathbb{E}_{\pi}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ &=\mathbb{E}_{\pi}[R_{t+1}+\gamma V_{\pi}(S_{t+1})|S_t=s] \end{aligned}

  • 然后通过动作价值函数对动作评估

Qπ(s,a)=Eπ[Gt∣St=s,At=a]=Eπ[Rt+1+γGt+1∣St=s,At=a]=Eπ[Rt+1+γQπ(St+1,At+1)∣St=s,At=a]\begin{aligned} Q_{\pi}(s,a) &= \mathbb{E}_{\pi}[G_t|S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi}[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi}[R_{t+1}+\gamma Q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a] \end{aligned}

的价值函数可以扩展成动作价值函数Qπ(s,a)Q_{\pi}(s,a)，相当于对当前状态s依据策略π\pi执行动作a得到的期望回报，这也是大名鼎鼎的Q函数

1.Q-learning

Q-learning是一种无模型的强化学习算法，主要用于学习在给定状态下采取各种动作的预期效用。它通过估计一个动作价值函数，即Q函数（Q-value function），来指导智能体如何在给定状态下选择动作以最大化累积奖励。Q函数的值Q(s, a)表示在状态s下采取动作a的长期回报的预期值。

原理

Q-learning的核心是更新Q值的规则，它使用贝尔曼方程（Bellman equation）的一种变体来迭代更新Q值。该更新规则如下：

Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)]Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s, a)]

其中：

  • Q(s,a)Q(s, a) 是当前状态ss下采取动作( a )的Q值。
  • α\alpha 是学习率（0 < α\alpha≤ 1），控制学习过程中新信息的重要性。
  • rr 是采取动作( a )后从状态( s )转移到状态( s' )获得的即时奖励。
  • γ\gamma 是折扣因子（0 ≤ γ\gamma < 1），表示未来奖励的当前价值。
  • max⁡a′Q(s′,a′)\max_{a'} Q(s', a') 是在下一个状态s′s'下所有可能动作的Q值中的最大值，代表未来奖励的最佳估计。

技术细节

  1. 探索与利用（Exploration and Exploitation）：为了平衡探索新动作和利用已知最佳动作之间的关系，Q-learning通常采用ε-贪婪策略（ε-greedy policy）。这意味着大部分时间（1-ε的概率）选择当前已知的最佳动作（最大Q值的动作），而有一小部分时间（ε的概率）随机选择动作，以探索未知的状态-动作对。

  2. 学习率（Learning Rate）：学习率α\alpha决定了新信息替代旧信息的速度。较高的学习率意味着新的估计会更快地覆盖旧的估计，而较低的学习率意味着学习过程更加缓慢，更多地依赖历史数据。

  3. 折扣因子（Discount Factor）：折扣因子γ\gamma决定了未来奖励对当前决策的重要性。当γ\gamma接近1时，智能体会更加重视长期奖励；当γ\gamma较小时，智能体则倾向于优先考虑短期奖励。

  4. 初始化Q值：Q-learning算法的性能部分依赖于Q值的初始化。通常，Q值可以初始化为0或一个小的随机值，以促进初期的探索。

  5. 策略收敛：理论上，如果每个状态-动作对被无限次访问，且学习率符合特定条件（如随时间逐渐减小），Q-learning保证能够找到最优策略。

  6. 函数逼近：在具有大量状态或连续状态空间的环境中，直接使用表格存储Q值变得不可行。在这种情况下，可以使用函数逼近方法（如神经网络）来估计Q函数，这是深度Q网络（DQN）的基础。

Q-learning算法因其简单性和在多种环境中的有效性而广受欢迎。尽管它在处理高维状态空间和连续动作空间时面临挑战，但通过与深度学习等技术的结合，Q-learning及其变种已经在诸如游戏、机器人导航等领域取得了显著的成功。

2.Sarsa

Sarsa（State-Action-Reward-State-Action）是一种在强化学习中使用的无模型的策略迭代算法，与Q-learning相似，它采取行动的时候用的也是ε-greedy policy，但主要区别在于它是一种同策略（on-policy）学习方法。这意味着Sarsa在更新值函数时使用的是实际会产生的下一步动作，而不是像Q-learning中那样使用最大化未来奖励的动作（理论动作）。和Q-learning的唯一区别就是在更新Q函数的时候，采用的规则为：

Q(s,a)←Q(s,a)+α[r+γQ(s′,a′)−Q(s,a)]Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \textcolor{red}{Q(s', a')} - Q(s, a)]

红色部分为不同的地方，这儿a′a'的选择不再仅仅是根据Q来了（取Q最大的），而是完全遵守当前策略（Policy）来得到的。

区别是什么？其实就是在ε-greedy上，完全遵守当前策略的话，那么就是有ε的可能性是完全随机的，而（1-ε）下是根据当前Q函数取了最大的那个action。所以Sarsa的Q函数更新过程是“知行合一”的，我在“确定了”下一步action后再更新行为价值，比如下一步可能由于ε-greedy落到了随机选择的那个a′a'。而Q-learning则是在“推演”之后的行为和行为价值的过程中仅仅设想了我“理性的”会选择Q最大的那一个来确定之后的行为价值参照（更新后的Q函数），而真实的下一步行动则是在更新的Q函数上采用当前Policy（i.e. ε-greedy）来制定的，所以真实的a′a'和在进行Q更新时候的所设想的a′a'，即arg max⁡a′Q(s′,a′)\argmax_{a'} Q(s', a')，可能是不一样的。为了区别这两种更新策略，定义了on-policy（目标策略=行为策略，比如Sarsa）和off-policy（目标策略!=行为策略，比如Q-learning）。

相比Q-learning，Sarsa更谨慎保守，因为Q-learning在Q函数的更新上总是朝收益最大的action倾斜，以此来直到实际的行为策略；而Sarsa更新Q函数的时候已经考虑了可能的随机探索情况，所以不会这么激进。