Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL

Thank you for your positive comments. We would like to respond to some of your listed weaknesses and questions.

1. Weaknesses/question 2: Closing the gap between the upper and lower bounds (for the amount of data required for transient states) is the main quantitative/information-theoretical question left unresolved by our work and is an interesting question for future research. Our conjecture is that the lower bound is basically tight, and that potentially the same algorithm with a sharper analysis could be used to close the gap.
2. Question 1: We believe that there is a very high possibility that the quantile clipping technique could be applied in other settings to obtain sharper (span-based) penalty/bonus terms. The most direct application in online RL would likely be to the discounted setting (considered in e.g. arXiv:2010.00587), but as you suggest, it seems likely that improvements for discounted online RL could then be useful for the average-reward setting (possibly through a direct reduction between the settings).

Thank you for your positive comments. Below we respond to your questions.

1. Question 1: In Theorem 3.3 $\delta$ is actually the failure probability parameter. The suboptimality of the policy is $1/2$ (with probability at least $\delta$) in the theorem, so in short, the transient data coverage assumption is necessary at least for any suboptimality less than $1/2$.
2. The hard instances used in Theorem 3.3 are actually unichain, so the direct answer is no: even for unichain MDPs, transient data coverage is necessary in general to get a convergence rate scaling with the bias span of the optimal policy (as opposed to a uniform-style parameter like the uniform mixing time; see the paragraph beginning on line 263 for more discussion on which convergence rates are shown by Theorem 3.3 to be impossible without transient data coverage).
3. You are correct that the uniform mixing time is large for the family of hard instances used in Theorem 3.3, so in this sense, uniform-mixing-based bounds would also suggest that these instances are difficult. However, as mentioned in the paragraph after Theorem 3.3, the uniform mixing time and the policy hitting radius parameter (as used in the transient data coverage assumption) actually behave in fundamentally different ways for these instances: as the parameter $m$ is increased the policy hitting radius stays bounded (by the other parameter $T$), while the uniform mixing time grows proportionally to at least $m$. Notice that because the uniform mixing time is $\Omega(m)$, any offline RL theorem with a convergence rate depending on the uniform mixing time like $O\left(\sqrt{\frac{\tau_{unif}}{m}}\right)$ (in the best case/ignoring other factors) would have a vacuous $O(1)$ suboptimality bound for these instances, whether or not transient data is provided. On the other hand, our lower bound shows that non-vacuous suboptimality is impossible when there is insufficient transient data, but once there is enough transient data, then our upper bound can apply and yield a vanishing suboptimality (as $T$ is fixed and $m$ increases). In summary, no algorithm with a uniform-mixing-based convergence guarantee would yield nonvacuous performance bounds for these instances, while our algorithm and lower bound together reveal that vanishing error is possible but only with sufficient transient data.

Thank you for your positive comments. We agree that the transient data coverage assumption, which our lower bound shows is necessary, is nevertheless an assumption which may not always hold in practice. We believe that by identifying this obstacle, our work may help lead to future research which can circumvent this issue, possibly by identifying forms of side information which can be provided to algorithms to prevent them from failing in the difficult scenario where there is no transient data coverage. For example, it may be sufficient to have knowledge that all nonzero transitions have probability at least $p$ for some known $p > 0$ (enabling the algorithm to estimate the support of $P$). Also, as you mention, our work can handle more general classes of MDPs than prior work, and the amount of transient data needed for vanishing suboptimality is $O(1)$ (independent of $m$ and bounded in terms of $T_{hit}$ of only the target policy).

Thank you for your positive comments. We now discuss a few points related to your question regarding key elements of the algorithm and analysis.

1. One key algorithmic feature is the use of quantile clipping and an empirical-span-based penalty function. This point is discussed in greater detail in the paragraph starting on line 195 as well as the proof sketch in section 4, but here we provide a brief summary. Using an empirical-span-based penalty term is essential for the average-reward setting, intuitively because it avoids a dependence on the effective horizon $\frac{1}{1-\gamma}$, which must be taken very large to obtain good average-reward performance. Naive implementations of empirical-span-based penalties fail (by breaking the monotonicity and contractivity properties of the associated pessimistic Bellman operator), but the new quantile clipping technique remedies these issues, getting the sharper penalty terms to work. As mentioned by reviewer Agk8/our response to reviewer Agk8, we feel like these sharper penalties may be of broader interest and utility.
2. It is possible that a key missing idea from previous work was the observation that transient data coverage is required. Since this is shown to be necessary by our Theorem 3.3, it suggests that prior attempts to obtain convergence rates involving single-policy complexity measures without this assumption were doomed to fail.
3. Many algorithms in the average-reward setting are plagued by the need for prior knowledge of complexity parameters (such as bias span or mixing time) in order to run the algorithm. Our algorithm does not face such difficulties, and we believe the analytical techniques we use to avoid this problem (discussed in the paragraph beginning on line 333) may be of independent interest to researchers working on average-reward RL.