Blackwell's Approachability with Time-Dependent Outcome Functions and Dot Products. Application to the Big Match
Kwon, Joon; Ziliotto, Bruno (2023), Blackwell's Approachability with Time-Dependent Outcome Functions and Dot Products. Application to the Big Match. https://basepub.dauphine.psl.eu/handle/123456789/24827
View/ Open
Type
Document de travail / Working paperExternal document link
https://hal.science/hal-04046399Date
2023Series title
Cahier de recherche CEREMADE, Université Paris Dauphine-PSLPublished in
Paris
Pages
16
Metadata
Show full item recordAuthor(s)
Kwon, Joon
Mathématiques et Informatique Appliquées [MIA Paris-Saclay]
Ziliotto, Bruno
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)
Blackwell's approachability is a very general sequential decision framework where a Decision Maker obtains vector-valued outcomes, and aims at the convergence of the average outcome to a given "target" set. Blackwell gave a sufficient condition for the decision maker having a strategy guaranteeing such a convergence against an adversarial environment, as well as what we now call the Blackwell's algorithm, which then ensures convergence. Blackwell's approachability has since been applied to numerous problems, in online learning and game theory, in particular. We extend this framework by allowing the outcome function and the dot product to be time-dependent. We establish a general guarantee for the natural extension to this framework of Blackwell's algorithm. In the case where the target set is an orthant, we present a family of time-dependent dot products which yields different convergence speeds for each coordinate of the average outcome. We apply this framework to the Big Match (one of the most important toy examples of stochastic games) where an ϵ-uniformly optimal strategy for Player I is given by Blackwell's algorithm in a well-chosen auxiliary approachability problem.Related items
Showing items related by title and author.
-
Doss, Halim (2011) Article accepté pour publication ou publié
-
Trabelsi, Saber; Mauser, Norbert; Bardos, Claude; Catto, Isabelle (2009) Article accepté pour publication ou publié
-
Dolbeault, Jean; Rein, Gerhard (2001) Article accepté pour publication ou publié
-
Bardos, Claude; Catto, Isabelle; Mauser, Norbert; Trabelsi, Saber (2010) Article accepté pour publication ou publié
-
Dolbeault, Jean (1999) Document de travail / Working paper