Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes the problem of learning from experience tuples that
omit the action. The authors analyze tabular Q-learning and show that if
the action-space is a refinement, then Q-learning can learn the optimal
value function. Motivated by this, an algorithm is proposed that labels
$(s,s')$ tuples with a discrete action $\hat a$, with Q-learning used
with these imputed actions. The proposed algorithm is shown to surpass
several baselines on grid world, continuous control, freeway (atari),
robotic manipulation and rich visual navigation environments.
main_review: 
Strengths
---------

-   An interesting approach to the problem of learning from action-less
    experience. The three part procedure of estimating latent actions
    with EM, doing Q-learning with the learned actions and using the
    value function on downstream tasks is promising and seems new.

-   The theoretical arguments that underpin the proposed method are
    mostly well thought out. There are some confusing parts, that I
    detail below, but I do think the overall approach is correct and the
    theory cleanly motivates the proposed algorithm.

Weaknesses
----------

-   The significance of the contribution is unclear. This is in part due
    to the obscure nature of the problem (of learning with action-less
    experience), partly because the related work is not well
    contextualized earlier in the paper and partly due to the
    experimental evaluation.

-   The experiments, while somewhat comprehensive, are not particularly
    compelling. The results are mostly evaluated using correlation of
    the learned value function and on downstream tasks, both of which
    makes assessing the overall effectiveness difficult without
    extensive ablation. It is not clear to me that correlation is a good
    performance criterion in this case. Furthermore, the results on
    downstream tasks are mostly inconclusive with overlapping confidence
    intervals.

Detailed Comments
-----------------

-   In Section 1 Paragraph 2, you motivate the method by stating that
    the learned value function can be helpful in many downstream tasks,
    including control. This is true, but the state-value function can be
    learned without actions already. The paragraph does not communicate
    the advantage of learning the action-value function with imputed
    actions instead of the state-value function.

-   Section 1, Paragraph 3 "Thus, the central technical question is how
    to learn a good value function from undirected observation streams."

    Sentences such as the one above should specify "action-value"
    function, because, as I mentioned above, a state-value function can
    be directly learned. This is partially addressed in the rest of
    paragraph 3 and in Section 3, but to say that Q-learning without
    actions is policy evaluation seems incorrect. Q-learning cannot be
    applied without actions, unless you impute the actions. A
    state-value function can still be learned using TD learning, which
    seems like the point that is being made in this paragraph.

-   Section 3, Regarding the choice of 4x - ground truth. Is balancing
    the actions in the larger set important? If one action is repeated
    15 times and the other ground truth actions are only repeated 1
    times, would that make the problem harder? Another more pressing
    issue is if the actions are not a refinement, such as if only two
    latent actions are permitted. This is more relevant in practice,
    where we may not know the right action space apriori.

-   "For downstream decision making, we only care about

the relative ordering of state values."

I don't understand this statement. For downstream tasks the relative
ordering of the action-values is the pertinent quantity, but I don't
think an ordering of state-values is meaningful. Since this is the
primary reason for using spearman's rank correlation, I do not see how
measuring correlation would be a useful measure of success.

-   How is correlation being measured exactly? And is this truly the
    measure of success? If correlation is used to overcome some constant
    bias in the state-values, then this implicitly assumes that the bias
    is uniform across states which may not be the case. Learning
    action-value functions offline leads to many issues in the quality
    of the value predictor which may not manifest itself in the control
    policy (such as divergent action-values for out-of-sample or
    out-of-distribution actions).

-   Ground truth actions are said to be an upper bound on the
    performance of your method, but in Table 1 for Kitchen manipulation
    the proposed method outperforms this upper bound. How is this to be
    interpreted in light of the stability comments in footnote 2? Based
    on footnote 2, it seems like the value function should be constant
    and not change between runs (i.e. shouldn't the correlation should
    be 1?).

-   The results on downstream tasks would benefit from TD0 as a
    baseline. While the value function learned is the value of the
    behavior policy (and not the optimal value function), it could still
    be used for all three settings (densified, embodiment transfer and
    guiding low level controllers).

-   Figure 4: while this does demonstrate improvement in the grid world
    setting, there is no significant difference between the methods in
    the other 2d navigation or freeway. Also, the difference in
    asymptotic performance in gridworld is strange. Shouldn't all
    methods eventually reach the optimal policy?

-   Putting the related work at the end of the paper prevents
    much-needed context for the proposed methods. The introduction does
    a good job of stating what you are doing, but the question of why is
    less clear.

Minor Comments
--------------

-   Page 4 , Line 3: ammounts -\> amounts
summary_of_the_review: 
This is an interesting paper with good ideas, but is held back by an
overall confusing experimental evaluation. The theoretical arguments
that motivate the proposed algorithm are well thought out. The empirical
analysis, however, does not give confidence that the proposed algorithm
is an improvement in the action-less regime. I would like to see an
environment that clearly shows that densified rewards with the proposed
algorithm is superior to densified rewards with a learned value function
via TD0. I also think that the correlation performance criterion needs
to be better justified. I will currently leave my rating at below the
acceptance threshold, but I am open to increasing my score if some of my
concerns are addressed.

Edit: After discussion with the authors, I have increased my score to a 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the problem of learning from an offline batch of data containing only states and rewards (no actions). A theoretical result shows when we can expect to recover the true optimal value function when using a different action space. This motivates the algorithm Latent Action Q-learning (LAQ), which first learns a discrete action space by modeling one-step transitions and then applies Q-learning with the learned action space. Experiments in a variety of settings, including reward-shaping and planning with low-level controllers, validate the effectiveness of the approach. 
main_review: Main points:
- I find the introduction to be well-written  and the motivation for this problem to be compelling. In particular, the idea that the same collected data could be used for different types of agents/embodiments is appealing to me, with potentially many practical use-cases.

- For the theoretical result, I find that the conditions needed to satisfy theorem 3.1 may be too stringent. If I understand correctly, it amounts to assuming that the new action set $\hat{A}$ contains all the actions of the original $A$, with possible duplicates. So, it does not allow other actions in $\hat{A}$ that are different than those already in $A$, which is very restrictive. Essentially, it seems to say that we need to obtain exactly the same actions in $A$.
I would find the theorem to be more meaningful if it allowed other actions in $\hat{A}$ at least, with perhaps a different conclusion. Adding new actions to $\hat{A}$ that are functionally different than those in $A$ may increase the optimal values in the general case, but maybe something more specific can be said under different conditions.
Another possible extension to the theorem would be to prove the necessity of the refinement assumption i.e. something like, if the optimal values in the two MDPs match, then one action space is a refinement of the other.

- The experiments were well done with approppriate baselines being chosen and a reasonable choice of environments. The variety of different evaluations to assess the method was welcome. I appreciated the experiments which tried to directly assess the quality of the learned value functions instead of only indirectly doing so with overall performance numbers. 
- I liked the experiments with changing the embodiments of the agent. I haven't exactly this kind of experiment before and it seems to me that it could be applicable to certain practical scenarios. 
- Planning with low-level controllers was also interesting and did a good job showcasing the strengths of the proposed approach.

Questions and suggestions:
- One aspect that confuses me is that the proposed algorithm is used to learn an action space but afterwards, this new action space is hardly used except to run Q-learning and obtain state-value functions. It seems like there should be an oppportunity to make more use of the learned action space. From an intuitive standpoint, it's not very clear to me why learning an action space is a good approach for action-less data. 

- Following up on the previous point, LAQ obtains a state-value function in the end, which can be used in various ways. LAQ also learns a one-step model as an intermediate step before doing Q-learning with the new actions. Have you considered trying to learn the state-value function directly as an alternate approach? This could be done using value iteration on the state-values with the learned model. 

- Did you try to interpret the learned actions at all? Do they seem to match the base actions or are they completely different?

- Can you clarify what the clustering approaches are? I did not see any explanations about how they are used.

- In Freeway, behaviour cloning seems to be performing the best. Why is that? Also, is there missing a green line extending from it for behaviour cloning + RL?

- In table 1, how exactly is the Spearman correlation computed? Is it calculated using state-value functions on a batch of data? Or is it using state-action value functions? How is the batch of data selected?

- Fig 4 plots are not clear. Is there learning in the actual environment? If that is the case, are batch RL methods used then? 
Are they first used to initialize the method and then continue learning?

- In section 5, the term "state-conditioned purity" is introduced but then it isn't explained in the later sections (only in the appendix). I suggest clarifying this in the main text or moving that entire discussion to the appendix.

- The (theoretical) limitation of LAQ to deterministic MDPs is quite strong. While there's a small discussion included in the text, have you done any experiments trying it out in stochastic MDPs? Perhaps it can do reasonably well anyway.

- I would clarify that the word "refinement" in this paper is defined to be something specific and doesn't have a standard meaning. This isn't clear right now in the abstract or the introduction. I was confused since "refinement" is related to a set being a subset of another in mathematics.
summary_of_the_review: The paper tackles an interesting topic and proposes a simple approach which performs well empirically. I don't think the theoretical result is very strong, but the paper focuses more on the empirical aspects so it's not a major concern. Also, the paper is generally well-written although there are certain areas that require more clarification, which is easily addressed.
Overall, given the thorough experiments and the interesting problem, I'm leaning towards acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the offline reinforcement learning problem based only on trajectories without actions. That is, given a set of experiences of the form $(s_t, r_t, s_{t+1})$, how might a learning algorithm proceed? The paper takes care in motivating the problem, both from a conceptual perspective (we might not know the action interface of an agent), and technically (there is good reason we might have access to such trajectories of experience, and learning seems feasible). Given this setting, the paper's main focus is twofold: First, to establish a simple variant of Q-learning that is well-behaved under this learning problem. This motivates Theorem 3.1/Lemma 3.2, which in turn inform the design of Latent Action Q-Learning (LAQ). Then, the second focus of the paper is on exploring the behavior of LAQ in a variety of domains and settings. The experiments are spread across five distinct environments of different kinds (gridworlds, Atari's Freeway, and so on), and each experiment examines a different characteristic of learning. 
main_review: I found the problem setting to be both technically and conceptually interesting. In addition to its motivation, I found the paper well written and easy to read overall. Ideas are introduced carefully (with the small exception of some details in Lemma 3.2), and I believe this paper will be broadly accessible to the RL community. The two presented theoretical results are quite compelling in their own right, if quite natural in hindsight. Some of the claims made (the paragraph headers in the experimental section) seemed too strong given the data. For instance, in the paragraph "LAQ value functions allow transfer across embodiments", it is stated that "LAQ-densified rewards functions, speed-up learning and consistently guide to higher reward solutions than sparse task rewards, or D3G". Looking at Figure 5, the confidence intervals are large enough that I believe it would be difficult to definitively conclude that orange strictly outperforms purple. I don't believe the overlapping intervals detracts from the paper, but I do believe that the paper would be stronger if such claims were of appropriate strength given the data.

I have no major concerns about the paper, and only one primary question. I include several writing suggestions below. I am not intimately familiar with state-only learning in RL, so unless this idea has already been examined elsewhere in the literature, I believe this paper is ready for publication (pending a few changes suggested below, and any other reservations that other reviewers might have).

**Major Comments/Questions**.
- [Q.1] In the discrete action case, it was unclear to me whether $n$ is known. That is, the number of actions in the true environmental model. This seems important for determining how to perform the latent action inference.
- [C.1] Including the pseudocode for LAQ would benefit the paper a lot.

**Minor Questions**
- Does Lemma 3.2 quantify over stochastic policies, or only deterministic ones? Ah, in looking at the proof in the appendix, it seems that these are necessarily _stochastic policies_. It would be helpful to state this explicitly in the Lemma in the main text.

**Writing Suggestions**
- An extremely minor point, but I consider $(s,a,r,s')$ to be such a canonical ordering that the initial $(s_t, a_t, s_{t+1}, r_t)$ read oddly to me.
- "bellman equation" --> "Bellman equation"
- It would be helpful to define "refinement" formally. So, use a definition block and state it precisely.
- I found the idea of a "fundamental action" to be quite sharp and added a lot of clarity to thinking about the proof. It is not strictly necessary, but if you found a way to make space, it might be nice to include a brief proof sketch for Lemma 3.2 in the main paper that highlights this idea.
- "induce same value in every state" --> "induce the same value in every state
- "in 2 ways." --> "in two ways."
- In the "Experimental Setup" paragraph, we move to using $o$ in place of $s$. I did not quite understand this move, and would suggest sticking with $s$.
- "in 5 representative environments" --> "in five representative environments"

(Appendix)
- "at at most" --> "at most"
- "be a functions which" --> "be functions which"
- I did not quite understand this: "we know a sum over action in each fundamental action", but perhaps changing to the following will help: "we know a sum over fundamental actions"
- A minor point, but many equations in the appendix do not have punctuation. I would recommend adding commas and periods to equations where appropriate.
- In Proof of Theorem 3.1: "First, is the case where" --> "In the first case,"
- This is just personal taste, but I prefer $\neg \exists$ notation to $\not \exists$ (I am referring to Theorem A.1)
summary_of_the_review: This is a clean idea, presented carefully, with interesting theory and well conducted, insightful experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: They address undirected (i.e., the data was not necessarily generated by an optimal agent) offline RL in the case that not actions, but only state transitions plus rewards are observed. They present a theoretical result that motivates their subsequent method for finding the true Q function from just the given data. In experiments, they evaluate the method in common toy environments like gridworld.
main_review: Some comments on motivation, related work, structure, etc.:

Motivation: I think the motivation is somewhat overstating the difficulty of the problem. Isn't it obvious that state-only often helps? I think there are enough common model examples where the action is even fully identifiable from just the current and next state (just think of a double integrator dynamics).

I'm OK wuth havung the extensuve related work section at the end, but at least having a rough idea of existing work in this direction up front would be important, this is missing.

I think the "refinement" is closely related to MDP homomorphisms and commutation of operators etc., but this seems entirely missing in the related work section.

Some comments on definitions, problem formulation etc.:

I'm a bit confused. There seem to be two issues: unobserved action, but "same embodiment", or unobserved actions and even allowing for different embodiments. It may well be that what is correctly addressed is the second case, but it would be helpful to at least discern the two things in the discussion.

The defi of "refinement" seems central so why put this in inline text, not as a Definition? And the inline formulation itself is very hard to parse, I think the second part of the sentence is somewhat incomplete. When continuing reading, it seems like "refinement" is formalized

Where is the value function V defined? This should be done explicitly in sec2.

Regarding Theorem 1:

It would also help to motivate this better -- it seems that this theorem should motivate the subsequent algorithm. Personally, I would have expected a more principled result as the basic theorem in the sense of "to what extent is the true MDP recoverable from just the given data. I think this is somehow implicated by theorem 1, but it may be worth making this more explicit and systematic.
summary_of_the_review: While the problem setting, i.e., state-only offline RL, is realistic and practically relevant (cheaper that classic RL), and the paper does contain some interesting ideas in terms of theory and algorithm, the paper is too premature. The writing sometimes lacks motivations and connections, and the theory, I think, can actually be extended (be made more systematic) already within this paper, this would be a deeper contribution.
review_title: null

Meta-review: The paper proposes a method for learning state value functions from (s,s',r) tuples, founded on the theoretical analysis in MDP setting. The extensive evaluation in several environments shows the benefit of the algorithm.

The consensus among the reviewers, and I concur, that the paper proposes an interesting and novel method. It is cleanly presented, and well-founded. The evaluations across range of environments, including robot manipulation validate the method.

During the rebuttal, the authors provided additional evaluation, added a discussion on the latent MDPs, and made numerous clarification, addressing most / all reviewers' questions.
Decision: Accept (Poster)