arXiv：cs.LG· Julius Durmann, Amelie Kleber·· 7 小时前AI 评分33
基于均值的算法：下界与遗憾
Mean-based algorithms: A lower bound and regret
AI 导读
该研究在未知时间跨度和 bandit 反馈下考察 mean-based 算法，首次给出算法定义序列 γ_t 的下界，为该类算法的学习速度确立了根本限制。作者提出两种 mean-based 算法：一种泛化 ε-greedy，另一种将 mean-based Exp3 扩展到未知时间跨度。
正文
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.
| Subjects: | Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT) |
| Cite as: | arXiv:2606.04931 [cs.LG] |
| (or arXiv:2606.04931v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2606.04931 arXiv-issued DOI via DataCite |
Submission history
From: Julius Durmann [view email]
[v1]
Wed, 3 Jun 2026 14:23:41 UTC (1,778 KB)
[v2]
Tue, 6 Oct 2026 08:18:25 UTC (2,425 KB)
来源：arXiv：cs.LG · arxiv.org