New Breakthrough in Partial Monitoring: E2D.PMSide Achieves Computationally Efficient Contextual Learning

Partial monitoring (PM) is a notoriously challenging paradigm in sequential decision-making: at each round the learner makes a choice but receives only limited feedback about the outcome—neither the true loss nor which outcome the environment actually selected is observed. When contextual information is added, the problem's complexity rises further. A recent study proposes the E2D.PMSide framework, achieving for the first time a computationally efficient solution to contextual partial monitoring under general function approximation.

Why Partial Monitoring Has Long Been Hard to Deploy

In the classic online learning setting, multi-armed bandits are already tricky enough—you only observe the reward of the chosen action. Partial monitoring goes a step further: the feedback signal may come from a symbol set different from the outcome space, and multiple rounds of information are needed to infer which actions are good.

The standard PM model assumes a finite game structure, and the learner must "decode" the mapping between feedback symbols and true outcomes through carefully designed exploration strategies. Most prior work has remained in the tabular setting (finite state and action spaces); once contextual features or large action spaces are introduced, computational complexity explodes.

This research targets exactly this pain point: can general function approximation be used to estimate outcome distributions while maintaining computational feasibility?

The feedback structure of partial monitoring can be divided into three classic settings, and understanding them is crucial to grasping the full paper. The first is global observability: although the feedback symbols differ from true outcomes, after several rounds of observation, the relative quality of any two actions can be consistently distinguished, and the learner only needs to compare at the global level. The second is local observability: a single round of feedback is insufficient to judge action quality, but repeated observations of a fixed action can gradually infer the outcome distribution, requiring more refined exploration design. The third is non-observability: no matter how one explores, certain actions cannot be distinguished, and only suboptimal regret bounds can be pursued. The division into these three settings determines what exploration rules an algorithm can adopt, and also explains why the global and local settings require separately designed ε-greedy and IGW.

E2D.PMSide: Replacing Brute-Force Search with a Regression Oracle

The research team designed E2D.PMSide based on the Estimation-to-Decisions (E2D) meta-algorithm proposed by Foster et al. The core idea is not complicated: through an online regression oracle, the outcome distribution is estimated from historical (context, action, feedback symbol) triples, avoiding explicit enumeration over every possible outcome distribution.

But there is a key obstacle here—the exploration rule of the original E2D algorithm is computationally infeasible. E2D requires solving an optimization problem involving information gain at each decision point, and under general function approximation this optimization problem is itself difficult.

The researchers' solution is to design efficient exploration rules separately for the two observability settings:

• Global observability setting: adopt an ε-greedy strategy, achieving optimal regret bounds at extremely low computational cost
• Local observability setting: adopt inverse gap weighting (IGW), a strategy previously thought to be effective only in bandit scenarios; this work successfully generalizes it to partial monitoring

This means that exploration behavior that originally required complex optimization to approximate can now be replaced by simple rules without losing the regret order.

The online regression oracle is the computational core of the E2D framework. Its input is a series of (context, action, feedback symbol) triples, and its output is an estimate of the outcome distribution. Unlike traditional methods that enumerate all possible distributions, the oracle only needs to solve a regression problem—for example, minimizing the squared error or log loss between the predicted distribution and observed feedback. This "oracle" is an abstract interface: as long as an efficient regression algorithm exists (such as linear regression, neural network training, or gradient descent), E2D can call it as a black box, thereby transforming the complex distribution estimation problem into a mature supervised learning problem. This is precisely the key to the work's ability to remain computationally efficient under general function approximation.

The relationship between information gain and ε-greedy, IGW requires further explanation. The original E2D exploration rule requires selecting at each round the action that maximizes "information gain about the optimal action," which is equivalent to solving an optimization problem involving mutual information or entropy, typically non-convex and computationally expensive under general function approximation. ε-greedy replaces precise information gain maximization with random exploration, requiring only constant time computationally; IGW allocates selection probabilities based on the currently estimated action gap—the smaller the gap, the more exploration—also avoiding explicit optimization. What both share is: using simple probabilistic rules to approximate exploration behavior that would otherwise require complex optimization, while regret analysis proves that this approximation does not lose the regret order.

Offline Oracle and the Independent Context Setting

Beyond the online scenario, the research also examines the case of contexts drawn i.i.d. In this setting, a variant of E2D.PMSide called OE2D.PMSide can combine with an offline regression oracle while still maintaining optimal regret.

The significance of this result is that offline data is far easier to obtain in practical applications than online interaction. If you have a large amount of historical interaction logs (even with incomplete feedback), OE2D.PMSide provides an efficient pathway from offline data to online decisions.

Of course, i.i.d. contexts are a strong assumption. In real scenarios, contexts often exhibit temporal correlation or distribution shift, which is a boundary the framework has not yet covered.

Validation from Synthetic Games to LLM Routing

The paper conducted experiments on two tasks. The first is a synthetic label-efficient prediction game, used to verify whether the theoretical guarantees hold in practice.

The second task is closer to engineering practice: LLM routing. The learner must decide, based on prompt features, uncertainty signals, and internal state, whether to escalate a query from a weak model to a strong model. This is a classic "partial monitoring" problem—you only see feedback on the final answer and cannot directly know whether the weak model could have handled it.

Experimental results show that E2D.PMSide outperforms prior methods on both tasks. For the LLM routing scenario, this means achieving comparable answer quality at lower inference cost—a type of efficiency optimization with direct engineering value at a time when model sizes continue to balloon.

LLM routing refers to a system choosing among multiple models of different sizes or capabilities when facing a user query, balancing cost and quality. A typical setup includes a weak model (e.g., 7B parameters) and a strong model (e.g., 70B parameters): the weak model has low inference cost but may answer incorrectly, while the strong model has high quality but is expensive. The router's task is to decide, based solely on prompt features, uncertainty signals, and internal state, whether to "escalate" a query to the strong model. Since only feedback on the final answer is observable, and one cannot directly know whether the weak model could have handled it, this is essentially a partial monitoring problem. E2D.PMSide's advantage in this scenario is that it does not need to enumerate all possible routing policies or outcome distributions, but instead estimates the weak model's success probability through a regression oracle, thereby achieving comparable answer quality at lower inference cost.

The Trade-off Between Efficiency and Generalization Remains

The most noteworthy aspect of this work is that it breaks the implicit assumption that "partial monitoring can only use tabular methods." Through the E2D framework plus efficient exploration rules, general function approximation has finally entered the feasible toolbox of PM.

But there are also areas that warrant observation. Although ε-greedy and IGW are computationally efficient, whether their worst-case performance fully matches information-theoretic lower bounds requires more follow-up work to verify the tightness of the regret order results given in the paper on practical problems. In addition, the experimental scale is relatively limited, and the specific experimental configuration and baseline choices for the LLM routing task also need to be reproduced under broader conditions.

Overall, E2D.PMSide provides an important piece of the puzzle for moving partial monitoring from theory to application. For researchers and engineers working on online learning, recommender systems, or LLM inference optimization, this is a direction worth tracking.

One-line Summary

E2D.PMSide is the first to achieve computationally efficient solving of contextual partial monitoring under general function approximation, and validates its effectiveness in an LLM routing task.

Paragraph Summary

Partial monitoring is a paradigm in sequential decision-making with extremely limited feedback, and adding context causes computational complexity to rise sharply. A recent study proposes the E2D.PMSide framework, based on the Estimation-to-Decisions meta-algorithm, which estimates outcome distributions through an online regression oracle and avoids explicit enumeration of the distribution space. To address the incomputability of the original E2D exploration rule, the work designs ε-greedy for the global observability setting and inverse gap weighting for the local observability setting, both achieving optimal regret order. Its offline variant OE2D.PMSide can also combine with an offline regression oracle, maintaining optimal regret under i.i.d. contexts. On both synthetic games and LLM routing tasks, the method outperforms prior approaches, providing an important piece for moving partial monitoring from theory to application.