线性赌博机

模型 ​

第 $t$ 轮学习器看到动作集合 ${\mathcal{A}}_t\subseteq {\mathbb{R}}^d$，选择 $x_t\in {\mathcal{A}}_t$，并观察

$$y_t=⟨{\theta }_{\ast },x_t⟩+{\eta }_t.$$

未知参数满足 $\Vert {\theta }_{\ast }{\Vert }_2\le S$，动作满足 $\Vert x{\Vert }_2\le L$。噪声对历史过滤 ${\mathcal{F}}_{t-1}$ 条件均值为零，并通常假设条件 $R$-次高斯：

$$\mathbb{E}[e^{\lambda {\eta }_t}\mid {\mathcal{F}}_{t-1}]\le e^{{\lambda }^2{R}^2/2}.$$

动作由过去数据自适应选择，所以设计矩阵不是独立固定样本；置信分析必须使用自归一化鞅界。

相对每轮线性最优动作

$$x_t^{\ast }\in \arg \underset{x\in {\mathcal{A}}_t}{max}⟨{\theta }_{\ast },x⟩$$

的伪遗憾为

$$R_T=\sum _{t=1}^T⟨{\theta }_{\ast },x_t^{\ast }-x_t⟩.$$

这里动作集可以随上下文变化。普通 $K$ 臂 bandit 是 $d=K$、动作取标准基向量的特例，但线性结构还能让相似动作共享信息。

正则最小二乘估计 ​

定义

$$V_t=\lambda I+\sum _{s=1}^{t-1}{x}_s{x}_s^{\mathrm{\top }},b_t=\sum _{s=1}^{t-1}{x}_s{y}_s,$$

以及 ridge 估计

$${\hat{\theta }}_t=V_t^{-1}{b}_t.$$

矩阵 $V_t$ 记录各方向获得了多少信息。对候选动作 $x$，量

$$\Vert x{\Vert }_{V_t^{-1}}=\sqrt{x^{\mathrm{\top }}{V}_t^{-1}x}$$

在很少探索的方向大、在反复观察的方向小。它不是动作的普通欧氏长度，而是由历史设计诱导的预测不确定性。

自归一化集中给出：以至少 $1-\delta$ 的概率，对所有 $t$，

$$\Vert {\hat{\theta }}_t-{\theta }_{\ast }{\Vert }_{V_t}\le R\sqrt{2\log \frac{\det {\left(V_t\right)}^{1/2}}{\det {\left(\lambda I\right)}^{1/2}\delta }}+\sqrt{\lambda }S=:{\beta }_t.$$

于是参数置信集合是椭球

$${\mathcal{C}}_t=\{\theta :\Vert \theta -{\hat{\theta }}_t{\Vert }_{V_t}\le {\beta }_t\}.$$

OFUL 的乐观动作 ​

OFUL 选择置信集合内可能最优的动作：

$$x_t\in \arg \underset{x\in {\mathcal{A}}_t}{max}\underset{\theta \in {\mathcal{C}}_t}{max}⟨\theta ,x⟩.$$

内层优化有闭式解，指数为

$$⟨{\hat{\theta }}_t,x⟩+{\beta }_t\Vert x{\Vert }_{V_t^{-1}}.$$

第一项利用当前估计，第二项奖励信息不足的方向。它把不确定性下乐观原则公理库不确定性下的乐观原则Optimism under uncertainty · Optimism in the face of uncertainty在仍与数据相容的模型中按最好可能价值行动，以探索消除不确定性。从每臂标量区间推广到参数椭球。

在真参数始终落入 ${\mathcal{C}}_t$ 的事件上，单轮遗憾可由

$$r_t\le 2{\beta }_t\Vert x_t{\Vert }_{V_t^{-1}}$$

控制。椭圆势引理进一步给

$$\sum _{t=1}^{T}min\{1,\Vert x_t{\Vert }_{V_t^{-1}}^2\}\le 2\log \frac{\det V_{T+1}}{\det V_1},$$

从而得到隐藏对数因子的

$$R_T=\tilde{O}(d\sqrt{T})$$

高概率界。维度依赖来自需要学习 $d$ 个参数方向，而非动作数；即使动作集合连续，也可保持有限遗憾。

一个共享信息例子 ​

推荐系统把每件内容表示为 $d$ 维特征向量，假设当前用户的期望点击率是未知偏好 ${\theta }_{\ast }$ 与内容特征的内积。展示一篇体育长文不仅更新这一篇的估计，也更新“体育”“长篇”等方向，从而影响许多未展示内容。普通独立臂 UCB 会把每篇文章视为无关，无法共享这份证据。

若两件内容特征相同却真实点击率不同，线性 realizability 已被破坏。算法会把系统偏差解释为噪声，置信椭球可能最终非常窄却不包含真奖励函数；继续运行不会靠更多样本修复错设。

计算与边界 ​

公式假设能解每轮的乐观动作优化。有限动作集可逐一打分，大型组合集合可能需要专门 oracle；统计遗憾小不代表每轮计算高效。更新 $V_t^{-1}$ 可用秩一公式，但数值实现仍需关注条件数，不能为省一次分解牺牲稳定性。

噪声条件、动作范数、参数范数和正则化 $\lambda$ 都进入 ${\beta }_t$。若奖励重尾、动作由未建模反馈产生或参数随时间漂移，标准 OFUL 置信事件不再成立。非平稳线性 bandit 需要变化预算和遗忘机制，不能只把 $S$ 调大。

参考资料

• Varsha Dani, Thomas Hayes, and Sham Kakade, “Stochastic Linear Optimization under Bandit Feedback,” COLT, 2008.
• Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári, “Improved Algorithms for Linear Stochastic Bandits,” NeurIPS, 2011.
• Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, linear bandit chapters.