Response to Reviewer C4A2
Thanks for your timely response and for agreeing with our explanations to most of your questions!
To better answer your question and avoid any unnecessary confusion, we first briefly summarize the logical flow of the paper.
1. We propose a robust OPE procedure.
2. We leverage the above procedure to construct a bi-level policy optimization algorithm, which is our information-theoretic algorithm.
3. We establish strong regret guarantees for the information-theoretic algorithm, e.g., Theorem 4.1, and we name the results as information-theoretic results.
4. We find our information-theoretic algorithm is computationally inefficient due to solving constrained optimization, while the information-theoretic results demonstrate desirable theoretical properties of the algorithm.
5. We propose a practical algorithm, i.e., the penalized adversarial estimation, for implementation and empirical evaluation.
6. We study the theoretical properties of the practical algorithm, i.e., Theorem 5.1, and find it inherits desirable characteristics of the information-theoretic algorithm but with sample complexity degradation.
7. We perform a study of the practical algorithm in linear MDPs.
> **The importance of the information-theoretic results**:
By the logical flow, we first develop the information-theoretical algorithm and it is natural to study its theoretical properties. In addition, there are several major reasons that explain why the information-theoretic results matter.
- As a theoretical-based paper (while we still provide a practical algorithm with comprehensive empirical evaluation), our information-theoretic results help to position our work in the existing literature and highlight our theoretical contributions in offline RL. We can fairly compare our results to the existing information-theoretic results, e.g., [1,2,3,4],
in terms of the function approximation and coverage conditions, sample complexity, horizon dependency, and bound tightness. Following the convention, all these existing algorithms are purely information-theoretic without practical implementation.
- The information-theoretic findings enhance the understanding of the practical algorithm. Specifically, a comparison between Theorem 4.1 and 5.1 reveals that Theorem 4.1 has a tighter bound than Theorem 5.1. This delivers an important message: to attain computational efficiency, the practical algorithm compromises on sample efficiency, i.e., $O(n^{-1/4})$ vs $O(n^{-1/2})$.
- The information-theoretic results provide a well theoretical justification for the information-theoretic algorithm. While the algorithm currently grapples with computational efficiency challenges, resolving these issues could offer significant advantages. This paves the way for developing a more refined algorithm in offline RL.
> **The connection between the information-theoretic results and the practical algorithm**:
By the logical flow, although the information-theoretic results are not directly developed for the practical algorithm, they do have some indirect relationships. The error decomposition technique is shared between the information-theoretic results and the results for the practical algorithm, while the development of the latter is much more involved (optimization error, mirror-descent update, and a trajectory-dependent bound). Second, following a similar proofing strategy, the results in Theorem 4.2, Corollary 4.1, 4.2 can be established for the practical algorithm as well. To keep completeness, we will add these new results in the updated supplementary materials.
> **Bound tightness**:
In terms of the dependency on $n$ or horizon, Theorem 4.1 is an ultimate regret bound and has achieved the minimax results [5]. Furthermore, as indicated by Theorem 4.1, it observes a trade-off between bias $\epsilon_b$ and variance $\epsilon_\sigma$, affecting the bound tightness. In fact, Theorem 4.1 intrinsically chooses the best bias-variance decomposition through the best choice of $\mathcal{U}^\star_2$. It's important to note that this decomposition is solely a proof technique, not a knob in the algorithm. Combine with the adaptation $\rho$ via $\min\{\rho: ||\rho/\mu||_{L_2(\mu)} \leq \mathcal{U}^\star_2\}$, we can conclude that our regret bound is hard to be further improved unless with additional conditions e.g., coverage or explicit MDP structure.
We hope these explanations adequately address your concern. We remain dedicated to refining our paper and welcome any further comments. Once again, thank you for your invaluable contribution to our work!
**References:**
[1] Jin, Y., et al. (2021), Is pessimism provably efficient for offline rl, ICML
[2] Uehara, M., et al. (2022), Pessimistic model-based offline rl, ICLR
[3] Zhan, W., et al. (2022), Offline rl with realizability and single-policy concentrability, COLT
[4] Chen, J., et al. (2022), Offline rl under value and realizability, UAI
[5] Xie, T., ta al, (2020), Q* approximation for batch rl, UAI