José Niño Mora
Departamento de Estadística. Universidad Carlos III de Madrid
0000-0002-2172-3983

jose.nino@uc3m.es

Abstract

Este artículo se propone presentar de forma concisa y accesible a lectores no especialistas las principales contribuciones del trabajo del autor “A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits”, Mathematics of Operations Research, vol. 45, no. 2, 465–496, 2020, que fue galardonado con el Premio SEIO – Fundación BBVA 2020 en la categoría de “Mejor contribución metodológica en Investigación Operativa”.

Keywords: Indexabilidad, Índice de Whittle, Leyes de conservación parciales, Restless bandits.

MSC Subject classifications: 90C40, 90B36, 90C39, 90C48.

Introducción

Este artículo se propone presentar de forma concisa y accesible a lectores no especialistas las principales contribuciones de mi artículo Niño-Mora (2020), que fue galardonado con el Premio SEIO – Fundación BBVA 2020 (en su primera convocatoria) en la categoría de “Mejor contribución metodológica en Investigación Operativa”.

El trabajo versa sobre problemas de tipo bandit, un término inglés sui géneris que emplearé en dicho idioma a falta de un equivalente exacto en español. El término one-armed bandit se emplea coloquialmente para designar lo que en español llamaríamos una máquina tragaperras, ya que, antes de que estas se operasen pulsando botones, el jugador debía accionar una palanca (arm) para jugar. En tal contexto, el lector apreciará el sentido del término bandit.

Un modelo probabilístico sencillo para un bandit podría representar los premios resultantes de distintas jugadas como variables aleatorias Bernoulli i.i.d. Así, en cada jugada ganamos un premio de \(1\) €  con cierta probabilidad \(p\), y no ganamos nada con probabilidad \(1-p\). Si el precio de cada jugada es un importe fijo de \(\lambda\) €, es evidente que solo nos interesa jugar si \(p > \lambda\).

El caso anterior resulta trivial porque hemos supuesto conocida la probabilidad \(p\). Resulta más realista suponer que no la conocemos. En tal caso, ¿hasta qué precio deberíamos estar dispuestos a pagar por jugar? Para poder responder a esta pregunta es necesario elaborar más el modelo. Adoptando un enfoque bayesiano, supongamos que \(p\) —vista ahora como una variable aleatoria— tiene una distribución a priori \(\mathrm{Beta}(m, n)\), donde \(m\) representa el número de éxitos (premio de \(1\) €) y \(n\) el número de fracasos (sin premio), de tal manera que la esperanza a priori de \(p\) es \(m / (m + n)\). Si no disponemos de información previa, podemos tomar, e.g., \(m = n = 1\). Si jugamos y ganamos, lo cual ocurre con probabilidad \(m / (m + n)\), la distribución a posteriori de \(p\) será \(\mathrm{Beta}(m+1, n)\), mientras que, si perdemos, será \(\mathrm{Beta}(m, n+1)\).

Lo anterior nos lleva a considerar que los parámetros de dicha distribución Beta en un momento dado constituyen el estado del sistema en cuestión. Este evoluciona y proporciona premios en jugadas sucesivas como una cadena de Markov con recompensas.

Ahora sí podemos formular con precisión la pregunta planteada anteriormente. Supongamos que las jugadas se realizan en etapas de tiempo \(t = 0, 1, 2, \ldots\), que las recompensas obtenidas en la etapa \(t\) se descuentan de forma geométrica con un factor de descuento por etapa \(0 < \beta < 1\), y que, en cada etapa, podemos decidir si continuamos jugando o abandonamos. En tal contexto, ¿hasta qué precio \(\lambda\) deberíamos estar dispuestos a pagar por jugar cada vez, partiendo del estado \((m, n)\)? O, de forma equivalente, ¿cuál es la política óptima para decidir cuándo abandonar el juego consiguiendo la máxima esperanza posible de la ganancia total descontada?

Este problema, que ya no es trivial, fue resuelto por primera vez por Bellman (1956), quien demostró lo siguiente: Existe una función \(\lambda^*\colon \mathbb{N}^2 \to \mathbb{R}\) (donde \(\mathbb{N}\) denota los números naturales empezando en \(1\)) tal que es óptimo jugar cuando el estado actual es \((m, n)\) si y solo si \(\lambda^*(m, n) \geqslant \lambda\), y es óptimo parar si y solo si \(\lambda^*(m, n) \leqslant \lambda\). Así, \(\lambda^*(m, n)\) representa el valor justo de jugar en el estado \((m, n)\).

Posteriormente, Gittins and Jones (1974) extendieron la solución de Bellman a un modelo general dado por una cadena de Markov con recompensas. Así, supongamos que el estado del bandit en cuestión evoluciona como una cadena de Markov \(X_t\) en etapas \(t = 0, 1, 2, \ldots\) sobre el espacio de estados \(\mathcal{X}\). Tras observar el estado \(X_t = x\) al comienzo de la etapa \(t\), podemos decidir continuar o parar. La opción de continuar (es decir, jugar una vez más) conlleva obtener una recompensa neta \(R(X_t) – \lambda\) (donde hemos restado el precio \(\lambda\) de jugar) que es función del estado, tras lo cual la cadena evoluciona al siguiente estado \(X_{t+1}\) de acuerdo con su ley de evolución Markoviana. La opción de parar no conlleva recompensa ni coste alguno, y supone abandonar el juego.

En tal contexto, podemos plantear la pregunta anterior: ¿Cuál es la política óptima para decidir cuándo abandonar consiguiendo la máxima esperanza posible de la ganancia total descontada? Resulta que la política óptima tiene la misma estructura que en el problema resuelto por Bellman, en términos de una función \(\lambda^*\colon \mathcal{X} \to \mathbb{R}\): es óptimo continuar jugando en el estado \(x\) si y solo si \(\lambda^*(x) \geqslant \lambda\), y es óptimo parar si y solo si \(\lambda^*(x) \leqslant \lambda\). Así, \(\lambda^*(x)\) representa el valor justo de jugar en el estado \(x\).

Pero Gittins and Jones (1974) fueron más allá, y consideraron el siguiente problema sustancialmente más complejo. Supongamos que, en lugar de un bandit, nos planteamos cómo jugar cuando tenemos enfrente una colección de, digamos, \(N\) bandits, donde cada bandit \(n = 1, \ldots, N\) tiene su propio espacio de estados, ley de evolución y función de recompensa de etapa. La restricción clave es que solo podemos jugar a uno de los \(n\) bandits en cada etapa.

Tal problema representa una versión de un problema clásico cuyo estudio se remonta a la década de 1930, con el trabajo pionero de Thompson (1933): el denominado problema multi-armed bandit (PMAB). La versión considerada por Gittins y Jones se puede abordar en principio mediante un enfoque de programación dinámica, basado en formular y resolver las ecuaciones de Bellman. Sin embargo, las incógnitas de dichas ecuaciones, que representan la función de valor óptimo, toman la forma \(v^*(x_1, \ldots, x_N)\), donde \(x_n\) es un estado del bandit \(n\), ya que el estado del sistema es ahora \(N\)-dimensional. Pero tal enfoque resulta numéricamente impracticable incluso para valores de \(N\) solo moderadamente grandes, ya que dichas ecuaciones sufren de la conocida como maldición de la dimensionalidad.

Descartado el enfoque numérico, numerosos autores trataron durante décadas, infructuosamente, de dilucidar la estructura de la política óptima para el PMAB. Pero no fue hasta el trabajo de Gittins and Jones (1974) cuando se aclaró que la política óptima tiene una estructura notablemente sencilla e intuitiva, dada en términos de las funciones \(\lambda_n^*(x_n)\) indicadas anteriormente: en una etapa en la cual el estado conjunto sea \((x_1, \ldots, x_N)\), es óptimo jugar a un bandit \(n\) con el mayor valor de \(\lambda_n^*(x_n)\).

Así, las funciones \(\lambda_n^*(x_n)\) se emplean como índices de prioridad, de tal manera que, cuanto mayor sea su valor, mayor es la prioridad para jugar al bandit correspondiente. La política óptima resultante es un ejemplo de política índice. En particular, la descrita anteriormente es la política índice de Gittins, y al índice \(\lambda_n^*(x_n)\) en que está basada se le conoce como índice de Gittins.

El enfoque anterior para el PMAB ha generado una vasta literatura, debido no solo a su interés teórico sino a sus múltiples aplicaciones. Ver, e.g., el artículo de discusión Gittins (1979) y la monografía Gittins (1989). Además, varios autores han presentado diversas demostraciones de tal resultado (optimalidad de una política índice) y extensiones. Ver, e.g., Whittle (1980), Varaiya, Walrand, and Buyukkoc (1985), Weber (1992), Tsitsiklis (1994), y Bertsimas and Niño-Mora (1996).

En un contexto más general, el PMAB modeliza la asignación dinámica óptima de un recurso a múltiples proyectos (en adelante emplearemos indistintamente los términos proyecto y bandit), uno de los cuales debe ser seleccionado como activo en cada etapa. Un supuesto clave en tal modelo es que los proyectos no seleccionados (pasivos) no cambian de estado. Whittle (1988) consideró las consecuencias de eliminar tal supuesto, permitiendo que los proyectos pasivos puedan cambiar de estado, según una ley de evolución que no tiene por qué coincidir con la que prevalece para proyectos activos. Los proyectos resultantes se denominan, por tanto, restless bandits.

La inclusión de transiciones de estado pasivas aumenta enormemente el poder de modelización del modelo clásico PMAB, dando lugar a su extensión conocida como el problema restless multi-armed bandit (PRMAB). En este, además, Whittle (1988) permitió también que se pudiese seleccionar un número arbitrario \(K\) de proyectos en cada etapa, con \(1 \leqslant K < N\), en contraste con el modelo clásico PMAB que requería \(K = 1\).

El poder aumentado de modelización del PRMAB con respecto al PMAB se obtiene a costa de perder la tractabilidad de este, ya que las políticas índice no son, en general, óptimas para aquel. De hecho, se ha probado que el PRMAB es computacionalmente intratable, en concreto P-space hard. Ver Papadimitriou and Tsitsiklis (1999). Pese a ello, Whittle propuso en dicho artículo una política índice subóptima para el PRMAB, basada en un enfoque de relajación lagrangiana y descomposición, y en la solución óptima de ciertos subproblemas para un único proyecto. Tal política índice de Whittle, basada en el empleo del índice de Whittle como índice de prioridad para el PRMAB, ha sido empleada en multitud de aplicaciones de dicho modelo. Los estudios computacionales típicamente reportan que su rendimiento es muy cercano al óptimo. En cuanto a su análisis teórico, Whittle conjeturó que su política índice es asintóticamente óptima, en el límite en que \(K\) y \(N\) tienden a infinito en razón constante. Dicha conjetura ha sido probada por diversos investigadores bajo distintos supuestos, comenzando con Weber and Weiss (1990). Para una panorámica de la investigación en este campo durante las tres últimas décadas, ver el reciente artículo de revisión Niño-Mora (2023).

Sin embargo, hay un obstáculo que dificulta la aplicación práctica de la política índice de Whittle. A diferencia del índice de Gittins, que existe para cualquier modelo bandit sin transiciones pasivas, el índice de Whittle solo existe para un subconjunto de modelos restless bandits, que Whittle denominó indexables. El propio Whittle indicó en su artículo seminal sobre este tema que no resulta sencillo determinar si un modelo dado es indexable, y que sería deseable disponer de condiciones suficientes de indexabilidad.

Los investigadores en este campo han empleado diversas técnicas ad hoc para probar, de forma más o menos rigurosa, la indexabilidad de los modelos considerados, y para calcular el índice de Whittle. En contraste con tales procedimientos, el autor de estas líneas ha venido desarrollando desde hace más de dos décadas una metodología general rigurosa y flexible para superar los obstáculos que plantea la indexabilidad. Los artículos clave en el desarrollo de dicha metodología son los siguientes: Niño-Mora (2001) (proyectos con estado finito), Niño-Mora (2002) (proyectos con estado finito incorporando asignación dinámica de un recurso genérico), Niño-Mora (2006) (proyectos con estado infinito numerable), y Niño-Mora (2020) (proyectos con estado real). Otros trabajos del autor no mencionados aquí abordan aspectos algorítmicos y aplicaciones.

El enfoque metodológico indicado más arriba se fundamenta en la identificación y aplicación de leyes de conservación, que extienden la identificada por Kleinrock en su trabajo clásico Kleinrock (1965), las cuales han desempeñado un importante papel en la resolución mediante políticas índice de modelos estocásticos de sistemas de servicio. Véase al respecto el artículo Niño-Mora (2011). En particular, Niño-Mora (2001) introdujo una extensión de las leyes de conservación identificadas anteriormente, que el autor denominó leyes de conservación parciales (PCL en sus siglas en inglés), en las cuales se basa dicho enfoque.

Los trabajos del autor indicados anteriormente desarrollan el enfoque basado en PCL para resolver la indexabilidad de modelos restless bandits, extendiéndolo a modelos cada vez más complejos, llegando hasta los modelos de tipo PRMAB donde los proyectos tienen un estado real en Niño-Mora (2020).

La principal motivación de estos últimos viene de un importante campo de investigación aplicada: la asignación dinámica óptima de recursos en redes de sensores. En efecto, los sensores recogen a lo largo del tiempo información sobre el estado del mundo real. Sin embargo, tal información es imperfecta, lo cual se puede modelizar considerando que el estado conocido es una distribución de probabilidad sobre el estado auténtico subyacente, el cual no es observable. Si este último solo puede tomar dos valores, \(0\) y \(1\), basta considerar la probabilidad de que se encuentre en el estado \(1\). Otra posibilidad es considerar que el estado conocido es la varianza del error de observación del sensor, suponiendo mediciones unidimensionales. En ambos casos, el estado conocido, que es distinto del estado subyacente no observable, es continuo, o, en particular, real.

Por tanto, diversos problemas de asignación dinámica de sensores se pueden formular como modelos de tipo PRMAB en los cuales los proyectos, que en tal contexto pueden representar, e.g., objetivos móviles sobre los que se desea realizar un seguimiento mediante la asignación dinámica de sensores, tienen un estado continuo. Ver, e.g., La Scala and Moran (2006), Mahajan and Teneketzis (2008), Moran, Suvorova, and Howard (2008), Washburn (2008), Liu and Zhao (2010), Dance and Silander (2015), Dance and Silander (2019) y Zhao (2020). En tal contexto, los proyectos se modelizan mediante procesos de decisión Markovianos parcialmente observados (POMDP en sus siglas en inglés). Ver, e.g., la monografía de Krishnamurthy (2016).

Si en modelos de tipo PRMAB con estado discreto no resulta sencillo establecer su indexabilidad, tal objetivo resulta aún más difícil en los modelos arriba mencionados para la operación óptima de redes de sensores, incluso cuando el estado de cada proyecto es real. Tal es la motivación del trabajo reseñado en este artículo, Niño-Mora (2020): encontrar condiciones generales para la indexabilidad de restless bandits con estado real, y dilucidar cómo calcular el índice de Whittle y extensiones en tales modelos.

El resto del artículo se organiza como sigue. La sección 2 plantea el problema resuelto en Niño-Mora (2020). La sección 3 esboza la resolución del problema mediante condiciones suficientes de indexabilidad. La sección 4 comenta sobre la aplicación de las condiciones de indexabilidad, y reseña cómo otros autores las han aplicado con éxito. Finalmente, la sección 5 concluye el artículo con una breve discusión.

Indexabilidad para proyectos con estado real: planteamiento del problema

Control dinámico de un proyecto, métricas y problemas \(\lambda\)-precio

Consideramos aquí un modelo de tipo restless bandit para la asignación dinámica óptima de un recurso a un proyecto, cuyo estado \(X_{t}\) evoluciona en tiempo discreto sobre un horizonte infinito a través del espacio de estados \(\mathsf{X} \triangleq [\ell, u]\).

Al comienzo de cada etapa de tiempo \(t = 0, 1, \ldots\), el controlador del proyecto observa el estado \(X_t\), tras lo cual selecciona una acción \(A_t \in \{0, 1\}\), donde \(A_t = 1\) (resp. \(A_t = 0\)) modeliza que el proyecto está siendo operado en el modo activo (resp. modo pasivo) en la etapa \(t\). Denotamos como \(\mathsf{K} \triangleq \mathsf{X} \times \{0, 1\}\) el espacio de estados-acciones. Si \((X_t, A_t) = (x, a)\) entonces: (i) asignamos al proyecto \(c(x, a)\) unidades del recurso y obtenemos una recompensa \(r(x, a)\) en la etapa \(t\), estando ambos geométricamente descontados con el factor \(\beta \in [0, 1)\); y (ii) el estado se mueve a \(X_{t+1}\) de acuerdo con un kernel Markoviano de transición \(\kappa^a(\cdot, \cdot)\) sobre \(\mathsf{X}\) con función de distribución cumulativa (CDF en sus siglas en inglés) \(Q^a(x, \cdot)\), luego \(\mathbb{P}\{X_{t+1} \leqslant y \, | \, (X_t, A_t) = (x, a)\} = Q^a(x, y) \triangleq \kappa^a(x, (-\infty, y])\).

En adelante mantendremos el siguiente supuesto

Nótese que el Supuesto [ass:first](ii) corresponde al enfoque de normas sup ponderadas para procesos de decisión Markovianos con criterio descontado (ver (Lippman 1975; Wessels 1977; Heilmann 1977; Van Nunen and Wessels 1978) y (Hernández-Lerma and Lasserre 1999, Supuesto 8.3.2)), el cual permite que \(r(\cdot, a)\) y \(c(\cdot, a)\) sean no acotadas.

Las acciones se seleccionan mediante una política de control \(\pi = (\pi_t)_{t=0}^\infty\), perteneciente a la clase \(\Pi\) de políticas aleatorizadas no anticipativas, las cuales seleccionan en cada etapa \(t\) la acción \(A_t = a\) con probabilidad \(\pi_t(a \, | \, \mathcal{H}_t)\), una función medible de la historia \(\mathcal{H}_t \triangleq \big((X_s, A_s)_{s=0}^{t-1}; X_t\big)\). Además consideramos la clase \(\Pi^{\scriptscriptstyle \textup{SR}}\) de políticas estacionarias aleatorizadas, donde \(\pi_t(a \, | \, \mathcal{H}_t) = p(a \, | \, X_t)\) para alguna función \(p(\cdot \, | \, \cdot) \geqslant 0\) con \(\sum_{a} p(a \, | \, x) = 1\) para cada \(x\), y la clase \(\Pi^{\scriptscriptstyle \textup{SD}}\) de políticas estacionarias deterministas, donde \(p(1 \, | \, x) = 1_{B}(x)\) para alguna región activa \(B \in \mathcal{B}(\mathsf{X})\). Así, nos referiremos a la \(B\)-política, escribiendo \(\pi = B\).

Para una política admisible \(\pi \in \Pi\) y una distribución de probabilidad \(p\) sobre \(\mathcal{B}(\mathsf{X})\) sobre el estado inicial (\(X_0 \sim p\)), sea \(\mathbb{P}_p^{\pi}\) la distribución de probabilidad que determinan sobre el espacio \(\mathsf{K}^\infty\) de caminos estado-acción con la \(\sigma\)-algebra producto. Denotamos con \(\mathbb{E}_p^{\pi}\) la correspondiente esperanza, escribiendo \(\mathbb{P}_x^{\pi}\) y \(\mathbb{E}_x^{\pi}\) cuando \(p = \delta_x\), la distribución de Dirac concentrada en \(x\).

Evaluamos una política \(\pi\) partiendo de \(p\) con las métricas de rendimiento de \((\)uso de\()\) recurso y de recompensa

\[\label{eq:FGboldx0pis}
F(p, \pi) \triangleq \mathbb{E}_{p}^{\pi}\left[\sum_{t = 0}^\infty
\beta^t r(X_{t}, A_{t})\right] \quad \textup{y} \quad G(p, \pi)\triangleq \mathbb{E}_{p}^{\pi}\Bigg[\sum_{t = 0}^\infty
\beta^t c(X_{t}, A_{t})\Bigg],\qquad(2)\]

las cuales escribimos como \(F(x, \pi)\) y \(G(x, \pi)\) cuando \(X_0 = x\), y como \(F(p, B)\) y \(G(p, B)\) cuando \(\pi = B\).

Supongamos que se carga un precio \(\lambda\) por unidad de recurso empleada, y denotemos con \(V_\lambda(p, \pi) \triangleq F(p, \pi)- \lambda G(p, \pi)\) la métrica de valor neto del proyecto. Consideremos la siguiente colección de problemas de control óptimo del proyecto, parametrizada por el precio del recurso \(\lambda \in \mathbb{R}\):

\[\label{eq:lpreciopfg1}
P_\lambda\colon \qquad \textup{encontrar } \pi_\lambda^* \in \Pi \textup{ tal que } V_\lambda(x, \pi_\lambda^*) = \sup_{\pi \in \Pi} \, V_\lambda(x, \pi) \textup{ para cada } x \in \mathsf{X}.\qquad(3)\]

Llamaremos a \(P_\lambda\) el problema \(\lambda\)-precio y denotaremos con \(V_\lambda^*(x) \triangleq \sup_{\pi \in \Pi} \, V_\lambda(x, \pi)\) su función de valor óptimo, para \(x \in \mathsf{X}\). Diremos que una política \(\pi_\lambda^*\) es \(P_\lambda\)-óptima si \(V_\lambda(x, \pi_\lambda^*) = V_\lambda^*(x)\) para cada \(x\).

A continuación esbozamos resultados relevantes del enfoque basado en normas sup ponderadas a los procesos de decisión Markovianos, los cuales aseguran, en particular, que cada problema \(\lambda\)-precio se puede resolver mediante una política estacionaria determinista. Denotemos con \(\mathbb{B}_w(\mathsf{K})\) y \(\mathbb{B}_w(\mathsf{X})\) los espacios de Banach (ver (Hernández-Lerma and Lasserre 1999, Prop. 7.2.1)) de funciones medibles \(w\)-acotadas \(u\colon \mathsf{K} \to \mathbb{R}\) y \(v\colon \mathsf{X} \to \mathbb{R},\) respectivamente, con \(w\)-normas finitas, dadas por

\[\label{eq:vxwnorm}
\| u \|_w \triangleq \sup \bigg\{\frac{\vert u \vert (x, a) }{w(x)}\colon (x, a) \in \mathsf{K}\bigg\}
\quad \textup{and} \quad
\| v \|_w \triangleq \sup \bigg\{\frac{\vert v \vert (x)}{w(x)}\colon x \in \mathsf{X}\bigg\},\qquad(4)\]

y escribamos como \(\mathbb{P}_w(\mathsf{X})\) el espacio de medidas de probabilidad \(p\) sobre \(\mathcal{B}(\mathsf{X})\) con \(w\)-norma finita, dada por

\[\label{eq:pmwnorm}
\| p \|_w \triangleq \int w \, dp = \mathbb{E}_{p}[w(X_0)].\qquad(5)\]

Denotemos además con \(\mathbb{C}_w(\mathsf{K}) \triangleq \mathbb{C}(\mathsf{K}) \cap \mathbb{B}_w(\mathsf{K})\) y \(\mathbb{C}_w(\mathsf{X}) \triangleq \mathbb{C}(\mathsf{X}) \cap \mathbb{B}_w(\mathsf{X})\) el subspacio correspondiente de funciones continuas \(w\)-acotadas.

En adelante, \(F(\cdot, \pi)\), \(G(\cdot, \pi)\) y \(V_\lambda(\cdot, \pi)\) denotarán las funciones sobre \(\mathsf{X}\) correspondientes a las métricas de recompensa, recurso y valor neto del proyecto, \(F(x, \pi)\), \(G(x, \pi)\) y \(V_\lambda(x, \pi)\).

A la luz de la Observación [re:assboundfs](vi), diremos que la acción \(a\) es \(P_\lambda\)-óptima en el estado \(x\) si \(\mathcal{T}_\lambda^a V_\lambda^*(x) \geqslant \mathcal{T}_\lambda^{1-a} V_\lambda^*(x)\). Por tanto, ambas acciones serán \(P_\lambda\)-óptimas en \(x\) si y solo si se cumple la siguiente ecuación:

\[\label{eq:bothactopt}
\mathcal{T}_\lambda^0 V_\lambda^*(x) = \mathcal{T}_\lambda^1 V_\lambda^*(x).\qquad(12)\]

Indexabilidad

Abordaremos la colección de problemas \(\{P_\lambda\colon \lambda \in \mathbb{R}\}\) mediante el concepto de indexabilidad, extendido en Whittle (1988) desde su origen en bandits sin transiciones pasivas a restless bandits con consumo de recurso \(c(x, a) \equiv a\), y extendido en Niño-Mora (2002) a funciones \(c(x, a)\) generales.

Para un precio \(\lambda\) y una acción \(a\), definimos la \(a\)-región \(P_\lambda\)-óptima \(S^{*, a}_\lambda\) por

\[\label{eq:Sstarlam}
S^{*, a}_\lambda \triangleq \big\{x \in \mathsf{X}\colon \mathcal{T}_\lambda^a V_\lambda^*(x)
\geqslant \mathcal{T}_\lambda^{1-a} V_\lambda^*(x)\big\},\qquad(13)\]

de tal manera que se compone de aquellos estados \(x\) donde la acción \(a\) es \(P_\lambda\)-óptima. Bajo indexabilidad, tales regiones están caracterizadas por un índice asociado a los estados del proyecto.

Definición 1: Decimos que un proyecto es indexable si existe un índice \(\lambda^*\colon \mathsf{X} \to \mathbb{R}\) tal que

\[\label{eq:Sstar10}
S^{*, 1}_\lambda = \{x \in \mathsf{X}\colon \lambda^*(x) \geqslant \lambda\} \; \textup{ y } \;
S^{*, 0}_\lambda = \{x \in \mathsf{X}\colon \lambda^*(x) \leqslant \lambda\}, \quad \lambda \in \mathbb{R}.\qquad(14)\]

Nos referiremos al índice de Gittins y al índice de Whittle según el proyecto no admita o admita transiciones pasivas de estado.

Observación 2:

Como ya se indicó en Whittle (1988), no todos los proyectos de tipo restless bandit son indexables. Ello motiva la cuestión de dilucidar condiciones suficientes de indexabilidad que no requieran evaluar la función de valor óptimo \(V_\lambda^*\). Tal el el principal objetivo de este trabajo.

Indexabilidad-umbral fuerte

Centraremos el análisis de la indexabilidad en el caso en que se cumple de forma consistente con la optimalidad de políticas umbral. Para cada umbral \(z \in \overline{\mathbb{R}}\) consideramos dos políticas estacionarias deterministas: la \(z\)-política, con región activa \((z, u]\), en la cual el proyecto está activo en la etapa \(t\) (\(A_t = 1\)) cuando su estado supera el umbral (\(X_t > z\)); y la \(z^{\scriptscriptstyle -}\)-política, con región activa \([z, u]\), en la cual \(A_t = 1\) cuando \(X_t \geqslant z\). Escribiremos las métricas correspondientes como \(F(p, z)\), \(G(p, z)\), \(F(p, z^{\scriptscriptstyle -})\) y \(G(p, z^{\scriptscriptstyle -})\).

Denotaremos con \(F(p, \cdot)\) y \(G(p,\cdot)\) las funciones sobre \(\mathbb{R}\) que mapean \(z\) a \(F(p, z)\) y \(G(p, z)\), respectivamente.

Además, para un umbral \(z \in \overline{\mathbb{R}}\) y un escalar \(\alpha \in [0, 1]\) nos referiremos a la política umbral aleatorizada \(\alpha z^{\scriptscriptstyle -} + (1-\alpha) z\), la cual, en cada estado \(x\), toma la acción \(a = 1\) si \(x > z\); toma la acción \(a = 0\) si \(x < z\); y toma las acciones \(a = 0\) y \(a = 1\) con probabilidades \(\alpha\) y \(1-\alpha\), respectivamente, si \(x = z\).

Métricas de rendimiento marginal e índice de productividad marginal

Emplearemos los conceptos de métricas de rendimiento marginal e índice de productividad marginal (PM), introducidos en Niño-Mora (2002) para restless bandits con estado discreto, los cuales adaptamos a continuación al presente contexto con estado real.

Para una acción \(a\) y una política \(\pi\), sea \(\langle a, \pi\rangle\) la política que toma la acción \(a\) en la etapa inicial \(t = 0\) y después adopta la política \(\pi\) desde \(t = 1\) en adelante. Medimos los cambios en recompensas ganadas y en recurso gastado, respectivamente, como resultado de cambiar de la política \(\langle 0, \pi\rangle\) a \(\langle 1, \pi\rangle\) comenzando en el estado \(x\) mediante la métrica de recompensa marginal

\[\label{eq:mrm1}
f(x, \pi)\triangleq \Delta_{a=0}^{a=1} F(x, \langle a, \pi\rangle) = F(x, \langle 1, \pi\rangle) – F(x, \langle 0, \pi\rangle)\qquad(15)\]

y la métrica de recurso marginal

\[\label{eq:mwm1}
g(x, \pi)\triangleq \Delta_{a=0}^{a=1} G(x, \langle a, \pi\rangle).\qquad(16)\]

Si \(g(x, B)\neq 0\) para algún \(x\) y \(B\), medimos la PM que resulta de tomar la acción activa vs. la pasiva en \(t = 0\) partiendo de \(x\), en relación a la \(B\)-política, mediante la PM-métrica

\[\label{eq:mpm1}
m(x, B)\triangleq \frac{f(x, B)}{g(x, B)}.\qquad(17)\]

Escribiremos como \(f(x, z)\), \(g(x, z)\), \(m(x, z)\) y \(f(x, z^{\scriptscriptstyle -})\), \(g(x, z^{\scriptscriptstyle -})\), \(m(x, z^{\scriptscriptstyle -})\) las métricas marginales para la \(z\)-política y para la \(z^{\scriptscriptstyle -}\)-política, respectivamente.

A continuación empleamos la PM-métrica para definir el índice PM.

Resolución del problema: un teorema de verificación para indexabilidad-umbral fuerte

En esta sección presentamos el principal resultado del artículo, un teorema de verificación que proporciona condiciones suficientes de indexabilidad, el cual, en contraste con la aplicación directa de la Definition [def:indx], no requiere ni que se evalúe la función de valor óptimo \(V_\lambda^*\) del problema \(\lambda\)-precio \(P_\lambda\) ni tampoco estudiar sus propiedades. En su lugar, las condiciones que tenemos que verificar aquí conciernen propiedades de las métricas del proyecto bajo políticas umbral, y por tanto requieren únicamente el análisis de rendimiento de tales políticas.

Las condiciones suficientes en nuestro teorema de verificación corresponden al concepto de PCL-indexabilidad, que este teorema extiende del contexto de estado discreto en Niño-Mora (2001, 2002, 2006, 2007) al presente contexto de estado real.

El teorema de verificación se formula a continuación.

Aplicación de las condiciones de indexabilidad

La Sección 12 del artículo Niño-Mora (2020) ilustra la aplicación del Teorema [the:pcliii] mediante dos ejemplos, uno sobre un modelo de transmisiones óptimas de paquetes de datos sobre un canal de comunicaciones parcialmente observable, y otro sobre la operación óptima de un robot de búsqueda en internet. Sin embargo, entre las aplicaciones de tal resultado desde su introducción destaca la desarrollada por Dance and Silander (2019). En este trabajo extraordinario, sus autores aplican el Teorema [the:pcliii] para demostrar la indexabilidad del modelo restless bandit con dinámica dada por el filtro de Kalman, el cual es relevante para aplicaciones de seguimiento de objetivos móviles mediante radares, véase La Scala and Moran (2006). Además, el trabajo Dance and Silander (2019) aclara por qué los intentos previos de obtener tal resultado mediante la aplicación de técnicas estándar, como la submodularidad, resultaron infructuosos: ello se debe a que este modelo no cumple los supuestos en que se basan tales técnicas.

Conclusión

El artículo Niño-Mora (2020), si bien extiende resultados previos del autor, sin embargo por otra parte representa un punto de partida para el análisis de modelos más complejos. En particular, el análisis de modelos restless bandits con estado real y múltiples acciones, y con estado continuo multi-dimensional, plantean desafíos que serán objeto de futuras investigaciones.

Agradecimientos

El artículo Niño-Mora (2020) ha sido desarrollado durante un largo período de tiempo desde el año 2008, con financiación del Ministerio de Educación y Ciencia [proyecto MTM2007-63140], el Ministerio de Ciencia e Innovación [proyecto MTM2010-20808], y el Ministerio de Economía y Competitividad [proyecto ECO2015-66593-P]. Este artículo ha ido elaborado en el marco del proyecto PID2019-109196GB-I00 de investigación financiado por MCIN/ AEI /10.13039/501100011033. El autor publicó ya en 2015 una versión inicial del artículo en arXiv, ver Niño-Mora (2015), que ya entonces envió a la revista Mathematics of Operations Research. El autor agradece al entonces Editor-en-Jefe de dicha revista, Jim Dai, que interviniese y desbloquease un proceso de revisión tortuoso que se vio indebidamente retrasado por interferencias espurias.

Referencias