Variational Bayesian Reinforcement Learning with Regret Bounds
Authors: Brendan O'Donoghue
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayes
reinforcement learning
utility theory
exploration
variational inference

Abstract: We consider the exploration-exploitation trade-off in reinforcement learning and show that an agent endowed with an exponential epistemic-risk-seeking utility function explores efficiently, as measured by regret. The state-action values induced by the exponential utility satisfy a Bellman recursion, so we can use dynamic programming to compute them.  We call the resulting algorithm K-learning (for knowledge) and the risk-seeking utility ensures that the associated state-action values (K-values) are optimistic for the expected optimal Q-values under the posterior.  The exponential utility function induces a Boltzmann exploration policy for which the 'temperature' parameter is equal to the risk-seeking parameter and is carefully controlled to yield a Bayes regret bound of $\tilde O(L^{3/2} \sqrt{S A T})$, where $L$ is the time horizon, $S$ is the number of states, $A$ is the number of actions, and $T$ is the total number of elapsed timesteps. We conclude with a numerical example demonstrating that K-learning is competitive with other state-of-the-art algorithms in practice.

Variational Bayesian Reinforcement Learning with Regret Bounds
Brendan O'Donoghue DeepMind, UK bodonoghue@googgee.co com
Abstract
In reinforcement learning the Q-values summarize the expected future rewards that the agent will attain. However, they cannot capture the epistemic uncertainty about those rewards. In this work we derive ated fixed point we call the 'knowledge values'.. These K-values compress both the expected future rewards and the epistemic uncertainty into single value, that high uncertainty, high reward, or both, can yield high K-values. The key principle is endow the agent with risk-seeking utility function that is carefully tuned balance exploration and exploitation. When the agent follows Boltzmann policy over the K-values it yields a Bayes regret bound of OSL") where L is the time horizon, is the number of states, A is the number of actions, and 7 is the total number of elapsed timesteps. We show deep connections of this approach to the soft-max and meximum-entrope strands of research in reinforcement learning.
Bellman operator with associ-
Introduction and related work
In reinforcement learning (RL) agent interacts with environment in episodic manner and attempts to maximize its return (54 45 In this work the environment is a Markov decision process (MDP) and consider the Bayesian case where the agent has some prior information and as it gathers data it updates its posterior beliefs about the environment. with the choice of visiting well understood states exploring the environment to determine the value of other states which might lead to a higher return. This trade-off is called the exploration- exploitation dilemma. One way to measure how well agent balances this trade-off is quantity called regret, which measures how sub-optimal the rewards the agent has received are so far, relative the (unknown) optimal policy [12]. In the Bayesian case the natural quantity to consider is the Bayes regret, which is the expected regret under the agents prior information [17].
this setting the agent faced
The optimal Bayesian policy can be formulated using belief states, but this is believed to be in- tractable for all but small problems [7]. Approximations to the optimal Bayesian policy exist, one of the most successful being Thompson sampling [53] 55) wherein the agent samples from the pos- terior over value functions and acts greedily with respect to that sample 38
27 41] It can be shown that this strategy yields both Bayesian and frequentist regret bounds under certain assump- tions 3. In practice, maintaining a posterior over value functions is intractable, and so instead the agent maintains the posterior over MDPs, and at each episode an MDP is sampled from this poste- rior, the value function for that sample is computed, and the policy acts greedily with respect to that value function. Due to the repeated sampling and computing of value functions this is practical only for small problems, though attempts have been made to extend it 37 43
Bayesian algorithms have the advantage of being able incorporate prior information about the problem and, as we show in the numerical experiments, they tend to perform better than non- Bayesian approaches in practice [17 51 49). Although typically Bayes regret bounds hold for any prior that satisfies the assumptions, the requirement that the prior over the MDP is known in advance
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is disadvantage for Bayesian methods. One common concern is about performance degradation when the prior is misspecified. In this case it can be shown that the regret increases by a multiplica- tive factor related to the Radon-Nikodym derivative of the true prior with respect to the assumed prior [8] 83.1]. In other words, a Bayesian algorithm with sub-linear Bayes regret operating under misspecified prior will still have sub-linear regret so long as the true prior is absolutely continu- ous with respect to the misspecified prior. Moreover, for any algorithm that satisfies a Bayes regret bound it is straightforward to derive high-probability regret bound for any family of MDPs that has support under the prior, in sense translating Bayes regret into frequentist regret; see 48 83.1], 38 Appendix A] for details.
In this work we endow an agent with a particular epistemic risk-seeking utility function, where "epistemic risk' refers to the Bayesian uncertainty that the agent has about the optimal value function of the MDP. In the context of RI., acting so as to maximize risk-seeking utility function which assigns higher values to more uncertain actions is a form of optimism in the face of uncertainty, a well-known heuristic to encourage exploration 21 5) Any increasing convex function could be used as a risk-seeking utility, however, only the exponential utility function has decomposition property which is required to derive a Bellman recursion I 44 20 46). We call the fixed point of this Bellman operator the 'K-values' for knowledge since they compress the expected downstream reward and the downstream epistemic uncertainty at any state-action into a single quantity. A high K-value captures the fact that the state-action has a high expected Q-value high uncertainty, or both. Following& a Boltzmann policy over the K-values yields a practical algorithm that we call 'K-learning' which attains a Bayes regret upper bounded by ( horizon, S is the number of states, A is the number of actions per state, and T is the total number of elapsed timesteps [11]. This regret bound matches the best known bound for Thompson sampling
where is the time
up to log factors (38 and is within a factor of vI. L. of the known information theoretic lower bound of (ALT)AT)
23 Appendix DJ.
The update rule we derive is similar to that used in 'soft' Q-learning (so-called since the 'hard' max is replaced with a soft-max) 6 16
18 30 47). These approaches are very closely related to maximum entropy reinforcement learning techniques which add an entropy regularization "bonus" to prevent early convergence to deterministic policies and thereby heuristically encourage exploration 2 25]. In our work the soft-max operator and entropy regularization arise naturally from the view of the agent as maximizing a risk-secking exponential utility. Furthermore, in contrast to these other approaches, the entropy regularization is not fixed hyper-paramcter but something we explicitly control (or optimize for) in order to carefully trade-off exploration and exploitation.
[57 59 28
35
The algorithm we derive in this work is based, i.e., requires estimating the full transition function for each state. There is a parallel strand of work deriving regret and complexity bounds for model-free algorithms, primarily based on extensions of Q-learning [23 58 26). We do not make a detailed comparison between the two approaches here other than to highlight the advantage that model-free algorithms have both in terms of storage and in computational requirements. On the other hand, in the numerical experiments model- based approaches tend to outperform the model- free algorithms. We conjecture that an online, model-free version of K K-learning with similar regret guarantees can be derived using tools developed by the model-free community. We leave exploring this to future work.
1.1 Summary of main results
We consider an agent endowed an epistemic risk-seeking utility function and derive a new optimistic Bellman operator that incorporates the 'value" from epistemic uncertainty about the MDP. The new operator replaces the usual max operator with a soft-max and it incor- porates 'bonus' that depends on state-action visitation. In the limit of zero uncertainty the new operator reduces to the standard optimal Bellman operator.
At each episode we solve the optimistic Bellman equation for the 'K-values' which repre- sent the utility of a particular state and action. If the agent follows a Boltzmann policy over the K-values with a carefully chosen temperature schedule then it will enjoy a sub-linear Bayes regret bound.
To the best of our knowledge this is the first work to show that soft-max operators and maximum entropy policies RI. can provably yield good performance as measured by Bayes regret. Similarly, we believe this is the first result deriving Bayes regret bound for

---

a Boltzmann policy in RL. This puts maximum entropy, soft-max operators. and Boltzmann exploration principled Bayesian context and shows that they are naturally derived from endowing the agent with an exponential utility function.
2 Markov decision processes
In Markov decision process (MDP) agent interacts with an environment in series of episodes and attempts to maximize the cumulative rewards. A finite horizon, discrete-time, discrete MDP is given by the tuple M {S, A. R P, I,, p), where S (1, (I,...,S) is the state-space, A (1....,) A} is the action-space, R8,8, a) is a probability distribution over the rewards received by the agent state taking action a at timestep I, Pt(s') a) [o. 1] is the probability the agent will transition to state s' after taking action in state at timestep L, L E IN is the episode length, and p is the initial state distribution. Concretely, the initial state s S of the agent sampled from p. then for timesteps / = 1,..., the agent is in state s E S, selects action E A. receives reward r (s, a) with mean (s. E and transitions to the next state s' with probability Pi(s' a.... After timestep L the episode terminates and the state is reset. We assume that at the beginning learning the agent does not know the reward or transition probabilities and must learn about them by interacting with the environment. We consider the Bayesian case in which the mean reward j and the transition probabilities P are sampled from a known prior Φ. We assume that the agent knows 5, A, T., and the reward noise distribution.
An agent following policy mi S A + [0, 1] at state E S time / selects action with probability TT(s,a) a). The Bellman equation relates the value of actions taken at the current timestep future returns through the Q-values and the associated value function [8, which for policy are denoted QJ E RSXA and Vi" E R$ for l = I,..., L + 1, and satisfy
Q = =T" (T) = Σ mi(s, a) Q}
aEA
for = I,...,,A L where QL+1 = 0 and where the Bellman operator for policy n at step is defined
(T a) = pu(ss a) + Σ Pls's s,a) Σ
d').
S'ES
a'EAA
The expected performance of policy æ is denoted J = Ex (T An optimal policy satisfies n² E argmax, J" and induces associated optimal Q-values and value function given by
Qi = ===T(' Q++,
Vi* = max Qi (s,a).
(2)
for = 1,..., L, where Vi+1 = and where the optimal Bellman operator is defined at step as
(T(,) = pr(s,a) + Σ Pi(8') 8, max Qi+1('',
(3)
e'ES
2.1 Regret
If the mean reward μ and transition function P are known exactly then (in principle) we could solve 2 via dynamic programming (9]. However, in practice these are not known and so the agent must gather data by interacting with the environment over series of episodes. The key trade-off is the iegloration-exploiaatii
dilemma, whereby an agent must take possibly suboptimal actions in order learn about the MDP. Here we are interested in the regret up to time T, which is how sub-optimal the agent's 's policy has been so far. The regret for an algorithm producing policies π², t = I,...,N executing on MDP M is defined as
RM(T) = EEm (F))
where N = [T/L] the number of elapsed episodes. In this manuscript we take the case where M is sampled from known prior & and we want to minimize the expected regret of our algorithm under that prior distribution. This referred to as the Bayes regret:
N
(T) = EMMOR -EM
E Eappl (Vi((v)) V=T(
(4)
3

---

In the Bayesian view of the RL problem the quantities je and P are random variables. and conse- quently the optimal Q-values Q*, policy म², and value function V are also random variables that must be learned about by gathering data from the environment. We shall denote by Fu the sigma- algebra generated by all the history before episode & where Fi @ and we shall use IE to denote E( Fe), the expectation conditioned on Ft- For example, with this notation E' Q' denotes the expected optimal Q-values under the posterior before the start of episode t.
3 K-learning
Now we present Knowledge Learning (K-learning) a Bayesian RL algorithm that satisfies a sub- linear Bayes regret guarantee. In standard dynamic programming the Q-values are the unique fixed point of the Bellman equation, and they summarize the expected future reward when following a particular policy. However, standard Q-learning is able to incorporate any of the uncertainty about future rewards or transitions. In this work we develop a new Bellman operator with associated fixed point we call the 'K-values' which represent both the expected future rewards and the uncer- lainty about those rewards. These two quantities are compressed into single value by the use of an exponential risk-sceking utility function, which is tuned to trade-off exploration and exploitation. In this section we develop the intuition behind the approach and defer all proofs to the appendix. We begin with the main assumption that we require for the analysis (this assumption standard, see, e.g. [41)
Assumption 1. The mean rewards are bounded in [0,1] almost surely with independent priors, the reward noise is additive --sub-Gauusian and the prior over transition functions is independent Dirichlet.
3.1 Utility functions and the certainty equivalent value
A utility function u IR + R measures an agents preferences over outcomes [56]. If u(x) >> u(y) for some x, y E IR then the agent prefers x to y, since it derives more utility from x than from y- If is convex then it is referred as risk-seeking, since Eu(X) 2 u(EX) for random variable X due to Jensen's ' inequality. The particular utility function we shall use is the exponential utility u(xx) r(exp(x/T)
1) for some 7 2 O. The certainty equivalent value of random variable under utility u measures how much guaranteed payoff is equivalent to random payoff, and for (s, a) under the exponential utility given by
() a) = "E' (s. a)) = T log E' exp(Q1
(5)
This the key quantity we use summarize the expected value and the epistemic uncertainty into single value. As an example, consider a stochastic multi-armed bandit (i.e., an MDP with L= 1 and S 1) where the prior over the rewards and the reward noise are independent Gaussian distributions. At round the posterior over Q* (a) is given by NN(,á (ot)²) for some μá and o for each action a, due to the conjugacy of the prior and the likelihood. In this case the certainty equivalent value can be calculated using the Gaussian cumulant generating function, and is given Evidently, this value combining the expected reward and
by (a(a) = p/ + (1/2)(a1)²/m) the epistemic uncertainty into single quantity with controlling the trade-off, and the value is higher for arms with more epistemic uncertainty. Now consider the policy x' r'(a) xx exp(O (a)/T)) This policy will in general assign greater probability to more uncertain actions, i.e., the policy is optimistic. We shall show later that for a carefully selected sequence of temperatures Tr we can ensure that this policy enjoys a O(VTT') Bayes regret bound for this bandit case. In the more general RL case the posterior over the Q-values is complicated function of downstream uncertainties and is not a simple distribution like a Gaussian, but the intuition is the same.
The choice of the exponential utility may seem arbitrary, but in fact it is the unique utility function that has the property that the certainty equivalent value of the sum of two independent random variables is equal to the sum of their certainty equivalent values 1 20 46). This property crucial for deriving a Bellman recursion, which necessary for dynamic programming to be applicable.

---

3.2 Optimistic Bellman operator
risk-seeking agent would compute the certainty equivalent value of the Q-values under the en- dowed utility function and then act to maximize this value. However, computing the certainty equivalent values in full MDP is challenging. The main result (proved in the appendix) that Q' satisfies a Bellman inequality with particular optimistic (i.e., risk-seeking) Bellman operator, which for episode t and timestep / is given by
(1 (L (T, Ki)(s, a) = E'sss a)+ 27(n((s,a
P(' | (T log Σ exp(Ki(s', d'EA
d'ES
(6)
for inputs 7 2 O, K₁ R where (s, a) the visitation count of the agent to state-action (s,a) at timestep I before episode and (- V = max(-.) 1). Concretely we have that for any (s,a) A
(s) (T, (s,)),, 1 1= 1.....,
From this fact we show that the fixed point of the optimistic Bellman operator yields guaranteed upper bound on º³, i.e..
( (i,,) 1- 1.,,..., (Ki Li I.,...,
We refer the fixed point the 'K-values' (for knowledge) and we shall show that they are sufficiently faithful approximation of Q' to provide a Bayes regret guarantee when used instead of the certainty equivalent values a policy.
Let us compare the optimistic Bellman operator E to the optimal Bellman operator T defined in B). The first difference is that the random variables μ and P' are replaced with their expectation under the posterior; in T they are assumed to be known. Secondly, the rewards in the optimistic Bellman operator have been augmented with bonus that depends on the visitation counts n'. This bonus encourages the agent to visit itate-actions that have been visited less frequently. Finally, the hard-max of the optimal Bellman operator has been replaced with soft-max. Note that the limit of zero uncertainty in the MDP (take (s, + oc for all (s, a)) we have B (0. T and we recover the optimal Bellman operator, and consequently in that case Kf a) (s. Qi (s,a) a). In other words, the optimistic Bellman operator and associated K-values generalize the optimal Bellman operator and optimal Q-values to the epistemically uncertain case, and the limit of zero uncertainty we recover the optimal quantities.
3.3 Maximum entropy policy
An agent that acts to maximize its K-values is (approximately) acting to maximize its risk-seeking utility. In the appendix we show that the policy that maximizes the expected K-values with entropy regularization is the natural policy to use, which is motivated by the variational description of the soft-max
Σ ((ss + ((((S())) Ta log Σ exp(Ki(s,a)/7)) aEA
max A
(8)
AEAA
where AA is the probability simplex of dimension 1 and H is entropy, Lee, H(T((s) = EnEA (s a) log (T(s,a) a) [3]. The maximum is achieved by the Boltzmann (or Gibbs) dis- tribution with temperature Tr
({, a) x (s,
This variational principle also arises in statistical mechanics where Eq. ( refers to the negative Helmholtz free energy and the distribution in Eq. (9) describes the probability that the system
temperature 7. is in a particular 'state' 222]
3.4 Choosing the risk-secking parameter temperature
The optimistic Bellman operator, K-values, and associated policy depend on the parameter 7r. By carefully controlling this parameter we ensure that the agent balances exploration and exploitation.
5

---

Algorithm K-learning for episodic MDPs
Input: MDP M = [S,A, R, L, for episode t = 1, .2....do do
calculate 7 using (T) or
set k = 0
compute K = B) (T. K 141) for .,....: using (
execute policy o (s, a) & exp(Ki(s, a)/T)), for 1 L,...,L
end for
We present two ways to so, the first of which is to follow the schedule
(
L2) + logt)
Te
(10)
4t log A
Alternatively, we find the that yields the tightest bound in the maximal inequality in 13 This turns out to convex optimization problem
(Tlog Σ (x,((K((s,0)/7)
minimize
aEA
(11)
subject to
Ki 2 (T,KK))),
== I
KL+1 = 0,
with variables т 2 0 and K2 E RSXA, 1 1....L L + 1. This is convex jointly in and K since the Bellman operator is convex both arguments and the perspective of the soft-max term in the objective is convex [IO). This generalizes the linear programming formulation of dynamic programming to the case where we have uncertainty over parameters that define the MDP [45] 9
Problem (11) is an exponential cone program and can be solved efficiently using modern methods
32 33
31]
Both of these schemes for choosing 7. yield a Bayes regret bound, though in practice the t; obtained by solving IT tends to perform better. Note that since actions are sampled from the stochastic policy in Eq. we refer to K-learning randomized strategy. If K-learning is run with the optimal choice of temperature of then additionally stationary strategy in that the action distribution depends solely on the posteriors and is otherwise independent of the time period 49)
3.5
Regret analysis
Theorem 1, Under assumption the K-learning algorithm satisfies Bayes regret bound
BR,(T) s + log A(1 log T/L)
(12)
= -(13///5AT)
The full proof is included in the appendix. The main challenge is showing that the certainty equiva- lent values Q' satisfy the Bellman inequality with the optimistic Bellman operator (6). This is used to show that the K-values upper bound Q' (Eq. (7) from which we derive the following maximal inequality
E' max (s. < log Σ ((s,)) S v. log Σ (s aEAA
(13)
aE.A
From this and the Bellman recursions that the K-values and the Q-values must satisfy, we can 'unroll' the Bayes regret (4) over the MDP. Using the variational description of the soft-max in Eq. ( we can cancel out the expected reward terms leaving us with sum over 'uncertainty" terms. Since the uncertainty is reduced by the agent visiting uncertain states we can bound the remaining terms using a standard pigeon-hole argument. Finally, the temperature T free-parann rree-parameter for each episode we can choose it so to minimize the upper bound. This yields the final result.

---

t=u
t=2
tEL
Figure 1: The DeepSea MDP
The Bayes regret bound in the above theorem matches the best known bound for Thompson sampling up to log factors (once the regret bound from [38] is translated into the slightly more general case we consider here where the mean reward and transition function can differ for each timestep / = 1, L). Moreover, the above regret bound is within factor of VL of the known information Appendix D).
theoretic lower bound of R(T) 2 Q(TVSAT) 23
Intuitively speaking, K-values higher where the agent has high epistemic uncertainty. Higher K-values will make the agent more likely to take the actions that lead to those states. Over time states with high uncertainty will be visited and the uncertainty about them will be resolved. The temperature parameter is controlling the balance between exploration and exploitation.
Numerical experiments
In this section we compare the performance both the temperature scheduled and optimized tem- perature variants of K-learning against several other methods in the literature. We consider small tabular MDP called DeepSea (39 shown in Figure which can be thought of as an unrolled version L x L grid where the agent starts at the top row and leftmost column. At each time-period the agent can move left or right and descends one row. The only positive reward at the bottom right cell. order to reach this cell the agent must take the 'right' action every timestep. After choosing action 'left' the agent receives random reward with zero mean, and after choosing right the agent receives a random reward with small negative mean. At the bottom rightmost corner of the grid the agent receives random reward with mean one. Although this is a toy example it provides a challenging 'needle in a haystack' exploration problem. Any algorithm that does exploration via simple heuristic like local dithering will take time exponential the depth to reach the goal. Policies that perform deep exploration can learn much faster 388 43).
of the RiverSwim environment [52]. This MDP can be visualized
show the time required to "solve' the problem as function of the depth of the environment, averaged over 5 seeds for each algorithm. We define 'time to solve" to be the first episode at which the agent has reached the rewarding state in least 10% of the episodes so far. If an agent fails to solve an instance within 10t episodes we do not plot that point, which is why some of the traces appear abruptly stop. We compare
In Figure
dithering approaches, Q-learning with epsilon- greedy (c 0.1) and soft-Q-learning [18] (T = 0.05). against principled exploration strategies RLSVI [39 UCBVI (7]. optimistic Q-learning (OQL) 23 BEB 24). Thompson sampling [38] and two variants of K-learning, one using the schedule (IO) and the other using the optimal choice 7. from solving (1I.. Soft Q-learning is similar to K-learning with two major differences: the temperature term is fixed hyperparameter and there is no optimism bonus added to the rewards. These differences prevent soft Q-learning from satisfying a regret bound and typically it cannot solve difficult exploration tasks in general (36]. We also ran comparisons against BOLT 4. UCFH (14)
7

---

10
K-learning. ti
Episodes until 90% failure
10
K-leaming, Fç'
Thompson
UCBVI
10"
E-greedy
BEB
RLSVI
10
OQL
Soft-Q
21L-1)
10'
10
20
30
40
50
DeepSea Size
Figure 2: Learning time on DeepSea.
and UCRL2 [21] but they did not perform much better than the dithering approaches and contributed the clutter in the figure so do not show them.
As expected, the two 'dithering' approaches are unable to handle the problem as the depth exceeds small value; they fail to solve the problem within 10 episodes for problems larger than L 6 for epsilon-greedy and = 14 for soft soft-Q-learning. These approaches are taking time exponential in the size of the problem solve the problem, which is seen by comparing their performance the grey dashed line which plots 24-1 The other approaches scale more gracefully, however clearly Thompson sampling and K-learning are the most efficient. The optimal choice of K-learning appears to perform slightly better than the scheduled temperature variant, which is unsurprising since is derived from tighter upper bound on the regret.
Figures and 4 we show the progress of K-learning using of and Soft Q-learning for a single seed running the L = 50 depth DeepSea environment. In the top row of each figure we show the value each state over time, defined for K-learning as
(s) Ti log Σ exp(KK(s.a)/T1)
(14)
PEA
and analogously for Soft Q-learning. The bottom row shows the log of the visitation counts over time. Although both approaches start similarly, they quickly diverge in their behavior. If we examine the K-learning plots, it is clear that the agent visiting more of the bottom row as the episodes proceed. This is driven by the fact that the value, which incorporates the epistemic uncertainty, is high for the unvisited states. Concretely, take the / = 300 case; at this point the K-learning agent has yet visited the rewarding bottom right state, but the value is very high for that region of the state space and shortly after this it reaches the reward for the first time. By the t = 1000 plot the agent travelling along the diagonal to gather the reward consistently. Contrast this to Soft Q-learning. where the agent does not make it even halfway across the grid after & 1000 episodes. This is because the soft Q-values do not capture any uncertainty about the environment, so the agent has no incentive to explore and visit new states. The only exploration that soft Q-learning is performing merely the local dithering arising from using a Boltzmann policy with a nonzero temperature. Indeed, the soft value function barely changes in this case since the agent is consistently gathering zero-mean rewards; any fluctuation the value function arises merely from the noise in the random rewards.
5 Conclusions
In this work we endowed a reinforcement learning agent with risk-seeking utility, which encour- ages the agent to take actions that lead to less epistemically certain states. This yields a Bayesian

---

10
10
10
20
20
20
20
20
30
30
30
30
30
40
40
40
40
40
20
40
40
20
logiCounts)
logiCounts)
log(Counts)
log(Counts)
logiCounts)
0
0
10
10
10
10-
10-
20
20
20
20-
20
30
30-
30
30
30
40
40
40
40
40
20
20
40
(a) L
(b) (
(c) 100.
(d)
300.
(e)
1000.
Figure 3: Value (as defined in (14 and log visitation count for each state in DeepSea under K- learning using 77. Darker color indicates larger value.
10
10
10
10-
10
20
20
20
20-
20
30
30
30
30
30
40
40
40
40
40
20
20
40
logiCounts)
IngiCounts)
log(Counts)
logiCounts)
log(Counts)
0
0
0
100
10-
10
10-
10
20
20
20
20
20
30
30
30
30
50
40
40
40
40
20
40
(a) t
(b) 8
(c) 100.
(d) 300.
(e)
1000.
Figure 4: Value (as defined in (14) and log visitation count for each state in DeepSea under soft
Q-learning. Darker color indicates larger value.
algorithm with bound regret which matches the best-known regret bound for Thompson sam- pling up to log factors and is close to the known lower bound. We call the algorithm 'K-learning', since the 'K-values' capture something about the epistemic knowledge that the agent can obtain by visiting each state-action. In the limit of zero uncertainty the K-values reduce to the optimal Q-values.
Although K-learning and Thompson sampling have similar theoretical and empirical performance, K-learning has some advantages. For one, to the case of two-player games and continues to enjoy a sub-linear regret bound, whereas Thomp- son sampling can suffer linear regret (34). Secondly, Thompson sampling requires sampling from the posterior over MDPs and solving the sampled MDP exactly at each episode. This means that Thompson sampling does not have a 'fixed' policy at any given episode since determined by the posterior information plus sampling procedure. This is typically deterministic policy, and it can vary significantly from episode episode. By contrast K-learning has single fixed policy at each episode, the Boltzmann distribution over the K-values, and it is determined entirely from the posterior information (i.e., no sampling). Moreover, K-learning requires solving a Bellman equa- tion that changes slowly more data is accumulated, so the optimal K-values at one episode are close to the optimal K-values for the next episode, and similarly for the policies. This suggests the possibility of approximating K-learning in online manner and making of modern deep RL
recently shown that K-learning extends naturally

---

techniques such as representing the K-values using a deep neural network [29]. This is in line with the purpose of this paper, which is not to get the best theoretical regret bound, but instead derive an algorithm that is close to something that is practical to implement in real RI. setting. Soft-max updates, maximum-entropy RI,, and related algorithms are very popular in deep RI.. However, they are not typically well motivated and they cannot perform deep-exploration. This paper tackles both those problems since the soft-max update, entropy regularization, and deep-exploration all fall out naturally from utility maximization point of view. The popularity and success of these other ap- proaches, despite their evident shortcomings data efficiency, suggest that incorporating changes derived from K- K-learning could yield big performance improvements in real- world settings. We leave exploring that avenue to future work.
Acknowledgments and Disclosure of Funding
I would like to thank Ian Osband, Remi Munos, Vlad Mnih, Pedro Ortega, Sebastien Bubeck, Csaba Szepesvári, and Yee Whye Teh for valuable discussions and clear insights. I received no specific funding for this work.
References
[1] A. E. Abbas. Invariant utility functions and certain equivalent transformations, Decision Anal- ysis, 4(1):17-31, 2007.
[2] A. Abdolmaleki, J. T. Springenberg. Tassa, R. M. N. Heess, and M. Riedmiller. Maximum posteriori policy optimisation. In International Conference on Learning Representations (ICLR), 2018.
[3] S. Agrawal and N. Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):30, 2017.
[4] M. Araya, O. Buffet, and V. Thomas. Near-optimal BRL using optimistic local transitions. In Proceedings of the 29th International Conference on Machine Learning (ICMI.), 2012.
[5] P. Auer, N. Cesa-Bianchi and P. Fischer. Finite-time analysis of the multiarmed bandit prob- lem. Machine learning, 47(2-3):235-2555 2002.
[6] M. G. Azar, V. Gómez, and H. J. Kappen. Dynamic policy programming. Journal of Machine Learning Research, 13(00953307733245, 2012.
[7] M. G. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272, 2017.
[8] R. Bellman. Dynamic programming. Princeton University Press, 1957.
[9] D. P. Bertsekas. Dynamic programming and optimal control, volume 1. Athena Scientific, 2005.
[10] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[11] N. Cesa-Bianchi, C. Gentile, G. Neu, and G. Lugosi. Boltzmann exploration done right. In Advances in Neural Information Processing Systems, pages 6287-6296, 2017.
[12] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[13] T. M. Cover and J. A. Thomas. Elements of information theory. John Wiley & Sons, 2012.
[14] C. Dann and E. Brunskill. Sample complexity of episodic fixed-horizon reinforcement learn- ing. In Advances in Neural Information Processing Systems, pages 2818-2826 2015.
[15] A. Domahidi, E. Chu, and Boyd. ECOS: An SOCP solver for embedded systems. In European Control Conference (ECC), pages 3071-3076, 2013.
10

---

[16] R. Fox, A. Pakman, and N. Tishby. Taming the noise in reinforcement learning via soft updates. 2015.
arXiv preprint
[17] M. Ghavamzadeh, S. Mannor, Pineau, and A. Tamar. Bayesian reinforcement learning: A survey, Foundations and Trends()) in Machine Learning, 8(5-6):359-483, 2015.
[18) T. Haarnoja, H. Tang, P. Abbeel, and S. Levine. Reinforcement learning with deep energy- based policies. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
[19] J. Hadar and W. R. Russell. Rules for ordering uncertain prospects. The American economic review, (91):53,3,, 1969.
[20] R. A. Howard. Value of information lotteries. IEEE Transactions on Systems Science and Cybernetics, 3(1):54 60, 1967.
[21] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr): 1600, 2010.
[22] E. T. Jaynes. Information theory and statistical mechanics. Physical review, 106(4):620, 1957.
[23] C. Jin, Z. Allen-Zhu, S. Bubecck and M. I. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, volume 31, 2018
[24] J. Z. Kolter and A. Y. Ng. Near-Bayesian exploration in polynomial time. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 513-520. ACM, 2009.
[25] S. Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: 1805.0090, 2018
[26] G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. arXiv preprint arXiv:2006.00441, 2020.
[27] Z. C. Lipton, J. Gao, L. Li, X. Li, F. Ahmed, and L. Deng. Efficient exploration for dialogue policy learning with BBQ networks & replay buffer spiking. arXiv preprint urXiv:1600 1608.05081, 2016.
[28] 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 Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 1928-1937, 2016.
[29] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):5295555 023999-33,000 02 2015.
[30] 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.
[31] B. O'Donoghue. Operator splitting for a homogeneous embedding of the linear complemen- tarity problem. SIAM Journal on Optimization. 3103):1999-2033, 2021.
[32] B. O'Donoghue, Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 1068, June 2016.
[33] B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd. SCS: Splitting conic solver, version 2.0.2. https://qithub wttpccwgcpcccc..c.ooocccc scs Nov. 2017.
[34] B. O'Donoghue, T. Lattimore, and I. Osband. Stochastic matrix games with bandit feedback. arXiv preprint arXiv:2006.0511 0455, 2020.
[35] B. O'Donoghue, R. Munos, K. Kavukcuoglu, and V. Mnih. Combining policy gradient and Q-learning In International Conference on Learning Representations (ICLR), 2017.
11

---

[36] B. O' D'Donoghue, I. Osband, and C. Ionescu. Making sense of reinforcement learning and prob- abilistic inference. In International Conference on Learning Representations (ICLR), 2020.
[37] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped DQN.
In Advances In Neural Information Processing Systems, pages 4026-4034, 2016.
[38] I. Osband, D. Russo, and B. Van Roy. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[39] I. Osband, D. Russo, Z. Wen, and B. Van Roy. Deep exploration via randomized value func- 2017.
tions. arXiv preprint arXiv:
[40] Osband and B. Van Roy. Gaussian-Dirichlet posterior dominance sequential learning- arXiv preprini arXiv: 7702.4 2017.
[41] L. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
[42] Osband, B. Van Roy, and Z. Wen. Generalization and exploration via randomized value functions. arXiv preprint arXiv: 1402.0402..333 2014.
[43] B. ODonoghue, I. Osband, R. Munos, and V. Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845, 2018.
[44] J. Pfanzag. A general theory of measurement applications to utility. Naval Research Logistics (NRL), 6(4):283-294, 1959.
[45] M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[46] H. Raiffa. Decision Analysis: Introductory Lectures on Choices under Uncertainty. Addison Wesley, 1968.
[47] H. Richemond and B. Maginnis. A short variational proof of equivalence between policy gradients and soft Q learning, arXiv preprint arXiv:1712.086500 2017.
[48] D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 122111321 2014.
[49] D. J. Russo, B. Van Roy. A. Kazerouni, I. Osband, and Z. Wen. A tutorial on thompson sampling. Foundations and Trends Machine Learning, 11(1):1 2018.
[50] A. Serrano. Algorithms for unsymmetric cone optimization and an implementution for prob- lems with the exponential cone. PhD thesis, Stanford University, 2015.
[51] J. Sorg, S. Singh, and R. L. Lewis. Variance-based rewards for approximate Bayesian rein- forcement learning. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, page 1,457, 2010.
[52] A. L. Strehl and M. L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 7498):1309-131,, 2008
[53] M. Strens. A Bayesian framework for reinforcement learning. In ICML., pages 943-950, 2000.
[54] R. Sutton and A. Barto. Reinforcement Learning: an Introduction. MIT Press, 1998.
[55] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294, 1933.
[56] J. Von Neumann and O. Morgenstern. Theory of games and economic behavior (commemora- tive edition). Princeton university press, 2007.
[57] R. J. Williams and J. Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-268 1991.
12

---

[58] Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model-free reinforcement learningvia reference- advantage decomposition. Advances Neural Information Processing Systems, 33, 2020.
[59] B. D. Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University, 2010.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This paper
a purely theoretical work with little societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [No] We included description of the data generation process for the simulations we ran.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] These experiments involved no training on external data.
(c) Did you report error bars (e.g.. with respect to the random seed after running exper- iments multiple times)? [No] produced Fig 2 with error bars, but it looked very cluttered and obscured the message without providing any additional insight.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] Included in appendix.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "pe2S09vsWM", "reviewer": "Reviewer_biBz", "summary": "The author considers the setting of the MDP is sampled from a known prior $\\phi$ rather than a fixed unknown one, which belongs to Bayesian reinforcement learning. Under this setting, the author firstly introduces an expected upper bound on the optimal Q-value $Q^{\\star}_l(s, a)$, then introduces a new operator called optimistic Bellman operator. This operator combines the principle of using upper confidence bound to encourage exploration and the randomness influence of the transition kernel and rewards, providing a sequence of optimistic estimation of the optimal Q-value. Furthermore, it also uses a soft-max exploration policy to sample from the environment.\n\nBased on these components, K-learning is proposed and has been proved to enjoy a tight Bayes regret bound $O(\\sqrt{L^3SAT})$. More numerical experiments are conducted to show the performance with comparisons to existing methods.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nIn the Bayesian reinforcement learning setting (MDP is sampled from a known prior $\\phi$), the algorithm K-learning is proposed to better balance exploration-exploitation by adding an exploration bonus and choosing the risk-seeking parameter (similar to the parameter in soft-Q-learning). Since the exploration bonus and the soft-Q-learning has already been proposed before, this work can be seen as proposing an algorithm using these principles in a new setting, which is of moderate originality.\n\nQuality:\nThe results seem reasonable, while I didn't read all the proof in the appendix.\n\nClarify:\nThe paper is well-organized and is clear. \n\nSignificance:\n1. It will be better to introduce more application scenarios that satisfy the Bayesian reinforcement learning, since the assumption of transition kernel is under some known prior is not well-explained in this work.\n2. Although intuition is introduced in lines 169-179, line 191, etc, the technical difficulty or novelty is not mentioned enough.\n3. The contributions of this work are not well-compared with existing works such as [1], [2], which also utilize exploration bonuses and even add more variance reduction techniques.\n\n\n\n\n[1] Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? In Advances\nin Neural Information Processing Systems, pages 4863–4873\n[2] Zhang, Z., Zhou, Y., and Ji, X. (2020b). Almost optimal model-free reinforcement learning via reference- advantage decomposition. Advances in Neural Information Processing Systems, 33.\n[3] Li, Gen, et al. \"Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction.\" arXiv preprint arXiv:2006.03041 (2020).\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Note:\n1. There is no definition for $\\sigma$ in line 161 and later. Furthermore, since $\\sigma$ appears in the regret bound in the main theorem 1, it is hard to tell whether $\\sigma$ is a universal constant or is actually related to the important parameters $L, T, S, A$.\n\n2. The assumptions in this paper seem only for the convenience of the proof, such as ensuring the Dirichlet prior to the transition in Assumption 4. It seems not reasonable in the real world? Can you justify these assumptions more carefully?\n3. This is just a question that makes me confusing:\nIt seems the author utilizes a Hoeffding-style exploration bonus. However, researchers can only achieve $O(\\sqrt{L^4SAT})$ regret bound in [1] using such bonus, while achieves $O(\\sqrt{L^3SAT})$ using Bernstein-style exploration bonus. Is it owing to some assumptions in the paper or some other reason?\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mdDRI0HZndt", "reviewer": "Reviewer_DyxF", "summary": "The paper proposes K-learning, a reinforcement learning exploration heuristic with Bayesian regret bounds.\nThe authors adopt a Bayesian perspective under which long-term (Q-)values have epistemic uncertainty associated with them. They argue that exploration behaviour can be induced by maximising a particular (exponential) utility function of the resulting distributions. It is shown, that these utility scores obey a Bellman-like operator and can be computed using dynamic programming and an algorithm for episodic settings is proposed. \nThe authors link the optimal policy maximising the new objective to entropy regularised approaches, discuss the optimal selection of a temperature parameter governing risk-sensitivity and provide formal regret bounds under certain assumptions regarding the structure of the agents prior.\nFinally, K-learning is compared empirically to a number of exploration baselines where it performs competitively.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The development of principled exploration exploration strategies for reinforcement learning is an active area of research and as such this work concerns a highly relevant problem. \nI hadn't seen the ``````  utility-based'' perspective on deriving policies from Q-value distributions previously and found it compelling and useful. It raises interesting question regarding the existence of other utilities that may induce behaviours of interest (e.g. pessimistic/risk-averse for safety critical domains etc.) and admit Bellman like updates.\n\nThe paper overall is well-structured and provides a good intuition for the presented approach.\n\nA couple of points for improvements are listed below:\n\nFirstly, I think the discussion of limitations could be expanded. In particularly, an analysis of the run-time complexity seems useful. My understanding is, that computation of K-values requires a full back-up across the entire state-action space and horizon which seems to be equivalent to the solution of a sampled MDP in Thompson sampling. As this was criticised as too costly in the introduction, it might indicate that K-Learning suffers from similar scalability issues.\n\nAdditionally, it would be valuable to know, how K-learning might relate to discounted formulations, continuous domains or belief structures that do not match the assumptions of the regret analysis -- all of which to my knowledge Thompson sampling can cope with. \n\nThe related work section might also need to be expanded to include approaches focussing on (Bayesian) exploration bonuses (BEB, VBRB, etc.). A number of these come with regret bounds and seem to have a similar structure to the K-scores, warranting further discussion. \n\nFinally, I found the mathematical notation and derivation difficult to follow in a few places.\nIn particular, there are no brackets for expectations making it difficult to follow what they are computed of / with respect to.\nThe symbols $\\rho$ (Eq. 4) and $\\sigma$ (Eq. 5) are not defined as far as I can tell.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "He-zuFEY94", "reviewer": "Reviewer_5rQg", "summary": "This paper studies the problem of Bayesian RL. The proposed algorithm is based on a soft-Q backward propagation and achieves regret bound of $\\tilde{O}(L\\sqrt{TSA})$.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well written and the proofs seem correct for me. The authors show that soft-Q backward propagation is powerful to guarantee good regret performance by tuning the temperature parameter properly.\n\nMinor comments:\n1. It might be incorrect to claim that the $\\tilde{O}(L\\sqrt{SAT})$ regret bound is tight. In finite-horizon case, the general minimax regret lower bound is $\\Omega(\\sqrt{L^3XAK})$, where $K=T/L$ is the number of episodes and $X=S/L$ is the number of states per layer. There is still a $\\sqrt{L}$ gap between the proposed upper bound and lower bound.\n\n2. The second way to find $\\tau_{t}$ is unnecessary since the final selection of $\\tau_{t}$ could be simple.\n\n3. eq(23): $=\\to \\leq $;\n\n4. Line541 equation (c): it is better to highlight that the convexity of $\\log(E[\\exp(X)])$ is used.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "There is no ethical issues.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "8Rv-6grXk3a", "reviewer": "Reviewer_AGCq", "summary": "This paper gives variational Bayesian reinforcement learning thereotical results with regret bounds  and an algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers the exploration-exploitation trade-off in reinforcement learning and show that an agent endowed with an exponential epistemic-risk-seeking utility function explores efficiently, as measured by regret.\n\nSeveral techniques are incorporated to get the Bayes regret.\n\nI think the theoretical result is interesting. However, the experiments are not sufficient at the current stage. \n\na. The paper assumes the MDP is time-inhomogeneous (see assumption 1) and states that by an unrolling procedure the method can be used to scenarios unfitting this assumption. Please give experiments to show the performance in this case. \n\nb. The experiments are simple with a deepsea environment. Could the method in the paper be used to more complex and real environments and be compared with more SOTA methods?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes K-learning, a reinforcement learning exploration algorithm with Bayesian regret bounds. The paper is in a tabular setting that works for an interesting exponential epistemic-risk-seeking utility function.  Although the regret bounds may not be tight, most of the reviewers believe that the contribution is sufficient for acceptance. The experiment part is also a plus.
Decision: Accept (Poster)