Would I have gotten that reward? Long-term credit assignment by counterfactual contribution analysis

Summary

This paper lays out a goal of addressing a weakness in HCA that HCA can confuse the contributions of actions to reaching a state, increasing the variance of gradient estimation. Instead, the COCOA method proposed in this paper generalizes HCA to use any feature that is predictive of rewards, such as the reward or reward-predicting features. Thus, it allows for selecting an appropriate rewarding outcome to disentangle the contributions of each action from the observed rewards. The paper derives a new unbiased gradient estimator (given the exact hindsight model). Experiments are then conducted to show that when these models are known, they can reduce variance in cases not handled by standard control variates.

Strengths

The biggest strength of this paper is thorough experimentation to illustrate when COCOA reduces variance when the hindsight models are known. The experiments and environment clearly show the COCOA method's impact in the cases: when distractor rewards are encountered during the episode and when the distractor rewards are of the same magnitude as the main reward. These experiments show clear evidence that selecting the appropriate disentangling factor is essential to reducing variance. The experiments to show the SNR as a function of credit assignment distance highlights how each gradient estimator degrades as the episode length and distance between action and rewarding stimulus increases. However, this should be evaluated at longer distances as the slopes and shapes of the curves are difficult to observe in this range.

Weaknesses

The biggest weakness of this paper is that there is no investigation into how accurate the estimates of hindsight models need to be to reduce variance. Past variance reduction techniques for policy gradients have proven useless in practice (Tucker et al. 2018). So it is crucial to understand the practical limitations when developing a new method. The comparison to q critic, when q is known, is odd. Because if q is known, then the natural gradient will be known (Kakade, 2001). It should be made precise what sources of variance these experiments are measuring. The bias can be much higher for COCOA methods than other methods (Figure 3 (D)), and it needs to be clearly discussed since this method is supposed to be unbiased. A more relevant baseline instead of the Advantage method would be the doubly robust control variate for policy gradient methods (Huang and Jiang, 2020). This has a significant variance reduction compared to standard baselines in policy gradient. The comparison would also better highlight the limits of information between the two approaches. The success/failure of an algorithm depends greatly on hyperparameter choices. It needs to be clear how each method's hyperparameters were chosen. Since this paper is trying to argue that COCOA has better sample efficiency, it should be made clear in what exact context this claim is being made. Furthermore, if one wants to say that COCOA has better information utilization through measuring performance, then the hyperparameters for the baseline methods need to be tuned to their absolute maximum. As the paper currently stands, the experiment design is insufficient to make this argument, even if it is likely true. Though not poor, the writing in the paper has room for improvement. One of the best ways for this paper to have a bigger impact is to make it written so that most RL people can easily understand the lessons. So I recommend that the authors spend time revising the writing for a future or camera-ready version of the paper. ___minor comments__ what are the decibel units? This is nonstandard in ML, so it is worth specifying. Table1: In the Advantage method, $v^\pi$ should just be $v$ because the baseline can be any state-dependent function Although common in the ML community $\nabla_\theta$ is a mathematical symbol for a directional derivative. However, it is used in this work as a partial derivative. Further, since the gradient is a function that takes a derivative with respect to all inputs and partial derivates are the quantities of interest, it makes mathematical sense to use mathematical symbols for partial differentiation, not gradients. Line 100: "it has a failure mode of practical importance" —say what this is. Section 3.1 Define reward outcomes first. It is unclear what they mean, making it hard to interpret. It also needs to be made clear when or why one would use different choices of f. Giving a few motivating examples would help here. Line 133: Eq 1. Check the JMLR guidelines for standard practice for referencing equations. It should be just (1) not Eq, and equation blocks should only be numbered if they are referenced. Line 146: missing for all k? Definition 1. Remark on definition 1 to clarify what is needed to satisfy this property in practice. Theorem 1: It is important to remark that the gradient estimator is unbiased only if the counterfactual term is known precisely, which is unlikely in practice. This would be like saying the DDPG is unbiased, which is misleading because it is only true if Q is known. Theorem 4. "equals" should be changed because the expression is not a statement of equality but proportionality. Line 246: "SNR indicates… fewer trajectories…" This is not universally true. It can require an exponential number of trajectories to get a gradient estimate, and lower variance estimates will not help this. REFERENCES Huang, Jiawei, and Nan Jiang. "From importance sampling to doubly robust policy gradient." International Conference on Machine Learning. PMLR, 2020. Kakade, Sham M. "A natural policy gradient." Advances in neural information processing systems 14 (2001). Tucker, George, et al. "The mirage of action-dependent baselines in reinforcement learning." International conference on machine learning. PMLR, 2018.

Questions

From Theorem 3 it wasn't clear if one should expect the same trend to hold in other cases. Would we expect the same ordering of variances in more settings?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors do mention that further work is needed on developing methods to learn the hindsight models so they do acknowledge this limitation. But a pilot study on the same environment is really warranted in this work.

Summary

This paper proposes Counterfactual Contribution Analysis (COCOA), an RL credit assignment approach inspired by the Hindsight Credit Assignment (HCA) family of algorithms. The paper notes that in some instances, the previously proposed State-HCA approach can degrade to as high a variance as REINFORCE due to using the future state for obtaining hindsight weights. Instead of estimating hindsight contributions of actions based on future states (as in State-HCA), this paper introduces the idea of a rewarding outcome which is a function of a future state, action, and reward (s’, a’, r’) tuple. The paper proposes two choices for the rewarding outcome– the reward itself or the reward predictive features of the state-action pair (COCOA-reward and COCOA-feature). The paper provides intuitions on how the COCOA approaches should lead to lower-variance policy gradients compared to State-HCA due to reduced encoding of state information. Experiments in a key-to-door environment shows that the COCOA approaches perform much better than State-HCA, REINFORCE (with and without baseline), and all-actions policy gradient on Q-values.

Strengths

**S1.** Hindsight-based approaches are a promising solution to the credit assignment problem in RL, which is of great interest to the research community. **S2.** While identifying the high-variance failure case of State-HCA may not be a novel contribution (see W2), the proposed solution to use rewards or reward predictive features instead of states is novel. The solution idea is simple, well-motivated with examples (e.g., Figure 2 and text below proposition 2), and fits the HCA family of approaches well. Focusing on features that can be useful for HCA is an interesting direction and opens a way to improve previous HCA approaches. **S3.** The paper is well-written and easy to follow.

Weaknesses

**W1.** The paper's claims would be more accurate with the clarification that HCA refers to the State-HCA algorithm from the HCA paper. The claim that this approach generalizes HCA (e.g., line 103) is inaccurate. HCA generally proposes any function of the future trajectory to estimate contributions, and future states are simply one instance in the proposed family. **W2.** The observation that State-HCA-based approaches can suffer from high-variance or spurious contributions (even in comparison to Monte-Carlo approaches) is not a novel finding, as it has also been noted in previous work [1,2]. Could the authors clarify the similarities and differences to the observation made in the papers above? **W3.** A crucial weakness is that it is hard to judge the applicability of the proposed approach based on evaluation in a single environment (linear key-to-door). While linear key-to-door is a challenging problem from the perspective of credit assignment, an evaluation in Atari games (along the lines of Deep HCA [3]) could be more informative in guiding intuitions of how this approach scales to complex settings. **W4.** The paper also needs to include evaluation against other hindsight baselines, for instance, return-conditioned HCA, which was concretely proposed in the HCA paper. An even more interesting comparison would be to Counterfactual Credit Assignment [4], which learns features for hindsight contribution. Overall, I appreciate the direction the authors took to address the limitation of State-HCA. Should these weaknesses be adequately clarified/addressed, I would happily increase my score. —------------------—------------------—------------------—------------------—------------------ ### References [1] Young, K. (2019). Variance Reduced Advantage Estimation with $\delta$ Hindsight Credit Assignment. arXiv preprint arXiv:1911.08362. [2] Zhang, P., Zhao, L., Liu, G., Bian, J., Huang, M., Qin, T., & Liu, T. Y. (2019). Independence-aware advantage estimation. [3] Alipov, V., Simmons-Edler, R., Putintsev, N., Kalinin, P., & Vetrov, D. (2021). Towards practical credit assignment for deep reinforcement learning. arXiv preprint arXiv:2106.04499. [4] Mesnard, T., Weber, T., Viola, F., Thakoor, S., Saade, A., Harutyunyan, A., ... & Munos, R. (2020). Counterfactual credit assignment in model-free reinforcement learning. arXiv preprint arXiv:2011.09464.

Questions

- In Figure 4, why does the COCOA policy not always collect the treasure before the reward switch? Is it due to an exploratory policy? Furthermore, why does the REINFORCE with baseline (Advantage) get much closer to always collecting the treasure in that period?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

Negative societal impact is not directly applicable. Limitations adequately discussed in the Discussion section.

Summary

This paper introduces COCOA, a new family of hindsight credit assignment methods that build on HCA, which uses hindsight importance weights for the policy gradient estimator to reduce its variance. HCA uses state-conditioned importance weights, i.e., the ratio of $p(a_t|s_t, s_{t+k})$ to $\pi(a_t|s_t)$. COCOA generalizes HCA by replacing $s_{t+k}$ with $u_{t+k} = f(s_{t+k}, a_{t+k}, r_{t+k})$ with a general function $f$. Specifically, the authors suggest using either $f(s, a, r) = r$ or $f(s, a, r) = g(s, a)$ where $g(s, a)$ is a function that can fully determine the reward. These variants lead to a lower variance compared to vanilla HCA by conditioning only on information that is related to the reward function. They evaluate COCOA on synthetic domains, showing that COCOA outperforms HCA with improved credit assignment.

Strengths

- The authors generalize HCA in an important direction, and the theoretical benefits of COCOA are significant and clear. - The paper contains informative discussions about various aspects of hindsight gradient estimators, which provides further insights into hindsight credit assignment in general. - The paper is well-written and easy to follow.

Weaknesses

- The paper lacks discussion regarding return-conditioned HCA. While the authors argue that (state-conditioned) HCA suffers from high variance, the original HCA paper also proposes a return-conditioned variant (Sec 3.2 and Theorem 5 in Appendix B), which can enjoy similar benefits to COCOA. Also, when referring to HCA, the authors only mention its state-conditioned variant throughout the paper. Discussing and comparing with the return-conditioned variant of HCA would be more relevant given its similarity to COCOA-reward. - The novelty of the method is a bit limited, as the original HCA paper also proposes a general version of HCA that is conditioned on any function of the future trajectory (Sec 3 in the HCA paper). Nonetheless, the paper further discusses sufficient conditions of this function to make the policy gradient estimator unbiased. - The experiments are conducted only on toy, synthetic environments. It is questionable how COCOA works in more realistic domains.

Questions

- How is COCOA-reward different from HCA-return? - Given that COCOA-reward shows the lowest variance (Theorem 3), when is COCOA-feature preferred to COCOA-reward? - Is COCOA-reward always *optimal* in terms of variance, meaning that there are no importance sampling-based gradient estimators with lower variance? - What would happen if the reward function is a constant function (e.g., $r(s, a) = 1$) but there are terminal signals? Can COCOA-reward directly handle this MDP (without transforming the MDP -- e.g., by creating an additional absorbing state with a zero reward)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors adequately address the limitations of COCOA in Section 5.

Summary

The paper presents a policy gradient estimator using credit assignment measure on influence of specific actions toward future rewards. The paper offers theoretical analysis on resulting algorithm such as (1) policy gradient estimator is unbiased, (2) variance of the estimator in relation to some existing methods, and so on. The authors also include numerical studies using a simple but specifically designed example to highlight the benefits of the proposed algorithm.

Strengths

1. With some assumptions, the paper provides analytical guarantees on a range of desirable aspects of the algorithm.

Weaknesses

1. Given HCA, contribution seems marginal. 2. Claims are either straightforward or require strong assumptions (quarantees in extreme cases such as Prop 2, Theorem 3) 3. Experiments too simple

Questions

1. Rare but possible that reward-based approach may result in larger variance (e.g., S=(1,2) but r(s,a) \in {-100, 0, 100)). 2. Why did you use only state-conditional HCA? (i.e., not using return-conditional HCA)? 3. In the last paragraph on p.5, it is argued that less informative encodings lead to lower variance. While this is intuitively true, less information also means less learning, which suggests that there should be a trade-off between lower variance and information loss in learning. How would you achieve a good balance?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

None

Summary

The paper introduces a novel credit assignment algorithm for reinforcement learning known as COCOA (Counterfactual Contribution Analysis). The proposed method extends the concept of Hindsight Credit Assignment (HCA) and aims at making the learning process more sample efficient. By leveraging counterfactual reasoning, COCOA measures the contribution of actions upon obtaining subsequent reward, thereby achieving improved credit assignment. The paper provides an extensive theoretical analysis of COCOA while addressing its potential advantages and limitations.

Strengths

- The proposal of a novel approach to credit assignment in RL. - Comprehensive theoretical derivations and analysis that support the argument. - Improvement in policy gradient estimators and progression in long-term credit assignment by distinguishing rewarding outcomes.

Weaknesses

- The absence of empirical comparisons with related methods, particularly RUDDER which is cited in the paper. - Unclear scalability of the proposed method in more complex environments and restricted quality of the inverse dynamics model. - Limited empirical evaluation and ablation studies, i.e. examining the influence of the dynamics model on performance.

Questions

- How does COCOA compare to similar SOTA credit assignment methods? - What is the expected influence of imperfect modelling on the performance of COCOA? - When employing COCOA, what are best practices for modelling action contributions for ‘rewarding outcomes’ and how does this impact the learning process?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

- Uncertain scalability to intricate environments. - Examination on how the choice of the dynamics model impacts COCOA's performance (arguably this is kept open in the discussion section).

Summary

This paper proposes Counterfactual Contribution Analysis (COCOA) to improve credit assignment in the reinforcement learning problem by building upon Hindsight Credit Assignment.

Strengths

This paper is written in a clear manner and allows non-expert audiences to understand its difference and contribution in contrast to previous work.

Weaknesses

I do not feel that I understand enough about this field to critique this paper.

Questions

A space is missing between policy and [15-17] on line 41.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Seems okay to me.

Summary

This paper presents family of algorithms namely Counterfactual Contribution Analysis (COCOA), which is based on measuring contribution of an action by asking counterfactual question. The new measure of contribution performs better than existing methods such as HCA in terms of lower variance. They define rewarding outcome as function of state, action and reward. They compute contribution coefficients which can be used to learn a policy with COCOA policy gradient estimator.

Strengths

1. The authors show that the presented COCOA policy gradient estimator can result in lower variance than existing method such as HCA, which suffers from spurious contributions which can be alleviated by using less informative encodings. 2. The authors demonstrate demonstrate the performance of COCOA compared to standard baselines in key-to-door environment. They further present improvement in sample efficiency due to favorable bias-variance trade off 3. The way COCOA is learning the correct distanglement enables long-term credit assignment better than existing methods.

Weaknesses

Compared to policy gradient methods like REINFORCE and Advantage, the COCOA estimators seem to be very computationally expensive.

Questions

1. Could you please highlight how expensive it is to compute these contribution coefficients. 2. Policy gradient methods have shown great performance in continuous state and continuous action MDPs. How can the coefficients be computed in such a setting? Or the proposed method is limited to tabular setting? 3. In many real world applications, we only have sparse rewards, how does the performance of these estimators vary between dense and sparse reward scenarios?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

-

Updated score

Thank you for your response. The clarifications in the response and inclusion of a new environment (and baselines) address some of my main concerns. Accordingly, I have increased my score from 4 to 6. As mentioned in the review (W3), it would still be beneficial to include a more varied range of environments to understand the behaviour of COCOA, especially when learning the contribution coefficients. I recognise the challenge with the code for Counterfactual Credit Assignment not being available. But perhaps comparing with a simpler re-implementation that directly learns features for hindsight contributions would further improve the paper.

Updated score

I acknowledge the revisions made by the authors. I appreciate the time and effort they have put into addressing the points raised in my initial review. Therefore, I revise my evaluation score to reflect the improvements made.