Timezone: »

Online Learning with Costly Features and Labels
Navid Zolghadr · Gábor Bartók · Russell Greiner · András György · Csaba Szepesvari

Sun Dec 08 02:00 PM -- 06:00 PM (PST) @ Harrah's Special Events Center, 2nd Floor

This paper introduces the "online probing" problem: In each round, the learner is able to purchase the values of a subset of feature values. After the learner uses this information to come up with a prediction for the given round, he then has the option of paying for seeing the loss that he is evaluated against. Either way, the learner pays for the imperfections of his predictions and whatever he chooses to observe, including the cost of observing the loss function for the given round and the cost of the observed features. We consider two variations of this problem, depending on whether the learner can observe the label for free or not. We provide algorithms and upper and lower bounds on the regret for both variants. We show that a positive cost for observing the label significantly increases the regret of the problem.

Author Information

Navid Zolghadr (University of Alberta)
Gábor Bartók (Google Zürich)
Russell Greiner (University of Alberta)
András György (Google DeepMind)
Csaba Szepesvari (University of Alberta)

More from the Same Authors