  We study the adversarial online learning problem and create a completely
online algorithmic framework that has data dependent regret guarantees in both
full expert feedback and bandit feedback settings. We study the expected
performance of our algorithm against general comparators, which makes it
applicable for a wide variety of problem scenarios. Our algorithm works from a
universal prediction perspective and the performance measure used is the
expected regret against arbitrary comparator sequences, which is the difference
between our losses and a competing loss sequence. The competition class can be
designed to include fixed arm selections, switching bandits, contextual
bandits, periodic bandits or any other competition of interest. The sequences
in the competition class are generally determined by the specific application
at hand and should be designed accordingly. Our algorithm neither uses nor
needs any preliminary information about the loss sequences and is completely
online. Its performance bounds are data dependent, where any affine transform
of the losses has no effect on the normalized regret.
