Online Learning with Uncertain Feedback Graphs
  Online learning with expert advice is widely used in various machine learning
tasks. It considers the problem where a learner chooses one from a set of
experts to take advice and make a decision. In many learning problems, experts
may be related, henceforth the learner can observe the losses associated with a
subset of experts that are related to the chosen one. In this context, the
relationship among experts can be captured by a feedback graph, which can be
used to assist the learner's decision making. However, in practice, the nominal
feedback graph often entails uncertainties, which renders it impossible to
reveal the actual relationship among experts. To cope with this challenge, the
present work studies various cases of potential uncertainties, and develops
novel online learning algorithms to deal with uncertainties while making use of
the uncertain feedback graph. The proposed algorithms are proved to enjoy
sublinear regret under mild conditions. Experiments on real datasets are
presented to demonstrate the effectiveness of the novel algorithms.
