TRABAJOS DE ESTADISTICA Y DE INVESTIGACION OPERATIVA VoI. 29, Cuad. 1, Madrid, 1978

NOTAS

U N A N O T A SOBRE S U S T I T U C I O N DE A C C I O N E S EN P O L I T I C A S

M A R K O V I A N A S H O M O G E N E A S CON D E S C U E N T O

Francisco Benito Institut ffir Operations Research F, idgen6ssische Technische Hochschule Ziirich

RESUMEN

Para modelos de Markov con finitos estados y acciones, en hori- zonte ilimitado y con descuento, se defmen polfticas equivalentes y acciones sustituibles y se da un procedimiento para determinarlas. Como aplicaci6n se puede obtener el conjunto de polflicas 6ptimas, como equivalentes a una 6ptima dada. Se ilustra con un ejemplo num6rico.

Introducci6n.

Consideremos un modelo de Markov M con m~mero finito N de estados s, s = 1 . . . . . N. Peri6dicamente, por ejemplo una vez al dfa, se observa el estado actual del sistema correspondiente al modelo y se elige una acci6n a de un conjunto finito A de acciones posibles. Dependiendo del estado actual s y de la acci6n elegida a, se obtiene una ganancia inmediata qa< + oo y el sistema s evoluciona a un nuevo estado s', siendo Psas h probabilidad del tr~nsito a un estado s' concreto. Finalmente, el factor de descuen to /~ ,0< /3< 1, representa el valor actual de la ganancia unidad a recibir despu6s de un periodo. Para este modelo se busca la polflica clue hace m~dma la esperanza matem~tica de la ganancia total en horizonte ilimitado.

Una pol[tica (determinista) asigna una acci6n a cada estado. Se llama marko- v/aria si en cada fecha h acci6n depende s61o del estado actual, sin referencia

97

a los estados anteriores per los que ha evolucionado el sistema. Si la acci6n para cada estado es independiente de la fecha, la pofftica es homog3nea. En adelante al hablar de polftica se entender~ una polftica markoviana y homog~nea, salvo que se indique expresamente otra cosa.

La notaci6n y terminologia se adapta en 1o posible a [1], Cap. 7.

PoHticas equivalentes.

DeIinici6n: Dos polfticas markovianas homog6neas del modelo M se llaman equivalentes cuando los valores relatives de los estados son id6nticos para ambas.

En el ejemplo de la Tabla 1 la polftica (2, 3, 1) - q u e elige para los estados s = 1, s = 2, s = 3 las acciones a = 2, a = 3, a = 1 respectivamente- y la polftica (1, 2, 3) son equivalentes. Los valores relatives de los estados en ambos cases son: vl = 36, v2 = 44, v3 = 32.

En case de existir m~is de una, es evidente que todas las polRicas 6ptimas del modelo M son equivalentes entre sf.

Teorema: Dadas dos polfticas markovianas homogdneas del modelo M equi- valentes entre si, cualquier politica resultante de sustituir en uno o mds estados las acciones de una politica per ias correspondientes de la otra, es equivalente a la s dadag

En el ejemplo de la Tabla 1 sustituyendo en los estados s = 1 y s = 3 las acciones de la polfiica (2, 3, 1) per las de (1 ,2 , 3) obtenemos una nueva polftica equivalente a 6stas: (1,3, 3).

La polftica resultante es una mezcla de las previas: para una parte de los estados se aplican las acciones sefialadas per una polftica y para el resto los de la otra. De mode obvio se define la mezcla de m~is de dos polfticas. Consecuencia inmediata del teorema es que h mezcla de un nfimero arbitrario de polfticas equivalentes entre sf, es una polftica equivaJente a elias.

Demostraei6n del teorema: Sean dos polfticas (al, a2 . . . . . aN), (al , a-2 . . . . . aN) con valores relatives de los estados vl, v 2 , . . . ,v N. Sin p~rdida de generalidad consideremos la polftica resultante de sustituir acciones en un s61o estado - c o m e hay un nfimero finite de estados las demos sustituciones son reiteraci6n finita de una sustituci6n as f - y sea el estado s = 1 - e n case contrario basta reordenar los estados. Se cumple (rid. [1]):

N (1) v i=q~i +~"/=1 ~" Pi/air~' i = 1,. . . , N

- N (2) Vi = q~t + ~"/=1 ~" Pi/~ v/, i = 1,. .. , N

98

Consideremos la polftica no homog6nea que coincide en el primer periodo con (al , a2 . . . . . aN) y despu6s con (al, a2 . . . . . aN). Los valores relativos

t t t

vl, v 2 , . . . , v N ser~n:

, N

/ - t

(3) N

e a t ai vi = qi + [3 .~ PC vl, i = 2 . . . . . N

]-1

Evidentemente, de (2) - c o n i = 1 - resulta v ' t = v l , y de (1): v ~ = v i ,

i = 2 . . . . . N.

La sustituci6n durante un per fodo de la acci6n al por la al no modifica los valores relativos. Repitiendo en cada peffodo este razonamiento se concluye que la polRica homog6nea (a'l, as . . . . . aN) equivale a l a s dadas.

Otros modm de demostrar la equivalencia se recogen en el Anexo.

Accionm sustituibles.

at y ~t son acciones susti tuibles en el estado s = 1, con respecto a la polftica (at , a2 . . . . . aN).

N6tese que v~ en (3) es el valor correspondiente a la acci6n at e n d estado s = 1 en el test que utiliza el algoritmo de Howard al tratar de mejorar la polftica (al , a2 . . . . . aN), y coincide con el valor relativo que tenfa ese estado.

Esto permite descubrir las acciones sustituibles en cada estado, con respecto a una polltica (at , a2 . . . . . aN) con valores relativos v t , v~ . . . . . v N. En el estado s = i las acciones a~ que cumplan

qor+ N _*t i ~/Z~,i / v!=v i

son sustituibles con a i. El conjunto de estas acciones sea A 1 (evidentemente

a i E A i ) .

En el ejemplo de la Tabla 1, para la polft ica(2, 3, 1)obtenemos los siguientes conjuntos de acciones sustituibles: At = { 2, 1 ,4 I, A2 = 13, 2, 4 I, A a = I 1, 3, 4 I.

Teniendo en cuenta que una polltica como la (h-t, a'2 . . . . . aN), equivalente a la (at , a2 . . . . . aN), se puede obtener a partir de ~sta mediante N sucesivas sustituciones: at -* a t , a2 -~ a2 . . . . . aN -~ aN entre acciones sustituibles en cada estado, se deduce que el conjunto de las polfticas equivalentes a la (at , a2 . . . . . a N) es el producto cartesiano de los conjuntos de acciones sustituibles: A 1 o ,42* . . . ~

99

Estado i

Acci6n a

1

2 3 4

1

2 3 4

1

2 3 4

=

1

0 0

1/2

1

0 0

1/2

Probabilidades de t_r~sito a

P#

1 / = 2 / = 3

0 0

1 0 0 1

1/2 1/2

0 0

1 0 0 I

0 1/2

0 0 1 0

0 1 1/2 0

Ganancia inmediata a

qi

18 14 0

17

0 22 28 27

14 0

16 12

Tabla 1: Parlmetros de un modelo con N = 3, A =I 1 ,2 ,3 ,4}, ~ = 1/2.

Una aplicaci6n inmediata es la obtenci6n del conjunto de polfficas 6ptimas, como equivalentes a una 6prima dada.

En el ejemplo de la Tabla 1 hay en total 27 polfficas: [ 2, 1, 4I| l 3, 2, 4 1 | | I 1, 3, 4 I, equivalentes a la (2, 3, 1). Todas elias son 6ptimas.

En la pr~ctica, la bfisqueda de acciones sustituibles tiene interns para ampliar las opciones disponibles sin modificar el valor de la funci6n objetivo.

ANEXO.

Otro razonamiento que utiliza conceptos usuales en la teorfa de modelos * * * de markovianos finitos, consiste en calcular los valores relativos vt , v 2 . . . . . v N

la polffica homog~nea (at, a2 . . . . . aN):

2v ~ �9

1=1

N V *. ai ai *

, = q i + ~ .Y Pi] b ' 1=1

i = 2 . . . . . N

Utilizando (1) y (2) resulta:

100

iv 71 p (v/ - v 7 )

N ai ai ai . V i - v ~ = q i --qi + fl .~ Pi] (I~]--V]),

I=1

Con la notaci6n:

obtenemos

i=2 . . . . . N

b-l i = 1 __/Pl/ , A v i = v i - v ~ ., i= 1 . . . . . N y p~ . - \ p~ ! ,

i= 2 N

N (A1) A v i = 0 + f l .~ pi/Av/, i = 1 , 2 . . . . . N

1"1

donde Av i son los valores relativos en una polftica con ganancia inmediata nula, y por tanto, Av i= O, i = 1, 2 . . . . . N.

Analfticarnente se llega a la misma conclusi6n ya que (AI) define el punto fijo de una contracci6n en R s . Usando valores absolutos (~/> 0, p~//> 0):

N N IAvil</3 / * .?, Pi/ IAv/I<<'f3 ~-, p~max l lAvil l : j=l j

N pues .Z p~ = 1,

I=1

N =~marx l[Avrll /~1P;'=flrrlraXl lAvrll

i = l , 2 , . . . , N . De aquf:

max I [AFr]I ~</3 max { IAvrl I r r

(1 --/~)max l lAvr l l~<0 r

y c o m o ( 1 - - ~ ) > 0 s e e o n c l u y e max I I A v r l l = 0 , o sea r = l , . . , N

Avr=O, r = l , 2 . . . . . N.

BIBLIOGRAFIA.

[1] HOWARD, R. A.: Dynamic Programming and Markov Processes, Wiley, New York (1960).

101