Costes e incentivos desde los Procesos de Decisión de Markov

Una estrategia es adecuada para una situación determinada, no tiene validez general. En este post vamos a ver cómo los costes pueden variar la estrategia cuando el terreno de juego es básicamente el mismo. Haremos algunas simulaciones sobre un tablero inventado. En un post posterior veremos un caso real sobre cómo unos incentivos mal diseñados provocarían una situación cuanto menos pintoresca.

Pero vayamos por partes, como dijo Jack el destripador:

Reglas del Juego

Tablero para el desarrollo
Figura 1

Fijémonos en la figura 1.

Para comenzar hay que situarse en la casilla A4; en cada paso estamos obligados a intentar movernos en una dirección, pero esto no sucede de forma indefinida. Si en un momento dado se llega a la casilla C1 se ganan 100 unidades y se termina el proceso. En cambio si se alcanza la casilla B1 hay una pérdida de 100 e igualmente el proceso finaliza.

La casilla B3 es inaccesible. Tampoco nos podemos salir del tablero.

Veamos la figura 2:

Cuando intentamos hacer un movimiento en una determinada dirección hay un 80 % de probabilidades que efectivamente nos desplacemos en la dirección elegida, pero por los motivos que sea hay un 10 % de probabilidad de irse a cada uno de los lados. Lo que nunca ocurre es que retrocedamos cuando intentamos movernos en la dirección contraria a la elegida.

Cada movimiento que hagamos tendrá un costo que ya indicaremos más adelante.

Movimientos desde una celda
Figura 2

Vamos a utilizar un algoritmo que nos fije cuál es la mejor política a implementar para que se maximice la probabilidad del beneficio o en su defecto, minimice la pérdida en los recorridos. ¿A qué nos referimos cuando hablamos de la política a implementar? Se trata simplemente de determinar para cada casilla cuál es el movimiento más adecuado para conseguir el objetivo. En definitiva, en cada casilla hay que decidir si intentamos movernos hacia adelante, hacia atrás o hacia uno de los lados, o visto de otra forma, hacia el norte, sur, este u oeste. NO se permiten movimientos en diagonal.

Se acepta intentar moverse hacia un destino imposible (contra el perímetro del área de circulación o contra la casilla inaccesible). Hay que tener en cuenta que en este caso tanto se produzca un movimiento (hacia los laterales) o quedemos inmóviles el costo del intento se contabiliza de cara a ver el resultado final. Cuando se aplica esta tipo de políticas existe una probabilidad de movernos de un 20 % (un 10 % para cada lado) y un 80 % de permanecer donde estemos.

Lo que vamos a analizar

Con estas reglas veremos qué solución encontramos al aplicar un algoritmo basado en los procesos de decisión de Markov. Esta solución consiste en indicarnos en cada casilla cuál es el movimiento que se debe elegir.

En este post y en el siguiente analizaremos los resultados con 4 niveles típicos de costo. El primero será uno que se considera ‘Normal’ y supone un desembolso de 4 unidades por cada movimiento o intento del mismo de una posición a otra. En el segundo se aplicará un costo muy reducido que se ha fijado en 0,4 unidades por actuación; en otro habrá un costo muy alto, 40 unidades y en el último caso existirá un beneficio (costo negativo) por cada movimiento o tentativa.

Resultados

Caso normal, ver figura 3
Política coste 4.0
Figura 3

Partiendo de la casilla A4 y si todo sale según las políticas previstas se llegaría en 5 pasos a la casilla C1. Bien comenzando el camino con un primer paso hacia la derecha o bien haciéndolo hacia arriba Estos serían los recorrido que maximiza el beneficio puesto que se tiene la recompensa de 100 con un número mínimo de pasos. Si ejecutamos el proceso siguiendo esta política una y otra vez obtendremos resultados diferentes puesto que en algún caso nos podemos deslizar hacia una casilla no prevista. En cualquier caso la solución es la óptima porque maximiza la esperanza matemática de los beneficios.

La política en la casilla A4 indica que se debe intentar ir a la derecha y NO hacia arriba porque en el segundo caso tendríamos que pasar en un momento dado del recorrido al lado de la casilla B1, con el riesgo de que si nos deslizamos de lado entraremos en el valle de la muerte. Esto ocurrirá en el 10 % de los casos que pasemos por allí. Ese riesgo no lo tenemos en el camino empezando por B4.

Siempre existe la posibilidad de que cuando estemos en la casilla C2 e intentemos ir a la C1 nos deslicemos hacia la izquierda y en el siguiente paso nos vuelva a ocurrir lo mismo y acabemos cayendo en la casilla maldita (B2), pero esto se daría sólo una vez de cada 100.

Si por una casualidad nos deslizamos hacia la casilla A1 el algoritmo nos dice que lo mejor es intentar ir hacia la casilla A2 a pesar del riesgo de caer en la casilla B1. Pero si intentamos movernos hacia la izquierda para evitar ese riesgo necesitaremos una media de 10 intentos para salir de ahí con un coste de 40 unidades. La esperanza matemática del coste de ir hacia abajo es de 4 unidades más 0,10 de 100, en total 14 unidades. Merece la pena arriesgarse a caer en la casilla B1.

Coste muy reducido, ver figura 4

¿Cómo cambia la política cuando se reduce mucho el costo?

Política coste 0.4
Figura 4

Estamos hablando de una cuantía por movimiento de 0,4 unidades. Si miramos al resultado vemos que ha cambiado la política de las casillas que lindan con el ‘Valle de la muerte’ incluida la casilla A2. En conjunto observamos dos grandes tendencias.

La primera de ellas es lo que ocurre con las casillas A1 y B2. Prefieren obstinarse en ir hacia posiciones imposibles dando la espalda a la casilla B1 antes que arriesgarse a caer en ella. Ya vimos que en el caso de A1 lo normal es salir en una media de 10 intentos, lo que supone un gasto de 4 unidades (0,4 x 10) en lugar de 10,4 si nos deslizamos hacia donde no queremos. (0,4 del movimiento más 100 x 0,10 del riesgo de caer en B1). De la casilla B2 se escapará con una media de 5 intentos, saliendo bien hacia la derecha o bien hacia la izquierda.

El segundo tema destacable es que si por un casual caemos en la casilla A3 e incluso en la casilla A2, se prefiere dar un rodeo para acercarnos por el ‘lado seguro’ que representa toda la fila C.

Como vemos la política se vuelve súper conservadora y evita a toda costa el riesgo de caer en B1 aunque ello suponga el realizar muchos más movimientos. Es lo que tiene que estos sean tan económicos.

Otros casos

En el próximo post te contaremos qué es lo que sucede cuando tenemos costes muy altos o por el contrario negativos. Habrá resultados muy interesantes.

Reconocimiento

Tanto el ejemplo presente como los resultados de aplicar el algoritmo basado en los procesos de decisión de Markov son originales de IA Grafos y los hemos obtenido del vídeo 161 de la serie “Descubriendo la Inteligencia Artificial” en YouTube