  We study the prediction with expert advice setting, where the aim is to
produce a decision by combining the decisions generated by a set of experts,
e.g., independently running algorithms. We achieve the min-max optimal dynamic
regret under the prediction with expert advice setting, i.e., we can compete
against time-varying (not necessarily fixed) combinations of expert decisions
in an optimal manner. Our end-algorithm is truly online with no prior
information, such as the time horizon or loss ranges, which are commonly used
by different algorithms in the literature. Both our regret guarantees and the
min-max lower bounds are derived with the general consideration that the expert
losses can have time-varying properties and are possibly unbounded. Our
algorithm can be adapted for restrictive scenarios regarding both loss feedback
and decision making. Our guarantees are universal, i.e., our end-algorithm can
provide regret guarantee against any competitor sequence in a min-max optimal
manner with logarithmic complexity. Note that, to our knowledge, for the
prediction with expert advice problem, our algorithms are the first to produce
such universally optimal, adaptive and truly online guarantees with no prior
knowledge.
