Bandido multi armado para la distribución general de recompensas

11

Estoy trabajando en un problema de bandidos multibrazos en el que no tenemos información sobre la distribución de recompensas.

He encontrado muchos documentos que garantizan límites de arrepentimiento para una distribución con límite conocido y para distribuciones generales con soporte en [0,1].

Me gustaría saber si hay una manera de desempeñarse bien en un entorno donde la distribución de recompensas no tiene ninguna garantía sobre su soporte. Estoy tratando de calcular un límite de tolerancia no paramétrico y estoy usando ese número para escalar la distribución de recompensas para poder usar el algoritmo 2 especificado en este documento ( http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf ) ¿Alguien piensa que este enfoque funcionará?

Si no, ¿alguien puede señalarme el lugar correcto?

¡Gracias un montón!

references multiarmed-bandit huésped
fuente

Respuestas:

6

La investigación de los algoritmos MAB está estrechamente vinculada a las garantías teóricas de rendimiento. De hecho, el resurgimiento del interés en estos algoritmos (recuerde que el muestreo de Thompson se propuso en los años 30) solo sucedió realmente desde que el artículo de 2002 de Auer demostraba que lamentaba los límites para los diversos UCB y -greedy algoritmos Como tal, hay poco interés en problemas en los que la distribución de recompensas no tiene un límite conocido ya que no hay casi nada que pueda decirse teóricamente.ϵO(log⁡(T))ϵ

Incluso el simple algoritmo de muestreo de Thompson que mencionas requiere recompensas distribuidas de Bernoulli, ¡e incluso eso tomó 80 años para demostrar un límite logarítmico de arrepentimiento!

Sin embargo, en la práctica, en los casos en que no conozca la distribución de recompensas con certeza, puede simplemente escalarla a dividiendo entre un gran número , y si observa una recompensa por encima de simplemente duplique el valor, . Sin embargo, no hay garantías de arrepentimiento con este enfoque, pero generalmente funciona bastante bien.S S S : = 2 S[0,1]SSS:=2S

Además, el algoritmo de muestreo de Thompson que menciona necesita pruebas de Bernoulli, por lo que no puede usar recompensas continuas arbitrarias. Podría ajustar una distribución posterior gaussiana en lugar de una Beta, pero esto es un poco sensible a su elección de anterior, por lo que es posible que desee configurarlo para que sea muy plano. Si no está buscando demostrar nada sobre su implementación, esto probablemente funcionará bastante bien.

Fairidox
fuente
1
¡Muchas Gracias por la respuesta! ¡Realmente lo aprecio! Aunque tenía una pregunta. Creo que el algoritmo 2 en el documento (en la parte superior de la página 39.4) que mencioné no requiere nada sobre la distribución de recompensas, PERO el hecho de que su soporte está en [0,1]. Tal vez estabas mirando el algoritmo 1?
invitado
Sí, genial, un truco bastante interesante para convertir valores reales en muestras de Bernoulli, gracias por señalar que los detalles se me habían escapado. En cualquier caso, como usted dice, aún necesita variables limitadas, puede hacer esto con el doble truco barato que mencioné y usar esta versión del muestreo de Thompson. Pero puede que sea mejor formular un método que use un posterior gaussiano.
fairidox
Analizaré más el método posterior gaussiano, pero ¿qué quieres decir con "plano" en términos de gaussiano? Supongo que correspondería a algo como un Beta (1,1) (uniforme) anterior, ¿correcto?
invitado
correcto, pero obviamente no puedes tener un uniforme previo sobre un dominio ilimitado. Entonces, si tiene un modelo posterior gaussiano, es probable que tenga un anterior gaussiano, por lo que generalmente desea tenerlo lo más "plano" o lo menos informativo posible. Esto generalmente significa hacer que la varianza sea lo más grande posible. No soy un experto, pero hay todo un campo de estudio sobre cómo construir previos poco informativos y potencialmente impropios que quizás desee analizar. Además, si tiene recompensas estrictamente positivas, es posible que desee considerar un modelo diferente.
fairidox