Using Machine Teaching to Investigate Human Assumptions when Teaching Reinforcement Learners

In our human experiments, we focus on a family of Q learners, denoted by $\mathcal{L}$, that is widely studied as potential theory of mind for humans, among which we describe two variants: (1) standard Q-learning and (2) Action Signaling (AS) [10]. The two learners mainly differ in their internal knowledge representation and how they perform learning updates.

A Q-learning agent stores an estimate of the Q table, $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, which approximates the future cumulative rewards that the agent can receive after perform an action $a\in\mathcal{A}$ in a state $s\in\mathcal{S}$. The learning update rule of Q-learning is defined by 2 parameters, the learning rate $\alpha$, and the discounting factor $\gamma$. $\alpha$ determines how aggressive the learner updates the current belief given the new experience, and $\gamma$ indicates how much the learner value future rewards compared to immediate rewards. Specifically, given a new piece of experience $e_{t}=(s_{t},a_{t},s_{t+1},r_{t})$, Q-learning only updates the $(s_{t},a_{t})$ entry of its Q table as

$$Q_{t+1}(s_{t},a_{t})=(1-\alpha)Q_{t}(s_{t},a_{t})+\alpha(r_{t}+\gamma\max_{a^{\prime}}Q_{t}(s_{t+1},a^{\prime}))$$

(1)

An Action Signaling (AS1) agent stores a multinomial distribution over actions for each state, representing its current belief distribution of the optimal action [10]. In this paper, we represent the multinomial distribution also with a table, $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, where $\sum_{a\in\mathcal{A}}Q(s,a)=1$. The learning update of an AS agent is defined by a single parameter, the learning rate $\kappa$, which serves the same role as $\alpha$ in Q-learning. Given a new piece of experience $e_{t}=(s_{t},a_{t},s_{t+1},r_{t})$, an AS agent will update the belief distribution over the current state $s_{t}$. If $r_{t}>0$, the probability w.r.t. $a_{t}$ will increase, whereas if $r_{t}<0$, the probability w.r.t. $a_{t}$ will decrease. In contrast to Q-learning, an AS agent does not make use of the next state $s_{t+1}$, and does not aim at optimizing long term reward. Specifically,

$$Q_{t+1}(s_{t},a)={Q_{t}(s_{t},a)e^{1_{[a=a_{t}]}\kappa r_{t}}\over\sum_{b\in A}Q_{t}(s_{t},b)e^{1_{[b=a_{t}]}\kappa r_{t}}},\;\forall a\in A.$$

(2)

We further observe that even without the normalization step, $\operatorname*{\arg\max}_{a}Q_{t}(s,a)$ will not change. Therefore, the learning update rule 2 can be equivalently changed to $Q_{t+1}(s_{t},a)=Q_{t}(s_{t},a)e^{1_{[a=a_{t}]}}\kappa r_{t}$. We again observe that if instead of $Q_{t}(s,a)$, we store $Q^{\prime}_{t}(s,a)=\log Q_{t}(s,a)$, then the update rule becomes $Q^{\prime}_{t+1}(s,a)=Q^{\prime}_{t}(s,a)+\kappa r_{t}$. Finally, we can drop the $\kappa$ factor, since it’s a constant scaling on all $(s,a)$-pairs, and we get $Q^{\prime}_{t+1}(s,a)=Q^{\prime}_{t}(s,a)+r_{t}$. Therefore, we have established that AS is equivalent to a variant of Q-learning, which simply stores the sum of rewards received on each $(s,a)$-pair. This motivates us to define another variant of the AS agent that instead of taking the sum of rewards, takes the average of rewards on each $(s,a)$-pair.

An Action Signaling (AS2) agent stores the average of rewards on each $(s,a)$-pair, whose update rule can be equivalently written as

$$Q_{t+1}(s,a)=(1-\frac{1}{n_{t}(s,a)})Q_{t}(s,a)+\frac{1}{n_{t}(s,a)}r_{t}$$

(3)

where $n_{t}(s,a)$ denotes the number of times the current $(s,a)$-pair has been visited. Similar to AS1, AS2 do not take into account of future rewards, and is in fact equivalent to a Q-learning agent with $\gamma=0$, and time-varying learning rate $\alpha_{t}=1/n_{t}(s,a)$. For those who are familiar with the classic RL/multi-armed bandit literature, the AS2 agent is equivalent to a multi-armed bandit algorithm that treats the MDP as $S$ parallel $A$-arm bandits.

We further assume that all learners will behave according to the $\mathbf{\varepsilon}$-greedy policy w.r.t. the current Q table, i.e.

$$a_{t}=\pi_{t}^{\varepsilon}(s_{t})=\left\{\begin{array}[]{ll}\operatorname*{\arg\max}_{a}Q_{t}(s_{t},a),&\mbox{ w.p. }1-\varepsilon\mbox{, break ties uniformly}\\ \mbox{uniform from }A,&\mbox{ w.p. }\varepsilon.\end{array}\right.$$

(4)

We distinguish two teaching settings: In a white-box teaching setting, we assume an omniscient teacher, who has knowledge of the underlying MDP $M$ and the learning agent’s parameters. It also observes the current interaction $s_{t},a_{t},s_{t+1}$ as well as the internal state of the agent $Q_{t}$, before providing the reward signal $r_{t}$; In a black-box teaching setting, we assume that the teacher can still observe $(s_{t},a_{t},s_{t+1},Q_{t})$ but does not know the precise learner update rule, and therefore cannot accurately predict the consequence of the current reward signal.

The teacher’s goal is to drive the learner to learn a target policy $\pi^{\dagger}$. For example, the teacher may want the learner to always perform a specific action $a^{\dagger}\in A$ at state $s^{\dagger}\in S$. This example goal can be expressed as a target set of Q tables that satisfy $\mathcal{Q}^{\dagger}:=\{Q:Q(s^{\dagger},a^{\dagger})>Q(s^{\dagger},a),\forall a\neq a^{\dagger}\}$. The teaching succeeds if the learner’s $Q_{t}$ falls into $\mathcal{Q}$ at some time step $t$, in which case the teaching process terminates. We are interested in calculating a teaching strategy that achieves the teaching goal with the fewest time steps.

One of our main observations is that the optimal teaching problem in the white-box teaching setting forms a higher level teaching MDP $\mathcal{N}=(\Xi,\Delta,\rho,\tau)$:

• •

  The teacher observes the teacher state $\xi_{t}\in\Xi$, which jointly characterizes the environment and the learner at time $t$: $\xi_{t}:=(s_{t},a_{t},s_{t}^{\prime},Q_{t}).$

• •

  The teacher’s action space consists of all possible rewards $r_{t}\in\mathbb{R}=\Delta$.

• •

  The teacher receives a constant cost of $\rho_{t}=1$ for every time step before the teaching goal is accomplished.

• •

  The teaching state transition probability is specified by $\tau(\xi_{t+1}\mid\xi_{t},r_{t})$. The new attack state $\xi_{t+1}=(s_{t+1},a_{t+1},s^{\prime}_{t+1},Q_{t+1})$ is generated as follows: $s_{t+1}$ is copied from $s_{t}^{\prime}$ in $\xi_{t}$; $a_{t+1}\sim\pi^{\varepsilon}_{t+1}(s_{t+1})$; $s^{\prime}_{t+1}\sim P(\cdot|s_{t+1},a_{t+1})$; $Q_{t+1}$ is the learner’s updated Q table.

The optimal teaching strategy is one where the teacher minimize its cumulative attack cost, $\sum_{t=0}^{T}\rho_{t}$, s.t. $Q_{T}\in\mathcal{Q}$. Due to the randomness of the MDP as well as the learner’s behavior policy, this quantity is a random variable, and thus we instead minimize its expected value. Formally, the teacher seeks a time-invariant teaching policy $\phi^{*}$: $\phi^{*}=\operatorname*{\arg\min}_{\phi:\Xi\mapsto\Delta}\mathbb{E}_{\mathcal{N}}\left[\sum_{t=0}^{T}\rho_{t}\mbox{ , .s.t }Q_{T}\in\mathcal{Q}^{\dagger}\right].$ We will also denote the shortest expected time step to achieve the teaching goal as the teaching dimension for the corresponding teaching problem instance, i.e.

$$TD(M,L,Q_{0},\pi^{\dagger})=\min_{\phi:\Xi\mapsto\Delta}\mathbb{E}_{\mathcal{N}}\left[\sum_{t=0}^{T}\rho_{t}\mbox{ , s.t. }Q_{T}\in\mathcal{Q}^{\dagger}\right]$$

(5)

The optimal control formulation allows us to computationally solve for the optimal teaching strategy on any specific teaching instance, defined by the MDP, learner type and target policy to be taught, using any optimal control solver. In this paper, we use Twin Delayed DDPG (TD3) [4], a state-of-the-art Deep Reinforcement Learning (DRL) algorithm that solves continuous control problems.

Our second theoretical insight is that the any learner in the Q-learning family $\mathcal{L}$ has the same teaching dimension. Specifically,

In other words, under the white-box setting, an optimal teacher can teach a learner in the family $\mathcal{L}$ equally fast.

Participants. We recruited 791 participants through Amazon MTurk. The number of participants was chosen a priori based on the authors’ intuition from similar previously conducted studies. We excluded 42 participants (11 for failing to complete the task, 19 due to experiment error, and 12 who selected “do nothing” for at least 36 steps). In addition, the dogs that were trained successfully with steps less than the optimal length (the number of steps the optimal teaching policy needs) were excluded from the analysis. For example, if the subject gave punishment on every step and the dog luckily went to the left at every tile all the way from the rightmost tile to the leftmost tile, the dog could be trained in just 4 steps. These data were excluded because they did not really reflect a success in training, but more likely a misunderstanding of the goal and luck. This composes 9.03 % of the total dogs (203 out of 2247 dogs).

Interface/Stimuli. The dog training task took place in a 4 $\times$ 1 MDP with an absorbing state on the right. Figure  1 shows the visual interface that the participants interacted with. Four states were represented by four tiles that the dog could walk on, and the absorbing state was represented by a door. At each step, the dog could only go right or left from a tile to the nearby tile or the door. If the dog went left at the leftmost tile, the dog would stay at the same tile. If the dog went right at the rightmost tile, the dog would go to the door and then placed back to the rightmost tile. The training for a dog ended if the dog had successfully learned the target policy, or the dog had already taken 40 steps but still had not learned the target policy. Once the training for the dog ended, a new dog with a different color would be shown and the participant was asked to train the new dog. The internal states were displayed as two rows provided by a “brain scanner”, which corresponded to the Q table and current optimal policy. At the beginning of each dog, the dog was placed at the rightmost tile with an initial Q table where the Q value of each state-action pair is zero. Participants responded via a continuous slider (feedback of -1 to 1), or could select a button to “do nothing” (feedback of zero).

Procedure. Participants were asked to teach three dogs to go home from any tile. They were given an extensive quiz about the instructions and could not continue until every question was answered correctly (see Supplementary Materials). There were two between-subjects conditions: learner type $\times$ learning dynamics. Each participant was assigned to either one of the four traditional Q-learners ($\gamma\in\{0.0,0.1,0.45,0.9\},\alpha=0.9$) and two action-signaling models. Learning dynamics were either shown (the whitebox setting) or not shown (the blackbox setting) to the participant. if they were shown, then the internal states displayed to the participant were synchronized to the current position of the slider. Otherwise the internal states only updated after the participant provided feedback. On each trial, the dog would move from one state to another. It followed an $\varepsilon$-greedy policy ($\varepsilon=0.1$), where the policy was the optimal one for the current Q-matrix. When a random action was selected for the dog, a squirrel would appear in the direction of that action (participants were told that when a squirrel appeared, the dog would move towards it no matter what its internal states were). After the dog moved, the participant would respond by dragging the feedback slider or hitting the “do nothing” button. Training concluded when the participant successfully taught the target policy or 40 steps had completed. Participants trained three dogs and then was given a short survey to ensure that they treated the slider symmetrically and gather standard demographic data.

Figure  2 shows the success rate of participants at training the full policy and the average number of steps taken when a dog was successfully trained. To analyze the success rate, we fit a mixed-effects logistic regression model where learner type, internal dynamics, and their interaction were fixed effects, and participant was a random effect. Learner type significantly influenced the success rate for a participant ($\chi^{2}(5)=20.7,p<0.001$), but the internal dynamics did not ($\chi^{2}(1)=0.66,p=0.42$). To analyze the average number of steps for successfully trained dogs, we fit a mixed-effects linear regression where learner type, internal dynamics, and their interaction were fixed effects, and participant was a random effect. There also was no interaction ($\chi^{2}(2)=1.64,p=0.90$). Both learner type and internal dynamics significantly affected the average number of steps a person took to train a dog successfully ($F(5,341.76)=2.21,p=0.05$ and $F(1,248.82)=4.19,p<0.05$, respectively).

How well did people teach the dogs? Clearly they were suboptimal – at best, the average success rate was 51% and when successful took about 21 steps (optimal has a success rate of 100% and takes an average of 11 steps). To analyze whether people adapted their teaching over time, we conducted the following permutation test. For each participant, we created 1000 simulated Q-learners. For each simulated Q-learner and state-action pair, we sampled a random permutation of the feedback provided by the participant for that state-action pair. This provides a Monte Carlo test of whether human teaching adapted with learning. Participants clearly adapted their behavior: none of the simulated Q-learners for any participant ever learned the target policy when the feedback for each action-state pair randomly permuted. Thus, human teaching is quite successful in this task (albeit still suboptimal).

In sum, we observed that human teachers are suboptimal: they did not always succeed in teaching the policy to an agent; and when they did, they required more steps compared to the 11 steps of the optimal teaching algorithm in Section 3. This is not surprising: we never expected humans to be optimal teachers. Our important discovery is that human teachers’ “favorite student” is Q0, which differs from other Q-learning agents in two key parameters: the smallest possible discounting factor $\gamma=0$, and a large Q-update step size $\alpha=0.9$. What does this mean? The favorite student is one which is predictable by the teacher (no complications from discounted future rewards because $\gamma=0$) and amenable to myopic control from the teacher (large $\alpha$ emphasizes immediate teacher reward). We thus suggest that human teachers assume such predictable, myopically controllable students when they teach. On the other hand, whether the teacher can see the “guts” of the agent (whitebox / blackbox setting with effect of reward slider on / off, respectively) turns out to not be very important for the teacher.