  We study interactive learning in a setting where the agent has to generate a
response (e.g., an action or trajectory) given a context and an instruction. In
contrast, to typical approaches that train the system using reward or expert
supervision on response, we study learning with hindsight instruction where a
teacher provides an instruction that is most suitable for the agent's generated
response. This hindsight labeling of instruction is often easier to provide
than providing expert supervision of the optimal response which may require
expert knowledge or can be impractical to elicit. We initiate the theoretical
analysis of interactive learning with hindsight labeling. We first provide a
lower bound showing that in general, the regret of any algorithm must scale
with the size of the agent's response space. We then study a specialized
setting where the underlying instruction-response distribution can be
decomposed as a low-rank matrix. We introduce an algorithm called LORIL for
this setting and show that its regret scales as $\sqrt{T}$ where $T$ is the
number of rounds and depends on the intrinsic rank but does not depend on the
size of the agent's response space. We provide experiments in two domains
showing that LORIL outperforms baselines even when the low-rank assumption is
violated.
