El problema de Warren Buffett

Aquí hay una abstracción de un problema de aprendizaje / bandido en línea en el que he estado trabajando en el verano. No he visto un problema como este antes, y parece bastante interesante. Si conoce algún trabajo relacionado, agradecería referencias.

El problema La configuración es la de los bandidos con múltiples brazos. Tienes N brazos. Cada brazo tiene una distribución de probabilidad desconocida pero fija sobre las recompensas que se pueden obtener al jugarlo. Para ser concretos, vamos a suponer que cada brazo i paga recompensa de $ 10 con probabilidad p [i] y la recompensa $ 0 con prob. 1-p [i] .

En cada ronda t seleccionas un conjunto S [t] de armas para jugar. Por cada brazo que seleccione, pagará una tarifa de $ 1 por adelantado. Para cada brazo seleccionado, usted recoge una recompensa que se extrae de la distribución de probabilidad de recompensa (desconocida) de ese brazo. Todas las recompensas se acreditan a su cuenta bancaria, y todas las tarifas se deducen de esa cuenta. Además, obtienes un crédito de $ 1 al comienzo de cada iteración.

El problema es desarrollar una política para seleccionar un subconjunto de armas para jugar en cada iteración para maximizar las ganancias (es decir, recompensas menos comisiones por jugar) en un horizonte lo suficientemente largo, sujeto a la restricción de que debe mantener un saldo de cuenta no negativo en todo el tiempo.

No especifiqué si las distribuciones de recompensa por brazo se eligen de una distribución previa o si las elige un adversario. Ambas opciones tienen sentido. La formulación del adversario es más atractiva para mí, pero probablemente sea más difícil avanzar. Aquí, el adversario elige un vector (D1, D2, .., DN) de distribuciones. Dadas las distribuciones, la política equilibrada de presupuesto óptimo es jugar todas las armas cuya recompensa esperada es mayor a $ 1. Deje que P sea el beneficio por paso de esta política omnisciente óptima. Quiero que mi política en línea minimice el arrepentimiento (es decir, la pérdida de ganancias en un período de tiempo T) con esta política omnisciente.

Me imagino que hay muchos enfoques posibles para este problema (muchos de los cuales estoy seguro que consideró). Aquí hay algunas ideas / referencias.

• $N$
• $O(2^{N/2} T^{1/2})$
• En un próximo artículo de NIPS 2010, Saten Kale, Rob Schapire y yo consideramos el caso en el que uno juega una lista de armas a la vez. En nuestro trabajo, sin embargo, el tamaño de la pizarra es fijo. Este documento también considera un problema similar. Otro trabajo similar apareció en ALT 2010. Quizás algunas de las ideas se transfieren.
• $2^N$$O(N\sqrt{T})$$O(2^N T)$

EDITAR a continuación:

$0$$1$$(n-1)/n$$T$$T$$(n-1)T/n$

$B$$0$$2B$$1/B$