1原著論文 Original Paper

Reinforcement Learning of Multi-Party Trading Dialog
Policies
Takuya Hiraoka

Nara Institute of Science and Technology∗1
takuya-h@is.naist.jp

Kallirroi Georgila

University of Southern California Institute for Creative Technologies

Elnaz Nouri(ditto)David Traum(ditto)Satoshi Nakamura

Nara Institute of Science and Technology

kgeorgila@ict.usc.edu
nouri@ict.usc.edu
traum@ict.usc.edu

s-nakamura@is.naist.jp

keywords: dialog policy, trading dialog, negotiation dialog, multi-party dialog, reinforcement learning
Summary
Trading dialogs are a kind of negotiation in which an exchange of ownership of items is discussed, and thesekinds of dialogs are pervasive in many situations. Recently, there has been an increasing amount of research on
applying reinforcement learning (RL) to negotiation dialog domains. However, in previous research, the focus wason negotiation dialog between two participants only, ignoring cases where negotiation takes place between more than
two interlocutors. In this paper, as a first study on multi-party negotiation, we apply RL to a multi-party trading
scenario where the dialog system (learner) trades with one, two, or three other agents. We experiment with different
RL algorithms and reward functions. We use Q-learning with linear function approximation, least-squares policy
iteration, and neural fitted Q iteration. In addition, to make the learning process more efficient, we introduce anincremental reward function. The negotiation strategy of the learner is learned through simulated dialog with trader
simulators. In our experiments, we evaluate how the performance of the learner varies depending on the RL algorithm
used and the number of traders. Furthermore, we compare the learned dialog policies with two strong hand-craftedbaseline dialog policies. Our results show that (1) even in simple multi-party trading dialog tasks, learning an effective
negotiation policy is not a straightforward task and requires a lot of experimentation; and (2) the use of neural fitted Q
iteration combined with an incremental reward function produces negotiation policies as effective or even better thanthe policies of the two strong hand-crafted baselines.

1. Introduction
Trading dialogs are a kind of interaction in which an
exchange of ownership of items is discussed, possibly resulting in an actual exchange. These kinds of dialogs arepervasive in many situations, such as marketplaces, business deals, school lunchrooms, and some kinds of games,
like Monopoly or Settlers of Catan [Guhe 12]. Most ofthese dialogs are non-cooperative [Asher 13, Traum 08],in the sense that mere recognition of the desire for one
party to engage in a trade does not provide sufficient inducement for the other party to accept the trade. Usually a∗1 Currently the first author (Takuya Hiraoka) is working at the Nippon Electric Company. This work was done while he was a Ph.D.
student at the Nara Institute of Science and Technology, and a visiting researcher at the University of Southern California Institute forCreative Technologies.

trade will only be accepted if it is in the perceived interestof each party. Trading dialogs can be considered as a kindof negotiation, in which participants use various tactics totry to reach an agreement. It is common to have dialogs
that may involve multiple offers or even multiple trades.
In this way, trading dialogs are different from other sortsof negotiation in which a single decision (possibly about
multiple issues) is considered, for example partitioning
a set of items [Georgila 14, Nouri 13]. Another difference between trading dialogs and partitioning dialogs iswhat happens when a deal is not made. In partitioning
dialogs, if an agreement is not reached, then participants
get nothing, so there is a very strong incentive to reach adeal, which allows pressure and can result in a “chickengame”, where people give up value in order to avoid a total loss. By contrast, in trading dialogs, if no deal is made,2participants stick with the status quo. Competitive twoparty trading dialogs may result in a kind of stasis, where
the wealthier party will pass up mutually beneficial deals,
in order to maintain primacy. On the other hand, multiparty trading dialogs involving more than two participantschanges the dynamic again, because now a single participant cannot necessarily even block another from acquiringa missing resource, because it might be available throughtrades with a third party. A player who does not engage indeals may lose relative position, if the other participants
make mutually beneficial deals.
The main goal of our research is to build dialog systems
that can negotiate and trade with humans or other agentsin the real or virtual world. Imagine a dialog system performing the role of a human in online auctions or marketplaces. In such situations, the system should be able tonegotiate with other participants with different values of
items; some of these participants may have goals similar
to the goals of the system (collaborative), and some may
have goals that compete with the system’s goals (competitive). In order for the dialog system to be successful in
trading and to decide on the right action in a particular
context, it needs to have a strong dialog policy.
In this paper, we present a first approach toward learning dialog policies for multi-party trading dialogs. We introduce a simple, but flexible game-like scenario, where
items can have different values for different participants,
and also where the value of an item can depend on otheritems held. We examine a number of strategies for thisgame, including random, simple, and complex hand-crafted
strategies, as well as several reinforcement learning (RL)
[Sutton 98] algorithms, and examine performance withdifferent numbers and kinds of opponents.
In most of the previous work on statistical dialog management, RL was applied to cooperative slot-filling dialog
domains. For example, RL was used to learn the policies
of dialog systems for food ordering [Williams 07a], tourist
information [Williams 07b], flight information [Levin 00],
appointment scheduling [Georgila 10], and e-mail access[Walker 00]. In these typical slot-filling dialog systems,
the reward function depends on whether the user’s goal has
been accomplished or not. For example, in the food ordering system presented by Williams and Young [Williams
07a], the dialog system earns higher rewards when it succeeds in taking the order from the user.
Recently, there has been an increasing amount of research on applying RL to negotiation dialog domains, which
are generally more complex than slot-filling dialog because the system needs to consider its own goal as wellas the user’s goal, and may need to keep track of more

人工知能学会論文誌 31 巻 4 号 B（2016 年）

information, e.g., what has been accepted or rejected sofar, proposals and arguments on the table, etc. Georgila
and Traum [Georgila 11] applied RL to the problem oflearning negotiation dialog system policies for different
cultural norms (individualists, collectivists, and altruists).
The domain was negotiation between a florist and a grocer who had to agree on the temperature of a shared retail space. Georgila [Georgila 13] used RL to learn the
dialog system policy in a two-issue negotiation domain
where two participants (the user and the system) organize a party, and need to decide on both the day that the
party will take place and the type of food that will beserved. Then Papangelis and Georgila [Papangelis 15]
extended this work and learned dialog policies in a fourissue negotiation scenario. Also, Heeman [Heeman 09]
modeled negotiation dialog for a furniture layout task, andParuchuri et al. [Paruchuri 09] modeled negotiation dialog
between a seller and a buyer. Efstathiou and Lemon [Efstathiou 14] focused on non-cooperative aspects of trading
dialog, and Georgila et al. [Georgila 14] used multi-agent
RL to learn negotiation policies in a resource allocation
scenario. Finally, Hiraoka et al. [Hiraoka 14] applied RL
to the problem of learning cooperative persuasive policies
using framing, and Nouri et al. [Nouri 12] learned models for cultural decision-making in a simple negotiation
game (the Ultimatum Game). In contrast to typical slotfilling dialog systems, in these negotiation dialogs, the dialog system is rewarded based on the achievement of its
own goals rather than those of its interlocutor. For example, in Georgila [Georgila 13], the dialog system gets ahigher reward when its party plan is accepted by the otherparticipant.
Note that in all of the previous work mentioned above,
the focus was on negotiation dialog between two participants only, ignoring cases where negotiation takes place
between more than two interlocutors. However, in the realworld, multi-party negotiation is quite common. In thispaper, as a first study on multi-party negotiation, we apply RL to a multi-party trading scenario where the dialog system (learner) trades with one, two, or three otheragents. We experiment with different RL algorithms andreward functions. The negotiation strategy of the learneris learned through simulated dialog with trader simulators.
In our experiments, we evaluate how the performance ofthe learner varies depending on the RL algorithm used andthe number of traders. To the best of our knowledge thisis the first study that applies RL to multi-party (more than
two participants) negotiation dialog management. We are
not aware of any previous research on dialog using RL to3

Reinforcement Learning of Multi-Party Trading Dialog Policies

learn the system’s policy in multi-party negotiation.∗2
Our paper is structured as follows. Chapter 2 provides
an introduction to RL. Chapter 3 describes our multi-party
trading domain. Chapter 4 describes the dialog state andset of actions for both the learner and the trader simulators,
as well as the reward functions of the learner and the handcrafted policies of the trader simulators. In Chapter 5, we
present our evaluation methodology and results. Finally,
Chapter 6 summarizes the paper and proposes future work.

2. Reinforcement Learning
Reinforcement learning (RL) is a machine learning technique for learning the policy of an agent that takes someaction to maximize a reward (not only immediate but also
long-term or delayed reward). In this section, we briefly
describe RL in the context of dialog management. In dialog, the policy is a mapping function from a dialog state
to a particular system action. In RL, the policy’s goal is
to maximize a reward function, which in traditional taskbased dialog systems is user satisfaction or task completion [Jokinen 09]. RL is applied to dialog modeling in theframework of Markov decision processes (MDPs) or partially observable Markov decision processes (POMDPs).
In this paper, we follow an MDP-based approach. An
MDP is defined as a tuple ⟨S, A, P, R, γ⟩ where S is the setof states (representing different contexts) which the system may be in (the system’s world), A is the set of actionsof the system, P : S × A → P (S, A) is the set of transition
probabilities between states after taking an action, R : S ×
A → ℜ is the reward function, and γ ∈ [0, 1] a discountfactor weighting long-term rewards. At any given time
step i the world is in some state si ∈ S. When the system
performs an action αi ∈ A following a policy π : S → A,
it receives a reward ri (si , αi ) ∈ ℜ and transitions to statesi+1 according to P (si+1 |si , αi ) ∈ P . The quality of thepolicy π followed by the agent is measured by the expected
future reward, also called Q-function, Qπ : S × A → ℜ.
We experiment with 3 different RL algorithms:
LinQ: This is the basic Q-learning algorithm with linear
function approximation [Sutton 98]. The Q-function∗2 Note that there is some previous work on using RL to learn negotiation policies among more than two participants. For example, Mayya et al. [Mayya 11] and Zou et al. [Zou 14] used multiagent RL to learn the negotiation policies of sellers and buyers ina marketplace. Moreover, Pfeiffer [Pfeiffer 04] used RL to learn
policies for board games where sometimes negotiation takes place
among players. However, these works did not focus on negotiation
dialog (i.e., exchange of dialog acts, such as offers and responses
to offers), but only focused on specific problems of marketing or
board games. For example, in Zou et al. [Zou 14]’s work, RL wasused to learn policies for setting selling/purchasing prices in orderto achieve good payoffs.

is a weighted function of state-action features. It is
updated whenever the system performs an action andgets a reward for that action (in contrast to batch RL
mentioned below).
LSPI: In least-squares policy iteration (LSPI), the Qfunction is also approximated by a linear function (similarly to LinQ). However, unlike LinQ, LSPI is a batchlearning method. It samples the training data one
or more times (batches) using a fixed system policy(the policy that has been learned so far), and the approximated Q-function is updated after each batch.
We use LSPI because it has been shown to achieve
higher performance than LinQ in tasks where states
are represented as multidimensional vectors, such as
the problem of riding a bicycle [Lagoudakis 03]. In
our domain, the agents have to keep track of information about multiple traders, and this informationis encoded into a multidimensional vector that represents the dialog state (see Section 4·1). Therefore we
expect LSPI to work better than LinQ in our domain
as well.
NFQ: Neural fitted Q iteration (NFQ) uses a multi-layered
perceptron as the Q-function approximator. Like LSPI,
NFQ is a batch learning method. We introduce NFQ
because it has been shown to perform well in sometasks [Riedmiller 05]. One such task is robot soccer[Riedmiller 09], where the state is represented as amultidimensional vector with a size larger than that of
the bicycle problem where LSPI is successful. In ourdomain, as the number of traders increases, the sizeof the vector that represents the state becomes larger
too. Therefore we expect NFQ to achieve better performance in trading domains with many traders.
During training we use ϵ-greedy exploration, i.e., thesystem randomly selects an action with a probability ofϵ (we used a value of 0.1 for ϵ) otherwise it selects theaction which maximizes the Q-function given the current
state. During testing there is no exploration and the policy
is dictated by the Q-values learned during training.

3. Multi-Party Trading Domain
Our domain is trading, where two or more traders havea number of items that they can keep or exchange withthe other traders in order to achieve their goals. The valueof each item for a trader is dictated by the trader’s payoff matrix. So at the end of the interaction each trader
earns a number of points based on the items that it holds
and the value of each item. Note that each trader has its
own payoff matrix. During the interaction, each trader can人工知能学会論文誌 31 巻 4 号 B（2016 年）

4

trade an item with the other traders (i.e., offer an item inexchange for another item). If the addressee of the offer
accepts it, then the items of the traders involved in this exchange are updated. If the offer is not accepted, the dialog
proceeds without any changes in the number of items thateach trader possesses. To make the search space of possible optimal trading policies more tractable, we assume
that (1) each trader can only trade one item at a time, (2)only one trader is allowed to take the turn (decide to trade)at a time, and (3) each offer is addressed only to one othertrader. Each trader can take the turn in random order, unless there is a pending offer. That is, if a trader makes anoffer to another trader, then the addressee of that offer haspriority to take the next turn; the addressee can decide toaccept the offer, or to do nothing, or to make a different
offer. Note that the traders do not know each other’s payoff matrices but they know the items that each trader owns.
The dialog is completed after a fixed period of time passes
or when all traders decide not to make any offers.
In our experiments, there are three types of items: apple,orange, and grape, and each trader may like, hate, or feelneutral about each type of fruit. At the end of the dialog
the trader earns 100 points for each fruit that he likes, 0
points for each fruit that he is neutral to, and –100 points
for each fruit that he hates. Payoff matrices are structured
such that there is always one fruit that each trader likes,
one fruit that he is neutral to, and one fruit that he hates.
Furthermore, all traders can get a big payoff for having
a fruit salad, i.e., the trader earns 500 additional points if
he ends up with one fruit of each type. Thus even hated
fruits may sometimes be beneficial, but only if they can bepart of a fruit salad. Thus the outcome for a trader otr is
calculated by Equation (1).

+ P ay(orangetr ) ∗ N um(orangetr )+ P ay(grapetr ) ∗ N um(grapetr )


500






P ay(saladtr ) =






0

(1)

if N um(appletr ) ≥ 1
and N um(orangetr ) ≥ 1
and N um(grapetr ) ≥ 1

4. Methodology for Learning Multi-Party Negotiation Policies
In this chapter, we present our methodology for training
the learner, including how we built our trader simulators.
The trader simulators are used as negotiation partners of
the learner for both training and evaluating the learner’s
policy (see Chapter 5).
4·1 Learner’s Model
Below we define the reward function, sets of actions,and state of our MDP-based learner’s model. Note that we
use two kinds of rewards.
The first type of reward is based on Equation (3). In thiscase, the learner is rewarded based on its outcome only atthe end of the dialog. In all other dialog turns i its reward
is 0.

rend =

otr = P ay(appletr ) ∗ N um(appletr )+ P ay(saladtr )fruit type and payoff matrix) of the traders (except for thelearner) are randomly assigned. The learner always has
the same payoff matrix for all dialogs, i.e., the learner always likes grape, always feels neutral about apple, andalways hates orange. Also, the total number of fruits thatthe learner holds in the beginning of the dialog is always
3. However, the number of each fruit type that the learnerholds is randomly initialized for each dialog, e.g., the learner
could be initialized with (1 apple, 2 oranges, 0 grapes), or(1 apple, 1 orange, 1 grape), etc. The total number of fruits
for each trader is determined based on his role (Rich: 4
items, Middle: 3 items, Poor: 2 items), which is also randomly assigned at the beginning of each dialog. Table 1
shows two example dialogs.

(2)

otherwise

where P ay is a function which takes as argument a fruit
type and returns the value of that fruit type for the trader,and N um shows the number of items of a particular fruit
type that the trader possesses. At the beginning of eachdialog, the initial conditions (i.e., number of items per


o

tr

0

if dialog ends

(3)

otherwise

We also introduce an incremental reward for training,
because rewarding a learning agent only at the end of the
dialog makes the learning problem very difficult, thus subgoals can be utilized to reward the learning agent incrementally [McGovern 01]. The incremental reward at turni is given by Equation (4), where otr (i) is the outcome fora trader applied at time point i.
 γ ∗ o (i) − o (i − 1) if i > 0
′
tr
tr
ri =
(4)
0
if i = 0This equation represents the improvement on the outcomeof the learner at turn i compared to its outcome at the previous turn i − 1. Note that this implementation of the incremental reward function is basically the same as reward

5

Reinforcement Learning of Multi-Party Trading Dialog Policies
Table 1 Examples of two trading dialogs among traders TR1, TR2, and TR3. In these examples, the payoff matrix of
TR1 is (apple: –100, orange: 100, grape: 0), that of TR2 is (apple: –100, orange: 0, grape: 100), and that of
TR3 is (apple: 0, orange: –100, grape: 100). Item and Outcome show the number of items per fruit type of eachtrader and the points that each trader has accumulated after an action. A stands for apple, O for orange, and G
for grape.

Item
Speaker
Dialog 1:
1: TR1
2: TR2
Dialog 2:
1: TR2
2: TR1
3: TR3
4: TR2

OutcomeTR2 TR3

Utterance

TR1

TR2

TR3

TR1

TR2, could you give me an orange?
I’ll give you a grape. (Offer)Okay. (Accept)

A: 0, O: 0, G: 3

A: 1, O: 1, G: 0

A: 0, O: 1, G: 2

0

–100

100

A: 0, O: 1, G: 2

A: 1, O: 0, G: 1

A: 0, O: 1, G: 2

100

0

100

TR1, could you give me a grape?
I’ll give you an apple. (Offer)
I want to keep my fruits. (Keep)
TR2, could you give me an apple?
I’ll give you a grape. (Offer)Okay. (Accept)

A: 0, O: 0, G: 3

A: 1, O: 1, G: 0

A: 0, O: 1, G: 2

0

–100

100

A: 0, O: 0, G: 3
A: 0, O: 0, G: 3

A: 1, O: 1, G: 0
A: 1, O: 1, G: 0

A: 0, O: 1, G: 2
A: 0, O: 1, G: 2

0
0

–100
–100

100
100

A: 0, O: 0, G: 3

A: 0, O: 1, G: 1

A: 1, O: 1, G: 1

0

100

500

shaping, and has the following property [Ng 99, El Asri13]: the policy learned by using Equation (4) maximizes
the expectation of the cumulative reward given by Equation (3).
The learner’s actions are presented below. By speaker
we mean the trader who is performing the action. In thiscase, the speaker is the learner, but as we will see below
this is also the set of actions that a trader simulator canperform.
Offer(A, Is , Ia ): offering addressee A to trade the speaker’s
item Is for the addressee’s item Ia .
Accept: accepting the most recent offer addressed to the
speaker.
Keep: passing the turn without doing anything. If there
is a pending offer addressed to the speaker, then thisoffer is rejected.
The dialog state consists of the offered table and the distribution of the items among the negotiators:
Offered table: The offered table consists of all possible tuples (Trading partner, Fruit requested, Fruit offered in return). If another agent makes an offer tothe learner then the learner’s offered table is updated.
The dialog state is represented by binary variables (orfeatures). In Example 1, we can see a dialog state ina 2-party dialog, after the learner receives an offer togive an orange and in return take an apple.
Number of items: The number of items for each fruit
type that each negotiator possesses. Once a trade isperformed, this part of the dialog state is updated in
the dialog states of all agents involved in this trade.
Thus the learner’s state is represented as a multidimensional vector that consists of (1) binary values representing
the offered table, and (2) integer values representing thenumber of items. To simplify the model, the state does notinclude information about previous actions of the traders.

4·2 Trader Simulator
In order to train the learner we need trader simulators togenerate a variety of trading episodes, so that in the end thelearner learns to follow actions that lead to high rewards
and avoid actions that lead to penalties. The trader simulator has the same dialog state and actions as the learner. We
have as many trader simulators as traders that the learner
negotiates with. Thus in a 3-party negotiation we have 2
trader simulators. The policy of the trader simulator canbe either hand-crafted, designed to maximize the reward
function given by Equation (3); or random.
The hand-crafted policy is based on planning. Moreconcretely, this policy selects an action based on the following steps:(1) Pre-compute all possible sets of items (called “hands”,
by analogy with card games, where each item is represented by a card), given the role of the trader (Rich,
Middle, Poor) and how many items there can be in
the hand.
(2) Compute the valuation of each of the hands, according to the payoff matrix.
(3) Based on the possible trades with the other agents,
compute a set of achievable hands, and order themaccording to the valuations defined in step 2. A handis “achievable” if there are enough of the right types
of items in the deal. For example, if the hand is 4
apples, and there are only 3 apples in the deal, thenthis hand is not achievable.
(4) Remove all hands that have a lower valuation than

人工知能学会論文誌 31 巻 4 号 B（2016 年）

6
Example1 Status of the learner’s dialog state’s features in a 2-party trading dialog (learner vs. Agent 1). Agent 1 has
just offered the learner 1 apple for 1 of the learner’s 2 oranges (but the learner has not accepted or rejected
the offer yet). This is why the (Agent 1, orange, apple) tuple has value 1. Initially the learner has (0 apples,2 oranges, 1 grape) and Agent 1 has (1 apple, 0 oranges, 1 grape). Note that if we had more negotiators e.g.,
Agent 2, the dialog state would include features for offer tuples for Agent 2, and the number of items that
Agent 2 possessed.

Trading
partner

Item requested
by partner

Item givenby partner
to learner

Occurrence
binary value(used as feature)

Agent 1

apple
apple
orangeorangegrape
grape

orange
grape
apple
grape
apple
orange

0
0
1
0
0
0

Agent who
possesses fruits
learner

Agent 1

Fruit type

Number of fruits(used as feature)apple
orangegrape
apple
orange
grape

0
2
1
1
0
1


the current hand. The remaining set is the set of achievable goals.
(5) Calculate a set of plans for each achievable goal. A
plan is a sequence of trades (one item in hand for one
item out of hand) that will lead to the goal. There aremany possible plans for each goal. For simplicity, we
ignore any plans that involve cycles, where the same
hand appears more than once.
(6) Calculate the expected utility (outcome) of each plan.
Each plan will have a probability distribution of outcomes, based on the probability that each trade is successful. The outcome will be the hand that resultsfrom the end state, or the state before the trade thatfails. For example, suppose the simulator’s hand is(apple, apple, orange), and the simulator’s plan is(apple→orange, orange→grape). The three possible
outcomes are:(apple, orange, grape) (i.e., if the plan succeeds) the probability is calculated as P (t1) ∗ P (t2).
(apple, orange, orange) (i.e., if the first trade succeeds
and the second fails) the probability is calculated
as P (t1) ∗ (1 − P (t2)).
(apple, apple, orange) (i.e., if the first trade fails) the
probability is calculated as 1 − P (t1).
Therefore, the simulator can calculate the expectedutility of each plan, by multiplying the probabilityof each trade with the valuation of each hand fromstep 2. We set the probability of success of each trade
to 0.5 (i.e., uninformative probability). This value of
probability represents the fact that the simulator does
not know a priori whether the trade will succeed ornot.
(7) Select the plan which has the highest expected utility as the plan that the policy will follow.
(8) Select an action implementing the plan that waschosen in the previous step, as follows: if the plan iscompleted (i.e., the simulator reached the goal), thepolicy will select Keep as an action. If the plan is notcompleted and there is a pending offer which will allow the plan to move forward, the policy will selectAccept as an action. Otherwise, the policy will select Offer as an action. The addressee of the offer israndomly selected from the traders holding the item
which is required for moving the plan forward. The
pseudocode of this step is shown in Algorithm 1.
In addition to the above hand-crafted trader simulator’s
policy, we also use a random policy.

5. Evaluation
In this chapter, we evaluate the learner’s policies learned
with (1) different algorithms i.e., LinQ, LSPI, and NFQ(see Chapter 2), (2) different reward functions i.e., Equations (3) and (4) (see Section 4·1), and (3) different numbers of traders.∗3
The evaluation is performed in trading dialogs with different numbers of participants (from 2 players to 4 players), and different trader simulator’s policies (hand-crafted
policy or random policy as presented in Section 4·2). Morespecifically, there are 9 different setups:
H: 2-party dialog, where the trader simulator follows ahand-crafted policy.
R: 2-party dialog, where the trader simulator follows arandom policy.
HxH: 3-party dialog, where both trader simulators follow hand-crafted policies.
∗3 Source files to replicate these experiments are available at:https://github.com/TakuyaHiraoka/
Reinforcement-Learning-in-Multi-PartyTrading-Dialog

Reinforcement Learning of Multi-Party Trading Dialog Policies

7

Algorithm 1 Action selection of the hand-crafted policy
Require: The following variables are given:(1) Index of the trader i.
(2) Set of other traders T −i .
(3) Trader’s plan P = [[Ig0 , Ir0 ], ..., [Igj , Irj ], ...], where
Igj represents the item that the trader will give in thejth trade, and Irj represents the item that the trader
will receive in return in the jth trade.
(4) Offered table O that returns a binary value according to the given tuple (Trading partner, Fruit requested, Fruit offered in return).
(5) Number of items N that returns an integer value
according to the given tuple (Trader, Fruit).
(6) Set of possible addressees A for the first trade of
the plan.
1: if P = ϕ then2:
return Keep
3: end if
4: for t ∈ T −i do5:
if O[(t, Ig0 , Ir0 )] == 1 then6:
return Accept
7:
end if
8: end for
9: A ← {}10: for t ∈ T −i do11:
if N [(t, Ir0 )] >= 1 then12:
A ← t∪A13:
end if
14: end for
15: randomly select an addressee of an offer a from A
16: return Offer(a, Ig0 , Ir0 )Random: weak baseline which randomly selects one action from all possible valid actions.
LinQ-End: learned policy using LinQ and reward given
at the end of the dialog.
LSPI-End: learned policy using LSPI and reward given
at the end of the dialog.
NFQ-End: learned policy using NFQ and reward given
at the end of the dialog.
LinQ-Incr: learned policy using LinQ and an incremental reward.
LSPI-Incr: learned policy using LSPI and an incremental reward.
NFQ-Incr: learned policy using NFQ and an incremental reward.
Handcraft1: strong baseline following the hand-crafted
policy presented in Section 4·2.
Handcraft2: strong baseline similar to Handcraft1 except the plan is randomly selected from the set ofplans produced by step 6, rather than picking only thehighest utility one (see Section 4·2).

HxR: 3-party dialog, where one trader simulator follows
a hand-crafted policy and the other one follows a random policy.
RxR: 3-party dialog, where both trader simulators follow random policies.
HxHxH: 4-party dialog, where all three trader simulators follow hand-crafted policies.
HxHxR: 4-party dialog, where two trader simulators follow hand-crafted policies and the other one follows arandom policy.
HxRxR: 4-party dialog, where one trader simulator follows a hand-crafted policy and the other ones follow
random policies.
RxRxR: 4-party dialog, where all three trader simulators follow random policies.
There are also 9 different learner policies:
AlwaysKeep: weak baseline which always passes theturn.

We use the Pybrain library [Schaul 10] for the RL algorithms LinQ, LSPI, and NFQ. The learning parameters
follow the default Pybrain settings except for the discountfactor γ; we set the discount factor γ to 1. We consider
2000 dialogs as one epoch, and learning is finished when
the number of epochs becomes 200 (400000 dialogs). The
policy at the epoch where the average reward reaches its
highest value is used in the evaluation.
We evaluate the learner’s policy against trader simulators. We calculate the average reward of the learner’s policy in 20000 dialogs. Furthermore, we show how fast thelearned policies converge as a function of the number of
epochs in training.
In terms of comparing the average rewards of policies(see Figure 1), NFQ-Incr achieves the best performancein almost every situation. In 2-party trading, the performance of NFQ-Incr is almost the same as that of Handcraft2 which achieves the best score, and better than theperformance of Handcraft1. In both 3-party and 4-party
trading, the performance of NFQ-Incr is better than that of
the two strong baselines, and achieves the best score. In
contrast to NFQ-Incr, the performance of the other learned
policies is much worse than that of the two strong baselines. As the number of trader simulators who follow arandom policy increases, the difference in performance
between NFQ-Incr and the other learned policies tends toalso increase. One reason is that, as the number of trader
simulators who follow a random policy increases, the variability of dialog flow also increases. Trader simulatorsthat follow a hand-crafted policy behave more strictly than

人工知能学会論文誌 31 巻 4 号 B（2016 年）

8

trader simulators that follow a random policy. For example, if the trader simulator following a hand-crafted policy
reaches its goal, then there is nothing else to do except for
Keep. In contrast, if a trader simulator following a random
policy reaches its goal, there is still a chance that it will
make an offer which will be beneficial to the learner. As aresult there are more chances for the learner to gain better
outcomes, when the complexity of the dialog is higher. In
summary, our results show that combining NFQ with anincremental reward produces the best results.
Moreover, the learning curve in 2-party trading (Figure 2) indicates that, basically, only the NFQ-Incr achieves
stable learning. NFQ-Incr reaches its best performancefrom epoch 140 to epoch 190. On the other hand, LSPI
somehow converges fast, but its performance is not sohigh. Moreover, LinQ converges in the first epoch, but
it performs the worst.
Note that the above results depend on the experimental
setup, especially the properties of the trader simulators. If
different types of simulators had been used then the experimental results might have been different.
Table 2 shows the average number (per dialog) of eachone of the learner’s actions (Offer, Accept, Keep). It also
shows the average number of the offers of the learner thatare accepted by the other traders, the average number of
all actions performed by the learner, and the average number of all turns (all actions performed by all traders), perdialog, over 20000 dialogs in the 3-party situation. First,
for each policy, we focus on the distribution of each one of
its actions in HxH, and we can see that the average number of NFQ-Incr’s “Accepted offers” is 0.350, which is thehighest among all policies (except for the random policy).
This result indicates that when NFQ-Incr trades with opponents (trader simulators) that follow hand-crafted policies, it makes appropriate offers that consider its opponents’ needs (or plans). The hand-crafted trader simulators always accept reasonable offers that are required forproceeding with their plans. NFQ-Incr has learned to exploit this property of the hand-crafted trader simulators inorder to achieve better outcomes. Next, we focus on the
distribution of each one of NFQ-Incr’s actions in dialogs
with trader simulators that follow a random policy. From
Table 2, we can see that, as the number of trader simulatorsthat follow a random policy increases, the average number
of NFQ-Incr’s “Accept” actions also increases. The average number of NFQ-Incr’s “Accept” actions in HxH is0.001, but it becomes 0.329 in HxR and 0.775 in RxR.
This shows that trader simulators that follow random policies tend to offer trades profitable to the learner, and NFQIncr learns to exploit this property in order to achieve bet-

ter outcomes.
It is interesting that, even in this simple trading domain,
applying RL does not always produce good policies. Without the incremental reward of Equation (4), all the RL algorithms that we use fail to learn policies comparable to or
better than the two strong baselines (Figure 1). Even when
the incremental reward is used, our RL algorithms (except
for NFQ) fail to learn successful policies. This shows thatour domain is quite complex, and certainly not easier thanother domains to which RL has been successfully appliedso far, e.g., slot-filling.
To measure the validity and portability of our learned
policies, we perform additional experiments in which thetrader simulators follow different policies in the training
and evaluation phases:
H’xH’: the learner’s policy is learned in HxH, but thelearned policy is evaluated in 3-party dialog where
both trader simulators follow Handcraft2.
H’xR: the learner’s policy is learned in HxR, but thelearned policy is evaluated in 3-party dialog where
one trader simulator follows Handcraft2 and the otherone follows a random policy.
Below we discuss our evaluation results (Figure 3, Table 3,
and Figure 4), with regard to the validity and portability of
our learned policies (especially NFQ-Incr).
Validity: In Figure 3, we can see that, in contrast to theexperimental result shown in Figure 1, NFQ-Incr performs slightly worse than the two strong baselines.
One reason for this is that NFQ-Incr is learned against
trader simulators following Handcraft1, and thus theselearned policies could be overfitted to these trader simulators. NFQ-Incr is very conservative while interacting with other trader simulators in HxH. NFQ-Incrdoes not accept most of the offers of the trader simulators (Table 2), but it works better than the twostrong baselines in this setting (Figure 1). In contrast, in H’xH’ the two strong baselines that accept
more offers from the other simulators than NFQ-Incr(Table 3), achieve better performance than NFQ-Incr(Figure 3). This shows that a conservative strategy
works better against Handcraft1 than Handcraft2. To
avoid such overfitting and produce policies that canperform well in various trading domains, learning shouldbe performed against trader simulators that follow avariety of policies.
Portability: Although NQF-Incr does not outperform thetwo strong baselines in H’xH’ and H’xR, it performs
much better than the weak baselines (Figure 3). Therefore, if the learner is required to adapt to a new trading
situation, we can potentially use the policy learned

9

Reinforcement Learning of Multi-Party Trading Dialog Policies

Fig. 1 Comparison of RL algorithms and types of reward functions. The upper figure corresponds to 2-party dialog, themiddle figure to 3-party dialog, and the lower figure to 4-party dialog. In these figures, the performances of thepolicies are evaluated by using the reward function given by Equation (3).

with NFQ-Incr as an initial policy of the learner. We
perform a preliminary experiment to evaluate the effect of transferring a learned policy to a new domain,which results in faster convergence during learningand policies that are as good or even better than Handcraft1 (Figure 4).
In our experiments, we focus on trading dialogs amonga small number of traders, and thus we do not need to apply scaling approaches to the state/action space of eachtrader. However, as the number of traders increases, thestate/action space of each trader can become large and intractable. It is possible that a large state space includes
redundant information. In such a case, to scale the state
space to a tractable size, it makes sense to consider only
important information. For example, in our trading domain, if we know that a trader can perform well based
only on information about (1) the current offer (i.e., what
fruit is requested and what fruit is offered in return), and人工知能学会論文誌 31 巻 4 号 B（2016 年）

10

Fig. 2 Number of epochs vs. performance of learned policies in 3-party trading. The upper figure shows the performance
when the reward is given by Equation (3). The lower figure shows the performance when the reward is given by
Equation (4).

Fig. 3 Comparison of RL algorithms and types of reward functions in 3-party dialog. In these figures, the performancesof the policies are evaluated by using the reward function given by Equation (3).

(2) the number of fruits that the trader possesses, we canreconstruct a new state, which consists of this information
only, and its size will be independent of the number of

traders. We can scale the traders’ action spaces in the samemanner. This type of scaling is similar to the summary
state [Williams 07b] and summary action [Thomson 10]

11

Reinforcement Learning of Multi-Party Trading Dialog Policies
Table2 Averages of the number of each one of the learner’s actions per dialog, of the number of total turns, and ofachievements of fruit salad per dialog, over 20000 dialogs in 3-party trading. Note that “Accepted offer” is anoffer made by the learner that is accepted by the other traders.

HxH
RandomAlwaysKeep
LinQ-End
LSPI-EndNFQ-End
LinQ-Incr
LSPI-IncrNFQ-Incr
Handcraft1
Handcraft2

Offer
3.577
0.000
6.296
1.546
5.266
6.312
5.462
4.520
3.078
3.370

Accepted offer
0.463
0.000
0.076
0.115
0.172
0.078
0.170
0.350
0.128
0.197

Accept
0.191
0.000
0.000
0.245
0.094
0.000
0.128
0.001
0.024
0.137

Keep
1.169
4.231
0.002
2.337
0.447
0.000
0.306
0.914
2.030
1.585

Total actions
4.937
4.231
6.298
4.128
5.807
6.312
5.896
5.435
5.131
5.092

Total turns
14.53411.00317.87611.001
16.78517.911
16.83515.462
14.09114.386Fruit salad
0.156
0.227
0.210
0.165
0.197
0.206
0.270
0.355
0.329
0.343

HxR
RandomAlwaysKeep
LinQ-End
LSPI-EndNFQ-End
LinQ-Incr
LSPI-IncrNFQ-Incr
Handcraft1
Handcraft2

Offer
4.204
0.000
0.017
2.018
5.386
6.632
5.826
5.069
2.529
3.326

Accepted offer
0.465
0.000
0.000
0.050
0.251
0.082
0.229
0.190
0.189
0.273

Accept
0.311
0.000
0.000
0.393
0.187
0.001
0.143
0.329
0.213
0.343

Keep
1.254
4.518
4.552
2.407
0.829
0.001
0.785
0.933
2.863
2.134

Total actions
5.769
4.518
4.569
4.818
6.401
6.633
6.754
6.331
5.605
5.803

Total turns
16.08411.80411.927
12.56217.73218.65118.86617.21314.84715.769Fruit salad
0.168
0.222
0.219
0.219
0.170
0.214
0.219
0.626
0.532
0.459

RxR
RandomAlwaysKeep
LinQ-End
LSPI-EndNFQ-End
LinQ-Incr
LSPI-IncrNFQ-Incr
Handcraft1
Handcraft2

Offer
4.656
0.000
7.071
6.334
5.123
7.056
2.499
4.081
1.810
2.742

Accepted offer
0.600
0.000
0.302
0.312
0.304
0.304
0.156
0.256
0.244
0.365

Accept
0.531
0.000
0.000
0.685
0.351
0.000
0.539
0.775
0.370
0.581

Keep
1.247
5.106
0.000
0.049
1.170
0.000
2.963
1.977
3.830
2.930

Total actions
6.434
5.106
7.071
7.067
6.644
7.056
6.001
6.833
6.010
6.253

Total turns
17.94114.18319.88919.86418.55619.89616.62618.37916.19717.082

Fruit salad
0.178
0.218
0.177
0.101
0.177
0.171
0.364
0.801
0.701
0.591

approaches. However, to apply these scaling approaches,
we need to know what features are really important forsuccessful trading. This is not always easy to do manually, but we could instead use unsupervised learning orfeature selection techniques to automatically construct thestate/action space.
Our current setup assumes that each trader knows thenumber of items that the other traders possess, but in areal life setting this may not be possible. In that case, itwould be more difficult for the trader to perform well, andhe may need to keep track of recent trades. Our current
model does not take into account the trade history (e.g.,what trades have succeeded or failed so far). Therefore if
the trader does not know the number of items that the othertraders have, he may ask his trading partner to provide anitem that the partner does not possess. Even if the trader
can keep track of the trade history, this additional information may not necessarily help him make an appropriate
offer. The reason is that a trade that failed in a previous
turn, may succeed after a redistribution of items resulting
from trades between other parties.

人工知能学会論文誌 31 巻 4 号 B（2016 年）

12Table3 Averages of the number of each one of the learner’s actions per dialog, of the number of total turns, and ofachievements of fruit salad per dialog, over 20000 dialogs in 3-party trading. Note that “Accepted offer” is anoffer made by the learner that is accepted by the other traders.

H’xH’
RandomAlwaysKeep
LinQ-End
LSPI-EndNFQ-End
LinQ-Incr
LSPI-IncrNFQ-Incr
Handcraft1
Handcraft2

Offer
4.427
0.000
6.970
2.511
5.892
6.954
6.068
5.286
2.406
3.045

Accepted offer
0.808
0.000
0.272
0.249
0.443
0.260
0.525
0.635
0.332
0.424

Accept
0.364
0.000
0.000
0.525
0.217
0.000
0.283
0.003
0.071
0.237

Keep
1.346
5.763
0.002
2.667
0.521
0.001
0.367
1.269
3.818
2.994

Total actions
6.137
5.763
6.973
5.702
6.630
6.955
6.717
6.558
6.294
6.276

Total turns
17.65514.74819.36515.26818.77919.30918.89018.076
16.54016.957

Fruit salad
0.144
0.222
0.175
0.106
0.166
0.169
0.262
0.429
0.545
0.486

H’xR
RandomAlwaysKeep
LinQ-End
LSPI-EndNFQ-End
LinQ-Incr
LSPI-IncrNFQ-Incr
Handcraft1
Handcraft2

Offer
4.545
0.000
0.019
2.674
5.538
6.901
5.643
5.035
2.146
2.943

Accepted offer
0.705
0.000
0.001
0.139
0.374
0.271
0.433
0.401
0.283
0.391

Accept
0.452
0.000
0.000
0.610
0.244
0.001
0.176
0.436
0.223
0.388

Keep
1.324
5.631
5.616
2.511
0.941
0.000
1.134
1.260
3.952
3.047

Total actions
6.321
5.631
5.636
5.796
6.723
6.902
6.953
6.730
6.320
6.379

Total turns
17.62615.01515.06415.61918.70319.19119.34618.193
16.66717.156Fruit salad
0.161
0.222
0.219
0.134
0.164
0.172
0.312
0.524
0.625
0.541

Fig. 4 Number of epochs vs. performance of learned policies in 3-party trading. The figure shows the performance
when the reward is given by Equation (4). NFQ-Incr-adapt uses policies learned in different trading domains as
initial policies. In this experiment, the policy learned in HxH is used as an initial policy in H’xH’, and the policy
learned in HxR is used as an initial policy in H’xR. Avg. Handcraft1 represents the average cumulative rewardof Handcraft1 over 20000 dialogs.

6. Conclusion
In this paper, we used RL to learn the dialog system’s(learner’s) policy in a multi-party trading scenario. We ex-perimented with different RL algorithms and reward functions. The negotiation policies of the learner were learned
and evaluated through simulated dialog with trader simulators. We presented results for different numbers of traders.

Reinforcement Learning of Multi-Party Trading Dialog Policies

13

Our results showed that (1) even in simple multi-party
trading dialog domains, learning an effective negotiation
policy is not a straightforward task and requires a lot ofexperimentation; and (2) the use of neural fitted Q iteration combined with an incremental reward function produces as effective or even better negotiation policies thanthe policies of two strong hand-crafted baselines. Theseexperimental results depend on the properties of the trader
simulators.
For future work we will expand the dialog model to augment the dialog state with information about the estimatedpayoff matrix of other traders. This means expanding froman MDP-based dialog model to a POMDP-based model.
We will also apply multi-agent RL [Georgila 14] to multiparty trading dialog. Furthermore, we will perform evaluation with human traders. Finally, we will collect andanalyze data from human trading dialogs in order to improve our models and make them more realistic.

[Guhe 12] Guhe, M., and Lascarides, A.: Trading in a multiplayer
board game: Towards an analysis of non-cooperative dialogue, In
Proc. of CogSci., pp. 1626–1631 (2012)[Heeman 09] Heeman, P. A.: Representing the reinforcement learningstate in a negotiation dialogue, In Proc. of ASRU, pp. 450–455 (2009)[Hiraoka 14] Hiraoka, T., Neubig, G., Sakti, S., Toda, T., and Nakamura, S.: Reinforcement learning of cooperative persuasive dialogue
policies using framing, In Proc. of COLING, pp. 1706–1717 (2014)[Jokinen 09] Jokinen, K., and McTear, M.: Spoken dialogue systems,
Synthesis Lectures on Human Language Technologies, Morgan &Claypool (2009)[Lagoudakis 03] Lagoudakis, M. G., and Parr, R.: Least-squares policy iteration, Journal of Machine Learning Research, Vol. 4, pp.
1107–1149 (2003)[Levin 00] Levin, E., Pieraccini, R., and Eckert, W.: A stochastic
model of human-machine interaction for learning dialog strategies,
IEEE Transactions on Speech and Audio Processing, Vol. 8, No. 1,
pp. 11–23 (2000)[Mayya 11] Mayya, Y., Kyung, L. T., and Seok, K. I.: Negotiationand persuasion approach using reinforcement learning technique on
broker’s board agent system, In Proc. of NCM, pp. 30–34 (2011)[McGovern 01] McGovern, A., and Barto, A. G.: Automatic discovery of subgoals in reinforcement learning using diverse density, Computer Science Department Faculty Publication Series, 8 pages (2001)[Ng 99] Ng, A. Y., Harada, D., and Russell, S.: Policy invariance under reward transformations: Theory and application to reward shaping, In Proc. of ICML, pp. 278–287 (1999)[Nouri 12] Nouri, E., Georgila, K., and Traum, D.: A culturaldecision-making model for negotiation based on inverse reinforcement learning. In Proc. of CogSci., pp. 2097–2102 (2012)[Nouri 13] Nouri, E., Park, S., Scherer, S., Gratch, J., Carnevale, P.,
Morency, L. P., and Traum, D.: Prediction of strategy and outcome
as negotiation unfolds by using basic verbal and behavioral features,
In Proc. of INTERSPEECH, pp. 1458–1461 (2013)[Papangelis 15] Papangelis, A., and Georgila, K.: Reinforcement
learning of multi-issue negotiation dialogue policies, In Proc. of SIGDIAL, pp. 154–158 (2015)[Paruchuri 09] Paruchuri, P., Chakraborty, N., Zivan, R., Sycara, K.,
Dudik, M., and Gordon, G.: POMDP based negotiation modeling, In
Proc. of MICON, pp. 66–78 (2009)[Pfeiffer 04] Pfeiffer, M.: Reinforcement learning of strategies for
Settlers of Catan, In Proc. of the International Conference on Computer Games: Artificial Intelligence, Design and Education (2004)[Riedmiller 05] Riedmiller, M.: Neural fitted Q iteration - first experiences with a data efficient neural reinforcement learning method, In
Proc. of ECML, pp. 317–328 (2005)[Riedmiller 09] Riedmiller, M., Gabel, T., Hafner, R., and Lange, S.:
Reinforcement learning for robot soccer. Autonomous Robots, Vol.
27, No. 1, pp. 55–73 (2009)[Schaul 10] Schaul, T., Bayer, J., Wierstra, D., Sun, Y., Felder, M.,
Sehnke, F., Rückstieß T., and Schmidhuber, J.: Pybrain, Journal of
Machine Learning Research, Vol. 11, pp. 743–746 (2010)[Sutton 98] Sutton, R. S., and Barto, A. G.: Reinforcement Learning:
An Introduction, MIT Press Cambridge (1998)[Thomson 10] Thomson, B., and Young, S.: Bayesian update of dialogue state: A POMDP framework for spoken dialogue systems,
Computer Speech and Language, Vol. 24, No. 4, pp. 562-588 (2010)[Traum 08] Traum, D.: Extended abstract: Computational models of
non-cooperative dialogue, In Proc. of SEMDIAL-LONDIAL (2008)[Walker 00] Walker, M. A.: An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system foremail, Journal of Artificial Intelligence Research, Vol. 12, pp. 387–416 (2000)[Williams 07a] Williams, J. D., and Young, S.: Partially observable
Markov decision processes for spoken dialog systems, Computer
Speech and Language, Vol. 21, No. 2, pp. 393–422 (2007)[Williams 07b] Williams, J. D., and Young, S.: Scaling POMDPs for
spoken dialog management, IEEE Transactions on Audio Speech andLanguage Processing, Vol. 15, No. 7, pp. 2116–2129 (2007)[Zou 14] Zou, Y., Zhan, W., and Shao, Y.: Evolution with reinforcement learning in negotiation, PLoS One, Vol. 9, No. 7 (2014)

Acknowledgments
This research was partially supported by the 2014 Global
Initiatives Program, JSPS KAKENHI Grant Number 24240032,
and the Commissioned Research of the National Instituteof Information and Communications Technology (NICT),Japan. This material was also based in part upon work supported by the National Science Foundation under Grant
Number IIS-1450656, and the U.S. Army. Any opinions,findings, and conclusions or recommendations expressedin this material are those of the authors and do not necessarily reflect the views of the National Science Foundationor the United States Government, and no official endorsement should be inferred.

♢ References ♢[Asher 13] Asher, N., and Lascarides, A.: Strategic conversation, Semantics and Pragmatics, Vol. 6, pp. 1–62 (2013)[Efstathiou 14] Efstathiou, I., and Lemon, O.: Learning noncooperative dialogue behaviours, In Proc. of SIGDIAL, pp. 60–68(2014)[El Asri 13] El Asri, L., Laroche, R., and Pietquin, O.: Reward shaping for statistical optimisation of dialogue management, In Proc. of
SLSP, pp. 93–101 (2013)[Georgila 10] Georgila, K., Wolters, M. K., and Moore, J. D.: Learning dialogue strategies from older and younger simulated users, In
Proc. of SIGDIAL, pp. 103–106 (2010)[Georgila 11] Georgila, K., and Traum, D.: Reinforcement learningof argumentation dialogue policies in negotiation, In Proc. of INTERSPEECH, pp. 2073–2076 (2011)[Georgila 13] Georgila, K.: Reinforcement learning of two-issue negotiation dialogue policies, In Proc. of SIGDIAL, pp. 112–116(2013)[Georgila 14] Georgila, K., Nelson, C., and Traum, D.: Single-agent
vs. multi-agent techniques for concurrent reinforcement learning ofnegotiation dialogue policies, In Proc. of ACL, pp. 500–510 (2014)

人工知能学会論文誌 31 巻 4 号 B（2016 年）

14〔担当委員：Danushka Bollegala〕

Received December 25, 2015.

Author’s Profile
Hiraoka, Takuya
Takuya Hiraoka graduated from the Department of Informatics, Faculty of Science and Engineering, Kinki University in Japan in 2011. He completed the Ph.D. program at
the Graduate School of Information Science, Nara Instituteof Science and Technology (NAIST) in Japan in 2016. Currently he is a researcher at the Nippon Electric Company
Central Research Laboratories.

Georgila, Kallirroi
Kallirroi Georgila is a Research Assistant Professor at theInstitute for Creative Technologies and at the Computer Science Department of the University of Southern California(USC). Before joining USC in 2009 she was a Research Scientist at the Educational Testing Service (ETS) in Princeton,
USA, and before that a Research Fellow at the School ofInformatics of the University of Edinburgh, in the United
Kingdom. Her research interests include all aspects of spoken dialogue processing with a focus on reinforcement learning of dialogue policies, expressive conversational speech synthesis, and speech recognition. Georgila
has published over 80 journal articles, conference papers, and technical reports on
various topics in spoken dialogue processing. She has served on the organizing,senior, and program committees of many conferences and workshops, including
being General Co-Chair for SIGDIAL 2014, Mentoring Chair for SIGDIAL 2012
and 2013, Associate Chair for ICMI 2013, Area Chair for EACL 2012, and Program Co-Chair for SemDial 2011.

Nouri, Elnaz
Elnaz Nouri is a Ph.D. candidate at the Computer Science
Department of the University of Southern California. She is
a Provost Fellowship recipient and a member of the Natural Dialogue group at the Institute for Creative Technologies
where she works under the supervision of Dr. Traum. Her
Ph.D. thesis proposes a framework for developing culturesensitive models for decision making in social interactions.

Traum, DavidDavid Traum is the Director of Natural Language Researchat the Institute for Creative Technologies (ICT) and a Research Faculty member of the Department of Computer Science at the University of Southern California (USC). He
leads the Natural Language Dialogue Group at ICT. Moreinformation about the group can be found here: http://
nld.ict.usc.edu/group/ Traum’s research focuseson Dialogue Communication between Human and Artificial
Agents. He has engaged in theoretical, implementational and empirical approaches
to the problem, studying human-human natural language and multi-modal dialogue,
as well as building a number of dialogue systems to communicate with humanusers. Traum has authored over 200 refereed technical articles, is a founding editorof the Journal Dialogue and Discourse, has chaired and served on many conference
program committees, and is a past President of SIGDIAL, the international special interest group in discourse and dialogue. Traum earned his Ph.D. in Computer
Science at the University of Rochester in 1994.

Nakamura, Satoshi (Member)
Satoshi Nakamura is Professor of Graduate School of Information Science, Nara Institute of Science and Technology,
Japan, Honorar professor of Karlsruhe Institute of Technology, Germany, and ATR Fellow. He received his B.S. from
Kyoto Institute of Technology in 1981 and Ph.D. from Kyoto University in 1992. He was Director of ATR Spoken
Language Communication Research Laboratories in 20002008 and Vice president of ATR in 2007-2008. He was
Director General of Keihanna Research Laboratories, National Institute of Information and Communications Technology, Japan in 2009-2010. He is currently
Director of Augmented Human Communication laboratory and a full professor of
Graduate School of Information Science at Nara Institute of Science and Technology. He is interested in modeling and systems of speech-to-speech translation,spoken dialog, and speech recognition. He has been serving for various speech-tospeech translation research projects in the world including C-STAR, IWSLT, and
A-STAR. He received many domestic academic awards including Kiyasu Award
from the Information Processing Society of Japan, ASJ Award for DistinguishedAchievements in Acoustics. He also received the Commendation for Science andTechnology by the Minister of Education, Science and Technology, and the Minister of Internal Affair and Communications. He also received LREC Antonio
Zampoli Award 2012. He is an Elected Board Member of International SpeechCommunication Association, ISCA, since June 2011, IEEE Speech and Language
Technology Committee member since April 2012, and IEEE Fellow from 2016.