Signature-Q-learning : a non-markovian reinforcement learning approach

Abstract

Die meisten Methoden des Reinforcement Learning (bestärkendes Lernen) gehen davon aus, dass die zugrunde liegende Umgebung durch einen Markov-Entscheidungsprozess (MDP, Markov Decision Process) beschrieben werden kann, in dem der aktuelle Zustand des Prozesses ausreicht, um eine optimale Strategie zu erlernen. Viele reale Probleme weisen jedoch historienabhängige Dynamiken auf, bei denen Zustandsübergänge und Belohnungen von vergangenen Zuständen und Aktionen abhängen können, sodass MDP-basierte Lernmethoden sich als unzureichend erweisen. Diese Arbeit widmet sich dieser Problematik und entwickelt einen Rahmen für Reinforcement Learning in nicht-Markov'schen Umgebungen. Dazu werden historienbasierte Entscheidungsprozesse (HDP, History-based Decision Process) als formales Modell eingeführt sowie der Signature-Q-Learning-Algorithmus vorgestellt, der Pfadsignaturen nutzt, um optimale Strategien in solchen Umgebungen zu approximieren. Der Hauptteil dieser Arbeit gliedert sich in drei Teile. Zunächst werden in Kapitel 4 historienbasierte Entscheidungsprozesse eingeführt, die den Rahmen der klassischen MDPs erweitern, um Umgebungen mit historienabhängigen Dynamiken zu modellieren. HDPs bieten einen nichtstationären Rahmen mit endlichem Zeithorizont, in dem die Strategie des Agenten nicht nur auf dem aktuellen Zustand, sondern auf der gesamten beobachteten Zustands- und Aktionshistorie beruht. In diesem Modell entwickeln wir ein dynamisches Programmierprinzip für die optimalen Wertfunktionen, in Analogie zu den Bellman-Gleichungen für MDPs, charakterisieren optimale Strategien als solche, die diesem Prinzip genügen, und beweisen deren Existenz. Zweitens wird in Kapitel 5 der Signature-Q-Learning-Algorithmus vorgestellt, eine neue Reinforcement-Learning-Methode für historienabhängige Umgebungen. Dieser basiert auf den universellen Approximationseigenschaften von Pfadsignaturen, einem Konzept, das in der Theorie der rauen Pfade (rough paths) eine wichtige Rolle spielt. Der Algorithmus approximiert die optimale Q-Funktion als lineares Funktional der Pfadsignaturen von beobachteten Zustands-Aktions-Historien und ermöglicht so eine effiziente Repräsentation von zeitlichen Abhängigkeiten. Im Gegensatz zum klassischen Q-Learning in MDPs, das auf einzelnen Zustands-Aktions-Paaren basiert, nutzt Signature-Q-Learning die gesamte Historie und bleibt dabei rechnerisch effizient, indem es gekürzte Pfadsignaturen und eine inkrementelle Aktualisierung auf Basis der Chen-Identität verwendet. Drittens evaluieren wir in Kapitel 6 den Algorithmus anhand zweier numerischer Experimente. Das Erste stellt eine nur teilweise beobachtbare Umgebung dar und zeigt, dass Signature-Q-Learning vergangene Zustände erfolgreich integriert, um das Problem zu lösen. Das Zweite wendet den Algorithmus auf das Problem der Liquidation einer Aktienposition unter Nutzung des ABIDES-Marktsimulators an, in dem historienabhängige Preiseffekte eine wesentliche Rolle spielen. In beiden Fällen lernt Signature-Q-Learning erfolgreich annähernd optimale Strategien, trotz der nicht-markovschen Natur der Umgebungen. Wir analysieren die Auswirkungen der Länge der Signaturekürzung, diskutieren die Überschätzung von Q-Werten und vergleichen die gelernte Strategie mit einer annähernd optimalen Basisstrategie.Diese Arbeit leistet einen Beitrag zur Weiterentwicklung des Reinforcement Learning, indem sie historienbasierte Entscheidungsprozesse als Modellierungsrahmen einführt und das Lernen in historienabhängigen Umgebungen mit der Approximation von Pfadfunktionalen durch die Signatur von Pfaden verbindet. Der vorgeschlagene Algorithmus ist eine modellfreie, online und off-policy Methode und stellt damit ein vielseitiges Werkzeug zur Lösung nicht-markovscher Probleme in verschiedensten Anwendungsbereichen dar. Zukünftige Forschungsschwerpunkte umfassen die Konvergenzanalyse der Methode, eine Verbesserung der Stichprobeneffizienz sowie die Erweiterung des Ansatzes auf kontinuierliche Aktionsräume.

Most reinforcement learning (RL) methods assume that the environment follows Markov Decision Process (MDP) dynamics, where the current state is sufficient for learning an optimal policy. However, many real-world problems exhibit history-dependent characteristics, in which transitions and rewards depend on past states and actions, rendering MDP-based learning methods inadequate. This thesis addresses this challenge, aiming to develop a reinforcement learning framework for non-Markovian environments by introducing History-Based Decision Processes (HDPs) as a model and proposing Signature-Q-Learning, an algorithm that leverages path signatures to approximate optimal policies in history-dependent settings. This thesis's main body is structured into three parts. First, we introduce History-based Decision Processes in Chapter 4, extending the MDP framework to account for history-dependent dynamics. HDPs provide a finite-horizon, non-stationary modeling framework in which an agent’s decision-making is based on observation–action histories rather than individual states. We establish a dynamic programming principle for optimal value functions in HDPs, analogous to the Bellman equations for MDPs. We characterize optimal policies as those that maximize value functions satisfying this principle and prove their existence. Second, in Chapter 5, we propose Signature-Q-Learning, a history-dependent reinforcement learning algorithm based on the universal approximation properties of path signatures, a notion that plays a prominent role in rough path theory. The algorithm formulates the optimal Q-function as a linear functional of the signature of an observation-action history, providing an efficient and expressive representation of temporal dependencies. Unlike traditional Q-learning in MDPs, which operates on state-action pairs, Signature-Q-learning encodes the entire history while maintaining computational efficiency through signature truncation and incremental updates based on Chen’s identity. Third, in Chapter 6, we implement and evaluate the algorithm through two distinct numerical experiments. The first experiment modifies the Mountain Car problem to a partially observable setting, demonstrating that Signature-Q-Learning effectively integrates past observations to solve the problem. The second experiment applies the algorithm to a financial execution problem using the ABIDES market simulator, where history-dependent price impacts play a crucial role. In both cases, Signature-Q-Learning successfully learns policies that maximize rewards despite the non-Markovian nature of the environments. We analyze the effects of signature truncation, discuss the overestimation of Q-values, and compare performance against a baseline policy. This work contributes to reinforcement learning by providing History-based Decision Processes as a novel modeling framework and bridging learning in history-dependent domains with function approximation via path signatures. The proposed method is model-free, online, and off-policy, making it a versatile tool for solving non-Markovian RL problems across various domains. Future research directions include a convergence analysis, improving the method's sample efficiency, and extending it to continuous action spaces.