Probabilistic Inference in Reinforcement Learning Done Right
Authors: Jean Tarbouriech
Tor Lattimore
Brendan O'Donoghue
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning
Bayesian inference
Exploration
TL;DR: We derive a principled Bayesian approach for 'RL as inference' that leads to efficient exploration.

Abstract: A popular perspective in Reinforcement learning (RL) casts the problem as probabilistic inference on a graphical model of the Markov decision process (MDP). The core object of study is the probability of each state-action pair being visited under the optimal policy. Previous approaches to approximate this quantity can be arbitrarily poor, leading to algorithms that do not implement genuine statistical inference and consequently do not perform well in challenging problems. In this work, we undertake a rigorous Bayesian treatment of the posterior probability of state-action optimality and clarify how it flows through the MDP. We first reveal that this quantity can indeed be used to generate a policy that explores efficiently, as measured by regret. Unfortunately, computing it is intractable, so we derive a new variational Bayesian approximation yielding a tractable convex optimization problem and establish that the resulting policy also explores efficiently. We call our approach VAPOR and show that it has strong connections to Thompson sampling, K-learning, and maximum entropy exploration. We conclude with some experiments demonstrating the performance advantage of a deep RL version of VAPOR.

Probabilistic Inference in Reinforcement Learning
Done Right
Jean Tarbouriech Google DeepMind jtarbouriechhgooge.ccom
Tor Lattimore Google DeepMind lattimore@google.c
Brendan O'Donoghue Google DeepMind
bodonooghue@googgeecco
Abstract
A popular perspective in Reinforcement learning (RI.) casts the problem as prob- abilistic inference on a graphical model the Markov decision process (MDP). The core object of study is the probability of cach state-action pair being visited under the optimal policy. Previous approaches to approximate this quantity can be arbitrarily poor, leading algorithms that do not implement genuine statistical inference and consequently do not perform well challenging problems. In this work, we undertake rigorous Bayesian treatment of the posterior probability of state-action optimality and clarify how it flows through the MDP. We first reveal that this quantity can indeed be used generate policy that explores efficiently, as measured by regret. Unfortunately, computing it is intractable, so we derive a variational Bayesian approximation yielding tractable convex optimization problem and establish that the resulting policy also explores efficiently. We call our approach VAPOR and show that has strong connections Thompson sampling, K- learning, and maximum entropy exploration. We conclude with some experiments demonstrating the performance advantage of a deep RL version of VAPOR.
Introduction
Reinforcement learning (RL) is the problem of learning control unknown system by taking actions to maximize its cumulative reward through time [76]. As the agent navigates the environment, it receives noisy observations which it can [21]. Unlike supervised learning, where the performance of an algorithm does not influence the data will later observe, in RL the policy of the agent affects the data it will collect, which in affects the policy, and so on. As a result, an agent must sometimes take actions that lead to states where has epistemic uncertainty about the value of those states, and sometimes take actions that lead to more certain payoff. The tension between these two modes is the exploration-exxlootaiion trade-off' [2, 35]. In this light, RL is statistical inference problem wrapped in a control problem, and the two problems must be tackled simultaneously for good data efficiency.
update its (posterior) beliefs about the enviromment
is natural apply Bayesian probabilistic inference the uncertain parameters in RL [21] and, since the goal of the agent is to find the optimal policy, relevant object study is the posterior probability of optimality for each state-action pair. In fact, the popular 'RI. inference' approach, most clearly summarized the tutorial and review of [37], embeds the control problem into graphical model by introducing optimality binary random variables that indicate whether state-action is optimal. In the 'RL as inference' setup these optimality variables are assumed to be observed and take the value one with probability depending on the local reward. This surrogate potential seems like peculiar and arbitrary choice, yet it has been widely accepted due to its mathematical convenience: for deterministic dynamics, the resulting probabilistic inference is equivalent maximum entropy RL [80, 87]. However, this approximation leads to a critical shortcoming: The surrogate potential functions do not take into account the Bayesian (epistemic) uncertainty, and consequently do not perform genuine statistical inference on the unknowns in the MDP. This leads to 'posteriors' that are
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in no way related to the true posteriors in the environment, and acting with those false posteriors leads to poor decision making and agents that require exponential time to solve even small problems [53].
Our contributions can be centered around a new quantity that we uncover as key for inference and control, denoted by Pr., which represents the posterior probability of each state-action pair being visited under the optimal policy.
We reveal that Pr- formalizes from a Bayesian perspective what it means for 'state-action pair to be optimal', an event at the core of the 'RL as inference" framework which had never been properly analyzed.
We establish that knowledge of Pr- is sufficient to derive policy that explores efficiently, as measured by regret (Section 3).
Since computing Pr. is intractable, we propose variational optimization problem that tractably approximates it (Section 4).
We first solve this optimization problem exactly, resulting in new tabular model- algorithm with a guaranteed regret bound (Section 5).
We then solve a variant of this optimization problem using policy-gradient techniques, resulting in a new scalable model-free algorithm (Section 7).
We show that both Thompson sampling [78, 75, 59, 71] and K-learning [47] can be directly linked to Pr.,, thus shedding new light these algorithms and tightly connecting them to variational approach (Section 6).
Our approach has the unique algorithmic feature of adaptively tuning optimism and entropy regularization for each state-action pair, which is empirically beneficial as our experiments on 'DeepSea' and Atari show (Section 8).
2 Preliminaries
We model the RL environment as finite state-action, tine-inhomogeneous MDP given by the tuple M {S, L, P. R. p}. where L is the horizon length, S = S1 U... Sy is the state space L.
with cardinality S = Et= Si where S = |S|]. A is the action space with A possible actions, Pt : St x A + (() denotes the transition dynamics at step 1, R4 St x A A (TR) is the reward function at step and E (SS)) is the initial state distribution. Concretely, the initial state 81 E S is sampled from p. then for steps / = 1..... L the agent is in state 81 E S,, selects action at E A, receives a reward sampled from Ri(st, ar) with mean ri( a) E IR and transitions to the next state S1+1 E S/41 with probability P( 81, a)) An agent following policy my E (AA))) at state at step I selects action a with probability mi(s,) a). The value functions are defined as
Qf (s, a) = a) + Σ Pi(s' (H))),
VT(()) = Σ (s Q) (s,
V = 0,
d'E4411
REA
+
En(s's Pi(s' (i))
VI((s) max Q7 (s. aeA
Vž+1 0.
s'ES1+1
An optimal policy x* satisfies Vi=" (s) (s) for each state and step l. Let { (s) a} be the event that action a is optimal for state at step 1, with ties broken arbitrarily so that only one action is
optimal at each state. Let R2..5A = { S M
be the set of functions S x A + R, for I E [L].
Occupancy measures. We denote the set of occupancy measures (a.k.a. stationary state-action distributions) with respect to the transition dynamics as A(P) = (XER R4SA
~m((s,))=
ΣAH1(s',a') - EP((s s.))
8,a
Note the correspondence between A(P) and the set of policies II= (A(A) 1. II induces A E A(P) such that XB (s. a) denotes the probability of reaching (s. a) at step I under æ. Conversely, any X E A(P) induces x E II given by m/ a) = Ar a)) (s)))a))
11=1 [66]. Any policy
so long as Ea Ae(s, 0; otherwise (s.... can be any distribution, e.g., uniform.
Bayesian RL. We consider the Bayesian view of the RL problem, where the agent has some beliefs about the MDP represented by a distribution & on the space of all MDPs. We use the shorthand notation E. and I& to denote the expectation and probability under é. In the Bayesian view, the mean rewards and transition dynamics P are random variables, and thus so are Q*, V*, n².

---

2.1 Previous Approach to 'RL as Inference'
The popular line of research casting 'RL as inference' is most clearly summarized in the tutorial and review of Levine, 2018 [37]. It embeds the control problem into a graphical model, mirroring the dual relationship between optimal control and inference [81, 34, 68]. As shown in Figure Sa, this approach defines an additional optimality binary random variable denoted by r7 which indicates which state- action at timestep 1 'optimal", i.e. which state-action is visited under the (unknown) optimal policy. In these works the probability of ; is then modeled as proportional to the exponentiated reward.
Approximation 1 (Inference over exponentiated reward [37]. Denoting by r (8, a) the event that state-action pair (s, a) is "optimal' at timestep I, set P (s, a)) exp(ri(s, a))-
Under Approximation 1, the optimality variables become observed variables in the graphical model, over which we can apply standard tools for inference. This approach has the advantage of being mathematically and computationally convenient. In particular, under deterministic dynamics it directly leads to RL algorithms with 'soft' Bellman updates and added entropy regularization, thus recovering the maximum maximum-entropy entropy RL framework [80, 87] and giving natural, albeit heuristic exploration strategy. Many popular algorithms lie within this class [65, 25, 1] and have demonstrated strong empirical performance in domains where efficient exploration is not bottleneck.
Despite its popularity and convenience, the potential function of Approximation ignores epistemic uncertainty [53]. Due to this shortcoming, the inference procedure produces invalid and arbitrarily poor posteriors. It can be shown that the resulting algorithms fail even in basic bandit-like problems (e.g.. [53, Problem IJ). as they underestimate the probability of optimal actions and take actions which have no probability of optimality under the true posterior. This implies that the resulting agents (e.g., Soft Q-learning [25]) can perform poorly in simple domains that require deep exploration [57]. The fact that the 'RL as inference' framework does not perform valid inference on the optimality variables leads us to consider how proper Bayesian inference approach might proceed. This brings us to the first contribution of this manuscript.
3 A Principled Bayesian Inference Approach to RL
In this section, we provide principled Bayesian treatment of statistical inference over 'optimality" variables in an MDP. Although it is the main quantity of interest of the popular 'RL as inference' framework, a rigorous definition of whether state-action pair is optimal has remained elusive. We provide a recursive one below.
Definition (State-action optimality). For any step E [L], state-action (s, St x A we define
(s) = {s| = s).
riti
U ( = ='}, SES
(s, (=())) a},
(5t+) = a'}.
In words, (s) is the random event that state s is reached at step I after executing optimal actions from steps 1 to 100--1, and the event 17 (7, (s,a) a) further requires that the action a is optimal at state s in step l. Equipped with this definition, 'optimality' in an MDP flows both in a backward way (via action optimality x², which can be computed using dynamic programming) and in a forward way (via state-action optimality I*). We illustrate this bidirectional property in the simplified graphical model of Figure 5b (which isolates single trajectory). In general, state-action optimality encapsulates all possible trajectories leading to given state being optimal (and there may be exponentially many of them). Thanks to the MDP structure and Bayes' rule, we show in Lemma that the posterior probability of state-action optimality lies in the space of occupancy measures. To simplify exposition, we first assume that the transition dynamics P are known (only rewards are unknown), and we extend our analysis to unknown P in Section 5.
Lemma 1. For known P, holds that Pr- = (Po (T)) A(P).
The significance of Lemma is that we can readily sample from Pr. with the induced policy
Po (s,
n ((( = Evee Po (T)(s,a') = =a (m) = (+)),
(1)
3

---

Figure I: Pair of MDPs {M+, 3 with uni- form prior @ (2.2). M and .M" only differ through their reward at state $1. resp. +1 and -1. Two actions are available at states $1 to $2-1: 1 exits the chain and moves to an absorb- ing, zero-reward state, and moves right with small negative reward -c.
-
+1 w.p. 0.5 1 0.5. 0.5
81
82
8L
SL
5/2
$/3
Agent starts at 81 (1( a) for a E (4. - (0, 1)
Agent reaches st, > ([(s;, a) for a E {4, ++}
Expected # episodes to reach $L
Policy
Baycs-optimal
(0, 1)
1
Approximation
(0.5, 0.5)
(0.5, 0.5)
(222
(e.... Soft Q-Learning)
Marginal (mt"))
(0.5, 0.5)
(0.5, 0.5)
22(2")
Conditional Ps(x" T
(0.5, 0.5)
(0, 1)
2
(0, 1) w.p. 0.5
Thompson Sampling
(0, 1)
2
(1,0) w.p. 0.5
VAPOR
(0.1)
(0, 1)
1
Table I: Comparison of algorithm performance on MDP in Figure 1. Unprincipled approaches like Soft Q- learning take time exponential in to reach the uncertain reward state. Naively using the marginal posterior probability of action optimality as the policy at each state also requires exponential time, however the policy derived from the posterior probability of state-action optimality Pr- takes consistent actions and is therefore efficient. Similar good performance is achieved by Thompson sampling (implicit approximation of Pr.. Section 6) and VAPOR (explicit approximation Fr.. Section 4).
which is the probability under the posterior that action is optimal state conditioned all actions taken before timestep being optimal. It turns out that this policy explores efficiently, as measured by regret (see Corollary 1). Concretely, and control) can be distilled into a single quantity: Pr.. We use Bayesian inference to compute Pr-- and then use that to derive good control policy. This is principled and consistent Bayesian 'RL as inference" approach. The remaining challenge thus lies in computing rr.. Unfortunately, doing so involves computing several complicated integrals with respect the posterior and is intractable in most cases. In Section 4, we introduce the second contribution of this manuscript, which is a way to approximate Pr. using a computationally tractable variational approach.
have shown that the two facets of RL. (inference
3.1 Instructive Example
To gain intuition on the difference between action optimality (i.e., P (xx)) and state-action optimality (i.e., Pr.), we consider the simple decision problem of Figure 1. Each episode starts in the leftmost state and the agent can traverse a chain of states in order to reach the rightmost state, where the reward is always either +1 or 11 with equal probability. Once the agent reaches the rightmost state will resolve its uncertainty. At each state the agent has the option to move -,, paying a cost of e where eL < 1, move with cost. We see that there only 2 consistent trajectories: either take action I at state $1 (optimal for M ). or repeat actions - to reach &L (optimal for M We detail how selection of algorithms perform on this problem in Table 1.
is worth examining in detail what has gone wrong for the policy that samples according to (T(()) Even if the agent has traveled to the right few times it will exit the chain with probability 0.5 at each new state, which leads to poor exploration. Taking action - a few times and then exiting the chain has zero probability of being optimal under the posterior, so this sequence of actions is inconsistent with the posterior. Conditioning on the event (s) when at state a forces the policy to be consistent with the set of the beliefs that would get the agent state in the first place, which, as we prove later, yields deep exploration. In our chain example, the only belief that takes action + is the one in which the end state has reward +1, so the only consistent policy conditioned on having taken - once is to continue all the way to the end state. The same issue arises in Thompson sampling, where in order achieve consistency the agent samples policy from its posterior and keeps it fixed for the entire episode since resampling at every timestep leads to inefficient exploration [71]. As we shall show in Section 6, Thompson sampling is exactly equivalent sampling from Pr.. In conclusion:
action optimality: state-action optimality:
at (s( .) aq ~ Fa( = [s)(s)) x (s((()))
Poor exploration,
Efficient exploration.

---

4 A Variational Bayesian Approach
Having access to Pr- is sufficient to enable deep exploration, but computing this probability is intractable in general. In this section, we derive variational, i.e., aprimization-basee approach to approximate Pr., In most variational Bayesian approaches [18], the optimization objective find surrogate probability measure that minimizes some dissimilarity metric (e.g., a KL-divergence) from the intractable probability measure of interest. Yet unlike standard variational inference techniques, we cannot minimize the KL-divergence to this distribution as we do not have access to samples. However, we do have downstream control objective. That is to say, we are not simply interested in approximating the distribution, but also in our approximation doing well in the control problem. This insight provides an alternative objective that takes into account the rewards and uncertainties that the agent is likely to encounter. The optimal value function V is a random variable under the beliefs ø. Our next lemma relates the expected value of V under & to our state-action optimality event T
Lemma 2. It holds that
Ex BVT((s)
Σ (P(TT((, (m((. (s) 1,8,
4.1 Information Theoretic Upper Bound
Lemma 2 depends on Pr., but the conditional expectation is not easy to deal with. To handle this, we upper bound each (g a) | r (s. a)] in Lemma 2 using tools from information theory. To simplify the exposition, we consider the following standard sub- Gaussas assumption [70, 61, 47] and we defer to Appendix E.3 the treatment of the general case. We say that X - R is --subb-Gaussin for v > 0 if EExx(e((
EX)) I exp(e2 /2), for all c E IR. Lemma 3. If Ifr((s, a) is or(s, a) ---sub--Coee (as---bb-aaaaa Gaussian under à ffrr E [L] and (s. E E A, then
of (7.
Es (r)(s,a) T7 (s, a)) s Bari(s,a) +
min <1,0))>0
(ss log (og(o((((ssa)) ( log P (L))
= a) to)(s,)
4.2 Optimization Problem
Finally, we combine Lemmas 2 and 3 to reveal a concave function in Pr- that upper bounds the value function objective Es~pEoV (T)).. For any T E RSM and occupancy measure À E A(P), we define the r-weighted entropy of X (summed over steps 1) as H. (A) == - -- Ti a) Ar) a) log Ar a). In the following definition we take division and the square-root to be applied elementwise, and denotes elementwise multiplication. With this we can define the following optimistic value functions
σ²) HA,(),,
Vo(A,T)==1
XT [gor
2T
VA(A)
min Vo(A.T) = =x 000
(3)
TER
Lemma 4. For known P and
r, we have
E Egg E. (s) (Pr-) S max (a(,),
(4)
xEA(P)
VAPOR
where the VAPOR optimization problem concave.
The above optimization problem is our variational objective, the solution of which yiclds an occu- pancy measure that approximates Pr-. We call the approach 'VAPOR', for variational approximation of the posterior probability of optimality in RL. We discuss various properties of the optimization problem in Appendix E (its unconstrained dual problem and message passing interpretation).
Since we are using variational inference a natural question to ask how well our variational solution approximates Pr.. Here we provide a bound quantifying the dissimilarity between IPr. and the solution of the VAPOR optimization problem, according to a weighted KL--divergence, where for any g484 X, X' e A(P) we define KL, (A || X') = Lt.a, T(ss, ())s a) log(Ar(s,a)) a)).
5

---

Lemma 5. Let X solve the VAPOR optimization problem (4) and T" E argmin, (o(*,,) then
kL,- (Pr- || -
(/ (s).
In other words, the (weighted) KL-divergence between Pr- and X is upper bounded by how loose our upper bound in (4) is. In practice however, we care less about a bound on the divergence metric than we do about performance in the control problem. Our next result shows that the variational policy also satisfies strong sub-linear Bayesian regret bound, i.e., the resulting policy performs well.
4.3 Bayesian Regret Analysis
Learning problem. We consider that the agent interacts with the MDP M over (possibly
unknown) number of N episodes. We denote by Fr the sigma-algebra generated by all the history (i.e., sequences of states, actions and rewards) before episode with Fi 0. We let E* [:] E[| Fi). (+)-) = P( Fe). We denote by nf (s, a) the visitation count to (s, a) at step before episode t, and (-V1) == max(", 1). In the Bayesian approach where M is sampled from known prior ø, want to minimize the Bayes regret over T = NL timesteps of an algorithm alg producing policy at each episode i, which is defined as its expected regret under that prior distribution
(ag, T) Σ Bang (+) (s)), (agg T) EM Ralg,,
The VAPOR learning algorithm proceeds as follows: at the beginning of each episode, it solves the VAPOR optimization problem and executes the induced policy. We now show that enjoys sub-linear Bayesian regret bound under the following standard assumption [61, 47, 62].
The mean rewards are bounded in [0, 1] almost surely with independent priors and the reward noise is additive --sub-Gaussiar for constant 0.
Assumption 1.
Assumption implies that the mean rewards are sub-Gaussian under the posterior (see [70, App. D.2]), where we can upper bound the sub-Gaussian parameter of a) S viv + 1)/(m((s, V V1) at the beginning of each episode L.
Theorem 1. For known P and under Assumption it holds that
(VAPOO,, T) S /2 + -1TTSAlog(SA)(( +
log T/L) =
In the above Ô suppresses log factors. The same regret bound holds for the (intractable) algorithm that uses (1) as the policy each episode.
Corollary 1. Denote by algr- the algorithm that produces policies based on Pf. for each episode t using (1). Then, under the same conditions as Theorem we have (algrt & O(TSAT).
4.4 Interpretation VAPOR
Inspecting V (3) reveals that the VAPOR optimization problem is equivalent to solving a two-player zero-sum game between a 'policy' player À E A(P) and a 'temperature' player 7 E R..... The latter finds the tightest that best balances two exploration mechanisms optimism term a² // that augments the expected reward E,r,, and a r-weighted entrupy regularization term. The policy player maximizes the engroiy-regulariized optimistic reward.
per state-action basis: an
The fact that entropy regularization falls out naturally from VAPOR is interesting because the standard 'RL as inference' framework conveniently reveals policy entropy regularization (Section 2.1). which has been widely studied theoretically [45, 20] and empirically for deep RL exploration [42, 26]. The specificity here is that it is with respect to the occupancy measure instead of the policy, and it is adaptively weighted for each state-action pair. This enables us to obtain an 'RL as inference' framework with entropy regularization that explores provably efficiently. Regularizing with the (weighted) entropy of the occupancy measure is harder to implement Section we propose a principled, albeit looser, upper bound of the VAPOR optimization problem that regularizes the optimistic reward with only the (weighted) entropy of the policy, making the resulting objective amenable to online optimization with policy gradients.
practice, therefore in

---

Algorithm 1 VAPOR learning algorithm
For episode = .... do
1. Compute expected rewards E,', transitions E uncertainty measure Zz
2. Solve VAPOR optimization problem X' E ArgmaX V (A) from Equation (3)
3. Execute policy xf( a) o a)) for I = I....,
Extension to Unknown Transition Dynamics
So far have focused on the special case of known transition dynamics P. In this section, we derive a generic reduction from the case of unknown P to known P. which may be of independent interest. We prove that any algorithm that enjoys Bayesian regret bound in the known- P special case can be easily converted into one that enjoys a regret bound for the more challenging unknown- P case. Our analysis relies on the mean rewards being sub- Gaussian under the posterior (which holds e.g., under Assumption 1) and on the following standard assumption [61, 47, 62].
Assumption 2. The transition functions functiion are independent Dirichlet under 6, with parameter a (s, a) e St+1 for each (s, a) E E, x A with Ex 0n(s, s') 2 1.
At a high level, our reduction transfers the uncertainty on the transitions to additional uncertainty on the rewards in the form of carefully defined zero-mean Gaussian noise. extends the reward perturbation idea of the RLSVI algorithm
[62], by leveraging property of Gaussian-Dirichle optimism [60] and deriving a new property of Gaussian sub-Gaussian optimism (Appendix G) which allows to bypass the assumption of binary rewards in {0, 1} from [62, Asm. 3]. Our reduction implies the following 'dominance' property of the expected V* under the transformed and original beliefs.
Lemma 6. Define the mapping T Φ + e that transforms the beliefs & into a distribution â on the same space, with transition dynamics equal EpP P and rewards distributed (Egr, @²) with
(I. 1I2
as) = 3..62 + Eg an(s,,88))
Original belief'
Transformed beliefs
Then it holds that
Mean reward
o-sub-Gaussian
A (Bar, 62)
Ea-pEEVV' S E3
Transitions P Dirichlet(ax)
E&P
Now, let us return to the episodic interaction case and denote by of == -(- Fi) the posterior at the beginning of episode Under Assumptions and can upper bound the uncertainty â' of the transformed posteriors Ø' ( a) s (3.62 + + (L (mf)) a) v 1). This brings us to a key result necessary for a general regret bound.
Lemma 7. Let alg be any procedure that maps posterior beliefs to policies, and denote by BRT (a T) the Bayesian regret of alg where at each episode t = ... the policy and regret are computed by replacing &f with T(Φ') (Lemma 6), then under Assumptions and 2,
B T) < (alg, T).
This tells us that if we have an algorithm with a Bayesian regret bound under known transitions P, then we can convert directly into an algorithm that achieves a regret bound for the case of unknown P. simply by increasing the amount of uncertainty in the posterior of the unknown rewards and replacing the unknown P with its mean when executing the algorithm. We now instantiate this generic reduction to VAPOR in Algorithm 1. Combining Lemma 7 and Theorem I yields the following regret bound.
Theorem 2. Under Assumptions and 2, it holds that BR, (VAPOR, T') < Ö(LVSAT).
The Bayes regret bound in Theorem 2 is within factor of VL of the known information theoretic lower bound [32, 13], up to constant and log terms. It matches the best known bound for K-learning [47] and Thompson sampling [61], under the same set of standard assumptions (see Appendix C). There exists a complementary line of work deriving minimax-optimal regret bounds in the frequentist setting, both in the model-based [3, 41] and model-free [86, 38] cases. We refer to e.g., [21] for discussion on the advantages and disadvantages of the Bayesian and frequentist approaches. Without
7

---

claiming superiority of either, is worth highlighting that compared to frequentist algorithms that tend to be deterministic and ntat-ntatio (i.e., explicitly dependent on the episode number), VAPOR is naturally stochastic and stationary (i.e., independent of the episode number).
6 Connections
TS/PSRL
VAPOR
Sample MDP M and compute TIM
Variationally approximate X x Pr
Thompson Sampling. Thompson sampling (TS) or posterior sampling for RL (PSRL) [78, 75, 59] first samples an environment (i.e, rewards and transition dynamics) from the pos- terior and then computes the optimal policy for this sample to be executed during the episode. Our principled Bayesian inference approach to RI. uncovers an alternative view of TS which deepens our understanding of this popular algorithm. The next lemma shows that TS implicitly approximates Pr. by sampling, thus tightly connecting it to VAPOR's explicit approximation of Pr..
P'r approx.
T8 Pr. R = Pr.
and compute x²
Explicit optimism
Exploration mcchanism
Stochastic optimism
+ -ntropp regularization
Lemma 8. Let XS be the occupancy measure of the TS policy, it holds that BE[AT)] Pr-
Plugging this observation into Lemma 4 and retracing the proof of Theorem 2 immediately yields regret bounds for TS matching that of VAPOR. The explicit variational approximation of IPr- by VAPOR has several advantages over the implicit sampling-
approximation of IPr- by TS: Having direct (approximate) access this probability can be desirable in some practical applica- tions, for example to ensure safety constraints or to allocate budgets.
TS suffers linear regret in the multi-agent and constrained cases [52], while we expect suitable modifications of VAPOR to be able to handle these cases, suggested in the multi-armed bandit setting [51].
The VAPOR optimization problem can naturally extend to parameterizing the occupancy measure to be in certain family (e.g., linear in some basis).
The objective we use in VAPOR is differentiable, opening the door to differentiable computing architectures such as deep neural network. In contrast, performing TS requires to maintain an explicit model over MDP parameters [59], which becomes prohibitively expensive as the MDP becomes large. To alleviate this computational challenge of TS, some works have focused on cheaply generating approximate posterior samples [57, 55, 62, 54], but it is not yet clear if this approach is better than the variational approximation we propose.
K-learning. K-learning [47] endows the agent with risk-seeking exponential utility function and enjoys the same regret bound as Theorem 2. Its update rule is similar to soft Q-learning [19, 25, 44, 22], which emerges from inference under Approximation 1 [37]. Although soft Q- learning ignores epistemic uncertainty and thus suffers linear regret [53], K-learning learns a scalar temperature parameter which balances both an optimistic reward and a policy entropy regularization term. In contrast, VAPOR naturally produces a separate risk- risk-seeking parameter for each state tiate-action. This enables a fine-grained control of the ppploration-exploiaaaat of the state-action space, which can make large difference in practice. In the multi-armed bandit case was shown that K-learning and VAPOR coincide when VAPOR is constrained have all temperature parameters (denoted r) equal [51]. It can be shown (see Appendix 1.12) that the same observation holds in the more general MDP case, up to additional entropic terms added to the K-learning 'soft' value functions, which only contribute small constant to the regret analysis. This sheds new light on K-learning as a variational approximation of our probabilistic inference framework with the additional constraint that all "temperature' parameters equal.
trade-off depending on the region
Maximum Entropy Exploration. A recent line of work called maximum entropy exploration suggests that in the absence of reward the agent should cover the state-action space as uniformly as possible by solving a maximum entropy problem over occupancy measures maXXEA(P) H(A) [29, 9, 85, 79], where H denotes the entropy summed over steps I. VAPOR can thus be interpreted as regularizing a reward-driven objective with maximum entropy exploration term, that is weighted with vanishing temperatures. other words, the principle of (weighted) maximum-entropy explo- ration can be derived by considering variational approximation to Bayesian state-action optimality.
maximummentrropy
8

---

7 A Policy-Gradient Approximation
Up this point, we instantiated our new Bayesian 'RL. as inference' approach with tabular, model- based algorithm that exactly solves the variational optimization problem and has a guaranteed regret bound (Algorithm I). In this section, we derive a principled, albeit looser, upper-bound approximation of the variational optimization problem, which can be solved using policy-gradient techniques by representing the policy using a deep neural network. This will yield a scalable, model-free algorithm that we call VAPOR-lite.
Denoting by f= the stationary state distribution of policy τ, note the relation (7 a) Ti(8, a) (s). The regularization term of VAPOR can thus be decomposed in a (weighted) pol- icy entropy regularization term and a (weighted) stationary state distribution entropy term, the latter of which is challenging to optimize in high-dimensional spaces [29, 36, 43]. In light of this, we introduce the following VAPOR-lite alternative optimization problem
max
[s) 1,a
Σ TI (s.) + +0((s, a) + Harts,)(((ss
(5)
TEII
where we define the weighted policy entropy (a. (T)(S .)) = 0i(s, ()m a) log (s a). Akin to policy-gradient methods, VAPOR-lite now optimizes over the policies which can be parametrized by a neural network. It depends on an uncertainty signal Ô which can also be parametrized by neural network (e.g., an ensemble of reward predictors, as consider in our experiments in Section 8). Compared to VAPOR, VAPOR-lite accounts for a weaker notion of weighted entropy regularization (i.e., in the policy space instead of the occupancy- which allows to solve the objective using selicy-gradient techniques. For simplicity it also sets the temperatures T to the uncertainties & instead of minimizing for the optimal ones. Importantly, VAPOR-1ite remains a principled approach. We indeed prove the following relevant properties of VAPOR-lite in Appendix H: (i) although the problem is no longer concave in π, solving it in the space of occupancy measures À remains a computationally tractable, concave optimization problem, (ii) VAPOR- upper bounds the VAPOR objective (up to a multiplicative factor in the uncertainty measure and a negligible additive bias), and (iii) it yields the same OLLVSAT) regret bound as VAPOR for a careful schedule of uncertainty measures ō over episodes.
space),
Essentially, VAPOR-lite endows a an mnceraainty-wiigheed policy entropy regularization. The latter exploration mechanism is novel and has an appealing interpretation: Unlike standard policy entropy regularization, it adaptively accounts for epistemic uncertainty, by eliminating actions from the entropy term where the agent has low uncertainty for each given state. In the limit of â - 0 (i.e., no uncertainty), the regularization of VAPOR-lite vanishes and we recover the original policy-gradient objective.
agent with (i) an uncertainty reward bonus and (ii)
8 Numerical Experiments
GridWorld. We first study empirically how well VAPOR approximates Fr.. Since E[ATS]= = Pr.. we estimate the latter by averaging over 1 1000 samples of the (random) TS occupancy measure (we denote it by XTS..). We design simple 10 x 10 GridWorld MDPs with four cardinal actions, known dynamics and randomly generated reward. Figure suggests that VAPOR and the TS average output similar approximations of Pr., thus showing the accuracy of our variational approximation in this domain. Unlike TS which requires estimating with many samples, VAPOR approximates Pr- by only solving a single convex optimization problem.
DeepSea. We now study the learning performance of the VAPOR Algorithm in the hard-exploration environment of DeepSea [62]. In this L x L grid MDP, the agent starts at the top-left cell and must reach the lower-right cell. It can move left or right, always descending to the row below. Going left yields no reward, while going right incurs small cost of LLO The bottom-right cell yields a reward of 1, so that the optimal policy is to always go right. Local dithering (e.g., Soft Q-learning e-greedy) takes time exponential in L, so the agent must perform deep exploration to reach the goal. Figure shows the time required to 'solve' the problem as a function of the depth L, averaged over 10 seeds. The 'time to solve' is defined as the first episode where the rewarding state has been found at least in 10% of the episodes so far [47]. We compare VAPOR to TS /PRII. [59], K-learning [47] and variant of RLSVI [62] that runs PSRL under the transformed posteriors of Lemma 6. (Several

---

Random reward
Rondom reward send
Rondom reward
1e0
163
VAPOR
TS average
VAPOR
15 average
VAPOR
average
Figure 2: seeds randomly generated reward means noises in GridWorld, visualization
limestep-averaged stationary state distribution (i.e., L --- Et, de(s, a)) for vwron (left) and X (right).
5000
24
12
1000
Nodor Tumann comaacoeeooadddddoommooo
500
100
Eploodes
Replay Actondrilic BAC entirpyy
K-leernigg
TS/PSRL
VAPOR-Ite
VAPOR
10
20
30
40
50
depth
Figure 4: Median human normalized score across 57 Atari games (with standard errors across seeds).
Figure Learning time on DeepSea
optimistic methods like UCBVI [3] or Optimistic Q-learning [32] were additionally compared by [47] but they performed worse.) We see that VAPOR achieves the lowest learning time as increases, thus displaying its ability to perform deep exploration.
Atari. Finally, we investigate the performance of VAPOR-lita on the Atari benchmark [5]. We consider replay-basee based actor-critic agent with V-trace off policy corrections [15] and an actor-learner decomposition [30] (see Appendix for the full experimental details). We compare this agent without and with added fixed policy entropy regularization commonly used [83, 42], to the same agent with stress that unlike simply adding entropy regularization, which leads to local dithering and suffers linear regret, VAPOR-lite relies on a principled approach of casting RI as Bayesian inference. Figure shows the performance advantage of augmenting a policy-gradieg Atari. It reaches the peak performance of the replay actor-critic agent (resp. with entropy regularization) in about 2x (resp. 1.5x) fewer environment frames, for essentially the same computational cost. This advantage comes from the fact that VAPOR- AAP leads to deep exploration, which results in finding higher rewarding states and better cumulative performance. In ablation in Appendix we illustrate the isolated benefits of tuning entropy regularization a per state-action basis with VAPOR-lite compared to tuning a single scalar for entropy regularization [49]. Our promising empirical results suggest that further gains could come from deriving more accurate practical approximation of VAPOR.
VAPOR-lis- objective.
agent with VAPOR-lite
Conclusion
RL a statistical inference problem wrapped control problem. In this paper, we demonstrated that single quantity can be used to handle both aspects of the problem - the posterior probability of each state-action pair being visited under the optimal policy, Pr.. We can perform Bayesian inference to compute this, and then use it to generate a control policy that performs efficient exploration. This a coherent and principled approach 'RL as inference', rather than the heuristic approaches in prior work which could not compute valid posteriors. Unfortunately, computing Pr is intractable in practice so we derived variational approximation that we showed also explores efficiently. We concluded with some numerical experiments showing improved performance in the challenging 'DeepSea' unit test, as well as on the Atari suite. We discuss some limitations of our work and directions for future investigation in Appendix D.
10

---

References
[1] A. Abdolmaleki, J. T. Springenberg, Tassa, R. Munos, N. Heess, and M. Riedmiller, Maxi- mum posteriori policy optimisation. arXiv preprint arXiv: arXiv:/806.06920, 2018.
[2] Auer. Using confidence bounds for exploiaation-explrraiin trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
[3] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning, In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[4] M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
[5] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling, The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
[6] P. Boyd and Vandenberghe. Corvex optimization. Cambridge university press, 2004.
[7] Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. arXiv preprint arXiv: 12894, 2018.
[8] C. Bälcäu. Weighted entropic perturbation for linear programming. Analele Universitaji Bucureşti. dnltematiiã-Ifformatiii 55, 01 2006.
[9] W. C. Cheung. Exploration-exploinai trade-off in reinforcement learning online markov decision processes with global concave rewards. arXiv preprint arXiv:1905.06466 2019.
[10] T. M. Cover and J. A. Thomas. Information theory and statistics. theory, 1(1):279-33)) 335, 1991.
Elements of information
[11] S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[12] A. Domahidi, E. Chu, and Boyd. ECOS: An SOCP solver for embedded systems. In European Control Conference (ECC), pages 3071-3076, 2013.
[13] O. D. Domingues, Ménard, Kaufmann, and M. Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
[14] V. Dwaracherla, Z. Wen, I. Osband, X. Lu, S. M. Asghari, and B. Van Roy. Ensembles for uncertainty estimation: Benefits of prior functions and bootstrapping. arXiv preprint arXiv:2206.03633, 2022.
[15] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International conference on machine learning. pages 1407-1416. PMLR, 2018.
[16] S.-C. Fang and H.-S. J. Tsao. Linear programming with entropic perturbation. Zeitschrift für Operations Research, 1712):171-186, 1993.
[17] M. Fellows, Mahajan, T. G. Rudner, and S. Whiteson. Virel: variational inference framework for reinforcement learning. Advances in neural information processing systems, 32, 2019.
[18] C. W. Fox and S. Roherts. tutorial on variational bayesian inference. Artificial intelligence review, 38:85-95, 2012.
[19] R. Fox, A. Pakman, and N. Tishby. Taming the noise reinforcement learning via soft updates. arXiv preprint arXiv:1512.08560 2015.

---

[20] M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning. pages 2160-2169. PMLR, 2019.
[21] M. Ghavanzadeh, S. Mannor, J. Pineau, A. Tamar, et al. Bayesian reinforcement learning: A survey, Foundations and Trends@ in Machine Learning, (15-6):359-448) 2015.
[22] Grau-Moya, Leibfried, and Vranex. Soft Q-learning with nutual-information regulariza- tion. In International conference on learning representations, 2019.
[23] R. M. Gray. Entropy and information theory. Springer Science & Business Media, 2011.
[24] D. Grytskyy, J. Ramírez-Ruiz, and R. Moreno-Bote general markov decision process formal- ism for action-state eetropy-regularized reward maximization. arXiv preprint arXiv:2302.01099; 2023.
[25] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine. Reinforcement learning with deep energy-based policies. In International conference on machine learning, pages 1352-1361. PMLR, 2017.
[26] T. Haarnoja, A. Zhou, P. Abbeel, and Levine. Soft actor-critie: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[27] Han and Y. Sung. Diversity actor-critic: Sample-aware entropy regularization for sample- efficient exploration. In International Conference on Machine Learning, pages 4018 -4299. PMLR, 2021.
[28] B. Hao and T. Lattimore. Regret bounds for information-dirrcteed preprint arXiv:2206. 04640, 2022.
renprdddddeeeeeeeeienneeeeeeeeee reinforcement learning. arXiv
[29] E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In International Conference Machine Learning, pages 2681-2691. PMLR, 2019.
[30] M. Hessel, M. Kroiss, A. Clark, I. Kemaev, J. Quan, T. Keck, F. Viola, and H. van Hasselt. Podracer architectures for scalable reinforcement learning. arXiv preprint arXiv:2104.06272. 2021.
[31] M. Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pages 435. PMLR, 2013.
[32] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[33] H. Juergensen and D. E. Matthews. Entropy and higher moments of information. Journal of Universal Computer Science, 16(5):749-794, 2010.
[34] H. J. Kappen, Gómez, and M. Opper. Optimal control as graphical model inference problem. Machine learning, 87:159-182, 2012.
[35] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49:209-232, 2002.
[36] L. Lee, B. Eysenbach, E. Parisotto, E. Xing, S. Levine, and R. Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv:1906. 05274, 2019.
[37] S. Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: 1805.0000000009 2018.
[38] G. Li, L. Shi, Y. Chen, Y. Gu, and Y. Chi. Breaking the sample complexity barrier to regret- optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762-17776. 2021.
[39] X. Lu, Van Roy, Dwaracherla, M. Ibrahimi, I. Oshand, Wen, et Reinforcement learning, bit by bit. Foundations and Trends@ in Machine Learning, 16(6):733-88) 865, 2023.
12

---

[40] C. E. Luis, A. G. Bottero, J. Vinogradska, F. Berkenkamp, and J. Peters. Model-based uncertainty in value functions. arXiv preprint arXiv:2302.12526, 2023.
[41] Ménard, O. D. Domingues, X. Shang, and M. Valko. UCB momentum Q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7609-7618. PMLR, 2021.
[42] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning, In International conference machine learning, pages 1928-1937. PMLR, 2016.
[43] M. Mutti, L. Pratissoli, and M. Restelli. aask-agnostic exploration via policy gradient of a non non-parametric state entropy estimate. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 9028-9036, 9036, 2021.
[44] O. Nachum, M. Norouzi, K. Xu, and D. Schuurmans. Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information Processing Systems, pages 2772-2782, 2017.
[45] G. Neu, A. Jonsson, and V. Gómez. A unified view of entropy-reeularized markov decision processes. arXiv preprint arXiv: urXiv:/775.0770 1705.07798, 2017.
[46] B. O'Donoghue. Operator splitting for a homogeneous embedding of the linear complementarity problem. SIAM Journal on Optimization, 31 31())1999-20033, 2021.
[47] B. O' O'Donoguue. Variational Bayesian reinforcement Icarning with regret bounds. Advances in Neural Information Processing Systems, 34:28208 282211, 2021.
[48] B. O' O'Donoghue. On the connection between Bregman divergence and value in regularized markov decision processes. arXiv preprint arXiv:2210./211 2022.
[49] B. O' O'Donoguue. Efficient exploration via epistemic-risk-seekinn policy optimization. arXiv preprint arXiv:2302.09339, 2023.
[50] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 16963):1422-168, June 2016.
[51] B. O' O'Donoguue and T. Lattimore. Variational Bayesian optimistic sampling. Advances in Neural Information Processing Systems, 34: 14:12507-12519, 2021.
[52] B. O' O'Donoghue, T. Lattimore, and I. Osband. Matrix games with bandit feedback. In Uncertainty in Artificial Intelligence, pages 279-289. PMLR, 2021.
[53] B. O'Donoghue, Osband, and C. Ionescu. Making sense of reinforcement learning and probabilistic inference. In International Conference on Learning Representations, 2020.
[54] B. O'Donoghue, I. Osband, R. Munos, and V. Mnih. The uncertainty Bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845, 2018.
[55] I. Osband. Deep Exploration via Randomized Value Functions. PhD thesis, Stanford University, 2016.
[56] Osband, Aslanides, and A. Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
[57] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems, pages 0026-4034, 2016.
[58] Oshand, Doron, M. Hessel, J. Aslanides, E. Sezener, A. Saraiva, McKinney, Lattimoree, C. Szepesvari, S. Singh, et al. Behaviour suite for reinforcement learning. arXiv preprint arXiv: 03568, 2019.
[59] Osband, Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling, Advances in Neural Information Processing Systems, 26, 2013.
13

---

[60] I. Osband and B. Van Roy. Gaussian-dirichle posterior dominance in sequential learning. arXiv preprint arXiv: 170.. 04126, 2017.
[61] I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pages 2701-2710. PMLR, 2017.
[62] I. Osband, B. Van Roy, J. Russo, and Z. Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20:1-62. 2019.
[63] G. Ostrovski, M. G. Bellemare, A. Oord, and R. Munos. Count-based exploration with neural density models. In International conference on machine learning, pages 2721-2730. PMLR, 2017.
[64] D. Pathak, P. Agrawal, A. Efros, and Darrell. Curiosity-driven exploration by self- supervised prediction. In International conference on machine learning, pages 2778-2787. PMLR, 2017.
[65] Peters, K. Mulling, and Y. Altun. Relative entropy policy search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 1607-1612, 2010.
[66] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[67] Qian, R. Fruit, M. Pirotta, and A. Lazaric. Concentration inequalities for multinoulli random variables. arXiv preprint arXiv:2001.11999 2020.
[68] K. Rawlik, M. Toussaint, and S. Vijayakumar. On stochastic optimal control and reinforcement learning by approximate inference. Proceedings of Robotics: Science and Systems VIII, 2012.
[69] D. Russo and B. Van Roy. Learning to optimize via information-directed sampling. Advances in Neural Information Processing Systems, 27, 2014.
[70] D. Russo and B. Van Roy. An information-thherrtiic analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):4442-2471 2016.
[71] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[72] T. Schaul, J. Quan, Antonoglou, and D. Silver. Prioritized experience replay. arXiv preprint 1rXiv:1511.05952 2015.
[73] M. J. Schervish. Theory of statistics. Springer Science & Business Media, 2012.
[74] S. A. Serrano. Algorithms for unsymmetric cone optimization and implementation for problems with the exponential cone. PhD thesis, Stanford University, 2015.
[75] M. Strens. A bayesian framework for reinforcement learning. ICML, volume 2000, pages 943-950. 2000.
[76] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[77] J. Tarbouricch and A. Lazaric. Active exploration in markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 974-982. PMLR, 2019.
[78] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4):285-29 1933.
[79] D. Tiapkin, D. Belomestny, D. Calandriello, E. Moulines, R. Munos, A. Naumov, P. Perrault, Tang, M. Valko, and Menard. Fast rates for maximum entropy exploration. arXiv preprint arXiv:2303.08059, 2023.
[80] E. Todorov. Linearly-solvabll markov decision problems. Advances in neural information processing systems, 19, 2006.
[81] E. Todorov.
Efficient computation of optimal actions. Proceedings of the national academy of sciences, 146(2)):1147811 11483, 2009.
14

---

[82] M. J. Wainwright, M. I. Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2))1-305, 2008.
[83] R. J. Williams and J. Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-26,, 1991.
[84] H. Yu, H. Zhang, and W. Xu. Do you need the entropy reward (in practice)? arXiv preprint arXiv:2201. 12434, 2022.
[85] T. 7ahavy, B. O'Donoghue, G. Desjardins, and S. Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 34:25746-25759, 2021.
[86] Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model- free reinforcement learning via reference- advantage decomposition. Advances in Neural Information Processing Systems, 33:15198- 15207, 2020.
[87] B. D. Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entopy. Carnegie Mellon University, 2010.
15

---

Appendix
Table of Contents
Graphical Models
17
B Algorithmic Connections 1
C Assumptions
18
D Limitations
19
E Properties of the VAPOR Optimization Problem
19
E.1
Dual Problem the VAPOR Optimization Problem
19
Message Passing View the VAPOR Optimization Problem
................................
F
Proofs
21
E.1
Proof of Lemma
21
F2
Proof of Lemma 2
21
E3
Proof of Lemma
22
E4
Proof of Lemma
23
E5
VAPOR without the Sub-Gaussian Assumption
23
Proof Lemma
24
E7
Proof of Theorem and Corollary
25
F8
Proof of Lemma 6
26
R9
Proof of Lemma 7
28
E10
Proof of Theorem 2
29
F11 Proof of Lemma
29
R12 Connection between K-learning and VAPOR
30
G Gaussian Sub-Gaussian Stochastic Optimism
31
H VAPOR-lite Analysis
33
Experimental Details
35
I.1
Reward-Free GridWorld
35
................................
1.2
DeepSea (tabular)
35
1.3 DeepSea (neural network)
1.4
Atari
36
16

---

T
F2
F
r
T1
3
T
T1
2
T4
Q
Q
Q
Q4
a
a²
a3
a4
a1
a2
a3
a4
S
22
S3
S4
S2
S3
S4
F1
r2
F3
14
F1
r2
r3
I4
(a) graphical model of the standard 'RI as inference' framework [37]
(b) graphical model for principled Bayesian 'RL as inference'
Figure 5: (a) In the standard 'RI. inference' framework, the binary random variables' of state-action optimality I independent and obxerved, equal with probability proportional to the exponentiated reward. i.e. P(T; 1) & exp(r:). This assumption is arbitrary and ignores the role of uncertainty and exploration. (b) In our model, only rewards r are observed, with unobserved binary optimality variables I and unobserved optimal values Q* Q depends on current reward ri and future Q and determines action optimality कं. Iř depends prior state-action optimality Tf-1 and current action optimality कं. 'Optimality' thus propagates both a backward way (via Q and a forward way (via Tī), Refraining from any modeling assumption on T' we derive variational approximation of posterior probability I which yields an algorithm that explores efficiently.
A Graphical Models
We illustrate in Figure 5 the graphical models representing the standard' 'RL as inference' framework [37] and our principled, Bayesian 'RL inference' framework. For ease of presentation, we consider here simplified representation where we isolate a single trajectory (s), ai,..., .,. 84, Q4) and consider that I does encompass the randomness in the transition dynamics (which is e.g., the case for deterministic dynamics).
'There exist other approaches the 'RL inference' perspective, such the VIREL framework [17]. that provide alternative benefits yet do not offer any principled guarantees either. "In the main text, we use the terminology of events but note that events can be seen as binary random variables by taking the indicator function of the event.
17

---

VAPOR-lite
upper bound
VAPOR
a)( -
K-learning, ERSAC
variational
P
IDS V-IDS
r
sampling
TS
appronimate
RVFs, RLSVI
(PSRL)
Figure 6: VAPOR an explicit, variational approximation of Prr., while Thompson sampling (TS) implicitly approximates Pr- by sampling, similarly to TS approximations Randomized value functions (RVFs), RLSVT [62]. A special case of VAPOR with equal temperatures approximately recovers K-lcarning and ERSAC [49]. We conjecture that there also exist connections between r' and information-thcorcie approaches such as information-directed sampling (IDS), variance-IDS (V-IDS) [69, 28, 39].
B Algorithmic Connections to 1**
Figure 6 illustrates how numerous exploration algorithms can be linked to r". This sheds new light on existing algorithms, tightly connects them our variational approach, and unifies these approaches within our principled Bayesian framework.
C Assumptions
this section, we review and discuss the assumptions made throughout the paper. We stress that these assumptions are not required computationally for our variational Bayesian approach, but only for the analysis to obtain VAPOR's regret bound (Theorem 2). These are:
(A) Layered, tume-inhomoooneous MDP,
(B) The reward noise is additive Sab--aasssian and the mean rewards are bounded almost surely with independent priors,
(C) The prior over transition functions independent Dirichlet.
(A) This assumption is nos-restrie in the sense that any finite-horizon MDP with cycles can be transformed into equivalent MDP without cycles by adding timestep variable E [L] to the state space (picking up additional factor of VL in the regret bound). It implies the transition function and the value function at the next state are conditionally independent, which is technical property that simplifies the regret analysis.
(B) The uab-Gaussian assumption is standard in the literature and arises commonly in practice. For instance, it holds in any environment with bounded rewards (e.g.. DeepSea, Atari). In Appendix F.3 (see Lemma 11) we extend Lemma 3 to the general case, and we refer to Appendix E,5 for the resulting VAPOR optimization problem (this would give generic regret bound for the VAPOR learning algorithm which would depend on how fast the posteriors concentrate).
(C) The Dirichlet prior over the transition functions is the canonical prior for transitions in Bayesian RL, see [21]. This because visiting a state-action pair simply increments by the appropriate entry of the Dirichlet vector note the ease of the update because the Dirichlet is the conjugate prior of categorical distribution (which models transition probabilities of wtw.reteestatttatio----aaae
Note that we make the same assumptions as existing state-of-the-ar Bayesian regret analyses, includ- ing PSRL [61]'. K-learning [47]. RLSVI [62]. To the best of our knowledge, an open question how to obtain an algorithm with a Ó(L Bayes regret bound without these assumptions.
"W point out that [61] originally considers time- homogeoomgnn dynamics but there a known mistake in the regret analysis, specifically in Lemma 3. We refer to e.g., these tutorial slides (see footnote of slide 65/91) and [67] for details. This issue be fixed by assuming inhomogeneous dynamics.
18

---

D Limitations
We now discuss some limitations of our work, which constitute relevant directions for future investi- gation.
The VAPOR convex optimization problem grows with L, A. Although large-scale exponential cone solvers exist that can handle this type of problem, it does not immediately lend itself to an online approximation.
The regret guarantee of VAPOR relies Assumptions 1 and 2 which, although standard (Ap- pendix C), can be strong and would be relevant to (partly) relax them.
VAPOR- -e makes some upper-bound approximations of our variational optimization problem to policy-gradient techniques, and there may be tighter way to approximate VAPOR in the case where the policy is parameterized using a deep neural network that is updated using online stochastic gradients.
E Properties of the VAPOR Optimization Problem
The VAPOR optimization problem an exponential cone program that can solved efficiently using modern optimization methods [50, 12, 74, 46]. In Appendix 1, show that its dual is convex optimization problem that is unconstrained in a 'value' variable and a 'temperature" variable. In Appendix E.2, relate VAPOR message passing, popular technique to perform inference in graphical models [82], by showing that VAPOR can be cast as passing some forward and backward messages back and forth.
E.1 Dual Problem of the VAPOR Optimization Problem
We derive the dual problem of the VAPOR optimization problem (4) and show that convex optimization problem in 'value" variable V 1R == {IRSI Ji and a "temperature' variable T E g..AA Even though the 'primal' admits flow constraints in X, this dual is unconstrained in (the only constraint is the non-negativity of T). In the case of unknown P (Section 5), the dual is the same as in Lemma except that replaced by E&P and the uncertainty a replaced by ō.
Lemma 9, The X E A(P) solving the VAPOR optimization problem (4) is unique and satisfies
(
() -1).
((s exp
where define the 'advantage" function
( Esri(s,a) + (s,
+ Pils Pi(s' (s)) (s)
(T,
and where V*, minimize the (convex) dual function
min VERLS TER
min
Ee(s)((s)) +
Σ a(s,a)exp Lsaa
(0rmuls,a)-1)
(6)
7(8,
The induced policy x² is uniquely defined as
Ayr (10,==((8.a)
exp
(1,a)
ni (8, a) En exp
Pyter1laa00 (s.a')
if the denominator is positive, otherwise nī (s. can be any distribution.
Proof. The proof follows from applying the method of Lagrange multipliers the VAPOR optimiza- tion problem using the definition of V in (3). Derivations of dual problems of related optimization problems in the space occupancy measures can found in egg., [65, 24]. Note that for fixed temperature function E RR-S4, VAPOR is an instance of linear programming with weighted entropic perturbation, which is class optimization problems shown to admit unconstrained convex dual [8, 16].
19

---

Algorithm 2 Trank-Wolfe algorithm for the VAPOR optimization problem (Lemma 10)
Require:
Accuracy level & > 0
Set the smoothing parameter 8 = =
Define (A) == Et,s,a >1(5,a) [ a) -(loo)/2(((/(( 5]
Set the number of iterations K (a (S)())))))
Initialize any ( E A
for iterations k 1,2...... K do
Backward message pass: Compute the optimal policy x(*-1) for the reward VV3 (A((-1))))
Forward message pass: Compute d(k-1) the stationary state distribution induced by x (kk-1), i.e.
at (s) =(s),
d (s") :0)=xx Σ Piss |s, a) (K- 10 as)
"ss
8,a
Combine: Compute for step size 7/ =
2 K+I
the occupancy measure
x (s, a) = -11- 7m) (
(s, n) + n ())
end for return A(K)
E.2 Message Passing View of the VAPOR Optimization Problem
Message passing is popular technique perform inference in graphical models [82]. In fact, as shown in [37, Section 2.3], the standard 'RL as inference' framework (Section 2.1) can recover the optimal policy using standard sum-product message passing, relying on single backward message pass. While VAPOR does not have such a simplified derivation, the next lemma shows that it can be cast as passing some forward and backward messages back and forth. In this view, a backward message amounts to computing the optimal policy for a given reward (via backward induction), and forward message amounts to computing the associated stationary state distribution (via the flow equations). This view stems from iteratively solving VAPOR using the Frank- Wolfe (a..a. conditional gradient) algorithm, where an update is equivalent to solving an MDP [29, 77, 85].
Lemma 10. For any accuracy& e >> O, there exist pSly(S, A, L, 6 E1 passes they oulput a MP E A(P) with maxXeA(P) V^(A) - Vo (XMP))
messages such that after
Proof. We consider in Algorithm 2 the Frank- Wolfe algorithm applied to maximizing the smoothed proxy Va over X E A (throughout the proof we write A A(P) and omit the dependence on the beliefs o for ease of notation). Each iteration represents one forward-backward message pass: the backward message computes the optimal policy for the reward given by the gradient of the objective Vs evaluated at the current iterate (via backward induction). while the forward message computes the associated stationary state distribution (via the flow equations). Note that the chosen number of iterations K is polynomial in the inverse of the accuracy level E- the maximum uncertainty Tmax maxi,,,a (s, a) and the MDP parameters L, S, A. To prove the e-convergence in the original objective V. we decompose
V(A*) - (()( = V(X*)- max (A + max V₂(A) - 13((4 + (o(((K)) - ((2(K)) AEλ
AEA
< <(**) Vo(A*)
+
max Va(A) - V)(A(K)) + (2(A())) - V(A(K)))
AEA
2
@ and @ can be bounded using the fact that for any X E A, Va(A) - VV() Iا T L.SA. @ can be bounded from the Wolfe convergence rate for smooth objective functions [31], since the proxy V is Cs-shooth by construction, with Cs 0(amax0-4)) As a result, @ < M5/ (KK/ + 2). where Ms is the curvature constant of Vs over A, with Ms 5 C.s diam (A), where diam (A) < 2L.
Therefore, choosing d = e/(omax LSA) and K- (omaxLe-1) -I) gives
V(A*) ((A(K)) s 0( (0 LSA0
mmax L
O(e).
8+K
20

---

Proofs
F.1
Proof of Lemma
Lemma 1. For known P, it holds that Pr- = (Po (T7) e A(P)
Proof. We omit the dependence on the beliefs for ease of notation. At the initial step,
P ((T a)) = P (fs1 = 3} n (T)(s) = a}) = p(s) (x) = a), and from Bayes' rule and the fact that assumed known, we have the recursive equation P (Ti+1(s',a') P (Ti+1 (m4 =
(r a' ( P (Tin(ss))
= =P(sL1(s))= a' (s')) Σ ( = =
= =P(ri=((5)) a' Titr(s')) Σ P ((s = [((ss.)) (T74))
=P(Fi=((8)= o' (+))
Piss' Σ P((s' I (T)
Summing (7) over implies the non-negativity and flow conservation properties of Pr..
Moreover, when Ev'e P (s)(),))) > 0, it holds that
((T)(s,))
(x) (f())) EvEA (TT(,a''))
which corresponds to (1).
F.2
Proof of Lemma 2
Lemma 2. It holds that
V/ = Σ PT (r((s,) [s))
1,8.0
Proof. Denote by Z* the random variable of the total reward accumulated along single rollout of the optimal policy π², and let (s) be the total reward accumulated by π from state at layer and Z7 (s, a) be the total reward accumulated by nT" from state at layer after taking action We can write the total reward accumulated as
=== Σ (s) =) Σ (T)))
Now for arbitrary E (I,...,, b- 1}.
Σ (+)0 Σ ((s (1(76)))
s,a
[7((s)))
s.a
Σ [(sssa) + Σ (1T7(s Σ
3,
Σ
+ Σ (()()))))))))))
and unrolling we obtain
Z' = Σ [((s,))
1,3,a
21

---

Denoting by F, the sigma-algebes generated by r, it holds from the tower property of conditional expectation that
E.g [ [F]] Eolnsss.))
Therefore it holds that
Bgn Es = Σ
Es (T((.))
1,8,
Now note that
E [=lr(s.a))((7((5.))
rPo(m(s,a) (
a) [F(ss.)))P(((((..)
Putting it all together,
B Be V*)
Σ P.(Ti(s.))R ())
1,8,a
F.3 Proof Lemma
We prove in Lemma 11 generalization of Lemma 3 that does not rely the assumption of a- sub-Gaussian mean rewards. builds on the Donsker- Varadhan representation [23, 70, 69, 28] (Proposition 1), see also [51, Theorem 1]. We denote by KT( || .) the Kullback-Leibler divergence, by Vx IR + the cumulant generating function of random variable X EX and by f TR R the convex conjugate of function R + IR, i.e.,
Donsker-Varadhan
V x (B) = log (exx((((( EX)),
(v( sup f(x)}
=ER
Lemma 11. Let Ω + R be random variable on (S.F, satisfying X E L1 such that the interior of the domain of V is non-empty, and let B E F be event with PBB) > 0. Then."
X
B S EX + (V*)) (K E B) P(X e )))
S EX
+ (V -Vx (- log P(B)).
Proof. Applying Proposition P = P(X E B) gives
A(X EX) for arbitrary À E R4 with the choices IP(X E E.
KL(P(X E B) P( EP)
sup {XE -EX) B - ElexpexpAoo X(X EX)]
XER sup {X(E[X] B EX) xx()))
XER
(X B EX).
by definition of V x the cumulant generating function of - EX and by definition of the convex conjugate of T x which satisfies (v) supxzo (Ny V xA Since V is strictly increasing, its inverse V -1 is also strictly increasing, so
E[X B - EX < (V*) (KL - B) | P(X E .)).
which proves the first inequality. We now derive the second inequality. Note the definition of the KL divergence
KL / log
dP dQ
d.P
If Vx 0. then take -1 0.
22

---

where dP dQ
is the Radon-Nikodym derivative of P with respect to Q. We can then write
dP(X E. B)
KL(P(X E. B) -
log
dP(X E. B)
|
dP(XE)
P(X 11))
(B)
log
dP - E.
PP(X E.)
P(B X E.)
@
log
dP EEXEE11 |
P(B)
log P(B X ) E
50 log (B),
where (i) is from the formulation of Bayes" theorem stated in [73, Theorem 1.31] and (ii) applies Bayes' rule.
Proposition (Variational form of the KL-Divergence given in Theorem 5.2.1 of [23]). Fix two probability distributions P and Q such that absolutely continuous with respect to Q. Then,
KL(P || Q) = sup [Ep[X] log Eolexp
where Ep and Eq denote the expectation operator under P and Q respectively, and the supremum is taken over all real valued random variahles X such that Ep[[X] is well defined and Eolexp X] < co.
Proof of Lemma 3. Under the (s, au- -usss-Gaanninnn Gaussian assumption of rz,s,, a), bound the cumu- lant generating function of ri (1, a) as
V (B) Boi(s,a)2
We therefore have that for any y 2 O, inf
(T) (((.a)) (v) (v)
(n V ri(aa) (1 (1/T(88 ((s.a))) S a))(s,)) 2y.
(8)
Plugging this bound into Lemma 11 yields Lemma 3.
E4 Proof of Lemma
Lemma 4, For known P and --sub-Gaussian r, we have
Egg Es Vi* (s) (Pr.)
max Vo(A), AEA(P)
(4)
VAPOR
where the VAPOR optimization problem concave.
Proof. The first inequality in (4) combines Lemmas 2 and 3. The second inequality comes from the fact that Prr. A(P) from Lemma 1. The VAPOR optimization problem is concave since (i) the objective function V is concave in À by concavity of the function x E (0, 1) + xV log æ, and (ii) the constraints a convex set due the fact that the state-action polytope A(P) is closed, bounded and convex [66, Theorem 8.9.4]. Finally, note that the maximum exists and is attained, since A(P) is closed, bounded and nonempty due to the fact that Pr- E A(P).
E.5 VAPOR without the Sub-Gaussian Assumption
From (8), for any set reward beliefs, the VAPOR optimization problem (Lemma 4) becomes
max A (Eor ( (- log A)) XEA(P)
Σ Ax(s, a) [Erri(s, a) + (V -1 (- log Aı
L.s.a
This objective remains a concave optimization problem since the function (w* (Ø) ()()))))) is always concave (as the inverse of the strictly increasing convex function v ())()))))
23

---

F.6 Proof of Lemma 5
Lemma 5. Let X solve the VAPOR optimization problem (4) and E argmin, Vo . then
- (V)
Proof. The proof extends the relationship between Bregman divergence and value in policy- regularized MDPs [48] to the setting of
MDPs. The Bregman divergence generated by & between two points X, X A(P) is defined as
D) = 2(A) 22() V X)
For ease notation, we omit the dependence on the beliefs & throughout the proof. We write
V(A) = Σ a((s,a)Enn(ssd)) SO(A),
V =
V(A), AEA(P)
X E argmaxx V(A),
XEA(P)
[=1
where Qi A(P) R is continuously differentiable strictly convex regularizer defined as
22(A) = Σ Σ oi (/1. \1(s, 1=1 8.0
By definition, X must satisfy the first-order optimality conditions for the maximum of V, and since X relint(A(P)) the following holds
(B&r VI((*)) --) - AAE((P).
Then.
Do(Prr,,7) = (2(PP-)) ) - Q(A*) - V2(A (PP- - X²)
= -2(PP-)) ) - 0(1") - EEr (P1- - -x")
V" - T
Pr- + -(Pr--)
= V" - ((Pr.).
(9)
We now notice that
of(8,a) 7(s.0))(ss.)00MM(..))
((A) = Σ
min (8,0)20
(m(
1=1 s.a
For any positive RLSA define
(F, 2T((5
2^(A)=
+ (ss.s)))((ss (s)
V.(A) = Σ Σ X1ss, als,a) - (2,
1=1 8.8
V-(A),
X E argmax V-(A). AEA(P)
AEA(P)
Using that the KL-divergence is the Bregman divergence generated by the negative-entropy function, (9) implies that
KL, (Pr- ||);) V.- (IPr.)..
Moreover, from strong duality (which holds because A(P) is convex),
min max V+(A) = max min V+()). TER S.S.A AEA(P)
XEA(P) rER
Denote 7" E argmin, Vr, then it holds that
KL, (Pr- X*) = V V.- (Pr.) 5V= -V-=V(PP V(Prr),
which concludes the proof.
24

---

F.7 Proof of Theorem and Corollary
Below we prove a more general statement that will imply Theorem and Corollary 1.
Lemma 12. Let alg produce any sequence of Femeeauuaall policies n',t 1,..., N, whose induced occupancy measures X= satisfy
Es S (a=X"")
(10)
where we assume that the uncertainty measure a' of the Vol function (3) satisfies
(f(8,))
(11)
Vi)
for some co > 0 and any [N]. EE [L], (s,a) St A. where we recall that (s a) denotes the visitation count to (s,a) at step before episode t and (. V = max(-, 1). Then it holds that
(ag, T) s v 2 loggg (SA)(1 + log T/T.
=((oVVAAT)
Proof. Note that E' x= corresponds to the occupancy measure of policy x' on the expected transition dynamics E' P.i.e ExX"" *(EE' P). We bound the Bayes regret of alg as
(agg T)
E Egpp
E
Vi((s)
VT (s)
L
E
Σ
Σ
E EAA (s, (s,
8,8
E
(B'A
E (s, (s,
E'X²' (s.
(s.000((8.0)/2220g83)) - 2log (s,
8,0
N
L ΣΣΣ
N
IA3
(EE
5.a
E
H(BBAP')
E
3> (s))
1=1=11 8.a
where (i) follows from the tower property of conditional expectation where the outer expectation with respect F F2, (ii) from the dual formulation of the value function averaged with respect to the initial state distribution [66] and the fact that > (s, a) and rs, a) are conditionally independent given Fe, (iii) is due to condition (10), (iv) is from the definition of Vor, , (v) and (vi) are by applying the Sauchy-Schwarr inequality. where H. denotes the entropy function [10].
We bound the left term by using the fact that H XT ) I log S.A. We bound the right term using condition (11) and by applying the pigconhole principle (e.g., [47, Lemma 6]) which gives
(s = E
N
E'AF' (s,
B
Σ a.a
nl(
n((s,a)v1 V1
R.
(s,
E
as
8,0
<
S:A(1 + log N)
t=
= SA((1 + log N):
25

---

which follows from the tower property of conditional expectation and since the counts at time t are Fe-mesurable. Taking T NL finally yields
(alg, T) V
log N)
=A(oVVSAT)
Theorem 1. For known and under Assumption 1, holds that BR& T) 2(v² + 1)TSA log(A)))) log (00_)))OOVSAAT Ö(VSAT)
Proof. Assumption implies that the mean rewards are sub-Gaussian under the posterior upper bound the sub-Gaussian parameter (s. s
(see [70, D.2]), where
V(v² + 1)/(n/ (n/(ss 1) at the beginning of each episode t. Thus the condition (11) holds for CD = VV² 1. Moreover, Lemma 4 implies that the occupancy measures that solve the VAPOR optimization problem satisfy condition (10). The result thus follows from applying Lemma 12. O
Corollary 1. Denote by algr. the algorithm that produces policies based on FT for each episode t
using (1). Then, under the same conditions as Theorem have ( T) S Ö(VSAT).
Proof. The result comes from combining Lemmas and 12, as done in the proof of Theorem 1.
F8 Proof Lemma
Definition 2 (Transformed beliefs). Consider any beliefs 6 such that the mean rewards are a-sub-
Gaussian and the transition dynamics are a- Dirichlet. We define the transformed beliefs â according to which the transition dynamics are known and equal to Eap P and the rewards are distributed as Egr + w, where wi(s, a) follows an independent zero-mean Gaussian distribution with variance 6² defined for each step E [L] and state-action pair (s, a) S A
(L 1)2
61(5,a)² = o. + Evesi ai(s, a,s")
We prove in Appendix F.8.1 the following stronger result which implies Lemma Lemma 13. For any step 1 E [L] and state E SS it holds that
Vi (s) s (z))
F881 Proof of Lemma 13
Overview. The proof relies on studying properties of two stochastic Bellman operators, drawing inspiration from [62, Section 6.5]. In particular will make use of the notion of stochastic optimism
(Definition 3). To deal with the unknown transitions, we will use the property of optimism [60]. To deal with unknown rewards, will derive property of Gaussian-sub- sua-Gaussian optimism (Lemma 19) which holds when the variance of the Gaussian distribution is multiplied by small universal constant.
Definition 3. A random variable X is stochastically optimistic with respect to another random variable Y, written Zso Y. Ex Eu(Y) for all convex increasing functions u -+ R.
Likewise, we will say that X is stochastically optimistic with respect to Y under 6 and write that X Φ 20o Y if (x((X) 2 (Y))(Y)) for all convex increasing functions u. R TR.
For any step E [L]. we introduce the Bellman operator By S S which is defined for any Q1+1 E 1 XA and state-action pair (8, a) E St A as
BiQ14155.a) = ri(8, a) + Pd(: 8, s, max Qutilsa')
r)) + Σ Pi(s' 8. max Q1+1(s',a").
26

---

We also define the 'transformed' Bellman operator B; R 1x + R as Eari(s, B.Q14((s. (ande,.))=an(((s000 a) + wi(s, a) + EyP s, s,a) max Q++1(-,a),
where recall that ()) ~ A (ss, a))) is distributed independently across the state-action pairs (s, a) E S A under o. Note that By and B can be viewed as randomized Bellman operators due the randomness in the MDP M and in the distribution w, respectively. We rely on two key properties.
Lemma 14 (Property 1: monotonicity). For any step I E [L], consider two random Q functions Q141 Q141,Qi+1 E I such that conditioned on the entries of Q4+1 (respectively Q/-1) are drawn independently across state-action pairs (s, a) S441 A and drawn independently of the noise terms wi a). Then
Q1+1(s,0 2so (1+1(),0) V(s,a) E S141 XA
implies
B,, 16 2so B,Q%+ 6 V(s.a) E S x A,
Proof. The proof follows exactly the steps of [62, Lemma 3J. It relies on the fact that conditioned on G. BiQ (8, a) is convex increasing function of (Q++1 (8, a))s,a convolved with the independent noise term wi (s, a). The result therefore follows from the fact that stochastic optimism is preserved under convex increasing operations [62, Lemma 2].
Lemma 15 (Property 2: stochastic optimism). For any 1 E [L] and (s,a) S441 A, it holds that
B,Qu+1(s,a) 1 2so B[Q(+1(s,a) ó for any fixed Q4+ E S XA such that Span(Q:-1) < L-1.
Proof. For any fixed Q++1, it holds that
8(Q(41(8, 16 N(b(s,,0.00((..3)) o
where we define
by(s, a) Egri(s, a) PpP(( ss, a) max Q++1 a²
Lemma 16 ([60]). Let Y Ei=1 A.b, for fixed b R" and random variable A, where A is Dirichlet with parameter a E R", and let X ~ xx with px 2 E Lad (gaa))(Span(b)) where Span(b) = max, b; miny bj. then X 2so Y.
Σ, and o 2
In case, in the notation of Lemma 16, A will represent the transition function probabilities, and b will represent V == max, Q(:aa), i.e., for a given (s,a) E Si x A let X be a random variable distributed A (Jux,03 where
Σ xx
(1((s.,,s Σ ai((s,,,z)) (a((s,,)))= )
Σ Eo[Pi(s' ((4))\442('')
S'ES.
S'ES112
due Assumption 2. Moreover, the lemma assumes that Span(V++1) s L - 1, we choose xx = (L (L- -1-1)//(E al,, As result, holds that
(L (1-1)²
N E.P(( s,a) max Qurlsaa),
E,0u(s, a1), 1 2so Pt( 8, s,a max Q4+1(,a')
Moreover, from the assumption of ar(8,, -as-u-uuuuusssee r((8, a) and from the Gaussian Sub- Gaussian stochastic optimism property of Lemma 19,
2so ri(s, a) - Bsr((s,a) Φ N (0. 3.. (s,
27

---

which means that
N a. a)) 10 2so ri(s,a) 1
As a result, since the random variables r((s,a), Pi( N (Egri(s, a), (s. and N (EoP( s,a) max Qu-1(;a)); Ev all are mutu- ally conditionally independent, we have
8, max Q4+1(,dd),
11-182
N (bi(s, (1),)))))))))) o ~ N (E 3.6 3.6'
(L (L-
+N E.P(( s,a) max (ixxtt)))))) Es a((),,,ss) 1
2so (1(s P(( s.a) max Q442(=4)) 1 B,Q(41ss,a) o
which concludes the proof.
Lemma 17. For any E [L] and (s, a) E St x
Q7 6 zso (s.
Proof. Note that under Φ, Qi B B2 ... .B,0 and under 3. =B==BB,, ..... By Lemma 15,
(8r,0)s, 2so (B,0) a) l.
Proceeding by induction, suppose that for some 1 < L,
(B. a) Zso
s.
Combining this with Lemma 14 shows
BB ... (B)0(ss (B00),,,.,)(( 16 2so
(s) 2so BB (2 10,
where the final step uses Lemma 15 and the fact that Span(B.41 ... B,,0) - L-
We are now ready to prove Lemma 13. We apply the property of stochastic optimism derived in Lemma 17 the convex increasing function u. (Q) max Q(s, a) for every step E [T.] and state s E S,, which yields the desired inequality EE, (s)) - 13 (s).
F.9 Proof of Lemma 7
Lemma 7. Let alg be any procedure that maps posterior beliefs to policies, and denote by o T) the Bayesian regret of alg where at each episode t = 1, the policy and regret are computed by replacing oi with ( (Lemma 6), then under Assumptions and 2,
(agg T) BRT T).
Proof. We recall that denote by o the prior the MDP, by 6' o Fi) the posterior beliefs at the beginning of each episode and by T the mapping that transforms the posteriors according to Lemma 6. Using the tower property of conditional expectation (where the outer expectation is with respect to Fi, we can define the Bayes regret over timesteps of alg under the sequence of original and transformed posteriors respectively
E Egnp Egge (1)(s) ((4))-r'(6)) v7)
BRg T) = E
BRl, 7) = _
R Repp B(a)y)
[Vi(s) Vi (s)
The result then immediately comes from combining Lemmas 13 and 18.
28

---

Lemma 18. For any fixed policy n. it holds that
Proof. We prove by induction the step / that Q7 (s, E 2F for any (s, E S A.
This is true at step L + 1. Assuming that true at step I + then
EØ (s, a) - 15
B
ri (8,aa) + E (8,0)
(((5'18,a) Σ (0
Esr((s + a) Σ BoPi(s' (s.))sssss.)))) Em
3
Pi' 8 a) Σ (441 E (s', 15
0, because 27 (s', = a') for every (s', E S441 A by induction hypothesis. In the above we used that [P( s, a) a)Q (s',,')] =']]=EpP(($ 8, a Q7+1 (s', which holds due to the time-inhomogeneity of the MDP, since the future return from fixed state-action pair cannot be influenced by the dynamics that gets the agent to that state-action. As a result,
E& (s) - B3 (T)) Σ T (s, EF
Σ
T a (7 a) = =0.
F.10 Proof of Theorem
Theorem 2. Under Assumptions / and 2, it holds that BR. (VAPOR, T) S Ö(INSAT)
Proof. We first explicitly bound the uncertainty measure Oe given our assumptions. The prior over the transition function Pt( | s, a) is assumed Dirichlet, and let us denote the parameter of the Dirichlet distribution (s, a) E St+ for each (s, a). where Eres,, as a, a, s') N i.e., we start with a total pseudo- count of at least one for every state-action (as done in [47]). Since the likelihood for the transition function is Categorical distribution, conjugacy of the categorical and Dirichlet distributions implies that the posterior over P((- S, a) at time t Dirichlet with parameter (s, a). where (s a, s¹) = (s, a, 8') + n/(ss, a, 8') for each s' E S1+1. where nf(s, 8') E N the number of times the agent has been state 8, taken action o, and transitioned state s' at timestep 1, and note that Exes mi(s, a, a²)" = (s, a), the total visit count to (s, as,a). Meanwhile, the reward noise is assumed additive --sub-aaussann, so we can upper bound the uncertainty measure of 124.5 as (s a) v(2 1) ()/(n((s,))) V As result,
bound
0l(,,)²² 5 3.62 + +L-
(12)
(ni(s, a)
The result follows from (VAPOR,, T) s BRy
log T/L) & (VAPOR, T) 2v3 + 1) L3)TSAlog(AA(11 log S(L
where the first incquality stems from Lemma 7 and the second inequality applies Lemma 12 whose condition (11) holds for co /3.62 +1) L?.
F11 Proof of Lemma
Lemma 8. Let XTS be the occupancy measure of the TS policy, it holds that TE{AT] Pr.
Proof. Given any environment M sampled from the posterior d, the optimal policy TM induces the occupancy measure X, (s, a) PM (T') a)). Marginalizing over the environment M yields CIATS(s, [u (sM = Po (T) (s)
29

---

F.12 Connection between K-learning and VAPOR
We sketch a proof of the connection between K-learning and VAPOR here. It proceeds via the dual in Lemma 9, by setting (s, a) for all 1, s, a and explicitly minimizing over the V E R variable. First, we define the following K K-function as done the original K-learning paper [47]
Ki(8, a) Eari(s, + alss,) +
P((s 8 (,))),=(
2r
for each 1,8,0, a. After setting the r parameters to be equal, we obtain the following dual over K E RLLSSA V BRSS,
Ki(s,a)-Vi(e) -1)
(()) +T subject to Ki(s, 2 Eoriss,a) + afss.))
minimize
exp
+E. P((s' s,a))i42(s")
2r
where we have introduced the K-function as an inequality constraint that becomes tight at the optimum and preserves convexity. Explicitly minimizing over Vi we obtain
(s,))))
Ki
Vi(() = = log Σ exp
log p(s)
for each E Si, and doing the same for Vi(s), 1 > 1 we have
K)(s,a) T log ((s)
Vi(s) = 7 log Σ exp
for each E St, where (s) is the dual variable associated with the inequality constraint and corresponds to stationary state distribution at s. Substituting
we can write the K-values as
(s + Pi('s | log
Σ exp (Kizi(s,aa)
Ki a) = Esr((s a)
2T
mi(s)
Thus we have derived a variant K-learning, with additional terms corresponding to the stationary state distribution. These additional terms becomes entropy in the objective function, and since the sum of these entropy terms can be bounded above by L log it only contributes a small additional term to the regret bound. Practically speaking this version of K-learning requires knowing the stationary state distribution μ(s), so it is more challenging to implement than the original K-learning. This analysis is not suggest this algorithm practical alternative, but instead demonstrate the connection between K-learning and VAPOR.
30

---

G Gaussian Sub-Gaussian Stochastic Optimism
The following technical lemma, which may be of independent interest, establishes relation of stochastic optimism (Definition 3) between sub-Gaussian and a Gaussian whose variance is inflated by a small universal constant.
Lemma 19. Lef Y be o-sub-Gaussian. Let X ~ NOO, o²) with 2 3.6. Then X 2so Y.
Proof. Let a R R be convex (increasing) function. We aim show that (x) 2 EY] Let Su I be subgradient of u at 0 (which exists since u is convex). Then by convexity of u, we have for all x E RR u(x) 2 u()) + sgt. Define the function ʃ + as [(x) = u(x) - v(O) - sp..
We have that [zz) 2 0 for all E IR and ʃ(0) = O. Since EX EY 0, it suffices to show that [x) 2 [B[(()) [Y) For any 2 0, define the e-sublevel set of the convex function f as
K. = {xr E R f(x) S e). Since K, is convex and by property of f. there exists a(e) E (
and b(E) E R2, U (+00 such that K, [a(e), b(e)]. Then, for any random variable Z.
Ef(Z)
(Z(( c) de
1. (P(2 2 b(e)) + P(Z S a()))) de.
By the o-sub-Gaussian property of Y.
Ef(r)
(P(Y 2 b(e)) + P(Y S sa(E))) de
exp (bb(e))
(=a(c)²
)) 20
exp
de
20²
(G(((e)) G(a(e)))
where we define
G(z) exp (-22//2222))
Let d := 2.69 and c= $ 2 1.338. Let Z ~ N' (222 and ((x):=PP() 2 z). Note that
1 - erf 2 F(x) 2
1
1/2 where erf denotes the error function, i.e., erf(y) = 2n 11/2 So exxx(=t)) dt. From Lemma 20, by choice of constants c, d, it holds that G(x) S dF (x). Therefore,
E B[ < d (F(b(e)) F(a(e))) de
d I0a
(PP(Z 2 b(e)) + P(Z 2 a(E)))
de
[E()
S E [f((dZ)
E [J()),
where the last inequality applies Lemma 21 to the convex function f that satisfies f(0) = 0, and the last equality is because ed which means that X and dZ follow the same distribution. D
Lemma 20. Denote by > 0 the (unique) solution of the equation
1
erf (1122)
1
exp (-1/(206))
2
Co 20
and let do > be defined as
2 eexp( -1/2)
do =
1-ert erl( 60
31

---

Note that = 1.33016 and du = 2.68271.
Then for any 2 on, d 2 do, the function Φ: R R defined as
d erf (v22) ))
<(x)
exp(-x221
is non-negative everywhere.
Proof. Define
do
(1 (1-cff crf (222)) exp(-x2/22)
do(x)
2
suffices to prove that (o 2 for all RR. By the choices of co, do. it holds that
do 1 erf (<1)2) exp(-1/2)
(1)
do cxp (-1/(2c7) + (1/2) 0.
(1)
cov2 2m
Moreover, analyzing the variations of yields that there exists To such that (x) 0 for E [o] and (x) < 0 otherwise. Therefore do is non-decreasing on [1, zo] and non-increasing elsewhere. Since l Φo(x) and (1)
get that do (x) for all R.
Lemma 21. For any convex function g R - R such that g(0) 0. for any 2 1 and R, holds that sg(x) & g(sx).
Proof. By convexity of g, for any x' R, have "(s-'z' I s- 50'9(x') + +1 s (0))
s-1 ((()), so by setting x' = sx it holds that sg(x) = sg(s sg(s=1z') $ g(x))= g(sx).
32

---

VAPOR-lite Analysis
Denoting the uncertainty signal of the VAPOR optimization problem by o, we define the VAPOR-lite(c) optimization problem for any multiplicative scalar e > 0 as follows
max AEA(R
Uz e2
((s
log )1(s,
)
Σ a)( + - >cōr(sssss cāi(s,
Es \r(s,b)
1,3,
Ae(o,-) Es (c((ssb))
as,
[Bni(s,a) + a)) + Hoōs(a.)
4,,0
(13)
Note that this corresponds to the same objective (5) except that it is optimized over the occupancy measures instead the policies. Lemma 22. The VAPOR-lite(c) optimization problem is concave X.
Proof. The objective is concave due to the fact that the normalized entropy function h of u Ry0 given by h(u) Σ i= u, log( 1 T u/u,) is concave (see [6, Example 3.19]) since the perspective operation preserves convexity.
Lemma 23. For any n > 0 and À E A)E it holds that
v2(2) S Uz(A, + 20 I.S.
where o = 22(1 + logll//// 1/n) and max = maxi,e Gi(s, a).
Proof. Any occupaney measure À A(E.P) be decomposed \s(s, a) (s) a). where nx denotes the stationary state distribution under æ, i.e., (T((s E. Ar(s, and n is the policy given by (s,s)a) a) = Ar(s, (),, (s) so long as ut (s) O, otherwise ((( :) can be any distribution, e.g., uniform. It holds that
Asss log as) M1ss, a) ass,
M(s,a) a) Mi (s)mi(s) log ni (s, (8) log (s)
$ Asss, a) - --4 (s) Avss, a) (1 + log (T (s) a) (s, a) (s,
a)) (s) log 1/1 + (sssa)))
where (i) that v- log 1 log(æ) for any x and (ii) uses that - log 5 and > 0. Hence, we have
x log 1/1 + 17 for any 0 S x <
Vo(A)= Σ Avss, a) (
+ Σ (1 -2 2 log (s)
Lss,a
1,5,0
a)) (Epr(ss,a) log l
1,,aa
EMi(s) (-2
Σ
(2 (27
Σ (2)
s Cz) + 20
Lemma 24. Consider the algorithm VAPOR-lite that each episode t = I,...,N N solves the optimization problem VAPOR-litefs = v2(1 + log SLt)). Then under Assumptions and 2, it holds that
BR,(VAPOR-Iite,TT Ō(LVSATT.
33

---

Proof. Denote by x' the policy executed by the algorithm at episode t, and by E'Pr- the posterior probability of state-action optimality in the expected model E' P. It holds that
E Egpp (s)
V
(E'Pr.)
69) (ETPr., 1/(8L()) 2 max//
Ug
6m
U3 -
E 1/(ST1)) + V2 max /1,
where (i) combines Lemmas 4 and 6, (ii) applies Lemma 23 to E'Pr. E A(E*)) with the choice
" 1/(SL(), and (iii) comes from the fact that E É XeA Ug- (A, 1/(TA)) Hence, retracing the steps of the regret derivation of the proof of Lemma 12, we can bound the Bayes regret of VAPOR-lite as
BR (VAPOR VAAOR--iite,T)
L
N
$
U3 (E' x .1((Stt) - Σ>
Σ
E' (s,
a))()))(( +
20
max
1
t
1=1 8,a
1=1
E
E E'AT' (8, (s,a)v2(1 log SLL)0
N
L
E' E' (s.a)v2(1+ log SLt) Σ (f
1=1
8,0
N
+ 20 max
7
To bound Z1 we apply the Seuchy-Schwarc inequality and the pigeonhole principle, as in the proof of Lemma 12, which gives that Z1 Ō max v SAT') To bound Zz, we introduce the second moment of the information [33] of a discrete random variable supported on finite set as
2 (X)
Σ xEX
P(X x) (- log P(X =))
and note that 22 < log" (111) for X
[33, Proposition 8). We bound
@
E E' ( 22 + log SL1)G) (- E' (s,
Zz
E
d0
IE
(B(A))))
2 2 (s,a)(1+ log (st)
1=1
where (i) that E' E'AJ' as, (s, a). (ii) applies the Cauchy-Schward inequality and (iii) uses the pigeonhole principle (as in the Z, bound) combined with the aforementioned logarithmic upper bound (2)) Finally, we bound the last term by using that Σn < 1 + log N. Putting everything together and using that @max = OLL) yields the desired bound BR,s (VAPORR--itte S ((TV)AAT.
34

---

100000
Haxfir Weighted Martre
kepizotes unti 92%% bod ep0000s
8000
1000
53000
solved
4020
2000
2008
70
100
150
700
Figure 7: Optimizing for weighted maximum entropy objective results in faster coverage time and thus more aggressive exploration in reward- free GridWorld.
problem
Figure 8: Learning time of VAPOR- DeepSea (one-hot pixel representation into neural net). Dashed line represents 2 where L denotes the depth.
I Experimental Details
L.1 Reward-Free GridWorld
We empirically complement our discussion in Section 6 on the connection of VAPOR to maximum entropy exploration. We consider simple 4-room GridWorld domain with no rewards, known deterministic transitions, four cardinal actions and varying state space size. We measure the ability of the agent to cover the state-action space as quickly as possible, iee, visit each state-action at least once. We consider the state-of-the-art algorithm of [79] for the original maximum entropy exploration objective maXXeA(P) H()), and compare it to the same algorithm that optimizes for weighted entropy maxXex(P) (A), where we define the uncertainty as (s, a) = I (n(s, a) = 0}, with n(s, a) the visitation count state-action (s, a). We see Figure that optimizing for this weighted entropy objective results in faster coverage time. This illustrates the exploration benefits of the state-action weighted entropy regularization of VAPOR (e.g., weighted by the uncertainty as done in VAPOR-1ite)
1.2 DeepSea (tabular)
We provide details the experiment of Figure 3. For the transition function use prior Dirichlet(1/ I/VS) and for rewards standard normal (N00, 1), done by [53]. Similar to [62, 47, 40], we accelerate learning by imagining that each experienced transition (s, a, s',r) r) is repeated 100 times. Effectively, this strategy forces the MDP posterior to shrink faster without favoring any algorithm, making them all converge in fewer episodes.
VAPOR implementation. The VAPOR optimization problem is exponential cone program that can be solved efficiently using modern optimization methods. We point out that we do not need to solve the two-player zero-sum game between À and since the minimization closed-form solution, see Equation (3). In our experiments, we use CVXPY [11], specifically the ECOS solver [12] (with 1e-8 absolute tolerance). In terms of runtime, this took few seconds the largest DeepSeas, which was sufficient for our purposes. There is a natural trade-off between a less accurate optimization solution (i.e., better computational complexity) and (i.e., better sample complexity), which can be balanced with the choice of CVXPY solver, its desired accuracy. its maximum number of iterations, elc. The implementation of the VAPOR optimization problem in CVXPY is straightforward using the library's 's atomic functions. Just note that although the expression / log that appears in the Va function (3) is not atomic function in CVXPY, simple trick is to use the equivalence
conveniently admits
accurate policy
max a
xV log I
max 2.
y
s.t.
S.L.
2 0, V20, 0, -xlog 2 /22x
where -r log (evxpy.entr(z)) and //2 (cvxpy.quad, over (in(yx))) are atomic functions.
35

---

Common Hyperparameter
Value
Discount factor
0.995
Replay buffer size
1e5
Replay fraction
0.9
Replay prioritization exponent
1.0
Adam step size
le 4
À of V-Trace(A)
0.9
Hyperparameter
None
Fixed, scalar
Tuned, scalar
Tuned, statc-action
(Figure 10)
Entropy regularization, Uncertainty scale
/
0.01
0.01
0.01
0.01
0.005
Tmin
/
0.005
Timax
/
10
Tinil
step size
le
Table Hyperparameters used the Atari experiments.
1.3 DeepSea (neural network)
We consider the DeepSea domain where instead of using a tabular state representation, we feed a one-hot representation of the agent location into neural network, using bsuite [58]. As discussed in prior works [62, 53, 49], agents that do not adequately perform deep exploration are far from being able solve depths of up to 100 within 10 episodes. This includes vanilla actor-critic or Soft Q-learning (which can only solve depths up to around 14, showcasing a learning time that suffers from an exponential dependence
depth), but also agents with some exploration mechanisms such as optimistic actor-critic or Bootstrapped DQN (depths up to around 50). In contrast, Figure 8 shows that MAPOR-lite te is able solve DeepSea instances out size 100 within 4 x 10 episodes, without a clear performance degradation. We chose the exact same algorithmic configuration and hyperparameter choices as our experiments on Atari (Appendix I.4), except Taale 3.0 and Replay fraction 0.995. This experiment shows that VAPOR-lite is capable of deep exploration, as suggested by the regret analysis in Appendix H.
L.4 Atari
RL agent. Our setup involves actors generating experience and sending them back to learner, which mixes online data and offline data from a replay buffer to update the network weights [30]. Our underlying agent is actor-critic algorithm with use of replay data, thus we call it 'Replay Actor-Critic (RAC)' We also made use of V-trace clipped importance sampling to the off-policy trajectories [15]. Replay was prioritized by TD-error and when sampling the replay prioritization exponent was 1.0 [72]. We note that, as commonly done on Atari, we consider the discounted RL setting (rather than the sorte-h setting used to derive theoretical results). We refer to Table for hyperparameter details.
Uncertainty measure in VAPOR-lite. For the uncertainty measure ô, we use an ensemble of reward predictors. Specifically, we set it to the standard deviation of H 10 randomly initialized reward prediction heads p(i) with randomized prior functions [56], i.e.,
ā (s, a) min (oeate stdisisn (s.)))
with oscale > scaling hyperparameter. We also added a small amount noise to the rewards the replay buffer for the targets for the reward prediction ensemble (specifically, 0.1 times an independent standard normal distribution) [14], to prevent the ensemble from potentially collapsing due the use of replay data.
36

---

0.75
0.5
CO-
0.00
40
20
0e-00
2e-20
Se+00
0e+00
26-20
5e+00
0e-C0
2e-00
Se+00
0e-50
20-00
Se+00
0h-50
2e+00
Se+05
0--00
2e+00
Seed5
bank besk
bot3k 2016
0.8-
beam
2.5
beraer
0.30
bonding
b00ing
0.25-
D.H-
0.05
0.50
0.4
0.6-
D-
0e-00
2+-20
Se+03
De+0D
26-20
Se+02
De+4D
2=-00
Se402
0s-00
2e-20
Se+
De+00
2e-200
Se+05
De+0D
20+20
Se4d8
BreaRQLE
centipdd
Chopper command
climeer
12.5
defenderr
demon DE3E
1.5-
10-
D4. 100
26
30-00
0e+00
2e-20
Ds
2o-00
Sesus
0e400
2o-20
0s-C0
E3
50405
0s-00
435
Senib
Wiible
Boniog derty
3.2
15-
0.9
25-
0.6-
5-
Human normalized score
0.2
20-
20
20-
0c+00 revenge
20-00
0c-50
0p-00
Sung,
pacman
name 2it game
phoenix
0.04
0.4
D.b-
0.09
25-
0.01
00
Se+00
De+00
2--20
fee
De-C0
7e
Dee00
7e-00
Seent
0e-50
Je
Se+08
0m-00
2e-08
1.2
200g
pfivato sye
0.75
quer
Distrras
20-
road purinrr
robolane
0.6
0.05
D0-00
20-C8
Ze+08
Sweit
De-00
2m-201
0e-c0
Se4d8
Dew00
2w
Se4
0.05
0.04
0.4
3011g
286/
50300 I993ders
10
25 Qurner
0.75
Sumound
0.01
0.2b
-0.0-
0.1
De- 00
2e-08
2a
30408
De4000
Ze--00 20
See
De
2e-c8
Se405
Dee00
Za-400
Sea 00
De-C0
Z D8
Se
0e-00
2er-00
Se
15
down
+5.00
1.5
/w// M
0.3
26
Sei00
3.5
Artir
0.5-
Frames
Figure 9: Per-game human normalized score (averaged over 5 seeds).
37

---

Median hurnan human-normalizen normalizmed score
1.5
Entropy regularization
0.5
fixed, scalar
tuned, scalar
tuned, state-action
0e+00
Ie+00
2e+00
3e-00
de+08
Se+008
Frames
Figure 10: Median human normalized score across 57 Atari games (with standard errors across 5 seeds) of optimixtic replay actor-critic agent, for differrnt choices of entropy regularization. VAPOR-lite "tuned, state-action' performs best.
Baselines.
In Figure we compare VAPOR-1ite, whose policy loss may condensely expressed
as
max rell
(N²T) (r+ +(²)) (Ha(T)))
(14)
to standard actor-critic objective
max elll
Tr,
(15)
as well as to actor-critic with fixed scalar entropy regularization
max FENT
(p*x) r (T*)T (BH((T))
(16)
where > O is hyperparameter (e.g., 3 = 0.01 in [42], which is also used in Figure 4 as it performed best). We later compare additional baselines (Figure 10).
On entropy regularization for policy improvement/vvlluatio.. We refer to [84] for in-depth discussion the difference of using entropy for policy improvement and/or for policy evaluation in entropy-regullrizee RI. Theory prescribes both [87] and some algorithms such as Soft Actor-Critic [26] implement both, yet as remarked by [84], omitting entropy for policy evaluation (i.e., not having entropy as an intrinsic reward) tends to result in more stable and efficient learning. We also observed the same and thus only use entropy for policy improvement.
Related works. We mention here couple of related works to our proposed algorithm. [22] argue that standard policy entropy regularization can be harmful when the RL problem contains actions that are rarely useful, and propose a method that uses prior action distribution. [27] discuss the limitation of policy entropy regularization being 'sample- unaware', and propose to regularize with respect to the entropy of weighted sum the policy action distribution and the sample action distribution from the replay buffer.
regularization to optimize a
Per-game results. Figure reports the performance of the Replay Actor-Critic (RAC) baseline compared to RAC augmented with VAPOR-lite, on each Atari game. We see that VAPOR-lite yields improvements in many games, especially hard-exploration games such as Montezuma's 's Revenge Venture.
38

---

Ablation on entropy regularization. VAPOR-1ite advocates for two ingredients: optimism and weighted entropy regularization. While the first has already been investigated in deep RL for various choices of uncertainty bonus [4], the second is novel so we focus our attention on it here. For fair comparison, we augment all agents with the optimistic reward component, to isolate the effect of the adaptive state-action entropy regularization of VAPOR-1ite We consider the following policy losses for various choices of entropy regularization
none:
max (,*TT² (r + +))
well
fixed, scalar:
max (1*x)" (r σ) (1(7) (BH(T)),
well
tuned, scalar [49]:
min well 720
(r (n"*²² 82 (2T)) + (1²) (TH(T)),
tuned, state-action (VAPOR-1ite):
max well
(f² (r (r+ (1²)) (Ha(T)))
In particular, have further compared an optimistic actor-critic objective with tuned, scalar entropy regularization, specifically the epistemic-risk-seekin objective of [49] which corresponds to solving principled saddle-point problem between policy player and a scalar temperature player parameterized by neural network. We refer to Table 2 for hyperparameter details. We observe in Figure 10 the isolated benefits of VAPOR lite''s runed, state-action entropy regularization.
Future directions.
Below we list some relevant directions for future empirical investigation:
Although our simple & uncertainty measure using an ensemble of reward predictors worked well. more sophisticated domain-specift uncertainty signals could be used [63, 64, 7].
A first 'looseness' of VAPOR-lite with respect to VAPOR that it sets the temperatures T to the uncertainties ā (which yields the same Ô regret bound). An interesting extension for VAPOR- -ite could be optimize directly the temperatures by minimizing VAPOR's saddle-point problem with state-action dependent temperature player parameterized by an independent neural network.
A second 'looseness' of VAPOR-lite with respect to VAPOR is that it bypasses the challenging optimization of the entropy of the state visitation distribution, by only wveight-)regulariiing with the entropy of the policy. Various attempts have turned to density models or non-parametric entropy estimation [29, 36, 43], and it could be relevant to incorporate such techniques to get closer the VAPOR objective.
Our agent relatively simple compared to modern state-of-the-arr Atari agents since it missing components like model-based rollouts, distributional heads, auxiliary tasks, etc. An interesting extension would be to incorporate the techniques discussed in this paper into the most effective policy-based agents.
39


Reviews:
[{"review_id": "ozUtSpdFAD", "reviewer": "Reviewer_3w7N", "summary": "The paper identifies \"the posterior probability of state-action optimality\" denoted $\\mathbb{P}_{\\Gamma^*}$ as a key object for inference and control and provides a variational optimization approach to estimate it. Clear presentation, insightful analysis, and experiments on GridWorld, DeepSea, and Atari are provided.", "questions": "None", "limitations": "There is no dedicated section for limitations, but limitations are sufficiently discussed in the conclusion.", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Outstanding paper in all respects. A fresh and principled approach to RL as inference. High quality execution both on the theory and experimental side.", "weaknesses": "None", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the complimentary review! We are delighted that you think our work is valuable. We welcome any further comments."}, {"review_id": "tlAKE7L9Gz", "reviewer": "Reviewer_NW3r", "summary": "This paper undertakes a rigorous Bayesian treatment of the posterior probability of state-action optimality. It proposes a variational approach to approximate the state-action optimality. The proposed method involves a tractable convex optimization problem and is provably efficient. This paper also conducts experiments showing that the proposed method compares favorably with previous methods.", "questions": "Is there a theoretical benefit for optimizing both the policy and stationary state distribution?\nIs there an intuitive explanation for the balance between optimism and entropy regularization?", "limitations": "This paper has not discussed the limitations of the proposed method and the theoretical analysis.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper, for the first time, undertakes a rigorous Bayesian treatment of the posterior probability of state-action optimality. It proposes a novel method having deep connections to previous work. Related work has been adequately cited.\n\nThis paper seems to be technically sound, though I did not check the proof in Appendix. All claims are well supported by theoretical analysis and experimental results. It is also clearly written and well organized.\n\nI believe the result presented in this paper is significant. What I find most interesting is that the proposed method finds a balance between optimism and entropy regularization, and the resulting reward bonus is the product of surprise and uncertainty.", "weaknesses": "This paper formally treats the posterior probability of state-action optimality and demonstrates its connection to Thompson sampling. Similar analysis has been given in [O’Donoghue et al.](https://openreview.net/pdf?id=S1xitgHtvS). This should be mentioned in the paper.\n\nThe proposed method is novel. However, its connection to previous work, especially K-learning, should be discussed in more depth. Specifically, K-learning could be understood as a variational approximation of the policy induced by the state-action optimality ([O’Donoghue et al.](https://openreview.net/pdf?id=S1xitgHtvS)). VAPOR proposed in this paper additionally optimizes the stationary state distribution, which, to my understanding, complicates the optimization by introducing the need for forward message passing. It is not discussed in this paper whether and why this is beneficial.\n\nIn Figure 2, this paper compares the stationary state distribution induced by VAPOR and TS. I believe it should additionally provide a comparison with K-learning as K-learning also approximates the policy induced by the state-action optimality.\n\nThis paper provides a performance comparison in environments like DeepSea and Atari. As Bayesian approaches, it should also compare the Bayesian regret by simulating in MDPs randomly generated from prior.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and for highlighting connections to previous work, on which we will expand in the revised version. We answer their queries below:\n\n__Discussion of O’Donoghue et al.__ Thanks for highlighting that O’Donoghue et al., 2020 argue that TS solves at each episode an inference problem that samples from “the _joint_ [posterior] probability over all the binary [_action_] optimality variables”. While this is stated without proof nor rigorous definition of this joint quantity (which appears quite convoluted at first glance), our paper reveals that it can be condensely expressed: it represents the policy induced by the posterior probability of _state-action_ optimality (Def 1) (which is an occupancy measure). Thanks to this new definition, we can write a formal link between TS and RL as inference (Lemma 8).\n\n__Connection to K-learning.__ As you say, O’Donoghue et al., 2020 show that K-learning can be derived as an approximate inference procedure, although this hinges on the _assumption_ that inference is over the moment generating function of $Q^\\star$ (Equation (7) of O’Donoghue et al., 2020). On the other hand, VAPOR’s derivation through our inference perspective is free from any assumption on the distribution of the optimality variables. Interestingly, we can show that VAPOR with equal temperature variables $\\tau$ approximately recovers K-learning, thus shedding a new light on K-learning as a variational approximation of our probabilistic inference framework with an additional constraint of equal $\\tau$ variables.\n\n__Suggestions of additional experimental insights.__ Thank you for the two suggestions (i.e., plot the occupancy measure of K-Learning in Figure 2, and compare the Bayesian regret of the approaches by simulating in MDPs randomly generated from a prior), which we will incorporate in the revised version.\n\n__Q1: Is there a theoretical benefit for optimizing both the policy and stationary state distribution?__ We show that the core quantity that formalizes RL as inference from a Bayesian viewpoint — the posterior probability of state-action optimality — is an occupancy measure (Lemma 1). Our variational approximation VAPOR naturally optimizes in this space. Intuitively, having a forward message passing enables the agent to capture prior episode information (i.e., to condition on prior steps in the episode being optimal), which is key to taking consistent actions (see our example in Figure/Table 1). Directly optimizing over occupancy measures is difficult in practice, thus we also propose VAPOR-lite which instead optimizes over the policies, akin to standard policy gradient methods (in this case, the optimization problem is no longer concave but good maxima can be found). \n\n__Q2: Is there an intuitive explanation for the balance between optimism and entropy regularization?__ This is a great question, in particular because it naturally falls out of our approach. One interpretation of having both exploration mechanisms work in tandem may be that optimism is providing a guidance on _which_ areas of the state space to visit next (i.e., uncertain states with high intrinsic reward). Entropy regularization, meanwhile, could be seen as providing guidance on _how_ to reach such desired states, where stochastic trajectories are preferred (which adds some local coverage/exploration).\n"}, {"review_id": "3QRkDARzxZ", "reviewer": "Reviewer_UaER", "summary": "The paper provides a Bayesian treatement for the reinforcement learning as probabilistic inference framework for the discrete state/action space. As extension to the standard formulation, posterior probabilities of state-action optimalities are regarded and formally defined. For tractability, an approximation of the probabilities via variational inference is derived. Further, the case of unknown dynamics is considered and links to other approaches discussed. The authors evaluate their method on a grid world problem, deep sea, and (in an reduced form) to atari.", "questions": "How strong is the assumption for VAPOR that $r_l$ is a sub-Gaussian (in Lemma 3)?\n\nIs it possible to apply the method to continuous state/action spaces?\n\nWhat are the runtimes for the experiments?", "limitations": "The formulation is limited to discrete/action spaces and does not seem to be scalable.\n\nNo runtimes are provided. It would have been very interesting to see how much time it takes to solve the two-player zero-sum geme in every iteration.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem which is considered in the paper is interesting for the use in state-of-the-art reinforcement learning. While not being obvious at first sight why a Bayesian treatment is advantageous, the simple decision problem makes that very clear. \n\nBy providing a formalization of the Bayesian formulation and the variational approximation and details about the algorithm the contribution of the paper is very good.\n\nThe paper is well-written and easy to follow.\n\nWhile just briefly looking at the appendix, all theorems seem to be proven and assumptions listed.", "weaknesses": "There is no code provided in the supplementary material or paper. In these days, I would expect this for an accepted paper at NeurIPS.\n\nFuture work and limitations are not sufficiently discussed in my opinion.\n\nFor atari evaluation, only a reduced version of the algorithm is considered (without weighted entropy)\n\nInformation on how to solve the VAPOR objective are only given in the appendix.\n\nThe paper seems very crowded, for example the table besides lemma 6 is a bit confusing. It is good, however, that it has a lot of content/contribution.\n\nMinor:\nThe quantity $\\lambda$ seems not to be well-defined for me as it is used a function but not defined this way. It took me a while to understand what it really is. This should be written in a more consistent way.\n\nline 110: Add \"pair\" after state-action.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and suggestions (such as expanding on the future work and limitations), which we will incorporate in the revised version.\n\n__No code.__ We will include more details on the implementation of both VAPOR and VAPOR-lite, such as detailed pseudo-code (including the code snippet of the VAPOR optimization problem that we solve using CVXPY) and hyper-parameter list.\n\n__$\\lambda$ notation.__ We will clarify on lines 71-74 that the notation $\\lambda_l \\in \\mathbb{R}+^{S \\times A}$ means that $\\lambda_l$ is a function $S \\times A \\rightarrow \\mathbb{R}_{+}$ for every $l \\in [L]$. \n\n__Q1: How strong is the assumption for VAPOR that $r_l$ is a sub-Gaussian (in Lemma 3)?__ We consider the sub-Gaussian mean reward assumption in the main paper since it is very standard in the literature (e.g., K-learning [O’Donoghue, 2021], PSRL [Osband and Van Roy, 2017], RLSVI [Osband et al., 2019]) and it allows us to present clean results and regret bounds. This assumption is not required _computationally_ for VAPOR (only for the analysis): in Appendix C.3 we extend Lemma 3 to the general case, and we refer to Appendix C.5 for the resulting VAPOR optimization problem.\n\n__Q2: Is it possible to apply the method to continuous state/action spaces?__ Our new framework of ‘RL as inference’ may be instantiated and approximated in various ways, targeting theoretical guarantees or scalability, which dictates which standard RL tools to use to solve the variational optimization problem we propose. In particular, we derive a tabular, model-based algorithm VAPOR with theoretical guarantees (Algorithm 1). Meanwhile, by optimizing in the space of policies instead of occupancy measures, VAPOR-lite is a model-free, policy-gradient-based algorithm that approximates our probabilistic inference framework, so it can readily leverage existing policy-gradient techniques suitable for continuous state/action spaces.\n\n__\"Only a reduced version of the algorithm is considered (without weighted entropy)\".__\nWe will make sure to add more details on VAPOR-lite in the revised version. We will clarify that VAPOR-lite does consider weighted entropic regularization (but in the space of policies instead of occupancy measures, which is a weaker but more scalable form of regularization). As such, VAPOR-lite retains the core algorithmic novelty of VAPOR of weighting optimism and entropy regularization on a per state-action basis. \n\n__Q3: What are the runtimes for the experiments?__\nAlthough VAPOR requires solving a convex optimization problem at each iteration, which makes it slower than dynamic programming approaches like Thompson Sampling, the problem is an exponential cone program that can be solved efficiently using modern optimization methods. We point out that we do not need to solve the two-player zero-sum game since the minimization over $\\tau$ conveniently admits a closed-form solution (see Equation 4). In our experiments, with the CVXPY solver ECOS (and 1e-8 absolute tolerance), solving the VAPOR optimization problem took a few seconds on the largest DeepSeas, which was sufficient for our purposes. There is a natural trade-off between a less accurate optimization solution (i.e., better computational complexity) and a more accurate policy (i.e., better sample complexity), which can be balanced with the choice of CVXPY solver, its desired accuracy, its maximum number of iterations, etc. We will include runtime details and discussion in the revised version. As for VAPOR-lite, its computational cost is essentially the same as the replay actor-critic baseline (it only needs to compute the uncertainty signal σ with an ensemble of reward predictors)."}, {"review_id": "cbfIqijt5L", "reviewer": "Reviewer_QdEN", "summary": "The paper views reinforcement learning as a Bayesian variational inference problem, and proposes VAPOR, an algorithm which computes an approximately optimal occupancy measure and its corresponding policy. Bayesian regret of VAPOR is analyzed to have a sub-linear bound. In numerical experiments, VAPOR shows good performance in simple GridWord and DeepSea environments. For more complex Atari environments, a further approximated VAPOR-lite is used and is compared with its entropy-regularized counterpart.", "questions": "- As described in the weakness, is $\\sigma_l(s, a)$ a constant or it follows a decay process? This seems critical to the algorithm and its analysis. It would be great if the authors can clarify the role of $\\sigma_l(s, a)$ and correct the proofs one way or another.\n\n- There are several issues in the lemmas that lead to the proof of Lemma 7. \n  - In the proof of Lemma 13, summations are missing from Bellman operators. It seems like the authors may want to use some short-hand notations for those summations, what are the definitions for those notations? It's not possible to follow the proof without proper descriptions and definitions.\n  - In the proof of Lemma 14, the second sentence claims to be conditioned on $\\phi$, but $\\hat{\\mathcal B}_l$ is defined using the distribution of $\\hat \\phi$ instead of $\\phi$. Is there some typos for $\\hat \\phi$ and $\\phi$? Either way, the proof requires more steps transiting from $\\phi$ to $\\hat\\phi$ to be true.\n  - In the proof of Lemma 18, why can one brings the expectation $\\mathbb E_\\phi$ inside the Q-function? This seems to be a consequence of independent Dirichlet, but one needs to show that it leads to some kind of independence for the Q-function.\n", "limitations": "Beside possible errors in the analysis, the assumption makes the analysis in the paper limited and there is no discussion on this aspect.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "- While the idea of \"RL as inference\" has been considered, this paper proposes a new approach which aims to directly approximate the optimal occupancy measure in the Bayesian setting. This approach has the potential to better approximate Bayesian optimal reinforcement learning policy which might handle hard exploration situations.\n\n- The motivation of the algorithm is explained well. The main idea of VAPOR is based on inequality (5) in Lemma 4. This inequality provides an upper bound of the optimal Bayesian performance, and the objective of VAPOR is basically finding the policy achieving the upper bound.  Some analysis of the approximation is provided in Lemma 5.\n\n- The performance of VAPOR is analyzed in terms of Bayesian regret in Theorem 1 with known transitions, and then the analysis is extended in Theorem 2 under the independent Dirichlet assumption on the transition dynamics. Bayesian regret is shown to be sub-linear in both cases.\n\n- VAPOR shows good performance compared with Thompson sampling based methods in simple GridWord and DeepSea environments. \n\n- For more complex Atari environments, a further approximated VAPOR-lite is used and is compared with its entropy-regularized counterpart.\n", "weaknesses": "- Although Lemma 5 provides a bound on the KL-divergence between the VAPOR solution and the optimal occupancy measure, the bound is in terms of the gap of the VAPOR approximation of the optimal Bayesian performance in (5). So this bound is basically using a property of VAPOR itself to bound another property of VAPOR and none of them can be evaluated. Therefore, beside numerical experiments, we have no idea how loose the upper bound (5) can.\n\n- Since the considered dynamics are time-inhomogeneous, the space of occupancy measure VAPOR is solving has dimension growing in the time horizon. This means that VAPOR might not be able to handle problems with long horizon, and this contradicts the statement at the end of Section 5 that VAPOR produces stationary policies, while it doesn't due to the time-inhomogeneous nature of the occupancy measure.\n\n- In VAPOR, $\\sigma$ seems to be a hyper-parameter, but it's not clearly defined. In particular, $\\sigma$ seems to be a constant in most lemma and theorem statements, but $\\sigma$ looks like a multi-dimensional vector with entry $\\sigma_l(s, a)$ in (2) and (4). This confusion makes the description of the algorithm inconsistent and it might lead to some errors.\n\n- The issue of $\\sigma$ mentioned above might lead to a major error in the regret analysis and the VAPOR algorithm. In the proof of Lemma 12, equation (14) implies $c_l(s, a) = \\sigma_l(s, a) \\sqrt{n^t_l(s, a) \\vee 1}$. According to (14), $c_{\\max} = \\max_{l, s, a} \\sigma_l(s, a) \\sqrt{n^t_l(s, a) \\vee 1}$. Therefore, unless $\\sigma_l(s, a)$ decrease at least at the rate of $1/\\sqrt{n^t_l(s, a) \\vee 1}$, the value of $c_{\\max}$ will not be a constant.  But from the statement of Theorem 1, $\\sigma$ seems to be treated as constant which is inconsistent with the proof of Lemma 12. It seems like, the uncertainty measure $\\sigma$ needs to follow a decay procedure. Gradually decreased uncertainty is generally required for a policy to have sub-linear regret because non-decreasing randomness would lead to linear regret due to the constant noise in policy. \n\n- Lemma 7 is very counter-intuitive. If it's true in general, uncertainty in the transition dynamics can be easily handled by replacing it with its mean. This would establish a kind of certainty equivalence for MDP which seems too strong to be true. I try to follow the proof of Lemma 7 and found several issues. Those issues may be correctable, but even if Lemma 7 is correct, it is probably too strong due to Assumption 1. Although Assumption 1 has been used in the literature, this assumption is restrictive and is not applicable in most applications. For example, any MDP with an unknown but fixed (over times/steps) transition function violates the assumption because the transition functions are not independent over times/steps. \n\n- VAPOR-lite sounds promising with its application in complex environments like Atari games, but the paper only provides very limited information for VAPOR-lite and there is no details available for its implementation. The numerical results are also very limited, with no results on individual games and no comparison with popular existing algorithms.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. When we encounter a reviewer that has clearly taken the time to read the paper in detail, as you have, and given the paper a low score, that is a signal to us that the paper is unclear in the highlighted areas — so thank you for bringing these issues to our attention! In this rebuttal we hope to clarify one-by-one your inquiries on the technical soundness, which we will incorporate in the revised version.\n\n__Q1: Is $σ_l(s,a)$ a constant or does it follow a decay process?__\nThanks for flagging that $σ$ was overwritten as a vector following a decay process (Lemma 3) and as a constant (Theorem 1). In short, the correspondence is $σ^{\\text{vector}}_l(s,a) = \\frac{σ^{\\text{constant}}}{\\sqrt{n_l(s,a)}}$. First, the constant $σ^{\\text{constant}}$ controls how noisy the rewards are (larger noise corresponds to a larger constant), we will replace it with the notation $c_0$ to avoid confusion. Second, we assume that the posterior uncertainty decays with data (of size $n$) at a particular $\\frac{c_0}{\\sqrt{n}}$ rate, which is a quite natural rate (also considered in the PSRL, RLSVI, K-learning analyses) that arises commonly in practice —  it holds, for instance, for Gaussian or bounded reward noise. As such, the condition of Lemma 12 should now read: ‘We _assume_ that the uncertainty $σ^t_l(s,a)$ decays at least as fast as $\\frac{c_0}{\\sqrt{n^t_l(s,a)}}$’. \n\n__Q2: Clarifications on the proof of Lemma 7.__\n- __Proof of Lemma 13.__ We will clarify the dot product notation $^\\top$ in line 737 that gives the summation, i.e., for any step $l \\in [L]$ the Bellman operator $B_l: \\mathbb{R}^{S_{l+1} \\times A} \\rightarrow \\mathbb{R}^{S_{l} \\times A}$ is defined for any $Q_{l+1} \\in \\mathbb{R}^{S_{l+1} \\times A}$ and $(s,a) \\in \\mathcal{S}_l \\times \\mathcal{A}$ as\n\n$(B_l Q_{l+1})(s,a) := r_l(s,a) + P_l(\\cdot \\mid s,a) ^\\top \\max_{a'} Q_{l+1}(\\cdot, a') := r_l(s,a) + \\sum_{s’ \\in \\mathcal{S_{l+1}}} P_l(s’ \\mid s,a) \\max_{a'} Q_{l+1}(s’, a')$.\n\n- __Proof of Lemma 14.__  Thanks for flagging that it should indeed be $\\hat\\phi$ instead of $\\phi$ in the conditioning of the second sentence. We will expand the proof with more detail, with steps broken out clearly (due to the rebuttal character limit we do not include it here but we can add it as an Official Comment if the reviewer wishes). We also recall that the proof is not our contribution as it follows exactly the steps of the proof of Lemma 3 of RLSVI (Osband et al., 2019).\n \n- __Proof of Lemma 18.__ We understand your question as: why can we use $\\mathbb{E}(P Q) = \\mathbb{E}(P) \\mathbb{E}(Q)$? This is due to the time-inhomogeneity of the MDP, which implies that $P$ at time $l$ and $Q$ at time $l+1$ are independent, since the future return from a fixed state-action pair cannot be influenced by the dynamics that gets the agent to that state-action.\n\n__KL-divergence bound of Lemma 5.__ The result shows that the weighted KL-divergence between $\\mathbb{P}_{\\Gamma}^{\\star}$ and its variational approximation is bounded by how much the VAPOR objective is optimistic. Thus it draws a connection between optimism (familiar to RL practitioners) and quality of approximation as measured by KL divergence (familiar to variational Bayes researchers). For this we included Lemma 5, which we do not feel is a major piece of the paper, it is more about building intuition.\n\n__'Stationary' terminology.__ Following some prior works we used the term ‘stationary’ to describe a strategy that does not depend on the episode number K (unlike many frequentist algorithms that have a log(K) dependence in the algorithm). In other words, stationary algorithms are entirely a function of the beliefs, not of the episode number. We will clarify this definition in the paper.\n\n__Lemma 7 is counter-intuitive.__ Yes indeed, we believe that Lemma 7 is actually an important contribution of the paper! Intuitively speaking, it doesn’t really matter to the algorithm where the uncertainty comes from (between r and P), just that there is uncertainty at some far away state-action that must be reduced by visiting it. Note that the amount of uncertainty moved from the transitions into the rewards is large, O(L) for finite horizon L, so it’s not a ‘free lunch’ so to speak. We also emphasize that the result holds only for Dirichlet posteriors over P, so quite a lot of structure is required on the problem for it to hold. However, Dirichlet posteriors over P are very natural for transition functions so we believe it is useful in practice. In fact, similar results have been used in the literature for TS, RLSVI, and K-learning. Our contribution is to make it general (i.e., it holds for any algorithm) and extend to the full sub-Gaussian case rather than just the Bernoulli reward case.\n\n__Assumption of time-inhomogeneous dynamics.__ This assumption is not inherent to the VAPOR algorithm, but rather to existing $L\\sqrt{SAT}$ Bayesian regret analyses. It is straightforward to instantiate the VAPOR algorithm under time-homogeneous dynamics (as we do in the GridWorlds of Fig. 2 and 6). The assumption is solely used to present clean theoretical results (which require the property that the transition function and the value function at the next state are conditionally independent). In fact, the analyses of K-learning, PSRL, RLSVI also require this assumption. Note that the example you gave (MDP with unknown but fixed transition function P) can be converted into a time-inhomogeneous MDP by unrolling (essentially copying the states L times), picking up an additional factor of sqrt(L) in the regret bound. In practice, this does not seem to matter much (most of these algorithms perform well in either case), but we take it for ease of analysis.\n\n__VAPOR-lite limited information.__ We will include much more details on the implementation given in Appendix E.3 (e.g., detailed pseudo-code and hyper-parameters) and add the learning curves for each individual Atari game."}, {"review_id": "a6E8dsAUxf", "reviewer": "Reviewer_MCkd", "summary": "The authors propose a model-based RL algorithm for MDPs with unknown rewards and transition dynamics, which approximates the posterior probability of an action being optimal in a given state to ensure efficient exploration. The approach is mostly contrasted with model-free RL as inference, but there is also an experiment comparing with a Thompson sampling-based baseline.\n\nEDIT AFTER DISCUSSION\nI revised my score from 3 to 7.", "questions": "Where does this paper stand with respect to existing literature on Bayesian approaches to model-based RL? Only once this question is answered exhaustively would it be possible to review this paper. I don't see how that's going to be possible within this cycle, though.", "limitations": "Unclear, as this paper is not properly positioned with respect to existing work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The presentation is clear and the proposed method is easy to understand.", "weaknesses": "I think the abstract is rather misleading and the authors are missing a large portion of existing literature on the topic. RL as inference, as presented by Levine [30], is a model-free algorithm. Any shortcomings of this approach notwithstanding, it is simple and computationally efficient, as model-free methods generally are. The abstract of this submission promises that the authors fix some problems with RL as inference, when in fact they just use a model to compute optimal actions instead. Sure, in some sense one could argue that this is better, but not exactly novel. The RL as inference framework is thus only tangentially relevant to the proposed method and the authors should compare with model-based approaches instead. There is some discussion of the relationship to PSRL in Section 6,  but way too little and too late.\n\nI don't do model-based RL myself, so I'm not really in a position to evaluate how the proposed method relates to existing approaches in that space. I also don't really know the right papers to use as baselines, but here are a few articles I found with a quick search in case that's helpful.\nAsmuth, J. and Littman, M. Learning is planning: Near Bayes-optimal reinforcement learning via Monte-Carlo tree search. In UAI, 2011.\nAsmuth, J., Li, L., Littman, M. L., Nouri, A., and Wingate, D. A Bayesian sampling approach to exploration in reinforcement learning. In UAI 2009, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009, pp. 19–26. AUAI Press, 2009.\nGuez, A., Silver, D., and Dayan, P. Efficient bayes-adaptive reinforcement learning using sample-based search. In NIPS, 2012.\nStrens, M. J. A. A Bayesian framework for reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), pp. 943–950, 2000.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. In this rebuttal we hope to convince you that our work is adequately positioned with respect to existing works on Bayesian model-based RL, and that its framing in the light of ‘RL as inference’ is relevant. \n\n__Where does this paper stand with respect to existing literature on Bayesian approaches to model-based RL?__ Thanks for the pointers to existing model-based literature! Bayesian model-based RL is indeed a rich line of research, inspired by Thompson (1933) and dating back from the 2000s (e.g., 2nd and 4th reference of the reviewer). These early works have laid the algorithmic foundations for the PSRL algorithm analyzed by Osband et al. (2013, 2017), which remains state-of-the-art both theoretically and empirically, along with the more recent K-learning. For completeness, we also point out that there are information-theoretic approaches (e.g., information-directed sampling [Russo and Van Roy, 2014], [Hao and Lattimore, 2022]) that provide elegant insights but are challenging to implement in practice (because of the difficulty of estimating mutual information). Finally, another line of research has adopted a tree-search approach to Bayesian RL (e.g., 1rst and 3rd reference of the reviewer), yet these approaches do not provide learning guarantees and are beyond the scope of this paper. All in all, we believe that PSRL, RLSVI and K-learning are the most relevant related works on no-regret Bayesian model-based RL and this is why we focus our theoretical (Section 6) and empirical (Section 8) comparison on them. \n\n[Russo and Van Roy, 2014] Learning to Optimize via Information-Directed Sampling.\n\n[Hao and Lattimore, 2022] Regret Bounds for Information-Directed Reinforcement Learning.\n\n__RL as inference, as presented by Levine [30], is a model-free algorithm…__ “RL as inference” in Levine, 2018 is not an algorithm but a framework. Since it is not an RL algorithm it is neither model-free nor model-based, although both model-free and model-based algorithms can in principle be derived from it. Our paper derives a _new_ framework that overcomes the (quite serious) shortcomings of the previous one. From our framework we can also instantiate both model-free and model-based algorithms, since we can use standard RL tools to solve the variational optimization problem we propose. We derive one particular model-based algorithm VAPOR, but our framework is not bound to be model-based. For instance, VAPOR-lite (Section 8 and Appendix E.3), which optimizes in the space of policies instead of occupancy measures, is a model-free, policy-gradient-based algorithm that approximates our probabilistic inference framework.\n\n__…they just use a model to compute optimal actions instead…__ We wish to clarify that one of our key insights is to sample (according to its posterior probability) the optimal action at any state _conditioned on the state being optimal_. We refer to this as state-action optimality (Definition 1) and prove that sampling from it yields efficient exploration and provides a principled view of RL as inference. We point out the subtle importance of such conditioning, without which simply following ‘action optimality’ is well known to lead to inefficient exploration (see our illustrative example in Section 3.1)."}]

Author rebuttal:

Meta-review: I am thrilled to convey my recommendation for the acceptance of your paper to be presented at NeurIPS. Your work won over both the reviewers and myself and I am confident that it will make a valuable contribution to the NeurIPS conference.

This is a highly intriguing paper with a lot of discussion. It is, effectively, an attempt to entirely reframe the RL as inference framework which works in the tabular setting, probably, and may be useful in more general settings after much future work. In the absence of strongly negative initial reviews which suggest something important about the clarity of the paper, and some remaining negative sentiment, I could have seen this being spotlight material.

Your responsiveness to the feedback provided during the review process reflects your commitment to advancing the field and strengthening your contribution. Your willingness to engage with the reviewers' insights demonstrates your dedication to delivering a high-quality presentation that will resonate with the conference attendees.

NeurIPS is a prestigious platform that attracts the brightest minds in the field, and your paper's acceptance adds to the conference's reputation for excellence. I am genuinely excited to see your work presented and discussed among peers who share your passion for pushing the boundaries of knowledge.

Congratulations once again on this well-deserved achievement.
Decision: Accept (poster)