Kareem Amin, Satyen Kale, Gerald Tesauro, and Deepak Turaga
Proceedings of 29th AAAI Conference on Artificial Intelligence (AAAI), 2015

We consider a budgeted variant of the problem of learning from expert advice with $$N$$ experts. Each queried expert incurs a cost and there is a given budget $$B$$ on the total cost of experts that can be queried in any prediction round. We provide an online learning algorithm for this setting with regret after $$T$$ prediction rounds bounded by $$O\!\!\left(\sqrt{\tfrac{C}{B}\ \log(N)T}\right)$$, where $$C$$ is the total cost of all experts. We complement this upper bound with a nearly matching lower bound $$\Omega\!\left(\sqrt{\tfrac{C}{B}\ T}\right)$$ on the regret of any algorithm for this problem. We also provide experimental validation of our algorithm.