Operator Theory-Driven Autoformulation of MDPs for Control of Queueing Systems
Authors: Victor Baillet
Yuanzhang Xiao
Nicolás Astorga
Mihaela van der Schaar
Venue: ICLR 2026 Poster (2026)
Keywords: Autoformulation
autoformalism
large language model
Markov decision process
queueing systems
Primary area: applications to robotics, autonomy, planning
TL;DR: We present an LLM-driven method that autoformulates MDPs from natural-language descriptions, achieving interpretability, accuracy, and reduced complexity by operator-graph Bellman representation, tailored MCTS and a low-complexity algorithm.

Abstract: Autoformulation is an emerging field that uses large language models (LLMs) to translate natural-language descriptions of decision-making problems into formal mathematical formulations. Existing works have focused on autoformulating mathematical optimization problems for $\textit{one-shot}$ decision-making. However, many real-world decision-making problems are $\textit{sequential}$, best modeled as $\textit{Markov decision processes}$ (MDPs). MDPs introduce unique challenges for autoformulation, including a significantly larger formulation search space, and for computing and interpreting the optimal policy. In this work, we address these challenges in the context of queueing problems---central to domains such as healthcare and logistics---which often require substantial technical expertise to formulate correctly. We propose a novel operator-theoretic autoformulation framework using LLMs. Our approach captures the underlying decision structure of queueing problems through constructing the Bellman equation as a graph of $\textit{operators}$, where each operator is an $\textit{interpretable}$ transformation of the value function corresponding to certain $\textit{event}$ (e.g., arrival, departure, routing). Theoretically, we prove a universal three-level operator-graph topology covering a broad class of MDPs, significantly shrinking the formulation search space. Algorithmically, we propose customized Monte Carlo tree search to build operator graphs while incorporating self-evaluation, solver feedback, and intermediate syntax checking for early assessment, and present a provably low-complexity algorithm that automatically identifies structures of the optimal policy (e.g., threshold-based), accelerating downstream solving. Numerical results demonstrate the effectiveness of our approach in formulating queueing problems and identifying structural results.

OPERATOR THEORY-DRIVEN AUTOFORMULATION OF MDPs FOR CONTROL OF QUEUEING SYSTEMS
Victor Baillet', Yuanzhang Xiao², Nicolás Astorga' & Mihaela van der Schaar
University of Cambridge Univerritty of Hawai'i at Mãnoa
ABSTRACT
Autoformulation is an emerging field that uses large language models (LLMs) to translate aatural-lngguaee descriptions of decision-making problems into formal mathematical formulations. Existing works have focused on autoformulating math- ematical optimization problems for one-shot Decision-making. However, many real-world decision-making problems are sequential, best modeled as Markov decision processes (MDPs). MDPs introduce unique challenges for autoformula- tion, including significantly larger formulation search space, and for computing and interpreting the optimal policy. In this work, we address these challenges in the context of queueing mentrrl to domains such as healthcare and logistics-wii -which often require substantial technical expertise to formulate cor- rectly. We propose novel operator-theoree autoformulation framework using LLMs. Our approach captures the underlying decision structure of queueing prob- lems through constructing the Bellman equation as graph of operators, where each operator is an interpretable transformation of the value function correspond- ing certain event (e.g., arrival, departure, routing). Theoretically, we prove a universal three-level operator-graph topology covering broad class of MDPs, significantly shrinking the formulation search space. Algorithmically, we propose customized Monte Carlo tree search to build operator graphs while incorporat- ing self- celf-evaluation, solver feedback, and intermediate syntax checking for early assessment, and present a provably low-complexity algorithm that automatically identifies structures of the optimal policy (e.g., threshold threshold-based), accelerating down- stream solving. Numerical results demonstrate the effectiveness of our approach in formulating queueing problems and identifying structural results.
INTRODUCTION
Autoformulation with large language models (LLMs) aims to translate natural-language descriptions of decision-making problems into formal optimization models with minimal human intervention (Zhang et al., 2025b). It democratizes the access to advanced operations research (OR) modeling tools for non-OR domain experts and facilitates rapid prototyping and adaptation for OR practitioners (Gurobi Optimization, 2023; Wasserkrug et al., 2025).
Existing works on autoformulation have been focusing on mathematical optimization, which models one-shot decision-making (Ramamonjison et al., 2023; Xiao et al., 2023; AhmadiTeshnizi et al., 2024; Astorga et al., 2025; Bertsimas & Margaritis, 2024; Liang et al., 2025; Yang et al., 2025; Lu et al., 2025; Zhang et al., 2025a; Huang et al., 2025). However, many real-world scenarios evolve dynamically and stochastically, thus requiring sequential decision-making over time. These problems are naturally modeled as Markov decision processes (MDPs) (Puterman, 2014). Autoformulating MDPs presents unique challenges that cannot be addressed by current works on autoformulating optimization problems (see Table 4 and the examples in Appendix A for more detailed breakdown).
Formulation Challenges. Similar to autoformulating optimization, autoformulating MDPs requires searching the vast space of possible formulations. Moreover, MDPs have additional components (e.g., states, transition probabilities) and implicit constraints (e.g.. nonnegative states, state-dependee action sets) that are not present in optimization and often omitted in the problem description. To ensure the accuracy, autoformulation must identify and infer these hidden structures (e.g., figuring out state transition probabilities of queue from arrival and service rates).

---

Taredatke Chalege E: fax medeinddiaa qpaare prac
Dermatadiv Challias New Nacallos Auylaa Coanna.
Compatidin Ch Chillgg Ca Coonas
Oriicll percens Gencill
Do never enhonll plok apriige god solaco carch secc
Talland MSC1S wilh gallae valver Cos NIAV.
hets
by joiend pricie Beclerp
Se To Pollies
Or anhil decll palor
yueing conic codram koys
Hs
Lihinal Tipelayy
prara ouree prace pricis
Tess Paa of Pomes (1P))
Poodai TT
Apotiia Se Tolia
Courrbetan LAjorrkau IS Thaeee-2
systne paicay unide Lie pukleg)
Remulako
cecporabll pollcr
Figure 1: Challenges in formulation, solution, and interpretation, and our contributions in addressing them.
Text-to-operator mappings improve accuracy and the interpretability of problem formulation The operator-basel Bellman equation reveals the structures of the optimal policy (e.g.. monotone or threshold) and the value function (e.g.. convex), enhancing both interpretability and computational tractability (by informing the choice of an appropriate solver).
Computational Challenges. Many optimization problems (e.g., convex optimization) are considered solved once formulated (Boyd & Vandenberghe, 2004). In contrast, MDPs are notorious for the curse of dimensionality (Puterman, 1994). Although formulating and solving are two distinct phases, we advocate for autoformulation that is amenable to discovering structural properties of the optimal policy (e.g., optimal action is monotone in state value) prior to the solving phase and therefore mitigating computational challenges (e.g., search among monotone policies instead of all policies).
Interpretability Challenges. Optimization models tend to be more readable, because variables and constraints in the problem formulation often have semantic meanings, and the optimal decision variables are easier to understand. In comparison, the optimal policy of an MDP is a mapping over multi-dimenssonal state-action pairs, which can be hard to interpret. Therefore, identifying structures of the optimal policy (c.g. monotonicity of action in state) makes the solution interpretable, which is important for decision-support systems (Hajek, 1984; Koole, 1995; Zhou et al., 2015).
Our Solution. Fig. illustrates how framework addresses the above challenges. Our work builds on the operator theory (Koole, 1998; 2007), which views the Bellman equation as a concatenation of operators. Each operator is an interpretable transformation of the value function that corresponds to certain event (e.g., arrival, departure) in the context of controlling queue systems. The operator-based Bellman equation provides an interpretable problem formulation. as well as theoretical foundations for identifying structures of the optimal policy, which can potentially reduce the complexity of solving MDPs and enhance the interpretability of the solution. We make significant contributions to fulfill the potential of operator theory-driven autoformulation of MDPs. Operator graph and universal topology: We are the first to represent Bellman equations as directed acyelic graphs (DAGs) of operators, namely the operator graph, and prove the existence of universal topology for large class of MDPs (Theorem 4. 1). This greatly reduces the autoformualtion search space from all possible operator graphs to graphs with the fixed universal topology (formulation challenge). Tailored Monte Carlo tree search (MCTS): We propose a customized MCTS with LLMs to generate and evaluate operator graphs (Sec. 4.2), while incorporating L.M selffevaluation, solver feedback, and intermediate syntax checking to improve the accuracy and efficiency of autoformulation without expensive fine-tuning of LLMs (formulation challenge). > Automatic identification of structures: We propose a low-complexity algorithm (Algorithms 1-3) that is guaranteed to identify theoretically known structures of the optimal policy (Theorem 4.2), thus mitigating the curse of dimensionality (computation challenge) and enhancing solution interpretability (interpretability challenge).
Contributions. ① Conceptually, we propose an operator theory-driven framework that for the first time, jointly automates the formulation of sequential decision-making problems from natural language and the discovery of the structures of the optimal policies (Sec. 4). Our novel view of Bellman equations as operator graphs addresses not only formulation challenges but also computation and interpretability challenges in the formulation phase. 2 Theoretically, we rigorously prove the existence of a universal operator graph topology for large class of MDPs, greatly reducing the search space of operator graphs (Theorem 4.1). ④ Algorithmically, we tailor MCTS for autoformulation of wwent-based MDPs by incorporating dense rewards and integrating the feedback from the solver for improved accuracy and efficiency (Sec. 4.2), and propose a provably low-complexity algorithm to automatically uncover structural results from the operator graph (Theorem 4.2). ① Empirically,
2

---

create the first dataset autoformulation of queueing problems, containing natural-languns problem descriptions labeled with the optimal policies and their structures, and demonstrate the accuracy and efficiency of our framework.
RELATED WORKS
Autoformulation of mathematical optimization. There have been considerable efforts in creating datasets containing natural-languee description of optimization problems (Ramamonjison et al., 2023; Yang et al., 2025) and developing LLMs and agents fine-tuned for optimization autoformulation (Xiao et al., 2023; AhmadiTeshhizi al., 2024; Liang et al., 2025; Lu et al., 2025; Zhang et al., 2025a; Huang et al., 2025). Recent works have shown that through prompting and efficient MCTS, open-source LLMs can achieve comparable (Bertsimas & Margaritis, 2024; Astorga et al., 2025). Our framework also uses MCTS without fine-tuning. However, we make significant contributions in addressing the formulation challenges specific to MDPs, and computation and interpretability challenges that these works do not face.
better performance without the cost of fine-tuning
Autoformulation of dynamic programming. The most related is the recent work autoformulating dynamic programming problems (Zhou et al., 2025). It focuses on synthetic dataset generation and LLM fine-tuning, but did not consider computation challenges and interpretability challenges.
Addressing computation challenges in MDPs. A large body of research addresses efficient solving of MDPs, notably through approximate dynamic programming (Bertsekas, 2012), reinforcement learning (Sutton, 2018), and exploiting structural properties of the solution (Yang, 2020; Koutas et al., 2025). These approaches are complementary ours, and can be used in conjunction with our work after structural properties are identified in the formulation phase.
Operator-based Bellman equations for control of queueing systems. Significant OR research is devoted to uncovering structural properties of the optimal solution (Zhuang & Li, 2010: Hsu et al., 2015; Çil et al., 2011). Despite the unifying operator theory framework Koole (1998; 2007), such practices are still on manual, case-by-case basis. In our attempt to autoformulate MDPs, we are the first to view the operator- based Bellman equation as an operator graph, and prove the novel result on the existence of universal graph topology. In addition, we propose low-complexity algorithm to automate the process of identifying structural results.
Table I: Comparison with existing works on antoformulation.
Reprosntative work
Probicm Formulated
Method
Formulation Challange
Computation Challenge
Interpretabliity Challang
ORLM (Huung al., 20055
opimizatiio
fine-tuning
optimization
spocifie to
N/A
N/A
Ausofonmuutor (Astooga 2025)
optimization
prompting
specific optanizattiou
N/A
NM
DPI. M 2025)
(disesto--ime) dynamtic programming
Gro-ttniin
Work
discrete-tiuee
continuous- time MDP
prompting
PROBLEM FORMULATION
Our framework autoformulates and solves discrete-time MDPs and continuous-time MDPs (through their equivalent discrete-time embedded MDPs). Throughout the paper, we illustrate framework using examples from healthcare (Chan et al., 2025; Bekker et al., 2017). But our framework can be applied to a variety of applications such as inventory management (Schwarz & Daduna, 2006), logistics (Adelman, 2007), transportation (Stidham, 1985; Ebben et al., 2004), and telecommunication (Koole & Mandelbaum, 2002; Bhulai & Koole, 2003). As shown in Appendix M, our prompts include no contextual information on application domains or even queuing systems in general.
3.1 PRELIMINARIES
Since the results here are established, we provide detailed derivations in Appendix D.I and a walk- through example in Appendix D.2.
3

---

Control of Queuing Systems as Continuous-Time MDPs. We consider continuous MDP specified by six elements (Lippman, 1975; Serfozo, 1979): (1) a countable state space S, (2) a finite set of eligible actions A, at each state E S, (3) cost Č(s, a) incurred at state when taking action a, (4) the state transition probability P(s'ls, a), (5) the random transition time from state-action pair (s, a) to different state, which follows an exponential distribution with rate X(s, a), and (6) discount rate a 2 0 that discounts the cost at time by eaot
Optimization Criteria. For stationary policy S + Ag, the a-discounted cost is (Serfozo, 1979)
(+) - E 1Ei= e ((8, a:) 80 =],
where 4 is the time of the i-th state transition. The averuge cost is (Sennott, 2009; Serfozo, 1979)
j- (s) A sup E E/ 0(s;, at)/t///// 80 =
t-3:00
where 4, = maxfi: : & S t) is the number of state transitions that occur in time t.
Discrete-Time Embedded MDPs and Standard Bellman Equations. For arbitrary upper bound of state transition rates A > supa,a X(s, a), we define a discrete-time MDP with discount factor y = A+a and state transition probabilities and the cost function
P(5'(s,a) 1 A(s, a) P(slss, if s' 1 a)s,a)/,,
and c(s,a) M(s,0) +a A+a
C(s,a).
i =s
The discrete-time embedded MDP is obtained by setting a Poisson clock with rate A and sampling the continuous-time process when the clock ticks. So the state may remain the same (s' = s).
Given a stationary policy π, the dddiscounted cost Vy (s) Ex E 7"t d((s a.) so = s]. and the average cost is Jg (s) lim simsup,- s Ex EnD c(s,, a 8o
The discrete-time MDP A,, c, P,7) is equivalent to the continuous- time MDP (S, AA,, 2, P, P,.). in the sense that Va, (s) Vy,a (s) and (x)s) Jn (A) for any stationary policy (Serfozo, 1979). We solve the discrete-time MDP by solving the standard Bellman equation:
(8)
min {c(s,a) +7 Eves P(d'(8, (v.))')) aEA,
(4)
where (s) ) is the minimum discounted cost during the last state transitions when starting from
Under mild conditions (Puterman, 2014), the minimum discounted cost V,, = inf Vy, (s) the limit of Vn,y(s) (s) when n. co (Sennott, 2009, Proposition 4.3.1), 1), and the minimum average cost J(s) = inf, (s) is the limit of (1 (s) when + 1 (Sennott, 2009, Proposition 6.2.3). Therefore, it suffices focus on the n--ransition discounted cost Vn,y the Bellman equation (4). For the remainder of the paper, we omit the discount factor in the subscript of Va,y and use Vn.
3.2 EVENT-BASER MDP AND OPERATOR- -ARRAD BELLMAN EQUATION
Definition 3.1. Event-based MDPs MDPs whose state (x,, e) has components: controllable component (e.g.. number of patients in the system) and an exogenous, uncontrollable component (e.g., arrivals), with transition probabilities decomposed as:
P [[x,,, (z, e). a] = Pa | (x,e), a) Pa(e' ( xx)).
(5)
Event-based MDPs are general enough to model decision -making problems in various applications (see Appendix for a comprehensive list). Many problems in control of queuing systems are special cases of event-based MDPs, where transitions of the queuing state are deterministic.
Definition 3.2. (Koole, 2007, Definition 3.1) Let X' be the set of controllable state components x and be the set of all functions from X' to R. An operator is a mapping
T: ve V, 82 1.
(6)
4

---

Controllable State
Event
Controllable State x'
Event e'
P ((d'ee))
P. [=' (z,e).a
Pa(e' 12')
Figure 2: State transition dynamics of event-based MDPs, where dashed arrows indicate dependency.
The definition of an operator is general, giving us flexibility to express the Bellman equation as concatenation of operators. Given the context, the operators also have physical meaning. For our example introduced in Fig 1, we can define operators related to optimal responses to events, namely the controlled arrivals (CA) and uncontrolled departures (D) for Critical (C) and General (G) patients. The details can be found in Appendix D.2 and Appendix E. In short, we have:
Toa V (x)] = VV4 (2, Ac); Toa [x) (2, T V (x:] Vi+1 (x,,
(7)
To [V (x)) V1, Dc);
with Acja and DC/a corresponding to arrival and departure events for Critical and General patients. also define a uniformization operator (with Ac + A + pc + (G))
(r)) U2(2), Un(r), = A U1(2) dE U2(2) + t U2(x)) -.(x))+(Uus(o))
and cost operator
Teost [U(x)] Ph (rc + xG) +a) a) U()).
(9)
Then the Bellman equation (38) can be rewritten as V going through an operator graph to get V
(x+1(z) Teest (Tunar (Tea, [V (z)] Tea, [V (=)] Tb,c (z)] T2. (x)))) (10)
Note that for event-based MDPs, often study the value function Vz((x) defined on the controllable state component æ, in addition to the standard value function (s) defined on the state 8.
METHOD
Our framework has two steps: autoformulation of operator-based Bellman equations and identification of structural results (see Fig. 1 for overview).
4.1 THFORETICAL FOUNDATION: UNIVERSAL TOPOLOGY OF OPERATOR GRAPHS
We can view the Bellman equation (10) as an operator graph with input V and output V If we view the process of problem formulation searching in the space of all operator graphs, the search space is vast due to the variety of operators (Koole, 2007) and the many ways they can be connected (i.e., graph topology). Specifically, the number of possible DAGs with N nodes (operators) and out-point (the operator that outputs Vit+1) grows in order of 2 (Robinson, 1973). have sense of how fast this number grows with N, the numbers of possible DAGs for N = .,..., ,9 are 1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312.
We prove the existence of universal graph topology for all event-based MDPs. This allows to fix the graph topology, thus significantly reducing the search space.
Theorem 4.1. For any event-based MDP with event set {e constructed by the following operator graph (the universal topology in Fig. I):
ee). its Bellman equation can be
Viti (x) = Teost {Tunit (Te, (v) ....),............. (x))),
(11)
where Teost [U()) c(x) + 7 Uxx), T Tunis (z), .... (.(())))...))))) Σラ P(ey (x) (z) and Te, [v) = ez,
Proof. See Appendix F.
5

---

Theorem 4.1 reduces the search space to three-level trees with Teost the root, Tunif as the single child of the root, and event operators as leaves. Hence, in addition to specifying the universal topology, also reduces the search space by specifying the rypes of operators at each level of the tree.
Takeaway: Theorem 4.1 is crucial for reducing the search space.
The original search space includes all the operator graphs with any topology and any operators as nodes, which is huge. Theorem 4.1 proves that there exists universal topology: a three-level tree with certain types of operators at each level. This significantly reduces the search space.
4.2 MCTS FOR AUTOFORMULATING EVENT-BASER MDPS.
Now that we know the universal graph topology, we aim to identify the correct nodes of the operator graph. Due to dependencies among components, MCTS well-suited for this hierar- chical search (see Appendix M for prompts). We decompose the search into four layers: mi (problem parameters, e.g., queue sizes), m2 (state variables and constraints), my (events, actions, costs, and their probabilities), and my (operators). This structure reflects the dependency hierarchy and guides exploration. Our MCTS follows the standard selesseletion, expansion, evaluation, and backpropagation- wiith two key modifications during backpropagation: (1) terminal nodes receive rewards from combination of LLM preference and solver feedback, and (2) intermediate nodes are evaluated for syntax validity provide dense supervision and penalize early errors.
Terminal Rewards. Every full rollout is scored relative to a bascline defined as the initial rollout. The LLM pro- vides a preference score sco TeLLM E [0, 1]. To reduce bias from LLM self-evaluation, we incorporate solver con- vergence s comereed E {0, 1}, and compute the final reward as scorefinal scOreLIM X scor
Back-prooagaaionn step in MC18
Eaily tecnination of bed bollouts
Rosaard from beminnal mudee
Intermediate Rewards. Inspired by AlphaZero (Silver et al., 2018), we assign rewards to intermediate nodes based on syntactic correctness. If partial formulation violates syntax constraints, the rollout is terminated early with zero reward. This enables faster pruning of invalid branches and accelerates convergence.
x 771
778
171
772
Symoo
LLM
Salver convergence
consesiency
evaluvtion
Figure 3: MCTS for constructing op- erator graphs. (1) Syntax check at intermediate nodes detects errors early, preventing failed full rollouts. (2) Solver feedback complements LLM self- evaluation for more objective rewards.
Iterative Prompting. Syntax errors are often local and should not always be penalized with zero reward. We allow the L.MM up to five attempts to fix syntax issues, using the error message as context. If correction fails, the error is attributed to carlier steps, and a zero reward is backpropagated. The backpropagation mechanism is illustrated in Figure with further details about our MCTS provided Appendix J.1.
4.3 AUTOMATIC IDENTIFICATION OF STRUCTURES OF OPTIMAL POLICIES USING DYNAMIC PROGRAMMING
Given the formulation of operator-based Bellman equations, aim identify the structures of optimal policies. This is usually done by identifying the properties of the value function V*(x). For example, if V*(z) is convex in x, the optimal policy x* decreasing x. For any operator T. we say that it propagates a property if, whenever V, satisfies the property, then T[V.] also satisfies it. For example, the linear cost operator Teast [x) +x(+ propagates monotonieity and convexity, because T=c.e (U()) is monotone (convex) if ([()) is monotone (convex). In the following and in the Appendix, we also say that an operator propagates A, where A is the space of functions having a certain property (for instance, all convex functions), and we may refer to A as "property" by abuse of language. There is some common wisdom regarding which properties certain typical operators propagate. However, since Vi (z) needs to go through the operator graph, the challenge is to find the properties that are propagated by all operators in the graph. A bruteforce approach would require checking exponentially growing number of possibilities.

---

To illustrate, consider two operators T1 and T2 and six spaces of functions A-F with certain properties. For example, A can be the space of convex functions, B the space of increasing functions, and An B the space of convex increasing functions. Operator Ií propagates A n B, E n C, and D. while operator 72 propagates C A, D n F, and B. In addition, we have B En C E.
By computing the closure under intersection, Tı is found propagate, for example, A BOD and E C D. Identifying the smallest common space propagated by both Ti and T2 requires leveraging the inclusion relationship; in this case, the minimal shared space is A B C, which is not immediately evident from the original lists of properties that each operator propagates. A more detailed explanation of this example can be found in Appendix G.I.
We introduce general dynamic programming algorithm to address this problem, providing a detailed explanation Appendix G.
Theorem 4.2 (Identification of Structural Results). Given an operator graph g. execution of Algo- rithuns 1-3 gives us the of properties propagated by all operators, with memory and time complexity (( and O(N O(N]G(), (e])), where [G] is the number of operators in the graph, N = maxTeg ntT, and Ny is the number of properties propagated by operator T.
Proof. See Appendix G.3.
A direct brutal force approach would construct, for each operator, the full family of spaces obtained by closing its propagated properties under intersection, but this closure grows exponentially. A key observation in our algorithm is that any common propagated space can be written as the intersection of a subset of the properties that each operator initially propagates. Thus, instead of generating the full closure, we focus on identifying the properties that may appear in the intersection defining the smallest common propagated space. This is achieved by iteratively removing any property that cannot belong to this intersection. In the example above, E' never appears in any space propagated by Tj and is not implied by any inclusion relationship, so no valid common space can involve F in its intersection representation. Consequently, properties such D n F propagated by Tr can be discarded. Repeating this pruning step yields a stable family of properties whose intersection is guaranteed be both common propagated space and the smallest such space. Proof and details on the treatment of inclusion relationships are provided in Appendix G.3.
Takeaway: Theorem 4.2 guarantees that, given an operator graph, Algorithm 1 can identify all structural properties detectable within our framework. Thus, our ability to recover structure from a problem description depends entirely on the operator graph generated by the LLM.
EXPERIMENTS
Dataset. We constructed dataset of 36 natural language descriptions of queueing control problems, varying in difficulty by size and shape of state spaces and number of event types. To assess perfor- mance structure identification and support future research, the dataset includes three categories: (1) problems with provable structural results (e.g., Example I): (2) problems with empirically observed, but unprovable, structures (e.g., Example 2); and (3) problems with no structural results. All problems are adapted from papers addressing realistic issues from domains such as hospital management (Bekker et al., 2017), telecommunications (Koole Mandelbaum, 2002; Bhulai & Koole, 2003; Bekker et al., 2011; Zhang et al., 2025c), freight dispatching (Schwarz & Daduna, 2006; Amjath et al., 2023), assembly lines (Adeyinka & Kareem, 2018), and traffic control (Boon al., 2023).
Experimental Setup. For each problem, we perform multiple MCTS roll-outs and select the best candidate by greedily following the highest-scoring path. Each formulation evaluated by running dynamic programming solver; if it fails to converge, it is deemed incorrect. The resulting value function is compared to the ground truth and accepted if within a predefined tolerance. We apply structure analysis algorithm to each roll-out. Results summarized in the following tables and interpreted with respect to the challenges in Appendix K, focusing on correctness, tractability, and interpretability. The code and dataset are available here.
7

---

5.1 ACCURACY OF AUTOFORMALIZATION AND ERROR ANALYSIS
Table 2 shows that our autoformulation framework outperforms baseline methods. Single-prompt methods fail entirely to solve the task, even with CoT prompting. CoT is both more computationally demanding and less effective than MCTS as a test-time scaling strategy. In contrast, MCTS achieves better performance with the same level of feedback (LLM, solver feedback, or syntax check). Although the first rollout is relatively costly, MCTS becomes increasingly efficient by reusing prior computations. Notably, achieves comparable or better performance using fewer computational resources than baseline methods.
Ablation suddycomppring with MCTS without SF and/or SC shows that the incorporation of syntax checks significantly enhances performance, as all formulations proposed by MCTS are executable by the solver- addressing the challenge of Syntuctic Validity.
Table 2: Comparison with baselines and ablation study. Values in parentheses denote the number of completion tokens. Targeted prompts split the task into successive prompts, mirroring the steps of MCTS that can found in Appendix M. SF: solver feedback, SC: syntax check.
Method
Rollout
Rollouts
12 Rollouts
GPT-4o (single prompt SF)
0% (2k)
0% (14k)
0% (38k)
CoT (single prompt w. SF)
0% (4k)
2.7% (20k)
2.7% (50k)
GPT-4o (targeted prompts w. SF)
5.5% (2k)
8.3% (16k)
8.3% (42k)
CoT (targeted prompts w. SF)
8.3% (6k)
11.0% (36k)
11.0% (85k)
MCTS (w/o. SF & SC)
11.0% (10k)
13.0% (43k)
16.0% (85k)
MCTS (w. SF, w/o. SC)
8.3% (10k)
36.1% (44k)
41.6% (86k)
GPT-4o (targeted prompts w. SF & SC)
44.4% (6k)
63.8% (30k)
72.0% (80k)
CoT (targeted prompts w. SF & SC)
52.7% (14k)
72.2% (74k)
75.2% (180k)
MCTS (w. SF & SC)
63.8% (1 (k)
77.7% (47k)
83.3% (96k)
The majority of remaining errors arise from Semantic Misunderstandinng, including issues with variable definitions, missing constraints, incorrect uniformizations, and misused operators.
Figure 4: Accuracy against number of rollouts. Our method improves formulations continuously during search.
Table 3: Error types in failed roll-outs.
Type of error
Occurrence
Nomber of spccesss
Parameter identification (m
5%
Variable definitions (m²)
26%
Missing constraints (m²)
24%
Incorrect events dynamics (m²²
12%
Incorrect uniformization (m²)
33%
Rollent index
Variable definition errors often occur when the LLM introduces unnecessary queues. In hospital scenarios, for example, beds represent the queue, but the LLM may incorrectly distinguish between patients in beds and those waiting, effectively modeling two queues instead of one. Missing constraints arise from implicit assumptions in the problem deseription-ee e.g., ensuring patient counts remain non non-negative. Solver feedback helps detect such issues by identifying unbounded state spaces. Incorrect uniformizations stem from deeper semantic misunderstandings. For instance, treatment probabilities differ when teams work in parallel vs. sequentially. These subtleties are primarily caught by the LLM signal. > Incorrect event dynamics another issue. While most events are identified, the LLM may omit actions in large action spaces invent spurious events (e.g., to model per-time-unit costs). These are typically detected via a combination of solver and LLM signals. Parameter Identification accounts for few errors and generally fails when the problem description includes irrelevant or distracting information that misleads the LLM. These cases are caught exclusively via the L.M signal.
8

---

5.2 COMPUTATIONAL TRACTABILITY AND INTERPRETABILITY
Structure Identification. When the operators identified by MCTS share a known propagated space, the second phase of our algorithm (Sec. 4.3) consistently recovers it, demonstrating that the Structural Inference challenge can be effectively addressed within our framework. Structural properties were identified in 74% of cases, also indicating strong performance on the second challenge: Expressiveness of the Formulation. Examples of successful structure extraction, along with discussion of their interpretabilityy. are provided in Appendix All failure cases fall into four categories: (i) Incorrect problem translation by MCTS, due to formalization errors discussed in Section 5.1, and not revisited here. (ii) Operator mislabeling, where the LLM correctly models state dynamics but misnames operators. This is the only remaining bottleneck for Structural Inference in our framework. (iii) Limited structural expressiveness, where the formulation is valid but does not expose the structure. This reveals that some correct formulations are less amenable structural analysis. We illustrate this in Example 1. (iv) Structural results beyond Koole's 's framework, where certain properties cannot be captured regardless of the operator graph. These cases expose fundamental limitations of the current. framework and suggest directions for future extensions. See Example 2.
Quantitative evaluation across the dataset shows that our method correctly identifies 74% of the structural properties, prior to solving the problem. Therefore, we can reduce the computational complexity by calling specialized solvers for large portion of the problems.
Takeaway:
Example 1 (Equivalent problem formulations with different structural expressiveness). Our hospital has I ward that manages types of patients with shared healthcare teams. There are N2 beds in total. The average arrival rates of the patients are >y/hour and xy/hour respectively. The teams take care of patients in parallel with an average rate that depends on their type py/hour and pz/hour respectively. When pulient arrive can refuse it, it occurs cost of cı for the first type of patients and 02 of the others.
We cannot obtain structural results from the straightforward problem formulation. How to find an equivalent combination of operators that allow us to obtain structural results?
Key challenges:
Straightforwant problem formulation. The natural events of this problem are controlled arrivals and departures the two types of patients, leading to the operator graph (found by MCTS):
n++ Teost {Tanir [Ta(1))V Tea(2) (VT), Tu (V (VG), (V,T) V.]
In this formulation, the probabilities in Tuuir depend on the state. For instance,
Pe(1) (fum))/(Ar + X2 + pNN) with max (21,
Due to state dependent probabilities in Tunir we cannot obtain any structural result. Equivalent problem formulation. We define new departure operator Drmatiies (T' = A1 +2 +
T (mmattia()) With the new departure operator, the probabilities in Tunif are independent of the state:
(xx ( T (>1 + A2) [[(= [((x- -1-F-
2uini
((x)
(A1 + x2)
1 PCA() = A,TT PDmaana = - (A1 A2) /r].
2
Structural results. From the equivalent problem formulation, we can identify the monotonicity property of the optimal policy.
Takeaway: Finding equivalent problem formulation with higher structural expressiveness is critical to identify structural results.
Example 2 (Problem with intractable structural results). Our hospital has wards arranged sequen- tially, with capacities of 5, 15, and 15 beds. respectively. Each ward has its own healthcare team and manages its own patients. On average, new patients arrive at rates of 3, 20, and 5 patients/day in the respective wards. The wards serve patients one time at rates of 10, 5, and 3 patients/day,

---

respectively. After being served in the first or second ward, cost of per transfer or keep them in the current ward. Patients served in the third ward leave the hospital. Additionally, patients can be moved back from ward 2 to ward I at rate of 3 patients/day or from ward to ward 2 at a rate of I patient/day, each transfer incurring a cost 2f Incoming patients can also be refused, incurring costs 5, 10, and 15 for wards 2, and 3, respectively.
transfer the next ward
Key challenges: The solution to the problem exhibits structural properties, but these cannot be anticipated regardless of the choice of operator graph.
Problem formulation. Our autoformulator correctly output the operator graph:
Va+1 = Toost {Tunit [TCc. Tca.)
T1m Vamnaa (cm,,,
Structural results. We can observe the structures (e.g,, monotone switching curve) of the optimal policy empirically (see Figure 6 in App. I). However, we have yet to find an equivalent problem formulation that would express these structural results.
The current method for identifying structural results fails on certain problems, as depends on limited theoretical results.
Takeaway:
DISCUSSION
We propose the first-ever autoformulator of event-based MDPs, a class of sequential decision decision-making problems encountered in various domains. Key to our framework is representation of the Bellman equation as an operator graph, which ensures interpretability and improves accuracy. By proving universal operator graph topology for event-based MDPs, significantly reduce the search space of autoformulation. We also propose a low-complexity algorithm to identify structural results based the operator graph. To construct the operator graph, we make significant modifications to MCTS by evaluating intermediate nodes for denser rewards and utilizing solver feedback for more objective evaluations. Experimental results demonstrate the effectiveness of our approach in accurately formulating problems and uncovering key structural insights. We also create the first dataset on autoformulating queueuing control problems, with a wide variety of labeled problems.
Autoformalising broader classes of operator graphs. A natural direction for future work is to extend autoformulation beyond event-based queueing models. The most immediate step is to consider broader families of MDPs that can be represented as graphs of operators, typically discrete-state MDPs with richer dynamics than those found in wentt-assdd systems, such as models with continuously available actions or deterministic events occurring at fixed frequencies. While the universal topology of Theorem 4. may no longer hold in these settings, the operator- graoor viewpoint remains applicable, component of our framework applies to any operator graph without
and the selucttral-ddettficaalte modification. The main challenge lies in designing a construction algorithm capable generating arbitrary operator-graph topologies.
Beyond analytic properties of the value function. This paper focuses on analytic structural properties, such convexity of the value function, that can be propagated through the operator graph. Many MDPs, however, do not admit such low-level analysis due to complex dynamics or irregular state spaces. We argue that the broader philosophy of designing autoformulators that are both computation- aware and interpretabilit-awaan analytical properties considered here. For example, hierarchical RL exploits the hierarchical structure inherent in certain tasks, illustrating how higher-level structure can guide algorithmic design even when low-level analytic results are unavailable. Incorporating such perspectives would enable autoformulation in domains with substantially more complex dynamics.
naturally extends to higher-level structural patterns beyond the
10

---

ACKNOWLEDGEMENTS
We thank the anonymous ICLR reviewers, members of the van der Schaar lab, and Andrew Rashbass for many insightful comments and suggestions. Nicolás Astorga thanks W.D. Armstrong Trust for their support. Yuanzhang Xiao was supported by the National Science Foundation under Grant NRT-AI 2244574.
REFERENCES
Daniel Adelman.
control of a closed logistics queueing network. Operations Research, 55(6):1022-1038, 2007.
Adekammi Adeyinka and Buliaminu Kareem. The application of queuing theory in solving automobile assembly line problem. International Journal of Engineering Research and, V7, 2018. doi:
(0.17577/EERTV71106662
AhmadiTeshnizi, Wenzhi Gao, and Madeleine Udell. Optimus: Scalable optimization modeling with (mi) 1p solvers and large language models. arXiv preprint arXiv:2402. 10/72, 2024.
Mohamed Amjath, Kerbache, Adel Elomri, and James Smith. Optimal buffers allocation in an inter-facility material transfer system modelled as closed qucucing network and analysed through a cotullaaionooiimmsatti approach. pp. 705-714, 714, 03 2023. doi: 10.46254/AN13.2020000
Nicolás Astorga, Tennison Liu, Yuanzhang Xiao, and Mihacla van der Schaar. Autoformulation of mathematical optimization models using LLMs. In Forty-second International Conference on Machine Learning (ICML), 2025.
René Bekker, GM Koole, Bo Friis Nielsen, and Thomas Bang Nielsen. Queues with waiting time dependent service. Queueing Systems, 68:61-78, 2011.
René Bekker, Ger Koole, and Dennis Roubos. Flexible bed allocations for hospital wards. Health Care Management Science, 20:453-466, 2017.
Marc G. Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning, 2017. URL https: // /ttp//axvv.//////////./////.at.a org/ wwwpabs////oooooooooo.o.o/e..aee /b7/1
Richard Bellman. On the theory of dynamic programming, Proceedings of the national Academy of Sciences, 3888):166-79, 1952.
Saif Benjaafar, M. ElHaf'si, and Tingting Huang. Optimal control of production-inventory system with both backorders and lost sales. Naval Research Logistics, 57(3):252-265, 2010a. doi:
10.1002/nav20339.
Saif Benjaafar, Jean-Philippe Gayon, and Seda Tepe. Optimal control of production-inventory system with customer impatience. Operations Research Letters, 38(4):267-272 2010b. ISSN 0167- 6377. doi: https://doi.org 0000 URL https: www. sciencedirect. com/ http///nne/aaattteee////////////
Jeroen Berrevoets, Ahmed Alaa, Zhaozhi Qian, James Jordon, Alexander ES Gimson, and Mihaela van der Schaar. Learning queueing policies for organ transplantation allocation using interpretable counterfactual survival analysis. In International Conference on Machine Learning, pp. 792-802.
PMLR, 2021.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume Athena scientific, 2012.
Dimitris Bertsimas and Georgios Margaritis. Robust and adaptive optimization under large language model lens, 2024. URL https: rxiv. org/ abs 2250 00568.
Dimitris Bertsimas, Nathan Kallus, Alexander M Weinstein, and Ying Daisy Zhuo. Personalized diabetes management using electronic medical records. Diabetes care, 40(2):210-217, 2017.
11

---

Sandjai Bhulai and Ger Koole. A queueing model for call blending in call centers. IEEE Transactions on Automatic Control, 48(8))14344 2003.
David Blackwell. Discounted dynamic programming. The Annals of Mathematical Statistics, 36(1):
February 1965.
Blai Bonet and Hector Geffner. Action selection for mdps: Anytime ao* vs. uct, 2019. URL
abs/ /tt/
attpss://axiia wwtp:/wwwwwwww//////////////////
Marko Boon, Guido Janssen, Johan van Leeuwaarden, and Rik Timmerman. Optimal capacity
allocation for heavy-trafin fixed-cycle rigft queues and intersections. Transportation Re-
search Part Methodological, 167:79-98, 2023. ISSN 0191-2615. doi: https://dbi.or//1..00166, trb.2022.1 11 010. URL https:://////.. /ww. sci enced rect. com/ sci ence/ eecee/erticeee////a/aa s01 91 522001911 91
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge university press, 2004.
Timothy CY Chan, Simon Y Huang, and Vahid Sarhangian. Dynamic control of service systems with returns: Application to design of postdischarge hospital readmission prevention programs. Operations Research, 73(4):2242-2263, 2025.
Thomas G. Dietterich. Hierarchical reinforcement learning with the maxq value function decomposi- tion, 1999, URL https:/:///axx org/ /tt/////////11/
Mark Ebben, Durk-Jouke van der Zee, and Matthieu van der Heijden. Dynamic one-way traffic control automated transportation systems. Transportation Research Part B: Methodological, 38 (5):441-558, 2004.
Benjamin Eysenbach. Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning, 2019. URL https: / org/ /11. 015.....555553.5553.. 05253.
David A. Freedman. The optimal reward operator in special classes of dynamic programming problems. The Annals of Probability, 2(5):942-949, 1974. URL http:://i /tt///wwwww www. jstor org/
stable/2959311. Accessed: 27 Nov. 2025.
Nakul Gopalan, Marie desJardins, Michael Littman, James MacGlashan, Sarah Squire, Stefanic Tellex, John Winder, and Lawson Wong. Planning with abstract markov decision processes. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 27, doi: 10. 1..16///caps..271111338.
pp. 480 488, 2017.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. CoRR, abs/l 106. 1822, 2011. URL htttp://arxvv/ wwtp:/iiwwrr/aaaaa /bb0/ 1822.
Gurobi Optimization. 2023 State Mathematical Optimization Report. com/ www.reeeeeeeeeeeeeeeeeeeeeeeeeee report state-tateeee of mat-mmatttiiccce zationiionoiiiiiioiiiiiioai 2023.
B. Hajek. Optimal control of two interacting service stations. IEEE Transactions Automatic Control, 29(6)4991-499 1984, doi: 10. 1091TA9AA,,,984, 1103577.
James E. Helm, Sheir AhmadBeygi. and Mark P. Van Oyen. Design and analysis of hospital admission control for operational effectiveness. Production and Operations Management, 20(3):359-374, 2011. doi: 10.1111/.1937-555622211
Yu-Pin Hsu, Navid Abedini, Natarajan Gautam, Alex Sprintson, and Srinivas Shakkottai. Opportuni- ties for network coding: To wait 1876-1889, 2015. doi: 10. 11111TTTT.2014234755555
wait. IEEE/ACM Transactions Networking, 23(6):
Chenyu Huang, Zhengyang Tang, Shixi Hu, Ruoqing Jiang, Xin Zheng, Dongdong Ge, Benyou Wang, and Zizhuo Wang. ORLM: A customizable framework in training large models for automated optimization modeling. Operations Research, May 2025.
12

---

Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Composi- tional reinforcement learning from logical specifications.
M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp- 10026-10039. Curran Associates, Inc., 2021. URL https: https::/proceee:: http:///ooccedeeeeeeee ngs neurips htcc//aper_fflesspppeeeeeee Pat.:/..8ppppppp......
Thomas Keller and Malte Helmert. Trial-based heuristic tree search for finite horizon mdps. Pro- ceedings of the International Conference on Automated Planning and Scheduling, 23:135-143, 06 2013. doi: 10. 1001f//sss v23te..ppp............... 223i1.13557.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), Machine Learning: ECML 2006, pp. 282-293, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg, ISBN 978-3-540-46056-5.
Ger Koole. A simple proof the optimality threshold policy in a two-server queueing sys- tem. Systems Control Letters, 26(5):301-30) 1995. ISSN 0167-6911. doi: https://doi.org/
10.101660167-0911000000111111111 URL https: http://wwww.cinnceeeeeeeeeeee wttpeeettcccccecooeoeeeeeeeeeeee science/
art.icleppii0016661111 0500000066771999910111111
Ger Koole. Structural results for the control of queueing systems using event-based dynamic pro- gramming, Queueing Systems, 30:323-339, 1998. URL https: api. semant icscholar.
org/CorpusID: :10M:sID::228444 17274845.
tions and Trends@ in Stochastic Systems, 1(1):1-76, 2007. Ger Koole. Monotonicity in Markov reward and decision chains: Theory and applications. Founda-
Ger Koole and Avishai Mandelbaum. Queueing models of call centers: An introduction. Annals of Operations Research, 113:41-553 59,11599227 2002.
Daniel Koutas, Daniel Hettegger, Kostas G. Papakonstantinou, and Daniel Straub. Convex is back: Solving belief MDPs with convexity deep reinforcement learning, 2025. URL https: //axxiv///xvvv./// org/ wttg/ab//////eooeeggggg//aeaees/ 2502. 09298.
Kuo Liang, Yuhang Lu, Jianming Mao, Shuyi Sun, Chunwei Yang, Congcong Zeng, Xiao Jin, Hanzhang Qin, Ruihao Zhu, and Chung-Piav Teo. LLM for Large-Scale Optimization Model nuto-Foomulatioo:: A Lightweight Few-Shot Learning Approach. http: /xx doi org/10/gg0 2139/sarnn 5329027. June 2025. Available at SSRN: https: ssw.s.ss.../////////////////// wwm aoaaabbtract= 5329027.
Steven Lippman. Applying a new device in the optimization of exponential queuing systems. Operations research, 23(4))687-710, 1975.
Hongliang Lu, Zhonglin Xie, Yaoyu Wu, Can Ren, Yuxuan Chen, and Zaiwen Wen. Optmath: scalable bidirectional data synthesis framework for optimization modeling, 2025. URL https: //laxxiv.orr..//.e abs /502 11102.
Pinhas Naor. The regulation of queue size by levying tolls. Econometrica: journal of the Econometric Society, pp. 15 15-24, 1969.
Martin L.. Puterman. Markov Decision Processes: Discrete Stochastie Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
Martin L Puterman. Markoy decision processes: Discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Rindranirina Ramamonjison, Timothy Yu, Raymond Li, Haley Li, Giuseppe Carenini, Bissan Ghad- dar, Shiqi He, Mahdi Mostajabdaveh, Amin Dehkordd.. Zirui Zhou, et al. NL4Opt competition: Formulating optimization problems based on their natural language descriptions. In NeurlPS 2022 Competition Track, pp. 189-203. PMLR, 2023.
Robert W Robinson. Counting labeled acyclic digraphs. New Directions in the Theory of Graphs, pp. 239-273, 1973.
13

---

Maike Schwarz and Hans Daduna. Queueing systems with inventory management with random lead times and with backordering. Mathematical Methods of Operations Research, 64(3):383-41) 2006.
Linn I Sennott. Stochastic dynamic programming and the control of queueing systems. John Wiley & Sons, 2009.
Richard F Serfozo.
equivalence between continuous and discrete time Markov decision processes. Operations Research, 27(3):616-620) 1979.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonogiou, Matthew Lai. Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 11401194111011144, 2018. doi: 10. 16/sccience. aar6404.
Shaler Stidham. Optimal control of admission to a queueing system. IEEE Transactions on Automatic Control, 30(8):70 1985.
Richard Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
A.C.C. van Wijk, IJB.... Adan, and G.J. Houtum. Optimal lateral transshipment policies for a two location inventory problem with multiple demand classes. European Journal of Opera- fional Research, 272(2):481-4) 1-9,, 2019. ISSN 0377-2217. doi: http:://doi.or//10.011//// 2018 3018.06.033. URL https: //wpw..//www//// sciencedirect com/ science//rtiice///eeeeeeee//e
Segev Wasserkrug, Leonard Boussioux, Dick den Hertog, Farzaneh Mirzazadeh, Birbil Ilker, Jannis Kurtz, and Donato Maragno. Enhancing decision making through the integration of large language models and operations research optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 39627) Apr. 2025, doi: 10.1609/aaii v39i27.3.....mm .5590. URL aaai www.e/aaaaa.a...a.a...e..e..eeee hitp//inxxxxx/////// php/ AAAI/ http///atceeeeeeeeeeeeeeeeeeeeee 35000
https:://ji
Ziyang Xiao, Dongxiang Zhang, Yangjun Wu, Lilin Xu, Yuan Jessica Wang, Xiongwei Han, Xiaojin Fu, Tao Zhong, Jia Zeng, Mingli Song, et al. Chain-of-Experts: When LLMs meet complex opera- tions research problems. In The Tweifth International Conference on Learning Representations. 2023.
Yu Xiong, Gendao Li, Yu Zhou, Kiran Fernandes, Richard Harrison, and Zhongkai Xiong. Dy- namic pricing models for used products in remanufacturing with lost-sales and uncertain qual- ity. International Journal of Production Economics, 147:678-688 688, 2014. ISSN 0925-5273, doi: http:///o..orr//0..01f....pppppp sci sccience/ase /ttce///rrtcclle/11///5555333333 Management.
URL https:/ hwt///www..t.. scie cieencedirect. com/ 98. Interdisciplinary Research in Operations
Insoon Yang. A convex optimization approach dynamic programming in continuous state and action spaces. Journal of Optimization Theory and Applications, 187(1)11331177, September 2020. ISSN 1573-2878. doi: 10.11077/119957-000-0177777 URL http::/da doi org/10. 100. 0007/s10977-02--00 747-11
Zhicheng Yang, Yiwei Wang, Yinya Huang, Zhijiang Guo, Wei Shi, Xiongwei Han, Liang Feng, Linqi Song, Xiaodan Liang, and Jing Tang. OptiBench meets ReSocratic; Measure and improve Ilms for optimization modeling, 2025. URL h httpa////axxvxw..//aaaee
org/ abaaabs/2400
Shuyu Yin, Qixuan Zhou, Fei Wen, and Tao Luo. A priori estimates for deep residual network in continuous-time reinforcement learning, 2024. URL https: 16899.
Huizhen Yu, A. Rupam Mahmood, and Richard S. Sutton. On generalized bellman equations and cemporal-differenee learning, 2018. URL htt.ttpss//aaxx...rrg/o// wwt.oorgg/abb///a/ooeeee/e abs/1704 04463.
Bowen Zhang, Pengcheng Luo, Genke Yang, Boon-Hee Soong, and Chau Yuen. OR-LLM-Apee Automating modeling and solving of operations research optimization problems with reasoning LLM, 2025a. URL https: //wrx//xvvvv org/ als 2203. 10009.
14

---

Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World model as graph: Learning latent landmarks for planning, 2021. URL https: /aaaaii///xv.v.aa//aa/aaaaaarai arxiv. org/ otg/abs/////oooooooto...stt..tbp 0bs/2001.12499
Yisong Zhang, Ran Cheng, Guoxing Yi, and Kay Chen Tan. A systematic survey on large language models for evolutionary optimization: From modeling solving. arXiv preprint arXiv:2509.00 08269,
2025b.
Ziyong Zhang. Tao Dong, Jie Yin, Yue Xu, Zongyi Luo. Hao Jiang, and Jing Wu. A particle swarm optimization- queue scheduling and optimization mechanism for large-scale low- earth-orbit satellite communication networks. Sensors, 25(4), 2025c. ISSN 1424-8220. doi: 10.3390/S25041669 URL http:::tp////
mdpi. com 1424
Bo Zhou, Ying Cui, and Meixia Tao. Stochastic throughput optimization for two-hop systems with finite relay buffers. IEEE Transactions Signal Processing, 63(20):554--5560, October 2015. /ttp://ddddoo....//010101.99 wtt.:/ooi..ogg//.../ooo /
ISSN 1941-0476. doi: 10. 202514522 URL http: /ttp://xxxooooo dx TSP 2015. 2452225.
Chenyu Zhou, Jingyuan Yang, Linwei Xin, Yitian Chen, Ziyan He, and Dongdong Ge. Auto- formulating dynamic programming problems with large language models. arXiv preprint arXiv:2507.11737, 2025.
Weifen Zhuang and Michael Z.F. Li. A new method proving structural properties for certain class of stochastic dynamic control problems. Operations Research Letters, 38(5):622-467, 2010. ISSN 0167-6377. doi: /tt.c//ce////ttteeea//////////1.
URL https: /www.
sciencedirect. com/
Eren Başar Çil, Fikri Karaesmen, and E. Lerzan Örmeci. Dynamic pricing and scheduling in multi-class single-server queueing system. Queueing Systems, 67(4):305 2011.
ISSN 1572-9443. doi: 10. 10.1007/111134.011992111 URL http::://......r//00.0000 211134-011-9214
15

---

CONTENTS
Autoformulating Optimization Problems versus MDPs
17
Event-Based MDPs in Various Applications
18
Extended related work
19
C.1 Operator-based formulations of Bellman equations
19
C.2 DAG-based structures for the study of MDPs
19
D Detailed Derivations of Results in Section
21
D.I Key Results Continuous- Time and Discrete-Time MDPs
21
D.2 Detailed Walk-Through of An Example: Parallel M/M/1 Queues with Controlled Arrivals and Shared Beds
23
E Details on Operator Theory
24
E.1
Illustrative Example
24
E.2 Operators (Used in This Work)
26
E,3 Set of Special Functions
27
E,4 Propagation Results
28
Proof of Theorem 4.1
29
G Algorithms for Identifying Structural Results (Section 4.3)
31
G.1 Why Challenging to Identify Structural Results?
G.2 Algorithm Description in Pseudo-Code.
................................
33
G.3 Proof of Theorem 4.2
34
H Why Theorem 4.1 Not Trivial? Illustrative Examples
40
H.l The M/M// Example With an Altemative Operator Graph Topology
40
H.2 An Example of Non-Eyent-Based MDP With Different Operator Graph Topology
41
I Detailed Descriptions of Examples in Section 5
42
J Details on the method
47
J.1 LLM enhanced MCTS
47
K Desiderata of Autoformulation
49
K.1 Desiderata and Corresponding Challenges
49
K.2 Typical Errors with Respect to These Challenges
50
Dataset
M Prompts
53
16

---

A AUTOFORMULATING OPTIMIZATION PROBLEMS VERSUS MDPS
Here is an example natural-language description of two parallel M/M/1 queues with controlled arrival and uncontrolled departure. It adapted from problems in hospital admission control (Bekker et al., 2017; Naor, 1969). Some representative formulation challenges are annotated.
We consider hospital with two wards: one for Critical patients and one for General patients, each staffed by a dedicated team. Both wards share Ng beds. On average, X Critical and AG General patients arrive per day [State-dependens action sets: admission decision only at an arrival, readmission decision only at a departure.). Treatment rates are PC and PG patients per day for Critical and General wards, respectively, with each team serving one patient at a time ['Transition probabilities need to be inferred from the arrival and departure rates.]. Treated patients leave the system, releasing their beds. Upon arrival, a patient may be admitted if a bed is available; otherwise, the patient is rejected, incurring a penalty cost ce (Critical) ca (General). Each admitted patient generates a holding cost ph per unit time. The objective is to minimize the long-run average operating cost. with discount factor a. [Throughout the description, the implicit constraint of queue length being nonnegative was not mentioned.]
Computation challenges. The optimal policy maps queue lengths admission decisions: Oca, v {0. 1} for Critical patients and Aga, E {0, } for General patients. Standard dynamic programming enumerates all queue lengths to determine the optimal decisions, repeating this process until con- vergence. However, if the optimal admission policy can be shown to follow a threshold structure, the search reduces to identifying the threshold values. Likewise, if the value function is convex, specialized dynamic programming solvers converges faster. Thus, uncovering structural properties of optimal policies and value functions before solving significantly reduces computational complexity.
Interpretability challenges. It is also desirable if the policy is interpretable: "admit only when the queue length is smaller than this threshold".
Next, we inspect hospital logistics problem in the NL40pt dataset (Ramamonjison et al., 2023).
A hospital can transport their patients either using a type ambulance or hospital van. The hospital needs to transport 320 patients every day. A type Il ambulance is mounted on truck-style chassis and can move 20 patients every shift and costs the hospital (including gas and salary) $820. A hospital van can move 1.5 patients and costs the hospital $550 every shift. The hospital can have at most 60% of shifts be hospital vans due to union limitations of the type II ambulance drivers. How many of shift using each type of vehicle should be scheduled to minimize the total cost to the hospital?
In terms of formulation challenges, there is no notion of states or transition probabilities, and the decision variables two scalars. In terms of computation challenges, this is a linear program that can scale with tens of thousands of decision variables. In terms of interpretability challenges, the optimal decisions are the numbers of vehicles of cach type, which is easy to understand.
Table 4 provides a side-by-side comparison of optimization and MDP autoformulation.
Table 4: Autoformulating mathematical optimization versus MDPs
Challenge
Aspect
Optimization
MDP
Need to derive states/uctions from context
Formulation
Variables
Often explicitly defined
Formulation
Constraints
Ofien explicitly defined Usually non-existent
Sometimes implicit and omitted
Formulation
Stochustic dynamics
Important to model
Computation
Scalahility
Scales well for convex problems
"Curse of dimensionality"
Easy inspect variable, objectives, constraints
digh-diimesional components (e.g., transition probabilities) hard to inspect
Interpretability
Problem formulation
Values of decision variables directly understandable
Interpretability
Solution
Policy mapping hard to interpret
17

---

B EVENT-BASED MDPS IN VARIOUS APPLICATIONS
Table 5 provides a non-exhaustive list of event-based MDPs a variety applications domains. We focus on problems that can be modeled as control of queueing systems.
Table 5: Event-based MDPs diverse application domains.
Domain
Problem
Representative Works
diabctes management
Bertsimas et al. (2017)
Healthcare
organ transplant
Berrevoets al. (2021)
hospitul admission control
Bekker ct al. (2017)
inventory management, logisties
Schwarz & Daduna (2006); Adelman (2007)
Business
assembly lines freight dispatching
Adeyinka & Kareem (2018)
Schwarz Daduna (2006); Amjath al. (2023)
Koole & Mandelbaum (2002); Bhulai & Koole (2003);
Telecommunications
call center management
Bekker et al. (2011); Zhang et (2025c)
Transportation
interscction management traffic control
Stidham (1985); Ebben et al. (2004)
Boon et (2023)
18

---

C EXTENDED RELATED WORK
In Section 2, we mostly discussed work on autoformulation. We now provide additional background on two technical dimensions central to our approach: operator-based formulations of Bellman equations and DAG-based structures for the study of MDPs. Our goal to situate our operator graph perspective within these broader lines of research.
C.I OPERATOR-BASED FORMULATIONS OF BELLMAN EQUATIONS
substantial body of work has examined Bellman equations through the lens of operators acting on value functions. Classical dynamic programming texts already present the Bellman update as contraction operator Freedman (1974); Blackwell (1965). However, the formal meaning of "pperator" varies significantly across the literature and is used in conceptually different ways.
The operators employed in the present work are representative of one such interpretation. Koole introduced a collection of elementary or event-based operators Koole (1998; 2007) from which the Bellman update can be constructed by composition. These atomic operators are not Bellman updates themselves; rather, they model primitive system events (arrivals, departures, etc.). The key insight is that one can establish structural or monotonicity properties at the level of these elementary operators, and then deduce analogous results for broad classes of Bellman equations without repeating the full analysis. This philosophy has been adopted in subsequent work, which introduces additional operators establish monotonicity or dominance properties in diverse stochastic control problems Helm et al. (201 I); Xiong et al. (2014); van Wijk et al. (2019); Benjaafar et al. (2010b;a). Once such properties are proved the operator level, they can be reused whenever those operators appear as components of a Bellman equation.
Other definitions of operators focus on variants or generalizations of the canonical Bellman update. One example is the generalized Bellman equation Yu et al. (2018), which defines an operator not only on value functions but on the parameter space of the learning algorithm itself (here, temporal- difference learning). Another example is the distributional Bellman equation Bellemare et al. (2017), where the operator acts on the distribution of returns rather than the value function (i.e., the expected return). Finally, in parts of the literature the term operator is used more informally for individual pieces of the Bellman update, without the systematic decomposition seen in Koole's 's framework. For instance, in one of Bellman's original formulations Bellman (1952) the operator is essentially the full update except for the max or min optimization step, whereas in Yin et al. (2024) is essentially the opposite, with the operator reduced to that optimization step alone.
C.2 DAG-BASED STRUCTURES FOR THE STUDY OF MDPs
One classical use of DAGs in MDPs that is closely related to our operator DAGs is the AND/OR search graph, where nodes are time-indexed states and edges represent possible transitions, often weighted by their probabilities Bonet & Geffner (2019). In DP or RL this structure is typically implicit, as it is algebraically collapsed into the Bellman equation. In contrast, several cegorithnssesppecin for finite-horizon problems problems-opprrtte directly on this graph, such as THTS Keller & Helmert (2013) and the MCTS algorithm used this paper. Our operator DAG can be viewed as intermediate representation between the full AND/OR search graph and its complete collapse into the Bellman equation. It factorizes the large AND/OR graph using the analytical structure of the Bellman update, retaining enough of the original graph topology to decompose the Bellman update into more atomic analytical transformations, the operators.
Another use of DAGs in MDPs, less related but potentially confusable with ours, arises in hicrarchical reinforcement learning (HRL), where a decision problem is decomposed into higher-level tasks and lower-level subtasks. Each node in this hierarchy is itself sequential decision problem, and the structure reshapes both the control problem and the learning dynamics of the optimal policy Dietterich (1999); Gopalan et al. (2017). The DAGS we consider in this paper are fundamentally different. Our operator DAG is an analytic hierarchy that specifies the order in which operations are applied to the value function within a single Bellman update. Although some nodes may involve choice, they correspond to a one-shot evaluation of the policy, not to sub-MDPs with their own temporal evolution or repeated policy execution. HRL thus defines hierarchy of behaviors unfolding over
19

---

many transitions, whereas operator DAG defines a hierarchy of operations applied within one transition.
Beyond these settings, DAGs appear in many other parts of the MDP and RL literature, reflecting the general versatility of graph-based abstractions. These uses, however, are conceptually quite different from our operator DAGs. For example, factored MDPs represent the transition model as a dynamic Bayesian network Guestrin et al. (2011), exploiting canditional-indeeeddeeee structure obtain compact transition models and more efficient computations. Other work employs graphs as high-level planning abstractions Eysenbach et al. (2019); Zhang et al. (2021), for instance by performing Dijkstra-style shortest-patee -ath computations on an abstract task graph while delegating low-level control to an RL policy, as in Jothimurugan et al. (2021).
20

---

D DETAILED DERIVATIONS OF RESULTS IN SECTION 3
In this section, we provide detailed proofs and derivations of the results in Sec. 3. In the first part, we provide some key results continuous-time and discrete-time MDPs make the paper self- contained. In the second part, we go through the entire process of solving the example of parallel M/M/1 queues with controlled arrivals and shared beds.
D.1 KEY RESULTS ON CONTINUOUS- TIME AND DISCRETE- TIMEE MDPs
D.1.1 BELLMAN EQUATIONS FOR CONTINUOUS- TIME MDPs
To solve for the minimum cost, we define (s) as the minimum a-discounted cost during the last n state transitions when starting from state 8. Defining (s, = 0, we have the following Bellman equation (Lippman. 1975; Serfozo, 1979)
a(s,)) (s) min ((ssa)+ + \(s + Eves P(s'|s, ())a(1))) aEA,
(12)
Mssa) where M(sa)-a Erwexp|A(ssaa) [e ar] is the expected discounting of the next state value Vn,a((s)) (s').
The Bellman equation in (12) standard due to the (s, ddeeended discounting A(s,a)+a We can remedy this issue by studying the discrete-time embedded MDP (Serfozo, 1979; Sennott, 2009; Lippman, 1975).
M(sa)
We first derive the Bellman equation of the continuous-time MDP in equation 12.
instantaneous cost
flowing cost
value from state s'
g 0, 8') So at p(s, a, s') dt
(sn
transitions go
State
State
transition time T
State transition dynamies and costs during sample path of a continuous-time MDP.
The figure above shows the state dynamics and the costs incurred during the transition from state s to state s'. The expected total cost starting from state s consists of two parts: the expected cost accumulated until the transition and the expected total cost starting from the next state. The cost during the transition can be calculated as
0(), + [e a(s,p(s,,,
ō(s, a) = st 81
(13)
st. a(s,a,s') + +ps(s,,s))) lr
c
aat dt
(14)
-07
() o' g(8,0,8)) + p(s, (s,,,,8).
(15)
oar
BywP(lba) g(s,a,8)) p(s,a, 8') Erwexp(A(aa))
(16)
BynP((aa) g(s,a,s)) + p().a.s)) aas
(17)
Σ s'ss + 6') P(5(ss,0) SeS
(18)
A(s,a) +a
Note that without discounting (a = 0), the term p(aaas)) is the cost rate p(s, a, 8') times the expected A(.a)
transition time A[sa]] With discounting, A(sa)+a E (x So e -at dt can be interpreted as the expectation of "discounted" transition time.
21

---

The second part is the cost starting from the next state s', discounted based on the transition time
(xx (e [e-ar (s)a(s') BewExx([(saa)) [e-ar] (s.((')))
M(s,a) ((s.a) (s'). (19)
Note that this is the cost if the next state is s'. So we need to take the expectation over s' to get the expected cost starting from state and action a:
a(s,a) a) ((s,a) + X(s,a) + e'ES
(20)
Therefore, starting from state 8, the minimum a-discounted cost during the last n + transitions is
( = -min (s,a(s,a), ae.A,
(21)
which is the Bellman equation equation 12.
D.1.2 EQUIVALENT DISCRETE-TIME MDPS AND VARIOUS PERFORMANCE CRITERIA
In Sec. 3, we introduced several notions of value functions for continuous-tin MDPs:
Va.ni discounted cost of a continuous-time MDP with discount rate a and under policy m
Va: minimum discounted cost of continuous-time MDP with discount rate
V minimum a-discounted cost of continuous-time MDP during the last transitions;
J=: average cost continuous- MDP under policy x;
J: minimum average cost of continuous-tine MDP.
The counterparts in discrete-time MDPs are Vy,an Vy, Vn,res Jæy J, where we use regular letters and the discount factor y in the subscript.
The relationship between these value functions are
V
n,a
g
continuous-time:
V.,
inf
V.
j jinf
J
$
$
(22)
discrete-time:
Veyar
inf
Vy
lim,- 1 (1-7)V,
J infe J
Va
In equation 22, the equivalence "**" between the continuous-time MDP and its discrete-time em- bedded MDP defined equation 23 is due the result in Serfozo (1979), which we restated here.
Theorem D.1 (Theorem in Serfozo (1979)), Lei (S, A,, a) be a continuous-ime MDP with bounded state Iransition rates (i.e., sup,,a X(s,a) A). Let (S,As, e, P, P, be the discrete-time MDP with discount factor A40. and state transition probabilities and the cost function defined
A
P(8'|s,a)= = M(s a) a)) a)/,
A(s, a) + if fs and c(s,a)=
-(s, (23)
if' =8
A A+a
For any stationary policy n, we have V, = V. and Jr = Jz/A.
22

---

This transformation, often referred the uniformization technique, allows us to reduce continuous- time MDP with exponential transition times into an equivalent discrete-time MDP with adjusted transition probabilities and costs.
The relationship "->" between other value functions are well-cstablished results. The minimum dis- oo is due to (Sennott, 2009, Proposition 4.3.1), and the minimum average cost [() = inf, J (s) as the limit of (1 - 7) (s) when Y - 1 is due to (Sennott, 2009, Proposition 6.2.3). Since these are not the focus of our paper, we omit the formal statements of these results and the conditions under which they hold (usually satisfied in practice).
counted cost (s) as the limit of (s) when
As can see from equation 22, solving any value function be done by solving the value function Vn,r for the discrete-time n-period discounted cost case. Suppose, for example, that we want to solve the value function J for the continuous-tine average cost case. Due to the equivalence established by uniformization, we can instead solve for the discrete- average cost J, which is obtained by solving V under sufficiently large discount factor 7 and then taking the limit -> XX.
D.2 DETAILED WALK-THROUGH AN EXAMPLE: PARALLEL M/M/1 QUEUES WITH CONTROLLED ARRIVALS AND SHARED BEDS
D.2.1 UNIFORMIZATION OF THE CONTINUOUS- TIME MDP
We illustrate the model components using a simple example of two parallel M/M/1 queues with controlled arrivals (CA) and uncontrolled departures (D). This constitutes generalization of the problem introduced in Fig. 10.
We consider hospital with two wards: one for Critical patients and one for General patients, each staffed by a dedicated team. Both wards share NB beds. On average, A Critical and XG General patients arrive per day. Treatment rates are PC and PG patients per day for Critical and General wards, respectively, with each team serving one patient at time. Treated patients leave the system, releasing their beds. Upon arrival, a patient may be admitted if a bed is available; otherwise, the patient is rejected, incurring a penalty cost cc (Critical) or cG (General). Each admitted patient generates a holding cost Ph per unit time. The objective is to minimize the long- run average operating cost, with discount factor a.
Let = (IC) denote the current queue lengths and let e E (Ac, (A Dc, DG) denote the most recent event: arrival of a Critical patient, arrival of a General patient, departure of a Critical patient, or departure of General patient. We define the post-event state as (I,ee. The action set empty for departure events, but for arrivals the decision is to accept (1) or reject (0). Hence
A(a,e) = (0,1). e (AC
if + IG < NR,
and
A(a,e) {0). if rc + DG 2 NB.
Interarrival and service times are naturally modeled as exponential (Poisson processes), even not explicitly stated. Thus, the state transition time is exponentially distributed with rate
== >c + XG + PC + PG-
When the system is empty, "departure" events may still occur but do not alter the state (see 27, 28),
allowing the same transition formulation to apply.
The state transition probability decomposes as
P [[ (z, a] P2 (I, (),,e),a] Pa (e')a,)),
(24)
with transition probabilities for the queue lengths (with the notation y max(y, 0)):
Pa(a' (1, Ac)
(25)
[a (a)
= 1x
(26)
Palz' (x, (x))
= 1x6=(e0-11tt
(27)
Pa (x, (x,
1
(28)
23

---

The event probabilities are (this discretization step corresponds to uniformization, as introduced in Theorem D.I):
Ao Pa 12) X
Pa xz)= A X P.(Dold)) PC
Po (
PG
(29)
The cost structure consists of one-time rejection penalties cc, og and holding cost ps. per patient unit time. The cost is given by
Ph (&c + DG +1]
c Acya),
1] - Cc/G +
(30)
A+a
Ph s + &G)
(z, Ac/oo) 0 CC/G +
(31)
A+
[x)) Ph (max [ 1, 0) + IG)
(32)
À +
[((x, Da)l Ph. (max [ - 1, 0) + xc))
(33)
À + a
D.2.2 DERIVATION OF THE BELLMAN EQUATION
Using the discrete-time embedded MDP of the original continuous tiem problem we can write the following optimal Bellman equations (we recall that x = (Ic, IG)).
V (I, Ac)
min (V, + 1, co (x)), -min (Vo + 1), ca + (x))
(34)
Vi (I, Ag)
(35)
Vi+ (Ir, Dc)
= (
(36)
Vi (Ir, DG)
=V, (IG - 1)+)).
(37)
where (x) is the value function defined on the queuing state x:
V (x) A Ph (#c + xG)
A+a
Ac Va Vi (c)
AG (I,
?
HC (z, + V Vi (z) A
+
(38)
It is worth noting the similarity between the post-event value functions V (z, e) and the Q-functions commonly used in reinforcement learning, which represent post-action value functions.
E DETAILS ON OPERATOR THEORY
We provide an overview of the operator theory constructing the operator-based Bellman equations. We focus the results used in this paper. We refer the readers Koole (2007) for comprehensive discussion of this topic.
The central idea is decompose the Bellman equation of an MDP into sequence of operators Koole (2007). Each operator intuitively captures distinct type of dynamic that arises as time progresses, such randomness, decision decision-making making, state transitions, or incurred costs.
E AN ILLUSTRATIVE EXAMPLE
We recall the example presented in Appendix D.2:
24

---

We consider hospital with two wards: one for Critical patients and one for General patients, each staffed by dedicated team. Both wards share Ng beds. On average, XC Critical and Ag General patients arrive per day. Treatment rates Pa and PG patients per day for Critical and General wards, respectively, with each team serving one patient at time. Treated patients leave the system, releasing their beds. Upon arrival, a patient may be admitted if bed is available; otherwise, the patient is rejected, incurring a penalty cost cc (Critical) or CG (General). Each admitted patient generates a holding cost ph per unit time. The objective is to minimize the long-run average operating cost, with discount factor a.
This model involves several distinct dynamics:
Randomness: Patient arrivals and departures occur at rates AC/D and JC/DD. respectively,
Decision-making The system must decide whether to accept or reject a patient upon arrival.
State transitions: The queue length may increase, stay the same, or decrease depending on the decisions made and event type.
Costs: Rejection incurs a penalty, and holding patients generates a time-dependent cost.
These elements are all incorporated into the full Bellman equation. In operator theoery, we view the Bellman equation as combination of operators, each capturing a specific aspect of the dynamics.
For the example above, the Bellman equation reads:
V. (x) A Ph
(#c + xG)
A t
Ac Vn Ac)
AG (z,
+ ?
HC +
Vo (c) Dc) + nG (z, D6)
(39)
with
Vit (I, Ac)
min (V, 1, co (z)) -min (Vi + 1), ca + (z))
(40)
Vit+ (I, Ag)
(41)
Vi+z (2, Dc)
= -V2o [a));
(42)
Vi (1 DG) (VT, 1)+
(43)
We identify and separate the stochastic dynamics into the uniformization operator Tunis, the decision-making upon arrival with its corresponding impact and cost into Tex and the patient departure mechanism into To. The holding cost and discount factor are captured by the cost operator Teost. These are formally defined as follows:
Tea,c (x)] Vn+i
(x,Ac), Ac), Tea. [+)( Vn+ 12r Ag),
(44)
To, [v)] = (a, Dc),
To,6 [V: = Vn+1 (zt Dc).
(45)
Tenis (U)(x), U2(),, (x())] = Ag Ui( + de U2(x)
+ # Uz(2) + d Ua(x).
(46)
Teost [U(x)] Ph. (xc + za) a) + U(z).
(47)
Then the Bellman equation equation 39 can be rewritten V going through an operator graph to get V i (x+ Toost (Tunir (Tea, e [V, (x) Tox, [V, Tb, (z)) (v))))
(48)
The motivation for introducing operators as a tool for autoformalism is twofold. First, it offers structured framework wherein identifying the Bellman equation reduces to two subtasks: (i)
25

---

identifying the relevant operators, and (ii) specifying the operator graph. In this work, focus a class of problems for which the second task the structure the graph- is solved advance (Theorem 4.1). Thus, the only remaining task is to identify the appropriate operators in this graph. Second, the operator- hased framework enables the automatic derivation of structural properties the value function, by analyzing the propagation behavior of the operators within the graph.
For instance, consider the space of convex value functions Cone, defined by the property that (x + 1) S Vz + Vit(z (a + 2) for all x 2 We can show that under any parameter values- provided the refusal cost is positive and the holding cost pn (r)) is convex-the previously defined operators preserve convexity:
V E Cone = (V*),") (Vn""))) Tees: E Cone.
Consequently, we have the propagation result:
V E Conv
V Toost { Tanir (Tea. Ten,clVis)
Ten, s[ To).
Conv.
(49)
From this, follows that V E Conw, which in turn implies that the optimal policy it is threshold. Specifically, there exist two thresholds TT, and NT, such that an arriving Critical (resp. General) patient is accepted if and only if æe + IG S TrC.C. (resp. Nr,G)
This approach is generalizable: whenever the Bellman equation be decomposed into known operators for which we have propagation results, structural properties of the value function and hence of the optimal policy-can be deduced, provided these operators share common invariant function space. In the following sections, we list the operators considered and detail their respective propagation properties.
F.2 OPERATORS (USED IN THIS WORK)
We introduce the operators used in this work; additional operators can be found in Koole (2007). In the following, & denotes the canonical basis of &R where & represents the number of queues.
Teost [V'(x)] - +())+>V'(()))
-umit (V) VJ()) Σ p())V(()) with Σ p(J) j=1
j=1
-Teass [V*(z)] min ((V (x) + c V (x + c2)
-Tor [V*(x)] ('(( ((((==;;)t)
-Toa [V*(x)] ((z;)) 5;) +)) + (1- (1-
- Teo [V* (z)) = min[(e) +V
V* t]} >
c + V(x) otherwise.
-TDI [V)( = V (" ( + +e,) if > 0
V*(x) otherwise.
Tem [V'()]] = minfcr + (z)x) + V* - = if >0
V*(x) otherwise.
The operator Trost represents the cost operator, while Tumis corresponds to the uniformization operator.
The operator T represents controlled arrivals queue whereas TDI models standard departure. The operator TD, represents departures a multi-server queue and is specifically used Example 1. Controlled departures from queue are denoted by TeD.i-
To model tandem queues, we use the operator TTDI, which describes the transition of a customer from queue to queue j. Similarly, Tem represents controlled tandem departures.
26

---

E.3 SET OF SPECIAL FUNCTIONS
We introduce the set of functions used in the propagation results.
- -Ve(())
V(x) S V(x+e))
for all x e 1 iiisk
-I= -I) (..))n...1)) -((mm,
-Ve (V)) if
V(x + 6+11 & V(x+e)
for all x and 1 i < k
-U UI(1) n UI(k 1), 1),
- E Cr(( if
2V + 64) S V(x) + V(x + 26:)
for all x and i k,
-Cr Cx(()
Cr(()),
- - E Super(i, if
V(x es) + V(x++e) (V) Super=
for all x and 1 i
= nugiccss
V E Sub((i,) if
V(x) + [
for all æ and 1 i
Sub = [
V E (i. if
V + e;) + +() (V(+t) v(x+
for all x and 1 i, < i
SuperC SuperC Nigisski [uspessskkuyySSeerC(.i...
V E SubC(ii,) if
V + e;) + +e)
2e, +eg)
for all x and 1 i < ki
SubC = -iglsshiy SubC((i,))
V E MM(i, if
V(z) V(x d + dj) V( +))+4)+V++ + V(x + dj)
for all æ and 1 i S k such that x + d,, x + d, E N
with d1 c, - + ck+11, 2....,k k
and dç Ekk
MM (
Further explanations for each be found in Koole (2007). The following inequalities hold for these sets:
Super(i, n SuperC(i..) c Cur(i) Sub(i, j) n SubC(i, c Cw(() MM C Super SuperC c Super Ca
We construct a non- trivial inclusion basis that satisfies the rules introduced in Appendix G.3 and corresponds the given inequalities. We define B the union of all the spaces introduced above,
27

---

excluding superspaces such SuperC. Instead, retain only the sets of the form SuperC(i..) j) to prevent non con-trivial equalities that cannot be derived solely through intersection or augmentation.
Next, we decompose inequalities to ensure they follow the standard form A {i}. For example, an inclusion such as
MM C Super n SuperC
(50)
rewritten as multiple separate inequalities, such as MM C Super(i. j) for specific indices i. The resulting set of inequalities constitutes the non-trivial inclusion basis, which satisfies the necessary constraints.
E.4 PROPAGATION RESULTS
We present some of the propagation results for the operators used in this work:
TeAo:: : I UI UI UI, Cr(i) (um)SSprr(.)) - Super(i..) Sub + Sub, Super(i,j) 0 SuperC((, +
- SuperC(i,
Sub(i, ( n - SubC Sub(i, (() SubC(())) SubC(J, i), MM - MM for 1; -TD( 11 1, Un + UI i m, 1(i) (Cx(i) Cx(i), Cx(j) + Cx(i)
for ii Super + Super, Sub + Sub, SuperC(j, k) + SuperC(j. k) (i #1),
T(i) n SuperC((i, - SuperC(i, (),,), Ca(j) n Super - SuperC(j. (f 1),
SubC(i, k) + SubC(j, k) (j. + i), I(2) n SubC(i.j) + SubC(i.)) # i),
Cr(() SubC(j, SubC(j. i), u MM + MM for m; TTdII I + T, UI UI for < m, U MM + for i < m, UI n C* O Super -> Cr for m, u Ca n Super + Super for m;
For the rest of the operators, again refer Koole (2007).
28

---

F PROOF OF THEOREM 4.
independent
dependent of action: [( c),a]
<(z)
Va
transitions go
Pale (z.c),a)
(a(aa)))
event
Pa(eslæ)
event j
State transition dynamics and costs during sample path of the discrete-time emhedded MDPP
For any MDP (8, As, c, P,n), the standard Bellman equation for the value function V*+1(s) on the full state s can written as:
a(s,a) +y E 1..0)/((61)
Va (s) min aEA,
(51)
s'ES
Separating the controllable state and the event MDPs equation 5 we have
(x, e) and using the definition of event-based
(2+1 c) min aEA(s,))
c((x, ((,,)),a]++ +7
Σ
P((a a] V2
(52)
(ar)
min a
cl(x, a7
+7 Σ
Ps [zd (z, al Po (o(e''e))
(53)
(ar,et)
min aEA(a.e)
e((x,e),, Σ
a) Σ Po(e(xx)) V (a(
(54)
Av;(x²)
[((z,e),a|+ Px a] vV66
min at aEAiz..)
(55)
where we define the value function (x) on the controllable state
(+(() = 7 Σ Pole Va,
(56)
(xx()) is the value of the state immediately after an action is taken but before the waiting time until the next event. Because there temporal gap between V and V,, the discount factor must be applied at this stage to account for that delay.
We can always decompose the cost c((2, e), a] into two parts: (1) a cost c(x) that depends only on the controllable state (e.g., the holding cost in the M/M/1 example), and (2) cost c((2,, e), al that depends on the full state-action pair, namely
c((x, e), a] = c(x) + (((xxe)).0
Note that if the component c(x) does not exist, we can always set c(x) = 0 and ब( e), a] = <((x, a).
29

---

Then the Bellman equation in equation 55 can be rewritten as
(z, = c(x) + min oEA(u)))
e((r,)),a] + Px a) [V)
(57)
and the value function Vn+ (I) can be rewritten
Vu+i(#) (a))
= y Σ Pa(el2)Vian (n)z((()))
(58)
}
Σ Pa(elz) c(x)+ + min
((()) aEA(sr.)
c((x,c),a]+
r
}
= ye(z) ty Σ po(e)z) (x)
min rEA(a.))
e((x,)),a)+ + (2,,) d) V3'(
Therefore, go from Vi (z) to Vi++ (z) through the following three operators:
Te [V) Vn+ eÿ) m {dl(z, e), + En (1111(2 a] (22(2
Tunis (U1()).... Ue(x)]==[]-]))) = =E P(ey (2) Uz(x)
Teoat
- [ +- Uxx)
The operator-based Bellman equation on the value function V (2) can written as
V * (x) Teost {Tenif (Te, (z) ...., (x))).
(59)
30

---

G ALGORITHMM FOR IDENTIFYING STRUCTURAL RESULTS (SECTION 4.3)
In this section, we provide a detailed discussion of the algorithm used to identify structural properties of the solution from the operator graph ( SSection 4.3).
G.1 WHY IT Is CHALLENGING TO IDENTIFY STRUCTURAL RESULTS?
Given the operator graph, our goal is to deduce structural properties of the optimal policy and the value function V (z). Consider the example from Section 3, further detailed in Appendix E. In that case, one can show that (x) is convex, which implies that the optimal acceptance policy is threshold. This follows from the fact that convexity propagated through each operator in the graph. Consequently, convexity is preserved by the entire Bellman equation. Since convexity is a fixed property under this composition of operators, must also be a property of the fixed point of the Bellman eguation-namely, the optimal value function.
More generally, consider problem where the operator graph consists of operators (T1:... Tk). For each operator, we given list of functional spaces (or properties) that it propagates. Our objective to identify a common functional space propagated by all operators; the optimal value function must then belong this space.
In practice, we do not have explicit lists of all propagated spaces, but only a set of primitive spaces from which additional spaces be generated. New propagated spaces may be obtained by applying the two fundamental set operations, intersection and union. Indeed, if T propagates A and B, then propagates both A n B and AU B.
In principle, one could therefore consider the closure of the initial families under both intersection and union. However, because the initial spaces are only intersections basis spaces, and because we are ultimately interested in the smallest common propagated space across all operators, it suffices to consider closure under intersection only.
A brief intuitive justification is as follows. Suppose space of the form A U B (with A + B) appears in the propagated closure for the operators. Writing this set in its Disjunctive Normal Form (a union of intersections), we obtain a union of terms, each of which must be propagated individually by all operators, since unions do not appear in the primitive families. If we now replace every union in this representation by an intersection, we obtain new space that is propagated by all operators and contained the original set. Consequently, any common propagated space built using unions admits smaller counterpart formed purely through intersections. As result, the smallest common propagated space is built entirely from intersections, and closure under intersections is therefore sufficient.
Our problem is therefore to find the smallest element (under () among all intersection-closure of the propagated spaces associated with each operator. This task is made more difficult by the presence of non-trivial inclusion relationships between these spaces, which may cause distinct expressions to represent the same underlying space.
To illustrate these challenges, consider the example discussed in Section 4.3, involving two operators Ti and T2 and six properties A through F:
T propagates An B, EnC, D, To propagates CnA, Dn B,
Bncce C
Taking the closure under intersection, we obtain for Ti the family of propagated spaces
P (AnB, EnC, D, AnBnD, EnCnE, AnBn AnBnEnCnD),
Similarly, for T2 we obtain
P2 = A, DO B, CΩANB, DUFOB, CO COANDOENB At first glance, the intersection Pi nP appears empty. However, using the inclusion B B. we see that
AnBnC AnBnCnE,
31

---

which shows that An AnBB C' belongs to both families. Hence,
PinP2 = (An
In general, for a typical operator, the number of primitive propagated spaces may grow quadratically with the size of the state space, while the intersection-closut of these spaces can grow exponentially in the number of primitives. Consequently, a naive approach that explicitly computes every propagated space for each operator and then intersects them is computationally infeasible.
To address this, we introduce a dynamic programming algorithm that reduces both the time and memory complexity of the procedure. The following sections present detailed discussion of this algorithm, including a proof of convergence, an analysis of its computational complexity and running example.
32

---

G.2 ALGORITHM DESCRIPTION IN PSEUDO-CODE
Algorithm Find smallest common propagated space
Require: O A of operators for which know propagation results.
Require: B: A set of basis function spaces.
Require: P: The propagation results for all the operators in O,
Require: (T....., T list of operators in the graph.
Require: the non-trivial inclusion basis.
Ensure: F the smallest common propagated space.
1: Create a mapping m between (1...., K} and B, with #B.
2: Create the sets P, E PP(1,.... K}) for each based on P and m.
3: Create a dictionary based on and m such that if {i} c then Rli..
4: Pe + <P) P) for all
5: n n
6: while (P) does not converge do
7: (pi)sg) < (Upepy P).s.
8: for j in (I,..., do
9: Phtt + Refine spopiepppppgtteessspc((pPP (pf) R)
10: end for
11:
1
12:
end while
pdd UpEpp-11
Create by mapping back 8 to B using m
15: Return J
Algorithm 2 Refine Propagated Spaces
Require: Pj: Set of elements of P(fl...., K})
Require: (p% ke:: List sets of integers [I....,NN] .N, B is the set of elements that appear in
Require: R: Dictionary corresponding to the non-trivial inclusion basis. If C* {i} then E R[i]
Ensure: p=+1, Refined list of spaces consistent across all operators. (PT7 with the notation of the subsection G.3.3)
1: p'+1 Pi
2: for each in P do
3: for each in do
4: if Do. covers. R, p²) then
5: break
6: end if
7:
for each p in (p]) do
8:
if i & ph then
9:
Remove a from Sp break end if end for
10:
11:
12:
end for
14:
end for
return Sh+11
33

---

Algorithm 3 Do i covers Pj
Require: i: An integer
Require: R: Non-trivial inclusion basis.
Require: : Set of clements P(fl...., K)), it is the set of elements that appear in Pj.
Ensure: covers: Boolean indicating whether i covers Pj
1: copers +- False
2: is key of R. then
3: for C' in Rij do
4: ifC C pj then
5: covers t True
6: Break
7: end if
8: end for
9:
end if
10:
return covers
G.3 PROOF OF THEOREM 4.2
G.3.1 MATHEMATICAL DEFINITION OF THE PROBLEM
In the framework introduced by Koole (2007), structural properties of the optimal value function and policy can be derived from the propagation behavior of the operators forming the operator graph representation of the Bellman equation.
Formally, consider a graph of operators Ti,..., Tg. where n is the dimension of the state space, and value functions belong RN" Define base family of K subspaces of R denoted as B = [B....., Bx}, ). In this framework, these base subspaces are generated systematically, with details provided in ??
From these base subspaces, we define the set of function spaces for which propagation results can be derived as:
S = span B E
B, P(LL....K))
.EQ
where P((1,.... K}) is the power set of (1....;A) KJ. We equip S with a non-trivial C relationship. We discuss more precisely what it means bellow.
For each operator Tj, we can identify a set propagated spaces S,, which subset of The objective is to determine the smallest common space under C across all Sy:
== min n span Sj.
F is indeed the smallest element of S that is propagated through all the operators and therefore through the overall graph. From Theorem 4.1, conclude that v* e F and derive structural results for the optimal policies.
Definition of the non-trivial C relationship.
The ordering relationship C must be defined according to the following rules:
Base (trivial relationships): The relationship starts from set of trivial inclusion relation-
ships, such as An B c B.
Generation rule for non-trivial relationships: We add a finite family of non-trivial inclusions of the form (i). From these, all other needed inclusions must be generated by the following rule alone (without invoking the general transitivity rule to create new
ones):
A C B and C C D, then A A C BOD.
This rule should be sufficient to produce a consistent ordering. We refer to this finite set of non-trivial inclusions as the non-trivial inclusion basis. A similar constraint hold for
34

---

equalities, in particular should not have the rule (A BB A) A=B and only the following ones: :
1. Intersection If A = B and C = D, then (AnC) ( (BnD)
2. Augmentation: If A B and A c C, then (AnC) B.
C. is fully defined by the non-trivial inclusion basis.
The idea behind this constraint is that we can check any inequality is verified in a constant time we have the non-trivial inclusion basis and non-trivial equalities have common form. It is used in lemma G.2 and in lemma G.3. We show that these rules are verified in our framework in section E.3.
G.3.2 REFORMULATION OF THE PROBLEM
We reformulate the problem better align it with an algorithmic approach:
Replace B with I = K}. In other words, each space is identified by an index.
Replace S with P(I) = P((1,.....
Replace C with an ordering relationship C* over P(I). This extends the canonical inclusion
relationship (II). For example, Nweu Bu N B, becomes V C* U.
The non canonical C implies non canonical equality relationship =' defined as U c V and V < U then U =" V. Notably trivial such as (1, 2, =* (2,3).
now have equalities that non
For each relationship in the non-trivial inclusion basis {i} C U, we introduce a tuple representation r = (i, U). Denote R as the set of all such inclusion relationships.
Replace S, with the corresponding Pj C P(Z), such that S, = {Nk B; B,QQ0 Q p
The closure under intersection, span Sj. is equivalent to span P,. which is defined as the closure under two operations: union and the generation of new sets using the extended ordering relationship C². In other words if U W E span P, and V c U, then the set V UUU W is also included in span P.,
The problem now becomes finding the biggest common element for C* across all span P,
IF =" max (N
N span Py.
Here, the intersection is taken with respect to the = relationship.
This reformulation is advantagcous for algorithmic purposes because the implicit relationships among functional spaces, captured by C* and P(I), are made explicit through the set R.
G.3.3 SOME NOTATIONS
Below we introduce several pieces of notation that will be used our construction. Throughout, let , c. PII), and let be any index in I.
We say that i appears each family (Ai...., AN) if, for every f1.....N) N). there exists at least one set a E A, such that E a. This notion naturally extends to subset I C I: we say that I appears in each family all i appear in each family according to the above definition. If we only consider one family A, we say that appears in A.
For a particular Aj, we say covers A₁ if there exists (i, U) E such that U appears in Aj.
We write 4 (j. (AI....,Ayy An)) if either appears in each family (Ai...,, AN), or covers AG-
35

---

Finally, given A A, P(I), for jach E {I.....J} define
Aj = f [ ViEa: (is (A1 ........... A.l))
We then define the function
F(AI....,AA)
Az).
G.3.4 THE ALGORITHM
straightforward yet naive method would be construct the span Pj for each j by exhaustively applying every closure rule, then intersect these sets at the end. However, due to the con-trivial inclusion relationships, this expansion can be both difficult to implement and prohibitively large in memory usage scaling exponentially with the size of each Pj-
Instead, we propose a more efficient procedure that avoids this blowup. We form sequence of tuples {P" with pd (PI...., Py) and p=+1 = F(P").
will be shown below that this sequence converges to a stationary limit
pc (PP ..... P.).
We then define
xd0
UP
PEPS
and prove that for each j.
U P. and p =" IT =² max (N span Py PEP
In other words, the family of subspaces (Br k p00) constitutes the smallest space that is propagated through the entire operator graph.
G.3.5 PROOF OF CONVERGENCE
Fixed points correspond to common propagated spaces. Lemma G.1. Let
(PI,..., Pj) ) a tuple of subsets in P(I) such that the corresponding function spaces of each P, are propagated by operators T,. Define pj UpeP, for each j. If P is a fixed point of F, then p; =* Pj for all i, and the set F == (B, p1} is common propagated space across the operators.
Proof. Since a fixed point F, every index i E p1 must satisfy
(1, Py)).
There are two ways this can happen:
appears each family (PI.... Py). this case, belongs to Py for every j.
2. i covers P,. Here, there exists (i, U) R such that U C Pi- By definition, {i} C* U. Consequently, pi (i) = pl.
Combining these observations, define
p1 = {i E Pı appears each family
From the cases above, we see pl =* P1, and fact pi =" p// for all j. Hence,
P1
P2
PJ-
Finally, let F, {B; E pj}. Since each F, is propagated by T, and F, =' F, for all i, we conclude that F = (B; E pi} indeed single common propagated space for all the operators.
36

---

Equalities under =" share useful structure.
Lemma G.2. Uf =" V, then Uand Vcan be decomposed as U = U1 U U22 and V = U/ where U1 V1, U =" U1, and V =" V1.
Proof. In our setting, and due to the specialized nature of the C relation, every non-trivial equality under =" can derived from a collection of trivial equalities by repeatedly applying two fundamental rules:
1. Union
B and D, then (AUC) = (BJD)
2. Augmentation: If = B and A C C. then (AUC) = B.
the equalities used in these steps already satisfy the decomposition property of the lemma, then the newly derived equality also satisfies it. Since all trivial equalities fulfill this property the outset, an induction argument ensures that every equality produced in this manner will do so as well.
Common propagated spaces have a corresponding fixed point.
Lemma G.3. Let's consider common propagated space F across the operators T3- There exists fixed point p = (PI....,P) PJ) of F which corresponding propagated space (lemma G.1) is F and such that Pj C P,
Proof. Let's consider a common propagated space F and a corresponding representation N
n span P.-- Lets Pj the representation of p in each span Pj. Thanks to the previous lemma G.2 we can write py p) pp for all j such that p = p1 = = p). Now let j. and take E Py. There 2 possibilities:
E p. and therefore appears each family (PI...., PJ).
E př and therefore {i} C* pt. And with arguments similar in the lemma G.2 (relying on the specialized nature of C we can say that covers Py.
In other words i (P, . Py)). We write each Pj union of elements of P, and define P/ the set of these elements. From the previous result we can conclude that P' = (Pl...., P')) is fixed point of F. This conclude the proof.
Theorem G.4. Let {P"]x be the sequence defined in the algorithm, where each P" This sequence converges to fixed point, and the corresponding function space the smallest common space propagated by all operators.
Proof. We note p = (PP.... PJ). For each [PP)) is a decreasing sequence of subsets of the finite set PIZ). Each one of them is then stationary after certain point, therefore {Pm ] is itself stationary after certain point.
We can now let poe be the limit of this sequence. By the previous lemma G.1 we can define Poo and Foo
[B; i p=o) } be the corresponding common propagated space.
Suppose there is another common propagated space F. By Lemma G.3, there exists fixed point P (Pi,..., P₃) corresponding to routine induction shows that any set removed from Pj some step of the algorithm can not appear in Pj. Therefore UpEP, C p. and Foo C F. Hence,
Fxo is the smallest among all common propagated spaces.
G.3.6 COMPLEXITY
Applying F to each P, requires ((N.2²) time per iteration, where max; EpEp, #p denotes the maximum total number of spaces across all propagated sets for any operator. In practice, the sequence {P"} typically converges in only few iterations, ensuring that the overall runtime remains tractable. Additionally, the memory complexity is O(NJ), representing a significant improvement the naive approach, which is exponential in both time and space.
37

---

This gain is already meaningful for small-scale problems. For instance, in state space of dimension n, the size of the base set B, and hence the quantity N, typically scales as n². When n = 4, the base set already contains #B 53 elements.
G.3.7 A RUNNING EXAMPLE
In this section, we illustrate the algorithm using a running example. Consider the following setting:
Ti propagates FnA, EnA, C, DOF, H,
T- propagates HnC, DOF, AnB, T3 propagates FNG, CnBnI, AND, H,
DOCCE, Fc B, ACG.
Using the notation from the formal proof, start with the initiation (n 0):
P (FnA, EnA, C, DnF, H}.
P (HnC, DnF, AnB),
P3 (FNG, CnBnI, An D, H},
p E,
P2 D, H),
P3 I.
First Iteration (n 1). We now evaluate which propagated sets preserved across all operators.
For Ti:
F, =
keep.
C:C'p n keep.
EnA:C E p2 np.. D. and DNC E keep.
DDF: D,F p n + keep.
Thus,
P = BENA,ENAL C, DOF, H).
For T2:
HNC:H,CH pi p2 keep.
DOF: D, E rp npg keep.
AnB: A A pl 0 gg. C and F E pd = keep.
Hence,
P = (HNC, DOE, B).
For Ts:
FnG: F E pf n p2, A G and A E p8 keep.
CnBnI: I & pl np and not involved in any relation = discard.
AND: A, E pl np + keep.
H: H E p 0 - keep.
38

---

Therefore,
P3 = (FnG, AND, H).
We now have
/ J.,. (A,B,C,D.F.H), P3 HH
Second Iteration (n 2).
We now report only the spaces that are discarded in this iteration.
For Ti:
C C P3 discard.
=i= (FnA, ENA, DO H).
For Tg:
HNC: C p3 + discard.
P2- - AnB).
For T3: We keep all the spaces, therefore: :
P2 (FnG, AND, H).
Update:
p D,
pg (A,
13 (A.
Third Iteration (n 3). For Ti:
EEN A: Previously kept due to D DOC c E, but now C' pf + discard.
H: & p discard.
(FnA, Dnf).
For T3: We keep all the spaces, hence:
p = (DNF AnB).
For T3:
H: $ p2 + discard.
PS = (FNG, AnD).
Update:
P (A,
2 F.
(A,D,F,G).
Fourth Iteration (n = 4). At this stage, the propagated sets remain unchanged, indicating conver- gence. Thus, the largest common propagated space is:
An = AnDOR
39

---

H
WHY THEOREM 4.1 IS NOT TRIVIAL? ILLUSTRATIVE EXAMPLES
Temas
Tixtt
Tats
Teoms
Tusr
Tain
T
Tusis
Tust'
Te
universal topology
atternative topology
topalogy for non-event-bareee MDPs
Universal topology for event-based MDPs, alternative topology for event-based MDP, and the topology for a non-event-based MDP.
In this section, we explain why the existence of a universal operator graph topology for event-based MDPs is not trivial. First, for event-based MDP, it is possible to have operator graphs with alternative topologies. Second, for a non-event-based MDP, may be impossible to construct an operator graph using the universal topology. We illustrate these two points through examples. The summary of the results is illustrated in the figure above.
H.1 THE M/M/1 EXAMPLE WITH AN ALTERNATIVE OPERATOR GRAPH TOPOLOGY
For easy reference, restate the Bellman equations for the M/M// example with controlled arrival and departure here:
Atp+a a
Atuta + (o)
(2,1(1, min
(1
(60)
A+a
À + +
(x, min ac.E(0.1]
gr(c)))
dcn
(x) (1-
am)) Vi -
(61)
+
where (x) is the value function defined on the queuing state x:
A+a +7 + Vo(I, P Vv( -1- A (1-At1) v)( (z) A Pn(x)
(62)
Instead of the value function V Vi((()) on the queue length, we can decompose the Bellman equation on the standard value function (x, e) the full state (x.e).
For example, the value function Va+1 (I, A) can be rewritten as
(2, Tain Teost, (Tunie' (Ty [V (z) To [+] Ter (=)))),
(63)
Toost, o (Tunit' (Th (v) (T
(64)
with the modified event operators
Tx (x)) (a A), Tor (v)( Va(x,D), Tor V+(x)] = Vn(x, Ø).
(65)
modified uniformization operator
Tonir (U(,, Uz, ((,,
(66)
Ph (x) +7 [ U(x,A) + P D) (1- A U(2,
(67)
A + a
A
an action-dependent cost operator
Toost a (U((z,)) e), al} = e), U((r,))),
(68)
and minimization operator
Tmin [U[(2, e]] min Ul(z,e).a].
(69)
aeA....)
40

---

H.2 AN EXAMPLE NON-EVENT-BASEE MDP WITH A DIFFERENT OPERATOR GRAPH TOPOLOGY
An example of a non-event-based MDP the M/M// queue with controlled arrival and service rate optimization.
Patients arrive according a Poisson process with rate and wait be served. The state (x, e) has two components: the number of patients in the queue E N4 and the event E { DJ, where denotes arrival and denotes departure. The action (CA) aca, E {0, I} when a new patient arrives, where 0 denotes rejection and 1 denotes acceptance, and service rate optimization (RO) Ago E "MI....,,KK. The actions space
(Aca) (go) consists of admission control
{0, 1 x (1....... (x) (11 P1....., px)
SE c=
A,
(70)
E (x
When the system is not empty (x the state transition time is exponentially distributed with rate A(s, a) = x + agc. and the state transition probability is
[a/=ztas]
A, e' A
A
1 (at (0'=xtaa-1)
e = A, e' = D
P()(s,0)=
Xtass
(71)
[w'=x]
e D, =
Xtaw
1 (m'=8-1) Xtas
D D
The cost includes one-time reward r for accepting a patient or one-time penalty p rejecting patient, holding cost unit time (z( that depends on the number of patients in the system, and a service cost per unit time Pa (ARo) that depends on the service rate. So the cost can be calculated as
Pa (a++))tp((m)) t
A, aca 1
č(8, a) =
c +
P. (a)
A, aca 0
(72)
A+
(om))
A+
We can see from equation 71 that while the state transition probability can be decomposed, the probability of the event Pa ar,a) actually depends the action. This is because the service rate affects the probability of the next event being an arrival or departure.
In this case, cannot use the universal topology for non-event-basee MDPs.
41

---

I DETAILED DESCRIPTIONS OF EXAMPLES IN SECTION 5
In this sections we give more details on the examples discussed in section 5.
Example 3 (The MCTS succeeds to generate formulation with high structural expressiveness in complex problems). Let us consider the following problem:
We aim to minimize the long-run average cost of operating our hospital. The hospital has 3 wards arranged sequentially, sharing total capacity of 20 beds. Each ward has its own healthcare team and manages its patients. On avverage, 7 patients arrive at the first ward per hour. The wards serve patients at average rates of 10, 5, and 2 patients/hour, respectively. Patients progress sequentially: from the first ward to the second, and then from the second the third. After treatment in the third ward, patients leave the hospital. Incoming patients can be rejected, incurring a cost of 20. Additionally, patients be directly transferred from ward to the next before being served at an average rate of 3 patients/hour for each ward, with each transfer costing 5.
Key challenges: There are various types of events (controlled arrivals, departures, transfers) and implicit constraints (nonnegativity) on the state space.
The first level of the consists of defining the parameters of the problem, while the second level identifies the state space. This gives:
Tbbeds = 20,
Tarrivals 7,
Tservice = (10, 5, 2),
2 + + 23 S 20, 31, 22,22,00 23 0.
Tiransfer opportunity
Crefusal 20,
Ctransfer
Here, x (I1, (I1,T2, constraints were implicit.
T2 xz)) represents the number of patients in the respective wards. Notably the positive
The next step defines the events, their probabilities, and the available actions with their corresponding
costs and effects on the state. Let I Tarivals + Tservice,1 + Tservice.2 + Tservice,3 + 3r wrunster opportunity
and (ex) (es) the canonical base of IR. The events are as follows:
Patient arrival:
Purrival = Farrivals/ T,
Anrrial auccept: ayefuse }
Pariival x I, Gaccept)
1 = x + &1),,
P Parivaal (x' D. Orefuse)
1 1(x' x),
Carival (x', D, a)
Crefusal L(a arefuse).
Patient served ward 1:
Pservice, Fservice,1
Avervice, Ø,
Pservice, 1 (a' (a'(x)) 11(x' + if > 0, 1(x' x),
otherwise,
Gservice, 1 (x', 0.
Patient transferred ward 1 to ward 2: Ptransfor,1 1 Ttransfor opportunity/ T,
Awanster, 1 agransters 4keop )
Piransfer, I (x² I, Ouransfer) 1(x' 61 E2)
P Piransfer, (x x, (keep) = 1(x' = x)
Cranster, 1 (x', 2, a) Cuanster (a Guanster)
We do not detail the system dynamics for the remaining events: "Patient served in ward 2", "Patient served ward 3", and "Patient transferred from ward 2 to ward 3," as they are similar to the examples illustrated above.
42

---

The next step is identify the operational cost, which in this problem is equal to (Maybe should add one).
Using the dynamics of the system for each event, already derive the corresponding operators. In the last layer the tree the LLM identifies the operators for which propagation results apply. For this problem, the identified operators are:
Patient arrival
TcA.I((x) min + f()); +e))
Patient served ward
01 f1
if > 0, otherwise.
TTD ff(x),
Patient transferred ward 1 to ward 2:
TcID.(1,))(z))) = min Cransffrr + f(x - (2),
Patient served ward 3
(x) f((x =(ax=
Similar operators can be derived for "Patient served ward 2" and "Patient transferred from ward ward 3."
For each of these operators we can automatically list the functional spaces they propagate, for instance TeA.1 propagate all the following spaces (see Appendix for the details of each of them)
1, UI, Cæ(1), Super(1, 1, 2). Super(1, 3). Sub, Super(1, (1, 2) SuperC 2), Super(1, n S1,erC(1,3). Super(1,3) n SuperC(3,, 1), Super(1, n SuperC(2, 2ub n SubC(L1,) 2) Sub(1, n SL), Sub(1, n Su) Sub(1, n SubC(3, 1), MM
We also do this for Tumit and Teoa Also, depending on the shape of the state space certain spaces must be dropped. Finally, we our second algorithm introduced in the subsection 4.3. For this problem we end up with the following propagated space:
In UI A MM
From which we can extract automatically the following structural results:
1. Controlled arrival in ward let "CA(1) S + {0, 1 be the optimal acceptance policy in the first ward such that 0 is refusal and acceptance.
(Ca(1) is decreasing in the number of patients in the hospital.
(CA(1) is decreasing in the directions (1, (1,00 and (1, 0, -1).
2. Controlled departure from ward 1 to ward 2 :. let "CTD(1.2) : S - {0, 1) be the optimal departure policy such that O correspond to keeping the patient in the ward and is moving them to ward? 2.
TCDD(1,2) decrcasing in the number patient in the ward 2, in the direction 1,))
"CDD(1.) increasing in the number of patient in the ward 1, ie in the direction (1,0,0).
3. Controlled departure from ward 2 to ward 3 let TCn((23) S - {0, 1} the optimal departure policy such that correspond to keeping the patient in the ward and is moving them ward 3.
43

---

Vn-1 Toose (umat) 0.95 unif
Vinit = Timi Cnnir(Vontteen Contenied acrival ward
Vervioe completion 1, Venntroled degarture
Coutcolled antival ward + 10V
10V Service completion
+ 5 Vervice completion 2
2Veeviice completion
3V Controled departurn
3 Controiid degacture
3 Controded departree
Controled anrival ward
Service complesion
Vservice completion (TD(aa(
VService completion
20) (V,)
= TTD(La)
(V.)))(V))
Voonteoied departure
Cantroleed departurr
VConteotec depurture
2 (V,)
TeD(sSoee=s) (Va)
Figure 5: Operator graph of Example 3
CTD(2.3)
is decreasing in the number of patient in the ward 3, ie in the direction
(0,0, 1).
(CID(2.3) increasing in the number of patient in the ward 2, in the direction (0, 1,)
In other words, the optimal policy of the problem is threshold along many different directions. These structural results and the optimal policy obtained by running solver on the formulation are then communicated back to the user.
Key takeaways: Autoformulating event-based MDP involves multiple steps, and our proposed algorithm effectively navigates these challenges in complex problems. Most the time the resulting formulation has high structural expressiveness
Example Two correct graphs of operators with different structural complexity
Let us consider the following problem:
We aim to minimize the long-run average cost of operating our hospital. The hospital has ward that manages types of patients with shared healthcare teams. There are No beds in total. The average arrival rates of the patients are /y/hour and >a/hour respectively. A team take care of a patient with average rate that depends their type py/hour and py/hour respectively. When patient arrive we can refuse it, it occurs a cost of e₁ for the first type of patients and 02 of the others.
Key challenges: We cannot obtain structural results from the straightforward problem formulation. How to find an equivalent combination of operators that allow us to obtain structural results?
Straightforward problem formulation. The natural events of this problem are Arrival of patient of type 1, Arrival of a patient of type 2, Departure of a patient of type I and Departure of a patient of type 2.
This approach lead to the following operator graph:
V = Teus {TTuii (TCA(L) (V,), (V,", TDII) (V)), (V"),
With probabilities Timi that depends on the state, you get for instance
11
with = max (11, (22). PD(1) A1 A2 +NN
Koole's s results don't extend probabilities that depend the state in Tuit. We can't get any structural result from this formulation, even it is right one.
However, this formulation is actually equivalent to the following one:
2 0+
Teus (Tuni [Tcaa) (V",) (Vo Tbaa
44

---

This time the probabilities in Tumir are (with r A1 + X2 (No)::
1. PCA(F) = X
2. PD(1) = PD(2) = 1 (1 )1P22)
which don't depend on the state. The dependence in the state has been absorbed by the new TD operators for which we have structural results:
r (A1 (A1 + 12) f((= - (()))
2pmn
2pmm (A1 (1-F))
f(x)
X2)
Indeed, with this formulation we can show that the following space is propagated through the Bellman equation:
InCx O Super
And we can deduce structural results from there.
Problem formulation and structural analysis inherently connected, certain valid formulations may not permit structural analysis.
Key Takeaways:
Example We don't have any formulation that reveals the structural results.
Let us consider the following problem
We aim to minimize the long-run average cost of operating our hospital. The hospital has 3 wards arranged sequentially, with capacities of 5, 15, and 15 beds, respectively. Each ward has its healthcare team and manages its own patients. On average, new patients arrive at rates of 3, 20, and 5 patients/day in the respective wards. The wards serve patients rates of 10, 5, and 3 patients/day, respectively. After being served in the first or second ward, we can transfer to the next ward at cost of per transfer or keep them in the current ward. Patients served in the third ward leave the hospital. Additionally, patients can be moved back from ward 2 to ward I at rate of 3 patients/day or from ward ward 2 at a rate of 1 patient/day, each transfer incurring a cost of Incoming patients can also be refused, incurring costs of 5, 10, and 15 for wards 1, 2, and 3, respectively.
The solution to the problem exhibits structural properties, but these cannot be anticipated regardless of the choice of operator graph.
Key challenges:
The autoformulation part of the algorithm managed to find correct operator graph
V T Toss ( (niii (T'A,1 (V,2) 2C,,, (V,),,
TCTD. (V,.., (23). (Cm.),.. (2..)..)))...).
TCTD, (V,,,, TDI,s
The structural results observed experimentally (see Figure 6) cannot be predicted from the operator graph. Unlike Example 2, this issue cannot be resolved with a better formulation, as the structural results have not yet been theoretically established.
Key takeaways: The current method for identifying structural results fails on certain problems, as it depends on limited theoretical results.
Example 6 (Two wards with controlled jockeying). Natural language description
We aim to minimize the long-run average cost of operating our hospital. The hospital has two wards running in parallel. each managing own patients with a dedicated healthcare team. The first ward can hold up to 5 patients, while the second can accommodate treatment in the second ward before leaving the hospital. Each patient in the hospital cost 2/hour to the hospital. On average, 3 patients arrive at the first ward per hour, and 5 arrive at the second. New patients can be rejected, incurring a cost of 5 for the first ward and 10 for the second. The first ward operates at frequency of 10 patients/hour, while the second operates at 5 patients/hour. Patients treated in the first ward can either remain there at no cost (but will require further care by the same team before leaving the ward) be transferred the second ward cost of 2. Additionally, patients can be transferred back from the second ward to the first at a frequency of patients/hour, with each transfer costing 2. Refusing a transfer incurs no cost.
to 10. Patients complete their
45

---

12
Figure 6: Optimal policy for controlled jockeying problem across three wards with controlled arrival and unControlled departures the last ward. One of the event is the opportunity to move a patient from ward 2 to ward 3, the possible actions are move (in red) or keep (in blue). The graph shows the switching curve the optimal policy depending on the number of patients in the wards. The optimal policy is structured but can not anticipate it with the results from Koole (2007) and therefore it's beyond the capacities of our algorithm.
The operator graph of the problem illustrated 5, The Bellman equation propagate the following function space:
I In Super SuperC
Let (n1, n2)) be the number of patients in the two wards. We have the following structural results for the optimal policy:
1. Controlled arrival ward let "CA(1) S + 1) be the optimal acceptance policy in the first ward such that 0 is refusal and acceptance.
(Ca(i) is decreasing in the number of patients in the hospital.
(CA(1) is decreasing in the direction (1, -1).
2. Controlled arrival in ward 2 let TCx(2) S + {0, 1} be the optimal acceptance policy in the first ward such that 0 is refusal and acceptance.
TCA(2) is decreasing in the number of patients in the hospital.
TCA(2) is decreasing in the direction (11
3. Controlled departure from ward 1 to ward 2 :, let =ČTD( (12) S - {0, be the optimal departure policy such that 0 correspond to keeping the patient in the ward and is moving them to ward 2.
(TD(1,2) is decreasing in the number of patient in the ward 2, ie in the direction (0, 1). (CDD(1,)) is increasing in the number of patient in the ward 1, ie in the direction (1, 0).
4. Controlled departure from ward 2 to ward :. let "TTD(2,)) : S - f0, 13 be the optimal departure policy such that 0 correspond to keeping the patient in the ward and is moving them ward 1.
CTD(221) is decreasing the number of patient in the ward 1, ie in the direction (1,0). (CTD(2,1) is increasing in the number of patient in the ward ie in the direction (0, 1).
46

---

(Vez))) 2 0.955
Vast Voaateia unind vard 12t Vierie copplitinn wed 12s Vousndelittagge oo
Wevetroee + Wooerrie
WV nxaphtiinn word
Clsttoll cangg to
Vovendalaniiall wards Tespersa (Va)
Vosttneet mord
Vanci neniitie aonnec word (bu
Visste change of
Te
Figure 7: Operator graph of Example 5
J DETAILS ON THE METHOD
J.1 LLM ENHANCED MCTS
The Monte Carlo Tree Search (MCTS) formulates the problem in four steps, which correspond to four levels of the tree. A node in the first layer, denoted m1, represents the parameters of the problem, such as the number and size of queues. A second-layer node represents the state variables and the constraints defining the state space. A third-layer node mg represents the possible events, their probabilities, the corresponding actions and operational costs. Finally, fourth-layer node m4 represents the operators associated with each event.
For given problem description, each m; is identified through the standard MCTS steps: selection, expansion, evaluation, and backpropagation, omitting the simulation step in this context. Details are given bellow. For give node m, we denote (m,)d(m;) the children of the node in the tree.
pookk-propggation step
Early termination of bad rollouts
Rowani from terminal nodea
171
LLM
evaluation
DOT geniog
Figure 8: MCTS for constructing operator graph of event-based MDPs, (1) Solver feedback complements LLM self-evaluation for more objective rewards. (2) Syntax checks at intermediate nodes detect errors early, preventing failed full rollouts.
J. SELECTION
The selection step guides the search towards promising regions of the tree. Starting from the root, the algorithm recursively selects child nodes using the Upper Confidence Bound for Trees (UCT):
In ((m)) mi+1 = arg max (Child(mm)) (V(m++)) + w N(m+41)
Kocsis & Szepesvári (2006). This process continues until reaching an unexpanded node. Here, mf+1 is the selected child node, V(m++1) is its estimated value, N(m,) and N(m+41) are visit counts for the parent and child nodes respectively. and w is exploration constant. This formula balances exploitation (first term, favoring high-value nodes) with exploration (second term, favoring less-visited nodes).
47

---

J.1.2 EXPANSION
Upon reaching an unexpanded node m, of depth we generate its child nodes through an expansion process. Unlike traditional MCTS, which operates within a predefined search space, our approach ex- plores an open-ended hypothesis space of component formulations. To facilitate this expansion, we employ LLMSs as adaptive hypothesis generators. These models, conditioned on the partial formulation constructed up to node m, propose potential formulations for the next component in the search process.
At each node ra,, the LLM generates potential child nodes m, corresponding to next-step component formulations. This process follows the probability distribution:
Pa (m d)
(73)
where d represents the problem description and mg: represents the partial formulation constructed up to that depth.
The LLM queried using a structured prompt consisting of three components: (1) the original problem description d, provided in natural language; (2) the partial formulation mgi. represented in ISON format; and (3) level-specific instructions that define the expected output format and relevant constraints. Additionally, we instruct the LLM return candidate formulations using the same structured dictionary format to ensure consistency across iterations.
For each node expansion, we sample H candidate formulations from the LLM'' output distribution:
Child(m:) {m/ m4+1 pol-Imsi, Vh [M]]
(74)
where m represents the h-th candidate formulation.
When generating new candidate formulations, we systematically verify their syntax consistency with the existing partial formulation by evaluating the mathematical expressions as the constraints or the probabilities of the events. This step allows us to immediately discard invalid options, ensuring coherence throughout the expansion process. candidate fails meet syntax consistency requirements, we re-query the LLM for revised formulation.
the maximum number of retries is reached, we assume that the inconsistency is not solely due the stochastic nature of the LLM but rather stems from issue in the existing partial formulation-suchh as missing variable definition in earlier steps. such cases, we terminate the rollout and immediately backpropagate score of (I along the current branch.
J.1.3 EVALUATION
After expanding a node, each newly created child node undergoes an initial evaluation to estimate its value, guiding subsequent selection the search process. Assessing the correctness of partial formulation relative to the original problem description is non-trivial, to address this challenge, we employ an LLM-based ranking evaluation for each set of child nodes, providing a more informed initial assessment.
Specifically we give the L.M the partial formulation till the current node m-;; and it rank the child nodes Child(m,). The resulting ranks are then center-normalized to the interval [0, 1], with the middle rank positioned at 0.5. We define the normalized score as s(m)t.). which used to initialize the value of each child node:
Vptior (m 1(m
(75)
This approach deviates from traditional Monte Carlo Tree Search (MCTS), which typically assigns uniform priors newly expanded nodes. Instead, the LLM evaluates the formulations by incorpo- rating optimization principles and problem-specific context, potentially capturing aspects such as formulation correctness, constraint feasibility, and alignment with the overall problem structure.
48

---

J.1.4 BACKPROPAGATION
Unlike conventional Monte Carlo Tree Search (MCTS), which typically simulates the problem to terminal state after expanding child node, our approach continues expansion until terminal node my reached. The resulting formalization m-çi is evaluated against a baseline, typically the formalization obtained after one rollout. The LLM assigns score between 0 and 1 based on its preference for the new formalization over the baseline. To mitigate bias in the LLM signal 8I.MM we also check whether the solver successfully converges on the formalization, setting Aconvered = if converges and otherwise. The final backpropagated score then given by SLLM X Sconverged.
The backpropagation process consists of updating the value of each node m, along the current branch using the following update rule:
back (m.) Vbuck (m,) (m,)) + SLLM X Sconverged
(76)
[(m,) +1
where (m)) denotes the number of times the value of m, has been updated. After applying this update, we increment the count:
(m,)) < ((m)) + 1.
(77)
K
DESIDERATA OF AUTOFORMULATION
K.1
DESIDERATA AND CORRESPONDING CHALLENGES
The overarching objective of autoformulation is to autonomously solve problems expressed in natural language. This objective can be decomposed into three essential desiderata: (see Fig. for how our framework fulfill them)
The ability to translate the natural language description into a suitable formal framework while preserving semantic accuracy. Autoformulation should correctly formulate the problem. (in the context of this paper output a MDP formulation that correctly reflects the problem description in natural language).
Accuracy.
Computational Tractability: The resulting formalization must support efficient computation of solution. For instance, autoformulation should identify structures of the optimal policy (e.g., the action is monotone the state). The structures should be identified based on the formulation only, before the problem is solved. This facilitates in selecting low-complexity algorithms tailored for finding policies with certain structures (e.g., solvers for threshold policies).
Interpretability: Autoformulation should also be interpretable in two aspects. Interpretability of formulation: We should be able to trace each components of problem formulation back to the natural language problem description. Interpretability of policies: By identifying structural properties of the optimal policy, the autoformulator can explain the policy, making it easier for non-technical domain experts to understand and adopt the policy.
These desiderata come with corresponding challenges that must be addressed. We discuss them below, and use them in Section 5 to evaluate the performance of our proposed algorithm against these criteria.
Challenges in Accuracy
Achieving correct formalization a non-trivial task, as it amounts to searching within vast space of possible formulations. The main challenges include:
Semantic Understanding:
The system must correctly capture the underlying dynamics of the problem described natural language. For example, understanding that admitting a new putient to a hospital reduces the number of available beds
Parameter Identification: Relevant variables. constraints, and objective components must be identified and instantiated correctly. For instance, the system should infer the arrival frequency of different types of patients to the hospital.
49

---

Syntactic Validity: The generated formulation must conform the syntactic requirements the chosen formal framework while preserving the original problem's 's intent. For example, state updates should be expressed using syntactically valid expressions, such correct Python formulas.
Challenges Computational Tractability
Fulfilling the second desideratum goes beyond achieving a correct formalization: the chosen repre- sentation must also support efficient solving. In this work, we particularly emphasize the extraction of structural properties, which gives rise to two key challenges:
Expressiveness of the Formulation: The formal representation must be sufficiently expres- sive to enable extraction meaningful structural results.
Structural Inference: Given formalization, the system should be able automatically identify structural properties that can guide or accelerate the solution process.
These two challenges are interconnected: the expressiveness of formulation determines which structures can be extracted, while the usefulness of the formulation itself depends on the system's capacity to exploit these structures.
Challenges in Interpretabilityy
For safety, usability, and insight, both the formulation and the solution should be interpretable. This is important for expert auditing and for practical deployment by non-expert users. The main challenges are:
Formulation Traceability: Each element of the formalization should be traceable corresponding concept statement in the original natural language problem description.
Policy Understanding: The optimal policy for high-dimensional problems often behaves as black box. Making its properties explicit enhances human understanding and trust.
We consider a bospital with two wards: one for Critical patients one for dedicated teams. Both wards share Ncheds, Daily avernge Ae Critical and he General patients.
Formalisation
Computation challenges Computational Tractability
paticats, staffed by
Formulation challengrs
SSute space: "s
Parameter Identification
not have negative number of patients hospital)
Solver convex value function
Treatment miles are Ao Critical and joo General palients per day, with each team hindling one patient at time. Treated patients leave, freeing their beds. Ip arrival,
Semmntic Understanding
Operators
Syntax Syatix validity
patient may he admitted a available or rejected, incurring cost of for Critical and for
-oost Formulation Traceubility
Gencral paticats. Each admitted paticot generates holding
Threshold policy
Pa unit time. The objective to minimize the long run average operating with discouut factor
Interpeotability challenges
Pollcy Understanding
Figure 10: The challenges of autoformulation illustrated with an hospital example.
K.2 TYPICAL ERRORS WITH RESPECT THESE CHALLENGES
In Section 5, we evaluate the extent to which our algorithm addresses the aforementioned challenges. Further details are provided below.
K.2.1 ERRORS IN ACCURACY.
While our method largely resolves the Syntactic Validity challenge and exhibits strong performance in Parameter Identification, our primary focus is on Semantic Understanding, where most errors tend to arise. Semantic errors can occurs several ways
Missing Constraints: The algorithm may overlook implicit constraints in the problem description, such as the non-negativity of the number of patients in hospital.
Incorrect Event Modeling: may introduce artificial events that do not exist in the actual problem. A common example is inventing event to account for holding cost, modeled as an event with frequency 1 per time unit in which the state remains unchanged but a cost is incurred.
50

---

Failure in Uniformization: The algorithm may miscompute event probabilities when uni- formizing the process. For instance, it sometimes fails to distinguish between sequential and parallel service models. If denotes the service frequency per server.
In the single-server case (sequential), the probability of service is S/T.
In the multi-server case (parallel), the correct probability is x xf/[", where is the number customers.
K.2.2 ERRORS IN COMPUTATIONAL TRACTABILITY AND INTERPRETABILITY.
Our algorithm exhibits limitations both Structural Expressiveness and Structural Inference.
Limited Structural Expressiveness: some cases, the generated formalization lacks the expressive power needed to enable structural inference. It is illustrated and discussed with Example
Structural Inference: Given the proven performance guarantees of our dynamic programming algorithm (see Appendix G.3), the primary remaining bottleneck in structural inference lies in the incorrect labeling operators. For example, consider an assembly line where two elements from two queues combined to produce an item in third queue. The correct operator is:
(v V [21 1, 22 1, Is + 1])
The algorithm may erroneously interpret this as tandem departure operator:
TTD(L.))V(z)) = V(x' = [z] 1, 22, 23 + 1))
which neglects the role of 22 and leads to incorrect structural predictions.
Limitations of the Current Framework.
Example 2 highlights intrinsic limitations of the current framework for structural result extraction. Our approach relies on known theoretical propagation results for a fixed set of operators. In that example, identify three possible reasons why structural results cannot be inferred:
1. The correct common propagated space has not yet been identified.
2. The appropriate operators to model the problem are missing from the current library and would need to be introduced along with corresponding propagation rules.
3. It is theoretically possible that the Bellman equation propagates functional space even though none of the individual operators does-our current framework relies on a sufficient but not necessary condition, namely that each operator propagates the space.
To overcome these limitations, future work could involve extending the family of operators and enriching the library of propagation results. This can be done manually, following the methodology of Koole, or through automated discovery using machine learning techniques.
L DATASET
We constructed a dataset of 36 natural language descriptions of queueing control problems, varying
in difficulty by state space size, state constraints, and number of event types. To assess performance
in structure identification and support future research, the dataset includes three categories: (1)
problems with provable structural results (e.g., Example 1); (2) problems with empirically observed.
but unprovable, structures (e.g., Example 2); and (3) problems with no structural results. All problems address realistic issues from domains such as hospital management Bekker et al. (2017),
telecommunications Koole & Mandelbaum (2002); Bhulai & Koole (2003); Bekker et al. (2011); Zhang al. (2025c), freight dispatching Schwarz & Daduna (2006); Amjath al. (2023), assembly lines Adeyinka & Kareem (2018), and traffic control Boon et al. (2023).
The problems are inspired by the literature and have each been manually designed and solved by an expert in OR. The ground truth consists of five randomly chosen states together with their optimal values. These optimal values were computed from the OR formulation using a general-purposs value iteration solver, with convergence assumed the value changed by less than 0.05 between two
51

---

Histogram of Number of States
Number of Dimensions
Nurbee of Operators
10
16-
IL
Number of Problems
12
10
107
107
Number of States llog scale!
Operazors
Figure 11: Distribution of some complexity measures across the dataset.
iterations. A formulation therefore considered correct if its optimal value function matches the ground truth within a tolerance 0.1.
Tab. 6 and Fig. 11 sum up the characteristics of the dataset.
Table 6: Overview of the dataset by domain.
With Structural Properties
Domain
# Problems
Avg. # States
Avg. Dim.
Avg. # Events
Hospital management
15
12
1017
3.3
6.7
Freight dispatching
9
335
2.2
5.9
Assembly lines
6
0
217
2.8
4.5
Traffic control
4
93
5.25
Telecommunications
2
2
726
2.5
5.0
Total
36
20 (56 %)
594
2.8
5.9
52

---

M PROMPTS
We aim to elicit the LLM to give the final output as a Python dictionary the following format:
formalization.dict template
"parameters";
"values": (b,
"descriptions" ()
,
"state "state_space": |
"variables": "constraints"; [1
ionnccioon {
apporattooooLoosspppomtmtttiiio null, saiscoun__factorr null, "description": null
"events": (),
"events_proball syennts_probbiiittiess"
ion_emmittiioo_ffoooooooooooo null,
"probabilities": ()
"pperators" ()
In the following, we describe the prompts that ask the LLM to generate nodes in the Monte Carlo tree. As will see, the prompts completely application-agnostic and can be directly applied to problems in different domains.
53

---

We give the LLM general context prompt at the beginning.
General context prompt
I have sequential decision problem: <<<PROBLEM DESCRIPTION>>>
want to analyze this problem using the Event-based Optimization Framework introduced by Koole (2007). This framework models systems where actions are taken in response to random, uncontrollable events that occur over time. The framework's 's core components are event operators, which serve the building blocks for defining the system's 's value function.
Framework Description
1. Event Operators: Event operators represent the dynamic transformations of the value function in response specific system events. Formally:
T; V - V, for i . 1,
where T; maps value function V from the state space to new value function over the same space.
2. Recursive Value Function: The system's 's value function, Vns is defined recursively to capture the sequential nature decision makinng:
--1 V Σ P..((V ==
where:
Vn- is the value function from the previous step.
pj is the probability of event occurring at each step, satisfying Σk-1
Pi
T; represents the impact of event i on the system.
C' is the operational cost.
is the discounting factor.
This formalization captures the stochastic nature of the problem, where random events dictate the evolution of the system, and the value function reflects the accumulated system performance time.
Objective Given this theoretical foundation, we need to formalize the problem by defining the following components:
<< <<<FORAAIIAATINN DICT>>>
54

---

The following prompt generates the first-level nodes my of the Monte Carlo tree.
Parameters completion prompt
_icc based on the problem deseription, you should complete the "parameters" field which consists of assigning constants to descriptive variable names. Only complete "parameters" and nothing else.
Task:
Complete
Guidelines:
1. Your primary responsibility is to define all the parameters from the problem descrip- tion that will later be used to define the state space, objective function, events and operators.
2. You may include additional parameters in format suitable for facilitating the subsequent tasks of defining the state space, objective function, events and operators.
For parameters that involve multiple indices (e.g. x [i] or [i, j]), use the most appropriate data structure, such as lists, dictionaries, or dictionaries with tuple keys, to represent them.
4. For each parameter, include clear, descriptive comment explaining its meaning.
5. Ensure that the parameter names (keys) descriptive and intuitive.
6. The dictionary should contain two keys: "values" " and "descriptions",
"values" " should contain the actual parameter values.
"descriptions" should contain the descriptions of the parameters.
Format: Return only the Python dictionary update (i.e., Cormalizationn "parameters") -...) following the described re-
quirements.
55

---

The following prompt generates the second-level nodes my of the Monte Carlo tree.
based on the State space completion prompt
Task: Complete the "state space" " field in the formalization problem description. Specifically, define:
1. Variables: Populate the "variables" field to represent the system's 's state. Each key-value pair must adhere the following structure:
<key>:
"description": <description>,
"type": <type>,
"iteration space": <space>, "default value": <default value>
Guidelines:
Essential Variables Only: Include only the strictly necessary variables to describe the system's 's state. Exclude costs, events, or redundant variables.
Less is better: Due the curse of dimensionality, keep the number of state variables minimal. If a variable can be derived from others, do not include it.
Symbolic Name: Use unique, descriptive names that reflect the variable's role.
Description: Clearly explain each variable's role in the system.
Type: Either "int" or "float".
Parameter Variables: Use parameter-defined values directly (without using parameters
Iteration Space: Use Python-style list comprehension syntax (e.g. range (n) ) Use None for scalar variables.
Default Value: Must be single int float initialize the variable across its iteration space.
Consolidation: Merge similar variables under a single key with an appropriate iteration space.
Populate the "constraints" field define boundaries of the state space. Each key-value pair must adhere to the following structure:
Constraints:
Kconstraint.key=
"equation"; <mathemati catptttiiallepaiiooo...oo "description": <description>
Guidelines:
Descriptive Constraints:
Use meaningful names.
Mathematical Description: Use Python-like math expressions. Use list compre- hensions when appropriate.
Equality and Inequality: Capture valid bounds and implicit problem constraints.
Parameter Variables: Refer directly them, nested parameters
syntax.
Indexed Variables: Use bracket notation (e.g., x [i))..
Each constraint should be preceded by comment explaining its purpose.
Comments:
Important Notes:
If the problem has no explicit constraints, consider implicit ones.
If no constraints apply, return: formal izat ion ["state
space"] ["constraints"] (None: None)
56

---

Return: Only the Python dictionary update (i.e., formal iiaziionniiiiioooo ct ("state
space"] ...) following the described requirements.
57

---

The following prompt generates the third-level nodes my of the Monte Carlo tree.
Objective function completion prompt
Complete formalization,de based on the problem description, you should complete the "objective ive function" field. Follow these requirements:
Task:
Define the operational cost and discount factor such that it adheres to the following structure:
*ob jective function" = {
"eperational cost": <cost>, "discount factor": <factor>, "description": <description>
Operational Cost:
Replace <cost> with the operational cost of the system. This represents the cost incurred between events, such as maintaining the system or executing ongoing operations.
Do not include costs triggered by events or actions - those in the "events" field.
Important:
Use parameter-defined variables, hard-coded values. Express the cost as string formula.
Default:
not provided, use "0"
2. Discount Factor:
Replace <factor> with the system's discount factor, which determines the relative importance of future rewards.
Use parameter-define variables if mentioned. Otherwise, use the default value 9.95.
Description:
Replace edescription ion> with short explanation justifying the chosen opera- tional cost and discount factor.
Return:
Only the Python dictionary update (i.e., formalization.ae.. ("objective function: ...) following these requirements.
58

---

The next few prompts generate the fourth-level nodes my of the Monte Carlo tree.
Events completion prompt
Complete formalizat -itt based on the problem description, you should complete the "events" s" field. Follow these requirements:
Task:
Each key-value pair in the dictionary must adhere to the following structure:
<key>:
"description":
Pactions"; <description,,
sactionkey>>:
"description": <action description>,
"cost": <cost>,
"state_change": <state_change>
}
Guidelines:
1. Events:
Define the events that can occur in the system. An event is random occurrence that changes the state, the cost, or triggers need for action.
2. Each <key> must be symbolic name representing distinct event and will be used in the Python implementation of operators.
3. Descriptive Events: Use unique, symbolic names for each event.
4. Event Description: Replace <description> with a string describing the event's impact on the system.
5. Actions: Define the actions that can be taken in response to each event. If there is decision involved, define only one action named "default".
6. Action Description: Replace <action description> with description of the action's ' role.
7. Cost:
Replace <cost> with a string representing the formula for the cost of the event-action pair. Use parameter-defined variables.
8. State Change: Replace <state <state.change> with a list of equations (as strings) describing how state variables change due the event and action.
9. Constraints: Do not repeat feasibility constraints infeasible states automatically result in V = +oc.
10. Parameter Variables: Use parameter-defined variables directly; do not reference
them via parameters ....].
11. Indexed Variables: Use bracket notation for indices (e.g., x [0]).
12. One Event per Entry: Do not merge events. Each event must have its own dictionary entry. Avoid undefined parameters (e.g., no generic in event keys).
Return: Only the Python dictionary update (i.e., foxmalization.dicet ("events") following these requirements.
59

---

Events probabilities completion prompt
Complete formalization dict based on the problem description, you should complete the "events probabi 1 iise"" field.
Task:
Requirements: Each key-value pair in the dictionary must adhere to the following structure:
<key>:
<probability>
1. Events Probabilities:
Define the probabilities of each event that can occur in the system. If needed, consider a uniformization framework.
2. Each <key> links to the corresponding
defined in the "events" section. 3. Replace <probabi ityy by the probability of the event. Use parameter-defined variables instead hard-coded values. Put the formula in a string format.
4. Parameter Variables: Use parameter-defined variables directly (do not reference
them via parameters .).
5. Indexed Variables: For indexed state variables or parameters, use standard bracket notation (e.g., x [.]).
Return: Only the Python dictionary update (i.e., formalizationdae sevents probabilities") ...) following these requirements.
Operators completion prompt
Complete Cormalizationa complete the "operator" field.
Task:
based on the problem description, you should
Each operator is 'sub Bellman' equation linking the optimal value function after the occurrence of the corresponding event (and the optimal action) to the value function before that.
List of Available Operators:
T_(A}
Description: Arrival operator
Definition:
TA (SState.variabll) f(x) f(r + estate vartaaee
Parameters: [' state variable']
T {CA)
Description: Controlled arrival operator
Definition: sestate.variable....oo f(x) min(f(#) cı fxx
vetate.variable) + 02)
Parameters: [' state.variablle, 'el1, 'c.2"]
Description: Departure operator
Definition: Tp(staae.vvriaaaa variable) f(x) = f((x @stato.variable)
Parameters:
[' state.variable"
T-[cD}
Description:
Controlled departure operator
Definition:
min(f(x) + c1,
if wartee > 0
Teofstate.vrriable.c.....
f(r -statttaaaaaa) o2), (())())
otherwise
Parameters: [' ('state.variable', 'cl', 'c.2
TT[TD}
60

---

Description: Tandem departure operator
Definition:
Thggleaieeerrrabbb....eeeeeereri f(x)
[( egtatovarribbll
if aatae..accabbl
+ +
f(x),
otherwise
Parameters: [' ('state.vrrabllel,,, 'state.variable.21
[CCDD]
Description: Controlled tandem departure operator
Definition:
Vorpsstate.variaaleel.. ott.aa/ee...ttte..aaaaaaea..o... =
[min(f(x))+ cr f(x + @state.wariablel Cstate.variable.)) + 62), if dssatewariable. la (a+f(a) f(x),
otherwise
Parameters:
[' ('state variable 1', 'tate variable 2',
' 1', ' 2
Field Format: Each key-value pair in the dictionary must follow this structure:
<key>:
"description": <description>, "operator"; <operator>
Guidelines:
1. Replace <key> with the name of the event the operator corresponds to.
2. Replace <description> with string that explains the operator's impact.
3. Replace <operator> with the selected operator and its parameters in string format (e.g., (i=xx( c.1=1, c_2=2) ").
4. If operator fits, use None.
5. Use parameter-defined variables directly (not via parameters
6. Use bracket notation for indexed variables (e.g., x [ii)).
7. For repeating patterns, use Python for-loops or list comprehensions where applicable.
8. Do not include event probabilities they are handled elsewhere.
Return:
Only the Python dictionary update ct formal 1 z on wow.ddiit"oooraaaaaaaaaaa ["operators"] = =...) following these requirements.
(i.c.,
61


Reviews:
[{"review_id": "1s3E0S1iyJ", "reviewer": "Reviewer_w778", "summary": "This paper proposes a method to autoformulate MDPs for the control of queueing systems using LLMs and grounded on operator theory.\nThe core of the proposal is to construct the MDP's Bellman equation as a graph of operators, each operator transforming the value function corresponding to certain event. The paper develops a three-level operator-graph topology that covers a broad class of MDPs. The paper proposes a Monte Carlo tree search algorithm to build such operator graphs, and an algorithm that identifies structures of the optimal policy to accelerate the solution.", "questions": "1. What is the complexity of the search procedure?\n2. How do the chosen operators apply to other domains?\n3. How much is the MDP search space reduced?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "S1. Core structural result (Theorem 4.1) on the existence of a universal three-level operator-graph topology that represents a broad class of MDPs for queueing/control.\n\nS2. Application of the operator graph to queueing-control MDPs and other examples, showing interpretability.\n\nS3. Positioning within operator-learning trends for the sake of structured representation learning.", "weaknesses": "W1. The blanket claim that this the first work to represent Bellman equations as directed acyclic graphs (DAGs) of operators is unsupportable. Prior work already treats Bellman-style equations/updates compositionally or on graphs. The paper asserts precedence for the general idea of viewing Bellman equations as DAGs (graphs) of operators. There is substantial prior literature that already represents Bellman-like computations compositionally, localizes Bellman updates to nodes in a graph/DAG, or studies Bellman operators and their compositions. Representative, explicit prior works:\n\nYu, Mahmood, Sutton: On Generalized Bellman Equations and Temporal-Difference Learning, ICML 2017. This paper develops generalized Bellman equations, explicitly treats different multi-step / trace-based operators and shows how value-function equations arise from composing/choosing among operators; the paper frames Bellman relations in operator terms. \n\nGopalan et al.: Planning with Abstract Markov Decision Processes, ICAPS 2017. This work decomposes planning into a hierarchy (a DAG-like structure) of abstract subtasks and perform Bellman-style planning localized to nodes/levels. \n\nJothimurugan et al.: Compositional Reinforcement Learning from Logical Specifications (DiRL), NeurIPS 2021. This work encodes specifications as abstract graphs and composes high-level planning with low-level RL; value/policy computations are decomposed across the graph structure.\n\nW2. Lack of comparison against existing structured MDP representations (factored MDPs, hierarchical MDPs, AMDPs, object-oriented MDPs, modular RL). Experimental comparisons use ad hoc baselines rather than state-of-the-art methods with established theoretical or empirical guarantees.\n\nW3. The scope of applicability (specific classes of queueing/control MDPs) is narrower than the broader claims sound. It is not demonstrated that the same reduction works well for more complex continuous-control MDPs or even on classical RL benchmarks (gridworlds, inventory control, navigation).\n\nW4. The search procedure is described only at a high level and its computational complexity is not specified.\n\nW5. It is unclear whether the chosen operator set (shift, clamp, increment, etc.) applies to other domains.\n\nW6. The claim that the operator-graph topology reduces the MDP search space dramatically is not empirically validated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cFcPwlJ8PD", "reviewer": "Reviewer_4PC5", "summary": "This paper introduces a novel operator-theoretic framework for the autoformulation of Markov Decision Processes (MDPs) from natural-language descriptions, with a specific focus on queueing control problems (e.g., hospital ward management, call centers). Unlike existing works that use large language models (LLMs) to autoformulate one-shot optimization problems, this paper extends the idea to sequential decision-making, which involves greater complexity due to dynamic transitions, stochasticity, and implicit constraints.", "questions": "Beyond queueing systems:  would be good to see the proposed operator-graph topology and autoformulation framework generalize to non-queueing domains.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Theoretical novelty: The paper makes a conceptually and mathematically novel contribution by connecting operator theory with automatic MDP formulation. It introduces an operator-graph representation of Bellman equations, and rigorously proves the existence of a universal three-level operator topology applicable to a broad class of event-based MDPs. This gives the autoformulation task a solid theoretical structure.\n\n2. End to end framework: The proposed operator-graph framework is comprehensive and well-engineered. It integrates syntax checking, solver feedback, and self-rewarding search to achieve high formulation accuracy and interpretable policies. Empirical evaluation on queueing control problems demonstrates consistent and significant gains over baselines.\n\nThis paper presents a theoretically grounded and well-validated framework that advances the automation of sequential decision problem formulation, making it a strong candidate for acceptance.", "weaknesses": "This framework is evaluated only on queueing control problems, which, although well-chosen, represent a narrow subclass of event-driven MDPs. The paper does not demonstrate whether the proposed method generalizes to other sequential decision domains such as robotics, finance, or inventory control.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tRCGQrJD9O", "reviewer": "Reviewer_7bBF", "summary": "The paper describes an approach to use LLMs to automatically formulate sequential decision problems as a class of MDPs. Of particular interest is the formulation of the solution of MDPs in terms of \"operators\" or transformations, and a dynamic programming approach to reason over the compositions of operators. When the MDP exhibits some structural properties such as monotonicity, the formulation is able to exploit it and solve the MDP efficiently. Besides the search space of different formulations is also made efficient by the operator theory approach. MCTS is used to search the space of formulations and is shown to be effective over 36 natural language descriptions of queuing problems of different complexities.", "questions": "The example in 313-317 sounds mysterious. You need an explanation of why A \\bigcap B \\bigcap C is the right answer right here and not in the appendix. In general it is not clear how \\bigcap and \\subset should be interpreted here and hence what B \\bigcap C \\subset E means. \n\nThere seems to be an error in the Equations in page 25. The last step of Equation (58) has one \\gamma. However, the next 3 transformations contain two \\gammas (the first and the third) and composing them seems to yield \\gamma^2. Can you clarify?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "+ Autoformulation is an important understudied problem that bridges the gap between the LLMs and the classical AI such as optimization. The current work closes an important gap by bringing autoformualtion to the MDP literature. \n+ Automatically deriving the structural properties of the policies through the analysis of the operator composition is an important contribution. It makes the application of MDPs to real world problems much easier by non-experts.  \n+ Empirical results show that Syntax Checks (SC) and Solver Feedback (SF) makes MCTS much more effective, out-competing state of the art methods such as Chain of Thought and targeted prompts.", "weaknesses": "- The appendix of the paper is too long (40+ pages) and unsuitable for conference reviewing. \n\n- On the other hand some parts of the appendix appear too important to be in the appendix, eg, the algorithms in F and the theorem in E. \nThe authors should consider a better packaging of the paper, cut the appendix, and write a full-length journal paper that includes all details. \n\n070, 074 ComputationAL challenges\n085. BellMAN equation\n311. \"brutal force\" -> \"bruteforce\"\n354. SF and SC are referred here for the first time, but defined only in 364. \n450. \"untractable\" -> \"intractable\"\n479. \"an universal\" -> \"a universal\" ('u' is a vowel, but a/an distinction is based on how it sounds).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pC6kHIiWHj", "reviewer": "Reviewer_zt4g", "summary": "A very interesting paper proposing an automated approach to translate and solve MDPs formulated as natural language descriptions within the domain of queueing theory. The approach uses LLMs to translate the natural language into an operator graph; the paper then provides theoretical and algorithmic results to operate on such graphs. The paper is complemented by a large set of tasks, itself a valuable resource.", "questions": "I don't have particular questions at the moment, the paper was clear in its logical flow.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "While this is not my research field, it seems to me that the topic and approach are highly original. The paper has a nice combination of theoretical results (the introduction of the operator graph and Thm 4.1), algorithmic results (including complexity results on them, Thm 4.2), and implementation. The data set assembled consists of many tasks from realistic scenarios, and itself may constitute a valuable resource.", "weaknesses": "My understanding is that the theoretical/ algorithmic results are still predicated on the LLM being able to construct a correct graph, which is clearly not always the case. The paper is very dense, nevertheless the addition of \"Take away\" summaries enable also the reader with passing knowledge to get a grasp of the main innovation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)