Spelling suggestions: "subject:"flerarmade bandit"" "subject:"flerarmade bandits""
1 |
Graph Bandits : Multi-Armed Bandits with Locality Constraints / Grafbanditer : Flerarmade banditer med lokala restriktionerJohansson, Kasper January 2022 (has links)
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.
|
2 |
Reference Tracking with Adversarial Adaptive Output- Feedback Model Predictive ControlBui, Linda January 2021 (has links)
Model Predictive Control (MPC) is a control strategy based on optimization that handles system constraints explicitly, making it a popular feedback control method in real industrial processes. However, designing this control policy is an expensive operation since an explicit model of the process is required when re-tuning the controller. Another common practical challenge is that not all states are available, which calls for an observer in order to estimate the states, and imposes additional challenges such as satisfying the constraints and conditions that follow. This thesis attempts to address these challenges by extending the novel Adversarial Adaptive Model Predictive Control (AAMPC) algorithm with output-feedback for linear plants without explicit identification. The AAMPC algorithm is an adaptive MPC framework, where results from an adversarial Multi-Armed Bandit (MAB) are applied to a basic model predictive control formulation. The algorithm of the project, Adversarial Adaptive Output-Feedback Model Predictive Control (AAOFMPC), is derived by extending the standard MPC formulation with output-feedback, i.e, to an Output-Feedback Model Predictive Control (OFMPC) scheme, where a Kalman filter is implemented as the observer. Furthermore, the control performance of the extended algorithm is demonstrated with the problem of driving the state to a given reference, in which the performance is evaluated in terms of regret, state estimation errors, and how well the states track their given reference. Experiments are conducted on two discrete-time Linear Time- Invariant (LTI) systems, a second order system and a third order system, that are perturbed with different noise sequences. It is shown that the AAOFMPC performance satisfies the given theoretical bounds and constraints despite larger perturbations. However, it is also shown that the algorithm is not very robust against noise since offsets from the reference values for the state trajectories are observed. Furthermore, there are several tuning parameters of AAOFMPC that need further investigation for optimal performance. / Modell Prediktiv Reglering (MPC) är en optimeringsbaserad reglertekniksmetod som hanterar processbegränsingar på ett systematiskt sätt, vilket gör den till en populär metod inom återkopplad reglering i processindustrin. Denna metod medför dock höga beräkningskostnader eftersom det krävs en explicit modell varje gång regulatorn justeras online. I praktiken är det också vanligt att alla tillståndsvariabler inte är tillgängliga, vilket kräver en observatör för att rekonstruera alla tillståndsvariabler. Detta leder till fler utmaningar som att uppfylla ytterligare systembegränsingar och villkor som följer. Detta projekt adresserar dessa utmaningar genom att förlänga den nya algoritmen Adversarial Adaptiv Modell Prediktiv Reglering (AAMPC) med output-feedback för linjära system utan explicit modellidentifiering. AAMPC-algoritmen är en adaptiv reglerstrategi där resultat från en adversarial multiarmed bandit (MAB) appliceras i en standard MPC-formulering. Denna MPC-formulering är förlängd med output-feedback dvs. Output-Feedback Modell Predktiv Reglering (OFMPC) där ett Kalman filter är implementerad som en observatör och resulterar i projektets algoritm: Adversarial Adaptiv Output- Feedback Modell Prediktiv Reglering (AAOFMPC). Vidare demonstreras den utökade algoritmens prestanda med problemet att driva tillståndsvariablerna till ett givet referensvärde, där prestandan evalueras i termer av regret, skattningsfel och hur väl tillståndsvariablerna följer de givna referensvärdena. Experiment utförs på två tidsdiskreta tidsinvarianta (LTI) system, ett andraordningssystem och ett tredjeordningssystem, som är perturberade med olika värden av brus. Resultaten visar att AAOFMPC:s prestanda uppfyller de givna teoretiska begränsningarna trots större störningar. Det visar sig dock att algoritmen inte är särskilt robust mot brus eftersom det sker avvikelser från de givna referensvärdena för tillståndsvariablerna. Dessutom finns det flera parametrar i algoritmen som kräver ytterligare utredningar för optimal prestanda.
|
Page generated in 0.0832 seconds