Title: Learning to Use Learners' Advice,
Abstract: 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^t$ that has been selected by
the central algorithm (forecaster), \emph{i.e.}, only the expert $i^t$ 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 least $O(t_j^{\regretRate-1})$ with $t_j$ learning steps where $\regretRate
\in [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, \emph{i.e.}, not allowing the
selected expert $i^t$ to learn at time $t$ for some time steps. Then, we design
a novel no-regret learning algorithm \algo for this problem setting by
carefully guiding the feedbacks observed by experts. We prove that \algo
achieves the worst-case expected cumulative regret of $O(\Time^\frac{1}{2 -
\regretRate})$ after $\Time$ time steps.