Minority Game using Reinforcement, Social (Imitation) Learning.
Msc Thesis Java implementation. Abstract: Learning has been given much attention in Artificial Intelligence (AI) and Game Theory (GT) disciplines, as it is the key to intelligent and rational behavior. However in a multiagent setting, as in Multi-agent Systems (MAS), where the environment changes according to the actions of the players, the participants cannot afford to be fully rational and resort to heuristics. In such cases classic Game Theory fails to provide convergence results of the adjustment process, thus losing predictive power. Evolutionary Game Theory (EGT), motivated from biology, has been proven suitable for analyzing bounded rationality and heuristic learning using the robust replicator dynamics. In this thesis we use a famous congestion game with many (odd) participants called the Minority Game (MG) as a learning paradigm. The most critical learning methods used in the MG are reviewed, motivated from both economics and machine learning perspective along with their results. Continuing, individual-reinforcement learning through replicator dynamics is analyzed and the asymptotic properties of the learning procedure in the MG are provided. Moreover, we compare individual learning with social learning through imitation using agent-based simulations. The two types of learning do share common convergence characteristics, but differ in the resource allocation schemes and in terms of robustness. Individual-reinforcement learning is a more utilitarian process maximizing system efficiency with disregard to single-agent performance. On the other hand, social imitation can provide a more egalitarian setting where individual scores are almost equal.
How It Works
In this model each square patch is a distinct agent.
Single-Population Case (Social Learning): There is a single population of agents and each agent is equipped with a mixed strategy to play actions {-1,1}. Each round an odd number of agents (NumberOfAgentsInPlay) are chosen to play the Minority Game. In short, the chosen agents play their encoded strategy and the ones using the action of the minority, win a point. At each revision round(NumberOfImitationRounds ) , agents have the chance to revise their strategy. Each agent (imitator) picks another agent (called agent-reference) at random from his OWN population. If the agent-reference has a better score than the imitator, the imitator takes the action without mutation following the pairwise revision protocol. That is he/she imitates with a probability proportional to their payoff difference.
Multi-Population Case (Reinforcement Learning): There are an odd number of population, consisting of agents.
Every population can be subdivided into two subpopulations of agents using action 1 and 0. Agents using action 1, 0 are colored blue and red respectively. Therefore, each population can be seen as a single agent using the mixed strategy corresponding to the portion of agents playing action 1, 0 respectively. In each round, a random agent from each population is chosen to play the Minority Game. In short, the chosen agents play their encoded action and the ones using the action of the minority, win a point.
At each revision round(NumberOfImitationRounds ) , agents have the chance to revise their action. Each agent (imitator) picks another agent (called agent-reference) at random from his OWN population. If the agent-reference has a better score than the imitator, the imitator takes the action without mutation following the pairwise revision protocol.
How To Use It
Select a seed to start the Random Number Generator. Set a large number of the number of Rounds for each Game(NumberOfRounds). Set the number of repetitions of the Game (NumberOfRuns). Choose number of initial populations. In the case of one population the game is played with social learning. If the populations are more than one, the algorithm will run the Reinforcement Learning process. Select NumberOfAgents for each population. The variable NumberOfAgentsInPlay is used in the single population case to determine how many agents play the game at each round. The NumberOfImitators is the number of agents revising their strategy-action when they have a revision opportunity. NumberOfImitationRounds the interval of rounds when imitation is to happen. Thus, every (NumberOfImitationRounds ) rounds, chosen agents have revision opportunity. ProbChangeFactor is the factor multiplied by the normalized payoff difference to regulate the probability of imitation. Check out the Prototype also, at http://grstathisportfolio.wordpress.com/category/artificial-intelligence/
Current Status
The core algorithm of reinforcement and imitation learning is done. Java Documentation is updated.
TODO
- Improve GUI.
- Implement Graphics.
- Improve User Experience.
- Introduce Mutation.