线性赌博机 | Codeboy's Blog

形式陈述

线性反馈模型

本页选择上下文赌博机的连续动作集合版本。设整数 $d\ge1$ ；第 $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 G_t$ 是本轮奖励揭示前的信息，包含此前历史、当前动作集合、选择动作所用随机性及 $x_t$ ；这些信息随轮次递增。噪声相对于它条件均值为零，并假设条件 $R$ -次高斯，其中 $R\ge0$ ：

\mathbb E[e^{u\eta_t}\mid\mathcal G_t] \le e^{u^2R^2/2}\qquad(u\in\mathbb R).

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

相对每轮线性最优动作

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$ 和标准基动作表示；一般对抗奖励不属于该固定参数模型。

正则最小二乘与置信椭球

固定正则化参数 $\lambda>0$ 和 $0<\delta<1$ ，定义

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$ 的事件上，记 $a_t=\|x_t\|_{V_t^{-1}}$ ，单轮遗憾满足 $r_t\le2\beta_t a_t$ 。同时，由参数与所有动作的范数界， $r_t\le2SL$ 。上式的 $\beta_t$ 非递减；令 $B_T=\max\{\beta_{T+1},SL\}$ ，两界合用才得到

r_t\le2B_T\min\{1,a_t\}.

矩阵行列式引理给出 $\det V_{t+1}=\det V_t(1+a_t^2)$ ；再用 $\min\{1,z\}\le2\log(1+z)$ 得椭圆势界

\sum_{t=1}^T\min\{1,a_t^2\} \le2\log\frac{\det V_{T+1}}{\det V_1}.

于是Cauchy–Schwarz 不等式给出

R_T\le2B_T\sqrt{2T\log\frac{\det V_{T+1}}{\det V_1}}, \qquad \log\frac{\det V_{T+1}}{\det V_1} \le d\log\left(1+\frac{TL^2}{d\lambda}\right).

当 $S,L,R,\lambda$ 固定时，代入置信半径得到隐藏对数因子的 $R_T=\widetilde O(d\sqrt T)$ 高概率界。这个推导不要求 $\lambda\ge L^2$ ：即使初期 $a_t>1$ ，瞬时遗憾的范数上界也补足了截断步骤。维度依赖来自需要学习参数方向，而非直接计数动作；连续动作仍需满足上述紧性、可测性和优化条件。

直觉

$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$ 有投影关系的许多候选动作。遗憾由维度而非动作总数控制，因而能够处理巨大的乃至连续的动作集。

在动态定价、广告和推荐中，上下文—动作对可以共同编码成特征向量，模型便成为线性上下文赌博机。统计保证之外还要解决乐观目标的优化：这里需要最大化包含 $\beta_t\|x\|_{V_t^{-1}}$ 的完整乐观目标。这个目标一般不是线性的，仅有线性优化 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 的乐观动作与遗憾界 ​

内容推荐中的共享信息 ​

计算与模型边界 ​