Vi definierar en allmän ram för en stor klass av combinatorial multi-armad bandit (CMAB) problem, där undergrupper av basarmar med okända distributioner bildar super armar. I varje omgång spelas en superarm och basarmarna i superarmen spelas och deras utfall observeras. Vi överväger vidare den förlängning där mer baserade vapen kan utlösas probabilistiskt på grundval av resultaten av redan utlösta vapen. Belöningen av superarmen beror på resultatet av alla spelade armar, och det behöver bara uppfylla två milda antaganden, som tillåter en stor klass av icke-linjära belöningsfall. Vi antar tillgängligheten av en offline (α, β) - approximation oracle som tar medel för resultatet fördelningar av armar och ger en super arm som med sannolikhet β genererar en α-fraktion av den optimala förväntade belöningen. Målet med en online-lärande algoritm för CMAB är att minimera (α, β) - approximation ånger, vilket är skillnaden i total förväntad belöning mellan αβ-fraktionen av förväntad belöning när alltid spela den optimala super armen, och den förväntade belöningen att spela super armar enligt algoritmen. Vi tillhandahåller CUCB algoritm som uppnår O(log n) distributionsberoende ånger, där n är antalet spelade rundor, och vi ger ytterligare distributionsoberoende gränser för en stor klass av belöningsfunktioner. Vår ångeranalys är snäv eftersom den matchar gränsen för UCB1-algoritm (upp till en konstant faktor) för det klassiska MAB-problemet, och den avsevärt förbättrar den ånger som är bunden i en nyligen publicerad tidning om kombinatoriska banditer med linjära belöningar. Vi tillämpar vårt CMAB ramverk för två nya applikationer, probabilistisk maximal täckning (PMC) för online-reklam och socialt inflytande maximering för viral marknadsföring, båda har icke-linjära belöning strukturer. I synnerhet, tillämpning på socialt inflytande maximering kräver vår förlängning på probabilistiskt utlösta armar. Nyckelord: combinatorial multi-armad bandit, online-inlärning, övre förtroende bundna, socialt inflytande maximization, online-reklam. * En preliminär version av detta dokument visas i ICML'2013 (Chen et al., 2013. Den nuvarande versionen innehåller utvidgningen av CMAB för att rymma probabilistiskt utlösta armar och dess tillämpning på socialt inflytande maximering.
Chen och Al. REF föreslog en algoritm för dessa problem och begränsade sitt beklagande.
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}