Límite inferior de Lai-Robbins ⇐ Proyectos de artículos

[Guest]

El límite inferior de Lai-Robbins da un límite inferior asintótico en el arrepentimiento que cualquier algoritmo uniformemente bueno debe incurrir en el problema estocástico del bandido multiarmado (Bandido multiarmado). El resultado original fue probado por Herbert Robbins (Tze Leung Lai) (Tze Leung Lai) y Herbert Robbins (Herbert Robbins) en 1985 para familias exponenciales (Familia exponencial) paramétricas. Trabajos posteriores ampliaron la declaración a clases de distribuciones más generales.>

== Problema de bandidos con múltiples brazos ==

El problema del bandido armado múltiple (MAB) es un juego secuencial (Juego secuencial) en el que el jugador debe intercambiar exploración (para aprender) y explotación (para ganar).

El jugador elige entre K acciones (armas) con distribuciones desconocidas \nu = (\nu_1,\dots,\nu_K). Se supone que el jugador conoce una clase de distribuciones \mathcal{D} tal que por cada k uno tiene \nu_k\in\mathcal{D} (por ejemplo, \mathcal{D} puede ser la familia de distribución normal|Distribución gaussiana o Bernoulli|Distribuciones Bernoulli).

En cada ronda t=1,\dots,T el jugador selecciona (tira) un brazo a_t y observa una recompensa X_t\sim\nu_{a_t}.

Denotamos
* N_a(t):=\sum_{s=1}^t\mathbf{1}_{\{a_s=a\ el número de veces que se ha tirado del brazo a en las primeras t rondas,
* \mu(\nu):=(\mu_1,\dots,\mu_K) el vector del brazo significa, donde \mu_k=\mathbb{E}_{X\sim\nu_k}[X],
* \mu^*:=\max_a \mu_a la media más alta
* \Delta_a:=\mu^*-\mu_a\ge 0 la brecha del brazo a.

Un brazo a con \mu_a=\mu^* se llama '''brazo óptimo'''; de lo contrario, se trata de un '''brazo subóptimo''.

El objetivo es '''minimizar el arrepentimiento''' en el horizonte T, definido por
:R_T:= \sum_{a=1}^K \Delta_a\,\mathbb{E}[N_a(T)].

Intuitivamente, el arrepentimiento es la pérdida total (esperada) en comparación con jugar siempre con un brazo óptimo:
:\text{arrepentimiento}=\sum_{a}\ (\text{costo de jugar }a)\times(\text{veces }a\text{ se juega}).

Un algoritmo MAB es una política (posiblemente aleatoria) que, en cada ronda t, elige un brazo a_t utilizando las observaciones recibidas de turnos anteriores.>

=== Ejemplo intuitivo ===
Supongamos que un agricultor debe elegir, cada año, una de las variedades de semillas K para plantar. Cada variedad k tiene un rendimiento medio desconocido \mu_k. Si el agricultor conociera la mejor variedad (con media \mu^*) la plantaría todos los años; en realidad debe probar variedades para saber cuál es la mejor. El arrepentimiento acumulado después de T años mide la pérdida total esperada de rendimiento debido a un conocimiento imperfecto.

'''Observaciones'''
# El modelo anterior es el MAB ''estocástico''; también existen variantes adversarias.>
# Se puede considerar una configuración de ''horizonte fijo'' (T conocida) o una configuración ''en cualquier momento'' (T desconocida).

== Límite inferior de Lai-Robbins ==

El teorema da la cantidad de tiempo correcta en la que debemos tirar de un brazo subóptimo k para distinguir si estamos en el caso con \nu_k o con \tilde{\nu}_k donde \tilde{\nu}_k es tal que \tilde{\mu}_k > \mu^*.

Conocer un límite inferior en el número de tirones de cada brazo subóptimo proporciona un límite inferior en el arrepentimiento, ya que solo los brazos subóptimos contribuyen al arrepentimiento.

Antes de enunciar el teorema formal necesitamos definir qué es un algoritmo consistente.

=== Consistencia (algoritmos uniformemente buenos) ===

Sea \mathcal{D} una clase de distribuciones de probabilidad y considere brazos K con distribuciones de recompensa
\nu = (\nu_1,\dots,\nu_K) \in \mathcal{D}^K.
Se dice que un algoritmo es ''consistente'' (también llamado ''uniformemente bueno'') en \mathcal{D}^K si, para cada instancia \nu \in \mathcal{D}^K, el arrepentimiento esperado R_T(\nu) crece subpolinomialmente:
:\forall \alpha > 0, \qquad
R_T(\nu) = o(T^\alpha)
\quad \text{as } T \to \infty

Esta suposición excluye algoritmos que funcionan bien en algunos casos pero que generan arrepentimiento lineal en otros.

=== Límite inferior formal ===

Para cualquier brazo subóptimo a.
Para una distribución \nu_a \in \mathcal{D} y un umbral x, defina
:\mathcal{K}_{\inf}(\nu_a, x, \mathcal{D})
:= \inf \Bigl\{
\nombreoperador{KL}(\nu_a, \nu'):
\nu' \en \mathcal{D},
\ \mu' > x
\Bigr\}
donde \operatorname{KL}(\cdot,\cdot) denota la divergencia Kullback-Leibler|Divergencia Kullback-Leibler.

Luego, para cualquier algoritmo consistente en \mathcal{D}^K y para cada instancia
\nu \in \mathcal{D}^K, cada brazo subóptimo a satisface
:\mathbb{E}_\nu[N_a(T)]
\ge
\frac{\ln T}{\mathcal{K}_{\inf}(\nu_a, \mu^*, \mathcal{D})}
+ o(\ln T)

En consecuencia, el arrepentimiento satisface
:R_T(\nu)
\ge
\izquierda(
\sum_{a:\,\mu_a < \mu^*}
\frac{\Delta_a}{\mathcal{K}_{\inf}(\nu_a, \mu^*, \mathcal{D})}
\derecha)
\ln T
+ o(\ln T)

El artículo original de 1985 estableció este resultado para familias exponenciales; trabajos posteriores demostraron que el límite se cumple bajo suposiciones mucho más débiles en \mathcal{D}.

=== Intuición ===

La coherencia impone que, por cada \nu, el número de tirones de un brazo óptimo debe ser grande. Esto significa que \mu^* se estima con mucha precisión. El objetivo es determinar, para un brazo subóptimo k, cuántas muestras se necesitan para tener confianza, con el nivel adecuado de confianza, en que \mu_k < \mu^*. Para hacerlo, utilizamos lo que se llama la '''instancia más confusa''': una instancia cercana a \nu tal que el brazo k sea óptimo. Lo definimos como \tilde{\nu} de modo que, para todo a \neq k, \tilde{\nu}_a = \nu_a, y \tilde{\nu}_k se elige de modo que \tilde{\mu}_k > \mu^*. El objetivo es determinar cuántas muestras del brazo k se requieren para distinguir si estamos en la instancia con \nu_k o con \tilde{\nu}_k en términos de distancia \operatorname{KL}.

== Algoritmos que alcanzan el límite inferior de Lai-Robbins ==

Se sabe que varios algoritmos logran el límite inferior asintótico de Lai-Robbins
bajo supuestos específicos sobre la clase de distribución de recompensas \mathcal{D}.
La siguiente lista resume una lista no exhaustiva de algoritmos que calculan el límite inferior.

== Ampliación a otros problemas ==

=== Bandido estructurado ===

Un bandido estructurado más complejo donde sabemos que la media de cada brazo está en un conjunto con alguna restricción. En este caso podemos demostrar un límite inferior más pequeño que utiliza el conocimiento de este conjunto.>

=== Identificación del mejor brazo (BAI) ===

Se ha demostrado un resultado similar para la identificación del mejor brazo, que es el mismo juego excepto que, en lugar de minimizar el arrepentimiento, el objetivo es identificar el mejor brazo con probabilidad 1 - \delta usando la menor cantidad de rondas posible.

=== Aprendizaje por refuerzo (RL) ===

Se han demostrado resultados similares para la minimización del arrepentimiento en el aprendizaje por refuerzo con recompensa promedio. El orden también es \ln T, con una constante que depende del problema.

== Ver también ==

* Bandido con múltiples brazos|Bandido con múltiples brazos
* Límite superior de confianza|Límite superior de confianza
* Intervalo de confianza|Intervalo de confianza



|último=Maillard
|primero=Odalric-Ambrym
|title=Matemáticas de la toma de decisiones estadísticas secuenciales
|año=2019
|tipo=tesis doctoral
|institución=Université de Lille, Ciencias y Tecnologías


|último=Kaufmann
|primero=Emilie
|title=Contribuciones a la solución óptima de varios problemas de bandidos
|año=2020
|tipo=tesis doctoral
|institución=Universidad de Lille


|last1=Tumbas
|primero1=Todd L.
|last2=Lai
|first2=Tze Leung
|title=Elección adaptativa asintóticamente eficiente de leyes de control en cadenas de Markov no controladas
|journal=Revista SIAM de Control y Optimización
|año=1997
|volumen=35
|número=3
|páginas=715–743
|editor=SIAM


|último1=Garivier
|first1=Aurélien
|last2=Kaufmann
|first2=Emilie
|title=Identificación óptima del mejor brazo con confianza fija
|año=2016
|clase=matemáticas.ST
|eprint=1602.04589


|último1=Boone
|first1=Víctor
|last2=Maillard
|first2=Odalric-Ambrym
|title=El límite inferior del arrepentimiento para comunicar los procesos de decisión de Markov
|año=2025
|clase=cs.LG
|eprint=2501.13013


|last1=Lattimore
|primero1=Tor
|title=Refinar el nivel de confianza para estrategias de bandidos optimistas
|journal=Revista de investigación sobre aprendizaje automático
|año=2018
|volumen=19
|número=20
|páginas=1–32
|url=http://jmlr.org/papers/v19/17-513.html


|last1=Agrawal
|first1=Shipra
|last2=Goyal
|first2=Navin
|title=Análisis del muestreo de Thompson para el problema de los bandidos multiarmados
|journal=Actas de la 25ª Conferencia Anual sobre Teoría del Aprendizaje
|editor1=Mannor, Shie
|editor2=Srebro, Nathan
|editor3=Williamson, Robert C.
|año=2012
|volumen=23
|series=Actas de la investigación sobre aprendizaje automático
|páginas=39.1–39.26 |editor=PMLR
|url=https://procedimientos.mlr.press/v23/agrawal12.html


|último1=Cowan
|first1=Wesley
|último2=Honda
|first2=Junya
|last3=Katehakis
|first3=Michael N.
|title=Bandidos normales de medios y variaciones desconocidos
|journal=Revista de investigación sobre aprendizaje automático
|año=2018
|volumen=18
|número=154
|páginas=1–28
|url=http://jmlr.org/papers/v18/15-154.html


|último1=Baudry
|primero1=Dorian
|last2=Kaufmann
|first2=Emilie
|last3=Maillard
|first3=Odalric-Ambrym
|title=Submuestreo para una exploración de bandidos no paramétrica eficiente
|año=2020
|clase=stat.ML
|eprint=2010.14323




|last1=Cappé
|primero1=Olivier
|last2=Garivier
|first2=Aurélien
|last3=Maillard
|first3=Odalric-Ambrym
|last4=Munos
|first4=Rémi
|last5=Stoltz
|first5=Gilles
|title=Límites de confianza superiores de Kullback-Leibler para una asignación secuencial óptima
|journal=Los anales de la estadística
|año=2013
|páginas=1516–1541


|último1=Garivier
|first1=Aurélien
|last2=Hadiji
|first2=Hedi
|last3=Ménard
|first3=Pedro
|last4=Stoltz
|first4=Gilles
|título=Interruptor KL-UCB: Límites de arrepentimiento óptimos para los bandidos estocásticos desde el punto de vista tanto dependiente de la distribución como libre de distribución
|journal=Revista de investigación sobre aprendizaje automático
|volumen=23
|número=179
|año=2022
|páginas=1–66


|last1=Lai
|primero1=T.L.
|last2=Robbins
|first2=Herbert
|title=Reglas de asignación adaptativa asintóticamente eficientes
|journal=Avances en Matemática Aplicada
|volumen=6
|número=1
|páginas=4–22
|año=1985
|doi=10.1016/0196-8858(85)90002-8
|url=https://dx.doi.org/10.1016/0196-8858%2885%2990002-8


|last1=Riou
|first1=Carlos
|último2=Honda
|first2=Junya
|title=Algoritmos bandidos basados en el muestreo de Thompson para distribuciones de recompensas acotadas
|book-title=Actas de la 31ª Conferencia Internacional sobre Teoría del Aprendizaje Algorítmico
|editor1-last=Kontorovich
|editor1-first=Aryeh
|editor2-last=Nuevo
|editor2-first=Gergely
|series=Actas de la investigación sobre aprendizaje automático
|volumen=117
|páginas=777–826
|ubicación=
|editor=PMLR
|año=2020
|url=https://proceedings.mlr.press/v117/riou20a.html


|último1=Honda
|first1=Junya
|last2=Takemura
|first2=Akimichi
|title=Análisis no asintótico de un nuevo algoritmo Bandit para recompensas semi-limitadas
|journal=Revista de investigación sobre aprendizaje automático
|volumen=16
|número=113
|páginas=3721–3756
|año=2015
|url=http://jmlr.org/papers/v16/honda15a.html


|último1=Honda
|first1=Junya
|last2=Takemura
|first2=Akimichi
|title=Un algoritmo Bandit asintóticamente óptimo para modelos de soporte acotado
|título-libro=COLT
|páginas=67–79
|año=2010


|último1=Baudry
|primero1=Dorian
|last2=Pesquerel
|first2=Fabien
|last3=Degenne
|first3=Rémy
|last4=Maillard
|first4=Odalric-Ambrym
|title=Algoritmos rápidos asintóticamente óptimos para bandidos estocásticos no paramétricos
|journal=Avances en los sistemas de procesamiento de información neuronal
|volumen=36
|páginas=11469–11514
|año=2023




More details: https://en.wikipedia.org/wiki/Lai-Robbins_lower_bound