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: | Borkar Vivek, Jain Rahul, Kalathil Dileep |
Keywords: | stochastic processes, graphs |
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.