强化学习杂谈 1

写在前面

本次杂谈中讨论了几个问题：

环境与动作的交互问题
利用与探索问题

符号与标记 Notation

Env	环境	Agent	智能体
$r$	奖励	$A$	动作
$P$	转移概率矩阵	$S$	状态

进入状态 s 的即时奖励：$r(s)$

奖励函数（时刻 $S_t$ 获得的即时奖励）：$r_t$

时刻 $S_t$ 之后获得的所有奖励：$G_t=r_t+\gamma r_{t+1}+\gamma^2r_{t+2}+…=\sum^{\infin}_{k=0}\gamma^kr_{t+k}$

价值函数（衡量进入状态 s 的长期奖励）：$V(s)=\mathbb{E}[G_t|S_t=s]$

从状态 $s$ 到状态 $s’$ 的转移概率：$p(s’|s)=P(S_{t+1}=s’|S_t=s)$

在状态 $s$ 选择动作 $a$ 变成状态 $s’$ 的转移概率：$p(s’|s,a)=P(S_{t+1}=s’|S_t=s,A_t=a)$

策略：$\pi(a|s)=P(A_t=a|S_t=s)$

环境的变与不变

Q&A：当智能体的动作与环境发生交互时，如何理解环境因为动作的改变发生变化？

我觉得这种所谓变与不变体现在环境给智能体的反馈上，并且这种反馈的产生是路径依赖的。

举最简单的两个例子：多臂老虎机$^{[1]}$与下围棋。在多臂老虎机中，动作是拉老虎机的拉杆，环境的反馈是拉杆之后的即时盈利，很明显即时盈利并不会因为赌徒的一系列动作而发生改变。所以反馈是不变的，我们就认为环境是不变的。在下围棋的过程中两位棋手对弈，环境是棋盘上所有落子构成的对弈棋局，动作是落子且每次落子都会改变棋局的模样（环境）。或者更具体一点，对手会根据你当前的动作做出决策，从而改变环境。这是动作与环境交互的过程，也是环境反馈改变的过程。

再举一个生活中的例子。我们与语音助手进行交谈时，语音助手会根据我们的回答以预设程序进行回答，而我们的每次问话并不会改变它预设的回答方式。此时环境是不因动作发生改变的。但是我们与其他人进行交谈时，我们的回答很可能会导致这场对话的走向发生改变。这意味环境也随之发生变化，且这种变化是由交谈双方共同导致的$^{[2]}$。

[1] 多臂老虎机：一个赌徒面前有N个老虎机，事先他不知道每台老虎机的真实盈利情况，他如何根据每次玩老虎机的结果来选择下次拉哪台或者是否停止赌博，来最大化自己的从头到尾的收益。多臂老虎机的问题可以纳入一个二元组的框架下进行讨论：$$

[2] 亲密关系能否形成是否也是路径依赖的？

利用与探索 Exploration & Exploitation

在多臂老虎机问题中，一方面我们希望利用最少的步数找到对应着最大化奖励的拉杆，另一方面我们也不希望因为探索不足而忽略了真正具有最大奖励的拉杆。这就涉及到利用与探索的问题。

假设一共有10根拉杆，我们已经随机拉杆多次并得到了一个奖励数据序列 $\{R^i_k\}_{k\in \N,i=1:10}=\{R^7_1,R^5_2,R^3_3,R^8_4,R^6_5,R^1_6,…\}$，其中下标表示拉拉杆的次数，上标表示通过某种方式选择的拉杆编号。我们希望通过这个序列推测最大奖励拉杆的编号，从而最大化奖励。此外，这个序列也是我们唯一可以从中学习的对象。

所谓利用就是通过过去数据学习如何进行决策，决策目标是广义奖励（即时奖励，多步奖励，长期奖励…）最大化，而所谓探索就是通过某个准则选择非最大化广义奖励的动作。

Q&A：什么时候需要进行探索？我将按我目前粗浅的理解进行解答

智能体对环境了解不深，具体来讲就是我们并不确定能够获得最大化奖励的策略。
环境会发生改变，需要进行探索更新我们对环境的认识？

Q&A：按什么准则进行探索？

完全随机探索（那么过去获得的数据将无法提供有价值的信息
利用决策的信息（其中已经包含了过去数据的部分信息）构成 $\epsilon-Greedy$ 算法$^{[3]}$
利用决策的信息以及动作次数构成 $\epsilon-Greedy$ 算法，$\epsilon$ 会随着动作次数的增加而减少
利用决策的信息以及过去数据包含的其他统计信息（期望、方差等）构成 $Thompson$ 采样算法$^{[4]}$
…

[3] $\epsilon-Greedy$ 算法
$a_t= \begin{cases} argmax_{a\in A}\hat{Q}(a)\quad &\text{以 }1-\epsilon\text{ 的概率}\\ \text{随机选择 }a\in A &\text{以 }\epsilon\text{ 的概率} \end{cases}$
Q&A：在上述算法框架下，为什么累计懊悔无法随时间的增长被控制？

[4] 探索价值的度量方法。

Idea：最开始我想到了 $Thompson$ 采样算法的雏形，即利用过去信息中包含的期望、方差信息得到上界估计，不过当时还没有清晰地认识到它是在衡量探索价值的大小

多臂老虎机的随机奖励

如果多臂老虎机的奖励并不随机，或者说奖励是方差为零的单点分布，那么我们仅需要将所有拉杆都尝试一遍，就能知道最大奖励对应的拉杆编号了。由此可见探索的概率是与奖励的分布密切相关的。

$Q(a)\overset{estimate}{\rightarrow} q^*(a)=\mathbb{E}[R_t|A_t=a]$

Q：但对于智能体与可变环境交互产生的奖励，那又应该如何衡量呢？以下围棋为例，棋局进行到某个时刻轮到执黑棋手下棋，那么如何衡量执黑下的该步棋的奖励呢？赢棋的概率或者是其他？如何理解奖励的随机性

$r(s,a)=\mathbb{E}[R_t|S_t=s,A_t=a]$

多臂老虎机动作价值的初值选择

有些价值迭代方法依赖于初值的选择。这些方法在统计上是有偏的。但是人为选定初值也有一个好处，那就是可以利用专家的先验知识。如果一个赌徒已经在一台多臂老虎机上赚得盆满钵满，想必他会对多臂老虎机的拉杆价值有一些初步的估计。

初值的设定还有利于探索$^{[5]}$。

Idea：或许可以结合 $Thompson$ 算法或者类似的上界估计？

[5] 详见 Reinforcement Learning by Sutton P34 Ch.2.6 Optimistic Initial Value

Unbiased Constant-Step-Size Trick

是否有可能找到既能避免常数步长的有偏性，又能保留常数步长在非稳定问题上的优势（即更加注重即时奖励）？考虑步长 $\beta_n\dot{=}\frac{\alpha}{\overline{o}_n}$，其中 $\alpha$ 为常数，$\overline{o}_n$ 为初值为零的数列

$\overline{o}_n=\overline{o}_{n-1} + \alpha(1-\overline{o}_{n-1}),\quad n\in\N_+$

则有

$1-\beta_i=\frac{(1-\alpha)\overline{o}_{i-1}}{\overline{o}_i}$

对于动作价值迭代式

$\begin{aligned} Q_{n+1}&=\beta_n R_n + (1-\beta_n)Q_n\\ &=... + \prod_{i=1}^{n}(1-\beta_i)Q_1 \end{aligned}$

最后一项为零，故按此步长更新是无偏的。上述步长是否保留了常步长的优势，还需验证中间项的系数。

马尔可夫奖励过程 MRP

马尔可夫奖励过程假设智能体与环境交互过程中的状态转移满足马尔可夫性，它可以纳入一个四元组框架进行讨论：$$

进入状态 $s$ 的价值，也即状态 $s$ 的长期奖励为 $V(s)=\mathbb{E}[G_t|S_t=s]$，稍加变形我们得到

$\begin{aligned} V(s)&=\mathbb{E}[G_t|S_t=s]\\ &=\mathbb{E}[r_t+\gamma G_{t+1}|S_t=s]\\ &=\mathbb{E}[r_t|S_t=s]+\gamma\mathbb{E}[G_{t+1}|S_t=s]\\ &=\mathbb{E}[r_t|S_t=s]+\gamma\sum_{s'\in S}\mathbb{E}[G_{t+1}|S_{t+1}=s']p(s'|s)\\ &=r(s)+\gamma\sum_{s'\in S}V(s')p(s'|s) \end{aligned}$

以上就是著名的 $Bellman$ 方程。如果已知 $r(s)$ 和 $p(s’|s)$，我们可以通过迭代找到不动点 $V(s^*)^{[6]}$

[6] 需验证迭代序列是否收敛

Q：如何通过采样了解整个马尔可夫链？如果答案是肯定的，这是否意味着我们可以通过蒙特卡罗方法估算 $p(s’|s)$？

马尔可夫决策过程 MDP

MDP在马尔可夫奖励过程的基础上加上动作空间，与之前不同，状态的转移不仅依赖于上一个状态，还依赖动作的选择。由此构成一个状态-动作-状态的循环网络

上一节中的价值函数准确来讲应该称为状态价值函数，同时因为动作空间的引入，我们还可以定义动作价值函数，用于衡量当处在某个状态时选择某个动作的价值

当然我们并不能简单照搬之前的定义，注意到基于奖励的动作选择构成一个策略。在某个状态下选择不同的动作对应不同的策略，不同的策略将导致状态的长期奖励不同。所以在衡量价值函数或者动作价值函数时，我们是针对策略进行考虑的

由此，我们考虑基于策略的状态价值函数 $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]$

改写一下上述两个等式，对于状态价值函数

$\begin{aligned} V^{\pi}(s)&=\mathbb{E}_\pi[G_t|S_t=s]\\ &=\mathbb{E}_\pi[r_t+\gamma G_{t+1}|S_t=s]\\ &=\sum_{a\in A}p(A_t=a|S_t=s)\{\mathbb{E}_\pi[r_t|S_t=s,A_t=a]+\gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a]\}\\ &=\sum_{a\in A}\pi(a|s)\{r(s,a)+\gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a]\}\\ &=\sum_{a\in A}\pi(a|s)\{r(s,a)+\gamma\sum_{s'\in S}\mathbb{E}_\pi[G_{t+1}|S_{t+1}=s']p(s'|s,a)\}\\ &=\sum_{a\in A}\pi(a|s)[r(s,a)+\gamma\sum_{s'\in S}V^{\pi}(s')p(s'|s,a)]\\ \end{aligned}$

同理对于动作价值函数

$\begin{aligned} Q^{\pi}(s,a)&=\mathbb{E}_\pi[G_t|S_t=s,A_t=a]\\ &=\mathbb{E}_\pi[r_t+\gamma G_{t+1}|S_t=s,A_t=a]\\ &=\mathbb{E}_\pi[r_t|S_t=s,A_t=a]+\gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a]\\ &=r(s,a)+\gamma\sum_{s'\in S}p(s'|s,a)\mathbb{E}_\pi[G_{t+1}|S_{t+1}=s']\\ &=r(s,a)+\gamma\sum_{s'\in S}p(s'|s,a)V^{\pi}(s')\\ &=r(s,a)+\gamma\sum_{s'\in S}p(s'|s,a)\sum_{a'\in A}\pi(a'|s')\mathbb{E}_\pi[G_{t+1}|S_{t+1}=s',A_{t+1}=a']\\ &=r(s,a)+\gamma\sum_{s'\in S}p(s'|s,a)\sum_{a'\in A}\pi(a'|s')Q^{\pi}(s',a')\\ \end{aligned}$

下表总结了四个重要的关系式


$V^{\pi}(s)=\sum_{a\in A}\pi(a	s)[r(s,a)+\gamma\sum_{s’\in S}V^{\pi}(s’)p(s’	s,a)]$
$Q^{\pi}(s,a)=r(s,a)+\gamma\sum_{s’\in S}p(s’	s,a)V^{\pi}(s’)$
$Q^{\pi}(s,a)=r(s,a)+\gamma\sum_{s’\in S}p(s’	s,a)\sum_{a’\in A}\pi(a’	s’)Q^{\pi}(s’,a’)$

Q：对于无限状态 / 动作的马尔可夫链，是否会出现无法通过采样进行估算的情况？

勘误

所谓利用就是通过过去数据学习如何进行决策，决策目标是广义奖励（即时奖励，多步奖励，长期奖励…）最大化，而所谓探索就是通过某个准则选择非最大化广义奖励的动作。

订正：事实上这里的表述容易让人引发误会。首先需要明确一点，如果仅考虑利用和探索的作用（从当前的视角看未来），利用更倾向于短期奖励，而探索的目的是找到最大化长期奖励。但是在实践中，当前时刻的利用其实也包含了过去探索所获得的信息。这是从过去的角度看现在，所以说它目标不仅仅是短期奖励其实也是合理的。