Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: In this work, the authors studied solving the CMDP problem, in particular to model the constraint propagation using the idea of the backward value functions. Using the time-reversed probability property, they first established Bellman optimality conditions for the backward value function, which accounts for the tail expected return, conditioned on the final state. 
Utilizing  the notion of backward value function, they further use that to model the constraint in the CMDPs, and proposed several safe policy iteration algorithms for both cases with discrete actions and with continuous actions. Experiments show that this method has better constraint guarantees than the state-of-the-art algorithms, such as the Lyapunov approach.

The idea of using backward value functions to model constraints in CMDP is interesting and so far I have not seen it in other places. The algorithms developed with this approach also appear to work reasonably well (especially in constraint guarantees) on benchmark domains such as gridworld and mujoco control tasks. The authors also provide several properties such as consistent feasibility and policy improvement, similar to the Lyapunov method,  and derive several versions of safe policy optimization algorithms. However, I found the intuition of using backward value function rather unclear. Unlike the Lyapunov function, which attempts to estimate a near-optimal "remaining constraint budget" w.r.t. CMDP constraint, what is the motivation behind using the backward value. Does the backward probability have any connections to occupation measures? Without similar motivations it is unclear how close the performance of the policy computed from this backward value approach with that of an optimal CMDP policy. Also unlike the Lyapunov approach in Chow'18, the consistent feasibility  property in this work appears to be more restricted as it is only limited to a slow policy update. Finally the experimental results look promising, but it would be great to also compare with other state-of-the-art results such as Lagrangian method, and conservative policy improvement (such as CPO).
 

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper presents a new approach for solving Constrained MDPs. Because the cost constraint is cumulative, the best action depends on the cumulative cost so far. They address this issue by learning a backward value function of the estimated cumulative cost so far. Their theoretical results show that the same properties for forward value functions hold here for backwards ones. They are then able to use the forward and backward cost estimates to constraint the actions selection, by adding a safety layer to the algorithm. The results show that the method does a better job of meeting safety constraints than the Lyapunov based method.

The backward value function idea is a nice novel way of addressing the cumulative cost constraint problem. 

The paper is clearly written and the results are nice.

The biggest issue with this paper is that too much material has been pushed to the appendix. I think at the least some of the details of the actual implementation with PPO or A2C should be moved into the main text. 

For the empirical results, it would be great to see something about the computation or wall clock time required. Does this method run more quickly than the Lyapunov based method? 
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The paper approaches the CMDP problem, in which one wishes to learn a max return policy subject to trajectory-based constraints.  The paper proposes a technique based on the introduced concept of "backward value functions".  These functions satisfy a sort of Bellman equation.  The paper proposes a safe policy improvement step based on these value functions, with theoretical guarantees on the safety of the resulting policy.  The method is evaluated on gridworlds and mujoco tasks, showing good performance.

The paper provides nice results some intriguing ideas, although after reading I am left with several questions as to the details of the method and its place relative to previous works.

-- How is the backwards value function learned exactly?  Since it relies on a backwards Bellman operator, it seems to necessitate on-policy samples.  Is the function learned in an off-policy fashion somehow?
-- The problem solved by SPI (constraint for each state) seems much more conservative than the constraint at the bottom of page 4 (single constraint based on average over all states). In it current form, the algorithm appears to be overly conservative, to the point that it may converge to a policy very far from optimal.
-- I am confused by the assumption on policies updating "sufficiently slowly".  Why is this needed?  Also, how does this relate to CPO (Achiam, et al.)?  It would appear that the methodology of CPO is more desirable, since it only requires the "sufficiently slow" assumption without the additional backward-value constraints. 
review_title: Official Blind Review #1

Meta-review: The paper considers the setting of constrained MDPs and proposes using backward value functions to keep track of the constraints.

All reviewers agreed that the idea of backward value functions is interesting, but there were a few technical concerns raised, and the reviewers remained unconvinced after the rebuttal. In particular, there were doubts whether the method actually makes sense for the considered problem (the backward VF averaging constraints over all trajectories, instead of only considering the current one), and a concern about insufficient baseline comparisons.

I recommend rejection at this time, but encourage the authors to take the feedback into account, make the paper more crisp, and resubmit to a future venue.
Decision: Reject