1. Educación

Modelos de control semi-Markovianos con distribución del tiempo
de permanencia parcialmente conocida bajo un costo descontado
Luz del Carmen Rosas Rosas, J. Adolfo Minjárez Sosa
-
Resumen—En este trabajo se aborda una clase de modelos
de control semi-Markovianos con espacios de estado y de
control de Borel y costos posiblemente no acotados, donde la
distribución F depende de un parámetro desconocido y
posiblemente no observable por el controlador y tal que puede
cambiar entre etapas. El sistema es modelado como un juego
contra la naturaleza, el cual es un caso particular de un sistema
de control minimax. El objetivo es demostrar la existencia de
estrategias minimax bajo un criterio de costo descontado.
Palabras clave. Procesos de control semi-Markovianos; Criterio de
costo descontado; Sistema de control minimax; Juegos contra la
naturaleza.
I. INTRODUCCIÓN
LOS modelos de control semi-Markovianos (MCSMs) son
una clase de modelos de control estocástico en tiempo
continuo donde la distribución de los tiempos entre épocas
(de decisión) consecutivas o tiempos de permanencia es
arbitraria. Generalmente, tal distribución depende del estado
y el control seleccionados por el controlador en cada época
de decisión. No obstante, en este trabajo suponemos que
depende además de un parámetro desconocido y
posiblemente no observable que puede cambiar de una etapa
a otra; en ese sentido, la distribución del tiempo de
permanencia es parcialmente conocida. Explícitamente, a fin
de estudiar este problema de control óptimo semiMarkoviano, introducimos aquí una clase de MCSMs
minimax conocidos como juegos contra la naturaleza. La
idea consiste en suponer que el controlador tiene un
oponente (la “naturaleza”), de manera que en cada época de
decisión Tn , una vez que el controlador elige su acción, la
naturaleza selecciona un parámetro de determinado conjunto
 , del cual lo único que se sabe es que podría depender del
estado del sistema y la acción previamente seleccionada. Así
pues, el propósito del controlador consiste en minimizar el
costo máximo generado por la naturaleza, por lo cual deberá
seleccionar las acciones que garanticen el mejor
funcionamiento en la peor situación posible. Ante tales
circunstancias, nuestro objetivo es demostrar la existencia de
estrategias minimax bajo un criterio de costo descontado.
II. DESCRIPCIÓN
Modelo de control semi-Markoviano.
Consideramos el modelo de control semi-Markoviano
SM :  X , A, A x  : x  X , Q, F , D, d 
tal que satisface las condiciones siguientes: ambos espacios,
de estado X y de control A , son de Borel; a cada x  X
asociamos un subconjunto medible no vacío A x   A ,
cuyos elementos son los controles (acciones) admisibles
para el controlador cuando el sistema se encuentra en el
estado x . Suponemos que el conjunto de pares estadoacción admisibles
K A :  x, a  : x  X , a  A x 
es un subconjunto de Borel de X  A . La ley de transición
Q  es un kérnel estocástico sobre X dado K A y
F  x, a,   es la función de distribución del tiempo de
permanencia en el estado x  X cuando es elegido el
control a  A x  , la cual depende de un parámetro
desconocido posiblemente no observable y que pertenece a
determinado conjunto  x, a  . Finalmente, las funciones de
costo D y d son reales en K A , medibles y posiblemente no
acotadas.
Interpretación del SM.
Al tiempo de la n -ésima época de decisión Tn , el sistema
está en el estado xn  x y el controlador elige un control
an  a  A x . Luego el sistema permanece en ese estado
durante un tiempo aleatorio no negativo  n 1 con
distribución F , y ocurre lo siguiente: 1) se produce un costo
inmediato D x, a ; 2) el sistema salta a un nuevo
estado x n1  y de acuerdo a una ley de transición Q x, a ;
y 3) se produce un nuevo costo debido al tiempo de
permanencia en el estado x , cuya razón de costo es d  x, a ;
y una vez en el estado y el proceso se repite. Las épocas de
decisión son Tn : Tn1   n (n  N )
y T0 : 0, y la
variable aleatoria  n1 : Tn1  Tn es llamada el tiempo de
[email protected] o [email protected]
Departamento de Matemáticas, Universidad de Sonora.
permanencia en el estado
xn .
De acuerdo a la definición e interpretación del modelo de
control SM, el parámetro puede cambiar de una etapa a otra.
Más aún, el costo por etapa, definido en términos de las
funciones de costo D y d , es una función c x, a, ,
x  X , a  A x ,    x, a . De modo que, el problema
de control óptimo para el controlador es encontrar una
estrategia de control dirigida a minimizar la secuencia de
costo
c xn , an ,  n nN , xn  X , an  A x,  n   xn , an ,
0
sobre un horizonte infinito usando un criterio descontado.
No obstante, en cada época de decisión la única información
respecto al parámetro  n es que pertenece al conjunto
 xn , a n , los procedimientos usuales para resolver el
problema de control óptimo semi-Markoviano no son
accesibles para el controlador.
Modelo de Control semi-Markoviano Minimax.
A fin de proponer una solución razonable modelamos el
problema de control semi-Markoviano previamente descrito
como un sistema minimax, en cuyo caso suponemos que el
controlador tiene un oponente que selecciona el parámetro
 en cada época de decisión, lo cual a su vez, determina la
distribución del tiempo de permanencia F . Para tal efecto,
consideramos un modelo de control minimax de la forma
el sistema permanece en el estado x durante el tiempo
aleatorio  n 1 con distribución F  x, a, . Luego, el
sistema evoluciona de acuerdo al modelo SM. Ahora, debido
a que el costo por etapa c x, a,  depende del parámetro
seleccionado precisamente en cada etapa, el propósito del
controlador consiste en minimizar el máximo costo generado
por la naturaleza.
Estrategias.
Las acciones o controles aplicados, tanto por el controlador
como por su oponente en las épocas de decisión son
seleccionados de acuerdo a reglas conocidas como
estrategias de control definidas como sigue. Sean H0 : X
H0' : K A ; mientras que, para cada n  N , sean
y
H n : K n  X y Hn' : K n  K A . De modo que, los
elementos típicos de H n y H n' toman las formas
siguientes, respectivamente:
hn : ( x0 , a0 , 0 , , xn1, an1, n1, xn )
y
hn' : (hn , an ) .
Una estrategia para el controlador es una sucesión
  { n } de kérneles estocásticos sobre A dado H n tal
que
 ( A( x n ) hn )  1
MSM :  X , A, , K A , K , Q, F , D, d ,
donde X , A,
Q,
F,
D,
d
y K A son como se
definieron en SM, y  es el espacio de acción del oponente
y el cual suponemos es un espacio de Borel. El conjunto
K
B  X  A  
es el conjunto de restricción para el
oponente. De aquí, para cada  x, a   K A suponemos que
 x, a  :    :  x, a,   K
es un subconjunto medible no vacío de  que representa el
conjunto de acciones admisibles para el oponente cuando el
estado es x  X y el controlador elige la acción a  A x .
De acuerdo a este escenario, F  x, a,   es la función de
distribución del tiempo de permanencia en el estado x  X
cuando es elegido el control a  A x  y el oponente
selecciona    x, a . Además, el costo por etapa c es una
función real en K , medible y posiblemente no acotada, y
que está definida en términos de las funciones de costo D y
d de acuerdo al criterio de optimalidad de interés particular.
Por lo tanto, el problema de control semi-Markoviano puede
ser visto como un juego contra la naturaleza definido
mediante el modelo de control minimax MSM. De hecho,
una vez que el controlador selecciona la acción a n  a
cuando el sistema está en el estado x n  x, el oponente (la
“naturaleza”), selecciona un parámetro  n     x, a  y
 hn  H n , n  N 0 .
Denotaremos por  A al conjunto de todas las estrategias
para el controlador, y por F A al subconjunto de todas las
estrategias estacionarias. Identificaremos cada estrategia
estacionaria   F A con alguna función medible
f :XA
tal que
 n  hn 
está concentrado en
f  x n   A x n  para todo hn  H n y n  N 0 , tomando la
forma   { f , f , }. Asimismo, una estrategia para el
oponente
es
una
sucesión
estocásticos sobre  dado
H n'
 '  { n ' }
de
kérneles
tal que
 n ' (( x n , a n ) hn' )  1  hn'  H n' , n  N 0 .
Denotaremos por   al conjunto de todas las estrategias
para el oponente, y por F    al conjunto de todas las
estrategias estacionarias. Análogamente, identificaremos
cada estrategia estacionaria  ' F con alguna función
 
medible g : X  A   tal que  n '  hn' está concentrado
en g  xn , an    xn , an  para todo hn'  H n' y n  N 0 .
Criterio Minimax.
Para estudiar el criterio descontado supondremos que los
costos son descontados en forma continua, es decir, para un
factor de descuento   0 , un costo C producido al tiempo
t es equivalente a un costo C exp( t ) al tiempo 0. Luego,
para cada ( x, a,  )  K definimos el costo por etapa (criterio
descontado) como
Hipótesis 2. (a) Las funciones de costo D( x, a) y
son semicontinuas inferiormente (s.c.i.) en K A . Más aún,
existe una función continua W : X  1,  y una constante
M 0  0 tal que
c( x, a,  ) : D( x, a)
 d ( x, a)
  exp(s)dsF (dt x, a,  ).
(1)
Más aún, para ( x, a,  )  K , sea


  ( x, a,  ) : exp( s) F (ds x, a,  )
(2)
maxD( x, a), d ( x, a)  M 0W ( x)
  ( x, a,  ) :
1    ( x, a,  )

De aquí se deduce que para cada ( x, a,  )  K , el costo por
etapa (1) toma la forma
(3)
c( x, a,  )  D( x, a)    ( x, a,  )d ( x, a).
Por otra parte, para   0 fijo, se define el costo descontado
esperado total, para cada estado inicial x  X y cada par de
estrategias ( ,  ' )   A    , como
 ' 
V ( x,  ,  ' ) : E x


 exp( s)c( x, a,  )
 n 0


(4)
donde E x ' denota el operador esperanza con respecto a la
medida de probabilidad Px ' inducida por ( ,  ' ) 
 A    , dado que x0  x (para la construcción de

u ( y)Q(dy x, a)

W ( y)Q(dy x, a)
( x, a) 
.
Px ' ,
ver por ejemplo, [3]).
Sea
V ' ( x,  ) : sup V ( x,  ,  ' ), x  X ,    A .
( x, a)  K A .
(b) La ley de transición Q es débilmente continua, es decir,
para cada función continua y acotada u : X  R , la
función
0
y
d ( x, a)
X
es continua en K A .
(c) La función
( x, a) 
X
es continua en K A .
(d) La multifunción x  A(x) es semicontinua superiormente (s.c.s.), y el conjunto A(x) es compacto para cada
x  X.
(e) La multifunción ( x, a)  ( x, a) es s.c.i., y para cada
( x, a)  K A , ( x, a) es un conjunto  -compacto.
Denotamos por BW al espacio lineal normado de todas
las funciones medibles u : X  R con norma
u ( x)
u W : sup
 ,
xX W ( x)
y por LW al subespacio de funciones s.c.i. en BW .
 ' 
Entonces, el problema de control semi-Markoviano minimax
descontado para el controlador es encontrar una estrategia
 *   A tal que
V ' ( x,  *)  inf V ' ( x,  )
Observación 1. (a) Es un hecho bien conocido que la
Hipótesis 2(b) puede ser sustituida por la condición
equivalente dada continuación: Para cada función s.c.i. y
acotada inferiormente u : X  R , la función
  A
 inf
( x, a) 
sup V ( x,  ,  ' )
  A  '

: V * ( x),
x  X.
(5)
En este caso, decimos que  * es una estrategia descontada
minimax y que
V * es la función de valor óptimo
descontada. Nuestro objetivo consiste en demostrar la
existencia de una estrategia minimax descontada para el
modelo MSM.
Hipótesis y Criterio de Costo Descontado.
A continuación introducimos dos clases de condiciones
sobre el modelo MSM, a saber, la Hipótesis 1 es una
condición de regularidad que asegura que en un intervalo de
tiempo acotado existe, a lo más, un número finito de
transiciones del proceso; mientras que, en la Hipótesis 2
imponemos condiciones de continuidad y compacidad, a fin
de garantizar la existencia de selectores minimax.
Hipótesis 1. Existe   0 y   0 tal que
F ( x, a,  )  1  
( x, a,  )  K.

X
u ( y)Q(dy x, a)
es s.c.i. en K A .
(b) No es difícil demostrar que LW es un subconjunto
cerrado de BW . De aquí, dado que BW es un espacio de
Banach, tenemos que LW es un subespacio completo de
BW .
Ahora bien, a fin de analizar el criterio de costo
descontado minimax definido de (1) a (5), nótese que,
usando propiedades de la esperanza condicional podemos
reescribir el índice de funcionamiento (4) como

V ( x,  ,  ' ) : E x ' c( x 0 , a 0 ,  0 )



n 1
   ( x
n 1 k  0
k , ak , k

)c ( x n , a n ,  n ) 

x  X , ( ,  ' )   A    .
(6)
De hecho, una primera consecuencia de las Hipótesis 1 y 2
es la siguiente.
(c) Para cada u  LW , existe f *  F A tal que
Lema 1. Bajo las Hipótesis 1 y 2(a) se tiene:
(a)  : sup ( x,a, )K  ( x, a, )  1;
T u ( x) 
(b) Para cada ( x, a, )  K y alguna constante M 1  0,
c( x, a,  )  M 1W ( x).
Demostración. (Véase demostración en: [13], p.141.)
Observación 3. Debido a que T es un operador de
Hipótesis 3. (a) Existe una constante b  0 tal que
1  b  1 , y para todo ( x, a)  K A

X
H  (u, x, f * ,  ), x  X .
Demostración. (Véase demostración en: [13], p.142-144.)
Nótese que la Hipótesis 2 (ver Lema 1(b)) permite una
función de costo por etapa c( x, a, ) no acotada, siempre y
cuando esté dominada por una función W . No obstante,
para enunciar nuestro resultado principal, requerimos
imponer una condición que limite su crecimiento. Además,
necesitamos una condición de continuidad sobre la función
de distribución del tiempo de permanencia.
W ( y)Q(dy x, a)  bW ( x),
sup
 ( x, f * )
(7)
donde W es la función en la Hipótesis 2.
(b) Para cada t  0, F (t x, a, ) es continua en K .
Observación 2. (a) Observe que para cada x  X , n  N 0
y ( ,  ' )   A    , de (7) se tiene
contracción que mapea LW en sí mismo (Lema 2) y
LW  BW es completo (Observación 1(b)), del Teorema
de Punto Fijo de Banach, existe una única función u~  L
W
tal que para todo x  X ,
u~( x)  T u~( x),
y
T n u  u~  (b ) n u  u~


W
W
u  LW , n  N 0 .
Para cada n  N , x  X y ( ,  ' )   A    ,
definimos el costo descontado esperado en n etapas
(ver (6)) como V 1 ( x,  ,  ' ) : E x ' c( x0 , a0 , 0 ) , y para
n  2,

V n ( x,  ,  ' ) : E x ' c( x0 , a 0 ,  0 )

n 1 j 1
E x ' W ( x n1 )  bE x ' W ( x n ),

  ( x , a
k

k ,  k )c( x j , a j ,  j ) .

j 1 k 0
lo cual implica que
Ex W ( xn 1)  b W ( x).
 '
n
Por lo tanto, de (6) y el Lema 1, para cada x  X y
( ,  ' )   A    ,



V ( x,  ,  ' )  E x '  c( x 0 , a 0 ,  0 ) 
 n c( x n , a n ,  n ) 


n 1


 M 1W ( x)
 (b )
M 1W ( x)
.
1  b 
n


bM 1
.
1  b 
n 0
Entonces,
V*
W
(b) De la Hipótesis 3(b) la función  ( x, a, ) en (2) es
continua en K , y además, de la Hipótesis 2(a) la función de
costo c( x, a, ) en (3) es s.c.i. en K A y continua en  .
Para u  BW y ( x, a, )  K , definimos
H  (u, x, a,  ) : c( x, a,  )
   ( x, a ,  )

X
y
T u( x) : inf
y para n  N , vn ( x)  T vn1 ( x), x  X .
Resultado central.
Ahora establecemos nuestro resultado principal como sigue.
Teorema 1. Si se satisfacen las Hipótesis 1, 2 y 3, entonces:
(a) La función de valor óptimo (5) es la única solución en
LW que satisface
V * ( x)  T V * ( x),
(b) Para cada n  N ,
vn  V *
sup H  (u, x, a,  ).
aA( x )  ( x, a )
Lema 2. Si se satisfacen las Hipótesis 1,2 y 3, entonces:
(a) T es un operador de contracción con módulo
b  1.
(b) T mapea LW en si mismo.
W
 M1
x  X.
(b ) n
.
1  b
(c) Existe f *  F A tal que
V * ( x) 
u ( y )Q(dy x, a)
{v n } en LW como v0  0,
Además, definimos la sucesión
sup
  ( x , f
*

*
c( x, f ( x),  )
( x )) 
   ( x, f * ( x),  )

X

V * ( y )Q(dy x, f * ( x)) ,
y además, f * es una estrategia minimax de costo descontado
para el controlador, es decir,
V * ( x)  sup V ( x, f * ,  ' ).
 ' 
Demostración. (Véase demostración en: [13], p.145-147.)
III. CONCLUSIÓN
Los problemas de control minimax han sido considerados
bajo diversos contextos. Por ejemplo, en [1], [2], [6], [7] y
[11] se consideran casos especiales a fin de estudiar modelos
de colas y de inventarios; mientras que, en [5] se presenta
una teoría general para problemas de control minimax en
tiempo discreto. Además, en trabajos tales como [4], [8], [9],
[15] y sus referencias se analizan modelos de control semiMarkovianos (criterios: descontado y promedio) suponiendo
que todas las componentes del modelo son conocidas por el
controlador. Por otra parte, cabe mencionar que los propios
autores del presente resumen, en trabajos previos han
abordado un problema similar bajo la hipótesis de que la
distribución del tiempo de permanencia es desconocida, pero
con densidad independiente de los pares estado-acción.
Por lo anterior, consideramos que la teoría aquí presentada
es una extensión a los trabajos de [5] y [12].
REFERENCIAS
[1] Altman, E.; Hordijk, A. Zero-sum Markov games
and worst-case optimal control of queueing systems. Queueing Syst. Theory Appl. 21, 415--447
(1995).
[2] Coraluppi, S.P., Marcus, S.I. Mixed risk-neutral/minimax control of discrete-time finite state
Markov decision process. IEEE Trans. Automat.
Control. 45, 528--532 (2000).
[3] Dynkin, E.B.; Yushkevich, A.A. Controlled Markov Processes. Springer-Verlag, New York (1979).
[4] Federgruen, A.; Schweitzer, P.J.; Tijms, H.C. Denumerable undiscounted semi-Markov decision
processes with unbounded rewards. Math. Oper.
Res. 8, 298-313 (1983).
[5] González-Trejo, T.J.; Hernández-Lerma, O.;
Hoyos-Reyes, L.F. Minimax control of discretetime stochastic systems. SIAM J. Control Optim.
41, 1626-1659 (2003).
[6] Hernández-Lerma, O.; Lasserre, J.B. DiscreteTime Markov Control Processes: Basic Optimality
Criteria. Springer, New York (1996).
[7] Hordijk, A.; Passchier, O.,;Spieksma, F.M. Optimal control against worst case admission policies:
A multichained stochastic game. Math. Methods
Oper. Res. 45, 281--301 (1997).
[8] Jagannathan, R. A minimax ordering policy for the
infinite stage dynamic inventory problem. Manage.
Sci. 24, 1138--1149 (1978).
[9] Jaskiewicz, A. An approximation approach to ergodic semi-Markov control processes. Math
Methods Oper. Res. 54, 1-19 (2001).
[10] Kalyanasundaram, S.; Chong, E.K.P.; Shroff, N.B.
Markov decision processes with uncertain transition rates: sensitivity and max-min control. Asian
J. Control. 6, 2, 253-269 (2004).
[11] Küenle, H.-U. Stochastiche Spiele und - Entscheidungsmodelle. B. G. Teubner, Leipzig
(1986).
[12] Luque-Vásquez, F.; Minjárez-Sosa, J.A. SemiMarkov control processes with unknown holding
times distribution under a discounted criterion.
Math. Meth. Oper. Res. 61, 455-468 (2005).
[13] Luque-Vásquez, F.; Minjárez-Sosa, J.A.; RosasRosas, L.C. Semi-Markov control models with
partially known holding times distribution: discounted and average criteria. Acta Appl Math
Optim. 114: 135-156. DOI:10.1007/s10440-0119605-y. (2011)
[14] Mandl, P. Estimation and control in Markov
chains. Adv. Appl. Probab. 6, 40-60 (1974).
[15] Milliken, P., Marsh, C., Van Brunt, B. Minimax
controller design for a class of uncertain nonlinear
systems. Automatica. 35, 583-590 (1999).
[16] Puterman, M.L. Markov Decision Processes. Discrete Stochastic Dynamic Programming. Wiley,
New York (1994)
[17] Rieder, U. Measurable selection theorems for
optimization problems. Manuscripta Math. 115131 (1978).
[18] Savkin, A.V.; Peterson, I.R. Minimax optimal
control of uncertain systems with structured uncertainty.
International Journal of Robust and Nonlinear Control. 5, 119-137 (1995).
[19] Schäl, M. Conditions for optimality and for the
limit on n-stage optimal policies to be optimal. Z.
Wahrs. Verw. Gebiete. 32, 179--196 (1975).
[20] Schweitzer, P.J. Iterative solution of the functional
equations of undiscounted Markov renewal programmming. J. Math. Anal. Appl. 34, 495-501
(1971).
[21] Yu, W.; Guo, X. Minimax controller design for
discrete-time time-varying stochastic systems. In
Proceedings of the 41st IEEE CDC, Las Vegas,
Nevada USA 598-603 (2002).