Posterior sampling for reinforcement learning (PSRL) is a useful framework for making decisions in an unknown environment. PSRL maintains a posterior distribution of the environment and then makes planning on an environment sampled from the posterior distribution. Though PSRL works well on single-agent reinforcement learning problems, how to apply PSRL to multi-agent reinforcement learning problems is largely unexplored. In this work, we extend PSRL to twoplayer zero-sum extensive-games with imperfect information (TZIEG), which is a class of multi-agent systems. Technically, we combine PSRL with counterfactual regret minimization (CFR), which is a leading algorithm for TZIEG with a known environment. Our main contribution is a novel design of interaction strategies. With our interaction strategies, our algorithm provably converges to the Nash Equilibrium at a rate of O( √ log T /T ). Empirical results show that our algorithm works well.
PSRL
------
This work considers the task of finding a Nash equilibrium in a two-player zero-sum imperfect information game, where some aspects of the game are not known to the agents (specifically, the chance node probabilities, and the reward function). 
The authors propose a method based on PSRL, i.e. at each iteration a set of game parameters are sampled from the posterior of the distribution. Then, CFR is applied in the inner loop; but instead of finding the NE strategy, one player finds the strategy that basically maximizes the reward deviation between two games sampled from the posterior, given that the opponent is playing Nash in the first game.
The authors prove convergence bounds for their algorithm, and demonstrate its performance on Leduc Hold'em with game parameters randomly chosen from a Dirichlet distribution.
-------------------------
I agree with the authors that standard CFR suffers from the requirement that the full game is known, so it doesn't work well in its standard form when the environment is not known. There *are* other regret minimizers that do work in the model-free setting ([1], [2], [3]), none of which are discussed by the authors.
I also find the proposed setting somewhat unconvincing. The authors are considering a situation where the environment is unknown, but it's not the RL setting because you still must control both (opposing!) agents. Of course, you can't actually find a Nash Equilibrium if you can't control the other player (because they might just never explore part of the game tree). But you would want your algorithm to be a regret minimizer regardless of your partner's strategy. Is this true of the proposed algorithm?
The proposed interaction strategy described in Eq. 5 and 6 is clever: basically, each player explores a part of the tree that maximizes the difference in payoffs between the two sampled games. This seems a bit inefficient thouggh, why doesn't the agent just find the BR to \sigma_{-i} under \tilde{d} given that the opponent plays the NE under d? I don't see why you would want to explore parameters that have a high reward uncertainty if there's a different strategy that does better than the whole confidence interval. It's like UCB: you should play a strategy not with the highest uncertainty, but with the highest optimistic payoff.
I think the work could be substantially improved by comparing against model-free baselines, e.g. fictitious self-play [2], CFR with outcome sampling [1]. The current work deosn't provide any evidence of what benefits the Bayesian approach provides over model-free regret minimization. Especially since the Bayesian approach presumably does not scale as well due to the requirement of maintaining beliefs over all possible games, and the requirement that a correct prior is provided. I would be curious to see Bayesian and model-free appraoches compared in games of different sizes to see how the different methods scale.
Nits:
- such as the private pokers in poker games (private cards)
- h_1, h_1 \in H^C, are independent
- The reference to Neil 2018 should be "Neil Burch", not "Burch Neil"
- And if you're going to say "we can directly apply the technique from [100-page PhD thesis]", please mention the page number.
[1] Lanctot, Marc, et al. "Monte Carlo sampling for regret minimization in extensive games." Advances in neural information processing systems. 2009.
[2] Heinrich, Johannes, Marc Lanctot, and David Silver. "Fictitious self-play in extensive-form games." International Conference on Machine Learning. 2015.
[3] Srinivasan, Sriram, et al. "Actor-critic policy optimization in partially observable multiagent environments." Advances in Neural Information Processing Systems. 2018.