揭示贪婪算法在结构化老虎机问题中成败的决定性条件。
Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
- 提出判断贪婪算法成败的可识别性条件。
- 满足条件时，任意非退化算法均能实现次线性后悔。
- 适用于上下文与交互决策场景，拓展性强。
我们研究具有已知奖励结构的老虎机问题中的贪婪（仅利用）算法。允许任意有限奖励结构，而以往工作仅关注少数特定结构。我们完全刻画了贪婪算法在时间上渐近成功或失败的条件，即后悔呈次线性或线性增长。该刻画表明，问题实例的局部可识别性是渐近成功的充要条件。值得注意的是，一旦该条件成立，问题即变得简单——只要算法满足温和的非退化条件，任何算法都能成功（以相同意义）。该刻画还扩展至上下文老虎机和任意反馈的交互决策问题。提供了广泛适用性的示例，并讨论了无限奖励结构的扩展。
原文摘要 · Abstract (English)
We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few specific ones. We fully characterize when the greedy algorithm asymptotically succeeds or fails, in the sense of sublinear vs. linear regret as a function of time. Our characterization identifies a partial identifiability property of the problem instance as the necessary and sufficient condition for the asymptotic success. Notably, once this property holds, the problem becomes easy -- any algorithm will succeed (in the same sense as above), provided it satisfies a mild non-degeneracy condition. Our characterization extends to contextual bandits and interactive decision-making with arbitrary feedback. Examples demonstrating broad applicability and extensions to infinite reward structures are provided.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。