Approachability in Stackelberg Stochastic Games with Vector Costs Academic Article uri icon


  • 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.

published proceedings


author list (cited authors)

  • Kalathil, D., Borkar, V. S., & Jain, R.

citation count

  • 6

complete list of authors

  • Kalathil, Dileep||Borkar, Vivek S||Jain, Rahul

publication date

  • September 2017