第 172 题：上下文老虎机(LinUCB)，特征维度的探索效率？
题目
上下文老虎机(LinUCB)，特征维度的探索效率？
完整讲解
一、上下文 Bandit 与 LinUCB
上下文 Bandit：每轮有一个上下文向量（用户/物品特征）$\boldsymbol{x}$，奖励与 $\boldsymbol{x}$ 和所选臂相关。LinUCB：假设奖励关于上下文线性，即 $r_a \approx \boldsymbol{x}^\top \boldsymbol{\theta}a + \epsilon$，用岭回归估计 $\boldsymbol{\theta}_a$ 并构造置信上界，选 $a^* = \arg\max_a \boldsymbol{x}^\top \hat{\boldsymbol{\theta}}_a + \alpha |\boldsymbol{x}|{A_a^{-1}}$（$A_a$ 为设计矩阵），$\alpha$ 控制探索强度。
二、特征维度的探索效率
- 高维：特征维数 $d$ 大时，要估计 $d$ 维参数，样本需求约 $O(d)$ 才能得到可靠估计；探索空间大，收敛变慢。可做特征选择、降维或稀疏假设减少有效维度。
- 探索项：$|\boldsymbol{x}|_{A_a^{-1}}$ 体现当前上下文在该臂上的不确定性；高维下该范数易大，探索成本高。可通过正则、共享参数（如线性模型只区分臂的偏置）降低维度。
- 工程：选与奖励相关的特征、控制 $d$、用增量更新 $A_a^{-1}$（Sherman-Morrison）保证在线效率。
三、与 Thompson Sampling 对比
- LinTS：对 $\boldsymbol{\theta}$ 用高斯后验，抽样后选 $\arg\max \boldsymbol{x}^\top \tilde{\boldsymbol{\theta}}_a$；同样受特征维度影响，但实现简单、常与 LinUCB 效果相当。
面试要点
- 能说清上下文 Bandit 与 LinUCB 的线性假设及选臂公式（估计+探索项）。
- 能说明特征维度高时探索效率下降：样本需求 $O(d)$、不确定性范数大；可特征选择/降维/共享参数。
- 能简述 LinUCB 与 LinTS 的工程实现要点（增量更新、正则）。
记忆要点
- LinUCB：奖励线性于上下文，选臂=估计+$\alpha|\boldsymbol{x}|_{A^{-1}}$；高维需 $O(d)$ 样本、探索成本高。
- 提升效率：特征选择、降维、共享参数；LinTS 为贝叶斯替代，实现简单。