Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work work in the setting of MDP with terminal states, and considers a lagrangian relaxation (really a reformulation) on the Q-values. While the fact that LP on V-functions and the occupancy measure LP are equivalent (without function approximation) follows from LP duality, the equivalent Q-value formulation is non-linear; the paper nevertheless shows that for the lagrangian strong duality holds.
main_review: 1. One motivation for this work is to work with Q-functions, rather than V-functions; the latter readily admit LP reformulations as the paper acknowledges. Usually, the advantage of having Q-functions is that one can immediately construct an (implicit) greedy policy out of it. But such an advantage is not specific to Q-functions if one has a simulator (i.e. can take samples from s' ~ s,a). Since creating a simulator on the translation task is straight-forward (dynamics are explicitly known), why is then the translation task a suitable application to demonstrate the efficacy of this approach?
2. It is hard to make a case for the distinction in results for MDP with terminal states vs. the discounted setting. Do the results here specifically make use of this distinction? (Is Theorem 4 a part of this answer?) Theorem 1, for example, essentially follows from B^n (for large enough n) being contractive for MDP with terminal rewards, which I would argue is sufficiently similar to the disocunted case -- the same proof structure goes through. An interesting consideration here would be if only for select policies (vs. all policies currently) was termination guaranteed. 
3. The policy optimization procedure of taking gradients while replacing max_a with some heuristic (like using the behavior policy) is a bit unsatisfactory. Why is such a substitution justified? In general, granted this formulation is non-linear, when is it solvable? From my understanding, this issue is also why Nachum, Dai 2020 take the gradient on the policy evaluation lagrangian (rather than for the optimal one). 
4. Lastly, which, if any, of these results translate when the domain of Q is some restricted class of functions?
summary_of_the_review: I'd be willing to raise my score if the above points are addressed. Otherwise, I feel the paper proves something interesting, but the translation of these ideas into either experiments or downstream theory is lacking.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors consider nonlinear Q-form Lagrangian function and show corresponding strong duality property. The main contributions are 1) the new proof of showing the duality gap as zero from a minmax perspective; 2) the generality of the theory with applications to machine translation tasks. A imitation learning algorithm is proposed as well and it turns out that it works well compared with the existing one.
main_review: The theoretical results to my knowledge is new and would cover some applications. The quality of the presentation of this paper is not good. It is hard to find a clear roadmap to see what are the major contributions. My main concerns about this work are as follows:

1) What are the challenges of showing the strong duality from the linear to nonlinear case.

2) Why does this work focus on the episodic leaning process? Will the strong duality results be applicable to other cases? What are the unique features of ELP so that the strong duality holds?

3) The organization of this paper is quite wired. Why section 5 is before the numerical section? and there is no simulation result to justify the theorem shown in section 5.

4) There is no any convergence analysis of the proposed imitation learning algorithm.

5) Besides algorithm1, is there a general algorithmic framework based on this nonlinear.

6) Numerical results are limited. The ELP example shown in Figure 2 is rather artificial. 
summary_of_the_review: In summary, this work indeed showed some progress regarding the nonlinear Q-function evaluation, but the quality of presenting the significance and challenges of having these results is not enough to be accepted at this stage.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the Q learning in episodic learning from a Lagrangian formulation of the Q-form Bellman optimality equation.   On the theory side, this paper studies the (1) fixed point of the bellman optimality operator when the discounting factor for non-terminal states are 1; (2) strong duality of the considered constrained optimization, i.e., saddle point,  reformulation; and (3)maximin type saddle points.  On the empirical side, this paper studies the efficacy of the minimax imitation learning algorithm for a machine translation application. 
main_review: **strengths**

The theory of episodic RL recently attracted a lot of research interests in the ML community.  This paper complements the theory of episodic RL with interesting new results with good insight. 

The overall presentation of this paper is well organized and follows a concentrated storyline. The authors also conducted well-designed machine translation experiments to demonstrate the usefulness of the derived learning algorithms and provide good insight connecting experiment observation and optimization theory. 



**weaknesses**

(1) The major weakness of this paper is:  It has an implicit assumption/restriction that the reward function of the problem must solely depend on the current state.  In most MDP/RL problems, the reward function should also depend on the action (and possibly the next state.)  This weakness tremendously restricts the usefulness of this paper.

(2) As a paper intending to establish new theories, it occasionally missed important points in some key steps.  Below are a few examples:

(2.1) The constrained optimization reformulation (7) from (4) is abrupt.  (4) is for general MDP while (7) is specifically for episodic learning. I expected the authors to explain how T comes into play. 

(2.2) The complementary slackness argument above (30) seems problematic.  The complementary slackness holds only under optimal (primal, dual) pairs.  Ignoring the MDP context, consider min f(x) s.t., g(x)<=0.  For a general given \lambda,  min f(x) + \lambda g(x) is not necessarily attained with a x such that g(x) = 0.   In the context of (30) to prove strong duality, it does not seem we are assuming any property of the dual variables.
summary_of_the_review: I recommend "6: marginally above the acceptance threshold" by assuming the technical weakness (2) is not flaws of the paper but rather imperfectness of presentation.  However, I strongly suggest the authors conduct certain clarifications in the final version if this paper is accepted.
review_title: null

Meta-review: Although the submission studies an interesting question, many parts are not clear enough and the presentation needs to be improved. I encourage authors to revise the paper accordingly and resubmit in future venues.
Decision: Reject