Många sekventiella beslutsproblem i kommunikationsnät som energiallokering i energiskördarkommunikation, mobil beräkningsavlastning och dynamiskt kanalval kan modelleras som kontextuella banditproblem som är naturliga förlängningar av det välkända multiarmade banditproblemet. I dessa problem kan varje resursfördelnings- eller urvalsbeslut använda sig av tillgänglig sidoinformation, t.ex. avverkad effekt, specifikationer för de arbetstillfällen som ska avlastas eller antalet paket som ska överföras. I kontextuella bandit problem, vid varje steg i en sekvens av prövningar, en agent observerar sidan information eller sammanhang, drar en arm och får belöningen för den armen. Vi anser att den stokastiska formuleringen där sammanhangsbelönade tuples är oberoende dras från en okänd distribution i varje försök. Målet är att utforma strategier för att minimera den förväntade kumulativa ånger eller belöning förlust jämfört med en distribution-medveten ande. Vi analyserar en miljö där belöningen är en känd icke-linjär funktion i sammanhanget och den valda armens nuvarande tillstånd vilket är fallet med många nätverksapplikationer. Denna kunskap om belöningsfunktionen gör det möjligt för oss att utnyttja den erhållna belöningsinformationen för att lära oss om belöningar för andra möjliga sammanhang. Vi först överväga fallet med diskreta och finita sammanhang-rymder och föreslå DCB ( ), en algoritm som ger ångra som skalar logaritmiskt i tid och linjärt i antalet armar som inte är optimal för något sammanhang. Detta är i kontrast till befintliga algoritmer där ångra skalor linjärt i det totala antalet armar. Lagringskraven för DCB ( ) växer inte heller med tiden. DCB( ) är en utvidgning av UCB1-policyn för standardmultiarmade banditer till kontextuella banditer med hjälp av sofistikerade bevistekniker för ångeranalys. Vi studerar sedan kontinuerliga kontext-rymder med Lipschitz belöning funktioner och föreslår CCB (, δ), en algoritm som använder DCB ( ) som en subrutin. CCB(, δ) avslöjar en ny ånger-lagring kompromiss som parametriseras av δ. Tuning δ till tidshorisonten gör att vi kan få sub-linjära ånger gränser, samtidigt som det kräver sub-linjär lagring. Gemensam inlärning för alla sammanhang resulterar i beklaga gränser som är ouppnåeliga av någon befintlig kontextuell bandit algoritm för kontinuerliga sammanhang-rymder. Liknande prestandagränser visas också hålla för okända horisont fall genom att använda en dubblering trick. Sammanhangsbanditer, multi-armade banditer (MABs), online-inlärning.
Den DCB ( ) algoritm som presenteras i REF, dock antar att kartläggning från sammanhanget och slumpmässiga instans till belöningen är en känd funktion och använder denna funktion kunskap för att minska den förväntade ånger.
Stochastic Contextual Bandits with Known Reward Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}