Summary
This work studies the question of reproducibility in reinforcement learning (RL). They define reproducibility as an algorithm returning the same policy on two different random draws from the environment, with probability at least $\rho$. In the generative model setting, they show that there exists an algorithm which is $\rho$-reproducible, returns an $\epsilon$-optimal policy with probability at least $1-\delta$, and collects at most $O(\frac{N^3 \log 1/\delta}{(1-\gamma)^5 \epsilon^2 \rho^2})$ samples, for $N$ the number of state-actions. They also show a lower bound that this is tight (up to a factor of $1/(1-\gamma)^2$). As the $N^3$ complexity could be prohibitively large in many cases, they show that by relaxing the definition of reproducibility somewhat, they are able to obtain a complexity that scales with $N$ instead.
Strengths
1. To my knowledge, the setting is novel: I do not think the question of reproducibility has been previously considered in the RL literature. Furthermore, the question of algorithmic reproducibility has in general seen attention recently in the broader machine learning literature, so there is general interest in the setting.
2. The results paint a fairly complete picture of the problem, with nearly matching upper and lower bounds. In addition, they show that the $N^3$ dependence can be reduced by considering a slightly relaxed formulation of the problem.
Weaknesses
1. The paper does not clearly motivated why we should care about reproducibility in RL. While reproducibility in science in general is an issue, in RL typically the goal is simply to find a policy that (approximately) maximizes the reward, and we don’t necessarily care whether two runs of the same algorithm produce identical policies or not, as long as they have similar performance. The paper does not give clear justification for why this problem is important, but I think this is necessary given the novelty of it.
2. Definition 2.6 should make clear that the algorithm is able to request which state-actions the $n(\epsilon,\delta)$ are from (if it is indeed able to). As it currently reads, it is ambiguous if the algorithm can request which state-actions they are from, or if it is simply given $n(\epsilon,\delta)$ samples from the generator—the latter option is clearly not possible since if all samples are from the same state-action it is not possible to learn a good policy.
3. Definition 2.9 is also somewhat unclear for a similar reason. My reading is that $\bar{S},\bar{S}’ \sim G$ means that samples from a particular set of state-actions are generated from $G$. Would this exclude the case when all the samples are coming from the state-action? Also, does it exclude an adaptive algorithm which chooses which state-actions to sample from based on the data it has already seen?
4. Using the notation $\bar{r}$ for the randomness of the algorithm is somewhat confusing as $r$ is already used for the reward.
5. I understand that space is limited, but if possible it would be helpful to give some more explanation for the algorithm, in particular the replicable rounding procedure, since this is non-standard in the RL literature. Some intuition on why the $N^3$ dependence arises would also be helpful.
Questions
The primary question I have is on motivating the problem setting, as I stated in the weaknesses section.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.