课程主页: 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$的平均回报

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

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

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

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

Counting Regret

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

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

  • 后悔值是gaps和couts的函数

Linear or Sublinear Regret

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

Greedy Algorithm

  • 利用MC估计$Q$值

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

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

$\epsilon$-Greedy Algorithm

  • $\epsilon$-贪心算法

    • 有$1-\epsilon$概率选择$a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \hat{Q}(a)$
    • $\epsilon$概率随机选择动作
  • 常数$\epsilon$确保最小后悔值

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

Optimistic Initialisation

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

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

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

Decaying $\epsilon_t$-Greedy Algorithm

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

  • 考虑如下规划

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

Lower Bound

后悔值有如下下界(Lai and Robbins)

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)

Hoeffding’s Inequality

UCB需要使用Hoeffding不等式:

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

Calculating Upper Confidence Bounds

利用Hoeffding不等式可得

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

UCB1

利用上述结果得到UCB1算法

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

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$是最佳动作的概率选择动作

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

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

Thompson Sampling

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

  • 利用贝叶斯法则计算后验概率$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

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

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

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}$

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

  • 所以动作价值函数的方差是二次的:
  • UCB:
  • 选择动作以最大化上限: