Online Reinforcement Learning in Stochastic Games
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 ε-maximin stationary policy with a sample complexity of O (poly(1/ε)), where ε is the gap to the best policy.
The paper considers the problem of online learning in two-player zero-sum stochastic games. The main result is constructing a strategy for player 1 that guarantees that the cumulative rewards will never go below the maximin value of the game by more than a certain bound, no matter what strategy the other player follows. The bound is shown to grow sublinearly in the number of rounds T of the game, and polynomially on other problem parameters such as the diameter, the size of the state and action spaces. The results imply that the proposed algorithm can be used in self-play to compute near-maximin strategies for both players. The algorithm and the analysis are largely based on the UCRL algorithm of Auer and Ortner (2007) and the analysis thereof.
I have reviewed a previous version of the paper for ICML'17, and have to say that the quality of the writing has improved quite a bit; the authors obviously invested a lot of effort into improving the readability of the paper. The paper is of course still very technical with most of the analysis details deferred to the appendix. Being already familiar with the analysis, I cannot objectively judge how easy it is to follow for first-time readers (I believe that it still looks rather intimidating), but I am now entirely convinced that the proofs are correct. Since the previous round of reviews, the authors fixed all the technical issues I've pointed out, so at this point, I have no technical objections.
The contribution itself is novel and interesting: the paper proposes a new (but very natural) regret definition suitable for stochastic games and proposes an efficient algorithm that comes with strong guarantees on the proposed regret notion. The fact that such strong results are actually possible was quite surprising to me.
All in all, I think that this paper is ready to be published.
Detailed comments
=================
-definition of \rho^* after line 83: at this point, the existence of the limit is not ensured. Please at least say that this requires some mild assumptions that will be specified later.
-112: Assumptions 1 and 2: Maybe it would be useful to use different letters for the two diameter notions to avoid confusion. 
-154: "Player 1 optimistically picks one model"---Well, not entirely optimistically, as the choice of the opponent's policy is done conservatively. Please rephrase for clarity.
-186: This Lemma 4 is very informal; please state explicitly that this is not the full statement of the lemma. Also, the statement itself is written a bit strangely.
-189: "analyzing techniques" -> "analysis techniques"
-195: "our algorithm makes [...]" -> "our algorithm uses policy [...]"
-261: Please highlight the fact that \pi_i^2 is a non-stationary policy, and in general all policies discussed in this section can be non-stationary.