用于改进强盗的无先验竞争比：尺度、曲率和地平线是自由的，但在噪声下不能同时存在

arXiv:2609.17595v1 公告类型：新 摘要：在改进的多臂老虎机问题中，每个 $k$ 臂都有一条未知的非递减、离散凹奖励曲线 $f_i$，并且第 $t$ 次拉动臂 $i$ 会产生 $f_i(t)$。对于足够长的视野，Blum 和 Ravichandran (ALT 2025) 证明，当最佳臂的尺度 $m=f^*(T)$ 已知时 ($T\ge2k$)，随机算法可实现对最佳单臂的 $O(\sqrt k)$ 近似；当最佳臂的尺度 $m=f^*(T)$ 未知时 ($T>4k$)，随机算法可实现 $O(\sqrt k\log k)$，而 $\Omega(\sqrt k)$ 较低绑定。对数因子是不必要的：一页 \emph{probe-and-commit} 算法在 $T\ge2\lfloor\sqrt k\rfloor$ 上实现了竞争比率 $4\sqrt3\,\sqrt k$，而无需了解规模，并且我们确定每个水平线的最佳比率 $\Theta(\sqrt k+k/T)$，也适用于未知水平线。没有噪声，\emph{根本不需要先验}：随机边缘探测算法既不读取 Blum、Garicano、Ravichandran 和 Sharma (UAI 2026) 的尺度 $m$，也不读取 Blum、Garicano、Ravichandran 和 Sharma (UAI 2026) 的凹包络指数 $\beta$，也不读取地平线 $T$，对于每个 $\beta$ 同时实现最佳 $\Theta(k^{\beta/(1+\beta)}+k/T)$每一个地平线。在 Blum 和 Ravichandran 的乘性噪声模型下，探测并提交在不知道噪声水平的情况下保持相同的全范围顺序 $\Theta(\sqrt k+k/T)$（并且 $\Theta(\sqrt k)$ 在同一范围内），但先验的价格会跳跃：对于任何固定的噪声水平 $\varepsilon\in(0,1/2]$，适应的统一价格$\phi_\varepsilon(k)$ --- 对于既不知道 $m$ 也不知道 $\beta$ 的算法，相对于 $k^{\beta/(1+\beta)}$ 的损失相对于 $k^{\beta/(1+\beta)}$ 的最坏情况是 $\Theta_\varepsilon(\sqrt{\log k/\log\log k})$，$k$ 在固定正 $\varepsilon$ 处渐近的下界，并由嵌套随机排列探测算法，而仅知道 $m$ 或 $\beta$ 即可恢复恒定价格。