TU Darmstadt / ULB / TUprints

An Ordinal Agent Framework

Joppen, Tobias (2022)
An Ordinal Agent Framework.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00019749
Ph.D. Thesis, Primary publication, Publisher's Version

[img]
Preview
Text
ThesisMainUpdated.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: An Ordinal Agent Framework
Language: English
Referees: Kersting, Prof. Dr. Kristian ; Fürnkranz, Prof. Dr. Johannes
Date: 2022
Place of Publication: Darmstadt
Collation: xii, 105 Seiten
Date of oral examination: 19 March 2021
DOI: 10.26083/tuprints-00019749
Abstract:

In this thesis, we introduce algorithms to solve ordinal multi-armed bandit problems, Monte-Carlo tree search, and reinforcement learning problems. With ordinal problems, an agent does not receive numerical rewards, but ordinal rewards that cope without any distance measure. For humans, it is often hard to define or to determine exact numerical feedback signals but simpler to come up with an ordering over possibilities. For instance, when looking at medical treatment, the ordering patient death < patient ill < patient cured is easy to come up with but it is hard to assign numerical values to them. As most state-of-the-art algorithms rely on numerical operations, they can not be applied in the presence of ordinal rewards. We present a preference-based approach leveraging dueling bandits to sequential decision problems and discuss its disadvantages in terms of sample efficiency and scalability. Following another idea, our final approach to identify optimal arms is based on the comparison of reward distributions using the Borda method. We test this approach on multi-armed bandits, leverage it to Monte-Carlo tree search, and also apply it to reinforcement learning. To do so, we introduce a framework that encapsulates the similarities of the different problem definitions. We test our ordinal algorithms on frameworks like the General Video Game Framework (GVGAI), OpenAI, or synthetic data and compare it to ordinal, numerical, or domain-specific algorithms. Since our algorithms are time-dependent on the number of perceived ordinal rewards, we introduce a binning method that artificially reduces the number of rewards.

Alternative Abstract:
Alternative AbstractLanguage

Diese Arbeit beschäftigt sich mit ordinalen Agenten im Rahmen von mehrarmigen Banditenproblemen, Monte-Carlo Baumsuche und verstärktem Lernen. Dabei liegt das Hauptaugenmerk auf der Einführung neuer Algorithmen, die in der Lage sind ordinale Belohnungen zu verarbeiten. Diese besitzen im Gegensatz zu numerischen Belohnungen kein Distanzmaß, was das Erstellen von Belohnungen für den Menschen oft vereinfacht. Ein beliebtes Beispiel kommt aus dem Bereich der ärztlichen Behandlung, wo die folgenden Konsequenzen leicht in eine Ordnung gebracht werden können: Patient stirbt < Patient krank < Patient geheilt. Den einzelnen Konsequenzen einen schlüssigen numerischen Wert zuzuordnen fällt eher schwer. In dieser Arbeit verfolgen wir zunächst die Idee, Ergebnisse aus dem Bereich der duellierenden Banditen auf sequentielle Entscheidungsprobleme zu übertragen, was aber eine nicht effiziente Verwendung von Belohnungen nach sich zieht. Der stattdessen in dieser Arbeit verwendete Hauptansatz baut auf Wahlsystemen auf (genauer: die Borda Methode) um unterschiedliche Verteilungen von ordinalen Belohnungen zu vergleichen und die beste Option im Stil einer Wahl zu identifizieren. Dazu führen wir ein neues Framework ein, das die unterschiedlichen Problemstellungen vereinheitlicht. Dieser Ansatz wird zunächst auf mehrarmigen Banditenproblemen getestet, folgend auf Monte-Carlo Baumsuche erweitert und weiterhin auf verstärktes Lernen angewendet. Dabei verwenden wir sowohl existierende Testframeworks, wie das General Video Game Framework (GVGAI) und OpenAI als auch synthetische Experimente. In den Experimenten vergleichen wir unsere neuen Algorithmen mit schon existierenden ordinalen Ansätzen, numerischen Algorithmen oder domänenspezifischen Algorithmen wenn möglich. Da unsere neu eingeführten Algorithmen laufzeittechnisch von der Anzahl der unterschiedlichen ordinalen Belohnungen abhängen, stellen wir eine Binning Methode vor, die die Anzahl der Belohnungen künstlich reduziert.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-197490
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Artificial Intelligence and Machine Learning
Date Deposited: 03 Mar 2022 13:25
Last Modified: 03 Mar 2022 13:25
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19749
PPN: 492785880
Export:
Actions (login required)
View Item View Item