El índice de Gittins es una medida de la recompensa que se puede lograr a través de un proceso estocástico dado con ciertas propiedades, a saber: el proceso tiene un estado de terminación final y evoluciona con una opción, en cada estado intermedio, de terminación. Al terminar en un estado dado, la recompensa lograda es la suma de las recompensas probabilísticas esperadas asociadas con cada estado desde el estado de terminación real hasta el estado terminal final, inclusive. El índice es un escalar real .
Terminología
Para ilustrar la teoría, podemos tomar dos ejemplos de un sector en desarrollo, como las tecnologías de generación de electricidad: energía eólica y energía de las olas. Si se nos presentan las dos tecnologías cuando ambas se proponen como ideas, no podemos decir cuál será mejor a largo plazo, ya que todavía no tenemos datos en los que basar nuestros juicios. [1] Sería fácil decir que la energía de las olas sería demasiado problemática para desarrollar, ya que parece más fácil instalar muchas turbinas eólicas que hacer los generadores flotantes largos, remolcarlos mar adentro y tender los cables necesarios.
Si tuviéramos que tomar una decisión en ese momento temprano del desarrollo, podríamos estar condenando una tecnología a dejarse en el estante y la otra se desarrollaría y pondría en funcionamiento. Si desarrollamos ambas tecnologías, podríamos juzgar cada una comparando el progreso de cada tecnología en un intervalo de tiempo establecido, como cada tres meses. Las decisiones que tomemos sobre la inversión en la siguiente etapa se basarán en esos resultados. [1]
En un artículo de 1979 llamado Bandit Processes and Dynamic Allocation Indices, John C. Gittins sugiere una solución para problemas como este. Toma las dos funciones básicas de un " problema de programación " y un problema de "bandido de múltiples brazos" [2] y muestra cómo estos problemas pueden resolverse utilizando índices de asignación dinámica . Primero toma el "Problema de programación" y lo reduce a una máquina que tiene que realizar trabajos y tiene un período de tiempo establecido, cada hora o día, por ejemplo, para terminar cada trabajo. La máquina recibe un valor de recompensa, basado en el acabado. o no dentro del período de tiempo, y se calcula un valor de probabilidad de si terminará o no para cada trabajo. El problema es "decidir qué trabajo procesar a continuación en cada etapa para maximizar la recompensa total esperada". [1] Luego pasa al "problema del bandido armado múltiple" donde a cada tirón de una palanca de " un bandido armado " se le asigna una función de recompensa por un tirón exitoso, y una recompensa cero por un tirón fallido. La secuencia de éxitos forma un proceso de Bernoulli y tiene una probabilidad de éxito desconocida. Hay múltiples "bandidos" y la distribución de los tirones exitosos se calcula y es diferente para cada máquina. Gittins afirma que el problema aquí es "decidir qué brazo tirar a continuación en cada etapa para maximizar la recompensa total esperada de una secuencia infinita de tirones". [1]
Gittins dice que "Los dos problemas descritos anteriormente implican una secuencia de decisiones, cada una de las cuales se basa en más información que sus predecesoras, y ambos problemas pueden abordarse mediante índices de asignación dinámica". [2]
Definición
En matemáticas aplicadas, el "índice de Gittins" es un valor escalar real asociado al estado de un proceso estocástico con función de recompensa y con probabilidad de terminación. Es una medida de la recompensa que se puede lograr mediante el proceso que evoluciona a partir de ese estado, bajo la probabilidad de que termine en el futuro. La "política de índice" inducida por el índice de Gittins, que consiste en elegir en cualquier momento el proceso estocástico con el índice de Gittins más alto en la actualidad, es la solución de algunos problemas de frenado como el de asignación dinámica, donde un decisor tiene que maximizar la recompensa total al distribuir una cantidad limitada de esfuerzo a una serie de proyectos en competencia, cada uno de los cuales devuelve una recompensa estocástica. Si los proyectos son independientes entre sí y solo puede evolucionar un proyecto a la vez, el problema se denomina bandido de múltiples brazos (un tipo de problemas de programación estocásticos ) y la política del índice de Gittins es óptima. Si pueden evolucionar varios proyectos, el problema se llama Bandido inquieto y la política del índice de Gittins es una buena heurística conocida, pero no existe una solución óptima en general. De hecho, en general este problema es NP-completo y generalmente se acepta que no se puede encontrar una solución viable.
Historia
Las preguntas sobre las políticas de parada óptimas en el contexto de los ensayos clínicos han estado abiertas desde la década de 1940 y en la década de 1960 algunos autores analizaron modelos simples que conducen a políticas de índice óptimas, [3] pero fue solo en la década de 1970 que Gittins y sus colaboradores demostraron en un marco de Markov, la solución óptima del caso general es una política de índice cuyo "índice de asignación dinámica" es computable en principio para cada estado de cada proyecto en función de la dinámica del proyecto individual. [2] [4] En paralelo a Gittins, Martin Weitzman estableció el mismo resultado en la literatura económica. [5]
Poco después del artículo fundamental de Gittins, Peter Whittle [6] demostró que el índice surge como un multiplicador de Lagrange a partir de una formulación de programación dinámica del problema llamado proceso de retiro y conjeturó que el mismo índice sería una buena heurística en una configuración más general llamada Bandido inquieto . La cuestión de cómo calcular realmente el índice para las cadenas de Markov fue abordada por primera vez por Varaiya y sus colaboradores [7] con un algoritmo que calcula los índices desde el más grande primero hasta el más pequeño y por Chen y Katehakis [8], quienes mostraron ese estándar. LP podría usarse para calcular el índice de un estado sin requerir su cálculo para todos los estados con valores de índice más altos. LCM Kallenberg [9] proporcionó una implementación LP paramétrica para calcular los índices para todos los estados de una cadena de Markov. Además, Katehakis y Veinott [10] demostraron que el índice es la recompensa esperada de un proceso de decisión de Markov construido sobre la cadena de Markov y conocido como Reinicio en estado y puede calcularse exactamente resolviendo ese problema con el algoritmo de iteración de políticas , o aproximadamente con el algoritmo de iteración de valor . Este enfoque también tiene la ventaja de calcular el índice para un estado específico sin tener que calcular todos los índices mayores y es válido en condiciones de espacio de estados más generales. Sonin [11] obtuvo en 2004 un algoritmo más rápido para el cálculo de todos los índices como consecuencia de su algoritmo de eliminación para la parada óptima de una cadena de Markov. En este algoritmo, la probabilidad de terminación del proceso puede depender del estado actual en lugar de ser un factor fijo. Un algoritmo más rápido fue propuesto en 2007 por Niño-Mora [12] explotando la estructura de un simplex paramétrico para reducir el esfuerzo computacional de los pasos de pivote y así lograr la misma complejidad que el algoritmo de eliminación gaussiano . Cowan, W. y Katehakis (2014), [13] proporcionan una solución al problema, con procesos de recompensa de espacio de estado potencialmente no markovianos e incontables, bajo marcos en los que, o los factores de descuento pueden no ser uniformes y variar con el tiempo , o los períodos de activación de cada bandido pueden no ser fijos o uniformes, sujetos en cambio a una duración de activación posiblemente estocástica antes de que se permita un cambio a un bandido diferente. La solución se basa en índices generalizados de reinicio en estado.
Definición matemática
Índice de asignación dinámica
La definición clásica de Gittins et al. es:
dónde es un proceso estocástico, es la utilidad (también llamada recompensa) asociada al estado discreto , es la probabilidad de que el proceso estocástico no termine, y es el operador de expectativa condicional dado c :
con siendo el dominio de X .
Formulación del proceso de jubilación
La formulación de programación dinámica en términos de proceso de jubilación, dada por Whittle, es:
dónde es la función de valor
con la misma notación anterior. Sostiene que
Formulación de reinicio en estado
Si es una cadena de Markov con recompensas, la interpretación de Katehakis y Veinott (1987) asocia a cada estado la acción de reiniciar desde un estado arbitrario, construyendo así un proceso de decisión de Markov .
El índice de Gittins de ese estado es la recompensa total más alta que se puede lograr en si siempre se puede optar por continuar o reiniciar desde ese estado .
dónde indica una política sobre . Sostiene que
- .
Índice generalizado
Si la probabilidad de supervivencia depende del estado , una generalización introducida por Sonin (2008) define el índice de Gittins como la recompensa total máxima con descuento por posibilidad de rescisión.
dónde
Si es reemplazado por en las definiciones de , y , entonces sostiene que
esta observación lleva a Sonin a concluir que y no es el "verdadero significado" del índice de Gittins.
Teoría de las colas
En la teoría de las colas, el índice de Gittins se utiliza para determinar la programación óptima de trabajos, por ejemplo, en una cola M / G / 1. El tiempo medio de finalización de los trabajos según un programa de índice de Gittins se puede determinar mediante el enfoque SOAP. [14] Tenga en cuenta que la dinámica de la cola es intrínsecamente markoviana, y la estocasticidad se debe a los procesos de llegada y servicio. Esto contrasta con la mayoría de los trabajos en la literatura sobre aprendizaje, donde la estocasticidad se explica explícitamente mediante un término de ruido.
Problemas fraccionales
Si bien los índices de Gittins convencionales inducen una política para optimizar la acumulación de una recompensa, un problema común que se plantea consiste en optimizar la proporción de recompensas acumuladas. Por ejemplo, este es un caso para que los sistemas maximicen el ancho de banda, que consiste en datos a lo largo del tiempo, o minimicen el consumo de energía, que consiste en energía a lo largo del tiempo.
Esta clase de problemas es diferente de la optimización de un proceso de recompensa semi-Markov, porque este último podría seleccionar estados con un tiempo de estadía desproporcionado solo por acumular una recompensa más alta. En cambio, corresponde a la clase de problema de optimización de recompensa de Markov lineal-fraccional.
Sin embargo, un aspecto perjudicial de tales optimizaciones de relación es que, una vez que la relación alcanzada en algún estado es alta, la optimización puede seleccionar estados que conducen a una relación baja porque tienen una alta probabilidad de terminación, por lo que es probable que el proceso termine antes. la proporción cae significativamente. Una configuración de problema para prevenir tales terminaciones anticipadas consiste en definir la optimización como la maximización de la relación futura vista por cada estado. Se supone que existe una indexación para este problema, que se puede calcular como una simple variación de los algoritmos de reinicio en estado o de eliminación de estado existentes y se evalúa para que funcione bien en la práctica. [15]
Notas
- ↑ a b c d Cowan, Robin (julio de 1991). "Tortugas y liebres: elección entre tecnologías de mérito desconocido". The Economic Journal . 101 (407): 801–814. doi : 10.2307 / 2233856 . JSTOR 2233856 .
- ^ a b c Gittins, JC (1979). "Procesos bandidos e índices de asignación dinámica". Revista de la Royal Statistical Society. Serie B (Metodológica) . 41 (2): 148-177. JSTOR 2985029 .
- ^ Mitón L (1960). "Una solución analítica al problema de secuencia de prueba de menor costo". Revista de Ingeniería Industrial . 11 (1): 17.
- ^ Gittins, JC; Jones, DM (1979). "Un índice de asignación dinámica para el problema del bandido multiarmado descontado". Biometrika . 66 (3): 561–565. doi : 10.2307 / 2335176 . JSTOR 2335176 .
- ^ Weitzman, Martin L. (1979). "Búsqueda óptima de la mejor alternativa". Econometrica . 47 (3): 641–654. doi : 10.2307 / 1910412 . hdl : 1721,1 / 31303 . JSTOR 1910412 .
- ^ Whittle, Peter (1980). "Bandidos armados múltiples y el índice de Gittins". Revista de la Sociedad Real de Estadística, Serie B . 42 (2): 143-149.
- ^ Varaiya, P .; Walrand, J .; Buyukkoc, C. (mayo de 1985). "Extensiones del problema del bandido multiarmado: el caso descontado". Transacciones IEEE sobre control automático . 30 (5): 426–439. doi : 10.1109 / TAC.1985.1103989 .
- ^ Chen YR, Katehakis MN (1986). "Programación lineal para problemas de bandidos de armas múltiples de estado finito". Matemáticas. Oper. Res . 11 (1): 180–183. doi : 10.1287 / moor.11.1.180 .
- ^ Kallenberg LCM (1986). "Una nota sobre el cálculo del índice de Gittins de MN Katehakis y Y.-R. Chen". Matemáticas. Oper. Res . 11 (1): 184–186. doi : 10.1287 / moor.11.1.184 .
- ^ Katehakis M., Veinott A. (1987). "El problema de los bandidos de armas múltiples: descomposición y cálculo". Matemáticas. Oper. Res . 12 (2): 262–268. doi : 10.1287 / moor.12.2.262 .
- ^ Sonin I (2008). "Un índice de Gittins generalizado para una cadena de Markov y su cálculo recursivo". Estadísticas y letras de probabilidad . 78 (12): 1526-1533. doi : 10.1016 / j.spl.2008.01.049 .
- ^ Ni, Mora J (2007). "A (2/3) ^ n algoritmo de pivote rápido para el índice de Gittins y parada óptima de una cadena de Markov". INFORMA Revista de Computación . 19 (4): 596–606. CiteSeerX 10.1.1.77.5127 . doi : 10.1287 / ijoc.1060.0206 .
- ^ Cowan, Wesley; Katehakis, Michael N. (enero de 2015). "Bandidos armados múltiples bajo depreciación general y compromiso" . Probabilidad en Ingeniería y Ciencias de la Información . 29 (1): 51–76. doi : 10.1017 / S0269964814000217 .
- ^ Scully, Ziv y Harchol-Balter, Mor y Scheller-Wolf, Alan (2018). "SOAP: un análisis limpio de todas las políticas de programación basadas en la edad". Actas de la ACM sobre medición y análisis de sistemas informáticos . ACM. 2 (1): 16. doi : 10.1145 / 3179419 . S2CID 216145213 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Di Gregorio, Lorenzo y Frascolla, Valerio (1 de octubre de 2019). Optimidad de traspaso en redes heterogéneas . Foro Mundial 5G . arXiv : 1908.09991v2 .CS1 maint: varios nombres: lista de autores ( enlace )
Referencias
- Scully, Ziv y Harchol-Balter, Mor y Scheller-Wolf, Alan (2018). "SOAP: un análisis limpio de todas las políticas de programación basadas en la edad". Actas de la ACM sobre medición y análisis de sistemas informáticos . ACM. 2 (1): 16. doi : 10.1145 / 3179419 . S2CID 216145213 .CS1 maint: varios nombres: lista de autores ( enlace )
- Berry, Donald A. y Fristedt, Bert (1985). Problemas de bandidos: asignación secuencial de experimentos . Monografías de estadística y probabilidad aplicada. Londres: Chapman & Hall. ISBN 978-0-412-24810-8.CS1 maint: varios nombres: lista de autores ( enlace )
- Gittins, JC (1989). Índices de asignación de bandidos de armas múltiples . Serie Wiley-Interscience en Sistemas y Optimización. prólogo de Peter Whittle . Chichester: John Wiley & Sons, Ltd. ISBN 978-0-471-92059-5.
- Weber, RR (noviembre de 1992). "En el índice de Gittins para bandidos con varios brazos". Los anales de la probabilidad aplicada . 2 (4): 1024–1033. doi : 10.1214 / aoap / 1177005588 . JSTOR 2959678 .
- Katehakis, M. y AF Veinott, Jr. (1987). "El problema de los bandidos de armas múltiples: descomposición y cálculo". Matemáticas de la investigación operativa . 12 (2): 262–268. doi : 10.1287 / moor.12.2.262 . JSTOR 3689689 .CS1 maint: varios nombres: lista de autores ( enlace )
- Cowan, W. y MN Katehakis (2014). "Bandidos armados múltiples bajo Depreciación y Compromiso General". Probabilidad en Ingeniería y Ciencias de la Información . 29 : 51–76. doi : 10.1017 / S0269964814000217 .
enlaces externos
- [1] Implementación de Matlab / Octave de los algoritmos de cálculo de índices
- Cowan, Robin (1991). "Tortugas y liebres: elección entre tecnologías de mérito desconocido". The Economic Journal . 101 (407): 801–814. doi : 10.2307 / 2233856 . JSTOR 2233856 .