Grafbanditer : Flerarmade banditer med lokala restriktioner

Multi-armed bandits (MABs) have been studied extensively in the literature and have applications in a wealth of domains, including recommendation systems, dynamic pricing, and investment management. On the one hand, the current MAB literature largely seems to focus on the setting where each arm is available to play at each time step, and ignores how agents move between the arms. On the other hand, there is work that takes the movement between arms into account, but this work models the problem as a Markov decision process and applies generic reinforcement learning (RL) algorithms, like Q-learning. This thesis examines an extension of the MAB problem to a setting where the set of available arms at each round depends on which arm was played in the previous round. In this formulation the arms are nodes in a graph, and arms that can be played successively are connected via edges. We denote this the Graph Bandit (GB) problem. We show that under certain conditions the optimal action is governed by a stationary policy. Furthermore, we develop an algorithm that leverages the graphical structure of the problem to find this policy when the reward distributions are perfectly known, and denote this algorithm the Q-graph. When the reward distributions are unknown, we show how to leverage the Qgraph algorithm together with standard sampling algorithms like Thompson sampling and upper confidence bound to create an online learning algorithm that provably achieves logarithmic regret. Finally, this regret-bound is supported in numerical simulations, and it is illustrated how the proposed Q-graph algorithm outperforms generic algorithms from the MAB and RL communities.Flerarmade banditer (FAB) har studerats omfattande i litteraturen och har applikationer inom en mängd domäner, såsom rekommendationssystem, dynamisk prissättning och finans. Å ena sidan verkar det som at en stor del av litteraturen fokuserar på situationen där alla armar är tillgängliga att spela vid varje tidssteg och ignorerar hur agenten rör sig mellan armarna. Å andra sidan finns det arbete som tar till hänsyn hur agenten rör sig mellan armarna men det arbetet modellerar systemet som en Markovprocess och använder sig av generiska inlärningsmetoder, såsom Q-learning. Den här uppsatsen undersöker en utvidgning av FAB-problemet till en situation där mängden tillgänliga armar vid varje runda beror på vilken arm som spelades i den föregående rundan. I denna formulering är armarna noder i en graf och armar som kan spelas i på varandra följande rundor är anslutna via kanter. Vi kallar det här problemt Grafbanditen. Vi visar att under vissa förutsättningar bestäms det optimala aggerandet av en stationär policy. Vi utvecklar också en algoritm som utnyttjar den grafiska strukturen i problemet för att beräkna denna policy när distributionerna hos alla armar är kända. Denna algoritm får namnet Q-grafen. När distributionerna är okända visar vi hur Q-grafen kan användas tillsammans med Thompson sampling eller upper confidence bound-metoder för att skapa en online inlärningsalgoritm som bevisligen uppnår logaritmisk regret. Slutligen stöds de teoretiska resultaten via numeriska simuleringar som illustrerar att Q-grafen är överlägsen många generiska inlärningsalgoritmer