6 - Prediction with Limited Feedback

Summary

Introduction

This chapter investigates several variants of the randomized prediction problem. These variants are more difficult than the basic version treated in Chapter 4 in that the forecaster has only limited information about the past outcomes of the sequence to be predicted. In particular, after making a prediction, the true outcome y_t is not necessarily revealed to the forecaster, and a whole range of different problems can be defined depending on the type of information the forecaster has access to.

One of the main messages of this chapter is that Hannan consistency may be achieved under significantly more restricted circumstances, a surprising fact in some of the cases described later. The price paid for not having full information about the outcomes is reflected in the deterioration of the rate at which the per-round regret approaches 0.

In the first variant, investigated in Sections 6.2 and 6.3, only a small fraction of the outcomes is made available to the forecaster. Surprisingly, even in this “label efficient” version of the prediction game, Hannan consistency may be achieved under the only assumption that the number of outcomes revealed after n prediction rounds grows faster than log(n)log log(n).

Section 6.4 formulates prediction problems with limited information in a general framework. In the setup of prediction under partial monitoring, the forecaster, instead of his own loss, only receives a feedback signal. The difficulty of the problem depends on the relationship between losses and feedbacks.