Set-Valued Approachability and Online Learning with Partial Monitoring
Shie Mannor, Vianney Perchet, Gilles Stoltz; 15(Oct):3247−3295, 2014.
AbstractApproachability 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.