Dear area chair,
Thank you for your questions.
1. The key reason that our paper breaks through the lower bound is the different definition of regret, and in particular, the definition of the optimal value. Specifically, denote $V^*$ the standard no-lookahead value used in RL, and $V^{R, *}$ the reward lookahead value, with the corresponding regret bounds $Reg$ and $Reg^R$.
Notice that for any agent (lookahead or not), one can always write $Reg = (V^* - V^{R,*})K + Reg ^R$.
By definition, the lookahead agent is more powerful, so mostly $V^* < V^{R,*}$. Since the first term in the decomposition above is negative linear while the second term is just sublinear, any difference between the values imposes a *negative linear regret* - completely breaking the standard lower bounds in RL.
For example, in Section 3, we described situations where $V^*\approx 1/AH$ while $V^{R,*}\approx 1$. Then, in terms of standard regret, for large enough $K,A,H$ we would get $Reg \approx -K$. We can add this explanation to the paper.
* In Jin et al. (2018), they have $T=HK$ (see caption under table 1), where $K$ is the number of episodes (as in our paper). Therefore, the lower bounds are the same - both allow non-stationary transition.
2. While reward learning doesn't usually dominate the rates, it is due to horizon factors: reward learning usually leads to a term of $\sqrt{H^2SAK}$ while transition learning to $\sqrt{H^3SAK}$. Even if we can just discretize the state for the reward component to a state $S^d$ (while not changing transition learning complexity), we would still have unavoidable dependence in the regret on $S^d$. Importantly, $S^d$ needs to encompass the reward observations for *all actions simultaneously*, so even if we use $N$ cells to discretize each reward component, we would get a term of $N^A$. Therefore, as soon as we do it, our bounds would explode (even if reward learning would just have affected the additive constant!!).
Moreover, moving the reward to the state means that reward observations are now state transitions, so using standard approaches would lead to a regret bound of $\sqrt{H^3S^dAK}$.
You are completely right about the transition lookahead - since we need to add the next state observation for all actions simultaneously, the state blows by a factor $S^A$.
We actually already use the augmented MDP for both proofs (mostly for the planning results) and describe in detail one way to do this extension in Appendices B.2 and C.2. If the AC thinks it would help clarity, we could further discuss it in the main paper. We could also discuss more about the implications of augmentation and discretization on learning, extending the discussion in this response.
----
We hope that we clarified all the issues; we will gladly provide more clarifications if we did not convey the message clearly enough and answer any other questions.