Ramverket Multi-Armed Bandits (MAB) belyser spänningen mellan att förvärva ny kunskap (Exploration) och att utnyttja tillgänglig kunskap (Exploitation). I det klassiska MAB problemet måste en beslutsfattare välja en arm varje gång steg, på vilken hon får en belöning. Beslutsfattarens mål är att maximera sin kumulativa förväntade belöning över tidshorisonten. MAB-problemet har studerats i stor utsträckning, särskilt under antagandet att vapnens belöningar är stationära, eller kvasi-stationära, över tiden. Vi anser att en variant av MAB-ramverket, som vi kallade Rotting Bandits, där varje arms förväntade belöning sönderfaller som en funktion av det antal gånger den har dragits. Vi är motiverade av många verkliga scenarier såsom online-reklam, innehållsrekommendation, crowdsourcing med mera. Vi presenterar algoritmer, tillsammans med simuleringar, och härleder teoretiska garantier.
Utmed samma linjer, i ruttnande banditer REF, belöningen på en arm är en minskande funktion av antalet gånger det har spelats i det förflutna.
Rotting Bandits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}