arXiv:2501.18359stat.MLcs.LG2025-01ICML被引 6

提出可处理无限维分布的在线决策框架,突破传统方法的无限后悔瓶颈。

Contextual Online Decision Making with Infinite-Dimensional Functional Regression

  • 用函数基重构上下文相关累积分布函数,实现对整体分布的直接学习。
  • 在多项式特征值衰减率γ下,后悔上界为T^(3γ+2)/(2(γ+2)),最优可达T^(2/3)。
  • 适用于带分布约束的在线风险控制、多臂赌博机等场景,适合研究者参考。

上下文序列决策问题在机器学习中至关重要,涵盖多臂赌博机、序贯假设检验和在线风险控制等应用,常需期望、方差、分位数等统计量。本文提出一种通用可接受算法框架,直接学习未知分布全貌而非单一统计量,显著提升难度因回归维度为不可数无穷。为此,提出高效无限维函数回归算子,将每个数据点建模为上下文依赖的累积分布函数(CDF)基函数组合。分析表明,设计积分算子的特征值序列衰减速率决定回归误差与效用后悔率。当特征值呈阶数1/γ≥1的多项式衰减时,后悔上界为 ilde{/mathcal{O}}(T^{(3γ+2)/(2(γ+2))})。取γ=0时,恢复有限维情形最优后悔率,并在更强指数衰减假设下仍保持最优。此外,提供计算积分算子特征值序列的数值方法,支持框架实际应用。

原文摘要 · Abstract (English)

Contextual sequential decision-making problems play a crucial role in machine learning, encompassing a wide range of downstream applications such as bandits, sequential hypothesis testing and online risk control. These applications often require different statistical measures, including expectation, variance and quantiles. In this paper, we provide a universal admissible algorithm framework for dealing with all kinds of contextual online decision-making problems that directly learns the whole underlying unknown distribution instead of focusing on individual statistics. This is much more difficult because the dimension of the regression is uncountably infinite, and any existing linear contextual bandits algorithm will result in infinite regret. To overcome this issue, we propose an efficient infinite-dimensional functional regression oracle for contextual cumulative distribution functions (CDFs), where each data point is modeled as a combination of context-dependent CDF basis functions. Our analysis reveals that the decay rate of the eigenvalue sequence of the design integral operator governs the regression error rate and, consequently, the utility regret rate. Specifically, when the eigenvalue sequence exhibits a polynomial decay of order $\frac{1}γ\ge 1$, the utility regret is bounded by $\tilde{\mathcal{O}}\Big(T^{\frac{3γ+2}{2(γ+2)}}\Big)$. By setting $γ=0$, this recovers the existing optimal regret rate for contextual bandits with finite-dimensional regression and is optimal under a stronger exponential decay assumption. Additionally, we provide a numerical method to compute the eigenvalue sequence of the integral operator, enabling the practical implementation of our framework.

在线决策函数回归后悔界分布学习

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