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.
Paper
References (85)
Scroll for more · 38 remaining
Similar papers
Peer review
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. EDIT AFTER DISCUSSION I revised my score from 3 to 7.
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. I 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. Asmuth, J. and Littman, M. Learning is planning: Near Bayes-optimal reinforcement learning via Monte-Carlo tree search. In UAI, 2011. Asmuth, 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. Guez, A., Silver, D., and Dayan, P. Efficient bayes-adaptive reinforcement learning using sample-based search. In NIPS, 2012. Strens, 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.
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.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
1 poor
Contribution
3 good
Limitations
Unclear, as this paper is not properly positioned with respect to existing work.
Updated evaluation
Following the discussion, here's my updated evaluation. I think there's an interesting contribution in this paper that could be published, but there are serious issues with presentation that make me hesitate to recommend acceptance. I don't agree with the framing of the paper, I think there's a substantial amount of discussion of existing literature that's missing, and, most importantly, the limitations of the proposed method are not discussed clearly enough. I think the key contribution is a tractable optimization objective, VAPOR, that approximates the optimal policy, correctly taking into account the epistemic uncertainty. The key insight is to optimize in the space of occupancy measures, targeting the occupancy measure corresponding to the optimal policy. I hesitate to call it Bayesian inference, since there aren't really any observations or posteriors in the usual sense. The "variational approximation" of VAPOR is also hardy justified. The solution of VAPOR is shown to be an upper bound on the expected reward of the optimal policy, but that of itself doesn't guarantee anything. The bound on KL between VAPOR policy and the optimal policy is self-referential. Ultimately, the justification of the algorithm is derived from the regret analysis, which is fine, but that's specifically not about the inference interpretation. I suppose it is debatable whether this whole procedure is in some sense Bayesian inference, but claims in published papers should not be debatable. Separately from the framing issue, the applicability of VAPOR is quite limited (I discuss the proposed extensions below). Specifically, there are two significant limitations: 1. VAPOR is only applicable in the tabular setting, and its optimization space grows with the product of states, actions, and time steps. 2. VAPOR can only handle epistemic uncertainty over reward distribution, and not the transition dynamics. I think those limitations are acceptable, but they need to be stated very clearly throughout the paper. As is, they are absent from the abstract and not prominently stated in the paper. The extension to uncertain transition dynamics relies on very restrictive assumptions. It's bad enough to require Dirichlet priors, but I think assuming independence is even worse. I don't mind a result like this being included, but again it should be very clear what the limitations are, along with some examples of priors which do and don't satisfy those assumptions. It's even less clear to me what happens to those assumptions later in the process, as beliefs are updated. VAPOR-lite, applicable in a non-tabular setting, is described very briefly and only in the appendix. If the authors want to claim that VAPOR is applicable outside of the tabular setting, VAPOR-lite needs to be given a prominent sport in the main body of the paper, with adequate analysis. As is, the discussion of existing literature is lacking, but I think the authors' responses cover the shortcomings. They just need to be included in the paper in some coherent form. Finally, this is all assuming that the theoretical analysis of the convergence bounds is correct. I'm not competent to check it, so I'm relying on the other reviewers for that. Overall, I think there's a good contribution here, but the authors oversell the paper quite a bit. Either walking the claims back or providing additional evidence for the questionable claims would work, but I think the latter would necessitate another round of reviewing.
Response to Reviewer MCkd
We appreciate the reviewer’s involved discussion. We wish to clarify some claims made by the reviewer. - “*There aren't really any observations or posteriors in the usual sense*”. Our object of interest is $\mathbb{P}_{\Gamma^\star}$, the **posterior** probability of state-action optimality conditioned on **observed data**. Computing this exactly requires Bayesian inference. - The variational approximation and regret analysis are “*debatable / hardly justified*”. **RL is both inference and control**: it is important to analyze the control behavior resulting from our inference framework, and we believe regret is a relevant measure of performance. Our approach is ‘variational’ because we replace exact inference of an intractable posterior $\mathbb{P}_{\Gamma^\star}$ with a (convex) optimization problem. - “*VAPOR can only handle epistemic uncertainty over reward distribution, and not the transition dynamics*”. Lemma 7 establishes an equivalence relationship which implies that VAPOR can handle epistemic uncertainty in the transition dynamics. - “*The bound on KL between VAPOR policy and the optimal policy is self-referential*”. The bound relates the KL divergence of the policies to the absolute difference between the value functions. 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). - “*The solution of VAPOR is shown to be an upper bound on the expected reward of the optimal policy, but that of itself doesn't guarantee anything [...] The justification of the algorithm is derived from the regret analysis*”. The upper bound property and the concentration property is what guarantees the regret bound. The upper bound is ‘optimism’, an idea that is very standard in reinforcement learning. - “*VAPOR is only applicable in the tabular setting, and its optimization space grows with the product of states, actions, and time steps.*” This is basically the case for all RL algorithms (without suitable parametrization) too. The point is to properly analyze our framework and obtain a guaranteed regret bound (on which we focus our paper), then transfer to more complicated setups with suitable parametrization of the policy or occupancy measure (which we briefly touch upon with VAPOR-lite, which is promising for more thorough future investigation). - It is “*bad/worse to assume independent Dirichlet transition priors*" $\alpha$. This is the canonical prior for transitions in Bayesian RL, see “Bayesian Reinforcement Learning: A Survey” (Ghavamzadeh et al., 2016). This is because visiting a state-action pair simply increments by 1 the appropriate entry of the vector $\alpha$ — note the ease of the update because the Dirichlet is the **conjugate** prior of the categorical distribution (which models transition probabilities of discrete-state-action-MDPs). We hope this clarifies “*what happens to those assumptions later in the process, as beliefs are updated*”. We also note that the state-of-the-art Bayesian regret analyses (including PSRL, K-learning, RLSVI) assume it — it is an open question in the community how to obtain a $L \sqrt{S A T}$ Bayes regret bound without this assumption.
Have it your way
After some deliberation, I came to the conclusion that this is not worth arguing about. There's a good contribution here, the results are sound, and I would be doing a disservice to the community by making the authors jump through additional hoops and use up another set of reviewers' time in the next conference cycle. There are a lot of papers out there that overclaim their results and frame them in objectionable ways, and that's bad, but I'm not going to die on that hill. If there were a journal-like mechanism to review a revised manuscript, I would insist on some editorial changes, but there isn't, we're out of time and have to move on. I'll raise my score to recommend acceptance. I thank the authors for patiently answering my questions, and I hope they use this discussion to improve their paper. As a disclaimer, this evaluation is predicated on the proofs being correct, which I'm not able to check by myself. As of writing this, I believe that any concerns about correctness were adequately addressed in the rebuttal, but I reserve the right to lower my score if this changes.
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.
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. - 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. - 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. - VAPOR shows good performance compared with Thompson sampling based methods 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.
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. - 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. - 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. - 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. - 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. - 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.
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. - There are several issues in the lemmas that lead to the proof of Lemma 7. - 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. - 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. - 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.
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
1 poor
Presentation
2 fair
Contribution
3 good
Limitations
Beside possible errors in the analysis, the assumption makes the analysis in the paper limited and there is no discussion on this aspect.
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.
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. By providing a formalization of the Bayesian formulation and the variational approximation and details about the algorithm the contribution of the paper is very good. The paper is well-written and easy to follow. While 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. Future work and limitations are not sufficiently discussed in my opinion. For atari evaluation, only a reduced version of the algorithm is considered (without weighted entropy) Information on how to solve the VAPOR objective are only given in the appendix. The 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. Minor: The 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. line 110: Add "pair" after state-action.
Questions
How strong is the assumption for VAPOR that $r_l$ is a sub-Gaussian (in Lemma 3)? Is it possible to apply the method to continuous state/action spaces? What are the runtimes for the experiments?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
The formulation is limited to discrete/action spaces and does not seem to be scalable. No 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.
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.
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. This 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. I 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. The 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. In 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. This 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.
Questions
Is there a theoretical benefit for optimizing both the policy and stationary state distribution? Is there an intuitive explanation for the balance between optimism and entropy regularization?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
This paper has not discussed the limitations of the proposed method and the theoretical analysis.
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.
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
Questions
None
Rating
10: Award quality: Technically flawless paper with groundbreaking impact, with exceptionally strong evaluation, reproducibility, and resources, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
There is no dedicated section for limitations, but limitations are sufficiently discussed in the conclusion.
Clarifying questions
Having read the rebuttal and the other reviews, I think there's something interesting here, but the presentation of the paper makes it very difficult to judge what's novel, what problems it solves, and what are the limitations of the proposed approach. The paper is full of lengthy derivations and vague terms like "genuine statistical inference", "rigorous Bayesian treatment", or "false posterior", but there's little analysis of the objectives produced and how they compare to existing methods, and effectively no discussion of shortcomings and limitations. Before going further, some clarifying questions: 1. It seems that the key step is to optimize in the space of occupancy measures. Is this approach novel? Or is anything about the optimization algorithm used novel? If not, what's the closest existing algorithm that operates in the space of occupancy measures? 2. How much does the entropy term matter? It seems to be what's gained by the lengthy derivations. Did you run ablations without this term, just using the unconditional expected reward with an exploration bonus? 3. Why does VAPOR always go right in Table 1? It has both entropy and exploration bonuses, so how can it produce a deterministic policy? 4. In VAPOR-lite, once you throw away the entropy term, are you just adding a heuristic exploration bonus to the entropy-regularized actor-critic, or does it do anything more?
Response to Reviewer MCkd (1/2)
Thanks for your clarifying questions! $\newcommand{\PG}{\mathbb{P}_{\Gamma^\star}}$ Our contributions can be centered around the new object that we uncover as key for inference and control, $\PG$: - We start by formalizing what it means for a ‘state-action pair to be optimal’. This event is at the core of the ‘RL as inference’ framework but had never been properly analyzed, leading to serious exploration shortcomings. Crucially, we reveal that the posterior probability of this event, $\PG$, is an occupancy measure. - We prove that $\PG$ suffices for principled exploration (i.e., extracting a policy from it has a guaranteed regret bound). - Since computing $\PG$ is intractable, we propose a variational optimization problem (VAPOR) that tractably approximates it. - We solve this optimization problem in two different ways: exactly (giving a tabular model-based algorithm with regret guarantees) and approximately (giving a scalable model-free policy-gradient algorithm). - We show that both TS and K-learning can also be directly linked to $\PG$, thus shedding a new light on these algorithms and tightly connecting them to our variational approach, and unifying these approaches within our framework. We will also make sure to expand on the limitations of our work in the revised version, in particular the challenge in solving the VAPOR optimization problem, the open problem of relaxing Assumption 1 for the regret analysis, and if there is a tighter way to approximate VAPOR with policy gradients.
Response to Reviewer MCkd (2/2)
1. To the best of our knowledge, we are the first to operate in the space of occupancy measures for the purpose of Bayesian exploration (and ‘RL as inference’). This stems from our novel observation that the core quantity that formalizes RL as inference from a Bayesian viewpoint, $\mathbb{P}_{\Gamma^\star}$, is an occupancy measure, which gives rise to our optimization in this space.\ Operating in the space of occupancy measures has been done for various reasons in the RL literature, for instance for policy search [Peters et al., 2010; Suttle et al., 2022] or (frequentist) regret minimization in adversarial MDPs [e.g., Zimin and Neu, 2013; Rosenberg and Mansour, 2019; Jin et al., 2020]. \ The variational _optimization problem_ we propose is novel. It can be solved using various standard _optimization algorithms/techniques_. For instance, our tabular VAPOR learning algorithm uses convex optimization techniques (e.g., ECOS solver from CVXPY), while our approximation VAPOR-lite uses policy gradients. As a comparison, [Peters et al., 2010] have a different optimization problem in the space of occupancy measures, and they propose to solve it with BFGS or using sample-based policy iteration. 2. The entropy term matters both theoretically and empirically. In the tabular case, just being optimistic (i.e., exploration reward bonus) amounts to the UCBVI [Azar et al., 2017] algorithm (and variants), which have been shown to empirically perform worse than Bayesian algorithms (see e.g., Figure 2 of [O’Donoghue, 2021] on DeepSea). In deep RL, our Figure 7 in Appendix ablates the entropy regularization for an optimistic actor-critic agent on Atari. It reveals that VAPOR-lite’s ‘tuned, state-action’ entropy regularization performs better than standard ‘fixed, scalar’ regularization, which itself improves over ‘none’. 3. Great question! For the MDP in Fig 1 we can break down the behavior of the agent into two cases (the first state $s_1$, and any other state $s_{>1}$):\ \- $s_{>1}$: VAPOR will always go right for any state $s_{>1}$. This is because, conditioned on optimality only ‘move right’ has probability of being optimal under the posterior. \ \- $s_1$: VAPOR will go right with some probability $\geq 0.6$. This lower bound is determined by solving a convex optimization problem, and as $L \epsilon \ll 1$ it tends to $1$. In the text we assumed that $L \epsilon \ll 1$, in which case the probability of moving right at $s_1$ is approximately $1$. Note that probability $\geq 0.6$ is sufficient for an expected regret bound tighter than that of TS, which always goes right from the first state with probability $= 0.5$. \ Recall that VAPOR uses a *state-action weighted* entropy, where the weighting is also computed from the beliefs. It turns out that the weighting on the entropy terms goes to zero for actions at $s_{>1}$ along the chain, allowing a deterministic policy. 4. VAPOR-lite maintains a weighted policy entropy regularization (it just removes the weighted entropy of the policy’s stationary state distribution). As such, VAPOR-lite is (i) adding an exploration bonus and (ii) adding a state-action weighted policy entropy regularization, the latter of which is novel. We refer to Appendix E.3 for details (e.g., Eq.16) but we will make sure to provide more details of VAPOR-lite in the main text! [Peters et al., 2010] Relative Entropy Policy Search\ [Suttle et al., 2022] Occupancy Information Ratio: Infinite-Horizon, Information-Directed, Parameterized Policy Search\ [Zimin and Neu, 2013] Online Learning in Episodic MDPs by Relative Entropy Policy Search\ [Rosenberg and Mansour, 2019] Online Convex Optimization in Adversarial MDPs\ [Jin et al., 2020] Learning Adversarial MDPs with Bandit Feedback and Unknown Transition\ [Azar et al., 2017] Minimax Regret Bounds for Reinforcement Learning\ [O’Donoghue, 2021] Variational Bayesian Reinforcement Learning with Regret Bounds
Re 3, what you say about $s_{>1}$ is true, but how does VAPOR know that? Do you set $\sigma$ to zero for all states other than $s_L$? In general, I can't find a clear description in the paper for how $\sigma$ is selected.
Response to Reviewer MCkd
In that example, as is the usual case in Bayesian RL, the prior $\phi$ is known to all the algorithms. See the caption for Figure 1 or the text lines 137-144 for descriptions on what is known. So indeed VAPOR (and the Bayes-optimal algorithm, Thompson Sampling, etc.) is given the fact that the variance at states other than $s_L$ is zero, and that the reward at state $s_L$ is $\pm 1$ with probability $(0.5, 0.5)$ — note that this is epistemic uncertainty and not aleatoric uncertainty. Assuming a less informative prior (i.e., $P$ and $r$ unknown) would lead to more complicated $\pi_l(s_l, \rightarrow)$ values (and initially $<1$) for any learning algorithm, but to similar conclusions: sampling according to Approximation 1 or the marginal $\mathbb{P}{\scriptsize \phi}(\pi^\star)$ suffers exponential regret, sampling according to the conditional $\mathbb{P}{\scriptsize \phi}(\pi^\star | \Gamma^\star)$, TS or VAPOR yields sublinear regret.
I would like to thank the authors for the detailed responses. From the response, Theorem 1 indeed requires an additional assumption to be correct. The likely non-verifiable assumption not only makes the results much weaker, there are still many unspecified details missing for this possible assumption. If the assumption considers the vector-version $σ_l(s,a)$ under the prior distribution as in Lemma 3, they are still time independent, and therefore cannot decay with $t$. If the assumption will involve some time-dependent $σ^t_l(s,a)$ which might come from the posterior, the paper needs to add more details on the posterior distribution and some analysis on its evolution under the proposed policy. I feel like these issues require some major revision and another round of reviews.
Response to Reviewer QdEN
We thank the reviewer for engaging. We believe that the reviewer has misunderstood our use of standard and familiar tools in Bayesian inference and hope to correct that misunderstanding below. We do not require any additional assumptions for Theorem 1. The only fact that we rely on is that in Bayesian inference the posteriors concentrate as we gather more data. This is entirely standard, e.g., [1] and references therein. The only question is how fast do the posteriors concentrate: Under our already stated assumptions the variance of the posteriors concentrate like 1/(#data samples). Concretely, as the agent navigates the environment it visits state-actions at *different schedules*, so the posteriors concentrate (uncertainty decays) at the same 1/(#data samples) *rate*, but at *different schedules*. As is usual in RL, we have assumed sub-Gaussian additive reward noise. That implies the following: - If each state-action reward posterior starts with some $\kappa$ uncertainty (the prior) and the reward noise has variance $c_0^2$ and for simplicity take $\kappa \gg c_0$ (if not it can only help the posteriors concentrate faster), - Then at time $t$ the uncertainty has decayed to $c_0^2 / n^t(s,a)$, where $n^t(s,a)$ is the number of times the agent has visited state-action (s,a) before episode $t$ (ie, the number of data samples of the reward from state-action (s,a)). This rate is all we need to prove the regret bound. It is ‘time-dependent’, but only in the sense that as time progresses the agent is gathering more data and the posteriors (or confidence sets) are concentrating, this is entirely standard in RL, both frequentist and Bayesian approaches (otherwise how would the agent ever learn?). The sub-Gaussian assumption is standard in the literature and arises commonly in practice. For instance, in both Atari and DeepSea (the experiments we ran) the assumption holds because the rewards are bounded. In slightly more detail: - Theorem 1 reads: For known $P$ and $c_0$-sub-Gaussian additive reward noise, it holds that $\mathcal{BR}(\text{VAPOR}, T) \leq c_0 \sqrt{S A T}$. - The *definition* of $c_0$-sub-Gaussian additive reward noise means that: at any time $t$, step $l$, state-action pair $(s,a)$, $\mathbb{E}^t [\exp(x (r_l(s,a) - \mathbb{E}^t r_l(s,a)))] \leq \exp \left(x^2 c_0^2 / 2 (n_l^t(s,a) \vee 1) \right), \quad \forall x \in \mathbb{R}.$ - This means that at any time $t$, we can *instantiate* the uncertainty $\sigma_l^t(s,a)$ in the VAPOR optimization problem as: $\sigma_l^t(s,a) = \frac{c_0}{\sqrt{(n_l^t(s,a) \vee 1)}}$. [1] Conjugate Bayesian analysis of the Gaussian distribution, Murphy, 2007.
Appreciate the authors' further clarification. As we discussed, Theorem 1 clearly requires concentration of the posterior. There is no discussion nor analysis on the concentration of posterior in the current version of the paper. One possible way to handle the posterior concentration could be making it as an assumption of the algorithm, but it then required much further discussion on why this assumption makes sense. Another possibility is that the posterior concentration is a consequence of the assumptions on prior and noise distributions, which is kind of suggested by the authors' response. This concentration could be true and might be established as in other works, but to do it the paper needs to provide analysis on the posterior evolution and prove that the posterior distribution indeed satisfies the desired concentration property. Either way, the paper requires extra justifications and does not look ready in the current form.
In the paper we clearly state that we assume additive sub-Gaussian reward noise. For simplicity let's just say the reward noise is Gaussian. It is a standard result that variance of the posterior of a Gaussian concentrates like $1/n$ (for a worst case, improper prior - any other prior would have *faster* concentration). We are simply using that fact for the posterior of the mean reward at each state and action. Sub-Gaussian simply replaces the exact concentration of $1/n$ with an upper bound of $1/n$. There is no extra analysis we can do other than to re-prove ancient results about Gaussians that you can read from this wikipedia page: https://en.wikipedia.org/wiki/Conjugate_prior#When_likelihood_function_is_a_continuous_distribution
Not my thread, but adding my two cents
I think a lot of confusion could be avoided if the authors clearly stated their assumptions regarding the priors and likelihoods used to model the environment. The paper silently assumes that we can exactly compute the posterior, which is generally not tractable. The authors avoid this problem by using independent conjugate priors, where the beliefs can be updated in closed form. This is fine, but something that needs to be clearly stated. A short paragraph in the preliminaries describing how the inference part is handled would go a long way towards making the paper more accessible. Now, to the issue at hand. I agree this concentration property holds for standard conjugate priors. What's not clear to me is whether this extends to the general case, where the likelihood is not Gaussian, the prior is not conjugate, and the priors on different variables (indexed by t,s,a) are not independent. I suspect that it does, but it's not obvious to me.
We state all the assumptions we require clearly in Theorem 1 and Assumption 1. These are: - (A) A time-inhomogeneous MDP. - (B) The mean rewards are bounded in [0, 1] almost surely with independent priors. - (C) The reward noise is additive σ-sub-Gaussian. - (D) The prior over transition functions is independent Dirichlet. We are happy to add a paragraph explaining these assumptions in more detail, but we are not "silently assuming that we can exactly compute the posterior" or anything like that, nor do we require closed-forms of the posteriors. Note combining assumptions (B) and (C) implies that the posterior is also sub-Gaussian (see App D.2 of [Russo and Van Roy, 2016, An Information-Theoretic Analysis of Thompson Sampling]). The sub-Gaussian property means we can *upper bound* _intractable_ posteriors with a _tractable Gaussian_ distribution. We do not require conjugate priors (other than Dirichlet) or Gaussian likelihoods, only these assumptions. This is the exact same set of assumptions as the published, state-of-the-art related works of K-learning [O’Donoghue, 2021, Asm 1], PSRL [Osband et al., 2017, Lem 3] and RLSVI [Osband et al., 2019, Asm 2 and 3]. Relaxing (partially) these assumptions without suffering a worse regret bound is indeed an important open question, which we believe is outside the scope of this paper but which we will clearly highlight in the paper as per reviewers’ suggestion. Finally, we emphasize that these assumptions are technicalities for the regret analysis, not fundamental ones for the algorithmic idea. A practical (approximate) implementation of VAPOR would likely be model-free and compute heuristically an uncertainty signal $\sigma(s,a)$, such as with an ensemble of reward predictors as done in VAPOR-lite.
Thank you for answering my questions. After reading the other reviews and discussions, I have decreased my confidence as the other reviewers probably have a deeper understanding of the paper. I still think the paper is well written and the technical contributions seem good to me, but there might be some issues as mentioned by reviewers QdEN and MCkd. I especially agree with them that limitations are not sufficiently discussed in the paper.
Not sure if they are typos or just very bad notations, but $\phi$ is referred to as the prior in some places (like line 200) but called the posterior in some other places (like line 164). This inconsistency makes the paper almost not possible to understand, and it also creates issues for many claims, including those in the responses. If we view $\phi$ in Assumption 1 as the prior as assumptions in the literature, there are still many issues. First, prior distribution and observation noise are different things, but the way the assumption is written messed up with the two. Second, despite the first issue, the assumption is still not exactly the same as in prior papers. For example, the PSRL paper does not assume time-inhomogeneous and independent prior across time. Lastly, despite all the mess-ups in notations/typos, there is no analysis on the posterior concentration. Concentration could well be true, but there is no proof, not even a statement, on the posterior concentration in the paper. In RL problems, because the posterior distribution depends on the algorithm which collects the data, there could be some subtle but critical issue appearing the the posterior analysis given certain properties of the algorithm. The claims in the paper may be true, but they can only be verified after the notations/typos being fixed, the non-consistent statements being rewritten, and the proof details being added.
Just want to make a comment on the necessity of a careful analysis for posterior in RL. Some properties for posterior do not always hold for all RL algorithms. For example, Example 2 in Osband, Ian, and Benjamin Van Roy. "Posterior sampling for reinforcement learning without episodes." arXiv preprint arXiv:1608.02731 (2016) provides a counterexample of a posterior sampling property under general policies.
Decision
Accept (poster)