Reward Centering

• Regarding organization of ideas in the paper

We tried a new way to convey the main ideas in a clear and concise way. There is indeed scope of improvement. As you also noted, the content is all there, some restructuring could help.

In particular, we started with the plots at the beginning of the paper to remind the readers of a widely prevalent problem faced by RL practitioners that using large discount factors is problematic. Eventually we described the problem setting and the main related works, but we agree those sections can be more explicit. We will try to simplify the presentation for readers to better contextualize the problem and assess the solution.

We also agree the background should contain a definition of a Blackwell-optimal policy if we use the term in the paper. At the same time, we can note that it is okay if the reader does not understand the specifics of the mathematical formulation; the implication of Blackwell’s result is more important for the paper (stated and cited at the end of page 2).

• Regarding the choice of plots in the main text vs the appendix

We performed numerous experiments to test our hypotheses. Given the page limits of the main text, we had to select a limited number of plots that provide a clear idea of the overall trends, and added the rest of the plots in the appendix for the more interested readers. For example, our experiments show that Centered Q-learning is robust to the choice of its parameter eta. We presented the plots for one domain in the main text (Fig 3), said the trend is repeated across the other four domains, and presented those plots in Appendix C.

That being said, are there specific plots that you would suggest are more appropriate to show in the main text?

Thank you again for taking the time to review this paper.

I thank the authors for their response and the clarifications.

My main concerns on the difficulty of the domains considered remain. Although these more simple experiments in which more runs are affordable are appreciated, I would also like to see whether these claims extend to more complex environments. I agree with the authors that it is reasonable to expect the results in these more intricated benchmarks to show similar trends; however, I retain that "being confident about this" is actually not enough for a paper of an empirical nature.

I will take into account any eventual and additional experiments into consideration for the discussion phase. In the eventual case in which the work is rejected, I invite the authors to expand their experimental campaign for future revisions of this manuscript.

I have no further questions for the authors.

Best regards,
Reviewer Kzst

1. I would ask the authors whether they expect their empirical results to hold in more intricated benchmarks (e.g., some Atari domain, for instance). Have the authors experimented with these more complex domains (or other domains of similar complexity)?

We expect the observed trends to hold across domains and function approximators. The reward-centering idea is very general; the motivation (removal of the need to estimate a large state-independent offset) applies across tabular, linear, and non-linear function approximations. In this first presentation of the idea, we thoroughly tested the idea on relatively simple domains by testing performance and sensitivity-to-hyperparameters up to 50 times per experiment configuration. The resulting trends are clear across the three types of function approximations. Such systematic experiments are hard to perform on Atari-scale domains (where 3–5 runs are hence typical), but given enough compute we are confident in observing similar benefits. Continuing versions of MinAtar domains are a reasonable step up in complexity. We will try to report some results in the rebuttal period after first converting one or more of the appropriate episodic domains of MinAtar to continuing.

2. It seems to me that if, we take the arg max w.r.t. this Q-function, we obtain an optimal policy for the original discounted MDP with discount factor gamma. First of all, I ask the authors if they confirm this claim. Secondly, I invite the authors to discuss it in the main paper.

Indeed, reward centering does not change the ordering of the policies in continuing problems, so the argmax policy w.r.t. the centered value function is the same as argmax policy w.r.t. the original uncentered value function. In other words, reward centering does not change the final solution but makes it easy to learn by reducing the effect of the potentially large state-independent offset in the original value function. While we mention this in the paper, we can certainly make it more prominent. Thank you for pointing this out.

3. I do not truly understand the role of $\bar{r}$ within the Theorem. As it is defined, it seems to be a free variable in a certain solution space, which makes the interpretation of Theorem 1 a bit cryptical. Could the authors discuss on this point?

$\bar{r}$ is indeed a free variable in a solution space, and for every solution in the $\bar{r}$ space, there is a corresponding solution in the value space. The ideal fixed point is the average reward of the target policy because at that point the offset is completely removed. Centered Q-learning shows one way among other possibilities in which the idea of reward centering can be combined with Q-learning. Theorem 1 says that Centered Q-learning converges to a unique tuple in the joint $\bar{r}$-values solution space. The discussion in Appendix B after the theorem proof quantifies the quality of the learned solution for the values. The quality of the corresponding $\bar{r}$ solution then follows, but we can explicitly add it to improve clarity. We hope this discussion helps with the interpretation of Theorem 1.

Thank you for taking the time to review this paper. This discussion will help in improving the paper; we hope it helps in answering your questions as well.

• Reward centering is compatible with advantage estimation, which solves a different problem

Reward centering and the advantage function have orthogonal benefits: the advantage function benefits the actor by reducing the variance of the updates in the policy space; reward centering benefits the critic estimation by eliminating the need to estimate the large state-independent constant offset. Note that the advantage function remains unchanged with the centered value function: $\bar{a}\_\pi^\gamma(s,a) = \bar{q}\_\pi^\gamma(s,a) - \bar{v}\_\pi^\gamma(s)$, as $\bar{q}\_\pi^\gamma(s,a) = q\_\pi^\gamma(s,a) - r(\pi)/(1-\gamma)$ and $\bar{v}\_\pi^\gamma(s) = v\_\pi^\gamma(s) - r(\pi)/(1-\gamma)$ (using the paper notation). Hence we expect the benefits of reward centering to carry over to policy-based methods. We will add this discussion to the paper.

• The idea of reward centering is also compatible with reward scaling

Scaling or centering the reward with a constant does not change the ordering of policies in a continuing problem. Scaling reduces the spread of the rewards, centering brings them close to zero, both of which can be favorable to complex function approximators such as artificial neural networks that are used for value estimation starting from a close-to-zero initialization. The popular stable_baselines3 repository scales (and clips) the rewards by a running estimate of the variance of the discounted returns (line 256). Mean-centering the rewards as well would be beneficial for continuing domains.

Note that the mechanism of tracking the mean and variance is trickier in the off-policy case than in the on-policy case. We use Wan et al.’s (2021) technique to estimate the mean, which is theoretically sound even in the off-policy case. Naively maintaining a running estimate of the variance introduces a bias (as in the stable_baselines’ approach); Schaul et al.’s (2021) technique is a good starting point. (both citations are in the paper)

• Reward centering is a kind of reward shaping

We realized this relation after submitting the paper: reward centering can be seen as reward shaping with a constant state-independent potential function: $\Phi(s) = r(\pi)/(1-\gamma) \forall s$. Ng et al.’s (1999) Thm 1 then also says that reward centering does not change the optimal policy of the problem. A common criticism of reward shaping is that fully specifying the shaping function can be tricky, especially for large state spaces. In the case of reward centering this is relatively easy: there is a single constant value to learn and we know how to learn the average reward reliably from data. We will add this discussion to the paper.

• Limitations of the empirical study

We agree that the empirical study is limited in the number/type of domains and with variants of Q-learning. However, we expect the observed trends to hold across domains, function approximators, and with centered versions of other algorithms. As mention in the global comment, in this first presentation of reward centering, we tested the idea on relatively simple domains by testing performance and sensitivity-to-hyperparameters up to 50 times per experiment configuration. The resulting trends are clear across tabular, linear, and non-linear function approximations. Such systematic experiments are hard to perform on Atari-scale domains (where 3–5 runs are hence typical), but given enough compute we are confident in observing similar benefits.

Reward centering can be added to any RL algorithm. We focused on Q-learning/DQN and its centered variants in this paper. We have also tried Sarsa's centered (and deep) variants and found similar improvements; a focused empirical study with centered variants of several common RL algorithms is a ripe avenue of future work.

Smaller points:

• You're right that performance will be clouded by a little exploration when epsilon is fixed with no separate evaluation period. We accepted this tradeoff in the spirit of continual learning, wherein the world could be changing and hence require constant exploration and adaptation. Moreover, the comparison is fair because this choice does not favor any method in particular.
• We apologize for the outdated arXiv reference; we will update to this peer-reviewed reference: Devraj, A., & Meyn, S. (2021). Q-learning with uniformly bounded variance. IEEE Transactions on Automatic Control, 67(11), 5948-5963. We will also add the missing DQN reference.
• Considering r as part of the transition dynamics is fairly common in the RL literature, likely since Sutton & Barto (2018) started using that convention throughout their textbook (see, e.g., eqn 3.20 on page 64 of the book).

Thank you for taking the time to review this paper. We hope this discussion helps answer your questions about it.

• Reward vs reward rate?

‘Reward rate’ denotes the rate at which the reward occurs, or the reward per step. It is used alternatively to ‘average reward’, for instance by Sutton and Barto (2018) (towards the bottom of page 249) or Wan et al. (2021), and also defined just below equation (2) in the submitted paper.

• Update frequency in lines 7,12 in Algo 3?

The weight-update and target-network-update frequency come from the DQN algorithm and not specific to the reward-centering idea. We did not tune them and set them to commonly used values in public implementations of DQN (exact values of all parameters are in Appendix C). So far, there is no exact science behind setting those deep-learning parameters.

• Irreducibility: loose or tight?

The irreducible assumption is tight, not due to theoretical necessity but for ease of presentation. It is common in non-episodic MDP literature. Our assumption builds on Devraj and Meyn's (2020), who use that assumption (Q1 in their paper). It can be relaxed to ‘weakly communicating’ at the cost of specifying convergence separately for recurrent and tranient states.

• $d$ in (17)?

$d$ should be $\mu$, which denotes the probability mass function defined in (12). Thank you for pointing this out.

• Extension of the analysis to function approximation

Our convergence analysis is indeed limited to the tabular case. Unfortunately, that is generally true for most RL algorithms due to our community’s limited understanding of the interaction of RL with complex function approximators, especially with neural networks.

• Comparison with scaling, GAE, etc

Reward centering is a general idea that is compatible with reward scaling and with policy-based methods; it is not a competitor. We didn’t experiment with all the combinations in this first investigation of the idea, but we can definitely make concrete predictions:

(a) Scaling/clipping

Scaling or centering the reward with a constant does not change the ordering of policies in a continuing problem. Scaling reduces the spread of the rewards, centering brings them close to zero, both of which can be favorable to complex function approximators such as artificial neural networks that are used for value estimation starting from a close-to-zero initialization. The popular stable_baselines3 repository scales (and clips) the rewards by a running estimate of the variance of the discounted returns (line 256). Mean-centering the rewards as well would be beneficial for continuing domains. That being said, more work needs to be done to soundly estimate the variance in the off-policy continuing case (stable_baselines’ running estimate introduces a bias). [please see additional discussion about scaling with reviewer ecFz; on shaping with JTzu]

Reward clipping in general changes the problem. Blinding the agent from large rewards can impose a performance ceiling or make problems impossible to solve (see Schaul et al.'s (2021) Sec 4.3 discussion on Atari).

(b) Advantage Estimation

Reward centering and the advantage function have orthogonal benefits: the advantage function benefits the actor by reducing the variance of the updates in the policy space; reward centering benefits the critic estimation by eliminating the need to estimate the large state-independent constant offset. Note that the advantage function remains unchanged with the centered value function: $\bar{a}\_\pi^\gamma(s,a) = \bar{q}\_\pi^\gamma(s,a) - \bar{v}\_\pi^\gamma(s)$, as $\bar{q}\_\pi^\gamma(s,a) = q\_\pi^\gamma(s,a) - r(\pi)/(1-\gamma)$ and $\bar{v}\_\pi^\gamma(s) = v\_\pi^\gamma(s) - r(\pi)/(1-\gamma)$ (using the paper notation). Hence we expect the benefits of reward centering to carry over to policy-based methods.

We will add this discussion to the paper.

• ...lacks cross-comparison...

Could you please explain what you mean by cross comparison in this context?

• ...the proposed method solves reward shifting, but practical examples are needed to illustrate the generality of this issue.

Shifting the rewards of a continuing problem does not change the problem (the ordering of policies remains the same). However, our experiments with multiple domains reveal that common algorithms behave significantly differently when the rewards are shifted. This is undesirable. If the problem doesn’t change, the performance of solution methods shouldn’t change either. So while an RL practitioner doesn’t typically shift the rewards, it is a hidden hyperparameter that affects the speed of learning. We are happy to note the reward-centering idea to solve a different problem of large gamma-dependent offsets also makes methods robust to any shifts in the rewards.

Thank you for taking the time to review this paper. This discussion will help in improving the paper; we hope it helps in answering your questions as well. (all the references are from the paper)

• How does the performance of the proposed Centered Q-learning algorithm compare to other state-of-the-art RL algorithms, such as Proximal Policy Optimization (PPO) or Soft Actor-Critic (SAC)?

Reward centering is a general technique that can be added to any RL algorithm and improve its performance. A more appropriate empirical comparison would be between PPO and Centered PPO; SAC and Centered SAC. We focused on Q-learning/DQN and its centered variants in this paper. We have also tried Sarsa and Deep Sarsa’s centered variants and found similar improvements; an extensive empirical study with centered variants of several common RL algorithms is a ripe avenue of future work!

• Can the reward centering technique be extended to handle episodic problems, where the ordering of policies may change due to reward shifts?

This is a great question and we recognize that a large fraction of the RL community would be interested in a similar simple technique for the episodic setting. We don’t have a concrete answer yet, but have identified a promising direction.

• Are there any potential drawbacks or limitations of the reward centering approach that were not discussed in the paper? For example, could centering the rewards introduce biases or affect the exploration-exploitation trade-off?

There are two potential drawbacks to reward centering. Firstly, reward centering reduces the effectiveness of optimistic initialization that is sometimes used in tabular (and some linear) implementations as an exploration technique. But for the same reason, reward centering also removes the drawbacks of inadvertent pessimistic initialization. The addition of reward centering makes RL algorithms robust to the effects of initialization—good or bad. Note that this discussion is not particularly relevant to non-linear function approximation, where generalization negates most benefits of an optimistic initialization. We allude to this effect in the paper but we can certainly make it more explicit!

Secondly, reward centering introduces an additional step-size parameter ($\eta$) to any algorithm that reward centering is added to. However, our parameter studies show that performance is not particularly sensitive to the value of eta (e.g., Fig 3, or the plots in Appendix C).

An attractive property of reward centering is that it does not introduce a bias because the ordering of the policies in a continuing problem is unchanged when a constant is added to all the rewards.

• The paper suggests that reward centering can be combined with scaling techniques to handle large magnitudes of relative values. Can you provide more details on how this combination might work and its potential benefits?

We haven’t worked out the exact mechanism of combining the two, but we can certainly comment on the potential benefits. Scaling or centering the reward with a constant does not change the ordering of policies in a continuing problem. Scaling reduces the spread of the rewards, centering brings them close to zero, both of which can be favorable to complex function approximators such as artificial neural networks that are used for value estimation starting from a close-to-zero initialization. The popular stable_baselines3 repository scales (and clips) the rewards by a running estimate of the variance of the discounted returns (line 256). Mean-centering the rewards as well would be beneficial.

Note that the mechanism of computing the mean and variance is trickier in the off-policy case than the on-policy case. We use Wan et al.’s (2021) technique to estimate the mean, which is theoretically sound even in the off-policy case. Naively maintaining a running estimate of the variance introduces a bias (as in the stable_baselines’ approach). Schaul et al.’s (2021) technique is a good starting point.

• The paper focuses primarily on the tabular case for the theoretical analysis, and the convergence results may not directly apply to the function approximation case.

Our convergence analysis is indeed limited to the tabular case. Unfortunately, that is generally true for most RL algorithms due to our community’s limited understanding of the interaction of RL with complex function approximators, especially with the prevalent artificial neural networks.

The reward-centering idea is motivated by Blackwell’s Laurent series expansion, which applies to the exact value function and not typically to approximated ones. However, our experiments with tabular, linear, and non-linear function approximation show that the implication of this theoretical result is indeed significant in the approximate empirical settings.

Thank you for taking the time to review this paper. This discussion will help in improving the paper; we hope it helps in answering your questions as well.

We have updated the PDF to address two main concerns and a few small clarifications:

1. We've highlighted that the focus of the paper is not Centered Q-learning but the general reward-centering idea that can be applied to any continuing RL algorithm that estimates values. To this effect, we've added a line to the abstract, a paragraph at the end of Section 2, and a couple of sentences in the concluding section.
2. We've added a discussion on related approaches in the appendix: how reward centering is compatible with (and not a competitor of) reward scaling and advantage estimation, and how it is a form of state-independent shaping.

The smaller clarifications include a discussion of the irreducibility assumption and a note on the quality of the reward-rate estimate. We also updated some references and fixed a couple of typos.

We thank the reviewers for their time in going through our responses. We hope the discussion (and a final look at the updated PDF) has given a clearer idea of the appeal and the benefits of reward centering.