Exploration par optimisation dans le suivi partiel

Résumé

Nous fournissons un nouvel algorithme pour la surveillance partielle adversariale à k actions et à d résultats qui est adaptatif, intuitif et efficace. Le point fort est que pour les jeux non dégénérés localement observables, le regret minimax à n tours est limité par 6m k^(3/2) sqrt(n log(k)), où m est le nombre de signaux. Cela correspond à la meilleure limite supérieure connue en théorie de l'information, dérivée de la dualité minimax bayésienne. Le même algorithme obtient également un regret quasi-optimal pour les jeux à information complète, les jeux de bandits et les jeux globalement observables. Des bornes de probabilité élevées et des expériences simples sont également fournies.