Answers.Body: <blockquote>
  <p>over which then we will estimate the gradient for the policy π
  ...</p>
  </blockquote>
  <p>It seems like you might be misunderstanding the type of algorithm. This (NFSP) doesn't use return of <span class="math-container">$\Pi$</span> as a loss. If Heinrich &amp; Silver were using a policy gradient method, they would, you would encounter the issue of the gradient being off-policy.</p>
  <p>This is actually strictly a Q Learning algorithm. The policy of the MDP is epsilon-greedy based on our Q estimator. The policy function <span class="math-container">$\Pi$</span> is an estimator for <span class="math-container">$\epsilon\text{-greedy}(Q)$</span>, and is trained using SL according to negative-log-likelihood.</p>
  <p>What you would need to be careful of when implementing this NFSP is when you clear the replay memories. If you update your Q-network parameters <span class="math-container">$\theta^{Q} \leftarrow \theta^{Q'}$</span> (an easy mistake) and continue sampling, your trajectory distribution will be different. However, the algorithm described in the paper is entirely on-policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-19T13:17:31.470Z
Answers.Text: oh I see, infact the SL loss of the actor was just a binary crossentropy (and not an actor critic loss), so $\pi$ is just trying to approximate the best response
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-19T13:18:50.083Z
Answers.Text: For some reason, I always though FSP was and Actor Critic method where the best actor would go against old versions of itself, how strange
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-19T13:27:37.233Z
Answers.Text: @AlbertoSinigaglia AlphaStar used both FSP and used policy gradient; NFSP being a Q learning method is probably owed to it being from 2016, when policy gradient wasn't as common.
Answers.UserDisplayName: Venna Banana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-19T13:14:59.293Z
Answers.LastActivityDate: 2023-07-19T13:14:59.293Z
Answers.UserDisplayName: Venna Banana
Body: <p>I was reading the <a href="https://arxiv.org/pdf/1603.01121.pdf" rel="nofollow noreferrer">NFSP player</a> from D. Silver, and I'm somewhat confused by the algorithm:</p>
  <p><a href="https://i.sstatic.net/FLoef.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FLoef.png" alt="enter image description here" /></a></p>
  <p>In particular, given that we sample an action according to best response (<span class="math-container">$\sigma = \epsilon-\text{greedy}(Q)$</span>), we also insert this transition in <span class="math-container">$\mathcal{M}_{RL}$</span>, over which then we will estimate the gradient for the policy <span class="math-container">$\pi$</span>... however, since this action has not been sampled from the policy <span class="math-container">$\pi$</span>, it biases the gradient, which usually should be corrected by the importance sampling ratio</p>
  <p>what am I missing?</p>
  
Tags: <reinforcement-learning><game-theory><self-play>
Title: Is neural fictitious self play violating off-policy theorem
UserDisplayName: Alberto
ThreadText: # Is neural fictitious self play violating off-policy theorem
  
  (Asked by: username_0 on 2023-07-19)
  
  I was reading the [NFSP player](https://arxiv.org/pdf/1603.01121.pdf) from D. Silver, and I'm somewhat confused by the algorithm:
  
  [![enter image description here](https://i.sstatic.net/FLoef.png)](https://i.sstatic.net/FLoef.png)
  
  In particular, given that we sample an action according to best response ($\sigma = \epsilon-\text{greedy}(Q)$), we also insert this transition in $\mathcal{M}\_{RL}$, over which then we will estimate the gradient for the policy $\pi$... however, since this action has not been sampled from the policy $\pi$, it biases the gradient, which usually should be corrected by the importance sampling ratio
  
  what am I missing?
  
  **Tags:** reinforcement-learning, game-theory, self-play
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-07-19. Score: 3 | Accepted answer
  
  > over which then we will estimate the gradient for the policy π
  > ...
  
  It seems like you might be misunderstanding the type of algorithm. This (NFSP) doesn't use return of $\Pi$ as a loss. If Heinrich & Silver were using a policy gradient method, they would, you would encounter the issue of the gradient being off-policy.
  
  This is actually strictly a Q Learning algorithm. The policy of the MDP is epsilon-greedy based on our Q estimator. The policy function $\Pi$ is an estimator for $\epsilon\text{-greedy}(Q)$, and is trained using SL according to negative-log-likelihood.
  
  What you would need to be careful of when implementing this NFSP is when you clear the replay memories. If you update your Q-network parameters $\theta^{Q} \leftarrow \theta^{Q'}$ (an easy mistake) and continue sampling, your trajectory distribution will be different. However, the algorithm described in the paper is entirely on-policy.
  
  > **Comments:**
  > **username_0**: oh I see, infact the SL loss of the actor was just a binary crossentropy (and not an actor critic loss), so $\pi$ is just trying to approximate the best response  
  > **username_0**: For some reason, I always though FSP was and Actor Critic method where the best actor would go against old versions of itself, how strange  
  > **username_1**: @AlbertoSinigaglia AlphaStar used both FSP and used policy gradient; NFSP being a Q learning method is probably owed to it being from 2016, when policy gradient wasn't as common.  
  
  ---
  
  