Autoregressive Policy Optimization for Constrained Allocation Tasks

Authors: david  winkel
niklas  strauß
maximilian  bernhard
zongyue  li
thomas  seidl
matthias  schubert
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:57:54

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

Main paper: 
 introduction: 
 Continuous allocation tasks are a class of problems where an 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-the-art solutions rely on using Reinforcement Learning (RL) to learn effective policies [6, 26, 3, 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 [3] . 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 in a data center. Formally, allocation constraints are expressed as linear constraints and form a system of linear inequalities, geometrically describing a 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 are 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 several techniques that ensure the satisfaction of hard constraints [18, 6, 11, 10, 20] . These approaches might generate actions that do not satisfy the constraints but utilize a correction mechanism to map the actions back into the valid action space. In addition, most of these approaches are restricted to off-policy algorithms [11, 20] . In another line of research, solutions tailored for constrained allocation 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-step 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 is implemented in a neural networkbased policy function, which can be employed in on-policy and off-policy RL 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 a 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 to a sub-optimal policy. • An empirical evaluation that optimizes our new policy function using PPO [22] and demonstrates improved results compared to state-of-the-art 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 5 describes the results of our experimental evaluation, Section 6 briefly discusses limitations and future work before Section 7 concludes the paper.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 empirically justify our approach in the experiments. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Resource allocation tasks are a widely researched area with numerous applications spanning logistics, power distribution, computational load balancing, security screening, and finance [6, 26, 3, 20, 27] . We identify three key research directions that are particularly important when discussing resource allocation tasks.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 [4, 15] . Several works employ primal-dual optimization to leverage the Lagrangian duality, including [9, 23, 13] . Another frequently used approach involves different penalty terms [25, 14, 31] . The authors of IPO [14] propose to use logarithmic barrier functions. CPO [2] extends TRPO [21] to ensure near-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 actions [18, 6, 20, 11] . In contrast, our method always generates feasible actions without the need for correction. OptLayer [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, [20] propose a 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 approximate version of OptLayer. In [11] , the authors propose an off-policy algorithm based on the generalized reduced gradient method [1] 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. In contrast, our approach can handle an arbitrary number of constraints as well as any type of linear allocation constraints.Action Space Decomposition/Factorization The decomposition or factorization of multidimensional action spaces has been examined in several works [24, 16, 19] . A notable example is [24] , in which the authors discretize a continuous action space into several independent action branches, each parameterized by individual network branches. In [16] , a 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-trivial challenge that our approach addresses.Question: Does the paper discuss the limitations of 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem description: 
 An allocation task can be described as a finite-horizon Markov decision process (MDP) (S, A, T, R, γ), where S represents the state space, A the action space, T : S×A×S → [0, 1] the state transition function, R the reward function, and γ ∈ [0, 1] a discount factor. The goal of this task is to find a policy π maximizing the expected cumulative rewardJ π R = E π [ n t=1 γ t R (s t , π(s t ), s t+1 )].The action a is an allocation a = {a 1 , . . . , a n } ∈ A over a set of n entities E = {e 1 , . . . , e n } at each time step. Each element a i of the action vector a represents the proportion allocated to entity e i . Furthermore, allocation tasks require a complete allocation, i. e., n i=1 a i = 1 and allocations cannot be negative (a i ≥ 0). Thus, the action space of unconstrained allocation tasks forms an n-dimensional standard simplex. A visualization of an unconstrained allocation action space is provided in Figure 1a .Allocation tasks frequently include constraints, such as allocating at most 30% to a subset of the entities. An example of a constrained action space is visualized in Figure 1b . Formally, an allocation constraint can be expressed as a linear inequality n i=1 c i a i ≤ b, where c i denotes the weighting of the allocation variable a i of entity e i and b ∈ R denotes the corresponding constraint limit. For the sake of readability and simplicity, we only define ≤ constraints since a ≥ b can be transformed into -a ≤ -b and a = b can be rewritten as a ≤ b and -a ≤ -b.The action space A of constrained allocation tasks can be easily expressed by a set of linear inequalities, defining a polytope A = {a ∈ [0, 1] n |Ca ≤ b}, whereEQUATIONis a matrix of coefficients for the m constraints, including those linked to the simplex constraints n i=1 a i = 1 and a i ≥ 0 ∀i ∈ {1, . . . n}, as well as all coefficients for additional allocation constraints. Let a ∈ [0, 1] n represent an allocation vector and b ∈ R m is the vector of constraint limits.Alternatively, constrained allocation tasks can be defined using the framework of constrained Markov decision processes (CMDPs). A 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 CF k are defined asJ π CF k = E[ T t=0 γ t CF k (s t , a t )].The m constraints to be satisfied in the CMDP are then stated as J π CF k ≤ d k , where d k denotes the cost limit with k ∈ {1, . . . , m}. To formulate constrained allocation tasks using CMDPs, the cost functions can be defined as CF k (s, a) = max{0, (Ca) k -b k } to measure any allocation constraint violation as a cost. In addition, strict adherence to all allocation constraints at any point in time is required, i.e., d k = 0. By formulating constraint allocation tasks using CMDPs, it becomes possible to use existing methods from Safe RL for soft constraints. However, these methods cannot guarantee constraint satisfaction at all times [15] . Let us note that our method does not use cost functions, instead it samples actions directly from the constrained action space.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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. ] for allocations into the first entity e 1 . Then, we sample the first allocation a 1 from this interval. The details of the sampling process will be further discussed in Section 4.2. Fixing an allocation impacts the shape of the remaining action space. Thus, we have to compute the shape of the polytope A (2) described by C (2) and b (2) before we can sample the next allocation a 2 .Each iteration i starts with determining the interval [a min i , a max i ] of all feasible values for a i . Geometrically, this interval is bounded by the minimum and the maximum value of the remaining polytope A (i) in the i-th dimension associated with the allocation a i . To determine a min i , we solve the following linear program: minimizea i s.t. C (i) a (i) ≤ b (i)where C (i) are the constraint coefficients for the entities e i , . . . , e n , b (i) are the adjusted constraint limits, and a (i) describes the unfixed allocations. We determine a max i by solving the respective maximization problem. For the first iteration i = 1, we define C (1) = C, b (1) = b and a (1) = a. After sampling an allocation a i from the interval [a min i , a max i ]. The resulting polytope A (i+1) for the next iteration i + 1 is described by the following inequality system:EQUATIONTo define the new coefficient matrix C (i+1) (red), we remove the first column of the coefficient matrix of the previous iteration C (i) . To calculate the new vector b (i+1) of constraint limits, we subtract the removed column (blue) scaled by the fixed allocation a i from the previous constraint limits b (i) (yellow). We iterate over all entities until we determine a n-1 . Allocation a n is already determined as soon as the allocations a 1 , . . . , a n-1 are fixed because of the simplex constraint n i=1 a i = 1. Sampling an allocation using this approach always guarantees constraint satisfaction and it is possible to sample any action in the constrained action space. A formal proof of these guarantees can be found in Appendix D.Figure 2 displays a 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 2b depicts the first iteration after a 1 = 0.3 has been determined, and the resulting new polytope A (2) , i.e., a set of valid solutions, shrinks to the red line is shown. Figure 2c shows the second iteration after also a 2 = 0.5 has been determined. It can be seen that the new polytope A (3) contains only a single valid solution represented as a red dot, making a third iteration unnecessary since the only remaining solution is to allocate a 3 = 0.2, resulting in a final allocation of a = (0.3, 0.5, 0.2).Our goal is to define a learnable stochastic policy function over the action space. For unconstrained allocation tasks, a Dirichlet distribution can be used to parameterize the action space [26, 28] . Unfortunately, to the best of our knowledge, there is no known parameterizable, closed-form distribution function over arbitrary convex polytopes as in our setting. In fact, even uniform sampling over a convex polytope is an active research problem [8] .We sequentially constructed an action a 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 a beta distribution that is normalized to the range [a min i , a max i ]. This distribution is also known as the four-parameter beta distribution [7] . Its probability density function is defined as:p(x; α, β, a min i , a max i ) = (x -a min i ) α-1 (a max i -x) β-1 (a max i -a min i ) α+β-1 B(α, β) ,where B(α, β) is the beta function. It is important to note that any other parameterizable distributions with bounded support in the range [a min i , a max i ] can be used, such as a squashed Gaussian distribution. However, our preliminary experiments indicated that the beta distribution performs particularly well.To optimize the policy π θ (s) over the complete allocations, we follow the approach of [19] for training an autoregressively dependent series of sub-policies. A fixed but arbitrary order of entities is used for sampling the allocations a i . The sub-policy π i θ (a i |a 1 , . . . , a i-1 ) is conditional on the previous allocations a 1 , . . . , a i-1 . Using this autoregressive dependence structure, the policy is defined as:π θ (a|s) = π 1 θ (a 1 |s) • π 2 θ (a 2 )|s, a 1 ) . . . π n θ (a n |s, a 1 , . . . , a n-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. for each sample j in {1, . . . , k} do5: Calculate interval [a min (j)i , a max (j)i ] using LP based on A (i) j 6:Normalize sampled allocation to support [0,1] of beta distribution:EQUATIONCompute polytopeA (i+1) j from A (i)j using sampled allocation a (j)i (see Eq. 2)8:end for 9:ML estimation of beta distribution parameters αi , βi using {a norm (j)i } j=1...k 10: end for An entropy term is often used to encourage exploration. However, our policy does not have a closed-form solution for entropy. Therefore, we follow [19] to empirically estimate the entropy:EQUATIONHere, H 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 to generate actions based on the current policy to estimate the entropy properly.We create an embedding of the state using an MLP, denoted as f θ (s) = M LP (s). We parameterize the probability distribution over allocations for each entity using an MLP π i θi (s) = M LP (f θ (s), a 1 , . . . , a i-1 ), which receives the latent encoding of the state and the previously sampled allocations a 1 , . . . , a i-1 as input. Note that each of the MLPs π i θi has its own parameters. For further details, we refer to the Appendix.A drawback of generating actions by an autoregressive process is that a random initialization of the beta distributions leads to a 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 i the cumulated fixed allocations for earlier entities i-1 j=1 a j must be at most 20%. However, this is rather unlikely if we initialize the distribution for all entities in a 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 an unconstrained seven-dimensional simplex with our autoregressive process for each entity e i . As expected, the mean for the first dimension is 0.5, which is the mean of a 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 a 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 a 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 a de-biasing term to the linear layers' initial bias terms, predicting α i and β i for entity i. As the default initialization of the bias terms has zero means, the first iterations use α and β values close to the de-biasing terms.To determine suitable initial values for each iteration step, we proceed as described in Algorithm 1. We start by uniformly sampling n 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 [a min i , a max i ] 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, we employ the standard maximum likelihood estimator to generate an empirical estimate of the α i and β i for each entity e i . The blue bars in Figure 3a correspond to the results on the unconstrained seven-dimensional unconstrained simplex. Figure 3b shows autoregressive sampling based on uniform distribution, whereas Figure 3c displays the result of our initialization for a three-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. 
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 [3] . Additionally, we create a synthetic benchmark with a reward surface generated by a 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 a minimum dividend yield or a maximum on the CO2 intensity.The environment is based on the paper of [3] and simulates a data center in which computational jobs need to be split into sub-jobs to enable parallel processing across nine servers. Here, we use five constraints that are randomly sampled as follows: First, we sample the number of affected entities for each constraint. We then sample the constraint coefficients from the range [0, 1].In addition to the aforementioned environments, we propose a synthetic benchmark. The reward surface consists of an MLP with random weights. Each episode compromises two states. As it is completely deterministic, it provides a simple yet 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 utilize a seven-dimensional setting with 611 constraints in our experiments.We train PASPO using PPO [22] and compare our approach to various baselines, including state-ofthe-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 [18] , a popular projection-based method for linear hard constraints. To maintain a consistent and fair comparison across different methods, we use the same hyperparameters across the different methods if possible. Many Safe RL approaches have difficulties handling equality constraints [11] . Therefore, we use 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 a 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 ten different seeds due to the stochasticity of the financial environment and train for 250,000 steps. Given the relatively small network sizes, training is conducted exclusively on CPUs. We implement our algorithm and the baselines using RLlib and PyTorch. More details regarding the environments, training, and hyperparameters can be found in the Appendix.We visualize the performance and constraint violations of all methods across our three environments in Figure 4 . A tolerance of 1e -3 is used for evaluating constraint violations and we report the total number of violations per episode. In all three environments, PASPO converges faster to a higher 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 of the environment. Overall, these results demonstrate that our approach is not only able to consistently outperform other algorithms in terms of rewards but also guarantees no constraint violations.We conduct ablation studies to 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 to highlight the effects. The results, shown in Figure 5 , indicate that without de-biased initialization (orange in (a)), learning is slower and converges prematurely to a sub-optimal policy. In (b), we explore the impact of allocation order by reversing it (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 in allocation tasks with many entities, as the sampling of each action requires solving a 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-dimensional settings. For future work, we plan to extend PASPO to also incorporate statedependent 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, our method for handling hard constraints can be easily combined with most Safe RL algorithms to handle soft cumulative constraints. 
conclusion: 
 In this paper, we examine allocation tasks where a certain amount of a resource has to be distributed over a 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 set of feasible allocations might be bound by a set of linear constraints. Formally, these restrict the action space to a convex polytope. To define a 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 of other entities. Our policy function consists of a sequence of one-dimensional beta distributions where the shape parameters α and β are learned by neural networks. To counter the effect of initialization bias, we utilize a de-biasing mechanism to ensure sufficient exploration and prevent premature convergence to a sub-optimal policy. In our experiments, we demonstrate that our novel method PASPO yields better results than state-of-the-art 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. the model_parameter_data_set_G_markov_states_2_12 data set with the include_cash_asset=true option. We initialize the environment with seed=2.Table 1 shows a list of the assets used in the experiments.For the experiments a 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 or environmental portfolio measures that can be calculated as an weighted average of the assets' individual measures, i.e., as a weighted linear combination. A list of these measure can be found in Table 2 .The experiments include 5 constraints, of which the number constraints of type (a) and type (b) is randomly decided. The exact implementation can be found in our code polytope_loader.py (gener-ate_random_fin_env_polytope_rejection_sampling). We use the seed 2 to generate the constraints.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: As we are not aware of direct ethical issues or direct negative consequences of our work, we abstain from putting safeguards as described above in place.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the 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 a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 in 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as details about compensation (if any)?Answer: [NA] Justification: The research presented in this paper does not involve crowdsourcing nor human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 in this paper does not involve crowdsourcing nor human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: The compute environment used for testing our approach is based on [3] . The agent's task is to allocate compute jobs to a given set of servers in a data center. A reward is triggered for each job that was completed in a 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 as 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.e., the data to be transferred to a 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 a setup of 9 servers and 9 users that generate compute jobs. The parameter set used is parameter_set_9_9_id_0. We initialize the environment with seed=1. 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 4 .To generate the constraints, we first sample the number of affected entities between 2 and 8 for each constraint and randomly choose the affected entities accordingly. We then uniformly sample constraint coefficients from the interval [0, 1], as well as a corresponding constraint limit between 0 and 1. We use a seed of 1 to generate 5 constraints. The implementation can be found in polytope_loader.py (generate_random_polytope_rejection_sampling).Max Compute Cycles per Second In addition to these environments, we propose a synthetic benchmark. Its reward surface consists of an MLP with random weights. An example of the reward surface in three dimensions is visualized in Figure 6 Each episode has two states. Since it is completely deterministic, it provides a simple but 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 use a seven-dimensional setting with 611 constraints in our experiments. More specifically, the network has one hidden layer and ReLU as a non-linearity. The input layer receives the state (as a number, i.e., 0 or 1) 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.py: MLPRewardNetwork). To generate the environment we use the seed 1 in our experiments.To generate the constraints, we sample 30 randomly from a 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 as constraints.We use the seed of 1 to generate the constraints. This results in 611 constraints. The algorithm to generate the constraints can be found in the code (random_polytope_generator.py) In Table 5 we list the most important parameters and hyperparameters. The full configurations used can be found in the config files (yaml/hydra based) in our code (run configs directory). We tuned hyperparameters on 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 8 to 90 cores and RAM between 32GB and 512GB. 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 A be the set of all actions that can be sampled with PASPO, and let P = {a ∈ R n |Ca ≤ b} be the convex polytope that corresponds to constrained action space. We defineA (i+1) * = {a ∈ R n |C (i+1) a (i+1) ≤ b (i+1) * , ∀j = 1, . . . , i : a j = a * j } where b (i+1) * = b - i j=1 a * j    c 1j . . . c mj    and C (i+1)and a (i+1) as defined in the paper.Thus, Ais the restricted action space after sampling/fixing already the allocations a * 1 , . . . , a * i . Theorem 1. Let P = {a ∈ R n |Ca ≤ b} ̸ = ∅ be the convex polytope that corresponds to a constrained action space. Let A be the set of all the points that can be generated by PASPO. It holds thatA = P . Proof. Well-defined: Show that A (n) ̸ = ∅ if P ̸ = ∅.Induction over i:i = 1 : A (1) * = {a ∈ R n |C (1) a (1) ≤ b (i+1) * } = {a ∈ R n |Ca ≤ b} = P ̸ = ∅ i → i + 1 : (i + 1 ≤ n) A (i) * ̸ = ∅ ⇒ ∃a ↑ , a ↓ ∈ A (i) * : a ↑ i = a min i , a ↓ i = a max i Now assume an arbitrary a * i is sampled from [a min i , a max i ] ⇒ ∃λ ∈ [0, 1] : a * i = (λa ↓ + (1 -λ)a ↑ :=a λ ) iBy convexity of polytopes as solution spaces for linear inequality systems, we get:   c 1,i • • • c 1,n . . . . . . . . . c m,i • • • c m,n       a λ i . . . a λ n    ≤ b - i-1 j=1 a * j    c 1j . . . c mj    ⇐====⇒ (a λ i =a * i )    c 1,i+1 • • • c 1,n . . . . . . . . . c m,i+1 • • • c m,n       a λ i+1 . . . a λ n    ≤ b - i j=1 a * j    c 1j . . . c mj    ⇒ a λ ∈ A (i+1) *To show that A = P :A ⊆ P : Let a * ∈ A.In the last step (n), a * n is sampled (by design) such thatC (n) a * n ≤ b - n-1 j=1 a * j    c 1j . . . c mj    ⇔ Ca * ≤ b ⇔ a * ∈ P A ⊇ P : Let a * ∈ P. ⇔ Ca * ≤ b ⇔ C (i) a * ≤ b (i) ∀i ⇔ a * ∈ A (i) * ∀i ⇒ We can construct a * by sampling a * i in every step i. ⇒ a * ∈ AThe intuition of why our approach can guarantee the satisfaction of constraints is based on three properties that we utilize: (1) If P i is the set of solutions to an system of linear inequalities, then by adding further constraints to the system of linear inequalities there will be a new set of solutions P i+1 but always such that P i+1 ⊆ P i . (2) For any two points a min and a max in a convex set it can be implied that there exists a point a λ for which the following is true for its i-th dimension ∃λ ∈ [0, 1] : We start with the original system of linear inequalities with the solution space P 1 ̸ = ∅ which is a convex polytope. We use (3) on P 1 to determine the upper and lower bounds for a 1 , i.e. ]. We know that the solution space P 1 must contain at least one point for which in its 1st dimension a 1 = a * 1 due to (2). In the next step we add the further constraint a 1 = a * 1 to the system of linear inequalities. This updated system of linear inequalities will have the solution space P 2 . Due to (2) P 2 ̸ = ∅, as well as P 2 ⊆ P 1 . We then repeat the entire process and use (3) on P 2 to determine the upper and lower bounds for a 2 , i.e. [a min 2 , a max 2 ]....EQUATIONAfter the n-th iteration a * n will be determined and we then have completed the generation of point a * = (a * 1 , ..., a * n ) ∈ P n ⊆ ... ⊆ P 1 , i.e. we succeed generating a point a * that satisfies all original constraints P 1 .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 in Figure 8 . The impact of the allocation order on PASPO without de-biased initialization in the synthetic benchmark with two states, a 7-dimensional action space, and no additional allocation constraints. Blue depicts the standard allocation order (i.e., e 1 , e 2 , . . . , e n ) 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 to 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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - The paper is motivated by a requirement of guaranteed constrained satisfaction however the result is empirical and not theoretical guarantees of constraint satisfaction. 

- The algorithm is explained in words in different parts of the paper but it misses an overall algorithm or flow of the framework. 

- 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.
questions: questions: - Since the constraint satisfaction is empirical, I would ask authors to not use the word guarantee for it.
- 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?
- In Figure 5 b) what does reverse allocation order mean?
- 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?
- Why do you use the word auto-regressive?
- why do you sample actions sequentially and not jointly all at once? 
- What are the state and action space dimensions of the environments used for empirical study?

- comment to improve the paper (optional)
I 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: limitations: None
paper_summary: paper_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.

In these problems, the core problem is that sampling over the polytope is challenging. 

The work puts forward an approach for sampling points that satisfy the constraints which can be used in known policy iteration algorithms.

The 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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The authors have adequately addressed limitations of the work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

3. 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.
questions: questions: none
limitations: limitations: none
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2. 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?
questions: questions: See above.
limitations: limitations: The authors discussed the limitations explicitly in the second last section.

Comments: comment: Thanks for the responses. I do not have further questions.
Thanks for your responses and the theoretical discussions! However, I think it is better to resubmit this paper next time with the theoretical results added. So I will keep my score.