4
$\begingroup$

Roughly, AlphaGo/AlphaGo Zero 's algorithm is as follows:

  1. Using a policy network, generate a distribution of move probabilities (intuitively, capturing how good those moves are based on a first-approximation).

  2. Pick a move based on those probabilities, and imagine the board position that results from the move. Then use the value network to evaluate the resulting position.

  3. Repeat this by using MCTS (monte carlo tree search) for $n$ times, which results in "augmented" move probabilities. (these probabilities represent the ratio of wins that resulted from the $n$ samples of the MCTS.

My question is:

  • Why does AlphaZero use both a policy network and a value network? It could also have used only a policy net with MCTS, or only a value net with MCTS. Is there a principled understanding of why this works well? (apart from "it turns out to work well in experiments").

  • Why does AlphaZero use both the value function AND an "upper confidence bound" to guide its search?

$\endgroup$
  • $\begingroup$ Can you add a brief explanation of how AlphaZero uses both the value function and UCB? There's no reference to it in your question except in your last sentence. The article about AlphaZero that you linked to is behind a pay wall. $\endgroup$ – Sycorax Oct 28 '18 at 20:23
3
$\begingroup$

First a small note: AlphaGo Zero actually does only use a single network, it no longer has separate value and policy networks like the original AlphaGo did. That single network does still have separate value and policy heads though (two separate outputs)... so I suppose you can intuitively still view it as having two networks (which happen to share a large number of parameters between them).


With that technicality out of the way, it is first important to have a good understanding of what the different roles are that are fulfilled by learning (regardless of whether it is a policy or a value network) on one hand, and search (MCTS) on the other hand:

  • The networks (both value and policy) obtained through learning can informally be viewed as providing a strong level of intuition to the program. These components look at a current state, and instantly make a "snap decision" for an action to play (in the case of policy network) or a "snap evaluation" to estimate the value of a state (in the case of value network). They can be trained to perform at an admirable level on their own already, but are always going to be constrained in some sense. When not combined with an element of search (like MCTS), they do not perform any additional "reasoning" or "thinking".
  • The search component (MCTS) provides "reasoning" / "thinking" / "deliberation" to the program. It does not make any instant "snap" decisions, but happily uses as much thinking time as it can get to continue reasoning and gradually improve the decision it would make during the specific turn it is "thinking" about. It really focuses on that one particular turn, rather than then learning components which focus on the complete game simultaneously. Given an infinite amount of thinking time, it would play optimally.

Why does AlphaZero use both a policy network and a value network? It could also have used only a policy net with MCTS, or only a value net with MCTS. Is there a principled understanding of why this works well? (apart from "it turns out to work well in experiments").

Note that:

  • Given a state $s$, the value network gives an estimate of the value $V(s)$ of that state $s$.
  • Given a state $s$, the policy network gives a recommendation of an action $a = \pi(s)$ to take (or a probability distribution $\pi(s, a)$ over the different possible actions $a$).

These are quite different kinds of outputs, and this means there are different parts in the MCTS algorithm where they can be used:

  • The output $V(s)$ of a value network is an evaluation "in hindsight". You first have to actually reach a state $s$, and then the value network can be used to evaluate it. This is useful, for example, if you want to terminate a Play-out / rollout of MCTS early (before it has been rolled out all the way to a truly terminal state), and return a reasonable evaluation for that rollout. However, it can not be used (efficiently) for action selection during a rollout for example; if you want to use a $V(s')$ estimate to determine which action to pick in a rollout, you have to first generate all possible successor states $s'$ for all possible actions, evaluate all of them, and then you can finally pick the best action accordingly. This is computationally expensive.
  • The output $\pi(s, a)$ of a policy network is a "proactive action selection". You can use it, for example, during a Play-out/rollout to immediately select an action for a current state $s$, no need to first generate and evaluate all possible successors $s'$. However, when you wish to terminate a rollout, evaluate the resulting state, and backpropagate that evaluation... the policy network does not provide the information required to do that, it doesn't give you a state-value estimate.

In practice, it is indeed desirable to be able to do both of the things that were described above as being easy to do for one network and difficult for the other. It is important to use a strong "intuition" (obtained throuhg learning) for action selection in MCTS, because this leads to more realistic rollouts and therefore also often better evaluations. This cannot be done using a value network (well, it can in the Selection phase / tree traversal of MCTS, but not once a node is reached that hasn't been fully expanded). It is also desirable to terminate rollouts early and backpropagate high-quality evaluations, rather than rolling them out all the way (which takes more time and introduces more variance due to greater likelihood of selecting unrealistic actions along the trajectory). This functionality can only be provided by a value network.


Why does AlphaZero use both the value function AND an "upper confidence bound" to guide its search?

When the search process starts, when we have not yet run through a large number of MCTS simulations, the evaluations based purely on MCTS itself (which are typically used in the UCB equation) are unreliable. So, initially it is useful to have a strong "intuition" for value estimates, as provided by the value network.

As the number of MCTS simulations performed increases (in particular as it tends to infinity, but of course also earlier than that in practice), we expect the MCTS-based evaluations to gradually become more reliable, eventually even potentially becoming more accurate than the learned value network. Note that the value network was trained to provide reasonable value estimates instantly for any game state. The MCTS search process dedicates all of its time just to computing reliable value estimates for the current game state, it is allowed to "specialize" to the current game state. So, as time moves on, we'll want to start relying a bit more on the MCTS-based evaluations, and a bit less on the initial "intuition" from the value network.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Using a policy network and a value network seems related to the trick that dueling DQNs use. The simplest dueling DQN is a single network that "branches" near the final layers to compute advantage values $A(s,a)$ for each action, as well as value $V(s)$ for the current state. Explicitly separating the advantage for each action from the values for the current state has better training stability, faster convergence and better performance on the Atari benchmark (Dueling Network Architectures for Deep Reinforcement Learning, Wang et al. 2015). This is because it makes explicit the two components of the $Q$ values: $$ Q(s,a) = V(s) + A(s,a) $$

The difference between AlphaZero and a dueling DQN appears to be that instead of using the same network with different branches to approximate $V(s)$ and $A(s,a)$, a distinct value and policy network are used instead.

This is just a parallel, but I think it gives a sense of why distinguishing different components of the problem can make learning a complex problem easier.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.