How to apply reinforcement learning to combinatorial puzzles? I want to apply machine learning to a problem I have. It's essentially a kind of combinatorial puzzle where you want to get a high score like in "2048", except that unlike 2048, it is deterministic, you can reverse moves (so you don't 'die', you just get stuck in local minima when the grid is filled), and the number of possible moves in each 'turn' is large. 
I was wondering what kind of reinforcement learning would be a good choice for it? I've heard that with Q-learning you need a small space of possible actions to get good performance. I thought an AlphaZero-type algorithm might be good since it's been applied to games with very large action spaces (e.g. Go), but it seems to be used in two-player games and I don't know if you can use it on "single-player" puzzles. Btw I'm also pretty new to ML so any advice would be appreciated.
 A: First thing to consider, depending on your goals, is whether reinforcement learning (RL) is a good choice for your problem. In combinatorial problems, you may be better off investigating other solvers. There are dozens of potentially useful algorithms that could apply to NP-complete combinatorial problems like the classic travelling salesman problem or knapsack problem.
The fact that you can easily backtrack and re-try suggests one or more global combinatorial or sequence optimisers might be a good first choice. For example simulated annealing is a relatively simple base algorithm that is highly efficient when local changes to a solution can be made and evaluated for low cost. There are many other options - the book Clever Algorithms: Nature-Inspired Programming Recipes describes a broad selection, and is available as a free-to-access HTML version on the site.
Assuming that you still want to apply RL, either because you think it is a good fit, or because one of your goals here is to learn RL techniques, then I think the following applies to your questions from your brief description:

I was wondering what kind of reinforcement learning would be a good choice for it?

They should all work reasonably well in principle, as you have a deterministic environment that you can model and use to drive even simple approaches such as Value Iteration. What will work best depends on the scale of your puzzle, i.e. how many combinations are possible.
Your first problem will be state representation. You need a representation that can enumerate every possible combination. For the simplest tabular RL solvers, all possible enumerations should be able to fit in memory - clearly that only applies to small combinatorial problems that could also fit into memory and be brute-force searched though.
It is likely that a naive approach using Value Iteration or a variant of Q learning will perform about as well as an A* search. That is, better than a brute-force search, but otherwise not particularly well.
One way to improve on this naive approach is to use function approximation for the value functions, which is what the recently successful DQN (for Atari) and AlphaZero do using neural networks. This can help if the combinatorial problem has some underlying data or pattern that would allow for generalisation. Again you need to look at the state representation - this would work poorly if the only data you have is the IDs of objects that you were putting in sequence to get a score.

I've heard that with Q-learning you need a small space of possible actions to get good performance.

Q-learning does suffer from speed and accuracy problems when the number of actions is large. That is because one of the steps involves finding $\text{argmax}_a[Q(S_t,a)]$. In your case you can ignore the accuracy problems (due to over-estimating the reward from the maximising action) as your reward signal is deterministic. However, if you have a very large number of possible actions on each step - e.g. your agent can choose to allocate any remaining item into the sequence to create the combination - then the calculation for this term will be expensive.
Typically when Q-learning would be a problem in this way, you would choose a policy gradient method. The simplest one would be REINFORCE, but more popular are Actor-Critic and deterministic policy gradient algorithms. These algorithms search more directly in policy space.

I thought an AlphaZero-type algorithm might be good since it's been applied to games with very large action spaces (e.g. Go), but it seems to be used in two-player games and I don't know if you can use it on "single-player" puzzles.

AlphaZero combines a stochastic planning process (that tests a tree of "most likely" moves) with an RL approach very similar to Actor-Critic. The algorithm is definitely adaptable to a single-player game, and that should simplify it in a few places.
Again, as with Q-learning, whether or not is would help depends critically on the nature of the elements you are making combinations of in your game, and how you can represent them. For instance, in Go, the layout of the board and the consistent rules for surrounding territory and capturing pieces allow for a representation of the board as a grid of stone positions (plus some other basic features, such as recent plays and logical capture information) to be analysed by a neural network. If you just enumerated all possible board configurations and made AlphaZero learn from the ids of those states, it would fail.
A: Your intuition is correct. AlphaZero-like algorithms (Approximate Policy Iteration) can be used for single-player puzzles. In fact, I just wrote a paper on how we used these methods to solve Rubik's Cube. 
https://arxiv.org/abs/1805.07470 
