Retournement de pièces, processus de décision et valeur de l'information

14

Imaginez la configuration suivante: vous avez 2 pièces, la pièce A qui est garantie d'être juste et la pièce B qui peut ou non être juste. On vous demande de faire 100 lancers de pièces, et votre objectif est de maximiser le nombre de têtes .

Votre information préalable sur la pièce B est qu'elle a été retournée 3 fois et a donné 1 tête. Si votre règle de décision était simplement basée sur la comparaison de la probabilité attendue des têtes des 2 pièces, vous retourneriez la pièce A 100 fois et vous en auriez fini. Cela est vrai même en utilisant des estimations bayésiennes raisonnables (moyennes postérieures) des probabilités, car vous n'avez aucune raison de croire que la pièce B rapporte plus de têtes.

Mais que se passe-t-il si la pièce B est réellement biaisée en faveur des têtes? Les «têtes potentielles» que vous abandonnez en retournant la pièce B à quelques reprises (et donc en obtenant des informations sur ses propriétés statistiques) seraient sûrement précieuses dans un certain sens et donc entreraient en ligne de compte dans votre décision. Comment décrire mathématiquement cette "valeur de l'information"?

Question: Comment construisez-vous mathématiquement une règle de décision optimale dans ce scénario?

M. Cypher
la source
J'efface ma réponse. Trop de gens se plaignent que j'ai explicitement utilisé un a priori (ce qui est standard dans la littérature). Profitez de la réponse incorrecte de Cam Davidson Pilon où il suppose également un précédent (mais personne ne s'y oppose) et prétend comme une méthode optimale qui est 1,035 inférieure à l'optimale.
Douglas Zare
whoah, quand est-ce que tout cela est arrivé? BTW, je suis d'accord avec Douglas que l'utilisation d'un prior est très bien. Je retire également mon affirmation d'optimalité.
Cam.Davidson.Pilon
J'accepte la solution de Cam car elle m'a beaucoup aidé. Je suis d'accord que ce n'est pas optimal, mais à moins que quelqu'un puisse indiquer une solution optimale générale qui peut être facilement calculée, c'est le meilleur pari.
M. Cypher
Pourquoi était-ce si grave que j'ai utilisé un préalable (que j'ai clairement indiqué) pour répondre à une question étiquetée «bayésienne»?
Douglas Zare
1
Je n'ai pas critiqué l'utilisation d'un a priori. J'ai mentionné en guise de note qu'il pourrait y avoir des prieurs plus appropriés que l'uniforme (par exemple Jeffrey's), mais cela n'est que marginalement pertinent pour la question. Votre solution était parfaitement bien, mais pas aussi utile pour moi car elle ne se généralise pas facilement.
M. Cypher

Réponses:

7

Bandit à bras multiples

Ceci est un cas particulier d'un problème de bandit multi-armé . Je dis un cas particulier parce que généralement nous ne connaissons aucune des probabilités des têtes (dans ce cas, nous savons que l'une des pièces a une probabilité de 0,5).

La question que vous soulevez est connue sous le nom de dilemme exploration vs exploitation : explorez-vous les autres options, ou restez-vous avec ce que vous pensez être le meilleur. Il existe une solution optimale immédiate en supposant que vous connaissiez toutes les probabilités : choisissez simplement la pièce avec la plus forte probabilité de gagner. Le problème, comme vous l'avez mentionné, est que nous ne savons pas quelles sont les véritables probabilités .

Il y a beaucoup de littérature sur le sujet, et il y a beaucoup d'algorithmes déterministes, mais depuis que vous avez tagué ce bayésien, j'aimerais vous parler de ma solution préférée personnelle: le bandit bayésien !

La solution Baysian Bandit

L'approche bayésienne de ce problème est très naturelle. Nous voulons répondre "Quelle est la probabilité que la pièce X soit la meilleure des deux?".

A priori , en supposant que nous n'avons pas encore observé de retournement de pièce, nous n'avons aucune idée de la probabilité que les têtes de la pièce B soient, dénotons ce inconnu . Nous devons donc attribuer une distribution uniforme préalable à cette probabilité inconnue. Alternativement, notre précédent (et postérieur) pour la pièce A est trivialement concentré entièrement à 1/2.pB

Comme vous l'avez indiqué, nous observons 2 queues et 1 têtes de la pièce B, nous devons mettre à jour notre distribution postérieure. En supposant un a priori uniforme, et les flips sont des flips de Bernoulli, notre postérieur est un . En comparant les distributions postérieures ou A et B maintenant:Betune(1+1,1+2)

entrez la description de l'image ici

Trouver une stratégie approximativement optimale

Maintenant que nous avons les postérieurs, que faire? Nous sommes intéressés à répondre "Quelle est la probabilité que la pièce B soit la meilleure des deux" (rappelez-vous de notre point de vue bayésien, bien qu'il y ait une réponse définitive à laquelle on est meilleur, nous ne pouvons parler qu'en probabilités):

wB=P(pb>0.5)

wB1wBwB

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

Ce schéma s'auto-met également à jour. Lorsque nous observons le résultat du choix de la pièce B, nous mettons à jour notre postérieur avec ces nouvelles informations, puis sélectionnons à nouveau. De cette façon, si la pièce B est vraiment mauvaise, nous la choisirons moins, et cette pièce B est en fait vraiment bonne, nous la choisirons plus souvent. Bien sûr, nous sommes Bayésiens, donc nous ne pouvons jamais être absolument sûrs que la pièce B est meilleure. Le choix probabiliste comme celui-ci est la solution la plus naturelle au dilemme exploration-exploitation.

Il s'agit d'un exemple particulier d' échantillonnage de Thompson . Plus d' informations et des applications fraîches à la publicité en ligne, se trouvent dans le document de recherche de Google et le document de recherche de Yahoo . J'adore ce truc!

Cam.Davidson.Pilon
la source
2
Je ne pense pas que cette stratégie soit correcte. Je ne pense pas que vous devriez choisir de choisir A ou B de manière probabiliste.
Douglas Zare
2
Je ne pense pas que ce document indique ce que vous pensez qu'il fait. Si vous n'êtes pas d'accord, veuillez calculer le nombre attendu de têtes que vous obtiendrez dans le cadre de cette stratégie.
Douglas Zare
5
Je ne pense pas que ce soit presque optimal. Cela suggère qu'au premier flip, vous avez choisi B avec une probabilité 1/2. Il doit être clair que vous n'obtenez aucune information si vous choisissez A, vous devez donc choisir B tout le temps. Le montant que vous perdez par cette erreur est d'environ 0,12 lorsque vous le faites, donc cela vous coûte environ 0,06 à la première étape. Vous perdez un montant similaire lorsque vous lancez grossièrement une pièce pour décider de collecter des informations sur les prochaines étapes. Retourner tôt signifie que vous avez moins de temps pour exploiter un avantage que vous pourriez trouver.
Douglas Zare
3
0,5
1
@DouglasZare Si votre seule mesure est le nombre attendu de têtes, étant donné nos pièces retournées, alors la meilleure stratégie est de toujours choisir la pièce A. Mais cela est incomplet car il se concentre trop sur l' explioitation , et pas assez sur le potentiel potentiel de l'exploration . La conclusion logique de votre suggestion est, si nous recommençons l'expérience, de lancer une fois la pièce B: si c'est Tails, choisissez toujours A; sinon retournez-le à nouveau, s'il s'agit de chefs, choisissez toujours B.
Cam.Davidson.Pilon
9

Il s'agit d'un cas simple d'un problème de bandit à plusieurs bras . Comme vous le constatez, vous souhaitez équilibrer les informations que vous collectez en essayant la pièce inconnue lorsque vous pensez qu'elle n'est pas optimale à court terme par rapport à l'exploitation des connaissances que vous avez.

1/2

En général, je pense que vous ne pouvez pas échapper à un problème de programmation dynamique, bien qu'il puisse y avoir des cas particuliers où la stratégie optimale peut être trouvée et vérifiée plus simplement.

Avec un uniforme avant, voici où vous devez vous arrêter:

(0 têtes,3 queues),(1 tête,5 queues),(2 têtes,6 queues),(3,sept),(4,8),...(31,35),(32,35),(33,36),(34,37),...(41,44),(42,44),...(46,48),(47,48),(48,49),(49,50)

61,3299

J'ai utilisé le code Mathematica suivant pour calculer les actions:

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]
           ]
      ]

À titre de comparaison, l'heuristique d'échantillonnage de Thompson (qui, selon Cam Davidson Pilon, est optimale) donne une moyenne de 60,2907 têtes, en baisse de 1,03915. L'échantillonnage de Thompson a le problème qu'il échantillonne parfois B lorsque vous avez suffisamment d'informations pour savoir que ce n'est pas un bon pari, et qu'il gaspille souvent les chances d'échantillonner B tôt, lorsque l'information vaut le plus. Dans ce type de problème, vous n'êtes presque jamais indifférent entre vos options, et il existe une stratégie optimale pure.

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
la source
Je suis d'accord qu'une solution optimale serait meilleure qu'une solution approximative. Je me demande s'il existe une solution générale optimale qui peut être appliquée efficacement en quelques millisecondes dans un environnement dynamique avec plusieurs centaines de "pièces". Sinon, je suppose que l'échantillonnage de Thompson est la meilleure option.
M. Cypher
L'échantillonnage de Thompson est une mauvaise approximation. Il existe de meilleures approximations que vous pouvez utiliser si vous ne voulez pas passer par le problème du calcul exact (au pire quadratique), mais que vous voulez tout de même éviter de grosses erreurs. En fait, le calcul exact pourrait être plus proche de linéaire.
Douglas Zare
Qu'est-ce qui nous permet de supposer qu'il existe une distribution préalable sur B? J'admets qu'une telle hypothèse rend le problème plus traitable, mais l'existence d'une évaluation objectivement valide de l'équité de B me paraît douteuse. Oui, nous avons les résultats de certains flips précédents, mais ceux-ci sont toujours cohérents avec toute valeur pourPrB(têtes) dans (0,1). Si en fait cette probabilité est inférieure à1/2, Alors je ne me soucie pas ce que avant que vous choisissez d'adopter: ce sera un fait objectif que le nombre attendu de têtes avec votre approche est moins50.
whuber
Je ne connais pas Mathematica, donc je ne peux pas suivre la façon dont vous avez calculé le nombre de têtes prévu. Voulez-vous expliquer cette partie? Si nous supposons que le biais de la pièce B est tiré d'une distribution uniforme sur [0,1], alors je ne vois pas comment vous pouvez vous attendre à battre 50/50.
jerad
1
Douglas: Parce que j'ai prêté plus d'attention à votre réponse :-). S'il vous plaît, ne vous méprenez pas - je l'aime et j'aime ce fil. J'ai pensé qu'il était important de souligner qu'il fallait ajouter une hypothèse pour obtenir votre réponse, c'est tout. En pratique, dans de nombreuses situations - y compris celle-ci - il n'y a pas de préalable . (Je ne voudrais certainement pas inventer un précédent personnel et ensuite miser gros!) Mais bien sûr, il y a toujours un optimum, à condition de spécifier une fonction de perte. ("Maximiser" une attente n'est pas une fonction de perte complète.)
whuber