Articles

Set-Valued Approachability and Online Learning with Partial Monitoring

S. MANNOR, V. PERCHET, G. STOLTZ

Journal of Machine Learning Research

octobre 2014, vol. 15, pp.3247-3295

Départements : Economie et Sciences de la décision

Mots clés : Online learning, Approachability, Regret, Partial monitoring

http://jmlr.org/papers/v15/mannor14a.html


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


JavaScriptSettings