Experts with Lower-Bounded Loss Feedback: A Unifying Framework
This work provides a unifying framework for understanding expert problems under partial feedback, which is significant for researchers working on online learning algorithms.
This paper introduces a new feedback model for the best expert problem, where an adversary provides a lower bound on the loss of each expert in addition to bandit feedback. The authors prove optimal regret bounds (up to logarithmic factors) for modified Exp3 algorithms, unifying and generalizing results for both bandit and full-information settings.
The most prominent feedback models for the best expert problem are the full information and bandit models. In this work we consider a simple feedback model that generalizes both, where on every round, in addition to a bandit feedback, the adversary provides a lower bound on the loss of each expert. Such lower bounds may be obtained in various scenarios, for instance, in stock trading or in assessing errors of certain measurement devices. For this model we prove optimal regret bounds (up to logarithmic factors) for modified versions of Exp3, generalizing algorithms and bounds both for the bandit and the full-information settings. Our second-order unified regret analysis simulates a two-step loss update and highlights three Hessian or Hessian-like expressions, which map to the full-information regret, bandit regret, and a hybrid of both. Our results intersect with those for bandits with graph-structured feedback, in that both settings can accommodate feedback from an arbitrary subset of experts on each round. However, our model also accommodates partial feedback at the single-expert level, by allowing non-trivial lower bounds on each loss.