非平稳线性多臂老虎机最佳臂识别的复杂度研究

该研究针对固定预算非平稳线性多臂老虎机的最佳臂识别（BAI）问题，建立了适用于任意臂集合的理论下界。针对此前 G-optimal 设计忽视几何结构导致复杂度估计过于悲观的问题，研究提出了 Adjacent-optimal 设计及 Adjacent-BAI 算法。其误差概率在常数级别上匹配该下界，确立了该设定下依赖于臂集合的复杂度。