# Tag Info

## Hot answers tagged monte-carlo-tree-search

6

$Q$-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for single-agent environments. The entire problem setting that these algorithms are developed for (Markov decision processes, or MDPs) is always framed in terms of a single agent situated in some environment, where ...

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 $... 3 Some basic advantages of MCTS over Minimax (and its many extensions, like Alpha-Beta pruning and all the other extensions over that) are: MCTS does not need a heuristic evaluation function for states. It can make meaningful evaluations just from random playouts that reach terminal game states where you can use the loss/draw/win outcome. So if you're faced ... 3 Deep Q Learning is a model-free algorithm. In the case of Go (and chess for that matter) the model of the game is very simple and deterministic. It's a perfect information game, so it's trivial to predict the next state given your current state and action (this is the model). They take advantage of this with MCTS to speed up training. I suppose Deep Q ... 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 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 ... 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 ... 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 ... 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 ...

1

It might be the case that if you perform a large number of random rollouts, the "best action" as chosen by the agent without the domain knowledge, is same as the agent with the domain knowledge. I guess what you can do is try to reduce the number of rollouts and see if the performance changes.

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