突破二维分布函数的后悔率瓶颈，实现更优学习效率。
Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs
- 设计新算法，利用二元反馈优化累积分布目标
- 实现$ ilde{O}(T^{7/10})$后悔率，优于旧有$T^{3/4}$上限
- 适用于固定价格双边交易利润最大化问题
我们研究在$[0,1]^2$上对形如$g(x) imesbP_{X ilde{ m D}}(X ilde{x})$的累积分布函数相关目标进行后悔最小化，其中$g$为已知Lipschitz函数，$bD$为未知分布。每轮中，学习者选择点$x_t$并观测二元反馈$bI(X_t ilde{x}_t)$，$X_t ilde{ m D}$。本文设计的算法达到$ ilde{ m O}(T^{7/10})$后悔率，优于此前最优的$ ilde{ m O}(T^{3/4})$，表明该类目标的维度诅咒可部分缓解，尽管仍与$Ω(T^{2/3})$下界存在差距。作为应用，该技术同样可获得固定价格重复双边贸易中的利润最大化问题的$ ilde{ m O}(T^{7/10})$后悔率。
原文摘要 · Abstract (English)
We study regret minimization for learning CDF-related objectives of the form \[ g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x), \] over $[0,1]^2$, where $g$ is a known Lipschitz function and $\mathcal{D}$ is an unknown distribution. At each round $t$, the learner selects a point $x_t$ and observes the binary feedback $\mathbb{I}(X_t\le x_t)$, where $X_t\sim\mathcal{D}$. We design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$, improving over the previous best-known bound of $\widetilde{\mathcal{O}}(T^{3/4})$ and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the $Ω(T^{2/3})$ lower bound. As an application, our techniques yield the same $\widetilde{\mathcal{O}}(T^{7/10})$ regret bound for profit maximization in repeated bilateral trade with fixed prices.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。