Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

问题表述
本文研究了基于简单遗憾目标的随机逻辑回归多臂赌博机（logistic bandits）。在该设定下，学习者在$T$轮中与一个环境进行交互，从集合$\mathcal{A}$中选择动作$A_t$，并观测到均值为$\mu(\phi(A_t)^\top \theta^*)$的伯努利奖励$X_t$，其中$\mu$是sigmoid函数，$\phi$是已知的特征映射，$\theta^*$是$\mathbb{R}^d$中的未知参数。与旨在最大化探索过程中奖励总和的累积遗憾不同，简单遗憾目标仅根据$T$轮后单个最终推荐$\hat{a}$的质量来评估学习者。遗憾定义为最优动作的期望奖励与推荐动作的期望奖励之差。

逻辑回归多臂赌博机的一个关键挑战在于动作的信息量不均匀。由于sigmoid链接函数的作用，处于“饱和”区域（即平均奖励接近0或1）的动作会产生近乎确定性的奖励，但几乎不提供关于参数$\theta^*$的信息。相反，靠近原点（即sigmoid最陡峭处）的动作信息量极大，但可能产生较低的即时奖励。这形成了一种几何结构，使得对即时奖励最优的动作（利用）与对识别最优动作最优的动作（探索）截然不同。

方法论
作者提出了两种曲率感知算法，旨在利用sigmoid函数的局部几何特性：

1. MULOG（最大不确定性 - 对数法）： 一种确定性纯探索算法。

   • 机制： MULOG维护$\theta^*$的置信集$W_t$，并构建一个曲率加权的设计矩阵$L_t$。动作$a$和参数$\theta$的不确定性分数定义为$U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$，其中$\dot{\mu}$是sigmoid的导数（代表局部曲率）。
   • 选择： 在每一轮中，算法选择使该不确定性分数最大化的动作 - 参数对$(A_t, \theta_t)$。
   • 终止： 经过$T$轮后，它返回一个相对于从最终置信集中采样的参数向量具有贪婪性的动作。
   • 优化： 对于有限动作集，选择步骤简化为求解一组有限个凸优化问题。

2. THATS（努力尝试汤普森采样）： 一种随机化、计算量更轻的替代方案。

   • 机制： 与求解精确的最大不确定性不同，THATS从以$L_t^{-1}$为协方差的零中心高斯分布中采样一个方向$\tilde{\theta}_t$。
   • 选择： 它选择使随机化不确定性分数$\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$最大化的动作，其中$\bar{\theta}_t$是受约束的最大似然估计。
   • 权衡： 这种方法避免了MULOG所需的凸优化，但付出了统计代价，导致遗憾界限略微宽松。

主要贡献

• 极小极大下界： 本文建立了一个一阶极小极大下界，量级为$\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$，其中$\kappa^*$是最优动作处sigmoid的倒数斜率（即$\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$）。
  • 独特的困难机制： 与依赖于信息成本（迫使学习者选择次优臂）的累积遗憾下界（例如Abeille等人，2021）不同，该下界源于“平移饱和超立方体”构造。在该构造中，统计信息和价值敏感性均由饱和区域中的同一局部曲率控制。这揭示出，即使拥有纯粹为了获取信息而采样的自由，如果最优动作位于sigmoid的平坦区域，问题依然困难。
• 最优算法：
  • MULOG实现了$\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$的简单遗憾上界，在忽略对数因子的情况下与下界匹配。这是逻辑回归多臂赌博机首个直接实现实例级极小极大最优性的纯探索保证。
  • THATS实现了$\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$的界限。额外的$\sqrt{d}$因子源于使用了几何无关的随机化近似来替代最大不确定性方向。
• 几何洞察： 作者证明，最坏情况几何（平移饱和实例）并非唯一情况。他们表明，动作集中可能存在“信息丰富但低奖励”的动作（探针）。这些动作位于sigmoid的高曲率区域，尽管期望奖励较低，但能提供关于最优方向的重要信息。

结果

• 理论方面： 推导出的界限证实，逻辑回归简单遗憾的难度由最优动作处的曲率决定。这些算法成功地在曲率加权的特征方向上控制了不确定性。
• 实证方面： 在“困难”几何（平移饱和超立方体）和“容易”几何（添加了信息丰富的探针臂）上的实验支持了理论发现：
  • 在困难实例上，MULOG和THATS的表现符合极小极大界限的预测。
  • 在带有探针臂的容易实例上，纯探索方法（MULOG和THATS）显著优于累积遗憾基线（如累积汤普森采样和在线转批处理转换）。纯探索方法主动采样低奖励、高信息的探针，大幅减少了达到低简单遗憾阈值所需的轮数。
  • 累积遗憾方法未能有效利用这些探针，因为它们的在线转批处理转换会对最终推荐分布中包含低奖励动作施加惩罚。

意义
本文声称，逻辑回归多臂赌博机中的纯探索具有与累积遗憾问题截然不同的几何结构。主要贡献在于识别出**最优动作处的局部曲率（$\kappa^*$）**是决定一阶极小极大速率的主导因素。通过开发显式考虑该曲率的算法，作者在最坏情况下实现了极小极大最优性能。此外，该工作强调了一个实际启示：在A/B测试或奖励模型数据收集等场景中，主动寻求“信息丰富但低奖励”的动作可以显著加速最佳最终策略的识别，而标准累积遗憾算法在结构上无法表现出这种行为。这些结果为非线性赌博机中面向决策的探索的更精确理论奠定了基础。