조합론적 행동 (combinatorial actions)에 대한 많은 온라인 결정 문제들은 볼록 완화 (convex relaxations)를 통해 다루어지며, 이는 조각별 선형 목적 함수 (piecewise linear objectives)와 유도된 다면체 구조 (polyhedral structure)를 갖는 온라인 볼록 최적화 (Online Convex Optimization, OCO)로 이어집니다. 본 연구에서는 이러한 문제에서의 후회 (regret)가 활성 영역 (active region)의 변화 횟수인 '다면체 불안정성 (polyhedral instability)'에 의해 결정됨을 보여줍니다. 완전 정보 피드백 (full information feedback) 및 고정된 분할 (fixed partition) 가정 하에, $\mathrm{RS}T$를 영역 전환 횟수, $V{\max}$를 영역당 최대 정점 (vertices) 수라고 할 때, 우리는 $\Regret_T= Θ(\sqrt{(1+\mathrm{RS}T),T,\log V{\max}})$임을 증명하며, 이는 전문가 기반 (experts-like) 속도와 차원 의존적 (dimension-dependent) OCO 속도 사이를 보간합니다. Lovász 볼록화 (Lovász convexification) 하의 온라인 서브모듈-오목 게임 (online submodular--concave games)의 경우, 이는 순열 전환 횟수 (permutation-switch count) $\mathrm{SC}_T$로 축소되어, $\Regret_T= Θ(\sqrt{(1+\mathrm{SC}_T),T,\log n})$이라는 일치하는 속도를 산출합니다. 합성 및 실제 조합론적 문제 (최단 경로 (shortest path), 영향력 최대화 (influence maximization))에 대한 실험을 통해 예측된 스케일링 (scaling)을 검증하였으며, 행동을 명시적으로 열거하지 않고도 실제 상황에서 낮은 불안정성 영역 (low-instability regimes)이 나타날 수 있음을 보여줍니다.