analiza aiqbench
This study establishes a theoretical lower bound for mean-based online learning algorithms, formally defining the speed limits of their convergence under unknown time horizons. While these methods exhibit slightly slower convergence than established bandit-feedback algorithms, they remain competitively performant and can satisfy no-regret criteria depending on specific parameter choices. The work clarifies the trade-offs between exploitability and convergence speed, offering a more rigorous framework for selecting algorithms in economic game settings.
Mean-based algorithms: A lower bound and regret
arXiv:2606.04931v1 Announce Type: new Abstract: Mean-based algorithms are a class of online learning algorithms that assign low probability to actions with low average rewards. Recent work indicates these algorithms converge favorably to serially undominated actions, which approximate Nash equilibria in economic games. However, empirical studies also show slower convergence compared to established algorithms in bandit-feedback scenarios. We study mean-based algorithms when the time horizon is unknown and only bandit feedback is available. In this setting, we provide the first lower bound on the algorithm-defining sequence $\gamma_t$ that formally establishes a limit on how fast these algorithms can learn. Additionally, we propose two mean-based algorithms: one generalizes $\epsilon$-greedy, and the other extends the mean-based Exp3 to unknown horizons. Our experiments show that mean-based algorithms, although slightly slower, can perform competitively with other bandit-feedback algorithms. We further analyze the relationship to no-regret algorithms. Depending on the choice of $\gamma_t$, the intersection with no-regret algorithms is non-trivial, and we show that algorithms exist that are both mean-based and no-regret. This adds context to the "exploitability" of this class of algorithms that previous contributions suggest.
Abstract:Mean-based algorithms are a class of online learning algorithms that assign low probability to actions with low average rewards. Recent work indicates these algorithms converge favorably to serially undominated actions, which approximate Nash equilibria in economic games. However, empirical studies also show slower convergence compared to established algorithms in bandit-feedback scenarios. We study mean-based algorithms when the time horizon is unknown and only bandit feedback is available. In this setting, we provide the first lower bound on the algorithm-defining sequence $\gamma_t$ that formally establishes a limit on how fast these algorithms can learn. Additionally, we propose two mean-based algorithms: one generalizes $\epsilon$-greedy, and the other extends the mean-based Exp3 to unknown horizons. Our experiments show that mean-based algorithms, although slightly slower, can perform competitively with other bandit-feedback algorithms. We further analyze the relationship to no-regret algorithms. Depending on the choice of $\gamma_t$, the intersection with no-regret algorithms is non-trivial, and we show that algorithms exist that are both mean-based and no-regret. This adds context to the "exploitability" of this class of algorithms that previous contributions suggest.
Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT)
arXiv:2606.04931 [cs.LG]
(or arXiv:2606.04931v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.04931 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 · 276 cuvinte
Subiecte conexe
Mean-based algorithms: A lower bound and regret
arXiv · 7 oct. 2026
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
arXiv · 17 aug. 2026
Ranking Bandits for Carousel Interfaces with Observable Browsing Depth
arXiv · 6 oct. 2026
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance
arXiv · 27 iul. 2026