Autoregressive Policy Optimization for Constrained Allocation Tasks

Thank you for the positive review and helpful comments. We are happy to address your questions below:

• W1: Please see our general response, where we address the theoretical guarantees in the form of a proof.
• W2: In theory, it is possible to learn the optimal policy regardless of the order as long as the policy is able to sample the complete action space. In practice, however, this might not be the case when the initialization of the policy does not uniformly sample over the action space, it might not be able to overcome this bias and converge early to a suboptimal policy because large allocations for later entities are not sufficiently explored. Instead of looking for the optimal order, we provide a de-biasing mechanism that mostly eliminates the impact of the order, which can be seen in our ablations (Figure 5b). There, we show that the order does not significantly impact the performance of our approach when using our de-biasing mechanism. We performed an additional experiment to also compare the impact of the order without using our de-biasing mechanism. This figure (which can be found in the PDF attached to our general response) shows that reversing the order without our de-biasing mechanisms does create a significant difference in performance.

Thank you for the positive review and helpful comments. We are happy to address your questions below:

• W1: Thank you for appreciating that we discussed this in our paper. Regarding the computational requirements, see also our response to reviewer QtCd question 1.
• W2: While several reviewers like the presentation and clarity of our paper, they noted that minor details were missing or unclear, which we address in our responses. We also added a proof to show that our approach guarantees constraint satisfaction (see our general response). Furthermore, our formulation of the problem as a CMDP with cost functions caused some confusion, since our approach does not require cost functions. We did this to show the relation to Safe RL and will clarify this in our paper (see also our response to reviewer 3hEE question 4). In case our response did not cover your concerns, could you please point us to more specific questions, we are happy to hear and address them in the discussion.
• W3: Please see our general response, where we address the theoretical guarantees in the form of a proof.

Thank you for the positive review and helpful comments. We are happy to address your questions below:

• W1: The novelty of our approach lies in utilizing the properties of the polytope to efficiently parameterize a stochastic policy over it in an autoregressive way that can be optimized using standard reinforcement learning algorithms like PPO. Additionally, we introduce a novel de-biasing mechanism. We are happy that the reviewer acknowledges the good results that our approach achieves.
• Q1: As discussed in the paper, our approach introduces some additional computational cost, since we are required to solve linear programs in our approach. Our approach does not have particularly demanding hardware requirements and can be trained on regular servers, PCs, or laptops. It is difficult to directly compare the runtimes because we trained on a cluster with various different servers and also ran multiple training runs in parallel, which impacted the duration of training. Therefore, we were hesitant to report exact numbers in the paper. Note that the runtime also depends on the number of constraints and dimensions of the action space and we did not optimize our implementation for runtime. For example, in our synthetic benchmark of dimensionality 7 and 150k environment steps, OptLayer took around 24h to train and our approach also took around 24h. In contrast to the other benchmark approaches, OptLayer can also guarantee constraint satisfaction. Approaches like IPO, CPO, etc, take around 10 minutes but do not guarantee constraint satisfaction at all times. Let us also note that we trained only on CPUs and used scipy to solve the linear programs. Note that works exist that utilize GPUs for solving linear programs (for example see [1]), which could be utilized to drastically speed up training.

[1] Spampinato, Daniele G., and Anne C. Elster. "Linear optimization on modern GPUs." 2009 IEEE International Symposium on Parallel & Distributed Processing. IEEE, 2009.

Thank you for the positive review and helpful comments. We are happy to address your questions. We try to be as detailed as possible given the 6k limit.

• W1/Q1: Please see our general response regarding the theoretical guarantees.
• W2: Thank you for the suggestion. To assist readers in understanding the overall flow of our approach, we will include a detailed algorithm and a visualization of the flow.
• W3: Sampling from the constrained simplex is not sufficient for RL. We need to define a stochastic policy over the polytope and update its parameters using a gradient in order to increase or decrease the probability of drawing these samples. Parameterizing such a differentiable distribution via rejection sampling is not straightforward. However, some algorithms use a related concept. They sample from a distribution over a superset, e.g., an unconstrained polytope, but instead of rejecting actions that fall outside the constrained polytope they project these onto the constrained polytope. OptLayer [18] is a prominent instance. However, action projections can lead to a biased policy gradient [15]. In contrast, our approach defines a stochastic policy only over the polytope and does not suffer from this problem. The experimental results also empirically demonstrate that we can outperform projection-based approaches like OptLayer.
• Q2: We use the synthetic benchmark without additional allocation constraints (i.e., only the simplex constraint) for our ablation. As in our main experiments, this environment is 7-dimensional. Since this was not sufficiently clear in the paper, we will add more details regarding the setting to the paper. We decided not to use additional allocation constraints because this makes the effect of de-biased initialization most pronounced since each constraint limits the possible allocations (e.g., if one is required to allocate at least 90% to one entity, there is not a lot of choice for the remaining allocations). Since the bias can occur regardless of the environment, we expect a similar performance in other environments.
• Q3: We will clarify this in the paper. To derive a considerably different allocation order, we reverse the allocation order. That means, instead of allocating to entity $e_1, \ldots, e_n$, we allocate in the order $e_n, \ldots, e_1$, i.e., we allocate the last entity first, the second last ($e_{n-1}$) second, and so on.
• Q4:

“do you impose any constraints as you describe in lines 135 and 133? [...]”

We apologize for the confusion. The last paragraph of section 3 is somewhat misplaced as it describes how the problem setting can be reformulated to apply methods from Safe RL. Thus, we will move this definition to the experiments. We do not use a cost function, instead we apply the constraints to the action space and our approach ensures that actions always comply with the constraints.

“objective of PPO?”

Our approach defines a differentiable stochastic policy function over the constrained action space and can be directly optimized using the standard objective of PPO.

• Q5: In our approach, each step depends on the outputs of all previous steps (cf. Figure 2 in the Appendix), similar to an autoregressive model. Hence, we use the word “autoregressive”.
• Q6: RL algorithms that are policy gradient based, require sampling actions from the current policy, i.e., a distribution which is parameterized by a neural network. However, directly defining such a distribution over a polytope is extremely difficult. In fact, even efficiently generating uniform samples from a polytope is a difficult problem subject to ongoing research [8]. Therefore, our approach decomposes the problem into dependent sub-problems. Because of this autoregressive dependency, we need to sample an action sequentially. Note that this decomposition and process allows for training using standard RL algorithms.
• Q7: We will add further details to the Appendix. In portfolio optimization the state space has 27 dimensions and the action space 13. In the computational workload distribution environment the state space has 18 dimensions and the action space 9. In our synthetic env, we have a discrete number of states, which are one-hot encoded. Our synthetic env uses a complex reward surface which is well suited to study the properties of various approaches, especially how well and fast approaches can optimize an arbitrary reward surface. Therefore, we do not want to focus too much on other properties of RL that are mostly orthogonal to our approach, such as delayed rewards, learning complex state representations, etc. As a result, we set the number of states to two and use a 7-dimensional action space.
• Q8: Our approach can be applied to all constrained RL tasks, where the action space is a convex polytope, as long as the constraints are explicitly given. However, since many people think of Safe RL in settings where the constraints are not explicitly given and typically only soft satisfaction is required, we decided to focus on allocation tasks. However, as shown in our problem definition, constrained allocation tasks can be defined within the framework of Safe RL and we discuss the relation to Safe RL in our related work.