An Information-Theoretic Approach to Bandits and Reinforcement Learning
Tid: Må 2025-12-15 kl 13.15
Plats: F3, Flodis, Lindstedtvägen 26
Videolänk: https://kth-se.zoom.us/j/61173029059
Språk: Engelska
Respondent: Amaury Gouverneur , Teknisk informationsvetenskap
Opponent: Research Assistant Professor Gergely Neu, Universitat Pompeu Fabra, Barcelona, Spain
Handledare: Professor Mikael Skoglund, Teknisk informationsvetenskap; Professor Tobias J. Oechtering, Teknisk informationsvetenskap
QC 20251124
Abstract
I denna avhandling utvecklar och utvidgar vi informationsteoretiska metoder för att analysera förstärkningsinlärning (eng: reinforcement learning), med särskilt fokus på banditproblem (eng: bandits). Vårt mål är att förstå hur inlärningsalgoritmer hanterar den grundläggande avvägningen mellan utforskning (eng: exploration) och exploatering (eng: exploitation), och hur informationsteoretiska storheter såsom entropi och ömsesidig information (eng: mutual information) kan användas för att karakterisera och begränsa deras prestanda. Med utgångspunkt i ramverket av Russo och Van Roy, som relaterar en algoritms Bayesianska ånger (eng: Bayesian regret) till dess inlärningseffektivitet mätt genom den så kallade informationskvoten (eng: information ratio), härleder vi nya resultat som utvidgar detta angreppssätt till mer komplexa och strukturerade inlärningsproblem.
Den första delen av avhandlingen återbesöker analysen av linjära banditer, en modell där belöningar beror linjärt på den valda handlingen via en okänd parameter. Även om befintliga informationsteoretiska analyser ger generella ångergränser, förutsätter de alltid ett ändligt handlingsutrymme. Vi fyller denna lucka genom att introducera förfinade analyser som visar att nära-optimala ångergränser kan uppnås även för oändliga eller kontinuerliga handlingsutrymmen.
Den andra delen av avhandlingen utvidgar det informationsteoretiska analysramverket till mer komplexa bandit-modeller. I den kontextuella bandit-miljön bygger vi vidare på den så kallade upplyfta informationskvoten (eng: lifted information ratio) och visar hur denna kan tillämpas för ett bredare spektrum av belöningsmodeller. Därtill tillhandahåller vi alternativa bevis baserade på klassiska informationsteoretiska verktyg, vilket förenklar analysen och möjliggör skarpare garantier för strukturerade problem. Vi studerar därefter Thompson Sampling-algoritmen för logistiska banditer, en centralt använd modell för binära belöningar. Här härleder vi de första ångergränserna som undviker det tidigare nödvändiga exponentiella beroendet av den logistiska lutningsparametern och som dessutom är oberoende av antalet handlingar, vilket löser en länge öppen fråga i området.
Den tredje delen av avhandlingen går bortom bandit-modeller och undersöker hur informationsteoretiska principer kan generaliseras till mer allmänna problem inom förstärkningsinlärning. Vi analyserar teoretiska prestandagränser och inlärningsgarantier för modellbaserad förstärkningsinlärning och etablerar ett ramverk för att studera dess Bayesianska ånger. Parallellt härleder vi PAC-Bayesianska gränser för offline-beslutsfattande (eng: offline decision-making), inklusive förbättrade garantier för offline banditer som är parameterfria och uppnår nära-optimala konvergenshastigheter.
Sammantaget presenterar avhandlingen en sammanhängande och bred utvidgning av informationsteoretisk analys till ett stort spektrum av inlärningsmiljöer: från linjära till icke-linjära modeller, från diskreta till kontinuerliga handlingsutrymmen, och från banditer till allmän förstärkningsinlärning.