Probabilistic methods often need to draw samples from a nontrivial distribution. A * sampling is a nice algorithm by building upon a top-down construction of a Gumbel process, where a large state space is divided into subsets and at each round A * sampling selects a subset to process. However, the selection rule depends on a bound function, which can be intractable. Moreover, we show that such a selection criterion can be inefficient. This paper aims to improve A * sampling by addressing these issues. To design a suitable selection rule, we apply Probability Matching, a widely used method for decision making, to A * sampling. We provide insights into the relationship between A * sampling and probability matching by analyzing a nontrivial special case in which the state space is partitioned into two subsets. We show that in this case probability matching is optimal within a constant gap. Furthermore, as directly applying probability matching to A * sampling is time consuming, we design an approximate version based on Monte-Carlo estimators. We also present an efficient implementation by leveraging special properties of Gumbel distributions and well-designed balanced trees. Empirical results show that our method saves a significantly amount of computational resources on suboptimal regions compared with A * sampling.
Summary: This paper introduces a probability matching approach for optimizing Gumbel processes, i.e. the extension of the Gumbel-Max trick to more general measure spaces. The basic idea is to use a more refined subset selection mechanism as compared to A* Sampling, but at the cost of being able to guarantee an exact sample. Instead, the authors study the algorithm's best Gumbel so far as a function of the time budget. 
Quality: This is an interesting and natural idea, and the experiments support the author's claim that it improves over A* Sampling in the regimes that they consider. The claims and proofs look correct to me.
Originality: This idea has not been explored in the literature, and is a sensible one to consider when having an exact sample is not necessary. 
Clarity: The comparison to A* Sampling is a bit apples-to-oranges and the paper lacks some clarity overall. In particular, the authors should be much more clear that their termination condition necessarily differs from A* Sampling's. In A* Sampling the termination condition guarantees that the algorithm has found the true optimum, but in PM-A* the authors consider only a fixed budget of time --- terminating whether or not the algorithm has found the true optimum. The difference is a necessary feature, because otherwise I'm fairly sure A* Sampling is optimal (It has to push the upper bound of every subset below the true maximum, so if the term. cond. is not currently satisfied the subset with the current max. upper bound must eventually be visited before termination. Since it is the only subset where that is necessarily true, taking it is the optimal choice.) More comments below.
Significance: I think this is interesting work, but I would recommend the authors consider some examples that clarify where these ideas might impact that problems that the ICLR audience would be interested in.
Overall: The paper's clarity problems get in the way of its contribution. I think it is an interesting direction, but the authors are not clear enough about the correctness of the algorithm (it is not guaranteed to return an exact sample) to recommend acceptance. If this and other issues are fixed, it would be a good paper.
Pros:
- Solid contribution to the literature on Gumbels.
- Beginnings of a regret analysis.
- Uniform performance gains in comparison to A* Sampling (in the regime considered).
Cons:
- Lacks clarity in comparisons to A* Sampling.
- Writing could clarify significance as well.
Specific questions / suggestions:
- One of the important omissions of the paper is the following question. What is the distribution of PM-A*'s output at time T for a fixed T? It won't be the target distribution in general, but it may be close. This applicability of this work will be greatly improved by that analysis.
- In general the figures and experiments need more details. In particular,
(1) In figure 2a, why are there two sets of lines? Different values of T?
(2) You need to report T throughout.
(3) What did you take as Y? This is a critical part of the method, and you should report the estimator used.
- In A* Sampling for two subsets without splitting algorithm,  shouldn't you be removing ALL previous Xi from  be S_i? i.e. S_i \ {Xi_1, Xi_2, ... Xi_{k-1}} or something like that.