Anytime-Competitive Reinforcement Learning with Policy Prior

Summary

This paper addresses the problem of anytime constrained RL. Contrary to traditional constrained RL where the constraints are expressed as expected costs, this work looks at a stronger criteria that the cost should be bounded for any episode. The cost is defined relative to the performance of an existing safe policy deployed in the environment of interest. An algorithm (ACD) is derived which consists in deriving a safe action set by computing the maximum allowed deviation from the prior policy. The computation relies on the knowledge of Lipschitz constants characterizing the transition model, the cost variation, and the policy prior. This algorithm allows to take safe actions but does not address optimizing the return. ACD is extended to ACRL which adds the learning and optimization parts to maximize the return while taking safe actions. ACRL is a model based algorithm. An analysis of the regret of the algorithm is provided to analyze the regret from the anytime constraint and from the learning part.

Strengths

The introduced framework of A-CMDP is very sound and fits many practical applications. The main assumption of the work that there exist a policy prior is a strong one but I believe it applies to a lot of problems and is quite relevant. The associated definition of regret makes sense, although the formalism of the A-CMDP is sometimes unclear. The article is fairly well written. All propositions and assumptions are followed by an intuitive explanation and they all seem sound. The discussion of the related work and their relation to what is being presented is clear and seems to cover most of the relevant topics. The structure of deriving first ACD and ACRL is useful to follow the work and the algorithms make sense given the proposed assumptions.

Weaknesses

The authors did not include the experiments in the main body of the paper. The experiments show that the algorithm is better in terms of worst case cost, but does not provide the best regret per episode (expected since stronger constraints). The algorithm is evaluated on only one problem, it would have been useful to test it on at least one other problem to show its value, maybe some classical benchmark from the safe RL literature. An ablation study of showing the performance of the model-based approach without the constraints would have been useful as well. Adding the experiments to the main body seems necessary to me. Although the intuitive explanation of the A-CMDP is clear, there are some unclarities in the mathematical definition of the A-CMDP (see questions). The main assumptions of the article require the cost functions, transition functions, and prior policy to have some sort of Lipschitz continuity property with known constants. At the same time, a main advantage of the proposed algorithm is that it does not require to know much of the dynamics, it seems a bit contradictory. The author provide some arguments with support from related work but I am still curious whether a precise knowledge of this constant is important or not. In ACRL, the state augmentation part increasing significantly the size of state by adding a dependency on the history. This approach raises scalability issues which are not discussed in the paper.

Questions

- I am not sure I understand why the notion of model (y) is needed in the definition the A-CMDP, as opposed to the notion of trajectories more common in the RL literature? - Why is the value definition an expectation over the first state $x_1$? Shouldn’t it be an expectation over trajectories like in regular MDPs? - How does one find the necessary Lipschitz constants in a problem where the dynamics is unknown? Is it important to have accurate values? - In proposition 4.1, how can the cost of the policy prior be known if it is not executed?

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.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors are explicitly mentioning the limitations at the end of the paper. However, I find the discussion somewhat contradicting. One of the main related works rely on knowledge of the dynamics and this work relies on knowledge of the Lipschitz constants and some information about the policy prior. Is it really much simpler to get this information compared to an approximate dynamics model?

Summary

Existing work on Constrained Markov Decision Processes (CMDPs) typically formulate a problem where the expected cumulative reward is maximized under a constraint where the expected cost over random dynamics is less than some threshold. Such existing work has a drawback that the safety constraint is violated in a specific episode. Hence, the authors study a problem named Anytime-CMDP (A-CMDP). The objective of the authors is to optimize the reward value function while guaranteeing the satisfaction of the safety constraint in each round of any episode. Under several assumptions (e.g., telescoping policy prior, Lipschitz continuity), the authors propose a new algorithm, called Anytime-Constrained Reinforcement Learning (ACRL) and provided theoretical results on constraint satisfaction and regret. The authors conduct experiments on the application of carbon-intelligent computing.

Strengths

- Important problem settings. The drawbacks of the typical CMDPs have been discussed in recent years, so I think this paper will attract much attention within safe RL research community. - Good theoretical results. Though there are many assumptions, the obtained theoretical results are indeed good. Given the difficulty of the problem (and the theoretical results the authors try to provide), the number and strength of the assumptions are somewhat reasonable.

Weaknesses

- There are several important missing citations and comparisons. Especially, Ref-1 is very relevant to this paper, which try to guarantee the satisfaction of the safety constraint with probability of 1. This paper is exactly the same motivation to Ref-1 though the approaches are quite different. Though I understand there are pros and cons as follows, it is extremely important to discuss the differences between Ref-1 and this paper. ``` [Ref-1] + High performance in complicated environments (e.g., Safety-Gym) + High affinity with deep RL + Assumptions are weak - No theoretical guarantee [This paper] + Theoretical guarantee - High affinity with deep RL - Assumptions are strong ``` - Also, anytime constraints have been also studied in several literature. For example, [Ref-2] and [Ref-3] formulate their safety constraint as an instantaneous one $c(s_t, a_t) \le d$ and propose algorithms to guarantee its satisfaction with high probability (though it is not probably of 1). It seems quite miss-leading that Table 1 show that ACRL is the first and only work to deal with any-time constraint. - Regarding experiments, the benchmark problem used in this paper is not popular and it would be better to evaluate their method in standard ones (e.g., Safety-Gym). Especially, if I understand correctly, the SOTA algorithm in the problem settings the authors address is Saute-RL in [Ref-1] and the I consider that there should be some comparison between ACRL and Saute-RL. - There are so many strong assumptions, which makes us to follow this paper. I guess it is partly because the authors try to derive regret bound as well as guarantee safety. I wonder what is the minimal set of assumptions for guaranteeing safety. It may be better to focus on guaranteeing safety with a small number of assumptions, which make this paper easy to follow and the contribution clearer. - References - [Ref-1] Sootla, Aivar, et al. "Sauté RL: Almost surely safe reinforcement learning using state augmentation." International Conference on Machine Learning. PMLR, 2022. - [Ref-2] Wachi, Akifumi, and Yanan Sui. "Safe reinforcement learning in constrained Markov decision processes." International Conference on Machine Learning. PMLR, 2020. - [Ref-3] Amani, Sanae, Christos Thrampoulidis, and Lin Yang. "Safe reinforcement learning with linear function approximation." International Conference on Machine Learning. PMLR, 2021.

Questions

[Q1] Is there any reason why standard safe RL benchmark problems (e.g., Safety Gym) were not used? [Q2] What is the minimal set of assumptions that are needed for guaranteeing safety?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Limitations have been adequately addressed.

Summary

The paper studies a novel problem of Anytime-Constrained Markov Decision Process (A-CMDP), where the goal is to optimize the expected reward while guaranteeing that the cumulative cost in each round of any episode does not exceed a relaxed version of the cost of a policy prior. The paper proposes a projection-based algorithm, called Anytime-Constrained Decision-making (ACD), which ensures the anytime cost constraints by projecting the output of a machine learning policy into safe action sets at each round. The paper also develops an efficient model-based reinforcement learning algorithm, called Anytime-Constrained Reinforcement Learning (ACRL), which learns the optimal ML policy for ACD via value iteration and model estimation. The paper provides theoretical analysis on the regret performance of ACRL, showing the trade-off between reward optimization and anytime constraint satisfaction, as well as the effectiveness of policy learning.

Strengths

- The paper addresses an important and novel problem of A-CMDP, which has direct motivations from many mission-critical applications that require strict cost constraints for safety and reliability. - The paper introduces a novel algorithm, ACD, which can guarantee the anytime constraints given any ML policy by projecting it into safe action sets. The paper also develops a model-based RL algorithm, ACRL, which can learn an optimal ML policy to be used in ACD. - The paper provides rigorous theoretical analysis on the regret performance of ACRL and shows how it depends on the relaxation parameters and the discrepancy between the policy prior and the optimal-unconstrained policy. - The paper presents empirical results on an application of resource management for carbon-aware computing, although all of this part is in appendix.

Weaknesses

- The paper makes some strong assumptions on the Lipschitz continuity of the cost and transition functions, and the telescoping property of the policy prior, which may limit its applicability to more general environments. Specifically, the telescoping property of the policy prior is a strong assumption for both the policy and the dynamics. It would be interesting to explore how to relax these assumptions or how to estimate them online without compromising safety. - The paper also relies on the assumption that the safe policy prior can be queried on any state, even if the state is not explored on the policy prior trajectory. This assumption may not be feasible in real applications. - The paper does not provide much intuition or discussion on how the relaxation parameters or other parameters would affect the exploration-exploitation trade-off and the robustness of ACRL.

Questions

- How does ACRL scale with large state-action spaces or long horizons? What would be the challenges there and how would the scale affect the convergence? - What are the computational challenges or bottlenecks in implementing ACRL? - How sensitive is ACRL to errors or uncertainties in estimating the Lipschitz constants, minimum cost value, or perturbation function? - In some applications there might be several constraints. How can ACRL be extended to handle multiple costs or multiple constraints?

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.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately listed most limitations in their work, such as assuming Lipschitz continuity, telescoping property, and known parameters. Those are reasonable to some extent since as stated by the authors, there is no way to guarantee any time safety constraints without any knowledge of the properties of the dynamics. However, they could also discuss some possible extensions or future directions based on their limitations, such as relaxing some assumptions, incorporating online estimation, exploring more applications, or improving scalability.

Summary

This paper proposed a novel problem called Anytime-constrained Markov Decision Process. Unlike CMDP, at each step, a constraint should be satisfied. A projection-based algorithm is proposed to solve the Anytime-constrained MDP. The authors gave a perturbation-based regret analysis for the algorithm.

Strengths

The paper has great novelty. The anytime constrained MDP is a new problem formulation and has good value for real-world safety-critical problems. The perturbation-based analysis is solid to me.

Weaknesses

Although the problem formulation is novel, the analysis might be weak. The assumptions of known Lipschitz constant, a prior policy, might be too strict. Thus, the regret analysis might have limited guidance for the real-world problem. I have seen that the authors already mentioned it in the limitations. The writing needs to be improved. Some words in the important part of the paper are confusing. For example, 1. in Definition 3.3, the initialized and corresponding look quite confusing to me. Initial distribution usually refers to the states at step, or round, 0. The correspondence is also not clear. You might need to add more explanation to lines 153-159. 2. in line 328, the linear kernel assumption is mentioned inline, which is critical to the major contribution of this paper. The assumptions should be highlighted and discussed more.

Questions

1. From intuitions of the constrained optimization theory, the projection-based algorithm might not be guaranteed to be optimal with non-convex objectives/constraints. Would you mind giving me some intuitions about why the projection-based algorithm will result in an asymptotically optimal ACD policy?

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.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors addressed the limitations well.

Thank you for the clarifications, please add the experiments to the main text

I thank the author for answering all my questions and comments, I acknowledge reading the rebuttal. I am willing to keep my recommendation for acceptance, since they author plan to add the experiment results in the main body of the paper. I would also appreciate it if they can make the scalability issue more obvious in the text. Being a bit more picky on the value definition, I think it is missing the dependency on the policy to be correct. It is conditioned on the starting state but should be also conditioned on the actions following a given policy.

Thank you for rebuttals

Thank you for the convincing rebuttals. **The differences between Ref-1 and this paper.** I understand the differences. It would be helpful for the readers to add such discussion. Please include it in the camera-ready version. **Reasons for the assumptions.** Though I still consider it quite strong, I understand the assumptions are indeed necessary for solving safe RL problems. **Why not evaluate on standard benchmarks?** I understand. If the benchmark is not standard one, it is more necessary to release the source-code for reproducibility. Please consider open-sourcing the source code for RL environments and agents. **The any-time constraint in Table 1.** I recommend the authors to improve the Table 1 for avoid over-claiming. Under the condition that the authors improve the paper based on the above comments, I increased the score from 3 to 5.

Thanks for the response

I want to thank the authors for their response. I find it helpful to address my questions. I would like to keep my original scores at this point.