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 t ∈ [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 ε-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.
Related
- Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
- Near Optimal Finite Model POMDP Approximation of Controlled Diffusion with Partial Information
- Bounds-Constrained Finite Element Approximation of Time-Dependent Partial Differential Equations
- Weak Convergence Rates for Partial-Sum Processes of Nonlinear Stochastic Approximation
- Efficient Numerical Evaluation of Arbitrary High-order Partial Derivatives via Algebraic Decomposition
BibTeX
@misc{balagopalan2026efficient,
title = {{Efficient contextual partial monitoring with general function approximation}},
author = {Kapilan Balagopalan and Hao Qin and Kwang-Sung Jun and Chicheng Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19804},
eprint = {2610.19804},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19804},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient contextual partial monitoring with general function approximation
AU - Kapilan Balagopalan
AU - Hao Qin
AU - Kwang-Sung Jun
AU - Chicheng Zhang
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19804
UR - https://arxiv.org/abs/2610.19804
AB - We study finite stochastic partial monitoring (PM) games with side information, a paradigm of sequential learning with partial feedback. On each round t ∈ [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 ε-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.
ER -