  The problem of online prediction with sequential side information under
logarithmic loss is studied, and general upper and lower bounds on the minimax
regret incurred by the predictor is established. The upper bounds on the
minimax regret are obtained by providing and analyzing a probability assignment
inspired by mixture probability assignments in universal compression, and the
lower bounds are obtained by way of a redundancy-capacity theorem. The tight
characterization of the regret is provided in some special settings.
