arXiv:1801.00048v1 [] 29 Dec 2017

Characterizing optimal hierarchical policy inference
on graphs via non-equilibrium thermodynamics

Daniel McNamee
Computational and Biological Learning Lab, University of Cambridge
d.mcnamee@eng.cam.ac.uk

Abstract
Hierarchies are of fundamental interest in both stochastic optimal control and
biological control due to their facilitation of a range of desirable computational
traits in a control algorithm and the possibility that they may form a core principle
of sensorimotor and cognitive control systems. However, a theoretically justified
construction of state-space hierarchies over all spatial resolutions and their evolution through a policy inference process remains elusive. Here, a formalism for
deriving such normative representations of discrete Markov decision processes is
introduced in the context of graphs. The resulting hierarchies correspond to a hierarchical policy inference algorithm approximating a discrete gradient flow between
state-space trajectory densities generated by the prior and optimal policies.

1

Stochastic policy inference in discrete Markov decision processes

Let M := {X , P, R} be a discrete MDP where states are denoted x ∈ X and R(x) is the reward
associated with a state x. It is assumed that actions are deterministic transitions on the state-space
X and thus the MDP can be summarized as a directed graph (though the general formalism is not
restricted to this case). Let x := (x0 , . . . , xT ) be a state trajectory1 with an arbitrary horizon T
(which might be infinite). Then the MDP objective from a “sum-over-paths” perspective [5] is
" T
#
X
∗
R(xt )
(1)
π := argmin Eπ [−R(x)] ≡ argmin Eπ −
π

π

t=0

where π is the “policy” over state trajectories induced from the policy π. This MDP can be embedded
in a linearly solvable MDP [13] (or equivalently, a KL Control problem [6]) by subtracting a policy
description length penalty −β −1 log π(x) for each state trajectory x [10]. This allows the objective
(Eqn. 1) to be re-formulated as a free energy functional J [π] incorporating a policy entropy H[π]
maximization objective:


J [π] = Eπ −R(x) + β −1 log π(x)
= E [π] + β −1 S [π]

(2)

where the entropy and energy terms are denoted E := Eπ [−R(x)] and S := −H[π] respectively.
This policy functional encapsulates the trade-off between policy value and policy complexity (Eqn. 2)
in the space of state trajectories X . By considering this inverse temperature parameter in the limit
β → ∞, one recovers the standard MDP objective of maximizing expected cumulative reward
[10, 12]. For simplicity, the inverse temperature is set to β = 1. A well-known trick [9, 13], is that
1

In general, bold type will be used when referring to trajectories.

Hierarchical Reinforcement Learning Workshop at the 31st Conference on Neural Information Processing
Systems (HRL@NIPS 2017), Long Beach, CA, USA.

both the optimal trajectory policy π ∗ and the minimum energy J [π ∗ ] can be expressed in closed
form using the Gibbs-Boltzmann distribution:
π ∗ (x) ∝ π prior eR(x)
J [π ∗ ]

h
i
= − log Eπprior eR(x)

(3)

These formulae explicitly reflect the balance between a control complexity penalty (minimized
by the prior policy π prior ) and reward eR(x) . An optimalPtransition policy π ∗ can be computed
by marginalizing over future trajectories, π ∗ (xt+1 |xt ) = xt+2:T π ∗ (xt+1:T |xt ), a calculation to
which standard approximate inference methods can be applied [6]. However, the goal of this study is
not to compute a transition policy π but to gain insight into the hierarchical structure of the MDP.
This will be accomplished by characterizing the dynamics of the trajectory policy π generated by an
optimal policy inference algorithm as it is transformed from the prior π prior to the optimal policy π ∗ .

2

Planning via non-equilibrium thermodynamics

This question will be addressed by exploiting the physical interpretation of the free energy functional
(Eqn. 2). It is the energy functional of a stochastic system of “particles” taking “positions” in the
discrete space of state trajectories which (i) are initialized accord to the density π prior , and (ii) evolve
over time τ under the influence of the potential Ψ(x) := −R(x). The Langevin dynamics associated
with the potential Ψ(x) cause particles to be attracted to state trajectories x with higher rewards. The
trajectory policy π τ reflects the density of such particles in trajectory space at time τ . The unique
thermal equilibrium of this system (i.e. the density of particles in the lowest energy state) is the
optimal policy π ∗ ≡ π ∞ given by Eqn. 3. Conceptually, planning (as inference [14]) is accomplished
by initializing the particle system at the prior policy π prior (away from the equilibrium density π ∗ )
and then allowing the particles to evolve according to the non-equilibrium thermodynamics described
above. Instead of simulating the stochastic dynamics of these particles, the evolution of their density
is studied. This is given by the Fokker-Planck (FP) equation for which the optimal policy π ∗ is the
unique stationary solution [1]:
π̇ = ∇ [(∇Ψ)π] + ∆π

(4)

where π : [0, ∞) × X → R doubles notationally as a policy flow (i.e. at each policy inference
timepoint τ , π(τ, ·) := π τ defines a trajectory density). Furthermore, the FP equation has the
following remarkable property – the time evolution of π τ according to the FP equation is guaranteed
to reach the optimal policy π τ → π ∗ , τ → ∞ by the steepest descent2 on the free energy functional
J [2, 4, 8]. At this global minimum, π ∞ will equal the optimal policy π ∗ and the particles will
remain in equilibrium. This implies that the FP equation is the gradient flow of the free energy J [π],
and therefore the evolution of π prior → π ∗ described by equation 4 is that generated by an optimal
policy inference algorithm. Since this stochastic process is considered at the level of trajectories, it is
described as “hierarchical” policy inference with respect to state transitions since it is sensitive to
dependencies between states at all temporal horizons. In the next section, the optimal probability
density flux between trajectories (Eqn. 5) will be re-expressed as a function of states (Eqn. 12).
Summing the total flux at each state (Eqn. 14) at each planning timepoint τ returns a dynamic state
hierarchy reflecting the magnitude of policy flux at each state under optimal policy flow.

3

Policy flow as a discretized differential equation

Applying the FP equation (Eqn. 4) in the context of variational optimization requires a temporal
discretization [1, 4]. Here, a spatial discretization is also required since the MDP state-spaces
considered are discrete. A spatially discretized form of the Fokker-Planck equation can be constructed
based on a Markov chain approximation of the underlying Langevin dynamics such that it retains the
key properties of the continuous case [2, 8]. Let π be the current trajectory policy (e.g. π = π prior at
planning timestep τ = 0) and define the generalized potential Ψ̄(x) := −R(x) + log π(x). Then
2

With respect to the Wasserstein metric – see the supplementary information for a definition.

2

the discrete FP equation (Eqn. 23, Supplementary Information) is
X


π̇(x) =
K(x, x0 )M (x, x0 ) Ψ̄(x0 ) − Ψ̄(x)
x0 ∈X
0

K(x, x )


=

π(x0 ) if Ψ̄(x0 ) > Ψ̄(x)
π(x) if Ψ̄(x0 ) < Ψ̄(x)

(5)

and M is the Markov stochastic matrix over the set of trajectories generated by the current policy
and K is a Laplacian kernel. Since trajectories are conditionally independent (across “samples” or
“episodes” in the MDP), M (x, x0 ) = π(x0 ). If Ψ̄(x0 ) > Ψ̄(x), the policy density at x increases due
to the inflow of policy “particles” attracted by the lower energy state associated with the generalized
potential Ψ̄(x). The policy flux along the “velocity field” defined by K is driven by two fluxes
(i) −∇R “pulls” policies towards action sequences with large expected rewards, and (ii) ∇ log π
“pushes” the policy away from policies with large description lengths. Summing over trajectories, the
total flux is
X
X


K(x, x0 )M (x, x0 ) Ψ̄(x0 ) − Ψ̄(x)
(6)
π̇(x) =
x,x0 ∈X

x∈X

X

=



π(x)π(x0 ) Γ− (x, x0 ) − Γ+ (x0 , x)

(7)

x,x0 ∈X

where the following functions have been used:

Ψ̄(x0 ) − Ψ̄(x) if Ψ̄(x0 ) > Ψ̄(x)
Γ+ (x, x0 ) :=
0
otherwise

0
Ψ̄(x) − Ψ̄(x ) if Ψ̄(x0 ) < Ψ̄(x)
Γ− (x, x0 ) :=
.
0
otherwise

(8)
(9)

These functions measure the density gain Γ+ (x, x0 ) and loss Γ− (x, x0 ) at each trajectory x due to
0
+
0
the optimal policy flux with respect to another trajectory
Px . Note that, for every Γ (x, x ) term there
− 0
is an equal and opposite Γ (x , x) term and therefore x π̇(x) = 0 reflecting thePFP equation’s role
as a differential continuity equation for the conservation of total probability i.e. x π̇(x) = 0.

4

“Pulling back” from trajectories to transitions

Although the total flux across trajectories is zero, the total flux associated with a particular state in
the original state-space X is not and reveals a state-space hierarchy. In this section, formulae are
recorded for these total flux values which reflect a state’s “rank” in the optimal hierarchy (Section 8,
Supplementary Information). For a pair (x, x0 ) of trajectories such that Ψ̄(x0 ) > Ψ̄(x):
|x|−1 |x0 |−1
+

0

Γ (x, x )

=

X X
t=0

Γ(xt , x0t0 )

[Γ(xt , x0t0 )]

(10)

t0 =0

Ψ̄(x0t0 +1 |x0t0 ) − Ψ̄(xt+1 |xt )
(11)

−R(xt )
where Ψ̄(xt+1 |xt ) := log π(xt+1 |xt )e
is the contribution to the generalized potential from
transition xt → xt+1 . Using Eqn. 34, one can rewrite this in terms of states as:
X
X
π̇(x) =
KD (x, x0 ) [Jπ (x) − Jπ (x0 )]
(12)
=



x∈X

x,x0 ∈X

where Jπ (x) = Ex0 ∼π(x0 |x) [Ψ̄(x0 |x)] = −R(x) − Hπ (x) is the local contribution to the free energy
objective (Eqn. 2) and

Dx0 ,x0 Dx0 x if Jπ (x0 ) > Jπ (x)
KD (x, x0 ) =
,
(13)
Dx0 ,x Dxx0 if Jπ (x0 ) < Jπ (x)
where x0 is the initial state and D := (I − Pπ )−1 is the fundamental matrix of the Markov chain
generated by the policy π. Ultimately, the discrete Fokker-Planck equation can be re-expressed
geometrically using a discrete Laplacian operator ∆D defined by KD [16]:
π̇(x) = ∆D Jπ (x) .
3

(14)

The role of the discrete Laplacian operator here has an intuitive physical meaning. The generalized
potential is not independent across states x (due to its dependence on π) analogous to the dependence
of, for example, a gravitational potential across distinct positions in the real world. A typical operation
in mathematical physics is to identify the independent sources which generate a physical field (e.g.
planets). This is accomplished by taking the divergence of the field which is equivalent to the
Laplacian of the field’s potential. Considering the local energy potential Jπ (x) as generating a
“planning complexity field”, this suggests that equation 14 can be interpreted as FP dynamics “solving”
the planning problem by targeting the independent sources which “generate” the planning complexity.

5

Example: a regular graph

As a simple, expository application, a regular graph which has previously been used for behavioral
experimentation [11] is considered. In Fig. 1A, each node represents a state (displayed as a fractal to
the participants in the experiment) and each edge an available transition. Regular graphs such as this
provide a challenging scenario for elucidating hierarchy due to their homogeneous local structure
(the number of available transitions is the same at each state). Despite this, there is an obvious
bottleneck between two “rooms” in Fig. 1A. Participants were tasked with solving shortest-path
problems between uniformly drawn states. In Fig. 1A, darker node color reflects higher ∆D Jπ (x)
(Eqn. 14) and thus one can observe that the key bottleneck is recovered. Participants were also asked
to identify “bottleneck” states in this state-space despite never having observed its global structure.
The hierarchical state ranking measure ∆D Jπ (x) approximately matched the full distribution of
bottlenecks chosen explicitly by subjects [11] which had not been previously predicted in a model.
The implication of the analysis presented here is that an optimal planning process should prioritize
the identification of transitions in the hierarchical order measured by ∆D Jπ (x) as this reflects the
steepest descent on J [π] over all trajectories. From an information-theoretic perspective, a transition
at a bottleneck state “communicates” the most amount of information regarding a shortest path
between states on average and the second highest ranked states give the next highest amount of
information and so on. This prediction was tested by simulating an “oracle planner” which simply
identifies the optimal transition at a given state on a shortest path or reveals that the state is not on the
shortest path. This procedure iteratively refines the set of candidate trajectories until a shortest path
is identified. The entropy of the remaining candidate trajectories measures the expected amount of
information remaining to be specified by the planning algorithm. This is plotted as a function of the
number of oracle samples in Fig. 1B-E. In Fig. 1C, trajectory entropy is plotted for the optimal oracle
sampling order, and in Fig. 1D, the average per shortest path length (darker is longer) is presented. As
expected, no random oracle sampling order (Fig. 1B) outperforms the optimal hierarchical sampling
order on average across tasks (Fig. 1E).

Figure 1: Trajectory entropy dynamics due to “oracle” planning on a regular graph.

6

Discussion

A preliminary study of discrete gradient flow in the context of hierarchical policy inference has
been presented. Amongst all possible policy inference processes, the FP equation describes the
expected time evolution of those which take the steepest descent on the free energy objective thus
establishing a principle of optimality. Considering policy inference in trajectory space implies that
state-space structure at all scales is integrated into the policy inference process. The resulting policy
flow provides a normative perspective on optimal hierarchical policy inference however it remains to
be seen whether the principles established here can be usefully embedded within practical algorithms.
The basic example provided establishes a link with hierarchical representations in human cognition
and thus a potentially fruitful research direction will be to examine whether aspects of the behavioral
and neural dynamics of natural planning and problem-solving can be explained within this framework.
4

Acknowledgements
Thanks to the reviewers for their feedback and Máté Lengyel and Daniel Wolpert for discussions.

References
[1] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savare. Gradient flows in metric spaces and in the
space of probability measures. Birkhauser, 2008.
[2] Shui-Nee Chow, Wen Huang, Yao Li, and Haomin Zhou. Fokker–Planck Equations for a Free
Energy Functional or Markov Process on a Graph. Arch. Rational Mech. Anal, 203:969–1008,
2012.
[3] Peter Dayan. Improving Generalization for Temporal Difference Learning: The Successor
Representation. Neural Computation, 5:613–624, 1993.
[4] Richard Jordan, David Kinderlehrer, and Felix Otto. The Variational Formulation of the
Fokker-Planck Equation. SIAM Journal on Mathematical Analysis, 29(1):1–17, 1998.
[5] Hilbert J. Kappen. Linear theory for control of nonlinear stochastic systems. Physical Review
Letters, 95(20):1–4, 2005.
[6] Hilbert J. Kappen, Vicenç Gómez, and Manfred Opper. Optimal control as a graphical model
inference problem. Machine Learning, 87(2):159–182, 2012.
[7] John G. Kemeny and J. Laurie Snell. Finite Markov Chains. Springer-Verlag, 1983.
[8] Jan Maas. Gradient flows of the entropy for finite Markov chains. Journal of Functional
Analysis, 261(8):2250–2292, 2011.
[9] Sanjoy Mitter and Nigel Newton. A variational approach to nonlinear estimation. SIAM Journal
on Control and Optimization, 42(5):1–21, 2003.
[10] Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal control and
reinforcement learning by approximate inference. Robotics: Science and Systems, 13(2):
3052–3056, 2012.
[11] Alec Solway, Carlos Diuk, Natalia Córdova, Debbie Yee, Andrew G Barto, Yael Niv, and
Matthew M Botvinick. Optimal behavioral hierarchy. PLoS Computational Biology, 10(8):
e1003779, aug 2014.
[12] Evangelos Theodorou, Krishnamurthy Dvijotham, and Emo Todorov. From information theoretic dualities to path integral and Kullback Leibler control: continuous and discrete time
formulations. 2013.
[13] Emanuel Todorov. Linearly-solvable Markov decision problems. Advances in Neural Information Processing Systems, 19(1):1369–1376, 2007.
[14] Marc Toussaint. Probabilistic inference as a model of planned behavior. Künstliche Intelligenz,
3(9):23–29, 2009.
[15] Cedric Villani. Optimal transport: old and new. Springer, 2009.
[16] Max Wardetzky, Saurabh Mathur, Felix Kaelberer, and Eitan Grinspun. Discrete Laplace
operators: No free lunch. Eurographics Symposium on Geometry Processing, pages 33–37,
2007.

5

Supplementary Information
7

Free energy, the Fokker-Planck equation, and variational optimization

A brief, self-contained, introduction to the properties of the Fokker-Planck equation in the context of
variational optimization is provided.
7.1

Stochastic processes and the Fokker-Planck equation

A general class of stochastic processes is given by the Itô stochastic differential equation:
√
dx(t) = µ(x(t), t) dt + 2σ(x(t), t) dw(t)

(15)

This equation describes the evolution of a random vector x ∈ X under a drift µ(x(t), t) dt and a
diffusion σ(x(t), t) dw(t). The diffusion coefficient σ(x(t), t) scales a Wiener process w(t) which
describes the accumulation of gaussian noise w(t + dt) − w(t) ∼ N (0, dt). In general xt and
µ(x(t), t) are n-dimensional random vectors, σ(x(t), t) an (n, m)-dimensional matrix, and w(t) an
m-dimensional vector. The Fokker-Planck equation describes the time-evolution of the probability
density ρ of the random vector x:
ρ̇ = −∇(µρ) + ∆(σ 2 ρ)

(16)

where ρ : [0, ∞) × M → [0, ∞) is a probability density flow (i.e. at each timepoint t, ρ(t, ·) defines
a density), M is the underlying manifold, and σ 2 := σσ T is known as the diffusion tensor. The
simplest case of the FP equation is Brownian motion with p
stationary (i.e. time-independent) and
invariant (i.e. position-independent) diffusion σ(x(t), t) = β −1 and zero drift µ(x(t), t) = 0. In
this case, the FP equation (16) is the heat equation with inverse temperature β controlling the “speed”
of the diffusion:
ρ̇ = β −1 ∆ρ
(17)
7.2

Langevin dynamics: drift potential

The special case in which the drift µ is a conservative time-homogeneous vector field corresponds
to Langevin dynamics. Here the vector field µ is generated by a scalar potential µ(x(t), t) =
−∇Ψ(x(t)). Further assuming a “white noise” diffusion with temperature β results in the stochastic
dynamics:
p
dx(t) = ∇Ψ(x(t)) dt + 2β −1 dw(t)
(18)
In this case, the FP equation (Eqn. 16) becomes
ρ̇ = ∇ · [(∇Ψ)ρ] + β −1 ∆ρ

(19)

and the corresponding velocity field v is
v = −∇Ψ − β −1 ∇ (log ρ)

(20)

such that ρ̇ = −∇(ρv). The expression j := ρv is referred to as the current density which reflects
the rate of probability density flow at a particular point x ∈ X.
7.3

Free energy minimization

The FP equation is intimately related to an associated free energy functional J of the density ρ:


J [ρ] = Eρ Ψ + β −1 log ρ
= E [ρ] + β −1 S [ρ]

(21)

where we have the energy E := Eρ [Ψ] and entropy S := −H[ρ] terms respectively. The free energy
J is a Lyapunov function for the FP dynamics (Eqn. 19). Conversely, and remarkably, the FP
equation is a gradient flow of the free energy functional [4]. Specifically, the FP equation defines the
trajectory of steepest descent on the free energy J with respect to the 2-Wasserstein metric dW2 on
the space P(X) of densities ρ, ρ0 ∈ P(X) on X:
Z
dW2 (ρ, ρ0 ) :=
inf 0
d(x, x0 )2 dλ
(22)
λ∈M (ρ,ρ )

6

X×X

where M (ρ, ρ0 ) is the set of probability densities λ on X × X whose marginals are equal to ρ and
ρ0 respectively. Although no derivations in this work will rely on the definition of the Wasserstein
metric, it may be interesting to point out that the appearance of this metric at this juncture is related
to its theoretical foundations in optimal transport theory [15].
Discrete Fokker-Planck theory
Here, our primary interest lies in discrete Markov decision problems thus the translation of continuous
FP theory to the discrete domain is reviewed [2, 8]. X is a discrete state-space (e.g. a graph) with
states
x ∈ X. A density on this state-space is a discrete distribution ρ : X → [0, 1] such that
P
x∈X ρ(x) = 1. A discrete potential Ψ is defined as a mapping from states to real numbers
Ψ : X → R. The discrete form of the Fokker-Planck equation (Eqn. 23) is based on a Markov chain
approximation of Langevin stochastic dynamics and retains the key properties of the continuous case
[2, 8]:
X
ρ̇(x) =
K(x, x0 ) [Ψ(x0 ) − Ψ(x) + log ρ(x0 ) − log ρ(x)]
x0 ∈N (x)

=

X



K(x, x0 ) Ψ̄[ρ](x0 ) − Ψ̄[ρ](x)

x0 ∈N (x)

=
K(x, x0 )

∆Ψ̄[ρ](x)
 0
ρ(x ) if Ψ̄(x0 ) > Ψ̄(x)
=
ρ(x) if Ψ̄(x0 ) < Ψ̄(x)

(23)

where Ψ̄ is the generalized potential:
Ψ̄(x) := Ψ(x) + β −1 log ρ(x)

(24)

The function K can be interpreted as the kernel of a discrete Laplacian operator ∆ applied to the
generalized potential Ψ̄ [16].

8

From trajectories to transitions: expectations of linear functions

Results are derived which will be used in the derivations in the main paper. An absorbing3 Markov
chain with stochastic matrix π is considered. Let f (x) be a function of state trajectories x ∈ X
in this chain and π be the induced probability distribution over trajectories. Assume that f can be
expressed as a sum over states:
f (x) :=

T
X

f (xi ) .

i=1

It is known that the expected value of f is [3]
Eπ [f ]

=

X

Dx0 x f (x) ,

(25)

x∈X

where D is the fundamental matrix of the Markov chain defined by π [7] and x0 is the initial state.
Analogous results for transitions are required. Assume that f can be expressed as a sum over
transitions
f (x) :=

T
−1
X

f (xi , xi+1 )

t=0
3

Analogous results can be derived for regular Markov chains.

7

(26)

Then
Eπ [f ]

X

:=

π(x)f (x)

x∈X

=

X X

π(xT )

X X

f xTt , xTt+1



t=0

T >0 xT ∈X T

=

T
−1
X

T
−1
X

ptπ (x|x0 )π(x0 |x)f (x, x0 )

(27)

T >0 x,x0 ∈X t=0

where ptπ (x|x0 ) is the probability of being in state x on timestep t after starting in state x0 . Therefore
X
Eπ [f ] =
Dx0 x π(x0 |x)f (x, x0 )
x,x0 ∈X

=

X

Dx0 x Ex0 ∼π(x0 |x) [f (x, x0 )]

(28)

x∈X

An intuitive example is given by the transition identity function f := 1x→x0 :

1 iff x = y, x0 = y 0
0
1x→x0 (y, y ) =
0 otherwise

(29)

Then 1x→x0 (x) simply counts the number of occurences of transition x → x0 in trajectory x and
Eπ [1x→x0 ]

Dx0 x π(x0 |x)

=

(30)

which, as expected, is simply the expected number of times the chain is in state x after starting in
state x0 multiplied by the probability of transitioning to x0 . Similarly, letting f be the state identity
function f (x) := 1x implies that Eπ [f ] returns an entry of the fundamental matrix which equals the
expected number of times state x is encountered:
Eπ [1x ]

=

Dx0 x .

(31)

Applying discrete Fokker-Planck dynamics requires us to develop analogous arguments for pairs
of trajectories. Let f (x, x0 ) be a linear sum of states x, x0 ∈ X in trajectories x, x0 ∈ X . The
contribution f (x, x0 ) to f (x, x0 ) for a specific state pair (x, x0 ) is weighted by the multiplicity of
the state combination (x, x0 ) in the set of trajectories X according to the distribution π(x, x0 ) =
π(x)π(x0 ). Analogous to previous arguments, this is equivalent to taking the expectation with
respect to the probability of generating a trajectory according to π with x and then x0 appearing on
arbitrary timesteps:
X
Eπ [f ] =
π(x)π(x0 )f (x, x0 )
x,x0 ∈X
0

=

X

−1 TX
−1
X TX

0

ptπ (x|x0 )ptπ (x0 |x)f (x, x0 )

x,x0 ∈X T,T 0 >0 t=0 t0 =0

=

X

Dx0 x Dxx0 f (x, x0 )

(32)

x,x0 ∈X

Finally, we consider the case where f (x, x0 ) decomposes as a sum of transition pairs within each
trajectory:
X
f (x, x0 ) =
f (x, y) + f (x0 , y 0 )
(33)
x,y,x0 ,y 0 ∈X

Then
Eπ [f ] =

X


Dx0 x Dxx0 Eπ(y|x) [f (x, y)] + Eπ(y0 |x0 ) [f (x0 , y 0 )]

x,x0 ∈X

8

(34)

