<style> .reveal section img { background:none; border:none; box-shadow:none; } .reveal { font-size: 30px; } .reveal p { text-align: left; } .reveal ul { display: block; } .reveal ol { display: block; } </style> # Exploració versus Explotació ## Taller Nous Usos de la Informàtica <center><img width="150" src="https://i.imgur.com/vvZMy0I.png"></center> --- <center><img width="350" src="https://i.imgur.com/2kJm6qu.png.png"></center> --- ## L'escenari Imaginem el següent escenari: + Suposem que cada vegada que arriba un usuari al nostre *web site* podem oferir-li una opció que triarem entre les $n$ opcions que tenim disponibles en aquell moment (anuncis, circuits de vacances, iteneraris d'avió, etc.). + Un cop oferta l'opció, i en funció de l'*acció* de l'usuari, rebem una *recompensa* que es pot representar numèricament (que pot ser simplement si ha estat seleccionada o no, el preu que paga o no l'usuari per aquella opció, etc.). + Suposem que la recompensa per cada opció es pot modelar com una funció estacionària de probabilitats (és a dir, la recompensa és una variable aleatòria, no és la mateixa per totes les ofertes, com és el cas d'una màquina escurabutxaques). --- ## L'objectiu Si el nostre objectiu és maximitzar la recompensa total al cap del temps i *coneguéssim* la mitjana de la recompensa real de cada acció (coneixement que en general no és possible tenir), triariem oferir sempre la millor acció. Aquest seria l'algorisme òptim, $A_{opt}$. Un objectiu interessant i més realista en aquest escenari és trobar un algorisme $A$ que maximitzi la **recompensa total esperada sobre un periode de temps** $T$ (per exemple, sobre 1000 accions). A cada una de les accions l'anomenem *jugada*. Vist des d'un altre punt de vista: volem minimitzar una mesura de *penediment* (*regret*), el total de recompenses que perdem pel fet de no realitzar sempre la millor acció, després de $T$ accions: $$ R(T) = \mbox{Guanys}_{A_{opt}}(T) - \mbox{Guanys}_{A}(T) $$ --- ## El problema + Aquesta formulació es coneix com el problema dels *n-armed bandits*, o de les *màquines escurabutxaques amb $n$ actuadors*, per analogia amb les màquines escurabutxaques o *one-armed bandit* (que tenen només un actuador i en les que només hem de decidir si volem continuar jugant). + En el nostre cas, cada acció té una *recompensa esperada* o *recompensa mitja* donada l'acció que es selecciona. Aquest concepte s'anomena *valor* de l'acció. + Si sabéssim el valor de cada acció la solució del problema seria trivial i consistiria en seleccionar sempre l'acció amb més valor. + En el nostre cas no saben el valor real de cada acció, **però en podem tenir estimacions a mesura que anem jugant**! --- ## El problema En una situació concreta, la tria entre *explotar* (triar l'acció que **creiem** que dóna més recompenses) o *explorar* (millorar les nostres estimacions sobre el valor de les altres recompenses) depèn d'una forma complexa de: + Els valors específics de les estimacions + Les incerteses sobre aquestes estimacions + El nombre de jugades que ens queden per fer. De totes maneres, veurem que és possible definir polítiques que trobin un bon balanç entre les dues possibilitats i millorin l'explotació pura en la immensa majoria dels casos. --- ## Mètodes d'acció-valor Primer hem de veure com estimar els valors de les accions i com usar aquestes estimacions per decidir quina acció seleccionem. + Anomenem $Q^*(a)$ al valor real de l'acció $a$, que és desconegut. Recordem que aquest valor és la mitja de les recompenses rebudes quan seleccionem aquesta acció. + Anomenem $Q_t(a)$ al seu valor estimat després de $t$ jugades. --- ## Mètodes d'acció-valor + Si suposem que fins a la jugada $t$ l'acció $a$ ha estat seleccionada $k_a$ vegades i hem obtingut unes recompenses $r_1 + r_2 + \dots r_{t}$, la forma natural d'estimar $Q_t(a)$ és: $$ Q_t(a) = \frac{r_1 + r_2 + \dots + r_{k_a}}{k_a} $$ --- ## Mètodes d'acció-valor + En el cas que $k_a=0$ definim $Q_t(a)$ amb un valor inicial tal com $Q_0(a)=0$. + Llavors, a mesura que $k_a \rightarrow \infty$, per la llei dels grans nombres, sabem que $Q_t(a)$ tendirà a $Q^*(a)$. + A aquest mètode l'anomenem el mètode de **la mostra promitjada** atès que per estimar els valors de les accions fem una simple mitja de les recompenses relacionades. --- ## Mètodes d'acció-valor: explotació ingènua + A partir d'aquí podriem pensar (de forma incorrecta) que el millor algorisme és: + Fer $t$ jugades per estimar el valor estimat de cada acció, + A partir d'aleshores, triar l'acció amb el valor estimat més alt, o dit d'una altra manera, seleccionar a partir de la jugada $t+1$ l'acció voraç $a^*$: $$Q_t(a^*) = max_a Q_t(a)$$ + Aquest mètode explota el coneixement que hem adquirit fins a la jugada $t$ per maximitzar la recompensa, però perd molt valor durant el periode fins a realitzar el total de les accions. --- ## Mètodes d'acció-valor: exploració-explotació + Una possible alternativa és actuar de forma voraç la majoria de vegades però de tant en tant, amb una petita probabilitat $\epsilon$, seleccionar una altra acció de forma uniformement aleatòria, independentment de les estimacions d'acció-valor. + Aquests darrers mètodes s'anomenen $\epsilon$-voraços. + Una propietat d'aquests mètodes (que no compleix el mètode anterior) és que a mesura que augmenta el nombre de jugades cada una de les accions serà mostrejada un nombre infinit de vegades, garantint que $k_a \rightarrow \infty$ per totes les $a$ i per tant assegurant que $Q_t(a)$ convergeix a $Q^*(a)$. --- ## Mètodes d'acció-valor A la gràfica de la pàgina següent podem veure el resultat del següent experiment: + S'han generat 2000 problemes de forma aleatòria amb $n=10$. + Els valors de les accions dels 2000 problemes s'han generat seleccionant les $Q^*(a)$ segons una distribució normal amb mitja 0 i variança 1. + Per cada acció $a$ que triem la recompensa es genera d'una distribució de probabilitats Gaussiana amb mitja $Q^*(a)$ i variança 1. + Si fem la mitja sobre les tasques, podem visualitzar l'eficiència i comportament dels mètodes a mesura que van estimants durant les primeres 1000 jugades. --- ## Mètodes d'acció-valor <center><img width="650" src="https://i.imgur.com/AtcmPby.png"></center> --- ## Mètodes d'acció-valor + Tot i que els mètodes $\epsilon$-voraços són simples i efectius per balancejar l'exploració i l'explotació, podem tenir un petit defecte: quan exploren trien de forma aleatòria entre totes les accions **per igual**. És a dir, té les mateixes probabilitats la pitjor que la més semblant a la millor. + La sol·lució obvia a aquest problema podria ser triar les accions segons una funció que les distribueixi en funció del seu valor estimat. --- ## Mètodes d'acció-valor + Aquesta estratègia s'anomena **mètode del softmax** (amb temperatura). + El mètode escull una acció $a$ a la jugada $t$ segons aquesta distribució de probabilitats: $$ \frac{e^{Q_t(a)/\tau}}{\sum_{b=1}^n e^{ Q_t(b)/\tau}} $$ + $\tau$ és un paràmetre positiu anomenat *temperatura*. --- ## Mètode Softmax + Temperatures altes ($\tau \rightarrow \infty$) fan que les accions siguin equiprobables (distribució uniforme) i per tant totes tenen la mateixa probabilitat de ser explorades. + Quan $\tau \rightarrow 0$ tenim el cas voraç pur i només explotem la que creiem més valuosa.  --- ## Implementació incremental de $Q_t(a)$ Fins ara hem estimat els valors de les accions com a mitjanes de les recompenses observades amb l'expressió: $$ Q_t(a) = \frac{r_1 + r_2 + \dots + r_{k_a}}{k_a} $$ El problema amb aquesta fòrmula és que els requeriments de memòria i càlcul creixen amb el temps, atès que hem de recalcular aquesta expressió a cada pas per cada acció $a$ i hem d'anar guardant la llista dels valors $(r_1, \dots, r_{k})$ per cada acció, que va creixent. --- ## Implementació incremental de $Q_t(a)$ + Sigui $Q_k$ la mitja de les seves primeres $k$ recompenses. Llavors, quan obtenim la recompensa $k+1$, $r_{k+1}$, podem calcular la mitja de les $k+1$ recompenses com: \begin{eqnarray*} Q_{k+1} & = & \frac{1}{k+1} \sum_{i=1}^{k+1} r_i =\frac{1}{k+1} \left( r_{k+1} + \sum_{i=1}^k r_i \right) \\ & = & \frac{1}{k+1} \left( r_{k+1} + kQ_k + Q_k - Q_k \right) \\ & = & \frac{1}{k+1} \left( r_{k+1} + (k+1) Q_k - Q_k \right) = Q_k + \frac{1}{k+1} \left( r_{k+1} - Q_k \right) \end{eqnarray*} + Aquesta expressió serveix fins i tot per $k=0$ i dona $Q_1=r_1$ per un $Q_0$ arbitrari. --- ## Implementació incremental de $Q_t(a)$ Aquesta formulació incremental segueix una forma general interessant: $$ NovaEst \leftarrow EstimacioAnt + MidaPas[ValorActual - EstimacioAnt] $$ + La part $[ValorActual - EstimacioAnt]$ es pot interpretar com l'error de l'estimació i per tant el mètode el que fa és fer un pas en la direcció del valor actual (en el nostre cas, el valor actual és la recompensa $r_{k+1}$). + Tal i com ho hem formulat, la mida del pas, que es pot escriure com $\alpha_k(a)$, canvia a cada pas: quan processem la recompensa $k$ de l'acció $a$ el mètode usa una mida $\frac{1}{k}$. Això ho fa per mantenir el pes de totes les recompenses igualat quan fa la mitjana. --- ## El cas dels problemes no estacionaris + Si la distribució de recompenses va variant amb el temps (**cas no estacionari**) no té sentit estimar les recompenses com ho fem, amb el mateix pes: hem de donar més pes a les més recents. + Una manera d'implementar això és usar una mida de pas constant a l'equació. Per exemple: $$ Q_{k+1} = Q_k + \alpha \left( r_{k+1} - Q_k \right) $$ + En aquest cas, decidim que la mida del pas, $\alpha$, $0 < \alpha \leq 1$, és constant. --- ## El cas dels problemes no estacionaris + Això resulta en una fórmula on $Q_k$ és una mitja ponderada de les recompenses passades i de l'estimació inicial $Q_0$: \begin{eqnarray*} Q_{k} & = & Q_{k-1} + \alpha\left[ r_{k} - Q_{k-1} \right] \\ & = & \alpha r_k + (1- \alpha) Q_{k-1} \\ & = & \alpha r_k + (1- \alpha) \alpha r_{k-1} + (1 - \alpha)^2 Q_{k-2} \\ & = & \alpha r_k + (1- \alpha) \alpha r_{k-1} + (1 - \alpha)^2 \alpha r_{k-2} + \dots \\ & & + (1- \alpha)^{k-1} \alpha r_1 + (1- \alpha)^{k} \alpha Q_0 \\ & = & (1 - \alpha)^k Q_0 + \sum_{i=1}^k \alpha (1 - \alpha)^{k-i} r_i \end{eqnarray*} --- ## El cas dels problemes no estacionaris + Això és una mitja ponderada perquè la suma dels pesos és $(1 - \alpha^k) + \sum_{i=1}^k \alpha (1 - \alpha)^{k-i} = 1$, tal i com es pot comprovar. + El pes de la recompensa $r_i$, $\alpha (1 - \alpha)^{k-i}$, va decreixent *exponencialment* en funció a mesura que el nombre de recompenses augmenta (que és el que voliem!). --- ## Incertesa dels valors estimats Suposem ara que tenim $k$ accions i les seves recompenses estimades després de $t$ accions, $Q_{t}(a)$. Cada una d'aquestes accions $a$ ha estat estimada fent una mitjana formada per diversos valors. Estadísticament, podriem calcular l'incertesa de cada una d'aquestes mitjanes. És útil incorporar aquesta incertesa en el procés d'exploració? --- ## Incertesa dels valors estimats Suposem tres valors estimats $\mu_a$ i les seves incerteses $u_a$: + $5 \pm 1$ + $4.5 \pm 2$ + $1 \pm 3$ Quina acció es podria triar? + En règim d'**explotació pura**, la primera, perquè és la que té el valor estimat més gran. + En règim d'**exploració pura**, la tercera, que és la més incerta. --- ## UCB1 L'interessant és trobar una via intermitja que no ens obligui a triar el règim i vagi variant de forma automàtica entre els dos. + L'algorisme UCB1 (*Upper Confidence Bound*) fa la següent tria: escollirem l'acció $a^*$ tal que: $$ a^* = \arg\max_a (\mu_a + u_a) $$ + En el nostre cas, és la segona acció: $4.5 \pm 2$. --- ## UCB1 Per calcular l'incertesa s'usa una expressió basada en la cota de Hoeffding: $$ Q_t(a) \pm \sqrt{\frac{2 \ln t}{t_a}} $$ on $t$ és el nombre d'accions totals que hem fet fins el moment i $t_a$ és el nombre de vegades que s'ha mostrejat l'acció $a$: + Cada cop que seleccionem l'acció $a$, $t_a$ es fa més gran i l'incertesa disminueix. + Cada cop que seleccionem una acció que no és $a$, $t$ es fa més gran, però amb un ordre logaritmic (cada cop menys). --- ## UCB1 En la teoria de la probabilitat, la cota de Hoeffding proporciona un **límit superior a la probabilitat que la suma de les variables aleatòries independents es desviï del seu valor esperat en més d'una certa quantitat**. Tot això fa que convergeixi a seleccionar la millor acció al cap d'un temps! --- ## UCB1 <center><img width="750" src="https://i.imgur.com/7Xz7qtX.png"></center> --- ## Thomson sampling El mètode **Thomson Sampling** modela la incertesa mitjançant la construcció d'una distribució de probabilitat a partir de recompenses històriques i després, a cada pas, mostreja aquesta distribució per triar les accions. En el cas senzill en què **les recompenses són binàries** (per exemple, click versus no-click), s'utilitza una distribució Beta. --- ## Thomson sampling En teoria de la probabilitat i estadística, la distribució beta és una família de distribucions de probabilitat contínues **definides en l'interval $[0, 1]$**, parametritzades per dos paràmetres de forma, denotats $\alpha$ i $\beta$, que apareixen com a exponents de la variable aleatòria i controlen la forma de la distribució. <center><img width="450" src="https://i.imgur.com/inSaT8O.png"></center> --- ## Thomson sampling El valor mig de la distribució és $\alpha/(\alpha+\beta)$, que representa el nombre de "recompenses positives" dividit per "recompenses positives+recompenses no positives". Per seleccionar una acció, prenem una mostra de cada opció segons els seus paràmetres i escollim l'acció amb el valor màxim. --- ## Thomson sampling Abans de començar, inicialitzarem els paràmetres de la funció Beta a $\alpha=1$ i $\beta=1$, que correspon a una distribució uniforme entre 0 i 1. <center><img width="350" src="https://i.imgur.com/Vs03iPo.png"></center> --- ## Thomson sampling Una altra avantatja de la funció Beta és la simplicitat de la seva actualització després de fer una acció. Quan obtenim una recompensa després d'una acció $a$ (que en el cas binari és $r_{t+1}=1$) o no (que en el cas binari és $r_{t+1}=0$), els paràmetres de la funció Beta de l'acció es poden actualitzar així: $$\alpha_{r_{t+1}} (a) = \alpha_{r_{t}} (a) + r_{t+1} \\ \beta_{r_{t+1}} (a) = \beta_{r_{t}} (a) + 1 - r_{t+1}$$ --- ## Thomson sampling A mesura que recollim més dades, $\alpha$ i $\beta$ augmenten. Com a resultat, la distribució Beta es fa més estreta i obtenim més certesa en la nostra estimació del valor. <center><img width="450" src="https://i.imgur.com/vBlqVnr.jpg"></center> Amb una distribució més estreta, els nostres valors mostrejats estaran més a prop de la mitjana, reduint així l'exploració i augmentant l'explotació. --- ## Aplicació de l'algorisme de Thomson sampling Suposant que cada possible acció $a_i$ està representada per la seva funció Beta ($Beta(a_i)$), a cada pas de l'algorisme fem: + Generem, per cada $a_i$, un valor aleatori $v_{a_i}$ segons la funció $Beta(a_i)$. + Executem l'acció $i$ tal que $v_{a_i}$ té el valor màxim d'entre els generats. + Recalculem les $Beta(a_i)$ per totes les possibles accions. En la majoria de casos, aquesta estratègia és millor que la UCB1. --- ## Conclusions + L'ús de la incertesa produeix millor mètodes: Els mètodes UCB i Thomson Sampling són en general millor que els mètodes $\epsilon$-greedy. + Quan la informació sobre la recompensa **es retarda**, Thompson Sampling supera UCB. Aquesta retroalimentació retardada, on les interaccions usuari-element no es processen immediatament, és habitual per a la majoria de sistemes del món real (com per exemple les màquines escurabutxaques). + En aquesta situació, com que la UCB selecciona les armes de manera determinista, tria la mateixa acció fins que s'incorpora una nova retroalimentació. En canvi, com que Thompson Sampling tria les accions de manera estocàstica mitjançant el mostreig de la distribució posterior, aleatoritza les accions fins i tot sense recompenses actualitzades. --- ## Aplicacions + Posar el millor anunci a una pàgina web quan no sabem "el valor" dels anuncis que tenim en cartera. + Assaig clínic per determinar el millor tractament d'una malaltia. + Escollir el millor servidor en una granja d'ordinadors per fer una tasca. + Portafolis financers (inversions). + *Pricing* dinàmic. + Recomanació, quan el nombre d'ítems no és molt gran. En aquest context també podem aplicar una variació dels mètodes vistos, *contextual bandits*, que incorpora informació sobre els ítems.