1 Introduction
Using reinforcement learning agents in multi-agent systems (MAS) is often considered impractical due to an exponential increase in the state space with each additional agent. Whilst assuming other agents’ actions to be part of the environment can save from having to calculate the value of all joint-policies, the time taken to learn a suitable policy can become impractical as the environment now appears stochastic.
One method, explored extensively in the single-agent literature, to reduce the time to convergence is reward shaping. Reward shaping is the process of providing prior knowledge to an agent through additional rewards. These rewards help direct an agent’s exploration, minimising the number of sub-optimal steps it takes and so directing it towards the optimal policy quicker.
Recent work has justified the use of these methods in multi-agent reinforcement learning (MARL) and so now our interest shifts towards how to encode knowledge commonly available. Previous research, again from the single-agent literature, translated knowledge encoded as STRIPS operators into a potential function for reward shaping (Grześ & Kudenko, Reference Grześ and Kudenko2008b). In this paper, we will discuss our attempts to use this approach in MAS with either coordinated plans made together or greedy plans made individually. Both are beneficial to agents but the former more so. However, planning together will not always be possible in practice and, therefore, we also present a subsequent investigation into how to overcome conflicted knowledge in individual plans.
The next section begins by introducing the relevant background material and existing work in MARL, reward shaping and planning. Section 3 goes on then to describe our novel combination of these tools. The bulk of experimentation and analysis is in Sections 4, 5 and 6. Finally, in the closing section, we conclude with remarks on the outcomes of this study and relevant future directions.
2 Background
In this section, we introduce all relevant existing work upon which this investigation is based.
2.1 Multi-agent reinforcement learning
Reinforcement learning is a paradigm which allows agents to learn by reward and punishment from interactions with the environment (Sutton & Barto, Reference Sutton and Barto1998). The numeric feedback received from the environment is used to improve the agent’s actions. The majority of work in the area of reinforcement learning applies a Markov Decision Process (MDP) as a mathematical model (Puterman, Reference Puterman1994).
An MDP is a tuple 
$$\left\langle {S,\,A,\,T,\,R} \right\rangle $$
, where S is the state space, A the action space, 
$$T(s,\,a,\,s')={\rm Pr}\left( {s'\left| {s,\,a} \right.} \right)$$
the probability that action a in state s will lead to state 
$s'$
, and 
$R(s,\,a,\,s')$
the immediate reward r received when action a taken in state s results in a transition to state 
$s'$
. The problem of solving an MDP is to find a policy (i.e. mapping from states to actions) which maximises the accumulated reward. When the environment dynamics (transition probabilities and reward function) are available, this task can be solved using dynamic programming (Bertsekas, Reference Bertsekas2007).
When the environment dynamics are not available, as with most real problem domains, dynamic programming cannot be used. However, the concept of an iterative approach remains the backbone of the majority of reinforcement learning algorithms. These algorithms apply so called temporal-difference updates to propagate information about values of states, V(s), or state-action pairs, Q(s, a) (Sutton, Reference Sutton1984). These updates are based on the difference of the two temporally different estimates of a particular state or state-action value. The SARSA algorithm is such a method (Sutton & Barto, Reference Sutton and Barto1998). After each real transition, 
$(s,\,a)\to(s',\,r)$
, in the environment, it updates state-action values by the formula:
$$Q(s,\,a)\!\leftarrow Q (s,\,a)\,{\plus}\,\alpha [r\,{\plus}\,\gamma Q(s',\,a')\,{\minus}\,Q(s,\,a)]$$
where α is the rate of learning and γ the discount factor. It modifies the value of taking action a in state s, when after executing this action the environment returned reward r, moved to a new state 
$s'$
, and action 
$a'$
was chosen in state 
$s'$
.
It is important whilst learning in an environment to balance exploration of new state-action pairs with exploitation of those which are already known to receive high rewards. A common method of doing so is ε-greedy. When using this method the agent explores, with probability ε, by choosing a random action or exploits its current knowledge, with probability 1−ε, by choosing the highest value action for the current state (Sutton & Barto, Reference Sutton and Barto1998).
Temporal-difference algorithms, such as SARSA, only update the single latest state-action pair. In environments where rewards are sparse, many episodes may be required for the true value of a policy to propagate sufficiently. To speed up this process, a method known as eligibility traces keeps a record of previous state-action pairs that have occurred and are therefore eligible for update when a reward is received. The eligibility of the latest state-action pair is set to 1 and all other state-action pairs’ eligibility is multiplied by λ (where λ⩽1). When an action is completed all state-action pairs are updated by the temporal difference multiplied by their eligibility and so Q-values propagate quicker (Sutton & Barto, Reference Sutton and Barto1998).
Applications of reinforcement learning to MAS typically take one of two approaches; multiple individual learners or joint-action learners (Claus & Boutilier, Reference Claus and Boutilier1998). The latter is a group of multi-agent specific algorithms designed to consider the existence of other agents. The former is the deployment of multiple agents each using a single-agent reinforcement learning algorithm.
Multiple individual learners assume any other agents to be a part of the environment and so, as the others simultaneously learn, the environment appears to be dynamic as the probability of transition when taking action a in state s changes over time. To overcome the appearance of a dynamic environment, joint-action learners were developed that extend their value function to consider for each state the value of each possible combination of actions by all agents.
Learning by joint action, however, breaks a common fundamental concept of MAS. Specifically, each agent in a MAS is self-motivated and so may not consent to the broadcasting of their action choices as required by joint-action learners. Furthermore, the consideration of the joint action causes an exponential increase in the number of values that must be calculated with each additional agent added to the system. For these reasons, this work will focus on multiple individual learners and not joint-action learners. However, it is expected that the application of these approaches to joint-action learners would have similar benefits.
Typically, reinforcement learning agents, whether alone or sharing an environment, are deployed with no prior knowledge. The assumption is that the developer has no knowledge of how the agent(s) should behave. However, more often than not, this is not the case. As a group, we are interested in knowledge-based reinforcement learning, an area where this assumption is removed and informed agents can benefit from prior knowledge. One common method of imparting knowledge to a reinforcement learning agent is reward shaping, a topic we will discuss in more detail in the next sub-section.
2.2 Multi-agent and plan-based reward shaping
The idea of reward shaping is to provide an additional reward representative of prior knowledge to reduce the number of sub-optimal actions made and so reduce the time needed to learn (Randløv & Alstrom, Reference Randløv and Alstrom1998; Ng et al., Reference Ng, Harada and Russell1999). This concept can be represented by the following formula for the SARSA algorithm:
$$Q(s,\,a)\leftarrow Q(s,\,a)\,{\plus}\,\alpha [r\,{\plus}\,F(s,\,s')\,{\plus}\,\gamma Q(s',\,a')\,{\minus}\,Q(s,\,a)]$$
where 
$F(s,\,s')$
is the general form of any state-based shaping reward.
Even though reward shaping has been powerful in many experiments it quickly became apparent that, when used improperly, it can change the optimal policy (Randløv & Alstrom, Reference Randløv and Alstrom1998). To deal with such problems, potential-based reward shaping (PBRS) was proposed (Ng et al., Reference Ng, Harada and Russell1999) as the difference of some potential function Φ defined over a source state s and a destination state 
$s'$
:
$$F(s,\,s')=\gamma \Phi (s')\,{\minus}\,\Phi (s)$$
where γ must be the same discount factor as used in the agent’s update rule (see Equation (1)).
Ng et al. (Reference Ng, Harada and Russell1999) proved that PBRS, defined according to Equation (3), does not alter the optimal policy of a single agent in both infinite- and finite-state MDPs.
However, in MARL the goal is no longer the single agent’s optimal policy. Instead some compromise must be made and so agents are typically designed instead to learn a Nash equilibrium (Nash, Reference Nash1951; Shoham et al., Reference Shoham, Powers and Grenager2007). For such problem domains, it has been proven that the Nash equilibria of a MAS are not altered by any number of agents receiving additional rewards provided they are of the form given in Equation (3) (Devlin & Kudenko, Reference Devlin and Kudenko2011).
Recent theoretical work has extended both the single-agent guarantee of policy invariance and the multi-agent guarantee of consistent Nash equilibria to cases where the potential function is dynamic (Devlin & Kudenko, Reference De Weerdt, Ter Mors and Witteveen2012).
Reward shaping is typically implemented bespoke for each new environment using domain-specific heuristic knowledge (Randløv & Alstrom, Reference Randløv and Alstrom1998; Babes et al., Reference Babes, de Cote and Littman2008; Devlin et al., Reference Devlin and Kudenko2011) but some attempts have been made to automate (Marthi, Reference Marthi2007; Grześ & Kudenko, Reference Grześ and Kudenko2008a) and semi-automate (Grześ & Kudenko, Reference Grześ and Kudenko2008b) the encoding of knowledge into a reward signal. Automating the process requires no previous knowledge and can be applied generally to any problem domain. The results are typically better than without shaping but less than agents shaped by prior knowledge. Semi-automated methods require prior knowledge to be put in but then automate the transformation of this knowledge into a potential function.
Plan-based reward shaping, an established semi-automated method in single-agent reinforcement learning, uses a STRIPS planner to generate high-level plans. These plans are encoded into a potential function where states later in the plan receive a higher potential than those lower or not in the plan. This potential function is then used by PBRS to encourage the agent to follow the plan without altering the agent’s goal. The process of learning the low-level actions necessary to execute a high-level plan is significantly easier than learning the low-level actions to maximise reward in an unknown environment and so with this knowledge agents tend to learn the optimal policy quicker. Furthermore, as many developers are already familiar with STRIPS planners, the process of implementing PBRS is now more accessible and less domain specific. (Grześ & Kudenko, Reference Grześ and Kudenko2008b).
In this investigation, we explore how multi-agent planning, introduced in the following sub-section, can be combined with this semi-automatic method of reward shaping.
2.3 Multi-agent planning
The generation of multi-agent plans can occur within one centralised agent or spread amongst a number of agents (Rosenschein, Reference Rosenschein1982; Ziparo, Reference Ziparo2005).
The centralised approach benefits from full observation making it able to, where possible, satisfy all agents’ goals without conflict. However, much like joint-action learning, this approach requires sharing of information, such as goals and abilities, that agents in a MAS often will not want to share.
The alternative approach, allowing each agent to make their own plans, will tend to generate conflicting plans. Many methods of coordination have been attempted including, amongst others, social laws (Shoham & Tennenholtz, Reference Shoham and Tennenholtz1995), negotiation (Ziparo, Reference Ziparo2005) and contingency planning (Peot & Smith, Reference Peot and Smith1992) but still this remains an ongoing area of active research (De Weerdt et al., Reference Devlin, Grześ and Kudenko2005).
In the next section, we will discuss how plans generated by both of these methods can be used with plan-based reward shaping to aid multiple individual learners.
3 Multi-agent, plan-based reward shaping
Based on the two opposing methods of multi-agent planning, centralised and decentralised, we propose two methods of extending plan-based reward shaping to MARL.
The first, joint-plan-based reward shaping, employs the concept of centralised planning and so generates where possible plans without conflict. This shaping is expected to outperform the alternative but may not be possible in competitive environments where agents are unwilling to cooperate.
Alternatively, individual-plan-based reward shaping, requires no cooperation as each agent plans as if it is alone in the environment.
Unfortunately, the application of individual-plan-based reward shaping to multi-agent problem domains is not as simple in practice as it may seem. The knowledge given by multiple individual plans will often be conflicted and agents may need to deviate significantly from this prior knowledge when acting in their common environment. Our aim is to allow them to do so. Reward shaping only encourages a path of exploration, it does not enforce a joint-policy. Therefore, it may be possible that reinforcement learning agents, given conflicted plans initially, can learn to overcome their conflicts and eventually follow coordinated policies.
For both methods, the STRIPS plan of each agent is translated into a list of states so that, whilst acting, an agent’s current state can be compared with all plan steps. The potential of the agent’s current state then becomes:
$$\Phi (s)=\omega \,{\times}CurrentStepInPlan$$
where ω is a scaling factor and CurrentStepInPlan the corresponding state in the state-based representation of the agent’s plan (e.g. see Listing 5).
If the current state is not in the state-based representation of the agent’s plan, then the potential used is that of the last state experienced that was in the plan. This was implemented in the original work to not discourage exploration off of the plan and is now more relevant as we know that, in the case of individual plans, strict adherence to the plan by every agent will not be possible. This feature of the potential function makes plan-based reward shaping an instance of dynamic PBRS (Devlin & Kudenko, Reference De Weerdt, Ter Mors and Witteveen2012).
Finally, to preserve the theoretical guarantees of PBRS in episodic problem domains, the potential of all goal/final states is set to 0. These potentials are then used as in Equation (3) to calculate the additional reward given to the agent.
In the next section, we will introduce a problem domain and the specific implementations of both our proposed methods in that domain.
4 Initial study
Our chosen problem for this study is a flag-collecting task in a discrete, grid-world domain with two agents attempting to collect six flags spread across seven rooms. An overview of this world is illustrated in Figure 1 with the goal location labelled as such, each agent’s starting location labelled Si where i is their unique id and the remaining labelled grid locations being flags and their unique id.
Multi-agent, flag-collecting problem domain
At each time step, an agent can move up, down, left or right and will deterministically complete their move provided they do not collide with a wall or the other agent. Once an agent reaches the goal state their episode is over regardless of the number of flags collected. The entire episode is completed when both agents reach the goal state. At this time both agents receive a reward equal to one hundred times the number of flags they have collected in combination. No other rewards are given at any other time. To encourage the agents to learn short paths, the discount factor γ is set to <1Footnote 1.
Additionally, as each agent can only perceive its own location and the flags it has already picked up, the problem is a decentralised partially observable Markov Decision Process (DEC-POMDP).
Given this domain, the plans of agent 1 and agent 2 with joint-plan-based reward shaping are documented in Listings 1 and 2. It is important to note that these plans are coordinated with no conflicting actions.
Alternatively, Listings 3 and 4 document the plans used to shape agent 1 and agent 2, respectively, when receiving individual-plan-based reward shaping. However, now both plans cannot be completed as each intends to collect all flags. How, or if, the agents can learn to overcome this conflicting knowledge is the focus of this investigation.
As mentioned in Section 3, these plans must be translated into state-based knowledge. Listing 5 shows this transformation for the joint-plan starting in hallA (listed in Listing 1) and the corresponding value of ω.
In all our experiments, regardless of knowledge used, we have set the scaling factor ω so that the maximum potential of a state is the maximum reward of the environment. As the scaling factor affects how likely the agent is to follow the heuristic knowledge (Grześ, Reference Grześ2010), maintaining a constant maximum across all heuristics compared ensures a fair comparison. For environments with an unknown maximum reward the scaling factor ω can be set experimentally or based on the designer’s confidence in the heuristic.
For comparison, we have implemented a team of agents with no prior knowledge/shaping and a team with the domain-specific knowledge that collecting flags is beneficial. These flag-based agents value a state’s potential equal to one hundred times the number of flags it alone has collected. This again ensures that the maximum potential of any state is equal to the maximum reward of the environment.
We have also considered the combination of this flag-based heuristic with the general methods of joint-plan-based and individual-plan-based shaping. These combined agents value the potential of a state to be
$$\eqalignno{ \Phi (s)=\; & (CurrentStepInPlan\,{\plus}\,NumFlagsCollected){\times}\omega \cr \omega = \;& MaxReward/(NumStepsInPlan \cr \,{\plus}\,NumFlagsInWorld) $$
where NumFlagsCollected is the number of flags the agent has collected itself, NumStepsInPlan the number of steps in its state-based plan and NumFlagsInWorld the total number of flags in the world (i.e. for this domain 6).
All agents, regardless of shaping, implemented SARSA with ε-greedy action selection and eligibility traces. For all experiments, the agents’ parameters were set such that α=0.1, γ=0.99, ε=0.1 and λ=0.4. For these experiments, all initial Q-values were 0.
These methods, however, do not require the use of SARSA, ε-greedy action selection or eligibility traces. PBRS has previously been proven with Q-learning and RMax and any action selection method that chooses actions based on relative difference and not absolute magnitude (Asmuth et al., Reference Asmuth, Littman and Zinkov2008). From our own experience, it also works with many multi-agent specific algorithms (including both temporal difference and policy iteration algorithms). Furthermore, it has been shown before without (but never before to our knowledge with) eligibility traces (Ng et al., Reference Ng, Harada and Russell1999; Asmuth et al., Reference Asmuth, Littman and Zinkov2008; Devlin et al., Reference Devlin and Kudenko2011).
All experiments have been repeated 30 times with the mean discounted reward per episode presented in the following graphs. All claims of significant differences are supported by two-tailed, two sample t-tests with significance p<0.05 (unless stated otherwise).
4.1 Results and conclusions
Figure 2 shows all agents, regardless of shaping, learn quickly within the first 300 episodes. In all cases, some knowledge significantly improves the final performance of the agents as shown by all shaped agents outperforming the base agent with no reward shaping.
Initial results
Agents shaped by knowledge of the optimal joint-plan (both alone or combined with the flag-based heuristic) significantly outperform all other agents, consistently learning to collect all six flagsFootnote 2. Figure 3(a) illustrates the typical behaviour learnt by these agents. Note that in these examples the agents have learnt the low-level implementation of the high-level plan provided.
Example behaviour of (a) joint-plan-based agents and (b) individual-plan-based agents
The individual-plan-based agents are unable to reach the same performance as they are given no explicit knowledge of how to coordinate.
Figure 3(b) illustrates the typical behaviour learnt by these agents. This time we note that agent 1 has opted out of receiving its shaping reward by moving directly to the goal and not following its given plan. The resultant behaviour allows the agents to receive the maximum goal reward from collecting all flags, but at a longer time delay and, therefore, a significantly greater discount.
Occasionally, the agents coordinate better with agent 1 collecting flag D or, even rarer, flags D and A. Whilst this is the exception, it is interesting to note that the agent not following its plan will always choose actions that take away from the end of the other agent’s plan rather than follow the first steps of their own plan.
The flag-based heuristic can be seen to improve coordination slightly in the agents receiving combined shaping from both types of knowledge, but not sufficiently to overcome the conflicts in the two individual plans.
To conclude, some knowledge, regardless of the number of conflicts, is better than no knowledge but coordinated knowledge is more beneficial if available.
Given these initial results, our aim in the following experiments was to try to close the difference in final performance between individual-plan-based agents and joint-plan-based agents by overcoming the conflicted knowledge.
5 Overcoming conflicted knowledge
In this section, we explore options for closing the difference in final performance caused by conflicted knowledge in the individual plans.
One plausible option would be to introduce communication between the agents. Another may be to combine individual-plan-based reward shaping with future coordinating Q-learning (FCQ) (De Hauwere et al., Reference De Hauwere, Vrancx and Nowé2011) to switch to a joint-action representation in states where coordination is required. However, as both multiple individual learners and individual-plan-based reward shaping were designed to avoid sharing information amongst agents, we have not explored these options.
Without sharing information, agent 1 could be encouraged not to opt out of following its plan by switching to a competitive reward function. However, as illustrate by Figure 4, although this closed the gap between individual-plan-based and joint-plan-based agents, the change was detrimental to the team performance of all agents regardless of shaping.
Competitive reward
Specifically, individual-plan-based agent 1 did, as expected, start to participate and collect some flags but collectively they would not collect all flags. Both agents would follow their plans to the first two or three flags but then head to the goal as the next flag would not reliably be there. For similar reasons joint-plan-based agents would also no longer collect all flags. Therefore, the reduction in the gap between individual-plan-based and joint-plan-based agents was at the cost of no longer finding all flags. We considered this an undesirable compromise and so will not cover this approach further.
Instead, in the following sub-sections, we will discuss two approaches that lessened the gap by improving the performance of the individual-plan-based agents.
The first of these approaches is increasing exploration in the hope that the agents will experience and learn from policies that coordinate better than those encouraged by their individual plans. The second approach was to improve the individual plans by reducing the number of conflicts or increasing the time until conflict.
Both methods enjoy some success and provide useful insight in to how future solutions may overcome incorrect or conflicted knowledge. Where successful, these approaches provide solutions where multiple agents can be deployed without sharing their goals, broadcasting their actions or communicating to coordinate.
5.1 Increasing exploration
Setting all initial Q-values to 0, as was mentioned in Section 4, is a pessimistic initialisation given that no negative rewards are received in this problem domain. Agents given pessimistic initial beliefs tend to explore less as any positive reward, however small, once received specifies the greedy policy and other policies will only be followed if randomly selected by the exploration steps (Sutton & Barto, Reference Sutton and Barto1998).
With reward shaping and pessimistic initialisation an agent becomes more sensitive to the quality of knowledge they are shaped by. If encouraged to follow the optimal policy they can quickly learn to do so, as is the case in the initial study with the joint-plan-based agents. However, if encouraged to follow incorrect knowledge, such as the conflicted plans of the individual-plan-based agent, they may converge to a sub-optimal policy.
The opposing possibility is to instead initialise optimistically by setting all Q-values to start at the maximum possible reward. In this approach agents explore more as any action gaining less than the maximum reward becomes valued less than actions yet to be tried (Sutton & Barto, Reference Sutton and Barto1998).
In Figure 5, we show the outcome of optimistically initialising the agents with Q-values of 600, the maximum reward agents can receive in this problem domain.
Optimistic initialisation
As would be expected, increased exploration causes the agents to take longer to learn a suitable policy. However, all agents (except for those receiving flag-based or combined-flag+joint-plan shaping) learn significantly better policies than their pessimistic equivalentsFootnote 3. This reduces the gap in final performance between all agents and the joint-plan-based agents, however, the difference that remains is still significant.
Despite that, the typical behaviour learnt by optimistic individual-plan-based agents is the same as the behaviour illustrated in Figure 3(a). However, it occurs less often in these agents than it occurred in the pessimistic joint-plan-based agents. This illustrates that conflicts can be overcome by optimistic initialisation but it cannot be guaranteed, by this method alone, that the optimal joint-plan will be learnt.
Furthermore, it takes time for the individual-plan-based agents to learn how to overcome the conflicts in their plans. However, this time is still less than it takes the agents with no prior knowledge to learn. Therefore, given optimistic initialisation, the benefit of reward shaping is now more important in the time to convergence instead of the final performance.
To conclude, these experiments demonstrate that some conflicted knowledge can be overcome given sufficient exploration.
5.2 Improving knowledge
An alternative approach to overcoming conflicted knowledge would be to improve the knowledge. The individual-plan-based agents received shaping based on plans to both collect all six flags. If these plans are followed the agents will collide at their second planned flag to collect. The agent that does not pick up the flag will no longer be able to follow their plan and will therefore receive no further shaping rewards. Instead, we now consider three groups of agents that are shaped by less-conflicted plans.
Specifically, plan-based six agents still both plan to collect all six flags, but the initial conflict is delayed until the second or third flag. The comparison of these agents to the individual-plan-based agents will show whether the timing of the conflict affects performance.
Plan-based-five agents plan to collect just five flags each, reducing the number of conflicted flags to four. Comparing this with both previous agents and subsequent agents will show whether the number of conflicts affects performance. These agents also experience their first conflict on the second or third flag.
Plan-based-four agents plan to collect four flags each, reducing the number of conflicted flags to two and delaying the first conflict until the third flag. This agent will contribute to conclusions both on timing of conflicts and amount of.
As can be seen in Figure 6, both the timing of the conflict and the amount of conflict affect the agents’ time to convergence. Little difference in final performance is evident in these results as the agents are still benefiting from optimistic initialisation. Alternatively, if we return to pessimistic initialisation as illustrated by Figure 7, reducing the amount of incorrect knowledge can also affect the final performance of the agents.
Optimistic partial plans
Pessimistic partial plans
However, to make plans with only partial overlaps, agents require some coordination or joint-knowledge that would not typically be available to multiple individual learners. If the process of improving knowledge could be automated, for instance with an agent starting an episode shaped by its individual plan and then refining the plan as it notices conflicts (i.e. plan steps that never occur), the agent may benefit from the improved knowledge without the need for joint-knowledge or coordination.
6 Scaling up
To further test multi-agent, plan-based reward shaping and our two approaches to handling incorrect knowledge, we extended the problem domain by adding six extra flagsFootnote 4 (as illustrated in Figure 8(a)) and then adding a third agent (as illustrated in Figure 8(b).)
Scaled up problem domains: (a) extra flags and (b) extra agent
6.1 Extra flags
As shown in Figures 9 and 10, the results for pessimistic initialisation with 12 flags and two agents were effectively the same as those in the original domain except for a slightly longer time to convergence as would be expected due to the larger state space.
Pessimistic initialisation in the scaled up problem domain
Pessimistic partial plans in the scaled up problem domain
The results for optimistic initialisation, however, took significantly longer. Figure 11 illustrates the results of just one complete run for this setting as performing any repeats would be impractical.
Optimistic initialisation in the scaled up problem domain
Whilst these results may be obtained quicker using function approximation or existing methods of improving optimistic exploration (Grześ & Kudenko, Reference Grześ and Kudenko2009), they highlight the poor ability of optimistic initialisation to scale to large domains. Therefore, these experiments further support that automating the reduction of incorrect knowledge by an explicit belief revision mechanism would be more preferable than increasing exploration by optimistic initialisation as the latter method does not direct exploration sufficiently. Instead optimistic initialisation encourages exploration to all states randomly taking considerable time to complete. A gradual refining of the plan used to shape an agent would encourage initially a conflicted joint-policy, which is still better than no prior knowledge, and then on each update exploration would be directed towards a more coordinated joint-plan.
6.2 Extra agent
Finally, Figure 12 shows the results for pessimistic initialisation for the scaled up setting with 12 flags and three agents illustrated in Figure 8(b). Under these settings, the performance of all agents is more variable due to the extra uncertainty the additional agent causes. This is to be expected as the underlying state-action space has grown exponentially whilst, as each agent only considers its own location and collection of flags, the state space learnt by each agent has not grown. For similar reasons, the agents without shaping or shaped by any potential function that includes the flag heuristic perform significantly worse now than when there were only two agents acting and learning in the environment.
Pessimistic initialisation in the scaled up problem domain with three agents
Alternatively, the agents shaped by individual plans or joint-plans alone have remained robust to the changes and converge on average to policies of equivalent performance to their counterparts with two agents in the environment. This was expected with the joint-plan agents as the plans received take into account the third agent and coordinate task allocation prior to learning.
However, in the case of the individual plans this is more impressive. The typical behaviour we have witnessed these agents learn is a suitable task allocation with each agent collecting some flags. This has occurred because with the third agent starting in the middle less flags are contended. It is quickly learnable that flags A and G belong to agent 1, flags C, E, F and K belong to agent 2 and flags B and H belong to agent 3 with the allocation of collecting the four remaining flags having little impact on overall performance provided they are collected by someone. Whereas before, with two agents, flags B and H in particular were highly contended with both agents having similar path lengths to reach them and needing to deviate significantly from the path they would take if they were not to collect them. Coordinating in this task is exceptionally challenging and a key feature of this environment with only two agents.
7 Closing remarks and future work
In conclusion, we have demonstrated two approaches to using plan-based reward shaping in MARL. Ideally, plans are devised and coordinated centrally so each agent starts with prior knowledge of its own task allocation and the group can quickly converge to an optimal joint-policy.
Where this is not possible, due to agents unwilling to share information, plans made individually can shape the agent. Despite conflicts in the simultaneous execution of these plans, agents receiving individual-plan-based reward shaping outperformed those without any prior knowledge in all experiments.
Overcoming conflicts in the multiple individual plans by reinforcement learning can occur if shaping is combined with domain-specific knowledge (i.e. flag-based reward shaping), the agent is initialised optimistically or the amount of conflicted knowledge is reduced. The first of these approaches requires a bespoke encoding of knowledge for any new problem domain and the second, optimistic initialisation, becomes impractical in larger domains.
Therefore, we are motivated to pursue in ongoing work the approach of automatically improving knowledge by an explicit belief revision mechanism. Where successful, this approach would provide a semi-automatic method of incorporating partial knowledge in reinforcement learning agents that benefit from the correct knowledge provided and can overcome the conflicted knowledge.
