Efficient Exploration and Robustness in Controlled Dynamical Systems

• In this thesis, we explore two distinct topics. The first part of the thesis delves into efficient exploration in  multi-task bandit models and model-free exploration in large Markov decision processes (MDPs). This section is driven by the recent research community's interest in uncovering optimal methods to navigate complex decision-making problems. In the second part, we examine attack vectors against MDPs and dynamical systems, which is motivated by the research community's recent push to enhance the safety of Machine Learning models against malicious attacks.  Additionally, we explore how to quantify uncertainty in an off-policy evaluation problem,  reflecting our ongoing efforts to deepen understanding in this domain. In the first part of the thesis, we present an investigation into the sample complexity of identifying the optimal arm in multi-task bandit problems. In this setting, an agent can select a task and efficiently learn through cross-task knowledge transfer. We derive instance-specific lower bounds that any probably approximately correct (PAC) algorithm should satisfy, revealing both theoretically and empirically significant improvements in scaling over previous methods. Subsequently, we investigate model-free exploration in Reinforcement Learning (RL) problems. By leveraging an information-theoretical viewpoint, we focus on the instance-specific lower bound for the number of samples needed to identify a nearly-optimal policy. We develop an approximation of this lower bound involving quantities that can be inferred using model-free approaches. This leads to a new model-free exploration strategy applicable to  continuous MDPs. In the second part of the thesis, we begin by investigating two types of attacks on MDPs: those that alter the observations and those that manipulate the control signals of the victim. We present strategies for designing optimal attacks to minimize the collected reward of the victim. Our strategies show how uncertainties induced by the attack can be modeled using a partially observable MDP (POMDP) framework. We also illustrate how to devise attacks that achieve lower detectability, approaching the problem from a statistical detection perspective. Next, we explore the problem of an eavesdropper aiming to detect changes in an MDP. Approaching this problem from a statistical detection perspective, we introduce a novel definition of online privacy based on the average amount of information per observation of the underlying stochastic system. We derive privacy upper bounds and calculate policies that attain higher privacy levels, supplementing our analysis with examples and numerical simulations. Finally, we present a new off-policy estimation method based on Conformal Prediction that outputs an interval containing the target policy's true reward, demonstrating how to handle the distribution shift between target and behavior policies, and maintain the certainty level while reducing the interval length.Next, we shift our focus onto linear dynamical systems. We study poisoning attacks on data-driven control methods, focusing on how slight changes in the dataset induced by an adversary can significantly deteriorate control methods and potentially destabilize the system. We propose a novel algorithm for computing effective attacks, providing a theoretical basis for our strategy. We also study the detectability of poisoning attacks, focusing on the impact of data poisoning on least-squares estimates. We establish conditions under which the set of models compatible with the data includes the true model of the system, and we analyze different poisoning strategies for the attacker. On the basis of the arguments presented herein, we propose a stealthy data poisoning attack on the least-squares estimator that can evade classical statistical tests. 

• I denna avhandling undersöker vi två distinkta ämnen. Den första delen av avhandlingen handlar om effektiv utforskning i multi-uppgift banditmodeller och modellfri utforskning i stora Markov beslutsprocesser (MDP). Detta avsnitt drivs av forskningsvärldens intresse på senaste tiden för att upptäcka optimala metoder för att navigera komplexa beslutsproblem. I den andra delen undersöker vi attackvektorer mot MDP:er och dynamiska system, vilket motiveras av forskningsvärldens senaste satsning på att förbättra säkerheten för maskininlärningsmodeller mot illvilliga attacker. Dessutom utforskar vi hur man kvantifierar osäkerhet i ett off-policy utvärderingsproblem, vilket speglar våra pågående insatser för att fördjupa förståelsen inom detta område.I den första delen av avhandlingen presenterar vi en undersökning av provkomplexiteten vid identifiering av den optimala armen i multi-uppgift banditproblem. I denna miljö kan en agent välja en uppgift och effektivt lära sig genom överföring av kunskap mellan uppgifter. Vi härleder instansspecifika undre gränser som varje sannolikt ungefärligt korrekt (PAC) algoritm bör uppfylla, vilket visar både teoretiskt och empiriskt betydande förbättringar i skalning jämfört med tidigare metoder. Därefter undersöker vi modellfri utforskning i förstärkningsinlärningsproblem (RL). Genom att använda ett informationsteoretiskt perspektiv fokuserar vi på den instansspecifika undre gränsen för det antal prover som behövs för att identifiera en nästan optimal policy. Vi utvecklar en approximation av denna undre gräns med kvantiteter som kan härledas med modellfria metoder. Detta leder till en ny modellfri utforskningsstrategi som är tillämplig på kontinuerliga MDP:er.I den andra delen av avhandlingen börjar vi med att undersöka två typer av attacker på MDP:er: de som ändrar observationerna och de som manipulerar offrets kontrollsignaler. Vi presenterar strategier för att utforma optimala attacker som minimerar den belöning som offret samlar in. Våra strategier visar hur osäkerheter som induceras av attacken kan modelleras med hjälp av ett ramverk för delvis observerbara MDP. Vi illustrerar också hur man utformar attacker med lägre detekterbarhet, genom att närma sig problemet ur ett statistiskt detektionsperspektiv. Därefter utforskar vi problemet med en avlyssnare som försöker upptäcka förändringar i en MDP. Genom att närma oss detta problem ur ett statistiskt detektionsperspektiv introducerar vi en ny definition av online-integritet baserad på den genomsnittliga informationsmängden per observation av det underliggande stokastiska systemet. Vi härleder övre gränser för integritet och beräknar policies som uppnår högre integritetsnivåer, och kompletterar vår analys med exempel och numeriska simuleringar. Slutligen presenterar vi en ny off-policy skattningsmetod baserad på konform prediktion som ger ett intervall som innehåller målpolicyns sanna belöning, och visar hur man hanterar fördelningsförskjutningen mellan mål och beteenderpolicy:er, samt bibehåller säkerhetsnivån samtidigt som intervallängden minskar.Därefter flyttar vi vårt fokus till linjära dynamiska system. Vi studerar förgiftningsattacker på datadrivna kontrollmetoder, med fokus på hur små förändringar i datasetet som induceras av en motståndare kan försämra kontrollmetoderna avsevärt och potentiellt destabilisera systemet. Vi föreslår en ny algoritm för att beräkna effektiva attacker och ger en teoretisk grund för vår strategi. Vi studerar även detekterbarheten av förgiftningsattacker, med fokus på datagiftets påverkan på minsta kvadratskattningar. Vi fastställer villkor under vilka mängden modeller som är kompatibla med datan inkluderar systemets sanna modell, och vi analyserar olika förgiftningsstrategier för angriparen. Baserat på de argument som presenteras här föreslår vi en smygande datagiftsattack på minsta kvadratuppskattaren som kan undgå klassiska statistiska tester.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Reglerteknik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Control Engineering (hsv//eng)

Nyckelord

reinforcement learning

efficient exploration

bandit algorithms

adversarial attacks

conformal prediction

data posioning

markov decision processes

attack detectability

optimal control

adaptive control

Electrical Engineering

Elektro- och systemteknik

Datalogi

Computer Science

Mathematical Statistics

Matematisk statistik

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)