Bandido armado multi para distribución general recompensa

Question

Estoy trabajando en un multi-armed bandit problema donde no tenemos ninguna información acerca de la recompensa de distribución.

He encontrado muchos artículos que garantizan el lamento de los límites para una distribución conocida, y para general las distribuciones con soporte en [0,1].

Me gustaría saber si hay una manera de llevar a cabo bien en un entorno donde la recompensa de distribución no tiene ninguna garantía acerca de su apoyo. Estoy tratando de calcular un test no paramétrico de límite de tolerancia y el uso que el número de la escala de la recompensa de la distribución, de manera que se puede utilizar el algoritmo 2 se especifica en este documento (http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf). No creo que nadie este enfoque de trabajo?

Si no, puede que nadie me señale el lugar adecuado?

Muchísimas gracias!

Answer 1

La investigación en el MAB algoritmos está estrechamente ligada a la teórica garantías de rendimiento. De hecho, el resurgimiento del interés en estos algoritmos (recordemos Thompson muestreo fue propuesto en los años 30) sólo se produjo desde Auer del documento de 2002 demostrando $\mathcal{O}(\log(T))$ lamento de los límites para los diferentes UCB y $\epsilon$-algoritmos voraces. Como tal, hay poco interés en los problemas donde la recompensa de distribución no se conoce ningún atado porque no hay casi nada que se puede decir teóricamente.

Incluso el simple Thompson algoritmo de muestreo de mencionar que se requiere de Bernoulli distribuyen las recompensas, e incluso que se llevó a 80 años para demostrar logarítmica lamento obligado!

En la práctica, sin embargo, En los casos en los que no saben que la recompensa de distribución por cierto, usted puede simplemente en escala de a $[0,1]$ dividiendo por el gran número de $S$, y si observa una recompensa por encima de $S$ el doble de valor, $S:=2S$. No hay arrepentimiento garantiza el uso de este enfoque, aunque, pero por lo general funciona bastante bien.

También, el Thompson algoritmo de muestreo de mencionar que las necesidades de ensayos de Bernoulli, entonces usted no puede usar arbitraria continua recompensas. Usted podría caber una Gaussiana posterior distribución en lugar de una versión Beta, pero esto es un poco sensible a su elección de antes, si lo desea, puede configurarlo para que sea muy plana. Si usted no está buscando a probar nada acerca de la implementación, esto probablemente va a funcionar bastante bien.