一、强化学习简介

搜索：

只能在确认环境中进行，得到的是从起点到终点动作序列

强化学习：

非确定环境，学会一个策略，能够在任意状态下找到最佳动作。

序列决策任务：

一个序列任务，通过各种动作达到自己目标。

智能体从交互中学习得到最大化累计奖励的行动。

关键要素

1. 状态（state）：$s \in S$ 对当前环境的描述。

2. 动作 （action) ：$a \in A$ 对智能体采取的行动

3. 策略（policy）：$\pi$ 如何根据观察到的状态做决策，从动作空间中选择一个动作。

   强化学习最终学得的就是一个策略函数。

   • 确定性策略：$\pi: S \rightarrow A$
   • 随机性策略：$\pi: S \times A \rightarrow \mathbb{R}$

4. 状态转移（state transition）：$P: S \times A \times S \rightarrow \mathbb{R}$ 从当前t时刻状态$s_t$转移到下一个时刻的状态$s_{t+1}$。

5. 奖励（reward）：$R: S \times A \times S \rightarrow \mathbb{R}$ 执行一个动作后，环境返回给智能体一个数值。

   奖励函数的好坏影响强化学习的结果。

6. 轨迹（trajectory）： 智能体观测到的所有状态、动作、奖励的序列。

   $s_1, a_1, r_1, s_2, a_2, r_2, \cdots, s_n,a_n,r_n$

7. 回报（return）：从当前时刻开始到本回合结束的所有奖励总和。

   $G_t = R_t + R_{t+1}+\cdots$

   强化学习的目标是最大化回报，即累计奖励，而不是最大化当前奖励。

   通常考虑折扣回报，即当前时刻的奖励具有更大权重。

   $\gamma \in [0, 1]$是未来奖励的折扣因子，使得和未来奖励相比起来智能体更重视即时奖励

   $G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2}+\cdots$

8. 回合（episode）：一局游戏。

交互过程

• 观察到状态$s_t$，根据策略$\pi(s_t)$ 选择动作 $a_t$
• 执行动作$a_t$，状态转移至$s_{t+1}$，获得奖励$r_t$

二、马尔科夫决策过程(Markov Decision Process, MDP)

1. 基本概念

• 状态变量：给定时刻$t$，随机变量$X$的取值$X_1, \cdots, X_t$
• 初始状态概率：随机变量$X$的先验概率分布
• 转移模型(transition model)：指定世界如何随时间演变，给定过去的状态变量取值之后，确定最新状态的概率分布$P(X_t|X_1X_2,\dots X_{t-1})$

马尔可夫假设：当前状态只依赖于有限的固定数量的过去状态。

状态 + 状态转移 = 马尔可夫过程

2. 定义

具有马尔可夫性质的随机过程。

状态$S_t$是马尔可夫的，当且仅当：

强化学习对应了马尔可夫四元组：$(S, A, P, R)$

有模型学习(model-based learning)：假设$S, A, P, R$均已知。

MDP模型的动态转换：

• 从状态$s_0$开始，智能体选择某个动作$a_0 \in A$，智能体得到奖励$r_0$

• MDP随机转移到下一个状态$s_1 \sim P_{s_0a_0}$

• 这个过程不断进行

  $$s_0 \xrightarrow{a_0,r_0} s_1 \xrightarrow{a_1, r_1} s_2 \xrightarrow{a_2, r_2} s_3$$

• 智能体的总回报为：$r_0 + \gamma r_1 + \gamma^2 r_2 + \cdots$

3. 一个例子——Grid World

环境：有若干网络单元组成的网格世界

可通行单元 / 禁止进入单元 / 目标单元 / 边界

任务：给定任意起始位置，寻找一条通往目标的"较好"路径。（如何定义“较好”？）

• 状态：在grid world中，状态就是agent所在的位置。

• 状态空间：所有状态的集合$\{S_1, S_2, \cdots, S_9\}$(假设一共只有9个格子)。

• 动作：上下左右、不动

• 动作空间：所有可行动作的集合

• 状态转移概率：$P(S_2|S_1, a_2) = \pi(a_2 | S_1)$自定。

• 奖励函数：

  • 越出边界：$r_{bound} = -1$
  • 进入禁止单元：$r_{forbid} = -1$
  • 到达目标单元：$r_{target} = 1$
  • 其他情况，奖励$r=0$

贝尔曼方程

1. 有模型学习

目标：选择能够最大化累计奖励期望的策略$\pi(s):S \rightarrow A$

三个步骤： 策略评估、改进、迭代

2. 价值函数

状态（或状态-动作二元组）的函数，用来评估当前智能体在给定状态（或给定状态与动作）下有多好。

• 状态值函数(State value function)

  $$V^{\pi}(s_t)=\mathbb{E}[r_t+\gamma r_{t+1}+\gamma^2r_{t+2} + \cdots |s =s_t]$$

• 状态-动作值函数(State-Action value function)

  $$Q^{\pi}(s_t, a_t)=\mathbb{E}[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2}+ \cdots | s=s_t, a= a_t]$$

• 两者的关系：

  $$V^{\pi}(s_t)=\sum_{a}\pi(s_t, a)\cdot Q^{\pi}(s_t, a)$$

3. 贝尔曼方程

其中：

• $r_{sa}(s')$表示从状态 s 采取动作 a 转换到状态 s' 所获得的奖励
• $P_{sa}(s')$表示从状态 s 采取动作 a 转换到状态 s' 的概率（归属于环境）
• $\pi(s, a)$表示在状态 s 下采取动作 a 的概率（归属智能体）

贝尔曼最优方程

最优策略对应的值函数称为最优值函数。

非最优策略的改进方式：将策略选择的动作改为当前最优的动作

4. 价值迭代

过程：

1. 对于每个状态$s$，初始化$V(s) = 0$

2. 重复以下过程直到收敛：

   • 对每个状态，更新$V(s) = max_a\sum_{s'\in S}P_{sa}(s')(r_{sa}(s') + \gamma V^{\pi}(s'))= max_a Q^{\pi}(sa)$

5. 策略迭代

过程：

1. 随机初始化策略$\pi$

2. 重复以下过程直到收敛：

   • 策略评估：$V:= V^{\pi}=\sum_a \pi(s, a)\sum_{s'\in S}P_{sa}(s')(r_{sa}(s')+\gamma V^{\pi}(s'))$
   • 策略改进：对每个状态，更新 $\pi(s) = arg\ max_{a \in A}Q^{\pi}(s,a)$

总结：

• 两种策略均可归结为基于动态规划的寻优算法
• 价值迭代是贪心更新法
• 策略迭代中，用Bellman等式更新价值函数代价很大
• 对于空间较小的MDP，策略迭代通常很快收敛
• 对于空间较大的MDP，价值迭代更实用（效率更高）

无模型学习

状态转移函数与奖励函数未知。

从“经验”中学习一个MDP模型：

• 学习状态转移概率

  $$P_{sa}(s') = \frac{\text{在s下采取动作a并转移到s'的次数}}{\text{在s下采取动作a的次数}}$$

有没有办法不学习MDP？能不能从经验数据中直接学习价值函数和策略函数？——模型无关的强化学习(Model-Free Reinforcement Learning)

1. 蒙特卡洛强化学习

• 在模型未知的情形下，从起始状态出发，使用某个策略进行采样获得轨迹

  Episode 1: $s_1, a_1, r_1, s_2, a_2, r_2, \cdots, s_r, a_r, r_r$

• 对于轨迹中出现的每一对状态-动作，记录其奖赏之和，作为该状态-动作对的一次累计奖赏采样值

• 多次采样得到多条轨迹之后，将每个状态-动作对的累计奖赏采样值进行平均，得到状态-动作值函数$Q$的估计

• 从某个状态-动作出发，执行策略得到一个回合的轨迹，基于该回合数据估计状态-动作的价值

  $s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_1} \dots$

• 一个长的回合可以看做很多个从不同状态-动作出发的子回合，可以用于估计多个不同状态-动作 的值；样本效率更高

  

• 访问在一个回合中的每个时间步长$t$的状态$s$

  • 增量计算器$N(s) \leftarrow N(s) + 1$
  • 增量总累计奖励$S(s) \leftarrow S(s) + G_t$
  • 价值被估计为累计奖励的均值$V(s) = S(s) / N(s)$

• 同理，可计算出$Q(s, a)$

注意：如果策略是确定性的，对于某个状态只会输出一个动作，使用这样的策略进行采样，只能得到多条相同的轨迹

引入$\epsilon-$贪心算法

1. 轨迹采样：按照当前策略的$\epsilon-$贪心版本与环境交互，得到 episode
2. 策略评估：根据采样的轨迹更新$Q(s,a)$的估计
3. 策略改进：根据新的$Q$，更新策略

异策略（off-policy）蒙特卡洛强化学习

仅在评估时引入$\epsilon$贪心策略，策略改进时改进原始策略

• 估计一个不同分布的期望：

  $$\begin{aligned} \mathbb{E}_{x-p}[f(x)]&=\int_x p(x)f(x)dx\\ &= \int_xq(x)\frac{p(x)}{q(x)}f(x)dx\\ &= \mathbb{E}_{x-q}[\frac{p(x)}{q(x)}f(x)] \end{aligned}$$

• 将每个实例的权重重新分配为$\beta(x) = \frac{p(x)}{q(x)}$

使用策略$\pi$的采样轨迹来评估策略$\pi$，实际上就是对累计奖赏估计期望

使用策略$\pi'$的采样轨迹来评估策略$\pi$，仅需对累计奖赏加权

$p_i^{\pi}$和$p_i^{\pi'}$分别表示两个策略产生第$i$条轨迹的概率

增量蒙特卡诺更新

• 对于状态-动作对$(s, a)$，假设基于$t$个采样已经估计出$Q^{\pi}_t(s,a) = \frac{1}{t}\sum_{i=1}^tG_i$

• 则在得到第$t+1$个采样时，有

  $$Q^{\pi}_{t+1}(s,a) =Q^{\pi}_t(s,a) + \frac{1}{t+1}(G_{t+1} - Q^{\pi}_t(s, a))$$

• 更一般地，可以把$\frac{1}{t+1}$更换为系数$\alpha$

  $$Q^{\pi}_{t+1}(s,a) = Q^{\pi}_t(s, a) + \alpha (G_{t+1} - Q_t^{\pi}(s, a))$$

注：蒙特卡洛强化学习通过考虑采样轨迹，克服了模型未知给策略估计造成的困难

蒙特卡洛强化学习的缺点：低效

• 求平均时以“批处理式”进行
• 在一个完整的采样轨迹完成后才对状态-动作值函数进行更新

2. 时序差分（temporal difference, TD）学习

开车从北京到上海，出发前模型预测总车程为14小时，即$\hat{q} =14$，到达上海发现实际用时是16小时。基于两者之差去更新模型，让模型预测更准。

• 假设我经过4.5小时到达济南，模型再次预测，发现济南到上海只需要11小时

  $$\hat{y} = r + \hat{q}' = 4.5 + 11 = 15.5$$

  TD 算法将$\hat{y} = 15.5$称为TD目标，它比最初的预测$\hat{q} = 14$更可靠。

其中$s'$是前一次在状态$s$处执行动作$a$后转移到的状态，$a'$是策略$\pi$在$s'$选择的动作

SARSA（on-policy）

学习与执行的是同一个策略

• 对于当前策略执行的每个（状态-动作-奖励-状态-动作）元组

• 更新状态-动作值函数为

  $$Q(s,a) \leftarrow Q(s,a) + a(r_{sa}(s') + \gamma Q(s', a') - Q(s,a))$$

两个actions都是由当前策略选择的。

Q-Learning

SARSA适用于需要安全探索的情形，学习的是实际执行策略的结果，不会高估风险状态。

Q-learning的目标是尽快找到最优策略，对学习稳定性要求低，适用于游戏AI。