量子算法首次解决带资源约束的多臂老虎机问题，显著降低后悔值并提速。
Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
- 利用量子查询实现资源与收益的高效获取
- 问题无关情形下后悔值提升因子达(1+√(B/OPT_LP))
- 适用于需优化资源分配的量子运筹场景
带背包的多臂老虎机（BwK）是结合随机整数规划与在线学习的核心模型。经典算法在时间跨度T下，问题无关后悔界为O(√T)，问题相关为O(log T)。本文首次研究量子计算下的BwK模型，允许通过量子预言机访问奖励与资源消耗。我们建立了问题无关与问题相关的量子后悔界：在问题无关情形，量子方法可使经典后悔界改进因子(1+√(B/OPT_LP))，其中B为预算约束，OPT_LP为BwK线性规划松弛的最优值；在问题相关情形，采用非精确量子线性规划求解器，实现问题参数上的二次改进及维度相关时间复杂度的多项式加速。相比先前仅考虑无约束多臂老虎机的量子算法，本工作首次引入资源约束，为运筹学中的量子优化提供新视角。
原文摘要 · Abstract (English)
Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent regret bound of ${O}(\sqrt{T})$ and a problem-dependent bound of ${O}(\log T)$. In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of $(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})$, where $B$ is budget constraint in BwK and $\mathrm{OPT}_{\mathrm{LP}}$ denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。