均值算法在未知时域与 bandit 反馈下的下界与 regret 研究

该研究首次给出均值算法定义序列 γ_t 的下界，揭示了此类算法学习速度的根本限制。作者提出两种均值算法，一种泛化 ε-greedy，另一种将均值 Exp3 扩展到未知时域。实验显示均值算法虽略慢，但在 bandit 反馈下可与其他算法竞争，且部分算法同时具备均值与 no-regret 性质。