El problema de la màquina escurabutxaques

El problema de la màquina escurabutxaques es pot esquematitzar de la manera següent:

S'és davant dues màquines escurabutxaques
L'una, $A$ , està en funcionament. Retorna per tant 1 euro per fitxa amb una probabilitat $p_{0}$ coneguda.
L'altra, $B$ , està espatllada, i retorna per tant 1 euro per fitxa amb una probabilitat $p_{1}$ desconeguda.
Es disposa de $N$ fitxes. Què fer per maximitzar raonablement el guany ?

Desbastar el problema

Algunes consideracions permeten evitar l'explosió combinatòria:

Només una aposta a $B$ pot aportar informació i només una aportació d'informació pot portar a canviar d'opinió. Per tant així que es deixa d'apostar per $B$ , s'està segur de no tenir mai motiu de tornar a apostar-hi.
El problema es resumeix en conseqüència en dir quantes fitxes s'apostarà per $B$ , en funció dels resultats, abans de canviar (definitivament) a $A$ o no. És el problema clàssic del disseny d'experiments.

Aplicació practica

L'aplicació més típica del problema de la màquina escurabutxaques és la de la tria entre una antiga i una nova posologia d'una vacuna o medicament (o entre dos diferents): cal determinar el més de pressa possible si el nou producte ha de ser adoptat o s'ha de mantenir l'antic. Tot error es traduiria en vides humanes perdudes (o, pel capbaix, en persones sofrint trastorns o bé a un tractament incomplet, o bé en efectes secundaris excessius).

Bibliografia

Guha, S.; Munagala, K.; Shi, P. «Approximation algorithms for restless bandit problems». Journal of the ACM, 58, 2010, pàg. 1–50. arXiv: 0711.3861. DOI: 10.1145/1870103.1870106.

Michael N. Katehakis «Computing Optimal Sequential Allocation Rules in Clinical Trials». IMS Lecture Notes-Monograph Series, 8, 1986, p. 29–39. DOI: 10.1214/lnms/1215540286.

Vegeu també