Dynamic Neighborhood Construction for Structured Large Discrete Action Spaces
Authors: Fabian Akkerman
Julius Luy
Wouter van Heeswijk
Maximilian Schiffer
Venue: ICLR 2024 poster (2024)
Keywords: Structured large discrete action space
Reinforcement learning
Neighborhood search
Primary area: reinforcement learning
TL;DR: We propose a method to deal with structured large discrete action spaces in RL and benchmark it against several state-of-the-art methods on three domains.

Abstract: Large discrete action spaces (LDAS) remain a central challenge in reinforcement learning. Existing solution approaches can handle unstructured LDAS with up to a few million actions. However, many real-world applications in logistics, production, and transportation systems have combinatorial action spaces, whose size grows well beyond millions of actions, even on small instances. Fortunately, such action spaces exhibit structure, e.g., equally spaced discrete resource units. With this work, we focus on handling structured LDAS (SLDAS) with sizes that cannot be handled by current benchmarks: we propose Dynamic Neighborhood Construction (DNC), a novel exploitation paradigm for SLDAS. We present a scalable neighborhood exploration heuristic that utilizes this paradigm and efficiently explores the discrete neighborhood around the continuous proxy action in structured action spaces with up to $10^{73}$ actions. We demonstrate the performance of our method by benchmarking it against three state-of-the-art approaches designed for large discrete action spaces across three distinct environments. Our results show that DNC matches or outperforms state-of-the-art approaches while being computationally more  efficient. Furthermore, our method scales to action spaces that so far remained computationally intractable for existing methodologies.

Published as a conference paper at ICLR 2024
DYNAMIC NEIGHBORHOOD CONSTRUCTION FOR STRUCTURED LARGE DISCRETE ACTION SPACES
Fabian Akkerman* .1, Julius Luy,.2.t Wouter van Heeswijk', Maximilian Schiffer
1 University of Twente (7500 AE Enschede, The Netherlands)
2 School of Management, Technical University of Munich (80333 Munich, Germany)
3 Munich Data Science Institute, Technical University of Munich (85748 Garching, Germany)
ABSTRACT
Large discrete action spaces (LDAS) remain a central challenge in reinforcement learning. Existing solution approaches can handle unstructured LDAS with up a few million actions. However, many real world applications in logistics, production, and transportation systems have combinatorial action spaces, whose size grows well beyond millions of actions, even on small instances. Fortunately, such action spaces exhibit structure, e.g., equally spaced discrete resource units. With this work, we focus handling structured LDAS (SLDAS) with sizes that cannot be handled by current benchmarks: we propose Dynamic Neighborhood Construction (DNC), novel exploitation paradigm for SLDAS. We present scalable neighborhood exploration heuristic that utilizes this paradigm and efficiently explores the discrete neighborhood around the continuous proxy action in structured action spaces with up to 107 actions. We demonstrate the performance of our method by benchmarking it against three state-of-the-an approaches designed for large discrete action spaces across three distinct environments. Our results show that DNC matches or outperforms wfat-oof-the-ar approaches while being computationalyy more efficient. Furthermore, our method scales to action spaces that so far remained computationally intractable for existing methodologies.
INTRODUCTION
In deep reinforcement learning (DRL), ample methods exist successfully handle large state spaces, but methods to handle large discrete action spaces (LDAS) remain scarce (Dulac-Amold et al., 2021). Off-the-shelf DRL algorithms - e.g., Deep Q-Networks (DQN) (Mnih et al., 2013), Deep Policy Gradients (DPG) (Silver et al., 2014), or Proximal Policy Optimization (PPO) (Schulman et al., 2017) fail to handle such LDAS, as they require in- or output nodes for each discrete action, which renders learning accurate Q-values action probabilities computationally intractable. Recent methods extending off-the-shelf algorithms focus on applications with unstructured LDAS, found in, e.g., recommender systems autonomous tool selection (cf. Dulac-Amol. et al., 2015; Chandak et al., 2019a; Jain et al., 2020). Herein, the agent's 's action space encodes an irregular set of features. To handle LDAS, current DRL research suggests to learn continuous policy and utilize output mapping to each discrete action (Dulac-Arnoke et al., 2015; Chandak et al., 2019a), which allows solving problems with moderately large action spaces up to few million actions. However, many real-world problems have (combinatorial) action spaces exhibiting billions of actions even for small problem instances. Examples are the management of order levels for items in a large warehouse (Boute et al., 2022) and the synthesis of new chemical structures for drug design (Gottipati et al., 2020). Current state-of-the-art techniques for LDAS cannot scale such very large LDAS as they define explicit mapping for each discrete action.
Yet, many problems with combinatorial action spaces exhibit structure, e.g., equally spaced discrete resource units in inventory replenishment (Boute et al., 2022), distance units in path planning for autonomous vehicles (Xie ct al., 2023), the movement of robot joints in a discretized action space (Neunert et al., 2020), and traffic signal control ordered by the sequence of lanes (Li et al., 2021). With this work, we show how to exploit such structure, eliminating the need to enumerate all actions, hence
Equal contribution.
Corresponding authors: Fabian Akkerman (frakkerman@utweeeenn)) Julius Luy (uuiuu.luy lu@@mumde)))

---

Published as a conference paper at ICLR 2024
allowing scale to much larger action spaces. Specifically, we propose novel algorithmic pipeline that focuses on structured LDAS (SLDAS) and exploits their structure by embedding continuous to- discrete action mappings via dynamic neighborhood construction into actor-critic algorithm. This pipeline overcomes the scalability limitations of the state of the art on SLDASS by bypassing explicit action space enumeration, scaling up action spaces of size 1073, while showing comparable or even improved algorithmic performance.
Related Literature To handle LDAS, some works employ factorization to reduce the action space's size by grouping actions into representations that are easier to learn. Examples are factorization into binary subsets (Sallans & Hinton, 2004; Pazis & Parr, 2011 1; Dulac-Amold et al., 2012), expert demonstrations (Tennenholtz & Mannor, 2019), tensor factorization (Mahajan et al., 2021), symbolic representations of state-action values (Cui & Khardon, 2016; 2018), or the use of value-based DRL, incorporating the action space structure into a Q-network (Tavakoli et al., 2018; Sharma et al., 2017; Wei et al., 2020; Tang et al.. 2022). Hierarchical reinforcement learning (HRL) and multi-agent reinforcement learning (MARL) approaches effectively employ factorization as well (Zhang et al., 2020b; Kim et al., 2021; Peng al., 2021; Enders et al., 2023). Although some of these works cover extremely large action spaces and prove to be effective for specific problem classes, the proposed approaches require an priori encoding for each discrete action, do not leverage the action space's structure, and frequently require substantial design- and parameter tuning effort (particularly in the case of MARL).
While factorization methods reduce the number of evaluated actions, methods that leverage continuous- toessstto-ddde to-discrete mappings consider the continuum between discrete actions, converting continu- ous actions to discrete ones subsequently. van Hasselt & Wiering (2009) use an actor-critic algorithm, rounding the actor's 's continuous output to the closest integer to obtain a discrete counterpart. Van- vuchelen et al. (2022) extend this concept to multi-dimensional action vectors, normalizing the actor's output and rounding it to the nearest discrete value. Such rounding techniques are straightforward and computationally efficient, but may be unstable if their mapping is too coarse. Different continuous outputs might be mapped to the same discrete action, while ignoring potentially better neighbors. To mitigate this issue, Dulac-Aroll et al. (2015) and Wang et al. (2021) replace the rounding step by k-nearest neighbor search or k-dimensional tree search. While such methods allow handling both unstructured- and SLDAS, they offer only limited scalability, necessitating the definition and storage of the discrete action space a priori, c.g., in matrix form.
Other works aim at learning action representations. Thomas & Barto (2012) use a goal-conditioned policy to learn motor primitives, i.c., aggregated abstractions of lower-level actions. Chandak al. (2019a) consider a policy that maps continuous actions into an embedding space and employ supervised learning to identify unique embedding for each discrete action. Follow-up works consider combined state-action embeddings (Whitney al., 2020; Pritz al., 2021), or reduce the impact of out-of-distributio actions in offline DRI. by measuring behavioral and data data-distributionall relations between discrete actions (Gu et al., 2022). Some works propose to learn embeddings for all feasible actions by means of a value-based approach (He et al., 2016), or learn to predict and avoid suboptimal actions (Zahavy et al., 2018). Chandak et al. (2019b) and Jain et al. (2020; 2022) consider the problem of adapting an RL agent to previously unseen tasks by mapping the structure of unseen actions to the set of already observed actions. In general, action representation learning allows handle unstructured and SLDAS, but requires vast amount of data learn accurate representations, often hampering algorithmic performance. Moreover, scalability issues remain due to learning dedicated representations for each action.
As can be seen, existing methods to handle SLDAS are constrained by the action space size due the following obstacles: (i) straightforward factorization approaches require handerafted encodings priori and are thus confined to enumerable action spaces, (ii) approaches that base on HRL or MARL are highly mooblem-specfff and rely on intense hyperparameter tuning, (iii) static mappings lack scalability as they require to define and store the discrete action space priori, (iv) learning action representations requires vast amount of data to obtain dedicated representations for each action. Thus, all existing approaches are upper-bounded on the number of actions they can handle.
Contribution To close the research gap outlined above, we propose novel algorithmic pipeline that exploits the structure in SLDAS while maintaining or improving the state-of-ther in solution quality and reaching new level of scalability to very large SIDDAS. This pipeline embeds continuous-
2

---

Published as a conference paper at ICLR 2024
to-discrete action mappings via dynamic neighborhood construction (DNC) into actor-critic algorithm. DNC is leveraged to convert the actor's continuous output into a discrete action via a simulated annealing (SA) search, guided by discrete actions' Q-values derived from its critic. Our approach has two novel components: (i) we exploit the structure of the action space using dynamic neighborhood construction, and (ii) we employ an SA neighborhood search to improve performance. Although our approach classifies as a continuous-to-disse definition of the action space. Moreover, our approach can be applied to a wide range of problem settings as long as the respective action space exhibits structure. We benchmark our pipeline against three oate-of-theeart approaches (Dulac-Arnold et al., 2015; Chandak al., 2019: 19;; Vanvuchelen et al., 2022) and vanilla actor critic (VAC) baseline across three environments: maze environment, joint inventory replenishment, and a job-shop scheduling problem. Our results verify the performance of our pipeline: it scales up to discrete action spaces of size 1073, while showing comparable or improving solution quality across all investigated environments.
action mapping, it requires no priori
2 PROBLEM DESCRIPTION
We study discrete, sequential decision-make making problems formalized as Markov decision processes (MDPs), described by a state space S, a discrete action space A, a reward function r S x A + R, and transition dynamics PP S A S [0, 1]. We represent states E S and actions a E A by N-and M M-dimeenionnll vectors, such that s E R and a E NN. We consider multi-dimensional action vectors to ensure general applicability. but refer to such vector as an action in the remainder of this paper for the sake of conciseness. We focus on regularly structured action spaces, which we can represent with a regular tessellation of an n-dimensional hypercube or hyperrectangle, Hence, we assume that the smallest distance between two neighboring vertices of the tesselated grid along each dimension n, Ad,, is constant. Figures la and lb visualize two examples of regularly structured grids, that can be found in, e.g., inventory problems, wherein coordinates @i and a2 represent the discrete resource units of items and 2 respectively (cf. Boute et al., 2022). Figure Ic exemplifies an irregularly structured action space. Note that our method extends to E Q as long the action space can be represented by a regular grid. For conciseness we will refer to "regularly structured" as "structured" action spaces and to "irregularly structured" "unstructured" action spaces in the remainder.
Aa
d2*
Aaz
0
(a) Regularly structured,
(b) Regularly structured, Aai # Aoz.
(c) Irregularly structured.
Aai Aaz.
Figure 1: Structured and unstructured action spaces in 2D. Each vertex represents action.
Let us denote policy by π S + A and the state-action value function by QT a) = E,, E /rry [s, a), where y E [0, 1) denotes the discount factor. We aim to find policy that maximizes the objective function J = Ea-n[ (Q=(sa)))) as.
To introduce our method, first consider an actor-critic framework, in which an actor determines action E AA based on a policy (actor network) no parameterized by weight vector 0, and a critic parameterized by u which estimates the value of this action, i.e., returns Qu. (8, a). The actor is updated in the direction suggested by the critic by maximizing the objective function J. The actor network's 's output layer contains |A| nodes, each reflecting the probability of an action a E AA i.c., the network (s) encodes the policy. In many real-world problems, |Al grows exponentially with the state dimension. In these cases, obtaining an accurate policy requires vast amounts of training data and exploration ensure generalization over A, making training of To intractable.
To bypass the need of learning accurate probabilities for each action, we will solve the following surrogate problem in the remainder of this paper: instead of finding discrete policy returning action
3

---

Published as a conference paper at ICLR 2024
probabilities for each E A, we find policy that returns continuous actions à R and function f(ā) = a that maps continuous actions to discrete ones. This approach allows to use off- sfellf policy gradient algorithmss which perform well in continuous action spaces to learn To (a(s) and ensures that no 's output layer grows linearly with the number of entries in á.
A straightforward implementation of would return the discrete neighboring action to å with the highest Q-value, as proposed in Dulac-Amold et al. (2015). Herein, the authors search for the closest neighbors â over the entire action space and return the discrete action with the highest Q-value. This requires an a priori definition of the action space, e.g., encoded as a matrix, hence reaching memory limits if action spaces are very large. Instead of searching the entire action space, we aim to efficiently search for an action a that maximizes Q. Formally, one can describe the underlying optimization problem as mixed-integer linear program (MILP);; the action space structure and the actions' discreteness allow imposing linear constraints to bound the action vector's s entries and, hence, for an efficient neighborhood search. Q-values are represented by deep neural networks (DNNs) to capture non-linearinn con-lincarities, which we express ReLU activation functions (cf. Bunel et al., 2017). Let E = {1. (1...., ; L} be the index of the I-th DNN layer and, with slight abuse of notation, d: denote neuron d E Dj {1, ................................ Di} in layer I. Let o be the DNN's output node o and wd:-,,d be the DNN's weights. The outputs yi of the DNN's neurons and the discrete action vector elements a; a, {1 (1....:N] represent the MILP's decision variables. As we assume the discrete action space has an underlying continuous structure, we expect the best discrete action to be close in vector distance the continuous proxy action and restrict our search space accordingly. Let ay (ā) and of (@) denote upper and lower bounds on the action vector's 's elements respectively. The MILP with the main set of constraints then reads:
MILP if the DNN solely consists of linear and
max (Q a)) = max Σ
Wdz a yds
(1)
04
de
S.t.
d' (a) < 0 S a, (a);
Vi NJ:
(2)
yd. 20 0,
VE C, D,
(3)
|a|<D
yd Σ di-1=1
1.d ad
Σ d=1=|aa
wT wdt-idd .d Vd
1 1= 2, Vdl.
(4)
The Objective (1) maximizes the weighted sum of outputs in the last layer, which equals Qu a). Constraints describe the neighborhood of à. Constraints 3 implement the ReL.U activation functions by imposing non-n non-negativity on the neurons' outputs. Constraints 4 describe the transition from the input to the second DNN layer. Here, v² are the outputs of previous feedforward layers processing only the state input s. We provide the full set of constraints in the supplement. The MILP bypasses the need to store the entire action space matrix in memory, but needs be solved in each training step as the DNN weights change, which is costly for large DNN architectures. Accordingly, we base our methodology in the following on efficiently finding a heuristic solution to this MILP via dynamically constructing and searching through local neighborhoods of â.
3 METHODOLOGY
Figure 2 shows the rationale of our algorithm's pipeline, which builds upon an actor-critic framework, leveraging DNC transform the actor's continuous output into a discrete action. Our pipeline comprises three steps. First, we use the actor's output à to generate a discrete base action ā E A.. We then iterate between generating promising sets of discrete neighbors A'' and evaluating those based on the respective Q-values taken from the critic. Here, we exploit the concept of SA (cf. Kochenderfer Wheeler, 2019) to guide our search and ensure sufficient local exploration. The remainder of this section details each step of our DNC procedure and discusses our algorithmic design decisions.
Generating a Discrete Base Action We consider an actor network whose output corresponds to the first-order (a (s))),, E RR and second-order (s).). E R moments of pre-specified distributions for each element n E [1.....N] .N of the action vector to parameterize a stochastic policy T with continuous actions à. To obtain discrete base actions, we scale and round each continuous à; to the closest discrete value, denoting the corresponding base action after rounding by a. We refer to the supplementary material for further details this generation procedure.
4

---

Assuming that an action's structured neighborhood relates to a locally convex J w.r.t. action vector changes, can show that the worst-case performance relative base action is bounded within a radius corresponding to the maximum perturbation distance (de). To formalize this, let A" (a A' ||a all2 (dc)) denote the set of maximally perturbed actions with respect to Published as a conference paper at ICLR 2024
Cont. action a
DNC
Disc.
State 8
Actor (s)
Find neighbors to base action a
action
Evaluate neighbors
Disc. action A
A'
Qw a), E A'
Move to A'
Figure 2: Pipeline for finding discrete actions in SLDAS
Generating Sets of Diserete Neighbors Within DNC, we aim to leverage neighbors of discrete base actions, motivated by the rationale that neighborhoods of actions exhibit certain degree of cohesion. Specifically, when generating action neighborhoods A', we premise that action pairs with small vector distances generate similar Q-values.
Definition
We measure action similarity within A' viu Lipschitz constant satisfying IQ" (8, a)= < Llla - 22122for all a, a' E A.
(P(aaa)Q""(a.e ensuring that [Q= a)
Lemma
Action similarity L is given by
a aa ||a ||a-a'lla
(T(s,a')) < L|la a' a'12 for all a' E..
To prove Lemma 1, we use that A' is discrete, finite, and maps onto the real domain, and thus finite exists. We refer the supplementary material for a formal proof.
To generate discrete neighbors of a, we perturb each action vector entry ün, E (1...., N). To do so, we define perturbation matrix P (Pig)=nt..., N.j.................. with being the neighborhood depth. Moreover, let denote scaling constant that allows us to look at more distant (larger e) or closer (smaller e) neighbors. With this notation, the perturbation matrix P reads as follows:
c (l( 1)/N| + 1), Ps = -e (L0 - 1)/N] +1-d), d), 0.
......,. . i+ N) jf E +i+ dN, i + (d 1)., ,, (2d 1) N}. otherwise.
if E {i,é+ N, 2N, 2N,
The first d N columns of P are vectors with one non-zero entry describing a positive pertur- bation of each entry in à the last d N columns describe negative perturbations. Let À (Ak)):=i....Ni=I...
the perturbed matrix denote a matrix that stores in each its columns. We then obtain (d.))imt....NN1 NN.=l.....dN as
+ P, such that A's columns form the set set A', yielding 2 N neighbors with maximum L2 distance (de). In each perturbation, we modify only one entry of a, such that each perturbed neighbor has a Hamming distance of 1 and an L2 distance of up to (de) to the base action. Note that we can define individually for each dimension which we omit in this description to remain concise.
The perturbation approach allows for efficient implementation and scales to very large action spaces by design as limits the exploration the neighborhood of a, which in a general case would still increase exponentially with respect to maximum Lę -a-ditaance of (de). Clearly, limiting the neighborhood evaluation may incur performance loss, but we argue that this loss is limited, as our search procedure described in the next section able to recover initially ignored neighbors.
Lemma 2 If J is locally upward convex for neighborhood A' with maximum perturbation (d around base action a, then worst-case performance with respect to bound by the maximally perturbed actions a" E A" via Q" (8, a') min Q (=(s,aa) Va' E A'.
a"EA"
To prove Lemma 2 we leverage that inequality min (" S Q" (s, ((a) +11 (1-x)(a'))
a"c,A"
with a, E A and À E [o, 1). holds by definition of upward convexity and refer to the supplementary material for complete proof.
5

---

Published as a conference paper at ICLR 2024
Evaluating Discrete Action Neighborhoods Algorithm 1 details the evaluation of base action's neighborhood and our final selection of the discrete action a that we map to â. We initially select selection
the discrete action within neighborhood that yields the highest Q-value. However, does not base on a single neighhorhood evaluation, but employs an iterative SA-based search scheme to explore various neighborhoods. SA is probabilistic search technique that facilitates escape local optima during a search by occasionally accepting worse actions than the best one found (cf. Kochenderfer & Wheeler, 2019).
Specifically, Algorithm works as follows. After generating a set of neighbors A'' (1.3), we utilize the critic to obtain Q- Q-values for a' E A'' which includes the current base action and each neighbor (l.4). Subsequently, we store the k-best neighbors in an ordered set K' S A' and store K'' in K, the latter set memorizing all evaluated actions thus far (1.5). From KC', we select action k1, which by definition of K.' has the highest associated Q-value, for evaluation (l.6). If the Q-value of L1 AC' exceeds the Q-value of the base action a. we accept kj as new base action ā (1.8). If it also exceeds the current best candidate action, a' (1.10), we accept it as the new best candidate action. If the action 1 does not exhibit higher Q-value than a, we accept it with probability 1 1 exp[ - (Q (ā) - Q (k))) /3] and reduce 3 by cooling parameter сa (1.12), or reject it and move to new base action, sampled from K. (1.14). Finally, the parameter is reduced by cooling parameter ck. Steps (1.3) to (1.15) are repeated until the stopping criterion (1.2) has been met. We then set a a", i.e., we the action with the highest Q-value found as our final discrete action. For a more detailed description of the search process, hyperparameter tuning, and the integration of Algorithm into generic actor-critic algorithm, we refer to the supplementary material.
Algorithm Dynamic Neighborhood Construction
1: Initialize k. B, Ca, and Cs. ā < g(ā), a" <- -a
2: while k > 0,
0 do
3: Find neighbors A' to ā with P.j
4: Get Q-values for all neighbors in A'
5: Obtain set K" with k-best neighbors, 10 + KUKK'
6:
In t K', with k = arg maxxex Qw
7:
if (w, k1) > (s, @) then
8:
Accept k E K", ā 4- kn
9:
if nm (8, k1) > Qu
(8, a*) then
10:
+ h1
11:
else if rand() < exp[ - (Quu (a) - (ki)) then
12:
Accept 1 E K', ā k1, 3 +- B C8
13: else
14:
Reject K, E K', ā kand E KC
k- [k
ck]
16:
Return ā²
Discussion A few technical comments the design of our algorithmic pipeline are in order. First, a composed policy of the form a T (s) = DNC(TT(s)) is not fully differentiable. To ensure that our overall policy's backpropagation works approximately, Dulac-Arnold et al. (2015). Step I bases the actor's loss function on the continuous action à to exploit information from the continuous action space that would have been lost if training the actor on the discrete action à. Step 2 trains the critic using the discrete action a, i.c., the actions that were applied to the environment and upon which rewards were observed. We detail the integration of DNC into an actor-critic algorithm in the supplementary material. Second, one may argue that using an superfluous, as our overall algorithmic pipeline already utilizes a
follow steps, similar to
iterative SA-based algorithm stochastic policy To that ensures exploration. Here, we note that utilizing no only ensures exploration in the continuous action space. To ensure that subsequent deterministic steps in A, i.c., base action generation and neighborhood selection, do not lead to local optima, we use SA search across different and potentially better neighborhoods in the discrete action space. Furthermore, as DNC does not explore the neighborhood exhaustively as, e.g., knn MILP based approach, SA ensures that potentially better neighbors are not left out. In fact, we can show that with the chosen algorithmic design, DNC leads improving actions in finite time.

---

Published as a conference paper at ICLR 2024
Lemma 3 Consider neighborhood A' and improving actions satisfying Q (s) A' A'. In finite time, DNC will accept improving actions, provided that max (s, E'E.A'
(i) B and k cool sufficiently slowly and (ii) maximum perturbation distance (de) is set such that all action pairs can communicate.
To prove Lemma 3, we utilize that under conditions (i) and (ii), our SA-based search can be formalized irreducible and aperiodic Markov chain over A. A positive transition probability then applies to each action pair. For complete proof, we refer to the supplementary material.
4 EXPERIMENTAL DESIGN
We compare the performance of our algorithmic pipeline (DNC) against four benchmarks: VAC, the static MinMax mapping proposed in Vanvuchelen et al. (2022), the k-nearest neighbors (knn) mapping proposed in Dulac-Arold et al. (2015), and the learned action representation (LAR) approach proposed in Chandak et al. (2019a). To this end, VAC can be seen as a baseline, while MinMax, knn, and LAR denote state-of-the art benchmarks. Furthermore, to show the added value of SA, we conduct an ablation study in which SA is removed from the solution method, which we label with DNC w/o SA. Here, we generate a set of discrete neighbors once and return the best action directly. We detail all of these benchmarks and respective hyperparameter tuning in the supplementary material. We consider three different environments to analyze algorithmic performance, which we summarize in the following. For their implementation details, we refer to the supplementary material.
First, we consider a maze environment, which is used as a testbed in state-of-the-ar works on LDAS (cf. Chandak et al., 2019a). Here, an agent needs navigate through maze, avoiding obstructions and finding a goal position. The agent receives continuous coordinates on its location as input and decides on the activation of N actuators- equally spaced around the agent- that move the agent in the direction they are pointing at. The resulting action space is exponential in the number of actuators, i... |A| 2 The agent incurs a small negative reward for each step and a reward of 100 when the goal is reached. Random noise of 10% is added to every action. In addition, we consider variation of the maze problem, wherein we add one teleporting tile that needs to be avoided when trying to find the goal. Landing on this tile will result in penalty of -20 and teleport the agent back to the starting position. With this variant, we study the policies' ability to deal with non-linear underlying Q-value distribution due to the reward and Q-value jumps close to the teleporting tile.
Second, we consider a joint inventory replenishment problem (cf. Vanvuchelen et al., 2022). Consider retailers' warehouse that stocks N item types i E I. Each timestep, customer demand is served from the warchouse stock and the retailer needs to decide on the ordering quantity, aiming to minimize total costs that comprise per-item ordering costs o,, holding costs h, and backorder costs b;. The latter constitute a penalty for not being able to directly serve demand from stock in a time step. All individual items i are linked together through common order costs O This fixed cost is incurred whenever at least one item is ordered, i.e., this term ensures that all items need to be considered simultaneously, since batch-reordering of multiple items is less costly. To ensure finite decision space, we let the agent decide on order-up-to levels, which are bound by Smax. i.e., Smax represents the maximum of items the retailer can stock. Hence, |A| (Smax + +1) which includes ordering zero items. For all our experiments we set Smax to 66, i.c., |A| = 67
Third, we consider well-known dynamic job-shop scheduling problem (see, c.g., Zhang et al., 2020a; Wu & Yan, 2023). In this problem, set of G jobs is allocated to N machines that can serve up to L jobs each, yielding an action space of size IA| = L.N We consider a boad-balancing variant of this problem, for which jobs need to be balanced over heterogeneous machines. Apart from positive reward for each finished job, we incur negative rewards for an unbalanced allocation of jobs over machines and for energy consumption, which is heterogeneous over machines and is affected by the deterioration and repair of machines. as such adding stochasticity to the transition function. For experiments, we set G 500, T. 100, and N 5.
5 NUMERICAL RESULTS
The following synthesizes the findings of our numerical studies, focusing on the scalability and algorithmic performance of each method. All results reported correspond to runs with the best
7

---

Published as a conference paper at ICLR 2024
hyperparameters found for each method, executed over 50 seeds. We refer to the supplementary material for detailed results and information on the hyperparameter tuning. We compare the methods' step time and memory usage in Appendix H.
Table Learning performance for different action space sizes |AY.
VAC
LAR
knn
MinMax
DNC w/o SA DNC
10a
|A|
106
oo
106
A S 10
[ >> 10
Table I compares algorithm performance in learning policies across different action space sizes in three environments. checkmark denotes consistent learning of performant policies for all instances in given action space size, while a circle indicates consistent learning for some instances, and minus for none. VAC already struggles spaces with thousands of actions, emphasizing the need for advanced methods to handle LDASS. For 10 < |A| < 10", knn succeeds to learn performant policy, but L.RR fails to learn. LAR learns unique embeddings for each action, which beneficial in unstructured action spaces where it identifies and uses meta-structure. However, in SLDAS, creating embeddings for every action becomes intractable. For action spaces with [A]] > 10 knn also fails due to memory constraints. Our DNC algorithm consistently learns performant policies across all sizes, showing robust scalability. The MinMax approach exposes difficulties in spaces larger than 10 it is susceptible to getting stuck in local optima the action space grows.
The remainder of this section focuses on algorithmic performance, i... the average performance during testing. Here, omit the analyses of algorithms that not capable of learning performant policies at all for the respective environments. We report results for solving the MILP, which does scale beyond the maze environment, in Appendix For all performant benchmarks, Figure shows the expected test return evaluated after a different number of training iterations and averaged over random seeds.
The two figures in the top row depict the results for the maze environment. We observe that VAC is unable find a good policy already for "smaller" action spaces of size 2 actions. The other algorithms do not differ significantly in their performance. We note that for this relatively
VAC
LAR
knn
MinMax
DNC wo SA
DNC
100
Maze blall 2-20
80
Tool expe000 H0UFT5
60
40
20
-20
3
Ieventeyy actonn actions
Inrtboyy 47"42 action
10"10 actiors
25000
20000
4.12
-72
25000
4.14
-7.
20000
4.78
-7A
15000
4.10
7.5
Epsoder (4100)
Sabodea (x10))
Epacdos (424
Figure 3: Average total expected returns during testing for 50 random seeds over the training iterations. The shaded area represents the 2 standard deviation training seed variance corridor. (Top) maze environment results. (Bottom) real-world environment results.
8

---

Published as a conference paper at ICLR 2024
simple environment with low reward variance and smooth Q-value distribution, the benefit of considering neighbors to â is limited, such that DNC does not outperform MinMax but obtains a similar performance. Hence, if continuous actions can already be accurately mapped to discrete ones, evaluating neighbors has limited added value.
The results of the maze variant with teleporting tile (second figure in the top row) show that methods incorporating neighborhood information (DNC, DNC w/o SA, knn) perform better compared to MinMax. The latter exhibits unstable learning behavior, since the coarse rounding step cannot resolve sharp changes in Q-values caused by the teleporting tile. We conjecture that, when the underlying Q-value distribution of a problem is non non-linear. the added benefit of considering more neighboring actions becomes more apparent. DNC is therefore able to provide high quality policies in more complex environments, comparable to knn. This result noteworthy, as MinMax is the only state-of-the-an method able to scale to very large SLDAS. We note that LAR did not complete the training required to learn action embeddings in the given time limit, hence only the first 2k episodes are shown for LAR. In the appendix, we provide boxplots showing the performance of the final learned policies. They suggest that convergence the maze environment is much more stable than perceived in Figure 3, as the observed variance is the result of the maze's 's reward spread.
The bottom row of Figure 3 reports results on the inventory and job-shop environments. For the inventory environment, observe that only DNC is able to learn performant policy, while VAC, knn and LAR simply run out of memory before finding a policy, and MinMax and DNC w/o SA converge to considerably less performant policy. Similar to the maze environment with teleporting tiles, the joint inventory problem has a more non-linear Q-value function due to joint order costs, and neighboring actions can result in significantly different rewards. Hence, incorporating neighborhood when selecting a discrete action and adding some randomness while exploring it proves advantageous.
The results for the job-shop scheduling enviromment (bottom- trightt graph in Figure 3) confirm the good performance of DNC. DNC outperforms its ablation DNC w/o SA and MinMax, while converging faster. This result demonstrates (i) the added value of considering multiple neighbors instead of only the nearest neighbor, highlighted by DNC w/o SA's advantage over MinMax, and (ii) the benefit of SA, highlighted by DNC's s outperformance of DNC w/o SA. We observe that MinMax still exhibits slight gradient at 20k episodes. To confirm that DNC outperforms MinMax after the latter's s convergence, we present an additional visualization in Appendix H. Figure 11, providing evidence of MinMax's and DNC w/o SA's convergence at comparable performance after 80k episodes.
Concluding, our experimental results show that DNC matches or surpasses current benchmarks for all SLDAS experiments. It equals the top performance in simple scenarios and competes effectively with knn and LAR - which use advanced learning representations - in complex cases with moderately large SLDAS featuring non-linear reward- and Q-value distributions. For very large SLDAS, DNC shows superior performance, since knn and LAR cannot scale beyond enumerable action spaces, and the remaining benchmarks, MinMax and DNC w/o SA, are consistently outperformed.
6 CONCLUSION
In this paper, we present novel algorithmic pipeline for deep reinforcement learning in environments with structured large discrete action spaces that enables to integrate an effective continuous-to- discrete action mapping in an actor critic algorithm. Our algorithmic pipeline shows two crucial advantages. First, does not require enumerating the full action space, nor does require storing the action space in-memory during the training process. Second, the perturbation scheme and search procedure allow for application space. We compare our approach against various state-of-the-ar benchmarks across three different environments. Our results show that our pipeline overcomes the benchmark's 's scalability limitations through a dynamic neighborhood evaluation. Our pipeline scales up action space sizes up 707 and shows comparable or improving solution quality across the investigated environments.
wide range of problems that exhibit a structured action
Our algorithmic pipeline shows significant benefit over benchmarks: (i) when the discrete action space is very large yet structured; (ii) when the environment exhibits non- linearitiies in the reward- and Quuunctio.. The promising results of DNC motivate future work to explore extensions of our pipeline to alternative neighborhood operators and selection criteria, efficient handling of infeasible actions and constraints, using graph neural networks efficiently evaluate neighborhoods.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
The code for running DNC and all benchmarks on the studied domains can be found in the attached supplement and https://github: com/ tumBAIs/ www.aa/ceiieiiooooooooooootttoee
Proofs of all lemmata can be found in the supplement. Furthermore, the supplement details comprehensive description considering the implementation of DNC in a standard actor-critic algorithm. Additionally, the supplement elaborates on the implementation of benchmarks.
ACKNOWLEDGEMENTS
We would like thank Yash Chandak for providing us with his implementation of the LAR approach. Moreover, we would like to thank Georgina Nouli for the discussions that helped us to substantiate the proofs for Lemmata 1, 2, and
REFERENCES
Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical Science, 8(1):10-15, 1993.
Robert N. Boute, Joren Gijsbrechts, Willem van Jaarsveld, and Nathalie Vanvuchelen. Deep rein- forcement learning for inventory control: A roadmap. European Journal of Operational Research, 298(2):401-412 2022.
Rudy Bunel, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda, A unified view of piecewise linear neural network verification. In Neural Information Processing Systems, 2017.
Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip Thomas. Learning action representations for reinforcement learning. In International conference on machine learning, pp. 941-950. PMLR, 2019a.
Yash Chandak, Georgios Theocharous, Chris Nota, and Philip Thomas. Lifelong learning with changing action set. In AAAI Conference on Artificial Intelligence, 2019b.
Hao Cui and Roni Khardon. Online symbolic gradient- based optimization for factored action mdps. In International Joint Conference on Artificial Intelligence, pp. 3075-3081. IJCALAAAI Press, 2016.
Hao Cui and Roni Khardon. Lifted stochastic planning, belief propagation and marginal map. In AAA/ Workshops, volume WS-18 of AAAI Technical Report, pp. 658-6664 AAAI Press, 2018.
Gabriel Dulac-Arnold Ludovic Denoyer, Philippe Preux, and Patrick Gallinari. Fast reinforcement learning with large action using error-correcting output codes for MDP factorization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 180-194. Springer, 2012.
Gabriel AnnocdArnold, Richard Evans, Hado van Hasselt, Peter Sunchag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv: 2015.
Gabriel Dulac-Arnold, Nir Levine, Daniel J. Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 11009):411-2468, 2021.
Tobias Enders, James Harrison, Marco Pavone, and Maximilian Schiffer. Hybrid multi-agent deep reinforcement learning for autonomous mobility on demand systems. Nikolai Matni, Manfred Morari, and George J. Pappas (eds.), Learning for Dynamics and Control Conference, volume 21 of Proceedings of Machine Learning Research, pp. 1284-1296. PMLR, 2023.
Matteo Fischetti and Andrea Lodi. Local branching. Mathematical Programming, 98(1):23-4 47, 2003.
10

---

Published as a conference paper at ICLR 2024
Sai Krishna Gottipati, Boris Sattarov, Sufeng Niu, Yashaswi Pathak, Haoran Wei, Shengchao Liu, Shengchao Liu, Simon Blackburn, Karam Thomas, Connor Coley, Jian Tang, Sarath Chandar, and Yoshua Bengio. Learning to navigate the synthetically accessible chemical space using reinforce- ment learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3668-3679. PMLR, 2020.
Pengjie Gu, Mengchen Zhao, Chen Chen, Dong Li, Jianye Hao, and Bo An. Learning pseudometric- based action representations for offline reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 7902-7918. PMLR, 2022.
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with a natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1621-1630. Berlin, Germany, 2016. Association for Computational Linguistics.
Ayush Jain, Andrew Szot, and Joseph J. Lim. Generalization to new actions in reinforcement learning. In Proceedings of the 37th International Conference Machine Learning. 2020.
Ayush Jain, Norio Kosaka, Kyung-Min Kim, and Joseph J Lim. Know your action set: Learning action relations for reinforcement learning. In International Conference on Learning Representations, 2022.
Minsu Kim, Jinkyoo Park, and joungho kim. Learning collaborative policies to solve np-hard routing problems. In M. Ranzato. A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 10418-10430. Curran Associates, Inc., 2021.
Mykel J. Kochenderfer and Tim A. Wheeler. Algorithms for Optimization. The MIT Press, 2019. ISBN 0262039427.
George Konidaris, Sarah Osentoski, and Philip Thomas. Value function approximation in rein- forcement learning using the fourier basis. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1):380-385, 2011.
Zhenning Li, Chengzhong Xu, and Guohui Zhang. A deep reinforcement learning approach for traffic signal control optimization, 2021.
Anuj Mahajan, Mikayel Samvelyan, Lei Mao, Viktor Makoviychuk, Animesh Garg, Jean Kossaifi Shimon Whiteson, Yuke Zhu, and Anima Anandkumar. Reinforcement learning in factored action spaces using tensor decompositions. ArXiv, abs/21 10. 14538,, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013.
Marius Muja and David G. Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11):2227-2444 2014
Michael Neunert, Abbas Abdolmaleki, Markus Wulfmeier, Thomas Lampe, Tobias Springen- berg, Roland Hafner, Francesco Romano, Jonas Buchli, Nicolas Heess, and Martin Riedmiller. Continoous-discrete reinforcement learning for hybrid control in robotics. In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura (eds.), Proceedings of the Conference on Robot Learning, volume 100 of Proceedings of Machine Learning Research, pp. 735-751 PMLR, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach Vitioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, performafoee deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bue E. Fox, and R. Gamett (eds.), Proceedings of the 33rd International Conference on Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
11

---

Published as a conference paper at ICLR 2024
Jason Pazis and Ron Parr. Generalized value functions for large action sets. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 1185-1192, 2011.
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Boehmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gradients. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 12208-12221 Curran Associates, Inc., 2021.
Paul J. Pritz, Liang Ma, and Kin K. Leung. Jointly-learned state-action embedding for efficient reinforcement learning. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, CIKM 221, pp. 1447-1456, New York, NY, USA, 2021. Association for Computing Machinery.
Brian Sallans and Geoffrey E. Hinton. Reinforcement learning with factored states and actions. J. Mach. Learn. Res., 1:1003-1088, 2004.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017.
Sahil Sharma, Aravind Suresh, Rahul Ramesh, and Balaraman Ravindran. Learning to factor policies and action-value functions: Factored action space representations for deep reinforcement learning. CoRR,
2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the Ist International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 387-395, Bejing, China, 2014. PMLR.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, Cambridge, MA, USA, second edition, 2018
Shengpu Tang, Maggie Makar, Michael Sjoding, Finale Doshi-Velez, and Jenna Wiens. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Arash Tavakoli, Fabio Pardo, and Petar Kormushev. Action branching architectures for deep reinforce- ment learning. In Proceedings of the Thirty-Second AAAI Conference on Artificall Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI'1,, AAAI Press, 2018
Guy Tennenholtz and Shie Mannor. The natural language of actions. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp.
PMLR, 2019.
Philip S. Thomas and Andrew G. Barto. Motor primitive discovery. In 2012 IEEE International Conference on Development and Learning and Epigenetic Robotics (ICDL), pp. 1-8, 2012.
Hado van Hasselt and Marco A Wiering, Using continuous action spaces to solve discrete problems. 2009 International Joint Conference on Neural Networks, pp. 1149-1156. 2009.
Wouter van Heeswijk and Han La Poutré. Deep reinforcement learning in linear discrete action spaces. In 2020 Winter Simulation Conference (WSC), pp. 1063-1074, 2020.
Nathalie Vanvuchelen, Bram de Moor, and Robert N. Boute. The use of continuous action representa- tions to scale deep reinforcement learning for inventory control. SSRN, 2022.
Gongju Wang, Dianxi Shi, Chao Xue, Hao Jiang, and Yajie Wang. Bic-ddpg: Bidirectionally- coordinated nets for deep multi-agent reinforcement learning. In Honghao Gao, Xinheng Wang, Muddesar Iqbal, Yuyu Yin, Jianwei Yin, and Ning Gu (eds.), Collaborative Computing: Network- ing, Applications and Worksharing, pp. 337-354, Cham, 2021. Springer International Publishing.
12

---

Published as a conference paper at ICLR 2024
Fengsheng Wei, Gang Feng, Yao Sun, Yatong Wang. Shuang Qin, and Ling-Chng Liang. Network slice reconfiguration by exploiting deep reinforcement learning with large action space. IEEE Transactions Network and Service Management, 17(4):217722111 2020.
William Whitney, Rajat Agarwal, Kyunghyun Cho, and Abhinav Gupta. Dynamics-aware embeddings. In International Conference on Learning Representations, 2020.
Xinquan Wu and Xuefeng Yan. spatial pyramid pooling-bace baaedd deep reinforcement learning model for dynamic job-shop scheduling problem. Computers & Operations Research, 160: 106401, 2023.
Jiaohong Xie, Yang Liu, and Nan Chen. Two-sided deep reinforcement learning for dynamic mobility- on-demand management with mixed autonomy. Transportation Science, 17(4):001--1046, 2023.
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, Grauman, N. Cesa Bianchi, Cesa-Bianchi, tion Processing Systems, volume 31. Curran Associates, Inc., 2018.
and R. Gamett (eds.), Advances in Neural Informa-
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1621-1632 Curran Associates, Inc., 2020a.
Tianren Zhang, Shangqi Guo, Tian Tan, Xiaolin Hu, and Feng Chen. Generating adjaceney- constrained subgoals in hierarchical reinforcement learning. In Proceedings of the 34th In- ternational Conference on Neural Information Processing Systems, NIPS'20,, 20, Red Hook, NY, USA, 2020b. Curran Associates Inc.
A PROOFS LEMMATA 1, 2, AND 3
Lemma Action similarity L given by
sup a.''E aata
1Q (a,a') la-a'l
ensuring that IQ (s, a)-
(* < L||a a' for all a' E..
Proof Since the action neighborhood A' finite and discrete, there exists a minimum Fuclidean distance ó 0 between any two distinct actions a, a' E A', i... la a' ||2 2 for & a'.
Consider any two distinct actions a, a' A' and their corresponding Q-values Q a) and (=(s,, a') E IR with state fixed. By the triangle inequality, we have:
05
-"sssa)-Q""ss.d -
+=*(s.a) (Q" -s (s) + (s.
Let QTax max Q (s(ssa) a) be the maximum Q-value over all actions in A'. From the triangle aE.A' inequality, follows that (Q"(s, a) ( (s, a')l < 2Q must hold.
Now, for any action pair a * a', we have ||a a' a'll2 2 8 and (Q" a) (s, a')l < 2Qmax a non-negative real number bounded by 2Q for a, a' A' satisfying * a'. Since the action space is finite, the number of ratios is also finite, and we bound the Lipschitz constant:
Hence, the ratio ("=..aa-Q"(s.ee"" |aaaal
Q* a) Q"
2Q
=
sup
a aata'
|| a'
Hence, exists and is finite, providing a measure action similarity.
13

---

Published as a conference paper at ICLR 2024
Lemma 2 If J is locally upward convex for neighborhood A' with maximum perturbation (d
around base action a, then worst-case performance with respect to is bound by the maximally perturbed actions a" E A" via Q" (s, a') z min Q (s, va A'.
a"EA"
Figure illustrates the intuition behind local convexity and our proof.
Quia":
Patertia loner
Gulw))
(2)
(m!")
Figure 4: Illustration of locally convex neighborhood of with respect the perturbed actions a'. DNC selects actions based on Q(a') and thus may return any a' E A'.. The convex property guarantees that J(a") I J(a'), Va' E A' for some maximally perturbed action a".
Proof Evaluating arg max Q (8, a)) may return any a E A', Qn might have arbitrary values. aEA Therefore, must prove that the performance bound holds for all A'. Via the local convexity of J around base action a, we prove that worst-case performance is bound by maximally perturbed action in A"
Let À E [0, 1]. a", a"",a" aa"" E A" and a' E A'. By definition of upward convexity, the following inequalities are satisfied.
min Q (s,aa)==
a"EA"
À min a"EA" ("(sa"") + A) min Q (s,a"))
d"EA"
AQ" (1 - (s, Q" (s, ((a") + (1 A)(a"
This result holds AA E [0.1] and all maximally perturbed actions. Now, we only need to prove that Va' E A 3 a a """) such that a' = Aa + (1 (11-))a² "" i.e., that linear combination of maximally perturbed actions can express all feasible actions a' A'.
Let us express neighbors via a' = ā + Pj for some j E {1,...,,NN) Moreover, let j+ E (Nd - (N 1), -..... Nd) be column indices corresponding to maximally positively perturbed actions and let j E [2Nd - (N 1),... 2Nd) correspond to maximally negatively perturbed actions, and let be the index of the non-zero entry of P,. Then, consider the maximally perturbed
actions A' Jt A'y., who only differ from on their Ith element. We can now express a'
a' = xA= + A
(5)
Here, we obtain the required À by solving Equation equation for X, for which the relevant perturbed entry Ptg Solving the equation leads to > P, yielding a value between and as -(de) < Pt < (de). Therefore, we can express all neighbors a' E A' linear combinations of maximally perturbed actions; hence, min Q" a") (s,, Va A'. E"EA""
2de
Lemma 3 Consider a neighborhood A' and improving actions satisfying (=,s > max Q a'), E A','' A'. In finite time, DNC will accept improving actions, provided that a'E.A'
(i) B and lo cool sufficiently slowly and (ii) a maximum perturbation distance (d set such that all action pairs can communicate.
14

---

Published as a conference paper at ICLR 2024
Proof The proof is structured into three steps: first, show that DNC's simulated annealing procedure behaves as a non-homogeneous Markov chain that searches over the action space. We then show that this Markov chain is aperiodic and irreducible. Finally, show that an arbitrary action can be reached with positive probability in a finite numher of steps.
1. Simulated annealing procedure behaves Markov chain We first establish the preliminaries of the simulated annealing procedure used in DNC, which is necessary to describe the procedure Markov chain (cf. Bertsimas & Tsitsiklis, 1993).
1. A a finite discrete action set.
2. There exists real-valued cost function Q" minima A C .A. Specifically, we associate each state-action pair with an estimated Q Q-value Qu, a.) IR. Since state is fixed while executing the simulated annealing algorithm, omit its notation moving forward.
S A R, with proper subset of local
3. Every action a E AA has non-empty neighborhood Aa S A that includes itself, such that Aa > This can be ensured by setting appropriate maximum perturbation distance (de) E R+- As DNC performs perturbations on each individual entry in the action vector, it follows that all feasible entries (and thus all actions) in the finite action space can be constructed through perturbation of neighboring entries. Finally, given that the Euclidean distance a symmetric metrie, it follows that a' Aa + a Aa'.
4.
When we find non-improving neighbors k which happens in finite time given that the action space is finite there exists a set of positive probabilities Pa,a', a * a' that reflect the probability of evaluating neighbor a' from a. The sum of probabilities satisfies La'eAr(a) Pa.a' 1. Specifically, in (1.14) of Algorithm 1, we associate T&T to each krand E K. As mentioned, we always reach (l.14) in finite time, due to the guarantee of finding non-improving actions in a finite space.
5. There a temperature scheme B N + (0, o0). with representing temperature time t E N and B, 2 Be+1, Vt. Similarly, the scheme k : N + [0, |Al]] returns the number of neighbors i; generated time f, with k2 2 kk+1, Vt. As preliminary for the remainder of the proof, the temperature must cool sufficiently slow to allow finite-time transitions between any a, a' A.
6. At an initial action is given. This action is generated by the contimuous-to-diicrete mapping function à + a, as detailed in the paper.
Given these preliminaries, we define the simulated annealing procedure used in our DNC as non-homogeneous Markov chain A Ap, A1, A2.... ... that searches over A. Here, A, is a random variable that denotes the accepted action after move f, i.e., A, = at, ag E A.
Let us denote 11 = arg max (Q(s, k)) and x = max (0, ((e.a)-Q(ekki) B
Then, from the algorith-
REK'
mic outline, we derive that the probability of AAt1 = a' when A = a is given by (exp(<) + (1 exp(x))
[T] if a' k a' + k
(6)
(xp())((s)) [K]
2. Markoy chain is irreducible and aperiodic We now show that the transition probabilities of the Markov chain imply it is (i) irreducible and (ii) aperiodic, which necessary and sufficient conditions to prove that P(Acer a' A. a) > 0 for some finite 7 E N.
(i) Irreducibility of A: To show that the Markov chain is irreducible, suppose we set the maximum perturbance distance to (d
max ||a a' 122 i.c., equaling the finite upper
a.a'
bound on perturbation. Now, suppose we wish to move between arbitrary actions a = (d.)vne(11...N)) and a' = (o....ne The chosen perturbation distance ensures that action entries can be perturbed to any target value o', {a,, (de)....., an + (de)). By perturbing each entry a, individually, we can reach a' within N steps, as Equation equation ensures a positive probability of accepting such perturbations. To generalize the established
15

---

Published as a conference paper at ICLR 2024
result, observe that may relax to (de) v max la a' a212 and can construct similar a.a'Ed
rationale for some smaller that satisfies communication between action pairs as well.
(ii) Aperiodicity of A: As accept non -omprovo actions with a probabiliiyy and Ea* A* with no improving neighbors, a one-step transition probability P(A,+1 = a" A, = a²) > 0 is implied by Equation equation 6. By definition of aperiodicity, identifying one aperiodic action suffices to prove that the entire Markov chain is aperiodic.
3. All actions are reachable with positive probability in finite time We have shown that the Markov chain is irreducible and aperiodic, proving that all actions belong to the same communicating class. By the FerronFFrobenuus theorem, V(a, a'), there exists a finite т such that P(A+++ Aa a) (P* )aa' O, where (Pr)aa is a 7-step transition matrix.
This result shows that there is a positive probability of reaching action from action a in T steps. Thus, given sufficiently large perturbation distances and an appropriate cooling scheme, DNC enables to find improving actions outside the initial neighborhood.
B FULL SET OF MILP CONSTRAINTS AND FURTHER RESULTS
In addition Constraints to 4, the following constraints are required to describe the DNN (Al 2 3)
yd, 2 Σ
Wd-1.dd 1. Vd
(7)
d1 4-1EDILL
yd, Szd. M
(8)
yd S(1 -
zdi M+ +
Σ
Wd Idi-1
(9)
de 1-1ED
EdirED Wdb dd ydc-1
2d 2
(10)
M
EdimieDin, Wd wd- Udi-1
2d, 21 +
(11)
M
zd. E 1).
(12)
These technical constraints are required to describe and ensure consistency of the ReLU values of the DNN, described in Bunel et al. (2017) or Heeswijk & La Poutré (2020). Moreover, to further bound and efficiently solve the MILP, we introduce the following branching constraints, which bounds the maximum Hamming distance & between the base action and the resulting optimal action ā", hence, further restricting the neighborhood and consequently the search space (Fischetti & Lodi, 2003):
k
Σ Mg (a' - =āa=ay
-af) +
Σ j:āz=ay'
My (ay -a")
Σ
Mg (at + +a7),
(13)
juaty <ayzay
where H
and
ax
a
i" a; + a 47 2,
vj: < < oj.
(14)
We report results for two approaches involving solving the MILP. We solve the MILP using Gurobi 10.00 and report results on the maze environment with an action space size of 212 in Figure 5. Figure 5a shows the results for solving the MILP during both training and testing (pure MILP) as well as the results of using DNC during training and solving the MILP during testing only. We refer to the latter approach as hybrid. First, we observe that if we solve the MIIP during both training and testing, the time limit is reached before convergence (cf. Figure 5a). When using the hybrid approach, we observe a worse performance compared to DNC. This performance difference between DNC and hybrid may be explained by the fact that DNC is able to find more distant actions in terms of Hamming and/or Euclidean distance by means of the SA procedure, whereas the MILP is confined to the original neighborhood's 's bounds. The results indicate that DNC benefits from the SA procedure's s ability to escape the initial (uferedefined) perturbation boundaries case the best neighbor happens to be outside them.
16

---

Published as a conference paper at ICLR 2024
MinMax
DNC weo
Hybrid
Maus 2-12 actions
fling
Total exppeted teturns
80
80
60
20
20
-20
Epicodes (c30k)
Eplaodes DOLOE)
(a) Maze, actuators, pure MILP and hybrid.
(b) Maze, 20 actuators teleporting tiles, hybrid.
Figure Average total expected returns during testing for 50 random seeds over the training iterations in the maze environment, including the performance of MILP and hybrid approach. The shaded area represents the 2 standard deviation training seed variance corridor.
C ENVIRONMENTS
Maze Our implementation follows the implementation described in Chandak al. (2019a). We set the episode length to 150 steps and provide reward of -0.05 for each move and 100 for reaching the target. The target, wall, and initial agent position follow the illustration in Figure 6a. Here, the red dot represents the agent with the actuators, the grey areas are walls which the agent cannot move through, and the yellow star is the target area. The agent cannot move outside the boundaries of the maze. Whenever wall or outside boundary is hit, the agent does not move and remains in the same state. Action noise was added to make the problem more challenging. On average 10% of the agent movements are distorted by noise signal, making the agents' movements result in slightly displaced locations. In Figure 6b we report the variation of the maze environment, wherein the agent starts in the lower right corner, receives reward of +100 when reaching the target, reward of -0.05 for each step, and a reward of -20 when entering the teleporting tile (grey rectangle in the middle). When entering the teleporting tile the agent's position reset to the lower right corner. This environment has the same action noise as in the original maze environment.
(a) Maze with wall.
(b) Maze with teleporting tile in the middle.
Figure 6: Illustration of the maze environment.
Inventory Replenishment We mostly follow the implementation detailed in Vanvuchelen al. (2022), wherein they consider a retailer managing uncertain demand for different items in its warehouse. Compared to them, costs per item E I are as follows: holding costs h; = 1, backorder costs b, = 19, ordering costs to the range [0, 66].
shorter episodes to decrease the computational burden. The
Og 10 and the common order costs O 75. The order-up-to levels We sample the demand rate from the Poisson distribution, with half of the items having demand rate of X; 10, and the other half of the items A; 20. We initialize all inventory levels 25. Every
17

---

Published as a conference paper at ICLR 2024
episode comprises 100 timesteps. The reward function can be denoted by:
R Σ (haT beT + o,a;) + 01 (Σ a,,300)
(15)
where 1 and Lie indicate all positive and negative stock levels, respectively. 11 I 9,,00) is the indicator function that indicates if at least one product is ordered.
Job-shop scheduling Each machine has different energy consumption per job. Whenever the number of jobs on machine is higher than 75% or lower than 50% of (the maximum number of jobs per machine) the machine's deterioration factor w, is increased or reduced, respectively, The deterioration factor directly impacts the efficiency of machines, and hence, it affects the energy consumption per job. We consider the increase in deterioration to be caused by wear, i.e., over-use, and the reduction of the deterioration to be achieved through machine repair, which are only possible when the utilization of the machine is low. Deterioration and repairs a uniform distribution. Deterioration causes an increase of the deterioration factor, bounded by Aw, [0.05, 0.4]. Repair causes a decrease in deterioration factor, Aw; E [-0.4, [-0.4,-0.05) -0.05). The deterioration factor is multiplied by the energy consumption b; to obtain the energy consumption per job. The deterioration factor W, of all machines is 1.0 in the first time step, and can never drop below 1.0 through repairs. We bound the energy consumption per machine by M. The reward function is given by:
stochastic and drawn from
N R = Σ (ap - (i,(min M)) a(a).
(16)
where are the number of jobs allocated to machine i, is the reward for each finished job, and (a) the load-balancin reward that provides negative reward for an unbalanced allocation using the standard deviation of the allocated jobs to machines. We set the reward factors to 3 and M 100. The value of 100. We sample the energy consumption à; per machine from the uniform distribution, with bounds [1.0, The results in the paper correspond problem with N machines.
D IMPLEMENTATION DETAILS
Integration of DNC in an actor-critic algorithm Algorithm 2 details the integration of DNC into an actor-critic reinforcement learning (RL) algorithm. Specifically, we initialize the network weights w and 0 of the critic and actor respectively (1.1), and set hyperparameters such as the Gaussian o and the critic- and actor learning rates Oer and Oaac (l.2). After initializing a state s (l.4), we loop through each time step of an episode (I.5). We obtain continuous action à by sampling it from To according to the learned μ4 and a a Gaussian distribution and the hyperparameter (1.6). Next, we obtain discrete action a' by applying DNC (1.7), whose details are provided in Algorithm I in the main body of the paper. We then apply a" to the environment, observe reward r and next state s' (1.8). We obtain the next state's continuous action à' (1.9) and then its discrete action a" (I.10). Using losses based on the observed TD-error (1.11), we update critic (1.12) and actor (I.13) weights. Note that we use both à and TD-error based on ä" and a" hence using slightly off-policy information to compute the actor loss. However, since in practice DNC does not move far away from à using off- off-policy information in the actor weight update does not heavily impact on learning stability.
Details the Neural Network Architecture When applying a deep network architecture, use two hidden layers with ReLU activation functions for both actor and critic for DNC and all benchmarks. In Section F provide further details for the architecture per environment. For all environments, we use tanh output layer for the actor and do not bound the output of the critic.
We train the actor and critic based on the stochastic gradient descent algorithm implemented in PyTorch and use Huber loss to train the critic and ensure stable weight updates.
Other Implementation Details We employ a discretization function g()) to obtain a discrete base action a from the continuous action à.
18

---

Published as a conference paper at ICLR 2024
Algorithm 2 Actor critic pseudo-code with DNC.
1: Initialize network weights w. 0
2: Set hyperparameters: a, Clars Clac
3: for each episode do
4: Initialize 8
5: for each time step do
6:
< T (based on or)
7:
a" (NC(a) (see Algorithm
8:
Apply a' to environment, observe reward r, and successor state s' à' < (T(s') (based on σ)
9:
a = DNC
11:
r + 2(s 10ss('a''' a" w) - Q(s ,", w)
12:
w - aer V w
13:
< + andd Vo log (8 à)
g()) clip(á)
Cmin
(Amaax
Ominn
amin
Cmax
Cmin
with
Cmin+
if à Cmin+
clip(a) Cmax
if Cmax:
à
otherwise,
denoting clipping function, as similar Vanvuchelen al. (2022). The discretization function has multiple hyperparameters that need to be selected based on (i) the output layer activation Cmin, Cmax; Omin; and Omax- Since
function, and (ii) the action dimension. These hyperparameters the action is sampled from a distribution, an action might overflow and result in non-existent actions, hence, clipping is required. Each value needs be set to an appropriate value. We use Cmin = 1, Cmax for clipping, since we employ a tanh activation function for the output layer. The values for Omin and amax are set depending on the environment; we use [0. 1] for maze, [0, 66] for the inventory environment, and j0, 100] for the job-shop environment.
We represent states across all environments by means of a Fourier basis described in Konidaris et al. (201 1) and applied in Chandak et al. (2019a). In the maze environment we use Fourier basis of order three with coupled terms. For the inventory and job-shop environments, we use decoupled terms to maintain reasonable state vector size.
E BENCHMARKS
We consider four benchmarks and an ablation: VAC, MinMax (MinMax), knn, LAR, and DNC without SA. For full and detailed explanation of the benchmarks, we refer Sutton & Barto (2018), Vanvuchelen et al. (2022), Dulac-Arnold et al. (2015), and Chandak et al. (2019a), respectively, Here, we restrict ourselves to a short description of each benchmark and explain how we embed these benchmarks in an actor-critic algorithm similar to Algorithm 2.
We employ standard actor-critic method as baseline. For this method we employ a categorical policy, i.e., π describes the probability of taking action a when being in state s. We denote the policy by x(a)a s) to emphasize that π a distribution. VAC's implementation follows Algorithm as detailed above, with the only difference that we obtain the discrete action directly from the actor, instead of obtaining continuous action and subsequently using DNC.
VAC
MinMax The MinMax benchmark uses actor-critic framework, in which the actor outputs continuous action vector and function g is applied in the same way as for DNC. We obtain the algorithm corresponding to MinMax by exchanging DNC in lines and 10 of Algorithm 2 by g.
knn The Ann approach uses an approximate nearest neighbor lookup (Muja & Lowe, 2014) to find discrete neighbors in the space A based continuous action à. The mapping function h finds the
19

---

Published as a conference paper at ICLR 2024
nearest discrete neighbors in terms of Euclidean distance:
hg
arg min a||2.
aE.A*
After finding k neighbors, the neighbor with highest Q-value is chosen and applied to the environment, using a similar approximate on-policy rationale as applied for DNC. Note that the critic is only used to select an action after all neighbors have been generated. In Section F we present different values of ki over which we search for the best performing hyperparameter setting for knn. To embed knn in an actor-critic algorithm, we modify Algorithm 2 in lines 7 and 10 as follows: instead of applying DNC, we search for the k-nearest neighbors of à and â', and, subsequently, obtain a" and a" by selecting the neighbor with highest Q-value.
To setup the LAR benchmark, we use the code that implements the work presented in Chandak et al. (2019a) and that was kindly shared with us. In the following we briefly describe the algorithm. Before training the RL agent, unique action embeddings E R for each discrete action a. We use buffer that stores state, action, and successor state transition data to feed the supervised learning model. We set the maximum buffer size to 6e5 transitions and obtain these transitions from, e.g., a random policy. The supervised loss is determined using the KL-divergence between the true distribution P(a, [8,, 814-1) and the estimated distribution Pa(ay) St, 8141), which deseribe probabilities of taking an action a, at time step t when having certain state tuple (8t, 81+1). Across all environments, we use a maximum of 3000 epochs to minimize the supervised loss. We note here that the training process always converged before reaching the 3000 epochs limit. We detail the different sizes of the two-layer neural network architecture, used in the supervised learning procedure, in Section F. Moreover, note that the size of may be both larger or smaller than the discrete action's 's size. It is up to the user determine the embedding size, hence, it is a hyperparameter whose values we also report in Section F.
LAR
apply an initial supervised learning process to learn
Following the initial supervised learning process, we proceed in similar manner to Algorithm 2. First, we obtain e from the continuous policy π (cf. line 6 in Algorithm 2). Second, we find the embedding e' closest to based corresponding to e' (cf. line 7 in Algorithm 2). At the end of each step of the episode, we update the continuous representations e' of by performing one supervised learning step.
L2 distance metric and look up the discrete action
DNC without SA Algorithm 3 details the DNC algorithm without the SA procedure, used for our ablation study. First, we obtain a discrete base action ā (I.1) and find its discrete neighbors by DNC (1.2). We obtain the critic's Q-values (I.3), and subsequently select the action with the highest Q-value (1.4).
Algorithm 3 Dynamic Neighborhood Construction w/o SA
1: Initialize ā + g(ā), ā" < a
2: Find neighbors A' to ā with P.j
3: Get Q-values for all neighbors in A'
4: ā' AA, with a" arg max Qw(
5: Return ā²
F HYPERPARAMETERS
In this section, we detail the hyperparameter settings used across the different environments. To this end, we provide an overview of hyperparameter settings Table and discuss specific settings that we over all environments. N/A indicates that the respective method did not yield performant policy for any hyperparameter setting.
We applied search over the reported set of values in Table 2 (column "Set of values") to choose the best hyperparameter setting. Note that a value of zero nodes of the critic and actor layer corresponds to shallow network. Moreover, do not report hyperparameter settings for MinMax separately, as its only hyperparameter corresponds to Cmin and Cmax, which we set to the minimum, resp. maximum value of the actor's output layer described in Section D.
20

---

Published as a conference paper at ICLR 2024
We study both (i) learning the second moment of the Gaussian distribution, 0, and (ii) setting to constant value. In Table 2, a indicates that a was learned by the actor. We found that a constant o often led to faster convergence without performance loss.
The DSC-specific parameters are (i) the neighborhood depth d. (ii) the k-best neighbors to consider, (iii) the acceptance probability parameter B3, and (iv) the cooling parameter We do not tune B and set it to an initial value of 0.99. The cooling parameter expresses by how much the parameter and / are decreased every iteration of the search, terms of percentage of the initial values of both parameters. We set k respective to the size of neighborhood [AA).
Table 2: Hyperparameters, set of values, and chosen values.
Chosen values
Hyperparameters
Set of values
Maze
Maze w/ teleport tiles
Inventory
Job-shop
(critic learning rate)
10-33,1033,000 10
10-2
10-2
10-3
10-4
Overall
(Pac (actor learning rate)
{10 10 10-0 }
10
10 20-2
10 4
5 10-00
(1.0.25, 0]
I
1
M actor NN nodes/layer
(0, 64, 128)
0
64
0
critic NN nodes/layer
(0,32, 64, 128]
32
128
32
knn LAR
e)
[0.5 s), [a]}
[a]
[8]
n/a
n/a
# supervised NN nodes
(0,
0
n/a
n/a
I:
[1,2,20,100)
2
100
n/a
n/a
(1.2.5.10)
10
DNC
k
[ [10%_50%
10%
10%
10%
10%
(10%.255..5%% 75%%
25%
25%
10%
10%
G COMPUTATIONAL RESOURCES
Our experiments conducted on high-peerfrmance cluster with 2.6Ghz CPUs with 56 threads and 64gb RAM per node. The algorithms are coded in Python 3 and we use PyTTorch to construct neural network architectures (Paszke al., 2019). For the maze environment, having relatively long episodes, the average training time was 21 CPU hours. The inventory and job-shop environments took on average 12 and 10 CPU hours train, respectively.
H COMPLEMENTARY RESULTS
In this section, provide complementary results that support the statements in the main body of the text. First, we present the memory usage and step times of the studied methods over different problem sizes. Next, show additional convergence curves and boxplots for the maze environment which clarify the performance difference between the various methods. We conducted an additional robustness study with randomized initial agent positions for the maze environment, show evidence of MinMax's 's and DNC w/o SA's convergence below DNC's s average performance in the job-shop scheduling problem, and provide exploration heatmaps for the maze environment.
Memory consumption DNC exhibits a consistent memory usage, even as the complexity of tasks increases, which beneficial in real-world implementations with limited hardware. Our results, presented in Table 3, show that while the memory requirements for KNN, LAR, and VAC rise substantially when scaling from a maze of size 212 (maze with actuators) to 10 (job-shop scheduling problem), the memory consumption for DNC remains stable at 68 to 73 MB. The memory consumption in the case of KNN, LAR, and VAC is driven by the need to set up a matrix containing all discrete actions. For example, in the case of the job-shop scheduling problem this would be matrix with 5 rows and 1000 columns. We obtained the consumed memory using the Python profiler guppy.
Algorithm step time Figure depicts each algorithm's 's step time, i.c., the average duration of obtaining decision from the policy and applying it to the environment, within episode during
21

---

Published as a conference paper at ICLR 2024
Table 3: Required MB heap consumed per algorithm for the the maze and job-shop environment, The action space size is displayed in parentheses in the top row.
Algorithm
Maze (2
Maze (2
Job-shop (10"
DNC
68 MB
68 MB
73 MB
DNC w/o SA
68 MB
68 MB
73 MB
MinMax
68 MB
68 MB
73 MB
KNN
68 MB
252 MB
373,000 MB
LAR
68 MB
252 MB
373,000 MB
VAC
68 MB
252 MB
373,000 MB
testing. As we apply DNC during both testing and training. the reported step times also apply during training. Our findings suggest that while SA increases training time, its benefits in terms of search quality may outweigh these computational costs, especially if the action space is too large for other neighborhood--asee methods to (i) learn at all due to memory restrictions (kNN, LAR) or (ii) learn less performant policies (MinMax, DNC w/o SA) due to inaccurate mappings. During training, longer rumning times acceptable the focus is model accuracy and learning, not speed. In testing and practical implementation, DNC offers step times in the range of milliseconds to few hundredths of second, hence remaining practical for real-time decision-making Note that step time metrics depend on system specifications and may vary with different hardware and software efficiencies.
2.15
LAX
Menaa
DNC wib SA
DWC
lnn
Mnlox
DNC with SA
DNC
(a) Maze 212
(b) Maze w/ teleporting tiles 220
0.02
0312
0.04
0.00
0.13
0.00
0.04
0890
0.000
0.00
0.02
DsC
(c) Inventory 20 items.
(d) Inventory 40 items.
(c) Job-shop.
Figure 7: Average step time in seconds in the maze, inventory, and job-shop environment over 50 seeds during testing.
Additional convergence curve To further illustrate the results in the maze environment with teleporting tiles, we provide an additional graph that shows the convergence curves excluding DNC w/o SA in Figure 8. As can be seen, the confidence intervals of DNC and MinMax overlap only slightly, with DNC converging to a considerably more narrow variance corridor.
Testing performance for the maze environment Since the confidence intervals for the maze domains overlap,
difficult to clearly observe performance differences. Therefore, we show boxplots of the total expected returns for the final learned policy, i.e., the policy found in the last training episode, in Figure 9. the agent finds the goal, the episode's total reward is close to 100. the agent does not find the goal, it is -7.45. due to the small negative step rewards collected over an episode. Consider, for example, DNC in Figure 9a, wherein the agent finds the goal in 49 out of 50 seeds and in one seed the agent fails to do so. The failed seed is outlier. This example explains the large confidence intervals as shown in the convergence curves. In this example, the standard deviation already amounts to R 15, even though there is only outlier.
22

---

Published as a conference paper at ICLR 2024
MinMax
DNC
100
Maze (wi to apprrtnng Lima) -2"20 actions
89
Tala
-20
Edleodes Cxl 1100
Figure 8: Average total returns during testing for 50 random seeds over the number of training iterations in the maze environment with teleporting tiles for DNC and MinMax. The shaded area represents the 2 standard deviation training seed variance corridor.
VAC
LA0
DRG we SA
DRC
Minbax
DWC
DWC
(a) Maze 2 actions.
(b) Maze (w/ teleporting tiles) -
actions.
Figure 9: Total expected returns during testing for 50 random seeds in the final episode.
Maze environment with randomized initial positions To test the robustness of learned policies, we conducted further testing the final policy in a maze environment featuring random starting positions. To this end, used the policies obtained for each seed on the original environment (with a fixed initial position) and executed these policies over 100 episodes with random initial positions. We took the average performance of these 100 episodes and again averaged over the random seeds. The resulting outcomes, detailed in Figure 10, show no significant deviation from earlier results in terms of performance and variance over seeds, implying that DNC learned robust policy.
VBC
1.88
100
DNC wO 54
DNC
knn
ManMax
DNC
DNC
(a) Maze 222
actions.
(b) Maze (w/ teleporting tiles) 20
actions.
Figure 10: Total returns during testing for 50 random seeds in the final episode, using random initial positions.
Convergence for MinMax and DNC w/o SA in the job-shop scheduling problem Figure 11 we report the convergence graphs of MinMax's 's and DNC w/o SA's average performance in the job-shop scheduling problem over 80k episodes to provide evidence of their convergence below DNC's average performance.
23

---

Published as a conference paper at ICLR 2024
MinMax
DNC w/o
Job-shop 10
35000
Total expected returns
30000
20000
15000
10000
5000
Episades (x10k)
Figure 11: Average total expected returns during testing for 50 random seeds over the training iterations in the job-shop scheduling problem, MinMax and DNC w/o SA only. The shaded area represents the 2 standard deviation training seed variance corridor.
Maze heatmaps We visually compare policies for the standard maze environment. Figure 12 shows exploration heatmaps for all methods (excluding the ablation) for the 12 actuator setting of the maze environment without teleporting tiles. Here, the more frequently a location is visited, the brighter the color, i... from least visits to most visits: black-red-orange- orange-yellow, We note that the start of training, the movement of the agent is still random. However, as the policies converge, a clearer path becomes visible, given the 10% action noise. VAC unable handle the large action space and gets stuck in the lower left corner. knn and MinMax eventually find comparable policy that reaches the goal state, albeit the shortest path is not found. seems that both policies learned to stay far away from the wall, as hitting the wall often results in getting stuck. Both LAR and DNC found policy that tracks more closely around the wall, hence taking a shorter path to the goal state. However, LAR got stuck at the lower boundary of the grid for number of episodes, whereas DNC displayed more productive learning behavior.
24

---

Published as a conference paper at ICLR 2024
Expl crptoration +eatmap
Exgloration Heatmap
Exploration Heatmap
100k pon cortinote
100r bon in Cortinate
60
20
40
3008
50
60
100x positin in coordinate
100x position in coordinate
120x positio inx coordinete
(a) Heatmap VAC
(b) Heatmap knn
(c) Heatmap MinMax
Exploration Hcatmap
Exploration Heatmap
L00 pootzn #1 coaromne
10tk
100x coartiiate
100x postion
(d) Heatmap LAR
Heatmap DNC
Figure 12: Exploration heatmap over all training episodes of each method for the 12 actuator case.
25


Reviews:
[{"review_id": "wSF2qWO5OS", "reviewer": "Reviewer_ZSBT", "summary": "This paper addresses the problem of reinforcement learning in large discrete action spaces, which vanilla techniques typically cannot handle, and require adaptations. The authors propose a technique that, similarly to other works, outputs a continuous action, which is then mapped to a valid discrete action that is executed in the environment. Their proposal applies for action spaces that are regularly structured (e.g., an equally-spaced grid), which allows the method to circumvent needing to store the valid actions in memory. Instead, to map to a discrete action, a simulated annealing search is proposed, that is shown (via reasonable assumption and a standard analysis technique) to yield actions that improve the (estimated) Q-value. The method is evaluated in environments with an exponential number of actions, showing similar performance with prior methods in regimes with less actions, and better performance in regimes with more actions.", "questions": "**C1**. The paper refers in several places to approaches for \"unstructured\" LDAS (abstract, intro, figure 1, etc.). This is somewhat of a misnomer since these problems *do* exhibit structure (i.e., the action space is such that actions that are close in embedding space yield similar Q-values and lead to similar outcomes when actuated in the environment). I think a better term would be *irregularly* structured. Similarly, the proposed method applies to *regularly* structured action spaces.\n\n**C2**. Related to the second point of W2 above, the paper mentions the use of \"SA to efficiently search across different and potentially better neighborhoods\" (Discussion on p6). While this statement potentially applies for the memory efficiency, it certainly doesn't in terms of time, and should be qualified. SA in general is not computationally efficient.\n\n**C3**. Small nitpick: \"Constraints 2\" -> \"Constraint 2\", etc. in the text at the end of Section 2.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1**. The proposed technique is simple, elegant, and rigorously analyzed. It is also shown to work well empirically in environments that satisfy the required conditions.\n\n**S2**. The writing of the paper is excellent and clear.", "weaknesses": "**W1**. My primary criticism is that the considered environments and scenarios where the technique applies are somewhat contrived. If one is faced with such a huge decision space, we would typically expect to spend the time in the modelling stage of the problem to design an action space that is substantially more manageable. For example, in the maze environment, we could design a discrete set of actions (move left, etc.), with the actual execution being handled by lower-level control primitives. Indeed, this needs to be performed for each individual problem (as the authors do mention).\n\n**W2**. I also have some concerns about the evaluation:\n\n- Firstly, for the maze environments, the variability of the techniques is such that the confidence intervals overlap substantially, and it is not possible to draw reliable conclusions from these figures alone. Would this still happen with substantially more seeds (e.g. 50+)? Alternatively, would another procedure (e.g., running many episodes with randomly initialised positions) yield more reliable (i.e., with non-overlapping CIs)?\n- The simulated annealing search procedure must introduce a computational overhead compared to picking the best action greedily (e.g., as in DNC w/o SA). This is not mentioned, and the impact on runtimes is not analyzed or discussed. This needs to be addressed, accompanied by measurements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "7Xxkeila4S", "reviewer": "Reviewer_x32f", "summary": "Given the need in fields like inventory management, an efficient method for RL with structured large discrete action spaces (n-dimensional lattices) is proposed. First a continuous action is generated and discretized, then through simulated annealing with perturbation defined by other actions on the lattice with low hamming distance, a final proposed discrete action is obtained. This avoids the necessity of constructing extremely large nearest neighbor graphs, or solving a linear program on every forward pass. The convergence for the action selection process is proven, and the method is evaluated in two simulated domains with strong results over baselines.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The method is well-motivated\n- Results are strong over baselines in Figure 3\n- Components are ablated", "weaknesses": "I should first couch my review by noting I'm not the most familiar with the literature in this area, so this is an educated guess:\n\n- The maze domain seems a bit too trivial to be useful, it is informative for a demonstration of the method, but unlike the inventory management environment, I'm not sure what the real-world justification might be. I would prefer to have at least one more grounded and complex environment (perhaps a video game with many different possible actions, perhaps a multi-agent setting? I'm not the most familiar with the domains in this subfield).\n- Perhaps this is my unfamiliarity with the domain, but sometimes the text is quite hard to follow. I think part of this is the reliance on lots of acronyms (LDAS, SLDAS, MILP, SA), but also the claim in Section 2 \"we formulate the task of finding a Q-value maximizing a as a mixed-integer linear program\" was a bit confusing on first read, as really the authors are proposing an approximate solution, so saying this upfront might be a bit more clear.\n- Would be nice to see MILP results in Figure 5 against the proposed method and other baselines in Figure 3, and the discussion at the end of Appendix B is informative and it may be nice to have a note in the text", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Mia9e1242o", "reviewer": "Reviewer_kH6M", "summary": "The authors present an approach for learning in environments with large, discrete action spaces. Specifically, they learn policies in a continuous space that can be mapped to the discrete actions. The mapping the propose leverages structure in the discrete space in which it performs a localized search to efficiently perform the mapping.", "questions": "Tiny nitpick: The second sentence in Problem Definition --- it would read better to describe the states and actions in the order you introduce them.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality:** The work presented in this paper is novel as far as I know. They propose an approach that has not been done before that attempts to mitigates drawbacks exhibited by other algorithms.\n\n**Quality:** The problem is well-motivated and the drawbacks of current SOTA approaches for the problem are identified and the authors describe sufficiently how their approach attempts to tackle one of these issues. While I have not delved thoroughly into the appendix to check every bit of the theory, the sketched out lemmas seem sound. The experiments conducted were reasonable and thorough enough (I appreciate the ablation study performed.)\n\n**Clarity:** Easy to read and understand.\n\n**Significance:** I believe this work could be impactful to others in the area.", "weaknesses": "My one issue is with the first set of experiments in the maze. The results do not really demonstrate that DNC actually provides any advantage over the other baselines. While the second set of experiments do, I think maybe adding another domain may support performance claims by the authors. Alternatively, if the argument is that the performance of DNC is competitive to other SOTA, what other benefits may it provide (better wall-clock time, memory usage, etc.)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)