We thank the reviewer for the comments and apologize for any clarity issue; we will consider adding a central example to improve the clarity of the introduction.

Sadly, due to the page limit, we had to move to the appendix some parts of the proof that we also find essential - we intend to use all the extra space in the camera-ready version to both address the remarks in the different reviews and then move proof sketches/figures to the main text of the paper. As space permits, we will prioritize the parts suggested by the reviewer.

We thank the reviewer for the opportunity to highlight our contributions. Reward lookahead is a different feedback paradigm than the standard one in RL that covers many realistic settings. This includes the trading/traffic examples in the people, but also other situations - for example, if the rewards depend on the weather forecast (e.g., in electricity grids). In some situations, it naturally exists, while in others, agents must actively pay to gather this information. The goal of our work is to establish a deep understanding of the effect of this information on the value. This has a direct implication when information has a price, but even when it is free - algorithms that incorporate lookahead are naturally much more complex and are oftentimes tailored to each specific application. It is thus important to ask how much do we expect to gain from using this information before deciding whether it is worth the direct and indirect costs.

While we agree that the environment that yields worst-case behavior is somewhat intuitive, we emphasize that our results also give a tight characterization as a function of the dynamics of the environment - we believe that these results are not straightforward (as we elaborate in the answer to question 1). In particular, if we are interested in the CR for a specific environment, the ratio $CR(P,r)$ can easily be calculated using standard planning modules while $CR(P)$ forms a zero-sum game between two Markov policies. Our results also draw a surprising link between reward lookahead and coverability/other concentrability coefficients; in particular, to our knowledge, it is the first instance where coverability appears intrinsically and not as an assumption/constant in upper bounds. As a final note, the definition of the CR is invariant to scaling, and since long-shot distributions are bounded, the same ratios $CR^L(P)$ and $CR^L$ would also be obtained when only considering Bernoulli rewards. Thus, to get different ratios, it is not enough to limit ourselves to ‘standard’ distributions, but we might also need additional regularity conditions.

Questions:

1. We agree that for delayed trees, longshot rewards are an intuitive choice. However, we would like to emphasize that we prove that longshot rewards are the worst-case for any dynamics and/or expected rewards, a result that we find unintuitive. This includes dense environments such as contextual bandits and situations with tradeoffs between navigation and reward collection such as in the chain (prophet)/grid examples. We also believe that the derivation of the closed-form expression of $CR(P)$, though relying on well-known tools such as the minimax theorem, was non-trivial to devise.
   Delayed tree and non-stationary environments: as a remark, we intentionally chose to present a worst-case environment with stationary dynamics – otherwise, one could legitimately claim that the $H$ dependence might be due to the non-stationarity, and a tighter bound of $\approx SA$ could be the ‘right’ CR in stationary environments. Moreover, even in non-stationary environments, we believe that a similar loop mechanism is still necessary. The idea is to create an environment where only one reward could be collected (to minimize the value $V^0$), but the probability of collecting this reward greatly increases when lookahead information is available. For the first part - the states where a reward could be collected must be transient (so that no-lookahead agents would not be able to go back there), while for the second part, we need to allow the lookahead agent to decide when to collect the reward based on its observed information – so the environment requires some waiting mechanism.

2. While we did not study it in this paper, we believe that some of our techniques could be extended to discounted situations, and maybe (under some regularity conditions) to stochastic shortest paths. We leave this for future work. For infinite-horizon average reward, it is not too hard to prove that the CR can approach zero even for environments with a constant number of states (by controlling the effective horizon via loops), but it is still interesting to analyze the CR as a function of the dynamics.

3. As previously mentioned, one could take the closed-form expressions in the theorems and evaluate them on non-toy applications that have lookahead information. In the paper itself, we aimed to give closed-form results and intuition, so smaller examples were more natural. In particular, the examples studied in the paper give valuable insights into different properties of environments and their effect on the value of lookahead information (reward density, navigation elements, etc.)
   We also believe that the connection to coverability\concentrability could lead to additional theoretical applications - in any situation where coverability appears, one could reformulate the problem using the ratio between lookahead values as an analysis tool.

We thank the reviewer for the insightful comments.

1. Thanks for the comment. To the best of our knowledge, there are two types of rollout approaches that are applied in control/RL: i) Rollout as a tool to perform planning: in this case, it is a computational scheme, and no future information is revealed. This kind of rollout is less relevant to our work (even though it might later be used as a planning tool for multi-step lookahead). In particular, ‘standard’ Q-values at the leaf of a rollout usually fall under this case. ii) Rollouts with additional information about state-reward realization: to our knowledge, this case is a particular instance of the Model Predictive Control Paradigm. We will try to clarify our discussion to reflect this, and will be happy to hear about any specific reference that the reviewer thinks we should discuss.

2. The no-lookahead agent is the standard agent used throughout the RL literature and serves as the ‘off-the-shelf’ agent. Therefore, the competitive ratio in our paper quantifies the maximal potential gain when moving from the standard RL scenario to agents that utilize future reward information. For example, consider a situation where we might get lookhead information, but obtaining it has a price (either because the information itself is costly or just because the lookahead algorithm is much more complicated). The CR can help determine whether the potential gain is worth the price. Another application is RL with adversarial rewards - as mentioned in Remark 1, our CR is an upper bound on the best achievable CR in adversarial settings. In fact, for full lookahead, one could calculate the policy that optimally covers the space (see, e.g., Al-Marjani et. al, 2023), and our results imply that it achieves the optimal CR with adversarial rewards. Finally, our results provide interesting insights on sequential decision-making and MDPs. In particular, our results provide a new definition of the coverability coefficient that goes beyond the mathematical expression: the worst case CR between vs. full lookahead given the dynamics. To our knowledge, this is the first result that obtains the coverability coefficient as an intrinsic quantity - previous papers only rely on it for the analysis or obtain upper bounds that depend on it. We will further discuss this in the final version of the paper.

3. We apologize for the confusion. When we say that rewards are dense, we assume that if a reward could be obtained for one action in some state, then the expected rewards of all other actions of this state can be at most $C$ times lower. If all the expected rewards at some state are zero, then the rewards will deterministically be equal to zero (since the rewards are non-negative), and such states do not affect this result. When this assumption holds, the cost of balancing immediate reward collection and future reward collection is bounded - even if we focus on future rewards, we still collect a fraction of the best immediate reward. This is not the case, for example, in the prophet problem - we either collect immediate rewards and move to non-rewarding states or collect a zero immediate reward and move to a state with a positive value. We will rephrase this example to make it clearer in the final version of the paper. We are also open to suggestions on alternative names for this scenario.

4. We completely agree that taking this work to practical settings is an important future work - we will discuss it in the final version of the paper.

We thank the reviewer for the feedback.

• Perfect future information: as stated in the conclusions section, we agree that situations with noisy/imperfect predictions are of great interest and should be further investigated in future work. Nonetheless, we believe that the case of perfect information is still important to study, due to multiple reasons:

1. Applicability: in some problems, perfect or near-perfect information is available. For example, consider an inventory management problem, where supplies are bought in a market. The item prices are exactly known before each transaction, even if the market itself is stochastic - so this scenario could be formulated as one-step reward lookahead. Another scenario is ride-sharing: assume we travel between two points but are willing to pick up other travelers on the way. The knowledge of where and when travelers want to be picked from is (approximately) accurate.

2. A stepping stone towards predictions. The case of perfect information is the edge case in many different formulations of reward predictions. One formulation is when predictions become increasingly noisy as we look further into the future; our results are the limit case of no-noise up to a certain point, and infinite noise later on. Another situation is when predictions can either be perfect or adversarial, and agents need to learn how to utilize the prediction without losing too much if they are inaccurate (‘consistency-robustness tradeoff’); our paper analyzes the ‘consistent’ case. In both cases, it would be extremely hard to analyze the general case without having tight characteristics at the limit of perfect information.

• Lookahead in complex environments: we also think that extending our analysis beyond tabular environments is very interesting and could have numerous practical implications. Yet, we would also like to stress that even in the tabular setting, there are many interesting open questions: planning with multi-step lookahead information, learning when lookahead information is available, tight characterization of transition lookahead and more. We believe that before moving to more complex settings, it would be beneficial to establish a deeper understanding of lookahead in tabular settings.