Adaptive Hedging under Delayed Feedback
This work addresses a specific challenge in online learning for scenarios with delayed feedback, representing an incremental advancement in hedging strategies.
The paper tackles the problem of online expert weight allocation under delayed feedback by developing the General Hedging algorithm, which achieves adversarial loss bounds in this setting and extends classical methods like Hedge and Fixed Share to handle delays.
The article is devoted to investigating the application of hedging strategies to online expert weight allocation under delayed feedback. As the main result, we develop the General Hedging algorithm $\mathcal{G}$ based on the exponential reweighing of experts' losses. We build the artificial probabilistic framework and use it to prove the adversarial loss bounds for the algorithm $\mathcal{G}$ in the delayed feedback setting. The designed algorithm $\mathcal{G}$ can be applied to both countable and continuous sets of experts. We also show how algorithm $\mathcal{G}$ extends classical Hedge (Multiplicative Weights) and adaptive Fixed Share algorithms to the delayed feedback and derive their regret bounds for the delayed setting by using our main result.