Achieving Minimax Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach

1. Could the authors provide a more explicit connection between the insight presented below Equation (7) – namely, "However, $\Delta_2=\min_{q\in \hat{\mathcal{P}}} E_q[\sum\gamma^t r_t ] - E_p[\sum \gamma^t r_t ]$" – and the improvements achieved through the Bernstein-style results? While I acknowledge that different distributions may indeed have the same expectations of reward, the paper appears to underutilize this insight in the subsequent analysis without specifying further structure in the reward. As the paper characters the worst-case suboptimality, any possible gap from two expected return from any two neighbor distributions should be included into considerations. It would be beneficial to explore how this observation can be further leveraged in the context of worst-case suboptimality characterization in a more rigorous (mathematical) manner.

2. I would appreciate a more comprehensive explanation regarding the advantages of employing both the chi-square divergence and the Bernstein-style uncertainty set. The paper suggests that the chi-square divergence, when compared to the total variation divergence with the same radius, is less conservative and can save on sample size (N^{-0.5}). However, it remains somewhat unclear how the use of the Bernstein-style radius and the Hoeffding-style radius contributes to saving (1-\gamma)^{-1}, which is the most salient improvement. Establishing a clearer connection between these elements and their implications on the chi-square divergence or the Bernstein inequality would enhance the understanding of their benefits.

To my understanding, the LCB approach essentially draws an uncertainty set around $\hat{P}$ with the radius of the bonus function $b$. This bonus function should ensure that it provides an upper bound of $(\hat{P} - P)^\top V$, and thus the estimated value function $\hat{V}$ is a pessimistic estimate. This is very similar to the DRO approach in the sense that the uncertainty set from the DRO takes the role of the uncertainty set from the LCB approach. Indeed, if we take a look at the effect of the DRO uncertainty set in the analysis, it exactly ensures the pessimistic $V_{\hat{r}, \mathrm{P}}^\pi(s) \geq V_{\hat{r}, \hat{\mathcal{P}}}^\pi(s)=V_{\hat{\mathcal{P}}}^\pi(s)$ and gives rise to the following inequalities for the other terms. $

\left|b^\left(V_{\hat{\mathcal{P}}}^{\pi_r}\right)(s)\right| =\gamma\left|\mathrm{P} _s^{\pi^(s)} V _{\hat{\mathcal{P}}}^{\pi _r}-\sigma _{\hat{\mathcal{P}} _s^{\pi^(s)}}\left(V _{\hat{\mathcal{P}}}^{\pi _r}\right)\right| \leq\left|\mathrm{P} _s^{\pi^(s)}-\mathrm{Q} _s^{\pi^(s)}\right|_1\left|V _{\hat{\mathcal{P}}}^{\pi_r}\right| _{\infty} \leq \frac{1}{1-\gamma} \sqrt{\frac{2 \log \frac{S A}{\delta}}{N\left(s, \pi^(s)\right)}} .

$

I believe the case is similar in the Bernstein-style uncertainty set, where the Chi-squared divergence gives you the variance term to better leverage the Bernstein inequality. I am very curious whether one can set $\sqrt{\frac{2 \log \frac{S A}{\delta}}{N\left(s, \pi^*(s)\right)}}$ as the LCB bonus term and achieve the same result, and similarly for the case of Bernstein-style uncertainty set. The constant terms might be a bit different, but the rest should look the same.

I wonder if the authors can further elaborate on the details of the difference between the LCB and DRO approaches, and show that one cannot be reduced to the other? I am happy to raise my rating if this can be clarified.

1. We know that $d_\mathrm{TV}(p,\hat{p}) = (1/2)\lVert p-\hat{p}\rVert_1$ And it's well-known that there is no dimension-free concentration result for $l^1$ norm. The authors made a mistake when they cite the Hoeffding's inequality in Eq. 10. Intuitively, you are summing up deviations in each coordinate, and the right hand side of Eq. 10 is only the vanilla Hoeffding's inequality bound which is only about the concentration of the empirical mean. See [A] for a simple proof of the concentration of the total variation distance between the true and learned (empirical) distribution. The consequence is that your Hoeffding sample complexity will now scale with $S^2$.

2. I observe that $\mu_\mathrm{min}$ potentially scales with $SA$ when the data generating distribution is a generative model. This could make the worst-case sample complexity in Eq. 9 at least $S^2A^2$ after burn-in cost. Am I missing anything?

In conclusion, I have concern about whether the sample complexity result presented in this paper is really minimax optimal. I look forward to discussing with the authors. Thank you.

[A} Canonne, C. L. (2020). A short note on learning discrete distributions. arXiv preprint arXiv:2002.11457.

Could the author/s make some comments on my review about weakness?