Articles

Set-Valued Approachability and Online Learning with Partial Monitoring

S. MANNOR, V. PERCHET, G. STOLTZ

Journal of Machine Learning Research

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

Departments: Economics & Decision Sciences

Keywords: 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