在分组强化学习中，高效找出满足条件的最优选项。
Fixed-Budget Constrained Best Arm Identification in Grouped Bandits
- 设计新算法FCSR，兼顾可行性与最优性
- 理论证明误差概率下界，算法逼近最优
- 适合需保证约束条件的决策场景
我们研究分组贝叶斯多臂问题中的固定预算最优臂识别，其中每个臂由多个独立属性构成，且具有随机回报。只有当所有属性的均值均高于给定阈值时，该臂才被视为可行。目标是找出可行臂中整体均值最大的臂。我们首先推导了任意算法在此设置下的误差概率下界。随后提出一种新算法Feasibility Constrained Successive Rejects（FCSR），在保证可行性的同时识别最优臂。理论上证明其对问题参数的依赖关系达到最优量级（常数因子内）。实验表明，FCSR在保持可行性保证的前提下，优于自然基线方法。
原文摘要 · Abstract (English)
We study fixed budget constrained best-arm identification in grouped bandits, where each arm consists of multiple independent attributes with stochastic rewards. An arm is considered feasible only if all its attributes' means are above a given threshold. The aim is to find the feasible arm with the largest overall mean. We first derive a lower bound on the error probability for any algorithm on this setting. We then propose Feasibility Constrained Successive Rejects (FCSR), a novel algorithm that identifies the best arm while ensuring feasibility. We show it attains optimal dependence on problem parameters up to constant factors in the exponent. Empirically, FCSR outperforms natural baselines while preserving feasibility guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。