Deceptive Reinforcement Learning for Privacy-Preserving Planning

Deception, psychologists broadly agree, is a pejorative term for the fostering or maintenance of false belief in the minds of others Carson (2010). Computer science has necessarily widened the definition, first, to accommodate mindless machines incapable of belief (as such) and second, to allow for the emerging realisation (particularly from the field of social robotics) that deception is a fundamental aspect of intelligent behaviour, frequently beneficial not only to the deceiver but to the deceived Shim and Arkin (2013); Wagner and Arkin (2011). Whereas deceptive AI has tended to focus on detection Avrahami-Zilberbrand and Kaminka (2014), ethical implications Arkin et al. (2012), and the qualities that make a deceptive act most likely to succeed Ettinger and Jehiel (2010), military strategists Bell and Whaley Whaley (1982); Bell (2003); Bell and Whaley (1982) provide a general theory focused on how to deceive. Their non-judgemental definition is “the distortion of perceived reality” which they maintain can only be achieved in one of two ways: by simulation (“showing the false”) or dissimulation (“hiding the true”). They propose three variations on each method and suggest that a deceptive strategy typically involves combinations of those six tactics in pursuit of some strategic objective.

In planning, deception is frequently associated with security and has become almost synonymous with privacy-protection Chakraborti et al. (2019). Dissimulation in this context becomes the task of obscuring intent by maximising a plan’s ambiguity Kulkarni et al. (2018b); Keren et al. (2016). Obscuring intent assumes an observer engaged in intention recognition; and deceptive planning is commonly (though not exclusively)¹¹1See Kulkarni et al. (2018a) for an argument against. conceived as an inversion of intention recognition Dragan et al. (2014); Keren et al. (2016); Masters and Sardina (2017b).

In this paper, we invert a type of cost-based goal recognition Ramirez and Geffner (2010). To generate a probability distribution over goals, they compare each goal’s cost difference, that is, the difference between the optimal cost of a plan via observed actions and the optimal cost of any alternative plan. The lower the cost difference, the higher the probability. Vered et al. (2016) take a similar approach but instead of cost difference use the ratio between the optimal cost of reaching each goal via the observations and the optimal cost per se. They propose two heuristics to minimise the computational effort in the context of online recognition, one of which suggests pruning a goal from consideration if observations deviate too far from the optimal behaviour. Masters and Sardina (2017b) apply Bell and Whaley’s theory to path-planning. They assume a naïve observer, modelled as a probabilistic intention recognition system. The inputs are observations $\@vec{o}$ and the output is a probability distribution across potential goals $P(G|\@vec{o})$. An action is deceptive if, at that step, the probability of the real goal $g_{r}$ does not dominate the probability of some other goal: $P(g_{r}|\@vec{o})\leq P(g)|\@vec{o})$ for all $g\in G\setminus\{g_{r}\}$. They observe that every path has one last deceptive point ($LDP$), even if it is the starting point, and show that there is a radius around goal within which trying to deceive is no longer valuable, and the agent should head directly to its true goal. At the path level, they define deceptive density as inversely proportional to the number of truthful steps it contains; and deceptive extent by the distance remaining after the last deceptive point has been reached, that is, the optimal cost from $LDP$ to $g_{r}$. Kulkarni et al. (2018b) extend a similar approach to classical task planning, more general than path planning. Both approaches, however, are applicable only to model-based problems, so do not generalise to MDPs.

Ornik and Topcu (2018) present the comprehensive model of planning for deception in MDPs. Their model defines the notion of a belief-induced reward, which is a reward that the agent receives, but that is also affected by the belief of an observer. This includes cases when the observer has only partial visibility of the environment. For example, the reward is received if the observer’s belief is that the agent is not in the state that receives the reward, otherwise it receives some negative reward. Ornik and Topcu then show how to define optimal policies for belief-induced rewards, and present some examples of deceptive belief-induced reward functions. However, their work is model-based, and further, they do not specify a dissimulative policy.

Karabag et al. (2019) present a model-based solution to a different deceptive problem. In their problem, an agent is provided a policy to follow to achieve a goal, specified in linear temporal logic, but can instead follow a different deceptive policy, modelled from an MDP, to achieve the goal. The aim is to try to achieve both policies while minimising the likelihood of the supervisor knowing.

A closely related area of research is differential privacy for reinforcement learning Vietri et al. (2020); Ma et al. (2019); Wang and Hegde (2019). The general approach to this is to modify Q-learning and policy-based reinforcement learning algorithms by e.g. adding Gaussian noise to the update rule Wang and Hegde (2019). While the general idea is similar, there are a few major differences. First, our problem definition is motivated by strategic deception based on theory of deception Whaley (1982); Bell and Whaley (1982), rather than on the idea of privacy per se. This difference manifests itself in the problem definition: we assume that reward functions are fully observable to the observer, but that the observer does not know which reward function the current policy is trained on. The work cited here, on the other hand, assume that there is a single reward function and it is not observable. A privacy-preserving approach like this is not strategic as it does not trade off against different goals. Further, it means that we explicitly measure the simulation of the policy, rather than the privacy of the reward function. While we could frame our problem in a similar way to Wang and Hegde, in strategic deception, it is uncommon for an observer not to have a model of likely goals for an actor. Second, we present a general model for MDPs, whereas Wang and Hegde (2019), Vietri et al. (2020), and Ma et al. (2019) are Q-learning and policy-gradient approaches. Finally, we measure the strategic deception achieve both in computational and human studies.

Some work in deceptive reinforcement learning investigates techniques to counter the deceptive strategies of other agents, such as the agent being fed incorrect reward signals Huang and Zhu (2019), deception in games and multi-agent systems Banerjee and Peng (2003); Li et al. (2020); Sakuma et al. (2008).

Our definition of deceptive reinforcement learning is related to inverse reinforcement learning Ng and Russell (2000) and imitation learning Ziebart et al. (2008). Inverse reinforcement learning is the problem of inferring a reward function given traces of an agent’s behaviour in a variety of circumstances and the sensory input to the agent. Imitation learning Ziebart et al. (2008) is similar to inverse reinforcement learning, but instead of inferring a reward function, the aim is to infer a policy. These methods learn a reward function by observing e.g., a human complete the same task many times. The problem that we define in this paper could be framed as the problem of producing a policy that makes it difficult to perform inverse reinforcement or imitation learning. However, there are two key differences. First, in this paper, we aim to simply deceive for a single trace of behaviour, whereas these inverse learning problems require either a known optimal policy from which to generate traces, or a set of traces of behaviour. Despite this, there is clearly a related problem that is of interest in studying the problem of deception as obfuscating inverse reinforcement learning. Second, we define a set of possible reward functions, whereas inverse reinforcement learning starts with the set of all reward functions. The approach from Wang and Hegde (2019) above proposes a Q-learning-based solution for such a problem.

A Q-function $Q:S\times A\rightarrow\real$ defines the value of selecting an action $a$ from state $s$ and then following the policy $\pi$, written $Q(s,a)$. An optimal policy $\pi$ can then be defined as $\pi(s)=\operatorname*{arg\,max}_{a\in A}Q(s,a)$.

Ornik and Topcu leave the actual instantiation of beliefs abstract, but the concept is that $L(s,a,s,B)$ is a reward that is some function of the belief of an observer and the real reward.

Using a belief-inducted reward, the task of solving an MDP is to synthesise a policy $\pi$ that maximises:

To specify a deceptive reinforcement learning problem, we must instantiate $\mathcal{B}$ and define $L$. In our setting, $\mathcal{B}=\mathcal{R}$, as we aim to deceive about the particular reward function. For $L$, we need to define what is means to deceive about a reward function.

First, we need to define the observer’s task. This is an intention recognition task Baker et al. (2009) in which the observer derives a probability distribution over $\mathcal{R}$ that defines the probability $P(r_{i}\mid\@vec{o_{t}})$ that the reward function $r_{i}$ is the true reward function, given $\@vec{o_{t}}$, the sequence of observed state-action pairs up until time $t$. For example, the probability of the final destination of the each of the three locations outlined in Figure 1. Our deceptive models later present some ways to define this for an MDP.

The challenge of this problem is that it is difficult to model the intention recognition of the observer. For example, is the observer naïve, in that they do not believe that they are being deceived? Or are they aware that they are being deceived? Or somewhere in the middle? If they have some awareness, what model of deception are they using in their own intention recognition model. For this reason, the straightforward model of just solving for Equation 1 is only optimal if our model of intention recognition is the same as the observers, which is unlikely.

In this paper, we present two solutions to this problem that do not have an explicit model of an observer: an ambiguity model and an irrationality model. Instead, the two models use only the information available to them by their given policy. We assume pre-trained Q-functions for all reward functions in $R_{n}$; or alternatively, pre-trained stochastic policies, but we only use Q-functions for the remainder of the paper. We use $Q_{r_{i}}$ to represent one trained on bogus reward function $r_{i}$.

In this model, an agent behaves ambiguously by selecting actions that have high Q-values not only for the real reward function but also for multiple bogus reward functions. As the trajectory progresses, fewer reward functions remain sensible, so these are pruned from consideration. Eventually, the policy selects actions only optimal for the true reward function. The final point before this occurs conforms to Masters and Sardina’s last deceptive point Masters and Sardina (2017b).

The main idea is for our policy to generate sequences of actions that have positive reward for several reward functions, including the true reward function. For this, we need a measure of how far a sequence of observed behaviour diverges from optimal behaviour. Observations $\@vec{o}$ consist of a sequence of tuples $(s,a)$. We measure how far observations diverge from the optimal solution by summing the Q-differences:

This formula is based on the definition by Ramirez and Geffner (2010). If $\@vec{o}$ follows a sequence that is optimal for reward function $r_{i}$, then $\Delta_{r_{i}}(\@vec{o})=0$, and any sub-optimal behaviour has a negative divergence. Other definitions are possible, such as using cost ratio like Vered et al. (2016); what matters is that $\Delta$ allows us to compare behaviour with respect to optimality.

The probability that reward function $r_{i}$ is the true reward function $r$, from the perspective of an observer, is defined using a Boltzmann distribution:

in which $P(r_{i})$ is the prior probability that $r_{i}$ is the true reward function, which can be uniform over $\mathcal{R}$ if this is unknown. If $\@vec{o}$ is far from optimal for $r_{i}$ compared to other reward functions in $\mathcal{R}$, its probability will be lower relative to the other reward functions. This gives us a probability distribution over all reward functions in $\mathcal{R}$. As with $\Delta_{r_{i}}(\@vec{o})$, other models could be used to define this, but we use what is common in intention recognition models.

Our model uses this probability distribution to minimise information gain by the observer using Shannon entropy²²2Shannon entropy measures information gain. Increasing uncertainty lowers information gain and increases entropy. Shannon (1948) each time an action is chosen.

We define the Q-gain of action $a$ for reward function $r_{i}$ as:

in which $R_{r_{i}}(\@vec{o})=Q_{r_{i}}(s^{\prime},a^{\prime})-Q_{r_{i}}(s_{0},a_{0})$ is the residual expected reward received so far in sequence $\@vec{o}$ where $(s^{\prime},a^{\prime})$ is the last pair in $\@vec{o}$ and $(s_{0},a_{0})$ is the first pair in $\@vec{O}$. Thus, $R_{r_{i}}(\@vec{o})$ represents the value of having arrived at state $s$ minus the reward of executing $a$, while $G_{r_{i}}(s,a)$ represents the gain that action $a$ gives compared to ‘remaining’ in state $s$. Intuitively, $G_{r_{i}}(s,a)<0$ implies that action $a$ is moving ‘away’ from the rewards given by $r_{i}$, and $G_{r_{i}}(s,a)>0$ is moving ‘towards’ the rewards.

Given a sequence of observations $\@vec{o}$, our model chooses the action that minimises the information gain for the observer:

in which $A^{+}(s)$ is the set of actions with non-negative Q-gain for the real reward function $r$, and $\kappa$ is a normalising term. Thus, an agent following policy $\pi^{D}$ will move ambiguously between all of the Q-functions to maximise entropy. Only evaluating actions in $A^{+}(s)$ ensure that progress is made towards the real goal.

However, sometimes a particular reward can become so irrational that it would be clear to an observer that this is no longer likely. We exclude such reward functions from the entropy calculation by re-evaluating the bogus reward functions at each step of the plan, and excluding those would be irrational (negative Q-gain). This is similar to the pruning heuristic from Vered and Kaminka (2017).

A reward function is pruned from the entropy calculation (set $\mathcal{R}$ in Equation 5) if $G_{r_{i}}(s,a)<\delta$, in which $\delta$ is a pruning parameter. If $\delta=0$, a reward function is pruned because it offers no gain over the current state. If $\delta<0$, the pruning would be less aggressive, allowing some actions that offer no gain. If $\delta={-}\infty$, nothing would be pruned. At each step, all reward functions are considered for all actions, so a pruned reward function can be re-considered later. This may have the negative effect that all but the true one are pruned. In implementation, a minimum number of policies can be specified.

Figure 2 illustrates a path planning problem in which the agent must navigate from the green start point to the orange destination. The bogus destinations are red. In Figure 2(a), the agent minimises information gain for all goals without pruning. It is difficult to see, but the thicker line in Figure 2(a) compared to Figure 2(b) is the agent zigzagging repeatedly left-to-right. In Figure 2(b) with pruning, at the first turn, labelled (a), the destination at the top left is pruned, while at turn (b), the destination on the right is pruned, and turn (c) prunes the destination at the bottom left. This delivers a shorter path than in Figure 2(a) because it avoids zigzagging behaviour from trying to maximise the entropy of all destinations.

The irrationality model is based on Masters and Sardina (2019). The deceptive Q-value of an action is a weighted sum of its optimal Q-value and a irrationality measure. The higher the weight on the optimal Q-value, the less deceptive the behaviour.

First, we define the irrationality measure for an observation sequence, which is dependent on the history of a sequence of actions, rather than a single action. This is because an action may appear rational in a one state, but not in the context of a longer sequence.

Under this definition, a sequence $\@vec{o}$ that has a low value for all reward functions has a high $IM$ — it is irrational not to make progress towards at least one goal. We take the minimum of all reward functions: if the sequence is rational for any of the possible reward functions, then it is deemed rational by an observer who does not know the true reward function.

The goal of the agent is to maximise its expected reward as well as its irrationality. We use a parameter $\alpha$ $(0\leq\alpha\leq 1)$ as the weight to define the importance of the Q-value versus the irrationality. The deceptive policy $\pi^{D}$ is defined as the weighed sum of the optimal Q-value and the irrationality measure:

in which $Q^{\prime}_{r}(s,a)$ is $Q_{r}(s,a)$ normalised against other actions $a^{\prime}\in A$ to range [0,1]. The higher $\alpha$, the lower the weight given to the Q-value and the more irrational the behaviour.

Figure 3 illustrates the irrationality model in a path planning setting. When $\alpha=0$, we get honest behaviour. As $\alpha$ increases, rationality decreases. For $\alpha=0.15$ and $0.3$, the agent moves away from both destinations. For $\alpha=0.3$, the blue block in the bottom corner reflects the agent’s excessive irrationality. As the agent moves towards its true destination, its behaviour becomes more rational, capturing a similar idea to the last deception point in Masters and Sardina (2017b): it becomes more difficult to deceive as one ‘approaches’ a goal.

We implemented the ambiguity and irrationality models defined in Section 3 and applied in two domains: the P4 path planning framework³³3See https://bitbucket.org/ssardina-research/p4-simulator/ and the Berkeley Pacman framework ⁴⁴4See http://ai.berkeley.edu/.

Independent variables  We evaluated four different agents in our experiments:

1. (1)

   an ‘honest’ agent, which uses the optimal policy for the real reward function;

2. (2)

   one deceptive agent that uses the ambiguity models; and

3. (3-4)

   two deceptive agents using the irrationality model, with $\alpha=0.3$ and $\alpha=0.5$ respectively.

Reward functions gave a reward of 10,000 for reaching the destination state. Negative rewards model actions costs, with $-1$ for an action up, down, left, or right, and $-\sqrt{2}$ for any diagonal move. For the ambiguity model, we set pruning parameter $\delta=0$. Q-functions were implemented as Q-tables for P4 and were learnt using value iteration Sutton and Barto (2018) until convergence, and implemented using linear function approximation for Pacman and were learnt using Q-learning.

Measures  We measured: (1) the total path cost, which is the inverse of the discounted reward; (2) the probability assigned to the true reward function, calculated using a naïve intention recognition algorithm Masters and Sardina (2017a); Vered et al. (2016); and (3) the simulation value of the paths from Masters and Sardina Masters and Sardina (2017b):

This definition calculates, for each state-action pair, the deceptiveness of the step by using the observer’s intention recognition model and taking the difference between the most likely reward function and the actual reward function. The deceptiveness $D(\@vec{o_{t}},\mathcal{R})$ is then the average deceptiveness over the observed trace

This intention recognition algorithm used for measures 2 and 3 assigns the probability of each destination as being the real destination by comparing how rational the observed behaviour is for each destination, where rationality is assigned based on how close the observed behaviour is to the optimal behaviour.

Experiment parameters  We used five different layouts for each domain, varying in size and structure. For example, for P4 we varied number and density of obstacles as follows:

1. (1)

   $49\times 49$ with no obstacles, such as in Figure 2;

2. (2)

   $49\times 49$ with some large obstacles, such as in Figure 3;

3. (3)

   $49\times 49$ map with random and high density obstacles;

4. (4)

   $100\times 100$ with ‘archipelago’ (a small number of large island obstacles);

5. (5)

   $100\times 100$ with many rooms and corridors.

For each layout type, we defined eight different variations by changing the number of goals (three or five in P4), distribution of rewards, and the position of the real reward, leading to a total of 40 layouts. For the Pacman domain, we used 10 maps from the Berkley framework. Each model was applied to all 50 maps for each domain. For each path generated, the intention recognition measure was taken at nine ‘checkpoints’: every $10\%$ along the path.

Figure 4 plots the average probability of the real ‘goal’ at each point for both domains. We separate the results into three-goal maps in P4, five-goal maps in P4, and the Pacman maps. In all cases, it is easier to identify the real reward function as more plan steps are revealed, however, there is a clear trend that the deceptive models make it more difficult. The irrationality models are more deceptive but this must be considered alongside path costs.

Figure 5 demonstrates the simulation measurements for different scenarios. The simulation level of the honest model is the lowest among all models in most of the time, which consists with the probability results. This is perhaps the most interesting measure in our experiment, as it measures true ‘deceptiveness’.

On the simulation data, we performed a Kolmogorov-Smirnov test of normality to confirm that our data matches the characteristics of a normal distribution. We then performed paired t-tests for independent samples between the honest model and the three deceptive models. The honest model showed the lowest level of simulation ($M$=-0.24, $SD$=0.17). In comparison, the ambiguity model ($M$=-0.16, $SD$=0.18) was more deceptive than the honest model $t(98)$=2.05, $p$=.04. Similarly, the IR_0.3 model ($M$=-0.13,$SD$=0.24) was more deceptive than the honest model $t(98)$=2.64, p=.009, as was the IR_0.6 model ($M$=-0.009,$SD$=0.21), $t(98)$=6.06, $p<.001$.

Figure 6 shows the path costs as a proportion of the length of optimal (honest) path. The ambiguity model arrives at the destination with fewer actions than either irrationality model. This is important because in addition to being deceptive, the objective of deceptive reinforcement learning is to maximise discounted expected rewards. In some cases, irrationality model with $\alpha$=$0.5$ was more than four times as long. If we give higher priority to the expected reward for the real reward function, we may prefer the ambiguity model or to use the irrationality model with a lower value of $\alpha$. In some cases, if deception is weighted low enough, the honest model would still be preferred because of the short paths, which results in higher actual reward for discount factor $\gamma<1$.

Analysis looking into individual maps, we see that the IR models generate longer paths due to the randomness in the paths. For the ambiguity model, the paths are slightly longer for the five-goal maps, because there are more bogus goals that ‘pull’ the agent away from the optimal honest path. This indicates that, in some domains in which the real reward is strongly weighted, even if there are many possible bogus reward functions, it may still be more suitable to select only a subset of the bogus goals for the entropy calculations. Further results on individual maps are available in the supplementary material.

Overall, we see that it is easier to deceive in the Pacman game than in path planning, which we attribute to the fact that there is just a single reward at the destination in path planning, and eventually we end up with fewer and fewer goals until finally the only likely goal from the observer’s view is the real goal.

The experiment design was similar to that used for the computational evaluation, with three exceptions: (1) instead of the intention recognition algorithm, we ask human participants to estimate the goal distribution; (2) the human participants were provided with only a random selection of the maps and methods; and (3) we assessed based only on the path-planning problem.

Our experiment used 40 maps $\times$ four possible models producing behaviour = 160 map-path pairs. We generated checkpoints at 25%, 50%, and 75%, leading to 480 stimuli in total. Each participant received 38 randomly-selected stimuli. Participants were ‘aware’; that is, they were explicitly told that the agent may try to hide its true destination, and that they should try to guess the true destination. We recruited 69 participants via Amazon Mechanical Turk, a crowd-sourcing platform often used for human-subject experiments Buhrmester et al. (2018). Participants were paid US$4 for completing all tasks, which took on average 11.5 minutes. Participants were aged 20-55 ($\mu=32)$. 15 participants were female, 54 were male, and none chose to specify their gender manually.

Figures 7 and 8 summarise the results for the human subject evaluation. We see similar outcomes to that of the naïve intention recognition algorithm, except that human subjects were overall less accurate than the naïve model, even for honest behaviour. This is understandable as the optimal behaviour is straightforward for an algorithm to calculate, but less so for a human. At the first checkpoint, by which point participants have seen 25% of the path, the accuracy is close to random.

For the ambiguity model with three goals, participants were more accurate than for the honest model at 75% density, but this is mostly accounted for by noisy data – the difference is less than 3%. The deceptive models were more effective at deceiving in the five-goal model than the three-goal model, which is unsurprising as there are more bogus goals to use.

An interesting point is the effect of the participants being aware that they are being deceived, which is not the case for the earlier computational experiments in which the observer model is naïve. In the computational experiments, the honest model is never considered deceptive. The simulation value is at most 0, meaning that the real destination is judged to be as likely as others. However, in the human subject experiments, the honest model is, on average, considered to be deceptive early in the experiment, presumably because the participants were assuming that the model was using deception as simulation (showing the false). Also interesting is that the deceptive models were considered deceptive right up until the 75% mark and presumably beyond. In the computational experiments, the simulation value was, on average, below 0 at the 75% mark for all deceptive models. This is perhaps due to the fact that the human participants are unable to make accurate judgements as quickly as the intention recognition algorithm. As such, results may differ if we had a non-naïve intention recognition model.

Overall, we see that our models deceived participants for the path planning task, but the effectiveness may not be sufficient if the length of the plan is considered too high. This largely depends on the weight $\omega$ in Equation 2.

There are several limitations with our study. First, while path planning is a good application for human behavioural experiments (people are good at spatial reasoning), it is only one domain, so further experimentation on different types of domains is necessary. Second, the naïve intention recognition model we used to evaluate deception in the computational evaluation is not as sophisticated as our model of deception – it does not mitigate for the fact that it is being deceived. This is difficult to mitigate because we need a level of separation between the methods and the evaluation metrics, and the only suitable model of which we are aware is the irrationality model Masters and Sardina (2019), on which our model is based. Third, there was only minimal incentive for our experimental participants, which is not reflective of some applications where failing to identify deception can have devastating outcomes.