Learning in Cooperative Multiagent Systems Using Cognitive and Machine Models

Learning to coordinate in cooperative multiagent systems (MAS) has been a central problem that has drawn much attention in interdisciplinary research from robotics, economics, web-service technology (Wang et al., 2017), and in artificial intelligence (AI) communities (Lauer and Riedmiller, 2000a). Coordination, in this context, refers to the ability of two or more agents to jointly reach an agreement on the actions to perform in an environment. Applications of such coordinating tasks can be found in diverse settings, for instance, a team of robots working together to locate victims in a search and rescue situation (Jennings et al., 1997), or a group of robots required to coordinate to pick up, carry, and deliver goods in object transportation problems (Rus et al., 1995), or in the context of autonomous vehicles, where the coordination between autonomous vehicles and human drivers is crucial (Toghi et al., 2021a, 2022, b). This highlights the need to develop MAS that can learn to coordinate and cooperate with humans and other agents.

In the MAS literature, learning coordination is a cooperative problem wherein multiple agents are encouraged to work together towards a common goal by receiving an equally-shared reward (Matignon et al., 2012). Moreover, based on the information available to the agents, they can be independent or joint-action learners (Claus and Boutilier, 1998; Gronauer and Diepold, 2021). The independent learners are essentially non-communicative agents; they have no knowledge of the rewards and actions of the other agents. In contrast, joint-action learners are aware of the existence of other agents and can observe others’ actions. Many practical control applications feature a team of multiple agents that must coordinate independently to achieve a common goal without awareness of other members’ actions (Agogino and Tumer, 2012; Verbeeck et al., 2007). One example of this problem is a team of rescuers splitting up in a network of underground caves wherein information exchange is unavailable. In the current research, we are interested in the coordination problem from the perspective of independent learners who try to learn and adapt their actions to the other teammates’ behavior without communicating during learning.

There are a number of challenges for modeling independent learners in multiagent cooperative tasks. One major problem is simultaneous learning within a shared dynamic environment. If the agent selects what appears to be an optimal action for itself as an individual, and if all agents act with the same goal, the situation would result in poor joint actions (i.e., miscoordination). For instance, if a group of drivers departs from one location to the same destination and the driving navigator provides all drivers with the same path, a miscoordination and traffic jam could be generated. Therefore, the navigator’s strategies are subject to change over time, and the other agent also has to adapt to this change. Consequently, the presence of other learning and exploring agents make the environment a non-stationary and dynamic situation from the perspective of the independent agents (Tan, 1993). A number of studies have been proposed to cope with the non-stationarity problem (Foerster et al., 2017a, b), and yet, these works were inspired by centralized learning where agents can communicate freely (Foerster et al., 2018), rather than non-communicative agents.

To address this emergent challenge with non-communicative agents, numerous methods have been proposed in the literature of multiagent reinforcement learning (MARL), including distributed Q-learning (Lauer and Riedmiller, 2000b), hysteretic Q-learning (Matignon et al., 2007, 2012), and lenient Q-learning (Panait et al., 2006; Wei and Luke, 2016). In general, distributed and hysteretic learning operate under an optimistic learning assumption. That is, an agent selects an action that meets the expectation that the other agents also choose the best matching actions accordingly. Under this assumption, the agent prefers positive results when playing actions. Alternatively, the lenient method rests on the assumption that agents are more lenient initially when exploration is still high, but they become less lenient over time. Simply put, the more agents explore the environment, the less lenient they become. This idea is formulated in the model through a parameter (i.e., temperature value) that is used to control the degree of leniency. Particularly, the model associates the selected actions with the temperature value that gradually decays by the frequency of state-action pair visits. In another thread of research on how to achieve effective coordination between agents in MAS, (Hao et al., 2014; Hao and Leung, 2013) proposed a social learning framework that focuses on achieving socially optimal outcomes with reinforcement social learning agents. Recently, the integration of deep learning into these traditional Reinforcement Learning (RL) methods led to new branches of research, including multi-agent deep reinforcement learning (MADRL) approaches (Omidshafiei et al., 2017a; Gupta et al., 2017; Palmer et al., 2018; Lanctot et al., 2017).

Despite the advance in MADRL, these algorithms still perform poorly in tasks in which the environment is not stationary due to the dynamics of coexisting agents and the presence of stochastic rewards. Indeed, the presence of stochastic rewards can add further complications to the cooperation among agents since agents are not always able to distinguish the environment’s stochasticity from another agent’s exploration (Claus and Boutilier, 1998). Previous research showed that independent learners often result in poor coordination performance in complex or stochastic environments (Claus and Boutilier, 1998; Lauer and Riedmiller, 2000a; Gronauer and Diepold, 2021). This is perhaps due to ambiguity in the source of stochasticity since it can emerge from many factors, including possible outcomes or their likelihood. Despite the fact that prior studies have presented different approaches to cope with stochasticity in MAS (Matignon et al., 2007; Omidshafiei et al., 2017b; Palmer et al., 2018), there is significant room left for characterizing sources of stochastic rewards and addressing their effects on the performance of independent agents in the context of fully cooperative MAS.

It is well-known that humans have the ability to adapt to non-stationary environments with stochastic rewards rapidly, and they learn to collaborate and coordinate effectively, while algorithms cannot capture this human ability (Lake et al., 2017). Yet, when humans confront stochastic rewards with small-probability outcomes (henceforth referred to as rare events), the decision problem might become complex not only for algorithms but for humans too  (Hertwig et al., 2004). These situations involving highly impacting but rare events are, in fact, very common in real life (e.g., disasters, economic crashes) (Taleb, 2007). In decision making, dynamic cognitive models inspired by the psychological and cognitive processes of human decision making have been able to capture and explain the tendency for humans to underweight rare events (Gonzalez and Dutt, 2011; Hertwig, 2015). This current state of affairs motivates the main idea of our paper: constructing algorithms that combine the strengths of MADRL models and cognitive science models, to develop agents that can improve their learning and performance in non-stationary environments with stochastic reward and rare events.

Cognitive modeling has been developed to understand and interpret human behavior by representing the cognitive steps by which a task is performed. In particular, Instance-based Learning Theory (IBLT) was developed to provide a cognitively-plausible account for how humans make decisions from experience and under uncertainty, through interactions with dynamic environments (Gonzalez et al., 2003). IBLT has shown an accurate representation of human choice and broad applicability in a wide number of decision making domains, from economic decision making to highly applied situations, including complex allocation of resources and cybersecurity, e.g. (Hertwig, 2015; Gonzalez, 2013; Gonzalez et al., 2003). Also, recent work in combining a cognitive model based on IBLT and the temporal difference (TD) mechanism in RL (IBL-TD) has shed light on how to exploit the respective strengths of cognitive IBL and RL models (Nguyen et al., 2023). The idea of IBL-TD and the disadvantages of current MADRL in stochastic rewards, lead to questions of how would the IBL-TD perform in the context of cooperative MAS? And how would MAS that exploit cognitive models compare to state-of-the-art MADRL approaches to address fully cooperative tasks with stochastic rewards?

To that end, our first contribution here is to propose novel multi-agent IBL (MAIBL) models that combine the ideas of cognitive IBL models and concepts used in MADRL models, namely decreasing $\epsilon$-greedy, hysteretic, and leniency to solve fully cooperative problems from the perspective of independent agents. Next, we characterize different properties of stochastic rewards, including problems with rare events, to aim at understanding their effects on the behavior of independent agents in fully cooperative Coordinated Multi-Agent Object Transportation Problems (CMOTP), which have been used to test current MADRL algorithms (Palmer et al., 2018). Finally, we evaluate the performance of our proposed MAIBL models against these state-of-the-art approaches in the MADRL literature, including decreasing $\epsilon$-greedy, hysteretic, and lenient Deep Q-Network algorithms (Palmer et al., 2018) on four scenarios of CMOTP with respect to varying stochastic rewards. We demonstrate that MAIBL can significantly outperform MADRL with respect to different evaluation metrics across the choice scenarios.

In general, a fully cooperative multi-agent problem is formulated as a Markov game, which is defined by a set of states $\mathcal{S}$ describing the possible configurations of all agents, a set of actions $\mathcal{A}_{1},...,\mathcal{A}_{m}$, and a set of observations $\mathcal{O}_{1},...,\mathcal{O}_{m}$ for each agent. $\mathbf{A}=\mathcal{A}_{1}\times...\times\mathcal{A}_{m}$ is the joint action set. To select actions, each agent $i$ uses its policy $\pi_{i}:\mathcal{O}_{i}\times\mathcal{A}_{i}\to\mathbb{R}$, which produces the next state according to the transition function $\mathcal{T}:\mathcal{S}\times\mathbf{A}\to\mathcal{S}$. The agent $i$ receives rewards based on a conditional probability $P_{i}:\mathcal{S}\times\mathbf{A}\times\mathbb{R}\to[0,1]$ determining the probability of achieving a reward $r\in\mathbb{R}$ if the joint action $a\in\mathbf{A}$ has been executed in the current state $s\in\mathcal{S}$, and receives private observations correlated with the states $\mathbf{O}_{i}:\mathcal{S}\to\mathcal{O}_{i}$.

To date, a large body of research on MADRL focused on building agents that can quickly learn an optimal joint policy in cooperative multi-agent tasks. The most fundamental, as well as recent approaches to MADRL, are summarized in the following.

IBLT is a theory of decisions from experience, developed to explain human learning in dynamic decision environments (Gonzalez et al., 2003). IBLT provides a decision making algorithm and a set of cognitive mechanisms that can be used to implement computational models of human decision learning processes. The algorithm involves the recognition and retrieval of past experiences (i.e., instances) according to their similarity to a current decision situation, the generation of expected utility of the various decision alternatives, and a choice rule that generalizes from experience. An “instance” in IBLT is a memory unit that results from the potential alternatives evaluated. These are memory representations consisting of three elements: a situation (a set of attributes that give a context to the decision, or observation $o$); a decision (the action taken corresponding to an alternative in state $s$, or action $a$); and a utility (expected utility or experienced outcome $x$ of the action taken in a state).

In particular, for the agent $i$, an option $k=(o,a)$ is defined by taking action $a$ after observing state $s$. At time $t$, assume that there are $n_{k,t}$ different generated instances $(k,x_{j,k,t})$ for $j=1,...,n_{k,t}$, corresponding to selecting $k$ and achieving outcome $x_{j,k,t}$. Each instance $j$ in memory has an Activation value, which represents how readily available that information is in memory, and it is determined by similarity to past situations, recency, frequency, and noise (Anderson and Lebiere, 2014). Here we consider a simplified version of the Activation equation which only captures how recently and frequently instances are activated:

where $d$ and $\sigma$ are the decay and noise parameters, respectively, and $T_{j,k,t}\subset\{0,...,t-1\}$ is the set of the previous timestamps in which the instance $j$ was observed. The rightmost term represents the Gaussian noise for capturing individual variation in activation, and $\xi_{j,k,t}$ is a random number drawn from a uniform distribution $U(0,1)$ at each timestep and for each instance and option.

Activation of an instance $j$ is used to determine the probability of retrieval of an instance from memory. The probability of an instance $j$ is defined by a soft-max function as follows

where $\tau$ is the Boltzmann constant (i.e., the “temperature”) in the Boltzmann distribution. For simplicity, $\tau$ is often defined as a function of the same $\sigma$ used in the activation equation $\tau=\sigma\sqrt{2}$.

The expected utility of option $k$ is calculated based on a mechanism called Blending (Lebiere, 1999) as specified in IBLT (Gonzalez et al., 2003), using the past experienced outcomes stored in each instance. Here we employ the Blending calculation for the agent $i$ as defined for choice tasks (Lejarraga et al., 2012; Gonzalez and Dutt, 2011):

The choice rule is to select the option that corresponds to the maximum blended value. In particular, at the $l$-th step of an episode, the agent $i$ select the option $(o_{i,l},a_{i,l})$ with

Our proposed Multi-Agent IBL (MAIBL) Models are developed to deal with fully cooperative tasks that can be described as a Markov game (Shapley, 1953) where all agents receive the same rewards. Also, (Nguyen et al., 2023) proposed an IBL model (IBL-TD) that uses the TD-learning mechanism of RL models, to estimate the outcome of an action as follows:

where $\alpha$ is a learning rate and $\delta_{i,l}$ is an TD error defined by:

We refer to (Nguyen and Gonzalez, 2020a, b, 2021) to demonstrate how to investigate IBLT for multi-state environments.

The MAIBL process is described in Algorithm 1. We propose three MAIBL algorithms that rely on the IBL-TD, and are enhanced with a $\epsilon$-greedy exploration strategy to deal with fully cooperative tasks in MAS (Greedy-MAIBL); and a Hysteretic-MAIBL and Lenient-MAIBL, which are respectively the integration of hysteretic and lenient concepts from MADRL into the MAIBL models.

To make our focus concrete, we specifically consider one of the prominent examples of fully cooperative games which is the Coordinated Multi-agent Object Transportation Problems (CMOTPs) (Busoniu et al., 2010; Palmer et al., 2018; Tuci et al., 2006) with the presence of stochastic rewards. In such environments, we examine how well IBL-based models can learn and adapt to the other teammates’ behavior to accomplish the task without communicating during the learning process. We compare our proposed models with the three state-of-the-art algorithms in CMOTPs (see Section 2): Decreasing $\epsilon$-greedy double Deep Q-Network algorithm (Greedy-MADRL) (van Hasselt et al., 2016), Scheduled Hysteretic Deep Q-Network algorithm (Hysteretic-MADRL) and Lenient Deep Q-Network (Lenient-MADRL) (Palmer et al., 2018).

Many practical real-world applications require coordination in multi-agent systems to accomplish a common goal in the absence of explicit communication. Coordination in MAS becomes particularly complicated in the presence of reward stochasticity and rare events, since miscoordination may arise when independent learners have difficulty differentiating between the teammate’s exploratory behavior and the stochasticity of the environment. As a result, the current state-of-the-art MADRL models show that sub-optimal solutions emerge in non-stationary environments, due to these dynamics of coexisting agents and stochastic rewards.

This research proposes and demonstrates a solution to this problem in the current MADRL. Our solution is inspired by the human ability to adapt quickly to non-stationary environments, by the benefits of cognitive modeling approaches that have been demonstrated to capture this human behavior, and by the efficiency of RL computational concepts, such as the “temporal difference” adjustments that can be combined with cognitive approaches (Nguyen et al., 2023). Building on such concepts, we proposed three novel models to study cooperation and coordination behavior in MAS in the presence of stochastic rewards. The models called Greedy-MAIBL, Hysteretic-MAIBL and Lenient-MAIBL, combine the cognitive principles of the Instance-Based Learning Theory (Gonzalez et al., 2003; Nguyen et al., 2022) and RL techniques to address coordination of MAS with stochastic rewards. In particular, the Greedy-MAIBL model is the enhancement of the IBL natural exploration process with the decreasing $\epsilon$-greedy Boltzmann exploration strategy due to the characteristics of the cooperative multi-agent tasks that typically require the agents to explore the environment extensively. The Hysteretic-MAIBL and Lenient-MAIBL are the methods that involve the integration of optimistic learning and leniency ideas from RL into the Greedy-MAIBL model.

We demonstrate the merits of combining cognitive IBL and RL approaches in fully-cooperative multi-agent problems that exhibit challenging characteristics of stochastic rewards. In particular, a simulation experiment demonstrates different sources of stochasticity challenges for the MADRL models and the benefits of using MAIBL models in a Coordinated Multi-agent Object Transportation Problem. The results demonstrate these benefits on metrics including efficiency and coordination.

Our findings reveal that our proposed approaches, which are a combination of cognitive IBL and RL concepts, outperform the three state-of-the-art Deep Reinforcement Learning (DRL) algorithms in all the scenarios of stochastic rewards. These results can be attributed to the benefits of leveraging the cognitive, memory retrieval process in IBL models when applied to multi-agent problems. Indeed, the results emphasize the importance of how MAIBL models characterize the cognitive frequency and recency information in the presence of stochastic reward in MAS. Although Lenient MADRL models have been advanced by incorporating the frequency information to determine how lenient an agent is supposed to be regarding others’ actions, our experimental results show that it does not characterize the frequency as effectively as MAIBL models do. In MAIBL models, such frequency and recency characteristics are well captured and represented due to the declarative knowledge offered by a well-known cognitive architecture, ACT-R (Anderson and Lebiere, 2014), which derives from well-validated human memory retrieval processes. Additionally, it is clear that the MAIBL models also inherit the advantage of RL concepts, that is, decreasing $\epsilon$-greedy for exploration and optimistic learning of hysteretic. Thus, it is this combination of the cognitive concepts or IBL models and the computational advantages of Deep RL mechanisms that can make the MAIBL models advantageous over the MADRL in stochastic situations.

These results can inform the selection of models that are more appropriate in specific stochastic settings and identify the characteristics of a task given an unknown reward scheme. More concretely, the results suggest that using the simple Greedy-MAIBL model itself, the one that has the least number of parameters, it is able to surpass the other sophisticated models in the scenarios where the highest expected reward is associated with the deterministic option regardless of the probability of returning the high value of the stochastic alternative. Our findings also indicate that Hysteretic and Leninent-based models are sensitive to the choice of the parameters and require a longer process to be able to accomplish the task. Given that hyper-parameter tuning is one of the challenging and crucial steps in the successful application of Deep RL algorithms, this work demonstrates the great benefit of using a simple Greedy-MAIBL model in settings in which the highest expected reward is associated with the deterministic alternative.

We also learned that when the stochastic option yields the higher expected reward, incorporating Hysteretic mechanism into the Greedy-MAIBL is beneficial, leading to the fact that Hysteretic-MAIBL outperforms other models in these cases. The advantages of the Hysteretic-MAIBL model are gained from the optimistic learning idea characterized in the hysteretic model and from the frequency, and recency biases inherited in the Greedy-MAIBL model. The results suggest that in the scenarios where the stochastic alternative yields the higher expected reward, it is important for a model to integrate optimistic learning, frequency, and recency biases to effectively address fully cooperative MAS. Interestingly, the results further demonstrate that not all combinations of the IBL model and RL concepts are advantageous. Specifically, we observed that Leniency-MAIBL is not as effective as expected, suggesting that incorporating both methods of characterization of frequency in Lenient-MAIBL might not be beneficial.

Arguably, one of the main goals of AI is to generate agents that can collaborate with humans and augment people’s capabilities. Due to human suboptimality, prior research in collaborative scenarios has shown that agents trained to play well with other AI agents perform much worse when paired with humans (Carroll et al., 2019). By incorporating the cognitive characteristics of humans’ decision behavior, we expect that the MAIBL models will enhance human-AI collaboration. That is, they would learn to be more adaptive to human behavior. Therefore, our future research will evaluate the performance of the MAIBL models as teammates collaborating with human participants. We further intend to experiment with heterogeneous teams wherein we team MAIBL models with different types of MADRL models. In future work, we also plan to investigate the robustness of our proposed models in different settings of multi-agent tasks, such as the sequentially coordinated delivery with the presence of multiple roles and expiration time. In such a problem, there are two roles of agents, and the accomplishment of the task requires the sequential collaborations of two sub-tasks. Moreover, progress in cognitive science suggests that computational models that accurately represent human behavior would be able to collaborate with humans more successfully than models that are focused on engineering rather than the cognitive aspects of learning (Lake et al., 2017). Given the demonstrated ability of IBL models to learn quickly and account for human learning in a wide range of tasks (Nguyen et al., 2022; Nguyen and Gonzalez, 2021), our proposed models that are based on the combination of IBL and DRL models are expected to be an effective human partner in cooperative human-machine teaming tasks.

The code of the MAIBL models is implemented using the SpeedyIBL library (Nguyen et al., 2022). All the code for MAIBL models, simulation data, and all scripts used for the analyses presented in this manuscript are available at https://github.com/DDM-Lab/greedy-hysteretic-lenient-maibl. The codes for the comparative models are available at https://github.com/gjp1203/nui_in_madrl.