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


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

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


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

You should not let the tree grow for only two seconds rather you should use the simulation number equal to 1000 or something like that. I use the simulation number equal to 10000 for making a single move in the tictactoe game and it was working fine for me. Also, after the agent has chosen the move you do not have to start the statistics(N = visit count, V = ...


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