Answers.Body: <p>My understanding is now that the author's formula is deliberate. It seeks to learn a worst-case maximizing policy. The formula I instead suggest would, I believe, instead be <a href="http://www.jmlr.org/papers/volume4/hu03a/hu03a.pdf" rel="nofollow noreferrer">Nash Q learning</a> where the agent seeks to learn to play a Nash equilibrium.</p>
  
  <p>After debugging, I have gotten <a href="https://github.com/pb4git/Nash-DQN-CSB-Article" rel="nofollow noreferrer">good results</a> with the second formula but cannot speak for the original Minimax Q learning one.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-21T12:18:16.133Z
Answers.LastActivityDate: 2019-02-21T12:26:02.880Z
Answers.LastEditDate: 2019-02-21T12:26:02.880Z
Answers.UserDisplayName: Agade
Body: <p>In the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.8293&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Markov games as a framework for multi-agent reinforcement learning </a> (which introduces the minimax Q Learning algorithm), at the bottom left of page 3, my understanding is that the author suggests, for a simultaneous 1v1 zero-sum game, to do Bellman iterations with <span class="math-container">$$V(s)=\min_{o}\sum_{a}\pi_{a}Q(s,a,o)$$</span> with <span class="math-container">$\pi_{a}$</span> the probability of playing action <span class="math-container">$a$</span> for the maximizing player in his best mixed strategy to play in state <span class="math-container">$s$</span>. </p>
  
  <p>If my understanding is correct, why does the opponent in this equation play a pure strategy (<span class="math-container">$\min_{o}$</span>) rather than his best mixed strategy in state <span class="math-container">$s$</span>. This would instead give <span class="math-container">$$V(s)=\sum_{o}\sum_{a}\pi_{a}\pi_{o}Q(s,a,o)$$</span> with <span class="math-container">$\pi_{o}$</span> the opponent's best mixed strategy in state <span class="math-container">$s$</span>. Which of these two formulations is correct and why? Are they somehow equivalent?</p>
  
  <p>The context of this question is that I am trying to use minimax Q learning with a Neural Network outputting the matrix <span class="math-container">$Q(s,a,o)$</span> for a simultaneous zero-sum game. I have tried both methods and so far have seen seemingly equally bad results, quite possibly due to bugs or other errors in my method.</p>
  
Tags: <reinforcement-learning><q-learning><minimax>
Title: Using the opponent's mixed strategy in estimating the state value in minimax Q learning
UserDisplayName: Agade
ThreadText: # Using the opponent's mixed strategy in estimating the state value in minimax Q learning
  
  (Asked by: username_0 on 2019-01-10)
  
  In the paper [Markov games as a framework for multi-agent reinforcement learning](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.8293&rep=rep1&type=pdf)  (which introduces the minimax Q Learning algorithm), at the bottom left of page 3, my understanding is that the author suggests, for a simultaneous 1v1 zero-sum game, to do Bellman iterations with $$V(s)=\min\_{o}\sum\_{a}\pi\_{a}Q(s,a,o)$$ with $\pi\_{a}$ the probability of playing action $a$ for the maximizing player in his best mixed strategy to play in state $s$.
  
  If my understanding is correct, why does the opponent in this equation play a pure strategy ($\min\_{o}$) rather than his best mixed strategy in state $s$. This would instead give $$V(s)=\sum\_{o}\sum\_{a}\pi\_{a}\pi\_{o}Q(s,a,o)$$ with $\pi\_{o}$ the opponent's best mixed strategy in state $s$. Which of these two formulations is correct and why? Are they somehow equivalent?
  
  The context of this question is that I am trying to use minimax Q learning with a Neural Network outputting the matrix $Q(s,a,o)$ for a simultaneous zero-sum game. I have tried both methods and so far have seen seemingly equally bad results, quite possibly due to bugs or other errors in my method.
  
  **Tags:** reinforcement-learning, q-learning, minimax
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2019-02-21. Score: 0 | Accepted answer
  
  My understanding is now that the author's formula is deliberate. It seeks to learn a worst-case maximizing policy. The formula I instead suggest would, I believe, instead be [Nash Q learning](http://www.jmlr.org/papers/volume4/hu03a/hu03a.pdf) where the agent seeks to learn to play a Nash equilibrium.
  
  After debugging, I have gotten [good results](https://github.com/pb4git/Nash-DQN-CSB-Article) with the second formula but cannot speak for the original Minimax Q learning one.
  
  
  ---
  
  