Answers.Body: <p>External sampling and outcome sampling are two ways of <strong>defining</strong> the sets <span class="math-container">$Q_1, \dots, Q_n$</span>. I think your mistake is that you think of the <span class="math-container">$Q_i$</span> as fixed and taken as input in these shampling schemes. It is not the case.</p>
  <p>In external sampling, there is as many sets <span class="math-container">$Q_{\tau}$</span> as there are pure strategies for the opponent and the chance player (a pure strategy is a deterministic policy). Think of it as &quot;the set of terminal nodes that I can reach if my opponent and chance play in this fixed way&quot;.</p>
  <p>Sampling a set <span class="math-container">$Q_{\tau}$</span> thus means sampling a pure strategy for the opponent and chance node. An alternative is to sample on the fly the opponent's policy <span class="math-container">$\sigma^{-i}$</span> (and chance) when needed. It gives identical probabilities for q(z), while does not correspond to a full definition of a deterministic policy <span class="math-container">$\tau$</span> (which would need a definition on all the information nodes).</p>
  <p>There are several implementations on Github, one can be found here: <a href="https://github.com/bakanaouji/cpp-cfr/blob/master/RegretMinimization/Trainer/Trainer.cpp" rel="nofollow noreferrer">https://github.com/bakanaouji/cpp-cfr/blob/master/RegretMinimization/Trainer/Trainer.cpp</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-15T20:06:31.647Z
Answers.Text: Do you know about any implementation code that is in python? That is the only programming language that i currently know
Answers.UserDisplayName: kpopgirl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T11:30:58.457Z
Answers.Text: Do I have to update strategies for all info sets doesn't that take up a lot of memory?
Answers.UserDisplayName: kpopgirl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-12T21:26:31.520Z
Answers.LastActivityDate: 2021-02-12T21:26:31.520Z
Answers.UserDisplayName: Phil
Body: <p>I have read many papers, such as <a href="https://papers.nips.cc/paper/2009/file/00411460f7c92d2124a67ea0f4cb5f85-Paper.pdf" rel="nofollow noreferrer">this</a> or <a href="https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&amp;item_id=199967&amp;item_no=1&amp;attribute_id=1&amp;file_no=1" rel="nofollow noreferrer">this</a>, explaining how external sampling works, but I still don't understand how the algorithm works.</p>
  <p>I understand you divide <span class="math-container">$Q$</span>, which is the set of all terminal histories into subsets <span class="math-container">$Q_1,..., Q_n$</span>.</p>
  <p><em>What is the probability of reaching some subset <span class="math-container">$Q_i$</span>? Is it just the product of chance probability, the opponent's probability, and my probability?</em></p>
  <p>As I understand it, the sampling only occurs in the opponent's information sets. <em>How does that work?</em> If there are two players, player 1 strategy is based on what strategy I use.</p>
  <p><em>What happens after you have determined a subset <span class="math-container">$Q_i$</span> you want to sample? How many times do you iterate over the subset <span class="math-container">$Q_i$</span>?</em></p>
  <p>I have searched around and I cannot find any Python code that uses external sampling, but plenty of papers that give formulas, but do not explain the algorithm in detail. So, a Python example of MC-CFR external sampling would probably make it a lot easier for me to understand the algorithm.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-11T23:52:25.807Z
Comments.Text: Hello. Welcome to Artificial Intelligence Stack Exchange. Please, [**ask only 1 question per post**](https://meta.stackexchange.com/a/39224/287113). If you have multiple questions, ask each of them in its separate post. Of course, in your case, the questions are all related to the same algorithm, but it's still fine to ask them in separate posts, provided that you provide the necessary context in each post to understand the question.
Comments.UserDisplayName: nbro
Tags: <python><papers><monte-carlo-methods><game-theory><games-of-chance>
Title: How exactly is Monte Carlo counterfactual regret minimization with external sampling implemented?
UserDisplayName: kpopgirl
ThreadText: # How exactly is Monte Carlo counterfactual regret minimization with external sampling implemented?
  
  (Asked by: username_0 on 2021-02-11)
  
  I have read many papers, such as [this](https://papers.nips.cc/paper/2009/file/00411460f7c92d2124a67ea0f4cb5f85-Paper.pdf) or [this](https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=199967&item_no=1&attribute_id=1&file_no=1), explaining how external sampling works, but I still don't understand how the algorithm works.
  
  I understand you divide $Q$, which is the set of all terminal histories into subsets $Q\_1,..., Q\_n$.
  
  *What is the probability of reaching some subset $Q\_i$? Is it just the product of chance probability, the opponent's probability, and my probability?*
  
  As I understand it, the sampling only occurs in the opponent's information sets. *How does that work?* If there are two players, player 1 strategy is based on what strategy I use.
  
  *What happens after you have determined a subset $Q\_i$ you want to sample? How many times do you iterate over the subset $Q\_i$?*
  
  I have searched around and I cannot find any Python code that uses external sampling, but plenty of papers that give formulas, but do not explain the algorithm in detail. So, a Python example of MC-CFR external sampling would probably make it a lot easier for me to understand the algorithm.
  
  **Tags:** python, papers, monte-carlo-methods, game-theory, games-of-chance
  > **Comments:**
  > **username_1**: Hello. Welcome to Artificial Intelligence Stack Exchange. Please, [**ask only 1 question per post**](https://meta.stackexchange.com/a/39224/287113). If you have multiple questions, ask each of them in its separate post. Of course, in your case, the questions are all related to the same algorithm, but it's still fine to ask them in separate posts, provided that you provide the necessary context in each post to understand the question.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-02-12. Score: 1
  
  External sampling and outcome sampling are two ways of **defining** the sets $Q\_1, \dots, Q\_n$. I think your mistake is that you think of the $Q\_i$ as fixed and taken as input in these shampling schemes. It is not the case.
  
  In external sampling, there is as many sets $Q\_{\tau}$ as there are pure strategies for the opponent and the chance player (a pure strategy is a deterministic policy). Think of it as "the set of terminal nodes that I can reach if my opponent and chance play in this fixed way".
  
  Sampling a set $Q\_{\tau}$ thus means sampling a pure strategy for the opponent and chance node. An alternative is to sample on the fly the opponent's policy $\sigma^{-i}$ (and chance) when needed. It gives identical probabilities for q(z), while does not correspond to a full definition of a deterministic policy $\tau$ (which would need a definition on all the information nodes).
  
  There are several implementations on Github, one can be found here: <https://github.com/bakanaouji/cpp-cfr/blob/master/RegretMinimization/Trainer/Trainer.cpp>
  
  > **Comments:**
  > **username_0**: Do you know about any implementation code that is in python? That is the only programming language that i currently know  
  > **username_0**: Do I have to update strategies for all info sets doesn't that take up a lot of memory?  
  
  ---
  
  