强化学习笔记(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} \]

则有

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

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

从 MDP 到 Reinforcement Learning

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

公式1：

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

公式2:

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

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

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

Value iteration

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

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

下标 \(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. 强化学习方法汇总