BasicRL(1)-从基本概念到Bellman方程

RL 的基础概念

智能体 Agent: 和环境交互，执行策略，获得奖励的实体。

环境 Env: 智能体所处的环境，负责决定智能体的行为得到的奖励，和智能体在当前状态进行下一个动作之后的状态转移。

动作 Action: 智能体在环境中的行为，智能体对环境造成影响的部分，同时造成智能体的状态发生变化。

策略 Policy: 指智能体在状态 s, 选择动作 a 的概率分布，通常用 $π(a|s)$ 表示。

状态 State: 智能体在环境中的状态，智能体在环境中的位置，速度，方向等。

观测 Observation: 智能体在环境中的观测，智能体在环境中的状态的一部分，通常是不完全的，即智能体无法观测到环境的全部状态。如果我们完全知道环境，可以认为 Observation = State。

RL: 找到一个策略 $\pi(a|s)$，使得智能体获得最大的奖励（期望）。

• Q: 奖励是什么？A: 是根据真实环境设计的反馈，类似 DL 之中设计 loss
• Q: 为什么有期望？A: 因为状态，动作等都可以是随机变量，后面会大量看到

以一个机器人在二维网格之中移动的例子为例，我们可以定义状态为机器人在网格中的位置，动作为机器人在网格中的移动方向，奖励为机器人到达目标的奖励，到达障碍物的惩罚。我们可以定义一个策略，使得机器人在网格中移动，最终到达目标。

RL 与 DL 的关键不同点：RL 的数据是从环境之中根据状态的转移“Observe”得来, 而不是 DL 那样的提前准备的数据集

• 因此，RL 的一大难点就在于，从环境中得到的数据的效率问题，以及不同状态/策略下从环境得到的数据分布变化的问题

探索(exploration)与利用(exploitation): 在 RL 中，智能体需要在探索新的策略，以获得更多的奖励，和利用已有的策略，以获得更多的奖励之间进行权衡。通常我们会引入 $\epsilon$-greedy 策略，即以 $\epsilon$ 的概率随机选择动作，以 $1-\epsilon$ 的概率选择当前最优的动作来平衡探索与利用。

Q: 为什么不把探索与利用分成两部分（两个策略）来完成？

A: 事实上是可以的，分开的情况下通常对应 off-policy 算法（后面会讲具体的意思），但需要理解的是，不同状态/策略分布下从环境得到的数据分布是不同的，如果使用不同的策略，那我们就需要一些机制（如重要性采样）来调整这些数据的分布，以保证算法的收敛性。相比来说，单策略算法（on-policy 算法）更加简单。

Q: 我认为 $\epsilon$-greedy 策略是不是有点简单了？过小的 $\epsilon$ 会导致探索的效率很低，过大的 $\epsilon$ 会导致智能体无法利用已有的策略，最后策略的结果变差。

A: 是的，$\epsilon$-greedy 策略是一个比较简单的策略，但是在实际应用中，我们可以使用更加复杂的策略，如 UCB 策略，Thompson Sampling 策略等，这些策略可以根据智能体在环境中的表现，自适应的调整探索与利用的比例，以获得更好的效果。一个简单的想法就是类似 DL 之中的 Adam, 我们可以让 $\epsilon$ 随着训练的进行而逐渐减小，如 $\epsilon_{t} = 1/t$，以平衡探索与利用。这几个算法会让“懊悔”（累积的收益与全局理论最优收益的差）随时间的增长而 log 级增长(原始 $\epsilon$-greedy 是线性)

轨迹 trajectory: 一个智能体在环境中的一系列状态，动作，奖励的序列，通常用 $\tau$ 表示。即为 $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, ..., s_T, a_T, r_T)$ 这样的“更新状态-采取动作(根据策略)-得到奖励”的序列

状态转移 state transition: $s_{t+1} = f(s_t, a_t)$ 的函数 $f$

确定性 determistic: 状态转移函数/奖励是确定的（而不是一个概率分布），非确定性 stochastic: 状态转移函数/奖励是一个概率分布

Markov Decision Process(MDP)

MDP 的定义: 马尔可夫决策过程，核心在于马尔可夫性质，即 当前状态的转移概率只与当前状态和当前动作有关，与之前的状态和动作无关。$s_{t+1}$ 只依赖于 $s_t$ 和 $a_t$，而不依赖于 $s_{t-1}, a_{t-1}, ...$。MDP 可以用来描述一个智能体在环境中的状态转移和奖励的过程。

MDP 是后续基本所有 RL 算法的基础，一般都会设计状态 s 让他满足

严格的来说，MDP 是一个五元组 $(S, A, P, R, \gamma)$，其中：

• S: 状态空间，智能体可能处于的状态的集合
• A: 动作空间，智能体可能采取的动作的集合
• P: 状态转移概率，$P(s_{t+1}|s_t, a_t)$ 表示在状态 $s_t$ 下采取动作 $a_t$ 后转移到状态 $s_{t+1}$ 的概率
• R: 奖励函数，$R(s_t, a_t, s_{t+1})$ 表示在状态 $s_t$ 下采取动作 $a_t$ 后转移到状态 $s_{t+1}$ 得到的奖励
• $\gamma$: 折扣因子，$0 \leq \gamma \leq 1$，用于平衡当前奖励和未来奖励的重要性

Q：$\gamma$ 的作用是什么？

A: $\gamma$ 的作用是平衡当前奖励和未来奖励的重要性。当 $\gamma=0$ 时，智能体只关注当前的奖励，而不关注未来的奖励，即智能体是一个短视的智能体；当 $\gamma=1$ 时，智能体关注当前的奖励和未来的奖励，即智能体是一个长视的智能体。通常我们会选择一个合适的 $\gamma$，以平衡当前奖励和未来奖励的重要性。在有些时候，我们会让 $\gamma$ 取 1, 来表示只要最后的结果，而不关心中间的过程。但一般来说，我们会让 $\gamma$ 取一个小于 1 的值，以平衡当前奖励和未来奖励的重要性。其实可以简单证明，选取一个小于 1 的 $\gamma$ 和诸如“对走过的路径长度做惩罚”是等效的 d

为了引入后续的算法，我们继续引入几个函数:

$U(t)$(也有写作 $G(t)$ 的): 从时间 t 开始的累积奖励，即 $U(t) = r_t + \gamma r_{t+1} + ...=\sum_{i=t}^{T} \gamma^{i-t} r_i$

$V_{\theta}(s)$: 又称为“价值函数”，表示在状态 s 下，智能体可以获得的累积奖励的期望，即 $V_{\theta}(s) = E[U(t)|s_t=s]$, 这里的 $\theta$ 是策略，写法上有 $V_{\theta}(s) = V(s|\theta)$，两种都很常见

$Q_{\theta}(s, a)$: 又称为“动作价值函数”，表示在状态 s 下，采取动作 a 后，智能体可以获得的累积奖励的期望，即 $Q_{\theta}(s, a) = E[U(t)|s_t=s, a_t=a]$

Bellman 方程

现在假设我们有一个 2*2 的世界，如下表

s1	s2
s3	s4

我们现在想要计算每个状态的 $V(s)$，应该怎么做？

假设 s1-> s2-> s3-> s4 的奖励分别为 r1, r2, r3, r4

$V(s_1)=r_1+\gamma r_2 + \gamma^{2}r_3+...$

$V(s_2)=r_2+\gamma r_3 + \gamma^{2}r_4+...$

$V(s_3)=r_3+\gamma r_4 + \gamma^{2}r_1+...$

$V(s_4)=r_4+\gamma r_1 + \gamma^{2}r_2+...$

我们发现, V(s1)和 V(s2)之间有一个关系，即 $V(s_1)=r_1+\gamma V(s_2)$，这个关系可以推广到所有的状态之间，即 $V(s)=R(s)+\gamma \sum_{s'}P(s'|s)V(s')$，这就是 Bellman 方程，即价值函数的递归关系。这个方程可以用来计算每个状态的价值函数，也可以用来计算每个状态的动作价值函数。

如果向量化的话，我们可以写成 $V(s)=R(s)+\gamma P(s)V(s)$，其中 $R(s)$ 是一个向量，$P(s)$ 是一个概率矩阵，$V(s)$ 是一个向量。这个方程可以用来计算每个状态的价值函数，也可以用来计算每个状态的动作价值函数。

有了上式，我们就可以解出 V(s), $V = (I-\gamma P)^{-1}R$

上面这个理论解的复杂度是多大呢？假设状态空间是 $N$，那么 $P$ 就是一个 $N \times N$ 的矩阵，$R$ 是一个 $N$ 维的向量，那么解这个方程的复杂度是 $O(N^3)$，这个复杂度是非常高的，当状态空间很大的时候，这个复杂度是无法接受的。因此我们需要一些近似的方法来解决这个问题。

在实际之中，我们通常采用迭代的方法来简化计算，达到 $O(N^2 logN)$ 左右的复杂度，具体有两种方法，一种叫做 Value Iteration，一种叫做 Policy Iteration，这里先给出Value Iteration的算法

$v_{k+1} = r_{\pi}+\gamma P_{\pi}v_k$, 可以证明, $v_k$ 会收敛到 $v_{\pi}$

假设我们已经求解出了 $V(s)$，那么我们如何求解对应的策略$\pi$呢？

回想$V(s)$的定义, $V(s)$是状态s下, 根据策略$\pi$选择动作$a$的期望收益，即$V(s) = \sum_a(\pi(a|s)Q(s,a)) = E(Q(s,a))$

而$Q(s,a)$是状态s下, 选择动作a后的收益，即$Q(s,a) = R(s,a) + \gamma \sum_{s'}P(s'|s,a)V(s')$，在$V(s)$和$P(s'|s,a)$均给定的情况下，$Q(s,a)$也会给定

因而，我们这个最大的$V(s)$对应的策略就是选择最大的$Q(s,a)$对应的动作（因为$V(s)$是$Q(s,a)$的期望！），即$\pi(a|s) = 1 \space if \space a=argmax_aQ_{\pi}(s,a) \space else \space 0)$，这就是对应的策略$\pi^*$

那这个最大的$V$是否对应的就是最优策略呢？

首先我们要定义什么是最优策略, 数学定义是$\forall \pi,\forall s, V_{\pi^*}(s) \geq V_{\pi}(s)$，注意这里要满足任意状态下都成立

这样的策略叫做Bellman最优策略, 可以证明它是存在且唯一的，写到之前的方程里面就是$v^{*}=max_{\pi}(r_{\pi}+\gamma P_{\pi}v^{*})$ $\pi^{*} = argmax_{\pi}(r_{\pi}+\gamma P_{\pi}v^{*})$称为Bellman方程

这样的定义下，这个最优策略就是上面提到的最大的$V(s)$对应的策略$\pi^*$, 即$v^{*}=v_{\pi^{*}}$

补充: 为什么$v_{k+1} = r_{\pi}+\gamma P_{\pi}v_k$ 能成立? 以及为什么是$log(N)$?

将上面的Bellman方程写下, $v=f(v)=max_{\pi}(r_{\pi}+\gamma P_{\pi}v)$

$||f(v_1)-f(v_2)||=||max(...)-max(...)|| \le ||max_{\pi}(\gamma P_{\pi}(v_1-v_2))|| \le \gamma||v_1-v_2||$

也就是在数轴上, 每一次迭代都让两个点的距离指数缩小，这实际上是数学之中的不动点, 由不动点的性质可知其唯一, 且收敛速度是指数级别的，因此是$log(N)$

也因为这玩意本质上是不动点，所以可以迭代求

另一个结论: $r \to ar+b$，最优策略不变, 代入bellman方程即可验证

因而我们得到了一个实际之中有用的小tip："绕路惩罚"没什么用, 如果每走一步都有一个惩罚, 最优策略不变

bellman方程有两个, 既然我们要迭代求, 那可以先迭代V, 也可以先迭代$\pi$，这就是Value Iteration和Policy Iteration的区别

Value Iteration:

1. 初始化$v$, $\pi$

2. $\pi_{k+1}=argmax_{\pi}(r_{\pi}+\gamma P_{\pi}v_k)$

3. $v_{k+1}=r_{\pi}+\gamma P_{\pi}v_k$

4. 重复2,3直到收敛

这里还有一点不清晰的地方是什么是$r_{\pi}$，我们可以更一般地将$v$展开,

$v(s)=max_{\pi}(\sum_{a}\pi(a|s)(rp(r|s,a)+\gamma \sum_{s'}P(s'|s,a)v(s')))$, 第一项 $\sum_{a}\pi(a|s)rp(r|s,a)$ 就是$r_{\pi}$

至于$P$? 这个是环境模型, 我们默认它是知道的，如果它不知道，我们就要用Model-Free的方法来求解，会在后面讲到，总之MDP就解不了了

Policy Iteration:

1. 初始化$\pi$, $v$
2. $v_{k+1}=r_{\pi}+\gamma P_{\pi}v_k$
3. $\pi_{k+1}=argmax_{\pi}(r_{\pi}+\gamma P_{\pi}v_k)$
4. 重复2,3直到收敛

有一个比较重要的观察是, 接近目标的策略会先变好(因为策略依赖于其他状态的值)，因而有一个做法是先用全局性质的Value Iteration来迭代一段距离之后，用Policy Iteration来细化，称为truncated policy iteration