De flesta kontextuella banditalgoritmer minimerar ånger till den bästa fasta policy-ett tvivelaktigt riktmärke för icke-stationära miljöer allmänt förekommande i applikationer. I detta arbete får vi effektiva kontextuella banditalgoritmer med starka garantier för alternativa föreställningar om ånger anpassade till dessa icke-stationära miljöer. Två av våra algoritmer utrustar befintliga metoder för i.i.d problem med sofistikerade statistiska tester, dynamiskt anpassa sig till en förändring i distribution. Den tredje metoden använder en ny teknik för att kombinera flera bandit algoritmer, med varje kopia börjar på en annan runda för att lära sig över olika datasegment. Vi analyserar flera föreställningar om ånger för dessa metoder, inklusive de första resultaten på dynamisk ånger för effektiva kontextuella banditalgoritmer. antaganden och studera lämpliga generaliseringar av ånger från i.i.d. till icke-stationära miljöer. Vi börjar med att modifiera den enklaste kontextuella banditalgoritmen, EPOCH-GREEDY [16], för att arbeta i icke-stationära inställningar. 1 Vi anpassar ytterligare den statistiskt och beräkningsmässigt optimala metoden för Agarwal et al. [1] till denna inställning också. Båda våra ändringar, ADA-GREEDY och ADA-ILTCB, sond för den längsta perioden i det förflutna där datadistributionen ser ungefär i.i.d., och beräkna en fördelning över policyer baserade på den perioden. Det exakta testet är algoritmspecifikt och bygger på att verifiera vissa koncentrationsojämlikheter som algoritmen förlitar sig på, men den allmänna idén kan vara tillämplig på att utöka andra kontextuella banditalgoritmer också.
Nyligen studerade Luo et al REF det icke-stationära banditproblemet och föreslog flera banditalgoritmer med statistiska tester för att anpassa sig till förändringar i miljön.
Efficient Contextual Bandits in Non-stationary Worlds
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}