Set-Valued Approachability and Online Learning with Partial Monitoring
Abstract
Approachability has become a standard tool in analyzing learning algorithms in the adversarial online learning setup. We develop a variant of approachability for games where there is ambiguity in the obtained reward: it belongs to a set rather than being a single vector. Using this variant we tackle the problem of approachability in games with partial monitoring and develop a simple and generally efficient strategy (i.e., with constant per-step complexity) for this setup. As an important example, we instantiate our general strategy to the case when external regret or internal regret is to be minimized under partial monitoring.
Cite
Text
Mannor et al. "Set-Valued Approachability and Online Learning with Partial Monitoring." Journal of Machine Learning Research, 2014.Markdown
[Mannor et al. "Set-Valued Approachability and Online Learning with Partial Monitoring." Journal of Machine Learning Research, 2014.](https://mlanthology.org/jmlr/2014/mannor2014jmlr-setvalued/)BibTeX
@article{mannor2014jmlr-setvalued,
title = {{Set-Valued Approachability and Online Learning with Partial Monitoring}},
author = {Mannor, Shie and Perchet, Vianney and Stoltz, Gilles},
journal = {Journal of Machine Learning Research},
year = {2014},
pages = {3247-3295},
volume = {15},
url = {https://mlanthology.org/jmlr/2014/mannor2014jmlr-setvalued/}
}