Repeated Games with Vector Losses: A Set-valued Dynamic Programming Approach

We consider infinitely repeated games with vector losses discounted over time. We characterize the set of minimal upper bounds on expected losses that a player can simultaneously guarantee across the different dimensions. Specifically, we show that this set is the fixed point of a set-valued dynamic programming operator. This approach also characterizes the strategies that achieve these bounds. These optimal strategies are shown to be independent of the player's own past actions and stationary relative to a compact state space obtained by parameterizing the set of the minimal bounds. We also present a computational procedure to approximate this set and the optimal strategies. We discuss two applications of our results: 1) characterization of the optimal strategy of the uninformed player in zero-sum discounted repeated games with incomplete information on one side; 2) characterization of the minmax optimal regret and the regret-optimal strategy in repeated games with discounted losses. Our approximation procedure can be used to compute approximately optimal strategies in both these applications. We illustrate this procedure by computing approximately regret-optimal strategies for the problem of prediction using expert advice from two and three experts under $\{0,1\}-$losses. Our numerical evaluations demonstrate improved performance over existing algorithms for this problem.