强化学习 Reinforcement Learning

强化学习是一种机器学习思想，其关心一个智能体如何采取行动以达到最大化激励回报。

基本的强化学习模型以马尔可夫决策过程建模。

马尔可夫决策过程 Markov Decision Process

系统要素

A 行动空间；
S状态空间；
\(P^a_{s's}=\mathbb{P}(S_{t+1}=s'|S_t=s, A_t=a)\) 状态转移函数（给定t时刻的状态和动作，t+1时刻的状态分布），在t时刻给定状态为s,动作为a，t+1时刻状态转移为s'的概率;
\(R_a(s',s)\) 即刻奖励函数，给定动作a，状态由s转移到s'所获得的即刻奖励（immediate reward）。

有时还包括衰减系数 \(\gamma\) ，值域[0,1]，t时刻的价值函数被定义为对未来奖励的指数衰减加权和：

\[G_t=\sum_{k=0}^{\infty} \gamma^{k}r_{t+k}=r_t + \gamma r_{t+1} +\gamma^2 r_{t+2} +\cdots \]

，其中 \(r_t\) 是t时刻的即刻奖励。

关键概念

代理/智能体 Agent / intelligent agent

在环境中行动的虚拟代理，执行行为动作根据模型中的“策略”而定。

策略 Policy

策略，是根据环境的当前状态表明不同动作的概率。

\[\pi: A\times S \mapsto [0,1] \\ \pi(a,s)=\mathbb{P}(A_t=a|S_t=s) \]

奖励函数 Reward

状态价值函数 state value function

在一个给定策略 \(\pi\) 下，（在某个时刻）状态s的价值函数被定义为以s作为初始状态，以策略 \(\pi\) 推演出的收益G的期望。

\[V_\pi(s)=\mathbb{E}_{\tau\sim \mathbb{P}_\pi}\left[G|s_0=s; \pi\right]=\mathbb{E}_{\tau\sim \mathbb{P}_\pi}\left[\sum_{t=0}^{\infty}\gamma^t r_t(s,a) \bigg| s_0=s ; \pi\right] \]

，其中收益G是从此刻起未来所有即刻奖励的指数衰减加权和（discounted reward）（G之所以是随机变量是因策略 \(\pi\) 是随机过程，导致依赖于此的收益R也是随机变量）:

\[G=\sum_{k=0}^{\infty} \gamma^k r_k \\ \begin{aligned} G_t &=\sum_{k=0}^{\infty}\gamma^k r_{t+k}=\sum_{k=0}^{\infty} \gamma^{k}r_{t+k}=r_t + \gamma r_{t+1} +\gamma^2 r_{t+2} +\cdots \\ &= r_{t+1}+\gamma G_{t+1} \end{aligned} \]

，其中 \(r_k\) 是相对R所处时刻(t)的未来第k个偏移时刻（即t+k时刻）的即刻奖励。

行动-状态价值函数 state-action pair value function

\[Q_\pi (s, a)=\mathbb{E}_{\tau\sim \pi}\left[G| s_0=s, a_0=a; \pi \right] \]

优势函数 Advantage Function

行动价值与状态价值之差：

\[A_\pi(s,a) =Q_\pi (s,a) - V_\pi(s) \]

记号 \(A\) 在某些情况下存在歧义，可能值优势函数，也可能指行动（Action）。

Average Reward

累积奖励函数（策略优化目标函数）上的基本思想是：累积奖励是未来所有时刻奖励的平均和。

平均奖励函数：

\[G(\pi):=\lim_{N\to \infty}\mathbb{E}_{\tau\sim \mathbb{P}_\pi}\left[ \frac{1}{N} \sum_{t=0}^{N-1} r(s_t,a_t)\right]=\mathbb{E}_{s\sim d_\pi \atop a\sim\pi}[r(s,a)] \\ \\ V_\pi(s):=\mathbb{E}_{\tau\sim\mathbb{P}_\pi}\left[\sum_{t=0}^{\infty}(r(s_t,a_t)-\rho(\pi)) \bigg| s_0=s\right] \\ \\ Q_\pi(s,a):=\mathbb{E}_{\tau\sim\mathbb{P}_\pi}\left[\sum_{t=0}^{\infty}(r(s_t,a_t)-\rho(\pi)) \bigg| s_0=s, a_0=a\right] \\ \\ A_\pi(s,a) := Q_\pi(s,a)-V_\pi(s) \]

其中 \(d_\pi(s):=\lim_{N\to \infty} \frac{1}{N}\sum_{t=0}^{N-1}\mathbb{P}(s_t=s|\pi)=\lim_{t\to \infty}\mathbb{P}(s_t=s|\pi)\) 是策略 \(\pi\) 下状态的平稳分布。 \(\tau=(s_0, a_0, s_1, a_1,\dots)\) 是轨迹（关于行动-状态对的时序）， \(\tau \sim \mathbb{P}_\pi\) 表示从策略 \(\pi\) 采样出的轨迹， \(s_0\sim \mathbb{P}, a_0\sim \pi(\cdot|s_0), a_t\sim \pi(\cdot|s_t), s_{t+1}\sim\mathbb{P}(\cdot|a_t, s_t)\) 。

Discounted Reward

累积奖励函数（策略优化目标函数）上的基本思想是：越远的未来时刻的预估奖励对当前策略优化影响越小（对预估累积奖励贡献越小）。

\(\gamma\in(0,1)\) , 衰减加权奖励函数：

\[G_\gamma(\pi):= \mathbb{E}_{\tau\sim \mathbb{P}_\pi}\left[\sum_{t=0}^\infty r(s_t,a_t)\right]=\frac{1}{1-\gamma}\mathbb{E}_{s\sim d_{\pi, \gamma}\atop a\sim \pi}\left[r(s,a)\right] \\ \begin{aligned} V_{\pi,\gamma}(s) & :=\mathbb{E}_{\tau\sim\mathbb{P}_\pi}\left[\sum_{t=0}^\infty \gamma^t r(s_t,a_t)\bigg| s_0=s \right] \\ &= \mathbb{E}_{a\sim\pi(\cdot|s)}\left[Q_{\pi,\gamma}(s,a)\right]=\sum_{a\in \mathcal{A}}\pi(a|s)Q_{\pi,\gamma}(s,a) \end{aligned} \\ Q_{\pi,\gamma} (s,a):=\mathbb{E}_{\tau\sim\mathbb{P}_\pi}\left[\sum_{t=0}^\infty \gamma^t r(s_t,a_t)\bigg| s_0=s, a_0=a \right] \\ A_{\pi, \gamma}=Q_{\pi, \gamma}(s,a)-V_{\pi, \gamma}(s) \]

Discounted Reward 与 Average Reward的关系：
当 \(\gamma\to 1\) 时， \(\rho_{\pi,\gamma}\to \rho(\pi)\) ，即Average Reward可以认为是Discounted Reward思想在 \(\gamma=1\) 时的特殊情况。

Disounted Reward的另一种特殊情况 \(\gamma=0\) ，相当于不利用未来奖励信息，仅用当前的。

References:

https://openreview.net/references/pdf?id=ChHAhiBSMN

策略类型 on-policy / off-policy

策略梯度 Policy Gradient

策略梯度是解决强化学习中梯度计算困难的一种方法。

\[\begin{aligned} \nabla_\theta J(\theta) &:= \nabla_\theta \sum_{s\in S}d_\pi(s) \sum_{a\in A}Q_\pi(s,a) \pi_\theta (a|s) \\ &=\nabla_\theta \mathbb{E}_{s\sim d_\pi \atop a\sim \pi} \left[ Q_\pi(s,a) \right] = \nabla_\theta \mathbb{E}_{s\sim d_\pi} \left[V_\pi(s)\right] \\ &\propto \sum_{s\in S}d_\pi(s) \sum_{a\in A}Q_\pi(s,a) \nabla_\theta \pi_\theta (a|s) \\ &= \sum_{s\in S}d_\pi(s) \sum_{a\in A}Q_\pi(s,a)\pi_\theta(a|s) \nabla_\theta \ln \pi_\theta (a|s) \\ &= \mathbb{E}_{s\sim d_\pi \atop a\sim \pi}[\nabla_\theta \ln \pi_\theta(a|s)] \\ &= \mathbb{E_{\tau\sim\mathbb{P}_\pi}} [G_t\nabla_\theta \ln \pi_\theta(a_t|s_t)] = \mathbb{E_{\tau\sim\mathbb{P}_\pi}} \left[G_t \frac{\nabla_\theta \pi_\theta(a_t|s_t)}{\pi_\theta(a_t|s_t)}\right] \end{aligned} \]

上述“正比于（ \(\propto\) ）”的证明详见书籍 Sutton&Barto 2020, Reinforcement Learning: An Introduction。

梯度更新策略（由于要最大化而非最小化目标函数，故应采用梯度上升而非下降）：

\[\theta_{t+1} \leftarrow \theta_t + \alpha G_t \frac{\nabla_\theta \pi_\theta(a_t|s_t)}{\pi_\theta(a_t|s_t)} \]

，其中 \(\alpha\) 为学习率。

时常会使用一个变体，其在 \(G_t\) 上减去一个基线值，以减少梯度估计的方差。

Q-Learning

函数Q并非已知计算式，而是用学习的方式来拟合。

Deep Q-learning Network, DQN

用深度神经网络学习Q函数。

GAE, Generalized Avantage Estimator

被用于策略梯度。

\[\hat A^{GAE(\gamma, \lambda)} := \sum_{k=0}^\infty (\gamma\lambda)^k \delta_{t+k}^V = \sum_{k=0}^\infty (\gamma\lambda)^k (r_{t+k} + V(s_{t+k+1})- V(s_{t+k})) \]

具有性质：
*

References: