Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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})$.
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.

Minor comments:
1. 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.

2. The second way to find $\tau_{t}$ is unnecessary since the final selection of $\tau_{t}$ could be simple.

3. eq(23): $=\to \leq $;

4. Line541 equation (c): it is better to highlight that the convexity of $\log(E[\exp(X)])$ is used.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

Based 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.

main_review: Originality:
In 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.

Quality:
The results seem reasonable, while I didn't read all the proof in the appendix.

Clarify:
The paper is well-organized and is clear. 

Significance:
1. 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.
2. Although intuition is introduced in lines 169-179, line 191, etc, the technical difficulty or novelty is not mentioned enough.
3. 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.




[1] Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? In Advances
in Neural Information Processing Systems, pages 4863–4873
[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.
[3] Li, Gen, et al. "Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction." arXiv preprint arXiv:2006.03041 (2020).


limitations_and_societal_impact: Note:
1. 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$.

2. 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?
3. This is just a question that makes me confusing:
It 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?
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper gives variational Bayesian reinforcement learning thereotical results with regret bounds  and an algorithm.
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.

Several techniques are incorporated to get the Bayes regret.

I think the theoretical result is interesting. However, the experiments are not sufficient at the current stage. 

a. 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. 

b. 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?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes K-learning, a reinforcement learning exploration heuristic with Bayesian regret bounds.
The 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. 
The 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.
Finally, K-learning is compared empirically to a number of exploration baselines where it performs competitively.

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. 
I 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.

The paper overall is well-structured and provides a good intuition for the presented approach.

A couple of points for improvements are listed below:

Firstly, 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.

Additionally, 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. 

The 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. 

Finally, I found the mathematical notation and derivation difficult to follow in a few places.
In particular, there are no brackets for expectations making it difficult to follow what they are computed of / with respect to.
The symbols $\rho$ (Eq. 4) and $\sigma$ (Eq. 5) are not defined as far as I can tell.



limitations_and_societal_impact: -
review_title: null

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)