Posterior Sampling for Reinforcement Learning on Graphs
Authors: Arnaud Robert
Aldo A. Faisal
Ciara Pike-Burke
Venue: Accepted by TMLR ()

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, \emph{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.

Published in Transactions on Machine Learning Research (03/2025)
Posterior Sampling for Reinforcement Learning on Graphs
Arnaud Robert Department of Computing Imperial College London
a.rober1200@mmperiidl.ccc
A. Aldo Faisal
a.foisal@imperial.ccm
Deportment Computing Imperial College London
Ciara Pike-Burke Department of Mathematics Imperial College London
c.p.lee-burkee@@mprrid... uk
Reviewed on OpenReview: https: // openreview. net/ forum? id= kd6CfmdPfx
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 directed acyelic 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 Dy- namic Programming can find the optimal policy known DAMDPs. We also demonstrate how to perform Reinforcement Learning in DAMDPs when the transition probabilities and the reward function unknown. To this end, we derive posterior sampling- based algo- rithm that is able to leverage the graph structure to boost learning efficiency. Morcover, 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 poste- rior sampling for Reinforcement Learning in both maximum flow problem and real-world wind farm optimisation task.
1 Introduction
Reinforcement. Learning (RI.) algorithms are typically used to solve Markov Decision Processes (MDPs), general model for sequential decision-making under uncertainty in which the state of the environment only depends on what happened in the previous time step. There exist many online reinforcement learning approaches for finding an optimal policy in an unknown MDP (e.g. Watkins & Dayan (1922); Sutton et al. (1999): Auer al. (2008); Azar et al. (201)); Strens (2000)). However, these methods tend to be quite general and do not make any assumptions beyond the MDP structure. This generality means that while these methods be applied to most MDP problems, they will fail to exploit any additional structure present in the problem and, such, can be sub-optimal in specific cases.
In this paper, we consider a special case of Markov Decision Processes in which the enviromment's 's dependency structure is encoded in a directed acyelic graph. In such setting, the state space can be decomposed into the state the nodes of the graph, and the reward and transitions depend on the connectivity of each node. In particular, the state at each node of the graph will depend on the state and action taken all its parent nodes.

---

Published in Transactions on Machine Learning Research (03/2025)
This structure is present in lot of real-world settings. For example, in wind farm optimisation, e.g. Abkar et al. (2023), a grid of rotating wind turbines creates stream of turbulence that impacts the yield of downstream wind turbines. The turbulence at downstream wind turbines depends on the orientation of the upstream wind turbines. Finding the optimal orientation of all wind turbines in the wind farm becomes an interesting control problem. Since the turbines' locations are known, the interaction pattern between all turbines composing the farm is also known. This interaction pattern can be encoded as a directed acyclic graph, where each node represents a wind turbine and each edge indicates a potential interaction. The graph structure consider also covers any problem formulated as a maximum flow problem (i.e. network routing Mammeri (2019) or supply chain management Rolf et al. (2023) ). Such problems are typically modelled as directed acyelic graphs where the state at each node depends on the action taken at the parent nodes, and we observe the outcome of the actions al the parent nodes before laking actions at the child nodes.
This paper will show that leveraging this latent graphical structure can significantly improve performance, both in thoory and practice. We develop Postcrior Sampling algorithm that effectively exploits graphical structures. We empirically show that the proposed algorithm outperforms algorit hms that ignore the latent structure. We also theoretically validate the improved efficiency of the proposed algorithm through an upper bound on the Bayesian regret. This analysis is achieved by a careful analysis of the proposed algorithm, which breaks down the combinatorial structure of the state and action spaces and reuses repeated patterns within the graph. Note that while there are some similarities between the DAMDPs that we consider and the Factored MDP (FMDP) framework (Boutilier et al. 2000), there are significant differences that necessitate further innovation. As elaborated in Section 7 the main difference is that FMDPs consider a time-homogeneous setting, where the state factorisation remains the same for every time step. On the other hand, we consider a time inhomogencous sctting where the factorisation structure might change over time; this allows us to capture more complex and realistic graph structures.
Contribution: To demonstrate the efficiency gains from leveraging a latent graphical structure, we start by formalizing the sub-class of MDPs we focus on and then show that when the transition function and rewards are known, a dynamic programming approach can be applied to find an optimal policy. When the rewards and transitions are unknown, we develop a posterior sampling algorithm and show an upper bound its Bayesian regret. This upper bound demonstrates
improvement compared to methods that ignore the latent graphical structure, such Auer et al. (2008); Osband et al (013)). We also provide empirical validation of our method's performance gain, first on a maximum flow problem and then wind farm optimization problem. To summarize, this paper proposes, analyses and evaluates a novel posterior sampling algorithm specifically designed to exploit the graphical structure present in many real-world problems.
2 Background
Before we introduce our decision-making framework, it is helpful to recall the foundations of Markov Decision Processes and Directed Acyclic Graphs.
2.1 Fixed-Horizon Markov Decision Process
(R.) (P.)) H. p). We consider finite time-dependent state spaces S, and action spaces A, for E (1...., H}. The mean reward function is defined by R, S, x A, + [0, 1] for all agent observes a reward Rs a.) + nr where T) are independent identically distributed sub-Gaussian noise (a 1). The probability of reaching a specific state $141 E S when action a, E Ar was performed in state 8 E S, is determined by (1 18t, at). The agent interacts with the environment during episodes of length H, and in each episode, the initial state 81 ~ p is drawn from the initial state distribution. For the following H time steps, E (1,..., HH), the agent observes a state 8, E S, and decides to perform an action a; the result of this action is immediately observed as a new state St41 P(((|st. az) and an immediate reward R2 (St, 0z) nt-
A fixed-horizon time-inhomogeneous MDP is a tuple M = ([S.)
[H]. In state 8t, after performing action d,, the
2

---

Published in Transactions on Machine Learning Research (03/2025)
Reinforcement learning algorithms aim to find policies Me St + A, for all E {1,... ,H} that maximise the cumulative reward over an episode. We measure this in terms of the value function:
H Σ
Vi E
Rs (sn,aa))) an) an pm(sp)) 8041 Pa(-lon an), = s)
(1)
where the expectation is taken the stochastic transition dynamics 81+1 the quality of policy in terms of the value function of the initial state 31, Val1 (s1), where the superscript M indicates that we compute the value in the MDP M. The aim is to find an optimal policy μ²' within the set of Markov deterministic policies II, which maximizes the value function,
0n)- Often, we evaluate
1 E arg max (s1).
(2)
Hell
It is also helpful to define the Q-function the expected reward the policy can obtain given that at time t in state 8t E S₁ the action 0r E A, is exccuted, Qu,r(st, 4:) = re(st, + P( at) 1.441 (8141). (8t))))))))))
V.
2.2 Directed Acyclic Graphs
Definition 2.1 (Directed Acyclic Graph). A directed acyclic graph (DAG) G (V, is defined by set of vertices V and set of edges E. Each edge has a direction associated with it The graph is said to be acyclic if there is no node for which there exists a path (with one or more edges) that leads to itself.
For any DAG, there is corresponding topological ordering of the nodes (Bang-Jensen & Gutin 2008 Sec. 2.3.2). It assigns a layer to each node; the layer of a node is equal to the length of the longest path from the root to the current node. If the DAG does not have a root we can trivially add an artificial node that serves as a root. In this work, we consider this form of layered directed acyclic graphs, whose edges only connect nodes from adjacent layers.
Definition 2.2 (Layered Directed Acyclic Graphs). A Layered, Directed Acyclic Graph (LDAG) is a DAG with a specific topology. Tt has a unique root node and a unique leaf node. All nodes are organised in layers, and all edges go from one layer to the next. Edges between nodes of the same layer are not allowed, as well as edges that connect nodes that are two or more layers away.
With layered directed acyclic graph, it is clear that all edges go from layer to a layer / + with e {1,..., H 1}. Larger steps, backward steps, and transversal steps (within the same layer) are not allowed. Note that the assumption of LDAG does not lose any generality. We show in Appendix G. that for any DAG, we can construct an LDAG. Since the corresponding LDAG conserves the same connectivity patterns, such transformation has a limited impact on the complexity measure considered in this article. We illustrate and discuss this point further in Appendix G
3 Directed Acyclic Markov Decision Process
We consider a particular sub-class of MDPs that can be rolled out on an LDAG. We define a Directed Acyelic Markov Decision Process (DAMDP) as a tuple Mg = (X, 1 (r An illustration of a simple DAMDP is given the leftmast plot of Figure D Critically, in addition to the MDP components (described below), a DAMDP Mc is structured by an LDAG, G. The nodes of an LDAG, G, can be organized in layers. A node belongs to a layer if the shortest path from root node to the current node is of length l. The execution of episode consists of graph traversal from the first layer to the last layer of G. Each node has its own state, and the original MDP state can be recovered by combining all nodes' states of the current layer. The horizon H of the DAMDP corresponds to the number of layers in G = EV, since we sequentially observe the graph's layers. Edges e E E connect a node from a layer to a node in layer + 1, for some I E (1.... H 1). At each time step, a layer of nodes of G describes the current state of the DAMDP: that is, in layer 1, the ny nodes that compose this layer describe the full state at time step I. For each layer i, we consider an arbitrary ordering of its nodes {1, ,n));
= [ H H, ( G).
J=1
3

---

Published in Transactions on Machine Learning Research (03/2025)
Directed Acyclic MDP
Time steps
Full states
2
4
82
83
t=3
Atomic actions
Reward contexts
Transition Contexts
Depending on outgoing edges)
Depending on outgoing edges)
Depending on incoming edges)
For nodes:
2
3
For nodes:
For nodes:
C(x) E C1
V1
(I,y) E X x 31
For node:
For node:
For node:
(z,8) X 3
C(x) E C2
Figure 1: Illustration of the important components of DAMDPs. Inside the top leftmost box is an illustration of a simple DAMDP, Mc. The underlying graph has four nodes, which are visited within three time steps, I = (1, 2,3) as depicted on the second box of the top row. The last box of the top row illustrates the full state representation of MG- At time step f, the full state 8; consists of the concatenation of the observations each node in layer The leftmost box of the bottom row shows the atomic action; in this particular example, the dimensionality of the atomic action space depends atomic action lies in }1 if the node has single outgoing edge, if the node has two outgoing edges the alomic action lies in )2. The second box of the bottom row depicts the two atomic reward contexts that arise in Ma, which are composed of the alomic slate and the alomic action y of the current node. The last box of the bottom row shows the two atomic transition contexts that arise in Mc. which consists of the atomic states and atomic actions observed at the current node, x x's, parents (i.c. nodes from the previous time step). Consequently, the transition function of node depends the number of incoming edges.
the number of outgoing edges, i.c. the

---

Published in Transactions on Machine Learning Research (03/2025)
which remains fixed for the entirety of the training. The edges of G encode the dependence between different nodes. In a DAMDP, each node of G has an alomic stale I, where x belongs to the alomic state space X. In general, the atomic state space X' is smaller than the original state space S for any time step t E [.]]. More precisely, the original state space St can be recovered by combining all the atomic state space of the tth layer nodes. Similarly, at each node, we can perform an alomic action y E ) where { denote the Ur different atomic action space:] For a given time step t E [H], and a node v E [mx] in layer i, which is in atomic state zy, if the agent perform the atomic action y E y), it receives a reward r (x², vf") + Te,, where (ar vi") is the mean atomic reward function associated with the jth atomic action space Vi, and We is i.i.d. sub-gaussian noise. Here, and throughout, V E {1,... .n.. denotes the position of the current node in its layer, and we use the notation zy and yi to refer to the ythh atomic state and action in the 1 layer. If two nodes have the same number of parents and if their parents have the same atomic action spaces, then these two nodes obey the same dynamics and are said to belong to the same transition equivalence class [ri], with i E {1.-..U,) U and U, the number of equivalence classes. Formally, this implies that the dynamics of nodes that belong to the same equivalence class [r:] are governed by the same atomic transition distribution p'(-lc), with e the transition context, which consists of the atomic state and actions at all parent nodes. Hence, nodes with the same number of incoming edges have the same transition function. Concretely, lct's consider the 4h node of layer L and assume that. this node belongs to the equivalence class [Tv...]: where we use the notation o,, denote the index of the equivalence class that node e in layer t belongs to. The atomic state at this node is drawn from the atomic transition function x. ~ =p't. (-Ic7). The transition context of E C.,.. consists of the concatenation of all parent's 's nodes atomic states and atomic actions. We denote by e.,, the space of all possible transition contexts, and note that this is the same for all nodes in the same equivalence class. We denote by NT"' the set containing the parent nodes of the node v in the 8th layer, then the space of transition contexts for the 7th equivalence class is, C, = DDEN; X' x V the Cartesian product of all possible configuration of the parent nodes atomic states and atomic actions. Finally, the initial atomic state components are sampled from initial atomic state distribution oi ~ 9% for all nodes of the initial layer of G, V (1.....,.) .113
We now illustrate the concepts introduced in this section with two practical examples. The key difference between the two examples lies in the construction of the atomic action spaces. The first example considers a single atomic action space Y for all nodes. While the second example considers that the atomic action space of a node depends on the number of outgoing edges, hence there are U, different atomic action spaces and (3))/=.
Wind farm yield optimisation: Optimisation of wind farm yield an interesting control problem that can be modelled as DAMDP. The extraction of kinetic energy and the interactions between the wind and the turbine's physical structure decrease the wind speed and increase the intensity of the turbulence in a wake region downstream of the wind turbine (Sedaghatizadch et al., 2018). This wake effect impacts the yield of the downstream turbine. It is, however, possible to deflect this effect by modifying the yaw angle, the angle between the wind direction and the turbine head. While this can impact the turbine's immediate yield, it improves the wind conditions downstream and, consequently, the yield of the wind turbine in the original wake region. There is an optimal set of yaw angles that maximises the wind farm's total yield for given farm layout and atmospheric conditions. When modelling this problem as a DAMDP, the graph G= G=(V, E) encodes potential interactions between wind turbines. Each node, V V, represents a wind turbine in the farm. If an edge exists between node U1 E V and node v2 E V, it indicates that the wake effect of wind turbine 11 might impact wind turbine Uy. The alomic stale space, X, consists of the atmospheric conditions observed at a specific wind turbine. Similarly, the atomic action, V, characterises the yaw angle (i.e. the angle between the wind turbine and the upstream wind direction). Note that the atomic action space is the same for all nodes, reflecting the fact that all wind turbines can be configured with the same set of yaw angles. The atomic reward r(=;;, vE) observed at the node in layer i is the yield of the corresponding wind turbine. In this example, the atomic reward context (z) vf) consists of the current node's atomic state x. E X' and alomic actions yi E y. Alomic transitions functions, p² (r(c), determine the alomic state E X
In some applications, the atomic action description can be tightly linked the number of outgoing edges at each node, hence is natural consider models where there are several different atomic action spaces.
5

---

Published in Transactions on Machine Learning Research (03/2025)
based on the atomic transition context (i.e. the parent nodes atomic states and actions), c E C, where C; = 8 DEEA&& &' x V, with N the set of parent nodes.
The maximum leaky flow problem Wayne 1999 is defined as a directed acyclic graph G = -V, with a single root node, the source node en E VV, and single leaf node, called the sink node UN E V. Using edges to transport flow from one node to the next, the goal is to transport as much flow as possible from the source node to the sink node. Because G is directed, it is only possible to transport flow in the edge's direction. Two parameters govern the environment: edges have given capacity, <> O, which denotes the maximum amount of flow that can be transported along that edge, and an unknown failure probability, E [0, I], which dictates how likely the edge is to fail to transport the flow assigned to it. This environment can also be modelled as a DAMDP. More specifically, the latent graph is G, and the atomic states space, X, describe the amount of incoming flow in each node, The atomic action spaces, (D5))/11 describe the proportion of incoming flow to assign to each outgoing edge. Note, this particular problem instance, the alomic action space Di depends on the number of outgoing edges j E [U+]. Indeed, to specify how to distribute the flow among n edges necessitates 11 entries. The atomic reward r (x],, v() is proportional to the amount of flow sent to the next layer by a node. The atomic reward context (x,, then consists of the node's atomic state xς E X' and actions yi E D/j- Similarly, the transition function, p' (r|c), computes the distribution of flow al a node given its transition context. The transition context of a node, c E C, consists of its parent's atomic states x E X which represent the amount of flow received at each parent node and cach parent's atomic action which is the proportion of flow they assign to the current node's incoming edges. Section 6.1 discusses this setting in more detail and includes visualization of several problem instances (see Fig.
Maximimum leaky flow:
3.1 Relationship between DAMDPs and MDPs
A DAMDP Mc = (x, ( (r') ( PA: G) is special case of finite horizon MDP, where the stale and action spaces are time-dependent, but the atomic dynamics are stationary. While the number of nodes and the connection patterns might vary from one layer to the next, the atomic reward function and the atomic transition function behaviours remain unchanged. Below, we discuss the relationship between MG and the corresponding MDP M constructed from the atomic components and the graph G.
The execution of a DAMDP episode is tightly linked to the graph G. Since the graph is laycrod, directed and acyelic, cach layer corresponds to time step in the corresponding MDP M. Hence, the depth H of the graph corresponds to the MDP's horizon. After executing K episodes, the total number of time steps is T = HK.
Time step and horizon:
State space: In any time step t, the full state E S2 is composed of the atomic state at each node in the graph's tth layer. Formally, in layer t we observe = [x], "[",, where xa is the observation collected in the 4h node of layer f (see Fig. [ middle box) and n, denotes the number of nodes in layer t. For simplicity, we assume that each node has the same atomic state space, X. Then the full state space at time step & the Cartesian product of the atomic state space of each node in layer t, St 8hh X. We will use the term full state to refer to the concatenation of the observed values at each node of a layer, i.e. 8, [xt,,.. ,x*',, which are the states obscrved in the corresponding MDP M. In contrast, an atomic state is the value obscrved at specific node, i.e. x for some E (1,....ne)..
Action space: We similarly define an atomic action space, which is the set of actions that can be taken at a particular node. Note that all nodes do not necessarily have the same action space; {D,} U. represents the Up different atomic action spaces available. Let 3f V).,, be the atomic action of the 4h node of layer t, and )),,, be the atomic action space associated with this specific node, with jt,v E {1, ,U.) indicating which equivalence class node v belongs to. The full action space al time step I can be expressed as the Cartesian product of the atomic action space of each node composing layer t, A, = 8'',, Di.. The full action at time stop t, a, E AA,, is the concatenation of the atomic actions selected at each node of layer t, In Figure [ (rightmost plot), we show examples where the dimension of the atomic action depends on the number of exiting edges.
a = [....... vy"*).
6

---

Published in Transactions on Machine Learning Research (03/2025)
Policies: Let μa === [pe) denote collection of time-dependent policies that maps full state St to full action: N4 St - A. for all & E {1,... ,H). Since nodes in the same layer can have common successors, all atomic actions in a given layer must be jointly selected; ignoring these common dependencies and selecting atomic actions independently could lead to sub-optimal policies. Hence, the policies we consider still operate on the full state and full action spaces. Note that. sometimes, we are interested in the action selected at a specific node. Let a = (s()s)) be the full action, we denote the atomic action corresponding to the 2hth node of layer & as (x(x)]ss)) E Vi... to make it explicit that the policy requires knowledge about the full state in order to select atomic actions.
We assume that the known latent graphical structure encodes conditional indepen- dence between nodes, with the state at a node depending only on the atomic state and actions taken at the parent nodes. We split nodes into equivalence classes [Ty] based on their connectivity patterns, with all nodes in the same equivalence class having the same number of parents with the same atomic action spaces. The DAMDP then governed by a set of atomic transition functions U In particular, the probability of observing an atomic state zi X at the tt node of layer is (x"""]]ee (c]),, where of E C,,,, denotes the alomic state and the atomic actions at all parent nodes and in denotes the equivalence class of the node. Figure ! (rightmost plot) shows all the transition contexts that arisc in simple DAMDP. The atomic transition function offers two immediate benefits. First, it reduces the number of dependent variables, focusing only on the subset of variables that influences the next atomic state. Second, it is possible that a layer contains more than a single node belonging to the equivalence class [r:]; in that case, within a single step, the algorithm will observe several samples from the same atomic transition function, p', offering more opportunities to collect data and learn the true unknown dynamics. We sometimes want the transition context to reflect that specific full action E At-1 was exccuted in layer t --1 1. In such cases, we write the context of node E (1,-.. ) in layer i as aaa- The context of any node in layer can be constructed using the alomic description of a,
Transition function:
[wi-1-".. Rt ----"". The probability of observing new full state 8141, given that the full action de has been executed in full state st is given by (r az) = [== piu> (f5+( (df41lc(,a,)) where 9; = [=].... .""","" 8t-1- = [=|_1.... ,x41" and c² denotes the context of node v in layer t given that full action was selected. Similarly, if actions are selected by given policy le, we make this relation explicit in our notation with E. Note that for the first transition, at ( == 1, we define the context to be the empty set, that is, cº 0.
We assume that the expected reward at a time stop t in the full MDP is the sum of the atomic expected reward observed at each node composing the 1th layer, Re(se, ax) = E rdw. (x vf), where zt and yf are the atomic states and atomic actions at node v, Jt,- denotes the action space available at the th node of layer t, and yft. (2, y) is the mean of the atomic reward distribution associated with atomic action set ) J....
Reward function:
3.2 Learning in a DAMDP
As depicted in Figure I (rightmost plot), G can be partitioned into layers, each representing a time step, E (1...., H), of the DAMDP. At each time step within an episode, i, the agent observes the state of each node within the gth layer of the graph. Note that the number of nodes, ne, will change depending time step t. Hence, the dimensionality of the full state and the observation also depends on the time step t. After observing each node's atomic state, the agent chooses the full action it wishes to perform (recall that this corresponds to an atomic action being taken at each node). Again, the dimensionality of the full action will depend on the current time step. Once the full action is taken, the agent observes the reward obtained at each node in the current layer and the new atomic states in each node of the next layer. This process repeats until the algorithm goes through all the H layers in the graph, which completes an episode.
the
Value function:
Similar to the value function of policy in an MDP, the value of a policy μ in DAMDP consists of the expected reward accumulated at each node; when ambiguous, we use the subscript Mc to indicate that this value function is computed under the DAMDP Mc, namely Vt E {I,.... :,, HI} and Vs E S.
H
MM = EE
Snie (xh wh) vi = un (x)))s))),, 8h-1 ~ Pa(-Ish, an), St = b x
(3)
/== v=l

---

Published in Transactions on Machine Learning Research (03/2025)
Among all the Markov and deterministic policies that operate the full state-action space j II, we aim to find the optimal policy, μ", i.e. the policy with the largest value function:
1 arg max Voda (s1).
PEll
We consider a sequential learning setting where the learner interacts with the DAMPD over K episodes. After each episode, the learner can use the information gathered to improve their policy in the next episode. To mcasure the Iearner's performance on this task, we define the regret, which compares, at each point in time, the performance of the current policy against the optimal policy n=
Definition 3.1 (Regret). A reinforcement learning algorithm A chooses for each episode & {1. K the policy that interacts with the environment. The regret of algorithm A over K episodes is defined as,
Regret( K, 21) = Σ A
(5)
where AŞ denotes the difference of value function in the true DAMDP, M2, between the optimal policy n* and the current policy pa:
4 Σ
p(s)
(V))
v
(6)
sES,
where p(s) = I[ (a)) with = [x] 1.
Note that the regret is a stochastic quantity that depends on the random atomic dynamics M& and the algorithm's 's sampling procedure. In the remainder of this paper, we consider the Bayesian regret, where we also take an expectation over all possible DAMDPs Mg that are drawn from a prior over MDPs f.
K
E Regrett K, 20] = Σ E[AR].
Note that, in gemeral, we use to denote the starting time of the Ath episode, so 4 (k: - 1)H 1, and we denote with ty + i the 7th time step of episode k.
4 Dynamic Programming on Graphs
We begin by considering how to learn an optimal policy in a known DAMDP. This will form an important building block of the reinforcement learning algorithm for DAMDPs presented in Section 5
The planning algorithm ! computes an optimal policy via backwards recursion. Dynamic programming algorithms rely on the self-consistency property of the Bellman operator. We show that there exists an atomic Bellman operator for any time step {1,..., ,I}, T,Ma, that performs a one-step rollout according to the policy μe using only the atomic description of the DAMDP Ma.
(TMo 1. (5t)
Σ pdin (x
+
Σ
II
pir ( V. (
(7)
8441 1 o=1
for all t (1..... H1 and for all St S, Here st = s the th node of layer when actions are selected by p..
[ xt and oi denotes the transition context of
The following lemma guarantees the self-consistency of the atomic Bellman operator in equation
Lemma 4.1 (Consistency of atomic Bellman operator). For any DAMDP Me
(X, (1
- Ur, fri 1= U H.PA, and policy μ., the value function V-Mo satisfies:
MM T.M Mc (st).
(8)
for E (1,... H 11 and st E St, with 1 (sn) max.eAs Ri Rn(S a) for all 8n Su-

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm Planning on DAMDP
Input: {p') [P0] |=11; G
un((s) = AH 20 pda. pd (f)
Yan E Sh
for t == -1,..... do
for 8t E do Evaluate (1(5)) according to:
u((s))
max a.E.
Σ plin
Σ
Il
8141 ES441 v=l
Sel
The
Ra+1
((() arg max a.E.A.
Σ
pd (x +
Σ
II
pr (1t4 )ut (e )
#141
where St [z]. x and a₁ ........."
end for end for
Output: a and un (s1) Vsl E E
This property is directly inherited from the MDP assumption; for the sake of completeness, a proof for this lemma is given in Appendix B
Before developing reinforcement learning algorithm for DAMDPs in Section we need to verify that there exists planning algorithm that compute the optimal policy for given atomic transition distribution p and atomic reward function We show in Theorem 4.2 that this can be done via dynamic programming outlined in Algorithm ! The algorithm leverages the one-step Bellman equation for DAMDP in equation 7 It starts by finding the optimal full action for each full state at the last. layer, H. This is trivial as the last full action will not impact future rewards. For each time step t E {H - 1,.... 1} and each full stote 8, E S it uses the one-step Bellman equation for DAMDP equation to find the corresponding value ue(s) and the optimal full action a". The following theorem guarantees that Algorithm [ retrieves the optimal policy pa and its associated value function V.Mg for any known DAMDP Mc. The policy μ² be directly used "..""
to find the optimal atomic actions, since the optimal full action, at .""""""""""" """"", directly encodes the optimal atomic action, yi" for each node E (1,..., ,n)) of the 8th layer of G.
Theorem 4.2. If Algorithm 1 receives as input {pi and {rybým the atomic reward and transition functions of known DAMDP Ma. then it relurns ue (s)) and n, the optimal value function and policy, t.e.
(11) = (s1) 4s E S and =x"
(9)
The full proof is in Appendix C and follows the presented in Puterman 2014 ch. 4).
Remark 4.3. Using the atomic description the environment does not impact the computational complexity of the planning algorithm, which remains O ()) where S denotes the largest full state space.
5 Posterior Sampling RL on Graphs
This section presents PSGRL, posterior sampling-based algorithm that can successfully leverage the latent graphical structure present in DAMDPs. First, we describe the algorithm in Section 5.1 Second, we state the main result of this paper, which an upper bound on the Bayesian regret suffered by PSGRL Section 5.2 Finally, we conclude this section by providing intuition on how the atomic representation used by PSGRL leads to the observed efficiency gains in Section 5.3

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 2 Posterior sampling graph MDPs (PSGRL)
Input Prior encoding G
for episodes k = 1,, 2.... do
Sample Ma,x ((-
Compute و _. using Algorithm for time steps 1 = 1, .... do
Select and execute at = pk(
Observe Tt = [r),..., r(') and 8141 = |0 1 ,
Append (st, az, Tt, St11) to Des4 end for end for
5.1 The algorithm
In Algorithm we present our posterior sampling algorithm for DAMDPs, which leverages the rich underly- ing structure in the DAMDP setting. The algorithm proceeds in episodes. At the beginning of each episode k the algorithm samples a DAMDP Mc. ~ f(-[Ds,, where f(- D2) represents the current belief about the true DAMDP M& given the observations collected up to episode k. DR. Note that the context of DAMDP, to sample Ma the algorithm essentially samples a set of atomic transition functions {r') and atomic reward functions (rd (-) The algorithm then computes the optimal policy Ma on MG,x and runs the policy for an episode. The trajectory (st, Gt. Tt, 81++1 ) is added to our dataset Dr. We then use Dr to update our belief about the distribution of the true DAMDP MỘ. We assume that each transition function is a catogorical distribution governed by a set of parameters p,. E IRx, for all i fl, Uz}. reward function has Gaussian distribution with mean μ4y and standard deviation Ø,,, for j E (U,). The prior f maintains Dirichlet distribution over the space of parameters 6yr and a permal-inverss gamma prior over the space of parameters p4l and o,s. This induces prior distribution over DAMDPs.
2
The expected
5.2 Upper bound on the Bayesian regret
The regret suffered by PSGRL (Alg. 2 is bounded by the following theorem.
Theorem 5.1. If is the distribution of M then the regret suffered by PSGRL (Alg. 2 over K episodes is upper bounded by,
U. H XYmmk Σ H (XV)m
U.
E RRRegret(K, PSGRL))
Σ
(10)
where X = | is the size of the atomic state space, Y = maxxe((,... (U,,,, ..,) [y is the size of the largest atomic action space. For nodes that belong to the ith equivalence class [Ti], d, denotes the number of parent nodes, and m denotes the number nodes in that share the same equivalence class [T.]. Finally, m is the number of nodes in G with the same atomic action space V/..
The proof of Theorem 5.1 is given in Appendix D follows the proof in Osband et al. (2013), with the key difference being that the confidence sets are built around the estimates of the atomic transition and reward functions. This approach has two immediate benefits. First, might be able to collect more than single sample per time step. If we consider the case where we have k nodes in the same layer, t, that belong to the same equivalence class, [r:], then at lime step 4, we collect k samples from p². Second, the input space of the atomic reward and transition function can be significantly smaller than the input space in the original MDP (i.c. the transition and reward functions over the full state and action spaces). This leads significant gain in performance since the atomic transition and reward function are casier to estimate than their full state-action counterparts.
10

---

Published in Transactions on Machine Learning Research (03/2025)
The bound presented in Theorem 5.1 is improvement over the lower bound that can be obtained by running any RL algorithm in the full MDP and ignoring the latent graphical structure. Indeed, by Osband et al. 2013), the lower bound for an RL algorithm that ignores the graphical structure is:
Ω Σ S 2
Σ ((XY).KH
(11)
Where Y (1.... Y2 is the size of the smallest action space in the DAMDP. The comparison of PSGRL upper bound in equation [0] and the lower bound in equation [ suggests an improved efficiency for PSGRL compared to RL algorithms that ignore the latent graphical structure. In particular, note that the number of incoming edges for any node in a given layer is always bounded by the number of nodes at the previous layer d; S n where denotes the equivalence class of any node in layer t. In conclusion, the regrot suffered by PSGRL, as described in equation [0] is smaller than the regret any RL algorithm that ignores the graphical structure G could suffer as described in equation
U² Σ H (Yym +
U, Hy (XY)4m)
H
Σ
&
(X
h=1
5.3 Efficiency gains via compact confidence intervals
This section gives more insight into the sources of PSGRL's efficiency gains. Specifically, it highlights that we can leverage the atomic components of the DAMDP to construct more compact confidence intervals. This leads to the improved theoretical guarantees seen in Theorem 5.1
The fact that both the transition and the reward functions can be written in terms of their atomic counter- parts represents an opportunity to increase the algorithm's efficiency. Indeed, the size of the combinatorial spaces S, and A can present challenge when a learner is tasked learn the full transition distribution P and the full reward function R directly. The inputs of the atomic transition functions and the alomic reward functions lie in spaces much smaller than their non-atomic counterparts, presenting an opportunity to speed up learning. The input space for the atomic transition function i depends on the size of the context space, [.l. for E [1,... U.}, where U- is the number of equivalence classes. Critically, |C, includes states and actions for only a subset of the nodes at the previous layer. This space is smaller than the full state-action space, which is the Cartesian product of the atomic state-action pairs of all nodes in the previous layer. Similarly, the atomic reward only depends on the atomic state x X' and the atomic action y E y/, for (1,... UU), which is also smaller than the full slate-action space.
We can exploit the structure to achieve further efficiency gains by observing that the input of the atomic transition and reward function can be observed more than once per time step. If two nodes in the same layer have the same number of incoming edges, then they are learning the same atomic transition function. Similarly, if they have the same atomic action space V/, then they are learning the same atomic reward function. This benefits the learner as they observe more samples corresponding to the atomic functions than their non-atomic counterparts.
PSGRL (i.c. Alg. 2 leverages the above two propertics to achieve efficiency gains. To see this, consider the sampling procedure of PSGRL when it samples candidate MDP Ma.x from set of plausible MDPs Ma. The regret of the algorithm is tightly linked with the pace at which the confidence sets MG. concentrate around the true MDP Ma. The atomic representation of the transition and reward function significantly simplifies the construction of the confidence intervals, which leads to the observed efficiency gains. Indeed, the width of the confidence interval for the atomic transition functior P depends on the square root of the = size of the outcome space, -x=v/zz To see this, let ø² be an empirical estimate of the atomic transition function for nodes in the equivalence class i [U^] and p be the true atomic transition function. The algorithm samples p¹ that are close to the current estimate Pk. i.e. 11p((-1)) pa p-(-)c]] S with probability greater than 1 5 for all E E, and for all E [U=]. The width of the confidence interval can be determined by
2 we focus on the transition function, although similar arguments can made for the reward function.
11

---

Published in Transactions on Machine Learning Research (03/2025)
the concentration inequality in WWissman et al. 2003) to be E S X log (3) + 2d, log 2U,XYmis
This explicitly shows that the width of the confidence interval scales with the square root of the outcome space, vX. Algorithms that construct confidence intervals with the full representation of the transition function will have confidence intervals that scale with respect to VIS), which is much larger than vX, leading to larger regret.
Another advantage of the atomic representation that PSGRL exploits is that the number of observed atomic transitions is larger or equal to the number of observed full transitions. This is a direct consequence of the atomic transition being stationary and potentially appearing several times within a layer or in different layers. This potentially incrcases the number of observations for each atomic transition function more than once per step. PSGRL uses all the atomic observations lo construct confidence sels. This can speed up learning as we see that the confidence intervals scale with 1/ so as the mumber of observations increases, the confidence sets shrink. However, using all the atomic observations complicates the analysis as we need to account for the fact that we can observe a reward or a transition input more than once per time step, in contrast to the classic analysis of RL. frameworks that assume that a single sample is collected at each time step.
6 Experiments
We now illustrate that the performance gains suggested by Theorem 5.1 manifest themselves empirically. We consider two experimental settings: the maximum leaky flow of a graph and wind farm yield optimization.
6.1 Maximum leaky flow of a graph
The maximum leaky flow problem (introduced in Sec. 3 is defined as directed acyclic graph G = (V, E), with a single root node, the source node E V, and a single leaf node, called the sink node un E V. Using the edges to transport flow from one node to the next, the goal is to transport as much flow as possible from the source node to the sink node. Because is directed, it is only possible to transport flow in the odge's direction. The environment is governed by two parameters: edges have given capacity, > 0, which denotes the maximum amount of flow that can be transported along that edge, and an unknown failure probability, p [0, 1], which dictates how likely the edge is to fail to transport the flow assigned to it.
The above problem is similar to the graph maximum flow problem (Ford & Fulkerson, 1956). However, the leaky version of the problem is more challenging as the probability of failure is unknown to the learner. In the leaky version of the problem, the learner is tasked to jointly learn the unknown dynamics and the paths that maximise the expected flow.
We consider two algorithms for this problem. The proposed PSGRL, which has access the graphical structure and extension of the PSRL algorithm (Osband et al. 2013) that works in time-inhomogenoous full MDP settings, which does not know the graphical structure.
PSGRL representation: At each time step f, we observe the set of atomic states {x] ( which represent the amount of flow into node of layer t. For each node, the agent decides how to distribute the current flow along its edges. For each node, the atomic action space consists of the possible allocation of flow along its edges; the action space discrete and represents a possible fraction of the total flow. The atomic reward is then the amount of flow a specific node sends to the next layer of the graph
PSRL representation: The full state representation at time step t, st is vector representing the amount of flow in each node in layer t. The full action representation is the flow assignment for all edges connecting nodes from layer / to layer t ++1 1. The reward at time step & is the total amount of flow the agent managed to move from layer & to layer & 4+1. 1.
Figure 2 compares the performances of PSGRL and PSRL on the leaky maximum flow problem. The first row of Figure 2 depicts the DAMDP considered, while the second row shows the cumulated regret incurred by PSGRL (in blue) and PSRL (in red). The uncertainty estimates around the curve are obtained by running
12

---

Published in Transactions on Machine Learning Research (03/2025)
Cumulative Regret
200
Cumulative Regret
Cumulative Regret
1000
psgrl
300
psrl
150
750
200
100
500
50
100
250
0
2000 4000
0
500 Episodes
1000
0
500
1000
Episodes
Episodes
Figure 2: The first row depicts the graph that governs the maximum leaky flow problem instance. The second row shows the learning curve for both algorithms considered. PSRL ignores the latent graphical structure, and PSGRL leverages the graphical structure. The left-most plot shows the performance obtained on a simple chain graph. As expected, the performance for both algorithms is similar. Looking al the remaining plots, where we consider larger diamond-shaped graphs, is clear that as we increase the complexity of the graph, the benefit PSGRL becomes evident. To monitor the evolution of the regret, we ran ten different sceds; the solid line represents the mean regret while the shaded area covers one standard deviation.
the experiment with seeds. We present in Appendix H (see Figure another series of experiments that highlights similar performance results different family of graphs.
The leftmost DAMDP is simple chain graph. For this specific DAMDP instance, the atomic represcntation and the full state representation are equivalent. This explains the similar performance of PSGRL and PSRL. In contrast, considering more complex DAMDP instances, the benefit of leveraging the latent graphical structure becomes more apparent. Breaking down the combinatorial nature of the full state space and full action space using the DAG structure beneficial. This even more obvious on the rightmost plot, which shows the most complex leaky maximum flow instance considered.
Remark 6.1. Even for a simple example like the leaky maximum flow problem, it is interesting to analyse how the Bayesian regret bound for PSGRL equation I0 compares to the RL lower bound equation II] The diamond-shaped graph with 16 nodes in the rightmost. part of Figure 2 implies that the DAMDP is parameterized by the following quantities. The number of distinct atomic action spaces is U, = 2 some nodes can distribute their flow in a single edge while others can distribule it in two different edges. We observe that there are 6 nodes with a single outgoing edge, hence m 6 and 9 nodes with two outgoing odges, m = 9. The number of transition equivalence classes is U, = 2 as some nodes have two incoming edges while others have a single incoming edge. We observe that there are 6 nodes with a single incoming edge (i.e m = 6) and 9 with two incoming edges (i.e. m = 9). We also note that the maximum number of nodes in a layer is Nmaz = 4, and the largest number of edges between two adjacent layers Mmaz 6. In this specific context, the regret upper bound of PSGRL can be expressed follows:
U-
Ux
(e = Σ H 2XY +
Σ
2(X
(12)
= H /12XX + HVI8XY,K + + HV19X3Y<K)
(13)
In orange, we have the regret associated with learning the transition function, and in blue, the regret associated with learning the reward function. Similarly, using the characteristios of this specifie problem
13

---

Published in Transactions on Machine Learning Research (03/2025)
episode return
2.8
episode return
psrl
psgri
3.25
2.6
3.00
2.4
1000
0
1000
number of episodes
number of episodes
Figure 3: The two leftmost plots summarize the results obtained on wind farm task with six wind turbines. The first plot shows the performance of PSGRL and PSRL, while the second plot illustrates the farm layout (cach node represents wind turbine, and cach edge contains the wake effect). The two rightmost plots show the same experiment for larger farm with nine wind turbines.
instance for any algorithm that do not leverage the latent graphical structure, such as PSRL, we obtain the following lower bound:
"
11
(K, =
Σ
V.S.AA =
Σ ((XY)
(14)
1=11
(T22VXX))++2((XXX)))) 2 V(XY)T).
(15)
where Y denotes the smallest atomic action space.
In this simple example, the efficiency gain provided by PSGRL will be significant as long as Vx*p2 <
(XY)² which is in general true, unless the discrepancy between the largest and smallest action space becomes too large, note that in the diamond graph considered expect to an efficiency gain as Y = and Y². Additionally, this efficiency gain is reinforced we increase the size of the graph. Considering that the number of nodes increases while the diamond- architecture on Figure 2 is preserved, PSGRL's regret equation 12 scales linearly with the number of nodes, through m and m². On the other hand, PSRL's lower bound on the regret scales exponentially with the number of nodes through ne, the number of nodes at each layer of the graph.
6.2 Wind farm yield optimisation
One real-world example with a known latent graphical structure is the case of wind farm optimization. To maximise the yield of a wind farm given a specific atmospheric condition (wind direction and speed), is important consider the interaction between wind turbines. Wind turbines generate a stream of turbulent wind that might impact the yield of downstream wind turbine. This phenomenon is known the wake effect. The wake of wind turbine can be deflected if the upstream wind turbine slightly rotates. This introduces an interesting control problem as for a single wind turbine to maximize its yield, it has to face the wind, but as soon as the yield of the entire farm is concerned, the optimal set of angles might include wind turbines not facing the wind in order to maximize the yield of other wind turbines. In what follows, we constructed a simple environment that models some of the dynamics of a wind farm. To model the wake effect, we use FLORIS, a wind farm simulation software (Annoni et al. 2018) + To simplify the setting, we discretize the atomic action y {30", ,0, } which are the possible angles (with respect the wind direction) for each wind turbine. The atomic state encodes the wind speed observed at cach wind turbine. We also discretize the state and consider all increments of 0. 1.mm/s / from 6m/s to 10m/s. Similarly to the maximum flow experiment, the full state and full action at time step t are obtained, respectively, by concatenating the atomic state each node in layer t and the atomic action of each node in layer t. The performance of PSGRL on the resulting DAMDP and PSRL on the corresponding MDP is shown in
3he code for the FLORIS simulator available at the following address:
14

---

Published in Transactions on Machine Learning Research (03/2025)
FMDP /DAMDP
DAMDP
DAMDP
This figure shows three examples of DAMDPs; the leftmost one has a constant connectivity pattern. Each layer has the same number of nodes, and the connectivity pattern from one layer to the next remains the same. MDPs that exhibit such a structure could be modelled by an FMDP or a DAMDP. On the contrary, the middle and the rightmost graphs could only be modelled by DAMDPs. The example depicted in the middle graph shows interactions that vary from one time step to the next, which cannot be modelled by an FMDP. The rightmost graph shows graph where the number of nodes varies from time step to time step, which also cannot be modelled as FMDP
Figure 4:
Figure 3 where each plot considers wind farms with grid layout with a varying number of wind turbines. We consider a grid-like layout where we explicitly encode the impacts between a wind turbine and its closest upstream wind turbinc. While the plots on the left of Figure g show a wind farm composed of six wind turbines, the right side of the figure shows an experiment with nine wind turbines. Again, it can be seen that the benefits of running PSGRL the DAMDP are significant compared to the performance of PSRL the corresponding MDP because of the re-usability of the atomic reward and transition function.
7 Related work
The DAMDP model considered in this paper is related to the factored MDP (FMDP) framework. While the first works on FMDP considered only a factorisation of the state space Kearns & Koller 1999 Boutilier
et al. 2000 Guestrin et al.) 2003), the FMDP framework was later extended to consider factorisation over the state-action space (Osband & Van Roy 2014 Chen et al. 2020) which in spirit is more similar to DAMDP. Indeed, FMDPs and DAMDPs share similar assumptions; they both consider the factorisation of the state and action spaces, the additivity of the reward function and the factorisation of the transition function. However, important difference between the two frameworks is that FMDPs were initially proposed in time- homogenonss setting, while DAMDPs allow the structure vary as dictated by the graph and its connectivity.
In particular, DAMDP models a larger class of problems, as depicted in Figure J the encoding of the entire episode in a graph allows the representation of richer dynamics. The leftmost plot of Figure | shows a graph that exhibits the same connection patterns across all layers; such a problem could be modelled with FMDPs DAMDPs. The remaining examples in the middle and on the right side of Figure 4 represent problems that cannot be directly modelled with FMDPs. The example in the middle of Figure 4 shows a scenario where the connection dynamics change from one layer to the next, while the rightmost example shows graph with varying number of nodes and edges in each layer. Since DAMDPs are rolled out on an arbitrary directed acyclic graph, we can model each of the three graphs in Figure 4 with a DAMDP. On the subset of DAMDP problems that can be modelled as FMDP, the regret obtained for the algorithm proposed in Osband & Van Roy (2014) equivalent to the regret of our algorithm, PSGRL.
In general, DAMDPs, naive extension of the regret proposed Osband & Van Roy (2014) to the time inhomogeneous setting, is worse than the result obtained in Theorem 5.1 A naive extension of the FMDP framework to the time inhomogeneous setting, where the factored dynamics are encoded in graph G, would produce a regret bound driven by the number of nodes in the graph G. To be more specific, using our nolation, the regret. paid by the posterior sampling-base algorithm proposed in Osband & Van Roy (2014) to
estimate the transition distribution of an FMDP is DMV, ((H(X))4 + (xY) yd. XT),, where |V| represents the number of nodes in G and d, is the number of incoming edges in node v. For the case of DAMDPs, the bound we propose in Theorem 5.1 is tighter as in equation 10 the size of the transition context. (XV)d. is
15

---

Published in Transactions on Machine Learning Research (03/2025)
2 Σ V(xry, as the first sum is over all nodes in
under the square root and, in general, the graph while the second is only over the U, equivalence classes. This difference becomes more evident if we consider increasing the number of nodes [V] while preserving relatively small number of equivalence classes Ur. For example, in the case of the diamond-shaped graph (e.g. Fig, 2), the graph's architecture remains constant, and the only term that grows is my, the largest number of nodes in a single layer that has the same transition context.
In this work, we have assumed that the graphical structure known. An interesting direction for future work would consist learning the latent graphical structure. Structure discovery has been studied in the case of time-homeen homoeeeooge FMDP Degris al. (2006); Strehl et al.) (2007); Mutti et al. (2023), but these methods have not been extended to the time-inhomogencous setting. Approaches like the one considerod in Mutti el al. (2023), where the proposed algorithm, C PSRL, can learn the factored representation, could be extended to the himeiinhomoeeneuus setting. Such an extension is not trivial as it would require adding another layer of inference in our proposed algorithm and treating the latent graph G as a random variable.
8 Conclusion
In this paper, have formalised new subclass of MDPs that have an additional graphical latent structure, DAMDPs. We then presented a posterior sampling- based algorithm, PSGRL, that exploits this graphical structure to efficiently learn a policy. We finally showed that PSGRL purperfsss PSRL both in theory and in practice when this graphical structure is present.
Although the structure of DAMDPs may appear restrictive, we argue that does appear in many practical settings, including the maximum flow of a graph and wind farm yield optimisation setting discussed in this paper. However, attributes; for example, if we revisit the wind farm optimisation example presented in Section 6.2 We could imagine that the potential effect two wind turbines have on each other might depend on the relative distance between the two; adding additional attributes to the edge would allow us to consider a richer set of transition dynamics and to model real-world problems more realistically. Such an increase in complexity will impact the upper bound on the regret but would offer more flexibility in the modelling. Second, to accommodate wider range of real-world problems, the proposed framework could be extended allow for continuous state and action. Quantifying the benefit of the graphical factorisation in such context remains of great interest. We leave these endeavours for future work as, for the lime being, our graph-based approach renders potentially large subset of real-world MDPs amenable to more efficient training. This phenomenon is even more evident when we consider that the graph computations are inherently parallelisable.
immediate future step could be to extend our model. First, we could add edge
Acknowledgments
AR was supported by EPSRC CASE studentship supported by Shell, and AAF supported by UKRI Turing AI Fellowship (EP (EP/VO25449/1
References
Mahdi Abkar, Navid Kchtabiyan-Rezate and Alexandros Iosifidis. Reinforcement learning for wind-farm flow control: Current state and future actions. Theoretical and Applied Mechanics Letters, pp- 100475, 2023.
J. Annoni, P. Fleming, A. Scholbrock, J. Roadman, S. Dana, C. Adcock, F. Porle-Agel, S. Raach, F. Haiz- mann, and D. Schlipf. Analysis of control-oriented wake modelling tools using lidar field results. Wind Energy Science, 3(2):819-88) 831, 2018. doi: 15119//ww---819---- URL htttps:///eet cwpernicus.coo org/ aaticles/3/819/2118)
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008
16

---

Published in Transactions on Machine Learning Research (03/2025)
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference. on Machine Learning, pp. PMI.R, 2017.
Jørgen Bang-Jensen and Gregory Z Gutin. Digraphs: theory, algorithms and applications. Springer Science & Business Media, 2008.
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial intelligence, 121(1-2):9-107 2000.
Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang. Efficient reinforcement learning in factored mdps with application to constrained rl. Xrviv preprint arXiv:2008. 13319, 2020.
Thomas Degris, Olivier Sigaud, and Pierre-Henrt Wuillemin. Learning the structure of factored markov decision processes reinforcement learning problems. In International Conference on Muchine Leurning, Рp. 257- 264, 2006.
Lester Randolph Ford and Delbert R. Fulkerson. Maximal flow through network. Canadian journal of Mathematics, 8:399-404, 1956.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha. Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19:399 468, 2003.
Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. In IJCAI, volume 16, pp. 740 747, 1999.
Zoubir Mammeri. Reinforcement learning based routing in networks: Review and classification of approaches. IEEE Access, 7:55916 -555000 2019.
Mirco Mutti, Riccardo De Santi, Marcello Restelli, Alexander Marx, and Giorgia Ramponi. Exploiting causal graph priors with posterior sampling for reinforcement learning. arXiv preprint arXiv:2310.07516 2023.
Tan Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. Advances in
Newral Information Processing Systems, 27, 2014.
lan Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley
Sons, 2014.
Benjamin Rolf, Ilya Jackson, Marcel Müller, Sebastian Lang, Tobias Reggelin, and Dmitry Ivanov. A review on reinforcement learning algorithms and applications in supply chain management. International Journal of Production Research, 61(20):7151 7179, 2023.
Nima Sedaghatizadehh, Maziar Arjomandi, Richard Kelso, Benjamin Cazzolato, and Mergen H. Ghayesh. Modelling of wind turbine wake using large eddy simulation. Renewable Eneryy, 115:1166 1176, 2018. ISSN 0960-1481. doi: https://doi.org. 10.1016/1 201.....017.000011 URL https:///wwt wwt.///www..c..ncnrrrrrr.cc....
Alexander T. Strehl, Carlos Diuk, and Michael I. Littman. Efficient structure learning in factored-state mdps. In AAAL, volume 7, pp. 645 650, 2007.
Malcolm Strens. A bayesian framework for reinforcement learning. In International Conference on Machine Learning, volume 2000, pp. 943 440- 2000.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 12, 1999.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279 292, 1992.
17

---

Published in Transactions on Machine Learning Research (03/2025)
Kevin Daniel Wayne. Generalized mazimum flow algorithms. Cornell University, 1999.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger. Inequalities for the 11 deviation of the empirical distribution. Hewlett- Pockard Labs, Tech. Rep, 2003.
18

---

Published in Transactions on Machine Learning Research (03/2025)
A
Notation
Symbol
Description
H
The episode's horizon.
G
The additional structure encoded in LDAG.
x
The atomic state space.
S
The full state space.
y
The atomic action space.
A
The full action space.
U,
The number of different action spaces.
rd
An atomic reward function with E [U,].
R2
The full MDP's mean reward function at time ste E HH.
U-
The number of nodes equivalence classes.
p'
The atomic transition function for nodes in equivalence class i E [U7].
P.
The full MDP's transition function at time / E H
PA
The atomic initial distribution for node v in the first layer of G.
P
The full MDP's initial state distribution.
B Proof of the consistency of the atomic Bellman operator
Lemma B.1 (Consistency of the atomic Bellman operator). For any DAMDP Ms (x, (,1 (r (p' J H, 10x G) and policy μ, the value function V satisfies:
MM Hit (st) = Mo utt+1 (
(16)
for tr (1...., . - 1) and 8t E St, with Villa (HH) = max.eAi (H( for all sh E Sh.
Proof.
T4e uit p1.+1 ($t) Σ
The41
T.May.Mo
New (x (xx)((())) sx)))
II
p (2f (c p,lf1 (8
V.MM
oml
$111ES111 um
The11
na
Si (x p(x ((22((ss)) (s:))
pa (2 (x
Σ
yu (of
( (142))))))))))
$11E5 s=1
h
H nh E
Sus (x" ((x)ss())ss)))
V-Mo (8t)
To obtain the first equality, used the definition of the Bellman operator, and to obtain the second equality, used the definition of 4..41- Observing that we consider all possible next state 8 weighted by its probability of appearing, we can directly include this computation into the expectation leading to the third equality.
C Proof of convergence of Algorithm
1
Thcorem C.1. If Algorithm receives as input p and the atomic reward and transition functions of known DAMDP MG, then il relurns in (81) and n, the optimal value function and policy, i.e.
un (81) (MM((s)) and p²
(17)
Proof. The proof follows the presented in Puterman 2014 ch. 4) and consists of two parts.
19

---

Published in Transactions on Machine Learning Research (03/2025)
Part i: Show that the learned value function ue(s)) 2 Valle (st) for all a II and for all (t, E (1,... HH
St, where IT is the class of all deterministic and Markov policies.
Part it: Show that the algorithm's 's output satsifies (x(s)) = V (st) for all t and all 8 E S..
Proof of Let x IT be any policy in the class of deterministic Markov policies. Since at the last time step H the goal only to maximise the immediate reward, the suggested result holds at time step H, us((s)) Valle (s#), for all sy Sp. Let's now assume that ur(8)) 2 V for I = h H. We prove by induction that it also holds for t h,
au Shi
un (sh) αελn
max
(1 Dh
Σ
II
y the (1 (0 (Sat1))
8h+t 6Sh+1
puni (2 Vih)
Σ
Il
p p (o V (8nt1)
max eEAn
111158K1 u=l
Bi++1
J T
(2)%)1))) (
+
Σ
p (x 1
V.G n (sn+1)
Sk 1E ==1
H
Jnw (xh T (x))))))) + Ex
3 (x (z)
(by def. of Mo equation 3
==1
(M) a,h
where the notation E, used to explicitly mention that actions are selected according to the policy m. Proof of ii: The second part is also shown by induction. We start by observing that the last step focuses only maximising the immediate reward. So at time step H it trivially holds that (s)s)) V- (s) for all E Sh. We then assume that uz(s) = V VaMe (s) for t = h 1, H and for all E S.. Then,
12 whe (x% 9h)
Rh+1
(s)(s) Ar
max
Σ
II
S'ES++1
max A
phi (x% wh) +
Σ
II
p th th (2h411l044.00 V-NG (5))
S'S u=l
Bh+t1
jni (oh 1 (1122 (x))s))) +
Σ
II
S'ESt
o=1
V Ma (x)
Where the third line is obtained by the hypothesis that us(s) = V.lla (s) for t 2 h and from the definition
of y²
Proof of Theorem 5.1
We follow the proof structure of Osband et al. (2013 where the analysis focuses on a modified regret term that removes the dependency on μ and equivalent to the original regret in expectation. For any episode k, we can write the modified regret as follows:
Á Σ
(V Ma. (s1) V.
(18)
Me.l
STES
20

---

Published in Transactions on Machine Learning Research (03/2025)
where Mt is the true DAMDP and Ma.x is the DAMDP sampled at episode k.
The equivalence in expectation between the original regret A and the modified regret A is possible thanks to the following lemma, which is first presented in Osband et al. 2013 Lemmma 1) and restated below in the DAMDP setting:
Lemma D.1. If f is the distribution of Mc and MG f then, for any (DD)) (DDa)-measurable function 9, Blg(Ma) (M.
(19)
Where o(D)) is the o-algebra generated by all the data accumulated up to episode k, Dx-
This allows the following equivalence between the two different regret terms, E
Ek=1
K
De E > k Åμ
Indeed, since D 1a-Ae - = E. (V Ma (s1) V. (s1)), from Lemma D.1 we get that E[Ar Ås D 0. Finally, by the tower rule E[Ax DR] [I [ 0.
To lighten the notation equation 18 allows us to rewrite the modified regret in terms of Bellman error,
write Vie. for Valle Working with the modified regret Á (presented in
MA Ma.a]
Ma.s T ( Ma Mo.s) (
(20)
To prove that equation 20 holds, we apply the Dynamic programming equation 7 inductively (note that we denote by pt. (xlc) the atomic true transition distribution for nodes that belong to the equivalence class [ri]):
(Vk pa.l ($1x+1))) (T Vh n4.2 Tpi, ($1++11)
112
=Th 1 2 ( Σ la
( (s')
s'ES2
(Th pa.1
T 14.2 (1) (11 + (V
V 2) (512+22 + dect1
H
(Th 1 Pa
Σ deyth
h=1
for
diath =
p (o Ic
1( Pu
Bu.41 Vi Vin (83)) - (V+
Me V (
o' S'E ==1
Since IE[(V #4. V te (+4+)++))+)+ Mc.a] Ve 1 (s') the terms d disappear in expectation (i.e. Eld,, MM Ma.1 = for all & and h E
Evesun Ih (ptn (2h 1t (V&
[I..... ....,,,))))) H{} and so we obtain equation 20
Since the regret has been rewritten as the sum of one-step Bellman errors (see equation 20 the next step is to show that interactions with the environment are observed, the sampled DAMDPs, Ma.k, concentrate around the true DAMDP Ma- This is done in the following subsection.
D.1 Confidence sets
For the remainder of this section, the notation bit more involved. The below list introduces recalls the concepts and the notation used.
21

---

Published in Transactions on Machine Learning Research (03/2025)
1. C=(V, is an LDAG that encodes the underlying structure in the execution of a DAMDP episode. We denote the 8h node of layer & by vt. We recall that each layer 1 = 1, H. has nn nodes. The graph has a total of M - -M nhe n nodes.
2. If two nodes ti and o/2, with ti) # (i2, 12) have the same number of parents and their parents have the same atomic action space, they belong to the same transition equivalence class [T.]. We denote by d; the number of parent (or incoming edges) of a node that belongs to equivalence class [Ti]. All nodes in G belong to one of the Ur equivalence classes, Ur The number of nodes in G that belong to the same oquivalence class is denoted by m and Σ m n. For example, in Fig. | there are two different equivalence classes, U, = 2, because there exist nodes with two parent nodes or a single parent node.
3. Each equivalence class [Tx] with i (I....., ,,), has a corresponding state-action space E; = di ( x J'k) that contains all the possible values the transition context (of an element of the 8th equivalence class [ri]) can take. Recall that the atomic action space might depend on the node, so two nodes belong to the same equivalence class if they have the same number of parent nodes with the same atomic action spaces. This space consists of the atomic states and the atomic action values of each parent of the node. We can upper-bound the size of this context space by (XY)a, where d, is the number of parent nodes in the ith equivalence class, and Y is the size of the largest atomic action space.
4. Each equivalence class [T]] has a dedicated transition function (+(c)) for all i E {I, ,U+) and all possible transition context & E C.
5. U, is the number of distinct atomic action sets. For example, in the case of the leaky maximum flow problem in Section 6.1 U, = 2, the alomic action space is different if a node has a single out- going edge or two out-going edges. In the wind farm optimisation problem U,- = 1, regardless of the number of outgoing edges, the atomic action space of a node remains the same. The number of nodes in G that have the atomic action set j is denoted by mi, for all j E {I, [..). Then, Σ/ m = n, where is the number of nodes in G.
6. For each distinct atomic action set ( we call the atomic reward context the associated atomic state-action space Z, X x V/- We denote by zj 2, an element of the reward context: j.
7. For each atomic action set (3)) we define a corresponding atomic reward function r" (2z))
8. Define (T) to count the number of times a node of the equivalence class [T]] has observed the transition context e E C, during the first 4 time steps, where l4 indicates the time step at which episode starts (i.c. to = (k 1)) + +1). Sometimes, we are interested in monitoring the number of visits more closely. Then, (c) counts the number of time the transition context c E C, given that the agent started episode l and already observed the e first nodes of G, with Nodes are indexed by layers, but the indexing within a layer is arbitrary and fixed before the learning starts In Figure leftmost plot, we show an example of an LDAG with a valid node indexing.
{1. m)).
Define NT. to count the number of times a node has observed the reward context E 2, during the first & time steps for all j E [U,] and for all E 2y. (z) counts the number of times the reward context z was observed until the 4h node of the execution of the k4h episode, where the node
indexing is the same the one considered for NT.a( (see entry & of this list for more details).
The posterior sampling algorithm procoeds by sampling an atomic reward function for each possible action set {},} and a transition function for each equivalence class [Ta] for all E {1,.... ",,... The alomic transition distributions and the atomic reward distributions sampled at the beginning of episode k (step 3. in Alg. 2 are denoted 1r and {r respectively. The sampled DAMDP then constructed by combining the atomic transition and reward function as dictated by the graph G. To show that the sampled DAMDPs, Mc concentrate around the true DAMDP MG. construct confidence intervals around the
22

---

Published in Transactions on Machine Learning Research (03/2025)
empirical atomic transition and reward functions. We define the confidence set of feasible DAMDPs that we may sample at episode & as:
M {M (11c p'(ee)) s ((() v e, vie [ & [+((2) S (e)=) V2 e 2,VJ (U,]].
(21)
Where P denotes the empirical estimate at time step h of the h atomic transition function, F denotes the empirical estimate at time step & of the jth reward function, (c) is the threshold for the error on the 7th transition function, and (²(2) is the error threshold for the error on the jth atomic reward function. We propose the following definition for the error thresholds:
XYmmk) )
[c(c) =
X log 5
+ 2d log
Vi {1, , and Ve E e,
(22)
No.
(c)
XYm
log
(=) = \
Vj (1, ,U, and V2 E 2,,
(23)
max NT.
(=))
where No.(( (z) and (c) are defined above (elements andd in the list).
D.1.1 Analysis of the Confidence Sets
Lemma D.2. For any k 2 1, the true MDP Mc belongs the confidence set at episode k. My. defined in with probability:
equation 21
P(M & M 6/k.
Proof. The Ln deviation between the true atomic transition distribution p¹ (-lc) and its empirical estimate (lc))c) is bounded for any by (Weissman et al. 2003):
P ( -' (-())) 26) < (2x exp (
nez ne²
vi {I, ,.,,,, and Ve C,
(24)
2
where X is the number of distinct outcomes of p(-cc) and is fixed number of samples.
We now define
2 Vi
(XY )d
2
(
2
X2 ))
& log
where &f <
X log
88
2d, log
n
8
This upper bound on dt gives the exact expression of (c) defined in equation 22
We can, therefore, show that the confidence bound in equation 21 holds with high probability. In particular, for the atomic transition probability given context c E C, and fixed number of visits n we have:
PP (18t(-10) -'(le)l 2 (L(e) = [1p((-1c) p-(cc)l11 2
X log -
2 + 2d, log
2 XY XYmik
8
< x exp
n ( (Et))
n1 2
2 2U, ( di
xx exp
log
2
8
23

---

Published in Transactions on Machine Learning Research (03/2025)
Now, with fixed number of samples n, the deviation between the true atomic expected reward and the empirical atomic mean reward is bounded by Hoeffding's inequality for any e. > 0:
( (x)) 2 22exp(-2n(e)) Ve (I,... ,U, and V2 E 2z.
(25)
We define
AUp.Ymihh
1
[AU,XYmtH
log
and note that & S
V
log
2n
5
8
Again, this upper bound on ef will be used to determine the exact expression of (z). Combining Hoeffdings inequality with definition of eL, we get:
4U XU,XX UUXKY
P (()))-(()))) x2(22) =P (+) - (z))
log
(26)
S 22xp( 22exp(-2n(ep) (2n((e))²)
(27)
AU AU, AU,.X mmth?
n
exp
log
(28)
2
6
(29)
XU XYm,k2
To compute the probability of interest P(M& & Ma); we need to compute the union bound by summing over all possible numbers of visits. It is important to note that in the same layer, more than one node might observe a reward for the same atomic state-action pair same layer, more than one node observes the same transition context As consequence, the mumber of observations can increase by more than a unit per time step. If we perform & episodes, the number of visits for specific reward context j might range between O and km/. where m is the number of occurrences of reward architecture j in G' (see element of the above list for a more complete definition). Similarly, there are m nodes that belong to the equivalence class [Ti], so a given transition context & can be observed up km,, times (sce clement of the above list for more complete definition). Now, computing the union bound by summing over all possible numbers of visits, we obtain the following:
(2, It also possible that in the
log 40, XY
m A:
8
P -P((())- - - 2
(30)
max(1, NTJ (2)))
2
XY
2U,XYk
10
2
20 2U,XÝm;k
P
10 - -'
log
+ 2d, log
m1 (c+))
milk
20, (
20, (XV)dd
1=1
This allows us define (c(c) (introduced in equation 21 for all i f1,... .U}} and for all E C,
2 (c) max(1, NT,
(2 (2,XXmm;
))
X log
+ 2d, log
(31)
8
8
and +x(=) for all E (1,... .... U.} and for all E E,,
24

---

Published in Transactions on Machine Learning Research (03/2025)
log 4U..Y
(=)=)=
(32)
max
NT. NT.
Summing the probabilities over all possible reward contexts E 3j (the number of which is bounded by XY) and transition context e (the number of which is bounded by (XY)4) get
U,
P(M& & Ma)
Σ
(() - (2)) {222)
P-Il p'(1)) < (2())
(33)
j=l
2E
i= DEC;
U,
U.
6
6
8
Σ
(34)
20 XYk
2U
k
jml ZEZ;
(= rEC;
desired.
D.2 Upper Bounding the Regret
The regret can be upper bounded by the sum of the errors made at each node.
Lemma D.3. If MG.x and Mt belong to the confidence set at time step k, Mr, then the one-step Bellman error upper bounded by the size of the confidence interval:
I(T Trucn)
Vi ( S H min
(c)) t (=f),
(35)
Proof. Error in the atomic Bellman operator has the most impact if the value function is high; we can then directly upper bound the value function with H.
|T
-T Vk A+ 1 (Su+2) HI(TT MT. Trach)
(36)
116 H
1111
nh
Th 11 p (4% ( (ttw))
<
x (x
II
p (=
II
(37)
mh
M4+11
< H
A (x
r (x
p (4 1ch
p (o (
(38)
< H
the (1x)) (c
Σ
2 (ailch)))
pk (4 - ptr (1
(39)
< H min
N (2h,p) + Bx (ch+1
(40)
Equation is directly obtained using the definition of the atomic Bellman operator equation Then equation obtained by grouping logether the terms depending the atomic reward functions and the one depending the atomic transition functions. To obtain equation 39 we the following inequality:
38
a - 1=1
I
b
a,
bel,
Va,, b, < 1.
i=1
Finally, in equation 40 we upper-bound the error in the transition and reward function at cach node with the width of the corresponding confidence interval. Note that since the reward at each time step is bounded in [0, 1), the sum of all the nodes' errors in given layer is upper-bounded by 1.
25

---

Published in Transactions on Machine Learning Research (03/2025)
With this upper bound the Bellman error, we now equipped to upper-bound the regret; we first decompose it as follows, observing that 4S S H for any & E (1,.., K). Hence,
K
K
Σ
D
Σ
DB ll AMG. H E [ (MGeME) + +1 (MggeMti
By Lemma D.1 E[ E a ( |P,] E[ (MGeMM)) [Pul- | Additionally, setting 8 # in Lemma D.2
shows the true DAMDP Mj does not belong to the confidence set at time step k, M with probability P(M& & MM) < t.. Then,
E
k
S E
d 1 (M.. MGMM
+ 2H
Σ k=1
PMM & M²)
(41)
2 E
E BI Man (MM,
+ 2HH
(42)
K
H
E
IT Buch
T Tr V h+1 +1)11 MEMM) + +2H
(43)
1=
h=1
H
Thg
(c) + A/ (z+) 1]] + +2H,
S HE
min
Σ
(44)
where Eq. 42 is obtained by applying the tower property and noting that Mr is measurable if Mg.x is known. Equation 43 is the definition of the modified regret term (see equation 18 Finally, equation 44 is a direct consequence of Lemma D.3 We also denote by n the number of nodes in G; we use is to denote the equivalence class of the node v and ju to denote the atomic action set available at node v. The transition context observed during episode & at node e is denoted by cg E C,,, and the reward context observed at node during the Etth episode is denoted by 2 E Zj..
The contribution to the regret incurred by errors in the reward function ré. can be upper-bounded by the sum of oé for every episode and every node E Vj, where V, is the set of nodes that exhibit the reward architecture j. Then, for single reward architecture j we have:
Σ R=V
Σ
Σ
Σ
Σ
(xp))))
(NT) (eg))
k=lvel
S=IveV
K
K
log (1 U.XXYmi
(
max (1, NT. (=())
k=
k=leeV,
Where 2f E 23 is used to denote the reward context observed in the th node of G during the 8 episode.
Consider a fixed = =. The where (z)( & mi happens less than 2mL times for each E Z, can be upper bounded as follows E I (N))()) S 2m,.Y. Now, let's suppose that NT. (z) >> m² for
a E 2,- In the th episode, for any node v E Vj, we have NrJ. (2) +1 S (z. + m. S 2N t (z). Note that the number of occurrences of a specific reward architecture in each layer depends on G, but we know that it occurs mg times over episode.
26

---

Published in Transactions on Machine Learning Research (03/2025)
We can then bound the following ratio:
K
1 (2
K
2
(45)
Nite (2k,e)
Ne (2k,0) +
VEV,
k= NEV,
Kmn
v Σ
(NT (z)) +1)-1/2
(46)
My (+)
V2 Σ
b b-1/2
(with T3 = Km + 1)
(47)
2E2,
b=1
S 2 Σ
x 1/2
(48)
2EZ, J
S 2XY
(3)
V2XY V2XYKm.
(49)
ZEZ,
Equation 46 rewrites the two sums as single one, where now, each index t in Nº uniquely encodes pair (tx, n). We obtain equation 47 by considering all possible reward contexts 2 E 2j and the total number of times this specific reward context was visited. In equation 48 we use the fact that the sum Σi=+1 x x/2 is
upper bounded by J.N dz/ Lastly, equation 49 is obtained by Cauchy-Schwartz inequality.
With the same approach, can bound the regret incurred by the error in the 8th transition function,
K
K
K
Σ
((()) S
Σ Σ
(cr)((())m
Σ
VEV,
k=vvEv
k=
where V; denotes all the nodes of the equivalence class [Ta]. For any e C,, the case where (c)(() s m happens less than 2m, times. Given that |C:] S (XY)4, we can upper-bound Σ Evev. (17)) S 2m; (XY)4, For a given transition context e and episode & when N > m., we have that for any node VE Vi, No. +1 (c) + m s (c).
We can then bound the following ratio:
K Σ
(cD)mm))))) NT
K
(50)
NZ (+) +1
kEV
k=1vEV
Km
= /2 Σ
(N) + +11-1/2
(51)
(e)
I 2
b-1/2
(with T, = Km, + 1)
(52)
3EC; b= l
(oTi(()
$
2
-1/2
(53)
DEE.
2(XY) de
(c)
22(XY)) Km,
(54)
CEC;
Where all steps here are obtained following the same reasoning as in equation 45
toequation 49
27

---

Published in Transactions on Machine Learning Research (03/2025)
Because the rewards at every time step (or layer) are bounded in [0, 1], the total regret consists of the following:
min
H
min
7k
+
2 (2)) (6)))))))))
(55)
k= h=
Ur
min
H
2mfXY + v 2X Lo
j=1
U.
2 2m 2x km (X log( + 2d, log(U, (o
+11
(56)
Ur
1 <min
H
2 + D0V KH
j=1
2 + 2d, (og(2UXXYm,)))) KH 2m (XY) + 2(XY) Km, (X log(
min
H
(57)
To complete the proof, we note that min(a + b, S Vac + b holds for a, b.c. > 0. We then apply this inequality twice in equation 57
U, X +
Equation 57
KH
2x
1=1
KH
2m (XP)d:
2( HKm, (X 2d, Log(2U,XYm
U,
< H Σ
V 122
Kmf log( XY +
Σ 22 + 2d, (2, XYmKKK Kt)))
This gives us the result obtained in Eq.
E Regret of PSRL on the full MDP
A natural baseline our approach is to consider the Posterior Sampling for Reinforcement Learning (Osband ct al.] 2013) algorithm. This algorithm can solve any DAMDP by considcring the MDP built from the DAMDP's atomic components. In that case, the algorithun will directly learn the full state transition distribution P and the reward function R.
To simplify the analysis, we upper bound the state space at each time step t, S, S Nmax, with the largest state space in the MDP, note that Nmar denotes the nurbee of nodes in the largest layer. Similarly, we upper bound the full action space at each time step f, C D.Nmas
If we apply the results of Osband et al. 2013) to the proposed MDP, get regret of
of Nmex V Nimes Tlog(()))))))))) Nmaz T)
(58)
F Computational complexity of PSGRL
This section provides an analysis of the computational complexity of running PSGRL. In PSGRL (sce Alg. 2 there are two sub-routing routines with non-trivial runtime, i.c. 'Sample MG.k f(-ID.,)" and "Compute μ Vo. using Algorithm
28

---

Published in Transactions on Machine Learning Research (03/2025)
GE
G :
3
G2:
G221
Figure 5: Illustration how transform a directed acyclic graph (on the left) into a layered directed acyclic graph (on the right)
First, let's consider the operations when the algorithm "samples Mc.x f(-lD=)'. At this point, the algorithm needs to sample the alomic transition and reward functions, {or jo' and {r² In the case of the transition function, the algorithm requires sampling the parameters for every equivalence class i [U>]. every context с E C, and for any potential next atomic state æ X. This consists of OUU Xddmaxx ydd operations. Similar reasoning combined number of operation to be O(U,X22mxr ydmax + U,XYY.
be used regarding the sampling of the reward functions. Resulting in
Second, the planning phase does not benefit from any speed up and is equivalent to the computa- tional complexity running backward induction on the considered non-stationary MDP, which consists of OΣ A,A operations.
In conclusion the computational complexity of running PSGRL for every episode k [K] consists of O
" 1=1 S.A, + +U 2dmma ydmax X,XY) operations.
G Additional properties of DAMDP
Remark G.1. Any DAMDP with an arbitrary DAG, G, has equivalent DAMDP with layered directed acyclic graph, G'.
We now show how a LDAG, G', can be constructed from a DAG, G. particular, we focus on two possible transformations that are illustrated in Figure that is, when an edge spans more than one layer (first row of Fig. 5) or when we have a transversal edge, i.e. an edge that connects two nodes that belong to the same layer, (second row of Fig.
Note that both illustrations Figure suggest that to transform DAG into LDAG, we need to add artificial nodes (represented by a red square) and artificial edges (coloured in blue and orange). The artificial node does not directly increase the complexity of the problem, as both its atomic state and atomic action will be identical to the atomic state and atomic action of its unique parent node. The additional edges do not increase the problem complexity as when we remove an "illegal' edge with a single orange edge and a single blue edge. In particular, it leaves the number of equivalence classes U, unchanged since all incoming illegal edges were replaced by single blue edge, and it leaves the number of action spaces unchanged as well all outgoing illegal edges are replaced by an orange edge. Since those transformations are always possible and leave the DAMDP characteristics unchanged, they have no impact on the algorithm complexity measure presented Theorem 5.1
While this argument reasonable problems of the type of "the leaky maximum flow" problem, this will not necessarily hold for more complex problems such as the wind farm optimization problem. Indced, the LDAG assumption allowed to assume all the layers spaced uniformly in the field. Hence, the
29

---

Published in Transactions on Machine Learning Research (03/2025)
transition context did not necessarily have to include information about the relative distance between two wind turbines, for example. If we would like to consider such scenarios, then the transformation ions are not trivial and will have repercussions on the algorithm's 's regret.
H
Additional experiments
In Figure D we present an additional set of Ieaky maximum flow experiments. We consider an alternative graph structure presented in the first row of Figure Observing the respective performance of PSRL and PSGRL, we can see that as the graph complexity increases, the benefit of PSGRL increases as well. These results are similar to the experiment presented in the main paper; we just revisit this experiment considering different network architecture. In the leftmost case, we see no benefit in using PSGRL as we have single node per layer. However, same equivalence class, the benefit of PSGRL becomes more evident.
increase the central grid of nodes, creating multiple nodes that belong to the
200
400
1500
psgrl
2000
Cumulative Regret
Cumulative Regret
Cumulative Regret
1250
Cumulative Regret
psri
150
300
1000
1500
100
200
750
1000
500
50
100
500
250
0
0
0
0
5000
5000
5000
5000
Episodes
Episodes
Episodes
Episodes
Figure 6: The first row depicts the graph that governs the DAMDP. The second row shows the learning curve for both algorithms considered. PSRL, which ignores the latent graphical structure and PSGRL, which leverages the graphical structure. The left-most plot shows the performance obtained on a simple chain graph. As expected, the performance for both algorithms is similar. Looking the remaining plots, it becomes clear that we increase the complexity of the graph, the benefit of PSGRL becomes self-evident.
30


Reviews:
[{"review_id": "YZCOJSOsEm", "reviewer": "Reviewer_Djn6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- It is an interesting and potentially practically consideration to involve graphical structures to capture the state-action spaces in MDP. This may inspire follow-up research towards a closer connection between RL and graph learning.\n\n- The overall writing is clear (although some modifications would be nice, as detailed in the following) and the authors did a good work in structuring the work and highlighting the contributions. The graphical illustrations are very helpful.\n\n- Rigorous theoretical results are provided for the proposed algorithm. In particular, the illustration that it can achieve better performance than the general lower bound is important to highlight the effectiveness of leveraging the structures.\n\n- The experiments are nice practical verifications of the algorithmic effectiveness.\n\nWeakness\n- The discussions on the planning, i.e., Section 3.2, seems straightforward to me without much contributions. Especially, given that the DAMDP is a subclass of MDP, many results seems as standard corollaries and extensions from MDP. If I missed anything specific to DAMDP, let me know.\n\n- The algorithmic design could be elaborated better. Especially, I believe that the key difference is how to leverage the graphical structure, which is however largely omitted in the main paper. Without that, the algorithm seems just as a common posterior sampling algorithm. I would encourage the authors to involve more discussions on how the algorithm leverage the structure.\n\n- Similarly, for the theoretical analyses, I believe it would be important to further highlight the uniqueness/contribution done in this work, which I believe lies in the construction of confidence sets, while that part is currently not discussed in the main paper.\n\n- Even with the specific construction of confidence sets, I still feel that the analyses largely follow previous works. In that sense, to highlight the problem class studied in this work, it would be more desired to show that different previous algorithms, not just PSRL, can be extended effectively with better performances, e.g., those in non-Bayesian setting and the model-free ones.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new subclass of the general MDP, i.e., DAMDP, which associates the state-action space with graphical structures. This subclass may be able to model some practical problems (e.g., the wind farm example provided by the authors). Theoretically, the newly introduced graphical structure allows algorithm design to speedup exploration and learning. As concretely demonstrated by the proposed design, a Bayesian regret bound can be achieved which is better than the lower bound in the general setting. Experiments are reported in two examples to verify the performance of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would encourage the authors to think about the points mentioned in the above weakness discussions, especially how to highlight the difference/contribution of the algorithmic design and analyses of this work.", "broader_impact_concerns": "This work is mainly theoretical and considering the extension of current RL studies, which I do not foresee major negative social impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4qSHrnX09o", "reviewer": "Reviewer_xpnV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n* Clear contribution: Show that a DAG structure can be used in combination with an MDP\n* Well-written: the paper is well structured and well written overall, see comments below\n* Experiments are nicely chosen to illustrate the benefits and limitations of the method\n\n## Weaknesses:\n* Perhaps limited impact? It is hard to judge but I guess so far people used function approximation (linear first, and then more general) to model the structure, and I am not sure why the graph would be more powerful\n* Section 3 would greatly benefit a more complete figure to illustrate the setting\n\n## General comment:\n\n1/ I believe this is an interesting proposal which can have some practical applications and bridge the tabular setting and the function approximation setting more commonly used when the state-action space is structured. Perhaps this connection could be made more explicitly? \n\n2/ Overall, the paper is well written and the contributions are clear. I believe that the notation is heavy and could deserve a bit more pedagogical presentation, typically via a Figure more complete than Figure 1, that should actually show what are “contexts”, and the related transition probability definitions. It took me a while to understand what are the different elements of your structure and Figure 1 only partially helps. The “All contexts” illustration is actually confusing, the “atomic action” y is either one arrow or 2 arrows? Why is it the same notation? I don’t understand the second column very well, what are the orange nodes? Anyway, what I mean is that in Section 3, you introduce a lot of notation and concepts like the equivalence classes, and this Figure does not help us processing them. I think it’d be really helpful if it would. \n\n3/ Unless I missed something, you do not comment on the discounted MDP setting. Is the finite-horizon crucial in preserving the dynamic programming consistency? Also, your transitions and rewards don’t explicitly depend on t, except through the graph structure, but you chose to denote U_x the  number of parameters for each component of the MDP instead of H. Can you say how H compares to U_x, for x\\in{r,\\tau}?\n\n## Minor comments:\nA/ In Section 5, there’s a repeated sentence:  “We observe that there are 6 nodes with a single incoming edge (i.e. m1 τ = 6) and 9 with two incoming edges (i.e. m2 τ = 9)” is said almost exactly identically a couple of lines above. \n\nB/ The line graph on the left of Figure 2 seems to suggest that DAMDPs are not so useful for these types of structures, and on Figure 3, the wind turbines you consider seem to be precisely organized as line graphs. I see that the wind turbines are in a grid, not just a line, but perhaps this choice of structure (and why it’s relevant) could be better discussed?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In a tabular finite-horizon MDP, the paper proposes to structure the state-action space with a “layered directed acyclic” graph, thus defining DAMDPs. The main idea is that states are now a combination of “atomic states” which are the nodes of a graph. Given a full state, the transition to the next full state is then defined by the product over probabilities defined by the graph structure. This modification of the value function definition is shown to preserve the good properties of RL, namely dynamic programming, and the authors show they can naturally extend algorithms based on extended value iteration, such as PSRL (Osband et al., 2017).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A nice and complete Figure 1 that pedagogically explains the proposed structure and the notation", "broader_impact_concerns": "Nine", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "toawpWQtWb", "reviewer": "Reviewer_yEM6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\n1. The DAMDP framework extends MDPs with DAG-based structures, enabling modeling of real-world problems like wind farm optimization and network flow.\n2. The paper provides a rigorous analysis of Bayesian regret for PSGRL, showing clear efficiency gains.\n\n3. Real-world applications (e.g., wind farms) and experiments provide compelling evidence of the framework’s applicability.\n\n 4. Definitions and explanations (e.g., state/action decomposition, equivalence classes) are precise, though hard to grasp at first glance.\n\n**Weaknesses**:\n\n1.   The assumption of known DAG structures may limit applicability to cases where such structures must be inferred.\n\n2.   While leveraging DAG structures reduces complexity, the scalability for very large graphs with many equivalence classes is unclear.\n\n3.  Comparisons primarily focus on PSRL. Evaluating against other RL methods (e.g., model-based RL) would strengthen empirical claims.\n\n4.   The framework focuses on discrete state/action spaces. It is unclear whether we could extend to continuous spaces, as mentioned in future directions, which would broaden applicability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces Directed Acyclic Markov Decision Processes (DAMDPs) as a subclass of Markov Decision Processes (MDPs) that leverage directed acyclic graph (DAG) structures in state and action spaces. \n\nThey introduce \n\n  - A dynamic programming algorithm is developed to find optimal policies in known DAMDPsand a posterior sampling-based reinforcement learning algorithm is proposed for DAMDPs.\n\n - An upper bound on Bayesian regret for PSGRL, demonstrating improved efficiency over standard reinforcement learning approaches that ignore graph structures.\n\nExperimental results on graph flow optimization and wind farm yield optimization showcase significant performance improvements of PSGRL over baseline methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.   Include comparisons with additional reinforcement learning algorithms beyond PSRL, particularly model-based approaches or methods handling structured environments.\n\n2.  Explore performance on other real-world problems or synthetic graphs with varying structural properties.\n\n3. In Figure 1, the horizon $H=3$ appears to match the number of states. Is this property universal for DAMDPs? From Definition 2.2, the horizon $H$ seems always equal to the number of layers in an LDAG. Clarify whether this holds for all DAMDPs and, if not, provide examples where this differs.\n\n4. Section 3.1 is difficult to follow without an example. Use a detailed scenario, such as wind farm optimization, to illustrate:\n     - How atomic transitions and rewards relate to full state and action dynamics.\n     -  The benefits of DAMDP over standard MDPs.\n\n5. Provide a detailed analysis of how computational costs scale with the number of equivalence classes and graph size. How do equivalence classes and graph size affect efficiency? How does DAMDP compare to standard MDPs with similar state/action space sizes?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YxU19gPDm3", "reviewer": "Reviewer_6dxW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- Utilizing prior information to improve reinforcement learning algorithm represents a key challenge. The proposed method is a good step into this direction and is also supported with a real-world example.\n- The presentation is very clear and the paper is well structured.\n- The theoretical proof is well presented and necessary details are well explained.\n\n# Weaknesses\n- In the experiment, the authors compare PSGRL that has access to the graph structure against PSRL that has no prior information. This comparison feels a bit unfair considering that it is possible to partially encode the graph structure in PSRL via the Dirichlet prior distributions.\n- The MDPS used for the experiments seem to all have a small state space. Is there any reason for this? How is the scalability of the algorithm in practice? What are the computation challenges?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors investigate a specific structural assumption of MDPs based on DAGs. They show that it is possible to apply dynamic programming and posterior sampling in this setting where the main advantage is that the resulting algorithm can learn more efficiently by exploiting the known graphical structure. A rigorous theoretical analysis of the approach is included.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Changes\n- Could you run the experiments of PSRL again with the graph structure encoded in the prior distributions? In other words, if there is a known edge between `s` and `s'` you can add pseudo counts in the corresponding distributions.\n-Could you add a brief section regarding the practical computational cost of running PSGRL?", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Given that the claims are clearly supported by evidence, that there is interest in the TMLR community, the writing is clear, and rigorous theoretical results are provided for their algorithm, I recommend acceptance.

Please finish all changes you described in your "reply to all reviewers".
Decision: Accept (poster)