Approximate Estimation of High-dimension Execution Skill for Dynamic Agents in Continuous Domains

The environments of interest for the skill estimation problem are those that feature continuous action spaces and can be modeled as Markov Decision Processes (MDPs). These MDPs consist of a set of states $S$, a continuous set of actions $A\subseteq\mathbb{R}^{n}$, a reward function $R:S\times A\mapsto\mathbb{R}$ and a transition function $P$ which specifies a distribution over potential subsequent states for any given state and action combination. An agent is an entity that acts in an MDP and consists of two components: one for decision-making and one for action execution. The decision-making component utilizes information about the current state of the MDP and the agent’s execution component to determine a target action, or more generally, a probability distribution over target actions, given the state. The distribution can be of any form so long as it produces a final intended or target action for a given state. The execution component refers to how accurately an agent can execute intended actions. This is represented by a probability distribution over random perturbations, $\chi$, from which a perturbation is sampled and added to the target action every time the agent acts. The resulting action, which is then actually executed in the MDP, is referred to as the executed action. Figure 1 depicts the relationship between these components as a part of the agent’s interaction with the environment.

The concepts of decision-making skill and execution skill were introduced in [3] as terms to describe the quality of an agent’s reasoning and the agent’s execution accuracy, respectively, in our setting. As described above, this notion of skill gave rise to the skill estimation problem [4, 6]. Precisely, this problem is to estimate parameters describing the agent’s decision-making and execution components, given observations of the agent acting in the MDP. These observations contain descriptions of the state as well as the executed action, but crucially, they do not include the target action. Methods have been proposed for estimating both execution skill and decision-making skill, and have been shown to be effective at producing skill estimates, under certain assumptions.

Several estimation methods have been proposed in the literature and shown to be effective at producing execution skill estimates. These methods differ in the type of information they utilize. The Observed Reward (OR) method [4] focused on estimating an agent’s execution skill by analyzing the rewards it receives during interactions with the environment. This method compares the average observed reward obtained by the agent with the rewards that would be expected from perfectly rational agents with a variety of execution skill levels. The final estimate is produced by interpolation. The OR method assumes that agents are perfectly rational, which limits its applicability. It was shown to produce accurate estimates for rational agents, but fails when agents do not make decisions optimally.

To relax the perfect-rationality assumption, an alternative method, The Bayesian Approach (TBA) (later referred to as AXE in [6]), was proposed [5]. This method models the skill estimation problem as a Bayesian network. Given the network, probabilistic inference can be performed to produce execution skill estimates, under the assumption that the agent would select one of a set of focal actions, or another action uniformly at random. This led to improved performance with a wider variety of agents, but required the definition of a set of focal points for a domain.

To avoid the need for any assumptions about an agent’s decision-making skill, later work proposed an alternate Bayesian network that explicitly incorporates the decision-making component as a random variable [6]. The resulting Joint Estimation of Execution and Decision-making Skill (JEEDS) method estimates both an agent’s execution and decision-making skill levels simultaneously. Reward information is utilized to reason about the agents’ decision-making, and the executed actions give insight into execution skill. JEEDS was shown to produce far more accurate skill estimates for agents across the entire spectrum of rationality levels.

Our proposed method, described in Section 3, utilizes a similar Bayesian approach as the prior methods, but differs in its modeling of the agent’s skill as time-varying random variables in the dynamic Bayesian network. Our proposed method also utilizes a different Bayesian inference algorithm to determine its skill estimates given the observations. The performance of the proposed method will be experimentally compared to JEEDS, since JEEDS is the best-performing existing method.

The topic of skill estimation has connections to many other lines of research. Methods for estimating the execution error of darts players have been proposed [25, 16], but in this work, the assumption is that the target action of the player is known. Recent work has proposed a novel handicap system for darts that utilizes execution skill estimates of the players [11]. A previous execution skill estimation technique [5] was used as a vital component in an application to baseball pitching [15]. In that paper, the interaction between pitcher and batter was modeled as a game, and equilibrium strategies for the pitcher were computed under various assumptions. This gives a good example of how execution skill estimates can be leveraged within larger frameworks to provide AI assistance to humans in real-world domains. Another paper focused on correlating the shape of a pitcher’s error distribution to their pitching mechanics, which was done in a controlled setting where targets could be specified for the pitcher [20].

The notion of decision-making skill has been defined for players in sports [1], and also relates to work on bounded rationality [21]. The specific softmax model that we utilize in this paper has been used in many other works, including the definition of quantal response equilibrium [14]. It has been used to adjust the strength of AI agents for Go [26], and to model human behavior [27]. Other work has proposed methods for determining this parameter for agents, given observations of their actions in two-player zero-sum games [13].

Estimating the properties of other agents in games is often called opponent modeling, and skill estimation can be seen as a method for determining important properties of observed agents [17]. Opponent modeling has been explored in the context of poker [8, 9, 10], real-time strategy games [19], and $n$-player games [22].

One could model the execution error as part of the transition function of the underlying MDP, resulting in a different MDP for each agent in the same environment. One potential way to view skill estimation work is as an attempt to separate transition information that is agent-specific from environment-specific information. This could potentially be helpful for transfer learning, an important problem in reinforcement learning [23, 28]. For example, how can a strategy developed for an agent with one execution skill level be utilized by an agent with a different execution skill level?

Finally, our proposed skill estimation method utilizes standard Bayesian reasoning techniques [18]. Particle filters have been used extensively in robotics to track the state of a robotic system [24]. One previous study used a particle filter for opponent modeling in Kuhn poker [7]. The task was to infer the parameters representing the strategy being used by the opponent in the game. At a high level, our approach is similar to theirs, but all the specific details: the components of the particle filter, the nature of the observations, and the whole setting, are different.

The dynamic Bayesian network used to guide inference for MCSE is shown in Figure 2. It consists of the following random variables:

• •

  $\Sigma$ is a multivariate random variable consisting of $k$ dimensions which correspond to the execution skill parameters of the agent that are to be estimated. $\Sigma$ is unobserved and isn’t directly influenced by anything else. Execution skill estimation methods will perform inference to update a probability distribution over possible execution skill levels, given the observations. $\sigma$ will be used to indicate a specific set of execution skill distribution parameters.

• •

  $\Lambda$ is a random variable corresponding to the decision-making skill of the agent. This is also unobserved and isn’t influenced by anything else, as it is considered an inherent characteristic of an agent. Decision-making skill estimation methods will infer a distribution over possible decision-making skill levels, given observations. $\lambda$ will be used to refer to a specific decision-making skill level.

• •

  $T$ is a random variable indicating the target action for a given observation. This random variable is also not directly observed, but can be influenced by the execution and decision-making skill random variables $\Sigma$ and $\Lambda$. A target action for a given observation will be referred to as $t$. The influence of the current state on the target action will be left implicit.

• •

  $X$ is a random variable indicating the action that is actually executed and observed. A specific executed action will be referred to as $x$. This random variable is directly influenced by the target action random variable $T$, as well as the execution skill multivariate random variable $\Sigma$. $P(x\hskip 2.0pt|\hskip 2.0ptt,\sigma)$ indicates the true conditional distribution over executed actions given an intended action $t$ and an execution skill level $\sigma$, and will directly correspond to the execution noise distribution $\chi^{\sigma}$, centered on $t$.

All of the variables are indexed by the observation number, as in this work, we model agents’ skill as time-varying, and the target and executed actions will in general also differ from observation to observation. Moreover, we focus on episodic environments but we hypothesize that MCSE can be successfully extended to sequential domains in the same way JEEDS was extended [6], by replacing the reward function with an optimal action-value function.

The proposed MCSE method will utilize a particle filter to perform probabilistic inference over the space of possible skill levels. A set of particles will be maintained, and this set will represent the current probability distribution over the agent’s skill. Each particle will correspond to a complete specification of an agent’s skill, including specific execution skill parameters $\sigma$ and rationality parameter $\lambda$. Every time an executed action and state are observed, each particle will compute a weight. This weight corresponds to the probability of an agent with that particle’s skill level executing the observed action. The particle will multiply its previous weight by this new weight. Periodically, a new set of particles will be resampled from the old set, with replacement. When resampling occurs, the weight for each newly resampled particle will be initialized to 1. When a skill estimate is required, it will be computed as the weighted average value of all particle skill parameters. Details for each of these components will be given in the following sections.

The MCSE method requires the ability to compute the probability of executing any specific action, given the parameters for an execution noise distribution and a target action. This will be represented abstractly by a probability density function (pdf) $f_{\sigma}$, where $\sigma$ represents a specific set of execution skill parameters. Thus, the conditional probability distribution $P(x\hskip 2.0pt|\hskip 2.0ptt,\sigma)=f_{\sigma}(x\hskip 2.0pt|\hskip 2.0ptt)$. This pdf can be made concrete given the specific parameterized execution skill distribution that will be used in a setting.

The MCSE method uses the softmax function, shown in Equation 1, to model imperfect decision-making as a function of the rationality parameter $\lambda_{b}$, as was done in [6]. This function provides a distribution over target actions, given a specific state, execution skill parameters $\sigma_{b}$, and decision-making parameter $\lambda_{b}$. Higher $\lambda_{b}$ values correspond to increased decision-making skill in this model.

The function $V:A\times\Sigma\mapsto\mathbb{R}$ is used to represent the expected reward for an action is a state $s$, given a target action and execution skill level. This is computed as $V(a,\sigma_{b})=\mathbb{E}_{\varepsilon\sim\chi^{\sigma_{b}}}[R(s,a+\varepsilon)]$.

The specific steps of the MCSE method are now provided. The details for some of the steps will be given in subsequent sections.

1. 1.

   Initialize the set of particles $B=\{b_{0},b_{1},\ldots,b_{M}\}$, where each $b_{i}=(\sigma_{b_{i}},\lambda_{b_{i}})$, with all skill parameters sampled from uniform distributions over their respective ranges.

2. 2.

   Repeat for each observed executed action $x_{n}$:

   1. (a)

      For each particle $b\in B$ update weight as
      $w_{b}\mathrel{*}=P(x_{n}\hskip 2.0pt|\hskip 2.0pt\sigma_{b},\lambda_{b})$ using Equation 2

   2. (b)

      Possibly resample new set of particles (see Section 3.5.2)

   3. (c)

      For each new particle $b\in B$ perturb particle parameters as described in Section 3.5.3 to account for dynamic skill

The traditional game of darts involves players throwing pointy projectiles (the darts) at a circular board. The player gets points depending on which region of the board the dart sticks in. The traditional game of darts has been the basis for much previous work in estimating agent skill [25, 16, 6]. We utilize the two-dimensional darts (2D-Darts) variant of the game introduced in [6], where the base rewards of the traditional dartboard are randomly shuffled. This variation guarantees that each dartboard presented to an agent is different and challenging, enabling the agent to showcase its decision-making and execution abilities more explicitly.

We parameterize execution skill in 2D-Darts using three parameters, which together define the covariance matrix of a bivariate Gaussian distribution. The three parameters we use are $\sigma_{x}$, $\sigma_{y}$, and $\rho$, which result in a covariance matrix of $\Sigma=\begin{pmatrix}\sigma_{x}^{2}&\sigma_{x}\sigma_{y}\rho\\ \sigma_{x}\sigma_{y}\rho&\sigma_{y}^{2}\end{pmatrix}$. We will represent by $f_{\Sigma}$ the probability density function corresponding to a bivariate Gaussian distribution with covariance $\Sigma$.

Different types of agents, each with an unique decision-making component, were utilized for the experiments. These are the same types used in the experiments conducted in [6]. The Rational agent selects an optimal action that will maximize its expected reward, with respect to its execution skill level. The Flip agent employs an $\epsilon$-greedy strategy, allowing it to select an optimal action w.p. $\lambda_{f}\in[0,1]$ or a uniform random one. The Softmax agent uses Equation 1 to probabilistically select an action w. p. $\lambda_{s}\in[0,\infty]$. From the possible actions that will yield an expected reward of $\lambda_{d}\in[0,1]$ times the maximum possible expected, the Deceptive agent selects the action that is the farthest from an optimal action. Note that the agents with an imperfect decision-making component have a single parameter ($\lambda$) to represent their level of rationality. For each, the higher the $\lambda$, the more rational the agent is. We assume that each agent has a correct model of its execution noise.

Each of these types of agents were combined with a wide variety of execution skill levels in the experiments. For the experiments conducted in [6], only agents with non-changing symmetrical execution skill distributions were tested. In contrast, for the current work, agents with both symmetric and asymmetric distributions were used. In addition, experiments were conducted both when agents have stationary execution skill distributions and when they have time-varying distributions. The results and findings for these experiments are presented in Section 5.1 and Section 5.2, respectively.

The process used to conduct each experiment was as follows. First, each agent being used in an experiment was initialized with the same execution skill level and a random decision-making skill level sampled from their respective range of rationality parameters. Each agent then repeatedly saw a state, selected a target action, and had an execution noise perturbation drawn from its execution noise distribution added to its target action. The final executed action was then observed by each of the estimation methods, which produced an estimate after each observation. All agents in an experiment experienced the same sequence of environment states and the same sequence of execution noise perturbations, to reduce variance in the results.

A resolution of 5.0 mm was used to discretize the action space. The reward function for each state was convolved with the agent’s execution noise distribution (using the same resolution) to compute the expected reward for all actions. Bivariate zero-mean Gaussian distributions were used for the true execution noise distributions, where $\sigma_{x}$ and $\sigma_{y}$ were selected from the range $[3.0,150.5]$ (mm), and $\rho$ from the range $[-0.75,0.75]$. The agent rationality parameter ranges were: $\lambda_{f},\lambda_{d}\in[0.0,1.0]$, and $\lambda_{s}\in[0.001,32.0]$.

Previous estimators output a single number representing the standard deviation of the agent’s symmetric execution noise distribution. Estimators were compared using the mean squared error (MSE) of this estimate compared to the true standard deviation. The MCSE method produces estimates for multiple execution skill parameters so the MSE won’t be as meaningful for comparison, as an error for each parameter would need to be included. Instead, we use Jeffreys divergence (JD) to measure the difference between the estimated execution noise distribution and the agent’s true execution noise distribution. The Jeffreys Divergence between two distributions $P$ and $Q$ is defined as follows: $JD(P||Q)=D_{KL}(P||Q)+D_{KL}(Q||P)$, where $D_{KL}$ is the Kullback-Leibler (KL) divergence. The KL divergence between two bivariate normal distributions can be computed in closed form from the corresponding means and covariance matrices.

The MCSE method has multiple parameters that must be specified. These include the number of particles to use ($M$), the amount of motion model noise to add to the parameters $w_{\%}$, the resampling strategy (always or $n_{eff}$, the percentage of particles to resample ($r$), and the $n_{eff}$ threshold to use when it is the resampling strategy, A preliminary set of experiments was conducted to explore different parameter values to select good parameters for the remaining experiments. These experiments only used stationary Rational agents, running for 100 observations in 2D-Darts. The results of this exploration are presented in the Appendix A, but the general observations were that higher $M$ improved performance, $w_{\%}$ didn’t appear to have much of an impact, and higher $r$ values generally led to better performance.

Based on this exploration, in the the remaining 2D-Darts experiments the MCSE parameter combination used was: $M=1000$, $r=0.9$, $w_{\%}=0.005$, with resampling based on $n_{eff}$ with a threshold of 0.5. This combination had the smallest average JD after 100 observations in the preliminary experiments. We will refer to this estimator as MCSE.

The selected MCSE method was compared to the JEEDS estimator from previous work. In the 2D-Darts experiments, JEEDS utilized 33 hypothesis skill levels for both decision-making and execution skill, resulting in 1,089 combined hypotheses. This number was chosen so that JEEDS would have approximately the same number of hypothesis samples as MCSE. The decision-making skill level hypotheses for JEEDS were logarithmically distributed. All JEED beliefs were initialized to be uniform over the space of possible skill parameters.

We first investigate the performance of MCSE at estimating execution skill in higher dimensions. To do this, the following process was repeated. First, a random set of execution skill parameters ($\sigma_{x},\sigma_{y},\rho$) were generated, each from their respective ranges. This execution skill level was used by all agents, who additionally each had a random decision-making skill level assigned, again from each agent’s respective range of rationality parameters. These agents faced 100 randomly generated 2D-Darts states, and each estimator observed the sequence of states and executed actions, producing their execution skill estimate after each observation. At least 4000 agents of each type were included in these experiments.

Figure 4 shows the average JD for each method over observations, where the average is taken across all experiments involving that agent. It is immediately clear that the performance of the MCSE estimators is significantly more accurate than JEEDS when used on agents with arbitrary execution noise distributions. The average Jeffreys divergence for the MCSE estimators converges to values between 1 and 2 after the 100 observations for all the different agents, while the JEEDS average JD only nears 9 for the Rational agent, but is between 12 and 15 for the other agent types. To give some sense of the scale of these JD values, a visualization is given in Figure 3, showing pairs of distributions and their corresponding JD.

To shed more light on where the improvement is coming from, Figure 5 separates the agents into two groups, those with more symmetric execution noise distributions and the others. There were 14% of the agents that we categorized as symmetric, with $|\sigma_{x}-\sigma_{y}|<50$ and $|\rho|<0.2$. It would make sense for JEEDS to do better on the symmetric agents, as those agents match the assumption of symmetry made by the JEEDS method. The symmetric results, shown on the top row of Figure 5, show that MCSE is competitive with and often barely outperforms JEEDS on these agents. The average JD for the both estimators is still good, converging to values below 2. The asymmetric results show that these are the cases where JEEDS really struggles and MCSE does very well, with the plots closely resembling the overall plots shown in Figure 4.

From these experiments, we conclude that the MCSE is much more effective at estimating execution skill in higher dimensions than the previous methods. It can do this consistently, even with agents who are not perfectly rational in their action selection mechanism.

We next explore the ability of MCSE to estimate execution skill as it changes over time. To do this, we made variations of the Rational and the Softmax agents, with two different ways that skill can change over time. Each require initial and final skill levels to be specified, with one agent type changing skill abruptly at a single observation, and the other changing skill gradually across all observations. Abrupt changes are made at a random point in the middle third of the observations (between 33 and 66 with 100 observations). The execution skill level for a given dynamic agent was created as follows: First, $[8.0,15.0]$ mm and $[130.0,145.0]$ mm were defined as representative ranges for agents with more accurate and less accurate execution skills, respectively. Then, two samples were drawn from each range (one for $\sigma_{x}$ and one for $\sigma_{y}$, along with a random $\rho$ value) to create the initial and final skill levels for the agent. The orders in which these were assigned varied as the agent’s skill level could progress from more accurate to less accurate or vice-versa.

MCSE again exhibits smaller errors than JEEDS at this task. The abrupt execution skill changes cause massive spikes in JD for JEEDS, from which it never completely recovers. While MCSE also has more error around the changes, it is of lower magnitude and the estimate quickly recovers afterwards. The gradual agents present more of a challenge, as the MCSE estimators reach average JD error levels of over 5. This is still less than the error of the JEEDS method. Perhaps more troubling is the fact that for the gradual agents, as the end of the observations nears, the error is ever-increasing. This is perhaps understandable, as the agent is always changing its execution skill level, and this is perhaps a greater challenge for both methods than we anticipated. Overall, MCSE shows much improvement over JEEDS at estimating dynamic skill, but there appears to still be room for improvement in the gradual changing skill case.

Experiments of MCSE with two different $w\%$ values were also performed to investigate whether the amount of noise affected the performance of the estimators on this task. Results, found in Appendix C show that the noise did not significantly affect their performance.