Return to search

Investigating Multi-Objective Reinforcement Learning for Combinatorial Optimization and Scheduling Problems : Feature Identification for multi-objective Reinforcement Learning models / Undersökning av förstärkningsinlärning av flera mål för kombinatorisk optimering och schemaläggningsproblem : Funktionsidentifiering för förstärkningsinlärning av flera mål för kombinatorisk optimering och schemaläggningsproblem

Reinforcement Learning (RL) has in recent years become a core method for sequential decision making in complex dynamical systems, being of great interest to support improvements in scheduling problems. This could prove important to areas in the newer generation of cellular networks. One such area is the base stations scheduler which allocates radio resources to users. This is posed as large-scale optmization problem which needs to be solved in millisecond intervals, while at the same time accounting for multiple, sometimes conflicting, objectives like latency or Quality of Service requirements. In this thesis, multi-objective RL (MORL) solutions are proposed and evaluated in order to identify desired features for novel applications to the scheduling problem. The posed solution classes were tested in common MORL benchmark environments such as Deep Sea Treasure for efficient and informative evaluation of features. It was ultimately tested in environments to solve combinatorial optmization and scheduling problems. The results indicate that outer-loop multi-policy solutions are able to produce models that comply with desired features for scheduling. A multi-policy multi-objective deep Q-network was implemented and showed it can produce an adaptive-at-run-time discrete model, based on an outer-loop approach that calls a single-policy algorithm. The presented approach does not increase in complexity when adding objectives but generally requires larger sampling quantities for convergence. Differing scalarization techniques of the reward was tested, indicating effect on variance that could effect performance in certain environment characteristics. / Försärkningsinlärning som en gångbar metod för sekventiellt beslutsfattande i komplexa dynamiska system har ökat under de senaste åren tack vare förbättrade hårdvaru möjligheter. Intressenter av denna teknik finns bland annat inom telekom-indistrin vars aktörer har som mål att uteveckla nya generationens mobilnätverk. En av de grundläggande funktionerna i en basstation är scheduleraren vars uppgift är att allokera radio resurser till användare i nätverket. Detta ställs med fördel upp som ett optimeringsproblem som nödvändiggör att problemet måste lösas på millisekund nivå samtidigt som den kan ta flera typer av mål i beaktning, såsom QoS krav och latens. I detta examensarbete så presenteras och utvärderas förstärningsinlärnings algoritmer för flera mål inom flera lösningsklasser i syfte att identifiera önskvärda funktioner för nya tillämpningar inom radio resurs schemaläggning. De presenterade lösningsklasserna av algoritmer testades i vanligt förekommande riktmärkesmiljöer för denna typ av teknik såsom Deep Sea Treasure för att på effektivt sätt utvärdera de kvalitéer och funktioner varje algoritm har. Slutligen testades lösningen i miljöer inom kombinatorisk optimering och schemaläggning. Resultaten indikerar att fler-policy lösningar har kapaciteten att producera modeller som ligger inom de krav problemet kräver. Fler-policy modeller baserade på djupa Q-närverk av flera mål kunde framställa adaptiva, diskreta realtidsmodeller. Denna lösning ökar inte komplexiteten när fler mål läggs till men har generellt behov av större mängder samplade preferenser för att konvergera. Olika skaläriseringstekniker av belöningen testades och indikerade att dessa påverkade variansen, vilket i vissa typer av miljö konfigurationer påverkade resultaten.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-325679
Date January 2022
CreatorsFridsén Skogsberg, Rikard
PublisherKTH, Skolan för elektroteknik och datavetenskap (EECS), Stockholm : KTH Royal Institute of Technology
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageSwedish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess
RelationTRITA-EECS-EX ; 2022:920

Page generated in 0.0025 seconds