A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions

Multiobjective reinforcement learning (MORL) aims to extend the capabilities of reinforcement learning (RL) methods to enable them to work for problems with multiple, conflicting objectives Roijers et al. (2013a). RL algorithms generally assume that the environment is a Markov Decision Process (MDP) in which the agent is provided with a scalar reward after each action, and must aim to learn the policy which maximises the long-term return based on those rewards. In contrast MORL algorithms operate within multiobjective MDPs (MOMDPs), in which the reward terms are vectors, with each element in the vector corresponding to a different objective. This creates a number of new issues to be addressed by the MORL agent. Most notably there may be multiple policies which may be optimal (in terms of Pareto optimality), and which policy the agent should learn is not immediately obvious.

In the utility-based paradigm of MORL Roijers et al. (2013a); Zintgraf et al. (2015) it is assumed that the preferences of the user can be defined in terms of a parameterised utility function $f$, and that the aim of the agent should be to learn the policy which produces vector returns which maximises the utility to the user as defined by $f$.

Various approaches have been explored for the form of the utility function – some may be better suited to express the preference of the user within a particular problem domain, while others offer benefits from an algorithmic perspective. A simple weighted linear scalarisation has been widely used because of its simplicity (for example, Barrett and Narayanan (2008); Castelletti et al. (2010); Perez et al. (2009)). Linear scalarisation transforms an MOMDP into an equivalent single-objective MDP, and enables existing RL approaches to be directly applied Roijers et al. (2013a). However for many tasks this may not be able to accurately represent the utility of the user, and so may fail to discover the policy which is optimal with regards to their true utility. As a result numerous non-linear scalarisation functions have been explored in the literature (for example, Gábor et al. (1998); Van Moffaert et al. (2013b, a)) – these tend to produce algorithmic complications, but also may better represent the true preferences of the user.

As well as the choice of scalarisation function and parameters, a second factor must be considered within this utility-based paradigm – the time-frame over which the utility is being maximised. Roijers et al. (2013a) identified two distinct possibilities. The agent may aim to maximise the expected scalarised return (ESR). That is, it is assumed the returns are first scalarised, and then this agent aims for the policy which maximises the expected value of that scalar. This ESR approach is suited to problems where the aim is to maximise the expected outcome within any individual episode. For example, when producing a treatment plan for a patient which trades off the likelihood of a cure versus the extent of negative side-effects - any individual patient will only undergo this treatment once, and so they care about the utility obtained within that specific episode.

In other contexts we may be concerned about the mean utility received over multiple episodes. In this situation the agent should aim to maximise the scalarised expected return (SER) - that is, it estimates the expected vector return per episode, and then maximises the scalarisation of that expected return. As demonstrated in Roijers et al. (2018), the optimal policy for a particular MOMDP under the ESR and SER setting may differ considerably, even if the same scalarisation function and parameters are used in both cases.

As noted by Roijers et al. (2018) and Rădulescu et al. (2019) much of the existing work in MORL has considered SER optimization, although this has often been implicit rather than explicitly stated. Much of this SER-focused work has been based on benchmark environments such as those of Vamplew et al. (2011), the majority of which are deterministic MOMDPs.

In this paper we demonstrate by example that the model-free value-based methods previously widely used in MORL research may fail to maximise the SER utility when applied to MOMDPs with stochastic state transitions.

As shown in Figure 1 the Space Traders MOMDP is a finite-horizon task with a horizon of 2 time-steps. It consists of two non-terminal states, with three actions available in each state. The agent starts at its home planet (state A) and must travel to another planet (state B) to deliver a shipment, and then return to State A with the payment. The agent receives a reward with two elements - the first is 0 on all actions, except that a reward of 1 is received when the agent successfully returns to state A, while the second element is a negative value reflecting the time taken to execute the action.

There are three possible pathways between the two planets. The direct path (actions shown by solid black lines in Figure 1) is fairly short, but there is a risk of the agent being waylaid by space pirates and failing to complete the task. The indirect path (grey lines) avoids the pirates and so always leads to successful completion of the mission, but takes longer. Finally the recently developed teleportation system (dashed lines) allows instantaneous transportation, but has a higher risk of failure. The figure also details the probability of success, and the reward for the mission-success and time objectives for each action – due to variations in local conditions such as solar winds and the location of the space pirates, the time values for the outward and return journeys on a particular path may vary.

Table 1 summarises the transition probabilities and rewards of the MOMDP, and also shows the mean immediate reward for each action from each state, weighted by the probability of success.

As there are three actions from each state there are a total of nine deterministic policies available to the agent. The mean reward per episode for each of these policies is shown in Table 2 and illustrated in Figure 2. The solid points in the figure highlight the policies which belong to the Pareto front, and the dashed grey line indicates the convex hull (only those policies lying on the convex hull can be located via methods using linear scalarisation – this set of policies is referred to as the Convex Coverage Set Roijers et al. (2013b)).

For the remainder of the paper we will assume that the agent’s aim is to minimise the time taken to complete the delivery and return to A, subject to having at least an 88% probability of successful completion. That is, the scalarisation function $f(\@vec{v})=v_{2}$ if $v_{1}>0.88$ and $-\infty$ otherwise. The optimal policy for this aim is to follow the direct path to B and then the indirect path back to A (policy DI).

In this section we will discuss how some of the value-based MORL methods previously used in the literature would perform on the Space Traders MOMDP. All the methods discussed are assumed to be based on a multiobjective extension of model-free value-based RL algorithms such as Q-Learning or SARSA – for example see (Van Moffaert and Nowé, 2014, p. 3668). For the purposes of this section we will restrict discussion to single-policy methods in which the scalarisation function $f$ is used to filter the multiple Pareto-optimal policies which may be available so as to obtain a single policy which is optimal with regards to $f$. Multiple-policy MORL methods will be discussed in Section 5.

All methods learn vector-valued estimated Q-values, but differ in terms of the scalarisation or ordering method used to perform action-selection, and the characteristics on which the Q-value and policy are conditioned.

The failure of the non-linear value-based MORL algorithms on the Space Traders MOMDP can be explained by the analysis of stochastic-transition MOMDPs previously carried out by Bryce et al. (2007) in the context of probabilistic planning. This analysis has been largely overlooked by MORL researchers so far, and so one of the contributions of this paper is to bring this work to the attention of the MORL research community.

Figure 3 illustrates a simple MDP reproduced from Bryce et al. (2007), with a stochastic branch occurring on the transition from the initial state. The table in the lower half of this figure specifies the mean return for the four possible deterministic policies. Keeping in mind that this MOMDP is phrased in terms of minising cost (rather than maximising the inverse of the cost), it can be seen that unlike Space Traders, there are no Pareto-dominated policies for this MOMDP.¹¹1While clearly illustrating the problem, this MOMDP also lacks the narrative drama of Space Traders!.

The aim of the agent is to minimise the cost, subject to satisfying at least a 0.6 probability of success. Within an ESR formulation of the problem (i.e. ensure the probability of success threshold is achieved in each episode), the optimal policy is to select sub-plan $\pi_{1}$ at branch $b_{1}$ and $\pi_{3}$ at branch $b_{2}$ as both of these sub-plans individually satisfy the probability threshold. However if considered from the SER perspective, the optimal plan is to execute $\pi_{2}$ at branch $b_{1}$ and $\pi_{3}$ at branch $b_{2}$ – while $\pi_{2}$ itself fails to achieve the probability threshold, this branch is executed with a low probability and so the mean outcome of the two sub-plans will achieve the threshold while also producing a significant cost saving.

As identified by Bryce et al. (2007), whether the overall policy meets the constraints depends on the probability with which each branch is executed as well as the mean outcome of each branch. Determining the correct sub-plan to follow at each branch requires consideration of the sub-plan options available at each other branch in combination with the probability of branch execution.

This requirement is fundamentally incompatible with the localised decision-making at the heart of model-free value-based RL methods like Q-learning, where it is assumed that the correct choice of action can be determined purely based on information available to the agent at the current state. The provision of additional information such as the sum of rewards received so far in the episode as discussed in Section 3.2 is insufficient, as it still only provides information about the branch which has been followed in this episode, rather than all possible branches which might have been executed.

The conclusion to be drawn from both this example and Space Traders is that value-based model-free MORL methods are inherently limited when applied in the context of SER optimisation of non-linear utility on MOMDPs with non-deterministic state transitions. These methods may fail to discover the policy which maximises the SER (i.e. the mean utility over multiple episodes). To the best of our knowledge this limitation has not previously been identified in the MORL literature. It is particularly important as the combination of SER, stochastic state transitions and non-linear utility may well arise in important areas of application such as AI safety Vamplew et al. (2018b).

In this section we will briefly review and critique various options which may address the issue identified above.

We have described a stochastic MOMDP and utility function which, despite their seeming simplicity, are not amenable to solution by the widely-used model-free value-based approaches to MORL. While this issue with MOMDPs with stochastic state transitions has previously been described in the context of probabilistic planning Bryce et al. (2007), this is the first work to identify the implications for MORL. Our example also demonstrates that under stochastic state-transitions, it is in fact possible for such MORL methods to converge to a Pareto-dominated policy.

The combination of SER optimisation, stochastic state transitions and the need for a deterministic policy are likely to arise in a range of applications (particularly in risk-aware agents), and so awareness of the limitations of some MORL methods to work under these characteristics is important in order to avoid the use of inappropriate methods.