{'fraction_non_alphanumeric': 0.0465912171320141, 'fraction_numerical': 0.0127744646245595, 'mean_word_length': 4.59170140204623, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tutorial and Survey on Probabilistic Graphical Model and Variational Inference in Deep Reinforcement Learning

Aiming at a comprehensive and concise tutorial survey, recap of variational inference and reinforcement learning with Probabilistic Graphical Models are given with detailed derivations. Reviews and comparisons on recent advances in deep reinforcement learning are made from various aspects. We offer detailed derivations to a taxonomy of Probabilistic Graphical Model and Variational Inference methods in deep reinforcement learning, which serves as a complementary material on top of the original contributions.


I. INTRODUCTION
Despite the recent successes of Reinforcement Learning, powered by Deep Neural Networks, in complicated tasks like games [1] and robot locomotion [2], as well as optimization tasks like Automatic Machine Learning [3]. The field still faces many challenges including expressing high dimensional state and policy, exploration in sparse reward, etc. Probabilistic Graphical Model and Variational Inference offers a great tool to express a wide spectrum of trajectory distributions as well as conducting inference which can serve as a control method. Due to the emerging popularity, we present a comprehensive and concise tutorial survey paper with the following contributions: • We provide Probabilistic Graphical Models for many basic concepts of Reinforcement Learning, which is rarely covered in literature. We also provide Probabilistic Graphical Models to some recent works on Deep Reinforcement Learning [4], [5] which does not exist in the original contributions. • We cover a taxonomy of Probabilistic Graphical Model and Variational Inference [6] methods used in Deep Reinforcement Learning and give detailed derivations to many of the critical equations, which is not given in the original contributions. Together with the recap of variational inference and deep reinforcement learning, the paper serves as a self-inclusive tutorial to both beginner and advanced readers.

A. Organization of the paper
In section I-B, we first introduce the fundamentals of Probabilistic Graphical Models and Variational Inference, then we review the basics about reinforcement learning by connecting probabilistic graphical models (PGM) in section II-A, II-B, II-C, as well as an overview about deep reinforcement learning, accompanied with a comparison of different methods in section II-D. In section III-A, we discuss how undirected graph could be used in modeling both the value function and the policy, which works well on high dimensional discrete state and action spaces. In section III-B, we introduce the directed acyclic graph framework on how to treat the policy as posterior on actions, while adding many proofs that does not exist in the original contributions. In section III-C, we introduce works on how to use variational inference to approximate the environment model, while adding graphical models and proofs which does not exist in the original contributions.

B. Prerequisite on Probabilistic Graphical Models and Variational Inference, Terminologies and Conventions
We use capital letter to denote a Random Variable (RV), while using the lower case letter to represent the realization. To avoid symbol collision of using A to represent advantage in many RL literature, we use A act explicitly to represent action.
We use (B ⊥ ⊥ C) | A to represent B is conditionally independent from C, given A, or equivalently p(B|A, C) = p(B|A) or p(BC|A) = P (B|A)P (C|A). Directed Acyclic Graphs (DAG) [7] as a PGM offers an instinctive way of defining factorized joint distributions of RV by assuming the conditional independence [7] through d-separation [7]. Undirected Graph including Markov Random Fields also specifies the conditional independence with local Markov property and global Markov property [8].
Variational Inference (VI) approximates intractable posterior Evidence Lower Bound (ELBO) [6], VI assigns the values to observed and latent variables at the same time. VI is widely used in Deep Learning Community like variational resampling [9]. VI is also used in approximating the posterior on the weights distribution of neural networks for Thompson Sampling to tackle the exploration-exploitation trade off in bandit problems [10], as well as approximating on the activations distribution like Variational AutoEncoder [11]. As a contribution of this paper, we summarize the relationship of evidence log p(x), KL divergence D KL , cross entropy H q (p), entropy H(q), free energy F (φ, θ) and ELBO(φ, θ) in Equation (1) Figure 1, Reinforcement Learning (RL) involves optimizing the behavior of an agent via interaction with the environment. At time t, the agent lives on state S t , By executing an action a t according to a policy [12] π(a|S t ), the agent jumps to another state S t+1 , while receiving a reward R t . Let discount factor γ decides how much the immediate reward is favored compared to longer term return, with which one could also allow tractability in infinite horizon reinforcement learning [12], as well as reducing variance in Monte Carlo setting [13]. The goal is to maximize the accumulated rewards, G = T t=0 γ t R t which is usually termed return in RL literature.
For simplicity, we interchangeably use two conventions whenever convenient: Suppose an episode last from t = 0 : T , with T → ∞ correspond to continuous non-episodic reinforcement learning. We use another convention of t ∈ {0, · · · , ∞} by assuming when episode ends, the agent stays at a self absorbing state with a null action, while receiving null reward.
By unrolling Figure 1, we get a sequence of state, action and reward tuples {(S t , A act t , R t )} in an episode, which is coined trajectory τ [14]. Figure 2 illustrates part of a trajectory in one rollout. The state space S and action space A, which can be either discrete or continuous and multi-dimensional, are each represented with one continuous dimension in Figure 2 and plotted in an orthogonal way with different colors, while we use the thickness of the plate to represent the reward space R. 2) DAGs for (Partially Observed ) Markov Decision Process: Reinforcement Learning is a stochastic decision process, which usually comes with three folds of uncertainty. That is, under a particular stochastic policy characterized by π(a|s) = p(a|s), within a particular environment characterized by state transition probability p(s t+1 |s t , a) and reward distribution function p(r t |s t , a t ), a learning agent could observe different trajectories with different unrolling realizations. This is usually modeled as a Markov Decision Process [12], with its graphical model shown in Figure 3, where we could define a joint probability distribution over the trajectory of state , action and reward RVs. In Figure 3, we use dashed arrows connecting state and action to represent the policy, upon fixed policy π, we have the trajectory likelihood in Equation (2) p(τ ) = p(s 0 ) T t=0 p(s t+1 |s t , a t )p(r t |s t , a t )π(a t |s t ) (2) Upon observation of a state s t in Figure 3, the action at the time step in question is conditionally independent with the state and action history E t = {S 0 , A act 0 , · · · , S t−1 }, which could be denoted as (A act t ⊥ ⊥ E t ) | S t . A more realistic model,  however, is the Partially Observable Markov Decision process [15], with its DAG representation shown in Figure 4, where the agent could only observe the state partially by observing O t through a non invertible function of the next state S t+1 and the action a t , as indicated the Figure by p(o t |s t+1 , a t ), while the distributions on other edges are omitted since they are the same as in Figure 3. Under the graph specification of Figure  4, the observable O t is no longer Markov, but depends on the whole history, however, the latent state S t is still Markov. For POMDP, belief state b t is defined at time t, which is associated with a probability distribution b t (s t ) over the hidden state S t , with S b(S t ) = 1, where state S takes value in latent state space S [15]. The latent state distribution associated with

B. Value Function, Bellman Equation, Policy Iteration
Define state value function of state s ∈ S in Equation (7), where the corresponding Bellman Equation is derived in Equation (8).
where S t+i ∼ p(s t+i+1 |s t+i , a t+i ) takes value from S, A act t+i ∼ π(a|S t+i+1 ) taking value from A, and we have used the π and ε in the subscript of the expectation E operation to represent the probability distribution of the policy and the environment (including transition probability and reward probability) respectively. State action value function [12] is defined in Equation (9), where in Equation (10), its relationship to the state value function is stated.
Combining Equation (8) and Equation (9), we have Define optimal policy [12] to be Taking the optimal policy π * into the Bellman Equation in Equation (8), we have Taking the optimal policy π * into Equation (9), we have Based on Equation (14) and Equation (13), we get and For learning the optimal policy and value function, General Policy Iteration [12] can be conducted, as shown in Figure  5, where a contracting process [12] is drawn. Starting from initial policy π 0 , the corresponding value function V π0 could be estimated, which could result in improved policy π 1 by greedy maximization over actions. The contracting process is supposed to converge to the optimal policy π * . As theoretically fundamentals of learning algorithms, Dynamic programming and Monte Carlo learning serve as two extremities of complete knowledge of environment and complete model free [12], while time difference learning [12] is more ubiquitously used, like a bridge connecting the two extremities. Time difference learning is based on the Bellman update error

C. Policy Gradient and Actor Critic
Reinforcement Learning could be viewed as a functional optimization process. We could define an objective function over a policy π θ (a|s), as a functional, characterized by parameter θ, which could correspond to the neural network weights, for example.
Suppose all episodes start from an auxiliary initial state s 0 , which with probability h(s), jumps to different state s ∈ S without reward. h(s) characterizes the initial state distribution which only depends on the environment. Let η(s) represent the expected number of steps spent on state s, which can be calculated by summing up the γ discounted probability P π (s 0 → s, k + 1) of entering state s with k + 1 steps from auxiliary state s 0 , as stated in Equation (17), which can be thought of as the expectation of γ k conditional on state s. In Equation (18), the quantity is calculated by either directly starting from state s, which correspond to k = 0 in Equation (17), or entering state s from states with one step, corresponding to k + 1 ≥ 2 in Equation (17).
For an arbitrary state s ∈ S, using s and s to represent subsequent states as dummy index, the terms in square brackets in Equation (22) are simply Equation (21) with a and s replaced by a and s . Since ∇ θ V π(θ) (s ∞ ) = 0, Equation (22) could be written as Equation (23), where s k represent the state of k steps after s and P π (s → s k , k) already includes integration of intermediate state s k−1 , . . . s 1 before reaching state s k .
Let objective function with respect to policy be defined to be the value function starting from auxiliary state s 0 as in Equation (24).
The optimal policy could be obtained by gradient accent optimization, leading to the policy gradient algorithm [12], as in Equation (29).
The policy gradient could be augmented to include zero gradient baseline b(s), with respect to objective function J(π θ ) in Equation (28), as a function of state s, which does not include parameters for policy θ, since a ∇ θ π θ (a|s) = 0. To reduce variance of the gradient, the baseline is usually chosen to be the state value function estimatorV w (s) to smooth out the variation of Q(s, a) at each state, whileV w (s) is updated in a Monte Carlo way by comparing withQ π θ (S, A) = G t . The actor-critic algorithm [12]

D. Basics of Deep Reinforcement Learning
Deep Q learning [1] makes a breakthrough in using neural network as the functional approximator for value function on complicated tasks. It solves the transition correlation problem by random sampling from a replay memory. Specifically, the reinforcement learning is transformed in a supervised learning task by fitting on the target R t + γmax a Q(s t+1 , a) from the replay memory with state s t as input. However, the target can get drifted easily which leads to unstable learning. In [1], a target network is used to provide a stable target for the updating network to be learned before getting updated occasionally. Double Deep Q learning [16], however, solves the problem by having two Q network and update the parameters in a alternating way. We review some state of art deep reinforcement learning algorithms from different aspects: 1) Off Policy methods: Except for Deep Q Learning [1] mentioned above, DDPG [17] extends Deterministic Policy Gradient (DPG) [18] with deep neural network functional approximator, which is an actor-critic algorithm and works well in continuous action spaces.
2) On Policy methods: A3C [19] stands out in the asynchronous methods in deep learning [19] which can be run in parallel on a single multi-core CPU. Trust Region Policy Optimization [2] and Proximal Policy Optimization [20] assimilates the natural policy gradient, which use a local approximation to the expected return. The local approximation could serve as a lower bound for the expected return, which can be optimized safely subject to the KL divergence constraint between two subsequent policies, while in practice, the constraint is relaxed to be a regularization.
3) Goal based Reinforcement Learning: In robot manipulation tasks, the goal could be represented with state in some cases [14]. Universal Value Function Approximator (UVFA) [21] incorporate the goal into the deep neural network, which let the neural network functional approximator also generalize to goal changes in tasks, similar to Recommendation System [22]. Work of this direction include [23], [14], for example. 4) Replay Memory Manipulation based Method: Replay memory is a critical component in Deep Reinforcement Learning, which solves the problem of correlated transition in one episode. Beyond the uniform sampling of replay memory in Deep Q Network [1], Prioritized Experience Replay [24] improves the performance by giving priority to those transitions with bigger TD error, while Hindsight Experience Replay (HER) [23] manipulate the replay memory with changing goals to transition so as to change reward to promote exploration. Maximum entropy regularized multi goal reinforcement learning [14] gives priority to those rarely occurred trajectory in sampling, which has been shown to improve over HER [14]. 5) Surrogate policy optimization: Like surrogate model used in Bayesian Optimization [25], lower bound surrogate is also used in Reinforcement Learning. Trust Region Policy Optimization (TRPO) [2] is built on the identity from [26] in Equation (30), where η π new (s) means the state visitation frequency under policy π new and advantage A π old (a t , s t ) = J(π new ) = J(π old ) + s η π new (s) a π new (a|s)A π old (a, s) Based on Policy Advantage [26] A π old ,η old (π new ) = s η π old (s) a π new (a|s)A π old (a, s), a local approximation L π old (π new ) to Equation (30) can be defined in Equation (31), based on which, a surrogate function M (π new , π old ) is defined in Equation (32) that minorizes J(π new ) at π old , where D max KL (π old , π new ) = max s D KL (π old (a|s), π new (a|s)) is the maximum KL divergence, so MM [2] algorithm could be used to improve the policy, leading to the trust region method [2].   Despite the success of deep reinforcement learning in many talks, the field still faces some critical challenges. One problem is exploration with sparse reward. In complicated real environment, an agent has to explore for a long trajectory before it can get any reward as feedback. Due to lack of enough rewards, traditional Reinforcement Learning methods M (π new , π old ) =L π old (π new ) − 4max a,s |A π old (s, a)|γ performs poorly, which lead to a lot of recent contributions in the exploration methods. Another challenge is how to represent policy in extremely large state and action spaces. Furthermore, sometimes it is beneficial to have multimodal behavior for a agent when some trajectory might be equivalent to other trajectories and we want to learn all of them. In this section, we give detailed explanation on how graphical model and variational inference could be used to model and optimize the reinforcement learning process under these challenges and form a taxonomy of these methods.
Together with the deep reinforcement learning methods mentioned in section II-D, we make a comparison of them in Table I.

A. Policy and value function with undirected graphs
We first discuss the application of undirected graphs in deep reinforcement learning, which models joint distribution of variables with cliques [7]. In [27], the authors use Restricted Boltzmann Machine (RBM) [8], which has nice property of tractable factorized posterior distribution over the latent variables conditioned on observed variables. To deal with MDPs of large state and action spaces, they model the stateaction value function with the negative free energy of a Restricted Boltzmann Machine. Specifically, the visible states of the Restricted Boltzmann Machine [27] consists of both state s and action a binary variables, as shown in Figure 6, where the hidden nodes consist of L binary variables, while state variables s i are dark colored to represent it can be observed and actions a j are light colored to represent it need to be sampled. Together with the auxiliary hidden variables, the undirected graph defines a joint probability distribution over state and action pairs, which defines a stochastic policy network that could sample actions out for on policy learning. Since it is pretty easy to calculate the derivative of the free energy F (s, a) with respect to the coefficient w k,j of the network, one could use temporal difference learning to update the coefficients in the network. Thanks to properties of Boltzmann Machine, the conditional distribution of action over state p(a|s), which could be used as a policy, is still Boltzmann distributed as in Equation (33), governed by the free energy F (a, s), where Z(s) is the partition function [7] and the negative free energy to approximate the state action value function Q(s, a). By adjusting the temperature T , one could also change between different exploration strength.
A few steps of MCMC sampling [7] could be used to sample actions, as an approximation of the policy, which can be fed into a time difference learning method like SARSA [12], to  update the state value function Q(s, a)'s estimation. Such an on-policy process has been shown to be empirically effective in the large state actions spaces [27].
B. Variational Inference on "optimal" Policies 1) policy as "optimal" posterior: The Boltzmann Machine defined Product of Expert Model in [27] works well for large state and action spaces, but are limited to discrete specifically binary state and action variables. For continuous state and action spaces, in [28], the author proposed deep energy based models with Directed Acyclic Graphs (DAG) [7], which we re-organize in a different form in Figure 7 with annotations added. The difference with respect to Figure 3 is that, in Figure  7, the reward is not explicit expressed in the directed graphical model. Instead, an auxilliary binary Observable O is used to define whether the corresponding action at the current step is optimal or not. The conditional probability of the action being optimal is p(O t = 1|s t , a t ) = exp(r(s t , a t )), which connects conditional optimality with the amount of award received by encouraging the agent to take highly rewarded actions in an exponential manner. Note that the reward here must be negative to ensure the validity of probability, which does not hurt generality since reward range can be translated [13].
The Graphical Model in Figure 7 in total defines the trajectory likelihood or the evidence in Equation (34): By doing so, the author is forcing a form of functional expression on top of the conditional independence structure of the graph by assigning a likelihood. In this way, calculating the optimal policy of actions distributions becomes an inference problem of calculating the posterior p(a t |s t , O t:T = 1), which reads as, conditional on optimality from current time step until end of episode, and the current current state to be s t , the distribution of action a t , and this posterior corresponds to the optimal policy. Observing the d-separation from Figure 7, in [13]. Similar to the forward-backward message passing algorithm [7] in Hidden Markov Models [7], the posterior p(a t |s t , O t:T = 1) could also be calculated by passing messages. We offer a detailed derivation of the decomposition of the posterior p(a t |s t , O t:T = 1) in Equation (35), which is not available in [13]. In Equation (35), we define message β(a t , s t ) = p(O t:T = 1|a t , s t )p(a t |s t ) and message β(s t ) = a t β(a t , s t )d{a t }. If we consider p(a t |s t ) as a prior with a trivial form of uniform distribution [13], the only policy related term becomes p(O t:T = 1|a t , s t ).
In contrast to HMM, here, only the backward messages are relevant. Additionally, the backward message β(a t , s t ) here is not a probability distribution as in HMM, instead, is just a probability. In Figure 7, the backward message β(a t , s t ) could be decomposed recursively. Since in [13] the author only give the conclusion without derivation, we give a detailed derivaion of this recursion in Equation (36). The recursion in Equation (36) start from the last time point T of an episode.

3) Connection between Message Passing and Bellman equation: If we define Q function in Equation (37) and V function in Equation (38)
then the corresponding policy could be written as Equation (39).
π(a t |s t ) = p(a t |s t , O t:T = 1) = exp(Q(s t , a t ) − V (s t )) (39) Taking the logrithm of Equation (36), we get Equation (40) which reduces to the risk seeking backup in Equation (41) as mentioned in [13]: The mathematical insight here is that if we define the messages passed on the Directed Acyclic Graph in Figure 7, then message passing correspond to a peculiar version Bellman Equation like backup, which lead to an unwanted risk seeking behavior [13]: when compared to Equation (10), the Q function here is taking a softmax instead of expectation over the next state. 4) Variational approximation to "optimal" policy: Since the exact inference lead to unexpected behavior, approximate inference could be used. The optimization of the policy could be considered as a variational inference problem, and we use the variational policy of the action posterior distribution q(a t |s t ), which could be represented by a neural network, to compose the proposal variational likelihood of the trajectory as in Equation (42): where the initial state distribution p(s 1 ) and the environmental dynamics of state transmission is kept log(β(s t , a t )) = log β(s t+1 )p(s t+1 |s t , a t )p(O t = 1|s t , a t )ds t+1 = log exp[r(s t , a t ) + V (s t+1 )]p(s t+1 |s t , a t )ds t+1 = r(s t , a t ) + log exp(V (s t+1 ))p(s t+1 |s t , a t )ds t+1 (40) q(τ ) = p(s 1 ) t [p(s t+1 |s t , a t )q(a t |s t )] intact. Using the proposal trajectory as a pivot, we could derive the Evidence Lower Bound (ELBO) of the optimal trajectory as in Equation (43), which correspond to an interesting objective function of reward plus entropy return, as in Equation (45).

5) Examples:
In [28], the state action value function is defined in Equation (46). and a soft version of Bellman update similar to Q Learning [12] is carried out, which lead to policy improvement with respect to the corresponding functional objective in Equation (47). Setting policy as Equation (39) lead to policy improvement. We offer a detailed proof for a key formula in Equation (48), which is stated in Equation (19) of [28] without proof. In Equation (48), we use π(·|s) to implicitly represent π(a|s) to avoid symbol aliasing whenever necessary. For the rest of the proof, we invite the reader to read the appendix of [28]. Algorithms of the this kind of maximum entropy family also include Soft Actor Critic [29].

C. Variational Inference on the Environment
Another direction of using Variational Inference in Reinforcement Learning is to learn an environmental model, either on the dynamics or the latent state space posterior.
1) Variational inference on transition model: In Variational Information Maximizing Exploration (VIME) [4], where dynamic model p θ (s t+1 |s t , a t ) for the agent's interaction with the environment is modeled using Bayesian Neural Network [10]. The R.V. for θ is denoted by Θ, and is treated in a Bayesian way by modeling the weight θ uncertainty of a neural network. We represent this model with the graphical model in Figure 8, which is not given in [4]. The belief uncertainty about the environment is modeled as entropy of the posterior distribution of the neural network weights H(Θ|ξ t ) based on trajectory observations ξ t = {s 1:t , a 1:t−1 }. The method encourages taking exploratory actions by alleviating the average information gain of the agent's belief about the environment after observing a new state s t+1 , which is E p(st+1|ξt,at) D KL (p(θ|ξ t+1 )||p(θ|ξ t )), and this is equivalent to the entropy minus conditional entropy H(Θ|ξ t , a t ) − H(Θ|ξ t , a t , s t+1 ) = H(Θ|ξ t , a t ) − H(Θ|ξ t+1 ). With the help of Equation (49), as derived following the definition of conditional mutual information, we derive in Equation (50) that the conditional entropy difference is actually the average information gain, which is equal to the conditional mutual information I(Θ, S t+1 |ξ t , a t ) between environmental parameter Θ and the new state S t+1 . Such a derivation is not given in [4]. Based on Equation (50), an intrinsic reward can be augmented from the environmental reward function, thus the method could be incorporated with any existing reinforcement learning algorithms for exploration, TRPO [2], for example. Upon additional observation of action a t and state s t+1 pair on top of trajectory history ξ t , the posterior on the distribution of the environmental parameter θ, p(θ|ξ t ), could be updated to be p(θ|ξ t+1 ) in a Bayesian way as derived in Equation (51), which is first proposed in [30]. In Equation (51), the denominator can be written as Equation (52), so that the dynamics of the environment modeled by neural network weights θ, p(s t+1 |θ, a t , ξ t ), could be used. The last step of Equation (52) makes use of p(θ|ξ t , a t ) = p(θ|ξ t ).
Since the integral in Equation (52) is not tractable, variational treatment over the neural network weights posterior distribution p(θ|ξ t ) is used, characterized by variational parameter φ, as shown in the dotted line in Figure 8. The variational posterior about the model parameter θ, updated at each step, could than be used to calculate the intrinsic reward in Equation (50).
Additionally, we characterize Equation (53) with the probabilistic graphical model in Figure 9 which does not exist in [5]. Compared to Figure 7, here the latent state S is in discrete space instead of high dimension, and the observation is a high dimensional image instead of binary variable to indicate optimal action. By assuming a factorized form of the variational posterior in Equation (54), The author assume the episode length to be T , and default frame prior observation to be blank frames. The Evidence Lower Bound (ELBO) of the observed trajectory of Equation (53) could be easily represented by a Varitional AutoEncoder [31] like architecture, where the encoder q φ , together with the reparametrization trick [31], maps the observed state O into parameters for the Con-crete distribution [32], so backprobagation could be used on deterministic variables to update the weight of the network based on the ELBO, which is decomposed into different parts of the reconstruction losses of the variational autoencoder like architecture. Like VIME [4], VaSt could be combined with other reinforcement learning algorithms. Here prioritized sweeping [12] is carried out on the Heviside activation of the encoder output directly, by counting the transition frequency, instead of waiting for the slowly learned environmental transition model p θ T (s t |s t−1 , a t−1 ) in Equation (53). A potential problem of doing so is aliasing between latent state s and observed state o. To alleviate this problem, in [5], the author actively relabel the transition history in the replay memory once found the observable has been assigned a different latent discrete state.

IV. CONCLUSION
As a tutorial survey, we recap Reinforcement Learning with Probabilistic Graphical Models, summarizes recent advances of Deep Reinforcement Learning and offer a taxonomy of Probabilistic Graphical Model and Variational Inference in DRL with detailed derivations which are not included in the original contributions.