analiza aiqbench
This paper advances online learning theory by introducing a Follow-the-Perturbed-Leader policy optimized for directed weakly observable feedback graphs, achieving near-linear time complexity and strong regret bounds in both adversarial and stochastic regimes. The core contribution lies in the novel graph-based loss estimator that integrates forced exploration and adaptive learning rates to maintain algorithmic simplicity while improving performance guarantees.
Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
arXiv:2611.04307v1 Announce Type: cross Abstract: We study online learning with directed weakly observable feedback graphs and propose a Follow-the-Perturbed-Leader (FTPL) policy that achieves best-of-both-worlds guarantee with nearly linear expected time complexity. To preserve the simple structure of FTPL, we develop a novel graph-based loss estimator that combines forced exploration, conditional geometric resampling and adaptive learning rates with surrogate probabilities. Our policy achieves $\tilde{\mathcal{O}}(\delta_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(\delta_* \log T / \Delta_{\min}^2)$ regret for stochastic regimes, where $\delta_*$ and $\Delta$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $\Theta(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.
Abstract:We study online learning with directed weakly observable feedback graphs and propose a Follow-the-Perturbed-Leader (FTPL) policy that achieves best-of-both-worlds guarantee with nearly linear expected time complexity. To preserve the simple structure of FTPL, we develop a novel graph-based loss estimator that combines forced exploration, conditional geometric resampling and adaptive learning rates with surrogate probabilities. Our policy achieves $\tilde{\mathcal{O}}(\delta_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(\delta_* \log T / \Delta_{\min}^2)$ regret for stochastic regimes, where $\delta_*$ and $\Delta$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $\Theta(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2611.04307 [stat.ML]
(or arXiv:2611.04307v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2611.04307 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 · 218 cuvinte