[广告策略算法系列十七]：强化学习基础

redhat9i · 发表于 2022-10-30 16:00

一转眼已经工作三年有余，作为一个勤劳的码农，一直在广告策略领域搬砖。最近有个强烈的想法，想要把广告策略方向涉及到的业务策略算法和技术栈做下梳理，一方面是对以往工作经验的一个回顾，另一方面也是对自我的一个重新认知，可以更好地为未来的进步找好方向。本文是该系列文章的第十七篇，往期文章可参考：

[广告策略算法系列一]：前言
[广告策略算法系列二]：预算分配
[广告策略算法系列三]：广告创意优化
[广告策略算法系列四]：新广告冷启动优化
[广告策略算法系列五]：成本控制策略
[广告策略算法系列六]：匀速投放
[广告策略算法系列七]：预估校准机制
[广告策略算法系列八]：多约束条件下的出价优化
[广告策略算法系列九]：多约束条件下的排序公式优化
[广告策略算法系列十]：混排策略和算法
[广告策略算法系列十一]：联盟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[U_{t}|S_{t}=s_{t},A_{t}=a_{t}] \\

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}[Q_{\pi}(S_{t},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[U_{t}|s_{t},a_{t}] \\ &= E[R_{t}+\gamma \cdot U_{t+1}|s_{t},a_{t}] \\ &= E[R_{t}|s_{t}, a_{t}] + \gamma \cdot E[U_{t+1}|s_{t},a_{t}] \\ &= E[R_{t}|s_{t}, a_{t}] + \gamma \cdot E[Q_{\pi}(S_{t+1}, A_{t+1})|s_{t},a_{t}] \\ &\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[R_{t} + \gamma \cdot Q^{*}(S_{t+1}, A_{t+1})] \\
其中：
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^{&#39;}|s,a^{1},a^{2},...,a^{n})=p(S=s^{&#39;}|S=s,A^{1}=a^{1},A^{2}=a^{2},...,A^{n}=a^{n}) \\
下个状态s^{&#39;}，依赖所有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[U_{t}^{i}|S_{t}=s_{t}] \\

收敛：每个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}[Q_{\pi}(s, A)] \\ &=\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 \frac{\partial ln \pi(A|s;\theta)}{\partial \theta}] &= 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}[b\cdot \frac{\partial ln \pi(A|s;\theta)}{\partial \theta}] \\ &= 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)

		自动登录	找回密码
密码			立即注册

[广告策略算法系列十七]：强化学习基础

本帖子中包含更多资源