TU Darmstadt / ULB / TUbiblio

An Ordinal Agent Framework

Joppen, Tobias (2022)
An Ordinal Agent Framework.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00019749
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (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.

Typ des Eintrags: Dissertation
Erschienen: 2022
Autor(en): Joppen, Tobias
Art des Eintrags: Erstveröffentlichung
Titel: An Ordinal Agent Framework
Sprache: Englisch
Referenten: Kersting, Prof. Dr. Kristian ; Fürnkranz, Prof. Dr. Johannes
Publikationsjahr: 2022
Ort: Darmstadt
Kollation: xii, 105 Seiten
Datum der mündlichen Prüfung: 19 März 2021
DOI: 10.26083/tuprints-00019749
URL / URN: https://tuprints.ulb.tu-darmstadt.de/19749
Kurzbeschreibung (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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
Status: Verlagsversion
URN: urn:nbn:de:tuda-tuprints-197490
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Künstliche Intelligenz und Maschinelles Lernen
Hinterlegungsdatum: 03 Mär 2022 13:25
Letzte Änderung: 04 Mär 2022 11:45
PPN:
Referenten: Kersting, Prof. Dr. Kristian ; Fürnkranz, Prof. Dr. Johannes
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 19 März 2021
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen