E2D.PMSide
A computationally efficient solution framework for contextual partial monitoring. Built on the E2D meta-algorithm, it estimates outcome distributions via an online regression oracle and replaces complex optimization with simple exploration rules such as epsilon-greedy and IGW, achieving optimal regret bounds under general function approximation.
Timeline (last 90 days)
The E2D.PMSide framework is the first to achieve computationally efficient solutions for contextual partial monitoring under general function approximation.
E2D.PMSide is designed based on the Estimation-to-Decisions (E2D) meta-algorithm proposed by Foster et al., using an online regression oracle to estimate the outcome distribution based on historical (context, action, feedback symbol) triples, avoiding explicit enumeration over every possible outcome distribution.
E2D.PMSide adopts an ε-greedy strategy in the globally observable setting, achieving the optimal regret bound at extremely low computational cost.
E2D.PMSide adopts an inverse gap weighting (IGW) strategy in the locally observable setting, successfully generalizing it from the bandit setting to partial monitoring.
The paper conducted experiments on two tasks, a synthetic label-efficient prediction game and LLM routing, and E2D.PMSide outperforms previous methods on both tasks.
In the LLM routing scenario, E2D.PMSide estimates the success probability of weak models via a regression oracle, achieving comparable answer quality at lower inference cost.
This work breaks the implicit assumption that 'partial monitoring can only use tabular methods', bringing general function approximation into the feasible toolbox for partial monitoring.
All Facts (7)
The E2D.PMSide framework is the first to achieve computationally efficient solutions for contextual partial monitoring under general function approximation.
50%UnverifiedE2D.PMSide is designed based on the Estimation-to-Decisions (E2D) meta-algorithm proposed by Foster et al., using an online regression oracle to estimate the outcome distribution based on historical (context, action, feedback symbol) triples, avoiding explicit enumeration over every possible outcome distribution.
50%UnverifiedE2D.PMSide adopts an ε-greedy strategy in the globally observable setting, achieving the optimal regret bound at extremely low computational cost.
50%UnverifiedE2D.PMSide adopts an inverse gap weighting (IGW) strategy in the locally observable setting, successfully generalizing it from the bandit setting to partial monitoring.
50%UnverifiedThe paper conducted experiments on two tasks, a synthetic label-efficient prediction game and LLM routing, and E2D.PMSide outperforms previous methods on both tasks.
50%UnverifiedIn the LLM routing scenario, E2D.PMSide estimates the success probability of weak models via a regression oracle, achieving comparable answer quality at lower inference cost.
50%UnverifiedThis work breaks the implicit assumption that 'partial monitoring can only use tabular methods', bringing general function approximation into the feasible toolbox for partial monitoring.
50%