We develop a novel and generic algorithm for the adversarial multi-armed
bandit problem (or more generally the combinatorial semi-bandit problem). When
instantiated differently, our algorithm achieves various new data-dependent
regret bounds improving previous work. Examples include: 1) a regret bound
depending on the variance of only the best arm; 2) a regret bound depending on
the first-order path-length of only the best arm; 3) a regret bound depending
on the sum of first-order path-lengths of all arms as well as an important
negative term, which together lead to faster convergence rates for some normal
form games with partial feedback; 4) a regret bound that simultaneously implies
small regret when the best arm has small loss and logarithmic regret when there
exists an arm whose expected loss is always smaller than those of others by a
fixed gap (e.g. the classic i.i.d. setting). In some cases, such as the last
two results, our algorithm is completely parameter-free.
The main idea of our algorithm is to apply the optimism and adaptivity
techniques to the well-known Online Mirror Descent framework with a special
log-barrier regularizer. The challenges are to come up with appropriate
optimistic predictions and correction terms in this framework. Some of our
results also crucially rely on using a sophisticated increasing learning rate
schedule.

提出了一种新颖的算法，采用乐观性和适应性技术，结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题，并在提高先前工作的同时，取得了多种新的数据依赖性遗憾界。