Distributional off-policy evaluation with Bellman residual minimization

We appreciate your positive feedback and the constructive comment.

(Weakness 1) Non-degeneracy of Theorem 3 (of previous manuscript) towards Theorem 2.

We agree with your comment that the nondegeneracy of Theorem 3 (of previous manuscript) to Theorem 1 under realizability requires additional study. We would like to provide additional insights/explanations and summarize the reasons why we were not able to achieve that in our current proof.

The statement of Theorem 3 changed in the new manuscript. Instead of comparing Theorems 2 and 3, it is now fair to compare Theorem 2 and the finite-sample error bound suggested in B.4.3 (or simplified version in Equation (186)) with fixed level of $m=1$.

To begin with, in non-realizable cases, the converging target is no longer the true distribution. Instead, we compromise our goal into the ``best approximation" $\Upsilon_{\tilde{\theta}}$, with $\tilde{\theta}$ defined in Equation (21). That being said, we are unable to make use of Theorem 1 anymore, which only required us to derive the convergence rate of estimated Bellman residual (our objective function). Therefore, unlike realizable scenario, it requires one additional procedure, which is obtaining convergence of the minimizing parameter. This leads us to take into account the function $\psi(\cdot)$ in B.4.3, which further slows down the rate by $1/q$.

In addition, the sampling contains two procedures, collecting the data $(s_i,a_i,r_i,s_i')$ ($1\leq i \leq N$) and resampling multi-step trajectories, as defined before Equation (22). Since we are re-using the samples for multiple times, this no longer guarantees the independence of the data that we use. Then we cannot make use of common tricks for showing sample mean converging to the population mean (e.g. Hoeffding's inequality), since they require independence of samples. Therefore, we resort to another trick (Lemma 3 of Appendix B.2.1) that resembles triangular inequality, but slows down the rate by $1/2$.

Due to the aforementioned reasons, the rate in non-realizable scenario is slower than realizable scenario by $1/(2q)$, that is $\sqrt{\log N/N}$ verses $\sqrt[(4q)]{\log N/N}$.

(Question 1) Limitations of EBRM

There remain a few limitations in our method. A major limitation is that our estimator is developed under the tabular setting. Given our discussion of Theorem 1 above, it is interesting to look into more general state-action spaces.

Besides, we focus on parametric family of the conditional distributions, i.e., $\Theta$ is a subset in a finite-dimensional space. Extension to nonparametric modeling of the conditional distributions is also interesting, and potentially lessens the chance of non-realizability due to more flexible modeling.

Another limitation is that we do not provide a complementary method for control problems (finding optimal policy), as some other distributional RL works (which address evaluation and control problems in the same paper).

(Question 2) Not using more standard metric

Energy distance is a well-known metric that is being widely used and thoroughly studied [8]. In addition, it satisfies good properties, including that it is generally easier to compute than Wasserstein metric, and that it can be regarded as multi-dimensional extension of Cramer distance [3]. It is also a special case of maximum mean discrepancy [4] associated with a specific kernel $k(\mathbf{x},\mathbf{y})=||\mathbf{x}||+||\mathbf{y}||-||\mathbf{x-y}||$. Given that [5] and [6] directly used maximum mean discrepancy, and [7] also tried to make an interpolation between Wasserstein metric and maximum mean discrepancy, the use of energy distance seems to be one reasonable choice of metric among the literature of distributional reinforcement learning.

As you also pointed out, we also calculated the inaccuracy levels with other metrics, including expectation-extended Wasserstein-1 metric in Tables 9 and 12 of Appendix D.4. In view of your comment, we will revise the paper to provide the corresponding discussion. In addition, we will add a new metric which is used in [2] (FLE, a method that we compared) in Corollary 4.14 of their paper. (This is also suggested by Reviewer 3TV7.) That is, treating the conditional return distributions as mixture components {$\Upsilon_\pi(s,a):(s,a)\in\mathcal{S}\times\mathcal{A}$} and mixture weights {$b_\mu(s,a): (s,a)\in\mathcal{S}\times\mathcal{A}$}, we formed the mixture distribution that can be regarded as the marginal return distribution $\Upsilon_\pi^{marginal}$. Then we measured Wasserstein-1 metric value between the estimated and true (marginal) distributions, as shown in the following tables. Similar to Tables 8--9, 11--12 of Appendix D.4, EBRM outperformed its competitors in all except for the non-realizable scenario with $\gamma=0.50$, where the performances between EBRM and FLE are very close.

• Realizable: $\sigma_0^2=20$

• Realizable: $\sigma_0^2=5000$

• Non-realizable: $\gamma=0.50$

• Non-realizable: $\gamma=0.99$

Thank you for your helpful comments.

(Weakness 1) The inequality (7) is not interesting.

In tabular settings, the two distances $\bar{\eta}$ and $\eta_\infty$ are equivalent: $\bar{\eta}(\Upsilon_1, \Upsilon_2)\le \eta_\infty (\Upsilon_1, \Upsilon_2) \le p_{\min}^{-1}\bar{\eta}(\Upsilon_1,\Upsilon_2)$ for any $\Upsilon_1,\Upsilon_2$. Due to (5) of our paper, the equivalence would lead to $\bar{\eta}(\Upsilon,\Upsilon_\pi) \le p_{\min}^{-1} (1-\gamma^{\beta_0})^{-1}\bar{\eta}(\Upsilon, \mathcal{T}^\pi \Upsilon)$. So the reviewer's insight holds for tabular settings. However, Theorem 1 can be applied to general state-action space, which includes continuous state-action space. In the general settings, the two distances are not necessarily equivalent. We also had a related discussion at the end of Section 2.2. Let us assume that state-action space is a subset of $\mathbb{R}^q$ with the data-generating probability being absolutely continuous with respect to the Lebesgue measure, thereby yielding the density $b_\mu(s,a)$. In general, we cannot bound $\eta_\infty$ by $\bar{\eta}$ up to any multiplicative constant. So Theorem 1 would not be implied by the corresponding results of supremum-extended distance. Overall, Theorem 1 is indeed a non-trivial result.

As we discussed in Section 1, there is a theory-practice gap regarding distances $\eta_\infty$ and $\bar{\eta}$. Every method mentioned in the first paragraph of Section 1 of our paper is not free from this ``distance mismatch" (Tables 1 and 3). They utilize expectation-extended distance in the objective functions of their algorithms; however, the theoretical properties that motivate their constructions are based on supremum-extended distance $\eta_\infty$. In its full generality, Theorem 1 provides a foundation for expectation-based distance for settings with general state-action spaces. Finally, we remark that our estimator (Sections 3 and 4) is based on tabular settings (and so would not be able to fully exploit the power of Theorem 1.) It is mainly because we aim to provide a more comprehensive study that involves nonstandard setups (e.g., non-realizability, multi-step extensions). Even with tabular settings, corresponding analyses are complicated and related theoretical results of these setups in distributional reinforcement learning are rare. To our knowledge, our work is the first that provides theoretically guarantee for non-realizable settings in distributional reinforcement learning. Extension to non-tabular settings with the full exploitation of Theorem 1 is left as a future work.

(Weakness 2) Limited experiments.

We admit that extensive numerical comparison is not our major focus, given the more theoretical flavor of this work. In our numerical experiments, our main focus lies in demonstrating that expectation-extended inaccuracy level converges to zero, and providing some reasonable comparisons with close competitors like FLE [2]. The environment was designed based on Figure 1 of the following paper that devised another distributional reinforcement learning method called RDPS [1]. We have also looked into the combination-lock environment used by [2], however it was designed for finite-horizon problems and so it is not appropriate. We will add more experiments. Specifically, we are considering a 2D example.

(Weakness 3) Broken notations

About $b_\mu$: We are sorry for the confusion. If we are assuming a continuous state-action space, then the base measure will be Lebesgue measure, and $b_\mu$ (in Assumption 1) becomes the density of a continuous random vector. In the manuscript, the notation $b_\mu$ is used to indicate both the probability measure and its density (slight notational abuse). Now, we made this clear below Equation (6).

About the kernel $k$: We have corrected the issue behind Equation (33) of Appendix A.3 in the original manuscript. The whole point of A.3 was to show that energy distance satisfies the properties of A.2.1. Instead of using the properties of the associated kernel, we directly showed that energy distance satisfies Property 1 of Appendix A.2.1. Thank you for pointing this out.

(Question 3) Are the weakness points raised correct?

First, we appreciate that you raised these points, which have helped us improve our paper.

(Weakness 1): We believe this is due to misunderstanding---our apology for confusing notation mentioned in (Weakness 3) which might have hindered your prior understanding. We hope that our response have addressed your concern.

(Weakness 2): We admit that extensive numerical comparison is not our major focus of this work. But we will add more experiments.

(Weakness 3): Thank you very much for pointing out these notational issues, which we have fixed.

References

[1] Morimura, Tetsuro, et al. "Nonparametric return distribution approximation for reinforcement learning." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.

[2] Runzhe Wu, Masatoshi Uehara, Wen Sun: Distributional Offline Policy Evaluation with Predictive Error Guarantees. ICML 2023: 37685-37712

[3] Marc G Bellemare, Ivo Danihelka, Will Dabney, Shakir Mohamed, Balaji Lakshminarayanan, Stephan Hoyer, and Remi Munos. The cramer distance as a solution to biased wasserstein gradients. arXiv preprint arXiv:1705.10743, 2017b.

[4] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Scholkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723–773, 2012.

[5] Thanh Nguyen-Tang, Sunil Gupta, and Svetha Venkatesh. Distributional reinforcement learning via moment matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9144–9152, 2021.

[6] Pushi Zhang, Xiaoyu Chen, Li Zhao, Wei Xiong, Tao Qin, and Tie-Yan Liu. Distributional reinforcement learning for multi-dimensional reward functions. Advances in Neural Information Processing Systems, 34:1519–1529, 2021

[7] Ke Sun, Yingnan Zhao, Yi Liu, Wulong Liu, Bei Jiang, and Linglong Kong. Distributional reinforcement learning via sinkhorn iterations. arXiv preprint arXiv:2202.00769, 2022.

[8] Gabor J Szekely and Maria L Rizzo. Energy statistics: A class of statistics based on distances. Journal of statistical planning and inference, 143(8):1249–1272, 2013.

Thank you for your constructive comments.

(Weakness 1) Not fully convinced if the chosen distributional distance is practically meaningful.

The analog of $Q$-function and value (expectation of $Q(S,A)$ over $S,A$) in distributional RL are the conditional return distributions {$\Upsilon_\pi(s,a):(s,a)\in\mathcal{S}\times\mathcal{A}$} and the marginal return distribution $\Upsilon_\pi^{marginal}$, i.e., the mixture distribution with mixture components {$\Upsilon_\pi(s,a): (s,a)\in\mathcal{S}\times\mathcal{A}$} and mixture weights {$b_\mu(s,a): (s,a)\in\mathcal{S}\times\mathcal{A}$}.For simplicity, we choose the reference distribution as $b_\mu$ for our discussion. Based on our understanding, we believe that the reviewer concerns why we are interested in the convergence/accuracy of conditional return distributions, instead of the marginal return distribution.

One of the major reasons is that, like $Q$-function, the conditional return distributions can be useful for handling a control problem (finding the optimal policy), as shown in the following works ([1] and $\rm [2]$). In these papers, they estimated the conditional return distributions $\Upsilon_\pi(s,a)$, and then developed it into a risk-sensitive policy learning strategy that can deal with the control problem. This is one step further from Q-learning of conventional reinforcement learning, in that we can take into account the risk that is not represented in the expectation value.

Second, given the conditional return distributions {$\Upsilon_\pi(s,a):(s,a)\in\mathcal{S}\times\mathcal{A}$}, we can easily estimate the marginal return distribution $\Upsilon_\pi^{marginal}$. This can be theoretically supported by our theorems (Theorems 2 and 3), since Lemma 3 of Nguyen [3] implies $\mathcal{E}(\Upsilon_{\hat{\theta}}^{marginal}, \Upsilon_\pi^{marginal})\leq \bar{\mathcal{E}}(\Upsilon_{\hat{\theta}}, \Upsilon_\pi)$ and $\mathcal{E}(\Upsilon_{\hat{\theta}}^{marginal}, \Upsilon_{\tilde{\theta}}^{marginal})\leq \bar{\mathcal{E}}(\Upsilon_{\hat{\theta}}, \Upsilon_{\tilde{\theta}})$. In the literature of distributional reinforcement learning, we are not aware of any results indicating that directly proving the convergence of marginal distribution $\Upsilon_\pi^{marginal}$ leads to a faster convergence rate. Indeed, the reviewer's comment has led to an interesting research direction.

(Weakness 2) Non-realizability section does not provide much intuition.

The insight for both realizable (Section 3) and non-realizable scenarios (Section 4) are elaborated in detail in the response for (Question 1) below. Here, we will only discuss the role of $G(\theta;\pi)$, along with the intuitive meaning of Equation (18) of the original manuscript. From its definition $G(\theta;\pi):=4\tilde{\eta}(\theta, \pi)=4\tilde{\eta}(\Upsilon_\theta, \Upsilon_\pi)$, this term represents the disparity from the true distribution. However, it can be simplified by replacing it with a constant $C:=4\cdot (\tilde{\eta}(\tilde{\theta},\pi) + L\cdot {\rm diam}(\Theta, ||\cdot||)) >0$, as in the updated manuscript. This demonstrates how challenging the given problem is, by combining the size of the model ${\rm diam}(\Theta, ||\cdot||)$ and the extent of non-realizability $\tilde{\eta}(\tilde{\theta},\pi):=\tilde{\eta}(\Upsilon_{\tilde{\theta}}, \Upsilon_\pi)$ that becomes zero in the realizable case. The implication of Equation (18) is that we can shrink this obstacle (that represents non-realizability) to zero by taking multi-step approach, with large enough step level $m$. This eventually allows our estimator to be close to the ``best approximation" $\tilde{\theta}:=\arg\min_{\theta}\bar{\mathcal{E}}(\Upsilon_\theta , \Upsilon_\pi)$. Please refer to the response to (Question 1) for more details.

(Weakness 3) Not convinced by the rate difference.

Please see our response to (Question 2) below.

(Question 1) Highlight the intuition behind algorithm.

First, under the realizable scenario (Section 3), the insight behind the construction of our estimator for the realizable scenario is directly based on Theorem 1, where we show that the inaccuracy $\bar{\mathcal{E}}(\Upsilon, \Upsilon_\pi)$ is bounded by Bellman residual $\bar{\mathcal{E}}(\Upsilon, \mathcal{T}^\pi \Upsilon)$ up to a multiplicative constant. This justifies our practice of minimizing the estimated Bellman residual $\hat{\theta}=\arg\min_{\theta}\hat{\bar{\mathcal{E}}}(\Upsilon_\theta , \hat{\mathcal{T}}^\pi \Upsilon_\theta)$.

Second, for the non-realizable scenario (Section 4), Bellman residual $\bar{\mathcal{E}}(\Upsilon_\theta, \mathcal{T}^\pi \Upsilon_\theta)$ can never become zero with any $\theta\in\Theta$, due to model misspecification. This may lead to a loose bound when the minimum value of Bellman residual $\min_{\theta}\bar{\mathcal{E}}(\Upsilon_\theta, \mathcal{T}^\pi \Upsilon_\theta)$ is very large. Therefore, we suggested an alternative of applying multi-step as follows.

Temporarily ignoring mathematical rigor, the most important insight is that we can approximate $(\mathcal{T}^\pi)^m\Upsilon\approx \Upsilon_\pi$ with sufficiently large step level $m\in\mathbb{N}$. Thanks to the properties of energy distance (Appendix A.3), we can obtain uniform convergence of $m$-step Bellman residual towards inaccuracy function, that is $\sup_{\theta}|\bar{\mathcal{E}}(\Upsilon_\theta , (\mathcal{T}^\pi)^m \Upsilon_\theta) - \bar{\mathcal{E}}(\Upsilon_\theta , \Upsilon_\pi)|\leq \gamma^m\cdot C \rightarrow 0$ as $m\rightarrow \infty$, where $C>0$ is the constant that quantifies non-realizability as illustrated in (Weakness 2).

This eventually allows us to obtain an estimator that converges to the best approximation, that is $\hat{\theta}_m^{(B)}\rightarrow^P \tilde{\theta}$, where $\tilde{\theta}\in\Theta$ is the minimizer of the inaccuracy function (defined in Weakness 2). However, larger step levels $m\in\mathbb{N}$ come with a price that resembles bias-variance trade-off, as specified in Equation (186) of Appendix B.4.4. This is why we suggested a rule of choosing the optimal level of $m$ in Appendix D.3.1.

We will later revise the paper to highlight the related insights.

(Question 2) Dive into the rate difference.

The statement of Theorem 3 has been changed in the new manuscript. Instead of comparing Theorems 2 and 3, we should compare Theorem 2 and the finite-sample error bound suggested in B.4.3 (or simplified version in Equation (186)) with fixed level of $m=1$.

To our understanding, the reviewer is suspecting the difference between algorithms of single-step and multi-step EBRM to be part of the reasons for rate difference (the third weakness listed in this response). Indeed, this partially explains the reason, since we form multi-step trajectories by resampling from the collected data $(s_i,a_i,r_i,s_i')$ ($1\leq i \leq N$), as mentioned before Equation (22). This practice of re-using the samples no longer guarantees the independence of the data that we use. Then we cannot make use of common tricks for showing sample mean converging to the population mean (e.g. Hoeffding's inequality), since they require independence of samples. Therefore, we resort to another trick (Lemma 3 of Appendix B.2.1) that resembles triangular inequality, but slows down the rate by $1/2$.

Second, in non-realizable cases, the converging target is no longer the true distribution. Instead, we compromise our goal into the ``best approximation" $\Upsilon_{\tilde{\theta}}$, with $\tilde{\theta}$ defined in Equation (21). That being said, Theorem 1, which only required us to derive the convergence rate of estimated Bellman residual (our objective function), is not enough now. Therefore, unlike realizable scenario, it requires one additional procedure, which is obtaining convergence of the minimizing parameter. This leads us to take into account the function $\psi(\cdot)$ in B.4.3, which further slows down the rate by $1/q$.

Due to the aforementioned reasons, the rate in non-realizable scenario is slower than realizable scenario by $1/(2q)$, that is $\sqrt{\log N/N}$ verses $\sqrt[(4q)]{\log N/N}$.

We will add related discussion to the paper.

References

[1] Morimura, Tetsuro, et al. "Nonparametric return distribution approximation for reinforcement learning." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.

[2] Morimura, Tetsuro, et al. "Parametric return density estimation for reinforcement learning." arXiv preprint arXiv:1203.3497 (2012).

[3] Thanh Nguyen-Tang, Sunil Gupta, and Svetha Venkatesh. Distributional reinforcement learning via moment matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9144–9152, 2021.

Thank you for your constructive comments.

(Weakness 1) Assumptions are strong. Provide examples and give comments on the consequences of relaxing those.

In the following, we provide the corresponding discussion of individual assumptions. We have also put some additional explanation below Assumption 8 in the updated manuscript.

First, we discuss the crucial assumptions.

• Assumption 1: This corresponds to coverage assumption that is essential for every OPE method, (e.g. FLE [1], Section 5.5 of [2]). It includes all examples where density can be lower-bounded by a positive number $\inf_{s,a}b_\mu(s,a)>0$.
• Assumptions 5 & 8: Based on these, we can quantify model complexity and non-realizability with $\tilde{\eta}$, as well as bound the estimation error. As mentioned in the manuscript, $\tilde{\eta}=\mathbb{W}_{1,\infty}$ (supremum-extended Wasserstein-1 metric) is an example that satisfies these requirements.
• Assumption 7: Lipschitz continuity allows us to control the model complexity via the metric entropy of $\Theta$ with respect to the Euclidean norm (see Remark 2). Combined with compactness, it also prevents ill-posed cases where the estimated objective function $\hat{F}_m^{(B)}(\cdot)$ does not have a minimizer (in $\Theta$). Our simulation examples in Appendix D.4 all satisfy this condition when we let $\tilde{\eta}$ to be supremum-extended Wasserstein-1 metric.

The following assumption is the strength of our paper, since it is already weak (realizable scenario) or has been even further relaxed (non-realizable scenario).

• Assumption 2: Realizability is already weaker than completeness which is widely assumed in the other papers (e.g. [1], [3], [4]). Even those who relaxed completeness (e.g. $\rm [5]$) are still assuming realizability, but we took an even further step by relaxing it in Theorem 3 (non-realizable scenario).

The remaining assumptions are relatively less crucial. They are assumed in order to make the proof simpler, and they can be relaxed.

• Assumption 3: Subgaussian distribution (e.g. Gaussian, bounded distributions) is widely assumed to apply standard concentration inequalities. We can assume slower-decaying tail probability, however this further complicates the analyses.
• Assumption 4: iid assumption can be relaxed into trajectory-based observations $(s_t,a_t,r_t,s_{t+1})$ ($1\leq t \leq N$). In this case, we would need additional assumptions (e.g. exponential $\beta$-mixing in Definition 1 of $\rm [6]$) to ensure an appropriate decaying rate of the dependence.
• Assumption 6: The role of polynomial degree $q\geq1$ is to quantify the convergence rate (Theorem 3), and we can still obtain consistency without it. Here is one example. Assume the same setting in Section 5, only differing in reward distribution $R(s,a)\sim N(0,1)$ for all $s,a$ and the model $\Upsilon_\theta(s,a)=\phi(0,\theta/(1-\gamma^2))$ with $\theta\in\Theta=[0,2]$, where $\phi(\mu,\sigma^2)$ indicates gaussian probability with parameters $\mu$, $\sigma^2$. Then we have a unique minimizer $\tilde{\theta}=1$ and $F(\theta)\geq F(\tilde{\theta})+c_1\cdot |\theta - 1|^2$ holds for some $c_1>0$, leading to $q=2$.

(Question 2) How does it compare with the paper about Linear MDP or average-reward MDP?

First, in the suggested paper [7], they are interested in estimating the average reward throughout infinite time progress $J_\pi = \lim_{T\rightarrow \infty} \mathbb{E}( \frac{1}{T} \sum_{t=1}^{T} r(s_t,a_t) )$. This is different from EBRM (our method) which is interested in estimating the distribution of return (cumulative discounted summation of consecutive rewards) in Equation (1) of our text. Due to the difference between the target quantities (expectation vs. distribution; limiting average vs. discounted sum), it is not clear how to compare these two methods.

Next, linear MDP may be useful in expanding our method into continuous state-action space by expressing the transition probability and reward distribution as linear combinations of multiple features $\phi(\cdot,\cdot):\mathcal{S\times A}\rightarrow \mathbb{R}^n$. To elaborate, it may allow us to construct an unbiased estimate of energy distance for continuous state-action space, where a single $s,a$ cannot be observed twice or more (almost surely). In such cases, our current estimation in Equation (10) leads to a biased estimate of the third term of expansion of $\mathcal{E}(\Upsilon_\theta(s,a), \mathcal{T}^\pi \Upsilon_\theta(s,a))$ shown in Equation (9), which is $\mathbb{E}|| R_\alpha + \gamma\cdot Z_\alpha(S_\alpha',A_\alpha';\theta) - R_\beta - \gamma\cdot Z_\beta(S_\beta',A_\beta';\theta) ||$. Here, we have $(R_\alpha,S_\alpha'), (R_\beta,S_\beta')\sim p(\cdots|s,a)$ and $A_\alpha'\sim\pi(\cdot|S_\alpha')$, $A_\beta'\sim\pi(\cdot|S_\beta')$, where $\alpha,\beta$ are for indicating independent copies. According to our current way of estimation (10), our estimate becomes $\mathbb{E}|| \gamma\cdot Z_\alpha(s',A_1';\theta) - \gamma\cdot Z_\beta(s',A_2';\theta) ||$ with $A_1',A_2'\sim\pi(\cdot|s')$ being independent. This is because the terms $\hat{R}_{i}=r$ ($i=\alpha,\beta$) have the same value, and are thereby cancelled out when there is only a single observation $(s,a,r,s')$. This bias might be prevented if we can estimate the distribution of terms $\hat{R}_i\sim\hat{p}(\cdots|s,a)$ ($i=\alpha,\beta$) (for $s,a$ that was observed only once) by expressing them with features. In addition, leveraging the structure of the linear MDP may improve the efficiency of our method. It will be interesting to see what the structure of return distribution induced by the linear MDP is, which requires further investigation. We will add some discussion on this reference in the paper.

References

[1] Runzhe Wu, Masatoshi Uehara, Wen Sun: Distributional Offline Policy Evaluation with Predictive Error Guarantees. ICML 2023: 37685-37712

[2] Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). The MIT Press.

[3] Duan, Yaqi, Zeyu Jia, and Mengdi Wang. "Minimax-optimal off-policy evaluation with linear function approximation." International Conference on Machine Learning. PMLR, 2020.

[4] Agarwal, Alekh, et al. "Reinforcement learning: Theory and algorithms." CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 32 (2019).

[5] Zanette, Andrea. "When is realizability sufficient for off-policy reinforcement learning?." International Conference on Machine Learning. PMLR, 2023.

[6] Antos, András, Csaba Szepesvári, and Rémi Munos. "Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path." Machine Learning 71 (2008): 89-129.

[7] Nevena Lazic, Dong Yin, Mehrdad Farajtabar, Nir Levine, Dilan Gorur, Chris Harris, and Dale Schuurmans. A maximum-entropy approach to off-policy evaluation in average-reward mdps. Advances in Neural Information Processing Systems, 33:12461–12471, 2020.

(Question 1) Why does EBRM outperform FLE? Is it due to the difference in focus (marginal distribution versus conditional return distribution)?

Both FLE [1] and EBRM (our method) are for off-policy evaluation. We believe the reviewer's question is regarding the performance of the two methods in terms of policy evaluation instead of policy learning (that is, finding the optimal policy).

First, we provide some explanations why the proposed EBRM achieved better performance than its competitors. The first explanation is that none of the simulated examples satisfy completeness, which FLE requires as its assumption. On the contrary, EBRM can be applied when completeness is violated, including realizable and non-realizable scenarios. Such effect becomes more apparent in our most difficult non-realizability setup (non-realizable example of D.2.3 with $\gamma=0.99$ demonstrated in bottom plots of Figure 3). The performance of FLE even deteriorates with larger sample size, and this pattern is consistently observed with other measures of inaccuracy (Tables 11, 12, and 13 of Appendix D.4.2). Another plausible reason is that FLE is not utilizing the closed-form probability measure in each update. Whenever they update their estimation at $t$-th iteration, they sample finitely many samples from the previous estimate $\Upsilon_{\theta_{t-1}}(s,a)$, which is prone to approximation error.

Second, it is true that [1] measured inaccuracy of FLE estimation by comparing the marginal return distribution $\Upsilon^{marginal}$, which is the mixture distribution with mixture components {$\Upsilon_\pi(s,a): (s,a)\in\mathcal{S}\times\mathcal{A}$} and mixture weights {$b_\mu(s,a): (s,a)\in\mathcal{S}\times\mathcal{A}$}. Therefore, we hereby evaluate the inaccuracy according to their method (Corollary 4.14 of [1]), by comparing the marginal distributions $\Upsilon_{\hat{\theta}}^{marginal}$ and $\Upsilon_\pi^{marginal}$ via Wasserstein-1 metric $\mathbb{W}_1$. The results, as shown in the following two tables, are based on the same simulations shown in Tables 8--13 of Appendix D.4, but evaluated based on marginal distribution. As in previous results (Tables 8--9, 11--12), EBRM outperformed its competitors in all except for the non-realizable scenario with $\gamma=0.50$, where the performances between EBRM and FLE are very close.

• Realizable: $\sigma_0^2=20$

• Realizable: $\sigma_0^2=5000$

• Non-realizable: $\gamma=0.50$

• Non-realizable: $\gamma=0.99$

Dear reviewers,

we sincerely appreciate your time and effort in reviewing our paper and responses. We hope that our reply has addressed your concerns. Please let us know if you have further comments or suggestions. Thank you once again for your detailed review and constructive feedback on our work.