Nonstochastic Bandits with Infinitely Many Experts
This work addresses a theoretical limitation in online learning for scenarios with infinitely many experts, offering incremental improvements in regret bounds.
The paper tackles the problem of nonstochastic bandits with expert advice by extending it from finitely to infinitely many experts, proposing a meta-algorithm that achieves a regret upper bound of $ ilde{\mathcal{O}} ig( i^*K + \sqrt{KT} ig)$ up to polylog factors, with optimal regret when $i^* = ilde{\mathcal{O}} ig( \sqrt{T/K} ig)$.
We study the problem of nonstochastic bandits with expert advice, extending the setting from finitely many experts to any countably infinite set: A learner aims to maximize the total reward by taking actions sequentially based on bandit feedback while benchmarking against a set of experts. We propose a variant of Exp4.P that, for finitely many experts, enables inference of correct expert rankings while preserving the order of the regret upper bound. We then incorporate the variant into a meta-algorithm that works on infinitely many experts. We prove a high-probability upper bound of $\tilde{\mathcal{O}} \big( i^*K + \sqrt{KT} \big)$ on the regret, up to polylog factors, where $i^*$ is the unknown position of the best expert, $K$ is the number of actions, and $T$ is the time horizon. We also provide an example of structured experts and discuss how to expedite learning in such case. Our meta-learning algorithm achieves optimal regret up to polylog factors when $i^* = \tilde{\mathcal{O}} \big( \sqrt{T/K} \big)$. If a prior distribution is assumed to exist for $i^*$, the probability of optimality increases with $T$, the rate of which can be fast.