Answers.Body: <p>AlphaZero is on-policy*, which partially answers your question.</p>
  <p>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 &quot;current&quot; policy.</p>
  <p>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.</p>
  <p>From the <a href="https://arxiv.org/pdf/1712.01815.pdf" rel="nofollow noreferrer">AlphaZero paper</a>:</p>
  <blockquote>
  <p>At the end of the game, the terminal position <span class="math-container">$s_T$</span> is
  scored according to the rules of the game to compute the game outcome <span class="math-container">$z: −1$</span> for a loss, <span class="math-container">$0$</span> for a draw, and <span class="math-container">$+1$</span> for a win. The neural network parameters <span class="math-container">$\theta$</span> are updated so as to minimise the error between the predicted outcome <span class="math-container">$v_t$</span> and the game outcome <span class="math-container">$z$</span>, and to maximise the similarity of the policy vector <span class="math-container">$p_t$</span>
  to the search probabilities <span class="math-container">$\pi_t$</span>.</p>
  </blockquote>
  <p>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).</p>
  <hr />
  <p>* 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T02:10:49.437Z
Answers.Text: 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.
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T02:16:24.983Z
Answers.Text: 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.
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T08:44:41.697Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T20:51:36.873Z
Answers.Text: 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?
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-24T10:49:10.570Z
Answers.Text: @sb3 I think that is a bit too much for me to answer in a comment. Please ask a new question on the site.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T23:56:20.123Z
Answers.LastActivityDate: 2020-12-23T00:08:21.243Z
Answers.LastEditDate: 2020-12-23T00:08:21.243Z
Answers.UserDisplayName: Neil Slater
Body: <p>In AlphaZero, we collect (<span class="math-container">$s_t, \pi_t, z_t$</span>) tuples from self-play, where <span class="math-container">$s_t$</span> is the board state, <span class="math-container">$\pi_t$</span> is the policy, and <span class="math-container">$z_t$</span> 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.</p>
  
Tags: <machine-learning><deep-rl><alphazero>
Title: Is there a training data capacity limit for AlphaZero (Chess)?
UserDisplayName: sb3
ThreadText: # Is there a training data capacity limit for AlphaZero (Chess)?
  
  (Asked by: username_0 on 2020-12-22)
  
  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.
  
  **Tags:** machine-learning, deep-rl, alphazero
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-22. Score: 1 | Accepted answer
  
  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](https://arxiv.org/pdf/1712.01815.pdf):
  
  > 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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: 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.  
  > **username_1**: @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.  
  > **username_0**: 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?  
  > **username_1**: @sb3 I think that is a bit too much for me to answer in a comment. Please ask a new question on the site.  
  
  ---
  
  