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.