Solving MDPs with Skew Symmetric Bilinear Utility Functions

1 Introduction

Decision-theoretic planning deals with planners involving decision-theoretic tools [Blythe, 1999; Boutilier et al., 1999]. As emphasized by Blythe [1999], AI planning and decision theory appear indeed to be complementary, and there has been interest in merging the two approaches for a considerable time. The study of Markov Decision Processes (MDPs) constitute perhaps the biggest part of decision-theoretic planning, because MDPs can be considered as a natural framework both for modeling and solving complex structured decision problems [Puterman, 1994]. In an MDP, scalar rewards, assumed to be additive, are granted along the process, and a policy is evaluated according to the expectation of the sum of rewards. Yet, expectation is far from being the only possible decision criterion. In particular, expectation is not a risk sensitive criterion, in the sense that it assumes risk neutrality (e.g., a sure $500 gain is equivalent to having a probability 1/2 of a $1000 gain or nothing). One of the topics of decision theory is precisely to provide risk sensitive criteria.

The most popular risk-sensitive criterion in decision theory is the expected utility (EU) model [von Neumann and Morgenstern, 1947]. In this model, an agent is endowed with a utility function u that assigns a numerical value u(x) to each consequence x in the set X of possible outcomes. A probability distribution p is preferred to q, denoted by p ≻ q, iff u(p) > u(q), where u(p) = ∑x∈X p(x)u(x). According to the shape of the utility function used, the maximization of expected utility will favor risk-averse or risk-seeking behaviors. Solution algorithms for MDPs with expected utility objective functions have been proposed by Liu [2005] and Liu and Koenig [2005; 2006; 2008]. Nevertheless, despite its intuitive appeal, the EU model does not make it possible to account for all rational decision behaviors. For instance, it is unable to explain the paradox of nontransitive dice as designed by statistician Efron and reported by Gardner [1970]. The specific variant we present here is due to Rowett.

Example 1 (Rowett Dice). Consider a two-player game involving the following set of six-sided dice: die A with sides (1, 4, 4, 4, 4, 4), die B with sides (3, 3, 3, 3, 3, 6) and die C with sides (2, 2, 2, 5, 5, 5). The players, each equipped with a personal set of Rowett dice, simultaneously choose a die to throw; the winner is the player who rolls the highest number. It is easy to realize that die A rolls higher than B most of the time, so die A should be preferred to B. Similarly die B rolls higher than C most of the time, and the same can be said about C against A. In other words, the relation "more likely to win" is not transitive, and in fact it is even cyclic.

This example can be formalized by characterizing dice A,B,C by probability distributions pA, pB, pC over the set X = {1, 2, . . . , 6} of possible outcomes. The expected utility model is obviously unable to accommodate the above preferences pA ≻ pB ≻ pC ≻ pA because it is impossible to have u(pA) > u(pB) > u(pC) > u(pA). Actually, every binary preference relation solely based on a unary functional u over distributions would fail to explain the paradox.

Interestingly, the skew symmetric bilinear (SSB) utility theory [Fishburn, 1984], which extends expected utility theory, enables to accommodate this type of intransitivities by using a binary functional ϕ over distributions, and governing the preference between p and q by the sign of ϕ(p, q), where p ≻ q iff ϕ(p, q) > 0. It is indeed possible that inequalities ϕ(pA, pB) > 0, ϕ(pB, pC) > 0 and ϕ(pC, pA) > 0 simultaneously hold. As we will see later on, the relation "more likely to win" can be modeled by SSB utility theory.

The possibility of cyclic preferences in SSB utility theory could be seen as a significant barrier to its use in automated decision. However, in a finite set of distributions, there always exists a convex combination of these distributions (probability mixture) that is preferred or indifferent to each mixture in the convex hull [Fishburn, 1984]. For instance, coming back to our dice example, playing die A (resp. B, C) with probability 3 13 (resp. 3 13 , 7 13 ) is a maximal strategy for the relation "more likely to win". Consequently, choice by maximal preference using SSB utility theory is well defined for finite horizon MDPs even if there are preference cycles between deterministic policies. Note that, as emphasized by Fishburn [1984], not only does SSB utility theory enable to explain cases of intransitivity, but it also accommodates reasonable behaviors that involves widely observed violations of the von Neumann-Morgenstern independence axiom [Allais, 1953; Kahneman and Tversky, 1979].

We model the problem of computing an SSB optimal policy in an MDP as the search for a Nash equilibrium in a zerosum two-player symmetric game defined from the MDP and the SSB utility function. The set of pure strategies in this game is the set of deterministic policies after transforming the given MDP in an "augmented" MDP [Liu, 2005], and the payoff function is inferred from the SSB utility function. The set of deterministic policies is combinatorial in nature, which makes impractical the generation of the whole payoff matrix of the game. We therefore adopt a double oracle approach [McMahan et al., 2003] that makes it possible to solve the game without generating the whole payoff matrix.

We provide the results of numerical experiments, notably on a famous TV game, Who Wants to Be a Millionaire?. Our results illustrate the enhanced possibilities offered by the use of an SSB utility function for controlling the shape of the probability distribution over payoffs.

2 SSB Utility Theory

Any policy in an MDP induces a probability distribution over possible final wealth levels (cumulated reward scores). Comparing policies amounts then to comparing their induced distributions. We assume throughout the paper that the outcome set, denoted W, of policies is the real line, interpreted as wealth, and that the agent's preferences between distributions are described by the SSB model as presented and axiomatized by Fishburn [1984]. In this model, an agent is endowed with a binary functional ϕ over ordered pairs (x, y) ∈ W2 of wealth levels, with x > y ⇔ ϕ(x, y) > 0. The value ϕ(x, y) can be interpreted as the intensity with which the agent prefers x to y. Functional ϕ is assumed to be skew symmetric, i.e., ϕ(x, y) = -ϕ(y, x) and bilinear w.r.t. the usual mixture operation on distributions. The SSB criterion for comparing probability distributions p and q is then written:

where p(x) (resp. q(y)) denotes the probability of wealth level x (resp. y) in distribution p (resp. q). We have p ≻ (resp. ≺) q if ϕ(p, q) > (resp. <) 0 (strict preference), and p ∼ q if ϕ(p, q) = 0 (indifference).

The SSB model is very general as it can represent preferences observed in Example 1.

Example 2. (Example 1 cont'd) Distributions pA, pB, pC are defined in Figure 1. By setting ϕ(x, y) = 1 if x > y, and ϕ(x, y) = -1 if x < y, ϕ(p, q) corresponds then to the probability that p beats q minus the probability that q beats p. The obtained SSB utilities in the example are:

ϕ(pA, pB) = 25/36-11/36 = 14/36,

ϕ(pB, pC) = 21/36-15/36 = 6/36,

ϕ(pC, pA) = 21/36-15/36 = 6/36.

Therefore we have ϕ(pA, pB) > 0, ϕ(pB, pC) > 0 and ϕ(pC, pA) > 0, which is consistent with the relation "more likely to win" between dice (i.e., pA ≻ pB ≻ pC ≻ pA).

Moreover, the SSB model can represent different risk attitudes via an adequate choice of functional ϕ. It accounts for a risk-averse (resp. risk-seeking) behavior (in the weak sense) if the certainty equivalent of a distribution p is less (resp. greater) than or equal to its expected value, where the certainty equivalent of a distribution p is the wealth level x such that ϕ(p, x) = 0 (which implies p ∼ x). For existence and unicity of the certainty equivalent, the following conditions on ϕ should hold for all x, y, t ∈ W: (1) for x ̸= y, ϕ(x, y)/ϕ(y, z) is continuous for all z ∈ W except z = y, (2) ϕ(y, t)/ϕ(x, t) is strictly increasing in t for x, y, t with x < t < y. Condition 1 implies that every distribution has at least one certainty equivalent [Fishburn, 1986], while condition 2 implies that the certainty equivalent is unique [Nakamura, 1989]. By defining ϕ1(x, y) = ∂ϕ(x, y)/∂x, Nakamura showed that, when ϕ1(x, x) ̸= 0 exists, ϕ is weakly risk-averse (risk-seeking) if and only if ϕ1(y, y)/ϕ(x, y) ≥ (≤) 1/(x - y). We return to this point later in Section 6.

The SSB model encompasses many decision criteria, e.g.: - ϕ(x, y) = x - y yields the expectation criterion;

- ϕ(x, y) = u(x) - u(y) yields the EU model;

- ϕ(x, y) = δθ(x) - δθ(y), where δθ(x) = 1 (0) if x ≥(<) θ, yields the probability threshold criterion [Yu et al., 1998], which states that p ≻ q if ∑x≥θ p(x) > ∑x≥θ q(x);

- ϕ(x, y) = 1 (resp. 0, -1) if x > y (resp. x = y, x < y) yields the dominance relation of Example 1, which states that p ≻ q if ∑x>y p(x)q(y) > ∑y>x p(x)q(y); this is called probabilistic dominance (PD) in the sequel.

Consequently, designing and implementing an algorithm for solving MDPs with SSB also gives us a tool to compute optimal policies for all these special cases. Although dedicated algorithms exist for solving MDPs with an EU objective [Liu and Koenig, 2008] or a threshold probability objective [Hou et al., 2014], it is interesting to have a generic algorithm easily adaptable to a large class of decision criteria. The next section presents the augmented MDP framework that will be used to determine SSB optimal policies.

3 Markov Decision Processes with SSB utility

3.1 Background

We study in this paper MDPs with finite state and action spaces, modeling finite horizon problems. As usual, an MDP is formally defined by M = (T, S,A,P,R, c) where: T, a positive integer, is the time horizon; S is a finite collection of states, one of which is designated as the initial state; A = {As|s ∈ S} is a collection of finite sets of possible actions, one set for each state; P = {Pt|t = 0, . . . , T - 1} is a collection of transition probabilities where Pt(s′ |s, a) is the probability that the state at time step t + 1 is s′ given that the state at time step t was s and that we have performed action a; R is the set of possible immediate rewards; c = {ct|t = 0, . . . T - 1} is a collection of reward functions where ct(s, a, s′ ) is the reward obtained if the state at time step t + 1 is s′ given that the state at time step t was s and that we have performed action a. To illustrate our notations on a voluntarily simple sequential decision problem, we (artificially) modify Example 1 from the introduction.

Example 3 (One-agent sequential variant of Rowett dice). An agent has first to choose whether she wants to throw (action a1) or not (action a′1 ) die A; if this is not the case, she needs to choose between die B (action a2) or C (action a3). Whatever die is chosen, we distinguish two cases: success (state s3) if one of the advantageous faces of the die is rolled (e.g., a face 4 for die A), or failure (state s2) otherwise. The objective function is the number rolled, to maximize.

The decision problem can be modeled by the MDP represented in Figure 2 with T = 2, S = {s1, s′1 , s2, s3}, A = {{a1, a′1 }, {a2, a3}, · · · , {a5}}, R = {0, · · · , 6} and where c1, c2 and c3 are the chance nodes induced by P. The values ct(s, a, s′ ) |Pt(s′ |s, a) (that do not depend on t in this example) are shown along the edges.

We call t-history a succession of state-action pairs of length t, ht = (s0,a0,s1,. . . ,st-1,at-1,st) .

A decision rule δt indicates which action to perform in each state for a given time step t. A decision rule can be historydependent meaning that it takes as argument the entire history generated so far or Markovian if it only takes as argument the current state. A decision rule will be deterministic if it always prescribes an action per state or randomized if it prescribes a probability distribution over actions per state.

A policy π at an horizon T is a sequence of T decision rules (δ0, . . . , δT-1). Note that our policies are non-stationary in the sense that the decision rules can be different, depending on the time step. A policy can be history-dependent, Markovian, deterministic or randomized according to the type of decision rules. We use the notations of Table 1 for the sets of the different types of policies. Importantly, given a set Π = {π1, π2, . . .} of policies, we define an enlarged set ˜Π of policies, that denotes the set consisting of mixtures of policies, i.e., ˜Π={˜π=(π1|α1, π2|α2, . . .) : ∑i αi=1, αi ≥ 0},

2

Table 1: Policy Notations

where ˜π is the mixed policy 1 that randomly selects policy πi with probability αi.

3.2 Comparing Two Policies

To compute the SSB criterion for comparing two policies, pairs of histories have to be compared (via the ϕ functional). In order to embed histories in the wealth level space W, we assume that the value of a history is completely defined by the final wealth level accumulated along the history. Let WT = {w1, . . . , wm} be the set of attainable wealth levels at horizon T . Following Iwamoto [2004], we define the wealth level, ω(hT ) ∈ WT of a T-history, hT , as an aggregation of rewards along hT :

where ◦ is a binary operator defined on W ×R and λ ∈ W is a left identity element with respect to ◦. Note that no special property is required for ◦ as only final wealth levels need to be compared. Therefore, many different ways of evaluating T -histories are compatible with this setting.

The agent's SSB utility function ϕ defines a preference relation on probability distributions over possible wealth level outcomes WT = {w1, . . . , wm} and therefore defines a preference relation ≿ on policies :

where pπx denotes the probability of x when applying policy π. As ≿ depends on wealth levels, optimal policies will also depend on them. For this reason, we incorporate those values in the state space. Following Liu and Koenig [2008], we transform the given MDP into an augmented MDP whose states are pairs (s, w) where s is a state of the original MDP and w ∈ W a wealth level attainable by executing actions in the given MDP.

Example 4. We illustrate the notion of augmented MDP on our modified Rowett dice problem, represented in Figure 2. In this example wealth levels are combined with the standard summation operator; w ◦ ct(s, a, s′ ) = w + ct(s, a, s′ ) and λ = 0. The augmented MDP is represented in Figure 3.

To avoid any confusion, we denote by s = (s,w) a state in the augmented MDP. For instance, Πts (resp. Πts,r ) denotes the set of deterministic (resp. randomized) Markovian policies in the augmented MDP. Note that, in the augmented MDP, Markovian decision rules take into account both the current state and the wealth level accumulated so far.

1 Not to be confused with the notion of randomized policies.

Let ST ⊆ S × WT the set of final states in the augmented MDP. Now, in the augmented MDP, the preference relation over policies only depends on the probability distributions induced by policies over final wealth levels. Those distributions can be computed in the following way. Recall that in any MDP (augmented or not), a policy induces a probability distribution over histories and a fortiori over final states. The probability distribution over final states associated to a policy can be easily computed by a standard dynamic programming procedure. In the augmented MDP, assuming a probability distribution (pπs )s∈ST has been computed, the associated probability distribution over final wealth levels (pπw )w∈WT can simply be obtained by marginalization: pπw = ∑s=(s,w)∈ST pπ s .

Collins and McNamara [1998] showed that, provided we are only interested in the probabilities of the final states, it is not a restrictive assumption to focus on mixed policies in ˜Πts . They indeed showed that for any mixed policy ˜π in ˜Πh,r there exists a mixed policy ˜π′ in ˜Πts such that p˜π s = p˜π′ s for all s ∈ ST .

Besides, from a mixed policy, it is possible to recover an equivalent (w.r.t. SSB) randomized policy. This is useful, in situations where an agent may prefer to apply a randomized policy instead of a mixed strategy. Strauch and Veinott [1966] showed how 2 to compute a randomized policy π in Πts,r from any mixed policy ˜π in ˜Πts in such a way that pπ s = p˜πs for all s ∈ ST . Consequently, in the remainder of the paper, we focus on policies in ˜Πts in the augmented MDP.

4 AGame on Policies

Assuming it exists, finding a preferred policy for our criterion is not straightforward. Not only can preference ≿ be intransitive (as illustrated by the Rowett dice problem), but the SSB criterion also does not respect Bellman's principle of optimality. The violation of Bellman's principle of optimality is illustrated by our one-agent sequential variant of the Rowett dice problem represented in Figure 2. Indeed, the PD-optimal policy is the randomized policy (s1→(a1| 3 13 , a′1 | 10 13 ),s′1→(a2| 3 10 , a3| 7 10 )) (play dice A, B

2 The randomized policy π corresponding to mixed policy ˜π = (π1|α1, π2|α2, . . .) is obtained by the following:

and C with probabilities 3 13 , 3 13 and 7 13 ). However, the PDoptimal sub-policy when in state s′1 with T = 1 is to play a2 (die B) with probability 1 as only dice B and C remain and that die B rolls higher than C most of the time. Therefore dynamic programming cannot be used directly and we turn to a game-theoretic analysis of the problem of identifying an SSB-optimal policy from the initial state.

When an MDP and a time step T are fixed, Equations 1 and 2 induce a zero-sum two-player symmetric game where the set of pure strategies can be reduced to Πts . Each player i ∈ {1, 2} chooses simultaneously a strategy πi (pure or mixed). The resulting payoff is then given by ϕ(π1, π2).

In a zero-sum symmetric game of payoff function ϕ, it is well-known that there exists a symmetric Nash equilibrium (NE). The following holds for an NE (π∗ , π∗ ):

We aim at computing such an NE of the game on policies characterized by payoff function ϕ (solving the game) since strategy π∗ will be SSB preferred to any other strategy and will therefore be an SSB optimal policy in the MDP.

Thanks to this game-theoretic view, it is now straightforward to prove that an SSB-optimal policy exists for any finite horizon MDP (M, T ).

Theorem 1. For any finite horizon MDP (M, T) and any SSB utility function ϕ, an SSB-optimal policy exists in ˜Πts .

Proof. The set Πts is finite (T, S and A are finite) and thus the game induced by the SSB criterion restricted to Πts is finite. Therefore, the von Neumann minimax theorem ensures that an optimal strategy exists as a mixed policy in ˜Πts .

Once realized that an NE of the game on policies of Πts provides us an SSB optimal policy, our aim becomes to solve this game. However, note that the large size of Πts prohibits solving it directly. We address this issue in the next section.

5 Solving the Game

In this section, we first describe the double oracle approach [McMahan et al., 2003] that enables to solve large-size games by avoiding the ex-ante enumeration of all pure strategies. Then, we adapt this procedure to our problem by providing a best response procedure (oracle) to a given mixed policy.

In our setting, the double oracle approach is implemented by the procedure described in Algorithm 1, which is a simplified version of the initial proposal by McMahan et al..

Double oracle approach. The double oracle algorithm finds a Nash equilibrium for a finite two player game where a best response procedure BR(·) exists. Given a mixed strategy ˜π, BR(˜π) returns a pure strategy π (a policy in Πts ) that maximizes ϕ(π, ˜π). The original double oracle algorithm applies to any zero-sum two-player game. The operation can be described as follows in the symmetric case. The algorithm starts with a small set Π of pure strategies (a singleton in Algorithm 1), and then grows this set in every iteration by applying the best-response oracle to the optimal strategy (given by NE) the players can play in the restricted game G = (Π′ , Π′ , ϕ|Π′ ), where Π′ is the set of available strategies

Algorithm 1: Double Oracle Algorithm

Data: Finite horizon MDP (M, T ), singleton Π′ = {π} including an arbitrary policy π ∈ Πts Result: an SSB optimal mixed policy ˜π ∈ ˜Πts 1 converge = False 2 while converge is False do 3 Find Nash equilibrium (˜π, ˜π) ∈ G = (Π′ ,Π′ , ϕ|Π′) 4 Find π = BR(˜π) ∈ Πts 5 if ϕ(π, ˜π) > 0 then 6 add π to Π′ 7 else 8 converge =True 9 return ˜π

for both players and ϕ|Π′ is the restriction of function ϕ to domain Π′ ×Π′ . An NE in a zero-sum two-player symmetric game can be computed by linear programming [Raghavan, 1994]. Execution continues until convergence is detected. Convergence is achieved when the best-response oracle does not generate a pure strategy π that is better than the current mixed strategy ˜π. In other words, convergence is obtained if the payoff ϕ(π, ˜π) given by the best-response oracle is not better than the payoff given by the current NE (0 for a zerosum two-player symmetric game).

The correctness of best-response-based double oracle algorithms for two-player zero-sum games has been established by McMahan et al [2003]; the intuition for this correctness is as follows. Once the algorithm converges, the current solution must be an equilibrium of the game, because each player's current strategy is a best response to the other player's current strategy. This stems from the fact that the best-response oracle, which searches over all possible strategies, cannot find anything better. Furthermore, the algorithm must converge, because at worst, it will generate all pure strategies. In practice, we expect the restricted-game to stay relatively small as many pure strategies will never enter the restricted strategy set.

Best response oracle. In order to use the double oracle approach, we look for a procedure to find a policy which is a best response to a fixed mixed policy ˜π = (π1|α1,. . .,πk|αk). This best response is an optimal policy according to the decision criterion maximizing the value function v(π) = ϕ(π, ˜π) and amounts to taking ˜π as a reference point.

Let Φ denote the skew-symmetric matrix where Φi,j = ϕ(wi, wj), and pπw denote vector (pπw1 , . . . , pπwm ). With such notations we can express ϕ(π, ˜π) as:

Denoting by ei the i-th canonical vector, we can interpret Φp˜πw as a reward function where one would receive (Φp˜πw ).ei as a reward each time one obtains a final wealth value of wi, and 0 at each previous time step. More formally, the reward function in the augmented MDP is then defined by:

Using this reward function, maximizing the classic expectation criterion is equivalent to maximizing tpπwΦp˜πw . A policy maximizing such criterion is classically found by backward induction in the augmented MDP, leading to a deterministic Markovian policy in Πts .

Example 5. Coming back to the sequential Rowett dice example, we show how to find the best response to the policy ˜π that chooses die A with probability 1. Assume that one uses the probabilistic dominance criterion, i.e., Φ is the skew-symmetric matrix with ones below the diagonal. In this example, (w1, . . . , wm) = (1, 2, . . . , 6) and p˜πw = ( 16 , 0, 0, 56 , 0, 0). Determining BR(˜π) amounts then to computing the policy maximizing expectation in the augmented MDP represented in Figure 3, where the reward function is replaced by :

Unsurprisingly, the policy obtained will play die C.

6 Experiments

We provide here experimental results in order to demonstrate the operationality of the method and to provide a deeper insight on the interest of using an SSB utility function.

Who Wants to Be a Millionaire? In this popular television game show, a contestant tries to answer a sequence of 15 multiple-choice questions of increasing difficulty. Questions (four possible answers are given) are played for increasingly large sums, roughly doubling the pot. At each time step, the contestant may decide to walk away with the money currently won. If she answers incorrectly then all winnings are lost besides what has been earned at a "guarantee point" (questions 5 and 10). The player is given the possibility of using 3 lifelines (50:50, removing two of the possible choices, ask the audience and call a friend for suggestions); each can only be used once in the whole game.

We used the two models of the Spanish 2003 version of the game presented by Perea and Puerto [2007]. 3 In the first model the probability of answering correctly is a function of the question's number and the lifelines (if any) used; lifelines increase the probability of answering correctly (the model is fitted using real data). This first model is overly simplistic as it does not actually take into account whether the player does in fact know the answer or not. The second model represents the hesitation of the contestant by distinguishing four epistemic cases, corresponding to the number of answers (among the four given) that are believed possible correct answers for the current question. At each step of the game, when a new question is asked, a categorical distribution dictates the probability of each of the epistemic cases. As the game proceeds, questions are more difficult, and the distribution is then skewed towards hesitating between larger sets of answers.

We computed the optimal policies for the two models according to several instantiations of the SSB utility function: the expectation (Exp), probabilistic dominance (PD), threshold probability (Th) criteria (threshold set to 2700) and a risk averse SSB utility function (RA) defined by ϕRA(x, y) = (x - y)/(x + y) 23 , which is indeed risk averse since Nakamura's condition holds (Section 2).

Given the simplicity of the first model of the game, policies can be compactly displayed; the optimal policies are reported on the left of Figure 4. The Exp, RA and Th criteria are associated with deterministic policies, while the PD-optimal policy can be seen either as a mixed policy or as a randomized policy (see right of Figure 4). According to intuition, the preferred policies for PD and RA make use of lifelines much earlier in the game, in order to secure a significant gain; the preferred policy for Th uses the lifelines to reach 2700 with high probability and stops playing thereafter. Finally, with Exp, one keeps aside the lifelines for later (more difficult) questions, even at a cost of a premature end of the game.

When using the second model, the state space is much larger and policies are too complex to be represented compactly. As we are interested in comparing their overall performance, we plot in Figure 5 the decumulative distribution of wealth (as the pot sky-rockets if the contestant reaches the very last questions, but this happens for all policies with low probabilities, we plot only the 9 first wealth levels for emphasizing the differences between the wealth distributions).

3 The possible wealth values are 0, 150, 300, 450, 900, 1800, 2100, 2700, 3600, 4500, 9k, 18k, 36k, 72k, 144k, 330k.

Unsurprisingly, the expectation-optimal policy yields the highest wealth expectancy (2387 and 1717 in the two models of the game). While the optimal policy according to PD achieves a lower expected value, it scores better very often: it achieves a wealth level at least as good as 75% (resp. 70%) of the time and strictly better 44% (resp. 48%) of the time, when considering the first (resp. second) model. The policy obtained with the RA criterion is safer than the expectationoptimal policy. Regarding the threshold-optimal policy, it obtains with higher probability (23%) the threshold objective as can be seen in Figure 5 (second model).

Regarding the computational aspect, the initial MDP in this problem consists of 9 (resp. 136) states for the first model (resp. second model) and the corresponding augmented MDP has 33 (resp. 496) states. The computation time (resp. number of iterations of the double oracle algorithm) for finding each optimal policy for the second model of the game was respectively of 7.6s (resp. 1) for the Exp criterion, 9.0s (resp. 8) for PD criterion, 7.8s (resp 3) for the RA criterion and 7.6s (resp 1) for the Th criterion. 4

Other domains. To have a deeper insight into the operationality of our method, we have carried out some preliminary experiments on other domains, notably on a simple grid world (GW) domain (with randomly generated instances) and a cancer clinical trials (CCT) domain (with a model proposed by Cheng et al. [2011]). In both domains, we used the probabilistic dominance criterion. In the GW domain, the initial state space includes from 100 to 400 states, and the augmented state space from thousands to tens of thousands states. The computation times vary from a few seconds to half an hour. Regarding the CCT domain, the initial state space includes 5078 states, and the augmented state space 5129 states. The method takes about two minutes to compute an optimal policy. Generally speaking, provided the structure of the MDP prevents the augmentation of the state space to be too costly (as can bee seen in the two previous examples, there is an important variability in the increase of the number of states after augmentation of the MDP), we believe the method is rather scalable. A more thorough study of its scalability is underway.

7 Conclusion

Skew Symmetric Bilinear utility functions (SSB) is a useful general decision model that encompasses many decision criteria (e.g., EU, threshold probability, probabilistic dominance...). We showed that there exists an optimal (potentially randomized) Markovian policy in an augmented MDPs where preferences are described with an SSB utility function and we proposed an iterative solution method based on a gametheoretic view of the optimization of an SSB utility function.

4 All times are wall-clock times on a 2,4 GHz Intel Core i5 machine with 8G main memory. Our implementation is in Python, with an external call to GUROBI version 5.6.3 in order to solve the linear programs required to find the Nash equilibria.

Our current work can be extended in several natural ways. First, a theoretical study in order to guarantee an upper bound on the number of iterations of the double oracle algorithm is needed. Besides, it would be useful to extend this work to factored MDP in order to tackle large size problems. Moreover, it would be interesting to investigate the use of SSB utility functions in reinforcement learning settings.