최적의 면(Optimal Faces)을 통한 가격이 책정된 움직임: 비정상적 적대적 MDP를 위한 노멀 팬(Normal-Fan) 기하학

변화하는 의사결정 문제에서, 표준적인 동적 후회 (dynamic-regret) 분석은 종종 비정상성 (non-stationarity)의 비용을 손실 (loss)이 얼마나 멀리 이동하는지와 동일시해 왔습니다. 그러나 손실 시퀀스가 멀리 이동하면서도 동일한 최적 정책 (optimal policy)을 유지하는 것이 동시에 가능할 수 있으며, 반대로 손실의 작은 움직임이 최적 정책을 완전히 바꾸도록 강제할 수도 있습니다. 따라서 손실 변화, 전이 변화, 또는 비교 대상 경로 길이 (comparator path length)를 통한 움직임의 크기는 적대자 (adversary)의 움직임을 설명할 뿐, 제어 문제에 미치는 그 움직임의 비용을 설명하지는 못합니다. 더 충실한 분석적 해석을 위해, 본 논문은 고정된 전이를 가진 유한 지평 적대적 MDP (finite-horizon adversarial MDPs)를 위한 노멀 팬 (normal-fan) 기하학을 개발합니다. 점유 측도 (Occupancy measures)는 다면체 (polytope)를 형성하며, 각 손실 벡터는 해당 다면체의 최적 면 (optimal face)을 드러냅니다. 따라서 보상에서의 비정상성은 노멀 팬을 통과하는 경로이며, 하나의 원뿔 (cone) 내부에서의 움직임은 최적 면을 변하지 않게 유지하는 반면, 벽 (wall)을 가로지르는 것은 후회 (regret)를 초래할 수 있습니다. 우리는 새로운 손실 하에서 이전의 최적 면에 머무름으로써 발생하는 최소 후회인 면 교차 가격 (face-crossing price)이라는 개념을 제안합니다. 이전 면을 추적하는 모든 학습자 (learner)에 대해, 동적 후회 (dynamic regret)는 본질적인 가격이 책정된 면의 움직임 (priced face motion)과 면 내부 선택 오차 (within-face selection error)의 합으로 정확히 분해됩니다. 결과적으로 도출된 이론은 결과적인 비정상성과 무해한 비정상성을 분리하며, 여기서 손실 변화는 0의 가격으로 임의로 클 수 있고, 동일한 하나의 좌표 변화가 후회에 있어 지평 규모 (horizon-scale)의 차이를 숨길 수 있습니다.