# DELAYED GEOMETRIC DISCOUNTS: AN ALTERNATIVE
## CRITERION FOR REINFORCEMENT LEARNING

**Anonymous authors**
Paper under double-blind review

ABSTRACT

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.

1 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 SoftActor-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.

2 REINFORCEMENT LEARNING WITH NON GEOMETRIC DISCOUNT

Consider an infinite horizon Markov Decision Process (MDP) = _,_ _,_ _, r, γ, p0_, where
_M_ _{S_ _A_ _P_ _}_ _S_
and∆( _A) is a state transition kernel are either finite or compact subsets of respectively[1], r :_ R is a continuous reward function, R[d] and R[d][′], (d, d[′]) ∈ N[2], p P0 : S × A →∆( ) an
initial state distribution andeach time stepS _t ∈_ N, the action γ ∈ (0 at, 1) to be chosen at the current state S × A → is the discount factor. A policy s πt. The goal of geometrically is a mapping indicating, at ∈ _S_
discounted reinforcement learning algorithms is to optimize the discounted returns:

_[∞]_
_L(π, r) := Eπ,p0_ _γ[t]rt_ _;_ _rt := r(st, at)_

_t=0_

h X i

where Eπ,p0 denotes the expectation over trajectories generated in M using the policy π and initialised according to p0.

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.

2.1 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:
_∈_ _∈_

_[∞]_ _N_
_D(π, r) := Eπ,p0_ ΦD(t)rt _where_ ΦD(t) := _γd[a][d]_ (1)
_L_
h Xt=0 i _{ad∈XN}d[D]=0_ _dY=0_

_such that_ _d_ _[a][d][=][t]_

[P]

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) = γ0[t] [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 moreP
weights on future time steps.

1∆(S) denotes the set of probability measures over S


-----

Figure 2: The normalized coefficients ΦD(t) over time for different values of the delay parameter D

Intuitively, the proposed criterion ( _D) describes the goal of an agent that discards short term gains_
_L_
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:

_D_

_η(π, r) := Eπ,p0_ _η(t)rt_ _such that_ _η(t) =_ _wdΦd(t)_ (2)
_L_

_t_ _d=0_

h X i X

where the depth D N and the coefficients wd 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.

2.2 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[π]η [:]


_D_ _[∞]_

_wdQ[π]d_ [(][s, a][)] _where_ _Q[π]d_ [(][s, a][) :=][ E][π] Φd(t)rt|s0, a0 = s, a (3)
_d=0_ _t=0_

X h X i


_Q[π]η_ [(][s, a][) =]


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:_


_D−1_

_r(s, a) +_ _γdQ[π]d_ [(][s][′][, a][′][)]

_d=0_

X

:= rD[π] [(][s, a][)]
{z



[Tπ[D][(][q][)](][s, a][) =][ E]s[′] (s,a)
_∼P_
_a[′]∼π(s[′])_


+γDEs[′]∼P(s,a)
_a[′]∼π(s[′])_


_q(s[′], a[′])_ _._ (4)
i


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 rD[π] [w.r.t. the][ γ][D][-discounted returns.]


-----

Intuitively, the instantaneous worth of an action (rD[π] [) 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]d[Q][(][θ][)][:]


1

2

h


_D_

_γdQθ¯d_ [(][s][′][, a][′][))][2][i] (5)
_d=0_

X


_JD[Q][(][θ][) =][ E]_ _s,a,s[′]_
_∼D_
_a[′]∼πφ(s[′])_


_Qθ_ (r(s, a) +
_−_


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:

_[D]_
_Jη[π][(][φ][) =][ −][E][s][∼D][,a][∼][π]φ_ _wdQθ¯d_ [(][s, a][)][ −] _[α][ log(][π][φ][(][a][|][s][))]_ (6)

_d=0_

h X i

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 _η. In practice, this can be further improved_
_L_
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 _η. This means that depending on the_
_L_
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.

**Algorithm 1 Generalized Soft Actor Critic**

1: Input: initial parameters (θd)[D]d=0[, φ][, learning rates][ (][λ][d][)][D]d=0[, λ][π][, pollyak parameter][ τ]

3:2: for initialise target network each iteration do _θ[¯]d ←_ _θd and initialise replay buffer D ←∅_
4: **for each environment step do**

5: _at_ _πφ(st), st+1_ (st, at), (st, at, st+1, ct)

6: **for d ∼ ∈** [0, D] do _∼P_ _D ←D ∪{_ _}_

7: **for each Qd gradient step do**

9:8: **for each policy updateupdate parameter θ dod ←** _θd −_ _λd∇[ˆ]_ _θd_ _Jd[Q][(][θ][d][)][ and update target][ ¯]θd ←_ _τ_ _θ[¯]d + (1 −_ _τ_ )θd

10: update policy φ ← _φ −_ _λπ∇[ˆ]_ _φJη[π][(][φ][)]_

11: Return: πφ, (Qθ¯d [)]d[D]=0


2.3 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:]

_[∞]_
_Vη[∗][(][s][) := max]a0:∞_ [E][a][0:][∞] _t=0_ _η(t)rt|s0 = s_ _,_ (7)
h X i

where Ea0:∞ 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 a0:H with H ∈ N) and the optimal value function Vf[∗][H][+1](η)


-----

where f is an operator transforming the weighting distribution as follows:


_f_ (η) (t) :=
i


_γd_


_wj_ Φd(t) = Γ **w, Φ(t)**
_⟨_ _·_ _⟩_
_j=d_

X 


_d=0_


_γ0_ _γ0_ _γ0_ _..._ _γ0_
0 _γ1_ _γ1_ _..._ _γ1_
0 0 _γ2_ _..._ _γ2_
. .
.. ... ..
0 0 0 _..._ _γD_


_w0_
_w1_
_w2_
.
.
.
_wD_


Φ0(t)
Φ1(t)
Φ2(t)
.
.
.
ΦD(t)


_where_ Γ :=


**w :=**


**Φ(t) :=**


For the sake of simplicity, let ⟨1, η⟩ := _d=0_ _[w][d][ and]_ _f_ _[n](η)_ (t) := ⟨Γ[n]·w, Φ(t)⟩ for any n, t ∈ N.

**Proposition 2 For any state s0** _, the following identity holds:_ 
_∈S_ [P][D]

_[H]_

_Vη[∗][(][s][0][) = max]a0:H_ Ea0:H _⟨1, f_ _[t](η)⟩rt_ + Ea0,a1,..,aH _Vf[∗][H][+1](η)[(][s][H][+1][)]_ (8)

_t=0_

n h X i  [o]

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]
_Lf 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 vk+1 = _∥ΓΓ··vvkk∥_ [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 v0 = w, then Γ is diagonalizable, γ0 is it’s largest eigenvalue and the following holds:

Γ[n] **w** _Vf[∗][n](η)[(][s][)]_
lim _·_ _and_ lim
_n_ _n_ _n_
_→∞_ **[v][n][+1][ = lim]→∞** _k_ _n_ _→∞_ _k_ _n_

_≤_ _[∥][Γ][ ·][ v][k][∥]_ [= [][1][i][=0][]][i][∈][[0][,D][]] _≤_ _[∥][Γ][ ·][ v][k][∥]_ [=][ V][ ∗][(][s][)][ (9)]

Under these premises, the right hand term of the minimisation problem in Equation 8 can be approx-Q Q
imated 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 _V[˜]η,H[∗]_ [(][s][0][)][:]



_[H]_

_V˜η,H[∗]_ [(][s][0][) = max]a0:H Ea0:H _⟨1, f_ _[t](η)⟩rt_ + _∥Γ · vk∥_ Ea0,a1,..,aH _V_ _[∗](sH+1)_ (10)

_t=0_ _k_ _H_

n h X i  Y≤   [o]

A direct consequence of Equation 9 is that limH→∞ _V[˜]η,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**

1: Compute π[∗], V POLICY ITERATION and initialize v0 **_w_**
2: for t ∈ [1, H] do[∗] _←_ _←_

5:6:4:3: for InitialiseSolveCompute t ∈ [ πH, VtH( 0] vs+1) dot ←(s)arg maxΓ ← · vVt−[∗]1(sa) ·v[Q]t _k≤ cH(s, a[∥][Γ]) +[ ·][ v] E[k][∥]s′_ (s,a) **_Vt+1(s[′])_**

7: Compute Vt ←(s) **_vt_** _∥ c(s, π∥·t(s)) + Es′_ _∼P(s,πt(s))_ **_Vt+1(s[′])_**
_←∥_ _∥·_ _∼P_  

8: Return: (πt)t∈[0,H], π[∗]  


-----

3 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 criterion _L[¯] defined as :_


1

_T_ [E][π,p][0]


¯(π, c) := lim
_L_ _T_
_→∞_


_rt_
_t=0_

X


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 (Guo et al., 2019) 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. (Guo et al.,
2019) 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).

4 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?

4.1 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 _D) in discrete hard exploration maze environments. We_
_L_


-----

fix the discount factor values to γi = 0.99 − 1000i [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.

(a) U-maze (b) T-maze (c) Random maze

Figure 3: Hard exploration environments

**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 Ld).

In all experiments, the expectations were averaged across 25 runs of the algorithm using trajectories
of length 4000 initialised in all possible states (uniform p0) . 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


-----

Figure 4: Learned stationary policy (GSAC) performances as the depth parameter varies

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 _V[˜]η,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); Eysenbach et al.
(2019): by learning a policy that reaches interesting intermediate state, these methods are implicitly
learning an approximate solution of _V[˜]η,H_ .

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.

Figure 5: Learned H-close optimal control

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


**SAC** **GSAC**


**SAC** **GSAC**


Walker2d-v2


Hopper-v2


5000

4000

3000

2000

1000


4000

3000

2000

1000


0.0 0.5 1.0 1.5 2.0 2.5
Million steps


0.0 0.2 0.4 0.6 0.8 1.0
Million steps


**SAC** **GSAC**


**SAC** **GSAC**


HalfCheetah-v2


Ant-v2


12000

10000

8000

6000

4000

2000


7000

6000

5000

4000

3000

2000

1000


0.0 0.5 1.0 1.5 2.0 2.5 3.0

Million steps


0.0 0.5 1.0 1.5 2.0 2.5 3.0

Million steps


Figure 6: Training curves on continuous control benchmarks. Generalized Soft-Actor-Critic (GSAC) shows
better sample efficiency across all tasks


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


-----

REFERENCES

Jinane Abounadi, Dimitrib Bertsekas, and Vivek S Borkar. Learning algorithms for markov decision
processes with average cost. SIAM Journal on Control and Optimization, 40(3):681–698, 2001.

Joshua Achiam, Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational autoencoding
learning of options by reinforcement. In NIPS Deep Reinforcement Learning Symposium, 2017.

Jonathan Baxter and Peter L Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artifi_cial Intelligence Research, 15:319–350, 2001._

Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.
Unifying count-based exploration and intrinsic motivation. Advances in neural information pro_cessing systems, 29:1471–1479, 2016._

David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pp. 719–
726, 1962.

C´edric Colas, Pierre Fournier, Mohamed Chetouani, Olivier Sigaud, and Pierre-Yves Oudeyer. Curious: intrinsically motivated modular multi-goal reinforcement learning. In International con_ference on machine learning, pp. 1331–1340. PMLR, 2019._

Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a
new approach for hard-exploration problems. arXiv preprint arXiv:1901.10995, 2019.

Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then
explore. Nature, 590(7847):580–586, 2021.

Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. arXiv preprint arXiv:1906.05253, 2019.

Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actorcritic methods. In International Conference on Machine Learning, pp. 1587–1596. PMLR, 2018.

Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv
_preprint arXiv:1611.07507, 2016._

Yijie Guo, Jongwook Choi, Marcin Moczulski, Shengyu Feng, Samy Bengio, Mohammad Norouzi,
and Honglak Lee. Memory based trajectory-conditioned policies for learning from sparse rewards. arXiv preprint arXiv:1907.10247, 2019.

Zhaohan Daniel Guo and Emma Brunskill. Directed exploration for reinforcement learning. arXiv
_preprint arXiv:1906.07805, 2019._

Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy
maximum entropy deep reinforcement learning with a stochastic actor. In International confer_ence on machine learning, pp. 1861–1870. PMLR, 2018._

Ronald A Howard. Dynamic programming and markov processes. 1960.

Sham Kakade. Optimizing average reward using discounted rewards. In International Conference
_on Computational Learning Theory, pp. 605–615. Springer, 2001._

Pierre-Yves Oudeyer and Frederic Kaplan. How can we define intrinsic motivation? In the 8th
_International Conference on Epigenetic Robotics: Modeling Cognitive Development in Robotic_
_Systems. Lund University Cognitive Studies, Lund: LUCS, Brighton, 2008._

Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement.
In International conference on machine learning, pp. 5062–5071. PMLR, 2019.

Danil V Prokhorov and Donald C Wunsch. Adaptive critic designs. IEEE transactions on Neural
_Networks, 8(5):997–1007, 1997._

Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.


-----

Joshua Romoff, Peter Henderson, Ahmed Touati, Emma Brunskill, Joelle Pineau, and Yann Ollivier.
Separating value functions across time-scales. In International Conference on Machine Learning,
pp. 5468–5477. PMLR, 2019.

Anton Schwartz. A reinforcement learning method for maximizing undiscounted rewards. In Pro_ceedings of the tenth international conference on machine learning, volume 298, pp. 298–305,_
1993.

Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement
learning with deep predictive models. arXiv preprint arXiv:1507.00814, 2015.

Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181–
211, 1999.

Chen Tessler and Shie Mannor. Reward tweaking: Maximizing the total reward while planning for
short horizons. arXiv preprint arXiv:2002.03327, 2020.

Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control.
In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026–5033.
IEEE, 2012.

Arthur F Veinott. On finding optimal policies in discrete dynamic programming with no discounting.
_The Annals of Mathematical Statistics, 37(5):1284–1294, 1966._

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


-----

