Skip to yearly menu bar Skip to main content


A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent

Mehdi Jafarnia · Rahul Jain · Ashutosh Nayyar

MR1 & MR2 - Number 43
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT

Abstract: In this paper, we propose Posterior Sampling Reinforcement Learning for Zero-sum Stochastic Games (PSRL-ZSG), the first online learning algorithm that achieves Bayesian regret bound of $\tilde\mathcal{O}(HS\sqrt{AT})$ in the infinite-horizon zero-sum stochastic games with average-reward criterion.Here $H$ is an upper bound on the span of the bias function, $S$ is the number of states, $A$ is the number of joint actions and $T$ is the horizon.We consider the online setting where the opponent can not be controlled and can take any arbitrary time-adaptive history-dependent strategy.Our regret bound improves on the best existing regret bound of $\tilde\mathcal{O}(\sqrt[3]{DS^2AT^2})$ by Wei et al., (2017) under the same assumption and matches the theoretical lower bound in $T$.

Live content is unavailable. Log in and register to view live content