One-shot Policy Elicitation via Semantic
Reward Manipulation

We formulate our domain as a Markov Decision Process (MDP)bellman1957markovian , wherein an agent acts to maximize an expected reward. $M$ is a Markov Decision Process defined by the 4-tuple $(S,A,T,R)$ where $S$ is the set of states in the MDP, $A$ is the set available actions, $T$ is a stochastic transition function describing the model’s action-based state transition dynamics, and $R$ is the reward function $R:S\times A\times S\rightarrow\mathbb{R}$. Intuitively, $M$ serves as a simulator for an agent in the task domain.

Belief estimation (inferring an agent’s plan) is performed by leveraging the assumption that the agent has a rational planner and any sub-optimal behavior can be attributed to a misinformed understanding of the task’s reward function $R_{h}$, where $R_{h}$ is the malformed reward function the agent is using tabrez2019explanation . We assume the agent’s dynamics model is correct $(T_{h}=T)$.

Inferring an agent’s reward function $R_{h}$ (e.g., the agent’s beliefs about the task w.r.t. the world) is non-trivial and an active field of research. Tabrez et al. tabrez2019explanation provides an approach to this problem by solving for whether the agent knows about particular components of the reward function; therefore if one can maintain a belief over which rewards another agent is aware of, their reward function may be able to be inferred.

Intuitively, estimating $R_{h}$ is achieved by observing agent behavior and the goal states they approach — in the emergency evacuation domain, this corresponds to observing their coverage of the building and which exits they are heading toward. Once we obtain $R_{h}$, we can simulate the MDP $M$ using $R_{h}$ to get the agent’s expected policy $\pi_{h}$.

Once we have our belief of the agent’s possible reward function $R_{h}$, we identify divergences between the optimal policy $\pi^{*}$ and the policy of the agent $\pi_{h}$ that would cause a reduction in the agent’s expected cumulative reward. We do this by comparing agent policies trained on $R$ and $R_{h}$, where $R$ is the true reward function of the domain and $R_{h}$ is the reward function used by the agent. We find a set of states $\bar{S}$ about which we communicate updated reward information to augment $R_{h}$, such that a more optimal policy (closer to the expected reward of $\pi^{*}$) is elicited (Figure 3b).

We approach the problem of efficiently describing state regions as a set cover problem, trying to find the smallest logical expression of communicable predicates to succinctly describe target states as in Hayes and Shah hayes2017hri . Unlike prior work, we solve for the minimum set cover of the targeted state region using an Integer Program. The inputs to our IP formulation include:

• •

  A set of state indices $\bar{S}$ that correspond to states with expected reward function divergence that needs to be communicated about for policy repair.

  $\bar{S}=\{s_{1},s_{2},\cdots,s_{|\bar{S}|}\}$,

• •

  A set of communicable predicates $\bar{P}=\{p_{1},p_{2},\cdots p_{|\bar{P}|}\}$ requiring the following for a solution to exist:
  

  $\exists\ \bar{Q}\subseteq\bar{P}$ such that $s\in\bar{S}$ is covered by a predicate in $\bar{Q}\text{, }\forall\text{ }s\in\bar{S}$ — for every state that needs to be covered ($\bar{S}$), there exists a non-empty subset of predicates that can cover it.

• •

  A set of costs $\bar{C}=\{c_{1},c_{2},\cdots,c_{|\bar{P}|}\}$, such that $c\neq 0\text{ }\forall\ c\in\bar{C}$ — every predicate has non-zero cost associated with using it to update the agent’s reward function $R_{h}$.

• •

  The desired trajectory for the agent $\bar{O}=\{o_{1},o_{2},\cdots,o_{|\bar{O}|}\}$, where $o_{i}$ describes the state achieved after taking the $i^{th}$ action following the optimal policy from the start state.

The cost for each predicate can be customized per task. This is an important characteristic, as many factors may influence the cost of a predicate. One such criteria for defining cost can be the length of the string describing the predicate. Such a criteria could generate more easily understood explanations by imposing penalties for being too verbose.

A solution to the policy elicitation problem consists of selecting predicates to communicate reward information about specific state regions such that a more optimal policy is produced within some $\epsilon$ bound of the optimal policy’s expected reward, $|E_{R}(\pi|R)-E_{R}(\pi|R_{h})|\leq\epsilon$. To minimize this objective while satisfying all the constraints, we define the mathematical formulation of our IP, which we refer to as SPEAR-IP, below:

subject to

where we define the $|\bar{S}|\times|\bar{P}|$ matrix $U$ by

and, the $|\bar{O}|\times|\bar{P}|$ matrix $V$ by

where $i$ and $k$ are the indices into sets $\bar{P}$ and $\bar{O}$ respectively. $x_{j}\in\{0,1\}$ is a binary variable with $x_{j}=1$ meaning predicate $p_{j}$ is included in the cover and $x_{j}=0$ indicating exclusion from the set cover. Equation 1 is the objective function which needs to be minimized for the desired set cover based on cost. The first term of Equation 1 ensures that the net cost of the predicates selected is as low as possible.

Equation 1’s second term heavily penalizes the objective function if the chosen set cover overlaps with the desired path, in the case of communicating a negative reward (for positive reinforcement this can be reversed). $L$ is a large positive number, and is used to encapsulate near-optimal behavior in the objective function (providing a soft constraint). The second term can be used separately to provide a hard constraint for finding a solution which will definitely elicit the desired path, but this approach inherently restricts the ability of an integer program to find solutions which would provide a near optimal policy update. This second term in the formulation leads to three possible cases: 1) Set cover solution with low objective value; 2) No solution for the set cover; and 3) Set cover solution with high objective value.

Cases 1 and 2 are simple and describe the ability of SPEAR-IP to solve the set cover. Case 3 is interesting and provides the option of further exploration to find an alternate solution with the given set of predicates. We can use the set cover from Case 3 to determine which states in the cover overlapped with the desired path. Using these states as a reference, we can simulate an alternate desired policy by penalizing these states in the true reward function as well, effectively coming up with a contingency for not having precise enough language available. This process of penalizing states through $R$ is repeated until either Case 1 or 2 is achieved (i.e. an immediate solution with low objective value or no solution for given a set of predicates).

Equation 2 provides a hard constraint for the inclusion of states from $\bar{S}$ in the set cover. Equation 3 defines the elements of matrix $U$, which encapsulates cover constraints from $\bar{S}$ (inclusion of all states). Equation 4 defines the elements of matrix $V$ using the desired trajectory $\bar{O}$, encapsulating the requirements for eliciting the desired policy.

Here we outline the details of SPEAR for finding the predicates to communicate which will elicit optimal behavior, as presented in Algorithm 1. We continue using our running example of an emergency evacuation scenario (Figure 1-right) to build intuition and illustrate the inner workings of our algorithm for a human-robot collaborative scenario.

Given an estimate of the human agent’s reward function, SPEAR communicates a reward update in an attempt to elicit the best possible policy. To achieve this, (Line 3-16) we perform multiple forward rollouts of the agent policy $\pi_{h}$ derived from $R_{h}$ and (Line 13-16) compare the accumulated expected reward to the reward threshold $R_{L}$. The moment this threshold is crossed, the reward from that transition is determined to be relevant for updating $R_{h}$ and the state is added to the set cover.

This can be easily illustrated for our example, where Figure 2b shows the belief of an agent trying to evacuate the building. Figure 3b gives insight into how updating the agent’s reward function can result in an optimal policy even if the agent’s belief about the fires doesn’t truly match the environment.

After finding the states responsible for meaningful reward divergence, we find a minimal set cover of communicable predicates that map onto these states. This is achieved through SPEAR-IP, discussed in Section 4.3. We use a third-party optimizer gurobi to solve SPEAR-IP (Line 18), where the $predicate\_selection$ method takes in the states to cover ($\bar{S}$) and the best agent policy $\pi^{*}_{h}$. This gives a set of communicable predicates and a final objective value using Algorithm 2.

Line 19 checks whether or not a solution exists for a given set of predicates. In lines 20-28, our algorithm evaluates case 3 to determine if alternate solutions exist. In lines 23-27, SPEAR performs multiple forward rollouts of the optimal policy to find states responsible for a high objective value. In line 26, these states are penalized in the true reward function ($R$) to incentivize the algorithm to find an alternate solution which avoids these states. This enables SPEAR to explore alternate solutions, making it more robust in applications where the available predicates are insufficient, overcoming barriers due to imprecise or unavailable language.

In line 28, now that all the appropriate states are penalized, the algorithm repeats the whole procedure from the beginning with a modified $R$, continuing this process until it finds a low objective solution or no solution (case 1 or 2). Finally, in line 30, the update is serialized as semantic feedback using the $Set\_Cover$. This feedback generation strategy uses negative reward to drive an agent’s policy away from undesirable states, as improved policies can then be elicited through the exclusion of states along the agent’s (hypothesized) originally intended path. While similar outcomes can be achieved via positive reward, a state exclusion-based strategy generally allows for the use of less precise predicates.

In Algorithm 2, we produce the set cover for communicating the reward update. Lines 4-7 evaluate states we want the agent to traverse (the desired trajectory $\bar{O}$) by performing a forward rollout of the best attainable agent policy $\pi^{*}_{h}$. In lines 8-13, the matrices U and V from Equation 3-4 are defined, which form the basis of the constraints governing the inclusion of states to cover and exclusion of optimal states (when giving information about negative reward) in the set cover respectively. Finally, in line 15, SPEAR-IP is solved using the matrices U and V to give $Set\_Cover$ and Objective.

In the first scenario, one agent needs to correct the policy of a second robotic agent to prevent it from removing specific items during a pick and place task (Figure 4). Importantly, these robots do not operate in the same state space, and therefore cannot directly communicate reward function updates to each other. Here, the Rethink Robotics Sawyer has been tasked with clearing trash from a table, and is operating with the malformed belief that all objects on the table’s surface are trash. The Kinova Movo is observing this scene and has accurate knowledge about the environment (i.e., it knows that certain objects in the scene aren’t trash). As Sawyer’s reach expresses intent to remove one of the items that isn’t trash, Movo detects that Sawyer’s policy is incorrect. Movo corrects Sawyer’s behavior by providing an update for its reward function, allowing Sawyer to compute a better policy. We accomplish this reward update step by generating semantic expressions about the reward function in parts of the state space (i.e., predicate-grounded natural language communicating about a region of negative reward) for Sawyer using SPEAR.

Within this task, Sawyer used a series of ArUco markers garrido2014automatic to track the 6-dof poses of various objects (states) on the tabletop. Using these poses, Sawyer systematically transferred all items classified as trash to the waste bin using an interruptable pick and place action. As Movo observes Sawyer, it detects Sawyer’s end effector reaching for one of the energy drinks on the table, thus indicating the intent to remove that object, and signalling to Movo that Sawyer’s policy was malformed. Using SPEAR, Movo is able infer Sawyer’s erroneous belief from this observed action (that a non-negative reward is associated with putting the energy drink in the trash). Movo performs a forward rollout with the inferred policy of Sawyer to predict which state transitions with negative reward Sawyer will reach. Next, Movo computes an updated policy for Sawyer by determining which states should be assigned negative reward and which of the available predicates are needed for communicating it with Algorithm 2. A DNF formula of predicates that covers the desired states is then computed and communicated by Movo through natural language: “There is a Bad Reward when energy drink is in the trash”. Finally, Sawyer uses its own set of predicates to map the communication into its own state space, update its reward function accordingly, and reconverge a repaired policy.

In our second scenario, our autonomous agent must help a human agent escape from a smart building in which a series of fires has broken out, as shown in Figure 2. While people in the building are not aware of the fire locations, they are assumed to understand the generated predicate-based language.

The building layout for each trial is generated with a stochastic placement of rooms, hallways, and exits over a gridworld of fixed size. For example, a gridworld of size 40X40 (1600 states) may have parameters: rooms = 10, hallways = 40, number of exits = 5. These can be changed depending on the desired architecture. We then use these areas to create predicates which are grounded in the layout of the building. In our validation, we also use randomly generated predicates to prove the generalizability of our approach.

To accommodate the full range of possible state regions to cover using predicates, we create composite predicates by creating the power set of base predicates. By combining base predicates into composite predicates, each scenario has an upper bound of $2^{n}-1$ total predicates.

Once the building layout and predicates are generated, we observe a randomly placed human agent explore a hazard-free building over a fixed number of episodes. The human agent’s policy is then trained to always seek the shortest path to the closest exit that was discovered during these exploration episodes. Initially, SPEAR has no knowledge about which exits the human is aware of, but gradually, its belief about the human’s reward function is updated from these observations. Next, we begin the evaluation by adding fire in the building via random placement and expansion. Once this process completes, we start the SPEAR evaluation. Predicates from SPEAR-IP are used to update the human agent’s reward function during the episode. We update the policy of the human using the repaired reward function after each update.

We evaluated the performance of our algorithm as a function of state space size and the number of predicates using different building layouts. We also demonstrated that our algorithm can generalize to arbitrary state mappings by using randomly generated predicates. To fairly evaluate this, we randomly generate ball-shaped predicates (evaluating to true within a given radius of a random state vector). When in a structured environment, the predicates grounded in the layout of the building tend to naturally make it easier to find potentially hazardous predicates. For example, in Figure 3a, predicates are grounded in the layout of the building and fire can be avoided through communicating the “Center Hallway” predicate as it is directly associated with pathway of the human. However, if predicates are placed stochastically throughout the map (corresponding to cases where the language isn’t tailored to the domain), finding a solution becomes more difficult. Hence, by using randomly placed predicates we make it difficult for the algorithm to find a low cost solution while also directly increasing the computational time, providing performance analysis for cases of predicate-domain mismatch.

We qualitatively assess our algorithm in an emergency evacuation scenario for both deterministic and stochastic environments (Figure 5). In the stochastic domain, a stochastic transition function was applied describing the model’s action-based state transition dynamics. For each map (25 X 25) in both environments, we evaluated our algorithm over the course of 100 episodes. In each episode the reward was computed both before and after the SPEAR update (exit: +100, fire: -100, and each step: -1 ). At each time step, our agent would take the prescribed action with a probability of 85% and would alternatively take a step in a different random direction. For our stochastic evaluation, we set our forward rollout count parameter, $k$, to 10. The results from our simulations show a substantial improvement in the episodic reward after the SPEAR update, (Figure 5) demonstrating its utility in both deterministic and stochastic domains.

Furthermore, we do performance analysis as a function of predicate count by dividing into two success cases described in Section 4.3: 1) Maps with a low objective value solution (Case 1); and 2) Maps with high objective value solution (Case 3).

For each map of a given size, we start with 100 base predicates and increase in increments of 10. Figure 6-right shows how algorithm performance changes with increasing predicate count on low objective value maps. For Case 1 solutions our algorithm exhibits linear computational costs as a function of the number of predicates, and the set cover can be computed within 50 seconds with nearly 10,000 communicable predicates to choose from. To provide context for the significance of this result, we can consider a comparison against the state-of-the-art method for succinctly describing state regions (using the Quine-McCluskey algorithm) by Hayes and Shah hayes2017hri . Our Integer Programming approach to this set cover problem achieves a several order of magnitude improvement over the QM based method (where set covers with 10 possible predicates takes  60-120 seconds to compute on similar hardware, deteriorating exponentially as a function of predicate count). SPEAR is made possible by this performance improvement, effectively operationalizing the insight of Hayes and Shah’s work as a means of communicating information about those state regions — enabling SPEAR’s policy update method.

Similarly, we plot the performance for Case 3 solutions as predicate count increases (Figure 6-left). We observe that the plots again scale linearly in practice with respect to the number of predicates, but with higher computation time due to multiple SPEAR runs. Computation time is higher here because the algorithm has to explore alternative solutions for the desired policy, solving for set cover solutions multiple times (Section 4.3).

Our method achieves a dramatic improvement in computation time over the QM based set cover approach for two reasons: offline computation of predicates and allowing approximate solutions. QM uses a two-step procedure: 1) finding prime implicants, and 2) using those prime implicants to find the exact minimal set cover (see mccluskey1956minimization ). In SPEAR, we alleviate a significant time sink by pre-computing predicate values over the state space (which the QM approach had to solve online in step 1). Secondly, since SPEAR is often able to use approximate set covers to communicate its reward updates (i.e., sometimes it’s okay to over-state or under-state the reward region, as in Figure 3b), we are able to relax the requirement of having an exact set cover. In contrast, QM solves for exact set cover making it slower in execution and limited in application. For example, referring to Figures 2c and 3a, QM will try to find the precise set cover for covering only the two fire states in the central hallway (and fail as there is no exact solution). Whereas, SPEAR will try to find the approximate set cover that encompasses those fire states, accepting inaccuracy if necessary so long as it still achieves the same outcome as if there were a perfect solution (Case 1) and preferring a suboptimal solution to no solution (Case 3). This added layer of approximation heuristic makes SPEAR faster and more flexible than the QM based approach.

Interestingly, we found some irregularities in performance as illustrated within the 80 X 80 world (Figure 6-left-purple). We found that a sudden dip in computation time can occur when new language enables the algorithm to find a Case 1 (single-loop of algorithm) or cheaper Case 3 (still multiple loops of the algorithm, but fewer) solution.

The final part of our analysis looks at the performance of our algorithm as domain size increases with fixed predicate count (100 base predicates). We generate a set of maps with similar parameters for a fixed state space size, sampling from these maps to get the mean and confidence bound for 10 simulation runs as shown in Figure 7. A significant take-away from this analysis is the insight that an attention mechanism is more important for abstracting and reducing the domain’s state space than for limiting the number of predicates to consider, as prior work anticipated abel2018state ; hayes2017hri ; tabrez2019explanation .

We have shown that SPEAR enables dramatic improvements in agent performance through policy elicitation, while also contributing a novel method for communicating about state regions that substantially outperforms prior work. These contributions enable semantically guided policy manipulation for a much broader class of problems than was previously possible, providing a method that scales linearly with predicate count as opposed to exponentially, advancing the state-of-the-art in autonomous coaching through new algorithms and improved foundational capability.