Non-Markovian Reward Decision Processes have proven very efective in defining and solving complex tasks for autonomous agents, and recent work has focused on devising relative models and algorithms. When applied to multiple agents, they can efectively define complex multi-agent behaviors. In this paper, we discuss the main advantages in using a Multi-Agent Model-Based Reinforcement Learning approach for solving complex tasks in Multi-agent systems with temporal goals. We use the challenging scenario of Multi-Agent Pickup and Delivery as a case study to illustrate potential benefits of the proposed approach.
Reinforcement Learning (RL) has exhibited exceptional results in diferent domains, due to its ability to
deal with complex environments, even with minimal prior knowledge. A crucial factor in designing
RL tasks is the definition of the reward function, i.e., a real-valued function capturing the agent’s task.
Indeed, when the task complexity grows, defining efective reward functions becomes increasingly
challenging, especially if temporal sub-tasks are involved. A body of research has investigated this
problem, leading to the introduction of Non-Markovian Rewards (NMRs) and Non-Markovian Reward
Decision Processes (NMRDPs) as models for capturing complex tasks, as well as to the adoption of
temporal logic and automata-based formalisms for the specification of NMRs – see, 1e,.g2.,,3[
A fundamental result of these works has been proving that every NMℳRcDaPn be mapped into
an equivalent Markov Decision Process (MDℳP)′, representing the NMR as a suitable Deterministic
Finite-state Automaton (DFA), modeling the synchronous joint dynamics of the environment and the
NMR. It has been shown that standard RL algorithms, in particular model-free, can be used for learning
in such a joint model4[
CEUR
ceur-ws.org
In this short paper, we discuss the use of model-based RL approaches in Multi-Agent Systems (MAS) with non-Markovian rewards, focusing on two important techniques: 1) decoupling and separately learning the Markovian environment transitions and rewards and the non-Markovian reward dynamics; 2) sharing the learned environment dynamics among the agents during training. The use of these techniques leads to solution methods that are significantly more sample-eficient than standard modelfree approaches.
More specifically, we consider homogeneous MAS, where the agents act in the same environment but have diferent non-Markovian tasks. In this context, each agent can learn separately the environment dynamics and the reward dynamics and can share the learned model of the environment dynamics with the other agents during training. This approach can greatly reduce the number of samples needed to perform the individual tasks, thus leading to a significant increase in the eficiency of the overall multi-agent learning process. We demonstrate the applicability and the scalability of the approach with an experimental analysis over the Multi-Agent Pickup and Delivery (MAPD) d7o]m, ashinow[ ing the ability of the approach to deal with novel variants of the problem.
Related Work. Recent active research lines concern model-based RL and RL with NGMaRosn.
and Brafman[
A Markov Decision Process (MDP) is a tupleℳ = (, , , ), with: the finite set of states, the ifnite set of actions, ∶ × → () probability distributi(o n′
|, ) an MDP ℳ is a function ∶ →
the transition function returning , ∈for and ∈ , a . The return () of a policy from is () = [ over , and ∶ × × → ℝ the reward function. pAolicy for ∞
∑=0 ],
with = ( , ( ), +1 ), 0 = , anddiscount factor ∈ [
is the return obtained by executining , then acting optimally. Given , an optimal policy i s∗() = argmax (, )
. In RL, , , and are unknown. The main solution
approaches aremodel-free and model-based, with representative algorithQm-lsearning [
A Non-Markovian Reward Decision Process (NMRDP) is a tupl e = (ℳ, ∶ + → ℝ theNon-Markovian Reward (NMR) function, returning rewards basedℳonhistories. Several models for exist, e.g., Reward Machines (RM4)][ or Restraining Bolt1s5[]. For simplicity we ), withℳ an MDP and assume based on aDeterministic Finite-state Automaton (DFA) = (, , alphabet , the finite set of states,0 ∈ the initial stat∶e, × → ⊆ the set of final state s; returns rewar d (, ,
0, , ) , with the input the transition function, and ′) based on last ’s transition(, , ′). We adopt this form for presentation convenience only; experiments are carried out using RMs.
In an NMRDP = (ℳ, ) withℳ = (, , ,
), rewards are based on trajectories. The reward
on trajector y0 0 ⋯ ′ ∈ ( × × ) + is (, , ′) + (, ′, ′), with the state reached by on
history 0 ⋯ and ′ on 0 ⋯ ′. This yields a diferent RL problem, for which direct use of existing
approaches is inadequate. RL with NMRs can be reduced to the Markovian case, by accessing the state
of the NMR’s DFA, which thus becomes a component oℳf’s state. This is detailed i3n],[which shows
that an NMRD P= (ℳ, ) is equivalent to an MDℳP′ = ( ′, , ′, ′) modeling the synchronous
execution ofℳ and , with ′ = × , ′ capturing joint transitionℳsofand , and ′ ∶ ′ × × ′
a Markovian reward function. While this reduction makes standard RL solution methods suitable for
non-Markovian settings (e.g4., [
This work addresses this problem in a Multi-Agent System (MAS) setting. We extend MDPs to MAS usingMarkov Games consisting of: a set of agenΛts= { 1, … , }, oneaction set for each agent 1, … , , state transitions controlled by joint actio n∶s, i×.e ., 1 × ⋯ × → () , and agents’ individual reward function s ∶ × 1 ×⋯× → ℝ. We denote agen t ’s joint action a(s , −̄ ), with the action performed by and −̄ those of all other agents. Agents have diferent goals associated to diferent DFAs. = (, , ,0 , , ) denotes the DFA modelin g ’s goal, wit h ,0 ∈ , ∶ × → , and ⊆ . Every agent having its own goal, individual DFA’s transitions depend only on the environment state and not on other DFAs.
The dynamics of an NMRDP = (ℳ, ) is as follows: 1. on reset, the environment is0inand performs a dummy transition0 → 0 (consuming 0); 2. at each step, on stat(,e) and action , ℳ progresses t o′ with probabilit(y, ) , progresses t o ′ = (, ′) with probability 1, and the returned reward is(, , ′) + (, ′, ′). The resulting transition function is captured by the distribution( ′, ′|, , ) = ( ′| ′, , , ) ( ′|, , ) , with( ′, ′|, , ) , ( ′| ′, , , ) , ( ′|, , ) the transition probability distributions, of, andℳ, respectively. Sincℳe’s transitions are Markovian, ( ′|, , ) = ( ′|, ) , i.e., given and , ′ is independent of the history that letdo . Also, ′ depending only o n and ′, ( ′| ′, , , ) = ( ′| ′, ) . Thus, ’s transition model can be rewritten as (♢)( ′, ′|, , ) = ( ′|, )( ′| ′, ) , and the reward function(a♡s)(, , , ′, ′) = (, , ′) + (, ′, ′). Note that (, ′, ′) is independent o,f , i.e., of how ( ′, ′) is reached from previous state (, ) . Equations ♢() and (♡) factorize the system dynamics decoupling the Markovian environment dynamics (( ′|, ) , (, , ′)) from the non-Markovian reward expressed by the D(FA ′(| ′, ) , (, ′, ′)).
Discrete model-based RL can be applied in the joint state×spacteo( ′, ′|, , ) and(, , , ′, ′).
An algorithm for this Ris-max [
Here, we focus on homogeneous collaborative MASs where the agents share the same environment transition and reward functions. Given the set of aΛge=nt{s 1, … , }, for every , , we have ( ′|, , −̄ ) = ( ′|, , −̄ ) and (, , −̄ , ′) = (, , −̄ , ′). Agent-independence is denoted by ( ′|, ∗, −̄∗) and (, ∗, −̄∗, ′). On the other hand, agents have diferent tasks, modeled by individual DFAs . As a result, for ever y , the NMRDP can be factorized b(y♣)( ′, ′|, , , −̄ ) = ( ′|, ∗, −̄∗)( ′| ′, ) and(♠)(, , , −̄ , ′, ′) = (, ∗, −̄∗, ′) + ( , ′, ′).
The multi-agent state sp acaend the joint action spa ce1 × ⋯ × significantly impact performance and scalability. When combined with NMRDPs, state representation is further expanded with the states of the DFAs modeling the tasks. To eficiently tackle this problem, we consider independent DFAs allowing for extending the state of each a gewnitth ′ = × . In his way, the factorization defined by Equations(♣) and(♠) together with the independe n(ce′|, ∗, −̄∗) and (, ∗, −̄∗, ′) provide for a significantly higher sample eficiency.
Using the above mentioned formulation, it is possible to devise algorithms for sample-eficient MARL in NMRDP. More specifically, the algorithm will implement and exploit the above mentioned techniques: 1) separate learning of the Markovian environment dynamics and the non-Markovian reward dynamics; 2) sharing of the environment dynamics among the agents during training.
In this short paper, we do not describe the details of any algorithm, since the main goal is to focus on the basic techniques described above. However, we provide in the next section some preliminary results when using a simple approach based on incremental individual training, in which each algeeanrtns the environment dynami c(s ′|, ∗, −̄∗) and (, ∗, −̄∗, ′) and the reward dynamic(s ′| ′, ) and ( , ′, ′) to accomplish its task and shares the agent-independent learned environment dynamics with the other agents. The naMmeAQR-max is used in the next section to refer to such a solution.
This approach improves sample eficiency, as the environment transitions and automaton transitions are learned separately and, once the environment model is stable, there is no need to keep learning them. When dealing with diferent (and even more complex) tasks in the same environment expressed by diferent automata, it is suficient to update the non-Markovian model, leveraging the previously learned environment estimates. In this way, the agents easily scale to more complex tasks reusing the learning environment models.
Multi-Agent Pickup and Delivery (MAPD) [
Here, we adopt an RL-based approach, modeling MAPD as a deterministic discrete NMRDP where each agent has its own non-Markovian reward, modeled as a RM, defining the agent’s goals and their fulfillment order; these goals require an agent to reach first the pickup and then the delivery location. Each agent learns its own policy usiMnAgQR-max.
In the NMRPD model, an agent’s state includes its current location, the current timestep, and the progress, tracked by the RM, in fulfilling the assigned tasks. Such compound st(a, t)e∈i s× , with = (, , ) the agent’s position on the gr,id (a vertex in grap h) at timestepand the state of the agent’s RM, tracking the progress towards its tasks. RM transitions between states depend on the occurrence ofpickup, delivery, andcollision events. A pickup event occurs (instantaneously) when the agent reaches the pickup location; delivery events occur similarly, but only if the pickup event has occured already. Collision events occur if two agents are in a same p o, sitiaotnsame timestep. The RM rewards the transitions firing on pickup and delivery events, while penalizes those occurring on collisions. More precisely, the RM capturing an agents’ non-Markovian goal is s.t., o,naevent transitio(n, ) → ( ′, ) takes place fro m to ′ returning a reward va lu.e (a) MAPD 13 × 13.
(b) MAPD 8 × 8.
(c) Priority legend.
The MAPD environments we use consist of grids with walls and narrow corridors, which challenge the agents’ coordination ability. As discussed, the agent’s observation space includes its current position, the timestep, and RM state. The action space comprises the four cardinal directions, thus having size 4 (note that we do not consider wait actions). Pickup and delivery actions are implicitly assumed to be automatically and instantaneously executed when the pickup and delivery locations are achieved. Executing actions that would make an agent hit an obstacle or a boundary yields no efect. In order to penalize adjacent agents when swapping positions simultaneously, each agent’s trajectory is augmented with an additional timestep for every recorded position (details omitted for space reasons).
Agents are trained incrementally, one after another, taking into account, in the reward signal, the potential occurrence of collisions stemming from the learnt policies of agents trained at previous iterations. Agents are assigned a priority corresponding to the training order: an agent receives a penalty whenever, at training time, occupies the same position as that another agent with higher priority would occupy, at the same timestep, when executing its learned policy.
We have used two distinct environments,8a×n8 and a13 × 13 map (see Figs. 1a and1b), and tasks, modeled as RMs and assigned before training. In both environments, priorities decrease from 1 to 5. Agents are assigned priorities and tasks as illustrated1ci,nwFhige.re the first and second cells reported in column “Pickup & Delivery” are the pickup and delivery locations, respectively. Observe how this approach allows for flexibly defining complex MAPD tasks. For instance, one could conveniently define a problem where the agents must perform multiple pickups and deliveries under order constraints on their visits.
In this section, we report the results of some preliminary experiments aiming at discussing potential benefits of algorithms exploiting Model-Based Multi-Agent RL techniques described before.
We carried out tests to evaluate sample eficiency and environment exploration rate, using a CPU i7-11800H 2.30GHz and 16 GB of RAM. Actions have0.6 success (move to intended cell) an0d.4 failure (remain still) probability. The threshold for a(,p)airto beknown is 100. Every 50 episodes, the current optimal policy is evaluated over 100 executions.
Fig. 2 shows the performance oMfAQR-max on the 8×8 MAPD domain (Fig.1b) with 4 agents, in the basic scenario where agents share no information (transition probabilities) about the environment. Fig. 3 illustrates the results for the same scenario, when agents benefit from the transition probability function learned by previous agents. A significant improvement in sample eficiency is obtained, in particular, by Agents 3 and 4, which show a clear decrease in convergence time and an increase in solution quality (timesteps taken to complete the task).
Fig.4 shows results for the same experiment, now with Agent 1 inheriting Agent 4’s learned transitions (70.33%). Agents 1 and 2 converge more rapidly, demonstrating scalability. The increasing fraction of known transitions after each training phase further underscores the importance of knowledge transfer.
We have also tested the approach on a×1133scenario (Figs.5 and6), to preliminarily test scalability. A behavior similar to that of th×e8 8scenario is observed, with the agents achieving a smaller makespan and requiring fewer episodes to learn the optimal policy than in the case without transfer learning. These results demonstrate the feasibility of our approach. Future refinements may further improve performance and scalability.
We have presented a formalization of Multi-Agent Model-Based Reinforcement Learning for NMRDPs that, by decoupling the Markovian transitions in the environment from the non-Markovian evolution of the reward and by sharing the learned environment model among the agents during training, allows the definition of sample-eficient RL algorithms for solving complex multi-agent problems. The general applicability of the proposed solution has been demonstrated by successfully addressing the Multi-Agent Pickup and Delivery problem. A more detailed investigation of algorithms exploiting these properties is left as future work. Work partly supported by the PNRR MUR project PE0000013-FAIR and the Sapienza project MARLeN (Multi-layer Abstraction for Reinforcement Learning with Non-Markovian Rewards).
The authors have not employed any Generative AI tools.