Autoregressive Policy Optimization for Constrained Allocation Tasks
Authors: David Winkel
Niklas Alexander Strauß
Maximilian Bernhard
Zongyue Li
Thomas Seidl
Matthias Schubert
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
Constraint Reinforcement Learning
Allocation Tasks
Primary area: reinforcement_learning

Abstract: Allocation tasks represent a class of problems where a limited amount of resources must be allocated to a set of entities at each time step. Prominent examples of this task include portfolio optimization or distributing computational workloads across servers.
Allocation tasks are typically bound by linear constraints describing practical requirements that have to be strictly fulfilled at all times. In portfolio optimization, for example, investors may be obligated to allocate less than 30\% of the funds into a certain industrial sector in any investment period. 
Such constraints restrict the action space of allowed allocations in intricate ways, which makes learning a policy that avoids constraint violations difficult.
In this paper, we propose a new method for constrained allocation tasks based on an autoregressive process to sequentially sample allocations for each entity. In addition, we introduce a novel de-biasing mechanism to counter the initial bias caused by sequential sampling. We demonstrate the superior performance of our approach compared to a variety of Constrained Reinforcement Learning (CRL) methods on three distinct constrained allocation tasks: portfolio optimization, computational workload distribution, and a synthetic allocation benchmark. Our code is available at: https://github.com/niklasdbs/paspo

Autoregressive Policy Optimization for Constrained Allocation Tasks
David Winkel" Niklas Strauß"
Maximilian Bernhard Zongyue Li
Thomas Seidl Matthias Schubert
Munich Center for Machine Learning, LMU Munich
(tinkel,strauss, strauss, bernhard, 1i, seidl, schubert) ifi 1mu de
Abstract
Allocation tasks represent class of problems where a limited amount of resources must be allocated to set entities at each time step. Prominent examples this task include portfolio optimization distributing computational workloads across servers. Allocation tasks are typically bound by linear constraints describing practical requirements that have to be strictly fulfilled at all times. In portfolio optimization, for example, investors may be obligated to allocate less than 30% the funds into certain industrial sector in any investment period. Such constraints restrict the action space of allowed allocations learning policy that avoids constraint violations difficult. In this paper, propose a new method for constrained allocation tasks based on an autoregressive process sequentially sample allocations for each entity. In addition, de-biasing mechanism to counter the initial bias caused by sequential sampling. We demonstrate the superior performance of our approach compared variety Constrained Reinforcement Learning (CRL) methods on three distinct constrained allocation tasks: portfolio optimization, computational workload distribution, and synthetic allocation benchmark. Our code is available at: https: / thub. com/ hsklaadbs/ppspo
intricate ways, which makes
introduce novel
Introduction
Continuous allocation tasks class of problems where agent needs to distribute a limited amount of resources over a set of entities at each time step. Many complex real-world problems are formulated as allocation tasks, and state-of th-the-rrt solutions rely on using Reinforcement Learning (RL) to learn
effective policies (6, 26 20 27]. Notable examples include portfolio allocation tasks, where portfolio managers must allocate the available financial resources among various assets [27]. or allocation tasks of computational workloads to a set of compute instances in data centers B In many
cases, allocation tasks come with allocation constraints 6 20 27 26 such as investing at most 30 % of the portfolio into a specific subset of the assets or to restrict the maximum workload to certain servers a data center. Formally, allocation constraints are expressed as linear constraints and form system of linear inequalities, geometrically describing convex polytope. Each point in this polytope describes a possible allocation and each dimension corresponds to one of the entities. Allocation tasks often require hard constraints, i.e., constraints that are explicitly given and must be satisfied at any point in time. However, most of the existing CRL literature focuses on soft constraints that not explicitly given (2) 29 31 14 25 These approaches typically cannot guarantee constraint satisfaction and tend to have many constraint violations during training. The majority of these methods approximate the cumulative costs of constraint violations and optimize the cumulative reward while trying to adhere to the maximum cumulative costs. While less explored, there exist
Both authors contributed equally.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

10 20]. These approaches might generate actions that do not satisfy the constraints but utilize correction mechanism to map the actions back into the valid action space. In addition, most of these approaches are restricted to off-policy algorithms [1 20) In another line of research, solutions tailored for constrained allocation
several techniques that ensure the satisfaction of hard constraints [T8 6
tasks have been proposed (27 28]. However, these solutions are severely limited since they can only handle a specific subset of linear constraints and cannot handle more than two.
In this paper, we propose Polytope Action Space Policy Optimization (PASPO), a novel RL-based method that, firstly, decomposes the action space into several dependent sub-problems and, secondly, autoregressively computes the allocations step-by-ste for each entity individually. In contrast to previous methods for hard constraints, we directly generate an action within the action space. This makes the correction of invalid actions unnecessary and, thus, avoids potential sampling bias introduced by the correction. Our new decomposition approach implemented in a neural network- based policy function, which can be employed in on-policy and off-policy RI. algorithms. We show that initialization bias can prevent proper exploration in early training which leads to premature convergence. Thus, we propose a de-biasing mechanism to stabilize exploration in early training stages.
We evaluate our approach against various baselines on three distinct allocation tasks: portfolio optimization, distributing computational workload in data centers, and synthetic benchmark. These experiments demonstrate that our approach can outperform existing methods consistently and show the importance of the proposed de-biasing mechanism.
To summarize, the main contributions of our paper are:
A new autoregressive stochastic policy function applicable to arbitrary convex polytope action spaces of constrained allocation tasks.
A new de-biasing mechanism to prevent premature convergence a sub-optimal policy.
An empirical evaluation that optimizes our new policy function using PPO [2] and demon- strates improved results compared to state-of-the-arr CRL methods.
The remainder of the paper is structured as follows: In Section 2 we provide an overview of the related work in CRL, constrained allocation tasks, and autoregressive policy functions. Afterward, we formalize constrained allocation tasks in Section 3 and present our novel approach in Section 4
Section dedscribes the results of our experimental evaluation, Section brieffly discusses limitations and future work before Section 7 concludes the paper.
2 Related Work
Resource allocation tasks are widely researched area with numerous applications spanning logistics, power distribution, computational load balancing, security screening, and finance 16 26 3 20 27). We identify three key research directions that are particularly important when discussing resource allocation tasks.
Safe Reinforcement Learning The majority of work in CRL addresses soft constraints, a setting often referred to as Safe RL. We will provide a brief overview of the most important methods in this field, For a more comprehensive examination of Safe RL, we direct readers to the survey papers by
15 12]. A common technique in Safe RL is the use of Lagrangian relaxation 15). Several works employ primal-dual optimization to leverage the Lagrangian duality, including 23 Another frequently used approach involves different penalty terms (2 14 31. The authors of IPO [14
propose to use logarithmic barrier functions. CPO [2] extends TRPO [21 to ensure coar-constraint satisfaction with each update. Additionally, two-step approaches such as FOCOPS (32) and CUP (30
are popular in the field. However, unlike our method, these approaches do not guarantee strict
constraint satisfaction, particularly during training.
Hard Constraints Although less studied than Safe RL, several works address hard instantaneous constraints on actions to ensure full constraint satisfaction at any time step. Most of these approaches employ mechanisms to correct infeasible actions, i.e., those that violate constraints, into feasible In contrast, our method always generates feasible actions without the need
actions 18 6 20
for correction. Optl [18 is one of the most prominent examples in this field, which employs
OptNet [5] to map infeasible actions to the nearest feasible action. Similarly, 200] propose more

---

efficient projection on the polytope action space than OptLayer. The authors of [6] focus on resource allocation with hierarchical allocation constraints by proposing a faster upproximate version of Optl.ayer. In [1] the authors propose an off- pooiccy algorithm based on the generalized reduced gradient method to handle non-linear hard constraints by projecting infeasible actions. In contrast, our method is not limited to off-policy algorithms.
In [27 28), the action space is decomposed into independent subspaces. However, these approaches can only handle up to two allocation constraints. Furthermore, they are only applicable to binary allocation constraints. contrast, our approach can handle an arbitrary number of constraints as well as any type of linear allocation constraints.
Action Space Peccopposition/aaattziztt
factorization of multi- dimensional action spaces has been examined in several works [24 16 19 notable example is 24] in which the authors discretize continuous action space into several independent action branches, each parameterized by individual network branches. In [6], variant of DQN [17] that discretizes a continuous action space into multiple discrete dimensions is proposed. These dimensions are sequentially parameterized, conditional on the previous sub-actions, Similarly, [19] propose an autoregressive factorization of an unconstrained action space into dependent sub-problems. Unlike our approach, these methods focus either on decomposing continuous action spaces into discrete action spaces or decomposing unconstrained action spaces. However, the decomposition of arbitrary convex polytope action spaces into tractable sub-action spaces remains a non- non-trivial challenge that our approach addresses.
The decomposition
3 Problem Description
An allocation task can be described as a finite-horizon Markov decision process (MDP) (S, A, R, 7). where S represents the state space, A the action space, T' AxAxS - [0, 1] the state transition function, R the reward function, and E [0, 1] a discount factor. The goal of this task is to find a policy æ maximizing the expected cumulative reward JR = E, En= ? (5t, π (8:), 8(42)].
The action a is an allocation a = {a....., a, E A over a set of n entities = fei.....e, en) at each time step. Each element a; of the action vector a represents the proportion allocated entity ej. Furthermore, allocation tasks require a complete allocation, i. e., Σ ag = and allocations cannot be negative (a; 2 0). Thus, the action space of unconstrained allocation tasks forms n-dimensional standard simplex. A visualization of an unconstrained allocation action space is provided in Figure Ta
Allocation tasks frequently include constraints, such as allocating at most 30% to subset of the entities. An example of a constrained action space is visualized in Figure [b] Formally, an allocation constraint can be expressed as linear inequality Σ Gaa S b, where denotes the weighting of the allocation variable a, of entity e, and b E IR denotes the corresponding constraint limit. For the only define constraints since -a I -b and a = b can be rewritten as a S b and -a < -b.
sake of readability and simplicity,
can be transformed into
The action space A of constrained allocation tasks can be easily expressed by set of linear inequali- ties, defining polytope = {a E [0, 1|a[Ca $ b}. where
Ci
Cin
CER
Cml
Cmn
is matrix of coefficients for the m constraints, including those linked to the simplex constraints Er a, 1 and a; 2 Vi E [1....n). n),, as well as all coefficients for additional allocation constraints. Let a E [0, 1J" represent an allocation vector and b E Rm is the vector of constraint limits.
Alternatively, constrained allocation tasks can be defined using the framework of constrained Markov decision processes (CMDPs). CMDP extends the standard MDP by a number of cost functions to incorporate the constraints. The goal is to maximize the expected cumulative reward while satisfying m constraints on the expected cumulative costs. The expected cumulative costs for the k-th cost function CF3 are defined as J to be satisfied in the CMDP are then stated as JCF. S dR. where dy denotes the cost limit with
"CFF at)]. The m constraints
3

---

2.5
0.5
8 0.6
0.5
2.4
0.4
0.3
0.7
0.4
0.6
0.4
0.
(a) Unconstrained standard simplex
(b) Constrained simplex with as S 0.6 and a2 S 0.7
Figure 1: Examples of 3-dimensional allocation action spaces (a) unconstrained and (b) constrained
(valid solutions as red area).
k (1.....m) To formulate constrained allocation tasks using CMDPs, the cost functions be defined as C.F (s, a) max(0, (Ca),: J: by] to measure any allocation constraint violation as a cost. In addition, strict adherence all allocation constraints at any point in time is required, i.e., de O. By formulating constraint allocation tasks using CMDPs, becomes possible to use existing methods from Safe RL for soft constraints. However, these methods cannot guarantee constraint satisfaction all times 15 Let us note that our method does not use cost functions, instead it samples actions directly from the constrained action space.
4 Polytope Action Space Policy Optimization (PASPO)
Our approach PASPO autoregressively computes the allocation to every single entity in an iterative process until all allocations are fixed. We will later show that this step-wise decomposition allows for a tractable parametrization of the action space.
4.1 Autoregressive Polytope Decomposition
PASPO starts by determining the feasible interval [arinn aamaajj for allocations into the first entity 61- Then, we sample the first allocation a1 from this interval. The details of the sampling process will be further discussed in Section 4.2] Fixing allocation impacts the shape of the remaining action space. Thus, have to compute the shape of the polytope A described by (2) and 6(2) before we sample the next allocation a2-
Each iteration starts with determining the interval Jamin amazz] of all feasible values for ag. Ge- ometrically, this interval is bounded by the minimum and the maximum value of the remaining polytope ( in the i-th dimension associated with the allocation og To determine amiin we solve the following linear program:
minimize
04
(())
< ((0)
s.t. where (1) are the constraint coefficients for the entities Ci....,Ca. ((0) are the adjusted constraint limits, and (+) describes the unfixed allocations. We determine mma by solving the respective
maximization problem. For the first iteration 1, we define C() = C, 50) = b and a()) =
After sampling an allocation a; from the interval (am a.ma]] The resulting polytope (++1) for the next iteration 1 is described by the following inequality system:
C1,+11
C1,1
a++1
b
(i)
C1,i
<
a
(2)
Cm,i+1
Cm.n
On
b
Cmn,
(64+1
a(
60++3
To define the new coefficient matrix ((++) (red), we remove the first column of the coefficient matrix of the previous iteration (1)), To calculate the new vector g(++1) of constraint limits, we subtract

---

0.8
0.5
0..0
0.6
0.6
0.6
0.4
0
0.2
0.7 0.1
0.7
0.1
08
08
(a) Original set of valid solutions,
(b) Remaining valid solutions
Only a single valid solution remains in A (red dot) after = 0.3 and d2 0.5 (dashed bluc lines) fixed, i.c., sampled
Le.. A (red area)
A (red line) after = 0.3 (dashed blue line) was fixed, i.c., sampled
Figure 2: Example of sampling process of an action a (01, 02 a3) in 3-dimensional constrained allocation task.
the removed column (blue) scaled by the fixed allocation a; from the previous constraint limits (() (yellow). We iterate over all entities until determine On-1- Allocation o,, already determined as soon as the allocations 01,-... On-1 are fixed because of the simplex constraint Σ (4 = 1. Sampling an allocation using this approach always guarantees constraint satisfaction and is possible to sample any action in the constrained action space. A formal proof of these guarantees can be found in Appendix [
Figure 2 displays visualization of the process for a 3-dimensional case. The set of valid solutions before any allocations have been fixed is shown in Figure 2a Figure 22 depicts the first iteration after 0.3 has been determined, and the resulting shrinks to the red line is shown. Figure 2c shows the second iteration after also 02 = 0.5 has been determined. can seen that the new polytope A contains only single valid solution represented as red dot, making a third iteration unnecessary since the only remaining solution is to allocate 43 = 0.2, resulting in a final allocation = (0.3, 0.5, 0.2).
polytope A i.e., set of valid solutions,
4.2 Parameterizable Policy Process
Our goal is to define a learnable stochastic policy function over the action space. For unconstrained allocation tasks, Dirichlet distribution can be used to parameterize the action space 266 28 Unfor- tunately, to the best of our knowledge, there is no known parameterizable, closed-form distribution function over arbitrary convex polytopes in our setting. In fact, even uniform sampling over convex polytope is an active research problem g
We sequentially constructed action from the polytope action space A in the previous section. Now, we describe how to utilize this process to define a parameterizable policy function over the action space A. We model the distribution for allocating each individual entity using beta distribution that normalized to the range (a? mmzz) J. This distribution is also known as the four-parameter beta distribution 7 Its probability density function is defined as:
(x - a (a - -x))))) 2:)0-1
p(æ; a. B, min amaa))
(amaaz
where B(a, (3 is the beta function. It important to note that any other parameterizable distributions with bounded support in the range [agtin a maazz can be used, such as squashed Gaussian distribution. However, our preliminary experiments indicated that the beta distribution performs particularly well.
To optimize the policy To(s) over the complete allocations, we follow the approach of [19 for training an autoregressively dependent series sub- aub-policies. fixed but arbitrary order of entities used for sampling the allocations o; The sub- sub-policy т (a; a1...........................a a;-1) is conditional on the previous allocations d1 (4 Using this autoregressive dependence structure, the policy defined as:
(o(als) TH (a (s) (#2)),, (1),..... T (a,,** 18, .1...., (n-1)) 1). This policy can be jointly optimized. We parameterize each sub-policy using a neural network that receives an embedding of the state and the previously selected actions as input.
5

---

(a) Mean allocations 0;
(b) Uniform sampling
(c) Our initialization
Figure 3: The impact of initialization in an unconstrained simplex. (a) Mean allocations a, each entity in seven entity setup when sampling each individual allocation using the uniform distribution (red) vs. our initialization (blue). (b.c) Distribution 2500 allocations in three entity setup when sampling each individual allocation uniformly (b) or using beta distributions with parameters set according to our initialization (c).
Algorithm 1 Maximum likelihood estimation of parameter de-biasing terms
Input: Polytope = {a E |Ca < 6}, number of samples k
Output: Beta distribution shape parameters å,, Br as de-biasing terms
Let (1)) for j (1,..... [......,k)
2: Sample allocations {(())) k...k uniformly within A via rejection sampling
3: for each dimension in [1..... do
4: for each sample j in (1.....k k do
mar using LP based on AA 5: Calculate interval [a])) "G)
G133i men "5)
6:
Normalize sampled allocation to support [0.1] of beta distribution:
norm ())
(()4
7: Compute polytope Al from 4 using sampled allocation a(j)i (see Eq.
2
8: end for
9: ML estimation of beta distribution parameters ai, 9 using (anorn jj=1...k
10: end for
An entropy term is often used to encourage exploration. However, our policy does not have closed-form solution for entropy. Therefore, we follow [9
empirically estimate the entropy:
Hemp (-Is)) = Ea
Σ
H (1s............
Here, denotes the entropy of the beta distribution. We compute the expectation within each training batch to estimate the entropy of the complete policy function over the entropies of single actions. Let us note that when using an off-policy algorithm, the actions must be resampled using the current policy. As the current policy might have a significantly different parametrization than the sampling policy, we have generate actions based on the current policy to estimate the entropy properly.
4.3 Policy Network Architecture
We create an embedding of the state using an MLP, denoted as fa(s) = MLP(s). We pa- rameterize the probability distribution MLP((f(s)) 01,-.., a,-1), which receives the latent encoding of the state and the previously pled allocations d1,... a;-1 as input. Note that each of the MLPs oi has its own parameters. For further details, we refer to the Appendix.
allocations for each entity using MI. = (s)
4.4 De-biasing Mechanism
drawhack of generating actions by an autoregressive process that random initialization of the beta distributions leads to sampling bias towards the entities selected earlier in the process. The

---

effect is caused by the autoregressive dependency structure of our process. To sample an allocation of 80% for entity a, the cumulated fixed allocations for earlier entities Σj=1 d, must be at most 20%. However, this is rather unlikely if we initialize the distribution for all entities in similar way. This effect can be observed in the red bars of Figure 3a The red bars correspond to the average allocation for each dimension when uniformly drawing from unconstrained ceven-dimensional simplex with our autoregressive process for each entity 6,- As expected, the mean for the first dimension is 0.5, which is the mean of uniform distribution over the interval [0, 1]. Correspondingly, the mean is decreased by half for any successive further entity until entity 6, which has the same mean as entity 7 due to the simplex constraint. Even though the bias is more complex for constrained allocation spaces, a similar effect can be expected.
For policy gradient methods, such bias in the initialization of the policy function can lead to convergence to poorly performing policies or long training times. As the initial policy is crucial for ensuring sufficient exploration of the state-action space, a biased initial distribution leads to underexplored regions in the state-action space. Consequently, well-performing actions might not be discovered. To counter this effect, we propose de-biasing mechanism that adjusts the initial parameters of beta distributions to estimate a uniform sampling over the joint action space. During learning, the amount of required exploration decreases, and the parameters of the policy function are optimized to increase the cumulative rewards. Thus, the impact of our de-biasing mechanism should diminish over time. We achieve this effect by adding de-biasing term to the linear layers' initial bias terms, predicting a; and B3 for entity i. As the default initialization of the bias terms has zero means, the first iterations use and /3 values close the de-biasing terms.
To determine suitable initial values for each iteration step, we proceed as described in Algorithm [] We start by uniformly sampling data points from the complete action space A. We do this by rejection sampling, i.e., we sample over the standard simplex and reject the samples outside the action polytope A. To determine the parameters corresponding to the acquired uniform sample, we project any allocation for each entity to a standard interval between [0, 1]. However, for this step, we have to determine the interval [am-in a["aa] for each entity following the above process. We determine the relative position in this interval, corresponding to the position in the named standard interval. After collecting relative values for each sample and entity, employ the standard maximum likelihood estimator to generate an empirical estimate of the a; and 3g for each entity e,. The blue bars in Figure 3a correspond to the results the unconstrained ceven-dimensional unconstrained simplex. Figure 3b shows autoregressive sampling based on uniform distribution, whereas Figure [3c displays the result of our initialization for thnee-dimensional example. It can be seen that the result of our initialization of the autoregressive process closely resembles a uniform distribution over the complete action space.
5 Experiments
In this section, we provide an extensive experimental evaluation of our approach in various scenarios demonstrating its ability to handle various allocation tasks and constraints. We use two real- world tasks: Portfolio optimization [27] and compute load distribution B. Additionally, we create a synthetic benchmark with reward surface generated by randomly initialized MLP. Each of these tasks comes with a different set of allocation constraints. We will briefly describe each setting in the following and refer the reader to the Appendix for more details.
Portfolio Optimization Portfolio optimization is a prominent constrained allocation task. In this task the agent has to allocate its wealth over 13 assets at each time step. We use the environment of [27]. Each investment period contains 12 months and the investor needs to reallocate the portfolio each month. This environment is highly stochastic since each trajectory is sampled from a hidden Markov model fitted on real-world NASDAQ- 100 data. After every 5120 environment steps, we run eight parallel evaluations on 200 fixed trajectories. Constraints in this setting define minimum and maximum allocation to groups of assets. Additionally, we add constraints where the constraint coefficients in C' correspond to portfolio measures like minimum dividend yield or maximum the CO2 intensity.
Compute I Load Distribution The environment is based on the paper of 3 and simulates data center in which computational jobs need to split into sub-jobs to enable parallel processing across nine servers. Here, we use five constraints that are randomly sampled as follows: First, sample
7

---

Ours
OptLayer
Lagrange
P30
IPO
CPO
CUP
14:0
16.00
1222
12.15
0.00
20006
Aeerovvent staps
servoc stegs
2002
1602
140
1583
2080
40000 (800002200211000
Tinenga
Timestez
Tireless
(a) Synthetic Benchmark
(b) Portfolio Optimization
(c) Compute Load Distribution
Figure 4: Learning curves of all methods in three environments. The x-axis corresponds to the number of environment steps. The y-axis is the average episode reward (first row), and the number of constraint violations during every epoch (second row). For portfolio optimization (b) we report the performance running eight evaluation on 200 fixed market trajectories. This is because in training, every trajectory is different which makes comparisons hard. Curves smoothed for visualization.
the number of affected entities for each constraint. We then sample the constraint coefficients from the range [0, 1].
Synthetic Environment In addition to the aforementioned environments, we propose a synthetic benchmark. The reward surface consists of MLP with random weights. Each episode compromises two states. As it is completely deterministic, it provides simple yet effective way to benchmark approaches for constrained allocation tasks. In this setting, we create the constraints by randomly sampling 30 points and their convex hull as the polytope defining the action space. We utilize seven-dimensional setting with 611 constraints in our experiments.
5.1 Experimental Setup
We train PASPO using PPO 22 and compare approach various baselines, including state-of- the-art approaches for constrained allocation tasks and Safe RL. Specifically, we compare PASPO with five representative approaches from Safe RL: CPO 2]. CUP (30] IPO 14, P3O 31 and PPO with Lagrangian relaxation. Additionally, we compare our method to OptLayer [8]. a popular projection-based method for linear hard constraints. To maintain consistent and fair comparison across different methods, we use the same hyperparameters across the different methods if possible. Many Safe RI. approaches have difficulties handling equality constraints (11). Therefore, a Dirichlet distribution to represent the policy in the baselines, thereby ensuring satisfaction of the simplex equality constraint. We do not share the parameters between the policy and value function. We use a fully-connected MLP with two hidden layers of 32 units and ReLU non-linearities for each policy, cost, and value function. In our approach, the state encoder and each policy head consists of two-layer MLP. The training process is run for 150,000 steps and the results are averaged over five different seeds. In the portfolio optimization task, we use different seeds due the stochasticity of the financial environment and train for 250,000 steps. Given the relatively small network sizes, training conducted exclusively on CPUs. We implement our algorithm and the baselines using RLlib and Py Torch. More details regarding the environments, training, and hyperparameters can be found in the Appendix.
5.1.1 Performance of PASPO
We visualize the performance and constraint violations of all methods across our three environments in Figure 4 tolerance of 1e-3 used for evaluating constraint violations and we report the total number of violations per episode. In all three environments, PASPO converges faster to higher

---

15.5
15.5
Latoode Neward ittem
15.0
Ealcodo Roward Maan
14.5
10.0
13.5
13.0
13.0
12.5
12.5
5000
10000
15000
5000
10000
15000
20000
Environment Steps
Steps
Figure 5: Ablations in (a) show the performance of our approach with (blue) and without (orange) the de-biased initialization. In (b) depicts the impact of the allocation order. We reverse the allocation
order (red).
average return compared to baselines. Additionally, while all compared soft-constraint methods display constraint violations, only the hard constraint approaches PASPO and OptLayer guarantee to permanently satisfy the constraints. Finally, we can observe that the variance of PASPO is rather low compared to other methods. However, in portfolio optimization task (b) our approach displays some variance which we attribute to the stochasticity the environment. Overall, these results demonstrate that our approach is only able consistently outperform other algorithms terms of rewards but also guarantees no constraint violations.
5.1.2 Importance of de-biased Initialization and Order
We conduct ablation studies investigate the impact of our de-biased initialization and the order of entity allocation on our synthetic benchmark. No constraints are applied except for the simplex constraint highlight the effects. The results, shown in Figure S indicate that without de- de-biased initialization (orange in (a)), learning is slower and converges prematurely to sub-optimal policy. In (b), we explore the impact of allocation order by reversing (red) and observe no significant performance difference. This indicates that our approach is robust to the allocation order due to the use of the de-biasing initialization.
Limitations and Future Work
While PASPO guarantees that constraints are always satisfied, it is considerably more computationally expensive than standard neural networks allocation tasks with many entities, as the sampling of each action requires solving series of linear programs. RL in high-dimensional continuous action spaces is a very challenging task. Our approach cannot overcome this issue and also struggles in very high- ditheemnnniinal settings. For future work, plan extend PASPO also incorporate state- dependent constraints. While we evaluate our approach only on benchmarks with hard constraints, it can be applied to settings with both hard and soft cumulative constraints. In these scenarios. method for handling hard constraints can be casily combined with most Safe RL algorithms to handle soft cumulative constraints.
7 Conclusion
In this paper, we examine allocation tasks where a certain amount of resource has to be distributed over set of entities at every step. This problem has many applications like logistics tasks, portfolio management, and computational workload processing in distributed environments. In all these applications, the these restrict the action space to convex polytope. To define stochastic policy function that can be used with policy gradient methods in RL, we propose an autoregressive process that computes allocation sequentially. We employ linear programming to compute the range of feasible allocations for an entity given the already fixed allocations sequence of one-dimensional beta distributions where the shape parameters and B are learned by neural networks. To counter the effect of initialization bias, we utilize de-biasing mechanism to ensure sufficient exploration and prevent premature convergence to sub-optimal policy. In our
feasible allocations might be bound by set of linear constraints. Formally,
other entities. Our policy function consists of

---

experiments, we demonstrate that our novel method PASPO yields better results than tar approaches while not having any constraint violations. Furthermore, we show that our initialization method yields better results than random initializations and counters the impact of the allocation order.
10

---

References
[1] Abadie. Generalization of the wolfe reduced gradient method to the case nonlinear constraints. Optimization, pages 37-47, 1969.
[2] Achiam, D. Held, A. Tamar. and P. Abbeel. Constrained policy optimization. International conference on machine learning, pages 22-31. PMLR, 2017.
[3] L. Ale, S. A. King, N. Zhang, A. R. Sattar, and J. Skandaraniyam. D3pg: Dirichlet ddpg for task partitioning and offloading with constrained hybrid action space in mobile-edge computing. IEEE Internet Things Journal, 9(19:11260011277 2022.
[4] E. Altman, Constrained Markov Decision Processes, volume 7. CRC Press, 1999.
[5] B. Amos and J. Z. Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[6] A. Bhatia, P. Varakantham, and A. Kumar. Resource constrained deep reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 610-620, 2019.
[7] J. Camahann Maximum likelihood estimation for the 4-parameter beta distribution. Communi- cations in Statistics- and Computation, 18(2):513-536, 1989.
[8] Y. Chen, R. Dwivedi, M. J. Wainwright, and B. Yu. Fast meme sampling algorithms on polytopes. Journal of Machine Learning Research, 19(55)1-86, 2018.
[9] Y. Chow, M. Ghavamzadeh, L., Janson, and M. Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(167):-51, 2018.
[10] G. Dalal, K. Dvijotham, M. Vecerik, T. Hester, C. Paduraru, and Y. Tassa. Safe exploration in continuous action spaces. arXiv preprint 1rXiv:1801.08753 2018.
2018.
[11] S. Ding, J. Wang, Y. Du, and Y. Shi. Reduced policy optimization for continuous control with hard constraints. Advances in Neural Information Processing Systems, 36, 2024.
[12] Gu, L. Yang, Y. Du, G. Chen, Walter, Wang, Y. Yang, and A. Knoll. A review of safe reinforcement learning: Methods, theory and applications. arXiv preprint arXiv:2205. 10330. 2022.
[13] Q Liang, F. Que, and E. Modiano. Accelerated primal-dual policy optimization for safe reinforcement learning, arXiv preprint arXiv:1802.064480 2018.
[14] Y. Liu, J. Ding, and X. Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 4940-49444 2020.
[15] Y. Liu, A. Halev, and X. Liu. Policy learning with constraints in model-free reinforcement learning: A survey. The 30th international joint conference on artificial intelligence (ijcai), 2021.
[16] L. Metz, J. Ibarz, N. Jaitly, and J. Davidson. Discrete sequential prediction of continuous actions for deep rl. arXiv preprint
2017.
[17] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 131.v:13/2.5602 2013.
[18) T.-H. Pham, G. De Magistris, and R. Tachibana. Optlayer- for deep reinforcement learning in the real world. In 2018 IEEE International Conference Robotics and Automation (ICRA), pages 6236-6243. IEFF, 2018.
constrained optimization
[19] T. PIERROT, V. Macé, J.B. Sevestre, L. Monier, A. Laterre, N. Perrin, K. Beguir, and O. Sigaud. Factored action spaces deep reinforcement learning, 2021. httts::tt/://:eeereee met//orrumrddnnnsAAnn2222..

---

[20] S. Sanket, A. Sinha, P. Varakantham, P. Andrew, and M. Tambe. Solving online threat screening games using constrained action space reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages
2020.
[21] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[22] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: seee::707700433 2017.
[23] A. Stooke, J. Achiam, and P. Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference Machine Learning, pages 9133-9143. PMLR, 2020.
[24] A. Tavakoli, F. Pardo, and P. Kormushev. Action branching architectures for deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[25] C. Tessler, D. J. Mankowitz, and S. Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2018.
[26] Y. Tian, M. Han, C. Kulkarni, and O. Fink. A prescriptive dirichlet power allocation policy with deep reinforcement learning. Reliability Engineering & System Safety, 224: 108529, 2022.
[27] D. Winkel, N. StrauB, M. Schubert, Y. Ma, and T. Seidl. Constrained portfolio management using action space decomposition for reinforcement learning. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 373-385. Springer, 2023.
[28] D. Winkel, N. StrauB, M. Schubert, and T. Seidl. Simplex decomposition for portfolio allo- cation constraints in reinforcement learning. In K. Gal, A. Nowé, G. J. Nalepa, R. Fairstein, and Radulescu, editors, ECAI 2023 26th European Conference on Artificial Intelligence, September 30 October 4, 2023, Kraków, Poland Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023), volume 372 of Frontiers Artificial Intelli- gence and Applications, pages 2662. IOS Press, 2023. doi: 10.3233/FA1A230573. URL https: org 10.g/11..0 3233/FAI4230579
[29] L. Yang, J. Ji, J. Dai, I.. Zhang, B. Zhou, P. Li, Y. Yang, and G. Pan. Constrained update projection approach safe policy optimization. Advances in Neural Information Processing Systems, 35:91 11011119999 11-9124, 2022.
[30] I.. Yang, J. J. Dai, Y. Zhang, P. Li, and G. Pan. Cup: A conservative update policy algorithm for safe reinforcement learning. arXiv preprint arXiv:200.007565, 2022.
[31] L. Zhang, L. Shen, L.. Yang, S. Chen, X. Wang, B. Yuan, and D. Tao. Penalized proximal policy optimization for safe reinforcement learning. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3744-3750, 2022.
[32] Y. Zhang, Q Vuong, and K. Ross. First order constrained optimization in policy space. Advances in Neural Information Processing Systems, 13:15338-15349 2020.
A Environments
The implementation for all three environments can be found at: httpp::/giithu..com/niik
paspo
A.1 Financial Environment
The financial environment used for testing our approach is based on (28). The financial market trajectories in this environment are sampled from hidden Markov model, which was fitted based on real-world NASDAQ- 100 data from January 3rd, 2011 to December 1st, 2021. The environment offers differently sized data sets of randomly selected assets contained in the NASDAQ-100 The experiments in the financial environment for this paper run with 13 assets, which corresponds to
12

---

the model parameter data set set_G G marrkvv_steaee Sttttssttt_____t 2 12 data set with the include niclude_cash asset=true option. We initialize the enviromment with seed=2.
Table shows a list of the assets used in the experiments.
For the experiments random combination of two types of constraints typical for financial tasks is used: (a) a randomly selected subset of assets to either stay above or below an randomly selected allocation threshold and (b) thresholds for financial environmental portfolio measures that can be calculated as an weighted average the assets' individual measures, i.e., as weighted linear combination. A list of these measure can be found in Table
The experiments include constraints, of which the number constraints type (a) and type (b) is randomly decided. The exact implementation can be found in our code ate tie_random_ fin fin__eve_______________e__ Lev taav__olytope_eeeeeeee sappeeeriooossaappinnneee We use the seed 2 to generate the constraints.
(gener-
Index
ISIN
Ticker
Name
CASH
CASH
2
US5949181045
MSFT
Microsoft Corporation
3
US0567521085
BIDU
Baidu Inc.
4
US00724F1012
ADBE
Adobe Inc.
5
US6937181088
PCAR
Paccar Inc.
6
LS67066G1140
NVDA
NVIDIA Corporation
7
US8552441094
SBUX
Starbucks Corporation
8
US4612021034
INTU
Intuit Inc.
9
US0530151036
ADP
Automatic Data Processing Inc.
10
US0231351066
AMZN
Amazon.com Inc.
11
US2786421030
EBAY
eBay Inc.
12
US031162100
AMGN
Amgen Inc.
13
US7475251036
QCOM
Qualcomm Inc.
Table I: List of assets used in the environment.
Est. Total CO2 Equivalent Emissions To EVIC USD in million
Est. Total
Est. Weighted Average Cost of Capital, (%)
Energy Use To EVIC USD in million
Est. Dividend yield, (%)
Est. Return On Equity, (%)
CASH
0.00
0.00
0.00
0.00
0.00
MSFT
23.49
1.75
8.19
1.89
40.15
BIDU
70.80
15.17
7.12
0.00
9.01
ADBE
12.98
1.12
6.81
2.28
92.49
PCAR
83.66
10.27
7.31
3.14
-43.29
NVDA
17.17
1.58
6.20
3.00
127.85
SBUX
85.73
6.79
7.24
1.13
26.61
INTU
41.23
17.15
7.87
0.00
21.50
ADP
1.70
0.15
8.12
0.56
22.46
AMZN
4.69
0.39
8.28
0.00
44.48
EBAY
3.49
0.30
9.35
0.02
80.24
AMGN
33.87
3.29
7.09
0.73
37.76
QCOM
47.07
4.09
8.33
2.16
36.06
Table KPI estimates for assets based on 2021 (final year the used data set, source: Refinitiv);
EVIC Enterprise value including Cash
13

---

A.2 Compute Environment
The compute environment used for testing our approach is based on [ The agent's task to allocate compute jobs to a given set of servers in a data center. A reward is triggered for each job that was completed predetermined maximum allowed computation time. The challenge of this environment is that the agent needs to match the queue of jobs still to be allocated with the different computational capabilities of the servers as well each server's individual queue of jobs still to be computed. It is assumed that the compute jobs in the environment can be arbitrarily split and computed in parallel. The creation of new compute jobs is triggered by n users and follows a Poisson process. A job is defined by its payload size, i.c., the data be transferred to server, its required CPU cycles for the processing workload, and its maximum allowed time until the job needs to be completely processed. These attributes for the jobs that can be created by each user are randomly sampled at creation of the environment.
The experiments in this paper run with setup of 9 servers and 9 users that generate compute jobs. The parameter set used is parameter_ __se______________ 9__ 9_9_id_ O. We initialize the environment with seed= The randomly sampled specifications for the nine servers can be found in Table 3 and the job attributes created by the nine users can be found in Table
To generate the constraints, we first sample the number of affected entities between and 8 for each constraint and randomly choose the affected entities accordingly. We then uniformly sample constraint coefficients from the interval [O, 1]. as well as corresponding constraint limit between O and 1. We use seed of 1 to generate 5 constraints. The implementation can be found in (generate randommmaammmmmmm polytope polytope_rejection rejection_samplingg sampling).
loader.py
Index
Max Compute Cycles per Second
836 258 583
855 913 878
652 109 364
789 819 414
187 852 760
974 311 629
005 143 973
481 875 307
216 715 088
Table 3: Server Specifications
Required Compute Cycles per Job
Average Number of Jobs Created per Interval
Data Size in Bits
Interval Length Seconds
User
per Job
1
587 168
690 694
10
0.01
2
240 447
092 255
10
0.01
3
257 396
867 139
10
0.01
4
364 400
819 594
10
0.01
5
387 953
3 463 247
10
0.01
6
309 269
2 300 810
10
0.01
7
44 420
129 119
10
0.01
8
318 062
092 402
10
0.01
9
490 880
(144 736
10
0.01
Table 4: User/Job Specifications
A.3 Synthetic Benchmark
In addition to these environments, we propose synthetic benchmark. Its reward surface consists of an MI.P with random weights. An example of the reward surface in three dimensions visualized in Figure Each episode has two states. Since it is completely deterministic, it provides simple but
14

---

Alocrttn
Figure 6: Example of the reward surface of our synthetic benchmark in three dimensions under constraints.
effective way to benchmark approaches for constrained allocation tasks. In this setting, we create the constraints by randomly sampling 30 points and use their convex hull as the polytope defining the action space. We seven-di mensional setting with 611 constraints in our experiments. More specifically, the network has one hidden layer and ReLU as a non non- non-linearitty The input layer receives the state number, i.c., 0 or and the action as input and has an output size of 32, the hidden layer has an input size of 32 and output size of 16. The output layer has an input size 16 and a output size of 1. The exact initialization of the neural network weights can be found in our code (synth_env.p) M..RewardNetwork) To generate the environment we use the seed in our experiments.
To generate the constraints, sample 30 randomly from Dirichlet distribution with concentration parameters set to 1. We then build the convex hull of these points and convert the resulting polytope into its halfspace representation, i.e., a system of linear inequalities which we use constraints. We use the seed of to generate the constraints. This results in 61 constraints. The algorithm to generate the constraints can be found in the code (random polttopepppppeeeeepeeeee cocooop_eenrattrpyy/
B
Architecture
polytope constraints
Branch one
Bruncch two
Brunch three
LP solver
solver
On fi
solves
Cra So
a3 ,g
encorder
Muue
<Eg
Figure 7: Architecture of PASPO
C Hyperparameters/rrannngg
In Table we list the most important parameters and hyperparameters. The full configurations used can be found the config files (yaml/hydra based) our code (run configs directory). We tuned hyperparameters our synthetic benchmark with five dimensions and five constraints.
We do not train using GPUs because of the small network sizes. We used an internal CPU cluster with consumer machines and servers ranging from to 90 cores and RAM between 32GB and 512GB.
15

---

Parameter
Ours
IPO
P30
CUP
Lag.
OptLayer
CPO
Training env steps Episode/Rollout length
150,000 (synth, compute), 250,000 (portfolio optimization)
512 environment steps
Number of parallel envs
Learning Rate
le-3
1e-3
le-3
1e-3 1e-3
le-3
Gradient clipping
2.0
Minibatch size
64
Optimizer
Adam
GAE lambda
0.95
Discount factor
1.0
No. grad update it per
10 (CPO only for the critic 40)
epoch
PPO clip parameter
0.3
0.3
0.3
0.3
0.3
0.3
Entropy coefficient
0.01
0.01
0.01
0.01
0.01
0.01
Cost limit
le.3
0.0
0.0
0.0
0.0
0.0
Table 5: The most important Parameters and Hyperparameters for Various Methods
D Guaranteed Constraint Satisfaction
In the following, we proof that our approach PASPO always guarantees constraint satisfaction and that our method is able to sample all possible actions from the constrained action space.
Definitions:
Let be the of all actions that can sampled with PASPO, and let P fa R" Ca < 6} be the convex polytope that corresponds to constrained action space. We define
A {a R" (
D. b(+t1] Vj l....,i ag a₃} where b((+1) b
Ci
Ej=1 aj
and ((++) and (++1) as defined in the paper.
Cmp
Thus, (1+1) is the restricted action space after sampling/fixnn already the allocations ei......3 0z
Theorem 1. Let P = {a E ["ICa < b} * I be the convex polytope that corresponds to constrained action space. Let A be the set of all the points that can be generated by PASPO. holds that A = P.
Proof. Well-defined: Show that A(m) if P P D.
Induction over i:
1=1:
A Ea E (a s 666 b(++11) = (a Ra S b) = P
i+i+1:
0 # + Fa at E 1 at = min a = max
(1+15m)
Now assume an arbitrary a; is sampled from mam _
Y E 00, 1] a (Aat + (1 A)at):
=
By convexity of polytopes as solution spaces for linear inequality systems, we get:
C1,1
Ci,
Cij
b
(a -===)
Cm.i
Gm,
a
Cmji
01,411
Ct.a
a
Clj
+ a E (++))
<
a
Cm.i+1
Gmn
0x
Cmj
16

---

To show that A = P:
A P
Let A. In the last step (n), a is sampled (by design) such that
Cij
c nn Sb
oj
Ca <bea' EP
j=1
Cmi
A P:
Let E P. + Ca" <b
C <
<b Vi + a' E A Vi
We can construct a' by sampling aj in every step a² E
The intuition of why our approach can guarantee the satisfaction of constraints is based on three properties that utilize: (1) If P; is the set of solutions
system of linear inequalities, then by adding further constraints to the system of linear incqualities there will be new set of solutions P++1 but always such that Pi+1 S P.. (2) For any two points min and m in convex set can be implied that there exists a point a for which the following is true for its i-th dimension YX E [0, 1] : a: = (Aamin + (1 A)a (3) Linear Programming can determine the upper and
lower bounds for single variables in system of linear inequalities, i.e. [a,Tin aq .a.naxxys (vi.
start with the original system of linear inequalities with the solution space Pt * which is convex polytope. We use (3) on Pi to determine the upper and lower bounds for i.e. [apin amaas] We sample value of from the range [at a. We know that the solution space P1 must contain least one point for which in its 1st dimension d of due (2). In the next step add the further constraint aj = of to the system of linear inequalities. This updated system of linear inequalities will have the solution space Ps. Due to (2) P2 + 0, as well P2 C Pt. We then repeat the entire process and use (3) on P2 to determine the upper and lower bounds for a2, i.e. [ahinn a.maa)....
After the n-th iteration o, will be determined and we then have completed the generation of point = (ai,..., ..., at))) E P. S ... S PI. i.e. we succeed generating a point that satisfies all original constraints P1.
E
The Impact of the Allocation Order
As already discussed in the ablations in the main paper, with our de-biased initialization the impact of the allocation order is small. However, without our de-biased initialization, the order of the allocation has a significant impact on the performance, as illustrated Figure
Episode Reward Mean
15.0
14.5
14.0
13.5
13.0
5000
10000
15000
20000
Environment Steps
Figure The impact of the allocation order on PASPO without bi-bia initialization in the synthetic benchmark with two states, a a 7-dimensional action space, and no additional allocation constraints. Blue depicts the standard allocation order (i.e., 61, 62, ....... e,) and red depicts the reversed allocation order (i.e., the entities are allocated in the reversed order). A significant difference in performance can be observed with respect the order without our de-biased initialization. In contrast, Figure 5b in the paper shows that with the de-biased initialization the difference is not significant.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We define the scope by thoroughly describing the considered task and empiri- cally justify our approach in the experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We address the limitations of our method in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
18

---

Justification:
Our paper does not contain theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe our experimental setup and the used hyperparameters in the main paper and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
19

---

Answer: [Yes]
Justification:
We disclose the code to reproduce the experiments presented in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/twpsscccppbll//guuiiiiap////paa / Swweleee/ooSSSSeeeeeeeeeee
wwt.Suubmisiooooiiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe the experimental settings in reasonable level of detail in the main paper and provide complete information in the appendix and the submitted code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We use a 2-sigma confidence interval around the estimated mean shown in all of our plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
20

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide information about the compute workers used in the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips. http:///w.......ccccccccccciiaaa
Answer: [Yes]
Justification: Our research does not involve human subjects and conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Constrained allocations tasks have no direct societal impacts, however, apply- ing methods for allocation tasks in certain contexts such as finance may indirectly impact society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As not aware of direct ethical issues direct negative consequences of our work, we abstain from putting safeguards as described above place.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We acknowledge the authors of the Portfolio Optimization and Compute Load Distribution environments by citing the corresponding papers.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
22

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We publish the code of our implementation and benchmark environments. A documentation can be found the Appendix and code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The research presented in this paper does not involve crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research presented this paper does not involve crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
23

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "lWrtLCdMBr", "reviewer": "Reviewer_3hEE", "summary": "The paper presents a method for a specific setting of constrained RL method. The setting deals with constraints on the simplex of action space. The authors motivate this setting with resource allocation problems. The proposed method uses sequential conditional sampling of actions to impose constraints and also they propose a de-biasing mechanism to be robust against initialization.", "questions": "- Since the constraint satisfaction is empirical, I would ask authors to not use the word guarantee for it.\n- While reading the paper, I had a question of how much de-biasing helps. It's nice that the authors did an ablation study.  Which environment is used for the ablation study? And do you expect similar performance for all the environments?\n- In Figure 5 b) what does reverse allocation order mean?\n- What is the final algorithm? What is the objective of PPO and do you impose any constraints as you describe in lines 135 and 133? or are constraints indirectly applied by restricting the action sampling?\n- Why do you use the word auto-regressive?\n- why do you sample actions sequentially and not jointly all at once? \n- What are the state and action space dimensions of the environments used for empirical study?\n\n- comment to improve the paper (optional)\nI understand that resource allocation is an application where the framework directly fits. However, satisfying hard/state/action-wise constraints is also not so trivial with general constraint RL algorithms. A possibility could be that the authors do not directly focus on allocation tasks but rather on a framework for safe RL with a particular type of constraints and later motivate is with application of resource allocations.", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written and easy to understand with references made to figures often\n- Presents an algorithm for Hard constraint type of problems and achieves good empirical performance. \n- de-biasing mechanism", "weaknesses": "- The paper is motivated by a requirement of guaranteed constrained satisfaction however the result is empirical and not theoretical guarantees of constraint satisfaction. \n\n- The algorithm is explained in words in different parts of the paper but it misses an overall algorithm or flow of the framework. \n\n- If I had to solve the same problem (Maximizing an objective while having joint constraints on the action space), I would directly sample actions from the constrained simplex and apply an RL algorithm, e.g., PPO to it (i think you can do rejection sampling to sample from constrained simplex). Am I missing something? How would this perform as compared to PASPO? Also, it would be nice if you could explain in detail why you think one would work better than the other.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n- W1/Q1: Please see our general response regarding the theoretical guarantees.\n- 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. \n- 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. \n- 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. \n- 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.\n- Q4: \n > “do you impose any constraints as you describe in lines 135 and 133? [...]”\n\n  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. \n  > “objective of PPO?”\n\n  Our approach defines a differentiable stochastic policy function over the constrained action space and can be directly optimized using the standard objective of PPO.\n- 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”. \n- 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. \n- 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.\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xjBc2qQTRy", "reviewer": "Reviewer_QtCd", "summary": "This work considers constrained allocation tasks, like portfolio optimization or server scheduling and focuses on how to do policy optimization while respecting the given constraints.\n\nIn these problems, the core problem is that sampling over the polytope is challenging. \n\nThe work puts forward an approach for sampling points that satisfy the constraints which can be used in known policy iteration algorithms.\n\nThe approach is logical: iterate over dimensions, determining feasible range and then random sampling. Careful choice and learning of distribution parameters for sampling leads to good outcomes, removing the bias resulting from fixing earlier parameters first. This is used as the core sampling method within Proximal Policy Optimization training.", "questions": "You discuss the high computational cost of your approach - can you discuss it in the context of the other RL approaches compared against in Figure 4?", "limitations": "The authors have adequately addressed limitations of the work.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The core sampling approach PASPO is presented in a very clear way, and the sample approach is sensible and quite simple in a complicated space. \n\nThe authors compare to prior approaches are are able to show that the PASPO approach is more effective and trains faster than prior work. \n\nThe approach seems to improve significantly on other RL based approaches to given problems, though I am not close enough to the area to validate that.", "weaknesses": "The sampling approach put forward is clear and straightforward. At the same time, it is not clear the level of full novelty involved in the solution - it is a greedy sampling approach with carefully constructed weighting to avoid bias. With that said, if that gets the improved results, then much better to have that come from a simple solution than a much more complicated solution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and helpful comments. We are happy to address your questions below:\n\n\n- 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. \n- 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.\n\n[1] Spampinato, Daniele G., and Anne C. Elster. \"Linear optimization on modern GPUs.\" 2009 IEEE International Symposium on Parallel & Distributed Processing. IEEE, 2009.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "luSBeCXNGV", "reviewer": "Reviewer_3WTq", "summary": "he paper presents Polytope Action Space Policy Optimization (PASPO), a novel RL methodology tailored for strict linear constraint allocation tasks. By autoregressively decomposing the action space into manageable sub-problems, PASPO enhances compliance and efficiency without the need for corrective actions. Additionally, an innovative de-biasing mechanism during early training prevents premature policy convergence, showing significant improvements over existing methods in constraint adherence and task performance.", "questions": "none", "limitations": "none", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is very well-written.\nThe idea of PASPO is novel and interesting.\nThe motivation of the problem is clear and have practical significance.\nThe experiment results are clear and performs well.", "weaknesses": "1. The algorithm requires substantial computing resources, demanding high-performance computational capabilities to effectively manage its intensive processing needs. This entails advanced processors, ample memory, and significant data storage capacity to efficiently handle and execute the complex calculations involved. I appreciate that the authors also highlighted this in the article.\n\n2. The paper lacks a comprehensive explanation of why the algorithm achieves high performance, omitting essential details on its operational principles and optimization techniques. Additionally, there is insufficient exploration of the algorithm's adaptive features, error handling, and scalability under varying conditions. These aspects are critical for understanding its potential effectiveness across diverse scenarios and applications.\n\n3. Given that the allocation problem is formulated as a clear CMDP problem, I am curious whether the authors could provide theoretical guarantees for their approach. As I am not well-versed in this topic, I will consider the insights of other reviewers on this matter.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and helpful comments. We are happy to address your questions below:\n\n- 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.\n- 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.\n- W3: Please see our general response, where we address the theoretical guarantees in the form of a proof.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2kS4SmAogE", "reviewer": "Reviewer_2peK", "summary": "This paper studies task allocation under resource constraints and proposes a new constrained RL algorithm based on autoregressive policy optimization with a novel de-biasing mechanism. Extensive simulations are provided demonstrating the improved performance.", "questions": "See above.", "limitations": "The authors discussed the limitations explicitly in the second last section.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and the algorithm design is novel.\n\nThe numerical performance of the proposed algorithm is much better than the benchmark: no constraint violation but enjoys better reward than benchmark algorithms that allow constraint violation.", "weaknesses": "1. Is there any theoretical guarantee to explain no constraint violation in the simulation? It is quite surprising to me that the proposed algorithm has no constraint violation since the problem formulation allows constraint violation. Can the authors provide some intuitions on such a good constraint satisfaction behavior in the simulation results?\n\n2. In Section 4.1, does the order of the constraints affect the performance (for example, if we first determine the feasible interval for constraint a_2, then determine a_1, will it cause a difference in the performance)? If there is no difference, what is the reason? If there are differences in performances, how to choose an (near) optimal ordering of the constraints to improve the performance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and helpful comments. We are happy to address your questions below:\n\n\n- W1: Please see our general response, where we address the theoretical guarantees in the form of a proof.\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their detailed and constructive feedback. We will integrate many suggestions in the paper and are happy that our approach has been well received. Specifically, we are glad that reviewers find that:
- our paper is well-written and clearly presented:
  - “PASPO is presented in a very clear way” (QtCd)
  - “The paper is clearly written and easy to understand with references made to figures often” (3hEE)
  - “The paper is very well-written.” (3WTq)
  - “The paper is well-written” (2peK)

- our solution is effective and the experiments are well-conducted:
  - “The experiment results are clear and performs well.” (3WTq)
  - “Presents an algorithm for Hard constraint type of problems and achieves good empirical performance.” (3hEE)
  - “The authors compare to prior approaches are are able to show that the PASPO approach is more effective and trains faster than prior work.” (QtCd)
  - “The numerical performance of the proposed algorithm is much better than the benchmark: no constraint violation but enjoys better reward than benchmark algorithms that allow constraint violation.” (2peK)

- our paper presents a novel and significant contribution:
  - “The idea of PASPO is novel and interesting. The motivation of the problem is clear and have practical significance.” (3WTq)
  - “[...] the algorithm design is novel.” (2peK)


Before we address the questions raised by the individual reviewers in our specific responses to the individual reviewers, we would like to address a point that has come up in multiple reviews:

## Can we provide theoretical guarantees that our approach always ensures constraint satisfaction? 
**We will add a proof to the paper that shows that our approach always guarantees constraint satisfaction and that our approach is able to generate every possible constraint-compliant action. The proof is included in the attached PDF-file to this response.**

In short, we show that the set of all actions $A$ that can be generated by PASPO is equivalent to the original constrained solution space $P$ of the system of inequalities.
We prove via induction that PASPO will always generate a point $a^*$ that satisfies all constraints if $P\neq \emptyset$. The intuition is that when we determine the allocation to a single entity (that means we fix the value of a single variable in the inequality system), we express this by adding further constraints to the original system of inequalities. Therefore, every solution for the resulting system of inequalities must also be a solution for the original system of inequalities.
Furthermore, we show that any point within $P$ can also be generated via PASPO and that $A=P$.

A geometric illustration of this process can be found in our paper in Figure 2.

In the individual responses, we refer to questions and weaknesses in order of their occurrence (i.e., W1 refers to the first weakness, Q1 refers to the first question). 
Apart from the proof, the PDF attached below also contains the result of an additional experiment conducted to better answer the question of reviewer 2peK regarding the impact of the allocation order in our approach.

Meta-review: This paper introduces a new technique for policy optimization in the context of constrained allocation tasks. The paper has several strengths. First, the problem is well motivated and of practical importance. Second, the approach taken is novel and creative. Third, the experimental analysis demonstrates the approach's effectiveness compared to previous approaches to this problem rather convincingly. Finally,  the paper is well written and easy to follow.

The paper also has some weaknesses. First, although it claims to produce solutions where no hard constraints are violated and the empirical analysis demonstrates this fact, no theoretical guarantee of this property is given in the paper. A proof of this property of the algorithm was provided during the rebuttal period, however, showing that for each sequential decision, the space that can be reached by PASPO is  the constrained sample space created by the previous decision. Other weaknesses identified include: (1 ) the presentation is unclear in specifying several important aspects of the PASPO algorithm, (2) the paper lacks a comprehensive explanation of why the algorithm achieves high performance, and omits essential details on its operational principles and optimization techniques, and (3) the approach has significant computational requirements in relation to prior approaches to this problem. Subsequent discussion during the rebuttal period argued that there would not be a significant runtime problem, and also proposed revisions to address other weaknesses. Please incorporate all of these revisions and the proof in your final version should this paper be accepted.
Decision: Accept (poster)