  Efficient allocation is important in nature and human society where
individuals often compete for finite resources. The Minority Game is perhaps
the simplest model that provides deep insights into how human coordinate to
maximize the resource utilization. However, this model assumes the static
strategies that are provided a priori, failing to capture their adaptive
nature. Here, we turn to the paradigm of reinforcement learning, where
individuals' strategies are evolving by evaluating both the past experience and
rewards in the future. Specifically, we adopt the Q-learning algorithm, each
player is endowed with a Q-table that guides their decision-making. We reveal
that the population is able to reach the optimal allocation when individuals
appreciate both the past experience and rewards in the future, and they are
able to balance the exploitation of their Q-tables and the exploration by
randomly acting. The optimal allocation is ruined when individuals tend to use
either exploitation-only or exploration-only, where only partial coordination
and even anti-coordination are observed. Mechanism analysis reveals that a
moderate level of exploration can escape local minimums of metastable periodic
states, and reaches the optimal coordination as the global minimum.
Interestingly, the optimal coordination is underlined by a symmetry-breaking of
action preferences, where nearly half of the population choose one side while
the other half prefer the other side. The emergence of optimal coordination is
robust to the population size and other game parameters. Our work therefore
provides a natural solution to the Minority Game and sheds insights into the
resource allocation problem in general. Besides, our work demonstrates the
potential of the proposed reinforcement learning paradigm in deciphering many
puzzles in the socio-economic context.
