\subsection*{$\diamondsuit$ ##1}}
}



\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}{Remark}
\newcommand{\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\Box$}\smallskip}{\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\Box$}\smallskip}
\newenvironment{proof}{\par\noindent{\it Proof.}}{\(\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\Box$}\smallskip\) \par}
\newenvironment{sketch}{\par\noindent{\it Proof Sketch.}}{\(\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\Box$}\smallskip\) \par}

\renewcommand{\O}[1]{\mbox{$O(#1)$}}
\newcommand{\Om}[1]{\mbox{$\Omega(#1)$}}
\newcommand{\Th}[1]{\mathit{\Theta(#1)}}

\newcommand{\del}{\nabla}                  %
\newcommand{\dprod}{\cdot}                 %
\newcommand{\times}{\times}
\newcommand{\vct}[1]{\mbox{{\bf #1}}}      %
\newcommand{\mat}[1]{\mbox{{\bf #1}}}      %
\def\norm#1{\mbox{$\parallel#1\parallel$}}      %
\newcommand{\vnorm}[1]{\mbox{${            %
            \left|{\bf #1}\right|}$}}
\newcommand{\mnorm}[1]{                    %
            \mbox{${\left\|{\bf #1}\right\|}$}}

\newcommand{\varepsilon}{\varepsilon}
\newcommand{\varpho}{\varpho}
\newcommand{\varphi}{\varphi}

\newcommand{\degrees}[1]{\ensuremath{#1^\circ}}
\newcommand{\mathop{\mathrm{arg\,max}}}{\mathop{\mathrm{arg\,max}}}
\newcommand{\mathop{\mathrm{arg\,min}}}{\mathop{\mathrm{arg\,min}}}

\newcommand{A}{A}
\newcommand{\textbf{a}}{\textbf{a}}
\def{\tt \char'40}{{\tt \char'40}}







\section{Experiments}
 We carried out two human-subject experiments to demonstrate how COACH works, one in simulation (Overcooked-AI~\cite{Carroll2019OnTU}) and the other with a real robot (Cooperative Ball Maze{}). Experiment setups are shown in Figure~\ref{fig:exp_setup}. We investigated the teaching performances of three types of teachers: 
the \textbf{fully-assistive} teacher who performs optimally concerning the student's initial capability, the \textbf{student-aware} teacher who behaves according to our teaching strategy, and the \textbf{random} teacher. The random teacher in the Cooperative Ball Maze{} experiment chooses sub-skills randomly, while the random teacher in the Overcooked-AI{} experiment executes actions randomly.
\subsection{Setups}
\noindent\textbf{Overcooked-AI.} Overcooked-AI is a benchmark environment for fully cooperative human-AI task performance and has become a well-established domain for studying coordination~\cite{knott2021eval,Charakorn2020InvestigatingPD, nal2021intention, sarkar2021pantheonRL}. The goal of the game is to cook and deliver as much soup as possible in a limited time. 
We decompose the policy into two sub-skills: \emph{putting ingredients in the pot} and \emph{delivering the soup}. To put ingredients in the pot, there exists one \emph{efficient strategy }to pass the ingredient through the middle table. 
In brief, rather than picking up one onion at a time and putting them into the pot, the efficient strategy is 1) put multiple onions on the middle table; 2) go to the pot; 3) pick up onions from the middle table; 4) put them into the pot. The overall idea is to reduce the number of movements needed to deliver the same amount of ingredients. 
\begin{wraptable}{r}{0.48\columnwidth}
    \centering
    \begin{tabular}{cc}
        \hspace{-10pt}\cincludegraphics[width=0.24\textwidth]{figs/setup.png}& 
        \cincludegraphics[width=0.2\textwidth]{figs/maze_setup_blur.png}
        \\
        \hspace{-10pt}(a) & (b)
    \vspace{-2mm}
    \end{tabular}
    \captionof{figure}{Experiment setups. (a) Overcooked-AI layout: human participants control the ``chef'' and the robot controls the ``robot''. (b) The real robot setup of Cooperative Ball Maze{} with a simplified setting.}
    \label{fig:exp_setup}
\end{wraptable} 
We recruited $N$=20 (8 females and 12 males) participants and randomly assigned them into three groups, each with a different teaching strategy. Students are trained with different teachers and are evaluated with a common unseen partner. We emulate the human partner in evaluation using a trained model. 
Each participant was trained for 5 games and then evaluated for 1 game. 

\noindent\textbf{Cooperative Ball Maze.} The Cooperative Ball Maze{} game requires coordination from both the robot and the human. Each party will hold one side of the maze board and tilt it to move the ball out from one of the two exits. 
We define two sub-skills \emph{leading the rotation} and \emph{following the rotation}.
We recruited $N$=21~(10 females and 11 males) participants to carry out human-subject experiments.
The participants were first evaluated in the two sub-skills, then trained for 20 interactions, and finally re-evaluated in the two sub-skills. Details can be found in the supplementary materials.
\begin{table}[t]
    \centering
    \begin{tabular}{ccc}
        \cincludegraphics[scale=0.2]{figs/overcooked_result.pdf}& 
        \cincludegraphics[scale=0.2]{figs/overcooked_percent.pdf}&
        \cincludegraphics[scale=0.2]{figs/overcooked_human_reward_fraction.pdf}
        \\
        \hspace{12pt}(a) & \hspace{22pt}(b) & \hspace{22pt}(c)
    \end{tabular}
    \captionof{figure}{Results of the Overcooked-AI experiment.
    (a) Rewards achieved together by the human-robot pairs during training and evaluation. The error bars correspond to the 95\% confidence intervals (95\%CI). The student-aware teacher outperformed the fully assistive and the random teachers in terms of the evaluation reward (with one-sided $p$-values $0.001$ and $0.03$).
    (b) Percentage of students who found the efficient strategy. None of the students are aware of this strategy at the beginning of the training.
    (c) Percentage of reward achieved by the human participants during training.
    }
    \label{fig:overcooked_result}
\end{table}
\begin{table}[t]
    \centering
    \begin{tabular}{ccc}
        \cincludegraphics[scale=0.2]{figs/ballmaze-preference.pdf}& %
        \cincludegraphics[scale=0.2]{figs/ballmaze-performance.pdf}&
        \cincludegraphics[scale=0.2]{figs/ballmaze-improvement.pdf}
        \\
        \hspace{12pt}(a) & \hspace{22pt}(b) & \hspace{22pt}(c)
    \end{tabular}
    \captionof{figure}{Results of the Cooperative Ball Maze experiment.
    (a) Evaluation of performances of the two sub-skills of all participants. The marker styles correspond to the sub-skill preferences of the participants.
    (b) Evaluation performances. The error bars correspond to the 95\%CIs.
    (c) Improvements after 20 interactions. The error bars correspond to the 95\%CIs.
    The students improve more under student-aware teachers than both fully-assistive and random teachers (with one-sided $p$-values $0.069$ and $0.039$). 
    }
    \label{fig:ballmaze_result}
\end{table}
\subsection{Results}
\emph{A fully-assistive teacher impedes human's acquisition of skills}. In the Overcooked-AI experiment shown in Figure~\ref{fig:overcooked_result}(a), we observe that the students trained with a fully-assistive teacher perform worse than the students with a random teacher: it seems that a student becomes ``lazy'' and free rides the teacher when the teacher unilaterally adapts to the student and performs optimally. We further investigate the learning pattern of the ``lazy student'' problem and find out that \emph{this ``laziness'' does not lie in the student's reluctance to take actions, but rather in the lack of motivation to explore and improve}. In Figure~\ref{fig:overcooked_result}(c), we show the percentage of reward achieved by the student in Overcooked-AI during training. Compared with the student-aware counterpart, the percentage of reward achieved by humans is similar. However, only 17\% of the participants of the group find out the efficient strategy (Figure~\ref{fig:overcooked_result}(b)), which is crucial to achieving high scores in the evaluation. 

\emph{Partially assistive or random partner motivates students to explore new strategies.} 
By leaving some/all work to the student, partially assistive and random teachers both motivate the student to acquire new skills. This is shown in Figure~\ref{fig:overcooked_result}(b) that most of the students under these two teachers can find out the efficient strategy in Overcooked-AI. However, their performance and the robustness of the learned strategies differ significantly. Though multiple explanations could account for it, we hypothesize the student under the random teacher learns a single fixed strategy to finish the task alone (Figure~\ref{fig:overcooked_result}(c)). Such a strategy that completes the task alone cannot utilize the possibly helpful inputs from the partner, therefore resulting in a poorer performance score.

\emph{An individualized curriculum should be designed for each student.} 
In the post-experiment survey of Cooperative Ball Maze{}, we asked the participants ``which mode of the robot is easier to cooperate with?''. Out of the 21 participants, 4 participants preferred to follow the robot and 17 participants preferred to lead the robot. Moreover, as we evaluated the student performance with partners of different sub-skills, we found that the student performances were consistent with their declared preferences (Figure~\ref{fig:ballmaze_result}(a)).  That is to say, the student may have a bias over which strategy to acquire, and tailoring the teaching curriculum to focus on that specific strategy is efficient and more intuitive to the student.
\begin{wraptable}{r}{0.4\columnwidth}
    \centering
    \begin{tabular}{cc}
        \cincludegraphics[scale=0.2]{figs/ballmaze-participant4.pdf}& 
        \cincludegraphics[scale=0.2]{figs/ballmaze-participant6.pdf}
        \\
        (a) & (b)
    \end{tabular}
    \captionof{figure}{
    Sub-skill performances (vertical axis) with respect to training progress (horizontal axis) of two example participants trained by the student-aware teacher. 
    Dots represent the raw scores and lines represent the smoothed scores.
    The top and bottom figures correspond to leading and following sub-skills respectively.
    (a) Participant 4. The student improved more when trained in the leading sub-skill.
    (b) Participant 6. The student improved more when trained in the following sub-skill.}
    \label{fig:ballmaze_example_participants}
    \vspace{-40pt}
\end{wraptable}
As demonstrated in Figure~\ref{fig:ballmaze_example_participants}(a), after the first 6 trials that estimated the student's proficiency for each sub-skill, the teacher found out this student improved more as the leader,
therefore, the teacher allocated 10 trials to perfect the \emph{leading} sub-skills and only 4 trials for \emph{following}.
Moreover, one participant in the random teacher group responded ``the robot leading mode is too difficult and I gave up''. This demonstrates the importance of an individualized curriculum: though there are multiple equally optimal strategies, the individual may have strong preferences, and teaching a non-preferable strategy will discourage the student from learning anything at all. 
We refer the readers to the Appendix for the complete data of all participants. 






\section{Introduction}  

How do we teach humans to re-orientate a table jointly or play tennis? Humans
often learn by practicing the skills with teachers or
partners~\cite{Gillies2016CooperativeLR, Ross1995DifferentiatingCL,
  Omidshafiei2019}.  This mode of learning is, however, difficult to scale up,
as it requires one-to-one interaction and there are not sufficient human
teachers~\cite{garcia2019teacher}.  With advances in machine learning, 
robots can not only master complex tasks~\cite{alphago, helicopter,ikea} but
also collaborate with humans and adapt to human behaviors~\cite{crosstraining,
  trust, cirl}.  In this work, we aim to create \emph{robot teachers} for
physical tasks, thus scaling up teaching and providing learning opportunities
to many even when human teachers are not available.

Specifically, we propose \emph{Cooperative rObot teACHing} (COACH),
a robot teaching framework to teach humans cooperative skills for two-player
physical tasks through interaction. We assume the robot teacher has full knowledge of the task, specifically,  a set of policies to execute the task. The objective is to teach the student a policy as fast as possible. See Fig.~\ref{fig:overview} for an illustration.
COACH treats the teaching task as a two-player Markov game for a \textit{target task}. One player is the
robot teacher, and the other is the human student. Under a suitable student
learning model,  COACH transforms the game into a \emph{partially observable Markov
decision process}  (POMDP).  The POMDP solution enables the robot teacher to adapt to
the different behaviors, according to the history of interactions. 


One key challenge of COACH is to represent the student's knowledge of the target skills and 
learning behaviors. First, we leverage \textit{item response theory} (IRT), a well-established framework for
educational assessment~\cite{irt}. IRT provides simplified parametric models that
capture the student's knowledge level with respect to the task difficulty in a small number of parameters.
COACH treats these parameters as latent variables in the teaching POMDP and learns them from human-robot interaction data by solving the POMDP. 
 Next, to teach complex skills, we 
 draw insights from student-centered
learning~\cite{jones2007student} and human-robot
cross-training~\cite{Nikolaidis2013}.
We decompose a complex target skill into a  set of sub-skills, based on the student's potential roles in the target task.
With this compact, decomposed skill representation, we  naturally obtain a \textit{partially assistive} robot teaching curriculum to facilitate learning: the human student learns the sub-skills one at a time, and the robot teacher assists with the sub-skills not yet learned, to complete the target task. 
While the robot  assists the human in the teaching task, its behavior differs from those in  common collaborative human-robot interaction tasks~\cite{Dragan2013,ReddyDL18}.
There, the primary objective is to complete the task, and  the robot is fully assistive: if the human does not perform, the robot then tries to complete the task on its own, if possible. In the teaching task, the robot is partially assistive and usually avoids assisting with the specific sub-skill to be learned, in order to encourage student exploration and learning. 













As a first attempt, 
we conducted human-subject experiments on two challenging human-robot collaboration tasks, Overcooked-AI{} and Cooperative Ball Maze{} ( Fig.~\ref{fig:exp_setup}). 
Our results show that COACH enables the robot teacher to model and reason over adaptive human students in cooperative teaching. Also,  a fully-assistive teacher may impede student learning, and a partially assistive teacher indeed motivates the student to explore new strategies.










\section{Limitation}
  
\noindent\textbf{Decomposition into sub-skills.} 
For many tasks, it is not easy to identify distinct roles to fulfill the local-independence criteria of sub-skills. We manually decompose the skill into a few sub-skills according to the role of the student. Often, such a decomposition may not be possible or requires careful design. We can mitigate this problem with recent progress on skill decomposition in single-agent task~\cite{srivastava2022assistive} and role-based task decomposition in multi-agent tasks~\cite{wang2021rode}. However, it still demands much more effort to verify their efficacy with a real human on real-world tasks.

\noindent\textbf{Teacher's Knowledge.} In the definition of the teaching task, we assume the teacher has full knowledge of the policies to be taught. However, it can be hard for the robot to know the oracle human policy beforehand. To make the conceptual framework practical, we need to relax the requirement on the teacher's prior knowledge. In our implementation, we reduce such an assumption by approximating the distance through the difference in performances. There can be cases where the target performance is hard to know or such relaxation results in severe information loss. We need more insights on tasks to make the framework practical. 

\noindent\textbf{Curriculum design.} 
In this work, we only design the curriculum over different sub-skills. However, during our experiment, we observe that humans show various responses to the same sub-skill of different difficulties. 
One specific finding is that people may give up learning when the task becomes too difficult. 
As a result, a finer-grained curriculum on the sub-skill training shall be generated to further facilitate human learning. 


\section{Related Work}

\begin{figure}
    \centering
    \includegraphics[width=.95\columnwidth]{figs/COACH.pdf}
    \caption{Cooperative robot teaching. In the  target task (left), two human players jointly reorient a table, for example. In the corresponding teaching task (right), the robot teacher interacts with the human student and teaches cooperative skills so that the student learns to cooperate with partners with varying capabilities or preferences in the target task.
    }
    \label{fig:overview}
\end{figure}
\noindent\textbf{Assistance in HRI.} One major aspect of HRI is how the robot could assist humans with a hidden human objective~\cite{Dragan2013,ReddyDL18}. 
The objective of the robot is to infer the human's intention and learns to assist the human. In its simplest form, the action selection and human intention inference are separated~\cite{Leike2008,jeon2020,chris2017}. A decision-theoretic framework, assistant POMDP, is developed to capture the general notion of assistance in HRI~\cite{Fern2014}. The robot integrates the reward learning and control modules to perform sophisticated reasoning over human feedback~\cite{shah2021benefits,sidekick_2021}. However, these two approaches neglect human learning/adaptation and may hinder humans from improving their skills. Our work focuses on how to generate behaviors that facilitate human learning during interactions. 

\noindent\textbf{Collaboration in HRI.} Another important aspect of HRI is to model interactions as the collaboration between the human and the robot~\cite{collaborativeplan}, for which the human and the robot share the same objective.
However, the joint optimal policy, e.g. rotating the table counter-clockwise, is unknown to both agents in the first place. Their interaction is mutually adaptative~\cite{Nikolaidis2016, Nikolaidis2017, Nikolaidis2017hri}. Particularly, as pointed out in~\cite{cirl}, if one side is only aware of partial information about the task, the optimal policy pair naturally induces the behavior of active teaching, active learning, and efficient communication between the robot and human. In this work, we focus on the following setting: given that the robot teacher knows the policy to teach, and how to carry out active teaching.


\noindent\textbf{Teaching Algorithm for Algorithms.} Teaching for algorithms aims to facilitate the learning of the algorithm by choosing or generating training samples. Various teaching techniques including curriculum learning~\cite{cirriculumlearning} and machine teaching~\cite{mt,mt1,mt2,mt3,imt} have been effectively applied to supervised learning and semi-supervised learning problems. Similar ideas are further extended to train reinforcement learning agents to learn complex skills, e.g.{}, generate training environment for reinforcement learning~\cite{Gur2022,Portelas2019,Fontaine*2021}, choose various demonstrations~\cite{Brown2019} or learn to decompose the skill~\cite{brian2004, GonzlezBrenes2013WhatAW}. Teaching in cooperative multi-agent RL allows agents to simultaneously become teachers and students for each other~\cite{Omidshafiei2019, Kim2020, Jaques2019}. However, such approaches generally require relatively more data for training and to some extent the controlled learning behavior of the learner. Transfer of these approaches to human learning is promising but difficult.

\noindent\textbf{Teaching Algorithm for Human.} Despite the aforementioned
practical challenges, some algorithms have been successfully deployed for
human learning. Attempts on teaching the crowd on classification or concepts
prove to be
successful~\cite{pomdpteaching,Singla2014,Zilles2011,Doliwa2010, Aodha_2018_CVPR}. While humans
can learn concepts from visual or verbal examples, complex skills like motor
control skills can hardly be mastered through these signals. Recently, skill discovery techniques in reinforcement learning have been introduced to generate a curriculum based on skill decomposition and facilitate humans to learn motor control skills~\cite{srivastava2022assistive}. It focuses on how to adaptively decompose the skill into learnable sub-skills for a human to practice on its own and achieves promising results. Here, we seek to automate the teaching process for humans to cooperate in a physical task and provide a framework for this teaching mode, e.g.{}, table co-reorientation.



\section{Method}
\begin{wrapfigure}{r}{0.5\textwidth}
\vspace{-25pt}
\hspace{-10pt}
\begin{minipage}{0.5\textwidth}
\begin{algorithm}[H]
\caption{\small Approximated Solution to the Teaching Task}\label{alg:cap}
{\fontsize{9}{9}\selectfont
\begin{algorithmic}[1]
\Require Maximum Interactions $L$, Predefined Interactions $N$
\For {$k \in \ensuremath{\bar{A}}$}:
\State Randomly initialize $\lambda$ and $\alpha_t$, $\beta$, and $\mathbb{X} = \{\}$
\For {\texttt{$i= 1,2,...,N$}}:
\State $\mathbb{X}.\texttt{add}(v_i)$
\EndFor
\EndFor
\For {\texttt{$i= 1,2,...,L$}}:
\For {$k \in \ensuremath{\bar{A}}$}:
\State Learn $\lambda$ and $\alpha_t$, $\beta$ from $\mathbb{X}$
\EndFor
\State $k \gets$  Action selection from $\lambda$ and $\alpha_t$, $\beta$ 
\State $v_i \gets $ Performance measure from interactions
\State $\mathbb{X}.\texttt{add}(v_i)$
\EndFor
\end{algorithmic}}
\end{algorithm}
\vspace{-20pt}
\end{minipage}
\end{wrapfigure}
In this section, we provide a solution that grounds all the elements in the conceptual framework of COACH. The main spirit of our solution is to parameterize students' knowledge state with IRT and decompose complex tasks into a set of role-based independent skills.
The action space in definition~\ref{defn2} allows the teacher to take all possible actions in the 2-player task. Thus, the teacher is able to switch roles freely. For example, the teacher may serve as either follower or leader in the classic leader-follower model~\cite{kheddar2009,kheddar2011}. 
This enables easier evaluation of the  students' proficiencies and provides a ground to derive the partially assistive interaction mode.
Our solution is summarized in Algorithm~\ref{alg:cap}.
To begin with, we first define the action space, $\ensuremath{\bar{A}}$.





\subsection{Action}\label{sec:action_space}

The action space is constructed through sub-skill decomposition. 
Sub-skills decomposition is well-studied for single-agent tasks~\cite{Graves2012label,shiarlis2018,kipf2019compositional}. However, extending the same idea to a multi-agent setting is still challenging since task completion relies on the interaction among multiple parties.
We observe that in a multi-agent game, the task naturally comprises several roles, of which each agent takes a subset.
The well-established leader-follower model is a particular choice of role-based skill decomposition~\cite{kheddar2009,kheddar2011, natha2012framework,roleofrole}. 
Therefore in our work, we propose to decompose skills based on role allocation.
We divide the skill into $K$ independent teachable sub-skills according to the student's potential roles in the task. 
The teacher's action space $\ensuremath{\bar{A}} = \{ k: k\in \mathbb{Z},~ 0 \leq k < K \}$ consists of teaching each sub-skill. Such a decomposition of skills naturally leads to a partially assistive mode of interaction. 
\subsection{State} \label{state_space}
The state space is constructed with Item Response Theory (IRT)~\cite{irt}. IRT provides a parametric form to represent students' skill levels. Given the limited interactions, we adopted the simplest form, the one-parameter logistic model (1PL), to model human skills. In the 1PL model, each sub-skill $k \in \ensuremath{\bar{A}}$ is assigned a parameter $\beta^k$ representing the difficulty, and a parameter $\alpha^k$ called the \emph{proficiency} representing a student’s knowledge state. 
The probability that a student has mastered sub-skill $k$ is given by $P(k) := \sigma(\alpha^k - \beta^k)$, where $\sigma$ is the sigmoid function. Hence, instead of representing the state with the student's policy $\ensuremath{\phi}{}$, we use $(\alpha,\beta)^K$ to represent the hidden state. That is, for $\ensuremath{\bar{s}} \in \ensuremath{\bar{S}}, \ensuremath{\bar{s}} = (\ensuremath{s}, (\alpha, \beta)^K)$, where $(\alpha ,\beta)^K$ is hidden. For each student and each $k\in \ensuremath{\bar{A}}$, we assume that $\alpha$ changes over time while $\beta$ does not. 
\subsection{Transition}

The transition model consists of two main parts, the target task transition model $\ensuremath{T}$, and the student's update function $\ensuremath{U}$. While the former one is known to the teacher, we need to make assumptions about the latter one. Since we define the state space over the student's proficiency $\alpha$ in Sec~\ref{state_space}, the transition model is also constructed over the proficiency.
Following the previous work on online estimation of student proficiency ~\cite{Ekanadham2017TSKIRTOE, Wilson2016BackTT}, for each sub-skill, we model the student's proficiencies over time as a Wiener process:
$
\small
    \ensuremath{U}(\alpha_{t+\ensuremath{\Delta t}} | \alpha_t) = \exp\left(
        -\frac{(\alpha_{t+\ensuremath{\Delta t}} - \alpha_t)^2}{2\lambda \ensuremath{\Delta t}}
    \right),
    \label{eq:subskill_prof_update}
$
where $\ensuremath{\Delta t}{}$ refers to the step interval and $\lambda$ is a parameter controlling the “smoothness” with which student's proficiency varies over time. For each student and for each $k\in \ensuremath{\bar{A}}$, we assume $\lambda$ does not change over time and is learned for each sub-skill respectively. To this end, we construct the transition model in the POMDP as $\ensuremath{\bar{T}} = \{\ensuremath{T}, U\}$, where $\ensuremath{T}$ is the transition function in the target task. 

\subsection{Observation}

The observation is composed of the target task state and the reward received, $(s, r)$. Recall that in Sec~\ref{sec:action_space}, we define the action as choosing one sub-skill to train the student, which is a macro-action. 
For teaching sub-skill $k$, we
redefine the observation as the ratio between the target task{} rewards achieved by the student's current and the policy to be taught:
$\small
    v
    := \frac{
        R(\ensuremath{s}, \ensuremath{\bar{a}}, \ensuremath{a^{\sss \studentsuper}})
    }{ 
        R(\ensuremath{s}, \ensuremath{\bar{a}}, a^*)
    },
    \label{eq:subskill_prof}
$
where $a^*$ is the action generated by the policy 
 to be taught $\ensuremath{\phi^*}$ and $a^\mathrm{S}$ is the action from student's policy given the same the target task{} state $s$. Since all the sub-skills are treated equally, we will omit the index $k$ for simplicity in the following discussion. 
As a result, for $\ensuremath{\bar{o}} \in \ensuremath{\bar{O}}$, $\ensuremath{\bar{o}} = (s, v)$. Unlike the binary response in conventional knowledge tracing, the response $v$ we have is continuous and we assume the teacher will only teach one sub-skill at a time. Thus, we use the continuous Bernoulli distribution to construct the observation model:
$\small
    Z(v | P(k)) = P(k)^{v}(1-P(k))^{1-v},
$
where $k$ is the sub-skill being taught when $v$ is observed. 
As a result, the observation model can be defined as $\ensuremath{\bar{{Z}}} = \{I, Z\}$, where $I$ is an identity mapping for the observable target task state, $I(s) = s$.

\subsection{Reward}
The distance between the student's policy and the policy to be taught can be represented using $P(k)$. We represent the distance as the average of one minus master probabilities of each sub-skill:
$\small \ensuremath{D} (\ensuremath{\phi}, \ensuremath{\phi^*}) = \frac{\sum_{k=0}^{K}1- P(k)}{K}$.
 There are other ways to specify the goal according to the decomposition of the skill, e.g.{} weakest or multiply~\cite{pittir26017}. We choose the sum due to our independence assumption on sub-skills. In this work, we assume the cost is uniform, thus, given a finite horizon of interactions, maximizing the reward function defined in Equation~(\ref{pomdpreward}) is equivalent to maximizing $\small \ensuremath{\bar{R}}(\ensuremath{\bar{s}}, \ensuremath{\bar{a}}_t, \ensuremath{\bar{s}}') = \frac{\sum_{k=0}^{K} P_{t+1}(k) - P_t(k)}{K}$, where $P_{t}(k) = \sigma(\alpha^k_t - \beta^k)$.
\subsection{Model Learning and Decision Making}
We use the student's performance during the interactions to estimate both $\lambda$ and $\alpha_t, \beta$. Parameters for each sub-skill are learned separately, thus, we omit $k$ for simplicity. Let $v_{1:t}$ denote sequences of student's performance measure against the policy to be taught up to step $t$. We have the posterior $P(\lambda, \alpha_t, \beta |v_{1:t}) \propto P(v_{1:t}|\lambda, \alpha_t, \beta) P(\lambda, \alpha_t, \beta)$.
The conditional probability of the observation and current proficiency can be obtained by integrating out all the previous proficiencies. The likelihood can be approximated through
     $P(v_{1:t}|\lambda, \alpha_t, \beta) \approx 
     \prod_{t'=1}^t \int P(v_{t'}| ~\lambda, \alpha_{t'}, \beta)\ensuremath{U}(\alpha_{t'}|\alpha_t) \mathrm{d}\alpha_{t'}.$
An approximation of the log posterior over the student’s current proficiency given previous responses can be derived to learn the parameters $\lambda$ and $\alpha_t$, $\beta$. 
Following~\cite{Ekanadham2017TSKIRTOE, Wilson2016BackTT}, we employ maximum a posteriori estimation (MAP) to learn these parameters.
Given the estimation of the current state using the past history, we use a one-step look-ahead. Such a choice allows us to reduce the impact of the learned inaccurate model and generate a more efficient solution compared with the full-blown POMDP solution.
At timestep $t$, the teacher's action is given as
\begin{equation}
    \ensuremath{\bar{a}}_{t+1} = \mathop{\mathrm{arg\,max}}_{k\in\ensuremath{\bar{A}}} \int \ensuremath{U}(\alpha^k_{t+1} | \alpha^k_t) 
    P_{t+1}(k)~\mathrm{d}\alpha^k_{t+1} - P_{t}(k).
\end{equation}
In practice, the student is asked to perform on each sub-skill for a few interactions to initialize the parameters. 
\subsection{Training on Sub-skills}

Our overall strategy for training students on each sub-skill is to diversify scenarios the student would encounter during training. Training students on sub-skills naturally leads to a partially assistive partner on unlearned sub-skills, which allows the student to explore the sub-skill freely. 
We adopt an intuitive assumption: \emph{an agent learns cooperation better with a diverse group of partners}. Such a teaching strategy is effective when dealing with synthetic students~\cite{lupu21a, Zhao2021}. The student could learn from a diverse set of partially assistive partners or learn to cope with them by acquiring new skills.


\section{Conclusion}
\vspace{-2mm}
In this work, we propose a conceptual framework, Cooperative Robot Teaching,
that enables robots to teach humans in cooperative tasks. We show that, by
abstracting a teaching task over the original duo cooperative task, the robot
can learn to act as a specialized teacher to humans. To be more specific, we
model the teaching task as a POMDP with hidden student policy and propose a
partially assistive teaching curriculum to support human learning. We believe
that robot teaching fills in the gap in the bilateral knowledge transfer in
HRI: unlike other HRI tasks where the humans instruct the robots how to
behave, the role is reversed and robots try to instill the knowledge back
into humans. Despite the challenges that lie ahead, we believe that
robot teaching has great potential and is a necessary step forward to bring
robots closer to our daily life.

\textbf{Acknowledgments.}
This research is supported in part by the National Research Foundation, Singapore under its Medium Sized Centre Program, Center for Advanced Robotics Technology Innovation (CARTIN), and  AI Singapore Programme (AISG Award No: AISG2-PhD-2022-01-036[T] and AISG2-PhD-2021-08-014), and by the Science and Engineering Research Council, Agency of Science, Technology and Research, Singapore, under the National Robotics Program (Grant No. 192 25 00054).

\section{Cooperative Robot Teaching}\label{sec:form}

We  identify four key elements in COACH: (1) target task, (2)  student, (3)  teacher, and (4) interactive teaching-learning. 

\noindent\textbf{Target task.} 
In this work, we focus on teaching in \textit{a two-player cooperative task}, which we call it the \textit{target task}.

\begin{defn}\label{defn1}. The \textit{target task} is a two-player cooperative Markov game $\mathcal{M}=( \ensuremath{S}, \ensuremath{A^\agenta}, \ensuremath{A^\agentb}, \ensuremath{T}, \ensuremath{R}, \gamma )$ between two agents, \ensuremath{1}{} and \ensuremath{2}{}, where 
\begin{tightlist}
 \item \ensuremath{S}\  is a set of target task states;
 \item \ensuremath{A^\agenta}\ is a set of actions for  agent \ensuremath{1};
 \item \ensuremath{A^\agentb}\ is a set of actions for  agent \ensuremath{2};
 \item $\ensuremath{T}(\ensuremath{s}' | \ensuremath{s}, \ensuremath{a^\agenta}, \ensuremath{a^\agentb})$ is a conditional probability  function on the next target task state $\ensuremath{s}'\in \ensuremath{S}$, given the current state $\ensuremath{s}\in \ensuremath{S}$ and   both agents' actions $\ensuremath{a^\agenta}\in\ensuremath{A^\agenta}$ and $\ensuremath{a^\agentb}\in \ensuremath{A^\agentb}$;
 \item \ensuremath{R}(\ensuremath{s}, \ensuremath{a^\agenta},\ensuremath{a^\agentb}) is a target task reward function that maps the target task state and players' actions to a real number;
 \item $\gamma$ is a discount factor. 
\end{tightlist}
\end{defn}
At each step $t$, agent \ensuremath{1}{} and \ensuremath{2}{} both observe the current task state $\ensuremath{s}_t$ and  select their respective actions $\ensuremath{a^\agenta}_t \sim \ensuremath{\pi^\agenta{}}{}$ and $\ensuremath{a^\agentb}_t \sim \ensuremath{\pi^\agentb{}}{}$, where $\pi^i$ the policy of agent $i \text{ for } i=1,2$. They then receive a joint reward $r_t=R(\ensuremath{s}_t,\ensuremath{a^\agenta}_t, \ensuremath{a^\agentb}_t)$. The next state is updated as $\ensuremath{s}_{t+1} \sim \ensuremath{T} (\ensuremath{s}_{t+1}~|~\ensuremath{s}_t,\ensuremath{a^\agenta}_t,\ensuremath{a^\agentb}_t)$.

Given the definition of the target task, we first answer how to represent the knowledge/skills. In this work, we choose to represent a \textit{skill} by a policy \ensuremath{\phi^*}{} to the target task. 
For example, in the table co-reorientation task, the agent needs to learn to deal with either stubborn or adaptive partners. We recognize that there are other ways to represent knowledge/skills, such as a set of demonstrations and the ground-truth reward function. However, such representations are indirectly linked with the skill's performance; therefore, evaluating its proficiency is more obscured. We choose a known policy to be taught as the representation since it can be directly optimized over and evaluated.

\noindent\textbf{Student.} The student policy is non-stationary since it will improve along with teaching. 
We model this evolutionary behavior with a tuple of student policy \ensuremath{\phi}{} and an
updating function \ensuremath{U}{}, $( \ensuremath{\phi}{}, \ensuremath{U}{} )$. The student policy represents the student knowledge state. It will take in the current target task state $s$ as input and output the student's action. The updating function $\ensuremath{U}{}$ models how the student changes its policy after each teaching step. 

 
\noindent\textbf{Teacher.} We define the teacher as a knowledgeable agent (expert) who 
knows a set of policies $\Phi^* $
for a target task. The teacher aims to acquire a teaching policy \ensuremath{\bar{\pi}}{}  that can teach any $\ensuremath{\phi^*}_i \in \Phi^*$ to the student effectively. In this general setting, the choice of the student policy to teach $\ensuremath{\phi^*}$ depends on the capability, preference, and current knowledge level of the student. 
A principled approach to selecting the policy to teach needs to consider the student's preference, his/her update model for the knowledge level, and an estimate of his/her current capability. In this paper, we assume that we have an oracle to choose the policy to teach $\ensuremath{\phi^*}{} \in \Phi^*$, such that this policy $\ensuremath{\phi^*}{}$ matches the preference of the student.
The teacher can be described by a tuple of a target task policy and the corresponding teaching policy, $(\ensuremath{\phi^*}{}, \ensuremath{\bar{\pi}}{})$.

\noindent\textbf{Interactive teaching-learning}.
In the target task, the teacher knows the target task policy $\ensuremath{\phi^*}{}$ while the student does not. The teacher's goal is to act in the most informative way so that the student learns $\ensuremath{\phi^*}{}$ fastest. The choice of $\ensuremath{\phi^*}{}$ should account for the student's preferences. To embed the objective of teaching and distinguish it from the \emph{Target Task}, we define it as the \emph{Teaching Task} in the following way:
\begin{defn}\label{defn2}. 
Given a target task $\mathcal{M}=( \ensuremath{S}, \ensuremath{A^\agenta}, \ensuremath{A^\agentb}, \ensuremath{T}, \ensuremath{R}, \gamma )$, a  student $( \ensuremath{\phi}{} , \ensuremath{U}{} )$, and a policy to teach $\ensuremath{\phi^*}{}$ for the target task, 
the teaching task is a POMDP   $\bar{\mathcal{M}} = ( \ensuremath{\bar{S}}, \ensuremath{\bar{A}}, \ensuremath{\bar{T}}, \ensuremath{\bar{O}}, \ensuremath{\bar{{Z}}}, \ensuremath{\bar{R}}, \ensuremath{\bar{\gamma}} )$ for the teacher, where
\begin{tightlist}
 \item \ensuremath{\bar{S}}\ is a set of teaching  states:  \ensuremath{\bar{s}}{} ~= $(s, \ensuremath{\phi})$, for target task state $s\in\ensuremath{S}\ $ and student policy $\ensuremath{\phi}$; 
 \item \ensuremath{\bar{A}}\ is a set of actions: $\ensuremath{\bar{A}} = \ensuremath{A^\agenta} \cup \ensuremath{A^\agentb}$;
 \item $\ensuremath{\bar{T}}(~\ensuremath{\bar{s}}' |~\ensuremath{\bar{s}}, \ensuremath{\bar{a}})$ is a conditional probability  function on the next state $\ensuremath{\bar{s}}' \in \ensuremath{\bar{S}}$, given the current state $\ensuremath{\bar{s}}\in\ensuremath{\bar{S}}$ and teacher's action $\ensuremath{\bar{a}}\in\ensuremath{\bar{A}}$;
 \item \ensuremath{\bar{O}}\ is a set of observations:  $\ensuremath{\bar{o}}{} = ( s, r )$, for target task state $s\in\ensuremath{S}$ and target task reward $r$;
 \item $\ensuremath{\bar{{Z}}}{}(~\ensuremath{\bar{o}}{}~ |~\ensuremath{\bar{a}}{}, \ensuremath{\bar{s}}{})$ is a conditional probability function on the observation  $\ensuremath{\bar{o}}{}\in\ensuremath{\bar{O}}\ $, given teacher's action $\ensuremath{\bar{a}}\in\ensuremath{\bar{A}}$ and current state $\ensuremath{\bar{s}}\in\ensuremath{\bar{S}}$;
 \item $\ensuremath{\bar{R}}(\ensuremath{\bar{s}}{}, \ensuremath{\bar{a}}{} , \ensuremath{\bar{s}}{}')$ is a teaching  reward function that maps  current state $\ensuremath{\bar{s}}{}\in \ensuremath{\bar{S}}{}$, teacher's action $\ensuremath{\bar{a}}\in\ensuremath{\bar{A}}$, and next state $\ensuremath{\bar{s}}'\in \ensuremath{\bar{S}}{}$ to a real number measuring the effectiveness of teaching; 
 \item \ensuremath{\bar{\gamma}}\ is a discount factor.
\end{tightlist}
\end{defn}

The objective of the teaching task is to derive a teaching policy \ensuremath{\bar{\pi}}{}, enabling students to learn $\ensuremath{\phi^*}{}$ for the target task fastest.
More specifically, the teacher can influence the student through interactive actions $\ensuremath{\bar{a}} \in \ensuremath{\bar{A}}$. 

First, we define the learning behavior of the student. We consider humans would take the interaction history into account. The history of observation is $h_t = [(\ensuremath{s}_0,r_0),...,(\ensuremath{s}_t,r_t)]$. Thus, the student updates \ensuremath{\phi}{} with any arbitrary iterative functions conditioned on the history of interactions:
$\ensuremath{\phi}_{t+1}=\ensuremath{U}(\ensuremath{\phi}_t,h_t)$.

Next, we give the definition of the reward function. To incentivize the teacher to speed up the teaching process, we introduce a step-wise teaching cost to the teacher $c_t= \ensuremath{C}(s_t, \ensuremath{\bar{a}}_t)$ to penalize unnecessary teaching actions. To this end, we define the reward function as
\begin{equation}
\small
\ensuremath{\bar{R}}(\ensuremath{\bar{s}}, \ensuremath{\bar{a}}_t, \ensuremath{\bar{s}}'; \ensuremath{D},\ensuremath{C},  \ensuremath{\phi^*}{}, \omega) = \ensuremath{D}(\ensuremath{\phi}_t, \ensuremath{\phi^*}{}) - \ensuremath{D}(\ensuremath{\phi}_{t+1}, \ensuremath{\phi^*}{}) - \omega \ensuremath{C}(s_t, \ensuremath{\bar{a}}_t),
\label{pomdpreward}
\end{equation}where  $\ensuremath{\bar{s}} = (\ensuremath{s}_t, \ensuremath{\phi}_t),~ \ensuremath{\bar{s}}' = (\ensuremath{s}_{t+1}, \ensuremath{\phi}_{t+1})$, $\omega$ is the weighting factor to trade-off the teaching cost and teaching efficiency, and {$\ensuremath{D}$ can be any reasonable distance measure between two policies, e.g.{}, initial state value in the target task.}

Lastly, we introduce our choice of the teaching policy $\ensuremath{\bar{\pi}}{}$. To devise a student-aware teaching strategy, apart from the current state $\ensuremath{s}_t$ and the target policy \ensuremath{\phi^*}{}, our $\ensuremath{\bar{\pi}}$ also takes the history of observation as input. The action of the teacher can be sampled from the policy,
i.e., $\ensuremath{\bar{a}}_t \sim \ensuremath{\bar{\pi}}(\ensuremath{\bar{a}}_t ~| ~ h_{t-1},s_t, \ensuremath{\phi^*}{})$.  The solution to the POMDP $\mathcal{M'}$ is a teaching policy $\ensuremath{\bar{\pi}}{}$ that maximizes the expected sum of rewards  $\mathop{\mathbb{E}}_{\ensuremath{\bar{a}}_t \sim \ensuremath{\bar{\pi}}}[\sum_{t=0}^{\infty}\ensuremath{\bar{\gamma}}^t \ensuremath{\bar{R}}(\ensuremath{\bar{s}}, \ensuremath{\bar{a}}_t, \ensuremath{\bar{s}}')]$. 








