Reinforcement learning meets minority game: Toward optimal resource allocation

The main point of this paper is to provide an affirmative answer through exploiting reinforcement learning (RL) in artificial intelligence (AI) for eliminating herding without any external control in complex resource allocation systems. In particular, we demonstrate that when agents are empowered with RL (e.g., the popular Q-learning algorithm in AI) in that they get familiar with the unknown game environment gradually and attempt to deliver the optimal actions to maximize the payoff, herding can effectively be eliminated. Furthermore, computations reveal the striking phenomenon that, regardless of the initial state, the system evolves persistently and relentlessly toward the optimal state in which all resources are used efficiently. However, the evolution process is not without interruptions: there are large fluctuations that occur but only intermittently in time. The statistical distribution of the time between two successive fluctuating events is found to depend on the parity of the evolution, i.e., whether the number of time steps in between is odd or even. We develop a physical analysis and derive mean-field equations to gain an understanding of these phenomena. Since AI is becoming increasingly widespread, we expect our RL empowered minority game system to have broad applications.

Figure 1

Typical temporal evolutionary behavior of the proposed minority game system with RL empowered agents. (a) Time series of the attendance $A\left(t\right)$ of resource $+1$. Interactions among the agents make the system self-organize into a special temporal pattern with two main features: the convergence of regular oscillations toward the optimal value $C_r=N/2$, and intermittent bursts of failures in utilizing resources. (b) A schematic sketch of the state transitions of agents during the dynamical process. There are self-satisfied agents in a fixed state and speculative agents that continuously switch states between $+1$ and $-1$. (c) Time series of $Q(s,a)$ as the numerical solutions of Eqs. (2, 3, 4). The parameters are as follows: learning rate $\alpha =0.9$, discount factor $\gamma =0.9$, exploration rate $\epsilon =0.02$, and system size $N=5001$.

Figure 2

Convergence of regular oscillations and bursts of failure. (a),(b) Convergence of the regular oscillation pattern depends on the exploration behavior of the agents as characterized by the rate $\epsilon$. For $\epsilon =0$ (gray region), the oscillation amplitude does not converge. (c),(d) Detailed processes for the bursts of failure. If the regular oscillations do not cross the line $C_r=N/2$ but behave either as (c) $A\left(t\right)>C_r$ and $A(t+1)>C_r$ or as (d) $A\left(t\right)<C_r$ and $A(t+1)<C_r$, the regular oscillations stop and a systematic failure burst emerges. The blue line specifies $A\left(t\right)=C_r$. The parameters are the same as in Fig. 1.

Figure 3

Statistical distributions of the time interval $T_0$ between two successive bursts of failure. (a) The distributions obtained from one realization of the system dynamics, where those of the odd $T_0$ values (red crosses) and even $T_0$ values (blue squares) are remarkably distinct. (b) $T_0$ vs the deviation $A_0-C_r$ of the equilibrium position from the resource capacity. The solid squares (triangles) denote the most probable value of the set of even (odd) $T_0$ values. The parameters are $\alpha =0.9$, $\gamma =0.9$, and $N=5001$. (c)–(f) Schematic illustration of four cases associated with the regular oscillations of $A\left(t\right)$, where cases (c),(d) lead to odd intervals $T_0$ while cases (e),(f) lead to the even values of $T_0$. The dashed curves represent the envelopes that cross the capacity value $C_r$ (solid blue lines), which triggers a failure burst.

Figure 4

Comparison of dynamical evolution of the system obtained from simulation and mean-field theory. The attendance $A\left(t\right)$ obtained from (a) multiagent simulation and (b) numerical solution of Eqs. (4, 5, 6, 7, 8, 9). (c), (d) The corresponding results of the elements of $\mathbf{Q}$ from multiagent simulation and from numerical solution, respectively. The insets in (a)–(d) show the corresponding time series of $A\left(t\right)$ and $\mathbf{Q}$ in a large time regime. The parameters are $\alpha =0.9$, $\gamma =0.9$, $\epsilon =0.02$, and $N=5001$.

Figure 5

Matrix norm $d$ for all agents empowered with RL. The norms are indicated by the two red arrow positions in Fig. 1. (a)–(d) Evolution of the matrix norm $d$ at three adjacent time steps: $t+1$ vs $t$ and $t+2$ vs $t+1$. The blue line is $x=y$. Panels (a),(b) correspond to the left arrow, and (c),(d) to the right arrow. (e),(f) The corresponding distributions of the matrix norm.