Game Theory Concepts for Reinforcement Learning

There are many flavors of games in Game Theory which are interesting from Machine Learning perspectives, especially from multi-agent Reinforcement Learning applications. Here is the summary of multiple game types are if MinMax algorithm works and what type of strategy one needs to employ.

Game ID	#Players	Outcome	Deterministic?	Information	#Round	Strategy
1	2	Zero-sum	Deterministic	Perfect Information	Single	MinMax works, Pure strategy
2	2	Zero-sum	Stochastic	Perfect	Single	MinMax works, Pure strategy
3	2	Zero-sum	Stochastic	Hidden	Single	MinMax does NOT work, Mixed Strategy
4	2	Non-zero sum	Stochastic	Hidden	outcome is same for every round	Solve for Nash Equilibrium, Pure or mixed
5	2	zero-sum	Stochastic	Hidden	defined by gamma	With finite states, it is a Markov Decision Process. Solve Minimax-Q algorithm
6	2 or more	Non-zero sum	Stochastic	Not-hidden	Defined by gamma	Active Research!

Comments on Strategy

Game ID#4: If strongly dominant strategy is present, then pure strategy might work or else might need a mixed strategy

Game ID#5: For small number of rounds (gamma~=0), betrayal might provide more reward, but for infinite number of rounds (gamm~=1), cooperation yields more reward

Interesting Facts from the Theory

1. Tit-for-Tat is not subgame perfect when considering a longer future time horizon! It means it can give itself more rewards overall if it does not choose to retribute against the other player! So forgiveness is a better virtue! This forgiving strategy is called Pavlov state machine!