Blackwell's approachability in stackelberg stochastic games: A learning version
Dileep M. Kalathil, Vivek S. Borkar, Rahul Kumar Jain · 2014
The notion of approachability was introduced by Blackwell (Blackwell, 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 player towards a given target set, irrespective of the strategies of the other players. In this paper, motivated by the multi-objective optimization and decision making problems in dynamically changing environments, we address the approachability problem for Stackelberg stochastic games with vector-valued cost functions. We give two results. First, we give a simple and computationally tractable strategy for approachability. Second, we give a reinforcement learning based algorithm to learn the approachable strategy when the transition kernel corresponding to the underlying dynamics is unknown. We also show that the conditions that we give for approachability are both necessary and sufficient for convex sets and thus giving a complete characterization.