# Response to Reviewer YNwE

>Thank you for your response. I still don't get why restriction is not required on the value functions. The authors have used Theorem 2 in [B] to upper-bound the total variation distance using Stein discrepancy. If I check Theorem 2 in [B], the result only holds for a sertain stein operator and a certain class of Stein functions, where the Stein functions have zero-expectation under true measure. To apply this to RL problem, it essentially amounts to the value functions satisfying zero expectation (at least, it seemed to me). I would like the authors to provide a complete (mathematical) characterization of Stein operator and Stein Set for the RL problem. Specifically, characterize all the quantities of Theorem 2 in [B]. I believe that would ease for me (or any reader) to understand the nitty gritty of the result.

**Response:** We thank the reviewer for the comment. We believe the major concern in regarding the requirement ***"it essentially amounts to the value functions satisfying zero expectation"***. Let us try to expand on it and explain in detail as follows.

Let us start with the upper bound we want to establish in Lemma 4.1, we use the following inequality
$$
U_{i}^k({P}^k(h_i))-U_{i}^k(P^*(h_i)) \leq \max_{s}|V^{{M}_k}_{{\mu}_k}(s)|\cdot \|{P}^{k}(\cdot|h_i)-P^*(\cdot|h_i)\|
\leq HR_{\text{max}}\|{P}^{k}(\cdot|h_i)-P^*(\cdot|h_i)\|
$$
where we utilize the definition of Bellman equation, apply Cauchy Schwartz inequality, and then take maxima of the value function over all possible states. This derivation is valid whenever the reward function is bounded and the horizon length is finite, independent of the methodology used to estimate transition dynamics. We defer the application of these ideas to infinite horizon settings to future work. Now, we have a term $\|{P}^{k}(\cdot|h_i)-P^*(\cdot|h_i)\|$ which is the total variation distance between the distributions. Next, we upper bound $\|{P}^{k}(\cdot|h_i)-P^*(\cdot|h_i)\|$ in terms of Wasserstein distance $d_{\mathcal{W}}({P}^{k}(\cdot|h_i),P^*(\cdot|h_i))$, via Theorem 2.1 and Lemma 5.1 in [A]. The result from Lemma 5.1 and proof of Theorem 2.1 guarantees that if both probability measures have smooth densities then the total variation can be upper-bounded by Wasserstein distance (even by a weaker metric Levy-Prokhorov) as detailed in [A].

Then, we utilize the result of Theorem 2 in [B] to upper bound it with kernelized Stein discrepancy under the appropriate assumption satisfied by the Stein operator design. Mathematically, let us try to explain things in more detail here. We follow the notations detailed in [D].

**Target distribution:** In our settings, our target distribution is the transition model $P^*(\cdot|h_i)$ which we want to estimate, and approximate it via $P^k(\cdot|h_i))$ at each iteration $k$.

**Stein Class:** A function $f(x)$ lies in the Stein class of target distribution if it satisfies:

$$
\int_x \nabla_x (f(x) p(x)) dx = 0,
$$
where $p(x)$ is the target distribution. In our RL setting, Stien class is a set of kernel functions $f(x)=\kappa(x,\cdot)$ that belongs to RKHS. A specific example of kernel $\kappa(x,\cdot)=\exp(-\frac{1}{2\sigma^2}\|x-y\|^2)$. Therefore, this is our test function class for RL problem of interest.

**Stein discrepency (Theorem 3.6 [D]):** We can utilize Stien class of kernels $\kappa(x,\cdot)$ and score function $S_{P^k}(x)$ to evaluate the the discrepency as

$$
KSD(P^k,P^*)=\mathbb{E}_{x,x'\sim P^*} [u_{P^k}(x,x')]
$$
where $u_{P^k}(x,x')$ is defined as
$$
u_{P^k}(x,x')=S_{P^k}(x)^T\kappa(x,x')S_{P^k}(x')+S_{P^k}(x)^T\nabla_{x'}\kappa(x,x')+\nabla_{x}\kappa(x,x')^TS_{P^k}(x')+\text{trace}(\nabla_{x,x'}\kappa(x,x')).
$$
Note that we only need access to the score function and kernel $\kappa$ to evaluate discrepancy. Therefore, we actually need the following
$$
\mathbb{E}_{P^*}[\mathcal{A}_{P^*}\kappa(\cdot,x)]=0
$$
where $\mathcal{A}_{P}\kappa(\cdot,x):=S_{P}(\cdot)\kappa(\cdot,x)+\nabla_x \kappa(\cdot,x)$ and **NOT**
$$
\mathbb{E}_{P^*}[V(\cdot)]=0.
$$
Hence, it is clear that at least to apply the Stien ideas, we don't need our value functions to lie in the Stien class.

Now, the next question is of how to employ the result of Theorem 2 in [B] in our setting. Since, $\kappa(\cdot,x)$ is a valid Stein test function and belongs to Stein class of target $P^*$, we can define the classical Stien set as

$$
\begin{eqnarray}
\mathcal{G}_{\|\cdot\|}:=&\Big\{\kappa(\cdot,x): \mathcal{X}\rightarrow \mathbb{R} ~|~ \sup_{x\neq y\in\mathcal{X} } \max \big(\|\kappa(\cdot,x)\|^*,\|\nabla_y\kappa(y,x)\|^*,\frac{\nabla_y\kappa(y,x)-\nabla_y\kappa(y',x)}{\|y-y'\|}\big)\leq 1\\&\ \text{and}\ \ \int\kappa(y,x)n(y)dy=0 \ \text{with} \ n(y)=y-x\Big\},
\end{eqnarray}
$$
for all $x\in\mathcal{X}$. So for the Stein set $\mathcal{G}_{\|\cdot\|}$ which is subset of RKHS, Theorem 2 in [B] would hold under the Stein operator $\mathcal{A}_{P^k}\kappa(\cdot,x):=S_{P^k}(\cdot)\kappa(\cdot,x)+\nabla_x \kappa(\cdot,x)$.

### Additional Discussion on the Confusion of $\mathbb{E}_{P^*}[V(\cdot)]=0$.

Here, we take another route to discuss the claim $\mathbb{E}_{P^*}[V(\cdot)]=0$ raised by the reviewer. From the definition of Stein class, we know that if value function lies in the Stien class of $P^{*}$, it would require to hold that
$$
\mathbb{E}_{P^*}[\mathcal{A}_{P^*}V(x)]=0,
$$
where $\mathcal{A}_{P^*}V(x)=S_{P^*}(x)V(x)+\nabla_x V(x)$. To check that, let us write
\begin{align}
\mathbb{E}_{P^*}[\nabla_x V(x)] &= \int_a^b P^*(x) \nabla_x V(x)\\
&= P^*(b) V(b) - P^*(a) V(a) - \int_a^b \nabla_x P^*(x) V(x) dx\\
&= P^*(b) V(b) - P^*(a) V(a) - \int_a^b \frac{\nabla_x P^*(x)}{P^*(x)} P^*(x) V(x) dx\\
&= P^*(b) V(b) - P^*(a) V(a) - E_{P^*} [S_{P^*}(x)V(x)]\\
\end{align}

After rearranging the terms, we get
$$
\mathbb{E}_{P^*}[\nabla_x V(x) + S_{P^*}(x)V(x)] = P^*(b) V(b) - P^*(a) V(a).$$

So for $V(x)$ to be in the Stein class of $P^*$ (as mentioned by the reviewer), we would need $P^*(b) V(b) - P^*(a) V(a) = 0$. This is not the case, as the value function initialized from two different states is not equal in the class of MDPs under consideration. Even if it is zero, it would just mean that $\mathbb{E}_{P^*}[\mathcal{A}_{P^*}V(x)]=0$ **and not** $\mathbb{E}_{P^*}[V(x)]=0$. Therefore, the requirement $\mathbb{E}_{P^*}[V(\cdot)]=0$ is not true and also not required in our analysis.

We believe that the above explanation helps to clarify any doubt. If there is still a confusion, we are happy to discuss more and provide any additional requested details.

### Additional Inequality to support our Lemma 4.1 (log-sobolev)
Alongside [B], we also observe that [C] derive the same upper bound $d_W(p,q) \leq S(p,q)$ for a centred probability measure on $\mathbb{R}^d$ admitting a Stein kernel with smooth test functions. Specifically, we refer to Proposition 3.1 in [C] which states that for every centred probability measure on $\mathbb{R}^d$ (under smoothness assumptions with finite moments), Wasserstein distance is upper bounded by the Stein discrepancy. Please refer to the proof detailed in Proposition 3.1 under section 3.1 [C], which can be shown under the smoothness criterions and using the central argument of Otto-Villani theorem which states that a logarithmic Sobolev inequality implies a Talagrand transport inequality.

**References**

[A] A novel approach to Bayesian consistency by Minwoo Chae, Stephen G. Walker.

[B] Jackson Gorham and Lester Mackey. Measuring sample quality with stein’s method. Advances in Neural Information Processing Systems, 28, 2015.

[C]. Ledoux, M., Nourdin, I., Peccati, G. Stein’s method, logarithmic Sobolev and transport inequalities Geom. Funct. Anal. 25, 256–306 (2015)

[D] Liu, Qiang, Jason Lee, and Michael Jordan. "A kernelized Stein discrepancy for goodness-of-fit tests." International conference on machine learning. PMLR, 2016.

**Request:** We thank the reviewer again for reviewing our work and providing valuable comments. If there are no more concerns, we kindly request the reviewer to consider raising the score. We are happy to address if there are any further questions.

> Thanks for the update. Since any Bayesian regret can be converted to a frequentist one as long as the true MDP is not impossible under the prior (as stated in [1], appendix A), I still think the lower bound in [2] should apply and still have doubt on if there's some missing piece in the updated analysis wrt to the dimensionality.
[1] Ian Osband, Daniel Russo, Benjamin Van Roy. (More) Efficient Reinforcement Learning via Posterior Sampling
[2] Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. Learning near optimal policies with low inherent bellman error. arXiv preprint arXiv:2003.00153, 2020.
Also, if the theoretical improvement comes from the use of coreset, we should also expect improvement on the empirical performance wrt previous work that does not use it, which is another concern about whether the proposed theoretical improvement is valid.

We apologize for any confusion. We agree that there is not doubt in the fact that one cannot convert Bayesian to frequentist regret, and that is also not our main point.

Our main emphasize in the previous respones is that there are certain settings under which a sublinear dependence on $d$ (in the form of $\sqrt{d}$) exits (for which we provided references in the previous response). We are just claiming that under the setting when Stein class of target distribution belongs to RKHS, and also different assumptions on target (mentioned in Lemma 4.1, 4.2, and Theorem 4.3) are satisfied, we are able to achived the improved performance.

We belive it is not fair to directly compare our results to [2]. If there is any issue in the analysis in the paper, that might help in figuring out the exact issue. But otherwise, it seems fine to have $\sqrt{d}$ dependence. We would again like to mention Table 1 in [A] where different lower bounds for bandit and RL settings are mentioned with $\sqrt{d}$ dependence under certain assumptions. So it seems at least possible we believe under specific settings which we explained in our previous response in detail.

[A] Foster, D. J., Kakade, S. M., Qian, J., & Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487.

Thank you for the questions. Here are the replies.

Dimension is not defined here. Are you now shifting to parameteric model (original version was non-parametric model)? Please define the exact transition model you are considering.

1) Dimension $d$ is defined in the paper which is "*$d$ is the aggregate dimension of the state and action space*". We are not considering any parametric model to estimate the posterior.

Now, for prior work considering non-parametric MDPs, there are two notions of model complexity, which appears in the bound -- eluder dimension and metric entropy. Please clarify whether here is eluder dimension or metric entropy? Note that in [A], state and action spaces can be arbtrary compact sets.

2) Our notion of model complexity is the number of data points required to estimate the posterior distribution.

The claim that your bound matches the lower bound is not correct -- the lower bound is even for the easier setting of linear MDPs. See [D].

Looking at the example, I guess is the dimension of state space here. If that is the case, then the comparison with prior work is vacuous. For example, in prior work considering linear transition models, is not the dimension of state space - instead it is the number of parameters of the transition distribution (and can also be thought of dimension of joint state-action-state space). Please clarify whether here is same as prior work or not.

[D] Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes, Dongruo Zhou and Quanquan Gu and Csaba Szepesv´ari, 2021.