在切换成本下，苹果品尝问题的最优后悔上界为√T量级。
Two-Action Apple Tasting with Switching Costs
- 设计揭示与盲选动作，通过切换惩罚建模真实决策场景。
- 证明最小最大后悔值在√T数量级，突破此前预期的T^{2/3}障碍。
- 适用于研究带切换成本的在线学习理论，尤其对反馈图分类有启示。
我们研究对抗性环境下的两动作苹果品尝问题，其中每次动作切换需支付单位代价。每轮学习者可选择揭示动作（收益为0，揭示隐藏值x_t∈[-1,1]）或盲选动作（收益为x_t，无信息）。后悔值相对于事后最优固定动作衡量。一般反馈图算法在该设定下可达到˜O(T^{2/3})的后悔界。此前认为两动作苹果品尝图是阻碍开关成本分类的Ω(T^{2/3})下界候选，但本文证明该障碍不存在：最小最大期望后悔满足1/(2√3)·√T ≤ R_T^* ≤ 2√3·√T。
原文摘要 · Abstract (English)
We study the two-action apple-tasting problem with switching costs against an oblivious adversary. In an equivalent normalized formulation, at each round the learner chooses between a revealing action and a blind action: the revealing action gives reward $0$ and reveals the hidden value $x_t\in[-1,1]$ of the blind action; the blind action gives reward $x_t$ but reveals nothing. The learner pays one unit whenever they switches actions, and regret is measured against the best fixed action in hindsight. General feedback-graph algorithms with switching costs give $\widetilde O(T^{2/3})$ regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing $Ω(T^{2/3})$ obstruction in the switching-cost classification: such a lower bound would have transferred to a large family of still-unclassified feedback graphs. We prove that this obstruction is not there: the oblivious minimax expected regret for this problem satisfies \[ \frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T}. \]
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。