Depth-Limited Solving for Imperfect-Information Games
A fundamental challenge in imperfect-information games is that states do not have well-defined values. As a result, depth-limited search algorithms used in singleagent settings and perfect-information games do not apply. This paper introduces a principled way to conduct depth-limited solving in imperfect-information games by allowing the opponent to choose among a number of strategies for the remainder of the game at the depth limit. Each one of these strategies results in a different set of values for leaf nodes. This forces an agent to be robust to the different strategies an opponent may employ. We demonstrate the effectiveness of this approach by building a master-level heads-up no-limit Texas hold'em poker AI that defeats two prior top agents using only a 4-core CPU and 16 GB of memory. Developing such a powerful agent would have previously required a supercomputer.
Summary:  The paper proposes a modification of the continual resolving algorithm for depth-limited search in imperfect information games. Instead of counterfactual value network mapping joint beliefs to counterfactual values, it suggests using a function that maps a public state to a set of values of diverse best response strategies again an approximate Nash equilibrium strategy. This function can be precomputed, or realized either by function approximation of by Monte Carlo simulation based on pre-computed strategies. The authors show that this approach performs well in poker with small computational requirements.   Quality:  The core ideas of the paper are correct and interesting. There are several technical details that are unclear or overstated.  1) The most important problem are the inconsistencies regarding the blueprint strategy. The paper assumes at several places that the player plays based on a precomputed strategy \sigma^*_1. At the same time, the paper says that the player never plays based on the blueprint strategy. Since the blueprint strategy is created using abstraction, which leads to huge exploitability in HUNL, it is likely substantially different from the strategy computed and played online, especially when the opponent uses actions not included in the abstraction. All the theoretical guarantees relay on the player playing based on the blueprint strategy. Therefore, they make only a very limited sense and serve only as an inspiration for the heuristic approach actually evaluated in the paper. This is not clearly stated. I do not see how the theory can be useful unless the blueprint strategy already solves the game and therefore, there is no need for online computation. I ask the authors to elaborate on this in the rebuttal.  2) The second important weakness of the paper is the lack of experimental comparison with the state of the art. The paper spends whole page explaining reasons why the presented approach might perform better under some circumstances, but there is no hard evidence at all.  What is the reason not to perform an empirical comparison to the joint belief state approach and show the real impact of the claimed advantages and disadvantages? Since this is the main point of the paper, it should be clear when the new modification is useful.  3) Furthermore, there is an incorrect statement about the performance of the state of the art method. The paper claims that "The evidence suggests that in the domain we tested on, using multi-valued states leads to better performance." because the alternative approach "was never shown to defeat prior top AIs". This is simply incorrect. Lack of an experiment is not evidence for superiority of the method that performed the experiment without any comparison.  4) The rock-paper-scissors example is clearly inspired by an example that appeared in many previous work. Please, cite the source appropriately.  5) As explained in 1), the presented method is quite heuristic. The algorithm does not actually play the blueprint strategy, only few values are used in the leaf states, which cannot cover the whole variety of the best response values. In order to assess whether the presented approach might be applicable also for other games, it would be very useful to evaluate it on some substantially different domains, besides poker.  Clarity:  The paper is well written and organized, and it is reasonably easy to understand. The impact of the key differences between the theoretic inspiration and the practical implementation should be explained more clearly.  Originality:  The presented method is a novel modification of continual resolving. The paper clearly explains the main distinction form the existing method.   Significance:  The presented method seems to substantially reduce the computational requirements of creating a strong poker bot. If this proofs to be the case also for some other imperfect information games, it would be a very significant advancement in creating algorithms for playing these games.   Detailed comments:  190: I guess the index should be 1 339: I would not say MCCFR is currently the preferred solution method, since CFR+ does not work well with sampling 349: There is no evidence the presented method would work better in stratego. It would depend on the specific representation and how well would the NN generalize over the types of heuristics.  Reaction to rebuttal:  1) The formulation of the formal statement should be clearer. Still, while you are using the BR values from the blueprint strategy in the computation, I do not see how the theory can give you any real bounds the way you use the algorithm. One way to get more realistic bounds would be to analyze the function approximation version and use error estimates from cross-valiadation. 2) I do not believe head-to-head evaluation makes too much sense because of well known intransitivity effects. However, since the key difference between your algorithm and DeepStack is the form of the used leaf evaluation function, it would certainly not take man-years to replace the evaluation function with the joint belief in your framework. It would be very interesting to see comparison of exploitability and other trade-offs on smaller games, where we can still compute it. 4) I meant the use of the example for save resolving. 5) There is no need for strong agents for some particular games to make rigorous evaluation of equilibrium solving algorithms. You can compute exploitability in sufficiently large games to evaluate how close your approach is to the equilibrium. Furthermore, there are many domain independent algorithms for approaximating equilibriua in these games you can compare to. Especially the small number of best response values necessary for the presented approach is something that would be very interesting to evaluate in other games.  Line 339: I just meant that I consider CFR+ to be "the preferred domain-independent method of solving imperfect-information games", but it is not really important, it was a detailed comment.