Learning Nash in Constrained Markov Games With an α-Potential

We develop a best-response algorithm forsolving constrained Markov games assuming limited viola-tions for the potential game property. The limited violationsof the potential game property mean that changes invalue function due to unilateral policy alterations can bemeasured by the potential function up to an error alpha.We show the existence of stationary is an element of-approximate con-strained Nash policy whenever the set of feasible stationarypolicies is non-empty. Our setting has agents accessingan efficient probably approximately correct solver for aconstrained Markov decision process which they use forgenerating best-response policies against the other agents'former policies. For an accuracy threshold is an element of>4 alpha, thebest-response dynamics generate provable convergence to is an element of-Nash policy in finite time with probability at least 1-delta atthe expense of polynomial bounds on sample complexitythat scales with the reciprocal of is an element of and delta