Efficient contextual partial monitoring with general function approximation
Contextual partial monitoring is a sequential learning problem where the learner observes only partial feedback instead of incurred losses. The paper proposes E2D.PMSide, a computationally efficient instantiation of the Estimation-to-Decisions (E2D) meta-algorithm that reduces contextual partial monitoring to online regression. Its core contribution is replacing E2D's intractable per-round minimax exploration rule with tractable surrogates—epsilon-greedy for globally observable games and inverse gap weighting for locally observable ones—thereby achieving optimal $O(T^{2/3})$ and $O(\sqrt{T})$ regret rates. The work matters because it provides the first oracle-efficient algorithms for this setting with general function approximation and demonstrates practical benefits on LLM routing and label-efficient prediction.
The paper makes a solid theoretical contribution. It identifies that the original E2D framework's minimax exploration rule is computationally intractable for contextual partial monitoring, and it rigorously derives a coverage-based surrogate objective that admits closed-form exploration policies. The resulting E2D.PMSide framework achieves optimal regret orders in $T$ while supporting general function approximation through online regression oracles.
The reduction to online regression is principled and the regret analysis is clean. The coverage definition elegantly trades off policy evaluation error against in-distribution estimation error, and the proofs that epsilon-greedy and inverse gap weighting certify small values of the relaxed objective $\mathcal{V}_{\gamma}$ directly translate into $O(T^{2/3})$ and $O(\sqrt{T})$ regret bounds in their respective settings.
The primary gap lies between theory and practice. The regret guarantees assume access to an online outcome estimation oracle with a provable Hellinger regret bound, but the experiments employ a histogram gradient boosting predictor without establishing such a bound for that function class; the nonlinear variant's favorable results are therefore not theoretically backed. Furthermore, the analysis is restricted to non-degenerate games, and the minimax lower bounds invoked for optimality are non-contextual, leaving open whether the $k$ and $m$ dependencies are tight for general function classes.
The theoretical evidence supports the main claims: the coverage surrogate yields rigorous bounds (Theorem 3.1 and Corollaries 1--2), and the comparison to exploration-by-optimization in Table 1 fairly notes that the proposed method avoids joint optimization over estimators and policies. The empirical comparison to CBPSide and ETC is internally consistent, though the experimental protocol tunes all methods with hindsight knowledge of the loss, which limits external validity. The claim of being the first computationally efficient contextual partial monitoring algorithm with general function approximation is consistent with the surveyed literature, where prior efficient algorithms required generalized linear or linear assumptions.
The experimental setup is described with datasets, preprocessing, model configurations, and hyperparameter grids, but the code and scripts are not yet released. The BoolQ cache and synthetic generator are standard, yet the relatively small scale of 20 random permutations and the use of test-set loss for hyperparameter selection raise concerns about variance and overfitting to the benchmark. Full independent reproduction is currently blocked by the unavailability of code and data release.
We study finite stochastic partial monitoring (PM) games with side information, a paradigm of sequential learning with partial feedback. On each round $t \in [T]$, 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 Foster et al.(2021) to design E2D.PMSide, 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 $T$: in the globally observable setting, our exploration rule is based on $\epsilon$-greedy, while in the locally observable setting, our exploration rule uses inverse gap weighting (Foster & Rakhlin, 2020), which was previously only known to be effective in the bandit setting. We show that a variant of E2D.PMSide named OE2D.PMSide 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 to prior approaches.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.