建设银行环县支行网站,话费充值代理平台,阳江网络问政平台新闻发布会,加快wordpress访问速度Markov决策过程#xff08;Markov Decision Process#xff0c;MDP#xff09;
Markov过程是一种用于描述决策问题的数学框架#xff0c;是强化学习的基础。MDP中#xff0c;决策者面对一系列的状态和动作#xff0c;每个状态下采取不同的动作会获得不同的奖励#xff…Markov决策过程Markov Decision ProcessMDP
Markov过程是一种用于描述决策问题的数学框架是强化学习的基础。MDP中决策者面对一系列的状态和动作每个状态下采取不同的动作会获得不同的奖励决策者的目标是制定一种策略使得长期累积的奖励最大化。
MDP具有以下特点
状态具有马尔可夫性质即当前状态包含了过去所有状态的信息未来状态只与当前状态相关与过去状态无关决策者在每个状态下采取的动作会影响下一时刻的状态转移在每个状态下采取的动作会获得一个即时奖励目标是最大化长期累积奖励。
MDP可以用五元组 ( S , A , p , r , γ ) (\mathcal{S}, \mathcal{A}, p, r, \gamma) (S,A,p,r,γ) 来表示其中 S \mathcal{S} S 是状态集合 A \mathcal{A} A 是动作集合 p ( s ′ ∣ s , a ) p(s|s,a) p(s′∣s,a) 表示在状态 s s s 采取动作 a a a 后转移到状态 s ′ s s′ 的概率 r ( s , a ) r(s,a) r(s,a) 表示在状态 s s s 采取动作 a a a 后获得的即时奖励 γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ∈[0,1] 是折扣因子用于平衡当前奖励和未来奖励的重要性。
定义在时间 t \mathrm{t} t, 从状态 s t s \mathrm{s}_{\mathrm{t}}\mathrm{s} sts 和动作 A t a \mathrm{A}_{\mathrm{t}}\mathrm{a} Ata 跳转到下一状态 S t 1 s ′ S_{t1}s^{\prime} St1s′ 和奖励 R t 1 r R_{t1}r Rt1r 的概率为: Pr [ S t 1 s ′ , R t 1 r ∣ S t s , A t a ] \operatorname{Pr}\left[S_{t1}s^{\prime}, R_{t1}r \mid S_ts, A_ta\right] Pr[St1s′,Rt1r∣Sts,Ata]
在MDP中决策者需要制定一种策略 π : S → A \pi: \mathcal{S} \rightarrow \mathcal{A} π:S→A将每个状态映射到相应的动作。根据策略可以计算出每个状态的状态值函数 V π ( s ) V^\pi(s) Vπ(s) 和动作值函数 Q π ( s , a ) Q^\pi(s,a) Qπ(s,a)用于评估策略的好坏。同时还可以使用值迭代、策略迭代等算法来寻找最优策略使得长期累积奖励最大化。
对于有限 Markov决策过程, 可以定义函数 p : S × R × S × A → [ 0 , 1 ] p: \mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} \rightarrow[0,1] p:S×R×S×A→[0,1] 为 Markov决策过程的动力 (dynamics): p ( s ′ , r ∣ s , a ) Pr [ S t 1 s ′ , R t 1 r ∣ S t s , A t a ] \mathrm{p}\left(\mathrm{s}^{\prime}, \mathrm{r} \mid \mathrm{s}, \mathrm{a}\right)\operatorname{Pr}\left[\mathrm{S}_{\mathrm{t}1}\mathrm{s}^{\prime} \quad, \mathrm{R}_{\mathrm{t}1}\mathrm{r} \mid \mathrm{S}_{\mathrm{t}}\mathrm{s}, \mathrm{A}_{\mathrm{t}}\mathrm{a}\right] p(s′,r∣s,a)Pr[St1s′,Rt1r∣Sts,Ata] p函数中间的坚线 “ ∣ \mid ∣ ”取材于条件概率中间的坚线。
利用动力的定义, 可以得到以下其他导出量。 状态转移概率1.1: p ( s ′ ∣ s , a ) Pr [ S t 1 s ′ ∣ S , s , A a ] ∑ r ∈ R p ( s ′ , r ∣ s , a ) , s ∈ S , a ∈ A , s ′ ∈ S p\left(s^{\prime} \mid s, a\right)\operatorname{Pr}\left[S_{t1}s^{\prime} \mid S,s, Aa\right]\sum_{r \in \mathbb{R}} p\left(s^{\prime}, r \mid s, a\right), \quad s \in \mathcal{S}, a \in \mathcal{A}, s^{\prime} \in \mathcal{S} p(s′∣s,a)Pr[St1s′∣S,s,Aa]r∈R∑p(s′,r∣s,a),s∈S,a∈A,s′∈S 给定 “状态 - 动作” 的期望奖励1.2 r ( s , a ) E [ R t 1 ∣ S t s , A t a ] ∑ r ∈ R r ∑ s ′ ∈ S p ( s ′ , r ∣ s , a ) , s ∈ S , a ∈ A r(s, a)\mathrm{E}\left[R_{t1} \mid S_{t}s, A_{t}a\right]\sum_{r \in \mathbb{R}} r \sum_{s^{\prime} \in S} p\left(s^{\prime}, r \mid s, a\right), \quad s \in \mathcal{S}, a \in \mathcal{A} r(s,a)E[Rt1∣Sts,Ata]r∈R∑rs′∈S∑p(s′,r∣s,a),s∈S,a∈A 给定 “状态 - 动作 -下一状态” 的期望奖励1.3: r ( s , a , s ′ ) E [ R t 1 ∣ S t s , A t a , S t 1 s ′ ] ∑ r ∈ R r p ( s ′ , r ∣ s , a ) p ( s ′ ∣ s , a ) , s ∈ S , a ∈ A , s ′ ∈ S r\left(s, a, s^{\prime}\right)\mathrm{E}\left[R_{t1} \mid S_{t}s, A_{t}a, S_{t1}s^{\prime}\right] \sum_{r \in \mathbb{R} } r \frac{p\left(s^{\prime}, r \mid s, a\right)}{p\left(s^{\prime} \mid s, a\right)}, \quad s \in \mathcal{S}, a \in \mathcal{A}, s^{\prime} \in \mathcal{S} r(s,a,s′)E[Rt1∣Sts,Ata,St1s′]r∈R∑rp(s′∣s,a)p(s′,r∣s,a),s∈S,a∈A,s′∈S 公式(1.3)推导过程 我们可以使用条件概率的公式来推导 r ( s , a , s ′ ) r(s,a,s) r(s,a,s′) 的公式。根据条件概率的定义有 E [ R t 1 ∣ S t s , A t a , S t 1 s ′ ] ∑ r r ⋅ Pr ( R t 1 r ∣ S t s , A t a , S t 1 s ′ ) \mathrm{E}\left[R_{t1} \mid S_{t}s, A_{t}a, S_{t1}s^{\prime}\right]\sum_{r} r \cdot \operatorname{Pr}\left(R_{t1}r \mid S_{t}s, A_{t}a, S_{t1}s^{\prime}\right) E[Rt1∣Sts,Ata,St1s′]r∑r⋅Pr(Rt1r∣Sts,Ata,St1s′) 利用条件概率公式的两种形式 P ( A B ) P ( A ∣ B ) ⋅ P ( B ) P(A B)P(A \mid B) \cdot P(B) P(AB)P(A∣B)⋅P(B) P ( A ∣ B ) ⋅ P ( B ) P ( A B ) P(A \mid B) \cdot P(B)P(A B) P(A∣B)⋅P(B)P(AB) 对下面的概率公式进行转化 Pr ( R t 1 r ∣ S t S , A t a , S t 1 s ′ ) Pr ( R t 1 r , S t s , A t a , S t 1 s ′ ) Pr ( S t s , A t a , S t 1 s ′ ) Pr ( R t 1 r , S t 1 s ′ ∣ S t s , A t a ) ⋅ Pr ( S t s , A t a ) Pr ( S t 1 s ′ ∣ S t s , A t a ) ⋅ Pr ( S t s , A t a ) Pr ( R t 1 r , S t 1 s ′ ∣ S t s , A t a ) Pr ( S t 1 s ′ ∣ S t s , A t a ) \begin{aligned} \operatorname{Pr}\left(R_{t1}r \mid S_tS, A_ta, S_{t1}s^{\prime}\right)\\ \frac{\operatorname{Pr}\left(R_{t1}r, S_ts, A_ta, S_{t1}s^{\prime}\right)}{\operatorname{Pr}\left(S_ts, A_ta, S_{t1}s^{\prime}\right)} \\ \frac{\operatorname{Pr}\left(\operatorname{R_{t1}} r, S_{t1}s^{\prime} \mid S_ts, A_ta\right) \cdot \operatorname{Pr}\left(S_ts, A_ta\right)}{\operatorname{Pr}\left(S_{t1}s^{\prime} \mid S_ts, A_ta\right) \cdot \operatorname{Pr}\left(S_ts, A_ta\right)} \\ \frac{\operatorname{Pr}\left(\operatorname{R}_{t1}r, S_{t1}s^{\prime} \mid S_ts, A_ta\right)}{\operatorname{Pr}\left(S_{t1}s^{\prime} \mid S_ts, A_ta\right)} \end{aligned} Pr(Rt1r∣StS,Ata,St1s′)Pr(Sts,Ata,St1s′)Pr(Rt1r,Sts,Ata,St1s′)Pr(St1s′∣Sts,Ata)⋅Pr(Sts,Ata)Pr(Rt1r,St1s′∣Sts,Ata)⋅Pr(Sts,Ata)Pr(St1s′∣Sts,Ata)Pr(Rt1r,St1s′∣Sts,Ata) 而根据贝叶斯公式我们可以将上式中的条件概率转换为联合概率和边缘概率的形式即 Pr ( R t 1 r ∣ S t s , A t a , S t 1 s ′ ) Pr ( S t 1 s ′ , R t 1 r ∣ S t s , A t a ) Pr ( S t 1 s ′ ∣ S t s , A t a ) \operatorname{Pr}\left(R_{t1}r \mid S_{t}s, A_{t}a, S_{t1}s^{\prime}\right)\frac{\operatorname{Pr}\left(S_{t1}s^{\prime}, R_{t1}r \mid S_{t}s, A_{t}a\right)}{\operatorname{Pr}\left(S_{t1}s^{\prime} \mid S_{t}s, A_{t}a\right)} Pr(Rt1r∣Sts,Ata,St1s′)Pr(St1s′∣Sts,Ata)Pr(St1s′,Rt1r∣Sts,Ata) 将上式代入前面的式子中得到 E [ R t 1 ∣ S t s , A t a , S t 1 s ′ ] ∑ r r ⋅ Pr ( S t 1 s ′ , R t 1 r ∣ S t s , A t a ) Pr ( S t 1 s ′ ∣ S t s , A t a ) \mathrm{E}\left[R_{t1} \mid S_{t}s, A_{t}a, S_{t1}s^{\prime}\right]\sum_{r} r \cdot \frac{\operatorname{Pr}\left(S_{t1}s^{\prime}, R_{t1}r \mid S_{t}s, A_{t}a\right)}{\operatorname{Pr}\left(S_{t1}s^{\prime} \mid S_{t}s, A_{t}a\right)} E[Rt1∣Sts,Ata,St1s′]r∑r⋅Pr(St1s′∣Sts,Ata)Pr(St1s′,Rt1r∣Sts,Ata) 根据MDP中的状态转移概率 p ( s ′ , r ∣ s , a ) p(s,r|s,a) p(s′,r∣s,a) 和状态转移概率的定义我们可以将上式中的条件概率表示为 p ( s ′ , r ∣ s , a ) p(s,r|s,a) p(s′,r∣s,a) 的形式即 Pr ( S t 1 s ′ , R t 1 r ∣ S t s , A t a ) p ( s ′ , r ∣ s , a ) \operatorname{Pr}\left(S_{t1}s^{\prime}, R_{t1}r \mid S_{t}s, A_{t}a\right)p\left(s^{\prime}, r \mid s, a\right) Pr(St1s′,Rt1r∣Sts,Ata)p(s′,r∣s,a) 同样地根据MDP中的状态转移概率 p ( s ′ ∣ s , a ) p(s|s,a) p(s′∣s,a) 和状态转移概率的定义我们可以将上式中的边缘概率表示为 p ( s ′ ∣ s , a ) p(s|s,a) p(s′∣s,a) 的形式即 Pr ( S t 1 s ′ ∣ S t s , A t a ) p ( s ′ ∣ s , a ) \operatorname{Pr}\left(S_{t1}s^{\prime} \mid S_{t}s, A_{t}a\right)p\left(s^{\prime} \mid s, a\right) Pr(St1s′∣Sts,Ata)p(s′∣s,a) 将上面两个式子代入前面的式子中得到 E [ R t 1 ∣ S t s , A t a , S t 1 s ′ ] ∑ r r ⋅ p ( s ′ , r ∣ s , a ) p ( s ′ ∣ s , a ) , s ∈ S , a ∈ A , s ′ ∈ S \mathrm{E}\left[R_{t1} \mid S_{t}s, A_{t}a, S_{t1}s^{\prime}\right]\sum_{r} r \cdot \frac{p\left(s^{\prime}, r \mid s, a\right)}{p\left(s^{\prime} \mid s, a\right)}, \quad s \in \mathcal{S}, a \in \mathcal{A}, s^{\prime} \in \mathcal{S} E[Rt1∣Sts,Ata,St1s′]r∑r⋅p(s′∣s,a)p(s′,r∣s,a),s∈S,a∈A,s′∈S 这就是 r ( s , a , s ′ ) r(s,a,s) r(s,a,s′) 的公式推导过程。 回报
假设某一回合在第 T T T 步终止则从 t ( t T ) t(tT) t(tT) 以后的回报 G t G_t Gt 定义为未来奖励和 G t R t 1 R t 2 ⋯ R T G_t R_{t1} R_{t2} \cdots R_T GtRt1Rt2⋯RT
引入折扣因子 γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ∈[0,1]则回报 G t G_t Gt 可以表示为 G t R t 1 γ R t 2 γ 2 R t 3 ⋯ ∑ τ 0 ∞ γ τ R t τ 1 G_t R_{t1} \gamma R_{t2} \gamma^2 R_{t3} \cdots \sum_{\tau 0}^{\infty} \gamma^\tau R_{t\tau1} GtRt1γRt2γ2Rt3⋯τ0∑∞γτRtτ1
其中 R t R_t Rt 表示第 t t t 步的奖励 γ \gamma γ 表示折扣因子 t t t 表示当前步数。
策略
定义策略(policy为从状态到动作的转移概率 π ( a ∣ s ) P r [ A t a ∣ S t s ] , s ∈ S , a ∈ A \pi(a\mid s)Pr[A_ta \mid S_ts],s \in S,a \in A π(a∣s)Pr[Ata∣Sts],s∈S,a∈A
价值函数
基于回报的定义可以进一步定义价值函数 (value function)。对于给定的策略 π \pi π, 可以定义以下价值函数。
状态价值函数 (state value function): 状态价值函数 v π ( s ) \mathrm{v}_\pi(\mathrm{s}) vπ(s) 表示从状态的开始采用策略 π \pi π 的预期回报。如下式所示: v π ( s ) E π [ G t ∣ S t s ] \mathrm{v}_{\mathrm{\pi}}(\mathrm{s})\mathrm{E}_{\mathrm{\pi}}\left[\mathrm{G}_{\mathrm{t}} \mid \mathrm{S}_{\mathrm{t}}\mathrm{s}\right] vπ(s)Eπ[Gt∣Sts]动作价值函数 (action value function)动作价值函数 q π ( s , a ) \mathrm{q}_{\pi}(\mathrm{~s}, \mathrm{a}) qπ( s,a) 表示在状态 s \mathrm{s} s 采取动作 a \mathrm{a} a 后采用策略 π \pi π 的预期回报。如下式所示: q π ( s , a ) E π [ G t ∣ S t s , A t a ] \mathrm{q}_\pi(\mathrm{s}, \mathrm{a})\mathrm{E}_\pi\left[\mathrm{G}_{\mathrm{t}} \mid \mathrm{S}_{\mathrm{t}}\mathrm{s}, \mathrm{A}_{\mathrm{t}}\mathrm{a}\right] qπ(s,a)Eπ[Gt∣Sts,Ata] 终止状态 s 终止 {s}_{终止} s终止不是一个一般的状态终止状态后没有动作。为了在数学上有统一的形式, 一般定义 v π ( s 终止 ) 0 , q π ( s 终止 , a ) 0 ( a ∈ A ) \mathrm{v}_\pi\left(\mathrm{s}_{\text {终止 }}\right)0, \mathrm{q}_\pi\left(\mathrm{s}_{\text {终止 }}, \mathrm{a}\right)0 \quad(a \in \mathcal{A}) vπ(s终止 )0,qπ(s终止 ,a)0(a∈A) 。
动作价值函数和状态价值函数的互相表示以及贝尔曼期望方程
用 t \mathrm{t} t 时刻的动作价值函数表示 t \mathrm{t} t 时刻的状态价值函数: v π ( s ) ∑ a π ( a ∣ s ) q π ( s , a ) , s ∈ S v_\pi(s)\sum_a \pi(a \mid s) q_{\pi} (s, a), \quad s \in S vπ(s)a∑π(a∣s)qπ(s,a),s∈S 推导对任一状态 s ∈ S s \in \mathcal{S} s∈S, 有 v π ( s ) E π [ G t ∣ S t s ] ∑ g g Pr [ G t g ∣ S t s ] ∑ g g ∑ a Pr [ G t g , A t a ∣ S t s ] 对概率部分利用条件概率公式变形拆成两个概率乘积 ∑ g g ∑ a Pr [ G t g , A t a , S t s ] Pr [ S t s ] ∑ g g ∑ a Pr [ G t g ∣ A t a , S t s ] ⋅ Pr [ A t a , S t s ] Pr [ S t s ] ∑ g g ∑ a Pr [ A t a ∣ S t s ] Pr [ G t g ∣ S t s , A t a ] ∑ a Pr [ A t a ∣ S t s ] ∑ g g Pr [ G t g ∣ S t s , A t a ] ∑ a Pr [ A t a ∣ S t s ] E π [ G t ∣ S t s , A t a ] ∑ a π ( a ∣ s ) q π ( s , a ) \begin{aligned} v_\pi(s)\mathrm{E}_\pi \left[G_t \mid S_{t}s\right] \\ \sum_g g \operatorname{Pr}\left[G_tg \mid S_ts\right] \\ \sum_g g \sum_a \operatorname{Pr}\left[G_tg, A_ta \mid S_ts\right] \\ 对概率部分利用条件概率公式变形拆成两个概率乘积\\ \sum_g g \sum_a \frac{\operatorname{Pr}\left[G_tg, A_ta, S_ts\right]}{\operatorname{Pr}\left[S_ts\right]} \\ \sum_g g \sum_a \frac{\operatorname{Pr}\left[G_tg \mid A_ta, S_ts\right] \cdot \operatorname{Pr}\left[A_ta, S_ts\right]}{\operatorname{Pr}\left[S_ts\right]} \\ \\ \sum_g g \sum_a \operatorname{Pr}\left[A_ta \mid S_ts\right] \operatorname{Pr}\left[G_tg \mid S_ts, A_ta\right] \\ \sum_a \operatorname{Pr}\left[A_ta \mid S_ts\right] \sum_g g \operatorname{Pr}\left[G_tg \mid S_ts, A_ta\right] \\ \sum_a \operatorname{Pr}\left[A_ta \mid S_ts \right] \mathrm{E}_\pi \left[G_t \mid S_ts, A_ta\right] \\ \sum_a \pi(a \mid s) q_\pi (s, a) \\ \end{aligned} vπ(s)Eπ[Gt∣Sts]g∑gPr[Gtg∣Sts]g∑ga∑Pr[Gtg,Ata∣Sts]对概率部分利用条件概率公式变形拆成两个概率乘积g∑ga∑Pr[Sts]Pr[Gtg,Ata,Sts]g∑ga∑Pr[Sts]Pr[Gtg∣Ata,Sts]⋅Pr[Ata,Sts]g∑ga∑Pr[Ata∣Sts]Pr[Gtg∣Sts,Ata]a∑Pr[Ata∣Sts]g∑gPr[Gtg∣Sts,Ata]a∑Pr[Ata∣Sts]Eπ[Gt∣Sts,Ata]a∑π(a∣s)qπ(s,a)用 t 1 t1 t1时刻的状态价值表示 t t t时刻的动作价值函数: q π ( s , a ) r ( s , a ) γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r γ v π ( s ′ ) ] , s ∈ S , a ∈ A \begin{aligned} q_\pi(s, a) r(s, a)\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \\ \sum_{s^{\prime},r} p\left(s^{\prime}, r \mid s, a\right)\left[r\gamma v_\pi \left(s^{\prime}\right)\right], \quad s \in \mathcal{S}, a \in \mathcal{A} \end{aligned} qπ(s,a)r(s,a)γs′∑p(s′∣s,a)vπ(s′)s′,r∑p(s′,r∣s,a)[rγvπ(s′)],s∈S,a∈A 推导对任意的状态 s ∈ S s \in \mathcal{S} s∈S 和动作 a ∈ A a \in \mathcal{A} a∈A, 有 E π [ G t 1 ∣ S t s , A t a ] ∑ g g Pr [ G t 1 g ∣ S t S , A t a ] ∑ g g ∑ s ′ Pr [ S t 1 s ′ , G t 1 g ∣ S t s , A t a ] ∑ g g ∑ s ′ Pr [ S t 1 s ′ , G t 1 g , S t s , A t a ] ‾ Pr [ S t S , A t a ] ‾ 注意观察划线区域在下面的位置变化 ∑ g g ∑ s ′ Pr [ S t 1 s ′ , G t 1 g , S t s , A t a ] ‾ Pr [ S t s , A t a , S t 1 s ′ ] ⋅ Pr [ S t s , A t a , S t 1 s ′ ] Pr [ S t S , A t a ] ‾ ∑ g g ∑ s ′ Pr [ S t 1 s ′ ∣ S t s , A t a ] Pr [ G t 1 g ∣ S t s , A t a , S t 1 s ′ ] 利用 M a r k o v 性对后面部分进行精简 ∑ g g ∑ s ′ Pr [ S t 1 s ′ ∣ S t s , A t a ] Pr [ G t 1 g ∣ S t 1 s ′ ] ∑ s ′ Pr [ S t 1 s ′ ∣ S t s , A t a ] ∑ g g Pr [ G t 1 g ∣ S t 1 s ′ ] ∑ s ′ Pr [ S t 1 s ′ ∣ S t s , A t a ] E π [ G t 1 ∣ S t 1 s ′ ] ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) \begin{aligned} \mathrm{E}_\pi \left[G_{t1} \mid S_ts, A_ta\right] \\ \sum_g g \operatorname{Pr}\left[G_{t1}g \mid S_tS, A_ta\right] \\ \sum_g g \sum_{s^{\prime}} \operatorname{Pr}\left[S_{t1}s^{\prime}, G_{t1}g \mid S_ts, A_ta\right] \\ \sum_g g \sum_{s^{\prime}} \frac{\operatorname{Pr} \underline{\left[S_{t1}s^{\prime}, G_{t1}g, S_ts, A_ta\right]}}{\operatorname{Pr} \underline{\left[S_tS, A_ta\right] }} \\ 注意观察划线区域在下面的位置变化 \\ \sum_g g \sum_{s^{\prime}} \frac{\operatorname{Pr} \underline{\left[S_{t1}s^{\prime}, G_{t1}g, S_ts, A_ta\right]}}{\operatorname{Pr}\left[S_ts, A_ta, S_{t1}s^{\prime}\right]} \cdot \frac{ \operatorname{Pr}\left[S_ts, A_ta, S_{t1}s^{\prime}\right] }{\operatorname{Pr} \underline{\left[S_tS, A_ta\right] }} \\ \sum_g g \sum_{s^{\prime}} \operatorname{Pr}\left[S_{t1}s^{\prime} \mid S_ts, A_ta\right] \operatorname{Pr}\left[G_{t1}g \mid S_ts, A_ta, S_{t1}s^{\prime}\right] \\ 利用Markov性对后面部分进行精简 \\ \sum_g g \sum_{s^{\prime}} \operatorname{Pr}\left[S_{t1}s^{\prime} \mid S_ts, A_ta\right] \operatorname{Pr}\left[G_{t1}g \mid S_{t1}s^{\prime}\right] \\ \sum_{s^{\prime}} \operatorname{Pr}\left[S_{t1}s^{\prime} \mid S_ts, A_ta\right] \sum_{g} g \operatorname{Pr}\left[G_{t1}g \mid S_{t1}s^{\prime}\right] \\ \sum_{s^{\prime}} \operatorname{Pr}\left[S_{t1}s^{\prime} \mid S_ts, A_ta\right] \mathrm{E}_\pi\left[G_{t1} \mid S_{t1}s^{\prime}\right] \\ \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \\ \end{aligned} Eπ[Gt1∣Sts,Ata]g∑gPr[Gt1g∣StS,Ata]g∑gs′∑Pr[St1s′,Gt1g∣Sts,Ata]g∑gs′∑Pr[StS,Ata]Pr[St1s′,Gt1g,Sts,Ata]注意观察划线区域在下面的位置变化g∑gs′∑Pr[Sts,Ata,St1s′]Pr[St1s′,Gt1g,Sts,Ata]⋅Pr[StS,Ata]Pr[Sts,Ata,St1s′]g∑gs′∑Pr[St1s′∣Sts,Ata]Pr[Gt1g∣Sts,Ata,St1s′]利用Markov性对后面部分进行精简g∑gs′∑Pr[St1s′∣Sts,Ata]Pr[Gt1g∣St1s′]s′∑Pr[St1s′∣Sts,Ata]g∑gPr[Gt1g∣St1s′]s′∑Pr[St1s′∣Sts,Ata]Eπ[Gt1∣St1s′]s′∑p(s′∣s,a)vπ(s′)
其中 Pr [ G t 1 g ∣ S t s , A t a , S t 1 s ′ ] P r [ G t 1 g ∣ S t 1 s ′ ] \operatorname{Pr}\left[G_{t1}g \mid S_ts, A_ta, S_{t1}s^{\prime} \quad\right]Pr\left[G_{t1}g \mid S_{t1}s^{\prime}\right] Pr[Gt1g∣Sts,Ata,St1s′]Pr[Gt1g∣St1s′] 用到了Markov性。
回忆前面我们定义的 G t R t 1 γ R t 2 γ 2 R t 3 ⋯ ∑ τ 0 ∞ γ τ R t τ 1 G_t R_{t1} \gamma R_{t2} \gamma^2 R_{t3} \cdots \sum_{\tau 0}^{\infty} \gamma^\tau R_{t\tau1} GtRt1γRt2γ2Rt3⋯τ0∑∞γτRtτ1 观察各项可以发现 G t 1 R t 2 γ R t 3 γ 2 R t 4 ⋯ G t − R t 1 γ G_{t1} R_{t2} \gamma R_{t3} \gamma^2 R_{t4} \cdots \frac{G_t-R_{t1}}{\gamma} Gt1Rt2γRt3γ2Rt4⋯γGt−Rt1 也就是说 G t 1 和 G t G_{t1} 和 G_{t} Gt1和Gt存在递推关系 G t R t 1 γ G t 1 G_t R_{t1}\gamma G_{t1} GtRt1γGt1
回顾1.2公式
给定 “状态 - 动作” 的期望奖励1.2 r ( s , a ) E [ R t 1 ∣ S t s , A t a ] ∑ r ∈ R r ∑ s ′ ∈ S p ( s ′ , r ∣ s , a ) , s ∈ S , a ∈ A r(s, a)\mathrm{E}\left[R_{t1} \mid S_{t}s, A_{t}a\right]\sum_{r \in \mathbb{R}} r \sum_{s^{\prime} \in S} p\left(s^{\prime}, r \mid s, a\right), \quad s \in \mathcal{S}, a \in \mathcal{A} r(s,a)E[Rt1∣Sts,Ata]r∈R∑rs′∈S∑p(s′,r∣s,a),s∈S,a∈A 结合刚刚推导出的 E π [ G t 1 ∣ S t s , A t a ] \mathrm{E}_\pi \left[G_{t1} \mid S_ts, A_ta\right] Eπ[Gt1∣Sts,Ata]的表达式 利用上式最终有 q π ( s , a ) E π [ G t ∣ S t s , A t a ] E π [ R t 1 γ G t 1 ∣ S t s , A t a ] E π [ R t 1 ∣ S t s , A t a ] E π [ γ G t 1 ∣ S t s , A t a ] E π [ R t 1 ∣ S t s , A t a ] γ E π [ G t 1 ∣ S t s , A t a ] ∑ r ∈ R r ∑ s ′ ∈ S p ( s ′ , r ∣ s , a ) γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r γ v π ( s ′ ) ] \begin{aligned} q_\pi(s, a) \mathrm{E}_\pi\left[G_t \mid S_ts, A_ta\right] \\ \mathrm{E}_\pi\left[R_{t1}\gamma G_{t1} \mid S_ts, A_ta\right] \\ \mathrm{E}_\pi\left[R_{t1} \mid S_ts, A_ta\right]\mathrm{E}_\pi\left[\gamma G_{t1} \mid S_ts, A_ta\right] \\ \mathrm{E}_\pi\left[R_{t1} \mid S_ts, A_ta\right]\gamma \mathrm{E}_\pi\left[G_{t1} \mid S_ts, A_ta\right] \\ \sum_{r \in \mathbb{R}} r \sum_{s^{\prime} \in S} p\left(s^{\prime}, r \mid s, a\right) \gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \\ \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r\gamma v_\pi \left(s^{\prime}\right)\right] \end{aligned} qπ(s,a)Eπ[Gt∣Sts,Ata]Eπ[Rt1γGt1∣Sts,Ata]Eπ[Rt1∣Sts,Ata]Eπ[γGt1∣Sts,Ata]Eπ[Rt1∣Sts,Ata]γEπ[Gt1∣Sts,Ata]r∈R∑rs′∈S∑p(s′,r∣s,a)γs′∑p(s′∣s,a)vπ(s′)s′,r∑p(s′,r∣s,a)[rγvπ(s′)] 这样就得到了结果
不同时刻价值函数表示
用下一时刻的状态价值函数表示当前时刻的状态价值函数 ν π ∑ a π ( s ∣ a ) ⋅ q π ( s , a ) , s ∈ S ν π ∑ a π ( s ∣ a ) [ r ( s , a ) γ ∑ s ′ p ( s ′ ∣ s , a ) ν π ( s ′ ) ] , s ∈ S \begin{aligned} \nu_\pi \sum_a \pi(s \mid a) \cdot q_\pi(s, a) , s \in S \\ \nu_\pi \sum_a \pi(s \mid a)\left[r(s, a)\gamma \sum_{s^\prime} p\left(s^{\prime} \mid s, a\right) \nu_\pi\left(s^{\prime}\right)\right] , s \in S \end{aligned} νπνπa∑π(s∣a)⋅qπ(s,a),s∈Sa∑π(s∣a)[r(s,a)γs′∑p(s′∣s,a)νπ(s′)],s∈S用下一时刻动作价值函数表示当前动作价值函数 q π ( s , a ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r γ v π ( s ′ ) ] , s ∈ S , a ∈ A q π ( s , a ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r γ ∑ a ′ π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) ] , s ∈ S , a ∈ A \mathcal{q}_{\pi} (s, a)\sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r\gamma v_\pi \left(s^{\prime}\right)\right] , \quad s \in \mathcal{S}, a \in \mathcal{A} \\ \mathcal{q}_{\pi} (s, a)\sum_{s^\prime,r} p\left(s^{\prime}, r \mid s, a\right)\left[r\gamma \sum_{a^{\prime}} \pi\left(a^{\prime} \mid s^{\prime}\right) q_\pi\left(s^{\prime}, a^{\prime}\right)\right], \quad s \in \mathcal{S}, a \in \mathcal{A} qπ(s,a)s′,r∑p(s′,r∣s,a)[rγvπ(s′)],s∈S,a∈Aqπ(s,a)s′,r∑p(s′,r∣s,a)[rγa′∑π(a′∣s′)qπ(s′,a′)],s∈S,a∈A
