We study the problem of decision-theoretic online learning (DTOL). Motivated
by practical applications, we focus on DTOL when the number of actions is very
large. Previous algorithms for learning in this framework have a tunable
learning rate parameter, and a barrier to using online-learning in practical
applications is that it is not understood how to set this parameter optimally,
particularly when the number of actions is large.
In this paper, we offer a clean solution by proposing a novel and completely
parameter-free algorithm for DTOL. We introduce a new notion of regret, which
is more natural for applications with a large number of actions. We show that
our algorithm achieves good performance with respect to this new notion of
regret; in addition, it also achieves performance close to that of the best
bounds achieved by previous algorithms with optimally-tuned parameters,
according to previous notions of regret.

本文聚焦于大量行动决策问题的决策理论在线学习（DTOL）。我们提出了一种全新无需参数的算法用于 DTOL，这解决了在线学习因无法在实际中优化设定学习率参数的困境。此外，我们引入了一种新的错误度量标准，该算法可以在此标准和以前的标准下实现优异的表现，接近以前有优化参数的最佳预算。