Answers.Body: <p>MCTS is often said to be a good choice for problems with large branching factors... but the context where that sentiment comes from is that it originally became popular for playing the game of Go, as an alternative to older game-playing approaches such as alpha-beta pruning. The branching factor of Go is more like 250-300 though, which is often viewed as a large branching factor for board games. It's not such an impressive branching factor anymore when compared to your branching factor of <span class="math-container">$6,000,000$</span>...</p>
  
  <p>I don't see MCTS working well out of the box when you have 6 million choices at every step. Maybe it could do well if you have an extremely efficient implementation of your MDP (e.g. if you can simulate millions of roll-outs per second), and if you have a large amount of "thinking time" (probably in the order of hours or days) available.</p>
  
  <hr>
  
  <p>To have any chance of doing better with such a massive branching factor, you really need generalization across actions. Are your 6 million actions really all entirely different actions? Or are many of them somehow related to each other? If you gather some experience (a simulation in MCTS, or just a trajectory with Reinforcement Learning approaches), can you generalize the outcome to other actions for which you did not yet collect experience? </p>
  
  <p>If there is some way of treating different actions as being "similar" (in a given state), you can use a single observation to update statistics for multiple different actions at once. The most obvious way would be if you can define meaningful features for actions (or state-action pairs). Standard Reinforcement Learning approaches (with function approximation, maybe linear or maybe Deep Neural Networks) can then relatively "easily" generalize in a meaningful way across lots of actions. They can also be combined with MCTS in various ways (see for example AlphaGo Zero / Alpha Zero). </p>
  
  <p>Even with all that, a branching factor of 6 million still remains massive... but generalization across actions is probably your best bet (which may be done inside MCTS, but really does need a significant number of bells and whistles on top of the standard approach).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-09T16:57:14.860Z
Answers.LastActivityDate: 2019-01-09T16:57:14.860Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>The question is whether MCTS is an appropriate method given these conditions.</p>
  
  <ul>
  <li><p>Action <span class="math-container">$a_t \in A_t$</span> </p></li>
  <li><p>State <span class="math-container">$s_t \in S_t$</span></p></li>
  <li><p><span class="math-container">$[a_t, s_t] \Rightarrow s_{t+1}$</span> </p></li>
  <li><p><span class="math-container">$t_i \land i \in [1, 40]$</span> </p></li>
  <li><p><span class="math-container">$A(t) \in \text{set} \, A \; \land \; \text{size} (A) = 6 x 10^6$</span></p></li>
  <li><p><span class="math-container">$S(t) \in \text{set} \, S \; \land \; \text{size} (S) = 1 x 10^8$</span> </p></li>
  <li><p>Transition function is stochastic</p></li>
  </ul>
  
  <p>MCTS focuses on the most promising sub-trees and is therefore asymmetric and well suited for some systems with a high branching factor, but the set sizes can be prohibitive unless some symmetries are exploited.</p>
  
  <p>The original MCTS algorithm does not converge quickly.  This is why alpha–beta pruning and other search strategies that focus on the minimization of the search space are often used, but they have limitations with regard to branching breadth too. Pruning heuristics can help with reducing the combinatoric explosion but may lead to the most advantageous action options being missed.</p>
  
  <p>Some variants of MCTS, such as those among the articles below and in the case of AlphaZero used to learn Go from only the game rules, show excellence in search speed, but perhaps not to the degree needed in this case without parallelism in the form of a computing cluster or significant hardware acceleration.</p>
  
  <p>An excellent characteristic of MCTS is that highly promising actions found early may be selected without exhausting all the sub-tree evaluations, but again, that may not be enough.</p>
  
  <p>A possibly constraining consideration is whether the Marcov property will be upheld, how, and whether it should be.  Another consideration is whether the system involves an opposing intelligent participant.  All sampling or pruning search strategies involve the risk of not reliably identifying a single branch in a sub-tree that leads readily to an irreversible (or difficult to reverse) loss.</p>
  
  <p>These are some excellent papers that discuss these considerations and provide a high level of experience in the form of research results. The computational challenge of tree searches with high branching is covered by the articles discussing approximate solvers, an area of high research intensity.</p>
  
  <ul>
  <li><p><a href="http://robotics.itee.uq.edu.au/~hannakur/dokuwiki/papers/isrr13_abt.pdf" rel="nofollow noreferrer"><em>An online POMDP solver for uncertainty planning in dynamic environment</em></a>, H Kurniawati, V Yadav, 2016</p></li>
  <li><p><a href="http://robotics.itee.uq.edu.au/dokuwiki/cache/ICRA15_GoldenABT.pdf" rel="nofollow noreferrer"><em>An online and approximate solver for pomdps with continuous action space</em></a>, KM Seiler, H Kurniawati, 2015</p></li>
  <li><p><a href="https://arxiv.org/pdf/1804.02573" rel="nofollow noreferrer"><em>Hindsight is Only 50/50: Unsuitability of MDP based Approximate POMDP Solvers for Multi-resolution Information Gathering</em></a>, S Arora, S Choudhury, S Scherer, 2018</p></li>
  <li><p><a href="http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/download/10985/11024" rel="nofollow noreferrer"><em>α-min: A Compact Approximate Solver For Finite-Horizon POMDPs</em></a>, Y Dujardin, T Dietterich, I Chades, 2015</p></li>
  <li><p><a href="http://www.aaai.org/ocs/index.php/WS/AAAIW16/paper/download/12582/12346" rel="nofollow noreferrer"><em>Reinforcement Learning as a Framework for Ethical Decision Making</em></a>, D Abel, J MacGlashan, ML Littman, 2016</p></li>
  <li><p><a href="https://arxiv.org/pdf/1807.04920" rel="nofollow noreferrer"><em>On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes</em></a>, N Balaji, S Kiefer, P Novotný, GA Pérez, 2018</p></li>
  <li><p><a href="https://arxiv.org/pdf/1802.09646" rel="nofollow noreferrer"><em>Optimizing over a Restricted Policy Class in Markov Decision Processes</em></a>, E Banijamali, Y Abbasi-Yadkori, 2018</p></li>
  <li><p><a href="https://www.jair.org/index.php/jair/article/download/10944/26075/" rel="nofollow noreferrer"><em>Probabilistic inference techniques for scalable multiagent decision making</em></a>, A Kumar, S Zilberstein, M Toussaint, 2015</p></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-06T14:43:56.533Z
Answers.Text: Thank you for the detailed answer and the suggestions.
  
  But does a stochastic transition function really imply the need for a POMDP? In my case every state is fully observable (nevertheless the transitions are stochastic) - so I think a MDP is adequate.
  
  Are there any suggestions for coping with stochastic transition functions (in the context of MDP & MCTS)? From what I've read, the stochastic transition is taken into account by the generative model, but is that really all? I doubt that in my case, because every state-action-pair has (due to stochastic) 90 potential subsequent states
Answers.UserDisplayName: D. B.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-20T17:35:40.100Z
Answers.LastActivityDate: 2019-01-20T19:17:52.353Z
Answers.LastEditDate: 2019-01-20T19:17:52.353Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>I'm doing a research on a finite-horizon Markov decision process with <span class="math-container">$t=1, \dots, 40$</span> periods. In every time step <span class="math-container">$t$</span>, the (only) agent has to chose an action <span class="math-container">$a(t) \in A(t)$</span>, while the agent is in state <span class="math-container">$s(t) \in S(t)$</span>. The chosen action <span class="math-container">$a(t)$</span> in state <span class="math-container">$s(t)$</span> affects the transition to the following state <span class="math-container">$s(t+1)$</span>.</p>
  
  <p>In my case, the following holds true: <span class="math-container">$A(t)=A$</span> and <span class="math-container">$S(t)=S$</span>, while the size of <span class="math-container">$A$</span> is <span class="math-container">$6 000 000$</span> (6 million) and the size of <span class="math-container">$S$</span> is <span class="math-container">$10^8$</span>. Furthermore, the transition function is stochastic.</p>
  
  <p>Would Monte Carlo Tree Search (MCTS) an appropriate method for my problem (in particular due to the large size of <span class="math-container">$A$</span> and <span class="math-container">$S$</span> and the stochastic transition function?)</p>
  
  <p>I have already read a lot of papers about MCTS (e.g. progressive widening and double progressive widening, which sound quite promising), but maybe someone can tell me about his experiences applying MCTS to similar problems or about appropriate methods for this problem (with large state/action space and a stochastic transition function).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-15T19:35:24.033Z
Comments.Text: What do you intend to use MCTS for exactly?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-18T17:22:49.333Z
Comments.Text: I would like to apply MCTS in the context of a stochastic optimization problem, which is why only 1 player exists in my problem.
Comments.UserDisplayName: D. B.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-19T14:10:20.730Z
Comments.Text: But which specific part of your problem you would like to solve with MCTS?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-09T03:29:21.607Z
Comments.Text: Do similar actions yield similar results? I.E. if I choose between two actions that appear similar, will they have very similar value in the long run? If so, it may be appropriate to embed the actions in some continuous space in the agent's policy, then perform an MCTS on the k-nearest neighbors (which are valid actions, of course) to the desired continuous proto-action. This is similar to this paper from DeepMind: https://arxiv.org/abs/1512.07679
Comments.UserDisplayName: Andrew Sansom
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-11T08:13:39.483Z
Comments.Text: i use MCTS for finding max action all the times, at least the action is somehow near the optimal action. Brute-force random action is crazy for problems with large possibility space
Comments.UserDisplayName: Dan D.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-12T21:24:58.027Z
Comments.Text: I'm not sure if there's a way to make MCTS work for this problem. But I would like to remark that $10^8$ states can probably be exhausted in a reasonable amount of time. And that your branching factor is quite close to the size of the state space, leading to short path on average. So there might be something to exploit there.
Comments.UserDisplayName: Celelibi
Tags: <reinforcement-learning><monte-carlo-tree-search><markov-decision-process><finite-markov-decision-process>
Title: Is Monte Carlo Tree Search appropriate for problems with large state and action spaces?
UserDisplayName: D. B.
ThreadText: # Is Monte Carlo Tree Search appropriate for problems with large state and action spaces?
  
  (Asked by: username_0 on 2019-01-09)
  
  I'm doing a research on a finite-horizon Markov decision process with $t=1, \dots, 40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t) \in S(t)$. The chosen action $a(t)$ in state $s(t)$ affects the transition to the following state $s(t+1)$.
  
  In my case, the following holds true: $A(t)=A$ and $S(t)=S$, while the size of $A$ is $6 000 000$ (6 million) and the size of $S$ is $10^8$. Furthermore, the transition function is stochastic.
  
  Would Monte Carlo Tree Search (MCTS) an appropriate method for my problem (in particular due to the large size of $A$ and $S$ and the stochastic transition function?)
  
  I have already read a lot of papers about MCTS (e.g. progressive widening and double progressive widening, which sound quite promising), but maybe someone can tell me about his experiences applying MCTS to similar problems or about appropriate methods for this problem (with large state/action space and a stochastic transition function).
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, markov-decision-process, finite-markov-decision-process
  
  > **Comments:**
  > **username_1**: What do you intend to use MCTS for exactly?  
  > **username_0**: I would like to apply MCTS in the context of a stochastic optimization problem, which is why only 1 player exists in my problem.  
  > **username_1**: But which specific part of your problem you would like to solve with MCTS?  
  > **username_2**: Do similar actions yield similar results? I.E. if I choose between two actions that appear similar, will they have very similar value in the long run? If so, it may be appropriate to embed the actions in some continuous space in the agent's policy, then perform an MCTS on the k-nearest neighbors (which are valid actions, of course) to the desired continuous proto-action. This is similar to this paper from DeepMind: https://arxiv.org/abs/1512.07679  
  > **username_3**: i use MCTS for finding max action all the times, at least the action is somehow near the optimal action. Brute-force random action is crazy for problems with large possibility space  
  > **username_4**: I'm not sure if there's a way to make MCTS work for this problem. But I would like to remark that $10^8$ states can probably be exhausted in a reasonable amount of time. And that your branching factor is quite close to the size of the state space, leading to short path on average. So there might be something to exploit there.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2019-01-09. Score: 1
  
  MCTS is often said to be a good choice for problems with large branching factors... but the context where that sentiment comes from is that it originally became popular for playing the game of Go, as an alternative to older game-playing approaches such as alpha-beta pruning. The branching factor of Go is more like 250-300 though, which is often viewed as a large branching factor for board games. It's not such an impressive branching factor anymore when compared to your branching factor of $6,000,000$...
  
  I don't see MCTS working well out of the box when you have 6 million choices at every step. Maybe it could do well if you have an extremely efficient implementation of your MDP (e.g. if you can simulate millions of roll-outs per second), and if you have a large amount of "thinking time" (probably in the order of hours or days) available.
  
  ---
  
  To have any chance of doing better with such a massive branching factor, you really need generalization across actions. Are your 6 million actions really all entirely different actions? Or are many of them somehow related to each other? If you gather some experience (a simulation in MCTS, or just a trajectory with Reinforcement Learning approaches), can you generalize the outcome to other actions for which you did not yet collect experience?
  
  If there is some way of treating different actions as being "similar" (in a given state), you can use a single observation to update statistics for multiple different actions at once. The most obvious way would be if you can define meaningful features for actions (or state-action pairs). Standard Reinforcement Learning approaches (with function approximation, maybe linear or maybe Deep Neural Networks) can then relatively "easily" generalize in a meaningful way across lots of actions. They can also be combined with MCTS in various ways (see for example AlphaGo Zero / Alpha Zero).
  
  Even with all that, a branching factor of 6 million still remains massive... but generalization across actions is probably your best bet (which may be done inside MCTS, but really does need a significant number of bells and whistles on top of the standard approach).
  
  
  ---
  
  ### Answer by username_6 on 2019-01-20. Score: -1
  
  The question is whether MCTS is an appropriate method given these conditions.
  
  * Action $a\_t \in A\_t$
  * State $s\_t \in S\_t$
  * $[a\_t, s\_t] \Rightarrow s\_{t+1}$
  * $t\_i \land i \in [1, 40]$
  * $A(t) \in \text{set} \, A \; \land \; \text{size} (A) = 6 x 10^6$
  * $S(t) \in \text{set} \, S \; \land \; \text{size} (S) = 1 x 10^8$
  * Transition function is stochastic
  
  MCTS focuses on the most promising sub-trees and is therefore asymmetric and well suited for some systems with a high branching factor, but the set sizes can be prohibitive unless some symmetries are exploited.
  
  The original MCTS algorithm does not converge quickly. This is why alpha–beta pruning and other search strategies that focus on the minimization of the search space are often used, but they have limitations with regard to branching breadth too. Pruning heuristics can help with reducing the combinatoric explosion but may lead to the most advantageous action options being missed.
  
  Some variants of MCTS, such as those among the articles below and in the case of AlphaZero used to learn Go from only the game rules, show excellence in search speed, but perhaps not to the degree needed in this case without parallelism in the form of a computing cluster or significant hardware acceleration.
  
  An excellent characteristic of MCTS is that highly promising actions found early may be selected without exhausting all the sub-tree evaluations, but again, that may not be enough.
  
  A possibly constraining consideration is whether the Marcov property will be upheld, how, and whether it should be. Another consideration is whether the system involves an opposing intelligent participant. All sampling or pruning search strategies involve the risk of not reliably identifying a single branch in a sub-tree that leads readily to an irreversible (or difficult to reverse) loss.
  
  These are some excellent papers that discuss these considerations and provide a high level of experience in the form of research results. The computational challenge of tree searches with high branching is covered by the articles discussing approximate solvers, an area of high research intensity.
  
  * [*An online POMDP solver for uncertainty planning in dynamic environment*](http://robotics.itee.uq.edu.au/~hannakur/dokuwiki/papers/isrr13_abt.pdf), H Kurniawati, V Yadav, 2016
  * [*An online and approximate solver for pomdps with continuous action space*](http://robotics.itee.uq.edu.au/dokuwiki/cache/ICRA15_GoldenABT.pdf), KM Seiler, H Kurniawati, 2015
  * [*Hindsight is Only 50/50: Unsuitability of MDP based Approximate POMDP Solvers for Multi-resolution Information Gathering*](https://arxiv.org/pdf/1804.02573), S Arora, S Choudhury, S Scherer, 2018
  * [*α-min: A Compact Approximate Solver For Finite-Horizon POMDPs*](http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/download/10985/11024), Y Dujardin, T Dietterich, I Chades, 2015
  * [*Reinforcement Learning as a Framework for Ethical Decision Making*](http://www.aaai.org/ocs/index.php/WS/AAAIW16/paper/download/12582/12346), D Abel, J MacGlashan, ML Littman, 2016
  * [*On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes*](https://arxiv.org/pdf/1807.04920), N Balaji, S Kiefer, P Novotný, GA Pérez, 2018
  * [*Optimizing over a Restricted Policy Class in Markov Decision Processes*](https://arxiv.org/pdf/1802.09646), E Banijamali, Y Abbasi-Yadkori, 2018
  * [*Probabilistic inference techniques for scalable multiagent decision making*](https://www.jair.org/index.php/jair/article/download/10944/26075/), A Kumar, S Zilberstein, M Toussaint, 2015
  
  > **Comments:**
  > **username_0**: Thank you for the detailed answer and the suggestions.  But does a stochastic transition function really imply the need for a POMDP? In my case every state is fully observable (nevertheless the transitions are stochastic) - so I think a MDP is adequate.  Are there any suggestions for coping with stochastic transition functions (in the context of MDP & MCTS)? From what I've read, the stochastic transition is taken into account by the generative model, but is that really all? I doubt that in my case, because every state-action-pair has (due to stochastic) 90 potential subsequent states  
  
  ---
  
  