Organizations: Department of Computer Science, University of Arizona, Tucson, AZ, USA · Graduate School of Artificial Intelligence, POSTECH, Pohang, South Korea
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.
Figure 1: A spanning in-tree T of the neighborhood graph (Π,E) , with root rootT ; every edge is directed toward the root. The dashed edges form pathT(a) , the directed path from action a to the root. The construction follows Lattimore & Szepesvári (2020) .
Figure 2: Comparison of algorithms for and LLM routing and Label efficient prediction game
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
ExO
Ours
Side information
No
Yes ↑
Outcome distribution
Adversarial ↑
Stochastic
Objective
optq(η)
Vγ
Minimax players
Policy vs. adversarial outcome x
Policy vs. comparator policy λ
Optimization variables
G and p jointly
p only ↑
Per-round computation
Exact solution of Equation 4
IGW for locally observable;
Appendix
Table 1: Comparison with exploration-by-optimization [ Lattimore & Szepesvári, 2020 ] . ↑ indicates a better result. NA indicates not applicable
λ∈Δ(Π)supCoverage(p,λ).
Appendix
Algorithm 4 OE2D.PMSide
Algorithm
Scaled quantity
Effect of larger s
CBPside
confidence width swi
more exploration
RandCBPside
sampled confidence width swi
more exploration
SquareCB.PMSide
IGW rate κ=sT
less exploration
ETC
exploration length sT2/3
more exploration
PG-TS
prior variance sσ0
more exploration
Appendix
Table 2: Meaning of the multiplier s for each algorithm.
Figure 3: Routing–accuracy trade-off on BoolQ. The horizontal axis reports the fraction of prompts routed to the strong model, while the vertical axis reports agreement with the cached strong-model response. Thus, points closer to the upper-left corner are preferable, as they achieve higher agreement while making fewer strong-model queries. Each marker is the mean over 20 shuffled online orders, with confidence intervals omitted for visual clarity. Along each curve, the connected markers follow increasing values ℓ01∈{1.8,2.0,2.2,2.4,2.6,2.8,3.0,3.2,3.3} . Increasing ℓ01 assigns a larger penalty to an incorrect weak-model response and therefore generally moves the policy toward more strong-model routing and higher agreement.
Figure 4: Cumulative empirical regret, measured as excess realized cost relative to the fixed five-fold cross-fitted HGB reference policy, for each value of ℓ01 . Curves show means over 20 paired random arrival orders, and shaded regions are pointwise 95% Student- t confidence intervals. Lower values are better; negative regret indicates that the online policy incurs lower realized cost than the fixed reference policy.
Figure 5: Cumulative regret against round t for each value of the information cost c , with every algorithm at its best multiplier. Shaded bands are 95% Student- t confidence intervals for the mean over 20 seeds.
We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves O~(T) policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator class. The algorithm selects one policy per geometrically growing epoch using confidence sets built cumulatively from past data, which keeps the cost of comparing adversary responses across policies logarithmic in T. We also prove a lower bound matching the T and aggregate-Eluder-dimension dependence, up to problem-dependent and logarithmic factors. Finally, we extend the framework to horizon-adaptive guarantees and adversaries with geometric fading memory.
Raman Arora
Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.
We consider online learning problems under a partial observability model capturing situations where the information conveyed to the learner is between full information and bandit feedback. In the simplest variant, we assume that in addition to its own loss, the learner also gets to observe losses of some other actions. The revealed losses depend on the learner's action and a directed observation system chosen by the environment. For this setting, we propose the first algorithm that enjoys near-optimal regret guarantees without having to know the observation system before selecting its actions. Along similar lines, we also define a new partial information setting that models online combinatorial optimization problems where the feedback received by the learner is between semi-bandit and full feedback. As the predictions of our first algorithm cannot be always computed efficiently in this setting, we propose another algorithm with similar properties and with the benefit of always being computationally efficient, at the price of a slightly more complicated tuning mechanism. Both algorithms rely on a novel exploration strategy called implicit exploration, which is shown to be more efficient both computationally and information-theoretically than previously studied exploration strategies for the problem.
Tomas Kocak, Gergely Neu, Michal Valko +1
SequeL team, INRIA Lille – Nord Europe, France · Current affiliation: Google DeepMind
We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near-optimal regret for contextual bandits with large action spaces with O(logT) calls to an offline regression oracle over T rounds, and makes O(loglogT) calls when T is known. The design of OE2D algorithm generalizes Falcon~\citep{simchi2022bypassing} and its linear reward version~\citep[][Section 4]{xu2020upper} in that it finds an action distribution that we term ``exploitative F-design'' that simultaneously guarantees low regret and good coverage, striking a balance between exploration and exploitation. Central to our regret analysis is a new complexity measure, the Decision-Offline Estimation Coefficient (DOEC), which we show is small in many settings, including bounded Eluder dimension per-context and the smoothed regret setting. We also establish a relationship between DOEC and Decision Estimation Coefficient (DEC)~\citep{foster2021statistical}, bridging the design principles of offline- and online-oracle efficient contextual bandit algorithms for the first time.