在延迟反馈下解决连续动作空间的最优选择问题。
Lipschitz Bandits with Arbitrary Feedback Delays
- 基于消除和EXP3思想设计新算法应对延迟反馈。
- 理论证明延迟导致额外约√D的误差，总误差为T^(d_z+1)/(d_z+2) + √D。
- 适用于有延迟反馈的在线优化场景，如推荐系统、自适应控制。
Lipschitz带宽问题将传统多臂老虎机扩展到连续动作空间，假设奖励函数满足Lipschitz条件。本文研究在任意反馈延迟下的Lipschitz带宽问题，即动作执行后奖励信号需经过任意延迟才可获取。考虑随机与对抗性奖励设定，分别提出基于消除和EXP3的算法。在两种设定下，算法在时间跨度T内达到 ilde{O}ig(T^{ rac{d_z+1}{d_z+2}}+ extstyle rac{D}{ extstyle T}+ extstyle rac{ extstyle D^{1/2}}{ extstyle T}ig)的后悔界，其中总延迟为D，主要差异在于缩放维度d_z的定义。该结果与无延迟情况下的现有后悔界一致，并量化了反馈延迟带来的额外 ilde{O}( extstyle rac{D^{1/2}}{ extstyle T})影响。
原文摘要 · Abstract (English)
The Lipschitz bandit problem extends the traditional multi-armed bandit framework to continuous action spaces by assuming that the reward functions satisfy a Lipschitz condition. This work investigates Lipschitz bandits under arbitrary feedback delays, where reward signals are not received immediately upon taking an action but after an arbitrarily chosen delay. We consider both stochastic and adversarial reward settings, proposing an elimination-based algorithm and an EXP3-based algorithm, respectively. For both settings, our algorithms achieve a regret bound of $\tilde{O}\left(T^{\frac{d_z+1}{d_z+2}}+\sqrt{D}\right)$ over a time horizon $T$ with total delay $D$, where the main difference between settings lies in the definition of the zooming dimension $d_z$. Our bounds match existing delay-free regret guarantees for Lipschitz bandits and characterize the additional $\tilde{O}(\sqrt{D})$ impact introduced by feedback delays.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。