Approachability in Stackelberg Stochastic Games with Vector Costs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2016, Springer Science+Business Media New York. The notion of approachability was introduced by Blackwell (Pac J Math 6(1):18, 1956) in the context of vector-valued repeated games. The famous Blackwells 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 Blackwells. 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 Blackwells 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.
