How should I define the action space for a card game like Magic: The Gathering?
There are several different ways you can model the state and action spaces in such sequential (extensive-form) environments/games. For environments with small action spaces or those typically introduced to beginning-RL students, the state space and action space remains constant along an agent's trajectory (termed normal form games when there are multiple agents). In sequential games which can be illustrated as trees, a &quot;state&quot; is analogous to &quot;information set&quot; which is defined as the sequence (tuple) of actions and observations since the beginning of the game's episode. Terminal states (leaf nodes) exist, and the action space $\mathcal{A}[x]$ at an information set $x$ can be defined as a union of action sequences that can be taken to each terminal state, not counting terminal states that cannot be reached from the current information set.
In the above examples, I discussed games such as the examples you stated where more than one agent can interact with the environment, but this is a generalization over RL and can be applied to when only one agent is maximizing its reward.