Mean-based algorithms: A lower bound and regret
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 $γ_t$, establishing a fundamental limit on the learning speed of such algorithms. In multi-armed bandit proble...
| Authors | Julius Durmann, Amelie Kleber |
|---|---|
| Primary category | cs.LG |
| Published | 3 June 2026 |
| Last updated at source | 6 October 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.