解决延迟反馈下的上下文老虎机问题，实现近最优后悔界。
Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
- 基于在线回归预言机设计新算法，适配一般函数逼近。
- 在先进先出假设下，后悔界为 $O(\ ext{\sqrt{KT\mathcal{R}_T} + \sqrt{d_{\max} D β}})$。
- 首次给出稳定性的理论分析，适合研究在线学习与延迟反馈的学者。
我们针对存在对抗性延迟反馈的上下文多臂老虎机问题，提出最小化后悔的算法。在直接访问有限策略类 $Π$ 的前提下，获得最优期望后悔界 $O(\sqrt{KT \log |Π|} + \sqrt{D \log |Π|})$，其中 $D$ 为总延迟。主贡献是研究一般函数逼近设置下，通过访问一个在线最小二乘回归预言机 $\mathcal{O}$，在先进先出（FIFO）条件下，实现期望后悔界 $O(\sqrt{KT\mathcal{R}_T(\mathcal{O})} + \sqrt{d_{\max} D β})$，其中 $d_{\max}$ 为最大延迟，$\mathcal{R}_T(\mathcal{O})$ 为预言机的后悔上界，$β$ 为关联的稳定性参数。进一步，我们为基于 Hedge 的 Vovk 聚合预测器提供新颖的稳定性分析，作为有限函数类 $\mathcal{F}$ 上的回归预言机实现，证明其 $β \leq \log |\mathcal{F}|$，从而得到 $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{\max} D \log |\mathcal{F}|})$ 的后悔界，仅比下界 $Ω(\sqrt{KT \log |\mathcal{F}|} + \sqrt{D \log |\mathcal{F}|})$ 少一个 $\sqrt{d_{\max}}$ 因子。
原文摘要 · Abstract (English)
We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over $K$ actions in the presence of delayed feedback, a scenario where loss observations arrive with delays chosen by an adversary. As a preliminary result, assuming direct access to a finite policy class $Π$ we establish an optimal expected regret bound of $ O (\sqrt{KT \log |Π|} + \sqrt{D \log |Π|)} $ where $D$ is the sum of delays. For our main contribution, we study the general function approximation setting over a (possibly infinite) contextual loss function class $ \mathcal{F} $ with access to an online least-square regression oracle $\mathcal{O}$ over $\mathcal{F}$. In this setting, we achieve an expected regret bound of $O(\sqrt{KT\mathcal{R}_T(\mathcal{O})} + \sqrt{ d_{\max} D β})$ assuming FIFO order, where $d_{\max}$ is the maximal delay, $\mathcal{R}_T(\mathcal{O})$ is an upper bound on the oracle's regret and $β$ is a stability parameter associated with the oracle. We complement this general result by presenting a novel stability analysis of a Hedge-based version of Vovk's aggregating forecaster as an oracle implementation for least-square regression over a finite function class $\mathcal{F}$ and show that its stability parameter $β$ is bounded by $\log |\mathcal{F}|$, resulting in an expected regret bound of $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{\max} D \log |\mathcal{F}|})$ which is a $\sqrt{d_{\max}}$ factor away from the lower bound of $Ω(\sqrt{KT \log |\mathcal{F}|} + \sqrt{D \log |\mathcal{F}|})$ that we also present.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。