analiza aiqbench
This research establishes a fundamental lower bound on the learning speed of mean-based algorithms in multi-armed bandit settings with unknown horizons, clarifying their theoretical limits relative to established no-regret methods. The authors propose two new variants that generalize standard approaches like $\epsilon$-greedy and Exp3, demonstrating through experiments that these can achieve competitive performance despite slower convergence rates. Ultimately, the work bridges the gap between mean-based strategies and regret minimization, offering a more nuanced understanding of algorithmic trade-offs in online learning environments.
Mean-based algorithms: A lower bound and regret
arXiv:2606.04931v2 Announce Type: replace Abstract: Mean-based algorithms are online learning algorithms that assign low probability to actions with low average rewards. Recent research shows that they converge to serially undominated actions, which serve as approximations to Nash equilibria in economic games. However, empirical studies indicate that mean-based algorithms converge more slowly in bandit-feedback settings than established no-regret alternatives. This work investigates mean-based algorithms under unknown horizons and bandit feedback. In this setting, we provide the first lower bound on the algorithm-defining sequence $\gamma_t$, establishing a fundamental limit on the learning speed of such algorithms. In multi-armed bandit problems, this result constrains the rate at which any algorithm can reliably identify low-reward actions while acting according to this knowledge. We also propose two mean-based algorithms: one generalizes $\epsilon$-greedy, and the other extends 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 study the relationship to regret. Depending on the choice of $\gamma_t$, the intersection with no-regret algorithms is non-trivial, and we show that some algorithms are both mean-based and no-regret.
Abstract:Mean-based algorithms are online learning algorithms that assign low probability to actions with low average rewards. Recent research shows that they converge to serially undominated actions, which serve as approximations to Nash equilibria in economic games. However, empirical studies indicate that mean-based algorithms converge more slowly in bandit-feedback settings than established no-regret alternatives. This work investigates mean-based algorithms under unknown horizons and bandit feedback. In this setting, we provide the first lower bound on the algorithm-defining sequence $\gamma_t$, establishing a fundamental limit on the learning speed of such algorithms. In multi-armed bandit problems, this result constrains the rate at which any algorithm can reliably identify low-reward actions while acting according to this knowledge. We also propose two mean-based algorithms: one generalizes $\epsilon$-greedy, and the other extends 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 study the relationship to regret. Depending on the choice of $\gamma_t$, the intersection with no-regret algorithms is non-trivial, and we show that some algorithms are both mean-based and no-regret.
Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT)
arXiv:2606.04931 [cs.LG]
(or arXiv:2606.04931v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.04931 Focus to learn more arXiv-issued DOI via DataCite
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 · 5 iun. 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