ORCHESTRATED VALUE MAPPING
Year: 2021

Abstract:
We present a general convergent class of reinforcement learning algorithms that is founded on two distinct principles: (1) mapping the value function into a different space via arbitrary functions from a broad class and (2) linearly decomposing the reward signal into multiple channels. The first principle enables asserting specific properties on the value function 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, including 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 classical Q-Learning, Log Q-Learning, and Q-Decomposition. Moreover, our convergence proof for this general class relaxes certain required assumptions in some existing algorithms. Using 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 suite of Atari 2600 games.

heading: 1 INTRODUCTION
text: The chief goal of reinforcement learning (RL) algorithms is to maximize the expected return — the value function — from each state (Sutton & Barto, 2018; Szepesvári, 2010). For decades, many algorithms have been proposed to compute the value function either as their main goal (critic-only algorithms) or as the means to help the policy search process (actor-critic algorithms). However, when the environment comprises certain properties, learning the induced value function may become very challenging (van Seijen et al., 2019). Examples include environments where rewards are dense in some parts of the state-space but very sparse in other parts, or when the size of rewards may vary dramatically. 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 like Tennis, as the agent acts randomly, it easily loses the game, causing negative rewards with high frequency. However, when the agent learns to capture the ball (hence no negative reward anymore), it may still take a very long time before the agent gains a score and see a positive reward. Such learning scenarios, for one reason or another, have proved challenging for the conventional RL algorithms.
One issue that may rise due to these environmental challenges is for the action gap — the optimal value difference between the best and second-best actions (Farahmand, 2011) — to become significantly non-uniform. A recent study (van Seijen et al., 2019) showed promising results by simply mapping the value function to a logarithmic space and add important algorithmic steps to guarantee the convergence under generic conditions. While this construction addresses the problem of nonuniform action-gap and facilitates the use of smaller discount factors, it further opens a new direction to improve the learning: learn the value function in a different space that admits better properties compared to the original space. This interesting view naturally raises theoretical questions about the required properties of the functions that map the value to the learning space, and whether the algorithm still guarantees to converge to the optimal value function under this new construction.
A loosely related topic is to presume a nonlinear Bellman equation. Originally, the Bellman equation of optimality (Bellman, 1954; 1957) is a direct result of defining return as a discounted sum of future
rewards. However, one may ignore this basis, and re-define Bellman equation in a generic non-linear way. In particular, van Hasselt et al. (2019) have shown that the new Bellman operator is still a contraction mapping and therefore the resulting algorithms may be well-behaved. 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 use different mappings concurrently as an ensemble, each of which adding different benefits, just like having various expertise in the board that runs a company. This may also be seen as a way of separation of concerns (van Seijen et al., 2016). Ideally, we may wish to dynamically modify the influence of different mappings as the learning advances. For example, the agent may start with mappings that facilitate learning from sparse rewards, then as the agent learns to collect more rewards and they get denser, it gradually switches to mappings that simplifies learning on dense rewards. Of note, if there are known sources of rewards with known, specific characteristics (say sparse positive rewards, but dense negative ones), same approach may prove beneficial. This has been the backbone for reward channeling architectures such as (van Seijen et al., 2017).
In this paper, building upon the aforementioned ideas, we present two orthogonal directions: generic value mapping and reward decomposition. We then combine the two and build a broad algorithm class, which can be instantiated to generate various interesting agents. We present the convergence results for the complete version of the algorithm. It is worth noting that this algorithm may be best seen as a blueprint for constructing other convergent algorithm classes.

heading: 2 VALUE MAPPING
text: We consider a general reinforcement learning problem, modeled as a Markov Decision Process (MDP) (Puterman, 1994) M = (S,A, P, r, γ), where S and A are the discrete sets of states and actions; P : S ×A× S → [0, 1] is a transition function that defines the transition probability from state s to s′ if action a is taken; r : S × A × S → [rmin, rmax] is a reward function and γ ∈ [0, 1] denotes a scalar discount factor. A policy π(s, a) = P[At = a | St = s] defines how an action is selected in a given state. Therefore, selecting actions according to a stationary policy in general results in a stochastic trajectory. The discounted sum of rewards over the trajectory induces a random variable, called return. We assume that all returns are finite and bounded. A trajectory is therefore called optimal if it induces maximum return. A state-action value function Qπ(s, a) is defined in conjunction with a policy π. Qπ(s, a) induces the expected return of taking action a at state s and following π thereafter. The optimal value function is defined as Q∗(s, a) = maxπ Qπ(s, a), which is the maximum expected return of all trajectories starting from (s, a). Similarly, an optimal policy is defined as π∗(s, a) = arg maxπ Qπ(s, a). The optimal value function is unique (Bertsekas & Tsitsiklis, 1996) and can be found for example as the fixed-point of the Q-Learning algorithm (Watkins, 1989; Watkins & Dayan, 1992), given by the following update rule:
Qt+1(st, at)←− (1− αt)Qt(s, a) + αt(r(st, at, st)) + γmax a′ Qt(st+1, a ′)) (1)
where αt is the learning rate (step size) parameter defined at time t. Our goal is to first map Q to a different space, and then perform the update, so that the learning process can benefit from the properties of the mapped space.
We define a function f that maps the value function to some new space. In particular, we consider the following assumptions:
Assumption 1 The function f(x) is a bijection (either strictly increasing or strictly decreasing) for all x in the given domain D = [c1, c2] ⊆ R.
Assumption 2 The function f(x) holds the following properties for all x in the given domain D = [c1, c2] ⊆ R:
1. f is continuous on [c1, c2] and differentiable on (c1, c2);
2. |f ′(x)| ∈ [δ1, δ2] for x ∈ (c1, c2), with 0 < δ1 < δ2 <∞;
3. f is either of semi-convex or semi-concave.
We next use f to map the value function, Q(s, a), to its transformed version, namely
Q̃(s, a) = f (Q(s, a)) (2)
Assumption 1 induces that f(x) is invertible, which we denote by f−1(x). Additionally, having known either of Q(s, a) or Q̃(s, a), the other one is uniquely computable. Of note, this assumption also implies that f preserves ordering; however, it will change the direction of ordering if f is decreasing. Assumption 2 imposes more restriction on f ; nevertheless, it is still a broad class of functions to consider. Throughout the paper, we use tilde notation to refer to the “mapped” function or variable, while the mapping f is understandable from the context (otherwise it is explicitly said).

heading: 2.1 BASE ALGORITHM
text: If the mapped value is naively placed in a Q-Learning-like algorithm, it will not converge to the optimal values in stochastic environments. More formally, for a tabular MDP, an update of the following form: (compare it with equation 1)
Q̃t+1(st, at) := (1− α)Q̃t(st, at) + αf ( rt + γmax
a′ f−1
( Q̃t(st+1, a ′) ))
(3)
converges1 to the fixed point Q̃ (s, a) that satisfies Q̃ (s, a) = Es′∼P (s,a,·) [ f ( R(s, a, s′) + γmax
a′ f−1
( Q̃ (s′, a′) ))] , (4)
where s′ denotes the next state. Let us define the notation Q (s, a) .= f−1 ( Q̃ (s, a) ) . If f is a
semi-convex bijection, f−1 will be semi-concave and equation 4 deduces
Q (s, a) . = f−1 ( Q̃ (s, a) ) = f−1 ( Es′∼P (s,a,·) [ f ( R(s, a, s′) + γmax
a′ Q (s′, a′) )]) ≥ Es′∼P (s,a,·) [ f−1 ( f ( R(s, a, s′) + γmax
a′ Q (s′, a′) ))] = Es′∼P (s,a,·) [ R(s, a, s′) + γmax
a′ Q (s′, a′)
] , (5)
where the third line follows Jensen’s inequality. Comparing (5) with the Bellman’s optimality equation in the regular space, i.e. Q∗(s, a) = Es′∼P (s,a,·) [R(s, a, s′) + γmaxa′ Q∗(s′, a′)]; we conclude that the value function to which (3) converges over-estimates Bellman’s backup. Similarly, if f is a semi-concave function, then Q (s, a) under-estimates Bellman’s backup. Either way, it follows that the learned value function deviates from the optimal one. Further, the Jensen’s gap at a given state s — the difference between left- and right-hand-side of (5) — depends on the action a because the expectation operator depends on a. That is, at a given state s, the deviation of Q (s, a) from Q∗(s, a) is not a fixed-value shift and can vary for various actions. Hence, the greedy policy w.r.t. Q (s, ·) may not preserve ordering and it may not be an optimal policy either. In an effort to address this problem in the spacial case of f being a logarithmic function, van Seijen et al. (2019) observed that in the algorithm described by equation 3, the step-size α generally 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/actions (happens in the f space). Moreover, they proposed to algorithmically separate the two and showed that such a separation will lift the Jensen gap between Q (s, a) and Q∗(s, a) if the learning rate of the regular space decays to zero fast enough.
Building from Log Q-Learning (van Seijen et al., 2019), we define the base algorithm as the following: at time t it receives Q̃t(s, a) and a transition tuple (s, a, r, s′) as defined previously, and outputs Q̃t+1(s, a), which then yields Qt+1(s, a) = f−1(Q̃t+1(s, a)). The steps are listed below:
1The convergence follows from stochastic approximation theory with the additional steps to show by induction that Q̃ remains bounded and then the corresponding operator is a contraction mapping.
Qt(s, a) := f −1 ( Q̃t(s, a) ) (6)
ã′ := arg max a′
( Qt(s ′, a′) )
(7) Ut := r + γf −1 ( Q̃t(s ′, ã′) ) (8)
Ût := f −1 ( Q̃t(s, a) ) + βreg,t ( Ut − f−1 ( Q̃t(s, a) )) (9)
Q̃t+1(s, a) := Q̃t(s, a) + βf,t ( f(Ût)− Q̃t(s, a) ) (10)
Here, the mapping f is any function that satisfies Assumptions 1 and 2. Remark that similarly to the Log Q-Learning algorithm, (9) and (10) have decoupled averaging of stochastic update targets from that of different state-actions.

heading: 3 REWARD DECOMPOSITION
text: Reward decomposition can be seen as a generic way to 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; hence, 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 the “monolithic” view of RL. 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-Learning to learn the corresponding Q function of each channel will lead to a non-optimal policy (they showed it through a counter example). Hence, they used a Sarsa-like update with respect to the action that maximizes arbitrator’s value. Laroche et al. (2017) provided a formal analysis of the problem, called attractor phenomenon, and studied a number of variations to Q-Decomposition. In a related topic but with a 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 trains a separate general value function (GVF) based on its own policy and (pseudo) reward function, which can be seen as a decomposition of the original reward in addition to auxiliary ones. van Seijen et al. (2017) built on these ideas and presented an architecture, called 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 sources of independent rewards, 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-sound algorithmic machinery. For example, reward decomposition can enable utilization of a specific mapping that has a limited domain. In the Log Q-Learning algorithm, for example, the log(·) function cannot be directly used on non-positive values. The reward is therefore decomposed such that two utility functions Q̃+ and Q̃− are learned for when the reward is non-negative or negative, respectively. Then the value is given by Q(s, a) = exp(Q̃+(s, a))− exp(Q̃−(s, a)). The learning process of each of Q̃+ and Q̃− bootstraps towards the value of next state with an action which is the arg max of the actual Q, rather than that of Q̃+ and Q̃−.
We generalize this idea to incorporate arbitrary decomposition beyond only two channels. We are particularly interested in the following form of decomposition: Let the reward function be decomposed into L separate channels r(j), j = 1 . . . L, as the following:
rt(st, at, st+1) := L∑ j=1 λjr (j) t (st, at, st+1) (11)
with λj ∈ R. The channel functions r(j) map the original reward into some new space in such a way that their weighted sum recovers the original reward. Clearly, the case of L = 1 and λ1 = 1 would retrieve the normal scenario with no decomposition. In order to provide the update, expanding from Log Q-Learning, we then define Q̃(j) for j = 1 . . . L corresponding to the above reward channels,
and construct the actual value function by the following:
Qt(st, at) := L∑ j=1 λjf −1 j ( Q̃ (j) t (st, at) ) (12)
We explicitly allow the mapping functions, fj’s, to be different. That is, each reward channel can have a different mapping and each Q̃(j) is then learned separately under its own mapping. Before discussing how the algorithm is updated with the new channels, we present a number of interesting examples of how (11) can be deployed.
As the first example, we can recover the original Log Q-Learning reward channels, by considering L = 2, λ1 = +1, λ2 = −1, and the following channels:
r (1) t := { rt if rt ≥ 0 0 otherwise
; r (2) t := { |rt| if rt < 0 0 otherwise
(13)
Note the original reward is retrieved by rt = r (1) t − r (2) t . This decomposition allows for using a mapping with only positive domain, like the logarithmic function. This is an example of using reward decomposition to ensure that values do not cross the domain of f .
In the second example, we consider different magnifications for different sources of reward in the environment so as 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 to the size-range of rewards. To be concrete, let r ∈ [0, 100] and consider the following two configurations for decomposition (can be extended to other ranges).
Configuration 1:
λ1 = 1, λ2 = 10, λ3 = 100
r (1) t := { rt if rt ∈ [0, 1] 0 rt > 1
r (2) t :=  0 if rt ≤ 1 0.1rt if rt ∈ (1, 10] 0 rt > 10
r (3) t := { 0 if rt ≤ 10 0.01rt if rt ∈ (10, 100]
Configuration 2:
λ1 = 1, λ2 = 9, λ3 = 90
r (1) t := { rt if rt ∈ [0, 1] 1 rt > 1
r (2) t :=  0 if rt ≤ 1 (rt − 1)/9 if rt ∈ (1, 10] 1 rt > 10
r (3) t := { 0 if rt ≤ 10 (rt − 10)/90 if rt ∈ (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, since the rewards are distributed over various channels, depending on their size. On the other hands, Configuration 2 keeps each channel to act as if there is a reward clipping at its upper bound, while each channel does not see rewards below its lower bound. As a result, it fully preserves the reward density at the first channel, and presents a better density for higher channels compared to Configuration 1. However, the number of active channels depends on the reward size and can be larger than one. Importantly, the magnitude of all reward channels always remains in [0, 1] in both configurations, which could be a desired property. The final point to be careful about in using these configurations is that the large weight of higher channels significantly amplifies their values; hence, even a small error in higher channels can shadow out the lower ones.
Over and above the cases we presented so far, reward decomposition enables an algorithmic machinery in order to utilize various mappings concurrently as an ensemble. In the simplest case, we note that in equation (11), by construction we can always write
r (j) t (st, at, st+1) = rt(st, at, st+1) and L∑ j=1 λj = 1. (14)
Algorithm 1: Orchestrated Value Mapping. Input: (at time t)
Q̃ (j) t for j = 1 . . . L
st, at, st+1, and rt Output: Q̃(j)t+1 for j = 1 . . . L
Compute r(j) for j = 1 . . . L
begin 1 Qt(st, at) := ∑L j=1 λjf −1 j ( Q̃ (j) t (st, at) ) 2 ãt+1 := arg maxa′ ( Qt(st+1, a ′) )
for j = 1 to L do 3 U
(j) t := r (j) t + γf −1 j
( Q̃
(j) t (st+1, ãt+1) ) 4 Û
(j) t := f −1 j
( Q̃
(j) t (st, at) ) + βreg,t ( U (j) t − f−1j ( Q̃ (j) t (st, at) )) 5 Q̃
(j) t+1(st, at) := Q̃ (j) t (st, at) + βf,t ( fj ( Û (j) t ) − Q̃(j)t (st, at) ) end
end
That is, the channels are merely the original reward with arbitrary weights, which should sum to one. We can then use arbitrary functions fj for different channels and build the value function as presented in equation (12). This construction directly induces an ensemble of arbitrary mappings with different weights, all would learn on the same reward signal. More broadly, this can potentially be combined with any other decomposition schemed, such as the ones we 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.

heading: 4 ORCHESTRATION OF VALUE-MAPPINGS USING DECOMPOSED REWARDS

heading: 4.1 ALGORITHM
text: To have a full orchestration, we next combine value mappings and reward decomposition. We follow the previous steps in equations (6) to (10), but now also accounting for the reward decomposition. The core idea here is to replace (6) with (12) and then compute Q̃(j) for each reward channel in parallel. In practice, these can be implemented as separate Q tables, separate Q networks, or different network heads with a shared torso (the shared neural network may be loosely interpreted as a feature extractor). At time t, the algorithm receives all the channel outputs Q̃(j)t 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. First, the three steps of the for-loop can be computed in parallel for all the L channels (i.e. each of Q table or head). Second, as mentioned previously, the mapping function fj may be different for each channel; however, the discount factor γ and both learning rates βf,t and βreg,t are shared among all the channels and must keep the same. Finally, note also that the action ãt+1, from which all the channels bootstrap, comes from arg maxa′ Qt(st+1, a
′) and not the local value of each channel. This directly implies that each channel-level value Q(j) = f−1(Q̃j) does not solve a channel-level Bellman equation by itself. In other words, Q(j) does not represent any specific semantics 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.

heading: 4.2 CONVERGENCE
text: Let Qt(st, at) be defined by equation (12) and all Q̃ (j) t (st, at) are updated according to the steps of Algorithm 1. We establish convergence of Algorithm 1 by the following theorem.
Theorem 1 Let the reward admit a decomposition as defined by (11), Qt(st, at) be defined by (12), and all Q̃(j)t (st, at) are updated according to the steps of Algorithm 1. Assume further that the following hold:
1. All fj’s hold Assumptions 1 and 2
2. TD error in the regular space (the 2nd term of line 4 in Algorithm 1) is bounded for all j 3. ∑∞ t=0 βf,t · βreg,t =∞
4. ∑∞ t=0(βf,t · βreg,t)2 <∞
5. βf,t · βreg,t → 0 as t→∞
Then Qt(s, a) converges to Q∗t (s, a) with probability one for all state and actions (s, a).
The proof follows basic results from stochastic approximation theory (Jaakkola et al., 1994; Singh et 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 βf,t ·βreg,t 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. We contrast this assumption with the one in the previous proof of Log Q-Learning, which requires βreg to 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 1 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 to the learning rates. To get around this problem, van Seijen et al. (2019) decided to keep βreg,t at a fixed value in their deep RL experiments, contrary to the theory. Our new condition, however, formally allows βreg,t to be set to a constant value as long as βf,t properly decays to zero.
A somehow hidden step in the previous proof of Log Q-Learning is also that the TD error in the regular space, the second term in (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 as well as fj spaces, and ensure boundness of U (j) t − f−1j (Q̃ (j) t ) by proper clipping.
Lastly, 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 proper construction from Algorithm 1.

heading: 4.3 REMARKS
text: TIME-DEPENDENT CHANNELS
The proof of Theorem 1 does not directly involve the channel weights λj . However, changing them will impact Qt, which changes the action ãt+1 in line 2 of Algorithm 1. In the case that λj’s vary with time, if they all converge to their final fixed value soon enough before the learning rates become too small, and if additionally all state-action pairs are still visited frequently enough after λj’s are settled to their final value, then the algorithm should still converge to optimality. Of course this analysis is 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 2 asserts that the derivative of fj 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 a bounded error term, which ultimately converges to zero under the conditions of Theorem 1. However, the bound on this error term (see Lemma 2 in Appendix A) is scaled by δmax = maxj δ(j), with δ(j) being defined as
δ(j) = δ (j) 2 / δ (j) 1 − 1 (15)
where δ(j)1 and δ (j) 2 are defined according to Assumption 2 (0 < δ (j) 1 ≤ |f ′j(x)| ≤ δ (j) 2 ). In the case of fj being a straight line δ(j) = 0; hence, no error is incurred and the algorithm shrinks to Q-Learning. An important extreme case is when δ(j)1 is too small while δ (j) 2 is not close to δ (j) 1 . It then follows from (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 f ′j 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 non-linear approximations. The bottom-line is that the mapping functions should be carefully selected in 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 f(x) = c · log(x+ d) (as investigated in the context of Q-Learning by van Seijen et 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 is a 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) = cx+d . Hence, δ2 = c d , whereas δ1 can be very close to zero depending on the maximum return. As a result, when learning on a task which often faces large returns, Log 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.

heading: 5 EXPERIMENTAL RESULTS
text: 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 x = 1 − d switches from a logarithmic mapping to a straight line with slope c (i.e. the same slope as c · log(x+ d) at x = 1− d):
f(x) := { c · log(x+ d) if x ≤ 1− d c · (x− 1 + d) if x > 1− d
We call the resulting method LogLinDQN, or Logarithmic-Linear DQN. Remark that choosing x = 1−d as the break-point has the benefit of using only a single hyperparameter c 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 (13) for the details), and use the same mapping function for both channels.
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. c = 0.5 and d ≈ 0.02. We test this method in the Atari 2600 games of the Arcade Learning Environment (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 a linear mapping function with slope one. We also include two other major baselines for reference: 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-normalized 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.e. handling dense or sparse reward distributions respectively), thereby enabling it to improve upon the per-game worst of LogDQN and DQN
(top panel) and perform competitively against the per-game best of the two (bottom panel) across a large set of games. Figure 2 shows median and mean human-normalized scores across the suite of 55 Atari 2600 games. Our LogLinDQN agent demonstrates a significant improvement over most baselines 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 advances including distributional learning, prioritized experience replay, and n-step learning.

heading: 6 DISCUSSION
text: In this paper we introduced a convergent class of algorithms based on the composition of two orthogonal foundations: (1) mapping the value function into a different space via arbitrary functions from a 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 easier or more efficient than the original return space. Additionally, the introduced methodology incorporates various versions of ensemble learning in terms of linear decomposition of the reward. We presented a generic proof, which also relaxes certain limitations of 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 the research on numerous special instantiations as future work, following our theoretical foundation.
REPRODUCIBILITY STATEMENT
We release a generic codebase — based on the Dopamine framework (Castro et al., 2018) — with the option of using arbitrary compositions of mapping functions and reward decomposition schemes as easy-to-code modules. This would enable the community to easily explore the design space that our theory opens up and investigate new convergent families of algorithms. This also enables to reproduce the results of this paper through an accompanying configuration script. The codebase will be made publicly available after the review phase.

heading: A PROOF OF THEOREM 1
text: 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 for example, Theorem 1 in Jaakkola et al. (1994) or Lemma 1 in Singh et al. (2000).
Lemma 1 Consider an algorithm of the following form:
∆t+1(x) = (1− αt)∆t(x) + αtUt(x) (16)
with x being the state variable (or vector of variables), and αt and Ut denoting respectively the learning rate and the update at time t. Then, ∆t converges to zero with probability one as t −→∞ under the following assumptions:
1. The state space is finite; 2. ∑ t αt =∞ and ∑ t α 2 t <∞;
3. ||E{Ut(x) | Ft}||W ≤ ξ ||∆t(x)||W , with ξ ∈ (0, 1) and || · ||W denoting a weighted max norm;
4. Var{Ut(x) | Ft} ≤ C (1 + ||∆t(x)||W ) 2, for some constant C.
where Ft is the history of the algorithm until time t.
Remark that in applying Lemma 1, the ∆t process generally represents the difference between a stochastic process of interest and its optimal value (that isQt andQ∗t ), and x represents a proper concatenation of states and actions. In particular, it has been shown that Lemma 1 applies to Q-Learning as the TD update of Q-Learning satisfies assumptions 3 and 4 (Jaakkola et al., 1994).
We define Q(j)t (s, a) := f −1 ( Q̃ (j) t (s, a) ) , for j = 1 . . . L. Hence,
Qt(s, a) = L∑ j=1 λjf −1 j ( Q̃ (j) t (s, a) ) = L∑ j=1 λjQ (j) t (s, a) (17)
We next establish the following key result, which is core to the proof of Theorem 1. The proof is given in the next section.
Lemma 2 Following Algorithm 1, for each channel j ∈ {1, . . . , L} we have
Q (j) t+1(st, at) = Q (j) t (st, at) + βreg,t · βf,t ·
( U
(j) t −Q (j) t (st, at) + e (j) t
) (18)
with the error term satisfying the followings:
1. Bounded by TD error in the regular space with decaying coefficient: |e(j)t | ≤ βreg,t · βf,t · δ(j) · ∣∣∣U (j)t −Q(j)t (st, at)∣∣∣ , (19)
where δ(j) = δ (j) 2
δ (j) 1
− 1 is a positive constant.
2. For a given fj , e (j) t does not change sign for all t (it is either always non-positive or
always non-negative).
3. e(j)t is fully measurable given the variables defined at time t.
From Lemma 2, it follows that for each channel:
Q (j) t+1(st, at) = Q (j) t (st, at) + βreg,t · βf,t
( U
(j) t −Q (j) t (st, at) + e (j) t
) , (20)
with e(j)t converging to zero w.p.1 under condition 4 of the theorem, and U (j) t defined as:
U (j) t := r (j) t + γ Q (j) t (st+1, ãt+1) .
Multiplying both sides of equation 20 by λj and taking the summation, we write L∑ j=1 λjQ (j) t+1(st, at) = L∑ j=1 λjQ (j) t (st, at) + βreg,t · βf,t L∑ j=1 λj ( U (j) t −Q (j) t (st, at) + e (j) t ) Hence, using equation 17 we have Qt+1(st, at) = Qt(st, at) + βreg,t · βf,t L∑ j=1 λj ( U (j) t −Q (j) t (st, at) + e (j) t )
= Qt(st, at) + βreg,t · βf,t L∑ j=1 λj ( r (j) t + γ Q (j) t (st+1, ãt+1)−Q (j) t (st, at) + e (j) t )
= Qt(st, at) + βreg,t · βf,t rt + γ Qt(st+1, ãt+1)−Qt(st, at) + L∑ j=1 λje (j) t  (21)
Definition of ãt+1 deduces that
Qt(st+1, ãt+1) = Qt ( st+1, arg max
a′ Qt(st+1, a
′) ) = max
a′ Qt(st+1, a
′)
Define et = ∑L j=1 λje (j) t ; we rewire equation 21 as the following:
Qt+1(st, at) = Qt(st, at) + βreg,t · βf,t ( rt + γ max
a′ Qt(st+1, a
′)−Qt(st, at) + et )
(22)
This is a noisy Q-Learning algorithm with the noise term decaying to zero with a quadratic rate with respect to the learning rate’s decay; more precisely, in the form of (βreg,t · βf,t)2. Lemma 1 requires the entire update to be properly bounded (as stated in its assumptions 3 and 4). It has been known from the proof of Q-Learning (Jaakkola et al., 1994) that TD error satisfies these conditions, meaning that rt + γ maxa′ Qt(st+1, a′) − Qt(st, at) satisfies assumptions 3 and 4 of Lemma 1.
To prove convergence of mapped Q-Learning, we therefore require to show that |et| also satisfies similar property; hence, not only in the limit it disappears, but also in the course of training, it does not interfere intractably with the learning process. To this end, we next show that as the learning continues, |et| is indeed bounded by a value that can be arbitrary smaller than the TD error. Consequently, as TD error satisfies assumptions 3 and 4 of Lemma 1, so does |et|, and so does sum of the two.
Let δmax = maxj δ(j), with δ(j) defined in Lemma 2. Multiplying both sides of (19) by λj and taking the summation over j, it yields:
|et| = ∣∣∣∣∣∣ L∑ j=1 λje (j) t ∣∣∣∣∣∣ ≤ L∑ j=1 λj |e(j)t |
≤ L∑ j=1 λjβf,tβreg,tδ (j) · ∣∣∣U (j)t −Q(j)t (st, at)∣∣∣ ≤ βf,tβreg,tδmax ·
L∑ j=1 λj ∣∣∣U (j)t −Q(j)t (st, at)∣∣∣ = βf,tβreg,tδmax ·
L∑ j=1 λj ∣∣∣r(j)t + γ Q(j)t (st+1, ãt+1)−Q(j)t (st, at)∣∣∣ (23)
The second line follows from Lemma 2. If TD error in the regular space is bounded, then ∣∣∣r(j)t + γ Q(j)t (st+1, ãt+1)−Q(j)t (st, at)∣∣∣ ≤ K(j)
for some K(j) ≥ 0. Hence, (23) induces:
|et| ≤ βf,tβreg,tδmax · L∑ j=1 λjK (j)
= βf,tβreg,tδmaxK (24)
with K = ∑L j=1 λjK
(j) ≥ 0. As (by assumption) βreg,t · βf,t converges to zero, we conclude that there exists T ≥ 0 such that for all t ≥ T we have
|et| ≤ ξ · ∣∣∣rt + γ max
a′ Qt(st+1, a
′)−Qt(st, at) ∣∣∣ (25)
for any given ξ ∈ (0, 1]. Hence, not only |et| goes to zero w.p.1 as t −→ ∞, but also its magnitude always remains upperbounded below the size of TD update with any arbitrary margin ξ. Since TD update already satisfies assumptions 3 and 4 of Lemma 1, we conclude that with the presence of et those assumptions remain satisfied, at least after reaching some time T where (25) with a sufficiently small ξ′ is guaranteed.
Finally, Lemma 2 also asserts that et is measurable given information at time t, as required by Lemma 1. Invoking Lemma 1, we can now conclude that the iterative process defined by Algorithm 1 converges to Q∗t with probability one.
PROOF OF LEMMA 2
PART 1
Our proof partially builds upon the proof presented in (van Seijen et al., 2019). By definition we have Q̃(j)t (s, a) = f ( Q (j) t (s, a) ) . Hence, we rewrite equations 3, 4, and 5 of Algorithm 1 in terms
of Q(j)t :
U (j) t = r (j) t + γQ (j) t (st+1, ãt+1) (26)
Û (j) t = Q (j) t (st, at) + βreg,t
( U
(j) t −Q (j) t (st, at)
) (27)
f(Q (j) t+1(st, at)) = f(Q (j) t (st, at)) + βf,t
( f(Û
(j) t )− f(Q (j) t (st, at))
) (28)
The first two equations yield
Û (j) t = Q (j) t (st, at) + βreg,t ( r (j) t + γ Q (j) t (st+1, ãt+1)−Q (j) t (st, at) ) (29)
By applying f−1 to both sides of (28), we get:
Q (j) t+1(st, at) = f
−1 ( f(Q
(j) t (st, at)) + βf,t
( f(Û
(j) t )− f(Q (j) t (st, at))
)) , (30)
which can be rewritten as:
Q (j) t+1(st, at) = Q (j) t (st, at) + βf,t
( Û
(j) t −Q (j) t (st, at)
) + e
(j) t , (31)
where e(j)t is the error due to averaging in the mapping space instead of in the regular space:
e (j) t := f
−1 ( f(Q
(j) t (st, at)) + βf,t
( f(Û
(j) t )− f(Q (j) t (st, at)) )) −Q(j)t (st, at)− βf,t ( Û (j) t −Q (j) t (st, at) ) (32)
We next analyze the behavior of e(j)t under the Theorem 1’s assumptions. To simplify, let us introduce the following substitutions:
a → Q(j)t (st, at) b → Û (j)t v → (1− βf,t) a+ βf,t b w̃ → (1− βf,t)f(a) + βf,tf(b) w → f−1(w̃)
The error e(j)t can be written as
e (j) t = f −1((1− βf,t)f(a) + βf,tf(b))− ((1− βf,t)a+ βf,tb ) = f−1(w̃)− v = w − v
We remark that both v and w lie between a and b. Notably e(j)t has a particular structure, which we can use to bound w − v. See Table 1 for the ordering of v and w for different possibilities of f . We define three lines g0(x), g1(x), and g2(x) such that they all pass through the point (a, f(a)). As for their slopes, g0(x) has the derivative f ′(a), and g2(x) has the derivative f ′(b). The function g1(x) passes through point (b, f(b)) as well, giving it derivative (f(a) − f(b))/(a − b). See Fig. 3 for all the possible cases. We can see that no matter if f is semi-convex, or semi-concave, and if it is increasing or decreasing these three lines will sandwich f over the interval [a, b] if b ≥ a, or similarly over [b, a] if a ≥ b. Additionally, it is easy to prove that for all x in the interval of a and b, either of the following holds:
g0(x) ≥ f(x) ≥ g1(x) ≥ g2(x) (33)
or
g0(x) ≤ f(x) ≤ g1(x) ≤ g2(x) (34)
The first one is equivalent with
g−10 (y) ≤ f−1(y) ≤ g −1 1 (y) ≤ g −1 2 (y) (35)
while the second one is equivalent with
g−10 (y) ≥ f−1(y) ≥ g −1 1 (y) ≥ g −1 2 (y) (36)
From the definition of g1 it follow that in all the mentioned possibilities of f combined with either of a ≥ b or b ≥ a, we always have g1(v) = w̃ and g−11 (w̃) = v. Hence, plugging w̃ in equation 35 and equation 36 (and noting that f−1(w̃) = w) deduces
g−10 (w̃) ≤ w ≤ v ≤ g −1 2 (w̃) (37)
or
g−10 (w̃) ≥ w ≥ v ≥ g −1 2 (w̃) (38)
Either way, regardless of various possibilities for f as well as a and b, we conclude that
|e(j)t | = |v − w| ≤ |g−12 (w̃)− g −1 0 (w̃)| (39)
From definition of the lines g0 and g2, we write the line equations as follows
g0(x)− f(a) = f ′(a)(x− a) g2(x)− f(a) = f ′(b)(x− a)
Applying these equations on the points (g−10 (w̃), w̃) and (g −1 2 (w̃), w̃), respectively, it yields
w̃ − f(a) = f ′(a)(g−10 (w̃)− a) w̃ − f(a) = f ′(b)(g−12 (w̃)− a)
which deduce
g−10 (w̃) = w̃ − f(a) f ′(a) + a ; g−12 (w̃) = w̃ − f(a) f ′(b) + a (40)
Plugging the above in equation 39, it follows |e(j)t | = |v − w| ≤ ∣∣∣∣ w̃ − f(a)f ′(b) − w̃ − f(a)f ′(a) ∣∣∣∣ = ∣∣∣∣( 1f ′(b) − 1f ′(a) ) · (w̃ − f(a))
∣∣∣∣ = ∣∣∣∣( 1f ′(b) − 1f ′(a) ) · ( (1− βf,t)f(a) + βf,tf(b)− f(a) )∣∣∣∣
= ∣∣∣∣βf,t( 1f ′(b) − 1f ′(a) )( f(b)− 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 f(b)− f(a) = f ′(c)(b− a). Remark that based on Assumption 2, c would satisfy f ′j(c) ≤ δ (j) 2 , also that 1f ′(b) − 1 f ′(a) ≤ 1
δ (j) 1 − 1 δ (j) 2 . Hence, |e(j)t | ≤ ∣∣∣∣βf,t( 1f ′(b) − 1f ′(a) )( f(b)− f(a) )∣∣∣∣ = ∣∣∣∣βf,t( 1f ′(b) − 1f ′(a) ) f ′(c)(b− a)
∣∣∣∣ ≤ ∣∣∣∣∣βf,t ( 1
δ (j) 1 − 1 δ (j) 2
) · δ(j)2 · (b− a) ∣∣∣∣∣ = ∣∣∣∣∣βf,t ( 1
δ (j) 1 − 1 δ (j) 2
) · δ(j)2 · ( Û (j) t −Q (j) t (st, at) )∣∣∣∣∣ (42) From equation 27, it follows that
Û (j) t −Q (j) t (st, at) = βreg,t
( U
(j) t −Q (j) t (st, at) ) We therefore can write
|e(j)t | ≤ ∣∣∣∣∣βf,t ( 1
δ (j) 1 − 1 δ (j) 2
) · δ(j)2 · ( Û (j) t −Q (j) t (st, at) )∣∣∣∣∣ = ∣∣∣∣∣βf,t ( 1
δ (j) 1 − 1 δ (j) 2
) · δ(j)2 · βreg,t ( U (j) t −Q (j) t (st, at) )∣∣∣∣∣ = βf,t · βreg,t · δ(j) ·
∣∣∣U (j)t −Q(j)t (st, at)∣∣∣ where δ(j) = δ(j)2 ( 1
δ (j) 1 − 1 δ (j) 2 ) is a positive constant. This completes the proof of part 1 of the
Lemma.
PART 2
For part 2, it can be directly seen from Fig. 3 that for a given fj , the order of w′, w, v, and v′ is fixed, regardless of whether a ≥ b or b ≥ a (compare each figure A, B, C, and D, with their counterparts at the bottom). Hence, the sign of e(j)t = w − v will not change for a fixed mapping.
PART 3
Finally, we note that by its definition, e(j)t comprises quantities that are all defined at time t. Hence it is fully measurable at time t, and this completes the proof.

heading: B DISCUSSION ON LOG VERSUS LOGLIN
text: As discussed in Sec. 4.3 (Slope of Mappings), the logarithmic (Log) function suffers from a too-low slope when the return is even moderately large. Figure 4 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 a 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 a 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 two worlds of logarithmic and linear spaces (when the return lies in the respective regions), we should expect it to work best if it is to be used as a generic mapping for various games.

heading: C EXPERIMENTAL DETAILS
text: The human-normalized scores reported in our Atari 2600 experiments are given by the formula (similarly to van Hasselt et al. (2016))
scoreagent − scorerandom scorehuman − scorerandom ,
where scoreagent, scorehuman, and scorerandom are the per-game scores (undiscounted returns) for the given agent, a reference human player, and random agent baseline. We use Table 2 from Wang et al. (2016) to retrieve the human player and random agent scores. The relative human-normalized score of LogLinDQN versus a baseline in each game is given by the formula (similarly to Wang et al. (2016))
scoreLogLinDQN − scorebaseline max(scorebaseline, scorehuman)− scorerandom ,
where scoreLogLinDQN and scorebaseline 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.

heading: D ADDITIONAL RESULTS
text: Figure 5 shows the relative human-normalized score of LogLinDQN versus LogDQN (top panel) and versus (Lin)DQN (bottom panel) for each game, across the suite of 55 Atari 2600 games. LogLinDQN outperforms both LogDQN and (Lin)DQN on several games significantly, and is otherwise on par with them (i.e. when LogLinDQN is outperformed by either of LogDQN or (Lin)DQN, the difference is not by a large margin).
Figure 6 shows the raw (i.e. without human-normalization) learning curves across the suite of 55 Atari 2600 games.

Review summaries:
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. 

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. 

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.