Spectral-Risk Safe Reinforcement Learning with Convergence Guarantees

Summary

This paper considers spectral-risk safe RL algorithm with convergence guarantee. In particular, the paper considers a constrained MDP approach where the objective is to maximize the expected cumulative reward subject to the constraint that the spectral-risk measure is below a certain threshold. The main challenge lies in solving the optimization problem as it requires solve a bi-level optimization framework. The paper proposes first proposes a policy gradient based approach for solving the inner problem, and then proposes a gradient-based approach to sample according to the optimal spectral risk-measure.

Strengths

1. Developing a safe RL policy with spectral risk measure is important research problem. 2. The paper provides convergence guarantees and effective policies. 3. The paper also provides practical approaches for implementation. The empirical performance is good.

Weaknesses

1. The paper is a little-bit dense to parse everything. 2. While the paper provides a convergence guarantee, the paper did not provide any non-asymptotic rates for convergence. In particular, the sample-complexity guarantee has not been provided.

Questions

1. In order to solve the inner-optimization problem, the paper considers a primal-dual type algorithm for solving the feasibility function. What types of feasibility functions $F$ have been considered? Can the authors provide some outline on how the dual-variable updates as shown in Appendix B ensure feasibility? 2. For solving the outer optimization, the paper relies on minimizing the loss function. However, optimal policy that maximizes $J(\pi,\beta)$ is difficult because of the non-linearity in the feasibility function. Hence, the reviewer did not get how the algorithm solves the inner-optimization problem which seems to be different compared to the inner-optimization problem described in Section 5. 3. The convergence result (Theorem 6.3) relies on the Robbins-Monroe condition. Is it satisfied (in particular, for the optimization framework considered in Section 6 which is different from Section 5)?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Not as such.

Summary

This paper proposes a spectral risk measure-constrained RL algorithm, called spectral-risk-constrained policy optimization (SRCPO). This algorithm leverages the duality of spectral risk measures and treats the risk-constrained RL problem as a bilevel optimization. In this bilevel optimization problem, the outer problem is to optimize dual variables derived from the risk measures, while the inner problem is to find an optimal policy given these dual variables. The proposed algorithm is the first to guarantee convergence to an optimum in the tabular setting. Furthermore, the authors conduct experiments on continuous control tasks, and show that the proposed algorithm achieves the best performance among the compared RCRL algorithms.

Strengths

1. The studied problem, i.e., spectral risk measure-constrained RL, is well-motivated and can be applied to safety-critical scenarios, e.g., healthcare and finance. 2. This paper is very well-written and easy to follow. 3. The authors design a general algorithm framework and provide the convergence guarantee for a family of spectral risk-constrained RL problems. 4. Empirical evaluations are also provided to demonstrate the performance superiority of the proposed algorithm in practice.

Weaknesses

1. The idea of handling risk-sensitive RL by solving an inner problem (i.e., find an optimal policy under a fixed dual variable) and an outer problem (i.e., optimize dual variables) is not new. This idea appears in prior risk-sensitive RL works, e.g., (although these prior works may not consider constraints) [1] Wang, Kaiwen, et al. "Near-minimax-optimal risk-sensitive reinforcement learning with cvar." International Conference on Machine Learning, 2023. [2] Chen, Yu, et al. "Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback." International Conference on Learning Representations, 2023. 2. The current format of Algorithm 1 is not clear enough. The specific algorithm steps should be included, e.g., the policy update, the distribution update (how to find $\xi$) and the sampling. 3. It seems that Theorems 5.3 and 6.3 are the theoretical guarantees for the inner and outer problems, respectively. Can the authors give the theoretical guarantee of the overall performance for the spectral risk measure-constrained RL problem? 4. The provided results only state that the algorithm will converge to the optimal policy. Can the authors comment on the convergence rate or sample complexity?

Questions

Please see the weaknesses above.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Please see the weaknesses above.

Summary

In this paper, the authors have considered the framework of risk-constrained reinforcement learning (RCRL) by tackling risk-measure-based constraints. The non-linearity of risk meaures makes the convergence of RL schemes challenging. In this paper, a spectral risk measure-constarined RL algorithm is proposed. The proposed algorithm is based on a bilevel optimization. The outer problem deals with optimization of dual variables, while the inner one finds the optimal solution given the a set of dual variables. The authors claims that the proposed scheme is the first method which convergs to optimality for tabular MDP problems. Simulation results are presented where the proposed methods are tested on continuous control tasks.

Strengths

The paper is well-written and easy to follow. The results and claims presented in the paper appears to be correct.

Weaknesses

There are some limitations with respect to the constructed loss function and scalability of the adopted linear interpolation mechanism.

Questions

1. The proposed approach approximates the spectrum by a discretized spectrum. What is the gap in performance with respect to the optimal solution of the original system? Although in Theorem 6.2, it is derived that as $M$ becomes large, performance gap reduces to zero, how does this $M$ scale as the number of states and actions increases? 2. The intuition behind the sampling process and why it works is not clear. 3. What is the rationale behind the loss function proposed by the authors? Why is the loss function novel? Is there any other loss function for which the scheme does work well? If yes, can the authors come up with a more general loss function? If no, then this is a limitation of the work that it works for only a specific type of loss function (constructed by the authors).

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

The paper provides the new spectral-risk-costrained policy optimization algorithm, that uses the duality of spectral measures, and bilevel optimization approach to address the risk constrained reinforcement learning problem, solving the inner primal problems and outer dual problem. The paper provides global convergence guarantees in the tabular setting. The paper supports the results with the experimental comparisons to other methods.

Strengths

The paper is well written, despite many complex notions used in the flow, they all are clearly introduced. The theoretical result seems to be solid and important to the community. The idea to solve the dual problem of the risk-constrained rl using a sampler distribution seems to be novel too. The proofs are provided, however I did not check them carefully. The experiments demonstrate a good performance of the proposed method.

Weaknesses

There are several things which are not very clearly defined and a few minor typos that I noticed. line 88: F_X is not defined, I believe it is a probability function? line 168: where the log in eq. (9) comes from? Conflicting notations: - Now, aplha is used both for denoting the learning rate and the risk parameter. Maybe, the authors could use different notations for these notions. - F is probably a probability function, and then a feasibility function (line 114). - in theorem 6.2 i is used to iterate over the discretization 1:M-1, but later used to iterate over constraints 1:N, and j is used for discretizations. maybe use j in thm. 6.2 and other places consistently too? Typos: line 102: an -> a

Questions

all questions are above in the weaknesses section

Rating

7

Confidence

2

Soundness

4

Presentation

3

Contribution

4

Limitations

The limitations are discussed. There is no potential negative societal impact.

Follow up

Thanks for your response. I will go over the comments carefully. As for the proof like CRPO that you provided in the general response, I have one question. Since this is a constrained problem, how you are ensuring that $J_R(\pi^*)-J_R(\pi_t)\geq 0$. Since this is a constrained problem, $\pi_t$ may be infeasible and may have a better value compared to $J_R(\pi^*)$.

Convergence rate analysis in the general response

As the reviewer DPN9 pointed out, the proof of the convergence rate provided in the general response above has an error: "$J_R(\pi^*) - J_R(\pi_t) \geq 0$ for $t \in \mathcal{N}$" does not hold. We apologize for the confusion. We modify the proof as follows, starting from the statement "Also, due to $J_R(\pi^*) - J_R(\pi_t) \geq 0$ for $t \in \mathcal{N}$" in the original proof above. --- Given that $D + \frac{2T\alpha^2K^2(\alpha + 1)^2}{(1-\gamma)^5} + \frac{2T\alpha^2K}{(1-\gamma)} \leq \frac{\alpha\eta T}{2}$, one of the following must hold: (1) $|\mathcal{N}| \geq \frac{T}{2}$ or (2) $\sum_{t \in \mathcal{N}}(J_R(\pi^*) - J_R(\pi_t)) \leq 0$. Assume neither condition is satisfied. Then, $\frac{\alpha\eta T}{2} < (T - |\mathcal{N}|)\alpha\eta = \sum_{t \notin \mathcal{N}}\alpha\eta < \sum_{t \in \mathcal{N}}\alpha(J_R(\pi^*) - J_R(\pi_t)) + \sum_{t \notin \mathcal{N}}\alpha\eta \leq D + \frac{2T\alpha^2K^2(\alpha + 1)^2}{(1-\gamma)^5} + \frac{2T\alpha^2K}{(1-\gamma)} \leq \frac{\alpha\eta T}{2}$, which leads to a contradiction. Therefore, one of the two conditions must hold. Furthermore, if we assume $|\mathcal{N}| = 0$, it follows that $\alpha\eta T \leq \frac{\alpha\eta T}{2}$, which is also a contradiction. Hence, $|\mathcal{N}| \neq 0$. If $|\mathcal{N}| \geq T/2$, $J_R(\pi^*) - \mathbb{E}\_{t \sim \mathcal{N}}[J_R(\pi_t)] = \frac{\sum_{t \in \mathcal{N}}(J_R(\pi^*) - J_R(\pi_t))}{|\mathcal{N}|}$ $\leq \frac{2(D + \frac{2T\alpha^2K^2(\alpha + 1)^2}{(1-\gamma)^5} + \frac{2T\alpha^2K}{(1-\gamma)})}{\alpha T} \leq \frac{2D + 20K^2}{(1-\gamma)^{2.5}\sqrt{T}}$, and this inequality also holds for $\sum_{t \in \mathcal{N}}(J_R(\pi^*) - J_R(\pi_t)) \leq 0$. Consequently, $J_R(\pi^*) - \mathbb{E}\_{t \sim \mathcal{N}}[J_R(\pi_t)]\leq\frac{2D + 20K^2}{(1-\gamma)^{2.5}\sqrt{T}}$. Also, $\mathbb{E}\_{t \sim \mathcal{N}}[J{C_i}(\pi_t)] - d_i \leq \eta = \frac{2D + 20K^2}{(1-\gamma)^{2.5}\sqrt{T}}$.

Thanks

I thank the authors for their response. I keep my score and support acceptance.