Índice de Gittins

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, ambos incluidos. El índice es un escalar real .

Terminología

Para ilustrar la teoría podemos tomar dos ejemplos de un sector en desarrollo, como es el de las tecnologías de generación de electricidad: la energía eólica y la energía de las olas. Si se nos presentan las dos tecnologías cuando 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 de desarrollar, ya que parece más fácil instalar muchas turbinas eólicas que fabricar los largos generadores flotantes, remolcarlos hasta el mar y tender los cables necesarios.

Si tuviéramos que tomar una decisión en ese momento inicial del desarrollo, podríamos estar condenando a que una tecnología se dejara de lado y que la otra se desarrollara y se pusiera en funcionamiento. Si desarrollamos ambas tecnologías, podríamos tomar una decisión sobre cada una comparando el progreso de cada tecnología en un intervalo de tiempo determinado, por ejemplo, cada tres meses. Las decisiones que tomemos sobre la inversión en la siguiente etapa se basarían en esos resultados. ^[1]

En un artículo de 1979 llamado Bandit Processes and Dynamic Allocation Indices ( Procesos de bandido e índices de asignación dinámica) , 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 " máquina tragamonedas de varios brazos " ^[2] y muestra cómo se pueden resolver estos problemas 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. A la máquina se le da un valor de recompensa, en función de terminar 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 de la máquina tragamonedas de varios brazos", donde a cada tirón de una palanca de una " máquina tragamonedas de un brazo " se le asigna una función de recompensa para un tirón exitoso y una recompensa cero para 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 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 de modo de maximizar la recompensa total esperada de una secuencia infinita de tirones". ^[1]

Gittins dice que "Ambos 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 una función de recompensa y con una probabilidad de terminación. Es una medida de la recompensa que puede alcanzar el proceso que evoluciona a partir de ese estado, bajo la probabilidad de que se termine en el futuro. La "política de índice" inducida por el índice de Gittins, que consiste en elegir en cada momento el proceso estocástico con el índice de Gittins más alto en ese momento, es la solución de algunos problemas de parada como el de asignación dinámica, donde un decisor tiene que maximizar la recompensa total distribuyendo una cantidad limitada de esfuerzo a un número 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 llama bandido multiarmado (un tipo de problemas de programación estocástica ) y la política del índice de Gittins es óptima. Si pueden desarrollarse varios proyectos, el problema se denomina Restless Bandit y la política de índice de Gittins es una heurística conocida pero no existe una solución óptima en general. De hecho, en general este problema es NP-completo y se acepta generalmente que no se puede encontrar una solución factible.

Historia

Las preguntas sobre las políticas óptimas de interrupción 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 conducían 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 markoviano que 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 como una función de la dinámica de ese 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 seminal de Gittins, Peter Whittle ^[6] demostró que el índice emerge 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 Restless bandit . La cuestión de cómo calcular realmente el índice para 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 demostraron que} el LP estándar 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 de 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 valores . 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 bajo condiciones de espacio de estados más generales. Un algoritmo más rápido para el cálculo de todos los índices fue obtenido en 2004 por Sonin ^[11] como consecuencia de su algoritmo de eliminación para la detención ó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 pivote y logrando así la misma complejidad que el algoritmo de eliminación gaussiana . Cowan, W. y Katehakis (2014), ^[13] ofrecen una solución al problema, con procesos de recompensa en el espacio de estados potencialmente no markovianos e incontables, bajo marcos en los que, o bien los factores de descuento pueden ser no uniformes y variar con el tiempo, o bien 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 el estado.

Definición matemática

Índice de asignación dinámica

La definición clásica de Gittins et al. es:

${\displaystyle \nu (i)=\sup _{\tau >0}{\frac {\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]\right\rangle _{Z(0)=i}}{\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}\right\rangle _{Z(0)=i}}}}$

donde 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 : ${\displaystyle Z(\cdot )}$ ${\displaystyle R(i)}$ ${\displaystyle i}$ ${\displaystyle \beta <1}$ ${\displaystyle \langle \cdot \rangle _{c}}$

${\displaystyle \langle X\rangle _{c}\doteq \sum _{x\in \chi }xP\{X=x|c\}}$

siendo el dominio de  X . ${\displaystyle \chi }$

Formulación del proceso de jubilación

La formulación de programación dinámica en términos del proceso de jubilación, dada por Whittle, es:

${\displaystyle w(i)=\inf\{k:v(i,k)=k\}}$

¿Dónde está la función de valor? ${\displaystyle v(i,k)}$

${\displaystyle v(i,k)=\sup _{\tau >0}\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]+\beta ^{t}k\right\rangle _{Z(0)=i}}$

con la misma notación que la anterior. Se cumple que

${\displaystyle \nu (i)=(1-\beta )w(i).}$

Formulación de reinicio en el estado

Si se trata de 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 . ${\displaystyle Z(\cdot )}$ ${\displaystyle i}$ ${\displaystyle M_{i}}$

El índice Gittins de ese estado es la recompensa total más alta que se puede lograr si uno siempre puede elegir continuar o reiniciar desde ese estado . ${\displaystyle i}$ ${\displaystyle M_{i}}$ ${\displaystyle i}$

${\displaystyle h(i)=\sup _{\pi }\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z^{\pi }(t)]\right\rangle _{Z(0)=i}}$

donde indica una política sobre . Se cumple que ${\displaystyle \pi }$ ${\displaystyle M_{i}}$

${\displaystyle h(i)=w(i)}$.

Índice generalizado

Si la probabilidad de supervivencia depende del estado , una generalización introducida por Sonin ^[11] (2008) define el índice de Gittins como la recompensa total máxima descontada por probabilidad de terminación. ${\displaystyle \beta (i)}$ ${\displaystyle i}$ ${\displaystyle \alpha (i)}$

${\displaystyle \alpha (i)=\sup _{\tau >0}{\frac {R^{\tau }(i)}{Q^{\tau }(i)}}}$

dónde

${\displaystyle R^{\tau }(i)=\left\langle \sum _{t=0}^{\tau -1}R[Z(t)]\right\rangle _{Z(0)=i}}$

${\displaystyle Q^{\tau }(i)=\left\langle 1-\prod _{t=0}^{\tau -1}\beta [Z(t)]\right\rangle _{Z(0)=i}}$

Si se reemplaza por en las definiciones de , y , entonces se cumple que ${\displaystyle \beta ^{t}}$ ${\displaystyle \prod _{j=0}^{t-1}\beta [Z(j)]}$ ${\displaystyle \nu (i)}$ ${\displaystyle w(i)}$ ${\displaystyle h(i)}$

${\displaystyle \alpha (i)=h(i)=w(i)}$

${\displaystyle \alpha (i)\neq k\nu (i),\forall k}$

Esta observación lleva a Sonin ^[11] a concluir que y no es el "verdadero significado" del índice de Gittins. ${\displaystyle \alpha (i)}$ ${\displaystyle \nu (i)}$

Teoría de colas

En la teoría de 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 bajo una programación de índice de Gittins se puede determinar utilizando el enfoque SOAP. ^[14] Nótese 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 de aprendizaje, donde la estocasticidad se explica explícitamente a través de un término de ruido.

Problemas fraccionarios

Si bien los índices Gittins convencionales inducen una política para optimizar la acumulación de una recompensa, un problema común consiste en optimizar la proporción de recompensas acumuladas. Por ejemplo, este es un caso en el que los sistemas buscan maximizar el ancho de banda, que consiste en datos a lo largo del tiempo, o minimizar 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 permanencia desproporcionado solo para acumular una recompensa mayor. 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 proporción es que, una vez que la proporción alcanzada en algún estado es alta, la optimización puede seleccionar estados que conducen a una proporción baja porque tienen una alta probabilidad de terminación, de modo que es probable que el proceso termine antes de que la proporción caiga significativamente. Una configuración de problemas para evitar tales terminaciones tempranas consiste en definir la optimización como la maximización de la proporción futura observada por cada estado. Se conjetura que existe una indexación para este problema, que se puede calcular como una variación simple de los algoritmos existentes de reinicio en el estado o de eliminación de estados y que se evalúa que funciona bien en la práctica. ^[15]

Notas

1. 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.
2. Gittins, JC (1979). "Procesos Bandit e índices de asignación dinámica". Revista de la Royal Statistical Society. Serie B (Metodológica) . 41 (2): 148–177. doi :10.1111/j.2517-6161.1979.tb01068.x. JSTOR  2985029. S2CID  17724147.
3. Mitten L (1960). "Una solución analítica al problema de la secuencia de pruebas de menor costo". Revista de ingeniería industrial . 11 (1): 17.
4. 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.
5. 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. S2CID  32530881.
6. Whittle, Peter (1980). "Bandidos multiarmados y el índice de Gittins". Revista de la Royal Statistical Society, Serie B. 42 ( 2): 143–149. doi :10.1111/j.2517-6161.1980.tb01111.x.
7. Varaiya, P.; Walrand, J.; Buyukkoc, C. (mayo de 1985). "Extensiones del problema del bandido multiarmado: el caso descontado". IEEE Transactions on Automatic Control . 30 (5): 426–439. doi :10.1109/TAC.1985.1103989.
8. Chen, Yih Ren; Katehakis, Michael N. (1986). "Programación lineal para problemas de bandidos multiarmados de estados finitos". Matemáticas de la investigación de operaciones . 11 (1): 180–183. doi :10.1287/moor.11.1.180.
9. Kallenberg, Lodewijk CM (1986). "Una nota sobre el cálculo del índice de Gittins de MN Katehakis y Y.-R. Chen". Matemáticas de la investigación de operaciones . 11 (1): 184–186. doi :10.1287/moor.11.1.184.
10. Katehakis, Michael N. ; Veinott, Arthur F. Jr. (1987). "El problema del bandido multiarmado: descomposición y computación". Matemáticas de la investigación de operaciones . 12 (2): 262–268. doi :10.1287/moor.12.2.262. JSTOR  3689689. S2CID  656323.
11. Sonin I (2008). "Un índice de Gittins generalizado para una cadena de Markov y su cálculo recursivo". Statistics and Probability Letters . 78 (12): 1526–1533. doi :10.1016/j.spl.2008.01.049.
12. Ni, Mora J (2007). "Un algoritmo de pivoteo rápido (2/3)^n para el índice de Gittins y la detención óptima de una cadena de Markov". INFORMS Journal on Computing . 19 (4): 596–606. CiteSeerX 10.1.1.77.5127 . doi :10.1287/ijoc.1060.0206. S2CID  122785013. 
13. Cowan, Wesley; Katehakis, Michael N. (enero de 2015). "Bandidos multiarmados bajo depreciación general y compromiso". Probabilidad en la ingeniería y las ciencias de la información . 29 (1): 51–76. doi : 10.1017/S0269964814000217 .
14. 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 . 2 (1). ACM: 16. doi :10.1145/3179419. S2CID  216145213.{{cite journal}}: CS1 maint: multiple names: authors list (link)
15. Di Gregorio, Lorenzo y Frascolla, Valerio (1 de octubre de 2019). Optimalidad de entrega en redes heterogéneas. Foro Mundial 5G. arXiv : 1908.09991v2 . Archivado desde el original el 28 de septiembre de 2020. Consultado el 18 de abril de 2020 .{{cite conference}}: CS1 maint: multiple names: authors list (link)

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 . 2 (1). ACM: 16. doi :10.1145/3179419. S2CID  216145213.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Berry, Donald A. y Fristedt, Bert (1985). Problemas de bandidos: asignación secuencial de experimentos . Monografías sobre estadística y probabilidad aplicada. Londres: Chapman & Hall. ISBN 978-0-412-24810-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Gittins, JC (1989). Índices de asignación de bandidos multiarmados . 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). "Sobre el índice de Gittins para bandidos multiarmados". Anales de probabilidad aplicada . 2 (4): 1024–1033. doi :10.1214/aoap/1177005588. JSTOR  2959678.
• Katehakis, Michael N. ; Veinott, Arthur F. Jr. (1987). "El problema del bandido multiarmado: descomposición y computación". Matemáticas de la investigación de operaciones . 12 (2): 262–268. doi :10.1287/moor.12.2.262. JSTOR  3689689. S2CID  656323.
• Cowan, W. y MN Katehakis (2014). "Bandidos multiarmados bajo depreciación general y compromiso". Probabilidad en la ingeniería y las 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.