analiza aiqbench
This research advances the theoretical understanding of Lipschitz bandits by rigorously analyzing performance under arbitrary feedback delays, providing new regret bounds for both stochastic and adversarial reward settings. The study is significant because it quantifies how latency impacts learning efficiency in continuous action spaces without degrading to worse-than-known limits when no delay exists.
Lipschitz Bandits with Arbitrary Feedback Delays
arXiv:2608.15036v1 Announce Type: new Abstract: 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.
Abstract: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.
Machine Learning (cs.LG)
arXiv:2608.15036 [cs.LG]
(or arXiv:2608.15036v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2608.15036 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 216 cuvinte
Subiecte conexe
Uplifting conversion across the acquisition funnel with personalization using contextual bandits on AWS
AWS · 1 oct. 2026
Capacity-Constrained Online Convex Optimization with Delayed Feedback
arXiv · 12 iun. 2026
Near-Optimal Stochastic Linear Bandits with Delay
arXiv · 16 iun. 2026
Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
arXiv · 19 aug. 2026