Efficient Value Propagation with the Compositional Optimality Equation

We thank the reviewer for their valuable feedback and suggestions. We are glad that the reviewer found our idea interesting.

Answers:

The COE-VI algorithm is heavily restricted to the deterministic shortest path setting.

We note that the deterministic setting is primarily a consideration for our theoretical analysis (see our general response for further details). We believe that our approach could provide empirical sample-efficiency gains even in stochastic environments. Our experiments in the continuous gridworld show that our approach can handle noisy transitions in practice.

The claim that COE-VI improves the convergence rate exponentially over standard value iteration could be superficial. If I inferred correctly from Section 4.2.1, the improvement is about the number of rounds that the value function is updated, which is not a standard metric for RL algorithms. In fact, it is unclear to me whether the sample complexity or even the computation complexity of COE-VI is better than vanilla value iteration because each update in COE-VI takes $O(|S|)$ time where vanilla VI only takes $O(1)$ time (also note that the distance between any two states is upper bounded by the number of states in this setting, and vanilla VI converges in $O(S)$ rounds).

We thank the reviewer for this observation. The COE update indeed requires computing the product for all the states, therefore increasing its computational complexity in the sequential setting by $O(|S|)$. We are interested in the number of updates. One can argue that the update can be easily parallelized, reducing the update cost to $O(\log |S|)$. In practice, however, that could be hard. We focused on the number of updates because our main goal was developing a well-motivated theory for the deep RL case. In this sense, the generator can be seen as an approximation of the subgoal selection from COE-VI, and the generator, of course, has cost $O(1)$.

We thank the reviewer for the valuable feedback and suggestions. We are glad the reviewer found our paper well-written and our results convincing.

Regarding our contributions, we consider the scalability of our approach to continuous deep RL scenarios as the most important component motivated by our theoretical analysis of COE in deterministic settings.

We thank the reviewer for suggesting the connection to the previously proposed Floyd-Warshall Reinforcement Learning. It indeed uses the same decomposition as ours. In future resubmissions, we will revise the paper to clearly highlight our contributions beyond the FWRL and emphasize generalization in deep RL. We have also submitted a new revision addressing the other concerns of reviewers and kindly request feedback on that.

Answers to the question:

COE converges faster, but the update is also more expensive to compute as it requires an extra loop over all states to compute the optimal subgoal. So it is as expensive as running value iteration for |S| additional times. Given an equivalent computational budget would this mean that both standard Bellman updates and COE solve the shortest path problem?

We thank the reviewer for raising this important issue.

Our main focus was the number of updates, as in the end, in our deep RL implementation, we will use an approximation of the update by using a generator. It is true that COE-VI in absolute terms, requires |S| more computations per update. However, some points still make COE favorable. These product computations can be very easily parallelized in contrast to sequentially applying Value Iteration. Of course, it can be hard to fit the entire state space into the memory. This is why we explicitly wrote Generalized Compositional Value Iteration, and not just COE-VI. It is up to the algorithm designer to select appropriate candidates for the intermediate state. Selecting an intermediate state from the set of neighboring states is equivalent to the Bellman update. Selecting it from all possible states gives COE-VI. There are also other choices. For example, one can choose the best state from all states in some neighbors, or have a separate estimator of the best possible state, which gives constant computation time with the possibility of having good interim states at the cost of the additional variance. This is the method we used to generalize to Deep RL.

We will include a discussion related to the additional cost of COE in the updated version of the paper.

We thank the reviewer for the detailed review, suggestions for improving textual clarity, and references to important related work. The feedback helps us improve the paper and understand a reader's point of view.

Answers to the questions:

Q1. Can you elaborate whether there is a single goal state or not?

Every episode has a single goal, but the goals can differ across episodes. We assume that the transition function doesn’t change the goal to treat the (state, goal) pair as an extended state and utilize the previously introduced definitions. Therefore, it is possible to view V(s,g) = V(s, subg)V(subg, g) as the decomposition of one episode into two subepisodes and using the combined reward.

Q2. Why is this suggested procedure not just a multi-step update to the Bellman equation? It seems that this should be true with the caveat that the step number differs by state. What differentiates it here?

This is an important question, and we thank the reviewer for raising this point. Multi-step updates also aim to have more equidistant updates in relation to the state and the goal. However, they rely on Monte-Carlo rollouts, and as a consequence, they are prone to high variance, as shown in past work [1,2,3]. Here, we propose an alternative approach to bootstrapping instead of Monte Carlo rollouts (in the form of a product of two value estimates), which tend to produce lower variance estimates. We will emphasize this in the introduction and related work.

Q3. Section 5.3 states that a solution to the COE equation is $0$ . However, on page 6 the text says that values cannot decrease. Given that values can easily be initialized to be greater than $0$.

Values cannot decrease for the tabular case, where we take maximum over all possible subgoals. Section 5.3 addresses generalization to the Deep-RL scenario, where we use a subgoal generator instead of having maximum over subgoals. Therefore, the value can decrease. Moreover, note that the reason why tabular COE-VI cannot decrease is the initialization of transitions to be 1 and $\gamma$ (lines 2-4) of Algorithm 1. This initialization assures that the algorithm can always choose at least the Bellman or the “null” decomposition, which keeps the value constant. Grounding update imitates this initialization for deep RL by updating the values of transitioning states to be $\gamma$.

Q4. It also seems that since the update equation is multiplicative and all values are initialized to some value $v \leq 1$, a value can never be larger than $1$. However, if I imagine an MDP with a single state absorbing state that is also the goal, the reward in that state would be $\gamma$ by definition. The maximum value I can obtain can clearly be larger than $1$. Can you explain where my logic is flawed?

We are missing the assumption that every goal state is also a terminal state. We thank the reviewer for pointing it out.

Q5. In fact, unless I am missing something, values will always approach $\gamma$ because the largest value product will always be $1 \star \gamma$. Why is this not the case?

As Above

Q6. In section 5.4, why would Q(s, a, s’) always be equal to $\gamma$? Same equation, I am not sure what “$Q_{Bellman}$” means? The Q-function should be defined according to section 3.

6. This is because we assume in section 5.4 that the Grounding Update is well-fitted, so that $Q(s, a, s')$ is close to $\gamma$: $(Q(s, a, s’) \approx \gamma$. There was a typo here. We thank the reviewer for pointing it out. In practice, Q(s, a, s’) will not be exactly $\gamma$, so this equation is approximate. We changed the equality to $\approx$ in the new revision for clarity.

Q7. If value iteration is a special case of the algorithm you propose, how can your algorithm be significantly faster?

7. Value Iteration is a special case of Generalized Compositional Value Iteration with the function ProduceSubgoal producing the next transition state. However, COE-Value Iteration is also a special case of Generalized Compositional Value iteration, so they don’t share this relation. We will make the statements more clear.

Q8. In the second part of the proof, it states something like “From our assumption $V_{k-1}(s, subg) = V^*(s, subg), V_{k-1}(subg, g) = V^*(subg, g).$" Why can we assume that these are optimal?

This is a part of the inductive assumption for the $k$th step.

Q9. The update equation in line 9 of the algorithm is missing what is being updated.

It’s true, $V_2(s, g)$ is being updated. We thank the reviewer for pointing it out.

For the next revision, we also corrected the typos and unclear definitions mentioned by the reviewer.

[1] - Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting

[2] - Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling

[3] - Anna Harutyunyan, Marc G Bellemare, Tom Stepleton, and Remi Munos. Q (λ) with off-policy corrections.

We thank the reviewer for their valuable feedback and suggestions. We are somewhat surprised by the reviewer's comments about the paper being "unreadable," especially since other reviewers (Reviewer jWih and Reviewer EvmW) consider the writing and structure of the paper to be one of its strengths. It is possible that typos and slight inconsistencies in the formal definitions might have caused difficulties. We have fixed them in the new revision and kindly invite the reviewer to read our revised submission.

Regarding the assumption about deterministic settings, as mentioned in our general response, the deterministic setting is primarily a consideration for our theoretical analysis. We believe that our approach could provide sample-efficiency gains even in stochastic environments. Our experiments in the continuous gridworld show that our approach can handle noisy transitions in practice.

Answers to questions:

We thank the reviewer for pointing out the typos in the background. We have fixed them in the revised version.

On Page 4, $V^\pi(s, g)$ is never defined. Previously, $V(.)$ was just defined as a function of only $s$. Because of this, I totally got lost when encountering formulations involving $V(s, g)$. For instance, the equation above Lemma 1 is nonsense to me.

$V(s, g)$ is defined implicitly by the last paragraph of the background, which states that in goal-conditioned RL $\mathcal{S} = \mathcal{S}_s \times \mathcal{S}_g$ and since $V: \mathcal{S} \rightarrow \mathbf{R}$ it directly becomes $V: \mathcal{S}_s \times \mathcal{S}_g \rightarrow \mathbf{R}$. This, however, was causing a bit of confusion also in other reviews, so we have clarified this in our updated version.

First line of Page 5: $d_\pi(s,g)$ is defined as the distance between $s$ and $g$, but in terms of what? Why is $d_\pi(s, g)=|T_\pi(s,g)| - 1$?

$d_\pi(s, g)=|T_\pi(s,g)| - 1$, because that's the formal definition of $d_\pi(s, g)$. The note about the distance is to make the definition more accessible. This quantity represents the number of steps policy $\pi$ has to execute to reach $g$ from $s$. We have clarified this bit in the new revision.

In the fourth line of Page 5, why is $V^\pi(s, g) = E[\gamma^{d_pi(s,g)}]$? Where does this come from? Since I got lost, I do not understand the subsequent results, so I'm not able to validate them

We thank the reviewer for the comment. We have attempted to clarify this in the new revision. To reiterate it here, this is a direct application of the definition of value function combined with the assumption about the reward from the environment and the definition of $d_\pi(s,g)$.

We hope that our response and updated version clarify the aspects needed to evaluate our work.

I thank the authors for the clarifications. I also noticed some updates in the paper, which make the paper easier to read.

Some issues still remain. For instance, the deterministic setting and the limitation of the current experiments, which are only based on two simple gridworlds.

I increased my score. I think the paper is still not ready for publication.