Body: <p>I am writing a report where I used a slightly modified version of MCTS (not parallelized). I thought It could be interesting if I could calculate its time complexity. I'd appreciate any help I could get.</p>
  
  <p>Here's the rough idea of how it works:</p>
  
  <p>Instead of tree search, I'm using graph search meaning I keep a list of visited nodes in order to avoid adding duplicate nodes.</p>
  
  <p>So in the expansion phase, I add all child nodes of the current node that aren't present elsewhere in the tree.</p>
  
  <p>For the remaining phases, it's essentially the same as the basic version of MCTS, with a default random policy in the simulation step.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-10T18:54:40.527Z
Comments.Text: Are you sure it makes sense to talk about time complexity in MCTS? It does not have a end or a certain amount of iterations you should do in each node, it is always relative for the problem you are trying to solve.
Comments.UserDisplayName: Miguel Saraiva
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-10T18:57:01.607Z
Comments.Text: I actually agree, my professor suggested it and I wanted to either calculate the complexity or have a good argument justifying why I didn't do it.
Comments.UserDisplayName: ATidedHumour
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-10T18:57:30.910Z
Comments.Text: You can still quantify the time complexity that depends on some parameter of the problem.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-10T19:06:26.677Z
Comments.Text: I would like to note that the time complexity of an algorithm actually depends on the implementation. For example, the usage of different data structures can affect the time complexity. So, I would suggest you to link us to or add to your post the algorithm (or its pseudocode) that you implemented. Furthermore, maybe this would be a question better asked on [https://cs.stackexchange.com](https://cs.stackexchange.com), even though I would say it is on-topic here too.
Comments.UserDisplayName: nbro
Tags: <monte-carlo-tree-search><time-complexity>
Title: What is the time complexity of an unparellelized Monte Carlo tree search?
UserDisplayName: ATidedHumour
ThreadText: # What is the time complexity of an unparellelized Monte Carlo tree search?
  
  (Asked by: username_0 on 2019-06-10)
  
  I am writing a report where I used a slightly modified version of MCTS (not parallelized). I thought It could be interesting if I could calculate its time complexity. I'd appreciate any help I could get.
  
  Here's the rough idea of how it works:
  
  Instead of tree search, I'm using graph search meaning I keep a list of visited nodes in order to avoid adding duplicate nodes.
  
  So in the expansion phase, I add all child nodes of the current node that aren't present elsewhere in the tree.
  
  For the remaining phases, it's essentially the same as the basic version of MCTS, with a default random policy in the simulation step.
  
  **Tags:** monte-carlo-tree-search, time-complexity
  
  > **Comments:**
  > **username_1**: Are you sure it makes sense to talk about time complexity in MCTS? It does not have a end or a certain amount of iterations you should do in each node, it is always relative for the problem you are trying to solve.  
  > **username_0**: I actually agree, my professor suggested it and I wanted to either calculate the complexity or have a good argument justifying why I didn't do it.  
  > **username_2**: You can still quantify the time complexity that depends on some parameter of the problem.  
  > **username_2**: I would like to note that the time complexity of an algorithm actually depends on the implementation. For example, the usage of different data structures can affect the time complexity. So, I would suggest you to link us to or add to your post the algorithm (or its pseudocode) that you implemented. Furthermore, maybe this would be a question better asked on [https://cs.stackexchange.com](https://cs.stackexchange.com), even though I would say it is on-topic here too.  
  
  ---
  
  ## 0 answers
  
  