Repeated Inverse Reinforcement Learning
We introduce a novel repeated Inverse Reinforcement Learning problem: the agent has to act on behalf of a human in a sequence of tasks and wishes to minimize the number of tasks that it surprises the human by acting suboptimally with respect to how the human would have acted. Each time the human is surprised, the agent is provided a demonstration of the desired behavior by the human. We formalize this problem, including how the sequence of tasks is chosen, in a few different ways and provide some foundational results.
## Summary
This is a theoretical work in which the authors present a new problem domain called repeated inverse reinforcement learning (RIRL). This domain describes interactions between a human (expert) and the RIRL agent, whereby the agent repeatedly presents solutions to tasks (in the form of a discounted state occupancy) and the human responds with a demonstration if surprised by the (suboptimality) of the agent's choice. At each iteration the agent also  potentially makes some choice about the domain, which can include the state transition structure, and/or the task specific part of the reward function. The goal is to determine the task independent reward function, which in real terms might refer to such things as norms, preferences and safety considerations. Towards the end of the paper, the authors relax the requirement for a full state occupancy to be presented, instead allowing trajectories to be presented. The solution is presented either as an optimal policy for any desired task, or by identifying the task independent reward function up to an equivalence class.
The main contributions of the paper are two algorithms and a series of convergence bounds proven for each setting. The algorithms making use of a 'volume reduction in ellipsoid' algorithm from the optimization literature, which reduces the space of possible reward functions to a minimal-volume enclosing ellipsoid. The paper is quite dense in theoretical results and pushes a number of proofs to appendices. Also, because of space considerations there are some very compact descriptions with high level intuition only. However, these results appear to be sound (to the best of my ability to judge) and to have general applicability in the newly defined problem domain. The authors could do a little more to provide both a concrete example to motivate the domain and some intuition to guide the reader (please see my comments below). Also, the tractability of this approach for 'interesting' domains is difficult to judge at this early theoretical stage.
## More detailed comments
# p2
# Authors use \Delta to represent a probability distribution over various sets, but don't define this notation anywhere, or scope its meaning (some authors forbid continuous sets, other authors forbid discrete distributions with zero components when using this notation).
# Or the identity function used for the state occupancy vector.
# p4, line 158
  Each task is denoted as a pair (X, R). 
# The authors do not describe the meaning of R in the general bandit description. From later text it becomes apparent, but it should be stated here explicitly.
# p5, lines 171-177
# Is this really a generalisation? It seems more like a constraint to me. It certainly implies a constraint on the relationship between rewards for two different states which share features. Extension/modification might be a better word than generalisation. 
# It is also implied, but not stated that the policy now maps from features to actions, rather than from states to actions. 
# p5 line 183, language
    ...for normalization purpose,
# for normalization purposes,
# p5, line 186, meaning
  ...also contains the formal protocol of the process.
# It is unclear what the authors mean by this.
# p5 line 197, clarity
    Therefore, the update rule on Line 7...
# on Line 7 of Algorithm 1
# p5 line 205, clarity
    ...in the worst case...
# I think 'at it's smallest' (or similar) would be clearer. As this 'worst case' would represent the most accurate approximation to theta* possible after . A good thing.
# p5 line 206, clarity
  To simplify calculation, we relax this l∞ ball to its inscribed l2 ball.
# This took me a little while to interpret. It would be clearer if the authors talked about the lower bound represented by the l∞ ball being relaxed, rather than the ball being relaxed.
# p6 line 208 and Equation below
# When the authors say 'The unit sphere', I guess they are now talking about the l2 norm ball. This should be explicit. As should the vol function representing the volume of an ellipsoid. Also some intuition could be given as to why the third part of the inequality is as it is. If I am right then C_d sqrt(d)^d is the volume of an l2 ball that contains \Theta0 and C_d (ε/4)^d is the volume of the aforementioned lower bound l2 ball.
# p7 meaning
    We argue that this is not a reasonable protocol for two reasons: (1) in
expectation, the reward collected by the human may be less than that by the agent, which is due to us conditioning on the event that an error is spotted
# Is there a way of making this statement clearer.
# p7 clarity
  demonstration were still given in state occupancy
# Is the meaning 'demonstration were still given in terms of a state occupancy vector'
# and '(hence μ t )' could be expanded to '(we call the resulting state occupancy μ t ). 
# p8 discussion for Algorithm 2, intuition.
# The authors could give some intuition behind the construction of the batch state vectors \bar{Z} and \bar{Z}^* in the Algorithm. The former appears to be an unnormalised state occupancy following \pi_t = \pi_{t-n} whose initial state distribution is uniformly sampled from the states with mistakes in between iterations t-n and t. Likewise, the \bar{Z}* vector is an unnormalised sum of discounted state visits from the n demonstrations initiated by the mistakes.  Is this correct?