David silver 强化学习 Lecture 9

课程主页： https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture 9的课程内容，这一讲简单介绍了Exploration（探索） and Exploitation（开发）。

Introduction

Exploration vs. Exploitation Dilemma

• 在线决策涉及一个基本选择：
  • 利用当前信息做出最佳决策
  • 探索收集更多信息
• 最佳的长期策略可能涉及短期牺牲
• 收集足够的信息以做出最佳的总体决策

以多臂赌博机的例子讨论上述问题。

The Multi-Armed Bandit

• 多臂赌博机是元组$\langle\mathcal{A}, \mathcal{R}\rangle$
• $\mathcal A$是已知的$m$个动作
• $\mathcal{R}^{a}(r)=\mathbb{P}[r | a]$是未知的概率分布
• 在每个时间$t$，智能体选择动作$a_t\in \mathcal A$
• 环境生成奖励$r_t\sim \mathcal R^{a_t}$
• 目标是最大化累计收益$\sum_{\tau=1}^{t} r_{\tau}$

Regret

• 动作-价值是动作$a$的平均回报

  $$Q(a)=\mathbb{E}[r | a]$$

• 最优价值$V^{\star}$为

  $$V^{*}=Q\left(a^{*}\right)=\max _{a \in \mathcal{A}} Q(a)$$

• 后悔值定义为每一步的机会损失

  $$I_{t}=\mathbb{E}\left[V^{*}-Q\left(a_{t}\right)\right]$$

• 全部后悔值是总的机会损失

  $$L_{t}=\mathbb{E}\left[\sum_{\tau=1}^{t} V^{*}-Q\left(a_{\tau}\right)\right]$$

• 最大化累计奖励=最小化全部后悔值

Counting Regret

• count $N_t(a)$是动作$a$的期望选择数量

• gap $\Delta_{a}$是动作$a$和最优动作$a^\star$的价值差

  $$\Delta_{a}=V^{*}-Q(a)$$

• 后悔值是gaps和couts的函数

  $$\begin{aligned} L_{t} &=\mathbb{E}\left[\sum_{\tau=1}^{t} V^{*}-Q\left(a_{\tau}\right)\right] \\ &=\sum_{a \in \mathcal{A}} \mathbb{E}\left[N_{t}(a)\right]\left(V^{*}-Q(a)\right) \\ &=\sum_{a \in \mathcal{A}} \mathbb{E}\left[N_{t}(a)\right] \Delta_{a} \end{aligned}$$

Linear or Sublinear Regret

• 如果一个算法永远探索，它将具有线性的总后悔值
• 如果算法从不探索，它将具有线性总后悔值
• 是否有可能实现亚线性的总后悔值？

Greedy Algorithm

• 利用MC估计$Q$值

  $$\hat{Q}_{t}(a)=\frac{1}{N_{t}(a)} \sum_{t=1}^{T} r_{t} \mathbf{1}\left(a_{t}=a\right)$$

• 贪心算法选择价值最高的动作

  $$a_{t}^{*}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \hat{Q}_{t}(a)$$

• 贪心算法会产生线性的总后悔值

$\epsilon$-Greedy Algorithm

• $\epsilon$-贪心算法

  • 有$1-\epsilon$概率选择$a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \hat{Q}(a)$
  • $\epsilon$概率随机选择动作

• 常数$\epsilon$确保最小后悔值

  $$l_{t} \geq \frac{\epsilon}{|\mathcal{A}|} \sum_{a \in \mathcal{A}} \Delta_{a}$$

• $\epsilon$贪心算法会产生线性的总后悔值

Optimistic Initialisation

• 该方法将$Q(a)$初始化为较大的值

• 从$N(a)>0$开始

  $$\hat{Q}_{t}\left(a_{t}\right)=\hat{Q}_{t-1}+\frac{1}{N_{t}\left(a_{t}\right)}\left(r_{t}-\hat{Q}_{t-1}\right)$$

• 利用贪心和$\epsilon-$贪心算法都会产生线性的后悔值

Decaying $\epsilon_t$-Greedy Algorithm

• 选择衰减规划$\epsilon_{1}, \epsilon_{2}, \dots$

• 考虑如下规划

  $$\begin{array}{l} c>0 \\ d=\min _{a | \Delta_{a}>0} \Delta_{i} \\ \epsilon_{t}=\min \left\{1, \frac{c|\mathcal{A}|}{d^{2} t}\right\} \end{array}$$

• 衰减$\epsilon_t-$贪心算法会产生对数线性的后悔值，但是需要知道gaps

Lower Bound

后悔值有如下下界（Lai and Robbins）

$$\lim _{t \rightarrow \infty} L_{t} \geq \log t \sum_{a | \Delta_{a}>0} \frac{\Delta_{a}}{K L\left(\mathcal{R}^{a} \| \mathcal{R}^{a^{*}}\right)}$$

Upper Confidence Bounds

• 对每个动作价值估计置信上界$\hat{U}_{t}(a)$

• 使得有高概率$Q(a) \leq \hat{Q}_{t}(a)+\hat{U}_{t}(a)$

• 这依赖于被选择的次数$N(a)$

  • 较小的$N_{t}(a) \Rightarrow$较大的$\hat{U}_{t}(a)$(估计价值不准确)
  • 较大的$N_t(a) \Rightarrow$较小的$\hat{U}_{t}(a)$(估计价值准确)

• 选择动作最大化Upper Condence Bound (UCB)

  $$a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \hat{Q}_{t}(a)+\hat{U}_{t}(a)$$

Hoeffding’s Inequality

UCB需要使用Hoeffding不等式：

假设$X_{1}, \ldots, X_{t}$是属于$[0,1]$的独立同分布随机变量，令$X_{t}=\frac{1}{\tau} \sum_{\tau=1}^{t} X_{\tau}$为样本均值，那么

$$\mathbb{P}\left[\mathbb{E}[X]>\bar{X}_{t}+u\right] \leq e^{-2 t u^{2}}$$

Calculating Upper Confidence Bounds

利用Hoeffding不等式可得

$$\mathbb{P}\left[Q(a)>\hat{Q}_{t}(a)+U_{t}(a)\right] \leq e^{-2 N_{t}(a) U_{t}(a)^{2}}$$

令

$$\begin{aligned} e^{-2 N_{t}(a) U_{t}(a)^{2}} &=p \\ U_{t}(a) &=\sqrt{\frac{-\log p}{2 N_{t}(a)}} \end{aligned}$$

取$p=t^{-4}$得到

$$\begin{aligned} e^{-2 N_{t}(a) U_{t}(a)^{2}} &=p \\ U_{t}(a) &=\sqrt{\frac{-\log p}{2 N_{t}(a)}} \end{aligned}$$

UCB1

利用上述结果得到UCB1算法

$$a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(a)+\sqrt{\frac{2 \log t}{N_{t}(a)}}$$

UCB算法可以得到对数后悔值

$$\lim _{t \rightarrow \infty} L_{t} \leq 8 \log t \sum_{a | \Delta_{a}>0} \Delta_{a}$$

Bayesian Bandits

• 之前都没有假设奖励的分布$\mathcal R$，贝叶斯赌博机假设先验$p[\mathcal{R}]$
• 然后计算后验概率$p\left[\mathcal{R} | h_{t}\right]$
  • 其中$h_{t}=a_{1}, r_{1}, \ldots, a_{t-1}, r_{t-1}$
• 如果先验准确，那么会有更好的效果

Probability Matching

• 概率匹配根据$a$是最佳动作的概率选择动作

  $$\pi\left(a | h_{t}\right)=\mathbb{P}\left[Q(a)>Q\left(a^{\prime}\right), \forall a^{\prime} \neq a | h_{t}\right]$$

• 面对不确定性，概率匹配是乐观的

  • 不确定的动作更有可能达到最大
• 从后验分析可能会很困难

Thompson Sampling

• 汤普森采样实现概率匹配

  $$\begin{aligned} \pi\left(a | h_{t}\right) &=\mathbb{P}\left[Q(a)>Q\left(a^{\prime}\right), \forall a^{\prime} \neq a | h_{t}\right] \\ &=\mathbb{E}_{\mathcal{R} | h_{t}}[\mathbf{1}(a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(a))] \end{aligned}$$

• 利用贝叶斯法则计算后验概率$p\left[\mathcal{R} | h_{t}\right]$

• 从后验中采样奖励

• 计算动作函数$Q(a)=\mathbb{E}\left[\mathcal{R}_{a}\right]$

• 选择最大化样本动作函数的动作$a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(a)$

• 汤普森采样达到了Lai和Robbins的下界

Information State Space

• 我们将赌博机视为一步的决策问题
• 也可以将其视为序列决策问题
• 每一步都有一个信息状态$\tilde s$
  • $\tilde s$是静态历史$\tilde{s}_{t}=f\left(h_{t}\right)$，总结到目前为止积累的所有信息
• 每个动作$a$都会导致过渡到新的信息状态$\tilde s’$，转移概率为$\tilde{\mathcal{P}}_{\tilde{s}, \tilde{s}^{\prime}}^{a}$
• 在增强信息状态空间中定义MDP $\tilde {\mathcal M}$

Example: Bernoulli Bandits

• 考虑一个伯努利赌博机，其中$\mathcal{R}^{a}=\mathcal{B}\left(\mu_{a}\right)$
• 赢得或输掉游戏的概率$\mu_a$
• 状态信息为$\tilde{s}=\langle\alpha, \beta\rangle$
  • $\alpha_a$计算arm $a$奖励为$0$的次数
  • $\beta_a$计算arm $a$奖励为$1$的次数

Bayes-Adaptive Bernoulli Bandits

• 假设价值函数$\mathcal R^a$的先验分布为$\operatorname{Beta}\left(\alpha_{a}, \beta_{a}\right)$
• 每次选择动作$a$，更新后验$\mathcal{R}^{a}$
  • 如果$r=0,\operatorname{Beta}\left(\alpha_{a}+1, \beta_{a}\right)$
  • 如果$r=1,\operatorname{Beta}\left(\alpha_{a}, \beta_{a}+1\right)$
• 这定义了Bayes-Adaptive MDP的转移函数$\tilde {\mathcal P}$
• 信息状态$\langle\alpha, \beta\rangle$奖励模型$\operatorname{Beta}(\alpha, \beta)$有关
• 每个状态转换对应于贝叶斯模型更新

图示如下：

Contextual Bandits

考虑内容赌博机，一个具体的例子是在线广告推送：

• 内容赌博机是元组$\langle\mathcal{A}, \mathcal{S}, \mathcal{R}\rangle$
• $\mathcal A$是动作集合
• $\mathcal{S}=\mathbb{P}[s]$是关于状态的未知分布
• $\mathcal{R}_{S}^{a}(r)=\mathbb{P}[r | s, a]$是关于奖励的未知概率分布
• 在每个时间戳$t$
  • 环境产生状态$s_t\sim \mathcal S$
  • 智能体选择动作$a_t\in \mathcal A$
  • 环境生成奖励$r_{t} \sim \mathcal{R}_{s_{t}^{a}}^{a_{t}}$
• 目标是最大化累计奖励$\sum_{\tau=1}^{t} r_{\tau}$

Linear Regression

考虑用线性函数逼近动作价值函数：

$$Q_{\theta}(s, a)=\phi(s, a)^{\top} \theta \approx Q(s, a)$$

利用最小二乘估计参数可得：

$$\begin{aligned} &A_{t}=\sum_{\tau=1}^{t} \phi\left(s_{\tau}, a_{\tau}\right) \phi\left(s_{\tau}, a_{\tau}\right)^{\top}\\ &b_{t}=\sum_{\tau=1}^{t} \phi\left(s_{\tau}, a_{\tau}\right) r_{\tau}\\ &\theta_{t}=A_{t}^{-1} b_{t} \end{aligned}$$

Linear Upper Confidence Bounds

• 最小二乘回归估计平均动作价值$Q_{\theta}(s, a)$
• 同样可以估计动作价值的方差$\sigma_{\theta}^{2}(s, a)$
• 参数估计误差带来的不确定性
• 增加不确定性的奖励，$U_{\theta}(s, a)=c \sigma$
• 即定义UCB为高于平均值的$c$个标准差

Calculating Linear Upper Confidence Bounds

• 对于最小二乘回归，参数协方差为$A^{-1}$

• 动作价值函数关于特征是线性：

  $$Q_{\theta}(s, a)=\phi(s, a)^{\top} \theta$$
• 所以动作价值函数的方差是二次的： $$\sigma_{\theta}^{2}(s, a)=\phi(s, a)^{\top} A^{-1} \phi(s, a)$$
• UCB： $$Q_{\theta}(s, a)+c \sqrt{\phi(s, a)^{\top} A^{-1} \phi(s, a)}$$
• 选择动作以最大化上限：

$$a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q_{\theta}\left(s_{t}, a\right)+c \sqrt{\phi\left(s_{t}, a\right)^{\top} A_{t}^{-1} \phi\left(s_{t}, a\right)}$$