Algoritmo de exploración y confirmación ⇐ Proyectos de artículos

[Anonymous]

Explore Then Commit (ETC) es un algoritmo para el problema de los bandidos armados múltiples en el que hay que hacer un equilibrio entre exploración y explotación.

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

El problema del bandido con múltiples brazos (Problema del bandido con múltiples brazos) es un juego secuencial (Juego secuencial) donde un jugador tiene que elegir en cada turno entre K acciones (brazos). Detrás de cada brazo a hay una distribución desconocida \nu_a que se encuentra en un conjunto \mathcal{D} conocido por el jugador (por ejemplo, \mathcal{D} puede ser el conjunto de Distribución normal|Distribuciones gaussianas o Distribución de Bernoulli|Distribuciones de Bernoulli).

En cada turno t el jugador elige (tira) un brazo a_t, luego obtiene una observación X_t de la distribución \nu_{a_t}.

=== Minimización del arrepentimiento ===

El objetivo es minimizar el arrepentimiento en el momento T que se define como
: R_T := \sum_{a=1}^K \Delta_a \mathbb{E}[N_a(T)]
donde
* \mu_a := \mathbb{E}[\nu_a] es la media del brazo a
* \mu^* := \max_a \mu_a es la media más alta
* \Delta_a := \mu^* - \mu_a
* N_a(t) es el número de tirones del brazo a hacia arriba para girar t

El jugador tiene que encontrar un algoritmo que elija en cada turno t qué brazo tirar en función de las acciones y observaciones anteriores (a_s,X_s)_{s < t} para minimizar el arrepentimiento R_T.

Este es un problema de equilibrio entre la exploración para encontrar el mejor brazo (el brazo con la media más alta) y la explotación para jugar tanto como sea posible con el brazo que creemos que es el mejor.>

== Algoritmo ==

La idea del algoritmo es explorar cada brazo M veces. Luego, durante el resto del juego, el algoritmo explota jugando el brazo con la media más alta. Si se conoce el horizonte T entonces el número de exploración M puede depender de T.

Existen adaptaciones del algoritmo y se pueden encontrar en la literatura para otros entornos.

=== Pseudocódigo ===

El jugador elige M
'''para'''' cada brazo '''yo''' '''hacer''':
seleccionar brazo '''i''' M veces
actualizar la media empírica mu['''i''']
'''para''' t de MK+1 a T '''do''':
seleccione el brazo '''a''' con la media empírica más alta mu['''a''']

== Resultados teóricos ==

Cuando todos los brazos son 1-sub gaussianos, al elegir explorar cada brazo M veces, se verifica el arrepentimiento en el momento T
:
R_T \leq M \sum_{i = 1}^K \Delta_i + (T - M K) \sum_{i=1}^K \Delta_i \exp\left( -\frac{M \Delta_i^2}{4} \right)


Podemos ver el primer término como el costo de la exploración
:
M \sum_{i = 1}^K \Delta_i
Y el segundo término como el costo de no haber explorado lo suficiente, lo que lleva a una probabilidad de no tener un brazo óptimo como el brazo con la media empírica más alta.
:
(T - M K) \sum_{i=1}^K \Delta_i \exp\left( -\frac{M \Delta_i^2}{4} \right)
Al aumentar M se aumenta el primer término y se disminuye el segundo. El mejor M posible depende del (\Delta_i)_i que el jugador desconoce.

Para dos brazos con distribución gaussiana de varianza 1 se demostró que ETC no puede alcanzar el arrepentimiento óptimo asintótico de la ecuación de Lai-Robbins.>

== 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



|last1=No
|first1=Guanyu
|last2=Agarwal
|first2=Mridul
|last3=Umrawal
|first3=Abhishek Kumar
|last4=Aggarwal
|first4=Vaneet
|last5=Quinn
|first5=Cristóbal Juan
|title=Un algoritmo de exploración y luego confirmación para la maximización submodular bajo retroalimentación de bandido completo
|book-title=Incertidumbre en la Inteligencia Artificial
|páginas=1541–1551
|año=2022
|editor=PMLR


|último1=Jin
|first1=Tianyuan
|último2=Xu
|first2=Desplazamiento
|last3=Xiao
|first3=Xiaokui
|last4=Gu
|first4=Quanquan
|title=Doble exploración y luego compromiso: optimización asintótica y más allá
|book-title=Conferencia sobre Teoría del Aprendizaje
|páginas=2584–2633
|año=2021
|editor=PMLR


|último1=Garivier
|first1=Aurélien
|last2=Kaufmann
|first2=Emilie
|last3=Lattimore
|primero3=Tor
|title=Sobre las estrategias para explorar y luego comprometerse
|book-title=Avances en los sistemas de procesamiento de información neuronal 29
|año=2016


|last1=Lattimore
|primero1=Tor
|last2=Szepesvári
|first2=Csaba
|title=Algoritmos bandidos
|año=2020
|editor=Prensa de la Universidad de Cambridge




Algoritmos
Teoría de la decisión
Métodos secuenciales
Algoritmos y métodos de optimización
Optimización estocástica
Teoría de juegos

More details: https://en.wikipedia.org/wiki/Explore-t ... _algorithm