享受多项逻辑回归赌博中的非线性

于红博

摘要: 我们考虑多项式逻辑赌博问题，这是一个变体，其中学习者通过选择行动与环境进行交互，以最大化基于多种可能结果的概率反馈的预期奖励。在二元设置中，最近的研究集中于理解逻辑模型的非线性（Faury等，2020年；Abeille等，2021年）的影响。他们引入了一个问题相关的常数$\kappa_* \geq 1$，在某些问题参数上可能呈指数增长，并且由Sigmoid函数的导数捕捉到。它包含了非线性，并将现有的回报保证从$O(d\sqrt{T})$改进到$O(d\sqrt{T/\kappa_*})$，其中$d$是参数空间的维度。我们将他们的分析扩展到多项式逻辑赌博框架，使其适用于具有超过两个选择的复杂应用，例如强化学习或推荐系统。为了实现这一点，我们将$\kappa_*$的定义扩展到多项式设置，并提出一种利用问题非线性的高效算法。我们的方法产生一个关于问题的依赖性遗憾界的阶$ \widetilde{\mathcal{O}}( R d \sqrt{{KT}/{\kappa_*}})$，其中$R$是奖励向量的范数，$K$是结果的数量。这超过了现有最佳保证的阶$ \widetilde{\mathcal{O}}( RdK \sqrt{T} )$。此外，我们提供了一个$\Omega(Rd\sqrt{KT/\kappa_*})$的下限，表明我们的算法是极小极优的，并且我们对$\kappa_*$的定义是最优的。

更新时间: 2025-10-08 15:15:45

领域: stat.ML,cs.AI,cs.LG,math.ST,stat.TH

下载: http://arxiv.org/abs/2507.05306v2