acceptodds
Under review as a conference paper at ICLR 2027

Efficient contextual partial monitoring with general function approximation

Abstract

We study finite stochastic partial monitoring (PM) games with side information, a paradigm of sequential learning with partial feedback. On each round , both player and environment observe a context and player chooses an action and environment simultaneously chooses an outcome. The player neither observes the outcome nor the loss; instead they only observe a feedback symbol which is partially informative about the outcome. We utilize the Estimation-to-Decisions (E2D) meta-algorithm of foster21thestatistical to design \edpm, a computationally-efficient framework for contextual partial monitoring, which uses an online regression oracle to efficiently estimate the outcome distributions based on historical (context, action, feedback symbol) tuples. Since the exploration rule given by the original E2D algorithm is intractable to compute, we propose two computationally-efficient exploration rules that achieve optimal regret orders in in globally and locally observable settings, respectively. We show that a variant of \edpm named \oedpm can be combined with offline regression oracles to give an efficient algorithm with optimal regret when the contexts are drawn independently from a fixed distribution. We evaluate our algorithm on a synthetic label-efficient prediction game and an LLM routing task, in which a learner decides from prompt, uncertainty and internal state features whether to escalate a query from a weak model to a strong one. We show that our method has superior performance than prior approaches.

Primary area:
learning theory
Keywords:
partial monitoring, online oracles, sequential decision making

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_H2P1OpenReview ↗
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 κ\kappa while invoking the same lemma, leaving the dependence on kk 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

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.

AuthorsOpenReview ↗

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 VγV_{\gamma}, whose approximate minimizers also certify a low DEC (Please see Remark 3 of Appendix C of the revised manuscript). The simple functional form of VγV_{\gamma} (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 kk 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 κ\kappa and Vγ\mathcal{V}_{\gamma} 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.

  1. 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.
  2. Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The Statistical Complexity of Interactive Decision Making. CoRR, abs/2112.1, 2021.
  3. Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pp. 2488–2515. PMLR, 2020.
  4. Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical contextual bandits with feedback graphs. Advances in Neural Information Processing Systems.
AuthorsOpenReview ↗

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 ϵ\epsilon-Greedy.PMSide efficiently construct exploration distributions with provably small VγV_{\gamma} 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 VγV_{\gamma} bounds are O(γ−1)O(\gamma^{-1}) (Lemma 3.1) and O(γ−1/2)O(\gamma^{-1/2}) (Lemma 3.2 in the updated manuscript), suppressing game-dependent factors. With polylogarithmic estimation regret, these yield O~(T)\widetilde{O}(\sqrt{T}) and O~(T2/3)\widetilde{O}(T^{2/3}) 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 q^t\hat{q}_t by fitting those models to the observed feedback. The rest is simple ϵ\epsilon-greedy and IGW allocation.

Question (c) The choice κ=γ8km2\kappa = \frac{\gamma}{8km^2} in Algorithm 3 is correct, yielding the bound, Vγ(q^,p)≤O(m2k2γ)\mathcal{V}_{\gamma}(\hat{q},p) \leq O\left(\frac{m^2k^2}{\gamma}\right)

Theorem A.2 contained a typographical error involving an additional factor of kk, which we have corrected in the revised manuscript. In fact, this is the place where we shaved off an additional kk 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.

  1. 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.
  2. David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.
  3. Yunbei Xu and Assaf Zeevi. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits.
Reviewer_7viTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies finite stochastic contextual partial monitoring. The learner observes a context and chooses an action. It then sees a feedback symbol. The paper assumes a realizable class of outcome distributions and separates learning into feedback-distribution prediction and exploration.

E2D.PMSide uses coverage to connect these tasks. Coverage measures whether data collected under one action distribution can support comparisons with other actions. The algorithm does not optimize coverage exactly at each round. It gives two simple rules that control the relevant objective. The globally observable case uses epsilon-greedy. The locally observable case uses inverse-gap weighting. The local analysis follows paths of decreasing predicted loss in the action neighborhood graph.

Critical strengths
  1. The estimation interface targets observable feedback distributions. It does not require the hidden outcome distribution to be fully identifiable. This matches the information available in PM.
  2. Both exploration rules are simple to compute. They avoid solving the original minimax problem or the nonconvex coverage optimization exactly at every round.
  3. The framework explicitly connects prediction error to decision regret. For iid contexts, the offline variant also reduces oracle calls.
  4. The experiments demonstrate linear logistic and nonlinear HGB predictors within the same exploration framework. They report specific comparisons with several baselines.
Critical weaknesses
  1. The globally observable branch has limited experimental coverage. The experiments, including Appendix A.4, focus on locally observable games. They do not test a hard game that is globally observable but not locally observable. A small hard-game experiment would help assess the epsilon-greedy branch.
  2. The practical computational benefit is not quantified. The appendix gives implementation details, including update frequency and training parameters. It does not provide a measured runtime comparison. Reporting exploration time and predictor training time separately would make the computational benefit easier to assess.
Questions for authors

none

3 comments
AuthorsOpenReview ↗

Additional experiments and justification

We sincerely thank the reviewer for recognizing the strengths of our paper and for their encouraging assessment. We address the identified weaknesses as follows:

Hard game example: We have included an example of a hard game by setting the expert cost 1) lower-cost regime c={0.5,0.6,0.7,0.8,0.9,1}c = \{ 0.5, 0.6, 0.7, 0.8, 0.9, 1\} and a higher-cost regime c={1,2,5,10}c = \{ 1, 2, 5, 10\} in Appendix E of the updated manuscript. (Please find the updated results in blue font in the revised manuscript.)

Computational efficiency: We have added the average run times in the updated manuscript. (Please find the updated results in blue font in the revised manuscript.)

We hope these additions adequately address the reviewer's concerns. We sincerely appreciate their constructive feedback and welcome any further questions or suggestions.

Thank you!

AuthorsOpenReview ↗

A gentle follow up

Dear Reviewer,

Thank you for your positive assessment of our work.

As the discussion period closes today, we wanted to confirm briefly that both of your requests are addressed in the revised PDF. We added the requested experiments for globally observable games, extending the expert-query cost to c≥0.5c \geq 0.5 and evaluating eps-Greedy.PMSide across both the lower-cost (c∈{0.5,0.6,0.7,0.8,0.9,1}c \in \{0.5, 0.6, 0.7, 0.8, 0.9, 1\}) and higher-cost (c∈{1,2,5,10}c \in \{1, 2, 5, 10\}) regimes. We also now report computational cost directly, as mean runtime per trial for every method and model class, in the runtime table of the revised PDF.

We remain happy to discuss anything still unclear.

Thank you for adding the globally observable game experiments and runtime comparisons. I maintain my rating.

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

This paper is about the problem of finite stochastic partial monitoring (PM) with side information (also called contextual PM). More specifically, the authors focus on the case where general function approximation is required for mapping contexts to outcomes. Building on the pre-existing Estimation-to-Decisions (E2D) meta-algorithm, the authors introduce the E2D.PMSide framework, which reduces contextual PM to online regression. They further use the framework to instantiate two algorithms, SquareCB.PMSide and epsilon-Greedy.PMSide, which are computationally efficient and can handle general function approximation. They provide associated regret analyses and conduct empirical experiments showing that the proposed algorithms are competitive with existing methods.

Critical strengths
  1. Important problem

Despite being relevant in several applications (as those stated in the paper), the PM problem has been mostly tackled from a theoretical perspective in the literature, with few computationally efficient strategies that could be considered in practice. This paper does a good job at formulating the PM problem in concrete applications and proposes a novel perspective for deriving contextual PM methods that are both computationally efficient while maintaining regret guarantees, bridging the gap between theory and practice. The experiments are also instantiated in the real-world example of LLM routing. This can help make the problem more approachable by practitioners without sacrificing the rigour of the paper (everything is formally defined, as expected from a paper on this topic).

  1. Versatile approach with theoretical guarantees and empirical demo

The authors adapt an existing meta-algorithm (E2D) to the contextual PM problem in such a way that it remains tractable. This enables them to derive algorithms along with their theoretical guarantees (regret upper bounds) within this framework. The theoretical results are discussed in perspective of existing results (problem lower bounds and existing upper bounds for other methods), providing a rather complete picture that helps positioning the contribution. The authors support their theoretical results with empirical experiments (many PM papers don’t even have experiments).

Critical weaknesses
  1. Choice of baselines

It is unclear how baselines were chosen for the two tasks (see questions). As RandCBPSide applies to the apple tasting problem, it is surprising that it is only used for the label efficient task. Moreover, there are other approaches, notably based on neural networks, that have been proposed for the (contextual) label efficient game. It seems like they should be considered, especially if this paper is focused on general function approximation.

  1. Experiments

One could argue that 10-dimensional contexts (as used in the label efficient game) are quite toy and that richer contexts (e.g., images) could have been considered to make the label efficient experiment closer to its potential applications (e.g., active learning [1]). Additionally, the proposed methods performs mostly on par with existing methods (ETC + HGB in Fig. 1a, RandCPBSide in Fig. 1b). If computation efficiency is where the proposed methods win (e.g., against RandCPBSide), it should be precisely documented (e.g., by reporting FLOPS). It is mentioned that ETC performs competitively due to the problem configuration (low amount data vs dimension size). Experiments in a setting where the proposed methods have a clear advantage would be important to assess when they should be used.

[1] Heuillet et al. (2024), “Neural active learning meets the partial monitoring framework”, UAI.

Minor:

  • Typo (L227): “For finite” should be “for finite”.
Questions for authors

Q1) The NeuralCBP [1] method appears to be appropriate for the contextual PM with general function approximation, unlike CBPSide and RandCBPSide which are limited to linear logistic. Could you explain why NeuralCBP should not be considered as part of the baselines?

Q2) Why is RandCBPSide only considered for the label efficient setting and not for the LLM routing example (apple tasting, easier PM game)?

Q3) Can you provide the difference in FLOPS for the benchmarked methods in the considered experimental settings?

[1] Heuillet et al. (2024), “Neural active learning meets the partial monitoring framework”, UAI.

4 comments
AuthorsOpenReview ↗

Additional experiments and justifications

We sincerely thank the reviewer for recognizing the key strengths of our paper and appreciating our efforts on the empirical side.

Critical Weaknesses

1. Choice of baselines:

We initially omitted RandCBPSide (Heuillet et al., 2024) from the LLM routing experiments because the original algorithm considers a linear model class with ridge regression loss, whereas our setting involves logistic loss. Nevertheless, in response to the reviewer's request, we adapted RandCBPSide to the logistic-loss setting and included it in our comparisons. Similarly, we adapted NeuralCBP to logistic loss and added it as an additional baseline.

Please find the updated results in blue font in the revised manuscript.

2. Experiments:

Computational efficiency: To provide a quantitative comparison of computational efficiency, we now report the average runtimes for each algorithm in the updated manuscript. Please find the updated results in blue font in the revised manuscript.

BoolQ dataset: For the BoolQ dataset (over 12,000 samples), we experimented with several feature dimensions and representations, using supervised logistic-loss performance to guide the selection of the current 138-dimensional representation. We acknowledge that the relative performance of our algorithm, ETC may depend on the relationship between dataset size and feature dimension. In particular, investigating larger datasets with relatively low-dimensional contextual representations would provide further insight into the regimes where our algorithm offers advantages over ETC. We consider this a valuable direction for future empirical investigation.

Questions

  1. We have added NeuralCBP as an additional baseline in the updated experiments. Thank you for pointing this out. (Please find the updated results in blue font in the revised manuscript.)

  2. As explained above, RandCBPSide was originally designed for a linear model class with ridge regression loss. We have now adapted it to logistic loss and included it in the LLM routing experiments. (Please find the updated results in blue font in the revised manuscript.)

  3. Please find the updated results in blue font in the revised manuscript.

We sincerely appreciate the reviewer's constructive feedback and have made every effort to address the concerns raised. We hope these additional results and clarifications will encourage the reviewer to reconsider their assessment.

Thank you!

Reviewer_wCbaOpenReview ↗

Clarification requested

Thank you for running the requested baselines and adding the runtimes! If I am reading this correctly, it seems like ETC performs on-par with the proposed approach on the LLM routing example, while using 200x less compute. On the LE game, RandCBPSide performs on-par with the proposed approach using 3x times more compute. Can you comment on that and the (empirical) relevance of the proposed approach in this case?

AuthorsOpenReview ↗

Comparison of RandCBPSide, ETC and SquareCB.PMSide

We thank the reviewer for taking a look at the additional results provided. Across these two experiments, we evaluate the following aspects

  1. Regret performance (total cost)
  2. Computational complexity (running time)
  3. Model compatibility (linear vs non-linear)
  4. Practicality of implementation (unknown horizon TT, larger data set)

Ours vs RandCBPSide: Although in our experiments on the label-efficient prediction game (where the linear model is well-specified), RandCBPSide performs on par with ours with more time complexity, its performance degrades when the true model is not well specified (LLM routing; non-linear underlying model). Hence,

  1. Regret performance : on par in LE, ours wins in LLM with HGB-10 (regret), MLP-10 (regret and running time)
  2. Computational complexity: ours wins
  3. Model compatibility: ours wins

Ours vs ETC: Explore-Then-Commit algorithm explores for certain amount of its budget, then fit the model once and then commit to the best actions according to the fit model.

We speculate that the inflated performance of ETC in LLM routing is because of the following reasons:

  1. For LLM experiments, we make an estimation decision every round, but we do a model update every 32 rounds, as mentioned in the experimental details (lines 2115-2116) (this was done to save time on experiments). This has a negative effect on all other adaptive algorithms; however, this does not affect ETC.
  2. High dimension-to-sample ratio in LLM routing (138 vs 12000)
  3. ETC in bandit explore uniformly over all the actions. However, when we modified it for the LLM routing and LE games, we made it to explore only the informative action. This provide another practical advantage in our implementation.

Although in LLM routing ETC performs on par, its performance fails in the LE game where we have a large horizon and update the model every round. Furthermore, ETC needs to know TT beforehand to decide its exploration budget.

Hence,

  1. Regret performance : on par in LLM , ours wins in LE
  2. Computational complexity: ETC wins Just fits the model once, so with increasing TT, the per round time decreases.
  3. Practicality of implementation: ours wins ETC needs to know TT beforehand to decide its exploration budget.

So with all the provided advantages (reasons 1,2,3), ETC's performance is not impressive.

Apart from that, we would also like to add another merit of our algorithms: Compatibility with Offline policy evaluation

Offline evaluation (Precup, 2000) is a technique used to evaluate a target policy from data collected by a behavioral/logging policy. There are many techniques available, the most popular being IPW (Inverse propensity weighting) (Horvitz and Thompson, 1952). For example, given the logged data $ (A_t, p_t(A_t), \sigma_t)_{t=1}^{T}$, where pt(At)p_t(A_t) is the probability of sampling arm AtA_t from the logging policy, the IPW score for the uniform policy (target policy) can be defined as

IPW score=1T∑t=1TGt(At,σt)k⋅pt(At)\text{IPW score} = \frac{1}{T} \sum_{t=1}^{T} \frac{\mathcal{G}_t(A_t, \sigma_t )}{k \cdot p_t(A_t)}

[Lattimore & Szepesvári, 2020, Horvitz and Thompson, 1952]

For IPW to work, we should have 1) computation of accurate probability assigned for each action at each round; 2) it must assign non-zero probability for each action at each round. Our algorithm SquareCB.PMSide is offline policy evaluation friendly by construction, while ETC is clearly not (ETC chooses a single arm every round with probability of 1). Even with RandCBPSide, we speculate some arms might get assigned probabilities that are too close to zero, making IPW estimators have a large variance.

Hence, on the whole, across all these evaluated aspects, SquareCB.PMSide strikes the best balance. Please let us know if you have any more questions.

  1. Precup, D. Eligibility traces for off-policy policy evaluation. Proceedings of The International Conference on Machine Learning (ICML), pages 759–766, 2000

  2. Horvitz, D. G. and Thompson, D. J. A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association, 47 (260):663–685, 1952.

  3. Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pp. 2488–2515. PMLR, 2020.

AuthorsOpenReview ↗

A gentle follow up

Dear Reviewer,

We wanted to follow up briefly on our response, as the discussion period closes today.

On the ETC comparison: the LLM routing benchmark favours ETC on three separate counts (points 1–3 above), and even with all three it only draws level with SquareCB.PMSide; it does not outperform our method on either experiment.

Across the five aspects we evaluated, neither baseline outperforms SquareCB.PMSide on more than one: RandCBPSide on none, ETC only on runtime, which follows directly from its fitting a single model.

If these responses resolve your concerns, we would be grateful if you would consider raising your score. We remain happy to discuss anything still unclear.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of contributions for the Area Chair

Dear Area Chair,

We summarise our contributions and their status following the discussion period.
  1. To our knowledge, ours are the first computationally and oracle-efficient algorithms for contextual partial monitoring with general function approximation. The algorithm of Foster et al. (2022) is oracle-efficient, but a direct implementation is not known to be computationally tractable.

  2. In establishing this, we show that a simple inverse-gap-weighting (IGW) allocation already guarantees optimal regret for non-degenerate locally observable games. IGW was previously known to suffice only for bandit problems, and every prior partial monitoring algorithm relies on a comparatively complex probability-redistribution mechanism. Table 3 of the revised manuscript compares these mechanisms directly.

  3. We further extend the algorithms to operate with an offline regression oracle, through a construction of the coverage term that avoids any dependence on q^t\hat{q}_t. To our knowledge, this is the first offline oracle-efficient algorithm for contextual partial monitoring; Table 5 situates it among offline oracle-based algorithms in adjacent settings.

  4. Alongside the theory, we report experiments on two problems, LLM routing and a label-efficient prediction game. Across the aspects evaluated, no baseline outperforms SquareCB.PMSide on more than one of them. As Reviewer wCba noted, many partial monitoring papers include no empirical evaluation at all.

No reviewer has raised a concern about the correctness of our results. The concerns that were raised have been addressed in our responses and in the revised manuscript, which adds experiments for globally observable games, additional baselines for LLM routing, a runtime comparison across all methods and model classes, and an expanded comparison with prior exploration rules.

We believe this constitutes a significant, empirically supported contribution to the literature, and we kindly ask that you take it into consideration in your decision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.