强化学习笔记(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 iterationPolicy 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. 强化学习方法汇总