{'fraction_non_alphanumeric': 0.032270299314137614, 'fraction_numerical': 0.011978886816903189, 'mean_word_length': 4.664160401002507, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Delayed Geometric Discounts: An Alternative Criterion for Reinforcement Learning

The endeavor of artificial intelligence (AI) is to design autonomous agents capable of achieving complex tasks. Namely, reinforcement learning (RL) proposes a theoretical background to learn optimal behaviors. In practice, RL algorithms rely on geometric discounts to evaluate this optimality. Unfortunately, this does not cover decision processes where future returns are not exponentially less valuable. Depending on the problem, this limitation induces sample-inefficiency (as feed-backs are exponentially decayed) and requires additional curricula/exploration mechanisms (to deal with sparse, deceptive or adversarial rewards). In this paper, we tackle these issues by generalizing the discounted problem formulation with a family of delayed objective functions. We investigate the underlying RL problem to derive: 1) the optimal stationary solution and 2) an approximation of the optimal non-stationary control. The devised algorithms solved hard exploration problems on tabular environment and improved sample-efficiency on classic simulated robotics benchmarks.


INTRODUCTION
In the infinite horizon setting, and without further assumptions on the underlying Markov Decision Process (MDP), available RL algorithms learn optimal policies only in the sense of the discounted cumulative rewards (Puterman, 2014). While the geometric discounting is well suited to model a termination probability or an exponentially decaying interest in the future, it is not flexible enough to model alternative weighting of the returns. Consider for example settings where the agent is willing to sacrifice short term rewards in favor of the long term outcome. Clearly, for such situations, a discounted optimality criterion is limited and does not describe the actual objective function. This is particularly true in hard exploration tasks, where rewards can be sparse, deceptive or adversarial. In such scenarios, performing random exploration can rarely lead to successful states and thus rarely obtain meaningful feedback. Geometric discounts tend to fail in such scenarios. Consider for example the U-maze environment in Figure 1a, where the reinforcement signal provides a high reward (+1) when reaching the green dot in the bottom arm, a deceptive reward (+0.9) when reaching the blue dot in the upper arm, and a negative reward (−1) for crossing the red corridor. If the agent is only interested in the long term returns, then the optimal control should always lead to the green dot. However, depending on the initial state, optimal policies in the sense of the discounted RL problem are likely to prefer the deceptive reward due to the exponentially decaying interest in the future (Figure 1b).
Naturally, higher discount factors are associated with optimal policies that also optimize the average returns (Blackwell, 1962), which can solve in principle the described hard exploration problem. However, in practice, such discount values can be arbitrarily close to 1 which entails severe computational instabilities. In addition, and particularly in continuous settings or when tasks span over extremely long episodes, discount-based RL approaches are sample-inefficient and are slow at propagating interesting feed-backs to early states.
In this paper, we generalize the geometric discount to derive a variety of alternative time weighting distributions and we investigate the underlying implications of solving the associated RL problem both theoretically and practically. Our contributions are twofold. First, we introduce a novel family that generalizes the geometrically discounted criteria, which we call the delayed discounted criteria. Second, we derive tractable solutions for optimal control for both stationary and non-stationary policies using these novel criteria. Finally, we evaluate our methods on both hard exploration tabular environments and continuous long-episodic robotics tasks where we show that: 1. Our agents can solve the hard exploration problem in a proof of concept setup.
2. Our methods improve sample-efficiency on continuous robotics tasks compared to Soft-Actor-Critic. Figure 1c showcases how non-geometrically discounted criteria impacts the profile of optimal value function in the U-maze example.
(a) (b) (c) Figure 1: (a) Hard exploration problem example, (b) optimal value function of geometrically discounted RL with a discount factor γ = 0.99 and (c) non-geometrically discounted RL.

REINFORCEMENT LEARNING WITH NON GEOMETRIC DISCOUNT
Consider an infinite horizon Markov Decision Process (MDP) M = {S, A, P, r, γ, p 0 }, where S and A are either finite or compact subsets of respectively R d and R d , (d, d ) ∈ N 2 , P : S × A → ∆(S) is a state transition kernel 1 , r : S × A → R is a continuous reward function, p 0 ∈ ∆(S) an initial state distribution and γ ∈ (0, 1) is the discount factor. A policy π is a mapping indicating, at each time step t ∈ N, the action a t to be chosen at the current state s t . The goal of geometrically discounted reinforcement learning algorithms is to optimize the discounted returns: where E π,p0 denotes the expectation over trajectories generated in M using the policy π and initialised according to p 0 .
In this section, we present our methods. First, Section 2.1 introduces our delayed discounted family of optimality criteria. Then, Section 2.2 investigates the optimization of the linear combination of this new family in the context of stationary policies. Finally, Section 2.3 generalizes the optimal control to non-stationary policies.

BEYOND THE GEOMETRIC DISCOUNT: A DELAYED DISCOUNTED CRITERION
We propose to investigate a particular parametric family of optimality criteria that is defined by a sequence of discount factors. For a given delay parameter D ∈ N, we define the discount factors γ d ∈ (0, 1) for any integer d ∈ [0, D] and we consider the following loss function: 1 ∆(S) denotes the set of probability measures over S This class of optimality criteria can be seen as a generalization of the classical geometric discount. In fact, we highlight that for D = 0, Φ 0 (t) = γ t 0 which implies that L 0 (π, r) = L(π, r) for any policy π and any reward function r. In Figure 2, we report the normalized distribution of the weights Φ D (t) (i.e. y(t) = Φ D (t) i Φ D (i) ) over time as we vary the parameter D ∈ {0, . . . , 9}. Notice how the mode of the probability distribution is shifted towards the right as we increased the delay, thus putting more weights on future time steps. Intuitively, the proposed criterion (L D ) describes the goal of an agent that discards short term gains in favor of long term discounted returns. In the following, we consider yet a more diverse problem formulation by using a linear combination of the delayed losses. Let L η be the following objective function defined as: where the depth D ∈ N and the coefficients w d ∈ R for any d ∈ [0, D] are known.
In general, the optimal control in the sense of L η is not stationary. However, learning solutions that admit compact representations is crucial for obvious computational reasons. In the following we propose to learn either the optimal stationary solution, or to approximate the optimal control with a non-stationary policy over a finite horizon followed by a stationary one.

OPTIMAL STATIONARY POLICIES
In this section, we propose to learn stationary solution using a policy-iteration like algorithmic scheme. As in the classical setting, the goal is to learn a control π * that maximizes the state-action value function Q π η : This is done by iteratively evaluating Q π η and then updating the policy to maximize the learned value function. Due to the linearity illustrated in Equation 3, the policy evaluation step is reduced to the estimation of Q π d . In geometrically discounted setting, the value function is the fixed point of the Bellman optimality operator. Luckily, this property is also valid for the quantities Q π d : Proposition 1 For any discount parameters (γ d ) D d=0 , the value functions Q π D is the unique fixed point of the following γ D -contraction: The value Q π D of a policy π with respect to the delayed criterion L D is the state-action value function of the same policy using an augmented policy dependent reward r π D w.r.t. the γ D -discounted returns. Intuitively, the instantaneous worth of an action (r π D ) is the sum of the environments' myopic returns (r(s, a)) and the long term evaluations (with lower delay parameters (Q π d ) d<D ). This has the beneficial side-effect of enhancing sample efficiency as it helps the agent to rapidly back-propagate long-term feed-backs to early states. This reduces the time needed to distinguish good from bad behaviors, particularly in continuous settings where function approximation are typically used to learn policies. This is discussed in details in Section 4.2.
Similarly to standard value based RL algorithms, given a data set of trajectories D = {s, a, s }, the value function Q π d can be approximated with parametric approximator Q θ d by optimising J Q d (θ): As for the policy update step, inspired from the Soft-Actor-Critic (SAC) algorithm, we propose to optimize an entropy regularized soft Q-value using the following loss where α is a parameter: We use Equations 5 and 6 to construct Algorithm 1, a generalization of the SAC algorithm that approximates optimal stationary policies in the sense of L η . In practice, this can be further improved using the double Q-network trick and the automatic tuning of the regularization parameter α. This is discussed in Appendix A.1. Unfortunately, unlike the geometrically discounted setting, the policy improvement theorem is no longer guaranteed in the sense of L η . This means that depending on the initialization parameters, Algorithm 1 can either converge to the optimal stationary control or get stuck in a loop of sub-optimal policies. This is discussed in detail in Section 4.1.

APPROXIMATE OPTIMAL CONTROL
In the general case, the optimal control is not necessarily stationary. Consider the problem of learning the optimal action profile a * 0:∞ which yields the following optimal value function: where E a0:∞ is the expectation over trajectories generated using the designated action profile. In this section we propose to solve this problem by approximating the value function from Equation 7. This is achieved by applying the Bellman optimality principle in order to decompose V * η into a finite horizon control problem (optimising a 0:H with H ∈ N) and the optimal value function V * where f is an operator transforming the weighting distribution as follows: For the sake of simplicity, let 1, η := D d=0 w d and f n (η) (t) := Γ n ·w, Φ(t) for any n, t ∈ N.
Proposition 2 For any state s 0 ∈ S, the following identity holds: As a consequence, the optimal policy in the sense of L η is to execute the minimising arguments a * 0:H of Equation 8 and the execute the optimal policy in the sense L f H+1 (η) . Unfortunately, solving L f H+1 (η) is not easier than the original problem.
However, under mild assumptions, for H large enough, this criterion can be approximated with a simpler one. In order to derive this approximation, recall that the power iteration algorithm described by the recurrence v k+1 = Γ·v k Γ·v k converges to the unit eigenvector corresponding to the largest eigenvalue of the matrix Γ whenever that it is diagonalizable. In particular, if 0 < γ D < ... < γ 0 < 1 and v 0 = w, then Γ is diagonalizable, γ 0 is it's largest eigenvalue and the following holds: Under these premises, the right hand term of the minimisation problem in Equation 8 can be approximated with the optimal value function in the sense of the classical RL criterion L (which optimal policy can be computed using any standard reinforcement learning algorithm in the literature).
Formally, we propose to approximate Equation 8 with a proxy optimal value functionṼ * η,H (s 0 ): A direct consequence of Equation 9 is that lim H→∞Ṽ * η,H (s) = V * η (s) for any state s ∈ S. In addition, for a given horizon H, the optimal decisions in the sense of the proxy problem formulation are to execute for the first H steps the minimising arguments a * 0:H of Equation 10 (they can be computed using dynamic programming) and then execute the optimal policy in the sense of the γ 0 -discounted RL (which can be computed using any standard RL algorithm).
Algorithm 2 H-close optimal control

RELATED WORK
Bridging the gap between discounted and average rewards criteria. It is well known that defining optimality with respect to the cumulative discounted reward criterion induces a built-in bias against policies with longer mixing times. In fact, due to the exponential decay of future returns, the contribution of the behaviour from the T th observation up to infinity is scaled down by a factor of the order of γ T . In the literature, the standard approach to avoid this downfall is to define optimality with respect to the average reward criterionL defined as : This setting as well as dynamic programming algorithms for finding the optimal average return policies have been long studied in the literature (Howard, 1960;Veinott, 1966;Blackwell, 1962;Puterman, 2014). Several value based approaches (Schwartz, 1993;Abounadi et al., 2001;Wei et al., 2020) as well as policy based ones (Kakade, 2001;Baxter & Bartlett, 2001) have been investigated to solve this problem. These approaches are limited in the sense that they require particular MDP structures to enjoy theoretical guarantees.
Another line of research, is based on the existence of a critical discount factor γ crit < 1 such that for any discount γ ∈ (γ crit , 1) the optimal policy in the sense of the γ-discounted criterion also optimises the average returns Blackwell (1962). Unfortunately, this critical value can be arbitrarily close to 1 which induces computational instabilities in practice. For this reason, previous works attempted to mitigate this issue by increasing the discount factor during training (Prokhorov & Wunsch, 1997), learning higher-discount solution via learning a sequence of lower-discount value functions (Romoff et al., 2019) or tweaking the reinforcement signal to equivalently learn the optimal policy using lower discounts (Tessler & Mannor, 2020).
Exploration Strategies. Another line of research attempted to tackle the hard exploration problem by further driving the agents exploration towards interesting states. Inspired by intrinsic motivation in psychology (Oudeyer & Kaplan, 2008), some approaches train policies with rewards composed of extrinsic and intrinsic terms. Namely, count-based exploration methods keep track of the agents' past experience and aim at guiding them towards rarely visited states rather than common ones (Bellemare et al., 2016;Colas et al., 2019). Alternatively, prediction-based exploration define the intrinsic rewards with respect to the agents' familiarity with their environments by estimating a dynamics prediction model (Stadie et al., 2015;Pathak et al., 2019). Other approaches maintain a memory of interesting states (Ecoffet et al., 2019;2021), trajectories  or goals (Guo & Brunskill, 2019). Ecoffet et al. (2019;2021) first return to interesting states using either a deterministic simulator or a goal-conditioned policy and start exploration from there.  train a trajectory-based policy to rather prefer trajectories that end with rare states. Guo & Brunskill (2019) revisit goals that have higher uncertainty. Finally, based on the options framework (Sutton et al., 1999), options-based exploration aims at learning policies with termination conditions-or macro-actions. This allows the introduction of abstract actions, hence driving the agents' exploration towards behaviours of interest (Gregor et al., 2016;Achiam et al., 2017).

EXPERIMENTS
In this section, we evaluate the performance of the proposed algorithm. Our goal is to answer the following questions: • How does the different parameters impact the ability of the proposed algorithms to solve hard exploration problems? • How does the proposed algorithm impact the performance in classical continuous control problems?

HARD EXPLORATION PROBLEMS
In this section we investigate our ability to approximate the solution of the proposed family of RL problems (w.r.t. the optimality criterion L D ) in discrete hard exploration maze environments. We fix the discount factor values to γ i = 0.99 − i 1000 throughout the experiments. This guarantees that Γ is diagonalizable and that its largest eigenvalue is γ 0 = 0.99. We evaluate the performance of both Algorithms 1 and 2 as we vary the depth parameter and as we increase the non stationarity horizon.
In Figure 3 we reported the shapes of the mazes as well as the used reinforcement signal in each of them. We used a sparse signal where the green dots represent the best achievable reward, the blue dots are associated with a deceptive reward and the red dots are associated with a penalty. This setting is akin to hard exploration problems as the agent might learn sub-optimal behaviour because of the deceiving signal or because of the penalty. Stationary solutions: We start by evaluating the performances of the learned policies using Generalised Soft Actor Critic (GSAC) (Algorithm 1). As discussed earlier, unlike the geometrically discounted setting, the policy update is not guaranteed to improve the performances. For this reason, depending on the initialisation, the algorithm can either converge to the optimal stationary policy, or get stuck in a sequence of sub-optimal policies.
In Figure 4, we reported the performances of GSAC as we varied the depth hyper-parameter D using two initialisation protocol. The blue curves are associated with a randomly selected initial parameters while the red curves are associated with experiment were the policy is initialised with the solution of the geometrically discounted problem. The solid lines correspond to the average reward while the dashed lines correspond to the Φ d weighted loss (as computed in L d ).
In all experiments, the expectations were averaged across 25 runs of the algorithm using trajectories of length 4000 initialised in all possible states (uniform p 0 ) . A common observation is that for a depth D higher than 6 7 the algorithm was unstable and we couldn't learn a good stationary policy in a reliable way. However, the learned stationary policies with even a relatively shallow depth parameter yielded reliable policies that not only maximise the Φ D weighted rewards but also improved the average returns. Notice how the baseline (D = 0, i.e. the geometrically discounted case) always under-performs when compared to the learned policies for a depth parameter around 3.
We also observe that the algorithm is sensitive to the used initialisation. Using the optimal policy in the sens of the geometrically discounted objective (red curves) helped stabilise the learning procedure in most cases: this is particularly true in the random maze environment where a random initialisation of the policy yielded bad performances even with a low depth parameter. This heurestic is not guaranteed to produce better performances in all cases, notice how for D = 7 in the T-maze, a random initialisation outperformed this heuristic consistently.
Optimal Control Approximation: In this section we investigate the performances of the policies learned using Algorithm 2 as we vary the non stationarity horizon H for three depth parameters D ∈ {5, 10, 15} (respectively the red, blue and green curves). As in the last experiment, we reported the expected returns as the average rewards using the continuous lines and as the Φ D weighted rewards using dashed lines. As a baseline, we can observe in each figure the performances of the optimal policy in the sense of the geometrically discounted criterion when the non-stationarity horizon H = 0. We also reported the performances of the best stationary policy learned using GSAC for a depth parameter D = 5.
The first notable observation is that increasing the hyper-parameter H does indeed improve performances. In addition, we notice that the maximum possible improvement is reached using a finite horizon H (i.e. the maximising argument of bothṼ η,H and V * η are the same). Intuitively, the H non stationary steps enable the agent to get to an intermediate state from which the optimal policy in the sense of the discounted RL formulation can lead to the state with the highest rewards. This explains the effectiveness of current hard exploration RL algorithmsEcoffet et al. (2019) In the case of D = 5, the obtained performances using Algorithm 2 converged to the performances of the optimal stationary policy obtained using GSAC in both the random and T-maze. On the other hand, unlike GSAC, the H-close algorithm is not sensitive to initialisation: in fact notice how even for arbitrarily high depth parameter (D = 15) the learned policy ends up saturating the average and the Φ D weighted rewards. More interestingly, increasing the depth can be beneficial as we observe empirically that for higher depth parameters, the non-stationarity horizon required to achieve the best possible performances decreases.

SIMULATED CONTINUOUS CONTROL BENCHMARKS
In this section, we propose to evaluate our methods on several continuous robotics domains. To this end, we consider 5 different environments within the MUJOCO physics engine (Todorov et al., 2012): Walker2d, Hopper, HalfCheetah, Ant and Humanoid. As results in the tabular settings showed that there exists a threshold beyond which increasing the value of the delay D hurts the performance, we fix D = 1, where only two discount factors γ 0 and γ 1 are used. We compare our proposed methods to the classic SAC algorithm to investigate the implications of using both critics Q θ0 and Q θ1 .
In Figure 6, we report the average rewards obtained by the different agents over time. Note that in all the environments, the GSAC agents are faster in collecting positive rewards than the SAC agents. The main reason behind this is that the critic tends to discern good from bad actions in the GSAC agents faster than the SAC agents. In fact, on the one hand, the SAC agents spend more time uncertain about the quality of their actions for a given state, and thus need more time and more experience to make the estimations of their critic more accurate and reflecting the true long-term value of an action. On the other hand, in the GSAC agents, Q θ1 takes into consideration the estimate of the actions by Q θ0 , and thus there is less uncertainty about their quality.

CONCLUSION
Designing human-like autonomous agents requires (among other things) the ability to discard short term returns in favor of long term outcomes. Unfortunately, existing formulations of the reinforcement learning problem stand on the premise of either discounted or average returns: both providing a monotonic weighting of the rewards over time.
In this work, we propose a family of delayed discounted objective functions that captures a wide range of non-monotonic time-preference models. We analyse the new formulation to construct 1) the Bellman optimality criterion of stationary solution and 2) a feasible iterative scheme to approximate the optimal control. The derived algorithms successfully solved tabular hard exploration problems and out-performed the sample efficiency of SAC in various continuous control problems; thus closing the gap between what is conceivable and what is numerically feasible.

BROADER IMPACT STATEMENT
Reinforcement learning provides a framework to solve complex tasks and learn sophisticated behaviors in simulated environments. However, its incapacity to deal with very sparse, deceptive and adversarial rewards, as well as its sample-inefficiency, prevent it from being widely applied in real-world scenarios. We believe investigating the classic optimality criteria is crucial for the deployment of RL. By introducing a novel family of optimality criteria that goes beyond exponentially discounted returns, we believe that we take a step towards more applicable RL. In that spirit, we also commit ourselves to releasing our code soon in order to allow the wider community to extend our work in the future. Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Modelfree reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference on machine learning, pp. 10170-10180. PMLR, 2020.

A.1 IMPLEMENTATION DETAILS IN CONTINUOUS ROBOTICS BENCHMARKS
This part includes details necessary to reproduce results in the continuous robotics environments. The code will be released with the camera-ready version of the paper.
Soft Actor Critic Details. Our algorithms are based on the Soft Actor Critic algorithm (Haarnoja et al., 2018). Notably, we use the double Q-Networks trick to help tackle the overestimation bias (Fujimoto et al., 2018). In our experiments, we do not automatically tune the entropy hyperparameter α. In fact, we found that fixing its value to α = 0.2 is sufficient for the purpose of this paper.
Delayed Networks. As the results for the GSAC learned stationary policies show that the performance tend to decrease for high values of delay D, we opt for D = 2 in the continuous robotics experiments. Our main objective is to study the effect of shallow delayed geometric discounts on classic robotics environments.
Networks Architecture. Each of the discount factors γ 1 and γ 2 is associated with a different critic and target critics networks. All these networks, as well as the policy, are 1-hidden layer networks of hidden size 256. They use ReLU activations and the Xavier initialization. We use Adam optimizers, with learning rates 3 × 10 −4 . The list of hyperparameters is provided in Table 1. In this section, we consider a simple 2000 states long corridor environment with a deceptive reward of 0.9 on one extremity, a desirable reward of 1 on the other and an adversarial reward of −1 in the middle (states 990 to 1010). For this environment, we consider that a policy is successful if it ends up reaching the best reward and that it failed in any other scenario (including the case where it reaches the deceptive reward). The success rate of a policy is consequently the proportion of states from which it reaches the best reward.
we investigate the performances of the obtained policies using GSAC 2 as we vary the delay parameter D ∈ {0, . . . , 14} and the discounts γ i≤D = γ ∈ [1 − 10 −1 , 1 − 10 −14 ]. For each couple of values, we evaluate the best (Figure 7a) and the average (Figure 7b) success rate of the learned policies in 10 randomly initialised runs of GSAC. The obtained performances are reported in Figure 7 as heat-maps where higher success rates (close to 1) are associated with red and lower ones with blue.
Naturally, for low discount parameter γ, the success rate is around 0.5 as states on each side of the adversarial reward are encouraged to leave that area in the direction of the closest positive reward. Interestingly, there is a limiting curve (continuous yellow line in Figure 7b) above which the best stationary policy in the sense of L D has a success rate of 1, and a second line (dashed yellow line) above which numerical instabilities induce poor numerical performances.
Notice that if we consider the vertical line in Figure 7 corresponding to D = 0, we recover the Blackwell criterion: there exist a critical value of the discount above of which agents are capable to reach the desirable reward. Intuitively, these observations generalize this criterion to the delayed geometrically discounted framework: There exists a critical frontier that depends on both the delay D and the discounts γ i≤D , above of which optimal stationary policies in the sense of the delayed criterion L D is also optimal in the sense of the average criterion In this section, we advance additional results in the continuous settings. We introduce two different maze environments based on the MUJOCO robotics engine: SMaze-v0 and UMaze-v0 (Figure 8).
In both environment, the agent is a sphere whose action space is 2-dimensional. The attributes of its state space correspond to both its positions and its velocity. The environment also contain two rewarding states: a deceptive rewarding state of +0.8 (blue dot) and a maximal rewarding state of +1.0 (red dot). Evaluation. To evaluate ours agents, we discretize the considered mazes into many cells (See Figure 9 for an illustration). At the beginning on each test episode, we initialize the agents in all the discretized cells. Following the experimental section of the main paper, we compare our proposed GSAC algorithm to the classic SAC algorithm. Our goal is to see if these agents are able to distinguish deceptive from real rewards from the cell they were initialized in.
Results. The grid plot on Figure 9 highlights the average rewards obtained by the agents when initialized in different cells. Experiments were conducted over 5 seeds. Depending on the cell in which they were initialized, both agents choose to opt either for the deceptive or the real reward. However, the GSAC agent is capable of choosing the real reward even if it was initialized close to the deceptive one. Meanwhile, the SAC agent is more myopic, as the number of cells that leads it to the deceptive rewards are more than the ones encountered in GSAC.

B.1 USEFUL INTERMEDIATE RESULTS
We start by introducing some useful intermediate results that will be used later on to prove propositions 1 and 2.
USEFUL RESULTS FOR PROPOSITION 1 To derive the desired property of the value function, it is useful to derive a relationship between the coefficients Φ D (t): Lemma 1 For any integer D > 0 , the following equalities hold: Now, consider the state-value function V π d (s) defined as: Lemma 1 can be used to derive a relationship between the value functions (V π d ) D d=0 for any depth parameter D ∈ N: Proposition 3 For any state s ∈ S and for any integer D ∈ N, we have: This proposition is proved using an induction reasoning. For this reason, we start by consider the simpler case of H = 1: Proposition 4 For any state s 0 ∈ S, the following identity holds:

B.2 PROOFS
In this section we provide the proofs of the technical results

PROOF OF PROPOSITION 1
Recall that: Q π D (s, a) = E s ∼P(s,a) V π D (s ) Then the statement from Proposition 3 can be reformulated as Which means that Q π D is a fixed point of T D π . Given that this operator is a γ D contraction with γ D ∈ (0, 1), it follows that it is the unique fixed point. This concludes the proof of the first equality. Similarly, the second equality is achieved through similar algebraic treatments: This concludes the proof of the second equality. The last one can be deduced directly using induction. In fact, the induction is a direct consequence of the second equality, and the basis case is trivially verified as:

PROOF OF PROPOSITION 3:
The proof relies on some algebraic manipulation as well as the last equality from Lemma 1.
V π D (s) = E π where the last equality relies on the Markov property of MDPs.

PROOF OF PROPOSITION 4:
The proof relies on the linearity of the expectation as well as proposition 3. Let's denote in this proof with the policy π the sequence of action a 0 , a 1 , . . . , a ∞ and with the transposed policy T π the sequence of actions a 1 , a 2 , . . . , a ∞ . The following property then holds w d c(s 0 , a 0 ) + E s1∼P(s0,a0) V * f (η) (s 1 )