提出高效算法，兼顾对抗与随机环境下的最优表现。
Best-of-Both Worlds for linear contextual bandits with paid observations
- 基于正则化跟踪框架与矩阵几何重采样设计新算法
- 对抗环境下达到最优的 $T^{2/3}$ 风险，随机环境下为对数级
- 适合需在不确定环境中稳定决策的研究者
研究线性上下文老虎机中带付费观测的问题：每轮学习者选择动作以最小化损失，并可支付固定成本观测任意臂的真实损失。基于带有高效估计器的跟随正则化领导者框架，我们引入一种计算高效的“双优”（Best-of-Both-Worlds, BOBW）算法。该算法在对抗性设定下实现 $Θ(T^{2/3})$ 的极小最大风险，而在（被污染的）随机情形下保证多项式对数级风险。方法借鉴了 extcite{BOBWhardproblems} 对“难题”的框架，采用针对本设定定制的分析技术。
原文摘要 · Abstract (English)
We study the problem of linear contextual bandits with paid observations, where at each round the learner selects an action in order to minimize its loss in a given context, and can then decide to pay a fixed cost to observe the loss of any arm. Building on the Follow-the-Regularized-Leader framework with efficient estimators via Matrix Geometric Resampling, we introduce a computationally efficient Best-of-Both-Worlds (BOBW) algorithm for this problem. We show that it achieves the minimax-optimal regret of $Θ(T^{2/3})$ in adversarial settings, while guaranteeing poly-logarithmic regret in (corrupted) stochastic regimes. Our approach builds on the framework from \cite{BOBWhardproblems} to design BOBW algorithms for ``hard problem'', using analysis techniques tailored for the setting that we consider.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。