Making Sense of Reinforcement Learning and Probabilistic Inference
Authors: Brendan O'Donoghue
Ian Osband
Catalin Ionescu
Venue:  (2020)
Keywords: Reinforcement learning
Bayesian inference
Exploration

Abstract: Reinforcement learning (RL) combines a control problem with statistical estimation: The system dynamics are not known to the agent, but can be learned through experience. A recent line of research casts ‘RL as inference’ and suggests a particular framework to generalize the RL problem as probabilistic inference. Our paper surfaces a key shortcoming in that approach, and clarifies the sense in which RL can be coherently cast as an inference problem. In particular, an RL agent must consider the effects of its actions upon future rewards and observations: The exploration-exploitation tradeoff. In all but the most simple settings, the resulting inference is computationally intractable so that practical RL algorithms must resort to approximation. We demonstrate that the popular ‘RL as inference’ approximation can perform poorly in even very basic problems. However, we show that with a small modification the framework does yield algorithms that can provably perform well, and we show that the resulting algorithm is equivalent to the recently proposed K-learning, which we further connect with Thompson sampling.


Published as a conference paper at ICLR 2020
MAKING SENSE OF REINFORCEMENT LEARNING AND PROBABILISTIC INFERENCE
Brendan O'Donoghue*t
lan Osband
Catalin Ionescu
ABSTRACT
Reinforcement learning (RL) combines a control problem with statistical estima- tion: The system dynamics are not known to the agent, but can be learned through experience. A recent line of research casts 'RL as inference' and suggests a partic- ular framework to generalize the RL problem probabilistic inference. Our pa- per surfaces a key shortcoming in that approach, and clarifies the sense in which RL be coherently cast as inference problem. In particular, an RL agent must consider the effects of its actions upon future rewards and observations: The sxplorationeexploitaaii tradeofT. In all but the most simple settings, the resulting inference is computationally intractable so that practical RL algorithms must re- sort to approximation. We demonstrate that the popular 'RL as inference' approx- imation can perform poorly in even very basic problems. However, we show that with a small modification the framework does yield algorithms that can provably perform well, and we show that the resulting algorithm is equivalent to the recently proposed K-learning, which we further connect with Thompson sampling.
INTRODUCTION
Probabilistic inference is a procedure of making sense of uncertain data using Bayes' rule. The optimal control problem is to take actions in a known system in order to maximize the cumulative rewards through time. Probabilistic graphical models (PGMs) offer a coherent and flexible language to specify causal relationships, for which a rich literature of learning and inference techniques have developed (Koller& & Friedman| 2009). Although control dynamics might also be encoded PGM, the relationship between action planning and probabilistic inference is not immediately clear. For inference, it is typically enough to specify the system and pose the question, and the objectives for learning emerge automatically. In control, the system and objectives are known, but the question of how to approach solution may remain extremely complex (Bertsekas) 2005).
Perhaps surprisingly, there is a deep sense in which inference and control can represent a dual view of the same problem. This relationship is most clearly stated in the of linear quadratic systems, where the Ricatti equations relate the optimal control policy in terms of the system dynamics (Welch al. 1995). In fact, this connection extends
wide range of systems, where control tasks can be related to a dual inference problem through rewards as exponentiated probabilities in distinct, but coupled, PGM [Todoroy] [2007] 2008). great benefit of this connection is that it can allow the tools of inference to make progress in control problems, and vice-versa. In both cases the connections provide new insights, inspire new algorithms and enrich our understanding (Toussaint Storkey
2006 Ziebart et al. 2008 Kappen et al. (2012).
Reinforcement learning (RL) is the problem of learning to control an unknown system (Sutton & Barto 2018). Like the control setting, an RL agent should take actions to maximize its cumulative rewards through time. Like the inference problem, the agent is initially uncertain of the system dynamics, but can learn through the transitions it observes. This leads to fundamental tradeoff: under-sddd states
The agent may be able to improve its understanding through exploring and actions, but may be able to attain higher immediate reward through exploiting its existing knowledge (Kearns & Singh, 2002). In many ways, RI. combines control and inference into a general framework for decision making under uncertainty. Although there has been ongoing research
"These authors contributed equally to this work.
I DeepMindd London, UK, (bodonoghue, losaand, cdi @google e com

---

Published as a conference paper at ICLR 2020
in this area for many decades, there has been a recent explosion of interest RL techniques have made high-profile breakthroughs in grand challenges of artificial intelligence research (Mnih et al. 2013 Silver et al. 2016).
A popular line of research has sought to cast 'RL as inference', mirroring the dual relationship for control in known systems. This approach is most clearly stated in the tutorial and review Levine (2018), and provides a key reference for research in this field. It suggests that a generalization of the RL problem can be cast as probabilistic inference through inference over exponentiated rewards, in continuation of previous work in optimal control (Todorov] 2009). This perspective promises several benefits: probabilistic perspective on rewards, the ability to apply powerful inference algorithms to solve RL problems and natural exploration strategy. In this paper we will outline an important way in which this perspective is incomplete. This shortcoming ultimately results in algorithms that can perform poorly in even very simple decision problems. Importantly, these are not simply technical issues that show up in some edge cases, but fundamental failures of this approach that arise in even the most simple decision problems.
In this paper we revisit an alternative framing of 'RL as inference'. In fact, we show that the orig- inal RL problem was already an inference problem all along Importantly, this inference problem includes inference over the agent's 's future actions and observations. Of course, this perspective is not new, and has long been known et al. 2013). The problem is that, due to the exponential lookahead, this inference problem is fundamentally intractable for all but the simplest problems (Gittins) 1979). For this reason, RL search focuses on computationally efficient approaches that maintain a level of statistical efficiency (Furmston & Barber 2010, Osband et al. 2017).
simply the Bayes-optimal solution, see, e.g., Ghavamzadeh
We provide a review of the RL problem in Section 2 together with simple and coherent framing of RL as probabílistic inference. In Section 3 we present three approximations the intractable Bayes-optimal policy. We begin with the celebrated Thompson sampling algorithm, then we review the popular 'RL as inference' framing, as presented by Levine (2018), and highlight clear and simple shortcoming in this approach. Finally, we review K-learning (O OO'Donoghue] 2018), which we re-interpret as a modification to the RL. as inference framework that provides a principled approach to the statistical inference problem, as well as presenting a relationship with Thompson sampling. In Section 4 we present computational studies that support our claims.
2 REINFORCEMENT LEARNING
We consider the problem of an agent taking actions in unknown environment in order to maximize cumulative rewards through time. For simplicity, this paper will model the environment as a finite horizon, discrete Markov Decision Process (MDP) M = (8, A, R, P, P, p) Here S {1, ... S} is the state space, A = {l,.., A} is the action space and each episode is of fixed length H E N. Each episode E N begins with state sq p then for timesteps h = ... H -1 the agent selects action dn. observes transition 8 with probability P(S 8h, an) E [0. 1] and receives reward Th+1 ~ R(*,, an) ), where we denote by p(*;, un) = Er the mean reward. We define a policy m to be mapping from S to probability distributions over A and write IT for the space of all policies. For any timestep 1 (f, h), we define F, (s), ag. rf, sh of 1: rff) to be the sequence of observations made before time t. An RL algorithm maps histories to policies nं = alg(S, Ft).
Our goal in the design of RL algorithms is to obtain good performance (cumulative rewards) for an unknown M E M, where M is some family of possible environments. Note that this is a different problem from typical 'optimal control', that seeks to optimize performance for one particular known MDP M; although you might still fruitfully apply an RI. algorithm to solve problems of that type. For any environment M and any policy π can define the action-value function,
M (s, a) ES M
Σ j=++1
I Note that, unlike control, connecting RI. with inference will not involve a separate 'dual' problem. Thii choice is for clarity; continuous, infinite horizon, pabtiell environments do not alter our narrative.
2

---

Published as a conference paper at ICLR 2020
Where the expectation in I is taken with respect to the action selection a, for j > h from the policy
t and evolution of the fixed MDP M. We define the value function VA VA (s) Qa~= M. (s, o))
and write 2 M. (8, a) = max 2% M. (s, a) for the optimal Q-values over policies, and the optimal value function is given by (s))+(s)) max, Q%: (s,a).
In order to compare algorithm performance across different environments, it is natural to normalize in terms of the regret, shortfall in cumulative rewards relative to the optimal value,
H
Regret(M (M, alg, L) E EMaale aal
Σ
VO (0f)
This quantity depends on the unknown MDP M, which is fixed from the start and kept the same throughout, but the expectations are taken with respect to the dynamics of M and the learning algorithm alg. For any particular MDP M, the optimal regret of zero can be attained by the non- learning algorithm algas that returns the optimal policy for M.
In order assess the quality of reinforcement learning algorithm, which is designed work across some family of M E M, we need some method to condense performance over a set to single number. There are two main approaches to this:
BayesRegret alg, L.) EM (M, alg, L.), WorstCase alg, L) max Regret M, alg, L), MEM
(3)
(4)
where is prior over the family M. These differing objectives often framed as Bayesian (average-case) (3) and frequentist (worst-case) 4 RL Although these two settings are typically studied in isolation, it should be clear that they are intimately related through the choice of .M and 6. Our next section will investigate what would mean to 'solve' the RL problem. Importantly, we show that both frequentist and Bayesian perspectives already amount problem in probabilistic inference, without the need for additional re-interpretation.
2.1 SOLVING THE RL PROBLEM THROUGH PROBABILISTIC INFERENCE
you want to 'solve' the RL problem, then formally the objective clear: find the RL algorithm that minimizes your chosen objective, 3 or (4). To anchor our discussion, we introduce a simple decision problem designed to highlight some key aspects of reinforcement learning. We will revisit this problem setting as we discuss approximations to the optimal policy.
Problem 1 (One unknown action). Fix N E N 2 3, c > O and define = {M M MN.) Both M and M share S {1), H 1 and A (1, N); they only differ through their rewards:
R+(1) (1) = (2) R (a) 1 - for 3..., N, RT(1) 1, R- R (a) =1 for a 3..,
Where R(a) IR is shorthand for deterministic reward of x when choosing action a.
Problem D is extremely simple, it involves no generalization and no long-term consequences: It is an independent bandit problem with only one unknown action. For known M- M the optimal policy is trivial: Choose ae 2 in A and a, unknown M E M should attempt to optimize the RL objectives (3) or (4). Unusually, and only because Problem is so simple, we can actually compute the optimal solutions to both in terms of L (the total number of episodes) and á = (p+.p" pp) where p* = P(M = M the probability of being in M
in M for all t. An RL agent faced with
For I. > 3 an optimal minimax (minimizing the worst-case regret) RI. algorithm is to first choose ag = 2 and observe r1. If 2 then you know you are in M+ pick a, 2 for all f 1, 2.., for Regret(L L) = 0. If rj = 2 then you know you are in M so pick a, = 1 for all = 1, 2.., for Regret(L) algorithm.
The worst-case regret of this algorithm is 3, which cannot be bested by any
Some frequentist results are high-prohahility bounds on the worst case rather than true worst-case bounds, but this distinction is not important for our purposes
3

---

Published as a conference paper at ICLR 2020
Actually, the same RL algorithm is also Bayes- for any = (p*.ppp) provided p* 3. This relationship is not a coincidence. All admissible solutions to the worst-case problem (4) are given by solutions to the average-case (3) for some 'worst-case" prior á |aldd 1950). As such, for ease of exposition, our discussion will focus the Bayesian (or average-case) setting. However, readers should understand that the same arguments apply to the worst-case objective.
In Problem I the key probabilisttic inference the agent must consider is the effects of it own fions upon the future rewards, i.e,, whether it has chosen action 2. Slightly more generally, where actions independent and episode length H 1, the optimal RL. algorithm can be computed via Gittins indices, but these problems are very much the exception (Gittins) 1979). In problems with generalization or long-term consequences, computing the Bayes-optimal solution is computation- ally intractable. One example of an algorithm that converges to Bayes-optimal solution in the limit of infinite computation is given by Bayes-adaptive Monte-Carlo Planning (Guez et al.] 2012). The problem is that, even for very simple problems, the lookahead tree of interactions between actions, observations and algorithmic updates grows exponentially in the search depth (Strehl et al.) 2006). Worse still, direct computational approximations to the Bayes-optimal solution can fail exponen- tially badly should they fall short the required computation (Munos] 2014). As a result, research in reinforcement learning amounts to trying to find computationally tractable approximations to the Bayes-optimal policy that maintain some degree of statistical efficiency.
3 APPROXIMATIONS FOR COMPUTATIONAL AND STATISTICAL EFFICIENCY
The exponential explosion of future actions and observations means solving for the Bayes-optimal solution is computationally intractable. To counter this, most computationally efficient approaches to RL simplify the problem at time t to only consider inference over the data F, that has been gath- ered prior to time t. The most common family of these algorithms are 'certainty equivalent' (under an identity utility): They take a point estimate for their best guess of the environment M, and try to optimize their control given these estimates M, Typically, these algorithms are used in con- junction with some dithering scheme for random action selection (e.g.. eesilon--reeeee premature and suboptimal convergence (Watkins) 1989). However, since these algorithms do not prioritize their exploration, they may take exponentially long to find the optimal policy (Osband) et al. 2014).
to mitigate
In order for an RL algorithm to be statistically efficient, must consider the value of information. To do this, an agent must first maintain some notion of epistemic uncertainty, so that it can direct its ex- ploration towards states and actions that it does not understand well (O'Donoghue et al. 2018). Here again, probabilistic inference finds a natural home in RL: We should build up posterior estimates for the unknown problem parameters, and use this distribution to drive efficient exploration
3.1 THOMPSON SAMPLING
One of the oldest heuristics for balancing exploration with exploitation is given by Thompson sam- pling, or probability matching (Tommpson) 1933). Each episode, Thompson sampling (TS) ran- domly selects a policy according to the probability it is the optimal policy, conditioned upon the data seen prior to that episode. Thompson sampling is a simple and effective method that success- fully balances exploration with exploitation (Russo et al. 2018).
Implementing Thompson sampling amounts to an inference problem at each episode. For each 8, a, define the binary random variable Oj, (s, a) where On(s, a) denotes the event that action a is optimal for state in timestep h problem,
5 The TS policy for episode & is thus given by the inference
(5) where P(O Fi) is the joint probability over all the binary optimality variables (hereafter we shall suppress the dependence on Fe). To understand how Thompson sampling guides exploration let us consider its performance in Problem when implemented with a uniform prior Φ (2) 1 In the
TS
P(O Fi),
*For the purposes of this paper, we will focus on optimistic approaches to exploration, although more sophisticated information-secking approaches merit investigation in future work (Russo & Van Roy 2014). For the prohlem definition in Section 2 there is always a deterministic optimal policy for Mr.
4

---

Published as a conference paper at ICLR 2020
first timestep the agent samples My 6. it samples M it will choose action dg and learn the true system dynamics, choosing the optimal arm thereafter. If it samples M it will choose action an 1 and repeat the identical decision in the next timestep. Note that this procedure achieves BayesRegret 2.5 according to Φ, but also worst-case regret 3, which matches the optimal minimax performance despite its uniform prior.
Recent interest in TS was kindled by strong empirical performance bandit tasks (Chapelle Lij 2011]. Following work has shown that this algorithm satisfies strong Bayesian regret bounds close to the known lower bounds for MDPs, under certain assumptions (Osband & Van Roy 2017 2016).
However, although much simpler than the Bayes-optimal solution, the inference problem in (5) can
still be prohibitively expensive. Table descrribes one approach to performing the sampling required ( implicitly, by maintaining an explicit model over MDP parameters. This algorithm can be computationally intractable as the MDP becomes large and so attempts to scale Thompson sampling to complex systems have focused on approximate posterior samples via randomized value functions, but it is not yet clear under which settings these approximations should be expected to perform well (Osband et al. 2017). As we look for practical, scalable approaches to posterior inference one promising (and popular) approach is known commonly 'RL as inference'.
Table 1: Model-hased Thompson sampling.
Before episode e
Sample M₁ = (S, Pl. H. F
(s. = (s(, + E.. (t a.) ((()))
Bellman equation
(x( = max 0 (s.
Policy
TS (s, E argmax Ø (s. a) Th
3.2
THE 'RL AS INFERENCE' FRAMEWORK AND ITS LIMITATIONS
The computational challenges of Thompson sampling suggest approximate algorithm that places (5) with parametric distribution suitable for expedient computation. It is possible to view the algorithms the 'RL as inference' approach in this light (Rawlik et al. [013 Todorov 2009
Toussaint [209 Deisenroth et al.) 2013 Fellows et al. (201)); seel Levine ( (201 8) for recent survey. These algorithms choose model the probability optimality according to,
(() & exp
BE' a(ss (otlaa))
(6)
for some 8 >> O, where Th (s, a) is trajectory sequence of state-action pairs) starting from (s, a) at timestep h. and where E denotes the expectation under the posterior at episode L. With this potential in place one can perform Bayesian inference over the unobserved 'optimality' variables. obtaining posteriors over the policy other variables of interest. This presentation of the RL as inference framework is slightly closer to the one in Deisenroth al. (2013 $2.4.2.2) than Levine (2088), but ultimately it produces the same family of algorithms. We provide such derivation in appendix for completeness.
Applying inference procedures to 6 leads naturally to RL algorithms with some 'soft' Bellman updates, and added entropy regularization. We describe the general structure of these algorithms in
Table 2 These algorithmic connections can help reveal connections to policy gradient, actor-critic.
and maximum entropy RL methods (Mnih et al., 2016; O'Donoghue et al. 2017 Haarnoja et al. 2017 2018 Eysenbach et al. 2018). The problem is that this resultant 'posterior' derived using (6) does not generally bear any close relationship to the agent's epistemic probability that (s, a, h) is optimal.
5

---

Published as a conference paper at ICLR 2020
Table 2: Soft Q-learning.
(((s,a)=E'ppl E'P('' a4a)
Bellman equation
Vh(() = 3- 3-1 log E. exp (s,
Policy
" & exp (s,aa
To understand how 'RL as inference' guides decision making, let us consider its performance in Problem [ Practical implementations of 'RL as inference' estimate E'p through observations. For N large, and without prior guidance, the agent is then extremely unlikely to select action d₂ = and so resolve its epistemic uncertainty. Even for an informed prior Φ (2. 2) action selection according to the exploration strategy of Boltzmann dithering is unlikely sample action 2 for which E' (2) = 0 Levine, 2018
et al. 2017). This because the much more probable under the Boltzmann policy.
'distractor' actions
with E' μ
This problem is the same problem that afflicts most dithering approaches to exploration. 'RL as inference' as framework does not incorporate agents epistemic uncertainty, and to poor policies for even simple problems. While (6) allows the construction distribution', this distribution does generally bear any relation the typical posterior an agent should compute conditioned upon the data it has gathered, e.g., equation ( Despite this short- coming RL inference has inspired many interesting and novel techniques, as well as delivered algorithms with good performance on problems where exploration is not the bottleneck (Eysenbach) al., 2018). However, due to the use of language about 'optimality" and 'posterior inference etc., may come as surprise to some that this framework does not truly tackle the Bayesian RL problem. Indeed, algorithms using 'RI as inference' can perform very poorly on problems where accurate uncertainty quantification is crucial to performance. We hope that this paper sheds some light on the topic.
lead
dual 'posterior
3.3
MAKING SENSE OF 'RL AS INFERENCE' VIA K-LEARNING
In this section we suggest subtle alteration to the 'RL as inference' framework that develops coherent notion of optimality. The K-learning algorithm was originally introduced through risk- seeking exponential utility (ODonnoguue 2018). this paper we re-derive this algorithm as principled approximate inference procedure with clear connections to Thompson sampling, and highlight its similarities to the 'RL as inference' framework. We believe that this may offer a road towards combining the respective strengths of Thompson sampling and the 'RL as inference' frame- works. First, consider the following approximate conditional optimality probability at (s, a, h):
P(On(s.0)l (s, a)) exp 3Q
M. (s,
for some > O, and note that this is conditioned the random variable marginalize over possible Q-values yielding
We can
(())(s,))) = N (s) x exp Go 3),
(8)
where G.2 (s. a, denotes the cumulant generating function of the random variable M (s, a) [Kndall 1946). Clearly K-learning and the 'RL as inference' framework are similar, since equa- tions (6) and (7) are closedly linked, but there is crucial difference. Notice that the integral per- formed in 8 is with respect to the posterior over Q.M.+ (s, a), which includes the epistemic uncer- tainty explicitly.

---

Published as a conference paper at ICLR 2020
Table K-learning.
Before episode !
Calculate 5e = BVE
0²
+ Σ
2n (n
Bellman equation
(y((s) = , log Ea exp (s,an))
Policy
( a) exp Br Kr (8,0)
Given the approximation to the posterior probability of optimality in (8) we could sample actions from it as our policy, as done by Thompson sampling ( However, that requires computation of (,,,,, as, B), which is non-trivial. It was shown in 1O'Donoguue 2018) that an upper bound to the cumulant generating function could be computed by solving particular 'soft' Bellman equation. The resulting K-values, denoted K,(s, a) at (s, h), are also optimistic for the expected optimal Q-values. Specifically, for any sequence { the following holds
the cumulant generating function C
(n(s,a) 2 (R, 2 E Q (s,a).
Following a Boltzmann policy over these K-values satisfies a Bayesian regret bound which matches the current best bound for Thompson sampling up logarithmic factors under the same set of assumptions. We summarize the K-learning algorithm in Table (3), where B > 0 is constant and and n²(s,a) a) is the visitation count of (8, a) before episode E, i.e., the number of times the is constant. The uncertainty in the transition
agent has taken action at state s, and function is incorporated into the constant a, which is a technical detail we omit here for clarity, see O'Donoghee] 2018) for details. In this way the agent given reward signal that includes bonus which is higher for states and actions that the agent has visited less frequently.
Comparing Tables 2 and is clear that soft Q-learning and K-learning share some similarities: They both solve a "soft' value function and use Boltzmann policies. However, the differences are important. Firstly, K-learning has an explicit schedule for the inverse temperature parameter 3e, and secondly it adds a bonus based on visitation count to the expected reward. These two relatively small changes make K-learning a principled exploration and inference strategy.
To understand how K-learning drives exploration, consider its performance on Problem I Since this is a bandit problem we can compute the cumulant generating functions for each arm and then use the policy given by (8). For any non-trivial prior and choice of / > 0 the cumulant generating function is optimistic for arm 2 which results the policy selecting arm 2 more frequently, thereby resolving its epistemic uncertainty. As 8 + oc K-learning converges to the policy of pulling arm 2 deterministically. This in contrast to soft Q-learning where arm exponentially unlikely to be selected as the exploration parameter 3 grows.
3.3.1 1 CONNECTIONS BETWEEN K-LEARNING AND THOMPSON SAMPLING
Since K-learning can be viewed as approximating the posterior probability of optimality of each action it is natural to ask how close an approximation it is. A natural way to measure this similarity is the Kullback-Leible (KL) divergence between the distributions,
DKL (P(O((s)) Th
Σ (ogPass.)) a)) (s.
where we are using the notation (s(s) (s and T (s) = (s. This different to the usual notion of distance that is taken in variational Bayesian methods, which would typically reverse the order of the arguments in the KL divergence (Blundell et al. 2015). However, in RL that 'direction" is not appropriate: distribution minimizing DKL(Ta, (s) (()) may put zero probability on regions of support of (O,, (s)). This means an action with non zero probability of be- ing optimal might never be taken. On the other hand policy minimizing D (s)) || TT (s)) must assign a non-zero probability to every action that has a non non-zero probability of being optimal, incur an infinite KI. divergence penalty. With this characterization in mind, and noting that the

---

Published as a conference paper at ICLR 2020
Thompson sampling policy satisfies TT (s)),s)),, our next result links the policies of K-learning to Thompson sampling.
Theorem 1. The K-learning value function VK and policy x R defined in Table 3 satisfy the follow- ing bound every state Sand h O.... H:
v (8) 2 BV (s) (s) + 1 DKL(((On(s)) [1 (s))
(10)
We defer the proof to Appendix 5.2 This theorem tells us that the distance between the true proba- bility of optimality and the K-learning policy is bounded for any choice of 3 < co. In other words, there is an action that might be optimal then K-learning will eventually take that action.
3.4
WHY IS 'RL AS INFERENCE' SO POPULAR?
The sections above outline some surprising ways that the 'RL as inference' framework can drive suboptimal behaviour in even simple domains. The question remains, why do so many popular and effective algorithms lie within this class? The first, and most important point, is that these algorithms can perform extremely well in domains where efficient exploration is not bottleneck. Furthermore, they are often easy to implement and amenable to function approximation (Peters et al. [0010] Kober & Peters 2009: Abdolmaleki al. 2018). Our discussion of K-learning in Section 3.3 shows that relatively simple fix to this problem formulation can result in a framing of RL as inference that maintains coherent notion of optimality. Computational results show that, tabular domains, K- learning can be competitive with, or even outperform Thompson sampling strategies, but extending these results to large-scale domains with generalization an open question (O O'Donoghue 2018
Osband et al. 2017].
The other observation is that the 'RL as inference' can provide useful insights to the structure of particular algorithms for RL. It is valid to note that, under certain conditions, following policy gradient is equivalent to a dual inference problem where the 'probabilities' play the role of dummy variables. but not supposed to represent the probability of optimality in the RL problem. In this light, Levine (2018) presents the inference framework as a way to generalize a wide range of state of the RL algorithms. However, when taking this view, you should remember that this inference duality is limited to certain RL algorithms, and without some modifications (e.g. Section 3.3 this perspective is in danger of overlooking important aspects of the RL problem.
4 COMPUTATIONAL EXPERIMENTS
4.1 ONE UNKNOWN ACTION (PROBLEM
Consider the environment of Problem I with uniform prior Φ (). We fix le 3 and consider how the Bayesian regret varies with N > 3. Figure I compares how the regret scales for Bayes-optimal (1.5), Thompson sampling (2.5), K-learning ( 2.2) and soft Q-learning (which grows linearly in N for the optimal 3 + O, but would typically grow exponentially for 3 > 0). This highlights that, even simple problem, there can be great value in considering the value of information.
3
300.0
agunl
Expected
Keeaming
Scht
Thompsox
100.0
1050.5
Problem size N
Figure 1: Regret scaling Problem Soft Q-learning does not scale gracefully with N.
Figure 2: DeepSea exploration: A simple example where deep exploration is critical.
8

---

Published as a conference paper at ICLR 2020
4.2 'DEEPSEA' EXPLORATION
Our next set of experiments considers the 'DeepSea' MDPs introduced by Oshand et al. (017). At high level this problem represents 'needle in a haystack', designed to require efficient exploration, the complexity which grows with the problem size N E N. DeepSea (Figure is a scalable variant of the "chain MDPs' popular in exploration research (Jaksch et al. 2010).
The agent begins each episode in the top-left state an N x grid. At each timestep the agent move left right one column, and falls right, and zero reward for left. There is only one rewarding state, at the bottom right cell. The only way the agent
There is small negative reward for heading
receive positive reward is to choose go right in each timestep. Algorithms that do not perform deep exploration will take an exponential number of episodes to learn the optimal policy, but those that prioritize informative states and actions can learn much faster.
Figure shows the 'time to learn' for tabular implementations of K-learning (Section 3.3), soft Q- learning (Section 3.2) and Thompson sampling (Section 3.1p. We implement each of the algorithms with [0,, 1) prior for rewards and Dirichlet(1/N) prior for transitions. Since these problems are small and tabular, we can use conjugate prior updates and exact MDP planning via value iteration. As expected, Thompson sampling and K-learning scale gracefully to large domains but soft Q- learning does not.
4.3 BEHAVIOUR SUITE FOR REINFORCEMENT LEARNING
So far our experiments have been confined to the tabular setting, but the main focus of 'RL as inference" is for scalable algorithms that work with generalization. In this section we show that the same insights we built in the tabular setting extend to the setting of deep RL. To do this we implement variants of Deep Q-Networks with a single layer. 50-umit MLP (Mnih et al., 2013). To adapt K-learning and Thompson sampling to this deep RL setting we
ensemble of size 20 with randomized prior functions to approximate the posterior distribution over neural network Q-values (Osband al. 2018) (full experimental details are included in Appendix (5.4). We then evaluate all of the algorithms on bsuite: A suite of benchmark tasks designed to highlight key issues in RL. (Osband 2019))
In particular, bsuite includes an evaluation on the DeepSea problems but with a one-hot pixel representation of the agent position. In Figure 3b we see that the results for these deep RL im- plementations closely match the observed scaling for the tabular setting. In particular, the algo- rithms motivated by Thompson sampling and K-learning both scale gracefully large problem sizes, where soft Q-learning is unable to drive deep exploration. Our bsuite evaluation includes many more experiments that can be fit into this paper, but we provide link the complete results at http:////neeeeeeeeeeeeeeooeeeeee
In general, the results for Thompson sampling and K- learning are similar, with soft Q-learning performing significantly worse on 'exploration' tasks. push a summary of these results to Appendix
Episodes unzil Repestognt 0.8
Lipiadde until toyestt 0.9
10000
10000
aquatt
agont
9000
Sod.0 therrpoon
5000
5ri4)) meveiogo
0.0000
30
30
Problem size
Proboeem size N
(a) Tabular state representation.
(b) One-hot pixel representation into neural net.
Figure 3: Learning times for DeepSea experiments. Dashed line represents 2
DDeeSSea figure taken with permission from the 'bsuite' Osband al. 2019

---

Published as a conference paper at ICLR 2020
5 CONCLUSION
This paper aims to make sense of reinforcement learning and probabilistic inference. We review the reinforcement learning problem and show that this problem of optimal learning already com- bined the problems of control and inference. As we highlight this connection, we also clarify some potentially confusing details in the popular 'RL inference' framework. We show that, since this problem formulation ignores the role of epistemic uncertainty, that algorithms derived from that framework can perform poorly on even simple tasks. Importantly, we also offer a way forward, to reconcile the views of RI. and inference in way that maintains the best pieces of both. In partic- ular, we show that a simple variant to the RL as inference framework (K-Icarning) can incorporate uncertainty estimates drive efficient exploration. We support our claims with series of simple di- dactic experiments. We leave the crucial questions of how to scale these insights up to large complex domains for future work.
REFERENCES
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learning Representations (ICLR), 2018.
Søren Asmussen and Peter W Glynn. Stochastic simulation: Algorithms and analysis, volume 57. Springer Science & Business Media, 2007.
Dimitri P Bertsekas. Dynamic programming and optimal control, volume Athena Scientific, 2005.
Charles Blundell, Julien Corneiise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. arXiv preprint 1rX1v:1505.05424, 2015.
Nicolò Cesa- Besa-Bianchhi, Claudio Gentile, Gergely Neu, and Gabor Lugosi. Boltzmann exploration done right. In Advances in Neural Information Processing Systems, pp. 6287-6296, 2017.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pp. 2249-2257, 2011.
Mare Peter Deisenroth, Gerhard Neumann, Jan Peters, al. A survey on policy search for robotics. Foundations and Trends in Robotics, 2(1-2):1-142, 2013.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint NXXXvv1802.06077 2018
Matthew Fellows, Anuj Mahajan, Tim GJ Rudner, and Shimon Whiteson. Virel: A variational inference framework for reinforcement learning. In Advances in Neural Information Processing Systems, pp. 7 7120-7134 2019.
Thomas Furmston and David Barber. Variational methods for reinforcement learning. In Pro- ceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 241-248 2010.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforcement learning: A survey. Foundations and Trends in Machine Learning, 8(5-6):359 4833, 2015.
John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B (Methodological), pp. 148-177, 1979.
Arthur Guez, David Silver, and Peter Dayan. Efficient adaesiade reinforcement learning using sample-based search. In Advances in Neural Information Processing Systems, pp. 1025-1033, 2012.
Tuomas Haarojja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep macrgy-based policies. Proceedings of the 34th International Conference on Machine Learning (ICMI.),011
10

---

Published as a conference paper at ICLR 2020
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.01290, 2018.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1533-1600) 2010.
Hilbert J Kappen, Vicenç Gómez, and Manfred Opper. Optimal control as a graphical model infer- ence problem. Machine learning. 87(2):15--188 2012.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine Learning, 49(2-3):299-232, 2002.
Maurice George Kendall. The advanced theory of statistics. Charles Griffin and Co., Ltd., London, 1946.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
Jens Kober and Jan R Peters. Policy search for motor primitives in robotics. In Advances in neural information processing systems, pp. 449-856, 2009.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: 00888800009999 2018
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. In NIPS Deep Learn- ing Workshop. 2013.
Volodymyr Mnih Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 1928-1937, 2016.
Rémi Munos.
From bandits to monte-carlo tree search: The optimistic principle applied to opti- mization and planning. Foundations and Trends Machine Learning. 7(1):1-129, 2014.
Brendan O' O'Donoghue. Variational Bayesian reinforcement learning with regret bounds. arXiv preprint arXiv:1807.09647 2018
Brendan Donoghuee Remi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. Combining policy gradient and Q-learning. In International Conference Learning Representations (ICLR), 2017.
Brendan O' O'Donoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty Bell- man equation and exploration. In Proceedings of the 35th International Conference Machine Learning 2018. 2018
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv::6066 007320222.... 2016.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. arXiv preprint
2014.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances In Neural Information Processing Systems, pp. 4026-4034, 2016.
11

---

Published as a conference paper at ICLR 2020
Ian Osband, Daniel Russo, Zheng Wen, and Benjamin Van Roy. Deep exploration via randomized 2017.
value functions. arXiv preprint
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 8617-8629, 2018.
lan Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepezvari, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado Van Hasselt. Behaviour suite for reinforcement learning. 2019.
Jan Peters, Katharina Milling, and Yasemin Altun. Relative entropy policy search. AAAI. Atlanta, 2010.
Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal control and rein- forcement learning by approximate inference. In Twenty-Than Third International Joint Conference on Artificial Intelligence, 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. In Advances in Neural Information Processing Systems, pp. 1583-1591, 2014
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, al. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1): 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittiesser, Ioannis Antonogiou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model- free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pp. 1-1- ACM, 2006.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-2) 1933.
Emanuel Todorov. Linearly-solvable markov decision problems. In Advances in neural information processing systems, pp. 1369-1376, 2007.
Emanuel Todorov. General duality between optimal control and estimation. 2008 47th IEEE
Conference Decision and Control, pp. 4286-4292 IEEE, 2008.
Emanuel Todorov. Efficient computation of optimal actions. Proceedings of the national academy of sciences, (06(28):1147881) 1483, 2009.
Mare Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference on machine learming, pp. 1049-1056. ACM, 2009.
Mare Toussaint and Amos Storkey. Probabilistic inference for solving discrete and continuous state markov decision processes. In Proceedings of the 23rd international conference Machine learning, pp. 945-952. ACM, 2006.
Abraham Wald. Statistical decision functions. 1950.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, University of Cambridge England, 1989.
Greg Welch, Gary Bishop, et al. An introduction to the Kalman filter. 1995.
Brian D Ziebart, Andrew Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. 2008.
12

---

Published as a conference paper at ICLR 2020
APPENDIX
5.1 SOFT Q-LEARNING DERIVATION
We present derivation of soft Q-learning from the RI. inference parametric approximation the probability of optimality. Although our presentation is slightly different to that of (2018) we show here that the resulting algorithms essentially identical. Recall from equation (6) that the parametric approximation to optimality we consider is given by
((O exp
Σ
(sT,a")ET(ss.a)
exp(3EE ((s, exp((EE
E
3E uls" ,a")
( (8),a)))
=exp(3E'm(s, a) ()) (m)
where (s, a) is trajectory starting from (s, a) at time h and B > is hyper-parameter. Now we using the (unknown) system dynamics. Since this
must marginalize out the possible trajectories algorithm we shall use the expected value of the transition probabilities, under the posterior at episode L, which means we can write
P(Tr a)) = E'P(s', 8, a)p(a') (oddsss))PPP (P (s),,))),
and we make the additional assumption that the 'prior' p(als) is uniform across all actions for each s (this assumption standard in this framework, see Levine (2018). In this case we obtain
((,)), E (...
Tu(s.a)
exp(SE' pls, a))
Σ
E'P(s',s, s,a)
Σ
s',a'
exp(3EE a(s,a))
Σ
s'.a'
Now with this we can rewrite
(og,((O(ssa) = 3E* p(s, a) + log
Σ s'aa'
s) log Z(s)
where (s)) is the normalization constant for state s, since Σ. P(O,(ss for any s, and using Jensen's 's we have the following bound
log (s, a)) 2 3E a(s,a) + Σ E'P(s'' s, log Σ iP log ((s)
now if introduce the soft Q-values that satisfy the soft Bellman equation
(n( a() Σ E'P(s' s. a) log Σ exp 3Q
then
(()((s)))) x exp (8,
Σ exp (Q,
and we have the soft Q-learning algorithm (the approximation comes from the fact we used Jensen's 's inequality provide bound).
5.2 PROOF THEOREM 1
Theorem. The K-learning value function VK and policy K defined in Table 3 satisfy the following bound every state s E and O.... H:
Vi Z Mi())((s)))))) B- DxL(((((()) (s)
13

---

Published as a conference paper at ICLR 2020
Proof. Fix some particular state S, and let the joint posterior over value and optimality be denoted by
(11)
where we use / to denote the conditional distribution over Q-values conditioned on optimality. Re- call that from equation (7) we have approximated the conditional posterior probability of optimality as
(()n(s (s, a)) x exp 3Q (s, a),
for some B > 0, which when yields
(s))(s & exp G (s, a, B).
From Bayes' rule this implies the following approximation to the conditional distribution
(s.)((s)))) = (s, "s. "s,,a)
(s)
P(On(s,a)) = =P(Q (s, e (s,a) as,
(12)
This is known the exponential tilt of the posterior distribution MI (s, a)) and has myriad of applications in statistics (Asmussen & Glynn] (007). From this we could derive an approximation to the joint posterior (II), however, the K-learning policy does not follow ( since computing the cumulant generating function is non-trivial. Instead we compute the K-values, which are the solution
to Bellman equation that provide a guaranteed upper bound on the cumulant generating function, and the K-learning policy is thus
T (s, a) a exp(3K
where we have O' D'Donoghue 2018
(Kn G (B)
(13)
With that mind we take our approximation the joint posterior 11 to be
P(VA (s), a)) = =i(Q (s, ()) a) a) (s,
Now consider the KI KL-divergence between the true joint posterior and our approximate one, quick calculation yields
DRI((P(V, (s) On,, || P(V. (s), (n(ss)))) DKr (s))+
Σ P(On P(O Dx) Mi* (s),s))s)s) a)) || (s.
(14)
for timestep and state 8. Considering the terms the right hand side of (14) separately have
DKL. DKI,( (P(Ox(()) (5)) H((P(O(()))))) 3 Σ ((a Σ exp exp 3K
where denotes the entropy, and using
Σ F((On(s.0)DDx (s.a))),ss a)) M. (s.)))(sss)))
Σ P(O B B(O M. (s.,))))ss)))
(s,a))) (s,aa)
Now we sum these two terms, using
[3) and the following identities
Σ P(O (s,,)))))s)a)) = E max Q M " a) = EV, *())
14

---

Published as a conference paper at ICLR 2020
and
((ON(S.)))0KK((10 (s.a))On(s.a) [I (s,
[ (/o.:////..////ooo/oa//////oloa ((P(A))(((()))))))))
H(P(O,(s)))
& M((((O(s))),
since ()) a)) S O, we obtain
D (P(V) (s), (s. || P(V ((V, On(s,)))) S log Σ exp exp,3Kn(s,0) -8V (s).
The theorem follows from this and the fact that the K-learning value function is defined as
(s) (s) 3-1 log Σ exp (K,(a))))
well as the fact that
D (P(O((()) II (s)) & (s), P|((,, On(ssa))
from equation
14
5.3
PROBLEM D K-LARNNING DETAILS
For bandit problem the K-learning policy is given by K x exp G. (3),
which requires the cumulant generating function of the posterior over each arm. For arm 1 and the distractor arms there is no uncertainty, in which case the cumulant generating function is given by
G (B) = MsB, = 1,3...... N.
In the case of arm 2 the cumulant generating function is G (B) log ((1/2) cxp(2 (1/2) exp(-28))
In O' D'Doogguu 2018 it was shown that the optimal choice of B is given by
8 argmin 320
B log
Σ
exp G.
which requires solving convex optimization problem in variable 3-1 In the of problem 1 the optimal choice of 3 == 10.23, which yields x = 0.94. Then, once arm 2 has been pulled once and the true reward of arm has been revealed, its cumulant generating function has the same form as the others, and then the optimal choice of /3 is simply
3 argmin 8 log
exp 14, Dc,
$20
at which point K-learning is greedy with respect to the optimal arm.
5.4 IMPLEMENTATION DETAILS FOR BSUITE EVALUATION
All three algorithms the same neural network architecture consisting of MLP (multilayer perceptron) with a single hidden layer with 50 hidden units. All three algorithms used replay buffer of the most recent 1 transitions to allow re-use of data. For all three the Adam optimizer (Kingma & Ba 2014) was used with learning rate 10-3 and batch-size 128, and learning is performed at every time-step. For both K-learning and soft Q-lcarning the temperature was Bootstrap DQN we chose an ensemble of size 20, and used the randomized prior functions (Osband af. 2018) with scale 3.. For K-learning, in order to estimate the cumulant generating function of the reward, we used an ensemble of neural networks predicting the reward for each state and action and used these to calculate the empirical cumulant generating function over them. Each these was a single hidden layer MLP with 10 hidden units. Finally, we noted that actually training a small ensemble of K-networks performed better than single network, we used an ensemble of size 10 for this purpose as well as using randomized priors to encourage diversity between the elements of the ensemble with scale 1.0. The K-learning policy was the Boltzmann policy over all the ensemble K-values at each state.
8-1 0.01. For
15

---

Published as a conference paper at ICLR 2020
bsuite report: Making sense of RL and Inference
The Behaviour Suite for Reinforcement Learning, or bsuite te for short, is a collection of carefully-designed experiments that investigate capabilities of reinforcement learning (RL) agent. The aim of bsuito project collect clear, informative scalable problems that capture key issues
design of efficient general learn- ing algorithms and study agent behaviour through their performance on these shared benchmarks. This report provides snapshot of agent performance bsuite201 obtained by running the experiments from github. com/ de deepaiins/bsuite Os- (band al. (2019)
6.1 AGENT DEFINITION
All agents were run with the same network architecture (a single layer MLP with 50 hidden units ReLU activation) adapting DQN (Mnih et al. 2013). Full hyperparameters Appendix (5.4
boon_dqn: hootstrapped DQN with prior networks (Oshand et al. 2016: 2018).
learn: K-learning via ensemble with prior networks (O'Donoghue 2018 Osband al. 2018).
soft_q: soft Q-learning with temperature 3 = 0.01 (O O'Donoghue et al. 2017).
6.2 SUMMARY SCORES
Each bsuite experiment outputs a summary score in [0,1]. We aggregate these scores by according to key experiment type, according to the standard analysis notebook. A detailed analysis of each of these experiments may be found in a notebook hosted on Colaboratory: sit.Ly/rl-inferent -auiiee bsuite
Explomation
Gredit Antogrmmnnn
Genoralisation
Rasic
Menny
agent
Teot Algi
Scale
k.omm
X0.
Nolse
Figure 4: Snapshot of agent behaviour.
Figure 5: Score for each bsuite experiment.
6.3 RESULTS COMMENTARY
Overall, we see that the algorithms K-learning and Bootstrapped DQN perform extremely similarly across bsui te evaluations. However, there is clear signal that soft Q-learning performs markedly worse on the tasks requiring efficient exploration. This observation is consistent with the hypothesis that algorithms motivated by 'RL Inference' fail to account for the value of exploratory actions.
Beyond this major difference in exploration score, we see that Bootstrapped DQN outperforms the other algorithms problems varying 'Scale'. This too is not surprising, since both soft Q and K- learning rely on a temperature tuning that will be problem-scale dependent. Finally, we note that soft Q also performs worse some 'basic' tasks, notably 'bandit' and 'mnist'. We believe that the relatively high temperature (tuned for best performance on Deep Sea) leads to poor performance on these tasks with larger action spaces, due many random actions.
16


Reviews:
[{"review_id": "ryez-G1Lqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors develop a criticism of the \"RL as inference\" standard approximations and propose a simple modification that solves its main issues while keeping hold of its advantage. Even though this modification ends up relating to a previously published algorithm, I judge the submission to be worthwhile publishing for the following contributions:\n- clarity/didacticism of the exposition, the minimal problem, the positioning,\n- the theorem,\n- the (hopefully to be completed) experiments\n\nThe experiments are my main criticism of the paper, in particular the bsuite ones that was absolutely impenetrable for me: not only the experiments but also the results. I hope this will be completed in the final version. It was also a bit unclear to me the advantage of K-learning over Thomson sampling methods.\n\nMinor remarks and typos:\n- famliy => family\n- I would not say that frequentist RL is the worst-case, but more high-probability (it's the worst case within the concentration bounds).\n- the agent in then => the agent is then\n- KL has 2 meanings in the notations: K-learning and KL divergence. For clarity, I suggest to use only K for K-learning (for instance).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gAoVaTYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper at hand presents an alternative view on reinforcement learning as probabilistic inference (or equivalently maximum entropy reinforcement learning). With respect to other formulations of this view (e.g. Levine, 2018; I am referring to the references of the paper here), the paper identifies a shortcoming in the disregard of the agent’s epistemic uncertainty (which seems to refer to the uncertainty with respect to the underlying MDP). It is argued, that algorithms based on the prevailing probabilistic formulation (e.g. soft Q-learning) suffer from suboptimal exploration.\nThe paper thus compares maximum entropy RL to K-learning (O’Donoghue, 2018), which is taken to address the issue of suboptimal exploration due to its temperature scheduling and its inclusion of state-action pair counts in the reward signal. \n\nAs its technical contribution, the paper re-interprets K-learning via the latent variable denoting optimality employed in Levine (2018) and introduces a theorem bounding the distance between the policies of Thompson sampling and K-learning. Empirical validation of the claims is provided via experiments on an engineered bandit problem and the tabular MDP (i.e. DeepSea from Osband et al., 2017), as well as via soft Q-learning results on the recently suggested bsuite (Osband et al., 2019).\n\nI consider this paper a weak reject. This is in light of me finding it very hard to follow the papers main claims and arguments, even though it positions itself as communicating connections (“making sense”) in prior work, rather than presenting a novel algorithm. While this is in part due to the complicated issue and math being discussed (and the paper probably catering to a very narrow audience), the paper in its current state does seem to hinder understanding as well.\n\nOn the positive side, I do appreciate the intention of the paper, namely to connect RL as probabilistic inference, Thompson sampling and K-learning. In my opinion, this can be taken as a valuable addition to the current understanding of these approaches. Also, I like the experiments as they are specifically constructed to support the claims of the paper.\nOn the negative side, vague language, missing assumptions and lax notation seem to hinder the understanding of the paper to a considerable extend: e.g. it is stated, that “we connect the resulting algorithm with […] K-learning”. However, I do not recognize a new algorithm being provided. Instead the paper argues in favor of K-learning. The assumptions that come with K-learning are not mentioned. The restriction of K-learning to tabular RL is taken to be understood implicitly (whereas RL as probabilistic inference seems applicable with function approximation also, which is not mentioned in the comparison). The paper always talks of shortcomings (plural) of RL as probabilistic inference, but only provides one argument (suboptimal exploration) with respect to this. RL as probabilistic inference is introduced in a different form as in prior literature (i.e. Equation 6), while the derivation in the Appendix spanning the differences in notation being hard to follow due to (maybe minor?) notational issues (e.g. x and y seem to have replaced s’ and a; further down there is a reference to Equation 7, however probably it is meant to be 8 and even that with some leap in notation).\nThe paper would benefit from better proof-reading, where mistakes in a very dense argumentation make it hard to follow (e.g. I do not understand the sentence “The K-learning expectation (7) is with respect to the posterior over Q[…] to give a parametric approximation to the probability of optimality.”)\n\nLiterature wise, the paper draws heavily from two unpublished papers (Levine, 2018; O’Donoghue, 2018). While this makes it harder to arrive at a high confidence level with respect to the paper’s claims, I would not argue this to be critical.\nI would consider raising my score, if the authors would improve the accessibility of the paper by polishing the argumentation and notation. \n\nConfidence: low. It is very likely, that I have misunderstood key arguments and derivations. Also, I did not attempt to follow all of the technical derivations.\n\n\n======\npost rebuttal comment:\n\n\nI changed the score of my review in light of the rebuttal.\nThe changes made to the paper overall address my concerns.\nI do consider the additional explanations and re-phrasings as well as the improved notation a nice improvement of the paper.\nWhile I did not read all of the appendix, Section 5.1 is much more readable and understandable in the new version.\n\nIn light of this paper probably being published, I share some typos/inconsistencies I still noticed:\n\np. 4: the solving for -> solving for the\np. 7: s_{h+1} -> s' (in Table 3) ?\np. 7: table -> Table; tables -> Tables\np. 7: (Fix position of K:) \\pi_h(s)^K -> \\pi_h^K(s) ((also in Appendix))\np. 9: (2x) soft-Q learning -> soft Q-learning; Q Networks -> Q-Networks; Soft Q -> soft Q-learning\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eIQQVUtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper criticizes the ‘RL as inference’ paradigm by highlighting its limitations and shows that a variant of this framework - the K-learning algorithm (O'Donoghue et. al., 2018) does not have these limitations. The paper first clarifies some points of confusion regarding RL as inference, namely the fact that RL was originally an inference problem all along. A simple example is used to demonstrate that the RL as inference framework (Levine, 2018) fails to choose the optimal actions that resolve epistemic uncertainty, whereas the K-learning algorithm does select the optimal action. Further, a connection is made which reveals that K-learning is an approximate version of Thompson sampling - the strategy of using as single posterior sample of parameters given data for greedy actions which originated in bandit settings. Some empirical results are provided highlighting the cases where Soft Q-learning (Levine, 2018) fails but Thompson sampling and K-learning do not.\n\nI vote for accepting this paper as it brings to light an important limitation of the popular RL as Inference framework with a didactic example which, to the best of my knowledge, has not been shown before.\n\nThe paper does a great job at succinctly introducing a simple bandit problem where the bayes-optimal policy is to take a first action that is supposed to immediately resolve all epistemic uncertainty and then exploit the optimal action repeatedly for future plays. However, this simple problem is designed in such a way that there are several other sub-optimal actions which make the RL as inference algorithm have an exponentially low probability of selecting the optimal action. This implies that RL as inference, unlike Thompson sampling, does not in fact take into account epistemic uncertainty.\n\nFeedback to authors:\n- The introduction of family of MDPs caused a lot of confusion about the problem setting. I was not sure if a new MDP is sampled from \\phi at every episode in L or a single MDP is sampled and kept the same throughout. This was clarified later on in the middle of section 2.1, but it could have been introduced more carefully earlier on,\n- The tables 1-3 summarizing algorithms are useful but it would be great if there could be a side by side comparison of all three in a single table.\n- The notation is very dense and I see that efforts were made to avoid this, but it still feels inaccessible.\n- I am not sure of the role of experiments in section 4.3, if there is no comparison to K-learning. I understand that the authors leave it to future work but then the experiments feel out of place.\n- “... RL as inference has inspired many interesting and novel techniques, as well as delivered algorithms with good performance on problems where exploration is not the bottleneck (Gregor et al., 2016)”. I think this sentence is false, Gregor et. al. do not employ RL as inference anywhere in their paper. Also, I don’t think the point of their paper was to show good performance on any problem. Maybe this was mixed up with Eysenbach, 2018, a successor paper which uses RL as inference?\n\n \n\nReferences:\nO'Donoghue, Brendan. \"Variational Bayesian Reinforcement Learning with Regret Bounds.\" arXiv preprint arXiv:1807.09647 (2018).\n\nLevine, Sergey. \"Reinforcement learning and control as probabilistic inference: Tutorial and review.\" arXiv preprint arXiv:1805.00909 (2018).\n\nGregor, Karol, Danilo Jimenez Rezende, and Daan Wierstra. \"Variational intrinsic control.\" arXiv preprint arXiv:1611.07507 (2016).\n\nEysenbach, Benjamin, et al. \"Diversity is all you need: Learning skills without a reward function.\" arXiv preprint arXiv:1802.06070 (2018).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores in more detail the "RL as inference" viewpoint and highlights some issues with this approach, as well as ways to address these issues. The new version of the paper has effectively addressed some of the reviewers' initial concerns, resulting in an overall well-written paper with interesting insights.
Decision: Accept (Spotlight)