Fundamental Limits in Stochastic Bandits

QC 20240918

Abstract

Denna avhandling bidrar till området för Förstärkningsinlärning (RL) genom att utforska de grundläggande gränserna (informationsteoretiska nedre gränser) för tre vanliga objekt i olika förstärkningsinlärningsapplikationer, genom en samling av fem distinkta uppsatser. Varje uppsats presenterar ett nytt perspektiv under en specifik struktur och scenario. Den första uppsatsen undersöker ångerminimering i decentraliserade multi-agent multi-armed banditer. Den andra och tredje uppsatsen dyker in i ren utforskning med fast förtroende i ett brett spektrum av strukturerade banditer. De två sista uppsatserna fokuserar på att erbjuda nya insikter i identifieringen av den bästa armen med en fast budget. 

I den första uppsatsen behandlas två populära scenarier i en decentraliserad multi-agent inställning, en som involverar kollision och den andra inte. I vardera av dem föreslår vi en instansspecifik optimal algoritm. Intressant nog visar våra resultat att de grundläggande gränserna matchar de som finns i den centraliserade analogin.Den andra uppsatsen introducerar en enkel men mångsidig algoritm, Frank-Wolfe Sampling, som uppnår instansspecifik optimalitet över en bred samling av rena utforskningar i strukturerade banditer. Samtidigt demonstrerar de numeriska resultaten och aktuella studier den starka numeriska prestandan för vår algoritm i olika rena utforskningsproblem. Dock är Frank-Wolfe Sampling inte beräkningsmässigt effektiv när antalet armar är extremt stort. För att lösa detta problem introducerar den tredje uppsatsen Perturbed Frank-Wolfe Sampling, vilket kan implementeras i polynomisk tid samtidigt som den instansspecifika minimala provkomplexiteten bibehålls i kombinatoriska semi-banditer.

Till skillnad från provkomplexitet eller ångerminimering som diskuterats ovan, förblir karaktäriseringen av den grundläggande gränsen för felprocenten vid identifiering av den bästa armen med en fast budget en utmaning. Den fjärde uppsatsen tar upp denna utmaning i två-armede banditer, genom att introducera en ny klass av algoritmer, stabila algoritmer, som omfattar ett brett spektrum av rimliga algoritmer. Vi demonstrerar att ingen konsekvent och stabil algoritm överträffar algoritmen som provtar varje arm jämnt, vilket svarar på de öppna problem som formulerats i tidigare arbete. I allmänna multi-armede banditer presenterar den sista uppsatsen i denna avhandling, till vår kännedom, den första stora avvikelseteoremen för den generiska adaptiva algoritmen. Baserat på detta ger vi den exakta analysen av den berömda algoritmen, Successive Rejects. Dessutom låter denna nya stora avvikelseteknik oss att utforma och analysera en ny adaptiv algoritm, vilket är den nuvarande state-of-the-art till bästa av vår kunskap. Denna avhandling ger ny insikt för att härleda grundläggande gränser i olika online stokastiska inlärningsproblem. Denna förståelse vägleder oss att utveckla mer effektiva algoritmer och system.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-353342