强化学习笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  主要记录关于强化学习的一些笔记,强化学习主要分为基于动态规划的有模型学习和基于蒙特卡洛方法的免模型学习。

强化学习(Reinforcement Learning)

  强化学习主要采用了任务与奖赏的思想,强化学习任务也通常用马尔可夫决策过程(Markov Decision Process, MDP)来描述,可以用一个四元组\(E=<X,A,P,R>\)来表示,其中\(E\)表示机器所处的环境,\(x \in X\)表示状态空间,\(a \in A\)表示动作空间,\(P : X \times A \times X \mapsto \mathbb{R}\)指定了状态转移概率,\(R : X \times A \times X \mapsto \mathbb{R}\)指定了奖赏。
  下图是西瓜书中的给的一个非常形象的例子。

  机器要做的是在环境中不断尝试而学得一个策略(policy)\(\pi\),根据这个策略,在状态\(x\)下执行的动作\(a=\pi(x)\)。策略有两种表达方式:

  • 一种是表示为函数\(\pi : X \mapsto A\),确定性策略常用这方式。
  • 另一种是用概率表示\(\pi : X \times A \mapsto \mathbb{R}\),随机性策略常用这种方式,\(\pi(x, a)\)表示在状态\(x\)下选择动作\(a\)的概率,其中\(\sum_{a} \pi(x, a)=1\)

  策略的优劣取决于长期执行这一策略后得到的累积奖赏,在强化学习的任务中,学习的目的也就是找到能使长期累积奖赏最大化的策略,长期累积奖赏有多种计算方式,常用的有两种:

  • \(T\)步累积奖赏:\(\mathbb{E}\left[\frac{1}{T} \sum_{t=1}^{T} r_{t}\right]\)
  • \(\gamma\)折扣累积奖赏:\(\mathbb{E}\left[\sum_{t=0}^{+\infty} \gamma^{t} r_{t+1}\right]\)

\(K\)-摇臂赌博机

探索-利用窘境(Exploration-Exploitation dilemma)

  与一般监督学习不同,强化学习任务的最终奖赏是在多步动作之后才能观察到,这里我们不妨先考虑比较简单的情形:最大化单步奖赏,即仅考虑一步操作。需注意的是,即便在这样的简化情形下,强化学习仍与监督学习有显著不同,因为机器需通过尝试来发现各个动作产生的结果,而没有训练数据告诉机器应当做哪个动作。
  欲最大化单步奖赏需考虑两个方面:一是需知道每个动作带来的奖赏,二是要执行奖赏最大的动作。若每个动作对应的奖赏是一个确定值,那么尝试一遍所有的动作便能找出奖赏最大的动作。然而,更一般的情形是,一个动作的奖赏值是来自于一个概率分布,仅通过一次尝试并不能确切地获得平均奖赏值。
  单步强化学习任务对应了一个理论模型,即\(K\)-摇臂赌博机”(K-armed bandit)。赌博机有\(K\)个摇臂,赌徒在投入一个硬币后可选择按下其中一个摇臂,每个摇臂以一定的概率吐出硬币,但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏,即获得最多的硬币,通常有两种策略:

  • 若仅为获知每个摇臂的期望奖赏,则可采用“仅探索”(exploration-only)法:将所有的尝试机会平均分配给每个摇臂(即轮流按下每个摇臂),最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。
  • 若仅为执行奖赏最大的动作,则可采用“仅利用”(exploitation-only)法:按下目前最优的(即到目前为止平均奖赏最大的)摇臂,若有多个摇臂同为最优,则从中随机选取一个。

  “仅探索”法能很好地估计每个摇臂的奖赏,却会失去很多选择最优摇臂的机会。“仅利用”法则相反,它没有很好地估计摇臂期望奖赏,很可能经常选不到最优摇臂。这两种方法都难以使最终的累积奖赏最大化。“探索”(即估计摇臂的优劣)和“利用”(即选择当前最优摇臂)这两者是矛盾的,因为尝试次数(即总投币数)有限,加强了一方则会自然削弱另一方,这就是强化学习所面临的“探索-利用窘境。

\(\epsilon\)-贪心(epsilon-Greedy)

  显然,欲累积奖赏最大,则必须在探索与利用之间达成较好的折中贪心。\(\epsilon\)-贪心法基于一个概率\(\epsilon\)来对探索和利用进行折中:每次尝试时,以\(\epsilon\)的概率进行探索,即以均匀概率随机选取一个摇臂,以\(1- \epsilon\)的概率进行利用,即选择当前平均奖赏最高的摇臂(若有多个,则随机选取一个)。
  \(Q(k)\)记录摇臂\(k\)的平均奖赏,若摇臂\(k\)被尝试了\(n\)次,得到的奖赏为\(v_1,v_2,\cdots,v_n\),则平均奖赏为: \[ Q(k)=\frac{1}{n} \sum_{i=1}^{n} v_{i} \qquad(1) \]   \(Q_{n}(k)\)也可以如式(2)一样进行增量式更新,这样无论摇臂被尝试了多少次,也只需要记录两个值。
\[ \begin{aligned} Q_{n}(k)&=\frac{1}{n}\left((n-1) \times Q_{n-1}(k)+v_{n}\right) \\ &=Q_{n-1}(k)+\frac{1}{n}\left(v_{n}-Q_{n-1}(k)\right) \qquad(2) \end{aligned} \]   算法流程图如下图所示。

  若摇臂奖赏的不确定性较大,例如概率分布较宽时,则需更多的探索,此时需要较大的\(\epsilon\)值。若摇臂的不确定性较小,例如概率分布较集中时,则少量的尝试就能很好地近似真实奖赏,此时需要的\(\epsilon\)较小。若尝试次数非常大,那么在一段时间后,摇臂的奖赏都能很好地近似出来,不再需要探索,这种情形下可让\(\epsilon\)随着尝试次数的增加而逐渐减小,例如\(\epsilon = \frac{1}{\sqrt{t}}\)

Softmax

  Softmax算法基于当前己知的摇臂平均奖赏来对探索和利用进行折中。若各摇臂的平均奖赏相当,则选取各摇臂的概率也相当。若某些摇臂的平均奖赏明显高于其他摇臂,则它们被选取的概率也明显更高。Softmax算法中摇臂概率的分配是基于Boltzmann分布: \[ P(k)=\frac{e^{\frac{Q(k)}{\tau}}}{\sum_{i=1}^{K} e^{\frac{Q(i)}{\tau}}} \]   其中,\(Q(i)\)记录当前摇臂的平均奖赏,\(\tau>0\)称为温度,\(\tau\)越小则平均奖赏高的摇臂被选取的概率越高,\(\tau\)趋于0时Softmax将趋于“仅利用”,\(\tau\)趋于无穷大时Softmax则将趋于“仅探索”。算法流程图如下:

  对于离散状态空间、离散动作空间上的多步强化学习任务,一种直接的办法是将每个状态上动作的选择看作一个\(K\)-摇臂赌博机问题,用强化学习任务的累积奖赏来代替\(K\)-摇臂赌博机算法中的奖赏函数,即可将赌博机算法用于每个状态:对每个状态分别记录各动作的尝试次数、当前平均累积奖赏等信息,基于赌博机算法选择要尝试的动作。然而这样的做法有很多局限,因为它没有考虑强化学习任务马尔可夫决策过程的结构,若能有效考虑马尔可夫决策过程的特性,则可有更聪明的办法。

有模型的学习(model-based learning)

  模型已知指的是四元组\(E=<X,A,P,R>\)均为已知,在已知模型的环境中学习称为有模型学习。此时\(P_{x \rightarrow x^{\prime}}^{a}\)\(R_{x \rightarrow x^{\prime}}^{a}\)均是己知的。为便于讨论,不妨假设状态空间\(X\)和动作空间\(A\)均为有限空间。

策略评估

  在模型己知时,对任意策略\(\pi\)能估计出该策略带来的期望累积奖赏。记函数\(V^{\pi}(x)\)表示从状态\(x\)出发,使用策略\(\pi\)所带来的累积奖赏。函数\(Q^{\pi}(x, a)\)表示从状态\(x\)出发,执行动作\(a\)后再使用策略\(\pi\)带来的累积奖赏。这里\(V(\cdot)\)称为“状态值函数”( state value function),\(Q(\cdot)\)称为“状态-动作值函数”(state-action value function),分别表示指定“状态”上以及指定“状态-动作”上的累积奖赏。
  由累积奖赏的定义,有状态值函数: \[ \left\{\begin{aligned} V_{T}^{\pi}(x) &=\mathbb{E}_{\pi}\left[\frac{1}{T} \sum_{t=1}^{T} r_{t} | x_{0}=x\right], & T步累积奖赏 \\ V_{\gamma}^{\pi}(x) &=\mathbb{E}_{\pi}\left[\sum_{t=0}^{+\infty} \gamma^{t} r_{t+1} | x_{0}=x\right],& \gamma折扣累积奖赏 \end{aligned}\right. \qquad(3) \]   令\(x_0\)表示起始状态,\(a_0\)表示起始状态上采取的第一个动作,对于\(T\)步累积奖赏,用下标\(t\)表示后续执行的步数,我们有状态-动作值函数: \[ \left\{\begin{array}{l}{Q_{T}^{\pi}(x, a)=\mathbb{E}_{\pi}\left[\frac{1}{T} \sum_{t=1}^{T} r_{t} | x_{0}=x, a_{0}=a\right]} \\ {Q_{\gamma}^{\pi}(x, a)=\mathbb{E}_{\pi}\left[\sum_{t=0}^{+\infty} \gamma^{t} r_{t+1} | x_{0}=x, a_{0}=a\right]}\end{array}\right. \qquad(4) \]   由于MDP具有马尔可夫性质,即系统下一时刻的状态仅由当前时刻的状态决定,不依赖于以往任何状态,于是值函数有很简单的递归形式,对于\(T\)步累积奖赏有: \[ \begin{aligned} V_{T}^{\pi}(x) &=\mathbb{E}_{\pi}\left[\frac{1}{T} \sum_{t=1}^{T} r_{t} | x_{0}=x\right] \\ &=\mathbb{E}_{\pi}\left[\frac{1}{T} r_{1}+\frac{T-1}{T} \frac{1}{T-1} \sum_{t=2}^{T} r_{t} | x_{0}=x\right] \\ &=\sum_{a \in A} \pi(x, a) \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} \mathbb{E}_{\pi}\left[\frac{1}{T-1} \sum_{t=1}^{T-1} r_{t} | x_{0}=x^{\prime}\right]\right) \\ &=\sum_{a \in A} \pi(x, a) \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}^{\pi}\left(x^{\prime}\right)\right) \end{aligned} \qquad(5) \]   类似对于\(\gamma\)折扣累积奖赏有: \[ V_{\gamma}^{\pi}(x)=\sum_{a \in A} \pi(x, a) \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}^{\pi}\left(x^{\prime}\right)\right) \qquad(6) \]   需注意的是,正是由于\(P\)\(R\)已知,才可以进行全概率展开。
  用上面的递归等式来计算值函数,实际上就是一种动态规划算法。对于\(V_{\gamma}^{\pi}(x)\)可设想递归一直进行下去,直到最初的起点,也就是说,从值函数的初始值\(V_{0}^{\pi}\)出发,通过一次迭代能计算出每个状态的单步奖赏\(V_{1}^{\pi}\),进而从单步奖赏出发,通过一次迭代计算出两步累积\(V_{2}^{\pi}\),以此递归循环,对于\(T\)步累积奖赏,只需迭代\(T\)轮就能精确地求出值函数。算法流程图如下图所示:

  对于\(V_{\gamma}^{\pi}\),由于\(\gamma^t\)\(t\)很大时趋于0,因此也能使用类似的算法。由于算法可能会迭代很多次因此需设置一个停止准则,常见的是设置一个阈值\(\theta\),若在执行一次迭代后值函数的改变小于\(\theta\)则算法停止,条件为\(\max _{x \in X}\left|V(x)-V^{\prime}(x)\right|<\theta\)
  有了状态值函数\(V\),就能直接计算出状态-动作值函数: \[ \left\{\begin{aligned} Q_{T}^{\pi}(x, a) &=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}^{\pi}\left(x^{\prime}\right)\right) \\ Q_{\gamma}^{\pi}(x, a) &=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}^{\pi}\left(x^{\prime}\right)\right) \end{aligned}\right. \qquad(7) \]

策略改进

  理想的策略应能最大化累积奖赏,即: \[ \pi^{*}=\underset{\pi}{\arg \max } \sum_{x \in X} V^{\pi}(x) \qquad(8) \]   一个强化学习任务可能有多个最优策略,最优策略所对应的值函数\(V^*\)称为最优值函数,即: \[ \forall x \in X : V^{*}(x)=V^{\pi^{*}}(x) \qquad(9) \]   注意,当策略空间无约束时,式(9)的\(V^{*}\)才是最优策略对应的值函数,例如对离散状态空间和离散动作空间,策略空间是所有状态上所有动作的组合,共有\(|A|^{|X|}\)种不同的策略。若策略空间有约束,则违背约束的策略是不合法的,即便其值函数所取得的累积奖赏值最大,也不能作为最优值函数。
  由于最优值函数的累积奖赏值已达最大,可对前面的Bellman等式(5)和(6)做一个改动,即将对动作的求和改为取最优: \[ \left\{\begin{array}{l}{V_{T}^{*}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}^{*}\left(x^{\prime}\right)\right)} \\ {V_{\gamma}^{*}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}^{*}\left(x^{\prime}\right)\right)}\end{array}\right. \qquad(10) \]   也就是: \[ V^{*}(x)=\max _{a \in A} Q^{\pi^{*}}(x, a) \qquad(11) \]   带入式(7)可得最优状态-动作值函数: \[ \left\{\begin{array}{l}{Q_{T}^{*}(x, a)=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} \max _{a^{\prime} \in A} Q_{T-1}^{*}\left(x^{\prime}, a^{\prime}\right)\right) ;} \\ {Q_{\gamma}^{*}(x, a)=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma \max _{a^{\prime} \in A} Q_{\gamma}^{*}\left(x^{\prime}, a^{\prime}\right)\right)}\end{array}\right. \qquad(12) \]   上述关于最优值函数的等式,称为最优Bellman等式,其唯一解是最优值函数。最优Bellman等式揭示了非最优策略的改进方式:将策略选择的动作改变为当前最优的动作。显然,这样的改变能使策略更好。不妨令动作改变后对应的策略为\(\pi^{'}\)改变动作的条件为\(Q^{\pi}\left(x, \pi^{\prime}(x)\right) \geqslant V^{\pi}(x)\),以\(\gamma\)折扣累积奖赏为例,由式(7)可计算出递推不等式: \[ \begin{aligned} V^{\pi}(x) & \leqslant Q^{\pi}\left(x, \pi^{\prime}(x)\right) \\ &=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{\pi^{\prime}(x)}\left(R_{x \rightarrow x^{\prime}}^{\pi^{\prime}(x)}+\gamma V^{\pi}\left(x^{\prime}\right)\right) \\ & \leqslant \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{\pi^{\prime}(x)}\left(R_{x \rightarrow x^{\prime}}^{\pi^{\prime}(x)}+\gamma Q^{\pi}\left(x^{\prime}, \pi^{\prime}\left(x^{\prime}\right)\right)\right) \\ &=\cdots \\ &= V^{\pi^{'}}(x)\end{aligned} \qquad(13) \]   值函数对于策略的每一点改进都是单调递增的,因此对于当前策略\(\pi\),可放心地将其改进为: \[ \pi^{\prime}(x)=\underset{a \in A}{\arg \max } Q^{\pi}(x, a) \qquad(14) \]   直到\(\pi\)\(\pi^{'}\)一致,不再发生变化,此时就满足了最优Bellman等式,即找到了最优策略。

策略迭代(policy iteration)与值迭代(value iteration)

  我们知道如何评估一个策略的值函数,并且知道在策略评估后如何改进至获得最优策略,将这两者结合起来即可得到求解最优解的方法,即从一个初始策略(通常是随机策略)出发,先进行策略评估,然后改进策略,评估改进的策略,再进一步改进策略,不断迭代进行策略评估和改进,直到策略收敛、不再改变为止,这样的做法称为策略迭代。下图是算法流程图(是基于\(T\)步累积奖赏策略迭代算法):

  类似的,可得到基于\(\gamma\)折扣累积奖赏的策略迭代算法。策略迭代算法在每次改进策略后都需重新进行策略评估,这通常比较耗时。
  由式(3)可知,策略改进与值函数的改进是一致的,因此可将策略改进视为值函数的改善,即由式(10)可得: \[ \left\{\begin{array}{l}{V_{T}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(\frac{1}{T} R_{x \rightarrow x^{\prime}}^{a}+\frac{T-1}{T} V_{T-1}\left(x^{\prime}\right)\right)} \\ {V_{\gamma}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V_{\gamma}\left(x^{\prime}\right)\right)}\end{array}\right. \qquad(15) \]   这就是值迭代算法,算法流程图如下所示(是基于\(T\)步累积奖赏的值迭代算法):

  若采用\(\gamma\)折扣累积奖赏,只需将上图算法中第3行替换为: \[ \forall x \in X : V^{\prime}(x)=\max _{a \in A} \sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V\left(x^{\prime}\right)\right) \qquad(16) \]   从上面的算法可看出,在模型己知时强化学习任务实际上就是基于动态规划的寻优问题,与监督学习不同,这里并未涉及到泛化能力,而是为每一个状态找到最好的动作。

免模型学习(model-free learning)

  在现实的强化学习任务中,环境的转移概率、奖赏函数往往很难得知,甚至很难知道环境中一共有多少状态,若学习算法不依赖于环境建模,则称为免模型学习。

蒙特卡罗强化学习(Monte Carlo Learning)

  在免模型情形下,由于模型未知而导致无法做全概率展开,策略迭代算法无法进行策略无法评估,因此只能通过在环境中执行选择的动作,来观察转移的状态和得到的奖赏。受\(K\)摇臂赌博机的启发,一种直接的策略评估替代方法是多次“采样”,然后求取平均累积奖赏来作为期望累积奖赏的近似,这就是蒙特卡罗强化学习,因为采样必须为有限次数,因此该方法更适合于使用\(T\)步累积奖赏的强化学习任务。
  另一个麻烦的地方是,策略迭代算法估计的是状态值函数\(V\),而最终的策略是通过状态-动作值函数\(Q\)来获得。当模型已知时,从\(V\)\(Q\)有很简单的转换方法,而当模型未知时,这也会出现困难。于是,我们将估计对象从\(V\)转变为\(Q\),即估计每一对状态-动作的值函数。
  此外,在模型未知的清形下,机器只能是从一个起始状态(或起始状态集合)开始探索环境,而策略迭代算法由于需对每个状态分别进行估计,因此,我们只能在探索的过程中逐渐发现各个状态并估计各状态动作对的值函数。
  综合起来在模型未知的情形下,我们从起始状态出发,使用某种策略进行采样,执行该策略\(T\)步并获得轨迹\(<x_{0}, a_{0}, r_{1}, x_{1}, a_{1}, r_{2}, \dots, x_{T-1}, a_{T-1}, r_{T}, x_{T}>\)。然后,对轨迹中出现的每一对状态-动作,记录其后的奖赏之和,作为该状态-动作对的一次累积奖赏采样值,多次采样得到多条轨迹后,将每个状态-动作对的累积奖赏采样值进行平均,即得到状态-动作值函数的估计。
  可以看出,欲较好地获得值函数的估计,就需要多条不同的采样轨迹。而我们的策略有可能是确定性的,即对于某个状态只会输出一个动作,若使用这样的策略进行采样,则只能得到多条相同的轨迹,这与\(K\)摇臂赌博机的“仅利用”法面临相同的问题,因此可借鉴探索与利用折中的办法,例如使用\(\epsilon\)-贪心法,以\(\epsilon\)的概率从所有动作中均匀随机选取一个,以\(1-\epsilon\)的概率选取当前最优动作,我们将确定性的策略\(\pi\)称为“原始策略”,在原始策略上使用\(\epsilon\)-贪心法的策略记为: \[ \pi^{\epsilon}(x)=\left\{\begin{array}{l}{\pi(x), \qquad\qquad\qquad\quad\quad\qquad以概率1-\epsilon} \\ {A中以均匀概率选取的动作, \qquad以概率\epsilon}\end{array}\right. \qquad(17) \]   分析一下,对于最大化值函数的原始策略\(\pi=\arg \max _{a} Q(x, a)\),其\(\epsilon\)-贪心策略\(\pi^\epsilon\)中,当前最优动作被选中的概率是\(1-\epsilon+\frac{\epsilon}{|A|}\),而每个非最优动作被选中的概率是\(\frac{\epsilon}{|A|}\)。于是,每个动作都有可能被选取,而多次采样将会产生不同的采样轨迹。
  与策略迭代算法类似,使用蒙特卡罗方法进行策略评估后,同样要对策略进行改进,与式(13)揭示的单调性类似,通过换入当前最优动作来改进策略,对于任意原始策略\(\pi\),其\(\epsilon\)-贪心策略\(\pi^\epsilon\)仅是将\(\epsilon\)的概率均匀分配给所有动作,因此对于最大化值函数的原始策略\(\pi^{'}\),同样有\(Q^{\pi}\left(x, \pi^{\prime}(x)\right) \geqslant V^{\pi}(x)\),于是式(13)仍成立,即可以使用同样方法来进行策略改进。
  下图给出了同策略(on-policy)蒙特卡罗强化学习算法,即被评估与被改进的是同一个策略,算法中奖赏均值采用增量式计算,每采样出一条轨迹,就根据该轨迹涉及的所有“状态-动作”对来对值函数进行更新。

  同策略蒙特卡罗强化学习算法最终产生的是\(\epsilon\)-贪心策略,然而,引入\(\epsilon\)-贪心是为了便于策略评估,在使用策略时并不需要\(\epsilon\)-贪心。我们需要改进的是原始(非\(\epsilon\)-贪心)策略。
  我们需要仅在策略评估时引入\(\epsilon\)-贪心,而在策略改进时却改进原始策略。不妨用两个不同的策略\(\pi\)\(\pi^{'}\)来产生采样轨迹,两者的区别在于每个状态-动作对被采样的概率不同,函数\(f\)在概率分布\(p\)下的期望可表达为: \[ \mathbb{E}[f]=\int_{x} p(x) f(x) \mathrm{d} x \]   通过从概率分布\(p\)上的采样\(\{x_1,x_2,\cdots,x_m\}\)来估计\(f\)的期望,即: \[ \hat{\mathbb{E}}[f]=\frac{1}{m} \sum_{i=1}^{m} f(x_i) \]   若引入另一个分布\(q\),则函数\(f\)在概率分布\(p\)下的期望也可等价地写为: \[ \mathbb{E}[f]=\int_{x} q(x) \frac{p(x)}{q(x)} f(x) \mathrm{d} x \]   上式可看作\(\frac{p(x)}{q(x)} f(x)\)在分布\(q\)下的期望,因此通过在\(q\)上的采样\(\{x_1^{'},x_2^{'},\cdots,x_m^{'}\}\)可估计为: \[ \hat{\mathbb{E}}[f]=\frac{1}{m} \sum_{i=1}^{m} \frac{p\left(x_{i}^{\prime}\right)}{q\left(x_{i}^{\prime}\right)} f\left(x_{i}^{\prime}\right) \qquad(18) \]   使用策略\(\pi\)的采样轨迹来评估策略\(\pi\),实际上就是对累积奖赏估计期望: \[ Q(x, a)=\frac{1}{m} \sum_{i=1}^{m} R_{i} \]   其中\(R_i\)表示第\(i\)条轨迹上自状态\(x\)至结束的累积奖赏,若改用策略\(\pi^{'}\)的采样轨迹来评估策略\(\pi\),则仅需对累积奖赏加权,即: \[ Q(x, a)=\frac{1}{m} \sum_{i=1}^{m} \frac{P_{i}^{\pi}}{P_{i}^{\pi^{\prime}}} R_{i} \]   其中\(P^{\pi}_i\)\(P^{\pi^{'}}_i\)分别表示两个策略产生第\(i\)条轨迹的概率,对于给定的一条轨迹\(\left\langle x_{0}, a_{0}, r_{1}, \dots, x_{T-1}, a_{T-1}, r_{T}, x_{T}\right\rangle\),策略\(\pi\)产生该轨迹的概率为: \[ P^{\pi}=\prod_{i=0}^{T-1} \pi\left(x_{i}, a_{i}\right) P_{x_{i} \rightarrow x_{i+1}}^{a_{i}} \]   虽然这里用到了环境的转移概率\(P_{x_{i} \rightarrow x_{i+1}}^{a_{i}}\),但式(18)中实际只需两个策略概率的比值: \[ \frac{P^{\pi}}{P^{\pi^{\prime}}}=\prod_{i=0}^{T-1} \frac{\pi\left(x_{i}, a_{i}\right)}{\pi^{\prime}\left(x_{i}, a_{i}\right)} \]   如果\(\pi\)为确定性策略而\(\pi^{'}\)\(\pi\)\(\epsilon\)-贪心策略,则\(\pi\left(x_{i}, a_{i}\right)\)对于\(a_i=\pi(x_i)\)始终为1,\(\pi^{\prime}\left(x_{i}, a_{i}\right)\)\(\frac{\epsilon}{|A|}\)\(1-\epsilon+\frac{\epsilon}{|A|}\),于是就能对策略\(\pi\)进行评估了,下图给出了异策略(off-policy)蒙特卡罗强化学习算法的伪代码:

时序差分学习(Temporal Difference Learning)

  基于动态规划的策略迭代和值迭代算法在每执行一步策略后就进行值函数更新两者相比,蒙特卡罗强化学习算法的效率低得多,因为蒙特卡罗强化学习算法没有充分利用强化学习任务的MDP结构,它通过考虑采样轨迹,克服了模型未知给策略估计造成的困难,它需在完成一个采样轨迹后再更新策略的值估计。而时序差分学习则结合了动态规划与蒙特卡罗方法的思想,能做到更高效的免模型学习。
  蒙特卡罗强化学习算法的本质是通过多次尝试后求平均来作为期望累积奖赏的近似,但它在求平均时是批处理式进行的,即在一个完整的采样轨迹完成后再对所有的状态动作对进行更新,实际上这个更新过程能增量式进行。对于状态-动作对\((x,a)\),不妨假定基于\(t\)个采样已估计出值函数\(Q_{t}^{\pi}(x, a)=\frac{1}{t} \sum_{i=1}^{t} r_{i}\),则在得到第\(t+1\)个采样\(r_{t+1}\)时,类似式(2)有: \[ Q_{t+1}^{\pi}(x, a)=Q_{t}^{\pi}(x, a)+\frac{1}{t+1}\left(r_{t+1}-Q_{t}^{\pi}(x, a)\right) \]   这也是一个增量式的,将\(\frac{1}{t+1}\)替换为系数\(\alpha_{t+1}\),则可将增量项写作\(\alpha_{t+1}\left(r_{t+1}-Q_{t}^{\pi}(x, a)\right)\)。在实践中通常令\(\alpha_t\)为一个较小的正数值\(\alpha\),若将\(Q_{t}^{\pi}(x, a)\)展开为每步累积奖赏之和,则可看出系数之和为1,即令\(\alpha_t=\alpha\)不会影响\(Q_t\)是累积奖赏之和这一性质,更新步长\(\alpha\)越大,则越靠后的累积奖赏越重要。
  以\(\gamma\)折扣累积奖赏为例,利用动态规划方法且考虑到模型未知时使用状态动作值函数更方便,由式(7)有: \[ \begin{aligned} Q^{\pi}(x, a) &=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma V^{\pi}\left(x^{\prime}\right)\right) \\ &=\sum_{x^{\prime} \in X} P_{x \rightarrow x^{\prime}}^{a}\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma \sum_{a^{\prime} \in A} \pi\left(x^{\prime}, a^{\prime}\right) Q^{\pi}\left(x^{\prime}, a^{\prime}\right)\right) \end{aligned} \]   通过增量求和可得,其中\(x^{'}\)是前一次在状态\(x\)执行动作\(a\)后转移到的状态,\(a^{'}\)是策略\(\pi\)\(x^{'}\)上选择的动作: \[ Q_{t+1}^{\pi}(x, a)=Q_{t}^{\pi}(x, a)+\alpha\left(R_{x \rightarrow x^{\prime}}^{a}+\gamma Q_{t}^{\pi}\left(x^{\prime}, a^{\prime}\right)-Q_{t}^{\pi}(x, a)\right) \qquad(19) \]   使用式(19),每执行一步策略就更新一次值函数估计,于是得到下图的Sarsa算法,该算法由于每次更新值函数需知道前一步的状态(state)、前一步的动作(action)、奖赏值(reward)、当前状态(state)、将要执行的动作(action)。Sarsa是一个同策略算法,算法中评估和执行的均为\(\epsilon\)-贪心策略。

  将Sarsa修改为异策略算法,则得到下图描述的\(Q\)学习(Q-learning)算法,该算法评估的是\(\epsilon\)-贪心策略,而执行的是原始策略。

值函数近似(value function approximation)

  前面我们一直假定强化学习任务是在有限状态空间上进行,而现实强化学习任务所面临的状态空间往往是连续的,有无穷多个状态。
  一个直接的想法是对状态空间进行离散化,将连续状态空间转化为有限离散状态空间,然而如何有效地对状态空间进行离散化是一个难题,尤其是在对状态空间进行探索之前。实际上,我们不妨直接对连续状态空间的值函数进行学习。假定状态空间为\(n\)维实数空间\(X=\mathbb{R}^{n}\),先考虑简单情形,即值函数能表达为状态的线性函数: \[ V_{\boldsymbol{\theta}}(\boldsymbol{x})=\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x} \qquad(20) \]   其中\(\boldsymbol{x}\)为状态向量,\(\boldsymbol{\theta}\)为参数向量。由于此时的值函数难以像有限状态那样精确记录每个状态的值,因此这样值函数的求解被称为值函数近似。
  我们希望通过式(20)学得的值函数尽可能近似真实值函数\(V^{\pi}\),近似程度常用最小二乘误差来度量: \[ E_{\boldsymbol{\theta}}=\mathbb{E}_{\boldsymbol{x} \sim \pi}\left[\left(V^{\pi}(\boldsymbol{x})-V_{\boldsymbol{\theta}}(\boldsymbol{x})\right)^{2}\right] \]   其中\(\mathbb{E}_{\boldsymbol{x} \sim \pi}\)表示由策略\(\pi\)所采样而得的状态上的期望。
  为了使误差最小化采用梯度下降法对误差求负导数: \[ \begin{aligned}-\frac{\partial E_{\boldsymbol{\theta}}}{\partial \boldsymbol{\theta}} &=\mathbb{E}_{\boldsymbol{x} \sim \pi}\left[2\left(V^{\pi}(\boldsymbol{x})-V_{\boldsymbol{\theta}}(\boldsymbol{x})\right) \frac{\partial V_{\boldsymbol{\theta}}(\boldsymbol{x})}{\partial \boldsymbol{\theta}}\right] \\ &=\mathbb{E}_{\boldsymbol{x} \sim \pi}\left[2\left(V^{\pi}(\boldsymbol{x})-V_{\boldsymbol{\theta}}(\boldsymbol{x})\right) \boldsymbol{x}\right] \end{aligned} \]   于是可得到对于单个样本的更新规则: \[ \boldsymbol{\theta}=\boldsymbol{\theta}+\alpha\left(V^{\pi}(\boldsymbol{x})-V_{\boldsymbol{\theta}}(\boldsymbol{x})\right) \boldsymbol{x} \]   我们并不知道策略的真实值函数\(V^{\pi}\),但可借助时序差分学习基于\(V^{\pi}(\boldsymbol{x})=r+\gamma V^{\pi}\left(\boldsymbol{x}^{\prime}\right)\)用当前估计的值函数代替真实值函数,即: \[ \begin{aligned} \boldsymbol{\theta} &=\boldsymbol{\theta}+\alpha\left(r+\gamma V_{\boldsymbol{\theta}}\left(\boldsymbol{x}^{\prime}\right)-V_{\boldsymbol{\theta}}(\boldsymbol{x})\right) \boldsymbol{x} \\ &=\boldsymbol{\theta}+\alpha\left(r+\gamma \boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x}^{\prime}-\boldsymbol{\theta}^{\mathrm{T}} \boldsymbol{x}\right) \boldsymbol{x} \end{aligned} \]   其中\(\boldsymbol{x}^{\prime}\)是下一时刻的状态。
  需注意的是,在时序差分学习中需要状态-动作值函数以便获取策略。我们可以令\(\boldsymbol{\theta}\)作用于表示状态和动作的联合向量上,例如给状态向量增加一维用于存放动作编号,即将式(20)中的\(\boldsymbol{x}\)替换为\((\boldsymbol{x};a)\),另一种做法是用0/1对动作选择进行编码得到向量\(\boldsymbol{a}=(0 ; \ldots ; 1 ; \ldots ; 0)\),其中“1”表示该动作被选择,再将状态向量与其合并得到\((\boldsymbol{x};a)\),用于替换式(10)中的\(\boldsymbol{x}\)。这样就使得线性近似的对象为状态-动作值函数。
  下图是线性值函数近似Sarsa算法,类似地可得到线性值函数近似\(Q\)学习算法。显然,可以容易地用其他学习方法来代替式(10)中的线性学习器,例如通过引入核方法实现非线胜值函数近似。

模仿学习(Imitation Learning)

  在强化学习的经典任务设置中,机器所能获得的反馈信息仅有多步决策后的累积奖赏,但在现实任务中,往往能得到人类专家的决策过程范例,例如在AlphaGo能学习人类经典的棋谱和经典的范例,这就称为模仿学习。

直接模仿学习

  强化学习任务中多步决策的搜索空间巨大,基于累积奖赏来学习很多步之前的合适决策非常困难,而直接模仿人类专家的状态-动作对可显著缓解这一困难,这称为直接模仿学习。
  假定我们获得了一批人类专家的决策轨迹数据\(\left\{\tau_{1}, \tau_{2}, \ldots, \tau_{m}\right\}\),每条轨迹包含状态和动作序列,其中\(n_i\)为第\(i\)条轨迹中的转移次数: \[ \tau_{i}=\left\langle s_{1}^{i}, a_{1}^{i}, s_{2}^{i}, a_{2}^{i}, \ldots, s_{n_{i}+1}^{i}\right\rangle \]   有了这样的数据,就相当于告诉机器在什么状态下应选择什么动作,于是可利用监督学习来学得符合人类专家决策轨迹数据的策略。
  我们可将所有轨迹上的所有状态-动作对抽取出来,构造出一个新的数据集合: \[ D=\left\{\left(s_{1}, a_{1}\right),\left(s_{2}, a_{2}\right), \ldots,\left(s \sum_{i=1}^{m} n_{i}, a_{\sum_{i=1}^{m} n_{i}}\right)\right\} \]   即把状态作为特征,动作作为标记。然后,对这个新构造出的数据集合\(D\)使用分类(对于离散动作)或回归(对于连续动作)算法即可学得策略模型。学得的这个策略模型可作为机器进行强化学习的初始策略,再通过强化学习方法基于环境反馈进行改进,从而获得更好的策略。

逆强化学习(inverse reinforcement learning)

  在很多任务中,设计奖赏函数往往相当困难,从人类专家提供的范例数据中反推出奖赏函数有助于解决该问题,这就是逆强化学习。在逆强化学习中,我们知道状态空间\(X\)、动作空间\(A\),并且与直接模仿学习类似,有一个决策轨迹数据集\(\left\{\tau_{1}, \tau_{2}, \ldots, \tau_{m}\right\}\)。逆强化学习的基本思想是:欲使机器做出与范例一致的行为,等价于在某个奖赏函数的环境中求解最优策略,该最优策略所产生的轨迹与范例数据一致换言之,我们要寻找某种奖赏函数使得范例数据是最优的,然后即可使用这个奖赏函数来训练强化学习策略。
  不妨假设奖赏函数能表达为状态特征的线性函数,即\(R(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}\)。于是,策略\(\pi\)的累积奖赏可写为状态向量加权和的期望与系数\(\boldsymbol{w}\)的内积: \[ \begin{aligned} \rho^{\pi}&=\mathbb{E}\left[\sum_{t=0}^{+\infty} \gamma^{t} R\left(\boldsymbol{x}_{t}\right) | \pi\right]=\mathbb{E}\left[\sum_{t=0}^{+\infty} \gamma^{t} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{t} | \pi\right] \\ &=\boldsymbol{w}^{\mathrm{T}} \mathbb{E}\left[\sum_{t=0}^{+\infty} \gamma^{t} \boldsymbol{x}_{t} | \pi\right] \end{aligned} \]   将状态向量的期望\(\mathbb{E}\left[\sum_{t=0}^{+\infty} \gamma^{t} \boldsymbol{x}_{t} | \pi\right]\)简写为\(\overline{\boldsymbol{x}}^{\pi}\)。注意到获得\(\overline{\boldsymbol{x}}^{\pi}\)需求取期望,我们可使用蒙特长罗方法通过采样来近似期望,而范例轨迹数据集恰可看作最优策略的一个采样,于是,可将每条范例轨迹上的状态加权求和再平均,记为\(\overline{\boldsymbol{x}}^{*}\),对于最优奖赏函数\(R(\boldsymbol{x})=\boldsymbol{w}^{* \mathrm{T}} \boldsymbol{x}\)和任意其他策略产生的\(\overline{\boldsymbol{x}}^{\pi}\),有: \[ \boldsymbol{w}^{* \mathrm{T}} \overline{\boldsymbol{x}}^{*}-\boldsymbol{w}^{* \mathrm{T}} \overline{\boldsymbol{x}}^{\pi}=\boldsymbol{w}^{* \mathrm{T}}\left(\overline{\boldsymbol{x}}^{*}-\overline{\boldsymbol{x}}^{\pi}\right) \geqslant 0 \]   若能对所有策略计算出\(\left(\overline{\boldsymbol{x}}^{*}-\overline{\boldsymbol{x}}^{\pi}\right)\),即可解出: \[ \begin{array}{c}{\boldsymbol{w}^{*}=\underset{\boldsymbol{w}}{\arg \max } \min _{\pi} \boldsymbol{w}^{\mathrm{T}}\left(\overline{\boldsymbol{x}}^{*}-\overline{\boldsymbol{x}}^{\pi}\right)} \\ {\text { s.t. }\|\boldsymbol{w}\| \leqslant 1}\end{array} \]   显然,我们难以获得所有策略,一个较好的办法是从随机策略开始,迭代地求解更好的奖赏函数,基于奖赏函数获得更好的策略,直至最终获得最符合范例轨迹数据集的奖赏函数和策略,下图是算法的伪代码。

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 强化学习(Reinforcement Learning)
  3. 3. \(K\)-摇臂赌博机
    1. 3.1. 探索-利用窘境(Exploration-Exploitation dilemma)
    2. 3.2. \(\epsilon\)-贪心(epsilon-Greedy)
    3. 3.3. Softmax
  4. 4. 有模型的学习(model-based learning)
    1. 4.1. 策略评估
    2. 4.2. 策略改进
    3. 4.3. 策略迭代(policy iteration)与值迭代(value iteration)
  5. 5. 免模型学习(model-free learning)
    1. 5.1. 蒙特卡罗强化学习(Monte Carlo Learning)
    2. 5.2. 时序差分学习(Temporal Difference Learning)
  6. 6. 值函数近似(value function approximation)
  7. 7. 模仿学习(Imitation Learning)
    1. 7.1. 直接模仿学习
    2. 7.2. 逆强化学习(inverse reinforcement learning)
  8. 8. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...