[广告策略算法系列十七]：强化学习基础
一转眼已经工作三年有余，作为一个勤劳的码农，一直在广告策略领域搬砖。最近有个强烈的想法，想要把广告策略方向涉及到的业务策略算法和技术栈做下梳理，一方面是对以往工作经验的一个回顾，另一方面也是对自我的一个重新认知，可以更好地为未来的进步找好方向。本文是该系列文章的第十七篇，往期文章可参考：[*][广告策略算法系列一]：前言
[*][广告策略算法系列二]：预算分配
[*][广告策略算法系列三]：广告创意优化
[*][广告策略算法系列四]：新广告冷启动优化
[*][广告策略算法系列五]：成本控制策略
[*][广告策略算法系列六]：匀速投放
[*][广告策略算法系列七]：预估校准机制
[*][广告策略算法系列八]：多约束条件下的出价优化
[*][广告策略算法系列九]：多约束条件下的排序公式优化
[*][广告策略算法系列十]：混排策略和算法
[*][广告策略算法系列十一]：联盟RTB策略
[*][广告策略算法系列十二]：浅谈博弈论与经济学的关系
[*][广告策略算法系列十三]：优化问题中的对偶理论
[*][广告策略算法系列十四]：常用预估模型及TF实现
[*][广告策略算法系列十五]：LTR预估
[*][广告策略算法系列十六]：基于上下文感知的重排序算法
欢迎大家通过博客：
和github：
来一起交流。
算法基础
专业术语
[*]state：状态
[*]action：动作
[*]policy：\pi(a|s)，指给定状态s下采取动作a的概率
[*]reward：奖励
[*]state transition：状态转移
[*]return：累积未来奖励，cumulative future reward
[*]discounted return：折扣回报，未来奖励权重应小于当前奖励权重
U_{t}=R_{t}+\gamma R_{t+1} + \gamma^{2}R_{t+1} + ... \\
[*]Action-Value Function，它表示在状态s_{t}下执行动作a_{t}的折扣回报期望
Q_{\pi}(s_{t},a_{t})=E \\
[*]Optimal Action-Value Function，它表示Action-Value Function对policy求最大化
Q^{*}(s_{t},a_{t})=\max_{\pi} Q_{\pi}(s_{t},a_{t}) \\
[*]State-Value Function，状态价值评估函数，它是Action-Value Function对action求期望
V_{\pi}(S_{t})=E_{A} \\
Value-Base Reinforcement Learning
什么是TD(Temporal Difference Learning)算法？
DQN算法思想
用神经网络Q(s, a;w)来近似Optimal Difference Learning，使用TD算法来进行模型训练：
1.观察状态S_{t}=s_{t}，以及动作A_{t}=a_{t}
2.预估：q_{t}=Q_{t}(s_{t}, a_{t};w_{t})
3.对价值网络求导：
d_{t}=\frac{\partial Q(s_{t},a_{t};w_{t})}{\partial w}|_{w=w_{t}}\\
4.得到新状态s_{t+1}和reward r_{t}
5.计算TD target:
y_{t}=r_{t}+\gamma*q(s_{t+1},a_{t+1};w_{t}) \\
5.梯度下降更新参数：
w_{t+1}=w_{t}-\partial *(q_{t}-y_{t})*d_{t} \\
Policy-Base Reinforcement Learning
算法思想： 使用神经网络\pi(a|s;\theta)来近似policy \pi(a|s)
V_{\pi}(s)=\sum_{a}\pi(a|s)*Q_{\pi}(s,a) \\
Policy-Gradient计算：
\begin{aligned} \frac{\partial V(s|\theta)}{\partial \theta} &= \frac{\partial \sum_{a}\pi(a|s;\theta)*Q_{\pi}(s,a)}{\partial \theta} \\ &=\sum_{a}\frac{\partial \pi(a|s;\theta)*Q_{\pi}(s,a)}{\partial \theta} \\ &=\sum_{a}\frac{\partial \pi(a|s;\theta)}{\partial \theta}*Q_{\pi}(s,a) \\ &=\sum_{a}\pi(a|s;\theta)*\frac{\partial log\pi(a|s;\theta)}{\partial \theta}*Q_{\pi}(s,a) \\ &=E_{A}[\frac{\partial log\pi(a|s;\theta)}{\partial \theta}*Q_{\pi}(s,A)] \end{aligned} \\
模型训练：
1.观察状态S_{t}
2.根据\pi(*|s_{t},a_{t})随机采样动作a_{t}
3.计算q_{t} \approx Q_{\pi}(s_{t},a_{t})
4.对策略网络求导：
d_{\theta, t}=\frac{\partial log_{\pi}(a_{t}|s_{t},\theta)}{\partial \theta}|_{\theta=\theta_{t}} \\
5.计算策略梯度：
g(a_{t},\theta_{t})=q_{t}*d_{\theta, t} \\
6.更新策略网络：
\theta_{t+1}=\theta_{t} + \beta*g(a_{t},\theta_{t}) \\
Actor-Critic Reinforcement Learning
算法思想： 用两个神经网络分别近似Optimal Difference Learning和policy \pi(a|s)
V_{\pi}(s)=\sum_{a}\pi(a|s)*Q_{\pi}(s,a) \approx \sum_{a}\pi(a|s;\theta)*Q_{\pi}(s,a;w) \\
模型训练：
1.观察状态S_{t}并根据\pi(*|s_{t},a_{t})随机采样动作a_{t}
2.执行动作a_{t}，然后得到新的状态S_{t+1}和奖励r_{t}
3.随机采样动作\hat a_{t+1}(不需要执行)
4.评估价值网络：q_{t}=q(s_{t},a_{t};w_{t})和q_{t+1}=q(s_{t+1},\hat a_{t+1};w_{t})
5.计算TD error
\delta_{t}=q_{t}-(r_{t} + \gamma * q_{t+1}) \\
6.对价值网络求导：
d_{w,t}=\frac{\partial q(s_{t},a_{t};w_{t})}{\partial w}|_{w=w_{t}}\\
7.更新价值网络(value network)
w_{t+1}=w_{t} - \alpha * \delta_{t}*d_{w,t}\\
8.对动作网络求导(action network)
d_{\theta, t}=\frac{\partial log_{\pi}(a_{t}|s_{t},\theta)}{\partial \theta}|_{\theta=\theta_{t}} \\
9.更新动作网络
\theta_{t+1} = \theta_{t} + \beta * q_{t} * d_{\theta, t} \\
TD训练算法
Sarsa(State-Action-Reward-State-Action)算法
折扣回报的定义：
\begin{aligned} U_{t} &= R_{t} + \gamma \cdot R_{t+1} + \gamma^{2} \cdot R_{t+2} + ... \\ &= R_{t} + \gamma \cdot U_{t+1} \end{aligned} \\
TD target推导：
\begin{aligned} Q_{\pi}(s_{t},a_{t}) &= E \\ &= E \\ &= E + \gamma \cdot E \\ &= E + \gamma \cdot E \\ &\approx r_{t} + \gamma * Q_{\pi}(s_{t+1},a_{t+1}) \end{aligned} \\
使用神经网络来近似Q_{\pi}:
[*]TD target：y_{t}=r_{t}+\gamma \cdot q(s_{t+1},a_{t+1};w)
[*]TD error：\delta_{t}=q(s_{t},a_{t};w)-y_{t}
[*]Loss: \delta_{t}^{2} / 2
[*]梯度
\frac{\partial \delta_{t}^{2} / 2}{\partial w}=\delta_{t} \cdot \frac{\partial q(s_{t},a_{t};w)}{\partial w} \\
[*]梯度下降更新参数
w \leftarrow w-\alpha \cdot \delta_{t} \cdot \frac{\partial q(s_{t},a_{t};w)}{\partial w} \\
Q-Learning 算法
目标：训练最优价值函数Q^{*}(s,a)。公式推导如下：
Q^{*}(s_{t},a_{t}) = E \\
其中：
A_{t+1} = arg\max_{a} Q^{*}(S_{t+1}, a) \\
因此：
\begin{aligned} Q^{*}(S_{t+1},A_{t+1}) &= \max_{a}Q^{*}(s_{t+1}, a) \\ Q^{*}(s_{t},a_{t}) &\approx r_{t} + \gamma \cdot \max_{a}Q^{*}(s_{t+1},a)\end{aligned} \\
使用神经网络来学习：
[*]观察到一个状态转移： (s_{t},a_{t},r_{t},s_{t+1})
[*]TD target： y_{t}=r_{t} + \gamma \cdot \max_{a} q^{*}(s_{t+1},a;w)
[*]TD error：\delta_{t}=q(s_{t},a_{t};w)-y_{t}
[*]Loss: \delta_{t}^{2} / 2
[*]梯度
\frac{\partial \delta_{t}^{2} / 2}{\partial w}=\delta_{t} \cdot \frac{\partial q(s_{t},a_{t};w)}{\partial w} \\
[*]梯度下降更新参数
w \leftarrow w-\alpha \cdot \delta_{t} \cdot \frac{\partial q(s_{t},a_{t};w)}{\partial w} \\
多步TD target
多步回报：
\begin{aligned} U_{t} &= R_{t} + \gamma \cdot U_{t+1} \\ &= R_{t} + \gamma \cdot R_{t+1} + \gamma^{2} U_{t+1} \\ &= ... \\ &= \sum_{i=0}^{m-1}\gamma_{i}\cdot R_{t+i} + \gamma^{m} \cdot U_{t+m} \end{aligned} \\
m-step TD target for Sarsa:
y_{t} = \sum_{i=0}^{m-1}\gamma_{i}\cdot r_{t+i} + \gamma^{m} \cdot q_{\pi}(s_{t+m}, a_{t+m}) \\
m-step TD target for Q-Learning:
y_{t} = \sum_{i=0}^{m-1}\gamma_{i}\cdot R_{t+i} + \gamma^{m} \cdot \max_{a}q^{*}(s_{t+1},a)\\
经验回放
前面介绍的TD算法有以下两个缺点：
[*]浪费经验。对于每个状态转移(transition)，使用完就会丢弃
[*]前后两个transition相关性很强
这里介绍一下replay buffer的概念：存储n个transition(s_{t},a_{t},r_{t},s_{t+1})。当加入一个新的transition时，必须移除最旧的transition。其中，n是超参数，大小取决于具体应用。使用梯度下降来更新参数：
[*]从replay中随机选取一个transition
[*]计算 TD error, \delta_{i}
[*]梯度
g_{i} = \frac{\partial \delta_{t}^{2} / 2}{\partial w}=\delta_{t} \cdot \frac{\partial q(s_{t},a_{t};w)}{\partial w} \\
[*]梯度下降更新参数
w \leftarrow w-\alpha \cdot g_{i} \\
优先经验回放
[*]使用非均匀抽样代替均匀抽样
[*]对于TD error大的transition给予更高的抽样权重
[*]对于抽样权重较大的transition，给予较小的学习率
高估问题
高估原因
[*]计算TD target时使用了最大化： y_{t}=r_{t} + \gamma \cdot \max_{a}q{*}(s_{t+1},a;w)
[*]BootStrapping造成了高估循环
解决方案
[*]targetNetwork
[*]与Q(s,a;w)具有相同的网络结构
[*]参数更新
[*]周期性更新
[*]w^{-} \leftarrow w或者w^{-} \leftarrow \tau \cdot w + (1-\tau)\cdot w^{-}
[*]使用方式：y_{t}=r_{t} + \gamma \cdot \max_{a}q{*}(s_{t+1},a;w^{-})
[*]Double DQN
[*]a^{*}=arg\max_{a}q(s_{t+1}, a;w)
[*]y_{t}=r_{t} + \gamma \cdot \max_{a}q{*}(s_{t+1},a;w^{-})
Dueling Network
相关定义：
\begin{aligned} Q^{*}(s,a) &= \max_{\pi}Q_{\pi}(s,a) \\ V^{*}(s) &= \max_{\pi}V_{\pi}(s)\\ A^{*}(s,a) &= Q^{*}(s,a)-V^{*}(s) \end{aligned} \\
定理一：
V^{*}(s) = \max_{a}Q^{*}(s,a) \\
对上述第三个定义两边取最大化可得：
\begin{aligned} \max_{a}A^{*}(s,a) &= \max_{a}Q^{*}(s,a) -V^{*}(s) \\ &= 0 \end{aligned} \\
定理二：
Q^{*}(s,a)=V^{*}(s)+A^{*}(s,a) - \max_{a}A^{*}(s,a) \\
使用两个神经网络分别近似V^{*}(s)和A^{*}(s,a)即可达到近似Q^{*}(s,a)的效果
多智能体学习概念
相关术语
多智能体四种常见设定：
[*]协作
[*]竞争
[*]协作+竞争
[*]自利（只看对自己是否有利）
假设有n个agent：
[*]S：状态
[*]A^{i}：第i个agent的action
[*]状态转移：
p(s^{'}|s,a^{1},a^{2},...,a^{n})=p(S=s^{'}|S=s,A^{1}=a^{1},A^{2}=a^{2},...,A^{n}=a^{n}) \\
下个状态s^{'}，依赖所有agent的action
[*]R^{i}：第i个agent的reward，它取决于所有agent的action
[*]R_{t}^{i}：第i个agent在时间t获得的奖励
[*]折扣回报：
U_{t}^{i}=R_{t}^{i} + \gamma \cdot R_{t+1}^{i} + \gamma^{2} \cdot R_{t+1}^{2} + ... \\
每个agent都有它自己的策略网络：\pi(a^{i}|s;\theta^{i})
[*]reward的随机性来自于以下两个方面：
[*]状态转移函数p
[*]策略网络\pi(*|s_{t};\theta^{i})
[*]第i个agent的状态价值函数：
V^{i}(s_{t}|\theta^{1},\theta^{2},...,\theta^{n})=E \\
[*]收敛：每个agent都无法通过改变策略来获得更大期望回报
[*]纳什均衡：当其余agent都不改变策略时，一个agent单独改变策略，不会让自己获得更高的回报
三种架构
1）去中心化。agent都是独立的个体，独立跟环境交互，用自己的观测和奖励来更新自己的策略，agent之间彼此不交流
2）完全中心化。所有agent都把信息传到中央控制器，中央控制器知道所有agent的观测、动作以及奖励，agent上没有策略网络，自己不做决策，只执行指令
3）agent有自己的策略网络，同时存在一个中央控制器，它会收集所有agent的观测、动作以及奖励。中央控制器负责训练价值网络，agent负责训练策略网络
策略梯度优化
策略梯度
[*]策略网络： \pi(a|s;\theta)，用于控制agent
[*]状态价值函数：
\begin{aligned} V_{\pi}(s)&=E_{A\sim \pi} \\ &=\sum_{a}\pi(a|s;\theta) \cdot Q_{\pi}(s,a) \end{aligned} \\
[*]策略梯度：
\frac{\partial V_{\pi}(s)}{\partial \theta}=E_{A\sim \pi}[\frac{\partial ln \pi(A|s;\theta)}{\partial \theta}\cdot Q_{\pi}(s,A)] \\
策略梯度Baseline
[*]baseline，b，是独立于A的任何表达式
\begin{aligned} E_{A\sim \pi}&= b \cdot E_{A\sim \pi}[\frac{\partial ln \pi(A|s;\theta)}{\partial \theta}] \\ &= b \cdot \sum_{a}\pi(a|s;\theta)\cdot[\frac{1}{\pi(a|s;\theta)}\cdot \frac{\partial \pi(a|s;\theta)}{\partial \theta}] \\ &= b \cdot \sum_{a}\frac{\partial \pi(a|s;\theta)}{\partial \theta} \\ &= b \cdot \frac{\partial 1}{\partial \theta} \end{aligned} \\
[*]带baseline的策略梯度
\begin{aligned} \frac{\partial V_{\pi}(s)}{\partial \theta} &= E_{A\sim \pi}[\frac{\partial ln \pi(A|s;\theta)}{\partial \theta}\cdot Q_{\pi}(s,A)] - E_{A\sim \pi} \\ &= E_{A\sim \pi}[\frac{\partial ln \pi(A|s;\theta)}{\partial \theta}\cdot (Q_{\pi}(s,A)-b)] \end{aligned} \\
虽然b不会影响策略梯度的期望，但合适的b能够降低策略梯度的偏差，加快收敛速度
[*]baseline b的选择
[*]b=0，此时退化为标准的策略梯度
[*]b=V_{\pi}(s_{t})
REINFORCE with Baseline
[*]折扣回报
U_{t}=R_{t} + \gamma \cdot R_{t+1} + \gamma^{2} \cdot R_{t+2} + ... \\
[*]策略梯度
\begin{aligned} \frac{\partial V_{\pi}(s)}{\partial \theta}&= E_{A\sim \pi}[\frac{\partial ln \pi(A|s;\theta)}{\partial \theta}\cdot (Q_{\pi}(s,A)-V_{\pi}(s_{t}))] \\ &= g(A_{t}) \end{aligned} \\
[*]随机采样：a_{t} \sim \pi(.|s_{t};\theta)
[*]g(a_{t})是策略梯度的一个无偏估计
[*]蒙特卡洛近似：Q_{\pi}(s_{t},a_{t}) \approx u_{t}，REINFORCE
[*]通过神经网络v(s;w)来近似V_{\pi}(s_{t})
[*]通过梯度提升来更新策略网络
\begin{aligned} \theta &\leftarrow \theta + \beta \cdot \frac{\partial ln \pi (a_{t}|s_{t};\theta)}{\partial \theta} \cdot (u_{t}-v(s_{t};w)) \\ &\leftarrow \theta - \beta \cdot \delta_{t} \cdot \frac{\partial ln \pi (a_{t}|s_{t};\theta)}{\partial \theta} \end{aligned} \\
[*]通过梯度下降更新价值网络
[*]预估误差
\delta_{t}=v(s_{t};w) - u_{t} \\
[*]梯度
\frac{\partial \delta^{2}/2}{\partial w}=\delta_{t}\cdot \frac{\partial v(s_{t};w)}{\partial w} \\
[*]梯度下降
w\leftarrow w-\alpha \cdot \delta_{t}\cdot \frac{\partial v(s_{t};w)}{\partial w} \\
Adventage Actor-Critic
把baseline应用到actor-critic算法
[*]观察一个转化：(s_{t},a_{t},r_{t},s_{t+1})
[*]TD target：y_{t}=r_{t} + \gamma \cdot v(s_{t+1};w)
[*]TD error：\delta_{t}=v(s_{t};w)-y_{t}
[*]更新策略网络
\theta \leftarrow \theta - \beta \cdot \delta_{t} \cdot \frac{\partial ln \pi (a_{t}|s_{t};\theta)}{\partial \theta} \\
[*]更新价值网络
w\leftarrow w-\alpha \cdot \delta_{t}\cdot \frac{\partial v(s_{t};w)}{\partial w} \\
[*]与REINFORCE的区别
[*]A2C使用带bootstrapping的多步TD target
y_{t}=\sum_{i=0}^{m-1}\gamma^{i}\cdot r_{t+i} + \gamma^{m}\cdot v(s_{t+m};w) \\
[*]REINFORCE使用已观测到的回报
u_{t}=\sum_{i=0}^{n-t}\gamma^{i}\cdot r_{t+i} \\
连续控制问题
在做离散化时，空间维度越高，需要探索的组合就越多，这会造成维度灾难。连续控制可以在一定程度上解决这个问题
Deterministic Policy Gradient(DPG)
[*]使用策略网络来做决策：a=\pi(s;\theta)
[*]通过DPG来更新策略网络：
\theta \leftarrow \theta + \beta \cdot \frac{\partial a}{\partial \theta} \cdot \frac{\partial q(s,a;w)}{\partial a} \\
[*]价值网络计算：q_{t}=q(s,a;w)
[*]target网络计算：\pi(s;\theta^{-})、q(s,a;w^{-})和q_{t+1}
[*]TD error：\delta_{t}=q_{t}-(r_{t}+\gamma \cdot q_{t+1})
[*]更新价值网络：
w \leftarrow w - \alpha \cdot \delta_{t} \cdot \frac{\partial q(s,a;w)}{\partial w} \\
[*]target网络更新：
[*]设置一个超参数：\tau \in (0,1)
[*]通过对权重求平均来更新target网络：
\begin{aligned} w^{-} &\leftarrow \tau \cdot w + (1-\tau) \cdot w^{-} \\ \theta^{-} &\leftarrow \tau \cdot \theta + (1-\tau) \cdot \theta^{-} \end{aligned} \\
Stochastic Policy for Continuous Control
[*]随机策略梯度
g(a)=\frac{\partial f(s,a;\theta)}{\partial \theta}\cdot Q_{\pi}(s,a) \\
[*]通过价值网络来近似Q_{\pi}：q(s,a;w)
[*]更新策略网络：
\theta \leftarrow \theta + \beta \cdot \frac{\partial f(s,a;\theta)}{\partial \theta} \cdot q(s,a;w) \\
[*]通过TD learning更新价值网络：q(s,a;w)
页:
[1]