Before revision:  Our method -- Online Double Oracle (ODO) -- achieves the  regret bound of \mathcal{O}(\sqrt{T k \log(k)}) in self-play setting where k is NOT the size of the game , but rather the size of \emph{effective strategy set} that is linearly dependent on the support size of the Nash equilibrium .
After revision:  Our method -- Online Double Oracle (ODO) -- is provably convergent to a Nash equilibrium (NE). Most importantly, unlike normal DO methods, ODO is regret bound of \mathcal{O}(\sqrt{T k \log(k)}) in self-play setting where k is NOT the size of the game , but rather the size of \emph{effective strategy set} that is linearly dependent on the support size of the Nash equilibrium .