Efficient learning with partial feedback and contextual information
Efficient contextual partial monitoring with general function approximation
Machine Learning
Summary
This paper addresses how a computer can learn to make good decisions when it only receives limited clues about the results of its actions, and when it also observes additional helpful information (called context) before deciding. The authors improve on a previous method to make it faster and more practical by creating simpler rules for exploring options that still guarantee good learning results. They test their approach on example problems, including deciding when to pass questions from a weak to a strong language model, and show it works better than earlier methods.
What this means in practice
- •For machine learning engineers: Create adaptive systems that decide using limited feedback and contextual data efficiently, like routing queries between models based on context and feedback signals.
- •For call center technology teams: Implement smarter escalation systems that send customer queries from automated assistants to human agents using partial feedback and contextual clues.
Authors
Kapilan Balagopalan, Hao Qin, Kwang-Sung Jun, Chicheng Zhang
Abstract
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 $ε$-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.