Advice-Efficient Prediction with Expert Advice
This work addresses a cost-efficient variant of expert advice prediction, which is incremental as it builds on existing frameworks by limiting advice queries.
The paper tackles the problem of prediction with expert advice when only a limited number of expert recommendations can be queried per round, presenting an algorithm that achieves O(√(N/M * T * ln N)) regret over T rounds.
Advice-efficient prediction with expert advice (in analogy to label-efficient prediction) is a variant of prediction with expert advice game, where on each round of the game we are allowed to ask for advice of a limited number $M$ out of $N$ experts. This setting is especially interesting when asking for advice of every expert on every round is expensive. We present an algorithm for advice-efficient prediction with expert advice that achieves $O(\sqrt{\frac{N}{M}T\ln N})$ regret on $T$ rounds of the game.