We design and analyze minimax-optimal algorithms for online linear
optimization games where the player's choice is unconstrained. The player
strives to minimize regret, the difference between his loss and the loss of a
post-hoc benchmark strategy. The standard benchmark is the loss of the best
strategy chosen from a bounded comparator set. When the the comparison set and
the adversary's gradients satisfy L_infinity bounds, we give the value of the
game in closed form and prove it approaches sqrt(2T/pi) as T -> infinity.
Interesting algorithms result when we consider soft constraints on the
comparator, rather than restricting it to a bounded set. As a warmup, we
analyze the game with a quadratic penalty. The value of this game is exactly
T/2, and this value is achieved by perhaps the simplest online algorithm of
all: unprojected gradient descent with a constant learning rate.
We then derive a minimax-optimal algorithm for a much softer penalty
function. This algorithm achieves good bounds under the standard notion of
regret for any comparator point, without needing to specify the comparator set
in advance. The value of this game converges to sqrt{e} as T ->infinity; we
give a closed-form for the exact value as a function of T. The resulting
algorithm is natural in unconstrained investment or betting scenarios, since it
guarantees at worst constant loss, while allowing for exponential reward
against an "easy" adversary.

本文研究了无约束在线线性优化博弈中最小化后悔的算法，其中对于一个有界比较器集合，得到了该博弈的解及其渐进行为，同时针对更宽松的惩罚函数提出了相应的算法并得到了渐进解。