Orchestrated Value Mapping for Reinforcement Learning
Authors: Mehdi Fatemi
Arash Tavakoli
Venue: ICLR 2022 Poster (2022)
Keywords: Reinforcement Learning
Value Mapping
Reward Decomposition

Abstract: We present a general convergent class of reinforcement learning algorithms that is founded on two distinct principles: (1) mapping value estimates to a different space using arbitrary functions from a broad class, and (2) linearly decomposing the reward signal into multiple channels. The first principle enables incorporating specific properties into the value estimator that can enhance learning. The second principle, on the other hand, allows for the value function to be represented as a composition of multiple utility functions. This can be leveraged for various purposes, e.g. dealing with highly varying reward scales, incorporating a priori knowledge about the sources of reward, and ensemble learning. Combining the two principles yields a general blueprint for instantiating convergent algorithms by orchestrating diverse mapping functions over multiple reward channels. This blueprint generalizes and subsumes algorithms such as Q-Learning, Log Q-Learning, and Q-Decomposition. In addition, our convergence proof for this general class relaxes certain required assumptions in some of these algorithms. Based on our theory, we discuss several interesting configurations as special cases. Finally, to illustrate the potential of the design space that our theory opens up, we instantiate a particular algorithm and evaluate its performance on the Atari suite.

Published as a conference paper at ICLR 2022
ORCHESTRATED VALUE MAPPING FOR REINFORCEMENT LEARNING
Mehdi Fatemi
Arash Tavakoli
Microsoft Research
Max Planck Institute for Intelligent Systems Tübingen, Germany
Montréal, Canada
mehdi. fatemi @mi crosoft.......... com
arash. tavakol i eetubbingent wpg. de
ABSTRACT
We present a general convergent class of reinforcement learning algorithms that is founded on two distinct principles: (I) mapping value estimates to a different space using arbitrary functions from a broad class, and (2) linearly decomposing the reward signal into multiple channels. The first principle enables incorporat- ing specific properties into the value estimator that can enhance learning. The second principle, on the other hand, allows for the value function to be repre- sented composition of multiple utility functions. This can be leveraged for various purposes, e.g. dealing with highly varying reward scales, incorporating a priori knowledge about the sources of reward, and ensemble learning. Combin- ing the two principles yields a general blueprint for instantiating convergent al- gorithms by orchestrating diverse mapping functions nels. This blueprint generalizes and subsumes algorithms such as Q-Learning, Log Q-Learning, and Q-Decomposition. In addition, our convergence proof for this general class relaxes certain required assumptions in some of these algorithms. Based on our theory, we discuss several interesting configurations special cases. Finally, to illustrate the potential of the design space that our theory opens up, we instantiate a particular algorithm and evaluate its performance on the Atari suite.
multiple reward chan-
INTRODUCTION
The chief goal of reinforcement learning (RL) algorithms is to maximize the expected return (or the value function) from each state (Szepesvári, 2010; Sutton & Barto, 2018). For decades, many algorithms have been proposed to compute target value functions either as their main goal (critic- only algorithms) or as means to help the policy search process (actor-critic algorithms). However, when the environment features certain characteristics, learning the underlying value function can become very challenging. Examples include environments where rewards are dense in some parts of the state space but very sparse in other parts, where the scale of rewards varies drastically. In the Atari 2600 game of Ms. Pac-Man, for instance, the reward can vary from 10 (for small pellets) to as large as 5000 (for moving bananas). In other games such as Tennis, acting randomly leads to frequent negative rewards and losing the game. Then, once the agent learns to capture the ball, it can avoid incurring such penalties. However, it may still take very long time before the agent scores a point and experiences positive reward. Such learning scenarios, for one reason or another, have proved challenging for the conventional RL algorithms.
One issue that can arise due to such environmental challenges is having highly non-uniform action gaps across the state space.' In a recent study, van Seijen et al. (2019) showed promising results by simply mapping the value estimates to a logarithmic space and adding important algorithmic components to guarantee convergence under standard conditions. While this construction addresses the problem of non-uniform action gaps and enables using lower discount factors, it further opens a new direction for improving the learning performance: estimate the value function in a different space that admits better propertics compared to the original space. This interesting view naturally raises theoretical questions about the required properties of the mapping functions, and whether the guarantees of convergence would carry from the basis algorithm under this construction.
Acttonn gap refers the value difference hetween optimal and second best actions (Farahmand, 2011 1).

---

Published as a conference paper at ICLR 2022
One loosely related topic is that of nonlinear Bellman equations. In the canonical formulation of Bellman equations (Bellman, 1954; 1957), they are limited in their modeling power to cumulative rewards that are discounted exponentially. However, one may go beyond this basis and redefine the Bellman equations in a general nonlinear manner. In particular, van Hasselt et al. (2019) showed that many such Bellman operators are still contraction mappings and thus the resulting algorithms are reasonable and inherit many beneficial properties of their linear counterparts. Nevertheless, the application of such algorithms is still unclear since the fixed point does not have direct connection to the concept of return. In this paper we do not consider nonlinear Bellman equations.
Continuing with the first line of thought, a natural extension is to employ multiple mapping functions concurrently in an ensemble, allowing each to contribute their own benefits. This can be viewed as form of separation of concerns (van Seijen et al., 2016). Ideally, we may want to dynamically modify the influence of different mappings as the learning advances. For example, the agent could start with mappings that facilitate learning on sparse rewards. Then, as it learns to collect more rewards, the mapping function can be gradually adapted to better support learning on denser rewards. Moreover, there may be several sources of reward with specific characteristics (e.g. sparse positive rewards but dense negative ones). in which case using different mapping to deal with each reward channel could prove beneficial.
Building upon these ideas, this paper presents a general class of algorithms based the combination of two distinet principles: value mapping and linear reward decomposition. Specifically, we present broad class of mapping functions that inherit the convergence properties of the basis algorithm. We further show that such mappings can be orchestrated through linear reward decomposition, proving convergence for the complete class of resulting algorithms. The outcome is a blueprint for building new convergent algorithms as instances. We conceptually discuss several interesting configurations, and experimentally validate one particular instance on the Atari 2600 suite.
VALUE MAPPING
We consider the standard reinforcement learning problem which is commonly modeled as a Markov decision process (MDP; Puterman (1994)) M = A, R, Po. where S and A are the discrete sets of states and actions, P(5'|s, [s,a)) = P( = 1,==,,, =a] is the state-transition distribution, r 8: = 8, 5, = 0, 81+1 = 81] (where we assume r E [Fmin: rmax)) is the reward distribution, (s(s) = P[so=s] is the initial-state distribution, and ? E [0, is the discount factor. A policy x{als) = Pf(a al st =] defines how an action is selected in given state. Thus, selecting actions according to a stationary policy generally results in a stochastic trajectory. The discounted sum of rewards over the trajectory induces random variable called the return. We assume that all returns are finite and bounded. The state-action value function Qr a) evaluates the expected return of taking action at state and following policy thereafter. The optimal value function defined as (* a) - max, Qr a), which gives the maximum expected return of all trajectories starting from the state-action pair (s. a). Similarly, an optimal policy is defined as T (alss) ) E arg max, Qx (s, a). The optimal value function is unique (Bertsekas & Tsitsiklis, 1996) and can be found, e.g., as the fixed point of the Q-Learning algorithm (Watkins, 1989; Watkins &
R(rls, a, s') = P(r. = r
Dayan, 1992) which assumes the following update:
Q1t1 at) + (1 Q a:) + (ra + y max Qe(s+41, a'
(1)
where a₁ is a positive learning rate time t. Our goal is map Q different space and perform the update in that space instead, so that the learning process can benefit from the properties of the mapping space.
We define a function f that maps the value function to some new space. In particular, we consider the following assumptions:
Assumption The function f(x) is bijection (either strictly increasing or strictly decreasing) for all x in the given domain 'D ([1,02) C R.
Assumption 2 The function fxx holds the following properties for all x in the given domain D (ci, C2) C R.
1. f is continuous on [es, 02) and differentiable on (c1, 02);
2

---

Published as a conference paper at ICLR 2022
2. [f(()) E [61,62] for (c1, 22), with 0 < 61 < 82
3. f is either of semi-convex semi-concave.
We next use f to map the value function, Q(x, to its transformed version, namely
((s. a) f(Q(s,)))
(2)
Assumption implies that f is invertible and, as such, Q(s, a) is uniquely computable from ((s. by means of the inverse function f-1. Of note, this assumption also implies that f preserves the ordering in x;; however, it inverts the ordering direction if is decreasing. Assumption 2 imposes further restrictions on S, but still leaves broad class of mapping functions to consider. Throughout the paper, we use rilde to denote a "mapped" function or variable, while the mapping f is under- standable from the context (otherwise it is explicitly said).
2.1 BASE ALGORITHM
If mapped value estimates were naively placed in a Q-Learning style algorithm, the algorithm would fail to converge to the optimal values in stochastic environments. More formally, in the tabular case, an update of the form (ef. Equation 1)
(1t1 az) t (1 - oz) Qe a.) + aaf ( 7 (
(3)
converges? the fixed point (0 a) that satisfies
(s. a)
(4)
Let us define the notation Q (8, a) = / 1 If is semi-convex bijection, f-1 will be semi-coneave and Equation deduces
(s) = f- (s)
= (Eg -~ R(
{ ( y max Q (s'
2 r- R(
1++ymaxe Q (s',
- RR.
y max Q (s)
(5)
where the third line follows Jensen's inequality. Comparing Equation 5 with the Bellman optimality equation the regular space, i.e. (* (s) E P. [r + max,' (" aa)), we conclude that the value function to which the update rule (3) converges overestimates Bellman's backup. Similarly, f is a semi-ce comi-concave function, then ( a) underestimates Bellman's backup. Either way, follows that the learned value function deviates from the optimal one. Furthermore, the Jensen's gap at a given state s - the difference between the left-hand and right-hand sides of Equation - depends the action because the expectation operator depends the deviation of @*( a) from Q" a) is not fixed-value shift and can vary for various actions. Hence, the greedy policy w.r.t. (with respect to) Q*(s, may preserve ordering and it may be an optimal policy either.
That is, at given state s,
In an effort to address this problem in the spacial case of f being logarithmic function, van Seijen et al. (2019) observed that in the algorithm described by Equation 3, the learning rate gener- ally conflates two forms of averaging: (i) averaging of stochastic update targets due to environment stochasticity (happens in the regular space), and (ii) averaging over different states and actions (hap- pens the f's mapping space). To this end, they proposed to algorithmically disentangle the two and showed that such a separation will lift the Jensen's 's gap if the learning rate for averaging in the regular space decays to zero fast enough.
Building from Log Q-Tearning (van Seijen et al., 2019), we define the base algorithm as follows: at each time the algorithm receives (s a) and transition quadruple (s, a, s'), and outputs Qe+1 (s, a), which then yields Q++1(8, a) = f-1 (Q++1(,,a) The steps are listed below:
"The convergence follows from stochastic approximation theory with the additional steps to show by induc- tion that @ remains bounded and then the corresponding operator is contraction mapping.
3

---

Published as a conference paper at ICLR 2022
Qs(s.a) ((lsaa===f) f- (δ)(s.a))
(6)
d' = arg max (c((6'a))
(7)
U. = r + rs (2)(
(8)
Ú; : f-1 (ō)(s.a) + Bregit (Ur (-1 (ō)(0,))))
(9)
Q0+1(s,0) = (x) + Sr (s(i)) ()))
(10)
Here, the mapping / is any function that satisfies Assumptions 1 and Remark that similarly to the Log Q-Learning algorithm, Equations 9 and 10 have decoupled averaging of stochastic update targets from that over different states and actions.
REWARD DECOMPOSITION
Reward decomposition can be seen generic way facilitate (i) systematic use of environmental inductive biases in terms of known reward sources, and (ii) action selection as well as value-function updates in terms of communication between an arbitrator and several subagents, thus assembling several subagents to collectively solve a task. Both directions provide broad avenues for research and have been visited in various contexts. Russell & Zimdars (2003) introduced an algorithm called Q- Decomposition with the goal of extending beyond the "monolithic" view of RI. They studied the case of additive reward channels, where the reward signal can be written as the sum of several reward channels. They observed, however, that using Q- QQ-Larnnig to learn the corresponding Q function of each channel will lead to a non-optimal policy (they showed it through a countercxample) Hence, they used Sarsa-like update w.r.t. the action that maximizes the arbitrator's ss value. Laroche et al. (2017) provided a formal analysis of the problem, called the attractor phenomenon, and studied a number of variations to Q-Decomposition. On related topic but with different goal, Sutton et al. (2011) introduced the Horde architecture, which consists of a large number of "demons" that learn in parallel via off-policy learning. Each demon estimates a separate value function based its own target policy and (pseudo) reward function, which can be seen as a decomposition of the original reward in addition auxiliary ones. van Seijen et al. (2017) built on these ideas and presented hybrid reward architecture (HRA) to decompose the reward and learn their corresponding value functions in parallel, under mean bootstrapping. They further illustrated significant results on domains with many independent sources of reward, such as the Atari 2600 game of Ms. Pac-Man.
Besides utilizing distinct environmental reward sources, reward decomposition can also be used as a technically-soune algorithmic machinery. For example, reward decomposition can enable utilization of specific mapping that has a limited domain. In the Log Q-Learning algorithm, for example, the log(-) function cannot be directly used on non non-positive values. Thus, the reward is decomposed such that two utility functions Q and Q are learned for when the reward is non- negattve or negative, respectively. Then the value is given by Q(x,aa = exp (Q+ (s.a)) - exp (Q (s, a)). The learning process of each of Q+ and Q bootstraps towards their corresponding value estimate at the next state with an action that is the arg max of the actual Q, rather than that of ++ and Q individually.
We generalize this idea to incorporate arbitrary decompositions, beyond only two channels. To be specifie, we interested in linear decompositions of the reward function into L separate channels p(i), for j 1... L, in the following way:
Xyr
(11)
with X5 E TR. The channel functions (i) map the original reward into some new space in such way that their weighted sum recovers the original reward. Clearly, the case of L = 1 and ' = would retrieve the standard scenario with no decomposition. In order to provide the update, expanding from Log Q-Learning, we define Ql)) for j 1 ... correppondngg to the above reward channels,
4

---

Published as a conference paper at ICLR 2022
and construct the actual value function Q using the following:
a=(s,a)== >115 (s.)..
(12)
We explicitly allow the mapping functions, fz. to be different for each channel. That is, each reward channel can have different mapping and each Q is learned separately under its own mapping. Before discussing how the algorithm updated with the new channels, we present a number of interesting examples of how Equation 11 can be deployed.
As the first example, we can recover the original Log Q-Learning reward decomposition by consid- =1,, and the following channels:
ering L 2, A1 +1, d2
f 0 otherwise
rr
(2)
rrl if 0
(13)
otherwise
Notice that the original reward is retrieved via r r() - ri This decomposition allows for using a mapping with only positive domain, such as the logarithmic function. This an example of using reward decomposition to ensure that values do not cross the domain of mapping function f.
(1)
In the second example, we consider different magnifications for different sources of reward in the environment so to make the channels scale similarly. The Atari 2600 game of Ms. Pac-Man is an example which includes rewards with three orders of magnitude difference in size. We may therefore use distinct channels according the size-range of rewards. To be concrete, let E [0, 100] and consider the following two configurations for decomposition (can also be extended to other ranges).
Configuration 1:
Configuration 2:
A 1,
A2 10,
As 100
A=
= 9, As = 90
if E 10
To ifr; E [0
r
(
Tt >>
Tt 1
(0
if $
if S 1 if E (1,10) > 10
((2)
0.1r
if E (1,10)
(n 1)/9
0
>>> 10
1
S ifr, S 10
0
if S 10 (rc 10)/90 if E (10, 100]
r
0.01rr
ifrr E (10, 100]
Each of the above configurations presents certain characteristics. Configuration 1 gives a scheme where, at each time step, at most one channel is non-zero. Remark, however, that each channel will be non-zero with less frequency compared to the original reward signal, since rewards get assigned to different channels depending on their size. On the other hands, Configuration 2 keeps each channel to act as if there is reward clipping at its upper bound, while each channel does not rewards below its lower bound. As a result, Configuration 2 fully preserves the reward density at the first channel and presents better density for higher channels compared to Configuration the number of active channels depends on the reward size and can be larger than one. Importantly, the magnitude of reward for all channels always remains in [0, 1] in both configurations, which could be a desirable property. The final point to be careful about in using these configurations is that the large weight of higher channels significantly amplifies their corresponding value estimates. Hence, even a small estimation error at higher channels can overshadow the lower ones.
However,
Over and above the cases we have presented so far, reward decomposition enables an algorithmic machinery in order to utilize various mappings concurrently in an ensemble. In the simplest case, we note that in Equation by construction we can always write
L
p(() = r and Σ j=1
=1
(14)
5

---

Published as a conference paper at ICLR 2022
That is, the channels are merely the original reward with arbitrary weights that should sum to one. We can then use arbitrary functions f, for different channels and build the value function as pre- sented in Equation 12. This construction directly induces ensemble of arbitrary mappings with different weights, all learning on the same reward signal. More broadly, this can potentially be com- bined with any other decomposition scheme, such as the ones discussed above. For example, in the case of separating negative and positive rewards, one may also deploy two (or more) different mappings for each of the negative and positive reward channels. This certain case results in four channels, two negative and two positive, with proper weights that sum to one.
ORCHESTRATION OF VALUE-MAPPINGS USING DECOMPOSED REWARDS
4.1 ALGORITHM
To have full orchestration, we next combine value mapping and reward decomposition. We follow the previous steps in Equations 6-10, but now also accounting for the reward decomposition. The core idea here is to replace Equation with 12 and then compute Q() for each reward channel in parallel. In practice, these can be implemented as separate Q tables, separate Q networks, or different network heads with shared torso. At each time f, the algorithm receives all channel outputs ((1)) for j 1... L, and updates them in accordance with the observed transition. The complete steps are presented in Algorithm 1.
A few points are apropos to remark. Firstly, the steps in the for-loop can be computed in parallel for all L channels. Secondly, mentioned previously, the mapping function fz may be different for each channel; however, the discount factor ? and both learning rates Sy, and Breg.t are shared among all the channels and must be the same. Finally, note also that the action 0e+1, from which all the channels bootstrap, comes from arg max, (+(8++1, a') and not the local value of each channel.
This directly implies that each channel-level value Q(i) (-)( does not solve channel-level Bellman equation by itself. In other words, Q(1) does not represent any specific semanties such as expected return corresponding to the rewards of that channel. They only become meaningful when they compose back together and rebuild the original value function.
4.2 CONVERGENCE
We establish convergence of Algorithm by the following theorem.
Algorithm 1: Orchestrated Value Mapping.
Input: (at time t)
211) for jorj= 1...L St. 0t, Tt, and 8141
Output: (0) for j = 1.... L
Compute r. (i) for j =1 1..L
begin
Qr(s;, Ej A115 (of (s))
(Q((8L41.a))
āet1 == arg max,'
j j = to L do
0.6) = r(())
+755 (Q: (5(11,
0.00 = 17 (Q! (st, Breg.t (v!1) 1 -8-1 (Q))) (st,
0112 (sr, (z) = 2.6h (sc, mn) + BI (I) (t(0) (s,,
end end

---

Published as a conference paper at ICLR 2022
Theorem Let the reward admit decomposition as defined by Equation 11, Qi(si, at) be defined by Equation 12, and all Q( (st:ae) updated according to the steps of Algorithm Assume further that the following hold:
1. All J3's satisfy Assumptions and 2;
2. TD error in the regular space (second term in line 4 of Algorithm 1) is bounded for all j;
3. EiS 35. Preggt oc;
4. Ee Ei=0(B3 Breg,t) < oc;
5. 35.t Bregst +0 as oc.
Then, Qr(s, a) converges to Qi (2, a) with probability one for all state-action pairs (s, a).
The proof follows basic results from stochastic approximation theory (Jaakkola et al., 1994; Singh al., 2000) with important additional steps to show that those results hold under the assumptions of Theorem 1. The full proof is fairly technical and is presented in Appendix A.
We further remark that Theorem 1 only requires the product Breg. i to go to zero. As this product resembles the conventional learning rate in Q-Learning, this assumption is no particular limitation compared to traditional algorithms.
contrast this assumption with the one the previous proof of Log Q-Learning which separately requires Breg go to zero fast enough. We note that in the case of using function approximation, as in a DQN-like algorithm (Mnih et al., 2015), the update in line 5 of Algorithm should naturally be managed by the used optimizer, while line 4 may be handled manually. This has proved challenging as the convergence properties can be significantly sensitive learning rates. To get around this problem, van Seijen al. (2019) decided to keep Bregit at fixed value in their deep RL experiments, contrary to the theory. Our new condition, however, formally allows Breg.t to be set constant value long as B3.t properly decays to zero
A somewhat hidden step in the original proof of Log Q-Learning is that the TD error in the regular space (second term in Equation 9) must always remain bounded. We will make this condition explicit. In practice, with bounds of the reward being known, one can easily find bounds of return in regular well ʃj spaces, and ensure boundness of U:()) 1 (Q(e) by proper clipping. Notably, clipping of Bellman target is also used in the literature to mitigate the value overflow issue (Fatemi al., 2019). The scenarios covered by Assumption 2, with the new convergence proof due to Theorem 1, may be favorable in many practical cases. Moreover, several prior algorithms such as Q-Learning. Log Q-Learning, and Q-Decomposition can be derived by appropriate construction from Algorithm 1.
4.3 REMARKS
TIME- DEEEDEEENDENT CHANNELS
The proof Theorem does not directly involve the channel weights Xy. However, changing them will impact Q.. which changes the action u,41 in line 2 of Algorithm 1. In the case that Xラ 's vary with time, if they all converge to their final fixed value soon enough before the learning rates become small, and if additionally all state-action pairs still visited frequently enough after Xy settled to their final values, then the algorithm should still converge to optimality. Of course, this analysis far from formal; nevertheless, we can still strongly conjecture that an adaptive case where the channel weights vary with time should be possible to design.
SLOPE OF MAPPINGS
Assumption asserts that the derivative of f, must be bounded from both below and above. While this condition is sufficient for the proof of Theorem 1, we can probe its impact further. The proof basically demonstrates bounded error term, which ultimately converges to zero under the condi- tions of Theorem 1. However, the bound on this error term (see Lemma 2 in Appendix A) is scaled by 8maz = max, 806,, with 8(0) being defined as
g(H) -66² / 06
(15)
7

---

Published as a conference paper at ICLR 2022
where 81 and 8 are defined according to Assumption (0 < 8 S [5)(2)] o64). In the case of fj being a straight line أها) = O, thus no error is incurred and the algorithm shrinks to Q-Learning. An important extreme case when 810) is too small while 86/) is not close 8( It then follows from Equation 15 that the error can be significantly large and the algorithm may need a long time to converge. This can also be examined by observing that if the return is near the areas where fj is very small, the return may be too compressed when mapped. Consequently, the agent becomes insensitive to the change of return in such areas. This problem can be even more significant in deep RL due to more complex optimization processes and nonlinear approximations. The bottom-line is that the mapping functions should be carefully selected light of Equation 15 to avoid extremely large errors while still having desired slopes to magnify or suppress the returns when needed. This analysis also explains why logarithmic mappings of the form fxx = c log + d) (as investigated in the context of Log Q-Learning by van Seijen al. (2019)) present unfavorable results in dense reward scenarios; e.g. in the Atari 2600 game of Skiing where there is a reward at every step. In this expression c mapping hyperparameter that scales values in the logarithmic space and d is a small positive scalar to ensure bounded derivatives, where the functional form of the derivative is given by f'(x)= = z Hence, 82 5. whereas do can be very close zero depending the maximum return. As result, when learning on task which often faces large returns, Logg Q-Learning operates mostly on areas of f where the slope is small and, as such, it can incur significant error compared to standard Q-Learning. See Appendix B for a detailed illustration of this issue, and Appendix D for the full list of reward density variations across a suite of 55 Atari 2600 games.
5 EXPERIMENTAL RESULTS
In this section, we illustrate the simplicity and utility of instantiating new learning methods based on our theory. Since our framework provides a very broad algorithm class with numerous possibilities, deep and meaningful investigations of specific instances go far beyond the scope of this paper (or any single conference paper). Nevertheless, as an authentic illustration, we consider the LogDQN algorithm (van Seijen et al., 2019) and propose an altered mapping function. As discussed above, the logarithmic mapping in LogDQN suffers from a too-small slope when encountering large returns. We lift this undesirable property while keeping the desired magnification property around zero. Specifically, we substitute the logarithmic mapping with a piecewise function that at the break-point 1 d switches from a logarithmic mapping to straight line with slope (i.e. the same slope as c log(æ + d) at a
d):
[c- log(z + d)
if 1
f(x) = cc. d) if > 1-d d
We call the resulting method LogLinDQN, Logarithmic--inee x = 1-d as the break-point has the benefit of using only a single hyperparameter to determine both the scaling of the logarithmic function and the slope of the linear function, which otherwise would require an additional hyperparameter. Also note that the new mapping satisfies Assumptions 1 and 2. We then use two reward channels for non-negative and negative rewards, as discussed in the first example of Section 3 (see Equation 13), and use the same mapping function for both channels.
DQN. Remark that choosing
Our implementation of LogLinDQN is based on Dopamine (Castro et al., 2018) and closely matches that of LogDQN, with the only difference being in the mapping function specification. Notably, our LogLin mapping hyperparameters are realized using the same values as those of LogDQN; i.e. = 0.5 and d R 0.02. We test this method in the Atari 2600 games of the Arcade Learning Envi- ronment (ALE) (Bellemare et al., 2013) and compare its performance primarily against LogDQN and DQN (Mnih et al., 2015), denoted by "Lin" or "(Lin)DQN" to highlight that it corresponds to linear mapping function with slope one. We also include two other major baselines for refer- ence: C51 (Bellemare et al., 2017) and Rainbow (Hessel et al., 2018). Our tests are conducted on a stochastic version of Atari 2600 using sticky actions (Machado et al., 2018) and follow a unified evaluation protocol and codebase via the Dopamine framework (Castro et al., 2018).
Figure 1 shows the relative human normaizor score of LogLinDQN w.r.t. the worst and best of LogDQN and DQN for each game. These results suggest that LogLinDQN reasonably unifies the good properties of linear and logarithmic mappings (i.c. handling dense or sparse reward distribu- tions respectively), thereby enabling it to improve upon the per-game worst of LogDQN and DQN
8

---

Published as a conference paper at ICLR 2022
LogLán vs. min(Log, Lin]
20016
200%
Alaon Maa Crom
Montaran B Blumitd Nareee
Upliitoni Chopper feor
Celor
A
Kongl R
Kelffn Horo denelii
"
200%
LogLin va. max(Log, Lin]
220%
letoe Aniieer
Battert
Beasing pertuato Addl Aif Airverre
Petall
Montamaall ALionned
Rosall Winsil Sentoyy
Sualtese Copplac
Crany: Stiing
VidrrPiabo
Koul
T Prieete
Butter
Diomss Spaniclo
Cooppert Kinght
Figure Difference numma-normalized score for 55 Atari 2600 games, LogLinDQN versus the worst (top) and best (bottom) of LogDQN and (Lin)DQN. Positive % means LogLinDQN outperforms the per-game respective baseline.
Mean
Median
Humat: Normolined Score
800%
150%
Rainbow
600%
100%
C51
(LinDQN
400%
LegDQN
50%
200%
LogLinDQN
0%
0%
Iseratoon
Iteration
Figure 2: Hluman-normallo mean (left) and median (right) scores across 55 Atari 2600 games.
(top panel) and perform competitively against the per-game best of the two (bottom panel) across large set of games. Figure shows median and mean numan-normalizer scores across a suite of 55 Atari 2600 games. Our LogLinnQQ) agent demonstrates significant improvement over most base- lines and is competitive with Rainbow in terms of mean performance. This is somewhat remarkable provided the relative simplicity of LogLinDQN, especially, w.r.t. Rainbow which combines several other advances including distributional learning, prioritized experience replay, and n-step learning.
6 CONCLUSION
In this paper we introduced convergent class of algorithms based on the composition of two distinct foundations: (1) mapping value estimates different space using arbitrary functions from broad class, and (2) linearly decomposing the reward signal into multiple channels. Together, this new family of algorithms enables learning the value function in a collection of different spaces where the learning process can potentially be casier or more efficient than the original return space. Ad- ditionally, the introduced methodology incorporates various versions of ensemble learning in terms of linear decompasition of the reward. We presented a generic proof, which also relaxes certain limitations in previous proofs. We also remark that several known algorithms in classic and recent literature can be seen as special cases of the present algorithm class. Finally, we contemplate re- search on numerous special instances as future work, following our theoretical foundation. Also, we believe that studying the combination of our general value mapping ideas with value decomposition (Tavakoli et al., 2021), instead of the the reward decomposition paradigm studied in this paper, could prove to be fruitful direction for future research.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We release generic codebase, built upon the Dopamine framework (Castro al., 2018), with the option of using arbitrary compositions of mapping functions and reward decomposition schemes as easy-to-code modules. This enables the community to easily explore the design space that our theory opens up and investigate new convergent families of algorithms. This also allows to reproduce the results of this paper through an accompanying configuration script. The source code can be accessed value value-mappinng mapping.
at: https:: /gi thub. conmmmocoosoft/orreeeeeeeeoe.eee
REFERENCES
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Marc G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. Proceedings of the International Conference on Machine Learning, pp. 449-458, 2017.
Richard E. Bellman. The theory of dynamic programming. Technical Report P-550, The RAND Corporation, 1954.
Richard E. Bellman. Dynamic Programming. Princeton University Press, 1957.
Dimitri P. Bertsekas and John Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
Pablo Samuel Castro, Subhodeep Moïtra, Carles Gelada, Saurabh Kumar, and Marc G. Bellemare. Dopamine: A research framework for deep reinforcement learning. arXiv:1812.06111,, 2018.
Amir-massoud Farahmand.
Action-gap gap phenomenon in reinforcement learning. In Advances in Neural Information Processing Systems, 2011.
Mehdi Fatemi, Shikhar Sharma, Harm van Seijen, and Samira Ebrahimi Kahou. Dead-ends and secure exploration in reinforcement learning. In Proceedings of the International Conference Machine Learning. pp. 1873-1881, 2019.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, 2018.
pp.
Tommi Jaakkola, Michael I. Jordan, and Satinder P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6(6):1185-120) 1994.
Romain Laroche, Mehdi Fatemi, Joshua Romoff, and Harm van Seijen. Multi-advises reinforcement learning. /t0l::/704.00700 2017.
Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew J. Hausknecht, and Michael Bowling. Revisiting the Arcade Learning Environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-5662 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, (2755(5))55995553 2015.
Martin I.. Puterman. Markov Decision Processex: Discrete Stochastic Dynamic Programming. John Wiley Sons, 1994.
Proceedings of the International Conference Machine Learning, pp. 656-663, 2003. Stuart Russell and Andrew L. Zimdars. Q-Decomposition for reinforcement learning agents. In
10

---

Published as a conference paper at ICLR 2022
Satinder P. Singh, Tommi Jaakkola, Michael L. Littman, and Csaba Szepesvári. Convergence results for single-step on- en-policy reinforcement-leaneee learning algorithms. Machine Learning, 38(3):287-300 2000.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2nd edition edition, 2018.
Richard S. Sutton, Joseph Modayil, Michael Delp. Thomas Degris, Patrick M. Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsuper- vised sensorimotor interaction. In Proceedings of the International Conference Autonomous Agents and Multiagent Systems, pp. 761-768, 2011.
Csaba Szepesvári. Algorithms for Reinforcement Learning. Morgan & Claypool, 2010.
Arash Tavakoli, Mehdi Fatemi, and Petar Kormushev. Learning to represent action values as hypergraph on the action vertices. In Proceedings of the International Conference on Learning Representations, 2021.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with Double Q- Learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 2094-2100, 2016.
Hado van Hasselt, John Quan, Matteo Hessel, Zhongwen Xu, Diana Borsa, and André Barreto. General non-linear Bellman equations. (rXivv/977.03687 2019.
Harm van Seijen, Mehdi Fatemi, Joshua Romoff, and Romain Laroche. Separation of concerns in reinforcement learning. arXiv:/612.05159, 2016.
Harm van Seijen, Mehdi Fatemi, Joshua Romoff, Romain Laroche, Tavian Barnes, and Jeffrey Tsang. Hybrid reward architecture for reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
Harm van Seijen, Mehdi Fatemi, and Arash Tavakoli. Using logarithmic mapping to enable lower discount factors in reinforcement learning. In Advances in Neural Information Processing Sys- tems, 2019.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanctot, and Nando de Freitas. Dueling network architectures for deep reinforcement learning. In Proceedings of the Interna- tional Conference on Machine Learning, pp. 1995-2003 2016.
Christopher J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, University of Cam- bridge, 1989.
Christopher J. C. H. Watkins and Peter Dayan. Q-Learning. Machine Learning, 8(3):799-292, 1992.

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM
We use a basic convergence result from stochastic approximation theory. In particular, we invoke the following lemma, which has appeared and proved in various classic texts; see, e.g., Theorem in Jaakkola et al. (1994) or Lemma in Singh et al. (2000).
Lemma 1 Consider algorithm of the following form:
A++1(z) == (1 (1-oz)AA(x) + a.p)(a))
(16)
with x being the state variable (or vector of variables), and og and the denoting respectively the learning rate and the update at time Then, Ae converges zero w.p. (with probability) one as + oo under the following assumptions:
The state space is finite;
a; = and E, o² < oo;
3.
w S < with E (0, and || l|w denoting a weighted
norm;
Var( (z) C (1+ [[Wr()))l)) . for some constant C::
where Fe is the history of the algorithm until time t.
Remark that in applying Lemma 1, the A, process generally represents the difference between stochastic process interest and its optimal value (that is Q₁ and Qi) and æ represents a proper con- catenation of states and actions. In particular, has been shown that Lemma applies Q-Learning as the TD update of Q-Learning satisfies the lemma's 's assumptions and 4 (Jaakkola et al., 1994).
We define Qi") (8, a) = 1 1 (कt (s, u)). for = 1 .... L. Hence,
L Q+(8,a) = EnS (s,a)) = En
(17)
We next establish the following key result, which is core to the proof of Theorem 1. The proof is given the next section.
Lemma 2 Following Algorithm 1, for each channel j E (I....,T.) D.} we have
Qi (St, oz) 22 (st,az) + Brega 3y, (u Q! (st, + te(")
(18)
with the error term satisfying the followings:
1. Bounded by TD error in the regular space with decaying coefficient
le.0 < Breg, Bra 505 (())) Q²") ())))((()))))) (st, ar)
(19)
where 800) = -5/0/ 8-5) is a positive constant;
2. For given f e does not change sign for all & (it is either always non-positive or always non-negative):
(1) 3. el is fully measurable given the variables defined at time
From Lemma 2, it follows that for each channel:
(st, az) (s,, a1) + Breg. 3I.0 (v.5) (s,, + +
(20)
12

---

Published as a conference paper at ICLR 2022
( converging to zero w.p. one under condition 4 of the theorem, and U,!) defined as:
with et
0. := rr.) + Q( (s441, a.+1).
Multiplying both sides of Equation 20 by >j and taking the summation, write:
Σ Ex00ff(05 Σ O) (5t, az) + Preae 8z Σ Xs (Ul) Ql (c) +el")
Hence, using Equation 17 we have:
Qut1(5E; 0t) Qe(se, at) Brega B1 Σ N (v!
(s),
j=1
= =e((e, ax) + Greg. 85 5=1
Σ Xi (rl) +7 ( (s),
(s), ot) +
el
Qe(se, at) + Bregi Big re + 7( Qe(s,, at) + Ngec
5=1
(21)
Definition of 1 deduces that
((+1) = Qe (1+1, arg max Qr (r(s+11, max (+(s+t1,a).
By defining e Ej=1 )ze(", rewire Equation 21 as the following:
+ max (r(s++1, - Qr at) + ee).
Q1+1 a+) = Q+(8,, ut) + Bregs 31 (''
(22)
a'
This is a noisy Q-Learning algorithm with the noise term decaying to zero a quadratic rate w.r.t. the learning rate's decay; more precisely, in the form of (Breg.x B3.,)².
Lemma requires the entire update to be properly bounded (as stated its assumptions 3 and 4). has been known from the proof of Q-Learning (Jaakkola et al., 1994) that TD error satisfies these conditions, i.e. rz + 7 max,' Qe(s++1, a') - Qe(se, ae) satisfies assumptions 3 and 4 of Lemma 1.
To prove convergence of mapped Q- Q-Learning, we therefore require to show that |ea also satisfies similar property; namely, not only it disappears the limit, but also does not interfere intractably with the learning process during training. To this end, we next show that as the learning continues, leel is indeed bounded by a value that can be arbitrarily smaller than the TD error. Consequently, as TT error satisfies assumptions 3 and 4 of Lemma 1, does |er], and does their sum.
Let 6max max, 86), with 866) defined in Lemma 2. Multiplying both sides of Equation 19 by X and taking the summation over j. it yields:
leal
Σ Age (
< Ayl- B1 Breg,t 860) |0,00) ((
< B1 Breg,t 8maz Σ 1yyl
-000 - (st
= Breg,t Smaz
Σ
My
(/0) + + + (s -01))) Q63 ( an)
1=1
(23)
13

---

Published as a conference paper at ICLR 2022
The second line follows from Lemma 2.
If TD emror in the regular space is bounded, then (7(0) ( (sc, ae) S k(
for some KG) 2 Hence, Equation 23 induces:
leel - S8,0 Breg,t 8max Σ 1yll K())
= 35.t Breggtt Omaz K,
(24)
with = Eド 1 KKO 2 0; thus, leel is also bounded for all t. As (by assumption) Breg.t 55,8 converges zero, conclude that there exists 2 0 such that for all & T we have
leal S { re + y max (s(44),, Qe(s)
(25)
for any given & E (0, 1].
Hence, not only lexl goes to zero w.p. one as + oo, but also its magnitude always remains upper- bounded below the size of TD update with any arbitrary margin &. Since TD update already satisfies assumptions 3 and 4 of Lemma I, we conclude that with the presence of e, those assumptions remain satisfied, at least after reaching some time T where Equation 25 holds.
Finally, Lemma 2 also asserts that e, is measurable given information at time t, as required by Lemma 1. Invoking Lemma I, we can now conclude that the iterative process defined by Algorithm converges to Q w.p. one.
PROOF OF LEMMA 2
PART
Our proof partially builds upon the proof presented by van Seijen et al. (2019). To simplify the notation, we drop j fj. while we keep j in other places for clarity.
By definition we have (s, (ot (o.))))))) Hence, we rewrite Equations 3, 4, and 5 of Algorithm in terms of Q!
v(T) = ((4) +- (8++1, Tx+1),
(26)
اه4ي = az) + Brege (U,5) - Q, (st, (s))a)))
(27)
(0f a.)) (00 (s)) + B3.1
az))
(28)
The first two equations yield:
0-ب0) Qf (st. ac) Breg, (1t + y (5411 2(11) (s()
(29)
By applying f1 to both sides of Equation 28, we get:
2 (Se, at)= = f (s
(st, (st + BB (5(1()) (sx, (st,aa)) at))
(30)
which can be rewritten as:
2ie Q(2 a.) )+ + 31.1 (f + o
(31)
where c. is the error due to averaging in the mapping space instead of in the regular space:
-- (s (Qf + 3r. (5(0()) -(Q(()) (s,, (s,, ai))))
Q.00) (s), (n)a))-- Br,1 (t() -Q( ((. (32)
14

---

Published as a conference paper at ICLR 2022
Table 1: Ordering of v and for various cases of SEMI-CONVEX
SEMI-CONCAVE
MONOTONICALLY INCREASING MONOTONICALLY DECREASING
f(w) S f()): wSv f(w) f(u): a f(w) f()); USW
f(w) 2 f()): w w
.) We next analyze the behavior of et under the Theorem I's assumptions. To simplify, let us intro- duce the following substitutions:
a (o), 0t)
b 0.6)
v (1 - -831) + 8yab
(1 - (aa) + Bza((b)
(w)
The error et can be written as
(i) f 1 -(1- -r,))(()) + ((1 B5,()a + By,
et
f (
w - U.
We remark that both and w lie between a and Notably, et has a particular structure which we can use to bound w See Table I for the ordering of u and w for different possibilities of f.
We define three lines (a)),,, 91 (x)). and (2(x) such that they all pass through the point (a, I fa)).
As for their slopes, (z) has the derivative fa( and g2 (z) has the derivative f'(b). The function gi (z) passes through point (b, fb)) as well, giving derivative (f(a) - f(b)/ 6). See Figure for all the possible cases. We
that matter if is semi-convex semi-concave and if is increasing or decreasing these three lines will sandwich f over the interval [a, b) if 2 a, or similarly over [b, al if 2 b. Additionally, it easy to prove that for all in the interval of a and b, either of the following holds:
(0(x) 2 f(z) 2 (x) (2(2)
(33)
9o(x) 1 f(x) $ (x)) - 92(2).
(34)
The first one is equivalent to
9o (v) | (v) و (1) - 92 (v).
(35)
while the second one equivalent to
(v) 2 f (y) > .. (v) 92 (v)
(36)
From the definition of 91 it follow that in all the mentioned possibilities of f combined with either of > b > a, we always have gi (v) and 91 (w) w. Hence, plugging t in Equation 35 and Equation 36 (and noting that (T) = w) deduces
90
W
I e 92 (w)
(37)
or
9o
( 7
N
92 (w).
(38)
Either way, regardless of various possibilities for f as well as a and b, we conclude that
(
|0 w|
10z (w) g0 (w))-
(39)
15

---

Published as a conference paper at ICLR 2022
A
(x)
5(b
[(a)
(x)
(1(3))
92(x)
(3r)
[(a)
f(0)
[(x)
8
01 w
(1
(x))
((x)
C
D
f(0)
[(a)
(x))
(x(x))
6
(x)
18
((6)
f(a)
(1
91 (ar)
((x)
E
92(1))
f(a)
f(x)
((b)
92(xr)
(x)
(xr)
9o(a)
06
f(b)
f(a)
1(x)
(1()))
6 m
b w
10
f(x)
G
H
0o(x))
f(a)
((
fxx
(a(x))
91 (2
(2(x)
1
9h
16
f(a)
5(b)
6
5 v/
u/
9o(x)
Figure 3: The lines 9o- 91 and for all the different possibilities of fy. Cases A-D correspond to a < b, and cases E-H are the same functions but for b < a. We use the notations w' = 9o (w) and = "9 (w).
16

---

Published as a conference paper at ICLR 2022
From definition of the lines Oo and O2. write the line equations as follows:
go(2) f(a) f') a),
g2(x) f(a) (b)((( a).
(w), 1) and (02 (w), i), respectively, it yields: Applying these equations the points (go (
i f(a) f' (9) (w) a).
8 [(a) = (b) (w) a))
which deduce
1 f(a)
1 f(a) (((b)
90
f((a)
+a
92 (w)
+
(40)
Plugging the above in Equation 39, follows:
f(a)
f(a)
le = 1 - w|
(((b)
(()a)
(w - f(a)) (w-f(a))
f'(b) f((a)
((tb) ((aa) )
(aL (11 (a 3r,s(b)) x(a))
1 81a (F(()) pla) (1(6)- ((66)-f(a))
(41)
We next invoke the mean value theorem, which states that if f is a continuous function on the closed interval [a, b) and differentiable on the open interval (a, b), then there exists a point c (a, b) such
that fbb fa)= (b(c)(b a). a). Remark that based on Assumption 2, would satisfy (c( S 8/ Hence,
also that T
['a]= I
|e(0) I
3,,0
1
) (F()) - f(a))
('(b)
f'(a)
1
(c)( 0)
1
(()
f'(a)
1
3
(b
8(5)
80
1
(0.0) (()(
3,
(42)
8(5)
801
From Equation 27, follows that
Q210(((( ar) = Bregi (u! - (s.,
We therefore can write
|e(0)
<
8f
1
(06) (0.0) - -Q(00 (st)
80)
1
5(3) Breg. (U(0) - Q.2 (se, (s.,
5(3)
(
Br.
Breg. 8(6)
0 - g.d0) (st, (st, ai)
where g()) 060)(
1
is positive constant. This completes the proof for the first part of
60
857
the lemma.
17

---

Published as a conference paper at ICLR 2022
PART 2
For this part, can be directly seen from Figure that for a given fj. the order of w', w, v, and o' is fixed, regardless of whether a 2 oor 2 (in Figure 3, compare each plot A, B, C, and D with their counterparts the bottom). Hence, the sign of (f)
will not change for fixed mapping.
PART 3
Finally, we note that by its definition, et comprises quantities that are all defined at time t. Hence, is fully measurable time i, and this completes the proof.
B DISCUSSION ON LOG VERSUS LOGLIN
10
8
y LogLin(x)
Mapped Returns
6
4
A
2
y = Log(x)
0
-2
-4
0 2 3 4 5 6 7 8 910 Original Returns
Figure 4: The functions Log and LogLin are illustrated. Remark the compression property of Log compared to LogLin for returns larger than one.
As discussed in Section 4.3 (Slope of Mappings), the logarithmic (Log) function suffers from too- low slope when the return is even moderately large. Figure visualizes the impact more vividly. The logarithmic-linear (LogLin) function lifts this disadvantage by switching to a linear (Lin) function for such returns. For example, if the return changes by unit of reward from 19 to 20, then the change will be seen as 0.05 in the Log space (i.e. log(20) log(19)) versus 1.0 in the LogLin space; that is, Log compresses the change by 95% for return of around 20. As, in general, learning subtle changes is more difficult and requires more training iterations, in such scenarios normal DQN (i.e. Lin function) is expected to outperform LogDQN. On the other hand, when the return is small (such as in sparse reward tasks), LogDQN is expected to outperform DQN. Since LogLin exposes the best of the worlds of logarithmic and linear spaces (when the return lies in the respective regions), we should expect to work best if is to be used as a generic mapping for various games.
18

---

Published as a conference paper at ICLR 2022
400%
LogLin vs. Log
0%
200%
Nome Theeeene
Astois
(Peer Booakoo Frodtbie
Chopper vemonaa
OpN Banuing
Monemmasl dovergge
Pitall
Gravite
Salans
A
Atlantie
Asterrida
Reseituunn eevefttnnne
Winrd Maant/W
Phostii
Blwiing winiing
Contiedt
Vommury
Amutar
Horrert
Botthr monteerone
Muthemmn
Corty Faslingd
Banklees
Videos
indesfiaaal
Iralnnks
Hors
Specell
DommA Artcckk
Sking
Temnu
Kong'
LogLin va. Lin
200%
0%
200%
Stathannee Nenu Kuampend lamedeen
Amadir Be Remaaiile
Choppet monmmn ponmaaedd Kungi Sigguueee Cenlped Cealpeeee
UphhDDost
Aleen
Riverns
Here
Pitbll
Howling
Curvior
TincPillo
Jeel leolinke
Attonigg Fisting Roviing
Coart Fattle ZofieZone
Freeeny
Eintbro Bauzlees Hele
Demant Woad OfW
Knill
Pratbiic
coree T foom
Temis modeneade dineeer Hesddig
Vi VideoPindal
Mi
Moniszanal
Spoces
Figure 5: Difference in LogDQN (top) and (Lin)DQN (bottom). Positive % means LogLinDQN outperforms the respective baseline.
score for 55 Atari 2600 games, LogLinDQN versus
C EXPERIMENTAL DETAILS
The human-normalized scores reported in our Atari 2600 experiments are given by the formula (similarly to van Hasselt et al. (2016)):
scOrengent ScOreandom
scorehaman ScOrerandem
where scoreagent- Scorepuman- and scorezandom are the per-game scores (undiscounted returns) for the given agent, reference human player, and random agent baseline. We use Table from Wang al. (2016) to retrieve the human player and random agent scores. The relative human-normalized score of LogLinDQN versus baseline in each game given by (similarly to Wang et al. (2016)):
scoreLagl.inDNN scorepuseline
max (axXTTeeaaseleee score scOrepandom
where sconeLagLinDDOy and scorepmeline are computed by averaging over the last 10% of each learning curve (i.e. last 20 iterations).
The reported results are based on three independent trials for LogLinDQN and LogDQN, and five independent trials for DQN.
D ADDITIONAL RESULTS
Figure shows the relative human-normalized score of LogLinDQN versus LogDQN (top panel) and versus (Lin)DQQ (bottom panel) for each game, across a suite of 55 Atari 2600 games. LogLinDQQ significantly outperforms both LogDQN and (Lin)DQQ on several games, and is otherwise on par with them (i.c. when LogLinDQN is outperformed by either of LogDQN or (Lin)DQN, the difference is not by large margin).
Figure shows the raw (i.e. without human- human-normalization)) learning curves across a suite of 55 Atari 2600 games.
Figures 7, 8, and 9 illustrate the change of reward density (measured for positive and negative rewards separately) at three different training points (before training begins, after iteration and after iteration 49) across suite of 55 Atari 2600 games.
19

---

Published as a conference paper at ICLR 2022
DQN
CS1
Rainbow
LogDQN
LogLinDQN
Autoroide
I5K
100
100
199
150
2014
Dicmatioon
Nurratiin
Ticradioo Lscarattader
Attantte
Starkt leart
Bustlettone
Herrark
10000
Pussatio
Duration
Boowiing
Beating
Contigode
Choppert commond
100
Sure
CrazyUlimber
DerwonArrack
DevahtaDunk
Stodaro
Dirtty
15000
Soure
Souce
Turadion
Tratsatoon
baradaa
12000
100
100
199
30
190
Dirmation
Nturattio
Tturaziee
Icallodooy
Farradhand
Kangaroo
KirnffuMaatter
5OVE
T5A
Turadiee
Tussation NhieTmieGame
Doraddan
Darauion
I'hoomix
Priverddiye
Qhert
Rivarratt
ReodRarnee
20000
100 Trassaion
Turradin
Dicradas
SeacoMst
Stttig
Spacelesndees
20000
Fon Tractionn TimoPhllr
199
170
StarGrrnve
18000
Ducaaion
Tuunatiin
Tansation
Donadaas
Veerue
VideoPaooll
Yorskevenge
Zanosu
2500
Figure 6: Learning curves in all 55 Atari 2600 games for (Lin)DQN, C51, Rainbow, LogDQN, and LogLinDQN. Shaded regions indicate standard deviation.
20

---

Published as a conference paper at ICLR 2022
Alien
Amidar
Assault
Asterix
Asteroids
0.25
0.2
0.5
0:25
0.25
0.00
0.00
0.0
0.00
Iteration
0.25
0.2
0.25
0.25
0.00
0.00
0.0
0.0
0.00
0.25
0.2
0.5
0:25
0.25
0.00
0.00
0.0
0.00
50
100
50
100
0
50
100
50
100
0
50
100
Atlantis
BankHeist
BattlcZone
BeamRider
Berzerk
0.2
0.2
0.1
0.2
0.2
0.0
0.0
0.0
0.0
0.0
Iteration
0.1
0.2
0.0
0.2
0.2
0.1
0.2
0.2
0.0
0.0
0.0
0.0
0.0
50
100
50
100
100
50
100
50
100
Bowling
Boxing
Breakout
Centipede
ChepperCommand
0.1
0.25
0.1
0.00
0.5
0.25
0.0
0.0
0.0
Iteration
0.25
0.1
0.5
0.00
0.5
0.0
0.25
0.0
0.0
0.1
0.25
0.1
0.00
0.5
-0.25
0.0
0.0
0.0
100
100
100
100
CrazyClimber
DemonAttack
DoubleDunk
Enduro
FishingDerby
0.2
0.25
0.5
0.0
0.00
0.0
-0.5
Ittration
0.2
0.2
0.2
0.25
0.5
0.0
0.00
0.0
0.0
0.0
0.2
0.2
0.2
0.2
0.25
0.5
0.0
0.00
0.0
-0.2
-0.5
50
100
50
100
50
100
50
100
50
100
Freeway
Frostbite
Gopher
Gravitar
Hero
0.25
0.0
0.00
0.0
Iteration
0.1
0.1
0.25
0.00
0
0.25
0.0
0.00
0.0
50
100
50
100
50
100
50
100
0
50
100
Positive
Negative
Steps (x10)
Figure 7: (Part 1/3) Reward density in the Atari suite. The rewards of each game are measured with three behavioral policies: (i) fully random (iteration 0: the first training iteration), (ii) an E-greedy policy using e 1, with state-action values estimated by (Lin)DQN agent after completing iterations of training, and (iii) similar to (ii) but after 49 training iterations. All experiments are averaged over 20 independent trials (shaded areas depict standard deviation) and for 1000 steps with a moving average window of 10 steps.
21

---

Published as a conference paper at ICLR 2022
IceHockey
Jamesbond
Kangaroo
Kruli
Kunaterr
0.1
0.1
0:25
0.0
-0.1
0.0
0.0
0.00
Iteration
0.1
0.1
0.25
0.0
-0.1
0.0
0.00
0.1
0.1
0:25
0.0
-0.1
0.0
0.0
0.00
50
100
0
50
100
0
50
100
50
100
0
50
100
MontozumaRevenge
MsPacman
NomeThisGame
Phoenix
Pitfall
0.01
0.5
0.25
0.00
0.25
10.01
0.00
0.0
0.00
Iteration
0.01
0.5
0.25
0
0.00
0.25
-0.01
0.00
0.0
0.00
0.01
0.5
0.25
0.00
0.25
-0.01
0.00
0.0
0.00
50
100
50
100
50
100
50
100
0
50
100
Pong
PrivateFyye
Qbert
Riverraid
RoadRunner
0.0
0.1
-0.5-
0.0
0.5
0.25
0.5
-0.1
0.0
0.00
0.0
Ittration
6
0.0
0.1
-0.5
0.5
0.25
0.5
0.1
0.0
0.00
0.0
0.0
0.5
0.25
0.5
-0.5
00.1
0.0
0.00
0.0
100
100
100
100
Robotank
Seaquest
Skiing
Solaris
Spacelnvaders
0.01
0.2
0.00
0,0
-0.01
Ittration
0.1
0.01
0.2
0.00
-0.01
0.0
0.01
0.2
0.00
0.0
00.01
0.0
50
100
50
100
0
50
100
50
100
0
50
100
SlarGunner
Tennis
TimePilot
Tutankham
UpNDown
0.2
0.1
0.2
0.25
0.0
0.25
0.0
0.1
0.0
0.00
0.00
Iteration
0.1
0.2
0.25
0.0
0.00
0.00
0.2
0.1
0.2
0.25
0.0
0.25
0.0
-0.1
0.0
0.00
0.00
50
100
50
100
50
100
50
100
0
50
100
Positive
Negative
Steps (x10)
Figure& 8: (Part 2/3) Reward density in the Atari suite. The rewards of each game are measured with three behavioral policies: (i) fully random (iteration 0: the first training iteration), (ii) an E-greedy policy using e 0. with state-action values estimated by (Lin)DQN agent after completing iterations of training, and (iii) similar to (ii) but after 49 training iterations. All experiments are averaged over 20 independent trials (shaded areas depict standard deviation) and for 1000 steps with a moving average window of 10 steps.
22

---

Published as a conference paper at ICLR 2022
Venture
VideoPinball
WizardOfWor
YarsRevenge
0.01
0.2
0.2
0.00
0.25
0.00
0.0
0.0
0.01
0.25
0.5
-0.03
0.00
0.01
0.2
0.2
0.00
0.25
0.00
0.0
0.0
50
100
50
100
100
50
100
100
Positive
Negative
Steps (x10)
Figure 9: (Part 3/3) Reward density the Atari suite. The rewards of each game are measured with three behavioral policies: (i) fully random (iteration 0: the first training iteration), (ii) an e-greedy policy using E 0.1, with state-action values estimated by (Lin)DQN agent after completing iterations of training, and (iii) similar to (ii) but after 49 training iterations. All experiments are averaged over 20 independent trials (shaded areas depict standard deviation) and for 1000 steps with moving average window of 10 steps.
23


Reviews:
[{"review_id": "TsG5IqV_28p", "reviewer": "Reviewer_1Ecs", "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": "The main contribution of the paper is a framework for mapping multiple reward channels to a \"nicer\" space in parallel. I find this general concept and framework to be both interesting and novel. I also thought the paper was well presented: the ideas are clearly described and easy to follow. The framework does build upon the work of van Seijen et al (2019), which somewhat hinders the novelty rating, but overall I believe this to be a useful contribution to the literature. In particular, I could see future work that seeks to discover good mappings or pick from a library of potential functions, and this paper provides the platform for that.\n\nOther positives include the softening of theoretical assumptions, which means we can get away with using a fixed learning rate (and have the other handled by Adam etc). This removes the need for yet another hyperparameter and will make implementing this framework (or even the original log Q learning work) easier. While I did not spend too much time on the appendix, I also liked the inclusion of Figure 3 in lemma 2, which made it slightly easier to follow than if it were just writing or mathematical notation. \n\nThe only downside for me to this paper is the misalignment between the theory and the experimental results. The theory and discussion talk at length about the advantages of various mappings. This is done with the Pac-Man example, as well as in the section \"Slope of Mappings\". While these discussions are interesting and highly relevant, the experiment itself only serves to show that the chosen mapping outperforms DQN and log Q learning across the Atari tasks. And while a reason for that performance is provided, this behaviour is never demonstrated experimentally. Put another way, the experiments could conceivably have come from *any* paper that improves upon DQN --- they don't really speak to the power or specifics of the framework here. \n\nI realise that space is an issue, but perhaps the Pacman example can be removed to make more room for an additional experiment? In particular, I could imagine something like a toy domain setup that has a top down view of the reward function and the effect that various choices of mappings have on it, as well as the resulting behaviour when the value functions are learned in the mapped space compared to the original reward function. Obviously, this is a very rough idea, but the main thing I'm looking for here would be to provide empirical support for some of the claims, such as \"As a result, when learning on a game which often has a large return, LogDQN operates mostly on areas of $f$ where the slope is small, and it can incur significant error compared to normal DQN.\"\n\nMinor comments:\n\n1. The second last paragraph in Section 4.2 that talks about boundedness. Do you mean here that if we know $r_{min}$ and $r_{max}$, then we know that the max return is $\\dfrac{r_{max}}{1 - \\gamma}$ and so we can use this to clip the values if necessary?\n2. How are c and d selected in Section 5?\n3. Bottom of page 3: \"bellow\"\n", "summary_of_the_paper": "The paper proposes a framework for estimating the Q-value function by decomposing the reward into a linear combination of reward signals or channels. These individual channels are then mapped into a new space, similarly to the log Q-learning approach of van Seijen et al (2019). However, here the framework is extended to a more general class of function (convex, etc). Additionally, some of the theoretical assumptions in the original log Q-learning paper are softened. The method (with a particular instantiation of reward mapping) is tested on the Atari benchmark, and demonstrates improved performance compared to DQN and log Q-learning.\n", "summary_of_the_review": "The paper proposes an interesting extension of prior work that offers great potential for expansion in future work. I'm very positive about the framework and theoretical results, but slightly down on the empirical ones, since they do not speak to the particulars of the framework. ", "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": "H9R04FRXne_", "reviewer": "Reviewer_159F", "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": "This paper applies the observations from [1] to describe a general algorithm that separates the Q-learning update into two steps: (i) averaging due to environment stochasticity, and (ii)  averaging over different states and actions, moving the latter into the other space. The paper presents these in a clear and simple way, which is very nice. It further formalizes these principles and incorporates them in a generic class of algorithms. It is interesting to see instances of these class in known existing algorithms. The paper is motivated from the view of small agent, big world needing to learn about many things at the same time, which is a promising avenue for autonomous agents. The paper is fairly clear, though it could benefit from some improvements in terms of structure. For instance, the section presenting the first idea describes a proof for a theorem it has not yet been stated, so it is a bit confusing. The authors could maybe move this discussion further down, after the theorem is presented. The assumption of having access to the minimum and maximum return is a bit alarming, how would one have access to those in an \\emph{unknown} environment, this seems to imply that the algorithm is not applicable in the same way to all instances of the same problem. The paper feels a bit disconnected, as one idea is presented after the next, and they are presented in a disconnected manner. The ideas are only at the end connected into an algorithm. In the reward decomposition section, there is a mention \"SARSA-like update\" as common knowledge, without introducing it. The reward decomposition is linear. Why? What are the limitations or assumptions that this is making, and why do we think that channels with separate properties will emerge in the reward space, such that they can be mapped to value functions with different properties, beyond the game-like artificial environments? Where do the values of the weightings applied to the reward channels come from ($\\lambda_i$)? The section discussing the \"slope of mappings\" makes insightful observations, but is a bit hard to follow, and would greatly benefit an illustration. It is only here that the reader is explained why \"Assumption 2\" was introduced all the way at the beginning, along with a lay word interpretation. The experimental section does not explain the results. What is $d$, where does it come from?", "summary_of_the_paper": "The paper describes a generic class of algorithms that decompose the reward signal into multiple channels and also map the value function into another generic space via arbitrary functions.  They argue such a class of function is useful to specify certain properties of the learned value on a specific reward signal, also decomposed into channels. They show that known algorithms from the literature are instances of this convergent class of methods.", "summary_of_the_review": "The paper presents an interesting idea of viewing value decomposition by mapping in a different space after separating the reward functions. Although some parts of the paper still leave open questions, most is clear and very simply written. This framework appears to be useful at least in the Atari domain, but the specifics of the experiment and interpretation of results would benefit some more clarity. The paper contains interesting insights.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "BuphmgjQ-Kc", "reviewer": "Reviewer_x9kQ", "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 strength: \n\n- New general value mapping that generalizes from previous work e.g. Log Q-learning\n- The orchestration of value mappings and decomnposed reward that can allow the above general value mapping. \n- Theoretical and experimental results to backup the proposed idea\n\nWeakness:\n\n- Contribution on value mapping and reward decomposition can be incremental.\n- Experiment results on average are still worse than Rainbow.\n\nIn overall, the paper is well written and pursues an interesting research problem. Though the proposed idea of value mapping and reward decomposition is incremental given existing work, it's worth trying and has showed the benefit.\n\nThe reward decomposition that is based on fixed and hand-designed configuration will limit the novelty and application. It's too technical comparing to the contributions in Sections 2 and 4.\n\nIt will be more useful if there are more choices of $f$. The current evaluation looks limited. Though there is improvement over LogDQN, it's unclear how and where the proposed ideas contribute to the score improvement. More ablation studies will also be helpful.", "summary_of_the_paper": "This paper proposes a new RL algorithm that contains two principles of value function mapping and reward decomposition. This proposal generalizes many existing RL frameworks such as classical Q-learning, Logarithmic Q-learning, and Q-Decomposition. The paper also provides generic theoretical results to backup the theory. The paper also demonstrates this idea on the suite of Atari 2600 games. ", "summary_of_the_review": "See above\n=====================\nAfter rebuttal: The author response has addressed my concerns. I am happy to increase the overall rating.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Description of paper content:

The paper provides a framework to develop a family of algorithms that decompose rewards into linear combinations of several reward channels. The value functions per channel are estimated in a new space using an invertible function transformation, f. The framework encompasses several previously published algorithms, including Log Q-Learning. Conditions are provided for acceptable choices of f. Convergence to the optimal Q function in the tabular case is proven for a special learning update.

Summary of paper discussion:

All review scores were above the acceptance threshold. Overall, the reviewers found the idea interesting, the theoretical results satisfying, and the writing and presentation clear. Initial concern about the directedness of the experiments in showing the usefulness of this particular theoretical framework to explain performance improvements was allayed when some of the results in the paper (e.g. reward density in Atari Skiing) were re-emphasized. Generally, all reviewers felt that this was a nice, thorough contribution with the demerit that the framework lacked “a killer application” experimentally.
Decision: Accept (Poster)