Plan-Based Relaxed Reward Shaping for Goal-Directed Tasks
Authors: Ingmar Schubert
Ozgur S Oguz
Marc Toussaint
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
reward shaping
plan-based reward shaping
robotics
robotic manipulation

Abstract: In high-dimensional state spaces, the usefulness of Reinforcement Learning (RL) is limited by the problem of exploration. This issue has been addressed using potential-based reward shaping (PB-RS) previously. In the present work, we introduce Final-Volume-Preserving Reward Shaping (FV-RS). FV-RS relaxes the strict optimality guarantees of PB-RS to a guarantee of preserved long-term behavior. Being less restrictive, FV-RS allows for reward shaping functions that are even better suited for improving the sample efficiency of RL algorithms. In particular, we consider settings in which the agent has access to an approximate plan. Here, we use examples of simulated robotic manipulation tasks to demonstrate that plan-based FV-RS can indeed significantly improve the sample efficiency of RL over plan-based PB-RS.

Published as a conference paper at ICLR 2021
PLAN-BASED RELAXED REWARD GOAL-DIRECTED TASKS
SHAPING FOR
Ingmar Schubert', Ozgur S. Oguz and Mare Toussaint 1.2
1 Learning and Intelligent Systems Group. TU Berlin, Germany
2 Max Planck Institute for Intelligent Systems, Stuttgart, Germany
3 Machine Learning and Robotics Lab, University of Stuttgart, Germany
{ingmar s schubert, toussa intsssainn/ii f -ut--berrl lil..in.. de ozgur oguz0 pvs. unw-stttuutee stuttgart.de
ABSTRACT
In high- digh-siimenional state spaces, the usefulness of Reinforcement Learning (RL) is limited by the problem of exploration. This issue has been addressed using potential-based reward shaping (PB-RS) previously. the present work, we in- troduce saal--oouuue-Preeevviie
Reward Shaping (FV-RS). FV-RS relaxes the strict optimality guarantees of PB-RS to guarantee of preserved long-term be- havior. Being less restrictive, FV-RS allows for reward shaping functions that are even better suited for improving the sample efficiency of RI. algorithms. In par- ticular, consider settings in which the agent has access Here, we use examples of simulated robotic manipulation tasks to demonstrate that plan-based FV-RS can indeed significantly improve the sample efficiency of RL over plan-based PB-RS.
approximate plan.
INTRODUCTION
Reinforcement Learning (RL) provides a general framework for autonomous agents to learn com- plex behavior, adapt to changing environments, and generalize to unseen tasks and environments with little human interference or engineering effort. However, RL in high-dimensional state spaces generally suffers from difficult exploration problem, making learning prohibitively slow and sample-ineffcient for many real-world tasks with sparse rewards.
A possible strategy increase the sample efficiency of RL algorithms is reward shaping MMataric 1994 Randløv & Alstrom 1998), in particular potential-base reward shaping (PB-RS) (Ng et al. 1999
Reward shaping provides dense reward signal the RL agent, enabling it converge faster to the optimal policy. In robotics tasks, approximate domain knowledge is often available and can be used by a planning algorithm to generate approximate plans. Here, the resulting plan can be provided to the RL. agent using plan-based reward shaping (Grzes & Kudenko 2008 |Brys et al.) 2015). Thus, plan-based reward shaping offers natural way to combine the efficiency of planning with the flexibility of RL. We analyze the use of plan-based reward shaping for RL. The key novelty that we theoretically introduce Final-Volume- Dolume-Preservinn Reward Shaping (FV-RS), a superset of PB-RS. Intuitively speaking, FV-RS allows for shaping rewards that convey the information encoded in the shaping reward in a more direct way than PB-RS, since the value of following a policy is not only determined by the shaping reward the end of the trajectory, but can also depend on all intermediate states.
While FV-RS inevitably relaxes the optimality guarantees provided by PB-RS, show in the periments that FV-RS can significantly improve sample efficiency beyond PB-RS, e.g. allowing RL. agents learn simulated 10-dimensional continuous robotic manipulation tasks after ca. 300 rollout episodes. We argue that the strict notion of optimality in PB-RS is not necessary in many robotics applications, while on the other hand relaxing PB-RS FV-RS facilitates speeding up the learning process. Using FV-RS could be better trade-off between optimality and sample efficiency in many domains. The contributions of this work are:
We introduce FV-RS as new class of reward shaping for RL methods in general.

---

Published as a conference paper at ICLR 2021
We propose to specifically use FV-RS for plan- based reward shaping.
We show that compared to no RS and plan-based PB-RS, plan-based FV-RS significantly increases the sample efficiency in several robotic manipulation tasks.
2 RELATED WORK
2.1 SPARSE REWARDS AND REWARD SHAPING
In many real-world RL settings, the agent is only given sparse rewards, exacerbating the exploration problem. There exist several approaches in the literature overcome this issue. These include mechanisms of intrinsic motivation and curiosity (Barto et al. 2004 Oudeyer et 2007 [Schembri jt al. 2007). which provide the agent with additional intrinsic rewards for events that are novel, salient, particularly useful for the learning process. In reward optimization (Sorg et al. [2010] Sequeira et al., 2011 2014), the reward function itself is being optimized to allow for efficient learning
Similarly, reward shaping (Mataric 1994: Randlov & Alstrom 1998) a technique to give the agent additional rewards in order guide during training. In PB-R RS-RS (Ng et al. 1999; Wiewiora (003)] Wiewiora et al. (2033] Devlin & Kudenko 2012)) this is done in way that ensures that the resulting optimal policy is the same with and without shaping. [Ng al. 1999) also showed that the reverse statement holds as well; PB-RS is the only type of modification to the reward function that can guarantee such an invariance if other assumptions about the Markov Decision Process (MDP) are made.
In this work, introduce Final-Volume- Volume-Preserving Reward Shaping (FV-RS), subclass of reward shaping that is broader than PB-RS and not necessarily potential-based, and therefore is not guar- anteed to leave the optimal policy invariant. However, FV-RS still guarantees the invariance of the asymptotic state of the MDP under optimal control. In the experiments section, we show that this relaxed notion of reward shaping allows us to substantially improve the sample efficiency during training.
2.2 DEMONSTRATION- AND BAAND REWARD SHAPING
Learning from Demonstration (Lff) aims at creating a behavioral policy from expert demonstra- tions. Existing approaches differ considerably in how the demonstration examples are collected and how the policy is derived from this (Argall et al. 2009, Ravichandar et al. 2020). The HAT algorithm (Taylor et al. 2011) introduces an intermediate policy summarization step, in which the demonstrated data is translated into approximate policy that is then used to bias exploration in a final RL stage. In Hester et al. (2077). the policy is simultaneously trained on expert data and collected data, using combination of supervised and temporal difference losses. In Salimans & Chen (2018), the RL agent is at the start of each episode reset to state in the single demonstration.
Other approaches (Thomaz et 2006 Knox & Stone 2010 rely on interactive human feedback during the training process.
At the intersection of RL and LID, reward shaping offers natural way to include expert demonstra- tions or plans of the correct behavior into an RL training process. Prior work in this area includes using abstract plan knowledge represented in the form of STRIPS operators
create a potential function for PB-RS (Grzes & Kudenko, 2008 Efthymiadis et al. [2066] Devlin & Kudenko 2016). which has been applied to the strategy game Starcraft (Fithhmiidis & Kudenko (013)) Brys al. (2015) use expert demonstrations to directly construct Gaussian potential function, and in Suay ctt al. 2016), this extended to include multiple demonstrations that are translated into potential function using Inverse Reinforcement Learning
intermediate step.
In this work, we use a planned sequence state-space to construct a shaping function similar to Brys et al. (2015), but in contrast to the aforementioned work, we do not use this shaping function as a potential function for PB-RS. Instead, we use it directly as a reward function for FV-RS. We show that this significantly improves the sample efficiency during training.
2

---

Published as a conference paper at ICLR 2021
3 BACKGROUND
3.1 MARKOV DECISION PROCESSES AND REINFORCEMENT LEARNING
We consider decision problems that be descrihed discrete-time MDPs (Bellman 1957) (S, A, T, R) Here, S is the set of all possible states, and A is the set of all possible actions. T: S x x + [0, 1] describes the dynamics of the system; T(s'ls, |s, a) is the probability (density) of the next state being s', provided that the current state is and the action taken is After the transition, the agent is given reward R(s, a, s'). The discount factor y E [0. 1) trades off immediate and future reward.
The goal of RL is to learn an optimal policy x² S. - [0, 1] that maximizes the expected discounted return, i.e.
Oc
π argmax
? " "
(a [R(s), at st41)l,
(1)
where Pu is the initial-state distribution, from collected transition and reward data D {(s;, at, Po= The Q-function of given policy is the expected return for choosing action ag in state So, and following thereafter, i.e.
(su, ao) Es, (-T(11)))))). (13)))
Σ yf R(s,,
There exists range of RL algorithms solve equation I Our reward-shaping approach only modifies the reward and therefore can be combined with any RL algorithm. In this work, we are interested in applications in robotics. where both S and & are typically continuous. A popular algorithm in this case is Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al. (2015), which will be used for most of the robotic manipulation examples this work. exception this are the examples in appendix A.4] which use Proximal Policy Optimization (PPO) (Schulman et al. 2017)
3.2 POTENTIAL--ASHE REWARD SHAPING
In many RL problems, rewards are sparse, making it harder for the RL algorithm to converge to the optimal policy. One possibility to alleviate this problem is to modify the reward R of the original MDP with shaping reward F.
a(s,,,')) R(s a, a²s" F(s,a,s))
In general, the optimal policy R* of the MDP M with the shaped reward R is different from the optimal policy r the MDP M with the original reward R. Ng et al. (1999) showed however that म* n²" and only if as, s') is derived from a potential function
E:
F(s, a') ( -(s))
This proof was extended (Wiewiora al. 2003) to potential functions both actions and states, provided that the next action taken, a' is known already. A further generalization to time-dependent potential functions was introduced in Devlin & Kudenko (2012).
4 FINAL- VOLUME- REWARD SHAPING
In the following, we introduce the notion of the optimal final volume, which will then allow us to introduce Final-Volume Volume-Preservingg Reward Shaping (FV-RS). FV-RS does not guarantee the in- variance of the optimal policy like PB-RS does, but instead provides a less restrictive guarantee of preserved long-term behavior.
4.1 OPTIMAL FINAL VOLUME
Definition 4.1. Let M an MDP with state-spuce S. If the set ne. es G2 non-emply, we call G the optimal final final volume of M. Here, & is the set of non non-empty sets Go C S such that
3lo 0: P Papaga (8e Ga) 1 At. 2
(5)
3

---

Published as a conference paper at ICLR 2021
Thus, the optimal final volume of MDP M is the minimal subset of the state space & of M that the MDP can be found in under optimal control with probability after finite time.
Notice that in order to keep the notation more concise, use the strict requirement Par-yg.- (st G) = instead c.g. P..-g.- (st E G) 2 1 - e in definition 4.1 For many stochastic MDPs, the stationary distribution under optimal policy has nonzero density the entire state space S. This means that strictly speaking, our definition would result the trivial optimal final volume G = for these MDPs. In practice however, many interesting MDPs such that can find a volume G for which it is so unlikely that the optimal agent will leave after some finite time has passed that we can readily assume that this probability 0 for all practical purposes.
4.2 COMPATIBLE MDPS AND VOLUME- PRESERVING REWARD SHAPING
Definition 4.2. Let M = (3, A,T. R) and M AS,A,,,7 Rt) be MDPs that are identical apart from different reward functions R and R, as well as different discount factors y and %. Let both M and M have optimal final volumes G and C, respectively. We call M a compatible MDP to M iff G C G, and we write M C M. If this is the case, also call it -ffunat-voume--rsseee shaping function.
reward
If M C M, this means that although the rewards and discounts (R,7) and (Rt 5) are different and, in contrast PB-RS, in general result in different optimal policies, they similar in the sense that after finite time, the state of M under optimal control will be inside the optimal final volume G of M. In other words; in the long run, behaving optimally in M will have the same "result" as behaving optimally in M.
Since PB-RS leaves the optimal policy invariant, M and M are also compatible M is the PB-RS counterpart to M. Thus, the notion of compatibility is less restrictive than the notion of an invariant optimal policy; FV-RS is a superset of PB-RS.
4.3 FV-RS
We now proceed to describe specific recipes to find compatible counterparts for MDPs with sparse reward.
Theorem 4.1. Lel M be an MDP with state space S and with the sparse reward function
R(s, s')==1 if E B: R(s, a, s') =0 else,
(6)
where BB C S is non-empty. Let M have the optimal final volume G. and let G C B. Let a(s, be a reward function that fulfills
R(s,a,s')=1 is's R(s, a, S') SA else.
Then, for every 0 < A < there exists discount factor 0 < 4 < 1 such that the MDP M corresponding to I and 7 is compatible with M.
Proof. See appendix A.5
This theorem gives worst-case bound the reward function: Independently of how small the difference 1 - A between the reward in TB and elsewhere is, as long as the conditions in equation are fulfilled, we can select sufficiently large 7 < that renders M a compatible MDP to M. Corollary 4.1.1. This lower bound on 5 is fy > A 1/ta-1))
Proof. Follows directly from the proof of theorem 4.1
Even if to is unknown but finite, M C M if 7 is chosen large enough. Note that so far, we have imposed no restrictions on R( a, s') for s' & B, other than R(s, a, s') < A. In that sense, the statements above represent an "upper bound on the lower bound of 5" if can not assume any additional structure for R. However, if we put more restrictions R. this worst-case bound can
4

---

Published as a conference paper at ICLR 2021
be relaxed. As example, discuss the case of reward function that the agent follow in a step-wise manner in appendix A.6 There it is shown that, depending on the step width w, the lower bound 9 A1/(6-1) can be relaxed to 7 > (1/(w-1), In the important case that the agent can follow the reward function monotonically (i.e. 1), this lower bound becomes O. For more details and a precise definition of the step width w, please refer to appendix A.6
4.4 FLAN-BASED FV-RS
We now describe how to construct plan-based FV-RS shaping reward function from plan, given as a sequence in state space. The goal to use the plan to create a continuous reward function that gives dense feedback to the policy guide along the plan.
Theorem 4.2. Let M be an MDP with metric state-space (S, d) with metric d : S x S + R and with the reward function
R(s, a, = if E IB; R(s, a, 8)) -0 else,
=1
(8)
where B C S is non-empty. Let M have the optimal final volume G, and let G C B. From planned sequence (pu: Pi..... PL.,) in with PL-1 E IB, we can construct the reward function
=1 k(s)) + L
s(s,ass)) = if'' e IB;
g(d(pe(s)): else,
(9)
where k(s') argmin, (d(pi, s')) and g: RR + (0, 1] is strictly monotonically decreasing, where g(0) 1. Then, for every < A < there exists 0 < 1 such that the MDP M corresponding R and is a compatible MDP to M.
Proof. Special case of theorem
This translates the plan into a continuous reward function that leads towards the target area B. The corresponding MDP M guaranteed to result the same optimal final volume as M. Thus, we established the machinery translate any MDP M with the sparse reward function in equation g into its plan-based FV-RS counterpart MDP M.
5 EXPERIMENTS
We demonstrate the efficiency of using FV-RS for plan- plan-based reward shaping using several exam- ples. We start with a simple discrete toy example to illustrate the difference between PB-RS and FV- RS that is not potential- based. We then compare PB-RS and FV-RS using a realistic (O-dimensional simulated robotic pushing example. This one of several robotic pushing and pick-and-place exam- ples we investigated. All results can be found in appendix A.2 Videos of all manipulation examples can be found in the supplementary material.
5.1 DISCRETE TOY EXAMPLE
We start off considering simple discrete example shown in figure La The agent starts in the middle and can choose between the actions A = {left, right, grab). where grab does not change the state, but allows the agent to grab the flag provided that is already at the position of the flag. The reward function is shown in figure lb Without shaping, reward 1 is only given if the flag captured. We also define the potential- reward function
-0.5 0
[0.5 if finish
Ren(s, a, s') R(s,a, 5') + 7)((')) (s)):
+(s)
=
(10)
else
where the shaping potential ((s) assigns value being the correct position, even if the flag is not captured. Similarly, we define the reward function
if s' fini sh and a = grab
Ryy as, = 0.5 if = finish and a a grab
(11)
else
5

---

Published as a conference paper at ICLR 2021
(a) Setup
No Shaping
No Shaping
left
1.0
left
right
right
0.4
grab
0.5
grab
PB-RS
PB-RS
0.2
left
left
right
0.0
right
0.0
grab
grab
FV-RS
-0.5
FV-RS
-
left
right
grab
-1.0
right
grab
-0.4
(b) Reward functions
(c) Q- Q-functions for T($) right
Figure 1: The toy example described in section 5.1 (a) The agent starts in the middle, and can move to the right and to the left. The goal is to grab the flag when at the goal position. The agent collects data during
episodes indicated by the arrows. (b) The reward functions without shaping, with PB-RS, and with FV-RS. (c) The resulting Q-functions for policy T(s) = right, based on the data from the two episodes.
which not potential-based but caal-vllue--reservvngg for the discount factor 7 = 0.7 of the original MDP. The agent collects data during rollout episodes starting in the middle, during one which always chooses to move right until the end the episode, and another episode during which the agent always moves left. Assume that this data is used in actor-critic setup, where the actor policy is not converged yet and therefore always chooses the action right. For this given policy and given data, the resulting Q-functions shaping, there is no reward signal collected during the rollouts, and therefore naturally, the Q- function contains no information. With PB-RS, the reward for moving to the correct position exactly canceled out by the discounted penalty for moving away from it again. As result, the values of the Q-function at the starting position contain no information about which action is preferable after these two training rollouts. With FV-RS, the shaping reward is not canceled out and propagated all the way through to the origin. In this case, the Q-function provides the agent with the information that moving to the right is preferable if it finds itself at the starting position.
shown in figure [Tc. Without reward
With PB-RS, the shaped return that is assigned to following a certain policy only depends on the discounted difference of the rewards at the final step and initial step of the recorded episode (Grzes) 2017). For non potential-basel shaping reward functions like Riv however, the shaped return de- pends on all intermediate rewards on the way there as well. that sense, FV-RS allows for shaped reward functions that propagate the reward information of intermediate states faster than PB-RS reward functions.
To physical analogy, PB-RS is analogous conservative force field, in which the potential energy a particle only depends on its current position. FV-RS that is not potential-base like a non-conservative (e.g. friction) force, for which the energy of particle only function of its position, but a function of the entire past trajectory.
5.2 ROBOTIC PUSHING TASK
In this example, test the efficiency of FV-RS in simulated robotic pushing task with realistic physics. The task is very similar to the man et al. 2016), but implemented using open-source software. Specifically,
environment in the OpenAl Gym (Brock-
the NVIDIA
PhysX engine (phy 2020) to simulate box of size 0.4 x 0.4 x 0.2 lying on table size 3 x 3, as shown in figure?

---

Published as a conference paper at ICLR 2021
Approximate Plan
End effector
Box
Goal
-1.5
1.5
(a)
(b)
Fraction of consistently successful agents
Mean asymptotic distance "Za5'
2.0
60%
No
PB-R5
oooe
50%
FV-RS
40%
No RS, quartile
30%
1.0
PB-RS, top quartile
FV-RS, top quartile
0%
Goal 0.0
250
500
750
1000
1250
1500
250
500
750
1000
1250
1500
Number of rollout episades N
Number of rollout episodes N
(d)
Figure 2: Robotic pushing task. (a) A box of size 0.4 x 0.4 0.2 (dark gray) lying table of size 3 x 3 (light gray) is supposed to be pushed to the green position by the spherical end effector (dark gray). (b) Top view of the table with 2-D projection of the planned 10-D trajectory (x and coordinates the end effector). The planned trajectory is not executable in the noisy environment. (c) With FV-RS, some agents consistently successful after around 300 training rollout episodes. Without reward shaping or with PB-RS, none of the agents were able to consistently reach the goal in this experiment. (d) Training progress of the top quartile of agents out of each category.
The agent controls the 3-dimensional velocity of a spherical end effector of radius 0.06. The max- imum velocity any direction 0.1 per time step. The actual movement of the end effector noisy; in 10% of the time steps, the end effector moves randomly. Using quaternion representation, the state space S has 7 3 10 degrees of freedom. The goal is to push the box within a distance of 0.1 from the goal position shown in green, with any orientation. Let IB be the set of states that fulfill this requirement. The unshaped reward R(s, a, s') is s' and is elsewhere.
The plan (Pus Pi. PL-1) is given sequence of states, shown in figure 2b The planned sequence has been created manually using a noise-free model, and therefore can not be followed directly in the realistic simulation. Instead, it is used to create plan-based shaped reward from it. we specifically compare the reward functions
Following the suggestion of theorem 4.2
{1 a (s')
if E
Rea
R(s,a,s)) (57pa((s) Ppp (s))
else
(12)
If Pyy is chosen suitably following theorem 4.2 Ryy is (hal--oolum--prssenvee with respect to reward function R of the original MDP. The aatential-based function Res acts as the baseline. Notice that Pyy and Ppn are chosen independently in order to facilitate a fair comparison FV-RS and PB-RS. We discuss and compare different choices both for Try and a in appendix A.1 There

---

Published as a conference paper at ICLR 2021
compare different gaussian plan- functions, similar to the ones used in Brys et al. (2015).
as well as a more simple function that only depends on the distance of the box to the target. Our analysis reveals that using the gaussian plan-based function
1 (s)) + exp (- [((s $ FF (8) - L
20² (-
(13)
with o = 0.2 results in a robust performance for FV-RS. Here, k(s) = argmin, argmin,(((p;,.. 8)), and d(:.)) the euclidean distance ignoring the coordinates corresponding to the orientation of the box. The value of this function increases the agent moves further along the planned path or closer towards the planned path. Similarly, our analysis also shows that using Pp = K (s)(s with K 50 results in a robust performance for PB-RS. We would like to emphasize that we did not impose that (s) a multiple of $Fv (s), rather our analysis revealed that this the most suitable choice. For more details, please refer to appendix A.
We apply DDPG (Lillicrap et al. 2013) for the examples presented throughout this paper. with the exception of the example presented in appendix [A.4 PPO (Schulman et al.] 2017). We use y デ 0.9 as discount factor. The agent collects data rollout episodes of random lenghh sampled uniformly between 0 and 300. Each of these episodes starts at the same initial position indicated in figure 2a we do not assume that the system can be reset to arbitrary states. The exploration policy acts e-greedily with respect to the current actor, where = 0.2. After every rollout, actor and critic are updated using the replay buffer. Both actor and critic are implemented as neural networks in Tensorflow (Abadi et al. 2016). Implementation details can be found in the supplementary code material.
The data reported in figure is obtained follows: For each of the shaping strategies (No RS, PB-RS, FV-RS), multiple agents a E {1,..., A} are trained independently from scratch. After N rollout episodes, multiple test episodes m E {L,..., M) } are run for 300 time steps or until the goal is reached. dei (N) is the distance of the box to the goal at the end of such a test episode.
We classify an agent as being consistently successful once d= 1/M En dlii (N) < 0.1. We emphasize that this is a rather strict criterion. Over M test rollouts, consistently successful agent must achieve an average asymptotic distance to the goal that is within the margin of 0.1, meaning that essentially all test rollouts have to be within the margin. We use A = 40 and M = 30 in all experiments reported. The training of an agent a is halted once it is consistently successful.
We report data from all agents in figure 2c and focus on the best performing quartile of agents out of each category in figure 2d The performance of agents ranked by how quickly they become consistently successful, or by how close to the goal they get in case they never become consistently successful. FV-RS helps to learn the task with significantly higher sample efficiency than PB-RS and without reward shaping. Some agents (see figure 2c) are consistently successful after ca. 300 rollout episodes (corresponding to ca. 45 000 MDP transitions) using FV-RS. In contrast, none of the agents using PB-RS or no reward shaping were able to consistently reach the goal after 1500 training rollouts in this example.
Apart from this pushing example, also investigated other robotic pushing tings in appendix A.2 Furthermore, we compare FV-RS and PB-RS using PPO instead of DDPG in appendix [A.4] While DDPG is off-policy and deterministic, PPO is on-policy and stochastic. Con- sistently across all experiments, we find a significant advantage of using FV-RS over PB-RS, which qualitatively confirms the findings discussed here. Videos of this and other manipulation examples can also be found in the supplementary material.
tack-and-place set-
6 DISCUSSION AND CONCLUSIONS
We introduced FV-RS, subclass of reward shaping that relaxes the invariance guarantee of PB-RS to a guarantee of preserved long-time behavior. We illustrated that since FV-RS is not necessarily potential-based it can convey the information provided by the shaping reward in more direct way than PB-RS. Using FV-RS, the value of following a policy does not necessarily depend on the discounted final reward only, but also depend on all intermediate rewards. Thus, FV-RS is analogous to a con-conservetive force (e.g. friction), and PB-RS to a conservative force (e.g. gravity).
8

---

Published as a conference paper at ICLR 2021
We proposed to FV-RS in order increase the sample efficiency of plan-informeds RL algo- rithms. We demonstrated the experiments that, compared to plan-based PB- PB-RS, plan-based FV-RS increase the sample efficiency of RL significantly. This observation is consistent across multiple manipulation examples and RI algorithms. In all manipulation examples tested, there were agents that were consistently successful after ca. 300 rollout episodes using FV-RS and DDPG.
An important limitation of plan-based reward shaping in general arises if the plan used for the shaping is globally wrong. In such case, the shaped reward would be of no use for the exploration and potentially misleading. Here, combining FV-RS with other exploration strategies could possibly remedy this limitation. Another limitation of the presented method that it is currently formulated for goal-driven sparse-reward setting, We restricted the present paper to the discussion of this class of MDPs since it often encountered e.g. robotic manipulation tasks. The direct application of RL still poses major obstacle here, making reward shaping an important tool.
Since reward shaping only modifies the reward itself, our approach makes no other assumptions about the RL algorithm used. It is orthogonal to and can be combined with other techniques used in RL, including popular methods for sparse-reward settings like Hindsight Experience Re- play (Andrychowicz et al., 2017). The same holds true for methods in LfD that also exploit task information provided in the form of an approximate demonstration or plan. relies relatively simple representation of the approximate plan in the form of sequence in state space. In addition, our method does not require the system to be reset to arbitrary states, as it the case e.g. in Salimans & Chen (2018).
hannbased FV-RS only
Both these aspects make a practical choice for real-world robotic applications. In many robotic manipulation settings, an approximate planner for the task is available, but the resulting plan can be directly executed on the real robot, Plan-based FV-RS could facilitate this sim-2-real transfer in an efficient and principled way using RL. Trading strict optimality guarantees for increased sample efficiency (while still guaranteeing preserved ang-timme behavior) could be beneficial in these cases.
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their insightful suggestions and comments. We thank the MPI for Intelligent Systems for the Max Planck Fellowship funding.
REFERENCES
Nvidia physx product site, August 2020.
URL dtttp:://developer..vidoo com/
gameworks -htpsphhpsxssxsee
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint 1603. 2016.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in neural information processing systems, pp. 5048-04880000 -048-505,,00 2017.
Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning. A survey of robot learning from demonstration. Robotics and autonomous systems, 576)) 2009.
Nikil Barhate. Ppo-pytorch. 2020.
Andrew Barto, Satinder Singh, and Nuttapong Chentanez. Intrinsically motivated learning of hier- archical collections of skills. In Proceedings of the 3rd International Conference on Development and Learning, pp. 112-19. Cambridge, MA, 2004.
Richard Bellman. A markovian decision process. Journal of mathematics and mechanics, pp. 679 684, 1957.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.0155p 2016.

---

Published as a conference paper at ICLR 2021
Tim Brys, Anna Harutyunyan. Halit Bener Suay, Sonia Chernova, Matthew E Taylor, and Ann Nowé. Reinforcement learning from demonstration through shaping. In fourth interna- tional joint conference on artificial intelligence, 2015.
Sam Devlin and Daniel Kudenko. Plan- Plan-based reward shaping for multi agent reinforcement learn- ing. Knowledge Eng. Review, 31(1):44-58, 2016.
Sam Michael Devlin and Daniel Kudenko. Dynamic potential-based reward shaping. In Proceedings of the 1 11th International Conference Autonomous Agents and Mulliagent Systems, pp. 433- 440. IFAAMAS, 2012.
Kyriakos Efthymiadis and Daniel Kudenko. Using plan-based reward shaping learn strategies in starcraft: Broodwar, In 2013 IEEE Conference on Computational Inteligence in Games (CIG), pp. 1-8. IEEE, 2013.
Kyriakos Efthymiadis, Sam Devlin, and Daniel Kudenko. Overcoming incorrect knowledge in plan- based reward shaping. Knowledge Eng. Review, 31(1):31-43 2016.
Marek Grzes. Reward shaping in episodic reinforcement learning. In Sixteenth International Con- ference on Autonomous Agents and Multiagent Sytems. ACM, 2017.
Marek Grzes and Daniel Kudenko. Plan-based reward shaping for reinforcement learning. In 2008 4th International IEEE Conference Intelligent Systems, volume 2, pp. 10-22. IEFE, 2008
Todd Hester, Matej Vecerik, Olivier Pietquin, Mare Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, et al. Deep q-learning from demonstra-
John Quan, Andrew Sendonaris, Gabriel 2017.
tions. arXiv preprint arXiv:1704.000
W Bradley Knox and Peter Stone. Combining manual feedback with subsequent mdp reward signals for reinforcement learning. In Proceedings of the 9th International Conference Autonomous Agents and Multiagent Systems: volume I-Volume I, pp. 5-12. Citeseer, 2010.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint ww.Xivv:50900000
2015.
Maja Mataric. Reward functions for accelerated learning, In Machine learming proceedings 1994, pp. 181-189, Elsevier, 1994.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application reward shaping. In ICML, volume 99, pp. 278-287, 1999.
Pierre Yves Oudeyer, Frdric Kaplan, and Verena V Hafner. Intrinsic motivation systems for au- tonomous mental development. IEEE transactions on evolutionary computation, 11(2):265-286, 2007.
Jette Randløv and Preben Alstrøm. Learning to drive a bicycle using reinforcement learning and shaping. In ICML, volume 98, pp. 463-471, 1998.
Harish Ravichandar, Athanasios Polydoros, Sonia Chernova, and Aude Billard. Recent advances in robot learning from demonstration. Annual Review of Control, Robotics, and Autonomous Systems, 3, 2020.
Tim Salimans and Richard Chen. Learning montezuma's 's revenge from single demonstration. arXiv preprint 1rXiv:181..03381, 2018
Massimiliano Schembri, Marco Mirolli, and Gianluca Baldassarre. Evolving internal reinforcers for an intrinsically motivated sinforeeeeentlearnnig robot. In 2007 IEEE 6th International Confer- on Development and Learning, pp. 282-287. IEFF, 2007.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
10

---

Published as a conference paper at ICLR 2021
Pedro Sequeira, Francisco S Melo, and Ana Paiva. Emotion-based intrinsic motivation for rein- forcement learning agents. In International conference on affective computing and intelligent interaction, pp. 326-336. Springer, 2011.
Pedro Sequeira, Francisco Melo, and Ana Paiva. Learning by appraising: an emotion-base approach intrinsic reward design. Adaptive Behavior, 22(5):330-349, 2014.
Jonathan Sorg, Richard L Lewis, and Satinder Singh. Reward design via online gradient ascent.
Advances in Neural Information Processing Systems, 23:2190-2198, 2010.
Halit Bener Suay, Tim Brys, Mathhw E Taylor, and Sonia Chernova, Learning from demonstration
for shaping through inverse reinforcement learning. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 429-437, 2016.
Matthew Taylor, Halit Bener Suay, and Sonia Chernova, Integrating reinforcement learning with human demonstrations of varying ability. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 2. pp. 617-6174 2011.
Andrea Lockerd Thomaz, Cynthia Breazeal, et al. Reinforcement learning with human teachers: Ev- idence of feedback and guidance with implications for learning performance. Aaai, volume 6, pp. 1000-1005. Boston, MA, 2006.
Eric Wiewiora. Potential-based shaping and q- galue initialization are equivalent. Journal of Artificial Intelligence Research, 19:205-208, 2003.
Eric Wiewiora, Garrison W Cottrell, and Charles Elkan. Principled methods for advising reinforce- ment learning agents. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 792-799, 2003.
A APPENDIX
Appendix A. compares different choices of shaping functions used for PB-RS and for FV-RS. The particular choice that was used for the experiments in this paper is also discussed and justified there. Appendix A.2 contains additional robotic manipulation examples. These are instances of both the simulated robotic pushing task presented in section 5.2 and simulated robotic pick-and-place task presented in appendix A.3
Appendix A.44 contains robotic pushing examples using PPO as RL algorithm instead of DDPG. Appendix A.5 contains the proof of theorem 4.1 In appendix AA.
special case of theorem 4.1 is discussed, additionally assuming a step-wing wise reward function that the agent can follow monotonically.
A. EXPERIMENTS ON THE CHOICE OF SHAPING FUNCTIONS USED FOR PB-RS AND FV-RS
We assume that the plan Rpg. and therefore 4pv and 4Pg. should provide a reward that is higher the closer the state of the environment is to the plan, and the further advanced it is along the plan towards the goal. Further- more, Ppv (s) Vss S has to be fulfilled in order to ensure that Rpv fulfills the requirements of theorem A canonical choice that satisfies these constraints are the Gaussian functions
is given as sequence of states. The functions ftv and
Gauss (s; 0) = ksss) +
exp (- (_R(ss
d3 Pk(s))
@FV
Gauss D
(5; = K (s;a)
Gauss
(14)
202
s)), d(.,) .) is the euclidean distance ignoring the coordinates corre- sponding to the orientation of the box, and K = 50 is a factor that is applied in order to render Rpy and Rpp comparable in scale. & is similar to the shaping potential that was used for potential- based reward shaping from demonstration in [Brys al. (2015).
where kss) =
As simpler alternative, we also compare against the negative distance functions
Th Dist (s) dBox (s,
PL-1;
T Dis P
K Dist (s)
(15)
11

---

Published as a conference paper at ICLR 2021
where d'ox(',PL- denotes the distance of the box the goal located at PL-1- These functions do not take the planned sequence into account, but only the intended final state, i.c. the goal. It is easy to verify that using d results in waall-volleeeeeeeeeeee
reward function.
We compare the performance of FV-RS agents using &pv or (.; for different against PB- RS agents using P or (., for different We use two different robotic pushing examples for this comparison. These are instances of the pushing example described in section 5.2 but with different initial positions and different goal positions. We measure the asymptotic distance over
different agents and rollouts as detailed in section 5.2 The results are presented in figure 3
Traction of consistenity successtul agems
PB
Fraction of consistently successffu aqpentx
8.0%
100%
Approximate Plan
80%
No RS
0.0
40%
(1 0:13
40%
2.0%
o/0 (; 0.44
20%
4,
0/
09%
-1.5
0.0
1.5
200
400
600
800
200
400
8000
800
Number rolluut episodes
Number
opicodes
(a)
(b)
Fracton of cornessanily successtal aqunts
Fractian of conecsenttyy surcessdaal aguets
PB-R5
FV-RS
1.5
Approximate Plan
30%
RS
80%
463 0.1)
20%
4ggnntr, 0.2)
60%
ng 0.4)
No RS
15%
4/1"
40%
(..0 0.11
20%
( 0.2)
20%
0s 0.4)
-1.5
-1.5
200
600
1000
Number of rollout episodes
Number of rallout episodes
(d)
(c)
(f)
Figure 3: Comparison of the performance of PB-RS and FV-RS when using different reward shap- ing functions as defined in equation [4] and equation 15 (a) The first row shows a very simple ex- ample. (b) In this example, using & Dis shows the best result with PB-RS, followed by Gauss (- 0.2) or & GaGauss (-, 0.4). (c) Similarly, 4Dii shows the best result with FV-RS, followed by hGauss which seems to be robust against different choices of a. (d) The second row shows more difficult exam- ple, in which the end effector has to move around the box before initiating the push. (e) Here, using the purely ristance-based potential function Dist is not successful, and the best result for PB-RS is achieved with GGGuuss (.2.. or o (- 0.1). ) (f) With FV-RS, a similar result is obtained, although @f (,, (.2) performs significantly better here.
Interestingly, dii and Dist perform best the simple example. However, using these functions for reward shaping does not scale well to the more difficult example. This can be ascribed to the missing path information when using purely distance-based information for reward shaping. On the other hand, using @. (.0.2) for PB-RS seems to be the second-best choice for the simple example, and one of the best for the more difficult one. The same holds true for using GGauss (., 0.2) for FV- RS. Since the manipulation problems we are interested in this paper resemble the more difficult example more than the simpler one, these experiments suggest that using & 0.2) for FV-RS is the best and most robust choice. We refer to this function as Ppy throughout the rest the paper. & Gauss (-, 0.2) for the baseline method PB-RS allows for fair comparison, since this choice has shown the best performance on the more difficult problem using FV-RS. We refer to this function h throughout the rest of the paper.
Furthermore, using PP
12

---

Published as a conference paper at ICLR 2021
0.14
0.35
1.5
1,5
1.5
Approximate
0.12
Approximate
0.30
--- Approximate Plan
End effector posiiion
0.10
0.25
0 0.2
0.20
0.0
0.06
0.15
0.04
0.10
0.02
0.05
-1.5
-1.5
1155
-1.5
0.00
-1.5
1.5
1.5
0.0
1.5
End effector pesition
End effector position
End effector position
(b)
(c)
Figure 4: Three different slices of the function & 0.2) defined in equation 14 using the example discussed in section 5.2 The state space is 10-dimensional: the figures show the function values for fixed 7-dimensional box position and orientation (indicated by the dark grey boxes) and fixed position of the end effector which is 2 0.14 for all three figures.
On different note, we observe that independently of the shaping function used, the performance of PB-RS decreases faster when moving to the more difficult example than the performance of FV-RS.
For the example discussed in section 5.2. plots of the function DG (.,0.) are shown in figure 4 & 0.2) is larger the closer is the approximate plan (po- P1. .L..1) given sequence of states, and the further advanced along the plan the state p; closest to s is (compare e.g. the scale of figure 4a to figure 4c). Using the approximate plan, the reward shaping function Ryv that is constructed using T GoGuss (.2.)) provides signal to the RL agent that helps guiding it towards the goal.
PP
A.2
ADDITIONAL ROBOTIC MANIPULATION EXAMPLES
The robotic manipulation examples presented in the following are instances of the simulated robotic pushing task presented in section 5.2 and a simulated robotic pick-and-place task presented in ap- pendix A.3 The results are summarized in figure 5 and figure respectively.
Qualitatively, the findings discussed in section 5.2 are confirmed across all examples. In both the pushing and the pick-and-plaa setting, FV-RS helps to learn the manipulation task with significantly higher sample efficiency than PB-RS. In all examples, there were agents that learned to consistently fulfill the task after ca. 300 rollout episodes using FV-RS, which corresponds to 45 000 MDP tran- sitions.
The first pushing example of figure 5 can be seen as an easier version of the second example. In- terestingly, no agent is able consistently succeed at the harder task with PB-RS, while one agents out of A = 40 is able to consistently succeed at the easier one with PB-RS. In contrast to that, the majority of agents learns consistently fulfill both tasks after ca. 300 training rollouts in both examples using FV-RS.
video of all experiments is included in the supplementary material.
A.3 ROBOTIC PICK-AND-PLACE TASK
For the robotic pick-and-place task, we use the NVIDIA PhysX engine (phy 2020 to simulate disk of radius 0.2 lying on a table of size as shown in figure 7a
We assume that the grasp is automatically established if the end effector touches the disk in the red area. Action and state space are the same as in section 5.2 apart from the information whether grasp has been established or not, which is appended to the state of the system (binary signal). Just as section 5.2 the movement of the end effector is noisy. The goal is to place the disk within distance of 0.1 from the goal position, shown in green in in figure 7al Let B be the set of states that fulfill this requirement. The unshaped reward R(s, a, s') is if E and is elsewhere. We
choose 7 3 0.9
13

---

Published as a conference paper at ICLR 2021
Faction of constaterdly surcesstt agannss
Approxmate Plan
No RS, top quartie
1.5
PB RS. top quartile
60%
PX-R5,
No Rt
0.0
40%
1.0
PV-RS
MMaan atymptattiicccc
20%6
0.5-
-1.5
Gasl
-1.5
0.0
1.5
200
400
600
800
1000
200
400
600
Number rollout
(b)
Traction of consssennty successtor agems
Moar asympuutti distance ---0pm
8075
Approximate Plan
2.0
60%
RS PB-R5
No top
0.0
6.7
PB-RS. top quartie
1.0
FVRRS, top quartil
09
-1.5
0.0
1.5
200
400
600
800
200
400
600
800
Number rolluut episodes N
Number rollict opisodes
(d)
Fraction of corsiiturttyy succusstul aquantss
Mean aageeng perppppotccc distarca A- (amm0
1.5
Approximate Plan
40%
PV-RS
30%
quartil quartile
20%
PV-R5. top quartle
10%
-1.5
8.0
1500
250
500
1000
1250
1590
Number rollout episodes
Number of rollout cpisodes
(h)
Figure 5: Additional pushing examples. Each row corresponds to a different example. With FV-RS, some agents are consistently successful after ca. 300 rollout episodes in all cases. With PB-RS, there one agents in the first example that learns to be consistently successful within the 1000 rollout episodes the experiment was run for. Across all examples, the training progress of the top quartile of agents significantly faster with FV-RS than with PB-RS without RS. Different evaluations from the first example were also shown in figure
Again, the plan (see figure 7bp is given as a sequence of states (Po, Pi,.....PP.1)))) and we construct the potential-bart based shaped reward Rpp and the final-volume-prees prrsseeeprsserving reward Rpy analogously to equation 12 and equation 13 This motivated by the analysis done appendix A. combined with the observation that the scale and complexity pick-and-place example is comparable to the scale and complexity the pushing example. In contrast to equation
[3 however, the euclidean distance whether grasp has been established or
d(.,.) also takes into account the binary information not. For PB-RS, we scale the potential function by K = 30. This is done order to ensure that the reward functions of PB-RS and FV-RS are of similar scale. The results for 2 different pick-and-plaae examples are discussed in appendix A.. specifically in figure 6 Here, we measure the asymptotic
distance different agents and rollouts detailed in section 5.2
14

---

Published as a conference paper at ICLR 2021
Tracton comsistently successfur ageens
1.5
Approximate Plan
8075
N5
asymptatic A
60%
No RS, top quartie top
1.0
top quartle
-1.5
200
Number of rollout episodes N
Number of rillout episodes
(a)
(b)
Fraucion of cirtsityyyyyy succesatu aggantss
Moan asymptatic Situncee A-S S,2200
Approximate Plan
No
PB RS
1.5-
60%
FV-RS
1.0-
No RtS, top quartie
0.0
40%.
PB-RS, quartil
quartie
-1.5
Gool
-1.5
0.0
200
400
600
800
1000
200
400
600
800
1000
Number rollout episodes
(d)
Figure 6: Pick-and-place examples. Each row corresponds to a different example. With FV-RS, some agents consistently successful after ca. 300 rollout episodes in both cases. With PB-RS or without reward shaping, none of the agents were able to consistently reach the goal in these experiments. The training progress of the top quartile of agents is significantly faster with FV-RS than with PB-RS or without reward shaping.
1.5
Approximate Plan
Goal
Disk
0.0
End effector
-1.5
0.0
1.5
x
(b)
Figure 7: Robotic pick-and-place task. (a) A disk of radius 0.2 (dark gray) lying on a table of size 3 x 3 (light gray) is supposed to be picked up the red and placed the green position by the spherical end effector (dark gray). (b) Top view of the table with 2-D projection of planned trajectory (x and y coordinates the end effector). The planned trajectory executable the noisy environment.
A.4 ROBOTIC PUSHING EXAMPLES USING PPO
We repeat the experiments presented in appendix A.I Juiig PPO instead of DDPG as RL algorithm. In DDPG, a deterministic policy is learned from off- off-policy data. In contrast to this, PPO is an on-policy algorithm for learning stochastie policy.
15

---

Published as a conference paper at ICLR 2021
We use open-source implementation from Barhate (2020). The actor network outputs mean values between -0.1 and 0.1 for the Gaussian policy, while the standard deviation of the policy output is fixed to 0.015. We use the clipping parameter 0.1 (see |Schulman et al. (2017) For more implementation details, please also refer to the supplementary material.
Since the environment is unchanged, tion 13
the shaping functions defined in equation 12 and equa- The results are presented in figure g The relative advantage of using FV-RS over PB-RS
Fredtio of consituntly successful aquents
1.5
1.00%
Approximate
quartie
80%
PB RS. top quartlle
-X--
PV RS. top quartie
Mian aoympttti distance
0.50
40%
0.5
PB-R5
-1.5
0%
PV-R5
Gool
-1.5
0.0
250
500
75.0
1000
1250
1500
250
500
750
1000
1250
1500
Number of rollout eptsodes N
Number rullout upiicodas M
(a)
(b)
(c)
Fraution of consisterntl succe costu aquats
Mean asymptoti artoncc-. 3ar
Approximate Plan
70%
No RS
60%
PB-RR
1.5
50%
0.0
1.0
30%
20%
0.5
No RS. top quartile
1.0%
PS RS. top quartie
-1.
8.0
FV quartile
-1.5
0.0
1.5
5000
10000
15000
20000
5000
10000
15000
20000
Number of rollout opisodes
Number milour eptsodes
(d)
(f)
Figure 8: Pushing experiments using PPO instead of DDPG as the RL algorithm. (a. b, c) On the simpler example, FV-RS only slightly outperforms PB-RS. (d, e, This difference increases however on the more difficult example. This relative advantage of using FV-RS over PB-RS using PPO is very similar the one reported in figure for DDPG.
with PPO is very similar to the one reported in figure 3 where results for the same examples using DDPG are reported. This relative advantage is relatively small on the simpler example, but increases drastically for the more difficult example.
As side note, the absolute number of samples needed by agent to consistently lear the task typically much higher using the on-policy PPO algorithm. This is especially true for the more difficult example. Another interesting observation that without any reward shaping (No RS), the stochastic PPO policy performs better than the deterministic DDPG policy in figure This is however not the case in the more difficult example.
A.5 PROOF OF THEOREM
We adopt notation from section 4 The largest reward can only be collected if s' is within B. Since M has the optimal final volume G C B and M and AM have the same dynamics T, there exists policy (the optimal policy of M) to drive the state of M to G B in finite time to. The only question that remains is whether it is suboptimal for policy to drive the state of M to G C B if this takes many steps, and whether it might be optimal to stay at a local maximum of R(s a, s').
The maximum return that can collected outside of A/ - 7). On the other hand, directly therefore find
navigating to G C B returns at least 700 1 7). For every 0 < A < 0 1 such that directly navigating to G C TB is favorable under reward R(s, a, s') and discount
16

---

Published as a conference paper at ICLR 2021
well. Once the state is within G, the optimal policy of M can be applied to keep the state within G. Again, this is feasible since M has the optimal final volume G. Thus, M M.
A.6 STEP-WISE REWARD FUNCTION
We discuss a possible relaxation of the lower bound on ? given in corollary 4.1.1 in case more assumptions are made about R. Specifically, we consider the case of a step-wise reward function that the agent can follow monotonically.
We adopt notation from section 4
Definition A.1. Let a reward function R fulfill
Vs,a,s' s' E B:
R(s.a,s')=1 -1
(16)
Vs,a,s' $ B: R(s, a, 6') E {A, A where B C S is non-empty. For E (N{0), call an MDP M monotonically (w, A) controllable with respect to R, iff there exists a policy πt and A such that
(17)
Vso & R, Vk 2 w P(A R(sk; 0k, 8k+1) 2 R(so, 0o, 00, 81)) =1
(18)
where actions and states follow the distribution
I (au, $1, Q1 ...|ss) = II P( ((alss))
(19)
0m0
We call w M's step width and we call A M's step height.
In words, we additionally require that given the dynamics of M, the reward function must be defined in a way that guarantees that the agent can advance to the next "step" within w time steps. We acknowledge that constructing such a reward function might not always be feasible, but it allows us to illustrate the relationship between the lower bound on & and the step width w. The following theorem states this relationship.
Theorem A.1. Let M be an MDP with metric state-space (s, d) and with the sparse reward function [1
i E
R(s, a, s')
(20)
0
else
where B C S is non-empty. Let M have the final volume G [ B. Let R(s, s²) be a reward function that fulfills
Vs,a, EB:
Ris, a, 8') =1
(21)
Vs,a, $ B: R(s, 5') E (A,A?....)
(22)
where 0 < A < 1. Additionally, let M be monotonically (w, A) controllable with respect to R.
Then, for every 0 < A < there exists a discount factor O < & < such that the MDP M corresponding to R and Fy is compatible to M.
Proof. This is special case of theorem 4.1
Corollary A.1.1. In this setting, M is compatible to M, if A1((-11,
Proof. Assume that the agent is in an area where it can collect the reward A The optimal agent has to decide if it advances the next "step" (where it can sustainably collect the reward A k- or if it stays in lower-reward areas. The return of the former is at least A 1/11 7). the return of the latter is at most A / - ()) Thus, the optimal agent will decide to steer towards the next step as long as 5 > 11)
Comparing this to corollary notable special case is w 1. in which there exists a policy so that the reward is increased at every step. In this case, any 7 > 0 is sufficient ensure compatibility.
we see that if w < lo this relaxes the lower bound on 7. A
For reward functions that do not strictly adhere to definition A.I but can be followed in a step- wise manner, the relation stated in theorem A. still qualitatively illustrates the following: The smaller the number of steps after which the agent can advance to a region of higher reward (i.e. the step width w), the more relaxed the lower bound on 7 becomes. In the important case that this step width becomes 1, this lower bound is 0.
17


Reviews:
[{"review_id": "uT65elha1YG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "POST-REBUTTAL UPDATE\n======================\n\nThe rebuttal and resulting changes have addressed most of my concerns, and expanding the alternative reward-shaping aspect of the evaluation has helped too. I've increased the score.\n\n======================\n\n\nSUMMARY\n\nThe paper introduces a new, plan-based reward shaping approach to RL called ASEQ-RS. It is a generalization of potential-based reward shaping, one that doesn't have the same optimality guarantees but empirically facilitates faster policy learning.\n\n\nHIGH-LEVEL ASSESSMENT\n\nThe paper's approach looks interesting, especially empirically. However, I have a number of concerns about the paper's theory: much of it seems to have errors. The paper can't be published with these errors, which is why I'm giving a slightly below borderline score for now. However, these error might be easily fixable. If the authors demonstrate a way to fix them without detracting much from the generality of the results, I'll increase the score, because the approach looks useful in practice.  \n\n\nTECHNICAL ISSUES/QUESTIONS\n\n-- Def. 4.3 seems to have an error, in the sense that it doesn't quite have the interpretation stated in the paragraph below it. If an MDP has G = \\emptyset (which is possible if different optimal policies lead to disjoint parts of the state space), it is asymptotically equivalent to any other MDP ver the same state and action space according to Def. 4.3, but it certainly doesn't mean that optimally behaving in this MDP and some other that has G \\neq \\empyset will have the same result. This may be fixable by excluding G = \\emptyset MDPs from consideration, although I haven't fully verified this.\n\n-- Def. 4.3 is also broken in the sense that the notion of equivalent it introduces is asymmetric, which contradicts the intuitive meaning of equivalence. Perhaps the easiest way to fix this one is to replace the term \"equivalent\" in this definition with something else.  \n\n-- Theorem 4.1's statement is ambiguous: when you say \"Let M be convergent with optimal asymptotic volume G \\subseteq B\", are you assuming that M's asymptotic volume is always a subset of B? Or are you implicitly saying \"*if* M's asymptotic volume is a subset of B, then let's call it G\"? If it's the former, then that assumption is invalid -- due to \\gamma being strictly less than 1, the optimal policy may eventually choose an action that lead to B with some probability and with some probability leads to a region with reward 0 (outside of B).\n\nThis can be quite an issue for Cor. 4.1.1 and Theorem 4.2, which are based on 4.1, and also in practice, because in non-ergodic MDPs with a discount factor the former version of the assumption can easily fail to hold, potenially breaking the paper's main results.\n\n-- Theorem 4.1 loses its meaning if B = emptyset, in a similar way as Def 4.3. \n\n-- The last paragraph on p.4 promises that the bound on gamma can be relaxed by Theorem 4.2, but I can't find a formal result that shows what the new bound on \\gamma as a result of Theorem 4.2 is. This is important because in practice due to issues caused by function approximation, in RL one wants to set \\gamma as low as possible. So what are the implications of Theorem 4.2 for choosing gamma?\n\n \nLanguage errors:\n\n\"worst-case bound to the reward function:\" --> \"worst-case bound on the reward function:\"\n\n\"lower bound to \\gamma\" --> \"lower bound on \\gamma\"\n\n\"upper bound to\" --> \"upper bound on\"\n\n(Please search through the paper and fix all mistakes like the above.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "Sj34a2kMy7Y", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "= Overview = \n\nThe paper proposes \"Asymptotically equivalent reward shaping\", a new reward shaping approach that extent potential-based reward shaping to allow for shaping functions that -- even if eventually altering the resulting optimal policy -- retain key elements in the performance of such policy, namely ensuring that the resulting policy leads the agent to a subset of the states that the original optimal policy does. The paper also proposes a method to compute a shaping function from behavior demonstration.\n \n= Positive points =\n\nThe idea of reward shaping is important in reinforcement learning, as it can have an important impact in terms of sample complexity. As far as I know, this area of research has not seen significant advances or new ideas in recent years. The paper provides a fresh view of this problem, by proposing to alleviate the requirement that the shaped function should lead to the same optimal policies.\n\n= Negative points =\n\nThe proposed approach seems to be restricted to a very narrow class of MDPs. Additionally, the proposed shaping function is presented with little motivation, intuition or discussion whatsoever. Finally, the experimental evaluation is not very convincing, as the proposed approach is compared with \"arbitrary\" potential based shaping functions (more details below).\n\n= Comments = \n\nThe paper addresses a problem that, in my view, is relevant to the RL community and has not seen many advances in recent years. Its premise is that the \"classical\" reward shaping may be too restrictive, in that it requires the optimal policies before and after shaping should be the same. The paper instead proposes to alleviate this requirement, as long as the resulting policies lead to \"similar\" long-term behavior. \n\nThis notion is, in my view, interesting and in line with work on intrinsic motivation, by Barto and collaborators, and in reward optimization conducted by Sorg, Sequeira and others. In this respect, it could be relevant to at least mention this line of work in the paper.\n\nIn addressing reward shaping, however, the paper restricts to problems where the reward is binary (i.e., 0 most of the time, and 1 in some states). These are, essentially, goal-driven MDPs, where the optimal policy just drives the agent towards one of the states with non-zero reward. The paper notes that, if the reward is shaped by providing sufficiently small reward values in the non-goal states and the discount is made sufficiently large, the optimal policy will still lead the agent to one of the goal states. This is a relatively straightforward conclusion, and the whole shaping strategy proposed by the paper follows from this simple observation.\n\nThe paper then proposes a shaping function from a given demonstration (consisting of a sequence of states). Unfortunately, the presented shaping function is introduced with no motivation, intuition, or discussion whatsoever, and one wonders why such shaping function is a good idea.\n\nThe paper concludes with an experimental evaluation section, where the proposed approach is compared against potential-based reward shaping and shown to outperform the latter. However, the potential-based shaping functions used for comparison are introduced in an ad hoc manner, and it is not clear to me why these shaping functions are good baselines for comparison.\n\nFinally, on a small note, I feel that the paper could benefit from cleaning up/streamlining the notation and language. For example, why the proposed notion of \"asymptotic equivalence\" is called asymptotic of equivalence is unclear, since the notion of \"optimal asymptotic volume\", on which the former builds, is defined for a finite time (not asymptotic), and the relation does not seem to be an equivalence (if for no other reason, it does not seem symmetric to me). Definitions 4.1-4.3 make use of heavy notation but translate a very simple notion: that an MDP M is \"asymptotically equivalent\" to an MDP M' if the optimal policy of the former leads the agent to a subset of the goal states of the latter.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GvwSjIoDWlR", "reviewer": "AnonReviewer1", "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": "In this paper the authors introduce an asymptotic-equivalent (ASEQ) reward shaping reinforcement learning algorithm, which, they argue, is a relaxation of potential based reward shaping (PB). The authors present results suggesting that the proposed ASEQ method is significantly better than PB. \n\nThe authors state that this new method is a superset of PB (or a “subclass of reward shaping broader than PB”) which allows for a policy to be determined by shaping rewards on all intermediate states in a trajectory. There is unconvincing details on how this is done (eg. the authors state that it is ‘more direct’). \n\nThe authors make claims that this new method is suitable in difficult exploration problems in high-dimensional states spaces. They do not show evidence to support this claim and evaluate their method in a 10-d state space robotic manipulation task. \n\nThe contributions of this work are stated unconvincingly. For example, claims 1 and 2 are the same. The authors do not compare this method with other learning from demonstration methods (e.g. behavioural cloning or Generative Adversarial Imitation Learning)\n\nDefinition 4.1 is unclear and \\mathcal{G} is undefined. There are assumptions that the authors state about the applicability of this method, such as at the end of section 4.1 regarding the likelihood of an agent leaving a well-defined volume of state space. The authors make claims that their method is asymptotically equivalent, that is in the long run, behaviour in a modified MDP will have the same result in a modified MDP. I would urge the authors to clarify this point. \n\nThe metic state-space (\\mathcal{S}, d) is not well defined in Theorem 4.2. \n\nThe authors present their method as a modification to DDPG, and show that reward shaping leads to better performance on their tasks than no reward shaping. This is a likely outcome, given that they are providing the method with additional information. \n\nI would urge the authors to compare against algorithms which use the same information, and stronger baselines rather than just ablative baselines on their method.  Finally, I do not think that this work is a good fit for ICLR given that it is more related to methods in reward shaping for reinforcement learning as opposed to the topics of more general greater interest to the audience at ICLR. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DAeZkKhOJW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "SUMMARY OF CONTRIBUTION:\n\nThis work presents asymptotically-equivalent (ASEQ) reward shaping as an alternative to potential-based shaping.  ASEQ shaping admits a more general class of augmented reward functions than potential based shaping, at the cost of a weaker notion of equivalence between the classes of optimal policies for the original MDP and the augmented MDP.  ASEQ assumes that the original MDP uses a binary reward function that is 1 for all states in a subset of the state space to which any optimal policy will converge (effectively the \"goal\" of the MDP), and 0 elsewhere.  The theoretical results presented in this work show that for any augmented reward function which is between 0 and 1 outside of the goal region, and for a sufficiently large discount factor, the an optimal policy for the augmented reward will converge to this goal region.  The flexibility of this form of reward shaping with a plan-based shaping reward that provides smaller rewards for reaching waypoints along a path to the goal.  The advantage of this form of shaping reward over more limited potential-based shaping is demonstrated on a set of simulated robotic manipulation tasks.\n\nAREAS OF CONCERN:\n\nOne potential issue with the experimental results is that the potential function used for the baseline is defined identically to the plan-based shaping reward used with ASEQ shaping.  While this is the most direct comparison between the two approaches, it is possible that using potential-based shaping with a simpler potential function, such as the distance between the box and the goal, would lead to better performance for potential-based shaping.\n\nAs reward shaping is a meta-algorithm that can be applied to almost any RL method, it would also be useful to evaluate ASEQ shaping on multiple RL algorithms, not simply DDPG, to show that the benefits of the more flexible class of shaping rewards are not limited to a single class of algorithms.\n\nThere are some places where the notation could be improved:\n  1) The notation in Equations (1) and (2) is somewhat awkward, as q_pi appears to be a distribution over transitions in (1), but is defined as a distribution over entire trajectories in (2).\n  2) It isn't entirely clear what the subscript 'a' of the sets G_a in definitions 4.1 and 4.2 refers to.\n\nCONCLUSION:\n\nWhile the form of shaping reward used in this work is not itself novel, the work does for the first time formally describes the class of problems to which this more general form of reward shaping can be applied, with conditions on the form of the shaping reward that guarantee compatibility with the original task.  The work does have its limitations, both in terms of the class of problems to which ASEQ shaping can be applied, and in terms of the depth of the empirical evaluations, but it will be of value to the community nonetheless.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary:
This paper introduces a novel type of reward shaping (not potential-based) that can work for MDPs with 0/1 rewards (e.g., systems with goal states). I think the paper contains a nice nice of empirical results, clear explanations/insights, and theoretical contributions.
As long as the authors do a good job saying up-front what kinds of MDPs the method does/does not address, this would provide an interesting addition to practical methods for solving sparse-reward RL tasks.
The paper could be strengthened with additional empirical results, but that is almost always true, and I think the number and quality of experiments are well above the bar.
The paper could also be strengthened if it better compared with other ways of using demonstrations. This is done in the text, but not empirically, as the authors wanted to focus on reward shaping methods. I think this is a relatively minor point and does not outweigh the many positives.

Discussion:
One reviewer remains against accepting this paper. I respectfully disagree with their evaluation and unfortunately they did not update their review after the responses. Hopefully they would agree the final version of this paper is indeed a useful contribution.

Recommendation:
I believe this paper should be accepted based on the science. 
Decision: Accept (Poster)