AI Insight
This paper addresses linear contextual bandits where observing feedback incurs a cost, proposing two algorithms that perform well in both adversarial and stochastic settings. The first algorithm (Agg-SPB) achieves T^(2/3) regret in adversarial cases and logarithmic regret in stochastic cases, while the second (CE-SPB) maintains similar adversarial guarantees but achieves polylogarithmic stochastic regret without requiring certain restrictive assumptions about context distribution. Both algorithms can handle corrupted stochastic environments with explicit performance guarantees.
Why it matters
This research has practical implications for online decision-making systems where obtaining feedback is expensive, such as clinical trials, recommendation systems, or A/B testing platforms. The algorithms' ability to automatically adapt to unknown environment types without manual tuning could reduce costs while maintaining near-optimal performance across different real-world scenarios.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
Abstract: We study linear contextual bandits with paid observations, where at each round the learner observes a context, selects an action, and may pay a fixed cost to observe feedback from a subset of arms. We propose two Follow-the-Regularized-Leader algorithms with Best-of-Both-Worlds guarantees. The first, Agg-SPB, extends the SPB-matching framework of Tsuchiya and Ito (2024) by aggregating context-dependent stability terms, achieving the characteristic $T^{2/3}$ adversarial regret rate and logarithmic dependence on $T$ in stochastic environments. The second, CE-SPB, combines arm-dependent observation probabilities with an entropy-adaptive learning rate inspired by Kuroki et al. (2024). It achieves an entropy-adaptive $widetilde{O}(T^{2/3})$ adversarial guarantee and polylogarithmic stochastic regret, while avoiding the minimum-context-mass dependence arising in the stochastic analysis of Agg-SPB. Both algorithms further extend to corrupted stochastic environments with explicit corruption-dependent guarantees. These results establish that logarithmic stochastic regret is compatible with the $T^{2/3}$ adversarial regime for linear contextual bandits with paid observations, while highlighting a tradeoff between sharper horizon dependence in stochastic settings and path-dependent matching without explicit minimum-context-mass dependence.
Source: Best-of-Both Worlds for linear contextual bandits with paid observations