Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: I thank the authors for their responses. They main point of remaining concern seems to be the necessity of analysis/evaluation under model misspecification. I feel like this concern is quite significant, but would defer to better experts in the field.

=====

The paper presents robust versions of the Q-learning and TDC algorithms and analyzes their rate of convergence in tabular and linear-approximation representations.
main_review: There's one central point of high significance and (to my knowledge) originality in this paper, which is the idea of thinking of each individual data point as a degenerate model, and showing that being robust w.r.t. each point averages out to being robust to the average. The analysis itself is incremental (i.e. doesn't introduce new tools) but strengthens the result with guarantees — it's also interesting that they nearly match guarantees without robustness. The paper is also written very clearly.

As a non-expert in robust RL, I was missing some justification of the setting. An adversary that can perturb each step independently and with knowledge of past agent actions seems very strong, and robustness to it may give an overly cautious agent. It's also unclear to me why a uncertainty set of the form (4) is reasonable (e.g. where would it be applicable? how does it compare with KL level sets?), and in what sense the true dynamics is its “centroid”.

It makes sense to leave proofs for an appendix, but this should be indicated clearly. The authors should also consider providing some intuitive overview of the proofs, particularly involving the novel aspects. For example, a discussion of how (6) averages out to provide convergence can be insightful.

The experiments are very limited, including only two very simple domains, with 6.2 even excluding one of them (why?). How was R selected in each experiment?
limitations_and_societal_impact: The authors adequately address the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the robust reinforcement learning with uncertainty in the transition. A robust Q-learning algorithm is proposed for tabular MDPs and a robust TDC algorithm is proposed for compatibility of (linear) function approximation. Convergence rates are proved for both of the proposed algorithms. Empirical studies show that the two algorithms work for perturbed MDPs.
main_review: The presentation (writing quality and clarity) is good until the section of robust TDC. The algorithm design is a solid contribution. Below are some major concerns.

1. The projection $\Pi$ should be presented with more clarity: Line 228--should include an explicit expression, which I believe would not take too much space. Line 248--since there is no explicit expression of $\Pi$, it is not completely clear from the context why the equation after "we know that" holds.

2. Two-timescale: While the convergence guarantee involving two stepsizes, the final simplified rate is obtained via setting the two timescales the same $O(1/T^{0.5})$. This makes me wonder: is two-timescale design/analysis really necessary?

3. Experiment and limitation: The setting for the experiments is $p\cdot \mathrm{uniform} + (1 - p)\cdot p_s^a$, which completely falls into the $R$-contamination uncertainty set. The results do show that the proposed algorithms work better than their vanilla counterparts. There are some cited works on robust RL. I think it would be better if the authors add comparisons with the methods proposed in the previous works in the experiment section. Moreover, even compared to the vanilla algorithms, do the robust versions always work better? What if (i) the MDP is not perturbed? (ii) the MDP is perturbed in a way that the $R$-contamination fails to cover? It would be nice if the authors can add discussion to such limitations and also add experiments to show what happens in those "unfavorable" cases.

Below are some minor comments:

4. The role of $K$: I feel that the radius $K$ plays an important role in robust TDC. From the view of reproducing kernel Hilber space, if $K$ is large enough, then with suitable feature, the model misspecification errors caused by the function approximation can be very small. I think the authors need to discuss this constant more. In addition, the choice of $K$ should also be mentioned in the experiment section. (This issue is less robustness related though) 

5. Typo: Line 103 -- "provides", Line 246 -- definition of $C$ should be outer product. Clarity: Line 255 & 266/ Eq(17, 18) -- what kind of norm is used? Assumption 5 -- is it for all $\pi$?
limitations_and_societal_impact: See the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the model-free robust reinforcement learning, where the uncertainty set is assumed to be unknown. The authors propose a robust Q-learning algorithm for tabular settings and a robust TDC algorithm for function approximation settings. The authors theoretically analyze the converge properties for these two algorithms. Numerical experiments demonstrate the robustness of the proposed methods.
main_review: This paper is theoretically sound. The authors present the analyses in detail, and the convergence guarantee is very nice. The algorithm and assumptions are natural in many applications. The paper is well-written. Moreover, the authors provide numerical experiments to show the effectiveness of the proposed methods. When considering the function approximation setting, the authors propose the TDC algorithm, which corresponds to the policy evaluation phase. It will be better if the authors could provide a brief discussion about the robust policy improvement.
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on model free robust Q-learning that can be implemented online. The authors estimate the unknown uncertainty set (R-contamination model) with current samples. Under the perfect duality condition they obtain the bellman operator which optimize their robust objectives. They propose two different algorithms: one for tabular case and another one with function approximation for problems with large state and action spaces. The robust algorithms presented in the paper converges as fast as their non-robust counterparts. They also provide empirical analysis to show the usefulness of their proposed methods.
main_review: The paper is well written and different ideas flow smoothly. The authors were able to make the content comprehensible.
(a)	Their model-free approach requires less space complexity compared to model based method while being robust to uncertainty.
(b)	They were able to prove that their Q-learning algorithm converges asymptotically to the optimal value function.
(c)	They prove that their algorithm converges as quickly as the vanilla Q-learning while being robust to uncertainty.
(d)	They provide a linear function approximation of their algorithm (Robust TDC) which can be used in domains with large state and action spaces.

The paper does clearly explain how they are different from the previous works which mostly address Non-robust model based RL algorithms. Their algorithm is robust to model uncertainty, model free and can be used online while maintaining the advantages of less space complexity and same convergence complexity as standard non-robust Q learning.

The authors only compare their robust Q-learning method against the standard Q-learning. It can be interesting to see how their algorithm perform when compared against other methods, for example different variants of policy gradient, and actor critic methods.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: Based on the reviews and the discussion afterwards, my recommendation weighs towards acceptance. While the reviewers reached a consensus that the algorithms make novel and solid contributions, there remain some criticisms. First, the experiments can be made much more solid and comprehensive by adding previous robust RL methods as baselines, showing the tradeoff between robustness and pure performance, and presenting the performance evaluation in the face of misspecified uncertainty set. Second, I encourage the authors to also add discussion (and possibly theories) to address the limitation of the R-contamination model. I hope that the above concerns, along with other clarity issues raised by the reviewers, are addressed in the camera-ready version.
Decision: Accept (Poster)