Workshop track -ICLR 2018 ADVERSARIAL POLICY GRADIENT FOR ALTERNATING MARKOV GAMES
Policy gradient reinforcement learning has been applied to two-player alternateturn zero-sum games, e.g., in AlphaGo, self-play REINFORCE was used to improve the neural net model after supervised learning. In this paper, we emphasize that two-player zero-sum games with alternating turns, which have been previously formulated as Alternating Markov Games (AMGs), are different from standard MDP because of their two-agent nature. We exploit the difference in associated Bellman equations, which leads to different policy iteration algorithms. As policy gradient method is a kind of generalized policy iteration, we show how these differences in policy iteration are reflected in policy gradient for AMGs. We formulate an adversarial policy gradient and discuss potential possibilities for developing better policy gradient methods other than self-play REINFORCE. The core idea is to estimate the minimum rather than the mean for the "critic". Experimental results on the game of Hex show the modified Monte Carlo policy gradient methods are able to learn better pure neural net policies than the REIN-FORCE variants. To apply learned neural weights to multiple board sizes Hex, we describe a board-size independent neural net architecture. We show that when combined with search, using a single neural net model, the resulting program consistently beats MoHex 2.0, the previous state-of-the-art computer Hex player, on board sizes from 9×9 to 13×13.
The paper makes the simple but important observation that (deep) reinforcement learning in alternating Markov games requires a min-max formulation of the Bellman equation as well as careful attention to the way in which one alternates solving for both players' policies in a policy iteration setting.
While some of the core algorithmic insights regarding Algorithms 3 & 4 in the paper stem from previous work (Condon, 1990; Hoffman & Karp, 1966), I was not actually aware of these previous results until I reviewed this paper.
A nice corollary of Algorithms 3 & 4 is that they make for a straightforward adaptation of policy gradient algorithms since when optimizing one policy, the other is fixed to the greedy policy.
In general, it would be nice to have the algorithms specified as formal algorithms as opposed to text-based outlines.  I found myself reading and re-reading descriptions to make sure I understood what math was being implied by the descriptions.
Section 6
> Hex is simpler than Go in the sense that perfect play can 
> often be achieved whenever virtual connections are found 
> by H-Search
It is not clear here what virtual connections are, what H-Search is, and how these imply perfect play, if perfect play as previously discussed is unknown.
Overall, the results on Hex for AMCPG-A and AMCPG-B vs. standard REINFORCE variants currently used are very encouraging.  That said, empirically it is always a question of whether these results are specific to Hex.  Because this paper is not proposing the best Hex player (i.e., the winning rate against Wolve never exceeds 0.5), I think it is quite reasonable to request the authors to compare AMCPG-A and AMCPG-B to standard REINFORCE variants on other games (they do not need to be as difficult as Hex).
Finally, assuming that the results do generalize to other games, I am left wondering about the significance of the contribution.  On one hand, the authors have introduced me to literature I was not aware of, but on the other hand, their actual novel contribution is a rather straightforward adaptation of ideas in the literature to policy gradients (that could be formalized in a more technically precise way) with an evaluation on a single type of game.  This is a useful contribution no doubt, but I am concerned with whether it meets the significance level that I am used to with accepted ICLR papers in previous years.