线性赌博机 | Codeboy's Blog

形式陈述

线性反馈模型

线性赌博机把上下文赌博机中的每轮动作集合表示成向量：第 $t$ 轮学习器看到 $\mathcal A_t\subseteq\mathbb R^d$ ，选择 $x_t\in\mathcal A_t$ ，并观察

y_t=\langle\theta_*,x_t\rangle+\eta_t.

其中 $\langle\theta_*,x_t\rangle$ 是内积给出的条件期望奖励。未知参数满足 $\|\theta_*\|_2\le S$ ，动作满足 $\|x\|_2\le L$ 。噪声对历史过滤 $\mathcal F_{t-1}$ 条件均值为零，并通常假设条件 $R$ -次高斯：

\mathbb E[e^{\lambda\eta_t}\mid\mathcal F_{t-1}] \le e^{\lambda^2R^2/2}.

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

相对每轮线性最优动作

x_t^*\in\arg\max_{x\in\mathcal A_t}\langle\theta_*,x\rangle

的伪遗憾为

R_T=\sum_{t=1}^T \langle\theta_*,x_t^*-x_t\rangle.

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

正则最小二乘与置信椭球

定义

V_t=\lambda I+\sum_{s=1}^{t-1}x_sx_s^\top, \qquad b_t=\sum_{s=1}^{t-1}x_sy_s,

以及 ridge 估计

\widehat\theta_t=V_t^{-1}b_t.

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

\|x\|_{V_t^{-1}}=\sqrt{x^\top V_t^{-1}x}

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

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

\|\widehat\theta_t-\theta_*\|_{V_t} \le R\sqrt{2\log\frac{\det(V_t)^{1/2}} {\det(\lambda I)^{1/2}\delta}} +\sqrt\lambda S =:\beta_t.

于是参数置信集合是椭球

\mathcal C_t=\{\theta:\|\theta-\widehat\theta_t\|_{V_t}\le\beta_t\}.

OFUL 的乐观动作与遗憾界

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

x_t\in\arg\max_{x\in\mathcal A_t} \max_{\theta\in\mathcal C_t}\langle\theta,x\rangle.

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

\langle\widehat\theta_t,x\rangle +\beta_t\|x\|_{V_t^{-1}}.

第一项利用当前估计，第二项奖励信息不足的方向。它把不确定性下乐观原则从每臂标量区间推广到参数椭球。

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

r_t\le2\beta_t\|x_t\|_{V_t^{-1}}

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

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

从而得到隐藏对数因子的

R_T=\widetilde O(d\sqrt T)

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

直觉

$V_t$ 可以看作一张不断变形的信息地图：样本密集的方向被拉紧，对应 $V_t^{-1}$ 下很短的置信半轴；尚未探索的方向仍然宽。OFUL 给动作的分数不是“经验奖励再随便加一点奖励”，而是沿该动作方向把椭球推到最远，所以探索奖金会随历史设计的几何形状改变。

乐观选择与遗憾证明使用的是同一条几何事实。在置信事件内，真最优动作的真实价值不会超过它的乐观值，而算法选中的乐观值又至少同样大；两者之间只剩所选方向上的置信宽度。椭圆势引理则说明，学习器不可能在很多轮里反复支付很大的同方向宽度而不获得相应信息。

例子与边界

内容推荐中的共享信息

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

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

计算与模型边界

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

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

推论与应用

普通 $K$ 臂赌博机可取 $d=K$ 、动作向量为标准基，此时每个坐标只对应一只臂；线性模型的真正收益出现在特征可复用时，因为一次观测会同时约束与 $x_t$ 有投影关系的许多候选动作。遗憾由维度而非动作总数控制，因而能够处理巨大的乃至连续的动作集。

在动态定价、广告和推荐中，上下文—动作对可以共同编码成特征向量，模型便成为线性上下文赌博机。统计保证之外还要解决乐观目标的优化：组合动作集合通常需要线性优化 oracle，而 oracle 的精确度会直接进入每轮选择和最终遗憾。

同样的椭球构造也是不确定性下乐观原则的几何版本。更复杂的广义线性、核化或非平稳模型会替换估计器与置信集合，但仍需分别证明覆盖、乐观选择和宽度累计，不能仅沿用 OFUL 的分数形式。

参考资料

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, Cambridge University Press, 2020.

形式陈述 ​

线性反馈模型 ​

正则最小二乘与置信椭球 ​

OFUL 的乐观动作与遗憾界 ​

内容推荐中的共享信息 ​