提出正则化贪心算法，有效解决有限时域贝努利老虎机问题。
The Greedy Advantage in Finite-Horizon Bandits
- 设计正则化贪心算法，通过调节正则项平衡探索与利用。
- 首次给出有限时域后悔上界，后悔随正则强度指数下降。
- 实测表现优于或媲美顶尖算法，适合实际应用落地。
组织越来越多依赖顺序实验来优化决策。尽管多臂老虎机文献已发展出具有强渐近后悔保证的算法，但许多实际应用受限于有限且外部设定的时间范围。针对有限时域设置，我们为多臂伯努利老虎机开发了一类正则化贪心算法。首次推导出正则化贪心老虎机的有限时域后悔上界，表明后悔可分解为瞬态探索成本和随正则强度指数衰减的次优收敛项。该表征为正则化参数提供了合理校准依据，并在极限情况下得到经典贪心策略更紧的后悔上界。在广泛的数值实验中，经校准的正则化贪心策略始终表现优异，甚至超越现有先进算法。结果表明，正则化贪心策略可为有限时域老虎机问题提供高效解决方案。
原文摘要 · Abstract (English)
Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。