2025/06/08 by Jiarui Gan, Gan, Jiarui, Rupak Majumdar +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2506.07186
openalex publication_date 2025/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of computing optimal correlated equilibria (CEs) in infinite-horizon multi-player stochastic games, where correlation signals are provided over time. In this setting, optimal CEs require history-dependent policies; this poses new representational and algorithmic challenges as the number of possible histories grows exponentially with the number of time steps. We focus on computing (ε, δ)-optimal CEs -- solutions that achieve a value within ε of an optimal CE, while allowing the agents' incentive constraints to be violated by at most δ. Our main result is an algorithm that computes an (ε,δ)-optimal CE in time polynomial in 1/(εδ(1 - γ))n+1, where γ is the discount factor, and n is the number of agents. For (a slightly more general variant of) turn-based games, we further reduce the complexity to a polynomial in n. We also establish that the bi-criterion approximation is necessary by proving matching inapproximability bounds. Our technical core is a novel approach based on inducible value sets, which leverages a compact representation of history-dependent CEs through the values they induce to overcome the representational challenge. We develop the value-set iteration algorithm -- which operates by iteratively updating estimates of inducible value sets -- and characterize CEs as the greatest fixed point of the update map. Our algorithm provides a groundwork for computing optimal CEs in general multi-player stochastic settings.