强化学习的数学基础

基本概念

强化学习的基础概名词

• 状态(State)：表示当下环境，是做决策的唯一依据

• 动作(Action)：做出的决策，动作种数一般用$i$表示

• 环境(Environment)：使智能体不断变换状态的位置

• 智能体(Agent)：动作主体

• 奖励(Reward)：智能体执行一个动作后返回的具体数值，由实验者定义

• 状态空间(State Space)：所有状态集合，表示为$\mathcal{S}$

• 动作空间(Action Space)：动作的集合，表示为$\mathcal{A}$

• 策略函数(Policy Function)：根据观测到的状态作决策控制智能体动作，记为$\pi(a \| s)=P(A=a \| S=s),\pi:\mathcal{S} \times \mathcal{A} \to [0,1]$

• 状态转移(State Transition)：指由当前状态$s$变为$s'$的过程，该过程执行动作$a$

• 状态转移函数(State-Transition Function)：产生新状态$s'$时用到的函数，可以是确定或随机的，如随机状态转移函数记为$p(s' \| s,a)=\mathbb{P}(S'=s' \| S=s,A=a)$

• 智能体与环境交互 (Agent Environment Interaction)：是上述所有参量组成的一整个循环系统

  

强化学习中的回报(Return)

整个流程下来的奖励综合就叫回报(Return)，而汇报依赖于(i) 观测到的不具随机性数值 (ii) 未观测到的具随机性的数值；随着时间的滞后奖励会乘以逐渐变小的折扣率(Discount Factor)，表示为折扣回报 (Discounted Return)：

$U_t=\sum\limits_{i=0}^{n} \gamma^{i} \cdot R_{t+i},\gamma \in [0,1]$

价值函数——回报的期望

由于在整个流程结束前，都无法获取$U_t$的实际值，因此需要对$U_t$求期望从而尽可能消除其中的随机性；考虑到这种随机性来源于未来，因此可以求得条件期望如下：

$$Q_{\pi}(s_t,a_t)=\mathbb{E}_{\{S_{t+i},A_{t+i} \| i=1,2,\cdots\}}\left[ \begin{matrix} U_{t} \| S_t=s_t,A_t=a_t \end{matrix} \right]$$ $$=\int \cdots \int P(\{S_{t+i},A_{t+i} \| i=1,2,\cdots\} \| s_t,a_t) \cdot U_t ds_{t+1}da_{t+1} \cdots ds_{t+n}da_{t+n}$$ $$=\int_{\mathcal{S}}ds_{t+1} \int_{\mathcal{S}}da_{t+1}\cdots \int_{\mathcal{S}}ds_{t+n} \int_{\mathcal{S}}da_{t+n}\left( \begin{matrix} \Pi_{k=t+1}^{n}p(s_k \| s_{k-1},a_{k-1}) \cdot \pi(a_k \| s_k) \end{matrix} \right) \cdot U_t$$

根据公式可得，$Q_{\pi}(s_t,a_t)$依赖的三个因素：

• 当前状态$s_t$越好，$Q_{\pi}(s_t,a_t)$越大，回报期望值越大
• 当前动作$a_t$越好，$Q_{\pi}(s_t,a_t)$越大，回报期望值越大
• 策略函数$\pi$越好，$Q_{\pi}(s_t,a_t)$越大，回报期望值越大

其中最优动作价值函数能排除策略的影响，通俗理解为其作为一个先知执行尽量高收益的动作；表示为：

$$Q_{\ast} (s_t,a_t)=\max_{\pi} \ Q_{\pi} (s_t,a_t) \to \pi * =arg \max_{\pi} \ Q_{\pi} (s_t,a_t)$$

状态价值函数则用于量化双方胜算，表示为：

$$V_{\pi}(s_t)=\mathbb{E}_{A_t \sim \pi(\cdot \| s_t)} \left[ \begin{matrix} Q_{\pi}(s_t,A_t) \end{matrix} \right] = \sum\limits_{a \in \mathcal{A}}\pi(a \| s_t) \cdot Q_{\pi}(s_t,a)=\mathbb{E}_{A_t,S_{t+1},A_{t+1},\cdots,S_{n},A_{n}} \left[ \begin{matrix} U_{t} \| S_t=s_t \end{matrix} \right]$$

强化学习过程中随机性的来源

基于当前状态$s$，考虑策略函数的随机性产生新动作；基于新动作和当前状态，考虑状态转移函数的随机性，产生新状态；基于新状态的随机性进而产生新奖励，该奖励也是随机的；从而形成一整条随机的轨迹(Trajectory)，完整简洁的数学表达如下：

$$Trajectory:s_t \stackrel{\pi(\cdot \| s_t)}{\longrightarrow} a_t \stackrel{p(\cdot \| s_t,a_t)}{\longrightarrow} s_{t+1},r_t \to \cdots$$

回报过程中其实也具有随机性，即在一定状态之后的部分是未知的，因此其状态和动作也都是未知的

策略学习与价值学习

强化学习方法主要分为两类：一类是基于模型的方法(Model-Based)，另一类是无模型方法(Model-Free)；无模型方法又可以分为价值学习和策略学习。

**价值学习(Value-Based Learning)**指学习最优价值函数$Q_{\ast}(s,a)$，使智能体通过$Q_{\ast}$做决策选出最好的动作，即每观测到一个状态$s_t$，把其输入至$Q_{\ast}$函数，让$Q_{\ast}$对所有动作做评价，选出得到最优评价的动作；该过程用公式表示为：

$$a_t=arg \max_{a \in \mathcal{A}} Q_{\ast}(s_t,a)$$

**策略学习(Policy-Based Learn)**指学习策略函数$\pi(a \| s)$；即将观测状态$s_t$输入到$\pi$函数中，让其对所有动作作评价，进而得到概率值$\pi(* \| s_t)$；然后智能体作随机抽样，执行选中动作

价值学习

DQN网络

DQN网络基本概念

构造DQN网络的目的是通过重复训练得到最优价值函数$Q_{\ast}$，其的逼近记为$Q(s,a;\bf{w})$，其中$w$为神经网络参数；在训练DQN时则需要对$w$求参数，具体表达为：

$$\bigtriangledown_w Q(s,a;{\bf{w}})=\frac{\partial Q(s,a;{\bf{w}})}{\partial {\bf{w}}}$$

DQN训练方法：时间差分算法(Temporal Difference)

DQN的基本流程

• 步骤一：确定起始点$s$和终止点$d$，随机取$\bf{w}$作预测$\hat{q}=Q(s,a;{\bf{w}})$

• 步骤二：统计实际值$y$，然后利用预测值和实际值求导：

  $${\bf{w}}'={\bf{w}}-\alpha \cdot \bigtriangledown_w L({\bf{w}})={\bf{w}}-\alpha \cdot (\hat{q}-y)\bigtriangledown_w Q(s,d;{\bf{w}}),L({\bf{w}})=\frac{1}{2} \left[\begin{matrix}Q(s,d;{\bf{w}})-y\end{matrix}\right]^2$$

• 步骤三：重复该过程至预测与实际用时一致

在实际过程中途，可以对预测作修正，得到TD目标(TD Targe)记为$\hat{y}$；将$\hat{y}$取代上式的$y$，记TD误差(TD error)$\delta=\hat{q}-\hat{y}$；进一步不断更新参数即可

利用TD训练DQN

由定义得回报的计算公式为：

$$U_t=\sum\limits_{k=t}^{n}\gamma^{k-t} \cdot R_k=R_t+U_{t+1}=R_t+\sum\limits_{k=t+1}^{n}\gamma^{k-t-1} \cdot R_k$$

最优价值函数写作：

$$Q_{\ast}(s_t,a_t)=\max_{\pi} \mathbb{E} \left[ \begin{matrix} U_{t} \| S_t=s_t,A_t=a_t \end{matrix} \right]$$

从上述两式可推导出最优贝尔曼方程：

$$\underbrace{Q_{\ast}(s_t,a_t)}_{U_t的期望}=\mathbb{E}_{S_{t+1} \sim p(\cdot \| s_t,a_t)} [R_t + \gamma \cdot \underbrace{\max\limits_{A \in \mathcal{A}} Q_{\ast}(S_{t+1},A)}_{U_{t+1}的期望}\| S_t=s_t,A_t=a_t ]$$

当智能体执行动作$a_t$，则可以利用$p(s_{t+1} \| s_t,a_t)$ 计算出$s_{t+1}$ ，使得$s_t,a_t,s_{t+1}$ 都被观测到；进而观测到$r_t$，从而拥有四元组$(s_T,a_t,r_t,s_{t+1})$，进而计算出$r_t+\max\limits_{a \in \mathcal{A}} \gamma \cdot Q_{\ast}(s_{t+1},a)$ ，以此看作项${\mathbb{E}}_{S_{t+1} \sim p(\cdot \| s_t,a_t)} [R_t + \gamma \cdot \max\limits_{A \in \mathcal{A}} Q_{\ast}(S_{t+1},A) \| S_t=s_t,A_t=a_t ]$ 的近似；然后$将{Q_{\ast}} (s,a)替换为{Q(s,a;{\bf{w}})}$ 得到：

$\underbrace{Q(s,a;{\bf{w}})}_{预测\hat{q_t}} \approx \underbrace{r_t+\gamma \cdot Q_{\ast}(s_{t+1},a;\bf{w})}_{TD目标\hat{y_t}}$

然后重复DQN基本流程中的步骤即可。

训练流程

根据四元组$(s_T,a_t,r_t,s_{t+1})$ 可以求出DQN的观测值，以及TD目标和TD误差；由于算法所需数据为四元组，与控制智能体运动的策略$\pi$ 无关，因此可以用任何策略控制智能体与环境交互，并记录算法轨迹作为训练数据。因此DQN的训练可以分为两个独立部分：

• 收集训练数据：可以用任何策略$\pi$ 与环境交互，该策略被称作行为策略(Behavior Policy)，常用的是$\epsilon -greedy$策略：

  $a_t=\left\{ \begin{aligned} & arg \max_{a} Q(s,a;{\bf{w}})\ \ \ \ \ \ 以概率(1-\epsilon) \\ & 均匀抽取\mathcal{A}中的一个动作 \ \ \ \ 以概率\epsilon \end{aligned} \right.$

  智能体在整个过程中的轨迹记作$\{ s_i,a_i,r_i \| i=1,2,\cdots,n \}$ ，把一条轨迹划为$n$个四元组$(s_T,a_t,r_t,s_{t+1})$ 存入数组，从而得到经验回放数组(Reply Buffer)

• 更新参数${\bf{w}}$ 随机从经验回放数组中取一个四元组记作$(s_j,a_j,r_j,s_{j+1})$ ，设当前DQN参数为$w_{now}$；执行下面步骤对参数做更新得到新参数$\bf{w}_{new}$ ：

  • 对DQN作正向传播，得到Q值：$\hat{q}_{j}=Q(s_{j},a_{j},{\bf{w}}_{now})和\hat{q}_{j+1}=\max\limits_{a \in \mathcal{A}} Q(s_{j+1},a_{j},{\bf{w}}_{now})$
  • 计算TD目标和TD误差：$\hat{y}_{j}=r_j+\gamma \cdot \hat{q}_{j+1}和\delta=\hat{q}_j-\hat{y}_j$
  • 对DQN作反向传播得到梯度：${\bf{g}}_{j}=\bigtriangledown_{\bf{w}} Q(s_j,a_j;{\bf{w}}_{now})$
  • 做梯度下降更新参数：${\bf{w}}_{now}-\alpha \cdot \delta_j \cdot {\bf{g}}_j \to {\bf{w}}_{new}$

因为两者是独立的；因此训练数据收集和参数更新可以同步进行，也可以异步进行。

利用Q学习算法训练DQN

Q学习最初以表格形式出现，参照表格作出决策；该种情况下$\mathcal{S}$和$\mathcal{A}$为有限集，它们的组合有限；从这些组合中，针对每个状态选择回报最大的动作，从而实现最优决策；数学表示为：

$a_t=arg \max_{a \in \mathcal{A}} Q_{\ast} (s_t,a)$

如果要让智能体的轨迹学习这样一个表格，则可用一个表格$\tilde{Q}$近似$Q_{\ast}$：

• 首先初始化$\tilde{Q}$，如使其为全0的表格
• 然后用表格形式的Q学习算法更新$\tilde{Q}$
• 每次更新表格的一个元素，使其最终收敛到$Q_{\ast}$

训练流程

根据四元组$(s_T,a_t,r_t,s_{t+1})$ 可以求出DQN的观测值，以及TD目标和TD误差；由于算法所需数据为四元组，与控制智能体运动的策略$\pi$ 无关，因此可以用任何策略控制智能体与环境交互，并记录算法轨迹作为训练数据。因此DQN的训练可以分为两个独立部分：

• 收集训练数据：可以用任何策略$\pi$ 与环境交互，该策略被称作行为策略(Behavior Policy)，常用的是$\epsilon -greedy$策略：

  $a_t=\left\{ \begin{aligned} & arg \max_{a} \tilde{Q}(s_{t},a)\ \ \ \ \ \ 以概率(1-\epsilon) \\ & 均匀抽取\mathcal{A}中的一个动作 \ \ \ \ 以概率\epsilon \end{aligned} \right.$

  智能体在整个过程中的轨迹记作$\{ s_i,a_i,r_i \| i=1,2,\cdots,n \}$ ，把一条轨迹划为$n$个四元组$(s_T,a_t,r_t,s_{t+1})$ 存入数组，从而得到经验回放数组(Reply Buffer)；事后通过经验回访更新表格$\tilde{Q}$

• 更新参数${\bf{w}}$ 随机从经验回放数组中取一个四元组记作$(s_j,a_j,r_j,s_{j+1})$ ，设当前DQN参数为$w_{now}$；执行下面步骤对参数做更新得到新参数$\bf{w}_{new}$ ：

  • 对DQN作正向传播，得到Q值：$\hat{q}_{j}=\tilde{Q}_{now} (s_{j},a_{j})和\hat{q}_{j+1}=\max\limits_{a \in \mathcal{A}} \tilde{Q}_{now} (s_{j+1},a)$
  • 计算TD目标和TD误差：$\hat{y}_{j}=r_j+\gamma \cdot \hat{q}_{j+1}和\delta=\hat{q}_j-\hat{y}_j$
  • 更新表格中$(s_{j},a_{j})$ 位置上的元素：$\tilde{Q}_{now} (s_{j},a_{j})-\alpha \cdot \delta_{j} \to \tilde{Q}_{new} (s_{j},a_{j})$

同理，因为两者是独立的;因此训练数据收集和参数更新可以同步进行，也可以异步进行。

同策略(On-policy)与异策略(Off-policy)

行为策略是控制智能体与环境交互的策略，作用是收集经验(即观测的环境、动作、奖励)；目标策略是结束训练后得到的用于控制目标智能体的策略函数，该策略函数暂时作为一个确定性策略，用于控制智能体：

$a_{t}=arg \max_{a} Q(s_{t},a_{t};\bf{w})$

同策略指用相同的行为策略和目标策略，异策略指用不同的行为策略和目标策略；DQN则是经典的异策略，通过经验回放的形式建立目标策略。

SARSA(State-Action-Reward-State-Action)算法

针对强化学习，$Q_{\pi}$常常和策略函数$\pi$结合使用，被称作Actor-Critic方法，而SARSA算法则就是被用来训练该方法$Q_{\pi}$的工具。

SARSA算法的推导

• 首先根据贝尔曼方程可知：

  $Q_{\pi} (s_{t},a_{t})={\mathbb{E}}_{S_{t+1},A_{t+1}} [R_t + \gamma \cdot Q_{\pi}(S_{t+1},A_{t+1}) \| S_t=s_t,A_t=a_t ]$

• 然后对贝尔曼方程左右两边作近似，左边近似为$q(s_{t},a_{t})$，是表格在$t$时刻对$Q_{\pi} (s_{t},a_{t})$做出的估计

• 对于方程右边，给定当前状态$s_{t}$和智能体执行动作$a_{t}$，环境给出奖励$r_{t}$和新状态$s_{t+1}$，然后基于$s_{t+1}$随机采样得到新动作

  $\tilde{a}_{t+1} \sim \pi (cdot \| s_{t+1})$

  进一步作蒙特卡洛近似得到：

  $r_t + \gamma \cdot Q_{\pi}(s_{t+1},\tilde{a}_{t+1})$

• 进一步把上面中公式中的$Q_{\pi}$近似成$q$，得到：

  $\hat{y_{t}} \triangleq r_t + \gamma \cdot q_{\pi}(s_{t+1},\tilde{a}_{t+1})$

  其被称作TD目标，是表格在$t+1$时刻对$Q_{\pi} (s_{t},a_{t})$做出的估计

$q(s_{t},a_{t})$和$\hat{y_{t}}$都是对动作价值$Q_{\pi} (s_{t},a_{t})$的估计，而$\hat{y_{t}}$部分基于真实观测到的奖励$r_{t}$；由于$\hat{y_{t}}$更可靠，因此鼓励$q(s_{t},a_{t})$趋近$\hat{y_{t}}$，即：

$(1-\alpha) \cdot q(s_{t},a_{t}) + \alpha \cdot \hat{y_{t}} \to q(s_{t},a_{t})$

SARSA的训练流程

前提假设：设当前表格为$q_{now}$，当前策略为$\pi_{now}$，每轮更新表格中的一个元素，把更新后的表格记作$q_{new}$

具体步骤

• 步骤一：观测到当前状态$s_{t}$，根据当前策略抽样：$a_{t} \sim \pi_{now} (\cdot \| s_{t})$
• 步骤二：把表格$q_{now}$中第$(s_{t},a_{t})$位置上的元素记为：$\hat{q_{t}}=q_{now}(s_{t},a_{t})$
• 步骤三：智能体执行动作$a_{t}$，观测到奖励$r_{t}$和新状态$s_{t+1}$
• 步骤四：根据当前策略抽样$\tilde{a}_{t+1} \sim \pi_{now} (\cdot \| s_{t})$ ，其中$\tilde{a_{t+1}}$ 为假想动作，智能体不予执行
• 步骤五：记$\hat{q}_{t+1} =q_{now} (s_{t+1}, \tilde{a}_{t+1})$，计算TD目标和TD误差$\hat{y_{t}}=r_{t}+ \gamma \cdot \hat{q}_{t+1},\delta_{t}=\hat{q}_{t}-\hat{y}_{t}$
• 步骤六：更新表格中$(s_{t},a_{t})$位置上的元素：$q_{now} (s_{t},a_{t}) -\alpha \cdot \delta_{t} \to q_{new} (s_{t},a_{t})$

Q学习与SARSA对比

• Q学习属于异策略，可以用经验回放，目标是学到表格$\tilde{Q}$作为$Q_{\ast}$的近似而与$\pi$无关，所以无论$\pi$是什么都不影响Q学习结果
• SARSA属于同策略，不能用经验回放，目标是学到表格$q$作为动作价值函数$Q_{\pi}$的近似吗，必须通过收集当前策略$\pi_{now}$学习$Q_{\pi}$

神经网络形式训练SARSA

若状态空间$\mathcal{S}$为无限集，则无法用表格表示$Q_{\pi}$，而是用神经网络$q(s,a;\bf{w})$近似：

$q(s,a;{\bf{w}})=Q_{\pi}, \forall s \in \mathcal{S},a \in \mathcal{A}$

神经网络的结构被预先设定，参数通过智能体与环境的交互确定

算法推导

给定当前状态$s_{t}$，智能体执行动作$a_{t}$，环境给出奖励$r_{t}$和新状态$s_{t+1}$，然后基于$s_{t+1}$作随机抽样，得到新动作$\tilde{a}_{t+1} \sim \pi (\cdot \| s_{t+1})$，定义TD目标：

$\hat{y}_{t}=r_{t}+ \gamma \cdot q (s_{t+1},\tilde{a}_{t+1};{\bf{w}})$

进而定义损失函数：

$L({\bf{w}}) \triangleq \frac{1}{2} [q(s_{t},a_{t};{\bf{w}})-\hat{y}_{t}]^{2}$

进一步利用梯度下降计算损失函数：

$\bigtriangledown_{\bf{w}} L({\bf{w}})=\underbrace{(\hat{q}_{t}-\hat{y}_{t})}_{TD误差 \delta_{t}} \cdot \bigtriangledown_{\bf{w}} q(s_{t},a_{t};{\bf{w}})$

然后作梯度下降更新：

$w-\alpha \cdot \delta_{t} \cdot \bigtriangledown_{\bf{w}} q(s_{t},a_{t};{\bf{w}})$

利用神经网络训练和上面一节的训练流程类似，只是把相应参数替换为了含$\bf{w}$的内容，此处省略

多步TD目标和蒙特卡洛与自举

多步TD目标实质上就是对贝尔曼方程做了一些修改：

$\underbrace{Q_{\pi} (s_{t},a_{t})}_{U_{t}的期望} = {\mathbb{E}} [(\sum\limits_{i=0}^{m-1} r^{i} R_{t+i}) + \gamma^{m} \cdot \underbrace{Q_{\pi}(S_{t+m},A_{t+m})}_{U_{t+m}的期望} \| S_t=s_t,A_t=a_t ]$

即用策略$\pi$控制智能体与环境交互$m$次得到轨迹后，再作近似得到近似结果；其它内容和传统训练方式差距不大

蒙特卡洛和自举可以看作是多步TD朝两个相反方向的延申。

前者依赖完整经历完一轮交互后的所有显式状态，无偏但方差大；后者仅依赖后一步交互，方差小但有偏差。

价值学习高级技巧

该部分主要包含两个技巧：经验回放(Experience Replay)、高估问题的解决方案

经验回放

概念：把智能体与环境交互的记录(即经验)储存到一个数组里，事后反复利用这些经验训练智能体；该数组被称为经验回放数组(Replay Buffer)，一般智能体轨迹被划分为四元组$(s_{t},a_{t},r_{t},s_{t+1})$，大小为最近保留的$b$条数据(一般被设置为$10^{5} \sim 10^{6}$)；在实践中，要等回放数组中有足够多四元组，才开始经验回放更新DQN。