(强化学习)- 多摇臂赌博机问题和解决方案

Exploration vs Exploitation

探索-利用窘境存在于 RL 环境以及现实环境中. 考虑你有一个喜欢的餐馆. 你可以考虑两种策略:

  • 只去我常去的餐馆: 失去了探索其他更好的餐馆的机会
  • 如果总是去新的餐馆吃饭, 那么你有可能吃到不合口味的饭菜

我们现在就想通过在已知的吸引人的广告和新广告之间做出选择, 选择一个合适的平衡.

如果我们学习了关于环境足够的信息, 那么就可以使用暴力(brute-force)的方法而非智能的方法就能够做出最好的决策. 但是一个窘态: 缺少足够的信息, 我们需要会的足够的信息来最做好的决策同时把风险(risk)降低到可控的范围.

通过利用(exploitation), 我们能利用已知的最好的策略; 通过探索(exploration), 可以花一定的风险去收集关于未知选项(options)的信息. 有长久眼光(long-term)策略会有短期的损失, 也就是说探索的时候可能会有错误的行为被惩罚, 但是长期来看, 我们在做决策时就知道这个行为不应采用.

Multi-Armed Bandit

Multi-Armed Bandit, 多臂赌博机(K摇臂赌博机)问题关于探索-利用窘境的经典问题. 现在的问题是: 什么是最好的策略使得有最好的长期回报?(What is the best strategy to achieve highest long-term rewards?)

我们只讨论有限的尝试不同的赌博机. 这个限制就导致了另外的关于探索的问题: 我们不知道回报的概率, 因为我们没有尝试足够多的机器.

Bernoulli multi-armed bandit 的工作原理: 在这个例子中, bandit 有 4 个 arm. , 没摇动一次就产生一个 reward, 为 0或1, 每个 arm 的回报为1的概率对于赌徒来说是未知的.

虽然可以更具大数定律在一台机器上玩许多回合(round)来回的最真实概率, 但是这个方法浪费时间且不能保证得到最好的长期回报.

问题定义

Bernoulli multi-armed bandit 可以被描述为一个元组$\langle \mathcal{A}, \mathcal{R} \rangle$, 其中:

  • 有$K$个机器, 有 reward 的概率为: $\left\{{\theta_1,\cdots,\theta_K}\right\}$
  • 在任何时间步(time step)$t$, 都能够在一台机器上采取一个行为并且获得回报$r$
  • $\mathcal{A}$是行为(action)的空间, 特定的行为$a$的值是期望的回报, $Q(a)=\mathbb{E}[r|a]=\theta$. 如果是在第i台机器上的行为, 则记为$Q(a_t)=\theta_i$
  • $\mathcal{R}$是回报函数. 在 Bernoulli multi-armed bandit 中, 得到的回报$r$是一个随机(stochastic)的 fashion(?). 在时间步$t$, $r_t=\mathcal{R}(a_t)$在概率$Q(a_t)$下返回1, 否则返回0.

这是一个简化版本的 MDP, 因为没有状态空间$\mathcal{S}$.

最终的目标就是最大化累积(cumulative)回报 $\sum_{t=1}^Tr_t$.

最优(optimal)行为$a^*$的最优回报的概率$\theta^*$:

$$\theta^{*}=Q(a^{*})=\max_{a \in \mathcal{A}} Q(a) = \max_{1 \leq i \leq K} \theta_i$$

以及损失函数就是累积到时间$T$未选择最优行为的总 regret:

$$\mathcal{L}_T = \mathbb{E} \Big[ \sum_{t=1}^T \big( \theta^{*} - Q(a_t) \big) \Big]$$

赌博策略(Bandit Strategies)

基于如何探索的问题, 这里有一些方法来解决多臂赌博机的问题:

  • 不探索: 最原始(naive)的以及最坏的办法
  • 随机探索(Exploration at random)
  • 在不确定的情况下智能地选择偏好行为

ε-greedy 算法

这个算法除了偶尔采用随机(random)探索, 其余情况都会在那个时间上的最好的行为. 行为价值都会根据到目前为止的过去采取行为$a$经验的平均回报来估计:

$$\hat{Q}_t(a) = \frac{1}{N_t(a)} \sum_{\tau=1}^t r_\tau \mathbb{I}[a_\tau = a]$$

其中$\mathbb{I}$是指示函数, $N_t(a)$是行为$a$到目前为止被选择的次数, $N_t(a) = \sum_{\tau=1}^t \mathbb{I}[a_\tau = a]$.

算法会在很小的概率$\epsilon$下采取随机的行为, 大多是时候会以概率$1-\epsilon$采取都目前为止学习到的好的行为: $\hat{a}^{*}_t = \arg\max_{a \in \mathcal{A}} \hat{Q}_t(a)$

Upper Confidence Bounds

ε-greedy 算法是我们能够采取不清楚的行为, 但是引入的随机性(randomness)会造成我们最终会探索一些在过去已经证实为不好的行为. 为了阻止低效的探索, 我们需要及时地减小 ε 并且对高不确定性表示乐观也因此更加的偏向于选择还没有进行确定性(confident)的值估计. 也就是说我们偏向于用强潜力最优值来探索(we favor exploration of actions with a strong potential to have a optimal value).

Upper Confidence Bounds (UCB) 算法通过一个回报值的 upper confidence bound 来度量这个潜力, 记为$\hat{U}_t(a)$, 真正(只要是不足的估计就会有偏差)的值很有可能(with high probability)会不大于范围: $Q(a) \leq \hat{Q}_t(a) + \hat{U}_t(a)$. 上界(upper bound)$\hat{U}_t(a)$是$N_t(a)$的函数. 一个更大的尝试次数$N_t(a)$应该产生一个更小的界$\hat{U}(a)$.

在 UCB 算法中, 我们总是最贪婪地选择一个能使 upper confidence bound 最大化的行为:

$$a^{UCB}_t = \arg\max_{a \in \mathcal{A}} \hat{Q}_t(a) + \hat{U}_t(a)$$

现在的文是: 如何估计 upper confidence bound?

Hoeffding's Inequality

文献Hoeffding’s Inequality 中的公式可以应用到有界(bounded)的分布.

设独立同分布(i.i.d.)的约束于区间$[0,1]$的随机变量$X_1, \dots, X_t$. 采样均值(sample mean)为$\overline{X}_t = \frac{1}{t}\sum_{\tau=1}^t X_\tau$. 然后, 对于$u>0$, 有:

$$\mathbb{P} [ \mathbb{E}[X] > \overline{X}_t + u] \leq e^{-2tu^2}$$

然后通过替换:

  • $r_t(a)$是随机变量
  • $Q(a)$是期望(true mean)
  • $\hat{Q}_t(a)$是采样均值
  • $u$是 upper confidence bound, $u=U_t(a)$

就得到了:

$$\mathbb{P} [ Q(a) > \hat{Q}_t(a) + U_t(a)] \leq e^{-2t{U_t(a)}^2}$$

我们想选择一个界限来去使得均值小于或等于采样均值+upper confidence bound. 因此$e^{-2t U_t(a)^2}$是个很小的概率. 定义一个阈值$p$:

$$e^{-2t U_t(a)^2} = p \text{ Thus, } U_t(a) = \sqrt{\frac{-\log p}{2 N_t(a)}}$$

UCB1

一种通过估计更多的观察过的回报的方式来决定 confident bound 的启发式的(heuristic)及时减小阈值$p$的算法. 设$p=t^{-4}$, 得到了 UCB1 算法:

$$U_t(a) = \sqrt{\frac{2 \log t}{N_t(a)}} \text{ and }
a^{UCB1}_t = \arg\max_{a \in \mathcal{A}} Q(a) + \sqrt{\frac{2 \log t}{N_t(a)}}$$

Bayesian UCB

我们没有预先假设回报的分布的先验分布而是使用了 Hoeffding's Inequality. 如果我们预先知道了分布, 那么就可以更好的对边界进行估计.

例如, 我们估计的每一个机器的平均回报是下图的高斯分布:

期望的回报是一个高斯分布, $\sigma(a_i)$是标准差, $c\sigma(a_i)$是 upper confidence bound. 常数$c$可调的超参数.

我们通过设置$\hat{U}_t(a)$两倍于标准差来设置置信区间(confidence interval)的上界为 95%.

Thompson Sampling

在每个时间步, 我们更具最优的概率来选择动作:

$$\begin{aligned}
\pi(a \; \vert \; h_t)
&= \mathbb{P} [ Q(a) > Q(a'), \forall a' \neq a \; \vert \; h_t] \\
&= \mathbb{E}_{\mathcal{R} \vert h_t} [ \mathbb{1}(a = \arg\max_{a \in \mathcal{A}} Q(a)) ]
\end{aligned}$$

其中$\pi(a \; \vert \; h_t)$是给定历史$h_t$的采取行动$a$的概率.

对于 Bernoulli bandit, 很自然的想到: 当$Q(a)$是本质上的获得回报的服从伯努利分布的概率$\theta$, $Q(a)$遵从了 beta 分布. $\text{Beta}(\alpha, \beta)$的值在区间$[0,1]$中. $\alpha$和$\beta$分别是成功失败得到回报的次数. 根据先验的$\alpha$和$\beta$可以得到回报的概率以及置信情况, 例如:

  • $\alpha=1$和$\beta=1$, 期望的回报概率为 0.5, 但是不太确定
  • $\alpha=1000$和$\beta=9000$, 回报概率为 0.1, 但是很确定.

在每个时间步$t$都从所有的行为$a_i$的先验分布$\text{Beta}(\alpha_i,\beta_i)$采样一个期望的回报 $\hat{Q}(a)$:

$$a^{TS}_t = \arg\max_{a \in \mathcal{A}} \tilde{Q}(a)$$

在真正的回报得到后, 就需要相应地通过贝叶斯推断(Bayesian inference)来更新 beta 分布:

$$
\begin{aligned}
\alpha_i & \leftarrow \alpha_i + r_t \mathbb{1}[a^{TS}_t = a_i] \\
\beta_i & \leftarrow \beta_i + (1-r_t) \mathbb{1}[a^{TS}_t = a_i]
\end{aligned}$$

Thompson sampling 实现了probability matching的思想. 因为估计的$\hat{Q}$时采样自后验概率(posterior distributions), 这些概率等价于在观察到的条件下, 采取关联的最优行为的概率.

更多关于 Thompson sampling 可参考论文: A Tutorial on Thompson Sampling

例子

待续

总结

因为探索需要的信息不足, 我们就需要不同的探索策略. 例如随机策略;有选择性的选择动作, 例如有高不确定性的行为很有可能被倾向于选择.

参考

有时间会更新

添加评论