arXiv:2410.17075cs.LG2024-10中稿 · ACM SIGMETRICS 202…被引 7

提出新型组合逻辑博弈框架,提升在线推荐与资源分配效率。

Combinatorial Logistic Bandits

  • 设计无方差依赖探索机制,简化算法并保证理论性能
  • 在强平滑条件下实现近最优 $ ilde{O}(d oot{T})$ regret,消除动作规模影响
  • 适用于内容推荐、动态信道分配等场景,实测表现优于基准方法

我们提出一种新框架——组合逻辑博弈(CLogB),每轮选择一组基础臂(称作超臂),每个基础臂的回报为二值,其期望服从逻辑回归参数模型,反馈由一般触发过程决定。研究涵盖满足两种光滑性条件的奖励函数,适用于在线内容分发、在线排序学习和动态信道分配等场景。首先提出简单高效的 CLogUCB 算法,采用无方差探索奖励;在 1-范数触发概率调制(TPM)光滑性条件下,达到 $ ilde{O}(d oot{κKT})$ 的后悔上界,相比之前工作提升 $ ilde{O}( oot{κ})$ 因子。随后引入方差自适应版本 VA-CLogUCB,同样在 TPM 条件下实现 $ ilde{O}(d oot{KT})$ 后悔,再优化 $ ilde{O}( oot{κ})$ 因子。在更强的触发概率与方差调制(TPVM)条件下,可进一步达到 $ ilde{O}(d oot{T})$ 的领先后悔界,完全消除对动作规模 $K$ 的依赖。此外,在上下文特征映射时间不变时,通过去除非凸优化过程提升计算效率,同时保持紧致的 $ ilde{O}(d oot{T})$ 后悔界。合成与真实数据集上的实验表明,所提算法显著优于基线方法。

原文摘要 · Abstract (English)

We introduce a novel framework called combinatorial logistic bandits (CLogB), where in each round, a subset of base arms (called the super arm) is selected, with the outcome of each base arm being binary and its expectation following a logistic parametric model. The feedback is governed by a general arm triggering process. Our study covers CLogB with reward functions satisfying two smoothness conditions, capturing application scenarios such as online content delivery, online learning to rank, and dynamic channel allocation. We first propose a simple yet efficient algorithm, CLogUCB, utilizing a variance-agnostic exploration bonus. Under the 1-norm triggering probability modulated (TPM) smoothness condition, CLogUCB achieves a regret bound of $\tilde{O}(d\sqrt{κKT})$, where $\tilde{O}$ ignores logarithmic factors, $d$ is the dimension of the feature vector, $κ$ represents the nonlinearity of the logistic model, and $K$ is the maximum number of base arms a super arm can trigger. This result improves on prior work by a factor of $\tilde{O}(\sqrtκ)$. We then enhance CLogUCB with a variance-adaptive version, VA-CLogUCB, which attains a regret bound of $\tilde{O}(d\sqrt{KT})$ under the same 1-norm TPM condition, improving another $\tilde{O}(\sqrtκ)$ factor. VA-CLogUCB shows even greater promise under the stronger triggering probability and variance modulated (TPVM) condition, achieving a leading $\tilde{O}(d\sqrt{T})$ regret, thus removing the additional dependency on the action-size $K$. Furthermore, we enhance the computational efficiency of VA-CLogUCB by eliminating the nonconvex optimization process when the context feature map is time-invariant while maintaining the tight $\tilde{O}(d\sqrt{T})$ regret. Finally, experiments on synthetic and real-world datasets demonstrate the superior performance of our algorithms compared to benchmark algorithms.

强化学习在线优化博弈论推荐系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。