Bandido armado múltiple - Multi-armed bandit

Una fila de máquinas tragamonedas en Las Vegas

En teoría de la probabilidad y de aprendizaje automático , el problema bandido múltiples brazos (a veces llamado el K - o N armada perpetrados problema bandido ) es un problema en el que un conjunto limitado fija de recursos debe asignar entre las opciones que compiten (alternativos) de una manera que maximiza su ganancia esperada, cuando las propiedades de cada opción se conocen solo parcialmente en el momento de la asignación, y pueden entenderse mejor a medida que pasa el tiempo o al asignar recursos a la elección. Este es un problema clásico de aprendizaje por refuerzo que ejemplifica el dilema de compensación de exploración-explotación. El nombre proviene de imaginar a un jugador en una fila de máquinas tragamonedas (a veces conocidas como " bandidos de un brazo "), que tiene que decidir qué máquinas jugar, cuántas veces jugar cada máquina y en qué orden jugarlas, y si continuar con la máquina actual o probar una máquina diferente. El problema de los bandidos con múltiples brazos también cae dentro de la amplia categoría de programación estocástica .

En el problema, cada máquina proporciona una recompensa aleatoria a partir de una distribución de probabilidad específica de esa máquina, que no se conoce a priori. El objetivo del jugador es maximizar la suma de recompensas obtenidas mediante una secuencia de tirones de palanca. La compensación crucial que enfrenta el jugador en cada prueba es entre la "explotación" de la máquina que tiene la recompensa más alta esperada y la "exploración" para obtener más información sobre las recompensas esperadas de las otras máquinas. La compensación entre exploración y explotación también se enfrenta en el aprendizaje automático . En la práctica, los bandidos con múltiples armas se han utilizado para modelar problemas como la gestión de proyectos de investigación en una gran organización como una fundación científica o una empresa farmacéutica . En las primeras versiones del problema, el jugador comienza sin un conocimiento inicial sobre las máquinas.

Herbert Robbins en 1952, al darse cuenta de la importancia del problema, construyó estrategias de selección de población convergente en "algunos aspectos del diseño secuencial de experimentos". Un teorema, el índice de Gittins , publicado por primera vez por John C. Gittins , proporciona una política óptima para maximizar la recompensa con descuento esperada.

Motivación empírica

¿Cómo se debe distribuir un presupuesto dado entre estos departamentos de investigación para maximizar los resultados?

El problema de los bandidos de armas múltiples modela un agente que simultáneamente intenta adquirir nuevos conocimientos (llamado "exploración") y optimizar sus decisiones basadas en el conocimiento existente (llamado "explotación"). El agente intenta equilibrar estas tareas en competencia para maximizar su valor total durante el período de tiempo considerado. Hay muchas aplicaciones prácticas del modelo de bandidos, por ejemplo:

• Ensayos clínicos que investiguen los efectos de diferentes tratamientos experimentales mientras se minimizan las pérdidas de pacientes.
• esfuerzos de enrutamiento adaptativo para minimizar los retrasos en una red,
• diseño de cartera financiera

En estos ejemplos prácticos, el problema requiere equilibrar la maximización de la recompensa basada en el conocimiento ya adquirido con el intento de nuevas acciones para aumentar aún más el conocimiento. Esto se conoce como la compensación entre explotación y exploración en el aprendizaje automático .

El modelo también se ha utilizado para controlar la asignación dinámica de recursos a diferentes proyectos, respondiendo a la pregunta de en qué proyecto trabajar, dada la incertidumbre sobre la dificultad y la rentabilidad de cada posibilidad.

Originalmente considerado por los científicos aliados en la Segunda Guerra Mundial , resultó tan intratable que, según Peter Whittle , se propuso que el problema se dejara caer sobre Alemania para que los científicos alemanes también pudieran perder el tiempo en él.

La versión del problema que ahora se analiza comúnmente fue formulada por Herbert Robbins en 1952.

El modelo de bandido de múltiples brazos

El bandido de múltiples brazos (abreviado: bandido o MAB) puede verse como un conjunto de distribuciones reales , cada distribución está asociada con las recompensas entregadas por una de las palancas. Sean los valores medios asociados con estas distribuciones de recompensa. El jugador juega iterativamente una palanca por ronda y observa la recompensa asociada. El objetivo es maximizar la suma de las recompensas recolectadas. El horizonte es el número de rondas que quedan por jugar. El problema de los bandidos es formalmente equivalente a un proceso de decisión de Markov de un solo estado . El arrepentimiento después de las rondas se define como la diferencia esperada entre la suma de recompensas asociada con una estrategia óptima y la suma de las recompensas recolectadas: ${\ Displaystyle B = \ {R_ {1}, \ dots, R_ {K} \}}$${\ Displaystyle K \ in \ mathbb {N} ^ {+}}$${\ Displaystyle \ mu _ {1}, \ dots, \ mu _ {K}}$${\ Displaystyle H}$ ${\ Displaystyle \ rho}$${\ Displaystyle T}$

${\ Displaystyle \ rho = T \ mu ^ {*} - \ sum _ {t = 1} ^ {T} {\ widehat {r}} _ {t}}$,

donde es la recompensa máxima media , y es la recompensa en la ronda t . ${\ Displaystyle \ mu ^ {*}}$${\ Displaystyle \ mu ^ {*} = \ max _ {k} \ {\ mu _ {k} \}}$${\ Displaystyle {\ widehat {r}} _ {t}}$

Una estrategia de arrepentimiento cero es una estrategia cuyo arrepentimiento promedio por ronda tiende a cero con probabilidad 1 cuando el número de rondas jugadas tiende a infinito. De manera intuitiva, se garantiza que las estrategias sin arrepentimiento converjan en una estrategia óptima (no necesariamente única) si se juegan suficientes rondas. ${\ Displaystyle \ rho / T}$

Variaciones

Una formulación común es el bandido binario de múltiples brazos o el bandido de múltiples brazos de Bernoulli, que emite una recompensa de uno con probabilidad y, de lo contrario, una recompensa de cero. ${\ Displaystyle p}$

En otra formulación del bandido de múltiples brazos, cada brazo representa una máquina de Markov independiente. Cada vez que se toca un brazo en particular, el estado de esa máquina avanza a uno nuevo, elegido de acuerdo con las probabilidades de evolución del estado de Markov. Existe una recompensa en función del estado actual de la máquina. En una generalización denominada "problema de los bandidos inquietos", los estados de armas no jugadas también pueden evolucionar con el tiempo. También se ha hablado de sistemas en los que el número de opciones (sobre qué brazo jugar) aumenta con el tiempo.

Los investigadores en ciencias de la computación han estudiado a los bandidos con múltiples brazos bajo las suposiciones del peor de los casos, obteniendo algoritmos para minimizar el arrepentimiento en horizontes de tiempo tanto finitos como infinitos ( asintóticos ) para los pagos de los brazos tanto estocásticos como no estocásticos.

Estrategias de bandidos

Un avance importante fue la construcción de estrategias o políticas de selección de población óptimas (que posean una tasa de convergencia máxima uniforme hacia la población con la media más alta) en el trabajo que se describe a continuación.

Soluciones óptimas

En el artículo "Reglas de asignación adaptativa asintóticamente eficientes", Lai y Robbins (siguiendo los artículos de Robbins y sus colaboradores que se remontan a Robbins en el año 1952) construyeron políticas de selección de población convergente que poseen la tasa de convergencia más rápida (para la población con media más alta) para el caso de que las distribuciones de recompensa de la población sean la familia exponencial de un parámetro. Luego, en Katehakis y Robbins se dieron simplificaciones de la política y la principal prueba para el caso de poblaciones normales con variaciones conocidas. El siguiente avance notable lo obtuvieron Burnetas y Katehakis en el artículo "Políticas adaptativas óptimas para problemas de asignación secuencial", donde se construyeron políticas basadas en índices con tasa de convergencia máxima uniforme, bajo condiciones más generales que incluyen el caso en el que las distribuciones de resultados de cada población depende de un vector de parámetros desconocidos. Burnetas y Katehakis (1996) también proporcionaron una solución explícita para el caso importante en el que las distribuciones de resultados siguen distribuciones discretas, univariadas arbitrarias (es decir, no paramétricas).

Más adelante, en "Políticas de adaptación óptimas para los procesos de decisión de Markov", Burnetas y Katehakis estudiaron el modelo mucho más amplio de los procesos de decisión de Markov con información parcial, donde la ley de transición y / o las recompensas esperadas de un período pueden depender de parámetros desconocidos. En este trabajo, la forma explícita para una clase de políticas adaptativas que poseen propiedades de tasa de convergencia máxima uniforme para la recompensa total esperada del horizonte finito, se construyó bajo supuestos suficientes de espacios finitos de acción estatal y la irreductibilidad de la ley de transición. Una característica principal de estas políticas es que la elección de acciones, en cada estado y período de tiempo, se basa en índices que son inflaciones del lado derecho de las ecuaciones de optimización de recompensa promedio estimadas. Estas inflaciones se han denominado recientemente el enfoque optimista en el trabajo de Tewari y Bartlett, Ortner Filippi, Cappé y Garivier, y Honda y Takemura.

Cuando se utilizan soluciones óptimas para tareas de bandidos con múltiples brazos para derivar el valor de las elecciones de los animales, la actividad de las neuronas en la amígdala y el estriado ventral codifica los valores derivados de estas políticas, y se puede utilizar para decodificar cuándo los animales hacen exploraciones versus elecciones explotadoras. Además, las políticas óptimas predicen mejor el comportamiento de elección de los animales que las estrategias alternativas (descritas a continuación). Esto sugiere que las soluciones óptimas para los problemas de los bandidos con múltiples brazos son biológicamente plausibles, a pesar de ser computacionalmente exigentes.

• UCBC (límites históricos superiores de confianza con clústeres): el algoritmo adapta UCB a un nuevo entorno de modo que pueda incorporar información histórica y de clústeres. El algoritmo incorpora las observaciones históricas utilizando tanto en el cálculo de las recompensas medias observadas como el término de incertidumbre. El algoritmo incorpora la información de agrupamiento jugando en dos niveles: primero seleccionando un grupo usando una estrategia similar a UCB en cada paso de tiempo, y luego eligiendo un brazo dentro del grupo, nuevamente usando una estrategia similar a UCB.

Soluciones aproximadas

Existen muchas estrategias que proporcionan una solución aproximada al problema de los bandidos y se pueden clasificar en las cuatro categorías generales que se detallan a continuación.

Estrategias semi uniformes

Las estrategias semi-uniformes fueron las primeras (y más simples) que se descubrieron para resolver aproximadamente el problema de los bandidos. Todas esas estrategias tienen en común un comportamiento codicioso en el que siempre se tira de la mejor palanca (basada en observaciones anteriores), excepto cuando se toma una acción (uniformemente) aleatoria.

• Estrategia de épsilon codicioso : se selecciona la mejor palanca para una proporción de las pruebas, y una palanca se selecciona al azar (con probabilidad uniforme) para una proporción . Un valor de parámetro típico podría ser , pero esto puede variar ampliamente según las circunstancias y predilecciones.${\ Displaystyle 1- \ epsilon}$${\ Displaystyle \ epsilon}$${\ Displaystyle \ epsilon = 0.1}$
• Primera estrategia de Epsilon : una fase de exploración pura es seguida de una fase de explotación pura. Para los ensayos en total, la fase de exploración ocupa los ensayos y la fase de explotación los ensayos. Durante la fase de exploración, se selecciona una palanca al azar (con probabilidad uniforme); durante la fase de explotación, siempre se selecciona la mejor palanca.${\ Displaystyle N}$${\ Displaystyle \ epsilon N}$${\ Displaystyle (1- \ epsilon) N}$
• Estrategia de disminución de épsilon: similar a la estrategia de épsilon-codicioso, excepto que el valor de disminuye a medida que avanza el experimento, lo que resulta en un comportamiento altamente exploratorio al principio y un comportamiento altamente explotador al final.${\ Displaystyle \ epsilon}$
• Estrategia adaptativa de épsilon-codicioso basada en diferencias de valor (VDBE) : similar a la estrategia de disminución de épsilon, excepto que épsilon se reduce en función del progreso del aprendizaje en lugar del ajuste manual (Tokic, 2010). Las altas fluctuaciones en las estimaciones de valor conducen a una alta épsilon (alta exploración, baja explotación); fluctuaciones bajas a épsilon bajo (exploración baja, explotación alta). Se pueden lograr mejoras adicionales mediante una selección de acciones ponderadas por softmax en caso de acciones exploratorias (Tokic & Palm, 2011).
• Estrategia adaptativa épsilon-codiciosa basada en conjuntos bayesianos (Epsilon-BMC) : Una estrategia de adaptación épsilon adaptativa para el aprendizaje por refuerzo similar a VBDE, con garantías de convergencia monótona. En este marco, el parámetro épsilon se ve como la expectativa de una distribución posterior que pondera un agente codicioso (que confía plenamente en la recompensa aprendida) y un agente de aprendizaje uniforme (que desconfía de la recompensa aprendida). Este posterior se aproxima utilizando una distribución Beta adecuada bajo el supuesto de normalidad de las recompensas observadas. Para abordar el posible riesgo de disminuir épsilon demasiado rápido, la incertidumbre en la varianza de la recompensa aprendida también se modela y actualiza utilizando un modelo de gamma normal. (Gimelfarb et al., 2019).
• Estrategia contextual-épsilon-codiciosa : similar a la estrategia épsilon-codiciosa, excepto que el valor de se calcula con respecto a la situación en los procesos experimentales, lo que permite que el algoritmo sea sensible al contexto. Se basa en la exploración / explotación dinámica y puede equilibrar adaptativamente los dos aspectos al decidir qué situación es más relevante para la exploración o explotación, lo que resulta en un comportamiento altamente explorador cuando la situación no es crítica y un comportamiento altamente explotador en una situación crítica.${\ Displaystyle \ epsilon}$

Estrategias de coincidencia de probabilidad

Las estrategias de emparejamiento de probabilidades reflejan la idea de que el número de tirones de una palanca determinada debe coincidir con su probabilidad real de ser la palanca óptima. Las estrategias de emparejamiento de probabilidades también se conocen como muestreo de Thompson o Bandidos Bayesianos, y son sorprendentemente fáciles de implementar si puede tomar muestras desde el posterior para el valor medio de cada alternativa.

Las estrategias de comparación de probabilidades también admiten soluciones a los llamados problemas de bandidos contextuales.

Estrategias de precios

Las estrategias de precios establecen un precio para cada palanca. Por ejemplo, como se ilustra con el algoritmo POKER, el precio puede ser la suma de la recompensa esperada más una estimación de las recompensas futuras adicionales que se obtendrán a través del conocimiento adicional. Siempre se tira de la palanca de mayor precio.

Estrategias con limitaciones éticas

• Behavior Constrained Thompson Sampling (BCTS) : En este artículo, los autores detallan un agente en línea novedoso que aprende un conjunto de restricciones de comportamiento mediante la observación y utiliza estas restricciones aprendidas como guía al tomar decisiones en un entorno en línea mientras sigue siendo reactivo para recompensar la retroalimentación. Para definir a este agente, la solución fue adoptar una extensión novedosa del entorno clásico de bandidos de múltiples brazos contextuales y proporcionar un nuevo algoritmo llamado Behavior Constrained Thompson Sampling (BCTS) que permite el aprendizaje en línea mientras obedece restricciones exógenas. El agente aprende una política restringida que implementa las restricciones de comportamiento observadas demostradas por un agente docente, y luego usa esta política restringida para guiar la exploración y explotación en línea basada en recompensas.

Estas estrategias minimizan la asignación de cualquier paciente a un brazo inferior ( "deber del médico" ). En un caso típico, minimizan los éxitos esperados perdidos (ESL), es decir, el número esperado de resultados favorables que se pasaron por alto debido a la asignación a un brazo más tarde resultó ser inferior. Otra versión minimiza los recursos desperdiciados en cualquier tratamiento inferior y más caro.

Bandido contextual

Una versión particularmente útil del bandido de múltiples brazos es el problema contextual del bandido de múltiples brazos. En este problema, en cada iteración un agente tiene que elegir entre brazos. Antes de tomar la decisión, el agente ve un vector de características d-dimensional (vector de contexto), asociado con la iteración actual. El alumno usa estos vectores de contexto junto con las recompensas de los brazos jugados en el pasado para elegir el brazo que jugará en la iteración actual. Con el tiempo, el objetivo del alumno es recopilar suficiente información sobre cómo los vectores de contexto y las recompensas se relacionan entre sí, de modo que pueda predecir el siguiente mejor brazo para jugar al observar los vectores de características.

Soluciones aproximadas para bandido contextual

Existen muchas estrategias que brindan una solución aproximada al problema de los bandidos contextuales y se pueden clasificar en dos categorías amplias que se detallan a continuación.

Bandidos lineales en línea

• LinUCB (Bound confianza superior) algoritmo : Los autores suponen una dependencia lineal entre la recompensa esperada de una acción y su contexto y modelar el espacio de representación usando un conjunto de predictores lineales.
• Algoritmo LinRel (aprendizaje de refuerzo asociativo lineal) : similar a LinUCB, pero utiliza la descomposición de valores singulares en lugar de la regresión de Ridge para obtener una estimación de la confianza.
• HLINUCBC (LINUCB histórico con agrupaciones) : propuesto en el documento, amplía la idea de LinUCB con información histórica y agrupada.

Bandidos no lineales en línea

• Algoritmo UCBogram : Las funciones de recompensa no lineales se estiman utilizando un estimador constante por partes llamado regresograma en regresión no paramétrica . Luego, se emplea UCB en cada pieza constante. Los refinamientos sucesivos de la partición del espacio de contexto se programan o se eligen de forma adaptativa.
• Algoritmos lineales generalizados : la distribución de recompensas sigue un modelo lineal generalizado, una extensión de los bandidos lineales.
• Algoritmo NeuralBandit : en este algoritmo se entrenan varias redes neuronales para modelar el valor de las recompensas conociendo el contexto, y utiliza un enfoque de múltiples expertos para elegir en línea los parámetros de perceptrones multicapa.
• Algoritmo KernelUCB : una versión kernelizada no lineal de linearUCB, con implementación eficiente y análisis de tiempo finito.
• Bandit Bosque algoritmo : un bosque al azar se construyó y analizó WRT el bosque aleatorio construido conocer la distribución conjunta de los contextos y las recompensas.
• Algoritmo basado en Oracle : el algoritmo reduce el problema de los bandidos contextuales a una serie de problemas de aprendizaje supervisados ​​y no se basa en la suposición de realizabilidad típica de la función de recompensa.

Bandido contextual restringido

• Bandidos atentos al contexto o Bandidos contextuales con contexto restringido : Los autores consideran una formulación novedosa del modelo de bandidos de múltiples brazos, que se denomina bandido contextual con contexto restringido, donde el alumno solo puede acceder a un número limitado de características en cada iteración. Esta novedosa formulación está motivada por diferentes problemas en línea que surgen en ensayos clínicos, sistemas de recomendación y modelado de atención. Aquí, adaptan el algoritmo estándar de bandidos de múltiples brazos conocido como Thompson Sampling para aprovechar la configuración de contexto restringido y proponen dos algoritmos novedosos, llamados Thompson Sampling with Restricted Context (TSRC) y Windows Thompson Sampling with Restricted Context (WTSRC). ), para el manejo de entornos estacionarios y no estacionarios, respectivamente.

En la práctica, generalmente existe un costo asociado con el recurso consumido por cada acción y el costo total está limitado por un presupuesto en muchas aplicaciones como el crowdsourcing y los ensayos clínicos. El bandido contextual restringido (CCB) es un modelo que considera las limitaciones de tiempo y de presupuesto en un entorno de bandidos con múltiples brazos. A. Badanidiyuru y col. Primero estudió a los bandidos contextuales con restricciones presupuestarias, también conocidos como Resourceful Contextual Bandits, y muestra que se puede arrepentir. Sin embargo, su trabajo se centra en un conjunto finito de políticas y el algoritmo es computacionalmente ineficiente. ${\ Displaystyle O ({\ sqrt {T}})}$

Marco de UCB-ALP para bandidos contextuales restringidos

Se propone un algoritmo simple con arrepentimiento logarítmico en:

• Algoritmo UCB-ALP : el marco de UCB-ALP se muestra en la figura de la derecha. UCB-ALP es un algoritmo simple que combina el método UCB con un algoritmo de programación lineal adaptativa (ALP) y se puede implementar fácilmente en sistemas prácticos. Es el primer trabajo que muestra cómo lograr arrepentimiento logarítmico en bandidos contextuales restringidos. Aunque está dedicado a un caso especial con restricción de presupuesto único y costo fijo, los resultados arrojan luz sobre el diseño y análisis de algoritmos para problemas CCB más generales.

Bandido adversario

Otra variante del problema de los bandidos con múltiples brazos se llama bandido adversario, introducido por primera vez por Auer y Cesa-Bianchi (1998). En esta variante, en cada iteración, un agente elige un brazo y un adversario elige simultáneamente la estructura de pago para cada brazo. Esta es una de las generalizaciones más fuertes del problema de los bandidos, ya que elimina todas las suposiciones de la distribución y una solución al problema de los bandidos adversarios es una solución generalizada para los problemas más específicos de los bandidos.

Ejemplo: dilema del prisionero iterado

Un ejemplo que se suele considerar para los bandidos adversarios es el dilema del prisionero repetido . En este ejemplo, cada adversario tiene dos brazos para tirar. Pueden negar o confesar. Los algoritmos estándar de bandidos estocásticos no funcionan muy bien con estas iteraciones. Por ejemplo, si el oponente coopera en las primeras 100 rondas, falla en las siguientes 200, luego coopera en las siguientes 300, etc., entonces algoritmos como UCB no podrán reaccionar muy rápidamente a estos cambios. Esto se debe a que, después de cierto punto, rara vez se jalan los brazos subóptimos para limitar la exploración y centrarse en la explotación. Cuando el entorno cambia, el algoritmo no puede adaptarse o ni siquiera puede detectar el cambio.

Soluciones aproximadas

Exp3

Algoritmo

 Parameters: Real ${\displaystyle \gamma \in (0,1]}$
 
 Initialisation: ${\displaystyle \omega _{i}(1)=1}$ for ${\displaystyle i=1,...,K}$
 
 For each t = 1, 2, ..., T
  1. Set ${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$       ${\displaystyle i=1,...,K}$
  2. Draw ${\displaystyle i_{t}}$ randomly according to the probabilities ${\displaystyle p_{1}(t),...,p_{K}(t)}$
  3. Receive reward ${\displaystyle x_{i_{t}}(t)\in [0,1]}$
  4. For ${\displaystyle j=1,...,K}$ set:
      ${\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}}$
 
      ${\displaystyle \omega _{j}(t+1)=\omega _{j}(t)exp(\gamma {\hat {x}}_{j}(t)/K)}$

Explicación

Exp3 elige un brazo al azar con probabilidad , prefiere brazos con pesos más altos (explotación), elige con probabilidad γ para explorar uniformemente al azar. Después de recibir las recompensas, se actualizan los pesos. El crecimiento exponencial aumenta significativamente el peso de los brazos buenos. ${\ Displaystyle (1- \ gamma)}$

Análisis de arrepentimiento

El arrepentimiento (externo) del algoritmo Exp3 es como mucho ${\ Displaystyle O ({\ sqrt {KTlog (K)}})}$

Siga el algoritmo de líder perturbado (FPL)

Algoritmo

 Parameters: Real ${\displaystyle \eta }$
 
 Initialisation: ${\displaystyle \forall i:R_{i}(1)=0}$
 
 For each t = 1,2,...,T
  1. For each arm generate a random noise from an exponential distribution ${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$
  2. Pull arm ${\displaystyle I(t)}$: ${\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}$
     Add noise to each arm and pull the one with the highest value
  3. Update value: ${\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}$
     The rest remains the same

Explicación

Seguimos el brazo que creemos que tiene el mejor rendimiento hasta ahora y le agregamos ruido exponencial para proporcionar exploración.

Exp3 vs FPL

Bandido de armas infinitas

En la especificación original y en las variantes anteriores, el problema del bandido se especifica con un número de brazos discreto y finito, a menudo indicado por la variable . En el caso de las armas infinitas, introducido por Agrawal (1995), las "armas" son una variable continua en dimensiones. ${\ Displaystyle K}$${\ Displaystyle K}$

Bandido no estacionario

Garivier y Moulines obtienen algunos de los primeros resultados con respecto a los problemas de los bandidos donde el modelo subyacente puede cambiar durante el juego. Se presentaron varios algoritmos para tratar este caso, incluidos UCB con descuento y UCB de ventana deslizante.

Otro trabajo de Burtini et al. introduce un método de muestreo de Thompson de mínimos cuadrados ponderados (WLS-TS), que resulta beneficioso tanto en los casos no estacionarios conocidos como en los desconocidos. En el caso no estacionario conocido, los autores producen una solución alternativa, una variante de UCB denominada Límite de confianza superior ajustado (A-UCB) que asume un modelo estocástico y proporciona límites superiores del arrepentimiento.

Otras variantes

En los últimos años se han propuesto muchas variantes del problema.

Bandido en duelo

La variante del bandido en duelo fue introducida por Yue et al. (2012) para modelar la compensación entre exploración y explotación para obtener una retroalimentación relativa. En esta variante, el jugador puede tirar de dos palancas al mismo tiempo, pero solo obtiene una retroalimentación binaria que indica qué palanca proporcionó la mejor recompensa. La dificultad de este problema se debe al hecho de que el jugador no tiene forma de observar directamente la recompensa de sus acciones. Los primeros algoritmos para este problema son InterleaveFiltering, Beat-The-Mean. La retroalimentación relativa de los bandidos en duelo también puede conducir a paradojas en la votación . Una solución es tomar como referencia al ganador de Condorcet .

Más recientemente, los investigadores han generalizado algoritmos desde el MAB tradicional hasta los bandidos en duelo: límites de confianza superior relativos (RUCB), pesaje exponencial relativo (REX3), límites de confianza de Copeland (CCB), divergencia empírica mínima relativa (RMED) y muestreo doble de Thompson (DTS). ).

Bandido colaborativo

Los bandidos de filtrado colaborativo (es decir, COFIBA) fueron presentados por Li y Karatzoglou y Gentile (SIGIR 2016), donde el filtrado colaborativo clásico y los métodos de filtrado basados ​​en contenido intentan aprender un modelo de recomendación estático dados los datos de entrenamiento. Estos enfoques están lejos de ser ideales en dominios de recomendación altamente dinámicos, como la recomendación de noticias y la publicidad computacional, donde el conjunto de elementos y usuarios es muy fluido. En este trabajo, investigan una técnica de agrupación adaptativa para la recomendación de contenido basada en estrategias de exploración-explotación en entornos de bandidos contextuales con múltiples brazos. Su algoritmo (COFIBA, pronunciado como "Coffee Bar") tiene en cuenta los efectos colaborativos que surgen por la interacción de los usuarios con los ítems, agrupando dinámicamente a los usuarios en función de los ítems considerados y, al mismo tiempo, agrupando ítems basado en la similitud de las agrupaciones inducidas sobre los usuarios. El algoritmo resultante aprovecha así los patrones de preferencia en los datos de una manera similar a los métodos de filtrado colaborativo. Proporcionan un análisis empírico sobre conjuntos de datos de tamaño medio del mundo real, que muestran la escalabilidad y un mayor rendimiento de predicción (medido por la tasa de clics) sobre los métodos de vanguardia para agrupar bandidos. También proporcionan un análisis de arrepentimiento dentro de una configuración de ruido estocástico lineal estándar.

Bandido combinatorio

El problema de Combinatorial Multiarmed Bandit (CMAB) surge cuando en lugar de una sola variable discreta para elegir, un agente necesita elegir valores para un conjunto de variables. Suponiendo que cada variable es discreta, el número de opciones posibles por iteración es exponencial en el número de variables. Se han estudiado varias configuraciones CMAB en la literatura, desde configuraciones donde las variables son binarias hasta configuraciones más generales donde cada variable puede tomar un conjunto arbitrario de valores.

Ver también

• Índice de Gittins  : una poderosa estrategia general para analizar los problemas de los bandidos.
• Algoritmo codicioso
• Parada óptima
• Teoría de la búsqueda
• Programación estocástica

Referencias

Otras lecturas

Scholia tiene un perfil de tema para Multi-Arms Bandit .

• Guha, S .; Munagala, K .; Shi, P. (2010), "Algoritmos de aproximación para problemas de bandidos inquietos", Journal of the ACM , 58 : 1–50, arXiv : 0711.3861 , doi : 10.1145 / 1870103.1870106 , S2CID  1654066
• Dayanik, S .; Powell, W .; Yamazaki, K. (2008), "Políticas de índices para problemas de bandidos descontados con restricciones de disponibilidad", Advances in Applied Probability , 40 (2): 377–400, doi : 10.1239 / aap / 1214950209.
• Powell, Warren B. (2007), "Capítulo 10", Programación dinámica aproximada: Resolviendo las maldiciones de la dimensionalidad , Nueva York: John Wiley and Sons, ISBN 978-0-470-17155-4.
• Robbins, H. (1952), "Algunos aspectos del diseño secuencial de experimentos", Boletín de la American Mathematical Society , 58 (5): 527–535, doi : 10.1090 / S0002-9904-1952-09620-8.
• Sutton, Richard; Barto, Andrew (1998), Aprendizaje por refuerzo , MIT Press, ISBN 978-0-262-19398-6, archivado desde el original el 11 de diciembre de 2013.

• Allesiardo, Robin (2014), "A Neural Networks Committee for the Contextual Bandit Problem", Neural Information Processing - 21st International Conference, ICONIP 2014, Malaisia, noviembre 03-06,2014, Proceedings , Lecture Notes in Computer Science, 8834 , Springer , págs. 374–381, arXiv : 1409.8191 , doi : 10.1007 / 978-3-319-12637-1_47 , ISBN 978-3-319-12636-4, S2CID  14155718.

• Weber, Richard (1992), "Sobre el índice de Gittins para bandidos con varios brazos", Annals of Applied Probability , 2 (4): 1024–1033, doi : 10.1214 / aoap / 1177005588 , JSTOR  2959678.
• Katehakis, M .; C. Derman (1986), "Computación de reglas de asignación secuencial óptimas en ensayos clínicos", Procedimientos estadísticos adaptativos y temas relacionados , Institute of Mathematical Statistics Lecture Notes - Monograph Series, 8 , págs. 29–39, doi : 10.1214 / lnms / 1215540286 , ISBN 978-0-940600-09-6, JSTOR  4355518 .
• Katehakis, M .; AF Veinott, Jr. (1987), "El problema de los bandidos con múltiples brazos: descomposición y cálculo" , Mathematics of Operations Research , 12 (2): 262-268, doi : 10.1287 / moor.12.2.262 , JSTOR  3689689 , S2CID  656323 .

enlaces externos

• MABWiser , implementación de Python de código abierto de estrategias bandit que admite políticas contextuales sin contexto, paramétricas y no paramétricas con capacidad de simulación y paralelización incorporada.
• PyMaBandits , implementación de código abierto de estrategias bandit en Python y Matlab.
• Paquete R contextual y de código abierto que facilita la simulación y evaluación de políticas de bandidos de armas múltiples, tanto contextuales como contextuales.
• bandit.sourceforge.net Proyecto Bandit , implementación de código abierto de estrategias bandit.
• Banditlib , implementación de código abierto de estrategias bandit en C ++.
• Leslie Pack Kaelbling y Michael L. Littman (1996). Explotación versus exploración: el caso de un solo estado .
• Tutorial: Introducción a Bandits: Algoritmos y Teoría. Part1 . Part2 .
• El problema del restaurante de Feynman , un ejemplo clásico (con una respuesta conocida) de la compensación entre explotación y exploración.
• Algoritmos Bandit frente a pruebas AB .
• S. Bubeck y N. Cesa-Bianchi Una encuesta sobre bandidos .
• Una encuesta sobre bandidos contextuales con varios brazos , una encuesta / tutorial para bandidos contextuales.
• Publicación de blog sobre estrategias de bandidos con múltiples brazos, con código Python .
• Tramas animadas e interactivas que ilustran estrategias de equilibrio de exploración / explotación de Epsilon-codicioso, muestreo de Thompson y Upper Confidence Bound.