Seminarios

Consideraremos el problema de tiempo discreto y horizonte infinito que consiste en maximizar la recompensa media obtenida por N procesos de decisión de Markov idénticos y débilmente acoplados a través de restricciones en la selección de acciones; el modelo se denomina multi-armed restless bandits en el caso particular en el que hay dos acciones y una única restricción que indica cuántos procesos tienen que usar cada acción. El conjunto de N procesos puede verse como un único proceso de decisión de Markov en un espacio de estados N-dimensional, y teóricamente pueden hallarse políticas óptimas en forma númerica utilizando programación dinámica. Sin embargo, esto es computacionalmente inviable debido a la alta dimensión del espacio de estados, por lo que es deseable una teoría que use la estructura del problema para calcular políticas aproximadamente óptimas en forma sencilla. Para ello, probaremos un límite fluido que vincula los procesos de Markov débilmente acoplados con un problema de control determinístico y de variable continua en el que el objetivo es maximizar la recompensa media asociada a una medida de ocupación que representa el límite de la distribución empírica de los procesos cuando N tiende a infinito. Además, probaremos que resolver este problema de control permite construir políticas asintóticamente óptimas para los procesos de Markov débilmente acoplados, y daremos condiciones suficientes para poder resolver el problema de control. Bajo hipótesis débiles, probaremos que las condiciones anteriores se cumplen y que las políticas pueden construirse en forma explícita en función de la solución de un problema de optimización lineal con tantas variables como pares estado-acción para un único proceso.