Detailed Instructions: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Problem:In this paper, we study a variant of the framework of online learning using expert advice with limited/bandit feedback. We consider each expert as a learning entity, seeking to more accurately reflecting certain real-world applications. In our setting, the feedback at any time t is limited in a sense that it is only available to the expert i that has been selected by the central algorithm (forecaster), i.e., only the expert i receives feedback from the environment and gets to learn at time t. We consider a generic black-box approach whereby the forecaster does not control or know the learning dynamics of the experts apart from knowing the following no-regret learning property: the average regret of any expert j vanishes at a rate of at leastO(t j ) with tj learning steps where [0, 1] is a parameter. In the spirit of competing against the best action in hindsight in multi-armed bandits problem, our goal here is to be competitive w.r.t. the cumulative losses the algorithm could receive by following the policy of always selecting one expert. We prove the following hardness result: without any coordination between the forecaster and the experts, it is impossible to design a forecaster achieving no-regret guarantees. In order to circumvent this hardness result, we consider a practical assumption allowing the forecaster to "guide" the learning process of the experts by filtering/blocking some of the feedbacks observed by them from the environment, i.e., not allowing the selected expert i to learn at time t for some time steps. Then, we design a novel no-regret learning algorithm LEARNEXP for this problem setting by carefully guiding the feedbacks observed by experts. We prove that LEARNEXP achieves the worst-case expected cumulative regret ofO(T 1 2 ) after T time steps and matches the regret bound of (T 1 2 ) for the special case of multi-armed bandits.
Solution:
Learning to Use Learners' Advice