We thank the reviewer for the further comments. We are grateful for the reviewer's feedback which has helped improve the clarification of the presentation of our paper.
We believe the root of the confusion might be Line 7 of Algorithm 1. We believe we would be better served if we wrote the output as $Uniform(\pi^1, \ldots, \pi^t)$ (there is no sampling over $h$). In other words, Algorithm 1 does not return a mixture policy, even though we may have referred to it as that in the rebuttal. Note that nowhere in the paper do we even use that word. What the Algorithm returns is one of the $T$ policy iterates uniformly sampled. Since each policy iterate is Markovian, what the algorithm returns is Markovian. We apologize for using that terminology in our earlier response. It might have caused unnecessary confusion.
Regarding the bound itself, we give a high probability bound on the sub-optimality of the output of Algorithm 1. As we noted above, the output of Algorithm 1 is a Markovian policy. We should also add that the sub-optimality is defined w.r.t. any comparator policy (i.e., results hold for all $\pi \in \Pi^{all}$). We can always choose the comparator policy $\pi$ to be $\pi^*$, so we do bound the near optimality of the policy returned by the learner. The source of randomness as we said before is the offline data and any internal randomization of the algorithm — this is typical in guarantees of this form. We are not deviating from the norm here in specifying these bounds (e.g., see the bounds of similar algorithms in [ZWB21,XCJ+21,CXJA22] for the norm of presentation). For better presentation, we can take the expectation with respect to the randomness of the algorithm when writing out the bound. So, we will replace $SubOpt_{\pi} (\hat{\pi})$ in Theorems 1 and 2 by $ \mathbb{E} [SubOpt_{\pi}(\hat{\pi}) | \mathcal{D} ] = V_1^{\pi}(s_1) - \frac{1}{T} \sum_{t=1}^T V_1^{\pi^t}(s_1)$, and clarify that the expectation is taken w.r.t. uniform sampling of the iterates. The only source of randomness that would remain then is the randomness inherent in the offline dataset.
Would that change be acceptable to the reviewer? We do think that will make things very clear.
---
For an alternative presentation, we also propose a different approach to addressing the confusion. This approach is essentially equivalent to the first approach above but totally avoids using the term “uniform distribution” over $\pi^1, …, \pi^T$ as the output of Algorithm 1. We propose to revise Line 197 (and thus Line 7 of Algorithm 1 accordingly) to read: “After $T$ update steps, Algorithm 1 *deterministically* outputs a single policy $\hat{\pi} = (\hat{\pi}_1, \ldots, \hat{\pi}_H)$ where we define $\hat{\pi}_h(a|s) = \frac{1}{T} \sum\_{t=1}^T \pi^t_h(a|s)$ for any $h \in [H]$" (please note that $\hat{\pi}_h$ is computed *deterministically* from $\pi^1_h, …, \pi^T_h$ without defining “uniform distribution” as the output of Algorithm 1). With that, since each policy iterate $\pi^t$ is Markovian, what the algorithm returns $\hat{\pi}$ is also Markovian.
Now, by linearity of the value function $V^{\pi}$ in terms of $\pi$, we have $V_1^{\hat{\pi}} (s_1)= \frac{1}{T} \sum_{t=1}^T V_1^{\pi^t} (s_1) $. This is a *deterministic* relation, without defining “uniform distribution” as the output of Algorithm 1. Consequently, we have the following *deterministic* relation:
$ SubOpt\_{\pi}(\hat{\pi}) = V_1^{\pi}(s_1) - V_1^{\hat{\pi}}(s_1) = V_1^{\pi}(s_1) - \frac{1}{T} \sum_{t=1}^T V_1^{\pi^t}(s_1) = \frac{1}{T} \sum_{t=1}^T ( V_1^{\pi}(s_1) - V_1^{\pi^t}(s_1))$.
Here, there is no internal randomization in the algorithm (as we do not define “uniform distribution” as the output of Algorithm 1) and the only source of randomness in our algorithm and in our high-probability bounds is the offline data.
Would that change also be acceptable to the reviewer? We think either of the approaches would help address the unnecessary confusion in our submission version.
Again, we apologize for the unnecessary confusion.
---
We would also add that in our proof of bounding the value sub-optimality of $\hat{\pi}$, we do bound the value sub-optimality $V_1^{\pi}(s_1) - V_1^{\pi^t}(s_1)$ of each individual $\pi^t$. Specifically, using Lemma B.4 in our supplementary: $V_1^{\pi}(s_1) - V_1^{\pi^t}(s_1)= \sum_{h=1}^H \mathbb{E} [\mathcal{E}\_h^{\pi^t}(Q_h, Q_{h+1})] + Q_1(s_1, \pi^t_1) - V_1^{\pi^t}(s_1) + SubOpt_{\pi}^{M(Q, \pi^t)}(\pi^t)$ for any $t \in [T]$. From Lemma B.6: $\sum_{t=1}^T SubOpt_{\pi}^{M(Q, \pi^t)}(\pi^t) ≤ Hb \sqrt{T \ln |\mathcal{A}|}$ (it holds deterministically). The high-probability bounds come from bounding $\sum_{h=1}^H \mathbb{E} [\mathcal{E}\_h^{\pi^t}(Q\_h, Q_{h+1})] + Q_1(s_1, \pi^t_1) - V_1^{\pi^t}(s_1)$ for any $t$. In fact, we bound $\sum_{h=1}^H \mathbb{E} [\mathcal{E}\_h^{\tilde{\pi}}(Q_h, Q_{h+1})] + Q_1(s_1, \tilde{\pi}_1) - V_1^{\tilde{\pi}}(s_1)$ uniformly over all $\tilde{\pi} \in \Pi^{soft}$ as $\pi^t \in \Pi^{soft}$.