- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposed a subgame solving approach for deep reinforcement learning in two-player zero-sum extensive-form games with a trained sampler to sample the state.
Critical strengths
- The writing of the paper is clear and easy to understand, especially the illustrations in Figure 1.
- The comparison with related work is comprehensive.
Critical weaknesses
- The code is unavailable.
- The benchmark games in this paper are too small. I would expect heads-up limit Texas hold'em/dark chess.
Questions for authors
How's the importance sampling factor incorporated into the training objective of the sampler? I would expect it to be large since it is the inverse of the reach probability.
6 comments
Thank you for your response!
Evaluation on Large Games
I think [1] could serve as a useful reference for evaluating the performance of test-time search in large games, such as dark chess. I would still expect to see experimental results on Texas Hold’em and/or dark chess.
Importance Sampling
Could you also report the variance of the importance-sampling factors and the average number of steps per game in each experiment?
[1] Zhang, Brian, and Tuomas Sandholm. "General search techniques without common knowledge for imperfect-information games, and application to superhuman fog of war chess." International Conference on Learning Representations. Vol. 2026. 2026.
Thank you for the ongoing discussion!
Large games
As we said, we agree that more evaluation is always better. However, we are still unsure whether experiments on Dark Chess or Texas Hold’em would bring any new insights into the paper. The goal of the large-scale experiment was to show that the additional training improves upon the blueprint and the update equivalence framework, which we explicitly state in line 427. We think that the results in the paper support this sufficiently.
While we could compare ourselves to Obscuro in Dark Chess, the comparison itself would not yield much useful insight, since the underlying algorithm used by Obscuro requires enumerating the states within an information set, which is not possible in the large Battleship. So even if Obscuro outperforms our method in Dark Chess, our approach is still applicable to a broader class of games. On the other hand, outperforming Obscuro would be a strong contribution of the paper, but not necessary, in our opinion.
Importance Sampling
We have added to Appendix B.3 a further description of the belief model. In it, we include the details about the normalization. The game lengths of the games we use are as follows:
Goofspiel X: X-1 actions per player
Leduc: at most 4 actions per player
Batteship 2x2: at most 4 actions per player
Battleship 7x7: 33 actions per player on average, at most 52 actions per player.
Battleship 10x10: 75 actions per player on average, at most 104 actions per player.
We would like to thank the reviewer for their review.
Codebase
We have included the code within the revision
Small benchmark games
We agree that more evaluation is always better, but we do not agree that the games we have used are too small, and we believe the results are representative of the performance in large games. The lower bounds on the game sizes for the Battleship variants we have used are following:
Battleship 7x7: 1038 unique states, 1032 unique decisions, 10133 nodes in the game tree and 10128 decisions if we assume perfect recall.
Battleship 10x10: 1073 unique states, 1065 unique decisions, 10328 nodes in the game tree, and 10320 decisions if we assume perfect recall.
The reason the game tree and decisions with perfect recall are so much higher is that they differentiate between the order of shots during gameplay (so shooting to Tile 1 and then Tile 2 is different from shooting to Tile 2 and then Tile 1).
We specifically decided to avoid Texas Hold 'em, as the variance in Poker requires at least tens of thousands of gameplays to estimate the quality of the strategy. With 10 seconds per decision, this may take several weeks just for gameplay experiments to yield reasonable estimates. Since the experiments we present already establish scalability of the method to large games, we considered this computation wasteful.
Importance Sampling
We use importance sampling as as Pjpi(w∣s)=Πt=0Tπj(sjt,ajt), where πj(sjtajt) is a probability player j played ajt in information set sjt at timestep t within the trajectory. So indeed, Pjpi(w∣s)1 can grow high in long games, because πj(sjtajt)≤1. However, several things can avoid blowup.
We agree that the importance sampling can grow. However, in order to keep unbiased estimates it is necessary to use it. It may be tempting to use the uniform strategy of the opponent for the sampling and then skip the importance sampling correction. However, this may introduce bias into the estimate.
Consider a game where Player 2 first selects between two decisions, then, based on the first decision, it either selects between 1000 actions or 2 actions. Now consider that Player 1 observes the ID of the action selected in the second round. If Player 1 observes an action with ID 1, then there are two states consistent with this hidden information, which correspond to these two sequences: 1,1; 2,1. As such, the belief model conditioned on the observation of Player 1 should sample, with 50% probability, the sequence 1,1 and, with 50% probability, the sequence 2,1. If you would only naively sample uniformly at each decision and avoid importance sampling, then the sequence 1, 1 would be sampled with probability 0.001⋅0.5 whereas the sequence 2, 1 would be sampled with probability 0.5⋅0.5.