On the Value of Stochastic Side Information in Online Learning
This work addresses the challenge of enhancing online learning algorithms with side information, which is incremental as it builds on classical regret bounds by incorporating stochastic elements.
The paper tackles the problem of leveraging stochastic side information in deterministic online learning to improve prediction performance against an expert class, showing that regret can be negative when the side information is more powerful than the experts, compared to the classical O(√n) regret scaling.
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.