Adapting to Reward Progressivity via Spectral Reinforcement Learning
Authors: Michael Dann
John Thangarajah
Venue: ICLR 2021 Poster (2021)
Keywords: Reinforcement Learning
Deep Reinforcement Learning

Abstract: In this paper we consider reinforcement learning tasks with progressive rewards; that is, tasks where the rewards tend to increase in magnitude over time. We hypothesise that this property may be problematic for value-based deep reinforcement learning agents, particularly if the agent must first succeed in relatively unrewarding regions of the task in order to reach more rewarding regions. To address this issue, we propose Spectral DQN, which decomposes the reward into frequencies such that the high frequencies only activate when large rewards are found. This allows the training loss to be balanced so that it gives more even weighting across small and large reward regions. In two domains with extreme reward progressivity, where standard value-based methods struggle significantly, Spectral DQN is able to make much farther progress. Moreover, when evaluated on a set of six standard Atari games that do not overtly favour the approach, Spectral DQN remains more than competitive: While it underperforms one of the benchmarks in a single game, it comfortably surpasses the benchmarks in three games. These results demonstrate that the approach is not overfit to its target problem, and suggest that Spectral DQN may have advantages beyond addressing reward progressivity.

Published as a conference paper at ICLR 2021
ADAPTING TO REWARD PROGRESSIVITY VIA SPECTRAL REINFORCEMENT LEARNING
Michael Dann & John Thangarajah
School of Computing Technologies, RMIT University, Melbourne, Australia (mi chaeh. dann, John. taangara ja jahhj wew.aitae..du...........m
ABSTRACT
In this paper we consider reinforcement learning tasks with progressive rewards: that is, tasks where the rewards tend to increase in magnitude over time. We hypothesise that this property may be problematic for value-based deep reinforce- ment learning agents, particularly if the agent must first succeed in relatively unre- warding regions of the task in order to reach more rewarding regions. To address this issue, propose Spectral DQN, which decomposes the reward into frequen- cies such that the high frequencies only activate when large rewards are found. This allows the training loss to be balanced so that it gives more even weight- ing across small and large reward regions. In two domains with extreme reward progressivity, where standard value-based methods struggle significantly, Spectral DQN is able to make much farther progress. Moreover, when evaluated on set of six standard Atari games that do not overtly favour the approach, Spectral DQN remains more than competitive: While it underperforms one of the benchmarks in a single game, it comfortably surpasses the benchmarks three games. These re- sults demonstrate that the approach is not overfit to its target problem, and suggest that Spectral DQN may have advantages beyond addressing reward progressivity.
INTRODUCTION
In decision making tasks involving compounding returns, such as stock market investing, it is com- mon for the rewards received by the agent to increase in magnitude over time. An investor that starts out with little capital will achieve relatively small profits or losses early on, but if they are successful, their capital- and hence their potential profits and losses will gradually increase. This property also arises in many games settings. For example, in the Atari game Video Pinball, the player can increase "bonus multiplier" that increases the score paid per bumper hit. Since the bonus multiplier does not reset until the player dies, the rewards typically increase with time. In this paper, we refer to any task exhibiting this phenomenon a progressive reward task.
We hypothesise that reward progressivity may be problematic for value- deep reinforcement learning agents. Our rationale is that the temporal difference errors that arise under such algorithms typically scale with the magnitude of the training targets. Accordingly, experience collected from states with large expected returns may dominate training, causing the agent's performance degrade in other states. While this is rational in one sense generally, it is more important to make accurate decisions in high-stakes situations because, on progressive reward tasks, it may be necessary for the agent to perform well in relatively unrewarding regions before it can reach more rewarding regions. For example, in stock market investing, an investor can only reach states where they have large capital if they first perform well with small capital. Note too that the rewards need not be strictly progressive for this problem to arise; all that is needed is for the rewards to be progressive over some extended period.
potentially harmful on progressive reward tasks. This is
Algorithms that clip the reward, such as DQN (Mnih et al., 2015), are less susceptible to this prob- lem, because they do not perceive increases in reward magnitude beyond the clipping point. How- ever, it is straightforward to construct examples where reward clipping masks the optimal solution. For example, in Bowling, clipping the rewards to [-1, 1] makes bowling strike appear better than hitting a single pin (Pohlen et al. 2018). While subsequent approaches make learning feasible without reward clipping (van Hasselt et al. 2016 Pohlen et al. 2018), we show in Section that

---

Published as a conference paper at ICLR 2021
these methods are negatively impacted by strong reward progressivity. Motivated by this, seek an algorithm that is capable of learning from unclipped rewards, while mitigating the negative impact that large rewards have the agent's 's ability to learn in less rewarding regions of the task.
To meet this aim, we propose Spectral DQN. Under this approach, rewards are decomposed into a multidimensional spectral reward, where each component is bound to [-1, 1]. The upper frequencies of the spectrum activate only when large magnitude rewards are received. For example, in Video Pinball, the lowest frequency activates on any score, while the upper frequencies only activate when the player has accumulated a large bonus multiplier. The bounded nature of the spectral rewards allows the agent to learn expected spectral returns without instability arising from large training targets. Meanwhile, the full, unclipped expected return can be recovered by summing across the return spectrum. (The full, technical definitions of these terms are provided in Section ( In terms of addressing reward progressivity, key advantage of this approach is that it allows us to balance the training loss and prevent the upper frequencies from receiving undue weight.
To test whether this approach helps mitigate the impact of reward progressivity, we perform two set of experiments: First, we apply Spectral DQN to two domains that we specifically designed to exhibit strong reward progressivity. While previous methods struggle on these tasks, failing to learn almost anything at all in the more extreme domain, Spectral DQN performs markedly better, making considerable progress on both tasks. Next, we apply our approach namely, 6 standard Atari games. Only some of these games exhibit reward progressivity, and none of them nearly so strongly the extreme domains from earlier. While Spectral DQN does not outperform the benchmarks as noticeably in these domains (it is beaten by one of the benchmarks in single game, but comfortably outperforms both benchmarks in three games), the results clearly show that Spectral DQN is not overfit to constructed domains. Moreover, since its outperformance in some of the games cannot be attributed solely to reward progressivity, it appears that the approach may offer additional advantages, as explained later in our analysis of the results.
less constructed set of tasks;
2 PREVIOUS APPROACHES TO HANDLING REWARD VARIABILITY
In the Atari domain, where the DQN algorithm was first evaluated. the agent receives reward equal to the score increase at each frame. However, since score magnitudes vary greatly across games, DQN clips all rewards to [-1, +1. This constrains the size of the training targets that it is easier to find a step size that performs well across the entire suite of games. While this heuristic turns to perform well in Atari, a clear downside of the approach is that the agent becomes unable to distinguish large rewards from small rewards.
The Pop-Art algorithm (van Hasselt et al. 2016) offers a more principled solution. It trains from the unclipped reward, while normalising the training targets to have zero mean and unit variance. To ensure that the network's predictions are preserved when the normalisation parameters are updated, the output of the final layer is scaled and shifted by an offsetting amount.
Pohlen et al. (0188) propose an alternative approach to handling unclipped rewards that reduces the variance of the training targets by applying squashing function, h. The agent learns squashed action-values, ((s, a) = h(Q(s, a)), via the transformed Bellman backup:
(() + ((s,, a.) + + [[((r++ y max (apxxhh'((((s)) ((((5=11;)))) - ((s,,
The authors prove that the transformed Bellman operator remains a contraction provided that both h and h-1 are Lipschitz continuous and ? < L, (where Ln, and L,, the respective Lipschitz constants). In their experiments, they use the following squashing function:
h(x) sign(z) + 1) cz
where e > ensures that h1 is Lipschitz continuous.
For the remainder of this paper, we refer to this approach target compression. In the Atari domain, Pohlen et al. found target compression to perform significantly better than Pop-Art. It has since become the dominant method for handling unclipped rewards in Atari, with several recent large- scale agents (Kapturowski et al. 2019 Badia et al. 2020a b). including the state-of of-the-an art Agent57, favouring target compression over Pop-Art.
2

---

Published as a conference paper at ICLR 2021
3 DEMONSTRATING THE PROBLEM OF REWARD PROGRESSIVITY
While both Pop-Art and target compression address reward variance across tasks, making it easier to devise a single learning configuration that performs well across task suite, they were not designed to address intra-task reward variability. As such, we posit that they are ill-suited to addressing reward progressivity, since is an intra-task property. To test this claim, we introduce two domains that are designed to exhibit extreme reward progressivity, and thus exacerbate the issue: Ponglantis and Exponential Pong.
Ponglantis. In Ponglantis, the game starts out exactly the same the Atari game Pong, where valued-based deep reinforcement learning methods are known to perform well (Mnih et al.) 2015). The reward scale in Pong is small relative most Atari games; the player receives a +1 reward for hitting the ball past the computer paddle, and a -1 reward if they concede a point. In Ponglantis, however, if the player manages score 10 points, the task immediately switches to Atlantis, where the reward scale is roughly 1000 times larger. The Atlantis phase ends upon the loss of single life.
Exponential Pong. The game Exponential Pong identical to regular Pong, except that the rewards are multiplied by 2", where n is the player's current score.
We applied two agents these games: Pop-Art and DQN+TC, where the latter is version of DQN that we modified to use target compression and learn from the unclipped reward. The results of this experiment, averaged over 5 seeds, are shown in Figure I (For full experimental details, see the Appendix.) To simplify analysis of the Exponential Pong results, we have plotted the unexponenti- ated scores, i.e. the scores that the agents would have achieved under standard scoring Pong. For context, the best possible score on standard Pong is +21, and the worst possible score is -21.
In Exponential Pong, which exhibits the more extreme reward progressivity (since the reward mul- tiplier can potentially reach 2 ~ million), both agents essentially fail, providing strong support for our hypothesis that reward progressivity can be damaging, at least in extreme cases.
In the more moderate case of Ponglantis, Pop-Art fails to make meaningful progress beyond the low-scoring Pong phase of the task. The likely reason for this is that as soon as the agent starts reaching Atlantis and receiving large rewards, the target scaling mechanism employed by Pop-Art starts dividing the training targets by a large factor, heavily dampening the much smaller learning signals arising from the Pong phase of the task. On the other hand, DQN+TC is eventually able to make some progress into the Atlantis phase. The fact that DQN+TC outperforms Pop-Art is consistent with our hypothesis; while Pop-Art sees the reward scale jump by factor of <z 1000 upon reaching Atlantis, the training targets of DQN+TC jump by smaller factor, owing to the square root squashing function (Equation 2). In Appendix B.2, we perform some additional experiments in Ponglantis to find where the "cutoff points" for Por-Art and DQN+TC lie. i.e. how big the jump in reward magnitude has to for the agents' performances to start deteriorating.
Given the above discussion, a natural question to ponder is whether DQN+TC might achieve bet- ter performance Exponential Pong by employing a logarithmic squashing function instead of a square root. Unfortunately though, Pohlen et al. (2018) point out to a reviewer of their work (see https:/ wwwp/vvieeeeiieeeeeeeeeeee net forum? i d= Balikkffnoot Q a logarithmic transform does not have a Lipschitz continuous inverse, and thus the transformed Bellman is no longer guaranteed to be a contraction.
Ponglantis
Exponential Pong
20
00000
DQNITC
DQN TC
Pop-Art
Pop-Art
50000
40000
Scom
30000
-20
2
3
Training frames
Training fromes
1n7
Figure 1: Mean episodic return for agents trained on Ponglantis and Exponential Pong.
3

---

Published as a conference paper at ICLR 2021
4 SPECTRAL REINFORCEMENT LEARNING
Based on the findings of the previous section, seems that what we require is an algorithm where:
(1) The training targets constrained in magnitude, matter how large the reward scale grows. (2) Regions of the task with small rewards yield meaningfully large temporal difference errors, even once much larger rewards have been discovered. Note that Pop-Art fails
the second criterion, while target compression fails to meet both, albeit it takes larger shifts in reward magnitude for the problems associated with reward progressivity to become apparent.
In this section, we introduce reinforcement learning approach that meets both of the above criteria by leveraging the idea of spectral decomposition. This algorithm does ward progressivity; in fact, we show that it behaves identically to the standard Q-learning algorithm [Watkins] 1989), given certain caveats. However, the properties of this algorithm focoiittmaciiltae facilitate adaption to progressive rewards, and in Section we present deep learning version of the approach that is capable learning in domains with extreme reward progressivity, such as Exponential Pong.
and of itself address re-
4.1 SPECTRAL DECOMPOSITION
Spectral decomposition is broad term that arises in many different fields, but in this paper refers to a specific method for decomposing real numbers into a sum of exponentially weighted components.
The intuition behind our method illustrated in Figure In this example, the number being spec- trally decomposed is 6.5. The method begins by dividing the number line into buckets of width 1 where b > 0 is the base of the decomposition and i Zzo. Since the base here is 2, bucket has width and spans from 0 to 1, bucket has width 2 and spans from to 3, bucket 2 has width 4 and spans from 3 to 7, etc. The idea is that each bucket corresponds to different frequency in the spec- trum. The spectral decomposition is found by calculating the proportion of each bucket that is filled. Since the number 6.5 completely fills the first two buckets, then 87.5% of the next bucket, then none of the remaining buckets, the spectral decomposition of 6.5 to base 2 is (1, 1, 0.875, 0, ...).
More generally, let r be a non-negative real number, and let ri, denote the ith element of r's spectral decomposition base b. The formula for calculating each element is:
= clomp((r 6' 1/8' 0,
(See the Appendix for the derivation of this formula.) The value r can be recovered from the spectral decomposition by multiplying the bucket widths by the bucket fill proportions and summing:
Eizo D b'rt
This method can be extended to negative numbers by negating the sign on each element of the representation. Given any real number r, the formula for calculating each element becomes:
=
sign(r) clamp )/-1)/66,00 0/b,0,,1) 0,
(5)
4.2 DECOMPOSING THE RETURN
The core idea behind our reinforcement learning approach is apply spectral decomposition the reward stream, and thus learn spectral decomposition of the expected return. Before delving into the technical details, see Table for worked example that highlights the intuition. The discount
Bucket number,
0
1
3
Bucket width (=2))
I
Filled amount
I
2
3.5
5
Filled proportion
1
0.875
Spectral representation of 6.5 (1, 0.8.85 0, 0, O....
Figure 2: A worked example illustrating the spectral decomposition of the number 6.5.
4

---

Published as a conference paper at ICLR 2021
Spectral reward components
Time step,
Reward,
r2
r2
r2
0
1
0.99
1
0.25
0
2
0.98
1
1
0.5
3
0.97
-4
-1
-1
-0.25
0 -0.375
0.961
-10
-1
Return
2.254
Spectral returns
1.039
0.039
0.024
0.130
Weight, b'
2
8 1.039
Spectral return x weight
1.039
0.078
0.098
((Spectral return x weight)
2.254
Table 1: An example of return being decomposed into weighted sum of spectral returns.
factor is 7 0.99, and the return over the first five time steps 2.254. The usual way of calculating the return is, of course, to multiply the rewards by 7 then sum. The alternative, spectral approach first compute the spectral decomposition of the rewards according to Equation then calculate the returns arising from each reward frequency. We refer to the decomposed rewards as spectral rewards, and to the decomposed returns as spectral returns. The overall return of 2.254 can be found by multiplying the spectral returns by their corresponding weights of b then summing.
To appreciate why we go to this extra effort in calculating the return, note that the spectral rewards are all bound to [-1, IJ. This in turn constrains the magnitude of the spectral returns to be no more than / - 7), which, again, is useful from function approximation standpoint. Moreover, note that the relative sparsity of large rewards is made more apparent by this approach: As progress from r2 to 2. the magnitudes of the spectral reward components decrease, with only the two largest magnitude rewards triggering a response in r
4.3 SPECTRAL Q-LEARNING
To translate the above intuition into a concrete algorithm, we begin by defining the spectral action- value function
F. E rhe I a4 = a, 8, =
where rí.c denotes the ith element of the spectral reward time As shown in the Appendix, is straightforward prove via the linearity of expectation that the standard action-value function be recovered as the weighted sum:
as ()os))=\bbb(((ssss (s,a,s
This leads to a natural extension of the Q-learning algorithm (Watkins 1989). whereby the greedy action is found by maximising this expression with respect to the available actions, and (T(ss, a, is trained via the standard Bellman backup, except that the reward is replaced by the ith element of the spectral reward. For clarity, the full pseudocode for this algorithm, which we term Spectral Q-learning, is provided in the Appendix (see Algorithm [I.
An important practical limitation this algorithm is that is impossible to train over full, infinite spectrum; that is, must choose finite upper bound for i. (This would not be issue if we knew the maximum reward magnitude advance, but for generality we do not wish to assume this.) Regardless, for base b, observe that the first N frequencies capture all rewards up magnitude (b^ (b~+1 - l) - 1), since the bucket widths form a geometric series. Given the exponential nature of this term, is possible capture large magnitude rewards with relatively small value of N. For example, with = 2 and N = 20, the algorithm fully captures all rewards of magnitude up to million, which is more than sufficient for Atari Taking this logic one step further, we arrive the following proposition, which is proved in the Appendix:
Proposition 1 In the tabular setting, Spectral Q-learning behaves identically to standard Q- learning, provided that the rewards are bound in magnitude no more than (bN+1 -1) 1).
5

---

Published as a conference paper at ICLR 2021
Now that we have presented the full algorithm, it is worth reflecting why representation for the rewards instead of, say, a binary encoding. Put simply, very small differences in reward should not matter much rational agent. For example, it should not matter much whether a particular reward's magnitude is 63 or 64. However, under a binary encoding, 63 is represented 0111111, while 64 is represented frequencies than a reward of 64, it would thus trigger a larger TD error at the start of training. The thermometer-style encoding introduced earlier addresses this problem.
spectral
1000000. Since reward of 63 activates more
5 SPECTRAL DQN
In order to create a deep learning version of the Spectral Q-learning algorithm, we modify the DQN algorithm in an analogous way which we modified the Q-learning algorithm in the previous section. We name the resultant algorithm Spectral DQN.
To parameterise all N +1 1 frequencies of the spectral action-value function via single network, we multiply the number of outputs on the standard DQN network by the same count. One crucial detail here is that we initialise the weights and biases of the final layer to zero. This allows us to set N to conservatively large value, since it ensures that superfluous heads have no effect on training. Moreover, ensures that the action-value caleulations do not blow out due to the exponential weights in Equation beinn applied to random noise.
For the training loss, we use a weighted sum of the temporal difference errors for each frequency:
(()) = Σ. wi [ré + max, Q(s', a', (,,0"=0))) ((s, a, i;
(8)
where w; is the error weighting given to the ith frequency, s is state sampled uniformly from the replay memory, a the sampled action, s' is the next state, r the reward (with spectral components ri for i (O..... N),, 0 are the parameters of the network being trained, and 0 are the parameters of the periodically refreshed target network.
An important detail here is the approach we take to weighting the loss for each frequency. Given that the ith frequency weighted by b' when calculating the overall action-values, it is tempting to set w, = '² However, this goes completely against one of the aims of our approach, which is to prevent the large reward frequencies from dominating the loss. In fact, we show in the next section that weighting by b' has a disastrous impact in the two extreme domains introduced earlier.
In light of the above, rather than weighting by b', we strive to give all frequencies equal weighting. However, do not simply set w; 1. because doing so would effectively give too much emphasis to the small reward frequencies. As pointed out by van Hasselt et al. (2016), the gradients propagated to the Q-network's 's hidden layers depend quadratically of their work). Since the lower frequencies have denser rewards, and hence larger training targets, they will dominate the gradients the hidden layers if this effect not accounted for. To address this, we set w; = 1/0 where a; is the standard deviation of the training targets for frequency i, calculated as a rumning average in the Pop-Art algorithm. Finally, to ensure that this correction only affects the hidden layers. we unscale the gradients at the final layer to train as if w, = 1, as in standard DQN. (Implementing this is not especially difficult; the precise details can be found in our source code.) In Appendix B. we provide an ablation where we do not correct the hidden layer gradients, and we find that this has a significant adverse effect on performance.
the scale of the targets (see Section 2.3
RETURNING TO THE EXTREME DOMAINS
To test how well Spectral DQN meets our aims, we first applied it to the two extreme domains from Section 3 Ponglantis and Exponential Pong - where reward progressivity clearly a key issue. In addition, to probe the importance of the frequency loss weighting, we included variant of Spectral DQN with exponential loss weighting, i.c. w, = b', which we argued against in the previous section. The results of this experiment, including the baseline results from Section 3 shown in Figure with each curve averaged over 5 seeds.
There are two clear findings here: (1) Spectral DQN is much better handling extreme reward progressivity than the baselines. It scores much higher in Ponglantis, and makes far more meaning- ful progress in Exponential Pong, eventually learning beat the computer player confortably on

---

Published as a conference paper at ICLR 2021
Ponglantis
Exponential Pang
DQN-TC
DQN+TC
Pop-An Spectal DDN
Pop-Art
300000
20
Spectral
Speciall DQN exp. weight
Spectral DQN cxp. weghtt
200000
100000
-10
Training frames
267
Traiiin framess
167
Figure 3: Mcan episodic return for Spectral DQN vs. various baselines on the two extreme domains.
Art
DON-TC
Specnal DQN
To Elet
0.10
$0.00
3.30
PD
0.25
0.0
0.00
0.00
0.00
Trsining
Traning tramss
mhiniing
Figure 4: Evolution of the temporal difference percentage error in Exponential Pong.
average. (2) The loss weighting is of crucial importance, with the agent using exponential weights performing worse than even DQN+TC. The latter finding matches our expectations; as we noted in Section 3 target compression does at least somewhat mitigate the overemphasis given to large reward regions of the task, while Spectral DQN with w, = gives heavy emphasis to such regions.
In Figure 4 we examine how the agents' training errors evolve they play Exponential Pong. The errors are broken down by the player's current score E 20,20]. with bluer lines corresponding to states with low player score and redder lines corresponding states with high player scores. To make the graphs comparable, we plot percentage TD errors, i.e.:
(9) where the means are running averages, calculated from states sampled from the replay buffer. In all cases we report the true TD error, i.e. for DQN+TC we report the error on the uncompressed action-values, and for Spectral DQN we report the error on the full, summed action-values.
mean(IQpredictter Qtargerl) / mean((Qtargeel))
The instability of Pop-Art is quite apparent here: After a very brief period of stable learning, the TD errors start spiking as soon as the agent reaches even middling scores. Consistent with our earlier analysis, DQN+TC appears lot more stable. For states with low player scores, the TD percentage errors hover at around 5%, although the agent never really learns accurate action-values for states where the player score exceeds x7 points. At first this might seem strange since the reward scale increases exponentially with the player's score, states with a high player score ought to be effectively prioritised by the loss function. However, there is additional effect to consider here: As soon the agent's 's predictions start to deteriorate for the lower-score states, its policy for these states likewise deteriorates and it starts struggling to reach the higher-score states. As such, the agent seems get stuck in a middle ground, where it does not encounter the higher-score states often enough to learn accurate action-valuee there, nor for the estimates in the lower-score states to truly deteriorate. appears that TD percentage error of around 5% is a crucial cutoff line, where the agent is right on the cusp of being able to play well, but playing better, conversely, leads to deterioration.
In contrast to both Pop-Art and DQN+TC, when Spectral DQN reaches new high score, it quickly learns accurate action-value estimates for the associated states, as indicated by the sharply dropping red lines in Figure 4 Moreover, the TD emrrrs for the lower-score states remain stable the agent improves, almost certainly because Spectral DQN's loss does not give so much weight to large magnitude rewards. Finally, note that the agent's 's sudden rise in performance around 2.5 x 107 frames Figure? 3 seems to coincide with the errors reducing below the 5% line, adding further credence to the analysis above.
7

---

Published as a conference paper at ICLR 2021
7 EXPERIMENTS IN STANDARD ATARI GAMES
To validate that Spectral DQN's success in extreme domains does not come at the expense of per- formance in less constructed tasks, we also applied it to 6 standard Atari games. Moreover, we included 3 games where reward clipping is known to be detrimental, per van Hasselt et al. (211)): Bowling, Centipede and Ms. Pacman. This was done to validate that the agent's 's earlier success was not attributable to it somehow performing an implicit form of reward clipping. The results of these experiments are shown in Figure [
with all curves averaged over 5 seeds.
While Spectral DQN's performance relative to the baselines is not exceptional here as in the extreme domains, it remains the strongest overall. Though the agent underperforms DQN+TC in Centipede, it noticeably outperforms both baselines in Bowling, Chopper Command and Video Pin- ball. On the other games, it performs at least on par with the benchmarks. Moreover, the fact that Spectral DQN's performance compares favourably to Pop-Art in Bowling, Centipede and Ms. Pacman shows that it is truly responding to the unclipped reward.
Since Video Pinball exhibits reward progressivity. as explained in the introduction, Spectral DQN's strong performance there fits well with our hypothesis. On the other hand, while Ms. Pacman also has progressive rewards- the player receives an increasing bonus for eating multiple ghosts with a single power pellet- - these rewards come so close together that they are within the agent's 's temporal horizon at the start of an episode. That is, there is not a small-expeeted-reuue phase preceding a large-expected-retum phase, which we hypothesised to be central component of the issue. (We return to this point and discuss further in the next section.)
Besides addressing reward progressivity, another possible advantage of Spectral DQN in high scor- ing games is simply that its training targets are more constrained. In games such as Video Pinball and Chopper Command, the expected returns can reach into the thousands, pression this may be problematic for DQN+TC. On the other hand, the only game where DQN+TC clearly outperforms Spectral DQN is Centipede, which is also high scoring. One possible explana- tion for this is that the reward structure in Centipede "confuses" Spectral DQN: Since large rewards trigger both low and high frequencies, it is likely that Spectral DQN learns a positive association between the various components of the return. However, in Centipede, losing a life triggers stream of consecutive small rewards. Therefore, associating small and large rewards may cause Spectral DQN to predict an inflated return from dying.
even with target com-
There has been some conjecture that an advantage of combining distributional RL. (Bellemare et al, 2017 Lyle et al.) 2019) with function approximation is that it forces the agent to learn a richer representation. The same argument may also apply to our approach. In particular, in some tasks, small rewards are of more informational value than their face value represents. For example, in Video
bowinng
command
DON-TO
DCN+TC
DQNTTC
120
Ar.
Pas-Art
Pos-frt
Spectul DQV
Special DQN
Specaul
30000
10000
60
20000
8500
10000
4000
2000
Theriing hames
Thaining barmes
Thering fremes
Eshing_dityy
ma paammmn
Wideo pirbwl
100000
DQN-TC
4000
Ar
DGN
80000
Specral DON
-20
10000
40000
-50
-300
Training homes
1n7
Training tromss
Training trames
3w7
Figure 5: Mean episodic return for Spectral DQN vs. baselines on standard Atari games.
8

---

Published as a conference paper at ICLR 2021
Pinball, where rewards range into the thousands, the play field includes "spinners" that pay only one point per hit. Despite their negligible face value, hitting the spinners can dramatically change the velocity of the ball, giving the lower frequencies more weight in the training loss may promote a stronger representation. Similarly, in Bowling, certain frequencies only activate after bowling strikes and spares. Since the game does not have a strongly progressive reward structure, improved representation learning is more plausible explanation of Spectral DQN's outperformance.
DISCUSSION AND CONCLUSION
In this paper, we brought attention to the idea of reward progressivity, a task property that poses a potential issue for value-based reinforcement learning agents. Specifically, agent's performance in relatively unrewarding regions of a task may degrade once it discovers larger rewards. To address this issue, proposed Spectral DQN, which decomposes the expected return magnitudinally, al- lowing the losses arising across different regions of the task to be balanced. Our experiments showed this approach to be particularly effective in domains exhibiting extreme reward progressivity, while still yielding more than competitive performance in less constructed domains.
Our discussion of the Ms. Paeman results from the previous section raised an interesting point: There is clearly a link between reward progressivity and discounting. If it were somehow possible to train reliably with 7 = 1, a Ponglantis agent would be able see that reaching the large, distant rewards in the Atlantis phase is contingent on first performing well in Pong. However, despite some recent progress, DON-style agents typically destabilise with discounts very close to 1. Agent57 (Badia) let al. (020aa) trains multiple value functions across range of discounts, ranging as high as 7 0.9999. However, the authors note that = 0.9999 generally yields very unstable learning, and they rely on a meta-controller to select smaller discounts in games where learning destabilises. As such, it does not offer a general solution to the problem. The idea of setting 7 = 1 also raises the issue of reward sparsity: If the agent is cognizant of large, distant rewards, then smaller, more immediate rewards may appear so negligible that the task effectively becomes a sparse reward problem.
We noted in Section 3 that another idea for addressing reward progressivity is apply target com- pression, but with logarithmic squashing instead of a square root. However, as Pohlle et al. (2018) note, the inverse of logarithmic mapping is not Lipschitz continuous, and thus the transformed Bellman is no longer guaranteed to be a contraction. On the other hand, one way to get around poor convergence in practice is use a shaper discount factor. Van Seijen et al. (2019) show that it is possible to achieve performance comparable to DQN via logarithmic squash. provided the dis- count small (7 0.96). However, they clip the rewards, which greatly constrains the gradient of the inverse mapping h - and thus limits the degree to which their implementation transgresses the theory. Moreover, the performance of their method degrades significantly with y = 0.99, consistent with convergence issues (see Appendix C.2 in their work). Unfortunately. it is simple to provide examples where y = 0.96 will lead to poor performance. For example, in the game Bowling, there is a delay of about 100 frames between the ball being released and the subsequent reward. However, the player bowls a spare, the reward is delayed by further 100 frames. Thus, under a discount of 0.96, it is better consistently bowl 9s than to bowl spares.
Our work fits into a broader line of research whereby reinforcement learning agents seek to predict quantities other than just the mean expected return (Jaderberg al., 2016 [ellemare et al. 2017 Fedus et al. 2019). Of this related work, one of the most similar approaches to ours is that of Romoff al. (2019). who learn the value function in modular way by decomposing based on the discount Tactor. Distributional reinforcement learning (Bellemare et al.) 2017] Dabney et al.] 2018b a) is another closely related approach. Finally, an older line of work in this vein is decomposed RL (Russell & Zimdars, 2003, Sprague & Ballard, [003] Van Seijen et al. 2017). whereby an agent is responsible for predicting only a portion of the action-value function. While some of these works bear many surface-level similarities to our own - the distributional C5/ / agent (Bellemare et al.) 2017) in particular bears quite a similar network architecture to ours - on a deeper level, they are not addressing the same problem. Leveraging probabilistic loss, as in C51, could foreseeably help to address the large training errors that arise in tasks like Exponential Pong. However, the method assumes that returns are constrained to [-10, 10], and it is unclear how this could be extended to unclipped rewards without requiring an intractable number of atoms in the distribution, or greatly reducing the precision of the atoms.

---

Published as a conference paper at ICLR 2021
REFERENCES
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the Atari Human Benchmark. arXiv preprint arXiv:2003. 133350 2020a.
http//dd/22200 1000003..33350 13350. pdf wwtp:/iw...////////......
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, al. Never Give Up: Learning Directed Exploration Strategies. In Proceedings of the 2020 International Conference on Learning Representations (ICLR), 2020b. URL 0002.06033 pdf
Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 449-458, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Will Dabney, Georg Ostrovski, David Silver, and Remi Munos. Implicit Quantile Networks for Distributional Reinforcement Learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1096-1105, Stockholmsmässan, Stockholm Sweden, 10-15 15 Jul 201 8a. PMLR.
Will Dabney, Mark Rowland, Mare G Bellemare, and Rémi Munos. Distributional Reinforcement Learning with Quantile Regression. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018b.
William Fedus, Carles Gelada, Yoshua Bengio, Mare G Bellemare, and Hugo Larochelle. Hyper- bolic Discounting and Learning over Multiple Horizons. arXiv preprini 190Xiv::922.06655 2019.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukeuoglu. Reinforcement Learning with Unsupervised Auxiliary Tasks. arXiv preprint pdf
2016. URL htttss:/aaxxiv.orr/p//////// 05397.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent Expe- rience Replay in Distributed Reinforcement Learning. In Proceedings of the 2019 International Conference on Learning Representations (ICLR), 2019.
Clare Lyle, Mare G Bellemare, and Pablo Samuel Castro. A Comparative Analysis of Expected and Distributional Reinforcement Learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4504 4511, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-Level Control Through Deep Reinforcement Learning. Nature, 518(7540):529-533 2015.
Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Budden, Gabriel Barth-Maron, Hado Van Hasselt, John Quan, Mel Večerík, et al. Observe and Look Further: Achieving Consistent Performance on Atari. arXiv preprint arXiv: 1805. / 11593, 2018.
Joshua Romoff, Peter Henderson, Ahmed Touati, Emma Brunskill, Joelle Pineau, and Yann Ollivier. Separating value functions across time-scales. volume 97 of Proceedings of Machine Learning Research, pp.
Long Beach, California, USA, 2019. PMLR.
Stuart Russell and Andrew Zimdars. Q-Decomposition for Reinforcement Learning Agents. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 656-663, 2003.
Nathan Sprague and Dana Ballard. Multiple-Goal Reinforcement Learning with Modular Sarsa(O). 2003.
Hado P van Hasselt, Arthur Guez, Arthur Guez, Matteo Hessel, Volodymyr Mnih, and David Silver. Learning values across many orders of magnitude. In Advances in Neural Information Processing Systems 29, pp. 4287-4295. Curran Associates, Inc., 2016.
10

---

Published as a conference paper at ICLR 2021
Hann Van Seijen, Mehdi Fatemi, Joshua Romoff, Romain Laroche, Tavian Baress, and Jeffrey Tsang. Hybrid Reward Architecture for Reinforcement Learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp- 5392-5402. 2017.
Harm Van Seijen, Mehdi Fatemi, and Arash Tavakoli. Using a Logarithmic Mapping to Enable Lower Discount Factors in Reinforcement Learning. H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' A'Ach Buc, E. Fox, and R. Gameet (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 11334-1144. Curran Associates, Inc., 2019.
Christopher John Cornish Hellaby Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Cambridge, 1989.

---

Published as a conference paper at ICLR 2021
A EXPERIMENTAL SETUP
The source code for our experiments available at SpectrraDie
We injected stochasticity into the Atari environment via the no-ops regime used in the Nature DQN paper (Mnih et al. 2015). Rather than conducting periodic evaluations of the agents with small exploration constant, we simply report their training performance, since this arguably provides a more reliable measure of progress. All curves in the paper were averaged over seeds. Shaded regions represent bootstrapped single standard deviation confidence intervals.
Hyperparameters specific Spectral DQN listed in Table 2 while hyperparameters common to all agents are listed in Table Spectral DQN used an identical network architecture to Nature DQN Mnih al. (2013), except that we multiplied the number of outputs by + 1.
Hyperparameter
Value
Base of spectral decomposition, b
2.0
Maximum frequency, N
20
Table 2: Hyperparameters specific to the Spectral DQN agent.
Hyperparameter
Value
Optimiser
Adam
Adam learning
2.5 10
Adam regularisation constant
0.005 32
Discount factor
0.991/3
Multi-step backup
3
Final exploration
0.01
Reward clipping
None
Life loss signal used
True
Table Hyperparameters shared between all agents.
B ADDITIONAL EXPERIMENTS
In this section, we provide the details of some additional experiments that had to be omitted from the main text due to space constraints.
B. ABLATION: No ERROR WEIGHTING
Recall from Section that we weight the frequencies' individual losses by w; = 1/0 where o the standard deviation of the training targets for frequency In Figure 6 we show the effect of ablating this adjustment and simply setting ui = 1. The results reveal that the adjustment is crucial component, with the ablation proving disastrous Fishing results are unaffected, because only one reward frequency is active in that game.)
of the 6 games. (Note: It unsurprising that the
B.2 EASIER PONGLANTIS
In Section 3 we applied Pop-Art and DQN+TC the game Ponglantis. The results suggested that DQN+TC was somewhat more robust to reward progressivity. Here, provide some further experiments to determine just how strong the reward progressivity has to be for these agents to start deteriorating.
To hone in on the agents' breaking points, we created two modified versions of the game: Ponglantis Easier and Ponglantis Even Easier. In Ponglantis Easier, the agent's perceived rewards in the Atlantis phase of the task are scaled down by factor 10. Ponglantis Even Easier, they are scaled down by factor of 100. The agents' results in these games shown in Figure For comparability,
12

---

Published as a conference paper at ICLR 2021
bowiigg
cempaade
chopper command
120
Spectnil DgV
30000
No wr.ad)
Special DON
Special DON
No wi sc]
25000
12500
20000
10000
15000
60
5000
40
5020
2520
20
2
Trarting
Triining
Thering
deiby
moopaacmen
vidio_pirbal
100000
Soccral
Speciall DIN
Sperial DQN wrad)
No
800000
Store
-20
(00033
40000
80
20003
Training homes
Training fromes
Tratning fromes
3n7
Figure 6: Mean episodic return for Spectral DQN vs. Spectral DQN with no weight adjustment
(w;- = 1) on standard Atari games.
Ponglamss
Ponglantss Easier
Ponglants Evan Easier
500000
DOV+TC
520000
DCN-TC
500000
DON-TTC
PepuAtt
Pas-Ar
Pizshnm Spoduu DQN
Spenial DUN
spoc DQN
300000
300000
300000
202003
200000
200000
0
Tra
1x7
Trainin
Tisking
Figure 7: Mean episodic return for agents in Ponglantis, Ponglantis Easier and Ponglantis Even Easier.
the plots show the true episodic return, rather than the perceived episodic return. We also include results for Spectral DQN as a reference point.
Relative its performance in the original Ponglantis task, DQN+TC performs markedly better in both easier tasks. Since the rewards jump by a factor of around 1000 in the original task, this suggests that DQN+TC can tolerate a jump in reward magnitude of around 100x. Further, this implies that DQN+TC's underperformance relative to Spectral DQN in the main Atari experiments is attributable to more than just reward progressivity. as none of the standard Atari games exhibit this level of jump. Our alternate hypotheses about representation learning and the relative ease with which the spectral architecture can represent large expected returns thus appear more likely.
Pop-Art, on the other hand, still performs poorly when the perceived rewards in Atlantis are scaled down by a factor of 10, only learning reliably when they are scaled down 100 times. In this case, is plausible that the algorithm struggles with reward progressivity in standard Atari games.
B.3 REVERSE PONGLANTIS
To test whether it is truly reward progressivity that the key issue in Ponglantis, as opposed to just reward variability, we created one further task, Reverse Ponglantis, where the Pong and Atlantis phases are reversed. The player progresses to the Pong phase upon losing a life in Atlantis.
The agents' results in this game are plotted in Figure 8 While all agents improve steadily, which confirms that progressivity is the main issue for Pop-Art, it is notable DQN+TC's performance is actually worse here than in Ponglantis Even Easier. This is despite the fact that the agents now start in the high-scoring Atlantis phase, so there is no need to play Pong well. From this result, it is clear that key issue for DQN+TC is simply the reward scale in Atlantis. This adds further weight to
13

---

Published as a conference paper at ICLR 2021
hypothesis from Section that one of the main advantages of Spectral DQN in standard Atari games the constrained nature of its training targets.
Reverse Ponglantis
DQN+TC
400000
Pop-Art
Spectral DQN
300000
Score
200000
100000
0
1
2
3
Training frames
1e7
Figure 8: Mean episodic return for agents in Reverse Ponglantis.
C SPECTRAL Q-LEARNING ALGORITHM
Pseudocode for the Spectral Q-Learning algorithm is provided in Algorithm !
Algorithm Spectral Q-Learning
var: the base of the spectral decomposition, b
2: var: the number of spectral components trained,
3: var: the learning rate,
4:
5: Initialise Q(s, i)
6: for each episode do
7: Sample from start distribution
8: while is not terminal do
9:
Choose a according to e-greedy policy derived from Q(s,a) E ()(
10:
Take action observe s' a' arg max, Di for i (O.... N) do
11:
Li-o 6' ('Q(s',a',) a',
12:
13:
Q(s,a,1) + as + alri + QQ('',a", - a.))
14:
s's
D DERIVATION OF THE SPECTRAL DECOMPOSITION FORMULA
Recall from Section 4.1 that the spectral representation of number is found by laying buckets of
exponentially increasing width on the number line, then calculating the proportion of each bucket that is filled.
To calculate the proportion the ith bucket that is filled by a non-negative number r, note that the sum of all the preceding buckets' widths is equal to:
Σm1 6
(10)
Therefore, the amount leftover to fill the ith bucket is:
(1I)
14

---

Published as a conference paper at ICLR 2021
To calculate the proportion of the ith bucket that is filled, must divide this quantity by the width of the ith bucket (which is equal to 8') then clamp the result to the allowable range of values:
Filled proportion clamp((r 1
(12)
Finally, to convert this into an odd function so that the representation of -r is equal to the negated representation of r, we replace with |r| and multiply the result by sigm(r). This yields the formula for the ith element of the spectral representation:
r = sign(r) x clamp((Ir) -/-1)//000000000 0.
(13)
E PROOFS
E. PROOF EQUATION
Starting with the standard definition of the action-value function, then replacing the reward each time step with its spectral decomposition, we have:
( a) = Ex
E k=t rkk
ar a, = s]
(14)
= FT ce 7tt k-t Eimo b'r b,k |a. = a 8r 5
(15)
Since there is no interaction between the summation indices, we can rearrange 15
into:
(s, = E 1 b' kimt " az a, =
(16)
Finally, using the linearity of expectation, we can take the expectation operator inside and write:
(8, = Ei=o U'E EE (T az a, 8t s]
(17)
E (QT
(18)
E.2 PROOF OF PROPOSITION
Proposition 1 In the tabular setting, Spectral Q-learning behaves identically to standard Q- learning, provided that the rewards are bound in magnitude no more than -b 1)/
We prove this statement via induction. The first point observe is that, provided the action-vall estimates of the two algorithms agree at given point in time, their e-greedy policies at that time will also be equivalent. Therefore, assuming that the action-value functions agree at / (e.g- they are both initialised to zero), all we need to prove is the inductive step, i.e. that agreement in aetion-valuce at time implics agreement in action-values at time f f++
To distinguish between the action-value estimates of the two algorithms at different time steps, use the following notation:
Let ((s, a; 1) denote the action-value estimates under standard Q-learning after / updates.
Let Q(s, t) EN B'Q(s, i; denote the action-values estimates under Spectral Q-learning after updates.
For the induction step, we need to show that Q(s, a; + 1) as, Vs E S. e A given that Q(s, a; t) (ss, a; t) Vs E S, E A.
To begin, note that the standard Q-learning backup expressed under the above notation is:
Qs + Q(s, + aIr + (Q('s, a' ((s..
(19)
where a arg max, Q a²:; 1) is the greedy action for the state.
15

---

Published as a conference paper at ICLR 2021
Since assume equal action-valle at time Spectral Q Q-learning will calculate the same greedy action for s'. Hence, the backup for each frequency of the spectral action-value function is:
Q(s,a,1;t+11 Qss, a, 1; afri + 7Q(s a", 1,t) ((,, a, i)]
(20)
After performing this update each frequency, the function time + becomes:
Q(s,a;t+1] E b' Q0 ((s, ( i:t) a + 1Q(s d', i;t) ((s,a,i;t))
(21)
E ('Q(s,a,i;t)) + Σ ab [1 + tQ ;;;) Q(,, a(s, + E. ab' lrt QQ d" 1;t) is
(22)
(23)
Since the induction base case assumes that Q(s = a;) Vs E S, E A. we can rewrite this as:
(( 1)
(s,a;tt + a
(24)
((,,;;1) + a E b + "Q,, -
(Qs,,())
(25)
Q(s,att) a Σ i=0 -
(26)
((),a;t) + [ E b'rj
+ 2 a²":)) (s..a; t]
(27)
Now, all that remains establish equality with the standard Q-learning update in (19) is show that EN b'rj, r. That is, we need to show that the partial sum over indices to fully captures the reward, or, equivalently, that rī for all >= N
From the spectral decomposition formula (3 and the proposition's 's statement that the rewards are bound no more than (6 [)/(6 1). we have:
0, Insl clamp b 0,, 1)
(28)
clamp(( 1 b 0/1,0,11
(29)
clamp(
(1 b-1
/bb / 0,
(30)
Now, if >= N + 1, it implies that (b - 1) s 0, so the whole expression in 30 becomes 0.
Thus Σ b'rg Σ b'rg and the proof is complete.
16


Reviews:
[{"review_id": "es7eCmturDX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper details the problems that might arise in value-based reinforcement learning methods in domains where reward progressivity is present. To show that current methods do not handle reward progressivity, the authors introduce two domains, _Exponential Pong_ and _Ponglantis_.\n\nAfter showing that current methods do not work well in these domains, the paper then goes on to propose a solution, spectral decomposition of rewards. The paper shows that returns learned separately on decomposed rewards can be composed to get the original return. The paper then presents spectral Q-learning and spectral DQN, with experiments on the domains presented earlier as well as experiments on 6 Atari games.\n\nOn the two domains where progressive rewards were shown to be problematic, Spectral DQN is shown to work better than current approaches. On Atari games, spectral does as well as current approaches, doing better in 3 out of 6 domains.\n\n## Positives\n+ The setting of progressive rewards is interesting.\n+ The domains proposed for testing these rewards are clear.\n+ The spectral reward decomposition is a simple idea and is explained well.\n+ The effectiveness of spectral DQN on the two domains introduced in the paper is clear.\n+ Experimental details are clear and additional steps taken to stabilize learning are included.\n\n## Negatives/ Questions\n- One question that does not seem to be satisfactorily addressed is whether there is a commonly used benchmark domain or one which was not specifically engineered for progressive rewards where value based deep reinforcement learning would fail or not perform well unless it was using Spectral DQN.\n- The spectral DQN objective (eqn. 8) includes target compression. It is unclear how much benefit the spectral decomposition is having in the presence of target compression. While it is fine to require target compression for the full benefit of spectral DQN, it would be good to see an ablation of how well spectral DQN does without target compression.\n- Another useful ablation could be to remove the monte carlo mixing and show how unstable the updates get.\n- How does the van Seijen et al. paper on logarithmic mappings (Using a Logarithmic Mapping to Enable Lower Discount Factors in Reinforcement Learning) compare to the related work? It is motivated by a different problem, but since a possible logarithmic mapping might mitigate the problems that come up with progressive rewards their method might be a possible solution to be compared against.\n\n## Other Comments\n* Figure 2 has a typo (Fiilled instead of filled).\n\n## Summary\nOverall, I find the idea in this paper clear, simple, and effective. There are some additional questions and comments that if addressed would make the paper a more well-rounded submission.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "P_2rs-Ix7u", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an extension to DQN, more generally applicable to value-based deep RL systems, that encodes the return using a thermometer encoding with exponentially-sized bins. This enables returns of vastly differing magnitudes to be learned without hurting performance. The authors propose an algorithm for learning these encode returns, including the use of a variance scaling term to speed up learning.\n\nOverall, I enjoyed reading the paper and appreciated the clear exposition, which is sensible throughout. My main concern is whether this is solving a real problem, or a hypothetical one. The experiments don't support the former case, while I would argue that solving the problem hypothetically would require a more thorough development. For example, if progressivity is an issue, what form do we expect it to take? The two synthetic examples, Ponglantis and Exponential Pong, make for a fun case but not necessarily a realistic one. Training on all Atari games with a single network, for example, might be a better case. \n\nI have a few technical questions for the authors:\n\n4.1: Why use a thermometer encoding versus a binary encoding? I.e., write the reward in binary, and encode its bits. \n\n4.2: Why not use base gamma instead of base 2? That seems like a more natural way to encode returns.\n\n4.3: \"impossible to train over full, infinite spectrum\" -- given that returns are bounded for gamma < 1, what do you mean? It seems like you need log(VMax) bins at most.\n\n5: \"We do not simply set ...\" I would have expected some ablation studies here, regarding the role of the parameter. The choice w_i = 1/sigma_i seems particularly ad-hoc. In particular, I'm disappointed that you did not include the experiment w_i = 1. It seems natural to me that exponential weights should fail, whereas it's not clear that w_i = 1 should, and the use of sigma complicates things (and adds a moving part).\n\nThe results of Fig. 4 are not terribly exciting. Sometimes spectral DQN works better, sometimes it does not. Can you comment on this? Should we be concerned? Also, you should include published DQN results (and if possible, other value-based methods) as I would expect these to be worse for games that have rewards of different magnitudes. \n\n8: \"the phenomenon of reward progressivity\". Is the issue really progressivity? Or is it that value-based learners struggle to deal with rewards of varying magnitude (the progression doesn't matter)?\n\nDistributional RL algorithms replace the L2 loss with probabilistic losses. For example, the C51 algorithm uses the KL divergence. That could help deal with reward scale also, by creating a loss that is insensitive to scale. In particular, I can imagine the binary cross-entropy loss making sense since most of your outputs are binary. \n\n\nMinor points\n\n- Condition on gamma < 1/L_h L_h-1 -- doesn't that mean that Lh must be almost 1? Not much slack. \n- Intro, 2nd paragraph. A concrete example would help the reader here.\n- Table 1 might want to be left justified, as it's a little jarring to read.\n\n\n==== Updated review\n\nIn light of the authors' revisions, I'm happy to raise my score to 6. I think the paper is better, although I still wish the presentation was more compelling -- as given, this seems more like an exercise than a contribution with a demonstrated impact. On the other hand, this level of contribution seems relatively on par with e.g. other deep RL papers.\n\nRegarding the revisions, I would encourage the authors to integrate them with the main text. For example, Figure 3 really wants the weight=1 result (maybe as two separate panels -- comparison to other algorithms, a); ablation on weights, b)).", "extra_scores": {}, "extra_text": {}}, {"review_id": "E46BITZp1PY", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#######################################################################\n\nSummary:\n\nIn this paper the authors propose a new RL method, spectral DQN, in which rewards are decomposed into different frequencies. This decomposition allow for the training loss to better balanced on certain tasks - in particular those with progressive rewards. The new method is shown to perform well on specially constructed tasks with extreme reward progressively, as well as on a selection of standard Atari tasks.\n\n#######################################################################\n\nReasons for score:\n\nI think a weak accept is appropriate here. I think the authors correctly identify a class of worth while tasks - namely those with progressive rewards, and reasonably establish that standard approaches struggle here. The new method is a strong implementation of a simple idea which is demonstrated to work, and does not require significant fine-tuning.\n\n#######################################################################Pros:\n\n1. The paper is well written and clearly presented. I'd commend the authors on their exposition and balanced motivation throughout \n\n2. I think this is an interesting direction of work more generally - exploring the performance of different methods against different reward distributions, and having agents predict quantities more flexible than the mean return. This would seem to be a contribution to that body of work.\n\n3. I see no reason that the constructed domain ExponentialPong shouldn't join the benchmark for any subsequent general-purpose agent 🙂\n\n#######################################################################\n\nCons:\n\n1. While I believe the selected experiments are sufficient to demonstrate the claims in the paper, they do not fully explore the capabilities of the method and the intuitions that motivate it. It would have been good to see some more thinking here (even if it means experiments outside of Atari)\n\n(1) It would seem that this approach would work for a parametrizable class of reward functions - why not test that? Perhaps ExponentialPong with reward $b^(\\alpha N)$ evaluated on a grid for $b$ and $\\alpha$?\n\n(2) Similarly for failure modes\n\n(3) Frequencies needn't be geometric, how might other choices have performed\n\n2. I'd like to have seen a slightly richer discussion/motivation of the mixed Monte Carlo update. Clearly something is necessary here, but why this? What else was tried?\n\n#######################################################################\n\nQuestions during rebuttal period:\n\nQ1: you note the obvious limitation in the selection of the number of reward frequencies, but as you note this is reasonably easily ameliorated in practice. A more interesting question perhaps is whether an adaptive approach for b might work - was this tried?\n\n#######################################################################\n\nSome typos:\n\n(1) 'Expoential Pong' → 'Exponential Pong', just above 4.1'\n\n(2) Fig2, last row, \"Fiilled proportion\" → 'Filed proportion'", "extra_scores": {}, "extra_text": {}}, {"review_id": "20jv0MjuRf0", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work describes and addresses the issue of _reward progressivity_ in reinforcement learning, where as the task progresses the scale of the reward changes. The authors argue that reward progressivity harms Q-learning when training signals arising from large rewards interfere with those arising from smaller rewards. They propose a form of reward decomposition with an analogous modification to the Q-network output, which together help to ensure that training losses from small and large rewards are similarly scaled. The authors present a handful of experimental results demonstrating that their proposed method outperforms two other reward re-scaling baselines when reward progressivity is an issue and maintains good performance in more standard tasks.\n  \n  \n### Clarity\nThis paper is exceptionally clear. There are a couple areas where techincal details are somewhat missing: namely, their implementation of the mixed Monte Carlo update. Otherwise, the ideas are very clearly presented and the authors are careful to spell out caveats and details, which will improve reproducibility and downstream adaptation.\n\n### Originality and Quality\n_Spectral DQN_ is, to my knowledge, original. However, comparison to other forms of reward decomposition is lacking, both experimentally and in the discussion. The authors mention several examples of works that enable non-scalar representation of rewards for handling variability but there is not much attention given to how  these prior works are different and/or why they are not included as baselines.\n  \n_Reward progressivity_ as a motivating issue is also, to my knowledge, original. Indeed, the authors point out the 2 main baselines do not consider _intra-task_ reward variability. This brings up one of my main issues with the paper: there is very little demonstration that reward progressivity is the disruptive force that the authors describe it as. The authors show that baselines suffer/fail on tasks that are engineered towards this problem, but this doesn't offer enough to convince a sceptical reader to believe the paper's underlying intuitions. My understanding of these intuitions is that reward progressivity causes RL to stagnate because it biases the Q-network to be accurate around large rewards at the expense of being accurate around low rewards -- the issue being that this latter inaccuracy leads to poor policies in important but low-reward regions of the task.\n   \nIf this is indeed the intuition, then it would be very useful to actually demonstrate some sort of accuracy trade-off induced by reward progressivity. This would also provide a useful lens through which to validate Spectral DQN, by perhaps being able to characterize how it balances Q-network accuracy for different reward scales compared to other baselines.\n  \nIt would also be valuable to discuss whether reward progressivity is ultimately an issue of discounting. The authors seem to touch on this when describing the _Mrs. Pacman_ results, but a bit more exposition would be useful.\n \nThere are numerous other examples where the authors add interpretation around a particular result to help characterize where Spectral DQN does/doesn't succeed and what a practitioner might want to look out for.These interpretations improve the paper's quality somewhat, but the level of analysis is ultimately lacking. For instance, the authors offer speculation over the results for _Centipede_ and _Bowling_ but don't back up this speculation with any meaningful analysis. I would not want to punish the authors for offering these insights (that commentary is valuable and honest) but I do think the paper would have been better served by spending more time on analysis to back up a couple key insights.\n  \n### Significance\nIf we take the authors' claims at face value (which I am still inclined to do even though the paper lacks more detailed validation), this paper presents a simple technique to handle reward progressivity. This contribution is significant from a practical standpoint but perhaps only when solving tasks with this particular reward structure. For this to have broader signficance, it would be necessary for the authors to provide a more detailed characterization of the potential pitfalls associated with the technique's heuristics. Again, these are discussed (which is appreciated) but only speculatively.\n\n\n**Pros**\n- Adds a simple technique for balancing losses associated with rewards of different\n scales.\n- Follows a straightforward intuition.\n- Overcomes extreme examples of the problem it is designed to address.\n- No obvious, systematic drawbacks of the proposed modification.\n- Exceptionally clear and well-written.\n\n**Cons**\n- Analysis is limited to a handful of training curves with only one minor ablation (in Figure 3)\n- The paper tends to emphasize speculation over more concrete demonstration.\n- Unclear whether the motivating problem presents a significant obstacle.\n\n### Suggestions for improvement\nI would be happy to increase my score if the authors are able to address my criticisms. In particular, I think an analysis demonstrating the how learning dynamics are negatively impacted by reward progressivity (via its measurable effects on the Q-network) would go a long way. In addition, a more thorough ablation study and/or sensitivity analysis would add very useful clarity around the impact of, for example, the mixed Monte Carlo update strategy.\n\n\n### Post-discussion feedback\nThank you for the valuable discussion and revisions. I believe the paper has improved and I've updated my score to reflect that.\n\nThe new analysis in Figure 4 and its surrounding discussion offer some useful insights. I think the authors could still improve this analysis a bit in a final version of the paper (if only just to make the plots a bit easier to parse visually), but the TD-error instability of the baselines seems reasonably clear and I'm inclined to agree with how the authors frame this as an example of the problem they solve. In addition, the added discussion around discounting is also valuable; and the simplification of the algorithm and added ablation experiments improve the quality of the contributions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a deep RL algorithm to handle tasks where rewards can differ greatly in magnitude.  The proposed solution decomposes the reward into a set of exponentially sized bins with a thermometer encoding, and computes a weighted sum of the value functions learned for each bin.  The approach addresses the common tactic of reward clipping and value rescaling in deep RL algorithms.  The experiments demonstrate the potential utility of this approach on artificially constructed Atari games, and the experiments also show the approach remains competitive on six standard Atari games.  

The reviewers found both strengths and weaknesses in the paper.  The overall approach was viewed as a clear and sensible (R1, R2, R4) approach to handling widely varying reward scales in a domain.  It may be a useful contribution in a manner similar to other methods that make deep RL algorithms more robust to scaling issues encountered in practice (R4).  The main concerns were whether this was solving a real problem or not (R2, R3), and the lack of a theoretical development for the multiple heuristics (R2,R3).  

The author response then simplified the algorithm, which also served to clarify which aspects of the algorithm were relevant to the performance improvements. The response removed some of the heuristics (mixing in Monte Carlo returns) and changed other choices to be more principled ($1/\sigma^2$). The author response also described how the proposed algorithm addressed different scaling concerns from those handled by earlier methods. The author response also provided clarifications to many minor questions raised by the reviewers.  In the ensuing discussion, the reviewers were happy with the revised paper.  Though some minor theoretical reservations remained, the reviewers agreed this paper was a useful contribution.

The reviewers indicate to accept the paper as a useful contribution in deep RL to address certain reward scaling issues.  The paper is therefore accepted. 
Decision: Accept (Poster)