高维上下文博弈中实现无遗憾学习，突破传统方法局限
High-dimensional Nonparametric Contextual Bandit Problem
- 引入上下文分布的随机假设，提升高维场景建模能力
- 当维度与样本数相当时，仍可实现无遗憾学习
- 提出宽松遗憾率分析，适合对实时性要求高的应用
我们研究具有大特征空间的核化上下文赌博问题。该问题包含 $K$ 个动作，预测者目标是通过学习上下文与回报之间的关系来最大化累积回报，适用于个性化在线广告和推荐系统等决策场景。核化上下文赌博问题扩展了线性上下文赌博问题，具备更强的建模灵活性。现有方法在使用高斯核时，当特征维度为 $Ω("log T)$ 时，会得到平凡的 $O(T)$ 上界。为此，我们对上下文分布引入随机假设，证明即使维度增长至与样本数相当，仍可实现无遗憾学习。此外，我们分析了宽松遗憾（lenient regret），允许每轮遗憾最多为 $Δ>0$，并推导出其遗憾率关于 $Δ$ 的表达式。
原文摘要 · Abstract (English)
We consider the kernelized contextual bandit problem with a large feature space. This problem involves $K$ arms, and the goal of the forecaster is to maximize the cumulative rewards through learning the relationship between the contexts and the rewards. It serves as a general framework for various decision-making scenarios, such as personalized online advertising and recommendation systems. Kernelized contextual bandits generalize the linear contextual bandit problem and offers a greater modeling flexibility. Existing methods, when applied to Gaussian kernels, yield a trivial bound of $O(T)$ when we consider $Ω(\log T)$ feature dimensions. To address this, we introduce stochastic assumptions on the context distribution and show that no-regret learning is achievable even when the number of dimensions grows up to the number of samples. Furthermore, we analyze lenient regret, which allows a per-round regret of at most $Δ> 0$. We derive the rate of lenient regret in terms of $Δ$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。