Henry Zha Field Notes

第一章：基础知识与习题

《深度强化学习》课后习题解答与强化学习数学基础（MDP、Monte Carlo、回报、价值函数等）。

课后习题解答

  • 第一章习题：1、A；2、B；3、C；4、B；5、1
  • 第二章习题：
    1. 13.6
    2. 按一元正态分布采样 f(x)f(x) 求均值
    3. 构造随机变量 Zi=4f(Xi,Yi)−πZ_i = 4 f(X_i, Y_i) - \pi，易知其满足 Bernstein 概率不等式条件，可得： P(∣1n∑i=1n4f(Xi,Yi)−π∣≥ϵ)≤exp⁡(−ϵ2n/24π−π2+ϵπ/3)\mathbb{P}\left(\left|\frac{1}{n} \sum_{i=1}^n 4f(X_i, Y_i) - \pi \right| \geq \epsilon \right) \leq \exp{\left(-\frac{\epsilon^2 n /2}{4\pi - \pi^2+\epsilon \pi /3}\right)} 令 ϵ=Cn\epsilon = \frac{C}{\sqrt n}，则右式为 exp⁡(−C2/2v+Cb/(3n))\exp{\left(-\frac{C^2/2}{v+Cb/(3\sqrt n)}\right)}，当 n→∞n\to \infty 时概率上界为 exp⁡(−C22v)\exp{\left( -\frac{C^2}{2v}\right)}。则对任意小的概率 δ\delta，选取 C=−2vln⁡δC = \sqrt{-2v\ln \delta} 可以使得 ∣qn−π∣\lvert q_n -\pi \rvert 大于 Cn\frac{C}{\sqrt n} 的概率不超过 δ\delta，即为原题定理。
    4. n=1n=1 时成立，假设 n=i−1n=i-1 时亦成立： qn=(1−1n)⋅qn−1+1n⋅f(xn)=n−1n⋅1n−1∑i=1n−1f(xi)+1n⋅f(xn)=1n∑i=1nf(xi)q_n = \left(1-\frac{1}{n}\right)\cdot q_{n-1} + \frac{1}{n}\cdot f(x_n)=\frac{n-1}{n} \cdot \frac{1}{n-1}\sum_{i=1}^{n-1}f(x_i)+\frac{1}{n}\cdot f(x_n)=\frac{1}{n}\sum_{i=1}^n f(x_i)
  • 第三章习题：1、C；2、D；3、B；4、E
  • 第四章习题：1、B；2、A；3、A；4、789，下；5、18，2；6、B，A；7、A
  • 第五章习题：
    1. A
    2. 因为每一步都会利用策略函数 π\pi 采样得到 aa 后计算 TD 目标
    3. 因为更接近无偏估计 utu_t
  • 第六章习题：1、A；2、B；3、B；4、B；5、B；6、A；7、C；8、B，C；9、A；10、A；11、ABCDEJ
  • 第七章习题：1、1；2、因为合为一的正数；3、B；4、C；5、随机梯度的近似、动作价值函数的近似；6、A
  • 第八章习题：1、B；2、B
  • 第十一章习题：1、ABD；2、d2×(d1+d2+1)d_2 \times (d_1 + d_2 + 1)
  • 第十三章习题：1、5；2、A；3、A；4、B
  • 第十五章习题：
    1. 推导如下： ∇θiJ(θ1,⋯ ,θm)=ES,A[(Qπ(S,A)−b)⋅∇θiln⁡π(A∣S;θ1,⋯ ,θm)]=ES,A[(Qπ(S,A)−b)⋅∇θi(ln⁡π(A1∣S;θ1)+⋯+ln⁡π(Am∣S;θm))]=ES,A[(Qπ(S,A)−b)⋅∇θiln⁡π(Ai∣S;θi)]\begin{aligned} \nabla_{\theta^i} J(\theta^1, \cdots, \theta^m) & = \mathbb{E}_{S,A}\Big[\big(Q_{\pi}(S,A) - b \big) \cdot \nabla_{\theta^i} \ln \pi(A\mid S;\theta^1,\cdots, \theta^m) \Big] \\ & = \mathbb{E}_{S,A}\Big[\big(Q_{\pi}(S,A) - b \big) \cdot \nabla_{\theta^i} \big( \ln \pi(A^1 \mid S;\theta^1) + \cdots + \ln \pi (A^m \mid S;\theta^m) \big) \Big] \\ & = \mathbb{E}_{S,A}\Big[\big(Q_{\pi}(S,A) - b \big) \cdot \nabla_{\theta^i} \ln \pi(A^i \mid S;\theta^i) \Big] \end{aligned}
  • 第十八章习题：1、A；2、C

基础知识

实际训练神经网络的时候，总是用 SGD（及其变体）而不用 GD。主要原因是 GD 用于非凸问题会陷在鞍点（saddle point），收敛不到局部最优；而 SGD 和小批量（mini-batch）SGD 可以跳出鞍点，趋近局部最优。另外，GD 每一步的计算量都很大，比 SGD 大 nn 倍，所以 GD 通常很慢（除非用并行计算）。

设 XX 是 dd 维随机变量，它的取值范围是集合 Ω⊂Rd\Omega \subset \mathbb{R}^d。函数 p(x)p(x) 是 XX 的概率密度函数，设 f:Ω↦Rf: \Omega \mapsto \mathbb{R} 是任意的多元函数，它关于变量 XX 的期望是：

EX∼p(⋅)[f(X)]=∫Ωp(x)⋅f(x)dx\mathbb{E}_{X \sim p(\cdot)}[f(X)] = \int_{\Omega} p(x)\cdot f(x) \mathrm{d} x

可以在集合 Ω\Omega 上均匀采样利用蒙特卡洛计算其定积分，但收敛速度较慢。可以按照概率 p(x)p(x) 进行非均匀采样，记作 x1,⋯ ,xn∼p(⋅)x_1, \cdots, x_n \sim p(\cdot)，并对函数值 f(x1),⋯ ,f(xn)f(x_1),\cdots, f(x_n) 求平均 qnq_n 作为期望 EX∼p(⋅)[f(X)]\mathbb{E}_{X \sim p(\cdot)}[f(X)] 的估计值。

如果按照该方式进行采样需要存储 nn 个函数值占用内存，可以初始化 q=0q=0，从 t=1t=1 到 nn，依次计算：

qt=(1−1t)⋅qt−1+1t⋅f(xt)q_t = \left(1- \frac{1}{t}\right) \cdot q_{t-1} + \frac{1}{t} \cdot f(x_t)

易证这样得到的 qnq_n 等于 1n∑i=1nf(xi)\frac{1}{n}\sum_{i=1}^n f(x_i)。可以进一步把上式中的 1t\frac{1}{t} 替换为 αt\alpha_t，得到公式：

qt=(1−αt)⋅qt−1+αt⋅f(xt)q_t = (1-\alpha_t)\cdot q_{t-1} + \alpha_t\cdot f(x_t)

这个公式叫做 Robbins-Monro 算法，其中 αn\alpha_n 称为学习步长或学习率，只要 αt\alpha_t 满足下面的性质，就能保证算法的正确性：

lim⁡n→∞∑t=1nαt=∞,lim⁡n→∞∑t=1nαt2<∞\lim_{n\to \infty} \sum_{t=1}^n \alpha_t = \infty, \quad \lim_{n\to \infty} \sum_{t=1}^n \alpha_t^2 < \infty

我们可以用蒙特卡洛近似期望来理解随机梯度算法，神经网络的训练可以定义为如下优化问题：

min⁡ωEX∼p(⋅)[L(X;ω)]\min_{\omega} \mathbb{E}_{X\sim p(\cdot)}[L(X;\omega)]

目标函数 EX[L(X;ω)]\mathbb{E}_X[L(X;\omega)] 关于 ω\omega 的梯度是（微分算子和积分算子的交换顺序需满足一定条件）：

g≜∇ωEX∼p(⋅)[L(X;ω)]=EX∼p(⋅)[∇ωL(X;ω)]g \triangleq \nabla_{\omega} \mathbb{E}_{X\sim p(\cdot)} [L(X;\omega)]=\mathbb{E}_{X\sim p(\cdot)} [\nabla_{\omega} L(X;\omega)]

直接计算梯度 gg 通常会比较慢，为了加速计算，可以对期望做蒙特卡洛近似，把得到的近似梯度 g~\tilde{g} 称作随机梯度（stochastic gradient），用 g~\tilde{g} 代替 gg 来更新 ω\omega。因为 E[g~]=g\mathbb{E}[\tilde{g}] = g，它是 gg 的一个无偏估计。

在实际应用中，样本真实的概率密度函数 p(x)p(x) 一般是未知的，在训练神经网络时，我们通常会收集一个训练数据集 X={x1,⋯ ,xn}\mathcal{X} =\{x_1, \cdots, x_n\}，并求解经验风险最小化问题：

min⁡ω1n∑i=1nL(xi;ω)\min_{\omega} \frac{1}{n} \sum_{i=1}^n L(x_i; \omega)

这相当于用下面这个概率质量函数代替真实的 p(x)p(x)：

p(x)={1n,if x∈X0,if x∉Xp(x) = \left\{ \begin{aligned} \frac{1}{n}, & \quad \text{if } x\in \mathcal{X} \\ 0, & \quad \text{if } x \notin \mathcal{X} \end{aligned} \right.

马尔可夫决策过程 (MDP)

强化学习的数学基础和建模工具是马尔可夫决策过程（Markov decision process，MDP）。一个 MDP 通常由状态空间 S\mathcal{S}、动作空间 A\mathcal{A}、状态转移函数 pp、奖励函数 rr 和折扣因子 γ\gamma 等组成。

思考与讨论
书中提到“知道这局游戏的历史记录（即每一步是怎么走的），并不会给你提供额外的信息”，但是对手的风格也是重要信息，AlphaGo 只利用前六步信息，是出于计算量的考虑还是信息和误差的考量？

通常假设奖励是当前状态 ss、当前动作 aa、下一时刻状态 s′s' 的函数，把奖励函数记作 r(s,a,s′)r(s,a,s')。有时假设奖励仅仅是 ss 和 aa 的函数，记作 r(s,a)r(s,a)。我们总是假设奖励函数是有界的，即对于所有 a∈Aa \in \mathcal{A} 和 s,s′∈Ss, s' \in \mathcal{S}，有 ∣r(s,a,s′)∣<∞\lvert r(s,a,s') \rvert < \infty。

状态转移概率函数（state transition probability function）通常假设为平稳的，即不随着时刻 tt 变化：

pt(s′∣s,a)=P(St+1′=s′∣St=s,At=a)p_t(s' \mid s, a) = \mathbb{P}(S_{t+1}'=s' \mid S_t =s, A_t=a)

轨迹 (trajectory) 是指一回合（episode）游戏中，智能体观测到的所有的状态、动作、奖励：

s1,a1,r1,s2,a2,r2,s3,a3,r3,⋯s_1, a_1, r_1, \quad s_2, a_2, r_2, \quad s_3, a_3, r_3, \cdots

回报 (return) 是从当前时刻开始到本回合结束的所有奖励的总和，所以回报也叫做累计奖励（cumulative future reward）。使用折扣回报（discounted return）作为折扣后的总奖励：

Ut=Rt+γ⋅Rt+1+γ2⋅Rt+2+γ3⋅Rt+3+⋯U_t = R_t + \gamma \cdot R_{t+1} + \gamma^2 \cdot R_{t+2}+ \gamma^3 \cdot R_{t+3} + \cdots

MDP 的时间步可以是有限期（finite-horizon）或无限期（infinite-horizon）。有限期 MDP 存在一个终止状态（terminal state），该状态被智能体触发后，一个回合（episode）结束。与之对应的是无限期 MDP，即环境中不存在终止状态，在折扣率 γ≥1\gamma \geq 1 时会导致回报趋于无穷。

假设对于所有的 s∈Ss\in \mathcal{S} 和 a∈Aa\in \mathcal{A}，回报函数有界 ∣r(s,a)∣<b\lvert r(s,a)\rvert < b，那么对于 γ∈[0,1)\gamma \in [0,1)，且 r(s,a)r(s,a)，有这样的性质：

∣lim⁡n→∞∑i=tnγi−tri∣≤b1−γ\left| \lim_{n \to \infty} \sum_{i=t}^n \gamma^{i-t} r_i \right| \leq \frac{b}{1-\gamma}

价值函数

假设观测到状态 sts_t，选中动作 ata_t，则回报 UtU_t 关于随机变量求条件期望，得到：

Qπ(st,at)=ESt+1,At+1,⋯ ,Sn,An[Ut∣St=st,At=at]Q_{\pi}(s_t, a_t) = \mathbb{E}_{S_{t+1},A_{t+1},\cdots, S_n,A_n}[U_t \mid S_t =s_t, A_t = a_t]

条件期望的结果 Qπ(st,at)Q_{\pi}(s_t, a_t) 被称作动作价值函数（action-value function），更准确地说应该是动作状态价值函数。

为了排除掉策略 π\pi 的影响，只评价当前状态和动作的好坏，可以利用最优动作价值函数（optimal action-value function）：

Q∗(st,at)=max⁡πQπ(st,at),∀st∈S,at∈AQ_*(s_t, a_t) = \max_{\pi} Q_{\pi}(s_t, a_t), \quad \forall s_t \in \mathcal{S}, a_t \in \mathcal{A}

如果只想知道当前状态 sts_t 是否对自己有利，可以利用状态价值函数（state-value function）：

Vπ(st)=EAt∼π(⋅∣st)[Qπ(st,At)]=∑a∈Aπ(a∣st)⋅Qπ(st,a)V_{\pi}(s_t) =\mathbb{E}_{A_t \sim \pi(\cdot \mid s_t)} [Q_{\pi}(s_t, A_t)] = \sum_{a \in \mathcal{A}} \pi(a\mid s_t) \cdot Q_{\pi}(s_t, a)

状态价值函数 Vπ(st)V_{\pi}(s_t) 也是回报 UtU_t 的期望：

Vπ(st)=EAt,St+1,At+1,⋯ ,Sn,An[Ut∣St=st]V_{\pi}(s_t) = \mathbb{E}_{A_t, S_{t+1}, A_{t+1},\cdots, S_n, A_n} [U_t \mid S_t = s_t]