解决奖励函数未知的广义线性博弈问题，提升实际决策可靠性。
Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions
- 提出STOR和ESTOR算法，处理单调递增的未知奖励函数。
- ESTOR实现近似最优的后悔率$ ilde{O}_T( oot T o oot)$，适用于时间跨度$T$。
- 扩展至高维稀疏场景，保持相同后悔率，适合真实复杂数据集。
广义线性博弈因在现实在线决策中的广泛应用而被广泛研究，但现有方法通常假设期望奖励函数已知，这一假设在实践中常不成立。若该链接函数误设，将导致所有现有算法失效。本文针对这一关键局限，提出新的广义线性博弈模型——奖励函数未知的单指标博弈（single index bandits）。首先考虑奖励函数单调递增的情形，提出两种新算法STOR与ESTOR，均在标准假设下实现良好后悔表现。值得注意的是，ESTOR在时间跨度$T$下达到近似最优的后悔界$ ilde{O}_T( oot T o oot)$。随后，将方法拓展至高维稀疏情形，并证明可基于稀疏性指数维持相同的后悔率。进一步提出对一般奖励函数无感的GSTOR算法，在高斯设计假设下建立后悔界。最后通过合成数据与真实数据集实验验证了算法的高效性与有效性。
原文摘要 · Abstract (English)
Generalized linear bandits have been extensively studied due to their broad applicability in real-world online decision-making problems. However, these methods typically assume that the expected reward function is known to the users, an assumption that is often unrealistic in practice. Misspecification of this link function can lead to the failure of all existing algorithms. In this work, we address this critical limitation by introducing a new problem of generalized linear bandits with unknown reward functions, also known as single index bandits. We first consider the case where the unknown reward function is monotonically increasing, and propose two novel and efficient algorithms, STOR and ESTOR, that achieve decent regrets under standard assumptions. Notably, our ESTOR can obtain the nearly optimal regret bound $\tilde{O}_T(\sqrt{T})$ in terms of the time horizon $T$. We then extend our methods to the high-dimensional sparse setting and show that the same regret rate can be attained with the sparsity index. Next, we introduce GSTOR, an algorithm that is agnostic to general reward functions, and establish regret bounds under a Gaussian design assumption. Finally, we validate the efficiency and effectiveness of our algorithms through experiments on both synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。