Success-Rate Targeted Reinforcement Learning by Disorientation Penalty
Authors: Haichuan Gao
Zhile Yang
Tian Tan
Feng Chen
Venue:  (2021)
Keywords: reinforcement learning
undiscounted return
success rate

Abstract: Current reinforcement learning generally uses discounted return as its learning objective. However, real-world tasks may often demand a high success rate, which can be quite different from optimizing rewards. In this paper, we explicitly formulate the success rate as an undiscounted form of return with {0, 1}-binary reward function. Unfortunately, applying traditional Bellman updates to value function learning can be problematic for learning undiscounted return, and thus not suitable for optimizing success rate. From our theoretical analysis, we discover that values across different states tend to converge to the same value, resulting in the agent wandering around those states without making any actual progress. This further leads to reduced learning efficiency and inability to complete a task in time. To combat the aforementioned issue, we propose a new method, which introduces Loop Penalty (LP) into value function learning, to penalize disoriented cycling behaviors in the agent's decision-making. We demonstrate the effectiveness of our proposed LP on three environments, including grid-world cliff-walking, Doom first-person navigation and robot arm control, and compare our method with Q-learning, Monte-Carlo and Proximal Policy Optimization (PPO). Empirically, LP improves the convergence of training and achieves a higher success rate.

Under review as a conference paper at ICLR 2021
OPTIMIZING SUCCESS RATE IN REINFORCEMENT LEARNING VIA LOOP PENALTY
Anonymous authors Paper under double-blind review
ABSTRACT
Current reinforcement learning generally uses discounted return as its learning ob- jective. However, real-world tasks may often demand high success rate, which can be quite different from optimizing rewards. In this paper, we explicitly formu- late the success rate as undiscounted form of return with {0, 1]-binary reward function. Unfortunately, applying traditional Bellman updates to value function learning can be problematic for learning undiscounted return, and thus not suit- able for optimizing success rate. From our theoretical analysis, we discover that values across different states tend to converge to the same value, resulting in the agent wandering around those states without making any actual progress. This fur- ther leads to reduced learning efficiency and inability to complete a task in time. To combat the aforementioned issue, we propose new method, which introduces Loop Penalty (LP) into value function learning, to penalize disoriented cycling behaviors in agent's decision-making. We demonstrate the effectiveness of proposed LP on three environments, including grid-world cliff-walking, Doom first-person navigation and robot control, and compare our method with Q- learning, Monte-Carlo and Proximal Policy Optimization (PPO). Empirically, LP improves the convergence of training and achieves higher success rate.
INTRODUCTION
Reinforcement learning usually adopts expected discounted return as objective, and has been applied in many tasks to find the best solution, e.g. finding the shortest path and achieving the highest score (Sutton & Barto 2018 Mnih et al., 2015) Shao et al. 2018). However, many real-world tasks, such as robot control or autonomous driving, may demand more in success rate (i.e. the probability for the agent to fulfill task requirements) since failures in these tasks may cause severe damage or consequences. Previous works commonly treat optimizing rewards equivalent to maximizing success rate (Zhu et al. 2018:) Peng et al. 2018 Kalashnikov al. 2018). but their results can be error-prone when applied to real-world applications.
We believe that success rate is different from expected discounted return. The reasons as follows: 1) expected discounted return commonly provides dense reward signals for transitions in an episode, while success not is a sparse binary signal only obtained at the end of an episode; expected discounted return commonly weights results in the immediate future more than potential rewards in the distant future, whereas success or does not have such weighting and only concerned about the overall or the final result. Policies with high expected discounted returns are often more demanding in short-term performance than those with high success rates and optimizing success rates often leads to multiple solutions. As a result, policies with high success rates tend to be more reliable and risk-averse while policies with high expected discounted returns tend to be risk-seeking.
See the cliff-walking example in Fig. [ where the objective is to walk from the origin state marked with a triangle to the destination state marked with a circle. The "Slip" area in light grey winds with a certain probability Pial = 0,1, making the agent uncontrollably move down; the dark gray area at the bottom row denotes "Cliff". In Fig. D the blue trajectory shown on the left is shorter but riskier than the green shown the right. In commonly used hyperparameter settings, such y 0.9, the agent tends to follow the blue trajectory rather than the green one, although the green trajectory has higher success rate.

---

Under review as a conference paper at ICLR 2021
Slip
Slip
A-
Cliff
Cliff
L p = (1 Poal)
Length=9, p=1
Figure 2: Illustration value fucntion discounted (left) and undiscounted (right)
Figure I: walkkig example
We acknowledge that for this simple example. optimizing expected discounted return with a careful design of 7 that meets (1 - Pian) < 7 can produce policy with the highest success rate. However, this result relies on task speccsseciiiic knowledge about the environment, generally not available in more complex tasks. These findings lead us to the following question: can we express success rate in a general form so that can be directly optimized? In this paper, we discover universal way of representing success rate is to 1) use {0, J-binary reward indicates whether or not trajectory successful, and 2) set 7 = so that the binary signal back-propagates without any discount.
Unfortunately, this expression belongs to undiscounted problems and the convergence of value it- cration often cannot be guaranteed (Xu et al., 2018). Nevertheless, we can still explicitly solve the Bellman equation in a matrix form for the special undiscounted return (success rate). We derive that if the transition dynamics of the environment permit existence an irreducible ergodic set of states, 7 1 will lead to undesirable situation: state or state-action values tend to converge the same value, which we refer to as uniformity. As shown in Fig. 2 for the contour of state values in cliff-walking example, uniformity is reflected as plateau the right figure, which is caused by non-discounting and does not exist in discounting cases (left figure). Uniformity makes the selection of actions purposeless within the plateau, resulting in disoriented and time-consuming behaviors in the agent's 's decision decision-making, and unsatisfactory success rates.
Based on the above analysis, we introduce Loop-Penalty (LP) into value function learning to penal- ize disoriented and cycling behaviors in trajectories. We derive that this penalty can be realized by multiplying a special mask function to the original value function. Note that our strategy is general and is applicable to many RL. algorithmss.. We provide concrete loss functions for three popular algo- rithms in this paper: Monte Carlo, Deep Q-learning and Proximal Policy Optimization (Schulman) et al., (017). We verify the effectiiveness in three representative environments: grid-world cliff- walking, rision-based robot grasping. and first-person navigation in 3D Vizdoom (Kempka et al.) 2016), showing that LP can alleviate the uniformity problem and achieve better performance. Fi- nally, we summarize the major contributions of our paper in the following:
We formally introduce the objective of "success rate" in reinforcement learning. Our for- mulation of success rate is general and is applicable for many different RL tasks.
We theoretically analyze the difficulty in optimizing success rate and show that the unifor- mity among state values and the resulting loops in trajectories are the key challenges.
We propose LP which can be combined with any general RL algorithm. We demonstrate empirically that LP can alleviate the problem of "uniformity" among state values and sig- nificantly improve success rates in both discrete and continuous control tasks.
RELATED WORK
To the best of our knowledge, currently there is no research that adopts success rate directly as the learning objective. The reason is that success rate is usually not the main criterion in tasks investi- gated by RL, e.g. video games and simulated robot control. Although some studies used success rate to evaluate the performance of the policies (Andrychowicz et al. 2018 Kalashnikov et al. 2018), they used specific reward design and discounted return during training, instead of directly optimizing success rate.
al.) 2017; Tobin al. 2018 Ghosh
The notion "success" may be reflected in constraints considered the domain of safe RL (Garcia & Fernández 2015). Geibel & Wysotzki (2055) considered constraints the agent's behavior and
2

---

Under review as a conference paper at ICLR 2021
discouraged the agent from moving to enror states. Geibel (2006) studied constraints on the expected return to ensure acceptable performance. A. & Ghavamzadeh (203)) proposed constraints on the variance of some measurements to pursue invariable performance. Previous studies have also considered safety in the exploration process (Garefa & Hembández-Rcoollo, 2012 Mannucci et al.) 2018). Although these studies deemed success rate as additional constraint in learning. they either simply assumed that the constraint can be certainly satisfied or penalized constraint violations.
The deficiency of expected discounted return training objective has been recognized by many studies. Instead of just optimizing expected return, Heger (1994); (Tamar et al. (2013) adopted the minimax criterion that optimizes the worst possible values of the return. By doing so, occasional small returns would not be ignored at test time. Gilbert & Weng (2016); et al. (2017) extended this idea to arbitrary quantiles of the return. However, all these studies are not optimizing success rate directly since they are based on quantitative measurement of performance and are unneces- sarily sensitive to the worst cases. contrast, success rate is based on binary signal which only distinguishes between success and failure.
Our work involves optimization of an undiscounted return. The instability in training towards an undiscounted return has been mentioned by |Schwartz (1993); Xu et al. (2018). However, most stud- ies on undiscounted return focused on continuous settings and considered the average reward as objectives (Schwartz 1993 Ortner & Ryabko 2012 Zahavy al. 2020). There seems to be gen- eral view that the instability in training towards undiscounted return only exists in continuous cases but not in episodic cases (Pitis (2019). Contrary to this view, we propose that training instability also exists in episodic cases. For optimizing success rate, we provide theoretical analysis and show the existence of training instability and propose practical method that alleviates this problem.
SUCCESS RATE IN REINFORCEMENT LEARNING
In this section we provide formal definition of success rate, explain its relationship with expected discounted sum of rewards, and analyze the problems in optimizing success rate.
3.1 SUCCESS RATE
In RL, given a policy ,, success rate specifically refers to the ratio of the successful trajec- tories to all trajectories. As in general setting of RL, a trajectory is expressed (sT, asr,ar, ar,arrrrr (T), ST+1} rolled out by following policy म, where s E S is state,
{(sp, ag, a, A denotes action, Fa represents immediate reward and T is the length of the trajectory. Be- cause the notion of success should only depend on the visited states a trajectory, we concisely express "success" by defining a set of desired states Sg C S that denote task completion, e.g. the destination state in our cliff-walking example. At a high level, the goal of the agent is to reach any state in S, within a given planning horizon 7", and the environment terminates either upon arriving at desired state or reaching maximum allocated timestep T. Without loss of generality, we say that "a trajectory 7 successful" if and only if T- E Sy. where T-1 the last state in 7. Formally, we use an indicator function [(s E Sg)) to denote success, where I(-) takes value of when the input statement is true and otherwise. Since this expression is task-independent, our analysis can be widely applicable. Accordingly, we formally define the success rate as follows:
Definition 1. The success rate of a given policy æ is defined as
(=(5)) Σ (T(())))
where (T((s))) = Ii (((lssss))ssss)) 1s,,, a,) is the probability of observing trajectory T.
In order to find policy that optimizes success rate, we derive a recursive form of policy evaluation similar to the Bellman equation (Sutton & Barto 2018), as shown in Theorem 1.
Theorem 1. The success rate is a state-value function represented as an expected sum of undis- counted return, with the reward function R(s) defined to take the value of 1 if s E Sg, 0 otherwise.
Proof sketch: We segment the trajectories and generate sub-trajectories, k E (0, T). Note that r Å. because 1) Vr T, we have Torr E f T, r C f. 2) Tosk
[, E f, where
3

---

Under review as a conference paper at ICLR 2021
is trajectory, f S r. Then the success rate (st) can be rewritten as the product sum of the probability of reaching sc+& and the indicator [Tee+ E Sg) for all St+E:
T-t
Bz = ΣE pr (=( E (g) k=15
where Px (51+4(ss) the probability of reaching S144 from 8t. Complete proof is in appendix.
Therefore, we can optimize success rate through setting the above {0. 1 J-binary reward function and adopting an undiscounted form of return. The problem is that this formulation falls into optimizing the undiscounted form of return and may have problems in training stability (Xu et al. 2018).
3.2 UNIFORMITY IN SUCCESS RATE OPTIMIZATION
In the following part, we will show that y can cause uniformity among state values, resulting in possible loops in trajectories, which hurts training stability.
A. The concept of uniformity
First, we define the concept of uniformity. Given a policy we say that uniformity arises when the state-value estimates of a set of strongly connected states become the same. Here we say two states are strongly connected if one state is reachable from the other and vice versa, e.g. the first two rows in the grid-world example (Fig. D. Since state value represents the expected sum of available rewards (Sutton& & Barto 2018), uniformity means that moving in this connected area/region will potentially lead to the same amount of return. This phenomenon can hardly occur with discounted return since the discounting poses a preference for time-efficiency in collecting rewards and penalizes purposeless wandering. However, uniformity may happen when the objective is success rate since efficient trajectories and inefficient ones become indistinguishable.
B. Proof of the existence of uniformity
In this section, we theoretically prove that y 1 in the expression of success rate cause unifor- mity. Because uniformity is a phenomenon about concrete state values, common techniques used to analyze the overall performance such regret bound and contraction mapping do not apply here. Hence, we directly solve the Bellman equation to get state values. As for the reward function, we are fortunate that our case the reward function only takes {0. 1 ---iinary values, which makes our analysis tractable. As for the optimization process, we analyze state values at convergence by first assuming a policy with uniformity, and then show that this policy will be kept during optimization.
For succinctness in description, we assume S to be finite to write the Bellman equation into matrix form: V = pa R + 7 P"V. where V, R E Si pa E R[S) and (S] is the cardinality of the state space. Without loss of generality, we denote the desired states at the bottom of each vector, so Rt = [O.....0, 0, I, I,..., 1|"
Then we formulate the concept of "area" as set of states S. Ç S that are irreducible ergodic in the Markov process conditioned on policy æ. By assuming the existence of π and Se, and denoting states in S. as the first |S.| elements in the vectors, the r-conditioned transition probability matrix can be divided into
P 0 P
pd
P
where P is the transition probability matrix for E S.. Accordingly, we have the following Bellman equation for E Se:
V== P. + +7 Ve PP V..
Analyzing uniformity requires solving Eq For y < 1, the solution is unique V. 00... ......... 0 T because P is a stochastic matrix and (I - PP* must be non non-singular and the value 0 drives the agent to leave S. in future policy update. However, when 7 = 1, there are infinite solutions, as established in the following theorem.
Theorem 2. For 7 1, if S. exists, the solution space of Eq is (V. = m [1,... 11 Im E RR.
Proof: Because states in S. are ergodic, for any start-distribution of and un among S., we have
lim (Pxr)² = -u= lim (Pr
(5)
1-+00
1-400
4

---

Under review as a conference paper at ICLR 2021
Trjectory without a aloop
r
Trajectory with aloop
r
Loop Penalty VLP($t) ((ss)o(ss)
Chif
Clif
(a) State-action values
(b) The policy and loops
Figure 3: Numeric example of uniformity and loop
Figure 4: Sketch of Loop Penalty
Thus, lim (P should be in the form that every row is the same, illustrated below:
2 22
=|5.1
21
22
2|S.
lim (P= 1-+00
(P=)*=
:
U1
22
1|s.
Note that all the elements are non-zero because S. is irreducible. Thus, for equation V, E R. Because P is stochastic matrix, these solutions also satisfy Eq Now, because solutions for Eq also satisfy Ve (lim,->co ) )'), V., the solution spaces of the two equations become the same. Therefore, the solu- tion space of Eq (Ve m [L...., 1 Im RR, which completes the proof.
(lim;-sso (Pe))) Vo,, the solutions are m [I.....
This theorem demonstrates that when evaluating policy in terms success rate, the converged values for states in S. are the same and may take arbitrary values. This proves the existence of uniformity among state values.
Now reason that there be policy that produces Se and that this policy can be kept by the agent during policy optimization. (1) As for S., it is common in RI environment that there is set of two initialized (or disturbed by random sampling during learning) to only stay in this set of states, then gives the set of states S.. Note that the desired states are not in S. because they are absorbing and cannot reach other states. This ensures that R. = 10..... .0'" by which Eq valid. (2) As for the agent keeping during policy optimization, we check if the state values satisfy the Bellman optimal equation. We have derived that any may be the value of state in S., If the value m is larger than the value states reachable from S. (probably due to initialization of value function), then the update target of values of states in S. remains m. This means that satisfies the Bellman optimal equation at states in Se, and that the policy at S is kept during policy update. So far, we have proved that the objective of success rate cause uniformity in state values.
states that reachable from each other without randomness. If the policy is
C. Problems caused by uniformity
In RL, the agent selects actions based on the evaluation of future returns. When uniformity happens, the evaluation of different actions become the same, so the agent can only make random selections. This leads to disoriented, time-consuming but meaningless behaviors and unsatisfactory success rate. In practice, because of disturbances due to random exploration, there may be slight differences between state values. Although this makes action-selection certain, it may result in undesirable policies, which causes instability in training. Fig. 3 shows a numeric example. We adopt Q-learning and illustrate the trained Q-values and the preferred actions respectively in (a) and (b). The Q-values are almost the same in upper grids, and there are several potential loops in the agent's trajectory. If the agent enters a loop, it will keep repeating the loop and fail in reaching the target.
METHOD: LOOP PENALTY
So far have shown the problems in optimizing success rate. As for the solution, insight is to suppress the generation of "loops" to penalize disoriented cycling behaviors in agents decision- making. In this section, we derive the cost function for minimizing the probability of loops, which
5

---

Under review as a conference paper at ICLR 2021
Algorithm Loop-Penalty Q-Learning
Initialize: action-valle value function Q. episode buffer D;
for episode= 1, do
Initialise episode buffer D;
= 1, do
With probability select random action de, otherwise select o, mar ( a); Execute action Oę in emulator, get and store transition (8t, Ct, Tt. 8141) in D; end for
for each transition {st, ar, Tz. St--1 in D do Initialise the marker factor of loop ((se) for each {i,j 0 < < 1, < < T do
Calculate Φi + 0e [s, 8y);
end for
for terminal 8141 Set 3/- (r: + mar, 1, a)),; for non-terminal 8141
Perform a gradient descent step on Iyy - de)ll:
end for end for
introduces Loop Penalty (LP) into value function learning. Then we introduce practical algorithm that can implement this framework for reinforcement learning problems.
4.1 LOoP PENALTY
Our idea is that the agent not only needs to maximize the success rate, but also minimize the proba- bility of "loops". This is formalized as follows:
π argmaz pa (T noopo Sg)),
(6)
where nno-loop is the trajectory without loops where the agent visits some states more than once, in which the agent never revisits a previous state. We now derive the recursive state-value function gloop- penalty (st) with our loop-penalty for the optimization Eq
Theorem 3. The state-value function policy for Eq
gloop
gloop-penalty penalty (st) E.-r [T( Sy))(s)) poop-penalty (8++1)]
where Ø(s:) == I(s, F 83, 0 < i < t, s T) is indicator that judges whether there is loop through 8; the trajectory т.
Proof sketch: The key idea is to convert Eq to sum of the probability products of (+( and I(s E (T))oono where ((-no)))op) judges if there not a loop in r. addition, we mark Pr(s1 so H s) and have:
the probability of reaching state as (s((s) Px
Pa no-lopp +Sy)= pp
Σ I(s S,) # s, vi+1<<<T),
(8)
We postpone the complete proof the appendix.
So far we have derived that reducing the probability of loops can be achieved in sampling with multiplying Φ(st) according the signal success or not in each collected trajectory, which is method of online policy evaluation for state values.
4.2 ALGORITHM
In this subsection, we design three implementation methods by substituting the state-value function with LP into the loss functions of three commonly used RL algorithms. Monte Carlo (MC), Q- Learning (QL), and Proximal Policy Optimization (PPO) (Schulman et al. 2017). As discussed above, LP takes the form of multiplying the original state-value function with @(s.) as shown in

---

Under review as a conference paper at ICLR 2021
Fig. Note that the indicator ((ss) can be implemented with many famous methods for measuring
state similarity, such as GAN or VAE YYu et al. 2019; Chen et al., 2016: Pathak et al. 2017). To that end, we derive three new adjusted loss functions, MC with Koop-Penaly (MC-LP), QL with Loop-Penalty (QI.-IP), PPO with Loop-Penalty (PPO-LP) as follows:
LMC-LP(TQ, e, si) Br e 1 rLo(s)) Q(sk: ((ssk.x)12211. ax)112)
(9)
LQL-LP(FQ, st) x E, ErNaR [ll(re11 + ymarau+ Q(5+1 (+1)))((s) a(s),a))ll2
(10)
TT(aast) dipl
Ta (a(a(s))
LPPO-LP(T,SS) & - -od min A(st,, a))1)))(()) Tk,ota(a|
(11)
Tkkald (8))
where is the exploration rate of MC, A(st, a) the advantage function and clip(.) the clipping function. Note that these algorithms all adopt online evaluation methods for value functions, because the probability of loops is related with the current policy. We choose QL-LP representative to show our algorithm (Alg The agent stores the state transitions collected in an episode into an online buffer D and use it learn at the end of the episode. The loss function of LP-QL takes the product of rt + maz, Q( a) and ((s) as the target Q-value yt in our algorithm.
5 EMPIRICAL RESULTS
In this section we aim to analyze the following three questions: 1) Does LP alleviate the unifor- mity of state values for success-rate optimization? 2) Does LP achieve better performance in terms of success rate, furthermore close to the highest possible success rate? 3) What is the difference between the policy with a high success rate and that with a high expected return?
5.1 TASK DESIGN
We design three environments to exhibit the problem and examine the effectiveness of our algorithm.
1) We use the aforementioned biff-walking grid-world to show how our algorithm works in detail. 2) We construct 3D first-person navigation task based on ViZDoom (Kempka al.) (0166) examine whether LP is suitable for complex tasks, 3) We construct robot (kinova jaco2) grasping task with CoppeliaSim (originally named V-REP) to examine the practicality.
In these three tasks, we constructed dangerous areas respectively, in which the agent fails with a certain probability: 1) windy area in the grid-world that makes the agent uncontrollably move down with certain probability P/all = 0.1 and fall down the cliff, 2) an area in the ViZDoom environment with a monster shooting at the agent, where the probability of failure depends on behaviors of the monster and the agent's s random initial health, 3) noisy area in the robot grasping task in which the arm is disturbed with 0.2 probability and may collide with the obstacle. These environments are illustrated in Fig. 5 b, c). The ViZDoom and robot grasping tasks only provide visual inputs for decision-making. To show our method is compatible with different RL algorithms, here we use three RL algorithms in three experiments: 1) QL and QL-LP in Grid-wor world, 2) MC and MC-LP in ViZdoom, 3) PPO and PPO-LP in Robot grasping. Other details are included in the appendix.
5.2 RESULTS ON CONVERGENCE AND SUCCESS RATE
First, we focus on the first question, i.e. whether our method alleviates the convergence problem of success-rate optimization. To reflect convergence, we plot curves about the change of success rate during training Fig. 6 which obtained by testing the policy ten times the end of each training episode to calculate the success rates. It shows that there high variance when using MC (7 1.0) and QL (7 = 1.0) to optimize success rate, while our methods (marked by LP) can converge stably to a high success rate. These results indicate that: 1) the difficulty of convergence exists when optimizing success rate, 2) LP can stably optimize success rate.
Then, we try to answer the second question, i.e. whether our method achieves better performance than optimizing the expected discounted return. Furthermore, we check whether the success rate of method can be close to 1. We test the model 1000 times at the end of training and calculated the success rate, as shown 1 In our experiments, PPO-LP with y = 1.0 has an obviously higher success rate than PPO optimized by expected discounted return with 7 0.7 and that with
7

---

Under review as a conference paper at ICLR 2021
(a) Grid-world cliff-walking
(b) ViZDoom navigation
(c) Robot grasping
Target
PPO 0.7
PPO-LP
MCLL
y 0.9
Calliion
Agenti
Start
Monster
(d) (s) sdiff-walking
(c) Paths ViZDaom
(f) Paths of robot grasping
Figure 5: Illustration of environments, value functions and policies
Table 1:
Success rate in robot grasping
Sucoeess Itate
Seerea Rate
0.8
0.8
0.5
QL-LP -01.
MC-LP ==1.
Algorithms
Success Rate
0.2
0.0
QL --000
Ol.
--0.8
--0.0 MC --1.0
PPO (r 0.7)
0.761
PPO 1.0)
0.109
dx
4x
3k
%
11k
PPO-LP (7 1.0)
0.987
Episode Number
Episode Number
Figure 6: Learning curve of cliff-walking (left), ViZDoom (right)
7 = 1.0, furthermore closer Results of success after training show that: Optimizing with expected discounted return can not achieve the highest success rate in our experiments, and 2) the success rate of our method can be close to the highest.
5.3 VISUALIZATION OF STATE VALUES AND POLICIES
Lastly, we focus on our third question, i.c. what are the characteristies policies trained with our method? We visualize the state values and the policy of our method in the grid-world task. As shown in Fig. (d), there is no uniformity in state values and the trajectory bypasses the dangerous area. Then we visualize the policies of ours and policies got by optimizing expected discounted returns in ViZDoom and robot grasping, as shown in Fig. (e.f). They show that the policies trained by maximizing success rate with LP tend be reliable and risk-averse. On the contrary, the policies trained by maximizing expected discounted return tend to be risk-seeking.
DISCUSSION
This paper formally introduces the objective of success rate, analyzes the uniformity problem in directly optimizing success rate in RL, and proposes LP to alleviate it. As a potential impact, we think the discovery of the relationship between success rate and expected undiscounted return may imply that expected undiscounted return has some useful properties. As for future work, we hope to investigate different methods for measuring state similarity to improve the efficiency of LP. In addition, we think it is also beneficial to develop methods that alleviate the sparse-rewar reward problem in optimizing success rate.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Prashanth L. A. and Mohammad Ghavamzadch. Actor-critic algorithms for risk-sensitive mdps. In Annual Conference on Neural Information Processing Systems, pp. 252-260, 2013.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight Experience Re- play. In Advances in Neural Information Processing Systems, 5048-5058, 2017.
Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Picter Abbeel. Infogan: Interpretable representation learning by information maximizing generative adversarial nets. In Annual Conference Neural Information Processing Systems, pp. 2172-2180, 2016.
Yinlam Chow, Mohammad Ghavamzadch, Lucas Janson, and Marco Pavone. Risk-constrained re- inforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18: 167:1-167:51, 2017.
Javier García and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16: 16:1437-1480, 2015.
Javier García and Fernando Fernández-Rebolle Safe exploration of state and action spaces in rein- forcement learning. Journal Of Artificial Intelligence Research, 45:515-564, 2012.
Peter Geibel. Reinforcement learning for mdps with constraints. European Conference on Ma- chine Learning, volume 4212, pp. 646-653. Springer, 2006.
Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligence Research, 24:81-108, 2005.
Dibya Ghosh, Avi Singh, Aravind Rajeswaran, Vikash Kumar, and Sergey Levine. Divide-and: conquer reinforcement learning. In International Conference Learning Representations. Open- Review.net, 2018
Hugo Gilbert and Paul Weng. Quantile reinforcement learning. CoRR, abs/1611.00862, 2016.
Matthias Heger. Consideration of risk in reinforcement learning. In International Conference Machine Learning, pp. 105-111. Morgan Kaufmann, 1994.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, and Sergey Levine. Scalable deep reinforcement learning for Aision-based robotic manipulation. In Annual Conference Robot Learning. volume 87 of Proceedings of Machine Learning Research, pp. 651-673. PMLR, 2018.
Michat Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaskowski. ViZ- Doom: A Doom-based Al research platform for visual reinforcement learning. In IEEE Confer- ence on Computational Intelligence and Games, pp. 341-348. IEEE, Sep 2016.
Tommaso Mannucci, Erik-Jan van Kampen, Comeelis C. de Visser, and Qiping Chu. Safe exploration algorithms for reinforcement learning controllers. IEEE Trunsactions on Neural Networks and Learning Systems, 1069 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioamnis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane I Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. 2015.
Nature, (277)(()):599-5555
Ronald Ortner and Daniil Ryabko. Online regret bounds for undiscounted continuous reinforcement learning, In Annual Conference on Neural Information Processing Systems, pp. 1772-1780, 2012.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity- exploration by self-supervised prediction. In International Conference Machine Learning. PMLR, 2017.

---

Under review as a conference paper at ICLR 2021
Xue Bin Peng. Marcin Andrychowicz, Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In IEEE International Conference on Robotics and Automation, pp. 1-8. IEEE, 2018.
Silviu Pitis. Rethinking the discount factor in reinforcement learning: A decision theoretic approach. In Thirty-Thire AAAI Conference on Artificial Intelligence, pp. 7949-7956, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, NF1117770063477, 2017.
Anton Schwartz. A reinforcement learning method for maximizing undiscounted rewards. In Inter- national Conference on Machine Learning, pp. 298-305. Morgan Kaufmann, 1993.
Kun Shao, Dongbin Zhao, Nannan Li, and Yuanheng Zhu. Learning battles in vizdoom via deep reinforcement learning. In IEEE Conference Computational Intelligence and Games, pp. 1-4. IEEE, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar, Huan Xu, and Shie Mannor. Scaling up robust mdps by reinforcement learning. CoRR, abs/1306.6189, 2013.
Josh Tobin, Lukas Biewald, Rocky Duan, Marcin Andrychowicz. Ankur Handa, Vikash Kumar, Bob McGrew, Alex Ray, Jonas Schneider, Peter Welinder, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization and generative models for robotic grasping. In JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3482-3489, IEEE, 2018
Zhongwen Xu, Hado van Hasselt, and David Silver. Meta-gradient reinforcement learning. In Annual Conference on Neural Information Processing Systems, pp. 2402-2413, 2018.
Xianwen Yu, Xiaoning Zhang, Yang Cao, and Min Xia. VAEGAN: A collaborative filtering frame- work based on adversarial variational autoencoders. In International Joint Conference on Artifi- cial Intelligence, pp. 4206-4212. ijcai.org, 2019.
Tom Zahavy, Alon Cohen, Haim Kaplan, and Yishay Mansour. Unknown mixing times in appren- ticeship and reinforcement learning. In Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, pp. 193, 2020.
Yuke Zhu, Ziyu Wang, Josh Merel, Andrei A. Rusu, Tom Erez, Serkan Cabi, Saran Tunyasuvu- nakool, János Kramár, Raia Hadsell, Nando de Freitas, and Nicolas Heess. Reinforcement and imitation learning for diverse visuomotor skills, In Robotics: Science and Systems, 2018.
A APPENDIX
A.1 PROOF OF THEOREM
In this section, we complete the proof of theorem 1.
Theorem 1. The success rate is a state-value function represented as an expected sum of undis- counted return, with the reward function R(s) defined to take value of 1 if E Sy. 0 otherwise.
Proof: We segment the trajectories and generate sub-trajectories, E T. E f. where k (0, T). Note that I = f, because 1) VT P, we have Torr = T,, I f. 2) To.k a trajectory, f C P. Then the success rate Br (8x) can be rewritten as the product sum of the probability of reaching 814k and the indicator T(Taste Sy)) for all 8
(8.)
ΣΣ
Σ
(=( Sy)
(12)
1=1 Sitk
10

---

Under review as a conference paper at ICLR 2021
where Pr (5 the probability of reaching s1+E from st. Then substitute the formula of probability of reaching state p- (5(+++((5)) = + 7(ay1)))0(( az) into 8 (8:):
T-
I+
Bn ( = Σ
EI
II
E Sg)
SELE t=!
(ac()))) Σ p(setalss, (1) E 5z)
(13)
Σ π (44411$(41))
Ep(s > I(T-1 Sg)((T)s411)
Σ ((ae(s)) Σ p(st41ls,, [[(44] E Sg) (+
8++1
we compare success rate of states (x() with the state-value function Va (st) Es, 7(a (t)) E.... p(s at) [ri+1 + (s(+1)) will find that the success rate is kind of undisouncted return with (0.1r-binary reward of [(s E Sg), which completes the proof.
A.2 PROOF OF THEOREM
In this section, we complete the proof of theorem 3.
Theorem 3. The state-value function policy for Eq
Bloop gloop-penalty penalty (st) E [(s++1 ())) ppop-penaltyy (
(14)
where ((s:) == [(s + 8j, 0 < i < t, < S T) is an indicator that judges whether there is loop through s the trajectory т.
Proof: The key idea is to convert Eq 6 to sum of the probability products of (T( and [(s E (y)((Too_ooo)) where T(7 judges if there is not loop in v. addition, we mark the probability of reaching state as (s) = P*(s0 =) + P=(81 8,80 # s). and have:
Pn (1_1
1oop
E -pp((())) Σ 1(s, E (,)[(s; Vi+1k)
1=1+1
= Epa(s)) Σ [(((ti18iit)
E Sy) + v,,ii T)+
"1
dit1
[ E Ep(ss4al5422 01+2)
Σ
I(se E Sy) * s, Vi+1 <j Ti]]]
0442
1=i+3
(pr(s [[1++1 S,) v vitii<sjss)
Si
T
E
Σ 1(s E S $ +s,
E
[[ E ES)]((s) 4w,0o<i<44444)7
B
Σ b,,
k=t+1
(15)
Then let ((8t) = [(3 * 8, 0A 1 <jj and we have
T Pa (T noooppp E Sy) = [[(841 E Sy)((s)) + Erar El E S,)6(s++11]
(16)
6+2
T
Considering Shoop-penalty.com = EyNT [s(+1 E Sg)((s=)] the gloop- penattpe) can also be
written as recursive form:
gloop- gloop-penalty (st) = Erar [[(s-1 E Sy)o(st) + gloop- gloop-penalty penalty penally((stt)) (s141)
(17)
which completes the proof.
11

---

Under review as a conference paper at ICLR 2021
Table 2: Learning rate
Table Exploration rate
Algorithms
Learning Rate
Algorithms
Exploration Rate
QI.
0.1
QL
0.3
MC
0.01
MC
random choice from [0,0.5] 0.0002 (coefficient)
PPO
0.0001
PPO
observttio
Coar26 (6.66)
observation
ReLU
Couv2d 33, 64)
MaxPPol K-1
Cour2d (16 32)
ReLU
9-2
MaxPael K-2
Rel.1
MaxPoool K-2
Canvad (04, 125) K-4 $-2
Conv2d
ReLU
RSLU
Marloel Re2
MaxcPool K-2
PC (1152, 512)
FC (452,300) 300)
ReLU
aclions)
PC (300 200)
state-action valne
Ret17
FC (200 150)
action
RS117
FC (150,
FC
adlioo
slate value
Figure 7: Schematics of the networks of 1) PPO the left 2) MC the right
A.3 EXPERIMENT DETAILS
We set the same syper-parameters for models of algorithms and the baselines. The learning rates and exploration rates are set as the Table 2 and Table 3, in which the exploration rate is expressed with the coefficient of policy entropy. The parameter for gradient clipping in PPO Ealip is set to 0.1. We implement ((s²) with environmental information (position information in ViZDoom and pose information of arm in robot grasping) as signals in the training. but not use the information in the testing. The models we used in World tasks are tabulars which has the same shapes as the environments" and those in ViZDoom tasks and Robot tasks are neural-networks. The models of
networks are shown in Fig. 7 And the inputs are shown in Fig. g
A.4 NUMERICAL RESULTS ON STATE-ACTION VALUES
We show the state-action values of MC-LP = 1.0), QL 0.6) and QL (- 1.0) after training Fig. State-action values of QL (7 1.0) show the phenomenon of uniformity. State-action values of QL (7 = 0.6) has no uniformity but tend to be risk-secking. State-action values of MC-LP (? 1.0) has no uniformity and perform conservative. with high success-rate.
12

---

Under review as a conference paper at ICLR 2021
(a) Observations in robot grasping
(b) An observation in ViZDoom
Figure 8: Exhibition of the inputs of networks
0.00
0.01
0.00
[2000
0.01
10000
9.01
0,20
0.12
10,02
0.01
10.00
0-87
0999
2.91
0.54 0056
0.57
0.69
8/22
6.12
0:03
0.35
0.36
0.994
0ST
0.54
ELY9
0.01
0:12
10.16
0.37
10.31
10:3
0.71
0.36
8:17
0.1
0.55
0052
0.16
0.21
1:25
0:33
0.96
T0,26
0.21
0,25
0:33
8.41
0.64
1,00
0.24
10.31
(0.44 12.39
0.30 10.59
9.39 T0.
0.50
10:0
0.51
on
0.30
0.21
0.54
0.46
0.20
0.30
13.3
0.26 f0.46
w35. f0.50
0.49 f1y75
1000
0.10
vI
6:71 17
0.00
0.09
0.00
0.00
0:00
0.00
0.60
0.00
0.00
0.00
0.00
(a) State-action values of QL (7 0.6)
(b) State-action values of QL (7 = 1.0)
0.00
10.50
10.94
10.9
10.9
10:00
0.00
0.50
0.73
0L52
0.75
0.92
0.59
0.30
0.26
0.54
0.90
0.33
0.06
0.79
0.45
0.30
0.00
0.08 1uu
1.07
10.24
122
0.00
0.40
0:11
fues
butz fu42
fu41
Tu44
1.A9 102
M.R 10:00
0m0
8.77
8:19
0.5
1.00
b:00
1929
0.00
1025
0.00
0.00
Statc-action values of MC-LP (y 1.0)
Figure 9: Illustration of state-action values
13


Reviews:
[{"review_id": "qZqSBM09Hk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nRelated 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.\n\nTermination: 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.\nPage 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)\n\nTheorem 3: the indicator phi(s_t) seems like it should be a function of tau as well\n\n“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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kPn6zkx0bwg", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "------------------------------------------\nPOST-REBUTTAL COMMENTS\n\nThanks for your comments.\n\nRe: 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.\n\nRe: A5, regarding \"D\" being analogous to \"gamma\" -- fair enough, but this approach is still a meaningful baseline to compare against.\n\nRegarding 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_.\n\nIn 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.\n\n---------------------------------------------------\n\n\nThe 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.\n\nThe 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:\n\n\n1) 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.\n\n2) 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\noften 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.\nNote 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.\n\n3) 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.\n\n4) 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?\n\n5) 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):\n\n   (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.\n\n   (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.\n\nAt 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.\n\n6) 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.\n\n\nThus, despite studying an interesting topic, I think this work needs to be significantly revised and extended before publication.\n\n\n\n[1] Kolobov, Mausam, Weld, Geffner. \"Heuristic search for generalized stochastic shortest path MDPs\" ICAPS-2011\n\n[1a] Little, Thiebaux \"Probabilistic Planning vs Replanning\" An ICAPS-2007  workshop \n\n[2] Kolobov, Mausam, Weld. \"A Theory of Goal-Oriented MDPs with Dead Ends\" UAI-2012\n\n[3] Bertsekas, Tsitsiklis. \"An Analysis of Stochastic Shortest Path Problems\" Mathematics of Operations Research, 1991\n\n[4] Yu, Bertsekas. \"On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems\" Mathematics of Operations Research, 2013\n\n[5] Jiang, Kulesza, Singh, Lewis. \"The Dependence of Effective Planning Horizon on Model Accuracy\" AAMAS-2015", "extra_scores": {}, "extra_text": {}}, {"review_id": "h0sSxWlxZMU", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Paper Summary\n\nThis 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. \n\n### Review Summary\n\nI 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. \n\n### Pros\n\nI 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. \n\n### Cons\n\nThe 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).\n\nThe 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. \n\nI 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.\n\nIn 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. \n\nAs 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. \n\n### References\n\nHere are a few recent papers that modify the task specification / Bellman equation in order to improve the optimization: \n\n- [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.\n\n- [2] De Asis, Kristopher, et al. \"Fixed-horizon temporal difference methods for stable reinforcement learning.\" arXiv preprint arXiv:1909.03906 (2019).\n\n- [3] Tessler, Chen, and Shie Mannor. \"Maximizing the Total Reward via Reward Tweaking.\" arXiv preprint arXiv:2002.03327 (2020).", "extra_scores": {}, "extra_text": {}}, {"review_id": "8fjmwZfS18l", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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. \n\nI 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.\n\nWith regards the analysis, I believe that the following is problematic:\n* 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.\n* 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.\n* 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.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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