How do you define an action space for a card game with an unlimited and variable hand size?

Question

I'm new to the world of AI and have been primarily reading through the documentation for OpenAI's Gym/Gymnasium in hopes of training an AI to play a board game. One piece of information I haven't been able to find is the best way to define an action space when the number of possible actions is countably infinite.

For instance, I've seen several examples of simple games where the player must choose a card to play from their hand. In all of these, the hand has a maximum size, and the action space is discrete with its cardinality being the largest possible hand size. But what if there is no theoretical limit to the size of the player's hand? Let's say a player starts with a hand of seven cards, but the number of cards in their hand could grow (or shrink) to any natural number throughout the course of the game. How would one go about defining the action space in this scenario?

I've thought of four potential ways to handle this:

1. Define one action for every possible card and mask the action space so that only cards in the player's hand are legal actions. This would mean 52 actions for a standard deck of playing cards, which doesn't seem so bad. But for certain games, there could be many more kinds of unique cards (potentially thousands in the case of trading card games), and I could see the action space becoming unwieldy in those situations.
2. Define a continuous action space on the interval [0,1] and partition it equally into however many cards are in the player's hand. For example, if there are 10 cards in the hand, an action in [0,0.1) would play the first card, one in [0.1,0.2) would play the second, and so on. I'm unsure if this would be a wise setup since "nearby" actions like 0.09 and 0.11 wouldn't necessarily correspond to similar results because cards 1 and 2 aren't ordered in a meaningful way.
3. Define two actions: one for playing a card and the other for passing. Loop through each card in the hand and apply the action to each one until the "play" action is used. In this case, I'm not sure if the AI would be able to "look ahead" to know that a better card is coming up so therefore it should pass on the current card.
4. Pick an arbitrarily large hand limit that a player would never reach in practice and define a discrete number of actions up to that limit.

Would any of these approaches work? Are any favored over the others? Are there other ways of approaching this that I haven't thought of?

Answer 1

A policy that handles an arbitrary number of actions can be specified as a function (think: neural network) that takes one specific action as input and outputs some kind of score.

That score may be the estimated action-value, but the point is that you can simply pick the action with maximum score now. Or feed the variable number of scores into a softmax distribution, then sample from it to pick a plausible random action.

I'm not sure if the Gym/Gymnasium API is any help in modelling this kind of action-space. For board games specifically you may find some recent papers[1] that explain their approach, which usually involves tree-search.

Also think about how your agent will see the world. If it gets to select one of 500 actions, it will have a really hard time (need a lot of data) to learn that action number 311 means something completely different in one state compared to another. So depending on the game, it may be useful to add local features. (Like state of the evaluated action's neighbours, if applicable.) If the game state is just one huge opaque bitmask, the agent will have to discover via trial and error that there are local neighbourhoods, symmetry, etc.

Again specifically for board-games, if you can exactly predict the next state based on an action, it may be sufficient learn the value of a state.

[1]: Schrittwieser et al., 2020: Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model