[人工智能]强化学习二-举例理解概念

MDP(离散型)概念理解(二)

一、说明基础概念

假设一个节点得状态空间为 S = { 0 , 1 , 2 , 3 , . . . , 13 } S=\{0,1,2,3,...,13\} S={0,1,2,3,...,13}，动作空间为 A = { ? 2 , ? 1 , 0 , 1 , 2 } A=\{-2,-1,0,1,2\} A={?2,?1,0,1,2},其中初始得一个策略为
$$\pi (a|s)=?\begin{array}{ll}0.8,& s<=5,?I_{max}\le a<0\\ 0.2& s<=5,a=0\\ 0.8& 5<s<Z_v?5,a=0\\ 0.1& 5<s<Z_v?5,a<0\\ 0.1& 5<s<Z_v?5,a>0\\ 0.8& Z_v?5\le s<Z_v,0<a\le I_{max}\\ 0.2& Z_v?5\le s<Z_v,a=0\end{array}$$?

注意到，这里得假设$Z_v=13,I_{max}=2$ ,具体的用示意图1表示为：

1.1 状态转移概率

• 公式： $P_{s{s}^{\prime }}^a=E(S_{t+1}|S_t=s,A_t=a)$,在当前状态s,动作a下的转移到状态s’的概率期望
• 举例：$P_{4,8}^0=P(S_{t+1}=8|S_t=5,a_t=0)=0.05$,在当前状态为4，动作为0,转移到状态为8的概率
  $P_{4,8}=0.2_{(a=0)}\times 0.05+0.4_{(a=?1)}\times 0.1+0.4_{(a=?2)}\times 0.1+0_{(a=1)}+0_{(a=2)}=0.09$。在当前状态为4，不知道动作，转移到状态为8,的概率期望

1.2 报酬

• 即时报酬：$R_{s{s}^{\prime }}^a$：在当前状态s下，执行动作a后，转移到状态s’后，得到的报酬。假设我们报酬为完成的自行车行程数量。在单个节点中，我们利用“出量+进量之和”作为该动作的报酬。如上：$R_{48}^0=6(走了1辆车，来了5辆车)$

• 动作报酬期望：$R_s^a={\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{R}_{s{s}^{\prime }}^a$.举例则$$\begin{array}{rl}& R_{s=4}^{a=0}\\ & =0.05_{s^{\prime }=1}?3+0.1_{s^{\prime }=2}?2+0.2_{s^{\prime }=3}?3+0.1_{s^{\prime }=5}?3+0.1_{s^{\prime }=6}?4+0.05_{s^{\prime }=7}?3+0.05_{s^{\prime }=8}?6+0.05_{s^{\prime }=9}?5\\ & =0.15+0.2+0.6+0.3+0.4+0.15+0.3+0.45\\ & =2.55\end{array}$$

  $$\begin{array}{rl}& R_{s=4}^{a=1}\\ & =0.05?1+0.1?4+0.1?3+0.1?4+0.1?5+0.1?6+0.1?7+0.1?8+0.05?9=4.2\end{array}$$

  $$R_{s=4}^{a=2}=R_{s=4}^{a=?1}=R_{s=4}^{a=?2}=4.2$$

• 策略报酬期望：$R_s^{\pi }={\sum }_{a\in A}\pi (a|s)R_s^a$

  $$\begin{array}{rl}{R}_{s=4}^{\pi }& =\pi (a=?1|4)?R_4^{?1}+\pi (a=?2|4)R_4^{?2}+\pi (0|4)?R_4^0+\pi (1|4)?R_4^1+\pi (2|4)R_4^2\\ & =0.4_{(a=?1)}?4.2+0.4_{(a=?2)}?4.2+0.2_{(a=0)}?2.55+0+0=3.87\end{array}$$

1.3 两个价值函数

1.3.1 状态价值函数(或累积回报函数)

是对当前状态的s=4的价值判断。

公式为： V π ( s ) = s u m a ∈ A π ( a ∣ s ) { R s s ′ a + γ ∑ s ′ ∈ S V π ( s ′ ) } V^{\pi}(s)=sum_{a\in A}\pi(a|s)\{R^a_{ss'}+\gamma\sum_{s'\in S} V^{\pi}(s')\} Vπ(s)=suma∈A?π(a∣s){Rss′a?+γs′∈S∑?Vπ(s′)}

举例为：

V π ( s = 4 ) = s u m a ∈ { ? 2 , ? 1 , 0 , 1 , 2 } π ( a ∣ s ) V^{\pi}(s=4)=sum_{a\in \{-2,-1,0,1,2\}}\pi(a|s) Vπ(s=4)=suma∈{?2,?1,0,1,2}?π(a∣s)? { R 4 a + γ ∑ s ′ ∈ { 0 , . . . , 13 } P 4 s ′ a V π ( s ′ ) } \{R^a_4+\gamma \sum_{s'\in \{0,...,13 \}}P^a_{4s'}V^{\pi}(s') \} {R4a?+γ∑s′∈{0,...,13}?P4s′a?Vπ(s′)}??

$=0.2?$???????????? $(R_4^0+\gamma \times$$[0.05\times V^{\pi }(1)+0.1\times V^{\pi }(2)+0.3\times V^{\pi }(30)0.1\times V^{\pi }(5)+0.1\times V^{\pi }(6)+0.05\times (V^{\pi }(7))+V^{\pi }(8)+V^{\pi }(9)]$?????????????)

$+0.4?$????? $(R_4^{?2}+\gamma \times$??

$[0.05\times V^{\pi }(3)+0.1\times (V^{\pi }(4)+V^{\pi }(5)+V^{\pi }(6)+V^{\pi }(7)+V^{\pi }(8)+V^{\pi }(9)+V^{\pi }(10)+V^{\pi }(11)+V^{\pi }(12))+0.05\times V^{\pi }(13)]$??
$+0.4?$?? $(R_4^{?1}+\gamma \times$??
$[0.05\times V^{\pi }(3)+0.1\times (V^{\pi }(4)+V^{\pi }(5)+V^{\pi }(6)+V^{\pi }(7)+V^{\pi }(8)+V^{\pi }(9)+V^{\pi }(10)+V^{\pi }(11)+V^{\pi }(12))+0.05\times V^{\pi }(13)]$

1.3.2 Q函数（状态动作函数）

对当前状态-动作的价值判断

公式为：$$Q^{\pi }(s,a)=R_S^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\sum _{a^{\prime }\in S}\pi (a|s)Q^{\pi }(s^{\prime },a^{\prime })$$
举例略()

1.3.3 Q函数与值函数的关系

$$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a)$$

$$Q^{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\pi }(s^{\prime })$$

1.4最优价值函数

1. 最优状态价值函数：是所有策略下产生的众多状态价值函数中的最大者，即：$V^{?}(s)={\max }_{\pi }{V}^{\pi }(s)$

2. 最优董总价值函数：是所有策略下产生的众多动作状态价值函数中的最大者，即：$Q^{?}(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$

3. 最优策略，基于动作价值函数可以定义胃：

   ${\pi }^{?}(a|s)=\{\begin{array}{ll}1,& ifa=\arg ma{x}_{a\in A}{Q}^{?}(s,a)\\ 0,& else\end{array}$

4. 只要我们找到了最大的状态价值函数或者动作价值函数，那么对应的策略${\pi }^{?}$?就是我们强化学习问题的解。

1.5 Bellman最优方程

可以根据最优价值函数的定义，可以推到其bellman方程形式

1. 最优状态价值函数 :$V^{?}(s)={\max }_{\pi }{V}^{\pi }(s)$

   $$\begin{array}{rlr}{V}^{?}(s)& =\underset{\pi }{\max }{V}^{\pi }(s)& 对不同策略取的V值取最大\\ & =\underset{\pi }{\max }(\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a))& 代入V值与Q值得关系\\ & =\underset{\pi }{\max }\underset{a\in A}{\max }{Q}^{\pi }(s,a)& 上一行是动作状态得期望，此行是动作状态得最值\\ & =\underset{a\in A}{\max }{Q}^{?}(s,a)& 调换两个max,逆用最优状态动作值函数\end{array}$$

   1.1 $\pi (a|s)\in [0,1],且{\sum }_{a\in A}\pi (a|s)=1$

   1.2 ${\sum }_{a\in A}\pi (a|s)Q^{\pi }(s,a)$得最大值：

   1. 假设在状态s下执行动作$a^{?}$?时，$Q_{\pi }(s,a^{?})$?得值最大，$Q_{\pi }(s,a^{?})\ge Q_{\pi }(s,a),a\in A$?

2. 最优行为价值函数:$Q^{?}(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$
   $$\begin{array}{rlr}{Q}^{?}(s,a)& =\underset{\pi }{\max }{Q}^{\pi }(s,a)& 对不同策略固定得a取Q最值\\ & =\underset{\pi }{\max }(R_{s{s}^{\prime }}^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\pi }(s^{\prime }))& 带入Q值与V值得关系\\ & =R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{?}(s^{\prime })& max进去后，逆用最优状态值函数\end{array}$$
   3.$Q^{?}(s,a)和V^{?}(s)$的递推表达式为：

$$V^{?}(s)=\underset{a\in A}{\max }(R_S^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}V?(s^{\prime }))$$?
$$Q^{?}(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\underset{a\in A}{\max }{Q}^{?}(s^{\prime },a^{\prime })$$

二、 常用案例迭代

这里时一个常用的MDP的案例。figq为原始案例图以及初值表示；fig2表示计算后的结果

注意：这里认为当下的策略是最优策略，没有对策略进行取最大值的步骤。此外，为方便计算折扣因子$\gamma =1$
我们根据最优Q*的迭代说明一下
$Q^{?}(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$,$V^{?}(s)={\max }_{\pi }{V}^{\pi }(s)$

• 公式为：
• $Q^{?}(s,a)=R_s^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{\max }_{a\in A}{Q}^{?}(s^{\prime },a^{\prime })$，
• $V^{?}(s)={\max }_{a\in A}(R_S^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}V?(s^{\prime }))$

• ${\sum }_{s^{\prime }}$ ，s‘是对当前状态s和动作a后产生的下一状态，任意状态都有$P_{s{s}^{\prime }}^a$的概率发生，所以要求和
• $R_s^a$是当下的动作的即时报酬
• $\gamma$是下一状态动作的折扣因子
• ${\max }_{a^{\prime }}{Q}^{?}(s^{\prime },a^{\prime })$:对未来状态s’，进行采取动作a’的最大动作-状态的报酬(值函数)

$Q^{?}(s,a)$迭代过程：

1. 方块是终点，所以迭代的初始值函数为0
2. • $Q^{?}(S_4,study)=10,Q^{?}(S_3,sleep)=0$
3. • $Q^{?}(S_4,pub)=1+0.2\times {\max }_{a^{\prime }}{Q}^{?}(S_2,a^{\prime })+0.4\times {\max }_{a^{\prime }}{Q}^{?}(S_3,a^{\prime })+0.4\times {\max }_{a^{\prime }}{Q}^{?}(S_4,a^{\prime })$
     求${\max }_{a^{\prime }}{Q}^{?}(S_4,a^{\prime })$,假设已知为最大值。
   • $\max Q^{?}(S_4,a^{\prime })$$=10$
4. • $Q^{?}(S_3,study)=?2+$${\max }_{a^{\prime }}{Q}^{?}(S_4,a^{\prime })$$=?2+10=8$
   • $\max Q^{?}(S_3,a^{\prime })=max(8,0)=8$
5. • $Q^{?}(S_2,study)=?2+$ ${\max }_{a^{\prime }}(S_3,a^{\prime })$$=?2+8=6$
   • $Q^{?}(S_3,pub)=?1+{\max }_{a^{\prime }}{Q}^{?}(S_1,a^{\prime })$
     求${\max }_{a^{\prime }}{Q}^{?}(S_2,a^{\prime })$。假设已知为最大值。
   • $\max Q^{?}(S_2,a^{\prime })$$=6$
6. • $Q^{?}(S_1,Fab)=?1+{\max }_{a^{\prime }}(S_1,a^{\prime })$
   • $Q^{?}(S_1,quit)=0+$${\max }_{a^{\prime }}(S_2,a^{\prime })$ $=6$
     求${\max }_{a^{\prime }}{Q}^{?}(S_1,a^{\prime })$。假设已知为最大值。
   • $\max Q^{?}(S_1,a^{\prime })$$=6$
7. 倒退逐步验证每一个假设
   • $Q^{?}(S_1,Fab)=?1+{\max }_{a^{\prime }}(S_1,a^{\prime })=5<\max Q^{?}(S_1,a^{\prime })=6$,假设成立
   • $Q^{?}(S_3,pub)=?1+{\max }_{a^{\prime }}{Q}^{?}(S_1,a^{\prime })=5<\max Q^{?}(S_3,a^{\prime })=10$,假设成立
   • $\begin{array}{rl}{Q}^{?}(S_4,pub)& =1+0.2\times \underset{a^{\prime }}{\max }{Q}^{?}(S_2,a^{\prime })+0.4\times \underset{a^{\prime }}{\max }{Q}^{?}(S_3,a^{\prime })+0.4\times \underset{a^{\prime }}{\max }{Q}^{?}(S_4,a^{\prime })\\ & =1+0.2\times 6+0.4\times 8+0.4\times 10\\ & =9.4<\max Q^{?}(S_4,a^{\prime })=10\end{array}$,假设成立

$V^{?}(s)$的迭代过程：

1. 方块是终点，所以迭代的初始值函数为0
   • $V^{?}(end)=0$
2. • V ? ( S 4 ) = max ? { V^*(S4)=\max\{ V?(S4)=max{$10+0$,$1+0.2\times V^{?}(S_2)+0.4\times V^{?}(S_3)+0.4\times V^{?}(S_4)\}$=10(假设已知为最大值。)
3. • V ? ( S 3 ) = max ? { V*(S_3)=\max\{ V?(S3?)=max{ $0+0$,$?2+V^{?}(S_4)\}$=8
4. • V ? ( S 2 ) = max ? { V^*(S_2)=\max\{ V?(S2?)=max{ $?1+V^{?}(S_1)$,$?2+V^{?}(S_3)\}$$=6(假设已知为最大值。)
5. • V ? ( S 1 ) = max ? { V^*(S_1)=\max\{ V?(S1?)=max{-1+V^*(S_1)\quad$,$0+V^{?}(S_2)$}=6(假设已知为最大值。)
6. 经验证，三个假设都成立。