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
TypeDocument de travail / Working paper
External document linkhttps://hal.science/hal-04046399
Series titleCahier de recherche CEREMADE, Université Paris Dauphine-PSL
MetadataShow full item record
Mathématiques et Informatique Appliquées [MIA Paris-Saclay]
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.
Showing items related by title and author.
Global-in-time existence of solutions to the multiconfiguration time-dependent Hartree-Fock equations: A sufficient condition Trabelsi, Saber; Mauser, Norbert; Bardos, Claude; Catto, Isabelle (2009) Article accepté pour publication ou publié
Time-dependent rescalings and Lyapunov functionals for the Vlasov-Poisson and Euler-Poisson systems, and for related models of kinetic equations, fluid dynamics and quantum physics 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é