Hispanopedia Wiki
Articulo de referencia

Bandido de múltiples brazos

Una hilera de máquinas tragamonedas en Las Vegas. En teoría de la probabilidad y aprendizaje automático , el problema del bandido multi-brazo ( a veces llamado problema del band...

Hispanopedia WikiContenido en espanolLectura gratuita
Una hilera de máquinas tragamonedas en Las Vegas.

En teoría de la probabilidad y aprendizaje automático , el problema del bandido multi-brazo ( a veces llamado problema del bandido K- [ 1 ] o N -brazo [ 2 ] ) recibe su nombre al imaginar a un jugador en una fila de máquinas tragamonedas (a veces conocidas como " bandidos de un 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 una máquina diferente. [ 3 ]

En términos más generales, se trata de un problema en el que quien toma las decisiones selecciona iterativamente una de varias opciones fijas (es decir, armas o acciones) cuando las propiedades de cada opción se conocen solo parcialmente en el momento de la asignación y pueden comprenderse mejor con el paso del tiempo. Un aspecto fundamental de los problemas de bandidos es que elegir un arma no afecta las propiedades de esa arma ni de las demás. [ 4 ]

Ejemplos del problema del bandido multi-brazo incluyen la tarea de asignar iterativamente un conjunto fijo y limitado de recursos entre opciones (alternativas) en competencia de manera que se minimice el arrepentimiento . [ 5 ] [ 6 ] Una configuración alternativa notable para el problema del bandido multi-brazo incluye el problema de " identificación del mejor brazo (BAI) ", donde el objetivo es identificar la mejor opción al final de un número finito de rondas. [ 7 ]

El problema del bandido multi-brazo 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 bandidos no afectan la distribución de recompensas de los brazos.

El problema del bandido multi-brazo también se enmarca 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 tiradas de palanca. [ 5 ] [ 6 ] La compensación crucial a la que se enfrenta el jugador en cada ensayo 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 compensación entre exploración y explotación también se presenta en el aprendizaje automático. En la práctica, los bandidos multi-brazos se han utilizado para modelar problemas como la gestión de proyectos de investigación en una gran organización, como una fundación científica o una empresa farmacéutica . [ 5 ] [ 6 ] En las primeras versiones del problema, el jugador comienza sin ningún conocimiento inicial sobre las máquinas.

En 1952, Herbert Robbins , consciente de la importancia del problema, construyó estrategias convergentes de selección de población 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 esperada descontada. [ 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 multi-brazo modela un agente que intenta simultáneamente adquirir nuevos conocimientos (denominado "exploración") y optimizar sus decisiones basándose en los conocimientos existentes (denominado "explotación"). El agente intenta equilibrar estas tareas contrapuestas para maximizar su valor total durante el período de tiempo considerado. Existen numerosas aplicaciones prácticas del modelo del bandido, por ejemplo:

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 dicho conocimiento. Esto se conoce como la disyuntiva 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 el beneficio de cada posibilidad. [ 14 ]

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

La versión del problema que se analiza habitualmente en la actualidad fue formulada por Herbert Robbins en 1952.

El modelo del bandido multi-brazo

El problema del bandido multi-brazo (abreviado: bandido o MAB) puede considerarse como un conjunto de distribuciones reales.B={R1,…,RK}{\displaystyle B=\{R_{1},\dots ,R_{K}\}}, cada distribución está asociada con las recompensas entregadas por uno de losK∈norte+{\displaystyle K\in \mathbb {N} ^{+}}palancas. Dejaμ1,…,μK{\displaystyle \mu _{1},\dots ,\mu _{K}}sean los valores medios asociados con estas distribuciones de recompensa. El jugador acciona iterativamente una palanca por ronda y observa la recompensa asociada. El objetivo es maximizar la suma de las recompensas recolectadas. El horizonteH{\displaystyle H}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ρ{\displaystyle \rho }despuésT{\displaystyle T}Las rondas se definen como la diferencia esperada entre la suma de recompensas asociada a una estrategia óptima y la suma de las recompensas recolectadas:

ρ=Tμ∗−∑t=1Tr^t{\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}},

dóndeμ∗{\displaystyle \mu ^{*}}es la media de recompensa máxima,μ∗=máximok{μk}{\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}, yr^t{\displaystyle {\widehat {r}}_{t}}es la recompensa en rondat{\displaystyle t}.

Una estrategia de arrepentimiento cero es una estrategia cuyo arrepentimiento promedio por ronda es...ρ/T{\displaystyle \rho /T}tiende a cero con probabilidad 1 cuando el número de rondas jugadas tiende a infinito. [ 16 ] Intuitivamente, las estrategias de arrepentimiento cero tienen garantizada la convergencia a una estrategia óptima (no necesariamente única) si se juegan suficientes rondas.

Variaciones

Una formulación común es el bandido multi-brazo binario o bandido multi-brazo de Bernoulli, que otorga una recompensa de uno con probabilidadpag{\displaystyle p}y, en caso contrario, una recompensa de cero.

Otra formulación del problema del bandido multi-brazos considera que cada brazo representa una máquina de Markov independiente. Cada vez que se juega un brazo, el estado de esa máquina avanza a uno nuevo, elegido según 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 denominada "problema del bandido inquieto", los estados de los brazos no jugados también pueden evolucionar con el tiempo. [ 17 ] También se ha analizado el caso de sistemas donde el número de opciones (sobre qué brazo jugar) aumenta con el tiempo. [ 18 ]

Investigadores de ciencias de la computación han estudiado bandidos multi-brazos bajo supuestos de peor caso, 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 ] .

Mejor identificación del brazo

Una variación importante del problema clásico de minimización del arrepentimiento en los bandidos multi-brazos es la identificación del mejor brazo (BAI), [ 20 ] también conocida 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 con la mayor recompensa esperada. Un algoritmo en este contexto se caracteriza por una regla de muestreo , una regla de decisión y una regla de parada , descritas a continuación:

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

En BAI existen dos entornos predominantes:

Configuración de presupuesto fijo: Dado un horizonte temporalT≥1{\displaystyle T\geq 1}El objetivo es identificar el brazo con la mayor recompensa esperada.a⋆∈arg⁡máximokμk{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}minimizando la probabilidad de errorδ{\displaystyle \delta }.

Configuración de confianza fija: Dado un nivel de confianzaδ∈(0,1){\displaystyle \delta \in (0,1)}El objetivo es identificar el brazo con la mayor recompensa esperada.a⋆∈arg⁡máximokμk{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}con la menor cantidad posible de ensayos y con probabilidad de errorPAG(a^τ≠a⋆)≤δ{\displaystyle \mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta }.

Por ejemplo, utilizando una regla de decisión , podríamos usarmetro1{\displaystyle m_{1}}dóndemetro{\displaystyle m}es la máquina n.º 1 (puede usar una variable diferente respectivamente) y1{\displaystyle 1}es la cantidad por cada vez que se intenta tirar de la palanca, donde∫∑metro1,metro2,(...)=METRO{\displaystyle \int \sum m_{1},m_{2},(...)=M}, identificarMETRO{\displaystyle M}como la suma de cada intentometro1+metro2{\displaystyle m_{1}+m_{2}}, (...) según sea necesario, y a partir de ahí puede obtener una razón, suma o media como probabilidad cuantitativa y muestrear su formulación para cada ranura.

También puedes hacerlo∫∑k∝inorte−(nortej){\displaystyle \int \sum _ {k\propto _ {i}}^{N}-(n_ {j})}dóndemetro1+metro2{\displaystyle m1+m2}cada uno es igual a una ranura de máquina única,incógnita,y{\displaystyle x,y}es la cantidad cada vez que se acciona la palanca,norte{\displaystyle N}es la suma de(metro1incógnita,y)+(metro2incógnita,y)(...){\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)},k{\displaystyle k}sería la cantidad total disponible en su posesión,k{\displaystyle k}es relativo anorte{\displaystyle N}dóndenorte=norte(nortea,b),(norte1a,b),(norte2a,b){\displaystyle N=n(n_{a},b),(n1_{a},b),(n2_{a},b)}reducidonortej{\displaystyle n_{j}}como la suma de cada ganancia o pérdida dea,b{\displaystyle a,b}(por ejemplo, supongamos que tiene 100$ que se define comonorte{\displaystyle n}, ya{\displaystyle a}sería una ganancia,b{\displaystyle b}es igual a una pérdida. A partir de ahí obtienes tus resultados, ya sean positivos o negativos, para sumar.norte{\displaystyle N}con su propia regla específica) yi{\displaystyle i}como el máximo que está dispuesto a gastar. Es posible expresar esta construcción utilizando una combinación de múltiples formulaciones algebraicas, como se mencionó anteriormente, donde puede limitar conT{\displaystyle T}para, o en el tiempo, etc.

Estrategias de bandidos

Un avance importante fue la construcción de estrategias o políticas óptimas de selección de población (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 "Reglas de asignación adaptativa asintóticamente eficientes", Lai y Robbins [ 21 ] (siguiendo los trabajos 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 (hacia 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 demostración principal para el caso de poblaciones normales con varianzas conocidas. El siguiente progreso notable fue obtenido por Burnetas y Katehakis en el artículo "Políticas adaptativas óptimas para problemas de asignación secuencial", [ 23 ] donde se construyeron políticas basadas en índices con tasa de convergencia uniformemente máxima, 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 los resultados siguen distribuciones univariadas discretas arbitrarias (es decir, no paramétricas).

Más adelante, en "Políticas adaptativas óptimas para procesos de decisión de Markov" [ 24 ], Burnetas y Katehakis estudiaron el modelo mucho más amplio de procesos de decisión de Markov bajo 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 de horizonte finito bajo supuestos suficientes de espacios de estado-acción finitos 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 optimalidad de recompensa promedio estimada. Estas inflaciones han sido denominadas recientemente 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 multi-brazos de Bernoulli, Pilarski et al. [ 29 ] estudiaron métodos de cálculo para derivar soluciones totalmente óptimas (no solo asintóticamente) utilizando programación dinámica en el artículo "Política óptima para bandidos de Bernoulli: cálculo y calibre del algoritmo" [ 29 ] . Mediante esquemas de indexación, tablas de búsqueda y otras técnicas, este trabajo proporcionó soluciones óptimas prácticamente aplicables para bandidos de Bernoulli siempre que los horizontes temporales y el número de brazos no fueran excesivamente grandes. Pilarski et al. [ 30 ] extendieron posteriormente este trabajo en "Bandidos de Bernoulli con recompensa retardada: política óptima y meta-algoritmo predictivo PARDI" [ 30 ] para crear un método de determinación de la política óptima para bandidos de Bernoulli cuando las recompensas pueden no revelarse inmediatamente después de una decisión y pueden retrasarse. Este método se basa en el cálculo de los valores esperados de los resultados de recompensa que aún no se han revelado y en la actualización de las 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 estriado ventral codifica los valores derivados de estas políticas y puede utilizarse 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 más adelante). Esto sugiere que las soluciones óptimas para problemas de bandidos de múltiples brazos son biológicamente plausibles, a pesar de ser computacionalmente exigentes. [ 32 ]

Soluciones aproximadas

Existen numerosas estrategias que proporcionan una solución aproximada al problema del bandido, y que pueden clasificarse en las cuatro grandes categorías que se detallan a continuación.

Estrategias semiuniformes

Las estrategias semiuniformes fueron las primeras (y más sencillas) descubiertas para resolver aproximadamente el problema del bandido. Todas estas estrategias tienen en común un comportamiento voraz , donde siempre se acciona la mejor palanca (basándose en observaciones previas), excepto cuando se realiza una acción aleatoria (uniforme).

  • Estrategia épsilon-greedy : [ 33 ] Se selecciona la mejor palanca para una proporción1−ϵ{\displaystyle 1-\epsilon }de los ensayos, y se selecciona una palanca al azar (con probabilidad uniforme) para una proporciónϵ{\displaystyle \epsilon }Un valor típico de un parámetro podría ser:ϵ=0.1{\displaystyle \epsilon =0.1}, pero esto puede variar ampliamente dependiendo de las circunstancias y las preferencias.
  • Estrategia épsilon-primero : Una fase de exploración pura es seguida por una fase de explotación pura. Paranorte{\displaystyle N}En total, la fase de exploración ocupaϵnorte{\displaystyle \epsilon N}ensayos y la fase de explotación(1−ϵ)norte{\displaystyle (1-\epsilon )N}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.
  • Estrategia decreciente de épsilon : similar a la estrategia épsilon-codiciosa, excepto que el valor deϵ{\displaystyle \epsilon }disminuye a medida que avanza el experimento, lo que da como resultado un comportamiento altamente exploratorio al principio y un comportamiento altamente explotador al final.
  • Estrategia adaptativa epsilon-greedy basada en diferencias de valor (VDBE) : Similar a la estrategia epsilon-decreciente, excepto que epsilon se reduce en función del progreso del aprendizaje en lugar de la sintonización manual (Tokic, 2010). [ 34 ] Las fluctuaciones altas en las estimaciones de valor conducen a un epsilon alto (alta exploración, baja explotación); las fluctuaciones bajas a un epsilon bajo (baja exploración, alta explotación). Se pueden lograr mejoras adicionales mediante una selección de acciones ponderada softmax en el caso de acciones exploratorias (Tokic y Palm, 2011). [ 35 ]
  • Estrategia adaptativa epsilon-greedy basada en conjuntos bayesianos (Epsilon-BMC) : Una estrategia de adaptación epsilon adaptativa para el aprendizaje por refuerzo similar a VBDE, con garantías de convergencia monótona. En este marco, el parámetro epsilon se considera como la esperanza 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). 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 epsilon 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 correspondencia de probabilidades

Las estrategias de igualación de probabilidad reflejan la idea de que el número de tiradas para una palanca dada debe coincidir con su probabilidad real de ser la palanca óptima. Las estrategias de igualación de probabilidad también se conocen como muestreo de Thompson o bandidos bayesianos, [ 37 ] [ 38 ] y son sorprendentemente fáciles de implementar si se puede muestrear a partir de la distribución posterior para el valor medio de cada alternativa.

Las estrategias de igualación de probabilidades también admiten soluciones a los llamados problemas de bandidos contextuales. [ 37 ]

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 acciona la palanca de mayor precio.

bandido contextual

Una generalización útil del problema del bandido multi-brazo es el bandido multi-brazo contextual. En cada iteración, un agente aún debe elegir entre brazos, pero también ve un vector de características d-dimensional, el vector de contexto que puede usar junto con las recompensas de los brazos jugados en el pasado para tomar la decisión sobre qué brazo jugar. Con el tiempo, el objetivo del aprendiz es recopilar suficiente información sobre cómo se relacionan los vectores de contexto y las recompensas entre sí, 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 numerosas estrategias que proporcionan una solución aproximada al problema del bandido contextual, y que pueden agruparse en dos grandes categorías que se detallan a continuación.

bandidos lineales en línea

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 parte constante. Los refinamientos sucesivos de la partición del espacio de contexto se programan o eligen de forma adaptativa. [ 42 ] [ 43 ] [ 44 ]
  • Algoritmos lineales generalizados : La distribución de recompensas sigue un modelo lineal generalizado , una extensión de los bandidos lineales. [ 45 ] [ 46 ] [ 47 ] [ 48 ]
  • Algoritmo KernelUCB : una versión no lineal kernelizada de LinUCB, con implementación eficiente y análisis de tiempo finito. [ 49 ]
  • Algoritmo Bandit Forest : se construye un bosque aleatorio y se analiza con respecto al bosque aleatorio construido conociendo la distribución conjunta de contextos y recompensas. [ 50 ]
  • Algoritmo basado en oráculo : El algoritmo reduce el problema del bandido contextual a una serie de problemas de aprendizaje supervisado y no se basa en la suposición típica de realizabilidad en la función de recompensa. [ 51 ]

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 multi-brazo. A. Badanidiyuru et al. [ 52 ] estudiaron por primera vez bandidos contextuales con restricciones presupuestarias, también conocidos como bandidos contextuales con recursos, y muestran que unO(T){\displaystyle O({\sqrt {T}})}El arrepentimiento es alcanzable. Sin embargo, su trabajo se centra en un conjunto finito de políticas y el algoritmo es computacionalmente ineficiente.

Marco de UCB-ALP para bandidos contextuales restringidos

En [ 53 ] se propone un algoritmo simple con arrepentimiento logarítmico.

  • Algoritmo UCB-ALP : La estructura de UCB-ALP se muestra en la figura de la derecha. UCB-ALP es un algoritmo sencillo que combina el método UCB con un algoritmo de Programación Lineal Adaptativa (ALP) y puede implementarse fácilmente en sistemas prácticos. Es el primer trabajo que muestra cómo lograr un arrepentimiento logarítmico en problemas de bandidos contextuales con restricciones. Si bien [ 53 ] se centra en un caso especial con una única restricción presupuestaria y un costo fijo, los resultados aportan información valiosa para el diseño y análisis de algoritmos para problemas de bandidos contextuales con restricciones más generales.

bandido adversario

Otra variante del problema del bandido multi-brazo se denomina 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 sólidas del problema del bandido [ 54 ] , ya que elimina todos los supuestos sobre la distribución y una solución al problema del bandido adversario es una solución generalizada a los problemas de bandido más específicos.

Ejemplo: Dilema del prisionero iterado

Un ejemplo que se suele considerar para los bandidos adversariales es el dilema del prisionero iterado . En este ejemplo, cada adversario tiene dos opciones: negar o confesar. Los algoritmos estándar de bandidos estocásticos no funcionan bien con estas iteraciones. Por ejemplo, si el oponente coopera en las primeras 100 rondas, traiciona en las siguientes 200, luego coopera en las 300 siguientes, etc., algoritmos como UCB no podrán reaccionar con rapidez a estos cambios. Esto se debe a que, a partir de cierto punto, rara vez se eligen opciones subóptimas para limitar la exploración y centrarse en la explotación. Cuando el entorno cambia, el algoritmo es incapaz de adaptarse o incluso puede que no detecte el cambio.

Soluciones aproximadas

Exp3

Fuente: [ 55 ]

EXP3 es un algoritmo popular para problemas de bandidos multi-armados adversariales, propuesto y analizado en este contexto por Auer et al. [2002b]. Recientemente, ha aumentado el interés en el rendimiento de este algoritmo en el entorno estocástico, debido a sus nuevas aplicaciones a problemas de bandidos multi-armados estocásticos con información adicional [Seldin et al., 2011] y a problemas de bandidos multi-armados en el entorno mixto estocástico-adversario [Bubeck y Slivkins, 2012]. Este artículo presenta 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 un entorno estocástico.

Algoritmo
Parámetros: Realγ∈(0,1]{\displaystyle \gamma \en (0,1]}Inicialización:ωi(1)=1{\displaystyle \omega _ {i}(1)=1}parai=1,...,K{\displaystyle i=1,...,K}Para cada t = 1, 2, ..., T 1. Conjuntopagi(t)=(1−γ)ωi(t)∑j=1Kωj(t)+γK{\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}      i=1,...,K{\displaystyle i=1,...,K} 2. Dibujarit{\displaystyle i_{t}}aleatoriamente según las probabilidadespag1(t),...,pagK(t){\displaystyle p_{1}(t),...,p_{K}(t)} 3. Reciba una recompensa.incógnitait(t)∈[0,1]{\displaystyle x_{i_{t}}(t)\in [0,1]} 4. Paraj=1,...,K{\displaystyle j=1,...,K}colocar:     incógnita^j(t)={incógnitaj(t)/pagj(t)si j=it0,de lo contrario{\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{si }}j=i_{t}\\0,&{\text{en otro caso}}\end{cases}}}    ωj(t+1)=ωj(t)exp⁡(γincógnita^j(t)/K){\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(1−γ){\displaystyle (1-\gamma )}Prefiere brazos con mayor peso (explotar), elige con probabilidadγ{\displaystyle \gamma }para explorar de forma uniforme y aleatoria. Tras recibir las recompensas, se actualizan los pesos. El crecimiento exponencial aumenta significativamente el peso de los brazos buenos.

Análisis de arrepentimiento

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

Algoritmo de seguimiento del líder perturbado (FPL)

Algoritmo
Parámetros: Realη{\displaystyle \eta }Inicialización:∀i:Ri(1)=0{\displaystyle \forall i:R_{i}(1)=0}Para cada t = 1,2,...,T 1. Para cada brazo, generar un ruido aleatorio a partir de una distribución exponencial.∀i:Zi(t)∼miincógnitapag(η){\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )} 2. Tirar del brazoI(t){\displaystyle I(t)}:I(t)=argramomáximoi{Ri(t)+Zi(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:RI(t)(t+1)=RI(t)(t)+incógnitaI(t)(t){\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)} El resto permanece igual
Explicación

Seguimos el brazo que creemos que tiene el mejor rendimiento hasta ahora, añadiéndole ruido exponencial para realizar una exploración. [ 56 ]

Exp3 vs 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 variableK{\displaystyle K}. En el caso de brazos infinitos, introducido por Agrawal (1995), [ 57 ] los "brazos" son una variable continua enK{\displaystyle K}dimensiones.

Bandido no estacionario

Este marco se refiere al problema del bandido multi-brazo en un entorno no estacionario (es decir, en presencia de deriva conceptual ). En el entorno no estacionario, se supone que la recompensa esperada para un brazok{\displaystyle k}puede cambiar en cada paso de tiempot∈T{\displaystyle t\in {\mathcal {T}}}:μt−1k≠μtk{\displaystyle \mu _{t-1}^{k}\neq \mu _{t}^{k}}. De este modo,μtk{\displaystyle \mu _{t}^{k}}ya no representa toda la secuencia de recompensas esperadas (estacionarias) para el brazok{\displaystyle k}. En cambio,μk{\displaystyle \mu ^{k}}denota la secuencia de recompensas esperadas para el brazok{\displaystyle k}, definido comoμk={μtk}t=1T{\displaystyle \mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}}. [ 58 ]

Un oráculo dinámico representa la política óptima que se compara con otras políticas en el entorno no estacionario. El oráculo dinámico optimiza la recompensa esperada en cada paso.t∈T{\displaystyle t\in {\mathcal {T}}}Al seleccionar siempre el mejor brazo, con la recompensa esperada deμt∗{\displaystyle \mu _{t}^{*}}Por lo tanto, la recompensa esperada acumuladaD(T){\displaystyle {\mathcal {D}}(T)}para el oráculo dinámico en el paso de tiempo finalT{\displaystyle T}se define como:

D(T)=∑t=1Tμt∗.{\displaystyle {\mathcal {D}}(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}.}

De ahí el arrepentimientoρπ(T){\displaystyle \rho ^{\pi }(T)}para políticaπ{\displaystyle \pi }se calcula como la diferencia entreD(T){\displaystyle {\mathcal {D}}(T)}y la recompensa esperada acumulada en el pasoT{\displaystyle T}para políticaπ{\displaystyle \pi }:

ρπ(T)=∑t=1Tμt∗−miπμ[∑t=1Trt]=D(T)−miπμ[∑t=1Trt].{\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 problemas de bandidos donde el modelo subyacente puede cambiar durante el juego. Se presentaron varios algoritmos para abordar este caso, incluyendo UCB con descuento [ 59 ] y UCB con ventana deslizante [ 60 ] . Un enfoque similar basado en el algoritmo de muestreo de Thompson es el muestreo de Thompson con ventana deslizante con descuento (f-dsw TS) [ 61 ] 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 conceptual 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 casos no estacionarios conocidos como desconocidos [ 62 ] .

Otras variantes

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

Bandido duelista

La variante del bandido duelista fue introducida por Yue et al. (2012) [ 63 ] para modelar la disyuntiva entre exploración y explotación en la retroalimentación relativa. En esta variante, el jugador puede accionar dos palancas simultáneamente, pero solo recibe una retroalimentación binaria que indica qué palanca proporcionó la mejor recompensa. La dificultad de este problema radica en que el jugador no puede observar directamente la recompensa de sus acciones. Los primeros algoritmos para este problema fueron InterleaveFiltering [ 63 ] y Beat-The-Mean [ 64 ] . La retroalimentación relativa de los bandidos duelistas también puede generar paradojas de votación . Una solución consiste en tomar como referencia al ganador de Condorcet [ 65 ] .

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

Bandido colaborador

Los enfoques que utilizan múltiples bandidos que cooperan compartiendo conocimiento para optimizar mejor su rendimiento comenzaron en 2013 con "A Gang of Bandits" [ 71 ] , 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 con el trabajo sobre el algoritmo CLUB [ 72 ] . A partir 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 y Karatzoglou y Gentile (SIGIR 2016) [ 73 ] , donde los métodos clásicos de filtrado colaborativo y filtrado basado en contenido intentan aprender un modelo de recomendación estático a partir de datos de entrenamiento.

bandido combinatorio

El problema del bandido multi-brazo combinatorio (CMAB) [ 74 ] [ 75 ] [ 76 ] surge cuando, en lugar de una única variable discreta para elegir, un agente necesita seleccionar valores para un conjunto de variables. Suponiendo que cada variable es discreta, el número de elecciones posibles por iteración es exponencial con respecto al número de variables. En la literatura se han estudiado diversas configuraciones del CMAB, desde configuraciones donde las variables son binarias [ 75 ] hasta configuraciones más generales donde cada variable puede tomar un conjunto arbitrario de valores. [ 76 ]

Véase también

Referencias

  1. 1 2 Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). "Análisis en tiempo finito del problema del bandido multi-brazo" . Machine Learning . 47 (2/3): 235– 256. doi : 10.1023/A:1013689704352 .
  2. ↑ Katehakis, Michael N.; Veinott, Jr., Arthur F. (1987). "El problema del bandido multi-brazo: descomposición y cálculo". Matemáticas de la investigación operativa . 12 (2): 262– 268. doi : 10.1287/moor.12.2.262 . S2CID 656323 . 
  3. ↑ Weber, Richard (1992), "Sobre el índice de Gittins para bandidos multi-armados", Annals of Applied Probability , 2 (4): 1024– 1033, doi : 10.1214/aoap/1177005588 , JSTOR 2959678 
  4. ↑ Bubeck, Sébastien (2012). "Análisis de arrepentimiento de problemas de bandidos multi-armados estocásticos y no estocásticos". Fundamentos y tendencias en aprendizaje automático . 5 : 1–122 . arXiv : 1204.5721 . doi : 10.1561/2200000024 (inactivo el 30 de marzo de 2026).{{cite journal}}: CS1 maint: DOI inactivo desde marzo de 2026 ( enlace )
  5. 1 2 3 4 Gittins, JC (1989), Índices de asignación de bandidos multi-armados , Serie Wiley-Interscience en Sistemas y Optimización, Chichester: John Wiley & Sons, Ltd., ISBN 978-0-471-92059-5
  6. 1 2 3 4 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
  7. ↑ Soare, Marta; Lazarico, Alejandro; Munos, Rémi (2014). "Identificación del mejor brazo en Linear Bandits". arXiv : 1409.6110 [ cs.LG ].
  8. ↑ Robbins, H. (1952). "Algunos aspectos del diseño secuencial de experimentos" . Boletín de la Sociedad Matemática Americana . 58 (5): 527– 535. Bibcode : 1952BAMaS..58..527R . doi : 10.1090/S0002-9904-1952-09620-8 .
  9. ↑ JC Gittins (1979). "Procesos de bandidos e índices de asignación dinámica". Journal of the 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 aleatorizados e investigación de efectividad comparativa", Proceedings of the National Academy of Sciences , 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 [ cs.LG ].
  13. ↑ Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015), "Portfolio Choices with Orthogonal Bandit Learning" , Actas de las Conferencias Conjuntas Internacionales sobre Inteligencia Artificial (IJCAI2015) , archivado del original el 4 de diciembre de 2021 , consultado el 20 de marzo de 2016.
  14. ↑ Farias, Vivek F; Ritesh, Madan (2011), "El problema irrevocable del bandido multi-brazo", Operations Research , 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. 1 2 Vermorel, Joannes; Mohri, Mehryar (2005), Algoritmos de bandidos multi-brazos y evaluación empírica (PDF) , En Conferencia Europea sobre Aprendizaje Automático, Springer, pp. 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", 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 del bandido multi-brazo 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 (2016). "Identificación óptima del mejor brazo con confianza fija". arXiv : 1602.04589 [ math.ST ].
  21. ↑ Lai, TL; Robbins, H. (1985). "Reglas de asignación adaptativa asintóticamente eficientes" . Advances in Applied Mathematics . 6 (1): 4– 22. Bibcode : 1985AdApM...6....4L . 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" . Advances in Applied Mathematics . 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". Mathematics of Operations Research . 22 (1): 222– 255. doi : 10.1287/moor.22.1.222 .
  25. ↑ Tewari, A.; Bartlett, PL (2008). "La programación lineal optimista produce un arrepentimiento logarítmico para MDP irreducibles" (PDF) . Advances in Neural Information Processing Systems . 20. CiteSeerX 10.1.1.69.5482 . Archivado del 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" . Theoretical Computer Science . 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", Communication, Control, and Computing (Allerton), 48.ª Conferencia Anual de Allerton de 2010 , pp. 115–122
  28. ↑ Honda, J.; Takemura, A. (2011). "Una política asintóticamente óptima para modelos de soporte finito en el problema del bandido multi-brazo". Machine Learning . 85 (3): 361– 391. arXiv : 0905.2776 . doi : 10.1007/s10994-011-5257-4 . S2CID 821462 . 
  29. 1 2 Pilarski, Sebastián; Pilarski, Slawomir; Varró, Dániel (febrero 2021). "Política óptima para los bandidos de Bernoulli: calibre computacional y algorítmico" . Transacciones IEEE sobre Inteligencia Artificial . 2 (1): 2– 17. Bibcode : 2021ITAI....2....2P . doi : 10.1109/TAI.2021.3074122 . ISSN 2691-4581 . S2CID 235475602 .  
  30. 1 2 Pilarski, Sebastian; Pilarski, Slawomir; Varro, Daniel (2021). "Bandidos de Bernoulli con recompensa retardada: 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). "Subsustratos subcorticales de las decisiones de exploración y 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 aprendizaje por refuerzo basada en diferencias de valor" (PDF) , KI 2010: Avances en Inteligencia Artificial , Lecture Notes in Computer Science, vol. 6359, Springer-Verlag, pp. 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, pp. 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 modelo" (PDF) , Actas de la Trigésimo Quinta Conferencia sobre Incertidumbre en Inteligencia Artificial , AUAI Press, pág. 162 .
  37. 1 2 Scott, SL (2010), "Una mirada bayesiana moderna al problema del bandido multi-brazo", Applied Stochastic Models in Business and Industry , 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" , Advances in Neural Information Processing Systems , 24 , Curran Associates: 2249–2257
  39. ↑ Langford, John; Zhang, Tong (2008), "El algoritmo Epoch-Greedy para bandidos multi-armados contextuales" , Advances in Neural Information Processing Systems , vol. 20, Curran Associates, Inc., pp . 817–824  
  40. ↑ 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 . IEEE Comput. Soc. pp. 270–279 . doi : 10.1109/sfcs.2000.892116 . ISBN  978-0-7695-0850-4. S2CID 28713091 . 
  41. ↑ 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  978-1-4577-2174-8. S2CID 14125100 . 
  42. ↑ Rigollet, Philippe; Zeevi, Assaf (2010), Nonparametric Bandits with Covariates , Conferencia sobre Teoría del Aprendizaje, COLT 2010, arXiv : 1003.1630 , Bibcode : 2010arXiv1003.1630R
  43. ↑ Slivkins, Aleksandrs (2011), Bandidos contextuales con información de similitud. (PDF) , Conferencia sobre Teoría del Aprendizaje, COLT 2011
  44. ↑ Perchet, Vianney; Rigollet, Philippe (2013), "El problema del bandido multi-brazo con covariables", Annals of Statistics , 41 (2): 693–721 , arXiv : 1110.6084 , doi : 10.1214/13-aos1101 , S2CID 14258665 
  45. ↑ Sarah Filippi; Olivier Cappé; Aurélien Garivier; Csaba Szepesvári (2010), " Bandidos paramétricos: el caso lineal generalizado" , Advances in Neural Information Processing Systems , 23 , Curran Associates: 586–594
  46. ↑ 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 : 2071–2080 , arXiv : 1703.00048 , Bibcode : 2017arXiv170300048L
  47. ↑ Kwang-Sung Jun; Aniruddha Bhargava; Robert D. Nowak; Rebecca Willett (2017), "Bandidos lineales generalizados escalables: Computación en línea y hashing" , Advances in Neural Information Processing Systems , 30 , Curran Associates: 99–109 , arXiv : 1706.00136 , Bibcode : 2017arXiv170600136J
  48. ↑ 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
  49. ↑ 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
  50. ↑ Féraud, Raphaël; Allesiardo, Robin; Urvoy, Tanguy; Clérot, Fabrice (2016). "Random Forest for the Contextual Bandit Problem" . Aistats : 93–101 . Archivado del original el 10 de agosto de 2016. Consultado el 10 de junio de 2016 .
  51. ↑ Alekh Agarwal; Daniel J. Hsu; Satyen Kale; John Langford; Lihong Li; Robert E. Schapire (2014), "Domando al monstruo: Un algoritmo rápido y sencillo para bandidos contextuales" , Actas de la 31.ª Conferencia Internacional sobre Aprendizaje Automático : 1638–1646 , arXiv : 1402.0555 , Bibcode : 2014arXiv1402.0555A
  52. ↑ Badanidiyuru, Ashwinkumar; Langford, John; Slivkins, Aleksandrs (2014), "Resourceful contextual bandits" , en Balcan, Maria-Florina; Feldman, Vitaly; Szepesvári, Csaba (eds.), Actas de la 27.ª Conferencia sobre Teoría del Aprendizaje, COLT 2014, Barcelona, ​​España, 13-15 de junio de 2014 , JMLR Workshop and Conference Proceedings, vol. 35, JMLR.org, pp. 1109-1134  
  53. 1 2 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
  54. ↑ Burtini, Giuseppe; Loeppky, Jason; Lawrence, Ramon (2015). "Un estudio sobre el diseño de experimentos en línea con el problema del bandido multi-brazo estocástico". arXiv : 1510.00757 [ stat.ML ].
  55. ↑ Seldin, Y., Szepesvári, C., Auer, P. y Abbasi-Yadkori, Y., diciembre de 2012. Evaluación y análisis del rendimiento del algoritmo EXP3 en entornos estocásticos. En EWRL (págs. 103–116).
  56. ↑ Hutter, M. y Poland, J., 2005. Predicción adaptativa en línea siguiendo al líder perturbado . Journal of Machine Learning Research, 6 (abril), pp. 639–660.
  57. ↑ Agrawal, Rajeev. El problema del bandido de brazos continuos. SIAM J. of Control and Optimization. 1995.
  58. ↑ Besbes, O.; Gur, Y.; Zeevi, A. Problema estocástico del bandido multi-brazo con recompensas no estacionarias. En Actas de 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 >
  59. ^ UCB con descuento, Levente Kocsis, Csaba Szepesvári, 2006
  60. ↑ Garivier, Aurélien; Moulines, Eric (2008). "Sobre políticas de límites de confianza superiores para problemas de bandidos no estacionarios". arXiv : 0805.3415 [ math.ST ].
  61. ↑ Cavenaghi, Emanuele; Sottocornola, Gabriele; Stella, Fabio; Zanker, Markus (2021). "Non Stationary Multi-Armed Bandit: Empirical Evaluation of a New Concept Drift-Aware Algorithm" . Entropy . 23 ( 3): 380. Bibcode : 2021Entrp..23..380C . doi : 10.3390/e23030380 . PMC 8004723. PMID 33807028 .  
  62. ↑ Mejora de experimentos de marketing online con algoritmos de bandidos multi-brazos dinámicos, Giuseppe Burtini, Jason Loeppky, Ramon Lawrence, 2015 < http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=Dx2xXEB0PJE=&t=1 >
  63. 1 2 Yue, Yisong; Broder, Josef; Kleinberg, Robert; Joachims, Thorsten (2012), "El problema de los bandidos duelistas de K brazos", Journal of Computer and System Sciences , 78 (5): 1538– 1556, CiteSeerX 10.1.1.162.2764 , doi : 10.1016/j.jcss.2011.12.028 
  64. ↑ Yue, Yisong; Joachims, Thorsten (2011), "Vence al bandido malvado", Actas de ICML'11
  65. ↑ 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) , archivado del original (PDF) el 2 de octubre de 2016 , consultado el 29 de abril de 2016.
  66. ↑ Zoghi, Masrour; Whiteson, Shimon; Munos, Remi; Rijke, Maarten D (2014), "Relative Upper Confidence Bound for the $K$-Armed Dueling Bandit Problem" (PDF) , Actas de la 31.ª Conferencia Internacional sobre Aprendizaje Automático (ICML-14) , archivado del original (PDF) el 26 de marzo de 2016 , consultado el 27 de abril de 2016.
  67. ↑ Gajane, Pratik; Urvoy, Tanguy; Clérot, Fabrice (2015), "Un algoritmo de ponderación exponencial relativa para bandidos duelistas adversarios basados ​​en utilidad" (PDF) , Actas de la 32.ª Conferencia Internacional sobre Aprendizaje Automático (ICML-15) , archivado del original (PDF) el 8 de septiembre de 2015 , consultado el 29 de abril de 2016.
  68. ↑ Zoghi, Masrour; Karnin, Zohar S; Whiteson, Shimon; Rijke, Maarten D (2015), "Copeland Dueling Bandits", Advances in Neural Information Processing Systems, NIPS'15 , arXiv : 1506.00312 , Bibcode : 2015arXiv150600312Z
  69. ↑ Komiyama, Junpei; Honda, Junya; Kashima, Hisashi; Nakagawa, Hiroshi (2015), "Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem" (PDF) , Actas de la 28.ª Conferencia sobre Teoría del Aprendizaje , archivado del original (PDF) el 17 de junio de 2016 , consultado el 27 de abril de 2016.
  70. ↑ Wu, Huasen; Liu, Xin (2016), "Muestreo de Thompson doble para bandidos en duelo", 30.ª Conferencia Anual sobre Sistemas de Procesamiento de Información Neuronal (NIPS) , arXiv : 1604.07101 , Bibcode : 2016arXiv160407101W
  71. ^ 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
  72. ↑ Gentile, Claudio; Li, Shuai; Zappella, Giovanni (2014), "Online Clustering of Bandits", 31.ª Conferencia Internacional sobre Aprendizaje Automático, Journal of Machine Learning Research (ICML 2014) , arXiv : 1401.8257 , Bibcode : 2014arXiv1401.8257G
  73. ↑ 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
  74. ↑ Gai, Yi; Krishnamachari, Bhaskar; Jain, Rahul (abril de 2010), "Aprendizaje de asignaciones de canales multiusuario en redes de radio cognitiva: una formulación combinatoria de bandido multi-armado" (PDF) , Simposio IEEE de 2010 sobre Nuevas Fronteras en Espectro Dinámico (DySPAN) , IEEE, págs. 1-9 , doi : 10.1109/DYSPAN.2010.5457857 , ISBN  978-1-4244-5189-0
  75. 1 2 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) , págs. 151–159 , archivado del original (PDF) el 19 de noviembre de 2016 , consultado el 14 de junio de 2019. 
  76. 1 2 Santiago Ontañón (2017), "Combinatorial Multi-armed Bandits for Real-Time Strategy Games" , Journal of Artificial Intelligence Research , 58 : 665–702 , arXiv : 1710.04805 , Bibcode : 2017arXiv171004805O , doi : 10.1613/jair.5398 , S2CID 8517525 

Lecturas adicionales

  • 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 y restricciones de disponibilidad", Advances in Applied Probability , 40 (2): 377–400 , doi : 10.1239/aap/1214950209.
  • Powell, Warren B. (2007), «Capítulo 10», Programación dinámica aproximada: Resolviendo las maldiciones de la dimensionalidad , Nueva York: John Wiley and Sons, ISBN 978-0-470-17155-4.
  • Robbins, H. (1952), "Algunos aspectos del diseño secuencial de experimentos", Bulletin of the American Mathematical Society , 58 (5): 527– 535, Bibcode : 1952BAMaS..58..527R , doi : 10.1090/S0002-9904-1952-09620-8.
  • Sutton, Richard; Barto, Andrew (1998), Aprendizaje por refuerzo , MIT Press, ISBN 978-0-262-19398-6Archivado del 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, pp. 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 multi-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 óptimas de asignación secuencial en ensayos clínicos", Procedimientos estadísticos adaptativos y temas relacionados , Apuntes de clase 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 del bandido multi-brazo: descomposición y cálculo", Mathematics of Operations Research , 12 (2): 262–268 , doi : 10.1287/moor.12.2.262 , JSTOR 3689689 , S2CID 656323  
  • MABWiser es una implementación de código abierto en Python de estrategias de bandidos que admite políticas contextuales paramétricas, no paramétricas y sin contexto, con capacidad de paralelización y simulación integradas.
  • PyMaBandits , implementación de código abierto de estrategias de bandidos en Python y Matlab.
  • Paquete R de código abierto y contextual que facilita la simulación y evaluación de políticas de bandido multi-brazo tanto contextuales como independientes del contexto.
  • bandit.sourceforge.net Proyecto Bandit , implementación de código abierto de estrategias Bandit.
  • 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 los Bandidos: Algoritmos y Teoría. Parte 1. Parte 2 .
  • El problema del restaurante de Feynman , un ejemplo clásico (con solución conocida) de la disyuntiva entre explotación y exploración.
  • Algoritmos de bandidos frente a pruebas A/B .
  • S. Bubeck y N. Cesa-Bianchi Un estudio sobre bandidos .
  • Un estudio sobre bandidos multi-armados contextuales , un estudio/tutorial sobre bandidos contextuales.
  • Entrada de blog sobre estrategias de bandidos multi-brazos, con código Python .
  • Gráficos animados e interactivos que ilustran estrategias de equilibrio entre exploración y explotación basadas en el método Epsilon-greedy, el muestreo de Thompson y el límite superior de confianza.