확률적 결정 집합과 적대적 손실을 가진 온라인 조합 최적화
요약
본 논문은 행동이 고장 나거나 차단될 수 있는 등 신뢰할 수 없는 복합 행동 환경에서 온라인 조합 최적화 문제를 다룹니다. 연구진은 확률적 가용성을 처리하는 새로운 학습 알고리즘을 제안하며, 이는 Follow-The-Perturbed-Leader 예측 방법을 기반으로 합니다. 이 알고리즘은 'Counting Asleep Times'라는 독창적인 손실 추정 기법에 의존하며, 전체 정보, (반-)밴디트, 제한 정보 설정 모두에 대한 후회 경계를 제공하고 기존 방법 대비 성능을 크게 개선했음을 입증했습니다.
핵심 포인트
- 신뢰할 수 없는 복합 행동(unreliable composite actions) 환경에서의 온라인 조합 최적화 문제를 다룸.
- 확률적 가용성(probabilistic availability)을 처리하는 새로운 학습 알고리즘을 제안함.
- 알고리즘은 'Counting Asleep Times'라는 독창적인 손실 추정 기법을 사용함.
- 전체 정보, (반-)밴디트, 제한 정보 설정에 대한 후회 경계(regret bounds)를 제공하며 성능 개선을 입증함.
순차 학습에 관한 대부분의 작업은 항상 이용 가능한 고정된 행동 집합을 가정합니다. 그러나 실제로는 행동이 때때로 고장 나거나 차단될 수 있는 센서에서 읽기를 선택하는 것, 차단될 수 있는 도로 구간, 또는 재고가 없는 물품과 같이 신뢰할 수 없는 복합 행동을 구성할 수 있습니다. 이 논문에서는 이러한 신뢰할 수 없는 복합 행동의 확률적 가용성을 처리할 수 있는 학습 알고리즘을 연구합니다. 우리는 학습자에게 제공되는 피드백이 다른 여러 학습 설정에 대해 Follow-The-Perturbed-Leader 예측 방법을 기반으로 하는 알고리즘을 제안하고 분석합니다. 우리의 알고리즘은 Counting Asleep Times라고 불리는 새로운 손실 추정 기법에 의존합니다. 우리는 이전에 연구된 전체 정보 (full information) 와 (반-)밴디트 ((semi-)bandit) 설정에 대한 알고리즘의 후회 경계 (regret bounds) 를 제공하며, 두 설정 사이의 자연스러운 중간 지점인 제한 정보 (restricted information) 설정에 대해서도 제공합니다. 우리의 결과의 특별한 결과는 확률적 가용성을 가진 수면 밴디트 (sleeping bandit) 문제에서 효율적인 알고리즘이 달성한 가장 잘 알려진 성능 보장에 대한 상당한 개선입니다. 마지막으로, 우리는 알고리즘을 경험적으로 평가하여 알려진 접근법에 비해의 개선을 보여줍니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기