- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies a variant of bandit called online monitoring. It proposed an algorithm based on the E2D framework and prove the regret guarantee. The author also extends the E2D from online estimation oracles to just offline estimation oracles. They paper also conducts some numerical experiments to verify the algorithm.
Critical strengths
The paper develops a unified framework for contextual partial monitoring with general function approximation, covering both online and offline estimation oracles while recovering near-optimal regret rates across different observability regimes. The algorithm is simple to understand and the model is presented clearly.
Critical weaknesses
a) The paper encapsulates the difficulty of the decision-making problem into the decision-estimation coefficient. The policy that the paper use is also very similar to E2D and inverse-gap-weighting, which are all very classical. I feel that the paper is just applying these policies to a different new setting.
b) For general model classes, obtaining a tractable upper bound on the decision-estimation coefficient may itself be difficult, and access to a regression oracle does not resolve this issue. Could the authors provide concrete bounds for the applications discussed in the paper, particularly LLM routing, and clarify the resulting computational and implementation requirements?
c) Algorithm 4 trains on the previous epoch but Theorem A.2 uses the current epoch’s sample size, invalidating the bound for arbitrary schedules. Algorithm 3 also uses inconsistent values of while invoking the same lemma, leaving the dependence on unjustified. I expect the authors to explain this.
d) The discussion of offline oracle-efficient learning is incomplete. The manuscript would benefit from comparisons with three related strands: general online-to-offline estimation reductions (Foster et al., 2024); offline regression or density-estimation methods for contextual bandits and MDPs (Qian, Hu, and Simchi-Levi, 2024; Hu, Qian, and Simchi-Levi, 2026; Levy and Mansour, 2026); and structured partial-feedback problems using offline regression (Zhang and Luo, 2024; Saha and Schapire, 2025). Although these works study different settings, comparing their oracle assumptions, oracle-call complexity, feedback structures, and regret guarantees would clarify which components of OE2D.PMSide are inherited and which are genuinely new.
e) The discussion of locally observable partial monitoring is also incomplete. Since Algorithm 3 relies on neighborhood paths and local loss-difference estimation, it should be compared with earlier neighborhood-based algorithms and more recent adaptive methods (Foster and Rakhlin, 2012; Bartók, 2013; Lattimore and Szepesvári, 2019; Tsuchiya et al., 2023). Such a comparison would better clarify what is genuinely new in SquareCB.PMSide.
[1] Dylan J. Foster, Yanjun Han, Jian Qian, and Alexander Rakhlin. “Online Estimation via Offline Estimation: An Information-Theoretic Framework.” NeurIPS 2024.
[2] Jian Qian, Haichen Hu, and David Simchi-Levi. “Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff.” NeurIPS 2024.
[3] Haichen Hu, Jian Qian, and David Simchi-Levi. “Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation.” arXiv:2605.00393, 2026.
[4] Orin Levy and Yishay Mansour. “Optimal Regret for Policy Optimization in Contextual Bandits.” ICML 2026.
[5] Mengxiao Zhang and Haipeng Luo. “Contextual Multinomial Logit Bandits with General Value Functions.” NeurIPS 2024.
[6] Aadirupa Saha and Robert E. Schapire. “Efficient and Near-Optimal Algorithm for Contextual Dueling Bandits with Offline Regression Oracles.” NeurIPS 2025.
[7] Dean Foster and Alexander Rakhlin. “No Internal Regret via Neighborhood Watch.” AISTATS 2012.
[8] Gábor Bartók. “A Near-Optimal Algorithm for Finite Partial-Monitoring Games Against Adversarial Opponents.” COLT 2013.
[9] Tor Lattimore and Csaba Szepesvári. “Cleaning Up the Neighborhood: A Full Classification for Adversarial Partial Monitoring.” ALT 2019.
[10] Taira Tsuchiya, Shinji Ito, and Junya Honda. “Best-of-Both-Worlds Algorithms for Partial Monitoring.” ALT 2023.
Questions for authors
Please see the weakness part.
6 comments
Theoretical novely explanations and additional comparisons.
We sincerely thank the reviewer for their careful reading, constructive feedback, and valuable suggestions. We address the concerns point by point below. We have also revised the manuscript (mostly blue font, except for the table and figure captions) and added pointers to the appropriate revised parts below.
Question (a)
a) We address this question by explaining the motivation and key discovery behind our work.
The DMSO framework (Foster et al., 2021) provides a unified approach to sequential decision-making problems, including bandits, partial monitoring, graph-feedback bandits, and reinforcement learning, by finding an exploration distribution that solves a minimax optimization problem at every decision step. However, solving such an optimization problem is intractable in general, since the objective function is oftentimes not convex-concave (See Section 2.3, Lines 246-250 in our paper).
A natural question is: Can we bypass this potentially expensive optimization with a simple, computationally efficient exploration strategy? For contextual bandits, SquareCB (Foster & Rakhlin, 2020) achieves this through inverse-gap weighting (IGW). However, extending this approach beyond bandits is not straightforward. For example, SquareCB.G(Zhang et al., 2023) uses constrained optimization for graph-feedback bandits rather than simply applying standard IGW.
Motivated by this gap, for partial monitoring in the locally observable setting, we first constructed a coverage term specialized for partial monitoring (please see section 3 lines 265-305); afterwards, we initially developed a novel exploration strategy combining IGW with a water-transfer operator (Lemma G.5 in the updated manuscript). The inspiration for the water-transfer component came from a proof technique in Lattimore & Szepesvari (2020), whose algorithm instead relies on min-max optimization. We discuss this distinction in detail in Appendix A1 (Additional Discussions on Important Related Works) of the revised manuscript.
Perhaps surprisingly, we subsequently discovered that IGW allocation alone satisfies the key properties required from the water-transfer operator, rendering that additional step unnecessary. This establishes that simple IGW allocation suffices for non-degenerate, locally observable partial monitoring games, as highlighted in Lines 377–380 of the revised manuscript. This is established by the careful construction of our relaxed DEC objective , whose approximate minimizers also certify a low DEC (Please see Remark 3 of Appendix C of the revised manuscript). The simple functional form of (greediness plus coverage) paves the way for our design of efficient exploration strategies.
Furthermore, eliminating the water-transfer operator improves the bound by a factor of compared with the corresponding bound of Lattimore & Szepesvari (2020). We view the simplicity of our exploration rule (and its procedural similarity with exploration rules used in other problems such as contextual bandits) as an advantage rather than a drawback. Please take a look at Table 3 in Appendix A3 of the revised manuscript.
Finally, the discrepancy involving and in the analysis of our offline oracle-efficient algorithms arose because those expressions had not been updated following our discovery that the water-transfer operator was unnecessary. We thank the reviewer for identifying this inconsistency and have corrected it in the revised manuscript.
- Dylan J. Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. Proceedings of the International Conference on Machine Learning (ICML), 2020.
- Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The Statistical Complexity of Interactive Decision Making. CoRR, abs/2112.1, 2021.
- Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pp. 2488–2515. PMLR, 2020.
- Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical contextual bandits with feedback graphs. Advances in Neural Information Processing Systems.
Theoretical novely explanations and additional comparisons.
Question (b)
Computational complexity. Our algorithmic contribution is to design efficient exploration rules that can approximately solve the minimax optimization problem in DEC. SquareCB.PMSide and -Greedy.PMSide efficiently construct exploration distributions with provably small for non-degenerate locally observable and globally observable games, respectively. These guarantees also yield DEC bounds (Remark 3, Appendix C in the updated manuscript)
Statistical complexity. The respective bounds are (Lemma 3.1) and (Lemma 3.2 in the updated manuscript), suppressing game-dependent factors. With polylogarithmic estimation regret, these yield and regret, matching the minimax horizon exponents for the corresponding easy and hard classes (Bart´ok et al., 2011; Lattimore & Szepesv´ari, 2020). Thus, our computationally efficient exploration rules retain the optimal horizon dependence without exact minimax optimization.
Hence, for the different model classes we used (MLP-10, HGB-15, linear logistic and ridge regression), we just need the outcome distribution by fitting those models to the observed feedback. The rest is simple -greedy and IGW allocation.
Question (c) The choice in Algorithm 3 is correct, yielding the bound,
Theorem A.2 contained a typographical error involving an additional factor of , which we have corrected in the revised manuscript. In fact, this is the place where we shaved off an additional factor by removing the water-transfer operator (Lemma G.5 in the updated manuscript) from the IGW allocation. We accidentally forgot to migrate this to the offline section. We thank the reviewer for identifying this discrepancy.
Additionally, in Lines 1569--1573, the correct expression should be \frac{Reg_{\{Off}}^{\{H}}(\{Q},\tau_{i-1}-\tau_{i-2})} {\tau_{i-1}-\tau_{i-2}}.
We have also corrected this indexing typo. We emphasize that these corrections do not affect the main theoretical conclusions of our work.
Question (d)
We have added a comprehensive comparison with existing offline-oracle-based methods in Appendix~D.3 (Comparison with Other Offline-Oracle-Based Methods) of the revised manuscript. To the best of our knowledge, OE2D.PMSide is the first offline-oracle-based framework specifically designed for contextual partial monitoring.
In short, our design of OE2D.PMSide algorithm is perhaps closest to the third line of work (Zhang and Luo, 2024; Saha and Schapire, 2025) pointed out by the reviewer, in that it proceeds in epochs, and for each epoch it uses the offline oracle to learn a predictor for the outcome distribution given the context, and uses it to compute a distribution that simultaneously achieves low regret and good coverage.
Such an approach has also been used in earlier works of FALCON(Simchi-Levi & Xu, 2022) and its linear variant~(Xu & Zeevi, 2020)for contextual bandit problems. While these works may be regarded as contextual partial monitoring with specific loss and observation matrices, none of them addresses contextual partial monitoring with general loss and observation matrices like ours.
Question (e)
SquareCB.PMSide uses a simple IGW-based probability allocation for non-degenerate, locally observable games. The neighborhood graph and tree structures are used only in the proof, not in the action-selection procedure. This contrasts with the more elaborate action-selection procedures of many prior algorithms.
We provide a detailed comparison with ExO(Lattimore & Szepesv´ari, 2020) (Appendix A.1) and E2D(Foster et al., 2021)(Appendix A.2), two closely related approaches, in Appendix~A (Additional Discussions on Important Related Works) of the revised manuscript. We have also updated discussions on other methods in Appendix A.3: Broader Comparison for Locally Observable Games and summarized all of them in Table 3 (algorithmic approaches) and Table 4 (guarantees and properties).
We sincerely appreciate the reviewer's constructive feedback and careful examination of our theoretical results. We hope these clarifications and revisions adequately address the concerns raised, and we welcome any further questions or suggestions.
- Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Minimax regret of finite partial-monitoring games in stochastic environments. In Sham M. Kakade and Ulrike von Luxburg (eds.), Proceedings of the 24th Annual Conference on Learning Theory.
- David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.
- Yunbei Xu and Assaf Zeevi. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits.
Dear Reviewer,
We are actively working on preparing rebuttals addressing your concerns and revising the manuscript based on your suggestions. We will update you soon.
Meanwhile, please feel free to take a look at the additional experiments in the revised manuscript and the rebuttals to the previous 2 reviewers. Thank you for your patience.