Budgeted Prediction with Expert Advice

Kareem Amin, Satyen Kale, Gerald Tesauro, Deepak S. Turaga

AAAI 2015 pp. 2490-2496

doi:10.1609/AAAI.V29I1.9621 /aaai/2015/amin2015aaai-budgeted/

Abstract

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(sqrt(C log(N)T/B)), where C is the total cost of all experts. We complement this upper bound with a nearly matching lower bound Omega(sqrt(CT/B)) on the regret of any algorithm for this problem. We also provide experimental validation of our algorithm.

PDF AAAI Semantic Scholar

Cite

Text

Amin et al. "Budgeted Prediction with Expert Advice." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9621

Markdown

[Amin et al. "Budgeted Prediction with Expert Advice." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/amin2015aaai-budgeted/) doi:10.1609/AAAI.V29I1.9621

BibTeX

@inproceedings{amin2015aaai-budgeted,
  title     = {{Budgeted Prediction with Expert Advice}},
  author    = {Amin, Kareem and Kale, Satyen and Tesauro, Gerald and Turaga, Deepak S.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {2490-2496},
  doi       = {10.1609/AAAI.V29I1.9621},
  url       = {https://mlanthology.org/aaai/2015/amin2015aaai-budgeted/}
}