ANALYTICALLY TRACTABLE BAYESIAN DEEP Q-LEARNING
Year: 2021

Abstract:
Reinforcement learning (RL) has gained increasing interest since the demonstration it was able to reach human performance on video game benchmarks using deep Q-learning (DQN). The current consensus of DQN for training neural networks (NNs) on such complex environments is to rely on gradient-descent optimization (GD). This consensus ignores the uncertainty of the NN’s parameters which is a key aspect for the selection of an optimal action given a state. Although alternative Bayesian deep learning methods exist, most of them still rely on GD and numerical approximations, and they typically do not scale on complex benchmarks such as the Atari game environment. In this paper, we present how we can adapt the temporal difference Q-learning framework to make it compatible with the tractable approximate Gaussian inference (TAGI) which allows estimating the posterior distribution of NN’s parameters using a closed-form analytical method. Throughout the experiments with onand off-policy reinforcement learning approaches, we demonstrate that TAGI can reach a performance comparable to backpropagationtrained networks while using only half the number of hyperparameters, and without relying on GD or numerical approximations.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has gained increasing interest since the demonstration it was able to reach human performance on video game benchmarks using deep Q-learning (DQN) (Mnih et al., 2015; Van Hasselt et al., 2016). Deep RL methods typically require an explicit definition of an exploration-exploitation function in order to compromise between using the current policy and exploring the potential of new actions. Such an issue can be mitigated by opting for a Bayesian approach where we estimate the uncertainty of the neural network’s parameters using Bayes’ theorem, and select the optimal action given a state according to the parameter uncertainty using Thompson sampling technique (Strens, 2000). Bayesian deep learning (BDL) methods based on variational inference (Kingma et al., 2015; Hernández-Lobato & Adams, 2015; Blundell et al., 2015; Louizos & Welling, 2016; Osawa et al., 2019; Wu et al., 2019), Monte-Carlo dropout (Gal & Ghahramani, 2016), or Hamiltonian Monte-Carlo sampling (Neal, 1995) have shown to perform well on regression and classification benchmarks, despite being generally computationally more demanding than their deterministic counterparts. Note that none of these approaches allow performing the analytical inference for the weights and biases defining the neural network. Goulet et al. (2021) recently proposed the tractable approximate Gaussian inference (TAGI) method that allows estimating the posterior of the neural network’s parameters using a closed-form analytical method. More specifically, TAGI leverages Gaussian conditional equations to analytically infer this posterior without the need of numerical approximations (i.e., sampling techniques or Monte Carlo integration) or optimization on which existing BDL methods rely. In addition, TAGI is able to maintain the same computational complexity as deterministic neural networks based on the gradient backpropagation. For convolutional architectures applied on classification benchmarks, this approach was shown to exceed the performance of other Bayesian and deterministic approaches based on gradient backpropagation, and to do so while requiring a smaller number of training epochs (Nguyen & Goulet, 2021).
In this paper, we propose a new perspective on probabilistic inference for Bayesian deep reinforcement learning which, up to now has been relying on gradient-based methods. More specifically, we present how can we adapt the temporal difference Q-learning framework (Sutton, 1988; Watkins & Dayan,
1992) to make it compatible with TAGI. Section 2 first reviews the theory behind TAGI and the expected value formulation through the Bellman’s Equation. Then, we present how the actionvalue function can be learned using TAGI. Section 3 presents the related work associated with Bayesian reinforcement learning, and Section 4 compares the performance of the TAGI-DQN with the deterministic DQN on on- and off-policy RL approaches.

heading: 2 TAGI-DQN FORMULATION
text: This section presents how to adapt the DQN frameworks in order to make them compatible with analytical inference. First, Section 2.1 reviews the fundamental theory behind TAGI, and Section 2.1 reviews the concept of long-term expected value through the Bellman’s equation (Sutton & Barto, 2018). Then, Section 2.3 presents how to make the Q-learning formulation (Watkins & Dayan, 1992) compatible with TAGI.

heading: 2.1 TRACTABLE APPROXIMATE GAUSSIAN INFERENCE
text: Bayesian deep learning aims to estimate the posterior of neural network’s parameters θ conditional on a given training dataset D = {(xi,yi) ,∀i ∈ 1 : D} using Bayes’ theorem so that
f(θ|D) = f(θ)f(D|θ) f(D) , (1)
where f(θ) is the prior Probability Density Function (PDF) of parameters, f(D|θ) is the likelihood and f(D) is the marginal likelihood or evidence. Until recently, the posterior f(θ|D) in Equation 1 has been considered to be intractable (Goodfellow et al., 2016; Goan & Fookes, 2020). TAGI has addressed this intractability issue by leveraging the Gaussian conditional equations; For a random vector of parameter θ and observations Y for which the joint PDF satisfies
f ( θ y ) = N ([ θ y ] ; [ µθ µY ] , [ Σθ Σ ᵀ Yθ ΣYθ ΣY ]) , (2)
the Gaussian conditional equation describing the PDF of θ conditional on y is defined following
f(θ|y) = N (θ;µθ|y,Σθ|y) µθ|y = µθ + Σ ᵀ YθΣ −1 Y (y − µY )
Σθ|y = Σθ −ΣᵀYθΣ−1Y ΣYθ. (3)
In its simple form, the intractable computational requirements for directly applying Equation 3 limits it to trivial neural networks. In order to overcome this challenge, TAGI leverages the inherent conditional independence structure of hidden layers Z(j−1) ⊥ Z(j+1)|z(j) under the assumptions that parameters θ are independent between layers. This conditional independence structure allows breaking down the computations for Equation 3 into a layer-wise two-step procedure; forward uncertainty propagation and backward update.
The first forward uncertainty propagation step is intended to build the joint prior between the hidden states of a layer j, Z(j), and the parameters θ(j) directly connecting into it. This operation is made by propagating the uncertainty from the parameters and the input layer through the neural network. In order to maintain the analytical tractability of the forward step, we must address two challenges: The first challenge is related to the product of the weights W and activation units A involved in the calculation of the hidden states Z so that
Z (j+1) i = A∑ k=1 W (j) i,k A (j) k +B (j) i , (4)
where B is the bias parameter, (j) refers to the jth layer, i refers to a node in the current layer, k refers to a node from the previous layer, and A is the number of hidden units from the previous layer. The second challenge is to propagate uncertainty through the non-linearity when activating hidden states with an activation function φ(.),
A (j+1) i = φ
( Z
(j+1) i
) . (5)
In order to tackle these issues, TAGI made the following assumptions
A1. The prior for the parameters and variables in the input layer are Gaussians. A2. The product of a weight and an activation unit in Equation 4 is approximated by a Gaussian
random variable, WA ≈ N (µWA, σ2WA), whose moments are computed analytically using Gaussian multiplicative approximation (GMA).
A3. The activation function φ(.) in Equation 5 is locally linearized using a first-order Taylor expansion evaluated at the expected value of the hidden unit being activated.
Note that the linearization procedure in the assumption A3 may seems to be a crude approximation, yet it has been shown to match or exceeds the state-of-the-art performance on fully-connected neural networks (FNN) (Goulet et al., 2021), as well as convolutional neural networks (CNN) and generative adversarial networks (Nguyen & Goulet, 2021). In order to maintain a linear computational complexity with respect to the number of weights for the forward steps, TAGI relies on the following assumptions
A4. The covariance for all parameters in the network and for all the hidden units within a same layer are diagonal.
A5. The hidden states on a given layer are independent from the parameters connecting into the subsequent layer, i.e., Z(j) ⊥ θ(j).
A6. The hidden states at layer j + 1 depend only on the hidden states and parameters directly connecting into it.
The empirical validity of those assumptions as well as the GMA formulations are provided by Goulet et al. (2021).
The second backward update-step consists in performing layer-wise recursive Bayesian inference going from hidden-layer to hidden-layer, and from hidden-layer to the parameters connecting into it (see Figure 1). The assumptions A1-A6 allow performing analytical inference while still maintaining a linear computational complexity with respect to the number of weight parameters in the network where only the posterior of hidden states for the output layer are computed using Equation 3. For the remaining layers, those quantities are obtained using the Rauch-Tung-Striebel recursive procedure that was developed in the context of state-space models (Rauch et al., 1965). For simplicity, we define the short-hand notation {θ+,Z+} ≡ {θ(j+1),Z(j+1)} and {θ,Z} ≡ {θ(j),Z(j)} so that the posterior for the parameters and hidden states are computed following
f(Z|y) = N (z;µZ|y,ΣZ|y) µZ|y = µZ + JZ ( µZ+|y − µZ+ ) ΣZ|y = ΣZ + JZ ( ΣZ+|y −ΣZ+ ) JᵀZ
JZ = ΣZZ+Σ −1 Z+ ,
(6)
f(θ|y) = N (θ;µθ|y,Σθ|y) µθ|y = µθ + Jθ ( µZ+|y − µZ+ ) Σθ|y = Σθ + Jθ ( ΣZ+|y −ΣZ+ ) Jᵀθ
Jθ = ΣθZ+Σ −1 Z+ .
(7)
Figure 1 presents a directed acyclic graph (DAG) describing the interconnectivity in such a neural network.
TAGI allows inferring the diagonal posterior knowledge for weights and bias parameters, either using one observation at a time, or using mini-batches of data. As we will show in the next sections, this online learning capacity is best suited for RL problems where we experience episodes sequentially and where we need to define a tradeoff between exploration and exploitation, as a function of our knowledge of the expected value associated with being in a state and taking an action.

heading: 2.2 EXPECTED VALUE AND BELLMAN’S EQUATION
text: We define r(s, a, s′) as the reward for being in a state s ∈ RS, taking an action a ∈ A = {a1, a2, · · · aA}, and ending in a state s′ ∈ RS. For simplicity, we use the short-form notation
for the reward r(s, a, s′) ≡ r(s) in order to define the value as the infinite sum of discounted rewards
v(s) = ∞∑ k=0 γkr(st+k). (8)
As we do not know what will be the future states st+k for k > 0, we need to consider them as random variables (St+k), so that the value V (st) becomes a random variable as well,
V (st) = r(st) + ∞∑ k=1 γkr(St+k). (9)
Rational decisions regarding which action to take among the set A is based the maximization of the expected value as defined by the action-value function
q(st, at) = µV ≡ E[V (st, at, π)] = r(st) + E [ ∞∑ k=1 γkr(St+k) ] , (10)
where it is assumed that at each time t, the agent takes the action defined in the policy π. In the case of episode-based learning where the agent interacts with the environment, we assume we know the tuple of states st and st+1, so that we can redefine the value as
V (st, at) = r(st) + γ ( r(st+1) +
∞∑ k=1 γkr(St+1+k) ) = r(st) + γV (st+1, at+1).
(11)
Assuming that the value V ∼ N (v;µV , σ2V ) in Equations 9 and 11 is described by Gaussian random variables, we can reparameterize these equations as the sum of the expected value q(s, a) and a zero-mean Gaussian random variable E ∼ N ( ; 0, 1), so that
V (s, a) = q(s, a) + σV E , (12) where the variance σ2V and E are assumed here to be independent of s and a. Although in a more general framework this assumption could be relaxed, such an heteroscedastic variance term is outside from the scope of this paper. Using this reparameterization, we can write Equation 11 as the discounted difference between the expected values of two subsequent states
q(st, at) = r(st) + γq(st+1, at+1)− σVtEt + γσVt+1Et+1 = r(st) + γq(st+1, at+1) + σV E .
(13)
Note that in Equation 13, σVt and γσVt+1 can be combined in a single standard deviation parameters σV with the assumption that Ei ⊥ Ej ,∀i 6= j. In the case where at a time t, we want to update the Q-values encoded in the neural net only after observing n-step returns (Mnih et al., 2016), we can reformulate the observation equation so that
q(st, at) = n−t−1∑ i=0 γir(st+i) + γ n−tq(sn, an) + σV Et,∀t = {1, 2, · · · , n− 1}. (14)
Note that in the application of Equation 14, we employ the simplifying assumption that Et ⊥ Et+i,∀i 6= 0, as Equation 13 already makes simplifying assumptions for the independence of σ2V and E . Note that in a more general framework, this assumption could be relaxed. An example of n-step returns is presented in the the algorithm displayed in §1 from Appendix A.
The following subsections will present, for the case of categorical actions, how to model the deterministic action-value function q(s, a) using a neural network.

heading: 2.3 TAGI DEEP Q-LEARNING FOR CATEGORICAL ACTIONS
text: Suppose we represent the environment’s state at a time t and t+ 1 by {s, s′}, and the expected value for each of the A possible actions a ∈ A by the vector q ∈ RA. In that context, the role of the neural network is to model the relationships between {s, a} and q. Figure 2a presents a directed acyclic graph (DAG) describing the interconnectivity in such a neural network, where red nodes denote state variables, green nodes are vectors of hidden units z, the blue box is a compact representation for the structure of a convolutional neural network, and where gray arrows represent the weights and bias θ connecting the different hidden layers. Note that unlike other gray arrows, the magenta ones in (b) are not directed arcs representing dependencies, but they simply outline the flow of information that takes place during the inference step. For simplification purposes, the convolutional operations are omitted and all regrouped under the CNN box. In order to learn the parameters θ of such a network,
s CNN z(1) z(2) qθ(c0) θ(0) θ(1) θ(q)
(a) Neural network DAG for modelling the action-value function q
we need to expand the graph from Figure 2a to include the reward r, the error term σV , and q′, the q-values of the time step t + 1. This configuration is presented in Figure 2b where the nodes that have been doubled represent the states s and s′ which are both evaluated in a network sharing the same parameters. Note that the value of q′ is computed using the same network presented in Figure 2a in which this network acts as a predictor taking input as s′. When applying Equation 13, q-values corresponding to a specific action can be selected using a vector hi ∈ {0, 1}A having a single non-zero value for the i-th component identifying which action was taken at a time t so that
qi = [q]i = h ᵀ i q. (15)
In the context TAGI-DQN, we employ Thompson sampling (Strens, 2000) for the selection of an action given a state. More specifically, the vector h′i ∈ {0, 1}A is defined such that the i-th non-zero value corresponds to the index of the maximal value among q′, a vector of realizations from the neural network’s posterior predictive output Q ∼ N (q′;µQ|D,ΣQ|D). Because of the Gaussian assumptions in TAGI, this posterior predictive is readily available from the forward uncertainty propagation step, as outlined in §2.1.
The red arrows in Figure 2b outline the flow of information during the inference procedure. The first step consists in inferring q using the relationships defined in either Equation 13 or 14. As this is a linear equation involving Gaussian random variables, the inference is analytically tractable. From there, one can follow the same layer-wise recursive procedure presented in §2.1 in order to learn
the weights and biases in θ. With the exclusion of the standard hyperparameters related to network architecture, batch size, buffer size or the discount factor, this TAGI-DQN framework only involves a single hyperparameter, σV , the standard deviation for the value function. Note that when using CNNs with TAGI, Nguyen & Goulet (2021) recommended using a decay function for the standard deviation of the observation noise so that after seing e batches of n-steps,
σeV = max(σ min V , η · σV )e−1, (16)
because it allows putting more weight on the prior rather than on the likelihood during the inference step at the early stage. This effect then diminishes with time. The model in Equation 16 has three hyperparameters, the minimal noise parameter σminV , the decay factor η and the initial noise parameter σV . As it was shown by Nguyen & Goulet (2021) for CNNs and how we show in §4 for RL problems, TAGI’s performance is robust towards the selection of these hyperparameters.
A comparison of implementation between TAGI and backpropagation on deep Q-network with experience replay (Mnih et al., 2015) is shown in Figure 3. A practical implementation of n-step TAGI deep Q-learning is presented in Algorithm 1 from Appendix A
Algorithm 1: TAGI-DQN with Experience Replay 1 Initialize replay memoryR to capacity N ; ΣV ; 2 Initialize parameters θ; 3 Discount factor γ; 4 for episode = 1 : E do 5 Reset environment s0;

heading: 6 for t = 1 : T do
text: 7 q(st, a) : Q(st, a) ∼ N (µQθ (st, a),Σ Q θ (st, a));
8 at = arg max a∈A q(st, a);
9 st+1, rt = enviroment(at); 10 Store {st, at, rt, st+1} inR; 11 Sample random batch of {sj , aj , rj , sj+1}; 12 q(sj+1, a ′) : Q(sj+1, a ′) ∼ N (µQθ (sj+1, a′),Σ Q θ (sj+1, a
′)); 13 a′j+1 = arg max
a′∈A q(sj+1, a
′);
14 µYj = rj + γµ Q θ (sj+1, a ′ j+1);
15 ΣYj = γ 2ΣQθ (sj+1, a ′ j+1) + ΣV ; 16 Update θ using TAGI on f(θ|y) (Equation 7);
Algorithm 2: DQN with Experience Replay 1 Initialize replay memoryR to capacity N ; 2 Initialize parameters θ; 3 Discount factor γ; 4 Define (epsilon-greedy function); 5 for episode = 1 : E do 6 Reset environment s0; 7 for t = 1 : T do 8 u : U ∼ U(0, 1);
9 at =
{ randi(A) u < ;
arg max a∈A
Qθ(st, a) u ≥ ;
10 st+1, rt = enviroment(at); 11 Store {st, at, rt, st+1} inR; 12 Sample random batch of {sj , aj , rj , sj+1}; 13 yj = rj + γ max
a′∈A Qθ(sj+1, a
′);
14 Update θ using gradient descent on
15 L = 0.5 [yj −Qθ(sj , aj)]2;
Figure 3: Comparison of TAGI with backpropagation on deep Q-network with experience replay. L: loss function; U : uniform distribution; randi: uniformly distributed pseudorandom integers.

heading: 3 RELATED WORKS
text: Over the last decades, several approximate methods have been proposed in order to allow for Bayesian neural networks (Neal, 1995; Kingma et al., 2015; Hernández-Lobato & Adams, 2015; Blundell et al., 2015; Louizos & Welling, 2016; Osawa et al., 2019; Wu et al., 2019; Gal & Ghahramani, 2016) with various degree of approximations. Although some these methods have shown to be capable of tackling classification tasks on datasets such ImageNet (Osawa et al., 2019), none of them have been applied on large-scale RL benchmark problems such as the Atari games environement. The key idea behind using Bayesian methods for reinforcement learning is to consider the uncertainty associated with Q-functions in order to identify a tradeoff between exploring the performance of possible actions and exploiting the current optimal policy (Sutton & Barto, 2018). This typically takes the form of performing Thompson sampling (Strens, 2000) rather than relying on heuristics such as -greedy.
For instance, MC dropout (Gal & Ghahramani, 2016) was introduced has a method intrinsically suited for reinforcement learning. Nevertheless, five years after its inception, the approach has not yet been reliably scaled to more advanced benchmarks such as the Atari game environment. The
same applies to Bayes-by-backprop (Blundell et al., 2015) which was recently applied to simple RL problems (Lipton et al., 2018), and which has not yet been applied to more challenging environments requiring convolutional networks. On the other hand, Bayesian neural networks relying on sampling methods such as Hamiltonian Monte-Carlo (Neal, 1995) are typically computationally demanding to be scaled to RL problems involving such a complex environment.
Although mainstream methods related to Bayesian neural networks have seldom been applied to complex RL problems, several research teams have worked on alternative approaches in order to allow performing Thompson sampling. For instance, Azizzadenesheli et al. (2018) have employed a deep Q-network where the output layer relies on Bayesian linear regression. This approach was shown to be outperforming its deterministic counterparts on Atari games. Another approach by Osband et al. (2016) employs bootstrapped deep Q-networks with multiple network heads in order to represent the uncertainty in the Q-functions. This approach was also shown to scale to Atari games while presenting an improved performance in comparison with deterministic deep Q-networks. Finally, Wang & Zhou (2020) have tackled the same problem, but this time by modelling the variability in the Q-functions through a latent space learned using variational inference. Despite its good performance on the benchmarks tested, it did not allowed to be scaled to the Atari game environment.
The TAGI deep Q-network presented in this paper is the first demonstration that an analytically tractable inference approach for Bayesian neural networks can be scaled to a problem as challenging as the Atari game environment.

heading: 4 BENCHMARKS
text: This section compares the performance of TAGI with backpropagation-based standard implementations on off- and on-policy deep RL. For the off-policy RL, both TAGI-based and backpropagationbased RL approaches are applied to deep Q-learning with experience replay (see Algorithm 1 & 2) for the lunar lander and cart-pole environments. For the on-policy RL, TAGI is applied to the n-step Q-learning algorithm (Mnih et al., 2016) and is compared with its backpropagation-based counterpart. For this purpose, we perform the comparison on five Atari games including Beamrider, Breakout, Pong, Qbert, and Space Invaders. Note that these five games are commonly selected for tuning hyperparameters for the entire Atari games (Mnih et al., 2016; 2013) because they represent the features sharing with the remaining Atari games. All benchmark environments are taken from the OpenAI Gym (Brockman et al., 2016).

heading: 4.1 EXPERIMENTAL SETUP
text: In the first experiments with off-policy RL, we use a fully-connected multilayer perceptron (MLP) with two hidden layers of 256 units for the lunar lander environment, and with one hidden layer of 64 units for the cart pole environment. In these experiments, there is no need for input processing nor for reward normalization. Note that unlike for the deterministic deep Q-network with experience replay, TAGI does not separate the Q-network with the target network that is used for ensuring the stability during training and allows eliminating the hyperparameter related to the target update frequency. For the deep Q-network trained with backpropagation, we employ the pre-tuned implementation of OpenAI baselines (Dhariwal et al., 2017) with all hyperparameters set to the default values.
For the Atari experiments with on-policy RL, we use the same input processing and model architecture as Mnih et al. (2016). More specifically, the Q-network uses two convolutional layers (16-32 filters) and a full-connected MLP of 256 units. The n-step Q-learning only uses a single network to represent the value function for each action, and relies on a single learning agent in this experiment. The reason behind this choice is that TAGI current main library is only available on Matlab which does not support running a Python multiprocessing module such as the OpenAI gym. In the context of TAGI, we use an horizon of 128 steps. As recommended by Andrychowicz et al. (2021) and following practical implementation details (Pytorch, 2019; 2020), each return in n-step Q-learning algorithm is normalized by subtracting the average return from the current n-steps and then dividing by the empirical standard deviation from the set of n returns.
The standard deviation for the value function, (σV ), is initialized at 2. σV is decayed each 128 steps with a factor η = 0.9999. The minimal standard deviation for the value function σminV = 0.3. These hyperparameters values were not grid-searched but simply adapted to the scale of the problems
and are kept constant for both experiments. The complete details of the network architecture and hyperparameters are provided in Appendix B and C.

heading: 4.2 RESULTS
text: For the first set of experiments using off-policy RL, Figure 4 presents the average reward over 100 episodes for three runs for the lunar lander and cart pole environment. The TAGI-based deep Q-learning with experience replay shows a faster and more stable learning than the one relying on backpropagation.
Table 1 shows that the average reward over the last 100 episodes obtained using TAGI are greater than the one obtained using backpropagation. Figure 5 compares the average reward over 100 episodes
for three runs obtained for TAGI, with the results from Mnih et al. (2016) for the second set of experiments on Atari games. Note that all results presented were obtained for a single agent, and that the results for the backpropagation-trained networks are only reported at the end of each epoch.
Results show that TAGI outperforms the results from the original n-step Q-learning algorithm trained with backpropagation (Mnih et al., 2016) on Breakout, Pong, and Qbert, while underperforming on Beam Rider and Space Invaders. The average training time of TAGI for an Atari game is approximately 13 hours on GPU calculations benchmarked on a 4-core-intel desktop of 32 GB of RAM with a NVIDIA GTX 1080 Ti GPU. The training speed of TAGI for the experiment of the offpolicy deep RL is approximately three times slower on CPU calculations than the backpropagationtrained counterpart. The reason behind this slower training time is because of its intrinsically different inference engine making TAGI’s implementation incompatible with existing libraries such as TensorFlow or Pytorch. TAGI’s library development is still ongoing and it is not yet fully optimized for computational efficiency. Overall, these results for on- and off policy RL approaches confirm that TAGI can be applied to large scale problems such as deep Q-learning.

heading: 5 DISCUSSION
text: Although the performance of TAGI does not systematically outperform its backpropagation-based counterpart, it requires fewer hyperparameters (see Appendix C). This advantage is one of the key
aspects for improving the generalization and reducing the computational cost of the hyperparameter tuning process which are the key challenges in current state of deep RL (Irpan, 2018; Henderson et al., 2018). For instance, in this paper, the TAGI’s hyperparameters relating to the standard deviation of value function (σV ) are kept constant across all experiments. Moreover, since these hyperparameters were not subject to grid-search in order to optimize the performance, the results obtained here are representative of what a user should obtain by simply adapting the hyperparameters to fit the specificities and scale of the environment at hand.
More advanced RL approaches such as advanced actor critic (A2C) (Mnih et al., 2016) and proximal policy optimization (PPO) (Schulman et al., 2017) employ two-networks architectures in which one network is used to approximate a value function and other is employed to encode the policy. The current TAGI-RL framework is not yet able to handle such architectures because training a policy network involves an optimization problem for the selection of the optimal action. Backpropagationbased approach currently rely on gradient optimization to perform this task, while TAGI will require developing alternative approaches in order to maintain the analytical tractability without relying on gradient-based optimization.

heading: 6 CONCLUSION
text: This paper proposes a Bayesian reinforcement learning framework that combines TAGI with deep Q-learning. The proposed framework allows estimating the uncertainty of neural network’s parameters and taking an action given a state according to the parameter uncertainty using Thompson sampling. Throughout the experiments with on- and off-policy reinforcement learning approaches, we demonstrate that TAGI can reach a performance comparable to backpropagation-trained networks while using only half the number of hyperparameters. These results challenge the common belief that for large scale problems such as the Atari environment, neural networks can only be trained using the gradient backpropagation. We have shown here that this current paradigm is no longer the only alternative as TAGI has a linear computational complexity and can be used to learn the parameters of complex networks in an analytically tractable manner, without relying on gradient-based optimization.

heading: A ALGORITHM
text: This section presents the n-steps Q-learning algorithm with Tractable Approximate Gaussian Inference (TAGI).
Algorithm 3: n-step Q-learning with TAGI 1 Initialize θ ; ΣV ; number of steps (N) 2 Initialize memoryR to capacity N ; 3 steps = 0; 4 for episode = 1 : E do 5 Reset environment s0; 6 for t = 1 : T do 7 steps = steps + 1; 8 q(st, a) : Q(st, a) ∼ N (µQθ (st, a),Σ Q θ (st, a));
9 at = arg max a∈A q(st, a);
10 st+1, rt = enviroment(at); 11 Store {st, at, rr} inR; 12 if steps mod N == 0 then 13 q(st+1, a ′) : Q(st+1, a ′) ∼ N (µQθ (st+1, a′),Σ Q θ (st+1, a
′)); 14 a′t+1 = arg max
a∈A q(st+1, a
′);
15 Take N samples of {sj , aj , rj} fromR; 16 µyN = µ Q θ (st+1, a ′ t+1); Σ y N = Σ Q θ (st+1, a ′ t+1);

heading: 17 for j = N − 1 : 1 do
text: 18 µyj = rj + γµ y j+1; Σ y j = γ 2Σyj+1 + ΣV ;
19 Update θ using TAGI; 20 Initialize memoryR to capacity N ;

heading: B MODEL ARCHITECTURE
text: This appendix contains the specifications for each model architecture in the experiment section. D refers to a layer depth; W refers to a layer width; H refers to the layer height in case of convolutional or pooling layers; K refers to the kernel size; P refers to the convolutional kernel padding; S refers to the convolution stride; σ refers to the activation function type; ReLU refers to rectified linear unit; Na refers to the number of actions.

heading: C HYPERPARAMETER
text: This appendix details the hyperparameters for each model architecture in the experiment section

Review summaries:
This paper proposed a new Bayesian Deep RL algorithm that learns deep Q networks (DQN) without using gradient descent. The updates of DQN's parameters follows from the tractable approximate Gaussian inference (TAGI) algorithm. Then it studies the empirical performance of proposed algorithm with DQN learned by gradient based optimization in several Atari benchmarks.

The paper describes how to adapt the Q-learning algorithm so that it is compatible with Bayesian deep learning, as opposed to the standard (semi-)gradient-based deep learning implementation. It explains how to propagate uncertainties about network parameters through the neural network computations and ultimately to the q-values, which enables action selection using Thompson sampling. Finally, it presents empirical results on CartPole, Lunar Lander, and five Atari games.

This paper proposes applying TAGI (Goulet et al, 2019), a framework for approximate Bayesian inference in deep neural networks, to deep q-learning. Using assumptions of Gaussianity on various distributions, TAGI infers both the neural network parameters and unit activations, without needing gradient descent. Because all distributions are assumed to be Gaussian, the means and variances can be updated analytically with linear computational complexity. TAGI is essentially used to infer the correct Q-value function, and the approach is applied to lunar lander, cartpole, and several Atari games.

This paper adapts a recently proposed analytical closed-form Bayesian approach to optimizing Neural Networks to Q-Learning. The proposed TAGI-DQN architecture is optimized without gradient descent. RL policies based on TAGI-DQN are shown to perform well on a collection of OpenAI Gym environments, including a small number of Atari games.