Vi anser en kombinatorisk generalisering av det klassiska multi-armade banditproblemet som definieras enligt följande. Det finns ett givet bipartitdiagram över M-användare och N ≥ M-resurser. För varje användarresurspar (i, j) finns det ett associerat tillstånd som utvecklas som en periodisk irreducerbar finit-state Markov-kedja med okända parametrar, med övergångar som sker varje gång den specifika användaren i tilldelas resurs j. Användaren i får en belöning som beror på motsvarande tillstånd varje gång den tilldelas resursen j. Systemets mål är att lära sig den bästa matchningen av användare till resurser så att den långsiktiga summan av de belöningar som tas emot av alla användare maximeras. Detta motsvarar minimerande ånger, definieras här som gapet mellan den förväntade totala belöningen som kan erhållas genom bästa möjliga statiska matchning och den förväntade totala belöningen som kan uppnås med en viss algoritm. Vi presenterar en polynom-lagring och polynom-komplexitet-per-steg matchning-lärande algoritm för detta problem. Vi visar att denna algoritm kan uppnå en ånger som är jämnt godtyckligt nära logaritmisk i tid och polynom i antalet användare och resurser. Denna formulering är allmänt tillämplig på schemaläggning och byte av problem i kommunikationsnät inklusive kognitiva radionät och avsevärt utökar tidigare resultat i området. 978-1-4244-9268-8/11/$26.00 ©2011 IEEE Detta dokument i fulltext granskades mot bakgrund av IEEE Communications Societys ämnesexperter för publicering i IEEE Globecom-förfarandet 2011.
Referensreferensreferensdokumentet presenterade den ungerska MU-MAB-policyn för problemet med att lära sig kombinatoriska matchningar mellan användare och resurser.
On the Combinatorial Multi-Armed Bandit Problem with Markovian Rewards
{'venue': '2011 IEEE Global Telecommunications Conference - GLOBECOM 2011', 'journal': '2011 IEEE Global Telecommunications Conference - GLOBECOM 2011', 'mag_field_of_study': ['Computer Science', 'Mathematics']}