How to handle multiple types of decisions?

Question

In lots of games there are multiple phases or decision points that are not similar yet seem to have a dependency on one another when taking the perspective of the overall strategy of the player. A couple examples I thought up:

1. In a simple draw poker, you can have a strategy for discarding cards and a strategy for betting. They may not be mutually exclusive if you know your opponents betting will change with the number of cards you draw.

2. In Cribbage there are two phases, Discard to crib and the Play. The Play phase is definitely dependent on which cards are discarded in the discard phase. So it seems knowledge of Play strategy would be needed to make the Discard decision.

The intent is to learn how to set up an unsupervised learning algorithm to play a game with multiple types of decision making. Doesn't matter the game. I'm at a loss at the highest level in what ML models to learn to use for this scenario. I don't think a single NN would work because of the different decision types.

My question is how are these dependencies handled in ML? What are some known algorithms/models that can handle this?

I'm at a loss on what to even search for so feel free to dump some terminology and keywords on me. =)

Answer 1

Your intuition is correct, neural networks are a no go (except see bottom).

It seems like you'd want to look into the ML sub-field called Reinforcement Learning. In a nutshell, RL offers a set of methods to learn what is the best action to take in a given situation.

More formally, in RL settings the algorithm learns from experience by observing a reward ($R$) associated to an action ($a$).

RL problems can be conceptualized as Markov Decision Processes (MDPs). From Sutton & Barto:

MDPs are a classical formalization of sequential decision making, where actions influence not just immediate rewards, but also subsequent situations, or states, and through those future rewards.

MDP can be faced with several methods, mainly Monte Carlo Methods and Temporal-Difference Learning.

In short, both use the Bellman equation in different ways. A key component of the eq. is the discounting term ( $\gamma$ ). Values for rewards associated with future states are discounted (multiplied) by $\gamma<1$ in order to modulate the importance of future rewards.

Since you're concerned with strategy, another way to influence the agent's learning wrt. the environmental rewards is the adoption of an epsilon value $\epsilon<1$. When defining an $\epsilon$-greedy policy, the agent will choose the action with highest value $Q$ only with a probability equal to $1-\epsilon$. This enables the agent to balance exploitation of previous experience with the exploration of the environment. Very useful in cases where an immediate low reward compromises the achievement of a much higher reward later during the episode.

There's many other ways to influence the behaviour of your learner of choice to respond differently to its environment. For a complete view, I recommend Sutton and Burton who offer their book in pdf format for free at the given link.

Edit: almost forgot. Neural networks can be useful when combined with more classical RL methods, say Q-learning (a type of Temporal-difference learning), taking on the name of deep Q-learning. Alpha go also uses a combination of Monte Carlo methods combined with 2 NNs for Value evaluation and policy evaluation Wikipedia. I wouldn't necessarily venture in this domain without first having a clear overview of classical RL methods.

Hope this helps.