Estimating a User Model with the Action Sequences in the Mind
Reading Game between a Human and a Life-like Agent(*1)Tomohiro Yamaguchi, (*1)Koji Ohnishi, (*1)Munehisa Agari, (*2)Seiji Yamada(*1) Dept. of Information Science, Nara National College of Technology
22 Yata-cho, Yamato-Koriyama city, Nara, 639-1080, Japan
yamaguch, ohnishi, agari@info.nara-k.ac.jp(*2) National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku,Tokyo, 101-8430, Japanseiji@nii.ac.jp
Abstract
This paper proposes an adaptive interaction between
a human and a life-like agent. We present the method
to estimate the partner’s context with the nth order
MDP model. In this framework, an agent plays a mind
reading game with a user in which the agent estimates
the user’s current mind state by the previous gamecontext.

I. Introduction
This paper describes an agent that identiﬁes human’s model in Human Agent Interaction (HAI, forshort). In many cases, partner’s model identiﬁcation
among their interaction is not one-way. Especially it is
two-way interaction with a human or a learning agent
that has learning ability. We call this problem as Human Agent Mutual Adaptation (HAMA, for short) in
HAI. HAMA is the situation in that a human user (auser, for short) adapts an agent both consciously andsubconsciously in the process of the agent adapts topersonalize the user, then both adapt mutually. It is
ideal in HAMA that the adaptation of them is cooperative and adequate. However, there are problems
in previous methods that inadequate adaptation of anagent aﬀects a user’s adaptation to cause a cognitive
load for the user.
To solve this, we proposed the HAMA task of amind reading game between a user and an agent. In
that, we proposed a framework that they learn eachmind mapping that represents a set of mapping froman expression to a mind in parallel [2]. Then we madethe learning experiments and discussed the conditions
without interference in both learning [1]. We foundthat the learning ability of the agent is limited andweak contrast to the learning ability of a user is ﬂexible, it is supposed that this causes one of the bottle-

neck to realize an ideal mutual adaptation. One of thelimitations of the learning ability of the agent is thatthe agent learns only a mind mapping. The agent has
the ﬁxed mind transition rules, and it can not learn
the regularity of the mind transitions of a user during
the iterated game.
Therefore, the objective of this paper is to improveadaptation ability of the agent in the iterated mind
reading game between a user and the agent. This paper presents online identiﬁcation of the model for mindtransition rules of a user to improve the guess accuracy of the game with the model. In this research, inthe process of the iterated guesses of the user’s mindby the agent, the agent identiﬁes the regularity of theuser’s mind transitions using the mind transition sequence.
The position of this research to our previous one [1]is to improve the adaptation ability and it’s accuracy
through interactions by combining the model identiﬁcation for mind transition rules in this paper with theleaning of mind mapping.

II. Identification of a user modeling ina mind reading gameA. Modeling for human agent interaction
In this section, we describe a common model forboth a user and an agent on HAI. First, we assume
that they have internal states and transition rules ofthem. An internal state is called a mind, and a rulethat transits the mind according to the situation (willbe described at Section II.c) is called a mind transition
rule. Though a mind is not directly observable, anobservable state that depends on a mind is called an
expression. A mapping from a mind to an expression

is called mind mapping [2].
Second, in this research, assumptions of the model
for partner’s identiﬁcation are as following;• Both set of minds and set of expressions are ﬁnite
and known.
• Mind mappings for each user are ﬁxed and individual.
• Mind transition rules for each user are individual.
Note that individual means the property that it isdiﬀerent for each user or agent, and is assumed tobe known of itself, and is unknown of partner’s. In
this paper, the objective is to identify mind transition
rules, and both an expression and a mind mapping are
not treated.

B. Iterated mind reading gameFirst, a mind reading game is described. The mind
reading game is a game in which when two players
share a situation, one guesses the partner’s mind before the partner tells his correct mind. Then the partner transits his mind according to the result of thegame. Fig.1 shows a procedure of the game. An iterated mind reading game is some ﬁxed number of iteration of the procedure shown in Fig.1.
In this paper, it is assumed that a situation depends on the sequence of the guess results in this game.
There are two cases on a relation of the two players ofthe mind reading game to identify other’s mind transition rules. One case is cooperative, another is competitive. This paper assumes the cooperative case.
step1 a mind transition: B transitshis mind according to a previous situation.
step2 guess: A estimates B’s current mind, then tell
it to B.
step3 judge and teach: B returns Yes or No as thejudge of A’s guess to A, then teaches B’s correct
mind to A.

transition and the mind of the partner’s guess. A guess
result for t times before is represented as rt .
Fig.3 shows an example of a simple mind transition
rule of the mind reading game. Fig.3(a) shows a rule
which represents a transition to P leased mind according to the guess r1 that corresponds to previous mindof N ormal. Fig.3(b) shows a rule which represents atransition to Confused mind according to the guess r1
in that P leased dose not correspond to previous mindof N ormal. Note that simple means that a situation
depends on not a sequence of guess results but only
previous guess result (i.e. t = 1).
Next, an example of not simple mind transition ruleis shown in Fig.3(c). In this case, the situation is thesequence of guess results r2 and r1 . This example
expresses a rule that has the input of the sequence ofguess results. After two times before guess of N ormal
mind is right and it transited to Pleased mind, thePleased mind is also the right guess, and the output
of transited Pleased mind.

C : Conf used, N : N ormal, P : P leased
Fig. 2. The relation between a symbol and a mind we used

r1 (N, N ) → P
r2 (N, P ) → C
r2 (N, N ), r1 (P, P ) → P

(a)
(b)
(c)

Fig. 3. An example of mind transition rules in the mind readinggame

D. Representation of the mind transition
rules by nth MDP model

C. Mind transition rules of the mind reading game

This section describes the modeling of mind transition rules by nth Markov decision processes (MDP, forshort) model. First, MDP model is the model which
has Markov property and which represents probabilistic state transition. It can be represented a probabilistic state transition graph which consists of a state asa node and an action as an arc.

This section describes mind transition rules usedin the mind reading game. Fig.2 shows three kinds ofminds used in this paper and symbols corresponding tothem. A mind transition rule is a rule which consistsof a sensed situation as input and a transited mind
as output. A situation for an iterated mind reading
game is a sequence of guess results of the game. A
guess result is a combination of a right mind before

Markov property (exactly, uniform simple discreteMarkov processes) is the property in that any statetransition occurs at discrete time, any state transition
probability is constant (uniformly in time) and it isable to decide only previous state transition. If thetransition probability of current state and action pairis known, next state can be estimated. Nth Markov

Fig. 1. A procedure of a mind reading gameproperty is that any state transition probability depends on only state transition sequence from current
state to n times before one. The case n = 1 is called
simple. Nth MDP model is translated into simple
MDP model if a state transition sequence from current state to n times before one is included into a state
description.
Now the modeling of a simple mind transition ruleby a simple MDP model is described. A simple mindtransition rules is modeled by a simple MDP modelthat consists of a state as a mind of itself and an action as a partner’s guess. Fig.4 shows an example ofmodeling of Fig.3(a). Note that N is N ormal, and P
is P leased.
Next, the modeling of non-simple mind transition
rule is described. In that, the input situation is a sequence of guess results. In the model, each state issegmented by a context, which is a sequence of mindtransitions from current to n times before to avoid apartially observable state. Note that in this paper, amind of a partner’s guess is not included to the context. The reason is to reduce the cost for the modeland it’s identiﬁcation instead of the accuracy of them.
This makes the identiﬁcation of a state transition fromprobabilistic by a partially observation to almost deterministic.
Fig.5 shows an example. Fig.5 is a set of mind transition rules. Note that * is a don’t care symbol. Fig.6
show the model representation of the state transitions
for Fig.5. When previous guess result is r1 (P, P ), thestate is segmented into three states as P P , N P and
CP by including two times before guess result r2 as
context. The transition that branches into N and P
probabilistically becomes diﬀerent deterministic statetransitions.

r2 (P, ∗), r1 (P, P ) → N
r2 (N, ∗), r1 (P, P ) → P
r2 (C, ∗), r1 (P, P ) → P
Fig. 5. a set of mind transition rules

PP
NP P

P

N

P

CP
Fig. 6. the model representation of the state transitions for
figure 5jective of the identiﬁcation is to guess the partner’s
a mind correctly. The goal of the model identiﬁcation
is to model the accurate and deterministic mind transition rules for a partner.
First, the identiﬁcation of a simple mind transition
rule is described. The objective of partner’s model
identiﬁcation is to perform maximum likelihood estimation of transition probabilities for all state transitions. In statistical science, it is known that a maximum likelihood estimation probability is equivalent to
the probability calculated by the frequencies. So, ina transition rule(i, a) from state i and action a, thetransition probability P (i, a, j) to state j is estimatedincrementally by the equation (1) as follows;
P (i, a, j) = N (i, a, j) / N (i, a)

N

N

P

Fig. 4. modeling a simple mind transition rule

E. identification of mind transition rules
by nth MDP model
The identiﬁcation of mind transition rules for apartner by nth MDP model is described. The ob-(1)Note that N (i, a) is the frequencies of executionof the rule(i, a), N (i, a, j) is the frequencies of thetransition to state j after executing the rule(i, a).
Next, the identiﬁcation of non-simple mind transition rule is described. Main problem is to decide aminimum length of the context. It is desirable to estimate an adequate length of the context during themodel identiﬁcation. As a heuristic method, all contexts (i.e. the complete sequence of guess results) of
the game is stored, and each state has context lengthn as a parameter (initial value is n = 1, simple). If
there is a state with a rule in which the state transition

probability is not deterministic, the context length n
is increased until each state transition probability becomes deterministic. This method is called variable
length context. Contrast to it, the method in that acontext length is ﬁxed is called fixed length context.

III. Experiment
A. The Experimental task
Using the iterated mind reading game between auser and the agent in Chapter II as a task, two experiments to perform model identiﬁcation of a user’s mindtransition rules when the agent guesses three kinds ofuser’s minds are described.
In the experiment 1, the guess strategy of the agent
is ﬁxed to random during the user’s model identiﬁcation. The objective is to evaluate the degree of theconsistency of the mind transition model of a user bycomparing the ﬁrst half of the identiﬁed model withthe latter half of one.
In the experiment 2, the guess strategy of the agent
is changed in the experiment. In the ﬁrst half of it,
the guess strategy is ﬁxed to random to perform themodel identiﬁcation of a user. In the latter half of it,
the guess strategy is changed to estimate a user’s mind
using the identiﬁed mind transition model in the ﬁrst
half if it. The objective is to evaluate the accuracyof the online model identiﬁcation by the rate of rightguess of the mind reading game.

B. The experimental method
First, the common conditions of two experiments
are described. There are ﬁve subjects consists of four
students and a teacher of our laboratory. Available
minds of each user in the experiments are three kinds
described as Fig.2 in Section II.C. The number of iterations of the game is 30, the ﬁrst half of it is ﬁfteen
and the latter half of it is ﬁfteen. Then the expected
number of the games per mind is ﬁve in each half.
The model for identiﬁcation is the MDP model with
context described in Section II.D and II.E. Next, theguess strategies of the agent used in the experiments
are described. Note that in all strategies, the model is
updated incrementally by the method in Section II.E
by using the guess result.
random strategy: It always tells a random mind inany situation. It is the simplest action selection strategy as an exploration strategy for model
identiﬁcation.
model estimation strategy: It tells a mind that has
the largest transition probability according to the

faced situation by referring the identiﬁed model.
Note that if the state is not explored yet, the random strategy is used.
Measured items are the identiﬁcation result of mindtransition rules for a user, and the number of rightguesses of the mind reading game in each ﬁrst half andlatter half of the experiment. Next, set up conditionsof each experiment are described.
B.1 the experiment 1: the evaluation of the consistency of mind transition rules for a user
The objective of the experiment is to evaluate theconsistency of mind transition rules that a user used.
Two kinds of identiﬁed models for the user with theﬁrst half of guess results and the latter half of them
are compared.
• The guess strategy of the agent is the random
strategy.
• The context length of the model is two and theﬁxed length context is used.
• The instruction to subjects is following; “Please
select and input a nearest mind you feel. “
B.2 the experiment 2: the guess with online model
identiﬁcation
The objective of the experiment is to evaluate theimprovement of the rate of right guess of the latter
half of the mind reading game. In the latter half, theestimation of the guess is performed with the user’s
model identiﬁed in the ﬁrst half of it. Additionally,questionnaires on the impressions for each subject according to the guess strategy change are performed.
• The guess strategies of the agent are in that theﬁrst half is the random strategy, and the latter
half is the model estimate strategy.
• The context length of the model is variable length
context in which the initial length is one.
• The instruction to subjects is following; “Please
select and input a nearest mind you feel. Please
cooperate with the agent that can guess yourmind accurately.“

C. The experimental results
C.1 The experiment 1: evaluating consistency of mindtransition rules of a user
Fig.7 shows the comparison of the ﬁrst half and thelatter half of identiﬁcation result of mind transition
rules of three subjects within ﬁve. Note that each displayed state transition is only the transition that has
the largest branching probability. First, mind transition rules are individual since each mind transition

rules of three is diﬀerent. Second, the mind transition
rules used and explored in the game is partial against
the whole model. The main reason is that the number of samplings of the experiment is about half of thenumber of rules in the whole model. It is only ﬁfteen
in each ﬁrst half and latter half. Contrast to it, thenumber of state transition rules is 3x3x3 = 27 under
three minds and the context length is two. Used mindtransition rules of the subject is not the same between
the ﬁrst half of the experiment and the latter half of
it. In time axis, it is partial. Third, the consistencyof the mind transition rules of each user between theﬁrst half of the experiment and the latter half of it isdescribed.

P

PP

CC

P, N

NC

PC

NN

PN

NP

CP

C

N

C
PC

P

PP

C

C

C

N, C

N, P
CC

NC

CN

NN

P

CN

PN

(a)

the first half
PP

C

CP

P

the latter half

NP

N PP

NC

PC

P

C
N

P

P

P, N
N

C

N
NN

CN

NC

CC

N
PN

NP

C
N

CC

P, N

C

CP

C

PN

P

NN

CN

(b)

the first half

the latter half

P

P

PP

C
PC

C.2 The experiment 2: evaluating the accuracy of theguess of the agent with online model identiﬁcationof a user

NP

CP

C, N

C

PC

As the result of three subjects in Fig.7, there is
no rule in that the state transition with maximum
transition probability is diﬀerent. It is supposed thatmind transition rules of a user is consistent in the experiment 1. Note that almost mind transition rules
are deterministic, so the small number of probabilistic rules reﬂects the unstableness of the regularity ofa user.

the latter half

the first half

NP

CP

CP

PP

N

P

N, P

C NP

C

C
CC

C

P

NC

PC

N, P

NC

CC

N

N, P

N
PN

C

CN

NN

PN

CN

N

NN

(c)

Fig.8 shows the number of right guesses of ﬁve subjects. It is the comparison between the ﬁrst half theexperiment and the latter half of it. In four subjects
within ﬁve, the number of right guesses is increased in
the latter half of the experiment.
The expected rate of right guess is 1/3 under the
random strategy with three minds. It is nearly equal
to the averaged rate of right guesses 5.6/15 in the ﬁrst
half of the experiment. Contrast to it, the averaged
rate of right guesses 10.8/15 in the latter half of the experiment is much greater. Therefore, in the case of thiscooperative task, it is possible to improve the accuracy
the latter half of the task with online model identiﬁcation. Next, results of the questionnaires of subjects
after the experiment 2 are summarized. One subject
C answered that intentionally he input the mind withregularity. Two subjects B and D answered that in theﬁrst half of the experiment, since the agent did not see
the user’s intention, the low rate of right guess muchannoyed the user. Additionally, D answered that in
the latter half of the experiment, he was able to cooperate with the agent since the reaction of the partner
could be expected. These impressions of the subjects

Fig. 7. modeling a simple mind transition rule

correspond to the interpretation of the experimental
results as shown in Fig.8.

IV. Conclusions
This paper presented the online identiﬁcation of
the model for mind transition rules of a user using
the mind transition sequence and its usage in the iterated mind reading game between a user and the agent.
From the result of the experiment 1, the properties ofthe mind transition rules of a user used in the game areconsistent, individual, almost deterministic and partial. From the result of the experiment 2, using online
identiﬁcation model, it is supposed that the guess accuracy can be improved without a disturbance to auser.
Future work is to introduce an adequate exploration
strategy for the model identiﬁcation. Then we havea plan to improve the adaptation ability and it’s ac-

Fig. 8. The experimental result2: Comparison between thefirst half of the number of right guesses and the latter halfof that by each subject

curacy through interactions by combining the model
identiﬁcation for mind transition rules in this paperwith the leaning of mind mapping.

References[1] T. Yamaguchi, Y. Ochi, S. Yamada “Mutual adaptationin communication between a human and a life-like agentby sharing context dependent facial expressions”, 4th AsiaPacific Conference on Simulated Evolution And Learning(Seal2002), #2192, Singapore, 2002.
[2] S. Yamada, T. Yamaguchi “Mutual Learning of Mind
Reading between a Human and a Life-like Agent”, The
5th Pacific Rim International Workshop on Multi-Agents(PRIMA-2002), K.Kuwabara and J.Lee (Eds.), pp.138-150,
Berlin, 2002.