Speeding up Policy Simulation in Supply Chain RL
Authors: Vivek Farias
Joren Gijsbrechts
Aryan I. Khojandi
Tianyi Peng
Andrew Zheng
Venue: ICML 2025 poster (2025)
Keywords: Parallel Computing
Markov Decision Process
Policy Evaluation
Supply Chain
Operations Research
Primary area: reinforcement_learning->everything_else

Abstract: Simulating a single trajectory of a dynamical system under some state-dependent policy is a core bottleneck in policy optimization (PO) algorithms. The many inherently serial policy evaluations that must be performed in a single simulation constitute the bulk of this bottleneck. In applying PO to supply chain optimization (SCO) problems, simulating a single sample path corresponding to one month of a supply chain can take several hours. We present an iterative algorithm to accelerate policy simulation, dubbed Picard Iteration. This scheme carefully assigns policy evaluation tasks to independent processes. Within an iteration, any given process evaluates the policy only on its assigned tasks while assuming a certain ‘cached’ evaluation for other tasks; the cache is updated at the end of the iteration. Implemented on GPUs, this scheme admits batched evaluation of the policy across a single trajectory. We prove that the structure afforded by many SCO problems allows convergence in a small number of iterations independent of the horizon. We demonstrate practical speedups of 400x on large-scale SCO problems even with a single GPU, and also demonstrate practical efficacy in other RL environments.

Speeding Up Policy Simulation in Supply Chain RL
Vivek Farias Joren Gijsbrechts 2
Aryan Khojandi Tianyi Peng Andrew Zheng?
Abstract
as dynamic optimization problems, albeit with intractable state-spaces that must track inventory and other resource levels across large number of products and nodes. The development of detailed simulators ('digital twins') of sup- ply chains in recent years has made SCO problems a ripe target for reinforcement learning. prime example of such target with immense economic significance is the so-called Fulfillment Optimization (FO) problem (Amazon. com, Inc., 2023; Acimovic & Graves, 2015; Acimovic & Farias, 2019; Zhao et al., 2022; Liu et al., 2023), which will be main focus of this paper.
Simulating a single trajectory of a dynamical sys- tem under some state-dependent policy is core bottleneck in policy optimization (PO) algorithms. The many inherently serial policy evaluations that must be performed in single simulation consti- tute the bulk of this bottleneck. In applying PO to supply chain optimization (SCO) problems, simu- lating a single sample path corresponding to one month of a supply chain can take several hours. We present an iterative algorithm to accelerate policy simulation, dubbed Picard Iteration. This scheme carefully assigns policy evaluation tasks to independent processes. Within an iteration, any given process evaluates the policy only on its as- signed tasks while assuming a certain 'cached' evaluation for other tasks; the cache is updated at the end of the iteration. Implemented on GPUs, this scheme admits batched evaluation of the pol- icy across single trajectory. We prove that the structure afforded by many SCO problems allows convergence in small number of iterations inde- pendent of the horizon. We demonstrate practical speedups of 400x on large-scale SCO problems even with a single GPU, and also demonstrate practical efficacy in other RL environments.
A time-step in an SCO problem typically corresponds to either a demand or supply event; there are hundreds of mil- lions of such events in a month for a large supply chain (Shopping, 2024). As such, the task of simulating fixed control policy is onerous, requiring the serial evaluation of the policy over a horizon, T, of tens or hundreds of millions of time-steps. For a policy parameterized by a non-trivial deep neural network (DNN), the task of simply simulating a single sample path under the policy can thus take several hours (or more) in the context of an SCO problem. This an impediment to the application of PO methods to SCO problems which require simulating multiple sample paths of the system at each policy update iteration, and conser- vatively require hundreds of PO iterations to converge to a good policy. The key expensive step in any policy simula- tion is the task of evaluating a policy at a system state. This cannot be batched since the states encountered on a sample path are themselves computed serially. Still, one may hope that clever scheme for parallel discrete event simulation (Fujimoto, 1990; Fujimoto et al., 2017) might help:
1. Introduction
The core problems in supply chain optimization (SCO) all re- late to managing inventory over time across some potentially large network of nodes, so to match costly supply with uncertain demand. These problems are naturally viewed
1.1. Time Warp Falls Short
Time Warp is the mainstay approach to parallel discrete event simulation (Jefferson, 1985; Jefferson et al., 1987; Ghosh et al., 1993; Barnes Jr et al., 2013; Fujimoto, 2024). Time Warp is at its core a message passing framework: a processor processes 'events' and then sends the outcome of this processing to other processors that are potentially impacted by these events. Upon receiving a processed event from neighboring processor, processor may need to 'roll back' its computations, if the received event invalidates them. If the set of processors potentially impacted by given processor is small (so called 'local causality"), ), Time
"Equal contribution 'Slonn School of Management, Mas- sachusetts Institute of Technology, Cambridge, MA 02139 'Esade Business School, Ramon Llull University, Barcelona, Spain "Operations Research Center, Massachusetts Institute of Tech- nology, Cambridge. MA 02139 *Columbia Business School, New York, NY 10027 Sauder School of Business, The University of British Columbia, Vancouver, Canada. Correspondence to: Vivek Farias
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Speeding Up Policy Simulation in Supply Chain RL
Local time 1
Iteration 1
8p
(1)
8442
(1)
8r43
(1)
Initial Guess
1) From P1 to P2: trigger an event at 1 + 8 lg
P1
Parallel π in Batch
Local time f2
P1
P2
P3
P4
S(+1 ((()(
P2
2) P2 rolls back to +
0, (s))
Computationally
3) Rollbacks/Corections cascade
Iteration 2
expensive
P3
P4
Iterate Until
P1
P2
P3
P4
Convergence
(a) Traditional Approach: Time Warp
(b) Picard Iteration
Figure 1. (a) Time Warp is a widely used method for simulating discrete event trajectories. It employs a message- algorithm where each processor (blue hox) maintains local time and processes events in parallel, potentially triggering new events. If processor receives an event with a timestamp earlier than its local time, it must roll back, potentially causing a cascading rollback effect. This overhead makes Time Warp inefficient for general MDP trajectory simulation. (b) Instead, we observe that often for RL problems, the transition fa computationally cheap while the policy ı is expensive. We propose Picard iteration by the following intuition: by initializing trajectory of states (or actions), the policy т can be executed in parallel. New trajectories are efficiently updated via lightweight transitions. This process can be iterated until convergence. Compared to Time Warp, this proposed Picard (I) is GPU-friendly, (2) enables new analyses for provable speedups. (3) achieves significant acceleration in practical SCO settings, and (4) demonstrates speedup potential for general RL.
Warp works well. But other than for special structures, this is not true for general MDPs (c.g., for SCO problems) every processor must communicate in effect with every other processor and the resulting rollbacks reduce Time Warp sequential evaluation while simultaneously adding message passing overhead that is highly sub-optimal for GPUs.
The Picard iteration proceeds by dividing up the simulation horizon of T' time-steps across (potentially, virtual) pro- cesses; the assignment of time-steps to processes may be informed by problem structure. We also initialize a 'cache' of actions, one for each time-step, that can be thought of as initial guess of the actions that will eventually be simu- lated. Each process runs an independent simulation of the policy with an important tweak: a process only evaluates the policy on time-steps it has been assigned; on all other time-steps it simply uses the action for that time-step from the cache (Figure 1(b) an example where each process is allocated single time-step). While each process must still evaluate system transitions at every time step, these evaluations are assumed cheap relative to the cost of evalu- ating the policy itself. As such, each process only takes time that is roughly proportional to the number of time-steps it is assigned. All processes run in parallel. At the end of an iteration, each process updates the cache in the time-steps it was responsible for. As such, single Picard iteration is faster than the serial policy simulation task by factor of roughly # #processes. Moreover each such iteration al- lows for batched policy evaluation with no message passing across processes. The key question then is how many such iterations are required to converge to the same outcome as serial policy simulation?
Indeed, it is unclear that parallelization can be fruitful for policy simulation in general, but SCO problems have two characteristics that make this a potentially feasible and worthwhile task: (1) evaluating system dynamics is sub- stantially cheaper than policy evaluation itself, and (2) large horizon 7 makes the potential acceleration offered by batching sigmificant.
So motivated, imagine, as a thought experiment, that an oracle revealed the sequence of T states encountered on the sample path being simulated (i.e. what we are trying to compute in the first place). In that event policy evaluation could be trivially batched, and could even leverage the 'sin- gle program multiple data' paradigm GPUs are optimized for. Our goal here is to come close to this ideal via an itera- tive scheme that 'guesses' at the entire sample path being simulated, and rapidly improves this guess. See Figure 1.
1.2. This paper: the Picard Iteration
Provable speedup: We prove that in Fulfillment Optimiza- tion (FO), the number of Picard iterations required to com- pute the same outcome as serial policy simulation is no more than the number of nodes in the supply chain. Thus, applicd to such problems the Picard iteration yields an ef- fective speedup of ~ #otooeeeses//#oddeee Since #nodes is at most few hundred and #processes can be scaled
This paper proposes a novel iterative approach to policy simulation we dub Picard i Succinetly, while Pi- card iteration applies to general policy simulation tasks, it provably yields a speedup in the context of SCO problems; in practice show this speedup is greater than 400x.
'The proof of the Picard Lindelöf thcorem inspired our itera- tive framework.
Amazon has ~ 200 nodes (Amazon, 2024); Walmart has ~
2

---

Speeding Up Policy Simulation in Supply Chain RL
to tens of thousands via GPU implementation, the Picard iteration guarantees large speedup in policy simulation for those problems. In addition, Appendix B shows how our results can easily be extended to inventory control problems with replenishment.
Clemente et al., 2017; Petrenko et al., 2020; Rutherford et al., 2023)), where embarrassing parallelism is imple- mented across different agents or rollouts. In contrast Picard iteration is concerned with an orthogonal problem: accelerat- ing the evaluation of a single trajectory, which is particularly relevant for our SCO settings where T' is gigantic. For such problems Picard iteration complements parallel RL.
Practical speedup for SCO: We show that even on a single A100 GPU, the use of the Picard iteration yields an effective speedup of greater than 400x relative to serial policy eval- uation for large-scale FO problem. The speedup relative to a (tailored, highly optimized) Time Warp algorithm is approximately 100x. The speedup displays attractive linear scaling with the number of processes (as predicted by our theory) and is robust across a range of challenging prob- lem instances. In addition, this speedup is persistent when scaling to an end-to-end RL pipeline.
Parallel Discrete Event Simulation: As discussed earlier, Time Warp (Jefferson et al., 1987; Steinman, 1993; Barnes Jr et al., 2013; Fujimoto et al., 2017; Fujimoto, 2024), a main- stay parallel discrete event simulation algorithm could rea- sonably be considered an alternative to our proposal; in fact Time Warp has recently been optimized for GPUs (Liu & Andelfinger, 2017). As discussed, SCO problems (and we anticipate many RL problems in general) do not satisfy the local causality assumptions needed for Time Warp to work well (Radhakrishnan et al., 1996). We implement an opti- mized variant of Time Warp suitable to GPUs and show that Picard iteration is almost two orders of magnitude faster that Time Warp. We attribute this to the inability to re-use policy evaluations computed on incorrect states within Time Warp, a point that will become clear later.
Practical speedup for RL problems beyond supply chain: In general MDP problems, we show Picard converges to the sequential simulation output after no more than I' iterations. Given its correctness in general, we explore whether the number of Picard iterations required is a lot smaller than T for problems outside SCO. Here we show that for a majority of OpenAl Gym MuJoCo environments, the Picard iteration could potentially yield a speedup of up to 40x.
Picard iteration leverages the batch computation power of GPUs for sequential problems. Non-RL. examples in this spirit include using lookahead decoding for LLM inference (Fu et al., 2024) and a three-stage algorithm for simulating cellular base stations (Li et al., 2013). A distinctive feature of our approach is the theoretical guarantee of speedup. where the number of required Picard iterations captures how coupled a problem is. This is rarely seen in the parallel computing literature and may be of broad interest.
1.3. Related literature
SCO and RL: Supply Chain Optimization (SCO) problems represent classic family of dynamic optimization problems with intractable state-spaces, and are becoming increasingly important due to the growing volumes in e-commerce. For instance, a 1% cost reduction in fulfillment for Amazon can be translated to about IB US dollars savings (Amazon.com com, Inc., 2023). Applying Deep Reinforcement Learning (RL) to solve intractable SCO problems has garnered increasing interest in recent years (Oroojlooyjadid et al., 2022; Gijs-
2. Model and algorithm
We consider a dynamical system with general state-space S, action space A, and a disturbance space Ω. The dynamical system itself is specified by a function f : S A x Ω S. We assume the existence of an 'always feasible' action a², so that for all 8, a E A(s), the set of feasible actions at state s. For our purposes a policy is simply a map x S x Ω + A; one may think of (T-) as a DNN and assume (T)) E A(s) Vs. We may think of the disturbance here as capturing both exogenous shocks (e.g.. demand in an SCO problem), as well as any randomization endogenous to n.
brechts et al., 2022; Temizöz et al., 2025; Alvo et al., 2023).
Large companies such as Amazon (Madeka et al., 2022),
Alibaba (Liu et al., 2023), and JD.com (Qi et al., 2023)
have reportedly been testing RL at scale in SCO contexts. Our motivation for this work is to eliminate the high costs of training and back-testing in these problems due to long horizons, T. While our framework is general, we showcase it on representative problem in SCO: online fulfillment optimization (Acimovic & Farias, 2019; Zhao et al., 2022; Xu et al., 2020; Talluri & Van Ryzin, 1998; Ma, 2023; Amil et al., 2022; Acimovic & Graves, 2015; Jasin & Sinha, 2015; Andrews et al., 2019).
We next formally define the task of policy simulation. As input, we are given an initial state 81 E S, hori- zon T, and a sequence of disturbances {wi : 6 E [7]]- Our desired output is the sample path of actions under n, {a: [aoo : E [T]} defined according to a: = T($, where st+1 = f(s,, yen ww). We remark that we view the application of x-), i.e. the computation ((,,w) as com- putationally costly, while we view the application of f()
Parallel RL: There is a substantial body of literature on parallel reinforcement learning (see e.g., Asynchronous RL (Mnih et al., 2016). RLlib (Liang et al., 2018), Enypool (Weng et al., 2022), and others (Stooke & Abbeel, 2018:
30 nodes in the U.S (Walmart, 2022).
3

---

Speeding Up Policy Simulation in Supply Chain RL
given an action, [(s, a, w) as computationally cheap. This is certainly the case in RL for SCO problems. Assuming single application of α (.) takes unit time, our desire is to compute { in time < T.
2023; Acimovic & Farias, 2019; Amil et al., 2022; Acimovic & Graves, 2015; Andrews et al., 2019). We also applied Picard to inventory control with replenishment, another rep- resentative class of SCO problems (Alvo et al., 2023; Gi- jsbrechts et al., 2022; Madeka et al., 2022; Dehaybe et al., 2024; Liu et al., 2023), demonstrating favorable theoretical and practical speedups. Details are deferred to Appendix B.
We next present the Picard iteration (Algorithm 1). We assume M virtual processes indexed by m. Each m is assigned a disjoint partition of time-steps, Tm C [T] where Un Tm [T'. Algorithm I implicitly assumes the 'cache' of actions, {o²} } and the disturbance sequence {wi} } sit in shared memory. Several remarks are in order:
For FO, We are concerned with I products, indexed by i [T] Inventory of each product is carried at or more of J nodes, indexed by E [J]. Each node is endowed with a processing capacity. Let Ct.j E R be the remaining capacity of node j at time t. In addition to the capacity constraint, let It,i, E R be the inventory level of product i at node j and time t. We use o E TR and 2, E RRJ to simplify the notation. The state time f then 9t == (x), An order time is associated with a product i(wx) and reward vector r(we) E RR.. A policy ιT assigns this order to node with available inventory of product i(wr) and non- zero capacity and earns the corresponding reward (or it does not fulfill and earns zero reward):
Correctness: It is easy to see that the Picard iteration out- puts the correct sequence of actions, i.e. {at in at most T iterations. Observe that for the processor responsible for time-step at = d1 Thus, iteration k = 2, the processor responsi- ble for t = 2, say m, will take the correct sequential action at f = 1 and thus the correct sequential action at = 2, i.e. d2
I, say m, 1 -.
d Consequently,
1mmh = _ so that a = a Continuing in this fashion,
we can show:
Proposition 2.1. The Picard iteration converges in at most T iterations and returns {.
ae :=
E ij E [J] CtS > 0, 00,1, > 0} [
While this proposition shows the correctness of the algo- rithm, it is not useful: if we required T iterations for conver- gence, we would achieve no speedup. We will later prove that Algorithm 1 converges in small number of iterations independent T in large class of SCO problems.
where '0' is the action of not fulfilling, i.e., a The goal is to design policy that maximizes the total reward over some finite horizon T.
The FO problem has state space S = RR'' R' and action space
[J] U {0). Capacity is updated according to C++1 = C Ca, while available inventory is updated accord- ing to 2t+1 2, Ei(wn), (where ej denotes the jth unit vector); this specifies f(-), which is computationally trivial.
Speedup and batching: A single iteration of Algorithm achieves substantial speedup over sequential computing. Specifically, assume that time-steps are divided up equally across all processes so that |Tm| ~ T/M for all m. Then, under the assumption that the time to evaluate (T)) is much larger than the time to evaluate f()), this speedup is approx- imately M. Consequently, the effective speedup provided by Algorithm 1 is M/# #iterations. It is also worth noting that Algorithm 1 allows for the batched application of क Specifically, the first application of T-)) on each of the M processes can be batched together, following which the sec- ond application of (-) on each of these processes can be batched, and so forth.
There is just one design decision we need to make in consid- ering how to apply the Picard iteration to the FO problem, viz. how to assign time-steps to each of the M processes. We consider the approach of partitioning by products: all time-steps associated with given product are assigned to the same process. Specifically, let T, = {l v((w)) = =i). Let [7] be divided into M disjoint partitions; denote the mtth Tm- Let processor m be responsible for all time-steps associated with products in Im. i..., Tm = LIEu,., Tç. Ideally, we find partition of [T] such that each T,, is roughly the same size. With this setup, we now state the main result of this section informally:
Our discussion so far applies to general dynamical systems. We cannot hope for an effective speedup in this generality. The next Section will focus on large class of SCO prob- lems, where we will theoretically establish that Algorithm achieves a non-trivial speedup over sequential computation.
Theorem 3.1 (Informal). Provided x(-) satisfies a set of regularity conditions, the Picard iteration, Algorithm con- verges in most J + 1 iterations for the FO problem.
3. Picard Iteration and RL for Fulfillment Optimization
Speedup: A corollary of the above result is that Algorithm I provides an effective speedup of T/(J max m. [Tm.l). When tasks are constant sizes, T/ maxm iTaa ~ M (see e.g.. 'balls into bins' problems (Raab & Steger, 1998)) so that the speedup provided by Algorithm is ~ M J. As noted in the introduction, even for a large instance of the FO problem
We focus here on the Fulfillment Optimization (FO) problem, a central class of SCO problems that has recently attracted significant attention for RL, solutions (Amazon.com, Inc.,
4

---

Speeding Up Policy Simulation in Supply Chain RL.
Algorithm 1 The Picard Iteration
0: k <- 1, 1, +- a for & E [T' {Initialize cache to always feasible action a²)
0: while true do
0: parfor m t 1 to M (Bvaluate each process in parallel)
81 k.m < 81
0:
0: for t 1 to T do
0:
if E Tm then dz
J.m = T (5, k.m ,w)) {Process m evaluates st-)}
else di k. = ot
k-1 if at k-1 E A(s; ) (or a o.w.) (Process m uses cached action)
0:
R.m = f(1
k.m kmm we) {Process m updates its state]
0:
S1+1
at
0:
at = at for m t to M. t E Tm (Process m updates cache on t E Tm
0:
if a = of k-1 44 then return {ot) (Converged)
0:
else t ++1
=0
(corresponding say to a retailer like Amazon), J ~ 200, whereas we can take M ~ 10a to 10a so that we can hope for a speedup on the order of 102 to 103.
capacity in the sequential scenario. Assuming Lemma 3.2, we prove Theorem 3.1 for the special case. Let us denote by ti. ....... .J. the values of T, sorted from smallest to greatest. We establish by induction that in iteration k, of a aea for all times i < Āx. This establishes a stronger statement: converge after |Qrl + iterations.
3.1. Proof of special case
Rg. i.. the cached action correct for all
We present here a short proof of a special case of Theo- rem 3.1, which should serve to provide some intuition about the result and its proof. Theorem 3.1 will also hold for a much more general class of policies, which we make pre- cise in Theorem 3.2; however we defer this proof to the assume that (1) inventory is not constraint (or equivalently that I1 = 71), and (2) that the policy TT-) is greedy (greedy policies have been used widely in practice (Zhao et al., 2022; Xu et al., 2020)) so that ((, w) E arg max (w)).
The induction statement is vacuously true for the initial cache; assume the statement true up to some k, and consider k + 1. By the induction hypothesis, at iteration A ++1 1, all pro- cesses yn have access to the correct cached action for times Fx so that at k+ 1,m = a, for t Fr. Consequently, & k+1.m = et for S Fx. and in particular, F k+1,m 0 for all E Q.z- Now by Lemma 3.2, we must have that for any E Tm such that oッ S t < #x+1,
Appendix. For the special case consider,
at k+1. E {{jan U Q = { U
The crux of the proof lies in understanding the structural properties of 'wrong' actions. To show that ot is correct (i.e., at at :o1), we need to show that the mistakes made in round k- - 1 by other processors are constrained in desired way (they would impact & and, therefore, a²). We conduct an inductive proof for showing those properties, where the challenges lie in identifying the 'right' induction hypothesis and connecting different structural properties.
But since k+1.m = 0 for all j E 2i. it must be that Fro
dg 1,m = -a seg so that a x+1 = a, for 7 S < 7x+1 proving the inductive step and completing the proof. We finish up with proving Lemma 3.2.
Proof of Lemma 3.2: Assume the Lemma holds for all t' E [T] for iterations up to k 1, and for t' < t in iteration k. Consider time-step i + 1 then and assume that this is handled by processor m. If a E Q++1 we are done, and assume that a k. [JT Now seg a++l E arg max ry(We+1)- So if (+1, > O for all j E [J] Q1+1, we are done. Now assume that k.m ar = =j [J]) for some t' S t. By the induc- tion hypothesis. it must be that j E [a;º)) U Qr. But le S. Q441. and since j E [M]V by assumption, must then be that j = ar seq,
For the special greedy case, the 'right' strueture properties turn out to be related to the set of nodes that run out of capacity in the sequential scenario. In particular, denote by Tj the first time at which node j runs out of inventory assuming sequentially correct actions: T, = min(t ci 0} (or T +1 if .ng
k.m
c.j > 0 for all E (T). Next we define Q. to be the set of all nodes that have run out of capacity at
some time t' < t: Q. {i E [J] T < t}. We then have the following invariant:
We have consequently shown:
Lemma 3.2. For any i E (T] and all iterations ie of Algo- rithm 1, we have that the cached action of {at [099) Q..
J.m 4+1
Σ
la kim = =}}
= C1,j
S'
That is to say, the action taken at time t is either going to be correct or will go to a node that would run out of
2 C1.j Σ
36q 1a
=]} = 3e9
=c,+1 > 0
5

---

Speeding Up Policy Simulation in Supply Chain RL
for j 26+1 completing the proof.
instance-dependent bound for Picard iterations.
In addition, we also generalize the theorem to the scenarios where replenishment is allowed (see Appendix C).
3.2. The general setting
We now remove the restrictions considered in the special case above, allowing for arbitrary initial inventories (so that inventory feasibility matters) and consider more general class of state-dependent policies. Specifically, we require that the policy TT-) satisfy the following assumptions:
4. Experiments with Fulfillment Optimization
This section presents the results of an implementation of the Picard iteration on large scale FO problem instances. We also conducted experiments on Inventory Control problems, another representative class SCO problems. The results are qualitatively similar (see Appendix B). The source code has been made publicly available (see the supplementary for anonymity). We seek to establish a few key points:
Assumption (Inventory Independence): Fix some i E [4] and let a and x' be two inventory positions in IJJ such that Fty = z for all j. Then, if i(w) = i, In simple terms, the fulfillment decision for order of specific product depends only on the inventory position across all nodes of that product.
we must have <(<x, w) = ((s(,,),,uu
Policy Evaluation Speedup. The Picard iteration of- fers speedup of 350-450x over sequential simulation in the FO problem. The speedup scales approximately linearly with batch size and is robust to a variety of problem characteristics.
Assumption 2 (Consistency)): <((x, w) = j. and let ((w) i. Consider a distinct state (x',e) such that x' differs from x only in its (i.j")th th component, and c' dif- fers from only in its j' component. Then, we must have ((=',c).w) {.
Policy Optimization Speedup. An end-to-end imple- mentation of a policy gradient algorithm the FO problem highlights the value of our speedup: on large scale instance, time to convergence with sequen- tial evaluation is ~1hh; speeding up policy evaluation on that instance with Picard iteration yields the same policy in 2mins.
Assumption 3 (Monotonicity): Let (T((,,) j. and let i(w) i. Then, if x' = x + eigi T((2', w) = j. Le. increasing inventory of product i to the node it was originally fulfilled from by ı will not change the fulfillment decision. Similarly, let c' = c + Eg for any j' such that Cy' > 0. Then, T(x,, d'),w) capacity to any node with positive capacity will not change the fulfillment decision.
j. Specifically, adding
Message Passing Degrades Performance. A well re- garded scheme for parallel discrete event simulation is Time Warp. Carefully adapting Time Warp to the FO problem yields only a 5x improvement over sequen- tial simulation assuming special structure; on those problems, Picard is 88x faster than Time Warp.
The Assumptions 1-2 are natural and met by most policies proposed for the FO problem thus far. The Assumption 3 also met by perhaps the most important class of policies proposed for the FO problem, the so-called 'bid price' poli- cies (Talluri & Van Ryzin, 1998; Andrews al., 2019)². Having stated these requirements, we can now re-state refined version of Theorem 3.1 formally.
Implementation. We implement two practical optimiza- tions that improve performance (but do not impact our the- oretical analysis): First, if freset is the smallest for which af A of k-1 then we know that the actions evaluated for times treset are correct and it is sufficient to start the kth Picard iteration at time = fresett Second, opposed to running Picard iteration over the entire horizon, we run the iteration in 'chunks' of size max_ max_steps and move on to the next chunk only after convergence of the preceding one. More precisely, we run the for loop in Line 5 of the algorithm over 1 E [Treset, minnT, frrset + max_s tt__sstpppp teps)]. Tuning the max max_steps parameter thus trades off the need for synchronization (the number of iterations of the while loop in Line 2), with the potential for 'wasting' computation (the number of iterations of the for loop in Line 5). Tuning max_ max_stepp steps is straightforward: reasonable heuristic is to simulate a sub-trajectory of length < T, and select the values which minimize the time required to simulate this sub-trajectory. All experiments were conducted on a single
Theorem 3.2. Provided T(-) satisfies Inventory Indepen- dence, Consistency and Monotonicity, Algorithm I con- verges in at most QT + 1 iterations for the FO problem.
The proof of Theorem 3.2 is more advanced due to the broader class of policies allow. As the policy can depend on the inventory in general way, Lemma 3.2 no longer holds. Instead, we find that the inventory levels maintain certain monotonicity. The formal proof is provided in the Appendix A.2. Recall that |Qrl represents the number of nodes that reach their capacity limit under the assump- tion of sequentially correct actions. In scenarios where demand is less than supply, (Qrl can be significantly less than J. Consequently, Theorem 3.2 can be interpreted as
'e experimentally demonstrate the robustness of Picard when Assumption 3 violated; see Appendix.
6

---

Speeding Up Policy Simulation in Supply Chain RL
Speedup vs. Sequential
512
8
Product Partitions
Uniform Partitions
256
0.0
441
363
128
-0.2
431
360
64
-0.4
194
361
-0.6
154
358
16
-0.8
24
354
-1.0
5
355
Table 1. Speedup of Picard Iteration relative to sequential, as a function of the demand distrihution.
1
10
100
1000
10000
Batch Size
are covered by a disproportionaaely small fraction of the products. We model this as Q; x i with typical values of 3 between -0.6 and -0.8 (Brynjolfsson et al., 2003; 2010). The case 3 0 corresponds to uniform demand.
Figure 2. Picard runtime problem instances with uniformly dis- tributed demand, as a function of the number of processes (batch size M). The y-axis normalizes computation time to M 1 (i.e., speedup). For M = le4, we achieve a 441x speedup relative to the sequential algorithm.
We expect this setting to be more challenging. If all orders for a product were assigned to the same partition Ti, parti- tions would be highly imbalanced, bottlenecking line 3 of the algorithm and limiting batching opportunities. A sim- pler alternative is to assign each of the T orders randomly to a partition, ensuring uniform sizes but likely increasing conflicts (e.g., multiple partitions acting on the same inven- tory). We evaluate both approaches in Table 1, finding that uniform assignment dominates for larger 3 (heavy-tailed demand). Regardless of 3, we achieve at least 350x speedup.
A100 GPU with 40GB of VRAM. The code is implemented in JAX (Bradbury et al., 2018) and is available on Github*. See further details in Appendix A.3.
4.1. Policy evaluation speedup
For policy evaluation, we approximate a greedy-like pol- icy using a simple MLP with two layers of width 64, with the goal of constructing a policy with predictable behavior which represents realistic computational workload. We evaluate problem instances with J 30 nodes, I 1M products, and T = 3M orders, which represent (moder- ately) large-scale real-world problem (Amazon, 2025; Wal- mart, 2022). We conduct two sets of experiments:
4.2. End-to-end policy optimization for FO
Next, we turn to finding an optimal policy for a sequence of FO instances using a policy gradient approach. At each iteration the approach rolls-out the policy at that iterate and computes a policy gradient. We will consider the speedup achieved by computing this roll-out via the Picard iteration, compared with simply rolling it out sequentially.
Uniform Demand, Increasing Batch Size: We divide the T orders across the 1 products uniformly at random, and vary the batch size M. We determined that our choice of π(.) allowed for a batch size of up to le4 and thus vary M in factors of 10 up to 1e4. Products are assigned to each partition T. at random. Recall from our discussion in Section 3, we expect a speedup of at least O(M/J).
In greater detail, we consider the following policy parametrization: let so(s) - (Pfn (s)] with (n (s) E R R ((C(((s) parameterized by 0; here we take fo to be two layer MLP of width 64. We then consider the dual policy (Balseiro et al., 2023)
R', be some function of state
Figure 2 plots our speedup relative to the sequential baseline. We see in all cases speedup greater than M/J; in the case of M 1e4 this translates an actual speedup of 441x. We observe further that the speedup is largely linear with respect to M, but flags as .M grows large. We attribute this to an increased number of iterations required for convergence as the number of products assigned to a single partition T. decreases.
my To( w)) E arg 3
(i(an) ()) (8t) Minv,(i(aa)))
(8t)- (st)).
For optimizing f. we perform 1K gradient steps using Adam with learning rate 3e-3. Table 2 reports our results for a sequence of problems of increasing size. each experiment, we report overall runtime for both sequential policy roll- out and roll-out via the Picard iteration. For the problem instance with 3M orders, the sequential implementation takes approximate 10hrs of wall clock time; whereas using the Picard iteration requires less than 2mins, demonstrating the value of Picard iteration for speeding up RL in SCO problems.
Heavy-Tailed Demand, Maximum Batch Size: We next consider that the T orders not split uniformly across the / products, but rather that a large fraction of the orders
Phttps://gitiien com/ at atzngg dicard-iteration
7

---

Speeding Up Policy Simulation in Supply Chain RL
Problem Scale #Orders/ #Products
Runtime Sequential
Runtime Picard
Picard Speedup
30k/100 10k 300k/ /100k
6m55s
1m01s
6.8x
1601
~ lh
1m04s
56.25x
1040
3M//IM /LM
10h
Im39s
363x
Table 2. Runtimes for an end-to-end RL pipeline.
1:08
1:08
4.3. A comparison to Time Warp on the GPU
Piard Beusioos
Surprisingly, there is no obvious baseline approach for the parallel policy simulation task. As detailed in Section 1.1, one popular family of approaches to parallel discrete event simulation is the Time Warp algorithm (Fujimoto et al., 2017; Jefferson et al., 1987; Steinman, 1993; Barnes Jr et al., 2013) which recently has been adapted to GPUs (Liu & Andelfinger, 2017).
Figure 3. Convergence of the Picard iteration for Gym MuJoCo environments, measured in relative RMSE between the Picard trajectory and the sequentially simulated correct trajectory (nor- malized by RMSE of the draft trajectory {<]))))))). Solid line shows median RMSE each itcration over 30 seeds; error bars show 20th and 80th percentiles. Median rel. RMSE converges to S 0.1% in under fifteen iterations for all environments, whereas T 200: five of eight converge within 5 iterations.
In attempting to generalize Time Warp, at least to the FO problem, we make the following observation: suppose a policy for FO satisfies the regularity conditions outlined in Section 3.2 (Assumptions 1, 2 and 3), and suppose all processes have the correct state at time (g- Then, we observe that all processes can execute in parallel between to and la + miny Go.j without requiring a rollback. We exploit this to implement Time Warp efficiently on GPU, in analogy to (Liu& & Andelfinger, 2017).
(Huang et al., 2022), a popular baseline implementation for RL algorithms. Jax training code is adapted from (Lu et al., 2022), which tries to replicate CleanRL. functionality, For numerical stability, we set learning rate of 3e-5 and perform one update per trajectory instead of 10.
Setup: Our goal is to measure the speedup afforded by Picard iteration to the policy evaluation step in given PPO iteration. For each environment, we run PPO for a total of 100k time-steps with policy updates occurring every 2048 time-steps. We collect the final and penultimate policy iterates which we refer to as π and 7 respectively. Our goal is to simulate π via Algorithm 1. We choose to set M = T = 200, such that each T.,. consists of single time- step. There is a natural and attractive choice of the initial cache: specifically, we set of = 7 (s) wt), the sequence of actions taken by the previous policy iterate on the sample path in question.
We benchmark this approach in the setting with 3M orders and 1M products. Recall that Picard Iteration achieves its 441x speedup over sequential simulation in this section (Sec- tion 4. I). In contrast we observe that Time Warp achieves a speedup of 5x. Picard is thus 88x faster than Time Warp, even when the latter is specifically tuned to exploit problem structure.
5. Exploratory Experiments on RL problems beyond Supply Chain
Results: Figure 3 plots the convergence of the Picard iter- ation across several environments, and multiple seeds for each enviromment. Defining the state trajectory simulated at the kth Picard iteration according to s = f(s?: at wr), we measure convergence here via relative root-mean- squared-error (RMSE): Σ, || .eq - s Il2/ E, ||st 11stt where s t,50q is the 'correct' state under - at f. This quan- tity is guaranteed to be O (up to numerical precision) for k = T = 200 by Proposition 2.1, but the key question whether we get convergence in k < T.
While we have focused our experiments and analysis on SCO problems, our Picard iteration applies to general RL environments. This Section briefly explores apply- ing the Picard iteration to RL environments outside SCO. Specifically, we consider variety of OpenAl gym MuJoCo environments commonly used for RL. benchmarks, imple- mented in jax via the Brax library (Freeman et al., 2021). We consider using the Picard iteration for policy roll-out at each policy optimization iteration in place of sequential simulation. We use PPO (Schulman et al., 2017), although our simulation approach is agnostic to the learning algo- rithm. Our goal here is simple: we wish to show that Picard iteration converges in small number of iterations, << T.
Figure 3 answers this question in the affirmative. We that in five of eight environments, the relative RMSE (me- dian over 30 random seeds) converges to S 0.1% in under five iterations whereas T = 200; further, all enviromments converge within fifteen iterations. These are exciting results suggesting the Picard framework might be of value in gen-
We adopt the network architecture for ग. and most policy optimization hyperparameters from the CleanRI. benchmark
8

---

Speeding Up Policy Simulation in Supply Chain RL
eral environments as well. For instance if evaluation of f were sufficiently faster than evaluation of (i.e. if dynamics were cheaper to simulate than policy evaluation), the results here would lead to an end-to-end speedup of 13-40x.
Amazon. Supply chain standards, 2024. URL https: / / /ssupllyy www.an.aaazznnnn.....o.mmm 05-22.
amazon. com/. Accessed: 2024-
Amazon. Our facilities, 2025. URL https://www aboutama zon. www.oo///////oo. Accessed: 2025-01-30.
6. Future Work
There are exciting avenues for future work on the surpris- ingly under-explored problem of parallel policy simulation: SCO Problems: Our findings extend to other SCO prob- lems. In Appendix B, we show that Picard iteration achieves comparable empirical and theoretical speedups when ap- plied to the One Warehouse Multi- Retailer replenishment problem. Many more opportunities for exploration remain. Convergence in Other Environments: We showed promis- ing results for environments outside SCO (viz. MuJoCo), although the theoretical basis for Picard's 's success in these settings remains unclear. Analyzing the factors influencing convergence in different environments would be valuable next step, perhaps starting with simple time-varying linear systems. In "contractive' systems, Picard iteration should converge linearly, with the rate determined by the associated contraction factor.
Amazon.com, Inc. Amazon.com, inc. 2023 annual report, 2023.
Amil, A., Makhdoumi, A., and Wei, Y. Multi-item order ful- fillment revisited: Lp formulation and prophet inequality. Available at SSRN 4176274, 2022.
Andrews, M., Farias, V. F., Khojandi, A. I., and Yan, C. M. Primal-dual algorithms for order fulfillment at urban out- fitters, inc. INFORMS Journal on Applied Analytics, 49 (5):355-370, 2019
Balseiro, S. R., Lu, H., and Mirrokni, V. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research, (1(1):0011119, January 2023. ISSN 0030-364X.
doi: 10. ww..127/opre.2221..222
Overall Speedup in Other RL problems: Assuming batch size M and that we require K Picard iterations for convergence, the overall speedup is (17 + 1) + 1/M) Here v is the ratio of the amount of time it takes to evaluate f(-) to that of evaluating (-)) In the case of SCO problems this ratio is ~0. On the other hand, for environments like MuJoCo, this ratio is actually close to 1/5. As such, we see that speeding up can result in dramatic time savings in concert with Picard. In the case of MuJoCo, this could be achieved with a more efficient vectorized physics engine.
Barnes Jr, P. D., Carothers, C. D., Jefferson, D. R., and LaPre, J. M. Warp speed: executing time warp on 1,966,080 cores. Proceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simula- tion, pp. 327-336, 2013.
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., and Zhang, Q. JAX: composable transformations of Python+NumPy programs, 2018. URL http://gi comm hwwoo//ooll////oooooooooooo jaa..
Impact Statement
Brynjolfsson, E., Hu, Y. J., and Smith, M. D. Consumer Surplus in the Digital Eeonomy: Estimating the Value of Increased Product Variety at Online Booksellers. Man- agement Science, 49(1 (9(11):580011 1596, November 2003. ISSN 0025-1909. doi: 10. 10.1287/mnsc.44 1.9.1..580..0580.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Brynjolfsson, E., Hu, Y. J., and Smith, M. D. The Longer Tail: The Changing Shape of Amazon's Sales Distribution Curve, September 2010.
References
Acimovic, J. and Farias, V. F. The fulfillment-opiimizzaion problem. In Operations Research & Management Science in the age of analytics, pp. 218-237. INFORMS, 2019.
Clemente, A. V., Castejón, H. N., and Chandra, A. Efficient parallel methods for deep reinforcement learning. arXiv preprint ArXiv:1705.04883 2017.
Acimovic, J. and Graves, S. C. Making better fulfillment decisions on the fly in an online retail environment. Man- ufaccturing & Service Operations Management, 17(1): 34-51, 2015.
Dehaybe, H., Catanzaro, D., and Chevalier, Deep rein- forcement learning for inventory optimization with non- stationary uncertain demand. European Journal of Oper- ational Research, 3 314(():4333444 2024.
Alvo, M., Russo, D., and Kanoria, Y. Neural inventory control in networks via hindsight differentiable policy optimization. arXiv preprint arXiv:2306.1 /246, 2023.
Freeman, C. D., Frey, E., Raichuk, A., Girgin, S., Mordatch, I., and Bachem, O. Brax differentiable physics engine

---

Speeding Up Policy Simulation in Supply Chain RL
for large scale rigid body simulation, 2021. URL http: //gi thub. - com google/brll.l..eeoo
Liang, E., Liaw, R., Nishihara, R., Moritz, P., Fox, R., Gold- berg, K., Gonzalez, J., Jordan, M., and Stoica, I. Rllib: Abstractions for distributed reinforcement learning. In International conference on machine learning, pp. 3053- 3062. PMLR, 2018.
Fu, Y., Bailis, P. Stoica, I., and Zhang, H. Break the sequen- tial dependency of Ilm inference using lookahead decod- ing. In Proceedings of the 41st International Conference on Machine Learning, ICML'224 24. JMLR.org. 2024.
Liu, J. Lin, S., Xin, I.,, and Zhang, Y. Ai vs. human buyers: A study of alibaba's inventory replenishment system. INFORMS Journal on Applied Analyties, 53(5): 372-387, 2023.
Fujimoto, R. M. Parallel discrete event simulation. Commu- nications of the ACM, 33(10):30-53, 1990.
Fujimoto, R. M. Development of the parallel and distributed simulation field. SIMULATION, 100(12):1197-1223 2024.
Liu, X. and Andelfinger, P. Time Warp on the GPU: De- sign and Assessment. In Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, pp. 109-120, Singapore Republic of Singa- pore, May 2017. ACM. ISBN 978-1-4503-4489-4 doi: 10. 10.1145/3064911.360 1..04991..
Fujimoto, R. M., Bagrodia, R., Bryant, R. E., Chandy, K. M., Jefferson, D., Misra, J., Nicol, D., and Unger, B. Parallel discrete event simulation: The making of a field. In 2017 Winter Simulation Conference (WSC), pp. 291. IEEE, 2017.
Lu, C., Kuba, J., Letcher, A., Metz, L., Schroeder de Witt, C., and Foerster, J. Discovered policy optimisation. Ad- vances Neural Information Processing Systems, 35: 16455-16468, 2022.
Ghosh, K., Fujimoto, R. M., and Schwan, K. Time warp simulation in time constrained systems. ACM SIGSIM Simulation Digest, 23(1):163-166, 1993.
Ma. W. Order-optimal correlated rounding for fulfilling multi-item e-commerce orders. Manufacturing & Service Operations Management, 25(4):1324-1337, 2023.
Gijsbrechts, J., Boute, R. N., Van Mieghem, A., and Zhang, D. J. Can deep reinforcement learning improve inventory management? performance on lost sales, dual- sourcing, and multi-echelon problems. Manufacturing & Service Operations Management, 24(3):1349-1368 2022.
Madeka, D., Torkkola, K., Eisenach, C.,, Luo, A., Foster, D. P., and Kakade, S. M. Deep inventory management. arXiv preprint arXiv:2210.03137, 2022.
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T. Silver, D., and Kavukcuoglu, K. Asyn- chronous methods for deep reinforcement learning. In International conference on muchine learning, pp. 1928- 1937. PMLR, 2016.
Huang, S., Dossa, R. J.J.,W Ye, C.,, Braga, J., Chakraborty, D., Mehta, K., and Araújo, J. G. Cleanrl: High-quality single- file implementations of deep reinforcement learning algo- rithms. Journal of Machine Learning Research, 23(274): 1-18, 2022. URL hitp:/ / /mlrr.lr..///..////m html.
Oroojlooyjadid, A., Nazari, M.. Snyder, L. V., and Takáë, M. A deep q-network for the beer game: Deep reinforcement learning for inventory optimization. Manufacturing & Service Operations Management, 24(1):285-304, 2022.
Jasin, S. and Sinha, A. An lp-based correlated rounding scheme for multi-item ecommerce order fulfillment. Op- erations Research, 63(6):1336-135) 2015.
Petrenko, A., Huang, Z., Kumar, T., Sukhatme, G., and Koltun, V. Sample factory: Egocentric 3d control from pixels at 100000 fps with asynchronous reinforcement learning. In International Conference on Machine Learn- ing, pp. 7652-7662. PMLR, 2020.
Jefferson, D., Beckman, B., Wieland, F., Blume, I.., and DiLoreto, M. Time warp operating system. In Proceed- ings of the eleventh ACM Symposium on Operating sys- tems principles, pp. 77-93, 1987.
Qi. M., Shi, Y., Qi, Y., Ma, C., Yuan, R., Wu, D., and Shen, Z.-J. A practical end-to-end inventory management model with deep learning. Management Science, 69(2): 759-773, 2023.
Jefferson, D. R. Virtual time. ACM Transactions on Pro- gramming Languages and Systems (TOPLAS), 7(3):004- 425, 1985.
Li, x., Cai, W., and Turner, S. J. Gpu accelerated three- stage execution model for event perallll simulation. In Proceedings of the 1st ACM SIGSIM Conference on Prin- ciples of Advanced Discrete Simulation, pp. 57-66, 2013.
Raab, M. and Steger, A. "alls into bins simple and tight analysis. In International Workshop on Randomiza- tion and Approximation Techniques in Computer Science, pp. 159-170, Springer, 1998.
10

---

Speeding Up Policy Simulation in Supply Chain RI.
Radhakrishnan, R., McBrayer, T. J., Subramani, K., Chetlur, M., Balakrishnan, V., and Wilsey, P. A. A comparative analysis of various time warp algorithms implemented in the warped simulation kernel. In Proceedings of the 29th Annual Simulation Symposium, pp. 107-116. IEEE, 1996.
Xu, Z., Zhang, H., Zhang, J., and Zhang, R. Q. Online demand fulfillment under limited flexibility. Management Science, 66(10):4677-4685, 2020.
Zhao, Y., Wang, X., and Xin, Multi-item online order ful- fillment in two-layer network. Chicago Booth Research Paper, (20-41), 2022.
Rutherford, A., Ellis, B., Gallici, M., Cook, J., Lupu, A., Ingvarsson, G., Willi, T., Khan, A., de Witt, C. S., Souly, A., et al. Jaxmarl: Multi-agent environments jax. arXiv preprint arXiv:2311. 2023.
Scarf, H., Arrow, K., Karlin, S., and Suppes, The opti- mality of (s, s) policies in the dynamic inventory problem. Optimal pricing, inflation, and the cost of price adjust- ment, pp. 49-56, 1960.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint AXXv:1707.06347 2017.
Shopping, C. O. How many orders does ama- zon get & deliver per day?, 07 2024. URL.
http::://cpptallomsshpp..o com/ researcch/mmmzznnorddesss peressyy-eday--
Steinman, J. S. Breathing time warp. In Proceedings of the seventh workshop on Parallel and distributed simulation, pp. 109-118, 1993.
Stooke, A. and Abbeel, Accelerated methods for deep reinforcement learning. arXiv preprint arXiv: /803.0288 2018. Simple batching for multiple trajectories.
Talluri, K. and Van Ryzin, G. An analysis of bid-price controls for network revenue management. Management Science, 44(11-pan 1)177-11):1177715533 1998.
Temizöz, T., Imdahl, C., Dijkman, R., Lamghari-Idrissi, D., and van Jaarsveld, W. Deep controlled learn- ing for inventory control. European Journal of Op- erational Research, 324(1):104-117, 2025. ISSN 0377-2217. doi: 026. URL UtLLtttpps///w...ceeeeeeeeeeeeee com/ sctiacceearrtcca///////272221122
Walmart. A era of fulfillment:
Introducing walmart's generation fulfillment centers, 2022. URL https:
//shorturl at /r.. Accessed: 2024-05-22.
Weng, J., Lin, M., Huang, S., Liu, B., Makoviichuk, D., Makoviychuk, V., Liu, Z., et al. Envpool: A highly parallel reinforeement learning environment execution engine. In Advances in Neural Information Processing Systems, volume 35, pp. 22409-22422 2022. C++ for environment step parallelization.

---

Speeding Up Policy Simulation in Supply Chain RL
A. Appendix/ / supplemental material
scenario:
A.I. Proof of Proposition 2.1
(1(C15" "" > 0)}ee( = (1(4.) > 0) se)
We will prove the proposition by induction on the following hypothesis:
Now consider an arbitrary product ic E [7] and its orders A within the time period 1 fx. ]: A 1 l- The orders in A is processed sequentially by a process and for any E A, we aim to show
seg 0g - dz
11
< k;
whence the desired result will follow immediately by setting k T. Letting n denote the processor to which order is assigned in iteration k, we have a aj 1. aj seq since all processors have the correct state at the beginning of the horizon: $1 1. 81 Vm.
k
ot
at
x ( f t (1(G-ī, km > ()) wi)
k.m
Now, assume that at = at vt S k. By this induction hypothesis (and the state update defined in Section 3), we have sg 8. = Sk Vm. Therefore, processor m2+1 makes k+1 the right decision for order k- + 1, and we have: ak+1 ,+1,m 0x+1
= x ( (1 ted hepp (1(4 > 0) wi)
k+1
This is evident since the capacity- set remains iden- tical between the local process and the sequential process, k.m and the inventory levels "t,,e.j and zz,,. share the same initial points at time fk.-1 and solely determined by the fulfillment decisions made for product ie at t E A. Thus all states and decisions remain the same between the local process and the sequential process during [Fr._ + 1, F. This completes the proof.
seq This completes the induction. "++1
A.2. Proof of Theorem 3.2
We will use the following lemma, which will facilitate greatly the proof of Theorem 3.2.
Lemma A.I. Let Q= = (j
E [V] [T) S.). 1) be the set of nodes that run out of capacity before t in the sequential scenario. We have, at any iteration 2 1, any time step t e [T,, any product i [4] and any process m E [M]
1. PROOF OF LEMMA A.I
Note that the capacity consumed at a node is the sum of the inventories consumed at that node. Therefore, for given k.m E [J], E [T], Lt,.. 2 F1,3. for all i E [7] implies that k.m
k.m 2 T15.5 Vj & Q Ftii.)
(1)
arg
C 2
k.m
Dea Vj E Qr-
(2)
seq 2 G, Thus it is sufficient to show (1).
4.j
Proof of Theorem 3.2. We will invoke Lemma A.1 for the proof. To begin, we state that for all k 2 1, the following holds
We prove this by induction. (I) holds for k = 0 since all orders are not fulfilled and all inventories are not consumed. For any given he E N, te E [T], assume this holds for any 0 k < ke, t (T) and k ke, 1 < t lc. Now we want to prove (1) for k ke, = tc.
sog 11c FR.
(3)
We can see that (3) directly implies Theorem 3.2. We pro- ceed to prove (3) by induction, assuming it holds when 1 < k < Ko. We want to prove the case for k = ke. By induction, ke
Consider process m associated with product subset Am and order subset Pm- Let the product at Time le be ig. It is sufficient to show
we have x Fe. -1,.j = Fec -1,1.j and k.:m
Fx. -1,j = sog - for all i E [T].] E [J] and m E [M]. In particular, the set of
k.m (e,ee.
Vj
$ Qt.
(4)
nodes {i= E [J],
koom
15 = 0}
ti- E [J], seg 1
0} = Qi, have run out of capacity at time - for both
since the inventory levels for other products will remain the same in processing order lc-
the local process m and the sequential scenario.
[ + 1, ), we have that in the sequential scenario node is running out of capacity dur-
Now, consider
If ie is handled by a process m' that is not m, i.e., ie e Amn * Ams m will skip the invocation of x and take dt k.m k-1,m In fact, this skip will occur for every di.
ing this period (note that the next depleted one is at f. sen Therefore Qi = Qhe and c.j > V, & Qive. Then by Lemma 1, we have that for E [7ke + 1, F..)
order related to ic, i.e., a k.m = oz k-1.m² for all E [7] with i(wr) = ic. This implies that the inventory level for i, at process m is the same as the inventory level at m' from the previous iteration, thus (4) holds by induction:
k.m 2
0, $ Que
Therefore, fort E 1, ). the process m maintains the same feasible set of fulfillment nodes as the sequential
k.m I Feckei = Ttetted
k-1mm
2 Teeee Vj Q..
12

---

Speeding Up Policy Simulation in Supply Chain RL
Next consider the case ie is handled by process m, i.e., E Am- Recall that the dynamics of the states are
Q1. ( = 0}). Together this with (6), we have
1 1 14 > 0) = 1(c.-m. > 0) for j & Que Thus (10) can be simplified to
R.m k.m 1,,,o)
Itt.
1
(ate k. =
k. Co. -1-
k.m
1
kmm = j]
(iie Die U - (10)
[I(ck:-,, 071sE(1),44.) {(a)")
We aim to show that even the decision dze ing not the same as a the inventory monotonicity in (4) still hold. Specifically, we will show
k.m is wrong, mean-
[ UQt
die
k.m
k.m E (aa,.) (on) U Qre U & fto Lied >
Ite Liceh )-
ang
Finally, by invoking Assumption 2-3 on the set of {i & soq -1o-1 and replace Ite- by
Q Lel >
k.m
seq
(5)
k. 1olof one can verify that
k.m k. * o, we have either Ot, E (5) implies that when dt.
k.m k.m = - {1 > w)
N.m (
Qu which is excluded when examing (4), or ot E {j of
dt
-lece > -.i.h J. which will maintain the inven- tory monotonicity after the state update. Thus, (5) implies (4).
Q
k.m
kmm E ((ag QQ. U & Q 1,1oo > af seq
Thus (5) holds and this completes the proof.
To prove that (5) holds, we examine the capacity level at time &c. Note that the capacity consumed the aggregation of inventories consumed at any time point, thus for all j &
A.3. Details of Problem Setup and Data-Generation Process
Que
Our experiments use synthetic data based broadly on and -istriibtitiiiio patterns ob- served at modern (moderately) large industrial retail- ers. We consider a fulfillment network comprising J = 30 nodes located in the 30 most-populous states (each one in the most-populous city of the corresponding state). Although the distribution of demand among products was varied in certain experiments, in all cases, we provided sufficient in- ventory and fulfillment capacity at the network level (i.e. across all J nodes) to permit the fulfillment of 80% of de- mand (not accounting for occasional cases of 'stranded' inventory, in which one is unable use inventory left over at a node with remaining capacity). For each product, i, the network inventory inventory was distributed across nodes pro rata based on population: 20,4.J population,; similarly, network capacity was distributed pro rata across nodes based on population: cu.j x population,- For each (order, node) pair (1, we computed the distance between the zip codes, dej, and then defined a reward for fulfilling Order t from Node as follows:
J.m Ct
1.j = CO.J -
Σ
(xo.s -
Lte (11.j
k,
iELT
2 CO.1
Σ
(mu.s.) 216-1185)
by induction
ba Cte
1.9"
Thus, both capacity and inventory for the node j & Qt, sat- isfy the monotonicity comparing to the sequential scenario:
to- 2 ct 1,j
k.m baa
(6)
km t/ -1i 2 1--1,
seg
(7)
We are going to use (6), (7), Assumptions 1-3 to show (5). Note that following our requirements for given by Assumption
* <(=;.-n Lic L bE( (1 > ()
oz seq
(8)
ry(wi) = max, dij dej
(11)
By Assumption 2, we can replace the inventory and capacity of the nodes in the set Qi, by 2, J.m him
max, dij
Pie-liio c and obtain
Finally, a (the always-feasible action) was associated with zero reward and had ties broken against it to ensure that we only choose it in the absence of any feasible alternatives.
π ( k.m t BERu
(9)
(1(4-11) > O)] U (1( > O))iEq. Wro)
We implement two practical optimizations that improve performance (but do not impact our theoretical analysis): First, if treset is the smallest t for which of * a k-1 then we know that the actions evaluated for times < freset are correct and it is sufficient to start the kth Picard iter- ation at time = breset- Second, as opposed to running
E (ago0 s00 UUe
Note that c,-11, l.j > 0 for j & Qt by the definition of
Qt. (the set of nodes running out of capacity before le, i.e.,
13

---

Speeding Up Policy Simulation in Supply Chain RL
Picard iteration over the entire horizon, we run the iteration in 'chunks' of size max_steps and move chunk only after convergence of the preceding one. More precisely, we run the for loop in Line 5 of the algorithm over I. E [freeet, min(T, freset + max_steps)] Tuning the max_steps parameter thus trades off the need for syn- chronization (the number of iterations of the while loop in Line 2), with the potential for 'wasting" computation (the number of iterations of the for loop in Line 5).
A.5. Effect of initial action sequence
the next
Loosely speaking, the closer the initialization is to the cor- rect trajectory, the fewer iterations will be required. We test the sensitivity of Picard Iteration to the initialization by experimenting with three natural initializations:
1. Unfulfill (441x Speedup): initially, all orders are unful- filled. This setting corresponds to the theoretical results and experiments the main body of the manuscript.
We consider a high-level (JAX (Bradbury et al., 2018)) im- plementation of Picard that does not require custom ker- nels. Notably, Line 3 of our algorithm is implemented via jax. vmap so that we forego fine- ane-grained control of batch- ing evaluations of T (-).
2. Naive (358x Speedup): Initially, fulfill all orders from their nearest fulfillment center, ignoring inventory and capacity constraints.
3. Random (390x Speedup): Initially, fulfill all orders from a random FC.
All experiments were run on single A100 GPU with 40GB of VRAM, at 16 bit precision. All key operations are jit- compiled. We also implement the sequential baseline on GPU, where it can leverage parallelism in subroutines such as matrix multiplication.
Clearly, different initialization methods have an impact on the simulation speed, although massive speedups are possi- ble regardless. Here, it appears that the "Unfulfill" strategy works the best. The intuitive explanation for this is con- sistent with our analysis: using this initialization strategy, after the first iteration, each processor will have correctly ac- counted for inventory and capacity consumed by orders for that processor's s own products in some sense, a "greedy" initialization which less naive than the "Naive" approach above. Further, unlike the alternatives, when initializing each chunk, this procedure able to account for inventory and capacity consumed in previous chunks.
A.4. Practical performance with capacity-dependent policies
The bound on number of iterations until convergence in Sec- tion 3.2 assumes that the fulfillment policy does not depend on node capacity. As a final robustness check, however, we are interested in gauging the empirical performance of Picard Iteration for policies that do depend capacity (be- yond ensuring feasibility), a regime for which our theory does not directly apply. We therefore conduct an ablation study using a simplified version of the policy that penal- izes capacity usage at low-capacity nodes using shadow prices, with strength modulated by parameter ?. Ranging y from 0 to oc interpolates between a closest-node policy and policy that always fulfills from the node with greatest remaining capacity (an unrealistic extreme scenario); for reference, a value of y 1.0 allows the node with greatest remaining capacity to improve its ranking by up to J - positions (i.c. even the most-expensive node may be chosen its remaining capacity is sufficiently attractive). The re- sults are shown in Table and demonstrate that empirically, the constraint on capacity (non-) moon)ydependence is non-vacuous but can be relaxed substantially; Performance is virtually unchanged for realistic settings of that incorporate shadow costs on capacity.
A.6. Limitations and worst-case set-up
To understand potential limitations, consider back-of-the- envelope analysis of the key factors contributing the sim- ulation runtime:
tx. the time execute the policy single time step
ty, the time to execute one step of the dynamics
. T, the problem horizon (number of steps)
K, the number of iterations required to converge
M, the number of parallel processors available
Sequential execution requires time T(tx + ty), whereas Picard iteration requires:
Table 3. Ablation study policy that discounts node proximity by (remaining) capacity scarcity
7
Conflicts
Speedup
Tt. (Tx M
K
+ +Tt)
(for M S T)
0 (no capacity dependence)
13
441x
0.5
14
427x
1.0
15
401x
Potential limitations are easy to see from this equation:
14

---

Speeding Up Policy Simulation in Supply Chain RL
If K' is sufficiently large, this can offset the benefits of parallelization. As we show in the paper, K is provably small in many useful cases, but this does not hold universally; see the worst-case setup in response to the next question.
r decides (i) how much the central warehouse replenishes, 9e,,, and (ii) how much retailer n(wz) replenishes from the central warehouse, It,((ar)
at == ((),, = (90.0: g),((w))) E R
l is sufficiently large (i.e., dynamics are very expen- sive), then the term KTYyy can dominate. In many real problems (such as the FO and inventory management settings we analyze), the dynamics are trivial to com- pute, so iy is negligible. For settings where this is not true, this dependence can be improved by computing expensive parts of the state transitions in parallel and caching them, as we do for actions.
The inventories evolve as follows:
(Ie,n(w)) - d(wi))
+ +mnn((r.(am)) Ft,0), if n(wi),
11+1,
if # n(wi).
(12)
The inventory of the central warchouse evolves as:
One can construct a problem and Picard iteration scheme (i.e., allocation of tasks to processors), for which conver- gence requires T iterations, although this is quite pathologi- cal. Consider a setting with a single product, two parallel processors and two fulfillment centers (FC), FCI and FC2, starting with equal capacity. Suppose that event assignments alternate between the two processors (i.e., processor 1 is responsible for odd-numbeeed events, and processor 2 for even-numbered events). Suppose that the policy is simply to fulfill orders from the FC having the largest remaining capacity, with preference for FC1 over FC2 in case of ties. Finally, suppose that the initial trajectory provided to Picard Iteration is to unfulfill all orders. In this scenario, the first iteration, both processors will fulfill all orders from FCI; In the second iteration, starting from the time t 2, both processors fulfill all subsequent orders from FC2; and in the third, starting from the time f = 3, both processors fulfill all subsequent orders from FC1. They continue to alternate like this for T iterations until convergence. Note that, in the implementation of Picard iteration that we analyze, since there is only one product, all events would be assigned to the same processor, which avoids these conflicts.
I1+1.0 (0t,0 (t,n(w))) + Qt,0=
where (-)+ represents the non-negative part. We also assume there is an upper bound for how much inventory can be hold at each location: Tt. S Cn Vn N......
B.2. Theoretical Guarantee
Policy. We consider the following policy æ. For each retailer n E [N], the replenishment decision Jr,n = Tn (It, wi) is a function of its local inventory and the exogenous in- formation (this exogenous information can include the his- torical demand across retailers). The function T. can be arbitrary (e.g., a neural net) except satisfying the capacity condition (æ1,n d(w)))+ + Qt. S Cn and positivity con- dition Qt, 2 O. For the central warehouse, we consider an (s, -policy (i.c., an order is placed to increase the item's 's inventory position to the level S as soon as this inventory position reaches or drops below the level s). That is
S xt.0 ()
Fi,0 (,,(w,)) S otherwise.
F1+100
(13)
B. Extension: Inventory Control with Replenishment
The (s, -)-oolicy is known to be optimal in a single-product setting with fixed ordering costs (Scarf et al., 1960), making it a common starting point for practical inventory manage- ment. We further assume & 2 Gny Vn simplify the analy- sis, whereas the experiments in Appendix B.3 are performed without this constraint.
B.1. Problem formulation
We describe here the One Warehouse Reetii-Rtaiilrr (OWMR) problem. We have one central distribution center and N retailers, indexed by E [N]. Let Fz,0 E R be the inventory of the central warehouse at time & and Fr.n E IR be the inventory level of retailer n at time t. The state at time is then
Picard Iteration. We allocate time steps based on retailers: m(w:)) = n). with the intuition that the replenish-
Tn = {t ment decisions across retailers are weakly entangled only through the central warchouse. Under this setup, the conver- gence speed of Picard iteration can be bounded by R, the number of times the central warehouse is replenished:
8: = (Ir,0, Lt, ...l.....,............... I..N).
For now, we assume all replenishments are immediate, hence we have no in-transit inventory. Each period f, a demand arrives at retailer n(wx) of quantity d(wi). policy
T
R
1 1
> 0).
15

---

Speeding Up Policy Simulation in Supply Chain RL
In many practical scenarios, it is reasonable expect that
of 230x compared naive sequential evaluation. We use 4,000 parallel workers and set max_ =0x_sttps==10; the policy call consists of a Multi-Layer Perceptron with two hidden layers with width 512. As per Theorem B.1, Picard Iteration needs 110 iterations (twice per weekly replenishment of the central warchouse). Next, we demonstrate the robustness of our results through an ablation study, systematically altering various problem and algorithm parameters.
R < T (e.g., when the cost of replenishing the central warehouse is high). In particular, we establish the following theorem:
Theorem B.I. For the OWMR problem and the correspond- ing policy π described in this section, the Picard Iteration converges in at most 2R iterations.
Proof Sketch. Under the (s,S) -poolicy, we have Vt, Zr,0 2 s 2 It... Thus, the replenishment decisions at local retailers are completely separable (i.e., U.,"" km st,n), making it sufficient to consider the decisions for the central warehouse. The dynamics of the central warehouse at each processor evolve as follows: when n((w)) & Nu where Nm denotes all retailers handled by processor m, we have
Ablation Study. We start by evaluating robustness under heavy-tailed demand. To do this, we define the weights for store selection as w, = (1 a)'. where represents the store index and a E [0. 1] controls the skewness of the distribution. The weights are normalized into probabilities Pt = w./ Σ, Wy- When a = 0, the distribution is uniform across stores. As a increases, the distribution becomes pro- gressively more skewed, favoring stores with lower indices. For instance, 20% of retailers are responsible for 80% of the demand when 0.002. Table 4 presents the speedup of Picard iteration compared to sequential evaluation. As expected, the performance improvement decreases as the demand distribution becomes more heavy-tailed. Note that we assign one processor per retailer; further optimization of the partitioning could yield better results, making the reported speedups conservative estimate.
[ sog (tml(we)
+
if R-1 =0 0, 00,0
k.m Jt.
otherwise.
If the decision to replenish the central warehouse at iteration k - 1 is incorrect, then z2.0 k.m will be wrongly replenished to S, causing error propagation and presenting major obstacle to proving convergence.
Fortunately, the following lemma ensures the correctness of the central warehouse decisions, leading to the guarantees stated in the theorem:
Lemma B.2. Suppose 2eg O for some ti. Let to deq > 0} U (T) be the next time step when min(t 1> 41,44,0
Speed-up
Speed-up
the central warehouse is replenished. Assume 9t. J.m = 9t,m
soq
0.000
230x
0.006
55x
for all t E [T), E [N] and 90.0" d.o for t S f1. Then for any {gt,o- vt E (t1,t2]3 at the kth iteration, after 2 iterations, we have 4t.0 2t,0 1L E (2).
0.001
227x
0.007
50x
0.002
113x
0.008
44x
0.003
111x
0.009
39x
0.004
74x
0.010
36x
The intuition for Lemma B.2 that, regardless of how incorrect o: is at the kth iteration, the k + 1th iteration will not replenish the central warehouse between i E (2) because the incorrect decisions from other processors will only delay the time that the inventory drops below s. Then, the l + 2th iteration will ensure the central warehouse is replenished at 12. Details are omitted for simplicity.
0.005
72x
0.011
33x
Table 4. Speedup of Picard Iteration relative to sequential, for dif- ferent values in the demand distribution.
B.3. Experiments
Figure 4 illustrates the effect of varying the number of re- tailers and batch size on speedup. As the number of retailers increases, we observe speedups reaching up to 380x for 1,000 retailers, followed by a gradual decline for larger counts, likely due to GPU memory. Varying the batch size for Picard iteration exhibits comparable trend, with speedups peaking at 383x for 1,000 parallel workers before slightly decreasing at larger batch sizes.
Base case. We consider a base setting inspired by Walmart, which operates over 4,000 stores (Walmart, 2022) to fulfill their online demand. We simulate one year of data of one product that sells about 10,000 units per day across the 4,000 stores (2.5 units per store per day). We set the replenishment policy of the central warehouse and local stores such that the central warchouse replenishes about once weekly. Such frequency is often observed in practice due to the presence of fixed order costs. Simulating one year of data (T = 10, 000 x 365 = 3, 650, 000) yields an empirical speed-up
Lastly, we modify the width of the two hidden layers in our DNN. While our speedups remain high, they gradually decline as the neural network size increases.
16

---

Speeding Up Policy Simulation in Supply Chain RI.
C. Extension: Fulfillment Problem with Refreshing Capacity
Consider setting where there exogenous steps that periodically refill the capacity with fixed amount, mod- eling, for example, the daily or hourly replenishment of fulfillment center's capacity.
Batch Size
For I steps, assume there are K refills, the frequency of each product in the demand is bounded by M, and the number of processors P. Then, the computational complexity of the Picard iteration is given by (assume T Z P)
Theorem C.1.
512
Speedup Sequential
256
T(K + JJM O
P
where is the number of fulfillmett nodes.
10
100
1000
10000
Number of Retailers (N)
Proof. We model each refill as introducing a new fulfillment node into the system. By treating these nodes as part the overall network, can then apply the reduction obtain the bound.
Figure Speedup of Picard Iteration relative sequential, function of different number of batch size and retailers N.
Speedup vs. Sequential
512
256
128
64
32
16
8
32
64
128
256
512
Width of hidden layers
Figure 5. Speedup of Picard Iteration relative sequential, function of size of neural net.
17


Reviews:
[{"review_id": "e9ojPHSSFe", "reviewer": "Reviewer_D3aU", "summary": "This paper introduces the Picard Iteration algorithm to accelerate policy simulation in reinforcement learning for supply chain optimization (SCO) problems, where simulating a single trajectory can take hours due to the serial nature of policy evaluations. The key innovation allows for the batched evaluation of a policy across a single trajectory by assigning policy evaluation tasks to independent processes and using a cached evaluation system that iteratively converges to the correct sequential simulation. The authors prove that for supply chain problems, this approach converges in a number of iterations independent of the time horizon, resulting in significant speedups. Empirical results demonstrate a 400x speedup on large-scale fulfillment optimization problems using a single GPU compared to sequential evaluation, and a 100x improvement over the Time Warp algorithm (a traditional parallel discrete event simulation approach). Additional experiments show that the method generalizes well to inventory control problems and has promising applications to standard reinforcement learning environments outside of supply chain, potentially providing speedups of up to 40x in MuJoCo environments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review! Please see our responses below.\n\n## Implementation Details \n*Re: \"...it provides limited detail on implementation challenges...\"*.\n\nThank you for raising this point. Due to space constraints, we provide detailed implementation specifics in Appendix A.3. As you note, chunk size significantly affects performance; however, our experiments show robust speedups of approximately 200-440X across a range of chunk sizes from 30 to 300; we can provide further details in the Appendix.\n\nSelecting good hyperparameters is straightforward: a reasonable heuristic for tuning this hyperparameter is to simulate a sub-trajectory of length $\\ll T$, and select the values which minimize the time required to simulate this sub-trajectory.\n\nWe will provide these details in the manuscript, and we also plan to release a package implementing Picard iteration. The supplementary materials provided with our submission also contain all the code used to generate the experiments in the paper.\n\n## Settings with expensive dynamics\n\n*Re: \"While this paper focuses on scenarios where policy evaluation is expensive compared to state transitions\"*\n\nThis is a great point. Actually, to a large extent, what one considers to be \"state\" vs. \"action\" in our framework is a design choice. In other words, the user has flexibility to determine which parts of the combined vector $(s_{t+1}, a_t)$ are generated in parallel and cached (i.e., treated as the \"action\"), and which are recomputed on the fly by each worker (i.e., treated as the \"state\"). The most efficient partitioning of state and action is problem dependent, and as you note, could involve a reversal of the nominal roles if dynamics are expensive. \n\n\n## Specific Questions\n\n### 1. Re: effect of initial action sequence \n\nLoosely speaking, the closer the initialization is to the correct trajectory, the fewer iterations will be required. In a policy optimization setting, the most obvious and effective approach to initialization is to use trajectories collected using the previous policy iterate to initialize Picard Iteration, to collect trajectories using the current policy iterate. This is what we do in our policy optimization and MuJoCo experiments.\n\nIn the policy evaluation setting for FO, we study the sensitivity of Picard Iteration to the initialization by experimenting with three natural initializations:\n\n- Unfulfill (441x Speedup): initially, all orders are unfulfilled. This setting corresponds to the theoretical results and experiments currently in the manuscript.\n- Naive (358x Speedup): Initially, fulfill all orders from their nearest fulfillment center, ignoring inventory and capacity constraints.\n- Random (390x Speedup): Initially, fulfill all orders from a random FC.\n\nClearly, different initialization methods have an impact on the simulation speed, although massive speedups are possible regardless.\n\nHere, it appears that the \"Unfulfill\" strategy works the best. The intuitive explanation for this is consistent with our analysis: using this initialization strategy, after the first iteration, each processor will have correctly accounted for inventory and capacity consumed by orders for that processor's own products -- in some sense, a \"greedy\" initialization which is less naive than the \"Naive\" approach above. Further, unlike the alternatives, when initializing each chunk, this procedure is able to account for inventory and capacity consumed in previous chunks. We will add this discussion to the appendix.\n\n\n### 2. Convergence of action sequences\nWe observe similar convergence behavior for the RMSE of actions as we do for states. This should intuitively be the case as we would expect reasonable controllers to exhibit some sort of Lipschitz continuity, especially over regions of the state space for which we have training data. \n\n### 3. Understanding convergence on MuJoCo\n\nThank you for highlighting this interesting observation. We agree that understanding the factors affecting convergence in continuous control settings is an exciting direction.\n\nAs a first step towards this kind of analysis, we can consider linear control of a linear dynamical system. Writing out the Picard iteration explicitly, with each timestep assigned to a different processor, this turns out to be equivalent to solving a particular linear system via fixed point iteration. More precisely, letting $X^{(k)} \\in \\mathbb{R}^{T \\times d}$ be the matrix of state variables at iteration $k$, across all times $t \\in [T]$, the Picard iteration computes $X^{(k+1)} = A X^{(k)} + b$ for some appropriately shaped $A, b$ which depend on the the matrices describing both the dynamics and the controller. It is then straightforward to show that $X^{(k)}$ converges geometrically at a rate depending on the spectral radius of the matrix $A$.", "claims_and_evidence": "Yes, the claims made in the paper are well-supported by both theoretical analysis and empirical evidence. The authors provide formal proofs for the convergence of their Picard Iteration algorithm in supply chain optimization contexts, along with extensive experimental results that demonstrate the claimed speedups across different problem settings, batch sizes, and demand distributions. The comparison against baseline methods like Time Warp is thorough, and they extend their evaluation to other domains like MuJoCo environments to show broader applicability.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are well-suited for the problem. The authors evaluate their Picard Iteration algorithm on relevant supply chain optimization problems (fulfillment optimization and inventory control), using realistic parameters based on industry settings. Their benchmarking against sequential simulation and Time Warp provides appropriate baselines. The additional exploration in MuJoCo environments demonstrates broader applicability beyond the supply chain domain.", "theoretical_claims": "I only checked the claims in the main text and I think they are reasonable. The proof approach for Theorem 3.1 in the special case (greedy policy without inventory constraints) is logically sound and builds intuitively on the properties of wrong actions and capacity exhaustion. The setup of Lemma 3.2 and its application to prove convergence in J+1 iterations follows naturally.", "experimental_designs_or_analyses": "I checked the experimental designs and analyses, and I feel the current setup is good. The authors present comprehensive experiments across different problem settings, with appropriate controls and ablation studies that demonstrate the robustness of their approach.\n\nWhile I think it could be possible to strengthen the paper by talking about how the initial actions affect the convergence - for example, explicitly showing that setting the actions to a better policy can speed up the convergence. In the MuJoCo experiments, they use the previous policy iterate to initialize the cache, which is intuitive, but a more systematic study of initialization strategies could provide additional insights.\n\nAlso, for the normalized error metrics, I think it would be interesting to show the RMSE of actions not only the states. This would provide a more complete picture of convergence behavior and could potentially reveal different convergence patterns between state trajectories and action trajectories.", "relation_to_broader_scientific_literature": "The paper's key contribution of using Picard iteration for parallel policy simulation relates to several research areas. It addresses limitations in parallel discrete event simulation methods like Time Warp, which don't work well for supply chain problems lacking local causality properties. The approach complements existing parallel reinforcement learning literature (e.g., Asynchronous RL, RLlib) by focusing on accelerating a single trajectory rather than parallelizing across multiple trajectories or agents.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\n\nPractical Impact: The paper addresses a significant bottleneck in applying RL to large-scale supply chain problems. A 400x speedup could transform what were previously impractical approaches into viable solutions.\n\nTheoretical Guarantees: The authors provide formal proofs that Picard converges to the correct trajectory and, more importantly, that it does so in a number of iterations independent of the simulation horizon length for SCO problems.\n\nComprehensive Evaluation: The experimental validation is extensive, testing across various problem configurations, including different batch sizes and demand distributions.\n\nWeakness:\n\nWhile the paper demonstrates impressive performance gains, it provides limited detail on implementation challenges. Although the authors mention using JAX and GPU acceleration, it would benefit the practitioners if they could talk more about optimization of synchronization between iterations, or parameter tuning strategies like selecting optimal chunk sizes.", "other_comments_or_suggestions": "While this paper focuses on scenarios where policy evaluation is expensive compared to state transitions, there's also an opportunity to consider the inverse case. In many complex environments like physics simulations or large-scale agent models, state calculations can be more expensive than policy evaluations. Perhaps a \"cached state\" approach could be developed, mirroring the Picard Iteration but in reverse. Instead of caching actions, we could cache intermediate states and only recalculate states when necessary.", "questions_for_authors": "1 How does the choice of initial action sequence affect convergence speed in practice across different environments? Have you systematically studied how different initialization strategies impact convergence rates in various problem settings, and are there heuristics for selecting initial action sequences that could accelerate convergence?\n\n2 In your convergence analysis for MuJoCo environments (Figure 3), you measure relative RMSE of state trajectories. Have you also analyzed the convergence behavior of action trajectories? \n\n3 Figure 3 shows significantly different convergence patterns across MuJoCo environments, with some converging in just 2-3 iterations while others require 10+ iterations. Do you have insights into why these differences occur? Are there specific properties of these environments (state transitions, policy complexity, dynamics) that predict faster or slower convergence with Picard iteration?", "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": "thvCOTvZbe", "reviewer": "Reviewer_UC5Y", "summary": "The paper studies the acceleration of policy simulation for supply chain problems often solved via RL. The objective is to accelerate sequential evaluations using caching mechanisms to be able to parallelize/batch simulations. Numerical experiments are performed for supply chain problems and beyond.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review! Please see our responses below.\n\n*Re: Do you have a supporting reference for the claim?*\n\nOur claim is based on direct experience from industry deployments and discussions with practitioners at major e-commerce companies. These conversations consistently confirmed the need for hours (if not days) of simulation time. It became very apparent in these calls with practitioners that the daily simulation need vastly exceeds the time available, such that often approximations (such as only simulating a portion of products and extrapolating their resource usage and cost to other products) are used to make daily decisions. Our work, however, may allow many of these simulations to be run in the available time window.  Unfortunately, we are not allowed to provide a specific citation for these useful discussions. \n\nNote that the fulfillment optimization problem only comprises a small piece of the daily supply chain puzzle to be solved. For instance, the outcome of our fulfilment simulation also informs resource planning at fulfilment centers, transportation planning, etc. It is thus essential the simulation happens fast, such that other algorithms can use the output. \n\nWhile confidentiality prevents us from explicitly citing these discussions, we've ensured our numerical settings are realistic and conservative, drawing on publicly available industry data from Amazon and Walmart, as cited at the beginning of Section 4.1 and in Appendix B.3. We believe our chosen settings are representative for a large amount of companies (and conservative for truly large-scale settings).\n\n## Specific questions\n\n### 1. Hyperparameter tuning\n\nYes, the main hyperparameter to tune is what we have called \"chunk size,\" i.e., the number of steps to execute at each iteration. While choosing a good value for this parameter can substantially improve performance, Picard Iteration still achieves massive speedups relative to sequential simulation for a wide range of chunk sizes -- our experiments show robust speedups of 200-440X across a range of chunk sizes from 30 to 300. Hyperparameters can be tuned at low cost by selecting those that maximize simulation speed for a small sub-trajectory. \n\n### 2. Limitations\n\nTo understand potential limitations, consider a back-of-the-envelope analysis of the key factors contributing to the simulation runtime:\n\n - $t_{\\pi}$, the time needed to execute the policy at a single time step\n - $t_f$, the time needed to execute one step of the dynamics\n - $T$, the problem horizon (number of steps)\n - $K$, the number of iterations required for Picard iteration to converge\n - $M$, the number of parallel processors available.\n\nSequential execution requires time $T(t_\\pi + t_f)$, whereas Picard iteration requires $K(Tt_\\pi/M + T t_f)$ (for $M \\leq T$). Potential limitations are easy to see from this equation:\n\n- If $K$ is sufficiently large, this can offset the benefits of parallelization. As we show in the paper, $K$ is provably small in many useful cases, but this does not hold universally; see the worst case setup in response to the next question.\n- If $t_f$ is sufficiently large (i.e., dynamics are very expensive) then the term $KTt_f$ can dominate. In many real problems (such as the FO and inventory management settings we analyze) the dynamics are trivial to compute, so $t_f$ is negligible. For settings where this is not true, this dependence can be improved by computing expensive parts of the state transitions in parallel and caching them, as we do for actions. \n\n### 3. Worst-Case Setup\n\nIndeed, one can construct a problem and Picard iteration scheme (i.e., allocation of tasks to processors), for which convergence requires $T$ iterations, although this is quite pathological. \n\nConsider a setting with a single product, two parallel processors and two fulfillment centers (FC), FC1 and FC2, starting with equal capacity. Suppose that event assignments alternate between the two processors (i.e., processor 1 is responsible for odd-numbered events, and processor 2 for even-numbered events). Suppose that the policy is simply to fulfill orders from the FC having the largest remaining capacity, with a preference for FC1 over FC2 in case of ties. Finally, suppose that the initial trajectory provided to Picard Iteration is to unfulfill all orders.\n\nIn this scenario, at the first iteration, both processors will fulfill all orders from FC1; In the second iteration, starting from the time $t=2$, both processors fulfill all subsequent orders from FC2; and in the third, starting from $t=3$, both processors fulfill all subsequent orders from FC1. They continue to alternate like this for $T$ iterations until convergence.\n\nNote that, in the implementation of Picard iteration that we analyze, since there is only one product, all events would be assigned to the same processor, which avoids these conflicts.", "claims_and_evidence": "The claims of the paper appear valid.", "methods_and_evaluation_criteria": "The approach used is interesting. The presentation of the concepts is reasonable.", "theoretical_claims": "The theoretical claims appear solid. However, I did not check all proofs provided in the Appendix in full detail.", "experimental_designs_or_analyses": "The experimental design is reasonable. Examples for supply chain problems as well as from MuJoCo are performed. Results are suitably discussed.", "relation_to_broader_scientific_literature": "The related literature is suitably discussed.", "essential_references_not_discussed": "n.a.", "other_strengths_and_weaknesses": "Strengths:\n\n- Analytical results (convergence)\n\n- The provided experiments are overall convincing\n\nWeaknesses:\n\n- Limitations of the approach could be discussed in more detail", "other_comments_or_suggestions": "page 1 contains the claim: “For a policy parameterized by a non-trivial deep neural network (DNN), the task of simply simulating a single sample path under the policy can thus take several hours (or more) in the context of an SCO problem”\n\nDo you have a supporting reference for the claim?", "questions_for_authors": "(1) Do hyperparameters have to be tuned?\n\n(2) What are the limitations/downsides of the approach?\n\n(3) Is there a worst case setup?\n\n(4) Can the approach be used outside Supply Chain problems? How do the assumptions have to be adapted/generalized?", "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": "wKVPXxlre3", "reviewer": "Reviewer_4umB", "summary": "This paper provides an iterative algorithm that is easy to parallelize with GPUs to speed up policy evaluation in RL. The theoretical analysis is specific to supply chain optimization, where the authors leverage the assumption that demand is significantly higher than supply so that actions at different time steps are largely independent, proving that the algorithm converges in a small number of iterations (independent of the time horizon length). The computational studies provide empirical evidence that largely aligns with the theoretical analysis and extends the applications to RL settings beyond supply chain analysis.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review! Please see our responses below.\n\n\n## Comments on Exposition\nThank you for these helpful comments! We will be sure to clarify these points in the updated manuscript. Please see specific clarifications below.\n\n### Re: Intro and scope\n\nYou are correct that, while Picard Iteration applies immediately to any MDP, the theoretical analysis of convergence is problem specific. However, there is actually a variety of problems in SCO that can be studied using similar methods. Our analysis for FO problem can admit replenishment as long as the replenishing frequency is not too high (Appendix C). Beyond the FO problem, we also address the inventory control problem — another representative example of SCO — in the Appendix B (due to space constraints). We develop a theoretical analysis for the inventory control problem, and demonstrate demonstrate significant speedups in experiments. \n  \n  That said, your suggestion regarding exposition is well taken—we will revise the introduction in the final version to better clarify the scope and focus of the paper, as well as to clearly state our theoretical assumptions.\n  \n### Re: Exposition of Theorem 3.1 / 3.2\n\nThank you for this suggestion! We will make the exposition clearer in this section. To clarify the goals of the current manuscript: \n  \nTheorem 3.1 is an informal statement of Theorem 2.2, with the goal of enabling the reader to quickly grasp the main idea of our result: that Picard Iteration provides a factor $\\sim M/J$ speedup, which we obtain by bounding the number of iterations as $|\\mathcal{Q}_{T}|$. \n\n  \n  In Section 3.1 we then prove a special case of the main theorem (Theorem 3.1/3.2) for a specific greedy policy, which is easier to analyze. The goal of this section is to demonstrate the more general proof architecture, and to provide intuition for why one might hope that the number of iterations required should be small: The action taken at every time step is either going to be correct or will go to a node that would run out of capacity in the sequential scenario (Lemma 3.2).  Theorem 3.1/3.2 follows directly from this Lemma, for a greedy policy. \n  \n  Subsequently, Section 3.2 states that the same result holds for a broader class of policies. As the analysis is more involved (but the result is the same), we defer this analysis to the Appendix. \n  \n### Re: No replenishment\nThanks for raising this point. First, we note that the setting without replenishment is commonly studied in the literature (e.g., https://pubsonline.informs.org/doi/10.1287/educ.2019.0199).  That said, adding replenishment indeed makes the setting more comprehensive and realistic. In Appendix B.3 we show the method's applicability in a one-warehouse-multi-retailer problem with replenishment. We find that the number of iterations is bounded by twice the number of times the central warehouse is replenished during the horizon, which is typically small compared to the total number of timesteps. We also confirm this result empirically, achieving up to 380x speed-ups for settings with 1,000 retailers. In addition, in Appendix C, we briefly present our generalization of the FO problem with replenishment, and show that the Picard iteration still converges quickly if the frequency of replenishment is low. We can add more details for the discussion in the revised version.\n\n### Re: usage of $\\mathcal{Q}_T$\n\nThank you, we will correct this -- it should be the cardinality $|\\mathcal{Q}_{T}|$. \n\n## Specific Questions\n1. *Re: MLP approximation to greedy:* The goal here is to simulate a computational workload representative of the kinds of heavy-weight neural network policies often used in reinforcement learning for supply chain. To this end, we need to experiment with some sort of neural network policy which behaves predictably, which we obtain by cloning the greedy policy. We will clarify this in the experimental setup.\n2. *Re: \"Increased conflicts\"*: Thank you for noting this -- we mean that the number of required Picard iterations increases.  We will correct the language in this section to make it consistent with the rest of the paper.", "claims_and_evidence": "The claims are generally well-supported. I only have one concern related to the introduction.\n\nWhile the introduction outlines a general challenge in supply chain optimization (SCO), the theoretical analysis focuses specifically on fulfillment optimization (FO) problems that are not supply-constrained and have no replenishment. The assumptions made in the theoretical analysis may not generalize well beyond FO problems. I suggest revising the introduction to more clearly state these key assumptions and the specific focus of the paper to better align with its scope and contributions.", "methods_and_evaluation_criteria": "The proposed method focuses on letting the algorithm converge in a small number of iteration. The numerical studies report the number of iterations taken to converge. They are well aligned.", "theoretical_claims": "I reviewed the proofs of Theorems 3.1 and 3.2. I didn't spot any major issues.", "experimental_designs_or_analyses": "Yes, I checked. I didn't identify any major issues. Some suggestions are mentioned in the \"strengths and weaknesses\" section below.", "relation_to_broader_scientific_literature": "The idea aligns with the recent trend of taking advantage of GPUs to accelerate optimization algorithms that are predominantly implemented with CPUs to date, thus could be interesting to a broad community.", "essential_references_not_discussed": "I didn't identify any missing references that are essential.", "other_strengths_and_weaknesses": "**Strengths**:\n\n- Overall, the paper is very well-written and thus easy to follow.\n- The idea aligns with the recent trend of taking advantage of GPUs to accelerate optimization algorithms that are predominantly implemented with CPUs to date, thus could be interesting to a broad community.\n- The numerical studies present significant speedups compared to existing methods.\n\n**Weaknesses**:\n\n- **Exposition**. My primary concern relates to the exposition, specifically the following two points.\n    -  **Intro**. While the introduction outlines a general challenge in supply chain optimization (SCO), the theoretical analysis focuses specifically on fulfillment optimization (FO) problems that are not supply-constrained and have no replenishment. The assumptions made in the theoretical analysis may not generalize well beyond FO problems. I suggest revising the introduction to more clearly state these key assumptions and the specific focus of the paper to better align with its scope and contributions.\n    - **Section 3**. In section 3, the authors choose to present a detailed proof of a specific result (Theorem 3.1) and defer the proof of a general result (Theorem 3.2) to the appendix. Given that presenting Theorem 3.1 does not seem to yield much additional insight, the authors might consider restructuring this section to highlight the most significant contribution, i.e., Theorem 3.2, and present Theorem 3.1 as a corollary. Alternatively, the authors might restructure the discussions around Theorem 3.1 to highlight the insights obtained by analyzing this simple case---which might be hard to obtain given the complexity of the more general case.\n\n- **Theorem 3.2**. $\\mathcal{Q}_T$ was defined as a set in lines 262--263, but is used as a scalar in this statement.\n\n- **No replenishment**. While the assumption of no replenishment enables elegant theoretical analysis, it warrants more careful justification since it may deviate from common supply chain practices. \n\n- **Data generation**. To ensure that the paper is self-contained, it would be helpful if the authors provided a brief description of their data generation process.", "other_comments_or_suggestions": "- PO is not defined in the main body.", "questions_for_authors": "- Section 4.1. What do you use an MLP to approximate the greedy algorithm instead of implementing it exactly?\n- Section 4.1. In line 320, what does \"increased conflicts\" mean?", "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:

Meta-review: This paper introduces the Picard Iteration algorithm to accelerate policy simulation in reinforcement learning for supply chain optimization (SCO) problems, where simulating a single trajectory can take hours due to the serial nature of policy evaluations. The authors prove that for supply chain problems, this approach converges in a number of iterations independent of the time horizon, resulting in significant speedups. Empirical results demonstrate a 400x speedup on large-scale fulfillment optimization problems using a single GPU compared to sequential evaluation, and a 100x improvement over the Time Warp algorithm. 

The reviewers unanimously agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the rebuttal/discussion, I tend to agree. Please incorporate the following comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Use the additional page to include some details about the implementation challenges and the effect of initialization (response to Rev. D3aU)
- Include the limitations and the worst-case setup for the Picard iteration (response to Rev. UC5Y)
- Restructure the introduction according to the suggestion of Rev. 4umB
Decision: Accept (poster)