蒙特卡洛方法求解强化学习任务——蒙特卡洛评估基本介绍

目录

上一节介绍了使用蒙特卡洛方法对状态价值函数 V π ( s ) V_\pi(s) Vπ​(s)的近似求解过程。本节对蒙特卡洛评估(蒙特卡洛方法近似求解状态-动作价值函数 q π ( s , a ) q_\pi(s,a) qπ​(s,a))进行基本介绍。

蒙特卡洛方法求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)的优势和缺陷 求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)的优势

上一节介绍了近似求解状态价值函数 V π ( s ) V_\pi(s) Vπ​(s)的两种方法：首次访问型(first-visit)，每次访问型(every-visit)。我们发现：求解状态-动作价值函数 q π ( s , a ) q_\pi(s,a) qπ​(s,a)比求解 V π ( s ) V_\pi(s) Vπ​(s)更有实际价值。

• 根据 V π ( s ) V_\pi(s) Vπ​(s)和 q π ( s , a ) q_\pi(s,a) qπ​(s,a)之间的关联关系，在策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)给定的条件下，可以直接通过 q π ( s , a ) q_\pi(s,a) qπ​(s,a)表示 V π ( s ) V_\pi(s) Vπ​(s); V π ( s ) = ∑ a ∈ A ( s ) π ( a ∣ s ) q π ( s , a ) V_\pi(s) = \sum_{a \in \mathcal A(s)}\pi(a \mid s)q_\pi(s,a) Vπ​(s)=a∈A(s)∑​π(a∣s)qπ​(s,a) 相反，之所以不用下一状态的状态价值函数 V π ( s ′ ) V_\pi(s') Vπ​(s′)进行表示，原因在于动态特性函数 p ( s ′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)是未知/不完全可知；因此无法直接进行表达。 V π ( s ) = ∑ a ∈ A ( s ) π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ V π ( s ′ ) ] V_\pi(s) = \sum_{a \in \mathcal A(s)}\pi(a \mid s)\sum_{s',r}p(s',r \mid s,a)[r + \gamma V_\pi(s')] Vπ​(s)=a∈A(s)∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[r+γVπ​(s′)]
• 如果我们直接将 q π ( s , a ) q_\pi(s,a) qπ​(s,a)求出，各种状态、各种动作对应的价值结果被求出后，更方便进行策略改进。 q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] q ∗ ( s , a ) = max ⁡ a q π ( s , a ) = q π ( s , π ′ ( s ) ) π ′ ( s ) = arg ⁡ max ⁡ a q π ( s , a ) \begin{aligned} q_\pi(s,a) & = \mathbb E_{\pi}[G_t \mid S_t = s,A_t = a] \\ q_*(s,a) & = \mathop{\max}\limits_{a}q_\pi(s,a) = q_\pi(s,\pi'(s)) \\ \pi'(s) & = \mathop{\arg\max}\limits_{a} q_\pi(s,a) \end{aligned} qπ​(s,a)q∗​(s,a)π′(s)​=Eπ​[Gt​∣St​=s,At​=a]=amax​qπ​(s,a)=qπ​(s,π′(s))=aargmax​qπ​(s,a)​

求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)的缺陷

求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)过程中，不同于状态价值函数 V π ( s ) V_\pi(s) Vπ​(s),我们需要关心两个变量：状态 s s s和动作 a a a成对出现(笛卡尔积结果)。 对场景进行设计： 状态集合 S \mathcal S S和动作集合 A \mathcal A A定义如下： S = { s 1 , s 2 , . . . , s m } A = { a 1 , a 2 , . . . , a n } \begin{aligned} \mathcal S & = \{s_1,s_2,...,s_m\} \\ \mathcal A & = \{a_1,a_2,...,a_n\} \\ \end{aligned} SA​={s1​,s2​,...,sm​}={a1​,a2​,...,an​}​ 我们需要针对 ∀ s ∈ S , ∀ a ∈ A \forall s \in \mathcal S, \forall a \in \mathcal A ∀s∈S,∀a∈A，获取对应变量的状态-动作价值函数。状态-动作价值函数 q π ( s , a ) q_\pi(s,a) qπ​(s,a)表示如下： q π ( s , a ) = ( q π ( s 1 , a 1 ) q π ( s 1 , a 2 ) ⋯ q π ( s 1 , a n ) q π ( s 2 , a 1 ) q π ( s 2 , a 2 ) ⋯ q π ( s 2 , a n ) ⋮ ⋮ ⋱ ⋮ q π ( s m , a 1 ) q π ( s m , a 2 ) ⋯   q π ( s m , a n ) ) q_\pi(s,a)= \begin{pmatrix} q_\pi(s_1,a_1) & q_\pi(s_1,a_2) & \cdots & q_\pi(s_1,a_n) \\ q_\pi(s_2,a_1) & q_\pi(s_2,a_2) & \cdots & q_\pi(s_2,a_n) \\ \vdots & \vdots & \ddots & \vdots \\ q_\pi(s_m,a_1) & q_\pi(s_m,a_2) & \cdots\ & q_\pi(s_m,a_n) \\ \end{pmatrix} qπ​(s,a)=⎝⎜⎜⎜⎛​qπ​(s1​,a1​)qπ​(s2​,a1​)⋮qπ​(sm​,a1​)​qπ​(s1​,a2​)qπ​(s2​,a2​)⋮qπ​(sm​,a2​)​⋯⋯⋱⋯ ​qπ​(s1​,an​)qπ​(s2​,an​)⋮qπ​(sm​,an​)​⎠⎟⎟⎟⎞​ 我们需要通过蒙特卡洛方法将 q π ( s , a ) q_\pi(s,a) qπ​(s,a)中的所有元素全部求出来。 其中：

• N s i , a j ( i = 1 , 2 , . . . , m ; j = 1 , 2 , . . . , n ) N_{s_i,a_j}(i=1,2,...,m;j=1,2,...,n) Nsi​,aj​​(i=1,2,...,m;j=1,2,...,n)表示在执行情节过程中，状态、动作分别是 s i , a j s_i,a_j si​,aj​的条件下，产生回报(Return)样本的数量。
• G t ( s i , a j ) ( k ) ( i = 1 , 2 , . . . , m ; j = 1 , 2 , . . . , n ; k = 1 , 2 , . . . N s i , a j ) G_{t({s_i,a_j})}^{(k)}(i=1,2,...,m;j=1,2,...,n;k=1,2,...N_{s_i,a_j}) Gt(si​,aj​)(k)​(i=1,2,...,m;j=1,2,...,n;k=1,2,...Nsi​,aj​​)表示当状态、动作分别是 s i , a j s_i,a_j si​,aj​的条件下，某一个具体的回报样本。

q π ( s 1 , a 1 ) = E π [ G t ∣ S t = s 1 , A t = a 1 ] = 1 N s 1 , a 1 ∑ k = 1 N s 1 , a 1 G t ( s 1 , a 1 ) ( k ) q π ( s 1 , a 2 ) = E π [ G t ∣ S t = s 1 , A t = a 2 ] = 1 N s 1 , a 2 ∑ k = 1 N s 1 , a 2 G t ( s 1 , a 2 ) ( k ) ⋮ \begin{aligned} q_\pi(s_1,a_1) & = \mathbb E_{\pi}[G_t \mid S_t = s_1,A_t = a_1] = \frac{1}{N_{s_1,a_1}} \sum_{k=1}^{N_{s_1,a_1}} G_{t({s_1,a_1})}^{(k)} \\ q_\pi(s_1,a_2) & = \mathbb E_{\pi}[G_t \mid S_t = s_1,A_t = a_2] = \frac{1}{N_{s_1,a_2}} \sum_{k=1}^{N_{s_1,a_2}} G_{t({s_1,a_2})}^{(k)} \\ \vdots \end{aligned} qπ​(s1​,a1​)qπ​(s1​,a2​)⋮​=Eπ​[Gt​∣St​=s1​,At​=a1​]=Ns1​,a1​​1​k=1∑Ns1​,a1​​​Gt(s1​,a1​)(k)​=Eπ​[Gt​∣St​=s1​,At​=a2​]=Ns1​,a2​​1​k=1∑Ns1​,a2​​​Gt(s1​,a2​)(k)​​ 就能得到 q π ( s , a ) q_\pi(s,a) qπ​(s,a)基于蒙特卡洛方法的近似结果。 但是通过该方法近似求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)需要一个特定条件：求解 q π ( s i , a j ) ( i = 1 , 2 , . . . , m ; j = 1 , 2 , . . . , n ) q_\pi(s_i,a_j)(i = 1,2,...,m;j=1,2,...,n) qπ​(si​,aj​)(i=1,2,...,m;j=1,2,...,n)使用的样本需要保证在被采样的情节集合中都能够被访问到(有机会将样本采出来)。

这次对采样的条件进行了双重限制 → \to → (状态，动作)；这自然是比 V π ( s ) V_\pi(s) Vπ​(s)中只限制状态条件采样要困难得多。因此，需要的情节集合的规模要比近似求解 V π ( s ) V_\pi(s) Vπ​(s)需要的情节集合规模更大；

即便情节集合足够大，但是在采样过程中，仍然存在： 基于策略 π \pi π，满足状态、动作二元组均发生的条件下的回报样本 G t ( s i , a j ) ( k ) G_{t({s_i,a_j})}^{(k)} Gt(si​,aj​)(k)​难以产生的情况。 具体就是：在某一状态 s s s确定的条件下，策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)中某个动作 a ′ a' a′发生的概率极低/甚至为零——这种情况下，状态动作二元组 ( s i , a j ) (s_i,a_j) (si​,aj​)很难/无法被访问完整； 针对该问题，提出一个假设：试探性出发假设(探索始点)

试探性出发假设(探索始点)

试探性出发假设的具体描述为： 每一个状态、动作二元组 ( s , a ) (s,a) (s,a)均以非零的概率被选中作为某一情节的起始点。 在这种假设的条件下，任意一个状态、动作二元组都有机会被访问到——保证样本完备性。

从描述中可以感觉到，试探性出发假设是一种条件极强的假设。在真实环境中，这种假设是极难实现的：

• 这种难度不仅体现在采样上面(均以非零的概率被采样)
• 在真实环境中，上述被采样的状态、动作二元组 ( s , a ) (s,a) (s,a)出现在某个情节的起始点可能根本就无法实现。

因此，试探性出发假设只能存在于理论中——如果满足该假设，我们可以放心地使用蒙特卡洛方法通过采样的方式近似求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)。

总结

本节我们介绍了使用蒙特卡洛方法直接近似求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)相比求解 V π ( s ) V_\pi(s) Vπ​(s)的优势和缺陷。 具体有两种优势：

• 直接近似求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)可以更方便地执行策略改进；
• 在策略 π \pi π给定的条件下， V π ( s ) V_\pi(s) Vπ​(s)可以直接使用 q π ( s , a ) q_\pi(s,a) qπ​(s,a)进行表示；

具体缺陷也有两种：

• 近似求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)过程中，针对状态、动作二元组 ( s , a ) (s,a) (s,a)的采样需要的情节集合规模要大于近似求解 V π ( s ) V_\pi(s) Vπ​(s)过程中仅对状态 ( s ) (s) (s)采样的情节集合规模；
• 在真实环境中，状态、动作二元组 ( s , a ) (s,a) (s,a)可能存在极难/无法被访问的情况。

针对该问题，提出试探性出发假设——只要满足该假设，就可以使用蒙特卡洛方法近似求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)。 因此，在求解 q π ( s , a ) q_\pi(s,a) qπ​(s,a)需要克服两大问题：

• 极大的情节集合规模；
• 试探性出发假设；

后续我们将从简单的满足试探性出发假设的蒙特卡洛控制算法进行介绍，随后引出基于同轨策略和离轨策略的蒙特卡洛控制方法。

相关参考： 【强化学习】蒙特卡洛方法-策略评估 深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著