Parameter-free Online Linear Optimization with Side Information via
  Universal Coin Betting
  A class of parameter-free online linear optimization algorithms is proposed
that harnesses the structure of an adversarial sequence by adapting to some
side information. These algorithms combine the reduction technique of Orabona
and P{\'a}l (2016) for adapting coin betting algorithms for online linear
optimization with universal compression techniques in information theory for
incorporating sequential side information to coin betting. Concrete examples
are studied in which the side information has a tree structure and consists of
quantized values of the previous symbols of the adversarial sequence, including
fixed-order and variable-order Markov cases. By modifying the context-tree
weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed
algorithm is further refined to achieve the best performance over all adaptive
algorithms with tree-structured side information of a given maximum order in a
computationally efficient manner.
