Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper explores optimizing a binary undiscounted success measure in RL, identifies the issue with learning in such undiscounted environments where many states have the same value (because the policy has no urgency to do anything), propose a “loop penalty” to fix the issue, and show that the loop penalty enables learning in this setting. The problem that the paper identifies of learning with a binary success measure without discounting is an interesting one, since discounting is a somewhat “hacky” solution and it results in suboptimal behaviors in practice. The presented proofs have some nice arguments why the value issue happens in this setting. The results are positive, although not outstanding, showing modest gains in three domains: grid world, VizDoom, and robot grasping. However, there are some issues with correctness and coverage of related work that I discuss below.

Related work - VICE (Ghosh et al. 2018) is cited but not treated fairly. The “AT” or “ANY” queries seem to consider exactly the issue discussed in this paper and do not require discounting. The solution presented in that paper, which modifies the bootstrapping update, seems a more general solution than the loop penalty presented in this paper.

Termination: the termination condition described is to end the episode on reaching a goal state or on reaching a maximum T. First, it seems that practically for policy optimization with function approximation, if termination is handled correctly in bootstrapping (ie. do not bootstrap for the target value in transitions that are terminal) the maximum T will actually have a similar effect as discounting, which perhaps explains why in Fig 6 the base RL methods still learn with discount = 1. Second, it seems that this finite horizon is not discussed in the proofs - it’s not clear to me that the same issue exists even in tabular MDPs if you use finite-horizon value iteration.
Page 4: V = R + gamma P V, not P R + gamma P V. Then in the same paragraph: what if there are multiple subsets S_e of the state that form an irreducible Markov chain, or there is no such subset with more than 1 element, or the entire MDP is irreducible? (I don’t think this breaks the proof, it should just be clarified “which” subset you choose because currently its ambiguous)

Theorem 3: the indicator phi(s_t) seems like it should be a function of tau as well

“Note that the indicator φ(st) can be implemented with many famous methods for measuring state similarity” - I did not understand this, do you threshold the difference between states in a latent space to get the resulting indicator? If so, how do you choose the threshold, it would seem to be highly dependent on the environment dynamics.
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: ### Paper Summary

This paper proposes an alternative surrogate objective for optimizing success rate in episodic tasks with bounded time horizon. Rather than optimize a discounted 0-1 loss (say with discount factor 0.99), the authors suggest to optimize the undiscounted 0-1 loss where reward is counted only for trajectories that do not contain loops. They call this a loop penalty, and show that it can work in 3 appropriate environments. 

### Review Summary

I like the idea and think it could develop into a good paper. That said, I have a couple technical issues (they should be easy enough to fix), take minor issue with the current presentation (again, this should be easy to fix), and importantly, would want to see this method tested against the the right baselines (easy to fix, but require some work) before I can recommend acceptance. 

### Pros

I like the overall approach and idea of introducing an alternative surrogate task for purposes of optimizing the success rate. If you can show either (1) that this actually leads to easier optimization in practice than the alternative surrogates (discounted reward specification, and also direct optimization (see below)) or (2) that provides certain other advantages to the alternative surrogates, this would make for a good contribution. 

### Cons

The framing here is a little off. You might consider the framing from some other papers (e.g., [1], [2], [3]) that introduce approximate task specifications as a surrogate training objective. My reasoning here is that (1) I think the idea of optimizing success rate is well recognized in the literature, and (2) once you introduce the loop penalty you are no longer optimizing undiscounted return / success rate, but using a surrogate task specification (more on this below). The appropriate baselines here are (1) discounted reward with a properly chosen discount, and (2) direct optimization of the success rate (see below).

The first contribution (introduction of success rate and association of success rate with undiscounted return) is obvious, and could be presented in a much more compact form.  Actually, as presented, I believe the statement and proof of Theorem 1 are incorrect given that in the definition of “success rate” the authors require the agent to be successful with at most T steps. The proof sketch is not a proper sketch, but only the first step. The full proof in the Appendix drops the reference to T at the second step, and the final step (identifying it with the binary undiscounted return) ignored that T < infinity. This might be fixed if the states themselves include the current timestep “t”, but then Figure 2 wouldn’t look like Figure 2 (we would have a different shape for each time step), we would haven’t plauteaux, and the Theorem 2 would be irrelevant. 

I think Equation (7) and Theorem 3 are incorrectly stated. You should be multiplying both the reward and target by phi(s_t), as you are doing, e.g., in Eqs (9), (10). Glancing at the proof, Equation (16) seems correct, so it is just the last “expressing in recursive form” step that is incorrect.

In stochastic environments, Loop Penalty can introduce the same kind of approximation as gamma < 1. E.g., it will favor a policy that produces very long non-loopy trajectories over one that produces short trajectories that are more likely to have loops. So this is actually very similar to using gamma < 1 as the surrogate objective.  I.e., it is a *surrogate* for the true success rate.  So, in your first experiment, for example, you should have a gamma < 1 baseline, e.g., gamma = 0.99. Like the loop penalty, it is also a surrogate objective. In the second experiment, why are you using gamma = 0.7 as the baseline? This discount factor seems unreasonably small, so of course it does poorly. As a rule of thumb, you can use a value for which the effective horizon (1 / (1-gamma)) is approximately the expected trajectory length. E.g., 0.98 for T = 50. 

As long as we are allowing our backup equation to consider the entire trajectory. Why not just directly optimize the success rate: i.e., what this episode successful or not? This seems like it would be almost the same from an implementation perspective and would make for a good additional baseline. 

### References

Here are a few recent papers that modify the task specification / Bellman equation in order to improve the optimization: 

- [1] Van Seijen, Harm, Mehdi Fatemi, and Arash Tavakoli. "Using a logarithmic mapping to enable lower discount factors in reinforcement learning." Advances in Neural Information Processing Systems. 2019.

- [2] De Asis, Kristopher, et al. "Fixed-horizon temporal difference methods for stable reinforcement learning." arXiv preprint arXiv:1909.03906 (2019).

- [3] Tessler, Chen, and Shie Mannor. "Maximizing the Total Reward via Reward Tweaking." arXiv preprint arXiv:2002.03327 (2020).
review_title: Interesting idea that could develop into a good paper

final_score: rating: 3: Clear rejection
review_content: The authors propose a new set-up for reinforcement learning which considers undiscounted episodic returns and introduces a loop-penalty to ensure that all episodes terminate and that the returns are bounded. In the tabular case, the loop-penalty zeros out the reward if a loop is detected in the current episode. For continuous state-spaces, the authors propose to detect loops using methods that estimate state-similarity.

The proposed formulation is relevant as well as novel and creative. While discount factors have been questioned repeatedly in recent years, research looking into alternative formulations remains sparse. The most common formulation for non-discounted reinforcement learning, average-reward RL, suffers from the difficulty of estimating the average reward effectively and alternative formulations could be beneficial; however, the paper is lacking in details when it comes to its experimental set-up as well as the method used for non-tabular methods and the analysis is often trivial. 

I would encourage the authors to spend more time on the practical questions of how to estimate the loop-penalty in non-tabular domains. The positive results on vizdoom as well as a robotics task imply that detecting such loops is possible, but there is no discussion of how this is done, in which cases it can work well and in which cases it is still too difficult. It would also be good if the empirical evaluation would include higher, more realistic discount factors such as 0.9 for robot grasping or 0.99 for VizDoom.

With regards the analysis, I believe that the following is problematic:
* A large part of the analysis focuses on uniformity. The authors first show that the value-function has no unique solution on ergodic states with zero reward and then draw a connection between this and the phenomenon illustrated in Figure 2. My first issue here is that the result is well-known in the average reward scenario of which this is a special case. The claim immediately follows and the proof in the paper is unnecessary. My second issue is that it is unclear how the constant offset that can be applied to the value function relates to the flatness of the value function shown in Figure 2. The constant offset can be applied to non-discounted value functions even when the value function does not exhibit this issue.
* Theorem 3 writes out the value function for RL with loop-penalty. The loop-penalty makes the reward non-markovian, therefore it is unclear what theoretical insights can be gained from this theorem.
* Theorem 1 is proving that the episodic return corresponds to success probability if the reward is 1 for success and 0 otherwise. This is trivial and the proof is overly complicated. I don’t believe a proof for this is necessary.

review_title: Creative and relevant idea, but missing crucial detail.

final_score: rating: 2: Strong rejection
review_content: ------------------------------------------
POST-REBUTTAL COMMENTS

Thanks for your comments.

Re: A2, time augmentation in finite-horizon settings increases the size of the state space you need to keep in memory by at most a factor of 2... But in any case, further discussion of this issue will have to wait until the revision with the additional experiments that you mentioned.

Re: A5, regarding "D" being analogous to "gamma" -- fair enough, but this approach is still a meaningful baseline to compare against.

Regarding the statement "contrary to this, initializing state values pessimistically requires task-specific knowledge", this isn't accurate. In a MAXPROB instance, initializing the the value function at all states to 0 is a problem-independent pessimistic initialization. Of course, task-specific knowledge may help design a better one, but it isn't _necessary_.

In conclusion, as the original review mentioned, I believe that the presented "loop penalty" idea may well have conceptual merit, but I encourage you to think more carefully how you "sell" it, because so far neither the original submission nor the rebuttal present convincing arguments that it is better than the alternatives either theoretically or empirically.

---------------------------------------------------


The paper argues that in many RL settings the expect discounted reward criterion common in RL is less appropriate than undiscounted success rate maximization, which this paper claims to introduce. The paper argues that the two result in different solutions, points out that success rate maximization can result in instability of existing RL approaches due to introducing "uniformity" of state values within state loops, and proposes modified losses for PPO, Monte-Carlo, and Q-learning algorithms that allows them to optimize the success rate more reliably than they are able to using their standard losses.

The paper's motivation is sound: the discounted-reward criterion is indeed conceptually less appropriate than success rate maximization for goal-directed decision-making problems. Unfortunately, however, the paper's claimed contributions in addressing this issue are not novel, and largely flawed:


1) Contrary to the paper's claimed contribution, success rate maximization in MDPs isn't new. Paper [1] introduced this criterion, calling it "MAXPROB", and analyzed it mathematically. Without an official name this criterion was known even before that (see, e.g., [1a]). The analysis in [1] focuses on MDP planning, i.e., assumes known model, but the mathematical properties pointed out there that affect value iteration convergence on these MDPs hold in the RL setting just the same.

2) The submission's claims about the success rate/MAXPROB criterion causing the instability of value iteration based approaches are partly imprecise and partly outright mistaken. In the intro, the paper states, "this expression belongs to undiscounted problems and the convergence of value iteration
often cannot be guaranteed (Xu et al., 2018)". First of all, I couldn't find any such claims in that paper. Second, that paper doesn't deal with *finite-horizon* MDPs, whereas this submission does, and the problem is that in finite-horizon MDPs succcess rate maximization poses no issues for value iteration at all. The reason is that value iteration in finite-horizon MDPs such as those in Section 3.1 essentially operates on time-augmented state space, needs a single backward pass from states with 0 steps-to-go to states with T steps-to-go in order to compute the optimal value function, and its convergence doesn't depend on the properties of the reward function.
Note that Section 3.2.C and Figure 3 that it refers to doesn't talk about value iteration's convergence difficulties during success rate maximization in finite-horizon MDPs from Section 3.1 anymore. It just states in a hand-wavy way that there are some difficulties with this criterion, but doesn't explain exactly what they are.

3) The concept of uniformity, as flawed as it is for finite-horizon MDPs defined in Section 3.1, is actually not novel and is subsumed by previously published analysis, again from paper [1]. [1] analyzes the success rate/MAXPROB criterion in *infinite-horizon* undiscounted MDPs with absorbing non-goal states, where vanilla value iteration truly has difficulties with this criterion, and shows that these difficulties are indeed caused by state values being uniform in loops/strongly connected components of the MDP's transition graph. In particular, as shown there, this uniformity introduces additional fixed points of the Bellman backup operator that value iteration relies on, and value iteration can converge to any of these fixed points as a result.

4) Several of the submission's other theoretical claims are quite sloppy as well. For instance, in the intro there is a statement "We believe that success rate is different from expected discounted return". I think this notion of difference should be made sufficiently precise so as to take faith out of the equation. Same goes for the loop penalty surrogate criterion in Section 4.1. Does optimizing it, at least in tabular MDPs using vanilla value iteration, result in obtaining a policy that maximizes success rate?

5) By itself, the loop penalty criterion looks new. However, a) as mentioned above, it's not clear whether it is a heuristic or has actual optimality guarantees w.r.t. success rate optimization and b) more importantly, papers [1] and [2] suggest at least two alternatives to fixing value iteration's convergence for success rate maximization (in infinite-horizon undiscounted MDPs):

   (a) As shown there, for value iteration/Q-learning-like methods, initializing state values *inadmissibly* (i.e., pessimistically in the face of uncertainty) and amending the Bellman backup operator to deal with "value uniformity" yields an optimal algorithm for this criterion.

   (b) Turn the success rate maximization MDP into a stochastic shortest path MDP (see [3] or almost any textbook by Bertsekas and Tsitsiklis) by assigning a positive cost to every action, introducing a "cap" D on the highest possible state cost, and minizing the undiscounted expected cost (see stochastic shortest path MDPs with finite dead-end penalty in [2]). D is a hyperparameter, and for *any* such cost assignment there exists a D s.t. the optimal policy for this surrogate MDP will that maximizes success rate in the original MDP. Results from [4] may even help prove something about convergence rate of this approach, although empirically convergence speed and resulting policy (note that there are generally many success rate-maximizing policies) will depend on the specific cost function choice.

At least method (b) is conceptually simpler than the loop disorientation penalty, and may even be theoretically similar to the latter, and provides a natural baseline for the proposed approach.

6) Last but not least, the empirical evaluation is too limited to be able to assess the merits of the proposed approach. While there are certainly problems where optimizing for success rate directly is preferable to optimizing the discounted reward, the use of discount factor in RL is important in many problems for mitigate the effects of estimation errors -- see, e.g., Xu et al. 2018 and [5]. Therefore, to get a better picture of whether success rate optimization is worth it in practice, one would need a more extensive evaluation on benchmarks such as goal-directed Atari or Procgen games and/or more complex robotics scenarios.


Thus, despite studying an interesting topic, I think this work needs to be significantly revised and extended before publication.



[1] Kolobov, Mausam, Weld, Geffner. "Heuristic search for generalized stochastic shortest path MDPs" ICAPS-2011

[1a] Little, Thiebaux "Probabilistic Planning vs Replanning" An ICAPS-2007  workshop 

[2] Kolobov, Mausam, Weld. "A Theory of Goal-Oriented MDPs with Dead Ends" UAI-2012

[3] Bertsekas, Tsitsiklis. "An Analysis of Stochastic Shortest Path Problems" Mathematics of Operations Research, 1991

[4] Yu, Bertsekas. "On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems" Mathematics of Operations Research, 2013

[5] Jiang, Kulesza, Singh, Lewis. "The Dependence of Effective Planning Horizon on Model Accuracy" AAMAS-2015
review_title: Theoretical analysis partly known, partly erroneous. Algorithmic contribution needs comparison to simpler alternatives and more extensive evaluation.

Meta-review: Despite the fact that some of the reviewers found the idea interesting, none of them believe that the paper is ready to be published at this stage. For example, better comparison with existing/similar work, and more solid argument on why the idea is better than alternatives are mentioned. All considered, unfortunately I cannot recommend acceptance of this paper in its current form. I encourage the authors to consider these comments and revise their paper accordingly.
Decision: Reject