기술 요약: 비관측 상태 및 제약된 결정 에포크를 가진 마르코프적 밴딧에서의 학습

1. 문제 정의

본 논문은 다음 두 가지 특정 제약 조건 하에서의 후회 최소화(regret minimization) 문제를 다룹다:

1. 비관측 상태 (Non-observable States): 제어자는 암(arms, 마르코프 체인)의 내부 상태를 관찰할 수 없다. 가용한 피드백은 활성화된 암에서 생성되는 보상뿐이다. 이는 상태 공간이 숨겨진 "풀 밴딧 피드백(full bandit feedback)" 설정에 해당한다.
2. 제약된 결정 에포크 (Constrained Decision Epochs): 제어자는 매 타임 스텝마다 임의로 암을 전환할 수 없다. 대신, 전환은 특정 결정 에포크($\tau_i$)에서만 허용된다. 즉, 결정 에포크는 보상의 흐름(예: 0이 아닌 보상)에 의해 결정되는 정지 시간(stopping times)이다. 구체적으로, 제어자는 특정 신호가 수신될 때까지 하나의 암에 계속 머물러야 한다.

암들은 활성화 여부에 따라 전이 역학(transition dynamics)이 달라지는 마르코프 결정 과정(MDP)으로 모델링된다. 시스템은 비활성화된 암은 수동 커널($p^0_a$)에 따라 전이하고, 활성화된 암은 능동 커널($p^1_a$)에 따라 전이하며 진화한다.

2. 학습 프레임워크 및 벤치마크

저자들은 분석 범위를 "순수 후회(pure regret)" 벤치마크로 제한한다.

• 순수 정책 (Pure Policies): 정책은 학습 호라이즌의 시작부터 끝까지 암을 한 번도 바꾸지 않고 단일 암만을 선택하는 경우 "순수"하다고 정의된다.
• 후회 정의 (Regret Definition): 후회는 학습 알고리즘의 누적 보상과 최적의 순수 정책(가장 높은 점근적 이득을 가진 암)의 누적 보상 간의 차이다.

순수 정책의 동기:
순수 정책은 "레스틀리스(restless)" 밴딧(비활성화된 암이 진화하는 경우)에서는 일반적으로 하위 최적(sub-optimal)일 수 있지만, 저자들은 **자기 퇴화적 레스틀리스 밴딧(self-degrading restless bandits)**이라는 클래스를 도입한다. 이 경우, 암이 비활성 상태로 남겨지면 그 기대 편향(expected bias, 평균 보상으로부터의 편차를 측정하는 척도)이 제어자의 관측치와 비교하여 감소하거나 일정하게 유지된다. 본 논문은 자기 퇴화적 밴딧에 대해 순수 정책이 점근적으로 최적임을 증명한다. 이 클래스는 "레스트(rested)" 밴딧(비활성화된 암이 정지하는 경우)을 일반화하며, 비선점형 길버트-엘리엇 채널(non-preemptive Gilbert-Elliott channels)이나 널럽-애로우(Nerlove-Arrow) 모델과 같은 비자명한 레스틀리스 사례를 포함한다.

3. 방법론: UCB-NOM

본 논문은 UCB 원리에 영감을 받은 낙관적 알고리즘인 UCB-NOM(Non-Observable Markovian bandits를 위한 Upper Confidence Bound)을 제안한다.

UCB-NOM의 핵심 구성 요소:

1. 경험적 이득 추정량 (Empirical Gain Estimator): 알고리즘은 해당 암이 활성화되었을 때 수집된 보상을 평균하여 암 $a$의 이득($g_a$)을 추정한다.
2. 낙관적 인덱스 구축 (Optimistic Index Construction): 상태의 비관측성과 제약 조건을 처리하기 위해, 알고리즘은 실제 이득에 대한 낙관적 상한 $\tilde{g}_a(t)$를 구축한다. 이 인덱스는 다음을 포함한다:
   • 경험적 평균 보상.
   • 다음과 같은 요소를 고려한 탐색 보너스(신뢰 구간):
     • 추출 횟수($N_a(t)$).
     • 알고리즘이 암 $a$로 전환한 횟수(전환 비용).
     • 암의 편향 스팬(bias span, $sp(b_a)$): 편향 함수의 최대 편차를 정량화함.
3. 더블링 트릭 (Doubling Trick): "드물게 전환하는(rarely switching)" 속성을 만족시키기 위해, 알고리즘은 더블링 트릭을 사용한다. 일단 암이 선택되면, 해당 암의 방문 횟수가 두 배가 될 때까지 플레이된다. 이를 통해 전환 횟수가 추출 횟수에 대해 로그 단위로 성장하도록 보장한다.

해결된 이론적 과제:

• 비관측성 (Non-observability): 재생 사이클(regeneration cycles)을 트리거하기 위해 상태 관찰에 의존하는 기존 연구(예: Tekin & Liu의 RCA)와 달리, UCB-NOM은 재생을 사용할 수 없다. 대신, 편향 스팬과 전환 횟수를 사용하여 오차를 제한한다.
• 제약된 에포크 (Constrained Epochs): 알고리즘은 다음 결정 에포크까지의 지연을 고려해야 한다. 분석은 다음 결정 에포크까지의 기대 시간($C_\tau$)에 대한 상한을 가정한다.

4. 주요 결과 및 이론적 보장

A. 하한 (Logarithmic Regret의 불가능성)

본 논문은 밴딧의 구조에 대한 사전 지식 없이, 일관되고 드물게 전환하는 알고리즘을 위해 로그 후회($O(\log T)$)를 달성하는 것은 불가능함을 확립한다.

• 정리 4: 모든 일관되고 드물게 전환하는 알고리즘에 대해, 기대 후회는 $\omega(\log T)$(초로그적, super-logarithmic)로 스케일링된다. 이는 보상만으로는 구별할 수 없지만 서로 다른 최적의 암을 가진 대안 모델을 구성함으로써 증명된다. 이는 알고리즘이 두 모델을 구별하기 위해 하위 최적의 암을 과도하게 추출하도록 강제한다.

B. UCB-NOM 성능 (일반적인 경우)

• 정리 6: UCB-NOM은 $O(f(T)^2 \log T)$의 후회 상한을 달로하며, 여기서 $f(T)$는 무한대로 발산하는 "스팬 프록시(span proxy)" 함수이다.
• 의의: $f(T)$를 임의로 느리게 발산하도록 선택함으로써, UCB-NOM은 이상적인 로그 영역에 임의로 가깝게 접근하여 초로그적 하한에 효과적으로 부합할 수 있다.

C. 사전 지식이 있는 경우의 성능 (유계 편향 스팬)

알고리즘에 모든 암의 편향 스팬에 대한 알려진 상한 $D$(및 결정 에포크 지연)가 제공되는 경우, 성능은 크게 향상된다.

• 정리 8 (사례 의존적): 고정된 스팬 프록시 $f \equiv D$에 대해, UCB-NOM은 $O(\log T)$의 사례 의존적 후회를 달성한다.
• 정리 9 (최악의 경우): 동일한 유계 스팬 가정 하에서, 알고리즘은 $O(\sqrt{T \log T})$의 최악의 경우 후회를 달성한다.

D. 튜닝 및 신뢰 매개변수

본 논문은 신뢰 매개변수 $\delta(t)$의 선택을 분석한다. 마르코프 환경에서는 확률적 밴딧에 비해 "과소 낙관적(under-optimistic)"이 되는 것(더 넓은 신뢰 구간을 위해 더 작은 $\delta(t)$를 선택하는 것)이 선호된다고 제안한다. 이는 편향 스팬으로 인해 마르코프 추정치의 노이즈가 보상의 분산보다 더 클 수 있으며, 낙관적 속성을 유지하기 위해 더 큰 탐색 보너스가 필요하기 때문이다.

5. 의의 및 기여

본 논문은 다음과 같은 기여를 주장한다:

1. 문제 정식화: 통신 네트워크(예: 비선점형 채널 스케줄링)에서 영감을 얻은, 비관측 상태와 내생적 제약 결정 에포크가 결려된 학습 환경을 공식화하였다.
2. 자기 퇴화적 밴딧: 순수 정책이 최적인 레스틀리스 밴딧의 클래스를 식별하고 정의하여, 순수 후회를 벤치마크로 사용하는 정당성을 부여하였다.
3. 근본적 한계: 상태의 비관측성이 제약된 에포크와 결합될 때, 일반적인 경우 로그 후회를 근본적으로 방해하며 초로그적 하한을 설정함을 증명하였다.
4. 알고리즘 설계: 상태 관찰 없이도 근사 최적의 후회를 달성하는 알고리즘인 UCB-NOM을 도입하였다. 결정적으로, 이 알고리즘의 후회 상한은 하부 underlying 마르코프 체인의 상태 수($|S_a|$)가 아니라 편향 스팬에 의존한다.
5. 구조적 통찰: 단순한 사전 지식(편향 스팬의 상한)이 있다면, 고전적인 확률적 밴딧의 로그 후회 보장을 회복할 수 있음을 보여줌으로써, 자기 퇴화적 환경에서 상태 비관측성이 (구조적 상한이 제공될 때) "가벼운 불편함"에 불과함을 입증하였다.

저자들은 본 설정이 표준적인 확률적 밴딧보다 복잡하지만, 제안된 프레임워크와 알고리즘은 순수 후제 벤치마크를 준수하는 한, POMDP와 관련된 복잡한 기법 없이도 견고한 이론적 보장을 제공한다고 결론짓는다.