- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies almost exogenous MDP in which some variables which are treated as exogenous are in fact affected by the learner action up to a strength controlled by some known parameter . The reward and the dynamics of the endogenous system are known to the learner. The paper contributions read as follows 1) upper bound for tabular almost exogenous MDPs in which the term in scales only with the number of exogenous states and not with the cardinality of the full state space and a linear term in which is controlled by (which should be interpreted as the price to pay for treating as exogenous a variable which is in fact endogenous), 2) Lower bounds against a class of algorithms that does not see the reward of the environment and one for algorithms which can (notice that Exo-UCBVI- belongs to the latter class) and 3) finally the upper bound is extended to linear mixture almost exogenous MDP in which the almost exogenous kernel can be written as a linear combinations of dimensional features. This results allows the number of exogenous states to be potentially infinite while retaining efficiency because only shows up in the bound.
Critical strengths
The results are very interesting.
Moreover, I think that the problem is important. In practice many times we might consider as exogenous variables which are in fact endogenous.
Critical weaknesses
Presentation can clearly be improved, there are many pointers to the appendix: I think presentation is problematic because many important definitions and the algorithms are deferred to the Appendix. I would for example put your algorithms in the main and leave in the Appendix the pointers to some refined results such as the one that avoids assuming a maximum bound on the action (i.e. Theorem 2).
Simple setting Some assumptions are not very well justified. Why are the actions supposed to be scalars? And why the endogenous dynamics are assumed to be known? Please make sure to mention these limitations and draft some possible solutions.
Questions for authors
needs to be known the bonuses used by Exo-UCBVI- and Exo-VTR- need to know the action influence parameter . PTO has the benefit of not requiring this knowledge. What happens if you drop the terms depending on from the exploration bonuses? Can you still get guarantees?
Lower Bounds I do not think that I understand why the lower bound in Theorem 3 is meaningful. Indeed, I do not think that algorithms which are not allowed to observe the reward function can be expected to have sublinear regret. Theorem 4, looks at a more interesting class of algorithms but I do not understand why the lower bounds holds only on the UP instance. I suggest to the author to state the lower bound in an information theoretic min max manner. That is, for any algorithm in the class, there exists an instance in such that the regret is at least . I think this is already what the authors prove but it is not stated in this way which I find easier to read.
Avoiding Exploration Why does the PTO approach does not work for Linear Mixture MDPs?
Please see also my questions in the weakness session.
4 comments
Questions 1, 2 and 3
3- Question 1: For tabular Exo-UCBVI, the answer is affirmative. Appendix D.7 analyzes the variant with only the statistical bonus . On the row-confidence event, which has probability at least , the deficit relative to the reference-optimal values is bounded by
Accounting for that deficit yields Theorem 1's capped guarantee, with the cap-dependent term sharpened to . Theorem PTO gives the same regret order after removing the entire bonus. Appendix D.7 also gives cap-free guarantees for both variants. Both tabular variants operate without as an input.
For Exo-VTR, removing only the influence term leaves a valid but weaker guarantee. Appendix F.6 obtains an additional deficit term
At fixed positive influence, this expression can grow as , and the regret bound can be capped by . The additional term quantifies the value-estimation deficit introduced by removing the influence-dependent bonus. Its growth is an upper-bound contribution, not a lower bound on the modified algorithm's regret.
4- Question 2: The reward-aware result is now the main lower-bound result. Theorem 4 covers planners that optimize an action-independent model selected from the stated pooled point-estimate or confidence-set classes, while using the known reward function freely. The reward-blind theorem is retained as a secondary result in the appendix.
UP is a common witness because pooling attributes an action-induced upward transition to the external process. After pinning, the pooled point-estimate planner expects the price to increase even while waiting and selects concentrated sales. Confidence-set planners can still choose a temporary partial hedge after pinning, and that schedule also incurs a first-order loss. Under the actual transition law, spreading sales has higher first-order value. In DOWN, concentrated sales are first-order optimal, so the same construction gives no corresponding persistent loss.
For sufficiently small , Theorem 4 states the expected lower bound for pooled point-estimate planners, including their random pinning time, and the probability- lower bound for confidence-set planners, including deterministic burn-in. Section 5 also states the requested minimax formulation for the confidence-set class:
\max_{v\in\\{\mathrm{UP},\mathrm{DOWN}\\}} \mathbb E[\operatorname{Regret}_{v}^{\mathcal A}(K)] \ge (1-2\delta)_{+} \frac{g\varepsilon}{96} (K-T_{\mathrm{cs}})_{+} (1-C_{g}\varepsilon).$$ With $g\in(0,1)$ is the price gap, $T_{\mathrm{cs}}$ is the deterministic burn-in threshold in Theorem 4, and $C_g$ is independent of $K$ and the planner. The bound holds for sufficiently small $\varepsilon$, and $(z)_+=\max\{z,0\}$. UP supplies the same witness for every planner in this class. Appendix E.8 gives separate algorithm-specific results. **5- Question 3:** Tabular PTO estimates complete external transition rows. The present VTR estimator instead updates from the value-targeted features of selected actions. Appendix F.6 gives a two-stage exact-exogeneity example where waiting has continuation feature $1/2$ and selling has feature zero. With the zero-initialized ridge estimate, the greedy action values are zero for waiting and $1/4$ for selling. Selling is the unique greedy choice and supplies only the regression pair $(0,0)$, so the estimate stays zero in every episode. The optimal policy waits and earns $1/2$, giving the modified learner exactly $K/4$ regret. The feature map in this example determines the reference kernel through normalization, so a planner enforcing that information avoids the failure. The counterexample therefore establishes a failure of bonus deletion for the specified ridge-VTR estimator, without implying that optimism is necessary for every algorithm under A1L.Thank you for the clarifications.
I am happy to keep my positive score
comment
Thank you. We appreciate your constructive feedback and the time you took to review our revisions. Your comments have helped us improve the presentation and clarify the theoretical contributions of the paper.
Critical Weaknesses 1 and 2
Thank you for the feedback. The revised version includes both algorithms and makes the model assumptions and lower-bound classes explicit. The additional analysis answers the two bonus-removal questions separately.
1-Critical Weakness 1: Algorithms 1 and 2 now appear in Sections 4 and 6. Section 3 states the known reward and successor map, the admissible policy class, the budget convention, and regret against the actual-model optimum. The cap-free refinement is in Appendix D.6, and the reward-blind result is in Appendix E.3. Section 5 focuses on the reward-aware lower bound.
2-Critical Weakness 2: Scalar actions express traded volume in the execution examples. The upper-bound arguments apply to arbitrary action spaces equipped with a known measurable nonnegative cost ch(x,a,ξ), provided the remaining model assumptions, including the measurability and planning-oracle requirements, hold. Appendix C.5 replaces the influence and budget conditions by
\le \varepsilon c_h(x,a,\xi),$$ and $$\sum_{h=1}^H c_h(x_h,a_h,\xi_h)\le\bar X.$$ The budget condition holds pathwise. The capped guarantees additionally use $c_h\le c_{\max}$, with $c_{\max}$ replacing $a_{\max}$. The budget augmentation preserves the external state size and reference feature dimension. The execution lower bounds retain their stated scalar constructions. The known endogenous map supplies information needed for sample reuse: given an observed external successor, the learner can compute the corresponding endogenous successor for each candidate action. Inventory and resource-balance equations fit this assumption. Appendix C.2 also gives a random-delivery example whose observed external state determines the delivered fraction. Additional randomness can be incorporated into the observed external state, provided the augmented model remains Markov, the endogenous update is known, and the influence and complexity assumptions hold. The analysis assumes this update is known; learning it from data requires additional analysis.