Summary
In this work, the authors make several contributions. Firstly, they propose a novel selective sampling algorithm (Algorithm 1) that utilizes a regression oracle and provide regret bounds and query complexity analysis. Secondly, they present a lower bound that demonstrates the unavoidable dependency of query complexity on the eluder dimension without additional assumptions. Thirdly, they introduce Algorithm 2, which is designed for to iid sample distributions and employs the disagreement coefficient as a substitute for the eluder dimension. For imitation learning, the authors prove an exponential gap in sample complexity between stochastic and deterministic expert demonstrations in the context of offline imitation learning. Lastly, they propose imitation learning algorithms that utilize regression oracles with selective sampling for both single and multiple stochastic expert settings.
Strengths
1.This work provides valuable insights into the field of neural network-based imitation learning with selective sampling, laying the foundations for future advancements in practical and efficient algorithms.
2.The authors' contributions encompass both selective sampling and imitation learning, showcasing the potential for designing imitation learning algorithms that offer provable efficiency. Their research opens up exciting possibilities for further advancements in the field.
Weaknesses
1.While this work presents self-contained proofs, it lacks a direct comparison of the imitation learning regret and query complexity of the proposed algorithm with Dagger and other existing algorithms. This omission makes it challenging to assess the efficiency and performance of the proposed approach accurately.
2.The experiment conducted on Cartpole may not provide sufficient insight and understanding of the algorithm's performance. Furthermore, the use of sophisticated selective sampling techniques may introduce significant computational overhead when applied to more complex experimental environments such as hopper and walker. This computational burden hinders the evaluation of the algorithm and makes it difficult to further explore its effectiveness in practical scenarios.
3.The usage of a deterministic Markov Decision Process (MDP) with a fixed starting state, which may not align with standard imitation learning problems. This restriction limits the applicability of the guarantees provided in this work to more general and diverse scenarios.
Questions
Questions:
1.Lemma 18 does not appear to me a variant of the performance difference lemma, where in the second inequality of the equation after line 1075 the value on the right is already $2H$, the upper bound of the performance difference. Please explain if this implies the other results that applies lemma 18 are already greater than $2H$.
2.In line 281, for AggreVate, I believe it takes $O(\log(H))$ rounds for the probability of executing expert policy to be lower than $1/H^2$, where by the union bound we have the probability of executing the learner's policy for whole $H$ steps greater than $(H-1)/H$. If mixing with the noisy expert is the only issue, I don't agree that AggreVaTe style algorithm should sample $\Omega(2^H)$ samples if I am allowed to mix the proposed algorithm 2 with noisy expert policy as AggreVaTe-style in the roll out.
3.I am confused why in line 266 we need a large margin over state space for Dagger instead of the recoverability assumption. By the performance difference lemma, we only need the expert's advantage function to be bounded by some value smaller than $H$ for Dagger to achieve better regret guarantee than behavior cloning. Please feel free to let me know if you need any reference.
4.I am curious why the number of queries for Dagger is not a straight line, which may due to sampling trajectories instead. Please provide more experimental details including model and training details for more transparent presentation.
5.Does the analysis in this work generalizable to non-deterministic learner policies?
6.Is proposition 1 extendable to stochastic transition dynamic setting? I am afraid the stochastic transition dynamics will make any roll out policy hard to reach the designed leaf node.
7.Is line 5 in algorithm 1 easy to compute when the policy class is exponentially large?
8.Querying all $M$ experts and assigning $H \times M$ learner policies is quite computationally demanding, any method to reduce to learning only one policy under some assumption of realizability?
Minor suggestions:
1.In line 1006 it would be better to define $r(x,a) = 0$ for none leaf nodes.
2.In line 1022 use $ \forall \pi \in \Pi$ to avoid confusion.
3.In line 257, could you please clarify the definition of your regret, which is missing the expectation over transition dynamics. I assume you are in the deterministic transition setting. The state that would have been generated is a bit vague, please point out the deterministic MDP setting with unique starting state directly.
4.In line 256 'the learner proposes an action' is a bit vague, I suppose you are suggesting a deterministic learner's policy in stead of a stochastic random policy like a noisy expert. Could you please make it more clear by mentioning 'deterministic'?
5.In line 491, though using the last round policy as warm start may result in similar performance as training from random initialization. It would be beneficial to conduct one extra experiment comparing the result of using warm start and naively start from random initialization for each round, which would empirically justify this speedup.
6.In the Figure 2, Dagger takes around 13 iterations to converge, where it would be helpful to mark the exact number of annotations for Dagger to achieve near expert performance as a dotted line on the right of figure 2.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
1.The lack of a direct theoretical comparison between the proposed algorithm's imitation learning regret and query complexity with Dagger and other preexisting algorithms hinders the interpretation of its efficiency. Comparative evaluations against existing algorithms would provide a clearer understanding of the algorithm's performance and effectiveness.
2.The experiment conducted solely on the Cartpole environment may not offer sufficient insights into the algorithm's behavior and capabilities. Additionally, the computational overhead associated with the sophisticated selective sampling technique might pose challenges when applying the algorithm to more complex environments like hopper and walker. This limitation makes it difficult to thoroughly evaluate the algorithm's performance in a broader range of scenarios.
3.The use of a deterministic Markov Decision Process (MDP) with a fixed starting state deviates from the standard settings in imitation learning problems. This restriction limits the guarantee and applicability of the proposed algorithm, as it may not generalize well to more diverse and realistic scenarios encountered in practice.
4.While Proposition 1 is supported by theoretical proof, it would be beneficial to include empirical observations to demonstrate its importance and practical relevance. Additionally, conducting experiments that involve behavior cloning would provide further insights and comparisons, enhancing the experimental evaluation and supporting the theoretical claims.