Posterior sampling for reinforcement learning on graphs
File(s)
Published version
Author(s)
Robert, A
Aldo Faisal, A
Pike-Burke, C
Type
Journal Article
Abstract
Many Markov Decision Processes (MDPs) exhibit structure in their state and action spaces that is not exploited. We consider the case where the structure can be modelled using a directed acyclic graph (DAG) composed of nodes and edges. In this case, each node has a state, and the state transition dynamics are influenced by the states and actions at its parent nodes. We propose an MDP framework, Directed Acyclic Markov Decision Process (DAMDP) that formalises this problem, and we develop algorithms to perform planning and learning. Crucially, DAMDPs retain many of the benefits of MDPs, as we can show that Dynamic Programming can find the optimal policy in known DAMDPs. We also demonstrate how to perform Reinforcement Learning in DAMDPs when the transition probabilities and the reward function are unknown. To this end, we derive a posterior sampling-based algorithm that is able to leverage the graph structure to boost learning efficiency. Moreover, we obtain a theoretical bound on the Bayesian regret for this algorithm, which directly shows the efficiency gain from considering the graph structure. We then conclude by empirically demonstrating that by harnessing the DAMDP, our algorithm outperforms traditional posterior sampling for Reinforcement Learning in both a maximum flow problem and a real-world wind farm optimisation task.
Date Issued
2025-03-25
Date Acceptance
2025-03-25
Citation
Transactions on Machine Learning Research, 2025, 2025
ISSN
2835-8856
Publisher
OpenReview
Journal / Book Title
Transactions on Machine Learning Research
Volume
2025
Copyright Statement
Copyright © 2025 The Author(s). This work is licensed under a Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/).
License URL
Publication Status
Published
Article Number
3512
Date Publish Online
2025-03-25