Thank you for your constructive comment. We have have conducted additional experiments as you suggested.
Thank you very much for your constructive feedback and inspiring comment on our draft. We hope to answer your questions by providing more theoretical details and additional experiments.
> r dependence on the behavior policy may cause problems when data is collected using multiple behavior policies.
In the theoretical analysis, we made a simplifying assumption that the heuristic $h$ is a function of the state in Theorem 1. In this case, HUBL can be viewed as solving a stationary reshaped MDP. In Theorem 2, we further consider a special case that $h(s)$ is the value function of a policy e.g. the behavior policy $\mu$ when proving an exact finite sample upper bound. This extra assumption that the heuristic is a policy’s value function is made as a sufficient condition to establish the heuristic is improvable (see [Definition 4.1, Cheng et al., 2021]), which roughly means that the heuristic value is attainable and as a result can guide the learning (i.e. $\tilde{V}^*(s) \geq h(s)$ [Proposition 4.4, Cheng et al., 2021]). This sufficient condition is used to show the second term in the regret $h(s’) - \tilde{V}^\pi(s’)$ can be non-positive:
$\textnormal{Regret}(\pi, h, \lambda):=
\tilde{V}^{\pi^*}(d_0) - \tilde{V}^{{\pi}}(d_0) + \frac{\gamma}{1-\gamma}E_{(s,a,s')\sim d^\pi}[\lambda(s') ( h(s') - \tilde{V}^{{\pi}}(s')) | s, s'\in\Omega ]$
On the other hand, we totally agree that in practical scenarios with mixed behavior policies, the estimated heuristics in Section 4.2 may lead to a non-stationary MDP. As discussed above, the current analysis would work through if this heuristic (in expectation) turns out to be improvable. We think analyzing the exact condition for this to happen in a scenario of mixed policies is interesting, but it’s beyond the scope of the current work. When the resulting heuristic is not improvable, it eventually will lead to an extra error term in Section 4.2. As a result, the performance of HUBL is affected by how well the heuristic function is calculated, which is affected by many factors like the randomness of the environment as you pointed out, the amount of data, the coverage of the data, and so on. Specifically for the randomness in environments, we provided experiments of HUBL with stochastic environments in Section D.3, where HUBL still provides performance improvement.
> Choosing lambda may not be straightforward
When the trajectories perform equally well, HUBL with Rank labeling behaves exactly as you expected: the trajectories will have similar lambda. However, this does not mean that HUBL will necessarily hurt the performance, as there is $\alpha <1$ discounting the amount of heuristics blended into bootstrapping. Empirically, we applied HUBL with Rank labeling on hopper-random-v2, walker2d-random-v2 and halfcheetah-random-v2. The results are provided below. We can see that HUBL is able to improve the performance. However, in this setting, the performance improvement of HUBL is limited. We believe the reason is as you suggested: the $\lambda$ function could not find well-performing trajectories to blend with bootstrapping. A better design for $\lambda$ is required for such scenarios, which is one of our future directions. We will include such discussions in the final version of the submission.
| | Relative Performance Improvement of HUBL | Base |
| --------------------- | ---------------------------------------- | ----- |
| hopper-random-v2 | 4% | 15.18 |
| walker2d-random-v2 | 7% | 3.94 |
| halfcheetah-random-v2 | 0% | 26.1 |
> Why is the training of a value function needed in step 2.
We are not quite sure which step you are referring to as we do not train a value function in Step 2 on page 4. We train a value function in Step 1: Computing heuristic $h_t$ on page 4 (footnote 3). That is because sometimes a trajectory ends not due to reaching a terminal stage but due to a timeout. When this happens, the simple Monte-Carlo sum of the rewards underestimates the value of this trajectory. Therefore, we need to estimate a value function to add at the end of such trajectories.