<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>

CC BY-SA 4.0
2019-06-10T18:54:40.527Z
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.
Miguel Saraiva
CC BY-SA 4.0
2019-06-10T18:57:01.607Z
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.
ATidedHumour
CC BY-SA 4.0
2019-06-10T18:57:30.910Z
You can still quantify the time complexity that depends on some parameter of the problem.
nbro
CC BY-SA 4.0
2019-06-10T19:06:26.677Z
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.
nbro
<monte-carlo-tree-search><time-complexity>
What is the time complexity of an unparellelized Monte Carlo tree search?
ATidedHumour
# 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

