Key points are not available for this paper at this time.
우리는 의사 결정자의 가능한 행동이 이진 벡터로 표현되는 온라인 선형 최적화 문제를 다룹니다. 의사 결정자의 후회는 그녀가 실현한 손실과 회고적으로 최선의 행동을 선택했을 때 달성할 수 있었던 최소 손실의 차이입니다. 우리의 목표는 최상의 (최악의 경우) 후회의 규모를 이해하는 것입니다. 우리는 의사 결정자가 받는 피드백에 대한 세 가지 다른 가정 하에서 문제를 연구합니다: 완전 정보, 그리고 이른바 "세미 밴딧" 및 "밴딧" 문제의 부분 정보 모델. 완전 정보의 경우, 우리는 표준 지수 가중 평균 예측기가 입증된 비 최적 전략이라는 것을 보여줍니다. 세미 밴딧 모델의 경우, 미러 강하 알고리즘과 INF (암시적 정규화 예측기) 전략을 결합하여 최초의 최적 경계를 증명할 수 있습니다. 마지막으로, 밴딧 경우에는 새로운 하한을 고려하여 기존 결과를 논의하고, 이 경우의 최적 후회에 대한 추측을 제안합니다.
Audibert 외 (Tue,)는 이 질문을 연구했습니다.