Skill or Luck? Return Decomposition via Advantage Functions

We thank the reviewer for the constructive feedback, please see our answers below.

It is not clear to me why off-policy corrections are not necessary given that the sequence of rewards was generated by a different policy; it feels like frequency at which the sequences appear must be corrected for.

Related to above, it appears that the only "off-policyness" in Eqn 5 is the -centered constraint. Why is this sufficient for the off-policy correction?

The key observation is that the following equation holds for any trajectory

$G = \sum_{t=0}^\infty \gamma^t (A^\pi(s_t, a_t) + \gamma B^\pi(s_t, a_t, s_{t+1}) + V^\pi(s_0)$.

In other words, this decomposition is invariant to the sampling policy. In contrast, take MC methods as an example, they are based on expectations over trajectories, which is why additional corrections are required when the sampling distribution and the target distribution mismatch.

One problem of the decomposition is that it is not unique for arbitrary $\hat{A}(s,a)$ and $\hat{B}(s,a,s’)$ (to see this, note that we can absorb $A^\pi$ into $\hat{B}$, such that $\hat{A}=0$ and $\hat{B}= B^\pi + A^\pi$ is also a solution). However, once we impose the centering constraints on $\hat{A}$ and $\hat{B}$, the decomposition becomes unique with solutions $A^\pi$ and $B^\pi$. For more details, please see appendix A for the proof.

The decomposition seems related to exogenous and endogenous stochasticity. Is there a way to phrase the current work in that context? I'd also refer the authors to this paper that seems relevant: https://people.csail.mit.edu/hongzi/var-website/content/iclr-19.pdf

The exogenous stochasticity introduced by [1] is mostly concerned with a special class of MDPs (input-driven MDPs) where external inputs may also interact with state variables, causing additional stochasticity. If the external inputs are observable, then the environment reduces to an ordinary MDP. In this case, the external inputs can be seen as actions from nature, and nature's policy can be factorized into two components: the external input and the state transitions. For unobserved external inputs, the problem becomes partially observable (POMDP), which is beyond the scope of the present work.

I am curious if once the advantage function is decomposed into skill and luck, is there a benefit to weighing each component differently? I would suspect that this leads to some bias in the policy ordering, but I am wonder if say the skill related component is too small, it may get overshadowed by the luck component, and the agent may not learn efficiently.

While we have demonstrated that the decomposition can improve value estimation, it is not clear whether it is optimal to optimize the policy based on the estimated advantage function. It is possible that by weighing components differently can lead to biased but lower variance targets for policy optimization.

In the case where the luck component dominates, the problem is inherently difficult, as it means the agent’s actions have little influence on the returns, and the returns are very noisy. This makes it challenging to differentiate between good and bad actions, and additional care may be required.

Related to above, I am curious how off-policy DAE performs as a function of environment stochasticity.

This can depend on several factors, such as whether the transition probabilities are known (see Figure 4 for comparison), or the backup lengths used. In the ideal case where the transition probabilities are known a priori along with infinite backup length, then we can expect similar convergence properties to a constrained linear regression as pointed out in Section 4.1.

In Figure 3 and 4, it is unclear to me why all methods are able to produce similar mean estimates? Of course each is different in terms of their variance, but all are centered around the same mean which is a bit surprising.

We note that these experiments were performed in tabular, and fixed-policy settings. Therefore, all the estimators were proven to converge to the true values of the states in the limit.

What were the number of trials for the Figure 5 results? These should be mentioned.

The results were aggregated over 20 random seeds. We have updated Figure 5 to include this information.

[1] Mao, H., Venkatakrishnan, S. B., Schwarzkopf, M., & Alizadeh, M. (2018). Variance reduction for reinforcement learning in input-driven environments. arXiv preprint arXiv:1807.02264.

Near eq.7: The second term $E[V^\pi(s_{t+1})|s_t, a_t]$. What are the random variables of expectation? If it's $s_{t+1}$, please use another notation to differentiate it from the existing one using $s_{t+1}$

We have updated the equations to explicitly point out the variable being integrated.

The complexity of the method seems very large (15 hours vs. 2 hours, as stated in D.7)

We acknowledge that the computational cost of the proposed method can be significantly larger than other methods. In the present work, we have focused on the correctness of the method, and we will leave it for future work to explore more efficient ways to combine it with other deep RL algorithms.

Why the decomposition of the return could benefit learning? Could the author give more insights into it?

Essentially, the decomposition enables better utilization of trajectories in comparison to MC methods, where only the starting state(-action)s are used. For example, in Figure 3 we can see that the rewards are caused by actions at state 3 for both starting states 1 and 2. However, MC methods ignore this relationship and estimate V(1) and V(2) independently. In contrast, DAE can account for the variance caused by the actions at state 3 through the advantage function, which is then shared between trajectories starting from either states 1 or 2. Off-policy DAE further extends this idea to include variance caused by stochastic transitions, as demonstrated in Figure 4.

What's the probability of the sticky action for stochastic environments?

As the MinAtar suite already includes both deterministic and stochastic environments, we did not use sticky actions in the experiments.

We thank the reviewer for the constructive feedback, please see our answers below.

The introduction is not quite clear. Although it starts with an intuitive example, it doesn't contribute too much to get the idea of the paper.

Section 3 lacks motivation, making it kind of hard to follow.

The lottery example in the introduction serves as an example to demonstrate that the return of a trajectory can be attributed to two sources: (1) actions from the agent (choosing a set of numbers), and (2) stochastic transitions (lottery drawing). Section 3 further develops this idea in a quantitative way by first analyzing deterministic environments and then generalizing to stochastic environments. We have made this connection more explicit at the beginning of Section 3.

For Figure 9, Table 2, Figure 10, 11, 12, are the results in deterministic environments? Are there any results in stochastic environments? I believe this is very important as the evaluation in stochastic environments is the main contribution of the paper.

We note that the MinAtar suite includes both deterministic (Breakout, and Space Invaders) and stochastic (Asterix, Freeway, and Seaquest) environments. As such, the aforementioned figures and table already include results in both deterministic and stochastic environments. These were separately aggregated in Figure 5 for easier visualization.

The authors used very large N (8) for Uncorrected. However, in existing literature, it's known 3 or 5 are the best. Therefore, the comparison is unfair.

We have included new results below for Uncorrected (N={3, 5}):

(the worst N results are from Table 2)

From the table, we see that while decreasing backup lengths may improve the performance of Uncorrected in some of the environments, it still largely underperforms Off-policy DAE. In addition, we would like to point out that it is not conclusive whether N = 3 or 5 is the best for Uncorrected. For example, in [1], the authors found that N = 10 or 20 can significantly outperform N = 5. In [2], it was also found that Uncorrected can achieve competitive performance for N up to 20.

What's the performance of 1-step DQN?

As the aim of the experiments is to compare how different value estimators can impact policy optimization performance in a controlled setting, we have not included other deep RL algorithms as baselines, except for the on-policy PPO-DAE baseline, which serves as a validation that the proposed off-policy method is truly more sample efficient. Consequently, we believe the lack of 1-step DQN baseline does not invalidate our findings.

The paper doesn't compare to other state-of-the-art multi-step off-policy method, such as Retrace

In the present work, we have only compared to Tree Backup as it is similar to Off-policy DAE in that, it also does not impose any constraint (aside from coverage of state-actions), or even need any knowledge about the behavior policy. In contrast, importance-sampling based methods (e.g., Retrace) require the behavior policy to compute the likelihood ratio, and often assumes the behavior policy to be Markovian, which we do not assume.

The below claim is exaggerated. I didn't find a theorem that clearly proves the properties of faster convergence.

We demonstrate that (Off-policy) DAE can be seen as generalizations of Monte-Carlo (MC) methods that utilize sample trajectories more efficiently to achieve faster convergence.

We have removed “to achieve faster convergence” from the sentence. However, we would like to note that the toy experiments in section 4 were meant as empirical evidence that (Off-policy) DAE can achieve faster convergence.

[1] Van Hasselt, H. P., Hessel, M., & Aslanides, J. (2019). When to use parametric models in reinforcement learning?. Advances in Neural Information Processing Systems, 32.

[2] Hernandez-Garcia, J. F., & Sutton, R. S. (2019). Understanding multi-step deep reinforcement learning: A systematic study of the DQN target. arXiv preprint arXiv:1901.07510.

Thanks for the response of the authors. And I'm happy to see the authors corrected some typos in the paper. Below are some further concerns.

We note that the MinAtar suite includes both deterministic (Breakout, and Space Invaders) and stochastic (Asterix, Freeway, and Seaquest) environments. As such, the aforementioned figures and table already include results in both deterministic and stochastic environments. These were separately aggregated in Figure 5 for easier visualization.

Then, Figure 5 is misleading. The paper never clearly stated that the deterministic environments are referred to as "Breakout, and Space Invaders", and stochastic environments refer to as "Asterix, Freeway, and Seaquest". I thought they referred to using sticky action prob=0 and stick action prob=0.1 at the beginning.

Minor Comments: In Breakout, the starting direction of the ball is also random. It's hard to say it's deterministic.

As the MinAtar suite already includes both deterministic and stochastic environments, we did not use sticky actions in the experiments.

I believe that evaluating the methods under larger stochasticity is necessary because this is the major contribution of the method. This implies that using a non-zero sticky action prob is necessary for this paper. First, the original stochasticity is not enough. Second, the zero sticky action prob is usually not convincing to test the behavior of the algorithm. See below for the statements in the MinAtar paper.

“This deterministic behavior can be exploited by simply repeating specific sequences of actions, rather than learning policies that generalize. Machado et al. (2017) address this by adding sticky-actions, where the environment repeats the last action with a probability 0.25 instead of executing the agent’s current action. We incorporate sticky-actions in MinAtar, but with a smaller probability of 0.1. ”

Due to the efficiency and simplicity of MinAtar compared to classic Atari environments, I would expect the author not to reduce the difficulty of the benchmark and evaluate the methods with sufficient stochasticity.

We have included new results below for Uncorrected (N={3, 5}):

As far as I know, Uncorrected DQN can perform quite well on Freeway and get a score of 60 even with N=3 (even under sticky action prob=0.1). I'm curious what happened to the 3-step Uncorred method here. What's the result of 1-step method?

We thank the reviewer for the positive feedback, please see our answer to your question below.

Can the method be directly applied to offline RL, and if so, what additional challenges might arise in that context?

One major challenge of offline RL lies in distribution shifts between target policies and behavior policies, causing agents to drift into less visited states in the dataset, where value estimates may be unreliable[1]. Previously, this was mitigated by using conservative/uncertainty estimation of the value functions [2, 3]. While in principle, the proposed method can also be applied to offline RL problems, we expect similar difficulties to arise. As such, an important question is how we can extend previous approaches to the proposed method.

[1] Levine, S., Kumar, A., Tucker, G., & Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643.

[2] Kumar, A., Zhou, A., Tucker, G., & Levine, S. (2020). Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33, 1179-1191.

[3] Ghasemipour, K., Gu, S. S., & Nachum, O. (2022). Why so pessimistic? estimating uncertainties for offline rl through ensembles, and why their independence matters. Advances in Neural Information Processing Systems, 35, 18267-18281.

We thank the reviewer for the constructive feedback, please see our answers below.

Off-policy DAE requires an additional neural network to estimate the transition distribution. This seems slightly unelegant since actor-critic algorithms are usually model-free. Is it possible to avoid this by converting the constraint into a loss function instead? i.e. optimize the Lagrangian of the constraint with SGD? Perhaps we would have to use an approximate loss here to make it tractable.

This is indeed possible, and, in fact, conditional moment constraints is an active area of research in other domains such as econometrics and causal inference (e.g., [1], and [2] for its relationship to RL), where various methods have been developed to enforce such constraints. In the present work, however, we opt for the conceptually simpler approach by learning the transition probabilities, and leave it for future work to explore other more efficient possibilities.

If we do learn a model to estimate $B^\pi$, is it possible to adapt the algorithm so the model is sampled-based only? Requiring a sum over all discrete latent states seems a bit restrictive in the choice of model and it seems to prevent easy scaling of the model size.

While we have not tried a sampling-based approach to estimate $B^\pi$, we do believe that approximating the sum (or integration) over the latent variables by Monte-Carlo methods is also a feasible approach. This may be especially useful in continuous control domains where the state transitions are better characterized by continuous distributions (e.g., robotics tasks).

Could you clarify how equation (10) reduces to the policy improvement lemma? In particular, what happens to the $B^\pi_t$ term?

Firstly, we note that $B^\pi$ satisfies the centering property of the advantage function, i.e., $\mathbb{E}\_{s'}[B^\pi(s,a,s')|s,a]=\sum_{s’}B^\pi(s,a,s’)p(s'|s,a)=0$. This means that in expectation, all the $B^\pi_t$ terms vanish, leaving only the $G$, $A$, and $V$ terms, resulting in $V^\mu(s) = \mathbb{E}\_\mu[G|s_0=s] = \mathbb{E}\_\mu[\sum_{t=0}^\infty \gamma^t (A^\pi_t + \gamma B^\pi_t) + V^\pi(s_0)|s_0=s] = \mathbb{E}\_\mu[\sum_{t=0}^\infty \gamma^t A^\pi_t|s_0=s] + V^\pi(s)$.

Why was Tree Backup chosen as the baseline? It seems like a less popular or effective choice compared to, say, Retrace [1] or its successors.

Tree Backup was chosen as the baseline as it is similar to Off-policy DAE in that, it also does not impose any constraint (aside from coverage of state-actions), or even need any knowledge about the behavior policy. In contrast, importance-sampling based methods (e.g., Retrace) require the behavior policy to compute the likelihood ratio, and often assumes the behavior policy to be Markovian, which we do not assume.

It could be interesting to try to incorporate off-policy DAE with model-based RL methods since those algorithms would already have a learned model to use. E.g. Dreamer-v3

This is certainly an interesting direction, and we believe that existing model-based methods can benefit from the proposed approach to improve off-policy critic training. We will leave this for future work to explore the optimal way to combine Off-policy DAE and model-based methods.

To improve the clarity of the notation, I would suggest using capital letters for the random variables. In certain places, the lowercase letters are used to denote both fixed values and random ones. E.g. below equation (7), in the definition of in the expectation should be uppercase.

We avoided using capital letters for the random variables because we were worried that it might lead to confusion between the advantage function and actions. As a remedy, we have updated the equations by explicitly pointing out the variable that is being integrated.

[1] Kremer, H., Zhu, J. J., Muandet, K., & Schölkopf, B. (2022, June). Functional generalized empirical likelihood estimation for conditional moment restrictions. In International Conference on Machine Learning (pp. 11665-11682). PMLR.

[2] Chen, Y., Xu, L., Gulcehre, C., Paine, T. L., Gretton, A., De Freitas, N., & Doucet, A. (2022). On instrumental variable regression for deep offline policy evaluation. The Journal of Machine Learning Research, 23(1), 13635-13674.