This thesis contributes to the field of stochastic bandits by exploring the fundamental limits (information-theoretic lower bounds) of three prevalent objects in various reinforcement learning applications, through a collection of five distinct papers. Each paper presents a novel perspective under a specific structure and scenario. The first paper investigates regret minimization in decentralized multi-agent multi-armed bandits. The second and third papers delve into pure exploration with fixed confidence in a broad spectrum of structured bandits. The last two papers focus on offering new insights into the best arm identification with a fixed budget. 

In the first paper, two popular scenarios in a decentralized multi-agent setting are addressed, one involving collision and the other not. In each of them, we propose an instance-specific optimal algorithm. Interestingly, our results show that the fundamental limits match the ones in the centralized analogue.The second paper introduces a simple but versatile algorithm, Frank-Wolfe Sampling, which achieves instance-specific optimality across a wide collection of pure explorations in structured bandits. Meanwhile, the numerical results and current studies demonstrate the strong numerical performance of our algorithm in various pure exploration problems. However, Frank-Wolfe Sampling is not computationally efficient when the number of arms is extremely large. To address this issue, the third paper introduces Perturbed Frank-Wolfe Sampling, which can be implemented in polynomial time while maintaining the instance-specific minimal sample complexity in combinatorial semi-bandits.

Unlike the sample complexity or regret minimization discussed above, characterizing the fundamental limit of the error probability in best arm identification with a fixed budget remains a challenge. The fourth paper addresses this challenge in two-armed bandits, introducing a new class of algorithms, stable algorithms, which encompass a broad range of reasonable algorithms. We demonstrate that no consistent and stable algorithm surpasses the algorithm that samples each arm evenly, answering the open problems formulated in prior work. In general multi-armed bandits, the final paper in this thesis presents, to our knowledge, the first large deviation theorem for the generic adaptive algorithm. Based on this, we provide the exact analysis of the celebrated algorithm, Successive Rejects. Furthermore, this new large deviation technique allows us to devise and analyze a new adaptive algorithm, which is the current state-of-the-art to the best of our knowledge. This thesis provides new insight for deriving fundamental limits in various online stochastic learning problems. This understanding guides us to develop more efficient algorithms and systems.

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.

Graphs have rich structures at both local and global scales. By exploiting structural properties in certain graph problems, it is possible to design computationally efficient algorithms or refine performance analysis. This thesis is divided into two parts: (i) designing new methods for discovering structure from graphs and (ii) studying the interplay between graphs and combinatorial multi-arm bandits. They differ in how structures are defined, discovered, and utilized. In part (i), we start with a graph-mining problem on signed networks [TOG20], where the graph patterns we aim to detect are groups with mostly positive intragroup edges and mostly negative inter-group edges. We design our objective such that, given a solution, it reflects how well that solution matches the desired pattern. Our proposed algorithm makes no assumptions about the graph. It demonstrates competitive empirical performance in real-world graphs and synthetic graphs. The performance evaluation is conducted through a worst-case analysis, approximating the optimal solution. Moreover, we extend our conflicting group detection [BGG+19, TOG20] as well as other graph-mining tasks (such as fair densest-subgraph detection [ABF+20], two-community detection [New06]) to a memory-limited and pass-limited setting. Under such a setting, Randomized SVD, which has been proposed by [HMT11], is the most preferable method in the memory-limited and pass-limited setting. However, for an input matrix of size n °ø n, it has no guarantee in the o(ln n)-pass regime, which is of most interest to practitioners. We hence derive a tighter analysis [TWA+22] for Randomized SVD for positive semi-definite matrices in any number of passes and for indefinite matrices under certain conditions. Furthermore, we initiate the study of a mixture of Johnson-Lindenstrauss distribution and the 0/1 Bernoulli distribution. We show that this mixture helps make the detection of 2-conflicting groups [BGG+19]

more efficient. In part (ii), we study combinatorial multi-arm bandits problems, where the graph properties play important roles but are somewhat hidden in the optimization problem. Instead, one derives the fundamental limit bounds on either the expected sample complexity or the expected cumulative regret, typically in the informationtheoretical sense, and then explores the abstract properties associated with those bounds to solve the problem satisfactorily, either statistically or computationally.

We focus on combiantorial semi-bandits where the learner observes individual feedbacks for each arm part of the selection. This formulation models many real-world problems, including online ranking [DKC21] in recommendation systems, network routing [CLK+14] in internet service providers, loan assignment [KWA+14], path planning [JMKK21], and influence marketing [Per22]. For best arm identification with fixed confidence, we propose the first polynomial-time algorithm whose sample complexity is instance-specifically optimal in high confidence regime and has polynomial dependency on the number of arms in moderate confidence regime. For regret minimization, we propose the first algorithm whose per-round time complexity is sublinear in the number of arms while matching the instance-specifically gap-dependent lower bound asymptotically.

Grafer har rika strukturer både på lokal och global skala. Genom att utnyttja strukturella egenskaper i vissa grafproblem är det möjligt att designa beräkningsmässigt effektiva algoritmer eller förfina prestandaanalysen. Denna avhandling är uppdelad i två delar: (i) att designa nya metoder för att upptäcka struktur från grafer och (ii) att studera samspelet mellan grafer och kombinatoriska multi-armbanditer. De skiljer sig .t i hur strukturer definieras, upptäcks och utnyttjas.

I del (i) börjar vi med ett grafgruvningsproblem på signerade nätverk [TOG20], där de grafmönster vi siktar på att upptäcka är grupper med mestadels positiva intra-gruppkanter och mestadels negativa inter-gruppkanter. Vi utformar vårt mål så att, givet en lösning, det återspeglar hur väl den lösningen matchar det önskade mönstret. Vår föreslagna algoritm ger inga antaganden om grafen. Den visar konkurrenskraftig empirisk prestanda i verkliga grafer och syntetiska grafer. Prestandautvärderingen genomförs genom en värsta fall-analys, som approximativt finner den optimala lösningen. Dessutom utvidgar vi vår konfliktgruppsdetektion [BGG+19, TOG20] samt andra grafgruvningsuppgifter (såsom rättvis tätaste subgrafdetektion [ABF+20], två-samhällesdetektion [New06]) till en minnesbegränsad och passbegränsad inställning. Under en sådan inställning är Randomized SVD, som föreslagits av [HMT11], den mest föredragna metoden i en minnesbegränsad och passbegränsad inställning. Men för en ingångsmatris av storlek n × n har den ingen garanti i o(ln n)-passregimen, vilket är av största intresse för praktiker. Vi härleder därför en stramare analys [TWA+22] för Randomized SVD för positivt semi-definita matriser i vilket antal pass som helst och för indefinita matriser under vissa villkor. Vidare initierar vi studien av en blandning av Johnson-Lindenstrauss distribution och 0/1 Bernoulli-distributionen. Vi visar att denna blandning hjälper till att göra detektionen av 2-konfliktgrupper [BGG+19] mer effektiv.

I del (ii) studerar vi kombinatoriska multi-arm banditproblem, där grafer- nas egenskaper spelar viktiga roller men är något dolda i optimeringsproblemet. I stället härleder man de fundamentala gränserna för antingen den förväntade provtagningskomplexiteten eller den förväntade kumulativa ånger, vanligtvis i informations-teoretisk mening, och utforskar sedan de abstrakta egenskaperna associerade med dessa gränser för att lösa problemet på ett tillfredsställande sätt, antingen statistiskt eller beräkningsmässigt. Vi fokuserar på kombinatoriska semi-banditer där läraren observerar individuella återkopplingar för varje arm som är en del av urvalet. Denna formulering modellerar många verkliga problem, inklusive online ranking [ DKC21 ] i rekommendationssystem, nätverksrouting [ CLK+14] hos internetleverantörer, lånefördelning [ KWA+14 ], vägplanering [JMKK21 ], och influencer-marknadsföring [ Per22 ]. För bästa armidentifiering med fast förtroende föreslår vi den första polynomtidalgoritmen vars provtagningskomplexitet är instansspecifikt optimal i hög förtroenderegim och har polynomberoende på antalet armar i måttlig förtroenderegim. För ångerminimering föreslår vi den första algoritmen vars per-rundans tidskomplexitet är sublinjär i antalet armar samtidigt som den matchar den instansspecifikt gapberoende nedre gränsen asymptotiskt.