정책을 밴디트 암으로 취급하는 트리 MDP 의 온라인 학습
요약
본 논문은 트리 마르코프 의사결정 문제(T-MDP)의 온라인 학습 문제를 다루며, 이는 완전 기억을 가진 순차적 게임의 의사결정을 추상화합니다. 연구진은 기존 밴디트 알고리즘인 $\textsc{UCB}$와 $\textsc{LUCB}$를 T-MDP에 적용하는 방법을 제시하며, 정책 수가 상태 수에 지수적으로 증가하는 기술적 난제를 해결했습니다. 핵심 혁신은 데이터 공유 기반의 신뢰 구간 설계로, 이를 통해 밴디트 알고리즘을 다항식 메모리와 단일 단계 계산으로 구현할 수 있게 했으며, 이론적 상한선과 실험적 우수성을 입증했습니다.
핵심 포인트
- T-MDP는 완전 기억을 가진 순차적 게임의 의사결정 과정을 모델링하는 데 사용됩니다.
- 기존 밴디트 알고리즘($\textsc{UCB}$, $\textsc{LUCB}$)을 T-MDP에 적용하여 온라인 학습 문제를 해결했습니다.
- 정책 수의 지수적 증가라는 기술적 난제를 데이터 공유 기반 신뢰 구간 설계로 극복했습니다.
- 이 접근법은 다항식 메모리와 단일 단계 계산으로 구현 가능하며, 샘플 복잡도와 regret에 대한 이론적 상한선을 제공합니다.
트리 마르코프 의사결정 문제 (T-MDP) 는 시작 상태 $s_{1}$ 에서 모든 상태가 정확히 하나의 상태 - 행동 궤적을 통해 도달 가능한 유한 시간 마르코프 의사결정 문제입니다. T-MDP 는 완전 기억을 가진 순차적 게임의 의사결정을 추상화하여 자연스럽게 발생합니다. 우리는 T-MDP 의 온라인 학습 문제를 PAC 와 regret-minimisation(회피 최소화) 제도에 모두 고려합니다. 잘 알려진 밴디트 알고리즘 -- \textsc{Lucb} 과 \textsc{Ucb} -- 는 각 정책을 암으로 취급함으로써 T-MDP 에 적용할 수 있음을 보여줍니다. 이 접근법의 apparent technical challenge(명백한 기술적 도전과제) 는 정책의 수가 상태 수에 지수적으로 증가한다는 점입니다. 우리의 주요 혁신은 데이터 공유를 기반으로 한 신뢰 구간 설계에 있으며, 이를 통해 밴디트 알고리즘은 다항식 메모리와 단 단계 계산으로 구현할 수 있습니다. 우리는 샘플 복잡도와 regret(회피) 에 대한 instance-dependent upper bounds(예상 상한선) 을 얻었으며, 이는 모든 끝 상태의 ``gap term''을 합산하는 방식입니다. 경험적으로, 우리의 알고리즘은 숨겨진 정보 게임의 일련에 대해 기존 대안보다 일관되게 성능이 뛰어납니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기