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 la probabilidad y aprendizaje automático , el problema de los bandidos con múltiples brazos (a veces llamado problema de los bandidos con K-[1] o N-armed [ 2 ^] ) es ^un problema en el que quien toma decisiones selecciona de forma iterativa una de múltiples opciones fijas (es decir, brazos o acciones) cuando las propiedades de cada elección se conocen sólo parcialmente en el momento de su asignación y pueden entenderse mejor a medida que pasa el tiempo. Un aspecto fundamental de los problemas de los bandidos es que la elección de un arma no afecta las propiedades del brazo ni de otras armas. ^[3]

Los ejemplos del problema de los bandidos con múltiples brazos incluyen la tarea de asignar iterativamente un conjunto fijo y limitado de recursos entre opciones (alternativas) competitivas de una manera que minimice el arrepentimiento . ^{[4] [5]} Las configuraciones alternativas para el problema de los bandidos con múltiples brazos incluyen el problema de "identificación del mejor brazo", donde el objetivo es identificar la mejor opción al final de un número finito de rondas. ^[6]

El problema de los bandidos con múltiples brazos es un problema clásico de aprendizaje por refuerzo que ejemplifica el dilema del equilibrio entre exploración y explotación . A diferencia de la RL general, las acciones seleccionadas en los problemas de bandidos no afectan la distribución de recompensa de las armas. El nombre proviene de imaginar a un jugador en una fila de máquinas tragamonedas (a veces conocido como "bandidos mancos"), 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 los bandidos con múltiples brazos también cae en 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 las recompensas obtenidas mediante una secuencia de tirones de palanca. ^{[4] [5]} El equilibrio crucial que enfrenta el jugador en cada prueba es entre la "explotación" de la máquina que tiene el mayor beneficio esperado y la "exploración" para obtener más información sobre los beneficios esperados de las otras máquinas. El equilibrio entre exploración y explotación también se enfrenta en el aprendizaje automático . En la práctica, se han utilizado bandidos con múltiples brazos para modelar problemas como la gestión de proyectos de investigación en una organización grande, 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.

Herbert Robbins en 1952, al darse cuenta de la importancia del problema, construyó estrategias de selección de población convergentes 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 se debe distribuir un presupuesto determinado entre estos departamentos de investigación para maximizar los resultados?

El problema de los bandidos de múltiples brazos modela un agente que simultáneamente intenta adquirir nuevos conocimientos (llamado "exploración") y optimizar sus decisiones basándose 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. Existen muchas aplicaciones prácticas del modelo bandido, por ejemplo:

• ensayos clínicos que investigan los efectos de diferentes tratamientos experimentales y al mismo tiempo minimizan las pérdidas de pacientes, ^{[4] [5] [10] [11]}
• esfuerzos de enrutamiento adaptativo para minimizar 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 basada en el conocimiento ya adquirido con el intento de nuevas acciones para aumentar aún más el conocimiento. Esto se conoce como 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. ^[14]

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

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

El modelo de bandido con múltiples brazos

El bandido de múltiples brazos (abreviado: bandido o MAB) puede verse como un conjunto de distribuciones reales , cada distribución 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 recompensa 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 media de recompensa máxima, 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 cero arrepentimiento convergerán hacia 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, en caso 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 juega un brazo en particular, el estado de esa máquina avanza a uno nuevo, elegido según las probabilidades de evolución del estado de Markov. Hay una recompensa dependiendo del estado actual de la máquina. En una generalización denominada "problema de los bandidos inquietos", los estados de las armas no utilizadas también pueden evolucionar con el tiempo. ^[17] También se ha debatido sobre sistemas en los que el número de opciones (sobre qué brazo jugar) aumenta con el tiempo. ^[18]

Los investigadores de informática han estudiado a los bandidos con múltiples brazos bajo los peores supuestos, obteniendo algoritmos para minimizar el arrepentimiento en horizontes de tiempo finitos e infinitos ( asintóticos ) para pagos de brazos tanto estocásticos ^[1] como no estocásticos ^[19] .

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 con 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 ^[20] (siguiendo 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 convergentes que poseen la tasa de convergencia más rápida (a la población con la 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 ^[21] se dieron simplificaciones de la política y la prueba principal para el caso de poblaciones normales con varianzas conocidas. El siguiente progreso notable lo obtuvieron Burnetas y Katehakis en el artículo "Optimal adaptivepolicies for sequential asignation problemas", ^[22] donde se construyeron políticas basadas en índices con una tasa de convergencia uniformemente máxima, bajo condiciones más generales que incluyen el caso en el que las distribuciones de los 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 y arbitrarias (es decir, no paramétricas).

Más adelante, en "Políticas adaptativas óptimas para los procesos de decisión de Markov" ^[23] 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, los autores construyeron una forma explícita para una clase de políticas adaptativas con propiedades de tasa de convergencia uniformemente máxima para la recompensa total esperada en un horizonte finito bajo supuestos suficientes de espacios finitos de acción estatal e 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 la recompensa promedio estimada. Estas inflaciones han sido denominadas recientemente el enfoque optimista en el trabajo de Tewari y Bartlett, ^[24] Ortner ^[25] Filippi, Cappé y Garivier, ^[26] y Honda y Takemura. ^[27]

Para los bandidos multiarmados de Bernoulli, Pilarski et al. ^[28] estudiaron métodos de cálculo para derivar soluciones totalmente óptimas (no sólo asintóticamente) utilizando programación dinámica en el artículo "Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge". ^[28] A través de 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 el número de armas no se volvieran excesivamente grandes. Pilarski et al. ^[29] posteriormente amplió este trabajo en "Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI" ^[29] 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 estar retrasado. Este método se basa en calcular los valores esperados de los resultados de las recompensas que aún no se han revelado y en actualizar las probabilidades posteriores cuando se revelan las recompensas.

Cuando se utilizan soluciones óptimas para tareas de bandidos de múltiples brazos ^[30] 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 usar para decodificar cuando los animales tomar decisiones exploratorias versus 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 a los problemas de los bandidos con múltiples brazos son biológicamente plausibles, a pesar de ser exigentes desde el punto de vista computacional. ^[31]

Soluciones aproximadas

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

Estrategias semiuniformes

Las estrategias semiuniformes fueron las primeras (y más simples) descubiertas 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 previas), excepto cuando se toma una acción (uniformemente) aleatoria.

• Estrategia codiciosa de Epsilon : ^[32] Se selecciona la mejor palanca para una proporción de las pruebas, 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 puede variar ampliamente según las circunstancias y predilecciones. ${\displaystyle 1-\epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon =0.1}$
• Primera estrategia de Epsilon ^{[ cita necesaria ]} : A una fase de exploración pura le sigue una fase de explotación pura. Para el total de ensayos, la fase de exploración ocupa los ensayos y la fase de explotación . Durante la fase de exploración, se selecciona aleatoriamente una palanca (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 decreciente de épsilon ^{[ cita necesaria ]} : Similar a la estrategia codiciosa de épsilon, 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 épsilon-codiciosa basada en diferencias de valores (VDBE) : similar a la estrategia épsilon-decreciente, excepto que épsilon se reduce en función del progreso del aprendizaje en lugar del ajuste manual (Tokic, 2010). ^[33] Las altas fluctuaciones en las estimaciones de valor conducen a un alto épsilon (alta exploración, baja explotación); fluctuaciones bajas a un épsilon bajo (baja exploración, alta explotación). Se pueden lograr mejoras adicionales mediante una selección de acción ponderada por softmax en el caso de acciones exploratorias (Tokic y Palm, 2011). ^[34]
• 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 a un agente codicioso (que confía plenamente en la recompensa aprendida) y a 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 gamma normal. (Gimelfarb et al., 2019). ^[35]

Estrategias de coincidencia de probabilidades

Las estrategias de emparejamiento de probabilidad 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 coincidencia de probabilidad también se conocen como muestreo de Thompson o bandidos bayesianos, ^{[36] [37]} y son sorprendentemente fáciles de implementar si se puede muestrear desde la parte posterior el valor medio de cada alternativa.

Las estrategias de emparejamiento de probabilidades también admiten soluciones a los llamados problemas contextuales de bandidos. ^[36]

Estrategias de precios

Las estrategias 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 gracias al conocimiento adicional. Siempre se tira de la palanca del precio más alto.

bandido contextual

Una generalización útil del bandido con múltiples brazos es el bandido con múltiples brazos contextual. En cada iteración, un agente todavía tiene que elegir entre armas, pero también ve un vector de características d-dimensional, el vector de contexto que puede usar junto con las recompensas de las armas jugadas en el pasado para elegir qué arma jugar. 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 observando los vectores de características. ^[38]

Soluciones aproximadas para bandido contextual.

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

Bandidos lineales en línea

• Algoritmo LinUCB (Upper Confidence Bound) : los autores asumen 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. ^{[39] [40]}
• Algoritmo LinRel (aprendizaje por refuerzo asociativo lineal) : similar a LinUCB, pero utiliza descomposición de valores singulares en lugar de regresión de crestas para obtener una estimación de confianza. ^{[41] [42]}

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 sucesivos refinamientos de la partición del espacio contextual se programan o eligen de forma adaptativa. ^{[43] [44] [45]}
• Algoritmos lineales generalizados : la distribución de recompensas sigue un modelo lineal generalizado, una extensión de los bandidos lineales. ^{[46] [47] [48] [49]}
• Algoritmo KernelUCB : una versión no lineal kernelizada de linearUCB, con implementación eficiente y análisis de tiempo finito. ^[50]
• Algoritmo de Bandit Forest : se construye y analiza un bosque aleatorio conociendo la distribución conjunta de contextos y recompensas. ^[51]
• Algoritmo basado en Oracle : el algoritmo reduce el problema contextual del bandido 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. ^[52]

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 las limitaciones de tiempo y presupuesto en un entorno de bandido con múltiples brazos. A. Badanidiyuru y col. ^[53] estudiaron por primera vez a los bandidos contextuales con restricciones presupuestarias, también conocidos como bandidos contextuales ingeniosos, y muestran que es posible arrepentirse. 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

Un algoritmo simple con arrepentimiento logarítmico se propone en: ^[54]

• 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 un arrepentimiento logarítmico en bandidos contextuales restringidos. Aunque ^[54] está dedicado a un caso especial con restricción presupuestaria única 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 pagos para cada brazo. Esta es una de las generalizaciones más fuertes del problema de los bandidos ^[55] , ya que elimina todos los supuestos de la distribución y una solución al problema de los bandidos adversarios es una solución generalizada a los problemas de bandidos más específicos.

Ejemplo: el dilema del prisionero iterado

Un ejemplo que se considera a menudo 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 bandidos estocásticos estándar no funcionan muy bien con estas iteraciones. Por ejemplo, si el oponente coopera en las primeras 100 rondas, deserta durante 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 recurre a armas subóptimas para limitar la exploración y centrarse en la explotación. Cuando el entorno cambia, el algoritmo no puede adaptarse o ni siquiera detecta el cambio.

Soluciones aproximadas

Exp3 ^[56]

EXP3 es un algoritmo popular para bandidos adversarios con múltiples armas, sugerido y analizado en este contexto por Auer et al. [2002b]. Recientemente hubo un mayor interés en el rendimiento de este algoritmo en el entorno estocástico, debido a sus nuevas aplicaciones a bandidos estocásticos de múltiples brazos con información secundaria [Seldin et al., 2011] y a bandidos de múltiples brazos en el estocástico mixto. entorno 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 un entorno estocástico, así como una modificación del algoritmo EXP3 capaz de lograr un arrepentimiento "logarítmico" en un entorno estocástico.

Algoritmo

 Parámetros: reales ${\displaystyle \gamma \in (0,1]}$  Inicialización: para ${\displaystyle \omega _{i}(1)=1}$ ${\displaystyle i=1,...,K}$  Para cada t = 1, 2, ..., T 1. Conjunto 2. Sortear aleatoriamente según las probabilidades 3. Recibir recompensa 4. Por conjunto:      ${\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 (explotar), elige con probabilidad de explorar de manera uniforme y aleatoria. Después de recibir las recompensas, los pesos se actualizan. El crecimiento exponencial aumenta significativamente el peso de las buenas armas. ${\displaystyle (1-\gamma )}$ ${\displaystyle \gamma }$

Análisis de arrepentimiento

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

Siga el algoritmo del líder perturbado (FPL)

Algoritmo

 Parámetros: reales ${\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 mayor valor. 3. Valor de actualización: ${\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 y le agregamos ruido exponencial para brindar exploración. ^[57]

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 del armado infinito, introducido por Agrawal (1995), ^[58] los "brazos" son una variable continua en dimensiones. ${\displaystyle K}$ ${\displaystyle K}$

Bandido no estacionario

Este marco se refiere al problema de los bandidos con múltiples brazos en un entorno no estacionario (es decir, en presencia de una deriva conceptual ). En el entorno no estacionario, se supone que la recompensa esperada por un brazo puede cambiar en cada paso del tiempo : . Por lo tanto, ya no representa toda la secuencia de recompensas esperadas (estacionarias) para el brazo . En cambio, denota la secuencia de recompensas esperadas por arm , definida como . ^[59] ${\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 para comparar con otras políticas en un entorno no estacionario. El oráculo dinámico optimiza la recompensa esperada en cada paso seleccionando siempre el mejor brazo, 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 la recompensa esperada acumulada en el paso por 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 obtienen algunos de los primeros resultados con respecto a los problemas de los bandidos en los que el modelo subyacente puede cambiar durante el juego. Se presentaron varios algoritmos para abordar este caso, incluidos UCB con descuento ^[60] y UCB de ventana deslizante. ^[61] Un enfoque similar basado en el algoritmo de muestreo de Thompson es el muestreo de Thompson con ventana deslizante con descuento (f-dsw TS) ^[62] 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 del concepto 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 en los desconocidos. ^[63]

Otras variantes

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

bandido en duelo

La variante de bandido en duelo fue introducida por Yue et al. (2012) ^[64] para modelar el equilibrio entre exploración y explotación para obtener retroalimentación relativa. En esta variante, el jugador puede tirar de dos palancas al mismo tiempo, pero sólo recibe una respuesta 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, ^[64] Beat-The-Mean. ^[65] La relativa retroalimentación 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 . ^[66]

Más recientemente, los investigadores han generalizado algoritmos del MAB tradicional a los bandidos en duelo: límites de confianza superiores relativos (RUCB), ^[67] pesaje exponencial relativo (REX3), ^[68] límites de confianza de Copeland (CCB), ^[69] divergencia empírica mínima relativa ( RMED), ^[70] y muestreo doble Thompson (DTS). ^[71]

Bandido colaborativo

Los enfoques que utilizan múltiples bandidos que cooperan compartiendo conocimientos para optimizar mejor su desempeño comenzaron en 2013 con "A Gang of Bandits", ^[72] un algoritmo que se basa en un gráfico de similitud entre los diferentes problemas de bandidos para compartir conocimientos. La necesidad de un gráfico de similitud fue eliminada en 2014 gracias al trabajo en el algoritmo CLUB. ^[73] Después de este trabajo, varios otros investigadores crearon algoritmos para aprender múltiples modelos al mismo tiempo bajo retroalimentación de bandidos. Por ejemplo, COFIBA fue presentado por Li, Karatzoglou y Gentile (SIGIR 2016), ^[74] donde el filtrado colaborativo clásico y los métodos de filtrado basado en contenido intentan aprender un modelo de recomendación estático dados los datos de entrenamiento.

bandido combinatorio

El problema Combinatorial Multiarmed Bandit (CMAB) ^{[75] [76] [77]} 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, 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 ^[76] hasta configuraciones más generales donde cada variable puede tomar un conjunto arbitrario de valores. ^[77]

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

1. Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). "Análisis en tiempo finito del problema de los bandidos multiarmados". Aprendizaje automático . 47 (2/3): 235–256. doi : 10.1023/A:1013689704352 .
2. Katehakis, Michael N.; Veinott, Jr., Arthur F. (1987). "El problema de los bandidos con múltiples armas: 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 estocásticos y no estocásticos de bandidos con múltiples brazos", Fundamentos y tendencias® en aprendizaje automático: vol. 5: N° 1, págs. 1-122. doi :10.1561/2200000024
4. Gittins, JC (1989), Índices de asignación de bandidos con múltiples brazos , 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 Linear Bandits. ArXiv, abs/1409.6110.
7. Weber, Richard (1992), "Sobre el índice de Gittins para bandidos armados", 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 Matemática Estadounidense . 58 (5): 527–535. doi : 10.1090/S0002-9904-1952-09620-8 .
9. JC Gittins (1979). "Procesos bandidos e índices de asignación dinámica". Revista de la Real Sociedad de Estadística. 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 investigaciones 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, Mateo 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, junio; Jiang, Yu-Gang; Zha, Hongyuan (2015), "Portfolio Choices with Orthogonal Bandit Learning", Actas de conferencias internacionales conjuntas sobre inteligencia artificial (IJCAI2015) , archivado desde el original el 4 de diciembre de 2021 , consultado el 20 de marzo de 2016.
14. Farías, Vivek F; Ritesh, Madan (2011), "El problema irrevocable de los bandidos multiarmados", 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", Revista de la 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 con múltiples brazos y evaluación empírica (PDF) , en la Conferencia europea sobre aprendizaje automático, Springer, págs.
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", Annals of Probability , 9 (2): 284–292, doi : 10.1214/aop/1176994469
19. Auer, P.; Cesa-Bianchi, N.; Freund, Y.; Schapire, RE (2002). "El problema no estocástico de los bandidos multiarmados". SIAM J. Computación. 32 (1): 48–77. CiteSeerX 10.1.1.130.158 . doi :10.1137/S0097539701398375. S2CID  13209702.  
20. Lai, TL; Robbins, H. (1985). "Reglas de asignación adaptativa asintóticamente eficientes". Avances en Matemática Aplicada . 6 (1): 4–22. doi : 10.1016/0196-8858(85)90002-8 .
21. 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. Código bibliográfico : 1995PNAS...92.8584K. doi : 10.1073/pnas.92.19.8584 . PMC 41010 . PMID  11607577. 
22. Burnetas, AN; Katehakis, MN (1996). "Políticas adaptativas óptimas para problemas de asignación secuencial". Avances en Matemática Aplicada . 17 (2): 122-142. doi : 10.1006/aama.1996.0007 .
23. Burnetas, Apostolos N.; Katehakis, Michael N. (1997). "Políticas adaptativas óptimas para los 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.
24. Tewari, A.; Bartlett, PL (2008). "La programación lineal optimista genera arrepentimiento logarítmico para los MDP irreducibles" (PDF) . Avances en los 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 . 
25. Ortner, R. (2010). "El arrepentimiento en línea limita los procesos de decisión de Markov con transiciones deterministas". Informática Teórica . 411 (29): 2684–2695. doi : 10.1016/j.tcs.2010.04.005 .
26. Filippi, S. y Cappé, O. y Garivier, A. (2010). "Límites del arrepentimiento en línea para los procesos de decisión de Markov con transiciones deterministas", Comunicación, control y computación (Allerton), 48ª Conferencia anual de Allerton de 2010 , págs.
27. Honda, J.; Takemura, A. (2011). "Una política asintóticamente óptima para modelos de soporte finitos en el problema de los bandidos con múltiples brazos". Aprendizaje automático . 85 (3): 361–391. arXiv : 0905.2776 . doi :10.1007/s10994-011-5257-4. S2CID  821462.
28. 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.
29. Pilarski, Sebastián; Pilarski, Slawomir; Varrón, Daniel (2021). "Bandidos de Bernoulli de recompensa retrasada: política óptima y metaalgoritmo predictivo PARDI". Transacciones IEEE sobre Inteligencia Artificial . 3 (2): 152–163. doi : 10.1109/TAI.2021.3117743 . ISSN  2691-4581. S2CID  247682940.
30. Averbeck, BB (2015). "Teoría de la elección en tareas de bandidos, muestreo de información y búsqueda de alimento". PLOS Biología Computacional . 11 (3): e1004164. Código Bib : 2015PLSCB..11E4164A. doi : 10.1371/journal.pcbi.1004164 . PMC 4376795 . PMID  25815510. 
31. Costa, VD; Averbeck, BB (2019). "Sustratos subcorticales de decisiones de exploración-explotación en primates". Neurona . 103 (3): 533–535. doi :10.1016/j.neuron.2019.05.017. PMC 6687547 . PMID  31196672. 
32. Sutton, RS y Barto, AG 1998 Aprendizaje por refuerzo: una introducción. Cambridge, MA: MIT Press.
33. Tokic, Michel (2010), "Exploración adaptativa ε-codiciosa en el aprendizaje por 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.
34. 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 , Apuntes de conferencias en informática, vol. 7006, Springer-Verlag, págs. 335–346, ISBN 978-3-642-24455-1.
35. Gimelfarb, Michel; Sanner, Scott; Lee, Chi-Guhn (2019), "ε-BMC: A Bayesian Ensemble Approach to Epsilon-Greedy Exploration in Model-Free Reinforcement Learning" (PDF) , Actas de la trigésima quinta conferencia sobre la incertidumbre en la inteligencia artificial , AUAI Press, pag. 162.
36. Scott, SL (2010), "Una mirada bayesiana moderna al bandido de múltiples brazos", Modelos estocásticos aplicados en los negocios y la industria , 26 (2): 639–658, doi :10.1002/asmb.874, S2CID  573750
37. Olivier Chapelle; Lihong Li (2011), "Una evaluación empírica del muestreo de Thompson", Avances en sistemas de procesamiento de información neuronal , Curran Associates, 24 : 2249–2257
38. Langford, Juan; Zhang, Tong (2008), "El algoritmo codicioso de época para bandidos contextuales con múltiples brazos", Avances en sistemas de procesamiento de información neuronal , vol. 20, Curran Associates, Inc., págs. 817–824
39. Li Hong Li; Wei Chu; John Langford; Robert E. Schapire (2010), "Un enfoque de bandido contextual para la recomendación personalizada de artículos de noticias", Actas de la 19ª conferencia internacional sobre la World Wide Web , págs. 661–670, arXiv : 1003.0146 , Bibcode : 2010arXiv1003.0146L, doi : 10.1145/1772690.1772758, ISBN 9781605587998, S2CID  207178795
40. Wei Chu; Li Hong Li; Lev Reyzin; Robert E. Schapire (2011), "Bandidos contextuales con funciones de pago lineal" (PDF) , Actas de la 14ª Conferencia Internacional sobre Inteligencia Artificial y Estadística (AISTATS) : 208–214
41. Auer, P. (2000). "Uso de límites superiores de confianza para el aprendizaje en línea". Actas del 41º Simposio Anual sobre Fundamentos de la Informática . Computación IEEE. Soc. págs. 270–279. doi :10.1109/sfcs.2000.892116. ISBN 978-0769508504. S2CID  28713091.
42. Hong, Tzung-Pei; Canción, Wei-Ping; Chiu, Chu-Tien (noviembre de 2011). "Agrupación de atributos compuestos evolutivos". 2011 Congreso Internacional sobre Tecnologías y Aplicaciones de la Inteligencia Artificial . IEEE. págs. 305–308. doi :10.1109/taai.2011.59. ISBN 9781457721748. S2CID  14125100.
43. 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
44. Slivkins, Aleksandrs (2011), Bandidos contextuales con información de similitud. (PDF) , Conferencia sobre Teoría del Aprendizaje, COLT 2011
45. Perchet, Vianney; Rigollet, Philippe (2013), "El problema de los bandidos de múltiples brazos con covariables", Annals of Statistics , 41 (2): 693–721, arXiv : 1110.6084 , doi :10.1214/13-aos1101, S2CID  14258665
46. Sara Filippi; Olivier Cappé; Aurélien Garivier; Csaba Szepesvári (2010), "Bandidos paramétricos: el caso lineal generalizado", Avances en los sistemas de procesamiento de información neuronal , Curran Associates, 23 : 586–594
47. Li Hong 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
48. Kwang-Sung Jun; Aniruddha Bhargava; Robert D. Nowak; Rebecca Willett (2017), "Bandidos lineales generalizados escalables: computación en línea y hashing", Avances en sistemas de procesamiento de información neuronal , Curran Associates, 30 : 99–109, arXiv : 1706.00136 , Bibcode : 2017arXiv170600136J
49. Branislav Kveton; Manzil Zaheer; Csaba Szepesvári; Li Hong 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
50. Michal Valko; Nathan Korda; Rémi Munos; Ilias Flaounas; Nello Cristianini (2013), Análisis en tiempo finito de bandidos contextuales kernelizados , 29.ª Conferencia sobre incertidumbre en inteligencia artificial (UAI 2013) y (JFPDA 2013)., arXiv : 1309.6869 , Bibcode : 2013arXiv1309.6869V
51. Féraud, Raphaël; Allesiardo, Robin; Urvoy, Tanguy; Clérot, Fabrice (2016). "Bosque aleatorio para el problema contextual de los bandidos". Aistats : 93-101. Archivado desde el original el 10 de agosto de 2016 . Consultado el 10 de junio de 2016 .
52. Alekh Agarwal; Daniel J. Hsu; Satyen Kale; John Langford; Li Hong 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
53. Badanidiyuru, A.; Langford, J.; Slivkins, A. (2014), "Bandidos contextuales ingeniosos" (PDF) , Actas de la conferencia sobre teoría del aprendizaje (COLT)^{[ enlace muerto permanente ]}
54. 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) , Curran Associates, 28 : 433–441, arXiv : 1504.06937 , Bibcode : 2015arXiv150406937W
55. Burtini, Giuseppe, Jason Loeppky y Ramon Lawrence. "Un estudio sobre el diseño de experimentos en línea con el bandido estocástico de múltiples brazos". Preimpresión de arXiv arXiv : 1510.00757 (2015).
56. Seldin, Y., Szepesvári, C., Auer, P. y Abbasi-Yadkori, Y., diciembre de 2012. Evaluación y Análisis del Desempeño del Algoritmo EXP3 en Ambientes Estocásticos. En EWRL (págs. 103-116).
57. Hutter, M. y Polonia, J., 2005. Predicción adaptativa en línea siguiendo al líder perturbado. Journal of Machine Learning Research, 6 (abril), páginas 639–660.
58. Agrawal, Rajeev. El problema de los bandidos armados del Continuum. SIAM J. de Control y Optimización. 1995.
59. Besbes, O.; Gur, Y.; Zeevi, A. Problema estocástico de bandidos con múltiples brazos con recompensas no estacionarias. En Actas de los avances en sistemas de procesamiento de información neuronal, Montreal, QC, Canadá, 8 a 13 de diciembre de 2014; págs. 199–207<https://proceedings.neurips.cc/paper/2014/file/903ce9225fca3e988c2af215d4e544d3-Paper.pdf>
60. UCB con descuento, Levente Kocsis, Csaba Szepesvári, 2006
61. Sobre políticas de límite superior de confianza para problemas de bandidos no estacionarios, Garivier y Moulines, 2008 <https://arxiv.org/abs/0805.3415>
62. Cavenaghi, E.; Sottocornola, G.; Estela, F.; Zanker, M. Bandido no estacionario con múltiples brazos: evaluación empírica de un nuevo concepto de algoritmo de detección de deriva. Entropía 2021, 23, 380. <https://doi.org/10.3390/e23030380>
63. Mejora de los experimentos de marketing online con bandidos a la deriva con múltiples brazos, Giuseppe Burtini, Jason Loeppky, Ramon Lawrence, 2015 <http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=Dx2xXEB0PJE=&t=1>
64. 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 
65. Yue, Yisong; Joachims, Thorsten (2011), "Beat the Mean Bandit", Actas de ICML'11
66. Urvoy, Tanguy; Clérot, Fabrice; Féraud, Raphaël; Naamane, Sami (2013), "Generic Exploration and K-armed Voting Bandits" (PDF) , Actas de la 30.ª Conferencia Internacional sobre Aprendizaje Automático (ICML-13) , archivada desde el original (PDF) el 2 de octubre de 2016 , recuperado el 29 de abril de 2016
67. Zoghi, Masrour; Whiteson, Shimón; Munos, Remi; Rijke, Maarten D (2014), "Confianza superior relativa ligada al problema de los bandidos armados en duelo de $K$" (PDF) , Actas de la 31ª Conferencia Internacional sobre Aprendizaje Automático (ICML-14) , archivada desde el original (PDF) el 26 de marzo de 2016 , consultado el 27 de abril de 2016
68. Gajane, Pratik; Urvoy, Tanguy; Clérot, Fabrice (2015), "Un algoritmo de pesaje exponencial relativo para bandidos de duelo basados ​​en utilidades adversarias" (PDF) , Actas de la 32.ª Conferencia internacional sobre aprendizaje automático (ICML-15) , archivada desde el original (PDF) en 2015. 8 de septiembre , consultado el 29 de abril de 2016.
69. Zoghi, Masrour; Karnin, Zohar S; Whiteson, Shimón; Rijke, Maarten D (2015), "Copeland Dueling Bandits", Avances en sistemas de procesamiento de información neuronal, NIPS'15 , arXiv : 1506.00312 , Bibcode : 2015arXiv150600312Z
70. Komiyama, Junpei; Honda, Junya; Kashima, Hisashi; Nakagawa, Hiroshi (2015), "Lamento el límite inferior y el algoritmo óptimo en el problema de los bandidos en duelo" (PDF) , Actas de la 28.ª Conferencia sobre teoría del aprendizaje , archivado desde el original (PDF) el 17 de junio de 2016 , consultado el 4 de junio de 2016. -27
71. Wu, Huasen; Liu, Xin (2016), "Double Thompson Sampling for Dueling Bandits", 30ª Conferencia Anual sobre Sistemas de Procesamiento de Información Neural (NIPS) , arXiv : 1604.07101 , Bibcode : 2016arXiv160407101W
72. Cesa-Bianchi, Nicolo; Gentil, Claudio; Zappella, Giovanni (2013), Una pandilla de bandidos , Avances en sistemas de procesamiento de información neuronal 26, NIPS 2013, arXiv : 1306.0811
73. Gentil, Claudio; Li, Shuai; Zappella, Giovanni (2014), "Agrupación 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
74. Li, Shuai; Alexandros, Karatzoglou; Gentile, Claudio (2016), "Collaborative Filtering Bandits", 39ª Conferencia Internacional ACM SIGIR sobre Recuperación de Información (SIGIR 2016) , arXiv : 1502.03473 , Bibcode : 2015arXiv150203473L
75. Gai, Y.; Krishnamachari, B.; Jain, R. (2010), "Aprendizaje de asignaciones de canales multiusuario en redes de radio cognitivas: una formulación combinatoria de bandidos con múltiples brazos", Simposio IEEE de 2010 sobre nuevas fronteras en el espectro dinámico (PDF) , págs.^{[ enlace muerto ]}
76. Chen, Wei; Wang, Yajun; Yuan, Yang (2013), "Bandido combinatorio de armas múltiples: marco general y aplicaciones", Actas de la 30ª Conferencia Internacional sobre Aprendizaje Automático (ICML 2013) (PDF) , págs. 151-159, archivado desde el original (PDF) el 19 de noviembre de 2016 , consultado el 14 de junio de 2019
77. Santiago Ontañón (2017), "Bandidos combinatorios de armas múltiples 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

Otras lecturas

• 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 índice para problemas de bandidos con descuento con restricciones de disponibilidad", Avances en probabilidad aplicada , 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 Sociedad Matemática Estadounidense , 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 contextual de los bandidos", Procesamiento de información neuronal - 21ª Conferencia Internacional, ICONIP 2014, Malaisia, 3 al 6 de noviembre de 2014, Actas , Apuntes de conferencias en Ciencias de la Computación, 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, S2CID  14155718.

• Weber, Richard (1992), "Sobre el índice de Gittins para bandidos armados", Annals of Applied Probability , 2 (4): 1024–1033, doi : 10.1214/aoap/1177005588 , JSTOR  2959678.
• Katehakis, M .; C. Derman (1986), "Cálculo de reglas de asignación secuencial óptima en ensayos clínicos", Procedimientos estadísticos adaptativos y temas relacionados , Notas de conferencias del Instituto de Estadística Matemática - Serie de monografías, 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 de los bandidos multiarmados: 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 bandit que admite políticas contextuales paramétricas y no paramétricas libres de contexto con capacidad integrada de paralelización y simulación.
• 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 bandidos multiarmados contextuales y sin 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 del Estado único.
• 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 equilibrio entre explotación y exploración.
• Algoritmos Bandit versus pruebas AB.
• S. Bubeck y N. Cesa-Bianchi Una encuesta sobre bandidos.
• Una encuesta sobre bandidos contextuales con múltiples armas, 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 las estrategias de equilibrio de exploración/explotación de Epsilon-greedy, Thompson sampling y Upper Confidence Bound.