Algebraic Markov Decision Processes

1 Introduction

In the field of planning under uncertainty, the theory of Markov Decision Processes (MDPs) has received much attention as a natural framework both for modeling and solving complex structured decision problems, see e.g. [Dean et al., 1993; Kaebling et al., 1999]. In the standard MDP approach, the utilities of actions are given by scalar rewards supposed to be additive, uncertainty in the states of the world and in the consequences of the actions are represented with probabilities, and policies are evaluated using the expected utility (EU) model. Although these choices are natural in various practical situations, many other options are worth investigating for several reasons :

• Rewards of actions are not necessarily scalar nor additive. In multi-agent planning or in multicriteria MDPs, the utility of any action is given by a vector of rewards (one per agent or criterion) and actions are compared according to Pareto dominance [Wakuta, 1995]. In qualitative frameworks, rewards are valued on an ordinal scale and therefore are not additive. The sum is then replaced by the min, max or any refinement of them, depending on the context.

Paul Weng LIP6 - Université Paris 6 4 Place Jussieu 75252 Paris Cedex 05, France paul.weng@lip6.fr

• Non-probabilistic representation of uncertainty might be of interest. In practice, it is sometimes difficult to quantify precisely the plausibility of states and consequences of actions. Assessing probabilities in such situations seems difficult. For this reason, alternative approaches based on qualitative representations of uncertainty have been proposed (see e.g. [Darwiche and Ginsberg, 1992; Dubois and Prade, 1995; Wilson, 1995]) and might be used in the context of MDPs.
• Non-EU theories offer also interesting descriptive possibilities. Despite the appeal of the expected utility model and its theoretical foundations [von Neumann and Morgenstern, 1947; Savage, 1954], recent developments of decision theory have shown the descriptive potential of alternative representations of preferences under uncertainty. For example, the rank dependent expected utility theory (RDEU) is a sophistication of EU theory using probability transforms to better account for actual decision making behaviors under risk [Quiggin, 1993]. Besides this extension, various alternatives to EU have been proposed for decision making in a non-probabilistic setting. Among them, let us mention the qualitative expected utility (QEU) theories proposed in [Dubois and Prade, 1995] and [Giang and Shenoy, 2001], and very recently, the generalized expected utility theory (GEU) proposed in [Chu and Halpern, 2003a; 2003b] which generalizes the notion of expectation for general plausibility measures.

Despite the diversity of models proposed for decision making under uncertainty, very few of them are used in the context of dynamic decision making. This gap can be explained by the inconsistencies entailed by the use of non-EU criteria (typically RDEU) in the dynamic context [Machina, 1989; Sarin and Wakker, 1998]. Indeed, when using a given nonlinear utility criterion at each decision stage, the Bellman principle is generally violated, so that backward induction is likely to generate a dominated policy; further, there is in general no operational way to determine an optimal policy. This simple statement largely explains the predominance of the EU model in dynamic decision making under risk.

In the last decade however, some alternative models to EU have been proved to be dynamically consistent, thus providing new possibilities for sequential decision making. This is the case of qualitative expected utility theory [Dubois and Prade, 1995] that has led to a possibilistic counterpart of MDPs [Sabbadin, 1999] with efficient algorithms adapted from backward induction and value iteration, substituting operations (+, ×) by (max,min) in computations. In the same vein, [Littman and Szepesvári, 1996] propose a generalized version of MDPs where max and + are substituted by abstract operators in Bellman equations, and [Bonet and Pearl, 2002] propose a qualitative version of MDPs. Besides these positive results, very few alternatives to standard MDPs have been investigated.

Among the diversity of possible choices for defining a reward system, a plausibility measure over events and a preference over lotteries on rewards, we need to know which combination of them can soundly be used in the context of MDPs and which algorithm should be implemented to determine an optimal policy. For this reason, we propose in this paper an algebraic generalization of the standard setting, relying on the definition of a semiring structure on rewards, a semiring structure on plausibilities of events, and a generalized expectation model as decision criterion [Chu and Halpern, 2003a]. The generalization power of semirings have been already demonstrated in AI by [Bistarelli et al., 1995] in the context of constraint satisfaction problems. Within this general setting, our aim is to present a unified treatment of MDPs and to provide algorithmic solutions based on the general Jacobi algorithm (initially introduced to solve systems of linear equations).

The paper is organized as follows: in Section 2, we show by example how to recast an MDP as an optimal path problem in a decision graph. Then we introduce an algebraic framework for MDPs, relying on the definition of algebraic structures on rewards, plausibilities and expectations (Section 3). In Section 4 we justify the use of the Jacobi algorithm as a general procedure to determine an optimal policy in an Algebraic MDP (AMDP). Finally, we consider in Section 5 some particular instances of AMDPs, including new probabilistic and possibilistic MDPs using partial preferences over rewards.

2 Decision Rule Graph inMDPs

We briefly recall the main characteristics of a Markov Decision Process (MDP) [Puterman, 1994]. It can be described as a tuple (S, A, T, R) where:

• S = {s1 , . . . , sn } is a finite set of states,
• A = {a1 , . . . , am} is a finite set of actions,
• T : S×A → Pr(S) is a transition function, giving for each state and action, a probability distribution over states (in the sequel, we write T (s, a, s′ ) for T (s, a)(s′ )),
• R: S × A → R is a reward function giving the immediate reward for taking a given action in a given state.

A decision rule is a function from the set of states S to the set of actions A. There are N = mn available decision rules at each step. We write ∆ = AS = {δ1 , . . . , δN } the set of decision rules. A policy at step t (i.e., the tth -to-last step) is a sequence of t decision rules. For a policy π and a decision rule δ, we note (δ, π) the policy which consists in applying first decision rule δ and then policy π.

A history is a realizable sequence of successive states and actions. The accumulated reward corresponding to a history γt = (st, at, st-1, . . . , a1, s0) (with initial state st) is R(γt) = ∑ti=1 R(si, ai). We denote Γt(s) the set of t-step histories starting from s. For an initial state s, a t-step policy π = (δt, . . . , δ1) induces a probability distribution Prπt (s, ·) over histories. The t-step value of being in state s and executing policy π is given by (expected accumulated reward):

Denoting vπ t the vector whose ith component is vπ t (si ), any two t-step policies π, π′ can be compared using the componentwise dominance relation ≥Rn defined by:

Example 1 Consider an MDP with S = {s1 , s2 }, A = {a1 , a2 }, T(si , aj , sk ) = 1 if i = j = k and 0.5 otherwise, R(s1 , a1 ) = 8, R(s1 , a2 ) = 7, R(s2 , a1 ) = 12 and R(s2 , a2 ) = 11. Thus, there are N = 4 available decision rules at each step (see Table 1). For instance, decision rule δ2 consists in applying action a1 in states s1 and action a2 in state s2 . In this example, the functions f i are given by:

The t-step value of a policy of the form (δi , π) is defined recursively by v(δi ,π) 0 = (0, . . . , 0) and v(δi ,π) t = f i (vπ t-1 ), where f i : Rn →Rn is the update function which associates to any vector x = (x1, . . . , xn) the vector (f i1 (x), . . . , f in (x)) where f i j (x) = R(sj , δi (sj )) + ∑nk=1 T (sj , δi (sj ), sk )xk .

Given a finite horizon H, the optimal policy π∗ can be found thanks to the following Bellman equations:

The solution of these equations can be reduced to a vectorweighted optimal path problem in a particular graph, with update functions (the f i 's) on the arcs allowing the propagation of policy values over nodes. Indeed, consider a graph where each node δi t corresponds to decision rule δi at step t, and each arc of the form (δi t , δj t-1 ) corresponds to a transition between decision rules. Moreover, nodes δj1 , j = 1 . . .N are connected to a sink denoted 0, and a source denoted H is connected to nodes δjH , j = 1 . . .N. Hence, any path from node δi t to node 0 corresponds to a t-step policy where decision δi is applied first. We name that graph the decision rule graph. Note that the Bellman update via f i 's is nicely separable (f i j 's can be computed independently) and therefore the vector value of a path can be obtained componentwise (state by state) as usual in classic MDP algorithms. This property will be exploited later on for Algebraic MDPs. Coming back to Example 1 and assuming that H = 2, there are 16 available policies (all possible combinations of two successive decision rules). The corresponding graph is pictured on Figure 1.

For all i = 1 . . . n, function f i is associated to every arc issued from δi t , t = 1 . . .H. Moreover, the identity function is assigned to every arc issued from H. Thus, the optimal policy can be computed thanks to backward induction on the decision rule graph, by propagating the value (0, . . . , 0) ∈ Rn from the sink 0 corresponding to the empty policy. In Example 1, backward induction leads to the labels indicated in Table 2. The optimal policy value can be recovered on node H. The optimal vector value is (17, 23) and the optimal policy (recovered from bolded values in Table 2) is (δ4 2 , δ1 1 ).

In the next section, we show how to generalize this approach to a wide range of MDPs. In this concern, we introduce the notion of algebraic Markov decision process.

3 Algebraic Markov Decision Process

We now define a more general setting to model rewards and uncertainty in MDPs. Our approach relies on previous works aiming at generalizing uncertainty measurement and expectation calculus. Our rewards take values in a set V and we use plausibility measures 1 [Friedman and Halpern, 1995] to model uncertainty. A plausibility measure Pl is here a function from 2W (the set of events) to P, where W is the set of worlds, P is a set endowed with two internal operators ⊕P and ⊗P (the analogs of + and × in probability theory), a (possibly partial) order relation ⪰P , and two special elements 0P and 1P such that 1P ⪰P p ⪰P 0P for all p ∈ P. Furthermore, Pl verifies Pl(∅) = 0P , Pl(W) = 1P and Pl(X) ⪰P Pl(Y ) for all X, Y such that Y ⊆ X ⊆ W. We assume here that Pl is decomposable, i.e. Pl(X ∪ Y ) = Pl(X) ⊕P Pl(Y ) for any pair of disjoint events X and Y . To combine plausibilities and rewards, we use the generalized expectation proposed by [Chu and Halpern, 2003a]. This generalized expectation is defined on an expectation domain (V, P, ⊞, ⊠) 2

1 This notion must not be confused with the Dempster-Shafer notion of plausibility function.

2 In [Chu and Halpern, 2003a], an expectation domain is written (U, P, V, ⊞, ⊠). This structure can be simplified here since V = U.

where ⊞ : V × V → V and ⊠ : P × V → V are the counterparts of + and × in probabilistic expectation, and the three following requirements are satisfied: (x⊞y)⊞z = x⊞(y⊞z), x ⊞ y = y ⊞ x, 1P ⊠ x = x. For any plausibility distribution Pl on V having its support in X, the generalized expectation

writes: ∑⊞x∈X Pl(x) ⊠ x. An Algebraic MDP (AMDP) is described as a tuple (S, A, T, R), where T and R are redefined as follows:

• T : S × A → Pl(S) is a transition function, where Pl(S) is the set of plausibility measures over S valued in P ,
• R: S ×A → V is a reward function giving the immediate reward in V .

Consistently with the standard Markov hypothesis, the next state and the expected reward depend only on the current state and the action taken. In particular, plausibility distributions of type T(s, a) are (plausibilistically) independent of the past states and actions. This plausibilistic independence refers to the notion introduced by [Friedman and Halpern, 1995] and leads to the following algebraic counterpart of the probabilistic independence property: Pl(X ∩ Y ) = Pl(X) ⊗P Pl(Y ) for any pair X, Y of independent events.

In this setting, rewards and plausibilities take values in two semirings. Roughly speaking, a semiring is a set endowed with two operators allowing the combination of elements (rewards or plausibilities) together. We now recall some definitions about semirings.

Definition 1 A semiring (X,⊕,⊗, 0, 1) is a set X with two binary operations ⊕ and ⊗, such that:

• (A1) (X, ⊕, 0) is a commutative semigroup with 0 as neutral element (i.e., a⊕b = b⊕a, (a⊕b)⊕c = a⊕(b⊕c), a⊕0 = a). (A2) (X, ⊗, 1) is a semigroup with 1 as neutral element, and for which 0 is an absorbing element (i.e., (a ⊗ b) ⊗ c = a ⊗

(b ⊗ c), a ⊗ 1 = 1 ⊗ a = a, a ⊗ 0 = 0 ⊗ a = 0). (A3) ⊗ is distributive with respect to ⊕ (i.e., (a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c), a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)).

A semiring is said to be idempotent when (X,⊕) is an idempotent commutative semigroup (i.e., a commutative semigroup such that a ⊕ a = a). The idempotence of ⊕ enables to define the following canonical order relation ⪰X:

From now on, we will assume that the rewards are elements of an idempotent semiring (V,⊕V ,⊗V , 0V , 1V ). Operator ⊕V is used to select the optimal values in V , whereas operator ⊗V is used to combine rewards. In classic MDPs with the total reward criterion, ⊕V = max and ⊗V = +.

Moreover the structure (P,⊕P ,⊗P , 0P , 1P ) is also supposed to be a semiring. Operator ⊕P allows to combine the plausibilities of disjoint events and operator ⊗P allows to combine the plausibilities of independent events. Note that the assumption that (P, ⊕P , ⊗P , 0P , 1P ) is a semiring is not very restrictive since [Darwiche and Ginsberg, 1992], who use similar properties to define symbolic probability, have shown that it subsumes many representations of uncertainty, such as probability theory, possibility theory and other important calculi used in AI.

Now that the general framework has been defined, we can follow the usual approach in MDPs and define a value function for policies. The accumulated reward for a history γ = (st, at, st-1, . . . , a1, s0) is R(γ) = ⊗ti=1 R(si, ai). For an initial state s, a t-step policy π = (δt, . . . , δ1) induces a plausibility measure Plπt (s, ·) over histories. Such a policy will be evaluated with respect to the generalized expectation of accumulated reward, which writes:

The policies can be compared with respect to the componentwise dominance relation ⪰V n between vectors in V n :

Most of the MDPs introduced previously in the literature are instances of our algebraic MDP:

- In standard MDPs, the underlying algebraic structure on P is (P,⊕P ,⊗P , 0P , 1P ) = ([0, 1],+,×, 0, 1), and operators ⊞ = + and ⊠ = × are used to define the classic expectation operation. When rewards are defined on (V, ⊕V , ⊗V , 0V , 1V ) = (R, max, +, -∞, 0) where R = R ∪ {-∞}, we recognize the total reward criterion. With (R, max, +γ , -∞, 0) (where x +γ y = x + γy), we recognize the weighted total reward criterion. With (R, max, +H, -∞, 0) where a+H b = 1H a+b, we recognize the average reward criterion assuming that there is an initial dummy step with zero reward.

- Qualitative MDPs, introduced in [Bonet and Pearl, 2002], are AMDPs where the rewards and the plausibility measures are defined on the semiring of two-sided infinite formal series, which is a subset of the extended reals [Wilson, 1995].

In order to assign functions to the arcs in the decision rule graph, we first define f i j : V n → V (the update function after applying decision rule δi in state sj ), for all x ∈ V n , by:

Then, for any decision rule δi , we define the update function f i : V n → V n which associates to any vector x ∈ V n the vector (f i1 (x), . . . , f in (x)).

Dynamic consistency in AMDPs is guaranteed by specific properties on functions f i . The fulfillment of these properties strongly relies on the following conditions:

Conditions (C1) and (C2) are two distributivity properties entailing a kind of additivity of ⪰V w.r.t. ⊠ and ⊞ (i.e., x ⪰V y ⇒ (z ∗ x ⪰V z ∗ y) for ∗ ∈ {⊠,⊞}). Condition (C3) enables the reduction of lotteries. Condition (C4) enables to isolate a sure reward in a lottery and is similar to the distributivity axiom used in [Luce, 2003]. Condition (C5) is a distributivity condition as in classic expectation. We now establish a monotonocity result that will be used later (Prop.

3) to justify a dynamic programming approach.

Proposition 1 If (C1) and (C2) hold, then f i is nondecreasing for all δi ∈ ∆, i.e

Proof. Let x, y in V n s.t. x ⪰V n y. For sj ∈ S, we have ∑⊞k T(sj , δi (sj ), sk ) ⊠xk ⪰V ∑⊞k T(sj , δi (sj ), sk ) ⊠yk by (C1) and (C2). Thanks to distributivity of ⊗V over ⊕V , we have f i j (x) ⪰V f i j (y). Therefore, f i (x) ⪰V n f i (y).

Moreover, the value of a policy π can be computed recursively thanks to the following result:

Proposition 2 Let π = (δi , π′ ) a (t + 1)-step policy, and assume that vπ 0 = (1V , . . . , 1V ). If (C3), (C4) and (C5) hold, then vπ t+1 = f i (vπ′ t ) for all t ≥ 0.

Proof. Let s be a state and a denote δi (s). We note γt = (st, at, . . . , a1, s0) and γt+1 = (s, a, st, at, . . . , a1, s0). We have:

In order to establish the algebraic version of Bellman equations, we define the subset of maximal elements of a set with respect to an order relation ⪰ as:

Furthermore, we denote P ∗ (X,⪰) the set {Y ⊆ X : Y = M(Y,⪰)}. When there is no ambiguity, these sets will be denoted respectively M(Y ) and P ∗ (X). Besides, for any function f : V n → V n , for all X ∈ P ∗ (V n ), f(X) denote {f(x) : x ∈ X}.

with x⊗V y = (x1 ⊗V y1, . . . , xn ⊗V yn). Hence, the algebraic generalization of Bellman equations (1) writes:

where f iM : P ∗ (V n ) → P ∗ (V n ) is defined by f iM (X) = M(f i (X)) for all X ∈ P ∗ (V n ).

4 Generalized path algebra for AMDPs

Following the construction proposed in Section 2, a decision rule graph can be associated to an AMDP. Clearly, solving algebraic Bellman equations amounts to searching for optimal paths with respect to the canonical order associated to ⊕. We now show how to solve this problem.

Consider the set F of functions from P ∗ (V n ) to P ∗ (V n ) satisfying for all f ∈ F, X ∈ P ∗ (V n ), Y ∈ P ∗ (V n ):

The ⊕ operation on P ∗ (V n ) induces a ⊕ operation on F defined, for all h, g ∈ F and X ∈ P ∗ (V n ), by:

Let ◦ denote the usual composition operation between functions, id the identity function, and (for simplicity) 0 the constant function everywhere 0. It has been shown by [Minoux, 1977] that the algebraic structure (F,⊕, ◦, 0, id) is a semiring. We now prove that update functions f iM 's belong to F.

Proof. For any δi , we have f iM (0) = 0 since ∑⊞i pi⊠0V = ∑⊞i pi ⊠ (0V ⊗V 0V ) = 0V ⊗V (∑⊞i pi ⊠ 0V ) = 0V by (C4) and absorption. Now, we show that f iM (X ⊕ Y ) = f iM (X) ⊕ f iM (Y ), ∀X, Y ∈ P ∗ (V n ). Consider X, Y in P ∗ (V n ). First, we have f i (M(X ∪ Y )) ⊆ f i (X ∪ Y ) (∗). Second, we prove that M(f i (X ∪ Y )) ⊆ f i (M(X ∪ Y )) (∗∗). Let z ∈ M(f i (X ∪ Y )). Then it exists w ∈ X ∪ Y such that f i (w) = z. If w ∈ M(X ∪ Y ) then z ∈ f i (M(X ∪ Y )). If w ̸∈ M(X ∪ Y ) then it exists w∗ ∈ M(X ∪ Y ) such that w∗ ≻V w. As f i is nondecreasing, we have f i (w∗ ) ⪰V f i (w). By assumption, f i (w) ∈ M(f i (X∪Y )), therefore f i (w∗ ) = f i (w). Finally, z ∈ f i (M(X ∪ Y )) since z = f i (w∗ ). By (∗) and (∗∗), we have M(f i (X ∪ Y )) ⊆ f i (M(X ∪ Y )) ⊆ f i (X ∪ Y ). Therefore M(f i (X ∪ Y )) = M(f i (M(X ∪ Y ))), which means, by definition, that f iM (X⊕Y ) = f iM (X)⊕f iM (Y ).

Propositions 2 and 3 prove that the algebraic generalization of Jacobi algorithm solves algebraic Bellman Equations (3) and (4) [Minoux, 1977]. Thanks to the particular structure 3 of the decision rule graph, the Jacobi algorithm takes the following simple form:

ALGEBRAIC JACOBI ALGORITHM

1. V0 ← 1; t ← 0
2. Qit = 0, ∀t = 1 . . .H, i = 1 . . .N
3. repeat
4. t ← t + 1

1. Vt ← ⊕Ni=1 Qit 7. until t =H

We recognize a standard optimal path algorithm on the decision rule graph valued with functions f iM . When the iteration has finished, Vt is the set of generalized expected accumulated rewards at step t associated to optimal paths. The above algorithm is not efficient since lines 5 and 6 require to consider N = mn decision rules in the computation of the Bellman update. Actually, the complexity of the algorithm can be significantly improved. Indeed, remark that ∪Ni=1 {f i j } = ∪mk=1{gk j }, where gk j (x) = R(sj , ak ) ⊗V ∑⊞i=1...n T (sj , ak , si ) ⊠ xi, and that ∀v ∈ V n , ∪Ni=1{f i (v)} = ∪mk=1{gk 1 (v)}×..×∪mk=1{gkn (v)}. Since the maxima over a Cartesian product equals the Cartesian product of maxima over components, we have ⊕Ni=1 f iM (Vt-1) = ⊕v∈Vt-1 (⊕mk=1 gk 1 (v) × .. × ⊕mk=1 gkn (v)). Hence, lines 5 and 6 can be replaced by:

3 The graph is layered; update functions labelling arcs issued from a same node are identical and invariant from a layer to another.

5.1. Vt ← ∅ 5.2. for v ∈ Vt-1 do 5.3. for j = 1 to n do 5.4. for k = 1 to m do qk tj ← gk j (v) 6.1. Vtj ← ⊕mk=1 qk tj 6.2. endfor 6.3. Vt ← Vt ⊕ (Vt1 × .. × Vtn) 6.4. endfor

This algebraic counterpart of backward induction runs in polynomial time when the reward scale is completely ordered and algebraic operators can be computed in O(1).

5 Examples

To illustrate the potential of the algebraic approach for MDPs, we now consider decision models that have not yet been investigated in a dynamic setting.

• Qualitative MDPs. In decision under possibilistic uncertainty, [Giang and Shenoy, 2001] have recently studied a new qualitative decision model (binary possibilistic utility), allowing to handle weak information about uncertainty while improving the discrimination power of qualitative utility models introduced by [Dubois and Prade, 1995]. The latter have been investigated in sequential decision problems by [Sabbadin, 1999]. We show here that the former can be exploited in sequential decision problems as well.

Possibilistic uncertainty is measured on a finite qualitative totally ordered set P, endowed with two operators ∨ and ∧ (max and min respectively). We denote 0P (resp. 1P ) the least (resp. greatest) element in P. The structure (P, ∨, ∧, 0P , 1P ) is a semiring.

In Giang and Shenoy's model, rewards are valued in an ordered scale (UP , ⪰) where UP = {〈λ, µ〉 : λ ∈ P, µ ∈ P, λ ∨ µ = 1P } and 〈λ, µ〉 ⪰ 〈λ′ , µ′ 〉 ⇔ (λ ≥ λ′ and µ ≤ µ′ ). The relevant semiring is here (V, ⊕V , ⊗V , 0V , 1V ) where:

Note that ⊕V and ⊗V are operators max and min on UP .

The binary possibilistic utility model is a generalized expectation with operators ⊞ and ⊠ taken as componentwise ∨ and ∧ respectively. Note that this criterion takes values in UP . Thanks to distributivity of ∨ (resp. ∧) over ∧ (resp. ∨), conditions (C1) to (C5) hold, which proves that algebraic backward induction yields the value of optimal policies.

• Multicriteria MDPs. In planning problems, different aspects (time, energy, distance...) enter into the assessment of the utility of an action, and often these aspects cannot be reduced to a single scalar reward. This shows the practical interest of investigating MDPs with multicriteria additive rewards and multicriteria comparison models. As an example, consider the following multicriteria decision model. Let Q denote the set of criteria and ⪰Q a (possibly partial) order relation over Q (reflecting the importance of criteria). Following [Grosof, 1991] and [Junker, 2002], we denote ≻G the following strict order relation between vectors:

The interest of such a definition is to unify in a single model both the lexicographic order (when ⪰Q is a linear order) and the Pareto dominance order (when ⪰Q= ∅).

In this case, the relevant semiring structure on rewards is defined by (neutral elements are omitted here):

Hence, such a reward system can easily be inserted in the classical probabilistic setting. When the generalized expectation is chosen as the componentwise (usual) expectation, conditions (C1) to (C5) hold, which proves that algebraic backward induction yields the value of optimal policies.

6 Conclusion

We have introduced a general approach for defining solvable MDPs in various contexts. The interest of this approach is to factorize many different positive results concerning various rewards systems, uncertainty and decision models. Once the structure on rewards, the representation of uncertainty and the decision criteria have been chosen, it is sufficient to check that we have two semirings on V and P and that conditions (C1) through (C5) are fulfilled to justify the use of an algorithm "à la Jacobi" to solve the problem. It is likely that this result generalizes to the infinite horizon case, provided a suitable topology is defined on the policy valuation space.

Remark that, despite its generality, our framework does not include all interesting decision theories under uncertainty. For instance, in a probabilistic setting, the RDEU model (as well as other Choquet integrals) cannot be expressed under the form of the generalized expectation used in the paper. Actually, RDEU is known as a dynamically inconsistent model [Machina, 1989; Sarin and Wakker, 1998] and it is unlikely that constructive algorithms like backward induction are appropriate. A further specific study for this class of decision models might be of interest.