77. In a Markov decision problem, another criterion often used, different than the expected average return per unit time, is that of the expected discounted return. In this criterion we choose a number α, 0 ∞

i=0αiR(Xi , ai)] (that is, rewards at time n are discounted at rate αn).

Suppose that the initial state is chosen according to the probabilities bi . That is, P{X0 = i} = bi , i = 1, . . . , n For a given policy β let yja denote the expected discounted time that the process is in state j and action a is chosen. That is,

Argue that yja can be interpreted as the expected discounted time that the process is in state j and action a is chosen when the initial state is chosen according to the probabilities bj and the policy β, given by

is employed.
Hint: Derive a set of equations for the expected discounted times when policy β
is used and show that they are equivalent to Equation (4.38).

(d) Argue that an optimal policy with respect to the expected discounted return criterion can be obtained by first solving the linear program

where the y∗
ja are the solutions of the linear program.

Transcribed Image Text:

Yja Eg "Xiana) L=0 where for any event A the indicator variable I is defined by [1, if A occurs IA = otherwise (a) Show that = Ln=0 or, in other words, ayia is the expected discounted time in state / under . (b) Show that = ja 1 1 a jabi+ayia Pij (a) i a