Online Reinforcement Learning in Stochastic Games
This work addresses the challenge of efficient learning in competitive Markov environments for AI and game theory applications, representing an incremental improvement over prior methods.
The paper tackles the problem of online reinforcement learning in average-reward stochastic games by proposing the UCSG algorithm, which achieves sublinear regret against arbitrary opponents and finds an ε-maximin stationary policy with a sample complexity of poly(1/ε).
We study online reinforcement learning in average-reward stochastic games (SGs). An SG models a two-player zero-sum game in a Markov environment, where state transitions and one-step payoffs are determined simultaneously by a learner and an adversary. We propose the UCSG algorithm that achieves a sublinear regret compared to the game value when competing with an arbitrary opponent. This result improves previous ones under the same setting. The regret bound has a dependency on the diameter, which is an intrinsic value related to the mixing property of SGs. If we let the opponent play an optimistic best response to the learner, UCSG finds an $\varepsilon$-maximin stationary policy with a sample complexity of $\tilde{\mathcal{O}}\left(\text{poly}(1/\varepsilon)\right)$, where $\varepsilon$ is the gap to the best policy.