H₁-SR
对Successive Rejects算法阶段调度进行数学优化得到的变体算法,在确定性等计数计划约束下达到最优调度,显著提升最佳臂识别效率
时间轴 (近 90 天)
一篇最新研究将 SR 的阶段调度设计形式化为针对归一化误差指数的优化问题,并提出了新的变体 H₁-Balanced Successive Rejects (H₁-SR)。
H₁-SR 的优化调度在具有确定性等计数计划的 SR 类算法中是最优的。
对于共同方差的高斯臂,H₁-SR 在所有自适应算法中至少能达到最优归一化速率的 11/12,且该比例对任意 K≥2 成立。
当候选臂数量 K 趋于无穷时,H₁-SR 的近似比以 1-O(1/log K) 的速度收敛至 1。
研究在十个合成实例和两个基于数据集的高斯基准上进行了实验,将优化调度与原始 SR 在有限时间范围内进行对比。
实验发现,在多数测试实例上优化调度带来了实质性性能提升,但在某些问题环境下,过于激进的早期淘汰策略反而会带来更高的代价。
H₁-SR 的计算开销几乎与原始 SR 相当。
全部知识事实 (7)
当候选臂数量 K 趋于无穷时,H₁-SR 的近似比以 1-O(1/log K) 的速度收敛至 1。
50%待验证H₁-SR 的优化调度在具有确定性等计数计划的 SR 类算法中是最优的。
50%待验证对于共同方差的高斯臂,H₁-SR 在所有自适应算法中至少能达到最优归一化速率的 11/12,且该比例对任意 K≥2 成立。
50%待验证实验发现,在多数测试实例上优化调度带来了实质性性能提升,但在某些问题环境下,过于激进的早期淘汰策略反而会带来更高的代价。
50%待验证H₁-SR 的计算开销几乎与原始 SR 相当。
50%待验证一篇最新研究将 SR 的阶段调度设计形式化为针对归一化误差指数的优化问题,并提出了新的变体 H₁-Balanced Successive Rejects (H₁-SR)。
50%待验证研究在十个合成实例和两个基于数据集的高斯基准上进行了实验,将优化调度与原始 SR 在有限时间范围内进行对比。
50%