Reinforcement Learning with Lookahead Information

Authors: nadav  merlis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 21:33:47

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.

Main paper: 
 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 of 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, at each timestep, agents first choose an 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 ('reward information'). Alternatively, in navigation problems, nearby traffic information is known to the agent before choosing which path to 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 can drastically increase the reward collected by agents -by a multiplicative factor of up to AH when immediate rewards are revealed in advance and A H/2 when observing the immediate future transitions.1 Intuitively, agents do not only gain from instantaneously using this information -they can also adapt their planning to account for lookahead information being revealed in 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.In this work, we aim to design provably-efficient agents that learn how to interact when given immediate ('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-guaranteed 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., 2021b ] that allow incorporating either reward or transition lookahead. In particular, we suggest a planning procedure that uses the 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 Õ √ H 3 SAK and Õ √ H 2 SK( √ H + √ A) 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 5 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, Camacho 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 , Zhang 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 as a planning tool; namely, agents test the possible outcomes after performing multiple steps to decide which actions to take or to better estimate the value [Tamar et al., 2017 , Efroni et al., 2019a , 2020 , Moerland et al., 2020 , Rosenberg et al., 2023 , El Shar and Jiang, 2020 , Biedenkapp et al., 2021 , Huang et al., 2019] . Specifically, the future value at the end of the lookahead is 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 et 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 is 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 , Jin 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 ]. Yet, we are not aware of 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] . interaction horizon. At each timestep h ∈ {1, . . . , H} ≜ [H] of an episode k ∈ [K], an agent, located in state s k h ∈ S, chooses an action a k h ∈ A and obtains a reward R k h = R h (s k h , a k h ) ∼ R h (s k h , a k h ). We assume that the rewards are supported by [0, 1] and of expectations r h (s, a). Afterward, the environment transitions to a state s k h+1 ∼ P h (•|s k h , a k h ) and the interaction continues until the end of the episode. We use the notation R ∼ R h (s) (or s ′ ∼ P h (s)) to denote reward (next-state) samples for all actions simultaneously at step h and state s and assume independence between different timesteps. 2 On the other hand, samples from different actions at a specific state/timestep are not necessarily independent.Reward Lookahead. With one-step reward lookahead at timestep h and state s, agents first observe the rewards for all actions R h (s) ≜ {R h (s, a)} a∈A and only then choose an action to perform. Formally, we define the set of reward lookahead policies as Π R = π : [H] × S × [0, 1] A → ∆ A , where ∆ A is the probability simplex, and denote a h = π h (s h , R h ). The value of a reward lookahead agent is the cumulative rewards gathered by it starting at timestep h and state s, denoted byV R,π h (s) = E H t=h R t (s t , π t (s t , R t (s t ))|s h = s .We also define the optimal reward lookahead value to be V R, * h (s) = max π∈Π R V R,π h (s). When interacting with an unknown environment for K episodes, agents sequentially choose reward lookahead policies π k ∈ Π R based on all historical information and are measured by their regret,Reg R (K) = K k=1 V R, * 1 (s k 1 ) -V R,π k 1 (s k 1 ) .We allow the initial state of each episode s k 1 to be arbitrarily chosen.Transition Lookahead. Denoting s ′ h+1 (s, a), the future state when playing action a at step h and state s, one-step transition lookahead agents observe s ′ h+1 (s) ≜ s ′ h+1 (s, a) a∈A before acting. The set of transition lookahead agents is denoted by Π T = π : [H] × S × S A → ∆ A with valuesV T,π h (s) = E H t=h R t (s t , π t (s t , s ′ t+1 (s t )))|s h = s .The optimal value is V T, * h (s) = max π∈Π T V T,π h (s), and we similarly define the regret versus optimal transition lookahead agents as Reg T (K) =K k=1 V T, * 1 (s k 1 ) -V T,π k 1 (s k 1 ) .When the type of lookahead is clear from the context, we sometimes denote values by V π h and V * h .Other Notations. For any p ∈ ∆ n and V ∈ R n , we define Var p (V ) =n i=1 p i V 2 i -( n i=1 p i V i ) 2 .Also, given a transition kernel P and a vector V ∈ R S , we let P V (s, a) = s ′ ∈S P (s ′ |s, a)V (s ′ ) and similarly define it for value or transition kernel differences. We denote by n k h (s, a), the number of times the pair (s, a) was visited at timestep h up to episode k (inclusive) and similarly denote n k h (s) = a∈A n k h (s, a). We also let rk h (s, a) =1 n k h (s,a) k k ′ =1 1 s k ′ h = s, a k ′ h = a R k ′ h and Ph (s ′ |s, a) = 1 n k h (s,a) k k ′ =1 1 s k ′ h = s, a k ′ h = a, s k ′ h+1 =s ′ be the empirical expected rewards and transition kernel at (s h , a h ) = (s, a) using data up to episode k and assume they are initialized to be zero. Finally, we denote by Rk h (s), the empirical reward distribution across all actions, and use P k h (s) to denote the empirical joint next-state distribution for all actions. In particular, if k i is the i th episode where s was visited at step h, to sample R ∼ Rk h (s), we uniformly sample i ∼ U n k h (s) and return R = R ki h (s, a)a∈A . A sample s ′ ∼ P k h (s) similarly returns s ′ = s ′ki h+1 (s, a)a∈A .When we want to indicate the distribution used to calculate an expectation, we sometimes state it in a subscript, e.g., write E R h (s) [R(a) ] to indicate that R(a) ∼ R h (s, a) or use E M to emphasize that all distributions are according to an environment M. In this paper, O-notation only hides absolute constants while Õ hides factors of polylog(S, A, H, K, δ). We also use the notation a ∨ b = max{a, b}. 
'transition learning rate' o( √: 
 H 3 SK): recall that the vanilla RL lower bound designs a tree with Ω(S) leaves, to which agents need to navigate at the right timing (with Ω(H) options) and take the right action (out of A). While all leaves might transition agents to a rewarding state, one combination of state-action-timing has a slightly higher probability of doing so [Domingues et al., 2021] . This roughly creates a bandit problem with SAH arms, constructed such that the maximal reward is Ω(H), yielding a total regret of H √ HSAK. 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 to test all leaves at all timings, and so there are still SH 'arms' with a corresponding regret of √ H 3 SK. Moreover, to test a leaf at a 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 an RL instance with stochastic action sets. While Boutilier et al. [2018] 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.h ∈ [H], at timestep 2h -1, the environment M R transitions from state s h × 0 to s h × R, where R ∼ R h (s)is a vector containing the rewards for all actions a ∈ A. This transition occurs regardless of the action that was played. At timestep 2h, given an action a h the environment transitions from s h × R to s h+1 × 0, where s h+1 ∼ P h (•|s h , a h ). 3. The reward at a state s × R when playing an 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 R are coupled; that is, assume that under a policy π in M, the agent visits a state s h , observes R h , plays an action a h and transitions to s h+1 . Then, in M R , the agent starts from s h × 0, transitions to s h × R (regardless of the action it played), takes the action a h and finally transitions to s h+1 × 0.Since the reward is embedded into the state, any state-dependent policy in M R is a one-step reward lookahead policy in the original MDP. Moreover, the policy at the odd steps of M does not affect the value, and assuming that the policy at the even steps in M R is the same as the policy in M, we trivially get the following relation between the valuesEQUATIONWhile M R has a 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 environments. This is because we are mainly interested in the value given the state -in expectation over the realized rewards. In particular, value-difference are analyzed assuming a 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 satisfiesV R, * H+1 (s) = 0, ∀s ∈ S, V R, * h (s) = E R∼R h (s) max a∈A R h (s, a) + s ′ ∈S P h (s ′ |s, a)V R, * h+1 (s ′ ) , ∀s ∈ S, h ∈ [H].Also, given reward observations R = {R(a)} a∈A at state s and step h, the optimal policy isπ * h (s, R) ∈ arg max a∈A R(a) + s ′ ∈S P h (s ′ |s, a)V R, * h+1 (s ′ ) .Proof. We prove the result in the extended MDP M R and remind the reader that in this formulation, the policy only uses state information, as in the standard RL 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 dynamic-programming equations [Puterman, 2014]EQUATIONBy the equivalence between M and M 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 (3), we get the desired value recursion for any h ∈ [H] and s ∈ S:V R, * h (s|M) = V * 2h-1 (s, 0|M R ) = E R h (s) V * 2h (s, R|M R ) = E R h (s) max a R(a) + s ′ ∈S P h (s ′ |s, a)V * 2h+1 (s ′ , 0|M R ) = E R h (s) max a R(a) + s ′ ∈S P h (s ′ |s, a)V R, * h+1 (s|M) .Similarly, for any h ∈ [H], s ∈ S and R ∈ R A , the optimal policy at the even stages of the extended MDP isπ * 2h (s, R) ∈ arg max a∈A R(a) + s ′ ∈S P h (s ′ |s, a)V * 2h+1 (s ′ , 0|M R ) ,alongside arbitrary actions at odd steps. Playing this policy in the original MDP will lead to an optimal one-step reward lookahead policy, as 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 relationV * 2h+1 (s ′ , 0|M R ) = V R, * h+1 (s ′ |M). Remark 1.As in Equation (4), one could also write the dynamic programming equations for any policy π ∈ Π R , namelyV π 2h (s, R|M R ) = R(π h (s, R)) + s ′ ∈S P h (s ′ |s, π h (s, R))V π 2h+1 (s ′ , 0|M R ), ∀h ∈ [H], s ∈ S, R ∈ R A , V π 2h-1 (s, 0|M R ) = E R h (s) V π 2h (s, R|M R ) , ∀h ∈ [H], s ∈ S.In particular, following the notation of Equation (3), one can also writeV R,π h (s, R|M) = R(π h (s, R)) + s ′ ∈S P h (s ′ |s, π h (s, R))V R,π h+1 (s ′ |M), and, V R,π h (s|M) = E R h (s) V R,π h (s, R|M) = E R h (s) R(π h (s, R)) + s ′ ∈S P h (s ′ |s, π h (s, R))V R,π h+1 (s ′ |M)) .We will use this notation in some of the proofs.Another useful application of the extended MDP is a variation of the law of total variance (LTV), which will be useful in our analysis Lemma 3. For any deterministic one-step reward lookahead policy π ∈ Π R , it holds thatE H h=1 Var P h (•|s h ,a h ) (V R,π h+1 (s h+1 ))|π, s 1 ≤ E   H h=1 R h (s h , a h ) -V R,π 1 (s 1 ) 2 |π, s 1   .Proof. We apply the law of total variance (Lemma 27) in the extended MDP; there, the rewards are deterministic and equal to either 0 (at odd steps) or R h (s h , a h ) (at even steps), so the total expected rewards areH h=1 R h (s h , a h ). E   H h=1 R h (s h , a h ) -V π 1 (s 1 , 0|M R ) 2 |π, s 1   = E       H h=1 Var(V π 2h (s h , R h (s h )|M R )|(s h , 0)) Odd steps + H h=1 Var(V π 2h+1 (s h+1 , 0|M R )|(s h , R h (s h ))) Even steps |π, s 1       ≥ E H h=1 Var(V π 2h+1 (s h+1 , 0|M R )|(s h , R h (s h )))|π, s 1 = E H h=1 Var P h (•|s h ,a h ) (V π 2h+1 (s h+1 , 0|M R ))|π, s 1 = E H h=1 Var P h (•|s h ,a h ) (V R,π h+1 (s h+1 |M))|π, s 1 . Noting that V π 1 (s 1 , 0|M R ) = V R,π 1 (s 1 |M) concludes the proof.Finally, though not needed in our analysis, we use the extended MDP to prove the following valuedifference 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 on the next value.Lemma 4 (Value-Difference Lemma with Reward Lookahead). Let M 1 = (S, A, H, P 1 , R 1 ) and M 2 = (S, A, H, P 2 , R 2 ) be two environments. For any deterministic one-step reward lookahead policy π ∈ Π R , any h ∈ [H] and s ∈ S, it holds thatV R,π h (s|M 1 ) -V R,π h (s|M 2 ) = E M1 V R,π h+1 (s h+1 |M 1 ) -V R,π h+1 (s h+1 |M 2 )|s h = s + E M1 s ′ ∈S P 1 h (s ′ |s h , π h (s h , R h )) -P 2 h (s ′ |s h , π h (s h , R h )) V R,π h+1 (s ′ |M 2 )|s h = s + E M1 E R 1 h (s) V R,π h (s h , R|M 2 ) -E R 2 h (s) V R,π h (s h , R|M 2 ) |s h = s , where V R,π h (s, R|M)is the value at a state given the reward realization, defined in Equation (3) and given in Remark 1.Proof. We again work with the extended MDPs M R 1 , M R 2 . Since under the extension, both the environments and the policy are Markovian, all values obey the following Bellman equations:V π 2h (s, R|M R ) = R(π h (s, R)) + s ′ ∈S P h (s ′ |s, π(s, R))V π 2h+1 (s ′ , 0|M R ), ∀h ∈ [H], s ∈ S, R ∈ R A V π 2h-1 (s, 0|M R ) = E R h (s) V π 2h (s, R|M R ) , ∀h ∈ [H], s ∈ 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 ∈ [H], we haveEQUATIONWe now focus on the first term. Denoting a h = π h (s h , R h ) the action taken by the agent at environment M 1 , We haveV π 2h (s h , R h |M R 1 ) -V π 2h (s h , R h |M R 2 ) = R h (a h ) + s ′ ∈S P 1 h (s ′ |s h , a h )V π 2h+1 (s ′ , 0|M R 1 ) -R h (a h ) + s ′ ∈S P 2 h (s ′ |s h , a h )V π 2h+1 (s ′ , 0|M R 2 ) = s ′ ∈S P 1 h (s ′ |s h , a h )V R,π h+1 (s ′ |M 1 ) - s ′ ∈S P 2 h (s ′ |s h , a h )V R,π h+1 (s ′ |M 2 ) = s ′ ∈S P 1 h (s ′ |s h , a h ) V R,π h+1 (s ′ |M 1 ) -V R,π h+1 (s ′ |M 2 ) + s ′ ∈S P 1 h (s ′ |s h , a h ) -P 2 h (s ′ |s h , a h ) V R,π h+1 (s ′ |M 2 ) = E M1 V R,π h+1 (s h+1 |M 1 ) -V R,π h+1 (s h+1 |M 2 )|s h , a h + s ′ ∈S P 1 h (s ′ |s h , a h ) -P 2 h (s ′ |s h , a h ) V R,π h+1 (s ′ |M 2 ).Substituting this back into Equation ( 5), we haveV π h (s|M 1 ) -V π h (s|M 2 ) = E M1 E M1 V R,π h+1 (s h+1 |M 1 ) -V R,π h+1 (s h+1 |M 2 )|s h , a h |s h = s + E M1 s ′ ∈S P 1 h (s ′ |s h , a h ) -P 2 h (s ′ |s h , a h ) V R,π h+1 (s ′ |M 2 )|s h = s + E R 1 h (s) V R,π h (s, R|M 2 ) -E R 2 h (s) V R,π h (s, R|M 2 ) = E M1 V R,π h+1 (s h+1 |M 1 ) -V R,π h+1 (s h+1 |M 2 )|s h = s + E M1 s ′ ∈S P 1 h (s ′ |s h , π h (s h , R h )) -P 2 h (s ′ |s h , π h (s h , R h )) V R,π h+1 (s ′ |M 2 )|s h = s + E M1 E R 1 h (s) V R,π h (s h , R|M 2 ) -E R 2 h (s) V R,π h (s h , R|M 2 ) |s h = s .h ∈ [H], at timestep 2h -1, the environment M T transitions from state s h × s ′ 0 to s h × s ′ h+1, where s ′ h+1 ∼ P h (s) is a vector containing the next state for all actions a ∈ A; this transition happens regardless of the action that the agent played. At timestep 2h, given an action a h , the environment transitions from s h × s ′ h+1 to s ′ h+1 (a) × s ′ 0 . 3. The rewards at odd steps 2h-1 are zero, while the rewards at even steps2h are R h (s h , a h ) ∼ R h (s h , a h ) of expectation r h (s h , a h ).As before, since the next state is embedded into the extended state space, any state-dependent policy in M T is a one-step transition lookahead policy in the original MDP. Also, the policy at even timesteps does not affect either the rewards or transitions, so it does not 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 T is the same as the policy in M, we trivially get the following relation between the valuesEQUATION)While M T is finite, it is exponential in size, so applying any standard algorithm in this environment would lead to exponentially-bad performance bounds. Nonetheless, as with the extended-reward environment, we use this representation to prove useful results on one-step transition lookahead.Proposition 2. The optimal value of one-step transition lookahead agents satisfiesV T, * H+1 (s) = 0, ∀s ∈ S, V T, * h (s) = E s ′ ∼P h (s) max a∈A r h (s, a) + V T, * h+1 (s ′ (s, a)) , ∀s ∈ S, h ∈ [H].Also, given next-state observations s ′ = {s ′ (a)} a∈A at state s and step h, the optimal policy isπ * h (s, s ′ ) ∈ arg max a∈A r h (s, a) + V T, * h+1 (s ′ (a)) .Proof. We prove the result in the extended MDP M T , in which (as with reward lookahead) the optimal value can be calculated using the Bellman equations as follows [Puterman, 2014]V T 2H+1 (s, s ′ |M T ) = 0, ∀s ∈ S, s ′ ∈ S A , V * 2h (s, s ′ |M T ) = max a r h (s, a) + V * 2h+1 (s ′ (a), s ′ 0 |M T ) , ∀h ∈ [H], s ∈ S, s ′ ∈ S A , V * 2h-1 (s, s ′ 0 |M T ) = E s ′ ∼P h (s) V * 2h (s, s ′ |M T ) , ∀h ∈ [H], s ∈ S. (8)By the equivalence between M and M T for all policies, this is also the optimal value in M.Combining both recursion equations and substituting Equation ( 7) leads to the stated value calculation for all h ∈ [H] and s ∈ S:V T, * h (s|M) = V * 2h-1 (s, s ′ 0 |M T ) = E s ′ ∼P h (s) V * 2h (s, s ′ h+1 |M T ) = E s ′ ∼P h (s) max a r h (s, a) + V * 2h+1 (s ′ h+1 (a), s ′ 0 |M T ) = E s ′ ∼P h (s) max a r h (s, a) + V T, * h+1 (s ′ h+1 (a)|M) .In addition, a given state s and next-state observations s ′ , the optimal policy at the even stages of the extended MDP isπ * 2h (s, s ′ ) ∈ arg max a∈A r h (s, a) + V * 2h+1 (s ′ (a)) ,alongside arbitrary actions at odd steps. Playing this policy in the original MDP will lead to 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 (V * 2h+1 (s, s ′ 0 |M T ) = V T, * h+1 (s|M)), this is equivalent to the stated policy.Remark 2. As in Remark 1, one could write the dynamic programming equations for any policy π ∈ Π T , and not just to the optimal one, namelyV π 2h (s, s ′ |M T ) = r h (s, π(s, s ′ )) + V * 2h+1 (s ′ (π h (s, s ′ )), s ′ 0 |M T ), ∀h ∈ [H], s ∈ S, s ′ ∈ S A , V π 2h-1 (s, s ′ 0 |M T ) = E s ′ ∼P h (s) V π 2h (s, s ′ |M T ) , ∀h ∈ [H], s ∈ S.In particular, following the notation of Equation (7), we can writeV T,π h (s, s ′ |M) = r h (s, π h (s, s ′ )) + V T,π h+1 (s ′ (π h (s, s ′ ))|M),and,V T,π h (s|M) = E s ′ ∼P h (s) V T,π h (s, s ′ |M) = E s ′ ∼P h (s) r h (s, π h (s, s ′ )) + V T,π h+1 (s ′ (π h (s, s ′ ))|M) ,a notation that will be extensively used for transition lookahead.We also prove a variation of the law of total variance (LTV) for transition lookahead:Lemma 10. For any one-step transition lookahead policy π ∈ Π T , it holds thatE H h=1 Var s ′ ∼P h (s h ) (V T,π h (s h , s ′ ))|π, s 1 ≤ E   H h=1 r h (s h , a h ) -V T,π 1 (s 1 ) 2 |π, s 1   .Proof. We apply the law of total variance in the extended MDP; there, the expected rewards are either 0 (at odd steps) or r h (s h , a h ) (at even steps), so the total expected rewards areH h=1 r h (s h , a h ). Hence, by Lemma 27, E   H h=1 r h (s h , a h ) -V π 1 (s 1 , s ′ 0 |M T ) 2 |π, s 1   = E       H h=1 Var(V π 2h (s h , s ′ h+1 |M T )|(s h , s ′ 0 )) Odd steps + H h=1 Var(V π 2h+1 (s h+1 , s ′ 0 |M T )|(s h , s ′ h+1 )) Even steps |π, s 1       ≥ E H h=1 Var(V π 2h (s h , s h+1 |M T )|(s h , s ′ 0 ))|π, s 1 = E H h=1 Var s ′ ∼P h (s h ) (V π 2h (s h , s ′ |M T ))|π, s 1 = E H h=1 Var s ′ ∼P h (s h ) (V T,π h (s h , s ′ |M))|π, s 1 .Using again the identityV π 1 (s 1 , s ′ 0 |M T ) = V T,π 1 (s 1 |M) leads to the desired result.Finally, prove a value-difference lemma also for transition lookaheadLemma 11 (Value-Difference Lemma with Transition Lookahead). Let M 1 = (S, A, H, P 1 , R 1 ) and M 2 = (S, A, H, P 2 , R 2 ) be two environments. For any deterministic one-step transition lookahead policy π ∈ Π T , any h ∈ [H] and s ∈ S, it holds thatV T,π h (s|M 1 ) -V T,π h (s|M 2 ) = E M1 r 1 h (s h , π h (s h , s ′ h+1 )) -r 2 h (s h , π h (s h , s ′ h+1 ))|s h = s + E M1 V T,π h+1 (s h+1 |M 1 ) -V T,π h+1 (s h+1 |M 2 )|s h = s + E M1 E s ′ ∼P 1 h (s h ) V T,π h (s h , s ′ |M 2 ) -E s ′ ∼P 2 h (s h ) V T,π h (s h , s ′ |M 2 ) |s h = s .where V T,π h (s, s ′ |M) is the value at a state given the reward realization, defined in Equation (7) and given in Remark 2.Proof. We again work with the extended MDPs M T 1 , M T 2 and use their Bellman equations, namely,V π 2h (s, s ′ |M T ) = r h (s, π(s, s ′ )) + V * 2h+1 (s ′ (π h (s, s ′ )), s ′ 0 |M T ), ∀h ∈ [H], s ∈ S, s ′ ∈ S A , V π 2h-1 (s, s ′ 0 |M T ) = E s ′ ∼P h (s) V π 2h (s, s ′ |M T ) , ∀h ∈ [H], s ∈ S.Using the relation between the value of the original and extended MDP (eq. ( 7)) and the Bellman equations of the extended MDP, for any h ∈ [H], we haveEQUATION)Denoting a h = π h (s h , s ′ h+1 ) the action taken by the agent at environment M 1 , We haveV π 2h (s h , s ′ h+1 |M T 1 ) -V π 2h (s h , s ′ h+1 |M T 2 ) = r 1 h (s h , a h ) + V π 2h+1 (s ′ h+1 (a h ), s ′ 0 |M T 1 ) -r 2 h (s h , a h ) + V π 2h+1 (s ′ h+1 (a h ), s ′ 0 |M T 2 ) = r 1 h (s h , a h ) -r 2 h (s h , a h ) + V T,π h+1 (s ′ h+1 (a h )|M 1 ) -V T,π h+1 (s ′ h+1 (a h )|M 2 ),when taking the expectation w.r.t. M 1 , it holds that s ′ h+1 (a h ) = s h+1 ; substituting this back into Equation ( 9), we get for s ∈ S do 6:V π h (s|M 1 ) -V π h (s|M 2 ) = E M1 r 1 h (s h , a h ) -r 2 h (s h , a h ) + V T,π h+1 (s ′ h+1 (a h )|M 1 ) -V T,π h+1 (s ′ h+1 (a h )|M 2 )|s h = s + E s ′ ∼P 1 h (s) V T,π h (s, s ′ |M 2 ) -E s ′ ∼P 2 h (s) V T,π h (s, s ′ |M 2 ) = E M1 r 1 h (s h , π h (s h , s ′ h+1 )) -r 2 h (s h , π h (s h , s ′ h+1 ))|s h = s + E M1 V T,π h+1 (s h+1 |M 1 ) -V T,π h+1 (s h+1 |M 2 )|s h = s + E M1 E s ′ ∼P 1 h (s h ) V T,π h (s h , s ′ |M 2 ) -E s ′ ∼P 2 h (s h ) V T,π h (s h , s ′ |M 2 ) |s h = s .if n k-1 h (s) = 0 then 7: V k h (s) = H 8: else 9:Calculate the truncated valuesV k h (s) = min      1 n k-1 h (s) n k-1 h (s) t=1 max a∈A rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′k t h (s) h+1 (s, a)) + b p k,h (s), H      10: end if 11:For any set of next-states s ′ ∈ S A , define the policy π kπ k h (s, s ′ ) ∈ arg max a∈A rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′ (a))12:end for 13:end for 14:for h = 1, 2, . . . H do 15:Observe s k h and s ′k h+1 = s ′k h+1 (s k h , a) a∈A 16:Play an actiona k h = π k h (s k h , s ′k h ) 17: Collect the reward R k h ∼ R h (s k h , a k h ) and transition to the next state s k h+1 = s ′k h+1 (s k h , a k h ) 18: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., 2021b] , described in Algorithm 4. For the bonuses, we use the notationV k h (s, s ′ ) = max a∈A rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′ (a)and define the following bonuses:b r k,h (s, a) = min L k δ n k-1 h (s, a) ∨ 1 , 1 , b p k,h (s) = 20 3 Var s ′ ∼ P k-1 h (s) ( V k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 400 3 HL k δ n k-1 h (s) ∨ 1 , where L k δ = ln 16S 3 A 2 Hk 2 (k+1) δ and Var s ′ ∼ P k-1 h (s) ( V k h (s, s ′ )) = E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) 2 -E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) 2 .The notation k t h (s) again represents the t th episode where the state s was visited at the h th timestep; in particular, line 9 of the algorithm is the expectation w.r.t. the empirical reward distribution P k-1 h (s). Since the transition bonus is larger than H when n k-1 h (s) = 0, we can arbitrarily define the expectation w.r.t. P k-1 h (s) when n k-1 h (s) = 0 to be 0, and one could write the update in a more concise way asV k h (s) = min E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) + b p k,h (s), H . 
comparing the values of lookahead agents and vanilla rl agents: 
 In the classic RL formulation [e.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 byV π h (s) = E H t=h r t (s t , π t (s t )|s h = s , where π ∈ Π M = {π : [H] × S → ∆ A } is a Markovian policy. The optimal value is V no h (s) = max π∈Π M V π h (s) and the regret is classically defined as Reg(K) = K k=1 V no 1 (s k 1 ) -V π k 1 (s k 1 ).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-lookahead counterpart. In other words, denoting the value gain due to lookahead information byG R (s) = V R, * 1 (s) -V no 1 (s) and G T (s) = V T, * 1 (s) -V no 1 (s), it holds that G R (s), G T (s) ≥ 0.In terms of regret, for any fixed algorithm, we can also writeReg(K) = Reg R (K) - K k=1 G R (s k 1 ) = Reg T (K) - K k=1 G T (s k 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, G R (s), G T (s) ≥ G 0 > 0. When this happens, any algorithm with sub-linear lookahead regret enjoys a negative linear standard regret:If Reg R (K) = o(K) and G R (s k 1 ) ≥ G 0 for all k ∈ [K], then Reg(K) ≤ -G 0 K + 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 Reg(K) ≥ 0 and G R (s k 1 ) ≥ G 0 for all k ∈ [K], then Reg R (K) ≥ G 0 K.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 is significant, one for reward lookahead and another for transition lookahead. Actions in the terminal state s f yield no reward. Without observing the rewards, agents will arbitrarily move from s i to s f , obtaining a reward V no = 1 /(A-1)H in expectation. On the other hand, when agents observe the rewards before acting, they should move from s i to s f only if a reward was realized for some action (and otherwise, stay in s i by playing a 1 ). Such agents will have (A-1)H opportunities to observe a unit reward across all timesteps and actions, collecting in expectation V R, * = (1 -1 /(A-1)H) (A-1)H ≥ 1 -1 /e. In other words, just by observing the rewards before acting, the agent's value multiplicatively increases by almost V R, * /V no ≈ AH. Moreover, the additive value gain is G R ≈ 1 -1 /e, so sub-linear lookahead regret with reward information results with a negatively-linear standard regret of Reg(K) ≲ -(1 -1 /e)K.Transition lookahead. Consider a chain of H/2 states (also described in further detail at Appendix 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 a 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 no = O(HA -H/2 ) rewards, while transition lookahead agents can collect V T, * = Ω(H); as such, lookahead agents achieve exponential increase in value, and sublinear regret versus the best lookahead agent will yield a standard regret of Reg(K) ≲ -HK.In the following sections, we will present agents that are guaranteed to always achieve sublinear regret compared to the best lookahead agent. 
planning and learning with one-step reward lookahead: 
 In this section, we analyze RL settings with one-step reward lookahead, in which immediate rewards are observed before choosing an 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 a value, the agent decides whether to take it as a 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 revenue can decrease by a factor of H. Notably, the example presented in Figure 1 is a small variant of the prophet problem, where the agent can either take one of A -1 values and finish the interaction or discard them and continue playing by staying at s i ; we showed that for this example, the lookahead information increases the value by a factor of V R, * /V no ≈ 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 a great cost. Even for Bernoulli rewards, there are 2 A possible reward combinations at any given state, and the augmentation increases the state space by this factor -leading to 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 satisfiesV R, * H+1 (s) = 0, ∀s ∈ S, V R, * h (s) = E R∼R h (s) max a∈A R h (s, a) + s ′ ∈S P h (s ′ |s, a)V R, * h+1 (s ′ ) , ∀s ∈ S, h ∈ [H].Also, given reward observations R = {R(a)} a∈A at state s and step h, the optimal policy isπ * h (s, R) ∈ arg max a∈A R(a) + s ′ ∈S P h (s ′ |s, a)V R, * h+1 (s ′ ) .We prove Proposition 1 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 s h × 0, while at even steps 2h, the state is s h × R h . Doing so creates an overlap between the values of the original and augmented environments at 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 et al., 2019b] .We remark that calculating the exact value is not always tractable -even for S = H = 1 (bandit problems) and Gaussian rewards, Proposition 1 requires calculating the expectation of the maximum Algorithm 1 Monotonic Value Propagation with Reward Lookahead (MVP-RL)1: Require: δ ∈ (0, 1), bonuses b r k,h (s), b p k,h (s, a) 2: for k = 1, 2, ... do 3: Initialize V k H+1 (s) = 0 4: for h = H, H -1, .., 1 do 5:Calculate the truncated values for all s ∈ SV k h (s) = min E R∼ Rk-1 h (s) max a∈A R(a) + b p k,h (s, a) + P k-1 h V k h+1 (s, a) + b r k,h (s), H 6:end for 7:for h = 1, 2, . . . H do 8: Observe s k h and R k h (s k h , a) for all a ∈ A 9:Play an actiona k h ∈ arg max a∈A R k h (s k h , a) + b p k,h (s k h , a) + P k-1 h V k h+1 (s k h , a) 10: Collect the reward R k h (s k h , a k h ) and transition to the next state s k h+1 ∼ P h (•|s k h , a k h ) 11:end for 12: 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 it can be used to achieve tight regret bounds when the environment is unknown.We now present a tractable algorithm that achieves tight regret bounds with one-step reward lookahead. Specifically, we modify the Monotonic Value Propagation (MVP) algorithm [Zhang et al., 2021b] 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 in 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 Zhang 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 to encourage reward exploration at the action level.A high-level description of the algorithm is presented in Algorithm 1, while the full algorithm and its bonuses are 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 1. When running MVP-RL, with probability at least 1 -δ uniformly for allK ≥ 1, it holds that Reg R (K) ≤ O √ H 3 SAK ln SAHK δ + H 3 S 2 A ln SAHK δ 2 .See proof in Appendix B.7. Remarkably, our upper bound matches the standard lower bound for episodic RL of et al., 2021] up to log-factors; this lower bound is proved for known deterministic rewards, so in particular, it also holds for problems with reward lookahead.Ω √ H 3 SAK [DominguesTo our knowledge, the only comparable bounds in settings with reward lookahead were proven to prophet problems; as agents observe (up to) n distributions at a fixed order, it can be formulated as a deterministic chain-like MDP, with H = n, S = n + 1 and A = 2. Agents start at the head of the chain and can either advance without collecting a 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 a regret bound of Õ(n 3 √ K) (albeit requiring a weaker form of feedback), and [Agarwal et al., 2023] proved a bound of Õ(n √ T ) -slightly better than ours, but heavily relies on the ability to control which distributions to observe, which is a specific instance of deterministic transitions. We are unaware of any previous results that cover general Markovian dynamics.When analyzing the regret of RL algorithms, a key step usually involves bounding the difference between the value of a policy in two different environments ('value-difference lemma'). In particular, for a given policy π k , many algorithms maintain a confidence interval on the valueV π k h (s) ∈ V k h (s), V k h (s), calculated based on optimistic and pessimistic MDPs that use the empirical model with bonuses/penalties [Dann et al., 2019 , Zanette and Brunskill, 2019 , Efroni et al., 2021] . Then, the instantaneous regret (without lookahead) is bounded using the optimistic values byV k h (s h ) -V π k h (s h ) = rk-1 h (s h , a h ) -r h (s h , a h ) + P k-1 h -P h V k h (s h , a h ) + P h V k h+1 -V π k h+1 (s h , a h ) + bonuses,while the pessimistic values are used either as part of the bonuses or while bounding them. However, when trying to perform a similar decomposition with reward lookahead, we do not have the difference of expected rewards, but rather terms of the formE R∼ Rk-1 h (s h ) R(π k h (s h , R)) -E R∼R h (s h ) R(π k h (s h , R))(see, e.g., the last term of Lemma 4 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 P V ∈ [0, H] A (as a function of the action at a given state), it holds w.h.p. thatEQUATION)Throughout the proof, whenever we face an expectation w.r.t. the empirical rewards, we reformulate the expression to fit the form of Equation (1) and use it as a '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 or in its analysis. In contrast to the optimistic ones, the pessimistic values are not calculated via value iteration, but rather by following the policy π k in the pessimistic environment. As such, they cannot be easily manipulated to fit the form in Equation (1).The analysis of the transitions adapts the techniques in [Efroni et al., 2021] , while requiring extra care in handling the dependence of actions in the rewards. 
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., 2018] . In this problem, an agent wants to navigate on a graph as fast as possible from a source to a target, but observes which edges at a node are available only upon reaching this node. When edge availability is stochastic and resampled every time a 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 3 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 is exponentially larger than the standard value, and any lookahead agent with low regret would greatly surpass no-lookahead agents.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 A , 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 transition-lookahead optimal values can be calculated using the following Bellman equations: Proposition 2. The optimal value of one-step transition lookahead agents satisfiesV T, * H+1 (s) = 0, ∀s ∈ S, V T, * h (s) = E s ′ ∼P h (s) max a∈A r h (s, a) + V T, * h+1 (s ′ (s, a)) , ∀s ∈ S, h ∈ [H].Also, given next-state observations s ′ = {s ′ (a)} a∈A at state s and step h, the optimal policy isπ * h (s, s ′ ) ∈ arg max a∈A r h (s, a) + V T, * h+1 (s ′ (a)) .The proof can be found at 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 s h × s ′ 0 (for an arbitrary fixed s ′ 0 ∈ S A ) and even steps with the state s h × s ′ h+1 . Beyond planning, this again allows proving a variant of the LTV and of a value-difference lemma.One important insight is that the policy π * h (s, s ′ ) admits the form of a list. Namely, consider the values V * h (s, s ′ , a) = r h (s, a) + V T, * h+1 (s ′ ) and assume some ordering of next-state-action pairs{(s ′ i , a i )} SA i=1 such that V * h (s, s ′ 1 , a 1 ) ≥ • • • ≥ V * h (s, s ′ SA , a SA ).Then, an optimal policy would look at all realized pairs (s ′ (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 on 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, a 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) ∈ S ×A and impose a 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.1 for details), and otherwise, it can be approximated through sampling, as we do in learning settings.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 2; the full details can be found at Appendix C.3). This time, we estimate the empirical expected reward and add a standard Hoeffding-like 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, namelyb p k,h (s) ≈ Var s ′ ∼ P k-1 h (s) ( V k h (s, s ′ )) n k-1 h (s) ∨ 1 , V k h (s, s ′ ) = max a∈A rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′ (a) .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., 2017] , so this variance naturally arises. The bonus is again designed to be monotone, as in 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 is polynomial, even if the precise joint distribution is complex. The algorithm enjoys the following regret bounds: Theorem 2. When running MVP-TL, with probability at least 1 -δ uniformly for all K ≥ 1, it holds thatReg T (K) ≤ O √ H 2 SK √ H + √ A ln SAHK δ + H 3 S 4 A 3 ln SAHK δ 2 .Algorithm 2 Monotonic Value Propagation with Transition Lookahead (MVP-TL)1: Require: δ ∈ (0, 1), bonuses b r k,h (s, a), b p k,h (s) 2: for k = 1, 2, ... do 3: Initialize V k H+1 (s) = 0 4: for h = H, H -1, .., 1 do 5:Calculate the truncated values for all s ∈ S this is the rate due to reward stochasticity. Consider a problem where at odd timesteps 2h -1 and across all states, all actions have rewards of mean 1 /2 -ϵ, except for one action of mean 1 /2. Assuming that the state-distribution is uniform, each such timestep forms a hard instance of a contextual bandit problem with S contexts, exhibiting a regret of Ω( √ SAK) [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 Ω(H √ SAK). The even steps can be used to 'remove' the lookahead and create a uniform state distribution. To do so, we set that when taking an action at odd steps, we always transition to a fixed state s d . From this state, one action a 1 leads uniformly to all states, while the rest of the actions lead to an absorbing non-rewarding state -rendering them strictly suboptimal. Thus, no-regret agents will only play a 1 , regardless of the lookahead information, and the state distribution at odd timesteps will be uniform.EQUATIONTransition lookahead causes similar issues as reward lookahead. Hence, it is natural to apply a 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 a 'change of measure' tool between the empirical and real next-state distribution. In particular, if V (s, s ′ , a) represents the value starting from state s, performing a and transitioning to s ′ , one can show that for allEQUATIONwhere the variance term stems from using a Bernstein-like concentration bound. However, in contrast to the reward lookahead, the √ SA-factor propagates to the dominant term of the regret, so pursuing this approach would lead to a worse regret bound of Õ √ H 3 S 2 AK .To avoid this, we pinpoint the two locations where this change of measure is needed -the proof that V k h is optimistic and the regret decomposition -and make sure to perform this change of measure only on a single valueV * h (s, s ′ , a) = r h (s, a) + V * h+1 (s ′), mitigating the need to cover all possible values and removing the additional √ SA-factor. However, doing so leaves us with a residual term.Defining V * h (s, s ′ ) = max a∈A {V * h (s, s ′ (a), a)} and assuming a similar optimistic value V k h (s, s ′ ), this term is of the form E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) -V * h (s, s ′ ) -E s ′ ∼P h (s) V k h (s, s ′ ) -V * h (s, s ′) . While similar terms have been analyzed before [e.g., 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, it 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 a list of next-state-actions (s ′ , a). In other words, instead of looking at the next-state s ′ (with S A possible values) to determine a value, we look at the highest-ranked realized pair (s ′ , a) in the list that corresponds to the policy that induces the value (with SA possible rankings). Since we have two values, we need to calculate the probability of being at a certain list location for both π k and π * , but the cardinality of this space is (SA) 2 : 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 a strong baseline that also uses lookahead information. Our algorithms rely on estimating the distribution of the reward or transition observations, a concept that might be utilized in other settings. In particular, we believe that our techniques for transition lookahead could be extended to RL problems with stochastic action sets [Boutilier et al., 2018] , but leave this for future work.One natural extension to our work would be to consider multi-step lookahead information -observing the transition/rewards L steps in advance. We conjecture that from a 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 O(KS 2 AH) computations per episode due to the planning stage, while model-free algorithms might potentially allow just O(AH) computations per episode.On the practical side, previous works presented RL algorithms that utilize/estimate a 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 Jin et al. 2020 ) and can also be generalized to situations where lookahead information can be queried under some budget constraints [Efroni et al., 2021] or when agents only observe noisy lookahead predictions; we leave these problems for future research.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The paper is purely theoretical and studies a fundamental decision-making 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.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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Due to the theoretical nature of the paper and the generality of the model, it 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [NA] Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 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 concentration-related good event, we can prove that the planning procedure in the algorithm is 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, we 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 at the end of the regret analysis.For transition lookahead, the appendix includes one more part that further analyzes the example presented in Section 3.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.To simplify the proofs, we assume the following 'tabular' data-generation process: Before the game starts, a set of K samples from the transition probabilities and rewards is generated for all (s, a, h). Once a state s at step h is visited for the i th time, the i th sample from the reward distribution R h (s) is the reward realization for all action a ∈ A. When a state-action pair is visited for the i th time, the i th sample from the transition kernel P h (•|s, a) determines the next-state realization. In particular, it implies that the reward samples from the first i visits to a state are i.i.d., and the same for the next-states samples and state-action visitations. Throughout this appendix, we use the notationR k h = R k h (s k h, a a∈A to denote the reward observation at episode k and timestep h for all the actions.For the proof, we define the following three filtrations. LetF k,h = σ s 1 t , a 1 t , R 1 t t∈[H] , . . . , s k-1 t , a k-1 t , R k-1 t t∈[H] , s k t , a k t , R k t t∈[h] , s k h+1 , F R k,h = σ s 1 t , a 1 t , R 1 t t∈[H] , . . . , s k-1 t , a k-1 t , R k-1 t t∈[H] , s k t , a k t , R k t t∈[h+1],the filtrations that contains all information until episode k and step h, as well as the state at timestep h + 1, or all information of time h + 1, respectively. We make this distinction so thatF k,h-1 contains only s k h , while F R k,h-1 also contains a k h .We also defineF k = σ s 1 t , a 1 t , R 1 t t∈[H] , . . . , s k t , a k t , R k t t∈[H] , s k+1 1 ,which contains all information up to the end of the k th episode, as well as the initial state at episode k + 1.In this appendix, we present an 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. V R,π (s|M). Specifically in this subsection, we distinguish between values without lookahead (denoted V π ) and values with lookahead (denoted V R,π ). 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 R in the value notation.For any MDP M = (S, A, H, P, R), define an equivalent extended MDP M R 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 s 1 . The extended environment starts at a state s 1 × 0, where 0 ∈ R A is the zeros vector.Algorithm 3 Monotonic Value Propagation with Reward Lookahead (MVP-RL)1: Require: δ ∈ (0, 1), bonuses b r k,h (s), b p k,h (s, a) 2: for k = 1, 2, ... do 3: Initialize V k H+1 (s) = 0 4: for h = H, H -1, .., 1 do 5:for s ∈ S do 6:if n k-1 h (s) = 0 then 7: V k h (s) = H 8: else 9:Calculate the truncated valuesV k h (s) = min      1 n k-1 h (s) n k-1 h (s) t=1 max a∈A R k t h (s) h (s, a) + b p k,h (s, a) + P k-1 h V k h+1 (s, a) + b r k,h (s), H      10:end if 11:For any vector R ∈ R A , define the policy π kπ k h (s, R) ∈ arg max a∈A R(a) + b p k,h (s, a) + P k-1 h V k h+1 (s, a)12:end for 13:end for 14:for h = 1, 2, . . . H do 15: Observe s k h and R k h = R k h (s k h , a) a∈A 16:Play an actiona k h = π k h (s k h , R k h ) 17: Collect the reward R k h (s k h , a k h ) and transition to the next state s k h+1 ∼ P h (•|s k h , a k h ) 18:end for 19:Update the empirical estimators and counts for all visited state-actions 20: end for We use a variant of the MVP algorithm [Zhang et al., 2021b] while adapting their proof and the one from [Efroni et al., 2021 ]. The algorithm is described in Algorithm 3 and uses the following bonuses:b r k,h (s) = 3 AL k δ 2(n k-1 h (s) ∨ 1) , b p k,h (s, a) = min      20 3 Var P k-1 h (•|s,a) ( V k h+1 )L k δ n k-1 h (s, a) ∨ 1 + 400 9 HL k δ n k-1 h (s, a) ∨ 1 , H      where L k δ = ln 144S 2 AH 2 k 3 (k+1) δ, and for brevity, we shortenVar P k-1 h (•|s,a) ( V k h+1 (s ′ )) to Var P k-1 h (•|s,a) ( V k h+1) (omitting the state from the value).For the optimistic value iteration, we use the notation k t h (s) to represent the t th episode where the state s was visited at the h th timestep. Thus, line 9 of Algorithm 3 is the expectation w.r.t. the empirical reward distribution Rk-1 h (s) (when defining its realization to be zero when n k-1 h (s) = 0). Since the bonuses are larger than H when n k-1 h (s) = 0, one could write the update in more concisely asV k h (s) = min E R∼ Rk-1 h (s) max a∈A R(a) + b p k,h (s, a) + P k-1 h V k h+1 (s, a) + b r k,h (s), H .We will often use this representation in our analysis.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 u ∈ R A , denotem h (s, u) = E R∼R h (s) max a {R h (a) + u(a)} , mk h (s, u) = E R∼ Rk h (s) max a {R h (a) + u(a)}with the convention that mk h (s, u) = max a u(a) if n k h (s) = 0. We define the following good events:E p (k) = ∀s, s ′ , a, h : |P h (s ′ |s, a) -P k-1 h (s ′ |s, a)| ≤ 2P (s ′ |s, a)L k δ n k-1 h (s, a) ∨ 1 + L k δ n k-1 h (s, a) ∨ 1 E pv1 (k) = ∀s, a, h : P k-1 h -P h V * h+1 (s, a) ≤ 2Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + HL k δ n k-1 h (s, a) ∨ 1 E pv2 (k) = ∀s, a, h : Var P h (•|s,a) (V * h+1 ) -Var P k-1 h (•|s,a) (V * h+1 ) ≤ 4H L k δ n k-1 h (s, a) ∨ 1 E r (k) = ∀s, h, ∀u ∈ [0, 2H] A : m h (s, u) -mk-1 h (s, u) ≤ 3 AL k δ 2(n k-1 h (s) ∨ 1) where we again use L k δ = ln 144S 2 AH 2 k 3 (k+1) δ. Then, we define the first good event asG 1 = k≥1 E r (k) k≥1 E p (k) k≥1 E pv1 (k) k≥1 E pv2 (k),for which, the following holds: Lemma 5 (The First Good Event). The good event G 1 holds w.p. Pr(G 1 ) ≥ 1 -δ/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 k ≥ 1, s, a, h and number of visits n ∈ [k], we utilize Lemma 16 w.r.t. the transition kernel P h (•|s, a), the value V * h+1 ∈ [0, H] and probability δ ′ = δ 8SAHk 2 (k+1) ; notice that by the assumption that samples are 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 ∈ [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 k-1 h (s, a) ∈ {0 . . . , k}, and taking another union bound over all k ≥ 1, s, a, h ensures that each of the events∩ k≥1 E p (k), ∩ k≥1 E pv1 (k) and ∩ k≥1 E pv2 (k) holds w.p. at least 1 -δ 8We now focus on bounding the probability of the event ∩ k E r (k). For any fixed k, h and s, observe that the event trivially holds if n k h = 0, then the event trivially holds, since for all u ∈ [0, 2H] A ,m h (s, u) -mk-1 h (s, u) = E R∼R h (s) max a {R h (s, a) + u(a)} -max a {u(a)} ( * ) ≤ 1 ≤ 3 AL k δ 2 ,where ( * ) uses the boundedness of the rewards in [0, 1]. Next, recall that for any fixedn k-1 h = n ∈ [k],the rewards samples at state s and step h are i.i.d. vectors on [0, 1] A . Therefore, by Lemma 18,Pr n k-1 h (s) = n, ∀u ∈ [0, 2H] A : m h (s, u) -mk-1 h (s, u) > 3 AL k δ 2(n k-1 h (s) ∨ 1) ≤ δ 8SAHk 2 (k + 1).Taking a union bound on all possible values of n ∈ [k], s and h, we getPr{E r (k)} ≥ 1 -SAk • δ 8SAHk 2 (k + 1) ≥ 1 - δ 8k(k + 1).By summing over all k ≥ 1, the event ∩ k E r (k) holds with a probability of at least 1 -δ/8. Finally, taking the union bound with the other three events leads to the desired result of Pr(G 1 ) ≥ 1-δ/2.In this subsection, we prove that under the good event G 1 , the values V k that MVP-RL produces are optimistic.Lemma 6 (Optimism). Under the first good event G 1 , for all k ∈[K], h ∈ [H] and s ∈ S, it holds that V * h (s) ≤ V k h (s).Proof. The proof follows by backward induction on H; 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 ∈ [K] and h ∈ [H], the desired inequalities hold at timestep h + 1 for all s ∈ 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 k h (s) < H, and in particular, the value is not truncated; otherwise, by the boundedness of the rewards,V * h (s) ≤ H = V k h (s).For similar reasons, we assume w.l.o.g. that b p k,h (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 23), under the good event, we have for all s ∈ S and a ∈ A thatEQUATIONEQUATIONHL k δ n k-1 h (s, a) ∨ 1      (Lemma 23) ≥ P k-1 h V * h+1 (s, a) + 10 3 Var P k-1 h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + 200 9 HL k δ n k-1 h (s, a) ∨ 1 ≥ P k-1 h V * h+1 (s, a) + 10 3 Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + 8HL k δ n k-1 h (s, a) ∨ 1 (Under E pv2 (k)) ≥ P h V * h+1 (s, a). (Under E pv1 (k))Thus, under the good event and the induction hypothesis, we have thatV k h (s) = E R∼ Rh (s) max a∈A R(a) + b p k,h (s, a) + P k-1 h V k h+1 (s, a) + b r k,h (s) ≥ E R∼ Rh (s) max a∈A R(a) + P h V * h+1 (s, a) + b r k,h (s).In particular, using Proposition 1, we getV k h (s) -V * h (s) ≥ E R∼ Rh (s) max a∈A R(a) + P h V * h+1 (s, a) + b r k,h (s) -E R∼R h (s) max a∈A R(a) + P h V * h+1 (s, a) ≥ 0,where the last inequality holds under the event E r (k) with u(a) = P h V * h+1 (s, a) ∈ [0, H] A .In this subsection, we present four good events that will allow us to replace the expectation over the randomizations inside each episode with their realization.Define the following bonus-like term that will later appear in the proof due to value concentration:b pv1 k,h (s, a) = min 2Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + 4H 2 SL k δ n k-1 h (s, a) ∨ 1 , H ,and letY k 1,h := V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ), Y k 2,h = Var P h (•|s t,h ,a t,h ) (V π k h+1 ), Y k 3,h = b p k,h (s k h , a k h ) + b pv1 k,h (s k h , a k h ).The second good event is the intersection of the eventsG 2 = E diff1 ∩ E diff2 ∩ E Var ∩ E bp defined as follows. E diff1 = ∀h ∈ [H], K ≥ 1 : K k=1 E[Y k 1,h |F k,h-1 ] ≤ 1 + 1 2H K k=1 Y k 1,h + 18H 2 ln 8HK(K + 1) δ , E diff2 = ∀h ∈ [H], K ≥ 1 : K k=1 E[Y k 1,h |F R k,h-1 ] ≤ 1 + 1 2H K k=1 Y k 1,h + 18H 2 ln 8HK(K + 1) δ , E Var = K ≥ 1 : K k=1 H h=1 Y k 2,h ≤ 2 K k=1 H h=1 E[Y k 2,h |F k-1 ] + 4H 3 ln 8HK(K + 1) δ , E bp = ∀h ∈ [H], K ≥ 1 : K k=1 E[Y k 3,h |F k,h-1 ] ≤ 2 K k=1 Y k 3,h + 50H 2 ln 8HK(K + 1) δ ,We define the good event G = G 1 ∩ G 2 . Lemma 7. The good event G holds with a probability of at least 1 -δ.Proof. The proof follows similarly to Lemmas 15 and 21 of [Efroni et al., 2021] .First, define the random process W k = 1 V k h (s) -V π k h (s) ∈ [0, H], ∀h ∈ [H], s ∈ S and define Ỹ k 1,h = W k Y k 1,h , which is bounded in [0, H]. Also observe that W k is F k-1 measurable,δ 8HK(K+1) that K k=1 E[ Ỹ k 1,h |F k,h-1 ] ≤ 1 + 1 2H K k=1 Ỹ k 1,h + 18H 2 ln 8HK(K + 1) δ .Since W k is F k,h-1 measurable, we can write the event asK k=1 W k E[Y k 1,h |F k,h-1 ] ≤ 1 + 1 2H K k=1 W k Y k 1,h + 18H 2 ln 8HK(K + 1) δ ,and taking the union bound over all h ∈ [H] and K ≥ 1, we get w.p. at least 1 -δ 8 that the eventẼdiff1 = ∀h ∈ [H], K ≥ 1 : K k=1 W k E[Y k 1,h |F k,h-1 ] ≤ 1 + 1 2H K k=1 W k Y k 1,h + 18H 2 ln 8HK(K + 1) δ .Importantly, by optimism (Lemma 6), under G 1 , it holds that W k = 1 for all k ≥ 1, so we immediately get thatG 1 ∩ Ẽdiff1 = G 1 ∩ E diff1 .Following the exact same proof just with the filtration F R k,h and defining the equivalent Ẽdiff2 , we get that this event also holds w.p. 1 -δ 8 and is the desired event when G 1 holds. Next, we prove that the other two events also hold w.p. at least 1 -δ 8 . By the assumptions of our setting, we know that V π k h (s) ∈ [0, H], and soH h=1 Y k 2,h = H h=1 Var P h (•|s t,h ,a t,h ) (V π k h+1 ) ∈ [0, H 3 ].In particular, applying Lemma 25 (w.r.t. the filtration F k ) with C = H 3 and any fixed K, we get w.p.1 - δ 8HK(K+1) that K k=1 H h=1 Y k 2,h ≤ 2 K k=1 H h=1 E[Y k 2,h |F k-1 ] + 4H 3 ln 8HK(K + 1) δ .Taking the union bound on all possible values of K ≥ 1 proves that E Var holds w.p. at least 1 -δ 8 . Similarly, by definition, we have thatY k 3,h = b p k,h (s k h , a k h ) + b pv1 k,h (s k h , a k h ) ∈ [0, 2H] and is F k,h measurable. Thus, for any fixed k ≥ 1 and h ∈ [H], using Lemma 25, we have w.p. 1 -δ 8HK(K+1) that K k=1 E[Y k 3,h |F k,h-1 ] ≤ 1 + 1 4H K k=1 Y k 3,h + 50H 2 ln 8HK(K + 1) δ ≤ 2 K k=1 Y k 3,h + 50H 2 ln 8HK(K + 1) δ ,applying the union bound on all K ≥ 1, the event E bp holds w.p. 1 -δ 8 . To summarize, we have that the event G 1 holds w.p. 1 -δ 2 (Lemma 5), and we proved that the events Ẽdiff1 , Ẽdiff2 , E Var , E bp hold each w.p. 1 -δ 8 , so we also have that the eventG = G 1 ∩ G 2 = G 1 ∩ E diff1 ∩ E diff2 ∩ E Var ∩ E bp = G 1 ∩ Ẽdiff1 ∩ Ẽdiff2 ∩ E Var ∩ E bpholds w.p. at least 1 -δ.We finally analyze the regret of the algorithm Theorem 1. When running MVP-RL, with probability at least 1 -δ uniformly for allK ≥ 1, it holds that Reg R (K) ≤ O √ H 3 SAK ln SAHK δ + H 3 S 2 A ln SAHK δ 2 .Proof. Assume that the good events G holds, which by Lemma 7, happens with probability at least 1 -δ. Then, by optimism (Lemma 6), for any k ∈ [K], h ∈ [H] and s ∈ S, it holds that V * h (s) ≤ V k h (s). Moreover, we can lower bound the value of the policy π k as follows (see Remark 1):EQUATIONRelation (1) is by the definition of π k (see Algorithm 3), while (2) holds under the good event E r (k) with u(a) = P k-1 h V k h+1 (s, a) + b p k,h (s, a) ∈ [0, 2H] (due to the value and bonus truncation). Finally, (3) is by the definition of V k h (s), where the inequality also accounts for its possible truncation. To further bound this, we need to boundP k-1 h V k h+1 (s, a) -P h V π k h+1 (s, a) = P h V k h+1 -V π k h+1 (s, a) + P k-1 h -P h V k h+1 (s, a) = P h V k h+1 -V π k h+1 (s, a) + P k-1 h -P h V * h+1 (s, a) + P k-1 h -P h V k h+1 -V * h+1 (s, a).The first error term can be bounded under the good event, while the second using Lemma 24. More formally, under the good event E pv1 (k), we haveP k-1 h -P h V * h+1 (s, a) ≤ 2Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + HL k δ n k-1 h (s, a) ∨ 1, and by Lemma 24 with α = 4H (using andP 1 = P h , P 2 = P k-1 h , under E p (k)), P k-1 h -P h V k h+1 -V * h+1 (s, a) ≤ 1 4H E P h (•|s,a) V k h+1 (s ′ ) -V * h+1 (s ′ ) + HSL k δ (1 + 4H • 2/4) n k-1 h (s, a) ∨ 1 ≤ 1 4H E P h (•|s,a) V k h+1 (s ′ ) -V π k h+1 (s ′ ) + 3H 2 SL k δ n k-1 h (s, a) ∨ 1 = 1 4H P h V k h+1 -V π k h+1 (s, a) + 3H 2 SL k δ n k-1 h (s, a) ∨ 1 ,where the second inequality is since the value of π k cannot exceed the optimal value.Since under the good event by Lemma 6, we have 0≤ V π k h+1 (s ′ ) ≤ V * h+1 (s ′ ) ≤ V k h+1 (s ′) ≤ H, we can trivially bound the error by H and boundP k-1 h V k h+1 (s, a) -P h V π k h+1 (s, a) ≤ min        1 + 1 4H P h V k h+1 -V π k h+1 (s, a) ≥0 + 3H 2 SL k δ n k-1 h (s, a) ∨ 1 + 2Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + HL k δ n k-1 h (s, a) ∨ 1 , H        ≤ 1 + 1 4H P h V k h+1 -V π k h+1 (s, a) + min 2Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + 4H 2 SL k δ n k-1 h (s, a) ∨ 1 , H ≜ 1 + 1 4H P h V k h+1 -V π k h+1 (s, a) + b pv1 k,h (s, a).Substituting back to Equation ( 6) while writing the linear operation P h V (s, a) as an expectation and letting the action bea h = π k h (s, R), we get under G for all k ∈ [K], h ∈ [H] and s ∈ S that V k h (s) -V π k h (s) ≤ E R∼R h (s) P k-1 h V k h+1 (s, π k h (s, R)) -P h V π k h+1 (s, π k h (s, R)) + b p k,h (s, π k h (s, R)) + 2b r k,h (s) ≤ E R∼R h (s) 1 + 1 4H E V k h+1 (s h+1 ) -V π k h+1 (s h+1 )|s h = s, a h (s, a) + b pv1 k,h (s, a h ) + b p k,h (s, a h ) + 2b r k,h (s) = E 1 + 1 4H V k h+1 (s h+1 ) -V π k h+1 (s h+1 ) + b p k,h (s h , a h ) + b pv1 k,h (s h , a h )|s h = s, π k + 2b r k,h (s).Next, taking s = s k h , the action a h = π k h (s, R) becomes a k h , and summing on all k, we can rewriteK k=1 V k h (s k h ) -V π k h (s k h ) ≤ K k=1 E 1 + 1 4H V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + b p k,h (s k h , a k h ) + b pv1 k,h (s k h , a k h )|F k,h-1 + 2 K k=1 b r k,h (s k h ) (1) ≤ 1 + 1 2H 1 + 1 4H K k=1 V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + 2 K k=1 b p k,h (s k h , a k h ) + b pv1 k,h (s k h , a k h ) + 2 K k=1 b r k,h (s k h ) + 68H 2 ln 8HK(K + 1) δ (2) ≤ 1 + 1 2H 1 + 1 4H K k=1 V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + 1 4H 1 + 1 2H K k=1 V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + 18 K k=1 Var P h (•|s k h ,a k h ) (V π k h+1 )L k δ n k-1 h (s k h , a k h ) ∨ 1 + K k=1 1620H 2 SL k δ n k-1 h (s k h , a k h ) ∨ 1 + 68H 2 ln 8HK(K + 1) δ + 2 K k=1 b r k,h (s k h ) ≤ 1 + 1 2H 2 K k=1 V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + 18 K k=1 L k δ Var P h (•|s k h ,a k h ) (V π k h+1 ) n k-1 h (s k h , a k h ) ∨ 1 + K k=1 1700H 2 SL k δ n k-1 h (s k h , a k h ) ∨ 1 + 6 K k=1 AL k δ 2n k-1 h (s) ∨ 1where inequality (1) holds when both E diff1 and E bp occur and inequality (2) is by Lemma 8. In the last inequality, we also substituted the definition of the reward bonus. Recursively applying this inequality up to h = H + 1 (where both values are zero), w.p. at least 1 -δ, we getReg R (K) ≤ K k=1 V * 1 (s k 1 ) -V π k 1 (s k 1 ) ≤ K k=1 V k 1 (s k 1 ) -V π k 1 (s k 1 ) (Lemma 6) ≤ 18 1 + 1 2H 2H K k=1 L k δ Var P h (•|s k h ,a k h ) (V π k h+1 ) n k-1 h (s k h , a k h ) ∨ 1 + 1 + 1 2H 2H K k=1 1700H 2 SL k δ n k-1 h (s k h , a k h ) ∨ 1 + 6 1 + 1 2H 2H K k=1 AL k δ 2n k-1 h (s) ∨ 1 ( * ) ≤ 100 √ H 3 SAKL K δ + 50 √ 2SAH 2 L K δ 1.5 + 5000H 2 SL K δ • SAH(2 + ln(K)) + 12 AL K δ SH + 2 √ SH 2 K = O √ H 3 SAKL K δ + H 3 S 2 A(L K δ ) 2 .Relation ( * ) is by Lemma 9 and Lemma 20.Lemma 8. Conditioned on the good event G, for any h ∈ [H], it holds thatK k=1 b p k,h (s k h , a k h ) + b pv1 k,h (s k h , a k h ) ≤ 1 8H 1 + 1 2H K k=1 V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + 9 K k=1 Var P h (•|s k h ,a k h ) (V π k h+1 )L k δ n k-1 h (s k h , a k h ) ∨ 1 + K k=1 810H 2 SL k δ n k-1 h (s k h , a k h ) ∨ 1 .Proof. We start by analyzing each of the terms separately. First, we apply Lemma 22 with α = 20 3 • 32HL k δ , noting that under the good event (by Lemma 6),EQUATIONs) ≤ H and using the event E pv ; doing so yieldsb p k,h (s, a) ≤ 20 3 Var P k-1 h (•|s,a) ( V k h+1 )L k δ n k-1 h (s, a) ∨ 1 + 400 9 HL k δ n k-1 h (s, a) ∨ 1 ≤ 20 L k δ Var P h (•|s,a) (V π k h+1 ) 3 n k-1 h (s, a) ∨ 1 + 1 32H P h V k h+1 -V π k h+1 (s, a) + 1 32H P k-1 h V k h+1 -V π k h+1 (s, a) + 6400H 2 L k δ 9n k-1 h (s, a) ∨ 1 + 20 3 4HL k δ n k-1 h (s, a) ∨ 1 + 400 9 HL k δ n k-1 h (s, a)∨ 1 Using Lemma 24 with α = 1, under the good event E p (k) and for any s, a, we can further boundP k-1 h V k h+1 -V π k h+1 (s, a) = P h V k h+1 -V π k h+1 (s, a) + P k-1 h -P h V k h+1 (s ′ ) -V π k h+1 (s, a) ≤ P h V k h+1 -V π k h+1 (s, a) + P h V k h+1 -V π k h+1 (s, a) + HSL k δ (1 + 2 • 1/4) n k-1 h (s, a) ∨ 1 (Lemma 24) ≤ 2P h V k h+1 -V π k h+1 (s, a) + 1.5HSL k δ n k-1 h (s, a) ∨ 1 Thus, we get the overall bound b p k,h (s, a) ≤ 20 L k δ Var P h (•|s,a) (V π k h+1 ) 3 n k-1 h (s, a) ∨ 1 + 3 32H P h V k h+1 -V π k h+1 (s, a) + 785H 2 SL k δ n k-1 h (s, a) ∨ 1For the second bonus, we apply Lemma 21 w.r.t.V π k h+1 (s) ≤ V * h+1 (s) and α = 32 2L k δ H and get b pv1 k,h (s, a) ≤ 2Var P h (•|s,a) (V * h+1 )L k δ n k-1 h (s, a) ∨ 1 + 4H 2 SL k δ n k-1 h (s, a) ∨ 1 ≤ 2Var P h (•|s,a) (V π k h+1 )L k δ n k-1 h (s, a) ∨ 1 + 1 32H P h V * h+1 -V π k h+1 (s, a) + 16HL k δ n k-1 h (s, a) + 4H 2 SL k δ n k-1 h (s, a) ∨ 1 ≤ 2Var P h (•|s,a) (V π k h+1 )L k δ n k-1 h (s, a) ∨ 1 + 1 32H P h V k h+1 -V π k h+1 (s, a) + 20H 2 SL k δ n k-1 h (s, a)∨ 1 where we again used the optimism. Combining both and summing over all k, we getK k=1 b p k,h (s k h , a k h ) + b pv1 k,h (s k h , a k h ) ≤ 9 K k=1 Var P h (•|s k h ,a k h ) (V π k h+1 )L k δ n k-1 h (s k h , a k h ) ∨ 1 + 1 8H K k=1 P h V k h+1 -V π k h+1 (s k h , a k h ) + K k=1 805H 2 SL k δ n k-1 h (s k h , a k h ) ∨ 1Finally, under the good event E diff2 , it holds thatK k=1 P h V k h+1 -V π k h+1 (s k h , a k h ) = K k=1 E V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 )|F R k,h-1 ≤ 1 + 1 2H K k=1 V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) + 18H 2 ln 8HK(K + 1) δ .Substituting this relation back concludes the proof.Lemma 9. Under the event E Var it holds thatK k=1 H h=1 Var P h (•|s k h ,a k h ) (V π k h+1 ) n k-1 h (s k h , a k h ) ∨ 1 ≤ 2 H 3 SAKL K δ + √ 8SAH 2 L K δ .Proof. Following Lemma 24 of [Efroni et al., 2021] , by Cauchy-Schwartz inequality, it holds thatK k=1 H h=1 Var P h (•|s k h ,a k h ) (V π k h+1 ) n k-1 h (s k h , a k h ) ∨ 1 ≤ K k=1 H h=1 Var P h (•|s k h ,a k h ) (V π k h+1 ) K k=1 H h=1 1 n k-1 h (s k h , a k h ) ∨ 1 .The second term can be bounded by Lemma 20, namely,K k=1 H h=1 1 n k-1 h (s k h , a k h ) ∨ 1 ≤ SAH(2 + ln(K)).We further focus on bounding the first term. Under E Var , we haveK k=1 H h=1 Var P h (•|s k h ,a k h ) (V π k h+1 ) ≤ 2 K k=1 E H h=1 Var P h (•|s k h ,a k h ) (V π k h+1 )|F k-1 + 4H 3 ln 8HK(K + 1) δ (Under E Var ) ≤ 2 K k=1 E   H h=1 R h (s k h , a k h ) -V π k 1 (s k 1 ) 2 |F k-1   + 4H 3 ln 8HK(K + 1) δ (By Lemma 3) ≤ 2H 2 K + 4H 3 ln 8HK(K + 1) δ ,where the last inequality is since both the values and cumulative rewards are bounded in [0, H].Combining both, we getK k=1 H h=1 Var P h (•|s k h ,a k h ) (V π k h+1 ) n k-1 h (s k h , a k h ) ∨ 1 ≤ 2H 2 K + 4H 3 ln 8HK(K + 1) δ SAH(2 + ln(K)) ≤ 2H 2 K + 4H 3 ln 8HK(K + 1) δ 2SAH ln 8HK(K + 1) δ ≤ 2 H 3 SAKL K δ + √ 8SAH 2 L K δ .As for the reward transition, we also assume that all data was generated before the game starts for all state-action-timesteps, and it is given to the agent when the relevant (s, a, h) is visited. Thus, the rewards and next-state from the first i th visits at a state (or a state-action pair) at a certain timestep are i.i.d.Throughout this appendix, we use the notation s ′k h+1 = s ′k h+1 (s k h , a) a∈A to denote the next-state observations at episode k and timestep h for all the actions, and use the equivalent filtrations to the ones defined at Appendix B.1, namelyF k,h = σ s 1 t , a 1 t , s ′1 t+1 , R 1 t t∈[H] , . . . , s k-1 t , a k-1 t , s ′k-1 t+1 , R k-1 t t∈[H] , s k t , a k t , s ′k t+1 , R k t t∈[h] , F k = σ s 1 t , a 1 t , s ′1 t+1 t∈[H] , . . . , s k t , a k t , s ′k t+1 , R k t t∈[H] , s k+1 1 .In particular, notice that since both s ′k h+1 and a k h are F k,h measurable, then so does s k h+1 .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 to apply various existing results on MDPs without the need to reprove them. We follow the same conventions as Appendix B.2 while denoting transition lookahead values by V T,π (s|M) (and again, the superscript T will be omitted in subsequent subsections).For any MDP M = (S, A, H, P, R), let M T be an MDP of horizon 2H and state space S A+1 that separates the state transition and next-state generation as follows:1. Assume w.l.o.g. that M starts at some initial state s 1 . The extended environment starts at a state s 1 × s ′ 0 , where s ′ 0 ∈ S A is a vector of A copies of some arbitrary state s 0 ∈ S.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 ′ ∈ S A , 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 A -dimensional to a dimension of SA.We start by defining the values starting from state s ∈ S, playing a ∈ A and transitioning to s ′ ∈ S, denoted byV π h (s, s ′ , a) = r h (s, a) + V π h+1 (s ′ ), V * h (s, s ′ , a) = r h (s, a) + V * h+1 (s ′ ), V k h (s, s ′ , a) = rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′ ),We similarly define (consistently with Remark 2)V π h (s, s ′ ) = V π h (s, s ′ (π h (s, s ′ )), π h (s, s ′ )), V * h (s, s ′ ) = max a V * h (s, s ′ (a), a),and ,V k h (s, s ′ ) = max a V k h (s, s ′ (a), a).List representation. We now move to defining lists of next-state-actions and distributions with respect to such lists. Let ℓ be a list that orders all next-state-action pairs from (s ′ ℓ(1) , a ℓ(1) ) to (s ′ ℓ(SA) , a ℓ(SA) ) and define the set of all possible lists to be L (with |L| = (SA)!). Also, define ℓ u , the list induced by a function u :S × A → R such that u(s ′ ℓ u (1) , a ℓ u (1) ) ≥ • • • ≥ u(s ′ ℓ u (SA) , a ℓ u (SA) ), where ties are 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 (s ′ 1 , a 1 ), . . . , (s ′ SA , a SA ). We now define the probability of list elements. Denote by E ℓ i the event that the highest-ranked realized element in the list is element i, namelyEQUATIONThen, for a probability measure P on S A , define µ(i|ℓ, P ) = P (s ′ ∈ E ℓ i ). Notably, when the list is induced by u and element i is the realized highest-ranked elements, we can write max a u(s ′ (a), a) = u(s ′ i , a i ), so we have that (e.g. by Lemma 17 with f (s ′ ) = max a u(s ′ (a), a))E s ′ ∼P h (s) max a {u(s ′ (a), a)} = E i∼µ(•|ℓ,P h (s)) [u(s ′ i , a i )]We also denote by μk h (i|s; ℓ) =1 n k h (s)∨1 K t=1 1 s t h = s, s ′t h+1 ∈ E ℓ i, the empirical probability for a list location i to be the highest-realized ranking according to a list ℓ at state s and step h, based on samples up to episode k; We have by Lemma 17 that μk h (i|s; ℓ) = P k h (E ℓ i |s) andE s ′ ∼ P k-1 h (s) max a {u(s ′ (a), a)} = E i∼μ k-1 h (•|s;ℓ u ) [u(s ′ i , a i )].Similarly, we will require the distribution probability w.r.t. two lists -the probability that the top element w.r.t. list ℓ is i and the top element w.r.t. list ℓ ′ is j; we denote the real and empirical probability distributions by µ(i, j|ℓ, ℓ ′ , P ) and μk h (i, j|s; ℓ, ℓ ′ ), respectively. This allows, for example, using Lemma 17 to write for any u, v :EQUATIONFinally, we say that a policy π h (s, s ′ ) is induced by lists ℓ h (s) if it chooses an action a such that its next-state s ′ (a) is ranked higher in ℓ than all other realized next-state-action pairs. In particular, the policy π k and the optimal policy π * (defined in Proposition 2) are such policies w.r.t. the lists lk h (s) and ℓ * h (s) -induced by V k h (s, s ′ , a) and V * h (s, s ′ , a), respectively. As such, for any probability measure P h (s), function u : S × S × A → R and a policy π induced by a list ℓ, it holds thatEQUATIONWe have already seen the optimal policy is induced by a list ℓ * h (s), and in particular, we can write the dynamic programming equations of Proposition 2 asV * h (s) = E s ′ ∼P h (s) max a∈A r h (s, a) + V T, * h (s ′ (a)) = E i∼µ(•|ℓ * h (s),P h (s)) r h (s, a i ) + V * h+1 (s ′ (a i )) .Therefore, one way to perform the planning is to build a list ℓ * h (s) of (s ′ , a) s.t. the valuesV * h (s, s ′ , a) = r h (s, a) + V * h+1 (s ′ )are sorted in a non-increasing order and calculate the probability of any pair in the list to be the highest-realized pair:µ(i|ℓ, P h (s)) = P h (E ℓ i ) = Pr s ′ h+1 (a i ) = s ′ i and ∀j < i, s ′ h+1 (a j ) ̸ = s ′ j |s h = s .In general, calculating this distribution is intractable, and one must resort to approximating it by sampling (as done in Algorithm 4. Nonetheless, if next states are generated independently between actions, this distribution could be efficiently calculated as follows:µ(i|ℓ, P h (s)) = Pr s ′ h+1 (a i ) = s ′ i and ∀j < i, s ′ h+1 (a j ) ̸ = s ′ j |s h = s (1) = Pr s ′ (a i ) = s ′ i and ∀j < i s.t. a j ̸ = a i , s ′ (a j ) ̸ = s ′ j |s h = s (2) = Pr{s ′ (a i ) = s ′ i |s h = s} a̸ =ai Pr ∀j < i s.t. a j = a, s ′ (a) ̸ = s ′ j |s h = s (3) = P h (s ′ i |s, a i ) a̸ =ai   1 - i-1 j=1 1{a j = a}P h (s ′ j |s, a)   .Relation (1) holds since if s ′ (a i ) = s ′ i , 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.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.t. the empirical and real model to be close. Finally, the empirical measure μk h (i, j|s; ℓ, ℓ * h (s)) must concentrate well around its mean for any list ℓ -this will allow the change-of-measure argument described in the proof sketch.Formally, define the following good events:E r (k) = ∀s, a, h : |r h (s, a) -rk-1 h (s, a)| ≤ L k δ n k-1 h (s, a) ∨ 1 E ℓ (k) = ∀s, h, ∀ℓ ∈ L, ∀i, j ∈ [SA] : μk-1 h (i, j|s; ℓ, ℓ * h (s)) -µ(i, j|ℓ, ℓ * h (s); P h (s)) ≤ 4SAL k δ µ(i, j|s; ℓ, ℓ * h (s); P h (s)) n k-1 h (s) ∨ 1 + 2SAL k δ n k-1 h (s) ∨ 1 E pv1 (k) = ∀s, h : E s ′ ∼P h (s) V * h (s, s ′ ) -E s ′ ∼ P k-1 h (s) V * h (s, s ′ ) ≤ 2Var s ′ ∼P h (s) (V * h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + HL k δ n k-1 h (s) ∨ 1 E pv2 (k) = ∀s, h : Var s ′ ∼P h (s) (V * h (s, s ′ )) -Var s ′ ∼ P k-1 h (s) (V * h (s, s ′ )) ≤ 4H L k δ n k-1 h (s) ∨ 1where we again useL k δ = ln 16S 3 A 2 Hk 2 (k+1) δ. We define the first good event asG 1 = k≥1 E r (k) k≥1 E ℓ (k) k≥1 E pv1 (k) k≥1 E pv2 (k),for which the following holds: Lemma 12 (The First Good Event). It holds that Pr(G 1 ) ≥ 1 -δ/2.Proof. We prove that each of the events holds w.p. at least 1 -δ/8. The result then directly follows by the union bound. We also remark that due to 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-actions were already previously visited.Event ∩ k≥1 E r (k). Fix k ≥ 1, s, a, h and visits n ≥ 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 n samples by rh (s, a, n), by Hoeffding's inequality, it holds w.p. 1 -δ 8SAHk 2 (k+1) that |r h (s, a) -rh (s, a, n)| ≤ ln 16SAHk 2 (k+1) δ 2n ≤ L k δ n .Taking the union bound over all n ∈ [k] at timestep k, we get that w.p. 1 -δ 8SAHk(k+1) |r h (s, a) -rk-1 h (s, a)| ≤ L k δ n k-1 h (s, a) ∨ 1, and another union bound over all possible values of s, a, h and k ≥ 1 implies that ∩ k≥1 E r (k) holds w.p. at least 1 -δ/8.The event ∩ k≥1 E ℓ (k). For any fixed k ≥ 1, s, h, a list ℓ ∈ L and number of visits n ∈ [k], we utilize Lemma 16 (event E p ) w.r.t. the distribution µ(i, j|ℓ, ℓ * h (s), P ) (whose support is of size M = (SA) 2 ). When applying the lemma, notice that given the number of visits n ≥ 1, the empirical distribution μk-1h (i, j|s; ℓ, ℓ * h (s)) is the average of n = n k-1 h (s) i.i.d samples, so that for all i, j ∈ [SA], μk-1 h (i, j|s; ℓ, ℓ * h (s)) -µ(i, j|ℓ, ℓ * h (s); P h (s)) ≤ 2µ(i, j|ℓ, ℓ * h (s); P h (s)) ln 2(SA) 2 δ ′ n + 2 ln 2(SA) 2 δ ′ 3n ≤ 4µ(i, j|ℓ, ℓ * h (s); P h (s)) ln 2SA δ ′ n + 2 ln 2SA δ ′ n w.p. 1 -δ ′ . Choosing δ ′ = δ 8|L|SHk 2 (k+1) (such that ln 2SA δ ′ ≤ SA ln 16S 3 A 2 Hk 2 (k+1)δ since |L| ≤ (SA) SA ), while taking the union bound on all n ∈ [k], all s, h and all lists ℓ ∈ L implies that ∩ k≥1 E ℓ (k) holds w.p. at least 1 -δ 8 . Events ∩ k≥1 E pv1 (k) and ∩ k≥1 E pv2 (k). We repeat the arguments stated in Lemma 5. For any fixed k ≥ 1, s, h and number of visits n ∈ [k] , we utilize Lemma 16 w.r.t. the next-state distribution for all actions P h (s), the value V * h (s, s ′ ) ∈ [0, H] and probability δ ′ = δ 8SHk 2 (k+1) ; we yet again remind that given the number of visits, samples are i.i.d.As before, the events ∩ k≥1 E pv1 (k) and ∩ k≥1 E pv2 (k) hold w.p. at least 1 -δ 8 through the union bound first on n ∈ [k] (to get the empirical quantities) and then on s, h and k ≥ 1. This proves that each of the events in G 1 holds w.p. at least 1 -δ 8 , so G 1 holds w.p. at least 1 -δ 2 .We now prove that under the event G 1 , the values that MVP-TL outputs are optimistic. Lemma 13 (Optimism). Under the first good event G 1 , for all k ∈[K], h ∈ [H], a ∈ A and s, s ′ ∈ S, it holds that V * h (s, s ′ , a) ≤ V k h (s, s ′ , a). Moreover, for all s ′ ∈ S A , V * h (s, s ′ ) ≤ V k h (s, s ′ ) and also V * h (s) ≤ V k h (s).Proof. The proof of all claims follows by backward induction on H; the base case naturally holds for h = H + 1, where all values are defined to be zero.Assume by induction that for some k ∈ [K] and h ∈ [H], the inequality V * h+1 (s) ≤ V k h+1 (s) holds for all s ∈ 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 k h (s) < H (namely, not truncated), since otherwise, by the boundedness of the rewards, V * h (s) ≤ H = V k h (s). In particular, under the good event E r (k), for all s and a , it holds that rk-1 h (s, a) + b r k,h (s, a) ≥ r h (s, a), so for all s, a and s ′ , we haveV k h (s, s ′ , a) = rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′ ) ≥ r h (s, a) + V * h+1 (s ′ ) = V * h (s, s ′ , a). where the inequality also uses the induction hypothesis. This proves the first part of the lemma. Moreover, it implies thatEQUATIONand 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 be used when applied to the empirical distribution of all possible next-states P k-1 h (s); indeed, the non-truncated optimistic value can be written asV k h (s) = E s ′ ∼ P k-1 h (s) max a∈A rk-1 h (s, a) + b r k,h (s, a) + V k h+1 (s ′ (a)) + b p k,h (s) ≥ E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) + max      20 3 Var s ′ ∼ P k-1 h (s) ( V k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 , 400 9 3HL k δ n k-1 h (s) ∨ 1     , which is exactly the required form in Lemma 23, w.r.t. the distribution P k-1 h (s) and the values V k h (s, s ′ ) (while noticing that due to the truncation of the values and bonuses, V k h (s, s ′ ) ∈ [0, 3H]). Thus, the lemma guarantees monotonicity in the value, so by Equation ( 13),V k h (s) ≥ E s ′ ∼ P k-1 h (s) V * h (s, s ′ ) + max      20 3 Var s ′ ∼ P k-1 h (s) (V * h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 , 400 9 3HL k δ n k-1 h (s) ∨ 1      ≥ E s ′ ∼ P k-1 h (s) V * h (s, s ′ ) + 10 3 Var s ′ ∼ P k-1 h (s) (V * h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 200 3 HL k δ n k-1 h (s) ∨ 1 ≥ E s ′ ∼ P k-1 h (s) V * h (s, s ′ ) + 10 3 Var s ′ ∼P h (s) (V * h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 50HL k δ n k-1 h (s) ∨ 1 (Under E pv2 (k)) ≥ E s ′ ∼P h (s) V * h (s, s ′ ) (Under E pv1 (k)) = V * h (s).In this subsection, we present three good events that allow replacing the expectation over the randomizations inside each episode by their realization. LetY k 1,h := V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 ) Y k 2,h = Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ )) Y k 3,h = b r k,h (s k h , a k h ).The second good event is the intersection of the events G 2 = E diff ∩ E Var ∩ E br defined as follows.E diff = ∀h ∈ [H], K ≥ 1 : K k=1 E[Y k 1,h |F k,h-1 ] ≤ 1 + 1 2H K k=1 Y k 1,h + 18H 2 ln 6HK(K + 1) δ , E Var = K ≥ 1 : K k=1 H h=1 Y k 2,h ≤ 2 K k=1 H h=1 E[Y k 2,h |F k-1 ] + 4H 3 ln 6HK(K + 1) δ , E br = ∀h ∈ [H], K ≥ 1 : K k=1 E[Y k 3,h |F k,h-1 ] ≤ 2 K k=1 Y k 3,h + 18 ln 6HK(K + 1) δ ,We define the good event G = G 1 ∩ G 2 . Lemma 14. The good event G holds with a probability of at least 1 -δ.Proof. The analysis of the first event follows E diff exactly as the one of E diff1 in Lemma 7: defineW k = 1 V k h (s) -V π k h (s) ∈ [0, H], ∀h ∈ [H],s ∈ S (which happens a.s. under G 1 due to the optimism in Lemma 13 and truncation) andỸ k 1,h = W k Y k 1,h , which is bounded in [0, H] and F k,h - measurable.The corresponding event w.r.t. this modified variables Ẽdiff then holds w.p. 1 -δ 6 by Lemma 25, and as in Lemma 7, we can use the fact that G 1 ∩ Ẽdiff = G 1 ∩ E diff to conclude this part of the proof.Moving to the second event, sinceV π k h (s, s ′ ) ∈ [0, H], then H h=1 Y k 2,h ∈ [0, H 3 ].Therefore, by Lemma 25 (w.r.t. the filtration F k ) with C = H 3 and any fixed K, we get w.p. 1 -δ 6HK(K+1) that K k=1 H h=1 Y k 2,h ≤ 2 K k=1 H h=1 E[Y k 2,h |F k-1 ] + 4H 3 ln 6HK(K + 1) δ .Taking the union bound on all possible values of K ≥ 1 proves that E Var holds w.p. at least 1 -δ 6 . Finally, by definition, we have thatY k 3,h = b r k,h (s k h , a k h ) ∈ [0, 1]and is F k,h -measurable. Thus, for any fixed k ≥ 1 and h ∈ [H], using Lemma 25, we have w.p. 1 -δ 6HK(K+1) that K k=1 E[Y k 3,h |F k,h-1 ] ≤ 1 + 1 2 K k=1 Y k 3,h + 18 ln 6HK(K + 1) δ ≤ 2 K k=1 Y k 3,h + 18 ln 6HK(K + 1) δ ,so that due to the union bound, E br holds w.p. 1 -δ 6 . To conclude, G 1 holds w.p. 1-δ 2 (Lemma 5) and the events Ẽdiff , E Var , E br each hold w.p. 1-δ 6 . As before, when accounting to the fact that Ẽdiff and E diff are identical under G 1 , the event G = G 1 ∩G 2 holds w.p. at least 1 -δ.Theorem 2. When running MVP-TL, with probability at least 1 -δ uniformly for all K ≥ 1, it holds that RegT (K) ≤ O √ H 2 SK √ H + √ A ln SAHK δ + H 3 S 4 A 3 ln SAHK δ 2 .Proof. Assume that the event G holds, which by Lemma 14, happens with probability at least 1 -δ. In particular, throughout the proof, we use optimism (Lemma 13), which implies that0 ≤ V π k h (s, s ′ ) ≤ V * h (s, s ′ ) ≤ V k h (s, s ′ ) ≤ 3H(the upper bound is also by the truncation), as well as0 ≤ V π k h (s) ≤ V * h (s) ≤ V k h (s) ≤ H.We first focus on lower-bounding the value of the policy π k : by Remark 2, we haveV π k h (s) = E s ′ ∼P h (s) r h (s, π k h (s, s ′ )) + V π k h+1 (s ′ (π k h (s, s ′ ))) = E s ′ ∼P h (s) rk-1 h (s, π k h (s, s)) + V k h+1 (s ′ (π k h (s, s ′ ))) + b r k,h (s, π k h (s, s ′ )) + E s ′ ∼P h (s) r h (s, π k h (s, s ′ )) -rk-1 h (s, π k h (s, s ′ )) -b r k,h (s, π k h (s, s ′ )) + E s ′ ∼P h (s) V π k h+1 (s ′ (π k h (s, s ′ ))) -V k h+1 (s ′ (π k h (s, s ′ ))) (1) = E s ′ ∼P h (s) max a∈A rk-1 h (s, a) + V k h+1 (s ′ (a)) + b r k,h (s, a) + E s ′ ∼P h (s) r h (s, π k h (s, s ′ )) -rk-1 h (s, π k h (s, s)) -b r k,h (s, π k h (s, s ′ )) + E s ′ ∼P h (s) V π k h+1 (s ′ (π k h (s, s ′ ))) -V k h+1 (s ′ (π k h (s, s ′ ))) (2) ≥ E s ′ ∼P h (s) V k h (s, s ′ ) -2E s ′ ∼P h (s) b r k,h (s, π k h (s, s ′ )) -E s ′ ∼P h (s) V k h+1 (s ′ (π k h (s, s ′ ))) -V π k h+1 (s ′ (π k h (s, s ′ )))where (1) is by the definition of π k and (2) uses the reward concentration event. Thus, we can writeEQUATIONBounding term (ii): using the concentration event E pv1 (k), we haveEQUATIONRelation (1) uses Lemma 21 with the values 0≤ V π k h (s, s ′ ) ≤ V * h (s, s ′ ) ≤ H with α = 8H • 2L k δ and(2) is by optimism.We first focus on the transition bonus; to bound it, we apply Lemma 22 w.r.t.P k-1 h (s ′ |s), P h (s ′ |s), the values 0 ≤ V π k h (s, s ′ ) ≤ V * h (s, s ′ ) ≤ V k h (s, s ′ ) ≤ 3H (by optimism), under the event E pv2 (k) and with α = 8H • 20 3 L k δ : b p k,h (s) = 20 3 Var s ′ ∼ P k-1 h (s) ( V k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 400 3 HL k δ n k-1 h (s) ∨ 1 ≤ 1 8H E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) -V * h (s, s ′ ) + 1 8H E s ′ ∼P h (s) [V * h (s, s ′ ) -V π k h (s, s ′ )] + 20 3 Var s ′ ∼P h (s) (V π k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 1600H 2 3n k-1 h (s) ∨ 1 + 20 3 4HL k δ n k-1 h (s) ∨ 1 + 400 3 HL k δ n k-1 h (s) ∨ 1 ≤ 1 8H E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) -V * h (s, s ′ ) -E s ′ ∼P h (s) V k h (s, s ′ ) -V * h (s, s ′ ) + 1 8H E s ′ ∼P h (s) V k h (s, s ′ ) -V π k h (s, s ′ ) + 20 3 Var s ′ ∼P h (s) (V π k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 700H 2 n k-1 h (s) ∨ 1 .Substituting back to term (i), we now have(i) ≤ 1 + 1 8H E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) -V * h (s, s ′ ) -E s ′ ∼P h (s) V k h (s, s ′ ) -V * h (s, s ′ ) + 1 8H E s ′ ∼P h (s) V k h (s, s ′ ) -V π k h (s, s ′ ) + 20 3 Var s ′ ∼P h (s) (V π k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 700H 2 L k δ n k-1 h (s) ∨ 1 .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 k h (s, s ′ ) = max a V k h (s, s ′ (a), a) and V * h (s, s ′ ) = max a V * h (s, s ′ (a), a), inducing the lists l = lk h (s) and ℓ * = ℓ * h (s), respectively; thus the expectations can be written as (see Appendix C.4 for further details on the list representation, and in particular, Equation ( 11)):E s ′ ∼ P k-1 h (s) V k h (s, s ′ ) -V * h (s, s ′ ) -E s ′ ∼P h (s) V k h (s, s ′ ) -V * h (s, s ′ ) (1) = E i,j∼μ k h (•|s; l,ℓ * ) V k h (s, s ′ l(i) , al (i) ) -V * h (s, s ′ ℓ * (j) , a ℓ * (j) ) -E i,j∼µ(•| l,ℓ * ,P h (s)) V k h (s, s ′ l(i) , al (i) ) -V * h (s, s ′ ℓ * (j) , a ℓ * (j) ) (2) ≤ 1 8H E i,j∼µ(•| l,ℓ * ,P h (s)) V k h (s, s ′ l(i) , al (i) ) -V * h (s, s ′ ℓ * (j) , a ℓ * (j) ) + 3H(SA) 2 L k δ (2SA + 8H • 4SA/4) n k-1 h (s) ∨ 1 (1) ≤ 1 8H E s ′ ∼P h (s) V k h (s, s ′ ) -V * h (s, s ′ ) + 30H 2 (SA) 3 L k δ n k-1 h (s) ∨ 1 ≤ 1 8H E s ′ ∼P h (s) V k h (s, s ′ ) -V π k h (s, s ′ ) + 30H 2 (SA) 3 L k δ n k-1 h (s) ∨ 1Relations (1) formulate the expectation using the list representations and backward, as done in Equation ( 11). For inequality (2) we rely on Lemma 24 with α = 8H 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) 2 ; were we to use the same result on the distributions P k-1 h (s) and P h (s), the support would be of size S A , which would lead to an exponential additive factor. And so, we finally have a bound ofEQUATION)Combining both terms. Substituting this and Equation (15) into Equation ( 14), we haveV k h (s) -V π k h (s) ≤ 1 2H E s ′ ∼P h (s) V k h (s, s ′ ) -V π k h (s, s ′ ) + 9 Var s ′ ∼P h (s) (V π k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 750H 2 (SA) 3 L k δ n k-1 h (s) ∨ 1 + 2E s ′ ∼P h (s) b r k,h (s, π k h (s, s ′ )) + E s ′ ∼P h (s) V k h+1 (s ′ (π k h (s, s ′ ))) -V π k h+1 (s ′ (π k h (s, s ′ ))) .and further bounding (using the concentration event E r (k)V k h (s, s ′ )) -V π k h (s, s ′ ) = rk-1 h (s, π k h (s, s ′ )) + b r k,h (s, π k h (s, s ′ )) + V k h+1 (s ′ (π k h (s, s ′ ))) -r k-1 h (s, π k h (s, s ′ )) -V π k h+1 (s ′ (π k h (s, s ′ ))) ≤ V k h+1 (s ′ (π k h (s, s ′ ))) -V π k h+1 (s ′ (π k h (s, s ′ ))) + 2b r k,h (s, π k h (s, s ′ )),we finally get the decompositionV k h (s) -V π k h (s) ≤ 1 + 1 2H E s ′ ∼P h (s) V k h+1 (s ′ (π k h (s, s ′ ))) -V π k h+1 (s ′ (π k h (s, s ′ ))) + 9 Var s ′ ∼P h (s) (V π k h (s, s ′ ))L k δ n k-1 h (s) ∨ 1 + 750H 2 (SA) 3 L k δ n k-1 h (s) ∨ 1 + 3E s ′ ∼P h (s) b r k,h (s, π k h (s, s ′ )) .At this point, we choose to take s = s k h and sum over all k ∈ [K]; specifically, for s ′ = s ′k h+1 , the action becomes π k h (s, s ′ ) = a k h and s ′ (π k h (s, s ′ )) = s k h+1 . Formally, we can write the bound asK k=1 V k h (s k h ) -V π k h (s k h ) ≤ 1 + 1 2H K k=1 E V k h+1 (s k h+1 ) -V π k h+1 (s k h+1 )|F k,h-1 + 3 K k=1 E b r k,h (s k h , a k h )|F k,h-1 + 9 K k=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ ))L k δ n k-1 h (s k h ) ∨ 1 + K k=1 750H 2 (SA) 3 L k δ n k-1 h (s k h ) ∨ 1 .and, in particular, under the events E diff and E br , it holds thatK k=1 V k h (s k h ) -V π k h (s k h ) ≤ 1 + 1 2H 2 K k=1 V k h+1 (s k h+1 )) -V π k h+1 (s k h+1 ) + 36H 2 ln 6HK(K + 1) δ + 3 K k=1 b r k,h (s k h , a k h ) + 54 ln 6HK(K + 1) δ + 9 K k=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ ))L k δ n k-1 h (s k h ) ∨ 1 + K k=1 750H 2 (SA) 3 L k δ n k-1 h (s k h ) ∨ 1 .To conclude the proof, we recursively apply this formula from h = 1 to h = H + 1 (where the values are zero) and use the optimism. This yieldsEQUATION(1)≤ 9 1 + 1 2H 2H K k=1 H h=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ ))L k δ n k-1 h (s k h ) ∨ 1 + 3 1 + 1 2H 2H K k=1 H h=1 L k δ n k-1 h (s k h , a k h ) ∨ 1 + 1 + 1 2H 2H K k=1 H h=1 750H 2 (SA) 3 L k δ n k-1 h (s k h ) ∨ 1 + 90H 3 1 + 1 2H 2H ln 6HK(K + 1) δ (2) ≤ 50 √ H 3 SKL K δ + 50 √ 2SH 2 L K δ 1.5 + 9 L K δ SAH + 2 √ SAH 2 K + 2050H 3 S 4 A 3 L K δ (2 + ln(K)) + 250H 3 L K δ = O √ H 2 SK √ H + √ A L K δ + H 3 S 4 A 3 L K δ 2 .Relation ) (V π k h (s k h , s ′ )) n k-1 h (s k h ) ∨ 1 ≤ 2 H 3 SKL K δ + √ 8SH 2 L K δ .Proof. Similar to Lemma 9, we again rely on the lookahead version of the law of total variation to prove this bound. First, by Cauchy-Schwartz inequality, it holds thatK k=1 H h=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ )) n k-1 h (s k h ) ∨ 1 ≤ K k=1 H h=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ )) K k=1 H h=1 1 n k-1 h (s k h ) ∨ 1.We use Lemma 20 to bound the second term byK k=1 H h=1 1 n k-1 h (s k h ) ∨ 1 ≤ SH(2 + ln(K))and focus on bounding the first term. Under E Var , we haveK k=1 H h=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ )) ≤ 2 K k=1 E H h=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ ))|F k-1 + 4H 3 ln 6HK(K + 1) δ (Under E Var ) = 2 K k=1 E   H h=1 r h (s k h , a k h ) -V π k 1 (s k 1 ) 2 |F k-1   + 4H 3 ln 6HK(K + 1) δ (By Lemma 10) ≤ 2H 2 K + 4H 3 ln 6HK(K + 1) δ ,where the last inequality is since both the values and cumulative rewards are bounded in [0, H].Combining both, we getK k=1 H h=1 Var s ′ ∼P h (s k h ) (V π k h (s k h , s ′ )) n k-1 h (s k h ) ∨ 1 ≤ 2H 2 K + 4H 3 ln 6HK(K + 1) δ SH(2 + ln(K)) ≤ 2H 2 K + 4H 3 ln 6HK(K + 1) δ 2SH ln 6HK(K + 1) δ ≤ 2 H 3 SKL K δ + √ 8SH 2 L K δ .Next, we relate V n to the empirical variance. By elementary algebra, we haveV n = 1 2n(n -1) n i,j=1 (U (X i ) -U (X j )) 2 = 1 n n i=1 U (X i ) 2 - 1 n(n -1) i̸ =j U (X i )U (X j ) = 1 n n i=1 U (X i ) 2 - n (n -1) 1 n i U (X i ) 2 + 1 n(n -1) n i=1 U (X i ) 2 = x∈X Pn (x)U (x) 2 - x∈X Pn (x)U (x) 2 + 1 n(n -1) n i=1 U (X i ) 2 - 1 n 2 (n -1) n i=1 U (X i ) 2 .The first two terms are exactly the variance w.r.t. the empirical distribution; therefore, using the inequality √ a -√ b ≤ |a -b| for positive numbers, we haveV n -Var Pn (U (X)) ≤ 1 n(n -1) n i=1 U (X i ) 2 - 1 n 2 (n -1) n i=1 U (X i ) 2 ≤ C 2 n -1 .Combining both inequalities and recalling the trivial bound of C on the difference, we get that w.p. at least 1 -δ,Var Pn (U (X)) -Var P (U (X)) ≤ min    C 2 ln 2 δ n -1 + C 2 n -1 , C    ≤ 4C ln 2 δ n ∨ 1 .Next, we present a short lemma that allows moving between different spaces of probabilities. Lemma 17. Let X be a finite set and let X 1 , . . . , X n ∈ X . Also, let E 1 , . . . , E m ⊆ X be a partition of the set X , namely, for all i ̸ = j, E i ∩ E j = ∅ and ∪ m i=1 E i = X . Finally, let f : X → R such that for all i ∈ [m] and x ∈ E i , it holds that f (x) = f (i), and definePn (x) = 1 n n ℓ=1 1{X ℓ = x}, and, Qn (i) = 1 n n ℓ=1 1{X ℓ ∈ E i }.Then, the following hold:1. Qn (i) = Pn (E i ) ≜ x∈Ei Pn (x) and, in particular, E i∼ Qn [f (i)] = E x∼ Pn [f (x)].2. If P is a distribution over X and X 1 , . . . , X n ∈ X are i.i.d. samples from P , thenE[ Qn (i)] = P (E i ) ≜ Q(i). It also holds that E x∼P [f (x)] = E i∼Q [f (i)].Proof. For the first part, we have by definition thatQn (i) = 1 n n ℓ=1 1{X ℓ ∈ E i } = x∈X 1 n n ℓ=1 1{X ℓ = x}1{x ∈ E i } = x∈X Pn (x)1{x ∈ E i } = x∈Ei Pn (x) = Pn (E i ).In particular, it holds thatE i∼ Qn [f (i)] = m i=1 Qn (i)f (i) = m i=1 x∈Ei Pn (x)f (i) (1) = m i=1 x∈Ei Pn (x)f (x) (2) = x∈X Pn (x)f (x) = E x∼ Pn [f (x)],whereEQUATIONFor the second part of the statement, notice that since the samples are i.i.d., it holds that E Pn (x) = P (x), and therefore,E[ Qn (i)] = E x∈Ei Pn (x) = x∈Ei P (x) = P (E i ) = Q(i).Finally, as in the first part of the statement, it holds thatE i∼Q [f (i)] = m i=1 Q(i)f (i) = m i=1 x∈Ei P (x)f (i) = m i=1 x∈Ei P (x)f (x) = x∈X P (x)f (x) = E x∼P [f (x)].Finally, we present two specialized concentration results that are needed for reward and transition lookahead, respectively. Lemma 18. Let X, X 1 , . . . X n ∈ R d be i.i.d. random vectors over [0, 1] and let C ≥ 1 be some constant. Then, for any δ ∈ (0, 1), with probability at least 1 -δ,∀u ∈ [0, C] d , E max i∈[d] {X(i) + u(i)} - 1 n n ℓ=1 max i∈[d] {X ℓ (i) + u(i)} ≤ 3 d ln 9Cn δ 2n . Proof. Denote m(u) = E max i∈[d] {X(i) + u(i)} and m(u) = 1 n n ℓ=1 max i∈[d] {X ℓ (i) + u(i)} and fix any u ∈ [0, C] d . Since the variables are bounded in [0, 1], their maximum is bounded almost surely in [max i u(i), max i u(i) + 1],namely, an interval of unit length. Therefore, by Hoeffding's inequality, for any δ ′ ∈ (0, 1), w.p.1 -δ ′ |m(u) -m(u)| ≤ ln 2 δ ′ 2n .Now, for some ϵ ∈ (0, C], let u ϵ be the closest vector to u on a grid {0, ϵ, 2ϵ, . . . , C} d . Then, it clearly holds that|m(u) -m(u)| ≤ |m(u ϵ ) -m(u ϵ )| + 2ϵ.Taking the union bound over all C ϵ + 1 d possible choices for u ϵ and fixing δ′ = δ (⌈ C ϵ ⌉+1) d , we get w.p. 1 -δ for all u that |m(u) -m(u)| ≤ ln 2(⌈ C ϵ ⌉+1) d δ 2n + 2ϵ ≤ d ln 6C ϵδ 2n + 2ϵ. Now, fixing ϵ = d ln 6C δ 2n and noting that 1 ϵ ≤ √ 2n for C ≥ 1, we get |m(u) -m(u)| ≤ d ln 6C √ 2n δ 2n + 2 d ln 6C δ 2n ≤ d ln 9Cn δ 2n + 2 d ln 6C δ 2n ≤ 3 d ln 9Cn δ 2n .Lemma 19. Let X, X 1 , . . . X n ∈ R d be i.i.d. random vectors with components supported over the discrete set [m] and let C ≥ 1 be some constant. Then, uniformly over all u ∈ [0, C] dm w.p. 1 -δ:E max i {u(X(i), i)} - 1 n n ℓ=1 max i {u(X ℓ (i), i)} ≤ 2md ln 6n δ Var(max i {u(X(i), i)}) n + + 8Cmd ln 6n δ 1.5 n .Proof. We follow a similar path to Lemma 18 and use a covering argument. Denoting w(u) = E[max i {u(X(i), i)}] and ŵ(u) = 1 n n ℓ=1 max i {u(X ℓ (i), i)}, by Bernstein's inequality, for any δ ′ ∈ (0, 1) and fixed u ∈EQUATIONNow, for some ϵ ∈ (0, C], let u ϵ be the closest matrix to u on a grid {0, ϵ, 2ϵ, . . . , C} md and denote Z(u) = max i {u(X(i), i)} with samples Z i (u). By the smoothness of the max function, it holds that |Z(u) -Z(u ϵ )| ≤ ϵ. In particular, we also have thatE[Z(u) 2 ] -E[Z(u ϵ ) 2 ] ≤ ϵ 2 + 2Cϵ, and E[Z(u)] 2 -E[Z(u ϵ )] 2 ≤ ϵ 2 + 2Cϵ, so we have Var max i {u(X(i), i)} -Var max i {u ϵ (X(i), i)} = |Var(Z(u)) -Var(Z(u ϵ ))| ≤ 2ϵ 2 + 4Cϵ. Similarly, it holds that |w(u) -ŵ(u)| ≤ |w(u ϵ ) -ŵ(u ϵ )| + 2ϵ.Taking the union bound over all C ϵ + 1 md possible choices for u ϵ and fixing δ′ = δ (⌈ C ϵ ⌉+1) dm , we get w.p. 1 -δ for all u that |w(u) -ŵ(u)| ≤ 2Var(max i {u ϵ (X(i), i)}) ln 2(⌈ C ϵ ⌉+1) md δ n + 2C ln 2(⌈ C ϵ ⌉+1) md δ 3n + 2ϵ ≤ 2mdVar(max i {u ϵ (X(i), i)}) ln 6C ϵδ n + 2Cmd ln 6C ϵδ 3 + 2ϵ ≤ 2md ln 6C ϵδ (Var(max i {u(X(i), i)}) + 2ϵ 2 + 4Cϵ) n + 2Cmd ln 6C ϵδ 3n + 2ϵ ≤ 2md ln 6C ϵδ Var(max i {u(X(i), i)}) n + 8mdCϵ ln 6C ϵδ n + 4mdϵ 2 ln 6C ϵδ n + 2Cmd ln 6C ϵδ 3n + 2ϵ. Now, fixing ϵ = C ln 6n δ nand noticing that 6C ϵδ ≤ 6n δ , we get|w(u) -ŵ(u)| ≤ 2md ln 6n δ Var(max i {u(X(i), i)}) n + √ 8mdC ln 6n δ n + √ 4mdC ln 6n δ 1.5 n 1.5 + 2Cmd ln 6n δ 3n + 2C ln 6C δ n ≤ 2md ln 6n δ Var(max i {u(X(i), i)}) n + 8Cmd ln 6n δ 1.5 n .Lemma 20. The following bounds hold:K k=1 H h=1 1 n k-1 h (s k h , a k h ) ∨ 1 ≤ SAH + 2 √ SAH 2 K, K k=1 H h=1 1 n k-1 h (s k h , a k h ) ∨ 1 ≤ SAH(2 + ln(K)), K k=1 H h=1 1 n k-1 h (s k h ) ∨ 1 ≤ SH + 2 √ SH 2 K, K k=1 H h=1 1 n k-1 h (s k h ) ∨ 1 ≤ SH(2 + ln(K)).Proof. Recall that every time a state (or state-action) is visited, its visitation-count is increased by 1, up to n K-1 h (s, a) at the last episode. therefore, we can writeK k=1 H h=1 1 n k-1 h (s k h , a k h ) ∨ 1 = H h=1 s∈S a∈A K k=1 1 s k h = s, a k h = a n k-1 h (s, a) ∨ 1 = H h=1 s∈S a∈A n K-1 h (s,a) i=0 1 √ i ∨ 1 ≤ H h=1 s∈S a∈A 1 + 2 n K-1 h (s, a) ≤ SAH + 2 SAH H h=1 s∈S a∈A n K-1 h (s, a) (Jensen's inequality) ≤ SAH + 2 √ SAH 2 K.where we bounded the total number of visits by the number of steps HK. Similarly, we also have We can likewise prove the inequalities for the state counts as follows: K k=1 H h=1 1 n k-1 h (s k h ) ∨ 1 = H h=1 s∈S K k=1 1 s k h = s n k-1 h (s) ∨ 1 = H h=1 s∈S n K-1 h (s) i=0 1 √ i ∨ 1 ≤ H h=1 s∈S 1 + 2 n K-1 h (s) ≤ SH + 2 SHLemma 21. Let P be a distribution over a finite set X and let X ∼ P . Also, let V 1 , V 2 : X → [0, C] for some C > 0 such that V 1 (x) ≤ V 2 (x) for all x ∈ X . Then, for any α, n > 0, it holds thatVar P (V 2 (X)) √ n ≤ Var P (V 1 (X)) √ n + 1 α E P [V 2 (X) -V 1 (X)] +Proof. By Lemma 26, we haveVar P (V 2 (X)) -Var P (V 1 (X)) ≤ Var P (V 2 (X) -V 1 (X))≤ E P [(V 2 (X) -V 1 (X)) 2 ] ≤ CE P [V 2 (X) -V 1 (X)]where the last inequality is by the boundedness and since V 1 (x) ≤ V 2 (x). Thus, we can boundVar P (V 2 (X)) -Var P (V 1 (X)) √ n ≤ CE P [V 2 (X) -V 1 (X)] √ n = E P [V 2 (X) -V 1 (X)] • C n ≤ 1 α E P [V 2 (X) -V 1 (X)] + Cα 4n ,where last inequality is due to Young's inequality (ab ≤ 1 α a 2 + α 4 b 2 for all α > 0). Lemma 22. Let P, P ′ be distributions over a finite set X and let X ∼ P . Also, let V 1 , V 2 , V 3 : X → [0, C] for some C > 0 such that V 1 (x) ≤ V 2 (x) ≤ V 3 (x) for all x ∈ X . Finally, assume that Var P (V 2 (X)) -Var P ′ (V 2 (X)) ≤ β for some β > 0. Then, for any α, n > 0, it holds thatVar P ′ (V 3 (X)) √ n ≤ Var P (V 1 (X)) √ n + 1 α E P ′ [V 3 (X) -V 2 (X)] + 1 α E P [V 2 (X) -V 1 (X)] + Cα 2n + β √ n ≤ Var P (V 1 (X)) √ n + 1 α E P ′ [V 3 (X) -V 1 (X)] + 1 α E P [V 3 (X) -V 1 (X)] + Cα 2n + β √ n .Proof. We decompose the l.h.s. as followsVar P ′ (V 3 (X)) √ n = Var P ′ (V 3 (X)) -Var P ′ (V 2 (X)) √ n + Var P ′ (V 2 (X)) -Var P (V 2 (X)) √ n + Var P (V 2 (X)) -Var P (V 1 (X)) √ n + Var P (V 1 (X)) √ nWe bound the first and third terms using Lemma 21 and bound the second term with the assumption and getVar P ′ (V 3 (X)) √ n ≤ 1 α E P ′ [V 3 (X) -V 2 (X)] + Cα 4n + β √ n + 1 α E P [V 2 (X) -V 1 (X)] + Cα 4n + Var P (V 1 (X)) √ n = Var P (V 1 (X)) √ n + 1 α E P ′ [V 3 (X) -V 2 (X)] + 1 α E P [V 2 (X) -V 1 (X)] + Cα 2n + β √ n ≤ Var P (V 1 (X)) √ n + 1 α E P ′ [V 3 (X) -V 1 (X)] + 1 α E P [V 3 (X) -V 1 (X)] + Cα 2n + β √ n ,where the last inequality uses the fact that V 1 (x) ≤ V 2 (x) ≤ V 3 (x) for all x ∈ X . The last two bounds are the desired results.Lemma 23 (Monotonic Bonuses, [Zhang et al., 2023] , Appendix C.1). For any p ∈ ∆ S , v ∈ R S + s.t. ∥v∥ ∞ ≤ H, δ ′ ∈ (0, 1) and positive integer n, define the functionEQUATIONH ln 1 δ ′ n    .Then, the function f (p, v, n) is non-decreasing in each entry of v.Lemma 24 (Efroni et al. 2021, Lemma 28) . Let Y ∈ R S be a vector such that 0 ≤ Y (s) ≤ H for all s ∈ S. Let P 1 and P 2 be two transition models and n ∈ R Lemma 25 (Efroni et al. 2021, Lemma 27) . Let {Y t } t≥1 be a real-valued sequence of random variables adapted to a filtration {F t } t≥0 . Assume that for all t ≥ 1 it holds that 0 ≤ Y t ≤ C a.s., and let T ∈ N. Then each of the following inequalities holds with probability greater than 1 -δ. Lemma 26 (Standard Deviation Differences, e.g., Zanette and Brunskill 2019, lines 48-51) . Let P ∈ ∆ d be some distribution over [d] and let V 1 , V 2 ∈ R d . Then, it holds thatVar P (V 1 ) -Var P (V 2 ) ≤ Var P (V 1 -V 2 ).Lemma 27 (Law of Total Variance, e.g., Zanette and Brunskill 2019, Lemma 15) . For any nolookahead policy π, it holds thatE H h=1 Var(V π h+1 (s h+1 )|s h )|π, s 1 = E   H h=1 r h (s h , a h ) -V π 1 (s 1 ) 2 |π, s 1   ,where Var(V π h+1 (s h+1 )|s h ) is the variance of the value at step s h+1 given state s h and under the policy π, due to the policy randomization and next-state transition probabilities.• The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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.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 (NeurIPS2024).This assumption is not used by our algorithms: it is only to ensure that the optimal policy is Markovian. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.


2. 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. 

[R1] Bertsekas, Dimitri. Reinforcement learning and optimal control. Vol. 1. Athena Scientific, 2019.
[R2] Biedenkapp, André, et al. "TempoRL: Learning when to act." International Conference on Machine Learning. PMLR, 2021.
[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.


3.  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.
questions: questions: 1. When the agents have access to both reward lookahead and transition lookahead, how would the regret bound be different?

2. 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: limitations: Discussed in the Weakness section.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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. 

[1] Chung, Stephen, Ivan Anokhin, and David Krueger. "Thinker: learning to plan and act." Advances in Neural Information Processing Systems 36 (2024).
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

Algorithm 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.
questions: questions: Line 150， the sentence should be "in this way"?

The 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. 

For 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: limitations: None
paper_summary: paper_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).
strength_weakness: strength_weakness: While the theoretical contribution is clear, the authors must also provide practical validation.
questions: questions: - Perform experimental validation to illustrate the practical performance. 
  For instance, it would be necessary to check the learning curves and the resulting performance. 
  The authors should also discuss the practical implementation. 

- H is the important parameter to be determined. Provide a practical guide line for choosing H. 

- can this method be extended to off-policy learning ?
  Is the method data-efficient ?
limitations: limitations: Some aspects of the approach might be seen as incremental advancements  rather than groundbreaking theoretical analysis .
paper_summary: paper_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:

1) Formalising the look-ahead setting for the reward and transition in an episodic MDP setting.
2) Derivation of the Bellman equations in the original space by setting up an equivalence with an equivalent new MDP.
3) Development of two algorithms for reward (MVP-RL) and transition lookahead ( MVP-TL).
4) First sub-linear regret bound win the lookahead setting.
strength_weakness: strength_weakness: 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.
questions: questions: How applicable is the theoretical argument you used to a model-free version of MVP-RL/TL?
limitations: 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.

Comments: title: Questions
comment: Thanks for your reply. I will maintain my score after reading your reply.
Yes, exactly!

Thanks for the improvement suggestions - we will correct all these issues in the final version of the paper. We will also reflect on our writing and presentation to make sure that all the questions that were raised in the discussion here will be clearer.
We thank the reviewer again. 

Combining multi-step lookahead with the decision of which future information to query is indeed a great question, also from a theoretical point of view! We will read the work in further detail and discuss the relations in the final version of the paper.
Thanks for the clarification and I think I understand now. Basically with additional information (lookahead) the optimal value of the MDP increases compared to vanilla agent, so standard algorithms that don't leverage the information can't compete. I was focusing on how the information helps with learning efficiency and omitted its role in planning.

Re blow-up: the explanation makes sense. As a minor change, perhaps it will be good to point to the construction in the appendix from the main text, and whenever the paper uses the word "exponential", say exponential-in-what (action, dimension, etc.).
Thanks for the response. I maintain my score after reading the responses and reviews.

One thing to note - works like [1] can usually be used to perform what you described. For example, in [1], one can replace the learned world model (the state-reward network in the dual network that is proposed) with the known environment dynamics so the agent can learn to take advantage of the stochasticity as in your example. The main difference with your proposed algorithm is that the agent has to decide which action to try instead of seeing all possible action's consequences. This, however, is essential for multi-step lookahead, as one cannot enumerate all action sequences with a decent depth.
Dear area chair,

Thank you for your questions.

1. The key reason that our paper breaks through the lower bound is the different definition of regret, and in particular, the definition of the optimal value. Specifically, denote $V^*$ the standard no-lookahead value used in RL, and $V^{R, *}$ the reward lookahead value, with the corresponding regret bounds $Reg$ and $Reg^R$. 

    Notice that for any agent (lookahead or not), one can always write $Reg = (V^* - V^{R,*})K + Reg ^R$.

   By definition, the lookahead agent is more powerful, so mostly $V^* < V^{R,*}$. Since the first term in the decomposition above is negative linear while the second term is just sublinear, any difference between the values imposes a *negative linear regret* - completely breaking the standard lower bounds in RL. 

    For example, in Section 3, we described situations where $V^*\approx 1/AH$ while $V^{R,*}\approx 1$. Then, in terms of standard regret, for large enough $K,A,H$ we would get $Reg \approx -K$. We can add this explanation to the paper.

* In Jin et al. (2018), they have $T=HK$ (see caption under table 1), where $K$ is the number of episodes (as in our paper). Therefore, the lower bounds are the same - both allow non-stationary transition. 

2. While reward learning doesn't usually dominate the rates, it is due to horizon factors: reward learning usually leads to a term of $\sqrt{H^2SAK}$ while transition learning to $\sqrt{H^3SAK}$. Even if we can just discretize the state for the reward component to a state $S^d$ (while not changing transition learning complexity), we would still have unavoidable dependence in the regret on $S^d$. Importantly, $S^d$ needs to encompass the reward observations for *all actions simultaneously*, so even if we use $N$ cells to discretize each reward component, we would get a term of $N^A$. Therefore, as soon as we do it, our bounds would explode (even if reward learning would just have affected the additive constant!!). 

    Moreover, moving the reward to the state means that reward observations are now state transitions, so using standard approaches would lead to a regret bound of $\sqrt{H^3S^dAK}$.

    You are completely right about the transition lookahead - since we need to add the next state observation for all actions simultaneously, the state blows by a factor $S^A$.

    We actually already use the augmented MDP for both proofs (mostly for the planning results) and describe in detail one way to do this extension in Appendices B.2 and C.2. If the AC thinks it would help clarity, we could further discuss it in the main paper. We could also discuss more about the implications of augmentation and discretization on learning, extending the discussion in this response. 

----

We hope that we clarified all the issues; we will gladly provide more clarifications if we did not convey the message clearly enough and answer any other questions.
Dear authors,

Thanks for the rebuttal. As I go over the reviews and your rebuttal, I have some quick questions which I hope to get some clarifications:

1. The paper refers to lower bounds in standard (i.e., no lookahead information) RL settings in several places (e.g., Line 190). Since the current setting provides additional information to the agent, one would expect that the upper bound you obtain to penetrate through the lower bounds in standard settings (for agents without such additional information), but I couldn't find a crisp statement on this in the paper.

More concretely, according to Table 1 in Jin et al. (2018), best upper bound is $\sqrt{H^2 SA T}$ (their $T$ is your $K$, and I also verified the reward boundedness conventions in two papers which are identical). Both of your results (Line 48) seem no better than this bound (the reward lookahead one is worse by $\sqrt{T}$, and the transition look-ahead one has an extra additive term)? I would appreciate a clarification here. If your result penetrates through the standard RL lower bound, a crisp, unambiguous complexity comparison will be very helpful.

* I also noticed the $\sqrt{H^3 SA T}$ lower bound on Line 191, which contradicts the upper bound I quoted above. Likely this is due to whether transition is time homogeneous...?

2. I agree with Line 149 that state augmentation is the most natural idea. The paper discusses why this approach does not work, but I am not entirely convinced by the argument. Reward continuity is discussed as a major difficulty (Line 40), but (1) one can usually discretize reward to get around it, and (2) reward learning is relatively easier than transition learning (as discussed on Line 289) and usually doesn't dominate the final rate. So one can simply ignore the reward lookahead information and solely focus on the transition lookahead information, in which there is no concern of continuity. So what is the main difficulty here? I imagine the problem is that since there is additional information for every action, the state space will blow-up in a way that may be exponential in A. Regardless, I think a formal description of the augmented MDP (define state, action, reward, transition, etc., after the augmentation) will be very useful, possibly in the appendix.

AC