2.1 Reinforcement learning

RL is a method where an agent learns by receiving rewards or punishments through continuous interaction with the environment (Sutton & Barto, Reference Sutton and Barto1998). The agent receives a numeric feedback relative to its actions and in time learns how to optimise its action choices. Typically RL uses a Markov Decision Process (MDP) as a mathematical model (Puterman, Reference Puterman1994).

An MDP is a tuple 〈S, A, T, R〉, where S is the state space, A the action space, T(s, a, s′)=Pr(s′|s, a) 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) that 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 RL 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). 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) → (s′, r), in the environment, it updates state-action values by the formula:

(1) $$Q(s,\,a)\leftarrow Q(s,\,a)\,{\plus}\,\alpha [r\,{\plus}\,\gamma Q(s\prime,\,a \prime)\,{\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 exploration. 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).

Typically, RL agents 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.

2.2 Reward shaping

One common method of imparting knowledge to an RL agent is reward shaping. In this approach, an additional reward representative of prior knowledge is given to the agent 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:

(2) $$Q(s,\,a)\leftarrow Q(s,\,a)\,{\plus}\,\alpha [r\,{\plus}\,F(s,\,s\prime)\,{\plus}\,\gamma Q(s \prime ,\,a \prime)\,{\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 was proposed (Ng et al., Reference Ng, Harada and Russell1999) as the difference of some potential function Φ defined over a source s and a destination state s′:

(3) $$F(s,\,s\prime)\,{=}\,\gamma \Phi (s\prime)\,{\minus}\,\Phi (s)$$

where γ must be the same discount factor as used in the agent’s update rule (see Equation (1)).

Potential-based reward shaping, defined according to Equation (3), has been proven to not alter the optimal policy of a single agent in both infinite- and finite-state MDPs (Ng et al., Reference Ng, Harada and Russell1999).

More recent work on potential-based reward shaping has removed the assumptions of a single agent acting alone and of a s static potential function from the original proof. In multi-agent systems, it has been proven that potential-based reward shaping can change the joint policy learnt but does not change the Nash equilibria of the underlying game (Devlin & Kudenko, Reference Devlin and Kudenko2011). With a dynamic potential function, it has been proven that the existing single and multi-agent guarantees are maintained provided the potential of a state is evaluated at the time the state is entered and used in both the potential calculation on entering and exiting the state (Devlin & Kudenko, Reference Devlin and Kudenko2012).

2.3 Plan-based reward shaping

Reward shaping is typically implemented bespoke for each new environment using domain-specific heuristic knowledge (Randløv & Alstrom, Reference Randløv and Alstrom1998; Devlin et al., Reference Devlin, Grześ 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. 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, generates a potential function from prior knowledge represented as a high-level STRIPS plan. STRIPS is a popular and well-studied formalism used to express automated planning instances. We briefly explain the STRIPS formalism here but refer the reader to Fikes and Nilsson (Reference Fikes and Nilsson1972) for further details on this topic.

The description of a planning problem in STRIPS includes the operators (or actions), the initial state and a goal state. Operators have a set of preconditions which have to be satisfied for the action to be executable, and a set of effects which occur when executing the operator. The start state contains a set of conditions which are initially true, and the goal state consists of conditions which have to be true or false for the state to be classified as a goal state.

The output of the planner is the sequence of actions, that will satisfy the conditions set at the goal state. The STRIPS plan is translated from an action-based, to a state-based representation so that, whilst acting, an agent’s current state can be mapped to a step in the planFootnote ¹ (as illustrated in Figure 1).

Figure 1

Plan-based reward shaping

The potential of the agent’s current state then becomes:

(4) $$\Phi (s)\,{=}\,CurrentStepInPlan\,{\times}\,\omega $$

where CurrentStepInPlan is the corresponding state in the state-based representation of the agent’s plan and ω is a scaling factor.

To not discourage exploration off the plan, 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 feature of the potential function makes plan-based reward shaping an instance of dynamic potential-based reward shaping (Devlin & Kudenko, Reference Devlin and Kudenko2012).

To preserve the theoretical guarantees of potential-based reward shaping, the potential of all terminal states is set to 0.

These potentials are then used as in Equation (3) to calculate the additional reward given to the agent and so encourage it to follow the plan without altering the agent’s original 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 potential-based reward shaping is now more accessible and less domain specific (Grześ & Kudenko, Reference Grześ and Kudenko2008b).

However, this method struggles when the given knowledge is partially erroneous and, in some cases, fails to learn the optimal policy within a practical time limit. Therefore, in this paper, we propose a generic method to revise erroneous knowledge online allowing the agent to still benefit from the knowledge given.

3.1 Assumptions

To implement plan-based reward shaping with knowledge revision we must assume an abstract high-level knowledge represented in STRIPS and a direct translation of the low-level states in the grid to the abstract high-level STRIPS states (as illustrated in Figure 1). For example, in this domain the high-level knowledge includes rooms, connections between rooms within the maze and the rooms which flags should be present in. Whilst the translation of low-level to high-level states allows an agent to lookup which room or hall it is in from the exact location given in its state representation.

The domain is considered to be static, that is, there are no external events not controlled by the agent which can at any point change the environment.

It is also assumed that the agent is running in simulation, as the chosen method of knowledge verification currently requires the ability to move back to a previous state.

We do not assume full observability or knowledge of the transition and reward functions. When the agent chooses to perform an action, the outcome of that action is not known in advance. In addition, we do not assume deterministic transitions, and therefore the agent does not know if performing an action it has previously experienced will result in transitioning to the same state as the previous time that action was selected. This assumption has a direct impact on the way knowledge verification is incorporated into the agent and is discussed later in the paper. Moreover, the reward each action yields at any given state is not given and it is left to the agent to build an estimate of the reward function through continuous interaction with the environment.

Domains limited by only these assumptions represent many domains typically used throughout RL literature. The domain we have chosen allows the agent’s behaviour to be efficiently extracted and analysed, thus providing useful insight, especially when dealing with novel approaches such as these. Plan-based reward shaping is not, however, limited to this environment and could be applied to any problem domain that matches these assumptions.

Future work is aimed towards extending the above assumptions by including different types of domain knowledge and evaluating the methods on physical environments, real-life applications and dynamic environments.

4.1 Identifying incorrect knowledge

At each time step t the agent performs a low-level action a (e.g. move_left) and traverses to a different state s′, which is a different square in the grid. When the agent traverses into a new square it automatically picks up a flag if a flag is present in that state. As the agent is performing low-level actions it can gather information about the environment and in this specific case, information about the flags it was able to pick up. This information allows the agent to discover potential errors in the provided knowledge. Algorithm 1 shows the generic method of identifying incorrect knowledge. We illustrate this algorithm with an instantiation of the plan states to the flags the agent should be collecting, that is predicate taken (flagX) shown in Listing 2. The preconditions are then instantiated to the preconditions which achieve the respective plan state which in this study refers to the presence of flags. The same problem instantiation is also used in the empirical evaluation.

More specifically, at the start of each experiment, the agent uses the provided plan in order to extract a list of all the flags it should be able to pick up. These flags are then assigned a confidence value much like the notion of epistemic entrenchment in belief revision (Gärdenfors, Reference Gärdenfors1992). The confidence value of each flag is set to the ratio successes/failures and is computed at the end of each episode with successes being the number of times the agent managed to find the flag up to the current episode, and failures the times it failed to do so. If the confidence value of a flag drops below a certain threshold, that flag is then marked for verification.

This dynamic approach is used in order to account for the early stages of exploration where the agent has not yet built an estimate of desired states and actions. If a static approach were to be used, which would only depend on the total number of episodes in a given experiment, failures to pick up flags would be ignored until a much later point in the experiment and the agent would not benefit from the revised knowledge at the early stages of exploration. In addition, varying the total number of episodes would have a direct impact on when knowledge verification will take place.

It is worth noting that while there are more types of wrong knowledge that can be provided to an agent, for example incomplete information, wrong plan sequence, etc., these are not within the scope of this report and are a part of future work.

4.2 Knowledge verification

When a flag is marked for verification the agent is informed of which flag has failed at being picked up and the abstract position it should appear in, for example RoomA. The agent is then left to freely interact with the environment as in every other case, but its mode of operation is changed once it enters the abstract position of the failing flag. At that point the agent will perform actions in order to try and verify the existence of the flag which is failing. Algorithm 2 shows the generic method of verifying incorrect knowledge by the use of depth first search (DFS). The algorithm is illustrated by using the same instantiations as those in Algorithm 1.

To verify the existence of the flag the agent performs a DFS of the low-level state space within the bounds of the high-level abstract state of the plan. A node in the graph is a low-level state s and the edges that leave that node are the available actions a the agent can perform at that state. An instance of the search tree is shown in Figure 3 in which the grey nodes (N1−N3) have had all their edges expanded and green nodes (N4−N7) have unexpanded edges (E9−E14).

Figure 3

Instance of the search tree

However, instead of performing DFS in terms of nodes the search is performed on edges. At each time step instead of selecting to expand a state (node), the agent expands one of the actions (edges). The search must be modified in this way because of our assumptions on the environment the agent is acting in. When an agent performs an action a at state s it ends up at a different state s′. The transition probabilities of those actions and states however are not known in advance. As a result the agent cannot choose to transition to a predefined state s′, but can only choose an action a given the current state s. Performing DFS by taking edges into account enables the agent to search efficiently while preserving the theoretical framework of RL.

After expanding an edge/making an action the agent’s coordinates in the grid are stored along with the possible actions it can perform. The graph is expanded with new nodes and edges each time the agent performs an action which results in a transition to coordinates which have not been experienced before. If the agent transitions to coordinates which correspond to an existing node in the graph, it simply selects to expand one of the unexpanded edges, that is perform an action which has not been tried previously.

In order to allow the agent to create an estimate of the provided knowledge, and to discourage knowledge verification and revision to take place instantly, this procedure only takes place after a few hundred episodes have been completed.

If a node has had all of its edges expanded (i.e. all of the available actions at that state have been tried once) the node is marked as fully expanded. However, instead of backtracking as it happens in traditional DFS, the agent jumps to the last node in the graph which has unexpanded edges. This is made possible by the fact that the agent is running in simulation, as mentioned in Section 3.1, and its state can easily be reset. This approach ensures that the assumptions on the domain regarding transition probabilities are not violated as a reverse action does not necessarily exist. A similar jump is performed in the case where expanding a node leads the agent into breaking the search condition, that is, the agent steps out of the room which contains the flag which is failing. It is worth noting that while the agent performs DFS, in order to be fair when comparing with other approaches, expanding an edge or jumping to a different node takes a time step to complete. In the context of this work performing each available action only once is sufficient as we have a deterministic domain. A stochastic domain would require each action to be performed multiple times before marking a node as fully expanded. If the agent was to be acting in a physical environment, the knowledge verification would not be by DFS but by heuristic search relying on the agent’s sensors of the environment, for example search at places not directly visible by the camera.

The search finishes once the agent has either found the failing flag or all of the nodes that were added to the graph have been marked as fully expanded. If found, the confidence value associated with the flag is reset and the agent returns to normal operation. If not, the agent returns to normal operation but the flag is marked for revision.

It is worth noting that the search does not have a cut-off value considering the small size of the grid graph the agent needs to search in. Furthermore, whilst verifying knowledge, no RL updates are made. The reason is for the agent not to get penalised or rewarded by following random paths while searching, which would otherwise have a direct impact on the learnt policy.

4.3 Revising the knowledge

As discussed previously, when an agent fails to verify the existence of a flag, that flag is marked for revision. Belief revision is concerned with revising a knowledge base when new information becomes apparent by maintaining consistency among beliefs (Gärdenfors, Reference Gärdenfors1992). In the simplest case where the belief base is represented by a set of rules there are three different actions to deal with new information and current beliefs in a knowledge base: expansion, revision and contraction. In this specific case, where the errant knowledge the agent has to deal with is based on extra flags which appear in the knowledge base but not in the simulation, revising the knowledge base requires a contractionFootnote ². Furthermore, as the beliefs in the knowledge base are independent of each other, as the existence or absence of a flag does not depend on the existence or absence of other flags, contraction equals deletion. The revised knowledge base is then used to compute a more accurate plan.

To illustrate the use of this method consider a domain similar to that shown in Figure 2 which contains one flag, flagA in roomA. The agent is provided with the plan shown in Listing 3. This plan contains an extra flag which is not present in the simulator, flagC in roomC. According to the plan the agent starts at hallA and has to collect flagA and flagC and reach the goal state in roomD.

Let us assume that the verification threshold for each flag is set at 0.3. At the end of the first episode the confidence value of each flag is computed. If flagA was picked up, its threshold will be equal to 1 which is greater than the verification threshold. As a result this flag will not be marked for verification. However, as flagC does not appear in the simulator its confidence value will be equal to 0, which is less than the verification threshold, and the flag will be marked for verification.

During the next episode when the agent will step into the room where flagC should appear in, that is roomC, it will switch into verification mode. At this point the agent will perform a DFS within the bounds of roomC to try and satisfy flagC. The DFS will reveal that flagC cannot be satisfied and as a result will be marked for revision. When the episode ends the knowledge base will be updated to reflect the revision of flagC and a new plan will then be computed. The new plan is shown in Listing 4.