# Which ML approach is the best for huge state spaces?

My issue derives from the challenge of solving a seemingly easy-looking game. To spare you the full catalogue of rules, here is a short summary of the game:

• Single player card game
• You go through a standard deck of cards and need to choose an action for each card (without knowing the next cards)
• For each of the choices you have a huge variant of possibilities (about ~15 stacks) to apply the cards to - given certain suit and rank combos you get points (lots of rules underlying - thus this description represents the gist setting of the game)

If the cards were known, you could (by backpropagation) calculate the perfect choice in order to get the maximum amount of points. Intuitively, I tried writing an algorithm to simulate as many moves as possible into the future to determine the best choice. Even with various pre- and post-pruning methods (such as trivial mini-max), it would take hours to calculate one decision in a semi-reliable manner (considering most rewards are only "seen" about 15+ moves after the choice).

For the last couple of weeks, I abandoned this basic approach and went ahead to look for viable reinforcement learning ideas. To say the least, I felt completely lost due to various problems, i.e. integrating the "card count" into my state space. Should I include the full track of cards remaining (more detailed) or revert to a well-known implementation (Hi-Lo System in Blackjack for example.. has many similarities to this project).

All in all, I wanted to ask for a usable proposal in order to solve a immense-state space ("continuous"?) problem with self, reinforcement learning. I peeked into DeepQ learning or alike, but couldn't find good literature in regards to solo-player card games like Blackjack which require you to keep a card count. Besides that, the delayed reward makes it harder to compare to such projects.

• On a slight off-topic note: With the statement "revert to a well-known implementation" I was implying a similar method to the Hi-Lo-System which Blackjack users might use. Obviously the development of such a novel concept might bring flaws. Furthermore, one of the benefits of (in comparison to humans) solving it with technical assistance should be that I could get an in-depth count and not an vague estimation. Though as mentioned in regards to card-counting I wouldn't know how to comprise it in an efficient state space -> in combination with the other factors we're left with a huge [1/2] Jan 19 at 13:43
• action space. Due to me not being the most experienced in ML projects (except of a few small usages), I had problems using e.g. DeepQ learning with my implementation / interpretation of this big action space. Surely, there is a more efficient and easier approach to this..! Jan 19 at 13:45
• I can't help about the exact question because I know nothing about reinforcement learning. But to me this problem is a good candidate for genetic learning: simulate multiple full games, at first by picking a random move. The objective function is calculated on the full game. The design of the features is very important, it has to represent all the possible strategies/choices. Jan 19 at 22:55
• @Erwan First off, thanks for your reply! Now to your reply.. "objective function is calculated on the full game": Though each move may distribute points (or hinder you to gain points in the future due to another stack rather needing that card). Is it a smart approach to only observe the end amount? Secondly, you mentioned that "[t]he design of the features is very important, it has to represent all the possible strategies/choices". All choices can be represented pretty easily, i.e. the card may go to any of the stacks. The strategy needs to be figured out by the ML approach.. Jan 20 at 9:17
• Assuming that your goal is to obtain a good AI player for the game, you probably need to model a large set of strategies rather than just the state of all possible actions. This means that features should represent an algorithm which determines which action to make depending on the current knowledge of the game. For example a feature could be "if card is X then do action Y", but it could also be more complex "if card is X1 and card X2 has been seen before then do action Z". What the genetic algorithm would find is the best performing strategy (actually only a local maximum). Jan 20 at 15:16

There have been success modeling card games with reinforcement learning (RL) using Deep Q-learning Network (DQN) with experience replay. Experience replay buffer is a large collection of tuples: (state (s), action (a), reward (r), next state (s′). An RL agent can learn which combinations lead to the highest reward. The representations are stored in a deep learning network which can learn very large state-space representations. This deep learning representation can replace an explicit card count.

One option is to adapt an OpenAI environment. There is already an OpenAI environment for Blackjack. After your card game is encoded in an environment, an agent can be trained with a DQN. A good starting point is Stable Baselines3 (SB3), a set of reliable implementations of reinforcement learning algorithms in PyTorch, which as a DQN implementation.

• According to your logic, my state shouldn't include the card count...? Wouldn't that be confusing if we look at single steps (i.e. from state to next state; s -> s') as the DQN would be punished once with a high card count for an action it was rewarded earlier. If we don't reward on steps and only on the final outcome of the game, the experience reply buffer doesn't seem to make sense for me. Jan 22 at 10:22

I found Superhuman AI for multiplayer poker a good paper on card games. Even though it is talking about a 6-player game, there is still much to use here. E.g. they reduce the huge number of betting moves to round numbers by action abstraction. (But note that this is mainly for training, and they let it be flexible when in actual play.)

Also this bit sounds like it might apply to your game:

The other form of abstraction that we use in Pluribus is information abstraction, in which decision points that are similar in terms of what information has been revealed (in poker, the player’s cards and revealed board cards) are bucketed together and treated identically

The other game your description reminded me of is sokoban, which is single player. You could consider the number of next moves is just 4 (the 4 directions the player can move), but from that point of view the games last hundreds and thousands of moves, and a mistake on move N is only discovered when you find a deadlock on move N+100. (Minimizing the number of moves made is a common metric used to evaluate a solver.)

arXiv:1802.04697 is a machine learning approach. I found it a bit disappointing, as I was more looking to find out what the state of the art currently is. They didn't compare their results to other sokoban solvers, which I take to mean their machine learning version was inferior, and that the best solvers are still hand-crafted expert systems.

But from your point of view that might make it a useful paper, and the Related Work should give some more jumping off points.

• Yes, in my research I also read about Pluribus and it's success against renowned Poker players. Using their abstraction approach might reduce the state, but only minimally, i.e. I could exclude the few played / remaining cards by doing calculation on the currently seen cards on the stacks. Still, including the card count would translate to an enormous state space. As far as comparing my game to Sokoban, which I didn't know of before your post, is a good idea - though the concepts in the linked paper poorly transfer to my situation, as far as I grasped them. Jan 25 at 11:13

I've never had the pleasure of working on AI in a space like this. And boy would I love to. you have so many good things working for you

• you don't need a dataset, as playing the game and winning effectively validates itself
• Judging model performance is fairly easy, as playing the game and winning means your better than the thing you played against (generally)

In terms of how to train and test your model, this seems like the best approach to me. Have your model play the game against other models, and be positively or negatively reinforced based on the outcome of that game. Exactly how you choose to do this is up to you, but some things to consider:

• you may want to employ regularization strategies, like batching games, dropout layers, etc.
• with a one player game, whoever gets the better score wins.

# Evolutionary hyperparameter selection

Some people mentioned evolutionary strategies in the comments. Something that particularly resonates with me is NEAT, and how it handles "breeding" models in "species". You may be interested in this for your problem.

Not only could you use an adversarial strategy to adjust model weights, you could also have the win/loss ratio for a particular model function as it's fitness, allowing you to breed hyperparameter settings for a particular "species" of model. That would allow you to explore multiple modeling paradigms and hyperparameter settings simultaneously. In essence, this would be a smarter version of random search hyperparameter tuning.

# Model choice

In terms of the actual model chosen, I must admit this isn't my field of expertise. Some people mentioned canned models designed for the use case, which are probably fine choices. Some modeling strategies that seem like they would work in my opinion:

(keep in mind, you can have these compete against each other by encapsulating in an evolutionary strategy)

## RNN

iteratively picking up cards and deciding on tasks based on that card, and the previous cards, seems like a task RNN's are designed to handle. Particularly an LSTM seems like a popular choice. You could mount an LSTM as your input layer, and pass the state between successive predictions to get an efficient way to encapsulate a long state space

## A really big multi dimensional NN

you could also have a dimension for each card, and a big long line of them. You could then compress that into a much smaller series of dense layers. That seems like it may be an ok way of distilling your large space into a more abstractaction, smaller dimension space quickly.

## ensemble decision tree

It seems like the decisions are pretty simple, the issue is you have a lot of them. You could use an ensemble of decision trees looking at different aspects of the historical record of past cards, and attempt to use them as a "funnel" to spit out a sensible solution.