정책을 밴디트 암으로 취급하는 트리 MDP 의 온라인 학습

요약

본 논문은 트리 마르코프 의사결정 문제(T-MDP)의 온라인 학습 문제를 다루며, 이는 완전 기억을 가진 순차적 게임의 의사결정을 추상화합니다. 연구진은 기존 밴디트 알고리즘인 $\textsc{UCB}$와 $\textsc{LUCB}$를 T-MDP에 적용하는 방법을 제시하며, 정책 수가 상태 수에 지수적으로 증가하는 기술적 난제를 해결했습니다. 핵심 혁신은 데이터 공유 기반의 신뢰 구간 설계로, 이를 통해 밴디트 알고리즘을 다항식 메모리와 단일 단계 계산으로 구현할 수 있게 했으며, 이론적 상한선과 실험적 우수성을 입증했습니다.

핵심 포인트

• T-MDP는 완전 기억을 가진 순차적 게임의 의사결정 과정을 모델링하는 데 사용됩니다.
• 기존 밴디트 알고리즘($\textsc{UCB}$, $\textsc{LUCB}$)을 T-MDP에 적용하여 온라인 학습 문제를 해결했습니다.
• 정책 수의 지수적 증가라는 기술적 난제를 데이터 공유 기반 신뢰 구간 설계로 극복했습니다.
• 이 접근법은 다항식 메모리와 단일 단계 계산으로 구현 가능하며, 샘플 복잡도와 regret에 대한 이론적 상한선을 제공합니다.