Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback

We are grateful for the reviewer's detailed comments and constructive suggestions. Below we present our response.

Regarding significance: We would like to stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe our work is non-trivial in terms of technique.

Regarding technical novelty: While the algorithmic framework depends on previous work, the key technical observation is that the number of possible trajectories $O( (SA^H)$ is smaller to that of possible policies $O( A^{SH})$. This is why we can remove the extra $\sqrt{S}$ factor compared to previous work Efroni et al., 21.

Regarding the large burn-in terms: Indeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. The current term is $S^{24}A^4H^{32}$. The main reason of such a large burn-in term is due to learning the reference model. This term can be significantly reduced under the assumption of an effective reference model.

Regarding other comments:

About the typos: Thanks for pointing out the typos. We will fix the typos accordingly in the next revision. In the second typo, we use $d_{P}^{\pi}$ to denote the feature vector with respect to $\pi$, which does not depend on the trajectory $\tau$.

About the preference-based learning: Preference-based RL (PbRL) is another RL paradigm to deal with the lack of reward signals. We will discuss the similarities and differences between the two settings in the next revision.

Regarding the questions:

Abut the exact burn-in term: Following the current analysis, the final regret bound is $\tilde{O}(\sqrt{SAH^3K}+S^{24}A^4H^{32})$.

About the extensions to other settings, e.g., linear MDP and MDP with function approximation: At the moment, we are not aware of any possible extensions to linear MDP or MDP with function approximation. We believe these problem settings should enjoy some advantages of low-rank structure so that we can construct a feature space with lower dimensions. For example, in linear MDP, we can take $(\phi_{s_1,a_1}, \phi_{s_2,a_2},..., \phi_{s_H,a_H})$ as a $dH$-dimensional unified feature to learn the reward kernel $(\theta_{1}, \theta_2,..., \theta_H)$. However, the exploration and policy design over this feature space is more complicated compared to the counterparts in the tabular case. It requires more efforts to solve the experimental design problem over these complicated structures.

About learning the reward and transition kernel simultaneously: Thanks for the interesting question. Although we cannot establish this definitively, we conjecture the answer is negative in the worst case. The problem could be reformulated as finding a mixed policy $\bar{\pi}$ to meet two following conditions simultaneously (we set $\phi(\tau)$ to be $\phi_{\tau}$ for display):

$\min_{\bar{\pi}\in \Delta^{\Pi}}\max_{\pi\in \Pi}\sum_{\tau}Pr_{\pi,P}[\tau]\phi^{\top}(\tau)\Lambda(\bar{\pi})^{-1}\phi(\tau)=O(SAH)$

$\min_{\bar{\pi}\in \Delta^{\Pi}}\max_{\pi\in \Pi}\sum_{s,a,h} \frac{d_{P}^{\pi}(s,a,h)}{d_{P}^{\bar{\pi}}(s,a,h)}=O(SAH).$

For the first problem, the target is to maximize $\log(\det(\Lambda(\bar{\pi})))$ where we recall that $\Lambda(\bar{\pi}) = \sum_{\tau}Pr_{\pi,P}[\tau]\phi(\tau)\phi^{\top}(\tau)$. For the second problem, the target is to maximize $\log(\Pi_{s,a,h}d_{P}^{\bar{\pi}}(s,a,h))=\log(\det(diag(\Lambda(\bar{\pi})))$, where $diag(\Lambda)$ denotes the matrix by setting all non-diagonal elements of $\Lambda$ to 0. As a result, the two optimization problem are substantially different when $h\geq 2$. So we conjecture that the answer to your question is probably negative in the worst case.

We are grateful for the reviewer's detailed reviews and valuable suggestions. Below we present our response.

Regarding Lemma B.1: In Lemma B.1, $\bar{\pi}$ represents a mixed policy. That is, by following $\bar{\pi}$, the learner takes each deterministic policy $\pi\in \Pi$ with a certain probability as $\lambda(\bar{\pi},\pi)$. As a result, $F(\bar{\pi})$ could be regarded as a multi-variable function with respect to the probability vector $[\lambda(\bar{\pi},\pi)]_{\pi\in \Pi}$. We will revise the proof accordingly in the next version.

Regarding clarification of KW theorem: In the proof, we do not directly use KW theorem. Instead, we generalize the KW theorem to a distributed version in Lemma B.1. In the next revision, we are planning to present the original version of the KW theorem together with our generalized version to make the difference clear.

Regarding computational inefficiency: We admit that the current algorithm is computationally inefficient, and indeed, devising algorithm with minimax optimal regret bound and polynomial running time for RL with trajectory feedback is an intriguing open problem. However, we notice that obtaining statistically (nearly) optimal algorithms is usually the first step for completely settling problems in machine learning theory, and we believe our techniques would be useful for later developments in the theory of RL with trajectory feedback.

Regarding large burn-in terms: Indeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. On the other hand, we would like stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe it is reasonable to have large burn-in terms in our bound. Moreover, we believe our new techniques are crucial for fully understanding the regret bound of RL with trajectory feedback.

Regarding other comments and suggestions:

About lines 282-284: We will rewrite this sentence as "Instead of approximating $P$ by $p$ under the $L_1$-norm, it is required the trajectory distribution under $P$ could be covered by that under $p$, up to a constant ratio."

About line 208: Thanks for pointing out the typo. We will fix accordingly.

Regarding the elimination-based online batch learning: In this work, the fundamental problem is still reinforcement learning. More precisely, even if assuming that the reward is known, we are required to learn the transition kernel. This step cannot be trivially implemented using a linear bandit algorithm. As a result, we choose to use a linear bandit algorithm to learn the reward function and an RL algorithm to learn the transition kernel. Another two reasons to apply the eliminated-based batch learning are that: (1) Designing an algorithm that can simultaneously learn both the reward function and transition kernel presents significant challenges. As a result, we have to learn the reward and transition kernel separately; (2) By batch learning, we can efficiently reduce the statistical dependencies between different batches, which makes the analysis less complicated.

We sincerely appreciate the reviewer's thorough evaluation and constructive feedback. Below we present our response.

Regarding the computational issue:

We admit that the current algorithm is computationally inefficient, and indeed, devising algorithm with minimax optimal regret bound and polynomial running time for RL with trajectory feedback is an intriguing open problem. However, we notice that obtaining statistically (nearly) optimal algorithms is usually the first step for completely settling problems in machine learning theory, and we believe our techniques would be useful for later developments in the theory of RL with trajectory feedback.

Regarding the burn-in terms:

Indeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. On the other hand, we would like stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe it is reasonable to have large burn-in terms in our bound. Moreover, we believe our new techniques are crucial for fully understanding the regret bound of RL with trajectory feedback.

Regarding other comments and suggestions:

About $c(s,a,h)$: We are sorry for this mistake. $c(s,a,h)$ is only used in the analysis for Algorithm 5. We will move the definition of $c(s,a,h)$ to Appendix D.4 in the next revision.

About $\delta$ in Algorithm 2: We will use $\delta$ as a common parameter across all algorithms and delete $\delta$ from the input of Algorithm 6.

About parameters in Appendix.A: Thanks for the suggestion. We will refine the lemma statements to improve clarity.

About the proof overview of Theorem 5.6: Thank you for pointing out the typo. It should be $\tilde{y}=2\epsilon_{\ell}$.

About $\tilde{P}$ in Lemma 5.2: Thank you for pointing out the typo. We will replace $\tilde{P}\to \hat{P}_2$ accordingly.

About Eq.(28): Here we use the fact that $\log(A)\log(B)=O(\log^2(AB))$ for $A,B\geq 1$. We have revised the inequality and reset the value of $\epsilon_0$ as $\epsilon_0=90000\log^3(\frac{SAHK}{\delta})\left( \frac{SAH^2}{K^{\frac{1}{4}}}+\frac{S^4AH^6}{K^{\frac{1}{2}}} \right)$. There should be an extra $H$ factor in the right-hand side of Eq.(28) to make the inequality holds. The revised version of Eq.28 is as follows. $\max_{\pi\in \Pi_{\mathrm{det}}}| W^{\pi}(\hat{R},P) - W^{\pi}(R,P)|\leq H\sqrt{\log(SAH)\log(16/\delta)}\left(b_1+ 325\sqrt{\frac{SAH\log(K)\log(8SAH/\delta)}{\bar{K}_1}} \right)\leq 1000\log^2\left(\frac{SAHK}{\delta}\right)\cdot \left(\frac{SAH^2}{K^{\frac{1}{4}}} + 4SAH^2b_1 \right).$ We remark that this $H$ factor is in the second order term so the final regret bound is still asymptotically optimal.

About $\mathcal{R}$: We are sorry for the abuse of notations. You are correct that $\mathcal{R}$ is the confidence region defined in line 13 of Algorithm 4. The proof of Lemma D.2 is under the proof of Lemma 5.2, which studies the properties of Algorithm 4. We will make this clear in the next revision.We will also replace $\mathcal{R}$ with $\mathsf{R}$ when introducing the reward distribution.

About Eq.(30), Eq.(31) and Eq.(32): Thanks for pointing out the typos. We will fix accordingly.

About the term "reward hacking": We will remove the term "reward hacking" from this paragraph.

About $\sup$: We will replace $\sup$ with $\max$.

About $xy$ and $x^{\top}y$: We will fix the notation about $\sup$ and $x^{\top}y$. We only use $xy$ as a shorthand of $x^{\top}y$ in Appendix D.4 to reduce the complexity of the notations.

About "the regret stemming from learning $\tilde{P}$ can be bounded by ...": We will mention that "$\tilde{P}$ serves as an efficient tool to help design the exploration policy" before this sentence.

We are grateful for the reviewer's detailed assessment and helpful suggestions. Below we present our response.

Regarding your concerns about correctness:

1. In the first $K_0=O(\sqrt{K})$ episodes (other factors ignored), the main target is to identify the infrequent state-action-state triples with probability $O(\sigma_0)=O(K^{-1/2})$. For the left triples, we want to compute an $(3,\sigma_0)$-approximate estimation for the transition probability $P_{s,a,h}$. Note that this approximate transition matrix is only for designing the exploration policy, not for computing the near-optimal policy. Hence, computing such an approximate transition matrix requires only $O(\sqrt{K})$ episodes.

2. We set $\epsilon_0 = O(K^{-1/4})$ ignoring other factors (please refer to Appendix.A). You are correct that it requires $1/\epsilon_0^2$ episodes to learn an $\epsilon$-optimal policy.
   Indeed, we compute this $\epsilon_0$ optimal policy to improve the efficiency of exploration in the following episodes. In the main algorithm, we use $K_0=O(\sqrt{K})$ episodes to identify the triples with probability $O(K^{-1/2})$. If we apply direct exploration, the regret in this stage might be $K_0H$, which violates the minimax bound $O(\sqrt{SAH^3K})$ due to the dependencies on $S,A$ and $H$. Instead, we first compute the set of $\epsilon_0$ optimal policies, and then conduct exploration within this policy set. In this way, the regret due to exploration is bounded by $O(K_1 H + K_0 \epsilon) = O(\sqrt{SAH^3K})$.

Regarding the computational inefficiency:

We admit that the current algorithm is computationally inefficient, and indeed, devising algorithm with minimax optimal regret bound and polynomial running time for RL with trajectory feedback is an intriguing open problem. However, we notice that obtaining statistically (nearly) optimal algorithms is usually the first step for completely settling problems in machine learning theory, and we believe our techniques would be useful for later developments in the theory of RL with trajectory feedback.

Regarding the large dependency on $S,A,H$:

Indeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. On the other hand, we would like stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe it is reasonable to have large burn-in terms in our bound. Moreover, we believe our new techniques are crucial for fully understanding the regret bound of RL with trajectory feedback.

Regarding other comments or suggestions:

We are sorry for the typos. The $T$ notation in Section 5 denotes number of episodes, not number of steps. We will use $\check{K}$ to replace $T$ throughout Section 5 and the corresponding analysis in the next revision. We will also separate $K$ from other factors. The final regret bound would be $\tilde{O}(\sqrt{SAH^3K}+S^{24}A^4 H^{32})$.