acceptodds
Under review as a conference paper at ICLR 2027

Regret Minimization in Factored MDPs with Endogenous and Exogenous Factors

Abstract

We study regret minimization in non-episodic factored MDPs whose state has an exogenous part, such as the demand arriving at a server, whose transitions do not depend on the action, and an endogenous part whose transitions do. Existing factored-MDP algorithms treat every factor alike and explore the exogenous factors as if actions could inform them, and the literature on MDPs with exogenous inputs exploits the split only under restrictions on the reward or on the endogenous dynamics. We allow the reward to depend jointly on both parts and the action, and the endogenous dynamics to be unknown and stochastic. Our algorithm, Hybrid-DORL, keeps UCRL2 style optimism on every factor but pools the visit counts of each exogenous factor across actions, since no action changes how often such a factor is observed. Its regret is with a factor on the endogenous factors only, and a matching lower bound shows that this dependence on the action count is tight. The algorithm is oracle-efficient: it plans on an augmented factored MDP with a standard planning oracle. Moreover, when the exogenous transitions are i.i.d. a plug-in variant needs neither optimism nor augmentation on the exogenous part: the prefactor falls from the diameter to its endogenous half and the augmented MDP shrinks by a factor exponential in the number of exogenous factors. In experiments Hybrid-DORL has lower regret than every baseline, its advantage over the best baseline grows with the number of actions as the bounds say, and the plug-in variant matches its regret at a fraction of the planning time.

Primary area:
reinforcement learning
Keywords:
factored MDP, exogenous factors, regret minimization, optimism in the face of uncertainty

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_JzhqOpenReview ↗
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 TT and ∣A∣|A|, 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 TT and ∣A∣|A|, 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
  1. 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?

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

  3. 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?

  4. 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?

  5. 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?

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

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 TT and ∣A∣|\mathcal{A}|. With the paper-wide bounds ∣Si∣≤W|\mathcal{S}_i| \le W and ∣S[ZiP]∣≤Wm|\mathcal{S}[Z_i^P]| \le W^m, Proposition 1 reads O~(D dendoWm+1∣A∣T+D dexoWm+1T)\widetilde O(D\ d_{\mathrm{endo}} \sqrt{W^{m+1} |\mathcal{A}| T} + D\ d_{\mathrm{exo}} \sqrt{W^{m+1} T}) and Theorem 2 reads Ω(dendoWm∣A∣T+dexoWmT)\Omega(\sqrt{d_{\mathrm{endo}} W^m |\mathcal{A}| T} + \sqrt{d_{\mathrm{exo}} W^m T}). The two agree in TT and in the position of ∣A∣|\mathcal{A}|, and the gap is the prefactor DD and a dW\sqrt{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)(dT^2)^{\Theta(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 π\pi of the true MDP MM that reaches it fastest. Run π\pi in the plug-in model McekM^k_{\mathrm{ce}} 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\Delta^k_{\mathrm{exo}} per step. Over n=2Dendo(M)n = 2 D_{\mathrm{endo}}(M) steps, the target is hit with probability at least 1/21/2 in MM by the Markov inequality, hence at least 1/41/4 in McekM^k_{\mathrm{ce}} once Δexok≤1/(4Dendo(M))\Delta^k_{\mathrm{exo}} \le 1/(4 D_{\mathrm{endo}}(M)), and restarting every nn steps gives Dendo(Mcek)≤8Dendo(M)D_{\mathrm{endo}}(M^k_{\mathrm{ce}}) \le 8 D_{\mathrm{endo}}(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)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)D_{\mathrm{endo}}(M) and not with a diameter of the planning model.

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 DendoD_{\mathrm{endo}} 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 tt contains the arrival level, the mean response length and the model mix of minute tt itself, and the capacity for minute tt 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 138138 and autocorrelations from 0.940.94 to 0.820.82 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 2020 sweeps, then increment span below 1/t1/\sqrt{t}), for T=105T = 10^5 and two seeds. Both algorithms make about 400400 planning calls at dexo=3d_{\mathrm{exo}} = 3 and 450450 at dexo=4d_{\mathrm{exo}} = 4, each stopping at 2020 sweeps. The total planning time is 6868 s against 0.50.5 s at dexo=3d_{\mathrm{exo}} = 3 and 12601260 s against 2.72.7 s at dexo=4d_{\mathrm{exo}} = 4 (Hybrid-DORL against Hybrid-DORL-PI), and the total online runtime is 7171 s against 3.43.4 s and 12621262 s against 5.65.6 s, the remainder being the environment simulation. The regret at T=105T = 10^5 is the same as in Figure 5(a) for both. In the revision, Figure 5(b) shows the total planning time against dexod_{\mathrm{exo}}, 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.

Reviewer_Y9vAOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies online regret in a factored MDP (FMDP) with a partitioned state space: an exogenous part that does not depend on actions and an endogenous part that does. They show that one can shave off a factor of \sqrt{A} where A is the action space size from the term that depends on the exogenous part of the state space. The \sqrt{A} factor remains in the term corresponding to the endogenous part. Experiments show the benefit of the improved algorithm.

Critical strengths

Handles a natural problem and arrives at informative upper and lower bounds

Critical weaknesses

Novelty relative to previous work is very low. I am not convinced that there is a major innovation here on top of Xu and Tewari (2021) and Rosenberg and Mansour (2022). The paper does not clarify what the crucial innovation is. The paper is more appropriate as a short note in a relevant journal than as a full paper in ICLR.

Questions for authors

What is the main novelty of your algorithm and its analysis relative to previous work?

1 comment

We thank the reviewer for the direct question, and we would like to clarify the novelty as follows. First, we agree with the reviewer regarding Proposition 1. Hybrid-DORL is DORL with the action removed from every exogenous scope, and Proposition 1 is what the analyses of Xu and Tewari (2020) and Rosenberg and Mansour (2021) give for this algorithm. Neither paper states this bound explicitly, so we state it in our paper, as a proposition rather than a theorem, because the two theorems need it as a reference point: Theorem 2 is compared with it term by term, and Theorem 1 is measured against it. We also admit that the submitted introduction starts from Hybrid-DORL and calls Hybrid-DORL-PI a variant, which may have given the impression that Proposition 1 is the main result. The revised introduction (in blue) states on the first page what is inherited and what is new. The new contributions are the following, and none of them is in the two cited papers.

(1) Lower bound. To the best of our knowledge, there was no regret lower bound for factored MDPs with a mixed endogenous/exogenous partition before this work. The closest result, Theorem 4 of Tian et al. (2020), is for the episodic setting where no factor depends on the action. Theorem 2 provides one. Its two terms come from two hypothesis tests: at an endogenous parent-action pair, the learner has to find which of the ∣A∣|\mathcal{A}| actions is biased, and at an exogenous parent value, the learner has to find which way a coin is biased, which cannot be accelerated by any action. The second test is the new part, and it incurs regret only because the reward is joint. Compared with Proposition 1, Theorem 2 shows that, in terms of the dependence on TT and ∣A∣|\mathcal{A}|, the partition gives exactly the pooled counts and nothing more.

(2) Hybrid-DORL-PI and Theorem 1. In terms of the prefactor, however, the partition gives much more. Hybrid-DORL-PI keeps the structure of Hybrid-DORL but applies no optimism and no lift to the exogenous factors, and uses their empirical distribution directly in planning. The prefactor of its regret bound is the endogenous diameter Dendo(M)D_{\mathrm{endo}}(M), the time to move between two endogenous states, instead of the diameter D(M)D(M), which also includes the time to reach the rarest exogenous configuration, a time that no policy can control. The two cited analyses cannot give this prefactor, since their prefactor is the diameter of the optimistic model. Specifically, without optimism on the exogenous part, the optimism inequality, which is the first step of every UCRL-type analysis, no longer holds. In Appendix D we replace it by a benchmark-defect term, bound the bias span by a new argument (Lemma 7), and carry the endogenous diameter of the plug-in model back to that of the true MDP (Lemma 8). As shown in Figure 5(a), the regret of the two algorithms is almost the same (within 4%4\%), and it does not increase when D(M)D(M) increases from 10210^2 to 2×1062 \times 10^6. Therefore, on these instances the bound in Proposition 1 is loose by four orders of magnitude, while the bound in Theorem 1, whose prefactor is 1+Dendo(M)=3.11 + D_{\mathrm{endo}}(M) = 3.1, is consistent with the experiment. We note that Theorem 1 assumes i.i.d. exogenous transitions, and this assumption is stated explicitly in the revision.

(3) Planning cost. Since the exogenous factors are not lifted, the planning model of Hybrid-DORL-PI is smaller by a factor of about WdexoW^{d_{\mathrm{exo}}}. The time per value-iteration sweep on the two lifts differs by a factor of 407407 at dexo=4d_{\mathrm{exo}} = 4 (Section 7.4). The revised Figure 5(b) reports the total planning time over an online run of T=105T = 10^5 steps: 12601260 s for Hybrid-DORL and 2.72.7 s for Hybrid-DORL-PI at dexo=4d_{\mathrm{exo}} = 4, with the same regret (Appendix F of the revision).

Regarding the comment that the paper is more suitable as a short note, we understand this impression given the organization of the submitted version. The revised introduction states the problem and the two questions first, presents Hybrid-DORL-PI as the main algorithm, and reduces the inherited part to one paragraph. If the reviewer still considers the technical contribution insufficient after this clarification, we would appreciate it if the reviewer could point out which part, so that we can address it.

Reviewer_VkopOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies average-reward regret minimization in factored MDPs with a known endogenous-exogenous partition, where exogenous factors are action-independent and evolve autonomously. The authors propose Hybrid-DORL, which pools visit counts of exogenous factors across actions, and Hybrid-DORL-PI, a plug-in variant for i.i.d. exogenous transitions that avoids lifting the exogenous block. The paper provides a regret upper bound, a matching lower bound in the dependence on TT and ∣A∣|\mathcal{A}|, and experiments on synthetic instances and a real LLM-serving trace.

Critical strengths

[S1] The pooling design is insightful and efficiency-aware. Pooling exogenous visit counts across actions is a simple but well-motivated trick that exploits the structure of the problem and yields concrete computational savings in the plug-in variant.

[S2] The theoretical results are complete and fill a genuine gap. The paper provides both upper and lower bounds, with the lower bound being the first for this mixed-partition setting under a joint reward, and the two match in the dominant terms.

[S3] The real-data experiment is persuasive. The BurstGPT-based LLM-serving instance demonstrates the practical relevance of the setting and clearly exposes the failure mode of the baseline.

Critical weaknesses

[W1] The known factored structure and known endogenous-exogenous partition are strong assumptions. The paper assumes the parent scopes {ZiP}\{Z_i^P\} and the partition [d]=Iendo∪Iexo[d]=I^{\text{endo}}\cup I^{\text{exo}} are known to the learner, and that the reward function is known. While these are inherited from the factored-MDP literature (Xu & Tewari, 2020; Rosenberg & Mansour, 2021), they substantially narrow the applicability of the results. In particular, the paper does not discuss how sensitive the pooling argument is to misspecification of the partition: if an "exogenous" factor is weakly action-dependent, or if an exogenous factor has an endogenous parent, the action-independence used in Definition 1(i) fails and the pooled counts become biased. A discussion of robustness to partition misspecification, or at least an explicit acknowledgment of this limitation, would strengthen the paper. The lower bound is constructed within the same known-structure model class, so it does not address this either.

Questions for authors

See Weaknesses

2 comments

We thank the reviewer for the positive evaluation and for pointing out the issue of partition misspecification. We agree that this is a limitation of our work, and the submitted version did not discuss it. In the revised PDF we have added a limitations paragraph at the end of Section 5 (in blue). It states that the factored structure, the partition and the reward are assumed to be known. It also states that if a factor declared as exogenous is actually weakly action-dependent, then the pooled estimate at a cell is an average of the true rows over the actions taken there, so the guarantees do not hold as stated, and that the lower bound is constructed within the same known-structure class and therefore does not cover misspecification either.

In addition, we have added a sensitivity experiment, which is now Figure 8 in Appendix F. On the main instance of Section 7, we make the exogenous factor read by the reward action-dependent, such that the rows of any two actions differ by at most Δi\Delta_i in ℓ1\ell_1 norm, and we sweep Δi\Delta_i from 00 to 11 while the learner still treats this factor as exogenous. We compare with Hybrid-DORL under the correct partition and with NFA-DORL, at T=105T = 10^5 over five seeds. When Δi=0\Delta_i = 0, the regret of the pooled learner is 3.9×1033.9 \times 10^3, compared with 6.1×1036.1 \times 10^3 under the correct partition. As Δi\Delta_i increases, the regret of the pooled learner increases linearly, by about 0.09 T0.09\,T per unit of Δi\Delta_i, and it becomes worse than the two per-action learners when Δi\Delta_i exceeds about 0.60.6. Therefore, a mislabeled factor leads to regret linear in TT, with a slope determined by its action dependence.

Regarding the second case mentioned by the reviewer, an exogenous factor with an endogenous parent, we agree that this case is excluded by Definition 1(ii) but may happen in practice, and we have included it in the limitations paragraph. We would like to note that in the above experiment the mislabeled factor indeed has an endogenous parent, so the point Δi=0\Delta_i = 0 corresponds to this case. In this case the pooled count is indexed by the full parent cell, which includes the endogenous parent, and we did not observe any loss. What this case affects is Theorem 1, which requires the exogenous part to evolve on its own. A guarantee that degrades continuously with a dependence coefficient, i.e., Δi\Delta_i for the action and a similar quantity for an endogenous parent, is left as future work, and we state this in the revision.

Thank you for the detailed response, the new limitations discussion in Section 5, and the sensitivity experiment in Figure 8. These additions clearly address my concerns regarding partition misspecification, and I am happy to maintain my positive score.

Comments on the paper

1 comment

We thank the three reviewers for their careful reading and detailed comments. We reply to each review separately below. Here we summarize the point raised by all three reviews and list the changes in the revised PDF (in blue).

Regarding what is inherited and what is new, we agree that Hybrid-DORL is the existing factored-MDP machinery with action-free scopes and that Proposition 1 follows from the analyses of Xu and Tewari (2020) and Rosenberg and Mansour (2021). The submitted paper says this in Section 5, but the introduction starts from Hybrid-DORL and calls Hybrid-DORL-PI a variant, which gave the impression that Proposition 1 is the main result. The revised introduction states on the first page what is inherited and what is new: Theorem 2, the first regret lower bound for a mixed partition, and Hybrid-DORL-PI with Theorem 1, whose prefactor is the endogenous diameter instead of the diameter. Both are explained in the revised Sections 5 and 6. We also state the scope of Theorem 1 precisely: it assumes i.i.d. exogenous transitions, it does not claim a regret advantage over the optimistic algorithm on i.i.d. instances, and whether a different analysis could give the same prefactor for the optimistic algorithm is an open question.

The revised PDF contains the following changes, all in blue. (a) Section 1: the problem and the two questions (what the partition gives in the rate, and what it gives in the prefactor) are stated before any algorithm, Hybrid-DORL-PI is presented as the main algorithm, and the inherited material is reduced to one paragraph on the first page. (b) Section 2: notation and the model definition are separated. (c) Section 5: the argument that the endogenous diameter of the plug-in planning model is at most eight times that of the true MDP (Lemma 8) is explained in the main text, the step that requires the i.i.d. assumption is identified, and the open question above is stated. (d) Section 6: the side-by-side comparison of the upper and lower bounds under the same structural parameters (Remark 1 in Appendix E) is placed in the main text. (e) Abstract, Section 1 and Section 3: the separation from the exogenous-information line is corrected to the one stated in Appendix I, namely that our endogenous dynamics are unknown and stochastic, whereas Sinclair et al. (2023) and Wan et al. (2024) assume known deterministic endogenous dynamics. (f) A limitations paragraph on partition misspecification at the end of Section 5, and a sensitivity experiment in Appendix F (new Figure 8). (g) Section 7.4, where Figure 5(b) now shows the total planning time over a run for the two algorithms, and Appendix F: the planning cost is reported in full, i.e., the number of planning calls, sweeps, total planning time and total runtime, for the planners of Algorithms 1 and 2, with the regret of these runs in the new Figure 7. (h) Section 7.5 and Appendix G: the timing of the observations in the serving experiment is stated explicitly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.