PROCESO DE DECISIÓN MARKOVIANO
NIVER OSWALDO TORRES BARRIGA
INGENIERIA INDUSTRIAL
FACULTAD DE INGENIERIA
UNIVERSIDAD ECCI
BOGOTÁ D.C.
2022
1
INTRODUCCION
Los procesos de decisión o control markovianos modelan sistemas dinámicos
estocásticos controlados, es decir, sistemas cuya evolución está sujeta a factores
aleatorios y que puede modificarse por medio de la selección de ciertas variables
de decisión o de control. Este tipo de modelos surgen en un sin número de áreas
de la ciencia y la ingeniería como f finanzas economía], robótica, programas de
salud redes de comunicación, aprovechamiento de recursos naturales; acuíferos;
petroleros, sistemas de transporte, sistemas de producción e inventario,
programas de mantenimiento y remplazo de equipo, etc.
Procesos de Decisión de Markov
• Tratamos ahora secuencias de acciones cuyos efectos son inciertos.
• Similares a espacios de estados, pero el efecto de una acción está descrito
mediante una distribución de probabilidad
• Además, se introduce la noción de “recompensa” en un estado. • Pueden verse
como “problemas de decisión secuenciales”
• ¿Cómo decidir la mejor acción en cada momento? • Sabiendo de antemano sus
posibles efectos y con qué probabilidad • Y la recompensa en cada situación.
Un Proceso de Decisión de Markov viene definido por:
• Un conjunto S de estados (con un estado inicial s0)
• Para cada estado, un conjunto A(s) de acciones aplicables a ese estado.
• Un modelo de transición, dado por una distribución de probabilidad P(s s,a) para
cada par de estados s,s y acción a aplicable a s (indicando la probabilidad de que
aplicando a a s se obtenga s).
• Una función de recompensa R(s). Propiedad de Markov: el efecto (incierto) de
una acción sobre un estado sólo depende de la acción y del propio estado (y no de
estados anteriores)
2
Políticas
• En este contexto, una solución no puede ser una secuencia de acciones, ya que
el efecto de cada acción es incierto.
• Más bien buscamos una política que en cada posible estado recomiende una
acción a aplicar: por cada estado que pasemos, aplicamos la acción que nos
recomienda esa política
S, de manera que π(s) ∈ A(s)
• Formalmente: una política es una función π definida sobre el conjunto de estados
• Una misma política puede generar secuencias de acciones distintas (aunque
unas con más probabilidades que otras).
• Se busca la política óptima: aquella que maximice la recompensa media
esperada para las posibles secuencias de acciones que se puedan generar.
Ejemplo de políticas en la cuadrícula
3
Valoración de secuencia de estados en el tiempo:
• Supongamos que, mediante aplicación de una secuencia de acciones, se ha
generado una secuencia de estados q0q1q2 ···
• ¿Cómo valoramos una secuencia de estados? Idea: a partir de las
recompensas, pero penalizando el largo plazo
• Valoración mediante recompensa con descuento: V ([q0q1q2 ···]) = R(q0) + γ
R(q1) +γ2R(q2) +··· donde γ es el llamado factor de descuento
• En el ejemplo de la cuadrícula:
• Con γ =0.8, la secuencia de estados (1, 1), (2,1),(3,1),(3,2),(3,3),(3,4) tiene una
valoración −0.04−0.04·0.8−0.04·0.82−0.04·0.83−0.04·0.84+1·0.85 = 0.193216
Valoraciones de secuencias: Observaciones
• Suponemos horizonte infinito
• No hay un plazo fijo de terminación
• Procesos estacionarios: la política óptima a partir de un momento sólo depende
del estado en ese momento
• ¿Esto implica que las valoraciones pueden ser infinitas? En general, no:
• Si hay estados terminales, los asimilamos a estados a partir del cual las
recompensas son cero. •
Aún con posibles secuencias infinitas, si las recompensas están acotadas por una
cantidad Rmax y γ < 1, entonces la valoración de una secuencia no puede ser
mayor de Rmax/(1 −γ) (¿por qué?)
Valoración de estados respecto de una política
• Dada una política π y un estado s, podemos valorar s respecto de π teniendo en
cuenta la valoración de las secuencias de estados que se generan si se sigue
dicha política a partir de s
• Ejemplo: si en la cuadrícula estamos en el estado (1,4) y aplicamos la política (a)
del gráfico anterior, podríamos generar distintas secuencias, cada una con una
probabilidad y una valoración. Entre otras:
• (1,4), (1,3), (1,2), (1,1), (2,1), (3,1), (3,2), (3,3), (3,4), con probabilidad 0.88 =
0.168 y valoración 0.0013 (siendo γ =0.8 y R =−0.04)
4
• (1,4), (1,3), (2,3), (3,3), (3,4) con probabilidad 0.83 · 0.1 = 0.0512 y valoración
0.291 • (1,4), (1,3), (2,3), (2,4) con probabilidad 0.8 · 0.12 = 0.008 y valoración-
0.609 • (1,4), (2,4) con probabilidad 0.1 y valoración-0.84
Valoración de estados respecto de una política
• Idea: valorar un estado s respecto de una política π como la media esperada (es
decir, ponderada por su probabilidad) de las valoraciones de todas las secuencias
que se podrían obtener.
• En el ejemplo anterior: 0.168·0.0013+0.0512·0.291−0.008·0.609−0.1·0.84+···
• La valoración de un estado respecto de una política π la notamos por Vπ(s).
Cálculo de valoración respecto de una política (ejemplo)
En la política (a) de la cuadrícula en la figura anterior, éstas serían alguna de las
ecuaciones que salen:
• Vπ(1,1) = −0.04+γ·(0.8·Vπ(2,1)+0.1·Vπ(1,1)+0.1·Vπ(1,2))
• Vπ(1,2) = −0.04+γ ·(0.8·Vπ(1,1)+0.2·Vπ(1,2))
• Vπ(1,3) = −0.04+γ·(0.8·Vπ(1,2)+0.1·Vπ(1,3)+0.1·Vπ(2,3))
• ···
• Vπ(3,4) = +1 Resolviendo este sistema, obtenemos Vπ.
