arXiv:2511.00257cs.LGstat.ML2025-11被引 1
确定了专家建议下非随机多臂赌博机的最优后悔上界。
A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
- 通过构造紧致下界，匹配已有上界。
- 最优后悔率为 Θ(√(T K log(N/K)))。
- 适合研究在线学习与决策理论的学者。
我们通过证明一个与Kale（2014）上界相匹配的下界，确定了经典非随机多臂赌博机带专家建议问题的极小极大最优期望后悔。两个界限共同确定最小极大最优期望后悔为Θ(√(T K log(N/K)))，其中K为动作数，N为专家数，T为时间范围。
原文摘要 · Abstract (English)
We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be $Θ\left( \sqrt{T K \log (N/K) } \right)$, where $K$ is the number of arms, $N$ is the number of experts, and $T$ is the time horizon.
强化学习在线学习后悔分析
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。