强化学习笔记 (1)- 概述

发表于 标签 ，

本文主要介绍强化学习的一些基本概念：包括 MDP、Bellman 方程等， 并且讲述了如何从 MDP 过渡到 Reinforcement Learning。

强化学习的任务

这里还是放上 David Silver 的课程 的图，可以很清楚的看到整个交互过程。这就是人与环境交互的一种模型化表示，在每个时间点，大脑 agent 会从可以选择的动作集合 A 中选择一个动作 \(a_t\) 执行。环境则根据 agent 的动作给 agent 反馈一个 reward \(r_t\)，同时 agent 进入一个新的状态。

RL

知道了整个过程，任务的目标就出来了，那就是要能获取尽可能多的 Reward。Reward 越多，就表示执行得越好。每个时间片，agent 根据当前的状态来确定下一步的动作。也就是说我们需要一个 state 找出一个 action，使得 reward 最大，从 state 到 action 的过程就称之为一个策略 Policy，一般用 \(\pi\) 表示:

强化学习的任务就是找到一个最优的策略 Policy 从而使 Reward 最多。

我们一开始并不知道最优的策略是什么，因此往往从随机的策略开始，使用随机的策略进行试验，就可以得到一系列的状态，动作和反馈：

\((s_1,a_1,r_1,s_2,a_2,r_2,...s_t,a_t,r_t)\)

这就是一系列的样本 Sample。强化学习的算法就是需要根据这些样本来改进 Policy，从而使得得到的样本中的 Reward 更好。由于这种让 Reward 越来越好的特性，所以这种算法就叫做强化学习 Reinforcement Learning。

MDP（Markov Decision Process）

强化学习的问题都可以模型化为 MDP(马尔可夫决策过程) 的问题，MDP 实际上是对环境的建模；MDP 与常见的 Markov chains 的区别是加入了 action 和 rewards 的概念。

因此，一个基本的 MDP 可以用一个五元组 \((S,A,P,R, \gamma)\) 表示，其中

  1. \(S\) 是一个有限状态集
  2. \(A\) 是一个有限动作集
  3. \(P\) 是一个状态转移概率矩阵，\(P_a(s, s′)=P(s_{t+1}=s′|s_t=s, a_t=a)\) 表示在状态 \(s\) 下执行动作 \(a\) 后转移到状态 \(s′\) 的概率
  4. \(R\) 是一个奖励函数，\(R_a(s, s′)\) 表示在状态 \(s\) 下执行动作 \(a\) 后转移到状态 \(s′\) 所得到的即时回报 (reward)
  5. \(\gamma\) 是一个折扣因子，一般取值在 [0,1]; 用来区分当前回报和未来回报的重要性，一般会加在未来的回报前，减小未来回报的权重。

因此，MDP 的核心问题就是找到一个策略 \(\pi(s)\) 来决定在状态 \(s\) 下选择哪个动作，这种情况下 MDP 就变成了一个 Markov chain，且此时的目标跟我们前面提到的强化学习的目标是一致的。

回报与价值函数

状态的好坏等价于对未来回报的期望。因此，引入回报 (Return) 来表示某个时刻 t 的状态将具备的回报：

\(G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^\infty\gamma^kR_{t+k+1}\)

上面 \(R\) 是 Reward 反馈，\(\gamma\) 是 discount factor（折扣因子）, 跟前面 MDP 中的符号的含义一致。

从上面的式子可以， 除非整个过程结束，否则我们无法获取所有的 reward 来计算出每个状态的 Return，因此，再引入一个概念: 价值函数 (value function), 记为 \(V(s)\)，通过 \(V(s)\) 来表示一个状态未来的潜在价值。从定义上看，value function 就是回报的期望：

\(V(s) = \mathbb E[G_t|S_t = s]\)

引出价值函数，对于获取最优的策略 Policy 这个目标，我们就会有两种方法：

  1. 直接优化策略 \(\pi(a|s)\) 或者 \(a = \pi(s)\) 使得回报更高
  2. 通过估计 value function 来间接获得优化的策略。道理很简单，通过价值函数可以知道每一种状态的好坏，这样我们就知道该怎么选择了（如选择动作使得下一状态的潜在价值最大），而这种选择就是我们想要的策略。

Bellman 方程

采用上面获取最优策略的第 2 种方法时，我们需要估算 Value Function，只要能够计算出价值函数，那么最优决策也就得到了。因此，问题就变成了如何计算 Value Function？

根据前面 \(G_t\) 和 \(V(s)\) 的定义，有

\[\begin{align} V(s) & = \mathbb E[G_t|S_t = s]\\\ & = \mathbb E[R_{t+1}+\gamma R_{t+2} + \gamma ^2R_{t+3} + ...|S_t = s]\\\ & = \mathbb E[R_{t+1}+\gamma (R_{t+2} + \gamma R_{t+3} + ...)|S_t = s]\\\ & = \mathbb E[R_{t+1}+\gamma G_{t+1}|S_t = s]\\\ & = \mathbb E[R_{t+1}+\gamma v(S_{t+1})|S_t = s] \end{align}\]

则有

\[\begin{align} V(s) = \mathbb E[R_{t+1} + \gamma V(S_{t+1})|S_t = s] \end{align}\]

上面这个公式就是 Bellman 方程的基本形态。从公式上看，当前状态的价值和下一步的价值以及当前的反馈 Reward 有关， 其中透出的含义就是价值函数的计算可以通过迭代的方式来实现。

从 MDP 到 Reinforcement Learning

回到 MDP 问题，如果我们知道了转移概率 \(P\) 和奖励函数 \(R\)，那么便可通过下面的方法求出最优策略 \(\pi(s)\), 首先，结合上面提到的价值函数和 Bellman 方程有

公式 1：

\[\begin{align} \pi(s):=\arg \max_a\ \{\sum_{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s'))\} \end{align}\]

公式 2:

\[\begin{align} V(s) := \sum_{s'}P_{\pi(s)}(s,s')(R_{\pi(s)}(s,s') + \gamma V(s')) \end{align}\]

公式 1 表示在状态 \(s\) 下的采取的最优动作，公式 2 表示在状态 \(s\) 下的价值，可以看到两者有依存关系

而在 转移概率 \(P\) 和奖励函数 \(R\) 已知的情况下，求解 MDP 问题常见做法有 Value iteration 或 Policy iteration

Value iteration

在 Value iteration 中，策略函数 \(\pi\) 没有被使用，迭代公式如下：

\[\begin{align} V_{i+1}(s) := \max_a \sum_{s'} P_a(s,s')(R_a(s,s') + \gamma V_i(s')) \end{align}\]

下标 \(i\) 表示第 \(i\) 次迭代，在每轮迭代中需要计算每个状态的价值，并且直到两次迭代结果的差值小于给定的阈值才能认为是收敛。

计算的出收敛的价值函数后，通过公式 1 就能够得出策略函数 \(\pi\) 了，其迭代过程如下图所示

Value Iteration

Policy iteration

Policy iteration 同时更新价值 \(V\) 和策略 \(\pi\), 且一般可分成两步：

  1. Policy Evaluation，策略评估，就是上面公式 2 的过程。目的是在策略固定的情况下更新 Value Function 直到 value 收敛，从另一个角度来讲就是为了更好地估计基于当前策略的价值
  2. Policy Improvement，策略改进，就是上面公式 1 的过程。就是根据更新后的 Value Function 来更新每个状态下的策略直到策略稳定

这个方法本质上就是使用当前策略 (\(\pi\)) 产生新的样本，然后使用新的样本更好的估计策略的价值 (\(V(s)\))，然后利用策略的价值更新策略，然后不断反复。理论可以证明最终策略将收敛到最优

具体的算法流程如下所示

Policy Iteration

区别与局限

问题来了，上面的 Policy Iteration 和 Value Iteration 有什么区别， 为什么一个叫 policy iteration，一个叫 value iteration？

原因其实很好理解，policy iteration 最后收敛的 value \(V\) 是当前 policy 下的 value 值（也做对 policy 进行评估），目的是为了后面的 policy improvement 得到新的 policy；所以是在显式地不停迭代 policy。

而 value iteration 最后收敛得到的 value 是当前 state 状态下的最优的 value 值。当 value 最后收敛，那么最优的 policy 也就得到的。虽然这个过程中 policy 在也在隐式地更新，但是一直在显式更新的是 value 的，所以叫 value iteration。

从上面的分析看，value iteration 较 之 policy iteration 更直接。不过问题也都是一样，都需要知道转移概率 \(P\) 和奖励函数 \(R\)。

但是对于 Reinforcement Learning 这一类问题，转移概率 \(P\) 往往是不知道，知道转移概率 \(P\) 也就称为获得了模型 Model，这种通过模型来获取最优动作的方法也就称为 Model-based 的方法。但是现实情况下，很多问题是很难得到准确的模型的，因此就有 Model-free 的方法来寻找最优的动作，像 Q-learning，Policy Gradient，Actor Critic 这一类方法都是 model-free 的。

前面的方法问题是需要已知转移概率 \(P\), 目的是为了遍历当前状态后的所有可能的状态，因此如果采用贪婪的思想，那么就不需要不遍历后面所有的状态，而是直接采取价值最大的状态动作来执行。

Q-learning 实际上就是采用这种思想的，Q-Learning 的基本思想是根据 value iteration 得到的，但要明确一点是 value iteration 每次都对所有的 Q 值更新一遍，也就是所有的状态和动作。但事实上在实际情况下我们没办法遍历所有的状态，还有所有的动作，因此，我们只能得到有限的系列样本。具体的算法流程会再下一篇文章具体介绍。

综上，本文主要介绍了强化学习的任务和一些概念，以及从 MDP 如何过渡到 Reinforcement，在后续的文章中会陆续介绍 Q-learning 类方法，Policy gradient 类方法以及结合两者的 Actor Critic 方法。

参考资料

  1. Markov decision process
  2. DQN 从入门到放弃 4 动态规划与 Q-Learning
  3. 强化学习方法汇总