Explicable Reward Design for Reinforcement Learning Agents
Year: 2022

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.

heading: 1 Introduction
text: A reward function plays the central role during the learning/training process of a 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 final output 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, a major challenge faced by an RL agent is 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-based reward shaping (when applied with appropriate state potentials) indeed allows us 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 is an important criterion, it is not the only criterion to consider when designing rewards for many practical applications. Another natural criterion to consider is sparseness as a proxy for ease of interpretability of the rewards. There are several practical settings where sparseness and interpretability of rewards are important, as 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 applications such as educational games [9], virtual reality-based training simulators [10, 11], and solving open-ended problems (e.g., block-based visual programming [12]). In this context, tasks can be challenging for novice learners and a teacher agent can assist these learners by designing explicable rewards associated with these tasks. The second motivating 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, 14]—these specifications induce a form of sparsity structure on the underlying reward function. The third motivating application is related to defense against reward-poisoning attacks in RL (see [15–19]) by designing structured and sparse reward functions that are easy to debug/verify. 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 properties 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-mentioned potential-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 we 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 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 a new reward function for the agent— see Figure 1 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 a 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-)optimality of target policies at different time horizons from any given starting state. Our main contributions are:1
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 a 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 potential-based reward shaping. (Sections 3.3 and 3.4)
IV. We provide a 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)

heading: 2 Problem Setup
text: Environment. An environment is defined as a Markov Decision Process (MDP) M := (S,A, T, γ,R), where the set of states and actions are denoted by S and A respectively. T : S ×S ×A → [0, 1] captures the state transition dynamics, i.e., T (s′ | s, a) denotes the probability of landing in state s′ by taking action a from state s. Here, γ is the discounting factor. The underlying reward function is given by R : S ×A → [−Rmax, Rmax], for some Rmax > 0. We interchangeably represent the reward function by a vector R ∈ R|S|·|A|, whose (s |A|+ a)-th entry is given by R (s, a). We define the support of R as supp(R) := {s : s ∈ S, R (s, a) 6= 0 for some a ∈ A}, and the `0-norm of R as ‖R‖0 := |supp(R)|. Preliminaries and definitions. We denote a stochastic policy π : S → ∆ (A) as a mapping from a state to a probability distribution over actions, and a deterministic policy π : S → A as a mapping from a state to an action. For any policy π, the state value function V π∞ and the action value function Qπ∞ in the MDPM are defined as follows respectively: V π ∞ (s) = E [ ∑∞ t=0 γ
tR(st, at)|s0 = s, T, π] and Qπ∞ (s, a) = E [ ∑∞ t=0 γ
trt|s0 = s, a0 = a, T, π]. Further, the optimal value functions are given by V ∗∞ (s) = supπ V π ∞ (s) and Q ∗ ∞ (s, a) = supπ Q π ∞ (s, a). There always exists a
1Github repo: https://github.com/adishs/neurips2021_explicable-reward-design_code.
deterministic stationary policy π that achieves the optimal value function simultaneously for all s ∈ S [7, 20], and we denote all such deterministic optimal policies by the set Π∗ := {π : S → A s.t. V π∞ (s) = V ∗∞ (s) ,∀s ∈ S}. From here onwards, we focus on deterministic policies unless stated otherwise. For any π and R, we define the following quantities that capture the∞-step (global) optimality gap and the 0-step (myopic) optimality gap of action a at state s, respectively:
δπ∞(s, a) := Q π ∞(s, π(s))−Qπ∞(s, a), and δπ0 (s, a) := Qπ0 (s, π(s))−Qπ0 (s, a), ∀s ∈ S, a ∈ A,
where Qπ0 (s, a) = R (s, a) is the 0-step action value function of policy π. The δ π ∞(s, a) values are same for all π ∈ Π∗, and we denote it by δ∗∞(s, a) = V ∗∞(s) −Q∗∞(s, a); however, this is not the case with δπ0 (s, a) values in general. For any state s ∈ S and a set of policies Π, we define Πs := {a : a = π(s), π ∈ Π}. Then, we have that δ∗∞(s, a) = 0,∀s ∈ S, a ∈ Π∗s . Explicable reward design. Figure 1 presents an illustration of the explicable reward design problem that we formalize below. A task is specified as an MDP M with a given goal-based reward function R where R has non-zero rewards only on goal states G ⊆ S , i.e., R (s, a) = 0,∀s ∈ S\G, a ∈ A. Many naturally occurring tasks (see Section 1 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 point of view: Given R and the corresponding optimal policy set Π ∗ w.r.t. R as the input, the teacher designs a 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 Π ∗ induced by R.2
Typical techniques for reward design and issues. Given a set of important states (subgoals) in the environment, one could design a handcrafted reward function R̂CRAFT 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. In particular, there are some well-known “reward bugs” that can arise in this approach and mislead the agent into learning sub-optimal policies (see [2, 3]). In the seminal work [3], the authors introduced the potential-based reward shaping (PBRS) method to alleviate this issue. The reward function produced by the PBRS method with optimal value function V ∗ ∞ under R as the potential function is defined as follows:
R̂PBRS (s, a) := R (s, a) + γ ∑ s′∈S T (s′ | s, a) · V ∗∞ (s′)− V ∗ ∞ (s) . (1)
The set of optimal policies Π̂∗ induced by R̂PBRS is exactly equal to the set of optimal policies Π ∗ induced by R since δ̂π∞(s, a) = δ ∗ ∞(s, a) for all π ∈ Π ∗ [3]. In addition, for any state s ∈ S , globally optimal actions Π ∗ s ⊆ A underR are also myopically optimal under R̂PBRS since δ̂π0 (s, a) = δ ∗ ∞(s, a) for all π ∈ Π∗ [3, 8] – this leads to a dramatic speed-up in the learning process. However, the potentialbased reward shaping produces dense reward function which is less interpretable (see Section 4).
2In the rest of the paper, the quantities defined corresponding to R := R are denoted by an overline, e.g., the optimal policy set by Π ∗ and the∞-step optimality gaps by δ∗∞; the quantities defined corresponding to R := R̂ are denoted by a widehat, e.g., the optimal policy set by Π̂∗.

heading: 3 Our Reward Design Framework EXPRD
text: In Sections 3.1, 3.2, 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.

heading: 3.1 Discrete Optimization Formulation
text: Given R and the corresponding optimal policy set Π ∗ , we systematically develop a discrete optimiza-
tion framework (EXPRD) to design an explicable reward function R̂ (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 an informativeness criterion I(R̂) of R̂ that captures how hard/easy it is to learn an optimal behavior induced by R̂. We explicitly enforce the invariance requirement (see Section 2) for the new reward R̂ by choosing a set of candidate policies Π† ⊆ Π∗, and satisfying the following (Bellman-optimality) conditions:
Qπ † ∞ (s, a) = R̂(s, a) + γ ∑ s′∈S T (s′|s, a) ·Qπ † ∞ (s ′, π†(s′)), ∀a ∈ A, s ∈ S, π† ∈ Π† (C.1)
Qπ † ∞ (s, π †(s)) ≥ Qπ † ∞ (s, a) + δ ∗ ∞(s), ∀a ∈ A\Π ∗ s, s ∈ S, π† ∈ Π†, (C.2)
where δ ∗ ∞(s) := mina∈A\Π∗s δ ∗ ∞(s, a),∀s ∈ S.3 The above conditions guarantee that any optimal policy induced by R̂ is also optimal under R, i.e., Π† ⊆ Π̂∗ ⊆ Π∗. Here, the set Π† ⊆ Π∗ is used to reduce the number of constraints. Note that for the potential-based shaped reward R̂PBRS, we have Π̂∗ = Π ∗ .
Maximizing informativeness for a given set of important states. When a domain expert provides us a set of important states (subgoals) in the environment [21–24], we want to use this set in a principled way to design a reward R̂, while avoiding the “reward bugs” that can arise from handcrafted rewards R̂CRAFT. To this end, for any given set of subgoals Z ⊆ S\G, we optimize the informativeness criterion I(R) while satisfying the invariance requirement:
g(Z) := max R:supp(R)⊆Z∪G I(R)
subject to conditions (C.1)− (C.2) with R̂ replaced by R hold (P1) |R (s, a)| ≤ Rmax, ∀s ∈ S, a ∈ A.
Let R(Z) denote the R that maximizes g(Z). LetR ⊆ R|S|·|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 (P1), we propose the following discrete optimization formulation that allows us to select a set of important states (of size B) and design a reward function that maximizes informativeness automatically:
max Z:Z⊆S\G,|Z|≤B
g(Z). (P2)
We can incorporate prior knowledge about the quality of subgoals using a set function D : 2S → R (we assume D to be a submodular function [25]). Finally, the full EXPRD formulation is given by:
max Z:Z⊆S\G,|Z|≤B
g(Z) + λ ·D(Z ∪ G), for some λ ≥ 0. (P3)
We study the problems (P1), (P2), and (P3) in the following subsections.
3Note that the true action values Q ∗ ∞ are used in the conditions (C.1)− (C.2) to obtain the terms δ ∗ ∞(s, a), A\Π∗s , and Π†. However, when we only have an approximate estimate of Q ∗ ∞, we can adapt (C.1) − (C.2) appropriately with approximate versions of δ ∗ ∞(s, a), A\Π ∗ s , and Π†.

heading: 3.2 Informativeness Criterion
text: Understanding the informativeness of a 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 π ∈ Π∗, 0-step and ∞-step optimality gaps induced by R̂PBRS are all equal to ∞-step optimality gaps induced by R, i.e., δ̂π0 (s, a) = δ̂ π ∞(s, a) = δ ∗ ∞(s, a). For any reward function R, one could ask how much these two quantities could differ, and even consider the intermediate cases between 0-step and∞-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 Qπh (s, a) = E [∑h t=0 γ tR(st, at)|s0 = s, a0 = a, T, π ] , and it satisfies
the following recursive relationship: Qπh(s, a) = R(s, a) + γ ∑ s′∈S T (s
′|s, a) ·Qπh−1(s′, π(s′)). Let H be a set of horizons for which we want to maximize informativeness. For any policy π and reward functionR, we define the following quantity that captures the h-step optimality gap of action a at state s: δπh(s, a) := Q π h(s, π(s))−Qπh(s, a),∀s ∈ S, a ∈ A, h ∈ H. Later, in the proof of Proposition 2, we show that δπh(s, a) is linear in R, i.e., δ π h(s, a) = 〈 wh;(s,a), R 〉 for some vector wh;(s,a) ∈ R|S|·|A|. Interestingly, the following proposition states that, for any policy π ∈ Π∗ and any h, the hstep optimality gap induced by R̂PBRS given in (1) is equal to the∞-step optimality gap induced byR: Proposition 1. The goal-based reward function R, and the potential-based shaped reward function R̂PBRS given in (1) satisfy the following: δ̂πh(s, a) = δ ∗ ∞(s, a),∀s ∈ S, a ∈ A, π ∈ Π ∗ , h ∈ H.
Let ` : R → R be a monotonically non-decreasing concave function. Then, based on the h-step optimality gaps, we define the informativeness criterion of the reward R as follows:
I`(R) := ∑ π†∈Π† ∑ h∈H ∑ s∈S ∑ a∈A\Π∗s `(δπ † h (s, a)).
From here onwards, we let I be I` in the problem (P1). As an example for `, we consider the negated hinge loss given by `hg(δ(s, a)) := −max(0, δ ∗ ∞(s, a)− δ(s, a)). By Proposition 1, we have that I`hg(R̂PBRS) = 0, and I`hg(R) ≤ 0 for any other R, i.e., R̂PBRS achieves the maximum value of I`hg .

heading: 3.3 Iterative Greedy Algorithm
text: First, we show that the problem (P1) can be efficiently solved using the standard concave optimization methods to find R(Z) for any given Z ⊆ S\G: Proposition 2. For any given Z ⊆ S\G, the problem (P1) is a concave optimization problem in R ∈ R|S|·|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 (P1) for different values of Z . The problem (P1) has |S| · |A| optimization variables and O(|S| · |A| ·
∣∣Π†∣∣ · |H|) constraints. Algorithm 1 Iterative Greedy Algorithm for EXPRD
1: Input: MDP M := ( S,A, T, γ,R ) , δ ∗ ∞(s, a) values, sets Π ∗ ,Π † ,G,H, sparsity budget B 2: Initialize: Z0 ← ∅ 3: for k = 1, 2, . . . , B do 4: zk ← arg maxz∈S\Zk−1 g(Zk−1∪{z})+λ·D(Zk−1∪G∪{z})−g(Zk−1)−λ·D(Zk−1∪G) 5: Zk ← Zk−1 ∪ {zk} 6: Output: ZB and the corresponding optimal reward function R(ZB).

heading: 3.4 Theoretical Analysis
text: Here, we provide guarantees for the solution returned by our Algorithm 1. Below, we give an overview of the main technical ideas, and leave a detailed discussion along with proofs in the
Appendix. For some µ ≥ 0, let I reg` (R) := I`(R) − µ ‖R‖ 2 2 be the regularized informativeness criterion. We define a normalized set function f : 2S → R as follows: f(Z) = max
R:supp(R)⊆Z∪G,R∈R (I reg` (R)− I reg ` (R (∅))) + λ · (D(Z ∪ G)−D(G)), (2)
where R(∅) = arg maxR:supp(R)⊆G,R∈R I reg ` (R). Note that the regularized variant (I` replaced by I reg` ) of the optimization problem (P3) is equivalent to maxZ:Z⊆S\G,|Z|≤B f (Z). For a given sparsity budget B, let ZGreedyB be the set selected by our Algorithm 1 and ZOPTB be the optimal set that maximizes the regularized variant of problem (P3). The corresponding f values of these sets are denoted by fGreedyB and f OPT B 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 setR (see the discussion after (P1)), 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 reg` 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 1 (Restricted Strong Concavity, Restricted Smoothness [31]). A functionL : R|S|·|A| → R is said to be restricted strong concave with parameter mΩ and restricted smooth with parameter MΩ on a domain Ω ⊂ R|S|·|A| × R|S|·|A| if for all (x, y) ∈ Ω:
−mΩ 2 ‖y − x‖22 ≥ L (y)− L (x)− 〈∇L (x), y − x〉 ≥ − MΩ 2 ‖y − x‖22 .
For any integer k, we define the following two sets: Ωk := {(x, y) : ‖x‖0 ≤ k, ‖y‖0 ≤ k, ‖x− y‖0 ≤ k, x, y ∈ R}, and Ω̃k := {(x, y) : ‖x‖0 ≤ k, ‖y‖0 ≤ k, ‖x− y‖0 ≤ 1, x, y ∈ R}. Let mk := mΩk and Mk := MΩk (similarly we define m̃k and M̃k).
When there is no R ∈ R constraint in (2), the following assumption on the regularized informativeness criterion is sufficient to prove the weak submodularity of f [29]: Assumption 1. The regularized informativeness criterion I reg` ism2B+|G|-restricted strongly concave and M2B+|G|-restricted smooth on Ω2B+|G|.
However, due to the additional R ∈ R constraint, we need to enforce further requirements on I reg` formally captured in Assumption 2 provided in the Appendix; here, we discuss these requirements informally. Let Z be any set such that Z ⊆ S\G, and∇I reg` (R(Z)) be the gradient of the regularized informativeness criterion at the optimal reward R(Z). Then, we need to ensure the following: (i) the `2-norm of the projection of ∇I reg` (R(Z)) on (Z ∪ G) is upper-bounded, captured by doptmax; (ii) the `2-norm of the projection of∇I reg` (R(Z)) on any j ∈ S\(Z∪G) is lower-bounded, captured by dnonmin; and (iii) the components of the optimal reward R(Z) outside (Z ∪ G) do not lie in the boundary ofR, captured by κ. Then, by using Assumption 1 and Assumption 2 (see Appendix), we prove the weak submodularity of f . Finally, by applying Theorem 3 from [29], we obtain the following theorem: Theorem 1. Let I reg` satisfies Assumption 1 and Assumption 2 requirements. Then, we have f Greedy B ≥ (1− e−γ) fOPTB , where γ = κ·m2B+|G| M2B+|G| · (d non min) 2
(doptmax) 2 +(dnonmin)
2 .
We provide Assumption 2 and a detailed proof of the theorem in the Appendix.

heading: 3.5 Extension to Large State Spaces using State Abstractions
text: 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 → Xφ, which is a mapping from high-dimensional state space S to a low-dimensional latent space Xφ. Let φ−1(x) := {s ∈ S : φ(s) = x} ,∀x ∈ Xφ, and M := ( S,A, T, γ,R ) . We propose the following pipeline:
1. By using M and φ, we construct an abstract MDP Mφ = ( Xφ,A, Tφ, γ, Rφ ) as follows,
∀x, x′ ∈ Xφ, a ∈ A: Tφ(x′|x, a) = 1|φ−1(x)| ∑ s∈φ−1(x) ∑ s′∈φ−1(x′) T (s
′|s, a), and Rφ(x, a) = 1 |φ−1(x)| ∑ s∈φ−1(x)R(s, a). We compute the set of optimal policies Π ∗ φ for the MDP Mφ.
2. We run our EXPRD framework on Mφ with Π† = Π ∗ φ, and the resulting reward is denoted R̂φ.
3. We define the reward function R̂ on the state space S as follows: R̂(s, a) = R̂φ(φ(s), a).
By assuming certain structural conditions on φ formalized in the Appendix, we can show that any optimal 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.

heading: 4 Experimental Evaluation
text: In this section, we evaluate EXPRD on two environments: ROOMSNAVENV (Section 4.1) and LINEKEYNAVENV (Section 4.2). ROOMSNAVENV corresponds to a navigation task in a grid-world where the agent has to learn a policy to quickly reach the goal location in one of four rooms, starting from an initial location. Even though this environment has a small state space, it provides a very rich and an intuitive problem setting to validate different reward design techniques, and variants of ROOMSNAVENV have been used extensively in the literature [14, 21, 22, 37–40]. LINEKEYNAVENV corresponds to a navigation task in a one-dimensional space where the agent has to first pick the key and then reach the goal. The agent’s location in this environment is 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-based extension of our framework from Section 3.5. This environment is inspired by variants of navigation tasks in the literature where an agent needs to perform sub-tasks [3, 41]. We give an overview of main results here, and provide a 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 S states each corresponding to cells in the gridworld indicating the agent’s current location (shown as “bluecircle”). Goal (shown as “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; however, if there is a wall (shown as “brown-segment”), the agent stays at the current location. Furthermore, when an agent takes an action a ∈ A, there is prand probability that an action a′ ∈ A \ {a} will be executed instead of a. In addition to these walls, there are a few terminal walls (shown as “thick-red-segment”) that terminates the
episode—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 0 for all other state-action pairs and there is a discount factor γ. This MDP has |S| = 49 and |A| = 4; we set prand = 0.1, Rmax = 10, and γ = 0.95 in our evaluation.
Techniques evaluated. We consider the following baselines: (i) R̂ORIG := R, which simply represents default reward function, (ii) R̂PBRS obtained via the PBRS technique with the optimal value function V ∗ ∞ w.r.t. R (see Section 2), (iii) R̂CRAFT that we design manually (see Section 2 and description below), and (iv) R̂PBRS-CRAFT(B=5) obtained via the PBRS technique with the optimal value function w.r.t. R̂CRAFT instead of V ∗ ∞ [42].
4 To design R̂CRAFT, 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 a reward of +1 for optimal actions and −1 for others. For the evaluation, we use B = 5 and denote the function as R̂CRAFT(B=5). Note that apart from B states, R̂CRAFT(B=5) also has a reward assigned for the goal state taken from R.
4The 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.
The reward functions R̂EXPRD designed by our EXPRD framework are parameterized by budgetB and hyperparameter λ. For λ, we consider two extreme settings: (a) λ = 0 where the problem (P3) reduces to (P2), and (b) λ→∞ 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 R̂CRAFT above. For budget B, we consider values from {3, 5, |S|}. In particular, we evaluate the following reward functions: R̂EXPRD(B=5,λ→∞), R̂EXPRD(B=3,λ=0), R̂EXPRD(B=5,λ=0), and R̂EXPRD(B=|S|,λ=0). For the evaluation in this section, we use the following parameter choices for EXPRD: H = {1, 4, 8, 16, 32}, ` is the negated hinge loss `hg, and Π† contains only one policy from Π ∗ .
Results. We use standard Q-learning method for the agent with a 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 error bars. The convergence behavior in Figure 3a demonstrates the effectiveness of the reward functions designed by our EXPRD framework.5 Note that R̂CRAFT(B=5) leads to sub-optimal behavior due to “reward bugs” (see Section 2), whereas R̂EXPRD(B=5,λ→∞) 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 to R̂EXPRD(B=3,λ=0) is comparable to that of R̂EXPRD(B=5,λ→∞). The visualizations of R̂ORIG, R̂PBRS, and R̂EXPRD(B=5,λ=0) in Figures 3b, 3c, and 3d highlight the trade-offs in terms of sparseness and interpretability of the reward functions. The reward function R̂EXPRD(B=5,λ=0) designed by our EXPRD framework provides a good balance in terms of convergence performance while maintaining high sparseness. Additional visualizations and results are provided in the Appendix.
4.2 Evaluation on LINEKEYNAVENV
A := {“left”, “right”, , “pick”}. “pick” action does not change the agent’s location, however, when
5As we discussed in Sections 1 and 2, R̂PBRS designed using V ∗ ∞ makes the agent’s learning process trivial.
executed 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 in the direction of move with the dynamics of the final location captured by two hyperparameters (∆a,1,∆a,2); for instance, with current location x and action “left”, the new location x′ is sampled uniformly among locations from (x −∆a,1 −∆a,2) to (x −∆a,1 + ∆a,2). Similar to ROOMSNAVENV, the agent’s move action is not applied if the new location crosses the wall, and there is prand probability of a random action. The agent gets a reward of Rmax after it has navigated to the goal locations after acquiring the key and then takes a “right” action; note that this action also terminates the episode. The reward is 0 elsewhere and there is a discount factor γ. We set prand = 0.1, Rmax = 10, γ = 0.95, ∆a,1 = 0.075 and ∆a,2 = 0.01.
Techniques evaluated. The baseline R̂ORIG := R represents the default reward function. We evaluate the variants of R̂PBRS and R̂EXPRD using an abstraction. For a given hyperparameter α ∈ (0, 1), the set of possible locations X are obtained by α-level discretization of the line segment from 0.0 to 1.0, leading to a 1/α set of locations. For the abstraction φ associated with this discretization [43], the abstract MDP Mφ (see Section 3.5) has |Xφ| = 2/α and |A| = 3. We use α = 0.05. We compute the optimal state value function in the abstract MDP Mφ, lift it to the original state space via φ, and use the lifted value function as the potential to design R̂PBRS [35]. We follow the pipeline in Section 3.5 to design R̂EXPRD – in the subroutine, we run EXPRD on Mφ for a budget B = 5 and a full budget B = |Xφ|; we set λ = 0. For other parameters (H, `, and Π†), we use the same choices as in Section 4.1.
Results. The agent uses Q-learning method in the original MDP M by using a fine-grained discretization 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 functions—R̂PBRS, R̂EXPRD(B=5,λ=0), R̂EXPRD(B=|Xφ|,λ=0)—substantially improves the convergence, whereas the agent is not able to learn under R̂ORIG. Based on the visualizations in Figures 5b, 5c, and 5d, R̂EXPRD(B=5,λ=0) provides a good balance between convergence and sparseness. Interestingly, R̂EXPRD(B=5,λ=0) assigned a high positive reward for the “pick” action when the agent is in the locations with key (see ‘p-’ bar in Figure 5d).

heading: 5 Related Work
text: Potential-based reward shaping. Introduced in the seminal work of [3], potential-based reward shaping is 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 R̂PBRS is obtained by modifying R using a state-dependent potential function. The technique preserves a strong invariance property: a
policy π is optimal under R̂PBRS iff it is optimal under R. Furthermore, when using the optimal valuefunction V ∗ ∞ 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 a 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 R̂EXPRD is also optimal under R; (ii) EXPRD finds R̂EXPRD 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 as an optimization problem [15–19]. In particular, optimization-based 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 we optimize for informativeness of the reward function under a sparseness constraint, which makes our problem formulation much more challenging.
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 a reinforcement learning method where an 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 use a wide-variety of ideas such as designing 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].
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-based reward shaping and optimization-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 an expert-driven technique with minimal domain knowledge (e.g., when using approximate potentials [3]).
Reward automatas, landmark-based rewards, and subgoal discovery. Our EXPRD framework is also connected to techniques that specify 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-based 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 on automatic discovery of subgoals in the environment [21–24] – these works are complementary and useful as subroutines in our framework by providing a prior knowledge about which states are important for assigning rewards.

heading: 6 Conclusions
text: 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 expertdriven explicable reward design. Importantly, EXPRD allows one to go beyond using a potential function for principled reward design, and provides a general recipe for developing an optimizationbased reward design framework with different structural constraints. We also provided a 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 a combination of our optimization-based reward design technique with automata-driven rewards as 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.

Review summaries:
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.

This paper the problem modifying a very sparse reward, e.g., an indicator for task completion, in a manner that remains sparse but increases the "informativeness". The resulting reward should ideally result in faster convergence of RL style learning algorithms.  The paper formulates this reward design problem as a form of discrete optimization and provide a greedy approximation scheme, which is proved to not deviate too much from the optimum.  Furthermore, a theoretical analysis shows the relates this new measure to existing reward design algorithms, and in particular potential based shaping. Finally, the paper illustrates the approach on two domains, leveraging state space abstraction to support continuous dynamics. There they show that the they are indeed able to learn sparse rewards in a manner that optionally incorporates and improves convergence time.  

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.