I en multi-armad bandit problem, en online algoritm väljer från en uppsättning strategier i en sekvens av n prövningar för att maximera den totala utbetalningen av de valda strategierna. Medan utförandet av bandit algoritmer med en liten ändlig strategi uppsättning är ganska väl förstådd, bandit problem med stora strategiuppsättningar är fortfarande ett ämne för mycket aktiv utredning, motiverade av praktiska tillämpningar såsom online auktioner och webbannonser. Målet med sådan forskning är att identifiera breda och naturliga klasser av strategiuppsättningar och vinstfunktioner som möjliggör utformning av effektiva lösningar. I detta arbete studerar vi en mycket allmän miljö för multi-armad bandit problem där strategierna bildar ett metriska utrymme, och payoff-funktionen uppfyller en Lipschitz villkor med avseende på metriska. Vi hänvisar till detta problem som Lipschitz MAB-problemet. Vi presenterar en fullständig lösning på det flerarmade problemet i denna miljö. Det vill säga, för varje metriska utrymme (L, X) definierar vi en isometry invariant MaxMinCOV(X) som begränsas från under prestanda Lipschitz MAB algoritmer för X, och vi presenterar en algoritm som kommer godtyckligt nära att möta denna gräns. Dessutom ger vår teknik ännu bättre resultat för godartade payoff-funktioner.
I REF, för armar definieras inom ett metriska utrymme och uppfyller en Lipschitz tillstånd, författarna hittade en optimal algoritm som matchar bästa möjliga ånger förhållandet.
Multi-armed bandits in metric spaces
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}