Online learning and Blackwell approachability with partial monitoring: optimal convergence rates - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2017

Online learning and Blackwell approachability with partial monitoring: optimal convergence rates

Abstract

Blackwell approachability is an online learning setup generalizing the classical problem of regret minimization by allowing for instance multi-criteria optimization, global (online) optimization of a convex loss, or online linear optimization under some cumulative constraint. We consider partial monitoring where the decision maker does not necessarily observe the outcomes of his decision (unlike the traditional regret/bandit literature). Instead, he receives a random signal correlated to the decision–outcome pair, or only to the outcome. We construct, for the first time, approachability algorithms with convergence rate of order O(T −1/2 ) when the signal is independent of the decision and of order O(T −1/3 ) in the case of general signals. Those rates are optimal in the sense that they cannot be improved without further assumption on the structure of the objectives and/or the signals.
Fichier principal
Vignette du fichier
approachability-partial-optimal_1.pdf (223.11 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-02734035 , version 1 (02-06-2020)

Identifiers

  • HAL Id : hal-02734035 , version 1
  • PRODINRA : 481342

Cite

Joon Kwon, Vianney Perchet. Online learning and Blackwell approachability with partial monitoring: optimal convergence rates. 20. International Conference on Artificial Intelligence and Statistics (AISTATS), Apr 2017, Fort Lauderdale, United States. ⟨hal-02734035⟩
18 View
19 Download

Share

Gmail Facebook X LinkedIn More