RL基础分享 (1)

- 1 -

$$\left<\mathcal S,\mathcal P\right>$$ $$\left<\mathcal S,\mathcal P, \mathcal R,\gamma\right>$$ $$\left<\mathcal S,\mathcal A,\mathcal P, \mathcal R,\gamma\right>$$ $$G_t = R_{t+1}+\gamma R_{t+2}+\dots$$

状态转移表

	Class1	Class2	Class3	Pass	Pub	TikTok	Sleep
Class1		0.5				0.5
Class2			0.8				0.2
Class3				0.6	0.4
Pass							1.0
Pub	0.2	0.4	0.4
TikTok	0.1					0.9
Sleep

episode:

• C1-C2-C3-Pass-Sleep：非常认真的学生
• C1-TicTok-TicTok-C1-C2-Sleep：第一节课走神的学生
• C1-C2-C3-Pub-C1-TicTok-TicTok-TicTok-C1-C2-C3-Pub-C3-Pass-Sleep：经常走神的学生

MDP上学案例状态函数求解

$$\begin{aligned} v(s) &= \mathbb E[G_t|S_t=s]\\ \end{aligned}$$ $$\begin{aligned} v_1 & = -2 + \gamma(0.5\times v_2 + 0.5\times v_6) \\ v_2 & = -2 + \gamma(0.8\times v_3 + 0.2\times v_7) \\ v_3 & = -2 + \gamma(0.6\times v_4 + 0.4\times v_5) \\ v_4 & = 10 + \gamma(1.0\times v_7) \\ v_5 & = 1 + \gamma(0.2\times v_1 + 0.4\times v_2 + 0.4\times v_3) \\ v_6 & = -1 + \gamma(0.1\times v_1 + 0.9\times v_6) \\ v_7 & = 0 + \gamma(1\times v_7) \end{aligned}$$

写成矩阵形式

$$\left[ \begin{matrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \\ v_6 \\ v_7 \end{matrix} \right] = \left[ \begin{matrix} -2 \\ -2 \\ -2 \\ 10 \\ 1 \\ -1 \\ 0 \end{matrix} \right] + \gamma\left[ \begin{matrix} & 0.5 & & & & 0.5 & \\ & & 0.8 & & & & 0.2 \\ & & & 0.6 & 0.4 & & \\ & & & & & & 1.0 \\ 0.2 & 0.4 & 0.4 & & & & \\ 0.1 & & & & & 0.9 & \\ & & & & & & 1 \end{matrix}\right] \left[ \begin{matrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \\ v_6 \\ v_7 \end{matrix} \right]$$

小规模的MDP问题，可以直接求解下式

$$\begin{aligned} v &= \mathcal R+\gamma\mathcal P v \\ v &= (1-\gamma\mathcal P)^{-1}\mathcal R \end{aligned}$$

上式也就是 Bellman 方程的形式，递归形式

$$v(s) = \mathcal R_s + \gamma\sum_{s'\in\mathcal S} \mathcal P_{ss'}v(s')$$

- 2 -

定义行动的有限集合$\mathcal A$和策略$\pi$

$$\pi(a|s) = \mathbb P[A_t = a|S_t = s]$$

基于所给MDP $\left<\mathcal S,\mathcal A,\mathcal P, \mathcal R,\gamma\right>$和policy $\pi$：
得到的马尔可夫过程为$\left<\mathcal S,\mathcal P^\pi\right>$

对应策略的状态转移概率和奖励为：

$$\begin{aligned} \mathcal P^\pi_{s,s'} &= \sum_{a\in\mathcal A}\pi(a|s)\mathcal P^a_{ss'}\\ \mathcal R^\pi_{s} &= \sum_{a\in\mathcal A}\pi(a|s)\mathcal R^a_{s} \end{aligned}$$

因为增加了行动，如何评价行动，参考状态价值函数，我们定义行动价值函数

$$\begin{aligned} v_\pi(s) &= \mathbb E_\pi[G_t|S_t=s]\\ q_\pi(s,a) &= \mathbb E_\pi[G_t|S_t=s,A_t=a] \\ \end{aligned}$$

$\mathcal R$：

s\a	Study	Thirsty	TikTok	Sleep	Quit
Class1	-2	\	-1	\	\
Class2	-2	\	\	0	\
Class3	10	1	\	\	\
TikTok	\	\	-1	\	0
Sleep	\	\	\	\	\

$\mathcal P^\pi$：

	Class1	Class2	Class3	TikTok	Sleep
Class1		0.5		0.5
Class2			0.5		0.5
Class3	0.1	0.2	0.2		0.5
TikTok	0.5			0.5
Sleep

$\mathcal R^\pi$：

Class1	Class2	Class3	TikTok	Sleep
-1.5	-1	5.5	-0.5	0

利用 Bellman 公式

$$\begin{aligned} v &= \mathcal R^\pi+\gamma\mathcal P^\pi v \\ v &= (1-\gamma\mathcal P^\pi)^{-1}\mathcal R^\pi \end{aligned}$$

计算出了当前策略下的价值

- 3 -

最优价值函数 Optimal Value Function

$$\begin{aligned} v_*(s) &= \max_\pi v_\pi(s) \\ q_*(s,a) &= \max_\pi q_\pi(s,a) \\ \end{aligned}$$

通过计算最好的选择，实现对状态的好坏进行评价，当得到最优价值函数后，MDP问题就解决了。

几个 Bellman 方程：

$$\begin{aligned} v_*(s) &= \max_a q_*(s,a) \\ v_*(s) &= \max_a \mathcal R^a_s + \gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}v_*(s') \\ q_*(s,a) &= \mathcal R^a_s+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}v_*(s') \\ q_*(s,a) &= \mathcal R^a_s+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}\max_a q_*(s',a') \\ \end{aligned}$$

策略提升：

$$\pi'(s) = argmax_a q_\pi(s,a)$$

最优策略：

$$\pi \ge \pi' \quad if v_\pi(s)\ge v_{\pi'}(s),\quad \forall s$$ $$\mathcal P^a \rightarrow \pi \rightarrow v_\pi(s) \rightarrow q_\pi(s,a) \rightarrow \pi' \rightarrow v_{\pi'}(s) \rightarrow \dots \rightarrow \pi_*$$

价值迭代推导过程：

$$\begin{aligned} & v_\pi(s) = \sum_{a\in\mathcal A}\pi(a|s)q_\pi(s,a) \\ & q_\pi(s,a) = \mathcal R_s^a+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}v_\pi(s')\\ & v_\pi(s) = \sum_{a\in\mathcal A}\pi(a|s)\left( \mathcal R_s^a+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}v_\pi(s') \right) \\ & q_\pi(s,a) = \mathcal R_s^a+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'} \sum_{a\in\mathcal A}\pi(a|s)q_\pi(s,a) \\ \end{aligned}$$ $$\begin{aligned} & v_\pi(s) \leftarrow \max_a q_\pi(s,a) \\ & v_\pi(s) \leftarrow \max_a \left( \mathcal R_s^a+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}v_\pi(s') \right) \\ \end{aligned}$$

value-base 方法

估计价值函数

$$\begin{aligned} & q_\pi(s,a) = \mathcal R_s^a+\gamma\sum_{s'\in\mathcal S} \mathcal P^a_{ss'}v_\pi(s')\\ \\ & q_\pi(s,a) \simeq \frac{1}{N}\sum^{N}{i=1}\sum^{\infty}_{k=0}\gamma^k R_{i+k} \end{aligned}$$

Monte-Carlo:

$$\begin{aligned} N(s)&\leftarrow N(s)+1\\ S(s)&\leftarrow S(s)+G_t\\ V(s)&\leftarrow S(s)/N(s)\\ V(s)&\rightarrow v_\pi(s)\quad if N(s)\rightarrow\infty \end{aligned}$$ $$\begin{aligned} N(S_t)&\leftarrow N(S_t)+1\\ V(S_t)&\leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t))\\ \end{aligned}$$

Temporal Difference:

Incremental every-visit Monte-Carlo

$$\begin{aligned} N(S_t)&\leftarrow N(S_t)+1\\ S(S_t)&\leftarrow S(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t))\\ \\ V(S_t)&\leftarrow V(S_t)+\alpha(G_t-V(S_t))\\ \end{aligned}$$

TD(0)

$$\begin{aligned} V(S_t)&\leftarrow V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))\\ \end{aligned}$$

Sarsa

$$\begin{aligned} Q(S,A)&\leftarrow Q(S,A)+\alpha(R+\gamma Q(S',A')-Q(S,A))\\ \end{aligned}$$

Importance Sampling

$$\begin{aligned} \mathbb E_{X\sim P}\left[f(X)\right] &= \sum P(X)f(X)\\ &= \sum Q(X)\frac{P(X)}{Q(X)}f(X)\\ &= \mathbb E_{X\sim Q}\left[\frac{P(X)}{Q(X)}f(X)\right] \end{aligned}$$

Q learning

$$\begin{aligned} Q(S,A)&\leftarrow Q(S,A)+\alpha(R+\gamma\max_{a'} Q(S',A')-Q(S,A))\\ \\ Q(S_t,A_t)&\leftarrow Q(S_t,A_t)+\alpha(R_{t+1}+\gamma Q(S_{t+1},A'_{t+1})-Q(S_t,A_t))\\ &A_t\sim \mu(\ \cdot|S_{t})\\ &A'_{t+1}\sim \pi(\ \cdot|S_{t+1})\\ \end{aligned}$$ $$\pi(a|s) = \begin{cases} \epsilon/m + 1 - \epsilon, & \text{if $a^*= argmax_{a\in \mathcal A}Q(s, a)$} \\ \epsilon/m, & \text{else} \end{cases}$$

行动策略 $\mu$ 、借鉴（评价）策略 $\pi$

$$V(S_t)\leftarrow V(S_t)+\alpha(\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}(R_{t+1}+\gamma V(S_{t+1}))-V(S_t))$$