ML Anthology

Minimizing Wide Range Regret with Time Selection Functions

Subhash Khot, Ashok Kumar Ponnuswami
COLT 2008 pp. 81-86
doi:10.1002/jbm.820070205 /colt/2008/khot2008colt-minimizing/

Abstract

We consider the problem of minimizing regret with respect to a given set S of pairs of time selection functions and modifications rules. We give an online algorithm that has O ( √ T log |S|) regret with respect to S when the algorithm is run for T time steps and there are N actions allowed. This improves the upper bound of O ( √ T N log(|I||F|)) given by Blum and Mansour [BM07a] for the case when S = I × F for a set I of time selection functions and a set F of modification rules. We do so by giving a simple reduction that uses an online algorithm for external regret as a black box. 1

PDF Semantic Scholar

Cite

Text

Khot and Ponnuswami. "Minimizing Wide Range Regret with Time Selection Functions." Annual Conference on Computational Learning Theory, 2008. doi:10.1002/jbm.820070205

Markdown

[Khot and Ponnuswami. "Minimizing Wide Range Regret with Time Selection Functions." Annual Conference on Computational Learning Theory, 2008.](https://mlanthology.org/colt/2008/khot2008colt-minimizing/) doi:10.1002/jbm.820070205

BibTeX

@inproceedings{khot2008colt-minimizing,
  title     = {{Minimizing Wide Range Regret with Time Selection Functions}},
  author    = {Khot, Subhash and Ponnuswami, Ashok Kumar},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2008},
  pages     = {81-86},
  doi       = {10.1002/jbm.820070205},
  url       = {https://mlanthology.org/colt/2008/khot2008colt-minimizing/}
}