1
$\begingroup$

In AlphaZero, we collect ($s_t, \pi_t, z_t$) tuples from self-play, where $s_t$ is the board state, $\pi_t$ is the policy, and $z_t$ is the reward from winning/losing the game. In other DeepRL off-policy algorithms (I'm assuming here that AlphaZero is off-policy (?)) like DQN, we maintain a memory buffer (say, 1 million samples) and overwrite the buffer with newer samples if it's at capacity. Do we do the same for AlphaZero? Or do we continually add new samples without overwriting older ones? The latter option sounds very memory heavy, but I haven't read anywhere that older samples are overwritten.

$\endgroup$
1
$\begingroup$

AlphaZero is on-policy*, which partially answers your question.

An on-policy algorithm is not the same as an online policy though, it is not required that updates are made on every step. It is simply required that all data used in the update is taken from the same "current" policy.

In practice, AlphaZero buffers results from games played with the current policy to create a dataset used to update its neural networks. That buffer is then emptied after the data has been used.

From the AlphaZero paper:

At the end of the game, the terminal position $s_T$ is scored according to the rules of the game to compute the game outcome $z: −1$ for a loss, $0$ for a draw, and $+1$ for a win. The neural network parameters $\theta$ are updated so as to minimise the error between the predicted outcome $v_t$ and the game outcome $z$, and to maximise the similarity of the policy vector $p_t$ to the search probabilities $\pi_t$.

This implies only a single game is buffered in this way before running each update and then discarding the dataset generated in that game. Theoretically the same approach could be used with any number of games for each update step (provided the training system has capacity to store more moves).


* AlphaZero is on-policy because the core algorithm requires using a specific policy and then updating it to match an improved version of the same policy discovered using MCTS for planning during play.

It could be possible to construct an off-policy update mechanism using similar MCTS routine. I am not sure why this is not considered, but suspect it would be due to complexity/efficiency of the algorithm compared to the ease of generating new game data.

$\endgroup$
5
  • $\begingroup$ This clarifies things, thank you! Yea, I suppose there would need to be a behavior policy different than the current optimal policy estimate to collect experience. I don't see why AlphaZero's implementation of MCTS couldn't function as this behavior policy. Although making it off-policy would be more sample-inefficient, so perhaps there isn't much to be gained. $\endgroup$ – sb3 Dec 23 '20 at 2:10
  • $\begingroup$ Actually now that I think about it, is AlphaZero not already set up to be off-policy? MCTS's PUCT can be thought of as the behavior policy that actually searches/collects experience. The network is only used during training to get a value estimate and probability prior on new unvisited states. Perhaps this is where my confusion stemmed from. $\endgroup$ – sb3 Dec 23 '20 at 2:16
  • $\begingroup$ @sb3: Yes, you could think of the trajectory created by MCTS as being from a different policy. The difference between AlphaZero and a normal off-policy method is then how those two policies relate to each other. In MCTS the results from planning are a version of the target policy, there is not the same independence between behaviour and target policy that exists in standard off-policy methods. $\endgroup$ – Neil Slater Dec 23 '20 at 8:44
  • $\begingroup$ I've got a follow up question for you: During self-play, we have the 'search' step where we expand the tree, and the 'play' step where we rollout a game. The paper also mentions doing 800 simulations of self-play. Does this mean 800 iterations of the search step, and then the play step once? Also, do we only collect (s, pi, z) tuples visited from the play step or from all nodes in the tree? $\endgroup$ – sb3 Dec 23 '20 at 20:51
  • $\begingroup$ @sb3 I think that is a bit too much for me to answer in a comment. Please ask a new question on the site. $\endgroup$ – Neil Slater Dec 24 '20 at 10:49

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.