Explicable Reward Design for Reinforcement Learning Agents
Authors: Rati Devidze
Goran Radanovic
Parameswaran Kamalaruban
Adish Singla
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
reward design
explicable reward functions

Abstract: We study the design of explicable reward functions for a reinforcement learning agent while guaranteeing that an optimal policy induced by the function belongs to a set of target policies. By being explicable, we seek to capture two properties: (a) informativeness so that the rewards speed up the agent's convergence, and (b) sparseness as a proxy for ease of interpretability of the rewards. The key challenge is that higher informativeness typically requires dense rewards for many learning tasks, and existing techniques do not allow one to balance these two properties appropriately. In this paper, we investigate the problem from the perspective of discrete optimization and introduce a novel framework, ExpRD, to design explicable reward functions. ExpRD builds upon an informativeness criterion that captures the (sub-)optimality of target policies at different time horizons in terms of actions taken from any given starting state. We provide a  mathematical analysis of ExpRD, and show its connections to existing reward design techniques, including potential-based reward shaping. Experimental results on two navigation tasks demonstrate the effectiveness of ExpRD in designing explicable reward functions.

Explicable Reward Design for Reinforcement Learning Agents
Rati Devidze' rdevidze mapissss.oiggggg
Goran Radanovic' graddnovicemmiisss..or
Parameswaran Kamalaruban" kparameswaran (wrriettttrruuuuu
Adish Singla'
adishs @ mppissssorg
Max Planck Institute for Software Systems (MPI-SWS), Saarbrucken, Germany
"The Alan Turing Institute, London, UK
Abstract
We study the design of explicable reward functions for reinforcement learning agent while guaranteeing that an optimal policy induced by the function belongs to set of target policies. By being explicable, seek to capture two properties: (a) informativeness so that the rewards speed up the agent's 's convergence, and (b) sparseness proxy for of interpretability of the rewards. The key challenge is that higher informativeness typically requires dense rewards for many learning tasks, and existing techniques do not allow one to balance these properties appropriately. In this paper, we investigate the problem from the perspective of discrete optimization and introduce novel framework, EXPRD, to design explicable reward functions. ExPRD builds upon an informativeness criterion that captures the bottimattt of target policies at different time horizons in terms of actions taken from any given starting state. We provide a mathematical analysis of ExPRD, and show its connections to existing reward design techniques, including potential- based reward shaping. Experimental results on two navigation tasks demonstrate the effectiveness of ExPRD in designing explicable reward functions.
Introduction
A reward function plays the central role during the learning/training process of reinforcement learning (RL) agent. Given a "task" the agent is expected to perform (i.e., the desired learning outcome), there are typically many different reward specifications under which an optimal policy has the same performance guarantees on the task. This freedom in choosing the reward function, in turn, leads to the fundamental question of reward design: What are different criteria that one should consider in designing a reward function for the agent, apart from the agent's 's sinal outpui policy? ? [1-3].
One of the important criteria is informativeness, capturing that the rewards should speed up the agent's convergence [1-6]. For instance, major challenge faced by an RL agent because of delayed rewards during training; in the worst-case, the agent's convergence is slowed down exponentially w.r.t. the time horizon of delay [7]. In this case, we seek to design a new reward function that reduces this time horizon of delay while guaranteeing that any optimal policy induced by the designed function is also optimal under the original reward function [3]. The classical technique of potential-bast -aaed reward shaping (when applied with appropriate state potentials) indeed allows to reduce this time horizon of delay to 1; see [3, 8] and Section 2. With 1, it means that globally optimal actions for any state are also myopically optimal, thereby making the agent's learning process trivial.
While informativeness an important criterion, it is not the only critcrion to consider when designing rewards for many practical applications. Another natural criterion to consider is sparseness as proxy for ease of interpretability of the rewards. There are several practical settings where sparseness and interpretability of rewards important, discussed next. The first motivating application is when
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

rewards are designed for human learners who are learning to perform sequential tasks, for instance, in pedagogical upplications such as educational games [9]. virtual reality-based training simulators [10. 111, and solving open-ended problems (e.g., block-based visual programming [12]). In this context, tasks can be challenging for novice learners and teacher agent can assist these learners by designing explicable rewards associated with these tasks. The second motivaring application is when rewards are designed for complex compositional tasks in the robotics domain that involve reward specifications in terms of logic, automata, or subgoals [13, 1he-these specifications induce form of sparsity structure on the underlying reward function. The third motivating application is related to defense against reward- reward-poisoning poisoning attacks in RL (see [15-19]) by designing structured and sparse reward functions that are easy to debug/verifyy Beyond these practical settings, many naturally occurring reward functions in real-life tasks are inherently sparse and interpretable, further motivating the need to distill these proper- ties in the automated reward design process. The key challenge is that higher informativeness typically requires dense rewards for many learning tasks for instance, the above-mentionel potential-base based shaped rewards that achieve a time horizon of 1 would require most of the states be associated with some real-valued reward (see Sections 2 and 4). To this end, an important research question that seek to address is: How to balance these two criteria of informativeness and sparseness in the reward design process while guaranteeing an optimality criterion on policies induced by the reward function?
In this paper. we formalize the problem of designing explicable reward functions, focusing on the criteria of informativeness and sparseness. We investigate this problem from an expert/teacher's 's point of view who has full domain knowledge (in this case, an original reward function along with optimal policies induced by the original function), and seeks to design new reward function for the agent- see Figure and further discussion in Section 5 on expert-driven vs. agent-driven reward design. We tackle the problem from the perspective of discrete optimization and introduce novel framework, EXPRD, to design reward functions. ExPRD allows us to appropriately balance informativeness and sparseness while guaranteeing that an optimal policy induced by the function belongs to a set of target policies. ExPRD builds upon an informativeness criterion that captures the (sub- joutmooptimaliyy of target policies different time horizons from any given starting state. Our main contributions are:"
I. We formulate the problem of explicable reward functions to balance the two important criteria of informativeness and sparseness in the reward design process. (Sections 2 and 3.1)
II. We propose a novel optimization framework, ExPRD, to design reward functions. As part of this framework, we introduce new criterion capturing informativeness of reward functions that is amenable to optimization techniques and is of independent interest. (Sections 3.2 and 3.3)
III. We provide a detailed mathematical analysis of ExPRD and show its connections to popular techniques, including pptential-basee reward shaping. (Sections 3.3 and 3.4)
IV. We provide practical extension to apply our framework to large state spaces. We perform extensive experiments on two navigation tasks to demonstrate the effectiveness of EXPRD in designing explicable reward functions. (Sections 3.5 and 4)
2 Problem Setup
Environment. An environment is defined as Markov Decision Process (MDP) M (S,A,T, Rt,, where the set of states and actions are denoted by S and A respectively. T S x A- [0, 1] captures the state transition dynamics, i.e., T s, a) denotes the probability of landing in state s' by taking action a from state s. Here, 7 is the discounting factor. The underlying reward function is given by R S x A + [- Rmmxx Rmaxx for some Ruax > O. We interchangeably represent the reward function by a vector R E T Si-AA, whose (s |Al + a)-th entry is given by R (s. a). We define the support of R as supp(R) = (s (8:8E& S, R (8, a) + O for some a E A), and the fo-nrmm of R as ||]] := (supp(R).
Preliminaries and definitions. We denote a stochastic policy т S A (A) as a mapping from state to probability distribution over actions, and deterministic policy π: S + A as mapping from a state to an action. For any policy ग, the state value function V and the action value function Q% in the MDP M are defined as follows respectively: V (s) = E 2 as)ss = s, T, Freee = 8, ag a, T, T). Further, the optimal value functions are given by V (s) = sup, (8) and Q (s,a) = sup, ²% (s,a). There always exists a
and Q% (s.a) E 1 =
'Github repo:
wwwp::/oeeeeeeecpiceeeeeeeeeeeee design_codee
2

---

Task specified as an MDP M with given reward function R
Teacher computes optimal Qx and IT'
Teacher designs a new explicable
RL agent learns optimal #* e Il' w.r.t.
w.r.t. R
reward function R
(a)
(b)
(c)
(d)
Figure 1: Illustration of the explicable reward design problem in terms of a task specified through MDP M, an RL agent whose objective is to perform this task, and teacher/expert whose objective is to help this RL agent. (a) MDP M with given reward function I specifying the task the RL agent expected to perform: (b) The teacher computes optimal action value function Qoo along with the set of optimal policies II w.r.t. R; (c) The teacher designs a new explicable reward function R for the RL agent; (d) The RL agent trains using the designed reward R and outputs a policy At from the set of optimal policies II w.r.t R. Our framework designs an explicable reward function / with three properties: invariance, informativeness, and sparseness; see main text for formal definitions of these properties.
deterministic stationary policy x that achieves the optimal value function simultaneously for all 8 E S [7, 20], and we denote all such deterministic optimal policies by the set TT* := { S + A s.t. V (s) = V (s) Vs E S}. From here onwards, we focus on deterministic policies unless stated otherwise. For any ιT and R, we define the following quantities that capture the co-step (global) optimality gap and the 0-step (myopic) optimality gap of action a at state 8, respectively:
6% (s. == (8,
Q (s, a), and oß (s, a) == Q (s, (6)) - Q8 a), Vs S, E A,
where (5, a) R (s, a) is the 0-step action value function of policy æ. The 8 (s, a) values are same for all E II", and we denote it by &t (s, = V (s) Q (s, a): however, this is not the case with 6Ø (s, a) values in general. For any state 8 E S and a set of policies II, we define II := (a: a = (s), π E II]. Then, we have that (s, a) = 0, V's E E IT:.
Explicable reward design. Figure 1 presents an illustration of the explicable reward design problem that we formalize below. A task is specified an MDP M with given goal-based reward function R where R has non-zero rewards only goal states G C S, i.e., R (s. a) O, Vs E S\ E A. Many naturally occurring tasks (see Section for motivating applications) are goal-based and challenging for learning an optimal policy when the state space S is very large. In this paper, we study the following explicable reward design problem from an expert/teacher's 's point of view: Given R and the corresponding optimal policy set IT" w.r.t. R as the input, the teacher designs new reward function R with criteria of informativeness and sparseness while guaranteeing an invariance requirement (these properties are formalized in Section 3). Informally, the invariance requirement is that any optimal policy learned using the new reward R belongs to the optimal policy set II" induced by R.
Typical techniques for reward design and issues. Given set of important states (subgoals) in the environment, one could design handcrafted reward function RERAFT by assigning non-zero reward values only to these states. Even though this simple approach produces a reward function with a specified sparsity level, it often fails to satisfy the invariance requirement. some well-known "reward bugs" that can arise in this approach and mislead the agent into learning sub-optimal policies (see [2. 3D. In the seminal work [3], the authors introduced the potential-base reward shaping (PBRS) method to alleviate this issue. The reward function produced by the PBRS method with optimal value function Voc under I as the potential function is defined as follows:
particular, there are
RPbRS (s, a) = (s,a) + ΣT (,)) V (5') V. (8).
e'ES
The set of optimal policies N' induced by RYERS is exactly equal to the set of optimal policies I'' induced by Tt since 5x (s, a)= = &5 (s, a) for all x E IT" [3]. In addition, for any state 8 E S, globally optimal actions II,, C A under It are also myopically optimal under APARS since 0ī (s, a) 6 (s, a) for all II" [3, 8] - this leads to a dramatic speed-up in the learning process. However, the potential- based reward shaping produces dense reward function which is less interpretable (see Section 4).
In the rest of the paper, the quantities defined corresponding to R = R are denoted by an overline, e.g., the optimal policy by II" and the co-step optimality gaps by 8x.; the quantitics defined corresponding to R. == R are denoted by widehat, e.g., the optimal policy set by fT*.
3

---

3 Our Reward Design Framework EXPRD
In Sections 3.1, and 3.3, we propose an optimization formulation and a greedy solution for the explicable reward design problem. In Section 3.4, we provide a theoretical analysis of our greedy solution. In Section 3.5, we provide a practical extension to apply our framework to large state spaces.
3.1 Discrete Optimization Formulation
Given R and the corresponding optimal policy set IT,, we systematically develop discrete optimiza- tion framework (EXPRD) to design explicable reward function ft (see Figure 1).
Sparseness, informativeness, and invariance. The sparseness of the reward function R is captured by supp(R), ()). In Section 3.2, we formalize informativeness criterion [R) of R that captures how hard/easy it to learn an optimal behavior induced by R. We explicitly enforce the invariance requirement (see Section 2) for the new reward by choosing a set of candidate policies II" C II", and satisfying the following (Bellman-optimae optimalityy conditions:
(s. a(s,a) t Σ T(s 1o (s', (s)),, (s), Va E, S E (C.1)
S'ES
Th (x, 2 Ozd + (x),,, Va E E E
(C.2)
where (s) = min AEAT (s, S.3 The above conditions guarantee that any optimal policy induced by R is also optimal under R. i... I1 C c C II'. Here, the set 11 C II' is used reduce the number of constraints. Note that for the potential-based shaped reward RPRRS, have ft- =
Maximizing informativeness for a given set of important states. When a domain expert provides us set of important states (subgoals) in the environment [21-24], want to this set in principled way design reward R, while avoiding the "reward bugs" that can arise from hand- crafted rewards RERAFT. To this end, for any given set of subgoals C SYG, we optimize the informativeness criterion ((R) while satisfying the invariance requirement:
g(2) =
max R:supp ZUG
I(R)
subject to conditions - (C.1)-(C.2) with R replaced by R hold [R(sa)) S Rmaxs Vs E S.a E A.
(PI)
Let R(22) denote the R that maximizes ( Let R C RISH-A be a constraint set on R that captures only the conditions (C.1) (C.2) and the Rmax bound.
Jointly finding subgoals along with maximizing informativeness. Based on (PI), we propose the following discrete optimization formulation that allows us to select set of important states (of size B) and design a reward function that maximizes informativeness automatically:
2: 2 9(Z).
(P2)
We incorporate prior knowledge about the quality of subgoals using set function D 2 IR (we assume D to be a submodular function [25]). Finally, the full ExPRD formulation is given by:
max Z: E.
g(2) D(ZUG), for some 0.
(P3)
We study the problems (P1), (P2), and (P3) in the following subsections.
Note that the true action values Q are used the conditions (C.1) - (C.2) to obtain the terms 5 (8, a). A IT. and IT'. However, when only have an approximate estimate of Q we adapt (C.1) (C.2) appropriately with approximate versions of 0= (s, a). A'Il,, and 11¹

---

3.2 Informativeness Criterion
Understanding the informativeness of reward function is an important problem, and several works have investigated it [4, 5, 26-28]. Our goal is to define an informativeness criterion that is amenable to optimization techniques. As noted in Section 2, for any policy E IT", O-step and oa-Step optimality gaps induced by RPBES (s, a) 8% (s, a) 8- (s, a). For any reward function one could ask how much these two quantities could differ, and even consider the intermediate cases between O-step and oc-step optimality, Inspired by the h-step optimality notions studied in [4, 26], we define the h-step action value function of any policy as Q7, (s E - 7 R(ss,, 0z)]so 8, ag a, T and it satisfies the following recursive relationship: (s, R(s,a) + E.'s (( (o__(6''m(ss))
all equal to co-step optimality gaps induced by R. i.e.,
Let H be set of horizons for which we want maximize informativeness. For any policy and reward function R, we define the following quantity that captures the h-step optimality gap of action state s: 07 (s, a): = Q7, (s, (8)) Q7 (s, a), Vs E E,Sa a A, h E H. Later, in the proof of Proposi- tion 2, we show that 5% (s, a) is linear in R, i.e., (s, a) (Whs(s,a) R) for some vector Wh;((.a) RISH-A Interestingly, the following proposition states that, for any policy E II and any h, the h- step optimality gap induced by RPBRS given in (1) is equal to the oc-step optimality gap induced by Rt Proposition 1. The goal-based reward function R. and the potential-base -baiiddl--aaddd--e shaped reward function RPERS given in (1) satisfy the following: 87 (s. = 5x (s. Ys S,a A, II h H.
Let 8 R + be monotonically non-decreasing concave function. Then, based on the htstep optimality gaps, we define the informativeness criterion of the reward R as follows:
((RR) = Σ ΣE Σ
((8% (s)
ætem! MEA #ES dEA;iI,
From here onwards, let 7 be Te in the problem (P1). As an example for f, we consider the negated hinge loss given by lig (8(s, a)) == max(0, 80 (s. a) a)). By Proposition 1, we have that Ling (RPBRR)= = 0, and Lim (R) < 0 for any other R, i.e., REBRS achieves the maximum value of lime
3.3 Iterative Greedy Algorithm
First, we show that the problem (P1) can be efficiently solved using the standard concave optimization methods to find R(2) for any given 2 C S:
Proposition 2. For any given Z C S'G the problem (P1) is a concave optimization problem in R E IISH-A with linear constraints. Further, the feasible set of the problem (P1) is non-empty.
Then, inspired by the Forward Stepwise Selection method from [29]. we propose an iterative greedy solution (see Algorithm 1) to solve the problems (P2) and (P3). To compute the incremental gain at each step, we would need to solve the concave optimization problem (PI) for different values of Z. The problem (PI) has |S] |A| optimization variables and ((S) |A] [IT' HH) constraints.
Algorithm 1 Iterative Greedy Algorithm for EXPRD
1: Input: MDP M = (S, T. 7, R), 8' (8,a) a) values, sets IT",, IT!, G. H. sparsity budget B
2: Initialize: Zo + 0
3: for k 1.2....; do
4: 24 + arg max B._ g(Zz (ww.apa....aauuu..aa.aauaa..0000
5: 2x + Z U {z+)
6: Output: En and the corresponding optimal reward function R(2a)
3.4 Theoretical Analysis
Here, we provide guarantees for the solution returned by our Algorithm 1. Below, we give an overview of the main technical ideas, and leave detailed discussion along with proofs in the
5

---

Appendix. For some 2 0, let (R) == [((R) - - be the regularized informativeness
criterion. We define normalized set function : + R as follows:
max 1(2) = TUSu
(TE) - ( + X ( -
(2)
where R!!0) = arg (taup (B). Note that the regularized variant (1z replaced by =1=h of the optimization problem (P3) is equivalent to max (Z). For given sparsity budget B. let 2 be the set selected by our Algorithm 1 and 1 be the optimal set that maximizes the regularized variant of problem (P3). The corresponding values of these sets are denoted by fCready and f& JorT respectively; in the following. we are interested in comparing these two values. The problem (P3) is closely related to the subset selection problem studied in [29] with a twist of an additional constraint set R (see the discussion after (PI)), making the theoretical analysis more challenging. Inspired by the analysis in [29], we need to prove a weak form of submodularity [25. 30] for f (since D is already a submodular function, we need to prove this for the case when À 0). To this end, we require the regularized informativeness criterion I. to satisfy certain structural assumptions. First, we define the restricted strongly concavity and restricted smoothness notions of a function that are used in our analysis.
Definition (Restricted Strong Concavity, Restricted Smoothness [31]). A ffuntionn L R|SH-A + R is said to be restricted strong concave with parameter ma and restricted smooth with parameter Ma on a domain Q C I (| x (R|S|-IAA for all (æ, y) E Q2
mn 2
- x12 z - (VL
-
x) 2 Ma
ll x122
2
For any integer k we define the following two sets: S4 == {(x, v) | S k. Ivllo S ki || - vllo S k. x. y E R.,, and Ω4 := {(xx v) ||=rllo S k. llvllo S k, || vllo S 1,,,V E RJ. Let my 10 and Mg = Ma, (similarly we define mh and Mg).
When there is R E R constraint in (2), the following assumption on the regularized informativeness criterion is sufficient to prove the weak submodularity of / [29]: Assumption 1. The regularized informativeness criterion 14 is 12 rrestricted strongly concave and M2B+igg smooth on 8228-191-
However, due to the additional R E R constraint, we need to enforce further requirements on 1. formally captured in Assumption 2 provided in the Appendix; here, we discuss these requirements informally. Let 2 be any set such that 2 C S'G and V let (R(()) be the gradient of the regularized informativeness criterion at the optimal reward R(2) Then, we need to ensure the following: (i) the norm of the projection of V ( on (z ()) is upper-bounded. captured by d (ii) the f--norm of the projection of (R(2)) on any j E (Z()) is lower-bounded, captured by dmon, and (iii) the components of the optimal reward R(2) outside (ZUg) do not lie in the boundary of R, captured by k. Then, by using Assumption 1 and Assumption (see Appendix), we prove the weak submodularity of f. Finally, by applying Theorem 3 from [29], we obtain the following theorem: Greedy 2
Theorem 1. Let 1ets satisfies Assumption I and Assumption 2 requirements. Then, we have J (1-e-7) SOPT, where 7
k-Man+lel
[quaus>
M28+10l
We provide Assumption 2 and a detailed proof of the theorem in the Appendix.
3.5 Extension to Large State Spaces using State Abstractions
This section presents an extension of our ExPRD framework that is scalable to large state spaces by leveraging the techniques from state abstraction literature [32-34]. We use an abstraction S: + Xz. which is a mapping from high-dimensional state space S to a low-dimensional latent space Xz. Let o (x) := (s E S ((s) = x} Vx E Xz. and M == AS, R). We propose the following pipeline:
1. By using M and d. we construct an abstract MDP Me = (Ko, 7, Rs) as follows, Va, x' E Rg E A: To(2' [r, = (क) Exco-1(a) Eves-1(a)) T(s'|s, a). and (x, =
(m) Eseo 2(x) R(s,a) a). We compute the set of optimal policies IT,, for the MDP M

---

2. We run our ExPRD framework on M with IIf = H and the resulting reward is denoted Rs.
3. We define the reward function R on the state space S as follows: R(s, a) Ro(()s))a).
By assuming certain structural conditions on e formalized in the Appendix, we can show that any opti- mal policy induced by the above reward R acts nearly optimal w.r.t. R. This pipeline can be extended to continuous state space as well, similar to [34-36]. We provide more details in the Appendix.
4 Experimental Evaluation
In this section, we evaluate EXPRD on two environments: ROOMSNAVENV (Section 4.1) and LINEKEYNAVENY (Section 4.2). ROOMSNAVENV corresponds to navigation task in grid- world where the agent has to learn policy to quickly reach the goal location in one of four rooms, starting from an initial location. Even though this environment has small state space, it provides a very rich and an intuitive problem setting to validate different reward design techniques, and variants of ROOMsNAV ENV have been used extensively in the literature [14, 21, 22, 37-40). LINEKEYNAVENN corresponds to navigation task in a -ie-dimensional space where the agent has to first pick the key and then reach the goal. The agent's location in this environment represented as a point on a line segment. Given the large state space representation, it is computationally challenging to apply the reward design technique from Section 3.3 and we use the state abstraction-basee extension of our framework from Section 3.5. This environment is inspired by variants of navigation tasks in the literature where an agent needs perform sub-tasks [3, 41]. We give an overview of main results here, and provide more detailed description of the setup and additional results in the Appendix.
4.1 Evaluation on ROOMSNAVENV
ROOMSNAVENV (Figure 2). We represent the environment as an MDP with 8 states each corresponding to cells in the grid- world indicating the agent's current location (shown as "blue- circle"). Goal (shown "green-star") is located at the top-right corner cell. The agent can take four actions given by A := {"up", "left", "down", "right"). An action takes the agent to the neighbouring cell represented by the direction of the action; how- ever, if there is a wall (shown "brown-segment" ", the agent stays at the current location. Furthermore, when an agent takes an action A, there is Prand probability that action d' E AY \ {a} will be executed instead of a. In addition to these walls, there are a few terminal walls (shown episode-at at the bottom-left corner cell, "left" and "down" actions terminate; at the top-right corner cell, "right" action terminates. The agent gets a reward of Rmax after it has navigated to the goal and then takes a "right" action (i.e., only one state-action pair has a reward); note that this action also terminates the episode. The reward is for all other state-action pairs and there a discount factor y. This MDP has |S| = 49 and [A| = 4; we set Prand = 0.1, Rmax 10, and = 0.95 in our evaluation.
Figure 2: ROOMSNAVENV
"thick=red-segmenn") that terminates the
Techniques evaluated. We consider the following baselines: (i) RORIG == R. which simply represents default reward function, (ii) ΠPARR obtained via the PBRS technique with the optimal value function V w.r.t. R (see Section 2), (iii) RECAFT that design manually (see Section 2 and description below), and (iv) RPRRS-CUAFT(RR (B=5) obtained via the PBRS technique with the optimal value function w.r.t. RCKAFT instead of V [42]. To design RERAFT. we first hand-crafted a set function D that assigns scores to the states in the MDP, e.g., the scores are higher for the four entry points in the rooms. In general, one could learn such D automatically using the techniques from [21-24]- see full details about D in the Appendix. Then, for a fixed budget B, we pick the top B states according to the scoring by D and assign reward of +1 for optimal actions and -1 for others. For the evaluation, we use B and denote the function as RCRAFT(B=S)- Note that apart from B states, RCRAIT(=55) also has a reward assigned for the goal state taken from R.
'The reward shaping method in [42] is based on the PBRS technique and leads to dense reward functions. However, their method is more practical as it does not require solving the original task w.r.t. R.
7

---

ES & -2
Ex 14-3)
PURS
CRAFT (0--1)
Ex (1
POKS-CRAI
Expestol roward
left
Epasode
down
right
down
right
down
right
(a) Convergence
(b) RONG
(c)
APaRS
(d) (B
Figure 3: Results for ROOMSNAVENV (a) shows convergence in performance of the agent w.r.t. training episodes. Here, performance is measured as the expected reward per episode computed using Te: note that the x-axis is exponential in scale. (b-d) visualize the designed reward functions RORGG RPBRS. and TEXPRD(B=G,A=1)) These plots illustrate reward values for all combinations of S x A shown four 7 7 grids corresponding to different actions. Blue color represents positive reward, red color represents negative reward, and the magnitude of the reward is indicated by color intensity. As an example, consider "right" action grid for RORI in (b) where the dark blue color in the corner indicates the goal. To increase the color contrast, we clipped rewards in the range [-4, +-4] for this visualization though the designed rewards are in the range [- 10, +00. See Section 4. for details.
The reward functions REXeRD designed by our EXPRD framework are parameterized by budget / and hyperparameter A. For A, consider two extreme settings: (a) À 0 where the problem (P3) reduces to (P2), and (b) À - oc where the problem (P3) reduces to (P1) corresponding to the reward design with subgoals pre-selected by the function D. We use the same function D that we used for RERAFT above. For budget B, we consider values from {3, 5, [S]]. particular, we evaluate the following REXERD(B=S..CC
BExeRD(B==.A==0) and REXPRD(B=1S) (S1)), A=0)) For the evaluation this section, we use the following parameter choices for ExPRD: H (1,4, 1,8, 8, 16, 32), L the negated hinge loss Eng. and II contains only one policy from IT".
reward functions: REXPRD(B=5.2--8
Results. We use standard Q-learning method for the agent with learning rate 0.5 and exploration factor 0.1 [7]. During training, the agent receives rewards based on R, however, is evaluated based on R. A training episode ends when the maximum steps (set to 50) is reached or an agent's action terminates the episode. All the results are reported as average over 40 runs and convergence plots show mean with standard етгоr bars. The convergence behavior in Figure 3a demonstrates the effectiveness of the reward functions designed by our EXPRD framework. Note that RCRAFT(B=5))
leads sub-optimal behavior due to "reward bugs" (see Section 2), whereas REXPRD(B=S. fixes this issue using the same set of subgoals. ExPRD leads to good performance even without domain knowledge (i.e., when À 0), e.g., the performance corresponding
BBx,)D) is comparable to that of REXPRD( - The visualizations of RORIG. RPERS- and (E)-RD(B-S.A-0)) in Figures 3b, 3c, and 3d highlight the trade-off's in terms of sparseness and interpretability of reward functions. The reward function BBS.)R designed by our ExPRD framework provides good balance in terms of convergence performance while maintaining high sparseness. Additional visualizations and results are provided in the Appendix.
4.2 Evaluation on LINEKEYNAVENT
LINEKEYNAVENT (Figure 4). We represent the environment as MDP with S states corresponding the agent's status comprising of
the current location (shown as "blue-circle" and is a point x in [0, 1) and a binary flag whether the agent has acquired a key (shown as "cyan-bolt"). Goal (shown as "green-star") is available in locations on the segment [0.9, 1), and the key available in locations on the segment 0.2). The agent take three actions given by A = ("left", "right", "pick"). "pick" action does not change the agent's location, however, when
Figure LiNEKRy
As discussed in Sections and 2, ReeRs designed using V makes the agent's learning process trivial.

---

PHRS
Expected reward
14
20 1K
1K
DK
2
Episode
0.0
0.25
0.5
0.75
1.0
0.0
0.25
0.5
0.75
1.0
0.0
0.25
0.5
0.75
1.0
(a) Convergence
(b) Ross
(c) ReARS
(d) RExeRD(D=SA
Figure 5: Results for LINEKEYNAVENT (a) shows convergence in performance of the agent w.r.t. training episodes. Here, performance is measured as the expected reward per episode computed using R. (b-d) visualize the designed reward functions RORIa. RPRRS. and =B These plots illustrate reward values for all combination triplets, i.e., agent's location on the segment [0.0, 1.0] (shown horizontal bar), agent's status whether it has acquired key not (indicated as 'K' or "-", and three actions (indicated as ' for "left", 'r' for "right", 'p" for "pick"). We use color representation similar to Figure 3, and clipped rewards in the range [-3, +3] to increase the color contrast for this visualization. As an example, consider 'rK' bar for RONG (b) where the dark blue color on the segment [0.9, 1] indicate the locations with goal. See Section 4.2 for details.
exccuted in locations with availability of the key, the agent acquires the key; if agent already had a key, the action does not affect the status. A move action of "left" or "right" takes the agent from the current location the direction of move with the dynamics of the final location captured by two hyperparameters. (Aa.1: Au.2); ; for instance, with current location x and action "left", the new location x sampled uniformly among locations from (x A,,1 2,,2) 2) to (x A.,1 2a.2). Similar to ROOMSNAVENY, the agent's move action is not applied if the new location crosses the wall, and there Prand probability of random action. The agent gets reward of Rmax after has navigated to the goal locations after acquiring the key and then takes "right" action; note that this action also terminates the episode. The reward 0 elsewhere and there is discount factor y. We set Prand 0,1, Rmax 10, 7 0.95, A 0.075 and A,, 0.01.
Techniques evaluated. The baseline Rowa R represents the default reward function. We evaluate the variants of RYBRS and REXERD using an abstraction. For a given hyperparameter
(0, 1), the set of possible locations X are obtained by a-level discretization of the line segment from 0.0 to 1.0. leading to a 1/2 set of locations. For the abstraction & associated with this discretization [43], the abstract MDP M (see Section 3.5) has | 2/a and |A|] 3. We use a 0.05. We compute the optimal state value function in the abstract MDP M lift the original state space via Φ and use the lifted value function as the potential to design RPBRS [35]. We follow the pipeline in Section 3.5 to design R in the subroutine, we run ExPRD on M & for budget B = 5 and full budget B |/ we set À = 0. For other parameters (H, l, and IT'), we use the same choices as in Section 4.1.
The agent uses Q-learning method in the original MDP M by using fine-grained dis- cretization of the state space; rest of the method's parameters are same as in Section 4.1. All the results are reported as average over 40 runs and convergence plots show mean with standard error bars. Figure 5a demonstrates that all three designed reward Munctions-Rpped REXeRD( (BxXPR((==SA=00)) REXORD(
Results.
substantially improves the convergence, whereas the agent is not able to learn under RogIa- Based on the visualizations in Figures 5b, 5c, and 5d, RE provides good balance between convergence and sparseness. Interestingly. REXeRD( (==) assigned high posi- tive reward for the "pick" action when the agent the locations with key (see 'p-' bar in Figure 5d).
Related Work
Potential-based reward shaping. Introduced in the seminal work of [3], potential-based reward shaping one of the most well-studied reward design technique (see [8, 14, 37, 38, 40, 44, 45, 45- 48]). As we discussed in Section 2, the shaped reward function RPERS obtained by modifying R using a state-dependent potential function. The technique preserves strong invariance property:

---

policy x is optimal under RPERS itf it is optimal under R. Furthermore, when using the optimal value- function Vo under R as the potential function, the shaped rewards achieve the maximum possible informativeness as per the notion we use in EXPRD. To balance informativeness and sparseness, our framework EXPRD can be seen as relaxation of the potential-based shaping in the following ways: (i) EXPRD provides a guarantee on preserving a weaker invariance property whereby an optimal policy under REXERD is also optimal under R: (ii) EXPRD finds REXPRD that maximizes informativeness under hard constraints of preserving this weaker policy-invariant property and a given spareness-level.
Optimization- based techniques for reward design. Beyond potential -based shaping, we can formulate reward design techniques for reward design are popularly used in data poisoning attacks where an attacker's ' goal is to minimally perturb the original reward function to force the agent into executing a target policy chosen by the attacker [17-19]. Our EXPRD framework builds on the optimization framework of [17-19]. The key novelty of EXPRD is that optimize for informativeness of the reward function under a sparseness constraint, which makes our problem formulation much more challenging.
optimization problem [15-19]. In particular, aptimization-based
Agent-driven reward design. An important categorization of reward design techniques is based on who is designing the rewards and what domain knowledge is available. Agent-driven reward design techniques involve reinforcement learning method where agent self-designs its own rewards during the training process, with the objective of improving the exploration and speeding up the convergence [6, 49-53]. These agent-driven techniques intrinsic rewards based on exploration bonus [49, 50, 54], designing rewards using some additional domain knowledge [51], and using credit assignment to create intermediate rewards [6, 52].
wide-variety of ideas such as designing
Expert-driven reward design. In contrast to agent-driven techniques, we have expert-driven reward design techniques where an expert/teacher with full domain knowledge can design a reward function for the agent [1,3, 14-19, 48). Our ExPRD framework falls into the category of teacher-driven reward design. The above-mentioned techniques of potential- potential-based reward shaping and citiiizzation-based techniques can be seen as expert-driven reward design techniques; however, the distinction between expert-driven and agent-driven techniques can be blurry at times when one uses expert-driven technique with minimal domain knowledge (e.g., when using approximate potentials [3]).
Reward automatas, landmark- rewards, and subgoal discovery. Our ExPRD framework also connected to techniques that specifyy rewards using higher-level abstract representations of the environment including symbolic automata and landmarks [13, 14, 37, 40, 55, 56). In recent works [13, 14, 55, 56), potential-basee reward shaping technique has been used with automata-based rewards to design interpretable and informative rewards. While similar in the overall objective, our work is technically quite different and our proposed optimization framework to reward design can be seen as complementary to these works. Another relevant line of work focuses automatic discovery of subgoals in the environment [21-24] - these works are complementary and useful as subroutines in our framework by providing prior knowledge about which states are important for assigning rewards.
Conclusions
We developed a novel optimization framework, EXPRD, to design explicable reward functions in which we can appropriately balance informativeness and sparseness in the reward design process. As part of the framework, we introduced a new criterion capturing informativeness of reward functions that is of independent interest. The mathematical analysis of ExPRD shows connections of our framework to the popular reward-design techniques, and provides theoretical underpinnings of expert- driven explicable reward design. Importantly, ExPRD allows one go beyond using potential function for principled reward design, and provides a general recipe for developing an optimization- based reward design framework with different structural constraints. We also provided practical extension to apply our framework in environments with large state spaces via state abstractions.
To make our framework more scalable, we plan to investigate alternate formulations of the reward design problem that avoids enumerating all the constraints explicitly (see Section 3). There are several promising directions for future work, including but not limited to the following: (a) using combination of our optimization-base reward design technique with automata- well as other structured rewards, (b) extending our framework for agent-driven reward design, (c) applying our framework in a transfer setting using techniques from [42, 57]. and (d) investigating the usage of our informativeness criterion for discovering subgoals.
rewards as
10

---

References
[1] Maja J. Mataric. Reward Functions for Accelerated Learning. In ICML, pages 181-189, 1994.
[2] Jette Randløv and Preben Alstrøm. Learning to Drive a Bicycle Using Reinforcement Learning and Shaping. In ICML, pages 463-471, 1998.
[3] Andrew Y. Ng. Daishi Harada, and Stuart J. Russell. Policy Invariance Under Reward Transfor- mations: Theory and Application to Reward Shaping. In ICML, pages 278-287, 1999.
[4] Adam Laud and Gerald DeJong. The Influence of Reward on the Speed of Reinforcement Learning: An Analysis of Shaping. In ICML, pages 440-447, 2003.
[5] Falcon Z. Dai and Matthew R. Walter. Maximum Expected Hitting Cost of Markov Decision Process and Informativeness of Rewards. In NeurIPS, pages 7677-7685, 2019.
[6] Jose A. Aijona-Meding Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brandstetter, and Sepp Hochreiter. RUDDER: Return Decomposition for Delayed Rewards. In NeurlPS, pages 13544-13555, 2019.
[7] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
[8] Haosheng Zou, Tongzheng Ren, Dong Yan, Hang Su, and Jun Zhu. Reward Shaping via Meta-Learming. CoRR, abs//190.093300 2019.
[9] Eleanor O' O'Rourke, Kyla Haimovitz, Christy Ballweher, Carol S. Dweck, and Zoran Popovic. Brain Points: A Growth Mindset Incentive Structure Boosts Persistence in Educational Game In CHI, pages 3339-3348, 2014.
[10] VirtaMed. Virtamed:
Simulators for Medical Training and Education. https://www.vittamed.
com/en/.
[11] Virtual Driver Interactive. https//wwww.direeieeaattte...co
[12] John H. Maloney, Kylie Peppler, Yasmin Kafai, Mitchel Resnick, and Natalie Rusk. Program- ming by choice: Urban youth learning programming with Scratch. In SIGCSE, pages 367-371, 2008.
[13] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. Reward Machines: Exploiting Reward Function Strueture in Reinforcement Learning. CoRR, abs/2010.03950, 2020.
[14] Yuqian Jiang, Suda Bharadwaj. Bo Wu, Rishi Shah, Ufuk Topcu, and Peter Stone. Temporal- Lasic Reward Shaping for Continuing Reinforcement Learning Tasks. In AAAI, 2021.
[15) Haoqi Zhang and David C. Parkes. Value-Based Policy Teaching with Active Indirect Elicitation. In AAAI, pages 208-214, 2008.
[16] Haoqi Zhang, David C. Parkes, and Yiling Chen. Policy Teaching through Reward Function Learning. In FC, pages 295-304, 2009.
[17] Yuzhe Ma. Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy Poisoning in Batch Reinforcement Learning and Control. In NeurlPS, pages 14543-14553, 2019.
[18] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning. In ICML, volume 119, pages 7974-7984, 2020.
[19] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks. Journal of Machine Learning Research, 22(210):1-44 155, 2021.
[20] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1st edition. 1994.
[21] Amy McGovern and Andrew G. Barto. Automatic Discovery Subgoals in Reinforcement Learning using Diverse Density. In ICML, pages 361-368, 2001.
[22] Özgür Simsek, Alicia P. Wolfe, and Andrew G. Barto. Identifying Useful Subgoals in Re- inforcement Learning by Local Graph Partitioning. ICML, volume 119, pages 816-823, 2005.
11

---

[23] Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic Goal Generation for Reinforcement Learning Agents. In ICML, volume 80, pages 1514-1523, 2018.
[24] Sujoy Paul, Jeroen van Baar, and Amit K. Roy-Chowdhury. Learning from Trajectories via Subgoal Discovery. In NewrlPS, pages 8409-8419, 2019.
[25] Andreas Krause and Daniel Golovin. Submodular Function Maximization. Tractability, 3:71-
104, 2014.
[26] Michael J. Kearns, Yishay Mansour, and Andrew Y. Ng. A Sparse Sampling Algorithm for Near- Optimal Planning in Large Markov Decision Processes. Machine Learning, 49(2-3):193-200) 2002.
[27] Hiroki Furuta, Tatsuya Matsushima, Tadashi Kozuno, Yutaka Matsuo, Sergey Levine, Ofir Nachum, and Shixiang Shane Gu. Policy Information Capacity: Information-Theoreee Measure for Task Complexity in Deep Reinforcement Learning. In ICML, pages 3541-3552, 2021.
[28] Adam Gleave, Michael Dennis, Shane Legg. Stuart Russell, and Jan Leike.
Quantifying
Differences in Reward Functions. In ICI.R, 2021.
[29] Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis. and Sahand Negahban. Restricted Strong Convexity Implics Weak Submodularity. Annals of Statistics, 4666B) 2018.
[30]
Abhimanyu Das and David Kempe. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In ICMI., pages 1057-1064, 2011.
[31] Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, Bin Yu, et al. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical science, 27(():538-55) -57, 2012.
[32] Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163 223, 2003.
[33] Lihong Li, Thomas J Walsh, and Michael I. Littman. Towards unified theory of state abstraction for mdps. ISAIM, 4:5, 2006.
[34] David Abel, David Hershkowitz, and Michael Littman. Near Optimal Behavior via Approximate State Abstraction. In ICML, pages 2915-2923, 2016.
[35] Bhaskara Marthi. Automatic shaping and decomposition of reward functions. In ICMI,, pages 601-608, 2007.
[36] Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Environment Shaping in Reinforcement Learning using State Abstraction. CoRR, abs/2006.131660 2020.
[37] Marek Grzes and Daniel Kudenko. Plan-based Reward Shaping for Reinforcement Learning. In International IEEE Conference on Intelligent Systems, volume 2, pages 10-22, 2008.
[38] John Asmuth, Michael I., Littman, and Robert Zinkov. Potential-based Shaping in Model-based Reinforcement Learning. In AAAI, pages 604-609, 2008
[39] Michael R. James and Satinder P. Singh. Sarsalandmark: An Algorithm for Learning in POMDPs with Landmarks. In AAMAS, pages 585-591, 2009.
[40] Alper Demir, Erkin Çilden, and Faruk Polat. Landmark Based Reward Shaping in Reinforcement Learning with Hidden States. In AAMAS, pages 1922-1924, 2019.
[41] Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling Others using Oneself in Multi-Agent Reinforcement Learning, In ICML, volume 80, pages 4254-4263, 2018.
[42] Anna Harutyunyan, Sam Devlin, Peter Vrancx. and Ann Nowé. Expressing Arbitrary Reward Functions as Bicential-Bssed Advice. In AAAI, pages 2652-2658, 2015.
[43] John Burden and Daniel Kudenko. Uniform state abstraction for reinforcement learning. arXiv preprint orXiv:2004.029/ 2020.
[44] Eric Wiewiora. Potential-Based Shaping and Q- Value Initialization are Equivalent. Journal of Artificial Intelligence Research, 19:205-208, 2003.
[45] Eric Wiewiora, Garrison W. Cottrell, and Charles Elkan. Principled Methods for Advising Reinforcement Learning Agents. In ICMI., pages 792-799, 2003.
[46] Sam Devlin and Daniel Kudenko. Dynamic Potential-baser Reward Shaping. AAMAS, pages 433-440, 2012.
12

---

[47] Marek Grzes, Reward Shaping in Episodic Reinforcement Learning. AAMAS, pages 565-573, 2017.
[48] Prasoon Goyal, Scott Niekum, and Raymond J. Mooney. Using natural language for reward shaping in reinforcement learning. In IJCAI, pages 2385-2391, 2019.
[49] Andrew G. Barto. Intrinsic Motivation and Reinforcement Learning. In Intrinsically Motivated Learning in Natural and Artificial Systems, pages 17-47. 2013.
[50] Tejas D. Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum, Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation. In NeurlPS, pages 3675-3683 2016.
[51] Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping Your Distance: Solving Sparse Reward Tasks Using Self-Balancing Shaped Rewards. In NeurIPS, pages 10376-10386, 2019.
[52] Johan Ferret, Raphaël Marinier, Matthieu Geist, and Olivier Pictquin. Self-Attentinal Credit Assignment for Transfer in Reinforcement Learning. In ICCA,, pages 2655-2661, 2020.
[53] Jonathan Sorg, Satinder P. Singh, and Richard I.. Lewis. Reward Design via Online Gradient Ascent. NeurIPS, pages 2190-2198, 2010.
[54] Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task- fano-Agnostic Exploration in Reinforcement Learning. In NeurlPS, 2020.
[55] Alberto Camacho, Oscar Chen, Scott Sanner, and Sheila A Mcllraith. Decision-Making with Non-Markovian Rewards: From LTL to Automata bassed Reward Shaping. In Proceedings of the Multi-disciplinary Conference on Reinforcement Learning and Decision Making (RIDM), pages 279-283, 2017.
[56) Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A Composable Specification Language for Reinforcement Learning Tasks. In NeurlPS, pages 13021-13030, 2019.
[57] Tim Brys, Anna Harutyunyan, Matthew E Taylor, and Ann Nowé, Policy Transfer using Reward Shaping. In AAMAS, pages 181-188, 2015.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] The paper is organized exactly according to the contributions listed at the end of the introduction section.
(b) Did you describe the limitations of your work? [Yes] We discussed the scalability related limitations of our EXPRD framework in Sections 3.3 and 6. We also outlined a future plan address these limitations.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] As stated in Section 6, this work primarily presents the theoretical underpinnings of reward design in reinforcement learning. As such in the present form there are no direct negative societal impacts of our work. However, given the importance of reward design in RL, one needs to be cautious in practical applications of these techniques in future. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We confirm that our paper conforms with the ethics review guidelines.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] For example, Assumption and Assumption 2 (see Appendix) gather the structural assumptions that the informativeness criterion needs to satisfy.
(b) Did you include complete proof's of all theoretical results? [Yes] Complete proofs of all theoretical results are included in the Appendix of the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code and instructions are included as a URL.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Training details are presented in the Appendix of the supplementary material and are also present in the code.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Error bars are included in all the result graphs, as be seen in Figures 3a and 5a.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The details are provided in the Appendix of the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zpzF5ovaXCv", "reviewer": "Reviewer_jgko", "summary": "This paper proposes an optimization-based framework for designing reward functions that balance sparsity/interpretability with informativeness. A novel optimization framework is proposed to directly learn these new reward signals given an initial reward signal and the corresponding optimal policy set. Three optimization problems are proposed that take into consideration subgoals, as well as learning subgoals on-the-fly given a budget on their number. An informativeness criterion is proposed based on Bellman residuals for optimization from which the new reward can be recovered. An iterative algorithm is proposed for approximately solving these problems, and state abstractions are also used to scale the method to larger state spaces. Theoretical analysis is provided to ensure feasibility of the optimization objective, and a near-optimal bound is provided for the iterative algorithm under reasonable assumptions on the informativeness criterion used. Finally experiments on simple domains are used to visualize the learned rewards in terms of their interpretability and informativeness.", "questions": "", "limitations": "", "rating": 6, "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": "originality: the work is original and novel, but some existing methodologies need further comparison, see limitations below\n\nquality: the work is technically sound, and all claims are supported by proofs\n\nclarity: the writing is very clear and precise, and well organized. however, I think it needs to be better motivated in the introduction, e.g. to state up-front what the use-cases of the method are, where it could be applied in practice, and where it could fail. This is somewhat indicated in the related work section, but I also feel could be elaborated on in the motivation. the assumptions of requiring the optimal policy set on the task seems to exclude a large number of use cases, which is important to discuss early on.\n\nsignificance: the work is quite significant as reward design, sparsity and interpretability are all important topics currently studied in RL. it is not fully clear that the method is \"better\" than other methods, since not many have been discussed (see limitations below). the experiments only seem to consider simple baselines which does not answer this matter. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "========  strengths  =========\n\n1. Intelligent reward design is an important problem in the reinforcement learning community. The connection between sparsity and explainability is quite interesting and novel, and to my knowledge has not been studied in a mathematically coherent framework in the past. The paper is also very clearly written and the mathematics is precise. \n\n2. The problem is cast as a problem in concave/convex optimization. This makes it possible to incorporate a variety of information into the objective function (e.g. subgoals or landmarks, other rewards, etc) and constrain the learned rewards appropriately. Theoretical results are provided that analyze the optimization objectives, proving feasibility. Furthermore, a greedy algorithm (Algorithm 1) is provided that iteratively solves these optimization problems near-optimally with a precise gap (Theorem 1). \n\n3. The method, while inherently computationally challenging to solve in large MDPs, can be cast using state abstraction to reduce the dimensionality, and apply the proposed methods to this transformed MDP. The experiments, while toy in nature, demonstrate how the method works in discrete and a continuous environment. The visualization and interpretation of the learned behaviors is very well illustrated for these domains. \n\n======== limitations ========\n\n1. It is not immediately clear that sparseness of the reward function is the deciding criterion for interpretability. On the contrary, I believe it is not difficult to derive reward functions that are both dense and interpretable. For instance, \"survivability\" of the agent can be best modeled by assigning a (constant) positive reward on each transition, as seen in the classical cart-pole domain. In many robotics/nagivation problems, we could design a reward function that awards the agent based on how close the agent is to a pre-determined goal state. Finally, in many OR-related real-world problems, the reward is often best described in terms of revenues, e.g. for inventory control how many items are sold in a period. While I agree with you that sparsity can be useful for some toy domains, is it reasonable to expect similar notions on the type of problems above?\n\n2. While the technical analysis of the method is very strong, a weaker point is the assumptions needed to realize the proposed methods. In lines 97-100, it is stated \"learning an optimal policy induced by the sparse reward R-bar is challenging due to high sample complexity\". The next lines mention that \"... given R-bar and the corresponding optimal policy set\". In some sense, it is difficult to see how these assumptions can be realized in practice on non-trivial domains, since learning this policy set is at least (if not more) challenging than learning even a single optimal policy with R-bar. \n\n3. In light of point 2, I have to wonder if the initial motivation and assumptions, and experimental design could be tailored to solve a slightly different problem to the one initially proposed in the introduction, making the motivation of the paper much stronger. Namely, suppose we have solved a source task and obtained both an R-bar (learned from the source reward data) and a set of optimal policies. This knowledge can then be used to initialize the algorithm on a target environment in which the dynamics are different, but the goals remain the same. Since reward invariance - a key property the ExpRD method is designed to satisfy -- is required in this setup, does it mean it can be applied directly to landmark/subgoal discovery and transfer? If not, what could be changed in the methodology to allow it to work under change of dynamics?\n\n======== other questions ========\n\n1. Conditions (C1) and (C2) essentially require that the true Q-values are known. How can this condition be satisfied when they are estimated, up to some error say epsilon? \n\n2. The current methodology seems quite reminiscent of the reward shaping literature in which arbitrary reward functions (in this case R-bar) can be converted to potential functions for PBRS (see, e.g. [1]). It seems as though subgoals can be encoded in a reward with \"bugs\", but then that method can be used to guarantee invariance, by learning a secondary value function on this subgoal-driven advice. This method has the advantage of being scalable to large or continuous spaces, and requiring little knowledge besides learning the secondary values on data. Given how similar the problem setting tackled by these two methods, can you compare them conceptually, if not experimentally? Does that method have limitations with regard to sparsity, or can sparsity be enforced in learning values by using state abstractions, sparse codings, etc?\n\n3. Theorem 1 provides a gap between the optimal objective value and the greedy one. Is it possible to understand how \"good\" this gap is? Is it the best bound possible under the given assumptions? \n\n[1] Harutyunyan, Anna, et al. \"Expressing arbitrary reward functions as potential-based advice.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 29. No. 1. 2015.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "9yVcvG0YyAL", "reviewer": "Reviewer_AMnw", "summary": "The paper introduces ExpRD, a novel optimization framework to design explicable reward functions that attempts to balance informativeness and sparsity of the reward. The proposed reward design framework is theoretically underpinned into the existing framework of PBRS and tested in two distinct environments with some success.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "- The paper is well-written and easy to follow.\n- The related work section is extensive and provides a good overview of related literature on methods that address reward function design. \n\n- I am not fully convinced that sparseness is a desirable characteristic for a reward function. I understand the reward functions are often sparse in real world environments and it is necessary to design learning algorithms that can work for them. However, the authors note sparsity as a “preferred characteristic” alongside informativeness [Line 100]. Settings highlighted to support this such as pedagogical and robotic applications [Line 35-38] might have to work with sparse rewards. However, I view this sparsity as a limitation to overcome rather than a characteristic to be desired. More discussion to support why we want sparsity would clarify the thesis of the paper.\n\n- Results in 2a suggest that PBRS still outperforms all variants of the proposed method notwithstanding that the proposed method has more parameters that needs to be optimized. Results in 4a suggest something similar - the proposed method (one variant) outperforms PBRS only slightly. It isn’t clear whether this justifies the optimization necessary to acquire the parameters that achieves this for the proposed method while PBRS seems to work out of the box.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The benefits of the proposed method hinges on sparsity being a preferred characteristic. I am not fully convinced of this. If the authors could clarify the case towards this, it would alleviate my primary reservation.\n\n- Author indicates that the proposed method can be seen as a relaxation of PBRS towards (1) guaranteeing a weaker invariance property and (2) maximizing informativeness under (1) and given sparsity constraints. It is not clear to me what the redeemable benefit to this relaxation is as the empirical results do not seem to clearly indicate a marginal benefit. \n\n- The work does not have any discernable negative societal impacts that is obvious to me. \n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "2Pl7lgnSDyR", "reviewer": "Reviewer_c46D", "summary": "This paper tackles an important question in reward design for reinforcement learning - the trade-off between sparseness and learnability. It describes a framework to build modified rewards that are denser than the original but produce a set of optimal policies that are guaranteed to be a subset of the optimal policies induced by the original reward. The framework, ExpRD, is benchmarked on two relatively simple environments against several baselines. Experiments show improved convergence compared to the original sparse reward while being relatively sparser compared to PBRS. ", "questions": "", "limitations": "", "rating": 7, "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": "This paper tackles an important question - how can one improve the informativeness of reward functions while not degrading their interpretability. To this question, the paper implies a strong correlation between sparseness and interpretability. Thus, the paper is fundamentally about the balance between informativeness and sparseness of reward functions. The authors take inspiration from PBRS - an important work that explored the design of dense rewards from an original sparse reward while avoiding locally optimal policies that are globally suboptimal (reward bugs). The ExpRD formulation achieves sparser rewards compared to PBRS. \n\nStrengths:\n1. The paper is grounded in theory - the authors provide detailed proofs of propositions in the appendix. \n2. The paper provides a simple concave optimization method to derive sparse-but-informative rewards.\n3. Provides a simple sparsity budget parameter B that can control the trade-off between sparseness and informativeness\n\nWeaknesses:\n1. The authors make \"explicability\" a central premise and imply an equivalence between explainability and sparsity. Beyond a few examples of rewards that are explainable and sparse, they do not explain why this equivalence should hold generally. Thus, this paper is fundamentally about the trade-off between how sparse and how learnable a reward function is. \n\n2.  The paper does a mixed job of providing intuition behind the defined quantities or features. For example, the informativeness metric and its properties could have been better intuited.\n\n3. Experiments conducted are relatively simple settings. While both environments capture the basic notion of a sparseness-informativeness trade-off, it is not clear that the performance improvements over the original sparse reward would hold for much larger state-spaces while still maintaining a comparable level of sparseness. The fundamental difference between PBRS and this method is the control over sparsity - and it is not clear to me that convergence would improve at all for small values of B when |S| is large.\n\nOverall this is a good paper when viewed as a fundamental theoretical study of reward functions - but could be much stronger if the experimental treatment were to be more extensive. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors point out that this paper is primarily a theoretical treatise on reward functions and that there are no direct negative social implications beyond risks inherent in any reward design. I would agree with the authors on this point.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1jqdBaVDmT", "reviewer": "Reviewer_5fTq", "summary": "This paper the problem modifying a very sparse reward, e.g., an\nindicator for task completion, in a manner that remains sparse but\nincreases the \"informativeness\". The resulting reward should ideally\nresult in faster convergence of RL style learning algorithms.  The\npaper formulates this reward design problem as a form of discrete\noptimization and provide a greedy approximation scheme, which is\nproved to not deviate too much from the optimum.  Furthermore, a\ntheoretical analysis shows the relates this new measure to existing\nreward design algorithms, and in particular potential based shaping.\nFinally, the paper illustrates the approach on two domains, leveraging\nstate space abstraction to support continuous dynamics. There they show\nthat the they are indeed able to learn sparse rewards in a manner that\noptionally incorporates and improves convergence time.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "I found the topic and techniques employed in this paper very\ninteresting. While I must admit it is outside my domain of\nexpertise, with the exception of the submodularity discussion,\nI was able to follow the exposition. Again, since this is\nnot my primary area, I hesitate to comment on the novelty,\nI believe the contribution to be original, with the paper\nhaving a well made related work section.\n\nThis empirical evaluation highlights how useful the sparsity is\nfor interpretability, and I found it much easier to parse the\nsynthesized reward compared to the potential based approach.\nTogether with a strong theoretical basis, I find this to be\ngood motivation for accepting this work and allowing for a\nmore general discussion.\n\n# Minor Points\n\nA minor point of feedback and a point of early confusion on my part\nwas the mixing of stochastic and deterministic policies, sometimes\nusing the same notation, i.e., on line 97 is delta* for stochastic\npolicies?  And on line 92, is the set of policies deterministic?\n\nAnother point I found hard to initially follow was the motivation\nfor the particular form of the informative criterion. In particular,\nhow does the choice of the function l empirically and theoretically\naffect convergence.\n\nFinally, I think to me the most interesting feature this algorithm does not have is the ability to introduce new memory (state) which may make the reward even easier to interpret and potentially more robust to domain transfer - relying less on features of the dynamics.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the problem of reward design is incredibly important for safe RL, both from an engineering perspective (less numerical errors and places to introduce the reward) and a human auditability perspective.\n\nThe primary limitation of this work, as I understand, seems to be that the reward designer must have a complete understanding of the dynamics. While reasonable for some applications, in many others, it somewhat defeats the purpose RL. Nevertheless, I think this is a very important subject to study.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the problem of reward design is important and particularly relevant for safe reinforcement learning (RL). It is also a timely subject now that the deployment of RL systems in the real world is becoming increasingly more common. There was also a consensus among the reviewers that the proposed approach is technically sound. 

Based on the submission, the reviews, the rebuttal and the subsequent discussions, we strongly advise the authors to make two modifications to the paper. 

First, the placement of the proposed approach should be much more clear and stated at the outset. Some passages of the text suggest that the motivation underlying the proposed method is to find a reward to replace the original, sparse, reward in order to solve a specific task. 

The connections made with Ng et al.'s PBRS and variants are one example. One of the requirements of the proposed approach is that one has access to (an approximation of) the optimal value function $\bar{V}^*$. One of the reviewers called attention to this fact and asked how realistic this is in practice, to which the authors responded that "similar to PBRS with $\bar{V}^*$ as the potential function, our framework does require solving the task w.r.t. the original reward function $\bar{R}$".

Although it is true that $\bar{V}^*$  can be used to derive PBRS' potential function, and Ng et al. point out that this choice gives rise to a particularly easy problem, their result apply to *any* potential function derived from a function $\Phi$ define over states (see Theorem 1 in Ng et al. 1999). In fact, Ng et al. emphasize that their method does *not* depend on $\bar{V}^*$, and also illustrate this point in their experiments by handcrafting a $\Phi$ that is intuitive but considerably different from $\bar{V}^*$. 

PBRS and variants aim at finding a reward $\hat{R}$ to replace the original, potentially sparse, reward $\bar{R}$ in order to solve a specific task. If we view the proposed approach as an alternative to these methods, the fact that it needs $\bar{V}^*$ is a strong limitation. 

An alternative view is that we *can* solve the task $\bar{R}$ but want a different version of it, $\hat{R}$, to be used in the future when we solve the task again. This new version of the reward, $\hat{R}$, should have two desirable properties: it should be informative and interpretable. Under this view, the fact that we need $\bar{V}^*$ seems to be less of an issue. Although this interpretation of the proposed approach seems to be favored in parts of the paper, it should be more clearly stated, and any passages that suggest otherwise should be modified to avoid ambiguities. 

A second modification to the paper we strongly suggest regards the use of sparsity as a proxy for interpretability. This concern came up in most of the reviews and was a point of contention in the discussions. We advise the authors to add the good points made during the discussion to the paper. Specifically, they should clarify why sparsity is a good measure of interpretability and explain how the proposed approach can be modified to accommodate other reward structures. They should also add the provided list with examples of applications where sparsity structure in the reward design is important. 

We hope the provided feedback will be helpful in making your paper even stronger.

Decision: Accept (Poster)