In this paper, we explore online convex optimization (OCO) and introduce a
new analysis that provides fast rates by exploiting the curvature of feasible
sets. In online linear optimization, it is known that if the average gradient
of loss functions is larger than a certain value, the curvature of feasible
sets can be exploited by the follow-the-leader (FTL) algorithm to achieve a
logarithmic regret. This paper reveals that algorithms adaptive to the
curvature of loss functions can also leverage the curvature of feasible sets.
We first prove that if an optimal decision is on the boundary of a feasible set
and the gradient of an underlying loss function is non-zero, then the algorithm
achieves a regret upper bound of $O(\rho \log T)$ in stochastic environments.
Here, $\rho > 0$ is the radius of the smallest sphere that includes the optimal
decision and encloses the feasible set. Our approach, unlike existing ones, can
work directly with convex loss functions, exploiting the curvature of loss
functions simultaneously, and can achieve the logarithmic regret only with a
local property of feasible sets. Additionally, it achieves an $O(\sqrt{T})$
regret even in adversarial environments where FTL suffers an $\Omega(T)$
regret, and attains an $O(\rho \log T + \sqrt{C \rho \log T})$ regret bound in
corrupted stochastic environments with corruption level $C$. Furthermore, by
extending our analysis, we establish a regret upper bound of
$O\Big(T^{\frac{q-2}{2(q-1)}} (\log T)^{\frac{q}{2(q-1)}}\Big)$ for
$q$-uniformly convex feasible sets, where uniformly convex sets include
strongly convex sets and $\ell_p$-balls for $p \in [1,\infty)$. This bound
bridges the gap between the $O(\log T)$ regret bound for strongly convex sets
($q=2$) and the $O(\sqrt{T})$ regret bound for non-curved sets ($q\to\infty$).

基于在线凸优化和曲率的可行集合的分析，本文提出了一种新的方法通过利用可行集合的曲率来实现快速收敛，不仅可以适用于凸损失函数，同时还能在随机、对抗性和受干扰的环境下获得良好的性能。

利用可行集的曲率在在线凸优化中获得快速速率

Fast Rates in Online Convex Optimization by Exploiting the Curvature of  Feasible Sets

Constrained reinforcement learning (CRL) has gained significant interest
recently, since safety constraints satisfaction is critical for real-world
problems. However, existing CRL methods constraining discounted cumulative
costs generally lack rigorous definition and guarantee of safety. In contrast,
in the safe control research, safety is defined as persistently satisfying
certain state constraints. Such persistent safety is possible only on a subset
of the state space, called feasible set, where an optimal largest feasible set
exists for a given environment. Recent studies incorporate feasible sets into
CRL with energy-based methods such as control barrier function (CBF), safety
index (SI), and leverage prior conservative estimations of feasible sets, which
harms the performance of the learned policy. To deal with this problem, this
paper proposes the reachability CRL (RCRL) method by using reachability
analysis to establish the novel self-consistency condition and characterize the
feasible sets. The feasible sets are represented by the safety value function,
which is used as the constraint in CRL. We use the multi-time scale stochastic
approximation theory to prove that the proposed algorithm converges to a local
optimum, where the largest feasible set can be guaranteed. Empirical results on
different benchmarks validate the learned feasible set, the policy performance,
and constraint satisfaction of RCRL, compared to CRL and safe control
baselines.

本文提出了基于可达性分析的 RCRL 方法来解决 CRL 中的安全约束问题，并利用可达性分析来建立新的自洽性条件以及特征化可行集。在多个基准测试中，RCRL 方法展现了优于 CRL 和安全控制基准的可行集、策略绩效和约束满足性。