Bayes-Adaptive Semi-Markov Decision Processes: A Pathway to Optimal Learning in Sequential Decision Making with Time under Uncertainty

Abstract

In many real-world situations, sequential decision-making demands not only managing environmental uncertainty but also accounting for the stochastic nature of timing, as events unravel unpredictably over time. Traditional reinforcement learning models often struggle in these contexts, specifically in effectively learning the sojourn time distributions and grappling with uncertainties about the environment's dynamics. This thesis addresses these challenges by delivering two key contributions: a novel solver for partially observable semi-Markov decision processes (POSMDPs) and the development of the Bayes-adaptive semi-Markov decision processes (BA-SMDPs) framework. Both tools significantly extend reinforcement learning capabilities, catering to problems where timing is crucial.

Our first major contribution is ChronosPerseus, an innovative POSMDP solver that combines the strengths of point-based value iteration and importance sampling to effectively handle a wide array of problem types. We designed this solver to handle episodic and non-episodic problems, mixed observability, discrete or continuous observation spaces, and a mixture of fixed and stochastic continuous sojourn times. ChronosPerseus represents a significant stride in tackling reinforcement learning problems involving timing.

Simultaneously, we introduce BA-SMDPs, a novel Bayesian reinforcement learning framework specifically designed for optimally learning the policy in problems of sequential decision-making under uncertainty. The heart of BA-SMDPs lies in the intricate interplay between timing, environmental exploration, and exploitation of current knowledge. Notably, we demonstrate that BA-SMDPs can be expressed as POSMDPs, enabling the application of ChronosPerseus for BA-SMDPs and thereby further broadening its utility.

Within the BA-SMDPs framework, we explore four distinct approaches: learning the sojourn time distribution parameters from a finite set of sojourn times; learning mixtures of known sojourn time distributions with unknown proportions; learning mixtures of known SMDPs with unknown proportions; and learning unknown continuous sojourn-time distribution parameters. Further, we contribute a conjugate prior for the mean parameter of the inverse Gaussian sojourn-time distribution, enhancing our ability to track the uncertainty of SMDP parameters whilst finding an optimal policy.

This thesis substantively contributes to reinforcement learning research, particularly in contexts where timing is essential. It provides a robust foundation for further exploration, such as examining the implications of an unknown reward function within the BA-SMDP framework. It also encourages the application of the developed frameworks and algorithms to a wider array of complex real-world problems, inviting both theoretical advancements and practical applications that can significantly impact various societal sectors. In essence, this work proposes powerful new tools and frameworks for reinforcement learning when timing is stochastic, opening the door to more nuanced and effective solutions in the field.

Dans de nombreuses situations réelles la prise de décision séquentielle exige non seulement de gérer l'incertitude environnementale mais aussi de tenir compte de la nature stochastique du temps puisque les événements se déroulent de manière temporellement imprévisible. Les modèles traditionnels d'apprentissage par renforcement ont souvent des difficultés dans ces contextes, notamment en ce qui concerne l'apprentissage efficace des distributions de temps de séjour et la prise en compte des incertitudes relatives à la dynamique de l'environnement. Cette thèse aborde ces défis en apportant deux contributions clés : un nouveau solveur pour les processus de décision semi-markoviens partiellement observables (POSMDP) et le développement d’un cadre décisionnel pour les processus de décision semi-markoviens adaptatifs de Bayes (BA-SMDP). Ces deux outils étendent considérablement les capacités d'apprentissage par renforcement en s’adressant aux problèmes où le temps est crucial.

Notre première contribution majeure est ChronosPerseus, un solveur POSMDP innovant qui combine les forces de l'itération de la valeur par évaluations ponctuelles et de l'échantillonnage par importance pour traiter efficacement un large éventail de types de problèmes. Nous avons conçu ce solveur pour traiter les problèmes épisodiques et non épisodiques, l'observabilité mixte, les espaces d'observation discrets ou continus, et un mélange de temps de séjour fixes et stochastiques continus. ChronosPerseus représente une avancée significative dans la résolution des problèmes d'apprentissage par renforcement impliquant le temps.

Simultanément, nous présentons le BA-SMDP, un nouveau cadre d'apprentissage par renforcement bayésien spécialement conçu pour l'apprentissage optimal de la politique décisionnelle dans les problèmes de prise de décision séquentielle en présence d'incertitude. Le cœur des BA-SMDP réside dans l'interaction complexe entre l’élément temporel, l'exploration de l'environnement et l'exploitation des connaissances actuelles. Nous démontrons notamment que les BA-SMDP peuvent être exprimés comme des POSMDP, ce qui permet d'appliquer ChronosPerseus aux BA-SMDP et d'élargir ainsi son utilité.

Dans le cadre des BA-SMDP nous explorons quatre approches distinctes : l'apprentissage des paramètres de la distribution des temps de séjour à partir d’un nombre fini d’échantillonnage ; l'apprentissage des proportions inconnues de l’apport de distributions de temps de séjour connues ; l'apprentissage de mélanges de SMDP connus avec des proportions inconnues ; et l'apprentissage des paramètres inconnus d’une distribution de temps de séjour continus. De plus, nous apportons une loi a priori conjuguée pour le paramètre moyen de la distribution inverse gaussienne du temps de séjour, améliorant ainsi notre capacité de gérer l'incertitude des paramètres du SMDP tout en trouvant une politique décisionnelle optimale.

Cette thèse apporte une contribution substantielle à la recherche sur l'apprentissage par renforcement en particulier dans les contextes où le temps est essentiel. Elle fournit une base solide pour des explorations ultérieures tel que l'examen des impactes d'une fonction de récompense inconnue dans le cadre du BA-SMDP. Elle encourage également l'application des cadres et algorithmes existants à un plus large éventail de problèmes complexes du monde réel, invitant à la fois à des avancées théoriques et des applications pratiques qui peuvent avoir un impact important dans de nombreux secteurs de la société. Fondamentalement, ce travail propose de nouveaux outils et cadres puissants pour l'apprentissage par renforcement lorsque le temps est stochastique ouvrant ainsi la voie à des solutions plus nuancées et plus efficaces dans ce domaine.