Reinforcement Learning with Lookahead Information
Authors: Nadav Merlis
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
Regret Minimization
Lookahead
Primary area: reinforcement_learning
TL;DR: We study RL settings where either immediate rewards or transitions are observed before acting and show how to achieve tight regret compared to stronger baselines with similar information.

Abstract: We study reinforcement learning (RL) problems in which agents observe the reward or transition realizations at their current state _before deciding which action to take_. Such observations are available in many applications, including transactions, navigation and more. When the environment is known, previous work shows that this lookahead information can drastically increase the collected reward. However, outside of specific applications, existing approaches for interacting with unknown environments are not well-adapted to these observations. In this work, we close this gap and design provably-efficient learning algorithms able to incorporate lookahead information. To achieve this, we perform planning using the empirical distribution of the reward and transition observations, in contrast to vanilla approaches that only rely on estimated expectations. We prove that our algorithms achieve tight regret versus a baseline that also has access to lookahead information -- linearly increasing the amount of collected reward compared to agents that cannot handle lookahead information.

Reinforcement Learning with Lookahead Information
Nadav Merlis FairPlay Joint Team, CREST, ENSAE Paris nadav. wataa.merlssdesse..rrr
Abstract
We study reinforcement learning (RL) problems in which agents observe the reward or transition realizations at their current state before deciding which action to take. Such observations are available in many applications, including transactions, navigation and more. When the environment is known, previous work shows that this lookahead information can drastically increase the collected reward. However, outside of specific applications, existing approaches for interacting with unknown environments are not well-ad adaa-dd these observations. In this work, we close this gap and design provably-efficiene learning algorithms able to incorporate lookahead information. To achieve this, we perform planning using the empirical distribution of the reward and transition observations, in contrast to vanilla approaches that only rely on estimated expectations. We prove that our algorithms achieve tight regret versus baseline that also has access to lookahead information linearly increasing the amount of collected reward compared to agents that cannot handle lookahead information.
Introduction
In reinforcement learning (RL), agents sequentially interact with a changing environment, aiming to collect as much reward as possible. While performing actions that yield immediate rewards is enticing, agents must also bear in mind that actions influence the state the environment, affecting the potential reward that could be collected in future steps. When the environment is unknown, agents also need to balance reward maximization based on previous data and exploration gathering of data that might improve future reward collection.
In the standard interaction model, each timestep, agents first choose action and only then observe its outcome on the rewards and state dynamics. As such, agents can only maximize the expected rewards, collected through the expected dynamics. Yet, in many applications, some information on the immediate outcome of actions is known before actions are performed. For example, when agents interact through transactions, prices and traded goods are usually agreed upon before performing any exchange (' f'reward information') )) Alternativel,, in navigation problems, nearby traffic information is known to the agent before choosing which path go through ('transition information') ").
In a recent work, Merlis et al. 2024 shows that even for agents with full statistical knowledge of the environment, such 'lookahead' information agents - by multiplicative factor of up to AH when immediate rewards are revealed in advance and 4/2 when observing the immediate future transitions Intuitively, agents do not only gain from instantaneously using this information they can also adapt their planning to account for lookahead information being revealed subsequent states, significantly increasing their future values. However, the work of Merlis et al. [2024] only tackles planning settings in which the model is known and does not provide algorithms or guarantees when interacting with unknown environments.
drastically increase the reward collected by
A is the size of the action space, S is the size of the state space and H is the interaction length.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this work, we aim to design provably-efficiee agents that learn how to interact when given imme- diate ('one-step lookahead') reward or transition information before choosing an action, under the episodic tabular Markov Decision Process model. While such information can always be embedded into the state of the environment, the state space becomes exponential at best, and continuous at worst, rendering most theoretically-gunt -ugaaaattedd approaches both computationally and statistically intractable. To alleviate this, we start by deriving dynamic programming ( ('Bellman') equations in the original state space that characterize the optimal lookahead policies. Inspired by these update rules, we present two variants to the MVP algorithm [Zhang et al. [02 that allow incorporating either reward or transition lookahead. In particular, we suggest planning procedure that uses the parttioni empirical distribution of the reward/transition observations (instead of the estimated expectations), which might also be applied to other complex settings. We prove that these algorithms achieve tight
regret bounds of Ö SASAK) and Ö (HHSSK (VH + VA)) after K episodes (for reward and transition lookahead, respectively), compared to a stronger baseline that also has access to lookahead information. As such, they can collect significantly more rewards than vanilla RL algorithms.
Outline. We formally define RL problems with reward/transition lookahead in Section 2 and further discuss the differences between our setting and standard RL problems in Section 3 Then, we present our results in two complementary sections: Section 4 analyzes reward lookahead while Section analyzes transition lookahead. We end with conclusions and future directions in Section 6
Related Work. Problems with varying lookahead information have been extensively studied in control, with model predictive control [MPC. [amaaho et al., 2007] as the most notable example. Conceptually, when interacting with an environment that might be too complex or hard to model, it is oftentimes convenient to use a simpler model that allows accurately predicting its behavior just in the near future. MPC uses such models to repeatedly update its policy using short-term planning. In some cases, the utilized future predictions consist of additive perturbations to the dynamics (Yu et al. 2020), while other cases involve more general future predictions on the model behavior [Li et al. 2019, ZZang et al. 2021a Lin et al. 2021 2022]. To the best of our knowledge, these studies focus on comparing the performance of the controller to one with full future information (and thus, linear regret is inevitable), sometimes also considering prediction errors. They do not, however, attempt to learn the predictions. In contrast, we estimate the reward/transition distributions and leverage them to better plan, thus increasing the value gained by the agent. In addition, these works focus on continuous (mostly linear) control problems, whereas we study tabular settings; results from any one of these settings cannot be directly applied to the other.
In RL, lookahead is mostly used planning tool; namely, agents test the possible outcomes after performing multiple steps to decide which actions to take or to hetter estimate the value (Tamar et al. 2017 Efroni et al.
2019a 2020 Moerland et al. (2020 Rosenberg al. 2023 EI Shar and Jiang 2020 2021 Huang et 2019). Specifically, the future value at the end of the lookahead
Biedenkapp et al.
often estimated using rollouts, and a longer lookahead is more robust to suboptimality of the rollout
policy [Bertsekas] 2023]. However, when agents actually interact with the environment, no additional lookahead information is observed. One notable exception is [Merlis al. 2024], which analyzes the potential value increase due to multi-step reward lookahead information (and briefly mentions transition lookahead). However, they only tackle planning settings, where the model known, and do not study learning. In this work, we continue a long line of literature on regret analysis for tabular RL [Jaksch et al. [2010] [in et al., 2018 Dann et al. 2019 Zanette and Brunskill 2019 Efroni et al.) 2019b 2021 Simchowitz and Jamieson, 2019 Zhang et al.] 2021b 2023 Yer, we are not aware any existing results on regret minimization with reward or transition lookahead information.
Finally, various applications that involve one-step lookahead information have been previously studied. The most notable ones are prophet problems [Correa et al., (2019), where one-step reward lookahead is obtained, and the Canadian traveler problem with resampling [Nikolova and Karger 2008), which can be formulated through one-step transition lookahead. We discuss the relation to these problems and the relevant existing results when analyzing each type of feedback, and also discuss the relation between transition lookahead and stochastic action sets (Boutilier et al. 2018).
2 Setting and Notations
We study episodic tabular Markov Decision Processes (MDPs), defined by the tuple M =
(S, A, H, P. R), where S is the state space (of size S), A is the action space (of size A) and H is the
2

---

interaction horizon. At each timestep h {1..... : H) [H] of an episode k E [K] an agent, located in state s E S, chooses an action of E A and obtains a reward R = RA (sh a ~ (s a We assume that the rewards are supported by [0, 1] and of expectations ( a). Afterward. the environment transitions to state $1+1
(-((-s ( and the interaction continues until the end of the episode. We use the notation R ~ (s) (or s' (s)) to denote reward (next-state) samples for all actions simultancously at step h and state s and assume independence between different [
timesteps On the other hand, samples from different actions at specific state/timestep are not necessarily independent.
Reward Lookahead. With one-step reward lookahead at timestep h and state agents first observe the rewards for all actions Ra (s) {Ra (8, ae and only then choose an action to perform. Formally, define the set of reward lookahead policies II { [H] S x [o, 1] + AA). where A is the probability simplex, and denote dn (Mh, R.). The value of reward lookahead agent the cumulative rewards gathered by starting at timestep and state 8, denoted by
H
Vi R. (s) E
Σ
Ro(s To Re(ss))ssn =
We also define the optimal reward lookahead value to be V (s) e (s). When inter- acting with an unknown environment for к episodes, agents sequentially choose reward lookahead policies x I based on all historical information and measured by their regret,
Reg
R (K) = Σ(<
(v ( V1 Villi (ot)
k=
We allow the initial state of each episode of to be arbitrarily chosen.
Transition Lookahead. Denoting ( a), the future state when playing action a at step h and state 8, one-step transition lookahead agents observe (s) (sh+1 a) a)) aEA before acting.
The set of transition lookahead agents is denoted by II2 = {T [H] x x S + Da} with values
H
VTx E
Σ
me m
The optimal value is V/ (s) = maxTTnT V/2 (s), and we similarly define the regret versus optimal transition lookahead agents as Reg" Reg"(K) = Σk (v+T'((st)) - -V," (st))
When the type of lookahead is clear from the context, we sometimes denote values by V and V
Other Notations. For any p E A. and V IR", we define (Vr, - -" Also, given a transition kernel P and vector V e R we let aV(s, and similarly define it for value or transition kernel differences. We denote by n a). the number of times the pair (s, a) was visited at timestep h up to episode A (inclusive) and similarly denote
((s))s,))V(ss)
n (x) = EaEA n (s,a). a). We also let ri((,, a)
{(x 8 = a a R and n (( Et= 11
(r('s(s, (s.a) Ek= 1f o = s = aa, h+1 = { be the empirical expected rewards and transition kernel at (sh, an) = (s, a) using data up to episode i and assume they are initialized to be zero. Finally, we denote by R (s), the empirical reward distribution across all actions, and use ()()) to denote the empirical joint next-state distribution for all actions. In particular, if k; is the gth episode where & was visited at step h, to sample R (s). we uniformly sample U ([ [[ (s)]) and return R [t (s, a)} "
A sample s' ~ 1o) (s) similarly returns s' = { /k, (s, a) JOEA"
When we want to indicate the distribution used calculate expectation, we sometimes state it in subscript, e.g., write [(((a) to indicate that R(a) ~ Rx a) or use EM to emphasize
This assumption is not used by our algorithms: it is only to ensure that the optimal policy is Markovian.
3

---

that all distributions are according to an environment M. In this paper, O-notation only hides absolute constants while O hides factors of polylog(S, A, H, K, K, We also use the notation a V b max(a, b).
3 Comparing the Values of Lookahead Agents and Vanilla RL agents
In the classic RL. formulation le.g., Azar et al. 2017 agents only observe the reward and transition after performing an action and aim to maximize the no-lookahead value, defined by
(s) E Σ rr,s, (s,))ss
where x E IT-M = [ x S + A is a Markovian policy. The optimal value is V max (s) and the regret is classically defined as Reg(K) = > (vro(s+) - VT" (of)
By definition, the set of lookahead policies also includes all Markovian policies (since agents are not obliged to use reward/transition information). so the optimal lookahead values are always larger than their no- lookahehee counterpart. In other words, denoting the value gain due to lookahead information by GR V. (s) (s) and (s) = In terms of regret, for any fixed algorithm, we can also write
V (s) Vin(ss, it holds that G GT 0.
K
K G 6
Reg(K) = Reg "e (K) - EGR( = Reg"
T (K)
k=1
1=1
As the value gains are non-negative. it directly implies that any regret bound w.r.t. the lookahead value also leads to the same bound for the standard regret. Even more so, in most cases, lookahead information leads to a strict improvement in the value, that is, (s),,, happens, any algorithm with sub-linean lookahead regret enjoys negative linear standard regret:
([ss),G" G* 2 Go O. When this
If Reg (KK o(K) and (sf 2 for all k E [K]. then Reg( () < GGoK + o(K).
The same also holds for transition lookahead. Conversely, any agent that suffers positive standard regret will suffer linear regret compared to the best lookahead agent, i.e.,
If (eg 2 0 and (*(st) 2 for all k E [K]. then Reg" Reg"(K) 2 GoK.
Notably, any agent that does not use lookahead information will suffer linear lookahead regret in any such environment. We now present two illustrative examples for environments where the lookahead value gain sigmificant, one for reward lookahead and another for transition lookahead.
Reward lookahead. Consider a simple 2-state environment, depicted in Figure T Starting at 8;, agents can either stay there by playing 01. earning no reward, or play any other action and move to the absorbing sy, obtaining Bernoulli reward Ber(//(-11)))) Actions in the terminal state s yield no reward. Without observing the rewards, agents will arbitrarily move from 8; to 8y, obtaining reward //no 1/(A-1)иr in expectation. On the other hand, when agents observe the rewards before acting, they should move from 8; to s only if a reward was realized for some action (and otherwise, stay in s; by playing a,) Such agents will have (A () opportunities to observe unit reward across all timesteps and actions, collecting in expectation VR,- = (1 1/((-1))((4 (A-1) > 1 - 1/c. other words, just by observing the rewards before acting, the agent's value multiplicatively increases by almost / fR, /n se At..
Yo of as
Rio) Bar (aripn)
Figure I: Two-state prophet-like problem
Moreover, the additive value gain is G x 1/e, so sub-linear lookahead regret with reward information results with a negatively-linear standard regret of Reg(K)= S ((1-/))K
Transition lookahead. Consider a chain of H/2 states (also described in further detail at Ap- pendix C.9 and depicted at Figure 2. In each state, one action deterministically keeps the agent in its

---

current state, while all other actions move the agent one state forward w.p. 1/A, but lead to terminal non-rewarding state otherwise. If the reward is located at the end of the chain, any standard RL agent can collect it only at an exponentially low probability. On the other hand, transition lookahead agents would move forward only if there is an action that allows it while staying at their current state otherwise; such agents will collect the rewards at the end of the chain with constant probability,
More specifically, any no-lookahead agent can collect at most V = O H A A-//2) rewards, while transition lookahead agents can collect VT: 22 H); as such, lookahead agents achieve exponential increase in value, and sublinear regret versus the best lookahead agent will yield standard regret of Reg( (K) S K.
In the following sections, we will present agents that are guaranteed to always achieve sublinear regret compared to the best lookahead agent.
4 Planning and Learning with One-Step Reward Lookahead
In this section, we analyze RL settings with one-step reward lookahead, in which immediate rewards observed before choosing action. One well-known example of this situation is the prophet problem [Correa et al.) 2019]. where an agent sequentially observes values from known distributions. Upon observing value, the agent decides whether to take it reward and stop the interaction, or discard it and continue to observe more values. This problem has numerous applications and extensions concerning auctions and posted-price mechanisms [Correa et al., 2017]. As shown in [Merlis et al.) 2024]. it is critical to observe the distribution values before taking a decision; otherwise. the agent's s revenue can decrease by factor of H. Notably, the example presented in Figure is a small variant of the prophet problem, where the agent can either take one of A - values and finish the interaction or discard them and continue playing by staying at st we showed that for this example, the lookahead information increases the value by factor of V RR, /V"o x AH.
The most natural way to tackle this setting is to extend (augment) the state space to contain the observed rewards; this way, we transition from a state and reward observations to a new state with new reward observations and return to the vanilla MDP formulation. However, this comes at great cost. Even for Bernoulli rewards, there are 2 possible reward combinations at any given state, and the augmentation increases the state space by this factor - leading an exponentially-large state space. Even worse, for continuous rewards, the augmented state space becomes continuous, and any performance guarantees that depend on the size of the state space immediately become vacuous. Hence, algorithms that naïvely use this reduction are expected to be both computationally and statistically intractable. We refer to Appendix B.2 for further details on one such augmentation.
We take a different approach and derive Bellman equations for this setting in the original state space. Proposition 1. The optimal value of one-step reward lookahead agents satisfies
V=+11 (s) = 0,
Vs E
}}
R. (s) = (R) A
max
(n, + Pa(s''s,
Vs Sheelell (H].
s'ES
Also. given reward observations R = (R(a)}aEA at state and step h, the optimal policy is
(3, R) E arg max R(a)+ + Σ (1)
REA
sEES
We prove Proposition]] I in Appendix B.2, where we present an equivalent environment with extended state space in which one could apply the standard Bellman equations [Puterman 2014] to calculate the value with reward lookahead. In contrast to the previously discussed augmentation approach, we find it more convenient to divide the augmentation into two steps at odd steps 2h- 1. the augmented environment would be in a state & x O, while at even steps 2h, the state is 8n x R., Doing so creates overlap between the values of the original and augmented environments odd steps, simplifying the proofs. We also use this augmentation to prove a variant of the law of total variance [LTV, e.g. Azar et al. 2017) and a value-difference lemma [e.g. Efroni al. 2019b)
We remark that calculating the exact value not always tractable even for S problems) and Gaussian rewards, Proposition| I Irequires calculating the expectation of the maximum
(bandit
5

---

Algorithm 1 Monotonic Value Propagation with Reward Lookahead (MVP-RL)
Require: 5 E (0, 1), bonuses 1 (s), k
2: for k == 1.2... do
3: Initialize V H+1 (s) = 0
4: for 1: H, H 1, do
5:
Calculate the truncated values for all 8 E ES
(i) min 2 E
max aEd
R(a) bb (s, P Vhillssa)) +bEn()))
6:
end for
7:
for h 1, H do
8: Observe sy and Rt, (sh a) for all EA
9: Play action Oa arg ma Rt (s a) + i (6%, a) + (V+1
Collect the reward 12) (s at) and transition to the next state sh (h(115h..0k a
11: end for
end for
of Gaussian random variables, which does not admit any simple closed-form solution. On the other hand, these equations allow approximating the value by using reward samples - in the following, we show that can be used achieve tight regret bounds when the environment unknown.
4.1 Regret-Minimization with Reward Lookahead
We now present tractable algorithm that achieves tight regret bounds with one-step reward lookahead. Specifically, we modify the Monotonic Value Propagation (MVP) algorithm [Zhang et al. 202 to perform planning using the empirical reward distributions instead of using the empirical reward expectations. To compensate for transition uncertainty. we add a transition bonus that uses the variance of the optimistic next-state values (w.r.t. the empirical transition kernel). designed to be monotone the future value. Such construction permits using the variance of optimistic values for the bonus calculation while being able to later replace it with the variance of the optimal value (see discussion in ZZang et al. 2021b). A reward bonus is used for the value calculation, but does not affect the action choice in the current state. Intuitively, this is because we get the same amount of information for all the actions of a state, so they have the same level of uncertainty - there is no need for bonuses encourage reward exploration the action level.
high-level description of the algorithm is presented in Algorithm I. while the full algorithm and its bonuses stated in Appendix [B.3 Notice that the planning requires calculating the expected maximum using the empirical distribution, whose support always contains at most K elements, so both the memory and computations are polynomial. The algorithm ensures the following guarantees:
Theorem When running MVP-RL, with probability at least uniformly for all K 2 1, it holds that Reg" R "(K) (VVH'SAK In SAHK 52 SAHK)
See proof in Appendix B.7 episodic RL of Ω for known deterministic rewards, so in particular, also holds for problems with reward lookahead.
Remarkably, our upper bound matches the standard lower bound for Domingues et al. 2021 up to log-factors; this lower bound is proved
H
To our knowledge, the only comparable bounds in settings with reward lookahead were proven to prophet problems; as agents observe (up to) n distributions
fixed order, it can be formulated as deterministic chain-like MDP, with H = n, S = n + and A = 2. Agents start at the head of the chain and can either advance without collecting reward or collect the observed reward and move to a terminal non-rewarding state (for more details, see Merlis et al. 2024). For this problem, Gatmiry et al. 2024] proved regret bound of Ö(n3 /K) (albeit requiring a weaker form of feedback), and Aarrwa et al. 2023] proved bound of (nv slightly better than ours, but heavily relies on the ability to control which distributions to observe, which a specific instance of deterministic transitions. We are unaware of any previous results that cover general Markovian dynamics.

---

4.2 Proof Concepts
When analyzing the regret of RL algorithms, key step usually involves bounding the difference between the value of a policy in two different environments ('value-diffrrence lemma'), ). In particular, for given policy æ²,, many algorithms maintain confidence interval the value V (s) [V7 V/ (s)]. calculated based on optimistic and pessimistic MDPs that use the empirical model with bonuses/penalties (Dann et al.) 2019 Zanette and Brunskill [019]] Efroni et al. [202]] Then, the instantaneous regret (without lookahead) 18 bounded using the optimistic values by
V (#n) - V (sn) = (Fh 1 (sh; an) - Th (1 (n)) + (Ph- Ph) VA (9h.aa)
Ph (++ Vi+1 (5h, as) + bonuses,
while the pessimistic values are used either as part of the bonuses or while bounding them. However, when trying perform a similar decomposition with reward lookahead, we do not have the difference of expected rewards, but rather terms of the form
E R (en) [R(* R))] RR [(T R))
(see, e.g., the last term of Lemma 1 in the appendix). As the action can be an arbitrary function of the reward realization, this term is extremely challenging to bound. For example, one could couple both distributions while trying to relate this error term to a Wasserstein distance between the empirical and real reward distribution; however, such distances exhibit much slower error rates than standard mean estimation [Fournier and Guillin 2015). Instead, we follow a different approach and show that uniformly for all possible expected next-state values PV E [0, HJ given state), it holds w.h.p. that
(as a function of the action at a
R R (s)
max R(aa + PV(s,a)
E (R)((()
max R(a) (V a)
A In
n1 (s) V1
Throughout the proof, whenever we face an expectation w.r.t. the empirical rewards, we reformulate the expression fit the form of Equation (T) and use it 'change of measure' tool. We remark that while this confidence interval admits an extra A-factor compared to standard bounds, the counts only depend on the visits to the state (and not to the state-action), which compensates for this factor.
The choice of MVP for the bonus is similarly motivated unlike some other bonuses (e.g., Zanette and Brunskill 2019). MVP does not require pessimistic values either in the bonus itself in its analysis. In contrast to the optimistic ones, the pessimistic values are not calculated via value iteration, but rather by following the policy x* in the pessimistic environment. As such, they cannot be easily manipulated to fit the form in Equation (I]
The analysis of the transitions adapts the techniques in [Efroni al. 2021 while requiring extra care in handling the dependence of actions in the rewards.
5 Reinforcement Learning with One-Step Transition Lookahead
We now move to analyzing problems with one-step transition lookahead, where the resulting next state due to playing any of the actions is revealed before deciding which action to play. For example, consider the stochastic Canadian traveler problem with resampling (Nikolova and Karger 2008 Boutilier et al. 20018). In this problem, an agent wants to navigate on graph as fast as possible from source a target, but observes which edges at node are available only upon reaching this node. When edge availability is stochastic and resampled every time node is visited, this is a clear case of one-step transition lookahead, as the information on the availability of edges is given before trying to traverse them. The example in Section and Appendix C.9 is one possible formulation of this problem on a chain - agents are awarded for arriving at the end of the chain as fast as possible, but trying to use a non-existing edge results with termination. We showed that in this particular instance, the lookahead value exponentially larger than the standard value, and any lookahead agent with low regret would greatly surpass no-lookahead agents.
7

---

As with reward lookahead, the future states for all actions can be embedded into the state, but doing so increases the size of the state space by a factor of S*, again making this approach intractable (see Appendix C.2 for an example for such an extension). We once more show that this is not necessary; the cansition-lookaaeee optimal values can be calculated using the following Bellman equations:
Proposition 2. The optimal value of one-step transition lookahead agents satisfies
V (s) = O, #++
Vs E S
VI (s) = B (p())
max aEA
Th (n + T (d (s,
Vs E S. E [M].
Also, given next-state observations s'= {o'(aa) (d'(a)) aEA at state and step h, the optimal policy is (s, 8') E arg max (a(s, Vizi(s
acA
The proof can be found Appendix C.2 and again relies on augmenting the state space to incorporate the transitions; this time, we divide the episode into odd steps whose extended state is 8y x % (for an arbitrary fixed s SA and even steps with the state Sp. x 4 Beyond planning. this again allows proving a variant of the LTV and of a value-difference lemma.
One important insight is that the policy (8, 8') admits the form of list. Namely, consider the values ViA (s, a) (s) + (s') and assume some ordering of next-state-action pairs {(s], a:) j= such that (s, (1.
Vi (s. O.s.). Then, an optimal policy would look at all realized pairs (a'()), a) and play the action with the highest location in this list. We refer the readers to Appendix C.4 for an additional discussion list representations in transition lookahead.
Similar results could be achieved through a reduction to RL problems with stochastic action sets [Boutilier et al. 2018). There, at every round, subset of base actions is sampled, and only these actions are available to the agent. In particular, one could sample A actions of the form (s', a) E S A and impose deterministic transition to s' given this extended action. However, since every original action must be sampled exactly once, this sampling procedure creates a dependence between pairs even when next-states at different actions are independent, adding unnecessary complications. We show that when transitions are independent between states, the expectation in Proposition 2 can be efficiently calculated (see Appendix C.4.I for details), and otherwise, it can be approximated through sampling, as we do in learning settings.
5.1
with Transition Lookahead
Relying on similar principals as with reward lookahead, we now present MVP-TL, an adaptation of MVP to settings with one-step transition lookahead (summarized in Algorithm [ the full details can be found at Appendix C.3). This time, we estimate the empirical expected reward and add standard Hoeffding- reward bonus, while performing planning using samples from the empirical joint distribution of the next-state for all the actions simultaneously. A variance-based transition bonus is added to the values; though this time, the variance also incorporates the rewards, namely
Var O P (6) (5,
69,,, (8) R
VA 6') = -mx-)-mmx((rr ph "ss a) (8, + V (s)))) aEA
V=)
The motivation for this modification is the technical challenges described in Section 4.2 in the context of reward lookahead. For reward lookahead, we analyzed a value term that included both the rewards and next-state values, and used concentration arguments to move from the empirical reward distribution to the real one. For transition lookahead, similar values are analyzed, but we require variance- based concentration to obtain tighter regret bounds [Azar et al., (017), so this variance naturally arises. The bonus is again designed to be monotone, as the original MVP algorithm, and does not affect the immediate action choice only the optimistic lookahead value. As before, the planning relies on sampling the next-state observations at previous episodes, and so it polynomial, even if the precise joint distribution is complex. The algorithm enjoys the following regret bounds:
Theorem 2. When running MVP-TL TL, with probability at least 1 uniformly for all K 2 1, it holds SAHK 8
that Reg" (K) S O (VHPSK (VH + VA)
H8S A3 SAHK 2
8

---

Algorithm 2 Monotonic Value Propagation with Transition Lookahead (MVP-TL)
Require: 5 E (0, 1), bonuses & (s. a), (s)
2: for k == 1.2... do
3: Initialize V H+1 (s) = 0 4: for 1: H, H 1, do
5: Calculate the truncated values for all E ES
( (k, + (())( +b +oRa(s),11 }
(i) min EanyE,,.. BA-
max aEd
6:
end for
7:
for h 1, H do
8:
Observe sy and 1 a) for all a
a))} 10: Collect the reward R% ~ (s a and transition to the next state s/ = s/k ( a%)
9: Play an action of E arg max ph: (s a) bg (5% a)
11: end for
12:
end for
See proof in Appendix C.8 For transition lookahead, the regret bounds we provide exhibit two rates, both corresponding to a natural adaptation of known lower bounds to transition lookahead.
1. 'Bandit rate' H(AHA)))): this is the rate due to reward stochasticity. Consider problem where at odd timesteps 2h- 1 and across all states, all actions have rewards of mean 1/2 c, except for one action of mean 1/2. Assuming that the ditt-diittiibtton is uniform, each such timestep forms a hard instance of contextual bandit problem with contexts, exhibiting a regret of 12( (A(VSA)) [Auer et al. 2002 Bubeck et al. 2012). Since there are H/2 odd steps and we can design each step independently, the total regret would be Q/H V SAK). The even steps can be used to 'remove' the lookahead and create uniform state distribution. To do so, we that when taking an action at odd steps, we always transition to a fixed state 8.- From this state, one action a1 leads uniformly to all states, while the rest of the actions lead to an absorbing non rewardigg state rendering them strictly suboptimal. Thus, no-regret agents will only play 41, regardless of the lookahead information, and the state distribution at odd timesteps will be uniform.
2. "Transition learning rate' OKVH3SK): recall that the vanilla RL lower bound designs tree with ((S) leaves, to which agents need to navigate at the right timing (with 2(H) options) and take the right action (out of A). While all leaves might transition agents to rewarding state, one combination of state-action-timing has slightly higher probability of doing so [Domingues] jet al. 2021). This roughly creates a bandit problem with SAH arms, constructed such that the maximal reward is S (MH)), yielding total regret of I! HVHSAK. Now consider the following simple modification where in each leaf, only one action can lead to a reward (and the rest of the actions are 'useless' never lead to rewards). Thus, the agent still needs test all leaves at all timings, and so there are still SH 'arms' with a corresponding regret of v H3SK. Moreover, to test leaf at certain timing, we must navigate to it, and since the agent is going to play the single useful action at the leaf, transition lookahead does not provide any additional information.
As discussed before, transition lookahead can be formulated as RL instance with stochastic action sets. While Boutilier et al. (0188) prove that with stochastic action sets, Q-learning asymptotically converges, they provide no learning algorithm nor regret bounds. Therefore, to our knowledge, our result is the first to achieve sublinear regret with transition lookahead.
5.2 Proof Concepts
Transition lookahead causes similar issues as reward lookahead. Hence, it is natural to apply similar analysis approach- - first, formulate the value as the expectation w.r.t. the next-state observations of the maximum of action-observation dependent values; then use uniform concentration as 'change of measure" tool between the empirical and real next-state distribution. In particular, Vs, s' represents the value starting from state s, performing and transitioning to s', one can show that for

---

all V-s, E [0, SASA (see Lemma 19p.
E B 2()) max (s,, (4)) - (s)) max V(s, (s, (a))
SAln Var si (a) maxo V(s, s' (a)) a)
Th
(s)
where the variance term stems from using a Bernstein- concentration bound. However, in contrast to the reward lookahead, the v /SA-factor propagates to the dominant term of the regret, so pursuing this approach would lead to worse regret bound of Ó (VH>S*AK)
To avoid this, we pinpoint the two locations where this change of measure is needed the proof that Ví is optimistic and the regret decomposition and make sure to perform this change of measure only on a single value V (8, s', a) = [s, a) + V (6"), mitigating the need to cover all possible values and removing the additional f-.t-f However, doing leaves us with residual term. Defining V% (s,8') 8') this term is of the form
maxae V (8,8 (a), a)} and assuming a similar optimistic value V/ (8, 8'),
E A (s)) (s, Vi s')] - E. V (s, 5') - (s, 8')].
While similar terms have been analyzed before Zanette and Brunskill 2019 Efroni et al. 2021] the analysis leads to a constant regret term that depends on the support of the distribution in question; in our case, is the distribution over all possible next-states of cardinality S.A. Therefore, following the same derivation would lead to an exponential additive regret term.
We overcome it by utilizing the fact that both the optimistic policy and the optimal one decide which action to take according to list of next-state-actions (s', a). In other words, instead of looking at the next-state s' (with S possible values) to determine value, we look at the highest-ranked realized pair (s', a) in the list that corresponds to the policy that induces the value (with S SA possible rankings). Since have two values, we need to calculate the probability of being at certain list location for both n and x² but the cardinality of this space is (SA)): polynomial and not exponential.
Conclusions and Future Work
In this work, we presented an RL setting in which immediate rewards or transitions are observed before actions are chosen. We showed how to design provably and computationally efficient algorithms for this setting that achieve tight regret bounds versus strong baseline that also uses lookahead information. Our algorithms rely on estimating the distribution the reward or transition observations, concept that might be utilized in other settings. In particular, we believe that our techniques for transition lookahead could be extended RL problems with stochastic action sets [Boutilier et al.. 2018). but leave this for future work.
One natural extension to our work would be consider multi-step lookahead information observing the transision/rewards L steps in advance. We conjecture that from statistical point of view, a similar algorithmic approach that samples from the empirical observation distribution would be efficient. However, it is not clear how to perform efficient planning with such feedback.
Another possible direction would be to derive model-free algorithms [Jin et al. 2018 with the aim to improve the computation efficiency of the solutions; our model-based algorithms require at most O2S AH) computations per episode due to the planning stage, while model-free algorithms might potentially allow just (AF)) computations per episode.
On the practical side, previous works presented RL algorithms that utilizeeestimatee world model with multi-step lookahead to perform planning and learning [Schrittwieser et al. 2020 Chung et al. 2024]. aiming to achieve the optimal no-lookahead value. For some of these approaches, it is quite natural to replace the simulated world behavior with lookahead information on the real future realization. We leave this adaptation and evaluation to future studies.
Finally, the notion of lookahead could be studied in various other decision-making settings (e.g., linear MDPs et al. 2020) and can also be generalized to situations where lookahead information can be queried under some budget constraints [Efroni et al. (02T] or when agents only observe noisy lookahead predictions; leave these problems for future research.
10

---

Acknowledgements
We thank Alon Cohen and Austin Stromme for the helpful discussions. This project has received funding from the European Union's 's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034255.
References
Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. stochastic optimization. arXiv preprint arXiv:2312.1542) 2023.
learning for monotone
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire, The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77, 2002.
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.
Dimitri Bertsekas. A course in reinforcement learning. Athena Scientific, 2023.
André Biedenkapp, Raghu Rajan, Frank Hutter, and Marius Lindauer. Temporl: Learning when act. In International Conference on Machine Learning, pages 914-924. PMLR, 2021.
Craig Boutilier, Alon Cohen, Avinatan Hassidim, Yishay Mansour, Ofer Meshi, Martin Mladenov, and Dale Schuurmans. Planning and learning with stochastic action sets. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 4674 4682, 2018.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends Machine Learning, 5(1):1-122, 2012.
Eduardo F Camacho, Carlos Bordons, Eduardo F Camacho, and Carlos Bordons. Model predictive control. Springer, 2007.
Stephen Chung. Ivan Anokhin, and David Krueger. Thinker: learning to plan and act. Advances in Neural Information Processing Systems, 36, 2024.
José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for a random stream of customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 169-186, 2017.
Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70) 2019.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. International Conference on Machine Learning, pages 1507-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 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-12234, 2019b.
Yonathan Efroni, Mohammad Ghavamzadeh, and Shie Mannor. Online planning with lookahead policies. Advances in Neural Information Processing Systems, 11140244-4033, 2020.

---

Yonathan Efroni, Nadav Merlis, Aadirupa Saha, and Shie Mannor. Confidence- budgee matching for sequential budgeted learning. In International Conference on Machine Learning, pages 2937-2947. PM 2021.
Ibrahim EI Shar and Daniel Jiang. Lookahead-boundee q-learning. In International Conference on Machine Learning, pages 8665-8675. PMLR, 2020.
Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707-738, 2015.
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit algorithms for prophet inequality and pandora's s box. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 462-500. SIAM, 2024.
Yunhan Huang, Veeraruna Kavitha, and Quanyan Zhu. Continuous-time markov decision processes with controlled observations. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 32-39. IEEE, 2019.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr)::533-1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137-2143. PMLR, 2020.
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. Bounded-regret mpe via per- turbation analysis: Prediction error, constraints, and nonlinearity. Advances Neural Information Processing Systems, 35:36174-36187, 2022.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. In Conference on learning theory, 2009.
Nadav Merlis, Dorian Baudry, and Vianney Perchet. The value of reward lookahead in reinforcement learning. arXiv preprint arXiv:2403. 1637, 2024.
Thomas M Moerland, Anna Deichler, Simone Baldi, Joost Broekens, and Catholijn M Jonker. Think neither too fast nor too slow: The computational trade-off between planning and reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Nancy, France, pages 16-20, 2020.
Evdokia Nikolova and David R Karger. Route planning under uncertainty: The canadian traveller problem. In AAAI, pages 969-974, 2008
Martin I. Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Aviv Rosenberg, Assaf Hallak, Shie Mannor, Gal Chechik, and Gal Dalal. Planning and learning with adaptive lookahead. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9606-9613 9613, 2023.
Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature. 588(7839):6044699, 2020.
12

---

Max Simchowitz and Kevin G Jamieson. Non- Non-asympiotic gap-dependent regret bounds for tabular mdps. In Advances Neural Information Processing Systems, pages 1153-1162, 2019.
Aviv Tamar, Garrett Thomas, Tianhao Zhang, Sergey Levine, and Pieter Abbeel. Learning from hindsight plan-episodie episodic mpc improvement. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 336-346- IEEE, 2017.
Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Advances in Neural Information Processing Systems, 33:1994 2004, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependen 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 lqr 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.
Zihan Zhang, Yuxin Chen, Jason Lee, and Simon Du. Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307. 13586, 2023.
13

---

Table of Contents
Structure the Appendix
B
Proofs for Reward Lookahead
15
B.
Data Generation Process
15
B.2
Extended MDP for Reward Lookahead
15
B.3
Full Algorithm Description for Reward Lookahcad
20
B. 4
The First Good Event Concentration
21
Optimism the Upper Confidence Value Functions
22
The Second Good Event Martingale Concentration
23
Regret Analysis
25
C
Proofs for Transition Lookahead
30
C.1
Data Generation Process
30
Extended MDP for Transition Lookahead
30
Algorithm Description for Transition Lookahead
................................
34
C.4
Additional Notations and Representation
35
The First Good Event Concentration
37
C.6
Optimism of the Upper Confidence Value Functions
................................
39
C.7
The Second Good Event Martingale Concentration
40
C.8
Regret Analysis
41
C.9
Example: Value Gain due to Transition Lookahcad
46
Auxiliary Lemmas
47
D. Concentration results
47
D
Count-Related Lemmas
51
D.3 Analysis of Variance terms
52
E Existing Results
53
A Structure of the Appendix
Both reward and transition lookahead appendices share the following structure. First, we describe our assumption on the data generation process and analyze general properties of reward and transition lookahead. This is done by looking at an extended MDP that incorporates the lookahead information into the state. Then, we present the full algorithm and describe the relevant probabilistic events that ensure the concentration of all the empirical quantities. For transition lookahead, we require some additional notions for the event definitions (including the list representation of values and policies), which are explained in a separate subsection.
Given the concentratiio--elated good event, we can prove that the planning procedure in the algorithm optimistic, which we do in the subsequent subsection. Then, we define an additional good event that allows adding and removing conditional expectations in a way that will be needed for the proof.
At this point, provided all (almost all) the results required for the regret analysis, and the proof of the main theorems is stated. The proofs also require some additional analysis for the bonuses (and especially variance terms), which is located the end of the regret analysis.
For transition lookahead, the appendix includes one more part that further analyzes the example presented in Section
At the end of the appendix, we state and prove several lemmas that will be used throughout our analysis, while also stating several existing results that will be of use.
14

---

B Proofs for Reward Lookahead
B.1 Data Generation Process
To simplify the proofs, we assume the following 'tabular' data-generation process: Before the game starts, set of K samples from the transition probabilities and rewards is generated for all (s, a, h.. Once state at step h is visited for the 7th time, the jth sample from the reward distribution (s(s) is the reward realization for all action a E A. When state-action pair is visited for the 4 time, the tth sample from the transition kernel Pa (-]s,, a) determines the next-state realization. In particular, it implies that the reward samples from the first i visits to state are i.i.d., and the same for the next-states samples and state-action visitations. Throughout this appendix, we use the notation actions.
R
{ RR) (s a) aEAA denote the reward observation at episode h and timestep h for all the
For the proof, we define the following three filtrations. Let
FR. -
(s), a.. Ri J
A
oz
k-1 R }
TEEHH)
{ st at, R
"EEW s shinl):
R.h o (s), R2) (E
k-1 R 1 az
{ st at Rt (
JEE[MY
the filtrations that contains all information until episode k and step h, as well as the state at timestep h + 1, all information of time h + respectively. We make this distinction that PE, contains - also contains at. We also define
only sh while F.R.
F = -
(fst. af R (E[H)
{ R. (E(m)
k++1 ).
which contains all information up the end of the h episode, as well the initial state episode k ++1. 1.
B.2 Extended MDP for Reward Lookahead
In this appendix, we present alternative formulation of the one-step reward lookahead that falls under the vanilla (no-lookahead) model and would be helpful for the analysis.
Throughout the section, we study the relations between MDPs with and without reward lookahead, and between different MDPs with lookahead. Therefore, for clarity, we state the concerning MDP in the value, e.g. RR (sl Specifically in this subsection, we distinguish between values without lookahead (denoted V") and values with lookahead (denoted V VR..), ). In the following subsections, unless stated otherwise, we will only consider lookahead values; for brevity, and with some abuse of notations, we will then omit the
the value notation.
For any MDP M = (S,A, H, P, R), define an equivalent extended MDP M of horizon 2H that separates the state transition and reward generation as follows:
1. Assume w.l.o.g. that M starts at some initial state 81. The extended environment starts at a state 81 x O, where O E IR is the zeros vector.
2. For any E [H] at timestep 2h- - 1, the environment M transitions from state 8y X 0 to 8h. R. where R (s) is vector containing the rewards for all actions E A. This transition occurs regardless of the action that was played. At timestep 2h, given an action di, the environment transitions from 8;, R to 8 O, where 8 Pa( (ab, an).
3. The reward at state R when playing action a is R(a), namely, the reward is deterministic and only obtained on even timesteps.
We emphasize that throughout the section, we assume that M and M are coupled; that is, assume that under policy in M, the agent visits a state 8h, observes RA, plays an action d and transitions to $5+1- Then, in M R the agent starts from S₁, X O, transitions to s; x (regardless the action played), takes the action as and finally transitions
8 x 0.
Since the reward is embedded into the state, any state-dependent policy in M is one-step reward lookahead policy in the original MDP. Moreover, the policy at the odd steps of M does not affect
15

---

the value, and assuming that the policy at the even steps in M is the same as the policy in M, we trivially get the following relation between the values
(s, RMM E
Σ (o as)lsn 8, Rr (x,) R. ग
A Vil... R[M),
V2h (s E
Rs (st, as)lsh = 8, n = V (s) Σ
(3)
While M has continuous state space, which generally makes algorithm design impractical, this representation permits applying classic results on MDPs to environments with one-step lookahead.
As a remark, rewards could be directly embedded into the state without separating the state and reward updates. However, this creates unnecessary complications when analyzing the relations between similar enviromments. This is because we are mainly interested the value given the state in expectation over the realized rewards. In particular, value-difference are analyzed assuming shared initial state, but in our case, we do not want to assume the same reward realization, but rather also account for the distance between reward distributions, which the step separation enables. For similar reasons, this representation also simplifies the proof of the law of total variance [Azar et al. 2017]
Proposition 1. The optimal value of one-step reward lookahead agents satisfies H++ (s) O,
E
(ss (R-(((s)
max aeA
Rn(s,a)+ + Pd
Vs S,e [H].
s'ES
Also, given reward observations R (R(a))aEd at state and step h, the optimal policy is
arg max R(a) E (a( }
(s, R)
aEA
e'ES
Proof. We prove the result in the extended MDP M and remind the reader that this formulation. the policy only uses state information, as in the standard RI. formulation. In particular, it implies that there exists a Markovian optimal policy that uniformly maximizes the value (in the extended state space), and the optimal value is given through the
equations (Puterman] 2014
(2 (RM R = O,
Vs E S, R e RA
(8, R. = max R(a)+ + Σ Pald VV } 4h E [M] R. RA
EES
V (2, 0 (R) (2 R]
vh E [H] E S.
(4)
By the equivalence between M and R for all policies, this is also the optimal value in M. Specifically, combining both recursion equations and substituting the relation between the original and extended values of Equation 33. we get the desired value recursion for any h E [H]] and S:
V.f.. (s|MM
V (s, (
= (x)( (s, R]
|
= ERI(1) max R(a) + Σ P,( a (44
x'ES
= (x) max R(a)+ + ()) a)
#'ES Similarly, for any h [H) E S and R E R.A, the optimal policy at the stages of the extended MDP is
(s, R) E arg max
R(a) + (6
aEA
e'eS
16

---

alongside arbitrary actions at odd steps. Playing this policy in the original MDP will lead to an optimal one-step reward lookahead policy, it achieves the optimal value of the original MDP. This policy directly translates to the optimal policy in the statement, by the equivalence between the original and extended MDPs and the relation 1 Ol.M) (
(s'MM)
Remark 1. As in Equation (4) one could also write the dynamic programming equations for any policy π. E TTR, namely
V2h (5, RMM (( R)) + Σ
TA TA (65
vh [II, E E RR
e'ES
V2h (8, M = (x)()) [V R].
th [H] E
In particular, following the notation of Equation one can also write
Vi (s, R.M) R(TT( (s, R)) + Σ
Paa('l [s. m. V) (s and,
s'ES
VR (s|M) ER((S) V/ Vi R|.M)
=RR((s)
((nn(s,R)) +
Σ
Pa(s'ls, (n (ss, ()
s'ES
We will use this notation in some of the proofs.
Another useful application of the extended MDP is variation of the law of total variance (LTV), which will be useful our analysis
Lemma 3. For any deterministic one-step reward lookahead policy 11 it holds that
"
2
E
E
[s an) - V2R (s1) |T, 81
Proof. We apply the law of total variance (Lemma 27 in the extended MDP; there, the rewards deterministic and equal to either (at odd steps) or Rí (8h, an) (at even steps), so the total expected rewards are F==1 Rí (Rn,
Ra(sn, az) V (1.1)) |, 81
"
E
Var (VT (8h, Ra (M 0))
Var( VT (s441, O|M" Rr (sn))) |T, 81
stops
Even stops
E
Var(VV (A (a
H
E
Var (12h 0)M [T
R
Varpa 1
Noting that V (8), 0|M)) = ViT (s concludes the proof.
Finally, though not needed in our analysis, we use the extended MDP to prove the following value- difference lemma, which could be of further use in follow-up works. While we prove decomposition just using the next-step values, one could recursively apply the formula until the end of the episode to immediately get another formula that does not depend the next value.
17

---

Lemma 4 (Value- Diffeereefeeeee Lemma with Reward Lookahead). Let M1 (S, RR) and M₂ (S, H, P2, RR²) be two environments. For any deterministic one-step reward lookahead policy π E R any h E [H] and E S, it holds that
(s)MM) (s(((s
Ri h+1 1 (sh+alMM) - (84+
+ EM, Σ (Ph(o'' Ta RA)) P7 (a Ba))) h+1 (5
LE'ES
EM
(BR
Vi
Vi (sh. RMM))
BRI(S) V/2 ViRii (sh. R\M2) |sh. =
where V. (s, M. is the value at a state given the reward realization, defined in Equation and given in [
Proof. We again work with the extended MDPs M Since under the extension, both the environments and the policy Markovian, all values obey the following Bellman equations:
V2 (s, R R) (s, R)) Σ
Ph (,sssss,TTS ((. V Ol.M)), wh E [H] s S, R.M
S'ES
(s, 0s = ER, (s) 127 R.
vh E [H] SE S.
Using the relation between the value of the original and extended MDP (eq. (3)) and the Bellman equations of the extended MDP, for any h E [H]. we have
Vi v- (s|MM) - R. (s
-V f - V22 (s. M
ERI(C)) [12% (s, R)MM (R [V (s, M
(x)(s) (v2 M.) VEA (s, R.M ERI(S) VT. R[M - (x [V7 (s. R[MM
(x) [2, (s, R(M (s, R +RRI(.)
V. (s. M2) BxR(a)) Vili (s, R(Ma)
=EM, (sh: RA (M (sb, R. Mb))ss 8]
+ (RR Vi, (s, R[M2]] ERR( V/ R. ((s)))))))
(5)
We focus the first term. Denoting an (n(n RA) the action taken by the agent at environment Mi, We have
V (Sh. - Vih RA R1)M
(B)
Ba (un) + (8 (1
JES
[Rn(ar) EPh
Ph [ shi an) ) V27
FES
Σ (n
Σ
Ph (86s an V (6))
s'ES
SESS
Σ P and (V - V, (s
s'ES
Σ (P) (s' an) (5'(ss an) V2 W (s M22)
+
K'ES
= EM,
k+11 (8h41 M1) V
12. (sh, 1 an (s an) - (s ss,, an) V2 M22)
+ Σ
FEES
18

---

Substituting this back into Equation ( we have
Vi (s)
Vi' (s|
= EMi
EM1
R. ( - V (8n+11 M2)] an 180 =s
+ E.
Σ (Ph(5'(s,aa)) an) (s an) V (s' [||2))s8 = 8
LO'ES
ERI(()) (+)
(s, RMM)) (RR(()) (s.
=EMi Vilt (ntt(snt1lMi))) V/-i (s M2))s3> | =
+ EM,
Σ (Ph(s (s RA)) Ps Ssh Th(sn RA,))
Lo'ES
+ E.M, [RRR((5)
[in (V (sh. RlMa)] (RR(()) [. R.. 12 (o) =8 s].
19

---

B.3 Full Algorithm Description for Reward Lookahead
Algorithm 3 Monotonic Value Propagation with Reward Lookahead (MVP-RI.)
Require: 5 <00,
(0,1). 1), bonuses bi, (s), b (s, a)
2: for k 1, 2.... do
3: Initialize # = 0
4: for h H, H1 .,, do
5: for 8 E S do
6: if n (s)
then V = H
7:
8:
else
9:
Calculate the truncated values
V
min
k-1
max
(b()) (8, (s, (s, P (s + (s, H
11
10:
end if
11:
For any vector
E RA,,A define the policy x²
x (s, R) arg max R(a) + bg (s, + Ph- Ph-iih (
aEA
12:
end for
13:
end for
14:
for h 1, 1, H do
15:
Observe s and R₁ = { [ h a)} Play an action a ) (sh R Collect the reward R2 (sft, a and transition to the next state shi Pha ..s...... a
aeA
18: end for
Update the empirical estimators and counts for all visited state-actions
20:
end for
We use variant of the MVP algorithm Zhang et al. 202 while adapting their proof and the one from [Erooni et al. 2021]. The algorithm is described in Algorithm S and uses the following bonuses:
ALE
(s) = VV
2(m
(s)
VI
20
VVk 1 Var (-1s.a)
h+1
400
H (s, a) V
(8, a) min
nh
as
9
k n,
1445 2 and for brevity, we shorten Var (Vitt (s')) to
where 1 In
Var pe- (-l,,) 1 (omitting the state from the value).
For the optimistic value iteration, state visited at the th timestep. Thus, line 9 of Algorithm 3 is the expectation w.r.t. the empirical reward distribution R (s) (when defining its realization be zero when n, nx (s) 0).
the notation kf, (s) represent the tth episode where the
Since the bonuses are larger than H when n k-((s) O, one could write the update in more concisely as
(s)
min E ER
'Vh max R(a) b (s) + - (s. (s.00) AEA
+ (s), H
(x)
We will often use this representation in analysis.
20

---

B.4 The First Good Event Concentration
We now define the first good event, which ensures that all empirical quantities are well-concentrated. For the transitions, we require each element to concentrate well, as well as both the inner product and the variance w.r.t. the optimal value function. For the reward, we make sure that the maximum of the rewards to concentrate well (with any possible bias, that will later correspond with the next-state values). Formally, for any fixed vector E ARA,, denote
mn(s, u) ER (o)
max Ra(a) + u(a)}}.
(s. u) E ER
m (a(a) + u(a)}}
with the convention that (s, u) = max. u(a) if nf, (s) = 0. We define the following good events:
2P 2P(s'(s.a)L3
L
(k) = Vs,s',a, h: (Pa(s"ss,)) a) - (s'ss, a)l - V
+
k n
(s,
V1
k
2--1
(s,8) V
E (h)
Vs, h: ( Ph. (Px----))iit(ttad) $
Vitzi(8.)
2arr 1b
H
" (8, V1
7/h
(8, a)
V1
E (k))
Vs, Ys Varrpathaa (Vitz)) /Vrrp. (Vž+1)
S SAH,
LB
nhh
AL
(k)
Ys, h, Vu Vu
[0, 2H |mn(s,u) u) m u)] 1
$
2(n% k
(s) v 1)
where we again L In 144.² A (
Then, we define the first good event as E (k)
G E" (k)
E
E (k)
EP
1
R21
for which, the following holds:
Lemma (The First Good Event). The good event G1 holds w.p. Pr(Gi) 2 1 1- 0/2
Proof. The proof of the first three events uses standard concentration arguments (see, e.g., Efroni et al. 2021 and is stated for completeness. For any fixed h: 2 s,8,a, h and number of visits E KJ. we utilize Lemma 16 w.r.t. the transition kernel Pa(-|s, a), the value Vi++1 E [0, H] and probability 8' (SA notice that by the assumption that samples generated i.i.d. before the game starts, given the number of visits, all samples are i.i.d., so standard concentration could be applied. By taking the union bound over all n E [k] and slightly increasing the constants to ensure that n 0 trivially holds, we get that the events also hold for any number of visit n (s, a) {0..., k), and taking another union bound over all k 2 1, 8, a, h ensures that each of (I:) holds w.p. at least
the events Okzi (k), Okz1 Evel (I:) and
We now focus on bounding the probability of the event 0g E" (k).. For any fixed k, h and s, observe that the event trivially holds if n = 0, then the event trivially holds, since for all u E [0, 2
(+)
AL
mm (s, u) k x u) (n-R.()) [n a) + u(a))] - maax
- 1 3
2
where (x) uses the boundedness of the rewards in J0, 1]. Next, recall that for any fixed n2 k-1 = =n E [k],
the rewards samples at state 8 and step h are i.i.d. vectors on [0, 1]4, Therefore, by Lemma 18
AL
8
Pr
Th k- (s) = n, Vu E [0, 2H|4 A
[m,
my
m (s, w)l > $V
2(m
((s
8SAHK2 +
Taking a union bound on all possible values of n E [ki, s and h, we get
8
Pr(E (k)) 2 1 SAk
SSAH 21 8k(k 1)
By summing over all A: 2 1, the event O (k)) holds with probability of least 5/8. Finally,
taking the union bound with the other three events leads to the desired result of Pr(G,) > 1-8/2. L
21

---

B.5 Optimism of the Upper Confidence Value Functions
In this subsection, we prove that under the good event G1, the values 5 that MVP-RL produces are optimistic.
Lemma 6 (Optimism), Under the first good event G1, for all E [K], E [H] and s E S, it holds that Vr (s) S (s).
Proof. The proof follows by backward induction on II; see that the claim trivially holds for h H++1, where both values are defined to be zero.
Now assume by induction that for some k E [ and h E [H]. the desired inequalities hold at timestep h + for 8 S; we will show that this implies that they also hold at timestep h.
At this point, we also assume w.l.o.g. that V/ < H, and in particular, the value is not truncated; otherwise, by the boundedness of the rewards, (s) v = (s). For similar reasons, we assume w.l.o.g. that b (s, a) < H, so that it is also not truncated.
By the optimism of the value at step h + 1 due to the induction hypothesis and the monotonicity of the bonus (Lemma 23p, under the good event, we have for all E and that
P V (8, a) + (8,
20
Var pk-1 (11.,)
(V++t)
400
HL
2 ph 1nk
1 (s, a) + max
3
" (8, V1
9 n
(s, a) V1
2 pk- 'v--lve (3,1) + max
20
Var Parpp-1(se) (-1.,0) (Vi41)
400 HL
(Lemma 23
3
nh (s, V1
9 n
k-
(s VI
10
Var ph 10- (11,,) (1i+1)
200
HL
2 P (s)))
3
n k-1 (8, V1
n
k-1
(s, V1
10
Varpa (Vitz 1
8HL
P V (s)
(Under E
n (s,a) V1
(s, V1
h
2 PA (s.
(Under Erel (k))
Thus, under the good event and the induction hypothesis, we have that
(s) = E (
max aEA
R(a)) + (s, a) + PA 44--v6 ' Vitnlo,aa) + (()
max R(a)) + Pa PaVi (o) + (z). aEd
R~ (8)
In particular, using Proposition
we get I
(5) (s) E (R)
max (R(a))+PPVi+ia) PAViit (s) aEd
ER~RA()
max max{[((a= [(aa + Pa V (s
aEA
2
0
where the last inequality holds under the event E*(kk with u(a) PaVi E H|A
22

---

B.6 The Second Good Event Martingale Concentration
In this subsection, we present four good events that will allow us replace the expectation over the randomizations inside each episode with their realization.
Define the following bonus- liku term that will later appear in the proof due to value concentration:
{
2ar P. (-s,a)
1
SH2 (0, a) V1
(. ()) = min
H s
k- (8,a) V1
"h
and let
y Vh (5 V (5
Yg
(1ta),
Y = b (s), a + bg.h (s ax).
The second good event is the intersection of the events G2 Edittl n Ediff2 n Ear n EdP defined as follows.
K
K
+ 18H In 8HK(K + 1)
Ediff
vh Ah HH, 21:
21:
Σ
B 1,b
Fx
1
Σ
2H
1
K
8HK(K +
Ediff2
Vh E [H], K 2
FR E|y
k. 11 S
1+
Σ
Y + 18/ In
1,
211
k=1
K
H
8HK(K +1)
VVaar
K 1: Σ yk S
BYy [k-1] + 4H3
8
1=11=1
1=
K
K
SHK(K + 1)
E thE K 1:
Σ
E
EY 3,h Fk.
2 2 Yg, h + 50H² In
Am
We define the good event G G1 G2.
Lemma 7. The good event G holds with probability of at least 8.
Proof. The proof follows similarly to Lemmas 15 and 21 of [Efroni et al. 2021
First, define the random process We 11 (1) V (s) [0, HJ, [H)s E $) and define Y = W&Y which is bounded in [0, H.. Also observe that W₂ is Fk-1 measurable, since both values and policies are calculated based on data up to the episode 1, and particular, it FR.n-1 measurable and 1.h FR,A measurable. thus, by Lemma 25 for any l E [K] and h E [H], we have
w.p. at least FIJ
8 that
K
BILA EDLA < 1+
R + 18 11H
8HK(K +1)
2H
8
1==
Since Wg is FR, measurable, we can write the event as
K Σ W.a < (1+ 2H
K
W&YK 1.4 + 18/12 In 8HK(K + +1)
8
k=1
and taking the union bound over all h [H] and K > 1, we get w.p. at least 1 - that the event
iditf1 { (w [H],
K Σ W.EL
< 1
w.yk 18/1 In
8HK(K + 1)
2H
Importantly, by optimism (Lemma 6). under G1 it holds that Wt. 1 for all k 2 1, so
immediately get that G O ddiffi G n E difft
23

---

Following the exact same proof just with the filtration k and defining the equivalent Ediff2 we get that this event also holds w.p. 1 and is the desired event when G1 holds.
Next, we prove that the other two events also hold w.p. at least g.
By the assumptions of our setting, we know that Vi (s) E [0, HH. and so
Varp& (+t1)) E [0, H²
In particular, applying Lemma 25 1 SHK(K+IJ that
(w..t. the filtration Fi)) with C = H and any fixed K, we get w.p.
8
K
H
K H
4H + 8HK(K+1)
Y2,
2
E 2
F
5
km
A=1
Taking the union bound all possible values of K 2 proves that Var holds w.p. at least
Similarly, by definition, we have that V 1/g_, (sx. ax) + Todl (stt, at)
[0, 2 and is FR. 8
measurable. Thus, for any fixed & 2 and h E [H]. using Lemma 25 we have w.p. SHK(K+IJ that
K
8HK(K +1)
E E FK,
y-k 3,h
+ 50H²
3,b
4H
5
8HK(K +1)
2
3,h + 50H² 2 In
8
k=1
applying the union bound on all K 2 1, the event Exr holds w.p. 1
8
To summarize, we have that the event G1 holds w.p. 1 (Lemma 5) and we proved that the events
ediff Ediff Var, Ee hold each w.p. g. also have that the event
G G G2
G Ediffl n Edilli Var n E
= Gj ddiffl
Ediff2 n Var n Ebp
holds w.p. at least 6. 8.
24

---

B.7 Regret Analysis
We finally analyze the regret of the algorithm
Theorem 1. When running MVP-RL, with probability at least 1 uniformly for all K 2 1, it holds
that Reg" (K) S O (VHHAAAA In SAHK 52 SAHK 2
Reg"(K)
(
6
Proof. Assume that the good events holds, which by Lemma 7 happens with probability at
least 1- - 6. Then, by optimism (Lemma [). for any k E [K], h [H] and E S, it holds that (s) & (s). Moreover, we can lower bound the value of the policy x² as follows (see Remark I::
Vi" (s) (s) R(Th(s, R)) + PA h+ (s, (s, R))
R(Th(s, R)) Pi h+ (s, n (s. R)) i (f R!)]
(R)
+ +ER~RA(s)
Pr. V. (s, म (s+ R)) - h+ (s, ((s, R)) (s, R))
2 (e)
max R(aa) p V k (s, a) 62 (s,
aEd
(R)
Ph h+1 (s, n (s, R)) 1 1 (s, T R)) (s, R))
(2)
2 E R (8)
max aEA
R(aa= + - V/ (s, a) + 12 (s.
(s)
+ ERR~RA(s)
Ph Pa (8, (s. R)) - - 1h (8, R)) 1/,n t (s. R))
(3) (s) -2bE,(
ER-RM(S)
Pr. ProVat (s, n (s,
Pk- 1/ R)) b 7T R))
(6)
Relation (1) is by the definition of n. (see Algorithm 3p. while (2) holds under the good event (*) with u(a) = PK - Vh+ (s, a) + b6 (s, a) E [0, 2H] (due to the value and bonus truncation). Finally, (3) is by the definition of V% (8), where the inequality also accounts for its possible truncation.
To further bound this, we need to bound
P/ 1 (8, a) Pv PA PAVT+i( (8, Pr (h+1
vit1 (8, + (Pi-1 Ph
V (s,
Ph h+t Vitta (s,
(k-1 Ph. Vit + (px (pk-1 P.)(
(s,
The first error term can be bounded under the good event, while the second using Lemma 24 formally, under the good event E (k:), we have
More
( - (x))vi
(Va (Vi+T)
HT. (8, V1
s
n k-1
(8,a)V1 V1
"
and by Lemma with a = 4H (using and P1 = Ph, P2 = pk-1 under (k()))
(ph-1 - P.) (V) Vitz)(s,
S Ba [+++)(+') - Vi++('')] + HSL + 4H 2/4)
1
4H
k- (s, V
< Epaclen))
1
FR (s") - (o)
3/1
4H
Thp
(s, v
1
Ph. (vi. - Vi=t (8, + n, (s, (s. V1
3/12SLk
4H
25

---

where the second inequality is since the value of π cannot exceed the optimal value.
Since under the good event by Lemma 6. we have 0 I Vit1(()) I (i4+ I Vitt(60) S H, we can trivially bound the error by H and bound
p VV (s, a) - Pa PPViit1s,s
S <min (1+
Pn
Vi h+1
- Vi h+1 (8, a) + k- (s,
31
2Vrr (Ha.)) (V (Vaa) 14 D.
+
HL
H
4H
nh
Th (8, V1
nn
(s, V1
20
1
(Vaar (V 1
4H2SLY
++
Ph (Vi+1
Viita) (s, ) + +min
H
4H
T (5, n (s,
+
Ph
(V/++ h+1
(s, + bg (s)a).
4H
Substituting back to Equation 66) while writing the linear operation PA Vs a) as an expectation and letting the action be ag = n. (s, R), we get under for all & E [K], h E [H] and s that
(s) VØ (8)
Pa V (8, (8, R)) + bg (8, क ( R3) 26% Ph ( (8 R))
(R)R
Ph
(1+
(RwRa(s)
E
V. h+1 (1 V (9h41)lss = s, an (5, + Ui an) + 1/ an) + (2
417
=B
1
1
V (sh+1)) + bh (sh, + b (sh. an)ls s, x
26%
411
Next, taking s s/ the action on = R) becomes att and summing on all k. we can rewrite
V
(sh))
V/ (sh)
K
K
E
(1+ 4H/
(o (vi ( - V (oh+t))))) + 12, (sh aht + (fh:a)))Fkn-) + 2 +2Σ
1% (sh)
k=1
k=1
1
(1+ Σ
(Th ( -Vett)))-itthhht.
1
2H
4H
k=1
K
Ue + 68 In 8HK(K +1)
(gnn (5h, att + beth (5 att) +
+
5
A=1
1
1
1+
K
1 h++ (s
V + 4H
(1
1+
1
Σ
K
(1442(5h+1)) - V
Vik
2H
4H
2H
1==
k=
K
Varpa att (Vott 1
K
1620H=
8HK(K + 1)
K
18
68H2 In
+
2
blrn (s%)
Th to at) V1
(5 at) v
8
The
k=1
2 K
) w
h+t1 V (8/
Vori (
+ 18
2H
(5
at) V1
k=
SLL
AL
Σ
(5t
- V1
(s)
where inequality (1) holds when both Ediill and Fp occur and inequality (2) is by Lemma 8 In the last inequality, we also substituted the definition of the reward bonus. Recursively applying this
26

---

inequality up to h H 1 (where both values are zero), w.p. at least 1 - 6, we get
K
Reg
(K)
(i)
VI7 (sf)
k=1
(st) V/r" (ot))
(Lemma 6
k=1
K
(g (V
1700H
18
1+ 2H
+
Th (sh an) V1
2H
T1 (8% a/)
V
km
knm
2
K
ALE
+
1
+
2H
2nh (8)
k=
35 1000HH'SAK L. (L))
+ 5000H SL (2 + + 12 ALE (SH+ (SH+2VSHPK*
= -VVVISAKKL + +
Relation (*) is by Lemma and Lemma 20
27

---

B.7.1 Lemmas for Bounding Bonus Terms
Lemma 8. Conditioned on the good event G, for any h E [H), it holds that
K
K
1 (sh: + 18, (0h: oht)
-
+
1
V
(++1(()+11) - V v
8H
2H
Var (-1o% a ) V
(Vak
4+1 1
K
810113SL
+ 9
k k- (sh, at) V
Th
Proof. We start by analyzing each of the terms separately. First, we apply Lemma 22 with a 3
20.
L. noting that under the good event (by Lemma 6). 0 S V (s) S (it S 1 S H and using the event E doing so yields
Var px ((|,,a) (V 1
20
400
HL
by R (s. S
3
"h (8.0) V1
n
R-1 (s, a) V1
L3 (lrra (V
1
Ph
V h+1
Vi (s, + 32 h
(Vh.,, h+t Viti (s,0)
3 3/ 1 (x, V1
32H
6400H1 L.
20
4HL
400
H
9m (s, a) V1
3 nh
(s. v1
v1
9 nn
(s, a) V1
Using Lemma 24 with a- = 1, under the good event (K) and for any 8, a, we can further bound ( ph-1
11+1 (s.a) a)
Ph 1/hh
V (s, + (Ph-1 Ph) (5)
V (s.a)
HSL (1 + 2. 1/44)
S Ph Vh+1
Vi++1
(s, a) + Ph (viti Vitii (s,
(Lemma 24
n/ (s, V1
12 k 1.5SL
$ 2Ph (Vi++1 - Vi+t1 (s a) +
(s, V1
Thus, we get the overall bound
(s, a) 20 L3 Lar
(V+++)
h+1
3
Ph (1/(//b Vitt1) (s, + n
785
3 k (1 V1
32H
k-
(s, V1
n/
For the second bonus, we apply Lemma
21
w.r.t. VA (8) S and a 322 2T H and get
2Varpa(-ls.a) (Vi+1) L
4H2SL
6aed (s) <
Th (s
1/
2Vrrp.(1s.a) h+ )
(Vr**
16HL
4H2SL
Pr. (Vi
V (s,
1h (3,0) V1
32H
T (s, a)
Th (s, a) V1
2 2Vrr (1) (V 1 (s, a) V1
h+
vitt-viti (3, (V
2011
Pr. (1++
32H
n as V1
where we again used the optimism. Combining both and summing over all k, get
Varp, ag) (3) (va* (V
1 K
(sh att + 6 o
Ph (vi+1 Vittt afi
<
Th (0%, V
SH
K
2
- att) V
k=
28

---

Finally, under the good event Ediif, it holds that
K
K
Ph k+1 Vitta (ot1)(sh))
(5h
a
18
V
(oh+1))))
( (5+
k=1
K
(+t1())+1) Va viti(sh+1)) 18722 8HK(K + 1)
2H
A=1
Substituting this relation back concludes the proof.
Lemma 9. Under the event Vor it holds that
H
Varpa
ag) (Vir
2 HASAKL + V8SAH
k=11=1
VTh
V1
Proof. Following Lemma 24 of EEfoni et al.
2021], by Cauchy-Schwaan inequality, it holds that
K
aa (Vatt)
K
H
Var P. (v
k=1k=1
(sh
k=1h=1
n
R
(s ) V1
The second term can be bounded by Lemma 20 namely,
v S (AH((+1n(())
k=1 T
We further focus on bounding the first term. Under EVar, we have
K
H
Var Palkh.aa (V7+t))
f1
SHK(K + +1)
<
2
Var p. (15) (g) (V++1))
+ 4
(Under Ear)
k=1
4=11
8HK(K + 1)
<
2
E
Rn al) VT (o4)
[Fs-1
+ 4 In
(By Lemma 3
8
1=1
< 2H + 4 (HK(K +1)
where the last inequality is since both the values and cumulative rewards are bounded in [0, H]. Combining both, we get
SHK(K +1)
2H2K 4/1 In
(2
vhh (s% o.) V1
5
8HK(K + 1)
SHK(K 11)
2H²K 4H
2SAH
8
2 H3SAKIK + +
29

---

C Proofs for Transition Lookahead
C.1 Data Generation Process
As for the reward transition, we also assume that all data was generated before the game starts for all selii--cttiontimmssteee and is given to the agent when the relevant (s, a, h) is visited. Thus, the rewards and next-state from the first 7th visits state (or state-action pair) certain timestep are i.i.d.
Throughout this appendix, we use the notation s/+ ( (5% a)) aeA to denote the next-state observations at episode & and timestep h for all the actions, and use the equivalent filtrations to the ones defined at Appendix B.I. namely
FR. = o o (fs) aj 1141 R2 tejpp.... for- aaat s/k-1 Rr ARft""eeee heE 10b, 8 R2 BeEm)
Fk = (fs), at. s heepp...... (sf, at, of Rt) heemp .h.t1).
In particular, notice that since both o and ot are FR,A measurable, then does 8h+1
C.2 Extended MDP for Transition Lookahead
In this appendix, we present an equivalent extended MDP that embeds the lookahead into the state to fall under the vanilla MDP model, similarly to Appendix B.2] We use this equivalence apply various existing results on MDPs without the need reprove them. We follow the same conventions as Appendix B.2 while denoting transition lookahead values by (s|MM) (and again, the superscript will be omitted in subsequent subsections).
For any MDP M = A, H, P, R), let M be an MDP of horizon 2/ and state space S that separates the state transition and next-state generation as follows:
1. Assume w.l.o.g. that M starts at some initial state The extended environment starts at state $1 s/ where s E SAA is a vector of A copies of some arbitrary state Su S.
2. For any [lf], timestep 2h-
the environment M transitions from state s4. x 8/ to x 1 where + Ps (s) is a vector containing the next state for all actions E A; this transition happens regardless of the action that the agent played. At timestep 2h, given an action a₁, the environment transitions from 8 X / to s (a) x 8/--
3. The rewards at odd steps 2h- - are zero, while the rewards at even steps 2h are Rr (88, Rr (sk, an) of expectation rh. (s,, an).
As before, since the next state is embedded into the extended state space, any state-dependent policy in MT is a one-step transition lookahead policy in the original MDP. Also, the policy at even timesteps does not affect either the rewards transitions, it does affect the value in any way. We again couple the two environments to have the exact same randomness, so assuming that the policy at the even steps in M is the same the policy in M, trivially get the following relation between the values
8' E
Rd ass (h-.) s
(x,"(s,
V
H
VS (3,
(s,, = s, = =V (s Σ
(7)
While M is finite, it is exponential in size, applying any standard algorithm in this environment would lead to exponentially-ber performance bounds. Nonetheless, as with the extended-rew reward environment, we use this representation prove useful results on one-step transition lookahead.
30

---

Proposition 2. The optimal value of one-step transition lookahead agents satisfies
V (s)
vs S
V (s)
Pp(s)
max aEA
Th (n(s, V (s (s.
vs 8. [H].
Also, given next-state observations s' fs= at state and step h, the optimal policy
(3, 8') E arg max (n(s, + (d()))
aEA
Proof. We prove the result in the extended MDP M in which (as with reward lookahead) the optimal value can be calculated using the Bellman equations as follows [Puterman] 2014]
VT (8, 8' (M") = O,
Ve E
8 max (8. + 1 (5) ((1")) ( s6 M²) (x) (s, s(M"
4h E E SA
wh E [H] se S. (8)
By the equivalence between M and M for all policies, this is also the optimal value in M. Combining both recursion equations and substituting Equation ( leads the stated value calculation for all h E [H] and E S:
(s| (s|M) (s, (s.
= -E(~Ph(s)
V2 8 [
(x
max (ix((r)ss + Vi (s (4), Mb)
(g) max ()) + (4
In addition, given state and next-state observations s', the optimal policy at the even stages of the extended MDP is
22n ( 8')
arg max max((r((e (1,(8, V (a)))
aeA
alongside arbitrary actions odd steps. Playing this policy in the original MDP will lead the optimal one-step transition lookahead policy, as it achieves the optimal value of the original MDP.
By the value relations between the two environments (Vin-1 (s, s M() (s M)),)), this is equivalent the stated policy.
Remark 2. As in Remark π E II,, and not just to the optimal one, namely
could write the dynamic programming equations for any policy
V 8 M' rn(s, (s, 8 8¹)) + Vah+t (5' (s, (MI")), the E S, E SA, (8, M² Bg'-P.(o) [V2, (8, 8' [M²)]
vh [H] E.
In particular, following the notation of Equation we can write
V s'MM) (T s')) VIT
TT (s.
and,
T (slM) = -Egr~Pa(t TT: (s,
=x rh(s, (n + (i M))
notation that will be extensively used for transition lookahead.
31

---

We also prove a variation of the law of total variance (LTV) for transition lookahead: Lemma 10. For any one-step transition lookahead policy x E II",, it holds that
H S E
2
E
(V. (sh. sT)]
Σ rh an) ((7 -
1,,, 81
Proof. We apply the law of total variance in the extended MDP; there, the expected rewards either O (at odd steps) Th (5h, an) (at even steps), the total expected rewards are Σ Th (Shs as). Hence, by Lemma] 27
on) (s( an) - (51 (s1, .(1M)))))
E
|T,
H
E
Var (V2h + (sn, s6)) +
Var (8 (sh, s/1+1) |TT
Oddd steps
Even
2 R
Var (V2) (sh, Sht1lM [(8,, (6)))[T,
h=1
E
Vargr (V (Vn, 8' (MM))) n., 81
H
E
Var. Pan (V) s(IM)) 81
Using again the identity (iT 66lM²) ViTi (s1 (M) leads to the desired result.
Finally, prove a value-difference lemma also for transition lookahead
Lemma 11 (Value-Differcee Difference Lemma with Transition Lookahead). Let M₁ (S, (S, and M2 (S, H, P2, R2) be two environments. For any deterministic one-step transition lookahead policy π E IIT, any h [H] and E S, it holds that
VI (s|.M))
T (s) (s)
E.M. [r) (sh, TA (sh, 8 1/1+)) - (s Th (sh, 8/4t))) = =s]
TT h+1 (sh41 M1) )1) - V (s M2) = =s]
+ EM,
E (gw ViT (sh, s' M2) - EggweR(on) V (sh, s' [MM ssh s)]
EM,
where VTTT (s, 8 M)) is the value at state given the reward realization, defined in Equation 7 and given Remark 2
Proof. We again work with the extended MDPs MT .M and use their Bellman equations, namely,
V (s, [M (s n (s, s')) + ViLai (s' (T s')), s(l,T) th [H] 8 E S, E SA, Wh [ E.
2h- (s, () = -Er~P) (s) V (s, s' ['|MT)]
32

---

Using the relation between the value of the original and extended MDP (eq. 77) and the Bellman equations of the extended MDP, for any h [H], we have
Vi (s)MM) (
- M( 1 (8,
[g 1/2 [s s [|M Pp(e) (22 (s.ssss..)) M((M
(H
V2 (s s [MF)) (s, s' [M)) + Bg())(())
(s, [M]) Bu V2n (8, [MM
B
22 (s, s (MF) (s, s [MM)]] +.gnr
V/ ViT s|) -B V/ ViT (8, M22)
EMI V/2 (h: 8 1/11l/B MM - V2A (sh, +/ MM²) ) |/4 = s]
+ E.gg (x) V/ Thi (3, 8'| M22 - Pp V/ T (s, 8' M2))
(9)
Denoting an = (Sh, 1/1+) the action taken by the agent at environment M1. We have
V2 (sn: MhT) (sh, (11))
= (r) ax) + +1 (sh+1 (an), M() - (r7 an) + V2h+1 (an),, Mb))))
-sh, ax) (sh. an) h+1 ( Vi (o)))
when taking the expectation w.r.t. M1, it holds that s//11 = sh+1: substituting this back into Equation (9). we get
V (s (s)
= EM, Ih (sh, an) - (s, an) + vT ( - (4+T((H+ =
+ +BowPp(())
ViT T. (s. (i, s' [Ma)]] Ep())(()) V/2 1/2'' (s. (1M2)
= =EM, (sp: Th 8 (1)) (s Tn (skr 1/1+1))(s,, s]
EM,
h+1 ( (sh+1 M1)
=
RM
[gn)))()))) VT.5 (st,, MaM
E Egnn)(()))
ViT (sh, s M2) 182
33

---

C.3 Full Algorithm Description for Transition Lookahead
Algorithm Monotonic Value Propagation with Transition Lookahead (MVP-TI.)
1: Require: 8 E (0,1). 1), bonuses U (s, (
2: for k 1.2... do
3: Initialize (1)) = 0
4: for h 11 ,., do
5: for 8 E E do
6: if n (s) then
7:
(s) H
8:
else
9:
Calculate the truncated values
V/ (s)
min
max 2/- (s, (s, Vati (1 (s. ( + (6,,
11
10:
end if
11:
For any set of next-states s' E SA, define the policy n²
ss, arg max (th ( a) + (5, a) + (d
aEA
12:
end for end for
14:
for f = 1, 2. .2....4. H do
Observe s%, and 8// { 15 (sh a
16:
Play action oA = t (s 8%%
17:
Collect the reward R/, Rr (s / a and transition to the next state s = s/ ( o%t
end for
19:
Update the empirical estimators and counts for all visited state-actions
20:
end for
As with reward lookahead, we again use a variant of the MVP algorithm Zhang et al. 202 described in Algorithm 4 For the bonuses, the notation
( max (F ( + (s, V (s(
and define the following bonuses:
L k- Th
(s, a) = min
(s,
20
Var Vargw (o) (8,
400 HL
n (s)
3 n
(s) V
where T. = In 165 (M++-) and
Var "" (s) (V) (8, 8')) = =
- (Egr (V [V/ s')))² (s.,))))
The notation kt, (s) again represents the th episode where the state visited at the th timestep: in particular, line 9 of the algorithm is the expectation w.r.t. the empirical reward distribution pk- (s). Since the transition bonus larger than H when ni (s) = O, we can arbitrarily define
k-1(s)
the expectation w.r.t. p when n. k-1 = 0 to be O, and one could write the update in more concise way as
V (s) min E Ba-
(1 (s,
bL, H}.
34

---

C.4 Additional Notations and List Representation
In this subsection, we present additional notations for both values and transition distributions that will be helpful in the analysis. In particular, we show that instead of looking at the distribution over all combinations of next state s' E 8 we can look at a ranking of all the next-state-actions and represent important quantities using the effective distribution on these ranks this moves the problem from being S dimennnnnio
dimension of SA.
We start by defining the values starting from state E S, Slaaying E A and transitioning to s' E S, denoted by
(), (s) (
(8, rr( + V (s'),
(s, = (s, (s, + V (
We similarly define (consistently with Remark 2
Vi, V% (s. (s) T (s,,') (s, 8') max (s, (a))
and
(s, 8') -max (s, (a),
List representation. We now move to defining lists of next-state-action and distributions with respect such lists. Let be list that orders all next-state-action pairs from (&1(1) aε(1)) to (s (((SA)) and define the set of all possible lists to C (with [4] = (SA))). Also, define E", the list induced by function : S x A R such that u(((' a{=(1)) 2 2 (($E=<(AA)) (SA(S))), where ties broken in any fixed arbitrary way. From this point forward, for brevity and when clear from the context, we omit the list from the indexing, e.g., write the list é by (81,a1),.... (A'S 054).
We now define the probability of list elements. Denote by E the event that the highest-ranked realized element in the list is element i, namely
E ss e S :s((a)) = s and Vj < vj i')) + s/}.
(10)
Then, for probability measure P on SA, define m(ile, P) P(s' E F.). Notably, when the list is induced by u and element the realized highest-ranked elements, we can write max, u(s' (()(()))) = u(s',, az), we have that (e.g, by Lemma 17 with f(s') max. u()((a),a)
Bg maxx(u(6 ((ax) ] -E
We also denote by 2 (t) (s)vv ΣK 15 = s, shit E E. the empirical probability for a list location i to be the highest-realized ranking according to list f at state and step h, based on samples up to episode k; We have by Lemma 17 that p (ils; E) PK (E)ls) and
F. P p/- max (u(s (a)) m)]] = ( (u(s// a;)].
(Houe)))
Similarly, we will require the distribution probability w.rt. two lists - the probability that the top element w.r.t list é is and the top element w.r.t list ll is ji we denote the real and empirical probability distributions by p(i, E P) and a (1,5s; e, 8"), respectively. This allows, for example, using Lemmal 17 to write for any u, S A R.
Ex max (u(s (u((uu))) a)} max(u(s (1s (o). a
- (x (2))
E a'' (t max ((s((()). a)} - (s)
-1)) (1))
35

---

Finally, we say that a policy (s, s') is induced by lists (s) if it chooses an action such that its next-state s' (a) is ranked higher in & than all other realized next-state-actton pairs. particular, the policy x and the optimal policy x (defined in Proposition 2 are such policies w.r.t. the lists (s) and (s) - induced by V (s. s', a) and V (s, s', a), respectively. As such, for any probability measure (s), function u : S S A R and policy æ induced by list holds that Ex) s' (I(a)), (a))] (2 (u 5/ a:)].
(12)
C.4.1 Planning with Transition Lookahead
We have already seen the optimal policy is induced by list (6), and in particular, we can write the dynamic programming equations of Proposition as
Vi (s) Eg (P()) max
maxx(ra(s,on rn(s, + Vi (b
(P) (8, a:) + Vi (5' (a:)))-
Therefore, one way to perform the planning to build a list (s) of (s', a) s.t. the values
(s, , a) rn(s, a) (s')
sorted in non-increasing order and calculate the probability of any pair in the list to be the highest-realized pair:
m(ile, Ps)))) = PA(E))
= 54 and Vj < i, (/4 # st,lss = =).
In general, calculating this distribution is intractable, and one must resort to approximating it by sampling (as done in Algorithm[[] Nonetheless, if next states are generated independently between actions, this distribution could be efficiently calculated as follows:
px(le) Pr(5/+((aa)) s/ and Vj < i, s/ (a,) + ss|1sh = s)
(1 Pr(s'(as) = b and Vj < i s.t. 0j + ai (a;) + 5/,101 =s}
2 Pr(s'(a;) = s/(ss, = $} II Pr(Vj ist. aj = a, s'aa) + 55118n = =s}
açai
1- --1 Σ
(a( 0:)
II aza,
1aa= (a,=
Relation (1) holds since if 5 (a,,) s/ it cannot get any previous value of the same action in the list, so these events can be removed. Relation (2) is by the independence and (3) directly calculates the probabilities.
36

---

C,5 The First Good Event - Concentration
Next, we define the events that ensure the concentration of all empirical measures. For rewards, an event handles the convergence of the empirical rewards to their mean. For the transitions, we want the Bellman operator, applied on the optimal value with the empirical model, to concentrate well, and we require the variance of values w.r.f. the empirical and real model to be close. Finally, the empirical measure it (1. j|s; f, f% (8)) must concentrate well around its mean for any list l this will allow the change-of-measure argument described in the proof sketch.
Formally, define the following good events:
L V - (5
[s) (A) Vs (ma(s,a) - "s, S
(A)) = (a
|Ab pph (t.5)1)))))) - (T() Ph()))
4SAL (1, (s);
2
1 (s)
n (s) V
2Var PI (, (5, 88)8
H
hs
S
14
(5)
(s)
V1
n1. [0] V1
LB
(k)
hs : (Var / (V (s,
S 4H
(s) V
where we again use I. = In 165 (3+11
We define the first good event as
G1 n E
(k)
E
(k)
E (k)
E
A21
A21
R21
121
for which the following holds: Lemma 12 (The First Good Event). It holds that Pr(G.) 2 1 1--1-87 8/2.
Proof. We prove that each of the events holds w.p. at least 1 - 6/8. The result then directly follows by the union bound. We also remark that due the domain of the variables and their estimators (e.g.. [0, 1] for the rewards), all bounds trivially hold when the counts equal zero, so w.l.o.g.. we only prove the results for cases in which states/state-actiie
were already previously visited.
Event Ox21 ET (A.). Fix & 2 1, a, h and visits n 2 1. Given all of these, the reward observations are i.i.d. random variables supported by [0, 1]. Denoting the empirical mean based on these samples by fx (s, a, n), by Hoeffding's 's inequality, it holds w.p. (6+T
8 that
165AH12(+1)) 3
D
(r a) (x a,s,a,n, n)l <
2n
Taking the union bound over all n E [k] at timestep k get that w.p. 1 ASAHA(++))
LB
(n, p/ k- (s, -
A (s, v1 n
and another union bound over all possible values of s, a, h and l 2 1 implies that Ex21 (k) holds w.p. at least 1 - 5/8.
The event 2 1 (k). For any fixed k 2 1, h. list E E L and number of visits n E [k6], we utilize Lemmal (event FP) w.r.t. the distribution μii (s), P) (whose support is of size M = (2)
When applying the lemma, notice that given the number of visits n 2 1, the empirical distribution
Al k (i. jls: f, (s)) is the average of n n
k-1 (s) i.idd samples, so that for all i,j E [SA].
2u(i, (s)) In A(S
In 2(8
A (1.11: (...) $
3n
(,):) (h() 28A
2
28A
8
n
37

---

w.p. 1 8' Choosing 8' (((1SHR*(+11) (such that In 25A 8 S S In 165 A since
[2] S (SA)SA), while taking the union bound all n E [b:], all 8, h and all lists & E L implies that Ok21 (k) holds w.p. at least 1
Events Nkz1 (k) and Ous B (ke). We repeat the arguments stated in Lemma 5 For any fixed k 1, and number of visits
[k]. utilize Lemma w.r.ttt the next-state distribution for all
actions (s), the value (s, s') [0, H] and probability 8 (5H1" yet again remind
that given the number of visits, samples are i.i.d.
As before, the events D221 F (k) and C=21 F hold w.p. at least 1 through the union
bound first on n E [k] (to get the empirical quantities) and then on s, h and h 2 1. This proves that
each the events G holds w.p. least 1 g. so G holds w.p. at least
38

---

C.6 Optimism of the Upper Confidence Value Functions
We now prove that under the event G1, the values that MVP-TL outputs are optimistic. Lemma 13 (Optimism). Under the first good event Gr for all k [K] h E [H] a A and 8,8' E S, it holds that Vi (s,8', , a) S V8, (8, 8. ,a), Moreover, for all s' E E (s, s (s, and also (8) S (s).
Proof. The proof of all claims follows by backward induction on H; the base case naturally holds for h H where all values are defined to be zero.
Assume by induction that for some & E [K] and
[H] the inequality 1 (s)
V A++(3: (s) holds
for all s E S; we will show that this implies that all stated inequalities also hold at timestep h. At this point, we also assume w.l.o.g. that V/ (s) H (namely, not truncated), since otherwise, by the
boundedness of the rewards, V2 (s) S H V (s). In particular, under the good event E" (k)), for all s and a it holds that 1%
14--1(s.. as. + (s, a) 2 rn a), so for all s, a and s', we have
V (s, s', = ( 1/ (s. a) + V 2 (s a) + V*+1 = V (s,
where the inequality also uses the induction hypothesis. This proves the first part of the lemma. Moreover, it implies that
(s, = max aEA
aEA { V (s, aa) 2 (s, (s), = (s,
(13)
and proves the second part of the statement.
To prove the last claim of the lemma, we use the monotonicity of the bonus, relying on Lemma 23
This lemma can used when applied to the empirical distribution all possible next-states p (s): indeed, the non-truncated optimistic value can be written as
V
E B P())
max Ph
(ssaa= + (3, + V (s))) + + (s)
Var Va (4)) (V s 8')) 400 3HE
20
2 E pt- (s, + max
3 V
" (8)
n h- (s) v1
which exactly the required form in Lemma 23 w.r.t. the distribution (s) and the values
V (s, 8') (while noticing that due to the truncation of values and bonuses, (s, 8') E (0,3H). Thus, the lemma guarantees monotonicity in the value, so by Equation (3))
Var g (6) (V (s,
1
20
100 3HL
(s) 2 E. (8,))')) max
n (s)
9 (s)
10
Var pe (w) (v,
200 H
2 E B (m) (s,
3
n (8)
3 n
(8) V
10
Var (h( (V) 8'))
50H L
2 (x- 1V (s.
(Under E (k))
31
(8) V1
m (s) V
2 (h
(Under geel (k))
(s).
39

---

C.7 The Second Good Event Martingale Concentration
In this subsection, we present three good events that allow replacing the expectation over the randomizations inside each episode by their realization. Let
1,A = 1 V (+t1())+1)
2, = Varg (V (sh.
3.6 ( af)
The second good event is the intersection of the events G2 = Ediff n E n E defined as follows.
K
K
6HK(K + 1)
Ediff
vh
H K21
FRAA-1) - 11
1. + 18
2H
6
k=1
R=1
H
6HK +
Var
K> 2 1: Σ 2,h
4H In
8
K
K
6HK(K + 1)
Edr
Ah
E|y F
1] 2 2 y-k + 18
8
k=1
We define the good event G G1 GG.
Lemma 14. The good event G holds with a probability of at least
Proof. The analysis of the first event follows Edift exactly the one of Ediffl in Lemma 7 define WE = 1 ()) V (s) E [0, HJ, vh E [H) E { (which happens a.s. under G2 due to the optimism in Lemma 13 and truncation) and Y Wi,Y,, which is bounded in [0, H] and FR,A- measurable. The corresponding event w.r.t. this modified variables Editf then holds w.p. Lemma 25 and as in Lemma 7 part of the proof.
by use the fact that G1 O Ediff G1 Ediff to conclude this
Moving to the second event, since V,," (s, 8') E [0, H). then Σ/ Y E [0, H Therefore, by (w..t. the filtration Fi)) with C = H and any fixed K, get w.p. 1 6Hк(K+1)
Lemma 25
8 that
6HK(K +1)
E BY 3
8
Taking the union bound on all possible values of K 2 proves that Var holds w.p. at least
Finally, by definition, we have that 3,h = b% (s) a E [0, 1] and is measuraaee,. Thus, for any fixed l 2 and h E [H), using Lemma 25 we have w.p. GπT that
K
6HK(K
Ysh + 18 6HK(K
PR <
yk 18
so that due to the union bound, Ebr holds w.p.
To conclude, G2 holds w.p. 1 (Lemma 5 and the events Edifll EVa Ebr each hold w.p. 1- As before, when accounting to the fact that Editf and Ediff are identical under G1 the event = G nG holds w.p. least 1 8.
40

---

C.8 Regret Analysis
Theorem When running MVP-TL with probability least uniformly for all K 2 1, it holds that Reg s O (VH'SK V+++VA VA) In SAHK
bo H A SAN
Proof. Assume that the event G holds, which by Lemma 14 happens with probability at least 1 1-6. 5. In particular, throughout the proof, we use optimism (Lemma [3). which implies that
S VI," (s, 8') S (s, s') S V (s. 8') S 3H (the upper bound is also by the truncation), as well as 0 S VE (8) S (s) S (s) < H.
We first focus on lowerinounding the value of the policy ,² by Remark 2 we have
VØ (s) Ev/ (a) (s mh s')) + V (s' (s)))
(+) P
(8, (8, + v
+ 1 (e,
(8 p (s,
F. (.()))))))
(
V
Eg Px(e)))
max - //
aEd
+ -. (r
, (s,
(s, 8'))]
+ E (.)
(5
V/
2 (s) s') - 2E, be
-. ( (Th s' ( Vs
where (1) is by the definition of x and (2) uses the reward concentration event. Thus, we can write
V/x(s) (s) V (s) S E A (s) [1/ (s. s')] Ex [V s')] + 2E [h (s, (his s'))] 1/ W (s' (T) (s, ())) Vi ( )1)) + (8)
Ex')Ph(s)
Ey B (0) [ (s, V/7 s')] Egwe)() (s, (s, 8')] + (s)
Bg (8, Bar ( (8,
+2 P (s, ((s,
Eg(o) Vit (s (T) s'))) (s' (
(14)
Bounding term (ii): using the concentration event (k), we have
2 2Vrr Pa (V (s. 8'))
H k
(11)
n (s) V1
vs)
The
wn
2 2Vrr (VT (5)
4H
HI.
Es Ph(s)
V (s, - (s, +
m (s)
8H
n -s) V1
n (s) V
I
2V PVar (VT"" (s, 8')
5
E. Px()) [// (8, V (s, (5) + n (s) V1
(1)
8H
(s)
(15)
Relation (1) uses Lemma 21 with the values S V. (s, S (M s') S H with a 8H V21. and (2) is by optimism.
41

---

Bounding term (i): We first focus on the transition bonus; to bound it, we apply Lemma 22 w.r.t.
(s'ss, (r (n(')) the values 0 - V (s, 2 (s, z (s, s') S 3H (by optimism),
under the event E and with a = 8H-
20
v L3:
3
20
Var Ph- (V/ (s, $')
400
HL
1/ (5)
3
h
k- (8) V1
3
k- h
(s) V1
1 8H
Vi (8, (8,
E. (o)
(s,
8H
20
Pa Viat (s. 8
1600
20 4HL
400
HL
+
3
n (s) V1
3nd
(s)
3 Th (s)
3 m (s)
P (8) [1 [/, (s, - (ss - -EginPa()) V% (s, - (s $1]
B
8H
20
Var (s (s) (V+** (s, $')
700H2
+
Px V/+ 5') -vm (s, 8')] +
811
3
nh k- (s) V1
n (s) V1
Substituting back to term (t), we now have
(i) S 1 +
1
[ (Ba- (0) [8 - (v)(,,'') - Par [ V/ (s,
8H
20
(ar (Vi'' (1,8)))
700
8H PP) (s, - V s(]
3
" (s)
" (x)
The next step in the proof involves bounding the first term of (i). At this point, we remind that both values can be written as V (s, 8') = max, V2 s'(a), a) and V os) = max. V s((a), a). inducing the lists E = (5) and 8 (s), respectively; thus the expectations can be written as (see Appendix C.4 for further details on the list representation, and in particular, Equation III):
B '(0) "6) (s, - (s, s')] E. ( (s, (s,
@ "15aa((1dd V/ s ano Vi (6)
77 $/00 an))
V/ (s. (5. (r
22)
((( 8H 4SA/4) n V1 V1
1/ (8. 10) ) - VV 5 6- -c
8H (1.
2 1
30FF
8H Ee (8, (s,
" (s) V (5
1
E. PP (1 V ( (1)
811
2/ (s)
Relations (1) formulate the expectation using the list representations and backward, as done in Equation 11 For inequality (2) we rely on Lemma 24 with a = SH under the event E*(k) and the optimism, which ensures that the value difference is bounded in [0, 3H]. We also remark that the support of the distributions is of size (SA)?; were we to use the same result on the distributions
ph (s) and (s). the support would be of size S.A, which would lead to an exponential additive factor. And so, we finally have bound of
3 8H E. Ex-rn (V)(,, V²"" (3''(,,'))) +
20
Var Mar (s) (V.* (s, 8')) R
7 (SA) L n k-
(i) S
3
n
(s) V1
(s) V
(16)
42

---

Combining both terms. Substituting this and Equation [5] into Equation
14
we have
1 (s) Vi (s) By Ph. (1)) (s, + +
Var P. (V. (8,
(5A
2H
k (s)
Th (s)
Pp) Th(s, s')] + Earo
[ (= (())) - val ( ('))]
and further bounding (using the concentration event (*(k)
(s, - (8, = ph (s, 8') + b (s, & &'))
- - ( S (
v (o 8'))) 2 (8, (f,,
we finally get the decomposition
(s) V (8)
1
E. Bg
Vhh (= (=
2H
750H Varg (V,"" (5,
m (8) V1 + +3Eg'
(b
16 (8, (1s, ( ()))
(s)
At this point, we choose to take s = , and sum over all l E [K]: specifically, for s' = s the action becomes ( s') = a and s' (s, = sh.- Formally, we can write the bound as
K
K
(b V (sh) S
1 2H
Vk (
Varg' (Vi'" 8 Th R-
+ 3
E B (8) a. 1 +
(sx) V1
K
750H (5A)31}
+
nh (s)) V1
and, in particular, under the events Ediff and Eor it holds that
K
(
V (6t) s
1+ 2H
Σ
K
V (sh+1))
V v + 36H22 In
6HK 1)
8
k=1
6HK(K
+ 3
bh (sh a + 54
8
k=
K
Var Vargr~Pace (o (VT" (s 8')
K T50H)
+ 9
n (s/) v1
n (
43

---

To conclude the proof, we recursively apply this formula from h to h = H + (where the values are zero) and use the optimism. This yields
Reg' (e)" =
(()) ViT"((h (s
K
<
(s() Vi (0%)
(Optimism)
k=1
(1)
2H
K
H
Var (e (VA" (5h 8'))
1+
2H
T (st) V1
Jem hml
2
K
T ( VI
1
2H
2H
K
LSA
2H
6H
(K
1)
1+
900 1+
In
2H
Th
V1
2H
5
==11
50VHASKL 50V (L.
+ +9/L% SAH 4AM + 2 L (2 In(K)) + 2
= (VH
(V V L3
A
Relation (1) is the recursive application of the difference alongside substitution of the reward bonuses, while relation (2) is by Lemma 15 and Lemma 20
44

---

C.8.1 Lemmas for Bounding Bonus Terms
Lemma 15. Under the event Var it holds that
K
H
(P (V7." (sh) s'))
2 H3SKL + V8SH
v+
Proof. Similar to Lemma 9 we again rely on the lookahead version of the law of total variation to prove this bound. First, by Seuchy-Schwand inequality, it holds that
K
H
Var Va (VE" s')
K
K
Var Varg'~ a Ph (V/5" (V (0% (5%
nh (s V1
n
(5
k=
Am11
A= A
R= P=
We use Lemma 20 to bound the second term by
ΣE
T S (H((2+n((K)
1 Th [5
and focus on bounding the first term. Under Var we have
K
Var Var (, (VT s'))
Pm
6HK(K + 1)
Var Parg:~Pa( (sh, 8')1
4/13 In
(Under Var)
k=1
2
6HK(K + 1)
E
Σ ( att VI (ot)
|Fa-1
+ 4 In
(By Lemma 10
< K 6HK(K +1
5
where the last inequality is since both the values and cumulative rewards are bounded in [0, H). Combining both, we get
K Var Va PPtt)) (V (0%, 8'))
6HK(K +
2H²K 4H3
(2H(2+In(X) In(K)
8
(5h) V1
2HP + 4H 6HK(K +1)
6HK(K +1)
2SH
8
8
22 HPSKL VSSH
45

---

C.9 Example: Value Gain due to Transition Lookahead
Q1
01g..ry
w.P.
W.p.
W.D.
w.p.
y=1
02g 9A
02. 1.. 0.A
w.p.
I
w.p.
w.p. x
y= 0
01 AA
Figure 2:
Random chain: agents start at the left side and must reach its right side to collect a reward.
We now present in further detail the example described at Section 3 This example inspired by the one in Appendix C.3 in Merlii et al. 2024). greatly simplifying it and achieving similar behavior for a much smaller environment.
Agents start at the left side of a chain of length H/2 (depicted in Figure 2 and have two options:
1. Play safe action a that leaves the agent in the same state (in green), or,
2. play one of the A- risky actions a2, a (in red). Each these actions moves the agent forward in the chain w.p. x but leads to terminal non-rewarding state w.p. 7-T
At the end of the chain, the last state is an absorbing state with a unit reward.
Without lookahead, all agents can do is try to randomly reach the end of the chain, succeeding with probability (A 1)-1122--- In particular, such agents cannot collect more than V'o < H(A - 1) 1)-H/2, On the other hand, with transition lookahead, agents observe whether the risky actions allow moving forward in the chain or lead to the bad terminal state. If one action allows progressing in the chain A-1
(which happens w.p. p
(1-
1 1//)), lookahead agent would take it, and
otherwise, they will use a1 to remain in the same state. In other words, optimal lookahead agents reach the reward after //2 successful 'progression steps' with probability p each. The probability of reaching the end of the chain using less than 5//6 steps is at least
Pr Bin
1, 111 1-11-1112
Z Co. for some absolute co >> 0.
6
Under this event, the agent collects Oo rewards, the lookahead value is at least VT, > coff
6 = Q(H).
To summarize, for this example, no lookahead optimal value is most HA HA-H/2 H/2 while transition lookahead agents can collect a value of z H: transition lookahead increases the value by an exponential multiplicative factor. The difference between the two values is GT Q(H), and following the discussion in Section 3, a sublinear transition lookahead regret would imply a negatively linear standard regret of Reg( () S --
The chain length was chosen to be H/2 for simplicity - similar conclusions can be achieved for length of ze 1 1/c. Then, the multiplicative increase in value due transition lookahead would be ze (A - ()(-)))) matching Proposition 2 in Merlis et al. 2024 In fact, setting the transition from the last state of the chain to the terminal state (rendering possible earn only one unit of reward), the analysis coincides with the one in [Merlis et al. 2024]. Following their exact derivation, the value with lookahead information is multiplicatively larger than its no-lookahead factor by exponential factor of θ ((A m) (1 (1-))==-,,3--) This significantly improves the
Remark 3.
result in Merlis al. 20244, that only holds if 2 111
46

---

D Auxiliary Lemmas
In this appendix, we prove various auxiliary lemma that will be used throughout our proofs.
D.1 Concentration results
We first present and reprove a set of well-known concentration results.
Lemma 16. Let P be distribution over discrete set X of size [ = M and let X, X1,..., Xu be independent samples from this distribution. Also, let U X [0, C] some > 0 and define the empirical distribution (x(z) = 1 + 1fx, = x}. Then, for any 8 E (0,1), 1). each of the following events hold w.p. at least 1 8:
2P(x) In
2M
2 2M
E
Yor E X, (P(x) P.(x))
+
3n
Σ (P((x) P(x)) P(O)) S
2ar p (U
2C' In 3n
à
DEN
In 3
E
V Varp, (U(X)) V VVrr(U(X)) S <4C
where (U()() = Exex P(x)U(t)) (EEEx ((x)
Proof. All the results require standard probability arguments and are stated for completeness.
For the first event EP, notice that each of the components (x) is the empirical mean of independent Bernoulli random variables X, (xx) of mean P(æ). Therefore, by Bernstein's 's inequality, recalling that the variance of the variable Ber(p) is p(1 - p). we get w.p. at least 37 that
PP(x) - PP))) 21(x) - P(x)) In 2M
21n 2M
2P(x) In
2 2M
+ 3n
n
3n
Taking the union bound over all x E X implies that E holds w.p. least 1 8.
For the second event gre1, we apply Bernstein's inequality on the variables Y; = U(x)). The empirical mean is given by Y, 1/2 E(X,) Exex Pa (x)) and its average is E[[]] Exsx (x)). Similarly, the variance of the random variables is Var(Y' = (X)) Thus, by Bernstein's inequality, w.p. least 1 5,
2Var
20 2
Yx E| S
3n
Stating the bounds in terms of X, leads to the second event.
For the last event, follow the analysis of [Efroni et al. 2021 Lemma 19), which in turn, relies
[Murrer and Pontil 2009 Theorem 10]. Define V,, 2n(n-1)
2ij (U(X)) U(X)))² This is
well-known unbiased variance estimator, namely, [[[]]] = (ary(U and by [Maurer and Pontil Theorem 10], for any d it holds w.p. at least 5 that
2009
2 In
Vv, Varp(U(X]) < CV.
n
where we scaled the bound by C' to account for the values being in [0, CJ.
47

---

Next, we relate V to the empirical variance. By elementary algebra, we have
Vn 2n(n
(U(X)) -Xx)))²
W-=
Ux+)²
1
EU(X)U(X,)
T(n - 1) itj
"
U(X)²² (n- ( E. EU(x))
2
" U(2)²
n(n - 1)
( (E
Σ EuXx))
(L))U()))
+
U(X,)² n²(n 1)
n(n 1)
TEX
TE
The first two terms are exactly the variance w.r.t. the empirical distribution; therefore, using the inequality |vā vol & Vla- bl for positive numbers, we have
VV V Varp, (U(X)) <
n(n 1) Σ U(X)²
Σ
U(X))
C²
n² 1)
Combining both inequalities and recalling the trivial bound of C on the difference, we get that w.p. at
least 1 8,
21n
C
In 3 n nvi
V Varp, (U(X)) VVarp(U(X)) < min C
+
Vn-1.-
C
< 40
n n-1
n-
Next, we present a short lemma that allows moving between different spaces of probabilities.
Lemma 17. Let X be a finite set and let .I...., Xn, E X. Also, let E1...., ... Em X' be a partition of the set X, namely, for all i # j. E, &.n E, = 0 and L E, = X. Finally, let f X + R such that for all [m] and E E., it holds that f(x) f(i), and define
(x(x) = 1(x= =x), x}, and, Qn(1)
1(x
n
t=1
Then, the following hold:
1. (1) = :P.())) E Pa(x) and, in particular, B ,, [[()] B p. [S(z)).
2. If P is a distribution over and XI...., Xn E X are iid. samples from P. then E(Q,..1) = P(E,) Q(1). It also holds that Ex = En-off(i)
Proof. For the first part, have by definition that
1 n (i)
Σ 1(xe e e
2 1[x==2111 E,} Σ Px(x)1(= E.)
1xx=
n
ZEX n
Σ P
ZEE,
In particular, it holds that
m E E, [f(1] = Σ (m())))== m
m
Pa(x){() 11)
PEP 2 Σ (x))f(()))
i=1 FEE,
TEX
= E Em _ [f(z))
48

---

where (1) is since f is constant inside E, and (2) is since {Ei partition X.
For the second part of the statement, notice that since the samples are i..d., it holds that Pa(a))
P(z). and therefore.
(1) =
Σ
Pa(x)) = Σ
P(F.) Q(1)
LEE:
sEE.
Finally, as in the first part of the statement, it holds that
m
Enolf(1)= Σ (00()) Σ
Σ E P(z)f())
Σ Σ P(z)f(z) (())(()
-Ez-)ff(r))
Finally, we present two specialized concentration results that are needed for reward and transition lookahead, respectively.
Lemma 18. Let X, X1,.... Xn, Rd be i.i.d. random vectors over [0, and let C' be some
constant. Then, for any 5 E (0, 1), with probability at least 5,
d dln 9Cn
Yu E [0, cT
E
max (i + u(i)} Lied
max Xe(i) + uu() EE|
S <31
2n
Proof. Denote m(u) E [ma (X + u())}] and m(u) Σ maxield (Xe(1) + u(t)) and fix any E [0, Cl Since the variables are bounded [0, 1]. their maximum is bounded almost surely in [max; u(i), max; u(i) + 1]. namely, an interval of unit length. Therefore, by Hoeffding's inequality, for any 8 E (0, 1), w.p. 1 8'
In ch
Im(u) m(uu)= S V
2n
Now, for some (0, C), let u, be the closest vector grid {0, 26, C). Then, clearly holds that
(m(u) - m((u) s (m(ue) mn(u)) + 2c.
Taking the union bound over all ( + 1) possible choices for u. and fixing 8'
([$]-1)a we
get w.p. 1 - 8 for all u that
dn
(m(u) m((u) s
+ 2c S
ca
+ 2c.
2n
2n
Now, fixing V
dlu oc
and noting that
1 S /2n for C' 2 1, get
d BCv/2n
dn
6C
dln
9Cn
6C dln
d 9Cn
mm(u) m((u)) $
+ +21
o
8
2
3
8
2n
2n
2n
2n
2n
49

---

2mdln 6C Lemma 19. Let LetX,X, X1....... Xn, E Rd be i.i.d. random vectors with components supported over the discrete set [m] and let C be some constant. Then, uniformly over all u E [0, C1am w.p. 8:
E
max(u(X(()),))
2md In on (ar[max, (x(X 8Cmd (In En 1.5
5)
n
n
Proof. We follow similar path to Lemma 18 and covering argument. Denoting w(u) E ( and ((x) = Ex=1 max; (()))()))))) 8)}. by Bernstein's inequality, for any 8' E (0, 1) and fixed a E [0, Cjamm it holds w.p. - 8' that
(aar(max i)) 2 2C 3
(w(u) - =b(w)) V
(17)
n
3n
Now, for some (0, C), let u, be the closest matrix grid (0, e, .e,...; C) md and denote (u) max; (xXx((((X(i)) } with samples (u). By the smoothness of the max function, it holds that
[z(u)= Z(ue) S.
In particular, we also have that
[E) [[) 2² + 2Cc,
and
( E[Z(u.]] S 22 2
so we have
Var
Var ux Var((Z Var(Z(u.)) S 22 + 4Ce.
Similarly, it holds that
[u=(u) - [()) S (w(u,)) - (uu)) + 2E.
Taking the union bound over all ( + 1) we get w.p. 1 5 for all that
md
possible choices for u. and fixing 8' (
2 Var(max, (ar(maxx(uu (u.()((), +[[]++1) nd
2C'n (1]
[w) w((u)
+
3n
2mdVar (u, (X.). ())
2Cmd In
+ 2c
n
3
es (ane0mmax;(((((((( ()) 26 + 4CC)
2Cmd cb
+ 2e
3n
2md In Var(max, (((())
SmdC'e In 6C e8
Amde2 cb
co
+
6C 20md In
of 2c.
3n
Cln op and noticing that 6C S we get
Now, fixing c
lm 6n
+ V8mdC'n 6n
V4mdC (In 6n
lw(u)= v((u) S
115
n
n
2n Gn 5
2n 4C 5
+
3n
2m
6n Var(maxx (acixxx(u(X(X) (u(X
8Cmd 6n) 1.5
50

---

D.2
Count-Related Lemmas
Lemma 20. The following bounds hold:
K
K
S SAH + SAH*K
I S2H + In(K)),
k=1k=1
(5% a/) V1
k=
h=1
( a
V1
K
H
K
H
S SH +2/SHPK
ΣΣ
S SH + In(K))
1/ (s
Proof. Recall that every time a state (or state-action) is visited, its visitation-comm is increased by 1,
up to nh K K-1(Ks (s, a) at the last episode. therefore, we can write
1 = s = a}
1 (0h a V
n/ (s,
aEAk
K (s,a)
Σ ViVI
N=1 aEA
1+2 mh (8,
A=18ESaE4
H
< SAH +2
SAH Σ 1m1se8
Σ aEA
T
K - (Jensen's 's inequality)
S SAH + 2V SAH'K.
where we bounded the total number of visits by the number of steps HK. Similarly, we also have
K (s.a)
ΣEΣ
(5 an V1
iVI
h=1 SES aEA
e (s,,a & SAH(2 + In(K)).
<ΣΣ
In+
h= aEA
We can likewise prove the inequalities for the state counts as follows:
1 =
n
(5)
1= BES
k=
A
(s)
H
VIVI
h=1
SES
1=0
H1
1 1+ 2 n (s)
SES
SH H
< SH +2,
T1
(1)
(Jensen's 's inequality)
h=
SH + 2VSKHKK
and
K Z
(s)
ΣΣ
1
ΣΣ
1
S ΣΣ
(2 In( -s)) & SH + In()))
h=1
Th
k-
SES
i=0
iV
SES
51

---

D.3 Analysis of Variance terms
Lemma 21. Let P be distribution over a finite X and let X P. Also, let V1, V22 : x [0, C7
for some C' > O such that (1(x)= S (2r all x E X. Then, for any a, n > 0, it holds that
(Varr(V((X)) vn
(Va))(V((X)) vn
+ E - + Co
4n
Proof. By Lemma 26
we have
Varr(V2(X)) - v Varp((V(())) & (Varp(V((X) - vi()))
I <Vp((VV(X) (X))
S VCCTp[VV2 (V2() - [i()
where the last inequality is by the boundedness and since Vx(x)= & V2(2). Thus, we can bound
(Var((2(X)) Varr (V(())
vn < / Vi(X)]
vn
VBP(V((X) Vi(X]]
n1
Ca
$ Ev(V((X) [i(X)
4n
where last inequality is due to Young's inequality (ab - a + b² for all 0).
Lemma 22. Let P. P' be distributions over finite set X and let X ~ P. Also, let V1, V2, V3 : X + [0, C) for some C > such that Vi (x) S V2(x)) S Va(x) for all E X. Finally, assume that
p (V2()) - / (V
8
for some B > O. Then, for any a, > 0, it holds that
Varp (Vs(X))
(Va
Epr BP. [V3(X) V((X)] - EV V1(X)] +
1
Ca
B
+
Vn
Vn
a
a
2n
Vn
v (Vr)(V((X))
Ca
B
Ep V3(X) - [X()] + Ex(Vs(X) - Vx(X) +
+
Vn
2n
Vn'
Proof. We decompose the l.s.s follows
(V(X)) VVar (V2(X)) (V2())
(Vr((( Varp((V(XX)
Vn
V
Vn
Varp Varp(V((X))
VXx)((V((X))
Vn
Vn
We bound the first and third terms using Lemma 21 and bound the second term with the assumption and get
Varp
(V)()))
Ca
B
Ep - +
Vn
4n
Vn.
Er((( vx(x)] + Co
(Var((V(X))
4n
Vn
Narp((((X))
+ 1 Epr [V((X) - Ve(X)]
1
Ca
B
-P - V((x)) +
+
Vn
a
2n
Vn
(arr(Vi(X))
Ca
B
Ep V3(X) - vi(x)]
Ex(VV(X) Vi(X) +
+
Vn
a
2n
Vn'
where the last inequality uses the fact that Vi $ V2(x)) < VV(x) for all X. The last two bounds are the desired results.
52

---

E
Existing Results
Lemma 23 (Monotonic Bonuses, [hhang al. 2023], Appendix C.1). For any p A E R s.t.
|| - H, 8' E 10) and positive integer define the function
20
Var (1) Var, In
400
H
((p,u,n) p" max
8
n
n
Then, the function (p, n, is non-decreasing in each entry of Lemma 24 (Efroni et al. 2021, Lemma 28). Let Y E R be vector such that 0 S Ys()) S H for all S. Let Pi and P2 be two transition models and TRSA If
(1 n(s,a)
C2
((s,a,s)) ESx
H]: (2,n('(ss,a) (1)
n(s,a)
for some C1, 0, then, for any a >
+ HSSL + aC1/4)
[(PIA - P2,x) (s, -
a(s,a) V1
Lemma 25 (Efroni et al. 2021 Lemma 27). Let {Yitt21 be real-valued sequence of random
variables adapted to filtration (Fi) Assume that for all 2 it holds that 0 Y, S C a.s., and let T E N. Then each of the following inequalities holds with probability greater than 1 - 6.
(1+
1 2C
Σ
Y, 2(2C +1 8'
T
CY E 4C 1
Lemma 26 (Standard Deviation Differences, e.g., Zanette and Brunskill 2019 lines 48-51), Let P E Ad be some distribution over [d] and let V1, V/2 E R.. Then, it holds that
Varp VVrp((V)) Varp(Vi V2).
Lemma 27 (Law of Total Variance, e.g.. Zanette and Brunskill 2019 Lemma 15). For any lookahead policy n, it holds that
H
F
2
Var(V (#n+ (8)))
Σ
rn (Sh, an) (n)
- VT((s)) T 81
where Var(V hh (Sn+1) (sh) the variance of the value at step 8h41 given state 8,, and under the policy due to the policy randomization and next-state transition probabilities.
53

---

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, we accurately present the setting and its motivation, as well as a summary of the results, all of which are 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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The main limitations in this work are result of the studied setup some possible extensions and improvement are discussed in the future work section.
Guidelines:
The answer NA means that the paper has 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 a 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 (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn 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 on few datasets or 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 low or images are taken in low lighting. Or speech-to-tex, 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
54

---

Answer:
[Yes]
Justification: Proofs for all the stated results are provided in the 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 or referenced in the statement of any theorems.
The proofs 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 complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be 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 affects the main claims and/or conclusions of the paper (regardless of 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 dataset and/or model, the authors should describe the steps taken to 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 be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
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 new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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 open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome 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 (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
55

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
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 NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccipps.c/puulli//guu /tte:///uuddde/oooSuuubbmiibia ssionPolicy) for more details.
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 omitted from the script and why.
At submission time, 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 (c.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 of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or 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, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
56

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error 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 out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not 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 rums as well as 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 the paper conform, in every respect, with NeurlPS Code of Ethics https htttps://neurpppi wwterippp.ccpppppp http://www....pppppp/..cacaaaaaa htt.bliic/hhhcccsuddeeeeesss
Answer: [Yes]
The paper is purely theoretical and studies a fundamental decision-makinn model; any ethical issue that might arise would be a core issue in the ethics of applying machine learning, and not tied specifically to this work.
Justification:
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: Due the theoretical nature of the paper and the generality of the model, is no direct societal impact.
Guidelines:
The answer NA means that there is 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.
57

---

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).
11. Safeguards
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)?
Question:
Answer: [NA]
Justification: No data or models are released with this paper.
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.
58

---

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 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 new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/model as part of 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 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 as 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 in 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 in the main paper.
According the NeurIPS Code of Ethies, 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 an equivalent approval/review based on 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 on 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
59


Reviews:
[{"review_id": "Fd9g1CgGfS", "reviewer": "Reviewer_MArZ", "summary": "The paper studies an RL problem with a special setting, called one-step lookahead, where the agent can observe the reward or the state at the next step before the current action is taken. The paper focuses on the problem with an unknown environment (transition function). The authors proposed an efficient algorithms leveraging the empirical distribution of the lookahead information and claimed that the algorithms achieve tight regret against a strong baseline.", "questions": "1. When the agents have access to both reward lookahead and transition lookahead, how would the regret bound be different?\n\n2. Why doesn't the paper present a case study that illustrates how would the agent behave differently between a normal RL setting and a lookahead setting?", "limitations": "Discussed in the Weakness section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies an interesting RL problem where one-step lookahead information is available to the agent while the environment is unknown. \n\n2. The paper clearly presents the problem, the solution, and a comparison between the proposed algorithm and the baseline in terms of regret bound.\n\n3. The paper offers explanation of the terms in the regret bounds and justified its explanation.", "weaknesses": "1. One concern is the application of such a lookahead setting. The agents during training and running needs to know what will be realized in order to make actions at the current state. Not sure what real-world scenarios this setting can be applicable to.\n\n\n2. RL with lookahead information has been investigated before from a theoretical point of view. See [R1, p64]. [R2] [R3]. [R1] discusses the lookahead in the approximation of the bellman function. [R2-R3] considers controlled lookahead where the agents decide the step of lookahead as a strategy. It is not straightforward to see in this paper how the lookahead studied in this paper different from those references. \n\n[R1] Bertsekas, Dimitri. Reinforcement learning and optimal control. Vol. 1. Athena Scientific, 2019.\n[R2] Biedenkapp, André, et al. \"TempoRL: Learning when to act.\" International Conference on Machine Learning. PMLR, 2021.\n[R3] Huang, Yunhan, Veeraruna Kavitha, and Quanyan Zhu. \"Continuous-time markov decision processes with controlled observations.\" 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2019.\n\n\n3.  It is not clear the source of the baseline mentioning in the paper. For example, \"compared to a stronger baseline that also has access to lookahead information\". The paper should includes the reference whenever the baseline is compared with the proposed solution.", "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# Weaknesses\n1.There are numerous applications where exact or approximate lookahead information is present:\n* Transactions/Market interaction - whenever the agent performs transactions, the traded items and their prices are mostly observed before the trade takes place - reward lookahead. This is also relevant for problems such as inventory management.\n* Communication networks - some networks continuously monitor the communication quality in different channels and use this information to choose which channel to use/avoid. This is similarly relevant in routing or situations where a protocol dictates when/where data could be sent.\n* Packing - When trying to pack items optimally, the learner often observes the next item/few items and uses this observation to decide how to pack the current item. One famous example is Tetris, where the next block is observed. This can also be extended to systems with an observable queue.\n* Navigation - depending on the problem, traffic information could be translated to either reward or transition lookahead. A related example is ride-sharing - travelers’ future location can be seen as future reward information.\n* Weather-dependent applications - weather predictions are extremely accurate in the near future, and can determine either the transition or reward (depending on the application)\n* Electricity grids - Electricity consumption can be accurately predicted in the near future, as well as electricity supply.\n\nSome of these applications fit well to our model, while in others, the agent gets noisy predictions/multiple steps in the future - we believe that the numerous potential extensions/generalizations will further motivate the community to work on similar models.\n\n3.When we measure regret, we calculate the difference between the value of the *optimal lookahead agent* and the value of the learning agent. The value of the optimal lookahead agent is much higher than the value of agents without lookahead (see the examples at the beginning of Sections 3 and 4, which explain why this value can be larger by a factor of roughly $AH$ and $A^H$, respectively, and an additional example below). When we talk about a stronger baseline, we talk about this optimal lookahead value - we want our agent to achieve sublinear regret compared to it and not compared to the standard no-lookahead value. Standard off-the-shelf RL agents cannot converge to the optimal lookahead value and will suffer linear regret vs. this baseline.\n\n2.We thank the reviewer for the references and apologize that our discussion in the related work is not clear enough. There are two concepts of lookahead in the literature. In the learning community (and as far as we could see, also in [R1]), it is mainly used as a planning technique - that is, the model is not accurate enough/too complex for long-term planning, and lookahead is used as a computational tool to estimate a policy with high ‘standard’ (no-lookahead)  value. For example, in [R1], it is motivated as an approach that mitigates the influence of errors in future value estimations. In particular, the aim is still to calculate the optimal Markovian policy, and lookahead is a means to calculate it.  We, on the other hand, aim to achieve the higher lookahead value (as done in some existing formulations of MPC). This is not a semantic difference - the algorithm actively utilizes the fact that additional information will be revealed in the future to achieve higher values. To our understanding, this difference also holds in [R2-R3] - they do not rely on new future information but rather plan how to act multiple steps to the future. We will extend our discussion to cover this and include the suggested references.\n## Example\nTo further illustrate the difference in values, consider the following 3-state environment.\n* The agent starts at $s_1$ and has two options: move to state $s_2$ and gain 0 reward or transition to state $s_3$ and deterministically gain a reward of $R=0.6$.\n* In $s_2$, two actions lead to state $s_3$, each giving a reward of $Ber(0.5)$.\n* $s_3$ is a no-rewarding terminal state.\n\nWithout lookahead information, an optimal agent would move directly from state $s_1$ to $s_3$, earning a value $V=0.6$. This is also true for agents calculated via rollouts/lookahead planning: the possible trajectories are $s_1->s_3$ and $s_1->s_2->s_3$, and if we use rollouts of length 3, we get that the trajectory $s_1->s_3$ is better in expectation (value $0.6$ compared to $0.5$ when going through $s_2$).\n\nIn contrast, in our setting, we assume to have lookahead information, that is, once we reach a state, we know that rewards will be revealed before choosing an action. Specifically, when reaching $s_2$, we can pick the action with the maximal *realized* reward - collect a unit reward w.p. $0.75$. In state $s_1$ we can still only earn $R=0.6$, so the optimal policy changed: now it is optimal to take the path $s_1->s_2->s_3$ (with value $V=0.75$). In other words, even though the expected rewards in $s_2$ are lower, the agent decides to go there because the rewards are more stochastic, and it relies on the fact that when observing the rewards, this stochasticity can be used to collect a higher value.\n# Questions\n1. When having both reward and transition lookahead, we believe that our algorithms could be naturally generalized by estimating both distributions simultaneously. Then, using similar techniques, it should be possible to prove a regret bound of $O(\\sqrt{H^4SAK})$ or better. We also suspect that the lower bound for this setting is $\\Omega(\\sqrt{H^3SK})$, so the hypothesized upper bound would be tight up to a factor of $\\sqrt{SA}$.\n2. We intended that the examples at the beginning of Sections 3 and 4 would be the illustrative examples that show the difference between situations with and without lookahead. We will try to further clarify them - we would appreciate any further feedback on what is missing in the examples.", "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": "MuxkR9UsfU", "reviewer": "Reviewer_49N6", "summary": "The paper considers the setting where the agent can see the possible next rewards and next states without assuming a prior knowledge of the environment dynamics. The predicted next rewards and next states are estimated by empirical distribution. The paper considers extending Monotonic Value Propagation to such a setting and proves that the proposed algorithms can achieve tight regret bounds.", "questions": "There has been prior work in deep RL that makes use of lookahead information even when the environment dynamic is unknown. One example is the Thinker algorithm [1], which allows agents to select an imaginary action trajectory to collect n-step lookahead information before selecting an action in each step (the environment dynamics are also assumed to be unknown). The related work section should be updated to reflect this (e.g. line 73-79). However, as these works are mostly empirical without proving the regret bound, I still recommend that the paper be accepted, given its theoretical significance. \n\n[1] Chung, Stephen, Ivan Anokhin, and David Krueger. \"Thinker: learning to plan and act.\" Advances in Neural Information Processing Systems 36 (2024).", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A tight regret bound is proved for the proposed algorithm, establishing theoretical justification for lookahead information and advantages of planning in RL in general.\n- The paper does not assume known environment dynamics as in most previous works, which makes the algorithm applicable to standard RL settings. The lack of known environment dynamics may bring various challenges to planning, such as agents not relying on the lookahead information when the estimated environment dynamics are still far from the true one in the early stages. The paper shows that the lookahead information can still be very beneficial despite such challenges.\n- The paper is well-written, and the proof is easy to follow.", "weaknesses": "Even though a tight regret bound has been proved, empirical experiments with examples showing how the agent uses the lookahead information will strengthen 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 positive comments and refer to the general response for a detailed discussion on simulations in our paper. We also provide an additional example of the advantage of lookahead information in the response to reviewer MArZ, and discuss how the distribution affects the lookahead value in the response to reviewer Dj8h - we are willing to further discuss this in the final version of the paper.\n\nWe acknowledge that in our literature survey, we focused on previous theoretical work; we apologize for that and will try to extend our survey to also cover more practical works, including [1]. Yet, we would like to point out that most previous works consider lookahead exclusively as a planning mechanism - that is, use it to calculate a better policy in the standard RL feedback model. In our framework, we know that we will encounter the exact same trajectory both in planning and when interacting with the environment, and this information could sometimes be leveraged to obtain a much higher value (see also the example in the response to reviewer MArZ that illustrates it). The two lookahead notions intersect when the environment is deterministic. On the other hand, in stochastic environments, the agent can actively take advantage of the stochasticity: learn the observation distribution in future states and decide in which future state observing rewards/transitions before acting would be more beneficial. Another potential intersection could appear when analyzing multi-step lookahead information - then, lookahead planners might be applied to effectively utilize lookahead information even in stochastic environments. We will further discuss this in our work.", "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": "HqIO6ZNliA", "reviewer": "Reviewer_CUjN", "summary": "This manuscript proposes the RL method with lookahead information. The authors discuss two scenarios: reward lookahead and transition lookahead. Under such scenarios, the proposed method estimates the reward distribution and transition distribution, respectively. Then the monotonic value propagation skill is applied to calculate the value function. The authors show that the proposed method has strong theoretical properties and the reward regret is strongly bounded under two circumstances.", "questions": "Line 150， the sentence should be \"in this way\"?\n\nThe estimated reward/transition distribution $\\hat{R}^k_h$ and $\\hat{P}^k_h$ are key components for the proposed method, it is suggested to give more details on the distribution estimation part. \n\nFor both cases, the authors proposes the bonuses, I am confused why do we need the bonus? only for calculating the variance value? However, even without the bonus value, we can also update the value function $\\bar{V}^k_h(s)$, right?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The manuscript is well organized, and the structure is clear. The authors shows very promising bound for both reward lookahead and transition lookahead scenarios.", "weaknesses": "This is a theoretical paper, however, the authors miss to deliver some numerical or empirical studies. It is suggested to add some empirical experiments, at least with simulated data. \n\nAlgorithm 1&2 shows the procedure for training, I am confused about the inference process. How to select the action give certain state in inference? The authors are suggested to give some explanations in the Algorithm 1&2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the response and refer to the general comment on empirical simulations.\n\nWe apologize for any clarity issue and will make an effort to clarify the setting and the algorithm. Our paper studies an online setting where we repeatedly interact with an unknown environment in episodes, with the goal of collecting as much reward as possible throughout the interaction. Thus, the training and inference are interleaved - on each episode, we aim to use all the historical data to maximize the reward, on the one hand, while continuing to explore to improve future performance, on the other hand. The regret is a measure of how well we perform this task - can we collect rewards almost as much as the optimal policy that knows the environment in advance?\n\nEvery episode starts with a planning phase, where we calculate an optimistic value (to ensure exploration), and then continue with interaction for a full episode ($H$ steps) with the environment. When each episode ends, the environment resets to a new initial state and the process repeats itself for $K$ episodes. For example, in Algorithm 1, lines 4-6 represent the planning stage, while line 9 represents the deployed policy for this episode. In Appendix B.3, we provide a more detailed version of the algorithm, where the planning stage is on lines 4-10 and the deployed policy is given on line 11.\n\nWith reward lookahead, every time we reach a state $s$ at step $h$, we first observe the rewards $R(a)$ for all actions and then use our approximate planning to pick up an action that maximizes the expected long-term gain from an action $a_h \\in \\arg\\max_a [ R(a)+\\sum_{s’}\\hat{P}_h(s’ | s, a){\\bar{V}} _{h+1}(s’)+ bonus]$. The first term accounts for the immediate *reward observation* while the second handles future values. The bonus ensures optimism/exploration. Importantly, we start without knowing anything about the environment, and without the bonuses, we would not be incentivized to visit new parts of the state space. As a result, we would not have data on these unvisited areas and would converge to a suboptimal policy. This is similar to the way that UCB1 does exploration in bandits, just adapted to RL. With transition lookahead, we apply similar principles, but the agent observes the next state for any action before acting instead of the rewards.\n\nIf we understand correctly, the reviewer considers an altenative setting, in which either the data is an offline data set and we need to find a good policy to deploy (‘offline RL’), or where we interact with an environment to gather data that will allow calculated a good policy (‘best-policy identification’) - while lookahead could definitely be studied there, we focused on online regret minimization. \n\n# Questions:\n\n * Line 150 - noted, thanks!\n\n* We will further elaborate on how the empirical distributions are calculated in the final version of the paper - thanks for the comment. The distributions are essentially uniformly sampling from a buffer: we keep all past reward/transition observations, and every time we want to sample an observation, we just take what we saw at a uniformly random past time step. More specifically, since we calculate an expectation over these distributions, this is just an empirical average using past observations - the explicit formula is provided in line 9 of Algorithms 3 and 4 (which are in the appendix). In practical implementations, it could be adapted using a finite buffer that tries to keep diverse information on different regions of the state space, or more elaborate distribution estimation mechanisms.\n\n    For transition kernels, we slightly abuse notations - we denote by $\\hat{P}_h^k(s’ | s,a)$ - the empirical probability to transition from state $s$ to $s’$ when playing $a$ at step $h$ - the fraction of times in the past that we took action $a$ at state $s$ and transitioned to $s’$. The distribution $\\hat{P}_h^k(s)$ is the empirical joint distribution of the next states at $s$ across all actions (that is, an $A$-dimension vector of next-states). It is calculated using the sampling from a buffer, as discussed in the previous paragraph.\n\n* The bonuses are needed for exploration, we hope that the previous part of the response clarified it, but if not, we will gladly provide additional clarifications.", "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": "FV8PRErH0T", "reviewer": "Reviewer_V5fX", "summary": "The authors proposed new forms of Bellman equations for environments where the agent knows the reward or transition outcomes one step ahead (without knowing the full model).", "questions": "- Perform experimental validation to illustrate the practical performance. \n  For instance, it would be necessary to check the learning curves and the resulting performance. \n  The authors should also discuss the practical implementation. \n\n- H is the important parameter to be determined. Provide a practical guide line for choosing H. \n\n- can this method be extended to off-policy learning ?\n  Is the method data-efficient ?", "limitations": "Some aspects of the approach might be seen as incremental advancements  rather than groundbreaking theoretical analysis .", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "While previous papers (e.g., Boutilier et al. 2018) discussed utilizing lookahead information (and proved convergence), the authors claim they are the first to present regret results.", "weaknesses": "While the theoretical contribution is clear, the authors must also provide practical 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 and refer to the general response on simulations. \n\n* As we explained in the general response, we agree that evaluation is important and believe that the best way to do so is to adapt our work to a deep RL setting, but this is outside the scope of this paper. Nonetheless, we would like to emphasize that our theoretical bounds *provably guarantee* well-behaved learning curves in tabular settings - in fact, since the bounds are minimax optimal, there exist some environments in which our algorithms converge at the optimal rate (up to absolute constants). We present a detailed algorithm description that includes the exact implementation details of both algorithms in Appendices B.3 and C.3, including the precise statement of the bonus and the update rules; any implementation of the theoretical algorithm would follow these schemes to the letter.\n\n* Horizon H: the horizon is indeed a very important parameter in episodic RL - after H steps, the interaction is over and a new episode starts. In most applications, the choice of the horizon is induced by the environment - the interaction *cannot* last more than a fixed number of steps (‘external termination of the agent/timeout’). In this sense, it is very different than a discount factor that induces a soft effective horizon - often tuned by the algorithm designer. Finite-horizon algorithms can also work with any upper bound on the number of steps - though this degrades the performance, the effect of $H$ on the regret is usually assumed to be much less significant than any dependence on the state space. In general, and to our knowledge, all previous works on finite-horizon regret minimization assume the horizon is given to the agent as an input [19, 9, 33, 12, 14, 30, 35, 36]. Nonetheless, a few papers study regret minimization in alternative interaction models, including average reward [18] or stochastic shortest paths [*]. We believe that extending our results to these settings is an interesting future work.\n\n* Our approach achieves optimal data efficiency, in the sense that our regret bounds are minimax optimal. In other words, for any algorithm, there exists an environment such that the difference between the collected reward and the optimal one must be larger than ours (up to absolute/additive constant). More broadly, our approach is model-based, and such approaches tend to use data more efficiently than model-free methods.\n\n* We admit that we do not fully understand the question about off-policy learning. In our algorithm, we use all the data from historical interactions to estimate an environment model and use this model to perform optimistic planning - calculate the optimal agent at an optimistic environment. This includes data from previous deployed policies which are different from the current one. In addition, while this planning module outputs a value that determines our policy, we never perform a policy evaluation of previously used policies and do not rely on policy iteration/computations that are usually considered as policy improvement. As such, we believe that our algorithm can be described as an off-policy algorithm. If the question was about using offline data - we believe that such data could be utilized to improve our model estimation. If it was about model-free algorithms - as we mention in the conclusions section, extending our paper to model-free algorithms (e.g., Q-learning) would be very natural - we refer to the response to reviewer Dj8h for more details. In case we did not answer the intended question, we would appreciate it if the reviewer could clarify the question and we will gladly answer in the reviewer-author discussion period.\n\n------\n\n[*] Rosenberg, Aviv, et al. \"Near-optimal regret bounds for stochastic shortest path.\" International Conference on Machine Learning. PMLR, 2020.", "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": "cCJAz5kTVu", "reviewer": "Reviewer_Dj8h", "summary": "This paper introduces reinforcement learning (RL) problems where agents observe one-step lookahead information (either rewards or transitions) before choosing actions in episodic tabular MDPs. Two relevant lines of work exist: the control literature, which studies a similar lookahead concept in the continuous state-space scenario, and the RL planning community, which commonly obtains lookahead information from learned transition models. However, this paper assumes the reward/transition information to be available before selecting an action. The core contributions are:\n\n1) Formalising the look-ahead setting for the reward and transition in an episodic MDP setting.\n2) Derivation of the Bellman equations in the original space by setting up an equivalence with an equivalent new MDP.\n3) Development of two algorithms for reward (MVP-RL) and transition lookahead ( MVP-TL).\n4) First sub-linear regret bound win the lookahead setting.", "questions": "How applicable is the theoretical argument you used to a model-free version of MVP-RL/TL?", "limitations": "The limitations outlined in the paper provide a fair representation of how the theoretical results could be extended in various directions, such as multi-step and stochastic action sets.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is the first to provide regret bound on the lookahead learning setting. This encompass a somewhat broad spectrum of problems that were independently studied such as the Canadian traveler problem and the prophet inequalities. \n\nThey paper is well written and easy to follow for non-expert in learning theory. It presents the core ideas in an understandable way in the main paper and use the appendix for technical proofs.", "weaknesses": "The paper could be strengthened by adding experimental results studying the difference in behaviour and performance between standard RL algorithm, MVP and the proposed solution MVP-RL. More specifically, I would be interested in understanding the difference in behaviour when changing the tails of the reward/transition distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and refer to the general comment regarding experiments. In particular, MVP converges to the no-lookahead value, so there would be a linear difference between its performance and our algorithms, so the algorithms are not really comparable.\n\nWhile the tail of the distribution will somewhat affect the sublinear regret rates, its dominant effect would be on the lookahead value. This is since any effect on the value is equivalent to linear regret terms - much larger than the $\\sqrt{K}$ terms. In simple environments, the effect of the tail on the value can be analyzed in closed form, so we do not need to resort to numerical evaluation. One interesting property is that the behavior of the lookahead value is not a simple function of the tail, and similar tails might have many different behaviors.\n\n----- \n\n Consider the following examples:\n\n**Reward lookahead in a prophet-like problem (Figure 1).** The value only depends on the reward distribution when moving from $s_i$ to $s_f$.\n\n1) *Bernoulli distributions.* Assume that when transitioning from $s_i$ to $s_f$, we obtain rewards $Ber(p)$. In particular, the optimal no-lookahead value is always $V^{no-lookahead}=p$. On the other hand, the lookahead value will be the probability of observing at least one unit reward $V^{R,*} = 1 - (1-p)^{AH}$, and in particular,\n    - If $p<1/(AH)$, we get that $V^{R,*}\\approx HAp$ - higher by a factor of $AH$ than the no-lookahead value. \n    - If $p\\approx 1/2$, then the lookahead value will approach $V^{R,*}\\approx 1$ - constant-factor improvement. \n    - Finally, for $p\\approx 1$, both values are roughly $1$ - no improvement. \n\n    Interestingly, when thinking on standard ‘tail measures’ (e.g., Chernoff bound for averages), the *least concentrated* situation (with the heaviest tails) is when $p\\approx 1/2$, even when only considering the upper tail of the distribution. On the other hand, the two lighter-tailed situations behave very differently: in one, we get a huge performance boost while in the other, we gain nothing.\n\n2) *Gaussian distributions* $\\mathcal{N}(\\mu,\\sigma)$. Analytically calculating the value is quite hard, but using the properties of the maximum of Normal R.V.s, it is quite easy to (approximately) bound the reward-lookahead value in the interval $V^{R,*}\\in [\\mu+\\sigma\\log(A), \\mu+\\sigma\\log(AH)]$. Without lookahead, the value would be $V^{no-lookahead}=\\mu$, so the difference between the values is proportional to the variance.\n\n3) More generally, if we limit ourselves to bounded distributions with expectation $\\mu$ and  effective support $[a,b]$, for large horizons, the lookahead value approaches $b$, while the no lookahead value will stay $\\mu$. The specific tail might affect the rate at which it happens, but will not change the limiting value.\n\n----- \n\n**Tail effects with transition lookahead.** We admit that we are not familiar with a notion of a tail for a transition kernel over a finite state space, but we will try to illustrate how stochasticity in the transitions affects lookahead values. Let us still consider transition lookahead on a chain (variant of the example in Section 4). To simplify things, assume that we have a chain of length $n<H$ with two actions. One action moves forward w.p. $p$ (and w.p. $1-p$, we ‘fail’ and cannot collect any rewards). A second action does not change the state. We aim to reach the end of the chain to collect a unit reward. For no-lookahead agents, the probability of successfully traversing the chain is $p^{n}$. For one-step lookahead agents, it is the probability of having at least $n$ successes for the binomial $Bin(H,p)$. In particular,\n- When $p>> 1- 1/n$, both agents will succeed to collect the reward - have unit values.\n- For $p<< n/H$, both are likely to fail, but the lookahead agent still has an exponentially larger probability to succeed traversing the chain. \n- In the intermediate regime, the lookahead agent will succeed and the no-lookahead agent will fail. \n\nThus, in some senses, the lookahead is more valuable in the ‘heavy tail’ regime (intermediate probability), but we see two different behaviors in the ‘light tail’ regime - similar values for large $p$ and exponentially different values for small $p$.\n\n----- \n\n**To summarize:** while it seems that ‘heavier tail’ generally helps lookahead agents, there is no clear way to translate tail properties to lookahead values. \n\n-----\n\n**Model-Free Algorithms:** generally speaking, even in the classical RL setting, the analysis techniques of model-based on model-free algorithms are very different, and we are not aware of any study that unifies regret analysis for both settings. We still believe that some elements could be taken from our work to the model-free setting - for example, using the structure and properties of the optimal value and the optimal policy (and, in particular, the list structure for transition lookahead), or using uniform concentration and avoiding pessimism. Nonetheless, the regret analysis will be more involved than the classic analysis of Q-learning [19] and will probably require new notions of Q-values that allow incorporating the observations into the policy. For example, with reward lookahead, the Q-values should not include immediate rewards, so that the reward observations could be later added when interacting with the environment.", "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:
## Experiments

Some of the reviewers expressed concern due to the lack of experiments in the paper. 

While conducting experiments is always interesting, our paper theoretically studies a new setting for which there are no existing algorithms with theoretical regret guarantees. Thus, when comparing our approach to any existing algorithms that converge to the ‘standard’ no-lookahead value (which is much lower than the lookahead value), the difference between the values will dominate the performance. As such, it is very challenging to devise experiments that provide meaningful insights beyond the fact that the algorithm converges (which the proof already ensures). On the other hand, it is possible to discuss both theoretically and numerically the difference between the standard values and lookahead values, to demonstrate how much we can gain from utilizing lookahead information. We refer to the response to reviewer Dj8h for an additional discussion on lookahead vs. no-lookahead values in various scenarios. If the reviewers think it would be beneficial, we could extend this discussion and provide plots that illustrate the difference between the two values in the paper.

We agree with the reviewers that further pursuing the empirical study of this setting is of great importance due to its vast potential applications (as we detail in the response to reviewer MArZ). However, for this to be relevant for large-scale applications, this evaluation should be done while adapting our approach to deep RL, which is outside the scope of our paper. Our scope is more theoretical - we formalize a new setting with numerous potential applications and fully analyze planning and learning. In particular, the regret bounds of our algorithms are minimax-optimal (‘converge at the fastest possible rate for some problems’). Moreover, our algorithms and proofs have many novel elements: instead of estimating the expected reward/transition kernel, our algorithms work with the joint reward/next-state distribution and integrate distribution estimation into planning and learning; we show how to modify the classic regret analysis techniques to bypass the strong dependence that the setting creates between actions and rewards/next states;  we demonstrate how to use the list representation of the policy to obtain tighter regret bounds; and more.

Meta-review: The reviewers unanimously agree that the paper studies an interesting problem of RL with additional side information ("lookahead"). The authors are advised to revise the paper according to the comments given by the reviewers and the AC, particularly regarding comparison to vanilla RL without side information.
Decision: Accept (poster)