SeeA*: Efficient Exploration-Enhanced A* Search by Selective Sampling

Authors: dengwei  zhao
shikui  tu
lei  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-01 14:59:14

Abstract: Monte-Carlo tree search (MCTS) and reinforcement learning contributed crucially to the success of AlphaGo and AlphaZero, and A$^*$ is a tree search algorithm among the most well-known ones in the classical AI literature. MCTS and  A$^*$ both perform heuristic search and are mutually beneficial. Efforts have been made to the renaissance of A$^*$ from three possible aspects, two of which have been confirmed by studies in recent years, while the third is about the OPEN list that consists of open nodes of A$^*$ search, but still lacks deep investigation. This paper aims at the third, i.e., developing the Sampling-exploration enhanced A$^*$ (SeeA$^*$) search by constructing a dynamic subset of OPEN through a selective sampling process, such that the node with the best heuristic value in this subset instead of in the OPEN is expanded. Nodes with the best heuristic values in OPEN are most probably picked into this subset, but sometimes may not be included, which enables SeeA$^*$ to explore other promising branches. Three sampling techniques are presented for comparative investigations. Moreover, under the assumption about the distribution of prediction errors, we have theoretically shown the superior efficiency of SeeA$^*$ over A$^*$ search, particularly when the accuracy of the guiding heuristic function is insufficient. Experimental results on retrosynthetic planning in organic chemistry, logic synthesis in integrated circuit design, and the classical Sokoban game empirically demonstrate the efficiency of SeeA$^*$, in comparison with the state-of-the-art heuristic search algorithms.

Main paper: 
 introduction: 
 In recent years, combining heuristic search algorithms with deep neural networks has demonstrated remarkable performance across a wide range of practical applications, such as board games [48, 50, 49, 66] , video games [46, 64, 67] , traveling salesman problem [8, 59] , de novo drug design [42] , retrosynthetic planning [6, 47, 68] , logic synthesis [9] , and so on. The search algorithm is a slow reasoning process, and heuristic functions serve as counselors to narrow down the search space [2] . Therefore, the effectiveness of search algorithms is significantly influenced by the quality of the guiding functions.Monte-Carlo tree search (MCTS) is a widely-used, effective algorithm for combinatorial problems. However, if the backup value in MCTS is provided by a heuristic estimator rather than actual rewards, the convergence to the true state value is not guaranteed, leading to compromised search performance. In single-agent problems such as combinatorial puzzles, neural-guided MCTS tends to have a relatively long runtime and often generates solutions that are considerably longer than the shortest path [1] .A * search [26] is a best-first search algorithm that expands nodes with the minimum total path value f at each step. The evaluation function f (n) on a node n is defined as the summation of g(n), the accumulated cost from the initial node n 0 to n, and h(n), the expected cost from n to the goal, i.e., f (n) = g(n) + h(n).(1)Notice that g(n) computes the cost from the known searching trajectory, whereas h(n) is a heuristic function to estimate the cost of the future path from n to the goal. In practice, it is usually difficult to obtain an accurate h(n). A * search is guaranteed to find the optimal solution if h(n) is admissible, i.e., h(n) never overestimates the real cost to the goal. However, due to its best-first expansion strategy, A * has limited exploration capability. If f (n) deviates from the true cost function f * (n) too much, A * search may become trapped in local optimal branches, and significant efforts are required to resume expansion within the optimal branch. Consequently, the computational efficiency of A * search is compromised in practical applications, even though the optimality of A * might still hold under the guidance of f (n).MCTS and A * both perform heuristic search. MCTS and reinforcement learning with the help of deep learning contributed crucially to the successes of AlphaGo and AlphaZero, which aroused the interest of comparing MCTS and A * for possible mutual benefits. Deep learning is also able to contribute to the renaissance of A * , three possible aspects are addressed with a family of possible improvements proposed under the name of Deep IA-search [61] . The first and also straightforward aspect is estimating f (n) with the help of deep learning, which makes current studies on A * including this paper into the era of learning aided A * . The second aspect is seeking a better estimation of f (n) with the help of global or future information, featured by two typical mechanisms. One is lookahead or scouting before expanding the current node to collect future information to revise f (n) of the current node, which takes a crucial rule for the success of AlphaGo [48] and also used more than 30 years ago in Algorithm CNneim-A [62] . The other is path consistency, that is, f (n) values on one optimal path should be identical, which has been further confirmed in recent studies [66, 67, 68] . This third aspect is about selecting nodes among the OPEN list that consists of open nodes of A * . It is an old tune even in the classical era of A * , e.g., one suggestion is dividing OPEN into two sublists OPEN and WAIT according to a priori and a posteriori in a Bayesian evaluation [61] . However, investigation is seldom made on what are effective and efficient ways for selecting among OPEN.In this paper, SeeA * search (short for Sampling-exploration enhanced A * ) algorithm is proposed by incorporating exploration behavior into A * search to target at the third aspect. The main contributions are summarized below. 2• SeeA * search employs a selective sampling process to screen a dynamic candidate subset D from the set O of open nodes that are awaiting expansion. The next expanding node is selected from D, and it may not be the node that has the best heuristic value in O and will be selected by A * , enabling SeeA * to explore other promising branches. To reduce the excessive expansion of unnecessary nodes during exploration, only the candidate node with the best heuristic value is expanded. Three sampling strategies are introduced to strike a balance between exploitation and exploration. The search efficiency is improved especially when the guiding heuristic function is not accurate enough.• We theoretically prove that SeeA * has superior efficiency over A * search when the heuristic value function deviates substantially from the true state value function. SeeA * achieves a reduced number of node expansions to identify the optimal path. This performance improvement becomes more pronounced as the complexity of the problems increases and the reliability of the guiding heuristics decreases.• Experiments are conducted on two real-world applications, i.e., the retrosynthetic planning problem in organic chemistry and the logic synthesis problem in integrated circuit design, as well as the classical Sokoban game. SeeA * outperforms the state-of-the-art heuristic search algorithms in terms of the problem-solving success rate and solution quality while maintaining a low level of node expansions. 
related work: 
 MCTS [5, 13] utilizes random sampling and tree-based search to efficiently explore search space. Upper Confidence bounds applied to Trees with predictor (PUCT) have been employed by AlphaZero [49] , achieving super-human performance in board games. A * search is widely employed for solving optimization problems, such as route planning [54, 53] , cubic and puzzle games [1] , robotics [17] , and so on. Many variants of A * search have been proposed for performance improvement. Weighted A * search (WA * ) [18] biased the expanding policy towards states closer to the goal byEQUATIONwhere ε is a hyperparameter to adjust the weight of the heuristic estimation h. WA * with iteratively decreasing weights is employed by the LAMA planner [27, 44] , achieving promising results in various domains including Sokoban. DeepCubeA [1] trained heuristic functions by reversing solution pathways from the goal state to guiding the search process of WA * . Commonly, WA * traded optimality for speed, and increasing ε was assumed to result in faster searches. Additionally, the greedy search based on h values was considered the fastest search. However, empirical observations revealed that increasing ε slowed down the search in some domains. Greedy search is fast if and only if there is a strong correlation between the heuristic estimations and the true distance-to-go, or if the heuristic is extremely accurate [55] . However, constructing a reliable heuristic function for complicated problems is challenging attributed to the vast search space and the difficulties associated with sample collection in real-world applications. Poor generalization performance also remains a pervasive issue across diverse practical domains, such as retrosynthetic planning. This paper sets out to develop an efficient search algorithm designed to minimize the adverse effects of inaccurate predictions by heuristic functions.There have been some preliminary studies on the integration of exploration into the A * search. ε-greedy node selection was incorporated into LAMA, suggesting that exploration can improve the coverage of search algorithms even multiple enhancements were already employed [52] . Type-WA * [11] augments WA * with type-based exploration [57] in the focal list [40] . The search space nodes are divided into T distinct groups, and one of these groups is randomly chosen to determine the expanded node. Levin tree search (LevinTS) [38] combined a penalization mechanism based on node depth to encourage exploration for A * search. Policy-guided heuristic search (PHS) [39] generalized LevinTS by introducing a heuristic factor, guided by both a value function and a policy. When the guiding heuristics are sufficiently accurate, the best-first search achieves optimal efficiency without the need for exploration. Insufficient exploration leads the search algorithm to be trapped in local optima guided by inaccurate heuristics. As the accuracy of the guiding heuristic diminishes, the importance of exploration becomes more pronounced in order to mitigate the potential misguidance.Search algorithms have played a crucial role in solving diverse real-world problems, such as retrosynthetic planning and logic synthesis. Retrosynthetic planning aims to identify a feasible synthetic route using known available building block molecules for a given target molecule. Considering that the synthesis of target molecules typically requires multiple steps and each step encompasses a substantial number of potential chemical reactions, retrosynthetic planning is formulated as a search problem to identify the optimal synthetic pathway. Both MCTS [28, 47, 65] and A * search, such as Retro * [6] and its descendants [24, 30, 33, 58] , have demonstrated promising results in retrosynthetic planning. Logic synthesis (LS) is a crucial step in the design of integrated circuits, mapping the high-level logic circuit description into gate-level implementation. In recent years, reinforcement learning algorithms [10, 29, 34, 41, 69] and search methods [9, 37] have shown promising results in the field of LS. Besides, Sokoban is an NP-hard [16] and PSPACE-complete [14] problem, which is a benchmark problem for evaluating the performance of artificial intelligence planning algorithms. Recently, combining reinforcement learning algorithms with search-based methods has demonstrated remarkable performance in effectively solving the Sokoban problem [19, 20, 22, 31, 43] . When the heuristic function f can accurately estimate the true cost f * , this best-first search is the most efficient. However, if the estimation by f is not accurate enough, the node with the minimum f value may not correspond to the optimal one, which instead has the lowest f * value. The search process might be trapped in a local optimal branch, and substantial computational efforts are required to resume expansion on the optimal branch, which diminishes the efficiency of the search algorithm.Considering an example in Figure 1 (a), suppose the cost for each step (or edge) on the optimal path is 100, and on the non-optimal path is only 1. The true total path cost at any node n is given by f* (n) = g(n) + h * (n), where g(n) is given by adding the costs from the root to the node n, and the real future cost h * (n) is a summation of all costs from n to the end (or terminal state). Suppose the evaluation function 1is exact on the optimal path but underestimates the real cost otherwise. Specifically, define the heuristic function h(n) as follows:f (n) = g(n) + h(n) by EquationEQUATIONThen, h(n) satisfies the admissible assumption as it never overestimates the cost, and h(n) ≤ h * (n) is established for all nodes. Therefore, A * is guaranteed to find the optimal solution guided by h(n) in Equation 3. However, as illustrated in Figure 1 (b), guided by the defined heuristic h, the nodes on the optimal path will not be expanded until all nodes on non-optimal branches with depths less than 200 have been expanded. The optimal solution is achieved within two steps under the guidance of f * , and the search efficiency of A * search is largely compromised when f (n) is not accurate enough. 
method: 
 SeeA * search is proposed on the basis of A As illustrated in Figure 1 (c)&(d), if the node with minimum f -value is not sampled into the candidate set D in Step 2a, the node selected to be expanded later is not the same as the one by A * search, which activates exploration on other branches.Step 2b excludes the unpromising nodes by the f -value. It should be noted that SeeA * with uniform sampling is different from the ε-Greedy method. The ε-Greedy activates exploration with probability ε and then uniformly samples a node for expansion, which may expand low-quality nodes. In Step 2a of SeeA * , uniform sampling is very likely to include at least one high-quality node with a reasonably low f -value and the node will be selected to expand in Step 2b. More discussions are referred to Appendix P.In the uniform sampling strategy, each node is selected with equal probability. However, there is a non-negligible probability that all sampled nodes are of low quality, leading to the exclusion of nodes along the optimal expansion path from the candidate set D. Therefore, a clustering sampling strategy is proposed, and it partitions open nodes into multiple clusters and subsequently sampling nodes from each cluster, as illustrated in Figure 2 in Appendix B. At least one node from each cluster is sampled compulsorily. Consequently, the probability of including nodes on the optimal branch is increased, thereby facilitating search efficiency. On the other hand, uniform sampling strategy is equivalent to assume that the nodes follow a Gaussian distribution, whereas clustering sampling strategy assumes that the nodes follow a Gaussian mixture distribution from multiple clusters, which provides a more descriptive representation for sampling.To reduce computational costs, competitive learning [51] is utilized for node clustering. After each node expansion, the incorporation of newly generated nodes into the set O resembles the process of online sample acquisition in competitive learning. A clustering process is conducted simultaneously with the search process. Offline clustering algorithms, such as K-means or Gaussian mixture model, require recalculating the clustering when incorporating new nodes, thereby imposing additional computational overhead. Each node is represented by a vector extracted by a function f h . N c cluster centers are randomly initialized as vectors with the same dimension of node embedding. During each expansion, the newly generated nodes are assigned to the cluster with the closest center separately, and the cluster center is updated by moving toward the position of the freshly added node. While preparing the candidate set D, nodes are sampled evenly from each cluster, and uniform sampling is employed to select nodes from each cluster. Details are displayed in Algorithm 3 & 5 in Appendix A.In AlphaZero [49] , PUCT achieved a good balance between exploitation and exploration with promising results. In light of this, a UCT-like sampling strategy is proposed. Due to the absence of Monte Carlo simulations, estimated f values are employed to substitute the Q value in PUCT, which is the average backup value obtained from multiple MCTS simulations. The depth of the node is employed as the penalization for exploration [38] . Each node is evaluated by [26] that the f * values of all nodes on the optimal path are equal to the same cost µ f 0 and lower than the f * value of nodes outside the optimal path, which was assumed to be sampled from a Gaussian distribution in [62] . In this paper, the prediction error for f * is assumed to follow a uniform distribution. Here, Gaussian distribution is denoted as G(•, •) and uniform distribution is denoted as U(•, •). Formally, an assumption is made as follows.EQUATIONAssumption 4.1 For each node n on the optimal path, f (n) ∼ U(µ f 0 -σ, µ f 0 + σ). For nodes not on the optimal path, f (n) ∼ U(f * (n) -σ, f * (n) + σ), and {f * (n)} are independently and identically sampled from G(µ f 1 , σ 2 s ).The µ f 0 and µ f 1 are the expected total cost for optimal and non-optimal solutions, respectively. The inequality µ f 0 < µ f 1 holds because the optimal path has a lower cost. The σ represents the magnitude of the prediction error, and the σ 2 s is a constant as the variance. Under Assumption 4.1, we can derive: Corollary 4.2 For a node n on the optimal path and a node n ′ off the optimal path, the probabilityEQUATIONdecreases as the prediction error σ increases. ItEQUATIONSeeA * expands n 1 with probabilityEQUATIONIf the uniform sampling strategy is used to select K candidates,EQUATIONBased on Equation 6& 8, when the prediction error σ is large, SeeA * expands the optimal node with a higher probability than A * search at each step, which is given by the following theorem. EQUATIONIn this situation, Inequality 9 holds. SeeA * tends to demonstrate superior performance compared to A * in solving complex problems.Notice that if the heuristic function f predicts the true cost f * without error, it leads to p σ = 1 in Equation 5. Then, Equation 9does not hold, and in this case, A * search becomes more efficient than SeeA * . However, learning an accurate heuristic function for complex real-world problems is quite challenging, and large prediction errors usually exist, which leads to small p σ and the establishment of Equation 9. The number of candidate nodes K is a key hyperparameter to balance the exploitation A * and the exploration introduced by SeeA * . P S (σ) in Equation 8reaches its maximum value when K * = -1/ log p σ . When p σ approaches 1, K * will be the largest ∞. In this situation, the candidate set is the same as the open set, and SeeA * degenerates into best-first A * . For small p σ , the optimal K * is the smallest value 1 and SeeA * becomes random sampling. An appropriate value of K should be selected according to the specific situation. According to Equation 7, P S (σ) is related to both p σ and P (n 1 ∈ D). Utilizing more efficient sampling algorithms than uniform sampling is also capable to enhance the performance of SeeA * . The clustering sampling and UCT-like sampling aim to achieve a higher P (n 1 ∈ D) by constructing a more diverse candidate set, thereby enhancing the likelihood of expanding the optimal node.For simplicity, suppose the probability of selecting the optimal node in a single expansion is P , and the probability for expanding the optimal node becomes 1 -(1 -P ) τ after τ expansions. To achieve a probability level of P min for expanding the optimal node, we haveEQUATION)Based on Theorem 4.3 and Equation 11, SeeA * is more efficient than A * search as it requires fewer expansions to find the optimal solution. It is noted that Equation 9 is derived on the uniform sampling strategy. For a more effective sampling strategy with a higher probability P (n 1 ∈ D), SeeA * will become more efficient as P S (σ) increases. 
experiments: 
 Real-world problems are usually complicated, and the amount of available samples for training the heuristic functions is typically small.Two real-world applications, i.e., retrosynthetic planning in organic chemistry and logic synthesis in integrated circuit (IC) design, are considered to evaluate the effectiveness of the proposed method. Since the molecular structures have enormous diversity but in contrast the available experimental data are very limited, the heuristic function to estimate the synthesis cost in retrosynthetic planning suffers from noticeable overfitting problems [68] . Furthermore, the vast chemical reaction space gives rise to a substantial number of branching factors in the search tree, leading to a rapid growth in the quantity of open nodes throughout the search process. Logic synthesis is another practical problem where it is challenging to train a reliable heuristic function to evaluate the solution's quality, due to the immense diversity of circuit functionalities and variations in design methodologies. Therefore, the above two real-world problems are suitable benchmarks to verify the efficiency of SeeA * when the heuristic function is not accurate enough. In addition, Sokoban is a widely-used benchmark for combinatorial optimization solvers. It only permits a maximum of four legal actions at each step, and simulations can be leveraged to generate a substantial amount of data for training high-quality heuristic value estimators. Sokoban is included to verify the impact of an accurate heuristic function on the searching performance. All experiments are conducted using NVIDIA Tesla V100 GPUs and an Intel(R) Xeon(R) Gold 6238R CPU.Chemical synthetic pathways are transformed into search trees following the literature [47] . A state is a set of molecules that are able to synthesize the target molecule. The initial state contains only the target molecule. The edges in the search tree represent the chemical reactions that enable state transitions between the connected nodes. The retrosynthetic planning problem is solved if all molecules within a state are available building blocks. A single-step retrosynthetic prediction model is utilized as the policy model to generate potential chemical reactions yielding the input molecule. The 50 chemical reaction templates with the highest probabilities constitute the set of valid actions for the current state. A heuristic function is employed to estimate the synthesis cost of the molecule, given the available building blocks. Each molecule is encoded using a 2048-dimensional Morgan Fingerprint vector [45] as the input for the heuristic functions. Both the single-step retrosynthetic prediction model and the cost estimator are provided by Retro * + [30] and used to guide the search algorithm. Details about the guiding heuristics are in Appendix D. The last hidden layer's output of the cost estimator is employed as the embedding representation of the input molecule.Experiments are conducted on the widely-used USPTO benchmark, comprising 190 molecules [6] .Commercially available molecules in eMolecules3 are used as building blocks. Since the invocation of the single-step retrosynthetic prediction model contributes the majority of the computational cost, all search algorithms are limited to a maximum of 500 single-step model calls, or 10 minutes of real-time, following previous works [6, 30] . The outputs of the single-step model are cached to avoid duplicate computation when the same molecule is encountered again [36] . The size of the candidate set is set to K = 50. In the clustering sampling, the parameter η is set to 0.15, and the number of clusters is 5. In the UCT-like sampling, the parameter c b is set to 0.35. Additional pruning is not considered. Since the prior policy is already clipped at a minimum value of 0.001, Bayes mixing with a uniform policy to avoid zero-probability is not used in LevinTS [38] and PHS [39] .The results on the USPTO benchmark are reported in Table 1 4 . Due to the exploration induced by selective sampling, the three SeeA * variants achieve superior performance in terms of the percentage of solved molecules and the average solution length while utilizing minimal wall-clock runtime. Among the three sampling strategies, the UCT-like sampling strategy achieves the best balance between exploration and exploitation. As in the literature [47] , predicting the synthetic cost of molecules is challenging, and the cost estimator is not accurate with a non-negligible prediction error σ. Then, it is expected and consistent with Theorem 4.3 that best-first search algorithms, including WA * and PHS, are less efficient because they excessively rely on the values of the heuristic function. MCTS requires more node expansions for problem-solving and generates solutions with longer lengths, which is consistent with the findings in the resolution of combinatorial puzzles [1] . The ε-Greedy node selection [52] achieves a success rate of 92.11%, surpassing the performance of A * search and demonstrating the practical benefits of introducing exploration when the reliability of guidance heuristics is compromised.Six additional datasets are collected from the literature for further comparisons. These datasets comprise 4719 molecules, much more than the USPTO dataset. Details of the datasets are referred to the Appendix E. According to the results in Table 3 & 4 in Appendix G, SeeA * maintains its superiority over other search algorithms, and SeeA * (Cluster) has the highest mean success rate of 63.56%. The clustering sampling and UCT-like sampling are better than uniform sampling in terms of the solved rate and the route length, indicating that the utilization of a superior sampling strategy is beneficial for the performance of SeeA * .For the logic synthesis problem, a Verilog-based hardware design is first converted into an andinverter-graph (AIG) representation, and then the AIG is optimized to have the lowest area-delay product (ADP) through a sequence of functionality-preserving transformations. The optimization is combinatorial because the sequence is constructed by selecting transformations one-by-one in order from a set. Following the literature, here the set is formed by seven legal transformations, and the sequence length is fixed at 10. The resyn2 transformation sequence is used as a baseline for comparisons [9, 10, 37] . More details about logic synthesis are in Appendix H. During the search 2.The results on the MCNC benchmark are presented in Table 2 5 . All three SeeA * variants outperform the existing methods in terms of the mean ADP reduction rates against the baseline resyn2.SeeA * (Cluster) achieves the highest ADP reduction (i.e., 23.5%), obviously surpassing the stateof-the-art ABC-RL's 20.9%. Guided by the same heuristic, SeeA * (Cluster) outperforms the A * search in 11 out of the 12 testing circuits. As illustrated by an example of the search process in Appendix K, the nodes expanded by A * tend to concentrate on a specific branch, whereas MCTS expands across multiple branches excessively due to its enforced exploration. SeeA * achieves a good balance between A * search and MCTS, ensuring that irrelevant branches are not unduly explored. The effects of three hyperparameters in SeeA * are empirically investigated below, i.e., the number of candidate nodes K, the number of clusters N c , and the adjustable weight c b in Equation 4.Experiments are conducted on the USPTO benchmark for the retrosynthesis planning problem. The number K is a critical parameter controlling the extent of exploration of SeeA * . When K = 1, the node to be expanded is solely determined by the selective sampling strategy, where the heuristic function has no impact on the selection. When K is too large, all opening nodes will be finally chosen as candidates because every node has a positive chance to be selected by the sampling strategy. In this case, SeeA * degenerates back to A * which highly depends on the heuristic function. When K is at an appropriate range, the sampling scheme endows SeeA * with helpful exploratory capability. It is observed from Figure 11 in Appendix O that a wide range of K enables SeeA * to obtain superior performance. For the extreme cases, SeeA * (K = 1) has the lowest success rate and longest solution length, and the performance of SeeA * (K = ∞), which is equivalent to A * , is also discounted.According to the results in Figure 12 in Appendix O, the performance of the clustering sampling strategy is generally very robust against the choices of N c . An inadequate number of clusters makes it towards uniform sampling by ignoring the differences among the nodes, while an excessive cluster number will distract the sampling process by noise in the node representation learning Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer:[Yes]Justification: The source code will be published once accepted.Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this paper, the SeeA * search is proposed to enhance the exploration behavior of the A * search by selecting expanded nodes from the sampled candidate nodes, rather than the entire set of open nodes. A node that is evaluated not to have the best estimated heuristic value may be selected and explored, thereby jumping out of the local optimum induced by inaccuracies in the heuristic function. Three sampling strategies are presented in the paper. Furthermore, we have theoretically established that SeeA * is more efficient than A * search when the estimation of heuristic functions is not accurate enough. Experiments on two diverse real-world applications in chemistry and circuit design and one puzzle-solving game demonstrate the efficiency of SeeA * .If the model exhibits precise state evaluation, the incorporation of exploration into A * search becomes redundant. However, in practical applications, where problems tend to be intricate or lack sufficient training data, obtaining accurately predictive heuristic functions is challenging. As suggested in Equation 7, in addition to reducing the prediction error σ, the probability of expanding the optimal nodes is also improved by using a smaller number of candidate nodes K to include the optimal node in the candidate set with a greater likelihood P (n 1 ∈ D). Screening candidate nodes reduces the search space, thereby enhancing search efficiency. Investigations on more effective sampling strategies will be conducted in future work. SeeA * will contribute to solving practical problems with limited samples. However, this work is still in the nascent stages without further applications related to people's daily lives currently, and thus there are no immediate ethical or harmful social impacts.A Pseudocodes for SeeA * and its sampling strategiesIn this section, pseudocode for the SeeA * search algorithm, and three sampling strategies: uniform sampling strategy, clustering sampling strategy, and UCT-like sampling strategy, are given. Algorithm 1 provides a comprehensive summary of the computational process of SeeA * . The algorithm begins by initializing the Open set Owith the initial node n 0 . In each step, a candidate set D is obtained using the sampling strategy F . The node with the minimum f value from the candidate set is selected to be expanded. If the algorithm reaches a goal state, it successfully finds a solution and terminates. Otherwise, the expanded node is moved to the Closed set C, and its child nodes are added to the Open set O. This process is repeated until the O becomes empty. S c = {S c 1 , S c 2 , • • • , S c Nc }, the number of candidate nodes K. Initialize D ← ∅ K e ← ⌈ K |S c | ⌉ for S c i ∈ S c do if |S c i | ≤ K e then D i ← S c i else D i ← Uniformly sample K e nodes from S c i end if D ← D ∪ D i end for return DThe clustering sampling strategy is summarized in Algorithm 3. The open nodes are divided into N c clusters, and an equal number of candidate nodes are sampled from each cluster. To sample K candidate nodes, each cluster requires sampling K c = ⌈ K |S c | ⌉ nodes. For each cluster, if the number of open nodes within this cluster does not exceed K c , all nodes are selected as candidate nodes. Otherwise, K c nodes are uniformly sampled as candidate nodes. To reduce computational overhead, competitive learning is employed for clustering, enabling avoidance of the need for re-clustering when new open nodes are added after each expansion. The algorithm for this competitive clustering process is displayed in Algorithm 5. N c clustering centers are initialized randomly. When a new node is added to the open set, it is assigned to the cluster whose center is closest to it, and the coordinates of that cluster center are updated by moving toward the position of the newly added node.UCT-like sampling strategy is provided in Algorithm 4, respectively. Each node n is evaluated by a statistic E(n) in Equation 4, which can achieve a balance between exploitation and exploration. The f value of the node is used to evaluate the quality and the depth d(n) is used to encourage exploration. for n ∈ CH(n) do w ← f h (n) j ← arg min w c i ∈W c ||w -w c i || S c j ← S c j ∪ {n} w c j ← w c j + η × (w -w c j ) end for return S c , W c 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: Considering the computation resources required, the error bar is not provided in this paper, but we are trying to make it available in the final version.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: As illustrated in the Experiments section, our experiments are conducted using NVIDIA Tesla V100 GPUs and an Intel(R) Xeon(R) Gold 6238R CPU Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The discussion on the impacts of the work is provided in the Conclusion section in Line 367 -369.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: SeeA * is an efficient search algorithm, and no specific model or dataset are employed.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: All assets used in this paper are publicly available.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: As shown in Figure 2 (a), the sampled nodes exhibit a uniform distribution overall, resulting in a proportional relationship between the number of sampled nodes within each cluster and the total number of nodes within each class. Clusters with fewer nodes are highly susceptible to the occurrence of no nodes being sampled as candidate nodes under limited sampling size. Therefore, this sampling strategy cannot effectively explore the various potential expansion directions. As depicted in Figure 2 (b), at least one node from each cluster is sampled compulsorily. Consequently, the probability of including nodes on the optimal branch is increased, thereby facilitating search efficiency.p σ is the probability of P (f (n) < f (n ′ )), in which n is the node on the optimal path and n ′ is the node on the non-optimal path. According to Assumption 4.1: EQUATIONEQUATIONEQUATIONEQUATIONIfEQUATIONIf µ 0 -2σ ≤ f * (n ′ ) < µ 0 :EQUATIONEQUATIONEQUATIONIn summary:EQUATIONWe have that:EQUATIONEQUATIONthen we want to prove thatEQUATIONEQUATIONEQUATIONIfEQUATIONEQUATIONIfEQUATIONEQUATION)EQUATIONEQUATIONTherefore, m(f * (n ′ )|σ) centrally symmetric about (µ f 0 , 1 2 ). Then we want to illustrate the monotonicity of the function m(µ f s |σ) about the variable σ, and σ > 0EQUATIONEQUATIONTherefore, as shown in Figure 3 ,P (f (n) ≤ f (n ′ )|f * (n ′ ), σ)is not always decrease with σ. However, on average, P (f (n) ≤ f (n ′ )|σ) will always decrease with σ, and we will prove this.For convenience, letEQUATIONBecause the function m is centrally symmetric about µ f 0 , 1 2 : Therefore:EQUATIONEQUATIONEQUATIONEQUATIONAssumption 4.1 gives µ f 1 > µ f 0 , and Equation 43 only considers the situation when f * (n ′ ) > µ f 0 . Therefore Equation 47 is not established and P (f * (n ′ )) ≥ P (2µ f 0 -f * (n ′ )). Therefore:EQUATIONEQUATION) Therefore, F (σ) is monotonic decreasing. The larger the estimation error σ, the less the probability ofP (f (n) < f (n ′ )|σ).The assumption in Corollary 4.2 that the prediction error for f * is uniformly distributed is quite strong. To further illustrate the applicability of the algorithm, we also prove that Corollary 4.2 is established if the noise follows a Gaussian distribution. Denoting Gaussian distribution as G(•, •), the assumption regarding the distribution of the estimated values will be adjusted to: Assumption C.1 For each node n on the optimal path, f (n) ∼ G(µ f 0 , σ 2 ). For nodes not on the optimal path, f (n) ∼ G(f * (n), σ 2 ), and f * (n) are independently and identically sampled from G(µ f 1 , σ 2 s ). µ f 0 < µ f 1 holds because the optimal path has a lower cost.For two Gaussian distributions, we have the following lemma [62, 67] :EQUATION2 ). If x, y are independent of each other and µ 2 > µ 1 , thenEQUATIONFor a node n on the optimal path, f (n) ∼ G(µ f 0 , σ 2 ). For a node n ′ off the optimal path, fEQUATIONOtherwise:EQUATIONThe probability that the f value of the optimal node is less than the f value of a non-optimal node isEQUATION)If σ 2 > σ 1 :EQUATIONEQUATION)Equation 54 is equivalent toEQUATIONAccording to the definition, m is monotonically increasing with respect to σ. Therefore,EQUATION2 ) and µ f 0 < µ f 1 , we haveP (2µ f 0 -f * (n ′ )) -P (f * (n ′ )) < 0 when f * (n ′ ) ≥ µ f 0 . Therefore, F (σ 2 ) -F (σ 1 )< 0 is established, and P (f (n) < f (n ′ )|σ) decreases as the prediction error σ increases when the noise is Gaussian distribution. The above analyses will be added to the revised paper to further elucidate the impact of prediction errors. Under both the uniform error distribution and the Gaussian error distribution, the larger the prediction error, the lower the likelihood of selecting the optimal node.Each molecule is encoded using a 2048-dimensional Morgan Fingerprint vector [45] as the input for the heuristic functions. The policy network is a multi-class task based on chemical reaction templates. 381302 templates are available. The policy network architecture is summarized as follows:• A fully connected layer with dimensions [2048, 512].• A batch normalization layer.• A dropout layer with a dropout rate of 0.3.• Another fully connected layer with dimensions [512, 381302].• A softmax layer.The top 50 reaction templates with the highest probabilities are retained, and corresponding chemical reactions are generated using rdchiral package [12] , an RDKit [32] wrapper for handling stereochemistry in retrosynthetic template extraction and application.The output of the value network is a scalar to estimate the synthetic cost of the input molecules. The architecture is summarized as follows:• A fully connected layer with dimensions [2048, 128].• A ReLU activation layer.• A dropout layer with a dropout rate of 0.1.• Normalize the output y with log(1 + e y ).Parameters of the policy and value network are the same with Retro * + [30] . No fine-tuning has been performed on the network.Besides the USPTO benchmark, six additional datasets comprising 4719 molecules are employed for ro-bust validation. The introduction of these datasets is as follows.logP [7] : The logarithm of the partition coefficient (logP) is a measure of the solubility of a molecule in a particular solvent. The logS of a molecule can affect the molecule's pharmacokinetics and pharmacodynamics.logS [60] : It is used to evaluate the solubility of molecules, which can affect the absorption, distribution, metabolism, and excretion (ADME) of a drug candidate.Toxicity LD50 [56] : Toxicity plays a key role in determining the safety and efficacy of drugs.Ames [25] : The Ames test is commonly used in the field of drug development to evaluate the potential mutagenicity of drug candidates, as well as other chemicals that may be used in drug manufacturing or as excipients.BBBP [35] : Blood-brain barrier (BBB) is a protective barrier that separates the bloodstream from the brain to prevent harmful substances from entering the brain. BBB penetration (BBBP) is considered when developing new drugs.ClinTox [21] : It is a dataset collecting drugs approved by the FDA and drugs that have failed clinical trials for toxicity reasons.To clean these datasets, molecules present in either the USPTO database or the building block set are removed. Additionally, molecules that can be solved by Retro * in one step and those that can be easily solved by a heuristic-based BFS planning algorithm within a fixed time limit are also excluded. After processing, 4719 molecules are retained.The search tree employed in this paper in retrosynthesis planning problem is displayed in Figure 4 . The initial state contains only the target molecule. The edges in the search tree represent the chemical reactions that enable state transitions between the connected nodes, which decompose the input product into its reactants. A state is a set of molecules that are able to synthesize the target molecule, which is decomposed from the target molecule along the traverse reaction path from the root to this node. The retrosynthetic planning problem is solved if all molecules within a state are available building blocks. For A single-step retrosynthetic prediction model is utilized as the policy model to generate potential chemical reactions yielding the input molecule. For non-terminal intermediate nodes, all molecules within the node are sorted in alphabetical order based on their SMILES representation. The first non-building block molecule in the sorted list is selected as the input molecule of the single-step prediction model. The number of available reactions provided by the policy for a given node corresponds to the number of branching factors within the search tree. Retro * and Retro * + utilize the AND-OR tree as the representation for the planning process. In this representation, a reaction is denoted by an AND node, with its child nodes representing the reactant molecules involved in that reaction. Similarly, a molecule is represented by an OR node, with its child nodes representing the chemical reactions capable of synthesizing that molecule. A chemical reaction can be taken if all of its child reactants can be synthesized, and a chemical molecule can be synthesized if there exists at least one child chemical reaction that can take place. We also applied SeeA * to the And-OR Tree framework, and under the same settings, utilizing the uniform sampling strategy to obtain candidate nodes, we observed an increase in success rate from Retro * +'s 91.05% to 92.11% in USPTO benchmark. The averafe siolution length is decreased from Retro * +'s 8.74 to 8.39. This finding demonstrates the effectiveness of the algorithm in the AND-OR tree structure.Average test results on the seven molecule datasets and results for the six additional testing molecule datasets are presented in Table 3 and 4 Logic synthesis is the process of transforming a hardware design at the register transfer level (RTL) into a Boolean gate-level network, which is represented by an and-inverter-graph (AIG), i.e., a netlist exclusively containing AND and NOT gates. Subsequently, a sequence of functionalitypreserving transformations is applied to generate an optimized AIG. Seven operations are allowed following the work of ABC [4] and other reinforcement learning algorithms [9, 29] , including balance, re-substitution, re-substitution -z, rewrite, rewrite -z, refactor, and refactor -z. The number of transformations is limited to 10, which is the same with ABC-RL [9] . Finally, post-technology mapping is performed using a 7nm technology library to obtain the final netlist, which is also generated using the ABC package. Time delay and area are estimated by ABC to evaluate the solution. An example framework of solving the logic synthesis problem is presented in Figure 5 . According to the partitioning in ABC-RL [9] , A total of 15 circuits from the MCNC dataset [63] are utilized as training circuits, while the remaining 12 circuits from the same dataset are employed to evaluate the performance. The number of nodes in the initial AIG of each circuit ranges from hundreds to thousands. The information about the circuits is summarized in Table 5 & 6. The number of input and output nodes varies from a few to several hundred, while the total number of nodes ranges from several hundred to thousands. The input of the value estimator consists of the initial AIG and the sequence of actions that have been taken. Nodes in the AIG (And-Inverter Graph) are represented by a two-dimensional vector, which records the node type and the number of inverted predecessors. The adjacency matrix is used to capture the node connectivity. Graph convolutional network (GCN) is used to extract the embedding for AIG, and the architecture is summarized as follows:• A GCN (Graph Convolutional Network) layer with a hidden size of 32.• A batch normalization layer.• A LeakyReLU activation layer.• A GCN layer with a hidden size of 32.• A batch normalization layer.• Mean pooling and max pooling are independently applied, and the outputs are concatenated to form the final embedding, which is a 64 dimension vector.The sequence of actions and the current number of steps are combined into a string, which serves as the input to the BERT model [15] to obtain a sequence embedding with 768 dimensions. AIG embedding and sequence embedding are concatenated together as the input of the value estimator, and the architecture is:• A fully connected layer with dimensions [832, 256].• A LeakyReLU activation layer.• A fully connected layer with dimensions [256, 256].• A LeakyReLU activation layer.• A fully connected layer with dimensions [256, 1].• A Tanh activation layer.MCTS simulations are performed on the training circuits to collect samples. During the evaluation of the leaf node before backpropagation, a complete search path is obtained through a fast rollout, which is then stored as a training dataset for the value estimator. 1500 action sequences are collected for each circuit. resyn2 synthesis recipe is used as the baseline during the evaluation. The area-delay product reduction for an action sequence P is defined asEQUATION)where ADP is Area × Delay. The reward in logic synthesis problem isEQUATIONwhere t is the index of the current step. The immediate reward is always 0 except for the last step. Therefore, the ground truth value for states in the sequence P are all equal to max{-1, ADP R(AIG, P )}. Mean square error loss is used as the learning target. Adam optimizer is employed to update the parameter with a 0.0001 learning rate. The learning process is presented in Figure 6 . The search trees for A * search, MCTS, and SeeA * when solving the logic synthesis problem for the alu4 circuit are depicted in Figure 7 , 8, and 9, respectively. For A * search, the initial three actions are consistently "113", indicating that the search process is trapped in a particular branch due to the lack of exploration. Due to the enforced exploratory nature, MCTS expands nodes across excessive branches, which can impede the efficiency of the search algorithm in generating solutions. SeeA * expands a moderate number of branches, striking a balance between the concentrated exploration of A * and the excessive expansion across multiple branches in MCTS. This approach allows for exploratory behavior without being confined to a single branch, while the selection of the candidate node with the minimum f -value prevents excessive expansion into irrelevant branches. As a result, SeeA * exhibits significant improvements in efficiency compared to both MCTS and A * .Sokoban is a puzzle video game where the objective is to move the crates strategically to push each crate to its corresponding storage locations. The input of the neural network is a four-dimensional tensor representing the positions of the box, the target, the person, and the walls, respectively. The architecture of the value estimator is summarized as:• A convolutional layer with a kernel size of 64 × 3 × 3.• A batch normalization layer.• A ReLU activation layer.• A ResNet with three residual blocks.• A convolutional layer with a kernel size of 1 × 1 × 1.• A batch normalization layer.• A ReLU activation layer.• A fully connected layer with dimensions [100, 1].• A ReLU activation layer.The EQUATIONMean square error is employed as the loss function:EQUATION)Adam optimizer with a 0.0001 learning rate is used to update the parameters. The search process allows a maximum of 10 5 expansions. The size of the candidate set in SeeA * is set to K = 100. In the clustering sampling strategy, N c = 2 clusters are employed and the parameter η is set to 0.1. In the UCT-like sample, c b is set 0.3. Experiment results are summarized in Table 7 .With the exploration behavior induced by the selective sampling, SeeA * yields shorter solutions than A * with a slight increase in the number of expanded nodes. By setting ε = 1.5, WA * identifies feasible solutions using the minimum average number of node expansions. However, the solutions by WA * tend to have longer lengths, indicating that excessive reliance on the heuristic function biases the search towards suboptimal solutions. To illustrate the effectiveness of SeeA * on problems where accurate heuristics could exist but the guiding heuristic used is unreliable, experiments on path finding are conducted, which is to find the shortest path from a starting point to a destination. The cost for each step is 1. g is the number of steps taken to reach the current position, and h is the Euclidean distance from the current position to the target position, which is reliable enough to guide the A * search in early studies. 100 robotic motion planning problems [3] are used to test the performance of A * and SeeA * . Under the guidance of the same reliable h, both A * and SeeA * find the optimal solutions for all testing cases, for which the average length is 400. The number of expansions of SeeA*(K = 5) with uniform sampling is 33283.21, slightly less than the 33340.52 of A * . To validate the superiority of SeeA * , an unreliable heuristic function ĥ is designed, which is randomly sampled from [0, 2 × h]. During the search process, nodes are evaluated by f = g + ĥ. In this situation, the average solution length of A * is 691. Ablation studies on logic synthesis are summarized below. The performance for different candidate set sizes K for SeeA * with uniform sampling is displayed in Table 8 . The performance is robust against different K, outperforming A* (K = ∞) consistently. The performance for different c b for UCT-like sampling is presented in Table 9 , which is robust against different c b . enhanced exploration with a larger c b leads to superior performance and longer running time.For the sokoban game, the average solution length and the average number of node expansions for uniform sampling strategy with different candidate sizes K are presented in Figure 14 . With the exploration behavior induced by the selective sampling, SeeA * yields shorter solutions than A * with a slight increase in the number of expanded nodes. The success rate of problem-solving is 100.0%.The ablation studies on the UCT-like sampling strategy are displayed in Table 10 . Under a limited number of expansions, the stronger the exploration with a larger c b , the shorter the identified solution path length, and the greater the number of expansions required to find a feasible solution. Both ε-Greedy and SeeA * involve introducing exploration to A * search. ε-Greedy selects the node with the best f -value with a probability of 1 -ε, and with a probability of ε, it randomly selects a node from the remaining nodes. SeeA * with uniform sampling strategy selects a candidate set uniformly and the node with the best f value within this candidate set is expanded. An example of the comparison of these two algorithms is given in Figure 15 . There are five nodes {s 1 , s 2 , s 3 , s 4 , s 5 }, and the f values estimated by the heuristic value function are in increasing order. In A * search, node s 1 is expanded with a probability of 100%. In ε-Greedy (ε = 0.5), there is a 60% probability of expanding node s 1 , and each of the remaining nodes has a 10% probability of being expanded. SeeA * expands s 1 (the node with the smallest f value) with a probability of 60%. It expands s 2 (the node with the second smallest f value) with a probability of 30%, and s 3 (the node with the third smallest f value) with a probability of 10%. The remaining two nodes with the largest f values are not eligible for expansion. Even though the selection of candidate nodes follows uniform sampling, which is quite random, only the candidate node with the smallest f value is expanded. This guarantees the quality of the expanded nodes, as nodes with significantly worse f values do not have a chance to be expanded, even if they might have been selected as candidates. Assuming there are N o open nodes and the size of the candidate set is K. The probability of expanding the node with the nth smallest f value under the uniform sampling strategy can be derived as follows:EQUATIONThe probability of being selected for expansion decreases gradually as the f value increases. Compared to ε-Greedy, SeeA * utilizes the f value to avoid excessive exploration in its decision process. Even though the estimated f value may be not reliable enough to guarantee that the node with the smallest f value is the real optimal node to be expanded, the f value still can serve as a measure of node quality within a certain range. The heuristic function possesses a certain level of reliability, and it is generally inappropriate to either completely trust, like A * search, or completely disregard, like ε-Greedy, the evaluations provided by the heuristic function. SeeA * aims to achieve a balance between fully trusting and fully disregarding the evaluations of the heuristic function.(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.Justification: Research conducted in this paper conform with the NeurIPS code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).The source code is available at https://github.com/CMACH508/SEEA_star.http://downloads.emolecules.com/free/2023-12-01/Red entries indicate the top rank, while blue entries signify the second position. Table 2 remains consistent.The MCTS in[37] did not utilize any guiding heuristics, and fast rollout was employed for node evaluation. PV-MCTS and PHS were guided by the policy from ABC-RL[9] and the value function trained in this paper. 


Decision: The work builds on  two search algorithms, MCTS an A*, to introduce  a new algorithm, SeeA*, which ehnances A* with a flexible exploration-exploitation balance.  Advantages of SeeA* over A* are justified theoretically and confirmed on real-world and synthetic search domains.

The reviewers seem to agree that the paper brings a significant contribution, is written well, and provides convincing empirical evaluation supported by theoretical analysis. Some reviewers expressed concerns about strong assumptions in the theoretical analysis, but appear to have been convinced by the authors that the theoretical results hold also for more liberal assumption. One reviewer wondered whether the paper fits well within NeurIPS, and the authors justified the appropriateness of the paper for the NeurIPS audience.

The paper introduces an important but simple to grasp enhancement to a broadly used algorithm with many applications in diverse areas of machine learning and artificial intelligence. I recommend the paper for an oral presentation at the conference.

Reviews: review: paper_summary: paper_summary: This work introduces a refined version of the A* search algorithm that integrates selective sampling to improve exploration & efficiency. The developed algorithm balances exploration and exploitation when heuristic guides are off the mark with the help of three sampling strategies. Also it outperforms traditional A* in both the quality of solutions and computational efficiency that is backed with practical tests.
strength_weakness: strength_weakness: 1.	Limited theoretical analysis for some sampling strategies
2.	Strong assumptions in theoretical results
3.	Experiment represents a narrow spectrum
4.	Scalability on resource-constrained environments/ large-scale system is not discussed
5.	No sufficient details on when SeeA* fails (or) perform suboptimally
questions: questions: -	In Alg 1, the termination condition “until O is empty” is not clear. For some challenging problems, if a solution may not exist, will SeeA* keep expanding nodes indefinitely? Consider adding a maximum iteration limit to guarantee termination?
-	The uniform sampling strategy discussed in Sec. 4.1.1 is clear and straightforward. However, the authors could discuss the potential drawbacks of this strategy, such as the possibility of selecting low-quality nodes, and how SeeA* addresses these drawbacks
-	The assumption in Corollary 4.2 that the prediction error for f* is uniformly distributed is quite strong. In practice, it’s more likely non-uniform like Gaussians? More info. on the sensitivity of the theoretical results to this assumption and empirical validation of the distribution of prediction errors will be helpful
-	NIT: The specific f and f* values seem arbitrary in Figure 1. Are these values generalize broadly (or) are they cherry-picked? 
-	The authors could provide more intuition on the implications of Theorem 4.3. How does the result relate to the trade-off between exploration and exploitation in SeeA*, and how can it guide the selection of the sampling strategy or hyperparameters?
-	In Sec. 5.2, the authors compare SeeA* with various baselines, including MCTS [1]. However, it is mentioned that the MCTS in [1] did not utilize any guiding heuristics. It would be informative to compare SeeA* with an MCTS variant that uses the same guiding heuristics for a fair comparison
-	The hyperparameter sensitivity analysis in Sec. 5.4 provides insights on the performance of SeeA*. However, the analysis is limited to the retrosynthetic planning problem. Does this generalize to other two problem domains and beyond? 
-	In the Sokoban experiment (Sec. 5.3), the authors compare SeeA* with several baselines, including DeepCubeA. However, the experimental setup for DeepCubeA is not clearly stated, making it difficult to asses the fairness of the comparison.

Reference:
[1] Walter Lau Neto, Yingjie Li, Pierre-Emmanuel Gaillardon, and Cunxi Yu. Flowtune: End-to-end automatic logic optimization exploration via domain-specific multi-armed bandit. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
limitations: limitations: -	The experiment focusses solely on synthetic search problems. Initial results on real-world domain for practical applicability would be valuable
-	Paper provides theoretical comparison of SeeA* vs A* for uniform sampling strategy, but lacks analysis for other proposed sampling strategies.
-	Paper only tests on problems that don’t have inaccurate heuristics. Testing on additional domains that have unreliable heuristics would be a good addition
paper_summary: paper_summary: The paper introduces a method for prioritizing nodes for expansion during heuristic search that builds on A* search. However, instead of selecting the node with the lowest cost in OPEN, it samples a subset of OPEN and selects the node with the lowest cost from that subset. The sampling procedure is done using a uniform, clustering, and UCT approach. Results show that this sample based approach performs better than regular A* search. Perhaps surprising, this includes the uniform sampling method.
strength_weakness: strength_weakness: I wonder what the results would be in an environment 

Line 123: Step 3 also occurs if a node is associated with a state in CLOSED, but is find via a shorter path
questions: questions: Is the clustering strategy susceptible to collapsing to a single cluster? Since the initialization is purely random, it seems like this could be the case. Is there any empirical evidence to suggest this does or does not happen?

How is the heuristic function for Sokoban trained?

It seems the uniform sampling method performs better than A* search. Is there any intuition as to why? For environments with large branching factors, where deep search trees are needed, and where shortest paths are sparse, the probability of sampling a subset of OPEN that contains nodes on a shortest path would be small. Would this not hurt performance for uniform?
limitations: limitations: In the questions section, I describe a scenario in which random sub sampling of OPEN could hurt performance. I am not sure if this is definitely the case, but, if it is, then I would consider that a limitation.
paper_summary: paper_summary: This paper proposes a novel search strategy, SeeA*. SeeA* employs a selective sampling process to screen a dynamic candidate subset based on an additional strategy. Under certain assumptions, SeeA* theoretically has better efficiency than A* search when SeeA* uses uniform select strategy and the heuristic value function deviates substantially from the true state value function. In experiments, SeeA* outperforms state-of-the-art heuristic search algorithms in terms of problem-solving success rate and solution quality while maintaining a low level of node expansions.
strength_weakness: strength_weakness: - Lots of information is in the appendix rather than the main text. Some parts should be moved to the main text, such as the algorithm pseudocode and results of different parameters in section N.

- Since this paper is about a traditional search algorithm and the learning part is not very clear, it may not be suitable for NeurIPS.
questions: questions: Line 116: The functions \(\tau\) and \(c\) should be defined.

Figure 1: I don't understand why this figure lists \(n\) with \(10^4\). Because \(n_{10^4}\) won't be explored by either algorithm. Naive A* will expand \(n_{200}\) at most.

Line 152: I would suggest moving the algorithm part into the main paper from the appendix.

Line 158: When using uniform sampling, \(K \to \infty\) means SeeA* = A*, and \(K \to 1\) means SeeA* = Random Search.

Equation 52: The equation contains \(N\) rather than \(N_o\), and what is lowercase \(k\)?

Line 190: PUCT should be pUCT, and \(Q\) is not defined. What are the estimated \(f\) values? Since \(f = g + h\) which could be calculated directly, why do we need to estimate it?

Lines 201-203: I don't understand, is \(f^*\) sampled from Gaussian and \(f^*\) also sampled from Uniform?

Line 215: \(N_o\) is not defined.

Equation 8: We can get an optimal \(K = -1/\ln p\). For large prediction error, \(K \to 1\), random selection. For small prediction error, \(K \to \infty\), A*.

Table 1: Why is uniform slower than cluster as Uniform has smaller expansions, and cluster needs additional cluster process time?
Tables 1 and 2 should indicate whether lower or higher values are better.

Lines 14-16: "Theoretically establish the superior efficiency of SeeA* over A*" should mention the theoretical analysis based on specific assumptions.

And I'm also expecting an experiment on path search since this method is highly related to A*.
limitations: limitations: The strategy parameters are still hand-crafted, which may result in less dynamism when the test case distribution changes.

Comments: title: Explanations of some paper symbol definitions
comment: Dear Reviewer KUFf:

Thank you very much for your response! We are glad to hear that your concerns have been addressed. The feedback is very helpful, and we will revise our next version of the paper accordingly. Thank you.

Best regards！
Dear Reviewer 8E9W:

Thanks for your feedback! It really helped improve the quality of the paper. We will make sure to include the added results and discussion in the next version of this work. Thank you.

Best regards！
Thank you for the responses to all my questions. I have no other question.
Dear Authors, 

Thank you for the detailed responses to all my questions. The responses to Q1, Q3, Q7 and Q9 align directionally with my comments and questions, thus addressing some of my questions. Therefore, I have increased my rating. I hope the authors can add relevant context in this rebuttal in the next iteration of this work.
Q9: The experimental setup for DeepCubeA is not clearly stated,.

A9: The experimental setup DeepCubeA is the same as the original paper [5]. The number of nodes expanded at each step is $1$, and the weight of the heuristic value is $0.8$. The test samples for SeeA* are the same as those for DeepCubeA. More details will be added to the appendix materials.

[5] Agostinelli, Forest, et al. "Solving the Rubik’s cube with deep reinforcement learning and search." Nature Machine Intelligence 1.8 (2019): 356-363.

Q10: Paper provides theoretical comparison of SeeA* vs A* for uniform sampling strategy, but lacks analysis for other proposed sampling strategies.

A10: For computational simplicity, only uniform sampling was considered in the theoretical portion. Based on Equation 7, the probability of expanding the optimal node $n_1$ by SeeA* is
$$
P_S(\sigma)=P(n_1\in\mathcal{D})P(n_1=\arg\min_{n'\in\mathcal{D}}f(n')|n_1\in\mathcal{D})
$$
$P(n_1\in\mathcal{D})=K/N_o$ for uniform sampling. The other two sampling strategies aim to achieve a higher $P(n_1\in\mathcal{D})$ compared to uniform sampling by constructing a more diverse candidate set, thereby enhancing the likelihood of expanding the optimal node. Uniform sampling approximates the distribution based on frequencies, while clustering sampling is akin to use Gaussian mixture model to learn the distribution of open nodes, where each cluster is a Gaussian. The candidate nodes are sampled from the learned distribution. We will provide the theoretical analysis of other sampling strategies in the future.
Q6: What are the estimated (f) values? Since (f = g + h) which could be calculated directly, why do we need to estimate it?

A6: $f(n)$ is the evaluation of a node $n$, which is calculated by $g(n)+h(n)$. $g(n)$ is the accumulated cost from the starting node to $n$, which is obtained during the interaction process. $h(n)$ is the expected future cost from $n$ to the termination, which is unknown and needs to be estimated by a heuristic function. We will revise this sentence to avoid potential misunderstandings.

Q7: Line 116: The functions ($\mathcal{T}$) and ($c$) should be defined.

A7: $\mathcal{T}$ is the state transition function defined in a Markov decision process, which is used to obtain the following state $s_{t+1}$ when taking action $a_t$ at state $s_t$. $c$ is the cost function, which gives the received cost when taking action $a_t$ at state $s_t$. We will revise the paper to provide precise definitions. 

Q8 Line 190: PUCT should be pUCT, and (Q) is not defined.

A8: pUCT is the summation of Q and U, where Q is the average value of the child nodes, and U is the exploration bonus. The definition of Q will be provided in more detail in the revised paper. 

Q9: Line 215: $N_o$ is not defined.

A9: $N_o$ is the number of nodes in the open set $\mathcal{O}$. The definition of $N_o$ will be included in the revised paper.

Q10: "Theoretically establish the superior efficiency of SeeA* over A*" should mention the theoretical analysis based on specific assumptions.

A10: Thank you for pointing that out. We will revise our paper accordingly.

Q11: N and k in Equation 52.

A11: Thank you for pointing that out. $N$ and $k$ should correspond to $N_o$ and $K$ in the main text. We will revise Equation 52 to maintain the consistency in the symbols used.

Q12: Tables 1 and 2 should indicate whether lower or higher values are better.

A12: Thank you for your suggestion. We will indicate in Table 1 and 2 whether larger values are preferred or smaller values are preferred. 

Q13: When using uniform sampling, $K \to \infty$ means SeeA* = A*, and $K \to 1$ means SeeA* = Random Search.

A13: We agree with your viewpoint. When $K \to \infty$, all open nodes are selected as the candidate nodes, and SeeA* degenerates back to A*. The expanded node is chosen using a best-first approach, relying entirely on the exploitation of the $f$ function. When $K \to 1$, only one node is selected as the candidate node, and hence, it is guaranteed to be expanded. The expanded node is determined by the exploration of the sampling strategy. Therefore, an appropriate value of $K$ ensures that SeeA* is a combination of A* search and random search, achieving a balance between exploitation and exploration.

Q14: Equation 8: We can get an optimal ($K = -1/\log p$). For large prediction error, ($K \to 1$), random selection. For small prediction error, ($K \to \infty$), A*.

A14: We agree with your viewpoint. Equation 8 reaches its maximum value when $K=-1/\log p$, at which point SeeA performs optimally. For large prediction errors, $p$ approaches $0$, and SeeA* degrades to random selection by setting $K=1$. For small prediction errors, $p$ approaches $1$, and SeeA* is the same as A* by setting $K=\infty$. Intuitively, if the prediction error is sufficiently small, then the best-first A* search is optimal. If the prediction error is significantly large, decisions based on $f$ values are likely to be misleading, and random sampling may perform better in this case. We will add this analysis to the main text. Thank you for your suggestion. 

Q15: The strategy parameters are still hand-crafted, which may result in less dynamism when the test case distribution changes.

A15: At present, the hyperparameters of algorithms indeed require manual design, but the performance is robust against different hyperparameter settings. The automated design to adapt to dynamically changing environments deserves more research efforts in the future.