  We study the effectiveness of stochastic side information in deterministic
online learning scenarios. We propose a forecaster to predict a deterministic
sequence where its performance is evaluated against an expert class. We assume
that certain stochastic side information is available to the forecaster but not
the experts. We define the minimax expected regret for evaluating the
forecasters performance, for which we obtain both upper and lower bounds.
Consequently, our results characterize the improvement in the regret due to the
stochastic side information. Compared with the classical online learning
problem with regret scales with O(\sqrt(n)), the regret can be negative when
the stochastic side information is more powerful than the experts. To
illustrate, we apply the proposed bounds to two concrete examples of different
types of side information.
