Categories
Algorithms Data Science OMSCS

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.

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#PlayersOutcomeDeterministic?Information#RoundStrategy
12Zero-sumDeterministic Perfect InformationSingle MinMax works, Pure strategy
22Zero-sumStochasticPerfect Single MinMax works, Pure strategy
32Zero-sumStochastic Hidden Single MinMax does NOT work, Mixed Strategy
42Non-zero sumStochastic Hidden outcome is same for every roundSolve for Nash Equilibrium, Pure or mixed
52zero-sum Stochastic Hidden defined by gamma With finite states, it is a Markov Decision Process. Solve Minimax-Q algorithm
62 or moreNon-zero sum Stochastic Not-hiddenDefined 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!