Delayed Geometric Discounts: An alternative criterion for Reinforcement Learning
Authors: Firas Jarboui
Ahmed Akakzia
Venue: ICLR 2022 Submitted (2022)

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.

Under review as a conference paper at ICLR 2022
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 the- oretical background 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. De- pending on the problem, this limitation induces saaplle-iefficinneyy (as beed-backs are exponentially decayed) and requires additional curricula/exploraiion mecha- nisms (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 prob- lem 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 sim- ulated 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, 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 adver- sarial. 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. Con- sider for example the U-maze environment in Figure La where the reinforcement signal provides 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 lb
Naturally, higher discount factors are associated with optimal policies that also optimize the aver- age returns (Blackwell] [962)), which can solve in principle the described hard exploration problem. However, in practice, such discount values can be arbitrarily close to which entails severe com- putational instabilities. addition, and particularly continuous settings or when tasks span over extremely long episodes, iiscount-based RL approaches are sample-inefficient and are slow prop- agating interesting feed-backs to early states.
In this paper, we generalize the geometric discount to derive 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 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

---

Under review as a conference paper at ICLR 2022
policies using these novel criteria. Finally, we evaluate 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 proof of concept setup.
2. Our methods improve sample-efiiciency on continuous robotics tasks compared to Soft- Actor-Critic.
Figure Ic showcases how gon- 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 discount factor yy 0.99 and (c) non non-geometrically discounted RL.
2 REINFORCEMENT LEARNING WITH NON GEOMETRIC DISCOUNT
where S and A are either finite or compact subsets of respectively Rd and R (d, E IN A A ((S) is state transition kerne r S A R is a continuous reward function, Po E A(S) an initial state distribution and E (0, 1) is the discount factor. A policy æ is mapping indicating, at each time step I. the action a, to chosen at the current state st. The goal of geometrically discounted reinforcement learning algorithms is to optimize the discounted returns:
Consider an infinite horizon Markov Decision Process (MDP) M
L(T, r) = E.
re == r=tt
where Ey,po denotes the expectation over trajectories generated in M using the policy x and ini- tialised according Po-
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 stationary policies. Finally, Section 2.3 generalizes the optimal control 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 sequence of discount factors. For a given delay parameter D) IN, define the discount factors Ya (0, for any integer d E [0, D] and we consider the following loss function:
DC
LD( Err,p Σ
@n(()))
where 2n(1):
Σ END such Dn Rymt
II 7
This class of optimality criteria can be seen generalization of the classical geometric discount. In C(T, for any policy report the normalized distribution of the weights & 1 (t) ,..,,,9 9). Notice how the mode of the probability distribution is shifted towards the right we increased the delay, thus putting more weights on future time steps.
fact, we highlight that for = 0, 4 (t) = 7 which implics that Lo( (. r) and any reward function In Figure
(i.e. y(() = Σ, ( over time as we vary the parameter D E (o....,
(t)
(S) denotes the of probability measures S
2

---

Under review as a conference paper at ICLR 2022
Time weights the criterion Lp(m, c)
0.010
D
normalised coefficents
0.008
D+2
D
0.006
D-5
D=7
0.004
D
0.002
0.000
t
Figure 2: The normalized coefficients 4D over time for different values of the delay parameter D
Intuitively, the proposed criterion (Lp) describes the goal of an agent that discards short term gains in favor of long term discounted returns. In the following, consider yet more diverse problem formulation by using a linear combination of the delayed losses. Let Log be the following objective function defined as:
(T, = EIT.PO Σ n(trra such that ntt) Σ (a(t
d=0
where the depth D IN and the coefficients wa R. for any d [0, D) are known.
In general, the optimal control in the sense of C.j is not stationary. However, learning solutions that admit compact representations crucial for obvious computational reasons. In the following propose to learn either the optimal stationary solution, to approximate the optimal control with non-stationary policy over finite horizon followed by stationary one.
2.2 OPTIMAL STATIONARY POLICIES
this section, we propose learn stationary solution using a policy-iteration like algorithmic scheme. As in the classical setting, the goal is to learn control x² that maximizes the state-action value function :
D ( a) = Σ d=0
Wa where Q7(8,0) = E Σ a0 = =saa
(3)
This is done by iteratively evaluating Q and then updating the policy to maximize the learned value function. Due to the linearity illustrated Equation the policy evaluation step is reduced the estimation of Q" 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?:
Proposition 1 For any discount parameters (na) the value functions Q3 is the unique fixed point of the following "ID contoratat::o::
IT. (p)(()s)))) a) E Eg-p(ra) r(s, a) + Σ (aQT)s' tYD (g(ss,aa) (4)
a'mx(o")
d=0
a' a'm)t(s')
(8)
The value QT of policy x with respect to the delayed criterion Lp is the state-action value function of the same policy using augmented policy dependent reward r% w.r.t. the yp discouund returns.
3

---

We use Equations and 6 to construct Algorithm [ 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 a. This is discussed in Appendix A.. Unfortunately, unlike the geometrically discounted setting, the policy improvement theorem no longer guaranteed in the sense of L, This means that depending on the initialization parameters, Algorithm [ can either converge to the optimal stationary control or Under review as a conference paper at ICLR 2022
Intuitively, the instantaneous worth of an action (r)) is the of the environments' myopic returns (r(s, a)) and the long term evaluations (with lower delay parameters (Q))
This has the beneficial side-effect of enhancing sample efficiency it helps the agent to rapidly pack-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 typ- ically used to learn policies. This is discussed in details in Section
Similarly standard value based RL algorithms, given data set of trajectories D as, a,,a,,), s)), the value function Q2 can be approximated with parametric approximator Qo by optimising J (0):
O²( E s' a a'~
( (r(s,a)
Σ La (())
(5)
As for the policy update step, inspired from the Soft-Actor-Critic (SAC) algorithm, we propose to optimize entropy regularized soft Q-value using the following loss where is parameter:
D
(6) = -EEND aroe
Σ d=
w (a (og((T(((ss))
(6)
stuck in a loop of sub-optimal policies. This is discussed detail in Section 4.1
Algorithm 1 Generalized Soft Actor Critic
Input: initial parameters (0u) o, learning rates (Au)d or d pollyak parameter
2: initialise target network 0₂ Og and initialise replay buffer D +-
3: for each iteration do
4: for each environment step do
5: Gg Tá (St). St+1 P(ss, at), D < D- (1
6: for d E [0, D) do
7: for each Qa gradient step do
8: update parameter 0a +- 0a >a 18 (0a) and update target 0. T0a (1 7)
9:
for each policy update do
10: update policy < Φ - A (o)
11:
Return: Th, (Qū, 12
2.3
APPROXIMATE OPTIMAL CONTROL
In the general case, the optimal control not necessarily stationary. Consider the problem of learn- ing the optimal action profile ai.00 which yields the following optimal value function:
D Σ m()rrel00 =s]
V (s)
max Enoic da
where Eng.. the expectation over trajectories generated using the designated action profile. In this section propose 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 0g. with H IN) and the optimal value function Visti
4

---

Under review as a conference paper at ICLR 2022
where f is operator transforming the weighting distribution as follows:
[(m) (t)=
Σ
wiy pu(() (T- w, 2())
j=d
70 700
70
100
Po(t)
0 71 71 ...
71
w1
(t)
where ;=
0
0 72
W2
D(t)
P2(()
0
7D_
(()
For the sake of simplicity, let (1,1) Ed=o wa and (f (1) (t) (w" Φ()) for any n, E IN.
Proposition 2 For any state E S, the following identity holds:
(50) max ag:
Eaa.H
Σ (1, (1)))r) + Eao.a Vi (sm+1)] 1=0
(8)
As a consequence, the optimal policy in the sense of L, to execute the minimising arguments Gi:H of Equation and the execute the optimal policy in the sense Lyn+r(n) Unfortunately, solving ( not easier than the original problem.
However, under mild assumptions, for H large enough, this criterion can be approximated with simpler one. order to derive this approximation, recall that the power iteration algorithm described by the recurrence V eigenvalue of the matrix whenever that is diagonalizable. In particular, if < 7D < ... < %
Pwy. Tv&ll converges to the unit eigenvector corresponding the largest
and w, then I is diagonalizable, " is it's largest eigenvalue and the following holds:
(s)
W
lim Vn+1 R-020
lim #20
[1i=0]xeto.D] and lim
Ik-5 vxll V*(s) (9)
vEl
Under these premises, the right hand term of the minimisation problem in Equation Iinaationnaan Cann be approx- imated with the optimal value function in the sense the classical RL criterion (which optimal policy be computed using any standard reinforcement learning algorithm in the literature).
Formally, propose approximate Equation with proxy optimal value function V.
H
V-- (50) = max Faa.u ag.1
Σ 11, (()) 1=0
+ III || vall) F Eao..a [V* (10) ASH
A direct consequence of Equation is that lim V ( (s) for any state E S. In addition, for a given horizon H, the optimal decisions in the sense of the proxy problem formulation execute for the first H steps the minimising arguments ag of Equation TO (they can be computed using dynamic programming) and then execute the optimal policy in the sense of the do-discounted RL (which can be computed using any standard RL algorithm).
Algorithm 2 H-close optimal control
1: Compute x² V <- POLICY ITERATION and initialize vn <- w
2: for t [1, !/| do
3: Compute 8; 1- 01-1
4: Initialise VH+1(s) + (s) HISH [| vvll
5: for E 0} do
6: Solve Te(3) + arg max, || c(s, a) + EgrP(()))) V442('))
7: Compute (s(s) + |elll c(s, (s)) + (x(p((s)))))) [++1(s))]
8: Return: (T=)e{o.HH) "
5

---

Under review as a conference paper at ICLR 2022
3
RELATED WORK
Bridging the gap between discounted and average rewards criteria. is well known that defin- ing optimality with respect to the cumulative discounted reward criterion induces built-in bias against policies with longer mixing times. fact, due to the exponential decay future returns, the contribution of the behaviour from the T observation up to infinity is scaled down by factor of the order of y² In the literature, the standard approach to avoid this downfall is to define optimality with respect to the average reward criterion L defined
[( lim
T-00
This setting well as dynamic programming algorithms for finding the optimal average return policies have been long studied in the literature (Howard 1960; Veinoti 1966; Blackwell, 1962. Puterman 2014). Several value based approaches (Schwartz, 1993 [ Abounadi al. 2001 Wei al,, 2020) as well as policy based ones (Kakade [001] Baxter & Bartlett 2001) have been investigated to solve this problem. These approaches are limited 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 Yovit < 1 such that for any discount 7 E (Yevis 1) the optimal policy in the sense of the 7-discounted criterion also optimises the average returns Blackwell] (962). Unfortunately, this critical value can be arbitrarily close to 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 TTssleer& & 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 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 af.) 2016, Colas et al. 2019). Alternatively, prediction-base exploration define the intrinsic rewards with respect the agents' familiarity with their environments by estimating dy- namics 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. (2199) 2021) first return to interesting states using either a deterministic simulator goal-conditione' policy and start exploration from there. (Guo 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 condi- tions 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.rt. the optimality criterion Lp) in discrete hard exploration maze environments. We

---

Under review as a conference paper at ICLR 2022
fix the discount factor values to % 0.99 1000 throughout the experiments. This guarantees that is diagonalizable and that its largest eigenvalue is " = 0.99. We evaluate the performance of both vary the depth parameter and as increase the non stationarity horizon.
Algorithms D and
In Figure we reported the shapes of the mazes as well as the used reinforcement signal in each of them. We used 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 hard exploration problems the agent might learn sub-optimal behaviour because of the deceiving signal or because of the penalty.
80
R=.1
100
Rm-1
70
R=1
R-0.9
80
60
40
50
40
20
30
20
20
10
-20
0
20
40
100
20
80
100
20
(a) U-maze
(h) T-maze
(c) Random maze
Figure 3: Hard exploration environments
Stationary solutions: We start by evaluating the performances of the learned policies using Gen- eralised Soft Actor Critic (GSAC) (Algorithm T]. As discussed earlier, unlike the geometrically discounted setting, the policy update is guaranteed to improve the performances. For this rea- son, depending on the initialisation, the algorithm can either converge to the optimal stationary policy, or get stuck in sequence of sub-optimal policies.
In Figure 4 we reported the performances of GSAC as we varied the depth hyper-parametee 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 & weighted loss (as computed in Ca).
In all experiments, the expectations were averaged across 25 runs of the algorithm using trajectories of length 4000 initialised in all possible states (uniform Po) A common observation is that for a depth D higher than the algorithm was unstable and we couldn't learn a good stationary policy in a reliable way. However, the learned stationary policies with even relatively shallow depth parameter yielded reliable policies that not only maximise the dp weighted rewards but also improved the average returns. Notice how the baseline (D 0, i.c. the geometrically discounted case) always under-pent mnder-performs when compared to the learned policies for depth parameter around 3.
We also observe that the algorithm is sensitive to the used initialisation. Using the optimal pol- icy the sens of the geometrically discounted objective (red curves) helped stabilise the learning procedure in most cases: this is particularly true in the random initialisation of the policy yielded bad performances even with a low depth parameter. This heurestic guaranteed produce better performances in all cases, notice how for D 7 in the T-maze, a random initialisation outperformed this heuristic consistently.
environment where a random
this section we investigate the performances the policies leamned using Algorithm 2 as we vary the non stationarity horizon H/ for three depth parameters D E (5, 10, 15) (respectively the red, blue and green curves). As the last experiment, we reported the expected returns 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
Optimal Control Approximation:

---

Under review as a conference paper at ICLR 2022
1.
0.3
15
02-
02
12
PP- or with 101300 CESEEE
Figure 4: Learned stationary policy (GSAC) performances the depth parameter varies
horizon H = O. We also reported the performances of the best stationary policy learned using GSAC for depth parameter = 5.
The first notable observation is that increasing the hyper-parameter H does indeed improve perfor- mances. In addition, we notice that the maximum possible improvement is reached using a finite horizon (i.e. the maximising argument of both Vy, and Vi are the same). Intuitively, the non stationary steps enable the agent to get to 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 algorithm&Fcoofet 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 Vn
In the case of D 5, the obtained performances using Algorithm 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 @ weighted rewards. More interestingly, increasing the depth can be beneficial empirically that for higher depth parameters, the non-stationarity horizon required to achieve the best possible performances decreases.
observe
maze
Random mazs
140
1.0
1.00
2w10
090
2.91
(C-5)
8.00
040
6.43
0.37
097
0.27
000
023
0:10
092
E41
Averics novers
weighted
093
800
250
100
108
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, consider different environments within the MUJOCO physics engine (Todorov 2012)) Walker2d, Hopper, HalfCheetah, Ant and Humanoid. As results the tabular settings showed that there exists threshold beyond which increasing the value of the delay D hurts the performance, fix D = 1, where only two discount factors %o and "n are used. We compare our proposed methods to the classic SAC algorithm investigate the implications of using both critics Qa, and Qa.-
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
8

---

Under review as a conference paper at ICLR 2022
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 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, Qo, takes into consideration the estimate of the actions by Qa. and thus there is less uncertainty about their quality.
SAC
GSAC
SAC
GSAC
Walker2d-v2
Hopper-v2
5000
4000
Average Reward
4000
Average Reward
3000
3000
2000
2000
1000
1000
0.0
10
0.2
Million steps
Million steps
SAC
GSAC
GSAC
HalfCheetah-v2
Ant-v2
12000
7000
Average Reward
10000
Average Reward
6000
4000
6000
2000
4000
2000
2000
0.5
2.0
055
1.0
Million steps
Million steps
Figure Training curves on continuous control benchmarks. Generalized Soft-Actor-Critic (GSAC) shows
better sample efficiency across all tasks
CONCLUSION
Designing human- autonomous agents requires (among other things) the ability to discard short term returns in favor of long term outcomes. Unfortunately, existing formulations of the reinforce- ment learning problem stand on the premise of either discounted or average returns: both providing 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 preferrfeeeece models. We analyse the new formulation to construct I) the Bellman optimality criterion of stationary solution and 2) a feasible iterative scheme to ap- proximate the optimal control. The derived algorithms successfully solved tabular hard exploration problems and out nut-performed the sample efficiency of SAC in various continuous control problems; thus closing the gap between what conceivable and what is numerically feasible.
BROADER IMPACT STATEMENT
Reinforcement learning provides framework solve complex tasks and learn sophisticated be- haviors in simulated environments. However, its incapacity to deal with very sparse, deceptive and adversarial rewards, well its sample-inefficiency, prevent it from being widely applied in real-world scenarios. We believe investigating the classic optimality criteria crucial for the de- ployment 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 releasing our code soon in order to allow the wider community extend our work in the future.
9

---

Under review as a conference paper at ICLR 2022
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 neural information pro- cessing systems, 29:147111111 1-479, 2016.
David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pp. 719- 726, 1962.
Cédric Colas, Pierre Fournier, Mohamed Chetouani. Olivier Sigaud, and Pierre-Yves Oudeyer. Cu- rious: 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 1rXiv:1901.10999 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: Bridg- ing planning and reinforcement learning. arXiv preprint arXiv:1906.00 05253, 2019.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596. PMLR, 2018.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv 2016.
preprint
Yijie Guo, Jongwook Choi, Marcin Moczulski, Shengyu Feng, Samy Bengio, Mohammad Norouzi, and Honglak Lee. Memory based dnjectory-conditioone policies for learning from sparse wards. arXiv preprint arXiv: 10247, 2019.
Zhaohan Daniel Guo and Emma Brunskill. Directed exploration for reinforcement learning. arXiv preprint 1rXiv:1906.078880 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with 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. International Conference on Computational Learning Theory, pp. 605-615. Springer, 2001.
Pierre-Y Yves Oudeyer and Frederic Kaplan. How can 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 machine learning, pp. 5062-5071. PMLR, 2019.
Danil V Prokhorov and Donald C Wunsch. Adaptive critic designs. IEEE transactions Neural Nenworks, 8(5):997-1007, 1997.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
10

---

Under review as a conference paper at ICLR 2022
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-477.. 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 Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv: 157.:0157..00844 2015.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work 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.00 0tth::0002.03322,, 2020.
Emanuel Todorov, Tom Frez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEF/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 Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference on machine learning, pp. 10170-1011 PMLR, 2020.


Reviews:
[{"review_id": "sd_LEVr-u6X", "reviewer": "Reviewer_tzWw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem considered in the paper---that of generalizing the optimality criterion in RL---strikes me as potentially interesting  and with potential to broaden the applicability of RL to other domains. It also follows recent work in off-policy TD-learning---see, for example, the references [a, b] below, which also consider time-dependent discounting although, it seems to me, in a more restricted setting than that considered in this paper.\n\nThis said, there are several aspects of the paper that are not very clear to me and/or which would benefit from added discussion. Specifically:\n\n- The considered discounts $\\Phi_D$ are introduced with no motivation whatsoever. Where does this particular definition come from?\nWithout any introduction, this definition seems completely arbitrary.\n\n- Still on the point above, the definition in (1) is far from clear. Can you provide some intuition on what it represents? Perhaps defining $\\Phi_D$ recursively (as done above) may be more easily parsed by the reader, and makes the subsequent derivations much more plausible upon a first read.\n\n- Under what conditions is the loss $\\mathcal{L}_D(\\pi,r)$ in (1) well-defined (i.e., is the series convergent)?\n\n- I don't understand what is depicted in Fig. 2. What is the normalized coefficients? Normalized over what? Time (the text in page 2 seems to suggest it)?\n\n- In the related work section, some discussion of the aforementioned works would certainly be of interest (please see refs. [a, b] below and other references therein).\n\n- As an overall comment on the results, it is somewhat strange that SAC and GSAC are compared in terms of \"average reward\", when neither of the two is optimizing the average reward. Also, although the paper states that GSAC shows better sample efficiency across all tasks, if we take into consideration the error margins, the difference seems to be significant only for the walker and half-cheetah. Or am I missing something? Also, it would be of interest if some discussion could be made regarding any qualitative differences between the corresponding optimal policies, in light of the motivation for considering the framework discussed in the paper.\n\n_Minor aspects:_\n\n- In the beginning of Section 4 the paper says \"we evaluate the performance of the proposed algorithm.\" But, actually, the paper proposes two algorithms...\n\n- Still in the experiments, in the \"Optimal Control Approximation\", the text refers to the \"red, blue and green curves\", but does not refer to a particular figure (which I guess is Fig. 5).\n\n\n- In the appendix, the reward seems to be denoted as $c$, which suggests a cost. Although there is no technical problem in that, it adds somewhat of a \"cognitive dissonance\" and may be worth making consistent.\n\n_Refs._\n\n[a] H. van Hasselt and A. Mahmood and R. Sutton. Off-policy TD$(\\lambda)$ with a true online equivalence. In _Proc. 30th Conf. Uncertainty in Artificial Intelligence_, pp. 330-339, 2014.\n\n[b] H. Yu and A. Mahmood and R. Sutton. On generalized Bellman equations and temporal-difference learning. _J. Machine Learning Res._ 19:1-49, 2018", "summary_of_the_paper": "The paper proposes an optimality criterion for RL that is generalizes the standard exponential discount commonly used in a large volume of RL research. In particular, the paper proposes substituting the standard discount term $\\gamma^t$ by a generalized discount term $\\Phi_D(t)$ built from a set of discounts $\\gamma_0,\\ldots,\\gamma_D$. The discount terms $\\Phi_D$ can be defined recursively as \n\n- $\\Phi_0(t)=\\gamma_0^t$ (corresponding to the standard exponential discounting);\n- $\\Phi_D(t)=\\sum_{k=0}^t\\gamma_D^k\\Phi_{D-1}(t-k)$\n\nThe consideration of non-uniform discounting implies that the resulting optimal policies may, in general, be non-stationary. Nevertheless, the paper introduces an equivalent to the $Q$-functions in the standard RL formulation and shows that these functions can be computed using standard dynamic programming. Letting\n\n$Q_d^\\pi(s,a)=E\\left[\\sum_{t=0}^\\infty\\Phi_d(t)r_t\\mid s_0=s,a_0=a\\right]$,\n\nit follows that $Q_0^\\pi$ corresponds to the standard $Q^\\pi$ with discount factor $\\gamma_0$, and each $Q_d^\\pi$ can be computed from $Q_{d-1}^\\pi$ using a dynamic programming operator $T_\\pi^d$ that has $Q_d^\\pi$ as its unique fixed point. These functions can also be computed using existing RL algorithms as part of a generalized policy iteration cycle that---upon convergence---may yield an \"optimal stationary policy\" (convergence is not guaranteed, though).\n\nThe paper also proposes an approximate policy that breaks down the value function for the problem into two terms---one that accounts for the rewards in the first $H$ steps and the other for the remaining steps. Under mild conditions on the discounts $\\gamma_0,\\ldots,\\gamma_D$, the latter term can be approximated by the standard optimal value function (with standard exponential discounting) for large $H$, allowing for the computation of an approximate (non-stationary) policy.", "summary_of_the_review": "Although the premise of the paper is interesting, and the proposed approach is novel, to the extent of my knowledge. However, the proposed framework is introduced in a rather arbitrary manner; it is not clear how it relates with some existing work; the results are hard to interpret.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_Ucn1dzoJAV", "reviewer": "Reviewer_hhP8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'm recommending rejection at this time, due to the following concerns:\n\n1. The arguments made about the algorithm aren't convincing. e.g., there's some explanation for why the algorithm would have improved sample efficiency, but the empirical evaluation cited for the explanation doesn't readily provide evidence that the explanation is correct.\n\n2. Many key implementation details are missing. The current paper (and supplement), as presented, are missing some key pieces of information to a point where it's not clear what was actually done. e.g., in the environments of Figure 3, the later text implies that they were tabular, but what were the sizes of their state spaces? Given discrete time, such information is key in setting expectations under the specified discount factor. Where are the error bars in Figure 4? How many runs were performed in Figure 6, and what do the shaded regions represent?\n\n3. The bulk of the results in Figure 6 don't appear statistically significant. The claim that GSAC \"shows better sample efficiency across all tasks\" doesn't seem supported here, and consequently puts into question the explanation for why GSAC should have better sample efficiency.\n\nAlong the lines of the above concerns, I have the following questions:\n\n1. What is the motivation behind considering Lη in the first place? There was discussion about delayed discounting, and how Equation 1 provided temporal weightings which discarded short term information and emphasized a delayed geometric weighting. With seemingly no context, a linear combination was then considered and became the focus of the work.\n\n2. For the tabular results, what was the rationale for running SAC/GSAC in these environments, as opposed to a simpler algorithm to demonstrate the proposed objective? Along this line, as opposed to the stochastic samples averaged over several runs in these environments, could the solutions not be computed directly?\n\n3. Can the authors comment on why the proposed method is unstable at higher depths in the tabular results? Is it some fundamental limitation of the objective, or does there exist some configuration where it learns something sensible (e.g., lower learning rate and more time)?\n\n4. Can the authors clarify the following: \"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.\" Section 4.2 doesn't really discuss it, but claims the empirical evaluation demonstrates improved sample efficiency, and restates that this explanation is the case. What aspect of the empirical evaluation provides evidence that this is the reason behind the improvements?\n\n5. Regarding Figure 7 in the supplement, is this \"critical frontier\" something to be expected of the objective? That is, will there be such a frontier in every environment, or is it just an observation in a single environment? Can the authors further comment on why the area above the frontier is dramatically inconsistent? I think this is another figure which would have greatly benefitted from computing an exact (or near exact) solution in a small tabular environment, and not be generated from stochastic samples under an algorithm with many moving parts.", "summary_of_the_paper": "This paper generalizes the discounted objective in RL with \"delayed\" discounted objectives. They analyze the proposed objective and how it may be used to approximate optimal control, and evaluate the proposed method empirically.", "summary_of_the_review": "In light of the above concerns pertaining to the proposed method's motivation, unclear arguments, and empirical methodology, I am recommending rejection at this time. I'm willing to raise my score should my questions and concerns (and potential misunderstandings) be adequately addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "MNmApYudw72", "reviewer": "Reviewer_1aQD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Evaluation.** I find the motivation of this paper to be compelling. Geometric discounting is of course standard in reinforcement learning, but there might be good reason to explore alternative kinds of temporal preferences. In this sense, I am sympathetic with the goals of the paper. I also find that the questions studied surrounding the new criterion are sensible: Is a contraction still guaranteed? How do RL algorithms handle this new kind of discounting?\n\nI did find that a number of concepts were unclear, including the primary contribution of the work: Equation 1. I provide more details on what I found unclear below under \"Primary Questions\". Given the central role of Equation 1, I believe the paper should spend more time on making this concept _extremely_ clear up front. I did find Figure 1 quite helpful for this purpose. However, in the conclusion, the paper states \" we propose a family of delayed discounted objective functions that captures a wide range of non-monotonic time-preference models.\" By the time I finished the paper I did not have a clean picture of what kinds of non-mononotic time-preferences can be captured by the new criterion. I believe adding further detail commenting on these other kinds of time-preferences would benefit the paper.\n\nI also found the experimental results to be lacking in strength in at least one respect: Results in both Figure 4 and 5 are estimates of expected returns (I believe -- the y-axis label just says \"Expected Returns\") based on 25 samples. It is critical to include some measure of variance in the reported figures (ideally 95% confidence intervals). If the variance is too high so as to prevent us from drawing conclusions, I suggest removing the requirement that the initial state is sampled uniformly at random from all states, and instead choose a small handful of representative start states. This will considerably lower the variance.\n\nThe two new algorithms seem interesting, and I believe aspects of the new discounted criterion will be of interest to the community. I believe the presentation of this idea could be made more clean.\n\n**Primary Questions**\n\n- [PQ.1] I am having a hard time making sense of Equation 1, and specifically $\\Phi_D(t)$. Since this is so central, I want to make sure I am understanding things correctly. First, what is $N$ in the superscript of the $\\prod$ term? Is this a typo, and should be $D$? Second, the subscript of the sum seems odd: We require $(\\sum_{d} a_d) = 1$, but $a_d$ takes values in $\\mathbb{N}$ up to D. Consequently, for many values of $t$ that are not expressible as the sum of consecutive natural numbers, it is unclear what happens in Equation 1. For instance, let $t = 2$ and $D = 3$. Now, by my reading, the subscript of the sum enumerates over natural numbers including 0, 1, 2, and 3. However there is no sum of consecutive numbers such that their sum adds to 2. Do we not require that the $a_d$'s used be consecutive? Then there is ambiguity (between say, when $t=6$, the case where $a_d \\in \\\\{2, 4\\\\}$ and $a_d \\in \\\\{1, 5\\\\}$). If all this is trying to articulate is that we only use the first $t$ natural numbers, then the subscript of the sum should just read $\\sum_{a_d=0}^{t-1}$\n\n- [PQ.2] Two closely related papers come to mind that were not discussed. I believe the results are quite different, though the perspectives taken are similar. The first is \"Rethinking the discount factor in reinforcement learning: A decision theoretic approach\" by Pitis (AAAI 2019). This paper looks at what criteria are needed on the discount factor in order for the objectives of an MDP to cohere with the constraints of the axioms of classical decision theory. In fact, one of Pitis' results motivates the use of discounts that might place _more_ utility on future events, rather than the present. I believe the work by Pitis might give further motivation to the use of the proposed delayed discount offered here. Second, \"Hyperbolic discounting and learning over multiple horizons\" by Fedus et al. (RLDM/arxiv 2019) explore hyperbolic discounting. I believe some discussion of the differences between delayed discounting and hyperbolic might be warranted.\n\n\n**Minor Questions**\n- [MQ.1] Is gamma part of the _objective_, or an algorithmic tool? That is, are we defining the task we want the agent to solve, or, are we viewing choice of gammas an algorithmic solution to solve the true task? These are slightly different perspectives and I think it would be helpful to address which of these is intended early on. For instance, the paper states that the delayed criterion can benefit sample efficiency---this could read as though the true objective is unchanged, and that the agent is simply using a different discounting scheme as an algorithmic trick. In other words, I take this paper to be about rethinking discounting for RL, rather than on exploration. I found the related work section on exploration strategies out of theme for this reason.\n- [MQ.2] \"discount-based RL approaches are sample-inefficient and are slow at propagating interesting feed-backs to early states.\" I'm not sure I quite get this. As opposed to non-discount based RL?\n- [MQ.3] Why is $Q^\\pi$ also indexed by $\\eta$ in Equation 3? I don't see $\\eta$ appearing (is this the learning rate?) I see $\\eta$ is again used to index $J^\\pi$ in Equation 6 but $\\eta$ does not appear anywhere on the right hand side of the equation. Are these only being used to indicate that we are considering the weighted objective from Equation 2? If so, there might be a better notation for this (or, I recommend calling specific attention to the meaning in the text).\n\n**Writing Suggestions**\n- You probably do not need the outline paragraph just before 2.1, and could remove it if space is tight.\n- The plots are pixelated. I suggest generating pdf versions (doable in matplotlib with plt.savefig(\"*.pdf\"))\n- The font size in the axes and the legend of Figure 1 are far too small.\n- Top of page 4: \"in details\" --> \"in detail\"\n- \"expectation over trajectories\" of infinite length?\n- \"non stationarity horizon.\" --> \"non-stationarity horizon.\"\n- Typo: \"a depth D higher than 6 7 the algorithm\" --> This should either be just \"7\", or a hyphen is missing.\n- \"sum of the environments'\" --> \"sum of the environment's\"\n- I suggest not using $\\mathcal{D}$ to represent a dataset of trajectories given the prevelance of $d$ and $D$ throughout the paper (with a different meaning).\n- In Equation 5 and 6, it is stated that $s,a,s' \\sim \\mathcal{D}$ or $s \\sim \\mathcal{D}$ -- is it assumed there is some underlying probability distribution over the dataset that is being sampled from?\n- \"double Q-network trick\" --> Consider citing the Double Q paper at this point.\n- Algorithm 1, inputs, \"pollyak\" --> \"Polyak\"\n- After Proposition 2: \"and the execute the optimal policy\" --> \"and then execute the optimal policy\"\n- \"whenever that it is diagonalizable\" --> \"whenever it is diagonalizable\"\n- \"is it’s largest eigenvalue\" --> \"is its largest eigenvalue\"\n- Why are the subscript of the two expectations in Equation 10 different?\n- What is $c(s,a)$ in Algorithm 2? I did not see it defined.\n- \"How does the different parameters\" --> \"How do the different parameters\"\n- \"all possible states (uniform $p_0$) .\" --> \"all possible states (uniform $p_0$).\"\n- A \\citet should be turned into a \\cite: \"exploration RL algorithmsEcoffet et al.\" --> ard exploration RL algorithms\\cite{ecoffet...}\"\"\n- ", "summary_of_the_paper": "**Summary.**\nThis paper proposes a generalization to the typical geometric discounting scheme in reinforcement learning. In particular, a new _delayed_ discount criterion is proposed (Equation 1) that captures traditional geometric discounting when $D=0$, but also allows for other kinds of temporal preferences. Figure 2 provides a clean visual illustrating the different kinds of discounting afforded for different settings of $D$. Following this, several natural questions emerge: What happens to the $\\gamma$-contraction in repeated application of the Bellman Operator? Proposition 1 addresses this question by stating that a $\\gamma_D$-contraction is still guaranteed. How might typical reinforcement learning algorithms handle this new discounting scheme? The paper addresses this question by introducing two new algorithms. The first (Algorithm 1) is a generalization of Soft Actor Critic, while the second (Algorithm 2) is a policy-based algorithm that approximates the finite horizon problem. The first set of experiments focus on three maze problems. Estimates of the expected returns of learned stationary policies are reported for Algorithm 1 under four conditions as the depth $D$ is changed from 0 up to 8. The main finding is that as $D$, returns do tend to increase up to a certain point, at which point it drops (around when $D = 6$ or $7$). Further experiments inspect the performance of Algorithm 2 in a similar way (Figure 5), and contrast the performance of Algorithm 1 with typical SAC on continuous control games like Ant-v2. On the chosen four games (Figure 6), the average reward of GSAC improves over SAC slightly, though the variance is arguably slightly higher.", "summary_of_the_review": "This paper is conceptually interesting but could be refined in its execution. A few small aspects of it are unclear (including, to me, the main definition: Equation 1). I believe the paper will be strengthened with a much more clear exposition of the central idea, and improved rigor in presentation of the empirical results. For these reasons I lean slightly toward rejection at the moment, but am willing to increase my score if the paper can be changed in these two ways. For clarity, they are: (1) Answer PQ.1 and provide further exposition in the paper to make the proposed criterion more clear, and (2) Include a variance measure in the first two sets of experiments, and hedge the statements made about the results in light of the observed variance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6FX5CPu_9x_", "reviewer": "Reviewer_7SFq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In reinforcement learning, it is very common to use variants of a discounting parameter to emphasize the importance of immediate rewards as opposed to rewards received in the future. This is both a) intuitively plausible and b) beneficial for theory (convergence guarantees for learning and planning usually hinge on the Bellman equation being a gamma-contraction). But, as the paper argues correctly, geometric discounting results in weights that get exponentially smaller as we increase the horizon. This ultimately results in policies that are myopic in nature regardless of how large the discount factor is. While the average reward could be thought of as the limiting case of gamma-discounted returns, in principle using gamma values extremely close to 1 cannot address the myopic-policy problem since even small amount of noise in the learning process can compensate for negligible improvements of the less myopic policies.\n\nThe solution that this paper advocates for is to use generalized geometric discounting scheme with two hyper-parameters (\\gamma, D). Intuitively, the role of the D parameter could be thought of as sacrificing the short term reward for ~O(D) steps before the geometric discounting kicks in.  As a micro point, I really struggled with the notation used to introduce the idea. There is Q_{\\mu} that is only used once, then there is Q_{d} and Q_{D}. In equation 1, there is regular N and then there is \\mathbb{N}. In general I don't think the notation used here is the most careful one, but that's a minor issue that will hopefully be fixed.\n\nGoing to the core of the idea, while I think this is a step towards learning less myopic policies, I think the original problem with the geometric discounts is still present in the generalization advocated here. In particular, the introduction of the D parameter is merely going to delay when the exponential nature of discounting kicks in, and does a marginal step to really eradicate the problem. The benefit of adding D is also, in my opinion, overshadowed by the fact that the discounting is now non-monotonic. That is to say, depending upon the setting of D, we may put less weight behind rewards that are received earlier in the trajectory relative to some of the rewards received later on. This means in principle, actions with disastrous short-term effects may be preferred so long as they lead into better long term ramifications. This is an undesirable property whose presence is not justified here. A second weakness is that the optimal policy is now non-stationary. Intuitively, I think this is because it actually matters how far in the trajectory we reach a certain state. If we go back to a state after a while, we may have to take a different action because the follow up states may now have larger or smaller weight. Thus, it is debatable if the marginal improvement in delaying the exponential decay actually justifies now having to deal with these technical issues.\n\nIn equation (4), it is stated that Q_{D} is the fixed-point of a Bellman like equation. Notice that in this equation, the reward itself depends upon the Q_d of all smaller ds. So while this may be a contraction all given Q_{d}s, it is not clear to me how to design a Policy Evaluation-like algorithm to solve for Q_{D}. While I conjecture that such an algorithm exists, the paper jumps into the function approximation case before a thorough treatment of Policy Iteration in the tabular case. Showing there exists a sound and convergent Policy Iteration algorithm in the tabular case is really the minimum we should desire to have. Notice that my main concern is due to the fact that solving for the fixed-point of Q_{D} requires knowing the fixed point for all previous ds. This is a) computationally expensive, and b) non-trivial in a convergence sense. In particular, I am not sure if the obvious algorithm of solving for lower level ds is actually convergent absence an analysis.\n\nWhile I appreciate experiments on Mujoco, I don't think these Mujoco domains are hard in terms of exploration. If the motivation of the paper is to do better on hard-to-explore problems, experiments need to support the thesis of the paper, and to demonstrate that the new algorithm is capable of doing well on actual hard-to-explore problems. Notice also that the value of D used is pretty small here (D=1), which really defeats the whole purpose of using the alternative discounting scheme.\n\nI also think two important comparisons are missing here. One is the idea of logarithmic discounting [1], which starts with the exact same motivation but proposes to do Q updates in the logarithmic space. And the second one is the idea of hyperbolic discounting [2], which is also known to be cognitively more plausible. It is surprising that these two works are not even acknowledged, let alone compared with.\n\nI finally like to highlight that the example provided in Figure 1 accentuates not just the weakness of geometric discounting but the weakness of any form of discounting. For any discounting scheme it is possible to construct an MDP for which learning in presence of discounting can yield suboptimal results. In that sense, only the average reward setting can truly hedge against this issue by getting rid of discounting altogether. So it would be nice to know what I am missing here.\n\n[1] van Seijen and friends \"Using a logarithmic mapping to enable lower discount factors in reinforcement learning\"\n[2] Fedus and friends \"Hyperbolic discounting and learning over multiple horizons\"  ", "summary_of_the_paper": "This paper proposes a discounting framework that generalizes the standard geometrically discounted reinforcement learning. The paper shows that the generalization still lends itself to deriving Bellman-like equations, and that it can provide empirical benefits on Mujoco problems.", "summary_of_the_review": "In light of the issues I outlined above, especially in terms of the absence of theory for the tabular case, lack of experiments on truly hard-to-explore domains, and missing existing work, I am voting for rejection. That said, I certainly acknowledge issues that arise when using geometric discounting and I encourage authors to further explore this idea. A better discounting scheme may in theory have a high impact, but the current manuscript is not demonstrating to me (at least yet) that this is a good alternative.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers were insufficiently enthused by this paper.  There was no rebuttal, and the authors did not engage or answer questions raised.  I concur with the reviewers, and encourage the authors to carefully consider the provided feedback.
Decision: Reject