Trading Regret Rate for Computational Efficiency in Online Learning with Limited Feedback
published: Aug. 26, 2009, recorded: June 2009, views: 3106
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
We study low regret algorithms for online learning with limited feedback, where there is an additional constraint on the computational power of the learner. Focusing on multi-armed bandit with side information, we demonstrate cases in which there is a trade-off between the regret rate and the computational efficiency of the online learning algorithm. In particular, for the class of linear hypotheses we show that the EXP4 prediction strategy achieves the optimal regret but is not efficient. In contrast, we propose much more efficient strategies, still with a vanishing regret, but a worse regret rate.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !