El problema de Warren Buffett

19

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.

Martin Pál
fuente
¿Estás seguro de que la mejor política es jugar todas las armas cuya recompensa esperada es mayor a $ 1 en cada ronda? Si tiene la restricción estricta de que tiene que mantener un saldo de cuenta no negativo en todo momento, puede haber rondas en las que ni siquiera se le permite jugar.
Matthias
¿Entonces no conoce las probabilidades de recompensa, pero puede distinguir el resultado de cada brazo individual?
David Thornley
No conoce las probabilidades y no conoce las recompensas esperadas. Sin embargo, una política "óptima" omnisciente con la que quiero compararme puede jugar todas las armas con una recompensa mayor que 1 porque es omnisciente.
Martin Pál
1
Θ(N)Ω(N)
Θ(N)

Respuestas:

13

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(2N/2T1/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.
  • 2NO(NT)O(2NT)

EDITAR a continuación:

01(n1)/nTT(n1)T/n

B02B1/B

Lev Reyzin
fuente
Hola Lev, gracias por los consejos. Estoy de acuerdo en que si tuviera un presupuesto inicial ilimitado, jugar N bandidos paralelos de un solo brazo resolvería el problema. Sin embargo, la restricción presupuestaria introduce el acoplamiento entre armas y hace las cosas interesantes. En particular, en el primer paso solo tienes presupuesto para jugar un brazo. En el segundo paso, puede jugar 11 brazos o solo 1 brazo, dependiendo de si tuvo suerte en el primer paso, etc. Por lo tanto, es importante encontrar un grupo de armas rentables desde el principio y luego usarlas para explorar más.
Martin Pál
2
No me di cuenta de que había un presupuesto inicial (ahora entiendo la parte del "saldo no negativo", pero ¿quizás pueda aclararlo en la pregunta?), Lo que hace que el problema sea más interesante. También puede ser divertido considerar la versión "contextual" o de expertos. Desafortunadamente, no conozco más referencias relevantes para este problema.
Lev Reyzin
Si acerté en la formulación del problema, ganas $ 1 extra por ronda. Martin, ¿podrías aclarar la pregunta?
Jukka Suomela
Creo que ganas lo que paga una máquina si la juegas y ganas y pierdes $ 1 cada vez que decides jugar.
Lev Reyzin