Lanzamiento de monedas, procesos de decisión y valor de la información.

Imagine la siguiente configuración: tiene 2 monedas, la moneda A que se garantiza que es justa y la moneda B que puede ser justa o no. Se le pide que haga 100 lanzamientos de monedas, y su objetivo es maximizar el número de caras .

Su información previa sobre la moneda B es que fue lanzada 3 veces y arrojó 1 cabeza. Si su regla de decisión se basó simplemente en comparar la probabilidad esperada de caras de las 2 monedas, lanzaría la moneda A 100 veces y terminaría con ella. Esto es cierto incluso cuando se usan estimaciones bayesianas razonables (medias posteriores) de las probabilidades, ya que no tiene ninguna razón para creer que la moneda B arroje más caras.

Sin embargo, ¿qué pasa si la moneda B está sesgada en favor de las caras? Seguramente las "caras potenciales" que abandonas al lanzar la moneda B un par de veces (y por lo tanto obtener información sobre sus propiedades estadísticas) serían valiosas en algún sentido y, por lo tanto, serían un factor en tu decisión. ¿Cómo se puede describir matemáticamente este "valor de la información"?

Pregunta: ¿Cómo construir matemáticamente una regla de decisión óptima en este escenario?

bayesian decision-theory M. Cypher
fuente

Estoy borrando mi respuesta. Demasiadas personas se quejan de que explícitamente utilicé un previo (que es estándar en la literatura). Disfrute de la respuesta incorrecta de Cam Davidson Pilon, donde también asume un previo (pero nadie se opone) y afirma que es un método óptimo que está 1.035 por debajo del óptimo.

Douglas Zare

whoah, cuando sucedió todo esto? Por cierto, estaría de acuerdo con Douglas en que usar un prior está bien. Retraigo mi afirmación de optimismo, también.

Cam.Davidson.Pilon

Estoy aceptando la solución de Cam porque me ayudó mucho. Estoy de acuerdo en que no es óptimo, pero a menos que alguien pueda señalar una solución óptima general que pueda calcularse fácilmente, es la mejor opción.

M. Cypher

¿Por qué fue tan malo que utilicé un previo (que dije claramente) para responder una pregunta etiquetada como "bayesiano"?

Douglas Zare

No critiqué el uso de un prior. Mencioné como nota al margen que podría haber antecedentes más apropiados que el uniforme (por ejemplo, el de Jeffrey), pero esto es solo marginalmente relevante para la pregunta. Su solución fue perfectamente buena, pero no tan útil para mí, ya que no se generaliza fácilmente.

M. Cypher

Respuestas:

Bandido Multi-armado

Este es un caso particular de un problema de bandido multi-armado . Digo un caso particular porque generalmente no conocemos ninguno de las probabilidades de cara (en este caso sabemos que una de las monedas tiene una probabilidad de 0.5).

El problema que plantea se conoce como el dilema de exploración vs explotación : ¿explora las otras opciones o se apega a lo que cree que es el mejor? Existe una solución óptima inmediata, suponiendo que conozca todas las probabilidades : simplemente elija la moneda con la mayor probabilidad de ganar. El problema, como ha aludido, es que no estamos seguros de cuáles son las verdaderas probabilidades .

Hay mucha literatura sobre el tema, y hay muchos algoritmos deterministas, pero desde que etiquetó a este Bayesiano, me gustaría contarle sobre mi solución favorita personal: ¡ el Bandido Bayesiano !

La solución Baysian Bandit

El enfoque bayesiano a este problema es muy natural. Estamos interesados en responder "¿Cuál es la probabilidad de que la moneda X sea la mejor de las dos?".

A priori , suponiendo que todavía no hayamos observado el lanzamiento de una moneda, no tenemos idea de cuál podría ser la probabilidad de que las cabezas de la moneda B denoten este desconocido $p_B$ . Entonces deberíamos asignar una distribución uniforme previa a esta probabilidad desconocida. Alternativamente, nuestro anterior (y posterior) para la moneda A se concentra trivialmente por completo en 1/2.

Como ha dicho, observamos 2 colas y 1 cara de la moneda B, necesitamos actualizar nuestra distribución posterior. Suponiendo un uniforme anterior, y los lanzamientos son monedas de Bernoulli, nuestro posterior es un . Comparando las distribuciones posteriores o A y B ahora: $Beta( 1 + 1, 1 + 2)$

ingrese la descripción de la imagen aquí

Encontrar una estrategia aproximadamente óptima

Ahora que tenemos los posteriores, ¿qué hacer? Estamos interesados en responder "¿Cuál es la probabilidad de que la moneda B sea la mejor de las dos?" (Recuerde desde nuestra perspectiva bayesiana, aunque hay una respuesta definitiva a cuál es mejor, solo podemos hablar en probabilidades):

w_{B} = P (p_{b} > 0.5)

$w_B = P( p_b > 0.5 )$

La solución aproximadamente óptima es elegir B con probabilidad y A con una probabilidad de . Este esquema maximiza las ganancias esperadas. se puede calcular de forma numérica, ya que conocemos la distribución posterior, pero una forma interesante es la siguiente: $w_B$ $1 - w_B$ $w_B$

1. Sample P_B from the posterior of coin B
2. If P_B > 0.5, choose coin B, else choose coin A.

Este esquema también se actualiza automáticamente. Cuando observamos el resultado de elegir la moneda B, actualizamos nuestra parte posterior con esta nueva información y seleccionamos nuevamente. De esta manera, si la moneda B es realmente mala, la elegiremos menos, y si la moneda B es realmente buena, la elegiremos con más frecuencia. Por supuesto, somos bayesianos, por lo tanto, nunca podemos estar absolutamente seguros de que la moneda B sea mejor. Elegir probabilísticamente de esta manera es la solución más natural para el dilema de exploración-explotación.

Este es un ejemplo particular de Thompson Sampling . Más información y aplicaciones de frío a la publicidad en línea, se pueden encontrar en trabajos de investigación de Google y el trabajo de investigación de Yahoo . ¡Amo estas cosas!

Cam.Davidson.Pilon
fuente

No creo que esa estrategia sea correcta. No creo que deba elegir si elegir A o B probabilísticamente.

Douglas Zare

No creo que ese documento diga lo que crees que hace. Si no está de acuerdo, calcule el número esperado de caras que obtendrá con esa estrategia.

Douglas Zare

No creo que esto esté cerca de lo óptimo. Sugiere que en la primera vuelta, elegiste B con probabilidad 1/2. Debe quedar claro que no obtiene información si elige A, por lo que debe elegir B todo el tiempo. La cantidad que pierde por este error es de aproximadamente 0,12 cuando lo hace, por lo que le cuesta aproximadamente 0,06 en el primer paso. Pierdes una cantidad similar cuando lanzas una moneda más o menos para decidir si recopilar información sobre los próximos pasos. Voltear A temprano significa que tiene menos tiempo para explotar una ventaja que pueda encontrar.

Douglas Zare

0.5

$0.5$

@DouglasZare Si su única medida es el número esperado de caras, dados nuestros lanzamientos de monedas, entonces la mejor estrategia es elegir siempre la moneda A. Pero esto es incompleto ya que se enfoca demasiado en la explotación y no lo suficiente en el potencial al alza de la moneda. la exploración . La conclusión lógica de su sugerencia es, si reiniciamos el experimento, lanzar la moneda B una vez: si es Tails, elija siempre A; si no es así, los Jefes siempre eligen B.

Cam.Davidson.Pilon

Este es un caso simple de un problema de bandido multi-armado . Como observa, desea equilibrar la información que recopila al probar la moneda desconocida cuando cree que es subóptima a corto plazo en lugar de explotar el conocimiento que tiene.

En el clásico problema del bandido multi-armado, no estaría seguro de la probabilidad de ninguna moneda. Sin embargo, aquí se le da a conocer que conoce el valor de la moneda A, por lo que cuando lanza A, no obtiene información. De hecho, bien podría ignorar la naturaleza estocástica de A y asumir que obtiene un piso $1/2$

En general, creo que no se puede escapar de un problema de programación dinámica, aunque puede haber casos especiales en los que se pueda encontrar y verificar la estrategia óptima de manera más simple.

Con un uniforme previo, aquí es donde debes parar:

$(0 ~ \text{heads}, 3 ~\text{tails}), (1 ~\text{head}, 5 ~\text{tails}), (2 ~\text{heads}, 6 ~\text{tails}), (3,7), (4,8),...(31,35), (32,35), (33,36), (34,37), ... (41,44), (42,44), ... (46,48), (47,48), (48,49), (49,50)$ .

Bajo esta estrategia, espera recolectar $61.3299$ cabezas

Usé el siguiente código de Mathematica para calcular las acciones:

Clear[Equity];
Equity[n_, heads_, tails_] := Equity[n, heads, tails] = 
    If[n == 0, heads, 
       Max[1/2 + Equity[n - 1, heads, tails], 
           (heads + 1)/(heads + tails + 2) Equity[n - 1, heads + 1, tails] + 
           (tails + 1)/(heads + tails + 2) Equity[n - 1, heads, tails + 1]
           ]
      ]

A modo de comparación, la heurística de muestreo de Thompson (que Cam Davidson Pilon afirmó que es óptima) da un promedio de 60.2907 cabezas, menor en 1.03915. El muestreo de Thompson tiene el problema de que a veces muestrea B cuando tienes suficiente información para saber que no es una buena apuesta, y a menudo desperdicia las posibilidades de probar B temprano, cuando la información vale más. En este tipo de problema, casi nunca eres indiferente entre tus opciones, y existe una estrategia óptima pura.

tp[heads_, tails_] := tp[heads, tails] = 
    Integrate[x^heads (1 - x)^tails / Beta[heads + 1, tails + 1], {x, 0, 1/2}]


Clear[Thompson];
Thompson[flipsLeft_, heads_, tails_] := Thompson[flipsLeft, heads, tails] = 
    If[flipsLeft == 0, heads, 
       Module[{p = tp[heads, tails]}, 
           p (1/2 + Thompson[flipsLeft-1,heads,tails]) + 
           (1-p)((heads+1)/(heads+tails+2)Thompson[flipsLeft-1,heads+1,tails] + 
           ((tails+1)/(heads+tails+2)) Thompson[flipsLeft-1,heads,tails+1])]]

Douglas Zare
fuente

Estoy de acuerdo en que una solución óptima sería mejor que una aproximada. Me pregunto si existe una solución general óptima que pueda aplicarse eficientemente en milisegundos en un entorno dinámico con varios cientos de "monedas". Si no, supongo que el muestreo de Thompson es la mejor opción.

M. Cypher

El muestreo de Thompson es una aproximación pobre. Hay mejores aproximaciones que puede usar si no quiere pasar por el problema del cálculo exacto (en el peor de los casos, cuadrático), pero aún así quiere evitar grandes errores. En realidad, el cálculo exacto podría estar más cerca de lineal.

Douglas Zare

¿Qué nos permite suponer que hay una distribución previa en B? Admito que tal suposición hace que el problema sea más manejable, pero la existencia de una evaluación objetivamente válida de la equidad de B es dudosa para mí. Sí, tenemos los resultados de algunos cambios anteriores, pero aún son consistentes con cualquier valor para

\underset{B}{Pr} (heads)

$\Pr_B(\text{heads})$ en

(0, 1)

$(0,1)$ . Si de hecho esa probabilidad es menor que

1 / 2

$1/2$ , Entonces no me importa lo que antes se decide adoptar: será un hecho objetivo que el número esperado de cabezas con su enfoque es menos de

50

$50$ .

whuber

No conozco Mathematica, así que no puedo seguir cómo calculó su número esperado de caras. ¿Te importaría explicar esa parte? Si asumimos el conocimiento de que el sesgo de la moneda B se extrae de una distribución uniforme en [0,1], entonces no veo cómo puede esperar vencer 50/50.

jerad

Douglas: Because I paid more attention to your answer :-). Please don't get me wrong--I like it and I like this thread. I thought it important to point out that you had to add an assumption in order to obtain your answer, that's all. As a practical matter, in many situations--including this one--there is no prior. (I sure wouldn't want to make up a personal prior and then have to bet big money on it!) But of course there is still an optimum, provided you specify a loss function. ("Maximizing" an expectation is not a full loss function.)

whuber