无需任何先验信息，一页算法就能搞定改进型老虎机，竞争比仅4√3√k！
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
📖 AI 总结
本文研究改进型多臂老虎机问题，其中每条臂对应一条未知的非递减离散凹收益曲线。此前Blum与Ravichandran（ALT 2025）证明，在已知最优臂规模时随机算法可达到O(√k)近似，未知规模时为O(√k log k)，并存在Ω(√k)下界。本文提出一种单页的“探测-承诺”算法，在无需任何规模先验的情况下达到4√3√k的竞争比，并给出任意时间范围内的最优比Θ(√k+k/T)。进一步发现，在无噪声情形下完全无需任何先验：一种随机边际探测算法可同时对所有凹性包络指数和所有时间范围达到最优。然而在乘性噪声下，先验的代价显著上升：若同时不知道规模与凹性指数，适应代价为Θ(√log k/log log k)，而仅知其一即可恢复常数代价。该结果揭示了规模、曲率与时间范围在无噪声时可自由获取，但在噪声下无法同时免费获得。
🔑 关键词速览
| 改进型多臂老虎机 | 一种多臂老虎机变体，每个臂的奖励随拉动次数非递减，且奖励曲线为离散凹函数。 |
| 竞争比 | 算法获得的累积奖励与最佳单臂累积奖励的比值，用于衡量算法的近似性能。 |
| 探测-承诺算法 | 一种两阶段算法：先进行少量探测以估计参数，然后承诺选择某个臂并持续拉动。 |
| 乘性噪声模型 | 奖励观测值受到与真实奖励成比例的随机噪声干扰的模型。 |
| 凹包络指数 β | 描述奖励曲线凹性程度的参数，影响最优竞争比中 k 的指数项。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅