提出高效安全线性探索算法，计算成本低且性能媲美顶尖方法。
Constrained Linear Thompson Sampling
- 基于扰动线性规划采样，避免复杂优化问题
- 两种变体分别实现零风险与低风险，理论误差约√(d³T)
- 适合需要快速决策的高维安全强化学习场景
我们研究安全线性多臂老虎机（SLBs），即智能体在每轮从凸集选择动作以最大化未知线性目标，同时满足未知线性约束。现有方法虽有强后悔界保证，但需求解代价高昂的优化问题（如二阶锥、NP难问题）。为此，我们提出受限线性汤普森采样（COLTS），一种基于采样的框架，通过求解扰动线性规划显著降低计算开销，同时保持与先前方法相当的后悔和风险水平。我们提出两个主要变体：S-COLTS 在已知安全动作前提下实现零风险和 $ ilde{O}( oot{3}{d^3 T})$ 后悔；R-COLTS 无需实例信息即可达到 $ ilde{O}( oot{3}{d^3 T})$ 后悔与风险。模拟结果显示，该方法性能媲美甚至超越现有最优SLB方法，且可扩展性大幅提升。技术上，我们引入新型耦合噪声设计，确保对真实最优解的频繁局部乐观性，并采用基于缩放的分析处理约束的逐轮波动性。
原文摘要 · Abstract (English)
We study safe linear bandits (SLBs), where an agent selects actions from a convex set to maximize an unknown linear objective subject to unknown linear constraints in each round. Existing methods for SLBs provide strong regret guarantees, but require solving expensive optimization problems (e.g., second-order cones, NP hard programs). To address this, we propose Constrained Linear Thompson Sampling (COLTS), a sampling-based framework that selects actions by solving perturbed linear programs, which significantly reduces computational costs while matching the regret and risk of prior methods. We develop two main variants: S-COLTS, which ensures zero risk and $\widetilde{O}(\sqrt{d^3 T})$ regret given a safe action, and R-COLTS, which achieves $\widetilde{O}(\sqrt{d^3 T})$ regret and risk with no instance information. In simulations, these methods match or outperform state of the art SLB approaches while substantially improving scalability. On the technical front, we introduce a novel coupled noise design that ensures frequent `local optimism' about the true optimum, and a scaling-based analysis to handle the per-round variability of constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。