An adaptive algorithm for finite stochastic partial monitoring (extended version)

An adaptive algorithm for finite stochastic partial monitoring (extended version). Bartók, G., Zolghadr, N., & Szepesvári, C. In ICML, pages 1–20, 06, 2012.

Paper abstract bibtex 1 download

We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual regret. Most importantly, the algorithm is adaptive in the sense that if the opponent strategy is in an "easy region" of the strategy space then the regret grows as if the problem was easy. As an implication, we show that under some reasonable additional assumptions, the algorithm enjoys an O(T^1/2) regret in Dynamic Pricing, proven to be hard by Bartok et al. (2011).

@inproceedings{BarZolSze1206,
	abstract = {We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual regret. Most importantly, the algorithm is adaptive in the sense that if the opponent strategy is in an "easy region" of the strategy space then the regret grows as if the problem was easy. As an implication, we show that under some reasonable additional assumptions, the algorithm enjoys an O(T^{1/2}) regret in Dynamic Pricing, proven to be hard by Bartok et al. (2011).},
	acceptrate = {243 out of 890=27.3\%},
	author = {Bart{\'o}k, G. and Zolghadr, N. and Szepesv{\'a}ri, Cs.},
	booktitle = {ICML},
	keywords = {partial information, online learning, stochastic partial monitoring, minimax bounds, theory},
	month = {06},
	pages = {1--20},
	title = {An adaptive algorithm for finite stochastic partial monitoring (extended version)},
	url_paper = {adaptive_partmon_full.pdf},
	year = {2012}}

Downloads: 1