Bandido de múltiples brazos

Problema de recursos en el aprendizaje automático

Una fila de máquinas tragamonedas en Las Vegas

En teoría de probabilidad y aprendizaje automático , el problema del bandido de múltiples brazos (a veces llamado el problema del bandido de K - ^[1] o N -brazos ^[2] ) es un problema en el que un tomador de decisiones selecciona iterativamente una de múltiples opciones fijas (es decir, brazos o acciones) cuando las propiedades de cada opción solo se conocen parcialmente en el momento de la asignación, y pueden entenderse mejor a medida que pasa el tiempo. Un aspecto fundamental de los problemas de bandido es que la elección de un brazo no afecta las propiedades del brazo o de otros brazos. ^[3]

Las instancias del problema de la máquina tragamonedas multiarmado incluyen la tarea de asignar iterativamente un conjunto fijo y limitado de recursos entre opciones competitivas (alternativas) de una manera que minimice el arrepentimiento . ^{[4] [5]} Una configuración alternativa notable para el problema de la máquina tragamonedas multiarmado incluye el problema de "identificación del mejor brazo", donde el objetivo es, en cambio, identificar la mejor opción al final de un número finito de rondas. ^[6]

El problema de las máquinas tragamonedas multibrazo es un problema clásico de aprendizaje por refuerzo que ejemplifica el dilema de la disyuntiva entre exploración y explotación . A diferencia del aprendizaje por refuerzo general, las acciones seleccionadas en los problemas de las máquinas tragamonedas no afectan la distribución de recompensas de los brazos. El nombre proviene de imaginar a un jugador en una fila de máquinas tragamonedas (a veces conocidas como "máquinas tragamonedas de un solo brazo"), que tiene que decidir en qué máquinas jugar, cuántas veces jugar en cada máquina y en qué orden jugarlas, y si continuar con la máquina actual o probar con una máquina diferente. ^[7] El problema de las máquinas tragamonedas multibrazo también cae dentro de la amplia categoría de programación estocástica .

En el problema, cada máquina proporciona una recompensa aleatoria de una distribución de probabilidad específica para esa máquina, que no se conoce a priori . El objetivo del jugador es maximizar la suma de las recompensas obtenidas a través de una secuencia de tirones de palanca. ^{[4] [5]} La disyuntiva crucial que enfrenta el jugador en cada prueba es entre la "explotación" de la máquina que tiene la mayor recompensa esperada y la "exploración" para obtener más información sobre las recompensas esperadas de las otras máquinas. La disyuntiva entre exploración y explotación también se enfrenta en el aprendizaje automático . En la práctica, se han utilizado bandidos multiarmados 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 . ^{[4] [5]} En las primeras versiones del problema, el jugador comienza sin ningún conocimiento inicial sobre las máquinas.

En 1952, Herbert Robbins , 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". ^[8] Un teorema, el índice de Gittins , publicado por primera vez por John C. Gittins , proporciona una política óptima para maximizar la recompensa descontada esperada. ^[9]

Motivación empírica

¿Cómo debe distribuirse un presupuesto determinado entre estos departamentos de investigación para maximizar los resultados?

El problema del bandido multiarmado modela un agente que intenta simultáneamente adquirir nuevos conocimientos (denominado "exploración") y optimizar sus decisiones en función de los conocimientos existentes (denominado "explotación"). El agente intenta equilibrar estas tareas en competencia para maximizar su valor total durante el período de tiempo considerado. Existen muchas aplicaciones prácticas del modelo del bandido, por ejemplo:

• ensayos clínicos que investigan los efectos de diferentes tratamientos experimentales minimizando las pérdidas de pacientes, ^{[4] [5] [10] [11]}
• esfuerzos de enrutamiento adaptativo para minimizar los retrasos en una red,
• Diseño de cartera financiera ^{[12] [13]}

En estos ejemplos prácticos, el problema requiere equilibrar la maximización de la recompensa en función del conocimiento ya adquirido con el intento de nuevas acciones para aumentar aún más el conocimiento. Esto se conoce como el equilibrio 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 los resultados de cada posibilidad. ^[14]

Originalmente considerado por los científicos aliados en la Segunda Guerra Mundial , resultó tan intratable que, según Peter Whittle , se propuso dejar el problema en manos de Alemania para que los científicos alemanes también pudieran perder el tiempo en él. ^[15]

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

El modelo del bandido multibrazo

El bandido multibrazo (abreviado: bandido o MAB) puede verse como un conjunto de distribuciones reales , cada una de las cuales 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 con 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 del bandido es formalmente equivalente a un proceso de decisión de Markov de un 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. ^[16] Intuitivamente, se garantiza que las estrategias de arrepentimiento cero convergerán a una estrategia óptima (no necesariamente única) si se juegan suficientes rondas. ${\displaystyle \rho /T}$

Variaciones

Una formulación común es la máquina tragamonedas binaria o máquina tragamonedas de Bernoulli, que otorga una recompensa de uno con probabilidad , y en caso contrario una recompensa de cero. ${\displaystyle p}$

Otra formulación del bandido de múltiples brazos es que cada brazo representa una máquina de Markov independiente. Cada vez que se juega con 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 que depende del estado actual de la máquina. En una generalización llamada el "problema del bandido inquieto", los estados de los brazos que no se juegan también pueden evolucionar con el tiempo. ^[17] También se ha discutido sobre sistemas en los que el número de opciones (sobre qué brazo jugar) aumenta con el tiempo. ^[18]

Los investigadores en ciencias de la computación han estudiado bandidos multiarmados bajo supuestos de peor caso, obteniendo algoritmos para minimizar el arrepentimiento en horizontes de tiempo finitos e infinitos ( asintóticos ) para pagos de brazos estocásticos ^[1] y no estocásticos ^[19] .

La mejor identificación del brazo

Una variación importante del problema clásico de minimización del arrepentimiento en las máquinas tragamonedas multiarmadas es el de identificación del mejor brazo (BAI) ^[20] , también conocido como exploración pura . Este problema es crucial en diversas aplicaciones, incluidos los ensayos clínicos, el enrutamiento adaptativo, los sistemas de recomendación y las pruebas A/B.

En BAI, el objetivo es identificar el brazo que ofrece la recompensa esperada más alta. Un algoritmo en este contexto se caracteriza por una regla de muestreo , una regla de decisión y una regla de detención , que se describen de la siguiente manera:

1. Regla de muestreo : es una secuencia de acciones en cada paso de tiempo. ${\displaystyle (a_{t})_{t\geq 1}}$
2. Regla de detención : es un tiempo de detención (aleatorio) que sugiere cuándo dejar de recolectar muestras. ${\displaystyle \tau }$
3. Regla de decisión : es una suposición sobre el mejor brazo en función de los datos recopilados hasta el momento. ${\displaystyle {\hat {a}}_{\tau }}$ ${\displaystyle \tau }$

Hay dos configuraciones predominantes en BAI:

Configuración de presupuesto fijo: dado un horizonte temporal , el objetivo es identificar el brazo con la mayor recompensa esperada minimizando la probabilidad de error . ${\displaystyle T\geq 1}$ ${\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}$ ${\displaystyle \delta }$

Configuración de confianza fija: dado un nivel de confianza , el objetivo es identificar el brazo con la mayor recompensa esperada con la menor cantidad posible de ensayos y con probabilidad de error . ${\displaystyle \delta \in (0,1)}$ ${\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}$ ${\displaystyle \mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta }$

Por ejemplo, utilizando una regla de decisión , podríamos usar donde es la máquina n.° 1 (puede usar una variable diferente respectivamente) y es la cantidad cada vez que se intenta tirar de la palanca, donde , identifica como la suma de cada intento , (...) según sea necesario, y a partir de allí puede obtener una proporción, suma o media como probabilidad cuantitativa y muestrear su formulación para cada ranura. ${\displaystyle m_{1}}$ ${\displaystyle m}$ ${\displaystyle 1}$ ${\displaystyle \int \sum m_{1},m_{2},(...)=M}$ ${\displaystyle M}$ ${\displaystyle m_{1}+m_{2}}$

También puedes hacer donde igual a cada una de las ranuras de una máquina única, es la cantidad cada vez que se activa la palanca, es la suma de , sería la cantidad total disponible en tu posesión, y como el máximo que estás dispuesto a gastar. Es posible expresar esta construcción utilizando una combinación de múltiples formulaciones algebraicas, como se mencionó anteriormente, donde puedes limitar con para, o en el tiempo, etc. ${\displaystyle \int \sum _{k\propto _{i}}^{N}}$ ${\displaystyle m1+m2}$ ${\displaystyle x,y}$ ${\displaystyle N}$ ${\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle T}$

Estrategias de bandidos

Un avance importante fue la construcción de estrategias o políticas de selección de población óptimas (que poseen una tasa de convergencia uniformemente máxima 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 "Asymptotically efficient adaptive mapping rules", Lai y Robbins ^[21] (siguiendo los artículos de Robbins y sus colaboradores que se remontan a Robbins en el año 1952) construyeron políticas convergentes de selección de población que poseen la tasa más rápida de convergencia (a la población con la media más alta) para el caso en que las distribuciones de recompensa de la población son la familia exponencial de un parámetro. Luego, en Katehakis y Robbins ^[22] se dieron simplificaciones de la política y la prueba principal para el caso de poblaciones normales con varianzas conocidas. El siguiente avance notable fue obtenido por Burnetas y Katehakis en el artículo "Optimal adaptive policies for sequential mapping problems", ^[23] donde se construyeron políticas basadas en índices con una 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 dependen 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 univariadas discretas arbitrarias (es decir, no paramétricas).

Más adelante, en "Políticas adaptativas óptimas para los procesos de decisión de Markov" ^[24], Burnetas y Katehakis estudiaron el modelo mucho más grande de los procesos de decisión de Markov bajo información parcial, donde la ley de transición y/o las recompensas esperadas en un período pueden depender de parámetros desconocidos. En este trabajo, los autores construyeron una forma explícita para una clase de políticas adaptativas con propiedades de tasa de convergencia máxima uniforme para la recompensa total esperada en el horizonte finito bajo supuestos suficientes de espacios de estado-acción finitos e irreducibilidad 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 optimalidad de recompensa promedio estimadas. Estas inflaciones se han llamado recientemente el enfoque optimista en el trabajo de Tewari y Bartlett, ^[25] Ortner ^[26] Filippi, Cappé y Garivier, ^[27] y Honda y Takemura. ^[28]

Para los bandidos multibrazo de Bernoulli, Pilarski et al. ^[29] estudiaron métodos computacionales para derivar soluciones completamente óptimas (no solo asintóticamente) usando programación dinámica en el artículo "Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge" ^[29] mediante esquemas de indexación, tablas de búsqueda y otras técnicas, este trabajo proporcionó soluciones óptimas prácticamente aplicables para los bandidos de Bernoulli siempre que los horizontes temporales y la cantidad de brazos no se volvieran excesivamente grandes. Pilarski et al. ^[30] luego ampliaron este trabajo en "Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI" ^[30] para crear un método para determinar la política óptima para los bandidos de Bernoulli cuando las recompensas pueden no revelarse inmediatamente después de una decisión y pueden demorarse. Este método se basa en el cálculo de valores esperados de resultados de recompensa que aún no se han revelado y en la actualización de probabilidades posteriores cuando se revelan las recompensas.

Cuando se utilizan soluciones óptimas para tareas de bandidos de múltiples brazos ^[31] para derivar el valor de las elecciones de los animales, la actividad de las neuronas en la amígdala y el cuerpo estriado ventral codifica los valores derivados de estas políticas, y se puede utilizar para decodificar cuándo los animales toman decisiones exploratorias o 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 bandidos de múltiples brazos son biológicamente plausibles, a pesar de ser computacionalmente exigentes. ^[32]

Soluciones aproximadas

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

Estrategias semi-uniformes

Las estrategias semiuniformes fueron las primeras (y más simples) estrategias descubiertas para resolver aproximadamente el problema del bandido. Todas esas estrategias tienen en común un comportamiento codicioso en el que siempre se tira de la mejor palanca (según las observaciones previas), excepto cuando se realiza una acción (uniformemente) aleatoria.

• Estrategia épsilon-codiciosa : ^[33] Se selecciona la mejor palanca para una proporción de los ensayos, y se selecciona una palanca al azar (con probabilidad uniforme) para una proporción . Un valor de parámetro típico podría ser , pero esto puede variar ampliamente dependiendo de las circunstancias y las predilecciones. ${\displaystyle 1-\epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon =0.1}$
• Estrategia de épsilon-first ^{[ cita requerida ]} : una fase de exploración pura es seguida por 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 ^{[ cita requerida ]} : similar a la estrategia épsilon-codiciosa, excepto que el valor de disminuye a medida que avanza el experimento, lo que resulta en un comportamiento altamente exploratorio al inicio y un comportamiento altamente explotador al final. ${\displaystyle \epsilon }$
• Estrategia adaptativa épsilon-greedy basada en diferencias de valores (VDBE) : similar a la estrategia de disminución de épsilon, excepto que épsilon se reduce en función del progreso del aprendizaje en lugar de un ajuste manual (Tokic, 2010). ^[34] Las fluctuaciones altas en las estimaciones de valores conducen a un épsilon alto (exploración alta, explotación baja); las fluctuaciones bajas a un épsilon bajo (exploración baja, explotación alta). Se pueden lograr mejoras adicionales mediante una selección de acciones ponderadas por softmax en el caso de acciones exploratorias (Tokic y Palm, 2011). ^[35]
• Estrategia adaptativa épsilon-codiciosa basada en conjuntos bayesianos (Epsilon-BMC) : una estrategia adaptativa de adaptación épsilon para el aprendizaje de refuerzo similar a VBDE, con garantías de convergencia monótona. En este marco, el parámetro épsilon se considera 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). Esta distribución 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 normal-gamma. (Gimelfarb et al., 2019). ^[36]

Estrategias de emparejamiento de probabilidad

Las estrategias de emparejamiento de probabilidad reflejan la idea de que la cantidad de veces que se tira de una palanca dada debe coincidir con su probabilidad real de ser la palanca óptima. Las estrategias de emparejamiento de probabilidad también se conocen como muestreo de Thompson o Bandits bayesianos, ^{[37] [38]} y son sorprendentemente fáciles de implementar si se puede tomar una muestra de la parte 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. ^[37]

Estrategias de precios

Las estrategias de fijación de precios establecen un precio para cada palanca. Por ejemplo, como se ilustra con el algoritmo POKER, ^[16] 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 precio más alto.

Bandido contextual

Una generalización útil del bandido multibrazo es el bandido multibrazo contextual. En cada iteración, un agente todavía tiene que elegir entre brazos, pero también ve un vector de características de dimensión d, el vector de contexto que puede usar junto con las recompensas de los brazos jugados en el pasado para elegir el brazo que jugará. Con el tiempo, el objetivo del aprendiz es recopilar suficiente información sobre cómo se relacionan entre sí los vectores de contexto y las recompensas, de modo que pueda predecir el siguiente mejor brazo para jugar observando los vectores de características. ^[39]

Soluciones aproximadas para el bandido contextual

Existen muchas estrategias que proporcionan una solución aproximada al problema del bandido contextual y pueden agruparse en dos amplias categorías que se detallan a continuación.

Bandidos lineales en línea

• Algoritmo LinUCB (límite de confianza superior) : los autores suponen una dependencia lineal entre la recompensa esperada de una acción y su contexto y modelan el espacio de representación utilizando un conjunto de predictores lineales. ^{[40] [41]}
• Algoritmo LinRel (aprendizaje de refuerzo asociativo lineal) : similar a LinUCB, pero utiliza descomposición en valores singulares en lugar de regresión de Ridge para obtener una estimación de confianza. ^{[42] [43]}

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 la regresión no paramétrica . Luego, se emplea UCB en cada parte constante. Los refinamientos sucesivos de la partición del espacio de contexto se programan o eligen de manera adaptativa. ^{[44] [45] [46]}
• Algoritmos lineales generalizados : la distribución de recompensas sigue un modelo lineal generalizado, una extensión de los bandidos lineales. ^{[47] [48] [49] [50]}
• Algoritmo KernelUCB : una versión no lineal kernelizada de linearUCB, con implementación eficiente y análisis de tiempo finito. ^[51]
• Algoritmo Bandit Forest : se construye y analiza un bosque aleatorio con respecto al bosque aleatorio construido conociendo la distribución conjunta de contextos y recompensas. ^[52]
• Algoritmo basado en Oracle : el algoritmo reduce el problema del bandido contextual a una serie de problemas de aprendizaje supervisado y no se basa en el supuesto de realizabilidad típico de la función de recompensa. ^[53]

Bandido contextual restringido

En la práctica, suele haber un coste asociado al recurso consumido por cada acción y el coste 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 tanto las restricciones de tiempo como las de presupuesto en un entorno de bandido con múltiples brazos. A. Badanidiyuru et al. ^[54] estudiaron por primera vez los bandidos contextuales con restricciones de presupuesto, también conocidos como bandidos contextuales ingeniosos, y demostraron que es posible llegar a un arrepentimiento. 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 trabajo de UCB-ALP para bandidos contextuales restringidos

En ^{[55] se propone un algoritmo simple con arrepentimiento logarítmico.}

• Algoritmo UCB-ALP : El marco de trabajo 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 un arrepentimiento logarítmico en bandidos contextuales restringidos. Aunque ^[55] está dedicado a un caso especial con una única restricción presupuestaria y un 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 las máquinas tragamonedas con múltiples brazos se denomina máquina tragamonedas adversarial, y fue introducida 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 pagos para cada brazo. Esta es una de las generalizaciones más sólidas del problema de las máquinas tragamonedas ^[56], ya que elimina todos los supuestos de la distribución y una solución al problema de las máquinas tragamonedas adversarial es una solución generalizada a los problemas de máquinas tragamonedas más específicos.

Ejemplo: dilema del prisionero iterado

Un ejemplo que se suele considerar para los bandidos adversarios es el dilema del prisionero iterado . En este ejemplo, cada adversario tiene dos brazos para tirar. Pueden negar o confesar. Los algoritmos de bandidos estocásticos estándar no funcionan muy bien con estas iteraciones. Por ejemplo, si el oponente coopera en las primeras 100 rondas, deserta en las siguientes 200, luego coopera en las siguientes 300, etc., entonces los 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 tira de 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 puede que ni siquiera detecte el cambio.

Soluciones aproximadas

Exp3^[57]

EXP3 es un algoritmo popular para bandidos multiarmados adversarios, sugerido y analizado en este entorno por Auer et al. [2002b]. Recientemente, hubo un creciente interés en el rendimiento de este algoritmo en el entorno estocástico, debido a sus nuevas aplicaciones para bandidos multiarmados estocásticos con información secundaria [Seldin et al., 2011] y para bandidos multiarmados en el entorno mixto estocástico-adversario [Bubeck y Slivkins, 2012]. El artículo presentó una evaluación empírica y un análisis mejorado del rendimiento del algoritmo EXP3 en el entorno estocástico, así como una modificación del algoritmo EXP3 capaz de lograr un arrepentimiento "logarítmico" en el entorno estocástico.

Algoritmo

 Parámetros: Real ${\displaystyle \gamma \in (0,1]}$  Inicialización: para ${\displaystyle \omega _{i}(1)=1}$ ${\displaystyle i=1,...,K}$  Para cada t = 1, 2, ..., T 1. Establecer 2. Sacar al azar según las probabilidades 3. Recibir recompensa 4. Para establecer:      ${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$        ${\displaystyle i=1,...,K}$ ${\displaystyle i_{t}}$ ${\displaystyle p_{1}(t),...,p_{K}(t)}$ ${\displaystyle x_{i_{t}}(t)\in [0,1]}$ ${\displaystyle j=1,...,K}$ ${\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 de que prefiera brazos con pesos más altos (exploit), elige con probabilidad explorar de manera uniforme y aleatoria. Después de recibir las recompensas, los pesos se actualizan. El crecimiento exponencial aumenta significativamente el peso de los buenos brazos. ${\displaystyle (1-\gamma )}$ ${\displaystyle \gamma }$

Análisis del arrepentimiento

El arrepentimiento (externo) del algoritmo Exp3 es como máximo ${\displaystyle O({\sqrt {KTlog(K)}})}$

Seguir el algoritmo del líder perturbado (FPL)

Algoritmo

 Parámetros: Real ${\displaystyle \eta }$  Inicialización:  ${\displaystyle \forall i:R_{i}(1)=0}$  Para cada t = 1,2,...,T 1. Para cada brazo genere un ruido aleatorio a partir de una distribución exponencial 2. Tire del brazo : ${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$ ${\displaystyle I(t)}$ ${\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}$ Añade ruido a cada brazo y tira del que tenga el valor más alto. 3. Actualizar valor: ${\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}$ El resto sigue igual

Explicación

Seguimos el brazo que creemos que tiene el mejor rendimiento hasta el momento agregándole ruido exponencial para proporcionar exploración. ^[58]

Exp3 frente a FPL

Bandido de brazos infinitos

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

Bandido no estacionario

Este marco se refiere al problema de la máquina tragamonedas multiarmada en un entorno no estacionario (es decir, en presencia de una deriva de concepto ). En el entorno no estacionario, se supone que la recompensa esperada para un brazo puede cambiar en cada paso de tiempo : . Por lo tanto, ya no representa la secuencia completa de recompensas esperadas (estacionarias) para el brazo . En cambio, denota la secuencia de recompensas esperadas para el brazo , definida como . ^[60] ${\displaystyle k}$ ${\displaystyle t\in {\mathcal {T}}}$ ${\displaystyle \mu _{t-1}^{k}\neq \mu _{t}^{k}}$ ${\displaystyle \mu _{t}^{k}}$ ${\displaystyle k}$ ${\displaystyle \mu ^{k}}$ ${\displaystyle k}$ ${\displaystyle \mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}}$

Un oráculo dinámico representa la política óptima que se debe comparar con otras políticas en el entorno no estacionario. El oráculo dinámico optimiza la recompensa esperada en cada paso seleccionando siempre la mejor opción, con una recompensa esperada de . Por lo tanto, la recompensa esperada acumulada para el oráculo dinámico en el paso de tiempo final se define como: ${\displaystyle t\in {\mathcal {T}}}$ ${\displaystyle \mu _{t}^{*}}$ ${\displaystyle {\mathcal {D}}(T)}$ ${\displaystyle T}$

${\displaystyle {\mathcal {D}}(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}}$

Por lo tanto, el arrepentimiento por la política se calcula como la diferencia entre y la recompensa esperada acumulada en el paso para la política : ${\displaystyle \rho ^{\pi }(T)}$ ${\displaystyle \pi }$ ${\displaystyle {\mathcal {D}}(T)}$ ${\displaystyle T}$ ${\displaystyle \pi }$

${\displaystyle \rho ^{\pi }(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]={\mathcal {D}}(T)-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]}$

Garivier y Moulines derivan algunos de los primeros resultados con respecto a los problemas de bandidos donde el modelo subyacente puede cambiar durante el juego. Se presentaron varios algoritmos para tratar este caso, incluyendo el UCB descontado ^[61] y el UCB de ventana deslizante ^[62] . Un enfoque similar basado en el algoritmo de muestreo de Thompson es el f-Discounted-Sliding-Window Thompson Sampling (f-dsw TS) ^[63] propuesto por Cavenaghi et al. El algoritmo f-dsw TS explota un factor de descuento en el historial de recompensas y una ventana deslizante relacionada con el brazo para contrastar la deriva de conceptos en entornos no estacionarios. Otro trabajo de Burtini et al. introduce un enfoque de muestreo de Thompson de mínimos cuadrados ponderados (WLS-TS), que resulta beneficioso tanto en los casos no estacionarios conocidos como desconocidos. ^[64]

Otras variantes

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

Bandido de duelo

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

Más recientemente, los investigadores han generalizado algoritmos del MAB tradicional a los bandidos en duelo: Límites de confianza superior relativos (RUCB), ^[68] Ponderación exponencial relativa (REX3), ^[69] Límites de confianza de Copeland (CCB), ^[70] Divergencia empírica mínima relativa (RMED), ^[71] y Muestreo de doble Thompson (DTS). ^[72]

Bandido colaborativo

Los enfoques que utilizan múltiples bandidos que cooperan compartiendo conocimiento para optimizar mejor su rendimiento comenzaron en 2013 con "A Gang of Bandits", ^[73] un algoritmo que se basa en un gráfico de similitud entre los diferentes problemas de bandidos para compartir conocimiento. La necesidad de un gráfico de similitud se eliminó en 2014 mediante el trabajo en el algoritmo CLUB. ^[74] Después de este trabajo, varios otros investigadores crearon algoritmos para aprender múltiples modelos al mismo tiempo bajo la retroalimentación de los bandidos. Por ejemplo, COFIBA fue introducido por Li y Karatzoglou y Gentile (SIGIR 2016), ^[75] 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.

Bandido combinatorio

El problema del Bandido Multiarmado Combinatorio (CMAB) ^{[76] [77] [78]} surge cuando en lugar de una única variable discreta para elegir, un agente necesita elegir valores para un conjunto de variables. Suponiendo que cada variable es discreta, la cantidad de opciones posibles por iteración es exponencial en la cantidad de variables. Se han estudiado varias configuraciones de CMAB en la literatura, desde configuraciones donde las variables son binarias ^[77] hasta configuraciones más generales donde cada variable puede tomar un conjunto arbitrario de valores. ^[78]

Véase también

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

Referencias

1. Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). "Análisis de tiempo finito del problema del bandido multiarmado". Aprendizaje automático . 47 (2/3): 235–256. doi : 10.1023/A:1013689704352 .
2. Katehakis, Michael N.; Veinott, Jr., Arthur F. (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. S2CID  656323.
3. Sébastien Bubeck y Nicolò Cesa-Bianchi (2012), "Análisis de arrepentimiento de problemas de bandidos multiarmados estocásticos y no estocásticos", Foundations and Trends® in Machine Learning: Vol. 5: No. 1, pp 1–122. doi :10.1561/2200000024
4. Gittins, JC (1989), Índices de asignación de bandidos multiarmados , Serie Wiley-Interscience en sistemas y optimización, Chichester: John Wiley & Sons, Ltd., ISBN 978-0-471-92059-5
5. Berry, Donald A. ; 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
6. Soare, M., Lazaric, A. y Munos, R. (2014). Identificación del mejor brazo en bandidos lineales. ArXiv, abs/1409.6110.
7. Weber, Richard (1992), "Sobre el índice de Gittins para bandidos multiarmados", Annals of Applied Probability , 2 (4): 1024–1033, doi : 10.1214/aoap/1177005588 , JSTOR  2959678
8. Robbins, H. (1952). "Algunos aspectos del diseño secuencial de experimentos". Boletín de la Sociedad Americana de Matemáticas . 58 (5): 527–535. doi : 10.1090/S0002-9904-1952-09620-8 .
9. JC Gittins (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.
10. Press, William H. (2009), "Las soluciones Bandit proporcionan modelos éticos unificados para ensayos clínicos aleatorios e investigación de efectividad comparativa", Actas de la Academia Nacional de Ciencias , 106 (52): 22387–22392, Bibcode :2009PNAS..10622387P, doi : 10.1073/pnas.0912378106 , PMC 2793317 , PMID  20018711. 
11. Prensa (1986)
12. Brochu, Eric; Hoffman, Matthew W.; de Freitas, Nando (septiembre de 2010), Asignación de cartera para optimización bayesiana , arXiv : 1009.5419 , Bibcode :2010arXiv1009.5419B
13. Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015), "Opciones de cartera con aprendizaje de bandidos ortogonales", Actas de las conferencias conjuntas internacionales sobre inteligencia artificial (IJCAI2015) , archivado desde el original el 2021-12-04 , consultado el 20 de marzo de 2016
14. Farias, Vivek F; Ritesh, Madan (2011), "El problema irrevocable del bandido multiarmado", Investigación de operaciones , 59 (2): 383–399, CiteSeerX 10.1.1.380.6983 , doi :10.1287/opre.1100.0891 
15. Whittle, Peter (1979), "Discusión del artículo del Dr. Gittins", Journal of the Royal Statistical Society , Serie B, 41 (2): 148–177, doi :10.1111/j.2517-6161.1979.tb01069.x
16. Vermorel, Joannes; Mohri, Mehryar (2005), Algoritmos de bandidos multiarmados y evaluación empírica (PDF) , en European Conference on Machine Learning, Springer, págs. 437–448
17. Whittle, Peter (1988), "Bandidos inquietos: asignación de actividades en un mundo cambiante", Journal of Applied Probability , 25A : 287–298, doi :10.2307/3214163, JSTOR  3214163, MR  0974588, S2CID  202109695
18. Whittle, Peter (1981), "Bandidos que adquieren armas", Anales de probabilidad , 9 (2): 284–292, doi : 10.1214/aop/1176994469
19. Auer, P.; Cesa-Bianchi, N.; Freund, Y.; Schapire, RE (2002). "El problema del bandido multiarmado no estocástico". SIAM J. Comput. 32 (1): 48–77. CiteSeerX 10.1.1.130.158 . doi :10.1137/S0097539701398375. S2CID  13209702.  
20. Aurelien Garivier; Emilie Kaufmann, "Identificación óptima del mejor brazo con confianza fija", Journal of Machine Learning Research (JMLR)
21. Lai, TL; Robbins, H. (1985). "Reglas de asignación adaptativa asintóticamente eficientes". Avances en Matemáticas Aplicadas . 6 (1): 4–22. doi : 10.1016/0196-8858(85)90002-8 .
22. Katehakis, MN; Robbins, H. (1995). "Elección secuencial de varias poblaciones". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 92 (19): 8584–5. Bibcode :1995PNAS...92.8584K. doi : 10.1073/pnas.92.19.8584 . PMC 41010 . PMID  11607577. 
23. Burnetas, AN; Katehakis, MN (1996). "Políticas adaptativas óptimas para problemas de asignación secuencial". Avances en Matemáticas Aplicadas . 17 (2): 122–142. doi : 10.1006/aama.1996.0007 .
24. Burnetas, Apostolos N.; Katehakis, Michael N. (1997). "Políticas adaptativas óptimas para procesos de decisión de Markov". Matemáticas de la investigación de operaciones . 22 (1): 222–255. doi :10.1287/moor.22.1.222.
25. Tewari, A.; Bartlett, PL (2008). "La programación lineal optimista da arrepentimiento logarítmico para MDP irreducibles" (PDF) . Avances en sistemas de procesamiento de información neuronal . 20. CiteSeerX 10.1.1.69.5482 . Archivado desde el original (PDF) el 25 de mayo de 2012. Consultado el 12 de octubre de 2012 . 
26. Ortner, R. (2010). "Límites de arrepentimiento en línea para procesos de decisión de Markov con transiciones deterministas". Ciencias Informáticas Teóricas . 411 (29): 2684–2695. doi : 10.1016/j.tcs.2010.04.005 .
27. Filippi, S. y Cappé, O. y Garivier, A. (2010). "Límites de arrepentimiento en línea para procesos de decisión de Markov con transiciones deterministas", Comunicación, control y computación (Allerton), 48.ª conferencia anual de Allerton sobre 2010 , págs. 115-122
28. Honda, J.; Takemura, A. (2011). "Una política asintóticamente óptima para modelos de soporte finito en el problema de la máquina tragamonedas multiarmada". Aprendizaje automático . 85 (3): 361–391. arXiv : 0905.2776 . doi :10.1007/s10994-011-5257-4. S2CID  821462.
29. Pilarski, Sebastián; Pilarski, Slawomir; Varró, Dániel (febrero 2021). "Política óptima para los bandidos de Bernoulli: calibre de algoritmos y computación". Transacciones IEEE sobre Inteligencia Artificial . 2 (1): 2–17. doi : 10.1109/TAI.2021.3074122 . ISSN  2691-4581. S2CID  235475602.
30. Pilarski, Sebastian; Pilarski, Slawomir; Varro, Daniel (2021). "Bandidos de Bernoulli con recompensa retrasada: política óptima y metaalgoritmo predictivo PARDI". IEEE Transactions on Artificial Intelligence . 3 (2): 152–163. doi : 10.1109/TAI.2021.3117743 . ISSN  2691-4581. S2CID  247682940.
31. Averbeck, BB (2015). "Teoría de la elección en tareas de bandidos, muestreo de información y búsqueda de alimento". PLOS Computational Biology . 11 (3): e1004164. Bibcode :2015PLSCB..11E4164A. doi : 10.1371/journal.pcbi.1004164 . PMC 4376795 . PMID  25815510. 
32. Costa, VD; Averbeck, BB (2019). "Sustratos subcorticales de las decisiones de exploración-explotación en primates". Neuron . 103 (3): 533–535. doi :10.1016/j.neuron.2019.05.017. PMC 6687547 . PMID  31196672. 
33. Sutton, RS y Barto, AG 1998 Aprendizaje por refuerzo: una introducción. Cambridge, MA: MIT Press.
34. Tokic, Michel (2010), "Exploración adaptativa ε-greedy en el aprendizaje de refuerzo basado en diferencias de valores" (PDF) , KI 2010: Avances en inteligencia artificial , Lecture Notes in Computer Science, vol. 6359, Springer-Verlag, págs. 203–210, CiteSeerX 10.1.1.458.464 , doi :10.1007/978-3-642-16111-7_23, ISBN  978-3-642-16110-0.
35. Tokic, Michel; Palm, Günther (2011), "Exploración basada en la diferencia de valores: control adaptativo entre Epsilon-Greedy y Softmax" (PDF) , KI 2011: Avances en inteligencia artificial , Lecture Notes in Computer Science, vol. 7006, Springer-Verlag, págs. 335–346, ISBN 978-3-642-24455-1.
36. Gimelfarb, Michel; Sanner, Scott; Lee, Chi-Guhn (2019), "ε-BMC: un enfoque de conjunto bayesiano para la exploración épsilon-codiciosa en el aprendizaje por refuerzo sin modelos" (PDF) , Actas de la trigésima quinta conferencia sobre incertidumbre en inteligencia artificial , AUAI Press, pág. 162.
37. Scott, SL (2010), "Una mirada bayesiana moderna al bandido multibrazo", Modelos estocásticos aplicados en los negocios y la industria , 26 (2): 639–658, doi :10.1002/asmb.874, S2CID  573750
38. Olivier Chapelle; Lihong Li (2011), "Una evaluación empírica del muestreo de Thompson", Avances en sistemas de procesamiento de información neuronal , 24 , Curran Associates: 2249–2257
39. Langford, John; Zhang, Tong (2008), "El algoritmo Epoch-Greedy para bandidos multiarmados contextuales", Advances in Neural Information Processing Systems , vol. 20, Curran Associates, Inc., págs. 817–824
40. Lihong Li; Wei Chu; John Langford; Robert E. Schapire (2010), "Un enfoque contextual-bandit para la recomendación personalizada de artículos de noticias", Actas de la 19.ª conferencia internacional sobre Internet , pp. 661–670, arXiv : 1003.0146 , Bibcode :2010arXiv1003.0146L, doi :10.1145/1772690.1772758, ISBN 9781605587998, Número de identificación del sujeto  207178795
41. Wei Chu; Lihong Li; Lev Reyzin; Robert E. Schapire (2011), "Bandidos contextuales con funciones de pago lineales" (PDF) , Actas de la 14.ª Conferencia internacional sobre inteligencia artificial y estadística (AISTATS) : 208–214
42. Auer, P. (2000). "Uso de límites de confianza superiores para el aprendizaje en línea". Actas del 41.° Simposio anual sobre fundamentos de la informática . IEEE Comput. Soc., págs. 270-279. doi :10.1109/sfcs.2000.892116. ISBN 978-0769508504. Número de identificación del sujeto  28713091.
43. Hong, Tzung-Pei; Song, Wei-Ping; Chiu, Chu-Tien (noviembre de 2011). "Agrupamiento evolutivo de atributos compuestos". Conferencia internacional de 2011 sobre tecnologías y aplicaciones de la inteligencia artificial . IEEE. págs. 305–308. doi :10.1109/taai.2011.59. ISBN. 9781457721748.S2CID14125100  .​
44. Rigollet, Philippe; Zeevi, Assaf (2010), Bandidos no paramétricos con covariables , Conferencia sobre teoría del aprendizaje, COLT 2010, arXiv : 1003.1630 , Bibcode :2010arXiv1003.1630R
45. Slivkins, Aleksandrs (2011), Bandidos contextuales con información de similitud. (PDF) , Conferencia sobre teoría del aprendizaje, COLT 2011
46. Perchet, Vianney; Rigollet, Philippe (2013), "El problema del bandido multiarmado con covariables", Anales de Estadística , 41 (2): 693–721, arXiv : 1110.6084 , doi :10.1214/13-aos1101, S2CID  14258665
47. Sarah Filippi; Olivier Cappé; Aurélien Garivier; Csaba Szepesvári (2010), "Bandidos paramétricos: el caso lineal generalizado", Avances en sistemas de procesamiento de información neuronal , 23 , Curran Associates: 586–594
48. Lihong Li; Yu Lu; Dengyong Zhou (2017), "Algoritmos demostrablemente óptimos para bandidos contextuales lineales generalizados", Actas de la 34.ª Conferencia internacional sobre aprendizaje automático (ICML) : 2071–2080, arXiv : 1703.00048 , Bibcode :2017arXiv170300048L
49. Kwang-Sung Jun; Aniruddha Bhargava; Robert D. Nowak; Rebecca Willett (2017), "Bandidos lineales generalizados escalables: computación en línea y hash", Avances en sistemas de procesamiento de información neuronal , 30 , Curran Associates: 99–109, arXiv : 1706.00136 , Bibcode :2017arXiv170600136J
50. Branislav Kveton; Manzil Zaheer; Csaba Szepesvári; Lihong Li; Mohammad Ghavamzadeh; Craig Boutilier (2020), "Exploración aleatoria en bandidos lineales generalizados", Actas de la 23.ª Conferencia Internacional sobre Inteligencia Artificial y Estadística (AISTATS) , arXiv : 1906.08947 , Bibcode :2019arXiv190608947K
51. Michal Valko; Nathan Korda; Rémi Munos; Ilias Flaounas; Nello Cristianini (2013), Análisis de tiempo finito de bandidos contextuales kernelizados , 29.ª Conferencia sobre incertidumbre en inteligencia artificial (UAI 2013) y (JFPDA 2013)., arXiv : 1309.6869 , Bibcode :2013arXiv1309.6869V
52. Féraud, Raphaël; Allesiardo, Robin; Urvoy, Tanguy; Clérot, Fabrice (2016). «Random Forest for the Contextual Bandit Problem». Aistats : 93–101. Archivado desde el original el 2016-08-10 . Consultado el 2016-06-10 .
53. Alekh Agarwal; Daniel J. Hsu; Satyen Kale; John Langford; Lihong Li; Robert E. Schapire (2014), "Domar al monstruo: un algoritmo rápido y simple para bandidos contextuales", Actas de la 31.ª Conferencia Internacional sobre Aprendizaje Automático (ICML) : 1638–1646, arXiv : 1402.0555 , Bibcode :2014arXiv1402.0555A
54. Badanidiyuru, A.; Langford, J.; Slivkins, A. (2014), "Bandidos contextuales ingeniosos" (PDF) , Actas de la Conferencia sobre teoría del aprendizaje (COLT)^{[ enlace muerto permanente ]}
55. Wu, Huasen; Srikant, R.; Liu, Xin; Jiang, Chong (2015), "Algoritmos con arrepentimiento logarítmico o sublineal para bandidos contextuales restringidos", 29.ª Conferencia anual sobre sistemas de procesamiento de información neuronal (NIPS) , 28 , Curran Associates: 433–441, arXiv : 1504.06937 , Bibcode :2015arXiv150406937W
56. Burtini, Giuseppe, Jason Loeppky y Ramon Lawrence. "Un estudio sobre el diseño de experimentos en línea con el bandido multibrazo estocástico". Preimpresión de arXiv arXiv :1510.00757 (2015).
57. Seldin, Y., Szepesvári, C., Auer, P. y Abbasi-Yadkori, Y., 2012, diciembre. Evaluación y análisis del rendimiento del algoritmo EXP3 en entornos estocásticos. En EWRL (pp. 103–116).
58. Hutter, M. y Poland, J., 2005. Predicción adaptativa en línea siguiendo al líder perturbado. Journal of Machine Learning Research, 6 (abril), págs. 639-660.
59. Agrawal, Rajeev. El problema del bandido armado continuo. SIAM J. of Control and Optimization. 1995.
60. Besbes, O.; Gur, Y.; Zeevi, A. Problema estocástico de bandidos multiarmados con recompensas no estacionarias. En Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canadá, 8-13 de diciembre de 2014; págs. 199-207<https://proceedings.neurips.cc/paper/2014/file/903ce9225fca3e988c2af215d4e544d3-Paper.pdf>
61. UCB con descuento, Levente Kocsis, Csaba Szepesvári, 2006
62. Sobre políticas de límite de confianza superior para problemas de bandidos no estacionarios, Garivier y Moulines, 2008 <https://arxiv.org/abs/0805.3415>
63. Cavenaghi, E.; Sottocornola, G.; Stella, F.; Zanker, M. Bandido multiarmado no estacionario: evaluación empírica de un nuevo concepto de algoritmo consciente de la deriva. Entropy 2021, 23, 380. <https://doi.org/10.3390/e23030380>
64. Mejorar los experimentos de marketing online con bandidos multiarmados a la deriva, Giuseppe Burtini, Jason Loeppky, Ramon Lawrence, 2015 <http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=Dx2xXEB0PJE=&t=1>
65. Yue, Yisong; Broder, Josef; Kleinberg, Robert; Joachims, Thorsten (2012), "El problema de los bandidos en duelo armados con K", Journal of Computer and System Sciences , 78 (5): 1538–1556, CiteSeerX 10.1.1.162.2764 , doi :10.1016/j.jcss.2011.12.028 
66. Yue, Yisong; Joachims, Thorsten (2011), "Derrotar al bandido malvado", Actas de ICML'11
67. Urvoy, Tanguy; Clérot, Fabrice; Féraud, Raphaël; Naamane, Sami (2013), "Exploración genérica y bandidos de votación armados con K" (PDF) , Actas de la 30.ª Conferencia internacional sobre aprendizaje automático (ICML-13) , archivado desde el original (PDF) el 2 de octubre de 2016 , consultado el 29 de abril de 2016
68. Zoghi, Masrour; Whiteson, Shimon; Munos, Remi; Rijke, Maarten D (2014), "Límite de confianza superior relativo para el problema del bandido de duelo armado con $K$" (PDF) , Actas de la 31.ª Conferencia internacional sobre aprendizaje automático (ICML-14) , archivado desde el original (PDF) el 26 de marzo de 2016 , consultado el 27 de abril de 2016
69. Gajane, Pratik; Urvoy, Tanguy; Clérot, Fabrice (2015), "Un algoritmo de ponderación exponencial relativa para bandidos en duelo basados ​​en utilidad adversaria" (PDF) , Actas de la 32.ª Conferencia internacional sobre aprendizaje automático (ICML-15) , archivado desde el original (PDF) el 8 de septiembre de 2015 , consultado el 29 de abril de 2016
70. Zoghi, Masrour; Karnin, Zohar S; Whiteson, Shimon; Rijke, Maarten D (2015), "Los bandidos en duelo de Copeland", Avances en sistemas de procesamiento de información neuronal, NIPS'15 , arXiv : 1506.00312 , Bibcode :2015arXiv150600312Z
71. Komiyama, Junpei; Honda, Junya; Kashima, Hisashi; Nakagawa, Hiroshi (2015), "Límite inferior de arrepentimiento y algoritmo óptimo en el problema del duelo de bandidos" (PDF) , Actas de la 28.ª Conferencia sobre teoría del aprendizaje , archivado desde el original (PDF) el 2016-06-17 , consultado el 2016-04-27
72. Wu, Huasen; Liu, Xin (2016), "Muestreo de doble Thompson para duelos de bandidos", 30.ª Conferencia anual sobre sistemas de procesamiento de información neuronal (NIPS) , arXiv : 1604.07101 , Bibcode :2016arXiv160407101W
73. Cesa-Bianchi, Nicolo; Gentile, Claudio; Zappella, Giovanni (2013), Una banda de bandidos , Avances en sistemas de procesamiento de información neuronal 26, NIPS 2013, arXiv : 1306.0811
74. Gentile, Claudio; Li, Shuai; Zappella, Giovanni (2014), "Agrupamiento en línea de bandidos", 31.ª Conferencia internacional sobre aprendizaje automático, Journal of Machine Learning Research (ICML 2014) , arXiv : 1401.8257 , Bibcode :2014arXiv1401.8257G
75. Li, Shuai; Alexandros, Karatzoglou; Gentile, Claudio (2016), "Bandidos del filtrado colaborativo", 39.ª Conferencia internacional ACM SIGIR sobre recuperación de información (SIGIR 2016) , arXiv : 1502.03473 , Bibcode :2015arXiv150203473L
76. Gai, Y.; Krishnamachari, B.; Jain, R. (2010), "Aprendizaje de asignaciones de canales multiusuario en redes de radio cognitivas: una formulación combinatoria de bandido multiarmado", Simposio IEEE de 2010 sobre nuevas fronteras en espectro dinámico (PDF) , págs. 1–9^{[ enlace muerto ]}
77. Chen, Wei; Wang, Yajun; Yuan, Yang (2013), "Combinatorial multi-armed bandit: General framework and applications", Actas de la 30.ª Conferencia Internacional sobre Aprendizaje Automático (ICML 2013) (PDF) , pp. 151–159, archivado desde el original (PDF) el 2016-11-19 , consultado el 2019-06-14
78. Santiago Ontañón (2017), "Bandoleras multiarmadas combinatorias para juegos de estrategia en tiempo real", Journal of Artificial Intelligence Research , 58 : 665–702, arXiv : 1710.04805 , Bibcode :2017arXiv171004805O, doi :10.1613/jair.5398, S2CID  8517525

Lectura adicional

• 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: solución de 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 Sociedad Matemática Americana , 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), "Un comité de redes neuronales para el problema del bandido contextual", Procesamiento de información neuronal – 21.ª conferencia internacional, ICONIP 2014, Malasia, 3-6 de noviembre de 2014, Actas , Lecture Notes in Computer Science, vol. 8834, Springer, págs. 374–381, arXiv : 1409.8191 , doi : 10.1007/978-3-319-12637-1_47, ISBN 978-3-319-12636-4, Número de identificación del sujeto  14155718.

• Weber, Richard (1992), "Sobre el índice de Gittins para bandidos multiarmados", Annals of Applied Probability , 2 (4): 1024–1033, doi : 10.1214/aoap/1177005588 , JSTOR  2959678.
• Katehakis, M. ; C. Derman (1986), "Computing optimal sequential mapping rules in clinical trials", Procedimientos estadísticos adaptativos y temas relacionados , Institute of Mathematical Statistics Lecture Notes - Monograph Series, vol. 8, págs. 29–39, doi : 10.1214/lnms/1215540286 , ISBN 978-0-940600-09-6, JSTOR  4355518.
• Katehakis, Michael N .; Veinott, Jr., Arthur F. (1987), "El problema del bandido multiarmado: descomposición y cálculo", Matemáticas de la investigación de operaciones , 12 (2): 262–268, doi :10.1287/moor.12.2.262, JSTOR  3689689, S2CID  656323

Enlaces externos

• MABWiser, implementación Python de código abierto de estrategias de bandidos que admite políticas contextuales paramétricas y no paramétricas libres de contexto con capacidad de simulación y paralelización incorporada.
• PyMaBandits, implementación de código abierto de estrategias de bandidos en Python y Matlab.
• Paquete R contextual de código abierto que facilita la simulación y evaluación de políticas de Bandido Multiarmado tanto contextuales como libres de contexto.
• bandit.sourceforge.net Proyecto Bandit, implementación de código abierto de estrategias de bandidos.
• Banditlib, implementación de código abierto de estrategias de bandidos 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. Parte 1. Parte 2.
• El problema del restaurante de Feynman, un ejemplo clásico (con respuesta conocida) del dilema entre explotación y exploración.
• Algoritmos Bandit vs. Pruebas AB.
• S. Bubeck y N. Cesa-Bianchi. Una encuesta sobre bandidos.
• Una encuesta sobre bandidos multiarmados contextuales, una encuesta/tutorial para bandidos contextuales.
• Entrada de blog sobre estrategias de bandidos con múltiples brazos, con código Python.
• Gráficos animados e interactivos que ilustran estrategias de equilibrio de exploración/explotación de muestreo de Thompson , Epsilon-greedy y límite de confianza superior.