4

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards: The leaf $s'$ position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, $(P(s′ , \cdot),V(s ′ )) = f_\theta(s′ )$. Each edge $...


2

I don't think you've necessarily made any real mistakes in your calculations or anything like that, that all seems accurate. I can't really confidently answer your questions about "Does X usually happen?" or "How common is X?", would have to experiment to make sure of that. I think we can also confidently immediately answer the question ...


2

Assuming a continuous/uncountable state space, we can only estimate our value function using function approximation, so our estimates will never be true for all states simultaneously (because, loosely speaking, we have far more states than weights). If we can look at the (approximated) value of states we take in, say, 5 actions time, it is better to make a ...


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 ...


2

First explore the nodes A,B,C once. For reference see this paper by David Silver and Sylvain Gelly, Combining Online and Offline Knowledge in UCT If any action from the current state $s$ is not represented in the tree, $\exists a \in \mathcal{A}(s),(s, a) \notin \mathcal{T},$ then the uniform random policy $\pi_{\text {random }}$ is used to select an action ...


2

If the initial state is not always the same, but if your agent is allowed to observe what the initial state is before it has to start running the search algorithm, there's basically no problem; it has all the information it needs when it starts running the tree search. This is how we typically use MCTS (or any other tree searches): we first observe what the ...


2

I looked at the Python pseudo-code attached to the Data S1 of the Supplementary Materials of the AlphaZero paper. Here is my findings: Contrary to the paper, AlphaZero does not store $\{N(s, a), W(S, a), Q(s, a), P(s, a)\}$ statistics for each edge $(s,a)$. Instead, AlphaZero stores $\{N(s), W(S), Q(s), P(s)\}$ statistics for each node $s$. When a leaf node ...


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 ...


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

Yeah, it seems that you're right and based on the description of the paper it would indeed behave uniformly random at the very first iteration (or maybe just always deterministically pick whichever action happens to be the first one in the list). I can't find anything that would suggest otherwise in the paper, and also the pseudocode they put on arXiv ...


1

There are a few different ways to improve on your simple heuristic approach, but they mostly resolve to these three things: Find a better heuristic. This could be done by calculating probabilities of results, or running loads of training simulations and somehow tuning the heuristic function. Look-ahead search/planning. There are many possible search ...


1

Some sources say MCTS (or planning in general) increases the sample efficiency. If we're thinking purely about experiments run in simulations, then I'd estimate there may be cases where a combination of pure learning + MCTS (or some other form of planning / model-based aspect) may be more efficient, and there may be different cases where only a single one ...


1

For easier visualization, I recommend this video: https://twitter.com/i/status/1257053365424578565 The more detailed article about GO algorithms: https://deepmind.com/blog/article/alphago-zero-starting-scratch. With its breadth of $250$ possible moves each turn (go is played on a $19$ by $19$ board, compared to the much smaller $8$ by $8$ chess field) and a ...


1

The most important word for answering your question from that quote from the paper is probably the word "usually": These search probabilities usually select much stronger moves than the raw move probabilities $p$ of the neural network. It's not always going to be true, but more often than not / most of the time / "on average", we ...


1

I am having trouble understanding how to keep track of the expansion, do I expand all stochastic possibilities and weight the return via their chance of happening? This is indeed one option you can take. This would be very similar in spirit to the idea of "Expectimax" as a variant of minimax for non-deterministic games, in the sense that you'll ...


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