Safe Online Convex Optimization with Multi-Point Feedback

本文的研究动机来自于现实世界应用中通常存在的严格安全要求。我们研究了一种安全的在线凸优化设置，其中玩家需要同时实现亚线性遗憾和零约束违规，同时仅使用零阶信息。特别地，我们考虑了多点反馈设置，在该设置下，玩家在每轮中选择$d+1$个点（其中$d$是问题维数），然后接收每个点的约束函数值和成本函数值。为了解决这个问题，我们提出了一种算法，利用前向差分梯度估计以及乐观和悲观的行动集，在约束函数平滑且强凸的假设下实现$\mathcal{O}(d\sqrt{T})$的遗憾和零约束违规。然后，我们进行了数值研究，以调查未知约束和零阶反馈对实证表现的影响。

在安全性要求严格的实际应用中，研究同时实现次线性遗憾和零约束违规的安全在线凸优化设置。

提出了一种算法，利用前向差分梯度估计以及乐观和悲观行动集，在假设约束函数是平滑和强凸的情况下，实现O（d√T）遗憾和零约束违规。

通过数值研究，探讨了未知约束和零阶反馈对实验性能的影响。

相关研究包括：《Safe and Efficient Off-Policy Reinforcement Learning》、《Optimization with First-Order Surrogate Constraints》、《Online Convex Optimization with Long-Term Constraints》等。