Modeling Human Behavior - Part I: Learning and Belief Approaches

Robotics can utilize demonstrated human capabilities as well as behaviors to learn skills or behavioral policies. For instance, humans can provide demonstrations of behavior for a robot learner using a Policy-gradient RL policy, which can then be improved through practice and exploration by the learner (Akbulut et al., 2021). Similarly, humans demonstrate the ability to adapt skills to variations and new scenarios. This adaptability has been explored in RL agents in robotics to enable generalization from initial demonstrations or exploration (Julian et al., 2020; Ramaraj et al., 2021), which enables aspects of learning from demonstrations and an interactive learning process as seen in Imitation Learning, Inverse Reinforcement Learning, and Active Learning. Robot agents can also learn to anticipate the movement of humans or other artificial agents in order to compensate for their movements or rendezvous at a later position (Wang et al., 2020c; Mavrogiannis et al., 2021; Möller et al., 2021). This concept can also be extended to further topics in human-robot collaboration (Semeraro et al., 2021). Additionally, robot vision can be designed to replicate models of human vision mimicking foveation (Baron et al., 1994), which allows agents to observe visual stimuli with similar attention and focus to stimuli. These topics demonstrate how robots can be designed to learn from humans and also learn to operate in an environment alongside humans. The approaches for these solutions span multiple disciplines, including ones described in this paper (e.g. RL, Inverse Reinforcement Learning (IRL), etc.).

There have been numerous examples of research performed to model and predict behavior in a driving scenario (Kolekar et al., 2021). These topics include methods which model pedestrian behavior (Choi et al., 2019) or the behavior of other drivers (Fernando et al., 2020; Bhattacharyya et al., 2020; Chandra et al., 2020). This type of modeling serves to train autonomous vehicles how to successfully drive while predicting or compensating for the behaviors of others through the use of models based on Inverse Reinforcement Learning, Imitation Learning, and related. This predictive power is essential so systems can anticipate and react to the non-uniform nature of human behavior. In addition to modeling the behavior of other drivers, systems have been investigated which can model the vehicle control behavior of drivers (Pentland and Liu, 1999). This allows for comprehension and modeling of driver control movements when operating a vehicle.

In the area of video and serious games, AI is being considered with respect to multiple aspects. In one aspect, researchers and developers are investigating techniques to integrate AI into game development and game character behavior (Young et al., 2004; Xia et al., 2020; Yannakakis and Togelius, 2018; Bontchev et al., 2021; Zhao et al., 2020). This allows for levels, players, etc. to be generated or controlled by adaptive behavior models to create a broader scope of experiences. These examples demonstrate uses of approaches such as planners (see Section 4), Reinforcement Learning, and related to improve the performance, adaptability, or creation of games. Non-Player Character (NPC) behavior can be supported by these techniques to generate policies based on historical gameplay data or learned models of play. This can be from learned models of behavior or based on past human player choices (de Almeida Rocha and Duarte, 2019). NPCs with these characteristics could prove better suited to respond to player choices and allow for more options. Similarly, the generation of levels and scenarios can also be expanded by allowing for more dynamic combinations of resources by the system.

For relevant survey papers and related, please refer to (Schatzmann et al., 2006).

RL is a method by which situations are mapped to actions so as to maximize a reward signal (Sutton and Barto, 2018). The maximization is performed by the learning agent through exploration of an environment and the possible actions. This exploration generates a feedback signal via rewards which the agent uses to learn the behaviors resulting in the most desirable feedback. The feedback received can be provided immediately or can be a result of a sequence of actions. For example, an agent could receive a reward for each step they make in an environment or simply a single reward at the end of a training session which corresponds to the outcome. The different parameters of the problem lead to numerous techniques for learning optimal behavior policies.

Given a scenario or MDP, an agent can be trained to find a policy $\pi:S\rightarrow p(A)$ which defines a likelihood of actions given current state. An agent’s policy is learned through trial and error by exploring the given MDP and observing the rewards $r\in R$ provided as output. A policy is based on an estimate of action utility based on past observations and estimates of trajectories. The agent can generate an estimate of discounted return based on a discounted sum of future rewards:

where $R_{t+k}$ denotes the reward observed time steps after time $t$ and $\gamma$ is the discount parameter. This describes a measure of estimated return based on observations of trajectories. The value of $\gamma$ determines how quickly the scale of future rewards decays, which impacts how strongly those observations impact the estimates. With this method of estimating returns, agents can generate a model of likely utility of actions in states. This concept is used to define a value function $\nu(s)$ given state $s$ where the assumption is that the agent starts in state $s$ and executes actions according to their policy $\pi$ in following states. The distinction in this case is the fact that the estimate is based on estimated behavior determined by a policy $\pi$. This means that the estimated value will consider the estimates of future values given the current state and expected trajectory of future states. In (Sutton and Barto, 2018), $\nu(s)$ is defined as:

Similarly, the action value function is used to estimate the value of executing an action $a$ in a given state $s$:

These are fundamental equations with respect to behavior policy learning via RL. Learning methods can be generated providing a means to learn a representation of value following Equation 3. This is done by utilizing the trial and error process of RL. Agents explore the environment and select actions (following a learning scheme - e.g. Epsilon Greedy) in order to observe the effect of actions. The effect is reflected in the rewards observed following an action or sequence of actions. These observed rewards are used in the estimated state-action value function in order to incrementally improve the estimated utility of actions. This is done by refining the estimate through a modeling process which uses immediate rewards and the current estimate of value to refine the estimate. This cycle is used to learn a policy through the feedback loop created by taking an action, observing an outcome, and updating the policy of actions accordingly. As an example, a temporal difference method can be used in Q-Learning to learn a state-action value function:

where $\alpha$ is the learning rate used to discount the scale of the current estimate in the update to the estimated value. As can be seen, there is a recursive relationship between the current state’s utility and the value of future states in the discounted $\gamma\max_{a^{\prime}}Q_{t}(s^{\prime},a^{\prime})$ term. This enables the relationship between the value of the current state and the value of future states under the assumption of following the current policy.

In RL, the method for defining and finding optimal behavior depends on the nature of the elements of the observation available to the agent. In the most general case, such as Q-Learning demonstrated above, the agent observes the current state and selects an action according to $\pi$. Typically, this is done by identifying $\operatorname*{argmax}_{a}q_{\pi}(s,a)$. An important aspect of basing decisions on discounted future utilities is the possibility of MDPs which could result in sub-optimal behavior given a myopic view. For instance, Figure 2 provides an example of how too greedy a nearsighted view of state values would lead an agent to bias its behavior to lead from state $4$ to state $1$ with a sum of rewards equal to $12$ rather than the optimal choice, which is $4$ to $7$ with a sum of rewards equal to $21$. Such a scenario can be quite common and is one of the many challenges for successful policy learning in RL.

RL contains numerous examples of constraints which differentiate families of problems. For instance, it is possible to have an environment which is only partially observable (Shani et al., 2013). In this case, not all aspects of a state are observable to an agent and so there is uncertainty regarding the exact state the agent is occupying. This results in a need for the agent to estimate the current state and use that estimation in the updates to the value function. In another case, the actions may not lead to an outcome with $100\%$ certainty. An example is a stochastic gridworld problem (e.g. OpanAI Gym FrozenLake (Brockman et al., 2016)). In this scenario, agents try to navigate a 2D world by moving up, down, left, or right. When an agent selects an action, there is a non-zero probability that the agent moves to an unintended state. For example, an “up" move could in fact move the agent to the left. In this case, the learning method must support this uncertainty. It is worth noting that the previous examples represent scenarios supported by tabular methods. The use of RL has also been extended to continuous cases and there are methods utilizing Deep Learning. This is referred to as Deep RL and is commonly used in the case of continuous and/or large domains such as robotic control or video games (Arulkumaran et al., 2017).

RL is an extensively studied and applied research topic. Agents have been trained to learn how to utilize attention or contextual information to improve policy learning (Salter et al., 2019; Oroojlooy et al., 2020). Agents can also be trained to utilize memories and past experiences in a more human-like manner in the hopes of solving credit assignment, handling sparse rewards, handling non-stationarity, comprehending relational knowledge, etc. (McCallum, 1996; Hung et al., 2019, 2019; Lillicrap and Santoro, 2019; Lansdell et al., 2019; Padakandla et al., 2020; Wang et al., 2020a; Džeroski et al., 2001; Forbes and Andre, 2002). Similarly, RL agents can learn techniques to associate aspects of past experiences to contextual information for decision-making (Fortunato et al., 2019; Li et al., 2020).

The use of past experience can also be extended to other agents or humans in the environment. An agent can learn to perform simultaneous control (i.e. shared autonomy) using RL methods (Reddy et al., 2018) or the observed behavior of others can be included in the observation space to allow for action selection conditioned on likely behavior of others (Xie et al., 2020). An additional aspect of comprehending others is the prediction of behavior or goals, as is demonstrated in (Nguyen and Gonzalez, 2020a, b). Further, past experiences or behavior can be utilized as a means to predict likely future outcomes in order to guide agent behavior (Sun et al., 2019; Zhang et al., 2020).

For relevant survey papers and related, please refer to (Arora and Doshi, 2021; Fernando et al., 2020).

IRL is a method by which an agent learns from examples of behavior without access to the underlying reward function motivating the behavior. The key distinction in this case is that the agent is trying to replicate or approximate the reward function $R_{E}$ or policy $\pi_{E}$ that caused the exemplar behavior. This results in effectively needing to learn a reward while simultaneously attempting to learn optimal behavior policy under the current estimated reward function. As such, the agent is performing two interdependent tasks. Given a policy $\pi_{E}$ or a set of $N$ demonstrated trajectories

the agent is tasked with learning a representation which could explain the observed behavior (Arora and Doshi, 2021).

Generally speaking, there are numerous methods or approaches with respect to IRL. Therefore, we will be unable to address all the techniques in this section. We will instead provide some preliminary examples to provide some intuition regarding the common techniques and underlying principles. One method for the IRL task is that of apprenticeship learning (Abbeel and Ng, 2004). In this case, there is an assumed vector of state-related features $\phi:S\rightarrow[0,1]^{k}$ which support the reward $R^{*}(s)=w^{*}\cdot\phi(s)$ with weight vector $w^{*}$. The feature vectors $\phi$ refer to observational data corresponding to the states (e.g. a collision detected flag). Given the definition of reward, the value of a policy $\pi$ can be measured by:

with the initial states being drawn $s_{0}\sim D$ and with behavior following from the policy $\pi$. Then, the feature expectation can be defined as:

which is used to define a policy’s value $\mathbb{E}_{s_{0}\sim D}[V^{\pi}(s_{0})]=w\cdot\mu(\pi)$. Given the estimation of feature expectation $\mu(\pi)$, the goal is to find a policy $\tilde{\pi}$ which can best match the observed demonstrations. In order to do so, this requires a comparison between $\tilde{\pi}$ and $\pi_{E}$. Since the policy $\pi_{E}$ is typically not provided, an estimate $\hat{\mu}_{E}$ based on demonstrations is needed. This can be accomplished by an empirical estimate:

for a given set of trajectories $\{s^{(i)}_{0},s^{(i)}_{1},\dots\}^{m}_{i=1}$.

Given this structure, algorithms can be defined for iteratively refining the weight vectors and resulting policies. This enables the two components of the IRL paradigm. First, the estimated weight vectors $w^{(i)}$ define an estimated reward function which can be refined by updating the weight vector so as to reduce the discrepancy between the two estimated feature expectations $\hat{\mu}_{E}$ and $\mu(\pi)$ which measure agent performance. Second, the estimated reward with the current weight $w^{(i)}$ enables learning a policy which is optimal for the current estimate of policy value (Equation 5) using RL, which is used in the first step to measure value discrepancy. This provides a cyclical process of reward refinement and policy learning.

It is important to note that the extra step of finding a suitable reward function and policy increases the complexity of the problem. The cycle of improving the reward requires the agent to retrain a behavior policy which reflects the new reward. On the other hand, finding an accurate representation of the reward would afford the agent a more general understanding of the behavior. Having access to a reward function allows an agent to understand desirable behavior at an abstract enough level to potentially transfer its understanding to a new environment. Of course, if the approximated reward isn’t accurate enough, one would expect this to result in potential issues. In any case, there is the potential for increased generality of the resulting agent. It’s worth mentioning that an exact replication of the underlying reward isn’t entirely necessary. In fact, an affine transformation of the true reward function would in fact result in an equivalent policy (Arora and Doshi, 2021).

As an example of IRL, we refer to (Yang et al., 2020a) in which they try to learn a model to replicate human gaze patterns when searching for a visual target. The authors propose the use of imagery data with the human gaze fixations annotated. They used simulated fovea to learn a plausible model of desirable objects for attention. This is used to model how a human’s gaze shifts around an image while attempting to locate an object within an image. The approach showed an improved ability to identify particular objects of interest rather than generating a saliency map to demonstrate attention.

In their method, they utilize an approach they refer to as Dynamic-Contextual-Belief (DCB), which is composed of three components: fovea, contextual beliefs, and dynamics. The fovea serves to mimic human vision and to provide only a sub-region in high detail while blurring or masking the remaining region. The masking results in a reduction in the observation space, limiting the input to a portion of the input space. In their approach, the masking is used to select a sub-region of the image to represent in high resolution while the remaining regions are represented using a blurred version of the image. This approximates the effect of the fovea on human vision and is used to represent the fixation of the observer. The contextual beliefs are used to represent a person’s understanding of the contents of the scene such as objects and background items of an image. Lastly, the dynamics collects information regarding the focal fixations during search. The dynamics are represented as a transition between versions of the image which are updated based on iterations of fixation. Each region which receives fixation is replaced by its high-resolution representation resulting in a transition represented by:

where $B_{t}$ represents the belief state after $t$ fixations and $M_{t}$ is the mask generated by the $t^{th}$ fixation. $L$ and $H$ are belief maps which represent object and background locations for low-resolution and high-resolution images, respectively. Based on this definition, we can see that the representation of the image and the beliefs $B_{t}$ regarding contextual information and item locations are updated based on the iterative search conducted by moving the fixation around the image.

To represent the reward and learn a policy representing visual search behavior, the authors utilize Generative Adversarial Imitation Learning (GAIL). The GAIL framework utilizes the adversarial paradigm with networks representing the discriminator $D:S\times A\rightarrow(0,1)$ and generator $G$. These are used to train the system to generate data which matches the patterns of the original sampled data. The discriminator is tasked with learning to distinguish between real human data representing beliefs and fixation transition actions versus data which is generated artificially by $G$. The generator $G$ is tasked with learning to generate beliefs and actions which are convincing enough to the discriminator $D$ so as to be labeled as real rather than artificially generated. This is accomplished by maximizing an objective function:

where $D(S,a)$ is the output of $D$ given the state-action pair $(S,a)$, $\mathbb{E}_{r}$ refers to the expectation over real state-action pairs, $\mathbb{E}_{f}$ refers to the expectation over fake search transition samples from $G$. The gradient term at the end of Equation 9 serves to improve the convergence rate. The definition of the reward is based on the output of the discriminator:

For the generator, the performance uses Equation 10 and is tasked with maximizing:

which shows that the higher likelihood of being real the discriminator places on generated data, the higher the resulting reward will be. To find an RL policy for the generator, the authors utilize Proximal Policy Optimization with the following representation:

where the advantage function $A$ is estimated using generalized advantage estimation (GAE). The advantage represents the gain observed by taking action $a$ versus the policies default behavior. This definition of loss for the policy learning helps guide the learner toward actions which will result in higher advantage over other actions. The term $H$ is the max-entropy IRL term $H(\pi)=-\mathbb{E}_{\pi}[\log(\pi(a|S))]$ which helps improve convergence.

To test the approach, the authors utilized the COCO-Search18 dataset. The images were selected based on five criteria: Five criteria were imposed when selecting the TP images. First, they used no images portraying an animal or person so as to avoid the known strong biases to these categories. Second, they enforced each image having only a single instance of the target item. Third, the size of the target item must be within $[0.01,0.1]$ the area of the image (measured by bounding box). Fourth, the target should lie outside the center of the image, which was determined by excluding items whose bounding box overlapped with a region in the center. Lastly, the image dimensions must have a ratio in $[1.2,2.0]$ to allow for their display screen. Further filtering was performed and the reader can refer to the original text for more details.

The algorithm was tested against relevant baselines as well as against human performance. The authors utilized results from $10$ participants who viewed the $6,202$ images in the dataset. During their participation, eye tracking was performed during their search task. The algorithms compared against were: a random scanpath, a ConvNet detector, Fixation heuristics, a Behavior Cloning CNN, and a Behavior Cloning LSTM. The results demonstrated show their method meeting or exceeding the performance of the compared algorithmic methods. The results demonstrate the relationship between the number of fixation transitions made before finding the target and the success rate of the searches.

Additional tests were performed to test additional aspects, which can be found in the original text. As was demonstrated, this approach was able to successfully approximate the behavior demonstrated by the humans and also succeed at the identification tasks.

For relevant survey papers and related, please refer to (Hussein et al., 2017).

IL is a process which attempts to reproduce behavior given by experts in order to learn a pattern of behavior under a given task (Osa et al., 2018). At an abstract level, IL is closely related to IRL. In both cases, the goal is to utilize observations of behavior to train a behavioral model or policy. The key distinction comes in the structure of the learning process. In IRL, the learning process attempts to learn a suitable reward function which aligns with the demonstrated behavior. Additionally, the learning process uses the learned reward to generate a policy of behavior. The learned policy of behavior should closely model the demonstrated behavior. For IL, the learning process is not designed to generate a reward function which fits the demonstrations; instead, the process attempts to directly learn a model of behavior which best fits the demonstrated behavior.

As a demonstration of the principles, IL can be formulated as follows. Given a trajectory $\tau=[\phi_{0},\dots,\phi_{T}]$ of features $\phi$, the learner is tasked with learning a policy reproducing the behavior. The vectors $\phi$ represent the features of the environment or system at each stage of the trajectory. The context, or state, $s$ representing the system state can be used in conjunction with an optional reward parameter $r$ as components of the underlying optimization problem.

With a set of demonstrations $\mathcal{D}=\{(\tau_{i},s_{i},r_{i})\}_{i=1}^{N}$ of trajectories $\tau$, contexts $s$, and rewards $r$, (NOTE: the reward values $r_{i}$ might not be provided), the goal is to find a policy $\pi^{*}$. The policy should minimize the discrepancy between the distribution of features from the expert $q(\phi)$ and the distribution of features from the learner $p(\phi)$:

where $D$ is a discrepancy measure such as Kullback-Leibler. A key feature of Equation 13 is the fact that it promotes the alignment of behavior through direct observation by penalizing distributions with large discrepancies from the demonstration. This goal of low discrepancy guides the policy search toward those policies which best fit the observed distribution over features. Overall, the method for building will vary with each approach, but the underlying principle of direct replication is still a key component.

In (Liu et al., 2019), the authors demonstrate an IL method which is capable of performing policy improvement through the creation of examples without domain knowledge from a human. This allows the learner to perform policy improvement which may avoid the biases of the human domain knowledge commonly observed in IL tasks. To accomplish this, they define a policy improvement operator and methods for generating behavior exemplars. Note, this method differs from IRL as it is attempting to directly learn and refine a policy to fit the observed behavior without learning from an estimated reward function.

For relevant survey papers and related, please refer to (Settles, 2009; Ren et al., 2020; Najar and Chetouani, 2021; Ramaraj et al., 2021).

AL is intended as an AI paradigm by which the learner is able to query an oracle regarding unlabeled data. The goal is to enable a more efficient usage of potentially costly data by allowing the learner to identify a representation of confidence or understanding in order to determine which items should be prioritized or require input from an oracle (Settles, 2009). This is described as a characteristic similar to the concept curiosity in humans, since AL demonstrates a motivation to inspect items with less experience or certainty. This is related to how the system is able to decide what it wants to learn more about, not a true reproduction of human cognition. However, it has been argued that humans must regulate their priorities regarding curiosity in order to when and what to learn (Ten et al., 2021). When prompted, the oracle can then provide labels for the queried samples, reducing the need to label larger sized datasets prior to the start of training.

There are numerous ways in which the learner can represent its understanding of the data to determine its confidence level. The representation is used to measure which would be the most desirable query. A possible definition could be the use of entropy to measure the confidence:

for labels $y_{i}$, instance $x$, and model $\theta$. This provides an information-theoretic representation of the uncertainty. Specifically, the instance selected for the oracle feedback is the one corresponding to the largest entropy in the probability of assignment to the various labels (as per Equation 19), i.e., the one for which the distribution of probabilities is closer to a uniform distribution, thus corresponding to the most uncertain assignment. Another approach is the instance with the least confident labeling:

where $y^{*}=\operatorname*{argmax}_{y}P(y|x;\theta)$ is the most likely class labeling. This promotes querying instances which have a best labeling with the least confidence.

The underlying principle in Equation 19 and Equation 20 remains the representation of how well the model can relate instances to the labels based on a self-aware measure of certainty. The utilization of this notion of confidence is what allows for systems to exhibit behaviors akin to curiosity. This allows them to guide the learning process and reduce the reliance on large datasets.

As a demonstration of AL, we will discuss the approach outlined in (Navidi, 2020; Navidi and Landry, 2021) in which the authors create a method of active imitation learning in a RL context. The proposed approach is a divergence from the above examples of approaches, but still utilizes the general principles of AL. In this case, the authors attempt to learn a model which can predict the oracle’s responses for improved performance and to compensate for potential delays between agent action and oracle response. The prediction model enables the agent in its learning process and guides the policy learning. Unlike the form of AL described above, the oracle feedback instead provides labels of good or bad behavior, so the agent’s policy learning phase will learn to avoid poorly performing actions rather than querying low-confidence items. This creates a method which combines concepts from IL, AL, and RL. This way, the behavior of the oracle encodes a model of the human’s preferences with respect to agent behavior. Regarding the underlying algorithm, the authors propose a combination of SARSA and A3C with human-in-the-loop training.

As a means to provide feedback from the teacher, agents observe a binary signal indicating positive or negative view from the human teacher. This is in contrast to other methods which might provide more complicated or graded feedback by utilizing varying levels of good or bad (e.g. $[-100,-50,50,100]$). In order to compensate for variance in both reaction time and frequency of responses from the teacher (e.g. some might tire of giving feedback), the authors propose a feedback prediction system.

The feedback predictor or manager $FB$ is designed to learn and predict the feedback behavior of the human teacher. $FB$ is provided responses from $\{-1,1\}$ to signify satisfaction: $1$ or dissatisfaction: $-1$. The feedback prediction policy is denoted as:

where $FB(O,A)$ denotes the teacher feedback policy, $\psi$ are the policy parameters, and $\theta(O,A)$ represents a density function modeling the human response delay.

The feedback is then used to guide the training of the RL policies for the agent. The authors test their approach utilizing the SARSA and A3C algorithms. The feedback weights past observations to give a teacher-based representation of the outcomes. These methods are tested against in the Open-AI Gym environment and the authors illustrate results for the Cart-Pole and Mountain-Car environments. In both cases, we can see the proposed methods performing strongly in the environments and against the baseline methods.

For relevant survey papers and related, please refer to (Costantini, 2002; Gershman et al., 2015; Ackerman and Thompson, 2017; Griffiths et al., 2019; Peterson and Beach, 1967; Khan et al., 2020; Hospedales et al., 2020; Wang, 2021).

Meta-reasoning and Meta-learning consider topics related to a level of abstraction which allows the algorithm to make determinations at two levels. In meta-reasoning, this is often referred to ‘reasoning about reasoning’ (Costantini, 2002). Similarly, meta-learning is often referred to as ‘learning to learn’ (Khan et al., 2020). These indicate the core aspect, which is the ability to perform introspection in order to dictate behavior. More concretely, this often relates to an ability to determine how resources or behavior policies will be allocated to perform a reasoning or learning task. This implies a notion of cost or effort regarding the task as well as an ability to identify the most suitable solution/behavior based on the context of the problem. The notion of allocation of resources for reasoning systems can also be related to examples in human cognition and the notion of bounded rationality (Zilberstein, 2011), which we discuss in Part II.

In (Lange and Sprekeler, 2020), the authors investigate memory-based meta-learning (related to the concept of ‘learning to learn’). For their scenario, the key concept is an algorithm which can determine when to rely on a learning algorithm for generating behavior versus utilizing a heuristic. This enables agents develop policies when it is feasible given the time/computational constraints and rely on heuristics otherwise. Relating to human cognition and behavior, the authors note a similarity between the hidden activations of LSTM-based meta-learners and the recurrent activity of neurons in the prefrontal cortex. Generally speaking, allowing a split between fast/frugal mechanisms and slower/costly reasoning systems fits examples in human cognition and the notion of bounded rationality, and we discuss these related concepts in Part II.

On the topic of learning behavior policies, the authors note three features of particular interest regarding the dependence of the meta-learning algorithm on the meta-reinforcement learning problem:

• •

  Ecological uncertainty: How diverse is the range of tasks the agent could encounter?

• •

  Task complexity: How long does it take to learn the optimal strategy for the task at hand?

• •

  Expected lifetime: How much time can the agent spend on exploration and exploitation?

Based on their analysis, they showed non-adaptive behaviors are optimal in two cases: low variance across tasks in the ensemble, and when time constraints prevent sufficient time for exploration.

For the first scenario investigated, they test their approach on a two-arm Gaussian bandit task. It is noted that this allows for an analytical solution of optimality. The agent interacts with the environment by performing a series of $T$ arm pulls. The rewards for the two arms are represented by a deterministic reward of $0$ for the first arm and a Gaussian distribution with variable mean $\mu$ for the second. The mean is sampled $\mu\sim\mathcal{N}(-1,\sigma^{2}_{p})$ (where $\sigma_{p}$ specifies the scale of ecological uncertainty) at the beginning of each episode, and then is used to define the reward function $r\sim\mathcal{N}(\mu,\sigma_{l})$. It is noted that this variability controls how many arm pulls are needed to estimate the mean reward and $\sigma_{l}$ controls how quickly the agent can learn the policy since it controls the consistency of the observed rewards. The scale of $\sigma_{p}$ clearly determines how much uncertainty should be expected for the agent regarding the mean reward observed from the stochastic arm, which consequently scales the difficulty of estimating the expected utility of this arm. For $\sigma_{l}$, this determines how difficult it will be to estimate the mean based on observed rewards.

Given this definition, the optimal solution is determined analytically. The solution is based on the problem characteristics. Since the agent should perform $n$ pulls for exploration before exploiting its knowledge, the goal is to identify the optimal number of trials $n^{*}$ before concluding the exploration. The solution is as follows:

where $\hat{\mu}$ is the estimated mean reward of the second arm after $n$ exploration trials.

Based on their experiments, the authors noted two distinct types of behavior. In the first, learning via exploration is the optimal behavior. In the second, the agent should instead not learn and exploit its knowledge. The value in stopping learning is attributed to two aspects: 1) small ecological uncertainty can make it very unlikely the first arm is better; 2) too high of variance causes the lifetime to be too short for valid learning. As a result, the authors note this leads to two consequences. First, the values of $\sigma_{l}$ and $\sigma_{p}$ create a threshold between learning and non learning of behaviors. This determines whether learning is suitable or if the agent should instead rely on exploitation of the existing knowledge. Second, the optimal strategy is dependent on the time allotted for learning. The amount of knowledge an agent can attain is strictly dependent on the variance parameters and the time they have to learn the dynamics of the arms. The results indicate the relationship between complexity and uncertainty with respect to the expected number of trials. There is a clear delineation between the two behaviors indicated in the results.

Given the above specification, the authors generated agents trained on the bandit scenario, which they subsequently compared to the theoretically optimal solution. The outcome indicates the meta-learning paradigm creates agents matching the analytical solution. Given this structure, they note that such an agent demonstrates the dual components which handle learning a behavior policy and utilizing a hard-coded choice which selects the deterministic arm (which is the optimal choice in expectation).

To test the proposed approach in a more general case, the authors then train and test an LSTM-based actor-critic agent in an ensemble of gridworld tasks. This scenario allowed them to investigate the impact of lifetime on the exploration strategies of the agents generated. Intuitively, in the case of a long lifetime, the agent has more opportunity to search for higher-valued goals where shorter lifetimes would necessitate greedier identification of goals. This was tested by placing goals of increasing value at farther distances from the start state.

As indicated by the results, the trained agent demonstrates a learned preference for goals based on the proximity and lifetime $T$ provided. The results indicate the agent is able to learn a priority for farther goals when there is more time to discover and return to the higher-valued goal. Similarly, the agent learns to focus on goals closer to the start state when there is a higher restriction on $T$ or when the agent should prioritize the goal states based on time remaining. The agent exploits its policy to find the highest value goal while there is time and then switches to the lower value state when there is only time for these path lengths. This indicates the agent is able to exploit different experiential knowledge while also identifying when to switch between exploration or learned behaviors. Based on the two scenarios, the authors demonstrate their method having the means to learn how to switch between learning and exploiting learned models. This demonstrates ‘learning to learn’ and an ability to minimize the cost of behavior.

For relevant survey papers and related, please refer to (Bianco and Ognibene, 2019; Graziano, 2019)

ToM is what gives humans the capacity for reasoning about the mental states such as beliefs and desires for other agents in their environment (Baker et al., 2011; Wang et al., 2021; Rabinowitz et al., 2018; Freire et al., 2019). In most, if not all, aspects of daily life, humans rely on and utilize their ability to estimate the mental state of others. One can imagine numerous scenarios they might encounter daily where they are able to interact with someone while relying on this type of reasoning. Something as simple as trying to anticipate on which side to pass another pedestrian requires you to utilize this technique. It is also easy to imagine a more complex scenario. For instance, poker players must reason about both the hand likelihoods as well as the mental state of their opponents to ensure a higher chance of success. In the case of poker, players can utilize methods of deception in an attempt to disguise their true mental state and gain an advantage. As a result, players would need to reason about the mental states of their opponents to guide their playing strategy.

ToM relies on multiple aspects of perception. A person will utilize the non-verbal cues, contextual clues, and other stimuli to form a picture of the world from the perspective of another person. ToM is what allows you to imagine yourself in someone else’s place to model the likely next steps. Such a skill allows humans to perform better both as individuals and as part of a team. As with the walking and poker examples, one could also imagine numerous scenarios where people work together to accomplish a goal. People working together will of course utilize verbal and other forms of communication, but there is also a significant reliance on each member’s ability to use a deeper understanding of the observed behaviors of their collaborators. Without this ability, we could expect that every aspect of these interactions would require explicit and comprehensive communication regarding all aspects of the interaction.

The representation of others is not necessarily exact, but can instead utilize an approximate and higher-level model (Rabinowitz et al., 2018). Further, it can be argued that humans bias their models of others based on their own perspective. It is natural to expect a person’s past experiences to impact their model of another person’s perspective. Given a system to model the perspective of others, the natural extension is using this ability to generate recursive relationships between them (Wang et al., 2021). For instance, the ability to model the mental state of others can be extended to model the other person’s model of yourself. This means a person can generate a model of how they are perceived from another person’s perspective. As is noted by (Freire et al., 2019), there are several notable approaches to address the problem of ToM. These include methods which rely on RL, Neural Networks, policy reconstruction, etc.

An aspect of ToM is the ability to predict the behavior of others in order to act accordingly. The authors of (Wang et al., 2020c) demonstrate a use case in which an RL-based learner predicts the movements of another agent to support rendezvous in a multi-agent environment. This is accomplished by generating a model for motion prediction, which supports a Hierarchical Predictive Planning (HPP) module.

Formally, the authors define the problem as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) $\mathcal{M}=\langle n,\mathcal{S},\mathcal{O},\mathcal{A}_{1,\dots,n},T,\mathcal{R},\gamma\rangle$ where $n$ is the number of agents. $\mathcal{S}$ denotes the set of states and $\mathcal{O}=[\mathcal{O}_{1},\dots,\mathcal{O}_{n}]$ is the joint observation space, where $\mathcal{O}_{i}$ is agents $i$’s observations. The joint action space $\mathcal{A}_{1,\dots,n}$ is the combination of the agent action spaces $\mathcal{A}_{i}$ for agents $i\in\{1,\dots,n\}$, which define the actions available to the agents. The transitions are defined by the function $T:\mathcal{S}\times\mathcal{A}_{1,\dots,n}\times\mathcal{S}\rightarrow[0,1]$, which models the probability of transitioning between states given a joint action $a_{1,\dots,n}$. $\mathcal{R}$ is the reward function and maps states and actions to a reward $r\in\mathbb{R}$. As defined in RL, $\gamma$ is the discount factor for the learning process. The assumption in DecPOMDPs is that agents receive noisy observations of the environment and so the true state $s_{i}$ is unknown and is instead represented by the observation $O_{i}$. Consequently, the behavior relies on the estimated current state to identify a desirable action.

Agents are provided observations $\mathcal{O}_{i}=[\mathbf{p}_{i},\mathbf{p}_{-i},\mathbf{o},\mathbf{g}]$ where $\mathbf{p}_{i}$ and $\mathbf{p}_{-i}$ refer to the agent positions, $\mathbf{o}$ are the sensor observations, and $\mathbf{g}$ is the agent’s goal. The agents learn a predictive model of motion via a self-supervision algorithm. The systems are tasked with learning two models: self-prediction$(\mathbf{f}_{i})$ and other-prediction$(\mathbf{f}_{-i})$. In this context, $\mathbf{f}_{i}$ and $\mathbf{f}_{-i}$ refer to self and other dynamics models respectively. Note that these models are the key point where ToM is used in this example as they enable modeling and prediction of others. These models are learned to generate a self-prediction of position $\Delta\mathbf{p}^{t+1}_{i}$ and observation $\Delta\mathbf{o}^{t+1}_{i}$, using a time window of past position which covers the previous $h$ steps:

Similarly, a model for other-prediction (i.e. other agent prediction) is defined as

The authors note that the models do not depend on actions, but instead utilize observations of positions and posed conditioned on goals, which prevents needing to know the action space of others.

Given the predictive models $\mathbf{f}_{i}$ and $\mathbf{f}_{-i}$, a decentralized policy $\Pi_{i}$ is generated. This is done via the cross-entropy method (CEM) to convert goal evaluations into belief updates over potential rendezvous points. They note the intuition behind this approach is that each agent is simulating a centralized agent that fixes the goal of all agents, which are used to pre-condition the the motion predicted by $\mathbf{f}_{i}$ and $\mathbf{f}_{-i}$. These predictions are performed in a rollout of $T$ time steps into the future to predict the pose of agents. Based on the rollouts, the predicted goals are scored according to

where $\mathbf{p_{\mu}}=\frac{1}{n}\sum_{k\in 1,\dots,n}\mathbf{p}_{k}$ and $d$ is a precision parameter. This emphasizes accuracy of predicted future states and smaller distances between agents at rendezvous points. Based on the predicted goal values, goal states are sampled via a normal distribution and the estimation process continues in order to favor goals which bring the agents closer together. This process generates the policy $\Pi_{i}$ which is used to complete the rendozvous without centralized control. With the above approach, the authors demonstrate a ToM method which utilizes the first level of ToM reasoning to predict likely agent behavior based on past observations and the current circumstances.

For relevant survey papers and related, please refer to (Ullman and Tenenbaum, 2020)

The topics in this section do not represent a comprehensive list, but instead serve to illustrate a type of learning which relies on a level of world comprehension to accomplish the learning task. In this case, learning agents are provided models which allow them to understand a feature of the environment instead of requiring the agent to learn these features as well. For example, humans demonstrate a capacity for modeling the fundamental characteristics of an environment such as physics, compositional structure, etc. (e.g. Solidity (Ullman and Tenenbaum, 2020)). With such an understanding, the components of a scenario can be considered when learning or utilizing a skill. Such a behavior is demonstrated in multiple aspects of daily life. Something as simple as understanding that gravity allows a person to pour water into a glass is something we take for granted. Comprehension of these aspects of the world enables a rich set of behavior. For artificial systems, such a comprehension is often not provided or demonstrated. To overcome this, researchers have investigated methods in which features such as physical, compositional, hierarchical, etc. are provided as a model for simulation or planning.

To demonstrate the use of a modeling system to enable deeper understanding, we will discuss (Zhi-Xuan et al., 2020), which integrates PDDL into the model for planning based on different likely goals or trajectories. The inclusion of a planning system was intended as a method by which the system could account for sub-optimal or failed plans and incorporate them into estimates of future outcomes. Further, this approach was desired as a method which could account for the difficulty of the planning phase itself. The authors noted how many methods attempting to estimate goals fail to consider the difficulty of the planning portion of the process. Additionally, they note how most methods require the assumption of optimal behavior or Boltzmann-rational action noise. The assumption of optimality for all goals would therefore require computation of all goals in advance, which is intractable. In their approach, the authors use the integration of a planning system to represent a boundedly rational agent, where the bounds provide a resource limitation on planning and plan execution. This model provides a mechanism for Bayesian inference of plans/goals, even those with sub-optimal solutions, requiring backtracking, or irreversible failure. The limitation forces a constraint on the time or resources available to make a decision, which forces the agent at times to generate only a partial plan up to the level afforded by the constraints.

As noted above, the proposed approach represents the states, observations, and goals using PDDL and a variant supporting stochastic transitions named Probabilistic PDDL. This is accomplished by representing states and goals via predicate-based facts, relations, and numeric expressions in PDDL format. This allows for modeling of world state and actions, which are available when the provided preconditions are satisfied (e.g. current state, tool availability, etc.). The combination of predicates (e.g. relations such as ‘on’ or ‘at’) and fluents (e.g. fuel-level) allows the planning system to identify system state and available resources in order to generate a chain of actions and outcomes leading to a goal state. The actions result in a change in predicates and fluents, which signify the transition between world and system states. For a simple example, stacking blocks can be planned and considers the stacking agent’s state as well as the current position of the blocks. A block which is covered by another would not be available for stacking and so the predicate’s constraint would not be met for this block. On the other hand, uncovered or top-most blocks would be available, so one from this set would be available for selection for movement. With this representation, the observer has a prior over goals $P(g)$ specified via a probabilistic program over PDDL goal specifications. It is also noted that observation noise can be modeled for both the Boolean predicates and numeric fluents. This is accomplished by flipping predicate values or adding continuous noise with some probability (e.g. flipping a block’s covered flag when covered by another block).

To represent bounded rationality, the authors define a budget

where $r$ denotes the maximum failure count and $q$ denotes the continuation probability. Therefore, $\eta$ sets an upper bound on the solution search. If the bound is reached, the agent executes a partial plan leading to the most suitable state reachable from the found plans. This allows the agent to find the best plan they can given the limited resources available. The authors note that this model supports any planner capable of producing partial plans. For their scenario, the authors are operating in a gridworld environment and utilize a variant of the $A^{*}$ algorithm (Hart et al., 1968). that makes search stochastic. They note the modification to the $A^{*}$ algorithm relates to the state successor component and modifies how best next states are weighted. If an agent reaches an unexpected state or the end of its plan, then a new plan is generated with a newly sampled budget $\eta$.

To test the proposed Sequential Inverse Plan Search (SIPS) approach, the authors utilize several environments with goal set $G$ and state space $S$:

• •

  Taxi ($|G|=3$, $|S|=125$) A taxi has to transport a passenger from one location to another in a gridworld

• •

  Doors, Keys, & Gems ($|G|=3$, $|S|\sim 105$) An agent must navigate a maze with doors, keys, and gems

• •

  Block Words ($|G|=5,|S|\sim 105$) Goals correspond to block towers that spell one of a set of five English words

• •

  Intrusion Detection ($|G|=20,|S|\sim 1030$) An agent might perform a variety of attacks on a set of servers (20 possible goals corresponding to a set of attacks on up to 10 servers)

They test their approach against a Bayesian IRL (BIRL) model generated by value iteration. This allows them to compare against an approach based on RL solutions.

As a demonstration of effectiveness, the performance of SIPS and BIRL were compared to human performance in goal prediction. The results indicate a strong match between the SIPS model and the demonstrated human performance. These results were generated by collecting human goal inferences on ten trajectories with six sub-optimal or failed with $N=8$ subjects. Human inferences were collected every six timesteps.

For evaluation of accuracy and speed, the authors tested with a dataset of optimal and non-optimal trajectories. The optimal trajectories were obtained via the $A^{*}$ algorithm and the non-optimal trajectories were generated using a replanning agent model with $r=2,q=0.95,\gamma=0.1$. They performed inference on these datasets with a uniform prior over goals. Based on their tests, they found good performance with $10$ particles per goal without the use of rejuvenation moves.

In both test cases, the proposed method demonstrates strong performance. Additionally, the performance versus computational cost is quite strong in the majority of cases in comparison with the baseline BIRL.