The Value of Reward Lookahead in Reinforcement Learning
Authors: Nadav Merlis
Dorian Baudry
Vianney Perchet
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Reinforcement Learning
Planning
Reward Lookahead
Competitive Ratio
Primary area: reinforcement_learning
TL;DR: The paper studies the potential increase in the value of RL problems given partial observations of the future realized rewards.

Abstract: In reinforcement learning (RL), agents sequentially interact with changing environments while aiming to maximize the obtained rewards. Usually, rewards are observed only _after_ acting, and so the goal is to maximize the _expected_ cumulative reward. Yet, in many practical settings, reward information is observed in advance -- prices are observed before performing transactions; nearby traffic information is partially known; and goals are oftentimes given to agents prior to the interaction. In this work, we aim to quantifiably analyze the value of such future reward information through the lens of _competitive analysis. In particular, we measure the ratio between the value of standard RL agents and that of agents with partial future-reward lookahead. We characterize the worst-case reward distribution and derive exact ratios for the worst-case reward expectations. Surprisingly, the resulting ratios relate to known quantities in offline RL and reward-free exploration. We further provide tight bounds for the ratio given the worst-case dynamics. Our results cover the full spectrum between observing the immediate rewards before acting to observing all the rewards before the interaction starts.

The Value of Reward Lookahead in Reinforcement Learning
Nadav Merlis
Dorian Baudry
FairPlay Joint Team, CREST, ENSAE Paris nadav. www.mmmeeeesss......mmmm
FairPlay Joint Team, CREST, ENSAE Paris Institut Polytechnique de Paris
Vianney Perchet
FairPlay Joint Team, CREST, ENSAE Paris
Critco Al Lab
Abstract
In reinforcement learning (RL), agents sequentially interact with changing envi- ronments while aiming maximize the obtained rewards. Usually, rewards are observed only after acting, and so the goal is to maximize the expected cumulative reward. Yet, in many practical settings, reward information is observed advance prices are observed before performing transactions; nearby traffic information is partially known; and goals are oftentimes given to agents prior to the interac- tion. In this work, we aim quantifiably analyze the value of such future reward information through the lens of competitive analysis. In particular, we measure the ratio between the value of standard RL agents and that of agents with partial fetard lookahead. We characterize the worst-case reward distribution and derive exact ratios for the worst-case reward expectations. Surprisingly, the sulting ratios relate to known quantities in offline RI. and reward-free exploration. We further provide tight bounds for the ratio given the worst-case dynamics. Our results cover the full spectrum between observing the immediate rewards before acting to observing all the rewards before the interaction starts.
Introduction
Reinforcement Learning [RL. Sutton and Barto 2018 is the problem of learning how interact with changing environment. The setting usually consists of two major elements: a transition kernel, which governs how the state of the environment evolves due the actions of agent, and reward given to the agent for performing an action at a given environment state. Agents must decide which actions to perform in order collect much reward possible, taking into account not only the immediate reward gain, but also the long-term effects of actions on the state dynamics.
In the standard RL framework, reward information is usually observed after playing action, and agents only aim to maximize their cumulative expected reward, also known as the value [Jaksch et al. 2010, Azar al. 2017 Jin et al. 2018, Dann et al. 2019 Zanette and Brunskill 2019 Efroni et al. 2019b Simchowitz and Jamieson 2019 Zhang et al. 2021bb. Yet, in many real-world scenarios, partial information about the future reward is accessible in advance. For example, when performing
transactions, prices are usually known. In navigation settings, rewards are sometimes associated with traffic, which can be accurately estimated for the near future. In goal-oriented problems (Schaul et al.) 2015 (Andyychowicz et al., 2017), the location of the goal is oftentimes revealed in advance. This information completely ignored by agents that maximize the expected reward, even though using this future information on the reward should greatly increase the reward collected by the agent.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

As an illustration, consider driving problem where an agent travels between two locations, aiming to collect as much reward as possible. In one such scenario, rewards are given only when traveling free roads. It would then be reasonable to assume that agents see whether there is traffic before deciding in which way to turn at every intersection ('one-step lookahead"). ) an alternative scenario, the agent participates in ride-sharing and gains a reward when picking up passenger. In this case, agents gain information on nearby passengers along the path, not necessarily just in the closest intersection ("multi-step lookahead"). Finally, the destination might be revealed only at the beginning of the interaction, and reward is only gained when reaching it ('full lookahead"), ) In all examples, the additional information should be utilized by the agent to increase its collected reward.
In this paper, we analyze the value of future (lookahead) information on the reward that could be obtained by the agent through the lens of competitive analysis. More precisely, we study the competitive ratio (CR) between the value of an agent that only has access to reward distributions and that of a lookahead agent who sees the actual reward realizations for several future timesteps before choosing each action. Our contributions are the following: (i) Given an environment and its expected rewards, we characterize the distribution that maximizes the value of lookahead agents, for all ranges of lookahead from one step to full lookahead; this distribution therefore minimizes the CR. In particular, we show that the lookahead value is maximized by long-shot rewards- very high rewards at extremely low probabilities. (ii) We derive the worst-case CR as a function of the dynamics of the environment (that is, for the worst-case reward expectations). Surprisingly, the CR that emerges is closely related to fundamental quantities in reward- free exploration and offline RL [ii et al. 2022 Al-Marjani et al. 2023). (iii) We analyze the CR for the worst-possible environment. Specifically ly, tree-like environments that require deciding both when and where to navigate exhibit near-worst-case CR. (iv) Lastly, we complement these results by presenting different environments and their CR, providing more intuition to our results.
The idea of utilizing lookahead information to update the played policy is related to a control concept called Model Predictive control [MPC, Camacho et al. 2007]. also known as receding horizon control. In complex control problems, it could be challenging to predict the system behavior in long horizons due to errors in the model or nonlinear dynamics. To mitigate this, MPC designs a control scheme for much shorter horizons, where the model is approximately accurate. oftentimes a simplified (e.g., lincarized) model. Then, to correct the deviations due to modeling errors, MPC continuously updates the controller according the actual system state. In context, the localized system estimates could be seen as lookahead information. Similar ideas have also been used for planning in reinforcement learning settings [Tamar al., 2017 Efroni et al., 2019a 2020). Yet, these concepts are mainly used to improve planning efficiency and account for nomlineartieesdissurbaaee in the model. A few notable exceptions study the competitive ratio (and/or dynamic regret) between
Related Work.
controllers with partial lookahead information to ones with full information (Li et al., 2019 Zhang
jet al., 202 la Lin et al., 2021 2022] a different measure than ours. Moreover, there no clear way to translate any of these results into tabular problems.
The special case of one-step lookahead, where immediate rewards are observed before making decision, has been studied in various problems. Possibly the most famous instance of such a problem is the prophet inequality. There, set of known distributions is sequentially observed, and agents choose whether to either take a reward and end the interaction or discard it and move to the next distribution [Correa al. 2019b). This could be formulated as chain environment with two actions - a rewarding action that moves to an absorbing state and a non-rewarding one that moves forward in the chain. A generalization of the prophet problem to resource allocation over Markov chains was studied in Dia et al.) 2023). To obtain a CR that is independent of the interaction length, the authors allow both the online and offline algorithms
choose their initial state. In both cases (and many other problems), the CR is measured between a one-step lookahead and a full lookahead agent, which observes all rewards in advance. In contrast, we measure the CR between no-lookahead agents and all possible lookaheads, so our results are complementary.
Finally, Garg al. 2013 studied another related resource allocation model. In their work, the competitive ratio for Markov Decision Processes is measured between an online agent with access to the L-future reward distributions and transition probabilities, versus an agent who observes all statistical information in advance. A similar adversarial notion is also presented specifically for resource allocation. In contrast, we assume that the distributions are known to both agents and only the oracle observes reward realizations.
2

---

2
Preliminaries
We work under the episodic tabular reinforcement learning model. The environment is modeled as Markov Decision Process (MDP), defined by the tuple (S, A, P. R. p), where S is the state space ((S) S), A is the action space (IAAI A), H N is the horizon, P is the transition kernel, R is the stochastic reward and J E As is the initial state distribution. At the first timestep, an initial state is generated $1 ~ μ. Then, at every timestep h E [H] A {l...., H. given environment state Sy E S, the agent performs action dn. E A. obtains stochastic reward R ($,, ap, and transitions 8h+1 E S with probability Pa ( as.. For brevity, we use the notation X' = [H] x S x A.
state
We assume that rewards at different timesteps are independent, but allow them to be arbitrarily correlated between state-actions at the same step. We denote the expected reward by rh, a) and assume that the rewards are non-negative Rewards and transitions are always assumed to be mutually independent, and transitions are independent between rounds. While we focus on non- stationary models, where the reward and transition distributions could depend on the timestep h, our analysis techniques could be easily adapted to stationary models, where the distributions are dumestep-independeee and all the proofs in the appendix also state the results for stationary models.
2.1 Lookahead Policies and Values
We assume w.l.o.g. that all rewards are generated before the interaction starts. We denote by the set of all rewards timestep h and by R [R.)+t/- /+ the L-lookahead reward information, containing all reward information for L-timesteps starting from h. By convention, R2. is the empty set. A lookahead policy is defined as follows.
R2 [R (s,
Definition 1. lookahead policy x² [H]
RRLL + A is a policy that for each timestep h, observes the state 3h and the lookahead reward information R2 and generates an action aj with probability n.. (an|sk, R.). The set of all lookahead policies is denoted by 11
For example, one-step lookahead policy observes the immediate rewards at the current state before acting. while full lookahead policy has access to all reward realizations before the interaction starts. When L = 0, the policy only depends on the state and is Markovian; we therefore denote 11-M 11
The goal of any agent is to maximize its cumulative reward, also known as the value, VL.
E + (sh, s1 p, T For brevity, we omit the conditioning the initial state distribution.
-
The optimal value given a lookahead L is F = sup,4emt VL,= If we want to emphasize that an environment parameter (say, the transition kernel P) is fixed, we shall specify it, e.g., VL (P, r).
We analyze the relation between the 'standard value" of an agent that plays optimally using no future information (v70.) and a lookahead agent that observes the L-future rewards before acting (V L.*. Formally, let D(r) be the set of all non-negative distributions with rewards expectations rn (8, a). The L-lookahead competitive ratio (CR) is defined as
inf (P,r(P,)) CR CR.(PPr) RHrD((r (P,r)
(1)
That is, the competitive ratio is the worst-possible multiplicative loss of the standard (no-lookahead) policy, compared to an L-lookahead policy, given fixed transition kernel and expected rewards. For ratios to be well-defined, we follow the convention that any division by zero equals +oo.
We emphasize that the reward distributions are known in advance to both the no- lookahead and the L-step lookahead agents, in striking contrast to adversarial settings. In the latter, the reward could be arbitrary and is only given to an oracle agent. In particular, any upper bound on CR (P, r) will also apply to adversarial settings.
Remark 1.
Remark 2. Without lookahead information, P and r suffice to calculate the optimal value {Sutton
and Barto 2018], so one could also write (R.((P,T) sup V2.-(P.))
(P.r)
We similarly study the L-lookahead CR for the worst-case reward expectations, defined a CR (P) = inf, (Pr).. Finally, we study the CR for the worst-case environment
'This assumption is standard when performance is measured by ratios otherwise, ratios are not dell-def While we limit the expectations to [0, 1]. the same results hold for ra R (see Remark 3 in the appendix).
3

---

P and initial state distribution μ4, denoted by CR'. In particular, we show that stationary environ- ments achieve wors--ooste CR.
Interpretation: the gain from lookahead information. The no-lookahead agent is the standard agent used throughout the RL literature and serves as 'off-the-shelf" agent. As such, the competitive ratios quantify the potential gain when moving from classic RL settings to agents that utilize future reward information. While using future information always increases the value, often comes at some price- either because access to such information is costly, or since lookahead algorithms are much more complicated and computationally expensive. The CRs analyzed in the paper can help determine whether the potential gain is worth the price and choosing which agent to deploy.
2.2 Occupancy Measures
Occupancy measures are the visitation probabilities of an agent in different state-actions. In par- ticular, for any (potentially lookahead) policy, we define di Pr(ss, 8} and (s, a) Pr(s), = s, αλ = a), where randomness is w.n.t both transitions, rewards and internal policy ran- domization, given that actions are generated from the policy
II', For h 1, the state distribution only depends on the initial state distribution 14, and we use di (s), di(s) and ju()) interchangeably. We also define the conditional occupancy measure di, [s]s; 8') Pr(sn = 8|8; s'} for some t & h and similarly use dz, (8, a 8 = s'). Intuitively, this is the reaching probability from state s' at time to state at time h when playing a policy æ. Without lookahead information, it well-knows that the set of occupancy measures induced by Markovian policies is a convex compact polytope Altman 2021]. 1, and the value of any Markovian policy could be expressed using occupancies by
V0,=
Σ
RA Sh. an)
=E
Σ
1f8h = s, RM
(h.s,a)Ex
Σ
Pr(sh = 8,00
s,00 - ())
= Σ ()) (2)
(K,8,))X
(h.,,))X
Finally, denote the optimal reaching probability to state s S as (s) mM di (s). Notice that rewards and transitions are independent, so reward information does not affect the optimal reaching probability and it is sufficient to look at Markovian policies. Moreover, after reaching a state 8, an agent could always deterministically choose an action a, so (). = max (s,a)) = (s).). Similarly, we define the optimal conditional reaching probability as di, (8/81 = 8') max di 8s = 8'), and as the for non-conditional occupancy measures, we have that d;, (s, a|s; = s') di (s|s: =').
3 Competitiveness Versus Full Lookahead Agents
Before analyzing the CR for the full range of lookahead values, we start by studying the full lookahead case, where all rewards are observed before the interaction starts. This regime is applicable, for example, in goal-orie oriented problems, where goals are given to the agent before an episode starts (Andrychowicz et al. 2017). Notably, we show a link between the CR for the worst-case reward expectations, CR (P). and existing complexity measures in offline RL and reward-free exploration. While the results of this section will later be covered by the more general multi-step lookahead, this case gives valuable insights on the worst-case distributions. Moreover, much of the proof techniques presented in this section will later be used to prove the results for the multi-step lookahead.
When all rewards are observed before the interaction starts, each instantiation of the reward is equivalent to an RL problem with known deterministic rewards. In particular, the optimal policy given the reward is Markovian, and using the value formulation in Equation ( we have
(H:,(P.r)) =E
max SETTM
Σ
dh (s)
SE
Σ
max Rs TETM
(h.s,))x
Σ
[[))))[R((s,))]====
Σ
(s))((()))))
(3)
(h,s,a)E
(K.8,))
4

---

At first glance, this bound seems extremely crude - the agent optimally navigates to collect all the expected rewards. Yet, at a second glance, gives intuition on the worst-case distribution: a situation where only one reward at single state is realized in every episode. Then, full lookahead agents can optimally navigate to this state and still collect all the realized rewards. While we cannot fully enforce a single reward realization (due to the independence of rewards in different timesteps), we can approximate this behavior by focusing on long-shot distributions [Hill and Kertz 1981].
Definition 2. Rewards have long-shol distributions with parameter é (0, and expectation if
[R a) = ={ (n,8aa/e w.p. w.p. 1 -
vh E [H], & S,aEA:
independently for all h, 8, a. We also use the notation R LS.
Notice that for any given e, long-shot distributions bounded; thus, long-shot rewards could always be scaled to be supported by [0, 1] without affecting the CR. Moreover, when e < 1 1/SAH, with high probability, at most single reward will be realized, and the bound in Equation 3 is achieved in equality as c - O. Formally, the CR versus a full lookahead agent characterized as follows:
Theorem 1. /CR versus Full Lookahead Agents; see Appendix forr the proof]
Worst-case distributions: CR (P,r) max Ejhiaaee (3.2))))
(hea)eN (,(3))n(saa)
Worst-case reward expectations: CR (P) = max min d7,())
(1.0)
Worst-case enviromments: For all environments, CR 2 max f 5AH (r) ). Also, for any 6 (0, 1) there exist stationary environments with rewards over [0, 1] s.t. if = A" +1for E (0..... H 1}.
then CR (P,r) S
14-
and if S 2 A 1, then (P.r) S
1+5 A
Sketch. Part I. Recalling Remark and Equation p). to prove the first part of the proposition, Proof Sketch. one only needs to calculate the full lookahead value for the worst-case distribution. An upper bound for this value is already given in Equation (3): we directly calculate the value for long-shot distributions (r) and show that this bound is achieved at the limit of + 0.
Part II. The proof of the second part of the theorem utilizes the previously calculated CR" (P.r) to optimize for the worst-case expectations. This done using the minimax theorem, exchanging the reward minimization and the policy maximization. To make the internal maximization problem concave, we move from the space of Markovian policies to the set of occupancy measures induced by Markovian policies, which convex [Altman| 2022]. To make the reward minimization convex, we show that the denominator can be converted to the constraint Li..s.ae di (s)r a) = 1. Then, the minimax theorem can be applied, and we explicitly solve the resulting optimization problem. The formal application of the minimax theorem and its solution is done in Lemma iin the appendix.
Part III. The proof of the final statement is further divided into two parts.
Lower bounding CR The lower bound CR > 1/A" is inductively achieved from the dy- namie programming equations for both the no-lookahead and full lookahead values. The bound CR 2 1/SAH is obtained by choosing specific policy E II and substituting in CR (P):
the Markovian policy whose occupancy is d (s. = नसस Env J') of Fhrrs (s,a), where is a policy that maximizes the reaching probability to (h, s,0) E
Th,sa E ITM
Upper bounding CR - designing a worst-case environment. We show that a modified tree graph achieves
competitive ratio. In tree-based MDPs, each state represents a node in a tree, with the initial state as its root, and actions take the agent downwards through the tree. In our example, rewards are long-shots located at the leaves of such trees. However, this structure, by itself, does not lead to the worst-case bound. Intuitively, standard RL agent would navigate to the leaf with the maximal expected reward, while an agent with full lookahead would navigate the leaf with the highest reward realization. Since there are at most S leaves with A actions in each, this would lead to CR (P) 33. tree, we allocate one action to 'delay' the entrance to the tree and stay in the root (as illustrated in Figure in the appendix). While agents without lookahead have no incentive to use this action, full lookahead agent could predict when reward will be realized and enter the tree at timing that allows
I. This is improved by simple modification:
the root of the
5

---

its collection. When H is large enough (compared to the tree depth), this allows the full lookahead agent to have approximately H attempts to collect reward and lead to the additional H-factor (up to
log factors). The proof could be extended to any value of S by allowing the tree to be incomplete we refer the readers to the remark at the end of Proposition T in the appendix for more details. D
Surprisingly, the CR for the worst-case reward expectation CR (P) is the inverse of a concentrability coefficient that appears in many different RL settings, called the coverability coefficient. In particular, it affects the learning complexity in both online and offline RL settings, where agents must learn to act optimally either based on logged date or interaction with the environment (Xie et al., 2022 has a central role in reward free exploration, where agents aim to learn the environment so that they can perform well for any given reward function [AI-Marjani ct al. 2023]. We emphasize that the lookahead setting is fundamentally different we assume that all agents have exact information on both the dynamics and reward distributions and ask about the multiplicative performance improvement due to additional knowledge on reward realization. In contrast, in learning settings, the main complexity is usually in learning the dynamics, and the rewards are oftentimes assumed to be deterministic. Moreover, the analyzed quantities are either regret measures or sample complexity, which cannot be directly linked to the competitive ratio.
also
The last part of Theorem [ shows that tree-like environments with a delaying action at their root exhibit worst-case CR. Similar delay mechanisms were previously used to prove regret and PAC lower bounds for nonstationary MDPs [Domingues et al. |021 Tirinzoni et al. 2022]. though with major difference- - in previous works, a nonstationary reward distribution is used to force the agent to learn when to traverse the tree and where navigate, and the reward is time-extended (obtained for (HH) rounds). In contrast, our formulation is fully stationary and a reward can only be collected once. Still, the lookahead agent can use the delay to linearly increase the reward-collection probability, without any need to create time-extended rewards.
4 Competitiveness Versus Multi-Step Lookahead Agents
We now generalize the results of Section 3 and analyze the competitive ratio compared to L-lookahead agents, for any possible lookahead range L E [H]. We also give special attention to the case of one-step lookahead, where the immediate rewards are revealed before taking an action.
Inspired by the full lookahead case, we focus on long-shot rewards. For such rewards, an agent would expect to see more than single reward during an episode, which would only be discovered L-steps in advance. As such, a reasonable strategy would play a Markovian policy that maintains a 'favorable' state distribution, such that whenever and wherever future reward is realized, the agent could optimally navigate to it. Letting (h) be the time step where the fi-step rewards are revealed to an L-lookahead agent, this corresponds with the following worst-case value:
Proposition 2. For any L E [H], let tu (h) max(h- - 1, Then, it holds that
VL. (L,r( = R#wD(()
sup
max TELLM
rh(s, a) (L,8,))
Σ
Σ di di (s'd (s)5 = s') S'ES
The proof can be found at Appendix B It comprised of calculating the value of long-shot rewards Rt ~ L.S. (r) at the limit when e - 0 and then showing that the same quantity also serves as an upper bound of the value for all reward distributions.
For full lookahead, we have tH (h) = 1, and di (k) becomes the initial state distribution μ.. This
leads to the same value as in Equation 3 The second extremity is when L= 1 and & (h) = h. Then,
the conditional occupancy is di 81z (h) = s') = Iss s'} and we get the simplified expression
VI.*(P,))= = max
Σ ())
sup RH~D(()
TEIL
(N.e.))E
Notably, this is the value of an agent that collects the rewards of all the actions in visited states (regardless of the action it actually played) but has no lookahead information.
'A subtle difference between the coefficients is whether the outer maximum is over all valid occupancy measures or all possible actt-n distributions; see AAlMarjani et al. 2023 Section 2.3] for further discussion.

---

Recalling Remark 2 one could use Proposition 2 to directly calculate (P.). This, in turn, allows analyzing the worst-case reward expectations and environment, as stated in the following:
Theorem 3. /CR versus Mulii-Step Lookahead Agents; see Appendix B for the proof] For any I. E [M), let Ir (n) = max(h h- I. 1, 1, Then, holds that:
c Laha (a(a,))
Worst-case distributions: CRR(P,r) mAx (mmaaee Ph(s,a) 2 t S2 (n) (1)
Worst-case reward expectations:
ds.(s,a)
CR)(P)= min max T'EII TElM (h,,,))X Eves df kn(()) (5'd =
min
Worst-case environments: For all environments, CR 2 max SAH (H-L+1)A² Also, for any
5 10,1) there exist stationary environments with rewards over [0, S A for E {0, (0,...,I L 1}, then (P,r $ ( 1+8
(H- and S 2 A 1, then
(R,((P)) S (1A4-1)
145
Proof Sketch. Sketch. The first part of the theorem a direct result of Proposition and Remark 2 For the second part, we first rewrite
Eihaoaex ans, E E(h,s,)ex (s a) Eves Tr (s)s)(()))))) = -'EIIM FElM
(P,r)=
min max
and as in the full lookahead case, we apply the minimax theorem using Lemma [ However, direct application would require calculating the infimum over x' IT-M and not minimum. Thus, compared to the full lookahead, we also need to prove that the minimum is obtained in this set. We do so in Lemma 2
relying on the set of occupancy measures being a convex compact polytope.
In the last part, we use the same tree example to upper bound (P,r),,) r). The lower bound is proven using a reduction from the full lookahead bound. In particular, the bound of 1/SAH trivially holds from the full lookahead case. For the second lower bound, we devise Markovian policy Th such that for the appropriate choice of reward functions r", we prove that
V (P.r) 2 H- + (Pr)(P,r)
max EXuoreSXA EitZ-1 r (s. (8, (s,a =') Ei+L-1
min NE [L+)
E(sateSXA Eit I as s')
EES
Each of the terms is the competitive ratio versus a full lookahead agent with horizon L that starts acting at 8; = s'. Hence, by Theorem 1 all terms are bounded by Ą.. To elaborate, the reward r limits the reward only to the new timesteps the lookahead agent gets observe when reaches step i, The policy Tu is mixture (in the occupancy space) of policies т. that start by playing the Markovian policy that maximizes the value Proposition 2 up timestep and then maximizes r"
Theorem 3 extends the full lookahead results of Theorem I and tightly characterizes the CR for the full spectrum of lookaheads, both function of the environment and for the worst-case environments. Notice that even though lookahead policies are highly non-M Mon-Maroovian, all bounds are expressed using Markovian policies.
One-step lookahead. In the case where the immediate reward is observed before acting, Theorem proves that even for the worst-case environment, CR O ( namely, independent of the size of the state-space. Morcover, for any transition kernel P, the CR is given by
CR' (P) = min max min (s, x' EIIM MEI (k,a,))xX d7 (s)
(5)
While the coverability coefficient of CR" (P) requires policy π to cover all states simultaneously proportion to their optimal reaching probability, (P) provides a weaker coverability notion: requires being able to cover any pre-known state-distribution induced by a Markov policy x². We emphasize that æ must cover this distribution using all actions, so imitating the behavior of n" might be challenging with ratio of 1/AH as the worst case.
7

---

81n
$2.1
$1,2
$2.3
$1.1
(a) Chain MDP: agents start the head of chain and can either move forward in the chain or transition to an absorbing terminal state.
(b) Grid MDP: agents start at the bottom-left corner of an n x n grid and can move either or right, until ending at the top-right corner after 2n 1 steps.
Figure I: Examples: CR for grid and chain environments.
Thus, CR! could be seen single-policy coverability [Xie et al., 2022]. defined by the ratio between the state-action occupancy of the optimal policy and single data distribution. Yet. Xie et al. [2022] argue that this notion is too weak to allow any guarantces. It is of interest to investigate whether our refined notion, which requires covering all valid state distributions, mitigates the issues they present and allows deriving meaningful results in offline and online RL.
intermediate point between the coverability coefficient and
In general, one could interpret the ratios CR+(P) class of decreasing (inverse) concentrability coefficients, starting from the coverability of all pre-known state distributions (CR and ending with the coverability coefficient (C (P)). Thus, it is intriguing to further study the connection of these values to other domains in which concentrability naturally arises.
Examples
We now present several MDP structures and analyze their competitive ratio for various lookaheads.
Disguised contextual bandit AA-Marjani al., 2023). Maybe the most basic scenario is when actions do not affect the transitions, i.e., ( 18, a) = (x for all possible (4, 8, 8'). Specifi- cally, the state distribution is independent of the played policy there exists occupancy measure dy such that for all policies, (s) = (s). Thus, it also holds that di (s) = dy (s). and
dz (8,a) max min xEIL has,a ds) MEll h,s,a (s)s)
de (s)r
CR
min
max min nA (als) A' TELL h.s.a
The last equality holds since T (als) ) E A Using the same arguments, one could also obtain this CR for one-step lookahead, by the monotonicity of the CR in the lookahead, CR²(P) 1 for all L E [H]. This is to be expected- - without control over the dynamics, the best lookahead agents could do is to maximize immediate rewards, and any additional lookahead information is useless. Then, in each state, knowing the realization can only increase the reward by a factor of Elmax, [s,sa)) max, (s,))
< A.
Delayed trees.
This is the example described in the proofs of the main results, also detailed in Proposition 1 and depicted in Figure In such environments, we get worst-case CR of CR (P,r)=
θ mmx
[H-LAA 3AH ))- These trees are an extreme case where lookahead information is not only used to collect immediate rewards but rather to navigate to long-term rewards.
Chain MDPs. We go back to a bandit-like scenario and add limited control on the dynamics, in the form of chain. The agent starts at the head of the chain (81), and each node i of the chain, it could choose to advance to the next node by taking the action a = ag or to move to an absorbing terminal state sy by taking any other action. The environment is depicted in Figure [(a]
'The sequence is decreasing by definition because increasing the lookahead only extends the policy class.

---

One special problem that falls into this structure is the prophet inequality problem. In particu- lar, assume that reward can only be obtained when moving from the chain to the terminal state (vki a, (8k, 01) = ( a) 0). Thus, at each node of the chain, the agent chooses whether to collect a reward and effectively end the interaction or discard it and move forward in the chain. In other words, the problem becomes an
problem. As such, it is reasonable to allow the agent to see the instantancous rewards before deciding whether to stop, leading to one-step lookahead agents. This problem has numerous applications, especially in the context of posted-price mechanisms [Correa et al., 2017 2019a]. A classical result is that the CR between one-step lookahead and full lookahead agents al always bounded by 1/2 (Hill and Kertz 1981
Assuming this reward structure with the worst-case reward distribution, the full lookahead agent could reach all rewards and collect them, thus collecting V (P.r) Σ EeEA I's (kk,,,, a) (as in
Equation L Similarly, a one-step lookahead agent could move forward in the chain using the policy T& (* = an while effectively collecting all rewards and achieving the same value (see Equation (4). In contrast, no-lookahead agent would have to choose single reward to collect, obtaining a value of / (P.r) = m MEE Thk (kk: (5k: a). The resulting CR for this reward structure would be
maX (ME.AA AK Σ TREATH(SK.))
1 (A 1)H
where the inequality is since there are only A rewarding actions, and equality is achieved when all expected rewards are equal. Notably, the reward structure in the prophet problem is wort-worst-;ase; one could verify that for chain MDPs, it holds that CR (P) 2 (1 2) 1
AH- This is due to the
second part of Theorem 1 using the following policy: for all chain states k E [M], move forward w.p.
T& (a1]))) = H and play any other action >> w.p. Ty. = (+) = (A-1)и At the absorbing state sr, play uniformly nn (a:ls)r = 1/A. This simple example provides two important insights.
Hardness versus one-step lookaheud: chain MDPs exhibit the worst-case CR versus one-step looka- head agents. A central reason is that to move towards rewarding states (forward in the chain), agents must take non-rewarding actions (az)~ there is tradeoff between gathering instantaneous rewards and moving to future rewarding states.
Easiness versus full lookahead: as previously mentioned, the CR between one-step and full lookahead agents is the well-known prophet inequality and is at least 1/2; In other words, for chain MDPs, the information- -aii from one-step-to full lookahead is marginal compared to the value of one-step versus no- nookooaahedd. This is mainly because navigating to rewarding states is especially easy in chain MDPs the agent only has to move forward. In contrast, in environments where navigating to rewarding states is difficult (e.g., the tree environment described in the main results), there is a substantial gain the full lookahead.
These insights motivate two natural assumptions that reduce the CR.
Dense rewards. Assume that in all states where the reward can be strictly positive, it holds that max, (a.))))
min, [s,s,a) < C. That is, if there exists rewarding action at state, all its actions yield some minimal reward. States are allowed to yield zero rewards for all actions. When this assumption holds, agents could navigate to rewarding future states and still collect rewards, mitigating the issue observed in the chain MDPs. Letting म¹ E arg max Σ E(hss,)ex (n as) we have
CR.(P,)) ma EchooaEx (h(ss (s) a) 2 E(hSajEx (ss (s, Emnaaeex (s, a a)d; (s)
max E(haaaee E(hsasEx (n(s,
Elhaajex de Ev Evesth(s, (s, ()) 1
> E(haaa)xx
(s)
AC
where (+) is since Eg di the CR, and for small C, we get a similar CR as in the disguised contextual bandit problem.
= di. (s). Thus, dense rewards remove the horizon dependence in
Ergodic MDPs. One way to make the navigation task easier is to limit the control of the agent on the state. (AI-Marjani et al. 2023), the authors suggest looking at MDPs whose transition kernels are near-uniform. Formally, for 0 < B < a < 1, they defined the family of transitions

---

1 1 8 S -
Pa. 9 E R.F Σ9 = 1, max q: S 5a-1 min qi 2
and assumed that Pa(-Is, a) E Pa.. for all h 8, a. As a goes to zero, the transition distribution becomes uniform, while at the limit of a, 3 + 1, this becomes the set of all possible transition kernels. Under this assumption, they prove that the coverability coefficient is bounded by SHAH (see
the end of the proof of Lemma 38 of Al-Marjani et al. 2023). which implies that CR" (P) z S"AH
In particular, if for all h 8, a, (s E
1 C/8 then CR (P) CAH independent of
the size of the state- space. Finally, in their proof. Al-Marjani et al. 2023 show that (-) Pa.. for all policies and timesteps. Substituting to Equation (5) (and using the uniform policy for TT) directly
leads to CR 2
1-8 As potentially improving the worst-case environment when S < H.
Grid MDPs We end this section by analyzing a navigation example, where an agent navigates from one corner of an n x n grid to the opposite corner (" ("Navigating in Manhattan". see Figure ((b) Due to space limits, we briefly describe the results while fully proving them in Appendix C.2 This example directly generalizes the chain example with added navigation difficulty; by enforcing zero rewards for all states above the bottom row, we effectively get chain MDP of horizon n. As a
direct result, we immediately get that CR (P) = O( 1t and CR (P) = O H.). Surprisingly, this bound tight - adding one additional dimension to the problem is just as difficult as a chain. Like chains, some of the difficulty comes from sparsity in the reward, but even when all rewards have unit expectations, we show that CP)(P) = +(z). This implies that the problem has additional hardness due to the need for navigation, which is the same order of magnitude as the one due sparse reward. As a final remark, we show that the ratio between one-step lookahead and full lookahead in grid MDPs is at most O ). This might be innuter-nttuiiive at first, as the worst-case CR versus different;
either of them is 0( H In fact, this is possible since the worst-case environments when competing with one-step lookahead agent, the hardness comes from reward sparsity, while versus full lookahead, it is also due to navigation issues. The one-step lookahead agent cannot use its information to navigate, so it has the same CR of 1/H as the no-lookahead.
Conclusions and Future Work
We studied the value of future reward lookahead information in tabular reinforcement learning through the lens of competitive analysis. We characterized the CR for the worst-case distributions, reward expectations and transition kernels for the full range of possible lookahead. We also showed the connection between the resulting CR and concentrability coefficients from the literature of offline and reward-free RL. We find the appearance of the same coefficients in seemingly completely different RL problems intriguing and warrants further study.
While we took the first step in analyzing competitiveness in RL, various other competitive measures could be studied. One natural alternative would be to study transition lookahead, where agents observe future transition realizations. We believe that the results would greatly differ from ours; indeed, even with one-step lookahead, the CR can be exponentially small (as we prove in Appendix C.3 Another relevant competitivity measure is to compare an agent with predictions of the future rewards to agents with exact lookahead information. This models the realistic scenario where agents get approximate information on future rewards and want to utilize it to improve performance. Also, as in the prophet problem, one could analyze the CR between multi-step lookahead to full lookahead agents.
Finally, we focus on the CR for the worst-case distribution, which allows us to derive the exact value of lookahead agents. However, planning with lookahead for general reward distribution can be challenging. For full lookahead, one can perform standard planning using reward realization, making planning tractable. With one-step lookahead, it is possible write Bellman equations for the value, but each calculation depends on the full distribution of the reward, making it hard to calculate. For multi-step lookahead, there is no clear way to perform planning without incorporating the future rewards into the state, rendering the planning exponential. While exact planning might be intractable, could be possible to devise methods for approximate planning. Lastly, it is of great interest to can efficiently leverage lookahead information, that is, achieve the lookahead value: our results indicate that it is significantly higher than the no-lookahead value, so aiming for it could dramatically boost the performance. We also leave this direction for future work.
design practical algorithms that
10

---

Acknowledgments
We thank Simon Mauras and Jose Correa for the helpful discussions. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sktrrowska-Curie grant agreement No 101034255. Dorian Baudry thanks the support of ANR-19-CHIA-02 SCAL.
Vianney Perchet's s research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23- SANR-23-PELA-0000 and through the grant was also funded by the European Union (ERC, Ocean, 10107 1601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
DOOM WARR23--E23-002
References
Aymen Al-Marjani, Andrea Tirinzoni, and Emilie Kaufmann. Active coverage for pac reinforcement learning. Proceedings of Thirty Sixth Conference on Learning Theory, volume 195, pages 5044-5109. PMLR, 2023.
Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR,
2017.
Eduardo F Camacho, Carlos Bordons, Eduardo F Camacho, and Carlos Bordons. Model predictive control. Springer, 2007.
José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for random stream of customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 169-186, 2017.
José Correa, Paul Dütting, Felix Fischer, and Kevin Schewior. Prophet inequalities for iid random variables from unknown distribution. In Proceedings of the 2019 ACM Conference Economics and Computation, pages 3-17, 2019a.
Jose Correa, Patricio Foncea, Ruben Hocksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet incqualities. ACM SIGecom Exchanges, 17(1):61-7,, 2019b.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. International Conference on Machine Learning, pages 1500-1516, 2019.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. How to combine tree-search methods in reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3494-3501, 2019a.
Yonathan Efroni. Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In Advances in Neural Information Processing Systems, pages 12224-12238 2019b.
Yonathan Efroni, Mohammad Ghavamzadeh, and Shie Mannor. Online planning with lookahead policies. Advances in Neural Information Processing Systems, 11140024-4033. 2020.

---

Vikas Garg, TS Jayram, and Balakrishnan Narayanaswamy. Online optimization with dynamic temporal uncertainty: Incorporating short term predictions for renewable integration in intelligent energy systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 1291-1297, 2013.
Theodore P Hill and Robert P Kertz. Ratio comparisons of supremum and stop rule expectations. Zeitschrift für Wahnscheinlichkeitsttenn und Verwandte Gebiete, 56:283-283, 1981.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(AA1)) 2010.
Jianhao Jia, Hao Li, Kai Liu, Ziqi Liu, Jun Zhou, Nikolai Gravin, and Zhihao Gavin Tang. Online resource allocation in markov chains. In Proceedings of the ACM Web Conference 2023, pages 3498 3500-3577222000 2023.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Yingying Li, Xin Chen, and Na Li. Online optimal control with linear dynamics and predictions: Algorithms and regret analysis. Advances in Neural Information Processing Systems, 32, 2019.
Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation- based regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 34:5174-5185, 2021.
Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Gounded-regred mpe via per- turbation analysis: Prediction error, constraints, and nonlinearity. Advances in Neural Information Processing Systems, 35:36174-36187, 2022.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference machine learning, pages 1312-1320. PMLR, 2015.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, pages 1153-1162, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar, Garrett Thomas, Tianhao Zhang, Sergey Levine, and Pieter Abbeel. Learning from the hindsight plan- episodic mpe improvement. In 2017 IEEE International Conference on Roboties and Automation (ICRA), pages 336-343. IEEE, 2017.
Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforcement learning for deterministic mdps. Advances in Neural Information Processing Systems, 35:8785- 8798, 2022.
Tengyang Xie, Dylan Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. In The Eleventh International Conference on Learning Representations, 2022.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online Iqr control with predictions. In 202/ American Control Conference (ACC), pages 697-703. IEEE, 2021a.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR, 2021b.
12

---

A Proofs for Full Lookahead Agents
Theorem (CR versus Full Lookahead Agents).
La (s.a))s)))
Worst-case distributions: CR (P,r) max Lmaajexx (e)rra(s,a)
Worst-case reward expectations: For non-stationary reward expectations,
(8,a)
CR = max min aEIl- (h,,,a)EX (s)
the reward expectations are stationary (r)(8, a)), then
Σ dh (8.0)
CP) = max xETl (x,))
min
Σ (8)
Worst-case environments: For all environments, CR 2 max 1
SAH 7 J. Also, any 8 E (0,1)
there exist stationary environments with rewards over [0, 1] s.t. if = forr E {0..... H 1},
145 then CR (P,r) Σ (H-1og,(8- (0)_2((5))-AA11(8---111 and S 2 A 1, then CR" (P, S 146
A
Proof. Worst-case distribution: We already saw in Equation
3 that for all reward distributions
H (P,r)s
Σ
(1()))((s.a).
(h,8,))EX
We now show that for any O, there exists distribution such that
(P,r) 2 (1 - 5) Σ (s)))
(haaaeex
This would imply that
(Prr
Σ (H(s)r((sa)
sup RdrD(())
(h.
and conclude this part of the proof (by Remark and Equation 2
Let E (0, 1) and assume long-shot reward distribution R~ LS.(r). For any (h, 8, E X, define the event that a positive reward was realized just in (h, a,a):
= =
Rn (s, = rn(s,a) v(h' s', d') # (h) (s =0)= 0).
Gh.s.
Under any of these events, the value of the optimal full lookahead agent is
Th [h(s,
ra(ss a) di
max TEILM
Σ
d,,(5',a')Runu (s ,a ad))
E
max di a) IElI
Ghaaa
Now, notice that each of these mutually exclusive events G occur w.p. e(1 - c) SAN-1 and that the value is non-negative when none of them occur. Hence, for this reward distribution,
(Prr()
Σ
Pr(GGaa,jIB
Σ
(i a') (s ",,'')) Gr,s,a
max REIM (f)
(h,,,))xx
E(1 - e) SAH-1 SAHHH))HHHSHS.. (1, (s)(s)
Σ
(H,,,a)Ex
(1 SAH-1
Σ
())))r(ssaa)
(6)
(K,8,a)EX
13

---

Setting proof.
sau-1
8 leads the desired bound and concludes this part of the SAH
Worst-case reward expectations: Before proving the results, remark the choice to limit reward expectations to [0, 1]. The main motivation for doing so is the ubiquity of this boundedness assumption in the literature of RL, but in fact, it is only matter of convention and has real impact. Indeed, since CR is invariant to scaling, the same result would directly hold for any bounded interval [0, C). Furthermore, explained in Remark B the result would also hold under the less restrictive assumptions that reward expectations are just non non-negative.
We proof both results using Lemma 1 As first step, we highlight that the only dependence of the optimization problem in the Markovian policy æ through the occupancy measure di. Therefore, denoting the set of all occupancy measures induced by Markovian policy with transition kernel P by D = (MM()))) the problem can be reformulated as
CR (P) = inf
CR (P,r)
rxE00,1aa
E(n,aa) (s, (s)
max r, FETI
inf
Σ E(h,,,)ex (s)r)((ss)))
E(haaeex da (s, (ss,a))
max r. (P)
inf
(7)
E(haajex (s)r
The set of the possible occupancy measures is convex and compact in R Allman 2021 so we apply Lemmal [ with 0h1 di(ss, (s), Vh,s,a = dr (s. a) and 2h,5.a ra (s. a), resulting with
ds
max min (7 a) WElM (h,,,)) (s)
CR
max JEDM(P) (b,E,
min
(s)
where again used the equivalence between optimizing over Markovian policies and their occupancy measures.
For stationary rewards, where (s a) r(s, a) for all (h, X, we rewrite Equation 7
E(e,)esxx E/H dn(s, r(s,a) Σ E(saEESXA E di (8) (s)))))))s)) r(s,a)
CR#(P)- inf rxE[0,1]8a dEDM(P)
max
Now, another application of Lemma r(s, yields
with ag,a
= Em (s), Vo.a = Elin dn a) and 2,,a =
ΣM du (8, Σ 07 (8)
Σ di (s, Σ (8)
CR" (P)=
max dED (x.4)
min
max *EIT (s,a)eSxx
min
which is the desired result for stationary environments.
14

---

Worst-case environment lower bound: We now derive the lower bound CR" max 3 )- We prove it for nonstationary enviromments, so particular, it also holds for stationary ones.
Recall that by definition, for any (h, a) X, d, (8,a) a) is the occupancy measure of Markovian policy that maximizes the visitation probability in (h, 8, a), and let sa,s, be a Markovian policy that achieves this occupancy. Since the set of occupancy measures induced by Markovian policies is convex [Altman 2021]. J. there exists Markovian policy Tu III such that its occupancy measure the average of all these occupancies, namely, for all (h, 8, a) X.
d (s.
1
E
do (s.
SAH (K'
Using the previous part of the theorem, for all environments P, it holds that
CR max min (s, HEll (N.A))E (s)(s)
(s,
min (KSa)EX
d7
SAH Enn a') dn
Fisiiaa ()
min (h.s.a)EX
(s)s
SAH dh
1 Thine (s,a)
min (baaa))X
(3)
(8,
min
SAH (N,,,))XX (s)
SAH
In (*), discard all the (non- inon-negative) terms in the summation where (h', 5','''aa) * (h, s, s,a), while in the following equalities, we use the definition of T and the fact that d (8, a) = (s). As this inequality holds for all environments, it also implies that CR 3AH
To prove that CRH 2 1
A we take different approach and go back to the Bellman equations. Denote by 17. (>] Rt), the optimal value of a full lookahead policy, starting from timestep h E [H] and state s E S, and given reward realization R. Therefore, the value of the full lookahead agent is given by Hr ER. [V] (s)).. Similarly, denote the standard value with lookahead information starting from timestep h E [H] and state E S by V.O, (s). As previously explained, given reward realizations, the optimal full lookahead policy is Markovian, both values can be calculated using the following Bellman equations for all and [H]:
(>( = max aEA
an + Σ
(*++()|R) =
s'ES
(s) (s) max aEA
Th (7( + Σ
Ph(s'ls, ( (17
#1 (s) = 0.
S'S
We prove by backward induction that for all h [H+1] and E S, [ < A Specifically, using this relation for h = 1 and taking the expectation over the initial state distribution would imply that y H.* < A y0,* regardless of the environment, and thus CR# > π
15

---

As the base of the induction, see that the claim trivially holds for h = H + 1, where all values are 0. Next, for any h E [H] and s S, given that the claim holds for all states in step h + 1, we have
(s)
E
max aEA
(s +
Σ S'ES
Pa(s'1s, a) (
S
Rn(8, +
Σ
Pa(s' 18, a (x+11
AEEA
e'ES
Σ
rn(8,a) + Σ
Pa( 18 (iii
9EA
s'ES
(n( + AH
Σ
a) (s')
s'ES
S 4
rn(s,a) + Pa(s'lss, Pa(6))s,aaVVii1(6
REA
F'ES
< H| h A max aed
an(s,a)+ +
Σ e'ES
- (s).
where throughout the derivation, negative and (*) is due to the induction hypothesis. This concludes the proof of the lower bound in the statement, namely, that for all dynamics and rewards, holds that CR 2 max 3AH }
the fact that all rewards (and thus the values) are non-
Worst-case environment- upper bound: see Proposition] I environment for which the aforementioned bounds near-tight.
where we present a tree-like stationary
16

---

B Proofs for Multi-Step Lookahead Agents
Proposition 2. For any L E [H], let (h)) max(h L 1,1.
Then, it holds that
sup Rdr
(L,) = max
E
rh(s,a) a)
Σ Li (d) = s') s'ES
TEIL
(h,,,))E
Proof. We start by lower-bounding the optimal value in the presence of long-shot rewards. Then, prove a matching upper value for all rewards and L-step lookahead policies.
Lower bound on the value of long-shots. Let > 0 and assume that R ~ LS. namely, that for any (h, 8, a) E X, a reward of rn (s, a)/E is generated with probability e; otherwise, the reward would be zero. Let
II be any Markovian policy that does not observe future rewards and let E II be a policy that plays π if all the L-step future rewards are zero and otherwise optimally navigates one strictly positive reward (ties broken arbitrarily). In particular, if only one long-shop reward is realized at (h, 8, a), this policy would play æ until timestep 4, (h) max - L + 1, 1} and then maximize the reaching probability from (h) to 84. If the agent successfully reaches 8/ = 8, it will play ag a and collect the reward.
The value of स can be lower-bounde bounded by the value that at most one long-shot is realized; Denoting
Ral(saa= [n(3,a) a) V(N, d') + (h, 8,a) (8, a) = 0)
Ghasa
the event that a reward was realized only in (h, s, a) E X. we bound
V L (P,r) 2 4 (P,r)
H
E
Ri (sw, )=
Σ
E
Ru. (w),, Craaa Pr Pr(Gnas.a
(h,,,a)ex
Li==1
Σ
E
115h~ s,an =aflā, Gh,saa Pr(Gr.oat
(b,8,))xX
Σ
Σ
(r( = = max x'Ell.
Prfsn = s,,0 = =alsen(0) = ,' T a)
) Pr (G
(h,a,))XX d'ES
= 8)) TT((,00 a) Pr(Gneeat
Σ
Σ
(h, JES
(l (5)d 50) ra(s,a) =((1 SAAH-
Σ
Σ
(h,s,a)EX SEES
e SAH
Σ
(n(
(s (s = 5¹).
(h,s,aexx
F'ES
In (1), we use the facts that the events GR,sa are disjoint and the rewards are non-negative. Next, in (2), we decompose steps until &y (h), where we play n, and steps from (h) to h. where we try to maximize reaching probability to (s, a) at timestep h. Notice that the reward is independent of the transition, the optimal reaching policy is Markovian. Relation (3) replaces the probability notation to conditional occupancy measure and (4) substitutes the probability of the events. Maximizing over and taking the limit of small we get lower bound of
sup VL. 2 <>0 FEIL
sup max e -SAH
Σ (n(s,a) a)
(d) = s¹)
R R(rD((r)
(h.s,a)xx
.EES
max TELLM
Σ
(s(s,a)
Σ
th
5').
(K,
s'eS
17

---

Upper bound on the value of all reward distributions. For any fixed lookahead policy π E II and any reward distribution, we bound
H
V S (P,r) =
Rs (sh, am)/=
E R (s, fss = a, = =
(N,S,))
Σ
= (1 s,00 = ; s5)
(Mea)EX'sES
E
Σ
= s,a, = S12(1) s', (T (12 = =
(h.a,)eX SEES
Σ
Σ
(k)
E
Rs( max
Pr(sh, an =a/T"" (h) s', Rs, (1) =s m-lll
(h.s,a)EX s'ES
Σ
Σ
di (s) s (T) = 88
(K, s'ES
Σ
Σ
(h.sa)EX e'ES
Σ
Σ
max
(hsa)EX d'ES
(3)
Σ (B,5,))XX S'ES
(d" = 8))n(8,a)
max MM
Relation (1) holds since the state dynamics are independent of the rewards realization and the maximal reaching probability is (s(stt,, s'). Relation (2) holds because reach the state at timestep ty (h) just before sceing (s, a); therefore, the two variables independent. Finally, relation (3) holds since we can rewrite the value as
H
max ΣΣ
(6))
1ftz(h) = i)d = s')rnss,a). (h,,,a)EX
Σ
L ESVES
This expression equivalent to the optimal value of no-lookahead agent whose expected re- ward at any (i, (a)) E X is (h.s,a)x (lr.()) (s)d (s)) s')rr(> a), so there exists Markovian policy that maximizes this value.
18

---

Theorem 5. [CR versus Multi-Stae Step Lookahead Agents] For any L [H]. let th(h)
max(h ++ 1,13. Then, it holds that
max, FIM Ei, ease (a(
Worst-case distributions: (Rr)(
max D(hAaEE Ph (h(s,a) Ene i2 (6)0))))))))),,0000
Worst-case reward expectations:
(H a) TElL- (h,s,))XX Es'es d
CR)(P)= min max
min
(s') =0)
the reward expectations are stationary (8, r(s,a),, then
Ex=1 d7 (8)
CRL(P)= min max 5" xETI- (x
min
Σ Eves (T, (8' (8)) (8))))(())) 8')
Worst-case environments: For all environments, CR 2 max SAH [H-L+ Also, for any
8 (0,1) there exist stationary environments with rewards over [0, 1] s.t. if A for E {0, {o,..., 1}. then CR-((,,) S 1I- and if S 2 A 1, then
145
(R,((P)) < (1(
148
Proof. Worst-case distribution: This part of the theorem is directly corollary of Proposition 2 applied with Remark 2 and Equation (2). We remark that we assume w.L.o.g. that rh (s, a) > 0 for at least one reachable (h, 8, a) E X (i.e., di, (5, a) > 0). Otherwise, both values in the numerator and denominator equal zero and the ratio defined as +0x.
Worst-case reward expectations: As in the proof of Theorem we start by rewriting the maximiza- tion problems in the competitive ratio using, (P) the of occupancy measures induced by the transition kernel P and all Markovian policies:
CR
inf CR.((Pr)
T
max E(haa)Ex a)d
inf 1) max E E(haaaex Th(ss, a) Eves of (s') (s))d =
E(h.s,)ex Pn a ()
max rxE(0,1]84 SA x Ell xEll Σ (lb,,,)ex Th a) Eves (2(M)) (8' d (12) = x")
inf
min
E(haa)exx Tn (s, add
max TxE(0,1) 8A d'EDM (MDDMP))E (P) E E( (s E (1)) (5')d7, (s) = 8¹)
inf min
EiheaeEx Tn a)dss.)dd(c) (s,
inf inf d'EDM(PjnNejojj..M dEDM(P) (P) E(hoaaex (h(s, Eves d' (1) (d 81z =
(8)
Continuing following the proof of Theorem
the convexity and compactness of the set of occupancy measures to apply Lemma T on the two internal problems, this time with as.s.a = Eves (m) (s')d,, (s)))2(1) s'). Doing so results with
di (s. a)
CR-(P)=
inf max min
(EDM(() (P) (h.8,))X Eves d' ( (n)(( (8) = s')
At this point, we deviate from the previous proof and analyze the external optimization problem. In particular, we want to show that the minimum is obtained in the set of Markovian policies. We prove using Lemma 2 For its application, notice that DM (P) a convex and compact polytope, and therefore so does its linear transformation P Evrss d' (k)) (s')d) (s(st =')ld so the conditions of the lemma hold: the infimum is obtained minimizer in the set. Substituting
ld E (P))) }
19

---

back into (P) and using the equivalence between occupancy measures and policies leads to the desired result:
(n(
(P) min (PDMMP))EDDC (b.x;a)EX EE of (1)))s')) (s') = =
max
min
(Lemma
(),
min
max
min
x'ElIM FETM (k.,,))eX Eves in (1) (s')d (s (s)st =
For stationary rewards, where (n a) = r(s, a), we rewrite Equation
8
as
(i du(s, ())
((ss,))))(,))) r(s,a)
CRL(P)= inf inf (PD de DM (P) E( EE Eves Ie (8')d (5) = =0)))((ss)) r(s, a)
max
We can now reapply Lemma with the appropriate Os,a = Em Eves (n (8)) = 8'),
followed by applying Lemma 2 to get
Σ ds(
(R)(P)= inf
(PDM((P (EDM(P) (P) (a.a)ESxA A Eh=1 Exes d' (n (sn)s (8)8)2(h) = (Lemma
max
min
E (3,
min
min
(Lemma)
x'Ell HEll (xx
E Eves di (m) (f) = =s)
Worst-case environment lower bound: First notice that by definition, any L-step lookahead policy is also full lookahead policy. In particular, for all environments, (P,'((,r)) S (.,.((,)r, r), and the reverse relation would hold for the CR. Thus, from Theorem L CRL 2 CR 2 SAH- We further proof that CR 2 (H-L+1)Ar using reduction to the full lookahead case.
we directly get the lower bound
To this end, we start by decomposing the no-lookahead value of any II as follows
v0i (P,r)
Σ
(nss,a)(((ssa)
Σ
rn(s,
a) Pr(sn = 0, =a
(haaaee
Σ un(s,u)
Σ
Pr( = ) Prf0n = a, als0, = 8'}
(haa)ex
e'ES
Σ an(s,a)
Σ
di (s)
(h,a,)eX
e'ES
Σ
(5')
Σ
(1ss,a)d,(ssalss =s)
S'ES
hm (3.a)eSXA
H-L+1
Σ
(s')
Σ
T=L-1(s.0)d =s).
SES
(sa))SXA
In the last inequality, we decompose the summation into two terms depending on whether to (h) 2
i (h) > For brevity, let {r*) [=1
H-L+1 be such that for all (h, 8, a) E X,
(s) rx a) (h e [Z]], a) = rx a) 1/h -- 1}, (2. H L-
Using this notation, one could rewrite the value as
H-L+1
(P.r
Σ
Σ
Σ
(9)
#=1
EEE
(x.a)ESxA
20

---

Notice that r are the expected rewards of timesteps observed by the lookahead agent at step i. We now define the following set of policies
A Markovian policy that maximizes the I-lookahead value is denoted by
π E arg max TEIIM
Σ (N,8,))EX
(8, a)
Σ S'ES
( (1/ (o)0)) = 8').
For any i - 1], let n. be Markovian policy that plays until reaching some state and then continues by policy that maximizes the reward function r" for the following L timesteps:
Σ Σ (s.,
Ti arg max
FEIL
(s,))ESXA
For 1, the state $1 would be the initial state, generated from the initial state distribution. Notice that starting for the 7th timestep, is an optimal policy given rewards r' in the standard MDP model, so there exists an optimal Markovian policy that maximizes its value simultaneously for all s; E S. By ignoring all but the ith term in Equation (9) one could clearly see that
*+-1
5d,z 2
Σ
df
(s')
Σ
Σ
(s, =s)
s'ES
(s,0)ESxA
h=
i+-1
Σ S'ES
Σ (sa)ESxA
Σ
max FEIL
A=
All aforementioned policies are Markovian, so by the convexity of the occupancies induced
by Markovian policies
Allman 2021 there exists Tu. E II-M such that for all (h, s, a) E X,
L+11
(s, a)
Σ
(s.
H L+1
Since values are linear in the occupancy measure, we can bound the optimal no-lookahead value by
0 (Prr) 2 V0.u (P,r)
H
L+1
Σ
vo,
H L+11
H L+1
44-11
Σ
Σ
(8)
max TEIL
Σ
Σ A=r
(l =')- (10)
H-L+1
EES
(a.))ESAA
Moving forwards, we use a similar decomposition to the L-lookahead value using Proposition 2
VL. s max #ElTA
Σ ra(s,a)
s')
(h.s,a)ex
s'ES
Σ
an(s,a) Σ
(s)d =')
s'ES
Σ di
Σ
(s)3) =
FES
hm (8,0)ESXA
#-L+1
141 =s)
S'ES
(8.0)SXAA
#-L+1
i+-11
Σ
Σ
(6)
Σ
Σ
(11)
E'
(s.0)ESXA
h=d
21

---

To conclude the reduction, recall the inequality Σ a. min; { which holds for all values 0,99
of 2iz, Ui, 04 2 0 s.t. Σ, 04 0, due the quasiconcavity of the ratio of linear functions (given the convention that x/ +00). Applying this on the CR with the coefficients 0i,s' di (s') and using Equations (TO) and we get for all environments that
(P,r)
(R,) = (P,r.
max E(So)eSXA Eith (1 (( = 80)
1
min -++1,
H L+
E(SnjeSXA Ehsi (s(s) =
x'ES
1
[H - + 1
The last inequality is the reduction to the full lookahead: each of the terms is exactly the CR versus full lookahead agent with horizon L and reward expectations r' (see Theorem | part 1). Thus, each of the terms is lower-bounded by the bound for the worst-case environment given horizon L (see Theorem part 3) by _.C
Worst-case environment upper bound: as in Theorem 3 this part of the proof is covered in
Proposition I
where present tree-like stationary environment with the stated behavior. -
22

---

C Analyzing the Competitive Ratio of Specific Environments
C.1 Upper-Rounde for Reward Lookahead Delayed Trees
a1
Ra(s,)) ~ LSAe
:
01
aA
()
Ra(s,a)
Va
~ LSSe
0.4
(xf,,)
a2
Vl
0.A
da.
va(e,0) =0
Tuls,a)
01
Va
(x5,4) -0
:
Ra(s,)
~ LSAe
Va
a
Ra(s,) ~ LSS.
a.A
Figure 2: A near-worst-case environment: tree-like MDP. An agent can decide to stay at the root of the tree, but once it starts traverse the tree, it must navigate to of its leaves, from which moves to non-rewarding terminal state. All leaves have ono-shot rewards, while all other nodes yield no reward.
Proposition 1. For any L E [H] and any 8 E (0, 1), there exist stationary environments with rewards 1+5
over [0, 1] s.t. if = A + 1 for n E LO -- then CR S (5-1)
and
S 2 A + 1, then CR² < [H [H-L+1)(A Moreover, if L = H and S 2 A 1, there exists
146
an environment s.l. CR 7
Proof. Assume that = A + for some n E N. We divide the proof into different cases, depending on the values of and L.
Case 1: [H] and L- 1). To prove this bound, we design tree MDP with an additional option to decide when to traverse it, as illustrated in Figure In particular, assume that the fixed initial state 81 the root of a tree depth n + such that the root has descendants and all other nodes have A descendants. Thus, the number of nodes in this tree is
A"
1 1 (A - Σ 1-1 (A 1)
A",
1=1
and the number of leaves is (A - 1)4"-1 Assuming that after traversing the tree, the environment moves terminal state 87, this environment could indeed be represented using A" + states. We denote the dynamics of this tree by P.
23

---

For the dynamics, we allocate one action in the root of the tree that keeps the agent at the root, while the rest of the actions allow traversing through the tree. At the leaves, all actions transition a terminal state sy. We emphasize that once an agent has decided to start traversing the tree, it has to continue all the way until the leaves (and terminal state), so the decision when to traverse the tree is taken at its root. Finally, the reward of any action at any leaf ís a long-shot LS, namely Bernoulli- distributed with probability e. In particular, this distribution is bounded in [0, 1].
In this example, any agent with no lookahead information will perform at most one action at a single leaf, independently of the reward realization, thus collecting in expectation no more than the expected reward of a single leaf V - [[) =
On the other hand, an L-lookahead agent could start traversing the tree only when reward will be realized upon its arrival to the leaf. To reach a leaf at timestep h, the agent has to start traversing the tree at timestep h Thus, this agent will wait at the root see whether reward is realized in any leaf at timesteps (n + 1,..., H). and only if so, will traverse it.
Since there are (A 1)A4"1 leaves with A actions each, the probability that no reward is realized in any leaf at these timesteps is (1 1--e] -) -)( (M (A-1))a-) and the optimal lookahead agent would
collect an expected reward of at least
h M 1 - (1 - () (H-)
2 HH n)) (A 1)A"c ((H nn) (A (A-1)
where the last inequality is since (1 - z)" 1 - nx + n² Combining both inequalities, for this environment we have that
V0,,
(R,) VL.
6
$
(H - n) (A- 1) ((H n) (A (A-))))))
(H - nn) (A - A) - ((H - n) (A 3
In particular, for any 8 > 0, we could fix small enough such that
1+8 CR²(P,T) (H (S (A - (((55))
where we used the relation S= = 4
Case 2: T. E [H] and 0. This is the case of S = 2. We separate it for the clarity of presentation, but the example remains the same: the first state 81 the initial state and the second 82 8T is a terminal non-rewarding state. When in $1, single action does not change the state but yields no reward, while all other A - actions transition the environment to state 82, giving a long-shot reward (e). As in the first case, without any lookahead information, the agent could collect reward at most once and obtain in expectation at most Vu,* < BILS. = E.
On the other hand, any lookahead agent would move from 81 to 82 only when reward is realized. Since there are A - rewarding actions and H opportunities collect rewards, lookahead agent could collect at least
VL yL*21-0 11211111-0 21- m(A-)) 2 ((A - 1)e - (A-1AA 1)262
where the last inequality is again due to the inequality (1 x)" 1 n1 + n²x22 Combining both bounds, we now get
V0,-
CR CRr(PP,)= VL S
H(A - 1)e - H2(A - 11222
- H2 -
Thus, for any 8 > 0, there exist small enough such that
1 8
CRT <
H(A-1)
24

---

Modification when S E [A + 2, 1= In this case, we cannot build a complete tree of depth log (S 1) + 1. Instead, we start from the complete tree of depth [log (S- 1)] and use Case 3: L [] - and S +1. We use the same example as in the first case and = --1 1,
ignoring all extra states. Direct substitution that bound results with
1+8 (Rr) (H-L+1) (A 1)
Case 4: Finally, if H and A -11, 1, we discard the loop the root and just build a full tree of depth H. leading to A leaves (with A actions each). From the root, the full lookahead agent reach any leaf with realized reward, which exists with probability 1 (1 -) Following 1+6 for any 8 > 0, concluding the proof. A
the exact same analysis would now yield CR" (P.r) -
any extra states to create additional leaves of depth [log, (S 1)] 1. The number of leaves for S = A + 1 was No (A 1)A==1 Therefore, 8-No of these leaves will have A descendants in the new tree, increasing the number of leaves by A each, while one additional 'old' leaf will take the rest of the states. For this reason, the total number of leaves N would be
S
No
S--NN Nu A 5 No
1
N 2 No + (A 1)
+
A
A
S No
-
A
2 8 1
A) - 2.
Recalling that in each leaf, we have A possible actions, so rewards could be realized in NA locations, and increasing the depth by (so that the lookahead agent has one less attempt), we can follow the exact same analysis and get more general bound of
1 6
1+8 (H log (S- 1)) AS
(P.) S
θ
H [log (S - 1)1) (S(A- - 2A)
for any A+2 S S S A +1
C.2 Analysis of Grid MDPs
In the grid MDP, an agent starts at the bottom-left corner of an x grid and can either move up or right until getting to the top-right corner ('Manhattan navigation', see Figure [(b].. After taking one last action, the interaction ends. We denote the states the ith column (starting from the left) by $1,11..., 8i, (with 81,1 as the bottom state) and the states on the jth row (starting from the bottom) by $1.j....: Sn.j (with $1,j the leftmost state). At the top edge of the grid, the agent must move right, and the right edge, it must move up. The size of the state space is S n², the action space is of size (at most)
and the horizon is = 2n
This MDP generalizes the chain MDP with AA = 2, analyzed in Section 5 indeed, by setting the reward be non-zero only when going up from the bottom row (s1.)). we effectively get chain of length and corresponding CR of CR CR To T In particular, the reduction immediately leads to an upper bound of ((+) for CR (and CR ), where the bound for one-step is almost worst-case, since CR' > 1 also versus full lookahead for the grid-MDP, as we now prove.
AH. 2ff Interestingly, this is a near- sear-woost-case reward placement
1
One way to prove this to analyze a flow on the grid graph, which is equivalent to occupancy in deterministic MDPs. The value of the full lookahead agent corresponds with the maximal possible flow through any edge in the graph, which is the unit flow (d) ($t.)) = 1). Hence, the goal of the no-lookahead agent
make sure that there is a minimal flow in all the edges of the graph, and this minimum would be the CR. This could be achieved by distributing a flow on the bottom and leftmost states and sending in straight lines the other side of the grid, as explained in Figure 3 The resulting flow ensures a minimal flow of 2(n-1) through all the edges. Even more, looking at the 1
flow description, could explicitly write the stochastic policy that achieves this flow by looking
25

---

$1,m
$2,
Sn, n.
1[m-1)
2(n-1)
2(m-1)
2[=11)
1(-11)
2(n-1)
2/n-13
2(n-1)
1
21
2(m-1)
$1,2
$2,2
5n,2
2[m-13
2(m-1)
2[ 1)
2
2(n 1)
$1,1
22
1n,
21-2
2
Figure 3: Illustration possible flow on grid graph, starting from the bottom- corner and ending at the top-right corner. The first step is distribute the flow the bottom and leftmost states, such that there is excess flow of 2(n-1) flow in each of these states (green). At the leftmost state, this excess flow is sent at a direct line towards the right (blue), while in the bottom row, this flow is sent up (red). Such flow ensures that all edges have a minimal flow of 2(n-1)
the ratio of the flow in each direction:
= j =
(start) (bottom) (leftmost)
1,j E ( n 1}
j == 1, E (2...., 1}
x (Mooe-Right(s; st.5)
2
1,j (2,..., 1}
(middle)
1
i= =n,j E (2...., 71 1}
(top)
0
== n, .2...,77 1} (rightmost))
! i i=j=n
(end)
For this policy, it is easy prove that the minimal occupancy d[+j-1 a) is lower-bounde by マリー by directly verifying on edges the grid (starting from the bottom and left edges and then
continuing to the top and right ones), and then proving with simple induction that strictly inside the grid, di ((t)-1(sin))
- This implies that
d)
1
1
CR" (P) = max min M (K.
max min MELL (I.))
& (+))-1885; 2(n
d7 (8)
In particular, for the grid MDP, the worst-case CR for full lookahead is at most worse by factor of 2 compared the CR versus one-step lookahead, similar to the chain MDP. However, contrast to chains, where the prophet inequality ensures a constant ratio between one-step and full lookahead, in grids, this ratio could depend on H. For example, assume long-shot rewards R LS.(1) for
arbitrarily small e. As we already calculated the value for long-shot rewards, know that one-step lookahead agents effectively collect all expected rewards along their trajectory (Equation (4) at
most 2H rewards while the full lookahead agents collect all reachable rewards (Equation (6)
total of ? (H²) rewards. At first glance, it might be seen as a contradiction, following a logic that no-lookahead full lookahead one-step lookahead
no-lookahead
one-step lookahead,
full lookahead
26

---

but the careful reader would notice that the CRs are derived for very different reward expectations; one CR calculated for sparse chain-like rewards while the other is calculated for dense rewards where all expectations are equal.
Dense rewards. We end this example by analyzing the CR when rewards dense -all all rewards are of unit expectation. Since all reward expectations are equal to 1, regardless of the policy, the value of all no-lookahead agents would trivially be !!. For the value of L-lookahead agents use and rewrite the value by decomposing to different values of & (h) as follows:
Proposition 2
VL (P,1)
Σ
(5 (s1se, = =s)
sup R*)D(()
max TEllM
(h,S,))EX
S'ES
L+1 (5))
Σ (5.))5xAA==1
Σ
(.)+))+ TEll
max
Σ
EGG S'ES
E
di+1-1(5|s;
(s.0)ESXA
Since the environment is deterministie, all occupancies d' are binary: one if state is reachable and zero otherwise. From the initial state, there are L reachable states so the first term is equal to L?. For the second term, we bound the number of reachable states after exactly L steps by L + 1 (all the possible number of "up' moves between and + L). This yields the bound
H-L+1 Σ
sup VL. (P,1) L R=1D(()
Σ [(((((++1)
max FEIl
EES
+ (11 -M=+(HL)(L++)
< H(L+1)
and result with CR of (P,() 2 LTT.
This bound near-tight, again using Proposition 2 For the proof, we focus on a policy æ that iterates between moving up and right. As previously explained, the number of reachable states when looking L steps forward is L + if we could perform all combinations of moving up and right. In particular, this the case as long as we are too close to the top-right border of the grid. By iterating the movements upwards and rightwards, for any h S H 2L, we arrive to a state st, such that max (i. < the border. Therefore, we can bound
A 2n 1-2 <
L, which ensures we are distance of at least 7. from
2
H-21
1
Σ
Σ
((()((+1))
sup R#vD(1)
L + max (HI -2L 1)(L+
= =2(HL)
where the last relation is immediately obtained by looking at either L< H/4 L H/4. Thus, we also have that (P,1) = (()LL), and we can conclude that CR, (1/L))
C.3 Upper-Bound for Transition Lookahead
In this appendix, analyze the competitive ratio versus one-step transition lookahead agents. Formally, at each timestep h and state 8n, such agents observe what the next state 8 would be upon playing any of the actions A. We assume that this is the only information available the agent (namely, the agent has no reward lookahead). We also assume that transitions are generated independently different timesteps and are independent the rewards. Notably, even with one-step information, the CR is exponentially small, as stated in the following proposition:
Proposition 2. For any A 2 2, H 2 5 and S 2 (1 there exists an environment such that the
CR versus one-step transition lookahead agents is CR
2
(A- (A-1)(2 (--
27

---

Proof. The environment we build is complete tree of depth d (to be determined), where each node has A descendants. The agent always starts the root of the tree. At each node, the agent can play A = 1 to stay at the same node, while the rest of the A 1 actions move the agent to one of the descendants of the node uniformly at random. Only one leaf a deterministic unit reward of R = for all actions, while all other leaves yield no reward. After traversing the tree, the agent moves to terminal non-rewarding state ST. The total number of states required to create this environment is
d-1 Σ 2
d-2
1
12
Σ 0
A'
Ad +1 A
and the number of leaves in the tree is N (A - 1)d-1.1.10000 A no-lookahead agent could not do better than randomly traversing the tree and would obtain an expected reward of at most V - 1/N.
On the other hand, one-step transition lookahead agents could choose the following policy: if an action leads in the direction of the rewarding leaf, take it; otherwise, wait in the current node. To obtain the reward, there have to be at least d timesteps where an action leads in the right direction, over the span of
attempts (one additional round required to collect the reward. Letting
Pa =1 11 -
2 1 - 1 be the probability that such an action exists at certain node ('success') ), the value of the one-step lookahead agent would at least the probability that a binomial distribution Bin(n H- p p.) has at least d - successes, Setting d [1 4) 1. so
that d - 1 (1 )H 1) 1, we use Hoeffding's inequality to get
V1* 2 Pr Bin
- H-1,1-
2 d 2d-1)
2 1 exp -2 (22(1-2) H 1) - -(d (d-1))
1
21 e²
Therefore, the competitive ratio is upper-bounded for
CR S 1/ - 1)(A-1)0-1
2 (A - (
We remark that the constraint A > allows building such tree, while H 2 5 ensures a depth of least d 2 2.
28

---

D Auxiliary Lemmas
Lemma 1. Let d and a R4. Also, let D IR be convex compact nonempty set. Then,
inf max y² x == VED a²x RED iEid] Q;
max min y/4
where we define all ratios be +00 if the denominator equals zero.
Proof. We first remark that if 0 for all E [d]. then by the definition of the division by zero, both sides are trivially equal +-c, and the result holds. Thus, from this point onwards, we assume w.l.o.g. that for some in E [d]. it holds that Oii 0.
Step I: We start from analyzing the l.h.s. problem and showing that
y²x inf =ER
inf max x =E RED oFx
maxy V² z. RED
Notice that choosing x; = [ = in} leads to a bounded value of m8XyeD Vig < 0o, so the value is aig finite - there cannot be a solution such that a²x (and the value is +o0), and we can w.l.o.g add the constraint a' x O. We further remark that both the numerator and denominator are always non-negative, so the infimum is bounded from below by O. Given that, the internal problem is always well-defined, and the maximizer is given by V/2 arg maXyeD y²
E We next show that the constraints E [0, 1] aa'xxxx x > 0 can be replaced by the constraints x
# Rd a" x = 1. First, for any x E [0, 1]dh s.t. a²xx a > O, define 2n a E IRd, for which a² 1 and
Y x yED aTx x
max
max 1 VED
max y yED
22 inf max y 2.
=ER yED x=1
Thus, we have the inequality
y" x
yrx max
inf max = DED a x
inf
inf maxy 2.
#e 0. DED a x a Tz>0
=E WED a ==1
On the other hand, for any E Rd s.t. a² = 1, define 02 max,
(which is well defined due to
the constraints). For this choice, we get that I, E [0, 1]dd and a xz particular, one can write at which implies that
aT
0. In
max y T = maxy DED
Ez aF x2
max
JTz= DED af x2
inf max
J
DED
=e[0,11 PED oTx
Therefore, we also have the other inequality
y inf max 2E(0.1] yED aT
inf max yT= ZRR VED T==1
which implies equality
y x
inf max
inf max 2.
zE|0.114 DED a
z WED
a=2=
Step I: Applying the minimax theorem.
The objective is linear in y (and thus convex and concave in the variables, respectively), and the set convex and compaet. The constraint on also convex, though not compact, but this casily fixable; notice that for all i such that a; 0, 21 does not affect the constraint. On the other
29

---

hand, setting > 0 can only increase the objective since yr. 2 2 0. Indeed, for any R4. s.t. a²= 1, letting& ã, 2, 1 {az > 0}. we have o² 2 = and y 2 S y² Hence, w.l.o.g., we can always add the constraint that 2; = 0 for all E [d] with a; = 0. With this additional constraint, the set Z { 14 1, Vi s.t. a, actually a minimum and we can apply the minimax theorem to obtain
2, 0} is convex and compact, so the infimum is
inf *ER VED
max maxy²= = max min siinyy yeb xE2
Step III:
Solving the internal problem for fixed values of y-
At this point, we note that components where d; = 0 do not affect either the value or the solution. Therefore, from this point onwards, assume w.l.o.g that og > 0 for all i; we will then apply our results only on the subset of components with a; > 0. Given that, we also assume w.l.o.g. that yi > 0 for all otherwise, the constraint could be met by letting 2 > 0 for components with ys 0, which would lead to the optimal value of 0 (we verify this case at the end of the proof).
Thus, focus solving the following problem: for any fixed y Rd s.t. yi 0 for all i, solve
min, s.t.
y 2
2 2 0. Vi [d],
a 1===1.
Due to the linearity of both the objective and constraints (in 2). KKT conditions are both necessary and sufficient for the solution of this problem. Letting μ and X be the dual variables for the constraints 2 E IR4 and aT 2 = 1, respectively, the KKT requires that for all i [d].
y1 #i Aay 0
(stationarity)
142 = 0
(complementary slackness)
14 0, 2 0 ====1.
(feasibility 1)
(feasibility 2)
For the stationarity to hold with the non-negativity μ4s, we must have that À S min.e(4] a, More- over, if this is strict inequality, all μ4 are strictly positive, which leads to the infeasible zero-reward vector (due to the complementary slackness). Therefore, we can conclude that À = min a and so 0 only in coordinates where this minimal ratio in achieved. By complementary slackness, zi 0 for the rest of the coordinates.
Substituting in the equality constraint, we get
0:
yize-
Explicitly, (1) is by the constraint and (2) is since z; 0 when the value of the internal problem is
Vi > X. Reorganizing, we get that a,
d
Σ
min y/1 iE(d]
1=1
We end by remarking that when y 0 for some E [d]. the value becomes 0 so that the result also holds this case.
Summary: Combining all parts of the proof, we got
yT
inf max = DED af x
max min
yeD ;0,>0 Oi
we define the internal value to too when a O, we can further write
y r
max min V/ yED iE(d] 06
inf max zE|0,1]4 yED TT
which concludes the proof.
30

---

Remark 3. Following almost identical proof. we could similarly prove that
inf max y" x RERd a-x
max min yED seld 0a
The only change would be in the first step; using the same rescaling idea (2g a E RR.), one could prove that
yfa 2 inf max v²z, 2,
inf max
rERd yED aTx
=ER yED a a=1=1
while the reverse inequality trivially holds since {= E f =1 C R4. The rest of the proof follows without any change.
1==
Notably, since this lemma is used in all proofs to calculate the CR for the worst-case reward expectations, it implies that we would get the same results were we to define the CR as CR)(P) = inf ER CR (R.) (P,r).
31

---

Lemma 2. Let d L N. Also, let D E R4 be a convex compact set and P E RR. be convex compact polytope, both assumed to be nonempty. Then
y/ min max min y PeP yED iE|d oz
inf max min PEP DED ke(d] Os
where we define all ratios to be +00 if the denominator equals zero.
Proof. We assume w.l.o.g. that p + {0), since the infimum singleton is always equal the minimum (in this case, both equal +oo), and the result trivially holds.
Next, for all E P, define f(a) maXyED min a there exists in [d] such that Oig 0, and
Notice that for any E P s.t. + 0,
y/i max min yED iE(d] Os vED
yio 0ão
((x)
S max < oc;
where the last inequality follows from the compactness of D. In particular, since P * {0} and is nonempty, such * 0 exists, and thus inf f(a) S f(ā) < oc, so the value at the optimization problem in the l.h.s. is finite.
We next prove that f(a) is quasi-concave over P, namely
Ya + 3 P, E (0,1): ʃ(Aa + -)3) > min(s(a), ((8)-
First, if * 0 and 3 0 (or the opposite), for any (0, 1) we have that
f(Aa + ))3) f(Aa) = f(a) 2 f(a) min(f(a), f(3)).
where we used the non-negativity of f(a) and the convention that f(0) +oo. Next, assume that both a, + O. Also, let y such that
y arg max min V/i BED
*E(d] Oi
and similarly define S Such y must exist, since we could always write
f(a) = max min Y/ = max min y/ yED iE(d] a; yED se|d]a,2>0
The maximum over finite number of linear functions is continuous and the set D is compact, so maximizer in D is always attainable. Using these definitions, we have,
f(Aa + (1 - (1)) yED REld, λa; + (1 A)
max min
y/1
Ayf + (1 2
min 1
(D convex)
da + (1 - 3)
yf. y
min min <E[d]
ai 3g
y/
y/
min
min .E ag iE
min
B
min(ffaa)
Relation (x) is due to the inequality atc > min g, à for b, c, d 2 0, and one could easily verify b48 that the inequality still valid when either / = 0 or = 0.
Finally, recall that P is a compact convex polytope; in particular, each interior point could be represented convex combination of one of its finite extreme points ext(P). Then, by the quasi- concavity, the value of each interior point is lower-bounded by the value of at least one of these extreme points so that
inf f(a) = min f(a). oEP
aEext(P)
This proves that the infimum is attainable by point in P, thus concluding the proof.
32

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract clearly present the concept of reward lookahead and claim to analyze it through competitive analysis; we do so our theorems, which are formally proved in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: As with many theoretical works, the main limitation of this paper lies in the choice of the model and its assumptions, which is necessarily a simplification of real-world problems. Nonetheless, while defining the setting, we tried to choose the assumptions that we believe are most natural to study this problem. clearly present our assumptions in Section and discuss potential alternative models and extensions in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattio, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
33

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide sketch of the proof of the main results in the paper, and fully detail each proof in appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
34

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeeeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////aaaaaa...cc//a/a///taaa
Answer: [Yes]
Justification: This is a fundamental research on a core theoretical model, with no clear ethical implications.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is fundamental research on a core theoretical model, with no direct societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
36

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
37

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "ZhNGG4XbaY", "reviewer": "Reviewer_mGpv", "summary": "This paper aims to quantifiably analyze the the value of future reward lookahead in Reinforcement Learning settings where future reward information is available before-hand. The authors utilize competitive analysis, and characterize the worst-case reward distribution while also deriving exact ratios for the worst case reward expectations between standard RL agents and agents with partial future-reward lookahead information.", "questions": "Please see weaknesses section for questions.", "limitations": "While authors include useful examples towards the end of the work, it will be useful to include a section on Broader Impact as it may allow to see how the results from this work can be translated to empirical studies.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1) The paper provides an important theoretical study shedding light on the importance of future reward lookahead in Reinforcement Learning settings. The problem is very relevant to not only simulation-based but also real-world scenarios where future reward information will either be known or can be inferred via exploration.\n2) The paper is well-written, easy to follow and provides useful intuitions throughout allowing for readers to gain insight into the problem and the theoretical analysis presented.", "weaknesses": "1) There seems to be an important missing piece, specifically in situating the work with respect to the existing literature. A rich literature exists in the field of Control Theory that talks about the rollout approach and there has been theoretical evidence shedding light on advantages of rollout, which assumes the presence of future rewards (or <state,action> Q-values). How does this work connect to the Rollout approach and/or its variants?\n2) It would be helpful to have conclusive statements along with definitions presented in the work. For example, line 121 - what are the implications of the fact that \"the competitive ratio is the worst-possible multiplicative loss of the standard (no-lookahead) policy\" to policy learning?\n3) There seems to be some confusion about how dense rewards have been defined in the paper, line 344 onwards. Do the authors make the assumption that a reward is available in every state? How is the density defined in this case? Also, it is not clear why it is important to consider all states with non-zero rewards. With sufficient number of trials given sparse rewards, agents could still navigate to rewarding future states. How does this break the competitive ratio analysis further presented in the paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments.\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jg7xPsFzdL", "reviewer": "Reviewer_ofoH", "summary": "This paper examines the value of having lookahead information about future rewards in reinforcement learning. Specifically, it analyzes the competitive ratio between the optimal agent under no lookahead versus agents that can see reward realizations for some number of future timesteps. This competitive ratio is defined as the value (expected cumulative reward) of a standard RL agent with no lookahead divided by the value of an agent with L-step lookahead. Using this measure the authors provide tight bounds on this competitive ratio for different lookahead ranges, characterizing the worst-case reward distributions and environments.\n\nInterestingly, they show connections between their results and fundamental quantities in offline reinforcement learning and reward-free exploration. The analysis provides theoretical insights into the value of future reward information, and opens up the roadmap for future works on transition look-ahead and development of approximate planning algorithms.", "questions": "-", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Strengths**\n\n- The paper provides a rigorous theoretical analysis of the value of future reward information in RL, covering the full spectrum from one-step to full lookahead. It derives tight bounds on the competitive ratio for various lookahead ranges, characterizing worst-case reward distributions and environments. Notably, the competitive ratio is shown to be closely related to concentrability coefficients used in offline RL and reward-free exploration, suggesting a deeper connection between these areas.\n    \n- The analysis also includes specific environment types (e.g., chain MDPs, grid MDPs) to provide concrete examples. Notably they introduce  \"delayed tree\" environment that exhibits near-worst-case competitive ratios, offering insights into what makes lookahead challenging to utilize.\n    \n- The focus on worst-case scenarios provides robust guarantees and insights that complement average-case analyses common in RL literature. This approach lays crucial groundwork for understanding lookahead in more complex environments and could inform future practical algorithm design, bridging theoretical robustness with potential real-world applications.", "weaknesses": "**Weakness**\n\n- The analysis assumes perfect knowledge of future rewards, which may be unrealistic in many practical scenarios where only noisy or partial information might be available.\n    \n- The paper focuses on theoretical analysis in a simplified tabular setting, which may not directly translate to more complex real-world RL problems or environments. Experiments on approximate planning for complex environments would complement its theoretical results and could have provided additional insights or validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback.\n\n* **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:\n\n1. *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. \n\n2. *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.\n\n* **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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nsYJlkk0aD", "reviewer": "Reviewer_C3mL", "summary": "The paper investigates theoretically the advantage that RL agents get from reward lookahead. In a tabular MDP setup, the reward is postulated as being a random variable $R_h(s, a)$, whose value is, by default, revealed to the agent after taking the action $a$ in state $s$ at a time-step $h$. Authors calculate exactly/prove bounds on the ratio between return obtained by a no-lookahead agent and an agent that has access to information about the particular values (samples) of the reward $L$ steps ahead. Exact calculation is given in the two cases of (1) fixed rewards' expectations, fixed dynamics (2) worst-case expectations, fixed dynamics, and the (tight) bounds are given the case of (3) worst-case expectations and worst-case dynamics. Authors also discuss the connection of their results to the notion of coverability coefficient, and walk the reader through several examples of MDPs including chain-, grid- and tree-shaped environments.", "questions": "1. The central idea of using tree-shaped MDPs plus long-shot reward distributions with vanishing probability $\\epsilon$ and then moving $\\epsilon \\to 0$ is quite straightforward. The value of the paper therefore seems to be in extending this idea to cover the case of $L < H$ and various other edge cases. However, the complications in formulas in Thm 1/3 seem to stem from the problem that there's \"too many\"/\"too few\" states wrt to the time horizon (which is mitigated by adding the waiting action). Wouldn't it simplify at lot if you would just index the states and actions by $h$, which would make the MDP always a complete $A$-ary tree?\n2. All of the development is done in a finite-horizon case. However, you also mention using the receding horizon idea - would that make it possible to extend your work to get around this limitation?\n3. What would be the value/an application of this work in a more-than-toy setup?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "The paper presents the main theorems rigorously. It provides extensive and very detailed proofs for all of its statements in the appendix. I also liked the idea of discussing proof sketches in the main part of the paper. The paper discusses the connections to the existing literature in detail, and carefully spells out the differences to previous approaches.", "weaknesses": "The presentation of the paper could be improved in my opinion. The paper briefly mentions several motivating examples in the introduction (trading with known prices, ride-sharing, traffic control), but this did not give me a good understanding of what the problem is - I only understood this once I got to the formal statements in section 2.1. It would be good to have more clearly and comprehensively presented \"central example\" that would show exactly what is going on. \n\nThe paper also suffers from moving important bits to appendix - such as Figure 3, which quite important to understand Part III of the proof sketch for Thm 1. The treatment of the Part II proof is also quite brief (although the main idea of using minimax theorem for the policy maximisation/reward minimisation is quite clear).  \n\nI did not get a clear take-away from the paper: although the results were mathematically meaningful, I did not get a sense of how much should I care about reward lookahead. Looking at those pathological edge cases of reward distributions seems unavoidable from the technical point of view, but maybe could be mitigated by e.g. examples constraining the distributions to be some reasonable family. Since the contribution itself relies on a quite straightforward proof idea (c.f. Q1 below), the strength of the paper stems mostly from meticulously working through the details of extending this to a broader setup. It would be good to see an example where the theorem helps to resolve some more-than-toy problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nSadly, 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.\n\nWe 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.\n\nWhile 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.\n\n# Questions:\n\n1. 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.  \n*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.\n\n2. 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.\n\n3. 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.)  \nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously agreed on the importance and value of the contributions of this paper. Two reviewers praised the paper for its clarity, and all agreed about the high technical rigor. Based on the discussion, no further issues were uncovered, and I believe this is a clear accept.
Decision: Accept (spotlight)