Is Monte Carlo Tree Search appropriate for problems with large state and action spaces?
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).