정확한 슬라이딩 윈도우 제약 조건 하의 선형 밴딧

우리는 정확한 슬라이딩 윈도우 제약 조건 하의 선형 밴딧을 연구합니다. 여기서 모든 연속적인 행동 블록은 미리 정해진 실현 가능한 집합에 속해야 합니다. 보상 함수가 알려진 오프라인 설정에서는, 볼록성과 주기적 이동 불변성이 $w
mid T$일 때 정상 상태 해(stationary solution)를 최적으로 만들고, 그렇지 않은 경우에는 추가적인 $O(w)$ 간격 내에서 그렇게 함을 보여줍니다. 온라인 설정에서는, 기하학적 구조만으로는 학습에 불충분하며, 준선형 후회(sublinear regret)가 불가능할 수 있음을 보여줍니다. 우리는 실현 가능한 도달 가능성(feasible reachability)을 정량화하는 전이 직경 $ au$를 도입하고, 오프라인 최적 실현 궤적에 대해 후회가 $ ilde{O}(d
oot{2} ext{T}+ au d+w)$인 희귀 스위칭 OFUL 알고리즘을 개발합니다. 마지막으로, 우리는 주기적 불변성을 제거하고 일반적인 슬라이딩 윈도우 제약 조건을 고려하며, 여기서 최적 행동은 비정상 상태일 수 있습니다. 최근 행동 이력을 유한 메모리 제어 문제의 상태로 표현하고, 실현 가능한 통신을 측정하는 히스토리-상태 직경 $D$를 도입합니다. 낙관적인 남은 호라이즌 계획(optimistic remaining-horizon planning)과 희귀 정책 업데이트를 결합하여, $ ilde{O}(d
oot{2} ext{T}+dD+w)$의 후회 경계를 얻습니다. 우리는 실제 및 합성 벤치마크에서 접근 방식을 평가하고, 정확한 실현 가능성을 유지하면서도 훨씬 적은 정책 업데이트로 기준선과 비교할 수 있는 보상 및 후회를 달성함을 보여줍니다.