arXiv:2412.06165cs.LGcs.AI2024-12被引 3

提出非线性上下文老虎机安全算法,兼顾性能与安全约束。

Conservative Contextual Bandits: Beyond Linear Representations

  • 基于IGW探索与在线回归预言机设计新算法
  • 实现高概率安全约束,且后悔率亚线性
  • 适合需要安全决策的工业场景,如推荐系统

保守上下文老虎机(CCB)通过要求代理策略在最小化遗憾的同时满足安全约束(即性能不超过基线策略的1+α倍)来应对序列决策中的安全性问题。已有工作在多臂和线性上下文设置中提出了UCB类算法,但在实际中动作代价常为非线性函数,导致现有方法失效。本文研究非线性情形下的CCB,提出两个算法C-SquareCB和C-FastCB,采用逆间隙加权(IGW)探索和在线回归预言机。证明安全约束以高概率成立,且C-SquareCB的遗憾为关于时间跨度T的亚线性,C-FastCB的遗憾为关于最优策略累计损失L*的一阶且亚线性。进一步使用神经网络进行函数逼近,以在线梯度下降作为回归预言机,分别获得$ ilde{O}( ext{√}KT + K/α)$ 和 $ ilde{O}( ext{√}KL^* + K(1 + 1/α))$ 的遗憾界。最后在真实数据上验证算法有效性,显著优于现有基线并保持性能保证。

原文摘要 · Abstract (English)

Conservative Contextual Bandits (CCBs) address safety in sequential decision making by requiring that an agent's policy, along with minimizing regret, also satisfies a safety constraint: the performance is not worse than a baseline policy (e.g., the policy that the company has in production) by more than $(1+α)$ factor. Prior work developed UCB-style algorithms in the multi-armed [Wu et al., 2016] and contextual linear [Kazerouni et al., 2017] settings. However, in practice the cost of the arms is often a non-linear function, and therefore existing UCB algorithms are ineffective in such settings. In this paper, we consider CCBs beyond the linear case and develop two algorithms $\mathtt{C-SquareCB}$ and $\mathtt{C-FastCB}$, using Inverse Gap Weighting (IGW) based exploration and an online regression oracle. We show that the safety constraint is satisfied with high probability and that the regret of $\mathtt{C-SquareCB}$ is sub-linear in horizon $T$, while the regret of $\mathtt{C-FastCB}$ is first-order and is sub-linear in $L^*$, the cumulative loss of the optimal policy. Subsequently, we use a neural network for function approximation and online gradient descent as the regression oracle to provide $\tilde{O}(\sqrt{KT} + K/α) $ and $\tilde{O}(\sqrt{KL^*} + K (1 + 1/α))$ regret bounds, respectively. Finally, we demonstrate the efficacy of our algorithms on real-world data and show that they significantly outperform the existing baseline while maintaining the performance guarantee.

强化学习安全决策非线性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。