Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback

For your questions about (1) the lower order term and (2) the intuition why trajectory-feedback does not hurt the regret performance, please refer to the common response.

About linearity of trajectory reward in Section 3: Thanks for the suggestion. We have provided a proof in the revision, which we also present here. $\mathbb{E}[r_{\tau}] = \mathbb{E}[\sum_{h=1}^H r_h] = \sum_{s,a,h}\mathbb{E}[ \mathbb{I}[(s_h,a,_h)=(s,a) ] ]r_h(s,a) = d^{\top}r$.

About mathematical derivations in Section 5: Thanks for the suggestion. We explain as follows. *

About the second observation in page 5: $d_{P}^{\pi}(s,a,h):=Pr_{\pi,P}[(s_h,a_h)=(s,a)] = \sum_{\tau}Pr_{\pi,P}[,\tau] \cdot I[ (s_h(\tau),a_h(\tau))=(s,a) ]$, where $(s_{h}(\tau),a_h(\tau))$ is the $h$-th state-action pair in $\tau$.

About (3): This equation is based on confidence regions for linear bandits.

About (8): the equation is by definition that $W^{\pi}(r,p) =E_{\pi,p}[\sum_{h=1}^H r_h] = \sum_{s,a,h}d_{p}^{\pi}(s,a,h)\cdot r_h(s,a) = (d_{p}^{\pi})^{\top}r$.

About writings: Thanks for the careful review. We have fixed the typos accordingly in the revision. In Algorithm 2, $\mathcal{D}_2$ is redundant so we remove $\mathcal{D}_2$.

About $\lambda_{\pi}$ in Algorithm 5: In Algorithm 5, we use $\lambda_{\pi}$ to denote the probability of $\pi$ following the probability vector $\lambda$ in Line 12.

About structure of Section 5: We have presented the high-level idea in Section 4. We borrow the ideas to construct a reference model from [1], and then conduct exploration with the help of the reference model. We also present the usage of each algorithm and the corresponding lemmas in Section 5.1-2.

About the double-state reward in Line 310: In Line 4 Algorithm 4, the optimization problem is $\max_{\pi}\Pr_{\pi}[\tau] \min\\{ \phi^{\top}\Lambda^{-1}\phi , 1\\}$. We simplify the target as $\max_{\pi}Pr_{\pi}[\tau] \phi^{\top}\Lambda^{-1}\phi$, which is actually $\sum_{(s,a,h,s',a',h')} \mathbb{I}[(s_h,a_h)=(s,a), (s_{h'},a_{h'}) =(s',a') ]W_{s,a,h,s',a',h'}$ where $W = \Lambda^{-1}$. We name it as the double-state reward function because the classical reward function could be viewed as a single-state reward function, where the reward only depends on one state-action pair. To optimize a double-reward function, the learner makes decisions according to its trajectory, which means its policy is non-Markovian. To our best of knowledge, there is no existing algorithms which could solve this problem efficiently, even if assuming the knowledge of the transition model.

About $\tilde{\pi}$ in Algorithm 4, Line 7: $\tilde{\pi}$ could be regarded as an approximate solution to Eq(6). As discussed above, we do not know how to solve the optimization problem in line 4 algorithm 4 efficiently, which is the major difficult to compute $\tilde{\pi}$.

About burn-in time: According to the final regret bound, the burn-in time would be $S^{24}A^{16}H^{28}$, which is impratically large. The main issue is from the initial step (line 3 in Algorithm 1) to learn the reference model, and it is a challenging problem to reduce this term (e.g., reduce the order of $H$ to tight).

About Design in Algorithm 5: The Design step (Line 11-13, Algorithm 5) stems from experimental design, where the target is to find a distribution over a set of datapoints to maximize some certain potential function.

About the examples in the introduction: Similar examples were indeed discussed by prior work on RL with trajectory feedback (e.g., Efroni et al (2021)) and we will add references in the next revision accordingly.

About comparison with (Efroni et al., 2021): In result, the main contribution is a near-tight asymptotic regret bound. In technique, we formulate the RL problem as a linear bandit problem with feature as the trajectory, while (Efroni et al., 2021) used the occupancy distribution as features. The major difference is that, the number of all possible trajectories is $(SA)^H$, while the number of deterministic policies is $A^{SH}$. This is way we can save an $\sqrt{S}$ factor compared to the best result in Efroni et al., 2021.

About $c>0$ in line 262: It does not depend on the problem. In fact, the exact inequality would be: with proability $1-\delta$, $\Lambda\geq \frac{1}{3}T\Lambda_{\bar{\pi}} -3\log(d/\delta)\mathbf{I}$.

About line 282-285: We present (9) and (10) to explain the high-level idea. There is possibility that some of the concentration inequalities might fail, and the learner would suffer a linear regret $KH$. But this probability is very small, so we ignore this probability in explaining the intuitions. On the other hand, the exact definition of $\Pi_{\ell+1}$ is presented in Line 9 Algorithm 5, where we eliminated policies with value smaller than the best LCB.

About $K_0$: We set $K_0 = 100000S^{4.5}A^{1.5}H^{8.5}\log(\frac{SAHK}{\delta})$ (see Appendix.A).

About computation cost in Algorithm 5 line 9: You are correct about this. In general this step is inefficient. But it is easy to test whether an element is in $\Pi_{\ell}$ since $\max_{\pi}W^{\pi}(u,\hat{p})$ could be computed with optimistic backward planning, which means we can optimize some functions with good properties over$\Pi_{\ell}$ (e.g., value function). However, the target function $\sum_{\tau}Pr_{\pi,p}[\tau]\min\\{ \phi_{\tau}\Lambda^{-1}\phi_{\tau} ,1\\}$ in Line 4 Algorithm 4 is more complicated, where we have to play enumeration to find the solution. This is the main difficulty in making the algorithm efficient in computation.

About more complicated or realistic bandit models: In this work, we introduce linear bandit problem due to the natural formulation of reinforcement learning. As for extensions, it would be an interesting problem to replace the tabular MDP with more complicated MDPs, e.g., (generalized) linear MDP. We think advanced bandit models are related to these problems.

About parameterized policy without elimination: As far as we can see, it is unclear that parameterized policies could help improve the regret bound. On the other hand, we make delayed updates to keep statistical independence, so it might be improper to make frequently updates.

About the case where ewards are nonlinear functions of the trajectories: The general idea is to formulate the problem as a bandit problem with structure. There is possibly more interesting formulation because the arm set in this problem is the set of trajectories, which also has a good structure.

About connections to linear bandits: Thanks for the suggestion and we will improve the presentation accordingly.

Please find our answers to the questions about inefficiency and why trajectory-feedback RL is as easy as standard RL in the common response.

About the constant $c$ in lines 261-262: By this statement, we mean that by running $\pi$ for $T$ rounds to get trajectories $\tau_i$ with feature $\phi_{\tau_i}$ for $1\leq i \leq T$, the information matrix $\Lambda = \sum_{i=1}^{T}\phi_{\tau,i}\phi_{\tau,i}^{\top}$ would be an upper bound of $\frac{1}{2} T E_{\pi}[\phi_{\tau}\phi_{\tau}^{\top} ]$ with high probability (allowing some logarithmic error terms).

About equation (10): Our goal was to present some high-level intuition. In the algorithm, we do not compute $\Pi_{\ell+1}$ with (10). Instead, we eliminate policies by comparing the value of some policy with the best LCB (lower confidence bound) over all policies (see Line 9 in Algorithm 4). By presenting equation (10), we aim to show that, for any policy $\pi\in \Pi_{\ell}$ the gap between its UCB and its LCB is at most $\tilde{O}(\sqrt{SAH^3/K_{\ell}})$. To compute $\max_{\pi}W^{\pi}(\hat{R},P)$, we can run simple backward planning since here we assume the knowledge of $P$. In the case $P$ is unknown, we compute $\max_{\pi}W^{\pi}(\hat{R},\hat{P})$ with optimistic backward planning, where $\hat{P}$ is the empirical transition model.

About small $K$: As far as we see, the answer is negative. Our algorithm depends on the knowledge of a reference transition model which requires a large sample complexity (in $S$, $A$ and $H$) using current techniques.