Approachability in Stackelberg Stochastic Games with Vector Costs

Approachability in Stackelberg Stochastic Games with Vector Costs

0.00 Avg rating0 Votes
Article ID: iaor20172976
Volume: 7
Issue: 3
Start Page Number: 422
End Page Number: 442
Publication Date: Sep 2017
Journal: Dynamic Games and Applications
Authors: , ,
Keywords: stochastic processes, graphs
Abstract:

The notion of approachability was introduced by Blackwell (Pac J Math 6(1):1–8, 1956) in the context of vector‐valued repeated games. The famous ‘Blackwell’s approachability theorem’ prescribes a strategy for approachability, i.e., for ‘steering’ the average vector cost of a given agent toward a given target set, irrespective of the strategies of the other agents. In this paper, motivated by the multi‐objective optimization/decision‐making problems in dynamically changing environments, we address the approachability problem in Stackelberg stochastic games with vector‐valued cost functions. We make two main contributions. Firstly, we give a simple and computationally tractable strategy for approachability for Stackelberg stochastic games along the lines of Blackwell’s. Secondly, we give a reinforcement learning algorithm for learning the approachable strategy when the transition kernel is unknown. We also recover as a by‐product Blackwell’s necessary and sufficient conditions for approachability for convex sets in this setup and thus a complete characterization. We give sufficient conditions for non‐convex sets.

Reviews

Required fields are marked *. Your email address will not be published.