强化学习笔记 (1)- 概述
本文主要介绍强化学习的一些基本概念:包括 MDP、Bellman 方程等, 并且讲述了如何从 MDP 过渡到 Reinforcement Learning。
强化学习的任务
这里还是放上 David Silver 的课程 的图,可以很清楚的看到整个交互过程。这就是人与环境交互的一种模型化表示,在每个时间点,大脑 agent 会从可以选择的动作集合 A 中选择一个动作 \(a_t\) 执行。环境则根据 agent 的动作给 agent 反馈一个 reward \(r_t\),同时 agent 进入一个新的状态。
知道了整个过程,任务的目标就出来了,那就是要能获取尽可能多的 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)\) 表示,其中
- \(S\) 是一个有限状态集
- \(A\) 是一个有限动作集
- \(P\) 是一个状态转移概率矩阵,\(P_a(s, s′)=P(s_{t+1}=s′|s_t=s, a_t=a)\) 表示在状态 \(s\) 下执行动作 \(a\) 后转移到状态 \(s′\) 的概率
- \(R\) 是一个奖励函数,\(R_a(s, s′)\) 表示在状态 \(s\) 下执行动作 \(a\) 后转移到状态 \(s′\) 所得到的即时回报 (reward)
- \(\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 这个目标,我们就会有两种方法:
- 直接优化策略 \(\pi(a|s)\) 或者 \(a = \pi(s)\) 使得回报更高
- 通过估计 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\) 了,其迭代过程如下图所示
Policy iteration
Policy iteration 同时更新价值 \(V\) 和策略 \(\pi\), 且一般可分成两步:
- Policy Evaluation,策略评估,就是上面公式 2 的过程。目的是在策略固定的情况下更新 Value Function 直到 value 收敛,从另一个角度来讲就是为了更好地估计基于当前策略的价值
- Policy Improvement,策略改进,就是上面公式 1 的过程。就是根据更新后的 Value Function 来更新每个状态下的策略直到策略稳定
这个方法本质上就是使用当前策略 (\(\pi\)) 产生新的样本,然后使用新的样本更好的估计策略的价值 (\(V(s)\)),然后利用策略的价值更新策略,然后不断反复。理论可以证明最终策略将收敛到最优
具体的算法流程如下所示
区别与局限
问题来了,上面的 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 方法。
参考资料
- Markov decision process
- DQN 从入门到放弃 4 动态规划与 Q-Learning
- 强化学习方法汇总