Online Learning and Blackwell Approachability in Quitting Games
Flesh, Janos; Laraki, Rida; Perchet, Vianney (2016), Online Learning and Blackwell Approachability in Quitting Games, in Vitaly Feldman; Alexander Rakhlin; Ohad Shamir, 29th Annual Conference on Learning Theory (COLT), Proceedings of Machine Learning Research (PMLR), p. 941-942
TypeCommunication / Conférence
External document linkhttps://hal.archives-ouvertes.fr/hal-03767990
Conference titleConference on Learning Theory (COLT 2016)
Conference countryUnited States
Book title29th Annual Conference on Learning Theory (COLT)
Book authorVitaly Feldman; Alexander Rakhlin; Ohad Shamir
MetadataShow full item record
Department of Quantitative Economics [Maastricht]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Centre de Recherche en Économie et Statistique [CREST]
Abstract (EN)We consider the sequential decision problem known as regret minimization, or more precisely its generalization to the vectorial or multi-criteria setup called Blackwell approachability. We assume that Nature, the decision maker, or both, might have some quitting (or terminating) actions so that the stream of payoffs is constant whenever they are chosen. We call those environments “quitting games”. We characterize convex target sets \cC that are Blackwell approachable, in the sense that the decision maker has a policy ensuring that the expected average vector payoff converges to \cC at some given horizon known in advance. Moreover, we also compare these results to the cases where the horizon is not known and show that, unlike in standard online learning literature, the necessary or sufficient conditions for the anytime version of this problem are drastically different than those for the fixed horizon.
Showing items related by title and author.