15

There is always a lot of confusion about this concept, because the naming is misleading, given that both tree and graph searches produce a tree (from which you can derive a path) while exploring the search space, which is usually represented as a graph. Differences Firstly, we have to understand that the underlying problem (or search space) is almost always ...


3

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" in the 2012 paper you linked. In algorithm 2 of the 2012 paper, they actually use the highest average reward, which corresponds to "Max child". It looks like ...


2

In short it looks like you have constructed a valid reinforcement learning method, but it does not have much in common with Monte Carlo Tree Search. It may have some weaknesses compared to more established methods, that means it will work better in some environments rather than others. Your approach may be novel, in that you have combined ideas into a method ...


1

The sketch of the proof for your first question: for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time for any node $n$, $f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function $h_1$ will be admissible (from Theorem 2 of ...


1

Assigning a value of $\infty$ to unvisited nodes is indeed the "default" or most basic choice, and it indeed ensures that the search never visits a node for a second time if it also still has siblings that have not had any visits. But many other kinds of values have been tried in the literature too. Gelly and Wang, in "Exploration exploitation ...


1

Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child? Expanding all nodes or expanding just one node are both possible. There are different advantages and disadvantages. The obvious disadvantage of immediately expanding them all is that your memory usage will grow more quickly. I suppose that the primary advantage is ...


Only top voted, non community-wiki answers of a minimum length are eligible