Behavior Pattern Recognition using A New Representation Model
Authors: Eric qiao, Peter A. Beling
ICLR 2013

Abstract: We study the use of inverse reinforcement learning (IRL) as a tool for the recognition of agents' behavior on the basis of observation of their sequential decision behavior interacting with the environment. We model the problem faced by the agents as a Markov decision process (MDP) and model the observed behavior of the agents in terms of forward planning for the MDP. We use IRL to learn reward functions and then use these reward functions as the basis for clustering or classification models. Experimental studies with GridWorld, a navigation problem, and the secretary problem, an optimal stopping problem, suggest reward vectors found from IRL can be a good basis for behavior pattern recognition problems. Empirical comparisons of our method with several existing IRL algorithms and with direct methods that use feature statistics observed in state-action space suggest it may be superior for behavior recognition problems.

arXiv:1301.3630v4  [cs.LG]  20 Mar 2013
Behavior Pattern Recognition using A New
Representation Model
Qifeng Qiao
Department of Systems Engineering
University of Virginia
Charlottesville, V A 22903
qq2r@virginia.edu
Peter A. Beling
Department of Systems Engineering
University of Virginia
Charlottesville, V A 22903
pb3a@virginia.edu
Abstract
We study the use of inverse reinforcement learning (IRL) as a tool for the recog-
nition of agents’ behavior on the basis of observation of the ir sequential decision
behavior interacting with the environment. We model the pro blem faced by the
agents as a Markov decision process (MDP) and model the obser ved behavior of
the agents in terms of forward planning for the MDP. We use IRLto learn reward
functions and then use these reward functions as the basis for clustering or classi-
ﬁcation models. Experimental studies with GridWorld, a navigation problem, and
the secretary problem, an optimal stopping problem, suggest reward vectors found
from IRL can be a good basis for behavior pattern recognition problems. Empir-
ical comparisons of our method with several existing IRL alg orithms and with
direct methods that use feature statistics observed in stat e-action space suggest it
may be superior for behavior recognition problems.
1 Introduction
The availability of sensing technologies, such as digital c ameras, global position system, infrared
sensors and others, makes the computer easily access the data recording the interaction between the
agents and the environment. The new web technology also prov ides a large amount of background
knowledge that describes the user behavior on the internet. More recent research has begun to build
the behavior recognition system using the real-world data to understand the users’ behavior.
Many approaches have been proposed to understand the agents ’ goals/plans from the observation
of the decision behavior. The entire trace of actions is to be recognized and matched against a plan
library or a set of possible goals/plans. Despite of the succ ess of these methods, they assume that
the plan library, a set of possible goals or some behavior model are known beforehand and provided
as an input. Goal information is often completely unknown inpractice, however, and so it is difﬁcult
to model goals accurately.
Consider some examples in the real-world. Human behavior co ntains more complex structure and
relations. E.g. Kautz pointed out two basic structure for be havior: decomposition and abstraction
[9]. Behavior can be decomposed into several events. For beh avior recognition, Israeli security
systems evaluate a series of events to reach a conclusion. Are they merely loitering in the area? Are
they wearing a warm coat on a hot day? When a list of behavior hi ts a certain number, the system
recognizes a potential threat. This method highly depends o n the empirical experience and hardly
recognizes the precise goal of the observed agent. To recomm end personalized advertisement, the
web companies hope to understand users’ interest by analyzi ng the web browsing history. Are
users interested in cameras, if they have booked a hotel rece ntly? There is considerable interest in
categorizing the users according to their interest, while i t is more difﬁcult to infer the precise goals
of the users. Due to the time and space limitation for adverti sement, effective identiﬁcation of the
1
user’s interest is of high importance for the companies. Another motivation for a new problem comes
from domains like high frequency trading of stocks and commo dities, where there is considerable
interest in identifying new market players and algorithms b ased on observations of trading actions,
but little hope in learning the precise strategies employed by these agents [22, 14].
In this paper, we propose a new problem, termed Behavior Pattern Recognition(BPR), that involves
recognizing agents based on observation of their behavior i n a sequential decision making setting.
Broadly, the problem is to classify or cluster the agents according to the patterns of decision behav-
ior that are learned from the samples of agents’ decision-ma king process. The recognition problem
can be framed as a classiﬁcation or clustering problem: (1) Given observations of decision trajecto-
ries consisting of sequential actions and given a label for e ach trajectory indicating which behavior
pattern that agent has, the problem is to determine the behav ior pattern for an agent with unlabeled
trajectories. (2) Given only observations of the decision trajectories, the problem is to assign trajec-
tories to clusters on the basis of similarity of behavior patterns.
A direct solution to BPR problem is to program some heuristic rules to recognize the behavior by
decomposing complex behavior into a series of simple events and then evaluating them to reach a
conclusion. However, programming the rules is hard. In cont rast to the manually coded rules, we
propose a learning model for BPR problem, characterizing the decision behavior with high level fea-
tures in terms of the underlying goals. Consider the problem of image recognition as an illustration
of behavior recognition. In that problem, a computer learnsto categorize images by representing ev-
ery image as a multi-dimensional feature vector that consists of the components such as RGB color,
texture, shape parameters or other advanced metrics. The ke y point of characterizing the behavior
is how to effectively ﬁnd a high level vector that represents the sequential behavior and encodes the
information on patterns. From the perspective of decision- making process, the underlying goal of
an agent is considered as an abstract representation of the behavior. If a decision-making process is
modeled by MDP, the reward function is assumed to encode the goal of that agent.
IRL [13] addresses the task of learning a reward function forgiven MDP that is consistent with obser-
vations of optimal decision making for the process. An assumption is that the expert’s goal/intention
can be characterized by the reward function. If the expert is rational, the demonstration behavior
should aim to maximize the long-term accumulative reward. We study the use of IRL to characterize
the decision behavior, modeling the problem faced by the agents as a MDP and assuming the reward
function of the MDP model as a high-level abstraction of the d ecision behavior. The motivation
is that even when the true behavior is not rational and we can’ t learn the precise goals/decision-
strategies, we still can categorize the agents by learning the reward functions that make MDP models
approximate the observed behavior.
IRL has received increasing attention in the machine learning ﬁeld in recent years. Most of this work
is focused on apprenticeship learning, in which IRL is used as the core method for ﬁnding decision
policies consistent with observed behavior [1, 12, 20]. A nu mber of IRL algorithms and modeling
constructs have been proposed for apprenticeship learning or imitation learning, including Max-
margin planning [16], gradient tuning methods [12], linear solvable MDP [8], bootstrap learning
[3], feature construction [11], Gaussian process IRL [15] and Bayesian inference [4].
On two well-know sequential decision-making problems, we c ompare our method with several ex-
isting IRL algorithms and with direct methods that use featu re statistics observed in state-action
space. Our main contributions include: (1) identiﬁcation o f a new learning task that categorizes
agents by learning their behavior patterns; (2) design of si mple methods to solve the BPR prob-
lem that characterize behavior in original observation space; (3) development of a new model-based
method to solve the BPR problem in MDP reward space; and (4) ob servation that our new method
using reward space provides a formal way to solve the behavio r recognition problem and performs
superior to other methods.
2 Preliminaries
We deﬁne the input of BPR problem as a tuple B = ( D1, D2, . . . D N ), where Dn, n ∈
{1, 2, . . . , N } is the observation of the n − th agent. For a classiﬁcation problem, Dn = ( On, yn),
where On is a set of observed decision trajectories and yn is the class label for the n − th agent.
2
The agents, who have the same behavior patterns, are given th e same class label. Similarly, in a
clustering problem, Dn only consists of the observed decision trajectories.
We deﬁne the set of decision trajectories On = {hj
n}, j = 1 , 2, . . . , |On|, where each trajectory hj
n
is deﬁned as a series of state and action pairs: {(s, a)t
n}, t = 1 , 2, . . . , |hj
n|. Here, the s denotes the
state for the decision problem and the a means the action selected by the agent at state s.
To determine a label for an agent, we may develop a model to decompose the observed behavior into
several events. Each event can be described by a complete or p art of a decision trajectory. When a
list of events hits a certain number, the model recognizes a label for an agent. However, this method
requires a lot of domain knowledge and human experience to program the heuristic rules.
Another way to solve BPR problem is to effectively represent the problem in a multi-dimensional
space and then apply the learning algorithms. The decision- making process can be characterized in
two layers. The outer layer characterizes the behavior by ca lculating some statistic information on
the observed state and action. The inner layer is an abstract ion of the behavior, which is related to
the goal or the internal mind of the agent that determines the behavior fundamentally.
3 Simple Representation of Behavior Recognition Problem
In this section, we describe two methods in outer layer that c ategorize the decision-making agents
just based on observation.
The ﬁrst method is called feature trajectory ( FT). Assume the length of a decision trajectory is H.
The vector to characterize the behavior in j − th decision trajectory is written as follows.
f(hj
n) = [ s1, a1, s2, a2, . . . , s H , aH ],
where si, i ∈ { 1, 2, . . . , H } is a discrete random variable meaning the state index at i − th decision
stage, and ai represents the action selected at state si. E.g., we have a problem that can be deﬁned
by 3 states and 2 actions. Then si ∈ { 1, 2, 3} and ai ∈ { 1, 2}. In the observation, every trajectory
starts from the same initial state. Given the observation se t On for n − th agent, the feature vector
fn is obtained by computing this equation: fn = 1
|On|
∑ |On|
j=1 f(hj
n), where the vector f(hj
n) is
preprocessed by scale-normalization before averaging.
Then, the n−th agent is represented by a feature vectorfn. Consider a supervised learning problem.
Given a real valued input vector fn ∈ F and a category label yn ∈ Y , we aim to learn a function
h : F → Y .
The second method is called feature expectation ( FE), which has been widely used by appren-
ticeship learning as a representation of the averaged long- term performance. Assume a basis
function φ : S → [0, 1]d, where S denotes the state space. The feature expectation fn =
1
|On|
∑ |On|
j=1
∑
st∈hj
n
γtφ(st), where γ ∈ (0, 1) is a discount factor. The associated apprentice-
ship learning algorithms aim to ﬁnd a policy that performs aswell as demonstrations by minimizing
the distance between their feature expectations. Here, we o nly use the observed state sequence to
compute the feature expectation vector for an agent, where t he γ is manually deﬁned constant, e.g.
0.95. Then, the n − th agent can be represented by the vector fn that is obtained from On.
4 A New Representation Model
To solve the BPR problem with high-level feature representa tion, we propose to use the following
steps.
1. Given the BPR problem with input B, we use the set {On}, n ∈ { 1, 2, . . . , N } to construct
the state space S and action space A for the decision-making problem.
2. For n − th observed agent, we assume an MDP model M = ( S, A, Rn, γ, P), where
Rn is the unknown reward function for this agent, γ is the constant discount factor, and
P = {Pa}a∈A is a set of transition probability matrices Pa for action a ∈ A . The entries
of Pa, written as Pa(s, s′), give the probability of transitioning to state s′ ∈ S from state
s ∈ S given the action is a. The rows of Pa, denoted Pa(s, :), give a probability vector
3
of transitioning from state s to all the states in S. The P can be modeled using prior
knowledge of the problem or estimated from the observed decision trajectories {On}. In a
ﬁnite state space the reward functionRn may be considered as a vector,rn, whose elements
give the reward in each state. Here we expect that there exists an unknown reward function
that can make the MDP ﬁnd a policy as similar as the observed behavior.
3. Apply IRL algorithms to learn the reward vector rn for n − th agent.
4. Estimate the reward vectors for every agent. Then the supe rvised learning problem is writ-
ten as: given the real valued input vector rn ∈ R and the category label yn ∈ Y , we aim to
learn a function h : R → Y .
5. Given a new observed agent, we repeat step 1-3 to get the rew ard vector for the agent and
then predict the label for the behavior pattern using estimated function h : R → Y .
In MDP model, a policy is deﬁned as a mapping π : S → A. The value function for a policy
π is V π (s0) = E[∑ ∞
t=0 γtR(st)|p(s0), π] where p(s0) is the distribution of the initial state and
the action at state st is determined by policy π. Similarly, the Q function is deﬁned as Q(s, a) =
R(s)+γ ∑
s′∈S Pa(s, s′)V π (s′). At state s, an optimal action is selected bya∗ = max a∈A Q(s, a).
An instance of the IRL problem is written as a triplet B = ( M \ r, p(r), O), where M \ r is a MDP
model without the reward function and p(r) is prior knowledge on the reward. The vector p(r) can
be a non-informative prior if we have no knowledge about the reward function or a Gaussian or other
distribution if we model the reward as a speciﬁc stochastic process.
We use an MDP to model the decision problem faced by an agent un der observation. The reality
of the agent’s decision problem and process may differ from t he MDP model, but we interpret
every observed decision of the agent as the choice of an actio n in the MDP. The dynamics of the
environment in the MDP are described by the transition probabilities P. These probabilities may be
interpreted as being a prior, if known in advance, or as an est imation of the agent’s beliefs of the
dynamics. Next, we will show how to learn the reward function s by employing some exiting IRL
algorithms.
5 Bayesian framework for IRL
Most existing IRL algorithms assume that the agents are perfectly rational and the observed behavior
is optimal. Prominent examples include the model in [13], which we term linear IRL (LIRL) because
of its linear nature, WMAL in [20], and PROJ in [1]. In these algorithms, the reward function is
written linearly in terms of features as R(s) = ∑ d
i=1 ωiφi(s) = ωT φ(s), where φ : S → [0, 1]d
and ωT = [ ω1, ω2, · · · , ωd].
Our computational framework uses Bayesian IRL to estimate t he reward vectors in a MDP, which
was initially proposed in [6]. The posterior over reward function for n − th agent is written as
p(rn|On) = p(On|rn)p(rn) ∝
|On|∏
j=1
∏
(s,a )∈hj
n
p(a|s, rn).
Then, the IRL problem is written asmaxrn log p(On|rn)+log p(rn). For many problems, however,
the computation of p(rn|On) may be complicated and some algorithms use Markov chain Mont e
Carlo (MCMC) to sample the posterior probability. Consider ing the computation complexity to
deal with a large number of IRL problems, we choose the IRL alg orithms that have well deﬁned
likelihood function to reduce the computation cost.
5.1 IRL with Boltzmann Distribution
To model the likelihood function, some IRL algorithm in [2], which we call maximum likelihood
IRL (MLIRL), uses Boltzmann distribution to calculate p(a|s, rn) using p(a|s, rn) = eQ(s,a)
∑
a∈A eQ(s,a) .
4
5.2 IRL with Gaussian Process
IRL algorithm, which is called GPIRL in [15], uses preference relations to model the likelihood
function P (On|rn) and assumes the rn is generated by Gaussian process for n − th observed agent.
Given a state, we assume that the optimal action is selected a ccording to Bellman optimality. The
preference relation is deﬁned as follows.
At state s, ∀ˆa, ˇa ∈ A , we deﬁne the
action preference relation as:
1. Action ˆa is weakly preferred to ˇa, denoted as ˆa ⪰ s ˇa, if Q(s, ˆa) ≥ Q(s, ˇa);
2. Action ˆa is strictly preferred to ˇa, denoted as ˆa ≻s ˇa, if Q(s, ˆa) > Q (s, ˇa);
3. Action ˆa is equivalent to ˇa, denoted as ˆa ∼s ˇa, if and only if ˆa ⪰ s ˇa and ˇa ⪰ s ˆa.
Given the observation set On, we have a group of preference relations at each state s, which is
written as
E ≡
{
(ˆa ≻s ˇa), ˆa ∈ ˆA, ˇa ∈ A \ ˆA
}
∪
{
(ˆa ∼s ˆa′), ˆa, ˆa′ ∈ ˆA
}
,
where ˆA ∈ A is the action subspace for state s obtained from the set On.
Let r be the vector of rn containing the reward for m possible actions at T observed states. We have
r = ( ra1 (s1), ..., ra1 (sT )  , . . . , ram (s1), . . . , ram (sT )  )
= ( ra1 , · · · , ram ),
where T = |S| and ram , ∀m ∈ { 1, 2, . . . , |A|}, denotes the reward with respect to m-th action.
Consider ram as a Gaussian process if, for any {s1, · · · , sT } ∈ S , the random variables
{ram (s1), · · · , ram (sT )} are normally distributed. We denote by kam (sc, sd) the function gen-
erating the value of entry (c, d) for covariance matrix Kam , which leads to ram ∼ N(0, Kam ).
Then the joint prior probability of the reward is a product of multivariate Gaussian, namely
p(r|S) = ∏ |A|
m=1 p(ram |S) and r ∼ N(0, K). Note that r is completely speciﬁed by the posi-
tive deﬁnite covariance matrix K.
A simple strategy is to assume that the |A| latent processes are uncorrelated. Then the covariance
matrix K is block diagonal in the covariance matrices
{
K1, ..., K|A|
}
. In practice, we use a squared
exponential kernel function, written as:
kam (sc, sd) = e
1
2 (sc−sd)Mam (sc−sd) + σ2
am δ(sc, sd),
where Mam = κam IT and IT is an identity matrix of sizeT . The function δ(sc, sd) = 1 , when sc =
sd; otherwise δ(sc, sd) = 0 . Under this deﬁnition the covariance is almost unity betwee n variables
whose inputs are very close in the Euclidean space, and decreases as their distance increases.
Then, the GPIRL algorithm estimates the reward function by iteratively con ducting the following
two main steps:
1. Get estimation of rMAP by maximizing the posteriorp(rn|On), which is equal to minimize
− log p(On|rn) − log p(rn|θ), where θ = ( κam , σam ) is the hyper-parameter controlling
the Gaussian process, and p(On|rn) = ∏ p((ˆa ≻s ˇa)) ∏ p((ˆa ∼s ˆa′)). Above optimiza-
tion problem has been proved to be convex programming in [15].
2. Find the optimized hyper-parameters by applying gradien t decent optimization method to
maximize log p(On|θ, rMAP ), which is the Laplace approximation of p(θ|On).
6 Experimentation
Our experiments are designed to evaluate the performance ofIRL algorithms in behavior recognition
in comparison to methods that use simple feature representations obtained directly from observation
space. We study two problems, GridWorld and the secretary problem. GridWorld provides insight
into the task of recognizing machine agents for decision problems that may be modeled using MDP
5
models under the strict rationality assumption. The secret ary problem provides an environment in
which the agents do not act with respect to the solution of an MDP. Agents in the secretary problem
employ heuristic decision rules derived from experimental study of human behavior in psychology
and economics.
To evaluate the recognition performance, we use the following algorithms: (1) Clustering: Kmeans
[7]; (2) Classiﬁcation: Support vector machine (SVM), K-ne arest neighbors (KNN), Fisher dis-
criminant analysis (FDA) and logistic regression (LR) [7]. We use clustering accuracy [21] and
Normalized Mutual Information (NMI) [19] to compare clustering results.
6.1 GridWorld problem
In the
GridWorld problem, which is used as a benchmark experiment by Ng and Russell in [13], an
agent starts from a given square and moves towards a destination square. The agent has ﬁve actions
to take: moving in the four cardinal directions or staying put. With probability 0.65 the agent moves
to its chosen location, with probability 0.15 it stays in thesame location regardless of chosen action,
and with probability 0.2 it moves in a random cardinal direction.
The IRL problem for GridWorld is to recover the reward structure given the observations of agent
actions. To produce these observations, we ﬁrst simulate th e agent’s behavior using the optimal
solution of an MDP to decide how to move in the GridWorld. We then collect observation data by
sampling the simulated movement. Note that the reward funct ion of the MDP used for simulating
the agents is not known to the IRL learner.
We investigated the behavior recognition problem in terms o f clustering and classiﬁcation on a
10 × 10
GridWorld problem. Experiments were conducted according to the steps in Algorithm 1.
Algorithm 1 GridWorld experimentation steps
1: Input the variables S, A and P. Design two ground truth reward functions written as r∗
1 and r∗
2 .
2: Simulate agents and sample their behavior.
3: for i = 1→ 2 do
4: for j = 1→ 200 do
5: Model an agent using M = (S, A, P, rij , γ), where the reward rij = r∗
i + random Gaussian noise.
6: Sample decision trajectories Oij , and make the ground truth labelyij = 0, if i = 1; yij = 1, if i = 2.
7: end for
8: end for
9: IRL has access to the problem B = (S, A, P, γ, Oij ) for this agent, and then infers the reward rij .
10: Recognize these agents based on the learned rij .
The simulated agents in our experiments have hybrid destinations. A small number of short decision
trajectories tends to present challenges to action featuremethods, which is an observation of particu-
lar interest. Additionally, the length of trajectories mayhave a substantial impact on performance. If
the length is so long that the observed agent reaches the destination in every trajectory, the problem
can be easily solved based on observations. Thus, we evaluate and compare performance by making
the length of decision trajectory small.
|On| FE FT PROJ GPIRL
4 0.0077 0.0012 0.0068 0.0078
8 0.0114 0.0016 0.0130 0.0932
16 0.0177 0.0014 0.0165 0.7751
20 0.0340 0.0573 0.0243 0.8113
30 0.0321 0.0273 0.0365 0.8119
40 0.0361 0.0459 0.0389 0.8123
60 0.0387 0.0467 0.0388 0.8149
80 0.0441 0.1079 0.0421 0.8095
100 0.0434 0.1277 0.0478 0.8149
200 0.0502 0.1649 0.0498 0.8149
Table 1: NMI scores for GridWorld problem
4 8 16 20 30 40 60 80 100 20040
50
60
70
80
90
100
Number of sampled decision trajectories
Clustering Accuracy
 
 
FE
FT
GPIRL
PROJ
Figure 1: Clustering accuracy
6
4 8 10 16 20 30 40 50 60 80 100 200 500 10000.4
0.5
0.6
0.7
0.8
0.9
1
Number of sampled observations
Classification Accuracy
 
 
FE
MLIRL
GPIRL
FT
PROJ Average
(a) SVM
4 8 10 16 20 30 40 50 60 80 100 200 500 10000.4
0.5
0.6
0.7
0.8
0.9
1
Number of sampled observations
Classification Accuracy
MLIRL
FE
FT
PROJ Average
GPIRL
(b) KNN
4 8 10 16 20 30 40 50 60 80 100 200 500 1000
0.5
0.55
0.6
0.65
0.7
0.8
0.9
1
Number of sampled observations
Classification Accuracy
GPIRL
FE
PROJ Average
FT
MLIRL
(c) LR
4 8 16 16 20 30 40 50 60 80 100 200 500 10000.4
0.5
0.6
0.7
0.8
0.9
1
Number of sampled observations
Classification Accuracy
GPIRL
MLIRL
FT
FE
PROJ Average
(d) FDA
Figure 2: Classiﬁcation results with respect to different classiﬁer.
Table 6.1 displays NMI scores and Figure1 shows clustering accuracy. The length of the trajectory
is limited to six steps, as we assume the observation is incomplete and the learner does not have suf-
ﬁcient information to infer the goal directly. Results are a veraged over 100 replications. Clustering
performance improves with increasing number of observatio ns. When the number of observations
is small, GPIRL method achieves high clustering accuracy and NMI scores due to the advantage of
ﬁnding more accurate reward functions that can well charact erize the decision behavior. The IRL
algorithms, such as PROJ and WMAL, are not effective in this problem because the length of the ob-
served decision trajectory is too small to provide a feature expectation that is a good approximation
to the agent’s long-term goals. Considering the utilization of feature learning algorithms to improve
the simple feature representations, we also did experiment s with PCA-based features where the
projection sub-space is spanned by those eigenvectors that correspond to the principal components
c = 10 , 20, . . . , 90 for FE and c = 2 , 4, 6, 8, 10 for FT. No signiﬁcant changes in the clustering NMI
scores and accuracy scores are observed. Therefore, we do not show the performance of PCA-based
features in Table 6.1and Figure 1.
Figure2 displays classiﬁcation accuracy for a binary class iﬁcation problem in which there are four
hundred agents coming from two groups of decision strategie s. The results are averaged over 100
replications with tenfold cross-validations. Four popular classiﬁers (SVM, KNN, FDA and LR) are
employed to evaluate the classiﬁcation performance. Resul ts suggest that the classiﬁers based on
IRL perform better than the simple methods, such as FT and FE, particularly when the number of
observed trajectories and the length of the trajectory are s mall. The results support our hypothesis
that recovered reward functions constitute an effective an d robust feature space for clustering or
classiﬁcation analysis in a behavior pattern recognition setting.
6.2 Secretary problem
The secretary problem is a sequential decision-making problem in which the binary decision to either
stop or continue a search is made on the basis of objects alrea dy seen. As suggested by the name,
7
Algorithm 2 Experimentation with Secretary Problem
1: Given a heuristic rule with a parameter h, k or ℓ.
2: Add random Gaussian noise to the parameter, which is writt en as ˆp.
3: Generate new secretary problem with X applications and let n − th agent solve these problems using this
heuristic rule with its own parameter ˆp. Save the observed decision trajectories into On.
4: Model the secretary problem in terms of an MDP consisting o f the following components:
1. State space S = {1, 2, . . . , X }, where s ∈ S means that at time s the current applicant is a
candidate.
2. Action space A consisting of two actions: reject and accept.
3. Transition probability P, computed as follows: given the reject action, the probabil ity of transi-
tioning from state si to sj , p(sj|si), is si
sj (sj − 1) if sj ≥ si, and 0 otherwise; given the accept
action, the probability of transitioning from state si to sj , p(sj |si), is 1 if si = sj , and 0 other-
wise.
4. The discount factor γ is a selected constant.
5. The reward function is unknown.
5: Infer the reward function by solving an IRL problem B = (S, A, P, γ, On).
the problem is usually cast in the context of interviewing ap plicants for a secretarial position. The
decision maker interviews a randomly-ordered sequence of a pplicants one at a time. The applicant
pool is such that the interviewer can unambiguously rank each applicant in terms of quality relative
to the others seen up to that point. After each interview, the decision maker chooses either to move
on to the next applicant, forgoing any opportunity to hire the current applicant, or to hire the current
applicant, which terminates the process. If the process goe s as far as the ﬁnal applicant, he or she
must be hired. Thus the decision maker chooses one and only on e applicant. The objective is to
maximize the probability that the accepted applicant is, in fact, the best in the pool.
To test our hypotheses on BPR, an idea experiment would invol ve recognizing individual human
decision makers on the basis of observations of hiring decisions that they make in secretary problem
simulations. Experiments with human decision making for the secretary problem are reported on in
[18, 17], but raw data consisting of decision maker action tr ajectories is not available. However, a
major conclusion of these studies is that the decisions made by the humans largely can be explained
in terms of three decision strategies, each of which uses the concept of a candidate. An applicant is
said to a candidate he or she is the best applicant seen so far. The decision strategies of interest are
the:
1. Cutoff rule (CR) with cutoff value h, in which the agent will reject the ﬁrsth − 1 applicants
and accept the next candidate;
2. Successive non-candidate counting rule (SNCCR) with parameter value k, in which the
agent will accept the ﬁrst candidate who follows k successive non-candidate applicants
since the last candidate; and
3. Candidate counting rule (CCR) with parameter value ℓ, in which the agent selects the next
candidate once ℓ candidates have been seen.
The optimal decision strategy for the secretary problem is t o use CR with a parameter that can be
computed using dynamic programming for any value of n, the number of secretaries. As n grows,
the optimal parameter converges to n/e and yields a probability of successfully choosing the best
applicant that converges to1/e. Thus only one of the three decision strategies enumerated above can
be viewed as optimal, and that only for a single parameter val ue out of the continuum of possible
values. Human actions are usually suboptimal and tend to loo k like mixtures of CR (with a non-
optimal parameter), SNCCR, and CCR [18].
As a surrogate for the action trajectories of humans, we use a gents that we generate action trajec-
tories for randomly sampled secretary problems using CR, SNCCR, and CCR. For a given decision
rule (CR, SNCCR, CCR), we simulate a group of agents that adopt this rule, differentiating individ-
uals in a group by adding Gaussian noise to the rule’s parameter. The details of the process are given
in Algorithm 2. We use IRL and observed actions to learn rewar d functions for the MDP model
given in Algorithm 2. It is critical to understand that the st ate space for this MDP model captures
nothing of the history of candidates, and as a consequence is wholly inadequate for the purposes of
8
−0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3
−0.4
−0.3
−0.2
−0.1
0
0.1
0.2
0.3
1
1
11
1
1
1
1
1
1
1 1
1
11
1
1
1 1
1
11
1 1
1
1
11
1 1
1
1
1
1
11
11
1 1
1
1
1
1
11
1
1 11111 11
11
1
1
1
1
1
11
1
1
1
11
1
1
1
1
1
1
1
1
1 1
11
1
1
11
1
1 1
11
1
1
1
1
1
1
11
1
1
2
2
2 22
2
2
2 2
2 2
2
2
2
2
2
22
2
2
2 22
2
2
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
2
2
2
222 2
2
22
2
2
2
2
22
2
2
2
2
2
22
2
2
2 2
2
2 22
2
2 2
22
2
2 2
22
2
22
2
2
2
2
2
2
2
2
2
22
2
2
2
3
3 33
33 33
3
3
3
3
3
33
3
3
3
3
3
3 3
3
3
3
33
3
3
3
3
3
3 3
3
3
3
3
3
3
33
3
3
3
3
33 3
3
3
3
3
3
3
3 333
3
3
3
3
33
3
3
3
33
33
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
 
 
cluster 1
cluster 2
cluster 3
Uncertainty
−0.1 −0.05 0 0.05 0.1 0.15
−0.06
−0.04
−0.02
0
0.02
0.04
0.06
0.08
1
11 1 1
1
1
1 111
1 1
1 1
1
1
1
1
11 11
1
11 11 1
1
1
1
111 11
1
11 1111
1
1
2
22
2
2
2
2 2
2
2
22
2
2
2
22
22
2
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
22
2
2
22
2
2
2
3
333 3
3
3
3
3
3
3
3
3
3
3
3
3
3333
3
33
333 3
3
3
3
3
3
3
3 33
33
3 3
33
33
33
3
3
3
3 3
3
3
3
3
3
33
3
3
3
3
3
3 3
33
 
 
cluster 1
cluster 2
cluster 3
Figure 3: Vectors with ground truth label projected in 2D spa ce. The feature expectation vector is
on the left and the reward vectors recovered by IRL are on the right.
−1 −0.5 0 0.5 1 1.5
−0.4
−0.3
−0.2
−0.1
0
0.1
0.2
0.3
 
 
1 (training)
1 (classified)
2 (training)
2 (classified)
Support Vectors
(a) Reward vectors projected in 2D space
−1
−0.5
0
0.5
1
1.5
−0.4
−0.2
0
0.2
0.4
−0.4
−0.3
−0.2
−0.1
0
0.1
0.2
 
2
2
2
2
2
22
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
2
222
222
2
2
2
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
2
22
2
2
2
22
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
22
2
2
2
2
2
2
22
2
2
2
2
2
2
2
2
22
22
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
22
2
2
22
222
2
2
2
2
2
2
22
2
22
2
2
2
2
22
2
22
2
2
2
2
2
22
2
2
2
22
2
2
2
2
2
22
2
22
22
2
222
2222
1
2
11
111
1
1
11
1
1
1
11
1
1
1
1111
1
1
1
1
1
1
1
11
1
1
111
1
1
11
1
1
1
111
1
1
11
11
11
1111
1111
1
11
1
1
1
1
1
111
11
11
1
1 111111
111
1
11
1
1
1
11
1
1
111
1
1
1
1
1
1
1
1
1
11
11
1
1111
1
11111
11111
1111
11
111
11 11111111
11
111111
1
1
1
111
1
1
1
1
1
111
11111111111 111111111111111111
 
DM using cutoff
DM using Random
(b) Reward vectors projected in 3D space
Figure 4: Visualization of a binary classiﬁcation problem for subjects using cutoff rule and random
rules. The PROJ IRL algorithm is used to recover the reward vectors.
modeling SNCCR and CCR. In other words, for general paramete rs, neither SNCCR nor CCR can
be expressed as a policy for the MDP in Algorithm 2. (There doe s exist an MDP in which all three
of the decision rules can be expressed as policies, but the state space for this model is exponentially
larger.) Hence, for two of the rules, the processes that we use to generate data and the processes we
use to learn are distinct.
As an initial set of experiments, we generated an equal numbe r of agents from each rule. All the
heuristic rules use the same parameter value. We have compared the method using statistical feature
representations obtained from the raw decision trajectori es and our IRL model-based method. We
employ 10 fold cross-validation to obtain the average accuracy, and it is always 100% .
Given that perfect classiﬁcation performance was achieved by all algorithms, the problem of recog-
nizing across decision rules appears to be quite easy. A more challenging problem is to recognize
variations in strategy within a single decision rule. For each rule, we conducted recognition experi-
ments in which 300 agents were simulated, 100 each for three d istinct values of the rule parameter.
Individuals were differentiated by adding random noise to the parameter. Here, we show the compar-
ison of the clustering performance between the simple method called
FE and our MDP model-based
method. In Figure3, the left ﬁgure displays an area marked “u ncertainty” for the method called FE,
while the right ﬁgure shows that the reward vectors have lower variance in the same group and higher
variance between different groups.Figure3 intuitively de monstrates that when the agents’ behavior
is represented in the reward space, the recognition problem becomes easier to solve.
Table 2 summarizes the NMI scores for using K-means clustering algorithm to recognize variations
in strategy within one heuristic decision rule. The column called H in Table 2 records the number of
decision trajectories that have been sampled for training. Table 2 proves that the feature representa-
tion in reward space is almost always better than the representation with statistical features computed
9
H CR SNCCR CCR
Action BIRL Action BIRL Action BIRL
1 0.0557 0.5497 0.0551 0.1325 0.0229 0.2081
11 0.3852 0.6893 0.2916 0.7190 0.1844 0.4974
21 0.6017 0.7898 0.4305 0.8179 0.2806 0.5181
31 0.7654 0.8483 0.5504 0.8641 0.4053 0.6171
41 0.8356 0.9676 0.5682 0.9218 0.4524 0.6533
51 0.8781 0.9739 0.5894 0.9423 0.5464 0.6507
61 0.9102 0.9913 0.5984 0.9518 0.5492 0.6513
71 0.9115 0.9915 0.6460 0.9639 0.6024 0.6512
81 0.9532 1.0000 0.6541 0.9721 0.6708 0.6563
91 0.9707 1.0000 0.6494 0.9864 0.6884 0.6544
Table 2: NMI score for Secretary Problem
from the raw observation data. Moreover, the reward space ca n particularly better characterize the
behavior when the scale of the observation data is small. Not e that though the MDP model cannot
generate the policy that is consistent with the SNCCR and CCR rules, the reward vectors learned in
the MDP environment still make the clustering problem easier to solve.
Figure4 shows a binary classiﬁcation result of using PROJ algorithm to learn the reward functions
for the agents in Secretary problem and then categorize the a gents into two groups. In this classiﬁ-
cation experiment, the users’ ground truth label is either cutoff decision rule or random strategy that
makes random decisions.
7 Conclusions
We have proposed the use of IRL to solve the problem of behavior pattern recognition. The observed
agent does not have to make decisions based on an MDP. However, we model the agent’s behavior
in an MDP environment and assume that the reward function has encoded the agent’s underlying
decision strategies. Numerical experiments on
GridWorld and the secretary problem suggest that
the advantage that IRL enjoys over action space methods is mo re pronounced when observations
are limited and incomplete. We also note that there is seems t o be a positive correlation between
the success of IRL algorithms in apprenticeship learning (cf. [15]) and their success in the behavior
recognition problem. To some degree, this relationship par allels results from [10, 5], where ap-
prenticeship learning beneﬁts from a learning structure that based on sophisticated methods for task
decomposition or hierarchical identiﬁcation of skill trees.
Validation of the ideas proposed here can come only through e xperimentation with more difﬁcult
problems. Of particular importance would be problems invol ving human decision makers or other
real-world scenarios, such as periodic investment, gambling, or stock trading.
References
[1] Pieter Abbeel and Andrew Y . Ng. Apprenticeship learning via inverse reinforcement learning.
In In Proceedings of the Twenty-ﬁrst International Conference on Machine Learning, 2004.
[2] Monica Babes-Vroman, Vukosi Marivate, Kaushik Subrama nian, and Michael Litman. Ap-
prenticeship learning about multiple intentions. In the 28th International Conference on Ma-
chine learning, W A, USA, 2011.
[3] Abdeslam Boularias and Brahim Chaib-draa. Bootstrappi ng apprenticeship learning. In Ad-
vances in Neural Information Processing Systems 24. MIT press, 2010.
[4] Jaedeug Choi and Kee-Eung Kim. Map inference for bayesia n inverse reinforcement learning.
In Advances in Neural Information Processing System, pages 1989–1997, 2011.
[5] Luis C. Cobo, Charles Lee Isbell Jr., and Andrea Lockerd T homaz. Automatic task decompo-
sition and state abstraction from demonstration. In AAMAS, pages 483–490, 2012.
[6] Ramachandran Deepak and Amir Eyal. Bayesian inverse reinforcement learning. In Proc. 20th
International Joint Conf. on Artiﬁcial Intelligence, 2007.
10
[7] Richard O. Duda, Peter E. Hart, and David G. Stork. Pattern Classiﬁcation. Wiley, 2001.
[8] Krishnamurthy Dvijotham and Emanuel Todorov. Inverse o ptimal control with linearly-
solvable mdps. In Proc. 27th International Conf. on Machine learning. ACM, 2010.
[9] H. Kautz. A Formal Theory of Plan Recognition. PhD thesis, University of Rochester, 1987.
[10] G.D. Konidaris, S.R. Kuindersma, R.A. Grupen, and A.G. Barto. Robot learning from demon-
stration by constructing skill trees.International Journal of Robotics Research, 31(3):360–375,
March 2012.
[11] Sergey Levine, Zoran Popovic, and Vladlen Koltun. Feat ure construction for inverse rein-
forcement learning. In Advances in Neural Information Processing Systems 24 . MIT press,
2010.
[12] Gergely Neu and Csaba Szepesvari. Apprenticeship learning using inverse reinforcement learn-
ing and gradient methods. In Proc. Uncertainty in Artiﬁcial Intelligence, 2007.
[13] Andrew Y . Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proc.
17th International Conf. on Machine Learning, pages 663–670. Morgan Kaufmann, 2000.
[14] Mark Paddrik, Roy Hayes, Andrew Todd, Steve Yang, Peter Beling, and William Scherer. An
agent based model of the e-mini s&p 500: Applied to ﬂash crash analysis. In 2012 IEEE
Symposium on Computational Intelligence for Financial Eng ineering and Economics (CIFEr
2012), 2012.
[15] Qifeng Qiao and Peter A. Beling. Inverse reinforcement learning via convex programming. In
Americon Control Conference, 2011.
[16] Nathan D. Ratliff, J. Andrew Bagnell, and Martin A. Zink evich. Maximum margin planning.
In In Proceedings of the 23rd International Conference on Machine Learning, 2006.
[17] Daniel Schunk and Joachim Winter. The relationship bet ween risk attitudes and heuristics
in search tasks: A laboratory experiment. Journal of Economic Behavior and Organization ,
71:347–360, 2009.
[18] Darryl A. Seale. Sequential decision making with relative ranks: An experimental investigation
of the ’secretary problem’. Organizational Behavior and Human Decision Process , 69:221–
236, March 1997.
[19] Alexander Strehl and Joydeep Ghosh. Cluster ensembles ? a knowledge reuse framework for
combining multiple partitions. Journal of Machine Learning Research, 3:583–617, 2002.
[20] Umar Syed and Robert E. Schapire. A game-theoretic appr oach to apprenticeship learning. In
Advances in Neural Information Processing Systems, pages 1449–1456. MIT Press, 2008.
[21] Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurm ans. Maximum margin clustering.
In Advanced Neural Information Process Systems, pages 1537–1544, 2005.
[22] Steve Yang, Mark Paddrik, Roy Hayes, Andrew Todd, Andre i Kirilenko, Peter Beling, and
William Scherer. Behavior based learning in identifying hi gh frequency trading strategies.
In 2012 IEEE Symposium on Computational Intelligence for Financial Engineering and Eco-
nomics (CIFEr 2012), 2012.
11


Peer review:
[Review]:
Based on the reviews, a revised version will be updated on arXiv tonight. Thanks.