- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies regret minimization in non-episodic factored MDPs with a known endogenous–exogenous partition, unknown transitions, and known rewards that may depend jointly on both state components and the action. Exogenous factors evolve autonomously. Hybrid-DORL specializes existing DORL machinery by pooling exogenous transition counts across actions. The paper also presents a lower bound matching the upper bound’s dependence on and , with gaps in other parameters, and analyzes a plug-in variant for i.i.d. exogenous dynamics whose bound uses the endogenous diameter. The experiments use synthetic instances and serving simulators fitted to a request trace.
Critical strengths
-
The paper provides a lower bound separating the action dependence of the endogenous and exogenous learning terms.
-
The authors include experiments to complement the theoretical results.
Critical weaknesses
My main concern is limited novelty. The core algorithm and general upper bound are inherited from existing methods, and I find the remaining contributions incremental.
The base algorithm does not constitute a substantial algorithmic contribution. The general factored-MDP framework already supports action-free parent scopes and the corresponding pooling of observations. As the authors acknowledge, Hybrid-DORL applies this structure to existing DORL machinery, and Proposition 1 follows from existing analysis. I therefore do not regard the base algorithm or its upper bound as a substantial advance over prior work.
The lower bound provides a limited characterization. It matches the upper bound only in and , leaving gaps in the diameter and structural parameters. Moreover, the construction increases the number of factors, factor sizes, and scope sizes, making the comparison less direct. Although the paper acknowledges these limitations, they weaken the lower bound’s significance as a central contribution. A simplified comparison under the same structural parameters is needed to make clear what has actually been characterized.
The plug-in refinement applies under a restrictive additional assumption. The improved diameter dependence requires i.i.d. exogenous dynamics, which excludes the non-i.i.d. setting used in the trace-based experiments. On the i.i.d. synthetic instances, the original and plug-in algorithms have essentially the same regret. Thus, the experiments provide little evidence of a statistical advantage from the refinement. It also remains unclear whether the improved diameter dependence requires the algorithmic modification or could follow from a sharper analysis of the existing optimistic algorithm.
The baseline comparisons provide limited evidence of novelty. The comparison with NFA-DORL chiefly measures the benefit of exploiting the known partition. Since action-free scopes can already be represented by existing factored-MDP methods, these results primarily demonstrate the benefit of using available structural information. They do not establish an algorithmic advantage over an existing method supplied with the same scopes.
The discussion of prior exogenous-information work is too broad. Some prior works already allow joint rewards and learn the exogenous distribution. For example, Wan et al. (2024) do so while assuming known deterministic endogenous dynamics conditional on the exogenous inputs. The paper should distinguish these assumptions more precisely. Joint rewards and the need to learn the exogenous distribution do not, by themselves, establish the claimed separation from that literature.
The proof overview does not make the technical contribution sufficiently clear. Section 5 contains a brief sketch, but it does not adequately explain what is new relative to the existing DORL analysis. In particular, the sketch relates the bias span to the endogenous diameter of the plug-in planning model, whereas the theorem depends on the endogenous diameter of the true MDP. The argument connecting these quantities appears central and should be explained in the main text.
The presentation makes the contribution harder to assess. The introduction starts with a literature review and moves quickly into the algorithmic approach before sufficiently developing the motivating problem and research questions. Application examples are provided, but their connection to the precise assumptions is underdeveloped. The preliminaries also mix notation and model definitions under the notation paragraph, making the exposition difficult to follow.
The serving evaluation leaves important protocol and modeling questions unresolved. The timing of the minute-level observations relative to the capacity decision is unclear. In addition, the evaluation uses fitted exogenous transition models and modeled server dynamics. The adequacy of the Markov and factorization assumptions, and sensitivity to the discretization and service model, require further justification before the results support strong conclusions about LLM serving.
The computational evaluation measures only part of the planning cost. Time per value-iteration sweep does not establish the complete computational savings. The number of sweeps required for convergence, total planning time, and total online runtime should also be reported.
Questions for authors
-
Which technical ideas in the lower bound and plug-in analysis go beyond specializing existing factored-MDP algorithms to action-free scopes? What makes the resulting contribution substantial beyond the already established benefit of pooling observations according to the known scopes?
-
Could the authors present simplified upper and lower bounds side by side using the same structural parameters? Can the lower bound be obtained with controlled diameter and without increasing the number of factors, factor sizes, or scope sizes?
-
How is the endogenous diameter of the plug-in planning model controlled by that of the true MDP? Could the authors explain this argument, and its differences from the analysis of Rosenberg and Mansour, in the main text?
-
Which step fundamentally requires i.i.d. exogenous dynamics? Under that assumption, could the original optimistic algorithm also satisfy a regret bound with the improved endogenous-diameter dependence?
-
In the serving experiment, are the arrival level, mean response length, and model mix available before the capacity decision? Do they describe the current minute or the preceding minute? Does the simulated policy receive any information that would only become available after the decision in an actual serving system?
-
How well do the fitted Markov and factorization assumptions describe the request trace, and how sensitive are the results to the discretization and service model? Could the authors also report complete planning and online runtime, including the number of sweeps required for convergence?
3 comments
As for the i.i.d. assumption (Q4), the step that requires it is the span bound (Lemma 7). When the exogenous coordinate is redrawn from one fixed distribution at every step, the Bellman equation of the plug-in model depends on the bias only through its average under that distribution, which is a function of the endogenous state alone, and the span of this function is bounded by the endogenous diameter. With a Markov exogenous chain the bias depends on the exogenous state, and its span may include the time to leave a rare exogenous state, which is the quantity we want to avoid. Regarding the optimistic algorithm, our argument does not apply to it, because the optimistic planner chooses the exogenous row inside the confidence box depending on the current state, so the exogenous draw is not a fixed distribution and the averaging step fails. Whether a different analysis could give the bound for the optimistic algorithm is an open question, and Figure 5(a) is consistent with both possibilities. We state this openly in the revised Section 5. We also agree that Theorem 1 does not cover the trace instances, whose exogenous chains are not i.i.d., and that it does not give a regret advantage over the optimistic algorithm on i.i.d. instances. What Theorem 1 provides is the prefactor guarantee that the existing analysis does not give, and the revision states its scope in these terms.
On the exogenous-information line, the reviewer is right: Appendix I of the submitted paper already states that Sinclair et al. (2023) and Wan et al. (2024) allow a joint reward and learn the exogenous distribution under known deterministic endogenous dynamics, but the sentences in Section 1 and Section 3 described the separation as the joint reward, which is incorrect. The separation is that our endogenous dynamics are unknown and stochastic. The revision replaces the sentences in the abstract, Section 1 and Section 3 with this statement.
Regarding the presentation, we agree with the reviewer, and the revised introduction states the problem and the two research questions, what the partition gives in the rate and what it gives in the prefactor, before any algorithm, and Section 3 connects the application examples to the two conditions of Definition 1. Section 2 is split into a notation paragraph and a model paragraph. Regarding the timing of the observations in the serving experiment (Q5), in the simulator the state at the start of minute contains the arrival level, the mean response length and the model mix of minute itself, and the capacity for minute is chosen based on this state. Therefore the simulated policy observes the levels of the minute it is about to serve, which in a real system are known only with a lag. A system that observes these quantities with a one-minute lag would use the levels of the previous minute as its exogenous factors, which also satisfies Definition 1, and this is the variant we should have run; we will report it in the next version. All four algorithms receive the same state, so the comparison between them is not affected, but the absolute regret values correspond to a server with one-minute lookahead. The revision states this explicitly in Section 7.5 and Appendix G.
On the fit and the computational cost (Q6), Appendix G reports the statistics behind the fit: the per-minute arrival counts have a variance-to-mean ratio of and autocorrelations from to over five lags, so the fitted chains are far from i.i.d., and the parent scopes were chosen from the conditional entropies of the levels. We did not run a sensitivity study over the discretization and the service model, and we do not claim conclusions about LLM serving beyond the stated instances. Regarding the computational cost, we agree that the time per sweep is only part of the picture, and we have measured the rest. We ran both algorithms online on the i.i.d. instances of Figure 5 with the planners of Algorithms 1 and 2, i.e., value iteration on the two lifts, with the same stopping rule (at least sweeps, then increment span below ), for and two seeds. Both algorithms make about planning calls at and at , each stopping at sweeps. The total planning time is s against s at and s against s at (Hybrid-DORL against Hybrid-DORL-PI), and the total online runtime is s against s and s against s, the remainder being the environment simulation. The regret at is the same as in Figure 5(a) for both. In the revision, Figure 5(b) shows the total planning time against , and Appendix F reports these numbers and the corresponding regret (new Figure 7).
I thank the authors for the rebuttal. The provided answers align with my original review, and I keep my score.
We thank the reviewer for the detailed review and the six questions. Since the weaknesses and the questions overlap, we group them by topic and answer the questions in order.
Regarding novelty and the baselines (Q1), we agree with the reviewer that Hybrid-DORL is the existing factored-MDP machinery with action-free scopes, that Proposition 1 follows from the existing analysis, and that the comparison with NFA-DORL measures the benefit of using the known partition rather than an algorithmic advantage. The submitted paper says the first two points in Section 5, and the revised introduction says all three. The technical ideas beyond this specialization are the following. (i) Theorem 2 is the first regret lower bound for a mixed partition. Its new part is the exogenous hypothesis test: at an exogenous parent value the learner has to find which way a coin is biased, which no action can speed up, and this test costs regret only because the reward is joint. (ii) In Theorem 1 the optimism inequality, the first step of the existing analysis, no longer holds without optimism on the exogenous part. We replace it by a benchmark-defect term, bound the bias span through the Bellman equation of the plug-in model (Lemma 7), and transfer the endogenous diameter of the plug-in model to that of the true MDP (Lemma 8).
On the lower bound (Q2), we agree that it characterizes only the dependence on T and ∣A∣. With the paper-wide bounds ∣Si∣≤W and ∣S[ZiP]∣≤Wm, Proposition 1 reads O(D dendoWm+1∣A∣T+D dexoWm+1T) and Theorem 2 reads Ω(dendoWm∣A∣T+dexoWmT). The two agree in T and in the position of ∣A∣, and the gap is the prefactor D and a dW factor from the Cauchy-Schwarz step of the upper bound. This comparison was Remark 1 in Appendix E, and the revision places it in Section 6. Regarding the second part of Q2, the construction enlarges the instance so that each block tests one hidden parameter, and we do not know how to avoid this. The hard instance also has a diameter of order (dT2)Θ(d), due to the reset that keeps it communicating, so it says nothing about the prefactor. A lower bound with a controlled diameter and the same structural parameters would need a different construction, which we do not have. We therefore claim matching rates rather than minimax optimality, and the revised Section 6 states this explicitly.
For the endogenous diameter of the plug-in model (Q3), the argument is Lemma 8 in Appendix D, and we agree that it should be in the main text. The revised Section 5 summarizes it, and the argument is as follows. Fix a target endogenous value and the policy π of the true MDP M that reaches it fastest. Run π in the plug-in model Mcek with the endogenous targets randomized so that the chosen rows reproduce the true endogenous rows, which is possible on the good event because the true row lies in the confidence box. The two path laws then differ only in the exogenous draw, by at most the exogenous estimation error Δexok per step. Over n=2Dendo(M) steps, the target is hit with probability at least 1/2 in M by the Markov inequality, hence at least 1/4 in Mcek once Δexok≤1/(4Dendo(M)), and restarting every n steps gives Dendo(Mcek)≤8Dendo(M). The difference from Rosenberg and Mansour is that their argument never leaves the optimistic model: optimism keeps every true transition available, so the diameter of the optimistic model is at most D(M). Here the exogenous part is not optimistic, so the planning model does not contain the true one, and the comparison has to go through a coupling with the true MDP. This is also why the bound is stated with Dendo(M) and not with a diameter of the planning model.