Efficient Action-Constrained Reinforcement Learning via Acceptance-Rejection Method and Augmented MDPs

Authors: Wei Hung, Shao-Hua Sun, Ping-Chun Hsieh
Primary area: reinforcement learning
Keywords: Reinforcement learning, action constraints

Abstract:
Action-constrained reinforcement learning (ACRL) is a generic framework for learning control policies with zero action constraint violation, which is required by various safety-critical and resource-constrained applications. The existing ACRL methods can typically achieve favorable constraint satisfaction but at the cost of either high computational burden incurred by the quadratic programs (QP) or increased architectural complexity due to the use of sophisticated generative models. In this paper, we propose a generic and computationally efficient framework that can adapt a standard unconstrained RL method to ACRL through two modifications: (i) To enforce the action constraints, we leverage the classic acceptance-rejection method, where we treat the unconstrained policy as the proposal distribution and derive a modified policy with feasible actions. (ii) To improve the acceptance rate of the proposal distribution, we construct an augmented two-objective Markov decision process (MDP), which include additional self-loop state transitions and a penalty signal for the rejected actions. This augmented MDP incentives the learned policy to stay close to the feasible action sets. Through extensive experiments in both robot control and resource allocation domains, we demonstrate that the proposed framework enjoys faster training progress, better constraint satisfaction, and a lower action inference time simultaneously than the state-of-the-art ACRL methods. We have made the source code publicly available to encourage further research in this direction.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1730114554976

thread_type:
official_review

<thread_object>
creator: reviewer_edlj

<content>
summary:
This work presents a groundbreaking approach to learning control policies that adhere to strict action constraints, making it perfect for safety-critical and resource-constrained applications. The authors introduce a novel framework that enhances traditional reinforcement learning methods by utilizing the acceptance-rejection method and an augmented two-objective Markov decision process.

strengths:
The framework significantly reduces the computational burden associated with traditional ACRL methods, which often rely on solving complex quadratic programs (QPs). By utilizing the acceptance-rejection method, the need for QP operations is largely obviated, leading to faster training times.

weaknesses:
The effectiveness of the acceptance-rejection method heavily relies on the quality of the initial policy. If the initial policy is far from optimal, it may result in a high number of rejected actions, which can hinder learning progress and increase computational overhead. While the augmented MDP approach aims to improve acceptance rates, it introduces additional complexity to the learning process. The design and tuning of the penalty function and self-loop transitions may require careful consideration, and improper tuning could lead to suboptimal performance.

questions:
1. What metrics were used to evaluate the acceptance rate during the experiments, and how were these metrics calculated?
2. Is there a systematic approach to determine the optimal penalty weight, or is it left to empirical tuning?
3. Conducting more experiments on hyperparameter sensitivity is better.
4. Whether introducing AUTO-MDP in the theoretical aspect will affect the guarantee of convergence, while the current article only discusses the optimality.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730213770787

thread_type:
official_review

<thread_object>
creator: reviewer_meyg

<content>
summary:
This paper aims to adapt the standard unconstrained RL method to ACRL via two proposed techniques: an acceptance-rejection method and an augmented two-objective MDP. It compares ARAM with various recent benchmark ACRL algorithms on MuJoCo tasks and Resource allocation for networked systems, showing the superiority of ARAM in terms of training efficiency, valid action rate, and per-action inference time.

strengths:
1. This paper is well-written and easy to follow.
2. I appreciate the experiments in terms of the considerable evaluation metrics.
3. I am not very familiar with the ACRL field. From my perspective and limited knowledge of this field, I appreciate the proposed direction to solve the ACRL problem, I think it is a new try.

weaknesses:
1. The proposed preference distribution tuning procedure seems a bit redundant. It is better to compare ARAM with fixed $\lambda$  to the baselines for a fair comparison. Otherwise, it is hard to distinguish whether the main components (acceptance-rejection method and AUTO-MDP) are more important or the preference distribution tuning procedure. As we can observe in Figure 11, ARAM is not quite robust to the  $\lambda$, and a single set of  $\lambda$  could not achieve satisfactory performance across all tasks.  To make the comparison more fair and isolate the effects of the main components, it would be helpful to suggest that the authors include results for ARAM with a fixed λ alongside the current results in the main paper and hope to see the superiority of ARAM without $\lambda$-tuning. This would allow readers to better understand the relative contributions of the acceptance-rejection method, AUTO-MDP, and preference tuning. Of course, you may not need to fully resolve this weakness, yet I suggest explicitly mentioning it as a limitation. 
2. Several experimental details have not been provided. For example, what is the value of M and $\kappa$ for all the tasks, and other parameters used? They are quite important details.

questions:
1. Could you provide the value of $M$ and $\kappa$ for all the tasks?  Do you need extra tuning on these two hyperparameters? 
2. Could you provide the computation infrastructure?
3. Is it possible that ARAM with a single setting of fixed $\lambda$  outperforms other baselines across MuJoCo locomotion tasks? It is suggested that the authors conduct an experiment with a single fixed λ across all MuJoCo tasks and report those results, or explain why such an experiment might not be feasible or meaningful.
4. I find in Table 2 that NFWPO enjoys the highest valid action rate. That indicates that it requires a smaller number of QP operations, as opposed to DPre+ and SPre+. Yet in Figure 4, NFWPO shows the highest number of QP operations, which seems conflict to with the analysis in Lines 456-462. Please clarify this apparent contradiction and, if necessary, correct either the data or the analysis.
5. In the last row of Table 2, 0.77 is much lower than 0.84, thus I suggest not making it bold.
6. As claimed in the abstract, "We propose a generic and computationally efficient framework that can adapt a standard unconstrained RL method to ACRL through two modifications". Could the authors provide ARAM techniques with another backbone standard RL algorithm to support this claim?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730636441675

thread_type:
official_review

<thread_object>
creator: reviewer_g8e7

<content>
summary:
This paper proposes a novel framework for action-constrained reinforcement learning, named ARAM, which integrates an acceptance-rejection method and an augmented Markov decision process to alleviate the low action acceptance rate problem under ARM. ARAM aims to avoid the computational burden associated with quadratic programs in existing ACRL methods while achieving less constraint violations. The authors demonstrate through experiments on robot control and resource allocation tasks that ARAM achieves faster training, better constraint satisfaction, and reduced action inference time compared to various recent ACRL algorithms.

strengths:
- Well-written paper with clear objectives.
- Although the two key improvements (ARM and AUTO-MDP) are straightforward, the experimental results demonstrate the elegance and efficiency of this method in addressing the ACRL problem.
- The paper is well-supported with experiments that compare ARAM against various benchmarks, showcasing improvements in training speed, constraint satisfaction, and inference time.
- The authors have the intention to share the code.

weaknesses:
- The experiments are only conducted in simple simulation environments. Applying the method to real-world scenarios would make the results more impressive and convincing.
- Lacks experimental comparisons of the ARM acceptance rate.
- The paper lacks a discussion on the limitations of the method.

questions:
- Does the choice of different target distributions in ARM have a significant impact on the final results?
- Is the ARM’s acceptance rate analyzed in detail across the different stages of training? It would be useful to understand if and how the acceptance rate varies in the proposed setup.
- What role do quadratic programs (QP) play in ARAM? QPs are not included in Algorithm 1 or Figure 2.
- How is MORL implemented in ARAM? Does it significantly increase computational requirements?
- The layout of Algorithm 1 in the paper needs adjustment.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720825232

thread_type:
official_review

<thread_object>
creator: reviewer_osn9

<content>
summary:
The paper presents acceptance-rejection augmented MDPs, a novel framework proposed to improve action-constrained reinforcement learning. The method aims to address the computational inefficiencies and architectural complexities in existing Action-Constrained Reinforcement Learning (ACRL), by incorporating two key innovations: an acceptance-rejection mechanism to filter out infeasible actions, and an augmented MDP to optimize policy training towards feasible regions by penalizing constraint violations. The framework is empirically tested against state-of-the-art ACRL benchmarks in robotic control and resource allocation domains. Overall, the idea of combining the acceptance-rejection method with the augmented MDP is interesting, but the work could be improved in both the methodology and the experimental demonstration (see Weakness and Questions below for further details).

strengths:
1. The computational overhead caused by solving QPs is challenging in existing ACRL methods, particularly scaling to high-dimensional action spaces.

2. The paper integrates a multitude of concepts such as action-constrained reinforcement learning, Acceptance-rejection
method, and Augmented MDPs. These topics have been at the forefront of recent research trends.

3. The paper is well-organized, with clear explanations of the background, the proposed methods, theoretical foundations (including Proposition 1), and detailed experimental setups.

weaknesses:
1. The two main components, i.e., the acceptance-rejection method and augmented unconstrained MDPs, seem somewhat contradictory. They represent opposing optimization strategies: the acceptance-rejection method directly filters out actions outside the feasible set, potentially leading to overly conservative decisions; then, the augmented MDP penalizes constraint violations in a gradual way, providing a “soft” learning approach for the agent. However, this softer approach does not fully guarantee that actions remain within the feasible set.

2. While some theoretical insights are provided, including optimality equivalence in Proposition 1, key theoretical gaps remain unaddressed. Specifically, for augmented MDPs, there is no guarantee that actions won’t violate constraints, i.e., a critical issue in action-constrained reinforcement learning.

3. The introduction highlights the computational challenges of scaling quadratic programs to high-dimensional action spaces. However, the experimental analysis in Section 5 primarily explores action constraints in relatively lower-dimensional spaces. The performance of ARAM in high-dimensional action spaces (such as complex robotic manipulators) would benefit from more in-depth analysis.

questions:
1. How can the augmented MDP approach guarantee that actions remain within constraints? Even if complete avoidance of constraint violations is not feasible, it would be useful to establish an understanding, such as defining a convergence rate and probability that constraint violations will diminish to a certain margin of error over time.

2. Can the scalability of the proposed ARAM framework be demonstrated in high-dimensional action spaces, through a comparative analysis with existing ACRL methods?

3. Although the authors state "... we directly leverage the multi-objective extension of SAC that can learn policies under all the penalty weights." (page 2), it seems that multi-objective reinforcement learning approaches might be sensitive to hyperparameters, such as the penalty weight. Is ARAM similarly sensitive to this hyperparameter, particularly in its convergence behavior? Additionally, how is the penalty weight selected in practice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732450195668

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Part2)

comment:
**Q4: Explain how ARAM ensures that actions remain within constraints.**

**A4:** Recall that the proposed ARAM framework involves two main components: (1) Acceptance-Rejection method and (2) Augmented MDPs. We would like to highlight the purpose of each component as follows:
* **Acceptance-Rejection method guarantees that actions remain within constraints:** To ensure that the actions can satisfy the constraints, ARAM leverages the Acceptance-Rejection method, which by design can filter out those actions that fall outside the feasible set and thereby ensures constraint satisfaction. 
* **The issue of possibly low acceptance rate with the Acceptance-Rejection method:** Despite the capability of the Acceptance-Rejection method on enforcing action constraints, one technical issue is the possibly low acceptance rate, which is likely to occur in the early training stage. Under a low acceptance rate, the sampling process could take indefinitely long and incur a high overhead during training. For example, if the action acceptance rate is as low as 0.001%, then in expectation it could take 10^5 samples to get one feasible action (under i.i.d. sampling).
* **Augmented MDPs can improve the action acceptance rate for the sampling process of the Acceptance-Rejection method:** To address the above issue, we propose to leverage an Augmented MDP, which guides the policy distribution towards feasible action sets for a higher acceptance rate. Note that Augmented MDP is only meant to proactively increase the action acceptance rate (not to ensure that the actions remain within constraints).
In summary, the Acceptance-Rejection method and the Augmented MDP serve different purposes. It is the Acceptance-Rejection method that ensures the actions remain within constraints.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732450238530

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Part1)

comment:
**Q1: Scalability of ARAM to high-dimensional action spaces**

**A1:** To demonstrate the scalability of ARAM to higher-dimensional environments, we extend the NSFnet environment to that with a 20-dimensional action space. Specifically, the agent manages packet delivery across a classic T3 NSFNET network backbone by simultaneously handling 20 packet flows (each with distinct routing paths). The action is defined as the rate allocation of each flow along each candidate path. In total, there are 30 communication links shared by these 20 different flows. The action constraints are meant to ensure that the distribution of packets on these shared links stays within the bandwidth capacity, defined as 50 units for each link.

The results are available at https://imgur.com/a/Uz7oD9Q

The above show the evaluation return, valid action rate, and the number of QP operations of ARAM and the benchmark algorithms. We observe that ARAM consistently demonstrates favorable growth in action valid rate, maintaining a high level of performance even under high-dimensional actions. Moreover, ARAM outperforms the ACRL benchmark methods in the evaluation return while enjoying the least amount of QP overhead. This highlights ARAM's ability to effectively adapt and learn under high-dimensional actions and complex constraints.

**Q2: Experiment on hyperparameter sensitivity (e.g., the violation penalty $\mathcal{K}$)**

**A2:** Recall that $\mathcal{K}$ denotes the constant penalty used in the Augmented MDP for improving the action acceptance rate. In the experiments of the original manuscript, we set  $\mathcal{K}=0.1$ for all the tasks across all environments, i.e., MuJoCo, NSFnet ,and BSS (that is, there was no task-specific tuning needed for $\mathcal{K}$ in our experiments).

To further assess the influence of this hyperparameter on training ARAM, as suggested by the reviewers, we provide an additional empirical study on the violation penalty $\mathcal{K}$.
The experiments are done on two tasks: HopperVel and Ant. We tested various values of $\mathcal{K}$ in both environments.

The results are available at https://imgur.com/a/Cqz2g93.

We observe that ARAM is rather insensitive to the choice of the violation penalty $\mathcal{K}$.


**Q3: Explain the multi-objective RL implementation of ARAM and why this design can obviate the need for the hyperparameter tuning of penalty weight $\lambda$ in training**

**A3:** We would like to clarify how ARAM leverages multi-objective SAC (MOSAC) during training. Specifically: 
* As MOSAC is designed to learn policies under all the penalty weights $\lambda=[\lambda_r, \lambda_c]$ (or also called “preference vector” in the MORL literature), its policy network and critic network are both penalty-weight-dependent, i.e., take the penalty weight as part of the network input. 
* During training, in each iteration, one or multiple $\lambda$ are randomly drawn from unit simplex based on a probability distribution $\rho_{\lambda}$ (e.g., uniform distribution as mentioned in Lines 352-354) for updating the policy and the critic, based on the loss functions $J_{\pi}(\phi;\lambda)$ and $J_{Q}(\theta;\lambda)$ (cf. Equations (4) and (5)). In this way, MOSAC can learn well-performing policies under all the penalty weights. 

Based on the above description, there are several key messages:
1. Under MOSAC, $\lambda$ is actually not a hyperparameter and hence no hyperparameter tuning for $\lambda$ is needed during training.
2. This explains why we propose a practical implementation of ARAM based on MOSAC, which obviates the need for hyperparameter tuning of $\lambda$ during training. This design can substantially save the cost of training samples, compared to the single-objective SAC implementation.
3. Therefore, the comparison of MOSAC-based ARAM and other ACRL baselines is indeed fair in terms of the environment steps used (as no hyperparameter tuning of $\lambda$ is needed for ARAM during training).
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents an interesting approach to action-constrained reinforcement learning (ACRL) by combining acceptance-rejection sampling and augmented MDPs. The authors have identified a crucial challenge in the field: the computational cost of solving quadratic programs, especially in high-dimensional action spaces. The paper is well-written and organized, providing a clear explanation of the methodology and supporting experiments. While the integration of acceptance-rejection and augmented MDPs appears somewhat contradictory, representing opposing ends of a "hard" vs. "soft" constraint handling spectrum, this novel combination is intriguing and shows promise.  However, the lack of a strong theoretical guarantee for constraint satisfaction within the augmented MDP framework is a significant concern, particularly for safety-critical applications.  Furthermore, the experiments primarily focus on lower-dimensional action spaces, leaving the method's effectiveness in high-dimensional settings, as initially motivated, somewhat uncertain. Despite these weaknesses, the paper's strengths, particularly its clear exposition of a novel approach to a relevant problem, and the well-presented, though limited, empirical results, outweigh the shortcomings.  The potential impact of this work, coupled with the clear need for further research to address the identified limitations, makes it a worthwhile contribution to the conference.  Therefore, I recommend accepting the paper.