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 \\

[*]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]
查看完整版本: [广告策略算法系列十七]:强化学习基础