Il problema del multi-armed bandit: hai diverse opzioni (“bracci”) con tassi di ricompensa ignoti, e una sequenza di scelte da fare. Ogni scelta dà informazione, ma comporta anche il costo di non aver scelto meglio.
Il trade-off
- Exploit: scegli l’opzione che al momento sembra migliore. Guadagni subito, ma potresti sbagliarti.
- Explore: scegli un’opzione su cui sei incerto. Guadagni meno ora, ma migliori le scelte future.
Una divisione fissa 50/50 ignora questo trade-off. Un algoritmo bandit lo risolve esplicitamente.
Regret
Il modo standard di valutare una strategia bandit è il regret: la differenza cumulata tra le ricompense ottenute e quelle che avresti ottenuto scegliendo sempre il braccio migliore.
- Divisione equa → il regret cresce linearmente con il numero di visitatori: paghi il divario su ognuno di essi.
- Thompson Sampling → il regret cresce logaritmicamente, che è il meglio ottenibile nel caso generale.
Nella pubblicità
Ogni variante di landing page è un braccio; ogni visitatore è una scelta; la ricompensa è un lead. È per questo che l’allocazione bandit si adatta al traffico meglio del test a campione fisso — vedi Thompson Sampling.
Termini correlati
- Thompson Sampling — l’algoritmo
- A/B testing — l’alternativa classica