Venue: UAI 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., lack of novelty, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: Q1 Summary and contributions: This paper focused on the discounted constrained Markov decision process (CMDP) and proposed the Coin Betting Politex (CBP) with $O(1/(1-\gamma)^3\sqrt{T})$ reward-suboptimality guarantee and $O(1/(1-\gamma)^2\sqrt{T})$ constraint violation. In addition, the experiment results also support the efficiency of this novel algorithm.
Q3 Main strengths: 1. Compared with prior works, the Coin Betting Politex does not require tuning a hyperparameter, which is much more stable than other algorithms.
2. This work provides a theoretical guarantee for algorithm performance. In addition, Experiment results also show that the novel algorithm outperforms other baseline algorithms.
Q4 Main weakness: 1. In the abstract, the author mentions that it is possible to find a policy with $O(1/(1-\gamma)^3\sqrt{T})$ reward-suboptimality guarantee and $O(1/(1-\gamma)^2\sqrt{T})$ constraint violation. However, there lacks the main theorem to illustrate this result. It is unclear how to set the parameter $\pi_0,\lambda_0,m$ in the Coin-Betting Politex. It is difficult to check the claim that the Coin Betting Politex algorithm does not require tuning this parameter.
2. For all works on linear function approximation, the dimension $d$ is important and relevant to the final result. However, if we assume the approximation error $\epison_b=0$, the result in the abstract shows that the output algorithm has the same guarantee whatever the dimension $d$ is, which conflicts with priors work on linear function approximation.
3. This work lacks an estimation for the complexity, and it is better if there exists a comparison with the prior results on both time and space complexity.
Q5 Detailed comments to the authors: See Q4
Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: There is no main theorem to describe the main result, and it is not clear how to set the parameters. Without this information, it is difficult to check the main contribution that the Coin Betting Politex algorithm does not require tuning this parameter.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept, e.g., novelty, outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: Q1 Summary and contributions: The paper describes a primal-dual framework for solving constrained MDPs by online linear function optimization based on an online betting algorithm (Coin Betting Politex or CBP) that doesn’t have hyper parameters that need to be tuned. (By contrast, hyper parameters are commonly used by gradient descent-ascent methods.) The CBP algorithm is proved sound and bounds are given.
Q3 Main strengths: The approach is mathematically sophisticated and appears to be very carefully thought through. 

Q4 Main weakness: The paper is written in a way that makes it difficult to understand or appreciate the contribution, and put it in perspective. In addition, the test problems are very small with no discussion of scalability. 
Q5 Detailed comments to the authors: The name “painless policy optimization” is used in the title, without explanation in the paper. My guess is that it means the approach minimizes hyper-parameter tuning. If so, that should be stated clearly. (My first guess was that the adjective “painless” is used ironically!)

Although difficult to read, the paper is in a sense also well-organized and carefully and precisely written. What I think is missing is that it does not place the results in perspective and provide a high-level explanation that can help the reader better understand the significance of the results. Is it all about reducing use of hyper-parameters in online optimization? I'm guessing that's it, but am not sure, or even sure that's important compared to simplicity or scalability (for example) -- I would have liked a clearer explanation.

The paper overly relies on long supplementary appendices, not just for proofs, but for details that should be in the paper itself. I wanted to ignore the appendices, but couldn’t, because I needed to see the details of the example problems to help interpret the results. Repeated references to supplementary appendices may be unavoidable, I don’t know, but it certainly makes it more difficult for the reader.

The test problems are surprisingly small: a 5 by 5 grid world and a cart pole problem. When test problems are this small, I think it’s important to include some discussion of scalability. Is it really true that the research community cannot solve completely observed constrained MDPs bigger than a 5 by 5 grid world?

The graphs are almost too small to read.

I missed some discussion of future work, potential applications, or any attempt to place this work into a wider perspective that could help the reader better understand its significance.

p. 4 typo: “our result does it require”
Q2(4) Quality of experiments (Optional): 2: Fair: The experimental evaluation is weak: important baselines are missing, or the results do not adequately support the main claims.
Q7 Justification for your score: A mathematically sophisticated approach to online linear optimization for constrained MDPs that seems technically correct (although it is beyond my ability to verify the details). The paper is difficult to read, however, and the authors do not do enough to help the reader place this work in perspective and understand its significance.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper with, with novel ideas, excellent impact on at least one area of AI or high to excellent impact on multiple areas of AI, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations. 
review_content: Q1 Summary and contributions: In this article, the authors propose an original RL algorithm for approximately solving Constrained MDPs.
They put together some recent techniques and add several new theoretical results.
The CBP algorithm is described and extensive experiments are presented.
Unfortunately, the code of the algorithm/experiments are not made available.
Q3 Main strengths: Numerous "strong" theoretical results.
Still an "intuitive" RL algorithm for CMDP. 
Q4 Main weakness: Unavailability of code and non-reproducibility of experiments.
Q5 Detailed comments to the authors: This paper provides a quite involved mathematical analysis of an original primal-dual type RL algorithm for CMDPs.
In addition to its mathematical strength, it provides good algorithmic description and strong experiments.
The only weak point of this paper is the lack of reproducibility of the experimental results. Even though it is mainly a theoretical contribution, the reproducibility of experimental results seems to me crucial, in the domain of RL.
This written, I find that the paper is still very good. 

Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: The contribution is very strong and the algorithm useful. for me, this is really a good paper.
My only reservation is about the unavailability of the code: My feeling is that code availability is nowadays as important as proofs availability, to assess algorithmic advances. I hope the authors will made their code available...
review_title: null

Meta-review: Meta Review: The theoretical merit are recognized by reviewers. There are also several drawbacks of the paper, as pointed out by reviewers (and not well-addressed in the review response), which are
* How to set the hyperparameters in the Coin Betting Politex algorithm
* The impact of the dimension d
* The content is too dense, so the paper is hard to follow.

Decision: Accept (Poster)