在任务成功反馈受限下，实现预算分配的高效学习与低损失。
Online Budget Allocation with Censored Semi-Bandit Feedback
- 基于乐观原则设计算法，处理只在成功时才观测奖励的反馈机制。
- 在收益递减场景下，损失随时间呈多对数增长，无需人工调参。
- 首次证明最坏情况下的损失下界为Ω(K√T)，揭示问题本质难度。
我们研究在K个任务上进行随机预算分配的问题。每轮t，学习者选择分配向量X_t ∈ Δ_K。任务k的成功概率为F_k(X_{t,k})，其中F_1,…,F_K是非递减的预算-成功率曲线，成功后获得均值未知的随机奖励μ_k。学习者观察哪些任务成功，但仅在成功时观测到奖励（被截断的半盲反馈）。该模型可刻画众包支付分配或同时拍卖出价等场景，且包含随机多臂老虎机和半盲老虎机。我们设计了一种基于乐观原则的算法，在被截断的半盲反馈下运行。主要结果表明：在收益递减情形下，该算法的遗憾度随时间T呈多对数增长，无需人为调参。对于一般非递减曲线，同一算法（相同调参）达到最坏情况遗憾上界˜O(K√T)。最后，我们建立了匹配的最坏情况遗憾下界Ω(K√T)，即使在全反馈算法下也成立，凸显了在非收益递减情形下的内在困难。
原文摘要 · Abstract (English)
We study a stochastic budget-allocation problem over $K$ tasks. At each round $t$, the learner chooses an allocation $X_t \in Δ_K$. Task $k$ succeeds with probability $F_k(X_{t,k})$, where $F_1,\dots,F_K$ are nondecreasing budget-to-success curves, and upon success yields a random reward with unknown mean $μ_k$. The learner observes which tasks succeed, and observes a task's reward only upon success (censored semi-bandit feedback). This model captures, for instance, splitting payments across crowdsourcing workers or distributing bids across simultaneous auctions, and subsumes stochastic multi-armed bandits and semi-bandits. We design an optimism-based algorithm that operates under censored semi-bandit feedback. Our main result shows that in diminishing-returns regimes, the regret of this algorithm scales polylogarithmically with the horizon $T$ without any ad hoc tuning. For general nondecreasing curves, we prove that the same algorithm (with the same tuning) achieves a worst-case regret upper bound of $\tilde O(K\sqrt{T})$. Finally, we establish a matching worst-case regret lower bound of $Ω(K\sqrt{T})$ that holds even for full-feedback algorithms, highlighting the intrinsic hardness of our problem outside diminishing returns.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。