Multiarmed Bandits With Limited Expert Advice
This addresses a theoretical challenge in online learning for researchers, offering a solution to a known open problem with tight bounds.
The paper solves the COLT 2013 open problem by providing an algorithm for multiarmed bandits with limited expert advice, achieving a regret bound of ilde{O}(\sqrt{ rac{\min\{K, M\} N}{M} T}) and proving a nearly tight lower bound of ilde{\Omega}(\sqrt{ rac{\min\{K, M\} N}{M} T}).
We solve the COLT 2013 open problem of \citet{SCB} on minimizing regret in the setting of advice-efficient multiarmed bandits with expert advice. We give an algorithm for the setting of K arms and N experts out of which we are allowed to query and use only M experts' advices in each round, which has a regret bound of \tilde{O}\bigP{\sqrt{\frac{\min\{K, M\} N}{M} T}} after T rounds. We also prove that any algorithm for this problem must have expected regret at least \tildeΩ\bigP{\sqrt{\frac{\min\{K, M\} N}{M}T}}, thus showing that our upper bound is nearly tight.