  We address the problem of sequential prediction with expert advice in a
non-stationary environment with long-term memory guarantees in the sense of
Bousquet and Warmuth [4]. We give a linear-time algorithm that improves on the
best known regret bounds [26]. This algorithm incorporates a relative entropy
projection step. This projection is advantageous over previous weight-sharing
approaches in that weight updates may come with implicit costs as in for
example portfolio optimization. We give an algorithm to compute this projection
step in linear time, which may be of independent interest.
