¿Cómo se obtiene el límite superior de confianza?

Question

He encontrado la fórmula para obtener los límites superiores de confianza en el problema del bandido k-armado:

$$c\sqrt{\frac{\text{ln} N_i}{n_i}}$$

donde $n_i$ es el número de muestras que tenemos para este bandido en particular y $N_i$ es la cantidad total de muestras que tenemos de todos los bandidos. El mismo algoritmo se utiliza en el Monte Carlo Tree Search también para obtener el límite superior de confianza.

Entiendo muy bien lo que es un límite superior de confianza, pero lo que no entiendo es de dónde sale esta fórmula. He intentado buscar en Internet en varios sitios, pero no he podido encontrar una explicación clara de cómo se obtiene esta fórmula. ¿Puede alguien explicarme de dónde procede esta fórmula? Por favor, asumid que no tengo grandes conocimientos de estadística.

Answer 1

Lo que tienes ahí se llama comúnmente término de exploración. El límite superior de confianza es la media empírica más este término de exploración.

Consideremos cada término por separado:

$c$ es una constante que permite al usuario establecer el equilibrio entre exploración y explotación. Para obtener resultados teóricos, a menudo se optimiza para el problema en cuestión (por ejemplo, bandidos k-armados con priores gaussianos).

$\sqrt{1/n_i}$ es proporcional a la desviación típica posterior tras $n_i$ muestras de acción $i$ . Esencialmente esto dice que a medida que se tira de un brazo más a menudo, hay menos desconocimiento sobre el brazo.

$\sqrt{ln(N_i)}$ garantiza que no dejes de explorar demasiado pronto. En $N_i$ se hace muy grande, las varianzas muestrales se vuelven lo suficientemente pequeñas como para que tengamos que compensarlas para asegurarnos de que nunca dejamos de explorar por completo. La mayor parte de la matemática técnica consiste en demostrar que $\sqrt{ln(N_i)}$ es la compensación justa (pero no excesiva).

Para una descripción más técnica, puede consultarse el documento de Auer et al. es un buen punto de partida.

Auer, Peter, Nicolo Cesa-Bianchi y Paul Fischer. "Finite-time analysis of the multiarmed bandit problem". Aprendizaje automático 47.2-3 (2002): 235-256.

Answer 2

Proviene de la desigualdad de Hoeffding, que proporciona un límite superior a la probabilidad de que la suma de delimitado variables aleatorias independientes se desvía de su valor esperado en más de una cantidad determinada. Véase https://en.wikipedia.org/wiki/Hoeffding%27s_inequality para más información sobre la desigualdad de Hoeffding. Véase el texto en torno a la ecuación (3) en el documento original de la UCT para una discusión detallada en relación con UCB1 en el escenario de bandido http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296